Context Navigation

source: sage/groups/perm_gps/permgroup.py @ 5214:c873c821aed7

Visit:

Revision 5214:c873c821aed7, 61.5 KB checked in by Nick Alexander <ncalexander@…>, 6 years ago (diff)

Fixes to permutation groups in response to David Joyner's large permutation groups patch.

removed <BLANKLINE>
Suzuki -> SuzukiGroup? for consistency, and better error checking in constructor
various conversion fixes, int -> Integer
add from_gap_list, change is_isomorphic to isomorphism_to, fix PermutationGroupMorphism?_im_gens, and make isomorphism_to return a usable(?) isomorphism.
make homology error checking less forgiving

Line
1	r"""
2	Permutation groups
3
4	A {\it permutation group} is a finite group G whose elements are permutations
5	of a given finite set X (i.e., bijections X --> X) and whose group operation is
6	the composition of permutations. The number of elements of $X$ is called the
7	{\it degree} of G.
8
9	In \sage a permutation is represented as either a string that defines a
10	permutation using disjoint cycle notation, or a list of tuples, which represent
11	disjoint cycles.
12
13	\begin{verbatim}
14	(a,...,b)(c,...,d)...(e,...,f) <--> [(a,...,b), (c,...,d),..., (e,...,f)]
15	() = identity <--> []
16	\end{verbatim}
17
18	You can make the "named" permutation groups (see \code{permgp_named.py})
19	and use the following constructions:
20
21	-- permutation group generated by elements,
22	-- direct_product_permgroups, which takes a list of permutation
23	groups and returns their direct product.
24
25	JOKE:
26	Q: What's hot, chunky, and acts on a polygon? A: Dihedral soup.
27	Renteln, P. and Dundes, A. "Foolproof: A Sampling of Mathematical
28	Folk Humor." Notices Amer. Math. Soc. 52, 24--34, 2005.
29
30	AUTHOR:
31	- David Joyner (2005-10-14): first version
32	- David Joyner (2005-11-17)
33	- William Stein (2005-11-26): rewrite to better wrap Gap
34	- David Joyner (2005-12-21)
35	- Stein and Joyner (2006-01-04): added conjugacy_class_representatives
36	- David Joyner (2006-03): reorganization into subdirectory perm_gps;
37	added __contains__, has_element; fixed _cmp_;
38	added subgroup class+methods, PGL,PSL,PSp, PSU classes,
39	- David Joyner (2006-06): added PGU, functionality to SymmetricGroup, AlternatingGroup,
40	direct_product_permgroups
41	- David Joyner (2006-08): added degree, ramification_module_decomposition_modular_curve
42	and ramification_module_decomposition_hurwitz_curve
43	methods to PSL(2,q), MathieuGroup, is_isomorphic
44	- Bobby Moretti (2006)-10): Added KleinFourGroup, fixed bug in DihedralGroup
45	- David Joyner (2006-10): added is_subgroup (fixing a bug found by Kiran Kedlaya),
46	is_solvable, normalizer, is_normal_subgroup, Suzuki
47	- David Kohel (2007-02): fixed __contains__ to not enumerate group elements,
48	following the convention for __call__
49	- David Harvey, Mike Hansen, Nick Alexander, William Stein (2007-02,03,04,05): Various patches
50	- Nathan Dunfield (2007-05): added orbits
51	- David Joyner (2007-06): added subgroup method (suggested by David Kohel),
52	composition_series, lower_central_series, upper_central_series,
53	cayley_table, quotient_group, sylow_subgroup, is_cyclic,
54	homology, homology_part, cohomology, cohomology_part,
55	poincare_series, molien_series, is_simple, is_monomial,
56	is_supersolvable, is_nilpotent, is_perfect, is_polycyclic,
57	is_elementary_abelian, is_pgroup, gens_small,
58	isomorphism_type_info_simple_group.
59	moved all the "named" groups to a new file.
60	- Nick Alexander (2007-07): move is_isomorphic to isomorphism_to, add from_gap_list
61
62	REFERENCES:
63	Cameron, P., Permutation Groups. New York: Cambridge University Press, 1999.
64	Wielandt, H., Finite Permutation Groups. New York: Academic Press, 1964.
65	Dixon, J. and Mortimer, B., Permutation Groups, Springer-Verlag, Berlin/New York, 1996.
66
67	NOTE:
68	Though Suzuki groups are okay, Ree groups should not be wrapped as permutation groups - the
69	construction is too slow - unless (for small values or the parameter) they are
70	made using explicit generators.
71
72	"""
73
74	#*****************************************************************************
75	# Copyright (C) 2006 William Stein <wstein@gmail.com>
76	# David Joyner <wdjoyner@gmail.com>
77	#
78	# Distributed under the terms of the GNU General Public License (GPL)
79	# http://www.gnu.org/licenses/
80	#*****************************************************************************
81
82
83	import random
84
85	import sage.structure.element as element
86	import sage.groups.group as group
87
88	from sage.rings.all import RationalField, Integer
89	from sage.interfaces.all import gap, is_GapElement, is_ExpectElement
90	import sage.structure.coerce as coerce
91	from sage.rings.finite_field import GF
92	from sage.rings.arith import factor
93	from sage.groups.abelian_gps.abelian_group import AbelianGroup
94	from sage.misc.functional import is_even, log
95	from sage.rings.rational_field import RationalField
96	from sage.matrix.matrix_space import MatrixSpace
97	from sage.rings.polynomial.polynomial_ring_constructor import PolynomialRing
98	from sage.rings.fraction_field import FractionField
99	from sage.matrix.matrix_space import MatrixSpace
100
101	def gap_format(x):
102	"""
103	Put a permutation in Gap format, as a string.
104	"""
105	if isinstance(x,str): return x
106	x = str(tuple(x)).replace(' ','')
107	return x.replace('),(',')(').replace(',)',')')
108
109	def from_gap_list(G, src):
110	r"""Convert a string giving a list of GAP permutations into a list of elements of G.
111
112	EXAMPLES:
113	sage: from sage.groups.perm_gps.permgroup import from_gap_list
114	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
115	sage: L = from_gap_list(G, "[(1,2,3)(4,5), (3,4)]"); L
116	[(1,2,3)(4,5), (3,4)]
117	sage: L[0].parent() is G
118	True
119	sage: L[1].parent() is G
120	True
121	"""
122	# trim away the list constructs
123	src = src.replace("[", "").replace("]", "")
124	# cut out the individual elements
125	srcs = src.split("),")
126	for i in range(len(srcs[:-1])):
127	srcs[i] = srcs[i] + ")"
128	srcs = map(G, srcs)
129	return srcs
130
131	def PermutationGroup(x, from_group=False, check=True):
132	"""
133	Return the permutation group associated to $x$ (typically a list
134	of generators).
135
136	EXAMPLES:
137	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
138	sage: G
139	Permutation Group with generators [(1,2,3)(4,5), (3,4)]
140
141	We can also make permutation groups from PARI groups:
142	sage: H = pari('x^4 - 2x^3 - 2x + 1').polgalois()
143	sage: G = PariGroup(H, 4); G
144	PARI group [8, -1, 3, "D(4)"] of degree 4
145	sage: H = PermutationGroup(G); H # requires optional database_gap
146	Transitive group number 3 of degree 4
147	sage: H.gens() # requires optional database_gap
148	((1,2,3,4), (1,3))
149
150	EXAMPLES:
151	There is an underlying gap object that implements each permutation group.
152
153	sage: G = PermutationGroup([[(1,2,3,4)]])
154	sage: G._gap_()
155	Group([ (1,2,3,4) ])
156	sage: gap(G)
157	Group([ (1,2,3,4) ])
158	sage: gap(G) is G._gap_()
159	True
160	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
161	sage: G._gap_().DerivedSeries() # output somewhat random
162	[ Group([ (1,2,3)(4,5), (3,4) ]), Group([ (1,5)(3,4), (1,5)(2,4), (1,4,5) ]) ]
163	"""
164	if not is_ExpectElement(x) and hasattr(x, '_permgroup_'):
165	return x._permgroup_()
166	return PermutationGroup_generic(x, from_group, check)
167
168
169	class PermutationGroup_generic(group.FiniteGroup):
170	"""
171	EXAMPLES:
172	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
173	sage: G
174	Permutation Group with generators [(1,2,3)(4,5), (3,4)]
175	sage: G.center()
176	Permutation Group with generators [()]
177	sage: G.group_id() # requires optional database_gap
178	[120, 34]
179	sage: n = G.order(); n
180	120
181	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
182	sage: loads(G.dumps()) == G
183	True
184	"""
185	def __init__(self, gens, from_group = False, check=True):
186	if from_group and isinstance(gens, str):
187	self.__gap = gens
188	self.gens() # so will check that group can be defined in GAP (e.g., no missing packages, etc.)
189	return
190	if is_GapElement(gens):
191	if from_group:
192	# the variable gens is actually a Gap group or string
193	# representation of one.
194	self.__gap = str(gens)
195	else:
196	# gens is a Gap object that represents a list of generators for a group
197	self.__gap = 'Group(%s)'%gens
198	self.gens() # so will check that group can be defined in GAP (e.g., no missing packages, etc.)
199	return
200
201	if check:
202	if isinstance(gens, tuple):
203	gens = list(gens)
204	elif not isinstance(gens, list):
205	raise TypeError, "gens must be a tuple or list"
206	gens = [gap_format(x) for x in gens]
207
208	cmd = 'Group(%s)'%gens
209	cmd = cmd.replace("'","") # get rid of quotes
210	self.__gap = cmd
211	self.gens()
212
213	def _gap_init_(self):
214	return self.__gap
215
216	def _magma_init_(self):
217	g = str(self.gens())[1:-1]
218	return 'PermutationGroup<%s \| %s>'%(self.degree(), g)
219
220	def __cmp__(self, right):
221	"""
222	Compare self and right.
223
224	The ordering is whatever it is in Gap.
225
226	EXAMPLES:
227	sage: G1 = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
228	sage: G2 = PermutationGroup([[(1,2,3),(4,5)]])
229	sage: G1 > G2
230	True
231	sage: G1 < G2
232	False
233	"""
234	if not isinstance(right, PermutationGroup_generic):
235	return -1
236	return right._gap_().__cmp__(self._gap_())
237
238
239	def __call__(self, x):
240	"""
241	Coerce x into this permutation group.
242
243	The input can be either a string that defines a permutation in
244	cycle notation, a permutation group element, a list of
245	integers that gives the permutation as a mapping, a list of
246	tuples, or the integer 1.
247
248	EXAMPLES:
249	We illustrate each way to make a permutation in S4:
250	sage: G = SymmetricGroup(4)
251	sage: G((1,2,3,4))
252	(1,2,3,4)
253	sage: G([(1,2),(3,4)])
254	(1,2)(3,4)
255	sage: G('(1,2)(3,4)')
256	(1,2)(3,4)
257	sage: G([1,2,4,3])
258	(3,4)
259	sage: G([2,3,4,1])
260	(1,2,3,4)
261	sage: G(G((1,2,3,4)))
262	(1,2,3,4)
263	sage: G(1)
264	()
265
266	Some more examples:
267	sage: G = PermutationGroup([(1,2,3,4)])
268	sage: G([(1,3), (2,4)])
269	(1,3)(2,4)
270	sage: G(G.0^3)
271	(1,4,3,2)
272	sage: G(1)
273	()
274	sage: G((1,4,3,2))
275	(1,4,3,2)
276	sage: G([(1,2)])
277	Traceback (most recent call last):
278	...
279	TypeError: permutation (1,2) not in Permutation Group with generators [(1,2,3,4)]
280	"""
281	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
282	if isinstance(x, PermutationGroupElement):
283	if x.parent() is self:
284	return x
285	else:
286	return PermutationGroupElement(x._gap_(), self, check = True)
287	elif isinstance(x, (list, str)):
288	if isinstance(x, list) and len(x) > 0 and not isinstance(x[0], tuple):
289	# todo: This is ok, but is certainly not "industry strength" fast
290	# compared to what is possible.
291	x = gap.eval('PermList(%s)'%x)
292	return PermutationGroupElement(x, self, check = True)
293	elif isinstance(x, tuple):
294	return PermutationGroupElement([x], self, check = True)
295	elif isinstance(x, (int, long, Integer)) and x == 1:
296	return self.identity()
297	else:
298	raise TypeError, "unable to coerce %s to permutation in %s"%(x, self)
299
300	def _coerce_impl(self, x):
301	r"""
302	Implicit coercion of x into self.
303
304	EXAMPLES:
305	We illustrate some arithmetic that involves implicit coercion
306	of elements in different permutation groups.
307
308	sage: g1 = PermutationGroupElement([(1,2),(3,4,5)])
309	sage: g1.parent()
310	Symmetric group of order 5! as a permutation group
311	sage: g2 = PermutationGroupElement([(1,2)])
312	sage: g2.parent()
313	Symmetric group of order 2! as a permutation group
314	sage: g1*g2
315	(3,4,5)
316	sage: g2*g2
317	()
318	sage: g2*g1
319	(3,4,5)
320
321	We try to implicitly coerce in a non-permutation, which raises
322	a TypeError:
323
324	sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
325	sage: G._coerce_impl(1)
326	Traceback (most recent call last):
327	...
328	TypeError: no implicit coercion of element into permutation group
329	"""
330	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
331	if isinstance(x, PermutationGroupElement):
332	if x.parent() is self:
333	return x
334	elif x.parent().degree() <= self.degree() and x._gap_() in self._gap_():
335	return PermutationGroupElement(x._gap_(), self, check = False)
336	raise TypeError, "no implicit coercion of element into permutation group"
337
338	def list(self):
339	"""
340	Return list of all elements of this group.
341
342	EXAMPLES:
343	sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
344	sage: G.list()
345	[(), (3,4), (2,3), (2,3,4), (2,4,3), (2,4), (1,2), (1,2)(3,4), (1,2,3), (1,2,3,4), (1,2,4,3), (1,2,4), (1,3,2), (1,3,4,2), (1,3), (1,3,4), (1,3)(2,4), (1,3,2,4), (1,4,3,2), (1,4,2), (1,4,3), (1,4), (1,4,2,3), (1,4)(2,3)]
346	"""
347	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
348	X = self._gap_().Elements()
349	n = X.Length()
350	return [PermutationGroupElement(X[i], self, check = False)
351	for i in range(1,n+1)]
352
353	def __contains__(self, item):
354	"""
355	Returns boolean value of "item in self"
356
357	EXAMPLES:
358	sage: G = SymmetricGroup(16)
359	sage: g = G.gen(0)
360	sage: h = G.gen(1)
361	sage: g^7hg*h in G
362	True
363	sage: G = SymmetricGroup(4)
364	sage: g = G((1,2,3,4))
365	sage: h = G((1,2))
366	sage: H = PermutationGroup([[(1,2,3,4)], [(1,2),(3,4)]])
367	sage: g in H
368	True
369	sage: h in H
370	False
371	"""
372	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
373	if isinstance(item, PermutationGroupElement):
374	if not item.parent() is self:
375	try:
376	item = PermutationGroupElement(item._gap_(), self, check = True)
377	except:
378	return False
379	return True
380	elif isinstance(item, (list, str)):
381	if isinstance(item, list) and len(item) > 0 and not isinstance(item[0], tuple):
382	item = gap.eval('PermList(%s)'%item)
383	try:
384	item = PermutationGroupElement(item, self, check = True)
385	except:
386	return False
387	return True
388	elif isinstance(item, tuple):
389	if isinstance(item, list) and len(item) > 0 and not isinstance(item[0], tuple):
390	item = gap.eval('PermList(%s)'%item)
391	try:
392	item = PermutationGroupElement(item, self, check = True)
393	except:
394	return False
395	return True
396	elif isinstance(item, (int, long, Integer)) and item == 1:
397	return True
398	return False
399
400	def has_element(self,item):
401	"""
402	Returns boolean value of "item in self" -- however ignores parentage.
403
404	EXAMPLES:
405	sage: G = CyclicPermutationGroup(4)
406	sage: gens = G.gens()
407	sage: H = DihedralGroup(4)
408	sage: g = G([(1,2,3,4)]); g
409	(1,2,3,4)
410	sage: G.has_element(g)
411	True
412	sage: h = H([(1,2),(3,4)]); h
413	(1,2)(3,4)
414	sage: G.has_element(h)
415	False
416
417	"""
418	L = [str(x) for x in self.list()]
419	return (str(item) in L)
420
421	def __iter__(self):
422	"""
423	Return an iterator over the elements of this group.
424
425	EXAMPLES:
426	sage: G = PermutationGroup([[(1,2,3)], [(1,2)]])
427	sage: [a for a in G]
428	[(), (2,3), (1,2), (1,2,3), (1,3,2), (1,3)]
429	"""
430	for g in self.list():
431	yield g
432
433	def gens(self):
434	"""
435	Return tuple of generators of this group. These need not be
436	minimal, as they are the generators used in defining this
437	group.
438
439	EXAMPLES:
440	sage: G = PermutationGroup([[(1,2,3)], [(1,2)]])
441	sage: G.gens()
442	((1,2,3), (1,2))
443
444	Note that the generators need not be minimal.
445	sage: G = PermutationGroup([[(1,2)], [(1,2)]])
446	sage: G.gens()
447	((1,2), (1,2))
448
449	sage: G = PermutationGroup([[(1,2,3,4), (5,6)], [(1,2)]])
450	sage: g = G.gens()
451	sage: g[0]
452	(1,2,3,4)(5,6)
453	sage: g[1]
454	(1,2)
455	"""
456	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
457	try:
458	return self.__gens
459	except AttributeError:
460	try:
461	gens = self._gap_().GeneratorsOfGroup()
462	except TypeError, s:
463	raise RuntimeError, "(It might be necessary to install the database_gap optional SAGE package, if you haven't already.)\n%s"%s
464	self.__gens = tuple([PermutationGroupElement(gens[n],
465	self, check = False) for n in \
466	range(1, Integer(gens.Length())+1)])
467	return self.__gens
468
469	def gens_small(self):
470	"""
471	Returns a generating set of G which has few elements. As neither
472	irredundancy, nor minimal length is proven, it is fast.
473
474	EXAMPLES:
475	sage: R = "(25,27,32,30)(26,29,31,28)( 3,38,43,19)( 5,36,45,21)( 8,33,48,24)" ## R = right
476	sage: U = "( 1, 3, 8, 6)( 2, 5, 7, 4)( 9,33,25,17)(10,34,26,18)(11,35,27,19)" ## U = top
477	sage: L = "( 9,11,16,14)(10,13,15,12)( 1,17,41,40)( 4,20,44,37)( 6,22,46,35)" ## L = left
478	sage: F = "(17,19,24,22)(18,21,23,20)( 6,25,43,16)( 7,28,42,13)( 8,30,41,11)" ## F = front
479	sage: B = "(33,35,40,38)(34,37,39,36)( 3, 9,46,32)( 2,12,47,29)( 1,14,48,27)" ## B = back or rear
480	sage: D = "(41,43,48,46)(42,45,47,44)(14,22,30,38)(15,23,31,39)(16,24,32,40)" ## D = down or bottom
481	sage: G = PermutationGroup([R,L,U,F,B,D])
482	sage: len(G.gens_small())
483	2
484	"""
485	return self._gap_().SmallGeneratingSet()
486
487	def gen(self, i):
488	return self.gens()[Integer(i)]
489
490	def cayley_table(self, names="x"):
491	"""
492	Returns the multiplication table, or Cayley table, of the
493	finite group G in the form of a matrix with symbolic coefficients.
494	This function is useful for learning, teaching, and exploring
495	elementary group theory. Of course, G must be a group of low order.
496
497	As the last line below illustrates, the ordering used here in the first
498	row is the same as in G.list().
499
500	EXAMPLES:
501	sage: G = PermutationGroup(['(1,2,3)', '(2,3)'])
502	sage: G.cayley_table()
503	[x0 x1 x2 x3 x4 x5]
504	[x1 x0 x3 x2 x5 x4]
505	[x2 x4 x0 x5 x1 x3]
506	[x3 x5 x1 x4 x0 x2]
507	[x4 x2 x5 x0 x3 x1]
508	[x5 x3 x4 x1 x2 x0]
509	sage: G.list()[3]*G.list()[3] == G.list()[4]
510	True
511	sage: G.cayley_table("y")
512	[y0 y1 y2 y3 y4 y5]
513	[y1 y0 y3 y2 y5 y4]
514	[y2 y4 y0 y5 y1 y3]
515	[y3 y5 y1 y4 y0 y2]
516	[y4 y2 y5 y0 y3 y1]
517	[y5 y3 y4 y1 y2 y0]
518	sage: G.cayley_table(names="abcdef")
519	[a b c d e f]
520	[b a d c f e]
521	[c e a f b d]
522	[d f b e a c]
523	[e c f a d b]
524	[f d e b c a]
525
526	"""
527	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
528	G = self
529	n = G.order()
530	gap.eval("G := %s"%G._gap_())
531	gap.eval("phi := RegularActionHomomorphism( G );")
532	gap.eval("gens := GeneratorsOfGroup( Image( phi ));")
533	N = Integer(gap.eval("N := Length(gens);"))
534	gens = [PermutationGroupElement(gap.eval("gens[%s];"%i)) for i in range(1,N+1)]
535	H = PermutationGroup(gens)
536	nH = H.order()
537	R,vars = PolynomialRing(RationalField(),names,nH).objgens()
538	multiplication_table_G = sum([(H.list()[i]).matrix()*vars[i] for i in range(nH)])
539	MT = multiplication_table_G.rows()
540	MT.sort()
541	MT.reverse()
542	MS = MatrixSpace(R,n,n)
543	return MS(MT)
544
545	multiplication_table = cayley_table
546
547	def identity(self):
548	"""
549	Return the identity element of this group.
550
551	EXAMPLES:
552	sage: G = PermutationGroup([[(1,2,3),(4,5)]])
553	sage: e = G.identity()
554	sage: e
555	()
556	sage: g = G.gen(0)
557	sage: g*e
558	(1,2,3)(4,5)
559	sage: e*g
560	(1,2,3)(4,5)
561	"""
562	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
563	return PermutationGroupElement('()', self, check=True)
564
565	def degree(self):
566	"""
567	Synonym for largest_moved_point().
568
569	EXAMPLES:
570	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
571	sage: G.degree()
572	5
573	"""
574	return self.largest_moved_point()
575
576	def exponent(self):
577	"""
578	Computes the exponent of the group. The exponent $e$ of a group $G$ is the lcm of
579	the orders of its elements, that is, $e$ is the smallest integer such that $g^e=1$ for all
580	$g \in G$.
581
582	EXAMPLES:
583	sage: G = AlternatingGroup(4)
584	sage: G.exponent()
585	6
586	"""
587	return Integer(self._gap_().Exponent())
588
589	def largest_moved_point(self):
590	"""
591	Return the largest point moved by a permutation in this group.
592
593	EXAMPLES:
594	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
595	sage: G.largest_moved_point()
596	4
597	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
598	sage: G.largest_moved_point()
599	10
600	"""
601	try:
602	return self.__largest_moved_point
603	except AttributeError:
604	n = Integer(self._gap_().LargestMovedPoint())
605	self.__largest_moved_point = n
606	return n
607
608	def smallest_moved_point(self):
609	"""
610	Return the smallest point moved by a permutation in this group.
611
612	EXAMPLES:
613	sage: G = PermutationGroup([[(3,4)], [(2,3,4)]])
614	sage: G.smallest_moved_point()
615	2
616	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
617	sage: G.smallest_moved_point()
618	1
619	"""
620	try:
621	return self.__smallest_moved_point
622	except AttributeError:
623	n = Integer(self._gap_().SmallestMovedPoint())
624	self.__smallest_moved_point = n
625	return n
626
627	def orbits(self):
628	"""
629	Returns the orbits of [1,2,...,degree] under the group action.
630
631	EXAMPLES:
632	sage: G = PermutationGroup([ [(3,4)], [(1,3)] ])
633	sage: G.orbits()
634	[[1, 3, 4], [2]]
635	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4,10)]])
636	sage: G.orbits()
637	[[1, 2, 3, 4, 10], [5], [6], [7], [8], [9]]
638
639	The answer is cached:
640	sage: G.orbits() is G.orbits()
641	True
642
643	AUTHOR:
644	-- Nathan Dunfield
645	"""
646	try:
647	return self.__orbits
648	except AttributeError:
649	O = self._gap_().Orbits("[1..%d]" % self.largest_moved_point()).sage()
650	self.__orbits = O
651	return O
652
653	def _repr_(self):
654	G = self.gens()
655	return "Permutation Group with generators %s"%list(self.gens())
656
657	def _latex_(self):
658	return '\\langle ' + \
659	', '.join([x._latex_() for x in self.gens()]) + ' \\rangle'
660
661	def order(self):
662	"""
663	Return the number of elements of this group.
664
665	EXAMPLES:
666	sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
667	sage: G.order()
668	12
669	"""
670	return Integer(self._gap_().Size())
671
672	def random_element(self):
673	"""
674	Return a random element of this group.
675
676	EXAMPLES:
677	sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
678	sage: G.random_element() ## random output
679	(1, 3)(4, 5)
680	"""
681	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
682	return PermutationGroupElement(self._gap_().Random(),
683	self, check=False)
684
685	def group_id(self):
686	"""
687	Return the ID code of this group, which is a list of two
688	integers. Requires "optional" database_gap-4.4.x package.
689
690	EXAMPLES:
691	sage: G = PermutationGroup([[(1,2,3),(4,5)], [(1,2)]])
692	sage: G.group_id() # requires optional database_gap-4.4.6 package
693	[12, 4]
694	"""
695	return [Integer(n) for n in eval(str(self._gap_().IdGroup()))]
696
697	def id(self):
698	"""
699	Same as self.group_id()
700	"""
701	return self.group_id()
702
703	def center(self):
704	"""
705	Return the subgroup of elements of that commute with
706	every element of this group.
707
708	EXAMPLES:
709	sage: G = PermutationGroup([[(1,2,3,4)]])
710	sage: G.center()
711	Permutation Group with generators [(1,2,3,4)]
712	sage: G = PermutationGroup([[(1,2,3,4)], [(1,2)]])
713	sage: G.center()
714	Permutation Group with generators [()]
715	"""
716	C = self._gap_().Center()
717	return PermutationGroup(C, from_group = True)
718
719	def direct_product(self,other,maps=True):
720	"""
721	Wraps GAP's DirectProduct, Embedding, and Projection.
722
723	SAGE calls GAP's DirectProduct, which chooses an efficient representation
724	for the direct product. The direct product of permutation groups will
725	be a permutation group again. For a direct product D, the GAP
726	operation Embedding(D,i) returns the homomorphism embedding the
727	i-th factor into D. The GAP operation Projection(D,i) gives the projection
728	of D onto the i-th factor.
729
730	INPUT:
731	self, other -- permutation groups
732
733	This method returns a 5-tuple - a permutation groups and 4 morphisms.
734
735	OUTPUT:
736	D -- a direct product of the inputs, returned as a permutation group as well
737	iota1 -- an embedding of self into D
738	iota2 -- an embedding of other into D
739	pr1 -- the projection of D onto self (giving a splitting 1 -> other -> D ->> self -> 1)
740	pr2 -- the projection of D onto other (giving a splitting 1 -> self -> D ->> other -> 1)
741
742	EXAMPLES:
743	sage: G = CyclicPermutationGroup(4)
744	sage: D = G.direct_product(G,False)
745	sage: D
746	Permutation Group with generators [(1,2,3,4), (5,6,7,8)]
747	sage: D,iota1,iota2,pr1,pr2 = G.direct_product(G)
748	sage: D; iota1; iota2; pr1; pr2
749	Permutation Group with generators [(1,2,3,4), (5,6,7,8)]
750	Homomorphism : Cyclic group of order 4 as a permutation group --> Permutation Group with generators [(1,2,3,4), (5,6,7,8)]
751	Homomorphism : Cyclic group of order 4 as a permutation group --> Permutation Group with generators [(1,2,3,4), (5,6,7,8)]
752	Homomorphism : Permutation Group with generators [(1,2,3,4), (5,6,7,8)] --> Cyclic group of order 4 as a permutation group
753	Homomorphism : Permutation Group with generators [(1,2,3,4), (5,6,7,8)] --> Cyclic group of order 4 as a permutation group
754
755	sage: g=D([(1,3),(2,4)]); g
756	(1,3)(2,4)
757	sage: d=D([(1,4,3,2),(5,7),(6,8)]); d
758	(1,4,3,2)(5,7)(6,8)
759	sage: iota1(g); iota2(g); pr1(d); pr2(d)
760	(1,3)(2,4)
761	(5,7)(6,8)
762	(1,4,3,2)
763	(1,3)(2,4)
764
765	"""
766	from sage.groups.perm_gps.permgroup_morphism import PermutationGroupMorphism_from_gap
767	G1 = self._gap_init_()
768	G2 = other._gap_init_()
769	cmd1 = "G:=DirectProduct("+G1+","+G2+")"
770	cmd2 = "iota1:=Embedding(G,1)"
771	cmd3 = "iota2:=Embedding(G,2)"
772	cmd4 = "pr1:=Projection(G,1)"
773	cmd5 = "pr2:=Projection(G,2)"
774	if not(maps):
775	return PermutationGroup(gap.eval(cmd1), from_group = True)
776	else:
777	D = PermutationGroup_generic(gap.eval(cmd1), from_group = True)
778	iota1 = PermutationGroupMorphism_from_gap(self,D, cmd2, "iota1")
779	iota2 = PermutationGroupMorphism_from_gap(other,D, cmd3, "iota2")
780	pr1 = PermutationGroupMorphism_from_gap(D,self, cmd4, "pr1")
781	pr2 = PermutationGroupMorphism_from_gap(D,other, cmd5, "pr2")
782	return D,iota1,iota2,pr1,pr2
783
784	def subgroup(self,gens):
785	"""
786	Wraps the PermutationGroup_subgroup constructor. The argument gens is
787	a list of elements of self.
788
789	EXAMPLES:
790	sage: G = PermutationGroup([(1,2,3),(3,4,5)])
791	sage: g = G((1,2,3))
792	sage: G.subgroup([g])
793	Subgroup of Permutation Group with generators [(1,2,3), (3,4,5)] generated by [(1,2,3)]
794
795	"""
796	return PermutationGroup_subgroup(self,gens)
797
798	def sylow_subgroup(self, p):
799	"""
800	Returns a Sylow p-subgroups of the finite group G, where p is
801	a prime. This is a p-subgroup of G whose index in G is coprime to p.
802	Wraps the GAP function SylowSubgroup.
803
804	EXAMPLES:
805	sage: G = PermutationGroup(['(1,2,3)', '(2,3)'])
806	sage: G.sylow_subgroup(2)
807	Permutation Group with generators [(2,3)]
808	sage: G.sylow_subgroup(5)
809	Permutation Group with generators [()]
810
811	"""
812	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
813	G = self
814	gap.eval("G := %s"%G._gap_init_())
815	gap.eval("Ssgp := SylowSubgroup(G, %s);"%p)
816	gap.eval("gens := GeneratorsOfGroup( Ssgp );")
817	N = Integer(gap.eval("N := Length(gens);"))
818	if N>0:
819	gens = [PermutationGroupElement(gap.eval("gens[%s];"%j)) for j in range(1,N+1)]
820	H = PermutationGroup(gens)
821	else:
822	H = PermutationGroup([()])
823	return H
824
825	def quotient_group(self, N):
826	"""
827	Returns the quotient group permgp/N, where N is a normal subgroup. Wraps the
828	GAP operator "/".
829
830	EXAMPLES:
831	sage: G = PermutationGroup([(1,2,3), (2,3)])
832	sage: N = PermutationGroup([(1,2,3)])
833	sage: G.quotient_group(N)
834	Permutation Group with generators [(1,2)]
835
836	"""
837	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
838	G = self
839	gap.eval("G := %s"%G._gap_())
840	gap.eval("N := %s"%N._gap_())
841	gap.eval(" Q := G/N;")
842	gap.eval("phi := RegularActionHomomorphism( Q );")
843	gap.eval("gens := GeneratorsOfGroup( Image( phi ));")
844	N = Integer(gap.eval("N := Length(gens);"))
845	if N>0:
846	gens = [PermutationGroupElement(gap.eval("gens[%s];"%i)) for i in range(1,N+1)]
847	Q = PermutationGroup(gens)
848	return Q
849	else:
850	return PermutationGroup([()])
851
852	def cohomology(self, n, p = 0):
853	"""
854	Computes the group cohomology H_n(G, F), where F = Z if p=0
855	and F = Z/pZ if p >0 is a prime. Wraps HAP's GroupHomology
856	function, written by Graham Ellis.
857
858	REQUIRES:
859	GAP package HAP (in gap_packages-*.spkg).
860
861	EXAMPLES:
862	sage: G = SymmetricGroup(3)
863	sage: G.cohomology(5) # requires optional gap_packages
864	Trivial Abelian Group
865	sage: G.cohomology(5,2) # requires optional gap_packages
866	Multiplicative Abelian Group isomorphic to C2
867	sage: G.homology(5,3) # requires optional gap_packages
868	Trivial Abelian Group
869	sage: G.homology(5,4) # requires optional gap_packages
870	Traceback (most recent call last):
871	...
872	ValueError: p must be 0 or prime
873
874	This computes $H^4(S_3,ZZ)$, $H^4(S_3,ZZ/2ZZ)$, resp.
875
876	AUTHORS:
877	David Joyner and Graham Ellis
878
879	REFERENCES:
880	G. Ellis, "Computing group resolutions", J. Symbolic Computation. Vol.38, (2004)1077--1118
881	(Available at \code{http://hamilton.nuigalway.ie/}.
882	D. Joyner, "A primer on computational group homology and cohomology",
883	\code{http://front.math.ucdavis.edu/0706.0549}
884
885	"""
886	gap.eval('RequirePackage("HAP")')
887	from sage.rings.arith import is_prime
888	if not (p == 0 or is_prime(p)):
889	raise ValueError, "p must be 0 or prime"
890	G = self
891	GG = G._gap_init_()
892	if p == 0:
893	L = eval(gap.eval("GroupCohomology(%s,%s)"%(GG,n)))
894	else:
895	L = eval(gap.eval("GroupCohomology(%s,%s,%s)"%(GG,n,p)))
896	return AbelianGroup(len(L),L)
897
898	def cohomology_part(self, n, p = 0):
899	"""
900	Computes the p-part of the group cohomology H^n(G, F), where F = Z if p=0
901	and F = Z/pZ if p >0 is a prime. Wraps HAP's Homology function, written by
902	Graham Ellis, applied to the p-Syow subgroup of G.
903
904	REQUIRES:
905	GAP package HAP (in gap_packages-*.spkg).
906
907	EXAMPLES:
908	sage: G = SymmetricGroup(5)
909	sage: G.cohomology_part(7,2) # requires optional gap_packages
910	Multiplicative Abelian Group isomorphic to C2 x C2 x C2
911	sage: G = SymmetricGroup(3)
912	sage: G.cohomology_part(2,3)
913	Multiplicative Abelian Group isomorphic to C3
914
915	AUTHORS:
916	David Joyner and Graham Ellis
917	"""
918	gap.eval('RequirePackage("HAP")')
919	from sage.rings.arith import is_prime
920	if not (p == 0 or is_prime(p)):
921	raise ValueError, "p must be 0 or prime"
922	G = self
923	GG = G._gap_init_()
924	if p == 0:
925	H = AbelianGroup(1,[1])
926	else:
927	gap.eval("S := SylowSubgroup(%s,%s)"%(GG,p))
928	gap.eval("R:=ResolutionFiniteGroup(S,%s)"%(n+1))
929	gap.eval("HR:=HomToIntegers(R)")
930	L = eval(gap.eval("Cohomology(HR,%s)"%n))
931	return AbelianGroup(len(L),L)
932
933	def homology(self, n, p = 0):
934	"""
935	Computes the group homology H_n(G, F), where F = Z if p=0
936	and F = Z/pZ if p >0 is a prime. Wraps HAP's GroupHomology
937	function, written by Graham Ellis.
938
939	REQUIRES:
940	GAP package HAP (in gap_packages-*.spkg).
941
942	AUTHORS:
943	David Joyner and Graham Ellis
944
945	The example below computes $H_7(S_5,ZZ)$, $H_7(S_5,ZZ/2ZZ)$, $H_7(S_5,ZZ/3ZZ)$, and $H_7(S_5,ZZ/5ZZ)$,
946	resp. To compute the $2$-part of $H_7(S_5,ZZ)$, use the \code{homology_part} function.
947
948	EXAMPLES:
949	sage: G = SymmetricGroup(5)
950	sage: G.homology(7) # requires optional gap_packages
951	Multiplicative Abelian Group isomorphic to C2 x C2 x C3 x C4 x C5
952	sage: G.homology(7,2) # requires optional gap_packages
953	Multiplicative Abelian Group isomorphic to C2 x C2 x C2 x C2 x C2
954	sage: G.homology(7,3) # requires optional gap_packages
955	Multiplicative Abelian Group isomorphic to C3
956	sage: G.homology(7,5) # requires optional gap_packages
957	Multiplicative Abelian Group isomorphic to C5
958
959	REFERENCES:
960	G. Ellis, "Computing group resolutions", J. Symbolic Computation. Vol.38, (2004)1077--1118
961	(Available at \code{http://hamilton.nuigalway.ie/}.
962	D. Joyner, "A primer on computational group homology and cohomology",
963	\code{http://front.math.ucdavis.edu/0706.0549}
964
965	"""
966	gap.eval('RequirePackage("HAP")')
967	from sage.rings.arith import is_prime
968	if not (p == 0 or is_prime(p)):
969	raise ValueError, "p must be 0 or prime"
970	G = self
971	GG = G._gap_init_()
972	if p == 0:
973	L = eval(gap.eval("GroupHomology(%s,%s)"%(GG,n)))
974	else:
975	L = eval(gap.eval("GroupHomology(%s,%s,%s)"%(GG,n,p)))
976	return AbelianGroup(len(L),L)
977
978	def homology_part(self, n, p = 0):
979	"""
980	Computes the p-part of the group homology H_n(G, F), where F = Z if p=0
981	and F = Z/pZ if p >0 is a prime. Wraps HAP's Homology function, written by
982	Graham Ellis, applied to the p-Syow subgroup of G.
983
984	REQUIRES:
985	GAP package HAP (in gap_packages-*.spkg).
986
987	EXAMPLES:
988	sage: G = SymmetricGroup(5)
989	sage: G.homology_part(7,2) # requires optional gap_packages
990	Multiplicative Abelian Group isomorphic to C2 x C2 x C2 x C2 x C4
991
992	AUTHORS:
993	David Joyner and Graham Ellis
994	"""
995	gap.eval('RequirePackage("HAP")')
996	from sage.rings.arith import is_prime
997	if not (p == 0 or is_prime(p)):
998	raise ValueError, "p must be 0 or prime"
999	G = self
1000	GG = G._gap_init_()
1001	if p == 0:
1002	H = AbelianGroup(1,[1])
1003	else:
1004	gap.eval("S := SylowSubgroup(%s,%s)"%(GG,p))
1005	gap.eval("R:=ResolutionFiniteGroup(S,%s)"%(n+1))
1006	gap.eval("TR:=TensorWithIntegers(R);")
1007	L = eval(gap.eval("Homology(TR,%s)"%n))
1008	return AbelianGroup(len(L),L)
1009
1010	def poincare_series(self, p=2, n=10):
1011	"""
1012	Returns the Poincare series of G mod p (p must be a prime), for n>1
1013	large. In other words, if you input a finite group G, a prime p,
1014	and a positive integer n, it returns a quotient of polynomials
1015	f(x)=P(x)/Q(x) whose coefficient of $x^k$ equals the rank of the
1016	vector space $H_k(G,ZZ/pZZ)$, for all k in the range $1\leq k \leq n$.
1017
1018	REQUIRES:
1019	GAP package HAP (in gap_packages-*.spkg).
1020
1021	EXAMPLES:
1022	sage: G = SymmetricGroup(5)
1023	sage: G.poincare_series(2,10) # requires optional gap_packages
1024	(x^2 + 1)/(x^4 - x^3 - x + 1)
1025	sage: G = SymmetricGroup(3)
1026	sage: G.poincare_series(2,10) # requires optional gap_packages
1027	1/(-x + 1)
1028
1029	AUTHORS:
1030	David Joyner and Graham Ellis
1031	"""
1032	gap.eval('RequirePackage("HAP")')
1033	from sage.rings.arith import is_prime
1034	if not (p == 0 or is_prime(p)):
1035	raise ValueError, "p must be 0 or prime"
1036	G = self
1037	GG = G._gap_init_()
1038	ff = gap.eval("ff := PoincareSeriesPrimePart(%s,%s,%s)"%(GG,p,n))
1039	R = PolynomialRing(RationalField(),"x")
1040	x = R.gen()
1041	nn = gap.eval("NumeratorOfRationalFunction(ff)")
1042	dd = gap.eval("DenominatorOfRationalFunction(ff)")
1043	FF = FractionField(R)
1044	return FF(nn)/FF(dd)
1045
1046	def molien_series(self):
1047	"""
1048	Returns the Moien series of a transtive permutation group.
1049	The function
1050
1051	M(x) = (1/\|G\|)\sum_{g\in G} det(1-x*g)^(-1)
1052
1053	is sometimes called the "Molien series" of G.
1054	GAP's \code{MolienSeries} is associated to a character of a group G.
1055	How are these related? A group G, given as a permutation
1056	group on n points, has a "natural" representation of
1057	dimension n, given by permutation matrices. The Molien series
1058	of G is the one associated to that permutation representation of
1059	G using the above formula. Character values then count fixed
1060	points of the corresponding permutations.
1061
1062	EXAMPLES:
1063	sage: G = SymmetricGroup(5)
1064	sage: G.molien_series() # requires optional gap_packages
1065	1/(-x^15 + x^14 + x^13 - x^10 - x^9 - x^8 + x^7 + x^6 + x^5 - x^2 - x + 1)
1066	sage: G = SymmetricGroup(3)
1067	sage: G.molien_series() # requires optional gap_packages
1068	1/(-x^6 + x^5 + x^4 - x^2 - x + 1)
1069
1070	"""
1071	G = self
1072	GG = G._gap_init_()
1073	gap.eval("pi := NaturalCharacter( %s )"%GG)
1074	gap.eval("cc := ConstituentsOfCharacter( pi )")
1075	M = gap.eval("M := MolienSeries(Sum(cc))")
1076	R = PolynomialRing(RationalField(),"x")
1077	x = R.gen()
1078	nn = gap.eval("NumeratorOfRationalFunction(M)")
1079	dd = gap.eval("DenominatorOfRationalFunction(M)")
1080	FF = FractionField(R)
1081	return FF(nn.replace("_1",""))/FF(dd.replace("_1",""))
1082
1083	def character_table(self):
1084	r"""
1085	Returns the matrix of values of the irreducible characters of
1086	a permutation group $G$ at the conjugacy classes of $G$. The
1087	columns represent the the conjugacy classes of $G$ and the
1088	rows represent the different irreducible characters in the
1089	ordering given by GAP.
1090
1091	EXAMPLES:
1092	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
1093	sage: G.order()
1094	12
1095	sage: G.character_table()
1096	[ 1 1 1 1]
1097	[ 1 1 -zeta3 - 1 zeta3]
1098	[ 1 1 zeta3 -zeta3 - 1]
1099	[ 3 -1 0 0]
1100	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3)]])
1101	sage: CT = gap(G).CharacterTable()
1102
1103	Type print gap.eval("Display(%s)"%CT.name()) to display this nicely.
1104
1105	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
1106	sage: G.order()
1107	8
1108	sage: G.character_table()
1109	[ 1 1 1 1 1]
1110	[ 1 -1 -1 1 1]
1111	[ 1 -1 1 -1 1]
1112	[ 1 1 -1 -1 1]
1113	[ 2 0 0 0 -2]
1114	sage: CT = gap(G).CharacterTable()
1115
1116	Again, type print gap.eval("Display(%s)"%CT.name()) to display this.
1117
1118	sage: SymmetricGroup(2).character_table()
1119	[ 1 -1]
1120	[ 1 1]
1121	sage: SymmetricGroup(3).character_table()
1122	[ 1 -1 1]
1123	[ 2 0 -1]
1124	[ 1 1 1]
1125	sage: SymmetricGroup(5).character_table()
1126	[ 1 -1 1 1 -1 -1 1]
1127	[ 4 -2 0 1 1 0 -1]
1128	[ 5 -1 1 -1 -1 1 0]
1129	[ 6 0 -2 0 0 0 1]
1130	[ 5 1 1 -1 1 -1 0]
1131	[ 4 2 0 1 -1 0 -1]
1132	[ 1 1 1 1 1 1 1]
1133	sage: list(AlternatingGroup(6).character_table())
1134	[(1, 1, 1, 1, 1, 1, 1), (5, 1, 2, -1, -1, 0, 0), (5, 1, -1, 2, -1, 0, 0), (8, 0, -1, -1, 0, zeta5^3 + zeta5^2 + 1, -zeta5^3 - zeta5^2), (8, 0, -1, -1, 0, -zeta5^3 - zeta5^2, zeta5^3 + zeta5^2 + 1), (9, 1, 0, 0, 1, -1, -1), (10, -2, 1, 1, 0, 0, 0)]
1135
1136	Suppose that you have a class function $f(g)$ on $G$ and you
1137	know the values $v_1, ..., v_n$ on the conjugacy class
1138	elements in \code{conjugacy_classes_representatives(G)} =
1139	$[g_1, \ldots, g_n]$. Since the irreducible characters
1140	$\rho_1, \ldots, \rho_n$ of $G$ form an $E$-basis of the space
1141	of all class functions ($E$ a ``sufficiently large''
1142	cyclotomic field), such a class function is a linear
1143	combination of these basis elements, $f = c_1\rho_1 + \cdots +
1144	c_n\rho_n$. To find the coefficients $c_i$, you simply solve
1145	the linear system \code{character_table_values(G)}*$[v_1, ...,
1146	v_n] = [c_1, ..., c_n]$,
1147	where $[v_1, ...,v_n]$ = \code{character_table_values(G)}$^{-1}[c_1, ...,c_n]$.
1148
1149	AUTHORS:
1150	- David Joyner and William Stein (2006-01-04)
1151	"""
1152	G = self._gap_()
1153	cl = G.ConjugacyClasses()
1154	n = Integer(cl.Length())
1155	irrG = G.Irr()
1156	ct = [[irrG[i+1,j+1] for j in range(n)] for i in range(n)]
1157
1158	# Now we have the tricky task of figuring out what common
1159	# cyclotomic field to put all these cyclotomic elements in.
1160	# Our trick is to compute a list of strings that begin with
1161	# the order of the root of unit for each element followed by ")junk",
1162	# then get rid of the junk.
1163	s = str(ct).split('E(')[1:] # with junk
1164	s = [eval(x.split(')')[0]) for x in s] # get rid of trailing junk
1165
1166	from sage.rings.all import lcm, CyclotomicField
1167	e = lcm(s)
1168
1169	# Now make field and coerce all elements into it.
1170	K = CyclotomicField(e)
1171	ct = [[K(x) for x in v] for v in ct]
1172
1173	# Finally return the result as a matrix.
1174	from sage.matrix.all import MatrixSpace
1175	MS = MatrixSpace(K,n)
1176	return MS(ct)
1177
1178	def conjugacy_classes_representatives(self):
1179	"""
1180	Returns a complete list of representatives of conjugacy classes
1181	in a permutation group G. The ordering is that given by GAP.
1182
1183	EXAMPLES:
1184	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
1185	sage: cl = G.conjugacy_classes_representatives(); cl
1186	[(), (2,4), (1,2)(3,4), (1,2,3,4), (1,3)(2,4)]
1187	sage: cl[3] in G
1188	True
1189
1190	sage: G = SymmetricGroup(5)
1191	sage: G.conjugacy_classes_representatives ()
1192	[(), (1,2), (1,2)(3,4), (1,2,3), (1,2,3)(4,5), (1,2,3,4), (1,2,3,4,5)]
1193
1194
1195	AUTHOR: David Joyner and William Stein (2006-01-04)
1196	"""
1197	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
1198	cl = self._gap_().ConjugacyClasses()
1199	n = Integer(cl.Length())
1200	L = gap("List([1..Length(%s)], i->Representative(%s[i]))"%(
1201	cl.name(), cl.name()))
1202	return [PermutationGroupElement(L[i], self, check=False) \
1203	for i in range(1,n+1)]
1204
1205	def conjugacy_classes_subgroups(self):
1206	"""
1207	Returns a complete list of representatives of conjugacy classes
1208	of subgroups in a permutation group G. The ordering is that given by GAP.
1209
1210	EXAMPLES:
1211	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
1212	sage: cl = G.conjugacy_classes_subgroups()
1213	sage: cl[3]
1214	Group([ (2,4) ])
1215
1216	sage: G = SymmetricGroup(3)
1217	sage: G.conjugacy_classes_subgroups()
1218	[Group(()), Group([ (2,3) ]), Group([ (1,2,3) ]), Group([ (1,3,2), (1,2) ])]
1219
1220	AUTHOR: David Joyner (2006-10)
1221	"""
1222	from sage.groups.perm_gps.permgroup_element import PermutationGroupElement
1223	G = self._gap_()
1224	cl = G.ConjugacyClassesSubgroups()
1225	n = Integer(cl.Length())
1226	L = gap("List([1..Length(%s)], i->Representative(%s[i]))"%(
1227	cl.name(), cl.name()))
1228	return [PermutationGroupElement(L[i], self, check=False) \
1229	for i in range(1,n+1)]
1230
1231	def normalizer(self,g):
1232	"""
1233	Returns the normalizer of g in self.
1234
1235	EXAMPLES:
1236	sage: G = PermutationGroup([[(1,2),(3,4)], [(1,2,3,4)]])
1237	sage: g = G.random_element()
1238	sage: G.normalizer(g) ## random output
1239	Group([ (2,4), (1,3) ])
1240	sage: g = G([(1,2,3,4)])
1241	sage: G.normalizer(g)
1242	Group([ (1,2,3,4), (1,3)(2,4), (2,4) ])
1243
1244	"""
1245	N = self._gap_().Normalizer(str(g))
1246	return N
1247
1248	def isomorphism_type_info_simple_group(self):
1249	"""
1250	Is the group is simple, then this returns the name of the group.
1251
1252	EXAMPLES:
1253	sage: G = CyclicPermutationGroup(5)
1254	sage: G.isomorphism_type_info_simple_group()
1255	rec( series := "Z", parameter := 5, name := "Z(5)" )
1256
1257	"""
1258	if self.is_simple():
1259	info = self._gap_().IsomorphismTypeInfoFiniteSimpleGroup()
1260	return info
1261	else:
1262	return TypeError, "Group must be simple."
1263
1264	###################### Boolean tests #####################
1265
1266	def is_abelian(self):
1267	"""
1268	Return True if this group is abelian.
1269
1270	EXAMPLES:
1271	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1272	sage: G.is_abelian()
1273	False
1274	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1275	sage: G.is_abelian()
1276	True
1277	"""
1278	t = self._gap_().IsAbelian()
1279	return t.bool()
1280
1281	def is_commutative(self):
1282	"""
1283	Return True if this group is commutative.
1284
1285	EXAMPLES:
1286	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1287	sage: G.is_commutative()
1288	False
1289	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1290	sage: G.is_commutative()
1291	True
1292	"""
1293	return self.is_abelian()
1294
1295	def is_cyclic(self):
1296	"""
1297	Return True if this group is cyclic.
1298
1299	EXAMPLES:
1300	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1301	sage: G.is_cyclic()
1302	False
1303	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1304	sage: G.is_cyclic()
1305	True
1306	"""
1307	t = self._gap_().IsCyclic()
1308	return t.bool()
1309
1310	def is_elementary_abelian(self):
1311	"""
1312	Return True if this group is elementary abelian. An elementary abelian
1313	group is a finite Abelian group, where every nontrivial element has order p,
1314	where p is a prime.
1315
1316	EXAMPLES:
1317	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1318	sage: G.is_elementary_abelian()
1319	False
1320	sage: G = PermutationGroup(['(1,2,3)','(4,5,6)'])
1321	sage: G.is_elementary_abelian()
1322	True
1323	"""
1324	t = self._gap_().IsElementaryAbelian()
1325	return t.bool()
1326
1327	def isomorphism_to(self,right,mode=None):
1328	"""
1329	Return an isomorphism self to right if the groups are isomorphic, otherwise None.
1330
1331	EXAMPLES:
1332	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1333	sage: H = PermutationGroup(['(1,2,3)(4,5)'])
1334	sage: G.isomorphism_to(H) is None
1335	True
1336	sage: G = PermutationGroup([(1,2,3), (2,3)])
1337	sage: H = PermutationGroup([(1,2,4), (1,4)])
1338	sage: G.isomorphism_to(H) # random
1339	Homomorphism : Permutation Group with generators [(1,2,3), (2,3)] --> Permutation Group with generators [(1,2,4), (1,4)]
1340	"""
1341	G = self._gap_init_()
1342	H = right._gap_init_()
1343	gap.eval("x:=IsomorphismGroups( %s, %s )"%(G,H))
1344	s = gap.eval("x")
1345	if s == "fail":
1346	return None
1347	# slice and dice the GAP return to build a SAGE group homomorphism
1348	src, dst = s.split("->")
1349	# we eval to get things as lists
1350	srcs = from_gap_list(self, src)
1351	dsts = from_gap_list(right, dst)
1352	from permgroup_morphism import PermutationGroupMorphism_im_gens
1353	return PermutationGroupMorphism_im_gens(self, right, srcs, dsts)
1354
1355	def is_monomial(self):
1356	"""
1357	Returns True if the group is monomial. A finite group is monomial if every irreducible
1358	complex character is induced from a linear character of a subgroup.
1359
1360	EXAMPLES:
1361	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1362	sage: G.is_monomial()
1363	True
1364	"""
1365	ans = self._gap_().IsMonomialGroup()
1366	return ans.bool()
1367
1368	def is_nilpotent(self):
1369	"""
1370	Return True if this group is nilpotent.
1371
1372	EXAMPLES:
1373	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1374	sage: G.is_nilpotent()
1375	False
1376	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1377	sage: G.is_nilpotent()
1378	True
1379	"""
1380	t = self._gap_().IsNilpotent()
1381	return t.bool()
1382
1383	def is_normal(self,other):
1384	"""
1385	Return True if the group self is a normal subgroup of other.
1386
1387	EXAMPLES:
1388	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1389	sage: H = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1390	sage: G.is_normal(H)
1391	True
1392	"""
1393	t = self._gap_().IsNormal(other._gap_())
1394	return t.bool()
1395
1396	def is_perfect(self):
1397	"""
1398	Return True if this group is perfect. A group is perfect if it equals its derived subgroup.
1399
1400	EXAMPLES:
1401	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1402	sage: G.is_perfect()
1403	False
1404	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1405	sage: G.is_perfect()
1406	False
1407	"""
1408	t = self._gap_().IsPerfectGroup()
1409	return t.bool()
1410
1411	def is_pgroup(self):
1412	"""
1413	Returns True if the group is a p-group. A finite group is a p-group if
1414	its order is of the form $p^n$ for a prime integer p and a nonnegative integer n.
1415
1416	EXAMPLES:
1417	sage: G = PermutationGroup(['(1,2,3,4,5)'])
1418	sage: G.is_pgroup()
1419	True
1420	"""
1421	ans = self._gap_().IsPGroup()
1422	return ans.bool()
1423
1424	def is_polycyclic(self):
1425	"""
1426	Return True if this group is polycyclic. A group is polycyclic if it has a subnormal series
1427	with cyclic factors. (For finite groups this is the same as if the group is solvable - see
1428	\code{is_solvable})].)
1429
1430	EXAMPLES:
1431	sage: G = PermutationGroup(['(1,2,3)(4,5)', '(1,2,3,4,5)'])
1432	sage: G.is_polycyclic()
1433	False
1434	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1435	sage: G.is_polycyclic()
1436	True
1437	"""
1438	t = self._gap_().IsPolycyclicGroup()
1439	return t.bool()
1440
1441	def is_simple(self):
1442	"""
1443	Returns True if the group is simple. A group is simple if it has no proper normal
1444	subgroups.
1445
1446	EXAMPLES:
1447	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1448	sage: G.is_simple()
1449	False
1450	"""
1451	ans = self._gap_().IsSimpleGroup()
1452	return ans.bool()
1453
1454	def is_solvable(self):
1455	"""
1456	Returns True if the group is solvable.
1457
1458	EXAMPLES:
1459	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1460	sage: G.is_solvable()
1461	True
1462	"""
1463	ans = self._gap_().IsSolvableGroup()
1464	return ans.bool()
1465
1466	def is_subgroup(self,other):
1467	"""
1468	Returns true if self is a subgroup of other.
1469
1470	EXAMPLES:
1471	sage: G = AlternatingGroup(5)
1472	sage: H = SymmetricGroup(5)
1473	sage: G.is_subgroup(H)
1474	True
1475	"""
1476	G = other
1477	gens = self.gens()
1478	for i in range(len(gens)):
1479	x = gens[i]
1480	if not (G.has_element(x)):
1481	return False
1482	return True
1483
1484	def is_supersolvable(self):
1485	"""
1486	Returns True if the group is supersolvable. A finite group is supersolvable if it has a
1487	normal series with cyclic factors.
1488
1489	EXAMPLES:
1490	sage: G = PermutationGroup(['(1,2,3)(4,5)'])
1491	sage: G.is_supersolvable()
1492	True
1493
1494	"""
1495	ans = self._gap_().IsSupersolvableGroup()
1496	return ans.bool()
1497
1498	############## Series ######################
1499
1500	def composition_series(self):
1501	"""
1502	Return the derived series of this group as a list of
1503	permutation groups.
1504
1505	EXAMPLES:
1506	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
1507	sage: G.composition_series() # somewhat random output
1508	[Permutation Group with generators [(1,2,3)(4,5), (3,4)],
1509	Permutation Group with generators [(1,5)(3,4), (1,5)(2,4), (1,3,5)],
1510	Permutation Group with generators [()]]
1511
1512	"""
1513	ans = []
1514	DS = self._gap_().CompositionSeries()
1515	n = DS.Length()
1516	for i in range(1,n+1):
1517	ans.append(PermutationGroup(DS[i], from_group = True))
1518	return ans
1519
1520	def derived_series(self):
1521	"""
1522	Return the derived series of this group as a list of
1523	permutation groups.
1524
1525	EXAMPLES:
1526	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
1527	sage: G.derived_series() # somewhat random output
1528	[Permutation Group with generators [(1,2,3)(4,5), (3,4)],
1529	Permutation Group with generators [(1,5)(3,4), (1,5)(2,4), (2,4)(3,5)]]
1530	"""
1531	ans = []
1532	DS = self._gap_().DerivedSeries()
1533	n = DS.Length()
1534	for i in range(1,n+1):
1535	ans.append(PermutationGroup(DS[i], from_group = True))
1536	return ans
1537
1538	def lower_central_series(self):
1539	"""
1540	Return the derived series of this group as a list of
1541	permutation groups.
1542
1543	EXAMPLES:
1544	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
1545	sage: G.lower_central_series() # somewhat random output
1546	[Permutation Group with generators [(1,2,3)(4,5), (3,4)],
1547	Permutation Group with generators [(1,5)(3,4), (1,5)(2,4), (1,3,5)]]
1548
1549	"""
1550	ans = []
1551	DS = self._gap_().LowerCentralSeriesOfGroup()
1552	n = DS.Length()
1553	for i in range(1,n+1):
1554	ans.append(PermutationGroup(DS[i], from_group = True))
1555	return ans
1556
1557	def upper_central_series(self):
1558	"""
1559	Return the derived series of this group as a list of
1560	permutation groups.
1561
1562	EXAMPLES:
1563	sage: G = PermutationGroup([[(1,2,3),(4,5)],[(3,4)]])
1564	sage: G.upper_central_series() # somewhat random output
1565	[Permutation Group with generators [()]]
1566	"""
1567	ans = []
1568	DS = self._gap_().UpperCentralSeriesOfGroup()
1569	n = DS.Length()
1570	for i in range(1,n+1):
1571	ans.append(PermutationGroup(DS[i], from_group = True))
1572	return ans
1573
1574	def direct_product_permgroups(P):
1575	"""
1576	Takes the direct product of the permutation groups listed in P.
1577
1578	EXAMPLES:
1579	sage: G1 = AlternatingGroup([1,2,4,5])
1580	sage: G2 = AlternatingGroup([3,4,6,7])
1581	sage: D = direct_product_permgroups([G1,G2,G1])
1582	sage: D.order()
1583	1728
1584	sage: D = direct_product_permgroups([G1])
1585	sage: D==G1
1586	True
1587	sage: direct_product_permgroups([])
1588	Symmetric group of order 0! as a permutation group
1589	"""
1590	from permgroup_named import SymmetricGroup
1591	n = len(P)
1592	if n == 0:
1593	return SymmetricGroup(1)
1594	if n == 1:
1595	return P[0]
1596	from sage.groups.perm_gps.permgroup_morphism import PermutationGroupMorphism_from_gap
1597	G = [H._gap_init_() for H in P]
1598	Glist = ""
1599	for H in G:
1600	Glist = Glist + H + ","
1601	cmd = "G:=DirectProduct([" + Glist[:-1] + "])"
1602	gap.eval(cmd)
1603	return PermutationGroup(gap.eval("G"), from_group = True)
1604
1605
1606	class PermutationGroup_subgroup(PermutationGroup_generic):
1607	"""
1608	Subgroup subclass of PermutationGroup_generic, so instance methods are
1609	inherited.
1610
1611	EXAMPLES:
1612	sage: G = CyclicPermutationGroup(4)
1613	sage: gens = G.gens()
1614	sage: H = DihedralGroup(4)
1615	sage: PermutationGroup_subgroup(H,list(gens))
1616	Subgroup of Dihedral group of order 8 as a permutation group generated by [(1,2,3,4)]
1617	sage: K=PermutationGroup_subgroup(H,list(gens))
1618	sage: K.list()
1619	[(), (1,2,3,4), (1,3)(2,4), (1,4,3,2)]
1620	sage: K.ambient_group()
1621	Dihedral group of order 8 as a permutation group
1622	sage: K.gens()
1623	[(1,2,3,4)]
1624	"""
1625	def __init__(self, ambient, gens, from_group = False,
1626	check=True):
1627	if not isinstance(ambient, PermutationGroup_generic):
1628	raise TypeError, "ambient (=%s) must be perm group."%ambient
1629	if not isinstance(gens, list):
1630	raise TypeError, "gens (=%s) must be a list"%gens
1631	if check:
1632	pass
1633
1634	self.__ambient_group = ambient
1635	self.__gens = gens
1636	cmd = 'Group(%s)'%gens
1637	cmd = cmd.replace("'","") # get rid of quotes
1638	self.__gap = cmd
1639
1640	G = ambient
1641	if check:
1642	for i in range(len(gens)):
1643	x = gens[i]
1644	if not (G.has_element(x)):
1645	raise TypeError, "each generator must be in the ambient group"
1646	self.__ambient_group = G
1647
1648	PermutationGroup_generic.__init__(self, gens, from_group, check)
1649
1650	def __cmp__(self, other):
1651	r"""
1652	Compare self and other. If self and other are in a common ambient group,
1653	then self <= other precisely if self is contained in other.
1654
1655	EXAMPLES:
1656	sage: G = CyclicPermutationGroup(4)
1657	sage: gens = G.gens()
1658	sage: H = DihedralGroup(4)
1659	sage: PermutationGroup_subgroup(H,list(gens))
1660	Subgroup of Dihedral group of order 8 as a permutation group generated by [(1,2,3,4)]
1661	sage: K=PermutationGroup_subgroup(H,list(gens))
1662	sage: G<K
1663	False
1664	sage: G>K
1665	False
1666	"""
1667	if self is other:
1668	return 0
1669	if not isinstance(other, PermutationGroup_generic):
1670	return -1
1671	c = cmp(self.ambient_group(), other.ambient_group())
1672	if c: return c
1673	if self.is_subgroup(other):
1674	return -1
1675	else:
1676	return 1
1677
1678	def _repr_(self):
1679	s = "Subgroup of %s generated by %s"%(self.ambient_group(), self.gens())
1680	return s
1681
1682	def _latex_(self):
1683	r"""
1684	Return latex representation of this group.
1685	"""
1686	return self._repr_()
1687
1688
1689	def ambient_group(self):
1690	"""
1691	Return the ambient group related to self.
1692	"""
1693	return self.__ambient_group
1694
1695	def gens(self):
1696	"""
1697	Return the generators for this subgroup.
1698	"""
1699	return self.__gens
1700

Note: See TracBrowser for help on using the repository browser.

Download in other formats: