OctoInformBeta

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

Lemma 2.2: For N≥1N \ge 1 and X∈[−1,1]NX \in [-1,1]^N, a real signing ε\varepsilon with |Pε(z)−PX(z)|≤196608(1+μ(X)log⁡(80N/μ(X)))|P_\varepsilon(z) - P_X(z)| \le 196608\,(1 + \sqrt{\mu(X)\log(80N/\mu(X))}) whenever |z|=1|z| = 1

Rounding to signs with error controlled by the defect mass.

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 Littlewood polynomial has every coefficient equal to −1-1 or 11, and the flatness problem asks how small its maximum modulus on the unit circle can be for a given length NN. Real coefficients in [−1,1][-1,1] are far easier to tune than signs, so a flat Littlewood polynomial can be sought in two steps: first a real coefficient vector X∈[−1,1]NX \in [-1,1]^N whose polynomial is flat, then signs εk\varepsilon_k to replace the entries XkX_k.

The result below, Lemma 2.2, controls the second step. The signs must keep the difference of the two polynomials small at every point z=e(t)z = e(t) of the unit circle at once, where e(t)=exp⁡(2πit)e(t) = \exp(2\pi i t) and t∈[0,1]t \in [0,1]; this is a discrepancy problem for the exponentials e(kt)e(kt), uniform in tt. The lemma bounds this uniform error in terms of NN and of the defect mass of XX, which measures how far the entries of XX lie from −1-1 and 11.

Signings and the Defect Mass

A real signing of length NN is a vector ε=(ε0,…,εN−1)\varepsilon = (\varepsilon_0, \dots, \varepsilon_{N-1}) of real numbers each of which is −1-1 or 11.

The polynomial PXP_X of a real vector X=(X0,…,XN−1)X = (X_0, \dots, X_{N-1}) is the function of a complex variable zz given by PX(z)=∑k=0N−1Xkzk,P_X(z) = \sum_{k=0}^{N-1} X_k z^k ,(1)✦ and when ε\varepsilon is a real signing, PεP_\varepsilon is its Littlewood polynomial.

The defect mass μ(X)\mu(X) of a real vector XX of length NN is the real number μ(X)=12∑k=0N−1(1−|Xk|).\mu(X) = \frac{1}{2} \sum_{k=0}^{N-1} \bigl(1 - |X_k|\bigr).(2)✦

The Claim

Theorem 1. Let N≥1N \ge 1, and let X=(X0,…,XN−1)X = (X_0, \dots, X_{N-1}) be a real vector with |Xk|≤1|X_k| \le 1 for every kk. Then there is a real signing ε\varepsilon of length NN such that, for every complex number zz with |z|=1|z| = 1, |Pε(z)−PX(z)|≤196608(1+μ(X)log⁡80Nμ(X)),\bigl|P_\varepsilon(z) - P_X(z)\bigr| \le 196608 \Bigl(1 + \sqrt{\mu(X) \log \frac{80N}{\mu(X)}}\,\Bigr),(3)✦ where the product under the square root is read as 00 when μ(X)=0\mu(X) = 0.

In the paper, the result reads: there is an absolute constant CC such that for every N≥1N \ge 1 and every X∈[−1,1]NX \in [-1,1]^N some signs εk\varepsilon_k satisfy max⁡t∈[0,1]|∑k<N(εk−Xk)e(kt)|≤C(1+μ(X)log⁡(80N/μ(X)))\max_{t \in [0,1]} \bigl|\sum_{k<N} (\varepsilon_k - X_k)\, e(kt)\bigr| \le C\bigl(1 + \sqrt{\mu(X)\log(80N/\mu(X))}\bigr), the square-root term being zero when μ(X)=0\mu(X) = 0.

The theorem above gives this with C=196608C = 196608, the point z=e(t)z = e(t) of the unit circle standing for the parameter tt.

What Is Checked

The claim (3) is stated over real vectors XX of length N≥1N \ge 1 with every |Xk|≤1|X_k| \le 1, the polynomial PXP_X of (1) at points of the unit circle, real signings ε\varepsilon with their Littlewood polynomials, and the defect mass μ(X)\mu(X) of (2).