Average sensitivity of polynomial threshold functions

Source and verification

This article explains family 127 of the October 6, 2026 OpenAI collection. Research conclusions are attributed to its manuscripts. The review covers statements, introductions, and selected proof mechanisms; it is not an independent verification of the complete proofs.

🏷️ Polynomial thresholds and influence

A polynomial threshold function on the cube is

$$f(x)=\mathrm{sgn}p(x),x\in \{-1,1{\}}^n,$$

where $p$ is a real polynomial and $\mathrm{sgn}(0)=1$. Replacing powers using $x_i^2=1$ gives a multilinear polynomial of no greater degree with identical cube values.

For $x^{\oplus i}$ obtained by flipping coordinate $i$, define average sensitivity, also called total influence, by

$$I(f)=\sum _{i=1}^n\mathrm{Pr}[f(X)\ne f(X^{\oplus i})],$$

with $X$ uniform. Equivalently, count all directed cube edges across which $f$ changes sign and divide by $2^n$. Every undirected edge is counted twice. The trivial bound is $I(f)\le n$.

The degree of the threshold polynomial is not generally the Fourier degree of its sign function. A low-degree polynomial can have a sign with Fourier coefficients at many degrees, so an influence bound cannot simply apply the degree formula for $p$ to $f$.

Manuscript statement

For every $n\ge 1$, every $1\le d\le n$, and every real multilinear polynomial of degree at most $d$,

$$I(\mathrm{sgn}p)\le 8d\sqrt{n}.$$

The constant is independent of $d$ and $n$, and zeros of $p$ are allowed with the specified sign convention. (OpenAI, 2026)

This addresses the asymptotic Gotsman–Linial bound. The separate exact-extremizer conjecture is false and is not asserted here. When the displayed bound exceeds $n$, the trivial bound remains stronger. Constant thresholds have zero influence.

🏷️ Central Hamming layers explain the scale

Let $t(x)=(n+x_1+\cdots +x_n)/2$ be the number of positive coordinates. Choose $d$ indices $j$ near $(n-1)/2$, and set

$$p_J(x)=\prod _{j\in J}(t(x)-j-\frac{1}{2}).$$

The sign changes exactly between Hamming weights $j$ and $j+1$ for $j\in J$. At such a boundary, there are

$$(n-j)\left(\genfrac{}{}{0ex}{}{n}{j}\right)=n\left(\genfrac{}{}{0ex}{}{n-1}{j}\right)$$

undirected cube edges. Hence

$$I(\mathrm{sgn}{p}_J)=n{2}^{-(n-1)}\sum _{j\in J}\left(\genfrac{}{}{0ex}{}{n-1}{j}\right).$$

For $1\le d\le \sqrt{n}$, the selected binomial probabilities are each comparable to $n^{-1/2}$ by the central-binomial estimate and neighboring-coefficient ratios. Thus influence is of order $d\sqrt{n}$. This shows the scale is necessary over that degree range without identifying an exact maximizer.

For a concrete check, let $n=9$ and $J=\{3,4,5\}$. The influence is $9(56+70+56)/256=819/128$. This is an exact edge count for one symmetric example, not a numerical test of the universal bound.

🏷️ A one-sided coupling lemma

The probability ingredient is elementary but unusually useful. Suppose $U,V$ have the same distribution, mean $m$, and variance ${\sigma }^2$. If

$$V-U\le a\text{almost surely},$$

then the manuscript proves

$$\mathbb{E}(U-V{)}^2\le 8a\sigma .$$

Neither independence nor exchangeability is assumed. Large jumps in the opposite direction are allowed. Equal marginal laws provide the balance that replaces a two-sided displacement bound.

Define the increasing function

$$g(t)=\frac{1}{2}(t-m)|t-m|.$$

For $u<v$, integration of $|t-m|$ gives

$$\begin{array}{c}\frac{(v-u{)}^2}{4}\le g(v)-g(u),\\ \begin{array}{rl}& g(v)-g(u)\\ & \le \frac{v-u}{2}(|u-m|+|v-m|).\end{array}\end{array}$$

The first inequality follows by considering whether the interval crosses $m$; the second follows because a convex function lies below its endpoint chord on an interval.

Since $g(U)$ and $g(V)$ have equal expectations, the absolute expected change is twice its positive part. On that positive part, $0<V-U\le a$. Therefore

$$\begin{array}{rl}& \mathbb{E}|g(V)-g(U)|\\ & \\ & \le a\mathbb{E}(|U-m|+|V-m|)\\ & \le 2a\sigma .\\ & \end{array}$$

The lower increment bound gives $(U-V{)}^2\le 4|g(V)-g(U)|$, completing the proof. The case $a=0$ is included: equal laws and one-sided ordering force zero squared displacement.

🏷️ Weighted polynomial grades

The main construction converts a threshold polynomial into a coupling to which this lemma applies. Work in the space of functions on the $2^n$ cube vertices, with the counting inner product.

Let $V_k$ be the space of cube polynomials of degree at most $k$. For any positive weight $w$, multiply this nested sequence by $\sqrt{w}$ and take successive orthogonal increments $E_k$. Multiplication by $\sqrt{w}$ is invertible, so

