Group presentation ($⟨S\mid R⟩$)

A group presentation $⟨S\mid R⟩$ describes the quotient of the free group $F(S)$ by the normal closure of the relators $R$. It is finite when both $S$ and $R$ are finite.

A recursive presentation has an effectively enumerable alphabet of generators and a recursively enumerable set of relators. Usually the alphabet is finite; when it is countably infinite this is specified explicitly. Enumerating finite products of conjugates of relators and their inverses enumerates all null words. Conversely the enumerable null words can themselves serve as the relators. Recursive presentability does not imply a soluble word problem for a group.

A finitely generated group embeds in a finitely presented group if and only if it has a recursive presentation of a group. The necessity follows by enumerating proofs that substituted generator words are trivial in the larger finite group presentation. The sufficiency is the embedding theorem; it also applies to effectively countably generated recursive presentations after an effective two-generator embedding. This is the theorem of Subgroups of finitely presented groups.

For a group presentation $\mathcal{P}=⟨X\mid R⟩$ with finitely many generators and a prime number $p$, defineThis uses the unshifted convention. Identity relators have zero weight, and a divergent sum gives value $-\infty$. Some literature subtracts one instead; inequalities must be shifted accordingly. Taking roots in the free group matters: roots appearing only after passing to the quotient do not change the relator weight. The p-rank of a group bounds this quantity above, and the index-p rewriting bound for p-deficiency gives the infinitude criterion p-deficiency at least one implies infinitude.

Enumerate all nonidentity words $w_i$ in the rank-two free group and impose relations $w_i^{p^{i+2}}=1$. The resulting two-generated group hasIt is infinite by p-deficiency at least one implies infinitude. Each element has order a power of $p$, so it is a torsion group. The infinitely many relators are essential to this particular construction; finite generation does not imply a finite group presentation.

If a group presentation has unshifted p-deficiency at least one, the p-rank of a group is at least one and gives a normal subgroup of index $p$. The index-p rewriting bound for p-deficiency gives this subgroup another presentation with p-deficiency at least one. Iterating produces subgroups of index $p^j$ for every $j$, so the group is infinite. This criterion applies even with infinitely many relators, provided the weighted sum in the definition converges.

If $H$ is a normal subgroup of index $p$ in a group presented by $\mathcal{P}$, the Reidemeister–Schreier theorem produces a presentation $\mathcal{Q}$ withThe preimage of $H$ in the free group has rank $1+p(d-1)$. A relator $w^{p^k}$ produces at most $p$ conjugate relators of weight $p^{-k}$ if its root lies in that preimage. If the root lies outside, $k\ge 1$, and the coset conjugates are redundant up to conjugation; one relator of weight at most $p^{-(k-1)}$ suffices. Thus the total weighted relator cost grows by at most $p$. Convergent infinite sums are handled term by term.

For a finitely generated group, let $G^p$ denote the subgroup generated by all $p$th powers. Its p-rank isThis is the dimension of the largest quotient that is an elementary abelian group of exponent $p$. In a group presentation with $d$ generators and $s$ relators that are not $p$th powers, reduction of the exponent sums modulo $p$ gives at most $s$ linear constraints. Hence $d_p(G)\ge d-s\ge {\mathrm{def}}_p(\mathcal{P})$. In particular a presentation of p-deficiency at least one yields a surjection onto $C_p$.

For a fixed finitely generated group with specified generators, its word problem asks for an algorithm deciding whether an input word represents the identity. For a finitely presented group, positive answers can be enumerated from the relators, but there need not be an algorithm deciding both positive and negative answers. An effective reduction from a nonrecursive halting set proves unsolvability.

An amalgamated free product of finite cyclic groups has an effective normal form theorem for an amalgamated free product: multiplication, subgroup membership and subgroup identifications are finite table operations. Replacing an amalgamated syllable by its image in the neighbouring factor and combining adjacent syllables from one factor strictly decreases syllable count. A remaining alternating product outside the amalgamated subgroup is nonidentity. This supplies a terminating word problem for a group algorithm.

