binary_partial_word_partition_both_bits
Every mentioned coordinate of a finite partial-word cube partition occurs with both Boolean values.
Statement
theorem binary_partial_word_partition_both_bits {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) (hessential : ∃ i, v ∈ s i) : ∀ bit : Bool, ∃ i, v ∈ s i ∧ b i v = bit
- 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 2
- 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…
- Used by 2
- 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…
- binary_partial_word_partition_min_degree_restrict_essentialFixing a coordinate with minimum occurrence count in a finite cube partition that mentions every coordinate leaves every other coordinate…
The proof, explained
Given a coordinate v fixed by some subcube i in the partition, consider the Boolean word f obtained by flipping the value of b(i) at v. Because the subcubes cover the entire hypercube, f must belong to some subcube j. This subcube j must be distinct from i and must also fix coordinate v, since otherwise the conflict coordinate between i and j would force f to take two different values at that coordinate. Thus j fixes v to the opposite bit ¬b(i)(v), showing that both Boolean values are attained at v.
We select a subcube i fixing coordinate v, define a word f by flipping the bit at v, and obtain a subcube j that covers f.
By the assumption that v is essential (hessential), there is some subcube index i with v ∈ s(i). We define f to agree with b(i) at every coordinate except v, where its value is inverted to ¬b(i)(v). Since the subcubes cover the hypercube (hcover), binary_partial_word_cube_cover_iff provides a subcube j such that f agrees with b(j) on all coordinates in s(j).
uses
binary_partial_word_cube_cover_iffclassical obtain ⟨i, hi⟩ := hessential let f := Function.update (b i) v (!(b i v)) obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover f
The covering subcube j is distinct from i.
Flipping a Boolean bit always produces a different value (hflip). If i = j, then because v ∈ s(i), the covering condition for j would give f(v) = b(i)(v). But by definition, f(v) = ¬b(i)(v) via Function.update_self, which would imply ¬b(i)(v) = b(i)(v), a contradiction.
uses
Function.update_selfhave hflip : (!(b i v)) ≠ b i v := by cases b i v <;> decide have hij : i ≠ j := by intro heq subst j have he := hj v hi exact hflip (by simpa only [f, Function.update_self] using he)
The subcube j also fixes coordinate v, that is, v ∈ s(j).
Suppose for contradiction that v ∉ s(j). Since i ≠ j, the partition conflict hypothesis (hconflict) guarantees a coordinate w ∈ s(i) ∩ s(j) where b(i)(w) ≠ b(j)(w). Because w ∈ s(j) and v ∉ s(j), we must have w ≠ v. Since w ≠ v, updating f at v leaves coordinate w unchanged (Function.update_of_ne), so f(w) = b(i)(w). But because w ∈ s(j), the covering property of j requires f(w) = b(j)(w). Hence b(i)(w) = b(j)(w), contradicting b(i)(w) ≠ b(j)(w).
uses
Function.update_of_nehave hvj : v ∈ s j := by by_contra hn obtain ⟨w, hw, hne⟩ := hconflict i j hij have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2 have he := hj w (mem_inter.mp hw).2 exact hne (by simpa only [f, Function.update_of_ne hwv] using he)
Subcube j assigns to coordinate v the flipped bit, b(j)(v) = ¬b(i)(v).
Since v ∈ s(j), the covering property ensures b(j)(v) = f(v). Evaluating f at v via Function.update_self gives ¬b(i)(v).
uses
Function.update_selfhave hbj : b j v = !(b i v) := by simpa only [f, Function.update_self] using (hj v hvj).symm
For every Boolean value bit, some subcube fixes v to that value.
Given any bit, we split on whether b(i)(v) = bit. If so, subcube i witnesses the claim since v ∈ s(i) and b(i)(v) = bit. If not, then because Bool has only two values, the flipped bit ¬b(i)(v) must equal bit. Subcube j then witnesses the claim since v ∈ s(j) and b(j)(v) = ¬b(i)(v) = bit.
intro bit by_cases hbit : b i v = bit · exact ⟨i, hi, hbit⟩ · refine ⟨j, hvj, hbj.trans ?_⟩ cases hbi : b i v <;> cases bit <;> simp_all
binary_partial_word_cube_cover_iff- A collection of partial-word cubes covers the entire space of Boolean functions on V if and only if every Boolean function agrees with at least one cube on all coordinates fixed by that cube.
Function.update_self- Updating a function at an input coordinate and then evaluating at that same coordinate yields the updated value.
Function.update_of_ne- Updating a function at an input coordinate does not change its value when evaluated at any distinct coordinate.
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_both_bits {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) (hessential : ∃ i, v ∈ s i) : ∀ bit : Bool, ∃ i, v ∈ s i ∧ b i v = bit := by classical obtain ⟨i, hi⟩ := hessential let f := Function.update (b i) v (!(b i v)) obtain ⟨j, hj⟩ := (binary_partial_word_cube_cover_iff s b).mp hcover f have hflip : (!(b i v)) ≠ b i v := by cases b i v <;> decide have hij : i ≠ j := by intro heq subst j have he := hj v hi exact hflip (by simpa only [f, Function.update_self] using he) have hvj : v ∈ s j := by by_contra hn obtain ⟨w, hw, hne⟩ := hconflict i j hij have hwv : w ≠ v := by rintro rfl; exact hn (mem_inter.mp hw).2 have he := hj w (mem_inter.mp hw).2 exact hne (by simpa only [f, Function.update_of_ne hwv] using he) have hbj : b j v = !(b i v) := by simpa only [f, Function.update_self] using (hj v hvj).symm intro bit by_cases hbit : b i v = bit · exact ⟨i, hi, hbit⟩ · refine ⟨j, hvj, hbj.trans ?_⟩ cases hbi : b i v <;> cases bit <;> simp_all