PaperlayerView exact revision on arXiv

Source-linked AI summary

Multiplying matrices via polynomials: exposition and barriers

Alimzhan Amanov, Maxim van den Berg, Jeroen Zuiddam

arXiv:2610.30054v1cs.CCmath.RAmath.RT

TL;DR

The paper presents a proof strategy for improving matrix-multiplication exponent bounds and extends the approach to every field. It combines polynomial-multiplication tensor degenerations using Strassen’s asymptotic spectrum, obtaining rectangular bounds and an operational barrier on what the current ingredients can achieve.

  • Problem

    The paper addresses how to improve square and rectangular matrix-multiplication exponent bounds and whether the proof ingredients can yield stronger bounds.

    Source: §1 · p. 2

  • Method

    The proof combines tensor degenerations and their combination rules, using Strassen’s asymptotic spectrum to analyze the search over combinations.

    Source: §1.1 · p. 3, §1.1.2 · p. 6

  • Results

    ωF(1, k, 1) = 2 for 0 ≤ k ≤ 1/2, and the current degeneration ingredients cannot improve the analyzed upper bounds through their specified combinations.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The bounds hold over every field, and improving them further requires going around the operational barrier imposed by the current ingredients.

    Source: §1 · p. 2

    The operational barrier concerns the current degeneration ingredients and their specified combinations, not all possible approaches to improving the bounds.

    Source: §1 · p. 2, §1.4 · p. 9

Abstract

from arXiv · show

We give an exposition of OpenAI's recent proof that the exponent $\omega_\mathbb{C}$ of matrix multiplication over the complex numbers satisfies $\omega_\mathbb{C}\leq9/4$. Our version of the proof gives $\omega_\mathbb{F}\leq9/4$ over every field $\mathbb{F}$. We also treat the rectangular matrix multiplication exponent $\omega_\mathbb{F}(a,b,c)$. Here we have $\omega_\mathbb{F}(1,k,1)=2$ for $0\leq k\leq1/2$ and $\omega_\mathbb{F}(1,k,1)\leq1+k+1/(4k)$ for $k\geq1/2$, and, for real numbers $a\geq b\geq c\geq0$, $\omega_\mathbb{F}(a,b,c)=a+b$ if $c(a+b)\leq ab$ and $\omega_\mathbb{F}(a,b,c)\leq(a+b+c)/2+(ab/c+ac/b+bc/a)/4$ otherwise. Our exposition is in the language of degeneration inequalities among polynomial multiplication tensors and Strassen's asymptotic spectrum duality. We moreover prove an operational barrier (which can be thought of as coming from an operational asymptotic spectrum) showing that the current analysis of all these upper bounds on $\omega_\mathbb{F}$ and $\omega_\mathbb{F}(a,b,c)$ is optimal and that in fact the current degeneration ingredients cannot improve the bounds.

1 Introduction

The exposition recasts a proof of matrix-multiplication bounds in terms of tensor degenerations and Strassen’s asymptotic spectrum, with a version that works over every field. It also establishes that the current degeneration ingredients cannot yield better bounds through the analyzed combinations.

1 Introduction

  • ωF(1, k, 1) = 2 for 0 ≤ k ≤ 1/2 over every field, improving the previously known rectangular range.The paper states this gives αF ≥ 1/2 and allows n² × n by n × n² matrix multiplication in O(n^(4+ε)) operations.Source: §1 · p. 2
  • The bound of Theorem 1.2 is optimal for its proof ingredients: neither the ingredients nor their specified combinations yield a better upper bound.Improving the bounds requires going around this operational barrier.Source: §1 · p. 2

1.1 Degeneration ingredients and combination rules

  • Degeneration suffices for upper bounds on ωF: a degeneration from ⟨n, n, n⟩ to ⟨r⟩ implies ωF ≤ log r / log n.Degeneration permits polynomial entries in a formal variable ε; asymptotic restriction also provides a reduction framework for combining tensors.Source: §1.1 · pp. 3–4

