Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Finite syntax and checkers for discharging presentations

Definition
FourColor_DischargeCertificate

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

four-color-theoremgraph-theory

Finite packets carry dart expressions, equality and inequality derivations, arity interval witnesses, configuration kernel images and paths, conservative flow bounds, and exhaustive branch trees. Reflected hits use the explicit mirrored permutation formulas. The recursive checkers return Boolean results. Their global soundness is a separate theorem; no certificate has an occurrence/reducibility proof field. Formalization note: a purely formal Lean checker interface to the source-backed presentation and coverage theorems, not a claim that the optimized source presentations have already been translated.

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.5, PDF p. 45, paragraph on PDF p. 45 giving the discharge formula; PDF pp. 44–48, interval splitting, configuration matching, hubcap and presentation paragraphs. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hubcap.v#L126-L153; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hubcap.v#L305-L375; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/present.v#L74-L204.

Definition code
import Definitions.Def_FourColor_DischargeRules
import Definitions.Def_FourColor_Configuration

/-!
A Lean-native, deliberately simple reference certificate language for local unavoidability.
Gonthier (2005), Section 5.5, PDF pp. 44–48, describes interval splits, local configuration
matching, discharging bounds, and reuse of previous branches. The pinned Rocq counterparts
are `part.v`, `redpart.v`, `hubcap.v`, `present.v`, and `present5.v` through `present11.v`.

This language does not reproduce the optimized source implementation. Its certificates
contain finite syntax only: permutation equality derivations, interval witnesses, kernel
maps and paths, and finite branching trees. Soundness is a separate theorem obligation.
Acceptance of the 633 reducibility jobs or of all seven unavoidability cases is not asserted.
More efficient source-style quizzes and hubcaps may replace it after a refinement proof.
-/

namespace FourColor.Discharge

/-- A permutation or its inverse, for navigating a hypermap. -/
inductive DartOperation
  | edge | node | face | edgeInv | nodeInv | faceInv
  deriving DecidableEq, Repr

namespace DartOperation

def inverse : DartOperation → DartOperation
  | .edge => .edgeInv | .node => .nodeInv | .face => .faceInv
  | .edgeInv => .edge | .nodeInv => .node | .faceInv => .face

def eval {n : ℕ} (H : Hypermap n) : DartOperation → Equiv.Perm (Fin n)
  | .edge => H.edge | .node => H.node | .face => H.face
  | .edgeInv => H.edge.symm | .nodeInv => H.node.symm | .faceInv => H.face.symm

end DartOperation

/-- A dart expression based at the hub anchor. -/
inductive DartExpression
  | anchor
  | apply (operation : DartOperation) (argument : DartExpression)
  deriving DecidableEq, Repr

namespace DartExpression

def eval {n : ℕ} (H : Hypermap n) (anchor : Fin n) : DartExpression → Fin n
  | .anchor => anchor
  | .apply op t => op.eval H (t.eval H anchor)

def faceIterate : ℕ → DartExpression → DartExpression
  | 0, t => t
  | n + 1, t => .apply .face (faceIterate n t)

def faceInverseTwice (t : DartExpression) : DartExpression :=
  .apply .faceInv (.apply .faceInv t)

def localFace (t : DartExpression) : ℕ → DartExpression
  | 0 => .apply .edge t
  | i + 1 => .apply .edge (faceIterate (i + 2) (.apply .edge t))

end DartExpression

structure ArityConstraint where
  expression : DartExpression
  range : ArityRange
  deriving DecidableEq, Repr

namespace ArityConstraint

def Holds {n : ℕ} (c : ArityConstraint) (H : Hypermap n) (x : Fin n) : Prop :=
  c.range.Contains (H.faceArity (c.expression.eval H x))

end ArityConstraint

namespace Part

private def sectorConstraints (t : DartExpression) (s : Sector) : List ArityConstraint :=
  [⟨t.localFace 0, s.spoke⟩, ⟨t.localFace 1, s.hat⟩] ++
    s.fans.zipIdx.map (fun (r, i) ↦ ⟨t.localFace (i + 2), r⟩)

private def tailConstraints : DartExpression → Part → List ArityConstraint
  | _, [] => []
  | t, s :: rest => sectorConstraints t s ++ tailConstraints (.apply .face t) rest

/-- Every exact-match test, expanded to concrete arity constraints on dart expressions. -/
def constraints (p : Part) (t : DartExpression) : List ArityConstraint :=
  ⟨t, .exactly p.length⟩ :: tailConstraints t p

end Part

/-- The semantic context of a certificate branch; every field is finite syntax. -/
structure CertificateContext where
  arities : List ArityConstraint := []
  equalities : List (DartExpression × DartExpression) := []
  inequalities : List (DartExpression × DartExpression) := []
  deriving DecidableEq, Repr

namespace CertificateContext

