op1525_three_fixed_points_reconstruct
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
- op1525_two_fixed_points_counterexampleOn the disjoint union of two fixed points and a six-point cyclic orbit, the indicated two colorings are not equivalent under a rotation…
- signed_graph_reconstructible_balanced_three_fixedEvery connected balanced signed graph on at least seven vertices is reconstructible from its switching deck if its underlying graph has…
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.
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.
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
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.
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
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.
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]
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.
uses
Finset.card_union_le,Finset.card_image_lehave 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
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.
uses
congrArg,Finset.card_univhave 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
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.
uses
Finset.mem_union_left,Finset.mem_union_right,Finset.mem_image.mprhave 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
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.
uses
op1525_bool_xor_commonobtain ⟨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 _ _ _
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.
uses
Ne.symmobtain ⟨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)
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'.
uses
op1525_bool_xor_cancel_fliprefine ⟨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.
- In Step 8, the deduction that π(r) = r relies on automated case exhaustion over Boolean valuations to show that each alternative anchor assignment contradicts the preserved anchor differences.
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.
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