Minimum point of the Ellenberg–Gijswijt bound

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

Numbers

$n$

convention

$\rho_n$ or $\gamma_n$

$\rho_n$:

1/2

$\gamma_n$:

$\rho_n$:

0.5930703308172535824813264335273661647775330572478490459624846838207375901821755783783906706995985153

$\gamma_n$:

1.686140661634507164962652867054732329555066114495698091924969367641475180364351156756781341399197031

$\rho_n$:

0.6572981061383759908250555200048017116450476861892634617720335487975394573147121369680843507888479620

$\gamma_n$:

1.521379706804567569604080832254438514428389828427903909090498015428156403430588216049163792696733877

$\rho_n$:

0.7041526820481346868919866932213269634363807579128100353088456638725219402096267467457988195956889451

$\gamma_n$:

1.420146547040548928303971333427466699557026098881438679357092449900816007813141221593605223665297332

$\rho_n$:

0.7397972891178014045096634298130904749149466600779959671837359746531860691968310434163160325263870735

$\gamma_n$:

1.351721633357817418393314482567553901249872146535485076367539634365362010450536075235037130091742728

$\rho_n$:

0.7678067796924252144592440296633669584299197593999305461781073459758621976098871990040577279068812743

$\gamma_n$:

1.302411005540467857961647248400319986270344105716185137361399641644415994862062700425102516567359598

$\rho_n$:

0.7903887237079046110561087556617897438123695942954799474243342551321727431355016062867602372278802325

$\gamma_n$:

1.265200236294817327267990952475657498217961080593644828196884920757541982425889564908337689385132255

$\rho_n$:

0.8089772279052349111126698870326819820915206846547188735936047248004316255430276267103496441171877711

$\gamma_n$:

1.236128738245697380441018706683008829530161628802622266674415482131775392052149702687382485604670640

$\rho_n$:

0.8245433284854554200772683589663926817533921263244569072000089462784490824531518877014930753301261991

$\gamma_n$:

1.212792542796784702950150386555760700438333544620091484124877147808719503683093631348405297816930200

$\rho_n$:

0.8377674796860114619731178419845721665495799759435053253795311126518275392247890281387321625119802220

$\gamma_n$:

1.193648624764943115967861313477747494676320512067210175633730164982140403245199934490336361077156937

$\rho_n$:

0.8491404716364564035320876069866256188534655367164366189759353042420294558043833190524196108753500047

$\gamma_n$:

1.177661451082184761708116919838959144623167477287051110862334825647200126370868040342688078554207986

$\rho_n$:

0.8590251016676569875917864047512332242346299133879335065774129658511854479527254097887696603686306166

$\gamma_n$:

1.164110336308756593173910293719361556806568959358868999881424371313208760182592692493961871932817145

$\rho_n$:

0.8676952886855291641606701235137989224144785284050510527947620977071930495732152811031104148724031166

$\gamma_n$:

1.152478310116099774593691865420006714289164456326386487864670280913873569106316586874400564615003341

$\rho_n$:

0.8753616884405092691954867943924196776941357234044416393313220820431294079378956203410653839023986726

$\gamma_n$:

1.142384928659076578110934938125318919300732775854132783386888820415892980886523677742201398441656192

$\rho_n$:

0.8821889424291327650368617151707255683923484243508026821790571891562174359495747255528311792335108988

$\gamma_n$:

1.133544019772534306493283278092648571689698615923708918703637194824409037436119482502431513242415623

$\rho_n$:

0.8883075804350725732623409510538278328272701634391913351504280065243892297303594413020311533347085663

$\gamma_n$:

1.125736199966033223161518792466933087447472108058760704577749572696449218136877170627779775179942187

$\rho_n$:

0.8938224132607180960297403242369392938952700432520690492381411248110233603088312890618393817890260458

$\gamma_n$:

1.118790472429461307513640477704291455979964589594970540744436129877821386885704516919440397689271356

