Diameters of Chevalley groups over local rings. (Q1925813)

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\).