Matrix multiplication bounds from the Cohn-Kleinberg-Szegedy-Umans wreath-product construction

edit · history · discussion · files · short url · matrix multiplication algebra groups

Numbers

$m$

$\beta_m$

2.990753937707703139970783026611635176155644319857067189120274132252362529558585604497525000880969726

2.956359852567514481091122480901207422909434633039965839911936144749355184302653513522216439953716509

2.937905232085047521737880363020522579392030117236071157111272563464873399785405220690614540008755198

2.927092240124884489150974952664953944169635445102519229832617779828164415055765917288878118373944610

2.920394710309200458390594431718046055280563982326829731332541740434466437837642612877894326368931057

10:

2.916099605993080110111630444502420023063304272495700573786934570219515189357246433587279672309967425

11:

2.913292034189045065128839882925173966083497103900471242438527998904872874353105556546831013959467465

12:

2.911447540109136510693399465785494511407957834772220470829768826739357531008650355684854790699439413

13:

2.910248519007511425368643954807995390644301596040950461927118188135602806499769411075429980510549919

14:

2.909494025393406213130814389909077812200796544186563470942179446387182970643704589270822275831617550

15:

2.909052308915036564367932526716185536161036535944559010518972216905492478243755072416189761713077382

16:

2.908834400832565620312219361225295278891830231809227110216915438050352303189814850761233675008440105

17:

2.908778718610087474601011945323448012350759244408427840788380972101303261225657898168326304780495111

18:

2.908841735583051031431274546897247725200013843470027244670611023511065359730474511986521421400965980

19:

2.908992134738632658995700474599866920292333356370807587827726964158021498252436485956947152897568386

20:

2.909207038576903676180691544278752542833183470359951408075161023522682634468384766486449512690362716

21:

2.909469515965127110872071318136807892757794886980159655740880947922445429052508908198213874177559140

22:

2.909766896625643066337923379397613280843968454656032031982155395611081719629790956696003514243414061

23:

2.910089609115791169507494655147192621759600580805444210750015321897744184261478081002408280810003319

24:

2.910430365621464134077033614751789334254782116175390826343066662738630043976603759627489625827315330

25:

2.910783581052687627853082772658591459298002022711155060686466427232032506334229830630810545468008969

26:

2.911144953240649697768723398947962452637480212696157366027753150386049419119688158151122540660710832

27:

2.911511155681873018133000035008651175465420230229187618114171769886889996293882682991997729824549744

28:

2.911879610053583450997633683321681482931063560728518564483716393121562826530187099445595499060096944

29:

2.912248316019150048999136844350855473649508258157802319495458222771259966201960235807557270688658034

30:

2.912615722676905404389395013041527146949745322912694925821097521100009671105696611758548312621765826

31:

2.912980630615466762481663751800815511722484334868021423615010815967669717141511685223817309812953072

32:

2.913342116693726679077968849153133860884069153367862129042164001275795560615463855344673421120216223

33:

2.913699475852349786634763851066559799461940705203930915191517175294137894692679850543933769274736941

34:

2.914052175800943074907808744440028069055439163274658987756613527770691923265443572622501146340186838

35:

2.914399821517456226643635935754335162715818933341308312086475397839130692362443250929994708648041609

36:

2.914742127280987086081429902185063078161157059065541794702779204413741422324985119246845781806601509

37:

2.915078894528405430925745693353601535258957632011122099535436503931032026388400412270631851278248973

38:

2.915409994242074264834677342200188669893930765677991064643493564300786380024772043493263720852011654

39:

2.915735352883915725791495475884743549081466581386860902099814421951694819476410934586626629684822853

40:

2.916054941120463084567079530810771169604976586168892751445726251505728516098705358953527308113387879

Definition

For an integer $m\geq5$, let $\beta_m$ be the unique real root in $(2,3)$ of $[2m(m-1)]^{\beta_m}=2m^3+\binom{m^3}{2}2^{\beta_m}$. It is the exponent bound obtained from the full complex character-degree spectrum of the two-factor wreath-product construction in [3], Section 2.

Parameters

$m$

— order of each cyclic factor ($m\geq5$)

Formulas

(1)

$D_{m^3,2}(s)=2m^3+\binom{m^3}{2}2^s$ for the character-degree moment, and $[2m(m-1)]^{\beta_m}=D_{m^3,2}(\beta_m)$. In particular, $D_{m^3,2}(2)=2m^6=|G_m|$ and $D_{m^3,2}(3)=4m^6-2m^3$.

(2)

Put $A_m=2m(m-1)$ and $g_m(s)=2m^3A_m^{-s}+\binom{m^3}{2}(2/A_m)^s$. For $m\geq5$, both bases lie in $(0,1)$, so $g_m$ is strictly decreasing. Moreover, $g_m(2)=m^4/[2(m-1)^2]>1$ and $g_m(3)=(2m^3-1)/[4(m-1)^3]<1$. Thus $g_m(\beta_m)=1$ has exactly one root in $(2,3)$; the construction inequality $g_m(\omega)\geq1$ implies $\omega\leq\beta_m$.

