The flattest polynomials of signs

Random roots crowd onto the circle drew every polynomial whose coefficients are all $+1$ or $-1$ and found their roots clustered on the unit circle. It ended with a question about the polynomials themselves rather than their roots. Such a polynomial — a Littlewood polynomial, after John Edensor Littlewood — has average square size on the unit circle exactly equal to the number of its coefficients, so its typical size there is $\sqrt n$. Can it be flat, staying between two fixed multiples of $\sqrt n$ at every point of the circle? Can it be ultraflat, staying within a factor arbitrarily close to one?

The first question was answered only in 2020, and the second is open. This essay computes what can be computed: three polynomials of sixty-four signs drawn around the circle, the identity that keeps one family bounded above, an exhaustive search through every sign pattern up to length twenty-two, and the sequences of signs the search keeps returning to.

Average size is fixed, the shape is not #

On the unit circle, $z = e^{i\theta}$, a polynomial $p(z) = \sum_{k=0}^{n-1} c_k z^k$ is a sum of rotating arrows of lengths $|c_k|$. Its average squared size around the circle is $\sum |c_k|^2$, because the cross terms $c_j c_k e^{i(j-k)\theta}$ average to nought — this is Parseval’s identity, the same fact that turns Fourier coefficients into energy. For signs, every $|c_k|^2 = 1$, so the average squared size is exactly $n$, whatever the signs are. The computation checks it to six decimal places for each polynomial drawn.

What the signs control is how that fixed amount is distributed around the circle. With every sign $+$, the arrows all line up at $\theta = 0$, where the polynomial is $n$, and almost cancel elsewhere: the whole average is spent at one point. With random signs, the size wanders around $\sqrt n$, rising to two and a half times it and falling to almost nothing in the figure. A flat polynomial would spread the fixed amount evenly, as $\sqrt n$ at every point; Littlewood’s question is how nearly the crudest possible coefficients can achieve that.

Two kinds of failure are possible and they are not symmetric. A polynomial can be too large somewhere — a peak — or too small somewhere — a near-zero. Since the average is fixed, a peak forces the size below average elsewhere, but a near-zero can occur with no peak at all. Controlling the maximum turns out to be easy; controlling the minimum is the hard part of flatness.

An identity that caps the maximum #

In 1951 Harold Shapiro, and in 1959 Walter Rudin independently, found sign polynomials whose maximum on the circle is at most $\sqrt 2$ times $\sqrt n$, for every length that is a power of two.

The construction builds two polynomials at once. Start with $P = Q = 1$. At each step, replace the pair $(P, Q)$ of length $m$ by $(P + z^m Q,\; P - z^m Q)$, of length $2m$. The coefficients stay $\pm 1$, because the new coefficient lists are those of $P$ followed by those of $Q$, or of $-Q$. And at every point of the circle,

$$|P + z^m Q|^2 + |P - z^m Q|^2 = 2\big(|P|^2 + |Q|^2\big),$$

the parallelogram law, because $|z^m| = 1$. Starting from $|P|^2 + |Q|^2 = 2$, the sum doubles at each step along with the length, so for a pair of length $n$ it is exactly $2n$ everywhere — the horizontal line in the figure. Neither square can exceed the sum, so neither polynomial exceeds $\sqrt{2n}$.

That one identity is the whole proof, and the figure shows what it does not give. The two squares trade off against each other: where $|P|^2$ is large $|Q|^2$ is small, and both touch nought somewhere. The Rudin–Shapiro polynomials are bounded above with a constant that holds for every length, and they are not bounded below at all.

The same pair, invented twice #

The Rudin–Shapiro pair has a second life under a different name. Marcel Golay, designing infrared spectrometers in 1949 and 1961, wanted pairs of sign sequences whose self-overlaps cancel: for every shift $k > 0$, the overlap of the first sequence with itself plus the overlap of the second with itself should be exactly nought. Such a pair is a Golay complementary pair, and by the formula connecting overlaps to size on the circle, it is exactly a pair with $|P|^2 + |Q|^2$ constant — the Rudin–Shapiro identity in another language. The doubling construction produces Golay pairs of every length that is a power of two, and other constructions give lengths 10 and 26; combining them gives all lengths of the form $2^a 10^b 26^c$, and no other lengths are known.

The coincidence is a recurring pattern in this subject. An engineer who needs a signal whose energy is spread evenly across frequencies, and a mathematician who wants a polynomial of bounded size on the circle, are asking the same question, because the size of the polynomial at angle $\theta$ is the strength of the signal at frequency $\theta$. Golay’s pairs, Barker’s pulses and Littlewood’s polynomials are three names for one family of objects, and the open problems about them are shared too.

