8
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ This feels to me like looking for increasing consecutive subsequences in one of a set of related permutations. My guess is that $M_p$ is $\Omega(\sqrt{p})$. Gerhard "Not Just A Random Walk" Paseman, 2016.06.28. $\endgroup$ Jun 28, 2016 at 16:52
  • $\begingroup$ @GerhardPaseman: Your intuition was right, see my response below. $\endgroup$
    – GH from MO
    Jun 28, 2016 at 17:58

2 Answers 2

8
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ Dear Lucia, indeed I appreciate your response and the general context! $\endgroup$
    – GH from MO
    Jun 29, 2016 at 7:40
  • $\begingroup$ It is worth pointing out (for the readers of this page) that the relevant result in Montgomery's book is Theorem 8 on Page 98, and it relies on the positivity of Fejér's kernel. $\endgroup$
    – GH from MO
    Jun 29, 2016 at 7:56
8
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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