def Holds {n : ℕ} (Γ : CertificateContext) (H : Hypermap n) (x : Fin n) : Prop :=
  (∀ c ∈ Γ.arities, c.Holds H x) ∧
  (∀ p ∈ Γ.equalities, p.1.eval H x = p.2.eval H x) ∧
  (∀ p ∈ Γ.inequalities, p.1.eval H x ≠ p.2.eval H x)

end CertificateContext

/-- Syntax for elementary equality reasoning; no Lean proofs occur in a packet. -/
inductive EqualityCertificate
  | given (index : ℕ)
  | reflexivity (expression : DartExpression)
  | symmetry (proof : EqualityCertificate)
  | transitivity (left right : EqualityCertificate)
  | congruence (operation : DartOperation) (proof : EqualityCertificate)
  | cancel (operation : DartOperation) (expression : DartExpression)
  | plain (expression : DartExpression)
  | cubic (expression : DartExpression)
  | triangle (expression : DartExpression)
  | facePeriod (arityIndex : ℕ)
  deriving Repr

/-- Return the equality checked by a derivation, rejecting malformed compositions. -/
def checkEquality (Γ : CertificateContext) :
    EqualityCertificate → Option (DartExpression × DartExpression)
  | .given i => Γ.equalities[i]?
  | .reflexivity t => some (t, t)
  | .symmetry p => (checkEquality Γ p).map fun (a, b) ↦ (b, a)
  | .transitivity p q => do
    let (a, b) ← checkEquality Γ p
    let (c, d) ← checkEquality Γ q
    if b = c then some (a, d) else none
  | .congruence op p => (checkEquality Γ p).map fun (a, b) ↦ (.apply op a, .apply op b)
  | .cancel op t => some (.apply op (.apply op.inverse t), t)
  | .plain t => some (.apply .edge (.apply .edge t), t)
  | .cubic t => some (.apply .node (.apply .node (.apply .node t)), t)
  | .triangle t => some (.apply .node (.apply .face (.apply .edge t)), t)
  | .facePeriod i => do
    let c ← Γ.arities[i]?
    let u ← c.range.upper
    if c.range.lower = u then some (c.expression.faceIterate u, c.expression) else none

/-- Closed intervals are disjoint if one upper endpoint is below the other's lower endpoint. -/
def ArityRange.disjoint (r s : ArityRange) : Bool :=
  (r.upper.any fun u ↦ decide (u < s.lower)) ||
    (s.upper.any fun u ↦ decide (u < r.lower))

inductive InequalityCertificate
  | given (index : ℕ)
  | symmetry (proof : InequalityCertificate)
  | transport (left : EqualityCertificate) (proof : InequalityCertificate)
      (right : EqualityCertificate)
  | injectivity (operation : DartOperation) (proof : InequalityCertificate)
  | edgeNotFixed (expression : DartExpression)
  | distinctArities (leftIndex rightIndex : ℕ)
  deriving Repr

/-- Inequality proofs use injectivity, plainness, branch facts, or incompatible arities. -/
def checkInequality (Γ : CertificateContext) :
    InequalityCertificate → Option (DartExpression × DartExpression)
  | .given i => Γ.inequalities[i]?
  | .symmetry p => (checkInequality Γ p).map fun (a, b) ↦ (b, a)
  | .transport p q r => do
    let (a, b) ← checkEquality Γ p
    let (c, d) ← checkInequality Γ q
    let (e, f) ← checkEquality Γ r
    if b = c ∧ d = e then some (a, f) else none
  | .injectivity op p => (checkInequality Γ p).map fun (a, b) ↦ (.apply op a, .apply op b)
  | .edgeNotFixed t => some (.apply .edge t, t)
  | .distinctArities i j => do
    let a ← Γ.arities[i]?
    let b ← Γ.arities[j]?
    if a.range.disjoint b.range then some (a.expression, b.expression) else none

/-- Interval intersection, also representing empty intervals explicitly. -/
def ArityRange.intersection (r s : ArityRange) : ArityRange :=
  ⟨max r.lower s.lower, match r.upper, s.upper with
    | none, v => v | v, none => v | some u, some v => some (min u v)⟩

inductive RangeCertificate
  | given (index : ℕ)
  | pentagonal (expression : DartExpression)
  | faceStep (inverse : Bool) (range : RangeCertificate)
  | intersection (left right : RangeCertificate)
  | transport (equality : EqualityCertificate) (range : RangeCertificate)
  deriving Repr

/-- Produce a checked arity interval. Pentagonal facts require the independent ≥5 premise. -/
def checkRange (Γ : CertificateContext) : RangeCertificate → Option ArityConstraint
  | .given i => Γ.arities[i]?
  | .pentagonal t => some ⟨t, .free⟩
  | .faceStep inverse p => (checkRange Γ p).map fun c ↦
    ⟨.apply (if inverse then .faceInv else .face) c.expression, c.range⟩
  | .intersection p q => do
    let a ← checkRange Γ p
    let b ← checkRange Γ q
    if a.expression = b.expression then
      some ⟨a.expression, a.range.intersection b.range⟩ else none
  | .transport p q => do
    let (a, b) ← checkEquality Γ p
    let c ← checkRange Γ q
    if b = c.expression then some ⟨a, c.range⟩ else none