$$\dim E_k=\left(\genfrac{}{}{0ex}{}{n}{k}\right).$$

Define a self-adjoint operator $M$ whose eigenvalue on $E_k$ is $k-n/2$. Its squared Hilbert–Schmidt norm, the sum of squared matrix entries, is fixed:

$$\begin{array}{rl}\Vert M{\Vert }_{\mathrm{HS}}^2& =\sum _k(k-n/2{)}^2(\genfrac{}{}{0ex}{}{n}{k})\\ & =\frac{n{2}^n}{4}.\end{array}$$

Coordinate multiplication raises degree by at most one and is self-adjoint. It therefore connects only equal or adjacent grades. These facts hold for every positive weight, even though the grade subspaces themselves move with the weight.

When $w=1$, the Fourier characters give $M$ as minus one-half the cube adjacency matrix. For general $w$, some edge entries shrink and other entries appear. The source’s edge-recovery lemma controls the total squared mass at distance at least two by diagonal mass and bounds individual edge entries. It then relates equal-sign edges to an anticommutator norm.

Specifically, if $H$ multiplies by a sign function $h$, then $(MH+HM{)}_{xy}=M_{xy}(h(x)+h(y))$. Opposite-sign entries vanish, while diagonal and equal-sign entries remain. The lemma proves

$$|{\mathcal{E}}_h|\le 2\Vert MH+HM{\Vert }_{\mathrm{HS}}^2,$$

where ${\mathcal{E}}_h$ is the set of directed neighboring pairs with equal $h$ values. This weighted edge estimate is a substantive operator input; it does not follow from the unweighted adjacency identity alone.

🏷️ Parity converts sensitivity into a grade constraint

Remove zeros of $p$ by adding a sufficiently small positive constant. Choose it below the absolute value of every negative value of $p$, if any. Then negative values stay negative, zeros become positive, and the threshold function is unchanged.

Set $w=|p|$, let $\chi (x)=x_1\cdots x_n$ be full parity, and put $h=\chi f$. Parity flips on every cube edge, so $h$ has equal signs exactly where $f$ changes sign. Thus

$$I(f)=2^{-n}|{\mathcal{E}}_h|.$$

Moreover, $hw=\chi p$ has Fourier support only in degrees at least $n-d$: multiplying a character by full parity replaces its index set by its complement.

Let ${\Pi }_r$ project to grade $E_r$. If $r+s<n-d$, an inner product between weighted polynomials from grades $r$ and $s$, with multiplication by $h$ between them, reduces to a cube sum of $\chi p$ against a polynomial of degree at most $r+s$. Character orthogonality therefore gives

$${\Pi }_{s}H{\Pi }_r=0(r+s<n-d).$$

This is how the polynomial degree produces a one-sided restriction on two grade indices, rather than directly bounding the Fourier degree of $f$.

🏷️ Binomial marginals and the constant eight

Define a joint law by

$$\begin{array}{rl}& \mathrm{Pr}[R=r,S=s]\\ & =2^{-n}\Vert {\Pi }_{s}H{\Pi }_r{\Vert }_{\mathrm{HS}}^2.\end{array}$$

Because $H$ is multiplication by a sign, it is unitary. Summing over $s$ gives $2^{-n}\dim E_r$, and summing over $r$ gives $2^{-n}\dim E_s$. Both marginals are therefore $\mathrm{Bin}(n,1/2)$.

Write $T=MH+HM$. Its $(s,r)$ grade block equals $(s+r-n){\Pi }_{s}H{\Pi }_r$, so

$$2^{-n}\Vert T{\Vert }_{\mathrm{HS}}^2=\mathbb{E}(R+S-n{)}^2.$$

Reflect one index: $U=S$ and $V=n-R$ have the same binomial law, variance $n/4$, and the vanishing region gives $V-U\le d$. The coupling lemma yields

$$2^{-n}\Vert T{\Vert }_{\mathrm{HS}}^2\le 4d\sqrt{n}.$$

Finally, the edge-recovery inequality gives $I(f)\le 2^{1-n}\Vert T{\Vert }_{\mathrm{HS}}^2\le 8d\sqrt{n}$. This proves the headline deduction from the weighted edge lemma and the grading properties, while keeping the ordered-edge normalization visible.

🏷️ Independent noise and learning consequences

Let ${\mathrm{NS}}_{\eta }(f)$ be the probability that $f$ changes when each input bit is independently flipped with probability $\eta$. The source derives a dimension-free estimate

$$\begin{array}{c}{\mathrm{NS}}_{\eta }(f)\le 8\sqrt{2}d\sqrt{\eta },\\ 0<\eta \le \frac{1}{2}.\end{array}$$

For rate $1/q$, randomly place original coordinates into $q$ buckets and multiply them by independent random signs. This gives a degree-at-most-$d$ threshold on a $q$-dimensional cube. Flipping one uniformly selected bucket reproduces independent rate-$1/q$ noise after averaging over the bucket choices and signs. Consequently its expected influence divided by $q$ bounds noise sensitivity by $8d/\sqrt{q}$. Monotonicity in the noise rate extends the bound to arbitrary $\eta$.

