Low-degree growth constants of finite p-group algebras

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

Numbers

$G$

$C_G$

$U_{3}(\mathbb F_{2})$:

6.871884323462463213677308993801736853130104739273362639977557690022254072431079967572869717814911035

$U_{4}(\mathbb F_{2})$:

48.09736567800296787307159818315776690357124287128719355162772937527354731768381148509422525722857290

$U_{5}(\mathbb F_{2})$:

648.0319552988921144630473918365032646538676017274491744874952891708787731783735113216041534758667945

$U_{6}(\mathbb F_{2})$:

16807.67358853206913241971181814783032390479263520450380625350316854194642801626806709207255180976222

$\operatorname{Heis}_{2}(\mathbb F_{2})$:

24.75178470343125824005484342628627315743717892516126638962910791017117561530235780471274608764635360

$\operatorname{Heis}_{3}(\mathbb F_{2})$:

88.83435156430603179379370069431973545261112160578216885726123402365329094844664556747257362667668639

$\operatorname{Heis}_{4}(\mathbb F_{2})$:

318.2817180850548733927628995101174932097180850243854031738762669696539881540476250925225533463168662

$U_{3}(\mathbb F_{3})$:

21.47947576800258584470520840670338522092640204189410656550916828878690199491355410676860602812368151

$U_{4}(\mathbb F_{3})$:

474.2311848672908300633933139992002630631173885081988469938030938206680198787954140225394926323779812

$U_{5}(\mathbb F_{3})$:

29653.78162587403270601056799020657484968312054007333523236436463807257096445689235579631359093120193

$U_{6}(\mathbb F_{3})$:

5251752.711615232854434831912866602539548581317645194839425758062900655012162796785740827151888863446

$\operatorname{Heis}_{2}(\mathbb F_{3})$:

165.0941516845182997818187010657329616404687779795009687011880238066569937801683352889615238376053582

$\operatorname{Heis}_{3}(\mathbb F_{3})$:

1262.167547071019757012100752164338041111287178163528066188878568975495396615305040255918167763320224

$\operatorname{Heis}_{4}(\mathbb F_{3})$:

9624.941369464651886484605280352809273304415559641499557923914775823808588570197843919737156664451771

$U_{3}(\mathbb F_{5})$:

92.01339538488585524963541590693885360052251493362165949824496313943736381986230486879991645938858643

$U_{4}(\mathbb F_{5})$:

8782.185149199656007382038167387329344546854656111313696519028895167974481112388277326181731289118231

$U_{5}(\mathbb F_{5})$:

3879794.378110226896476197421457741131930558527965555386737788825392515523054256950795008584776490427

$\operatorname{Heis}_{2}(\mathbb F_{5})$:

1861.898031152593555562542568459525531895722375875913532030409588070822888483006458417948937764499354

$\operatorname{Heis}_{3}(\mathbb F_{5})$:

37409.92167542695352582907303669379812802828214534505274532984972666304039728015659235784157740378717

$\operatorname{Heis}_{4}(\mathbb F_{5})$:

749146.8594225097175908178169460864019436100436169258312370112596915857358570931868683196062272882908

$U_{3}(\mathbb F_{7})$:

242.7629603088535310571037396964003641210380284015266149912659442730815663445094432714566677160509466

$U_{4}(\mathbb F_{7})$:

61409.57277868652091426598168017858182520605792056846408851333603148180458829290088253619236749466819

$\operatorname{Heis}_{2}(\mathbb F_{7})$:

9370.183189665322050020831859560473692459914111548664929538072288069932312944109024260606914613775851

$\operatorname{Heis}_{3}(\mathbb F_{7})$:

358816.1915578654634389851550357498405140279922046074285028184429197844455423080619460136621022951671

$\operatorname{Heis}_{4}(\mathbb F_{7})$:

13689229.36769076704786997922587534591468265631870659284969592830592992084718988701040667934566914958

Definition

For a nontrivial finite $p$-group $G$, write $H_G(t)$ for its augmentation Hilbert series over $\mathbb F_p$ and $d_G=\deg H_G$. Its low-degree growth constant is $C_G=\min_{0<t\leq1}H_G(t)t^{-d_G/3}$.

Parameters

$G$

— finite p-group (a nontrivial finite group of prime-power order $|G|=p^m$, with coefficients taken over the prime field $\mathbb F_p$)

Formulas

(1)

For the dimension subgroups $D_j(G)=\{g\in G:g-1\in I^j\}$, put $e_j=\log_p|D_j(G)/D_{j+1}(G)|$. Then $H_G(t)=\prod_{j\geq1}(1+t^j+\cdots+t^{(p-1)j})^{e_j}$ [1].

(2)

For $U_n(\mathbb F_p)$, $e_j=n-j$ for $1\leq j<n$, the other $e_j$ vanish, and $d_G=(p-1)n(n^2-1)/6$ [2]. For $\operatorname{Heis}_r(\mathbb F_p)$, $e_1=2r$, $e_2=1$, the other $e_j$ vanish, and $d_G=(p-1)(2r+2)$ [3].

(3)

The minimum is attained at the unique $t_G\in(0,1)$ satisfying $3t_G H_G^{\prime}(t_G)=d_G H_G(t_G)$. Thus $C_G=H_G(t_G)t_G^{-d_G/3}$ and $1<C_G< H_G(1)=|G|$.

(4)

For each integer $k\geq1$, let $L_G(k)=\sum_{j=0}^{\lfloor k d_G/3\rfloor}[t^j]H_G(t)^k$. Then $L_G(k)\leq C_G^k$, $\lim_{k\to\infty}L_G(k)^{1/k}=C_G$, and $C_{G^k}=C_G^k$.

