binary_partial_word_partition_restrict
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
- binary_partial_word_cubeThe finite Boolean cube determined by fixing the coordinates of a finite support to the values of a Boolean word.
- binary_partial_word_cube_cover_iffA family of partial-word cubes covers the whole Boolean cube exactly when every Boolean assignment agrees with one of the partial words on…
- binary_partial_word_restrict_supportRestrict the support of a partial word to the coordinate subtype excluding one specified coordinate.
- Used by 2
- binary_partial_word_partition_order_convexIn a finite Boolean cube partition with one more part than mentioned coordinates, linearly order the parts so that every false occurrence…
- binary_partial_word_partition_singular_coordinateA finite Boolean cube partition mentioning every coordinate and having exactly one more part than coordinates, with a nonempty coordinate…
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.
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.
classical dsimp only constructor
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.
uses
Subtype.ext· intro i j hij obtain ⟨w, hw, hbits⟩ := hconflict i.val j.val (fun h => hij (Subtype.ext h))
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.
uses
mem_inter,not_nothave 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)
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.
uses
mem_inter,binary_partial_word_restrict_support,mem_filter,mem_univ,true_andrefine ⟨⟨w, hwv⟩, ?_, hbits⟩ simpa only [mem_inter, binary_partial_word_restrict_support, mem_filter, mem_univ, true_and] using hw
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).
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
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.
uses
dif_pos,Or.inlhave 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
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.
uses
mem_filter,dif_negrefine ⟨⟨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
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.
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