Ellenberg–Gijswijt constants and reduced polynomial multiplication subrank

edit · history · discussion · files · long url · combinatorics matrix multiplication probability theory algebraic

Numbers

$n$

convention

$C_n$ or $J_n$

$C_n$:

1.889881574842309747150815910917342525855377197052261970122962668232949514770939225594094843654382641

comment: $C_2=3/2^{2/3}$.

$J_n$:

0.9449407874211548735754079554586712629276885985261309850614813341164747573854696127970474218271913206

$C_n$:

2.755104613023633000221276546533686195215875426463525346966602966549772951682590920914659277193121590

comment: $C_3=3(207+33\sqrt{33})^{1/3}/8$, the Ellenberg–Gijswijt cap-set bound constant.

$J_n$:

0.9183682043412110000737588488445620650719584754878417823222009888499243172275303069715530923977071966

$C_n$:

3.610718613276039349818649008384058627465108585736487594521763797541004333803238392557787864439524797

$J_n$:

0.9026796533190098374546622520960146568662771464341218986304409493852510834508095981394469661098811992

$C_n$:

4.461577765702577811408482138847640902979038718830487539627830294377659695061061129776653571703950814

$J_n$:

0.8923155531405155622816964277695281805958077437660975079255660588755319390122122259553307143407901627

$C_n$:

5.309733691992887434079430917281284936777938870724665841044453717011714779443904674640405290134560121

$J_n$:

0.8849556153321479056799051528802141561296564784541109735074089528352857965739841124400675483557600201

$C_n$:

6.156204863216738416428644990546841466205405827877607890833949757640918167951839114712714136737641693

$J_n$:

0.8794578376023912023469492843638344951722008325539439844048499653772740239931198735303877338196630989

$C_n$:

7.001554754994007458132247312391453137141290881157766454749461036481561012867577096104981057552070506

$J_n$:

0.8751943443742509322665309140489316421426613601447208068436826295601951266084471370131226321940088133

$C_n$:

7.846120582585805712506584327561245930739237581122945647224305075381835216767871975241730536025075227

$J_n$:

0.8717911758428673013896204808401384367488041756803272941360338972646483574186524416935256151138972474

$C_n$:

8.690116576079060742512191146179986370489966791408626749378432954976619322294976657073741082167696860

$J_n$:

0.8690116576079060742512191146179986370489966791408626749378432954976619322294976657073741082167696860

$C_n$:

9.533685392075550992755846001437429533000441168129705770711056798670868646722037248646914834885199425

$J_n$:

0.8666986720068682720687132728579481393636764698299732518828233453337153315201852044224468031713817659

$C_n$:

10.37692571383077301850362406851000710961443989210820240544576157182148984724075471987786670176772057

$J_n$:

0.8647438094858977515419686723758339258012033243423502004538134643184574872700628933231555584806433807

$C_n$:

11.21990798911487743710354307874670920930982759503582714727794423690869844896843629953620629955309443

$J_n$:

0.8630698453165290336233494675959007084084482765412174728675341720698998806898797153489389461194688026

$C_n$:

12.06268385820579756828775421588276014198350979438614085264675059291178555163784091335839108038999082

$J_n$:

0.8616202755861283977348395868487685815702506995990100609033393280651275394027029223827422200278564871

$C_n$:

12.90529203952007762721414126333438408781414939841586356417309178499764130062054364638911409848959750

$J_n$:

0.8603528026346718418142760842222922725209432932277242376115394523331760867080362430926076065659731670

$C_n$:

13.74776213458745700186503241050408124151866114254620165836689659630678989079172897423301581823712276

$J_n$:

0.8592351334117160626165645256565050775949163214091376036479310372691743681744830608895634886398201728

$C_n$:

14.59011716296566909733292591731068890488059646602334509949288407205741169587924818121697097503086644

$J_n$:

0.8582421860568040645489956421947464061694468509425497117348755336504359821105440106598218220606392023

$C_n$:

15.43237529572923798881424954244460875402418502986858508803204463485251409737780889315196312489555855

$J_n$:

0.8573541830960687771563471968024782641124547238815880604462247019362507831876560496195535069386421414

$C_n$:

16.27455106840026451533064402457870391069290751031910411756140381861415131049867918607719897511494822

$J_n$:

0.8565553193894876060700338960304581005627846058062686377663896746639027005525620624251157355323656959

$C_n$:

17.11665624703724042829551717949306777389361168601931976597618934535962137119928084196259224686677456

$J_n$:

0.8558328123518620214147758589746533886946805843009659882988094672679810685599640420981296123433387280

$C_n$:

17.95870045794891806136794450939831377329526291481132176088567675361394531841181870723289312783950346

$J_n$:

0.8551762122832818124460925956856339892045363292767296076612227025530450151624675574872806251352144507

$C_n$:

