PaperlayerView exact revision on arXiv

Source-linked AI summary

Disjoint and nearly disjoint sums of matrix multiplication tensors and their centroids

Martin Kassabov, J. M. Landsberg, Victor Souza, Philip Speegle

arXiv:2608.27434v1math.AGcs.CCmath.ACmath.RA

TL;DR

The paper studies whether tensors associated with centroid constructions have minimal border rank and seeks new tensors for Strassen’s laser method. It develops border-apolarity techniques using centroids and extended centroids, proving minimal-border-rank results and constructing counterexamples to a prior conjecture.

  • Problem

    Since 1989, upper bounds on the exponent of matrix multiplication have used the big Coppersmith-Winograd tensor, which cannot yield a bound better than ω ⩽2.3; the paper also asks whether the tensors u1,...,ud are always of minimal border rank.

  • Method

    The paper uses border apolarity together with the geometry of centroids and extended centroids to construct border-rank decompositions.

  • Results

    The paper shows that big centroid tensors have minimal border rank and provides a doubly infinite sequence of counterexamples to Conjecture 2.5 in.

  • Takeaways & Limitations

    Border apolarity can provide upper bounds on tensor border rank, and the resulting constructions supply tensors relevant to improving Strassen’s laser method.

  • Takeaways & Limitations

    The paper uses the off-the-shelf laser method and does not attempt to analyze it.

Abstract

from arXiv · show

This paper addresses centroids, which are fundamental invariants of tensors. Our main results are as follows: (i) The construction of explicit tensors with very large centroids, whereas previously it had been conjectured that none such exist. (ii) An upper bound on the dimension of the centroid that is essentially attained by our examples. (iii) The development of a geometric technique to write down border rank decomposition of tensors using centroids and "extended centroids". (iv) The technique is applied to tensors of this paper to prove they are of minimal border rank. The technique is versatile and enables us to geometrically derive and improve upon previous ad hoc decompositions. (v) The construction of symmetric tensors with large centroids and proof that they are wild in the sense of Buczyńska-Buczyński. Our results also pave the way for new upper bounds on the exponent of matrix multiplication. The geometric technique also constructs new "better" tensors for Strassen's laser method from old, and we apply this to the tensors of Strassen and Schönhage to get better tensors in the sense that they give better upper bounds on the exponent than the original tensors.

1. Introduction

The paper constructs tensors with unusually large centroids, bounds their possible dimension, and develops geometric tools connecting centroids to border rank and matrix-multiplication complexity.

  • Centroids: The examples provide counterexamples to the expectation that symmetric tensors cannot have centroids larger than their local dimension.An earlier (9, 9, 9)-tensor with an 11-dimensional centroid had already challenged that expectation.
  • Centroids: Centroid dimensions reach n^3 + 1 when m = n^2 + n, and n^d + 1 for local dimension m = n^(d−1) + n.These are called balanced big centroid tensors.
  • Centroids: For balanced concise valence-d tensors with local dimension m, the centroid dimension is at most m^(d/(d−1)), essentially matching the examples.The bound uses a variant of the Loomis–Whitney inequality and nilpotent-algebra module structure.
  • Geometric techniques: The paper develops geometric tools based on centroids, extended centroids, and border apolarity to construct border-rank decompositions.The tools are applied to prove that the balanced big centroid tensors have minimal border rank.
  • Complexity theory: Unrestriction transforms existing laser-method tensors into tensors that are at least as good and sometimes better for bounding the matrix-multiplication exponent.Applying this to Strassen’s and Schönhage’s tensors yields improved bounds, including ω < 2.46016, ω < 2.46710, and ω < 2.522.
  • Symmetric tensors: The paper also constructs symmetric large-centroid tensors that furnish new wild polynomials in the sense of Buczyńska–Buczyński.These examples are connected to minimal Waring border rank in the valence-three case.

2. Main results and a brief history

