A D V E R T |
I S E M E N T |
| Math Sites: lean ages 13-∞ readme referees parents | >>> MAITH GAMES <<< | all 372 compute stand |
|
LEVEL 1 OF 3 · Matrix multiplication with exponent at most $9/4$
An Upper Bound of 9/4 for the Matrix Multiplication Exponent
expertly designed by an internal OpenAI model · released 2026-10-02
· original PDF
IntroductionThe exponent \(\omega\) of matrix multiplication over \(\mathbb C\) is the infimum of the real numbers \(\tau\) such that, for every \(\varepsilon>0\), two \(n\times n\) matrices can be multiplied in \(O_\varepsilon(n^{\tau+\varepsilon})\) scalar arithmetic operations. The dimension \(n\) tends to infinity; the algorithm and its constants may depend on \(\varepsilon\). We prove the following bound. Theorem 1. For every \(\varepsilon>0\), two \(n\times n\) complex matrices can be multiplied using \(O_\varepsilon(n^{9/4+\varepsilon})\) arithmetic operations. In particular, \(\omega\leq9/4\). Strassen’s seven-product algorithm for two-by-two matrices showed that recursion can reduce the arithmetic exponent below three [13]. Bilinear algorithms can be represented by trilinear coefficient arrays, or tensors; linear substitutions and tensor products then express reductions and recursive composition. Approximate bilinear algorithms enlarge the available constructions, and Bini’s interpolation argument converts them into exact asymptotic algorithms [3]. Schönhage’s asymptotic sum inequality turns efficient simultaneous computations of independent matrix products into bounds on the exponent [11]. Strassen’s laser method extracts such independent products from tensor powers [14, 15]. His asymptotic spectrum describes asymptotic tensor comparisons through numerical invariants compatible with sums, products, and restrictions [16, 4]. Coppersmith and Winograd combined tensor powers with progression-free sets to extract independent products from an auxiliary form [5]. Higher-power analyses by Stothers [12] and Davie–Stothers [6], Vassilevska Williams [18], and Le Gall [10] developed this construction; Le Gall formulated its analysis through convex optimization. Alman and Vassilevska Williams refined the extraction of independent components [2]. Duan, Wu, and Zhou analyzed losses caused by combining components across recursion levels [7]. Further asymmetric analyses by Vassilevska Williams, Xu, Xu, and Zhou [19] and Alman et al. [1] improved the resulting bounds. Dupont et al. report \(\omega<2.371177\) by optimizing this combination-loss framework [8]. The present proof combines explicit tensor degenerations with the spectral viewpoint. It derives inequalities for character values on polynomial multiplication, then uses their discrete growth to bound the values on matrix multiplication. Interpolation, counting words with prescribed frequencies, and balancing the tensor legs retain their roles from the earlier tensor-power methods. The central finite construction here separates blocks that already have independent variables on two of their three legs. Theorem 1 concerns the asymptotic arithmetic exponent; its proof does not specify a competitive finite matrix size. Separation and polynomial multiplication.The three variable groups of a trilinear form are called legs. A basic difficulty in tensor constructions is that useful pieces can share variables. A full direct sum requires independent variables on all three tensor legs. Our principal construction starts with blocks that are independent on two legs and share the third. A finite Fourier projection supplies a tentative block label on the shared leg, and a degeneration whose total weight is the square of the label mismatch retains exactly the correct labels. The resulting independent blocks each carry an auxiliary dot product. The number of output blocks compensates for the cost of the Fourier copies at the exponential scale. Proposition 5 and Corollary 6 give this construction and its entropy consequence for arbitrary tensors with this block structure. We apply the separation inequality to ordinary polynomial multiplication. A determinant filtration compares neighboring input degrees, while a three-sector decomposition compares one input length with roughly three times that length. The determinant filtration is preserved by every multiplication map, so one choice of bases and weights works simultaneously for all first-input slices. Route to the exponent.We use Strassen’s spectral viewpoint [16, 4]: tensor characters are normalized numerical invariants that add on direct sums, multiply on tensor products, and are monotone under restriction. The detecting-character result, Lemma 3, makes it sufficient to bound these invariants on matrix multiplication for every character. Each character has value \(n^{3t}\) there for a positive parameter \(t\). Multiplication of polynomials with coefficient vectors of lengths \(a,b\) has an output vector of length \(a+b-1\). We measure this tensor by a normalized geometric mean of its character values under all six permutations of the legs. The resulting profile \(P(a,b)\) is positive and symmetric in the input lengths. Polynomial interpolation gives \(P(a,b)\leq(a+b-1)^{1/t}\). The two constructions above show that its successive increments do not increase in either input length and that \[P(a,3h+a-1)\geq3P(a,h).\] Together with \(P(1,b)=b\), these properties force \(P(a,a)\geq a^{4/3}\). Comparing the two growth rates yields \(t\leq3/4\), hence \(3t\leq9/4\). Section 2 introduces the character framework and states the required existence result. Section 3 proves the separation inequality, and Section 4 derives the two polynomial inequalities. Section 5 proves the discrete growth estimate and completes the arithmetic argument. Appendix 6 gives a complete proof of the character-existence result used here. Tensors and their charactersWe first describe the numerical invariants to which the constructions will be applied. Throughout, tensors are finite trilinear forms over \(\mathbb C\). Their three variable groups are called the \(X\)-, \(Y\)-, and \(Z\)-legs. A restriction applies an independent linear substitution on each leg. We write \(A\geq B\) if \(B\) is a restriction of \(A\). The tensor product multiplies coefficient arrays and pairs the corresponding variable indices on each leg. Let \(S\) be the set of tensors modulo mutual restriction. Full direct sum and tensor product make \(S\) a commutative semiring, and restriction induces an order compatible with both operations. We write products either by juxtaposition or by \(\otimes\). The zero tensor is \(0\), the scalar tensor \(xyz\) is \(1\), and the integer \(m\geq0\) denotes the direct sum of \(m\) copies of \(1\). Thus \(mA=A^{\oplus m}\). In a full direct sum, the summands have disjoint variables on all three legs. The tensor rank \(\mathop{\mathrm{R}}(A)\) is the least integer \(m\) with \(m\geq A\). It is finite by expansion in bases. Every nonzero tensor restricts to \(1\), by evaluating its three arguments on suitable lines, so \[ \mathop{\mathrm{R}}(A)\geq A\geq1\qquad(A\ne0). \tag{1}\] Rank is monotone, subadditive, and submultiplicative. We do not assume its additivity. A leg flattening is the matrix obtained by placing that leg against the pair of other legs. Its matrix rank is restriction-monotone, additive on full direct sums, and multiplicative on tensor products. The trilinear form encoding \(n\times n\) matrix multiplication and its exact-rank exponent are \[ T_n=\sum_{i,j,k=1}^n x_{ij}y_{jk}z_{ki}, \qquad \nu=\inf_{n\geq2}\log_n\mathop{\mathrm{R}}(T_n). \tag{2}\] Reindexing identifies \(T_nT_m\) with \(T_{nm}\). Flattening and the displayed expansion give \(n^2\leq\mathop{\mathrm{R}}(T_n)\leq n^3\), so \(2\leq\nu\leq3\) and \(\mathop{\mathrm{R}}(T_n)\geq n^\nu\). At the end of the proof we convert the bound on \(\nu\) into the asserted arithmetic bound. Definition 2. A tensor character is an additive, multiplicative, restriction-monotone map \(\lambda:S\to\mathbb R_{\geq0}\) with \(\lambda(1)=1\). The three flattening ranks are examples. Characters are the spectral points of the tensor semiring [16, 4]. They satisfy \(\lambda(m)=m\) and \(1\leq\lambda(A)\leq\mathop{\mathrm{R}}(A)\) for \(A\ne0\). The following special case of spectral separation is the only existence statement needed. Its proof in Appendix 6 uses finite dimensional separation, compactness, and a fixed-point theorem. Lemma 3 (Detecting characters). Let \(d\geq2\) and \(k\geq0\) be integers with \(k<d^\nu\), where \(\nu\) is defined by (2). There is a tensor character \(\lambda\) with \(\lambda(T_d)\geq k\). Dot-product exponentsFor \(m\geq1\), define the oriented dot products by \[B_X(m)=x\sum_{i=1}^m y_i z_i,\] and \(B_Y(m),B_Z(m)\) obtained by cyclically permuting the legs. For any character there are numbers \(p_X,p_Y,p_Z\in[0,1]\) such that \[ \lambda(B_X(m))=m^{p_X},\qquad \lambda(B_Y(m))=m^{p_Y},\qquad \lambda(B_Z(m))=m^{p_Z}. \tag{3}\] Indeed, \(f(m)=\lambda(B_X(m))\) is positive and nondecreasing, satisfies \(f(mn)=f(m)f(n)\), and lies between \(1\) and \(m\). Put \(p_X=\log_2 f(2)\). For \(r\geq1\), let \(\ell=\lfloor r\log_2m\rfloor\). Comparison with \(2^\ell\leq m^r<2^{\ell+1}\) gives \(f(2)^\ell\leq f(m)^r\leq f(2)^{\ell+1}\). Taking logarithms and letting \(r\to\infty\) proves the first identity; the other two follow in the same way. The product \(B_X(m)B_Y(m)B_Z(m)\) has variables \(x_{bc},y_{ac},z_{ab}\) and monomials \(x_{bc}y_{ac}z_{ab}\), so it is isomorphic to \(T_m\). Consequently \[ \lambda(T_m)=m^{p_X+p_Y+p_Z}. \tag{4}\] Setting all off-diagonal variables of \(T_m\) to zero leaves \(m\) independent scalar products. Hence \(T_m\geq m\), and \(p_X+p_Y+p_Z\geq1\). In particular, the parameter \(t=(p_X+p_Y+p_Z)/3\) used below is always positive. Degenerations and interpolationWe use only the following elementary form of degeneration. After fixed linear substitutions, give each variable an integer weight, multiply it by the corresponding power of a parameter \(\varepsilon\), and retain the terms of minimum total weight. Write \(A\mathrel{\rightsquigarrow}B\) if this procedure takes \(A\) to \(B\), with the convention \(0\mathrel{\rightsquigarrow}0\). Individual weights may be negative. Shifting the minimum total weight to zero makes the resulting tensor a polynomial in \(\varepsilon\) with constant coefficient \(B\). Lemma 4 (Interpolation). If \(A\mathrel{\rightsquigarrow}B\), then \(\lambda(A)\geq\lambda(B)\) for every tensor character \(\lambda\). Proof. This is the interpolation passage from approximate to exact bilinear algorithms [3], applied to characters. Let \(F(\varepsilon)=B+\varepsilon F_1+\cdots+\varepsilon^L F_L\) be the transformed tensor. For each nonzero \(\varepsilon\), it is a restriction of \(A\). The polynomial \(F(\varepsilon)^{\otimes j}\) has degree at most \(jL\) and constant coefficient \(B^{\otimes j}\). Interpolation at \(jL+1\) distinct nonzero points writes this coefficient as a linear combination of specializations. A linear combination of tensors on common spaces is a restriction of their full direct sum: identify the corresponding variables and absorb each scalar coefficient into one leg. Therefore \[\lambda(B)^j\leq(jL+1)\lambda(A)^j.\] Taking \(j\)th roots and letting \(j\to\infty\) proves the result. The degeneration, and hence \(L\), is fixed during this limit. ◻ Separating a shared tensor legSuppose blocks share their first leg, while each of the other two legs determines the same block label. The following construction makes the blocks fully independent. Its auxiliary factor is retained in the output and will supply the entropy gain. Proposition 5 (Finite separation). Let \(M\geq1\) and \[A=\sum_{h=1}^M A_h,\qquad A_h\in X\otimes Y_h\otimes Z_h,\] where the \(Y_h\) are disjoint coordinate spaces and so are the \(Z_h\). There are no terms between unmatched second- and third-leg sectors. Then \[ A^{\oplus5M}\mathrel{\rightsquigarrow} \bigoplus_{h=1}^M\bigl(A_h\otimes B_X(M)\bigr). \tag{5}\] Each \(A_h\) on the right has its own copy of \(X\). Proof. Choose a common first-leg basis \(x_a\) and sector bases \(y_{h,b},z_{h,c}\), and write \[A=\sum_{h,a,b,c}c_{h,a,b,c}x_a y_{h,b}z_{h,c}.\] The internal index ranges may depend on \(h\). Set \(L=5M\), and choose a primitive \(L\)th root of unity \(\zeta\). Index the \(L\) source copies by \(r=0,\ldots,L-1\). Introduce target variables \(X_{a,g},Y_{h,b,u},Z_{h,c,v}\), where \(g,u,v\in\{1,\ldots,M\}\). The index \(g\) is a tentative sector label; \(u,v\) will supply the retained dot product. Make the substitutions \[\begin{align*} x_a^{(r)}&\longmapsto\sum_{g=1}^M\zeta^{2rg}X_{a,g},\\ y_{h,b}^{(r)}&\longmapsto\sum_{u=1}^M\zeta^{r(u-h)}Y_{h,b,u},\\ z_{h,c}^{(r)}&\longmapsto\frac1L\sum_{v=1}^M \zeta^{r(-v-h)}Z_{h,c,v}. \end{align*}\] All copies map into the same target spaces. Summing over \(r\) multiplies each target coefficient by \[\frac1L\sum_{r=0}^{L-1}\zeta^{r[u-v+2(g-h)]}.\] This is the indicator of equality modulo \(L\). Since \(|u-v+2(g-h)|\leq3(M-1)<L\), precisely the terms satisfying \[ u-v+2(g-h)=0 \tag{6}\] survive. The phase on each leg uses only indices already present on that leg. To force the tentative label \(g\) to equal \(h\), give the target variables the weights \[w(X_{a,g})=g^2,\qquad w(Y_{h,b,u})=hu-h^2,\qquad w(Z_{h,c,v})=-hv.\] On every surviving term, (6) gives \[g^2+hu-h^2-hv=(g-h)^2\geq0.\] The weight-zero tensor is therefore \[D=\sum_{h,a,b,c,u}c_{h,a,b,c}X_{a,h}Y_{h,b,u}Z_{h,c,u}.\] All three variable groups distinguish \(h\). For each fixed \(h\), the remaining equality of the \(u\) indices supplies exactly \(B_X(M)\). Thus \(D\) is the full direct sum in (5). The transformed tensor has degree at most \((M-1)^2\), even though some individual variable weights are negative. ◻ The source in (5) uses \(5M\) copies in total. The output has \(M\) full direct-sum blocks, each with an \(M\)-dimensional dot product. These are two different multiplicities: the dot-product index does not label additional full direct-sum blocks. Corollary 6 (Shared-leg entropy inequality). Let \(T=\sum_{i=1}^s T_i\) be a sum of nonzero tensors with a common first space and matched, pairwise disjoint sectors on the other two legs, as in Proposition 5. For every tensor character \(\lambda\) and every probability vector \(q=(q_1,\ldots,q_s)\), \[ \lambda(T)\geq e^{p_X H(q)}\prod_{i=1}^s\lambda(T_i)^{q_i}, \qquad H(q)=-\sum_{i=1}^s q_i\log q_i. \tag{7}\] Here logarithms are natural and \(0\log0=0\). Proof. We use the fixed-frequency counting familiar from tensor-power arguments; see, for example, [10]. Proposition 5 turns the number of words of a given frequency into the entropy factor in (7). First take \(q\) rational and let \(N\) run through multiples of a common denominator. On the second and third legs of \(T^{\otimes N}\), retain only words with \(Nq_i\) occurrences of sector \(i\). Every supported term has the same sector word on these two legs. The retained tensor \(A\) therefore has \[M=\frac{N!}{\prod_i(Nq_i)!}\] matched sectors, with the first leg still shared. Each sector is a product of the prescribed \(T_i\), up to reordering factors, and hence has character value \(C_N=\prod_i\lambda(T_i)^{Nq_i}\). Proposition 5 and Lemma 4 give \[5M\lambda(T)^N\geq5M\lambda(A)\geq M^{1+p_X}C_N.\] Cancel \(M\) and take \(N\)th roots. Stirling’s formula gives \(N^{-1}\log M\to H(q)\), proving (7) for rational \(q\). For each fixed \(N\), degeneration monotonicity was established first; no uniform bound on its degree as \(N\) grows is required. Finally, \(\lambda(T_i)\geq1\), so the right side of (7) is continuous on the probability simplex. Rational approximation proves the result for all \(q\). ◻ Two inequalities for polynomial multiplicationWe now apply the shared-leg inequality to a family with a simple rank bound. For positive integers \(a,b\), let \[ C(a,b)=\sum_{i=0}^{a-1}\sum_{j=0}^{b-1}x_i y_j z_{i+j}. \tag{8}\] This is multiplication of homogeneous binary forms of degrees \(a-1\) and \(b-1\), paired with the dual of the output space. Evaluation at \(a+b-1\) distinct points followed by interpolation gives \(\mathop{\mathrm{R}}(C(a,b))\leq a+b-1\). Its output flattening has rank \(a+b-1\), since every output monomial is a product of input monomials. Hence \[ \mathop{\mathrm{R}}(C(a,b))=a+b-1. \tag{9}\] Fix a character \(\lambda\), put \(t=(p_X+p_Y+p_Z)/3>0\), and let \(\lambda_\pi(A)\) denote its value after permuting the legs of \(A\) by \(\pi\in S_3\). Each \(\lambda_\pi\) is again a character; denote its first-leg dot-product exponent by \(p_X^{(\pi)}\). Each of the three original exponents occurs twice, so \[ \sum_{\pi\in S_3}p_X^{(\pi)}=2(p_X+p_Y+p_Z)=6t. \tag{10}\] Products over permuted legs are a standard balancing device in tensor-power analysis [10]. Here all six permutations make the profile insensitive to the leg exchanges used below. Define the symmetrized profile \[ P(a,b)=\left(\prod_{\pi\in S_3}\lambda_\pi(C(a,b))\right)^{1/(6t)}. \tag{11}\] Interchanging the input legs permutes the factors in this product. Also \(C(1,b)=B_X(b)\). Together with (9) and (10), these observations give \[ P(a,b)=P(b,a)>0,\qquad P(1,b)=b,\qquad P(a,b)\leq(a+b-1)^{1/t}. \tag{12}\] The next two lemmas give the additional constraints that force the diagonal values of \(P\) to grow. A determinant filtrationWe obtain neighboring input lengths by tensoring with \(B_X(2)\), which doubles the second-input and output spaces, and retaining the multiplication induced on suitable quotient and kernel spaces. The filtration must be preserved by multiplication by every first input, so that the resulting comparison is a degeneration of the whole tensor. Lemma 7 (Discrete concavity). For \(a\geq1\) and \(b\geq2\), \[ 2P(a,b)\geq P(a,b+1)+P(a,b-1). \tag{13}\] By symmetry, the analogous inequality holds in the first argument. Proof. Let \(V_e\) be the degree-\(e\) homogeneous forms in \(u,v\), and set \(W_1=\operatorname{span}(s,w)\) for a second pair of variables. The tensor \(C(a,b)\otimes B_X(2)\) represents multiplication \[V_{a-1}\times(V_{b-1}\otimes W_1) \longrightarrow V_{a+b-2}\otimes W_1.\] Put \(D=uw-vs\). For \(e\geq1\), diagonal substitution \((s,w)=(u,v)\) gives the exact sequence \[ 0\longrightarrow D V_{e-1} \longrightarrow V_e\otimes W_1 \longrightarrow V_{e+1}\longrightarrow0. \tag{14}\] The last map is surjective on monomials. Its kernel contains \(DV_{e-1}\); multiplication by \(D\) is injective, and both the kernel and \(V_{e-1}\) have dimension \(e\), proving exactness. This is the determinant exact sequence underlying the degree-one Clebsch–Gordan construction [9]. We next check the compatibility with all multiplication maps that is needed for the tensor degeneration. Choose quotient lifts \(u^{e-i}v^i s\) for \(0\leq i\leq e\), followed by \(v^e w\), and append the kernel basis \(D u^{e-1-j}v^j\) for \(0\leq j<e\). Their diagonal images and their kernel factors are the standard monomial bases. Use these bases at degrees \(b-1\) and \(a+b-2\). For every \(f\in V_{a-1}\), multiplication commutes with diagonal substitution and sends \(Dg\) to \(D(fg)\). Thus every slice has the form \[ \begin{array}{c|cc} &\text{input quotient}&\text{input kernel}\\ \hline \text{output quotient}&M_f^{+}&0\\ \text{output kernel}& * &M_f^{-} \end{array} \tag{15}\] in these fixed bases. Here \(M_f^{+}\) is multiplication \(V_b\to V_{a+b-1}\), and \(M_f^{-}\) is multiplication \(V_{b-2}\to V_{a+b-3}\). In particular, the two diagonal tensor blocks are exactly \(C(a,b+1)\) and \(C(a,b-1)\). Give weight zero to the first leg and to all quotient coordinates, weight \(-1\) to the second-leg kernel coordinates, and weight \(+1\) to the output-dual kernel coordinates. The only potentially negative block in (15) is zero. The block marked \(*\) has weight \(+1\) and disappears. The weight-zero tensor therefore consists of \(C(a,b+1)\) and \(C(a,b-1)\), with a common first leg and disjoint second and third legs. For example, when \(a=b=2\), the identity \(u(vw)=v^2s+vD\) shows that multiplication of a quotient lift can have both quotient and kernel components. Applying degeneration monotonicity and Corollary 6 to these two blocks, for any probability pair \(q=(q_+,q_-)\) we obtain \[2^{p_X^{(\pi)}}\lambda_\pi(C(a,b)) \geq e^{p_X^{(\pi)}H(q)} \lambda_\pi(C(a,b+1))^{q_+} \lambda_\pi(C(a,b-1))^{q_-}.\] Use the same \(q\) for all six characters. By (10), multiplication and the power \(1/(6t)\) yield \[2P(a,b)\geq e^{H(q)}P(a,b+1)^{q_+}P(a,b-1)^{q_-}.\] For positive \(A,B\), the maximum of \(e^{H(q)}A^{q_+}B^{q_-}\) is \(A+B\), attained at \(q=(A,B)/(A+B)\). For positive \(q_+,q_-\), this follows from the weighted arithmetic-geometric mean inequality applied to \(A/q_+\) and \(B/q_-\); the boundary follows by continuity. Taking this common maximizing pair proves (13). ◻ Three sectorsLemma 8 (Shifted tripling). For all positive integers \(a,h\), \[ P(a,3h+a-1)\geq3P(a,h). \tag{16}\] Proof. Put \(B=3h+a-1\). A supported term of \(C(a,B)\) has indices \(0\leq x<a\), \(0\leq y<B\), and \(z=x+y\). Partition the \(Y\)-indices and \(Z\)-indices as follows: \[\begin{array}{c|ccc} &\text{left}&\text{middle}&\text{right}\\ \hline Y &[0,h-1]&[h,2h+a-2]&[2h+a-1,3h+a-2]\\ Z &[0,h+a-2]&[h+a-1,2h+a-2]&[2h+a-1,3h+2a-3]. \end{array}\] Give weight \(+1\) to middle \(Y\)-coordinates, weight \(-1\) to middle \(Z\)-coordinates, and zero to all other coordinates. A left \(Y\)-index forces a left \(Z\)-index, because \(x+y\leq h+a-2\); a right \(Y\)-index forces a right \(Z\)-index. Thus no supported term has negative weight. The weight-zero part consists exactly of the three matched sectors. Figure 1 shows the smallest nontrivial example. Translations identify the two outer branches with \(C=C(a,h)\). The middle branch is \[\sum_{u=0}^{a-1}\sum_{r=0}^{h-1} x_{a-1-u}y_{h+u+r}z_{h+a-1+r}.\] It is \(C\) with its second and third legs exchanged and its first-leg basis reversed. The reversal identifies this individual branch; no different first-leg maps are applied to the three branches of the whole tensor. Let \(\sigma\) exchange the second and third legs. The uniform probability vector on the three branches gives \[\lambda_\pi(C(a,B))\geq 3^{p_X^{(\pi)}}\lambda_\pi(C)^{2/3} \lambda_\pi(C^\sigma)^{1/3}.\] Composition with \(\sigma\) permutes the six leg permutations. Thus \(\prod_\pi\lambda_\pi(C^\sigma)=\prod_\pi\lambda_\pi(C)\). Multiplying the six inequalities and taking the power \(1/(6t)\) proves (16). ◻ Discrete growth and the arithmetic exponentThe tensor constructions are complete. The following lemma turns the profile’s concavity and shifted tripling into growth along the diagonal. Lemma 9 (Diagonal growth). Let \(P:\mathbb N_{>0}^2\to\mathbb R_{>0}\) be symmetric, with \(P(1,b)=b\). Suppose it satisfies (13) for \(a\geq1,b\geq2\) and (16) for \(a,h\geq1\). Then \(P(a,a)\geq a^{4/3}\) for every \(a\geq1\). Proof. For fixed \(a\), concavity makes the increments \(\Delta_{a,h}=P(a,h+1)-P(a,h)\) nonincreasing in \(h\). Set \(D_a=P(a,a)\) and \(H_a=2D_a/(3a-1)\). Tripling with \(h=a\) gives \[2D_a\leq P(a,4a-1)-D_a =\sum_{h=a}^{4a-2}\Delta_{a,h} \leq(3a-1)\Delta_{a,a}.\] Thus \(\Delta_{a,a}\geq H_a\). For \(a\geq2\), symmetry and concavity bound the two increments between consecutive diagonal values: \[ D_a-D_{a-1} =\Delta_{a-1,a-1}+\Delta_{a,a-1} \geq H_{a-1}+H_a. \tag{17}\] Substituting \(D_a=(3a-1)H_a/2\), rearranging, and iterating from \(H_1=1\) gives \[\begin{align*} H_a&\geq\left(1+\frac1{3(a-1)}\right)H_{a-1} &&(a\geq2),\\ H_a&\geq\prod_{m=1}^{a-1}\left(1+\frac1{3m}\right) &&(a\geq1). \tag{18}\end{align*}\] For \(a=1\) the product is empty and equals \(1\). For \(m\geq1\), the elementary inequality \((1+1/(3m))^3\geq1+1/m\) now gives \[H_a^3\geq\prod_{m=1}^{a-1}\left(1+\frac1{3m}\right)^3 \geq\prod_{m=1}^{a-1}\left(1+\frac1m\right)=a.\] Since \((3a-1)/2\geq a\), we conclude \(D_a\geq aH_a\geq a^{4/3}\). ◻ Proof of Theorem 1. For every character, the profile (11) satisfies all hypotheses of Lemma 9. Combining it with (12) gives \[a^{4/3}\leq P(a,a)\leq(2a-1)^{1/t}.\] Letting \(a\to\infty\) forces \(t\leq3/4\). Equation (4) therefore gives \(\lambda(T_d)\leq d^{9/4}\) for every character. For each integer \(d\geq2\), take \(k_d=\lceil d^\nu\rceil-1\). Then \(d^\nu-1\leq k_d<d^\nu\), so Lemma 3 supplies a character with \(\lambda(T_d)\geq k_d\). Hence \[d^\nu\leq d^{9/4}+1.\] Taking logarithms and letting \(d\to\infty\) yields \(\nu\leq9/4\). The detecting character may depend on \(d\); the upper bound applies uniformly to every character. To obtain an arithmetic algorithm, fix \(\varepsilon>0\) and choose \(0<\delta<\varepsilon\). The definition of \(\nu\) supplies a fixed integer \(u\geq2\) and an exact rank decomposition of \(T_u\) of length \(r<u^{9/4+\delta}\). Its bilinear identities remain valid on matrix blocks: their coefficients are central scalars, and each product has its left-input block before its right-input block. For \(N\) a power of \(u\), recursive application therefore has cost \[S(N)\leq rS(N/u)+C_{u,r}(N/u)^2.\] Flattening gives \(r\geq u^2\). Summing the recursion levels gives \(S(N)=O(N^{\log_u r})\) if \(r>u^2\), and \(S(N)=O(N^2\log N)\) if \(r=u^2\). Both are \(O_\varepsilon(N^{9/4+\varepsilon})\). Padding an arbitrary \(n\) to the next power of \(u\) increases its size by less than the fixed factor \(u\) and proves the theorem. ◻ Remark 10. All coefficients of the recursive algorithm are fixed once \(\varepsilon\) is chosen. The argument is in the complex arithmetic model. If algebraic coefficients are desired, the equations for an exact rank decomposition have rational coefficients; a complex solution therefore implies a solution over \(\overline{\mathbb Q}\), by the Nullstellensatz. The finitely many resulting coefficients lie in one number field. Existence of detecting charactersWe prove Lemma 3 directly within the asymptotic-spectrum framework [16, 4]. A state is a normalized, additive, restriction-monotone map \(S\to\mathbb R_{\geq0}\). Every state satisfies \(0\leq\lambda(s)\leq\mathop{\mathrm{R}}(s)\), and \(\lambda(s)\geq1\) for \(s\ne0\). A character is a state that is also multiplicative. Fix integers \(d\geq2\) and \(k\geq0\) with \(k<d^\nu\). To obtain a character with \(\lambda(T_d)\geq k\), we will construct states satisfying the stronger family of inequalities \[ \lambda(T_ds)\geq k\lambda(s)\qquad(s\in S). \tag{19}\] This family is preserved by normalized tensor multiplication: for any nonzero \(z\), replacing \(\lambda(x)\) by \(\lambda(zx)/\lambda(z)\) preserves every inequality by applying (19) to \(zs\). The next lemma explains why this invariance produces multiplicativity in a nonempty compact convex family of states. We will then prove that the required family is nonempty. An empty family would give tensors \(D\) and \(s\ne0\) with \(D+ks\geq D+T_ds\). Repeating this conversion while keeping \(D\) fixed would contradict \(k<d^\nu\). Obtaining multiplicativityLemma 11. Let \(\mathcal K\) be a nonempty compact convex set of states in the topology of coordinatewise convergence. Suppose that, for every nonzero \(z\in S\), the map \[(P_z\lambda)(x)=\frac{\lambda(zx)}{\lambda(z)}\] takes \(\mathcal K\) into itself. Then \(\mathcal K\) contains a multiplicative state. Proof. Since \(\lambda(z)\geq1\), each \(P_z\) is continuous in the product topology. The space \(\mathbb R^S\) is Hausdorff and locally convex, so the Schauder–Tychonoff fixed-point theorem [17] applies: a continuous self-map of a nonempty compact convex subset of such a space has a fixed point. Choose a fixed point \(\mu\) of \(P_z\) and freeze \(c=\mu(z)\). The subset \[\mathcal K'= \{\lambda\in\mathcal K:\lambda(zx)=c\lambda(x) \text{ for every }x\in S\}\] is nonempty and compact. Because \(c\) is fixed, its defining equations are linear in \(\lambda\), so it is convex. Taking \(x=1\) shows that \(\lambda(z)=c\) throughout \(\mathcal K'\), so all its members are fixed by \(P_z\). Moreover, every \(P_w\) with \(w\ne0\) preserves it: \[(P_w\lambda)(zx)=\frac{\lambda(zwx)}{\lambda(w)} =c\frac{\lambda(wx)}{\lambda(w)} =c(P_w\lambda)(x).\] The construction can be repeated in \(\mathcal K'\), retaining all earlier frozen equations. By induction, every finite collection of the original maps \(P_z\) has a common fixed point in \(\mathcal K\). Their fixed sets are closed, so compactness and the finite intersection property give a simultaneous fixed point for all nonzero \(z\). It satisfies \(\lambda(zx)=\lambda(z)\lambda(x)\) for \(z\ne0\). Additivity implies \(\lambda(0)=0\), which handles multiplication by zero. ◻ Constructing the detecting state spaceProof of Lemma 3. For the fixed integers \(d,k\) above, let \(\mathcal K\) be the subset of \(\prod_{s\in S}[0,\mathop{\mathrm{R}}(s)]\) defined by normalization, additivity, monotonicity, and (19). These conditions are closed affine equalities and inequalities. The product is compact, so \(\mathcal K\) is compact and convex. We must first show that it is nonempty. Suppose it were empty. Compactness supplies a finite inconsistent subsystem of the defining conditions. Let \(E\subset S\) contain every coordinate appearing in this subsystem, together with \(0\) and \(1\). Adjoin \(\lambda(0)=0\), \(\lambda(1)=1\), and write each coordinate bound homogeneously as \[\lambda(s)\geq0,\qquad \mathop{\mathrm{R}}(s)\lambda(1)-\lambda(s)\geq0\quad(s\in E).\] The resulting finite system remains inconsistent. Let \(e_s\), \(s\in E\), be the coordinate vectors of \(\mathbb R^E\). Quotient by the span of the selected additive relation vectors and \(e_0\), and write \(u\) for the image of \(e_1\). Let \(C\) be the cone generated by the images of all inequality vectors. Before taking the quotient, these vectors have the forms \[e_b-e_a\ (b\geq a),\qquad e_{T_ds}-ke_s,\qquad e_s,\qquad \mathop{\mathrm{R}}(s)e_1-e_s.\] The finitely generated cone \(C\) is closed. If \(-u\notin C\), separation gives a linear functional \(L\) nonnegative on \(C\) with \(L(u)>0\). Dividing by \(L(u)\) would give a normalized solution of the finite subsystem, including its bounds. This contradicts inconsistency, so \(-u\in C\). All vectors and relations have integer coefficients. Membership \(-u\in C\) is a feasible rational linear system, so there are rational nonnegative cone coefficients and rational coefficients for the relation vectors. Clearing denominators yields a positive integer \(m\) and an identity with nonnegative integer coefficients on the inequality vectors. Map this identity to the additive Grothendieck group of \(S\) by sending \(e_s\) to \([s]\). This group adjoins formal additive inverses to the commutative monoid \((S,+)\); in particular, all additive relation vectors map to zero. The bound vectors map to the order differences \([s]-[0]\) and \([\mathop{\mathrm{R}}(s)]-[s]\). Direct sums combine the ordinary order differences into \([y]-[x]\) with \(y\geq x\). Distributivity combines the special differences into \([T_ds]-k[s]\) for one \(s\in S\). We obtain \[-m[1]=[y]-[x]+[T_ds]-k[s],\qquad y\geq x.\] Equality in this group means equality after adding a common element of the monoid. Thus there is \(c\in S\) with \[m+y+T_ds+c=x+ks+c.\] Put \(D=y+c\). Using \(y\geq x\) gives the catalytic comparison \[ D+ks\geq D+m+T_ds. \tag{20}\] Here \(s\ne0\): otherwise \(D\geq D+m\), contradicting the additivity and monotonicity of any flattening rank. Ruling out the obstruction. The tensor \(D\) is a fixed additive cost. Reusing (20) converts \(nk\) copies of \(s\) into \(n\) copies of \(T_ds\) while paying for \(D\) only once. We show that this contradicts the definition of \(\nu\). Additive iteration gives, for every integer \(n\geq1\), \[D+nks\geq D+nm+nT_ds\geq nT_ds.\] Since \(s\geq1\), we have \(\mathop{\mathrm{R}}(D)s\geq\mathop{\mathrm{R}}(D)\geq D\). With \(K=nk+\mathop{\mathrm{R}}(D)\), it follows that \[ Ks\geq nT_ds,\qquad K^js\geq n^jT_{d^j}s\quad(j\geq1). \tag{21}\] For the induction, multiply the \(j\)th comparison by \(K\), then use \(Ks\geq nT_ds\): \[K^{j+1}s\geq n^jT_d^j(Ks)\geq n^{j+1}T_d^{j+1}s.\] This keeps a single factor \(s\) and requires no cancellation. Also \(K>0\), since the first right-hand side in (21) is nonzero. We next use the \(n^j\) scalar copies to obtain a second matrix-multiplication factor. Its matrix dimension will multiply \(d^j\), while the auxiliary tensor \(s\) still occurs only once. Fix \(n\) and \(\delta>0\). By the definition of \(\nu\), choose a fixed integer \(u\geq2\) with \(\mathop{\mathrm{R}}(T_u)\leq u^{\nu+\delta}\), and set \[\ell_j=\left\lfloor\frac{j\log_u n}{\nu+\delta}\right\rfloor, \qquad g_j=u^{\ell_j}.\] Submultiplicativity gives \[\mathop{\mathrm{R}}(T_{g_j})\leq\mathop{\mathrm{R}}(T_u)^{\ell_j} \leq u^{(\nu+\delta)\ell_j}\leq n^j.\] Thus the diagonal tensor \(n^j\) restricts to \(T_{g_j}\). Multiplying this restriction by \(T_{d^j}s\) and using \(s\geq1\), we obtain \[K^js\geq n^jT_{d^j}s\geq T_{d^jg_j}s\geq T_{d^jg_j}.\] A direct sum of \(K^j\) copies of \(s\) has rank at most \(K^j\mathop{\mathrm{R}}(s)\). Therefore \[\mathop{\mathrm{R}}(s)K^j\geq\mathop{\mathrm{R}}(T_{d^jg_j})\geq(d^jg_j)^\nu.\] First let \(j\to\infty\), keeping \(n,\delta,u\) fixed. Since \(g_j^{1/j}\to n^{1/(\nu+\delta)}\), taking \(j\)th roots gives \[nk+\mathop{\mathrm{R}}(D)\geq d^\nu n^{\nu/(\nu+\delta)}.\] Next let \(\delta\downarrow0\) at fixed \(n\); the choice of \(u\) has disappeared from the inequality. We get \(nk+\mathop{\mathrm{R}}(D)\geq nd^\nu\). Finally divide by \(n\) and let \(n\to\infty\). The catalyst \(D\) is fixed, so \(k\geq d^\nu\), a contradiction. Consequently \(\mathcal K\) is nonempty. Completing the construction. For nonzero \(z\), the map \(P_z\) of Lemma 11 preserves normalization, additivity, and monotonicity. It preserves (19), because \[(P_z\lambda)(T_ds)=\frac{\lambda(T_dzs)}{\lambda(z)} \geq k\frac{\lambda(zs)}{\lambda(z)}=k(P_z\lambda)(s).\] Its coordinate bounds follow from \(zx\leq\mathop{\mathrm{R}}(x)z\). Lemma 11 supplies a multiplicative state in \(\mathcal K\), hence a character. Taking \(s=1\) in (19) gives \(\lambda(T_d)\geq k\). ◻
|
| ||||||||
|