1.1.1 Degeneration ingredients

  • Polynomial multiplication tensors and their permutations generate matrix multiplication tensors and their direct sums, while interpolation gives polynomial multiplication a border-rank upper bound.The exposition therefore studies matrix multiplication through these polynomial multiplication tensors.Source: §1.1.1 · p. 4, §1.1 · p. 4
  • Partial direct sums can be separated into direct sums using a polynomial-tensor factor, which can be partially consumed as a catalyst.The separation rule changes a factor Pm,t to P1,t; the cited ingredient also permits an arbitrary shared partial direct sum on both sides.Source: §1.1.1 · p. 5
  • Concavity degeneration trades two copies of Pa,b for Pa,b+1 and Pa,b−1, while tripling degeneration combines three partial copies into Pa,3b+a−1.The concavity construction is related to SL2 representation theory; the tripling construction uses one larger polynomial multiplication to compute three smaller ones.Source: §1.1.1 · p. 5

1.1.2 Combination rules

  • The combination search spans infinitely many parameterized ingredients and may require large n, so Strassen’s spectral duality turns it into an optimization problem.The proof combines degeneration ingredients using direct sums, tensor products, and permutations of tensor legs.Source: §1.1.2 · pp. 5–6

1.2 Understanding how the ingredients can be combined

The section shows how polynomial-multiplication degenerations can be combined into partial direct sums of matrix-multiplication tensors, then symmetrized and powered to obtain square matrix multiplication. A concrete example yields an upper bound below 2.695, and the construction extends toward 9/4.

1.2.1 From Pa,b to partial direct sum of ⟨1, 1, n⟩and permutations

  • Ingredient (D3) branches P_a,b into P_a,b+1 and P_a,b−1, while (D4) converts suitable summands into matrix-multiplication tensors, producing partial direct sums.For example, P_a,a+2 becomes two copies of ⟨a, 1, 1⟩ and one of ⟨1, a, 1⟩.Source: §1.2.1 · p. 6

1.2.2 From partial direct sums to ⟨n, n, n⟩via symmetrisation and powering

  • Symmetrization and tensor powers turn the resulting rectangular partial sums into an asymptotic restriction to square matrix multiplication, with a common square tensor factor acting as a catalyst.The construction keeps summands with a fixed number of each type, then uses symmetrization to make the resulting tensor square.Source: §1.2.2 · p. 7

1.2.3 Concrete example of applying ingredients (D3) and (D4)

  • 2.695 is an upper bound on ω_F from starting with ⟨5⟩⊵P_2,4 and applying (D4); the P_2,2 example gives a bound below 2.74.Starting from P_a,a with a tending to infinity extends the example to explicit ingredient combinations whose bounds tend to 9/4.Source: §1.2.3 · p. 8

1.3 High-level proof description and role of asymptotic spectrum duality

The proof uses Strassen’s asymptotic spectrum duality to bound the matrix multiplication exponent, while an operational barrier shows that the listed degeneration ingredients cannot improve those bounds. The barrier has a dual certificate, though it is not known to be a spectral point.

1.3 High-level proof description and role of asymptotic spectrum duality

  • Strassen’s duality turns the search for combinations of degeneration ingredients into optimization over spectral points, and the ingredient inequalities imply ω_F ≤9/4.The proof bounds the sum of three logarithms of spectral-point values using superadditivity, concavity, and a tripling inequality.Source: §1.3 · p. 8

1.4.1 No barrier from irreversibility

  • The standard irreversibility barrier does not explain the 9/4 bound: for the tensors S_a, its bound tends to the trivial value 2 as a grows.The paper also reports no irreversibility barrier for rectangular matrix multiplication.Source: §1.4.1 · p. 9

