Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Proof of Theorem 1.14, (29) — rank ≤ 2 gives two outer products, and (29) for A is the system (30)

Proved
TensorNP.Rank.eq29_iff_system30

by mikedeng1 · Oct 7, 2026 · Mathlib 0df444a (Lean v4.33.1)

p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rational-pointstensor-rank

This item makes precise the step "Suppose not and that there exist ui,vi∈Q2\mathbf u_i, \mathbf v_i \in \mathbb Q^2ui​,vi​∈Q2 with (29). Identity (29) gives eight equations found in (30)" of the proof of Theorem 1.14. It has two parts.

  1. Let EEE be a field and B∈El×m×n\mathcal B \in E^{l\times m\times n}B∈El×m×n. If rank⁡E(B)≤2\operatorname{rank}_E(\mathcal B) \le 2rankE​(B)≤2, then there are u1,v1∈El\mathbf u_1,\mathbf v_1 \in E^lu1​,v1​∈El, u2,v2∈Em\mathbf u_2,\mathbf v_2\in E^mu2​,v2​∈Em, u3,v3∈En\mathbf u_3,\mathbf v_3 \in E^nu3​,v3​∈En with B=u1⊗u2⊗u3+v1⊗v2⊗v3\mathcal B = \mathbf u_1\otimes\mathbf u_2\otimes\mathbf u_3 + \mathbf v_1\otimes\mathbf v_2\otimes\mathbf v_3B=u1​⊗u2​⊗u3​+v1​⊗v2​⊗v3​.
  2. Let KKK be a field of characteristic zero, A\mathcal AA the rational tensor of Theorem 1.14 with entries read in KKK, and ui=[ai,bi]⊤\mathbf u_i = [a_i,b_i]^\topui​=[ai​,bi​]⊤, vi=[ci,di]⊤∈K2\mathbf v_i = [c_i,d_i]^\top \in K^2vi​=[ci​,di​]⊤∈K2 for i=1,2,3i = 1,2,3i=1,2,3. Then
A=u1⊗u2⊗u3+v1⊗v2⊗v3(29)\mathcal A = \mathbf u_1\otimes\mathbf u_2\otimes\mathbf u_3 + \mathbf v_1\otimes\mathbf v_2\otimes\mathbf v_3 \tag{29}A=u1​⊗u2​⊗u3​+v1​⊗v2​⊗v3​(29)

holds if and only if a1,…,d3a_1,\dots,d_3a1​,…,d3​ satisfy the eight equations (30).

Applied with E=K=QE = K = \mathbb QE=K=Q, the two parts turn "rank⁡Q(A)≤2\operatorname{rank}_{\mathbb Q}(\mathcal A) \le 2rankQ​(A)≤2" into a rational solution of (30).

Formalization Note The paper only says "suppose not"; part 1 is the step that absorbs the scalars λs\lambda_sλs​ and pads a decomposition with fewer than two terms by zero terms. It is stated for an arbitrary tensor over an arbitrary field so that it is not vacuous (for the paper's A\mathcal AA over Q\mathbb QQ its hypothesis is false, by Lemma 8.1). Part 2 is stated over every field of characteristic zero for the same reason; over R\mathbb RR both sides hold for the decomposition of the first milestone. The paper says (29) "gives" (30); the equivalence states that (30) is exactly the entrywise reading of (29). Vectors are indexed from 0, so aia_iai​ is u_i 0 and bib_ibi​ is u_i 1.

Preamble
import Mathlib
import Definitions.Def_TensorNP_Rank_Defs
import Definitions.Def_TensorNP_Rank_Construction
Formal statement
namespace TensorNP.Rank

theorem eq29_iff_system30 :
    (∀ {E : Type} [Field E] {l m n : ℕ} (B : Fin l → Fin m → Fin n → E),
      rankOver E B ≤ 2 →
        ∃ (u₁ v₁ : Fin l → E) (u₂ v₂ : Fin m → E) (u₃ v₃ : Fin n → E),
          B = outer u₁ u₂ u₃ + outer v₁ v₂ v₃) ∧
    (∀ {K : Type} [Field K] [CharZero K] (u₁ u₂ u₃ v₁ v₂ v₃ : Fin 2 → K),
      ((fun i j k => (tensorA i j k : K)) = outer u₁ u₂ u₃ + outer v₁ v₂ v₃ ↔
        System30 (u₁ 0) (u₂ 0) (u₃ 0) (u₁ 1) (u₂ 1) (u₃ 1)
          (v₁ 0) (v₂ 0) (v₃ 0) (v₁ 1) (v₂ 1) (v₃ 1))) := by sorry

end TensorNP.Rank
Source
Hillar & Lim, Most Tensor Problems Are NP-Hard, J. ACM 60(6) (2013), Art. 45 (final version, arXiv:0911.1393v5), p. 0:26, proof of Theorem 1.14, (29)
Human review
  • Endorsed by Shuze Chen · Oct 8, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 8, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me