def checkEntails (Γ : CertificateContext) (needed : ArityConstraint)
    (certificate : RangeCertificate) : Bool :=
  match checkRange Γ certificate with
  | none => false
  | some c => decide (c.expression = needed.expression) && c.range.subset needed.range

structure MatchCertificate where
  constraints : List RangeCertificate
  deriving Repr

structure MissCertificate where
  constraintIndex : ℕ
  disjointRange : RangeCertificate
  deriving Repr

/-- All atoms must be justified; list length is checked before zipping. -/
def checkMatch (Γ : CertificateContext) (p : Part) (t : DartExpression)
    (certificate : MatchCertificate) : Bool :=
  let atoms := p.constraints t
  decide (certificate.constraints.length = atoms.length) &&
    (atoms.zip certificate.constraints).all (fun (a, c) ↦ checkEntails Γ a c)

/-- One provably incompatible atom suffices to exclude a rule. -/
def checkMiss (Γ : CertificateContext) (p : Part) (t : DartExpression)
    (certificate : MissCertificate) : Bool :=
  match (p.constraints t)[certificate.constraintIndex]?, checkRange Γ certificate.disjointRange with
  | some a, some b => decide (a.expression = b.expression) && a.range.disjoint b.range
  | _, _ => false

/-- Bound every incoming rule from above and every outgoing rule from below.
`none` deliberately gives the conservative bound 1 incoming or 0 outgoing. -/
structure FlowCertificate where
  incoming : List (Option MissCertificate)
  outgoing : List (Option MatchCertificate)
  deriving Repr

private def incidentTests (degree : ℕ) (incoming : Bool) : List (Part × DartExpression) :=
  (List.range degree).flatMap fun i ↦
    let hub := DartExpression.faceIterate i .anchor
    let dart := if incoming then DartExpression.apply .edge hub else hub
    rules.map fun p ↦ (p, dart.faceInverseTwice)

/-- Explicit charge bound using the fixed 71-rule list; it is intentionally unoptimized. -/
def checkFlow (Γ : CertificateContext) (degree : ℕ) (certificate : FlowCertificate) : Bool :=
  let ins := incidentTests degree true
  let outs := incidentTests degree false
  let bound : ℤ := 60 - 10 * degree +
    certificate.incoming.countP Option.isNone - certificate.outgoing.countP Option.isSome
  decide (certificate.incoming.length = ins.length) &&
  decide (certificate.outgoing.length = outs.length) &&
  (ins.zip certificate.incoming).all (fun ((p, t), c) ↦
    match c with | none => true | some c => checkMiss Γ p t c) &&
  (outs.zip certificate.outgoing).all (fun ((p, t), c) ↦
    match c with | none => true | some c => checkMatch Γ p t c) &&
  decide (bound ≤ 0)

/-- The actual preserved-edge set is certified in both directions on kernel darts. -/
inductive EdgeCertificate
  | preserved (equality : EqualityCertificate)
  | excluded (inequality : InequalityCertificate)
  deriving Repr

namespace EdgeCertificate

def isPreserved : EdgeCertificate → Bool
  | .preserved _ => true | .excluded _ => false

def check (Γ : CertificateContext) (left right : DartExpression) : EdgeCertificate → Bool
  | .preserved p => decide (checkEquality Γ p = some (left, right))
  | .excluded p => decide (checkInequality Γ p = some (left, right))

end EdgeCertificate

/-- A kernel-only source-preembedding witness. Neither reducibility nor occurrence is a field. -/
structure OccurrenceCertificate (C : Configuration) where
  mirrored : Bool
  image : Fin C.dartCount → DartExpression
  faceEqualities : Fin C.dartCount → EqualityCertificate
  arityCertificates : Fin C.dartCount → RangeCertificate
  edgeCertificates : Fin C.dartCount → EdgeCertificate
  faceCover : Fin C.dartCount → Fin C.dartCount
  paths : Fin C.dartCount → Fin C.dartCount → List (Fin C.dartCount)

private def targetFace (mirrored : Bool) (t : DartExpression) : DartExpression :=
  if mirrored then .apply .faceInv t else .apply .face t

private def targetEdge (mirrored : Bool) (t : DartExpression) : DartExpression :=
  if mirrored then .apply .face (.apply .node t) else .apply .edge t

