Explicit tensors break past linear flattening rank limits
Explicit tensors beyond the linear flattening barrier
Data Structures and Algorithms
Summary
Figuring out how to measure the complexity of three-way data arrays, called tensors, is important but challenging. The authors created explicit examples of tensors that have higher complexity than previously known examples could show using a common method called linear flattening. They also proved a fundamental limit on how good linear flattening can be at measuring this complexity. This work helps clarify how certain mathematical tools can or cannot capture the true complexity of tensors.
What this means in practice
- •For computer algebra system developers: Design verification routines that recognize tensors with higher complexity beyond linear flattening-based measures.
- •For quantum computing engineers: Evaluate limitations of standard tensor approximation tools when simulating quantum states or operations with complex entanglement structures.
A theory result. No direct application yet.
Authors
Benjamin Lovitz
Abstract
We construct explicit n x n x n tensors of border rank at least 3n-o(n), improving the previous record of (2 + $\varepsilon$)n due to (Landsberg and Michalek 2025). We also prove that the linear flattening method cannot be used to establish lower bounds on border rank beyond 2n-1. When n is odd, we prove that this bound is achieved by Koszul flattenings. When n is even, a result of (Landsberg 2015) shows that Koszul flattenings can achieve 2n-2, leaving an open gap of size one. Our 2n-1 bound improves the best known 6n-4 linear flattening barrier due to (Garg et al. 2019) and (Buczyński 2026). Combined, these results show that our 3n-o(n) construction, as well as the construction of Landsberg and Michalek, provide explicit examples of tensors with higher border rank than any linear flattening can achieve.