$\rho_n$:

0.8988185655745158867245524033817432245308652635489870001674462440821240405166643177568082126685156910

$\gamma_n$:

1.112571589307136693181972512580130385479267940891209996463747167807213672989436861437104745901908596

$\rho_n$:

0.9033658878176048386063893060216821582136635005717500152078881767555224391385012710238608576719579260

$\gamma_n$:

1.106971176890294740094260102952581132852852752089120743900551037008266547166426551512163736294358559

$\rho_n$:

0.9075222331817433690880646928165524196267516179483492631553556756712865541690740864728945452534601804

$\gamma_n$:

1.101901378761854235499525173747009044798466440514781339803492958564492381321178780317711670180807934

$\rho_n$:

0.9113359260736960705719758530043870231947725283126087300436840224843758233977339028255486913333424914

$\gamma_n$:

1.097290221299949084211939594897600932312770273754821041969602548000383084712702440228103937546396144

$\rho_n$:

0.9148476454835643517927033228381697845715114342843201934030021274988378932997585634118048447005028870

$\gamma_n$:

1.093078180762466036692755239911905990119407388920224390133773627109422652934098960475681823787049246

$\rho_n$:

0.9180918788322840213271288784647203001707923531438549704659134991243776708967783779963210675857683545

$\gamma_n$:

1.089215603640775544808380508495398294541680944092081148481593147059913620336719256682598122135988913

$\rho_n$:

0.9210980563483186102865772378571343039484558776060130819750295914042605136201427952289201270487501850

$\gamma_n$:

1.085660742749243364859398113520118634643524356138145290051465118356414020156138628203907747861019371

$\rho_n$:

0.9238914449499613678152108679361422946817367989556164141605428349087597485520722409924146766973354641

$\gamma_n$:

1.082378244182313785626033886193978129549789862322153460053234647521357221193288659028777634499598723

$\rho_n$:

0.9264938590662340304322021972135981661621586308379611570345841475685268074461284501603373864065628783

$\gamma_n$:

1.079337968853726742428749282897868691218557122082829100972639751719301203541699256583175347550995350

$\rho_n$:

0.9289242306767918704358217568141574391843087002374174040631052249169579192795402221149412812459102341

$\gamma_n$:

1.076514065384454480359484790375876313435507625874404673358372148075238589948420115245160227341231034

$\rho_n$:

0.9311990700509964580294839759662035168931035551555676243712451047417797397554389875571215897644594534

$\gamma_n$:

1.073884233953579558165432584858558488142565959465698692531304961830037839273094458930959016574092384

$\rho_n$:

0.9333328408727790912005539024626112472824637788580907389740812851760574145824509128522008719268986008

$\gamma_n$:

1.071429136753485553705041486344382675109321924600516261357311096775474639384251971077609021196990601

$\rho_n$:

0.9353382677492268250246572509779329916027577107607348017371023147303128157645441773952591342280241656

$\gamma_n$:

1.069131922086726389098386753720500528442569800186675982862012902988237000209467033998748701455199903

$\rho_n$:

0.9372265899039274634998542871296030461240703975919837523603234830012608824023999098767701473973576990

$\gamma_n$:

1.066977837347217461279440530091593095174206517112928235207710723287718338928957059575154180317447951

Definition

For an integer $n\geq2$, let $S_n(t)=\sum_{j=0}^{n-1}t^j$ and $F_n(t)=S_n(t)t^{-(n-1)/3}$ for $t>0$, with positive real powers [1]. This table records the unique minimizing argument $\rho_n=\operatorname*{argmin}_{t>0}F_n(t)$ in two invertible conventions, $\rho_n$ and $\gamma_n=1/\rho_n$.

Parameters

$n$

— algebra dimension ($n\geq2$)

convention

— minimizing-argument convention

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)

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

(3)

