Erdős Problem #228

Erdős Problem #228: flat Littlewood polynomials

Partial reconstruction of the upper bound, 23 September 2026.

1) Statement and scope

For every sufficiently large $n$, the problem asks for a polynomial $P$ of degree $n$, every coefficient equal to $1$ or $-1$, satisfying \[ c\sqrt n\le |P(z)|\le C\sqrt n\qquad(|z|=1) \] with absolute constants $c,C>0$. Balister, Bollobás, Morris, Sahasrabudhe and Tiba proved this. Here we reconstruct an upper bound for every degree, prove a complementary-pair identity, and identify precisely why it fails to supply the required lower bound for one polynomial.

2) Complementary recursion

Set $P_0=Q_0=1$. If $P_j,Q_j$ have $m=2^j$ coefficients, define \[ P_{j+1}=P_j+z^mQ_j,\qquad Q_{j+1}=P_j-z^mQ_j.\tag{1} \] The coefficient ranges of the two summands are disjoint, so both new polynomials have exactly $2m$ coefficients, all equal to $\pm1$. The parallelogram identity gives, on $|z|=1$, \[ |P_{j+1}(z)|^2+|Q_{j+1}(z)|^2 =2\left(|P_j(z)|^2+|Q_j(z)|^2\right). \] Induction from $j=0$ therefore proves \[ |P_j(z)|^2+|Q_j(z)|^2=2^{j+1}=2m.\tag{2} \] In particular, each modulus is at most $\sqrt{2m}$, and at least one of the two is at least $\sqrt m$ at each point of the circle.

3) An upper bound in every degree

The first $2^j$ coefficients of $P_{j+1}$ are those of $P_j$, so the $P_j$ define an infinite sign sequence. Let $R_N$ be its first $N$ terms, viewed as a polynomial of degree $N-1$.

Every aligned coefficient block of length $2^j$ in a sufficiently large $P_J$ is the coefficient list of one of $P_j,-P_j,Q_j,-Q_j$. This follows by repeatedly splitting $1$ into its two equal blocks: a $P$ block splits into $P,Q$, and a $Q$ block into $P,-Q$, with any overall sign preserved. The binary decomposition of an initial block of length $N$ uses at most one aligned block of each length $2^j$, $j\le\lfloor\log_2N\rfloor$. Applying the triangle inequality and $2$ to those blocks, including their harmless powers of $z$, yields \[ \max_{|z|=1}|R_N(z)| \le\sqrt2\sum_{j=0}^{\lfloor\log_2N\rfloor}2^{j/2} \le(2+2\sqrt2)\sqrt N.\tag{3} \] Taking $N=n+1$ supplies the requested upper bound with an absolute constant for every $n\ge1$.

4) Why the pointwise choice of a member is insufficient

Equation $2$ says that $\max(|P_j(z)|,|Q_j(z)|)\ge\sqrt{2^j}$; it does not say that the same member works for all $z$. There is an explicit obstruction in this construction. At $z=-1$, $P_1(-1)=0$ and $Q_1(-1)=2$. For every $j\ge1$, the exponent $2^j$ is even, so $1$ at $-1$ becomes \[ (P_{j+1}(-1),Q_{j+1}(-1)) =(P_j(-1)+Q_j(-1),P_j(-1)-Q_j(-1)). \] Two iterations multiply both entries by two. Hence $P_{2r+1}(-1)=0$ for all $r\ge0$. Infinitely many of these upper-bound polynomials have no positive lower bound on the circle.

Finally, Parseval gives $\frac1{2\pi}\int|R_N(e^{i\theta})|^2d\theta=N$, confirming that $\sqrt N$ is the natural scale. Mean-square size cannot exclude individual zeros.

5) Remaining gap and sources

UNRESOLVED in this attempt. A construction keeping one polynomial uniformly away from zero in every degree has not been reconstructed. The upper bound and complementary-pair statement are complete, but this missing lower bound is essential to the original question.

Sources: https://www.erdosproblems.com/228, checked 23 September 2026; P. Balister, B. Bollobás, R. Morris, J. Sahasrabudhe and M. Tiba, Flat Littlewood polynomials exist, Ann. of Math. 192 $2020$, 977--1004, https://arxiv.org/abs/1907.09464. That paper is the source of the full known resolution; its main theorem is not being substituted for a reconstruction of the missing lower-bound argument.

The estimate describes coverage of the two-sided construction, not a correctness probability.

6) COMPLETION ESTIMATE

COMPLETION: 30%