op1525_invariant_mono_subset_reconstruct
Let A and B be Boolean colorings of a set V, and let P be a predicate on permutations of V preserving a subset S. Assume A is constant on S, that S has three distinct points, and that two distinct points lie outside S. Suppose a bijection π matches every one-point flip of A with the flip of B at π(v), up to a permutation allowed by P and a global color exchange, with those choices allowed to vary by card. Then A and B themselves agree up to a permitted permutation and global color exchange. No finiteness or group-closure assumption is needed.
Statement
theorem op1525_invariant_mono_subset_reconstruct {V : Type} [DecidableEq V] (A B : V → Bool) (P : Equiv.Perm V → Prop) (S : Set V) (a b c : V) (ha : a ∈ S) (hb : b ∈ S) (hc : c ∈ S) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (u v : V) (hu : u ∉ S) (hv : v ∉ S) (huv : u ≠ v) (hA : ∀ x ∈ S, ∀ y ∈ S, A x = A y) (hpres : ∀ g, P g → ∀ x, x ∈ S ↔ g x ∈ S) (π : Equiv.Perm V) (hdeck : ∀ w, ∃ g, P g ∧ ∃ d : Bool, ∀ x, xor (A (g x)) (decide (g x = w)) = xor (xor (B x) (decide (x = π w))) d) : ∃ g, P g ∧ ∃ d : Bool, ∀ x, A (g x) = xor (B x) d
- Related work
- A structural reconstruction criterion for the partition-switching model in OP-1525; compare arXiv:2611.13901, Section 4.1.
- Verified
- 13 Nov 2026
- Axioms
Classical.choiceQuot.soundpropext- Used by 1
- signed_graph_reconstructible_balanced_mono_invariantA connected balanced signed graph is reconstructible from its switching deck if its underlying graph has an automorphism-invariant vertex…
Read back from the Lean
Let V be a type with decidable equality. Let A, B : V → Bool be functions, P : Equiv.Perm V → Prop be a predicate on permutations of V, and S : Set V be a subset of V. Assume: 1. There exist three elements a, b, c ∈ S that are pairwise distinct (a ≠ b, a ≠ c, and b ≠ c). 2. There exist two elements u, v ∉ S such that u ≠ v. 3. A is constant on S: for all x ∈ S and y ∈ S, A x = A y. 4. Any permutation satisfying P preserves S: for all g : Equiv.Perm V such that P g holds, and for all x : V, x ∈ S ↔ g x ∈ S. 5. π is a permutation of V (π : Equiv.Perm V). 6. (Deck hypothesis) For every w : V, there exists a permutation g : Equiv.Perm V such that P g holds, and there exists a boolean d : Bool such that for all x : V, xor (A (g x)) (decide (g x = w)) = xor (xor (B x) (decide (x = π w))) d. Then, there exists a permutation g : Equiv.Perm V such that P g holds, and there exists a boolean d : Bool such that for all x : V, A (g x) = xor (B x) d.
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
The reconstruction of coloring A from B proceeds by showing that B must also be constant on the subset S, and then matching the card at a point a ∈ S. First, helper lemmas show that single-point flips outside S preserve constancy on S, and that any coloring having two distinct flips constant on a set of size at least three must itself be constant on that set. By transferring the monochromaticity of two flips of A outside S across the deck bijection, B is shown to be constant on S. Inspecting the deck card at a ∈ S, the preimage q = g⁻¹(a) is forced to equal the flip location π(a) in B, because any discrepancy would contradict the constancy of A and B on S. Finally, with q = π(a), the single-point flips on both sides coincide for every point, and canceling the flip reveals that A ∘ g and B agree everywhere up to a global color flip.
XOR addition with a constant is injective on Booleans. automation
Exhaustive case analysis on all truth values of x, y, and c using the decide tactic confirms that x ⊕ c = y ⊕ c implies x = y.
cases x <;> cases y <;> cases c <;> decide
A common flip term cancels across XOR equations. automation
Exhaustive case analysis on all 16 truth assignments to a, b, c, and d using the decide tactic verifies that a ⊕ d = (b ⊕ d) ⊕ c implies a = b ⊕ c.
cases a <;> cases b <;> cases c <;> cases d <;> decide
Among three distinct points in S, at least one is distinct from any two given points u and v.
By case analysis, if any of the three distinct points a, b, c in S is distinct from both u and v, that point witnesses the existential. If all three failed, each would have to equal u or v, which by the pigeonhole principle contradicts their pairwise distinctness.
by_cases h : a ≠ u ∧ a ≠ v · exact ⟨a, ha, h⟩ by_cases h' : b ≠ u ∧ b ≠ v · exact ⟨b, hb, h'⟩ by_cases h'' : c ≠ u ∧ c ≠ v · exact ⟨c, hc, h''⟩ exfalso push_neg at h h' h'' have ha' : a = u ∨ a = v := by by_cases ht : a = u <;> aesop have hb' : b = u ∨ b = v := by by_cases ht : b = u <;> aesop have hc' : c = u ∨ c = v := by by_cases ht : c = u <;> aesop rcases ha' with ha' | ha' <;> rcases hb' with hb' | hb' <;> rcases hc' with hc' | hc' <;> subst_vars <;> contradiction
If two distinct single-point flips of f are constant on a subset S of at least three points, then f itself is constant on S.
Using fresh_of_three, pick a point z ∈ S distinct from both flip locations u and v. For any x ∈ S, at least one of the two flip locations is not equal to x, so one of the two flipped colorings leaves both x and z untouched, yielding f(x) = f(z). By transitivity through z, f(x) = f(y) for all x, y ∈ S.
uses
fresh_of_threeobtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ := hthree obtain ⟨z, hz, hzu, hzv⟩ := fresh_of_three S a b c ha hb hc hab hac hbc u v have heq (x : V) (hx : x ∈ S) : f x = f z := by by_cases hxu : x = u · have hxv : x ≠ v := by simpa [hxu] using huv have hh := h2 x hx z hz simpa [mono, flip, hxv, hzv] using hh · have hh := h1 x hx z hz simpa [mono, flip, hxu, hzu] using hh intro x hx y hy exact (heq x hx).trans (heq y hy).symm
Flipping f at a point outside S preserves the constancy of f on S.
For any x, y ∈ S, neither x nor y can equal the flip point v outside S, so the flip leaves f(x) and f(y) unchanged.
intro x hx y hy have hxv : x ≠ v := fun h => hv (h ▸ hx) have hyv : y ≠ v := fun h => hv (h ▸ hy) simpa [flip, hxv, hyv] using hf x hx y hy
Permuting and globally flipping a coloring transfers constancy on S.
If g preserves S, then x, y ∈ S implies g(x), g(y) ∈ S, so F(g(x)) = F(g(y)). Since F(g(x)) = H(x) ⊕ c and F(g(y)) = H(y) ⊕ c, xor_cancel_common cancels c to give H(x) = H(y).
uses
xor_cancel_commonintro x hx y hy apply xor_cancel_common _ _ c rw [← heq x, ← heq y] exact hF (g x) ((hpres x).mp hx) (g y) ((hpres y).mp hy)
The single-point flips of B at π(u) and π(v) are both constant on S.
Since u and v lie outside S, flipping A at either point preserves constancy on S by flip_outside_mono. The deck hypothesis provides permutations g₁, g₂ preserving S and color flips d₁, d₂ relating these cards to the flips of B at π(u) and π(v). By transfer_mono, both of these flipped B colorings are constant on S.
uses
transfer_mono,flip_outside_monohave hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c := ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ obtain ⟨g1, hg1, d1, heq1⟩ := hdeck u obtain ⟨g2, hg2, d2, heq2⟩ := hdeck v have hB1 : mono S (flip B (π u)) := transfer_mono S _ _ g1 d1 (hpres g1 hg1) heq1 (flip_outside_mono S A u hA hu) have hB2 : mono S (flip B (π v)) := transfer_mono S _ _ g2 d2 (hpres g2 hg2) heq2 (flip_outside_mono S A v hA hv)
The coloring B is constant on S.
Since π is injective and u ≠ v, π(u) and π(v) are distinct. Because S contains three distinct points and two distinct single-point flips of B are constant on S, mono_of_two_flips implies that B is constant on S.
uses
mono_of_two_flipshave hB : mono S B := mono_of_two_flips S B (π u) (π v) (fun h => huv (π.injective h)) hthree hB1 hB2
The deck card at a ∈ S yields a candidate permutation g and color flip d, with preimage q = g⁻¹(a) lying in S.
Evaluating the deck hypothesis at a ∈ S yields a permutation g satisfying P and a global flip d. Setting q = g⁻¹(a), we have g(q) = a. Since a ∈ S and g preserves S, q must also belong to S.
obtain ⟨g, hg, d, heq⟩ := hdeck a let q := g.symm a have hgq : g q = a := by simp [q] have hq : q ∈ S := by apply (hpres g hg q).mpr simpa [hgq] using ha
The preimage q must equal the deck flip point π(a).
Suppose for contradiction that q ≠ π(a). By fresh_of_three, there is a third point z ∈ S distinct from both q and π(a). Since g is injective and preserves S, g(z) ∈ S and g(z) ≠ a. Because A and B are constant on S, A(g(z)) = A(a) and B(q) = B(z). Evaluating the card relation at q gives ¬A(a) = B(z) ⊕ d, while evaluating at z gives A(a) = B(z) ⊕ d, which forces ¬A(a) = A(a), a contradiction.
uses
fresh_of_threehave hmatch : q = π a := by by_contra hne obtain ⟨z, hz, hzq, hzw⟩ := fresh_of_three S a b c ha hb hc hab hac hbc q (π a) have hgzS : g z ∈ S := (hpres g hg z).mp hz have hgz : g z ≠ a := by intro he apply hzq apply g.injective simpa [hgq] using he have hAz : A (g z) = A a := hA (g z) hgzS a ha have hBqz : B q = B z := hB q hq z hz have hqeq := heq q have hzeq := heq z simp [hgq, hne, hBqz] at hqeq simp [hgz, hzw, hAz] at hzeq cases hAa : A a <;> cases hBz : B z <;> cases hd : d <;> simp [hAa, hBz, hd] at hqeq hzeq
For every element x, the condition g(x) = a is equivalent to x = π(a).
We propose (g, d) as the witness. Since g is injective, g(x) = a = g(q) if and only if x = q. Because q = π(a), this is equivalent to x = π(a), so decide(g(x) = a) equals decide(x = π(a)).
refine ⟨g, hg, d, ?_⟩ intro x have hEq := heq x have hpred : (g x = a) ↔ x = π a := by constructor · intro h have hsame : g x = g q := h.trans hgq.symm exact (g.injective hsame).trans hmatch · intro h subst x simpa [hmatch] using hgq have hdec : decide (g x = a) = decide (x = π a) := by simp only [hpred]
For every x, A(g(x)) = B(x) ⊕ d, completing the reconstruction.
Substituting decide(g(x) = a) = decide(x = π(a)) into the card equation at x gives A(g(x)) ⊕ D = (B(x) ⊕ D) ⊕ d, where D is the indicator. By xor_cancel_flip, the flip D cancels from both sides, yielding A(g(x)) = B(x) ⊕ d.
uses
xor_cancel_fliprw [hdec] at hEq exact xor_cancel_flip _ _ _ _ hEq
xor_cancel_common- XOR addition with a Boolean constant c is injective: if x ⊕ c = y ⊕ c, then x = y.
xor_cancel_flip- If a ⊕ d = (b ⊕ d) ⊕ c for Booleans, then a = b ⊕ c, canceling the common flip d.
fresh_of_three- Given three distinct points in a subset S and any two points u and v, at least one of the three points in S is distinct from both u and v.
mono_of_two_flips- If a subset S contains at least three distinct points and two distinct single-point flips of a coloring f are both constant on S, then f itself is constant on S.
flip_outside_mono- Flipping a coloring at a point outside a subset S preserves the property of being constant on S.
transfer_mono- If a permutation preserves a subset S and maps a coloring F to a coloring H up to a global color flip, and F is constant on S, then H is constant on S.
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.
namespace OP1525Monovariable {V : Type} [DecidableEq V]def flip (f : V → Bool) (v x : V) : Bool := xor (f x) (decide (x = v))def mono (S : Set V) (f : V → Bool) : Prop := ∀ x ∈ S, ∀ y ∈ S, f x = f ylemma xor_cancel_common (x y c : Bool) : xor x c = xor y c → x = y := by cases x <;> cases y <;> cases c <;> decidelemma xor_cancel_flip (a b c d : Bool) : xor a d = xor (xor b d) c → a = xor b c := by cases a <;> cases b <;> cases c <;> cases d <;> decidelemma fresh_of_three (S : Set V) (a b c : V) (ha : a ∈ S) (hb : b ∈ S) (hc : c ∈ S) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (u v : V) : ∃ z ∈ S, z ≠ u ∧ z ≠ v := by by_cases h : a ≠ u ∧ a ≠ v · exact ⟨a, ha, h⟩ by_cases h' : b ≠ u ∧ b ≠ v · exact ⟨b, hb, h'⟩ by_cases h'' : c ≠ u ∧ c ≠ v · exact ⟨c, hc, h''⟩ exfalso push_neg at h h' h'' have ha' : a = u ∨ a = v := by by_cases ht : a = u <;> aesop have hb' : b = u ∨ b = v := by by_cases ht : b = u <;> aesop have hc' : c = u ∨ c = v := by by_cases ht : c = u <;> aesop rcases ha' with ha' | ha' <;> rcases hb' with hb' | hb' <;> rcases hc' with hc' | hc' <;> subst_vars <;> contradictionlemma mono_of_two_flips (S : Set V) (f : V → Bool) (u v : V) (huv : u ≠ v) (hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c) (h1 : mono S (flip f u)) (h2 : mono S (flip f v)) : mono S f := by obtain ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ := hthree obtain ⟨z, hz, hzu, hzv⟩ := fresh_of_three S a b c ha hb hc hab hac hbc u v have heq (x : V) (hx : x ∈ S) : f x = f z := by by_cases hxu : x = u · have hxv : x ≠ v := by simpa [hxu] using huv have hh := h2 x hx z hz simpa [mono, flip, hxv, hzv] using hh · have hh := h1 x hx z hz simpa [mono, flip, hxu, hzu] using hh intro x hx y hy exact (heq x hx).trans (heq y hy).symmlemma flip_outside_mono (S : Set V) (f : V → Bool) (v : V) (hf : mono S f) (hv : v ∉ S) : mono S (flip f v) := by intro x hx y hy have hxv : x ≠ v := fun h => hv (h ▸ hx) have hyv : y ≠ v := fun h => hv (h ▸ hy) simpa [flip, hxv, hyv] using hf x hx y hylemma transfer_mono (S : Set V) (F H : V → Bool) (g : Equiv.Perm V) (c : Bool) (hpres : ∀ x, x ∈ S ↔ g x ∈ S) (heq : ∀ x, F (g x) = xor (H x) c) (hF : mono S F) : mono S H := by intro x hx y hy apply xor_cancel_common _ _ c rw [← heq x, ← heq y] exact hF (g x) ((hpres x).mp hx) (g y) ((hpres y).mp hy)end OP1525Monoopen OP1525Monotheorem op1525_invariant_mono_subset_reconstruct {V : Type} [DecidableEq V] (A B : V → Bool) (P : Equiv.Perm V → Prop) (S : Set V) (a b c : V) (ha : a ∈ S) (hb : b ∈ S) (hc : c ∈ S) (hab : a ≠ b) (hac : a ≠ c) (hbc : b ≠ c) (u v : V) (hu : u ∉ S) (hv : v ∉ S) (huv : u ≠ v) (hA : ∀ x ∈ S, ∀ y ∈ S, A x = A y) (hpres : ∀ g, P g → ∀ x, x ∈ S ↔ g x ∈ S) (π : Equiv.Perm V) (hdeck : ∀ w, ∃ g, P g ∧ ∃ d : Bool, ∀ x, xor (A (g x)) (decide (g x = w)) = xor (xor (B x) (decide (x = π w))) d) : ∃ g, P g ∧ ∃ d : Bool, ∀ x, A (g x) = xor (B x) d := by have hthree : ∃ a ∈ S, ∃ b ∈ S, ∃ c ∈ S, a ≠ b ∧ a ≠ c ∧ b ≠ c := ⟨a, ha, b, hb, c, hc, hab, hac, hbc⟩ obtain ⟨g1, hg1, d1, heq1⟩ := hdeck u obtain ⟨g2, hg2, d2, heq2⟩ := hdeck v have hB1 : mono S (flip B (π u)) := transfer_mono S _ _ g1 d1 (hpres g1 hg1) heq1 (flip_outside_mono S A u hA hu) have hB2 : mono S (flip B (π v)) := transfer_mono S _ _ g2 d2 (hpres g2 hg2) heq2 (flip_outside_mono S A v hA hv) have hB : mono S B := mono_of_two_flips S B (π u) (π v) (fun h => huv (π.injective h)) hthree hB1 hB2 obtain ⟨g, hg, d, heq⟩ := hdeck a let q := g.symm a have hgq : g q = a := by simp [q] have hq : q ∈ S := by apply (hpres g hg q).mpr simpa [hgq] using ha have hmatch : q = π a := by by_contra hne obtain ⟨z, hz, hzq, hzw⟩ := fresh_of_three S a b c ha hb hc hab hac hbc q (π a) have hgzS : g z ∈ S := (hpres g hg z).mp hz have hgz : g z ≠ a := by intro he apply hzq apply g.injective simpa [hgq] using he have hAz : A (g z) = A a := hA (g z) hgzS a ha have hBqz : B q = B z := hB q hq z hz have hqeq := heq q have hzeq := heq z simp [hgq, hne, hBqz] at hqeq simp [hgz, hzw, hAz] at hzeq cases hAa : A a <;> cases hBz : B z <;> cases hd : d <;> simp [hAa, hBz, hd] at hqeq hzeq refine ⟨g, hg, d, ?_⟩ intro x have hEq := heq x have hpred : (g x = a) ↔ x = π a := by constructor · intro h have hsame : g x = g q := h.trans hgq.symm exact (g.injective hsame).trans hmatch · intro h subst x simpa [hmatch] using hgq have hdec : decide (g x = a) = decide (x = π a) := by simp only [hpred] rw [hdec] at hEq exact xor_cancel_flip _ _ _ _ hEq