The Setting
The Boolean cube of dimension is the set of the points that assign a sign to each index between and ✦; the coordinate of a point is its sign at , the real number or .✦ Points and are neighbors when their Hamming distance , the number of indices at which they differ, is , and the ordered edges of are the ordered pairs of neighbors.✦ The set of constant edges of a real function on is the set of ordered edges along which is constant: (1)✦
In the proof of Theorem 1 of the source paper on the average sensitivity of polynomial threshold functions, is a polynomial threshold function, with a real multilinear polynomial, and , with the parity of all coordinates. Then is the set of ordered edges along which changes sign, and for the average sensitivity .
The weight there is , and the centered grading built from is , where and is the orthogonal projection onto , with , , multiplication by and the span of the characters with . With multiplication by , Lemma 3 bounds through the Hilbert-Schmidt norm of the anticommutator .
The library states this bound for any complex matrix on under three conditions on its entries. Two of them come from bounds on the commutators of with the multiplications by the coordinates , and the library bounds such commutators for the centered grading of a general family of orthogonal projections. The last part of the lemma is a counting inequality for nonnegative weights.
Matrices and Shells
A matrix on a finite set is a complex matrix with rows and columns indexed by ; on these are the operators on in the point basis. The commutator of two matrices and on is . The squared Hilbert-Schmidt norm of a complex matrix with rows and columns indexed by finite sets is the sum of the squared moduli of its entries, (2)✦
The multiplication matrix of a real function on is the diagonal matrix on with diagonal entries .✦ For between and , the matrix is the multiplication matrix of the coordinate .✦
The shell at of a function from a finite set to is the set .✦ For the Hamming distance on , the shell at is the set of ordered edges and the shell at is the diagonal.
Projection Families and Gradings
A finite family of matrices on is an orthogonal projection family if it decomposes the identity into Hermitian projections: each is self-adjoint and idempotent, ; distinct members are orthogonal, for ; and .✦
The weighted grading of a finite family of matrices on with real weights is the matrix on .✦ The centered grading of a family of matrices on is its weighted grading with weights , (3)✦
A matrix on is block tridiagonal with respect to a family of matrices on if whenever .✦
The Claim
Theorem 1. (a) Let be a matrix on , and let be a real function on with values in and multiplication matrix . Suppose that , that , and that whenever . Then (4)✦
(b) Let be an orthogonal projection family of matrices on a finite set with centered grading , and let be a unitary matrix on that is block tridiagonal with respect to the family. Then, for all , (5)✦ and (6)✦
(c) Let be a matrix on with for every and all . Then, for all distinct , (7)✦
(d) Let be a matrix on with for every . Then (8)✦
(e) Let be a function from a finite set to with shells , and let be a function from to with and . Then (9)✦
In the paper, the result reads: for , a weight with the centered grading built from it, and a function with multiplication by , .
What Is Checked
The claim is stated over the cube with its coordinates , its Hamming distance and its ordered edges, complex matrices on finite sets with their squared Hilbert-Schmidt norm, the multiplication matrices and , the set of constant edges, orthogonal projection families with their centered gradings, unitary matrices block tridiagonal with respect to such a family, and the shells of a function with values in . About these constructions the library also gives that the weighted grading of an orthogonal projection family acts as on the range of each , and that a centered grading equals , with , when its family sums to the identity.