op1525_mixed_pair_counterexample
There is an eight-point permutation action with two fixed points and an invariant two-point orbit, and two nonequivalent colorings whose one-point switch decks agree. The two-point orbit has different colors, showing why the monochromatic-pair hypothesis cannot simply be dropped in the abstract criterion.
Statement
theorem op1525_mixed_pair_counterexample : let V := Fin 2 ⊕ (Fin 2 ⊕ Fin 4) let a : V → Bool := fun x => match x with | .inl _ => false | .inr (.inl i) => decide (i = 0) | .inr (.inr i) => decide (i = 0 ∨ i = 3) let b : V → Bool := fun x => match x with | .inl _ => false | .inr (.inl i) => decide (i = 1) | .inr (.inr i) => decide (i = 0 ∨ i = 3) let rot : Fin 4 → V → V := fun k x => match x with | .inl i => .inl i | .inr (.inl i) => .inr (.inl (i + if k = 0 ∨ k = 2 then 0 else 1)) | .inr (.inr i) => .inr (.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 4) (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
- A finite obstruction for OP-1525, found by recorded permutation-action computation 24925; this is not a signed-graph counterexample.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext
The proof, explained
The theorem constructs a counterexample showing that the monochromatic-pair hypothesis cannot simply be dropped in the abstract switch reconstruction criterion. On an 8-element set partitioned into two fixed points, an invariant 2-point orbit, and an invariant 4-point orbit under a cyclic action of order 4, two colorings a and b differ only on the 2-point orbit, where they have mixed colors. The proof shows that a and b are not equivalent under rotation and complementation, yet their one-point switch decks coincide via an explicit involution p. Both assertions are verified by finite exhaustive evaluation.
The goal reduces to two separate claims: that the colorings a and b are not equivalent, and that there exists a permutation p of V matching the switch deck of a to that of b.
We unfold the local definitions of the 8-element vertex set V, the colorings a and b, the rotation action, the flip operation, and coloring equivalence, then split the resulting conjunction into two subgoals.
dsimp only constructor
The colorings a and b are not equivalent under any rotation and color complementation. automation
An exhaustive check over all 4 rotation shifts and 2 boolean complementation values confirms that no combination aligns a and b: matching the fixed points forces no complementation, matching the 4-cycle forces the zero rotation, but a and b disagree on the 2-cycle.
· decideTo show that the switch decks of a and b agree, it suffices to verify that for each vertex v, the switch flip(a, v) is equivalent to flip(b, p(v)) under the explicit permutation p.
We supply an explicit permutation p witnessing the existential quantifier. The permutation p is an involution formed by composing four disjoint transpositions: swapping the two fixed points, swapping the two vertices of the 2-cycle, and reflecting the 4-cycle by swapping 0 with 3 and 1 with 2.
uses
Equiv.swap· refine ⟨(Equiv.swap (.inl 0) (.inl 1)).trans ((Equiv.swap (.inr (.inl 0)) (.inr (.inl 1))).trans ((Equiv.swap (.inr (.inr 0)) (.inr (.inr 3))).trans (Equiv.swap (.inr (.inr 1)) (.inr (.inr 2))))), ?_⟩For every vertex v in V, the switched coloring flip(a, v) is equivalent to flip(b, p(v)). automation
An exhaustive check over all 8 vertices confirms that for each v, there exist a rotation shift and complementation bit that map flip(a, v) to flip(b, p(v)).
decide
Equiv.swap- the permutation that swaps two given elements x and y and leaves all other elements fixed
- The proofs of both non-equivalence (line 22) and the deck matching (line 27) are discharged by the `decide` tactic, which evaluates decidable propositions over the finite 8-element domain and the 4-element rotation group by exhaustive computation.
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_mixed_pair_counterexample : let V := Fin 2 ⊕ (Fin 2 ⊕ Fin 4) let a : V → Bool := fun x => match x with | .inl _ => false | .inr (.inl i) => decide (i = 0) | .inr (.inr i) => decide (i = 0 ∨ i = 3) let b : V → Bool := fun x => match x with | .inl _ => false | .inr (.inl i) => decide (i = 1) | .inr (.inr i) => decide (i = 0 ∨ i = 3) let rot : Fin 4 → V → V := fun k x => match x with | .inl i => .inl i | .inr (.inl i) => .inr (.inl (i + if k = 0 ∨ k = 2 then 0 else 1)) | .inr (.inr i) => .inr (.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 4) (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 (.inl 0)) (.inr (.inl 1))).trans ((Equiv.swap (.inr (.inr 0)) (.inr (.inr 3))).trans (Equiv.swap (.inr (.inr 1)) (.inr (.inr 2))))), ?_⟩ decide