OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Theorem 1.1: Nonconstant Boolean functions violate every fixed multiple of the square root of their Fourier degree

Singleton sums have unbounded degree ratios.

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

The square-root degree question compares the linear Fourier coefficients of a Boolean function with the square root of its Fourier degree. The signed sum of those coefficients and the sum of their absolute values give two different comparisons.

For a finite index set II, the sign cube QI={−1,1}IQ_I=\{-1,1\}^I is the set of sign vectors indexed by II; write Qn={−1,1}nQ_n=\{-1,1\}^n when I={1,…,n}I=\{1,\ldots,n\}.✦ A Boolean function f:QI→ℝf:Q_I\to\mathbb R is a function taking only the values −1-1 and 11.✦ A nonconstant function f:QI→ℝf:Q_I\to\mathbb R is one for which there are x,y∈QIx,y\in Q_I with f(x)≠f(y)f(x)\ne f(y).✦

For a real function gg on a finite set AA, the uniform mean 𝔼Ag\mathbb E_A g is the real number given by (1), with mean zero when AA is empty: 𝔼Ag={1|A|∑a∈Ag(a),A≠⌀,0,A=⌀.\mathbb E_A g= \begin{cases} \displaystyle\frac{1}{|A|}\sum_{a\in A}g(a),& A\ne\varnothing,\\ 0,& A=\varnothing. \end{cases}(1) For S⊆IS\subseteq I, the Fourier character χS:QI→ℝ\chi_S:Q_I\to\mathbb R is the coordinate product in (2): χS(x)=∏i∈Sxi.\chi_S(x)=\prod_{i\in S}x_i.(2)✦ The real Fourier-Walsh coefficient fˆ(S)\widehat f(S) of f:QI→ℝf:Q_I\to\mathbb R is its uniform mean against χS\chi_S, as in (3): fˆ(S)=𝔼x∈QI[f(x)χS(x)].\widehat f(S)=\mathbb E_{x\in Q_I}\bigl[f(x)\chi_S(x)\bigr].(3)✦

The Fourier degree deg⁡f\deg f of f:QI→ℝf:Q_I\to\mathbb R is the nonnegative integer defined in (4), measuring its ordinary real multilinear degree, with constants and the zero function having degree zero. This degree is distinct from polynomial threshold degree and degree over a finite field. deg⁡f=max⁡({0}∪{|S|:S⊆I,fˆ(S)≠0}).\deg f=\max\bigl(\{0\}\cup \{|S|:S\subseteq I,\ \widehat f(S)\ne0\}\bigr).(4)✦ The signed singleton sum L(f)L(f) and absolute singleton sum A(f)A(f) of f:QI→ℝf:Q_I\to\mathbb R are the two sums in (5): L(f)=∑i∈Ifˆ({i}),A(f)=∑i∈I|fˆ({i})|.L(f)=\sum_{i\in I}\widehat f(\{i\}), \qquad A(f)=\sum_{i\in I}|\widehat f(\{i\})|.(5)

The set ℛ⊆ℝ\mathcal R\subseteq\mathbb R of absolute degree ratios consists of the ratios in (6), taken over Boolean functions of positive degree on positive-dimensional cubes: ℛ={A(f)deg⁡f:n≥1,f:Qn→ℝBoolean,degf>0}.\mathcal R= \left\{\frac{A(f)}{\sqrt{\deg f}}: n\ge1,\ f:Q_n\to\mathbb R\ \text{Boolean},\ \deg f>0\right\}.(6) The signed violation property 𝒱\mathcal V is the assertion that for every real C>0C>0 there are an integer n≥1n\ge1 and a nonconstant Boolean function f:Qn→ℝf:Q_n\to\mathbb R satisfying (7): Cdeg⁡f<L(f).C\sqrt{\deg f}<L(f).(7)✦

The Claim

Theorem 1. The signed violation property holds, and the absolute degree ratios are unbounded above, as in (8) and (9): 𝒱.\mathcal V.(8)✦ 𝒱andℛis unbounded above.\mathcal V \quad\text{and}\quad \mathcal R\ \text{is unbounded above}.(9)✦ If the signed violation property 𝒱\mathcal V holds, then (10) holds: For every M∈ℝ there is r∈ℛ with M<r.\text{For every }M\in\mathbb R\text{ there is }r\in\mathcal R \text{ with }M<r.(10)✦ For every finite index set II and every nonconstant real function f:QI→ℝf:Q_I\to\mathbb R, the degree satisfies (11): 0<deg⁡f.0<\deg f.(11)✦

In the paper, the result reads: for every real C>0C>0 there are an integer n≥1n\ge1 and a nonconstant Boolean function f:Qn→{−1,1}f:Q_n\to\{-1,1\} with ∑i=1nfˆ({i})>Cdeg⁡f\sum_{i=1}^n\widehat f(\{i\})>C\sqrt{\deg f}, and consequently the supremum of ∑i=1n|fˆ({i})|/deg⁡f\sum_{i=1}^n|\widehat f(\{i\})|/\sqrt{\deg f} over n≥1n\ge1 and positive-degree Boolean functions is infinite.

What Is Checked

The signed and joint assertions concern Boolean functions on positive-dimensional finite sign cubes, with nonconstancy in 𝒱\mathcal V and positive degree in ℛ\mathcal R. The conditional assertion (10) uses precisely the signed violation property; the positivity assertion (11) applies to real functions on any finite sign cube, without a Boolean hypothesis.