Littlewood polynomial

Roots of all Littlewood polynomials of degree 16.

Roots of all Littlewood polynomials of degrees 1 through 14.

In mathematics, a Littlewood polynomial is a polynomial whose coefficients are all either $1$ or $-1$. Equivalently, its coefficient vector is a finite binary sign sequence. Littlewood polynomials are named after J. E. Littlewood, who studied their values on the unit circle and posed several influential extremal problems about them in the 1960s.

The natural size of a Littlewood polynomial of degree $n$ on the unit circle is $\sqrt{n+1}$, because its normalized $L^2$ norm is exactly that value. A central question asked whether the modulus could remain between two fixed positive multiples of $\sqrt{n+1}$ at every point of the circle. Littlewood conjectured that this was possible; the conjecture was proved in 2020 by Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe, and Marius Tiba. Stronger questions about asymptotically constant modulus, extremal $L^q$ norms, Mahler measure, zero distribution, and autocorrelation remain active.

Definition and elementary properties

A polynomial $$P(z)=\sum _{j=0}^n{a}_j{z}^j$$ is a Littlewood polynomial of degree $n$ if $a_j\in \{-1,1\}$ for every $j$. There are $2^{n+1}$ such polynomials. Multiplication by $-1$, the substitution $z\mapsto -z$, and passage to the reciprocal polynomial $$P^{\ast }(z)=z^{n}P(1/z)$$ preserve the class. These operations account for many of the natural symmetries used in enumerations.

Every zero $\alpha$ of a Littlewood polynomial satisfies $$\frac{1}{2}<|\alpha |<2.$$ Indeed, when $|z|\le 1/2$, the constant term has greater modulus than the sum of all remaining terms, and the upper bound follows by applying the same argument to the reciprocal polynomial.

For $0<q<\mathrm{\infty }$, its normalized norm on the unit circle is $$\Vert P{\Vert }_q={(\frac{1}{2\pi }{\int }_0^{2\pi }|P(e^{it}){|}^{q}dt)}^{1/q},$$ and $\Vert P{\Vert }_{\mathrm{\infty }}=\underset{|z|=1}{max}|P(z)|$. Parseval's identity gives $$\Vert P{\Vert }_2^2=\sum _{j=0}^n|a_j{|}^2=n+1.$$ Thus $\sqrt{n+1}$ is the root-mean-square modulus and the reference scale in flatness problems.

Flatness on the unit circle

A sequence of Littlewood polynomials $(P_n)$, with $\mathrm{deg}{P}_n=n$, is called flat if there are absolute constants $0<c<C$ such that $$c\sqrt{n+1}\le |P_n(z)|\le C\sqrt{n+1}(|z|=1)$$ for every $n$ in the sequence. The upper and lower bounds play different roles: the upper bound limits peaks, while the lower bound excludes zeros and deep troughs on the unit circle.

Rudin–Shapiro polynomials

The Rudin–Shapiro polynomials provide a classical explicit upper-bound construction. Define $$P_0(z)=Q_0(z)=1,$$ and recursively $$\begin{array}{cc}{P}_{m+1}(z)& =P_m(z)+z^{2^m}{Q}_m(z),\\ Q_{m+1}(z)& =P_m(z)-z^{2^m}{Q}_m(z).\end{array}$$ Both $P_m$ and $Q_m$ are Littlewood polynomials with $N=2^m$ coefficients. On the unit circle they satisfy $$|P_m(z){|}^2+|Q_m(z){|}^2=2N,$$ and hence $\Vert P_m{\Vert }_{\mathrm{\infty }},\Vert Q_m{\Vert }_{\mathrm{\infty }}\le \sqrt{2N}$. This does not by itself give a uniform positive lower bound. Rodgers proved in 2017 that suitably normalized values of the Rudin–Shapiro polynomials become uniformly distributed in the unit disk. In 2026, Erdélyi quantified their oscillation around the middle of their range, proving upper and lower bounds for the number of solutions of $|P_m(e^{it}){|}^2=N$ and $|Q_m(e^{it}){|}^2=N$ on every subarc of the unit circle.

Littlewood's flatness conjecture

Littlewood conjectured in 1966 that flat Littlewood polynomials exist. An influential earlier contribution was József Beck's 1991 paper on flat polynomials and Littlewood's problem. Balister, Bollobás, Morris, Sahasrabudhe, and Tiba proved the stronger statement that there are absolute constants $\mathrm{\Delta }>\delta >0$ such that, for every $n\ge 2$, some Littlewood polynomial $P$ of degree $n$ satisfies $$\delta \sqrt{n}\le |P(z)|\le \mathrm{\Delta }\sqrt{n}(|z|=1).$$ Their proof combines discrepancy theory with probabilistic and combinatorial methods. It resolved Littlewood's 1966 conjecture after more than five decades.

