diff options
| -rw-r--r-- | gap/subgroupladders.gi | 103 |
1 files changed, 67 insertions, 36 deletions
diff --git a/gap/subgroupladders.gi b/gap/subgroupladders.gi index aba383a..7c373d5 100644 --- a/gap/subgroupladders.gi +++ b/gap/subgroupladders.gi @@ -4,78 +4,97 @@ # Implementations # - +# +# Generate a Young subgroup of a partition part = (p_1, ..., p_k) of some positive integer n. +# Every p_i is a list of positive integers such that the union of the p_i is disjoint and equals {1,...n}. +# The Young subgroup is then the direct product of symmetric groups on the p_i. +# InstallGlobalFunction( YoungGroupFromPartition, function(part) local - i, - P, - G, - grps, - olds, - news, - perms, - info, - generators; - + p, # loop variable over the partition. + Y, # the Young subgroup formed over the partition. + generators, # the generators of Y. + G, # the symmetric group on p. + grps, # record entry of info. + olds, # record entry of info. + news, # record entry of info. + perms, # record entry of info. + info; # record for the DirectProductInfo of Y. + + + # Initialize the variables. grps := []; olds := []; news := []; perms := []; generators := []; - for i in part do - G := SymmetricGroup(i); + # Generate the record entries of info. + for p in part do + G := SymmetricGroup(p); Append(generators, GeneratorsOfGroup(G)); Add(grps, G); - Add(olds, i); - Add(news, i); + Add(olds, p); + Add(news, p); Add(perms, ()); od; - P := Group(generators); + # Generate the Young subgroup Y and add the DirectProductInfo info to Y. + Y := Group(generators); info := rec( groups := grps, olds := olds, news := news, perms := perms, embeddings := [], projections := [] ); - SetDirectProductInfo(P, info); + SetDirectProductInfo(Y, info); - return P; + return Y; end); InstallGlobalFunction( SubgroupLadder, function(G) local - orb, - i, - k, - n, - pair, - ladder, - directfactors, - generators, - mapping, - output, - partition, - FindPos; - - FindPos := function(list, x) - local n, i; - n := Length(list); + orb, # the orbits of the permutation group G + n, # largest moved point of G + i, # loop variable + k, # size of current partition + ladder, # the ladder is a list containing pairs [partition, mapping] + partition, # partition is a list of positive integers (a_1, ..., a_k) such that + # a_1 is the biggest integer of the list. + mapping, # mapping is a list of positive integers (m_1, ..., m_n) such that + # 1 <= m_i <= k for all i. + pair, # a entry of the ladder [partition, mapping] used to construct a young subgroup + output, # a list of groups forming the ladder of G into S_n + FindPos; # a local function + + # + # l = [l_1, ..., l_n] is a list of lists. + # Check wether x in contained in some list l_i of l. + # If it is, return the smallest integer i such that x in l_i. + # Otherwise return 0. + # + FindPos := function(l, x) + local + n, # length of l + i; # loop variable over l + n := Length(l); for i in [1..n] do - if x in list[i] then + if x in l[i] then return i; fi; od; + return 0; end; + # Check if G is a permuatation group if (not IsPermGroup(G)) then ErrorNoReturn("the argument must be a permutation group!\n"); fi; + # Initialize the variables n := LargestMovedPoint(G); orb := List(Orbits(G, [1..n])); @@ -91,12 +110,19 @@ function(G) mapping := List([1..n], x -> FindPos(orb, x)); ladder := [[List(partition), List(mapping)]]; + # Start the iterative construction of the ladder while (Length(partition) <> 1 or partition[1] < n) do - if (Length(partition) = 1 and partition[1] < n) then + # This is the case where partition = (a) and the current young subgroup is S_{a}. + # Add the group S_{a+1} to the ladder + # and continue iteration with this group. + if (Length(partition) = 1) then mapping[Position(mapping, 0)] := 1; partition[1] := partition[1] + 1; Add(ladder, [List(partition), List(mapping)]); else + # This is the case where partition = (a_1, a_2, a_3, ..., a_k) and a_2 = 1. + # Add the young subgroup with partition (a_1, a_3, ..., a_k) + # and continue iteration with this group. if (partition[2] = 1) then Remove(partition, 2); for i in [1..n] do @@ -106,6 +132,10 @@ function(G) od; partition[1] := partition[1] + 1; Add(ladder, [List(partition), List(mapping)]); + # This is the case where partition = (a_1, a_2, a_3, ..., a_k) and a_2 > 1. + # First add the young subgroup with partition (a_1, 1, a_2 - 1, a_3, ..., a_k). + # Then add the young subgroup with partition (a_1 + 1, a_2 - 1, a_3, ..., a_k) + # and continue iteration with this group. else mapping[Position(mapping, 2)] := Length(partition)+1; partition[2] := partition[2] - 1; @@ -120,6 +150,7 @@ function(G) fi; od; + # Construct the young subgroups of the pairs [partition, mapping] stored in ladder for pair in ladder do k := Length(pair[1]); mapping := pair[2]; |