binary_partial_word_partition_dimension_bound
A finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than coordinates.
Statement
theorem binary_partial_word_partition_dimension_bound {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) (hessential : ∀ v, ∃ i, v ∈ s i) : Fintype.card V + 1 ≤ Fintype.card I
- 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 6
- 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_cardA partial-word cube on a finite coordinate type has cardinality two to the number of coordinates outside its support.
- binary_bool_signThe rational sign of a Boolean value: true gives one and false gives minus one.
- binary_partial_word_signThe rational signed incidence of a coordinate in a partial word, with zero outside its support.
- binary_partial_word_partition_momentsFor a partition by pairwise conflicting partial-word cubes, the cardinality-weighted first signed incidences and mixed signed incidences…
- weighted_orthogonal_card_boundA finite family of vectors with nonzero weighted squared norms and zero off-diagonal weighted pair products has size at most its ambient…
- Used by 1
- 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
The theorem is proved by constructing an orthogonal system of |V| + 1 non-zero vectors in the weighted space Q^I, where each index i is weighted by the size of its corresponding subcube w_i = 2^(|V| - |s i|). The system consists of the constant-one vector (indexed by none) together with the coordinate sign vectors (indexed by each v ∈ V), which are shown to be pairwise orthogonal using the partition moments theorem. Because every coordinate is essential, each vector has strictly positive weighted norm, and the bound |V| + 1 ≤ |I| follows from the standard linear algebraic bound on the size of an orthogonal system.
Define the subcube weights w on I and the test vectors y on Option V.
Working classically, each partition element i ∈ I is assigned the weight w(i) equal to the size of its subcube in the Boolean cube. A family of vectors y_a ∈ Q^I indexed by a ∈ Option V is defined: the extra element none gives the constant-one vector y_{none}(i) = 1, while each coordinate v ∈ V gives the sign vector y_v(i), which is 1 if the i-th partial word fixes v to true, -1 if it fixes v to false, and 0 if v is unassigned.
classical let w : I → ℚ := fun i => (binary_partial_word_cube (s i) (b i)).card let y : Option V → I → ℚ := fun a i => match a with | none => 1 | some v => binary_partial_word_sign (s i) (b i) v
Every weight w(i) is strictly positive.
Unfolding the definition of w and rewriting with binary_partial_word_cube_card, the size of subcube i is 2^(|V| - |s i|). The positivity tactic verifies that this power of two is strictly positive.
uses
binary_partial_word_cube_cardhave hw (i : I) : 0 < w i := by dsimp [w] rw [binary_partial_word_cube_card] positivity
The index set I is non-empty.
The all-false assignment belongs to the universal set of assignments (mem_univ). Since the subcubes cover the universal set (hcover), the all-false assignment lies in the union of all subcubes, so by mem_biUnion there exists at least one index i ∈ I containing it.
uses
mem_univ,mem_biUnionhave hex : ∃ i : I, True := by have hf : (fun _ : V => false) ∈ univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by rw [hcover] exact mem_univ _ rcases mem_biUnion.mp hf with ⟨i, hi, hf⟩ exact ⟨i, trivial⟩
The weighted first and second moments of the sign vectors vanish.
Because the subcubes pairwise conflict (hconflict) and cover the entire Boolean cube (hcover), binary_partial_word_partition_moments supplies the two moment conditions: the weighted sum of y_v is 0 for every coordinate v, and the weighted sum of products y_u * y_v is 0 for any distinct coordinates u ≠ v.
uses
binary_partial_word_partition_momentshave hm := binary_partial_word_partition_moments s b hconflict hcoverThe family of vectors {y_a} is pairwise orthogonal with respect to the weights w.
Given distinct a, c ∈ Option V, we case-split on whether each is none or some coordinate. If both are none, they cannot be distinct. If one is none and the other is some v, the weighted inner product reduces to the first moment condition ∑_i w_i y_v(i) = 0. If they are some u and some v, then u ≠ v by congrArg, so the weighted inner product vanishes by the second moment condition.
uses
congrArghave horth (a c : Option V) (hac : a ≠ c) : (∑ i, w i * y a i * y c i) = 0 := by cases a with | none => cases c with | none => exact (hac rfl).elim | some v => simpa [w, y] using hm.1 v | some u => cases c with | none => simpa [w, y] using hm.1 u | some v => exact hm.2 u v (fun he => hac (congrArg some he))
Every vector y_a has strictly positive, hence non-zero, weighted norm-squared.
By ne_of_gt, it suffices to show that ∑_i w_i (y_a(i))^2 > 0. Every summand is non-negative because w_i > 0 and squares are non-negative (sq_nonneg). By sum_pos', it suffices to exhibit a single index where the term is strictly positive. For a = none, y_{none}(i) = 1, and any index in I (which is non-empty) gives w_i > 0. For a = some v, the essentiality hypothesis hessential guarantees an index i where v ∈ s i; at this index, if_pos simplifies y_v(i) to ±1, making the summand w_i * (±1)^2 = w_i > 0.
uses
ne_of_gt,sum_pos',mem_univ,sq_nonneg,if_poshave hnorm (a : Option V) : (∑ i, w i * y a i * y a i) ≠ 0 := by apply ne_of_gt cases a with | none => obtain ⟨i, hi⟩ := hex simpa [y] using (sum_pos' (fun j hj => (hw j).le) ⟨i, mem_univ _, hw i⟩) | some v => obtain ⟨i, hi⟩ := hessential v apply sum_pos' · intro j hj have hq := sq_nonneg (y (some v) j) nlinarith [hw j] · refine ⟨i, mem_univ _, ?_⟩ dsimp [y, binary_partial_word_sign] rw [if_pos hi] cases hbit : b i v <;> simpa [binary_bool_sign, hbit] using hw i
The number of parts is at least one more than the dimension: |V| + 1 ≤ |I|.
The lemma weighted_orthogonal_card_bound implies that any family of non-zero pairwise orthogonal vectors in Q^I has cardinality at most |I|. Since the family is indexed by Option V, whose cardinality is |V| + 1 by Fintype.card_option, the desired inequality follows immediately.
uses
Fintype.card_option,weighted_orthogonal_card_boundsimpa only [Fintype.card_option] using weighted_orthogonal_card_bound w y horth hnorm
binary_partial_word_cube_card- The cardinality of the subcube defined by a partial word specifying coordinates s is 2^(|V| - |s|).
mem_univ- Every element of a finite type belongs to its universal finset.
mem_biUnion- An element belongs to a finset union ⋃_{a ∈ s} t(a) if and only if it belongs to t(a) for some a ∈ s.
binary_partial_word_partition_moments- For any partition of the Boolean cube by pairwise conflicting partial words, the weighted first moment of coordinate signs is zero for every coordinate, and the weighted second moment is zero for any pair of distinct coordinates.
congrArg- If two arguments are equal, applying any function to them yields equal results.
ne_of_gt- If b < a in a preorder, then a ≠ b.
sum_pos'- A finite sum of non-negative elements is strictly positive if at least one term is strictly positive.
sq_nonneg- The square of any element in an ordered semiring is non-negative.
if_pos- A conditional expression if c then t else e reduces to t whenever the condition c is true.
Fintype.card_option- For any finite type α, the cardinality of Option α is |α| + 1.
weighted_orthogonal_card_bound- A family of pairwise orthogonal non-zero vectors in a weighted space Q^I has cardinality at most |I|.
- The base element none in Option V corresponds to the constant-one vector, allowing the coordinates V and the constant vector to be treated together as a single orthogonal family of size |V| + 1.
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_dimension_bound {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) (hessential : ∀ v, ∃ i, v ∈ s i) : Fintype.card V + 1 ≤ Fintype.card I := by classical let w : I → ℚ := fun i => (binary_partial_word_cube (s i) (b i)).card let y : Option V → I → ℚ := fun a i => match a with | none => 1 | some v => binary_partial_word_sign (s i) (b i) v have hw (i : I) : 0 < w i := by dsimp [w] rw [binary_partial_word_cube_card] positivity have hex : ∃ i : I, True := by have hf : (fun _ : V => false) ∈ univ.biUnion (fun i => binary_partial_word_cube (s i) (b i)) := by rw [hcover] exact mem_univ _ rcases mem_biUnion.mp hf with ⟨i, hi, hf⟩ exact ⟨i, trivial⟩ have hm := binary_partial_word_partition_moments s b hconflict hcover have horth (a c : Option V) (hac : a ≠ c) : (∑ i, w i * y a i * y c i) = 0 := by cases a with | none => cases c with | none => exact (hac rfl).elim | some v => simpa [w, y] using hm.1 v | some u => cases c with | none => simpa [w, y] using hm.1 u | some v => exact hm.2 u v (fun he => hac (congrArg some he)) have hnorm (a : Option V) : (∑ i, w i * y a i * y a i) ≠ 0 := by apply ne_of_gt cases a with | none => obtain ⟨i, hi⟩ := hex simpa [y] using (sum_pos' (fun j hj => (hw j).le) ⟨i, mem_univ _, hw i⟩) | some v => obtain ⟨i, hi⟩ := hessential v apply sum_pos' · intro j hj have hq := sq_nonneg (y (some v) j) nlinarith [hw j] · refine ⟨i, mem_univ _, ?_⟩ dsimp [y, binary_partial_word_sign] rw [if_pos hi] cases hbit : b i v <;> simpa [binary_bool_sign, hbit] using hw i simpa only [Fintype.card_option] using weighted_orthogonal_card_bound w y horth hnorm