OctoInformBeta

OpenAI preprint, September 2026 · §5. Parity and the binomial coupling (proof of Theorem 1) · equation (14)

Low blocks vanish: For multilinear pp of degree at most dd, χp∈V≥n−d\chi p\in V_{\ge n-d}, and if pp has no zero, ΠsHΠr=0\Pi_s H\Pi_r=0 for r+s<n−dr+s<n-d

The parity times a threshold function has no low blocks.

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 pp be a real multilinear polynomial in nn variables, of degree at most dd, with no zero on the cube Ω\Omega, and let f=sgn(p)f=\mathrm{sgn}(p) be its polynomial threshold function. The proof of Theorem 1 of the paper draws two functions on Ω\Omega from pp: the weight w=|p|w=|p|, positive at every point, and h=χfh=\chi f, where χ\chi is the full parity. The weight defines orthogonal layers E0,…,EnE_0,\dots,E_n of ℂΩ\mathbb{C}^{\Omega}, the kk-th built from the functions of Fourier degree at most kk multiplied by w\sqrt{w}, with orthogonal projections Π0,…,Πn\Pi_0,\dots,\Pi_n. Multiplication by hh, written HH, then has a block ΠsHΠr\Pi_s H\Pi_r for each pair of layers. The question is which of these blocks vanish, in terms of rr, ss and the degree dd. A second question concerns pp alone: where the Fourier spectrum of the product χp\chi p lies.

Characters and Polynomials on the Cube

The cube Ω\Omega of dimension nn is the set {−1,1}n\{-1,1\}^n of points x=(x1,…,xn)x=(x_1,\dots,x_n), each coordinate xix_i a real sign 11 or −1-1.✦ For a subset SS of {1,…,n}\{1,\dots,n\}, the character χS\chi_S is the complex function on Ω\Omega with χS(x)=∏i∈Sxi\chi_S(x)=\prod_{i\in S}x_i.✦ The full parity χ\chi is the real function on Ω\Omega with χ(x)=∏i=1nxi\chi(x)=\prod_{i=1}^{n}x_i.✦

A real polynomial pp in nn variables is multilinear if every monomial with a nonzero coefficient in pp has exponent at most 11 in each variable; equivalently, pp is a real linear combination of the monomials ∏j∈Sxj\prod_{j\in S}x_j.✦ The degree of a real polynomial pp is its total degree.

The threshold sign is the function sgn\mathrm{sgn} on ℝ\mathbb{R} with sgn(t)=1\mathrm{sgn}(t)=1 for t≥0t\ge 0 and sgn(t)=−1\mathrm{sgn}(t)=-1 for t<0t<0.✦ The polynomial threshold function of pp is the function sgn(p)\mathrm{sgn}(p) on Ω\Omega that sends xx to sgn(p(x))\mathrm{sgn}(p(x)).✦

For a natural number kk, the space VkV_k of functions of Fourier degree at most kk is the subspace of the space ℂΩ\mathbb{C}^{\Omega} of complex functions on Ω\Omega spanned by the characters χS\chi_S with |S|≤k|S|\le k, and the space V≥kV_{\ge k} is the subspace spanned by the characters χS\chi_S with |S|≥k|S|\ge k: Vk=span⁡ℂ{χS:|S|≤k},V≥k=span⁡ℂ{χS:|S|≥k}.V_k=\operatorname{span}_{\mathbb{C}}\{\chi_S : |S|\le k\},\qquad V_{\ge k}=\operatorname{span}_{\mathbb{C}}\{\chi_S : |S|\ge k\}.(1)✦

The Weighted Fourier Flag

The space ℂΩ\mathbb{C}^{\Omega} carries the counting inner product ⟨f,g⟩=∑x∈Ωf(x)¯g(x),\langle f,g\rangle=\sum_{x\in\Omega}\overline{f(x)}\,g(x),(2) for which the point masses δx\delta_x, x∈Ωx\in\Omega, form an orthonormal basis, the point basis. The matrix of a linear operator BB on ℂΩ\mathbb{C}^{\Omega} is (⟨δx,Bδy⟩)x,y∈Ω(\langle\delta_x,B\delta_y\rangle)_{x,y\in\Omega}✦; operators are identified with their matrices. For a real function hh on Ω\Omega, multiplication by hh has the diagonal matrix HH with entry h(x)h(x) at (x,x)(x,x).✦

For a weight ww on Ω\Omega with w(x)>0w(x)>0 at every point, the scaling DD by the square root of ww is the invertible linear operator on ℂΩ\mathbb{C}^{\Omega} given by (Df)(x)=w(x)f(x)(Df)(x)=\sqrt{w(x)}\,f(x); its inverse is multiplication by 1/w1/\sqrt{w}.✦

The Fourier flag is the sequence of subspaces {0},V0,V1,…\{0\},V_0,V_1,\dots of ℂΩ\mathbb{C}^{\Omega}.✦ The weighted Fourier flag of a weight ww is the sequence of subspaces K−1={0}K_{-1}=\{0\} and Kk=DVkK_k=DV_k for k≥0k\ge 0.✦

The kk-th layer EkE_k of the weighted Fourier flag, for k=0,…,nk=0,\dots,n, is the subspace of the vectors of KkK_k orthogonal to Kk−1K_{k-1} for the inner product (2): Ek=Kk∩Kk−1⟂.E_k=K_k\cap K_{k-1}^{\perp}.(3)✦ The projection Πk\Pi_k is the orthogonal projection of ℂΩ\mathbb{C}^{\Omega} onto EkE_k, taken as a complex Ω×Ω\Omega\times\Omega matrix in the point basis.✦

The Claim

Theorem 1. Let pp be a real multilinear polynomial in nn variables of degree at most dd.

(i) The function χp\chi p, which sends xx to χ(x)p(x)\chi(x)\,p(x), lies in the span of the characters χS\chi_S with |S|≥n−d|S|\ge n-d: χp∈V≥n−d.\chi p\in V_{\ge n-d}.(4)✦

(ii) Suppose moreover that p(x)≠0p(x)\ne 0 at every point xx of Ω\Omega. Let Π0,…,Πn\Pi_0,\dots,\Pi_n be the projections onto the layers of the weighted Fourier flag of the weight w=|p|w=|p|, and let HH be the diagonal matrix of multiplication by h=χsgn(p)h=\chi\,\mathrm{sgn}(p). Then for all rr and ss in {0,…,n}\{0,\dots,n\} with r+s<n−dr+s<n-d, ΠsHΠr=0.\Pi_s H\Pi_r=0.(5)✦

In the paper, the result reads: with w=|p|w=|p| and HH the multiplication by h=χsgn(p)h=\chi\,\mathrm{sgn}(p), ΠsHΠr=0\Pi_s H\Pi_r=0 if r+s<n−dr+s<n-d.

What Is Checked

The claim is stated over the cube Ω\Omega with its real coordinates, the characters χS\chi_S and the full parity χ\chi, real multilinear polynomials and their values on Ω\Omega, the threshold sign and the polynomial threshold function sgn(p)\mathrm{sgn}(p), the spaces VkV_k and V≥kV_{\ge k} of (1), and, for the weight w=|p|w=|p|, the scaling DD, the weighted Fourier flag with its layers (3), and the matrices of the projections Πk\Pi_k and of HH in the point basis.