# Group Actions

A *group action* of a group G on a set Ω (from the right) is defined by a map μ: Ω × G → Ω that satisfies the compatibility conditions μ(μ(x, g), h) = μ(x, g*h) and μ(x, one(G)) == x for all x ∈ Ω.

The maps μ are implemented as functions that take two arguments, an element x of Ω and a group element g, and return the image of x under g.

In many cases, a natural action is given by the types of the elements in Ω and in G. For example permutation groups act on positive integers by just applying the permutations. In such situations, the function `^`

can be used as action function, and `^`

is taken as the default whenever no other function is prescribed.

However, the action is not always determined by the types of the involved objects. For example, permutations can act on vectors of positive integers by applying the permutations pointwise, or by permuting the entries; matrices can act on vectors by multiplying the vector with the matrix, or by multiplying the inverse of the matrix with the vector; and of course one can construct new custom actions in situations where default actions are already available.

Thus it is in general necessary to specify the action function explicitly, see the following sections.

## Common actions of group elements

`on_tuples`

— Function```
on_tuples(tuple::GAP.GapObj, x::GAPGroupElem)
on_tuples(tuple::Vector{T}, x::GAPGroupElem) where T
on_tuples(tuple::T, x::GAPGroupElem) where T <: Tuple
```

Return the image of `tuple`

under `x`

, where the action is given by applying `^`

to the entries of `tuple`

.

For `Vector`

and `Tuple`

objects, one can also call `^`

instead of `on_tuples`

.

**Examples**

```
julia> g = symmetric_group(3); g[1]
(1,2,3)
julia> l = GAP.GapObj([1, 2, 4])
GAP: [ 1, 2, 4 ]
julia> on_tuples(l, g[1])
GAP: [ 2, 3, 4 ]
julia> on_tuples([1, 2, 4], g[1])
3-element Vector{Int64}:
2
3
4
julia> on_tuples((1, 2, 4), g[1])
(2, 3, 4)
julia> (1, 2, 4)^g[1]
(2, 3, 4)
```

`on_sets`

— Function```
on_sets(set::GAP.GapObj, x::GAPGroupElem)
on_sets(set::Vector, x::GAPGroupElem)
on_sets(set::Tuple, x::GAPGroupElem)
on_sets(set::AbstractSet, x::GAPGroupElem)
```

Return the image of `set`

under `x`

, where the action is given by applying `^`

to the entries of `set`

, and then turning the result into a sorted vector/tuple or a set, respectively.

For `Set`

objects, one can also call `^`

instead of `on_sets`

.

**Examples**

```
julia> g = symmetric_group(3); g[1]
(1,2,3)
julia> l = GAP.GapObj([1,3])
GAP: [ 1, 3 ]
julia> on_sets(l, g[1])
GAP: [ 1, 2 ]
julia> on_sets([1, 3], g[1])
2-element Vector{Int64}:
1
2
julia> on_sets((1, 3), g[1])
(1, 2)
julia> on_sets(Set([1, 3]), g[1])
Set{Int64} with 2 elements:
2
1
julia> BitSet([1, 3])^g[1]
BitSet with 2 elements:
1
2
```

`permuted`

— Function```
permuted(pnt::GAP.GapObj, x::PermGroupElem)
permuted(pnt::Vector, x::PermGroupElem)
permuted(pnt::Tuple, x::PermGroupElem)
```

Return the image of `pnt`

under `x`

, where the action is given by permuting the entries of `pnt`

with `x`

.

**Examples**

```
julia> g = symmetric_group(3); g[1]
(1,2,3)
julia> a = ["a", "b", "c"]
3-element Vector{String}:
"a"
"b"
"c"
julia> permuted(a, g[1])
3-element Vector{String}:
"c"
"a"
"b"
julia> permuted(("a", "b", "c"), g[1])
("c", "a", "b")
julia> l = GAP.GapObj(a, recursive = true)
GAP: [ "a", "b", "c" ]
julia> permuted(l, g[1])
GAP: [ "c", "a", "b" ]
```

