Asymptotic Rank of Complete Graph Tensors
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≥ 2, over the complex numbers, we prove ⌊n2/4⌋ ≤ log2R̃(GT2(Kn)) ≤ n2/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≥5, answering a question of Christandl, Vrana, and Zuiddam. Our proof extends the polynomial multiplication approach underlying OpenAI's bound ω≤9/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≥3, the specified formal reduction rules cannot certify an exponent below n2/4 for GT2(Kn), 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.
Related
- Statistical inference for low-rank tensors: Heteroskedasticity, subgaussianity, and applications
- Maximal rank of 4× 4× 4 and k× 4× 3 tensors over 𝔽2
- Upper Bounds on the Strassen CP Rank Gap and Symmetric Rank Gap of Third-Order Tensors
- Rank and Border Rank Additivity of Complex Tensors with a Hankel Summand
- Low-Rank Single-Index Bandits with Unknown Links: From Matrices to Tensors
BibTeX
@misc{zhou2026asymptotic,
title = {{Asymptotic Rank of Complete Graph Tensors}},
author = {Huanyi Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.34273},
eprint = {2610.34273},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.34273},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Asymptotic Rank of Complete Graph Tensors
AU - Huanyi Zhou
PY - 2026
DA - 2026/10/25
PB - arXiv
DO - 10.48550/arxiv.2610.34273
UR - https://arxiv.org/abs/2610.34273
AB - 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≥ 2, over the complex numbers, we prove ⌊n^2/4⌋ ≤ log_2R̃(GT_2(K_n)) ≤ 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≥5, answering a question of Christandl, Vrana, and Zuiddam. Our proof extends the polynomial multiplication approach underlying OpenAI's bound ω≤9/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≥3, the specified formal reduction rules cannot certify an exponent below n^2/4 for 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.
ER -