A quarter turn quiets the echoes

A radar pulse is a sequence of signs: transmit a burst for $+1$, invert it for $-1$, and listen for the echo. The receiver slides the known pattern along what comes back and looks for the moment of best agreement. If the pattern agrees with itself only when perfectly aligned, the echo arrives as one sharp spike and its timing is exact. If the pattern also half-agrees with itself at some shift, every echo arrives with ghosts beside it.

The flattest polynomials of signs took that pattern as the coefficients of a polynomial and asked how close its size can stay to $\sqrt n$ at every point of the unit circle. That is the hardest form of the question, because one bad point spoils it. Marcel Golay asked a softer one in 1972: not the worst agreement at any shift, but the total of all of them, squared and added. That total has a clean meaning on the circle and a clean meaning to an engineer, and it leads to a result with no business being true — that the squares modulo a prime, written as signs and turned a quarter of the way round, give one of the quietest sequences known.

Overlaps added up as squares #

Write the signs as $a_0, a_1, \ldots, a_{n-1}$, each $+1$ or $-1$. Shift a copy by $k$ places and multiply the signs that now sit together; agreements count $+1$ and disagreements $-1$. The total

$$C_k = \sum_{j=0}^{n-1-k} a_j a_{j+k}$$

is the overlap at shift $k$. At $k = 0$ every sign meets itself and $C_0 = n$. The other overlaps are the ghosts. Golay’s measure adds their squares,

$$E = \sum_{k=1}^{n-1} C_k^2, \qquad F = \frac{n^2}{2E},$$

and calls $F$ the merit factor. A larger $F$ means quieter ghosts. The factor 2 and the $n^2$ are chosen so that the measure does not drift with the length, as the next figure explains.

In the hero the random sequence has overlaps as large as 9, and the squares add to 552, so its merit factor is $1681/1104 \approx 1.52$. The second sequence was built from arithmetic rather than from coin tosses, and its largest overlap is 7 while its squares add to 176, a merit factor of 4.78. Nothing about it looks special to the eye. It has 21 plus signs and 20 minus signs and no visible pattern, and yet two-thirds of the random sequence’s echo energy has gone.

A random sequence is easy to analyse. For a fixed $k$, the overlap $C_k$ is a sum of $n - k$ independent signs, so its square has average exactly $n - k$. Adding over $k$ gives an expected $E$ of $n(n-1)/2$, and a merit factor close to 1. That is the baseline: anything that reliably beats 1 at long lengths has to be built.

The same number on the unit circle #

The overlaps are also the Fourier coefficients of a single function. Put $p(z) = \sum a_j z^j$ and look at it on the unit circle, $z = e^{i\theta}$. Multiplying $p$ by its conjugate collects terms by the difference of their exponents, and the coefficient of each difference is an overlap:

$$|p(e^{i\theta})|^2 = n + 2\sum_{k=1}^{n-1} C_k \cos k\theta .$$

Averaged round the circle every cosine vanishes, which leaves $n$: the average of $|p|^2$ is the length, whatever the signs. That is the identity the flattest polynomials started from. The next average is the one that sees the signs. Squaring and averaging again, each cosine contributes half its squared coefficient, so

$$\text{average of } |p|^4 = n^2 + 2E .$$

Divide $|p|^2$ by $n$ to make a curve whose mean is 1. Its mean square is $1 + 2E/n^2 = 1 + 1/F$, and so its variance is exactly $1/F$. The merit factor is one over the variance of the curve.

The figure computes both averages from 601 points and finds 1.655 and 1.207 against the exact 1.657 and 1.209, so the identity can be watched as well as derived. The random curve swings from almost 0 to over 3.4. The Legendre curve stays between roughly 0.1 and 2, with no tall peaks.

Two different demands are now visible, and the difference matters for everything below. Littlewood’s flatness asks that the curve stay between two fixed multiples of its mean at every point, which the largest value controls. The merit factor asks only that it stay close on average, and a single tall narrow spike barely moves a variance. So a sequence can have a high merit factor and a poor maximum, and the reverse. What the two share is the target. Ultraflat polynomials, with $|p|^2/n$ tending to 1 uniformly, would also have merit factors tending to infinity, and whether the merit factor can be pushed to infinity at all is the open question this essay ends with.

