# On the sum $\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$

Motivated by Question 316142 of mine, I consider the new sum $$S(n):=\sum_{\pi\in S_{n}}e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}$$ for any positive integer $$n$$, where $$S_n$$ is the symmetric group of all the permutations of $$\{1,\ldots,n\}$$. Note that $$S(n)$$ is the permanent of the matrix $$[e^{2\pi ijk/n}]_{1\le j,k\le n}$$. As $$S(n)\equiv\det[e^{2\pi ijk/n}]_{1\le j,k\le n}\pmod2$$, it is easy to see that $$S(n)\equiv n\pmod2$$ in the ring of all algebraic integers.

Suppose that $$S(n)\not=0$$. Then the coefficient of $$x_1^{n-1}\ldots x_n^{n-1}$$ in the polynomial $$P(x_1,\ldots,x_n):=\prod_{1\le j is $$\text{per}[(e^{2\pi ij/n})^{k-1}]\not=0$$. Applying Alon's Combinatorial Nullstellensatz to the subset $$A=\{z\in\mathbb C:\ z^n=1\}$$ of the complex field $$\mathbb C$$, we see that there is a permutation $$\sigma\in S_n$$ such that $$j+\sigma(j)\not\equiv k+\sigma(k)\pmod n$$ for all $$1\le j. Thus $$\sum_{k=1}^n(k+\sigma(k))\equiv\sum_{j=1}^n j\pmod n$$ and hence $$\sum_{k=1}^nk=n(n+1)/2\equiv0\pmod n$$. This shows that $$n$$ must be odd.

Via a computer I find that $$\begin{gather}S(1)=1,\ S(3)=-3,\ S(5)=-5,\ S(7)=-105,\ S(9)=81,、 \\S(11)=6765=3\cdot5\cdot11\cdot41,\ S(13)=175747=11\cdot13\cdot1229, \\ S(15)=30375=3^5\cdot 5^3,\ S(17)=25219857=3\cdot13\cdot17\cdot38039.\end{gather}$$ Thus it is natural for me to formulate the following conjecture.

Conjecture. (i) For each $$n=1,3,5,\ldots$$, the sum $$S(n)$$ is an integer divisible by $$n$$.

(ii) For any odd prime $$p$$, we have $$S(p)\equiv-p\pmod{p^2}$$.

Any ideas towards the solution?

• I don't mean to be rude, but why do you always state your posts as "QUESTION: …? I conjecture that this question has a positive answer" rather than just "CONJECTURE: …."? – LSpice Dec 4 at 3:12
• @LSice Thank you for your inquiry. Indeed, I prefer to state it as a conjecture rather than a question. But Mathoverflow prefers questions and answers. – Zhi-Wei Sun Dec 4 at 3:16
• $S(n)$ is an integer because it is invariant under the Galois group $\mathrm{Gal}(\mathbf{Q}(\zeta_n)/\mathbf{Q})$. If $p$ is an odd prime then $S(p)$ is a sum of $p!$ terms each congruent to 1 mod $1-\zeta_p = 1-e^{2\pi i/p}$. Since the norm of $1-\zeta_p$ is equal to $p$, it follows that $S(p)$ is divisible by $p$. – François Brunault Dec 4 at 5:52

The conjectures are true, and can be recovered from the action of $$({\bf Z} / n {\bf Z})^2$$ on $$S_n$$ by composition from the right and left with translations $$k \mapsto k + a \bmod n$$.

Translation by $$1$$ from either side multiplies $$\exp \frac{2\pi i}{n} \sum_k k \phi(k)$$ by $$\exp\bigl(\pm 2\pi i {n \choose 2} / n\bigr) = \exp(\pm \pi i (n-1))$$, which is $$-1$$ if $$n$$ is even and $$+1$$ if $$n$$ is odd. The even case immediately shows that $$S(n) = 0$$ if $$n$$ is even.

In any case $$S(n) \in \bf Z$$ because $$S(n)$$ is an algebraic integer in the $$n$$-th cyclotomic field $$K_n$$ and the Galois group of $$K_n$$ permutes the summands (conjugate $$\pi$$ by the map $$k \mapsto mk \bmod n$$ for $$m \in ({\bf Z} / n {\bf Z})^*$$).

Since the action of $${\bf Z} / n {\bf Z}$$ from the right is free, the summands come in batches of $$n$$ equal $$n$$-th roots of unity, so $$S(n)/n$$ is also an algebraic integer in $$K_n$$, and thus a rational integer. (We could have used the action from the left to the same effect.)

If $$p$$ is an odd prime then the action of $$({\bf Z} / p {\bf Z})^2$$ is not free but the only permutations with nontrivial stabilizer are the affine-linear maps $$k \mapsto mk + c \bmod p$$ with $$m,c \in {\bf Z} / p {\bf Z}$$ and $$m \neq 0$$. For each of these $$p^2-p$$ permutations, $$\sum_k k \pi(k) \equiv 0 \bmod p$$. Therefore $$S(p)$$ is $$p^2 - p$$ plus a multiple of $$p^2$$, which gives the desired congruence. This argument fails for $$p=3$$ because it uses $$\sum_{k=1}^p k^2 \equiv 0 \bmod p$$, but we already know that $$S(3) = -3$$. This completes the proof.

P.S. this action of $$({\bf Z} / p {\bf Z})^2$$ on $$S_p$$ also gives one combinatorial proof of Wilson's theorem: since the action is free on all but $$p^2-p$$ permutations, we deduce $$p! = \#S_p \equiv p^2-p \bmod p^2$$, which is equivalent to $$(p-1)! \equiv -1 \bmod p$$.

The conjecture is true.

(i) $$S(n)=0$$ when $$n$$ is even. Proof: We identify $$S_n$$ as permutations of the elements of $$\mathbb Z/n\mathbb Z$$. Denote by $$\sigma$$ the permutation which satisfies $$\sigma(i)=i-1$$ for all $$i$$. Then we have $$\frac{\sum_{k=1}^n k\pi(\sigma(k))}{n}=\frac{\sum_{k=1}^n k\pi(k)}{n}+\frac{1+2+\cdots+n}{n}=\frac{\sum_{k=1}^n k\pi(k)}{n}+\frac{n+1}{2}.$$ This means that when $$n$$ is even we have $$e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}+e^{2\pi i\sum_{k=1}^{n}k\pi(\sigma(k))/n}=e^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}(1+e^{\pi i})=0$$ as desired.

