linear_flattening_rank_sum_pure_le
If rank L(x ⊗ y ⊗ z) ≤ ρ for all x, y, z, then rank L(T) ≤ r ρ for every sum T of r pure tensors; this is why potency greater than r yields equations for tensors of rank at most r.
Statement
theorem linear_flattening_rank_sum_pure_le {n u v : ℕ}
(L : (Fin n → Fin n → Fin n → ℂ) →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (ρ : ℕ)
(hρ : ∀ x y z : Fin n → ℂ, (L (tensor3_pure x y z)).rank ≤ ρ)
(r : ℕ) (x y z : Fin r → Fin n → ℂ) :
(L (∑ i, tensor3_pure (x i) (y i) (z i))).rank ≤ r * ρ- Formalizes
- arXiv:2610.08504 (Explicit tensors beyond the linear flattening barrier), Sec. 1 (the linear flattening method: Pot(L) > r gives nontrivial equations for σ_r); rank version, without the closure step to border rank
- Verified
- 07 Oct 2026
- Axioms
Classical.choiceQuot.soundpropext- Built on 1
- tensor3_pureThe pure tensor x ⊗ y ⊗ z in ℂⁿ ⊗ ℂⁿ ⊗ ℂⁿ, with entries x_i y_j z_k.
The proof, explained
The theorem is proved by combining the subadditivity of matrix rank with the linearity of L. First, matrix rank is subadditive under addition, which extends by finite induction to show that the rank of any finite sum of matrices is bounded by the sum of their individual ranks. Applying linearity distributes L over the sum of r pure tensors, expressing L(T) as a sum of r matrices. Since each pure tensor has image rank at most ρ by hypothesis, subadditivity bounds the total rank by the sum of these r bounds, which evaluates to r * ρ.
For any two matrices A and B, rank(A + B) ≤ rank(A) + rank(B).
Unfolding the definition of rank (Matrix.rank) as the dimension of the range of the associated linear map and rewriting the map of a sum as the sum of maps (Matrix.mulVecLin_add), the range of the sum is contained in the span of the ranges by LinearMap.range_add_le. By monotonicity of subspace dimension (Submodule.finrank_mono), the rank of A + B is at most the dimension of this span, which by Submodule.finrank_add_le_finrank_add_finrank is bounded by the sum of the individual ranks.
uses
Matrix.rank,Matrix.mulVecLin_add,LinearMap.range_add_le,Submodule.finrank_mono,Submodule.finrank_add_le_finrank_add_finrankdsimp [Matrix.rank] rw [Matrix.mulVecLin_add] have h_le : LinearMap.range (Matrix.mulVecLin A + Matrix.mulVecLin B) ≤ LinearMap.range (Matrix.mulVecLin A) ⊔ LinearMap.range (Matrix.mulVecLin B) := LinearMap.range_add_le _ _ have h_mono := Submodule.finrank_mono h_le exact h_mono.trans (Submodule.finrank_add_le_finrank_add_finrank _ _)
For any finite set s and family of matrices F, rank(∑_{i ∈ s} F i) ≤ ∑_{i ∈ s} rank(F i).
We proceed by induction on the finite set s using Finset.cons_induction. For the empty set s = ∅, both sides evaluate to zero. For the inductive step s ∪ {a} with a ∉ s, we split off the term F(a) using Finset.sum_cons, apply two-matrix subadditivity (linear_flattening_rank_sum_pure_le_rank_add) to F(a) + ∑_{i ∈ s} F(i), and invoke the induction hypothesis via Nat.add_le_add_left.
uses
Finset.cons_induction,Finset.sum_cons,linear_flattening_rank_sum_pure_le_rank_add,Nat.add_le_add_leftinduction s using Finset.cons_induction with | empty => simp | cons a s ha ih => rw [Finset.sum_cons, Finset.sum_cons] have h_add := linear_flattening_rank_sum_pure_le_rank_add (F a) (∑ i ∈ s, F i) exact h_add.trans (Nat.add_le_add_left ih _)
The rank of L(∑_{i=1}^r x_i ⊗ y_i ⊗ z_i) is bounded by the sum of ranks ∑_{i=1}^r rank(L(x_i ⊗ y_i ⊗ z_i)).
By linearity of L (map_sum), L distributes over the sum of pure tensors. Applying the finite subadditivity lemma (linear_flattening_rank_sum_pure_le_rank_sum) over the full index set Finset.univ bounds the rank of this matrix sum by the sum of the ranks of each term.
uses
map_sum,linear_flattening_rank_sum_pure_le_rank_sumrw [map_sum] have h1 : (∑ i, L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ i, (L (tensor3_pure (x i) (y i) (z i))).rank := linear_flattening_rank_sum_pure_le_rank_sum Finset.univ _
The sum of ranks ∑_{i=1}^r rank(L(x_i ⊗ y_i ⊗ z_i)) is at most r * ρ.
By hypothesis hρ, each pure tensor satisfies rank(L(x_i ⊗ y_i ⊗ z_i)) ≤ ρ. Summing these bounds over Fin r via Finset.sum_le_sum gives the sum of the constant ρ over Fin r. Applying Finset.sum_const, evaluating the cardinality of Fin r as r via Finset.card_fin, and converting natural scalar multiplication to ordinary multiplication via nsmul_eq_mul simplifies this bound to r * ρ.
uses
Finset.sum_le_sum,Finset.sum_const,Finset.card_fin,nsmul_eq_mulhave h2 : ∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ _i : Fin r, ρ := Finset.sum_le_sum (fun i _ => hρ (x i) (y i) (z i)) rw [Finset.sum_const, Finset.card_fin, nsmul_eq_mul] at h2
The rank of L(∑_{i=1}^r x_i ⊗ y_i ⊗ z_i) is at most r * ρ.
Combining the subadditivity bound from the third step with the rank bound on the sum from the fourth step by transitivity of inequality concludes the proof.
exact h1.trans h2
Matrix.rank- The rank of a matrix is the dimension (finrank) of the range of its associated linear map.
Matrix.mulVecLin_add- The linear map associated with the sum of two matrices is the sum of the linear maps associated with each matrix.
LinearMap.range_add_le- The range of the sum of two linear maps is contained in the join (sum of submodules) of their individual ranges.
Submodule.finrank_mono- Submodule dimension is monotonic with respect to inclusion: if s ≤ t, then the dimension of s is at most the dimension of t.
Submodule.finrank_add_le_finrank_add_finrank- The dimension of the join of two submodules is at most the sum of their individual dimensions.
Finset.cons_induction- Induction principle for finite sets: a property holds for all finite sets if it holds for the empty set and is preserved when inserting a new element.
Finset.sum_cons- The sum of a function over a finite set with a new element inserted equals the value at that element plus the sum over the original set.
linear_flattening_rank_sum_pure_le_rank_add- The rank of the sum of two complex matrices is at most the sum of their individual ranks.
Nat.add_le_add_left- Adding a fixed natural number to the left of both sides of an inequality preserves the inequality.
map_sum- A linear map preserves finite sums, mapping the sum of elements to the sum of their images.
linear_flattening_rank_sum_pure_le_rank_sum- The rank of a finite sum of complex matrices is at most the sum of their individual ranks.
Finset.sum_le_sum- If each term in a finite sum is bounded by the corresponding term in another sum, the total sum is bounded by the second sum.
Finset.sum_const- The sum of a constant value over a finite set equals the cardinality of the set scalar-multiplied by that constant.
Finset.card_fin- The cardinality of the universal set of type Fin n is n.
nsmul_eq_mul- Scalar multiplication of an element by a natural number equals ordinary multiplication by that natural number in a semiring.
- In step 2 (line 16), the base case for the empty set is handled by the `simp` tactic, which automatically evaluates empty sums to zero and proves 0 ≤ 0.
- In step 4 (line 34), scalar multiplication by a natural number (r • ρ) arising from Finset.sum_const is formally rewritten to standard multiplication (r * ρ) via nsmul_eq_mul.
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.
lemma linear_flattening_rank_sum_pure_le_rank_add {u v : ℕ} (A B : Matrix (Fin u) (Fin v) ℂ) : (A + B).rank ≤ A.rank + B.rank := by dsimp [Matrix.rank] rw [Matrix.mulVecLin_add] have h_le : LinearMap.range (Matrix.mulVecLin A + Matrix.mulVecLin B) ≤ LinearMap.range (Matrix.mulVecLin A) ⊔ LinearMap.range (Matrix.mulVecLin B) := LinearMap.range_add_le _ _ have h_mono := Submodule.finrank_mono h_le exact h_mono.trans (Submodule.finrank_add_le_finrank_add_finrank _ _)lemma linear_flattening_rank_sum_pure_le_rank_sum {ι : Type*} {u v : ℕ} (s : Finset ι) (F : ι → Matrix (Fin u) (Fin v) ℂ) : (∑ i ∈ s, F i).rank ≤ ∑ i ∈ s, (F i).rank := by induction s using Finset.cons_induction with | empty => simp | cons a s ha ih => rw [Finset.sum_cons, Finset.sum_cons] have h_add := linear_flattening_rank_sum_pure_le_rank_add (F a) (∑ i ∈ s, F i) exact h_add.trans (Nat.add_le_add_left ih _)theorem linear_flattening_rank_sum_pure_le {n u v : ℕ} (L : (Fin n → Fin n → Fin n → ℂ) →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (ρ : ℕ) (hρ : ∀ x y z : Fin n → ℂ, (L (tensor3_pure x y z)).rank ≤ ρ) (r : ℕ) (x y z : Fin r → Fin n → ℂ) : (L (∑ i, tensor3_pure (x i) (y i) (z i))).rank ≤ r * ρ := by rw [map_sum] have h1 : (∑ i, L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ i, (L (tensor3_pure (x i) (y i) (z i))).rank := linear_flattening_rank_sum_pure_le_rank_sum Finset.univ _ have h2 : ∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ _i : Fin r, ρ := Finset.sum_le_sum (fun i _ => hρ (x i) (y i) (z i)) rw [Finset.sum_const, Finset.card_fin, nsmul_eq_mul] at h2 exact h1.trans h2