A walk through every pattern #

For short lengths the best merit factor can be found by trying every sign pattern. There are $2^n$ of them, and negating every sign changes nothing, so $2^{n-1}$ need checking. Each check would cost about $n^2$ multiplications if the overlaps were recomputed from scratch.

They need not be. The patterns can be listed in the reflected binary order of a Gray code, where consecutive patterns differ in a single sign. Flipping $a_i$ changes $C_k$ only through the two products in which $a_i$ meets $a_{i+k}$ and $a_{i-k}$, so each overlap is updated with one subtraction and $E$ follows. The cost per pattern falls from $n^2$ to $n$, and every length to 26 — 33,554,432 patterns at the last — takes a few seconds.

The tall bars are the Barker lengths. At 5, 7, 11 and 13 the best sequence has every overlap equal to 0 or $\pm 1$, the smallest that parity allows, and $E$ is just $(n-1)/2$. At 13 that gives $169/12 \approx 14.08$, the highest merit factor of any sign sequence known at any length. The search reaches the Barker values by itself; it finds two optimal patterns at 13, a sequence and its reversal, and nothing better.

Past 13 the best values fall back sharply. At 14 the best is 5.16. They then wander, reaching 8.48 at 21, 8.00 at 24 and 8.68 at 25. There is no smooth trend in these 24 numbers, and that is itself information. The best sequence of each length is an isolated object, found by a search over a space that doubles with every step, and the best of one length says almost nothing about the best of the next. The longest exact results known come from branch-and-bound searches that prune patterns whose partial overlaps already exceed the record; they have been carried, with enormous effort, to lengths in the sixties, and the optimal merit factors found there remain far above 6.342. Above that only heuristic searches exist, and they too find values well above 6.342 at lengths of a few hundred, with no proof that anything better is impossible and no description of the sequences that achieve them.

In statistical physics this search has a second name. Read the signs as spins and $E$ as the energy of their interactions, and the best sequence is the ground state of what Jean Bernasconi called in 1987 a spin glass without disorder: every coupling is fixed, there is no randomness in the problem at all, and yet the energy landscape has so many shallow valleys that local searches are trapped in them. It has become a standard benchmark for optimisation methods for exactly that reason.

Squares modulo a prime #

The good sequences that come in infinite families do not come from search. They come from number theory. For a prime $p$, write $+1$ at position $j$ if $j$ is a nonzero square modulo $p$ and $-1$ if it is not, with a $+1$ at position 0 by convention. This is the Legendre sequence, the list of Legendre symbols read in order.

Read cyclically, round a circle of $p$ positions, its overlaps are as small as they can be. When $p$ leaves remainder 3 on division by 4, every cyclic overlap is exactly $-1$; when it leaves 1, every one is $1$ or $-3$. The proof is a Gauss-sum computation: the cyclic overlap at shift $k$ counts how often $j$ and $j + k$ are both squares, and that count is fixed by the number of points on a conic over the field with $p$ elements. These are the facts behind Paley’s graphs and behind the largest determinants of sign matrices.

A radar pulse is not a circle, however. It is transmitted once, and its echoes are compared with the pulse cut open into a line. Cut the Legendre sequence at position 0 and its linear overlaps are no longer all small. The merit factor is about 1.5, barely better than chance. The two ends spoil what the circle had arranged.

So cut it somewhere else. Moving the first fraction $r$ of the sequence to the end gives the same cyclic pattern, cut at a different point. Tom Høholdt and Helge Jensen proved in 1988 that the merit factor then tends, as the prime grows, to

$$F(r) = \frac{1}{2/3 - 4|r| + 8r^2}, \qquad |r| \le \tfrac12,$$

which is 1.5 at $r = 0$ and reaches its maximum of exactly 6 at $r = 1/4$. The 81 dots for $p = 1009$ sit on the curve almost everywhere and fall short of it by about 0.12 at the peaks, which is the finite length showing.

