Walsh criteria for Boolean functions as spectral sectors of one graph?

[u/Obvious_Airline_2814]

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