AFTD Auto-Formalizing Theoretical Domains

op1525_three_fixed_points_reconstruct

theoremverifiedoriginal

Let A and B be Boolean colorings of a finite set V of at least seven points, and let P be any predicate on permutations, all of whose permitted permutations fix the same three distinct points. Suppose there is a bijection π of V matching every one-point flip of A to the one-point flip of B at π(v), via a permitted permutation and possibly a global color exchange. Then A itself is carried to B, up to a global color exchange, by a permitted permutation. The permitted permutation and color exchange in each card match may depend on v.

Statement

theorem op1525_three_fixed_points_reconstruct
    {V : Type} [DecidableEq V] [Fintype V]
    (A B : V → Bool) (P : Equiv.Perm V → Prop)
    (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)
    (hsize : Fintype.card V ≥ 7)
    (hfix : ∀ g, P g → g r = r ∧ g s = s ∧ g t = t)
    (π : Equiv.Perm V)
    (hdeck : ∀ v, ∃ g, P g ∧ ∃ c : Bool, ∀ x,
      xor (A (g x)) (decide (g x = v)) =
        xor (xor (B x) (decide (x = π v))) c) :
    ∃ g, P g ∧ ∃ c : Bool, ∀ x, A (g x) = xor (B x) c
Related work
The subset-switching form of the balanced signed-graph question OP-1525, arXiv:2611.13901, Section 4.1.
Verified
13 Nov 2026
Axioms
Classical.choiceQuot.soundpropext
Used by 2

Read back from the Lean

Let $V$ be a finite type with decidable equality, and let $A, B : V \to \text{Bool}$ be functions. Let $P$ be a predicate on permutations of $V$ (Equiv.Perm V → Prop). Suppose: 1. $r, s, t \in V$ are pairwise distinct elements ($r \neq s$, $r \neq t$, and $s \neq t$). 2. The cardinality of $V$ is at least 7 (Fintype.card V ≥ 7). 3. Every permutation $g$ of $V$ satisfying $P(g)$ fixes $r$, $s$, and $t$ (that is, $g(r) = r$, $g(s) = s$, and $g(t) = t$). 4. There is a permutation $\pi$ of $V$ such that for every $v \in V$, there exists a permutation $g$ of $V$ satisfying $P(g)$ and a boolean $c \in \text{Bool}$ such that for all $x \in V$: $$\text{xor}(A(g(x)),\, [g(x) = v]) = \text{xor}(\text{xor}(B(x),\, [x = \pi(v)]),\, c)$$ (where $[\cdot]$ denotes decide). Then there exists a permutation $g$ of $V$ satisfying $P(g)$ and a boolean $c \in \text{Bool}$ such that for all $x \in V$: $$A(g(x)) = \text{xor}(B(x),\, c)$$

Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.

The proof, explained

