[GAP Forum] Does every finite group have a built-in total ordering?
Hulpke,Alexander
Alexander.Hulpke at colostate.edu
Sat Apr 22 15:51:56 BST 2017
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<mailto:hulpke at colostate.edu>, Phone: ++1-970-4914288
http://www.math.colostate.edu/~hulpke
More information about the Forum
mailing list