1.4.2 Tight barrier for (D0)–(D4) + (C1)–(C4)

  • No derivation from ingredients (D0)–(D4) and rules (C1)–(C4), including limits of such bounds, improves the stated square or rectangular exponent bounds.The result also covers asymptotic consequences of those rules.Source: §1.4.2 · p. 9
  • A function F⋆ in the outer approximation ∆⪯ reaches 2^(9/4) on ⟨2, 2, 2⟩, serving as a dual certificate for the barrier.The same argument uses other functions in ∆⪯ to certify the rectangular bounds.Source: §1.4.2 · pp. 9–10
  • It is unknown whether F⋆ agrees with a spectral point on the relevant tensors; if it did, the first inequality in (1.7) would be equality and ω_F would equal 9/4.Source: §1.4.2 · p. 10

1.5 Organisation of the paper

  • The paper’s sections define tensors and degenerations, construct ingredients, prove the exponent bounds, and establish the barrier to improving them with those ingredients.Source: §1.5 · p. 10

2 Restriction and degeneration

The section develops tensor operations and restriction and degeneration relations used to compare computational tensors. It gives a block-triangular criterion for degeneration and a weight-based way to select tensor terms.

2.1 Tensors

  • Tensors are elements of three-way tensor products; direct sums and tensor products combine them, while a partial direct sum shares the first leg.The section also defines the unit tensor and matrix multiplication tensors as basic examples.Source: §2.1 · p. 10

2.2 Restriction and tensor rank

  • Restriction applies linear maps to the three legs, and tensor rank is the least number of rank-one tensors in a sum representing the tensor.Equivalently, rank is the least r such that the tensor is a restriction of the unit tensor ⟨r⟩.Source: §2.2 · p. 11

2.3 Degeneration and border rank

  • A tensor is a degeneration of another when polynomial changes of basis produce it as the leading ε-term; border rank is the least unit-tensor size that degenerates to it.Degeneration is transitive and is preserved by direct sums, tensor products, and permutations of the legs.Source: §2.3 · p. 12

2.4 Degeneration from block triangular tensors and weights

  • A tensor with a zero lower-left block degenerates on its second and third legs to the sum of its diagonal blocks.The two-leg degeneration scales the first row and second column by ε, leaving the diagonal blocks at the leading order.Source: §2.4 · p. 13, Figure 3 · p. 13
  • Integer-valued weights with nonnegative sums on the source terms select the zero-weight terms as a degeneration.The construction uses diagonal matrices with powers of ε; the first leg is unchanged when its weight is zero.Source: §2.4 · p. 14

3 Degenerations among polynomial multiplication tensors

The section constructs, over every field, degeneration ingredients involving polynomial multiplication tensors. These include rank bounds, a separation step for partial direct sums, a concavity relation, and a tripling construction.

3 Degenerations among polynomial multiplication tensors

  • Over every field, the section constructs degenerations among unit and polynomial multiplication tensors, partial direct sums, and polynomial multiplication tensors themselves.These are the ingredients used in the proofs of the paper’s main theorems.Source: §3 · p. 14

3.1 Polynomial multiplication tensors

  • Pa,b has border rank at most a + b −1, and ⟨n⟩ degenerates to Pn,n.Polynomial multiplication tensors encode multiplying polynomials of degrees at most a−1 and b−1.Source: §3.1 · p. 15

3.2 Separating partial direct sums into direct sums

  • A polynomial multiplication tensor factor separates a partial direct sum into a direct sum, while changing from Pm,t to P1,t.The proposition states (T1 ⊕···⊕Tm) ⊗P1,t ⊴ (T1 ⊕1···⊕1Tm) ⊗Pm,t; the paper describes Pm,t as a resource partially consumed in this degeneration.Source: §3.2 · p. 16

3.3 Concavity degeneration for Pa,b

  • The concavity degeneration converts two copies of Pa,b into Pa,b+1 and Pa,b−1, and extends to majorization relations among tuples of polynomial degrees.The all-fields proof uses subspaces and quotients; the alternative Clebsch–Gordan proof is over C, where that decomposition is available.Source: §3.3 · pp. 16, 18

3.4 Tripling degeneration for Pa,b

  • Tripling splits a larger polynomial multiplication tensor into diagonal Pa,b blocks and a reversed middle block, then removes the off-diagonal blocks by degeneration.The stated tripling degeneration is impossible when n<N, as the second and third flattening ranks rule it out.Source: §3.4 · pp. 19–20

