Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS

   
Mobile Device Pairing
Green Open Access
Proceedings of the American Mathematical Society
Proceedings of the American Mathematical Society
ISSN 1088-6826(online) ISSN 0002-9939(print)

 

Poly-log diameter bounds for some families of finite groups


Author: Oren Dinai
Journal: Proc. Amer. Math. Soc. 134 (2006), 3137-3142
MSC (2000): Primary 05C25; Secondary 05C12
Published electronically: June 8, 2006
MathSciNet review: 2231895
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Fix a prime $ p$ and an integer $ m$ with $ p > m \geq 2$. Define the family of finite groups

$\displaystyle G_{n}:=SL_{m}\left(\mathbb{Z}/p^{n}\mathbb{Z}\right)$

for $ n=1,2,\ldots $. We will prove that there exist two positive constants $ C$ and $ d$ such that for any $ n$ and any generating set $ S\subseteq G_{n}$,

$\displaystyle diam(G_{n},S)\leq C\cdot {log}^{d}(\left\vert G_{n}\right\vert)$

when $ diam\left(G,S\right)$ is the diameter of the finite group $ G$ with respect to the set of generators $ S$. It is defined as the maximum over $ g\in G$ of the length of the shortest word in $ S\cup S^{-1}$ representing $ g$.

This result shows that these families of finite groups have a poly-logarithmic bound on the diameter with respect to any set of generators. The proof of this result also provides an efficient algorithm for finding such a poly-logarithmic representation of any element.


References [Enhancements On Off] (What's this?)


Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2000): 05C25, 05C12

Retrieve articles in all journals with MSC (2000): 05C25, 05C12


Additional Information

Oren Dinai
Affiliation: Einstein Institute of Mathematics, Edmond Safra Campus, Givat Ram, 91904 Jerusalem, Israel

DOI: http://dx.doi.org/10.1090/S0002-9939-06-08384-5
PII: S 0002-9939(06)08384-5
Received by editor(s): October 26, 2004
Received by editor(s) in revised form: June 8, 2005
Published electronically: June 8, 2006
Communicated by: Jonathan I. Hall
Article copyright: © Copyright 2006 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.