OctoInformBeta

OpenAI preprint, September 2026 · §5. Parity and the binomial coupling (proof of Theorem 1) · equation (13)

The parity twist: For ff with values ±1\pm 1, the ordered edges on which χf\chi f is constant are as many as those along which ff changes

Average sensitivity of a Boolean function from its parity twist.

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

Let ff be a Boolean function on the cube Ω={−1,1}n\Omega=\{-1,1\}^n, a function with values ±1\pm 1, such as a polynomial threshold function f=sgn⁡(p)f=\operatorname{sgn}(p), where pp is a real multilinear polynomial and sgn⁡(t)=1\operatorname{sgn}(t)=1 for t≥0t\ge 0 and −1-1 for t<0t<0. Its average sensitivity I(f)I(f) measures how often ff changes value along an edge of the cube. Multiplying ff by the full parity χ\chi gives its parity twist h=χfh=\chi f, and the question is how I(f)I(f) is read off from hh: along how many ordered edges of the cube is hh constant?

The Cube and Its Edges

The Boolean hypercube Ω\Omega of dimension nn is the set {−1,1}n\{-1,1\}^n of all points that assign a sign ±1\pm 1 to each index ii between 11 and nn; it has 2n2^n points.✦

For a point xx of Ω\Omega and an index ii, the coordinate xix_i of xx is the real number 11 if the ii-th sign of xx is positive and −1-1 if it is negative.✦

For a point xx of Ω\Omega and an index ii, the coordinate flip x⊕ix^{\oplus i} is the point of Ω\Omega obtained from xx by reversing its ii-th sign, the other coordinates unchanged.✦

The full parity χ\chi is the character of all nn coordinates, the real function on Ω\Omega given by χ(x)=∏i=1nxi.\chi(x)=\prod_{i=1}^{n} x_i .(1)✦

The Hamming distance ρ(x,y)\rho(x,y) of two points xx and yy of Ω\Omega is the number of coordinates in which they differ. An ordered edge of Ω\Omega, or ordered neighbor pair, is an ordered pair (x,y)(x,y) of points of Ω\Omega with ρ(x,y)=1\rho(x,y)=1.✦

For a real function hh on Ω\Omega, the set ℰh\mathcal{E}_h of ordered constant edges of hh is the set of ordered edges of Ω\Omega on which hh takes equal values: ℰh={(x,y)∈Ω×Ω:ρ(x,y)=1,h(x)=h(y)}.\mathcal{E}_h=\{(x,y)\in\Omega\times\Omega:\ \rho(x,y)=1,\ h(x)=h(y)\}.(2)✦

Sensitivity

For a real function ff on Ω\Omega and an index ii, the set Si(f)S_i(f) of sensitive vertices of ff in direction ii is the set of points of Ω\Omega at which reversing the ii-th coordinate changes the value of ff: Si(f)={x∈Ω:f(x⊕i)≠f(x)}.S_i(f)=\{x\in\Omega:\ f(x^{\oplus i})\neq f(x)\}.(3)✦

For a real function ff on Ω\Omega, the sensitive edge count s(f)s(f) of ff is the number of its ordered sensitive edges, the pairs (x,x⊕i)(x,x^{\oplus i}) with x∈Si(f)x\in S_i(f), that is s(f)=∑i=1n|Si(f)|.s(f)=\sum_{i=1}^{n}|S_i(f)|.(4)✦

The average sensitivity I(f)I(f) of ff is the real number I(f)=∑i=1n|Si(f)|2n,I(f)=\sum_{i=1}^{n}\frac{|S_i(f)|}{2^n},(5)✦ whose ii-th term is 𝑷{f(X)≠f(X⊕i)}\mathbf{P}\{f(X)\neq f(X^{\oplus i})\} for XX uniform on Ω\Omega.

The Claim

Theorem 1. Let ff be a real function on Ω\Omega taking only the values 11 and −1-1, and let h=χfh=\chi f be its parity twist. Then the ordered constant edges of hh are as many as the ordered sensitive edges of ff, |ℰh|=s(f),|\mathcal{E}_h|=s(f),(6)✦ and the average sensitivity of ff is I(f)=|ℰh|2n.I(f)=\frac{|\mathcal{E}_h|}{2^n}.(7)✦

What Is Checked

The claim is stated over the cube Ω\Omega with its real coordinates and coordinate flips, the full parity χ\chi of (1), the ordered edges of Ω\Omega and the ordered constant edges ℰh\mathcal{E}_h of (2), the sensitive vertices Si(f)S_i(f), the sensitive edge count s(f)s(f) and the average sensitivity I(f)I(f), for every real function ff on Ω\Omega with values ±1\pm 1.