OctoInformBeta

OpenAI preprint, September 2026 · §3. Weighted Fourier grading

Characters and the degree spaces Vₖ: VkV_k as functions on Ω\Omega and in ℂΩ\mathbb{C}^\Omega with the counting inner product, and b¯a∈Vr+s\overline{b}a\in V_{r+s} for a∈Vra\in V_r, b∈Vsb\in V_s

Orthogonal characters and the degree spaces they span.

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

The Boolean cube Ω\Omega of dimension nn is the set {−1,1}n\{-1,1\}^n of the points xx that assign a sign to each index ii between 11 and nn✦, and the coordinate xix_i of such a point is its ii-th sign, the real number 11 or −1-1.✦

Fourier analysis on the cube expands a complex function on Ω\Omega in products of coordinates, one product for each set of indices, and the degree of the function is the largest number of coordinates in a product its expansion uses.

The Claim

Definition 1. For a subset SS of {1,…,n}\{1,\dots,n\}, the character χS\chi_S of SS is the complex function on Ω\Omega given by χS(x)=∏i∈Sxi.\chi_S(x)=\prod_{i\in S}x_i.(1)✦ For an integer k≥0k\ge0, the degree space VkV_k is the subspace of the complex functions on Ω\Omega spanned over ℂ\mathbb{C} by the characters of the sets of at most kk indices: Vk=span⁡{χS:|S|≤k}.V_k=\operatorname{span}\{\chi_S : |S|\le k\}.(2)✦ The space ℂΩ\mathbb{C}^\Omega of complex functions on Ω\Omega is a Hilbert space under the counting inner product, and VkV_k is a subspace of it: ⟨u,v⟩=∑x∈Ωu(x)¯v(x),Vk⊆ℂΩ.\langle u,v\rangle=\sum_{x\in\Omega}\overline{u(x)}\,v(x),\qquad V_k\subseteq\mathbb{C}^\Omega.(3)✦

Theorem 1. For subsets SS and TT of {1,…,n}\{1,\dots,n\}, ∑x∈ΩχS(x)¯χT(x)={2nif S=T,0if S≠T.\sum_{x\in\Omega}\overline{\chi_S(x)}\,\chi_T(x)= \begin{cases}2^n & \text{if } S=T,\\ 0 & \text{if } S\neq T.\end{cases}(4)✦ For integers r,s≥0r,s\ge0, if aa is a function in VrV_r and bb is a function in VsV_s, then the function b¯a\overline{b}a, with value b(x)¯a(x)\overline{b(x)}\,a(x) at xx, satisfies b¯a∈Vr+s.\overline{b}\,a\in V_{r+s}.(5)✦

What Is Checked

The relations (4) and (5) and the space (3) are stated over the cube Ω\Omega with its real coordinates xi=±1x_i=\pm1, the characters χS\chi_S of (1) as complex functions on Ω\Omega, and the degree spaces VkV_k of (2) as spans of characters inside the complex functions on Ω\Omega.