Theorem 1.14 — there is a rational tensor A ∈ ℚ^{2×2×2} with rank_ℝ(A) < rank_ℚ(A)
ProvedTensorNP.Rank.theorem_1_14p2o-batch-pfp2bp2o-gran-per-chapterp2o-plan-paperp2o-v1rational-pointstensor-rank
Tensor rank depends on the field. There is a tensor with rational entries such that
where is the rank (6) computed with coefficients and vectors from the field .
For matrices the rank does not change when the field is enlarged; this theorem shows that for 3-tensors it can, even between and . In particular Håstad's NP-hardness of tensor rank over does not transfer to automatically.
Formalization Note The existential is the printed statement. The milestones of this mission concern the paper's explicit tensor , for which . The real rank is the rank of with its entries cast to .
Preamble
import Mathlib import Definitions.Def_TensorNP_Rank_Defs
Formal statement
namespace TensorNP.Rank
theorem theorem_1_14 :
∃ A : Fin 2 → Fin 2 → Fin 2 → ℚ,
rankOver ℝ (fun i j k => (A i j k : ℝ)) < rankOver ℚ A := 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:11, Theorem 1.14 (proof p. 0:26)
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.