The Setting
Let be a Boolean function on the cube , a function with values , such as a polynomial threshold function , where is a real multilinear polynomial and for and for . Its average sensitivity measures how often changes value along an edge of the cube. Multiplying by the full parity gives its parity twist , and the question is how is read off from : along how many ordered edges of the cube is constant?
The Cube and Its Edges
The Boolean hypercube of dimension is the set of all points that assign a sign to each index between and ; it has points.✦
For a point of and an index , the coordinate of is the real number if the -th sign of is positive and if it is negative.✦
For a point of and an index , the coordinate flip is the point of obtained from by reversing its -th sign, the other coordinates unchanged.✦
The full parity is the character of all coordinates, the real function on given by (1)✦
The Hamming distance of two points and of is the number of coordinates in which they differ. An ordered edge of , or ordered neighbor pair, is an ordered pair of points of with .✦
For a real function on , the set of ordered constant edges of is the set of ordered edges of on which takes equal values: (2)✦
Sensitivity
For a real function on and an index , the set of sensitive vertices of in direction is the set of points of at which reversing the -th coordinate changes the value of : (3)✦
For a real function on , the sensitive edge count of is the number of its ordered sensitive edges, the pairs with , that is (4)✦
The average sensitivity of is the real number (5)✦ whose -th term is for uniform on .
The Claim
Theorem 1. Let be a real function on taking only the values and , and let be its parity twist. Then the ordered constant edges of are as many as the ordered sensitive edges of , (6)✦ and the average sensitivity of is (7)✦
What Is Checked
The claim is stated over the cube with its real coordinates and coordinate flips, the full parity of (1), the ordered edges of and the ordered constant edges of (2), the sensitive vertices , the sensitive edge count and the average sensitivity , for every real function on with values .