`on_indeterminates`

— Function```
on_indeterminates(f::GAP.GapObj, p::PermGroupElem)
on_indeterminates(f::MPolyRingElem, p::PermGroupElem)
on_indeterminates(f::MPolyIdeal, p::PermGroupElem)
on_indeterminates(f::GAP.GapObj, p::MatrixGroupElem)
on_indeterminates(f::MPolyRingElem{T}, p::MatrixGroupElem{T, S}) where T where S
on_indeterminates(f::MPolyIdeal, p::MatrixGroupElem)
```

Return the image of `f`

under `p`

. If `p`

is a `PermGroupElem`

then it acts via permuting the indeterminates, if `p`

is a `MatrixGroupElem`

then it acts via evaluating `f`

at the vector obtained by multiplying `p`

with the (column) vector of indeterminates.

For `MPolyRingElem`

and `MPolyIdeal`

objects, one can also call `^`

instead of `on_indeterminates`

.

**Examples**

```
julia> g = symmetric_group(3); p = g[1]
(1,2,3)
julia> R, x = polynomial_ring(QQ, ["x1", "x2", "x3"]);
julia> f = x[1]*x[2] + x[2]*x[3]
x1*x2 + x2*x3
julia> f^p
x1*x3 + x2*x3
julia> x = [GAP.Globals.X( GAP.Globals.Rationals, i ) for i in 1:3];
julia> f = x[1]*x[2] + x[2]*x[3]
GAP: x_1*x_2+x_2*x_3
julia> on_indeterminates(f, p)
GAP: x_1*x_3+x_2*x_3
julia> g = general_linear_group(2, 5); m = g[2]
[4 1]
[4 0]
julia> R, x = polynomial_ring(base_ring(g), degree(g));
julia> f = x[1]*x[2] + x[1]
x1*x2 + x1
julia> f^m
x1^2 + 4*x1*x2 + 4*x1 + x2
```

## G-Sets

The idea behind G-sets is to have objects that encode the permutation action induced by a group (that need not be a permutation group) on a given set. A G-set provides an explicit bijection between the elements of the set and the corresponding set of positive integers on which the induced permutation group acts, see `action_homomorphism(Omega::GSetByElements{T}) where T<:GAPGroup`

.

`gset`

— Method`gset(G::GAPGroup[, fun::Function], seeds, closed::Bool = false)`

Return the G-set `Omega`

that consists of the closure of the seeds `seeds`

under the action of `G`

defined by `fun`

.

This means that `Omega`

contains all elements `fun(omega, g)`

for `omega`

in `seeds`

and `g`

in `G`

.

`fun`

can be omitted if the element type of `seeds`

implies a reasonable default, for example, if `G`

is a `PermGroup`

and `seeds`

is a `Vector{T}`

where `T`

is one of `Int`

, `Set{Int}`

, `Vector{Int}`

.

If `closed`

is set to `true`

then `seeds`

is assumed to be closed under the action of `G`

. In this case, `collect(Omega)`

is guaranteed to be equal to `collect(seeds)`

; in particular, the ordering of points in `seeds`

(if applicable) is kept. Note that the indexing of points in `Omega`

is used by `action_homomorphism`

.

**Examples**

```
julia> G = symmetric_group(4);
julia> length(gset(G, [[1]])) # natural action
4
julia> length(gset(G, [[1, 2]])) # action on ordered pairs
12
julia> length(gset(G, on_sets, [[1, 2]])) # action on unordered pairs
6
```

`permutation`

— Function`permutation(Omega::GSetByElements{T}, g::BasicGAPGroupElem{T}) where T<:GAPGroup`

Return the element of the permutation group that describes the action of `g`

on `Omega`

, where `g`

is an element of `acting_group(Omega)`

.

**Examples**

```
julia> G = symmetric_group(4);
julia> Omega = gset(G, [[1, 2]]);
julia> x = gen(G, 1)
(1,2,3,4)
julia> permutation(Omega, x)
(1,2,4,7)(3,6,9,12)(5,8,10,11)
```

