presentation of finite group

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Results in the Presentation of Finite Groups

I've been looking at combinatorial group theory, but all the results seem to be about infinite groups. Are there any important results about the presentations finite groups specifically (or are useful for finite groups?). About how the minimum number of relations implies something about the structure of the group?

I'd prefer results that are applicable to all finite groups or to all finite simple or all simple groups.

• presentations-of-groups
• gr.group-theory
• combinatorial-group-theory

• 2 $\begingroup$ There's the Golod-Shafarevich inequality for finite p-groups, closely related to the still open conjecture of whether the minimal number of relators for a finite p-group is equal to the dimension of its second cohomology (mod p). $\endgroup$ –  Steve D Commented Mar 8, 2012 at 4:43
• $\begingroup$ @Steve D: As you gave the above comment, I would like to know if you have any comment on this question: mathoverflow.net/questions/209438/… $\endgroup$ –  Alireza Abdollahi Commented Jun 18, 2015 at 10:51

3 Answers 3

One such result that springs to mind is that, if the finite group $G$ has a presentation with $r$ generators and $s$ relations, then the Schur Multiplier $M(G) = H_2(G)$ of $G$ can be generated by at most $s-r$ elements. So in particular $s \ge r$. (Of course you can prove that more directly - a finitely presented group with $s<r$ has infinite abelianization.)

We can deduce for example that a finite abelian group $G$ of rank $r$ requires at least $r(r+1)/2$ relations to present it, because $M(G)$ has rank $r(r-1)/2$. In this case the converse holds - the obvious presentation of $G$ has $r$ generators and $r(r+1)/2$ relations.

The converse does not hold in general. Swan constructed examples of finite solvable groups with trivial multiplier and arbitrarily large minimum $s-r$. But I believe it is still an open problem for finite $p$-groups. i.e. does every $d$-generator finite $p$-group have a presentation with $d$ generators and $d + {\rm rk}(M(G))$ relations?

Finite groups of defect 0 - i.e. $r=s$ have also been much studied. There are lots of 2-generator examples known, a few 3-generator examples and none requiring 4 or more generators.

• 1 $\begingroup$ I'd like to also mention that given a finite presentation for a finite group $G$, there is an algorithm for computing the Schur multiplier. If $G=\langle X\ |\ R\rangle$, then the subgroup $H=\langle R\rangle$ is central in $\langle X\ |\ [X,R]\rangle$. It is a finitely generated abelian group, and its torsion subgroup is $M(G)$. This is not hard to prove using Hopf's formula, and every step is something a computer can do (presentation of finite index subgroup, abelianization, etc.). $\endgroup$ –  Steve D Commented Mar 8, 2012 at 4:45

Yes, of course, here are a few examples:

Finite Coxeter groups (see any book on Coxeter groups), they are given by their presentations.

Finite simple groups, see http://pages.uoregon.edu/kantor/PAPERS/GKKL2.pdf and references there.

The result by Guralnick, Kantor, Kassabov and Lubotzky (which is mentioned already in Mark Sapir's answer) is one of the most striking results in finite group theory of the last decade, in my opinion. It shows that there is a uniform bound on the length of the presentation for (probably all) nonabelian finite simple groups. This is much stronger than what anyone before this result even conjectured, so it's absolutely amazing. More precisely, they show the following:

All nonabelian finite simple groups of rank $n$ over a field of size $q$, with the possible exception of the Ree groups $^2G_2$, have presentations with at most 80 relations and bit-length $O(\log n + \log q)$.

(By the way, the assumption "nonabelian" is essential, the theorem is false for cyclic groups of prime order!) Their results appeared in a series of 3 papers:

• Presentation of finite simple groups: a quantitative approach
• Presentation of finite simple groups: cohomological and profinite approaches
• Presentation of finite simple groups: a computational approach

I would recommend you to have a look at the first of those 3 papers, it contains a wealth of information about presentations of finite (simple) groups, and it is written in a very readable and enjoyable style.

• $\begingroup$ It's not clear from what you write what exactly is false for abelian simple groups! Cyclic groups of order $n$ have a presentation of total length at most $O(\log n)$, but not with a fixed number of generators and relations. $\endgroup$ –  Derek Holt Commented Mar 8, 2012 at 9:56

Your Answer

Sign up or log in, post as a guest.

Required, but never shown

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy .

Not the answer you're looking for? Browse other questions tagged presentations-of-groups gr.group-theory combinatorial-group-theory or ask your own question .

• Featured on Meta
• Bringing clarity to status tag usage on meta sites
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Announcing a change to the data-dump process

presentation of a group

The standard notation for the presentation of a group is

Title	presentation of a group
Canonical name	PresentationOfAGroup
Date of creation	2013-03-22 12:23:23
Last modified on	2013-03-22 12:23:23
Owner	rmilson (146)
Last modified by	rmilson (146)
Numerical id	20
Author	rmilson (146)
Entry type
	msc 20A05
Classification	msc 20F05
Synonym	presentation
Synonym	finite presentation
Synonym	finitely presented
Related topic	GeneratingSetOfAGroup
Related topic	CayleyGraph
Defines	generator
Defines	relation
Defines	generators and relations
Defines	relator

Stack Exchange Network

Stack Exchange network consists of 183 Q&A communities including Stack Overflow , the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Q&A for work

Connect and share knowledge within a single location that is structured and easy to search.

A finitely presented group $G$ is given by a presentation $\langle S,R\rangle$, where $R$ is finite. Show that $S$ is finite.

We were asked to prove this theorem in an exercise. This is what I have thus far:

Suppose $S$ were infinite. Denote the set of symbols of $S$ that do not occur in any relation by $S'$. Then the free group $F_{S'}$ is isomorphic to a subgroup of $G$. Because $R$ is finite and $S$ is infinite, $S'$ must be infinite so $F_{S'}$ has infinite rank.

This is where I'm stuck. I initially thought that this would be enough to conclude that $G$ has no finite presentation, but finitely presented groups can have free groups with infinite rank as subgroups, right?

Any help is appreciated.

• abstract-algebra
• group-theory
• group-presentation

• $\begingroup$ What is your definition of "finitely presented"? I'm used to "both finitely generated and finitely related". $\endgroup$ –  Eric Towers Commented Jun 11, 2014 at 15:06
• $\begingroup$ Sorry, I should have been more clear: A group is finitely presented if and only if it has a presentation $<S,R>$ where $S$ and $R$ are finite. $\endgroup$ –  mval Commented Jun 11, 2014 at 15:07
• $\begingroup$ Then the question is vacuous. A non-vacuous version of the question would be "A given finitely presented group G has another presentation $\langle S, R \rangle$ with $R$ finite. Show $S$ is finite." $\endgroup$ –  Eric Towers Commented Jun 11, 2014 at 15:09
• 1 $\begingroup$ @Eric, a finitely presented group can still have a presentation with infinitely many generators. The proposition is saying that if a presentation has finitely many relations, then this cannot be the case. $\endgroup$ –  Dan Rust Commented Jun 11, 2014 at 15:10
• 5 $\begingroup$ Pedants like to distinguish between a finitely presentable group, which means that is can be defined by a finite presentation, and a finitely presented group, which means that is defined by a finite presentation. $\endgroup$ –  Derek Holt Commented Jun 11, 2014 at 15:32

2 Answers 2

Just kill the generators $S^{\prime}$.

More formally: Let $G=\langle S; R\rangle$ be finitely presentable and assume that $R$ is finite. Suppose $S$ is infinite. Then kill every generator which appears (or its inverse appears) in any relator from $R$. You are left with an infinitely generated free group, hence your group $G$ cannot be finitely generated, and hence $G$ is not finitely presentable. This is a contradiction, and so $S$ must be finite.

(If you are comfortable with free products: If $S$ is infinite then define $S_1$ as follows. $$S_1:=\{g\in S; s\text{ or }s^{-1}\text{ occurs in some relator from }R\}$$ Define $S_2$ to be such that $S=S_1\coprod S_2$. Then $G=\langle S_1, S_2; R\rangle$ is the free product $\langle S_1; R\rangle\ast F(S_2)$. Because $S$ is infinite but $S_1$ is finite, $S_2$ must be infinite, hence $F(S_2)$ is infinitely generated free. What the above paragraph does is kill the generators $S_1$ and you are left with $F(S_2)$.)

A finitely presented group must have a presentation with a finite set of generators (be finitely generated) and a finite set of relations (finitely related). You have shown that if $S$ is infinite and $R$ is finite (for a given $S$ and $R$ ), then $G$ can not be finitely presented as it would not be finitely generated. It follows that if $G$ is finitely presented, $S$ must be finite.

• $\begingroup$ I'm not sure I quite understand. I have proven that $G$ has a subgroup that is not finitely generated. As far as I know, finitely presented groups can have infinitely generated subgroups. Would you mind explaining how you got around this problem? $\endgroup$ –  mval Commented Jun 11, 2014 at 15:13
• 1 $\begingroup$ Define a homomorphism $f\colon G\to\langle S'\rangle$ by $f(s)=e$ if $s\notin S'$ and $f(s)=s$ if $s\in S'$. This morphism splits and so $G$ is actually isomorphic to $\langle S\setminus S'\mid R\rangle\rtimes\langle S'\rangle$ which can not be finitely generated. $\endgroup$ –  Dan Rust Commented Jun 11, 2014 at 15:17
• $\begingroup$ Ah, I suppose that a finite product is finitely generated iff its factors are finitely generated? I suppose that makes sense. $\endgroup$ –  mval Commented Jun 11, 2014 at 15:20
• 1 $\begingroup$ I think if $G$ is finitely generated, then $G/N$ is finitely generated because the image of the generators of $G$ form a generating set for $G/N$. The contrapositive of this statement would imply that if $\langle S'\rangle\cong G/\langle S\setminus S'\mid R\rangle$ is infinitely generated (which it is), then $G$ is infinitely generated. $\endgroup$ –  Dan Rust Commented Jun 11, 2014 at 15:29
• 1 $\begingroup$ I should have amended the above comments, the kernel of the homomorphism $f$ is not $\langle S\setminus S'\mid R\rangle$ (as this is not a normal subgroup), it is just the normaliser of the subgroup $\langle S\setminus S'\rangle$ $\endgroup$ –  Dan Rust Commented Jun 11, 2014 at 16:49

You must log in to answer this question.

Not the answer you're looking for browse other questions tagged abstract-algebra group-theory group-presentation ..

• Featured on Meta
• We've made changes to our Terms of Service & Privacy Policy - July 2024
• Bringing clarity to status tag usage on meta sites
• 2024 Community Moderator Election
• 2024 Election Results: Congratulations to our new moderator!

Hot Network Questions

• "Authorized ESTA After Incorrectly Answering Criminal Offense Question: What Should I Do?"
• What's the proper way to shut down after a kernel panic?
• Purpose of burn permit?
• How to make a ParametricPlot3D into solid shape
• Why does a 240V dryer heating element have 3+1 terminals?
• Is it OK to make an "offshape" bid if you can handle any likely response?
• Which cards use −5 V and −12 V in IBM PC compatible systems?
• Where should the chess pieces be placed in 4x4, 6x6 and 9x9 chessboards?
• A simplified Blackjack C++ OOP console game
• How to attach a 4x8 plywood to a air hockey table
• How can I draw water level in a cylinder like this?
• Trying to find an old book (fantasy or scifi?) in which the protagonist and their romantic partner live in opposite directions in time
• How Can this Limit be really Evaluated?
• Interpretation of the ideal gas single particle partition function
• Reduce String Length With Thread Safety & Concurrency
• Sci-fi short story about a dystopian future where all natural resources had been used up and people were struggling to survive
• How do I safely remove a mystery cast iron pipe in my basement?
• What is it called when perception of a thing is replaced by an pre-existing abstraction of that thing?
• Need strftime() output in the buffer
• Inconsistent “unzip -l … | grep -q …” results with pipefail
• Is it possible to do physics without mathematics?
• Meaning of て form here: 「あなたどう思って？」と聞いた。
• degeneration of a Veronese surface
• When was this photo taken?

Finite Group

A finite group is a group having finite group order . Examples of finite groups are the modulo multiplication groups , point groups , cyclic groups , dihedral groups , symmetric groups , alternating groups , and so on.

Properties of finite groups are implemented in the Wolfram Language as FiniteGroupData [ group , prop ].

The classification theorem of finite groups states that the finite simple groups can be classified completely into one of five types.

A convenient way to visualize groups is using so-called cycle graphs , which show the cycle structure of a given abstract group . For example, cycle graphs of the 5 nonisomorphic groups of order 8 are illustrated above (Shanks 1993, p. 85).

Frucht's theorem states that every finite group is the graph automorphism group of a finite undirected graph .

1246789111213141516182022232425262730

#	Abelian	#	non-Abelian	total
1		0	-	1
1		0	-	1
3	1		0	-	1
2		0	-	2
5	1		0	-	1
1		1		2
1		0	-	1
3		2		5
2		0	-	2
10	1		1		2
1		0	-	1
2		3		5
1		0	-	1
1		1		2
1		0	-	1
5		9		14
17	1		0	-	1
2		3		5
19	1		0	-	1
2		3		5
21	1		1		2
1		1		2
1		0	-	1
3		12		15
2		0	-	2
1		1		2
3		2		5
28	2		2		4
29	1		0	-	1
4		3		4
31	1		0	-	1

12345691011121314

group	Abelian	PG	MMG						counts of
	yes	yes	yes	1	1	1	1	1	1
	yes	yes	no	2		2	1, 2	2	1, 2
	yes	yes	yes	3		2	1, 3	2	1, 1, 3
	yes	yes	yes	4		3	1, 2, 4	3	1, 2, 1, 4
		yes	no	yes	4		5	1,	5	1, 4, 1, 4
	yes	yes	no	5		2	1, 4	2	1, 1, 1, 1, 5
	yes	yes	yes	6		4	1, 2, 3, 6	4	1, 2, 3, 2, 1, 6
	no	yes	no	3	1, 2, 3	6	1,	3	1, 4, 3, 4, 1, 6
7		yes	yes	no	7		2	1, 7	2	1, 1, 1, 1, 1, 1, 7
8		yes	yes	yes	8		4	1, 2, 4, 8	4	1, 2, 1, 4, 1, 2, 1, 8
	yes	no	yes	8		8	1,	4	1, 4, 1, 8, 1, 4, 1, 8
	yes	no	yes	8		16	1,	4	1, 8, 1, 8, 1, 8, 1, 8
	no	yes	no	5		10	1,	6	1, 6, 1, 8, 1, 6, 1, 8
	no	no	no	5		6	1, 2,	6	1, 2, 1, 8, 1, 2, 1, 8
	yes	yes	no	9		3	1, 3, 9	3	1, 1, 3, 1, 1, 3, 1, 1, 9
	yes	no	no
	yes	yes	yes	10		4	1, 2, 5, 10	4	1, 2, 1, 2, 5, 2, 1, 2, 1, 10
	no	yes	no	4	1,	8	1,	3	1, 6, 1, 6, 5, 6, 1, 6, 1, 10
	yes	yes	no	11		2	1, 11	2	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 11
	yes	yes	yes	12		6	1, 2, 3, 4, 6, 12	6	1, 2, 3, 4, 1, 6, 1, 4, 3, 2, 1, 12
	yes	no	yes	12		10	1,	10	1, 4, 3, 4, 1, 12, 1, 4, 3, 4, 1, 12
	no	yes	no	4	1, 3,	10	1,	3	1, 4, 9, 4, 1, 12, 1, 4, 9, 4, 1, 12
	no	yes	no	6		16	1,	8	1, 8, 3, 8, 1, 12, 1, 8, 3, 8, 1, 12
	no	no	no	6		8	1, 2, 3,	3	1, 2, 3, 8, 1, 6, 1, 8, 3, 2, 1, 12
	yes	yes	yes	13		2	1, 13	2	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 13
	yes	yes	no	14		4	1, 2, 7, 14	4	1, 2, 1, 2, 1, 2, 7, 2, 1, 2, 1, 2, 1, 14
		no	yes	no	5	1,	10	1,	3	1, 8, 1, 8, 1, 8, 7, 8, 1, 8, 1, 8, 1, 14
