summaryrefslogtreecommitdiffstats
path: root/gap
diff options
context:
space:
mode:
Diffstat (limited to 'gap')
-rw-r--r--gap/subgroupladders.gi103
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];