`action_homomorphism`

— Method`action_homomorphism(Omega::GSetByElements{T}) where T<:GAPGroup`

Return the group homomorphism `act`

with domain `G = acting_group(Omega)`

and codomain `symmetric_group(n)`

that describes the permutation action of `G`

on `Omega`

, where `Omega`

has `n`

elements.

This means that if an element `g`

in `G`

maps `collect(Omega)[i]`

to `collect(Omega)[j]`

then `act(g)`

maps `i`

to `j`

.

**Examples**

```
julia> G = symmetric_group(6);
julia> Omega = gset(G, [Set([1, 2])]); # action on unordered pairs
julia> acthom = action_homomorphism(Omega)
Group homomorphism from
Sym( [ 1 .. 6 ] )
to
Sym( [ 1 .. 15 ] )
julia> g = gens(G)[1]
(1,2,3,4,5,6)
julia> elms = collect(Omega);
julia> actg = acthom(g)
(1,2,3,5,7,10)(4,6,8,11,14,13)(9,12,15)
julia> elms[1]^g == elms[2]
true
julia> 1^actg == 2
true
```

`orbit`

— Method`orbit(Omega::GSet, omega::T) where T`

Return the G-set that consists of the elements `fun(omega, g)`

where `g`

is in the group of `Omega`

and `fun`

is the underlying action of `Omega`

.

**Examples**

```
julia> G = sylow_subgroup(symmetric_group(6), 2)[1]
Group([ (1,2), (3,4), (1,3)(2,4), (5,6) ])
julia> Omega = gset(G, [1, 5]);
julia> length(orbit(Omega, 1))
4
```

`orbit`

— Method`orbit(G::GAPGroup[, fun::Function], omega)`

Return the G-set that consists of the images of `omega`

under the action of `G`

defined by `fun`

.

This means that the result contains all elements `fun(omega, g)`

for `g`

in `G`

.

`fun`

can be omitted if the type of `Omega`

implies a reasonable default, for example, if `G`

is a `PermGroup`

and `omega`

is one of `Int`

, `Set{Int}`

, `Vector{Int}`

.

**Examples**

```
julia> G = symmetric_group(4);
julia> length(orbit(G, 1))
4
julia> length(orbit(G, [1, 2]))
12
julia> length(orbit(G, on_sets, [1, 2]))
6
```

`orbits`

— Method`orbits(Omega::GSet)`

Return the vector of transitive G-sets in `Omega`

.

**Examples**

```
julia> G = sylow_subgroup(symmetric_group(6), 2)[1]
Group([ (1,2), (3,4), (1,3)(2,4), (5,6) ])
julia> orbs = orbits(gset(G));
julia> map(collect, orbs)
2-element Vector{Vector{Int64}}:
[1, 2, 3, 4]
[5, 6]
```

## Stabilizers

`stabilizer`

— Method`stabilizer(G::Oscar.GAPGroup, pnt::Any[, actfun::Function])`

Return the subgroup of `G`

that consists of all those elements `g`

that fix `pnt`

under the action given by `actfun`

, that is, `actfun(pnt, g) == pnt`

holds.

The default for `actfun`

depends on the types of `G`

and `pnt`

: If `G`

is a `PermGroup`

then the default actions on integers, `Vector`

s of integers, and `Set`

s of integers are given by `^`

, `on_tuples`

, and `on_sets`

, respectively. If `G`

is a `MatrixGroup`

then the default actions on `FreeModuleElem`

s, `Vector`

s of them, and `Set`

s of them are given by `*`

, `on_tuples`

, and `on_sets`

, respectively.

**Examples**

```
julia> G = symmetric_group(5);
julia> S = stabilizer(G, 1); order(S[1])
24
julia> S = stabilizer(G, [1, 2]); order(S[1])
6
julia> S = stabilizer(G, Set([1, 2])); order(S[1])
12
julia> S = stabilizer(G, [1,1,2,2,3], permuted); order(S[1])
4
```