4 Upper bounds via spectral points

This section uses Strassen’s asymptotic spectrum and tensor degenerations to derive exponent bounds for matrix multiplication, including ω_F ≤ 9/4 and bounds for rectangular multiplication. It develops spectral-point inequalities—including quadratic constraints, superadditivity, and concavity—that yield an outer approximation of the matrix multiplication spectrum and piecewise rectangular bounds, including for shapes (1, k, 1).

4.1 Spectral points, asymptotic spectrum duality, and basic properties

  • Strassen’s duality makes exponent bounds follow from bounding spectral-point values, and expresses 2ω_F(a,b,c) as the maximum of ϕ(⟨2,1,1⟩)^a ϕ(⟨1,2,1⟩)^b ϕ(⟨1,1,2⟩)^c over ϕ ∈ ∆F [Str88].For the upper bounds, the argument uses the abstract spectral-point properties rather than requiring a complete explicit description of the spectrum.Source: §4.1 · pp. 21–22

4.2 Superadditivity on partial direct sums

  • For tensors T1 through Tm, the partial-direct-sum inequality states that ϕ(T1 ⊕1 ··· ⊕1 Tm)^(1/p) is at least ϕ(T1)^(1/p) + ··· + ϕ(Tm)^(1/p).Partial direct sums and direct sums need not be equivalent under asymptotic restriction.Source: §4.2 · pp. 22–23

4.3 Concavity and tripling for each leg

  • When p > 0, b ↦ ϕ(Pa,b)^(1/p) is concave and satisfies a tripling inequality, while min(a, b) ≤ ϕ(Pa,b) ≤ a + b − 1 and ϕ(Pa,b) is nondecreasing.The tripling inequality is 2ϕ(Pa,b)^(1/p) + ϕ((23) · Pa,b)^(1/p) ≤ ϕ(Pa,3b+a−1)^(1/p).Source: §4.3 · p. 25

4.4 Square matrix multiplication

  • For every ϕ ∈ ∆F, using ϕ(π · P_n,n) ≤ 2n − 1 for every π ∈ S3 and integer n ≥ 1, the proof obtains ϕ(⟨2,2,2⟩) ≤ 2^(9/4), hence ω_F ≤ 9/4 by Theorem 4.2.Source: §4.4 · p. 27

4.5 Quadratic constraints on asymptotic spectrum of matrix multiplication

  • The rectangular extension generalizes the concave-function growth argument to account for the ratios of the three leg weights in ω_F(a,b,c).Lemma 4.13 generalizes Lemma 4.11, which is the case u = v = b and r = s = 1.Source: §4.5 · p. 27
  • For p_i=log ϕ of the three tensors ⟨1,1,2⟩, ⟨2,1,1⟩, and ⟨1,2,1⟩, 4(p1x2x3+p2x1x3+p3x1x2)≤(x1+x2+x3)^2 for all nonnegative x_i.This holds for every ϕ in the asymptotic spectrum Δ_F.Source: §4.5 · pp. 28–29
  • The log-spectrum satisfies P⊆log Δ_m F⊆Q∩{w:w1+w2+w3≥2}, the best inner and outer approximations stated here.For x1=x2=x3=1, the bound is attained at 3/4(1,1,1).Source: §4.5 · p. 29, Figure 4 · p. 30

4.6 Rectangular matrix multiplication

  • ω_F(a,b,c)=a+b when c(a+b)≤ab, and otherwise ω_F(a,b,c)≤(ab+bc+ca)^2/(4abc), with equality in the first case.The theorem holds over every field F.Source: §4.6 · p. 30
  • ω_F(1,k,1)=2 for 0≤k≤1/2, and ω_F(1,k,1)≤1+k+1/(4k) for k≥1/2.For example, the theorem gives ω_F(6,3,2)=9 and ω_F(1,1,1)≤9/4.Source: §4.6 · p. 31
  • The bounds α_F≥1/2, ω_F(1,0.709,1)<2.0617, and ω_F(1,2,1)≤25/8 improve prior OpenAI and laser-method bounds [WXXZ24].OpenAI reported α_C>0.465 and ω_C(1,0.709,1)<2.092; laser-method bounds were α_F>0.321334 [WXXZ24] and ω_F(1,2,1)≤3.250035.Source: §4.6 · p. 31

