Average sensitivity of polynomial threshold functions

1 · The essentials

Imagine a rule that reads a string of bits and returns one of two answers. The rules studied here make their decision from whether a polynomial’s value is negative or nonnegative. To measure how easily an answer changes, choose a bit string uniformly at random and count how many individual bit flips would change the answer. The average of that count is called average sensitivity. The main result says it is at most $8 d n$ , where $n$ is the number of bits and the polynomial has degree at most $d$ , with $1 \leq d \leq n$ . The rule assigns the positive answer when the polynomial is exactly zero. This bound has a Lean formalization and establishes what the source calls the asymptotic form of the Gotsman–Linial conjecture.

A picture to help (an imperfect image, not to be taken literally)

As an imperfect image, picture a panel of switches connected to a lamp: at a randomly chosen setting, count how many switches would change the lamp’s state if flipped individually. Average sensitivity is like the average of that count, but the result applies specifically to rules determined by the sign of a polynomial, not to every possible switch panel.

Why it matters

The result links the degree of a polynomial decision rule to how often its answer can change under single-bit flips. Its bound holds uniformly across all the stated choices of degree and number of bits. The source identifies this as establishing the asymptotic Gotsman–Linial conjecture.

2 · Going further

A polynomial threshold function assigns an output according to the sign of a polynomial evaluated on the Boolean cube. For a uniformly chosen input $x$ , let $x^{(i)}$ denote the input obtained by flipping bit $i$ . Its average sensitivity is $AS (f) = E_{x} [# {i : f (x) \neq = f (x^{(i)})}]$ : the expected number of single-bit flips that change the output.

The main manuscript states that for every $n \geq 1$ and $1 \leq d \leq n$ , every such function represented by a polynomial of degree at most $d$ satisfies $AS (f) \leq 8 d n$ . The bound is uniform in both parameters. Polynomial zeros are allowed, with the explicit convention $sgn (0) = 1$ . The source describes this result as establishing the asymptotic form of the Gotsman–Linial conjecture, and identifies the main result as Lean-formalized.

The supplied abstract states the result but does not describe the argument, so it does not provide a basis for explaining a proof strategy. Only the main manuscript is supplied; no companion manuscripts or relationships between their arguments are described.

Useful notions

Bit strings and single-bit flips
Uniform random choice and averages
Polynomials and their degree
The sign of a number

What was known before / what is new

Before

The source identifies the asymptotic Gotsman–Linial conjecture as the question resolved by this bound. It gives no earlier bounds, historical timeline, or account of previous methods.

New

The main result supplies the explicit bound $8 d n$ for every $n \geq 1$ and $1 \leq d \leq n$ , uniformly in both parameters. It allows polynomial zeros under the convention $sgn (0) = 1$ . The main bound has a Lean formalization.

Limits and assumptions

The statement concerns polynomial threshold functions on the uniformly distributed Boolean cube, with degree at most $d$ and $1 \leq d \leq n$ . Its zero-value convention is part of the statement. The source establishes the asymptotic form of the named conjecture; it does not state a sharper or exact form here. The main bound is identified as Lean-formalized, but the supplied material does not detail the formalization’s internal scope or describe any remaining open questions.

Mini glossary

Boolean cube: The collection of all bit strings of a fixed length $n$ .
Polynomial threshold function: A two-valued rule whose output is determined by the sign of a polynomial, with zero assigned the positive output here.
Average sensitivity: The expected number of individual bit flips that change a function’s output at a uniformly chosen input.
Uniform distribution: A choice of input in which every bit string has the same probability.
Uniform bound: A bound given by the same expression for every allowed choice of the parameters.

Keywords : Polynomial threshold functions · Average sensitivity · Gotsman–Linial conjecture

AI-generated explanation based on the manuscript. Unofficial. Refer to the manuscript for the authoritative version.

3 · Technical details and sources

Claim made in the manuscript (source text)

Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most $8 d n$ , uniformly for $1 \leq d \leq n$ . Average sensitivity counts expected output changes under single-bit flips. This establishes the asymptotic Gotsman–Linial conjecture, allowing polynomial zeros with $sign (0) = 1$ .

Verified by Lean: the Lean software checked the part of the reasoning described below, sometimes only part of the manuscript. This does not mean independent mathematicians have validated the result.

Scope of the Lean formalization (source text)

…

lean/docs/127.md

Manuscripts in this family

★

Average sensitivity of polynomial threshold functions

25/09/2026

Verified by Lean

For every n ≥ 1 and $1 \leq d \leq n$ , we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most $8 d n$ . This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention $sgn (0) = 1$ .

PDF GitHub folder Lean formalization