private def checkPath (C : Configuration) (certificate : OccurrenceCertificate C)
    (x y : Fin C.dartCount) : Bool :=
  let p := certificate.paths x y
  let r := C.map.node (C.map.face x) :: (p ++ [y])
  (r.zip r.tail).all (fun (a, b) ↦ decide (C.map.SameFace (C.map.edge a) b)) &&
    p.all (fun z ↦ decide (C.InKernel z) && (certificate.edgeCertificates z).isPreserved)

/-- Check precisely the source preembedding obligations, restricted to the kernel.
When `mirrored` is true, the target face is inverted and the target edge is `face ∘ node`.
Geometric admissibility of the fixed configuration is supplied by the catalogue-validity theorem. -/
def checkOccurrence (Γ : CertificateContext) (C : Configuration)
    (certificate : OccurrenceCertificate C) : Bool :=
  decide (∀ x : Fin C.dartCount, C.InKernel x →
    checkEquality Γ (certificate.faceEqualities x) =
      some (certificate.image (C.map.face x), targetFace certificate.mirrored (certificate.image x)) ∧
    checkEntails Γ ⟨certificate.image x, .exactly (faceArity C.map x)⟩
      (certificate.arityCertificates x) = true ∧
    (certificate.edgeCertificates x).check Γ
      (certificate.image (C.map.edge x))
      (targetEdge certificate.mirrored (certificate.image x)) = true ∧
    C.map.SameFace x (certificate.faceCover x) ∧
    (certificate.edgeCertificates (certificate.faceCover x)).isPreserved = true) &&
  decide (∀ x y : Fin C.dartCount,
    C.InKernel x → (certificate.edgeCertificates x).isPreserved = true →
    C.InKernel y → (certificate.edgeCertificates y).isPreserved = true →
    checkPath C certificate x y = true)

/-- Complete finite branching, with contradiction, charge, and occurrence leaves. -/
inductive PresentationCertificate (catalogue : List Configuration)
  | emptyRange (range : RangeCertificate)
  | contradiction (equality : EqualityCertificate) (inequality : InequalityCertificate)
  | charge (certificate : FlowCertificate)
  | occurrence (index : Fin catalogue.length)
      (certificate : OccurrenceCertificate catalogue[index])
  | splitArity (expression : DartExpression) (threshold : ℕ)
      (lower upper : PresentationCertificate catalogue)
  | splitEquality (left right : DartExpression)
      (equal unequal : PresentationCertificate catalogue)
  | strengthen (range : RangeCertificate) (child : PresentationCertificate catalogue)

/-- Total, syntax-directed checking. Every split checks both exhaustive branches. -/
def checkPresentationIn (catalogue : List Configuration) (degree : ℕ)
    (Γ : CertificateContext) : PresentationCertificate catalogue → Bool
  | .emptyRange p => match checkRange Γ p with
    | some c => c.range.upper.any fun u ↦ decide (u < c.range.lower)
    | none => false
  | .contradiction p q => match checkEquality Γ p, checkInequality Γ q with
    | some (a, b), some (c, d) => decide (a = c ∧ b = d)
    | _, _ => false
  | .charge p => checkFlow Γ degree p
  | .occurrence i p => checkOccurrence Γ catalogue[i] p
  | .splitArity t k l r =>
    checkPresentationIn catalogue degree
      { Γ with arities := Γ.arities ++ [⟨t, ⟨0, some k⟩⟩] } l &&
    checkPresentationIn catalogue degree
      { Γ with arities := Γ.arities ++ [⟨t, ⟨k + 1, none⟩⟩] } r
  | .splitEquality a b l r =>
    checkPresentationIn catalogue degree { Γ with equalities := Γ.equalities ++ [(a, b)] } l &&
    checkPresentationIn catalogue degree { Γ with inequalities := Γ.inequalities ++ [(a, b)] } r
  | .strengthen p child => match checkRange Γ p with
    | none => false
    | some c => checkPresentationIn catalogue degree { Γ with arities := Γ.arities ++ [c] } child

/-- The starting branch fixes the actual hub degree. -/
def checkPresentation (catalogue : List Configuration) (degree : ℕ)
    (certificate : PresentationCertificate catalogue) : Bool :=
  checkPresentationIn catalogue degree { arities := [⟨.anchor, .exactly degree⟩] } certificate

end FourColor.Discharge
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.5, PDF p. 45, paragraph on PDF p. 45 giving the discharge formula; PDF pp. 44–48, interval splitting, configuration matching, hubcap and presentation paragraphs. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hubcap.v#L126-L153; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hubcap.v#L305-L375; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/present.v#L74-L204.
Read-back

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

Notation for imported data. A hypermap on D={0,…,n−1}D=\{0,\ldots,n-1\}D={0,…,n−1} is given by edge, node, and face permutations e,v,fe,v,fe,v,f with v(f(e(x)))=xv(f(e(x)))=xv(f(e(x)))=x. Its face arity aH(x)a_H(x)aH​(x) is the cardinality of the face-permutation cycle containing xxx. An arity range has a natural lower endpoint lll and an optional natural upper endpoint uuu; membership means l≤ml\le ml≤m and, when uuu exists, m≤um\le um≤u. The range may be empty. Write [l,∞)[l,\infty)[l,∞) when there is no upper endpoint. All interval notation here refers to natural numbers. In the symbolic checkers below, expressions are finite syntax trees: checking two expressions for equality compares the trees exactly and does not identify trees merely because their evaluations agree.