5 Operational barrier

The section establishes that the paper’s degeneration ingredients and combination rules cannot improve the bounds of Theorem 1.2. It formalizes this operational barrier with monotone functions on formal tensor expressions, which also test whether adding ingredients preserves the barrier.

5 Operational barrier

  • No combination of degeneration ingredients (D0)–(D4) using rules (C1)–(C4) improves the bounds of Theorem 1.2.The result is an operational barrier on what these ingredients and rules can establish.Source: §5 · p. 31
  • The construction uses a formal semiring of polynomial multiplication tensors and a preorder encoding only the allowed ingredients and combination rules.This preorder represents degeneration constructions obtainable from that restricted toolkit.Source: §5 · p. 31
  • The paper does not obtain a degeneration-monotone spectral point that directly obstructs all degenerations yielding ωF < 9/4.Instead, it restricts the analysis to the formal-expression semiring and its operational preorder.Source: §5 · pp. 31–32
  • Monotone functions on this formal system obstruct every allowed degeneration that would yield ωF < 9/4, and analogously obstruct improvements to the rectangular bounds.These functions establish the operational barrier without claiming a barrier for all possible degenerations.Source: §5 · p. 32
  • Adding degeneration ingredients preserves the barrier whenever the constructed functions remain monotone under the enlarged preorder.This supplies a test for whether new ingredients could help improve the bounds.Source: §5 · p. 32

5.1 Symmetric notation Px,y,z for permuted polynomial multiplication

The section replaces the notation for permuted polynomial multiplication tensors with a symmetric three-parameter notation. Admissible triples index exactly these tensors up to isomorphism.

5.1 Symmetric notation Px,y,z for permuted polynomial multiplication

  • The tensor terms are indexed by triples satisfying i + j + k = a + b + 1 after reindexing the third leg.Here the largest leg dimension is M = a + b − 1.Source: §5.1 · p. 32
  • A triple (x, y, z) is admissible when x + y + z = 2 max(x, y, z) + 1, so its largest entry is the sum of the other two minus 1.The definition takes x, y, and z to be at least 1.Source: §5.1 · p. 32
  • Up to isomorphism, tensors Px,y,z for admissible integer triples are exactly the permutations of Pa,b for positive integers a and b.Permuting tensor legs permutes the triple entries.Source: §5.1 · p. 32

5.2 Set F of formal combinations of tensors

The section defines formal expressions for polynomial multiplication tensors and their combinations. These expressions support a precise account of which degeneration ingredients, isomorphisms, and combination rules are allowed.

5.2 Set F of formal combinations of tensors

  • The formal system uses direct sums, tensor products, and partial direct sums in each of the three directions.A partial direct sum is allowed only when the corresponding legs have equal dimensions.Source: §5.2 · pp. 32–33
  • The set F consists of formal expressions generated by Px,y,z for admissible positive-integer triples under the permitted operations.It also includes shorthand expressions for unit tensors and matrix multiplication tensors.Source: §5.2 · p. 33
  • Each expression represents a tensor by recursively evaluating its generators and operations, but distinct expressions may represent the same tensor.Keeping expressions distinct allows the formal preorder to track only the permitted degeneration ingredients and rules.Source: §5.2 · pp. 32–33

5.3 Formal preorder relation ⪯on F and operational barrier statement

The paper formalizes a preorder on expressions that captures the degeneration ingredients used in its proofs. The operational barrier shows that relations in this preorder yield no stronger matrix-multiplication exponent bounds than the stated bounds.

Formal preorder relation ⪯ on F

  • The preorder is the smallest one compatible with ⊕ and ⊗ and satisfying the listed combination rules, restrictions, and isomorphisms.Its ingredients include the D0–D4 rules, renumbering of tensor legs, and properties R and I.Source: §5.3 · pp. 33–34

