weighted_orthogonal_card_bound
A finite family of vectors with nonzero weighted squared norms and zero off-diagonal weighted pair products has size at most its ambient coordinate type. The weights and vectors are rational.
Statement
theorem weighted_orthogonal_card_bound {I J : Type*} [Fintype I] [Fintype J] (w : I → ℚ) (v : J → I → ℚ) (horth : ∀ a b, a ≠ b → (∑ i, w i * v a i * v b i) = 0) (hnorm : ∀ a, (∑ i, w i * v a i * v a i) ≠ 0) : Fintype.card J ≤ 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- Used by 1
- binary_partial_word_partition_dimension_boundA finite partition of a Boolean cube by pairwise conflicting partial words, mentioning every coordinate, has at least one more part than…
The proof, explained
The theorem is proved by showing that the family of vectors $v$ is linearly independent over $\mathbb{Q}$, which immediately implies the cardinality bound $|J| \le |I|$ because the ambient space $\mathbb{Q}^I$ has dimension $|I|$. To establish linear independence, suppose a linear combination $\sum_{j \in J} g_j v_j = 0$ vanishes. Taking the weighted inner product of this relation with an arbitrary vector $v_a$, all terms with $j \ne a$ vanish by the orthogonality hypothesis, leaving $g_a \sum_{i \in I} w_i v_a(i)^2 = 0$. Since each weighted squared norm is nonzero by hypothesis, every coefficient $g_a$ must be zero.
To prove that the family $v$ is linearly independent, it suffices to show that any vanishing linear combination $\sum_{j} g_j v_j = 0$ has $g_a = 0$ for each $a \in J$, and we begin by applying the weighted functional $f \mapsto \sum_{i} w_i f(i) v_a(i)$ to both sides of this relation.
Using classical logic and the equivalence of linear independence with the triviality of linear relations for finite types (`Fintype.linearIndependent_iff`), we assume a linear relation $\sum_j g_j v_j = 0$ and pick an arbitrary index $a \in J$. Applying the linear functional $f \mapsto \sum_i w_i f(i) v_a(i)$ to both sides via `congrArg` gives an equality between weighted pairings.
uses
Fintype.linearIndependent_iff,congrArgclassical have hli : LinearIndependent ℚ v := by rw [Fintype.linearIndependent_iff] intro g hg a have he := congrArg (fun f : I → ℚ => ∑ i, w i * f i * v a i) hg
The weighted functional distributes across the linear combination: $\sum_{i} w_i (\sum_{j} g_j v_j(i)) v_a(i) = \sum_{j} g_j (\sum_{i} w_i v_j(i) v_a(i))$.
We expand function evaluation and scalar multiplication pointwise (`Finset.sum_apply`, `Pi.smul_apply`, `smul_eq_mul`), distribute products over sums (`mul_sum`, `sum_mul`), exchange the two summations (`sum_comm`), and use polynomial ring arithmetic (`ring`) to identify the individual summands $w_i (g_j v_j(i)) v_a(i)$ and $g_j (w_i v_j(i) v_a(i))$.
uses
Finset.sum_apply,Pi.smul_apply,smul_eq_mul,mul_sum,sum_mul,sum_comm,sum_congrhave heq : (∑ i, w i * (∑ j, g j • v j) i * v a i) = ∑ j, g j * (∑ i, w i * v j i * v a i) := by simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul] simp_rw [mul_sum, sum_mul] rw [sum_comm] apply sum_congr rfl intro j hj apply sum_congr rfl intro i hi ring
$\sum_{j} g_j (\sum_{i} w_i v_j(i) v_a(i)) = 0$.
We replace the left-hand side of our relation using the interchange identity `heq`. On the right-hand side, the zero function evaluates to 0 everywhere (`Pi.zero_apply`), and multiplying by 0 gives 0, so the entire right-hand side evaluates to 0 (`mul_zero`, `zero_mul`, `sum_const_zero`).
uses
Pi.zero_apply,mul_zero,zero_mul,sum_const_zerorw [heq] at he simp only [Pi.zero_apply, mul_zero, zero_mul, sum_const_zero] at he
$\sum_{j} g_j (\sum_{i} w_i v_j(i) v_a(i)) = g_a \sum_{i} w_i v_a(i)^2$.
By the pairwise orthogonality hypothesis `horth`, whenever $j \neq a$ the inner sum $\sum_i w_i v_j(i) v_a(i)$ is zero, so $g_j \cdot 0 = 0$. Applying `sum_eq_single`, all off-diagonal terms vanish, leaving only the term corresponding to $j = a$.
uses
sum_eq_single,mul_zerohave hs : (∑ j, g j * (∑ i, w i * v j i * v a i)) = g a * (∑ i, w i * v a i * v a i) := by apply sum_eq_single a · intro j hj hja rw [horth j a hja, mul_zero] · simp
The coefficient $g_a$ is 0, completing the proof that the family $v$ is linearly independent over $\mathbb{Q}$.
Substituting the collapsed sum into the equation yields $g_a (\sum_i w_i v_a(i)^2) = 0$. In $\mathbb{Q}$, a product is zero only if one factor is zero (`mul_eq_zero.mp`); since the norm squared $\sum_i w_i v_a(i)^2$ is nonzero by hypothesis `hnorm a`, we resolve the disjunction to conclude $g_a = 0$.
uses
mul_eq_zero.mprw [hs] at he exact (mul_eq_zero.mp he).resolve_right (hnorm a)
$|J| \leq |I|$.
The coordinate space $I \to \mathbb{Q}$ has a standard basis `Pi.basisFun ℚ I` of cardinality $|I|$. By `card_le_card_of_linearIndependent`, any linearly independent family indexed by $J$ has size at most the basis size $|I|$.
uses
Pi.basisFun,card_le_card_of_linearIndependentexact (Pi.basisFun ℚ I).card_le_card_of_linearIndependent hli
Fintype.linearIndependent_iff- A family of vectors indexed by a finite type is linearly independent if and only if every vanishing linear combination has all coefficients equal to zero.
congrArg- Applying a function to equal inputs yields equal outputs.
Finset.sum_apply- Evaluating a finite sum of functions at a point equals the sum of the values of the functions at that point.
Pi.smul_apply- Evaluating a scalar multiple of a function at a point equals the scalar multiple of the value at that point.
smul_eq_mul- Scalar multiplication in a ring by an element of the same ring agrees with ring multiplication.
mul_sum- Multiplication on the left distributes over finite summation: $a \sum_i f_i = \sum_i a f_i$.
sum_mul- Multiplication on the right distributes over finite summation: $(\sum_i f_i) a = \sum_i f_i a$.
sum_comm- The order of two independent finite summations can be swapped.
sum_congr- Two finite sums are equal if their index sets match and their terms are equal at every index.
Pi.zero_apply- The zero function evaluates to zero at every argument.
mul_zero- Multiplication by zero on the right equals zero: $a \cdot 0 = 0$.
zero_mul- Multiplication by zero on the left equals zero: $0 \cdot a = 0$.
sum_const_zero- The sum of zeros over any finite set is zero.
sum_eq_single- A finite sum collapses to a single summand $f(a)$ if every term with index $b \neq a$ is zero.
mul_eq_zero.mp- If the product of two elements is zero in an integral domain, at least one of the factors is zero.
Pi.basisFun- The canonical coordinate basis for the function space $\mathbb{Q}^I$.
card_le_card_of_linearIndependent- Any linearly independent family in a module with a finite basis has cardinality at most the cardinality of that basis.
- In step 4 (line 32), `sum_eq_single` generates a secondary goal requiring the summand to vanish if the index $a$ were not in the index set; because the sum is taken over all elements of the finite type (`Finset.univ`), this condition is vacuously impossible and is closed automatically by `simp`.
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 weighted_orthogonal_card_bound {I J : Type*} [Fintype I] [Fintype J] (w : I → ℚ) (v : J → I → ℚ) (horth : ∀ a b, a ≠ b → (∑ i, w i * v a i * v b i) = 0) (hnorm : ∀ a, (∑ i, w i * v a i * v a i) ≠ 0) : Fintype.card J ≤ Fintype.card I := by classical have hli : LinearIndependent ℚ v := by rw [Fintype.linearIndependent_iff] intro g hg a have he := congrArg (fun f : I → ℚ => ∑ i, w i * f i * v a i) hg have heq : (∑ i, w i * (∑ j, g j • v j) i * v a i) = ∑ j, g j * (∑ i, w i * v j i * v a i) := by simp only [Finset.sum_apply, Pi.smul_apply, smul_eq_mul] simp_rw [mul_sum, sum_mul] rw [sum_comm] apply sum_congr rfl intro j hj apply sum_congr rfl intro i hi ring rw [heq] at he simp only [Pi.zero_apply, mul_zero, zero_mul, sum_const_zero] at he have hs : (∑ j, g j * (∑ i, w i * v j i * v a i)) = g a * (∑ i, w i * v a i * v a i) := by apply sum_eq_single a · intro j hj hja rw [horth j a hja, mul_zero] · simp rw [hs] at he exact (mul_eq_zero.mp he).resolve_right (hnorm a) exact (Pi.basisFun ℚ I).card_le_card_of_linearIndependent hli