AFTD Auto-Formalizing Theoretical Domains

signed_graph_cyclic_eight_switch_deck_obstruction

theoremverified

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.

  1. 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).

    lines 9–10

      dsimp only
      constructor
  2. 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.

    line 11

      · decide
  3. It 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).

    line 12

    uses Equiv.swap

      · refine ⟨(Equiv.swap 0 3).trans ((Equiv.swap 1 2).trans ((Equiv.swap 4 7).trans (Equiv.swap 5 6))), ?_⟩
  4. 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.

    line 13

        decide
Equiv.swap
the permutation that swaps two specified elements and leaves all other elements fixed

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

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
See it in the graphDiscuss this resultChallenge it