AFTD Auto-Formalizing Theoretical Domains

binary_partial_word_partition_restrict

theoremverified

Fixing one coordinate of a finite partial-word cube partition and retaining the compatible words gives a partition with the same pairwise-conflict property on the remaining coordinates.

Statement

theorem binary_partial_word_partition_restrict {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) (bit : Bool) :
    let J := {i : I // v ∉ s i ∨ b i v = bit}
    let t : J → Finset {w : V // w ≠ v} := fun i =>
      binary_partial_word_restrict_support (s i.val) v
    let c : J → {w : V // w ≠ v} → Bool := fun i w => b i.val w.val
    (∀ i j, i ≠ j → ∃ w ∈ t i ∩ t j, c i w ≠ c j w) ∧
      (univ.biUnion (fun i => binary_partial_word_cube (t i) (c i))) = univ
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 2

The proof, explained

Restricting a partial-word partition of {0, 1}^V to the subcube where coordinate v is fixed to `bit` retains only the cubes compatible with this assignment. Any two distinct surviving cubes must conflict on some coordinate other than v, because if their only conflict were at v, both would have to assign value `bit` there, a contradiction. To see that the surviving restricted cubes cover all assignments on V \ {v}, any such assignment extends uniquely by setting coordinate v to `bit`, and the original partition provides a cube covering this extension which necessarily survives and restricts to cover the original assignment.

  1. It suffices to show that the restricted cubes have the pairwise-conflict property and that their union covers all binary assignments on V \ {v}.

    We open classical logic, simplify the definitions of the restricted index set J, restricted supports t, and restricted partial words c, and split the goal into the two conjuncts: pairwise conflict and covering.

    lines 16–18

      classical
      dsimp only
      constructor
  2. Distinct surviving cubes have distinct original indices, giving a coordinate w where their original partial words conflict.

    Let i and j be distinct indices in J. Since subtype elements with different values have different underlying indices by Subtype.ext, i.val ≠ j.val in I. Applying the pairwise conflict hypothesis hconflict to i.val and j.val yields a coordinate w in the intersection of their supports s(i.val) ∩ s(j.val) on which their bit assignments differ.

    lines 19–20

    uses Subtype.ext

      · intro i j hij
        obtain ⟨w, hw, hbits⟩ := hconflict i.val j.val (fun h => hij (Subtype.ext h))
  3. The conflict coordinate w cannot be the fixed coordinate v.

    Suppose for contradiction that w = v. Then v ∈ s(i.val) ∩ s(j.val), so v belongs to both supports by mem_inter. Because i and j belong to J, each satisfies the survival condition: either v is not in the support or the partial word assigns value `bit` at v. Since v is in both supports, both partial words must assign `bit` at v (using not_not to reject the first disjunct). But this implies b(i.val, v) = b(j.val, v), contradicting the assumption that their values differ at w. Thus w ≠ v.

    lines 21–28

    uses mem_inter, not_not

        have hwv : w ≠ v := by
          intro h
          subst w
          have hi : b i.val v = bit := i.property.resolve_left
            (by simpa only [not_not] using (mem_inter.mp hw).1)
          have hj : b j.val v = bit := j.property.resolve_left
            (by simpa only [not_not] using (mem_inter.mp hw).2)
          exact hbits (hi.trans hj.symm)
  4. The coordinate w, regarded as an element of V \ {v}, witnesses a conflict between the restricted cubes for i and j.

    Since w ≠ v, we can form the subtype element ⟨w, hwv⟩ in {w' : V // w' ≠ v}. Because w ∈ s(i.val) ∩ s(j.val), unfolding the definition binary_partial_word_restrict_support along with mem_inter, mem_filter, mem_univ, and true_and shows that ⟨w, hwv⟩ belongs to the intersection of the restricted supports t(i) ∩ t(j). The restricted bit values c(i, ⟨w, hwv⟩) and c(j, ⟨w, hwv⟩) are b(i.val, w) and b(j.val, w), which are unequal.

    lines 29–31

    uses mem_inter, binary_partial_word_restrict_support, mem_filter, mem_univ, true_and

        refine ⟨⟨w, hwv⟩, ?_, hbits⟩
        simpa only [mem_inter, binary_partial_word_restrict_support, mem_filter, mem_univ,
          true_and] using hw
  5. Any assignment on V \ {v} extends to an assignment on V, which is covered by some cube i from the original partition.

    By binary_partial_word_cube_cover_iff, covering the space of assignments is equivalent to showing every assignment is compatible with some cube. Given an assignment f on {w : V // w ≠ v}, we extend it to ext : V → Bool by setting ext(v) = bit and ext(w) = f(w) for w ≠ v. Because the original cubes cover all assignments on V, there is an index i ∈ I such that ext agrees with b(i) on the entire support s(i).

    lines 32–35

    uses binary_partial_word_cube_cover_iff

      · rw [binary_partial_word_cube_cover_iff]
        intro f
        let ext : V → Bool := fun w => if h : w = v then bit else f ⟨w, h⟩
        obtain ⟨i, hi⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover ext
  6. The covering index i satisfies the survival condition, so i ∈ J.

    We check whether v ∈ s(i). If v ∈ s(i), then since ext agrees with b(i) on s(i), we have b(i, v) = ext(v) = bit using dif_pos. If v ∉ s(i), the first branch of the disjunction holds immediately by Or.inl. In either case, i satisfies the condition to belong to J.

    lines 36–40

    uses dif_pos, Or.inl

        have hisurv : v ∉ s i ∨ b i v = bit := by
          by_cases hv : v ∈ s i
          · right
            simpa only [ext, dif_pos rfl] using (hi v hv).symm
          · exact Or.inl hv
  7. The restricted cube for i covers the assignment f.

    For any w in the restricted support t(i), its underlying element w.val lies in s(i) by mem_filter. The agreement of ext with b(i) on s(i) therefore gives ext(w.val) = b(i, w.val). Since w.val ≠ v by the subtype property of w, ext(w.val) simplifies by dif_neg to f(w). Thus f(w) = b(i, w.val) = c(i, w) for all w in the restricted support, showing that the restricted cube covers f.

    lines 41–45

    uses mem_filter, dif_neg

        refine ⟨⟨i, hisurv⟩, ?_⟩
        intro w hw
        have hwi : w.val ∈ s i := (mem_filter.mp hw).2
        have := hi w.val hwi
        simpa only [ext, dif_neg w.property] using this
Subtype.ext
Two subtype elements are equal if their underlying values are equal.
mem_inter
An element belongs to the intersection of two finite sets if and only if it belongs to both sets.
not_not
Double negation elimination: ¬¬P is equivalent to P.
binary_partial_word_restrict_support
The restricted support of a partial word removing coordinate v, consisting of elements w ≠ v that belong to the original support.
mem_filter
An element belongs to a filtered set if and only if it is in the original set and satisfies the predicate.
mem_univ
Every element of a finite type belongs to the universal finite set Finset.univ.
true_and
Conjunction with True simplifies to the proposition itself: (True ∧ p) = p.
binary_partial_word_cube_cover_iff
A collection of partial-word cubes covers all binary assignments if and only if every total assignment is compatible with at least one partial word.
dif_pos
A dependent if-then-else expression evaluates to its `then` branch when the condition is true.
Or.inl
From a proof of A, deduce the disjunction A ∨ B.
dif_neg
A dependent if-then-else expression evaluates to its `else` branch when the condition is false.

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_restrict {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) (bit : Bool) :    let J := {i : I // v ∉ s i ∨ b i v = bit}    let t : J → Finset {w : V // w ≠ v} := fun i =>      binary_partial_word_restrict_support (s i.val) v    let c : J → {w : V // w ≠ v} → Bool := fun i w => b i.val w.val    (∀ i j, i ≠ j → ∃ w ∈ t i ∩ t j, c i w ≠ c j w) ∧      (univ.biUnion (fun i => binary_partial_word_cube (t i) (c i))) = univ := by  classical  dsimp only  constructor  · intro i j hij    obtain ⟨w, hw, hbits⟩ := hconflict i.val j.val (fun h => hij (Subtype.ext h))    have hwv : w ≠ v := by      intro h      subst w      have hi : b i.val v = bit := i.property.resolve_left        (by simpa only [not_not] using (mem_inter.mp hw).1)      have hj : b j.val v = bit := j.property.resolve_left        (by simpa only [not_not] using (mem_inter.mp hw).2)      exact hbits (hi.trans hj.symm)    refine ⟨⟨w, hwv⟩, ?_, hbits⟩    simpa only [mem_inter, binary_partial_word_restrict_support, mem_filter, mem_univ,      true_and] using hw  · rw [binary_partial_word_cube_cover_iff]    intro f    let ext : V → Bool := fun w => if h : w = v then bit else f ⟨w, h⟩    obtain ⟨i, hi⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover ext    have hisurv : v ∉ s i ∨ b i v = bit := by      by_cases hv : v ∈ s i      · right        simpa only [ext, dif_pos rfl] using (hi v hv).symm      · exact Or.inl hv    refine ⟨⟨i, hisurv⟩, ?_⟩    intro w hw    have hwi : w.val ∈ s i := (mem_filter.mp hw).2    have := hi w.val hwi    simpa only [ext, dif_neg w.property] using this
See it in the graphDiscuss this resultChallenge it