THE CAYLEY GRAPHS OF FINITE TWO-GENERATOR BURNSIDE GROUPS OF EXPONENT 7

Толық мәтін

Introduction. The definition of the Cayley graph was given by the famous English mathematician Arthur Cayley in the XIX century to represent algebraic group defined by a fixed set of generating elements. During the last decades the Cayley graph theory has been developing as a separate big branch of the graph theory. The Cayley graphs are used both in mathematics and outside it. In particular, the Cayley graphs were used in information technology after the pioneering work of 1986 by S. Akers and B. Krishnamurti [1] who first pro- posed the use of these graphs to represent computer net- works, including for topology modeling (i.e. methods of connecting processors to each other) multiprocessor computer systems (MCS) - supercomputersSince then, this direction is actively developing [2-11]. This is due to the fact that the Cayley graphs have many attractive prop- erties, of which we distinguish their regularity, vertex transitivity, small diameter and degree with a sufficiently large number of vertices in the graph. Note that such basic network topologies as ”ring”, ”hypercube” and ”torus” are the Cayley graphs. Let’s recall the definitions of the main terms used in the work. Let X be a generating set of the group G, i. е. rather complicated problem. This is due to the fact that, in general, the task of the determination of the minimal word of a group element, as shown by S. Iven and O. Gol- dreich [13], is NP-hard (nondeterministic polynomial). Thus, in the worst case, the number of elementary opera- tions that must be performed to solve this problem is an exponential function of |X|. Ih the case of large number of vertices in the Cayley graphs we need use MCS. One of the widely used topologies of MCS is the k-dimensional hypercube. This graph is determined by the k-generated Burnside group of exponent 2. This group has a simple structure and is equal to the direct product of k copies of a cyclic group of order 2. Generalization of a hypercube is the n-dimensional torus which is generated by direct product of n cyclic subgroups wich may have different orders. In the articles [14-16] Cayley graphs of Burnside group of exponent 3, 4 and 5 are studied. In this paper will research the Cayley graphs of some finite two-generated Burnside groups of exponent 7. We will use the algorithm from [16] to study the graphs. Since the orders of given groups are rather big we will apply MCS. Cayley graphs study algorithm. Suppose B = a , a is a finite two-generated Burnside groups of G = X . The Cayley graph G = Cay (G, X ) = (V , E ) k 1 2 is a named orgraph with the following properties: a) a set of vertices V(G) correspond to the elements of G group, b) a set of edges E(Г) consist of all ordered pairs exponent 7 where a1 and a2 - generating elements and k | Bk |= 7 . Using the computer algebra system GAP, it is easy to obtain pc-presentation (power commutator presen- tation) of this group [17]. In this case: (g, xg), where g Î G и x Î X . "g Î B Þ g = ax1 ax2 ¼axk , x Î Z . k 1 2 k i 7 Hence, Suppose ax1 ¼axk and ay1 ¼ayk are two random ele- Г = Cay(G, X ) = (V , E) , 1 k 1 k ments of Bk written in commutator form. Then their where V = G and E = {(g, xg) g Î G, x Î X } . product is equal to ax ¼ax × ay ¼ay = az ¼az . 1 k 1 1 k 1 k 1 k k 1 k A number of vertices | V | is equal to the order of G. The Cayley graph is directed, and its degree s, i.е. the number of edges, going out of each vertice, is equal to the number of generating elements of the group: s =| X | . The basis for finding coefficients is a collection proc- ess (see [17, 18]) which is realized in computer algebra systems of GAP and MAGMA. Besides, there is an alter- native method for product computation of group elements We call the ball Ks of radius s of a group G the set of offered by F. Hall ([19]). Hall showed that zi represents all its elements, which can be presented as a group of words with length s in the alphabet X. For each nonnega- tive integer s, one can define the growth function of the group F(s), which is equal to the number of elements of the group G with respect to X, that can be represented as an irreducible group words with the length s. Thus, F (0) =| K0 |= 1, F (s) =| Ks | - | Ks-1 |, s Î N . As a rule, the growth function of a finite group is rep- resented in the form of a table which contains non-zero values of F(s). Also, we note that, along with computing the growth function of a group, we define some characteristics of the corresponding Cayley graph, for instance, the diameter and the average diameter [12]. Let F (s ) > 0 , but polynomial functions (in our case over the field ℤ7 ) de- pending on variables x1, ¼, xi , y1, ¼, yi which are now accepted to be called Hall's polynomials. According to [19]: zi = xi + yi + pi (x1, ¼, xi-1, y1, ¼, yi-1 ). In the work [20] were calculated Hall’s polynomials of Bk groups which allow to make product of group’s ele- ments much quicker than via collection. On their basis we shall calculate the important special cases of polynomials necessary for further computation of Cayley graphs of B14 group and its factors. 1 1 2 14 1 2 14 1) a × ay1 ay2 ¼ay14 = ay1 +1ay2 ¼ay14 ; 0 2) a-1 × ay1 ay2 ¼ay14 = ay1 +6ay2 ¼ay14 ; F (s0 +1) = 0 , then s0 will be the diameter of the Cayley 1 1 2 14 1 2 14 3) a × ay1 ay2 ¼ayn = az1 az2 ¼azn , where: graph of the group G in the generating alphabet X, which we will denote DX(G). Accordingly, the average diameter 2 1 2 z1 = y1, n 1 2 n DX (G ) is equal to the average length of minimal (irrez2 = y2 +1, ducible) group words. Unfortunately, although the computation of the growth function of a large finite group is solvable, it is a z3 = y1 + y3 , 4 1 4 1 z = 3y + y + 4 y2, z5 = y5 + y1 y2 , 7. if F (s) > 0 , transition to 2; otherwise s0 = s -1 , z = 5 y + y + 3y2 + 6 y3, transition to 8; 6 1 6 1 1 1 s0 z = y + 3y y + 4 y2 y , 8. D (G) = s , D (G ) = å F (s )× s ; 7 7 1 2 1 2 X 0 X z = y + 3y y + 4 y y2, s=0 8 8 1 2 1 2 9. Exit. z = 5 y + y + 6 y2 + 5 y3 + 5 y4, 9 1 9 1 1 1 z = 2 y + y + 5 y y + 4 y y + 3y2 y + 3y2 y + In [16] is proved the correctness of algorithm A-I and 10 1 10 1 2 1 3 1 2 1 3 + 6 y3 y + 4 y2 + y3, also shown that T (| G |) ÎQ(| G |2 ) under | X |≪| G | , 1 2 1 1 where T (| G |) is computational complexity of the algoz = 5 y + y + 3y y + 4 y2 y + 3y2 + 6 y3, 11 1 11 1 3 1 3 1 1 z = y + 2 y2 y2 + 6 y y + 5 y y2 + y2 y + 6 y y y , rithm A-I and Q is simultaneously upper and lower complexity asymptotical estimate. 12 12 1 2 1 2 1 2 1 2 1 2 3 13 13 1 2 1 2 1 2 3 z = y + 3y y + 4 y2 y + y y y , To lower the complexity a method for enumeration of elements is required. Suppose ax1 ¼axk - random elez = y + 5 y y + 3y y2 + 6 y y3; 1 k 14 14 1 2 1 2 1 2 4) a-1 × ay1 ay2 ¼ayn = az1 az2 ¼azn , where: ment from Bk. We shall define bijective mapping φ as follows: 2 1 2 z1 = y1, n 1 2 n j(g) = (xk xk -1 ¼ x1 )7 , z = y + 6, j-1 ((x x ¼x ) ) = ax1 ax2 ¼axk = g. 2 2 k k -1 1 7 1 2 k z3 = 6 y1 + y3 , Here j(g ) is an integer nonnegative number written z = 4 y + y + 3y2, in the sevenfold form, which we shall take as an ordinal 4 1 4 1 z = y + y + 6 y y , number g. It is clear that j(g ) runs over values from 0 5 1 5 1 2 z = 2 y + y + 4 y2 + y3, to (7k -1) . 6 1 6 1 1 7 1 7 1 2 1 2 1 z = 3y + y + 4 y y + 3y2 y + 4 y2, We modify A-I algorithm as follows. We shall add a Boolean vector of V of size 7k to step 1, all elements of z = 6 y + y + 5 y y + 3y y2, which originally are equal to 0. For convenience the in- 8 1 8 1 2 1 2 z = 2 y + y + y2 + 2 y3 + 2 y4, dexing of elements of V begins with 0. As K0 = {e} and 9 1 9 1 1 1 10 1 10 1 2 1 3 1 2 z = 3y + y + 2 y y + 3y y + 4 y2 y + + 4 y2 y + y3 y + 3y2 + y3, j(e) = 0 therefore V0 = 1 . Let’s replace the step 4.2 of the algorithm A-I as fol- lows: 1 3 1 2 1 1 z = 2 y + y + 4 y y + 3y2 y + 5 y3, 4.2. if Vj( g ) = 0 , Vj( g ) = 1 и Ks = Ks È{g}. 11 1 11 1 3 1 3 1 z = y + y + 5 y2 y2 + 4 y y + 6 y y + As the complexity of the procedure of the group 12 1 12 1 2 1 2 1 3 + 2 y y2 + 2 y2 y + y y y , element transfer to a number and back is equal to Q(1) , 1 2 1 2 1 2 3 13 1 13 1 2 1 3 1 2 1 1 2 3 z = 3y + y + 4 y y + y y + 4 y2 y + 3y2 + 6 y y y , 14 1 14 1 2 1 2 1 2 z = y + y + 4 y y + y y2 + y y3. Further the basic algorithm for computation of the Cayley graph of a finite group is provided [16]. Algorithm A-I Input: a finite group G = X , ○ where X = {x1, x2,..., xm} is the generating set of G. Output: the diameter DX (G) , the average diameter DX (G ) of the Cayley graph G = Cay(G, X ) , and also growth function F(s) of the group G where 0 £ s £ DX (G) : 1. s = 0, K0 = {e} , F (0) = 1 , P = K0 ; 2. s = s +1 ; 3. Ks = Ks-1 ; according to [16] complexity of the modified algorithm A-I will be equal to Q(| G |) . Also, we shall note that in the step 4.1 all elements g are calculated independently of each other, therefore this section of the algorithm can be easily parallelized. In this case at first all products g are calculated simultaneously, then for every element do step 4.2 consequentially. Note that in step 4.1 products of group elements are calculated using Holl’s polynomials as suggested above. The study of graphs Bk. The modified algorithm A-I was implemented in C++. As a tool for parallelization, it was used the library OpenMP. For the calculations, it was used a computer with an 64-core processor and 512 Gb of RAM, running the Linux operating system. The program was compiled by the embedded compiler GCC. As the result characteristics of the Cayley graph of Bk were calculated under k £ 14 for minimal a1, a2 and symmetrical a ,a-1, a , a-1 generating sets. In the first case com- 4. "x Î X и "p Î P : 4.1. g = x ○ p ; 4.2. if g Î Ks , Ks = Ks 5. P = Ks - Ks-1 ; 6. F (s) =| P | ; È{g}; 1 1 2 2 putation time under k = 14 takes about18 hours, in the second - 36 hours. Table presents diameters D and aver- age diameters D for the Cayley graphs of Bk for the specified generating sets. For illustration in fig. 1, 2 growth functions of the group B14 are presented. Cayley graphs of group Bk characteristics Bk Bk = a1 , a2 B = a ,a-1 , a , a-1 k 1 1 2 2 k D D D D 2 12 6 6 3 3 14 8 8 5 4 18 11 11 7 5 23 15 12 8 6 28 17 15 10 7 28 20 17 12 8 35 23 21 14 9 36 26 22 16 10 39 28 24 18 11 42 31 26 20 12 43 34 27 21 13 49 37 31 23 14 56 41 34 25 Fig. 1. The graph of the growth function of the group B14 = a1 , a2 Рис. 1. График функции роста группы B14 = a1 , a2 Fig. 2. The graph of the growth function of the group B = a ,a-1 , a , a-1 14 1 1 2 2 Рис. 2. График функции роста группы B = a ,a-1 , a , a-1 14 1 1 2 2 Conclusion. As mentioned above the Cayley graphs represent an effective model for the topology of multi- processor computing systems design. Therefore, for the creation of supercomputers with exaFLOPS performance (1018 floating point operations per second) knowledge of characteristics of super-large-scale Cayley graphs might be required. The results of this research can be used for perspective topologies design of MCS.

Авторлар туралы

A. Kuznetsov

Reshetnev Siberian State University of Science and Technology

Email: kuznetsov@sibsau.ru
31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

V. Kishkan

Reshetnev Siberian State University of Science and Technology

31, Krasnoyarsky Rabochy Av., Krasnoyarsk, 660037, Russian Federation

Әдебиет тізімі

Қосымша файлдар