# 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( [ 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 permutation 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 ] )
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( [ 1 .. 5 ] )

julia> order(G)
120

source
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
alternating_groupFunction
alternating_group(n::Int)

Return the full alternating group on the set {1, 2, ..., n}..

Examples

julia> G = alternating_group(5)
Alt( [ 1 .. 5 ] )

julia> order(G)
60

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

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.
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> 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]
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 $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 ] )
source
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
source
cpermFunction
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(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.

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

source

## Operations on permutations

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

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

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

julia> cycle_structure(ans)
1-element Oscar.CycleType:
1 => 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

## Operations for permutation groups

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

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

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

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

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

source