The Setting
In the proof of Theorem 1 of the paper on the average sensitivity of polynomial threshold functions, take a polynomial threshold function of degree at most on the cube , with and , where is the full parity, the character of all coordinates. With the multiplication by and the span of the characters with , put , and ; the space is the orthogonal sum of , and the projections onto these pieces give the grading and the centered grading . The operator of multiplication by is unitary, and the quantity to bound is for the anticommutator .
An operator on splits into the blocks , one for each pair in , the block carrying into . The item is about these blocks: how anticommuting with acts on them, and how the masses of the blocks of a unitary spread over the pairs .
The library states the item for complex matrices with rows and columns indexed by a finite set , the operators on , with any family of mutually orthogonal projections summing to the identity in place of the projections onto the , and any matrix in place of multiplication by .
Projection Families and Block Masses
Fix a finite set . The squared Hilbert-Schmidt norm of a complex matrix with rows indexed by and columns indexed by a finite set is .✦
A family of matrices on , one for each in a finite index set, is an orthogonal projection family if each is self-adjoint and idempotent, , if for , and if .✦
The grading of a family of matrices on with real weights is the matrix .✦ The centered grading of a family of matrices on is the matrix obtained from the grading by taking the weights : (1)✦
The binomial weights of order are the probabilities , , of the binomial law .✦
The block coupling weight of a family and a matrix on is the function on given by (2)✦
The Claim
Theorem 1. Let be a finite set, and natural numbers, and matrices on , the centered grading (1) of the , and the block coupling weight (2) of the and .
If the form an orthogonal projection family, then every matrix on satisfies, for all , (3)✦ and (4)✦
Suppose the form an orthogonal projection family with for every . If , then for every (5)✦ and if , then for every (6)✦
If whenever , then (7)✦
If is an array of nonnegative reals with row sums for every and column sums for every , and with whenever , then (8)✦
If the form an orthogonal projection family with for every , is unitary, and whenever , then (9)✦
In the paper, the result reads: for and , ; the weights form the law of a pair with marginals supported on ; and Lemma 2 with , , and gives .
What Is Checked
The claim is stated over families and matrices on for a finite set , orthogonal projection families, the centered grading , the squared Hilbert-Schmidt norm, the binomial weights and the block coupling weight , and in part (d) over arrays of nonnegative reals indexed by .