PaperlayerView exact revision on arXiv

Source-linked AI summary

Asymptotic Rank of Complete Graph Tensors

Huanyi Zhou

arXiv:2610.34273v1cs.CCcs.DMmath.CO

TL;DR

Whether the maximum-cut lower bound determines the asymptotic rank of complete graph tensors remains open; for the triangle, this is equivalent to whether ω = 2. The proof separates shared tensor legs simultaneously, derives an entropy inequality, and applies it to polynomial tensors with n−1 independent inputs. The upper bound is exact for even n, and for odd n its gap over the standard cut lower bound is only 1/4.

  • Problem

    Whether the maximum-cut lower bound determines the asymptotic rank of complete graph tensors remains open; for the triangle, this is equivalent to whether ω = 2.

    Source: §1.1 · p. 4

  • Method

    The proof separates shared tensor legs simultaneously, derives an entropy inequality, and applies it to polynomial tensors with n−1 independent inputs.

    Source: §1.3 · pp. 7–8, §3 · p. 20

  • Results

    The upper bound is exact for even n, and for odd n its gap over the standard cut lower bound is only 1/4.

    Source: §1.2 · p. 5

  • Takeaways & Limitations

    The specified polynomial-construction rules cannot certify an exponent below n^2/4, even with tensor powers and subexponential overhead.

    Source: §1.4 · pp. 8, 10

    The barrier applies to the specified formal rules, not all complex tensors, and it leaves open whether odd complete graphs have the extra 1/4 gap in their true asymptotic rank.

    Source: §1.4 · p. 10

Abstract

from arXiv · show

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 $\omega\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.

1 Introduction

The paper extends polynomial-multiplication methods to bound the asymptotic rank of complete graph tensors while preserving each vertex as a separate tensor leg, and examines the limits of specified formal polynomial-reduction constructions. Those rules impose an exponent threshold of n²/4 even with tensor powers and subexponential overhead; this matches the maximum-cut bound for even complete graphs, while the odd-n gap remains unresolved by these constructions.

1.1 Graph tensors and previous bounds

  • Christandl, Vrana, and Zuiddam [CVZ19] asked whether the maximum cut determines asymptotic rank; the prior 3/4-per-edge baseline still left a quadratic gap from that cut.For triangle tensors, the question is whether the matrix multiplication exponent ω equals 2.Source: §1.1 · pp. 4–5

1.2 Our rank bound and its context

  • For every n ≥ 2, the logarithmic asymptotic-rank bounds are floor(n^2/4) ≤ log_2 R̃(GT_2(K_n)) ≤ n^2/4; they coincide for even n and differ by 1/4 for odd n.The resulting exponent per edge is below 2/3 for every n ≥ 5, and the maximum-cut lower bound is tight for every even complete graph.Source: §1.2 · pp. 5–6

1.3 The polynomial method in higher order

  • The higher-order method separates n − 2 shared legs simultaneously using only linearly many source copies, then applies an entropy inequality to polynomial tensors with n − 1 independent inputs.The polynomial tensor has rank D = 1 + sum of its input lengths; when all lengths equal a, its rank is O_n(a).Source: §1.3 · p. 7
  • Discrete concavity and shifted tripling force the symmetrized spectral profile to grow at least as a^(2(n−1)/n), which, compared with interpolation, yields the upper bound n^2/4.The growth argument increases the diagonal profile by at least 1 + 2/(na) at each of n − 1 steps.Source: §1.3 · p. 8

1.4 A barrier for the polynomial constructions

  • For n ≥ 3, the specified formal reduction rules cannot certify an exponent below n^2/4, even with tensor powers, subexponential overhead, and common auxiliary factors.The system extends the symmetric three-leg certificate of Amanov, van den Berg, and Zuiddam [ABZ26] to n legs and includes interpolation, concavity, shifted tripling, and simultaneous separation.Source: §1.4 · pp. 8–9
  • The certificate is monotone under the specified formal reductions, with edge and identity values yielding the n^2/4 threshold.It is defined on formal expressions, not asserted to be a spectral point on all complex tensors.Source: §1.4 · p. 10
  • For tensor powers with subexponential overhead and a common auxiliary factor, the rules imply log2 R_N ≥ Nn^2/4 − log2 h_N, so they cannot certify a lower exponent.The bound follows when the diagonal budget is R_N h_N and log2 h_N = o(N).Source: §1.4 · p. 10
  • For even n, n^2/4 equals the maximum cut size; for odd n, the maximum cut is smaller by 1/4, and the true asymptotic-rank gap remains open.The stated polynomial constructions retain the n^2/4 threshold for odd n.Source: §1.4 · p. 10

2 Preliminaries

The preliminaries define tensor operations and asymptotic parameters, establishing asymptotic-restriction and spectral tools within Strassen’s framework. They also introduce graph tensors and cut parameters used to derive bounds.