The curve has a reason, though not a short one. Each linear overlap of a rotated sequence is a cyclic overlap, which is tiny, minus the products that the cut has separated, and those are sums of products of Legendre symbols over intervals. Squaring and adding them gives a quadratic expression in $r$ whose coefficients are averages of such character sums, and the averages can be computed exactly because the symbols are multiplicative and their sums over a whole period vanish; the error terms are controlled by the same square-root bounds that count points on curves over a finite field. What the computation produces is a quadratic denominator with its minimum at a quarter. Nothing in the definition of the sequence singles out a quarter; it falls out of the arithmetic.

Four families, four ceilings #

How do the families behave as the length grows? The next figure follows four of them to several thousand signs.

Random signs settle on 1 within a few hundred terms, as the expected value of $E$ predicted. The Rudin–Shapiro sequences, built by the doubling rule of the flattest polynomials, settle on exactly 3 — 3.0029 at 1,024 and 2.9985 at 2,048 — because their doubling rule gives an exact recurrence for the fourth moment, which Littlewood solved in 1966 and which settles at $\tfrac43 n^2$. The rotated Legendre sequences climb from 2.42 at 11 to 5.98 at 3203, approaching 6 from below. The fourth family, the subject of the last figure, climbs higher still.

The ordering of the four limits says something about what each construction controls. Random signs control nothing and get 1. Rudin–Shapiro sequences control the maximum, through an algebraic identity, and get 3 as a side effect. Legendre sequences control every cyclic overlap through the arithmetic of a finite field, and the merit factor, which is an average of linear overlaps, inherits most but not all of that control. The arithmetic does better than the identity, and both do much worse than the short optimal sequences in the search, whose merit factors sit near 8 and 9 at lengths in the twenties.

Running on past the end #

In 1999 A. Kirilusha and G. Narayanaswamy noticed numerically that rotating was not the only free choice. A Legendre sequence can also be run on periodically past its own length, so that the sequence of length $tp$ repeats its first few per cent at the end, and this improves the merit factor further. Peter Borwein, Kwok-Kwong Stephen Choi and Jonathan Jedwab conjectured in 2004, from long computations, that the best limit over both knobs was about 6.342, and Jedwab, Daniel Katz and Kai-Uwe Schmidt proved it in 2013. The exact value is the largest root of

$$29x^3 - 249x^2 + 417x - 27 = 0,$$

which is $6.3420617\ldots$, reached with $r$ near 0.22 and $t$ near 1.058.

At $p = 503$ the map is a broad ridge, not a sharp peak. The plain quarter turn at $t = 1$ gives 5.87, and the best cell gives 6.315, already within 0.03 of the limit, though the ridge’s crest moves slightly as $p$ grows and the best cell here sits a little away from where the limit puts it. Running on past the end helps because the extra terms are copies of the beginning, which agree with the beginning’s echoes in a controlled way: for a short extension they add more to the zero shift than to the ghosts. Too long an extension starts to repeat a whole period, and a sequence that repeats has echoes at the period, which is why $t$ must stay close to 1.

Nothing since 2013 has beaten 6.342 with a proof. Long sequences with merit factors above 6.34 have been found by search starting from extended Legendre sequences, but none is a member of an infinite family whose limit is known. The gap between the best proved family and the search values in the eights and nines is one of the clearest in the subject. It means that the structured sequences, which number theory can analyse, are measurably worse than the unstructured ones, which only computers can find.

The same question in three trades #

The merit factor turns up under three names and was found three times. Golay had come to such sequences through infrared spectrometry and communications, and the merit factor of 1972 was his figure of quality for a binary sequence whose echoes must not be mistaken for signals. Littlewood’s question about the size of polynomials with $\pm 1$ coefficients, asked in the 1960s, contains the merit factor as its fourth moment: the average of $|p|^4$ is $n^2(1 + 1/F)$. And Bernasconi’s spin model makes the same $E$ an energy. The radar engineer wants a sharp echo, the analyst wants a flat polynomial, and the physicist wants a ground state, and the three are one optimisation over one finite set.

