Diameters of Chevalley groups over local rings.

DOI10.1007/S00013-012-0451-6MaRDI QIDQ1925813zbMATH OpenOpenAlexFDO

Authors Oren Dinai

Publication date 19 December 2012

Published in Archiv der Mathematik (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1201.4686, http://hdl.handle.net/20.500.11850/60011

zbMATH Keywords

Cayley graphsChevalley group schemesdiameter of groupslocal rings

Mathematics Subject Classification ID

Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Group schemes (14L15) Arithmetic and combinatorial problems involving abstract finite groups (20D60) Generators, relations, and presentations of groups (20F05) Other matrix groups over rings (20H25)

Abstract: Let G be a Chevalley group scheme of rank l. We show that the following holds for some absolute constant d>0 and two functions p_0=p_0(l) and C=C(l,p). Let p>p_0 be a prime number and let G_n:=G(�/p^n�) be the family of finite groups for n>0. Then for any n>0 and any subset S which generates G_n we have diam(G_n,S)< C n^d, i.e., any element of G_n is a product of Cn^d elements from Scup S^{-1}. In particular, for some C'=C'(l,p) and for any n>0 we have, diam(G_n,S)< C' log^d(|G_n|). Our proof is elementary and effective, in the sense that the constant d and the functions p_0(l) and C(l,p) are calculated explicitly. Moreover, there exists an efficient algorithm to compute a short path between any two vertices in any Cayley graph of the groups G_n.

Review text

The diameter of groups, aside from being a fascinating field of research, has a huge amount of applications to other important fields. In addition to Group Theory and Combinatorics, the diameter of groups is widely known for its role in Theoretical Computer Science areas such as Communication Networks, Algorithms and Complexity. The wide spectrum of applications involved makes this an interdisciplinary field. Let \(G\) be a Chevalley group scheme of rank \(l\). Let \(G_n:=G(\mathbb Z/p^n\mathbb Z)\) be the family of finite groups for \(n\in\mathbb N\) and some fixed prime number \(p>p_0\). This paper proves a uniform poly-logarithmic diameter bound of the Cayley graphs of \(G_n\) with respect to arbitrary sets of generators. In other words, for any subset \(S\) which generates \(G_n\), any element of \(G_n\) is a product of \(Cn^d\) elements from \(S\cup S^{-1}\). The proof is elementary and effective, in the sense that the constant \(d\) and the functions \(p_0(l)\) and \(C(l,p)\) are calculated explicitly. Moreover, the author gives an efficient algorithm for computing a short path between any two vertices in any Cayley graph of the groups \(G_n\).

Recommendations

• Diameters of Cayley graphs of Chevalley groups
• A diameter bound for finite simple groups of large rank
• Poly-log diameter bounds for some families of finite groups
• On the diameter of a Cayley graph of a simple group of Lie type based on a conjugacy class
• Diameters of Cayley graphs generated by transposition trees

Cites work

• Chevalley groups over local rings
• Expander graphs, gonality, and variation of Galois representations
• Growth in SL2 over finite fields
• scientific article; zbMATH DE number 2221904 (Why is no real title available?)
• New results on expanders
• On the diameter of Cayley graphs of the symmetric group
• On the diameter of permutation groups
• On the Rigidity of Lie Lattices and Just Infinite Powerful Groups
• Poly-log diameter bounds for some families of finite groups
• Uniform diameter bounds for some families of Cayley graphs

Cited in

(5)

• Poly-log diameter bounds for some families of finite groups
• Trivial points on towers of curves
• Navigating directed Cayley graphs of small diameter: a potent Solovay-Kitaev procedure
• Diameters of Cayley graphs of Chevalley groups
• Finite groups of uniform logarithmic diameter.

This page was built for publication: Diameters of Chevalley groups over local rings.

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1925813)