Research shelf / Mathematics / GF(2) Algebra
Written Updated
GF(2) algebra — seven papers on the smallest interesting field
GF(2) has 16 binary operations. Enumerate them all and something falls out: AND is the only nontrivial operation that forms a ring with XOR. The series runs from that result through permutation polynomials, bifurcation dynamics, circuit minimisation and what a neural network chooses when you let it learn logic gates.
Experiments were run and the numbers are reported here.
From an exhaustive enumeration of all 16 binary operations to permutation polynomials, circuit optimisation and differentiable logic gates — including a uniqueness theorem for AND.
A seven-paper series on the binary finite field GF(2). Paper 1 establishes the GF(2) Ring Uniqueness Theorem by exhaustive enumeration: AND is the only nontrivial operation that forms a ring with XOR.
The cryptographic thread identifies the AES inverse x⁻¹ = x²⁵⁴ as one of 128 permutation polynomials on GF(2⁸), verified through the Monomial Permutation Criterion: xᵏ permutes GF(2ⁿ) if and only if gcd(k, 2ⁿ − 1) = 1.
The applied thread reports gate-count reductions — Rule 110 from 19 gates to 6, a 68% cut; full-adder sum down 78%; XOR down 80% — and a differentiable logic gate network that favoured AND in 10 of 96 slots and NOR in 11 of 96, against a uniform expectation of 6.
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 |
|---|---|---|---|
| GF(2) Ring Uniqueness Theorem | AND is the only nontrivial ring partner for XOR | Derived | Exhaustive enumeration, computer verified |
| AES inverse classification | x²⁵⁴ is 1 of 128 permutation polynomials on GF(2⁸) | Derived | Monomial Permutation Criterion |
| Monomial Permutation Criterion | xᵏ permutes GF(2ⁿ) iff gcd(k, 2ⁿ−1) = 1 | Derived | Stated and verified |
| Rule 110 gate reduction | 19 → 6 gates (68%) | Measured | Circuit optimisation |
| Full-adder sum reduction | 78% | Measured | Circuit optimisation |
| XOR reduction | 80% | Measured | Circuit optimisation |
| Learned gate preference | AND 10/96, NOR 11/96 vs uniform 6/96 | Measured | 2,000 steps, 6 random seeds |
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. All 16 binary operations, with computer verification.
- Algebraic normal form. ANF / Zhegalkin conversion throughout.
- Numerical Jacobian analysis. For contraction bounds and bifurcation mapping.
- Differentiable logic gate network. 2,000 training steps across 6 random seeds.
What it does not do
Taken from the folder’s own README. Nothing here has been softened.
- The empirical work is small-network and synthetic, not industrial scale.
- No third-party formal-methods verification of the enumeration results.
- Paper 7's ECE relationship is a framework or heuristic, not a proven law.
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.