Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Configurations, contracts, Kempe semantics, and a complete reducibility checker

Definition
FourColor_Configuration

by Minghui · Sep 26, 2026 · Mathlib c5ea003 (Lean v4.30.0)

four-color-theoremgraph-theory

A 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: D={0,…,n−1}D=\{0,\ldots,n-1\}D={0,…,n−1} is the dart set, n=∣D∣n = |D|n=∣D∣ its size, and p=νHp = \nu_Hp=νH​ is the node permutation. Write e,fe,fe,f for the edge and face permutations, with p(f(e(d)))=dp(f(e(d)))=dp(f(e(d)))=d. Edge, node and face counts E,N,FE,N,FE,N,F are numbers of permutation orbits, including singleton orbits. The component count CCC uses the equivalence generated by all three permutations. Planarity means the exact Euler equality E+N+F=n+2CE+N+F=n+2CE+N+F=n+2C, and connectedness means C=1C=1C=1.

A plain hypermap has a fixed-point-free involution eee. Cubic means every node orbit has size three; precubic means every node orbit has size at most three. Bridgeless means ddd and e(d)e(d)e(d) never lie in the same face orbit. A kkk-coloring is a map D→{0,…,k−1}D\to\{0,\ldots,k-1\}D→{0,…,k−1} 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 Fin⁡(m)\operatorname{Fin}(m)Fin(m); cubicity, connectedness and lower face-degree bounds are not assumed.

The fixed catalogue C\mathcal CC 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 AAA, let RAR_ARA​ be its ordered boundary ring, KAK_AKA​ the darts whose faces avoid that ring, and SAS_ASA​ the list containing both darts of every selected contract edge. Geometric admissibility means that the map is planar, bridgeless, plain and connected; RAR_ARA​ 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 SAS_ASA​ avoids RAR_ARA​, 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 {0,1,2,3}\{0,1,2,3\}{0,1,2,3}, 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 SAS_ASA​. 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 AAA in HHH requires geometric admissibility of AAA and a map of its darts into HHH preserving face steps and exact face arities on KAK_AKA​. 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 HHH or in its mirror, whose edge, node and face maps are respectively f∘pf\circ pf∘p, p−1p^{-1}p−1 and f−1f^{-1}f−1.

The concrete transfer tH(y)t_H(y)tH​(y) counts, with multiplicity, matches of the 71 symmetrized source patterns at f−2(y)f^{-2}(y)f−2(y). Their 38 base entries include repeated entries implementing larger transfers. With FH(x)F_H(x)FH​(x) the face orbit of xxx and aH(x)=∣FH(x)∣a_H(x)=|F_H(x)|aH​(x)=∣FH​(x)∣, the score is

qH(x)=60−10aH(x)+∑y∈FH(x)(tH(e(y))−tH(y)).q_H(x)=60-10a_H(x)+\sum_{y\in F_H(x)}(t_H(e(y))-t_H(y)).qH​(x)=60−10aH​(x)+y∈FH​(x)∑​(tH​(e(y))−tH​(y)).

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.

Definition code
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
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.
Read-back

What the Lean code literally says, in plain math · gpt-6

Configuration and its hypermap. A configuration CCC consists of a natural number ddd, a dart set D={0,…,d−1}D=\{0,\ldots,d-1\}D={0,…,d−1} with three permutations e,v,fe,v,fe,v,f satisfying v(f(e(x)))=xv(f(e(x)))=xv(f(e(x)))=x for every dart, and two finite lists of darts, a ring RRR and a contract KKK. No further conditions are part of this structure: d=0d=0d=0, empty lists, and repeated entries are allowed. Write x∼fyx\sim_f yx∼f​y for membership in the same fff-cycle, x∼vyx\sim_v yx∼v​y for membership in the same vvv-cycle, and a(x)a(x)a(x) for the length of the fff-cycle of xxx. The first decidability instance decides x∼fyx\sim_f yx∼f​y for every finite hypermap and every pair of its darts.

ConfigurationColor. The color set is exactly {0,1,2,3}\{0,1,2,3\}{0,1,2,3}.

configurationColorAdd. For two colors a,ba,ba,b, the defined operation a⊕ba\oplus ba⊕b is their bitwise exclusive-or, reduced modulo 444, rather than integer addition modulo 444.

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 111 with skip leaves the stack unchanged; color 222 with push puts false on top; color 333 with push puts true on top. Pop-same removes a false top for color 222 or a true top for color 333; pop-other removes a true top for color 222 or a false top for color 333. All other combinations reject, including every occurrence of color 000, 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 EEE replaces each contract entry xxx, in order, by the two entries x,e(x)x,e(x)x,e(x). Multiplicities are retained; its length is twice the contract-list length.

InKernel. A dart xxx is in the kernel exactly when x̸∼frx\not\sim_f rx∼f​r for every ring entry rrr. This is the union of the face cycles containing no ring entry. An empty ring makes every dart a kernel dart.

