A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/7

For studying the growth in finite groups, we present a resource-efficient algorithm which is a modification of our early algorithm. The purpose of the modification is to minimize the space complexity of the algorithm and to save its time complexity at an acceptable level. The main idea of the modified algorithm is to take in the given group G a suitable subgroup N such that |N| ^ |G|, to calculate growth functions for all cosets gN independently of each other, to summarize these functions and to obtain the growth function for the group G. By using this algorithm, we calculate the growth functions for the group Big with two generators a1 and a2 and for the groups Big, B19 with four generators a1, a-1, a2 and a-1, where Bk = B0(2, 5)/(ak+1,..., a34) is a quotient of the group B0(2, 5) = (a1,a2) which is the largest two-generator Burn-side group of exponent 5 (its order is 534), a1 and a2 are generators of B0 (2, 5) and a3,..., a34 are the commutators of B0(2, 5), so each element in B0(2, 5) can be represented as a^1 -а^2 ·.. .-aOf4, a G Z5, i = 1,2,..., 34. Based on these data, we formulate a hypothesis about the diameters of Cayley graphs of the group B0(2, 5) with generating sets A2 = {а12} and A4 = {a1, a-1, a2, a-1}, namely, Da2(B0(2, 5)) w 105 and Da4(B0(2, 5)) w 69.
Download file
Counter downloads: 102
  • Title A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5
  • Headline A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 42
  • Date:
  • DOI 10.17223/20710410/42/7
Keywords
Burnside group, the Cayley graph, the growth function, функция роста, группа Бернсайда, граф Кэли
Authors
References
Кузнецов А. А. Об одном алгоритме вычисления функций роста в конечных двупорождённых группах периода 5 // Прикладная дискретная математика. 2016. №3(33). C. 116-125.
Кузнецов А. А., Кузнецова А. С. Параллельный алгоритм для исследования графов Кэли групп подстановок // Вестник СибГАУ. 2014. №1. C. 34-39.
Even S. and Goldreich O. The Minimum Length Generator Sequence is NP-Hard // J. Algorithms. 1981. No. 2. P. 311-313.
Skiena S. The Algorithm Design Manual. London: Springer Science+Business Media, 2008. 730 p.
Sims C. Fast multiplication and growth in groups // Proc. 1998 Intern. Symp. Symbolic Algebraic Computation. 1998. P. 165-170.
Havas G., Wall G., and Wamsley J. The two generator restricted Burnside group of exponent five // Bull. Austral. Math. Soc. 1974. No. 10. P. 459-470.
Sims C. Computation with Finitely Presented Groups. Cambridge: Cambridge University Press, 1994. 628 p.
Holt D., Eick B., and O'Brien E. Handbook of Computational Group Theory. Boca Raton: Chapman & Hall/CRC Press, 2005. 514 p.
Кузнецов А. А. Кузнецова А. С. Быстрое умножение элементов в конечных двупорождённых группах периода пять // Прикладная дискретная математика. 2013. № 1. C. 110-116.
 A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/7
A resource-efficient algorithm for study the growth in finite two-generator groups of exponent 5 | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2018. № 42. DOI: 10.17223/20710410/42/7
Download full-text version
Counter downloads: 538