Research · Papers · Symmetry, state encodings and search gauges · MF-092
Exact nonlinear cost of an eight-state controller under affine relabeling
Affine maps over F₂ preserve XOR–AND count/depth: 40,320 3-bit encodings form 30 orbits with exact minimum ANDs: 1×2, 4×3, 15×4, 10×5
Published 2026-08-29
For everyone
Plain summary
An eight-state controller tracks eight internal conditions, assigning a three-bit binary label to each state. Relabeling states with reversible XOR combinations and fixed bit offsets preserves both the total AND-gate count and the longest chain of dependent AND gates. Because AND-based costs do not change under these relabelings, circuits map directly from one labeling to another without recomputing nonlinear cost. Across all 8! = 40,320 possible labelings, the states partition into 30 equivalence groups. Exact synthesis shows their minimum costs span 2, 3, 4, or 5 AND gates, meaning state assignment shifts the AND-gate footprint by a factor of 2.5. This equivalence applies strictly to AND metrics; it does not preserve XOR counts, physical chip area, or switching activity.
Result
Let an FSM state encoding be transformed by an invertible affine map over F₂. Every jointly synthesised XOR–AND implementation transports under that map with identical AND count and multiplicative depth.
For the fully specified eight-state controller, the 8! = 40,320 three-bit assignments form 30 affine orbits with the following exact minima:
| exact minimum | affine orbits | encodings |
|---|---|---|
| 2 ANDs | 1 | 1,344 |
| 3 ANDs | 4 | 5,376 |
| 4 ANDs | 15 | 20,160 |
| 5 ANDs | 10 | 13,440 |
State assignment shifts the exact nonlinear cost by a factor of 2.5, while affine quotienting reduces the exact synthesis search space from 40,320 encodings to 30 orbit representatives.
Setting and definitions
The controller is a fully specified finite-state machine with eight states, indexed by three-bit words. An invertible affine map over F₂ consists of a nonsingular linear XOR transformation plus a constant binary offset vector. An affine orbit is the equivalence class of state encodings related by these maps. Joint synthesis optimizes the state encoding and XOR–AND logic network simultaneously. Nonlinear cost denotes the total AND gate count. Multiplicative depth denotes the maximum number of cascaded AND gates along any path through the network.
Method
Census records, verification outputs, and computational artifacts are available in this paper's downloadable evidence pack.
The pipeline enumerated all 40,320 three-bit state assignments, partitioned them into 30 affine orbits, and computed the exact AND-count minimum for each orbit. Two independent synthesis executions and two separate verification paths produced identical distributions. Every synthesized circuit was verified by full truth-table replay across all input rows.
Discussion
Affine quotienting collapses 40,320 state encodings down to 30 orbit representatives without loss of AND count or multiplicative depth optimality. A single exact synthesis run per orbit representative characterizes every encoding in that orbit.
This invariance is strictly nonlinear. Affine recoding does not preserve XOR gate counts, PLA terms or literals, LUT area, standard-cell area, or switching activity; physical area and side-channel metrics still vary within an orbit and require downstream evaluation. The census characterizes this specific eight-state controller and does not provide universal cost bounds for incompletely specified FSMs. MF-008 documents the carry-state instance at minimum rank.
The register notes no external prior-art position; the result stands on the proved structure theorem, exact census, and verified execution logs.
For everyone — the takeaway
What this means
How you assign binary labels to machine states changes how many AND gates the circuit needs. Reversible label shifts built from XOR gates leave both the AND count and the longest dependent AND chain unchanged. When designing a circuit for low AND-gate cost, you don't need to test all 40,320 possible three-bit labelings; testing one representative from each of the 30 groups covers them all. For this eight-state controller, the best labelings need only 2 AND gates while the worst require 5. However, this symmetry doesn't extend to XOR count, chip size, lookup tables, or power draw—those physical metrics still differ inside each group and need separate checks.
Register references
Entry: MF-092.
Receipt artifacts: 05-orbit-state-encoding/REPORT.md; ascon_orbit_screen.py; ascon_orbit_screen_results.json; sop_proxy_census.py; sop_proxy_results.json; agent-fsm/.
Prior art: the register does not record this.
Every artifact named above is bundled in, or hashed by, this paper's evidence pack below.
Evidence pack
Everything needed to check this entry against its receipts: the register text, a manifest with a SHA-256 hash for every named receipt, and 5 of 5 receipt files bundled (42 KB). Anything not bundled is still hashed in the manifest and lives in the compute-box working trees.
Changelog
Last reviewed 2026-08-29
- 2026-08-29Published on this site.