Finite syntax and checkers for discharging presentations
DefinitionFourColor_DischargeCertificateFinite 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: is the dart set, its size, and is the node permutation. Write for the edge and face permutations, with . Edge, node and face counts are numbers of permutation orbits, including singleton orbits. The component count uses the equivalence generated by all three permutations. Planarity means the exact Euler equality , and connectedness means .
A plain hypermap has a fixed-point-free involution . Cubic means every node orbit has size three; precubic means every node orbit has size at most three. Bridgeless means and never lie in the same face orbit. A -coloring is a map constant on face orbits and different across each edge step. No requirement uses all available colors. The empty dart set has zero components, is planar, and is colorable, but is not connected.
An admissible hypermap is planar, bridgeless, plain and precubic. A minimal counterexample is a non-four-colorable admissible hypermap such that every admissible hypermap with fewer darts is four-colorable. Minimality includes all finite carriers through their enumeration by ; cubicity, connectedness and lower face-degree bounds are not assumed.
The fixed catalogue is the ordered list of all 633 literal configuration maps, boundary rings, and selected contracts, decoded from the pinned source. It is shared by reducibility and coverage; it is not an arbitrary or existentially chosen family. The table checker establishes array sizes, index bounds, and inverse/triangle identities only.
For a configuration , let be its ordered boundary ring, the darts whose faces avoid that ring, and the list containing both darts of every selected contract edge. Geometric admissibility means that the map is planar, bridgeless, plain and connected; is a nonempty node cycle meeting each face at most once; off-ring nodes have arity three; ring faces have arity 3–6; and there is a kernel face having a common adjacent kernel face with every kernel face. Contract validity means that avoids , its darts lie in pairwise distinct node orbits, the contract has 1–4 edges, and a four-edge contract has the source's kernel triad (more than two incident selected-face darts and not every selected face adjacent).
Colors are the Klein-four group , with bitwise XOR as addition. A boundary trace records sums of consecutive face colors around the reversed ring, including the closing pair. Ordinary traces arise from proper face colorings. Contract traces arise from face-constant colorings with equal colors across exactly the edges selected by . A trace set is Kempe-closed if it is closed under all permutations fixing zero and, for each member, contains every trace matching some compatible four-symbol noncrossing-chord word. The stack matcher rejects zero colors and requires an empty final stack. Coclosure of a set consists of traces whose every containing Kempe-closed set meets that set. C-reducibility means contract validity and inclusion of all contract traces in the coclosure of the ordinary traces.
An occurrence of in requires geometric admissibility of and a map of its darts into preserving face steps and exact face arities on . Every kernel face must contain an edge-preserving dart; such darts obey the explicit ring-link path condition in the definition. A total injective map of all permutations is not required. Occurrence up to reflection means occurrence in or in its mirror, whose edge, node and face maps are respectively , and .
The concrete transfer counts, with multiplicity, matches of the 71 symmetrized source patterns at . Their 38 base entries include repeated entries implementing larger transfers. With the face orbit of and , the score is
All intervals are inclusive; a missing upper endpoint means no upper bound. Only the positive hub is eventually restricted to degrees 5–11. Neighboring faces are not silently restricted to those degrees.
Source: Georges Gonthier, A Computer-Checked Proof of the Four Colour Theorem (2005), https://www.microsoft.com/en-us/research/wp-content/uploads/2012/10/4colproof.pdf; Section 5.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.
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
Read-back
What the Lean code literally says, in plain math · gpt-6
Notation for imported data. A hypermap on is given by edge, node, and face permutations with . Its face arity is the cardinality of the face-permutation cycle containing . An arity range has a natural lower endpoint and an optional natural upper endpoint ; membership means and, when exists, . The range may be empty. Write 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 and hypermap on darts, evaluation assigns these six operation symbols the permutations 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 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 and chosen anchor dart , the anchor symbol evaluates to 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 and expression , the result is nested applications of the face symbol to , denoted . At the result is exactly as a syntax tree.
DartExpression.faceInverseTwice. For every expression , this forms the nested expression .
DartExpression.localFace. For every expression and natural index , the result is at and at . In particular, indices and 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 , finite hypermap , and anchor dart , the constraint holds exactly when the face arity at the evaluation of with anchor belongs to : 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 , a hat range, and one fan range; a seven-sector has spoke range , a hat range, and two ordered fan ranges; an eight-sector has spoke range , a hat range, and three ordered fan ranges. For a part and expression , its constraint list begins with . Then, for in order, put and append the constraints that the arity at lies in the spoke range of , the arity at lies in its hat range, and for each fan index starting at zero the arity at lies in fan range . 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 .
CertificateContext. A context 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 , finite hypermap , and anchor , all listed arity constraints must hold at , 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 .
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 , 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 ; symmetry reverses the checked pair; transitivity takes checked pairs and returns only if are the same syntax tree. Congruence returns from a checked pair for any operation . Cancellation returns . The plain, cubic, and triangle forms return , , and respectively. These last four forms return their pairs without inspecting the context. A face-period form selects an arity constraint , requires an existing upper endpoint with lower endpoint exactly , and returns ; a missing entry, absent upper endpoint, or unequal endpoints causes failure. At that returned pair is . Failures of child checks propagate. No hypermap is an argument of this checker.
ArityRange.disjoint. For any ranges , this Boolean is true exactly when an upper endpoint of exists and is strictly below the lower endpoint of , or an upper endpoint of exists and is strictly below the lower endpoint of . 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 , an inequality , and a right equality , and returns exactly when are syntactically identical and are syntactically identical. The injectivity-named form sends a checked pair to by applying its operation to both expressions. The edge-not-fixed form always returns . 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 , the intersection record has lower endpoint . Its upper endpoint is absent if both are absent, is the existing endpoint if exactly one exists, and is 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 always returns . A face-step form takes a checked constraint to when its Boolean is false and to 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 and checked constraint , requires to be syntactically identical, and returns . 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 , and range certificate, the Boolean result is false on range-check failure. For a successful range result it is true exactly when are the same syntax tree and the endpoint subset test from to succeeds: , together with no upper requirement if is unbounded, and otherwise an upper endpoint of at most that of . 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 , root expression , and match certificate, form the ordered constraint list consisting of exact central arity followed by the successive spoke, hat, and fan constraints of the sectors at . 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 , root expression , 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 , any natural degree , and a flow certificate. Let be the fixed 71-position rule list defined by DischargeRules, including its repeated entries. In the helper's order, first take , then each rule in its list order. At position the incoming test is for rooted at the expression , and the outgoing test is for rooted at . Acceptance requires both certificate lists to have length exactly ; 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
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 the length conditions force two empty lists and the bound is , 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 , and edge certificate, a preserved certificate passes exactly when its equality checker returns precisely , and an excluded certificate passes exactly when its inequality checker returns precisely . Both comparisons are comparisons of complete ordered pairs of syntax trees; the reversed pair does not automatically pass.
OccurrenceCertificate. For any configuration with finite dart set , this record contains a Boolean mirrored flag; a dart expression for every source dart ; an equality certificate, arity-range certificate, and edge certificate for each such dart; a source dart for every source dart; and a finite list 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 , existence of a target hypermap, embeddability, or correctness condition is imposed by the record. If is empty all these source-indexed fields are empty functions.
checkOccurrence and its target/path helpers. A configuration supplies source permutations , a ring list, and a contract list, with ; 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 to be when the mirrored flag is false and when true, and the target-edge expression to be when false and when true. Acceptance first requires, for every source kernel dart , that its equality certificate check to the exact ordered pair ; its range certificate entail exact arity equal to the source face-cycle length at at expression ; its edge certificate check for the pair ; the chosen dart lie in the same source face as ; and the edge-certificate tag at be preserved. Acceptance also requires, for every ordered pair of kernel darts with preserved tags, that successive darts in the list followed by followed by satisfy that is in the source face of , and that every intermediate entry of be a kernel dart with a preserved tag. This path check includes ; 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 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 , context , 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 . An occurrence leaf is accepted exactly by checkOccurrence for its indexed catalogue configuration. At an arity split with expression and threshold , both children must accept: one in the context obtained by appending to the arity list and the other after appending . At an equality split , both children must accept, one after appending 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 or is imposed; the split with 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 , and presentation certificate for that catalogue, this calls checkPresentationIn with the context consisting of exactly the one arity constraint , 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.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.