(3)

$\displaystyle\beta_m<\gamma_m=\frac{6\log m-\log2}{\log(m(m-1))}<3$ for $m\geq5$, where $\log$ is the natural logarithm. The coarse estimate replaces $D_{m^3,2}(s)$ by $2^{s-1}m^6$, which is strictly larger for $s>2$ [1], Section 2.

Comments

(4)

Write $C_m$ for the cyclic group of order $m$, $H_m=(C_m)^3$, and $G_m=H_m\wr S_2=H_m^2\rtimes S_2$, where the nonidentity permutation $z$ swaps the two factors. Let $H_1,H_2,H_3$ be the coordinate subgroups of $H_m$ and set $H_4=H_1$. The subsets $S_i=\{(a,b)z^j:a\in H_i\setminus\{0\},\ b\in H_{i+1},\ j\in\{0,1\}\}$ realize square matrix multiplication of size $2m(m-1)$ by the triple product property [1], Lemma 2.1.

(5)

With $q=m^3$, the group $G_m$ has $2q$ linear characters and $\binom q2$ irreducible characters of degree $2$, including multiplicities and the trivial character. Equal base characters give the two linear extensions, and unordered pairs of distinct base characters give degree-two induced representations. This is the permutation-degree-two case of the colored-partition degree formula [2]. The associated character-degree power sums use $D_{q,n}(s)=\sum_{\chi\in\operatorname{Irr}_{\mathbb C}(C_q\wr S_n)}\chi(1)^s$; any abelian base of order $q$ has the same degree multiset.

(6)

The cyclic factor order is $m$ here and $n$ in Section 2 of [1]. In the companion moment notation, $n$ is the permutation degree, so this construction uses $q=m^3$ and $n=2$. All powers are positive real powers, and character sums are unnormalized.

(7)

For the matrix-multiplication exponent $\omega$ over $\mathbb C$, Theorem 1.8 of [1] gives $\omega\leq\beta_m$. These values describe one historical construction mechanism; they are neither values of the unknown exponent nor claims of current records.

(8)

The estimate in Section 2 of [1] uses only the largest character degree and gives the coarser bound $\gamma_m$ in (3). The entries use the full degree spectrum. Among the listed integers $5\leq m\leq40$, the smallest $\beta_m$ occurs at $m=17$.

Programs

(P1)

Python

# Approximate a further construction bound. This snippet is not a certificate.
import mpmath as mp
mp.mp.dps = 120

def beta(m):
    if not isinstance(m, int) or m < 5:
        raise ValueError("m must be an integer at least 5")
    q = m**3
    A = 2*m*(m-1)
    return mp.findroot(
        lambda s: mp.power(A, s) - 2*q - (q*(q-1)//2)*mp.power(2, s),
        (mp.mpf("2.8"), mp.mpf("3.1")))

beta(41)

References

[1]

H. Cohn, R. Kleinberg, B. Szegedy and C. Umans, Group-theoretic Algorithms for Matrix Multiplication (2005). Theorem 1.8, Section 2 and Lemma 2.1. (arXiv)

[2]

H. Gao and N. Jing, Irreducible Characters of the Generalized Symmetric Group, Journal of Lie Theory 35 (2025), 593–616. Theorem 4.1, equation (4.4). (doi)

Links

[3]

Cohn, Kleinberg, Szegedy and Umans: full text

Similar tables

Power sum of character degrees of abelian wreath products — supplies the group-algebra cost $D_{m^3,2}(s)$ that defines the construction-bound equation

Exponent of matrix multiplication complexity — records bounds on the unknown exponent itself; this table resolves the bound equation of one specified construction

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds every integer $m$ with $5\leq m\leq40$, covering the initial sizes that beat cubic cost, the region of the coarse optimum at $m=17$ reported in [1], and larger sizes. The parameter is the cyclic factor order in that published construction, not an independently sampled real input. The upper cutoff is a noncanonical practical reference boundary, independent of numeral notation; extending it would add depth within the same mechanism. The attached argument-selection note explains the extent)

How they were obtained:

The roots are enclosed by bisection with exact rational endpoints. Arb ball arithmetic certifies opposite signs of the strictly increasing equation $[m(m-1)]^s-\binom{m^3}{2}-2m^3 2^{-s}=0$ at the retained endpoints. The computation uses 96 extra working bits and 357 bisection steps; every returned ball has at least 358 bits of relative accuracy and supports the 100 significant digits stored. Uniqueness follows from (2).

Independent MPFI arithmetic at 512 bits certifies opposite signs of the original cost equation at both ends of every displayed decimal interval. Separate 150-digit mpmath secant solves lie inside all 36 intervals. The square-root-of-two controls pass before these checks. All 36 cubic and $9/4$ character moments agree with the stored companion values. Direct group multiplication verifies the triple product property at $m=2,3,4,5$, and a deliberately invalid construction gives 48 violations as a control. GAP character tables recover the degree multiplicities at $m=2,3$ after an $S_3$ control. The attached checks and numerical evidence state the scope, software versions and source provenance.