DartOperation. There are exactly six operation symbols: edge, node, face, inverse-edge, inverse-node, and inverse-face. Equality of operation symbols is decidable.

DartOperation.inverse. This function exchanges edge with inverse-edge, node with inverse-node, and face with inverse-face in both directions.

DartOperation.eval. For every natural nnn and hypermap HHH on nnn darts, evaluation assigns these six operation symbols the permutations e,v,f,e−1,v−1,f−1e,v,f,e^{-1},v^{-1},f^{-1}e,v,f,e−1,v−1,f−1 respectively. It requires no anchor dart, so the function is also defined for the empty hypermap.

DartExpression. An expression is either a distinguished anchor symbol AAA or an operation symbol applied to another expression. Expressions have decidable structural equality. There are no other constants or variables and no quotient by permutation identities.

DartExpression.eval. For every finite hypermap HHH and chosen anchor dart xxx, the anchor symbol evaluates to xxx and an operation applied to an expression evaluates by applying the corresponding hypermap permutation to the recursively evaluated argument. For a hypermap with zero darts no anchor can be supplied.

DartExpression.faceIterate. For every natural number mmm and expression ttt, the result is mmm nested applications of the face symbol to ttt, denoted fm(t)f^m(t)fm(t). At m=0m=0m=0 the result is exactly ttt as a syntax tree.

DartExpression.faceInverseTwice. For every expression ttt, this forms the nested expression f−1(f−1(t))f^{-1}(f^{-1}(t))f−1(f−1(t)).

DartExpression.localFace. For every expression ttt and natural index jjj, the result is e(t)e(t)e(t) at j=0j=0j=0 and e(fj+1(e(t)))e(f^{j+1}(e(t)))e(fj+1(e(t))) at j≥1j\ge1j≥1. In particular, indices 111 and 222 use two and three nested face operations respectively. This constructs expressions without evaluating or simplifying them.

ArityConstraint. An arity constraint is a pair consisting of a dart expression and an arity range. Equality of constraints is decidable. No satisfiability condition is required.

ArityConstraint.Holds. For every constraint (t,r)(t,r)(t,r), finite hypermap HHH, and anchor dart xxx, the constraint holds exactly when the face arity at the evaluation of ttt with anchor xxx belongs to rrr: it is at least the stored lower endpoint and at most the upper endpoint whenever that endpoint exists.

Part.constraints and its list-building helpers. A part is a finite ordered list of sectors. A basic sector stores a spoke range and a hat range and has no fans; a six-sector has spoke range {6}\{6\}{6}, a hat range, and one fan range; a seven-sector has spoke range {7}\{7\}{7}, a hat range, and two ordered fan ranges; an eight-sector has spoke range {8}\{8\}{8}, a hat range, and three ordered fan ranges. For a part p=[s0,…,sm−1]p=[s_0,\ldots,s_{m-1}]p=[s0​,…,sm−1​] and expression ttt, its constraint list begins with (t,{m})(t,\{m\})(t,{m}). Then, for j=0,…,m−1j=0,\ldots,m-1j=0,…,m−1 in order, put tj=fj(t)t_j=f^j(t)tj​=fj(t) and append the constraints that the arity at e(tj)e(t_j)e(tj​) lies in the spoke range of sjs_jsj​, the arity at e(f2(e(tj)))e(f^2(e(t_j)))e(f2(e(tj​))) lies in its hat range, and for each fan index iii starting at zero the arity at e(fi+3(e(tj)))e(f^{i+3}(e(t_j)))e(fi+3(e(tj​))) lies in fan range iii. The recursive helpers produce this order by adding one sector's spoke, hat, and fans, then advancing the center expression by one face operation. Even an empty part yields the one constraint (t,{0})(t,\{0\})(t,{0}).

CertificateContext. A context Γ\GammaΓ consists of three finite lists: arity constraints, ordered pairs of expressions representing equalities, and ordered pairs representing inequalities. Each list defaults to the empty list. Equality of contexts is decidable. No consistency or realizability proof is part of the structure.

CertificateContext.Holds. For every context Γ\GammaΓ, finite hypermap HHH, and anchor xxx, all listed arity constraints must hold at (H,x)(H,x)(H,x), the two expressions in each listed equality must evaluate to the same dart, and the two expressions in each listed inequality must evaluate to distinct darts. All three lists are universally quantified; an empty context holds for every supplied H,xH,xH,x.

