[GAP Forum] Ordering of group elements
William DeMeo
williamdemeo at gmail.com
Wed Jan 8 22:31:03 GMT 2014
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
--
More information about the Forum
mailing list