The paper constructs tensors with exceptionally large centroids, proves near-optimal centroid-dimension bounds and minimal border rank, and develops geometric decomposition techniques with applications to matrix multiplication.

  • Construction: In the three-valence case, the tensors are sums of three nearly disjoint matrix multiplication tensors, with each pair sharing one set of variables.This structure makes them potentially useful for Strassen’s laser method.
  • Large centroids: The centroid dimension of a concise valence d tensor is at most the (d − 1)-st root of the product of its local dimensions, and the examples asymptotically attain this bound.For balanced local dimension m, the bound specializes to m^(d/(d−1)).
  • Border rank: Over fields F ≠ F2, equal-dimensional big centroid tensors have minimal border rank nd−1 + n.Minimal border rank means border rank equals the local dimension for concise tensors.
  • Geometric techniques: The paper develops centroid and extended-centroid geometry to systematically construct border-rank decompositions, extending techniques previously presented explicitly without explanation.The approach is based on border apolarity and applies beyond minimal-border-rank tensors, although the paper focuses mainly on that case.
  • Symmetric tensors: Symmetric big centroid tensors form counterexamples to the centroid-dimension conjecture, are minimal-border-rank tensors in valence three under stated field conditions, and are wild.Their smoothable rank is strictly larger than their border rank.

3. Preliminary results and observations

This section establishes tensor-complexity preliminaries, including flattenings, rank notions, direct and Kronecker products, and nilpotent-algebra filtrations. These tools support later analysis of concise tensors and centroids.

  • Tensor preliminaries: Flattenings view a tensor as a linear map between dual tensor factors and provide the language for conciseness.A tensor is concise when every one-factor flattening spans the corresponding factor.
  • Tensor operations: Direct sums and Kronecker products satisfy subadditive and submultiplicative rank bounds, respectively, with corresponding border-rank inequalities.These operations also define iterated direct sums and Kronecker powers.
  • Tensor complexity: Rank, border rank, and asymptotic rank measure the complexity of evaluating a multilinear map.Rank is the smallest number of rank-one tensors in a decomposition; border rank is defined through closure or limits.
  • Matrix multiplication: The matrix-multiplication exponent is defined through the asymptotic rank of matrix-multiplication tensors, whose best known upper bound is ω ⩽2.371177.Strassen’s laser method has been used for all upper bounds since 1989, motivating new tensors for that method.
  • Nilpotent filtrations: Nilpotent algebras induce compatible increasing filtrations on acted-upon vector spaces, with algebra elements lowering filtration level.Tensor-product constructions produce nilpotent algebras of class 1 + P_i∈I(k_i−1), and the associated tensor-product algebra decomposes as span{Id} ⊕ fA_I.

4. Basic properties of centroids

This section develops structural properties of centroids, including their algebra structure, tensor-space realization, decomposition criteria, dimension bounds, and behavior under tensor products. It also introduces filtrations that constrain tensors carrying nilpotent centroid subalgebras.

  • Centroid structure: For concise tensors, the centroid is a commutative unital algebra whose projections into each End(V_i) are injective algebra homomorphisms.The centroid action on T is the common contraction obtained from any factor projection.
  • Centroid space: The centroid space contains a Zariski-open family of tensors isomorphic to T and determines concise tensors up to the corresponding Grassmannian orbit.For concise tensors, centroid-space and centroid dimensions coincide.
  • Idempotents and decompositions: A non-trivial centroid idempotent is equivalent to decomposability of a concise tensor across compatible direct-sum decompositions of all factors.Thus semisimple centroid structure detects direct-sum structure.
  • Minimal rank: A concise tensor has minimal rank exactly when its centroid is isomorphic to F⊕dim V as a commutative algebra.This gives an algebraic characterization of minimal rank in the equal-factor setting.
  • Dimension bounds: For primitively 1_{s,s′}-generic tensors, centroid dimension is bounded by the dimension of the largest commutative subalgebra in the associated matrix space.The more general bound scales with border rank and the remaining local dimension.
  • Large centroids: The tensor T_bigcen realizes centroid dimension vw + 1, which is the largest possible value for a 1A-generic tensor in A⊗B⊗B under the stated dimensions.The optimality follows from the maximal dimension of a commuting space of b×b matrices.
  • Nilpotent centroid filtrations: A class-k nilpotent centroid subalgebra forces a concise tensor into a corresponding filtered corner, while its powers map into progressively lower filtration levels.Example 4.13 illustrates the resulting tensor filtration through successive blocks.

5. Big centroid tensors and generalizations

