Group actions

A group action of a group $G$ on a set $\Omega$ (from the right) is defined by a map $\mu:\Omega\times G\to \Omega$ that satisfies the compatibility conditions $\mu(\mu(x,g),h) = \mu(x, gh)$ and $\mu(x, 1_G) = x$ for all $x\in\Omega$.

The maps $\mu$ are implemented as functions that take two arguments, an element $x$ of $\Omega$ 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 $\Omega$ 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::GapObj, x::GAPGroupElem)
on_tuples(tuple::Vector, x::GAPGroupElem)
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 = 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::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 = 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::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 = GapObj(a; recursive = true)
GAP: [ "a", "b", "c" ]

julia> permuted(l, g[1])
GAP: [ "c", "a", "b" ]

on_indeterminates — Function

on_indeterminates(f::GapObj, p::PermGroupElem)
on_indeterminates(f::MPolyRingElem, p::PermGroupElem)
on_indeterminates(f::FreeAssociativeAlgebraElem, p::PermGroupElem)
on_indeterminates(f::MPolyIdeal, p::PermGroupElem)

Return the image of f under p where p acts via permuting the indeterminates.

For MPolyRingElem, FreeAssociativeAlgebraElem, 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

on_indeterminates(f::GapObj, p::MatrixGroupElem)
on_indeterminates(f::MPolyRingElem{T}, p::MatrixGroupElem{T}) where T
on_indeterminates(f::MPolyIdeal, p::MatrixGroupElem)

Return the image of f under p where p acts via evaluating f at the vector obtained by multiplying p with the (column) vector of indeterminates. This corresponds to considering the variables of the polynomial ring containing f as the basis of a vector space on which p acts by multiplication from the right.

For MPolyRingElem and MPolyIdeal objects, one can also call ^ instead of on_indeterminates.

Examples

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

on_lines — Function

on_lines(line::GapObj, x::GAPGroupElem)
on_lines(line::AbstractAlgebra.Generic.FreeModuleElem, x::GAPGroupElem)

Return the image of the nonzero vector line under x, where the action is given by first computing line * x and then normalizing the result by scalar multiplication from the left such that the first nonzero entry is the one of the base_ring of line.

Examples

julia> n = 2;  F = GF(5);  g = general_linear_group(n, F);

julia> v = gen(free_module(F, n), 1)
(1, 0)

julia> m = gen(g, 2)
[4   1]
[4   0]

julia> v * m
(4, 1)

julia> on_lines(v, m)
(1, 4)

on_echelon_form_mats — Function

on_echelon_form_mats(m::MatElem{T}, x::MatrixGroupElem) where T <: FinFieldElem

Return the image of m under x, where the action is given by first computing the product m * x and then normalizing the result by computing its reduced row echelon form with echelon_form.

Identifying m with the subspace of the natural module for the group of x that is generated by the rows of m, on_echelon_form_mats describes the action on subspaces of this natural module. Note that for computing the orbit and stabilizer of m w.r.t. on_echelon_form_mats, m must be in reduced row echelon form.

Examples

julia> n = 3;  q = 2;  F = GF(q);  V = free_module(F, n);

julia> G = GL(n, F);

julia> W, embW = sub(V, [gen(V,1), gen(V,3)])
(Subspace over F with 2 generators and no relations, Hom: W -> V)

julia> m = matrix(embW)
[1   0   0]
[0   0   1]

julia> S, _ = stabilizer(G, m, on_echelon_form_mats);  order(S)
24

julia> orb = orbit(G, on_echelon_form_mats, m);  length(orb)
7

on_subgroups — Function

on_subgroups(x::GapObj, g::GAPGroupElem) -> GapObj
on_subgroups(x::T, g::GAPGroupElem) where T <: GAPGroup -> T

Return the image of the group x under g. Note that x must be a subgroup of the domain of g.

Examples

julia> C = cyclic_group(20)
Pc group of order 20

julia> S = automorphism_group(C)
Aut( <pc group of size 20 with 3 generators> )

