AFTD Auto-Formalizing Theoretical Domains

op1525_invariant_mono_subset_reconstruct

theoremverifiedoriginal

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

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.

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

    line 8

      cases x <;> cases y <;> cases c <;> decide
  2. 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.

    line 10

      cases a <;> cases b <;> cases c <;> cases d <;> decide
  3. 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.

    lines 15–27

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

    lines 32–42

    uses fresh_of_three

      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).symm
  5. 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.

    lines 46–49

      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
  6. 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).

    lines 54–57

    uses xor_cancel_common

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

    lines 76–83

    uses transfer_mono, flip_outside_mono

      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)
  8. 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.

    line 84

    uses mono_of_two_flips

      have hB : mono S B := mono_of_two_flips S B (π u) (π v) (fun h => huv (π.injective h)) hthree hB1 hB2
  9. 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.

    lines 85–90

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

    lines 91–107

    uses fresh_of_three

      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
  11. 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)).

    lines 108–120

      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]
  12. 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.

    lines 121–122

    uses xor_cancel_flip

      rw [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

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
See it in the graphDiscuss this resultChallenge it