18.80069165303463167721060272905695539603183725508351238525688361521033029686341853313376516276830275

$J_n$:

0.8545768933197559853277546695025888816378107843219778356934947097822877407665190242333529619440137613

$C_n$:

19.64263645872880846855649800712949925601009365863221995640860762065059998041396218852527810849562218

$J_n$:

0.8540276721186438464589781742230217067830475503753139111482003313326347817571287908054468742824183558

$C_n$:

20.48454044116147916198302272902931448786773868803798105025698410265236202894410366572002373229252964

$J_n$:

0.8535225183817282984159592803762214369944891120015825437607076709438484178726709860716676555121887350

$C_n$:

21.32640831010467458504116449092661287095567773974091854382443599636089285940597636870884468445937400

$J_n$:

0.8530563324041869834016465796370645148382271095896367417529774398544357143762390547483537873783749601

$C_n$:

22.16824407758279487232843479623049345778481218956449371893402295889287332733816062681686995351983639

$J_n$:

0.8526247722147228797049397998550189791455696995986343738051547291881874356668523318006488443661475534

$C_n$:

23.01005118248578718050749133276735336886865749162501965933234483724538751301841478529232026432678195

$J_n$:

0.8522241178698439696484256049173093840321724996898155429382349939720513893710523994552711209009919242

$C_n$:

23.85183258939439353356728987303321698456760495377874749242228700041568144144431652101718856841138329

$J_n$:

0.8518511639069426261988317811797577494488430340635266961579388214434171943372970186077567345861208319

$C_n$:

24.69359086763659075194245991317129618483238935199885216576996831118702789745328151457429727831708527

$J_n$:

0.8515031333667789914462917211438377994769789431723742126127575279719664792225269487784240440798994921

$C_n$:

25.53532825504039261744849575048727122217582857276215913827088218567631002329337560637915370305724100

$J_n$:

0.8511776085013464205816165250162423740725276190920719712756960728558770007764458535459717901019080334

$C_n$:

26.37704670973149142375844507925916831824336087590794973275658160686783154332697299621400680881170544

$J_n$:

0.8508724745074674652825304864277151070401084153518693462179542453828332755911926772972260260907001753

$C_n$:

27.21874795251220672602238447846984018710029446168994811491047518123368074217463998660274975009528365

$J_n$:

0.8505858735160064601881995149521825058468842019278108785909523494135525231929574995813359296904776139

Definition

For an integer $n\geq2$, set $S_n(t)=\sum_{j=0}^{n-1}t^j$ and $C_n=\min_{t>0}S_n(t)t^{-(n-1)/3}$, with positive real powers [2]. The Ellenberg–Gijswijt constant $C_n$ is recorded as one number in two invertible conventions: $C_n$ and $J_n=C_n/n$ [3].

Parameters

$n$

— algebra dimension ($n\geq2$)

convention

— normalization

Formulas

(1)

$P_n(t)=3tS_n^{\prime}(t)-(n-1)S_n(t)=\sum_{j=0}^{n-1}(3j-n+1)t^j$, and $P_n(\rho_n)=0$. The root $\rho_n$ is the unique positive root of $P_n$.

(2)

$C_n=F_n(\rho_n)=nJ_n$.

(3)

For $\gamma_n=1/\rho_n>1$, $\frac{1}{\gamma_n-1}-\frac{n}{\gamma_n^n-1}=\frac{n-1}{3}$ and $C_n=\frac{\gamma_n^n-1}{\gamma_n-1}\gamma_n^{-2(n-1)/3}$ [1], equation (31).

(4)

For $p_j=\rho_n^j/S_n(\rho_n)$, $0\leq j<n$, one has $\sum_j j p_j=(n-1)/3$ and $\log C_n=-\sum_j p_j\log p_j$, using natural logarithms [4], Lemma 5.

(5)

$C_2=3/2^{2/3}$ and $C_3=3(207+33\sqrt{33})^{1/3}/8$ [1]. In particular, $\log C_2$ is the entropy in nats of Bernoulli$(1/3)$.

Comments

(6)

Let $A_n=\mathbb C[u]/(u^n)$, where $u$ is the polynomial variable, and let $M_n$ be its multiplication tensor. In monomial bases its nonzero coefficients occur at $i+j=k$; reversing the output index gives $i+j+k=n-1$, with $0\leq i,j,k<n$. The asymptotic subrank of $M_n$ equals $C_n$, denoted $z(n)$ in [1], Section 4.2.1.

(7)

For a tensor $T$, its subrank $Q(T)$ is the largest integer $r$ such that independent linear maps on its three legs send $T$ to the diagonal tensor $\sum_{a=1}^r e_a\otimes e_a\otimes e_a$. The asymptotic subrank is $\widetilde Q(T)=\lim_{m\to\infty}Q(T^{\otimes m})^{1/m}$; thus $C_n=\widetilde Q(M_n)$, with the restriction convention of [1].

