Path 2 — Selection · Lesson 9 of 11

Why GF(7): The Minimal Prime Theorem

The alphabet size is not a free parameter — it is forced. Every prime smaller than 7 fails an explicit test. 7 is the unique minimal prime where chirality and color are both derivable at zero extra cost.

Two Questions, Answered in Sequence

The full MDL selection breaks into two questions:

Question 1
Which alphabet family?

Which prime p gives the smallest field GF(p) where all necessary symmetry groups are algebraically derivable?

Question 2
Which rule within that family?

Among all GF(p) rules consistent with the orbit data, which one does the interpolation select?

L08 answered Question 2 — the orbit interpolation picks p = C+R−CR−LCR. This lesson answers Question 1: why p = 7.

The Derivability Criterion

MDL selects the shortest description. So the right question is: which field allows the necessary physical symmetry groups to be described for free, without extra axioms?

What "derivable" means

A cyclic group ℤ_M is algebraically derivable from the field GF(p) if ℤ_M is isomorphic to a subgroup of the multiplicative group GF(p)* — the set of nonzero field elements under multiplication.

Why this matters for MDL cost

When ℤ_M is derivable from GF(p), color rotations by M steps are already implemented by multiplication by existing field elements. No new axioms needed — zero extra bits.

When ℤ_M is not derivable, the theory must specify a separate multiplication table for the color group. That costs at least ⌈log₂ M⌉ extra bits per generation.

By Lagrange's theorem, GF(p)* has order p−1. For ℤ_M to be derivable, M must divide p−1.

Which groups must be derivable?

The Standard Model requires two non-trivial symmetry groups to emerge:

ℤ₂ — chirality / weak-isospin parity
ℤ₃ — QCD color charge

For both to be derivable at zero cost, we need both 2 | (p−1) and 3 | (p−1), i.e. 6 | (p−1). The smallest prime p satisfying this is p = 7, since 7−1 = 6.

Prime-by-Prime Elimination

There are only four primes to check below 7. Each fails explicitly:

Prime p
GF(p)* ≅
2 | p−1?
3 | p−1?
Verdict
2
ℤ₁ (trivial)
No
No
Fails both
3
ℤ₂
Yes
No
Fails ℤ₃
5
ℤ₄
Yes
No
Fails ℤ₃
7
ℤ₆ ≅ ℤ₂×ℤ₃
Yes
Yes
Passes both ✓

The key insight about GF(5): 5−1 = 4. Since 3 does not divide 4, there is no 3-element subgroup in GF(5)*. Color charge cannot be derived from GF(5) — it must be specified as an additional axiom.

GF(7)*: since 7−1 = 6 = 2×3, the multiplicative group ℤ₆ automatically contains both ℤ₂ and ℤ₃ as subgroups. Both symmetries come for free.

The Internal Structure of GF(7)*

The six nonzero elements of GF(7) are {1, 2, 3, 4, 5, 6}. Under multiplication mod 7, they form a cyclic group of order 6 with this subgroup structure:

ℤ₁
{1}
Identity
ℤ₂
{1, 6}
Chirality / weak parity
ℤ₃
{1, 2, 4}
QCD color charge
ℤ₆
{1,2,3,4,5,6}
Full mult. group

You can verify the subgroup structure by direct multiplication mod 7:

The elements {1, 6} form the ℤ₂ subgroup under multiplication mod 7:

ℤ₂ = {1, 6} — chirality group

1 × 1 = 1  (mod 7) → stays in {1, 6}
1 × 6 = 6  (mod 7) → stays in {1, 6}
6 × 6 = 36 = 1 (mod 7) → stays in {1, 6}

Note: 6 ≡ −1 (mod 7). So {1, −1} is the chirality pair.

0
1
2
3
4
5
6

Yellow = ℤ₂ subgroup elements in GF(7)

The elements {1, 2, 4} form the ℤ₃ subgroup under multiplication mod 7:

ℤ₃ = {1, 2, 4} — color group

2¹ = 2  (mod 7)
2² = 4  (mod 7)
2³ = 8 = 1 (mod 7) → cycle closes

The generator is 2. Cycle: 1 → 2 → 4 → 1 (period 3).

0
1
2
3
4
5
6

Blue = ℤ₃ subgroup elements in GF(7)

GF(7)* is cyclic with generator 3 (verify: 3¹=3, 3²=2, 3³=6, 3⁴=4, 3⁵=5, 3⁶=1):

0
1
2
3
4
5
6