Adjacent. Darts x,yx,yx,y are adjacent in the defined sense when some dart zzz satisfies x∼fzx\sim_f zx∼f​z and e(z)∼fye(z)\sim_f ye(z)∼f​y. This definition does not require x≠yx\ne yx=y or add a separate symmetry condition.

RLink. The directed relation for configuration paths holds for darts x,yx,yx,y exactly when e(x)∼fye(x)\sim_f ye(x)∼f​y.

NodeRing. The ring list is nonempty, every two entries in list order belong to different face cycles, and vvv 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 vvv.

KernelRadiusTwo. There exists a kernel dart xxx such that for every kernel dart yyy there is a kernel dart zzz with both xxx adjacent to zzz and yyy adjacent to zzz, with adjacency defined through a source edge between the represented faces. The case y=xy=xy=x is included. No distinctness is imposed on x,y,zx,y,zx,y,z. An empty kernel makes this condition false.

Embeddable. The following conjunction is required of a configuration: the number of eee-cycles plus the number of vvv-cycles plus the number of fff-cycles equals ddd plus twice the number of components generated by the permutation steps and their reversals; there is exactly one such component; e(e(x))=xe(e(x))=xe(e(x))=x and e(x)≠xe(x)\ne xe(x)=x for every dart; x̸∼fe(x)x\not\sim_f e(x)x∼f​e(x) for every dart; the ring satisfies the nonempty cyclic NodeRing condition; each dart not literally listed in the ring has vvv-cycle length exactly 333; each ring entry rrr has 3≤a(r)≤63\le a(r)\le63≤a(r)≤6; and there is a kernel dart xxx such that every kernel dart yyy shares an adjacent kernel dart zzz with xxx. 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 xxx, count the darts yyy in its face cycle for which some completed-contract entry ppp satisfies e(y)∼fpe(y)\sim_f pe(y)∼f​p. This count must be strictly larger than 222, and it must be false that xxx is adjacent to every completed-contract entry ppp. The count is of darts yyy, not distinct neighboring faces. The predicate does not require xxx 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 EEE; each pair of entries of EEE in list order belongs to different vvv-cycles; the contract length satisfies 1≤∣K∣≤41\le |K|\le41≤∣K∣≤4; and if ∣K∣=4|K|=4∣K∣=4, some kernel dart satisfies the triad condition. Thus repeated entries in EEE 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 k:D→{0,1,2,3}k:D\to\{0,1,2,3\}k:D→{0,1,2,3} is constant on every face cycle, and for every dart xxx it satisfies k(e(x))=k(x)k(e(x))=k(x)k(e(x))=k(x) if and only if xxx is an entry of EEE. 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 ℓ\ellℓ, a boundary trace is any function {0,…,ℓ−1}→{0,1,2,3}\{0,\ldots,\ell-1\}\to\{0,1,2,3\}{0,…,ℓ−1}→{0,1,2,3}. When ℓ=0\ell=0ℓ=0, there is exactly one, the empty function. No realizability condition is part of the type.

Chromogram. For a ring of length ℓ\ellℓ, a chromogram assigns one of the four stack-matching symbols to each index 0≤i<ℓ0\le i<\ell0≤i<ℓ. There is exactly one empty chromogram when ℓ=0\ell=0ℓ=0.

boundaryTrace. For any function k:D→{0,1,2,3}k:D\to\{0,1,2,3\}k:D→{0,1,2,3}, reverse the ring list to obtain r0′,…,rℓ−1′r'_0,\ldots,r'_{\ell-1}r0′​,…,rℓ−1′​. The resulting trace at i<ℓi<\elli<ℓ is k(ri′)⊕k(r(i+1) mod ℓ′)k(r'_i)\oplus k(r'_{(i+1)\bmod\ell})k(ri′​)⊕k(r(i+1)modℓ′​), where ⊕\oplus⊕ is the color exclusive-or operation. No coloring condition is required of kkk. If ℓ=0\ell=0ℓ=0, there are no indices at which to evaluate the modular expression, so the trace is the unique empty one. If ℓ=1\ell=1ℓ=1, its sole value is 000.

RingTrace. A trace ttt is realizable as an ordinary ring trace exactly when some function k:D→{0,1,2,3}k:D\to\{0,1,2,3\}k:D→{0,1,2,3} is constant on face cycles, has k(e(x))≠k(x)k(e(x))\ne k(x)k(e(x))=k(x) for every dart, and has reversed-ring consecutive exclusive-or trace equal to ttt. The function need not be unique. With an empty ring, the unique trace is realizable precisely when such a coloring exists.

ContractRingTrace. A trace ttt is realizable as a contract ring trace exactly when some function k:D→{0,1,2,3}k:D\to\{0,1,2,3\}k:D→{0,1,2,3} is constant on face cycles, has k(e(x))=k(x)k(e(x))=k(x)k(e(x))=k(x) exactly for the darts in EEE, and has reversed-ring consecutive exclusive-or trace equal to ttt. Neither validity of the contract nor uniqueness of kkk is required.

