Host reflection and configuration occurrence in either orientation
DefinitionFourColor_ReflectionThe mirror replaces edge, node and face by face composed with node, inverse node and inverse face. Its triangular identity is proved. Occurrence up to reflection is the disjunction of occurrence in the host and in this mirror. Preservation of minimality is a separate theorem. Formalization note: direct source construction and a formal bridge for the source-backed mirror-preservation and configuration-exclusion parent/child targets.
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.1, PDF p. 19, paragraph on PDF p. 19 giving the hypermap identity; Section 5.5, PDF pp. 44–48, configuration-matching and symmetry paragraphs. Relevant displays are unnumbered. Pinned executable reference: https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/hypermap.v#L366-L375; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/coloring.v#L369-L379; https://github.com/rocq-community/fourcolor/blob/c1d6b1cd5288bea4b067aac13cdde3c18dffe018/theories/proof/present.v#L167-L183.
import Definitions.Def_FourColor_Configuration
/-!
Orientation reversal for the configuration occurrence interface.
Source: Gonthier (2005), Section 5.1, PDF pp. 19–20 (permutation maps), and
Section 5.5, PDF pp. 44–48 (configuration matching in discharging).
The exact mirror is pinned Rocq `hypermap.v`, `mirror` (lines 366–369):
edge = face ∘ node, node = node⁻¹, face = face⁻¹. The reflected case is used
explicitly in `present.v`, `no_fit_the_redpart` (lines 176–182).
Preservation of minimal-counterexample structure is a separate theorem; it is
not a field of this definition and is not assumed by an occurrence witness.
-/
namespace FourColor
namespace Hypermap
/-- Reverse the orientation with the precise source convention. -/
def mirror {n : ℕ} (H : Hypermap n) : Hypermap n where
edge := H.node.trans H.face
node := H.node.symm
face := H.face.symm
edge_node_face := by
intro x
simp
end Hypermap
namespace Configuration
/-- A configuration can occur in either orientation of the host. -/
def OccursUpToReflection {n : ℕ} (C : Configuration) (H : Hypermap n) : Prop :=
C.Occurs H ∨ C.Occurs H.mirror
end Configuration
end FourColor
Read-back
What the Lean code literally says, in plain math · gpt-6
Hypermap.mirror. For every natural number and hypermap on , let its edge, node, and face permutations be , with . The mirror is the hypermap on the same dart set with edge permutation , node permutation , and face permutation . These permutations satisfy the required node-after-face-after-edge identity. The definition includes and assumes no planarity, plainness, connectedness, or coloring property.
Configuration.OccursUpToReflection. For every configuration and hypermap on any natural number of darts, occurrence up to reflection means that occurs in or in the mirror with permutations ; the disjunction is inclusive. To expand occurrence, write for , let mean that are in the same source face cycle, and call a kernel dart when its face contains no ring entry. In either alternative, must satisfy the cycle-count identity , where components are generated by the permutation steps and their reversals; have exactly one component; have a fixed-point-free involution and for every dart; have a nonempty ring of pairwise different faces whose listed darts are cyclically permuted by ; have -cycle length three at every dart not listed in the ring; have face lengths between three and six inclusive at each ring entry; and have a kernel dart such that every kernel dart shares an adjacent kernel dart with , where adjacency of means and for some source dart . There must also exist a function into the selected target which commutes with the face permutation and preserves face length at source kernel darts; for each source kernel dart , some satisfies ; and for every ordered pair of kernel darts satisfying that edge equality, there is a finite list of kernel darts satisfying the edge equality such that every consecutive pair in followed by followed by satisfies . The function need not be injective. The contract list has no condition in occurrence. No admissibility property is imposed on the target. Empty source or target dart sets cannot realize occurrence because the required source kernel is nonempty.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.