Episode 192, October 2026

Beyond the square root?

A preprint claims that a yes-or-no rule’s total correlation with its inputs is not bounded by any constant times the square root of its degree

Covers result 192 in OpenAI’s catalog: its one paper. See its connections to other results and the work it cites.

Play Episode 192: Beyond the square root? Bars of the largest sum of linear coefficients by degree for 7 coins (ours), under the square-root curve, with an arrow breaking above it.

5:59. English captions available. The video loads from YouTube when you press play.

Chapters

The claim, in plain words

Feed n fair ±1 coins to a yes-or-no rule f. Its linear Fourier coefficients f̂({i}) are its correlations with single coins, and their sum is its correlation with the total of the coins. That sum is at most √n, and majority, the sign of the total, gets about 0.8√n. The rule’s degree, the degree of the polynomial that represents it exactly, can be far smaller than n. A dictator has degree 1 and sum 1; majority of 3 has degree 3 and sum 1.5. In our search of every rule on 4 coins, and exact optimization up to 7 coins, the sum never exceeds √(degree).

The paper credits the question to Gopalan and Servedio, around 2009, as recorded in O’Donnell’s problem list: can √n be replaced by √(degree)? A sharper version using majority’s exact value was settled for degrees 2 and 3 and refuted at degree 4 by Kudin and Pašalić (2021); our search finds one such function on 7 coins, with degree 4 and sum 1.75, above majority’s 1.5 but below √4 = 2. Square-root bounds do hold for decision trees, with average depth in place of degree (O’Donnell and Servedio), and the sum is known to be at most the degree.

Result 192 is one OpenAI preprint, Unbounded Violations of the Square-Root Degree Bound (23 pages, dated September 26, 2026). Its Theorem 1.1: for every real C > 0 there are n and a nonconstant f : {−1,1}ⁿ → {−1,1} with Σ_i f̂({i}) > C·√deg(f); consequently the ratio Σ_i|f̂({i})| / √deg(f) is unbounded. So the square-root bound fails with every constant, and the truth lies somewhere between √(degree) and the degree.

What it doesn’t claim

Any explicit rule or size: “we do not obtain useful bounds on their growth”. By our numerics on the proof’s own parameters, its key step meets the paper’s own condition (J < 1/4) only when its parameter m is about 10²³, and then gains about 10^−10²⁵ per round; that describes the proof, not the smallest counterexample, which nobody knows. Nothing about where between √(degree) and the degree the truth lies, nothing about monotone rules, and nothing for small rules.

Where it stands

Posted as a preprint: OpenAI, 23 pages, dated September 26, 2026
Peer reviewed: Not yet
Checked in Lean: The theorem, exactly as stated, formalized by OpenAI by a variant route; not run by us

Last checked October 19, 2026. The preprint has not been revised since it was added to the repository in its initial commit on October 6, 2026. OpenAI published a Lean formalization: the comparator statement gives both the signed version and the unbounded ratio of Theorem 1.1. The Lean proof follows one of the paper’s variant routes (the switching rule), with smoothed tests and explicit constants (about 10³⁰⁸ leaves). By our count it takes 21 files and about 3,600 lines, excluding Mathlib (source). We found no unproved steps by search; we have not rebuilt the proof. The collection’s formalization.yaml does not list this result. The paper is not among those OSVerify reviewed, and we have seen no expert review.

How the proof goes

Value per unit of degree. Build an observation, a way of chopping the cube into cells, with a value (the variance of the total the cell still predicts) and a price (the highest degree of a cell’s indicator). The sign of the best guess is a rule of degree at most the price, and with many copies the ratio approaches about 0.8√(value/price) (Lemma 2.2). Revealing coins gives value = price.
A rule that keeps a sliver more. With m + 1 roughly Gaussian scores, one selects a leaf and every leaf has a tiny target window. Usually the rule reports all scores but one; on the rare event that only the selected leaf misses, it reports a tag, and there the total is predicted with mean squared error below 1. So the value exceeds m (Lemmas 3.1, 3.2).
The tag is cheap. Its indicator looks at all m + 1 scores, yet equals a sum of terms each using only m of them, minus one more such term (identity (3)): the degree saving comes from cancellation.
Amplify. Scores built from many coins are nearly Gaussian; feeding m + 1 blocks into the rule multiplies value/price by at least 1 + η/m. Repeat finitely many times, then take the sign. The paper gives several further routes to the same theorem (§4.1, §4.2, §5, Appendices A and B).

The numbers in the video

Small cases (ours): every Boolean function on up to 4 inputs, and exact integer programs up to 7; the largest sum by degree on 7 coins is 1, 1, 1.5, 1.75, 1.875, 1.875, 2.1875 for degrees 1 to 7, never above √(degree); the best ratio at degree 2 or more is 0.875.
The majority benchmark B_d = E|X₁+…+X_d| (1, 1, 1.5, 1.5, 1.875, …).
Identity (3) on our 8-bit toy: it holds on all 256 inputs; the tag’s indicator depends on all 8 bits but has degree 6; this small instance has no gain.
The curve of J against m, the crossing of the proof’s condition J < 1/4 near m ≈ 10^23.4, and J = 1 (where the gain turns positive) near m ≈ 10²¹ are our numerical evaluation of the quantities in Lemma 3.2. The Lean count is our count of the import closure.

