Permutation groups

Constructing permutation groups

Permutation groups can be defined as symmetric groups, alternating groups or their subgroups.

PermGroupType
PermGroup

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 order n as a group of permutations. Same holds replacing dihedral_group by quaternion_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)
source
PermGroupElemType
PermGroupElem

Element of a group of permutations. It is displayed as product of disjoint cycles.

Assumptions:

  • for x,y in Sym(n), the product xy is read from left to right;
  • for x in Sym(n) and i in {1,...,n}, i^x and x(i) return the image of i under the action of x.
source
symmetric_groupFunction
symmetric_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
source
alternating_groupFunction
alternating_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
source
permutation_groupFunction
permutation_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
source
@permutation_groupMacro
@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
source
projective_general_linear_groupFunction
projective_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
source
projective_special_linear_groupFunction
projective_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
source
projective_symplectic_groupFunction
projective_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
source
projective_orthogonal_groupFunction
projective_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
source
projective_special_orthogonal_groupFunction
projective_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
source
projective_omega_groupFunction
projective_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
source
projective_unitary_groupFunction
projective_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
source
projective_special_unitary_groupFunction
projective_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
source

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.

degreeMethod
degree(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 into symmetric_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 which G and its element acts.
  • One can use the syntax G(H) in order to get a group that consists of the same permutations as H but has the same degree as G, provided that the elements of H move only points up to degree(G).
Note

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]
source
smaller_degree_permutation_representationMethod
smaller_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)
source

The following functions deal with the natural action of a given permutation group GG.

is_transitiveFunction
is_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
source
transitivityFunction
transitivity(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
source
is_primitiveFunction
is_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)
source
is_regularFunction
is_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
source
is_semiregularFunction
is_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
source
rank_actionFunction
rank_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
source
blocksFunction
blocks(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]
source
maximal_blocksFunction
maximal_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]
source
minimal_block_repsFunction
minimal_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]
source
all_blocksMethod
all_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]
source

The following functions allow efficiently "recognizing" certain permutation groups as alternating or symmetric groups.

is_natural_symmetric_groupMethod
is_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.

source
is_natural_alternating_groupMethod
is_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.

source

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.

permFunction
perm(L::AbstractVector{<:IntegerUnion})

Return the permutation xx which maps every ii from 1 to nn= length(L) to L[i][i]. The parent of xx is set to symmetric_group(n)(n). An exception is thrown if L does not contain every integer from 1 to nn exactly once.

The parent group of xx is set to symmetric_group(n)(n).

Examples

julia> x = perm([2,4,6,1,3,5])
(1,2,4)(3,6,5)

julia> parent(x)
Sym(6)
source
perm(G::PermGroup, L::AbstractVector{<:IntegerUnion})
(G::PermGroup)(L::AbstractVector{<:IntegerUnion})

Return the permutation xx which maps every i from 1 to nn= length(L) to L[i][i]. The parent of xx is G. An exception is thrown if xx is not contained in G or L does not contain every integer from 1 to nn 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
source
cpermFunction
cperm(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 [a1,a2,,an],[b1,b2,,bm],[a_1, a_2, \ldots, a_n], [b_1, b_2, \ldots , b_m], \ldots of positive integers, return the permutation x=(a1,a2,,an)(b1,b2,,bm)x = (a_1, a_2, \ldots, a_n) * (b_1, b_2, \ldots, b_m) * \ldots. Arrays of the form [n, n+1, ..., n+k] can be replaced by n:n+k.

The parent of xx is G. If G is not specified then the parent of xx is set to symmetric_group(n)(n), where nn 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 xx 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
source
@permMacro
@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
source
@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)
source

The function Vector{T} works in the opposite way with respect to perm:

VectorType
Vector{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
source

Operations on permutations

signMethod
sign(g::PermGroupElem) -> Int

Return the sign of the permutation g.

The sign of a permutation gg is defined as (1)k(-1)^k where kk is the number of cycles of gg of even length.

Examples

julia> sign(cperm(1:2))
-1

julia> sign(cperm(1:3))
1
source
isoddMethod
isodd(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 1-1.

Examples

julia> isodd(cperm(1:2))
true

julia> isodd(cperm(1:3))
false

julia> isodd(cperm(1:2,3:4))
false
source
isevenMethod
iseven(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 +1+1.

Examples

julia> iseven(cperm(1:2))
false

julia> iseven(cperm(1:3))
true

julia> iseven(cperm(1:2,3:4))
true
source
cycle_structureMethod
cycle_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
source
cyclesMethod
cycles(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]
source

Permutations as functions

A permutation can be viewed as a function on the set {1,...,n}, hence it can be evaluated on integers.

Note

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.

degreeMethod
degree(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
source
isevenMethod
iseven(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
source
isoddMethod
isodd(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
source
orderMethod
order(::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
source
signMethod
sign(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
source
cycle_structuresMethod
cycle_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]
source