EqualityCertificate. An equality-certificate tree has one of ten forms: select an equality by a natural list index; reflexivity at an expression; symmetry of a child; transitivity of two children; applying one of the six operations to a child equality; cancellation for an operation and expression; a plain-edge form at an expression; a cubic-node form at an expression; a triangle form at an expression; or a face-period form selecting a natural arity-list index. The datatype itself does not require these records to pass a checker or to have a hypermap interpretation.

checkEquality. Given any context Γ\GammaΓ, the checker returns either failure or an ordered pair of expressions. An indexed equality returns that list entry and fails if its zero-based natural index is out of range. Reflexivity returns (t,t)(t,t)(t,t); symmetry reverses the checked pair; transitivity takes checked pairs (a,b),(c,d)(a,b),(c,d)(a,b),(c,d) and returns (a,d)(a,d)(a,d) only if b,cb,cb,c are the same syntax tree. Congruence returns (o(a),o(b))(o(a),o(b))(o(a),o(b)) from a checked pair (a,b)(a,b)(a,b) for any operation ooo. Cancellation returns (o(o−1(t)),t)(o(o^{-1}(t)),t)(o(o−1(t)),t). The plain, cubic, and triangle forms return (e(e(t)),t)(e(e(t)),t)(e(e(t)),t), (v(v(v(t))),t)(v(v(v(t))),t)(v(v(v(t))),t), and (v(f(e(t))),t)(v(f(e(t))),t)(v(f(e(t))),t) respectively. These last four forms return their pairs without inspecting the context. A face-period form selects an arity constraint (t,r)(t,r)(t,r), requires an existing upper endpoint uuu with lower endpoint exactly uuu, and returns (fu(t),t)(f^u(t),t)(fu(t),t); a missing entry, absent upper endpoint, or unequal endpoints causes failure. At u=0u=0u=0 that returned pair is (t,t)(t,t)(t,t). Failures of child checks propagate. No hypermap is an argument of this checker.

ArityRange.disjoint. For any ranges r,sr,sr,s, this Boolean is true exactly when an upper endpoint of rrr exists and is strictly below the lower endpoint of sss, or an upper endpoint of sss exists and is strictly below the lower endpoint of rrr. Absent upper endpoints contribute false. This is the specified endpoint comparison, with no separate test for either range's own inconsistent endpoints.

InequalityCertificate. An inequality-certificate tree has one of six forms: select an inequality by a natural index; reverse a child inequality; transport a child inequality using a left and a right equality certificate; apply one of the six operation symbols to a child inequality; assert the edge-not-fixed form at an expression; or use two natural arity-list indices for distinct arities. The structure alone carries no successful-check requirement.

checkInequality. For any context, an indexed form returns its stored inequality or fails for an out-of-range index; symmetry reverses a checked pair. Transport checks a left equality (a,b)(a,b)(a,b), an inequality (c,d)(c,d)(c,d), and a right equality (e,g)(e,g)(e,g), and returns (a,g)(a,g)(a,g) exactly when b,cb,cb,c are syntactically identical and d,ed,ed,e are syntactically identical. The injectivity-named form sends a checked pair (a,b)(a,b)(a,b) to (o(a),o(b))(o(a),o(b))(o(a),o(b)) by applying its operation to both expressions. The edge-not-fixed form always returns (e(t),t)(e(t),t)(e(t),t). The distinct-arities form obtains the two indexed arity constraints and returns their expression pair only when their ranges pass the stated strict-endpoint disjointness test. Missing entries, failed children, or failed comparisons give failure. The checker takes no hypermap argument.

ArityRange.intersection. For any ranges r,sr,sr,s, the intersection record has lower endpoint max⁡(lr,ls)\max(l_r,l_s)max(lr​,ls​). Its upper endpoint is absent if both are absent, is the existing endpoint if exactly one exists, and is min⁡(ur,us)\min(u_r,u_s)min(ur​,us​) if both exist. The record is returned even when its resulting upper endpoint is below its lower endpoint.

RangeCertificate. A range-certificate tree is one of five forms: select an arity constraint by a natural index; a pentagonal form at an expression; move a child range one face step with a Boolean selecting forward or inverse direction; intersect two child ranges; or transport a child range using an equality certificate. No semantic hypotheses are stored in this datatype.

checkRange. For any context, a given-index form returns the indexed arity constraint and fails for an out-of-range index. The pentagonal form at ttt always returns (t,[5,∞))(t,[5,\infty))(t,[5,∞)). A face-step form takes a checked constraint (t,r)(t,r)(t,r) to (f(t),r)(f(t),r)(f(t),r) when its Boolean is false and to (f−1(t),r)(f^{-1}(t),r)(f−1(t),r) when it is true. Intersection takes two checked constraints, requires their expression trees to coincide, and returns that expression with the maximum-lower/minimum-existing-upper intersection range. Transport takes a checked equality (a,b)(a,b)(a,b) and checked constraint (t,r)(t,r)(t,r), requires b,tb,tb,t to be syntactically identical, and returns (a,r)(a,r)(a,r). All failed child checks or required comparisons cause failure. Empty intersection ranges are allowed, and no hypermap or lower-face-arity hypothesis is supplied as an argument to this checker.

