The Setting
The cube is the set of points whose coordinates are the real numbers ; it has points.✦ Take a real multilinear polynomial of degree at most on and the polynomial threshold function , where for and for . The question is how large its average sensitivity , defined below, can be in terms of and . Theorem 1 of the paper behind the library, Average sensitivity of polynomial threshold functions, answers it, and the last step of its proof turns statements about operators on into a bound on .
In that proof the weight is , and is the diagonal matrix on that multiplies each value at a point by . For , is the orthogonal projection onto , where is the image under of the span of the characters with , and . The centered grading of the projections is the matrix on .
The full parity is the character of all coordinates, .✦ With and multiplication by , put . The set consists of the ordered pairs of points of at Hamming distance with .
The library states the last step in two forms: one in which a family of orthogonal projections on takes the place of , and one that involves only and two real numbers.
Average Sensitivity
For a point of and a coordinate , the flip is the point of obtained from by reversing its -th coordinate.✦ A sensitive vertex of a real function on in direction is a point of with .✦ The average sensitivity of a real function on is the number of its sensitive vertices, counted over the directions and divided by ; for uniform on , (1)✦
Multiplication Matrices and Projection Families
The multiplication matrix of a real function on is the diagonal complex matrix indexed by with entry at each point .✦ For , the coordinate matrix is the multiplication matrix of the coordinate function .✦
A family of complex square matrices , one for each in a finite index set and all indexed by the same finite set, is an orthogonal projection family if it decomposes the identity into mutually orthogonal self-adjoint projections: (2)✦
A complex square matrix is block tridiagonal with respect to a family of complex square matrices indexed by the same finite set as if couples the index only to the indices , and : (3)✦
The Claim
Theorem 1. Let be a nonnegative integer and a real function on the cube .
Suppose that takes only the values , and let be multiplication by . Let be an orthogonal projection family (2) of complex square matrices indexed by such that for every , every coordinate matrix is block tridiagonal (3) with respect to , and whenever . Then (4)✦
Suppose that and are real numbers with , and . Then (5)✦
In the paper, the result reads , with in the place of and in that of .
What Is Checked
The claims (4) and (5) are stated over the cube with its coordinates and flips , and over the average sensitivity (1) built from sensitive vertices; (4) is stated also over the full parity , the multiplication matrices and , orthogonal projection families and block tridiagonal matrices.