ColorSymmetry. A color symmetry is a permutation of {0,1,2,3}\{0,1,2,3\}{0,1,2,3} fixing 000, equivalently any permutation of the three nonzero colors.

permuteTrace. For every configuration, color symmetry ppp, and trace ttt, the permuted trace is i↦p(t(i))i\mapsto p(t(i))i↦p(t(i)). Ring indices remain in their original order.

Matches. A trace ttt matches a chromogram www 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 PPP on traces is closed in this sense if for every ttt satisfying PPP, every pointwise color-symmetry permutation of ttt satisfies PPP, and there exists a chromogram www matched by ttt such that every trace uuu matching www satisfies PPP. The chromogram witness may depend on ttt. Only one such matching chromogram is required for each ttt, not every matching chromogram. The empty predicate is closed vacuously.

KempeCoclosure. For any trace predicate PPP and any trace ttt, coclosure membership means that every trace predicate QQQ closed under color symmetries and the existential matching-chromogram condition, if it contains ttt, contains some trace uuu with P(u)P(u)P(u). The witness uuu may depend on QQQ. If no such closed predicate contains ttt, the condition is vacuous.

CReducible. A configuration is reducible in this sense when its contract is valid and, for every contract ring trace ttt, every closed trace predicate containing ttt 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 nnn, hypermap HHH on nnn darts with permutations eH,vH,fHe_H,v_H,f_HeH​,vH​,fH​, and function h:D→{0,…,n−1}h:D\to\{0,\ldots,n-1\}h:D→{0,…,n−1}, this predicate imposes four conditions. At each source kernel dart xxx, h(f(x))=fH(h(x))h(f(x))=f_H(h(x))h(f(x))=fH​(h(x)) and the source face length equals the target face length at h(x)h(x)h(x). Each source kernel dart xxx has a same-face dart yyy with h(e(y))=eH(h(y))h(e(y))=e_H(h(y))h(e(y))=eH​(h(y)). Finally, for every ordered pair of kernel darts x,yx,yx,y at which that edge equality holds, there exists a finite list ppp such that consecutive darts (a,b)(a,b)(a,b) in [v(f(x))][v(f(x))][v(f(x))] followed by ppp followed by [y][y][y] satisfy e(a)∼fbe(a)\sim_f be(a)∼f​b, and every entry zzz of ppp is a kernel dart satisfying h(e(z))=eH(h(z))h(e(z))=e_H(h(z))h(e(z))=eH​(h(z)). The case x=yx=yx=y, empty paths, and paths with repetitions are included. Injectivity of hhh is not required. With empty source kernel all four conditions are vacuous for any function hhh that exists.

Occurs. For every configuration CCC and hypermap HHH on any natural number nnn of darts, occurrence means that CCC satisfies all the conditions of Embeddable and there exists a function into the darts of HHH 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 HHH. 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 AAA and trace ttt, addition is permitted if either some color symmetry sends ttt to a member of AAA, or every chromogram matched by ttt is matched by at least one u∈Au\in Au∈A. The latter condition is vacuous if ttt matches no chromogram. No requirement t∉At\notin At∈/A 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 AAA and finite addition list, the checker returns AAA successfully for the empty list. For a first entry ttt, it tests whether a color symmetry of ttt is already present or every chromogram matched by ttt also matches a present trace. If so, it inserts ttt 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 ttt realizable by an ordinary coloring, every closed trace predicate containing ttt 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 AAA, and trace ttt, assume that every closed trace predicate containing any member of AAA contains an ordinary ring trace. If some color symmetry of ttt belongs to AAA, or every chromogram matched by ttt is matched by some member of AAA, then every closed trace predicate containing ttt also contains an ordinary ring trace. Empty AAA and t∈At\in At∈A are not excluded.

checkAdditions_sound. For every configuration, finite trace sets A,BA,BA,B, and finite list LLL, assume every trace in AAA belongs to the coclosure of ordinary ring traces and the sequential addition checker returns BBB successfully from (A,L)(A,L)(A,L). Then every trace in BBB 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 ttt: any trace predicate closed under color symmetries and the existential matching-chromogram rule and containing ttt 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 A,BA,BA,B, and finite lists L,ML,ML,M, if checking LLL from AAA returns BBB successfully, then checking the concatenation of LLL and MMM from AAA has exactly the same optional result as checking MMM from BBB. That common result may be failure. No coclosure hypothesis is required.

checkAdditions_subset. For every configuration, finite trace sets A,BA,BA,B, and finite addition list LLL, successful checking of LLL from AAA with final result BBB implies A⊆BA\subseteq BA⊆B. For the empty list, the successful final set is AAA 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.

Human review
  • Endorsed by Shuze Chen · Sep 27, 2026

    Confirmed by the moderator at approval.

  • Endorsed by Minghui · Sep 27, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me