The Ellenberg–Gijswijt constant satisfies $C_n=S_n(\rho_n)\rho_n^{-(n-1)/3}=\frac{\gamma_n^n-1}{\gamma_n-1}\gamma_n^{-2(n-1)/3}$.

(4)

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

(5)

$\rho_2=1/2$, $\gamma_2=2$, $\rho_3=(\sqrt{33}-1)/8$ and $\gamma_3=(\sqrt{33}+1)/4$. The dimension-three values are also the positive root of $4t^2+t-2$ and the positive root of $2t^2-t-4$, respectively.

Comments

(6)

The minimum occurs at $0<\rho_n<1$. To see uniqueness, put $t=e^s$: the second derivative of $\log F_n(e^s)$ is the strictly positive variance of $j$ under probabilities proportional to $e^{js}$. Its first derivative changes from negative to positive before $s=0$, and $F_n(t)$ tends to infinity at both endpoints of $t>0$.

(7)

[1] uses $q$ for the dimension and $\rho$ for the minimizing argument. [2], Section 4.2.1, uses the reciprocal $\gamma_n>1$. These are one number in two invertible conventions. Dimension one is excluded because $F_1$ is constant and has no unique minimizer.

(8)

The dimension $n$ belongs to the algebra $A_n=\mathbb C[u]/(u^n)$, where $u$ is the polynomial variable. In monomial bases its multiplication tensor has support $i+j=k$; reversing the output index gives $i+j+k=n-1$, with $0\leq i,j,k<n$ [2]. Its asymptotic subrank is the minimum value $C_n=F_n(\rho_n)$, so this family also includes dimensions that are not prime powers.

(9)

The minimizing argument determines a probability law on $\{0,\ldots,n-1\}$ with mean $(n-1)/3$. This law maximizes Shannon entropy among probability distributions on that support with that mean [3], Remark 6. At $n=2$ it is Bernoulli$(1/3)$, whose entropy in nats equals $\log C_2$.

(10)

The dimension-three entry is the minimizing argument in the Ellenberg–Gijswijt cap-set upper bound [1]. It is distinct from the upper-bound constant $C_3$.

Programs

(P1)

Python

from mpmath import mp
mp.dps = 110

def minimum_point(n):
    # n is an integer at least two; returns approximate rho_n and gamma_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)
    return rho, 1/rho

print(minimum_point(3))

References

[1]

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)

[2]

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

Links

[3]

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

Similar tables

Ellenberg–Gijswijt constants and reduced polynomial multiplication subrank — the minimum values $C_n=F_n(\rho_n)$ and their per-dimension normalizations

Shannon entropies of discrete probability distributions — the law determined by $\rho_2=1/2$ is Bernoulli$(1/3)$, with entropy $\log C_2$ in nats

Algebraic numbers of degree 2 — the two dimension-three values are quadratic algebraic numbers indexed there by their defining polynomials

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds every algebra dimension $2\leq n\leq32$, in both conventions $\rho_n$ and $\gamma_n$; the noncanonical cutoff covers initial discrete-family examples, 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 converts this entire enclosure to a ball and propagates it through the reciprocal, using 96 extra working bits and 24 further bisection steps. The computed balls retain at least 424 bits of relative accuracy, and their full enclosures fit inside every stored 100-significant-digit decimal interval. The two dimension-two values are exact rationals; rational-root tests exclude other rational optimizers in the covered range.

An independent check solves the reciprocal equation in (2) by exact rational signs at 480 bisection steps and evaluates related quantities in 560-bit ball arithmetic. Controls use the exact dimension-two values, a known nonzero Bernoulli entropy and the dimension-three radicals. The checks cover every displayed interval, both conventions, the probability normalization and mean, entropy, the companion constants, the stored Bernoulli$(1/3)$ entropies and both quadratic values. They are repeated on entries read from the database. The attached generator, checks and numerical evidence reproduce the certification; the Programs snippet gives ordinary floating-point approximations.