Violet = both subgroups (element 1) · Blue = ℤ₃ only · Yellow = ℤ₂ only · Gray = generator elements

No other prime below 13 (the next prime with 6 | p−1) has this structure. GF(7) is the unique minimal solution.

The MDL Cost Comparison

Here is what happens to the description length if you try to use GF(5) instead of GF(7):

GF(5) — color not derivable

GF(5)* ≅ ℤ₄. There is no 3-element subgroup. To get color symmetry ℤ₃, you must specify it as an additional external structure — with its own multiplication table of 9 entries (a 3×3 table, each entry from {0,1,2}):

GF(5)
field + ⌈log₂3⌉ extra bits per gen

GF(7) — both derivable

GF(7)* ≅ ℤ₆. Both ℤ₂ and ℤ₃ are subgroups. No external specification needed:

GF(7)
field only — zero extra
The MDL Uniqueness Theorem

GF(7) is the unique smallest field where both ℤ₂ (chirality) and ℤ₃ (color) are algebraically derivable as subgroups of the multiplicative group. Any field with a smaller prime incurs a strictly positive MDL penalty for color. Machine-certified:

 

Why Not a Larger Prime?

GF(13) also satisfies 6 | (13−1) = 12 — so ℤ₂ and ℤ₃ are both derivable there too. Why doesn't MDL choose GF(13)?

The answer is raw description cost. The alphabet size contributes directly to the description length:

The orbit classification (3 lepton generations, not 12 or 18) is also unique to GF(7): the PSC filter on GF(7) yields exactly 3 non-vacuum orbit types. Larger primes produce different orbit structures that do not match the three-generation pattern without additional tuning — which again costs extra bits.

The exhaustive machine check

The MDL Uniqueness Theorem is proved by exhaustive machine-verification over all 3125 = 5⁵ Z₅×Z₃ neighborhood states, confirming that Z₇×Z₃ beats Z₅×Z₃ in total description cost. No Lean-formalized competitor produces a shorter description.

What GF(7) Certifies That Rule 110 Alone Cannot

Rule 110 is the binary restriction of the GTE polynomial — what you get when you plug in only 0s and 1s. It certifies one important thing: Turing universality. The substrate can compute anything. But Turing universality covers only 8 of the 19 bits. The remaining 11 bits — the GF(7) field structure — are needed to certify five things that a binary (2-state) system cannot even express.

Why 19 bits and not 8?

A binary CA rule is fully specified by 8 bits — its truth table on {0,1}³ inputs. Rule 110 taken alone costs only 8 bits. But Rule 110 alone certifies only Turing universality. It cannot certify particle generations, charge quantization, color charge, chirality, or baryon number. Here is what each extra layer adds:

  1. Generation arithmetic. The GTE orbit {73, 42, 275} lives in GF(7): you need 7 states to track the winding numbers across the three generations. A binary system has no way to represent the three distinct orbit types — it collapses them all to a single class.
  2. Fractional electric charge. Charges like 1/3 and 2/3 arise from ℤ₇ winding ratios in the multiplicative group GF(7)*. A binary field produces only charges mod 2 — no fractional values.
  3. Color charge (ℤ₃). The strong force's SU(3) color symmetry comes from the Sylow-3 subgroup of GF(7)* ≅ ℤ₆. There is no ℤ₃ subgroup in any binary field — GF(2)* is trivial.
  4. Chirality (V−A). The left-handed asymmetry of the weak interaction is a GF(7) orbit property: the chiral ℤ₂ subgroup {1, 6} ⊂ GF(7)* distinguishes forward from mirror orbits. Binary systems are symmetric under all reflections.
  5. Baryon number. Baryon number is conserved because of a ℤ₇ winding conservation law on the GTE orbit. It is not definable in a 2-state field, which has no non-trivial winding structure.

Rule 110 is the binary shadow of the polynomial — what you see when you restrict to {0,1} inputs. The polynomial is primary; Rule 110 is the shadow it casts on the 8-corner subspace of the full {0,…,6}³ input domain.

This is the key upgrade GF(7) provides over any binary substrate: a 2-state system can be computationally universal, but computational universality alone does not explain why the universe has three generations, quarks with color, or left-handed neutrinos. Those structures require the algebraic richness of a 7-state field. The GTE polynomial is the unique compact specification that packages all of it in 19 bits.

Key Takeaways

See Also

Lean 4 proofs (ugp-lean)
Source papers
Full tutorial (PDF)