International Mathematics Competition
for University Students
2016

IMC2016: Day 1, Problem 5

5. Let $S_n$ denote the set of permutations of the sequence $(1,2,\dots,n)$. For every permutation $\pi=(\pi_1,\dots,\pi_n)\in S_n$, let $\mathrm{inv}(\pi)$ be the number of pairs $1\le i\lt j\le n$ with $\pi_i\gt \pi_j$; i.e. the number of inversions in $\pi$. Denote by $f(n)$ the number of permutations $\pi\in S_n$ for which $\mathrm{inv}(\pi)$ is divisible by $n+1$.

Prove that there exist infinitely many primes $p$ such that $f(p-1)\gt \dfrac{(p-1)!}p$, and infinitely many primes $p$ such that $f(p-1)\lt \dfrac{(p-1)!}p$.

Proposed by Fedor Petrov, St. Petersburg State University

Solution. 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,\ldots,n-1)$, we can get a permutation of $(1,2,\ldots,n)$ such that we insert the element $n$ at one of the $n$ possible positions before, between or after the numbers $1,2,\ldots,n-1$; the number of inversions increases by $n-1,n-2,\ldots,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) = \frac1{n+1} \sum_{k=0}^{n-1} G_n(\varepsilon^k) = \frac{n!}{n+1} + \frac1{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}+\ldots+\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)$, \dots, $(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}{\big(1-e^{\frac{2k\pi i}{p}}\big)^{p-1}}. $$ Hence, $f(p-1)-\frac{(p-1)!}{p}$ has the same sign as $$ \sum_{k=1}^{p-1} (1-e^{\frac{2k\pi i}{p}})^{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}. $$ 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\equiv3\pmod4$ and it is negative if $p\equiv1\pmod4$.