Read the source

Unbounded Violations of the Square-Root Degree Bound (PDF), 23 pages.
The Lean scope note.
The collection’s catalog, where this is result 192.

The paper

OpenAI groups related papers into one result; this one has a single paper.

Unbounded Violations of the Square-Root Degree Bound

Transcript

Read the full script

0:00The question

Flip n fair coins, each plus or minus one, and feed them to a yes-or-no rule. The rule’s correlation with a single coin is one of its linear Fourier coefficients; add them all up, and you get its correlation with the total of the coins. That sum is at most √n, and majority, which outputs the sign of the total, comes close, at about 0.8√n. The rule’s degree, the degree of the polynomial that represents it exactly, can be much smaller than n. A dictator, which copies one coin, has degree 1 and sum 1. Majority on 3 coins has degree 3 and sum 1.5. In our exhaustive search of every rule on 4 coins, and exact optimization up to 7 coins, the sum never exceeds √deg. The paper credits the question to Gopalan and Servedio, around 2009, as recorded in O’Donnell’s problem list: can √n be replaced by √deg? The same list floated a sharper version, using majority’s exact value. Kudin and Pašalić proved degrees 2 and 3 of that version, and refuted it at degree 4, in 2021. Our search finds one such function: 7 coins, degree 4, sum 1.75, above majority’s 1.5, but still below √4 = 2. Square-root bounds do hold for decision trees, with average depth in place of degree, by O’Donnell and Servedio. And a linear bound is known to hold: the sum is at most the degree.

1:34The claim

Result 192 is one OpenAI preprint, 23 pages, dated September 26, 2026. It claims: for every constant C, there is a nonconstant yes-or-no rule whose sum of linear coefficients exceeds C√deg. So the square-root bound fails, not just with constant 1 but with every constant, and the ratio of the sum of absolute values to √deg is unbounded. The linear bound survives, so the truth lies somewhere between √deg and the degree itself. Not claimed: any explicit rule, or any size. The paper says it obtains no useful bounds on how large its examples are. By our numerics on the proof’s own parameters, its key step meets the paper’s own condition only when its parameter m is about 10^23, and then gains about 10^(−10^25) per round. That describes the proof, not the smallest counterexample, which nobody knows. Nothing about where between √deg and the degree the truth lies, nothing about monotone rules, and nothing for small rules: every one we could check obeys the bound.

2:48How the proof goes

The proof changes the question. Instead of a rule, build an observation: a way of chopping the cube into cells. It has a value, how much of the variance of the total the cell still predicts, and a price, the highest degree of the cells’ indicator functions. Reading off the sign of the best guess gives a yes-or-no rule of degree at most the price, and, after averaging many copies, the ratio we care about approaches 0.8√(value/price). So if value over price can be made as large as we like, the theorem follows. Revealing coins outright gives value equal to price: ratio 1. The key trade uses m + 1 roughly Gaussian scores. Revealing m of them keeps exactly m units of variance, at price m. The paper’s rule does slightly better. One score selects one of the other m, the leaf, and every leaf has a tiny target window. Usually the rule reports all scores but one. But on a rare event, where every leaf hits its window except the selected one, it reports just a tag. On that event the windows pin the total down with mean squared error less than 1, so the rule keeps slightly more than m. And the tag is cheap: its indicator looks at all m + 1 scores, yet equals a sum of terms that each involve only m of them, minus one more such term. The degree saving comes from cancellation. On our 8-bit toy, that identity holds on all 256 inputs, and the tag depends on all 8 bits but has degree only 6. At that size, though, there is no gain. Scores built from many coins are nearly Gaussian, by the central limit theorem, and the small gain survives the approximation. Feed m + 1 blocks of the current observation into the rule, and value over price grows by a factor of at least 1 + gain/m. Start from a single coin, repeat finitely many times until the ratio is large enough, and take the sign. The catch is size: the gain per round is about the chance that m narrow windows are all hit, which is astronomically small, so the number of rounds, and of coins, is far beyond anything physical. The paper also gives several further routes to the same theorem.

5:04Where it stands

The preprint is unrefereed and has not been revised. OpenAI’s Lean files state the theorem exactly, both the signed version and the unbounded ratio, and prove it in 21 files and about 3,600 lines, with no gaps we could find by search; we did not run the check. The Lean proof follows one of the paper’s variant routes, the switching rule, with smoothed tests and explicit constants, about 10^308 leaves. The collection’s formalization catalog does not list it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, a yes-or-no rule’s total correlation with its inputs is not bounded by any constant times √deg. The truth lies somewhere between that and the degree itself.

Spot a mistake?

This episode simplifies on purpose, but it shouldn’t be wrong. If something is, open an issue on GitHub or leave a comment on YouTube. Corrections are noted here with a date.