Power sums of p-th roots of unity

Question

The following question was asked by a colleague of mine. For any prime $p$ consider $$ M_p:=\min_{z_1,\dots,z_p}\max_{j,k}\left|z_1^k+\dots+z_j^k\right|,$$ where $z_1,\dots,z_p$ are the complex $p$-th roots of unity in any order, and $j,k\in\{1,\dots,p-1\}$ are arbitrary. Is $M_p$ bounded?

Answer 1

This is closely related to the problems surrounding Turán's power sum method. For example see the chapter in Montgomery's Ten Lectures book, or this paper of Gonek. Lemma 1 (attributed to Cassels) there shows that if $b_j >0$, and $|z_j|=1$ (for $j=1$, $\ldots$, $N$) then for $K>N$ $$ \max_{k\le K} \Big| \sum_{j=1}^{N} b_j z_j^k \Big| \ge \frac{\sqrt{K-N}}{\sqrt{K}} \Big(\sum_{j=1}^{N} b_j^2 \Big)^{\frac 12}. $$ Now apply this in your situation with $N=(p-1)/2$ (this is $j$ in your problem) and $K=(p-1)$ to get essentially the result you have. Of course your proof is easy enough in this case, but I thought you might appreciate the general context.

Answer 2

I think I can answer my own question (which is really my colleague's question).

Let $p>2$, and let $j\in\{1,\dots,p-1\}$ be fixed. Then $$ \sum_{k=1}^{p-1}\left|z_1^k+\dots+z_j^k\right|^2 = \sum_{k=1}^{p-1}\sum_{1\leq i,i'\leq j} z_i^k \overline{z_{i'}^k} = \sum_{1\leq i,i'\leq j} \sum_{k=1}^{p-1} (z_i/z_{i'})^k. $$ On the right hand side, the inner sum equals $p-1$ when $i=i'$, and it equals $-1$ when $i\neq i'$. Hence $$ \sum_{k=1}^{p-1}\left|z_1^k+\dots+z_j^k\right|^2 = j(p-1)-j(j-1)=j(p-j),$$ and we infer $$ \max_k\left|z_1^k+\dots+z_j^k\right|\geq\sqrt{\frac{j(p-j)}{p-1}}. $$ Choosing $j:=(p-1)/2$, we get $$ \max_{j,k}\left|z_1^k+\dots+z_j^k\right|\geq\frac{\sqrt{p+1}}{2}. $$ That is, $M_p$ is at least $\sqrt{p+1}/2$, and so it is not bounded.