15		yes	yes	no	15		4	1, 3, 5, 15	4	1, 1, 3, 1, 5, 3, 1, 1, 3, 5, 1, 3, 1, 1, 15

124568910121314161718202122242526282930323334363738404142434445474849

1	1	51	1	1	101	1	1	151	1	1
1	1	52	5	2	102	4	1	152	12	3
3	1	1	53	1	1	103	1	1	153	2	2
2	2	54	15	3	104	14	3	154	4	1
1	1	55	2	1	105	2	1	155	2	1
2	1	56	13	3	106	2	1	156	18	2
7	1	1	57	2	1	107	1	1	157	1	1
5	3	58	2	1	108	45	6	158	2	1
2	2	59	1	1	109	1	1	159	1	1
2	1	60	13	2	110	6	1	160	238	7
11	1	1	61	1	1	111	2	1	161	1	1
5	2	62	2	1	112	43	5	162	55	5
1	1	63	4	2	113	1	1	163	1	1
2	1	64	267	11	114	6	1	164	5	2
15	1	1	65	1	1	115	1	1	165	2	1
14	5	66	4	1	116	5	2	166	2	1
1	1	67	1	1	117	4	2	167	1	1
5	2	68	5	2	118	2	1	168	57	3
19	1	1	69	1	1	119	1	1	169	2	2
5	2	70	4	1	120	47	3	170	4	1
2	1	71	1	1	121	2	2	171	5	2
2	1	72	50	6	122	2	1	172	4	2
23	1	1	73	1	1	123	1	1	173	1	1
15	3	74	2	1	124	4	2	174	4	1
2	2	75	3	2	125	5	3	175	2	2
2	1	76	4	2	126	16	2	176	42	5
27	5	3	77	1	1	127	1	1	177	1	1
4	2	78	6	1	128	2328	15	178	2	1
1	1	79	1	1	129	2	1	179	1	1
4	1	80	52	5	130	4	1	180	37	4
31	1	1	81	15	5	131	1	1	181	1	1
51	7	82	2	1	132	10	2	182	4	1
1	1	83	1	1	133	1	1	183	2	1
2	1	84	15	2	134	2	1	184	12	3
35	1	1	85	1	1	135	5	3	185	1	1
14	4	86	2	1	136	15	3	186	6	1
1	1	87	1	1	137	1	1	187	1	1
2	1	88	12	3	138	4	1	188	4	2
39	2	1	89	1	1	139	1	1	189	13	3
14	3	90	10	2	140	11	2	190	4	1
1	1	91	1	1	141	1	1	191	1	1
6	1	92	4	2	142	2	1	192	1543	11
1	1	93	2	1	143	1	1	193	1	1
4	2	94	2	1	144	197	10	194	2	1
2	2	95	1	1	145	1	1	195	2	1
46	2	1	96	231	7	146	2	1	196	17	4
1	1	97	1	1	147	6	2	197	1	1
52	5	98	5	2	148	5	2	198	10	2
2	2	99	2	2	149	1	1	199	1	1
50	5	2	100	16	4	150	13	2	200	52	6

201202204205206208209210212213214216217218220221222224225226228229230232233234235236237239240241243244245247248249

2	1	251	1	1	301	2	1	351	14	3
2	1	252	46	4	302	2	1	352	195	7
203	2	1	253	2	1	303	1	1	353	1	1
12	2	254	2	1	304	42	5	354	4	1
2	1	255	1	1	305	2	1	355	2	1
2	1	256	56092	22	306	10	2	356	5	2
207	2	2	257	1	1	307	1	1	357	2	1
51	5	258	6	1	308	9	2	358	2	1
1	1	259	1	1	309	2	1	359	1	1
12	1	260	15	2	310	6	1	360	162	6
211	1	1	261	2	2	311	1	1	361	2	2
5	2	262	2	1	312	61	3	362	2	1
1	1	263	1	1	313	1	1	363	3	2
2	1	264	39	3	314	2	1	364	11	2
215	1	1	265	1	1	315	4	2	365	1	1
177	9	266	4	1	316	4	2	366	6	1
1	1	267	1	1	317	1	1	367	1	1
2	1	268	4	2	318	4	1	368	42	5
219	2	1	269	1	1	319	1	1	369	2	2
15	2	270	30	3	320	1640	11	370	4	1
1	1	271	1	1	321	1	1	371	1	1
6	1	272	54	5	322	4	1	372	15	2
223	1	1	273	5	1	323	1	1	373	1	1
197	7	274	2	1	324	176	10	374	4	1
6	4	275	4	2	325	2	2	375	7	3
2	1	276	10	2	326	2	1	376	12	3
227	1	1	277	1	1	327	2	1	377	1	1
15	2	278	2	1	328	15	3	378	60	3
1	1	279	4	2	329	1	1	379	1	1
4	1	280	40	3	330	12	1	380	11	2
231	2	1	281	1	1	331	1	1	381	2	1
14	3	282	4	1	332	4	2	382	2	1
1	1	283	1	1	333	5	2	383	1	1
16	2	284	4	2	334	2	1	384	20169	15
1	1	285	2	1	335	1	1	385	2	1
4	2	286	4	1	336	228	5	386	2	1
2	1	287	1	1	337	1	1	387	4	2
238	4	1	288	1045	14	338	5	2	388	5	2
1	1	289	2	2	339	1	1	389	1	1
208	5	290	4	1	340	15	2	390	12	1
1	1	291	2	1	341	1	1	391	1	1
242	5	2	292	5	2	342	18	2	392	44	6
67	7	293	1	1	343	5	3	393	1	1
5	2	294	23	2	344	12	3	394	2	1
2	2	295	1	1	345	1	1	395	1	1
246	4	1	296	14	3	346	2	1	396	30	4
1	1	297	5	3	347	1	1	397	1	1
12	3	298	2	1	348	12	2	398	2	1
1	1	299	1	1	349	1	1	399	5	1
250	15	3	300	49	4	350	10	2	400	221	10

Explore with Wolfram|Alpha

More things to try:

• finite group
• 5th minterm in 3 variables
• Dynamic options

Referenced on Wolfram|Alpha

Cite this as:.

Weisstein, Eric W. "Finite Group." From MathWorld --A Wolfram Web Resource. https://mathworld.wolfram.com/FiniteGroup.html

Subject classifications

Representation Theory of Finite Groups: a Guidebook

• © 2019
• David A. Craven 0

School of Mathematics, University of Birmingham, Birmingham, UK

You can also search for this author in PubMed   Google Scholar

• Provides an overview of the whole subject of representation theory of finite groups
• A unique survey of current research aimed at beginning researchers
• Only basic knowledge is assumed with most topics covered in a self-contained fashion

Part of the book series: Universitext (UTX)

25k Accesses

13 Citations

1 Altmetric

This is a preview of subscription content, log in via an institution to check access.

Access this book

Subscribe and save.

• Get 10 units per month
• Download Article/Chapter or eBook
• 1 Unit = 1 Article or 1 Chapter
• Cancel anytime
• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

About this book

This book provides an accessible introduction to the state of the art of representation theory of finite groups. Starting from a basic level that is summarized at the start, the book proceeds to cover topics of current research interest, including open problems and conjectures.

The central themes of the book are block theory and module theory of group representations, which are comprehensively surveyed with a full bibliography. The individual chapters cover a range of topics within the subject, from blocks with cyclic defect groups to representations of symmetric groups.