To reconstruct the coloring A from the deck of one-point flips of B under permutations fixing three distinct anchors r, s, t, we first select a point v outside {r, s, t} ∪ π⁻¹({r, s, t}), which exists because |V| ≥ 7 while this bad set has at most 6 elements. Evaluating the card match at v on the three anchors reveals that the relative color differences between the anchors are identical in A and B. Next, evaluating the card match at r and using these preserved differences forces π(r) = r, since otherwise π(r) would have to equal both s and t. Finally, with π(r) = r, the permutation and color exchange associated with the card at r align A and B everywhere on V.

  1. For any Booleans a, b, c, adding a common bit c to both terms cancels out under XOR: (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b. automation

    Proved by exhaustive case analysis over all possible truth values of a, b, c using the decide tactic.

    lines 1–3

    private lemma op1525_bool_xor_common (a b c : Bool) : xor (xor a c) (xor b c) = xor a b := by
      cases a <;> cases b <;> cases c <;> decide
    
  2. For any Booleans a, b, c, if a ⊕ true = (b ⊕ true) ⊕ c, then a = b ⊕ c. automation

    Proved by exhaustive case analysis over all possible truth values of a, b, c using the decide tactic.

    lines 4–7

    private lemma op1525_bool_xor_cancel_flip (a b c : Bool) :
        xor a true = xor (xor b true) c → a = xor b c := by
      cases a <;> cases b <;> cases c <;> decide
    
  3. The anchor set {r, s, t} has cardinality at most 3.

    We define the anchor set {r, s, t} and the bad set {r, s, t} ∪ π⁻¹({r, s, t}). Because the anchors r, s, t are pairwise distinct, the anchor set contains at most three elements.

    lines 8–24

    theorem op1525_three_fixed_points_reconstruct
        {V : Type} [DecidableEq V] [Fintype V]
        (A B : V → Bool) (P : Equiv.Perm V → Prop)
        (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)
        (hsize : Fintype.card V ≥ 7)
        (hfix : ∀ g, P g → g r = r ∧ g s = s ∧ g t = t)
        (π : Equiv.Perm V)
        (hdeck : ∀ v, ∃ g, P g ∧ ∃ c : Bool, ∀ x,
          xor (A (g x)) (decide (g x = v)) =
            xor (xor (B x) (decide (x = π v))) c) :
        ∃ g, P g ∧ ∃ c : Bool, ∀ x, A (g x) = xor (B x) c := by
      classical
      let anchors : Finset V := {r, s, t}
      let bad : Finset V := anchors ∪ anchors.image π.symm
      have ha : anchors.card ≤ 3 := by
        dsimp [anchors]
        simp [hrs, hrt, hst]
  4. The bad set {r, s, t} ∪ π⁻¹({r, s, t}) has cardinality at most 6. automation

    By Finset.card_union_le, the size of a union is at most the sum of the sizes of the two sets. By Finset.card_image_le, the preimage image under π⁻¹ has size at most that of the anchor set, which is at most 3. Linear arithmetic (omega) combines these bounds to show the bad set has size at most 6.

    lines 25–29

    uses Finset.card_union_le, Finset.card_image_le

      have hb : bad.card ≤ 6 := by
        have hu := Finset.card_union_le anchors (anchors.image π.symm)
        have hi := Finset.card_image_le (s := anchors) (f := π.symm)
        dsimp [bad]
        omega
  5. There exists a vertex v ∈ V that is not in the bad set. automation

    Suppose for contradiction that all vertices were in the bad set, so the bad set equals the universe V. Taking cardinalities with congrArg and Finset.card_univ implies |V| ≤ 6, contradicting |V| ≥ 7 via omega. We pick an element v outside the bad set.

    lines 30–39

    uses congrArg, Finset.card_univ

      have hv : ∃ v, v ∉ bad := by
        by_contra h
        push_neg at h
        have he : bad = Finset.univ := by
          ext x
          simp [h x]
        have hc := congrArg Finset.card he
        simp only [Finset.card_univ] at hc
        omega
      obtain ⟨v, hv⟩ := hv
  6. Neither v nor π(v) equals any of the anchors r, s, t.

    Because v is outside the bad set, it cannot belong to the left union summand {r, s, t} (by Finset.mem_union_left), so v ≠ r, s, t. Nor can v belong to the right summand π⁻¹({r, s, t}) (by Finset.mem_union_right). If π(v) were an anchor, v would be in the preimage image by Finset.mem_image.mpr, a contradiction; hence π(v) ≠ r, s, t.

    lines 40–51

    uses Finset.mem_union_left, Finset.mem_union_right, Finset.mem_image.mpr

      have hvn : v ≠ r ∧ v ≠ s ∧ v ≠ t := by
        have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)
        simpa [anchors] using h
      have hvp : π v ≠ r ∧ π v ≠ s ∧ π v ≠ t := by
        have hnot : v ∉ anchors.image π.symm := by
          intro h
          exact hv (Finset.mem_union_right _ h)
        have hp : π v ∉ anchors := by
          intro h
          apply hnot
          exact Finset.mem_image.mpr ⟨π v, h, by simp⟩
        simpa [anchors] using hp
  7. The relative differences between anchors are preserved between A and B: A(r) ⊕ A(s) = B(r) ⊕ B(s) and A(r) ⊕ A(t) = B(r) ⊕ B(t).

    Evaluating the card match at v at each anchor x ∈ {r, s, t}, none of the flip indicators are triggered because neither v nor π(v) is an anchor. Since the permutation fixes all three anchors, this yields A(r) = B(r) ⊕ c, A(s) = B(s) ⊕ c, and A(t) = B(t) ⊕ c. Cancelling the common color flip c with op1525_bool_xor_common gives the preserved differences.

    lines 52–65

    uses op1525_bool_xor_common

      obtain ⟨g, hg, c, hc⟩ := hdeck v
      obtain ⟨hgr, hgs, hgt⟩ := hfix g hg
      have er := hc r
      have es := hc s
      have et := hc t
      simp [hgr, hvn.1.symm, hvp.1.symm] at er
      simp [hgs, hvn.2.1.symm, hvp.2.1.symm] at es
      simp [hgt, hvn.2.2.symm, hvp.2.2.symm] at et
      have hbase1 : xor (A r) (A s) = xor (B r) (B s) := by
        rw [er, es]
        exact op1525_bool_xor_common _ _ _
      have hbase2 : xor (A r) (A t) = xor (B r) (B t) := by
        rw [er, et]
        exact op1525_bool_xor_common _ _ _
  8. The bijection π fixes the anchor r, that is, π(r) = r. automation

    Evaluating the card match at r, we get a permutation g' fixing r, s, t and an offset c'. If π(r) ≠ r, then assuming π(r) ≠ s yields A(r) ⊕ 1 = B(r) ⊕ c' and A(s) = B(s) ⊕ c', which contradicts the preserved difference A(r) ⊕ A(s) = B(r) ⊕ B(s) via Boolean case analysis and Ne.symm; hence π(r) = s. Symmetrically, assuming π(r) ≠ t contradicts A(r) ⊕ A(t) = B(r) ⊕ B(t), forcing π(r) = t. This implies s = π(r) = t, contradicting s ≠ t; hence π(r) = r.

    lines 66–85

    uses Ne.symm

      obtain ⟨g', hg', c', hc'⟩ := hdeck r
      obtain ⟨hg'r, hg's, hg't⟩ := hfix g' hg'
      have e'r := hc' r
      have e's := hc' s
      have e't := hc' t
      have hπr : π r = r := by
        by_contra hn
        have hs : π r = s := by
          by_contra hs
          simp [hg'r, hg's, hrs.symm, Ne.symm hn, Ne.symm hs] at e'r e's
          cases hAr : A r <;> cases hAs : A s <;> cases hBr : B r <;>
            cases hBs : B s <;> cases hcc : c' <;>
              simp [hAr, hAs, hBr, hBs, hcc] at hbase1 e'r e's
        have ht : π r = t := by
          by_contra ht
          simp [hg'r, hg't, hrt.symm, Ne.symm hn, Ne.symm ht] at e'r e't
          cases hAr : A r <;> cases hAt : A t <;> cases hBr : B r <;>
            cases hBt : B t <;> cases hcc : c' <;>
              simp [hAr, hAt, hBr, hBt, hcc] at hbase2 e'r e't
        exact hst (hs.symm.trans ht)
  9. For all x ∈ V, A(g' x) = B(x) ⊕ c', completing the reconstruction of A from B.

    We verify that g' and c' globally align A and B. Because π(r) = r and g' fixes r injectively, g'(x) = r if and only if x = r. When x = r, both flip indicators are true, and cancelling them via op1525_bool_xor_cancel_flip gives A(g' r) = B(r) ⊕ c'. When x ≠ r, neither indicator is true, and the card match equation directly gives A(g' x) = B(x) ⊕ c'.

    lines 86–104

    uses op1525_bool_xor_cancel_flip

      refine ⟨g', hg', c', ?_⟩
      intro x
      have heq := hc' x
      rw [hπr] at heq
      have he : (g' x = r) ↔ x = r := by
        constructor
        · intro h
          apply g'.injective
          simpa [hg'r] using h
        · intro h
          simpa [h] using hg'r
      by_cases hx : x = r
      · have hgx : g' x = r := he.mpr hx
        have h1 : decide (g' x = r) = true := by simp [hgx]
        have h2 : decide (x = r) = true := by simp [hx]
        rw [h1, h2] at heq
        exact op1525_bool_xor_cancel_flip _ _ _ heq
      · have hgx : g' x ≠ r := fun h => hx (he.mp h)
        simpa [hx, hgx] using heq
Finset.card_union_le
The cardinality of the union of two finite sets is at most the sum of their cardinalities: |s ∪ t| ≤ |s| + |t|.
Finset.card_image_le
The cardinality of the image of a finite set under any function is at most the cardinality of the domain set: |f(s)| ≤ |s|.
congrArg
If two arguments are equal, applying any function to them yields equal values: if a₁ = a₂, then f(a₁) = f(a₂).
Finset.card_univ
The cardinality of the universal finset on a finite type equals the cardinality of the type: |Finset.univ| = Fintype.card α.
Finset.mem_union_left
If an element belongs to a finite set s, it belongs to the union s ∪ t.
Finset.mem_union_right
If an element belongs to a finite set t, it belongs to the union s ∪ t.
Finset.mem_image.mpr
If an element a ∈ s satisfies f(a) = b, then b is in the image Finset.image f s.
op1525_bool_xor_common
XORing two Booleans with a common third Boolean preserves their XOR difference: (a ⊕ c) ⊕ (b ⊕ c) = a ⊕ b.
Ne.symm
Inequality is symmetric: if a ≠ b, then b ≠ a.
op1525_bool_xor_cancel_flip
If negating a equals negating b and XORing with c, then a equals b XOR c: (a ⊕ true) = ((b ⊕ true) ⊕ c) → a = b ⊕ c.

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

private lemma op1525_bool_xor_common (a b c : Bool) : xor (xor a c) (xor b c) = xor a b := by  cases a <;> cases b <;> cases c <;> decideprivate lemma op1525_bool_xor_cancel_flip (a b c : Bool) :    xor a true = xor (xor b true) c → a = xor b c := by  cases a <;> cases b <;> cases c <;> decidetheorem op1525_three_fixed_points_reconstruct    {V : Type} [DecidableEq V] [Fintype V]    (A B : V → Bool) (P : Equiv.Perm V → Prop)    (r s t : V) (hrs : r ≠ s) (hrt : r ≠ t) (hst : s ≠ t)    (hsize : Fintype.card V ≥ 7)    (hfix : ∀ g, P g → g r = r ∧ g s = s ∧ g t = t)    (π : Equiv.Perm V)    (hdeck : ∀ v, ∃ g, P g ∧ ∃ c : Bool, ∀ x,      xor (A (g x)) (decide (g x = v)) =        xor (xor (B x) (decide (x = π v))) c) :    ∃ g, P g ∧ ∃ c : Bool, ∀ x, A (g x) = xor (B x) c := by  classical  let anchors : Finset V := {r, s, t}  let bad : Finset V := anchors ∪ anchors.image π.symm  have ha : anchors.card ≤ 3 := by    dsimp [anchors]    simp [hrs, hrt, hst]  have hb : bad.card ≤ 6 := by    have hu := Finset.card_union_le anchors (anchors.image π.symm)    have hi := Finset.card_image_le (s := anchors) (f := π.symm)    dsimp [bad]    omega  have hv : ∃ v, v ∉ bad := by    by_contra h    push_neg at h    have he : bad = Finset.univ := by      ext x      simp [h x]    have hc := congrArg Finset.card he    simp only [Finset.card_univ] at hc    omega  obtain ⟨v, hv⟩ := hv  have hvn : v ≠ r ∧ v ≠ s ∧ v ≠ t := by    have h : v ∉ anchors := fun h => hv (Finset.mem_union_left _ h)    simpa [anchors] using h  have hvp : π v ≠ r ∧ π v ≠ s ∧ π v ≠ t := by    have hnot : v ∉ anchors.image π.symm := by      intro h      exact hv (Finset.mem_union_right _ h)    have hp : π v ∉ anchors := by      intro h      apply hnot      exact Finset.mem_image.mpr ⟨π v, h, by simp⟩    simpa [anchors] using hp  obtain ⟨g, hg, c, hc⟩ := hdeck v  obtain ⟨hgr, hgs, hgt⟩ := hfix g hg  have er := hc r  have es := hc s  have et := hc t  simp [hgr, hvn.1.symm, hvp.1.symm] at er  simp [hgs, hvn.2.1.symm, hvp.2.1.symm] at es  simp [hgt, hvn.2.2.symm, hvp.2.2.symm] at et  have hbase1 : xor (A r) (A s) = xor (B r) (B s) := by    rw [er, es]    exact op1525_bool_xor_common _ _ _  have hbase2 : xor (A r) (A t) = xor (B r) (B t) := by    rw [er, et]    exact op1525_bool_xor_common _ _ _  obtain ⟨g', hg', c', hc'⟩ := hdeck r  obtain ⟨hg'r, hg's, hg't⟩ := hfix g' hg'  have e'r := hc' r  have e's := hc' s  have e't := hc' t  have hπr : π r = r := by    by_contra hn    have hs : π r = s := by      by_contra hs      simp [hg'r, hg's, hrs.symm, Ne.symm hn, Ne.symm hs] at e'r e's      cases hAr : A r <;> cases hAs : A s <;> cases hBr : B r <;>        cases hBs : B s <;> cases hcc : c' <;>          simp [hAr, hAs, hBr, hBs, hcc] at hbase1 e'r e's    have ht : π r = t := by      by_contra ht      simp [hg'r, hg't, hrt.symm, Ne.symm hn, Ne.symm ht] at e'r e't      cases hAr : A r <;> cases hAt : A t <;> cases hBr : B r <;>        cases hBt : B t <;> cases hcc : c' <;>          simp [hAr, hAt, hBr, hBt, hcc] at hbase2 e'r e't    exact hst (hs.symm.trans ht)  refine ⟨g', hg', c', ?_⟩  intro x  have heq := hc' x  rw [hπr] at heq  have he : (g' x = r) ↔ x = r := by    constructor    · intro h      apply g'.injective      simpa [hg'r] using h    · intro h      simpa [h] using hg'r  by_cases hx : x = r  · have hgx : g' x = r := he.mpr hx    have h1 : decide (g' x = r) = true := by simp [hgx]    have h2 : decide (x = r) = true := by simp [hx]    rw [h1, h2] at heq    exact op1525_bool_xor_cancel_flip _ _ _ heq  · have hgx : g' x ≠ r := fun h => hx (he.mp h)    simpa [hx, hgx] using heq
See it in the graphDiscuss this resultChallenge it