[GAP Forum] Does every finite group have a built-in total ordering?
Alexander Hulpke
hulpke at fastmail.fm
Sun Apr 23 01:19:55 BST 2017
> On Apr 22, 2017, at 5:47 PM, Will Chen <oxeimon at gmail.com <mailto:oxeimon at gmail.com>> wrote:
>
> 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?)
A saved workspace is like the same session, so there it is guaranteed. A.
>
> On Sat, Apr 22, 2017 at 10:51 AM, Hulpke,Alexander <Alexander.Hulpke at colostate.edu <mailto: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 <mailto:hulpke at colostate.edu>, Phone: ++1-970-4914288 <tel:(970)%20491-4288>
> http://www.math.colostate.edu/~hulpke <http://www.math.colostate.edu/~hulpke>
>
>
>
>
>
> --
>
> William Chen
> Member, School of Mathematics
> Institute for Advanced Study,
> Princeton, NJ, 08540
> oxeimon at gmail.com <mailto:oxeimon at gmail.com>
More information about the Forum
mailing list