nucleation

LIT-346: Analysis of Boolean Functions

1 min read

Properties6
StatusActive — read in part 2026-09-29 (NOTE-291); worth reading as the standard, freely available text on Fourier analysis of functions on the Boolean cube. Chapters 1–2 alone give the character basis, Plancherel and Parseval, convolution, and the level-by-level diagonalisation of the noise operator and Laplacian. Read it as abelian harmonic analysis only: it has no nonabelian representation theory, no irreps of dimension > 1 and no isotypic decomposition.
Version2
Tagsmathematics, learning-theory, information-theory
SupportsCLAIM-385 — If a symmetric operator on ℝⁿ commutes with an orthogonal representation of a compact group, each eigenspace is a sum of real irreducibles and each multiplicity a sum of multiples of their dimensions, so SO(2) and ℤ/n for n ≥ 3 force paired eigenvalues; conversely the spectrum fixes neither the group nor a basis inside an eigenspace
Cited as “paper” byNOTE-291 — Analysis of Boolean Functions
Cited as “source” byTHEORY-019 — Symmetry forces spectral degeneracy but degeneracy does not identify a symmetry: an operator commuting with a group has eigenspaces built from its real irreducibles, so abelian rotation groups force pairs over ℝ, and the spectrum fixes neither the group nor a basis inside a multiplet, THEORY-022 — The reverse-engineered grokking network computes modular addition by multiplying characters of ℤ/p at a few frequencies, the same real two-dimensional irreducibles later found as circles in language models; in both the group comes from the task, not the network

Graph View

Ryan O’Donnell (2014), Cambridge University Press (book); arXiv version 2021 — DOI-10.1017/CBO9781139814782

Standing in the record

Registered on 2026-09-29 at the owner’s request, because the owner’s prior-art novelty map (a private working document on concepts as projectors, the linear representation hypothesis and their neighbours) cites it: row 7 must-cite: Boolean-Fourier/character machinery for predicate harmonics. It is seeded from metadata and published descriptions and has not been read here.

It was filed Deferred, unread. NOTE-291 is the close reading of 2026-09-29, and it placed the work: Active — worth reading as the standard, freely available text on Fourier analysis of functions on the Boolean cube. Chapters 1–2 alone give the character basis, Plancherel and Parseval, convolution, and the level-by-level diagonalisation of the noise operator and Laplacian. Read it as abelian harmonic analysis only: it has no nonabelian representation theory, no irreps of dimension > 1 and no isotypic decomposition.

Backlinks