#5664: [with patch, needs review] Bugs in PermutationGroup_subgroup.__cmp__
--------------------------+-------------------------------------------------
Reporter: SimonKing | Owner: SimonKing
Type: defect | Status: new
Priority: critical | Milestone: sage-4.0
Component: group_theory | Keywords: comparison subgroup
--------------------------+-------------------------------------------------
Comment(by SimonKing):
The new patch (relative to sage-3.4.1.rc3) now relies on gap's
{{{IsSubgroup}}}.
Hence, the examples discussed above now work as expected, {{{__cmp___}}}
extends the subgroup lattice:
* If G is subgroup of H then G<H
* If neither G is subgroup of H nor H is subgroup of G, then, in order to
give any answer at all, return whatever gap suggests.
However, there is a price to pay. The result is not an ordering!
{{{
sage: H1 = PermutationGroup([[(1,2)],[(5,6)]])
sage: H2 = PermutationGroup([[(3,4)]])
sage: H3 = PermutationGroup([[(1,2)]])
# H1,H2 are mutually not subgroups, and H2,H3 are mutually not subgroups
sage: H1 < H2 # according to Gap's ordering
True
sage: H2 < H3 # according to Gap's ordering
True
sage: H3 < H1 # since H3 is a subgroup of H1
True
}}}
So, really our choices are:
1. Return gap's ordering -- which has nothing to do with subgroups. Nasty
2. Do as suggested in my new patch -- then we don't have transitivity.
Nasty
3. Invest an enormous amount of work into finding a total ordering on
permutation groups that extends the subgroup lattice.
Since I doubt that 3. is mathematically possible (and even if it is, it
would probably be unfeasible), I think we should chose 2.
What do you think?
Sidenote:
Working on this patch, I found that the method {{{is_subgroup()}}} does
not rely on gap's {{{IsSubgroup}}}. Instead, it tests if any element of
the first group is element of the second group.
And the element containment test (G.has_element(g)) also does not directly
rely on Gap. Instead, the list of all elements of G is created (but not
cached), and it is tested whether g is on this list.
It seems to me that {{{IsSubgroup}}} is much faster than {{{is_subgroup}},
hence I suggest that the latter should be rewritten. But this will be a
different ticket.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/5664#comment:21>
Sage <http://sagemath.org/>
Sage - Open Source Mathematical Software: Building the Car Instead of
Reinventing the Wheel
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
