[GAP Forum] Ordering of group elements

[William DeMeo]

Hello Forum,

We are working on an application involving functions defined on
groups.  In our programs functions are represented as vectors that are
indexed by the elements of a given group.  Therefore, the order in
which group elements are listed is important when performing
operations with these functions (e.g. convolution).

I noticed that, in GAP, the default cyclic group of order 8 has 3
generators, and the elements of the group are listed as follows:

gap> G:=CyclicGroup(8);
<pc group of size 8 with 3 generators>

gap> Elements(G);
[ <identity> of ..., f1, f2, f3, f1*f2, f1*f3, f2*f3, f1*f2*f3 ]

gap> GeneratorsOfGroup(G);
[ f1, f2, f3 ]

Suppose instead we want the 8 element cyclic group to be represented
with one generator.  We can do this as follows:

gap> f:= FreeGroup("x");
<free group on the generators [ x ]>

gap> g:= f/[f.1^8];
<fp group on the generators [ x ]>

gap> Elements(g);
[ <identity ...>, x, x^2, x^4, x^3, x^-3, x^-2, x^-1 ]

AsSet or AsList or AsSortedList or AsSSortedList all give the same
ordering of the group elements as does the Elements function.


Finally, here are my questions:


Question 1: Why is the default ordering of the elements not one of the
alternatives below?

[ <identity ...>, x, x^2, x^3, x^4, x^-3, x^-2, x^-1 ]

or

[ <identity ...>, x, x^2, x^3, x^4, x^5, x^6, x^7 ]


Question 2: Suppose our application requires the group elements be
listed in this "natural" way.  Is it possible to do this without
having to inspect each group we use by hand?  In other words, is it
possible to anticipate the ordering that GAP will use for a given
group, so that we can write our programs accordingly?


Question 3: Is there no conventional or "natural" ordering of elements
for certain groups, in particular the cyclic groups?  And why does GAP
prefer ...x^2, x^4, x^3... over ...x^2, x^3, x^4... in the example
above?


As another example, here is the cyclic group of order 16:

gap> g:= f/[f.1^16];
<fp group on the generators [ x ]>

gap> Elements(g);
[ <identity ...>, x, x^2, x^4, x^8, x^3, x^5, x^9, x^6, x^10, x^12,
x^7, x^11, x^13, x^14, x^15 ]


Thank you in advance for any suggestions or advice.  If there is no
general way to anticipate how GAP will order elements of a group, then
any comments on GAP's choice of element ordering for particular
examples (like cyclic groups or symmetric groups) would be very much
appreciated.


Sincerely,

William


--
  William DeMeo
  Department of Mathematics
  University of South Carolina
  1523 Greene Street
  Columbia, SC 29208
  USA

  phone: 803-261-9135
  http://williamdemeo.org
  http://williamdemeo.github.io/CV
--