# Permutation groups

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

`PermGroup`

— Type`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 ] )
```

`PermGroupElem`

— Type`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`

— Function`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
```

`is_natural_symmetric_group`

— Method`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`

— Method`is_isomorphic_with_symmetric_group(G::GAPGroup)`

Return `true`

if `G`

is isomorphic with a symmetric group, and `false`

otherwise.

`alternating_group`

— Function`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
```

`is_natural_alternating_group`

— Method`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`

— Method`is_isomorphic_with_alternating_group(G::GAPGroup)`

Return `true`

if `G`

is isomorphic with an alternating group, and `false`

otherwise.

In OSCAR, every permutation group has a degree `n`

, that corresponds to the size of the set on which `G`

acts.

`degree`

— Method`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.

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

## 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`

— Function`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`

— Function```
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.

`@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( [ 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 ] )
```

The function `Vector{T}`

works in the opposite way with respect to `perm`

:

`Vector`

— Type```
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
```

## Operations on permutations

`sign`

— Method`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`

— Method`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`

— Method`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`

— Method`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
```

## 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
```

## Operations for permutation groups

`is_transitive`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Function`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`

— Method`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]
```