summaryrefslogtreecommitdiffstats
path: root/gap/subgroupladders.gi
blob: 7c373d5830594f323c9d75aa730432b4fa518425 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
#
# subgroupladders: This package provides an algorithm that computes a subgroup ladder from a permutation group up to the parent symmetric group.
#
# 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
		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 := [];

	# Generate the record entries of info.
	for p in part do
		G := SymmetricGroup(p);
		Append(generators, GeneratorsOfGroup(G));
		Add(grps, G);
		Add(olds, p);
		Add(news, p);
		Add(perms, ());
	od;

	# 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(Y, info);

	return Y;
end);


InstallGlobalFunction( SubgroupLadder,
function(G)
	local
		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 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]));
	SortBy(orb, x->-Length(x));

	output := [];

	if (YoungGroupFromPartition(orb) <> G) then
		output := [G];
	fi;

	partition := List(orb, Length);
	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
		# 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
					if (mapping[i]) > 1 then
						mapping[i] := mapping[i] - 1;
					fi;
				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;
				Add(partition, 1);
				Add(ladder, [List(partition), List(mapping)]);

				mapping[Position(mapping, Length(partition))] := 1;
				Remove(partition);
				partition[1] := partition[1] + 1;
				Add(ladder, [List(partition), List(mapping)]);
			fi;
		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];
		Add(output, YoungGroupFromPartition(List([1..k], i -> Filtered([1..n], x -> i = mapping[x]))));
	od;

	return output;
end);

# vim: set noet ts=4: