Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Validated finite permutation tables for configurations

Definition
FourColor_ConfigurationTable

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

four-color-theoremgraph-theory

Arrays describe edge, node and face maps. Exact lengths, range checks and all three cyclic inverse laws justify conversion to permutations. Ring and contract indices are checked before conversion. Out-of-bounds default values do not enter a valid configuration. Formalization note: a purely formal serialization bridge for the fixed source catalogue.

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 3, PDF p. 9, paragraph on PDF p. 9 identifying the 633 configurations; Section 5.2, PDF pp. 26–32, configuration construction and finite checks. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfmap.v#L127-L131; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfmap.v#L1140-L1141; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfcontract.v#L903-L905; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/configurations.v#L2076; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/reducibility.v#L16-L20.

Definition code
import Definitions.Def_FourColor_Configuration

/-!
# Checked finite configuration tables

A serialization boundary for the explicit catalogue in Gonthier's proof:
Gonthier (2005), Section 5.2, PDF pp. 26–32; pinned Rocq `cfmap.v`
(configuration maps) and `cfcontract.v` (contract dart enumeration).
These table validity checks establish finite permutation data only; geometric
embeddability and reducibility remain separate mathematical obligations.
The default-zero lookup is never used out of bounds in a valid table:
all array lengths and every index are checked before conversion.
-/

namespace FourColor

/-- Finite tables whose validity is checked before they are used as a hypermap. -/
structure DartTable where
  dartCount : ℕ
  edge : Array ℕ
  node : Array ℕ
  face : Array ℕ
  deriving Repr

namespace DartTable

def entry (a : Array ℕ) (i : ℕ) : ℕ := a[i]?.getD 0

def Valid (T : DartTable) : Prop :=
  T.edge.size = T.dartCount ∧ T.node.size = T.dartCount ∧ T.face.size = T.dartCount ∧
    ∀ i : Fin T.dartCount,
      entry T.edge i < T.dartCount ∧ entry T.node i < T.dartCount ∧ entry T.face i < T.dartCount ∧
      entry T.node (entry T.face (entry T.edge i)) = i ∧
      entry T.face (entry T.edge (entry T.node i)) = i ∧
      entry T.edge (entry T.node (entry T.face i)) = i

instance (T : DartTable) : Decidable T.Valid := inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _))

def toHypermap (T : DartTable) (h : T.Valid) : Hypermap T.dartCount := by
  let e : Fin T.dartCount → Fin T.dartCount := fun x ↦ ⟨entry T.edge x, (h.2.2.2 x).1⟩
  let n : Fin T.dartCount → Fin T.dartCount := fun x ↦ ⟨entry T.node x, (h.2.2.2 x).2.1⟩
  let f : Fin T.dartCount → Fin T.dartCount := fun x ↦ ⟨entry T.face x, (h.2.2.2 x).2.2.1⟩
  have h₁ (x) : n (f (e x)) = x := Fin.ext ((h.2.2.2 x).2.2.2.1)
  have h₂ (x) : f (e (n x)) = x := Fin.ext ((h.2.2.2 x).2.2.2.2.1)
  have h₃ (x) : e (n (f x)) = x := Fin.ext ((h.2.2.2 x).2.2.2.2.2)
  exact {
    edge := ⟨e, n ∘ f, h₁, h₃⟩
    node := ⟨n, f ∘ e, h₂, h₁⟩
    face := ⟨f, e ∘ n, h₃, h₂⟩
    edge_node_face := h₁ }

end DartTable

/-- Serialized finite patch data. Invalid table entries cannot construct a configuration. -/
structure ConfigurationTable where
  darts : DartTable
  ring : List ℕ
  contract : List ℕ
  deriving Repr

namespace ConfigurationTable

def Valid (T : ConfigurationTable) : Prop :=
  T.darts.Valid ∧ (∀ x ∈ T.ring, x < T.darts.dartCount) ∧
    (∀ x ∈ T.contract, x < T.darts.dartCount)

instance (T : ConfigurationTable) : Decidable T.Valid :=
  inferInstanceAs (Decidable (_ ∧ _ ∧ _))

/-- All indices and inverse laws are discharged before exposing the semantic value. -/
def toConfiguration (T : ConfigurationTable) (h : T.Valid) : Configuration where
  dartCount := T.darts.dartCount
  map := T.darts.toHypermap h.1
  ring := T.ring.pmap (fun x hx ↦ (⟨x, hx⟩ : Fin T.darts.dartCount)) h.2.1
  contract := T.contract.pmap (fun x hx ↦ (⟨x, hx⟩ : Fin T.darts.dartCount)) h.2.2

end ConfigurationTable
end FourColor

