OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Theorem 1: The sign of a real multilinear polynomial of degree at most dd in nn variables, with sgn⁡(0)=1\operatorname{sgn}(0) = 1, for all nn and dd

Degree-dd threshold functions have average sensitivity at most 8dn8d\sqrt{n}..

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

Fix nn and dd and consider the Boolean functions on the cube Ω={−1,1}n\Omega = \{-1,1\}^n that are the sign of a real polynomial of degree at most dd: the polynomial threshold functions of degree dd. Along an edge of the cube, from a point to a point that differs from it in one coordinate, such a function ff may change value or not, and its average sensitivity I(f)I(f) measures how often it does. The question is how large I(f)I(f) can be in terms of nn and dd; Gotsman and Linial conjectured that it is at most of order dnd\sqrt{n}.

Threshold Functions on the Cube

A point x=(x1,…,xn)x = (x_1, \dots, x_n) of the cube Ω\Omega is a sequence of nn signs xi∈{−1,1}x_i \in \{-1,1\}, and Ω\Omega has N=2nN = 2^n points.✦ For a point xx of Ω\Omega and a coordinate i∈{1,…,n}i \in \{1, \dots, n\}, the point x⊕ix^{\oplus i} of Ω\Omega is xx with its ii-th coordinate reversed.✦

A real polynomial pp in the variables x1,…,xnx_1, \dots, x_n is multilinear if every monomial occurring in pp with a nonzero coefficient has degree at most one in each variable; such a polynomial of total degree at most dd has the form p=∑S⊆{1,…,n},|S|≤dcS∏j∈Sxj,cS∈ℝ.p = \sum_{S \subseteq \{1, \dots, n\},\ |S| \le d} c_S \prod_{j \in S} x_j, \qquad c_S \in \mathbb{R}.(1)✦ The value p(x)p(x) of a real polynomial pp at a point xx of Ω\Omega is the real number obtained by substituting the coordinates x1,…,xnx_1, \dots, x_n of xx for the variables.✦

The sign function sgn\operatorname{sgn} is the function from ℝ\mathbb{R} to {−1,1}\{-1,1\} 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 in x1,…,xnx_1, \dots, x_n is the function sgn⁡(p)\operatorname{sgn}(p) on Ω\Omega that takes the value sgn⁡(p(x))\operatorname{sgn}(p(x)) at each point xx.✦

Average Sensitivity

Let ff be a real function on Ω\Omega and ii a coordinate. A point xx of Ω\Omega is sensitive for ff in direction ii if f(x⊕i)≠f(x)f(x^{\oplus i}) \ne f(x).✦ The average sensitivity I(f)I(f) of ff is the sum, over the nn directions, of the fraction of points of Ω\Omega that are sensitive for ff in that direction: with XX a uniform random point of Ω\Omega, I(f)=1N∑i=1n|{x∈Ω:f(x⊕i)≠f(x)}|=∑i=1n𝑷{f(X)≠f(X⊕i)}.I(f) = \frac{1}{N} \sum_{i=1}^{n} \bigl|\{x \in \Omega : f(x^{\oplus i}) \ne f(x)\}\bigr| = \sum_{i=1}^{n} \mathbf{P}\{f(X) \ne f(X^{\oplus i})\}.(3)✦

The Claim

Theorem 1. Let nn and dd be integers with 1≤d≤n1 \le d \le n, and let pp be a real multilinear polynomial in x1,…,xnx_1, \dots, x_n of degree at most dd. Then the polynomial threshold function f=sgn⁡(p)f = \operatorname{sgn}(p) satisfies I(f)≤8dn.I(f) \le 8d\sqrt{n}.(4)✦ More generally, let n,d≥0n, d \ge 0 be any integers and pp any real multilinear polynomial in x1,…,xnx_1, \dots, x_n of degree at most dd. Then I(sgn⁡(p))≤8dn.I(\operatorname{sgn}(p)) \le 8d\sqrt{n}.(5)✦

What Is Checked

The claim is stated over the cube Ω\Omega with its coordinate reversals x↦x⊕ix \mapsto x^{\oplus i}, the real multilinear polynomials of total degree at most dd read at the points of Ω\Omega, the sign function (2) with sgn⁡(0)=1\operatorname{sgn}(0) = 1, the polynomial threshold function sgn⁡(p)\operatorname{sgn}(p), and the average sensitivity (3), counted through the points sensitive in each direction.