Source-linked AI summary
Explicit tensors beyond the linear flattening barrier
Benjamin Lovitz
TL;DR
The paper addresses the challenge of constructing explicit tensors with high border rank. It develops explicit tensors and analyzes the reach of linear flattenings, obtaining a 3n-o(n) lower bound alongside a 2n−2 limit for equations from the linear-flattening method.
Problem
A central challenge is to exhibit explicit tensors with provably high border rank.
Source: §1 · p. 1Method
The paper constructs polynomial-time explicit tensors and studies equations for border-rank varieties obtained by linear flattenings.
Source: §1 · p. 2Results
3n-o(n) is the lower bound on the border rank of an explicit tensor, while the linear-flattening method yields equations for σ_r only when r≤2n−2.
Source: §1 · pp. 2–3Takeaways & Limitations
The constructed tensors have higher border rank than the threshold at which the linear-flattening method can yield equations.
Source: §1 · pp. 2–3The paper's definition of the linear-flattening method excludes minors that might yield equations for larger σ_r through a different argument.
Source: §1 · p. 2
Abstract
from arXiv · showhide
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\'nski 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.
1 Introduction
The paper constructs explicit tensors with border rank at least 3n-o(n) and determines the limits of the linear-flattening method, including exact sharpness for odd n. Its proof overview combines border substitution with Koszul flattenings on restricted tensors, and it leaves open whether explicit tensors can exceed 3n.
1 Introduction
- 3n-o(n) is the new lower bound on the border rank of an explicit tensor, improving the previous (2+ε)n record.The construction is polynomial-time explicit under the paper's definition: its integer entries can be recorded in binary in polynomial time.Source: §1 · pp. 1–2
1.1 Proof overviews
- For odd n, the central Koszul flattening reaches the upper bound, improving the prior 2n−4 bound and extending the n=5 case to arbitrary n.For even n, the cited construction uses a Koszul flattening composed with projection of the first factor onto C^(n−1).Source: §1 · pp. 2–3
1 Introduction
- The linear-flattening method yields equations for σ_r only when r≤2n−2; odd n attains this endpoint, while even n attains r=2n−3.The paper determines Π(n) exactly for odd n and to within a vanishing additive gap for even n.Source: §1 · pp. 2–3
1.1 Proof overviews
- The explicit-tensor proof combines roughly n from border substitution with 2n from Koszul flattenings on restricted tensors.The block support pattern k=i+j and a pigeonhole argument yield a block upper-triangular submatrix whose rank can be analyzed.Source: §1.1 · p. 3
1.2 Open questions
- Whether explicit tensors of border rank (or even tensor rank) greater than 3n exist remains open; answering this requires techniques beyond border substitution and linear flattenings on restricted tensors, such as border apolarity [18] [19] or Kronecker-Young flattenings [20].Source: §1.2 · p. 4
2 Background
This section introduces the tensor tools and linear-algebra background used in the paper, including Koszul flattenings and border substitution.
2 Background
- A tensor is A-concise when its contraction map from A* is injective.The section also treats tensors as maps A* → B ⊗ C and B ⊗ C as maps B* → C.Source: §2 · p. 5
- A Vandermonde matrix is invertible exactly when its evaluation points are pairwise distinct.The section also defines v_h(t) = (1, t, …, t^(h−1))^T and C[t]_<h as polynomials of degree less than h.Source: §2 · p. 5
- Koszul flattenings are defined degree by degree for tensors in A ⊗ B ⊗ C, by extending their action on rank-one tensors linearly.The section states that a rank inequality for these maps persists for tensors of border rank at most r because the condition is closed.Source: §2 · p. 6
- Border substitution bounds a concise tensor’s rank through a restriction to a lower-dimensional subspace of its first factor.For a q-dimensional restriction W, the lemma gives R(T|W) ≤ R(T) − n + q.Source: §2 · p. 7
3 An explicit construction
The section constructs a tensor whose restricted Koszul flattenings contain structured matrix blocks, then uses their ranks and border substitution to obtain a lower bound.
3 An explicit construction
- The construction’s Koszul matrix is invertible when every e-vector subset in each of two associated vector collections is linearly independent.The proof uses a kernel argument and the independence of the corresponding c-vectors to show injectivity.Source: §3 · p. 7
- The determinant of Mf(t) has roots whose multiplicities are at least the nullities of Mf(a) at the corresponding evaluation points.Row operations at each a expose r zero rows when r = dim ker Mf(a), so (t − a)^r divides the determinant.Source: §3 · p. 8
3.1 The tensor and its border rank
- Te,m is defined on three spaces of dimension me², with nonzero coordinates on k = i + j given by powers 2^(α(j+u+v)).The construction verifies A-conciseness using the Vandermonde matrix [2^(αj)] and its invertibility.Source: §3.1 · p. 9
- The restriction argument selects covectors whose associated polynomials are monic and have distinct degrees.Border substitution and zero-padding then transfer a restriction lower bound to the ambient construction.Source: §3.1 · pp. 9, 11
- The retained Koszul matrix is block upper triangular, with diagonal blocks Mf(2j), so their ranks contribute to its rank.The diagonal block arises by projecting the restriction onto E ⊗ Bj ⊗ Cj+i.Source: §3.1 · p. 10
4 Proof of the flattening barrier
The section proves an upper bound on the potency of every nonzero linear flattening, using random matrices and moment estimates.
4 Proof of the flattening barrier
- The proof supplies an elementary argument for a lemma that can also be obtained from the Kempf–Ness theorem.The stated alternative uses the theorem for tensors in [26, Theorem 4].Source: §4 · p. 11
- For independent random unit vectors x, y, z, the proof forms a random matrix M from the coefficient matrices Mijk.The matrices are selected so that the proof can apply the moment estimate to M.Source: §4 · pp. 12, 15
- The rank bound on M and a fourth-moment estimate yield the inequality used to bound Pot(L).The proof combines Cauchy–Schwarz for M’s nonzero squared singular values with the estimate involving ρ and r.Source: §4 · p. 15
- Pot(L) ≤ 2n²/(n + 1) = 2n − 2 + 2/(n + 1), yielding the section’s upper bound on Π(n).The proof takes the supremum over nonzero linear flattenings after bounding Pot(L).Source: §4 · pp. 11, 15
5 Sharpness of the flattening barrier in odd dimensions
For odd n, the upper bound on Π(n) is sharp and is attained by a Koszul flattening. The proof constructs a tensor whose central Koszul flattening is invertible.
5 Sharpness of the flattening barrier in odd dimensions
- For odd n, the upper bound on Π(n) is sharp and is attained by a Koszul flattening.Source: §5 · p. 15
- The proof constructs a tensor S_n for which K_p(S_n) is invertible.The construction reduces sharpness to finding a tensor with an invertible central Koszul flattening.Source: §5 · p. 15
- Kernel constraints force each f_I to have p+1 distinct double roots despite degree at most 2p, making K_p(S_n) injective and, since it is square, invertible.Source: §5 · p. 18