Research shelf / Mathematics / Boolean n = 3…8
Written Updated
Where Boolean functions stop being decomposable
A Boolean function of n variables lives in a space of 2^(2ⁿ) elements — 256 functions at n = 3, and about 1.16 × 10^77 at n = 8. The question this paper asks is what fraction of them genuinely need all n variables, and the answer rises so fast that by n = 8 essentially every function is irreducible.
Experiments were run and the numbers are reported here.
A dimension-by-dimension census of Boolean function space from three to eight variables, tracking the fraction of genuinely irreducible functions from roughly a quarter to a virtual ceiling.
The paper catalogues, dimension by dimension, exact counts of the linear, balanced, self-dual and threshold function families, and estimates the fraction of genuinely n-dimensional functions at each level. Counts are exact by verified enumeration up to n = 4 and statistically sampled above it — a distinction the paper keeps visible rather than blurring.
The headline structural finding is dimensional emergence: irreducibility rises from about 25% at n = 3 to a virtual ceiling of 99.9% at n = 8. Complexity does not accumulate gradually; it arrives, and past a certain width almost nothing decomposes into lower-dimensional pieces.
Four applied families are then characterised and mapped to three domains: majority threshold functions and Byzantine voting kernels to n-modular redundancy in safety-critical systems; bent (maximally nonlinear) functions to cryptographic primitive design and S-box construction; and parity functions to quantum error correction, with the 7-qubit Steane code as the worked case.
Every number, and what stands behind it
A claim is only worth the evidence attached to it. Each row below carries its basis: measured on the author’s own hardware, derived from the construction, measured on synthetic data, projected from literature, or simply cited.
| Claim | Figure | Basis | Context |
|---|---|---|---|
| Function space size | 2^(2ⁿ) | Derived | 256 at n = 3; ≈1.16 × 10⁷⁷ at n = 8 |
| Irreducible fraction at n = 3 | ≈25% | Derived | Verified enumeration |
| Irreducible fraction at n = 8 | ≈99.9% | Synthetic | Statistical sampling, not exhaustive |
| Exact enumeration range | n ≤ 4 | Derived | Above this the paper samples and says so |
| Families catalogued | linear, balanced, self-dual, threshold | Derived | Exact counts where enumeration is feasible |
| Quantum mapping | 7-qubit Steane code | Cited | Parity-function family, worked example |
| Scaling table | n = 2 to n = 8 | Derived | Provided for engineering use |
Measured — author-run experiment on the stated setup. Synthetic — measured, but on synthetic rather than real data. Derived — follows from the stated construction or proof. Projected — paper-stated projection, not an author-run benchmark. Cited — taken from external literature.
How it works
- Exhaustive enumeration to n = 4. All 65,536 functions at n = 4 classified directly — no sampling error in that range.
- Statistical sampling for n ≥ 5. Above n = 4 exhaustive enumeration is infeasible, so the irreducibility fractions are estimates with sampling uncertainty.
- Family classification. Linear, balanced, self-dual, threshold and bent families characterised separately.
- Application mapping. Each family tied to a concrete engineering domain: cryptography, quantum error correction, n-modular redundancy.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- The 99.9% figure at n = 8 is sampled, not enumerated. 2^256 functions cannot be counted.
- Bent functions exist only for even n; the framing of the family across all dimensions glosses that.
- The application mappings are structural correspondences, not designs. No S-box is constructed and no code is implemented.
- Threshold-function counts are known to be hard beyond small n; the paper’s figures inherit that difficulty.
- No code, no reference implementation.
Free under AGPL-3.0+ for almost everyone
Personal use, charities, education and organisations under AUD 50,000 a year pay nothing. A tiered commercial licence covers everyone else.