Groups

This module gives some basic functionality on groups.

Group is an abstract type, but the following is assumed of a concrete implementation of a group:

• The function generators(G) returns the list of generators of G (this can also be abbreviated gens(G)).
• The function one(G) returns the identity element of G.

There is a constructor of a group with arbitrary type elements, Group(l) where l isa AbstractVector{T} constructs a Groupof{T} which knows only the general methods in this module.

Examples

julia> G=Group([-1]) # the group (of order 2) generated by -1
Group([-1])

julia> generators(G), number_of_generators(G)
([-1], 1)

julia> minimal_words(G)
OrderedDict{Int64, Vector{Int64}} with 2 entries:
  1  => []
  -1 => [1]

The next example uses Group(AbstractVector{<:Perm}) which constructs a PermGroup which has more efficient methods.

julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))

julia> gens(G) # same as generators
2-element Vector{Perm{Int16}}:
 (1,2)
 (1,2,3)

julia> ngens(G) # same as number_of_generators
2

julia> minimal_words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
  ()      => []
  (1,2)   => [1]
  (1,2,3) => [2]
  (1,3)   => [1, 2]
  (2,3)   => [2, 1]
  (1,3,2) => [2, 2]

Actions

Some functions like orbit take as argument an action which describes how the group argument operates. Example of actions are

• '^', the default. For a point p and a permutation g, p^g is the image of p by g. For two elements of a group g1^g2 is conjugacy inv(g2)*g1*g2.

julia> orbits(G,1:3)
1-element Vector{Vector{Int64}}:
 [1, 2, 3]

julia> orbits(G,elements(G)) # the conjugacy classes of G
3-element Vector{Vector{Perm{Int16}}}:
 [()]
 [(2,3), (1,3), (1,2)]
 [(1,2,3), (1,3,2)]

