Class Graph Explorer
Every Boolean function belongs to an affine equivalence class, and changing a single bit of its truth table moves it to a neighbouring class. By the Theorem of Connectivity, every function in a class has the same neighbours, in the same proportions, so the classes form a graph. Here it is for $n = 3$, $4$ and $5$, layered by nonlinearity from the affine class at the bottom to the most nonlinear classes at the top.
Reading the graph
- Height is nonlinearity; circle size is the number of functions in the class (log scale), from the self-mapping constant. Almost all functions live in a few large classes near the top-middle.
- Lines join classes that are one bit apart. The panel lists, for the selected class, where each of the $2^n$ possible single-bit changes leads. ▲ means up in nonlinearity.
- Hill climb starts from a random function and repeatedly makes the single-bit change that most increases nonlinearity, the simplest version of the heuristic searches used to find cryptographically strong functions. Run it a few times on $n = 5$: some climbs reach the top, others stall at a local maximum.
The graphs are computed exactly from the class representatives on the class tables: for $n \le 5$ the absolute Walsh and autocorrelation distributions together identify a class uniquely. They reproduce Figures 4.1–4.3 of the PhD thesis (2003), with the layout re-ordered to reduce crossings.