How sensitive can it be?

0:00Threshold functions and sensitivity

Take the Boolean cube: all strings of n pluses and minuses. A polynomial threshold function of degree d labels each corner by the sign of a real polynomial of degree at most d; degree one gives a halfspace, like majority. Its average sensitivity, also called total influence, counts how many of the n coordinates, on average over the corners, change the label when flipped one at a time. For majority it is of order √n. Taking the sign of a degree-d polynomial in the number of pluses, with one root in each of the d gaps between levels closest to the middle, gives about d√n, as long as d is at most about √n. In our check, these symmetric examples come out between about 0.7 and 0.8 times d√n, approaching √(2/π) when d is small compared with √n. In 1994, Gotsman and Linial conjectured that these symmetric functions are the extreme ones. That exact form turned out to be false: Chapman, and independently Kim, Maldonado and Wellens, found counterexamples. The asymptotic form, that average sensitivity is at most a constant times d√n, stayed open. Two independent teams, Harsha, Klivans and Meka, and Diakonikolas, Raghavendra, Servedio and Tan, proved bounds that grow more slowly than n, for each fixed degree, with an exponent of n that approaches one as d grows. Kane reached root n, up to a power of log n that grows with d, and a factor that grows very fast with d. The question was whether those losses are needed.

1:37The claim

Result 127 is a single OpenAI preprint, 13 pages, dated September 25. It claims that every polynomial threshold function of degree at most d on the n-dimensional cube has average sensitivity at most 8d√n, for every n and every d from one to n. The polynomial may vanish on the cube, with the sign of zero taken as plus one, and no regularity is assumed. The constant is absolute, and d may grow with n. Together with the symmetric examples, this pins the largest possible average sensitivity at order d√n, whenever d is at most √n; beyond that, the trivial bound n takes over. It makes no claim about the exact extremal functions. The paper makes no claim that the constant eight is the best possible, and the symmetric examples sit near 0.8, ten times lower. And since average sensitivity is never more than n, the bound adds something only when n exceeds 64d². The paper also derives a noise-sensitivity bound of at most a constant times d√η, and an agnostic learning algorithm for these functions under the uniform distribution. OpenAI published a Lean formalization of the main theorem, 22 files and about 4,000 lines with its imports, not counting Mathlib; the two consequences are not part of it. We have not run the Lean check ourselves.

3:07How the proof goes

The proof has two parts. The first is a probability lemma. Let U and V have the same distribution, with variance σ², and suppose V − U is never more than a. Then the expected squared gap between them is at most 8aσ, even though U − V may be large. The trick is a primitive of the distance to the mean, ½(t − m)|t − m|, whose increments dominate a quarter of the squared gap; equal laws make its expected change zero, so its total change is twice its upward change, and each upward step is at most a times the distance to the mean, which averages to at most σ. In our check, the worst coupling of two binomials with 100 trials and V − U at most one gives an expected squared gap of about 15, against a bound of 40. The second part is an operator on functions on the cube. Take the polynomials of degree at most k, multiply them by the square root of a positive weight, and orthogonalize: you get layers of dimension C(n, k). Give the k-th layer the eigenvalue k − n/2. With the constant weight, this operator is minus one half times the adjacency matrix of the cube. For any weight, its squared Hilbert–Schmidt norm is fixed, at n·2ⁿ/4, and multiplying by a coordinate only links each layer to itself and its immediate neighbours. These two facts show that each edge entry has size at most 1/2, and that the total shortfall on edges is at most twice the squared mass on the diagonal. For a sign function h, the anticommutator of this operator with multiplication by h kills every entry between corners where h differs, and doubles, up to sign, every entry where h agrees, including the diagonal and those edges. So the number of edges where h agrees is at most twice its squared norm. Now multiply f by the full parity: the edges where the new function agrees are exactly the sensitive edges of f. Take the weight to be the absolute value of the polynomial, after a tiny shift that removes zeros without changing any sign. Multiplying the polynomial by parity moves its Fourier support to degrees at least n − d. Since h times the weight is exactly this product, the blocks of multiplication by h between layers r and s vanish whenever r + s is less than n − d. The squared norms of the remaining blocks form a probability law on pairs of layers, with both marginals binomial, with n trials and probability one half. Reflect one index: U is the index s, and V is n − r. They have the same law, and the vanishing blocks say that V − U is at most d. The anticommutator’s blocks are those of h, scaled by r + s − n, so its squared norm over 2ⁿ is exactly the expected squared gap between U and V. The lemma, with σ = √n/2, bounds that gap by 4d√n, and the edge count turns this into 8d√n. In our check, we rebuilt the weighted layers on cubes of up to 7 dimensions, with random polynomials, and checked the key identities, the binomial coupling and the whole chain of inequalities: all held.

6:29Where it stands

The preprint is not peer reviewed and has not been revised. The Lean formalization covers the main theorem; we have not run it. The paper is not among those OSVerify reviewed, and we have seen no expert review. If it holds, the asymptotic Gotsman–Linial conjecture is settled: polynomial threshold functions of degree d have average sensitivity at most a constant times d√n, with an absolute constant, by a short argument. The paper does not determine which functions are exactly extremal; the original symmetric guess is already known to fail.