Theorem 3.5 — the zero-padded block tensor has border rank
OpenExplicitTensorBarrier694.Explicit.Supplement.theorem_3_5complexity-theorylinear-algebrap2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-border-rank
Let , and set
Let be obtained by zero-padding the block tensor of equation (3.2). Then its complex border rank satisfies
This is Theorem 1.1 in more detail: it pins the specific explicit witness, while the mission goal only asserts that some polynomial-time explicit family exists. This is a paper-proved result awaiting a formal proof.
Differences from the source:
- encoding: T_n obtained by zero-padding T_{e,m}, e = ⌊n^{1/4}⌋, m = ⌊n/e²⌋ → complexify (explicitFamily n) from the published Construction definition; reason: for n ≥ 16 explicitFamily n is exactly blockEntry (fourthRoot n) (n / fourthRoot n ^ 2), zero outside the me² × me² × me² block, and fourthRoot is the integer floor of the fourth root
- encoding: border rank R̲ → the published borderRank (least r with T in the closure of the rank ≤ r locus); reason: sequential limits and closure agree in finite-dimensional complex space
Preamble
import Mathlib import Definitions.Def_ExplicitTensorBarrier694_Explicit_Construction
Formal statement
namespace ExplicitTensorBarrier694.Explicit.Supplement
open ExplicitTensorBarrier694.Explicit
/-- Lovitz, STOC 2027 submission #694 (October 2026), Theorem 3.5, p.11. For n ≥ 16, with
e = ⌊n^{1/4}⌋ and m = ⌊n/e²⌋, the tensor T_n ∈ (ℂⁿ)^{⊗3} obtained by zero-padding T_{e,m}
(the published `explicitFamily n`, complexified) has border rank ≥ 3n − 11 n^{3/4}. -/
theorem theorem_3_5 (n : ℕ) (hn : 16 ≤ n) :
3 * (n : ℝ) - 11 * (n : ℝ) ^ ((3 : ℝ) / 4) ≤
(borderRank (complexify (explicitFamily n)) : ℝ) := by sorry
end ExplicitTensorBarrier694.Explicit.Supplement
Source
Benjamin Lovitz, STOC 2027 submission #694 (October 2026), Theorem 3.5, equation (3.3), p.11; T_{e,m} equation (3.2), p.9 (PDF same); https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/694.pdf