Comments

(5)

The augmentation Hilbert series is $H_G(t)=\sum_{j\geq0}\dim_{\mathbb F_p}(I^j/I^{j+1})t^j$. Here $I$ is the kernel of the augmentation map $\mathbb F_p[G]\to\mathbb F_p$ sending each group element to $1$, and $I^0=\mathbb F_p[G]$.

(6)

The group $U_n(\mathbb F_p)$ consists of upper unitriangular $n\times n$ matrices over the prime field, with $n\geq2$ and $p$ prime [2].

(7)

The group $\operatorname{Heis}_r(\mathbb F_p)$ consists of triples $(a,b,c)$, where $a,b\in\mathbb F_p^r$, $c\in\mathbb F_p$ and $r\geq1$, with multiplication $(a,b,c)(a^{\prime},b^{\prime},c^{\prime})=(a+a^{\prime},b+b^{\prime},c+c^{\prime}+a\cdot b^{\prime})$. This law fixes the characteristic-two case as well. Our $r$ equals $n-1$ in Petrov's notation $H_{n-1}$ [3].

(8)

The rank-one Heisenberg group $\operatorname{Heis}_1(\mathbb F_p)$ is isomorphic to $U_3(\mathbb F_p)$ and is represented by that row. The rows use increasing $p$, then increasing unitriangular matrix size $n$, then increasing Heisenberg rank $r$.

(9)

The constant $C_G$ is the exponential growth rate of the dimensions in augmentation degrees at most one third of the top degree in direct powers $G^k$, as expressed in (4). The polynomial coefficients are integer dimensions over $\mathbb F_p$. The stored constant is not divided by $|G|$, and the minimizing argument is not a separate entry.

(10)

The fixed threshold $d_G/3$ comes from the weighted monomial argument [4]. In $\mathbb F_p[G^k]$, the ideal $X=I^{\lfloor k d_G/3\rfloor+1}$ satisfies $X^3=0$, and its codimension is $L_G(k)$ from (4). The displayed minimization and its direct-power growth interpretation are a specialization of the Chernoff method, rather than notation assigned by the cited papers.

(11)

These quantities belong to the group-algebra approach to bounding multiplicative matchings [2]. They are neither tensor ranks nor the exponent of matrix multiplication, and by themselves do not provide a matrix-multiplication algorithm.

Programs

(P1)

Python

import mpmath as mp
mp.mp.dps = 120
# U_3(F_2) = Heis_1(F_2); this snippet gives an approximation.
H = lambda t: (1+t)**2 * (1+t*t)
f = lambda t: 3*t*mp.diff(H, t)-4*H(t)
t_star = mp.findroot(f, (mp.mpf('0.4'), mp.mpf('0.8')))
C = H(t_star)/mp.power(t_star, mp.mpf(4)/3)
print(mp.nstr(C, 100))

References

[1]

Laurent Bartholdi and Rostislav I. Grigorchuk, Lie Methods in Growth of Groups and Groups of Finite Width, 2000, Section 2, equation (3). (arXiv)

[2]

Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow and Chris Umans, Which groups are amenable to proving exponent two for matrix multiplication?, 2017, Sections 3.1–3.2 and Example 3.15. (arXiv)

[3]

Fedor Petrov, Combinatorial results implied by many zero divisors in a group ring, 2020, Sections 6–7. (arXiv)

Links

[4]

Petrov: the group-algebra method and matrix p-groups

Similar tables

Augmentation Hilbert series of finite p-groups — holds the full polynomials $H_G(t)$ whose minima $H_G(t)t^{-d_G/3}$ give the constants in this table

Exponent of matrix multiplication complexity — records the complexity exponent that motivates the group-algebra approach; a growth constant here is not a value of that exponent

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds $U_n(\mathbb F_p)$ for primes $p\leq7$, $3\leq n\leq6$ and $(p-1)n(n^2-1)/6\leq80$, together with $\operatorname{Heis}_r(\mathbb F_p)$ for the same primes and $2\leq r\leq4$; the rank-one Heisenberg cases are the $U_3$ rows. These 25 groups cover small characteristics, varying nilpotency class and varying generator count at class two. The noncanonical prime, size, rank and degree bounds match the readable polynomial coverage of the Hilbert-series companion, allowing each constant to be traced to its full grading. The attached argument-selection note explains all bounds)

How they were obtained:

Exact integer arithmetic brackets the unique positive zero of $3tH_G^{\prime}(t)-d_G H_G(t)$; a single coefficient sign change and the endpoint signs prove that it is the minimum. Arb ball arithmetic propagates the entire root bracket through the objective, producing rigorous enclosures that justify 100 significant digits. The calculation uses 413 working bits, including 80 extra bits. Every enclosure retains at least 404 bits of relative accuracy, exceeding 119 decimal digits.

All 25 Hilbert polynomials agree exactly with the companion snapshot. A separate 180-digit mpmath computation using the individual weighted degree distributions agrees with the certified values, and a 140-digit certified computation checks precision. Known-answer controls use $H(t)=1+t$ and $H(t)=(1+t)^3$. Checks cover coefficient symmetry, degree, total dimension, the stationary equation, the entropy identity, and exact bounded-composition counts for direct powers $1\leq k\leq4$. The direct-power minimum identity is checked for $k=2,3$. The attached derivation proves the growth-rate interpretation. The independent computations and enclosure-containment checks also pass on all 25 values read back from the draft.