checkEntails. For any context, needed constraint (t,s)(t,s)(t,s), and range certificate, the Boolean result is false on range-check failure. For a successful range result (u,r)(u,r)(u,r) it is true exactly when u,tu,tu,t are the same syntax tree and the endpoint subset test from rrr to sss succeeds: ls≤lrl_s\le l_rls​≤lr​, together with no upper requirement if sss is unbounded, and otherwise an upper endpoint of rrr at most that of sss. The predicate uses this syntactic range comparison even for empty ranges.

MatchCertificate. A match certificate stores a finite ordered list of range certificates. Its structure imposes no length or validity condition.

MissCertificate. A miss certificate stores a natural index of one required constraint and a range certificate intended for a disjoint range. The index may be out of range; the structure itself does not reject it.

checkMatch. For any context, part ppp, root expression ttt, and match certificate, form the ordered constraint list consisting of exact central arity ∣p∣|p|∣p∣ followed by the successive spoke, hat, and fan constraints of the sectors at t,f(t),…t,f(t),\ldotst,f(t),…. Acceptance requires the certificate's range-certificate list to have exactly the same length, and each corresponding certificate must pass checkEntails for the required constraint. The length condition prevents omission by a shorter zipped list. An empty part still has its one central-arity-zero constraint and therefore requires one range certificate.

checkMiss. For any context, part ppp, root expression ttt, and miss certificate, select the indicated zero-based entry of the same required-constraint list and check the certificate's range. Acceptance requires both operations to succeed, their expression trees to be identical, and their ranges to pass the strict-endpoint disjointness test. Any missing index, failed range check, different expression, or failed disjointness test yields false. One selected required constraint is tested; there is no requirement to reject each constraint.

FlowCertificate. A flow certificate consists of a finite list of optional miss certificates for incoming positions and a finite list of optional match certificates for outgoing positions. Each position may contain no certificate. The structure imposes no prescribed lengths.

checkFlow and the incident-test helper. Fix the context Γ\GammaΓ, any natural degree ddd, and a flow certificate. Let R\mathcal RR be the fixed 71-position rule list defined by DischargeRules, including its repeated entries. In the helper's order, first take i=0,…,d−1i=0,\ldots,d-1i=0,…,d−1, then each rule ppp in its list order. At position (i,p)(i,p)(i,p) the incoming test is for ppp rooted at the expression f−1(f−1(e(fi(A))))f^{-1}(f^{-1}(e(f^i(A))))f−1(f−1(e(fi(A)))), and the outgoing test is for ppp rooted at f−1(f−1(fi(A)))f^{-1}(f^{-1}(f^i(A)))f−1(f−1(fi(A))). Acceptance requires both certificate lists to have length exactly 71d71d71d; every present incoming certificate must pass checkMiss for its corresponding part and expression; every present outgoing certificate must pass checkMatch for its corresponding part and expression; and the integer inequality

60−10d+#{incoming entries with no certificate}−#{outgoing entries with a certificate}≤060-10d+\#\{\text{incoming entries with no certificate}\}-\#\{\text{outgoing entries with a certificate}\}\le060−10d+#{incoming entries with no certificate}−#{outgoing entries with a certificate}≤0

must hold. Missing incoming and outgoing certificates impose no local check. Incoming positions with present certificates are not counted in the positive term; outgoing positions with absent certificates are not counted in the subtracted term. All subtraction in this bound is integer subtraction. At d=0d=0d=0 the length conditions force two empty lists and the bound is 60≤060\le060≤0, so the checker returns false. The degree is otherwise any natural number, and no hypermap is an input.

EdgeCertificate. An edge certificate is either a preserved tag containing an equality certificate or an excluded tag containing an inequality certificate. The tags themselves store no validity assertion.

EdgeCertificate.isPreserved. This Boolean returns true exactly for the preserved constructor, independently of the contained equality certificate or any context; it returns false for the excluded constructor.

EdgeCertificate.check. For any context, ordered pair of expressions (a,b)(a,b)(a,b), and edge certificate, a preserved certificate passes exactly when its equality checker returns precisely (a,b)(a,b)(a,b), and an excluded certificate passes exactly when its inequality checker returns precisely (a,b)(a,b)(a,b). Both comparisons are comparisons of complete ordered pairs of syntax trees; the reversed pair does not automatically pass.

