AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_twins

theoremverified

If a coordinate appears in exactly two parts of a Boolean cube partition, once at each value, those parts have equal supports and agree at every other supported coordinate.

Statement

theorem binary_partial_word_partition_twins
    {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V]
    (s : I → Finset V) (b : I → V → Bool)
    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)
    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)
    (v : V) (hsing : ∀ bit : Bool,
      (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1) :
    ∃ i₀ i₁ : I, i₀ ≠ i₁ ∧ v ∈ s i₀ ∧ b i₀ v = false ∧
      v ∈ s i₁ ∧ b i₁ v = true ∧
      (∀ i, v ∈ s i → i = i₀ ∨ i = i₁) ∧ s i₀ = s i₁ ∧
      (∀ w ∈ s i₀, w ≠ v → b i₀ w = b i₁ w)
Source
Reusable finite-cube and ordered-biclique helpers for the uniform OP-205 / RT-1 full-root-gap reduction following arXiv:2610.15635. The deficiency-one singular-coordinate/tree argument formalizes the Boolean setting of arXiv:1103.3693 Lemma 2.5.4 and Corollary 2.5.6; arXiv:2212.14685 Section 2.3 gives a related partition-size discussion. These are helper formalizations, not an original graph covering result; no advance is claimed.
Verified
27 Oct 2026
Axioms
Classical.choiceQuot.soundpropext
Built on 3
Used by 1

The proof, explained

To show that two parts restricting coordinate v are twins, the proof first isolates their indices i₀ and i₁ and confirms that no other part restricts v. The pivotal move is a flipping lemma: flipping coordinate v in any word of cube i₀ must land in cube i₁ because the partition covers the full cube and pairwise conflict prevents any other part from containing the flipped word. This flipping property implies that neither cube can have a supported coordinate missing from the other, proving equal supports. Finally, flipping v on the pattern of i₀ itself forces the two parts to agree on all other supported coordinates.

  1. There exist unique indices i₀ and i₁ whose parts restrict coordinate v to false and true, respectively.

    By the assumption that exactly one part restricts v to each bit, we extract the unique witness i₀ for false and the unique witness i₁ for true from the singleton filters.

    lines 16–24

    uses card_eq_one, mem_filter

      classical
      obtain ⟨i₀, hi₀⟩ := card_eq_one.mp (hsing false)
      obtain ⟨i₁, hi₁⟩ := card_eq_one.mp (hsing true)
      have hzero : v ∈ s i₀ ∧ b i₀ v = false := by
        have : i₀ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = false) := by rw [hi₀]; simp
        exact (mem_filter.mp this).2
      have hone : v ∈ s i₁ ∧ b i₁ v = true := by
        have : i₁ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = true) := by rw [hi₁]; simp
        exact (mem_filter.mp this).2
  2. The indices i₀ and i₁ are distinct.

    If i₀ = i₁, the pattern value at coordinate v would have to be false and true simultaneously, which is impossible.

    lines 25–29

      have hne : i₀ ≠ i₁ := by
        intro he
        have : b i₀ v = true := he ▸ hone.2
        rw [hzero.2] at this
        contradiction
  3. Any part restricting coordinate v must be either i₀ or i₁.

    For any part i restricting v, its bit at v is either false or true. In either case, i belongs to the corresponding singleton filter, forcing i = i₀ or i = i₁.

    lines 30–39

    uses mem_filter, mem_univ, mem_singleton

      have huniq (i : I) (hvi : v ∈ s i) : i = i₀ ∨ i = i₁ := by
        cases hbit : b i v
        · left
          have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = false) :=
            mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩
          simpa only [hi₀, mem_singleton] using this
        · right
          have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = true) :=
            mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩
          simpa only [hi₁, mem_singleton] using this
  4. Flipping coordinate v in any word belonging to cube a ∈ {i₀, i₁} yields a word in the opposite cube d.

    Because the subcubes cover the entire Boolean cube, the flipped word g must belong to some cube j. It cannot be cube a because its bit at v has been inverted. Furthermore, j must restrict coordinate v: if it did not, pairwise disjointness would force a conflict with a at some coordinate w ≠ v, but g agrees with cube a outside v, a contradiction. Since j restricts v and j ≠ a, uniqueness implies j = d.

    lines 40–64

    uses binary_partial_word_cube_cover_iff, binary_partial_word_cube_mem, Function.update_self, mem_inter, Function.update_of_ne

      have hflip (a d : I) (had : a ≠ d) (hva : v ∈ s a) (hvd : v ∈ s d)
          (hopp : b d v = !(b a v))
          (honly : ∀ j, v ∈ s j → j = a ∨ j = d) :
          ∀ f, f ∈ binary_partial_word_cube (s a) (b a) →
            Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d) := by
        intro f hf
        let g := Function.update f v (!f v)
        obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover g
        have hfv : f v = b a v := (binary_partial_word_cube_mem _ _ _).mp hf v hva
        have hja : j ≠ a := by
          intro he
          subst j
          have heq := hj v hva
          have hnot : (!f v) ≠ f v := by cases f v <;> decide
          exact hnot (by simpa only [g, Function.update_self, ← hfv] using heq)
        have hvj : v ∈ s j := by
          by_contra hn
          obtain ⟨w, hw, hbits⟩ := hconflict a j hja.symm
          have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2
          have he := hj w (mem_inter.mp hw).2
          have hfa := (binary_partial_word_cube_mem _ _ _).mp hf w (mem_inter.mp hw).1
          exact hbits (hfa.symm.trans (by simpa only [g, Function.update_of_ne hwv] using he))
        have hjd : j = d := (honly j hvj).resolve_left hja
        subst j
        exact (binary_partial_word_cube_mem _ _ _).mpr hj
  5. Flipping coordinate v maps cube i₀ into cube i₁ and vice versa.

    We specialize the flipping lemma to the pairs (i₀, i₁) and (i₁, i₀), establishing the flipping property in both directions.

    lines 65–67

      have hf₀ := hflip i₀ i₁ hne hzero.1 hone.1 (by simp [hzero.2, hone.2]) huniq
      have hf₁ := hflip i₁ i₀ hne.symm hone.1 hzero.1 (by simp [hzero.2, hone.2])
        (fun j hj => (huniq j hj).symm)
  6. If flipping coordinate v maps cube a into cube d, then the support of d is contained in that of a (s d ⊆ s a).

    Suppose some coordinate w ∈ s d were not in s a. Since v ∈ s a, w ≠ v. We can construct a word in cube a whose value at w disagrees with cube d. Flipping v produces a word in cube d, which must match cube d at w, contradicting our construction because w ≠ v was untouched by the flip.

    lines 68–84

    uses binary_partial_word_cube_mem, Function.update_of_ne, Function.update_self

      have hsub (a d : I)
          (hflipad : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) →
            Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d))
          (hva : v ∈ s a) : s d ⊆ s a := by
        intro w hwd
        by_contra hwa
        have hwv : w ≠ v := by rintro rfl; exact hwa hva
        let f := Function.update (b a) w (!(b d w))
        have hf : f ∈ binary_partial_word_cube (s a) (b a) := by
          rw [binary_partial_word_cube_mem]
          intro u hu
          have huw : u ≠ w := by rintro rfl; exact hwa hu
          simp only [f, Function.update_of_ne huw]
        have hgd := hflipad f hf
        have he := (binary_partial_word_cube_mem _ _ _).mp hgd w hwd
        have hnot : (!(b d w)) ≠ b d w := by cases b d w <;> decide
        exact hnot (by simpa only [Function.update_of_ne hwv, f, Function.update_self] using he)
  7. The supports of i₀ and i₁ are equal (s i₀ = s i₁).

    Mutual inclusion s i₁ ⊆ s i₀ and s i₀ ⊆ s i₁ follows from the support inclusion lemma applied to both directions, so s i₀ = s i₁ by antisymmetry.

    line 85

      have hsupport : s i₀ = s i₁ := (hsub i₁ i₀ hf₁ hone.1).antisymm (hsub i₀ i₁ hf₀ hzero.1)
  8. The witnesses i₀ and i₁ satisfy all required properties, and their patterns agree on all supported coordinates other than v.

    Providing the witnesses and previously proved properties leaves only checking agreement at other coordinates w ≠ v in s i₀. The pattern b i₀ itself belongs to cube i₀. Flipping coordinate v yields a word in cube i₁, which must match b i₁ at w. Since w ≠ v, the flip leaves coordinate w unchanged, forcing b i₀ w = b i₁ w.

    lines 86–92

    uses binary_partial_word_cube_mem, Function.update_of_ne

      refine ⟨i₀, i₁, hne, hzero.1, hzero.2, hone.1, hone.2, huniq, hsupport, ?_⟩
      intro w hw hwv
      have hbmem : b i₀ ∈ binary_partial_word_cube (s i₀) (b i₀) :=
        (binary_partial_word_cube_mem _ _ _).mpr (fun u hu => rfl)
      have hgd := hf₀ (b i₀) hbmem
      have he := (binary_partial_word_cube_mem _ _ _).mp hgd w (hsupport ▸ hw)
      simpa only [Function.update_of_ne hwv] using he