Assuming only modest background knowledge at the level of a first graduate course in algebra, this guidebook, intended for students taking first steps in the field, will also provide a reference for more experienced researchers. Although no proofs are included, end-of-chapter exercises make it suitable for student seminars.

Similar content being viewed by others

Research in Representation Theory of Finite Groups

IntroSurvey of Representation Theory

Subgroup structure and representations of finite and algebraic groups.

• Group representation
• Representations of finite groups
• Representations of symmetric groups
• Finite groups of Lie type
• Block theory
• Modular representation theory
• Local-global conjectures
• Blocks with cyclic defect groups

Table of contents (9 chapters)

Front matter.

David A. Craven

Blocks and Their Characters

The local-global principle, blocks with cyclic defect groups, blocks with non-cyclic defect groups, clifford theory, representations of symmetric groups, representations of groups of lie type, back matter.

“The book is intended for students and general readers. ... each of the chapters is followed by a series of exercises (83 in all), which are suitable for student seminars.” (A. S. Kondrat'ev, Mathematical Reviews, November, 2020)

“The book is highly recommended for researchers in representation and character theory of finite groups.” (Mohammad-Reza Darafsheh, zbMATH 1446.20002, 2020)

Authors and Affiliations

About the author, bibliographic information.

Book Title : Representation Theory of Finite Groups: a Guidebook

Authors : David A. Craven

Series Title : Universitext

DOI : https://doi.org/10.1007/978-3-030-21792-1

Publisher : Springer Cham

eBook Packages : Mathematics and Statistics , Mathematics and Statistics (R0)

Copyright Information : Springer Nature Switzerland AG 2019

Softcover ISBN : 978-3-030-21791-4 Published: 16 September 2019

eBook ISBN : 978-3-030-21792-1 Published: 30 August 2019

Series ISSN : 0172-5939

Series E-ISSN : 2191-6675

Edition Number : 1

Number of Pages : VIII, 294

Number of Illustrations : 49 b/w illustrations

Topics : Group Theory and Generalizations , Associative Rings and Algebras , Category Theory, Homological Algebra

• Publish with us

Policies and ethics

• Find a journal
• Track your research

www.springer.com The European Mathematical Society

• StatProb Collection
• Recent changes
• Current events
• Random page
• Project talk
• Request account
• What links here
• Related changes
• Special pages
• Printable version
• Permanent link
• Page information
• View source

Finitely-presented group

A group on finitely many generators defined by finitely many relations between these generators. Up to an isomorphism, there are countably many such groups. Every set of defining relations between the elements of any finite generating set of a finitely-presented group contains a finite set of defining relations in these generators.

[1]	A.G. Kurosh, "The theory of groups" , , Chelsea (1955–1956) (Translated from Russian)

A finitely-presented group is isomorphic to a quotient group $F/N(R)$, where $F$ is a free group of finite rank and $N(R)$ is the smallest normal subgroup of $F$ containing a given finite subset $R$ of $F$ (the set of relations).

Some standard references on group presentations are [a1] – [a4] .

[a1]	H.S.M. Coxeter, W.O.J. Moser, "Generators and relations for discrete groups" , Springer (1984)
[a2]	D.L. Johnson, "Presentations of groups" , Cambridge Univ. Press (1988)
[a3]	R.C. Lyndon, P.E. Schupp, "Combinatorial group theory" , Springer (1977)
[a4]	W. Magnus, A. Karrass, B. Solitar, "Combinatorial group theory: presentations in terms of generators and relations" , Wiley (Interscience) (1966)

• Group theory and generalizations
• This page was last edited on 26 October 2014, at 18:26.
• Privacy policy
• About Encyclopedia of Mathematics
• Disclaimers
• Impressum-Legal

[MathJax on]

47 Finitely Presented Groups

A finitely presented group (in short: FpGroup) is a group generated by a finite set of abstract generators subject to a finite set of relations that these generators satisfy. Every finite group can be represented as a finitely presented group, though in almost all cases it is computationally much more efficient to work in another representation (even the regular permutation representation).

Finitely presented groups are obtained by factoring a free group by a set of relators. Their elements know about this presentation and compare accordingly.

So to create a finitely presented group you first have to generate a free group (see  FreeGroup ( 37.2-1 ) for details). There are two ways to specify a quotient of the free group: either by giving a list of relators or by giving a list of equations. Relators are just words in the generators of the free group. Equations are represented as pairs of words in the generators of the free group. In either case the generators of the quotient are the images of the free generators under the canonical homomorphism from the free group onto the quotient. So for example to create the group

⟨ a, b ∣ a^2, b^3, (a b)^5 ⟩

you can use the following commands:

Note that you cannot call the generators by their names. These names are not variables, but just display figures. So, if you want to access the generators by their names, you first have to introduce the respective variables and to assign the generators to them.

To relieve you of the tedium of typing the above assignments, when working interactively , there is the function AssignGeneratorVariables ( 37.2-3 ).

Note that the generators of the free group are different from the generators of the FpGroup (even though they are displayed by the same names). That means that words in the generators of the free group are not elements of the finitely presented group. Vice versa elements of the FpGroup are not words.

Such calculations comparing elements of an FpGroup may run into problems: There exist finitely presented groups for which no algorithm exists (it is known that no such algorithm can exist) that will tell for two arbitrary words in the generators whether the corresponding elements in the FpGroup are equal.

Therefore the methods used by GAP to compute in finitely presented groups may run into warning errors, run out of memory or run forever. If the FpGroup is (by theory) known to be finite the algorithms are guaranteed to terminate (if there is sufficient memory available), but the time needed for the calculation cannot be bounded a priori. See 47.6 and 47.16 .

A consequence of our convention is that elements of finitely presented groups are not printed in a unique way. See also SetReducedMultiplication ( 47.3-4 ).

47.1 IsSubgroupFpGroup and IsFpGroup

47.1-1 issubgroupfpgroup.

( )	( category )

is the category for finitely presented groups or subgroups of a finitely presented group.

47.1-2 IsFpGroup

( )	( filter )

is a synonym for IsSubgroupFpGroup( G ) and IsGroupOfFamily( G ) .

Free groups are a special case of finitely presented groups, namely finitely presented groups with no relators.

Note that FreeGroup(infinity) (which exists e.g. for purposes of rewriting presentations with further generators) satisfies this filter, though of course it is not finitely generated (and thus not finitely presented). IsFpGroup thus is not a proper property test and slightly misnamed for the sake of its most prominent uses.

Another special case are groups given by polycyclic presentations. GAP uses a special representation for these groups which is created in a different way. See chapter 46 for details.

47.1-3 InfoFpGroup

( info class )

The info class for functions dealing with finitely presented groups is InfoFpGroup .

47.2 Creating Finitely Presented Groups

( , )

( method )

creates a finitely presented group given by the presentation ⟨ gens ∣ rels ⟩ or ⟨ gens ∣ eqns ⟩ , respectively where gens are the free generators of the free group F . Relations can be entered either as words or as pairs of words in the generators of F . In the former case we refer to the words given as relators , in the latter we refer to the pairs of words as equations . The two methods can currently not be mixed.

The same result is obtained with the infix operator / , i.e., as F / rels .

47.2-2 FactorGroupFpGroupByRels

( , )

( function )

returns the factor group G / N of G by the normal closure N of elts where elts is expected to be a list of elements of G .

47.2-3 ParseRelators

Will translate a list of relations as given in print, e.g. x y^2 = (x y^3 x)^2 xy = yzx into relators. gens must be a list of generators of a free group, each being displayed by a single letter. rels is a string that lists a sequence of equalities. These must be written in the letters which are the names of the generators in gens . Change of upper/lower case is interpreted to indicate inverses.

47.2-4 StringFactorizationWord

( )	( function )

returns a string that expresses a given word w in compact form written as a string. Inverses are expressed by changing the upper/lower case of the generators, recurring expressions are written as products.

47.3 Comparison of Elements of Finitely Presented Groups

Two elements of a finitely presented group are equal if they are equal in this group. Nevertheless they may be represented as different words in the generators. Because of the fundamental problems mentioned in the introduction to this chapter such a test may take very long and cannot be guaranteed to finish.

The method employed by GAP for such an equality test use the underlying finitely presented group. First (unless this group is known to be infinite) GAP tries to find a faithful permutation representation by a bounded Todd-Coxeter. If this fails, a Knuth-Bendix (see 52.5 ) is attempted and the words are compared via their normal form.

If only elements in a subgroup are to be tested for equality it thus can be useful to translate the problem in a new finitely presented group by rewriting (see IsomorphismFpGroup ( 47.11-1 ));

The equality test of elements underlies many basic calculations, such as the order of an element, and the same type of problems can arise there. In some cases, working with rewriting systems can still help to solve the problem. The kbmag package provides such functionality, see the package manual for further details.

47.3-2 \<

Compared with equality testing, problems get even worse when trying to compute a total ordering on the elements of a finitely presented group. As any ordering that is guaranteed to be reproducible in different runs of GAP or even with different groups given by syntactically equal presentations would be prohibitively expensive to implement, the ordering of elements is depending on a method chosen by GAP and not guaranteed to stay the same when repeating the construction of an FpGroup. The only guarantee given for the < ordering for such elements is that it will stay the same for one family during its lifetime. The attribute FpElmComparisonMethod ( 47.3-3 ) is used to obtain a comparison function for a family of FpGroup elements.

47.3-3 FpElmComparisonMethod

( )	( attribute )

If fam is the elements family of a finitely presented group this attribute returns a function smaller( left , right ) that will be used to compare elements in fam .

47.3-4 SetReducedMultiplication

For an FpGroup obj , an element obj of it or the family obj of its elements, this function will force immediate reduction when multiplying, keeping words short at extra cost per multiplication.

47.4 Preimages in the Free Group

47.4-1 freegroupoffpgroup.

returns the underlying free group for the finitely presented group G . This is the group generated by the free generators provided by the FreeGeneratorsOfFpGroup ( 47.4-2 ) value of G .

47.4-2 FreeGeneratorsOfFpGroup

( )	( operation )

FreeGeneratorsOfFpGroup returns the underlying free generators corresponding to the generators of the finitely presented group G which must be a full FpGroup.

FreeGeneratorsOfWholeGroup also works for subgroups of an FpGroup and returns the free generators of the full group that defines the family.

47.4-3 RelatorsOfFpGroup

returns the relators of the finitely presented group G as words in the free generators provided by the FreeGeneratorsOfFpGroup ( 47.4-2 ) value of G .

Note that these attributes are only available for the full finitely presented group. It is possible (for example by using Subgroup ( 39.3-1 )) to construct a subgroup of index 1 which is not identical to the whole group. The latter one can be obtained in this situation via Parent ( 31.7-1 ).

Elements of a finitely presented group are not words, but are represented using a word from the free group as representative. The following two commands obtain this representative, respectively create an element in the finitely presented group.

47.4-4 UnderlyingElement

Let elm be an element of a group whose elements are represented as words with further properties. Then UnderlyingElement returns the word from the free group that is used as a representative for elm .

47.4-5 ElementOfFpGroup

( , )

( operation )

If fam is the elements family of a finitely presented group and word is a word in the free generators underlying this finitely presented group, this operation creates the element with the representative word in the free group.

47.5 Operations for Finitely Presented Groups

Finitely presented groups are groups and so all operations for groups should be applicable to them (though not necessarily efficient methods are available). Most methods for finitely presented groups rely on coset enumeration. See  47.6 for details.

The command IsomorphismPermGroup ( 43.3-1 ) can be used to obtain a faithful permutation representation, if such a representation of small degree exists. (Otherwise it might run very long or fail.)

47.5-1 PseudoRandom

( )	( method )

The default algorithm for PseudoRandom ( 30.7-2 ) makes little sense for finitely presented or free groups, as it produces words that are extremely long.

By specifying the option radius , instead elements are taken as words in the generators of F in the ball of radius l with equal distribution in the free group.

47.6 Coset Tables and Coset Enumeration

Coset enumeration (see [Neu82] for an explanation) is one of the fundamental tools for the examination of finitely presented groups. This section describes GAP functions that can be used to invoke a coset enumeration.

Note that in addition to the built-in coset enumerator there is the GAP package ACE . Moreover, GAP provides an interactive Todd-Coxeter in the GAP package ITC which is based on the XGAP package.

47.6-1 CosetTable

returns the coset table of the finitely presented group G on the cosets of the subgroup H .

Basically a coset table is the permutation representation of the finitely presented group on the cosets of a subgroup (which need not be faithful if the subgroup has a nontrivial core). Most of the set theoretic and group functions use the regular representation of G , i.e., the coset table of G over the trivial subgroup.

The coset table is returned as a list of lists. For each generator of G and its inverse the table contains a generator list. A generator list is simply a list of integers. If l is the generator list for the generator g and if l[i] = j then generator g takes the coset i to the coset j by multiplication from the right. Thus the permutation representation of G on the cosets of H is obtained by applying PermList ( 42.5-2 ) to each generator list.

The coset table is standard (see below).

For finitely presented groups, a coset table is computed by a Todd-Coxeter coset enumeration. Note that you may influence the performance of that enumeration by changing the values of the global variables CosetTableDefaultLimit ( 47.6-7 ) and CosetTableDefaultMaxLimit ( 47.6-6 ) described below and that the options described under CosetTableFromGensAndRels ( 47.6-5 ) are recognized.

The last printout in the preceding example provides the coset table in the form in which it is usually used in hand calculations: The rows correspond to the cosets, the columns correspond to the generators and their inverses in the ordering g_1, g_1^{-1}, g_2, g_2^{-1} . (See section  47.7 for a description on the way the numbers are assigned.)

47.6-2 TracedCosetFpGroup

( , , )

( function )

Traces the coset number pt under the word word through the coset table tab . (Note: word must be in the free group, use UnderlyingElement ( 47.4-4 ) if in doubt.)

47.6-3 FactorCosetAction

returns the action of G on the cosets of its subgroup H .

47.6-4 CosetTableBySubgroup

returns a coset table for the action of G on the cosets of H . The columns of the table correspond to the GeneratorsOfGroup ( 39.2-4 ) value of G .

47.6-5 CosetTableFromGensAndRels

is an internal function which is called by the functions CosetTable ( 47.6-1 ), CosetTableInWholeGroup ( 47.8-1 ) and others. It is, in fact, the workhorse that performs a Todd-Coxeter coset enumeration. fgens must be a set of free generators and grels a set of relators in these generators. fsgens are subgroup generators expressed as words in these generators. The function returns a coset table with respect to fgens .

CosetTableFromGensAndRels will call TCENUM.CosetTableFromGensAndRels . This makes it possible to replace the built-in coset enumerator with another one by assigning TCENUM to another record.

The library version which is used by default performs a standard Felsch strategy coset enumeration. You can call this function explicitly as GAPTCENUM.CosetTableFromGensAndRels even if other coset enumerators are installed.

The expected parameters are

generators of the free group F

relators as words in F

subgroup generators as words in F .

CosetTableFromGensAndRels processes two options (see chapter  8 ):

The limit of the number of cosets to be defined. If the enumeration does not finish with this number of cosets, an error is raised and the user is asked whether she wants to continue. The default value is the value given in the variable CosetTableDefaultMaxLimit . (Due to the algorithm the actual limit used can be a bit higher than the number given.)

If set to true the algorithm will not raise the error mentioned under option max but silently return fail . This can be useful if an enumeration is only wanted unless it becomes too big.

47.6-6 CosetTableDefaultMaxLimit

( global variable )

is the default limit for the number of cosets allowed in a coset enumeration.

A coset enumeration will not finish if the subgroup does not have finite index, and even if it has it may take many more intermediate cosets than the actual index of the subgroup is. To avoid a coset enumeration running away therefore GAP has a safety stop built in. This is controlled by the global variable CosetTableDefaultMaxLimit .

If this number of cosets is reached, GAP will issue an error message and prompt the user to either continue the calculation or to stop it. The default value is 4096000 .

See also the description of the options to CosetTableFromGensAndRels ( 47.6-5 ).

At this point, a break -loop (see Section  6.4 ) has been entered. The line beginning Error tells you why this occurred. The next seven lines occur if OnBreak ( 6.4-3 ) has its default value Where ( 6.4-5 ). They explain, in this case, how GAP came to be doing a coset enumeration. Then you are given a number of options of how to escape the break -loop: you can either continue the calculation with a larger number of permitted cosets, stop the calculation if you don't expect the enumeration to finish (like in the example above), or continue without a limit on the number of cosets. (Choosing the first option will, of course, land you back in a break -loop. Try it!)

Setting CosetTableDefaultMaxLimit (or the max option value, for any function that invokes a coset enumeration) to infinity ( 18.2-1 ) (or to 0 ) will force all coset enumerations to continue until they either get a result or exhaust the whole available space. For example, each of the following two inputs

have essentially the same effect as choosing the third option (typing: maxlimit := 0; return; ) at the brk> prompt above (instead of quit; ).

47.6-7 CosetTableDefaultLimit

is the default number of cosets with which any coset table is initialized before doing a coset enumeration.

The function performing this coset enumeration will automatically extend the table whenever necessary (as long as the number of cosets does not exceed the value of CosetTableDefaultMaxLimit ( 47.6-6 )), but this is an expensive operation. Thus, if you change the value of CosetTableDefaultLimit , you should set it to a number of cosets that you expect to be sufficient for your subsequent coset enumerations. On the other hand, if you make it too large, your job will unnecessarily waste a lot of space.

The default value of CosetTableDefaultLimit is 1000 .

47.6-8 MostFrequentGeneratorFpGroup

is an internal function which is used in some applications of coset table methods. It returns the first of those generators of the given finitely presented group G which occur most frequently in the relators.

47.6-9 IndicesInvolutaryGenerators

returns the indices of those generators of the finitely presented group G which are known to be involutions. This knowledge is used by internal functions to improve the performance of coset enumerations.

47.7 Standardization of coset tables

For any two coset numbers i and j with i < j the first occurrence of i in a coset table precedes the first occurrence of j with respect to the usual row-wise ordering of the table entries. Following the notation of Charles Sims' book on computation with finitely presented groups [Sim94] we call such a table a standard coset table .

The table entries which contain the first occurrences of the coset numbers i > 1 recursively provide for each i a representative of the corresponding coset in form of a unique word w_i in the generators and inverse generators of G . The first coset (which is H itself) can be represented by the empty word w_1 . A coset table is standard if and only if the words w_1, w_2, ... are length-plus-lexicographic ordered (as defined in [Sim94] ), for short: lenlex .

This standardization of coset tables is different from that used in GAP versions 4.2 and earlier. Before that, we ignored the columns that correspond to inverse generators and hence only considered words in the generators of G . We call this older ordering the semilenlex standard as it also applies to the case of semigroups where no inverses of the generators are known.

We changed our default from the semilenlex standard to the lenlex standard to be consistent with [Sim94] . However, the semilenlex standardisation remains available and the convention used for all implicit standardisations can be selected by setting the value of the global variable CosetTableStandard ( 47.7-1 ) to either "lenlex" or "semilenlex" . Independent of the current value of CosetTableStandard ( 47.7-1 ) you can standardize (or restandardize) a coset table at any time using StandardizeTable ( 47.7-2 ).

47.7-1 CosetTableStandard

specifies the definition of a standard coset table . It is used whenever coset tables or augmented coset tables are created. Its value may be "lenlex" or "semilenlex" . If it is "lenlex" coset tables will be standardized using all their columns as defined in Charles Sims' book (this is the new default standard of GAP ). If it is "semilenlex" they will be standardized using only their generator columns (this was the original GAP standard). The default value of CosetTableStandard is "lenlex" .

47.7-2 StandardizeTable

standardizes the given coset table table . The second argument is optional. It defines the standard to be used, its values may be "lenlex" or "semilenlex" specifying the new or the old convention, respectively. If no value for the parameter standard is provided the function will use the global variable CosetTableStandard ( 47.7-1 ) instead. Note that the function alters the given table, it does not create a copy.

47.8 Coset tables for subgroups in the whole group

47.8-1 cosettableinwholegroup.

is equivalent to CosetTable( G , H ) where G is the (unique) finitely presented group such that H is a subgroup of G . It overrides a silent option (see  CosetTableFromGensAndRels ( 47.6-5 )) with false .

The variant TryCosetTableInWholeGroup does not override the silent option with false in case a coset table is only wanted if not too expensive. It will store a result that is not fail in the attribute CosetTableInWholeGroup .

47.8-2 SubgroupOfWholeGroupByCosetTable

takes a family fpfam of an FpGroup and a standardized coset table tab and returns the subgroup of fpfam !.wholeGroup defined by this coset table. The function will not check whether the coset table is standardized. See also  CosetTableBySubgroup ( 47.6-4 ).

47.9 Augmented Coset Tables and Rewriting

47.9-1 augmentedcosettableinwholegroup.

( [, ] )

( function )

For a subgroup H of a finitely presented group, this function returns an augmented coset table. If a generator set gens is given, it is guaranteed that gens will be a subset of the primary and secondary subgroup generators of this coset table.

It is mutable so we are permitted to add further entries. However existing entries may not be changed. Any entries added however should correspond to the subgroup only and not to a homomorphism.

47.9-2 AugmentedCosetTableMtc

( , , , )

( function )

is an internal function used by the subgroup presentation functions described in 48.2 . It applies a Modified Todd-Coxeter coset representative enumeration to construct an augmented coset table (see 48.2 ) for the given subgroup H of G . The subgroup generators will be named string 1 , string 2 , ... .

The function accepts the options max and silent as described for the function CosetTableFromGensAndRels ( 47.6-5 ).

47.9-3 AugmentedCosetTableRrs

is an internal function used by the subgroup presentation functions described in 48.2 . It applies the Reduced Reidemeister-Schreier method to construct an augmented coset table for the subgroup of G which is defined by the given coset table table . The new subgroup generators will be named string 1 , string 2 , ... .

47.9-4 RewriteWord

RewriteWord rewrites word (which must be a word in the underlying free group with respect to which the augmented coset table aug is given) in the subgroup generators given by the augmented coset table aug . It returns a Tietze-type word (i.e. a list of integers), referring to the primary and secondary generators of aug .

If word is not contained in the subgroup, fail is returned.

47.10 Low Index Subgroups

47.10-1 lowindexsubgroupsfpgroupiterator.

( [, ], [, ] )

( operation )

These functions compute representatives of the conjugacy classes of subgroups of the finitely presented group G that contain the subgroup H of G and that have index less than or equal to index .

LowIndexSubgroupsFpGroupIterator returns an iterator (see  30.8 ) that can be used to run over these subgroups, and LowIndexSubgroupsFpGroup returns the list of these subgroups. If one is interested only in one or a few subgroups up to a given index then preferably the iterator should be used.

If the optional argument excluded has been specified, then it is expected to be a list of words in the free generators of the underlying free group of G , and LowIndexSubgroupsFpGroup returns only those subgroups of index at most index that contain H , but do not contain any conjugate of any of the group elements defined by these words.

If not given, H defaults to the trivial subgroup.

The algorithm used finds the requested subgroups by systematically running through a tree of all potential coset tables of G of length at most index (where it skips all branches of that tree for which it knows in advance that they cannot provide new classes of such subgroups). The time required to do this depends, of course, on the presentation of G , but in general it will grow exponentially with the value of index . So you should be careful with the choice of index .

By default, the algorithm computes no generating sets for the subgroups. This can be enforced with GeneratorsOfGroup ( 39.2-4 ):

If we are interested just in one (proper) subgroup of index at most 10 , we can use the function that returns an iterator. The first subgroup found is the group itself, except if a list of excluded elements is entered (see below), so we look at the second subgroup.

As an example for an application of the optional parameter excluded , we compute all conjugacy classes of torsion free subgroups of index at most 24 in the group G = ⟨ x,y,z ∣ x^2, y^4, z^3, (xy)^3, (yz)^2, (xz)^3 ⟩ . It is know from theory that each torsion element of this group is conjugate to a power of x , y , z , xy , xz , or yz . (Note that this includes conjugates of y^2 .)

If a particular image group is desired, the operation GQuotients ( 40.9-4 ) (see  47.14 ) can be useful as well.

47.11 Converting Groups to Finitely Presented Groups

47.11-1 isomorphismfpgroup.

returns an isomorphism from the given finite group G to a finitely presented group isomorphic to G . The function first chooses a set of generators of G and then computes a presentation in terms of these generators.

47.11-2 IsomorphismFpGroupByGenerators

( , [, ] )

( function )

( , , )

( operation )

returns an isomorphism from a finite group G to a finitely presented group F isomorphic to G . The generators of F correspond to the generators of G given in the list gens . If string is given it is used to name the generators of the finitely presented group.

The NC version will avoid testing whether the elements in gens generate G .

The main task of the function IsomorphismFpGroupByGenerators is to find a presentation of G in the provided generators gens . In the case of a permutation group G it does this by first constructing a stabilizer chain of G and then it works through that chain from the bottom to the top, recursively computing a presentation for each of the involved stabilizers. The method used is essentially an implementation of John Cannon's multi-stage relations-finding algorithm as described in [Neu82] (see also [Can73] for a more graph theoretical description). Moreover, it makes heavy use of Tietze transformations in each stage to avoid an explosion of the total length of the relators.

Note that because of the random methods involved in the construction of the stabilizer chain the resulting presentations of G will in general be different for repeated calls with the same arguments.

Also in the case of a permutation group G , the function IsomorphismFpGroupByGenerators supports the option method that can be used to modify the strategy. The option method may take the following values.

This may be specified for groups of small size, up to 10^5 say. It implies that the function first constructs a regular representation R of G and then a presentation of R . In general, this presentation will be much more concise than the default one, but the price is the time needed for the construction of R .

This is a refinement of the previous possibility. In this case, bound should be an integer, and if so the method "regular" as described above is applied to the largest stabilizer in the stabilizer chain of G whose size does not exceed the given bound and then the multi-stage algorithm is used to work through the chain from that subgroup to the top.

This chooses an alternative method which essentially is a kind of multi-stage algorithm for a stabilizer chain of G but does not make any attempt do reduce the number of relators as it is done in Cannon's algorithm or to reduce their total length. Hence it is often much faster than the default method, but the total length of the resulting presentation may be huge.

This simply means that the default method shall be used, which is the case if the option method is not given a value.

Though the option method := "regular" is only checked in the case of a permutation group it also affects the performance and the results of the function IsomorphismFpGroupByGenerators for other groups, e. g. for matrix groups. This happens because, for these groups, the function first calls the function NiceMonomorphism ( 40.5-2 ) to get a bijective action homomorphism from G to a suitable permutation group, P say, and then, recursively, calls itself for the group P so that now the option becomes relevant.

Since GAP cannot decompose elements of a matrix group into generators, the resulting isomorphism is stored as a composition of a (faithful) permutation action on vectors and a homomorphism from the permutation image to the finitely presented group. In such a situation the constituent mappings can be obtained via ConstituentsCompositionMapping ( 32.2-8 ) as separate GAP objects.

47.12 New Presentations and Presentations for Subgroups

IsomorphismFpGroup ( 47.11-1 ) is also used to compute a new finitely presented group that is isomorphic to the given subgroup of a finitely presented group. (This is typically the only method to compute with subgroups of a finitely presented group.)

When working with such homomorphisms, some subgroup elements are expressed as extremely long words in the group generators. Therefore the underlying words of subgroup generators stored in the isomorphism (as obtained by MappingGeneratorsImages ( 40.10-2 ) and displayed when View ( 6.3-3 )ing the homomorphism) as well as preimages under the homomorphism are stored in the form of straight line program elements (see  37.9 ). These will behave like ordinary words and no extra treatment should be necessary.

If desired, it also is possible to convert these underlying words using EvalStraightLineProgElm ( 37.9-4 ):

(If you are only interested in a finitely presented group isomorphic to the given subgroup but not in the isomorphism, you may also use the functions PresentationViaCosetTable ( 48.1-5 ) and FpGroupPresentation ( 48.1-4 ) (see 48.1 ).)

Homomorphisms can also be used to obtain an isomorphic finitely presented group with a (hopefully) simpler presentation.

47.12-1 IsomorphismSimplifiedFpGroup

applies Tietze transformations to a copy of the presentation of the given finitely presented group G in order to reduce it with respect to the number of generators, the number of relators, and the relator lengths.

The operation returns an isomorphism with source G , range a group H isomorphic to G , so that the presentation of H has been simplified using Tietze transformations.

IsomorphismSimplifiedFpGroup uses Tietze transformations to simplify the presentation, see 48.1-6 .

47.13 Preimages under Homomorphisms from an FpGroup

For some subgroups of a finitely presented group the number of subgroup generators increases with the index of the subgroup. However often these generators are not needed at all for further calculations, but what is needed is the action of the cosets of the subgroup. This gives the image of the subgroup in a finite quotient and this finite quotient can be used to calculate normalizers, closures, intersections and so forth  [Hul01] .

The same applies for subgroups that are obtained as preimages under homomorphisms.

47.13-1 SubgroupOfWholeGroupByQuotientSubgroup

takes a FpGroup family fpfam , a finitely generated group Q such that the fp generators of fpfam can be mapped by an epimorphism phi onto the GeneratorsOfGroup ( 39.2-4 ) value of Q , and a subgroup U of Q . It returns the subgroup of fpfam !.wholeGroup which is the full preimage of U under phi .

47.13-2 IsSubgroupOfWholeGroupByQuotientRep

( )	( representation )

is the representation for subgroups of an FpGroup, given by a quotient subgroup. The components G !.quot and G !.sub hold quotient, respectively subgroup.

47.13-3 AsSubgroupOfWholeGroupByQuotient

returns the same subgroup in the representation AsSubgroupOfWholeGroupByQuotient .

See also SubgroupOfWholeGroupByCosetTable ( 47.8-2 ) and CosetTableBySubgroup ( 47.6-4 ).

This technique is used by GAP for example to represent the derived subgroup, which is obtained from the quotient G/G' .

47.13-4 DefiningQuotientHomomorphism

if U is a subgroup in quotient representation ( IsSubgroupOfWholeGroupByQuotientRep ( 47.13-2 )), this function returns the defining homomorphism from the whole group to U !.quot .

47.14 Quotient Methods

An important class of algorithms for finitely presented groups are the quotient algorithms which compute quotient groups of a given finitely presented group. There are algorithms for epimorphisms onto abelian groups, p -groups and solvable groups. (The low index algorithm – LowIndexSubgroupsFpGroup ( 47.10-1 )– can be considered as well as an algorithm that produces permutation group quotients.)

MaximalAbelianQuotient ( 39.18-4 ), as defined for general groups, returns the largest abelian quotient of the given group.

47.14-1 PQuotient

( , [, ][, ][, ] )

( function )

computes a factor p -group of a finitely presented group F in form of a quotient system. The quotient system can be converted into an epimorphism from F onto the p -group computed by the function EpimorphismQuotientSystem ( 47.14-2 ).

For a group G define the exponent- p central series of G inductively by cal P_1(G) = G and cal P_{i+1}(G) = [cal P_i(G),G]cal P_{i+1}(G)^p . The factor groups modulo the terms of the lower exponent- p central series are p -groups. The group G has p -class c if cal P_c(G) ≠ cal P_{c+1}(G) = 1 .

The algorithm computes successive quotients modulo the terms of the exponent- p central series of F . If the parameter c is present, then the factor group modulo the (c+1) -th term of the exponent- p central series of F is returned. If c is not present, then the algorithm attempts to compute the largest factor p -group of F . In case F does not have a largest factor p -group, the algorithm will not terminate.

By default the algorithm computes only with factor groups of order at most p^256 . If the parameter logord is present, it will compute with factor groups of order at most p^ logord . If this parameter is specified, then the parameter c must also be given. The present implementation produces an error message if the order of a p -quotient exceeds p^256 or p^ logord , respectively. Note that the order of intermediate p -groups may be larger than the final order of a p -quotient.

The parameter ctype determines the type of collector that is used for computations within the factor p -group. ctype must either be "single" in which case a simple collector from the left is used or "combinatorial" in which case a combinatorial collector from the left is used.

47.14-2 EpimorphismQuotientSystem

For a quotient system quotsys obtained from the function PQuotient ( 47.14-1 ), this operation returns an epimorphism F → P where F is the finitely presented group of which quotsys is a quotient system and P is a pc group isomorphic to the quotient of F determined by quotsys .

Different calls to this operation will create different groups P , each with its own family.

47.14-3 EpimorphismPGroup

( , [, ] )

( operation )

computes an epimorphism from the finitely presented group fpgrp to the largest p -group of p -class cl which is a quotient of fpgrp . If cl is omitted, the largest finite p -group quotient (of p -class up to 1000 ) is determined.

47.14-4 EpimorphismNilpotentQuotient

returns an epimorphism on the class n finite nilpotent quotient of the finitely presented group fpgrp . If n is omitted, the largest finite nilpotent quotient (of p -class up to 1000 ) is taken.

A related operation which is also applicable to finitely presented groups is GQuotients ( 40.9-4 ), which computes all epimorphisms from a (finitely presented) group F onto a given (finite) group G .

47.14-5 SolvableQuotient

This routine calls the solvable quotient algorithm for a finitely presented group F . The quotient to be found can be specified in the following ways: Specifying an integer size finds a quotient of size up to size (if such large quotients exist). Specifying a list of primes in primes finds the largest quotient involving the given primes. Finally tuples can be used to prescribe a chief series.

SQ can be used as a synonym for SolvableQuotient .

47.14-6 EpimorphismSolvableQuotient

computes an epimorphism from the finitely presented group fpgrp to the largest solvable quotient given by param (specified as in SolvableQuotient ( 47.14-5 )).

47.14-7 LargerQuotientBySubgroupAbelianization

Let hom a homomorphism from a finitely presented group G to a finite group H and U ≤ H . This function will –if it exists– return a subgroup S ≤ G , such that the core of S is properly contained in the kernel of hom as well as in the derived subgroup of V , where V is the pre-image of U under hom . Thus S exposes a larger quotient of G . If no such subgroup exists, fail is returned.

47.15 Abelian Invariants for Subgroups

Using variations of coset enumeration it is possible to compute the abelian invariants of a subgroup of a finitely presented group without computing a complete presentation for the subgroup in the first place. Typically, the operation AbelianInvariants ( 39.16-1 ) when called for subgroups should automatically take care of this, but in case you want to have further control about the methods used, the following operations might be of use.

47.15-1 AbelianInvariantsSubgroupFpGroup

AbelianInvariantsSubgroupFpGroup is a synonym for AbelianInvariantsSubgroupFpGroupRrs ( 47.15-3 ).

47.15-2 AbelianInvariantsSubgroupFpGroupMtc

uses the Modified Todd-Coxeter method to compute the abelian invariants of a subgroup H of a finitely presented group G .

47.15-3 AbelianInvariantsSubgroupFpGroupRrs

uses the Reduced Reidemeister-Schreier method to compute the abelian invariants of a subgroup H of a finitely presented group G .

Alternatively to the subgroup H , its coset table table in G may be given as second argument.

47.15-4 AbelianInvariantsNormalClosureFpGroup

AbelianInvariantsNormalClosureFpGroup is a synonym for AbelianInvariantsNormalClosureFpGroupRrs ( 47.15-5 ).

47.15-5 AbelianInvariantsNormalClosureFpGroupRrs

uses the Reduced Reidemeister-Schreier method to compute the abelian invariants of the normal closure of a subgroup H of a finitely presented group G . See 48.2 for details on the different strategies.

The following example shows a calculation for the Coxeter group B_1 . This calculation and a similar one for B_0 have been used to prove that B_1' / B_1'' ≅ Z_2^9 × Z^3 and B_0' / B_0'' ≅ Z_2^91 × Z^27 as stated in in [FJNT95, Proposition 5] .

47.16 Testing Finiteness of Finitely Presented Groups

As a consequence of the algorithmic insolvabilities mentioned in the introduction to this chapter, there cannot be a general method that will test whether a given finitely presented group is actually finite.

Therefore testing the finiteness of a finitely presented group can be problematic. What GAP actually does upon a call of IsFinite ( 30.4-2 ) (or if it is –probably implicitly– asked for a faithful permutation representation) is to test whether it can find (via coset enumeration) a cyclic subgroup of finite index. If it can, it rewrites the presentation to this subgroup. Since the subgroup is cyclic, its size can be checked easily from the resulting presentation, the size of the whole group is the product of the index and the subgroup size. Since however no bound for the index of such a subgroup (if any exist) is known, such a test might continue unsuccessfully until memory is exhausted.

On the other hand, a couple of methods exist, that might prove that a group is infinite. Again, none is guaranteed to work in every case:

The first method is to find (for example via the low index algorithm, see  LowIndexSubgroupsFpGroup ( 47.10-1 )) a subgroup U such that [U:U'] is infinite. If U has finite index, this can be checked by IsInfiniteAbelianizationGroup ( 47.16-1 ).

Note that this test has been done traditionally by checking the AbelianInvariants ( 39.16-1 ) (see section  47.15 ) of U , IsInfiniteAbelianizationGroup ( 47.16-1 ) does a similar calculation but stops as soon as it is known whether 0 is an invariant without computing the actual values. This can be notably faster.

Another method is based on p -group quotients, see NewmanInfinityCriterion ( 47.16-2 ).

47.16-1 IsInfiniteAbelianizationGroup

( )	( property )

returns true if the commutator factor group G / G ' is infinite. This might be done without computing the full structure of the commutator factor group.

47.16-2 NewmanInfinityCriterion

Let G be a finitely presented group and p a prime that divides the order of the commutator factor group of G . This function applies an infinity criterion due to M. F. Newman [New90] to G . (See [Joh97, chapter 16] for a more explicit description.) It returns true if the criterion succeeds in proving that G is infinite and fail otherwise.

Note that the criterion uses the number of generators and relations in the presentation of G . Reduction of the presentation via Tietze transformations ( IsomorphismSimplifiedFpGroup ( 47.12-1 )) therefore might produce an isomorphic group, for which the criterion will work better.

This proves that the subgroup k (and thus the whole group g ) is infinite. (This is the original example from  [New90] .)

generated by GAPDoc2HTML

arXiv's Accessibility Forum starts next month!

Help | Advanced Search

Mathematics > Group Theory

Title: finite-dimensional pseudofinite groups of small dimension, without cfsg.

Abstract: Any simple pseudofinite group G is known to be isomorphic to a (twisted) Chevalley group over a pseudofinite field. This celebrated result mostly follows from the work of Wilson in 1995 and heavily relies on the classification of finite simple groups (CFSG). It easily follows that G is finite-dimensional with additive and fine dimension and, in particular, that if dim(G)=3 then G is isomorphic to PSL(2,F) for some pseudofinite field F. We describe pseudofinite finite-dimensional groups when the dimension is fine, additive and \<4 and, in particular, show that the classification G isomorphic to PSL(2,F) is independent from CFSG.

Subjects:	Group Theory (math.GR); Logic (math.LO)
Cite as:	[math.GR]
	(or [math.GR] for this version)
	Focus to learn more arXiv-issued DOI via DataCite

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs .