# 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_tuplesFunction
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)

source
on_setsFunction
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

source
permutedFunction
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" ]

source
on_indeterminatesFunction
on_indeterminates(f::GAP.GapObj, p::PermGroupElem)
on_indeterminates(f::Nemo.MPolyElem, p::PermGroupElem)
on_indeterminates(f::MPolyIdeal, p::PermGroupElem)
on_indeterminates(f::GAP.GapObj, p::MatrixGroupElem)
on_indeterminates(f::Nemo.MPolyElem{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 Nemo.MPolyElem 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 = PolynomialRing(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 = PolynomialRing(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

source

## 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.

gsetMethod
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

source
permutationFunction
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)

source
action_homomorphismMethod
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

source
orbitMethod
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

source
orbitMethod
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

source
orbitsMethod
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]

source

## Stabilizers

stabilizerMethod
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, Vectors of integers, and Sets of integers are given by ^, on_tuples, and on_sets, respectively. If G is a MatrixGroup then the default actions on FreeModuleElems, Vectors of them, and Sets 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

source