2.1 Tensor coordinates and operations

  • Independent coordinate permutations within fixed legs define tensor equivalence, while local maps define restrictions and the tensor operations distinguish pairing legs from concatenating them.The Kronecker direct sum and product retain tensor order; tensor construction concatenates legs, and the partial direct sum separates two legs while sharing aligned coordinates on the others.Source: §2.1 · pp. 12–15

2.2 Asymptotic rank and the spectrum

  • Rank is the least identity-tensor size restricting to T, subrank the greatest size restricting from it, and their asymptotic limits exist by Fekete’s lemma.Strassen’s spectral duality connects these parameters to numerical inequalities; restriction on the tensor semiring is a Strassen preorder for order k ≥ 2.Source: §2.2 · pp. 16–17
  • A degeneration S ⊴ T implies S ≲ T by Bini’s interpolation, using bN+1 evaluation copies with subexponential overhead.The Nth tensor power yields a polynomial of degree at most bN; Vandermonde interpolation extracts S^⊗N, and log(bN+1)=o(N).Source: §2.2 · pp. 17–18
  • Spectral points characterize asymptotic restriction: S ≲ T exactly when every ϕ in Φ_k satisfies ϕ(S) ≤ ϕ(T), by Strassen’s spectral duality.Spectral points are additive, monotone under restriction, and lie between 1 and rank on nonzero tensors.Source: §2.2 · p. 18

2.3 Graph tensors and cuts

  • Graph tensors assign a shared label to each edge and group incident-edge labels at each vertex, giving vertex-leg dimensions q^d_v.Pairing edge labels gives GT_p(G) ⊗^N ≅ GT_{p^N}(G), as established by the isomorphism GT_p(G) ⊗ GT_q(G) ≅ GT_{pq}(G).Source: §2.3 · pp. 18–19
  • ⌊k^2/4⌋ and k−1 are respectively the maximum- and minimum-cut sizes of K_k; grouping tensor legs across a cut gives matrix rank q^|δ_G(S)|.These cut quantities supply lower-bound parameters; for disconnected graphs, MinCut(G)=0 and e_Q(GT_2(G))=1.Source: §2.3 · p. 20

3 Separating Several Shared Tensor Legs

A finite construction separates all shared tensor legs simultaneously using linearly many direct-sum copies, then yields an entropy inequality for higher-order tensors. Applied to fixed-type blocks, the inequality relates their spectral values to the entropy of their frequency distribution.

3.1 A finite separation construction

  • Fourier projection and local weights force surviving terms to agree on every shared leg, after which coordinate projections yield a full direct sum.The weights make total degree a sum of squared label differences, so degree zero enforces agreement.Source: §3.1 · pp. 20, 22

3 Separating Several Shared Tensor Legs

  • (2k −1)M source copies separate M matched blocks at once, leaving each output block with an M-dimensional edge tensor.The edge index remains within each block rather than serving as an additional direct-sum label.Source: §3.2 · p. 22

3.2 The entropy inequality

  • Tensor powers and fixed-frequency sector words turn simultaneous separation into an entropy inequality for the spectral values of matched blocks.The inequality extends from rational frequency vectors to all probability vectors by continuity.Source: §3.2 · pp. 22–23

4 Polynomial Multiplication and the Complete Graph Bound

This section constructs a symmetric spectral profile from polynomial multiplication and derives growth inequalities that yield a near-tight asymptotic-rank bound for complete-graph tensors. It also gives edge-exponent consequences, including maximum-cut equality for even complete graphs and an odd-order gap of 1/4.

4.1 Polynomial tensors and spectral profiles

  • The n-input polynomial tensor has rank D = 1 + sum_j(a_j − 1), while interpolation gives a linear-in-length rank bound and keeps every input in a separate leg.The profile averages spectral values over permutations of all n legs; its growth controls the spectral value of the complete graph tensor.Source: §4.1 · pp. 24–25
  • For each pair of legs, a spectral edge weight determines the edge tensor’s spectral value at every dimension, enabling evaluation on the complete graph.The symmetric profile is a numerical function formed by averaging over leg permutations, not itself asserted to be a spectral point.Source: §4.1 · pp. 25, 27

4.2 Discrete concavity

  • For b ≥ 2, 2Pϕ(..., b) ≥ exp(H(θ, 1−θ))Pϕ(..., b + 1)^θPϕ(..., b − 1)^(1−θ); symmetry extends this inequality to every input coordinate.The proof retains quotient and kernel sectors while keeping the first n−2 shared inputs separate, then applies the entropy inequality.Source: §4.2 · pp. 27, 29
  • Positivity of neighboring profile values permits θ = A/(A + B), yielding the discrete concavity inequality for Pϕ.Here A and B are the neighboring profile values defined in the proof.Source: §4.2 · pp. 29–30

