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<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?
 A: 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$.
A: 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.
