3
$\begingroup$

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|$?

Improve this question
$\endgroup$
5
  • 6
    $\begingroup$ Isn't that the diameter of the Cayley graph? $\endgroup$
    – LeechLattice
    Commented Jul 9, 2018 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
    Commented Jul 9, 2018 at 12:20
  • $\begingroup$ Computing the quantity $N(S,G)$ is hard in general. The GAP package may be useful for your purpose. $\endgroup$
    – LeechLattice
    Commented Jul 9, 2018 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
    Commented Jul 9, 2018 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
    Commented Jul 9, 2018 at 14:03

2 Answers 2

Reset to default
7
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jul 10, 2018 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.
    Commented Jul 10, 2018 at 9:12
  • $\begingroup$ thanks, I was not aware of this definition. $\endgroup$
    – Yiftach Barnea
    Commented Jul 10, 2018 at 10:00
1
$\begingroup$

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

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .