OctoInformBeta

OpenAI preprint, September 2026 · §6. Rounding with a small defect mass

Lemma 6.1: If s≤Rs \le R, an R×sR \times s matrix with entries in [−1,1][-1,1] has a column signing with row sums of absolute value at most 8192slog⁡(2R/s)8192\sqrt{s\log(2R/s)}

Column signings with small row sums for bounded matrices.

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

Let B=(Bik)B = (B_{ik}) be a real matrix with RR rows and ss columns and every entry in [−1,1][-1,1], the rows indexed by ii and the columns by kk. Putting a sign on each column, one asks how small all RR row sums can be made at once. This is the question of Spencer’s theorem in discrepancy theory, whose bound for s≤Rs \le R is of order slog⁡(2R/s)\sqrt{s\log(2R/s)}.

On the circle the question concerns Littlewood polynomials. Let 𝕋=ℝ/ℤ\mathbb{T} = \mathbb{R}/\mathbb{Z} be the circle and write e(x)=exp⁡(2πix)e(x) = \exp(2\pi i x). For points t1,…,tmt_1, \dots, t_m of 𝕋\mathbb{T}, the 2m2m rows (cos⁡2πktj)0≤k<s(\cos 2\pi k t_j)_{0 \le k < s} and (sin⁡2πktj)0≤k<s(\sin 2\pi k t_j)_{0 \le k < s} have entries in [−1,1][-1,1], and for signs ξ0,…,ξs−1\xi_0, \dots, \xi_{s-1} in {−1,1}\{-1,1\} their row sums are the real and imaginary parts of the values Pξ(e(tj))P_\xi(e(t_j)) of the Littlewood polynomial Pξ(z)=∑k<sξkzkP_\xi(z) = \sum_{k<s} \xi_k z^k.

Signings and Partial Colorings

A signing of the columns of BB is a vector ξ=(ξk)\xi = (\xi_k) in {−1,1}s\{-1,1\}^s. A partial coloring of the columns of BB is a vector z=(zk)z = (z_k) in {−1,0,1}s\{-1,0,1\}^s; it fixes the columns kk with zk≠0z_k \neq 0.

For a vector xx in ℝs\mathbb{R}^s, the row sums of BB at xx are the coordinates of BxBx, (Bx)i=∑kBikxk,(Bx)_i = \sum_k B_{ik} x_k,(1) and ∥Bx∥∞=max⁡i|(Bx)i|\|Bx\|_\infty = \max_i |(Bx)_i| is the largest of them in absolute value.

The Claim

Theorem 1. Let BB be a real R×sR \times s matrix with every entry in [−1,1][-1,1], and let s≤Rs \le R.

(a) There is a signing ξ\xi of the columns of BB with ∥Bξ∥∞≤8192slog⁡(2R/s).\|B\xi\|_\infty \le 8192\sqrt{s\log(2R/s)}.(2)✦

(b) There is a signing ξ\xi of the columns of BB with ∥Bξ∥∞≤4096slog⁡(16R/s).\|B\xi\|_\infty \le 4096\sqrt{s\log(16R/s)}.(3)✦

(c) If s≥1s \ge 1, there is a partial coloring zz of the columns of BB that fixes at least s/16s/16 columns and has ∥Bz∥∞≤64slog⁡(16R/s).\|Bz\|_\infty \le 64\sqrt{s\log(16R/s)}.(4)✦

In the paper, the result reads: there is an absolute constant C0C_0 such that for integers 1≤s≤R1 \le s \le R and every B∈[−1,1]R×sB \in [-1,1]^{R \times s} some ξ∈{−1,1}s\xi \in \{-1,1\}^s has ∥Bξ∥∞≤C0slog⁡(2R/s)\|B\xi\|_\infty \le C_0\sqrt{s\log(2R/s)}.

The bound (2) gives this with C0=8192C_0 = 8192.

What Is Checked

The bounds (2), (3) and (4) are stated over real matrices with entries in [−1,1][-1,1] whose rows and columns are indexed by finite sets of sizes RR and ss with s≤Rs \le R, and over the signings and partial colorings of their columns, measured by the row sums (1).