not_sum_pure_of_linear_flattening_potency_gt
If a linear flattening L on (ℂⁿ)⊗³ and a tensor T satisfy (L T).rank > r * (L(x ⊗ y ⊗ z)).rank for all x, y, z ∈ ℂⁿ, then T cannot be expressed as a sum of r pure tensors.
Statement
theorem not_sum_pure_of_linear_flattening_potency_gt {n u v : ℕ}
(L : (Fin n → Fin n → Fin n → ℂ) →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (r : ℕ)
(T : Fin n → Fin n → Fin n → ℂ)
(hT : ∀ x y z : Fin n → ℂ, r * (L (tensor3_pure x y z)).rank < (L T).rank)
(x y z : Fin r → Fin n → ℂ) :
T ≠ ∑ i, tensor3_pure (x i) (y i) (z i)- Source
- arXiv:2610.08504 Sec. 1
- Verified
- 20 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.
- Used by 1
- linear_flattening_testable_tensor_rank_gtIf the secant variety σ_r((ℂⁿ)⊗³) is testable by the linear flattening method, then there exists a tensor in (ℂⁿ)⊗³ that cannot be written…
Read back from the Lean
For any natural numbers $n, u, v$, let $L$ be a $\mathbb{C}$-linear map from order-3 tensors of shape $n \times n \times n$ over $\mathbb{C}$ (functions Fin n → Fin n → Fin n → ℂ) to $u \times v$ complex matrices (Matrix (Fin u) (Fin v) ℂ). Let $r \in \mathbb{N}$, and let $T$ be an order-3 tensor (Fin n → Fin n → Fin n → ℂ).
Assume that for all vectors $x', y', z' : \text{Fin } n \to \mathbb{C}$,
$$r \cdot \operatorname{rank}(L(\operatorname{tensor3\_pure}(x', y', z'))) < \operatorname{rank}(L(T))$$
(where $\operatorname{rank}$ is the matrix rank in $\mathbb{N}$).
Then for any three collections of $r$ vectors $x, y, z : \text{Fin } r \to \text{Fin } n \to \mathbb{C}$, $T$ cannot be written as the sum of the corresponding $r$ pure tensors:
$$T \neq \sum_{i : \text{Fin } r} \operatorname{tensor3\_pure}(x(i), y(i), z(i)).$$
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
The proof, explained
The theorem is proved by contradiction: suppose T = ∑_{i=1}^r x_i ⊗ y_i ⊗ z_i is a sum of r pure tensors. Linearity of L and subadditivity of matrix rank over finite sums imply that rank(L T) ≤ ∑_{i=1}^r rank(L(x_i ⊗ y_i ⊗ z_i)). On the other hand, the potency hypothesis asserts that r * rank(L(x_i ⊗ y_i ⊗ z_i)) < rank(L T) for all i. If r = 0, rank(L T) is simultaneously ≤ 0 and > 0; if r > 0, summing the integer bounds over all r components and dividing by r yields ∑_{i=1}^r rank(L(x_i ⊗ y_i ⊗ z_i)) ≤ rank(L T) - 1 < rank(L T), contradicting subadditivity.
The rank of the sum of two complex matrices is at most the sum of their individual ranks: rank(A + B) ≤ rank(A) + rank(B).
Matrix rank is defined as the dimension of the range of the associated linear map. Because (A + B)v = Av + Bv, the range of A + B is contained in the span (join) of the ranges of A and B. By monotonicity of submodule dimension and the fact that dim(U ⊔ V) ≤ dim(U) + dim(V), the rank of A + B is at most rank(A) + rank(B).
uses
Matrix.mulVecLin_add,Submodule.finrank_mono,LinearMap.range_add_le,Submodule.finrank_add_le_finrank_add_finranklemma not_sum_pure_of_linear_flattening_potency_gt_rank_add_le {m n : Type*} [Fintype n] (A B : Matrix m n ℂ) : (A + B).rank ≤ A.rank + B.rank := by unfold Matrix.rank rw [Matrix.mulVecLin_add] calc Module.finrank ℂ ↥(A.mulVecLin + B.mulVecLin).range ≤ Module.finrank ℂ ↥(A.mulVecLin.range ⊔ B.mulVecLin.range) := Submodule.finrank_mono (LinearMap.range_add_le _ _) _ ≤ Module.finrank ℂ ↥A.mulVecLin.range + Module.finrank ℂ ↥B.mulVecLin.range := Submodule.finrank_add_le_finrank_add_finrank _ _
For any finite set s and family of matrices A_i, the rank of their sum is at most the sum of their ranks: rank(∑_{i ∈ s} A_i) ≤ ∑_{i ∈ s} rank(A_i).
This is proved by induction on the finite set s using `Finset.induction`. If s is empty, both sides vanish, giving 0 ≤ 0. For the inductive step, adding an element a ∉ s splits the sum into A_a + ∑_{i ∈ s} A_i. The claim follows by applying rank subadditivity for two matrices to this split and applying the induction hypothesis via congruence (`gcongr`).
uses
Finset.induction,Finset.sum_insert,not_sum_pure_of_linear_flattening_potency_gt_rank_add_lelemma not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le {m n : Type*} [Fintype n] {ι : Type*} (s : Finset ι) (A : ι → Matrix m n ℂ) : (∑ i ∈ s, A i).rank ≤ ∑ i ∈ s, (A i).rank := by classical induction s using Finset.induction with | empty => simp | insert a s ha ih => rw [Finset.sum_insert ha, Finset.sum_insert ha] calc (A a + ∑ i ∈ s, A i).rank ≤ (A a).rank + (∑ i ∈ s, A i).rank := not_sum_pure_of_linear_flattening_potency_gt_rank_add_le _ _ _ ≤ (A a).rank + ∑ i ∈ s, (A i).rank := by gcongr
Assuming for contradiction that T is a sum of r pure tensors, rank(L T) is bounded above by the sum of the ranks of each flattened component.
Assume T = ∑_{i=1}^r x_i ⊗ y_i ⊗ z_i for contradiction. Linearity of L distributes it across the sum (`map_sum`), giving L(T) = ∑_{i=1}^r L(x_i ⊗ y_i ⊗ z_i). Applying subadditivity of matrix rank over finite sums (`not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le`) to the full index set `Finset.univ` gives rank(L T) ≤ ∑_{i=1}^r rank(L(x_i ⊗ y_i ⊗ z_i)).
uses
map_sum,not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le,Finset.univ/-- A tensor witnessing potency > r for L cannot be expressed as a sum of r pure tensors. -/ theorem not_sum_pure_of_linear_flattening_potency_gt {n u v : ℕ} (L : (Fin n → Fin n → Fin n → ℂ) →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (r : ℕ) (T : Fin n → Fin n → Fin n → ℂ) (hT : ∀ x y z : Fin n → ℂ, r * (L (tensor3_pure x y z)).rank < (L T).rank) (x y z : Fin r → Fin n → ℂ) : T ≠ ∑ i, tensor3_pure (x i) (y i) (z i) := by intro hsum classical have hL : L T = ∑ i : Fin r, L (tensor3_pure (x i) (y i) (z i)) := by rw [hsum, map_sum] have hrank : (L T).rank ≤ ∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank := by rw [hL] exact not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le Finset.univ _
For each i, the potency hypothesis yields r * rank(L(x_i ⊗ y_i ⊗ z_i)) < rank(L T), and the case r = 0 leads to an immediate contradiction.
Specializing the potency hypothesis hT to each component gives r * rank(L(x_i ⊗ y_i ⊗ z_i)) < rank(L T) for all i. A case split on r = 0 shows that if r = 0, the empty sum gives rank(L T) ≤ 0. However, evaluating the potency condition at the zero vectors yields 0 < rank(L T). Linear integer arithmetic (`omega`) closes this case due to the contradiction between rank(L T) ≤ 0 and rank(L T) > 0.
have hlt : ∀ i : Fin r, r * (L (tensor3_pure (x i) (y i) (z i))).rank < (L T).rank := fun i => hT (x i) (y i) (z i) by_cases hr : r = 0 · subst hr have hb : (L T).rank ≤ 0 := by simpa using hrank have hpos : 0 < (L T).rank := by have := hT (fun _ => 0) (fun _ => 0) (fun _ => 0) simpa using this omega
When r > 0, summing the potency bounds over all r terms implies that the sum of ranks is strictly less than rank(L T), contradicting subadditivity and completing the proof.
Since r ≠ 0, we have r > 0 (`Nat.pos_of_ne_zero`). Since r * rank(L(x_i ⊗ y_i ⊗ z_i)) < rank(L T) in ℕ, each term satisfies r * rank(L(x_i ⊗ y_i ⊗ z_i)) ≤ rank(L T) - 1 (`Nat.le_sub_one_of_lt`). Distributing r over the sum (`Finset.mul_sum`) and summing these bounds using `Finset.sum_le_sum` gives r * ∑ rank(L(x_i ⊗ y_i ⊗ z_i)) ≤ r * (rank(L T) - 1), where `Finset.sum_const` evaluates the sum of the constant over r terms. Dividing by r > 0 (`Nat.le_of_mul_le_mul_left`) yields ∑ rank(L(x_i ⊗ y_i ⊗ z_i)) ≤ rank(L T) - 1. Moreover, the index 0 exists because r > 0, and the potency bound at index 0 shows rank(L T) > 0 (`lt_of_le_of_lt`, `Nat.zero_le`). Linear integer arithmetic (`omega`) deduces False from rank(L T) ≤ ∑ rank(L(...)) ≤ rank(L T) - 1 and rank(L T) > 0.
uses
Nat.pos_of_ne_zero,Finset.mul_sum,Finset.sum_le_sum,Nat.le_sub_one_of_lt,Finset.sum_const,Nat.le_of_mul_le_mul_left,lt_of_le_of_lt,Nat.zero_le· have hrpos : 0 < r := Nat.pos_of_ne_zero hr have hmul : r * (∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank) ≤ r * ((L T).rank - 1) := by rw [Finset.mul_sum] calc ∑ i : Fin r, r * (L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ _i : Fin r, ((L T).rank - 1) := Finset.sum_le_sum (fun i _ => Nat.le_sub_one_of_lt (hlt i)) _ = r * ((L T).rank - 1) := by simp [Finset.sum_const] have hle : (∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank) ≤ (L T).rank - 1 := Nat.le_of_mul_le_mul_left hmul hrpos have hbpos : 0 < (L T).rank := by have h0 := hlt ⟨0, hrpos⟩ exact lt_of_le_of_lt (Nat.zero_le _) h0 omega
Matrix.mulVecLin_add- The linear map associated with the sum of two matrices is the sum of their associated linear maps.
Submodule.finrank_mono- If a submodule is contained in another, its dimension (finrank) is less than or equal to that of the containing submodule.
LinearMap.range_add_le- The range of the sum of two linear maps is contained in the span (join) of their individual ranges.
Submodule.finrank_add_le_finrank_add_finrank- The dimension of the sum (join) of two submodules is at most the sum of their dimensions.
Finset.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_insert- Inserting an element not already present into a finite set adds its evaluation to the sum over the set.
not_sum_pure_of_linear_flattening_potency_gt_rank_add_le- The rank of the sum of two complex matrices is at most the sum of their ranks.
map_sum- An additive homomorphism or linear map distributes over finite sums.
not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le- The rank of a finite sum of complex matrices is at most the sum of their individual ranks.
Finset.univ- The universal finite set containing all elements of a finite type.
Nat.pos_of_ne_zero- A natural number that is not zero is strictly positive.
Finset.mul_sum- Multiplication distributes over finite sums from the left.
Finset.sum_le_sum- A sum of pointwise smaller terms over a finite set is less than or equal to the sum of the larger terms.
Nat.le_sub_one_of_lt- For natural numbers, if a < b, then a ≤ b - 1.
Finset.sum_const- Summing a constant value over a finite set equals the cardinality of the set times that constant.
Nat.le_of_mul_le_mul_left- For natural numbers, if c * a ≤ c * b and c > 0, then a ≤ b.
lt_of_le_of_lt- If a ≤ b and b < c, then a < c (transitivity of non-strict and strict inequality).
Nat.zero_le- Zero is less than or equal to any natural number.
- The proof uses the `omega` tactic to automatically handle integer arithmetic contradictions in both the r = 0 and r > 0 branches, and `simpa` to automatically evaluate empty sums over `Fin 0` to zero.
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 not_sum_pure_of_linear_flattening_potency_gt_rank_add_le {m n : Type*} [Fintype n] (A B : Matrix m n ℂ) : (A + B).rank ≤ A.rank + B.rank := by unfold Matrix.rank rw [Matrix.mulVecLin_add] calc Module.finrank ℂ ↥(A.mulVecLin + B.mulVecLin).range ≤ Module.finrank ℂ ↥(A.mulVecLin.range ⊔ B.mulVecLin.range) := Submodule.finrank_mono (LinearMap.range_add_le _ _) _ ≤ Module.finrank ℂ ↥A.mulVecLin.range + Module.finrank ℂ ↥B.mulVecLin.range := Submodule.finrank_add_le_finrank_add_finrank _ _lemma not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le {m n : Type*} [Fintype n] {ι : Type*} (s : Finset ι) (A : ι → Matrix m n ℂ) : (∑ i ∈ s, A i).rank ≤ ∑ i ∈ s, (A i).rank := by classical induction s using Finset.induction with | empty => simp | insert a s ha ih => rw [Finset.sum_insert ha, Finset.sum_insert ha] calc (A a + ∑ i ∈ s, A i).rank ≤ (A a).rank + (∑ i ∈ s, A i).rank := not_sum_pure_of_linear_flattening_potency_gt_rank_add_le _ _ _ ≤ (A a).rank + ∑ i ∈ s, (A i).rank := by gcongr/-- A tensor witnessing potency > r for L cannot be expressed as a sum of r pure tensors. -/theorem not_sum_pure_of_linear_flattening_potency_gt {n u v : ℕ} (L : (Fin n → Fin n → Fin n → ℂ) →ₗ[ℂ] Matrix (Fin u) (Fin v) ℂ) (r : ℕ) (T : Fin n → Fin n → Fin n → ℂ) (hT : ∀ x y z : Fin n → ℂ, r * (L (tensor3_pure x y z)).rank < (L T).rank) (x y z : Fin r → Fin n → ℂ) : T ≠ ∑ i, tensor3_pure (x i) (y i) (z i) := by intro hsum classical have hL : L T = ∑ i : Fin r, L (tensor3_pure (x i) (y i) (z i)) := by rw [hsum, map_sum] have hrank : (L T).rank ≤ ∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank := by rw [hL] exact not_sum_pure_of_linear_flattening_potency_gt_rank_sum_le Finset.univ _ have hlt : ∀ i : Fin r, r * (L (tensor3_pure (x i) (y i) (z i))).rank < (L T).rank := fun i => hT (x i) (y i) (z i) by_cases hr : r = 0 · subst hr have hb : (L T).rank ≤ 0 := by simpa using hrank have hpos : 0 < (L T).rank := by have := hT (fun _ => 0) (fun _ => 0) (fun _ => 0) simpa using this omega · have hrpos : 0 < r := Nat.pos_of_ne_zero hr have hmul : r * (∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank) ≤ r * ((L T).rank - 1) := by rw [Finset.mul_sum] calc ∑ i : Fin r, r * (L (tensor3_pure (x i) (y i) (z i))).rank ≤ ∑ _i : Fin r, ((L T).rank - 1) := Finset.sum_le_sum (fun i _ => Nat.le_sub_one_of_lt (hlt i)) _ = r * ((L T).rank - 1) := by simp [Finset.sum_const] have hle : (∑ i : Fin r, (L (tensor3_pure (x i) (y i) (z i))).rank) ≤ (L T).rank - 1 := Nat.le_of_mul_le_mul_left hmul hrpos have hbpos : 0 < (L T).rank := by have h0 := hlt ⟨0, hrpos⟩ exact lt_of_le_of_lt (Nat.zero_le _) h0 omega