4.3 Shifted tripling

  • For n ≥ 3, shifted tripling gives Pϕ(a_1, …, a_{n−2}, 3h + S) ≥ 3Pϕ(a_1, …, a_{n−2}, h), where S is the sum of the other input degrees.The construction extends [Ope26a, Lemma 4.2].Source: §4.3 · p. 30

4.4 Diagonal growth

  • Tracking all n−1 coordinate steps gives exponent 2(n−1)/n, which combines with the linear rank bound to constrain average spectral edge weight.The argument uses discrete concavity to bound a long increment by its first step and shifted tripling to lower-bound that increment.Source: §4.4 · p. 31

4.5 The complete graph bound and its consequences

  • For every n ≥ 2 over the complex numbers, floor(n^2/4) ≤ log_2 R~(GT2(K_n)) ≤ n^2/4.The upper and lower bounds coincide for n = 2; the lower bound is the maximum cut of K_n.Source: §4.5 · p. 33
  • For even n, the upper bound equals the maximum-cut lower bound; for odd n, it exceeds that lower bound by 1/4.For K_{2m}, both bounds equal m^2.Source: §4.5 · pp. 33–34
  • For every n ≥ 5, τ(K_n) ≤ n/(2(n−1)) < 2/3, and lim_{n→∞} τ(K_n) = 1/2.This answers the cited existence question affirmatively for every n ≥ 5.Source: §4.5 · p. 34

5 An Operational Barrier for the Polynomial Method

This section extends the polynomial-method barrier to n legs by constructing a comparison function and monotone certificate for explicitly permitted formal reductions. The certificate establishes an operational threshold of n²/4 for the generated relation on expressions, not a barrier for every tensor degeneration or a matching lower bound on true asymptotic rank.

5 An Operational Barrier for the Polynomial Method

  • n^2/4 is the threshold of the extended symmetric certificate for the polynomial constructions, matching their growth on polynomial tensors.Amanov, van den Berg, and Zuiddam [ABZ26, Section 5] proved the three-leg barrier at 9/4 even under repeated combinations.Source: §5 · p. 34

5.1 Formal expressions and polynomial resources

  • Simultaneous separation enforces every shared label and yields a direct sum of the block tensors paired with a retained edge tensor, for independently chosen block count and edge dimension.The retained terms have the same block label on each shared leg, while an additional index is shared only by the two edge legs.Source: §5.1 · p. 36

5.2 Permitted derivations and their soundness

  • Every permitted derivation gives a valid tensor degeneration, but the rules do not permit arbitrary substitutions inside partial sums or identify all expressions with locally isomorphic evaluations.The certificate is monotone only for this explicitly generated relation; it is not asserted to be a spectral point on Tens_n(C).Source: §5 · p. 34, §5.2 · pp. 37–38

5.3 A comparison function for polynomial lengths

  • The symmetric comparison function is coordinatewise nondecreasing and separately concave, with H_d(1, ..., 1, b) = b and H_d(a, 3h + S) ≥ 3H_d(a, h).These properties provide the numerical estimates needed for truncation, neighboring lengths, shifted tripling, and the polynomial-resource budget.Source: §5.3 · p. 40
  • The comparison function H_d is concave and normalized, satisfies H_d(a) ≤ product a_i, and supplies star and shifted-tripling inequalities.These bounds support the certificate’s monotonicity checks.Source: §5.3 · p. 41

5.4 A certificate and the barrier

  • The positive, leg-permutation-invariant certificate V_n extends the symmetric square-multiplication certificate of Amanov, van den Berg, and Zuiddam [ABZ26, Equation (5.3)] to arbitrary order and is monotone under the permitted formal relation.Its construction uses H_{n−1} and the simultaneous separation budget.Source: §5.4 · pp. 41–42
  • For n≥3, the permitted formal rules cannot certify an exponent below n²/4, even with tensor powers, subexponential overhead, or catalysts; this is not a lower bound on true asymptotic rank.For odd n, the threshold exceeds MaxCut(K_n) by 1/4.Source: §5.4 · pp. 43–44

Open Problems

The paper leaves open the asymptotic rank of odd complete-graph tensors and whether the maximum-cut expression gives the rank exponent for broader graph families.

Odd complete graphs

  • For odd n, the exponent may equal floor(n^2/4), equal n^2/4, or lie strictly between them.At n = 3, these endpoint cases correspond to ω = 2 and ω = 9/4, respectively.Source: Open Problems · p. 44
  • For odd complete graphs, the lower endpoint needs a better upper bound, the upper endpoint needs a lower bound beyond flattening, and an intermediate value needs progress on both sides.Within the polynomial system, proving the lower endpoint requires an ingredient beyond its listed rules.Source: Open Problems · p. 44

