PermutationGroup.is_transitive is broken

[boothby]

sage: G = Graph({0:[1],1:[2]}); G.num_verts()
3
sage: A = G.automorphism_group(); A
Permutation Group with generators [(2,3)]
sage: A.is_transitive()
True
sage: A.gens()[0].list()
[1,3,2]

Huh? The cyclic group of order 2 acting on 3 letters is transitive?

CC: @aghitza

Component: algebra

Issue created by migration from https://trac.sagemath.org/ticket/3544

[rlmill]

comment:1

This is closely related to #3404. See #3545.

[wdjoyner]

comment:2

This wraps IsTransitive, which is assuming that the degree is 2:

sage: G = Graph({0:[1],1:[2]})
sage: A = G.automorphism_group(); A
APermutation Group with generators [(2,3)]
sage: GA = gap(A)
sage: GA.Transitivity()
2
sage: GA.IsTransitive()
true

However, the docstring for is_transitive is wrong. There is no method A.set() implemented.

[sagetrac-mabshoff]

comment:3

Please always assign a milestone.

Cheers,

Michael

[wdjoyner]

comment:4

I would suggest the following:

(a) There is no bug in is_transitive but the docstring is wrong.

(b) a "set" method should be implemented for the class PermutationGroup.

(c) Possibly a verbose option could be added which prints (if the group
is transitive) the set on which the group acts transitively?

If this seems reasonable, I could try working on this.

[rlmill]

comment:5

I don't like this approach. Instead, you should be able to tell the permutation group what it is acting on, and all the functions should be consistent. This is part of my goal for my summer work with permutation groups.

[williamstein]

comment:7

Some remarks:

• In GAP it is clearly documented that IsTransitive(G) returns whether or not G is transitive on the set of points moved by G. That's why this "bug" happens (this ticket).

• In Magma, all permutation groups G are embedded in a specific S_n and IsTransitive returns whether or not G is transitive on [1..n].

• Sage has a degree method for permutation groups, which gives back an n.

I think we view permutation groups as contained in S_n, which naturally acts on [1..n], so that should be the default. I think permutations groups should also at some point in the future be equipable with an action on any set. But the resulting object will be "a permutation group equipped with an action", and is_transitive will be defined relative to that. So for this ticket, we just need to decide on the default set acted on by a permutation group generated by a list of permutations. I think the most natural choice is the set {1,2, ..., n} given the embedding in S_n.

Anyway, I've attached a patch that fixes the bug, and makes is_transitive() return whether or not the group is transitive on [1..G.degree()]. I also fixed a few surrounding docstrings and added one to load_hap, so that doctest coverage for the file permgroup.py is now 100%.

[williamstein]

Attachment: trac_3544.patch.gz

[rlmill]

comment:9

Looks good to me!

[sagetrac-mabshoff]

comment:10

Merged in Sage 3.3.alpha1