Asymptotic Rank of Complete Graph Tensors

Source abstract

Graph tensors extend the matrix multiplication tensor by placing a two-party identity tensor on every edge of a graph and keeping one tensor leg at every vertex. We study the asymptotic rank of the tensor associated with the complete graph. For every integer $n\geq 2$, over the complex numbers, we prove $$\left\lfloor\frac{n^2}{4}\right\rfloor \leq \log_2\widetilde R\bigl(\mathsf{GT}_2(K_n)\bigr) \leq \frac{n^2}{4}.$$ The upper bound matches the maximum-cut lower bound for every even $n$ and differs from it by only $1/4$ for every odd $n$. In particular, the exponent per edge is below $2/3$ for every $n\geq5$, answering a question of Christandl, Vrana, and Zuiddam. Our proof extends the polynomial multiplication approach underlying OpenAI's bound $ω\leq9/4$. The main step separates any fixed number of shared tensor legs simultaneously, using only linearly many direct-sum copies in the number of blocks. This yields an entropy inequality for higher-order tensors. We apply it to the tensor for multiplying $n-1$ polynomials, whose rank is linear in the input length. Discrete concavity and a shifted tripling inequality then force a lower bound on a symmetrized spectral profile. Comparing this growth with polynomial interpolation gives the stated upper bound while preserving all $n$ tensor legs. We also prove an operational barrier for these higher-order polynomial constructions. For $n\geq3$, the specified formal reduction rules cannot certify an exponent below $n^2/4$ for $\mathsf{GT}_2(K_n)$, even after taking tensor powers and allowing subexponential overhead and common auxiliary factors. This extends the symmetric three-leg barrier of Amanov, van den Berg, and Zuiddam and explains the remaining gap for odd complete graphs within this method.