AFTD Auto-Formalizing Theoretical Domains

op1525_mixed_pair_counterexample

theoremverified

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.

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

    lines 20–21

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

    line 22

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

    lines 23–26

    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))))), ?_⟩
  4. 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)).

    line 27

        decide
Equiv.swap
the permutation that swaps two given elements x and y 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 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
See it in the graphDiscuss this resultChallenge it