I noticed a possible connection between the standard Walsh conditions for Boolean functions and the spectrum of one finite graph.
In Boolean-function cryptography, balancedness, correlation immunity, and resilience are usually checked through the vanishing of low-weight Walsh coefficients. So the construction below is about the low-weight Walsh layers.
I tried to package this structure into one graph:
G_block^(n) = O_n ∪ Q_n ∪ B
where `Q_n` is the Boolean cube, `O_n` is the cross-polytope graph, and `B` connects them by coordinate incidence.
If the vertices of `O_n` are written as poles `±e_i`, and the vertices of `Q_n` as `σ ∈ {±1}^n`, then the incidence rule is:
(i,s) ~ σ iff σ_i = s
The main lemma is:
B χ_u = 0 iff wt(u) ≥ 2
So the incidence matrix only sees Walsh weights `0` and `1`. All weights `≥ 2` stay as separate spectral sectors. Weight `1` is the layer that couples to the cross-polytope axes.
After embedding a Boolean function into the cube side of the graph, balancedness, correlation immunity, and resilience can be read as vanishing of projections onto the corresponding low-weight spectral sectors.
I am not claiming a new Walsh transform or a new cryptographic criterion. I want to understand whether this reading is correct at all: ordinary low-weight Walsh conditions as spectral sectors of this enlarged graph.
Weights `≥ 2` seem to remain clean Walsh sectors, while weight `1` becomes the part coupled to the cross-polytope axes.
Is this interpretation right? Or is the combination of the Walsh decomposition on the cube and the spectrum of the enlarged graph not valid?
This came out of a larger finite-carrier theory project, but the note itself should be self-contained. The only idea used from the project is to represent a finite structure as an explicit graph carrier.
I would appreciate it if someone could check the idea and implementation: whether the graph, Laplacian, spectral decomposition, and translation of the standard Walsh criteria into spectral projections are done correctly. I am especially interested in possible issues for `n = 3,4`, where eigenvalue collisions occur.
GitHub note and verification script: [https://github.com/Nondual-Observer/DOTheory/blob/main/02\_Bridges/05\_Cryptographic\_Spectral\_Block/DOT\_Cryptographic\_Spectral\_Block.md](https://github.com/Nondual-Observer/DOTheory/blob/main/02_Bridges/05_Cryptographic_Spectral_Block/DOT_Cryptographic_Spectral_Block.md)
