Diameter of the Cayley graph

We use the group algebra to determine the diameter of the Cayley graph of a group.

> G := Alt(6);
> QG := GroupAlgebra( Rationals(), G );
> e := QG!1 + &+[ QG!g : g in Generators(G) ];
> e;
Id(G) + (1, 2)(3, 4, 5, 6) + (1, 2, 3)

The group elements that can be expressed as words of length at most n in the generators of G have non-zero coefficient in . The following function returns for a group algebra element e a sequence with the cardinalities of the supports of and breaks when the group order is reached.

> wordcount := function(e)
>     f := e;
>     count := [ #Support(f) ];
>     while count[#count] lt #Group(Parent(e)) do
>         f *:= e;
>         Append(~count, #Support(f));
>     end while;
>     return count;
> end function;

Now apply this function to the above defined element:

> wordcount( e );
[ 3, 7, 14, 26, 47, 83, 140, 219, 293, 345, 360 ]

Thus, every element in can be expressed as a word of length at most 11 in the generators (1,2)(3,4,5,6) and (1,2,3). A better 2-generator set is for example (1,2,3,4,5) and (1,5,3,6,4), where all elements can be expressed as words of length at most 10 and this is in fact optimal. A worst 2-generator set is given by (1,2)(3,4) and (1,5,3,2)(4,6).

> wordcount( QG!1 + G!(1,2,3,4,5) + G!(1,5,3,6,4) );
[ 3, 7, 15, 31, 60, 109, 183, 274, 350, 360 ]
> wordcount( QG!1 + G!(1,2)(3,4) + G!(1,5,3,2)(4,6) );
[ 3, 6, 11, 18, 28, 43, 63, 88, 119, 158, 206, 255, 297, 329, 352, 360 ]

Next Group: Random distribution of words Previous Group: Group Algebras