For $S\subseteq {\mathbb{N}}_{>0}$, form the Right-angled Artin group on generators $b_i$ indexed by $i\in \mathbb{Z}$, imposing $[b_i,b_j]=1$ precisely when $|i-j|\in S$. Translation $b_i\mapsto b_{i+1}$ is an automorphism. Its semidirect product with an infinite cyclic group generated by $t$ is countable and generated by $b_0,t$. If $n\notin S$, killing all $b_i$ except $b_0,b_n$ retracts the graph group onto the rank-two free group, so their commutator is nonidentity. This proves the displayed equivalence. For non-recursively-enumerable $S$, enumerable identities of finitely generated subgroups rules out an embedding of this two-generated group in any finitely presented group.

If a finitely generated group embeds in a finitely presented group, its null words in any fixed finite generating set form a recursively enumerable set. Choose words for the generator images in the larger group. Enumerate finite products of conjugates of its defining relators and their inverses, freely reduce, and compare with substituted words. Dovetailing over input words enumerates exactly the subgroup's identities. Choosing the finite image words is nonuniform, but their existence suffices for existence of an enumeration algorithm.

A finitely generated group $G$ has a soluble word problem for a group if and only if there are a simple group $S$ and a finitely presented group $P$ with embeddings $G\hookrightarrow S\hookrightarrow P$. The theorem does not require $S$ itself to be finitely presented. In particular, a finitely generated subgroup of a finitely presented simple group has soluble word problem. The primary statement is Theorem I of An algebraic characterization of groups with soluble word problem.

Let $S$ be a nontrivial simple group inside a finitely presented group $P$, and fix $a\ne 1$ in $S$. For an input word $w$ in $S$, enumerate products of conjugates in $P$ of $w^{\pm 1}$ and proofs in $P$ that such a product equals $a$. This search terminates exactly when $w\ne 1$: the normal closure of a nontrivial element of $S$ is all of $S$, and its conjugators are also elements of $P$, while a null word has only trivial conjugates. Run this search alongside the enumerable proofs that $w=1$. Exactly one search terminates, solving the word problem for a group on any specified finitely generated subgroup of $S$. No effective generating set for the possibly infinitely generated $S$ is needed.

A finitely generated group with soluble word problem for a group embeds in a countably generated simple group with a recursive presentation of a group. Start with $P_0=G\ast ⟨a⟩$, retaining decidable membership in $⟨a⟩$. At stage $n$, add a free infinite cyclic generator $z_n$. For every nonidentity base element $g$, conjugate $[g,z_n]$ to $a$ and conjugate $g{z}_n$ to $a$; also conjugate $z_n$ to $a$, using distinct stable letters. All associated subgroups are infinite cyclic, with decidable membership by effective cyclic membership in a free product. Britton's lemma preserves embeddings, decidable word problem and decidable membership in the inherited $⟨a⟩$.

In the union, any nontrivial normal subgroup contains some nonidentity $g$ and hence $a$, by the commutator-conjugation relation. The other relations force $z_n$ and then every old $g$ into the normal closure of $a$. Every stable letter becomes an old element at a later stage, so the normal closure of $a$ is the whole union. The union is nontrivial and simple. Effective word enumeration at each stage makes all relators recursively enumerable. A two-generator HNN embedding followed by the Higman embedding theorem embeds this simple envelope in a finitely presented group.

A finite group presentation has finitely many generators and finitely many relators. It defines the quotient of the free group on $X$ by the normal closure of $R$. Free products of finitely presented groups and HNN extensions along explicitly finitely generated associated subgroups have finite presentations obtained by adjoining finitely many generators and relations.

A finitely presented group is a group admitting a finite group presentation. Finite presentability concerns the existence of such a presentation, not the decidability of its word problem for a group.

