The InduceReduce provides a function for computing the table of ordinary irreducible characters of a finite group G using an algorithm based on Brauer's theorem on induced characters (see the Wikipedia article), which has been described by W. Unger in [Ung06]. By Brauer's theorem, the ring ℤIrr}(G) of generalized characters of G is generated by the induced characters Ind}_H^G(λ), where H runs over all elementary subgroups of G and λ runs over all irreducible characters of H. The algorithm runs over suitably chosen elementary subgroups of G, computes their irreducible characters and induces them to G. In the resulting lattice of generalized characters, it searches for an orthonormal basis by means of LLL lattice reduction. Once an orthonormal basis of size equal to the number of conjugacy classes of G is found, it is clear from character theory that the elements of this basis are up to sign the irreducible characters of G.
Unger's Algorithm is implemented in the function CharacterTableUnger (1.2-1).
‣ CharacterTableUnger( G[, Opt] ) | ( function ) |
This function computes the character table of a finite group using Unger's algorithm. The argument G must be a finite group, the argument Opt must be a record which sets some options for the algorithm (more details in Section 1.3 below).
gap> G:=AlternatingGroup(6);; gap> CharacterTableUnger(G); CharacterTable( Alt( [ 1 .. 6 ] ) )
‣ InfoCTUnger | ( info class ) |
The info class InfoCTUnger makes the function CharacterTableUnger (1.2-1) display information about the current state of the computation, which may be useful for computations with large groups. If InfoCTUnger is set to 1 then the function first displays the number of conjugacy classes of G and then shows for any elementary subgroup E = ZP whose characters are induced to G the order of Z, the order of P and the number of conjugacy classes of E. If InfoCTUnger is set to 2 then it additionally displays the orders of the conjugacy. Moreover, it shows after each LLL reduction the total number of irreducible characters found so far, the dimension of the character lattice and the determinant of the Gram matrix.
gap> G:=AlternatingGroup(6);; gap> SetInfoLevel(InfoCTUnger,1); gap> CharacterTableUnger(G); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 5, 1, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 4, 1, 4 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] CharacterTable( Alt( [ 1 .. 6 ] ) ) gap> SetInfoLevel(InfoCTUnger,2); gap> CharacterTableUnger(G); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 5, 1, 5 ] #I Reduce: |Irr| = 1, dim = 4, det(G) = 43 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 4, 1, 4 ] #I Reduce: |Irr| = 1, dim = 6, det(G) = 8 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 2, dim = 7, det(G) = 4 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) )
‣ CTUngerDefaultOptions | ( global variable ) |
The global variable CTUngerDefaultOptions contains a record with four components DoCyclicFirst, DoCyclicLast, LLLOffset and Delta, which specify the default options for the function CharacterTableUnger (1.2-1). The options can be changed manually by the user, for more details see Subsection 1.3-4 below. The initial values for the record components are as follows:
gap> CTUngerDefaultOptions; rec( Delta := 3/4, DoCyclicFirst := false, DoCyclicLast := false, LLLOffset := 0 )
In this section, we explain the options for CharacterTableUnger (1.2-1) using the optional second argument Opt, which should be a record with components DoCyclicFirst, DoCyclicLast, LLLOffset and Delta. You only need to specify those components of the record that you want to manually set to a certain value, the others will be assigned their default value by the program. Additional components of the record will be ignored. The intended use of the different components of Opt is as follows:
The component Opt.DoCyclicFirst should be a boolean which is by default set to false. It tells the function CharacterTableUnger (1.2-1) to first induce all irreducible characters of the cyclic subgroups and then proceed to do the same for the non-cyclic elementary subgroups. The option Opt.DoCyclicLast does the opposite, that is, it tells CharacterTableUnger (1.2-1) to first induce the characters of the non-cyclic elementary subgroups and then proceed to induce the characters of the cyclic subgroups. The default value is also false Note that even when Opt.DoCyclicLast is true, it may happen that some cyclic group are used by the algorithm earlier than some non-cyclic elementary subgroups, but only when the group P in E = ZP is cyclic. When both Opt.DoCyclicFirst and Opt.DoCyclicLast are set to be true then the program still induces from cyclic groups first.
gap> CharacterTableUnger(G,rec( DoCyclicFirst:=true )); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce: from cyclic subgroups #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) ) gap> CharacterTableUnger(G,rec( DoCyclicLast:=true )); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 5, 5 ] #I Reduce: |Irr| = 1, dim = 4, det(G) = 43 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 8, 5 ] #I Reduce: |Irr| = 5, dim = 6, det(G) = 2 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 9, 9 ] #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) )
The component Opt.LLLOffset should be an integer telling the function CharacterTableUnger (1.2-1) to not apply LLL reduction to the Gram matrix of the character lattice each time after the characters of some elementary subgroup have been induced. More precisely, the first LLL reduction will be carried out after the characters of the first Opt.LLLOffsetelementary subgroups have been induced. When Opt.DoCyclicFirst is true then the first LLL reduction will be carried out after the characters of the cyclic groups and the first Opt.LLLOffset non-cyclic elementary groups have been induced. The default value for Opt.LLLOffset is 0.
gap> CharacterTableUnger(G,rec( LLLOffset:=3 )); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 5, 1, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 4, 1, 4 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 2, dim = 7, det(G) = 4 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) )
The component Opt.Delta can be used to specify the parameter δ for the LLL reduction, where 1/4 < δ ≤ 1. The default value for Opt.Delta is 3/4 and Opt.Delta is ignored if it is not a rational with 1/4 < Opt.Delta and Opt.Delta ≤ 1.
gap> SetInfoLevel(InfoCTUnger,2); gap> G:=AlternatingGroup(6);; gap> CharacterTableUnger(G,rec( Delta:=3/10 )); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 5, 1, 5 ] #I Reduce: |Irr| = 1, dim = 4, det(G) = 43 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 4, 1, 4 ] #I Reduce: |Irr| = 1, dim = 6, det(G) = 8 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 2, dim = 7, det(G) = 4 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 3, 1, 3 ] #I Reduce: |Irr| = 5, dim = 7, det(G) = 1 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 9, 9 ] #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) ) gap> CharacterTableUnger(G,rec( Delta:=3/10, DoCyclicLast:=true )); #I Induce/Restrict: group with 7 conjugacy classes. #I Induce/Restrict: orders of class reps: [ 1, 2, 3, 3, 4, 5, 5 ] #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 5, 5 ] #I Reduce: |Irr| = 1, dim = 4, det(G) = 43 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 9, 9 ] #I Reduce: |Irr| = 2, dim = 6, det(G) = 3 #I Induce/Restrict: Trying [|Z|, |P|, k(E)] = [ 1, 8, 5 ] #I Reduce: |Irr| = 5, dim = 7, det(G) = 1 #I Reduce: |Irr| = 7 CharacterTable( Alt( [ 1 .. 6 ] ) )
In cases where the character tables of several groups need to be computed using the same options, it may be useful to change the default options, which are specified in the record CTUngerDefaultOptions (1.2-3). This can be done by simply overwriting the the components of that record.
gap> CTUngerDefaultOptions; rec( Delta := 3/4, DoCyclicFirst := false, DoCyclicLast := false, LLLOffset := 0 ) gap> CTUngerDefaultOptions.Delta:=1;; gap> CTUngerDefaultOptions.DoCyclicLast:=true;; gap> CTUngerDefaultOptions; rec( Delta := 1, DoCyclicFirst := false, DoCyclicLast := true, LLLOffset := 0 )
generated by GAPDoc2HTML