OccurrenceCertificate. For any configuration CCC with finite dart set DCD_CDC​, this record contains a Boolean mirrored flag; a dart expression I(z)I(z)I(z) for every source dart zzz; an equality certificate, arity-range certificate, and edge certificate for each such dart; a source dart q(z)q(z)q(z) for every source dart; and a finite list P(x,y)P(x,y)P(x,y) of source darts for every ordered source-dart pair. These are total functions on all source darts, not just on kernel darts. No injectivity of III, existence of a target hypermap, embeddability, or correctness condition is imposed by the record. If DCD_CDC​ is empty all these source-indexed fields are empty functions.

checkOccurrence and its target/path helpers. A configuration supplies source permutations eC,vC,fCe_C,v_C,f_CeC​,vC​,fC​, a ring list, and a contract list, with vC(fC(eC(z)))=zv_C(f_C(e_C(z)))=zvC​(fC​(eC​(z)))=z; source kernel membership means that the source face cycle contains no ring entry. Given a context and occurrence certificate, define the target-face expression at ttt to be f(t)f(t)f(t) when the mirrored flag is false and f−1(t)f^{-1}(t)f−1(t) when true, and the target-edge expression to be e(t)e(t)e(t) when false and f(v(t))f(v(t))f(v(t)) when true. Acceptance first requires, for every source kernel dart zzz, that its equality certificate check to the exact ordered pair (I(fC(z)),target-face(I(z)))(I(f_C(z)),\text{target-face}(I(z)))(I(fC​(z)),target-face(I(z))); its range certificate entail exact arity equal to the source face-cycle length at zzz at expression I(z)I(z)I(z); its edge certificate check for the pair (I(eC(z)),target-edge(I(z)))(I(e_C(z)),\text{target-edge}(I(z)))(I(eC​(z)),target-edge(I(z))); the chosen dart q(z)q(z)q(z) lie in the same source face as zzz; and the edge-certificate tag at q(z)q(z)q(z) be preserved. Acceptance also requires, for every ordered pair of kernel darts x,yx,yx,y with preserved tags, that successive darts (a,b)(a,b)(a,b) in the list [vC(fC(x))][v_C(f_C(x))][vC​(fC​(x))] followed by P(x,y)P(x,y)P(x,y) followed by [y][y][y] satisfy that eC(a)e_C(a)eC​(a) is in the source face of bbb, and that every intermediate entry zzz of P(x,y)P(x,y)P(x,y) be a kernel dart with a preserved tag. This path check includes x=yx=yx=y; empty or repeated intermediate lists are permitted when their stated tests hold. All required equality-check outputs are compared syntactically. The entire Boolean is these two universal checks: embeddability and reducibility of CCC are not additional conjuncts, and no hypermap or injectivity check is an argument. If the source kernel is empty, both universal checks are vacuous and the result is true.

PresentationCertificate. For any finite ordered catalogue of configurations, a presentation certificate is a finite tree with seven possible forms: a range certificate for an empty-range leaf; equality and inequality certificates for a contradiction leaf; a flow certificate for a charge leaf; a valid zero-based catalogue index and an occurrence certificate for exactly that indexed configuration; an arity split at any expression and natural threshold with two child trees; an equality split at two expressions with two child trees; or a range certificate together with one child for strengthening. For an empty catalogue no occurrence index exists, while the other constructors remain available. The datatype does not assert checker acceptance.

checkPresentationIn. For any finite catalogue, natural degree ddd, context Γ\GammaΓ, and presentation tree, the Boolean checker acts recursively as follows. An empty-range leaf accepts exactly when its range checker returns a range with an existing upper endpoint strictly below its lower endpoint. A contradiction leaf accepts exactly when the equality and inequality checkers both return the same ordered pair of expression trees. A charge leaf is accepted exactly by checkFlow at (Γ,d)(\Gamma,d)(Γ,d). An occurrence leaf is accepted exactly by checkOccurrence for its indexed catalogue configuration. At an arity split with expression ttt and threshold kkk, both children must accept: one in the context obtained by appending (t,[0,k])(t,[0,k])(t,[0,k]) to the arity list and the other after appending (t,[k+1,∞))(t,[k+1,\infty))(t,[k+1,∞)). At an equality split (a,b)(a,b)(a,b), both children must accept, one after appending (a,b)(a,b)(a,b) to the equality list and one after appending it to the inequality list. For strengthening, the range checker must return a constraint, which is appended to the arity list before recursively checking the sole child. Failed optional checks yield false. Appending preserves all previous entries and indices. No bound on ddd or kkk is imposed; the split with k=0k=0k=0 includes exact arity zero in its first branch. The checker takes no hypermap and this declaration makes no additional semantic soundness assertion.

checkPresentation. For any finite catalogue, natural degree ddd, and presentation certificate for that catalogue, this calls checkPresentationIn with the context consisting of exactly the one arity constraint (A,{d})(A,\{d\})(A,{d}), an empty equality list, and an empty inequality list. The natural degree may be zero. No minimum-degree, maximum-degree, catalogue-nonemptiness, or configuration-embeddability condition is inserted into the initial context.

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