What the complementary pair does not give is a single flat sequence. It spreads the energy evenly across two sequences together, so that each fills in the other’s gaps, and either alone can still nearly vanish at some frequency. Transmitting both, one after the other, is how the engineering uses it; asking for one sequence to do the job alone is Littlewood’s question.

Why a random choice fails at both ends #

A polynomial of random signs fails flatness in both directions, and the reasons are the two halves of elementary probability. At any fixed angle the value is a sum of $n$ random arrows of length one, and by the central limit theorem — the subject of a bell curve assembled out of coin flips — it is approximately a random point of the plane with spread $\sqrt n$ in each direction. Its size is therefore usually near $\sqrt n$, sometimes larger, sometimes smaller.

Around the circle there are about $n$ essentially independent angles, since a polynomial of degree $n$ cannot change much between angles closer than $1/n$. Among $n$ independent bell-shaped values, the largest is about $\sqrt{2\log n}$ standard deviations out, which is where the $\sqrt{n \log n}$ maximum of Salem and Zygmund comes from: how far from the average a thing can be is governed by the tails, and with $n$ chances the tail is reached. At the other end, the chance that a random point of the plane lands within $\varepsilon\sqrt n$ of the origin is about $\varepsilon^2$, so among $n$ angles one of them typically comes within about $1/\sqrt n$ of nought, and the minimum of a random sign polynomial is tiny.

So randomness is the wrong tool on its own: it produces exactly the peaks and the near-zeros that flatness forbids. The 2019 construction uses randomness only as a repair, starting from a structured polynomial that has no peaks and steering a random process that lifts its zeros without creating new peaks — which is the reason it works and a random choice from scratch does not.

Searching every sign pattern #

For short lengths the question can be settled by trying everything. A polynomial with $n$ coefficients has $2^n$ sign patterns, half of which differ only by an overall sign, and for each one the largest and smallest values on the circle can be computed. Changing one coefficient at a time, in the order of a Gray code, lets each new pattern’s values be updated from the last in a single pass, which makes all $2^{21}$ patterns of length 22 a matter of seconds.

The two curves never meet the dashed line. The smallest maximum any sign polynomial achieves is at least 1.146 times $\sqrt n$ at every length searched, and the largest minimum at most 0.838. The best values are irregular in the length — the search finds no smooth trend, only lengths where the signs happen to fit together well — and the best of all are at lengths 7, 11 and 13. At length 7 the lowest maximum drops to 1.173, at 11 to 1.146, and at 13 the largest minimum rises to 0.838, the closest any of these lengths comes to flatness from below.

Those lengths are not accidents. The polynomials that achieve them are Barker sequences: $+++--+-$ of length 7, $+++---+--+-$ of length 11, and $+++++--++-+-+$ of length 13, sign patterns whose shifted copies overlap themselves as little as possible. They were found by Ronald Barker in 1953 for a different reason — they make the best radar pulses, because a pulse that overlaps its own echo only slightly can be timed precisely — and the search, which knows nothing about radar, finds them by itself.

Why a small self-overlap makes a flat polynomial #

The link between overlaps and flatness is one line of algebra. The squared size of $p$ on the circle is

$$|p(e^{i\theta})|^2 = n + 2\sum_{k=1}^{n-1} C_k \cos k\theta, \qquad C_k = \sum_i c_i c_{i+k},$$

where $C_k$ is the aperiodic autocorrelation: the sum of products of the signs that overlap when the sequence is shifted against itself by $k$. If every $C_k$ is small, the squared size stays close to $n$ at every angle, and the polynomial is flat to that extent. For the length-13 Barker sequence every $C_k$ with $k > 0$ is 0 or 1, the smallest possible, and its polynomial stays between 0.84 and 1.39 times $\sqrt{13}$. The computation rebuilds the curve from the overlaps at a scatter of angles and finds the identity exact.

Barker sequences are as flat as sign sequences can be made by this route, and they run out. No Barker sequence of odd length beyond 13 exists — Richard Turyn and Jerome Storer proved that in 1961 — and none of even length beyond 4 is known; a long even one would have to be enormous if it existed, and it is widely believed none does. So the cleanest mechanism for flatness stops at thirteen signs, and long flat polynomials, if they exist, must be flat for a subtler reason than small overlaps.

The maximum as the length grows #

For random signs the maximum grows slowly with the length. A theorem of Raphaël Salem and Antoni Zygmund from 1954 says that for almost every random sign polynomial the maximum on the circle is about $\sqrt{n \log n}$, so the ratio to $\sqrt n$ grows like $\sqrt{\log n}$, without bound but very slowly. The medians in the figure rise from 1.9 at sixteen coefficients to 2.7 at a thousand and twenty-four. The Rudin–Shapiro polynomials stay at or just under $\sqrt 2$ at every length, as their identity guarantees, so for the maximum there is a clean separation: a random choice is unbounded, a clever choice is not.