(ii) $$S(n)$$ is an integer divisible by $$n$$ when $$n$$ is odd. Proof: With the same definition for $$\sigma$$ as above we have: $$\frac{\sum_{k=1}^n k\pi(\sigma(k))}{n}=\frac{\sum_{k=1}^n k\pi(k)}{n}+\frac{n+1}{2}\equiv\frac{\sum_{k=1}^n k\pi(k)}{n} \pmod{\mathbb Z}$$ therefore $$\sum_{j=0}^{n-1} e^{2\pi i\sum_{k=1}^{n}k\pi(\sigma^j(k))/n}=ne^{2\pi i\sum_{k=1}^{n}k\pi(k)/n}.$$ From here we can make a choice of coset representatives of $$\langle \sigma\rangle$$ in $$S_n$$. Say, $$T_n$$, the permutations which fix $$n$$. Then we can write $$\frac{S(n)}{n}=\sum_{\pi \in T_n}e^{2\pi i\sum_{k=1}^{n-1}k\pi(k)/n}$$ which shows $$S(n)/n$$ is an algebraic integer. Moreover since multiplication by some number $$a$$ relatively prime to $$n$$, is a bijection on elements of $$T_n$$ we have: $$\varphi(n)\frac{S(n)}{n}=\sum_{\gcd(a,n)=1}\sum_{\pi \in T_n}e^{2\pi i\sum_{k=1}^{n-1}ka\pi(k)/n}\in \mathbb Z$$ which means $$S(n)/n$$ is rational and therefore an integer.

(iii) $$S(p)=-p\pmod{p^2}$$. Proof: Similarly to above we have $$S(p)/p=\sum_{\pi\in T_p}e^{2\pi i\sum_{k=1}^{p-1}k\pi(k)/p}$$ and from here we have $$(p-1)\frac{S(p)}{p}=\sum_{a=1}^{p-1}\sum_{\pi\in T_p}e^{2\pi i\sum_{k=1}^{p-1}ka\pi(k)/p}=(p-2)!(p-1)=-1\pmod{p}$$ which gives $$\frac{S(p)}{p}=-1\pmod{p}$$ as desired.