signed_graph_cyclic_eight_switch_deck_obstruction
On the cyclic group of order eight, take subsets {0,1,3} and {0,2,3}. No rotation or global complement carries one to the other, but there is a bijection of the eight vertices matching their one-vertex switch cards up to rotation and global complement. This is a permutation-group obstruction, not a counterexample for undirected graphs.
Statement
theorem signed_graph_cyclic_eight_switch_deck_obstruction : let a : Fin 8 → Bool := fun i => decide (i = 0 ∨ i = 1 ∨ i = 3) let b : Fin 8 → Bool := fun i => decide (i = 0 ∨ i = 2 ∨ i = 3) let flip : (Fin 8 → Bool) → Fin 8 → Fin 8 → Bool := fun f v i => xor (f i) (decide (i = v)) let equiv : (Fin 8 → Bool) → (Fin 8 → Bool) → Prop := fun f g => ∃ (k : Fin 8) (c : Bool), ∀ i : Fin 8, f (i + k) = xor (g i) c ¬ equiv a b ∧ ∃ p : Equiv.Perm (Fin 8), ∀ v, equiv (flip a v) (flip b (p v))
- Source
- OP-1525, arXiv:2611.13901; obstruction to proving reconstruction for arbitrary permutation groups acting on the balance partition.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The proof shows that the subsets {0, 1, 3} and {0, 2, 3} of the cyclic group ℤ/8ℤ form a switch-deck reconstruction obstruction under rotations and global complementation. First, an exhaustive check confirms that no rotation or complementation maps {0, 1, 3} to {0, 2, 3}. Next, the proof introduces the reflection p(i) = 3 - i (mod 8), written as the product of transpositions (0 3)(1 2)(4 7)(5 6), and verifies by finite exhaustion that flipping any vertex v in the first subset yields a card equivalent to flipping p(v) in the second.
The goal splits into proving that a and b are inequivalent, and exhibiting a permutation of the vertices that matches their one-vertex switch decks.
We simplify the local definitions of the subsets a and b, the vertex-flip operation, and the equivalence relation (equivalence under cyclic shift and global complementation). Splitting the conjunction yields two independent subgoals: showing ¬ equiv a b, and finding a permutation p such that each flipped card flip a v is equivalent to flip b (p v).
dsimp only constructor
The subsets a and b are not equivalent under any cyclic rotation or global complementation. automation
Because Fin 8 and Bool are finite, checking whether any cyclic rotation k ∈ ℤ/8ℤ and boolean complement c ∈ {0, 1} make a(i + k) = b(i) ⊕ c for all i requires testing only 8 × 2 = 16 candidates. The decide tactic evaluates all cases and confirms none works.
· decideIt suffices to show that the permutation p = (0 3)(1 2)(4 7)(5 6) matches each one-vertex switch card of a to the corresponding switch card of b.
We supply the explicit permutation p given by the product of four disjoint transpositions (0 3), (1 2), (4 7), and (5 6), which corresponds geometrically to the reflection i ↦ 3 - i (mod 8). This leaves the remaining obligation to verify that for every vertex v, flip a v is equivalent to flip b (p v).
uses
Equiv.swap· refine ⟨(Equiv.swap 0 3).trans ((Equiv.swap 1 2).trans ((Equiv.swap 4 7).trans (Equiv.swap 5 6))), ?_⟩For every vertex v, the switch card flip a v is equivalent under cyclic rotation and complementation to flip b (p v). automation
For each of the 8 vertices v, verifying equivalence requires finding some shift k ∈ ℤ/8ℤ and boolean c matching flip a v to flip b (p v). The decide tactic searches the 16 possible pairs (k, c) for each vertex and verifies that a matching pair exists for all 8 cards.
decide
Equiv.swap- the permutation that swaps two specified elements and leaves all other elements fixed
- Both the inequivalence of the two subsets and the card-by-card equivalence of their switch decks are verified by finite exhaustive search using Lean's `decide` tactic.
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 signed_graph_cyclic_eight_switch_deck_obstruction : let a : Fin 8 → Bool := fun i => decide (i = 0 ∨ i = 1 ∨ i = 3) let b : Fin 8 → Bool := fun i => decide (i = 0 ∨ i = 2 ∨ i = 3) let flip : (Fin 8 → Bool) → Fin 8 → Fin 8 → Bool := fun f v i => xor (f i) (decide (i = v)) let equiv : (Fin 8 → Bool) → (Fin 8 → Bool) → Prop := fun f g => ∃ (k : Fin 8) (c : Bool), ∀ i : Fin 8, f (i + k) = xor (g i) c ¬ equiv a b ∧ ∃ p : Equiv.Perm (Fin 8), ∀ v, equiv (flip a v) (flip b (p v)) := by dsimp only constructor · decide · refine ⟨(Equiv.swap 0 3).trans ((Equiv.swap 1 2).trans ((Equiv.swap 4 7).trans (Equiv.swap 5 6))), ?_⟩ decide