Operational barrier

  • If ⟨n1, n2, n3⟩ ⪯ ⟨r⟩, then the relation is a tensor degeneration and gives an upper bound on ω_F.The preorder’s defining properties also hold for tensor degeneration.Source: §5.3 · p. 34
  • For a = log n1, b = log n2, c = log n3 in nonincreasing order, the barrier gives a + b when c(a + b) ≤ ab, and (ab + bc + ca)^2/(4abc) when c(a + b) > ab.In particular, n1 = n2 = n3 = n implies n^(9/4) ≤ r.Source: §5.3 · p. 34
  • No relation in this preorder, nor any limit of bounds obtained from such relations, gives an upper bound on ω_F below 9/4.The same conclusion applies to the resulting rectangular exponent bounds relative to the paper’s stated bound.Source: §5.3 · p. 34

5.4 Definition of functions F ⋆θ on F

The authors construct positive functions F⋆θ on formal expressions, with θ indexing the functions. Their values are chosen to make the degeneration inequalities tight while satisfying a constraint on the exponents at matrix-multiplication tensors.

Definition of F⋆θ

  • For each θ in Θ, the construction gives a positive function F⋆θ on F that is additive, multiplicative, normalized by F⋆θ(⟨r⟩) = r, and intended to be monotone under the preorder.The functions are defined on formal combinations in F, not directly on tensors.Source: §5.4 · pp. 34–35
  • The construction aims to make the inequalities supplied by degeneration rules D0–D4 essentially tight.At matrix-multiplication tensors, the function has values of the form n^p3, with the exponents constrained by Proposition 4.14.Source: §5.4 · p. 34
  • For an admissible triple, the definition uses A_s = (d_s − θ_s)/(1 − θ_s) and chooses indices ordered by the d_s and A_s values.Admissibility means the largest entry is the sum of the other two minus 1.Source: §5.4 · p. 35

5.5 Choice of θ for the ω(a, b, c) barrier

The authors choose θ to make the operational barrier sharp for the square and rectangular cases. This yields the piecewise bound in the logarithmic dimensions and the 9/4 square-case barrier.

Choice of θ

  • For the second case, the parameter choice in Lemma 5.6 makes ap2 + bp3 + cp1 equal (ab + bc + ca)^2/(4abc).The resulting inequality bounds this expression by log r.Source: §5.5 · pp. 35–36
  • When c(a + b) ≤ ab, the barrier gives a + b; when c(a + b) > ab, it gives (ab + bc + ca)^2/(4abc), for a ≥ b ≥ c.Here a, b, and c are the ordered logarithms of n1, n2, and n3.Source: §5.5 · p. 36
  • If c(a + b) ≤ ab, taking θ2 = θ3 = (1 − θ1)/2 and letting θ1 approach 0 yields a + b ≤ log r.The derivation uses p2 = p3 = 1/(1 + θ1) and cp1 ≥ 0.Source: §5.5 · p. 36
  • For n1 = n2 = n3 = n, choosing θ1 = θ2 = θ3 = 1/3 gives n^(9/4) ≤ r.The choice makes p1 = p2 = p3 = 3/4 in the inequality p2 log n1 + p3 log n2 + p1 log n3 ≤ log r.Source: §5.5 · p. 36

5.6 Basic properties of F ⋆

The paper establishes basic shape and monotonicity properties of F⋆θ, including bounds on its values at tensors with an admissible third dimension. These properties support proving that the functions are monotone under the preorder.

