> < ^ From:

< ^ Subject:

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 ___________________________________________________________________

> < [top]