AFTD Auto-Formalizing Theoretical Domains

not_sum_pure_of_linear_flattening_potency_gt

theoremverified

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

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.

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

    lines 1–10

    uses Matrix.mulVecLin_add, Submodule.finrank_mono, LinearMap.range_add_le, Submodule.finrank_add_le_finrank_add_finrank

    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 _ _
  2. 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`).

    lines 12–24

    uses Finset.induction, Finset.sum_insert, not_sum_pure_of_linear_flattening_potency_gt_rank_add_le

    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
    
  3. 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)).

    lines 25–38

    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 _
  4. 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.

    lines 39–47

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

    lines 48–63

    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.

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

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