AFTD Auto-Formalizing Theoretical Domains

weighted_orthogonal_card_bound

theoremverified

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

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.

  1. 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.

    lines 10–14

    uses Fintype.linearIndependent_iff, congrArg

      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
  2. 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))$.

    lines 15–24

    uses Finset.sum_apply, Pi.smul_apply, smul_eq_mul, mul_sum, sum_mul, sum_comm, sum_congr

        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
  3. $\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`).

    lines 25–26

    uses Pi.zero_apply, mul_zero, zero_mul, sum_const_zero

        rw [heq] at he
        simp only [Pi.zero_apply, mul_zero, zero_mul, sum_const_zero] at he
  4. $\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$.

    lines 27–32

    uses sum_eq_single, mul_zero

        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
  5. 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$.

    lines 33–34

    uses mul_eq_zero.mp

        rw [hs] at he
        exact (mul_eq_zero.mp he).resolve_right (hnorm a)
  6. $|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|$.

    line 35

    uses Pi.basisFun, card_le_card_of_linearIndependent

      exact (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.

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

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
See it in the graphDiscuss this resultChallenge it