This section constructs big-centroid tensors, determines their large centroids, studies symmetric projections and twists, and extends the constructions through tensor products. The resulting tensors include minimal-border-rank examples and objects relevant to matrix-multiplication complexity.

  • Centroid computation: The centroid of T_bigcen is spanned by the image of φ together with scalar matrices, yielding dimension u_1···u_d + 1.The proof bounds the centroid projection from above and combines it with the image of φ for the matching lower bound.
  • Geometric properties: In the valence-three equal-dimension case, T_bigcen has geometric rank 2p and centroid dimension substantially larger than the largest local dimension.Its associated matrix space has bounded rank 2p.
  • Symmetric tensors: Symmetric projections of big-centroid tensors retain large centroids and, for d = 3, have minimal border rank and minimal Waring border rank.The construction supplies counterexamples to Conjecture 2.5 in.
  • Symmetric tensors: For dim U = n, the symmetric construction is centroid overabundant when n ⩾3.The tensors have size (m,m,m) and a bounded-rank space of dimension 2n.
  • Twists and outer structures: Twisting a concise tensor S with W produces S ≀W, which equals S⊠W exactly when S has (Z/3Z)-symmetry and can have a large centroid under 3u > 2v^2.In that regime, dim Cen(S≀W) ⩾ 3uv − 2v^3 + 1.
  • Generalizations: Kronecker products extend the construction to centroids with higher nilpotent radical classes while preserving asymptotically maximal centroid growth.For the displayed iterated construction, the centroid has dimension n^3m^3+n^3+m^3+1 and radical class three.

6. Border apolarity

Border apolarity is extended from a lower-bound test into a geometric tool for finding border-rank decompositions and unrestrictions. Applied to the paper’s tensors, it proves minimal border rank and identifies promising matrix-multiplication constructions.

  • Extended centroid spaces: An extended centroid space contains an r-dimensional 111-space whose Grassmannian limit is realized by a border-rank decomposition when the tensor has border rank r.The construction uses complementary spaces, their triple intersection, and a limiting r-plane containing the tensor.
  • Unrestrictions: The method produces unrestrictions: larger concise minimal-border-rank tensors that restrict to the original tensor, although such unrestrictions need not be unique.Typically, restriction identifies the larger tensor’s centroid space with the original tensor’s extended centroid space.
  • Extended centroid spaces: Border apolarity can prove upper bounds by analyzing extended centroid spaces and using their structure to guide explicit border-rank decompositions.Previously used for lower bounds, the method is initiated here for upper bounds and recovers earlier decompositions geometrically.
  • Extended centroid spaces: The flag condition requires a complete flag whose projectivizations lie in prescribed secant varieties, forcing rank-one or tangent-vector structure in the relevant spaces.In particular, one space must contain a rank-one element and either another rank-one element or a tangent vector.
  • Applications: The big centroid tensors and their symmetric cousins are shown to have minimal border rank, while the approach also predicts useful sums of matrix multiplication tensors.For Schönhage’s direct sum, the extended centroid has dimension uv + 1 and yields border rank uv + 1.
  • Applications: Adding arbitrary elements of U1 ⊗· · · ⊗Ud to a big centroid tensor can preserve its centroid.This equality is stated for the modified big centroid tensor construction.

7. Border rank decompositions via geometry

The paper develops geometric constructions of border-rank decompositions from generalized centroid spaces, using tangent configurations, rank-one limits, and higher-order derivatives. These constructions recover known examples, establish minimal border rank for new tensors, and yield wild symmetric tensors.

  • Geometric constructions: The method uses rank-one curves over formal power series, with their limits defining order-k border-rank decompositions.For nonzero parameter values, the component tensors have rank one, and lower orders are preferred in complexity applications.
  • Generalized centroid spaces: A generalized centroid space is obtained as a limiting r-plane in a Grassmannian and can guide an explicit border-rank decomposition.For suitable 1*-generic minimal-border-rank tensors, this limiting space coincides with the centroid space.
  • Geometric constructions: First-order constructions cancel zeroth-order terms with configurations whose basis-vector sum has low rank, leaving tangent vectors that span the target tensor.For big centroid tensors, tangent vectors suffice; Schönhage’s case requires second derivatives.
  • Geometric constructions: Lemma 7.1 bounds the border rank by dim(A1 ⊗B1 ⊗C1) + 1 for tensors in the span of the corresponding Segre tangent spaces.Applying it to Strassen’s tensor recovers its minimal border rank.
  • Symmetric tensors: The symmetric tensors Tbigcen_S,3,n have minimal border rank under stated field conditions and are wild over C for every n.The minimal-border-rank theorem assumes n(n −3) ≠ 0 in F, or n = 3 with a primitive third root of unity.

8. Tensors of this paper and the exponent of matrix multiplication

