op1525_two_fixed_points_counterexample
On the disjoint union of two fixed points and a six-point cyclic orbit, the indicated two colorings are not equivalent under a rotation and a global color exchange, but their one-point switch decks can be matched by a bijection under that equivalence. Thus the three-fixed-point reconstruction criterion cannot be weakened to two fixed points for arbitrary permutation actions.
Statement
theorem op1525_two_fixed_points_counterexample : let V := Fin 2 ⊕ Fin 6 let a : V → Bool := fun x => match x with | .inl i => decide (i = 0) | .inr i => decide (i = 0 ∨ i = 1 ∨ i = 3) let b : V → Bool := fun x => match x with | .inl i => decide (i = 1) | .inr i => decide (i = 0 ∨ i = 1 ∨ i = 3) let rot : Fin 6 → V → V := fun k x => match x with | .inl i => .inl i | .inr i => .inr (i + k) let flip : (V → Bool) → V → V → Bool := fun f v i => xor (f i) (decide (i = v)) let equiv : (V → Bool) → (V → Bool) → Prop := fun f g => ∃ (k : Fin 6) (c : Bool), ∀ i : V, f (rot k i) = xor (g i) c ¬ equiv a b ∧ ∃ p : Equiv.Perm V, ∀ v, equiv (flip a v) (flip b (p v))
- Source
- Boundary example for op1525_three_fixed_points_reconstruct and OP-1525; compare arXiv:2611.13901, Section 4.1.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- op1525_three_fixed_points_reconstructLet A and B be Boolean colorings of a finite set V of at least seven points, and let P be any predicate on permutations, all of whose…
The proof, explained
The theorem proves that two colorings a and b on V = Fin 2 ⊕ Fin 6 are not equivalent under rotations and color complementation, yet their one-point switch decks are isomorphic. The colorings agree on the 6-cycle (having the chiral 3-element pattern {0, 1, 3}) but differ on the two fixed points; any equivalence would require color-complementing the 6-cycle, which fails because {0, 1, 3} is not rotationally equivalent to its complement {2, 4, 5}. However, flipping any single vertex on the 6-cycle produces a 2- or 4-element pattern, which is necessarily achiral (reflection-symmetric) on ℤ₆, allowing the decks to be matched by a permutation p that swaps the fixed points and reflects the 6-cycle.
The goal reduces to proving two separate claims: first, that the colorings a and b are not equivalent under rotation and color complementation, and second, that there exists a permutation p of V matching the single-vertex flip of a at each v to that of b at p(v).
We unfold the local definitions of the vertex set V, the colorings a and b, the rotation action, the flip operation, and the equivalence relation using `dsimp only`. We then split the resulting conjunction into two goals using `constructor`.
dsimp only constructor
The colorings a and b are not equivalent under any rotation and boolean color complement. automation
Because the vertex set V = Fin 2 ⊕ Fin 6 is finite, whether there exist a cyclic rotation k ∈ Fin 6 and a complement bit c ∈ Bool satisfying a(rot k i) = xor (b i) c for all i ∈ V is a decidable proposition. The `decide` tactic refutes all 12 pairs (k, c) by exhaustive finite computation.
· decideTo show that the one-point switch decks of a and b can be matched, it suffices to verify the matching for the explicit permutation p of V that swaps the two fixed points and reflects the 6-cycle.
We supply an explicit candidate permutation p ∈ Perm(V) using `refine`. The permutation is constructed by composing four disjoint transpositions: swapping the two fixed points (.inl 0 and .inl 1) and reflecting the 6-cycle via (.inr 0 ↔ .inr 5), (.inr 1 ↔ .inr 4), and (.inr 2 ↔ .inr 3).
uses
Equiv.swap· refine ⟨(Equiv.swap (.inl 0) (.inl 1)).trans ((Equiv.swap (.inr 0) (.inr 5)).trans ((Equiv.swap (.inr 1) (.inr 4)).trans (Equiv.swap (.inr 2) (.inr 3)))), ?_⟩For every vertex v ∈ V, the flipped coloring flip a v is equivalent to flip b (p v). automation
This universal statement over the 8 vertices of V asserts that for each vertex v, there exist a rotation k ∈ Fin 6 and a complement bit c ∈ Bool matching flip a v to flip b (p v). Since all sets and quantifiers are finite, the `decide` tactic verifies the claim by exhaustive evaluation over all vertices and candidate symmetries.
decide
Equiv.swap- The permutation of a type with decidable equality that swaps two elements and leaves all other elements fixed.
- The proof relies on the `decide` tactic to verify both the non-equivalence of the two colorings and the valid matching of their switch decks by exhaustive computation over the finite search space, rather than through symbolic symmetry arguments.
Written by a model (gemini-3.8-flash) from the Lean proof and the goal states Lean reported at each step. Lean verified the proof; this explanation is a reading aid and is not itself machine-checked.
Lean source view module on GitHub
Choose a tactic — a marked line — to see the goals Lean had before and after it, as in Lean’s infoview. Step with ← → or j k.
theorem op1525_two_fixed_points_counterexample : let V := Fin 2 ⊕ Fin 6 let a : V → Bool := fun x => match x with | .inl i => decide (i = 0) | .inr i => decide (i = 0 ∨ i = 1 ∨ i = 3) let b : V → Bool := fun x => match x with | .inl i => decide (i = 1) | .inr i => decide (i = 0 ∨ i = 1 ∨ i = 3) let rot : Fin 6 → V → V := fun k x => match x with | .inl i => .inl i | .inr i => .inr (i + k) let flip : (V → Bool) → V → V → Bool := fun f v i => xor (f i) (decide (i = v)) let equiv : (V → Bool) → (V → Bool) → Prop := fun f g => ∃ (k : Fin 6) (c : Bool), ∀ i : V, f (rot k i) = xor (g i) c ¬ equiv a b ∧ ∃ p : Equiv.Perm V, ∀ v, equiv (flip a v) (flip b (p v)) := by dsimp only constructor · decide · refine ⟨(Equiv.swap (.inl 0) (.inl 1)).trans ((Equiv.swap (.inr 0) (.inr 5)).trans ((Equiv.swap (.inr 1) (.inr 4)).trans (Equiv.swap (.inr 2) (.inr 3)))), ?_⟩ decide