Ultraflat polynomials

A sequence is ultraflat if $$\underset{|z|=1}{max}|\frac{|P_n(z)|}{\sqrt{n+1}}-1|⟶0.$$ Jean-Pierre Kahane proved that ultraflat sequences exist when the coefficients are allowed to be arbitrary complex numbers of modulus $1$. Bombieri and Bourgain later obtained stronger quantitative constructions in this unimodular setting. Erdős conjectured that no ultraflat Littlewood sequence exists. The general $\{-1,1\}$ problem remains open in the peer-reviewed literature; bounded flatness, proved in 2020, is substantially weaker than ultraflatness.

Autocorrelation, $L^4$ norm, and merit factor

Let $P(z)=\sum _{j=0}^{N-1}{a}_j{z}^j$, and define the nontrivial aperiodic autocorrelations $$C(k)=\sum _{j=0}^{N-1-k}{a}_j{a}_{j+k}(1\le k<N).$$ Expanding the squared modulus gives $$|P(e^{it}){|}^2=N+2\sum _{k=1}^{N-1}C(k)\cos (kt),$$ and Parseval then yields the exact identity $$\Vert P{\Vert }_4^4=N^2+2\sum _{k=1}^{N-1}C(k{)}^2.$$ Consequently, minimizing the $L^4$ norm is equivalent to minimizing the total squared aperiodic autocorrelation.

The associated merit factor is $$F(P)=\frac{N^2}{2\sum _{k=1}^{N-1}C(k{)}^2}=\frac{N^2}{\Vert P{\Vert }_4^4-N^2}.$$ High merit factor means that the coefficient sequence has low aggregate autocorrelation. This problem originated in communications and signal design and has generated a large literature on character sequences, difference sets, and recursive constructions.

A Barker sequence is a sign sequence satisfying $|C(k)|\le 1$ for every nonzero shift. Such sequences therefore produce exceptionally small $L^4$ defect. Barker sequences are known only for lengths $1,2,3,4,5,7,11,13$; no odd Barker sequence has length greater than $13$, while the existence of a longer even one remains open.

Arithmetic constructions also provide tractable norm problems. For an odd prime $p$, the Fekete polynomial $$f_p(z)=\sum _{j=1}^{p-1}\left(\frac{j}{p}\right)z^j$$ is defined using the Legendre symbol; $z^{-1}{f}_p(z)$ is a Littlewood polynomial. Explicit limiting formulas are known for its normalized even $L^q$ norms and for related finite-field character polynomials.

Mahler measure

The Mahler measure of a nonzero polynomial is the geometric mean of its modulus on the unit circle, $$M(P)=\exp (\frac{1}{2\pi }{\int }_0^{2\pi }\log |P(e^{it})|dt).$$ It satisfies $M(P)\le \Vert P{\Vert }_2=\sqrt{N}$ for a Littlewood polynomial with $N$ coefficients. Flat Littlewood polynomials have Mahler measure comparable to $\sqrt{N}$ because their modulus has a uniform lower bound of that order.

For the Rudin–Shapiro polynomials, Erdélyi first proved a lower bound of order $\sqrt{N}$ and later proved Saffari's conjectured asymptotic $$M(P_m)\sim M(Q_m)\sim \sqrt{\frac{2N}{e}}(N=2^m).$$ Mahler measure also links Littlewood polynomials to algebraic-number-theoretic questions about reciprocal polynomials and small algebraic integers. For example, Borwein, Hare, and Mossinghoff determined the minimum Mahler measure of a nonreciprocal polynomial with all coefficients odd and computed the smallest measures of reciprocal Littlewood polynomials through degree $72$.

Zeros

The distribution of zeros of Littlewood polynomials is highly varied despite the elementary coefficient restriction. Some polynomials have roots on the unit circle, while others have none. For degrees $n$ with $n+1$ prime, Borwein, Choi, Ferguson, and Jankauskas proved that for every $0\le k\le n-1$ there is a degree-$n$ Littlewood polynomial with exactly $k$ zeros in the open unit disk and no zeros on its boundary.