Suppose $G=⟨Y\mid R(Y)⟩$ is a finite group presentation, and $X$ is any finite generating set. Write $y_j=u_j(X)$ and $x_i=v_i(Y)$. A finite presentation on $X$ is obtained using the relators $R(u(X))$ and $x_i=v_i(u(X))$. The substitutions in both directions give inverse homomorphisms, proving that finite presentability does not depend on the finite generators chosen.

// Target: geometry-and-topology.bigb

The Higman group has the finite group presentation $Q=⟨a_1,a_2,a_3,a_4\mid a_i{a}_{i+1}{a}_i^{-1}=a_{i+1}^2(i\mathrm{mod}4)⟩$. Its subgroup $⟨a_1,a_3⟩$ is a rank-two free group, and the normal closure of each $a_i$ is all of $Q$. It has no nontrivial finite quotients of a group: a least prime divisor among the four generator orders in a finite image contradicts the multiplicative-order constraints imposed by conjugation to squares. These properties give finite-presentation constructions embedding arbitrary finitely presented groups into groups with no nontrivial finite quotients.

The two three-generator components on $\{a,b,c\}$ and $\{c,d,a\}$ are iterated HNN extensions of infinite cyclic groups. The subgroup on $\{a,c\}$ is free of rank two in each component by Britton's lemma. Amalgamating over these free subgroups gives the displayed infinite finitely presented group. Its cyclic squaring relations forbid every nontrivial finite quotient by the least-prime multiplicative-order argument.

A group presentation with a cyclic list of generators $a_i$ and relations $a_i{a}_{i+1}{a}_i^{-1}=a_{i+1}^2$ has no nontrivial finite quotient of a group. In a finite image, all generator orders are odd. Choose the least prime $p$ dividing any nontrivial generator order and let $x$ be the predecessor of a generator $y$ whose order is divisible by $p$. Conjugation by $x$ acts as squaring on $⟨y⟩$, so the multiplicative order of $2$ modulo $p$ divides the order of $x$. That multiplicative order is greater than one and divides $p-1$, giving a prime divisor smaller than $p$ in the order of $x$, a contradiction. This argument applies to any cycle length; it asserts absence of finite quotients, not infinitude of the presented group.

An isomorphism-invariant property of finitely presented groups is Markov when some finitely presented group has it and some finitely presented group cannot embed in any finitely presented group having it. The second witness is an obstruction to embedding, rather than merely a group failing the property. The Adian–Rabin theorem makes every such property algorithmically undecidable from arbitrary finite presentations.

No Markov property of finitely presented groups is decidable by an algorithm taking an arbitrary finite group presentation as input. The proof reduces the word problem for a group to property recognition using an effective construction which collapses when an input word is trivial and embeds the input group when it is nontrivial.

In the effective group form used for recognition problems, a finite group presentation of $K$ and a word $w$ yield, by an algorithm, a finite presentation of a group $K_w$. If $w=1$ in $K$, then $K_w$ is trivial; if $w\ne 1$ in $K$, then the specified generators embed $K$ in $K_w$. One can additionally arrange that the normal closure of the image of $w$ is all of $K_w$. The finite presentation can be written without first deciding which case holds. This is the collapse-versus-embedding construction behind the Adian–Rabin theorem.

A Tietze transformation changes a group presentation without changing the presented group, by adding or removing a consequence of the relators, or by adding or eliminating a generator together with a defining equation expressing it in the others. For example a generator $t$ defined by $t=xs{x}^{-1}$ can be eliminated by substitution in every remaining relator.

A finite group presentation with cyclically reduced symmetrized relators is a Dehn presentation if every nonempty freely reduced null word contains a relator segment longer than half that relator. Replacing the segment by the inverse complementary segment strictly shortens the word. Finiteness of both the alphabet and the relator set is part of this definition; merely permitting all null words as an infinite relator set would make the shortening property vacuous as a finiteness criterion.

