Real Littlewood Polynomials Attain the √N Peak Bound at Every Large Length

A real Littlewood polynomial of length N has coefficients that are all +1 or −1, one for each power from 0 to N−1. As z travels around the unit circle, the terms rotate at different rates and add as vectors. The question is how small the largest resulting modulus can be.

There is an unavoidable floor. Average the squared modulus around the circle and expand it. Terms involving different powers average to zero; each diagonal term contributes 1, since each coefficient squared is 1. The average squared modulus is therefore N. Since a maximum cannot be below its average, every such polynomial satisfies max |P(z)| ≥ √N on the unit circle. This is an average-energy argument, not a claim that the modulus is constant around the circle.

The manuscript proves that this floor is asymptotically attainable. For every positive relative tolerance η, all sufficiently large integer lengths N admit a choice of signs for which max |P(z)| ≤ (1 + η)√N. The claim covers every sufficiently large length, not merely a subsequence. It controls the highest peak, but does not establish two-sided uniform flatness: it does not rule out low valleys in the modulus, and it gives no useful convergence rate or efficient recipe for finding the signs.^†

There is a weaker, averaged flatness consequence. For each fixed finite p > 0, the normalized modulus |P_N(e^(2πit))|/√N converges to 1 in the integral p-th-power sense: the integral from t = 0 to 1 of its distance from 1, raised to p, tends to zero. This says that deviations become small on average for each fixed p. It does not say that the largest deviation at any angle tends to zero, which would be a uniform, two-sided claim.

The proof first relaxes the coefficients: instead of signs, it allows values anywhere in [−1, 1]. The aim is to create coefficients with almost the full mean-square energy while keeping their Fourier maximum small.

One local step adds a fresh cosine to an existing function p, scaled by (1 − p²)/2. Near either endpoint of the allowed interval, this scale becomes small, helping keep the updated function inside [−1, 1]. Averaging over the fresh circle variable, the cosine contributes zero and its square contributes 1/2. If M_j is the updated mean square, the increase is one-eighth of the average of (1 − p_(j−1)²)². The average of a square is at least the square of its average, so this increase is at least one-eighth of (1 − M_(j−1))².

Because M_j cannot exceed 1, it cannot converge to a value below 1: such a limit would keep the increments bounded below by a positive amount. Thus this local mechanism drives the relaxed function’s mean square toward 1. But high energy alone does not control the largest Fourier peak. The rest of the construction must arrange the spectrum so that large contributions do not pile up at the same angle.

The manuscript spreads the auxiliary functions’ Fourier coefficients using quadratic oscillations in extra variables, then samples along quadratic paths in fixed blocks. A single oscillating mode contributes mainly near points where its phase is stationary. The absolute curvature determines the width of that contribution; after normalization by √N, its peak is bounded in terms of the coefficient’s magnitude divided by the square root of the absolute curvature.

The construction budgets the widths and heights together. A packing lemma places the signed intervals associated with all blocks without overlap. Both a mode and its opposite have to be included because the coefficients are real. The point of the packing is that, at any angle, at most one leading stationary contribution survives. The remaining error tends uniformly to zero.

The source’s visual explanation presents this as a sequence of spreading, sampling, and separation: the construction keeps the spectral intervals apart so leading contributions do not overlap. This step depends on coefficient spreading, interval packing, and uniform error estimates. The argument’s structure is that spreading limits individual contributions while separation prevents several leading contributions from reinforcing one another.

The relaxed coefficients must eventually become signs. Their total defect μ is half the sum of their distances from the nearest sign. For |x| ≤ 1, 1 − |x| ≤ 1 − x², so near-full mean-square energy makes this defect small relative to N.

Independent rounding would not suffice: errors from different coefficients could reinforce one another in the Fourier sum. Instead, the manuscript uses discrepancy theory to coordinate the sign choices across a grid of angles, then applies a derivative bound to extend control from the grid to the entire circle. Its stated rounding error is bounded by an absolute constant times 1 + √(μ log(80N/μ)). When the relative defect μ/N tends to zero, this error is negligible on the √N scale. This is an existence bound, not an independent-rounding algorithm.

The order of limits matters. First fix a small tolerance and all auxiliary data, including the dimensions, frequencies, packing, and blocks. Then let N grow through the integers. The normalized maximum is bounded above by a term K_δ that tends to 1 as the tolerance δ shrinks, plus a rounding loss that also tends to zero. Only after taking the large-length limit does the proof shrink δ. No divisibility condition on N is needed. Combined with the energy lower bound, this gives min ||P||∞/√N → 1, where the minimum is over all sign choices of length N.

For a sign sequence, its aperiodic autocorrelation at shift u is the sum of products of overlapping signs, without wrapping the sequence around. Expanding |P|² shows that these autocorrelations are its nonconstant Fourier coefficients. Parseval’s identity gives a fourth-power average equal to N² + 2Σ C_u², where C_u is the autocorrelation at shift u.

The merit factor is N² divided by the extra term, 2Σ C_u². Meanwhile, the fourth-power average is at most ||P||∞² times the second-power average, which is N. For polynomials attaining the asymptotic peak bound, this is at most N² times a factor tending to 1. The extra autocorrelation energy, relative to N², must therefore tend to zero. The manuscript concludes that the maximum merit factor among binary sequences tends to infinity as the length grows through all integers.

The result is an asymptotically optimal ceiling on the peak, not a perfectly level wave. Its proof combines near-sign energy, separated spectral contributions, and coordinated rounding.