A random Littlewood polynomial has independent coefficients taking the values $1$ and $-1$ with equal probability. This model goes back to work of Littlewood and Offord on random algebraic equations. Yakir proved that, as $N\to \mathrm{\infty }$, all but $o(2^N)$ Littlewood polynomials with $N$ coefficients have $N/2+o(N)$ zeros inside the unit disk. For the same Rademacher coefficient model, Do, Nguyen, and Vu proved that the expected number of real roots of a degree-$n$ polynomial is $$\frac{2}{\pi }\log n+C+o(1),$$ where $C$ is a constant depending on the coefficient distribution.

Random coefficients also have a predictable norm profile. Borwein and Lockhart obtained asymptotic expected $L^q$ norms for broad classes of independent coefficients, and Duan, Fang, and Zhan proved in 2024 that for random Littlewood polynomials $P_N$ with $N$ coefficients, $$\frac{\Vert P_N{\Vert }_4}{\sqrt{N}}⟶2^{1/4}$$ almost surely.

Arithmetic and algebraic questions

Littlewood polynomials also give rise to Diophantine and Galois-theoretic problems. Hajdu, Herendi, Tengely, and Varga studied when a Littlewood polynomial takes a square value at an integer argument. They classified the square values for degrees $3$ and $5$ and for every even degree at most $24$, and gave computational data for odd degrees at most $17$.

For random Littlewood polynomials, it is conjectured that the probability of irreducibility tends to $1$ with the degree. In 2025, Bary-Soroker, Hokken, Kozma, and Poonen proved unconditionally that $$\underset{n\to \mathrm{\infty }}{lim\; sup}Pr(P_n\text{ is irreducible})=1.$$ More precisely, there is a constant $c>0$ such that, when $n=p^r-1$, with $p=2$ or with $p\ge 7$ a prime for which $2$ generates $(\mathbb{Z}/p^2\mathbb{Z}{)}^{\times }$, a random degree-$n$ Littlewood polynomial is irreducible with probability at least $1-n^{-c}$.

For reciprocal and skew-reciprocal Littlewood polynomials, Hokken obtained leading-term asymptotics for the number having square discriminant. The result is related to a bounded-height analogue of a conjecture of van der Waerden on Galois groups of random polynomials.

Values at roots of unity

For a Littlewood polynomial with $N$ coefficients, define the periodic autocorrelations $$R(t)=\sum _{j=0}^{N-1}{a}_j{a}_{j+tmodN}.$$ If $\omega =e^{2\pi i/N}$, the discrete Fourier transform gives $$|P({\omega }^k){|}^2=\sum _{t=0}^{N-1}R(t){\omega }^{kt}.$$ Therefore $$|P({\omega }^k)|=\sqrt{N}(0\le k<N)$$ if and only if $R(0)=N$ and every nontrivial periodic autocorrelation is zero. The circulant matrix whose first row is $(a_0,\dots ,a_{N-1})$ is then a circulant Hadamard matrix.

Ryser's conjecture on circulant Hadamard matrices states that this exact discrete flatness occurs only for $N=1$ and $N=4$. The required modulus is therefore $\sqrt{N}$. A quantitative strengthening proposed by Steinerberger asks whether there is an absolute ${\epsilon }_0>0$ such that every Littlewood polynomial of length $N>4$ satisfies $$\underset{0\le k<N}{max}||P({\omega }^k)|-\sqrt{N}|\ge {\epsilon }_0{N}^{1/4}.$$

Related coefficient classes

Several nearby families are studied with similar methods. Newman polynomials have coefficients in $\{0,1\}$, while Borwein polynomials have coefficients in $\{-1,0,1\}$. Unimodular polynomials allow arbitrary complex coefficients of absolute value $1$; Kahane's ultraflat construction belongs to this larger class. Fekete polynomials are character polynomials with coefficients given by Legendre symbols, and after removal of their zero constant coefficient they give Littlewood polynomials. Cyclotomic Littlewood polynomials, whose roots are all roots of unity, form another structured subclass with explicitly computable norms.

Open problems

The 2020 flatness theorem settles the existence of uniformly bounded upper and lower constants, but does not determine optimal constants or produce ultraflat Littlewood polynomials. The existence or nonexistence of an ultraflat Littlewood sequence remains a central open question. Other major problems include determining the optimal asymptotic merit factor, or equivalently the smallest possible normalized $L^4$ norm; deciding whether Barker sequences of length greater than $13$ exist; resolving Ryser's conjecture on exact flatness at roots of unity; and proving that a random Littlewood polynomial is irreducible with probability tending to $1$ without restricting the degree to special subsequences.

See also

• Barker code
• Fekete polynomial
• Mahler measure
• Rudin–Shapiro sequence
• Shapiro polynomials
• Ryser's conjecture on circulant Hadamard matrices

Further reading

• Template:Cite book
• Template:Cite book