OctoInformBeta

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

Dyadic rounding and the passage to the circle: Dyadic steps keep each row error of a bounded matrix small; a polynomial bound at enough roots of unity holds doubled on the circle

Rounding a vector of small mass to zeros and ones.

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

Take a real matrix A=(Aik)A = (A_{ik}) with RR rows, indexed by ii, and n≤Rn \le R columns, indexed by kk, every entry in [−1,1][-1,1], and a vector p∈[0,1]np \in [0,1]^n whose entries have a small sum. The problem is a rounding problem of discrepancy theory: replace pp by a vector with entries 00 and 11, without raising that sum, so that every row sum ∑kAikpk\sum_k A_{ik} p_k moves by an amount controlled by the size of the sum and by RR.

Write e(x)=exp⁡(2πix)e(x) = \exp(2\pi i x) for real xx. Let MM be a positive integer. When the rows of AA are the real and imaginary parts of the characters k↦e(kj/M)k \mapsto e(kj/M), for j∈ℤ/Mℤj \in \mathbb{Z}/M\mathbb{Z}, the row sums against a vector of coefficients are the real and imaginary parts of a polynomial at the MM-th roots of unity e(j/M)e(j/M). The size of such a polynomial, a function of the form (2) defined below, on the whole circle is then controlled by its size on this grid.

Masses, Signings and Dyadic Vectors

The mass of a vector p∈[0,1]np \in [0,1]^n is the sum ∑kpk\sum_k p_k of its entries. For a second vector p′∈[0,1]np' \in [0,1]^n, the row errors of p′p' against pp are the RR numbers ∑kAik(pk′−pk),i a row of A.\sum_k A_{ik}\,(p'_k - p_k), \qquad i \text{ a row of } A.(1)

A signing ξ\xi of the columns of AA is a vector ξ∈{−1,1}n\xi \in \{-1,1\}^n; its row sums are the numbers ∑kAikξk\sum_k A_{ik}\,\xi_k.

A dyadic vector pp of level jj, for an integer j≥0j \ge 0, is a vector in [0,1]n[0,1]^n whose entries are pk=ak/2jp_k = a_k/2^j with integers 0≤ak≤2j0 \le a_k \le 2^j. The dyadic vectors of level 00 are the vectors in {0,1}n\{0,1\}^n.

A polynomial PP of degree below NN with complex coefficients is a function of a complex variable of the form P(z)=∑k=0N−1ckzk,c0,…,cN−1∈ℂ.P(z) = \sum_{k=0}^{N-1} c_k z^k, \qquad c_0, \dots, c_{N-1} \in \mathbb{C}.(2)

The Claim

Theorem 1. Let A=(Aik)A = (A_{ik}) be a real matrix with RR rows and n≤Rn \le R columns, with |Aik|≤1|A_{ik}| \le 1 for all ii and kk.

  1. There is a signing ξ∈{−1,1}n\xi \in \{-1,1\}^n with ∑kξk≤0\sum_k \xi_k \le 0 whose row sums satisfy, for every row ii, |∑kAikξk|≤8192nlog⁡(2R/n).\Bigl|\sum_k A_{ik}\,\xi_k\Bigr| \le 8192\sqrt{n\log(2R/n)}.(3)✦

  2. Let μ\mu be a real number with 0<2μ≤R0 < 2\mu \le R, let j≥0j \ge 0 be an integer, and let pp be a dyadic vector of level j+1j+1 with mass at most μ\mu. Then there is a dyadic vector p′p' of level jj, with mass at most that of pp, whose row errors (1) satisfy, for every row ii, |∑kAik(pk′−pk)|≤8192(34)j+1μlog⁡(2R/μ).\Bigl|\sum_k A_{ik}\,(p'_k - p_k)\Bigr| \le 8192\Bigl(\frac{3}{4}\Bigr)^{j+1}\sqrt{\mu\log(2R/\mu)}.(4)✦

  3. Let μ\mu and jj be as in (b), and let pp be a dyadic vector of level jj with mass at most μ\mu. Then there is a vector p′∈{0,1}np' \in \{0,1\}^n, with mass at most that of pp, whose row errors satisfy, for every row ii, |∑kAik(pk′−pk)|≤24576(1−(34)j)μlog⁡(2R/μ).\Bigl|\sum_k A_{ik}\,(p'_k - p_k)\Bigr| \le 24576\Bigl(1 - \Bigl(\frac{3}{4}\Bigr)^{j}\Bigr)\sqrt{\mu\log(2R/\mu)}.(5)✦

  4. Let μ\mu be as in (b), and let p∈[0,1]np \in [0,1]^n have mass at most μ\mu. Then there is a vector p′∈{0,1}np' \in \{0,1\}^n, with mass at most that of pp, whose row errors satisfy, for every row ii, |∑kAik(pk′−pk)|≤1+24576μlog⁡(2R/μ).\Bigl|\sum_k A_{ik}\,(p'_k - p_k)\Bigr| \le 1 + 24576\sqrt{\mu\log(2R/\mu)}.(6)✦

  5. Let N≥1N \ge 1 and M≥2NM \ge 2N be integers, let PP be a polynomial (2) of degree below NN with complex coefficients, and let G≥0G \ge 0 be a number with |P(e(j/M))|≤G|P(e(j/M))| \le G for every j∈ℤ/Mℤj \in \mathbb{Z}/M\mathbb{Z}. Then, for every zz on the unit circle, |P(z)|≤2G.|P(z)| \le 2G.(7)✦

In the paper, the result reads: signs reversed so that ∑kξk≤0\sum_k \xi_k \le 0 keep the mass from increasing, the dyadic steps give ∥A(p′−p)∥∞≤1+C0(2−1)−1μlog⁡(80N/μ)\|A(p' - p)\|_\infty \le 1 + C_0(\sqrt{2} - 1)^{-1}\sqrt{\mu\log(80N/\mu)} for a constant C0C_0, and a bound on a grid of 20N20N points passes to the whole circle.

What Is Checked

The claim is stated over real matrices with RR rows, n≤Rn \le R columns and entries in [−1,1][-1,1], over signings of their columns, over vectors in [0,1]n[0,1]^n and dyadic vectors of each level with mass at most a number μ\mu satisfying 0<2μ≤R0 < 2\mu \le R, and over complex polynomials of degree below NN bounded at the MM-th roots of unity for M≥2NM \ge 2N.