[GAP Forum] Does every finite group have a built-in total ordering?

[Will Chen]

Thanks for your answer!

When you say "it also is not guaranteed to be stable between different GAP
sessions", do you mean that if I use "SaveWorkspace", and later load the
saved workspace, the ordering may have changed? (Ie, a stored minimal
element may no longer be minimal upon loading the saved workspace?)

On Sat, Apr 22, 2017 at 10:51 AM, Hulpke,Alexander <
Alexander.Hulpke at colostate.edu> wrote:

> Dear Will, Dear Forum,
>
> In other words, given a finite group G represented in GAP, is G guaranteed
> to have an immutable total ordering which "Minimum" is always guaranteed to
> use when called via "Minimum(List(X))" where X is a subset of G?
>
>
> The intention is that all classes of objects (group elements, polynomials,
> finite field elements) provide a total order, via the `<` operator. This
> comparison is not dependent on the representation, that is subgroups
> compare the same regardless of the generating set. (In general groups,
> cosets etc. compare the same as their sorted element lists would.)
> This is the order used by `Minimum`, thus what you are doing will work.
>
> Caveats:
>
> 1) This order is not guaranteed to be the one every user would consider
> ``natural’’ (e.g. the natural ordering on the elements of the field with 11
> elements is
>
> gap> List(Elements(GF(11)),Int);
> [ 0, 1, 2, 4, 8, 5, 10, 9, 7, 3, 6 ]
>
> ) but may dependent on internal workings or even arbitrary internal
> choices. (It is obviously the natural order for rationals, but will *not*
> be so for real irrationals!)
>
> 2) In some situations (say cosets of a subgroup of a finitely presented
> group) calculation of the order can be extremely costly.
>
> 3) The order is only guaranteed to be stable within classes of objects
> that GAP can compare for equality. If you create A5 twice as finitely
> presented group with the same presentation, the order might be different.
> It also is not guaranteed to be stable between different GAP sessions (So
> depending o the kind of objects you may not be able to store minimal
> elements.)
> This issue is irrelevant for permutations.
>
> 4) The availability of such an order is a policy but not policed
> automatically by the type system, but relies on the implementor. You *can*
> implement a class of objects that are group elements for which `<` does not
> work, but that should not be the case for objects provided in the library.
>
> All the best,
>
>   Alexander Hulpke
>
> -- Colorado State University, Department of Mathematics,
> Weber Building, 1874 Campus Delivery, Fort Collins, CO 80523-1874, USA
> email: hulpke at colostate.edu, Phone: ++1-970-4914288 <(970)%20491-4288>
> http://www.math.colostate.edu/~hulpke
>
>
>


-- 

William Chen
Member, School of Mathematics
Institute for Advanced Study,
Princeton, NJ, 08540
oxeimon at gmail.com