Noise smoothing then approximates each threshold function in $L_1$ by a polynomial of degree

$$O(d^2{\alpha }^{-2}\log (4/\alpha )),$$

or at most $n$ if that is smaller. Polynomial regression and independent validation yield agnostic learning with error at most the best degree-$d$ threshold error plus $\alpha$. Runtime and sample size are polynomial in the number of retained monomial features, $1/\alpha$, and the logarithm of inverse confidence. The input marginal must be uniform; labels may be arbitrary, and the returned hypothesis need not belong to the original threshold class.

🏷️ Key steps and proof outlines

A commutator bounds each weighted edge entry

The missing operator step is “Recovering edges from the anticommutator.” Let $Z_i$ multiply a cube function by coordinate $x_i$, and let ${\Pi }_k$ be the weighted grade projections. Because $Z_i$ changes polynomial grade by at most one, the commutator $C_i=M{Z}_i-Z_{i}M$ keeps only adjacent-grade blocks, multiplying a block from $r$ to $s$ by $s-r$. (OpenAI, 2026)

Define two unitary operators on the complexified function space,

$$J=\sum _k(-1{)}^k{\Pi }_k,W=\sum _k{\mathrm{i}}^k{\Pi }_k.$$

The operator $O_i=(Z_i-J{Z}_{i}J)/2$ removes equal-grade blocks and has norm at most one by the triangle inequality. Conjugating it by $W$ multiplies adjacent blocks by ${\mathrm{i}}^{s-r}=\mathrm{i}(s-r)$, so $W{O}_i{W}^{\ast }=\mathrm{i}{C}_i$. Therefore $\Vert C_i{\Vert }_{\mathrm{op}}\le 1$.

In the point basis, $(C_i{)}_{xy}=(y_i-x_i)M_{xy}$. For distinct vertices choose a coordinate where they differ. Its factor has magnitude two, giving $|M_{xy}|\le 1/2$. In particular every neighboring entry has squared magnitude at most its unweighted value $1/4$. This establishes a nonnegative deficit at each individual cube edge.

Long-range energy is paid by the diagonal

Let $N=2^n$, let $A_0={\sum }_x|M_{xx}{|}^2$, and let $F$ be squared mass on pairs of Hamming distance at least two. Summing the commutators’ squared Hilbert–Schmidt norms gives

$$\sum _{x,y}\mathrm{dist}(x,y)|M_{xy}{|}^2\le nN/4=\sum _{x,y}|M_{xy}{|}^2.$$

Subtract the right side. Distance-one terms cancel, diagonal terms contribute $-A_0$, and every farther term has coefficient at least one. Thus $F\le A_0$. Because the total energy is fixed, the full deficit on the $nN$ directed neighboring pairs is

$$\sum _{\mathrm{dist}(x,y)=1}\left(\frac{1}{4}-|M_{xy}{|}^2\right)=A_0+F\le 2A_0.$$

The weighted grading may shrink many edge entries, but it can do so only by moving energy into diagonal and farther entries, and the latter are themselves paid by the diagonal.

The anticommutator sees both the surviving edges and their deficit

Let $A_h$ be squared mass on directed neighboring pairs with equal $h$ values. Nonnegativity of every edge deficit bounds the deficit restricted to these pairs by the total deficit, so

$$|{\mathcal{E}}_h|/4\le A_h+2A_0\le 2(A_h+A_0).$$

For $T=MH+HM$, equal-sign and diagonal entries are multiplied by $\pm 2$, whereas opposite-sign entries vanish. Hence $\Vert T{\Vert }_{\mathrm{HS}}^2\ge 4(A_0+A_h)$. Combining these gives $|{\mathcal{E}}_h|\le 2\Vert T{\Vert }_{\mathrm{HS}}^2$ with the exact directed-edge normalization used earlier.

The parity construction then chooses $h$ so these equal-sign edges are precisely the sign-changing edges of the threshold function. Its grade-coupling law has binomial marginals because multiplication by $h$ is unitary. Low degree forbids $R+S<n-d$, which becomes a one-sided displacement bound after reflecting one index. The elementary equal-marginal coupling lemma controls the anticommutator energy, and the edge estimate converts that energy into influence. Thus the proof has three distinct conversions: polynomial degree to forbidden grade pairs, grade pairs to a displacement second moment, and weighted operator energy back to actual cube edges.

See Also

• Fourier degree and sensitivity concerns the degree of a Boolean function itself, clarifying why threshold degree requires a different argument.
• Noise and binary information uses the same cube noise operator for an information extremum rather than a sensitivity bound.

🏷️ Manuscripts and verification scope

• Average sensitivity of polynomial threshold functions — pinned manuscript and companion source.

The family scope page describes selected formalization coverage. The scope selects the bound 8d times the square root of n with the stated sign convention. It does not assert the separate exact-extremizer conjecture. No Lean build, axiom audit, or manuscript-to-formal-statement equivalence check was performed for these notes.

OpenAI collection provides prerequisites and the reading sequence; coverage register records completed and pending families.

🐻  OpenAI 2026. Average sensitivity of polynomial threshold functions.