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<k\le n}(x_k-x_j)\left(e^{2\pi ik/n}x_k-e^{2\pi ij/n}x_j\right)$$ 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<k\le n$. 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?

  • 1
    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
  • 1
    $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.

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.