Permutation groups (PermGroups)

This module is a port of some GAP functionality on permutation groups. A PermGroup is a Group where gens are Perms. It depends on the modules Groups and Perms which could be independent packages on their own.

julia> G=Group([Perm(i,i+1) for i in 1:2])
Group((1,2),(2,3))

julia> collect(G) # PermGroups are iterators over their elements
6-element Vector{Perm{Int16}}:
 ()
 (1,2)
 (1,3,2)
 (2,3)
 (1,2,3)
 (1,3)

julia> last_moved(G)  # maximum moved point of any element of `G`
3

julia> orbits(G) # the orbits are orbits on points it moves
1-element Vector{Vector{Int16}}:
 [1, 2, 3]

julia> Perm(1,2) in G
true

julia> Perm(1,2,4) in G
false

elements, in and other functions are computed on G using Schreier-Sims theory, that is computing the following

julia> get_stabchain(G)
b:1 c:Group((1,2),(2,3))
  δ:1=>(),2=>(1,2),3=>(1,3,2)
b:2 c:Group((2,3))
  δ:2=>(),3=>(2,3)

See Stabchain,stabchain,get_stabchain for explanations.

There are efficient methods for PermGroups for the functions in, length, elements, position_class. The function on_classes determines the permutation of the conjugacy classes effected by an automorphism. Finally, we give application to the group of simultaneous row and column permutations of a matrix: see stab_onmats, Perm.

finally, benchmarks on julia 1.9

julia> @btime collect(symmetric_group(8));
  1.921 ms (50128 allocations: 3.29 MiB)

julia> @btime some_words(symmetric_group(8));
  6.441 ms (80971 allocations: 10.88 MiB)

julia> @btime elements(symmetric_group(8)); # Gap takes 8 ms
  1.565 ms (49539 allocations: 3.71 MiB)

julia> rubik_gens=[
  perm"(1,3,8,6)(2,5,7,4)(9,33,25,17)(10,34,26,18)(11,35,27,19)",
  perm"(9,11,16,14)(10,13,15,12)(1,17,41,40)(4,20,44,37)(6,22,46,35)",
  perm"(17,19,24,22)(18,21,23,20)(6,25,43,16)(7,28,42,13)(8,30,41,11)",
  perm"(25,27,32,30)(26,29,31,28)(3,38,43,19)(5,36,45,21)(8,33,48,24)",
  perm"(33,35,40,38)(34,37,39,36)(3,9,46,32)(2,12,47,29)(1,14,48,27)",
  perm"(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)"];

julia> @btime length(Int128,Group(rubik_gens)) # Gap takes 5ms
  4.906 ms (104874 allocations: 13.64 MiB)
43252003274489856000

Note the use of Int128 in length: the computation does not fit in an Int64.

last_moved(a::Perm) is the largest integer moved by a

last_moved(G::PermGroup) the largest moved point by any g∈ G

first_moved(a::Perm) is the smallest integer moved by a

first_moved(G::PermGroup) the smallest moved point by any g∈ G

x in G for G a group: whether x is an element of G

A Stabchain is a Vector{Stablink} S=[S₁,…,Sₖ] associated to a PermGroup{T} G. The Vector{T} given by B=[S₁.b,…,Sₖ.b] is called a base for G. At each stage one has Sᵢ.c=C_G(B[1:i-1]) and Sᵢ.δ=transversal(Sᵢ.c,Sᵢ.b)

stabchain(G::PermGroup{T},B=T[];trans=transversal)where T

Constructs a Stabchain for G [starting with base B]

The code refers to the Handbook of computational group theory, by Holt, Eick, O'Brien, section 4.4.2.

trans could be SchreierTransversal.

This function adds to G a stabchain

on_classes(G, aut)

aut is an automorphism of the group G (for a permutation group, this could be given as a permutation normalizing G). The result is the permutation of 1:nconjugacy_classes(G) induced by aut.

julia> W=Group(Perm(1,2),Perm(2,3),Perm(4,5),Perm(5,6))
Group((1,2),(2,3),(4,5),(5,6))

julia> on_classes(W,Perm(1,4,2,5,3,6))
(2,4)(3,7)(6,8)

symmetric_group(n::Int) The symmetric group of degree n

onmats(m::AbstractMatrix,g::Perm) synonym for invpermute(m,g;dims=(1,2)) or invpermute(m,g,g).

stab_onmats([G,]M;extra=nothing)

If onmats(m,p)=^(M,p;dims=(1,2)), and the argument G is given (which should be a PermGroup) this is just a fast implementation of centralizer(G,M,onmats). If G is omitted it is taken to be symmetric_group(size(M,1)). The program uses sophisticated algorithms, and can handle matrices up to 80×80. If a list extra is given the result centralizes also extra.

julia> stab_onmats((1:30)'.*(1:30).%15)
Group((1,16),(4,19),(11,26),(14,29),(2,17),(7,22),(8,23),(13,28),(6,21),(9,24),(1,4)(2,8)(3,12)(6,9)(7,13)(11,14)(16,19)(17,23)(18,27)(21,24)(22,28)(26,29),(3,18),(12,27),(1,11)(2,7)(4,14)(5,10)(8,13)(16,26)(17,22)(19,29)(20,25)(23,28),(5,20),(10,25),(15,30))

Perm_onmats(M, N[, m ,n])

returns p such that onmats(N,p)=M if it exists, nothing otherwise; so is just an efficient version of transporting_elt(symmetric_group(size(M,1)),N,M,onmats) If in addition the vectors m and n are given, p should satisfy invpermute(n,p)=m.

A ProdIterator([i₁,…,iₙ]) takes a list i₁,…,iₙ of iterators and iterates on all the products i₁[j₁]*…*iₙ[jₙ] (where the inner loop jₙ runs the fastest). It tries to be fast by re-using partial products i₁[j₁]*…*iₖ[jₖ] for k<n.

It is used internally for iterating over a permutation group.