OctoInformBeta

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

Removing zeros: Multilinear of degree at most dd, and without zeros the average sensitivity is at most 8dn8d\sqrt{n}

Every polynomial threshold function has a polynomial without zeros.

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 multilinear polynomial pp of degree at most dd in nn variables and the polynomial threshold function f=sgn⁡(p)f = \operatorname{sgn}(p) it defines on the cube Ω={−1,1}n\Omega = \{-1,1\}^n, where sgn⁡(t)\operatorname{sgn}(t) is 11 for t≥0t \ge 0 and −1-1 for t<0t < 0. The polynomial may vanish on the cube: p(x)=x1+x2p(x) = x_1 + x_2 is zero at every point with x2=−x1x_2 = -x_1, and ff takes the value 11 there. Can pp be replaced by a multilinear polynomial of degree at most dd that defines the same ff and vanishes nowhere on Ω\Omega? And once pp has no zero on Ω\Omega, how large can the average sensitivity of ff be, that is, the expected number of coordinates ii for which reversing the ii-th coordinate of a uniform random point changes the value of ff?

Polynomials on the Cube

The Boolean cube Ω\Omega is the set of points x=(x1,…,xn)x = (x_1, \dots, x_n) whose coordinates xix_i are the real numbers 11 or −1-1; it has N=2nN = 2^n points.✦ For a point xx of Ω\Omega and an index ii between 11 and nn, the point x⊕ix^{\oplus i} of Ω\Omega is xx with its ii-th coordinate reversed and the others unchanged.✦

A real polynomial pp in nn variables is multilinear when every monomial with a nonzero coefficient in pp has each variable to the power at most one.✦ For a subset SS of {1,…,n}\{1, \dots, n\}, the character χS\chi_S of SS is the function χS(x)=∏j∈Sxj\chi_S(x) = \prod_{j \in S} x_j on Ω\Omega; a multilinear polynomial is a real combination of these characters, one for each subset SS of {1,…,n}\{1, \dots, n\}, p=∑S⊆{1,…,n}cSχS,cS∈ℝ,p = \sum_{S \subseteq \{1, \dots, n\}} c_S \, \chi_S, \qquad c_S \in \mathbb{R},(1) The degree of a multilinear polynomial p=∑ScSχSp = \sum_S c_S \chi_S is the largest |S||S| with cS≠0c_S \neq 0.

The threshold sign is the function sgn\operatorname{sgn} on the real numbers given by sgn⁡(t)={1,t≥0,−1,t<0.\operatorname{sgn}(t) = \begin{cases} 1, & t \ge 0, \\ -1, & t < 0. \end{cases}(2)✦ The polynomial threshold function of a real polynomial pp is the function sgn⁡(p)\operatorname{sgn}(p) on Ω\Omega that sends each point xx to sgn⁡(p(x))\operatorname{sgn}(p(x)).✦

Average Sensitivity

For a real-valued function ff on Ω\Omega and an index ii between 11 and nn, the sensitive vertices of ff in direction ii are the points xx of Ω\Omega with f(x⊕i)≠f(x)f(x^{\oplus i}) \neq f(x).✦ The average sensitivity I(f)I(f) of a real-valued function ff on Ω\Omega is the sum over the directions ii of the number of sensitive vertices of ff in direction ii, divided by NN: I(f)=∑i=1n|{x∈Ω:f(x⊕i)≠f(x)}|N=∑i=1nPr⁡{f(X)≠f(X⊕i)},I(f) = \sum_{i=1}^{n} \frac{\bigl|\{x \in \Omega : f(x^{\oplus i}) \neq f(x)\}\bigr|}{N} = \sum_{i=1}^{n} \Pr\{f(X) \neq f(X^{\oplus i})\},(3)✦ with XX uniform on Ω\Omega.

The Claim

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

  1. There is a real multilinear polynomial qq of degree at most dd with q(x)≠0andsgn⁡(q(x))=sgn⁡(p(x))for every x∈Ω.q(x) \neq 0 \quad \text{and} \quad \operatorname{sgn}(q(x)) = \operatorname{sgn}(p(x)) \qquad \text{for every } x \in \Omega.(4)✦

  2. If pp has no zero on Ω\Omega, then I(sgn⁡(p))≤8dn.I(\operatorname{sgn}(p)) \le 8d\sqrt{n}.(5)✦

What Is Checked

The claims (4) and (5) are stated over real multilinear polynomials (1) of degree at most dd and their values at the points of Ω\Omega, the threshold sign (2) and the polynomial threshold functions it defines, and the average sensitivity (3), built from the reversed points x⊕ix^{\oplus i} and the sensitive vertices.