gap
gap copied to clipboard
gap-system
definition of `IsTransitive`?
Is the following really intended?
gap> g:= Group([ (2,4,3), (3,4) ]);
Group([ (2,4,3), (3,4) ])
gap> IsTransitive(g, [3,4]);
true
gap> Transitivity(g, [3,4]);
2
The definition of IsTransitive in the Reference Manual says the following.
41.10-1 IsTransitive
‣ IsTransitive( G, Omega[, gens, acts][, act] ) ─────────────────── operation ‣ IsTransitive( G ) ─────────────────────────────── property ‣ IsTransitive( xset ) ────────────────────────────── property
returns true if the action implied by the arguments is transitive, or false otherwise.
We say that a group G acts transitively on a domain D if and only if for every pair of points d, e ∈ D there is an element g in G such that d^g = e.
This definition does not require that G acts on the domain D. In this sense, the above GAP session is correct. On the other hand, we have the following.
gap> RankAction(g, [3,4]);
Error, RankAction: action must be transitive at /.../gap/lib/oprt.gi:3116 called from
[...]
This indicates that RankAction requires transitivity in the sense that G acts on the given domain.
Which of the two definitions is the right one?
To me, saying "... G act transitively on a domain D ... " as in the quoted manual segment always implies "G acts on D" and hence I would indeed expect and prefer an error, so I can catch my wrong input before it causes more problems later on. Indeed, I remember running into a variant of this very issue in the past and being confused for quite some time about things until I finally realized that I had accidentally provided a bad "domain".
I stumbled over the inconsistency when I wanted to construct an example that produces an error, and was surprised that there was no error. I hope that nobody relies on the strange behaviour, and I propose to require transitivity on the given domain, and to make the documentation more explicit in this respect. (I will provide a pull request.)
The example fits with the documentation. But I would also prefer the definition: IsTransitive(G[, Omega][, act]) returns true iff Omega is a single orbit of G under the action act. The current documentation and the method only want that Omega is a subset of a single orbit. I think this is not the usual mathematical meaning of IsTransitive.
This is a can of worms.
Fixing/changing IsTransitive is easy, and Transitivity is then automatically fixed.
However, related functions have similar problems:
gap> g:= Group( [ (2,4,3), (3,4) ] );
Group([ (2,4,3), (3,4) ])
gap> Blocks( g, [ 3, 4 ] ); # no error because the length is prime
[ [ 3, 4 ] ]
gap> Blocks( g, [ 3, 4, 5, 6 ] );
Error, <G> must operate transitively on <D> at
[...]
gap> hom:= ActionHomomorphism( g, [ 3, 4 ], OnPoints );
<action homomorphism>
gap> MappingGeneratorsImages( hom ); # the object is not valid ...
[ [ (2,4,3), (3,4) ], [ fail, (1,2) ] ]
gap> Image( hom ); # ... and here we get an error (at least)
Error, no method found!
[...]
All the methods in question assume that the given group acts on the given domain. If we add checks whether this is the case, the natural next step is to provide a way to omit these checks.
After a discussion with @fingolfin, I think that it will be already an improvement if the documentation of the operations in question states that there are currently no checks whether the input really defines a group action on the given domain. ~~I will provide a pull request in this direction.~~ I have added the documentation changes to pull request #4907.
(Related open issues are #3364 and #3541.)