#9102: Docstring improvements for strong generating systems of permutation
groups
---------------------------+------------------------------------------------
Reporter: rbeezer | Owner: AlexGhitza
Type: enhancement | Status: needs_work
Priority: blocker | Milestone: sage-4.4.4
Component: algebra | Keywords:
Author: Rob Beezer | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
---------------------------+------------------------------------------------
Comment(by nthiery):
Hi Jason,
(please ignore my previous comment which was a fumble)
Replying to [comment:5 jasonbhill]:
> While looking at the amssymb issue, I came across a problem elsewhere in
what has been added to the docstring.
>
> "``base_of_group`` is a list of the positions on which ``self`` acts,"
>
> This is not correct. The base of a permutation group G is defined as a
list L of points in the domain of the action such that no element of G
fixes all points of L.
>
> http://en.wikipedia.org/wiki/Base_(group_theory)
>
> Computationally, this is equivalent to requiring no strong generator to
fix all points of the base, and hence the size of a base corresponds
directly to the length of the stabilizer chain given by the Schreier-Sims
algorithm. (In fact, this algorithm yields a base and the strong
generating system relative to that specific base.)
>
> The assertion that the base is not unique is correct, but the specific
base used must correspond to the stabilizer chain constructed from a
strong generating set. Otherwise, the information of the strong generating
set is of less computational value.
>
> For instance, a symmetric group of degree n has base of size n-1. So,
S_5 on points [1..5] has bases [1,2,4,5], [1,2,3,4], etc., depending on
the SGS. At the same time, any cyclic group has a base of size 1.
>
> You may of course artificially inflate the base and it will still follow
the definition, but then anyone using the strong generating set for
calculations (MANY invariants of a group follow from this) must
recalculate the base and this will often result in a different SGS.
Well, the code is correct: given a user-provided base, the code
returns a strong-generating-set with respect to this base. Indeed, the
definition of {{{base}}} in the docstring is needlessly restrictive;
it sure needs not contain all points.
A patch fixing this would be very welcome. I agree with Rob though
that this would be best left in a followup ticket. It would also
probably be best to wait until Mike's patch for permutation groups on
any set is merged in Sage to avoid conflicts, and not make his job
harder. There are several little things that could be improved as well
in the future:
* Check that {{{base}}} is a subset of the domain of this group
(i.e. the set on which the group act)
* Test that the final stabilizer set is indeed trivial
* Use the current base of the group as default value, and return
directly the strong generating set that GAP already has computed
for this group.
Cheers,
Nicolas
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/9102#comment:8>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
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.
