binary_partial_word_cube_minimum_incidence
For pairwise conflicting finite partial words, if total support size plus 2^m equals the number of words times m+1, then their volume sum is one and every support size is m or m-1, expressed without truncated subtraction.
Statement
theorem binary_partial_word_cube_minimum_incidence {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (m : ℕ) (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v) (hcost : (∑ i, (s i).card) + 2^m = Fintype.card I * (m+1)) : (∑ i, (1 : ℚ) / 2^(s i).card) = 1 ∧ ∀ i, (s i).card = m ∨ (s i).card + 1 = m
- 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
- dyadic_integer_tangentFor natural m and t, the rational number m+1-t is at most 2^m divided by 2^t.
- binary_partial_word_cube_volume_boundThe sum of 2 to the negative support sizes of pairwise conflicting finite partial words is at most one.
- dyadic_integer_tangent_eq_iffEquality in the rational dyadic tangent bound occurs exactly at t=m or t+1=m.
- Used by 1
- ordered_biclique_minimum_incidence_intervalsLet g be positive and take g-1 bicliques indexed by cuts r+1 of the ordered set Fin g, with the first side strictly above r and the second…
The proof, explained
The proof uses a dyadic tangent line inequality: for every natural number t, the affine function m + 1 - t is bounded above by 2^m / 2^t, with equality if and only if t = m or t + 1 = m. Summing this inequality over all partial words and substituting the given cost condition yields 2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card, which implies the volume sum is at least 1. Since the partial words pairwise conflict, their corresponding subcubes are disjoint, so their volume sum cannot exceed 1; combining these bounds forces the volume sum to equal exactly 1. Finally, because the sum of the lower bounds equals the sum of the upper bounds, equality must hold term-by-term, characterizing every support size as either m or m - 1.
The volume sum ∑ i, 1 / 2^(s i).card is at most 1.
Enabling classical logic, we apply the volume bound for pairwise conflicting binary partial words (`binary_partial_word_cube_volume_bound`). Because the partial words pairwise conflict on overlapping coordinates, the subcubes they define in {0, 1}^V are pairwise disjoint, so the sum of their volumes cannot exceed 1.
uses
binary_partial_word_cube_volume_boundclassical have hu := binary_partial_word_cube_volume_bound s b hconflict∑ i, ((m : ℚ) + 1 - (s i).card) = 2^m.
We cast the cost hypothesis to rational numbers. Distributing the sum over the subtraction with `sum_sub_distrib` and evaluating the sum of the constant (m + 1) via `sum_const`, `nsmul_eq_mul`, and `card_univ`, linear arithmetic (`linarith`) rearranges the equation into ∑ i, ((m : ℚ) + 1 - (s i).card) = 2^m.
uses
sum_sub_distrib,sum_const,nsmul_eq_mul,card_univhave hc : (∑ i, ((s i).card : ℚ)) + 2^m = (Fintype.card I : ℚ) * (m+1) := by exact_mod_cast hcost have hsum : (∑ i, ((m : ℚ)+1-(s i).card)) = 2^m := by simp only [sum_sub_distrib, sum_const, nsmul_eq_mul, card_univ] linarith
2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card.
By the dyadic tangent inequality `dyadic_integer_tangent`, every natural number t satisfies m + 1 - t ≤ 2^m / 2^t. Summing this termwise via `sum_le_sum` and replacing the left-hand sum with 2^m, we obtain 2^m ≤ ∑ i, 2^m / 2^(s i).card. Factoring out 2^m using `mul_sum`, `div_eq_mul_inv`, and `one_mul` gives the claimed lower bound.
uses
sum_le_sum,dyadic_integer_tangent,div_eq_mul_inv,one_mul,mul_sumhave hl : (2 : ℚ)^m ≤ 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by calc (2 : ℚ)^m = ∑ i, ((m : ℚ)+1-(s i).card) := hsum.symm _ ≤ ∑ i, (2 : ℚ)^m / 2^(s i).card := sum_le_sum (fun i hi => dyadic_integer_tangent m (s i).card) _ = 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by simp only [div_eq_mul_inv, one_mul, mul_sum]
The volume sum ∑ i, 1 / 2^(s i).card equals 1, proving the first conjunct.
Since 2^m > 0 (by `positivity`), dividing the lower bound 2^m ≤ 2^m * ∑ i, 1 / 2^(s i).card by 2^m yields 1 ≤ ∑ i, 1 / 2^(s i).card. Non-linear arithmetic (`nlinarith`) combines this with the upper bound ∑ i, 1 / 2^(s i).card ≤ 1 to deduce that the sum is exactly 1, which establishes the first goal of the conjunction.
have hp : (0 : ℚ) < 2^m := by positivity have hv : (∑ i, (1 : ℚ)/2^(s i).card) = 1 := by nlinarith refine ⟨hv, ?_⟩
For every i, equality holds in the tangent inequality: (m : ℚ) + 1 - (s i).card = 2^m / 2^(s i).card.
Each term satisfies (m : ℚ) + 1 - (s j).card ≤ 2^m / 2^(s j).card by `dyadic_integer_tangent`. Furthermore, the sum of the left-hand sides is 2^m, and the sum of the right-hand sides is 2^m * ∑ j, 1 / 2^(s j).card = 2^m * 1 = 2^m by `div_eq_mul_inv`, `one_mul`, `mul_sum`, and `mul_one`. By `sum_eq_sum_iff_of_le`, when a sum of smaller terms equals the sum of larger terms over a finite set, equality must hold term-by-term. Specializing to i using `mem_univ` yields the claim.
uses
dyadic_integer_tangent,div_eq_mul_inv,one_mul,mul_sum,mul_one,sum_eq_sum_iff_of_le,mem_univhave hterm : ∀ i, (m : ℚ)+1-(s i).card = 2^m / 2^(s i).card := by intro i have hle : ∀ j ∈ (univ : Finset I), (m : ℚ)+1-(s j).card ≤ 2^m / 2^(s j).card := by intro j hj exact dyadic_integer_tangent m (s j).card have heq : (∑ j, ((m : ℚ)+1-(s j).card)) = ∑ j, (2 : ℚ)^m / 2^(s j).card := by rw [hsum] simp only [div_eq_mul_inv, one_mul] at hv ⊢ rw [← mul_sum, hv, mul_one] exact (sum_eq_sum_iff_of_le hle).mp heq i (mem_univ _)
For every i, (s i).card = m or (s i).card + 1 = m.
For any index i, termwise equality holds from the previous step. The lemma `dyadic_integer_tangent_eq_iff` states that (m : ℚ) + 1 - t = 2^m / 2^t if and only if t = m or t + 1 = m. Applying this equivalence to t = (s i).card proves the second conjunct.
uses
dyadic_integer_tangent_eq_iffintro i exact (dyadic_integer_tangent_eq_iff m (s i).card).mp (hterm i)
binary_partial_word_cube_volume_bound- for pairwise conflicting partial words, the sum of their volumes 2^(-|s i|) is at most 1
card_univ- the cardinality of Finset.univ for a finite type is the cardinality of the type
div_eq_mul_inv- division a / b is definitionally multiplication by the inverse, a * b⁻¹
dyadic_integer_tangent- for any natural numbers m and t, the affine function (m + 1) - t is bounded above by 2^m / 2^t
dyadic_integer_tangent_eq_iff- the equality (m + 1) - t = 2^m / 2^t holds for natural numbers m and t if and only if t = m or t + 1 = m
mem_univ- every element of a finite type belongs to the universal finset Finset.univ
mul_one- multiplying an element on the right by 1 leaves it unchanged
mul_sum- multiplication distributes over finite sums from the left
nsmul_eq_mul- scalar multiplication of an element by a natural number n is equal to multiplication by the coercion of n
one_mul- multiplying an element on the left by 1 leaves it unchanged
sum_const- summing a constant value over a finite set equals the cardinality of the set multiplied by that constant
sum_eq_sum_iff_of_le- if each term f(x) is at most g(x), then their sums are equal if and only if f(x) = g(x) for all terms
sum_le_sum- if f(x) ≤ g(x) for all elements in a finite set, then the sum of f is at most the sum of g
sum_sub_distrib- a sum of differences equals the difference of the sums
- The condition that every support size is m or m-1 is formalized without truncated natural number subtraction as `(s i).card = m ∨ (s i).card + 1 = m`.
- In step 4 (lines 25–27), `nlinarith` automatically closes the non-linear deduction that the sum is 1 from the lower bound, the upper bound, and positivity of 2^m.
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_cube_minimum_incidence {I V : Type*} [Fintype I] [Fintype V] [DecidableEq V] (s : I → Finset V) (b : I → V → Bool) (m : ℕ) (hconflict : ∀ i j, i ≠ j → ∃ v ∈ s i ∩ s j, b i v ≠ b j v) (hcost : (∑ i, (s i).card) + 2^m = Fintype.card I * (m+1)) : (∑ i, (1 : ℚ) / 2^(s i).card) = 1 ∧ ∀ i, (s i).card = m ∨ (s i).card + 1 = m := by classical have hu := binary_partial_word_cube_volume_bound s b hconflict have hc : (∑ i, ((s i).card : ℚ)) + 2^m = (Fintype.card I : ℚ) * (m+1) := by exact_mod_cast hcost have hsum : (∑ i, ((m : ℚ)+1-(s i).card)) = 2^m := by simp only [sum_sub_distrib, sum_const, nsmul_eq_mul, card_univ] linarith have hl : (2 : ℚ)^m ≤ 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by calc (2 : ℚ)^m = ∑ i, ((m : ℚ)+1-(s i).card) := hsum.symm _ ≤ ∑ i, (2 : ℚ)^m / 2^(s i).card := sum_le_sum (fun i hi => dyadic_integer_tangent m (s i).card) _ = 2^m * ∑ i, (1 : ℚ)/2^(s i).card := by simp only [div_eq_mul_inv, one_mul, mul_sum] have hp : (0 : ℚ) < 2^m := by positivity have hv : (∑ i, (1 : ℚ)/2^(s i).card) = 1 := by nlinarith refine ⟨hv, ?_⟩ have hterm : ∀ i, (m : ℚ)+1-(s i).card = 2^m / 2^(s i).card := by intro i have hle : ∀ j ∈ (univ : Finset I), (m : ℚ)+1-(s j).card ≤ 2^m / 2^(s j).card := by intro j hj exact dyadic_integer_tangent m (s j).card have heq : (∑ j, ((m : ℚ)+1-(s j).card)) = ∑ j, (2 : ℚ)^m / 2^(s j).card := by rw [hsum] simp only [div_eq_mul_inv, one_mul] at hv ⊢ rw [← mul_sum, hv, mul_one] exact (sum_eq_sum_iff_of_le hle).mp heq i (mem_univ _) intro i exact (dyadic_integer_tangent_eq_iff m (s i).card).mp (hterm i)