×

zbMATH — the first resource for mathematics

On subgroup distortion in finitely presented groups. (English. Russian original) Zbl 0905.20020
Sb. Math. 188, No. 11, 1617-1664 (1997); translation from Mat. Sb. 188, No. 1, 51-98 (1997).
Let \(G\) be a group generated by a finite set \({\mathcal A}=\{a_1,\dots,a_m\}\). Then the length \(| g|=| g|_{\mathcal A}\) of an element \(g\) is the length \(\| w\|\) of the shortest word \(w\) on the alphabet \({\mathcal A}^{\pm 1}\) representing the element \(g\). If there exists an isomorphic embedding \(G\hookrightarrow H\) and \(H\) is generated by a set \({\mathcal B}=\{b_1,\dots, b_n\}\) then \(| g|_{\mathcal B}=c| g|_{\mathcal A}\) for some constant \(c\) independent of the element \(g\). In particular, if \(G=\langle{\mathcal A}\rangle=\langle{\mathcal B}\rangle\), then there exist positive constants \(c_1,c_2\) such that \(c_1| g|_{\mathcal A}\leq| g|_{\mathcal B}\leq c_2| g|_{\mathcal A}\) for every \(g\in G\).
The functions \(\ell_1,\ell_2\colon G\to\mathbb{N}\) are said to be equivalent if there are positive constants \(c_1,c_2\) such that \(c_1\ell_1(g)\leq\ell_2(g)\leq c_2\ell_1(g)\) for every element \(g\in G\). A function \(\ell\colon G\to\mathbb{N}\) is said to be computable if for each representation of an arbitrary element \(g\) as a word on some generating set one can algorithmically compute \(\ell(g)\).
Theorem 2. Let \(\ell\colon G\to\mathbb{N}\) be a computable function satisfying the following conditions: (D1) \(\ell(g)=\ell(g^{-1})\) for every \(g\in G\) and \(\ell(g)=0\) if and only if \(g=1\); (D2) \(\ell(gh)=\ell(g)+\ell(h)\), \(g,h\in G\); (D3) there exists a positive number \(a\) such that \(\text{card}\{g\in G\mid\ell(g)\leq r\}\leq a^r\) for every \(r\in\mathbb{N}\). Then there exists an isomorphic embedding \(G\hookrightarrow H\) where \(H\) is a finitely presented group such that \(\ell\) is equivalent to the restriction of \(|\;|_H\) to \(G\).
The following theorem is a refinement of Higman’s theorem. Theorem 3. Let \(R\) be a group with a finite set of generators \(\mathcal A\) and a recursively enumerable set of (defining) relations. Then there exists an isomorphic embedding \(R\hookrightarrow H\) where \(H\) has a finite set of generators \(\mathcal B\) and finite set of defining relations such that \(| g|_{\mathcal A}=| g|_{\mathcal B}\) for any \(g\in G\).
The following theorem gives a possibility to choose a universal group \(U\). Theorem 4. There exists a group \(U\) having a finite set of generators \(\mathcal B\) and finite set of defining relations satisfying the following property: for every group \(H\) with finite set of generators \(\mathcal A\) and a recursively enumerable set of defining relations there exists an isomorphic embedding \(H\hookrightarrow U\) such that \(| g|_{\mathcal A}\leq| g|_{\mathcal B}\) for all \(g\in H\).

MSC:
20F05 Generators, relations, and presentations of groups
20F10 Word problems, other decision problems, connections with logic and automata (group-theoretic aspects)
20F65 Geometric group theory
05C25 Graphs and abstract algebra (groups, rings, fields, etc.)
20E07 Subgroup theorems; subgroup growth
03D20 Recursive functions and relations, subrecursive hierarchies
PDF BibTeX XML Cite
Full Text: DOI