The Theorem of Connectivity
Affine equivalence groups functions that share the same cryptographic properties, but it says nothing about how those classes sit relative to one another. The theorem of connectivity supplies exactly that missing structure: it describes how a function relates to its immediate neighbours — the functions one bit-flip away in the truth table — and shows that this local structure is itself an invariant of the equivalence class. The result lets us view the whole Boolean space not as a flat collection of $2^{2^{n}}$ functions but as a set of connected equivalence classes — the cosets of $\mathrm{RM}(1,n)$ under the affine group.
The 1-local neighbourhood
The starting point is the immediate neighbourhood of a function: everything at Hamming distance one from it.
Definition. The 1-local neighbourhood of a Boolean function $f \in \mathcal{B}_n$ consists of all $2^n$ functions $f_{(i)}$, $i \in \mathbf{Z}_2^{\,n}$, with $\operatorname{dist}(f, f_{(i)}) = 1$. We say $f_{(i)}$ is connected to $f$: $$f_{(i)}(x) = \begin{cases} f(x) & x \neq i \\ f(x) \oplus 1 & x = i. \end{cases}$$
The theorem
The key result is that an affine transform maps neighbours to neighbours: if $f$ and $g$ are affine equivalent under some transform, then every neighbour of $f$ corresponds — under that same transform — to a neighbour of $g$.
Theorem (Connectivity). Let $f_{(i)}$ be defined as above. Then for $g(x) = f(\mathcal{D}x \oplus a) \oplus b \cdot x \oplus c$ there exists a connecting function $g_{(j)}$ such that $$g_{(j)}(x) = f_{(i)}(\mathcal{D}x \oplus a) \oplus b \cdot x \oplus c, \qquad j = \mathcal{D}^{-1}(i \oplus a), \qquad i = \mathcal{D}j \oplus a.$$
Because $\mathcal{D}$ is non-singular this correspondence is a bijection, which gives the property that makes connectivity useful:
Corollary. The 1-local neighbourhood of $g$ is a permutation of the 1-local neighbourhood of $f$. Repeating the argument extends this to any distance $m$: the $m$-local neighbourhood of $g$ is a permutation of that of $f$.
Connectivity between classes
Since neighbours are preserved, we can summarise a class by which classes it connects to, and how often. Every function in a class has the same connection profile. For $n = 3$, for instance, every single-bit change to a class-1 function yields a class-2 function; a class-2 function has one change leading back to class 1 and seven leading to class 3.
Equivalence class connectivity, $n = 3$
| class | connecting class (frequency) distribution |
|---|---|
| 1 | C2(8) |
| 2 | C1(1), C3(7) |
| 3 | C2(8) |
Equivalence class connectivity, $n = 4$
| class | connecting class (frequency) distribution |
|---|---|
| 1 | C2(16) |
| 2 | C1(1), C3(15) |
| 3 | C2(2), C4(14) |
| 4 | C3(3), C5(1), C6(12) |
| 5 | C4(16) |
| 6 | C4(8), C7(8) |
| 7 | C6(15), C8(1) |
| 8 | C7(16) |
The $n = 5$ connectivity profile follows the same form across its 48 classes (see the equivalence class tables for the classes themselves).
Class connection diagrams
Drawing one node per class and one branch per connection turns the space into a tree. Arranged by nonlinearity, the affine class sits at the root and the maximally nonlinear classes — including the bent classes for even $n$ — form the topmost leaves. The branches are sparse near the top (high-nonlinearity classes have few connections) and grow thicker toward the root, revealing the inherent shape of the Boolean space.
For $\mathcal{B}_3$ the tree is a simple chain; for $\mathcal{B}_4$ it begins to branch, with class 5 forming a leaf at nonlinearity 4 and the bent class 8 at the very top. The diagram for the 48 classes of $\mathcal{B}_5$ is far richer but follows the same principle; only a partial, high-nonlinearity component is feasible for $\mathcal{B}_6$.
Why it matters
The connection profile is an affine invariant, so it is a powerful tool for telling classes apart and for navigating the space:
- A non-exhaustive equivalence test. Two functions can be shown inequivalent by comparing their connecting-class distributions — the first distinguishing technique for Boolean functions of six or more inputs that does not require an exhaustive search for an affine transform. For $n = 6$, comparing distributions out to a distance of four gives complete class distinction.
- Enumerating the classes. Starting from the constant-zero function and repeatedly examining connecting functions for new classes is guaranteed (by the theorem) to find them all. Run for $n = 6$, this independently verified the existence of exactly 150,357 equivalence classes and confirmed the set is complete.
- A map of the space. The connections form a tree-like diagram of how the classes relate — a visual representation of the structure of $\mathcal{B}_3$, $\mathcal{B}_4$ and $\mathcal{B}_5$, and a partial map of $\mathcal{B}_6$.
The theorem of connectivity was the foundation of the PhD research from which this site grew — the result that turns the unmanageable Boolean space into a navigable structure.