OctoInformBeta

OpenAI preprint, September 2026 · §3. Weighted Fourier grading · equation (7)

Tridiagonality: For a positive weight ww, ΠsZiΠr=0\Pi_s Z_i \Pi_r = 0 whenever |r−s|>1|r-s|>1, as for any self-adjoint operator mapping each stage of a flag into the next

Coordinate multiplication is block tridiagonal in the weighted grading.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take the cube Ω={−1,1}n\Omega=\{-1,1\}^n, with N=2nN=2^n points, and the space ℂΩ\mathbb{C}^{\Omega} of complex functions on it, graded by Fourier degree. In the study of the average sensitivity of a polynomial threshold function f=sgn⁡(p)f=\operatorname{sgn}(p), the grading is weighted by w=|p|w=|p|: the spaces of functions of degree at most kk are rescaled by w\sqrt{w}, and ℂΩ\mathbb{C}^{\Omega} splits into orthogonal layers, the kk-th holding what the rescaled space of degree at most kk adds to the one of degree at most k−1k-1. The question is how multiplication by one coordinate xix_i moves a function between these layers: from the layer of one degree, which layers can it reach?

The Weighted Grading

The cube Ω\Omega of dimension nn is the set {−1,1}n\{-1,1\}^n of points x=(x1,…,xn)x=(x_1,\dots,x_n), each coordinate xix_i a real number ±1\pm1. The character χS\chi_S of a subset SS of {1,…,n}\{1,\dots,n\} is the function χS(x)=∏j∈Sxj\chi_S(x)=\prod_{j\in S}x_j on Ω\Omega✦, and the space VkV_k of functions of degree at most kk is the subspace of ℂΩ\mathbb{C}^{\Omega} spanned by the characters of the sets of size at most kk, Vk=span⁡{χS:|S|≤k}.V_k=\operatorname{span}\{\chi_S : |S|\le k\}.(1)✦ With the counting inner product ⟨f,g⟩=∑x∈Ωf(x)¯g(x)\langle f,g\rangle=\sum_{x\in\Omega}\overline{f(x)}\,g(x), ℂΩ\mathbb{C}^{\Omega} is a Hilbert space and each VkV_k a subspace of it.

For a sequence F0,F1,…F_0,F_1,\dots of subspaces of a finite-dimensional inner product space UU, the layer at stage kk is the subspace Fk+1∩Fk⟂F_{k+1}\cap F_k^{\perp} of the vectors of Fk+1F_{k+1} orthogonal to FkF_k✦, and the layer projection PkP_k is the orthogonal projection of UU onto it.✦ The image of the sequence under an invertible linear operator DD on UU is the sequence DF0,DF1,…DF_0,DF_1,\dots.✦

A positive weight on Ω\Omega is a real function ww on Ω\Omega with w(x)>0w(x)>0 at every point xx. Its square root weight map DD is the operator on ℂΩ\mathbb{C}^{\Omega} of multiplication by w\sqrt{w}, (Df)(x)=w(x)f(x)(x∈Ω),(Df)(x)=\sqrt{w(x)}\,f(x)\qquad(x\in\Omega),(2)✦ and the weighted space KkK_k of degree kk is the image DVkDV_k of VkV_k, for k=0,…,nk=0,\dots,n, with K−1={0}K_{-1}=\{0\}.

The shifted Fourier flag is the sequence {0},V0,V1,…\{0\},V_0,V_1,\dots of subspaces of ℂΩ\mathbb{C}^{\Omega}, whose stage k+1k+1 is VkV_k.✦ The weighted Fourier flag of ww is its image under DD, the sequence {0},K0,K1,…\{0\},K_0,K_1,\dots.✦ The layer of the weighted Fourier flag at stage kk is Ek=Kk∩Kk−1⟂,k=0,…,n,E_k=K_k\cap K_{k-1}^{\perp},\qquad k=0,\dots,n,(3) and its layer projection Πk\Pi_k is the orthogonal projection of ℂΩ\mathbb{C}^{\Omega} onto EkE_k.

Matrices

The matrix of a linear operator TT on a finite-dimensional complex inner product space UU, in an orthonormal basis (bj)j∈J(b_j)_{j\in J} of UU, is the complex J×JJ\times J matrix with entries Tjl=⟨bj,Tbl⟩.T_{jl}=\langle b_j,Tb_l\rangle .(4)✦ On ℂΩ\mathbb{C}^{\Omega} the basis is the point basis of point masses, and an operator is identified with its Ω×Ω\Omega\times\Omega matrix in it; the weighted projection matrix Πk\Pi_k is the matrix of the layer projection Πk\Pi_k of the weighted Fourier flag.✦

For a real function hh on Ω\Omega, the multiplication matrix of hh is the diagonal Ω×Ω\Omega\times\Omega matrix with entry h(x)h(x) at (x,x)(x,x), the matrix of f↦hff\mapsto hf.✦ The coordinate matrix ZiZ_i is the multiplication matrix of the coordinate x↦xix\mapsto x_i: (Zi)xy={xi,x=y,0,x≠y.(Z_i)_{xy}=\begin{cases} x_i, & x=y,\\ 0, & x\ne y.\end{cases}(5)✦

A complex square matrix BB is block tridiagonal with respect to complex matrices A0,…,AnA_0,\dots,A_n of the same size when its blocks between indices more than one apart vanish: AsBAr=0for all r,s∈{0,…,n} with |r−s|>1.A_sBA_r=0\qquad\text{for all } r,s\in\{0,\dots,n\}\text{ with } |r-s|>1.(6)✦

The Claim

Theorem 1. Let ww be a positive weight on Ω\Omega and let i∈{1,…,n}i\in\{1,\dots,n\}. Then ZiZ_i is block tridiagonal with respect to the weighted projection matrices Π0,…,Πn\Pi_0,\dots,\Pi_n: ΠsZiΠr=0for all r,s∈{0,…,n} with |r−s|>1.\Pi_sZ_i\Pi_r=0\qquad\text{for all } r,s\in\{0,\dots,n\}\text{ with } |r-s|>1.(7)✦ More generally, let UU be a finite-dimensional inner product space, let F0⊆F1⊆⋯F_0\subseteq F_1\subseteq\cdots be an increasing sequence of subspaces of UU with layer projections P0,P1,…P_0,P_1,\dots, and let ZZ be a self-adjoint operator on UU that maps each FkF_k into Fk+1F_{k+1}. Then PsZPr=0for all r,s≥0 with |r−s|>1.P_sZP_r=0\qquad\text{for all } r,s\ge0\text{ with } |r-s|>1.(8)✦

What Is Checked

The claim is stated over a positive weight ww on the cube Ω\Omega, the coordinate matrix ZiZ_i and the matrices Πk\Pi_k, 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 DD, and more generally multiplication by a function aa on Ω\Omega that vanishes nowhere, is an invertible operator on ℂΩ\mathbb{C}^{\Omega}, the inverse being multiplication by 1/a1/a✦; and that taking matrices in an orthonormal basis is an isomorphism of complex algebras from the linear operators on UU onto the complex square matrices indexed by the basis.✦