Configurations, contracts, Kempe semantics, and a complete reducibility checker
DefinitionFourColor_ConfigurationA finite patch carries a hypermap, an ordered ring and selected contract darts. The bundle defines all semantics below and proves soundness and completeness of a finite trace-addition checker. It does not prove reducibility of the fixed catalogue. Formalization note: source-derived Lean-native finite semantics and proved checker bridges.
Notation: is the dart set, its size, and is the node permutation. Write for the edge and face permutations, with . Edge, node and face counts are numbers of permutation orbits, including singleton orbits. The component count uses the equivalence generated by all three permutations. Planarity means the exact Euler equality , and connectedness means .
A plain hypermap has a fixed-point-free involution . Cubic means every node orbit has size three; precubic means every node orbit has size at most three. Bridgeless means and never lie in the same face orbit. A -coloring is a map constant on face orbits and different across each edge step. No requirement uses all available colors. The empty dart set has zero components, is planar, and is colorable, but is not connected.
An admissible hypermap is planar, bridgeless, plain and precubic. A minimal counterexample is a non-four-colorable admissible hypermap such that every admissible hypermap with fewer darts is four-colorable. Minimality includes all finite carriers through their enumeration by ; cubicity, connectedness and lower face-degree bounds are not assumed.
The fixed catalogue is the ordered list of all 633 literal configuration maps, boundary rings, and selected contracts, decoded from the pinned source. It is shared by reducibility and coverage; it is not an arbitrary or existentially chosen family. The table checker establishes array sizes, index bounds, and inverse/triangle identities only.
For a configuration , let be its ordered boundary ring, the darts whose faces avoid that ring, and the list containing both darts of every selected contract edge. Geometric admissibility means that the map is planar, bridgeless, plain and connected; is a nonempty node cycle meeting each face at most once; off-ring nodes have arity three; ring faces have arity 3–6; and there is a kernel face having a common adjacent kernel face with every kernel face. Contract validity means that avoids , its darts lie in pairwise distinct node orbits, the contract has 1–4 edges, and a four-edge contract has the source's kernel triad (more than two incident selected-face darts and not every selected face adjacent).
Colors are the Klein-four group , with bitwise XOR as addition. A boundary trace records sums of consecutive face colors around the reversed ring, including the closing pair. Ordinary traces arise from proper face colorings. Contract traces arise from face-constant colorings with equal colors across exactly the edges selected by . A trace set is Kempe-closed if it is closed under all permutations fixing zero and, for each member, contains every trace matching some compatible four-symbol noncrossing-chord word. The stack matcher rejects zero colors and requires an empty final stack. Coclosure of a set consists of traces whose every containing Kempe-closed set meets that set. C-reducibility means contract validity and inclusion of all contract traces in the coclosure of the ordinary traces.
An occurrence of in requires geometric admissibility of and a map of its darts into preserving face steps and exact face arities on . Every kernel face must contain an edge-preserving dart; such darts obey the explicit ring-link path condition in the definition. A total injective map of all permutations is not required. Occurrence up to reflection means occurrence in or in its mirror, whose edge, node and face maps are respectively , and .
The concrete transfer counts, with multiplicity, matches of the 71 symmetrized source patterns at . Their 38 base entries include repeated entries implementing larger transfers. With the face orbit of and , the score is
All intervals are inclusive; a missing upper endpoint means no upper bound. Only the positive hub is eventually restricted to degrees 5–11. Neighboring faces are not silently restricted to those degrees.
Source: Georges Gonthier, A Computer-Checked Proof of the Four Colour Theorem (2005), https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/4colproof.pdf; Section 5.2, PDF p. 28, paragraph on PDF p. 28 on chromogram matching; PDF pp. 26–32, especially the unnumbered chromogram/coclosure paragraphs on pp. 28–30; Section 5.4, PDF pp. 38–44, embedding and contract paragraphs. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/coloring.v#L394-L474; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/chromogram.v#L88-L112; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/coloring.v#L505-L524; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfreducible.v#L39-L66; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/embed.v#L1446-L1467.
import Definitions.Def_FourColor_Hypermap
import Mathlib.GroupTheory.Perm.Cycle.Factors
import Mathlib.Data.Fintype.Perm
import Mathlib.Data.Fintype.Pi
import Mathlib.Data.List.Chain
import Mathlib.Data.List.OfFn
import Mathlib.Data.Finset.Max
import Mathlib.Data.Finset.Powerset
/-!
Concrete configurations, boundary-color semantics, and a reference certificate checker.
Source: Gonthier (2005), Sections 5.2 and 5.4, PDF pp. 26–32 and 38–44; pinned
rocq-community/fourcolor `c1d6b1cd5288bea4b067aac13cdde3c18dffe018`, `coloring.v`
(embeddable, valid_contract, C_reducible, preembedding), `chromogram.v` (matchg,
Kempe_closed), and `cfreducible.v` (check_reducible_valid).
The concrete finite data contain no proof of reducibility or nonoccurrence. The checker
uses explicit finite enumeration and a list of traces to add to the Kempe coclosure.
It is a deliberately simple reference algorithm, not a claim of efficient computation on
all 633 configurations. Efficient implementations may refine it with proved correctness.
-/
namespace FourColor
instance {n : ℕ} (H : Hypermap n) (x y : Fin n) : Decidable (H.SameFace x y) :=
inferInstanceAs (Decidable (H.face.SameCycle x y))
/-- A finite configuration remainder map, its ordered outer node ring, and contract edges. -/
structure Configuration where
dartCount : ℕ
map : Hypermap dartCount
ring : List (Fin dartCount)
contract : List (Fin dartCount)
/-- Four colors, with the Klein-four operation used to form edge-color traces. -/
abbrev ConfigurationColor := Fin 4
def configurationColorAdd (a b : ConfigurationColor) : ConfigurationColor :=
⟨(Nat.xor a.val b.val) % 4, Nat.mod_lt _ (by decide)⟩
/-- A noncrossing chord word: a skipped edge, opening chord, or one of two closing parities. -/
inductive ChromogramSymbol
| skip | push | popSame | popOther
deriving DecidableEq, Repr
instance : Fintype ChromogramSymbol where
elems := {.skip, .push, .popSame, .popOther}
complete := by intro x; cases x <;> simp
/-- Gonthier's stack matcher. Color 0 never matches; color 1 skips a chord endpoint. -/
def matchChromogram : List Bool → List ConfigurationColor → List ChromogramSymbol → Bool
| [], [], [] => true
| stack, e :: es, symbol :: symbols =>
match e.val, symbol, stack with
| 1, .skip, _ => matchChromogram stack es symbols
| 2, .push, _ => matchChromogram (false :: stack) es symbols
| 3, .push, _ => matchChromogram (true :: stack) es symbols
| 2, .popSame, false :: rest => matchChromogram rest es symbols
| 3, .popSame, true :: rest => matchChromogram rest es symbols
| 2, .popOther, true :: rest => matchChromogram rest es symbols
| 3, .popOther, false :: rest => matchChromogram rest es symbols
| _, _, _ => false
| _, _, _ => false
namespace Configuration
variable (C : Configuration)
/-- Both darts of every selected contract edge, retaining multiplicities for sparsity checks. -/
def edgeCompletion : List (Fin C.dartCount) :=
C.contract.flatMap fun x ↦ [x, C.map.edge x]
/-- The kernel consists of faces disjoint from the outer ring. -/
def InKernel (x : Fin C.dartCount) : Prop :=
∀ r ∈ C.ring, ¬ C.map.SameFace x r
/-- Face adjacency, rather than dart equality. -/
def Adjacent (x y : Fin C.dartCount) : Prop :=
∃ z, C.map.SameFace x z ∧ C.map.SameFace (C.map.edge z) y
/-- A directed ring step crosses one edge and then stays within the new face. -/
def RLink (x y : Fin C.dartCount) : Prop := C.map.SameFace (C.map.edge x) y
/-- A nonempty ordered node cycle meeting each face at most once.
The catalogue always has a nonempty perimeter; this explicitly excludes the empty cycle. -/
def NodeRing : Prop :=
C.ring ≠ [] ∧ C.ring.Pairwise (fun x y ↦ ¬ C.map.SameFace x y) ∧
∀ p ∈ C.ring.zip (C.ring.rotate 1), C.map.node p.1 = p.2
/-- The source's exact-two-hop condition on the face kernel. -/
def KernelRadiusTwo : Prop :=
∃ x, C.InKernel x ∧ ∀ y, C.InKernel y →
∃ z, C.InKernel z ∧ C.Adjacent x z ∧ C.Adjacent y z
/-- Geometric configuration hypotheses, separate from reducibility and from occurrence. -/
def Embeddable : Prop :=
C.map.Planar ∧ C.map.Bridgeless ∧ C.map.Plain ∧ C.map.Connected ∧ C.NodeRing ∧
(∀ x, x ∉ C.ring → C.map.nodeArity x = 3) ∧
(∀ x ∈ C.ring, 3 ≤ C.map.faceArity x ∧ C.map.faceArity x ≤ 6) ∧ C.KernelRadiusTwo
/-- A triad has at least three incident selected faces and misses some selected face. -/
def Triad (x : Fin C.dartCount) : Prop :=
2 < (Finset.univ.filter fun y : Fin C.dartCount ↦
C.map.SameFace x y ∧ ∃ p ∈ C.edgeCompletion, C.map.SameFace (C.map.edge y) p).card ∧
¬ ∀ p ∈ C.edgeCompletion, C.Adjacent x p
/-- The nonempty contract has at most four edges; four require the source's triad condition. -/
def ValidContract : Prop :=
(∀ x ∈ C.ring, x ∉ C.edgeCompletion) ∧
C.edgeCompletion.Pairwise (fun x y ↦ ¬ C.map.node.SameCycle x y) ∧
1 ≤ C.contract.length ∧ C.contract.length ≤ 4 ∧
(C.contract.length = 4 → ∃ x, C.InKernel x ∧ C.Triad x)
/-- Contract coloring identifies exactly the selected edges and colors all others properly. -/
def ContractColoring (k : Fin C.dartCount → ConfigurationColor) : Prop :=
(∀ x y, C.map.SameFace x y → k x = k y) ∧
∀ x, (k (C.map.edge x) = k x ↔ x ∈ C.edgeCompletion)
/-- The finite type of edge traces on the perimeter. -/
abbrev BoundaryTrace := Fin C.ring.length → ConfigurationColor
/-- The finite type of chord words of the perimeter length. -/
abbrev Chromogram := Fin C.ring.length → ChromogramSymbol
/-- Colors of consecutive faces on the reversed ring differ by the Klein-four operation.
The reverse matches `C_reducible` in the source; the last coordinate closes the cycle. -/
def boundaryTrace (k : Fin C.dartCount → ConfigurationColor) : C.BoundaryTrace :=
fun i ↦
let j : Fin C.ring.length := ⟨(i.val + 1) % C.ring.length,
Nat.mod_lt _ (Nat.zero_lt_of_lt i.isLt)⟩
configurationColorAdd
(k (C.ring.reverse.get ⟨i.val, by simpa only [List.length_reverse] using i.isLt⟩))
(k (C.ring.reverse.get ⟨j.val, by simpa only [List.length_reverse] using j.isLt⟩))
/-- Realizable ordinary coloring traces. -/
def RingTrace (t : C.BoundaryTrace) : Prop :=
∃ k : Fin C.dartCount → ConfigurationColor, C.map.Coloring k ∧ C.boundaryTrace k = t
/-- Realizable contract-coloring traces. -/
def ContractRingTrace (t : C.BoundaryTrace) : Prop :=
∃ k : Fin C.dartCount → ConfigurationColor, C.ContractColoring k ∧ C.boundaryTrace k = t
/-- Every permutation of the three nonzero edge colors, fixing zero. -/
abbrev ColorSymmetry := {p : Equiv.Perm ConfigurationColor // p 0 = 0}
def permuteTrace (p : ColorSymmetry) (t : C.BoundaryTrace) : C.BoundaryTrace :=
fun i ↦ p.val (t i)
def Matches (t : C.BoundaryTrace) (w : C.Chromogram) : Prop :=
matchChromogram [] (List.ofFn t) (List.ofFn w) = true
/-- Kempe closure uses all color permutations and one matching chord word per trace. -/
def KempeClosed (P : C.BoundaryTrace → Prop) : Prop :=
∀ t, P t →
(∀ p : ColorSymmetry, P (C.permuteTrace p t)) ∧
∃ w : C.Chromogram, C.Matches t w ∧ ∀ u, C.Matches u w → P u
/-- A trace lies in the coclosure when every Kempe-closed set containing it meets `P`. -/
def KempeCoclosure (P : C.BoundaryTrace → Prop) (t : C.BoundaryTrace) : Prop :=
∀ Q, C.KempeClosed Q → Q t → ∃ u, P u ∧ Q u
/-- Semantic C-reducibility, without quantification over minimal counterexamples. -/
def CReducible : Prop :=
C.ValidContract ∧ ∀ t, C.ContractRingTrace t → C.KempeCoclosure C.RingTrace t
/-- Source preembedding on the kernel. Injectivity is a conclusion of later geometry. -/
def Preembedding {n : ℕ} (H : Hypermap n) (h : Fin C.dartCount → Fin n) : Prop :=
(∀ x, C.InKernel x → h (C.map.face x) = H.face (h x)) ∧
(∀ x, C.InKernel x → C.map.faceArity x = H.faceArity (h x)) ∧
(∀ x, C.InKernel x → ∃ y, C.map.SameFace x y ∧ h (C.map.edge y) = H.edge (h y)) ∧
∀ x y, C.InKernel x → h (C.map.edge x) = H.edge (h x) →
C.InKernel y → h (C.map.edge y) = H.edge (h y) →
∃ p : List (Fin C.dartCount),
List.IsChain C.RLink (C.map.node (C.map.face x) :: (p ++ [y])) ∧
∀ z ∈ p, C.InKernel z ∧ h (C.map.edge z) = H.edge (h z)
/-- Concrete occurrence: geometric admissibility and a partial combinatorial embedding. -/
def Occurs {n : ℕ} (H : Hypermap n) : Prop :=
C.Embeddable ∧ ∃ h : Fin C.dartCount → Fin n, C.Preembedding H h
instance (x : Fin C.dartCount) : Decidable (C.InKernel x) := by
unfold InKernel Hypermap.SameFace
infer_instance
instance (x y : Fin C.dartCount) : Decidable (C.Adjacent x y) := by
unfold Adjacent Hypermap.SameFace
infer_instance
instance (x : Fin C.dartCount) : Decidable (C.Triad x) := by
unfold Triad
infer_instance
instance : Decidable C.ValidContract := by
unfold ValidContract
infer_instance
instance (k : Fin C.dartCount → ConfigurationColor) : Decidable (C.ContractColoring k) := by
unfold ContractColoring Hypermap.SameFace
infer_instance
instance (k : Fin C.dartCount → ConfigurationColor) : Decidable (C.map.Coloring k) := by
unfold Hypermap.Coloring Hypermap.SameFace
infer_instance
instance (t : C.BoundaryTrace) : Decidable (C.RingTrace t) := by
unfold RingTrace
infer_instance
instance (t : C.BoundaryTrace) : Decidable (C.ContractRingTrace t) := by
unfold ContractRingTrace
infer_instance
instance (t : C.BoundaryTrace) (w : C.Chromogram) : Decidable (C.Matches t w) := by
unfold Matches
infer_instance
/-- One justified coclosure addition: a known color permutation or every matching chord word
has a known trace. This is an actual finite proposition and contains no proof oracle. -/
def CanAdd (known : Finset C.BoundaryTrace) (t : C.BoundaryTrace) : Prop :=
(∃ p : ColorSymmetry, C.permuteTrace p t ∈ known) ∨
∀ w : C.Chromogram, C.Matches t w → ∃ u ∈ known, C.Matches u w
instance (known : Finset C.BoundaryTrace) (t : C.BoundaryTrace) :
Decidable (C.CanAdd known t) := by
unfold CanAdd
infer_instance
/-- An untrusted finite trace list; each addition is independently checked. -/
structure ReducibilityCertificate where
additions : List C.BoundaryTrace
/-- Reference extension enumerator; more efficient color-tree implementations need a theorem. -/
def ordinaryTraces : Finset C.BoundaryTrace := Finset.univ.filter C.RingTrace
/-- Check the trace list in order, stopping on an unjustified addition. -/
def checkAdditions : Finset C.BoundaryTrace → List C.BoundaryTrace → Option (Finset C.BoundaryTrace)
| known, [] => some known
| known, t :: ts =>
if C.CanAdd known t then checkAdditions (insert t known) ts else none
/-- Check geometry-independent C-reducibility data by finite computation. -/
def checkReducibility (certificate : C.ReducibilityCertificate) : Bool :=
decide C.ValidContract &&
match C.checkAdditions C.ordinaryTraces certificate.additions with
| none => false
| some known => decide (∀ t, C.ContractRingTrace t → t ∈ known)
/-- Ordinary extendibility is included in its Kempe coclosure. -/
theorem ringTrace_coclosure {t : C.BoundaryTrace} (h : C.RingTrace t) :
C.KempeCoclosure C.RingTrace t := by
intro Q _ ht
exact ⟨t, h, ht⟩
/-- Every accepted elementary addition preserves semantic coclosure membership. -/
theorem canAdd_sound {known : Finset C.BoundaryTrace} {t : C.BoundaryTrace}
(hknown : ∀ u ∈ known, C.KempeCoclosure C.RingTrace u) (h : C.CanAdd known t) :
C.KempeCoclosure C.RingTrace t := by
intro Q hQ ht
rcases h with ⟨p, hp⟩ | hgrams
· exact hknown _ hp Q hQ ((hQ t ht).1 p)
· obtain ⟨w, htw, hclosed⟩ := (hQ t ht).2
obtain ⟨u, hu, huw⟩ := hgrams w htw
exact hknown u hu Q hQ (hclosed u huw)
/-- The invariant for a checked list of coclosure additions. -/
theorem checkAdditions_sound {known result : Finset C.BoundaryTrace}
{steps : List C.BoundaryTrace}
(hknown : ∀ u ∈ known, C.KempeCoclosure C.RingTrace u)
(h : C.checkAdditions known steps = some result) :
∀ u ∈ result, C.KempeCoclosure C.RingTrace u := by
induction steps generalizing known with
| nil =>
simp only [checkAdditions, Option.some.injEq] at h
exact h ▸ hknown
| cons t ts ih =>
simp only [checkAdditions] at h
split at h
next hadd =>
apply ih ?_ h
intro u hu
rcases Finset.mem_insert.mp hu with rfl | hu
· exact C.canAdd_sound hknown hadd
· exact hknown u hu
next => simp at h
/-- Kernel-checked soundness of the reference certificate checker.
This proves the checker implication for every input; it does not assert that any of the
633 catalogue certificates pass. -/
theorem checkReducibility_sound (certificate : C.ReducibilityCertificate)
(h : C.checkReducibility certificate = true) : C.CReducible := by
unfold checkReducibility at h
have hv : C.ValidContract := of_decide_eq_true (Bool.and_eq_true_iff.mp h).1
have hh := (Bool.and_eq_true_iff.mp h).2
split at hh
next => cases hh
next known hk =>
refine ⟨hv, ?_⟩
intro t ht
have hmem : t ∈ known := of_decide_eq_true hh t ht
apply C.checkAdditions_sound (result := known) ?_ hk t hmem
intro u hu
exact C.ringTrace_coclosure (Finset.mem_filter.mp hu).2
/-- Concatenating checked addition lists composes their finite executions. -/
theorem checkAdditions_append {known middle : Finset C.BoundaryTrace}
{steps rest : List C.BoundaryTrace}
(h : C.checkAdditions known steps = some middle) :
C.checkAdditions known (steps ++ rest) = C.checkAdditions middle rest := by
induction steps generalizing known with
| nil =>
simp only [checkAdditions, Option.some.injEq] at h
exact h ▸ rfl
| cons t ts ih =>
simp only [checkAdditions] at h
simp only [List.cons_append, checkAdditions]
split at h
next hadd => rw [if_pos hadd]; exact ih h
next => simp at h
/-- Checked additions retain all previously known traces. -/
theorem checkAdditions_subset {known result : Finset C.BoundaryTrace}
{steps : List C.BoundaryTrace}
(h : C.checkAdditions known steps = some result) : known ⊆ result := by
induction steps generalizing known with
| nil =>
simp only [checkAdditions, Option.some.injEq] at h
exact h ▸ Finset.Subset.refl _
| cons t ts ih =>
simp only [checkAdditions] at h
split at h
next => exact (Finset.subset_insert t known).trans (ih h)
next => simp at h
/-- Completeness of the finite certificate language for semantic C-reducibility.
A maximal reachable trace set has a Kempe-closed complement. Such a complement cannot
contain a contract trace by semantic reducibility. This is an existence proof, not a
claim that the reference enumerator is efficient. -/
theorem checkReducibility_complete (hC : C.CReducible) :
∃ certificate : C.ReducibilityCertificate, C.checkReducibility certificate = true := by
classical
let reachable : Finset (Finset C.BoundaryTrace) :=
Finset.univ.filter fun known ↦ ∃ steps, C.checkAdditions C.ordinaryTraces steps = some known
have hr : C.ordinaryTraces ∈ reachable := by
apply Finset.mem_filter.mpr
exact ⟨Finset.mem_univ _, [], rfl⟩
obtain ⟨known, hknown, hmax⟩ := Finset.exists_max_image reachable Finset.card ⟨_, hr⟩
obtain ⟨steps, hs⟩ := (Finset.mem_filter.mp hknown).2
have hstop : ∀ t, t ∉ known → ¬ C.CanAdd known t := by
intro t ht hadd
have hreach : insert t known ∈ reachable := by
apply Finset.mem_filter.mpr
refine ⟨Finset.mem_univ _, steps ++ [t], ?_⟩
rw [C.checkAdditions_append hs]
simp only [checkAdditions, if_pos hadd]
have hle := hmax (insert t known) hreach
rw [Finset.card_insert_of_notMem ht] at hle
exact Nat.not_succ_le_self known.card hle
have hclosed : C.KempeClosed (fun t ↦ t ∉ known) := by
intro t ht
constructor
· intro p hp
exact hstop t ht (Or.inl ⟨p, hp⟩)
· have hnot : ¬ ∀ w : C.Chromogram, C.Matches t w → ∃ u ∈ known, C.Matches u w :=
fun h ↦ hstop t ht (Or.inr h)
obtain ⟨w, hw⟩ := not_forall.mp hnot
have hparts := Classical.not_imp.mp hw
refine ⟨w, hparts.1, ?_⟩
intro u huw humem
exact hparts.2 ⟨u, humem, huw⟩
have hcoverage : ∀ t, C.ContractRingTrace t → t ∈ known := by
intro t ht
by_contra hnot
obtain ⟨u, hu, hunot⟩ := hC.2 t ht _ hclosed hnot
apply hunot
exact C.checkAdditions_subset hs (Finset.mem_filter.mpr ⟨Finset.mem_univ _, hu⟩)
refine ⟨⟨steps⟩, ?_⟩
unfold checkReducibility
apply Bool.and_eq_true_iff.mpr
refine ⟨decide_eq_true hC.1, ?_⟩
simp only [hs]
exact decide_eq_true hcoverage
/-- Accepted finite certificates characterize exactly semantic C-reducibility. -/
theorem checkReducibility_iff :
(∃ certificate : C.ReducibilityCertificate, C.checkReducibility certificate = true) ↔
C.CReducible :=
⟨fun ⟨certificate, h⟩ ↦ C.checkReducibility_sound certificate h, C.checkReducibility_complete⟩
end Configuration
end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
Configuration and its hypermap. A configuration consists of a natural number , a dart set with three permutations satisfying for every dart, and two finite lists of darts, a ring and a contract . No further conditions are part of this structure: , empty lists, and repeated entries are allowed. Write for membership in the same -cycle, for membership in the same -cycle, and for the length of the -cycle of . The first decidability instance decides for every finite hypermap and every pair of its darts.
ConfigurationColor. The color set is exactly .
configurationColorAdd. For two colors , the defined operation is their bitwise exclusive-or, reduced modulo , rather than integer addition modulo .
ChromogramSymbol and its finite enumeration. There are exactly four distinct symbols: skip, push, pop-same, and pop-other. Their equality is decidable, and the supplied finite enumeration includes all four symbols.
matchChromogram. Given any finite Boolean stack, color list, and symbol list, the matcher processes the two lists in order. Color with skip leaves the stack unchanged; color with push puts false on top; color with push puts true on top. Pop-same removes a false top for color or a true top for color ; pop-other removes a true top for color or a false top for color . All other combinations reject, including every occurrence of color , an unavailable required stack top, or unequal remaining list lengths. Acceptance occurs exactly when both lists and the stack are empty together. Thus two empty input lists accept precisely when the initial stack is empty.
edgeCompletion. For a configuration, its completed contract list replaces each contract entry , in order, by the two entries . Multiplicities are retained; its length is twice the contract-list length.
InKernel. A dart is in the kernel exactly when for every ring entry . This is the union of the face cycles containing no ring entry. An empty ring makes every dart a kernel dart.
Adjacent. Darts are adjacent in the defined sense when some dart satisfies and . This definition does not require or add a separate symmetry condition.
RLink. The directed relation for configuration paths holds for darts exactly when .
NodeRing. The ring list is nonempty, every two entries in list order belong to different face cycles, and sends every listed dart to the next listed dart cyclically, including the last to the first. For a singleton ring, the last condition requires its dart to be fixed by .
KernelRadiusTwo. There exists a kernel dart such that for every kernel dart there is a kernel dart with both adjacent to and adjacent to , with adjacency defined through a source edge between the represented faces. The case is included. No distinctness is imposed on . An empty kernel makes this condition false.
Embeddable. The following conjunction is required of a configuration: the number of -cycles plus the number of -cycles plus the number of -cycles equals plus twice the number of components generated by the permutation steps and their reversals; there is exactly one such component; and for every dart; for every dart; the ring satisfies the nonempty cyclic NodeRing condition; each dart not literally listed in the ring has -cycle length exactly ; each ring entry has ; and there is a kernel dart such that every kernel dart shares an adjacent kernel dart with . The condition outside the ring concerns dart membership, not membership in ring faces. The dart set and the kernel must be nonempty. This predicate imposes no condition on the contract list.
Triad. For a dart , count the darts in its face cycle for which some completed-contract entry satisfies . This count must be strictly larger than , and it must be false that is adjacent to every completed-contract entry . The count is of darts , not distinct neighboring faces. The predicate does not require to be in the kernel, and it fails if the completed contract list is empty.
ValidContract. No ring entry is in the completed contract list ; each pair of entries of in list order belongs to different -cycles; the contract length satisfies ; and if , some kernel dart satisfies the triad condition. Thus repeated entries in fail its pairwise condition, an empty contract fails, and the triad requirement is imposed only at length four. Embeddability is not a conjunct.
ContractColoring. A function is constant on every face cycle, and for every dart it satisfies if and only if is an entry of . Equality is therefore required on all completed-contract darts and inequality on all other darts. Contract validity is not assumed in this definition.
BoundaryTrace. For a ring of length , a boundary trace is any function . When , there is exactly one, the empty function. No realizability condition is part of the type.
Chromogram. For a ring of length , a chromogram assigns one of the four stack-matching symbols to each index . There is exactly one empty chromogram when .
boundaryTrace. For any function , reverse the ring list to obtain . The resulting trace at is , where is the color exclusive-or operation. No coloring condition is required of . If , there are no indices at which to evaluate the modular expression, so the trace is the unique empty one. If , its sole value is .
RingTrace. A trace is realizable as an ordinary ring trace exactly when some function is constant on face cycles, has for every dart, and has reversed-ring consecutive exclusive-or trace equal to . The function need not be unique. With an empty ring, the unique trace is realizable precisely when such a coloring exists.
ContractRingTrace. A trace is realizable as a contract ring trace exactly when some function is constant on face cycles, has exactly for the darts in , and has reversed-ring consecutive exclusive-or trace equal to . Neither validity of the contract nor uniqueness of is required.
ColorSymmetry. A color symmetry is a permutation of fixing , equivalently any permutation of the three nonzero colors.
permuteTrace. For every configuration, color symmetry , and trace , the permuted trace is . Ring indices remain in their original order.
Matches. A trace matches a chromogram exactly when the lists of their values in increasing ring-index order are accepted by the stack matcher starting with an empty stack. Matching includes the required empty final stack. The empty trace matches the empty chromogram.
KempeClosed. A predicate on traces is closed in this sense if for every satisfying , every pointwise color-symmetry permutation of satisfies , and there exists a chromogram matched by such that every trace matching satisfies . The chromogram witness may depend on . Only one such matching chromogram is required for each , not every matching chromogram. The empty predicate is closed vacuously.
KempeCoclosure. For any trace predicate and any trace , coclosure membership means that every trace predicate closed under color symmetries and the existential matching-chromogram condition, if it contains , contains some trace with . The witness may depend on . If no such closed predicate contains , the condition is vacuous.
CReducible. A configuration is reducible in this sense when its contract is valid and, for every contract ring trace , every closed trace predicate containing also contains an ordinary ring trace. Here closed means the color-symmetry and existential matching-chromogram conditions just defined, and ordinary and contract traces are the respective realizable reversed-ring color differences. No embeddability condition is included. If there are no contract ring traces, only contract validity remains.
Preembedding. For every natural , hypermap on darts with permutations , and function , this predicate imposes four conditions. At each source kernel dart , and the source face length equals the target face length at . Each source kernel dart has a same-face dart with . Finally, for every ordered pair of kernel darts at which that edge equality holds, there exists a finite list such that consecutive darts in followed by followed by satisfy , and every entry of is a kernel dart satisfying . The case , empty paths, and paths with repetitions are included. Injectivity of is not required. With empty source kernel all four conditions are vacuous for any function that exists.
Occurs. For every configuration and hypermap on any natural number of darts, occurrence means that satisfies all the conditions of Embeddable and there exists a function into the darts of satisfying the four Preembedding conditions: kernel-face preservation, kernel-face-length preservation, an edge-preserving representative in each kernel face, and the specified source paths between all edge-preserving kernel darts. No injectivity is required. There is no separate planarity, plainness, connectedness, or coloring condition on . Because the source kernel must be nonempty, occurrence in a target with no darts is impossible.
Finite-predicate decidability instances. For every configuration and the relevant darts, colorings, traces, or chromograms, decision procedures are supplied for kernel membership, adjacency, the triad predicate, contract validity, contract coloring, ordinary hypermap coloring, ordinary ring-trace realizability, contract ring-trace realizability, and trace/chromogram matching. They introduce no additional hypotheses.
CanAdd and its decidability instance. Given a finite trace set and trace , addition is permitted if either some color symmetry sends to a member of , or every chromogram matched by is matched by at least one . The latter condition is vacuous if matches no chromogram. No requirement is imposed. A decision procedure for this predicate is supplied.
ReducibilityCertificate. A certificate is a finite ordered list of traces to be added. Empty lists and repetitions are allowed, and the structure contains no correctness hypothesis.
ordinaryTraces. This is the finite set of all traces realizable by a coloring constant on faces and unequal across each edge. It may be empty.
checkAdditions. Given any initial finite trace set and finite addition list, the checker returns successfully for the empty list. For a first entry , it tests whether a color symmetry of is already present or every chromogram matched by also matches a present trace. If so, it inserts as a set member and continues; otherwise it returns failure. Repeated additions need not increase cardinality. A successful return contains the final finite set.
checkReducibility. For a configuration and certificate list, the Boolean result is true exactly when the contract is valid, sequential checking from the set of all ordinary ring traces succeeds, and its resulting set contains every contract ring trace. Failure of any of those tests yields false. Coverage is vacuous when there are no contract ring traces. An empty addition list is allowed.
ringTrace_coclosure. For every configuration and trace realizable by an ordinary coloring, every closed trace predicate containing contains an ordinary ring trace. Thus every ordinary ring trace belongs to the defined coclosure of ordinary ring traces.
canAdd_sound. For every configuration, finite trace set , and trace , assume that every closed trace predicate containing any member of contains an ordinary ring trace. If some color symmetry of belongs to , or every chromogram matched by is matched by some member of , then every closed trace predicate containing also contains an ordinary ring trace. Empty and are not excluded.
checkAdditions_sound. For every configuration, finite trace sets , and finite list , assume every trace in belongs to the coclosure of ordinary ring traces and the sequential addition checker returns successfully from . Then every trace in belongs to that coclosure: each closed trace predicate containing any such trace contains an ordinary ring trace. No contract-validity or embeddability hypothesis is required.
checkReducibility_sound. For every configuration and certificate, acceptance by the reducibility checker implies validity of the contract and the following condition for every contract ring trace : any trace predicate closed under color symmetries and the existential matching-chromogram rule and containing contains an ordinary ring trace. This is exactly the defined reducibility predicate; embeddability is not a conclusion.
checkAdditions_append. For every configuration, finite trace sets , and finite lists , if checking from returns successfully, then checking the concatenation of and from has exactly the same optional result as checking from . That common result may be failure. No coclosure hypothesis is required.
checkAdditions_subset. For every configuration, finite trace sets , and finite addition list , successful checking of from with final result implies . For the empty list, the successful final set is itself.
checkReducibility_complete. For every configuration with valid contract such that every closed trace predicate containing any contract ring trace contains an ordinary ring trace, there exists a finite ordered list of trace additions accepted by the reducibility checker. No list-length bound, uniqueness, or embeddability is asserted.
checkReducibility_iff. For every configuration, existence of a finite certificate accepted by the reducibility checker is equivalent to contract validity together with the condition that every closed trace predicate containing any contract ring trace contain an ordinary ring trace. Both directions apply to the raw configuration structure without an additional geometric hypothesis.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.