OctoInformBeta

OpenAI preprint, September 2026 · §2. Reduction to approximation and rounding

Proposition 2.1: For 0<δ<1/200<\delta<1/20, vectors XN∈[−1,1]NX_N\in[-1,1]^N with |QXN(t)|/N≤Kδ+O(1/N)|Q_{X_N}(t)|/\sqrt N\le K_\delta+O(1/N) for t∈[0,1]t\in[0,1] and normalized energy tending to L≥1−7δL\ge 1-7\delta

Almost-sign coefficient vectors with small maximum modulus.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

A signing of length NN is a vector ε=(ε0,…,εN−1)\varepsilon=(\varepsilon_0,\dots,\varepsilon_{N-1}) with every entry −1-1 or 11, and Pε(z)=∑k<NεkzkP_\varepsilon(z)=\sum_{k<N}\varepsilon_k z^k is its Littlewood polynomial. The question is how small the ratio of the maximum of |Pε||P_\varepsilon| on the circle to N\sqrt N can be kept as NN grows.

Relaxing the signs to the cube [−1,1]N[-1,1]^N turns this into an approximation problem: find coefficient vectors XX that are nearly signings, their entries mostly near ±1\pm1, whose polynomials ∑k<NXkzk\sum_{k<N}X_kz^k have maximum modulus on the circle close to N\sqrt N. Theorem 1 below, an almost-sign approximation, gives such vectors at every length, with the closeness controlled by a parameter δ\delta.

Phases, Polynomials and Energy

For a real number xx, the phase eixe^{ix} is the complex number exp⁡(ix)\exp(ix), the point of the unit circle at angle xx.✦ The phase e(x)e(x) of period 11 of a real number xx is the complex number e(x)=e2πix,e(x)=e^{2\pi i x},(1) and t∈[0,1]t\in[0,1] parametrizes the unit circle by z=e(t)z=e(t).

For a coefficient vector X=(X0,…,XN−1)X=(X_0,\dots,X_{N-1}) in [−1,1]N[-1,1]^N, the trigonometric polynomial QXQ_X of XX is the function on [0,1][0,1] given by QX(t)=∑k<NXke(kt);Q_X(t)=\sum_{k<N}X_k\,e(kt);(2) for a signing ε\varepsilon it is the Littlewood polynomial on the circle, Qε(t)=Pε(e(t))Q_\varepsilon(t)=P_\varepsilon(e(t)). The maximum modulus of QXQ_X is ∥QX∥∞=max⁡t∈[0,1]|QX(t)|\|Q_X\|_\infty=\max_{t\in[0,1]}|Q_X(t)|.

The normalized energy of a vector X∈ℝNX\in\mathbb{R}^N is the mean 1N∑k<NXk2\frac1N\sum_{k<N}X_k^2 of the squares of its entries. On the cube it equals 11 exactly at the signings, and is smaller at every other vector.

For 0<δ<1/200<\delta<1/20, the constant KδK_\delta is the number Kδ=(1+δ)31−δ,K_\delta=\sqrt{\frac{(1+\delta)^3}{1-\delta}},(3) which exceeds 11 and tends to 11 as δ→0\delta\to0.

The Claim

Theorem 1. Let 0<δ<1/200<\delta<1/20. There are vectors XN=(XN,0,…,XN,N−1)X_N=(X_{N,0},\dots,X_{N,N-1}) in [−1,1]N[-1,1]^N, one for each length N≥1N\ge1, a real number L≥1−7δL\ge1-7\delta and a constant C≥0C\ge0 such that limN→∞1N∑k<NXN,k2=L,|QXN(t)|N≤Kδ+CN(N≥1,t∈[0,1]).\lim_{N\to\infty}\frac1N\sum_{k<N}X_{N,k}^2=L, \qquad \frac{|Q_{X_N}(t)|}{\sqrt N}\le K_\delta+\frac{C}{N}\quad(N\ge1,\ t\in[0,1]).(4)✦

In the paper, the result reads: for every 0<δ<1/200<\delta<1/20 there are vectors XN∈[−1,1]NX_N\in[-1,1]^N, one for each N≥1N\ge1, with limsup⁡N→∞∥QXN∥∞/N≤Kδ\limsup_{N\to\infty}\|Q_{X_N}\|_\infty/\sqrt N\le K_\delta and liminf⁡N→∞1N∑k<NXN,k2≥1−7δ\liminf_{N\to\infty}\frac1N\sum_{k<N}X_{N,k}^2\ge1-7\delta.

The theorem sharpens the limit superior in the paper’s form to a bound at every length with error C/NC/N, and the limit inferior to an actual limit of the normalized energy.

What Is Checked

The claim is stated over real coefficient vectors of every length N≥1N\ge1 and their trigonometric polynomials (2), built from the phase eixe^{ix} at x=2πktx=2\pi kt, for a parameter 0<δ<1/200<\delta<1/20.