Permutation groups
Constructing permutation groups
Permutation groups can be defined as symmetric groups, alternating groups or their subgroups.
PermGroup
— TypePermGroup
Groups of permutations. Every group of this type is a subgroup of Sym(n) for some n.
Examples
symmetric_group(n::Int)
: the symmetric group Sym(n)alternating_group(n::Int)
: the alternating group Alt(n)- subgroups of Sym(n)
dihedral_group(PermGroup, n::Int)
: the dihedral group of ordern
as a group of permutations. Same holds replacingdihedral_group
byquaternion_group
If G
is a permutation group and x
is a permutation, G(x)
returns a permutation x
with parent G
; an exception is thrown if x
does not embed into G
.
julia> G=symmetric_group(5)
Sym(5)
julia> x=cperm([1,2,3])
(1,2,3)
julia> parent(x)
Sym(3)
julia> y=G(x)
(1,2,3)
julia> parent(y)
Sym(5)
If G
is a permutation group and x
is a vector of integers, G(x)
returns a PermGroupElem
with parent G
; an exception is thrown if the element does not embed into G
.
Examples
julia> G = symmetric_group(6)
Sym(6)
julia> x = G([2,4,6,1,3,5])
(1,2,4)(3,6,5)
julia> parent(x)
Sym(6)
PermGroupElem
— TypePermGroupElem
Element of a group of permutations. It is displayed as product of disjoint cycles.
Assumptions:
- for
x
,y
in Sym(n), the productxy
is read from left to right; - for
x
in Sym(n) andi
in {1,...,n},i^x
andx(i)
return the image ofi
under the action ofx
.
symmetric_group
— Functionsymmetric_group(n::Int)
Return the full symmetric group on the set {1, 2, ..., n}
.
Examples
julia> G = symmetric_group(5)
Sym(5)
julia> order(G)
120
alternating_group
— Functionalternating_group(n::Int)
Return the full alternating group on the set {1, 2, ..., n}
..
Examples
julia> G = alternating_group(5)
Alt(5)
julia> order(G)
60
permutation_group
— Functionpermutation_group(n::IntegerUnion, perms::Vector{PermGroupElem})
Return the permutation group of degree n
that is generated by the elements in perms
.
Examples
julia> x = cperm([1,2,3], [4,5]); y = cperm([1,4]);
julia> permutation_group(5, [x, y])
Permutation group of degree 5
@permutation_group
— Macro@permutation_group(n, gens...)
Input the permutation group of degree n
with generators gens...
, given by permutations in cycle notation.
Examples
julia> g = @permutation_group(7, (1,2), (1,2,3)(4,5))
Permutation group of degree 7
julia> degree(g)
7
projective_general_linear_group
— Functionprojective_general_linear_group(n::Int, q::Int)
Return the factor group of general_linear_group
, called with the same parameters, by its scalar matrices. The group is represented as a permutation group.
Examples
julia> g = projective_general_linear_group(2, 3)
Permutation group of degree 4 and order 24
julia> order(g)
24
projective_special_linear_group
— Functionprojective_special_linear_group(n::Int, q::Int)
Return the factor group of special_linear_group
, called with the same parameters, by its scalar matrices. The group is represented as a permutation group.
Examples
julia> g = projective_special_linear_group(2, 3)
Permutation group of degree 4 and order 12
julia> order(g)
12
projective_symplectic_group
— Functionprojective_symplectic_group(n::Int, q::Int)
Return the factor group of symplectic_group
, called with the same parameters, by its scalar matrices. The group is represented as a permutation group.
Examples
julia> g = projective_symplectic_group(2, 3)
Permutation group of degree 4 and order 12
julia> order(g)
12
projective_orthogonal_group
— Functionprojective_orthogonal_group(e::Int, n::Int, q::Int)
Return the factor group of orthogonal_group
, called with the same parameters, by its scalar matrices.
As for orthogonal_group
, e
can be omitted if n
is odd.
Examples
julia> g = projective_orthogonal_group(1, 4, 3); order(g)
576
julia> g = projective_orthogonal_group(3, 3); order(g)
24
projective_special_orthogonal_group
— Functionprojective_special_orthogonal_group(e::Int, n::Int, q::Int)
Return the factor group of special_orthogonal_group
, called with the same parameters, by its scalar matrices.
As for special_orthogonal_group
, e
can be omitted if n
is odd.
Examples
julia> g = projective_special_orthogonal_group(1, 4, 3); order(g)
288
julia> g = projective_special_orthogonal_group(3, 3); order(g)
24
projective_omega_group
— Functionprojective_omega_group(e::Int, n::Int, q::Int)
Return the factor group of omega_group
, called with the same parameters, by its scalar matrices.
As for omega_group
, e
can be omitted if n
is odd.
Examples
julia> g = projective_omega_group(1, 4, 3); order(g)
144
julia> g = projective_omega_group(3, 3); order(g)
12
projective_unitary_group
— Functionprojective_unitary_group(n::Int, q::Int)
Return the factor group of unitary_group
, called with the same parameters, by its scalar matrices. The group is represented as a permutation group.
Examples
julia> g = projective_unitary_group(2, 3)
Permutation group of degree 10 and order 24
julia> order(g)
24
projective_special_unitary_group
— Functionprojective_special_unitary_group(n::Int, q::Int)
Return the factor group of special_unitary_group
, called with the same parameters, by its scalar matrices. The group is represented as a permutation group.
Examples
julia> g = projective_special_unitary_group(2, 3)
Permutation group of degree 10 and order 12
julia> order(g)
12
Operations for permutation groups
All operations, properties and attributes for general groups described in the previous sections are supported for permutation groups. In addition there are some specific to permutation groups.
In OSCAR, every permutation group has a degree n
, that corresponds to the size of the set on which G
acts.
degree
— Methoddegree(G::PermGroup) -> Int
Return the degree of G
as a permutation group, that is, an integer n
that is stored in G
, with the following meaning.
G
embeds intosymmetric_group(n)
.- Two permutation groups of different degrees are regarded as not equal, even if they contain the same permutations.
- Subgroups constructed with
derived_subgroup
,sylow_subgroup
, etc., get the same degree as the given group. - The range
1:degree(G)
is used as the default set of points on whichG
and its element acts. - One can use the syntax
G(H)
in order to get a group that consists of the same permutations asH
but has the same degree asG
, provided that the elements ofH
move only points up todegree(G)
.
The degree of a group of permutations is not necessarily equal to the largest moved point of the group G
. For example, the trivial subgroup of symmetric_group(n)
has degree n
even though it fixes n
.
Examples
julia> s4 = symmetric_group(4);
julia> degree(s4)
4
julia> t4 = trivial_subgroup(symmetric_group(4))[1];
julia> degree(t4)
4
julia> t5 = trivial_subgroup(symmetric_group(5))[1];
julia> t4 == t5
false
julia> t4 == s4(t5)
true
julia> show(Vector(gen(symmetric_group(4), 2)))
[2, 1, 3, 4]
julia> show(Vector(gen(symmetric_group(5), 2)))
[2, 1, 3, 4, 5]
smaller_degree_permutation_representation
— Methodsmaller_degree_permutation_representation(G::PermGroup) -> PermGroup, map
Return an isomorphic permutation group of smaller or equal degree and the isomorphism from G
to that group.
Examples
julia> g = symmetric_group(4);
julia> s, _ = sylow_subgroup(g, 3);
julia> rho = smaller_degree_permutation_representation(s)
(Permutation group of degree 3 and order 3, Hom: s -> permutation group)
The following functions deal with the natural action of a given permutation group .
is_transitive
— Functionis_transitive(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return whether G
acts transitively on L
, that is, L
is an orbit of G
.
Examples
julia> G = symmetric_group(6);
julia> is_transitive(G)
true
julia> is_transitive(sylow_subgroup(G, 2)[1])
false
julia> is_transitive(stabilizer(G, 1)[1])
false
transitivity
— Functiontransitivity(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return the maximum k
such that G
acts k
-transitively on L
, that is, every k
-tuple of points in L
can be mapped simultaneously to every other k
-tuple by an element of G
.
The output is 0
if G
acts intransitively on L
, and an exception is thrown if G
does not act on L
.
Examples
julia> transitivity(mathieu_group(24))
5
julia> transitivity(symmetric_group(6))
6
julia> transitivity(symmetric_group(6), 1:7)
0
julia> transitivity(symmetric_group(6), 1:5)
ERROR: ArgumentError: the group does not act
is_primitive
— Functionis_primitive(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return whether the action of G
on L
is primitive, that is, the action is transitive and the point stabilizers are maximal in G
.
Examples
julia> G = alternating_group(6);
julia> mx = filter(is_transitive, map(representative, maximal_subgroup_classes(G)))
3-element Vector{PermGroup}:
Permutation group of degree 6 and order 24
Permutation group of degree 6 and order 36
Permutation group of degree 6 and order 60
julia> [(order(H), is_primitive(H)) for H in mx]
3-element Vector{Tuple{ZZRingElem, Bool}}:
(24, 0)
(36, 0)
(60, 1)
is_regular
— Functionis_regular(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return whether the action of G
on L
is regular (i.e., transitive and semiregular).
Examples
julia> G = symmetric_group(6);
julia> H = sub(G, [G([2, 3, 4, 5, 6, 1])])[1]
Permutation group of degree 6
julia> is_regular(H)
true
julia> is_regular(G)
false
is_semiregular
— Functionis_semiregular(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return whether the action of G
on L
is semiregular (i.e., the stabilizer of each point is the identity).
Examples
julia> G = symmetric_group(6);
julia> H = sub(G, [G([2, 3, 1, 5, 6, 4])])[1]
Permutation group of degree 6
julia> is_semiregular(H)
true
julia> is_regular(H)
false
rank_action
— Functionrank_action(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))
Return the rank of the transitive action of G
on L
. This is defined as the number of G
-orbits in the action on ordered pairs of points in L
, and is equal to the number of orbits of the stabilizer of a point in L
on L
, see [Cam99] Section 1.11.
An exception is thrown if G
is not transitive on L
.
Examples
julia> G = symmetric_group(4); rank_action(G) # 4-transitive
2
julia> H = sylow_subgroup(G, 2)[1]
Permutation group of degree 4 and order 8
julia> rank_action(H) # not 2-transitive
3
julia> K = stabilizer(G, 1)[1]
Permutation group of degree 4 and order 6
julia> rank_action(K, 2:4) # 2-transitive
2
julia> rank_action(K, 3:5)
ERROR: ArgumentError: the group is not transitive
blocks
— Functionblocks(G::PermGroup, L::AbstractVector{Int} = moved_points(G))
Return a G-set that is a block system for the action of G
on L
, i.e., a non-trivial partition of L
preserved by the action of G
.
Here, L
must be a subvector of 1:degree(G)
on which G
acts transitively. G
may move points outside L
, in this case the restriction of the action of the set stabilizer of L
in G
to L
is considered.
An exception is thrown if this action is not transitive.
Examples
julia> g = sylow_subgroup(symmetric_group(4), 2)[1]
Permutation group of degree 4 and order 8
julia> collect(blocks(g))
2-element Vector{Vector{Int64}}:
[1, 2]
[3, 4]
maximal_blocks
— Functionmaximal_blocks(G::PermGroup, L::AbstractVector{Int} = moved_points(G))
Return a G-set that is a maximal block system for the action of G
on L
, i.e., a maximal non-trivial partition of L
preserved by the action of G
.
Here, L
must be a subvector of 1:degree(G)
on which G
acts transitively. G
may move points outside L
, in this case the restriction of the action of the set stabilizer of L
in G
to L
is considered.
An exception is thrown if this action is not transitive.
Examples
julia> G = transitive_group(8, 2)
Permutation group of degree 8
julia> collect(maximal_blocks(G))
2-element Vector{Vector{Int64}}:
[1, 2, 3, 8]
[4, 5, 6, 7]
minimal_block_reps
— Functionminimal_block_reps(G::PermGroup, L::AbstractVector{Int} = moved_points(G))
Return a vector of block representatives for all minimal non-trivial block systems for the action of G
on L
.
Here, L
must be a subvector of 1:degree(G)
on which G
acts transitively. G
may move points outside L
, in this case the restriction of the action of the set stabilizer of L
in G
to L
is considered.
An exception is thrown if this action is not transitive.
Examples
julia> G = transitive_group(8, 2)
Permutation group of degree 8
julia> minimal_block_reps(G)
3-element Vector{Vector{Int64}}:
[1, 3]
[1, 5]
[1, 7]
all_blocks
— Methodall_blocks(G::PermGroup)
Return a vector of smallest representatives of all block systems for the action of G
on the set of moved points of G
.
Examples
julia> G = transitive_group(8, 2)
Permutation group of degree 8
julia> all_blocks(G)
6-element Vector{Vector{Int64}}:
[1, 2, 3, 8]
[1, 5]
[1, 3, 5, 7]
[1, 3]
[1, 3, 4, 6]
[1, 7]
The following functions allow efficiently "recognizing" certain permutation groups as alternating or symmetric groups.
is_natural_symmetric_group
— Methodis_natural_symmetric_group(G::GAPGroup)
Return true
if G
is a permutation group acting as the symmetric group on its moved points, and false
otherwise.
is_isomorphic_to_symmetric_group
— Methodis_isomorphic_to_symmetric_group(G::GAPGroup)
Return true
if G
is isomorphic to a symmetric group, and false
otherwise.
is_natural_alternating_group
— Methodis_natural_alternating_group(G::GAPGroup)
Return true
if G
is a permutation group acting as the alternating group on its moved points, and false
otherwise.
is_isomorphic_to_alternating_group
— Methodis_isomorphic_to_alternating_group(G::GAPGroup)
Return true
if G
is isomorphic to an alternating group, and false
otherwise.
Permutations
Permutations in OSCAR are displayed as products of disjoint cycles, as in GAP. An explicit permutation can be built using the functions perm
, cperm
, or @perm
.
perm
— Functionperm(L::AbstractVector{<:IntegerUnion})
Return the permutation which maps every from 1
to = length(L)
to L
. The parent of is set to symmetric_group
. An exception is thrown if L
does not contain every integer from 1 to exactly once.
The parent group of is set to symmetric_group
.
Examples
julia> x = perm([2,4,6,1,3,5])
(1,2,4)(3,6,5)
julia> parent(x)
Sym(6)
perm(G::PermGroup, L::AbstractVector{<:IntegerUnion})
(G::PermGroup)(L::AbstractVector{<:IntegerUnion})
Return the permutation which maps every i
from 1 to = length(L)
to L
. The parent of is G
. An exception is thrown if is not contained in G
or L
does not contain every integer from 1 to exactly once.
Examples
julia> perm(symmetric_group(6),[2,4,6,1,3,5])
(1,2,4)(3,6,5)
Equivalent permutations can be created using cperm
and @perm
julia> x = perm(symmetric_group(8),[2,3,1,5,4,7,8,6])
(1,2,3)(4,5)(6,7,8)
julia> y = cperm([1,2,3],[4,5],[6,7,8])
(1,2,3)(4,5)(6,7,8)
julia> x == y
true
julia> z = @perm (1,2,3)(4,5)(6,7,8)
(1,2,3)(4,5)(6,7,8)
julia> x == z
true
cperm
— Functioncperm(L::AbstractVector{<:T}...) where T <: IntegerUnion
cperm(L::AbstractVector{<:AbstractVector{T}}) where T <: IntegerUnion
cperm(G::PermGroup, L::AbstractVector{<:T}...)
cperm(G::PermGroup, L::AbstractVector{<:AbstractVector{T}}) where T <: IntegerUnion
For given lists of positive integers, return the permutation . Arrays of the form [n, n+1, ..., n+k]
can be replaced by n:n+k
.
The parent of is G
. If G
is not specified then the parent of is set to symmetric_group
, where is the largest integer that occurs in an entry of L
. However this incurs non-trivial overhead and so it is generally better to provide G
explicitly.
An exception is thrown if is not contained in G
, or one of the given vectors is empty or contains duplicates.
See also perm
and @perm
for other ways to create permutations.
Examples
julia> cperm([1,2,3],4:7)
(1,2,3)(4,5,6,7)
julia> cperm([1,2],[2,3]) # cycles may overlap
(1,3,2)
julia> cperm()
()
julia> p = cperm([1,2,3],[7])
(1,2,3)
julia> degree(p)
7
Two permutations coincide if, and only if, they move the same points and their parent groups have the same degree.
julia> G = symmetric_group(5);
julia> A = alternating_group(5);
julia> x = cperm(G, [1,2,3]);
julia> y = cperm(A, [1,2,3]);
julia> z = cperm([1,2,3]); parent(z)
Sym(3)
julia> x == y
true
julia> x == z
false
In the example above, x
and y
are equal because both act on a set of cardinality 5
, while x
and z
are different because x
belongs to Sym(5)
and z
belongs to Sym(3)
.
cperm
can also handle cycles passed in inside of a vector
julia> x = cperm([[1,2],[3,4]])
(1,2)(3,4)
julia> y = cperm([1,2],[3,4])
(1,2)(3,4)
julia> x == y
true
@perm
— Macro@perm ex
Input a permutation in cycle notation. Supports arbitrary expressions for generating the integer entries of the cycles. The parent group is inferred to be the symmetric group with a degree of the highest integer referenced in the permutation.
The actual work is done by cperm
. Thus, for the time being, cycles which are not disjoint actually are supported.
Examples
julia> x = @perm (1,2,3)(4,5)(factorial(3),7,8)
(1,2,3)(4,5)(6,7,8)
julia> parent(x)
Sym(8)
julia> y = cperm([1,2,3],[4,5],[6,7,8])
(1,2,3)(4,5)(6,7,8)
julia> x == y
true
julia> z = perm(symmetric_group(8),[2,3,1,5,4,7,8,6])
(1,2,3)(4,5)(6,7,8)
julia> x == z
true
@perm n gens
Input a list of permutations in cycle notation, created as elements of the symmetric group of degree n
, i.e., symmetric_group(n)
, by invoking cperm
suitably.
Examples
julia> gens = @perm 14 [
(1,10)
(2,11)
(3,12)
(4,13)
(5,14)
(6,8)
(7,9)
(1,2,3,4,5,6,7)(8,9,10,11,12,13,14)
(1,2)(10,11)
]
9-element Vector{PermGroupElem}:
(1,10)
(2,11)
(3,12)
(4,13)
(5,14)
(6,8)
(7,9)
(1,2,3,4,5,6,7)(8,9,10,11,12,13,14)
(1,2)(10,11)
julia> parent(gens[1])
Sym(14)
The function Vector{T}
works in the opposite way with respect to perm
:
Vector
— TypeVector{T}(x::PermGroupElem, n::Int = x.parent.deg) where T <: IntegerUnion
Vector(x::PermGroupElem, n::Int = x.parent.deg)
Return the list of length n
that contains x(i)
at position i
. If not specified, T
is set as Int
.
Examples
julia> pi = cperm(1:3)
(1,2,3)
julia> Vector(pi)
3-element Vector{Int64}:
2
3
1
julia> Vector(pi, 2)
2-element Vector{Int64}:
2
3
julia> Vector(pi, 4)
4-element Vector{Int64}:
2
3
1
4
julia> Vector{ZZRingElem}(pi, 2)
2-element Vector{ZZRingElem}:
2
3
Operations on permutations
sign
— Methodsign(g::PermGroupElem) -> Int
Return the sign of the permutation g
.
The sign of a permutation is defined as where is the number of cycles of of even length.
Examples
julia> sign(cperm(1:2))
-1
julia> sign(cperm(1:3))
1
isodd
— Methodisodd(g::PermGroupElem)
Return true
if the permutation g
is odd, false
otherwise.
A permutation is odd if it has an odd number of cycles of even length. Equivalently, a permutation is odd if it has sign .
Examples
julia> isodd(cperm(1:2))
true
julia> isodd(cperm(1:3))
false
julia> isodd(cperm(1:2,3:4))
false
iseven
— Methodiseven(g::PermGroupElem)
Return true
if the permutation g
is even, false
otherwise.
A permutation is even if it has an even number of cycles of even length. Equivalently, a permutation is even if it has sign .
Examples
julia> iseven(cperm(1:2))
false
julia> iseven(cperm(1:3))
true
julia> iseven(cperm(1:2,3:4))
true
cycle_structure
— Methodcycle_structure(g::PermGroupElem) -> CycleType
Return the cycle structure of the permutation g
as a cycle type. A cycle type behaves similar to a vector of pairs k => n
indicating that there are n
cycles of length k
.
Examples
julia> g = cperm(1:3, 4:5, 6:7, 8:10, 11:15)
(1,2,3)(4,5)(6,7)(8,9,10)(11,12,13,14,15)
julia> cycle_structure(g)
3-element Oscar.CycleType:
2 => 2
3 => 2
5 => 1
julia> g = cperm()
()
julia> cycle_structure(g)
1-element Oscar.CycleType:
1 => 1
cycles
— Methodcycles(g::PermGroupElem)
Return all cycles (including trivial ones) of the permutation g
as a sorted list of integer vectors.
Examples
julia> g = cperm(1:3, 6:7, 8:10, 11:15)
(1,2,3)(6,7)(8,9,10)(11,12,13,14,15)
julia> cycles(g)
6-element Vector{Vector{Int64}}:
[1, 2, 3]
[4]
[5]
[6, 7]
[8, 9, 10]
[11, 12, 13, 14, 15]
julia> g = cperm()
()
julia> cycles(g)
1-element Vector{Vector{Int64}}:
[1]
Permutations as functions
A permutation can be viewed as a function on the set {1,...,n}
, hence it can be evaluated on integers.
The multiplication between permutations works from the left to the right. So, if x
and y
are permutations and n
is an integer, then (x*y)(n) = (y(x(n))
, NOT x(y(n))
. This works also if the argument is not in the range 1:n
; in such a case, the output coincides with the input.
julia> x = cperm([1,2,3,4,5]);
julia> x(2)
3
julia> x(6)
6
Cycle structures
For a permutation, its cycle structure cycle_structure
determines the degree, order, number of moved points, sign.
degree
— Methoddegree(c::CycleType) -> Int
Return the degree of the permutations with cycle structure c
.
Examples
julia> g = symmetric_group(3);
julia> all(x -> degree(cycle_structure(x)) == degree(g), gens(g))
true
iseven
— Methodiseven(c::CycleType) -> Bool
Return whether the permutations with cycle structure c
are even.
Examples
julia> g = symmetric_group(3);
julia> all(x -> iseven(cycle_structure(x)) == iseven(x), gens(g))
true
isodd
— Methodisodd(c::CycleType) -> Bool
Return whether the permutations with cycle structure c
are odd.
Examples
julia> g = symmetric_group(3);
julia> all(x -> isodd(cycle_structure(x)) == isodd(x), gens(g))
true
order
— Methodorder(::Type{T} = ZZRingElem, c::CycleType) where T <: IntegerUnion
Return the order of the permutations with cycle structure c
.
Examples
julia> g = symmetric_group(3);
julia> all(x -> order(cycle_structure(x)) == order(x), gens(g))
true
sign
— Methodsign(c::CycleType) -> Int
Return the sign of the permutations with cycle structure c
.
Examples
julia> g = symmetric_group(3);
julia> all(x -> sign(cycle_structure(x)) == sign(x), gens(g))
true
cycle_structures
— Methodcycle_structures(G::PermGroup) -> Set{CycleType}
Return the set of cycle structures of elements in G
, see cycle_structure
.
Examples
julia> g = symmetric_group(3);
julia> sort!(collect(cycle_structures(g)))
3-element Vector{Oscar.CycleType}:
[1 => 1, 2 => 1]
[1 => 3]
[3 => 1]