Permutation groups

PermGroup

Groups of permutations. Every group of this type is the 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 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( [ 1 .. 5 ] )

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

julia> parent(x)
Sym( [ 1 .. 3 ] )

julia> y=G(x)
(1,2,3)

julia> parent(y)
Sym( [ 1 .. 5 ] )

If G is a group and L 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( [ 1 .. 6 ] )

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

julia> parent(x)
Sym( [ 1 .. 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(::Type{T} = PermGroup, n::Int)

Return the full symmetric group on the set {1, 2, ..., n}, as an instance of T, where T is in {PermGroup, PcGroup}.

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_with_symmetric_group(G::GAPGroup)

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

alternating_group(::Type{T} = PermGroup, n::Int)

Return the full alternating group on the set {1, 2, ..., n}, as an instance of T, where T is in {PermGroup, PcGroup}.

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_with_alternating_group(G::GAPGroup)

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

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.

Examples

julia> degree(symmetric_group(4))
4

julia> t4 = trivial_subgroup(symmetric_group(4))[1];

julia> degree(t4)
4

julia> t4 == trivial_subgroup(symmetric_group(5))[1]
false

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]

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

julia> degree(parent(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( [ 1 .. 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( [ 1 .. 5 ] )

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

julia> parent(x)
Sym( [ 1 .. 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( [ 1 .. 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( [ 1 .. 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{fmpz}(pi, 2)
2-element Vector{fmpz}:
 2
 3

sign(g::PermGroupElem)

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)

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

julia> cycle_structure(ans)
1-element Oscar.CycleType:
 1 => 1

is_transitive(G::PermGroup, L::AbstractVector{Int} = 1:degree(G))

Return whether the action of G on L is transitive.

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 the action of G on L is k-transitive. The output is 0 if G is not transitive on L.

Examples

julia> transitivity(mathieu_group(24))
5

julia> transitivity(symmetric_group(6))
6

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, maximal_subgroup_reps(G))
3-element Vector{PermGroup}:
 Group([ (1,2)(3,4), (1,2)(5,6), (1,3,5)(2,4,6), (1,3)(2,4) ])
 Group([ (1,2,3), (4,5,6), (1,2)(4,5), (1,5,2,4)(3,6) ])
 PSL(2,5)

julia> [(order(H), is_primitive(H)) for H in mx]
3-element Vector{Tuple{fmpz, 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]
Group([ (1,2,3,4,5,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]
Group([ (1,2,3)(4,5,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 Peter J. Cameron (1999) 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]
Group([ (1,2), (3,4), (1,3)(2,4) ])

julia> rank_action(H)  # not 2-transitive
3

julia> K = stabilizer(G, 1)[1]
Group([ (2,4,3), (3,4) ])

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

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)
4[x]2

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)
4[x]2

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)
4[x]2

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]