The 38 base and 71 symmetrized discharging patterns
DefinitionFourColor_DischargeRulesConcrete interval sectors describe all source rules with multiplicity. Executable matching is proved equivalent to semantic arity constraints. The transfer counts matches at inverse-face squared; its rational score is the existing face charge. The bundle proves score at most 60 minus five times arity under a separate transfer cap of five, and hence the positive-hub degree bound. Formalization note: source-derived literal rules with proved matching and arithmetic bridges; no unavoidability is assumed.
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 unnumbered discharge formula; PDF pp. 44–48, including the 71-pattern paragraph on p. 45. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/part.v#L159-L175; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/part.v#L603-L626; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/part.v#L801-L852; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/part.v#L892-L927; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L66-L172; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/discharge.v#L378-L398.
import Definitions.Def_FourColor_Discharging
import Mathlib.GroupTheory.Perm.Cycle.Factors
import Mathlib.Tactic.Linarith
import Mathlib.Tactic.NormNum
/-!
The literal rule data are derived from work copyright 2006–2018 Microsoft Corporation
and Inria, distributed under CeCILL-B. See
`missions/four-color-theorem/data/LICENSE.fourcolor`.
Concrete discharging patterns and all 38 base-rule entries at
rocq-community/fourcolor `c1d6b1cd5288bea4b067aac13cdde3c18dffe018`.
The data represent the 32 numbered RSST rules, with the source's specializations
and multiplicities. The source is `discharge.v`, lines 66–157; local matching and
reflection are specified by `part.v`, lines 159–175, 603–626, and 892–927.
See Gonthier (2005), Section 5.5, PDF pp. 44–48.
Intervals and lists replace the source's packed recursive syntax. The algorithms
below are total Lean functions; no rule or matching oracle is assumed correct.
-/
namespace FourColor.Discharge
/-- A closed arity interval; `none` is an unbounded upper endpoint. -/
structure ArityRange where
lower : ℕ
upper : Option ℕ
deriving DecidableEq, Repr
namespace ArityRange
def Contains (r : ArityRange) (n : ℕ) : Prop :=
r.lower ≤ n ∧ ∀ u ∈ r.upper, n ≤ u
instance (r : ArityRange) (n : ℕ) : Decidable (r.Contains n) :=
inferInstanceAs (Decidable (r.lower ≤ n ∧ ∀ u ∈ r.upper, n ≤ u))
def contains (r : ArityRange) (n : ℕ) : Bool := decide (r.Contains n)
/-- The unconstrained range used for pentagonal hypermaps. -/
def free : ArityRange := ⟨5, none⟩
def exactly (n : ℕ) : ArityRange := ⟨n, some n⟩
def atLeast (n : ℕ) : ArityRange := ⟨n, none⟩
def atMost (n : ℕ) : ArityRange := ⟨5, some n⟩
/-- Sufficient interval containment, with the same result as `cmp_range = Psubset`
on the fifteen nonempty source ranges. -/
def subset (r s : ArityRange) : Bool :=
decide (s.lower ≤ r.lower) && match s.upper, r.upper with
| none, _ => true
| some _, none => false
| some v, some u => decide (u ≤ v)
theorem contains_iff (r : ArityRange) (n : ℕ) :
r.contains n = true ↔ r.Contains n := by simp [contains]
theorem subset_sound {r s : ArityRange} (h : r.subset s = true) :
∀ n, r.Contains n → s.Contains n := by
intro n hn
have hh : decide (s.lower ≤ r.lower) = true ∧ (match s.upper, r.upper with
| none, _ => true
| some _, none => false
| some v, some u => decide (u ≤ v)) = true := by simpa [subset] using h
obtain ⟨lo, hu⟩ := hh
refine ⟨le_trans (of_decide_eq_true lo) hn.1, ?_⟩
cases hs : s.upper with
| none => simp
| some u =>
cases hr : r.upper with
| none => simp [hs, hr] at hu
| some v =>
have hvu : v ≤ u := by simpa [hs, hr] using hu
intro z hz
have hz' : z = u := by simpa [hs, eq_comm] using hz
subst z
exact le_trans (hn.2 v (by simp [hr])) hvu
end ArityRange
/-- One sector, with an optional fixed number of constrained fan faces.
Nontrivial fans fix the spoke arity, so reflection preserves their indexing. -/
inductive Sector where
| basic (spoke hat : ArityRange)
| six (hat fan : ArityRange)
| seven (hat fan₁ fan₂ : ArityRange)
| eight (hat fan₁ fan₂ fan₃ : ArityRange)
deriving DecidableEq, Repr
namespace Sector
def spoke : Sector → ArityRange
| .basic s _ => s
| .six .. => .exactly 6
| .seven .. => .exactly 7
| .eight .. => .exactly 8
def hat : Sector → ArityRange
| .basic _ h | .six h _ | .seven h _ _ | .eight h _ _ _ => h
def fans : Sector → List ArityRange
| .basic .. => []
| .six _ f => [f]
| .seven _ f₁ f₂ => [f₁, f₂]
| .eight _ f₁ f₂ f₃ => [f₁, f₂, f₃]
/-- Reflection reverses fans and takes the hat from the next sector. -/
def reflect (h : ArityRange) : Sector → Sector
| .basic s _ => .basic s h
| .six _ f => .six h f
| .seven _ f₁ f₂ => .seven h f₂ f₁
| .eight _ f₁ f₂ f₃ => .eight h f₃ f₂ f₁
/-- The source's sufficient subset test, including its conservative treatment
of a basic sector compared with one carrying fan constraints. -/
def subset (p q : Sector) : Bool :=
p.spoke.subset q.spoke && p.hat.subset q.hat &&
match p, q with
| _, .basic .. => true
| .six _ f, .six _ g => f.subset g
| .seven _ f₁ f₂, .seven _ g₁ g₂ => f₁.subset g₁ && f₂.subset g₂
| .eight _ f₁ f₂ f₃, .eight _ g₁ g₂ g₃ =>
f₁.subset g₁ && f₂.subset g₂ && f₃.subset g₃
| _, _ => false
end Sector
/-- An ordered, counterclockwise sequence of sectors around the hub face. -/
abbrev Part := List Sector
/-- Executable orbit arity, using Mathlib's bounded finite-cycle decision procedure. -/
def faceArity {n : ℕ} (H : Hypermap n) (x : Fin n) : ℕ :=
(Finset.univ.filter (H.face.SameCycle x)).card
theorem faceArity_eq {n : ℕ} (H : Hypermap n) (x : Fin n) :
faceArity H x = H.faceArity x := by
unfold faceArity Hypermap.faceArity
congr 1
ext y
simp [Hypermap.faceDarts, Hypermap.SameFace]
/-- Local face addressed by a subpart location: 0 is the spoke; 1 is the hat;
2, 3, and 4 are the three possible fans. -/
def localDart {n : ℕ} (H : Hypermap n) (x : Fin n) : ℕ → Fin n
| 0 => H.edge x
| i + 1 => H.edge ((H.face : Fin n → Fin n)^[i + 2] (H.edge x))
namespace Sector
/-- Exact local arity constraints, stated using the original hypermap semantics. -/
def Matches {n : ℕ} (s : Sector) (H : Hypermap n) (x : Fin n) : Prop :=
s.spoke.Contains (H.faceArity (localDart H x 0)) ∧
s.hat.Contains (H.faceArity (localDart H x 1)) ∧
∀ i : Fin s.fans.length, s.fans[i].Contains (H.faceArity (localDart H x (i + 2)))
def matchBool {n : ℕ} (s : Sector) (H : Hypermap n) (x : Fin n) : Bool :=
s.spoke.contains (faceArity H (localDart H x 0)) &&
s.hat.contains (faceArity H (localDart H x 1)) &&
decide (∀ i : Fin s.fans.length,
s.fans[i].Contains (faceArity H (localDart H x (i + 2))))
theorem matches_iff {n : ℕ} (s : Sector) (H : Hypermap n) (x : Fin n) :
s.matchBool H x = true ↔ s.Matches H x := by
simp [matchBool, Matches, faceArity_eq, ArityRange.contains, and_assoc]
end Sector
namespace Part
def rotate (i : ℕ) (p : Part) : Part := p.drop i ++ p.take i
private def mirrorAux (firstHat : ArityRange) (acc : Part) : Part → Part
| [] => acc
| s :: rest =>
let nextHat := match rest with | [] => firstHat | t :: _ => t.hat
mirrorAux firstHat (s.reflect nextHat :: acc) rest
/-- The source's reflection across the first spoke, without changing the hub. -/
def mirror (p : Part) : Part :=
mirrorAux (match p with | [] => .free | s :: _ => s.hat) [] p
/-- Sufficient source-compatible containment of sectors. -/
def subset : Part → Part → Bool
| _, [] => true
| [], _ :: _ => false
| p :: ps, q :: qs => p.subset q && subset ps qs
def sectorFits {n : ℕ} (H : Hypermap n) : Fin n → Part → Prop
| _, [] => True
| x, s :: rest => s.Matches H x ∧ sectorFits H (H.face x) rest
def sectorMatches {n : ℕ} (H : Hypermap n) : Fin n → Part → Bool
| _, [] => true
| x, s :: rest => s.matchBool H x && sectorMatches H (H.face x) rest
/-- Exact matching includes hub arity, rather than merely matching a partial sector. -/
def Matches {n : ℕ} (p : Part) (H : Hypermap n) (x : Fin n) : Prop :=
H.faceArity x = p.length ∧ sectorFits H x p
def matchBool {n : ℕ} (p : Part) (H : Hypermap n) (x : Fin n) : Bool :=
decide (faceArity H x = p.length) && sectorMatches H x p
theorem sectorMatches_iff {n : ℕ} (H : Hypermap n) (x : Fin n) (p : Part) :
sectorMatches H x p = true ↔ sectorFits H x p := by
induction p generalizing x with
| nil => simp [sectorMatches, sectorFits]
| cons s p ih => simp [sectorMatches, sectorFits, Sector.matches_iff, ih]
theorem matches_iff {n : ℕ} (p : Part) (H : Hypermap n) (x : Fin n) :
p.matchBool H x = true ↔ p.Matches H x := by
simp [matchBool, Matches, faceArity_eq, sectorMatches_iff]
end Part
/-- Complete the rule list with source-prescribed reflected patterns.
The rotation is repeated five times, exactly as in `symmetrize_drules`. -/
def symmetrize : List Part → List Part
| [] => []
| p :: rest =>
let reflected := (Part.rotate (p.length - 1))^[5] (Part.mirror p)
let tail := p :: symmetrize rest
if p.subset reflected then tail else reflected :: tail
-- BEGIN GENERATED BASE RULES
/-- The 38 base entries preserve all original multiplicities and specializations. -/
def baseRules : List Part := [
-- drule1
[.basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule1
[.basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule2
[.basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule2'
[.basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule3
[.basic (.exactly 5) ArityRange.free, .basic (.atMost 6) ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule3'
[.basic (.exactly 5) ArityRange.free, .basic (.atMost 6) ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule4
[.basic (.atMost 6) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule4'
[.basic (.atMost 6) ArityRange.free, .basic (.exactly 6) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule5
[.basic (.exactly 6) ArityRange.free, .six (.atMost 6) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule6
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 5) (.atMost 6), .basic (.atLeast 7) (.exactly 5), .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule7
[.basic (.exactly 6) ArityRange.free, .six (.exactly 6) (.atMost 6), .basic (.atLeast 7) (.exactly 5), .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule8
[.basic (.exactly 5) ArityRange.free, .basic (.atMost 6) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule9
[.basic (.atMost 6) ArityRange.free, .basic (.atMost 6) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule10
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule10'
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule11
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule12
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule13
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 8) (.exactly 5), .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule14
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule15
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free],
-- drule16
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free],
-- drule17
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) (.exactly 6), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule18
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.exactly 7) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule19
[.basic (.exactly 6) ArityRange.free, .basic (.atLeast 6) ArityRange.free, .basic (.atLeast 8) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.exactly 6) (.exactly 5), .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free],
-- drule20
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule21
[.basic (.atMost 6) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule22
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free],
-- drule23
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule24
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule25
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .seven ArityRange.free ArityRange.free (.exactly 5), .basic (.exactly 5) (.exactly 6), .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule26
[.basic (.exactly 6) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free],
-- drule27
[.basic (.atLeast 7) ArityRange.free, .basic (.exactly 6) ArityRange.free, .seven (.exactly 6) (.exactly 5) (.atLeast 6), .basic (.exactly 7) ArityRange.free, .basic (.atMost 6) (.exactly 5), .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule28
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule29
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free],
-- drule30
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 6) (.exactly 5), .basic (.exactly 5) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic ArityRange.free ArityRange.free],
-- drule31
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.atLeast 6), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.atLeast 6) ArityRange.free],
-- drule31'
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) (.exactly 5), .basic (.atLeast 6) ArityRange.free, .basic ArityRange.free ArityRange.free, .basic (.atLeast 6) ArityRange.free],
-- drule32
[.basic (.exactly 5) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 7) (.exactly 5), .basic (.atLeast 7) ArityRange.free, .basic (.exactly 6) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free, .basic (.exactly 5) ArityRange.free]
]
def rules : List Part := symmetrize baseRules
theorem baseRules_length : baseRules.length = 38 := by decide
theorem rules_length : rules.length = 71 := by decide
/-- Rule-match count transferred from the face of `x` to that of `edge x`. -/
def transferCount {n : ℕ} (H : Hypermap n) (x : Fin n) : ℕ :=
rules.countP (fun p ↦ p.matchBool H (H.face.symm (H.face.symm x)))
def transfer {n : ℕ} (H : Hypermap n) (x : Fin n) : ℚ :=
transferCount H x
noncomputable def score {n : ℕ} (H : Hypermap n) (x : Fin n) : ℚ :=
H.faceCharge (transfer H) x
-- END GENERATED BASE RULES
open scoped BigOperators
/-- The fixed rule counts obey the generic linear bound when every transfer is at most five.
Source: pinned `discharge.v`, `dscore_cap1`, lines 378–389. -/
theorem score_le_of_transfer_cap {n : ℕ} (H : Hypermap n)
(cap : ∀ y, transferCount H y ≤ 5) (x : Fin n) :
score H x ≤ 60 - 5 * (H.faceArity x : ℚ) := by
have bound (y : Fin n) : transfer H (H.edge y) - transfer H y ≤ 5 := by
have hlo : (0 : ℚ) ≤ transfer H y := by
exact Nat.cast_nonneg _
have hhi : transfer H (H.edge y) ≤ (5 : ℚ) := by
change (transferCount H (H.edge y) : ℚ) ≤ 5
exact_mod_cast cap (H.edge y)
linarith
have hs : (∑ y ∈ H.faceDarts x, (transfer H (H.edge y) - transfer H y)) ≤
(H.faceArity x : ℚ) * 5 := by
calc
_ ≤ ∑ _y ∈ H.faceDarts x, (5 : ℚ) := Finset.sum_le_sum (fun y _ ↦ bound y)
_ = _ := by simp [Hypermap.faceArity]
unfold score Hypermap.faceCharge
linarith
/-- A positive-charge hub has degree at most eleven under the separate transfer cap. -/
theorem positive_score_arity_lt_twelve {n : ℕ} (H : Hypermap n)
(cap : ∀ y, transferCount H y ≤ 5) (x : Fin n) (positive : 0 < score H x) :
H.faceArity x < 12 := by
have h := score_le_of_transfer_cap H cap x
have hc : (H.faceArity x : ℚ) < 12 := by linarith
exact_mod_cast hc
end FourColor.Discharge
Read-back
What the Lean code literally says, in plain math · gpt-6
ArityRange. An arity range is a natural-number lower endpoint and either no upper endpoint or a natural-number upper endpoint . Its data may have ; no consistency condition is built into the structure. Equality of these records is decidable.
ArityRange.Contains. For an arity range and natural number , membership means and, if an upper endpoint exists, . With no upper endpoint only the lower inequality is required. An interval with has no members.
ArityRange.contains and membership decidability. For any range and natural , membership is decidable, and the Boolean membership function returns true exactly for that decision.
ArityRange.free. This is the range with lower endpoint and no upper endpoint; its members are exactly the natural numbers at least .
ArityRange.exactly. For any natural , including , this range has both endpoints and contains exactly .
ArityRange.atLeast. For any natural , this range has lower endpoint and no upper endpoint, so it contains exactly the natural numbers at least .
ArityRange.atMost. For any natural , this range has lower endpoint and upper endpoint , so it contains exactly the naturals between and inclusive. For it is empty.
ArityRange.subset. For ranges , the Boolean test first requires . If has no upper endpoint the remaining test is true. If has an upper endpoint but does not, it is false. If both have upper endpoints, it also requires . There is no separate treatment of inconsistent or empty ranges.
ArityRange.contains_iff. For every range and natural number , its Boolean membership test is true if and only if and every existing upper endpoint of is at least .
ArityRange.subset_sound. For all arity ranges , if their stated endpoint subset test returns true, then every natural number in is in . This is a one-directional implication, including possibly empty ranges; the converse is not asserted.
Sector. A sector is one of four forms: a basic sector containing a spoke range and a hat range ; a six-sector containing a hat range and one fan range; a seven-sector containing a hat range and two ordered fan ranges; or an eight-sector containing a hat range and three ordered fan ranges. The range records may be arbitrary, and sector equality is decidable.
Sector.spoke. The spoke range of is ; that of is the singleton range respectively.
Sector.hat. Each of the four sector forms returns its stored hat range.
Sector.fans. A basic sector has the empty fan list. The other three forms return their stored one, two, or three fan ranges in the listed order.
Sector.reflect. Given any replacement hat range , reflection leaves the sector form and its spoke range unchanged, replaces the old hat range by , and reverses the fan order. Thus becomes , becomes , becomes , and becomes .
Sector.subset. For sectors , the Boolean test requires the endpoint subset test from the spoke of to the spoke of and from the hat of to the hat of . If is basic, there is no fan condition. If both sectors are six-sectors, both seven-sectors, or both eight-sectors, each corresponding ordered fan range must pass the same endpoint subset test. In all other constructor combinations the test is false, even if some range records are empty.
Part. A part is an arbitrary finite ordered list of sectors; the empty list and repetitions are permitted.
faceArity. For every natural , hypermap on , and dart , this is the cardinality of the set of all darts in the same cycle of the face permutation as . A hypermap consists of edge, node, and face permutations with . The arity at a supplied dart is positive; for there is no dart argument.
faceArity_eq. For every finite hypermap and every dart, the finite-cycle count just defined equals the inherited hypermap face arity, which is the cardinality of the same-face dart set.
localDart. For every finite hypermap with edge and face permutations , dart , and natural index , the local dart is when , and when . In particular, the first three are , , and . Iteration indices are natural numbers; the resulting darts need not be distinct.
Sector.Matches. A sector matches at a dart of any finite hypermap if the face arity at local dart lies in its spoke range, the face arity at local dart lies in its hat range, and for every fan-list index the face arity at local dart lies in fan range . Here local dart is and local dart is . For a basic sector the fan condition is vacuous. No distinctness of tested darts is required.
Sector.matchBool. For every sector, finite hypermap, and dart, this Boolean is the conjunction of the spoke, hat, and all fan range-membership tests at those same local darts, using the computable cycle-cardinality version of face arity.
Sector.matches_iff. For every sector, finite hypermap, and dart, the Boolean sector matcher is true if and only if all the spoke, hat, and indexed fan face-arity conditions of Sector.Matches hold.
Part.rotate. For a natural number and a part , the result is the list obtained by deleting its first entries and then appending those first entries. If , including an empty part, the result is itself; the index is not first reduced modulo the length.
Part.mirror and its accumulation helper. For a nonempty part , replace each by its sector reflection with replacement hat equal to the original hat of , then reverse the order of the resulting sectors. The empty part yields the empty part. The recursive helper remembers the first original hat, uses the next original sector's hat except at the last sector, and prepends each reflected sector to an accumulator. Its default first hat for an empty input is the range of naturals at least five and does not create an output sector.
Part.subset. This Boolean list test returns true whenever the target list is empty, irrespective of remaining source entries; it returns false for empty source and nonempty target. For two nonempty lists it requires their first sectors to pass Sector.subset and then recurses on both tails. Thus it compares the full target length against a prefix of the source and may ignore surplus source entries.
Part.sectorFits. For a finite hypermap, dart , and part , this predicate requires to match at for every . Equivalently it is true for an empty list, and for a nonempty list it requires the first sector at and the tail at . It has no condition equating to the face length, so the face orbit can be traversed repeatedly.
Part.sectorMatches. This Boolean is the sequential conjunction of the Boolean sector tests at for the entries of the part. It returns true on the empty part.
Part.Matches. A part matches at a dart of a finite hypermap exactly when the face arity at equals and each successive sector matches at the corresponding dart . An empty part cannot match a supplied dart, since that dart's face cycle contains the dart itself.
Part.matchBool. The Boolean part matcher checks the equality between the computable face-cycle cardinality and the part length, and conjoins the sequential Boolean sector tests.
Part.sectorMatches_iff. For every finite hypermap, dart, and part, sequential Boolean sector matching is true if and only if every indexed sector matches at the corresponding face iterate. This equivalence also includes the empty part, for which both conditions hold.
Part.matches_iff. For every finite hypermap, dart, and part, the Boolean part matcher is true if and only if the face length equals the list length and all the successive sector conditions hold.
symmetrize. For any finite list of parts, process each original part in order. Form by mirroring and then applying Part.rotate with index exactly five times; subtraction here is natural subtraction, so the index is for an empty part. If the part-prefix subset test from to is true, output only at that position. Otherwise output followed by . Continue recursively through the original list, preserving all original multiplicities. The empty input list yields the empty list.
baseRules. This is the following ordered list of 38 parts, with every repeated entry retained. In this table, , , , and are arity ranges. is a basic sector with spoke and hat ; has spoke exactly six, hat , and the one fan ; has spoke exactly seven, hat , and ordered fans . Each table row is one entire ordered part. Rows 1 and 2 are identical and occupy two positions in the list.
| Position | Ordered part |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | |
| 7 | |
| 8 | |
| 9 | |
| 10 | |
| 11 | |
| 12 | |
| 13 | |
| 14 | |
| 15 | |
| 16 | |
| 17 | |
| 18 | |
| 19 | |
| 20 | |
| 21 | |
| 22 | |
| 23 | |
| 24 | |
| 25 | |
| 26 | |
| 27 | |
| 28 | |
| 29 | |
| 30 | |
| 31 | |
| 32 | |
| 33 | |
| 34 | |
| 35 | |
| 36 | |
| 37 | |
| 38 |
rules. This is exactly the list obtained from the specified 38-entry base list by symmetrize: each base part contributes either itself or its computed reflected part followed by itself according to the stated subset test. It is a list with multiplicities, not a set of distinct conditions.
baseRules_length. The length of the specified base-rule list is exactly .
rules_length. The length of the symmetrized rule list is exactly .
transferCount. For any natural , hypermap with face permutation , and dart , the transfer count is the number of positions in the 71-entry rule list whose part matcher accepts at . Thus a rule contributes one for each list occurrence, including repetitions. Part matching requires equality of the tested face length and the part length and all the specified sector arity conditions along that face. The count is a natural number between and ; no admissibility condition is assumed on .
transfer. For every finite hypermap and dart, transfer is its transfer count regarded as a rational number.
score. For any finite hypermap with edge permutation , dart , face-cycle set , face length , and transfer-count function , the rational score is
Here counts, with multiplicity, the rules accepting at the double inverse-face iterate of , and its natural values are cast to rationals. The definition imposes no bound of five on and no planarity or plainness hypothesis.
score_le_of_transfer_cap. For every natural , hypermap on darts, and dart , if for every dart of , then its score as defined by the rational face sum satisfies . The cap is assumed on all darts. No geometric hypothesis on is needed; when there is no choice of .
positive_score_arity_lt_twelve. For every finite hypermap and dart , if every dart's rule-transfer count is at most five and the rational score at is strictly positive, then its face length satisfies the strict inequality . The conclusion follows under precisely that global cap and strict positivity, without an additional face-length lower bound or admissibility assumption.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.