The surprise is in which tool works. A problem posed by an engineer about pulses, and stated by an analyst about polynomials, has its best proved answers from the arithmetic of squares modulo a prime — the same quadratic residues that decide which numbers are sums of two squares and that Gauss’s sums square to $\pm p$. Nothing in the definition of $E$ mentions primes. The reason they help is that a finite field has more symmetry than any list of coin tosses: multiplication by a square permutes the Legendre sequence onto itself, up to sign, and every overlap inherits the symmetry.

Two dozen lengths say nothing about a thousand #

Every figure here is finite. The search ends at 26, and its best values say nothing about the best at 100 or 1,000; the curve of best merit factors may rise, fall or settle, and none of those is visible in two dozen bars. The rotation law and the extended limit are theorems about the limit as $p$ grows, and the dots and the map only illustrate them. At $p = 503$ the best cell is still 0.03 short, and at 3203 the quarter turn is still 0.02 short of 6. A reader could not tell from these figures alone whether 6 and 6.342 are the true limits or merely where the numbers happen to have stopped growing.

Nor do the figures say anything about the maximum of $|p|$. A high merit factor bounds the variance of the curve on the circle, not its peaks, and the Legendre sequences that do well here have maxima growing faster than a constant times $\sqrt n$. The two forms of flatness have to be measured separately, and the essay on Littlewood’s problem measured the other one.

Searched to 26, the rotation law quoted #

Computed here: the overlaps, $E$ and $F$ of every sequence drawn, by direct summation; the identity between the mean square of $|p|^2/n$ and $1 + 1/F$, checked on 601 points of the half-circle to within 0.003; the exhaustive optimum at every length from 3 to 26, by a Gray-code walk updating each overlap in constant time, with the Barker lengths reaching $E = (n-1)/2$ checked separately; the cyclic overlaps of the Legendre sequences of 1009 and 1019, which take the values 1 and $-3$, and $-1$, as stated; the rotation curve at 81 points for $p = 1009$; the four families to 2,048 for random and Rudin–Shapiro signs and to the prime 3203 for Legendre sequences, the extended family maximised over a three-by-three grid of $r$ and $t$ at each prime; and the map at $p = 503$. The value 6.3420617 was computed as the largest root of the cubic by bisection.

Quoted: Golay’s definition and his conjecture; Høholdt and Jensen’s rotation law; the extended limit and its history through Kirilusha and Narayanaswamy, Borwein, Choi and Jedwab, and Jedwab, Katz and Schmidt; the reach of the exact branch-and-bound searches and the heuristic values at lengths of a few hundred; Bernasconi’s spin model. None of these was rederived here.

Still open: whether the merit factor is bounded #

Is there a constant that no sign sequence’s merit factor exceeds, however long it is? Equivalently, is the average of $|p|^4$ on the circle always at least $(1 + c)\,n^2$ for some fixed $c > 0$? This is the fourth-moment form of Erdős’s conjecture that sign polynomials cannot be ultraflat, and it is open. Golay argued, from a hypothesis about the overlaps behaving like independent quantities, that the best attainable limit is about 12.32. Nobody has proved any finite upper bound, and nobody has proved that any family exceeds 6.342.

The second open question is the shape of the gap. The search values at lengths in the sixties and beyond suggest that the true best merit factors at long lengths are well above 6.342, but they may be a property of short sequences, as the Barker values at 13 turned out to be. Whether there is an infinite family with merit factor above 6.342, and whether it could be described by arithmetic as the Legendre sequences are, is the question on which the next improvement depends.

Six, then a little more #

A sign sequence’s merit factor is the reciprocal of the variance of its polynomial’s squared size on the circle, so it measures flatness on average. Random signs give 1 and Rudin–Shapiro sequences give 3. The squares modulo a prime, cut open a quarter of the way round, give 6, and run on 6% past their end they give the best value proved for any family, 6.342. Searching every pattern finds far better short sequences, 14.08 at the Barker length 13 and between 7.5 and 8.7 at lengths 24 to 26, but no theorem reaches them.