IMC 2016 · Day 1 · P5

We will use the well-known formula $$\sum_{\pi \in S_n} x^{\mathrm{inv}(\pi)} = 1 \cdot (1 + x) \cdot (1 + x + x^2) \dots (1 + x + \dots + x^{n-1}).$$ (This formula can be proved by induction on $n$. The cases $n = 1, 2$ are obvious. From each permutation of $(1, 2, \dots, n-1)$, we can get a permutation of $(1, 2, \dots, n)$ such that we insert the element $n$ at one of the $n$ possible positions before, between or after the numbers $1, 2, \dots, n-1$; the number of inversions increases by $n-1, n-2, \dots, 1$ or $0$, respectively.)

Now let $$G_n(x) = \sum_{\pi \in S_n} x^{\mathrm{inv}(\pi)}.$$ and let $\varepsilon = e^{\frac{2\pi i}{n+1}}$. The sum of coefficients of the powers divisible by $n + 1$ may be expressed as a trigonometric sum as $$f(n) = \frac{1}{n+1} \sum_{k=0}^{n-1} G_n(\varepsilon^k) = \frac{n!}{n+1} + \frac{1}{n+1} \sum_{k=1}^{n-1} G_n(\varepsilon^k).$$ Hence, we are interested in the sign of $$f(n) - \frac{n!}{n+1} = \sum_{k=1}^{n-1} G_n(\varepsilon^k)$$ with $n = p - 1$ where $p$ is a (large, odd) prime.

For every fixed $1 \le k \le p - 1$ we have $$G_{p-1}(\varepsilon^k) = \prod_{j=1}^{p-1} (1 + \varepsilon^k + \varepsilon^{2k} + \dots + \varepsilon^{(j-1)k}) = \prod_{j=1}^{p-1} \frac{1 - \varepsilon^{jk}}{1 - \varepsilon^k} = \frac{(1 - \varepsilon^k)(1 - \varepsilon^{2k}) \cdots (1 - \varepsilon^{(p-1)k})}{(1 - \varepsilon^k)^{p-1}}.$$ Notice that the factors in the numerator are $(1 - \varepsilon)$, $(1 - \varepsilon^2)$, …, $(1 - \varepsilon^{p-1})$; only their order is different. So, by the identity $(z - \varepsilon)(z - \varepsilon^2) \dots (z - \varepsilon^{p-1}) = 1 + z + \dots + z^{p-1}$, $$G_{p-1}(\varepsilon^k) = \frac{p}{(1 - \varepsilon^k)^{p-1}} = \frac{p}{\bigl( 1 - e^{\frac{2k\pi i}{p}} \bigr)^{p-1}}.$$ Hence, $f(p-1) - \frac{(p-1)!}{p}$ has the same sign as $$\begin{align*} \sum_{k=1}^{p-1} \bigl( 1 - e^{\frac{2k\pi i}{p}} \bigr)^{1-p} &= \sum_{k=1}^{p-1} e^{\frac{k(1-p)\pi i}{p}} \left( -2i \sin\frac{\pi k}{p} \right)^{1-p} = \\ &= 2 \cdot 2^{1-p} (-1)^{\frac{p-1}{2}} \sum_{k=1}^{\frac{p-1}{2}} \cos\frac{\pi k (p-1)}{p} \left( \sin\frac{\pi k}{p} \right)^{1-p}. \end{align*}$$ For large primes $p$ the term with $k = 1$ increases exponentially faster than all other terms, so this term determines the sign of the whole sum. Notice that $\cos\frac{\pi (p-1)}{p}$ converges to $-1$. So, the sum is positive if $p - 1$ is odd and negative if $p - 1$ is even. Therefore, for sufficiently large primes, $f(p-1) - \frac{(n-1)!}{p}$ is positive if $p \equiv 3 \pmod 4$ and it is negative if $p \equiv 1 \pmod 4$.