AFTD Auto-Formalizing Theoretical Domains

op1525_two_fixed_points_counterexample

theoremverified

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

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.

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

    lines 17–18

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

    line 19

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

    lines 20–22

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

    line 23

        decide
Equiv.swap
The permutation of a type with decidable equality that swaps two 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 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
See it in the graphDiscuss this resultChallenge it