This is Problem 4.31 in [Ha74], in which it is described as a conjecture of Erdős and Newman.

The lower bound of $\sqrt{n}$ is trivial from Parseval's theorem. The answer is no (contrary to Erdős' initial guess). Kahane [Ka80] constructed 'ultraflat' polynomials $P(z)=\sum a_kz^k$ with $\lvert a_k\rvert=1$ such that\[P(z)=(1+o(1))\sqrt{n}\]uniformly for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$, where the $o(1)$ term $\to 0$ as $n\to \infty$.

For more details see the paper [BoBo09] of Bombieri and Bourgain and where Kahane's construction is improved to yield such a polynomial with\[P(z)=\sqrt{n}+O(n^{\frac{7}{18}}(\log n)^{O(1)})\]for all $z\in\mathbb{C}$ with $\lvert z\rvert=1$.


See also [228].

View the LaTeX source

This page was last edited 29 December 2025.