Let $G$ be a finite group and $S$ be generating set it. Now given all words with alphabet $S$, then there exists a minimum word length $N(S,G)$ such that all group elements are represented by a word of length $\le N(S,G)$. A famous example is the group of Rubik's Cube where the answer is known to be 26 (if $S$ is the set of all quarter twists) and this is known as God's number.

Where can I find more example of this kind, i.e. groups where $|S|$ and $N(S,G)$ are know (or there is at least some bound) and we have that $|S|,N(S,G)\ll |G|$?

More generally, can we expect that for most groups we can find some generating set $S$ such that $|S|,N(S,G)\ll |G|$?

  • 6
    $\begingroup$ Isn't that the diameter of the Cayley graph? $\endgroup$ – Bullet51 Jul 9 '18 at 12:18
  • 1
    $\begingroup$ I can imagine an asymptotic meaning, but how do I decide for a single group $G$ and generating set $S$ whether $\lvert S\rvert, N(S, G) \ll \lvert G\rvert$ is true? $\endgroup$ – LSpice Jul 9 '18 at 12:20
  • $\begingroup$ Computing the quantity $N(S,G)$ is hard in general. The GAP package may be useful for your purpose. $\endgroup$ – Bullet51 Jul 9 '18 at 12:32
  • 4
    $\begingroup$ One example that comes to mind are the Coxeter groups. For example for $G=S_n$ with S=the neighbour-transpositions the length of the longest element (the permutation $(1,n)(2,n-1)...$) is $\frac{n(n-1)}{2}=O(n^2)$, but the order of the group is of course $n! \gg n^2$ $\endgroup$ – Johannes Hahn Jul 9 '18 at 12:32
  • 1
    $\begingroup$ Intuitively I would say that you will find such a set $S$ for most groups, yes. You might be interested in this conjecture here ( en.wikipedia.org/wiki/Diameter_(group_theory) ), stating that $N(S,G)$ remains small no matter what set $S$ you take, at least as long as $G$ is simple. $\endgroup$ – Dirk Jul 9 '18 at 14:03

This is one of the fundamental questions in the theory of groups known as the width problem.

One of the best (general) references devoted to this problem is the book Words: Notes on Verbal Width in Groups by Dan Segal.

Yet another good reference is the paper Width questions for finite simple groups by Martin Liebeck.

A well-known conjecture due to Babai states that there must exists a constant $c$ such that $N(S,G)<(\log|G|)^c$ for all non-abelian finite simple groups $G$ and generating sets $S$.

L. Babai and A. Seress, On the diameter of permutation groups, European J. Combin. 13 (1992), 231–243.

  • $\begingroup$ I don't think this is width, as far as I remember, width is for specific word. I think it is the diameter of the Cayley graph, $\endgroup$ – Yiftach Barnea Jul 10 '18 at 9:07
  • $\begingroup$ @YiftachBarnea The width of a group $G$ with respect to a generating set $S$ is the same as the diameter of Cayley graph $\mathrm{Cay}(G,S)$, that is the smallest positive integer $k$ such that every element of $G$ is the product of at most $k$ elements of $S$. $\endgroup$ – M. Farrokhi D. G. Jul 10 '18 at 9:12
  • $\begingroup$ thanks, I was not aware of this definition. $\endgroup$ – Yiftach Barnea Jul 10 '18 at 10:00

The requirement $|S|\ll |G|$ looks odd to me as $S$ is a subset of $G$. As to $N(S,G)$ -- well, at least for finite abelian groups it is known to be strictly smaller than the size of the group. In fact, if $G$ is finite abelian of the type $(m_1,\dotsc, m_r)$ with $m_1\mid\dotsb\mid m_r$, then the largest possible value of your $N(S,G)$ as $S$ varies over all generating sets is $(m_1-1)+\dotsb+(m_r-1)$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.