The Setting
Take the cube , with points, and the space of complex functions on it, graded by Fourier degree. In the study of the average sensitivity of a polynomial threshold function , the grading is weighted by : the spaces of functions of degree at most are rescaled by , and splits into orthogonal layers, the -th holding what the rescaled space of degree at most adds to the one of degree at most . The question is how multiplication by one coordinate moves a function between these layers: from the layer of one degree, which layers can it reach?
The Weighted Grading
The cube of dimension is the set of points , each coordinate a real number . The character of a subset of is the function on ✦, and the space of functions of degree at most is the subspace of spanned by the characters of the sets of size at most , (1)✦ With the counting inner product , is a Hilbert space and each a subspace of it.
For a sequence of subspaces of a finite-dimensional inner product space , the layer at stage is the subspace of the vectors of orthogonal to ✦, and the layer projection is the orthogonal projection of onto it.✦ The image of the sequence under an invertible linear operator on is the sequence .✦
A positive weight on is a real function on with at every point . Its square root weight map is the operator on of multiplication by , (2)✦ and the weighted space of degree is the image of , for , with .
The shifted Fourier flag is the sequence of subspaces of , whose stage is .✦ The weighted Fourier flag of is its image under , the sequence .✦ The layer of the weighted Fourier flag at stage is (3) and its layer projection is the orthogonal projection of onto .
Matrices
The matrix of a linear operator on a finite-dimensional complex inner product space , in an orthonormal basis of , is the complex matrix with entries (4)✦ On the basis is the point basis of point masses, and an operator is identified with its matrix in it; the weighted projection matrix is the matrix of the layer projection of the weighted Fourier flag.✦
For a real function on , the multiplication matrix of is the diagonal matrix with entry at , the matrix of .✦ The coordinate matrix is the multiplication matrix of the coordinate : (5)✦
A complex square matrix is block tridiagonal with respect to complex matrices of the same size when its blocks between indices more than one apart vanish: (6)✦
The Claim
Theorem 1. Let be a positive weight on and let . Then is block tridiagonal with respect to the weighted projection matrices : (7)✦ More generally, let be a finite-dimensional inner product space, let be an increasing sequence of subspaces of with layer projections , and let be a self-adjoint operator on that maps each into . Then (8)✦
What Is Checked
The claim is stated over a positive weight on the cube , the coordinate matrix and the matrices , in the point basis, of the layer projections of the weighted Fourier flag; its general form is stated over an increasing sequence of subspaces of a finite-dimensional inner product space, its layer projections, and a self-adjoint operator that maps each stage into the next.
About these constructions the library proves that , and more generally multiplication by a function on that vanishes nowhere, is an invertible operator on , the inverse being multiplication by ✦; and that taking matrices in an orthonormal basis is an isomorphism of complex algebras from the linear operators on onto the complex square matrices indexed by the basis.✦