Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2509.17841 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866908552614903808 |
|---|---|
| author | Wagner, Francis |
| author_facet | Wagner, Francis |
| contents | This is the first of a sequence of papers devoted to studying the link between the complexity of the Word Problem for a finitely generated recursively presented group $G$ and the isoperimetric functions of the finitely presented groups in which $G$ embeds. We prove here that if a finitely generated group has a presentation $\mathcal{P}$ whose relators can be enumerated by a computational model satisfying certain technical requirements, then the group embeds quasi-isometrically into a finitely presented group whose Dehn function is bounded above by a function of the model's computational complexity and the Dehn function of $\mathcal{P}$. This generalizes a previous result of the author pertaining to the embeddings of free Burnside groups and gives a recipe for establishing such Higman embeddings into groups with desired geometric properties. As an example of the use of this embedding scheme, we find a substantial improvement to the seminal result of Birget, Ol'shanskii, Rips, and Sapir showing that the Word Problem of a finitely generated group is in class NP if and only if the group embeds into a finitely presented group with polynomial Dehn function. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_17841 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Quasi-isometric Higman embeddings and the Dehn function Wagner, Francis Group Theory 20F05, 03D15, 20F10, 20F06, 03D10, 20F65, 20F69 This is the first of a sequence of papers devoted to studying the link between the complexity of the Word Problem for a finitely generated recursively presented group $G$ and the isoperimetric functions of the finitely presented groups in which $G$ embeds. We prove here that if a finitely generated group has a presentation $\mathcal{P}$ whose relators can be enumerated by a computational model satisfying certain technical requirements, then the group embeds quasi-isometrically into a finitely presented group whose Dehn function is bounded above by a function of the model's computational complexity and the Dehn function of $\mathcal{P}$. This generalizes a previous result of the author pertaining to the embeddings of free Burnside groups and gives a recipe for establishing such Higman embeddings into groups with desired geometric properties. As an example of the use of this embedding scheme, we find a substantial improvement to the seminal result of Birget, Ol'shanskii, Rips, and Sapir showing that the Word Problem of a finitely generated group is in class NP if and only if the group embeds into a finitely presented group with polynomial Dehn function. |
| title | Quasi-isometric Higman embeddings and the Dehn function |
| topic | Group Theory 20F05, 03D15, 20F10, 20F06, 03D10, 20F65, 20F69 |
| url | https://arxiv.org/abs/2509.17841 |