GAP Forum
On Tue, Jul 10, 2001 at 02:56:23PM +0100, Kurt Ewald wrote:
> Dear Forum,
> I can't find functions as
> IsTransitive(G)
> Transitivity(G) -> 0,1,2
> Have I overlooked anything

Dear Kurt,

You've hit on a problem with the documentation that I'd noticed
only a few weeks ago and have fixed in the development version of GAP.
By the way, your query really should have gone to `gap-trouble'
rather than `gap-forum' i.e. gap-trouble@dcs.st-and.ac.uk.

When you do:

gap> ?IsTransitive
Help: several sections match this topic, type ?2 to see topic 2.
[1] reference:istransitive for class functions
[2] reference:istransitive.ctblfuns
[3] reference:istransitive.oprt

Though it's not obvious the one you want is the one with `.oprt'.
A similar thing happens with `Transitivity'.

I'm not sure what you meant by:

Transitivity(G) -> 0,1,2

In general, a group can have many actions on a given set. The one
usually termed the `natural' action is the default in GAP (GAP calls
it `OnPoints') e.g. the group G generated by (2 3 4) and (2 3), in GAP:

gap> G := Group( (2,3,4), (2,3) );
Group([ (2,3,4), (2,3) ])

has a natural action on the points {2, 3, 4}. To see if G is transitive
under this natural action, in GAP, we simply do:

gap> IsTransitive(G);
true

However, the natural action induces actions `on unordered pairs' and
`unordered triples' of distinct points. The set of unordered pairs of
distinct points of {2, 3, 4} is { {2,3}, {2,4}, {3,4} }. In GAP, the
command to get such is set is `Combinations':

gap> Combinations([2,3,4], 2);   
[ [ 2, 3 ], [ 2, 4 ], [ 3, 4 ] ]

(the second argument 2 indicated we wanted pairs).
To check whether G is transitive on unordered pairs of distinct points
we would do:

gap> IsTransitive(G, Combinations([2,3,4], 2), OnPairs);
true

A shorter way of saying that `G is transitive on unordered pairs of distinct
points' is to say it is `2-transitive'.

We can similarly check whether G is transitive on unordered triples of
distinct points, similarly ... but there is only one such triple {2, 3, 4}.
So the set of such triples { {2,3,4} } contains just one element. So, it
is not a surprise that:

gap> IsTransitive(G, [ [2,3,4] ], OnTuples);
true

... which says G is `3-transitive'.

(`OnTuples' is the generalisation of `OnPairs ... and, in fact, we could
have used `OnTuples' instead of `OnPairs' when checking.

We shouldn't be surprised that G is 3-transitive; after all it's really
just S_3 in disguise.

Finally, if we do:

gap> Transitivity(G);
3

which tells us that the largest integer k for which G is k-transitive
is 3, which we had already observed.

In GAP 4.3 (still a couple of months off) you will be able to do
(actually, now that I look at it, a few more improvements may happen
before then):

gap> ?IsTransitive
Help: several entries match this topic - type ?2 to get match [2]

[1] Reference: IsTransitive!for class functions
[2] Reference: IsTransitiveBinaryRelation
[3] Reference: IsTransitive!for group actions
[4] Reference: IsTransitive!for characters
gap> ?3

> IsTransitive( <G>, <Omega>[, <gens>, <acts>][, <act>] )!{for group
    actions}                                                             O
> IsTransitive( <xset> )!{for group actions}                             P

returns `true' if the action implied by the arguments is transitive, or
`false' otherwise.

An action is *transitive* if the whole domain forms one orbit.
[...lines deleted...]

gap> ?Transitivity                                                     
Help: several entries match this topic - type ?2 to get match [2]

[1] Reference: Transitivity!for class functions
[2] Reference: Transitivity!for group actions
[3] Reference: Transitivity!for characters
gap> ?2

> Transitivity( <G>, <Omega>[, <gens>, <acts>][, <act>] )!{for group
    actions}                                                             O
> Transitivity( <xset> )!{for group actions}                             A

returns the degree $k$ (a non-negative integer) of transitivity of the
action implied by the arguments, i.e. the largest integer $k$ such that
the action is $k$-transitive. If the action is not transitive `0' is
returned.

An action is *$k$-transitive* if every $k$-tuple of points can be mapped
simultaneously to every other $k$-tuple.

gap> g:=Group((1,3,2),(2,4,3));;
gap> IsTransitive(g,[1..5]);
false
gap> Transitivity(g,[1..4]);
2

*Note:* For permutation groups, the syntax `IsTransitive(<g>)' is also
permitted and tests whether the group is transitive on the points moved
by it, that is the group $< (2,3,4),(2,3)>$ is transitive (on 3 points).

The GAP 4.3 descriptions are relevant for your use with GAP 4.2.

  Regards,
  Greg Gamble
___________________________________________________________________
Greg Gamble   __________________   mailto:gregg@math.rwth-aachen.de
Lehrstuhl D fuer Mathematik                     Tel: +49 241 804545
Templergraben 64                                
52062 Aachen, Germany   http://www.math.rwth-aachen.de/~Greg.Gamble
___________________________________________________________________