This section applies the standard laser method to the paper’s tensors and their unrestrictions, obtaining bounds on the matrix-multiplication exponent ω.

  • Laser method: Strassen’s laser method uses a low-complexity auxiliary tensor to prove upper bounds on the exponent ω of matrix multiplication.The paper uses a version based on decomposing tensors into blocks that are isomorphic to matrix multiplication tensors.
  • Laser method: Theorem 8.1 combines the tensor’s block support, matrix-multiplication dimensions, and a probability distribution with Shannon-entropy terms to produce an exponent bound.The distribution’s marginals enter the bound, and Remark 8.2 strengthens it when the distribution is recoverable from its marginals.
  • Big centroid tensors: Tbigcen p,q,r is a sum of three nearly disjoint matrix multiplication tensors sharing pairwise one variable set, so Theorem 8.1 applies directly.Each local space is divided into two blocks, and the support tensor has size 3; the relevant tensors have minimal border rank for the listed triples.
  • Unrestrictions and improvements: The tensors Tbigcen 1,1,n slightly improve Strassen’s bounds because the extra M⟨1,1,1⟩ block can receive positive probability.Assigning zero probability to that block recovers Strassen’s bound.
  • Scope: The analysis uses the standard laser method without analyzing Kronecker powers, which is left for future work.Without Kronecker powers, the large Coppersmith–Winograd tensor gives ω < 2.39.
  • Unrestrictions and improvements: The paper also applies the same framework to TSch,u,v and its unrestriction T++ Sch,u,v to obtain bounds listed in Table 2.These tensors are built by combining four matrix multiplication tensors.

9. Bounds on the dimension of the centroid

The paper proves an upper bound on the centroid dimension of concise tensors through an induction on nilpotent centroid algebras, with equality characterized by big centroid tensors.

  • Main bound: The section proves Theorem 2.4, an upper bound on the centroid dimension of a concise tensor in terms of the dimensions of its local spaces.The proof uses an induction argument involving semisimple elements and Theorem 9.4.
  • Main bound: The centroid splits into semisimple and nilpotent parts; its semisimple dimension is bounded by the smallest local dimension, while the nilpotent part requires the main argument.The centroid projections into the endomorphism spaces are injective.
  • Equality cases: Equality in the dimension bound occurs precisely when C has nilpotency class 2 and T is isomorphic to a big centroid tensor.The proof derives this through equality conditions in Gromov’s inequality and suitable basis choices.
  • Scope and assumptions: Conciseness is necessary: for the zero tensor, the centroid can contain a much larger nilpotent algebra than the theorem’s bounds allow.The cited remark contrasts the zero-tensor centroid with the bounds under the concise hypothesis.
  • Inductive proof: For a nilpotent centroid subalgebra C, the proof uses filtrations of the local spaces and a tensor filtration to reduce the nilpotency class inductively.The induction constructs a reduced tensor, maps C into its centroid, and embeds the kernel into a tensor-product subspace.
  • Inductive proof: The base case k = 2 bounds contractions of the image of an injective map σ using Gromov’s tensorial reduction inequality.Equality analysis uses conciseness to identify the relevant contraction with the full tensor product of quotient spaces.

10. A proof of Gromov’s Inequality

This section proves Gromov’s tensorial reduction inequality by translating tensor contractions into set projections and applying the combinatorial Shearer inequality.

  • Classical projection inequalities: The proof begins from the classical projection inequalities of Loomis–Whitney and Shearer and develops their tensorial analogue.The section also records a broader vector-space formulation due to Gromov.
  • Classical projection inequalities: A fractional cover assigns nonnegative weights to subsets so that every index is covered with total weight at least one.This is the combinatorial structure used in Shearer’s inequality and its tensorial generalization.
  • Leading sets and contractions: Compatible orders on tensor-product bases allow leading sets of subspaces to behave like projections under contractions.Lexicographic orders provide compatible extensions, with a cancellation property under tensoring by a common basis element.
  • Leading sets and contractions: Proposition 10.9 shows that the leading set of a contraction is contained in the corresponding projection of the leading set.The proof chooses a dual basis vector to isolate the relevant tensor factor while preserving the leading term.
  • Tensorial reduction: Theorem 10.5 follows by identifying basis tensors with elements of a product set, so tensor contractions coincide with set projections and Shearer’s inequality applies.The resulting chain combines the combinatorial bound with Proposition 10.9.
  • Tensorial reduction: Theorem 9.7 is obtained as a special case using the fractional cover that weights each codimension-one subset by 1/(|I|−1).The section also analyzes equality through equality conditions in the combinatorial and contraction inequalities.
Loading 2608.27434v1…