card_eq_one
A finite set has cardinality 1 if and only if it is a singleton set {a} for some element a.
mem_filter
An element belongs to filter p s if and only if it belongs to s and satisfies the predicate p.
mem_univ
Every element of a finite type belongs to the universal finset univ.
mem_singleton
An element belongs to the singleton set {a} if and only if it equals a.
binary_partial_word_cube_cover_iff
A family of partial word subcubes covers the entire Boolean cube if and only if every Boolean word matches some part on its support.
binary_partial_word_cube_mem
A Boolean word f belongs to the subcube defined by support s and pattern b if and only if f agrees with b on all coordinates in s.
Function.update_self
Evaluating an updated function at the modified input yields the new value.
mem_inter
An element belongs to the intersection of two sets if and only if it belongs to both sets.
Function.update_of_ne
Evaluating an updated function at an input distinct from the updated point leaves its value unchanged.

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

open Finsetset_option maxHeartbeats 1000000set_option maxRecDepth 4000theorem binary_partial_word_partition_twins    {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V]    (s : I → Finset V) (b : I → V → Bool)    (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v)    (hcover : (univ.biUnion (fun i => binary_partial_word_cube (s i) (b i))) = univ)    (v : V) (hsing : ∀ bit : Bool,      (univ.filter (fun i => v ∈ s i ∧ b i v = bit)).card = 1) :    ∃ i₀ i₁ : I, i₀ ≠ i₁ ∧ v ∈ s i₀ ∧ b i₀ v = false ∧      v ∈ s i₁ ∧ b i₁ v = true ∧      (∀ i, v ∈ s i → i = i₀ ∨ i = i₁) ∧ s i₀ = s i₁ ∧      (∀ w ∈ s i₀, w ≠ v → b i₀ w = b i₁ w) := by  classical  obtain ⟨i₀, hi₀⟩ := card_eq_one.mp (hsing false)  obtain ⟨i₁, hi₁⟩ := card_eq_one.mp (hsing true)  have hzero : v ∈ s i₀ ∧ b i₀ v = false := by    have : i₀ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = false) := by rw [hi₀]; simp    exact (mem_filter.mp this).2  have hone : v ∈ s i₁ ∧ b i₁ v = true := by    have : i₁ ∈ univ.filter (fun i => v ∈ s i ∧ b i v = true) := by rw [hi₁]; simp    exact (mem_filter.mp this).2  have hne : i₀ ≠ i₁ := by    intro he    have : b i₀ v = true := he ▸ hone.2    rw [hzero.2] at this    contradiction  have huniq (i : I) (hvi : v ∈ s i) : i = i₀ ∨ i = i₁ := by    cases hbit : b i v    · left      have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = false) :=        mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩      simpa only [hi₀, mem_singleton] using this    · right      have : i ∈ univ.filter (fun j => v ∈ s j ∧ b j v = true) :=        mem_filter.mpr ⟨mem_univ _, hvi, hbit⟩      simpa only [hi₁, mem_singleton] using this  have hflip (a d : I) (had : a ≠ d) (hva : v ∈ s a) (hvd : v ∈ s d)      (hopp : b d v = !(b a v))      (honly : ∀ j, v ∈ s j → j = a ∨ j = d) :      ∀ f, f ∈ binary_partial_word_cube (s a) (b a) →        Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d) := by    intro f hf    let g := Function.update f v (!f v)    obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover g    have hfv : f v = b a v := (binary_partial_word_cube_mem _ _ _).mp hf v hva    have hja : j ≠ a := by      intro he      subst j      have heq := hj v hva      have hnot : (!f v) ≠ f v := by cases f v <;> decide      exact hnot (by simpa only [g, Function.update_self, ← hfv] using heq)    have hvj : v ∈ s j := by      by_contra hn      obtain ⟨w, hw, hbits⟩ := hconflict a j hja.symm      have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2      have he := hj w (mem_inter.mp hw).2      have hfa := (binary_partial_word_cube_mem _ _ _).mp hf w (mem_inter.mp hw).1      exact hbits (hfa.symm.trans (by simpa only [g, Function.update_of_ne hwv] using he))    have hjd : j = d := (honly j hvj).resolve_left hja    subst j    exact (binary_partial_word_cube_mem _ _ _).mpr hj  have hf₀ := hflip i₀ i₁ hne hzero.1 hone.1 (by simp [hzero.2, hone.2]) huniq  have hf₁ := hflip i₁ i₀ hne.symm hone.1 hzero.1 (by simp [hzero.2, hone.2])    (fun j hj => (huniq j hj).symm)  have hsub (a d : I)      (hflipad : ∀ f, f ∈ binary_partial_word_cube (s a) (b a) →        Function.update f v (!f v) ∈ binary_partial_word_cube (s d) (b d))      (hva : v ∈ s a) : s d ⊆ s a := by    intro w hwd    by_contra hwa    have hwv : w ≠ v := by rintro rfl; exact hwa hva    let f := Function.update (b a) w (!(b d w))    have hf : f ∈ binary_partial_word_cube (s a) (b a) := by      rw [binary_partial_word_cube_mem]      intro u hu      have huw : u ≠ w := by rintro rfl; exact hwa hu      simp only [f, Function.update_of_ne huw]    have hgd := hflipad f hf    have he := (binary_partial_word_cube_mem _ _ _).mp hgd w hwd    have hnot : (!(b d w)) ≠ b d w := by cases b d w <;> decide    exact hnot (by simpa only [Function.update_of_ne hwv, f, Function.update_self] using he)  have hsupport : s i₀ = s i₁ := (hsub i₁ i₀ hf₁ hone.1).antisymm (hsub i₀ i₁ hf₀ hzero.1)  refine ⟨i₀, i₁, hne, hzero.1, hzero.2, hone.1, hone.2, huniq, hsupport, ?_⟩  intro w hw hwv  have hbmem : b i₀ ∈ binary_partial_word_cube (s i₀) (b i₀) :=    (binary_partial_word_cube_mem _ _ _).mpr (fun u hu => rfl)  have hgd := hf₀ (b i₀) hbmem  have he := (binary_partial_word_cube_mem _ _ _).mp hgd w (hsupport ▸ hw)  simpa only [Function.update_of_ne hwv] using he
See it in the graphDiscuss this resultChallenge it