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
— Functionon_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
— Functionon_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
— Functionpermuted(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
— Functionon_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
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
— Methodgset(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
— Functionpermutation(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
— Methodacting_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
— Methodaction_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
— Methodaction_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
— Methodis_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
— Methodis_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
— Methodorbit(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
— Methodorbit(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
— Methodorbits(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
— Methodstabilizer(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, 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
stabilizer
— Methodstabilizer(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{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))