In a finite Dehn presentation, every nonidentity finite-order element has a shortest conjugacy representative of length at most half the length of some relator. Indeed a positive power contains a Dehn segment. If the representative had length at least $k=\lfloor |r|/2\rfloor +1$, the first $k$ letters of that segment would fit into a cyclic rotation and could be replaced by fewer letters, contradicting minimality. Bounded relator lengths and a finite alphabet therefore give finitely many conjugacy classes of finite-order elements. With no relators the group is free and torsion-free, so only the identity class remains.

For a Dehn presentation, repeatedly freely reduce a word or replace a relator segment longer than half its perimeter by its shorter complementary segment. Length decreases strictly. A word represents the identity exactly when the procedure reaches the empty word: any nonempty terminal null word would contradict the defining Dehn property. The finite list of relators makes each search effective.

A set of relator words is symmetrized if it includes their inverses and cyclic permutations. Symmetrizing a finite set remains finite, preserves each relator's length and presents the same group. It permits a matching relator segment to be taken anywhere on either orientation of a cell boundary.

A map from the generators $S$ of $⟨S\mid R⟩$ to a group $G$ extends to a homomorphism exactly when every relator in $R$ evaluates to the identity. The extension is then unique.

A relator is a word in the generators of a free group that is imposed as the identity in a group presentation.

A free presentation of a group is a quotient $G\cong F/R$ in which $F$ is a free group and $R$ is the normal closure of the chosen relators.

A finite group presentation is balanced when it has the same number of generators and relators.

For a finite group presentation, the relator exponent-sum matrix records in row $i$ the total exponent of each generator in relator $r_i$. It presents the abelianization of the group. For a balanced presentation of a perfect group, it is a unimodular matrix.

For a free presentation $G\cong F/R$, the relation module is the abelianization $R/[R,R]$ equipped with the $G$-action induced by conjugation in $F$.

If $I_F$ is the augmentation ideal of $\mathbb{Z}F$, a free presentation $G\cong F/R$ gives an exact sequenceThe middle module is free over $\mathbb{Z}G$ on the free generators of $F$.

Fox calculus assigns noncommutative derivatives $\partial /\partial x_i$ to words in a free group. The product rule and the identityturn relators into module maps and give the presentation relation sequence.

The Fox derivative of a word in a free group obeys $\partial (uv)/\partial x=\partial u/\partial x+u\partial v/\partial x$ and $\partial x^{-1}/\partial x=-x^{-1}$.

For a word $w\in F(S)$ representing the identity in $⟨S\mid R⟩$, its area is the least $N$ for whichin $F(S)$, where $r_i\in R$ and ${\epsilon }_i\in \{-1,1\}$.

The Dehn function of a finite presentation isIt measures the worst number of relator applications needed to prove a null word of bounded length.

Choose bounded-length substitutions $T$ from the first generating set to the second, and $U$ back. Each substituted relator of the second group presentation has bounded area in the first, and every generator correction $a(UT(a){)}^{-1}$ has bounded area. Substitution into a minimal second-presentation diagram and filling the correction strips givesThe reverse construction gives the opposite inequality. Thus the optimal Dehn functions are coarsely equivalent, and the existence of a recursive isoperimetric bound, hence solvability of the word problem for a group, is independent of the finite group presentation.

A nondecreasing function bounding the area of every null word of length at most $n$ is an isoperimetric function for a finite group presentation. The Dehn function is the minimal such bound. A subrecursive bound means one dominated by a total computable function. Arbitrarily enlarged bounds are not invariants: even a group presentation with zero area function admits both linear and exponential upper bounds, which are not equivalent under the usual coarse comparison.

A finite group presentation has a recursive upper bound on its Dehn function exactly when its word problem for a group is decidable. If the maximal relator length is $\ell$ and a word has length $n$, a diagram of area at most $N$ can be chosen with at most $\ell N+n$ edges. Enumerating all finite labelled planar diagrams within that bound gives a terminating test. Conversely, a word decider identifies the finitely many null words of length at most $n$; exhaustive finite diagram searches find their minimal areas, whose maximum computes the Dehn function.