Basic properties

  • The stated properties are used to establish monotonicity under the preorder, with part (iv) used for D2 and R.The paper identifies parts (i)–(iii) with properties of spectral points.Source: §5.6 · p. 36
  • For z = x + y − 1, F⋆θ(x, y, z) is at least min(x, y) and is nondecreasing in x and y.The proof uses weighted geometric means and affine combinations of the transformed arguments.Source: §5.6 · pp. 36–37
  • For z = x + y − 1, the paper also states bounds on F⋆θ involving x, y, and the exponent p = p1.The supplied statements include x^(1−p)y^p ≤ F⋆θ(x, y, z); another stated property concerns F⋆θ(x, 2y + z, y + 2z).Source: §5.6 · pp. 36–37
  • The proof of the preorder properties relies on identities among the p_i and θ_i, including p_i(1 − θ_j) + p_j(1 − θ_i) = 1.The authors show the relevant function is continuously differentiable by matching the derivatives of its two cases at A = B.Source: §5.6 · p. 37

5.7 Proof of monotonicity of F ⋆ θ and the operational barrier

The section verifies that the constructed function F⋆θ is monotone under the generated preorder, so the operational barrier applies. It also shows the barrier survives specified extensions of the degeneration relations.

5.7 Proof of monotonicity of F⋆θ and the operational barrier

  • The preorder generated by direct-sum and tensor-product compatibility, degeneration rules (D1)–(D4), (R), and (I) is contained in the relation certified by monotonicity of F⋆θ.The proof checks the defining properties, including invariance under leg renumbering.Source: §5.7 · p. 39
  • For (R), the value at T1 is at most those at T1 ⊕ T2 and T1 ⊕1 T2; the latter is at most the former because (x^(1/p) + y^(1/p))^p ≤ x + y for x,y > 0 and p ∈ [0,1].Source: §5.7 · p. 39
  • The proof establishes that F⋆θ is monotone for every θ ∈ Θ, allowing the previously established barrier proposition to apply.The same argument verifies monotonicity under the specified extension of the preorder.Source: §5.7 · p. 39
  • Adding Strassen’s degenerations ⟨⌈3n²/4⌉⟩ ⊴ ⟨n,n,n⟩ leaves the barrier valid because F⋆θ remains monotone.The barrier also applies to the polynomial multiplication degenerations cited in Remarks 3.10 and 3.12, and to the asymptotic closure of the preorder.Source: §5.7 · p. 39

5.8 Operational asymptotic spectrum ∆⪯

The section formulates an operational barrier through the asymptotic spectrum of the semiring of preorder-equivalence classes. Its maximum over that spectrum matches the stated piecewise bound for real shapes a ≥ b ≥ c ≥ 0.

5.8 Operational asymptotic spectrum Δ⪯

  • Δ⪯ consists of positive functions normalized at ⟨1⟩, additive on direct sums, multiplicative on tensor products, and monotone under ⪯.It is the asymptotic spectrum of preorder-equivalence classes, where equivalence means comparison in both directions.Source: §5.8 · p. 40
  • For a ≥ b ≥ c ≥ 0, the maximum over Δ⪯ equals 2a + b when c(a + b) ≤ ab, and 2(ab + bc + ca)²/(4abc) otherwise.The second expression is the bound (a + b + c)/2 + (ab/c + ac/b + bc/a)/4.Source: §5.8 · p. 40
  • Equality in the maximum is obtained using θ with the parameters of Lemma 5.6 in the second case and the flattening rank R(1) in the first.Both witnesses belong to Δ⪯.Source: §5.8 · p. 40
  • The upper-bound proof uses properties that every F ∈ Δ⪯ satisfies, including F(P1,m,m) = m^p for p = log F(P1,2,2) ∈ [0,1] and F(Px,y,z) ≥ 1.The argument also uses the properties in Lemma 4.10, derived from (D1)–(D4), (R), and (I).Source: §5.8 · p. 40
  • The theorem identifies the spectral region as Q intersected with the constraints w1 + w2 ≥ 1, w1 + w3 ≥ 1, and w2 + w3 ≥ 1.The section states that this region is convex and contains the indicated part of Q with w1 + w2 + w3 ≥ 2.Source: §5.8 · p. 40
  • The authors state that their operational barrier covers any combination of the degeneration ingredients and all rectangular shapes, extending prior square-matrix analyses.The section also notes concurrent proofs of related bounds over fields and associative rings.Source: §5.8 · p. 41
Loading 2610.30054v1…