(8)

Write $F_n(t)=S_n(t)t^{-(n-1)/3}$. Its unique minimizing argument $\rho_n$ lies in $(0,1)$. Indeed, the second derivative of $\log F_n(e^s)$ is the positive variance of $j$ under probabilities proportional to $e^{js}$, and its first derivative changes sign before $s=0$. The objective diverges as $t$ tends to either endpoint of $(0,\infty)$.

(9)

The normalization $J_n$ is $J(n)$ in [3], equation (4.10); multiplying it by the known dimension $n$ recovers $C_n$. [2] writes $\theta=C_n$ and uses $q$ for the algebra dimension. The tensor-power length is written $m$ here.

(10)

For prime-power $n$, a tri-colored sum-free set in $(\mathbb Z/n\mathbb Z)^m$ has size at most $3C_n^m$ [3], Theorem 4.14. Such a set consists of triples $(a_i,b_i,c_i)$ for which $a_i+b_j+c_k=0$ holds exactly when $i=j=k$. The algebraic definition of $C_n$ also applies to dimensions that are not prime powers.

(11)

The dimension-three entry is the Ellenberg–Gijswijt upper-bound constant for cap sets, subsets of $(\mathbb Z/3\mathbb Z)^m$ with no nonconstant three-term arithmetic progression [1], Section 4.2. This upper-bound constant is not asserted to be the exact growth rate of cap sets.

(12)

The sum-free bounds obstruct particular group-theoretic constructions seeking the matrix-multiplication exponent $\omega=2$ [3]. They do not identify $C_n$ with $\omega$.

Programs

(P1)

Python

from mpmath import mp
mp.dps = 110

def ellenberg_gijswijt(n):
    # n is an integer at least two; returns approximate C_n and J_n.
    stationary = lambda t: sum((3*j-n+1)*t**j for j in range(n))
    rho = mp.findroot(stationary, (mp.mpf(0), mp.mpf(1)),
                      solver="bisect", tol=mp.mpf("1e-105"), maxsteps=400)
    c = sum(rho**j for j in range(n)) * rho**(-mp.mpf(n-1)/3)
    return c, c/n

print(ellenberg_gijswijt(3))

References

[1]

Matthias Christandl, Péter Vrana and Jeroen Zuiddam, Universal points in the asymptotic spectrum of tensors, version 3 (2018), Section 4.2.1, equations (30)–(31). (arXiv) https://arxiv.org/html/1709.07851v3#S4.SS2.SSS1

[2]

Robert Kleinberg, Will Sawin and David E. Speyer, The growth rate of tri-colored sum-free sets, Discrete Analysis 2018:12, introduction and Section 3. (arXiv) (doi)

[3]

Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Eric Naslund, William F. Sawin and Chris Umans, On Cap Sets and the Group-theoretic Approach to Matrix Multiplication, Discrete Analysis 2017:3, equation (4.10) and Theorem 4.14. (arXiv) (doi)

Links

[4]

Kleinberg–Sawin–Speyer: the entropy characterization (Section 3)

Similar tables

Shannon_entropies_of_discrete_probability_distributions — the Bernoulli$(1/3)$ entropy in nats is $\log C_2$

Matrix_multiplication_complexity — sum-free bounds constrain particular group-theoretic approaches to the matrix-multiplication exponent

Minimum point of the Ellenberg–Gijswijt bound — the unique minimizing arguments $0<\rho_n<1$ and their reciprocals $\gamma_n=1/\rho_n$ determine the constants here through $C_n=S_n(\rho_n)\rho_n^{-(n-1)/3}$

Data properties

Entries are of type: real number

digits: 100 (Unknown key)

How well the digits are known: proven

Table is complete: no (it holds every algebra dimension $2\leq n\leq32$, in both normalizations $C_n$ and $J_n$; the noncanonical cutoff gives initial discrete-family reference coverage, including non-prime-power dimensions, while keeping the stationary polynomials at degree at most 31)

How they were obtained:

Exact rational sign bisection encloses the unique positive root of $P_n$. Arb evaluates the positive-real objective over this entire enclosure, with 128 extra working bits and 32 further bisection bits. The computed enclosures retain at least 454 bits of relative precision; every stored 100-significant-digit decimal interval contains the full computed enclosure.

An independent check isolates $\gamma_n$ through the rational equation in (3) at 520 bisection steps and evaluates both that formula and the entropy in (4) at 560 bits. Both independent enclosures fit inside every displayed interval. Exact polynomial identities, both normalizations, the closed forms at $n=2,3$, the source’s rounded values at $n=2,\ldots,10$, and the stored Bernoulli$(1/3)$ entropies in T339 were checked. The attached generator, checks and numerical evidence reproduce these tests. The Programs snippet supplies an ordinary floating-point approximation, separate from the certified generator.