Permutation groups

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)

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.

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

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

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

@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(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(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(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(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(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(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(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(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

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).

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(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)

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

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

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)

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

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

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

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]

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]

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]

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]

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.

is_isomorphic_to_symmetric_group(G::GAPGroup)

Return true if G is isomorphic to a symmetric group, and false otherwise.

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.

is_isomorphic_to_alternating_group(G::GAPGroup)

Return true if G is isomorphic to an alternating group, and false otherwise.

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

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

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

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 $x$ which maps every i from 1 to $n$= length(L) to L$[i]$. The parent of $x$ is G. An exception is thrown if $x$ is not contained in G or L does not contain every integer from 1 to $n$ 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(L::AbstractVector{<:T}...) where T <: IntegerUnion
cperm(G::PermGroup, L::AbstractVector{<:T}...)
cperm(L::Vector{Vector{T}}) where T <: IntegerUnion
cperm(g::PermGroup,L::Vector{Vector{T}}) where T <: IntegerUnion

For given lists $[a_1, a_2, \ldots, a_n], [b_1, b_2, \ldots , b_m], \ldots$ of positive integers, return the permutation $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 $x$ is G. If G is not specified then the parent of $x$ is set to symmetric_group$(n)$, where $n$ is the largest integer that occurs in an entry of L.

An exception is thrown if $x$ is not contained in G or one of the given vectors is empty or contains duplicates.

Examples

julia> cperm([1,2,3],4:7)
(1,2,3)(4,5,6,7)

julia> cperm([1,2],[2,3])
(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

julia> G=symmetric_group(5)
Sym(5)

julia> x = cperm(G,[[1,2],[3,4]])
(1,2)(3,4)

julia> parent(x)
Sym(5)

Equivalent permutations can be created using perm and @perm:

julia> x = cperm([1,2,3],[4,5],[6,7,8])
(1,2,3)(4,5)(6,7,8)

julia> y = perm(symmetric_group(8),[2,3,1,5,4,7,8,6])
(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

At the moment, the input vectors of the function cperm need not be disjoint.

@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)

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

sign(g::PermGroupElem) -> Int

Return the sign of the permutation g.

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

Examples

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

julia> sign(cperm(1:3))
1

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$.

Examples

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

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

julia> isodd(cperm(1:2,3:4))
false

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$.

Examples

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

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

julia> iseven(cperm(1:2,3:4))
true

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

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]

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

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

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

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

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

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]