General graphs

  • For general graphs, it remains open whether log2 eR(GT2(G)) equals MaxCut(G); the equality holds for bipartite graphs and even complete graphs.The analogous asymptotic-subrank question has a graph-theoretic answer through log2 eQ(GT2(G)) = MinCut(G).Source: Open Problems · p. 44

AI Disclosure

The author describes how AI tools contributed to exploring and developing the paper’s mathematical direction, while retaining responsibility for the manuscript.

Research development

  • The author first used GPT-6 Pro to study existing results and explore possible improvements, but those attempts made limited progress.The project began with the author’s earlier interest in graph tensors and questions about their asymptotic rank and subrank.Source: AI Disclosure · p. 45
  • The author proposed applying polynomial multiplication techniques from OpenAI’s matrix multiplication result, after which GPT-6 Pro developed the higher-order construction and upper bound.Source: AI Disclosure · p. 45
  • The author noticed the operational-barrier work of Amanov, van den Berg, and Zuiddam [ABZ26] in an AI-generated draft, then guided GPT-6 Pro to adapt the approach to higher-order graph tensors.Source: AI Disclosure · p. 45

Manuscript preparation

  • The manuscript was prepared with GPT-6 Astra Ultra under detailed author instructions, and the author takes full responsibility for its correctness, completeness, and integrity.Source: AI Disclosure · p. 45

A Flattening Rank, Cut Bounds, and Triangle Covers

Flattening ranks turn graph cuts into lower bounds on asymptotic rank, while triangle covers give upper bounds by comparison with matrix multiplication. These tools yield a maximum-cut lower bound, exact asymptotic rank for bipartite graphs, and a triangle-cover comparison whose numerical value uses ω ≤ 9/4.

Flattening rank

  • A rank decomposition into r simple tensors bounds each flattening rank by r, since a simple tensor flattens to a rank-one matrix.Flattening rank is also monotone under local restrictions and equals q for the identity tensor Ik(q).Source: A Flattening Rank, Cut Bounds, and… · p. 48

Cut bounds

Triangle covers

  • The triangle-cover bound’s numerical cost of 3/4 per edge specifically uses OpenAI’s matrix multiplication bound ω ≤ 9/4.The symbolic covering argument is separate from that numerical substitution.Source: A Flattening Rank, Cut Bounds, and… · p. 50
  • A triangle cover yields an upper-bound comparison for a graph when every edge occurs in at least r of the listed triangles.The cover may repeat triangles and may use unequal edge multiplicities.Source: A Flattening Rank, Cut Bounds, and… · p. 50

B Asymptotic Subrank and the Minimum Cut

This appendix gives a tensor-language proof of the Vrana–Christandl minimum-cut formula for graph tensors’ asymptotic subrank, combining orthogonal representations, edge-labeling degenerations, and an exact spanning-tree restriction.

B Asymptotic Subrank and the Minimum Cut

  • For connected G with at least three vertices, the line graph has an integral general-position orthogonal representation in dimension d = |E(G)| − MinCut(G).The construction uses the Lovász–Saks–Schrijver theorem after showing the line graph is MinCut(G)-vertex-connected [LSS00].Source: B Asymptotic Subrank and the Minimum Cut · p. 51
  • Rational approximation preserves the required orthogonality and general position, then clearing denominators yields integral vectors.The vectors are adjusted continuously near a real representation before rational coordinates are chosen.Source: B Asymptotic Subrank and the Minimum Cut · pp. 51–52
  • A spanning-tree restriction extracts an identity tensor from any connected graph tensor, absorbing interpolation overhead with logarithmically many copies.The restriction keeps labelings that are zero off the tree and constant across its edges.Source: B Asymptotic Subrank and the Minimum Cut · p. 52
  • For every finite simple graph G with at least two vertices, log2 eQ(GT2(G)) = MinCut(G), proving the Vrana–Christandl formula [VC17, Theorem 1].The proof establishes a cut-based upper bound and a matching lower bound.Source: B Asymptotic Subrank and the Minimum Cut · pp. 51, 52, 54
  • A pigeonhole fiber of edge labelings degenerates to an identity tensor because distinct surviving labelings remain distinguishable at every vertex.The fiber is selected by equal weighted vector sums; orthogonality supplies local weights that retain exactly this fiber.Source: B Asymptotic Subrank and the Minimum Cut · pp. 53–54
  • Interpolation converts the degeneration into an ordinary asymptotic-subrank lower bound, and letting the tensor-power parameter grow makes it match the minimum-cut upper bound.For fixed q, the overhead uses tN = O(log N) copies; the upper bound follows by minimizing over nonempty proper vertex subsets.Source: B Asymptotic Subrank and the Minimum Cut · pp. 52, 54

Related papers

Loading 2610.34273v1…