• ontuples(p,g) is `p.^g'

julia> orbits(G,[[1,2]],ontuples)
1-element Vector{Vector{Vector{Int64}}}:
 [[1, 2], [2, 1], [2, 3], [3, 2], [1, 3], [3, 1]]

• onsets(p,g) assume that p is a set, represented as a sorted list without repetitions. onsets is the action of g given by (p,g)->sort!(p.^g).

julia> orbits(G,[[1,2]],onsets)
1-element Vector{Vector{Vector{Int64}}}:
 [[1, 2], [2, 3], [1, 3]]

• onmats(m,g) is the action of the permutation g by simultaneous permutation of the rows and columns of the matrix m.

julia> m=[1 2 3;2 3 2;3 2 1]
3×3 Matrix{Int64}:
 1  2  3
 2  3  2
 3  2  1

julia> orbit(G,m,onmats)
3-element Vector{Matrix{Int64}}:
 [1 2 3; 2 3 2; 3 2 1]
 [3 2 2; 2 1 3; 2 3 1]
 [1 3 2; 3 1 2; 2 2 3]

for more information on the functions defined in this module, look at Group, comm, orbit, orbits, transversal, words_transversal, centralizer, stabilizer, center, normalizer, some_words, minimal_words, word, in, elements, length, order, conjugacy_class, conjugacy_classes, classreps, number_of_conjugacy_classes, fusion_conjugacy_classes, position_class, isabelian, iscyclic, istrivial, rand, transporting_element, intersect, Hom, kernel, Coset, NormalCoset

(G::Group)(i...)

A Group used as a function takes integer arguments in eachindex(gens(W)). This constructs the element of G product of the generators with the specified indices. An argument can also be negative, then the inverse of the corresponding generator is used.

julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))

julia> G(2,1,-2) # returns gens(G)[2]*gens(G)[1]/gens(G)[2]
(1,3)

Group(l::AbstractVector{T}[,one]) where T

A group may be constructed from a list of l elements of the same type. These elements must respond to the functions * and inv. If it is not possible to compute one from l (because l[1] does not respond to one, or l is empty and T does not respond to one), then the identity element of the group must be given as a second argument.

julia> G=Group([[-1 -1;1 0]])
Group([[-1 -1; 1 0]])

julia> elements(G)
3-element Vector{Matrix{Int64}}:
 [1 0; 0 1]
 [-1 -1; 1 0]
 [0 1; -1 -1]

gens(G::Group) or generators(G::Group) is the Vector of generators of G.

ngens(G::Group) or number_of_generators(G::Group) is the number of generators of G.

one(G::Group) returns the identity element of G.

orders_of_generators(G::Group) or ordergens

The list of orders of the generators (this may be expensive to compute so could be worth being cached in G).

ontuples(t,g)

Assume that t is a Vector or a NTuple. ontuples is the action of g given by (t,g)->map(x->x^g,t).

onsets(s,g)

Assume that s is a set, represented as a sorted list without repetitions. onsets is the action of g given by (s,g)->sort!(map(x->x^g,s)).

orbit(gens::AbstractVector,p,action::Function=^)

orbit(G::Group,p,action::Function=^)

the orbit of point p under repeated action of gens (under repeated actions of gens(G) in the second case).

The type of point p should be hashable.

action(p,g) is a function representing the action of element g on point p. The default is ^. For example if g is a permutation and p an integer, p^g is the image of p by g; if h and g are group elements, then h^g is the conjugate inv(g)*h*g.

julia> orbit([Perm(1,2),Perm(2,3)],1)
3-element Vector{Int64}:
 1
 2
 3

julia> orbit([Perm(1,2),Perm(2,3)],[1,3],ontuples)
6-element Vector{Vector{Int64}}:
 [1, 3]
 [2, 3]
 [1, 2]
 [3, 2]
 [2, 1]
 [3, 1]

julia> orbit([Perm(1,2),Perm(2,3)],[1,3],(v,g)->sort(v.^g)) # "OnSets"
3-element Vector{Vector{Int64}}:
 [1, 3]
 [2, 3]
 [1, 2]

orbits(gens::Vector,v,action=^;trivial=true)

orbits(G::Group,v,action=^;trivial=true)

the orbit of point p under repeated action of gens (under repeated actions of gens(G) in the second case).

The elements of v should be hashable.

If trivial=false the one-element orbits are not returned.

julia> G=Group(Perm(1,2),Perm(2,3));
julia> orbits(G,1:4)
2-element Vector{Vector{Int64}}:
 [1, 2, 3]
 [4]

elements(G::Group) the list of elements of G

transversal(G::Group,p,action::Function=^)

returns an OrderedDict t with keys orbit(G,p,action) and where t[x] is an element of G such that x==action(p,t[x]). Like orbit, it thus requires the type of p to be hashable.

julia> G=Group(Perm(1,2),Perm(2,3));
julia> transversal(G,1)
OrderedDict{Int64, Perm{Int16}} with 3 entries:
  1 => ()
  2 => (1,2)
  3 => (1,3,2)

orbit functions can take any action of G as keyword argument

julia> transversal(G,(1,2),ontuples)
OrderedDict{Tuple{Int64, Int64}, Perm{Int16}} with 6 entries:
  (1, 2) => ()
  (2, 1) => (1,2)
  (1, 3) => (2,3)
  (3, 1) => (1,3,2)
  (2, 3) => (1,2,3)
  (3, 2) => (1,3)

words_transversal(gens,p,action::Function=^)

A transversal recording words. returns a Dict t with keys orbit(gens,p,action) and where t[x] is a sequence of integers such that x==action(p,prod(gens[t[x]])), that is for each element x of the orbit of p describes as a word in gens an element bringing p to x.

julia> words_transversal([Perm(1,2),Perm(2,3)],1)
OrderedDict{Int64, Vector{Int64}} with 3 entries:
  1 => []
  2 => [1]
  3 => [1, 2]

centralizer(G::Group,p,action=^)

computes the subgroup of elements g of G such that action(p,g)==p.

julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> centralizer(G,1)
Group((2,3))

centralizer(G::Group,H::Group) the centralizer in G of the group H

julia> G=Group(Perm(1,2),Perm(1,2,3))
Group((1,2),(1,2,3))

julia> centralizer(G,Group(Perm(1,2)))
Group((1,2))

center(G::Group) the center of G

julia> G=Group(Perm(1,2),Perm(3,4),Perm(1,3)*Perm(2,4))
Group((1,2),(3,4),(1,3)(2,4))

julia> center(G)
Group((1,2)(3,4))

stabilizer(G::Group,s,action=^)

computes the subgroup of elements g of G such that action(p,g)==p.

julia> G=Group(Perm(1,2),Perm(1,2,3,4))
Group((1,2),(1,2,3,4))

Assume that s is a set, represented as a sorted list without repetitions. onsets is the action of g∈ G given by (g,p)->sort(p.^g).

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

normalizer(G::Group,H::Group) the normalizer of H in G

word(G::Group,w) a minimal word in gens(G) representing element w of G

comm(a,b) or commutator(a,b) is a^-1*b^-1*a*b

length(G::Group) the number of elements of G.

length(T,G) do the computation with the integer type T.

class_representatives(G::Group) or classreps

representatives of conjugacy classes of G. By default queries the attribute G.classreps, and if this attribute is present it will be used by conjugacy_classes.

conjugacy_classes(G::Group) conjugacy classes of G (as a Vector{ConjugacyClass})

conjugacy_class(G::Group,g) the class of g

number_of_conjugacy_classes(G::Group) or nconjugacy_classes

the number of conjugacy classes of G"

position_class(G::Group,g) index of conjugacy class to which g belongs

fusion_conjugacy_classes(H::Group,G::Group)

A Vector{Int} telling for each conjugacy class of subgroup H of which class of G is is a subset

some_words(G::Group)

returns a Dict giving for each element of G a positive word in the generators representing it. It is faster than minimal_words but the words are not guaranteed minimal.

julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> some_words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
  ()      => []
  (1,2)   => [1]
  (1,2,3) => [2]
  (1,3)   => [1, 2]
  (2,3)   => [2, 1]
  (1,3,2) => [1, 2, 1]

minimal_words(G::Group)

returns a Dict giving for each element of G a minimal positive word in the generators representing it.

julia> G=Group(Perm(1,2),Perm(1,2,3));
julia> minimal_words(G)
OrderedDict{Perm{Int16}, Vector{Int64}} with 6 entries:
  ()      => []
  (1,2)   => [1]
  (1,2,3) => [2]
  (1,3)   => [1, 2]
  (2,3)   => [2, 1]
  (1,3,2) => [2, 2]

minimal_words(G::Group,w)

Gives all expressions of w as words in the generators of G of minimal length (uses minimal_words(G)).

julia> G=Group(Perm(1,2),Perm(2,3));

julia> minimal_words(G,Perm(1,3))
2-element Vector{Vector{Int64}}:
 [1, 2, 1]
 [2, 1, 2]

words(G::Group;minimal=false)

returns a for each element of G a positive word in the generators representing it. These words are not guaranteed minimal unless the keyword minimal=true is given (which makes the function somewhat slower).

julia> G=Group(Perm(1,2),Perm(1,2,3));

julia> words(G)
6-element Vector{Vector{Int64}}:
 []
 [1]
 [2]
 [1, 2]
 [2, 1]
 [1, 2, 1]

julia> words(G;minimal=true)
6-element Vector{Vector{Int64}}:
 []
 [1]
 [2]
 [1, 2]
 [2, 1]
 [2, 2]

transporting_elt(G,p,q,action=^) or transporting_element(G,p,q,action=^)

returns an element g∈ G such that p^g==q (or action(p,g)==q if action is given), if such a g exists, and nothing otherwise. The set of possible g forms a right coset of the centralizer of p in G.

julia> g=Group(perm"(1,2,3)(6,7)",perm"(3,4,5)(7,8)")
Group((1,2,3)(6,7),(3,4,5)(7,8))

julia> transporting_elt(g,1,5)
(1,5,4,3,2)

julia> transporting_elt(g,1,6)

julia> transporting_elt(g,[1,2,3,4],[2,3,4,5],(s,g)->sort(s.^g))
(1,2,3,4,5)(6,7,8)

julia> transporting_elt(g,[1,2,3,4],[3,4,5,2],(s,g)->s.^g)

intersect(G::Group, H::Group) the intersection as a group

rand(W::Group) a random element of W

isabelian(G::Group) whether G is abelian

iscyclic(G::Group) whether G is cyclic

istrivial(G::Group) whether G is trivial

Hom(S::Group,T::Group,images)

builds an object representing the homomorphism from S to T which maps gens(S) to images.

julia> S=Group(Perm(1,2),Perm(2,3))
Group((1,2),(2,3))

julia> T=Group(Perm(1,2))
Group((1,2))

julia> h=Hom(S,T,[T(1),T(1)])
Hom(Group((1,2),(2,3))→ Group((1,2));[(1,2), (2,3)]↦ [(1,2), (1,2)]

julia> h(S(1,2)) # the image by h
()

kernel(h::Hom) the kernel of the homomorphism h

Coset(G::Group,phi=one(G)) constructs the (left) coset G.phi where G isa Group{<:T} and phi isa T, as an object of type Cosetof{T}. This general coset knows only the general methods for a coset C=G.phi defined in this module, which are

• Group(C) returns G.
• isone(C) returns true iff phi in G
• one(C) returns the trivial coset G.1
• length(C) returns length(G)
• elements(C) returns elements(G).*Ref(phi)
• x in C returns x/phi in G

NormalCoset(G::Group,phi=one(G)) constructs the coset C=G.phi where G isa Group{<:T} and phi isa T, as an object of type NormalCosetof{T}. It is assumed that phi normalizes G. This general coset knows only the general methods defined for normal cosets in the module Groups, which in addition to those defined for cosets (see Coset) are

• inv(C) return G.inv(phi) (assumed equal to inv(phi).G)
• C*D given another coset G.psi returns G.phi*psi
• C/D given another coset G.psi returns G.phi*inv(psi)
• C^D given another coset G.psi returns G.inv(psi)*phi*psi
• C^n returns G.phi^n
• order(C) the smallest n such that isone(C^n)

The conjugacy classes of a normal coset G.phi are relative to the conjugation action of G on G.phi. We have the functions conjugacy_classes, nconjugacy_classes, classreps, position_class.

Finally the function G/H for two groups constructs the quotient as a group of NormalCosets, and fusion_conjugacy_classes(H::NormalCoset,G::NormalCoset) expresses the fusion of conjugacy classes.