An algorithm for computation of the growth functions in finite two-generated groups of exponent~$5$

A. A. Kuznetsov

Prikladnaâ diskretnaâ matematika, no. 3 (2016), pp. 116-125.

Résumé

Let $B_0(2,5)=\langle a_1,a_2\rangle$ be the largest $2$-generator Burnside group of exponent $5$. It has the order $5^{34}$. There is a power commutator representation of $B_0(2,5)$. In this case, every element of the group can be uniquely represented as $a_1^{\alpha_1}\cdot a_2^{\alpha_2}\cdot\dots\cdot a_{34}^{\alpha_{34}}$, where $\alpha_i \in\mathbb Z_5$, $a_i\in B_0(2,5)$, $i=1,2,\dots,34$. Here, $a_1$ and $a_2$ are generators of $B_0(2,5)$, commutators $a_3,\dots,a_{34}$ are recursively defined by $a_1$ and $a_2$. We define $B_k=B_0(2,5)/\langle a_{k+1},\dots,a_{34}\rangle$ as a quotient of $B_0(2,5)$. It is clearly that $|B_k|=5^k$. A new algorithm for computing the growth function of $B_k$ is created. Using this algorithm, we calculated the growth functions of $B_k$ relative to generating sets $\{a_1,a_2\}$ and $\{a_1,a_1^{-1},a_2,a_2^{-1}\}$ for $k=15,16,17$.

Détail

Keywords: Burnside group, the growth function.

Bibliographie

[1] Even S., Goldreich O., “The Minimum Length Generator Sequence is NP-hard”, J. Algorithms, 1981, no. 2, 311–313 | DOI | MR | Zbl

[2] Kuznetsov A. A., Kuznetsova A. S., “A parallel algorithm for study of the Cayley graphs of permutetion groups”, Vestnik SibGAU, 2014, no. 1, 34–39 (in Russian)

[3] Holt D., Eick B., O'Brien E., Handbook of Computational Group Theory, Chapman Hall/CRC Press, Boca Raton, 2005, 514 pp. | MR | Zbl

[4] Camelo M., Papadimitriou D., Fàbrega L., Vilà P., “Efficient routing in data center with underlying Cayley graph”, Proc. 5th Workshop on Complex Networks CompleNet, 2014, 189–197

[5] Kuznetsov A. A., “The Cayley graphs of Burnside groups of exponent 3”, Siberian Electronic Math. Reports, 12 (2015), 248–254 (in Russian) | DOI | Zbl

[6] Havas G., Wall G., Wamsley J., “The two generator restricted Burnside group of exponent five”, Bull. Austral. Math. Soc., 10 (1974), 459–470 | DOI | MR | Zbl

[7] Sims C., “Fast multiplication and growth in groups”, Proc. 1998 Intern. Symp. Symbolic Algebraic Computation, 1998, 165–170 | DOI | Zbl

[8] Filippov K.A., “About Cayley diameter of one subgroup of the group $B_0(2,5)$”, Vestnik SibGAU, 2012, no. 1, 234–236 (in Russian)

[9] Sims C., Computation with Finitely Presented Groups, Cambridge University Press, Cambridge, 1994, 628 pp. | MR | Zbl

[10] Skiena C., Algorithms, Guide for the Development, BKhV-Petersburg Publ., SPb., 2014 (in Russian)

[11] Hall P., Nilpotent Groups, Notes of Lectures Given at the Canadian Mathematical Congress Summer Seminar, University of Alberta, 12–30 August, 1957, Queen Mary College, London, 1969 | Zbl

[12] Kuznetsov A. A. and Kuznetsova A. S., “Fast multiplication in finite two-generated groups of exponent five”, Prikladnaya Diskretnaya Matematika, 2013, no. 1, 110–116 (in Russian)