namespace FourColor.DartTable
/-- A Boolean form of the unchanged table laws, avoiding dependent finite quantifier reduction. -/
def validB (T : DartTable) : Bool :=
  (T.edge.size == T.dartCount) && (T.node.size == T.dartCount) &&
    (T.face.size == T.dartCount) && (List.range T.dartCount).all fun i ↦
      decide (entry T.edge i < T.dartCount) && decide (entry T.node i < T.dartCount) &&
      decide (entry T.face i < T.dartCount) &&
      (entry T.node (entry T.face (entry T.edge i)) == i) &&
      (entry T.face (entry T.edge (entry T.node i)) == i) &&
      (entry T.edge (entry T.node (entry T.face i)) == i)
/-- Reflection of every bound and all three inverse laws into the original validity predicate. -/
theorem validB_iff (T : DartTable) : T.validB = true ↔ T.Valid := by
  simp only [validB, Valid, Bool.and_eq_true_iff, beq_iff_eq, List.all_eq_true,
    List.mem_range, decide_eq_true_eq]
  constructor
  · rintro ⟨⟨⟨he, hn⟩, hf⟩, h⟩
    refine ⟨he, hn, hf, ?_⟩
    intro i
    rcases h i.val i.isLt with ⟨⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩, h6⟩
    exact ⟨h1, h2, h3, h4, h5, h6⟩
  · rintro ⟨he, hn, hf, h⟩
    refine ⟨⟨⟨he, hn⟩, hf⟩, ?_⟩
    intro i hi
    rcases h ⟨i, hi⟩ with ⟨h1, h2, h3, h4, h5, h6⟩
    exact ⟨⟨⟨⟨⟨h1, h2⟩, h3⟩, h4⟩, h5⟩, h6⟩
end FourColor.DartTable
namespace FourColor.ConfigurationTable
/-- Executable validation of the hypermap table and both index lists. -/
def validB (T : ConfigurationTable) : Bool :=
  T.darts.validB && T.ring.all (fun x ↦ decide (x < T.darts.dartCount)) &&
    T.contract.all (fun x ↦ decide (x < T.darts.dartCount))
/-- Kernel-checkable Boolean certificates prove exactly the original table-validity statement. -/
theorem validB_iff (T : ConfigurationTable) : T.validB = true ↔ T.Valid := by
  simp only [validB, Valid, Bool.and_eq_true_iff, List.all_eq_true, decide_eq_true_eq,
    DartTable.validB_iff]
  exact and_assoc
end FourColor.ConfigurationTable
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 3, PDF p. 9, paragraph on PDF p. 9 identifying the 633 configurations; Section 5.2, PDF pp. 26–32, configuration construction and finite checks. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfmap.v#L127-L131; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfmap.v#L1140-L1141; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/cfcontract.v#L903-L905; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/configurations.v#L2076; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/reducibility.v#L16-L20.
Read-back

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

A dart table consists of an arbitrary natural number ddd and three arrays E,N,FE,N,FE,N,F of natural numbers. Array lookup at position iii returns the stored entry when present and 000 otherwise, including for indices outside the array. Such a table is valid exactly when each array has length ddd and, for every integer 0≤i<d0\le i<d0≤i<d, its three entries lie below ddd and N(F(E(i)))=iN(F(E(i)))=iN(F(E(i)))=i, F(E(N(i)))=iF(E(N(i)))=iF(E(N(i)))=i, and E(N(F(i)))=iE(N(F(i)))=iE(N(F(i)))=i. From any table together with a proof of these conditions, the conversion constructs a hypermap on {0,…,d−1}\{0,\ldots,d-1\}{0,…,d−1} whose edge, node, and face permutations are respectively the three lookup functions; their inverses are respectively N∘FN\circ FN∘F, F∘EF\circ EF∘E, and E∘NE\circ NE∘N. A configuration table adds two arbitrary finite lists of natural numbers, called ring and contract. It is valid exactly when its dart table is valid and every entry of both lists is below ddd; there is no additional requirement that either list have distinct entries, an adjacency structure, or a particular length, nor any planarity, embeddability, or contraction-reducibility condition. Its conversion, given a proof of validity, uses the constructed hypermap and regards each listed number as a dart, retaining the exact order and repetitions of both lists. Both validity conditions are decidable, and the respective Boolean checkers test exactly the array lengths, all indices 0,…,d−10,\ldots,d-10,…,d−1, the three composition identities, and (for a configuration table) the two lists' bounds; for every table the checker returns true if and only if its propositional validity condition holds. The case d=0d=0d=0 is allowed: a valid dart table then has three empty arrays, and a valid configuration table also has empty ring and contract lists, while the universally quantified composition tests are empty.

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