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 — Functionon_tuples(tuple::GAP.GapObj, x::GAPGroupElem)
on_tuples(tuple::Vector, x::GAPGroupElem)
on_tuples(tuple::T, x::GAPGroupElem) where T <: TupleReturn 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 — Functionon_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
2permuted — Functionpermuted(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 — Functionon_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 + x2G-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 — Methodgset(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 — Functionpermutation(Omega::GSetByElements{T}, g::BasicGAPGroupElem{T}) where T<:GAPGroupReturn 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 — Methodaction_homomorphism(Omega::GSetByElements{T}) where T<:GAPGroupReturn 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 = 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
orbit — Methodorbit(Omega::GSet, omega::T) where TReturn 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 — Methodorbit(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 — Methodorbits(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 — Methodstabilizer(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