The minimum is another matter. For random signs it is typically very small, close to nought somewhere on the circle, and for Rudin–Shapiro polynomials it is near nought as well. A sign polynomial bounded away from nought everywhere, with a constant independent of the length, was not known to exist for sixty years.

Flat polynomials exist #

In 2019 Paul Balister, Béla Bollobás, Robert Morris, Julian Sahasrabudhe and Marius Tiba proved that flat Littlewood polynomials exist for every length: there are constants $\delta > 0$ and $\Delta$ such that for every $n$ some sign polynomial of length $n$ satisfies $\delta\sqrt n \le |p(z)| \le \Delta\sqrt n$ on the whole unit circle. Their construction starts from a Rudin–Shapiro-like polynomial, which handles the upper bound, and repairs the places where it is small by adjusting signs according to a carefully controlled random process, so that the small values are lifted without creating large ones.

The proof is probabilistic, in the sense of the graph that coin tosses always make: it shows that a suitable random procedure succeeds with positive probability, and so does not produce a single explicit polynomial. The constants it gives are far from the values the exhaustive search finds at short lengths. So the situation is that flatness is possible, an explicit long flat polynomial is not known, and the best explicit ones are bounded above but not below.

How close to the square root of the length #

Flatness allows any constants $\delta$ and $\Delta$. Ultraflatness asks for both to approach 1: a sequence of polynomials whose size on the circle is $(1 + o(1))\sqrt n$ everywhere. For polynomials whose coefficients are complex numbers of size one — arrows of unit length pointing in any direction — Jean-Pierre Kahane proved in 1980 that ultraflat polynomials exist. With real signs the arrows can only point forwards or backwards, and that restriction appears to matter.

Paul Erdős conjectured that it matters decisively: that every sign polynomial reaches at least $(1 + c)\sqrt n$ somewhere on the circle, for a fixed $c > 0$. The exhaustive search is consistent with that — the smallest maximum never drops below 1.146 times $\sqrt n$ up to length 22 — but lengths of twenty-two say nothing about lengths of a million. A related question asks for the smallest possible average of the fourth power of the size, measured by the merit factor, and there too the conjectured best constants come from computer searches and from algebraic constructions based on quadratic residues, and no proof matches them.

A question about cancellation #

All of these questions are about how much cancellation a sum of $n$ rotating arrows of fixed length can be forced into, using only the choice of which way each one points. The arrows in the sums of roots of unity that add to nothing pointed in the directions of roots of unity and cancelled completely, at one angle. Here each has length one and only two possible directions, and the question is whether, by choosing directions cleverly, the sum can be kept uniformly sized as the angle turns.

The upper bound comes from algebra: the Rudin–Shapiro doubling preserves an identity that caps the size. The lower bound comes from probability: a guided random process avoids the small values. Ultraflatness would need both at once, to an accuracy that tends to perfect, and the evidence from short lengths is that sign polynomials cannot get much closer than about 1.15 at the top or 0.84 at the bottom, at least not by length 22.

What the search does not show #

The exhaustive search samples the circle at eight points per coefficient and then refines each length’s winning polynomials on a grid sixteen times finer, so the reported extremes are accurate to well under a per cent, and the identity of the winners is reliable. But the winners are the best among polynomials of length up to 22, and nothing measured there constrains the best polynomials of length 1,000 except the theorems. That the flattest short polynomials are Barker sequences is exactly the kind of small-case pattern that need not persist, and with no Barker sequences beyond 13 it cannot.

The random polynomials in the growth figure are a median of twelve at each length; the theorem of Salem and Zygmund describes the typical behaviour, and twelve samples show it only roughly.

Still open: ultraflat signs #

Whether there is a sequence of sign polynomials whose size on the unit circle is $(1 + o(1))\sqrt n$ everywhere — Erdős’s question, in the form that he conjectured has the answer no — is open. It is not even known whether the constant $\Delta$ in the flatness theorem can be brought below $\sqrt 2$, the Rudin–Shapiro bound, while keeping a lower bound at all; the 2019 construction pays for its lower bound with a larger upper one.

Two neighbouring questions are open in the same way. The largest possible merit factor of long sign sequences — the reciprocal of how far the fourth moment of $|p|$ exceeds the second moment squared — is conjectured to be about 6.34, achieved by shifted Legendre-symbol sequences, and no proof shows that larger values are impossible. And whether any Barker sequence of even length longer than 4 exists is open, with the smallest possible length, if any exists, known to be astronomically large. Each is a question about how evenly signs can spread energy across frequencies, and each has resisted the algebra that settles the upper bound and the probability that settles flatness.