julia> H, _ = sub(C, [gens(C)[1]^4])
(Sub-pc group of order 5, Hom: H -> C)

julia> all(g -> on_subgroups(H, g) == H, S)
true

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. Note that the explicit elements of a G-set Omega can be obtained using collect(Omega).

gset — Method

gset(G::Union{GAPGroup, FinGenAbGroup}[, fun::Function], seeds, closed::Bool = false, check::Bool = true)

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 check is set to false then it is not checked whether the entries of seeds are valid as the first argument of fun.

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)

acting_group — Method

acting_group(Omega::GSetByElements)

Return the group G acting on Omega.

Examples

julia> G = symmetric_group(4);

julia> acting_group(gset(G, [1])) == G
true

action_function — Method

action_function(Omega::GSetByElements)

Return the function $f: \Omega \times G \to \Omega$ that defines the G-set.

Examples

julia> G = symmetric_group(4);

julia> action_function(gset(G, [1])) == ^
true

julia> action_function(gset(G, [[1, 2]])) == on_tuples
true

julia> action_function(gset(G, on_sets, [[1, 2]])) == on_sets
true

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(6)
  to Sym(15)

julia> g = gen(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

is_conjugate — Method

is_conjugate(Omega::GSet, omega1, omega2)

Return true if omega1, omega2 are in the same orbit of Omega, and false otherwise. To also obtain a conjugating element use is_conjugate_with_data.

Examples

julia> G = sylow_subgroup(symmetric_group(6), 2)[1]
Permutation group of degree 6 and order 16

julia> Omega = gset(G);

julia> is_conjugate(Omega, 1, 2)
true

julia> is_conjugate(Omega, 1, 5)
false

is_conjugate_with_data — Method

is_conjugate_with_data(Omega::GSet, omega1, omega2)

Determine whether omega1, omega2 are in the same orbit of Omega. If yes, return (true, g) where g is an element in the group G of Omega that maps omega1 to omega2. If not, return (false, nothing). If the conjugating element g is not needed, use is_conjugate.

Examples

julia> G = sylow_subgroup(symmetric_group(6), 2)[1]
Permutation group of degree 6 and order 16

julia> Omega = gset(G);

julia> is_conjugate_with_data(Omega, 1, 2)
(true, (1,2))

julia> is_conjugate_with_data(Omega, 1, 5)
(false, ())

orbit — Method

orbit(Omega::GSet, omega)

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]
Permutation group of degree 6 and order 16

julia> Omega = gset(G, [1, 5]);

julia> length(orbit(Omega, 1))
4

orbit — Method

orbit(G::Union{GAPGroup, FinGenAbGroup}[, 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]
Permutation group of degree 6 and order 16

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::GAPGroup, pnt::Any[, actfun::Function])

Return S, emb where S is 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, and emb is the embedding of S into G.

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

stabilizer — Method

stabilizer(Omega::GSet{T,S})
stabilizer(Omega::GSet{T,S}, omega::S = representative(Omega); check::Bool = true) where {T,S}
stabilizer(Omega::GSet{T,S}, omega::Set{S}; check::Bool = true) where {T,S}
stabilizer(Omega::GSet{T,S}, omega::Vector{S}; check::Bool = true) where {T,S}
stabilizer(Omega::GSet{T,S}, omega::Tuple{S,Vararg{S}}; check::Bool = true) where {T,S}

Return the subgroup of G = acting_group(Omega) that fixes omega, together with the embedding of this subgroup into G.

If omega is a Set of points in Omega then stabilizer means the setwise stabilizer of the entries in omega. If omega is a Vector or a Tuple of points in Omega then stabilizer means the pointwise stabilizer of the entries in omega.

If check is false then it is not checked whether omega is in Omega.

Examples

julia> Omega = gset(symmetric_group(4));

julia> stabilizer(Omega)
(Permutation group of degree 4 and order 6, Hom: permutation group -> Sym(4))

julia> stabilizer(Omega, [1, 2])
(Permutation group of degree 4 and order 2, Hom: permutation group -> Sym(4))