Explicit tensors with quadratic border rank
Let $\underline{R}$ denote border rank over $\mathbb{C}$, a tensor in $\mathbb{Q}^{n \times n \times n}$ being regarded as one in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$. For $n > 3$, a generic tensor in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$ has border rank $\lceil n^3/(3n-2) \rceil$, which is asymptotic to $n^2/3$ (Lickteig). Landsberg and Michałek gave a sequence of tensors in $\mathbb{C}^n \otimes \mathbb{C}^n \otimes \mathbb{C}^n$, the $n$-th computable in time polynomial in $n$, of border rank at least $2.02n$ for every sufficiently large $n$. Lovitz reports explicit tensors of this kind, with integer entries, of border rank at least $3n - 11n^{3/4}$.
Problem. Construct tensors $T_n \in \mathbb{Q}^{n \times n \times n}$ such that a single deterministic algorithm, given $n$, outputs the entries of $T_n$, each as an integer numerator and denominator in binary, in time polynomial in $n$, and prove that $\underline{R}(T_n) \ge c n^2$ for some constant $c > 0$ and every sufficiently large $n$.
Source: Stated by OpenProblemsInNLA, after Landsberg and Michałek (2025), Section 1, who take up the 'hay in a haystack' problem (find an explicit object that behaves generically) for three-way tensors, explicit as in their Definition 1.1.
Imported from github.com/ajt60gaibb/OpenProblemsInNLA.
Classification
- Primary
- AG — Algebraic Geometry
- Secondary
- NA
- Keywords
- border rank, explicit tensors, OpenProblemsInNLA
- Literature checked
- Oct. 8, 2026 by clemens-admin
References
@article{landsberg2025,
author = {Landsberg, Joseph M. and Micha{\l}ek, Mateusz},
title = {Towards Finding Hay in a Haystack: Explicit Tensors of Border Rank Greater Than $2.02m$ in $\mathbb{C}^m\otimes\mathbb{C}^m\otimes\mathbb{C}^m$},
journal = {Theory Comput.},
volume = {21},
number = {13},
year = {2025},
pages = {1--17},
doi = {10.4086/toc.2025.v021a013},
eprint = {1912.11927},
archivePrefix = {arXiv},
}
@article{lickteig1985,
author = {Lickteig, Thomas},
title = {Typical tensorial rank},
journal = {Linear Algebra Appl.},
volume = {69},
year = {1985},
pages = {95--120},
doi = {10.1016/0024-3795(85)90070-9},
}
@misc{lovitz2026,
author = {Lovitz, Benjamin},
title = {Explicit tensors beyond the linear flattening barrier},
year = {2026},
eprint = {2610.08504},
archivePrefix = {arXiv},
}
@misc{openproblemsinnla-ac06,
author = {Townsend, Alex},
title = {{AC-06}: Explicit tensors with quadratic border rank},
howpublished = {Open Problems in Numerical Linear Algebra, GitHub repository},
year = {2026},
url = {https://github.com/ajt60gaibb/OpenProblemsInNLA/blob/main/arithmetic-and-complexity/AC-06/README.md},
note = {Read at commit b8c7852, 2026-10-07},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00182, "Explicit tensors with quadratic border rank", clopen.solutions.