OctoInformBeta

OpenAI preprint, September 2026 · §1. Introduction

Average sensitivity and polynomial threshold functions: The share of points where reversing coordinate ii changes a real function, summed over ii, and the sign of a real polynomial

Average sensitivity and polynomial threshold functions on the cube.

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

Two points of the nn-dimensional Boolean cube are neighbours when they differ in exactly one coordinate, and a function on the cube either changes its value across such an edge or keeps it. Its average sensitivity measures how often it changes, direction by direction. For a polynomial threshold function of degree dd, the sign of a real multilinear polynomial of degree at most dd evaluated at the points of the cube, the Gotsman-Linial conjecture concerns how large the average sensitivity can be in terms of nn and dd.

The Definition

Definition 1. The Boolean cube Ω\Omega is the set of strings xx of nn Boolean values, true or false, each read as a sign: Ω={−1,1}n.\Omega = \{-1, 1\}^n.(1)✦ For i=1,…,ni = 1, \dots, n, the ii-th coordinate of a point x∈Ωx \in \Omega is the real number xi={1if the i-th value of x is true,−1if it is false.x_i = \begin{cases} 1 & \text{if the $i$-th value of $x$ is true,} \\ -1 & \text{if it is false.} \end{cases}(2)✦ For x∈Ωx \in \Omega and a coordinate ii, the point x⊕i∈Ωx^{\oplus i} \in \Omega is xx with its ii-th coordinate reversed: (x⊕i)j={−xiif j=i,xjif j≠i.(x^{\oplus i})_j = \begin{cases} -x_i & \text{if } j = i, \\ x_j & \text{if } j \neq i. \end{cases}(3)✦ The sign sgn⁡(t)\operatorname{sgn}(t) of a real number tt is the number sgn⁡(t)={1if t≥0,−1if t<0.\operatorname{sgn}(t) = \begin{cases} 1 & \text{if } t \geq 0, \\ -1 & \text{if } t < 0. \end{cases}(4)✦ For a function f:Ω→ℝf \colon \Omega \to \mathbb{R} and a coordinate ii, the sensitive vertices of ff in direction ii form the set Sens⁡i(f)⊆Ω\operatorname{Sens}_i(f) \subseteq \Omega of the points at which reversing the ii-th coordinate changes the value of ff: Sens⁡i(f)={x∈Ω:f(x⊕i)≠f(x)}.\operatorname{Sens}_i(f) = \{\, x \in \Omega : f(x^{\oplus i}) \neq f(x) \,\}.(5)✦ With XX a uniform random point of Ω\Omega, the average sensitivity of a function f:Ω→ℝf \colon \Omega \to \mathbb{R} is the number I(f)=∑i=1n|Sens⁡i(f)|2n=∑i=1n𝑷{f(X⊕i)≠f(X)}.I(f) = \sum_{i=1}^{n} \frac{|\operatorname{Sens}_i(f)|}{2^n} = \sum_{i=1}^{n} \mathbf{P}\{ f(X^{\oplus i}) \neq f(X) \}.(6)✦ A real polynomial p=∑αcαx1α1⋯xnαnp = \sum_\alpha c_\alpha x_1^{\alpha_1} \cdots x_n^{\alpha_n} in the variables x1,…,xnx_1, \dots, x_n, with real coefficients cαc_\alpha and exponent vectors α=(α1,…,αn)\alpha = (\alpha_1, \dots, \alpha_n) of nonnegative integers, is multilinear when no variable occurs in a monomial of pp with an exponent above one: cα≠0⟹αi≤1 for i=1,…,n.c_\alpha \neq 0 \implies \alpha_i \leq 1 \text{ for } i = 1, \dots, n.(7)✦ The value of a real polynomial pp in x1,…,xnx_1, \dots, x_n at a point x∈Ωx \in \Omega is pp evaluated at the coordinates (2) of xx: p(x)=∑αcαx1α1⋯xnαn.p(x) = \sum_\alpha c_\alpha x_1^{\alpha_1} \cdots x_n^{\alpha_n}.(8)✦ The polynomial threshold function of a real polynomial pp in x1,…,xnx_1, \dots, x_n is the function sgn⁡(p):Ω→ℝ\operatorname{sgn}(p) \colon \Omega \to \mathbb{R} given by sgn⁡(p)(x)=sgn⁡(p(x)),x∈Ω.\operatorname{sgn}(p)(x) = \operatorname{sgn}\bigl(p(x)\bigr), \qquad x \in \Omega.(9)✦

What Is Checked

The definitions are stated over the cube Ω\Omega of strings of nn Boolean values, over real-valued functions on Ω\Omega, and over polynomials in x1,…,xnx_1, \dots, x_n with real coefficients.