18
$\begingroup$

Any finitely presented simple group has solvable word problem, and hence recursive Dehn function. I'm curious though how wild these recursive functions could possibly be.

One concrete question is whether there are even any examples known of a finitely presented simple group whose Dehn function is exponential. The only examples I can think of at the moment of finitely presented simple groups where something is known about their Dehn functions are Burger-Mozes groups (quadratic Dehn function) and Thompson's groups $T$ and $V$ (polynomial Dehn function, conjecturally quadratic).

Another (vaguer) question is whether there is some stronger bound on what sorts of functions can be Dehn functions of finitely presented simple groups (stronger than just being recursive, I mean). E.g., maybe there's some reason they can't be super-exponential?

$\endgroup$
3
  • 2
    $\begingroup$ Note that the same question for residually finite groups was open for a long time before being answered by Kharlampovich-Myasnikov-Sapir in "Algorithmically complex residually finite groups". $\endgroup$
    – E.Rauzy
    Commented May 8, 2023 at 15:11
  • 1
    $\begingroup$ Ordinarily, I’d write “this morning on the arXiv, a paper appeared answering this question” but I won’t make the same mistake twice on the same question :-) (the paper looks great!) $\endgroup$ Commented May 25, 2023 at 5:44
  • $\begingroup$ @Carl-FredrikNybergBrodda Haha thanks! Yeah I thought of how to build these, but it was too complicated for a mathoverflow comment or answer, so it became a paper :-) When I have some more time I'll explain the main ideas in an answer. $\endgroup$ Commented May 25, 2023 at 11:24

2 Answers 2

13
$\begingroup$

To answer the vaguer question: I think there is no known bound on the Dehn functions of finitely presented simple groups. Recall:

Boone–Higman Embedding Theorem. A finitely presented group has solvable word problem if and only if it can be embedded in a recursively presented simple group.

In their paper, they asked about strengthening their theorem:

Question. Is every finitely generated group G with soluble word problem embeddable in some finitely presented simple group?

This is still open (as I learnt from a talk by Jim Belk last year) and if the answer were yes, then we could embed groups with "arbitrarily bad" solvable word problem in finitely presented simple groups, whereas a bound on the Dehn function gives a bound on the complexity of the word problem.

Boone, William W.; Higman, Graham, An algebraic characterization of groups with soluble word problem, J. Aust. Math. Soc. 18, 41-53 (1974). ZBL0303.20028 MR0357625.

$\endgroup$
5
  • 3
    $\begingroup$ Note: Belk, Bleak, Matucci & Zaremsky have recently proved that the question has a positive answer for all hyperbolic groups, i.e. any hyperbolic group can be embedded in some finitely presented simple group. $\endgroup$ Commented May 5, 2023 at 8:25
  • 1
    $\begingroup$ Aha, "a bound on the Dehn function gives a bound on the complexity of the word problem," excellent point. I know groups with hard Dehn function can embed in groups with easy Dehn function, so I didn't think Boone-Higman stuff was going to help, but the same is not true for hard/easy word problem so that does pretty much answer the vaguer question. $\endgroup$ Commented May 5, 2023 at 10:31
  • 1
    $\begingroup$ @Carl-FredrikNybergBrodda Indeed, working on writing up some details of this yesterday is exactly what made this question come to mind! :-) $\endgroup$ Commented May 5, 2023 at 10:31
  • 3
    $\begingroup$ @MattZaremsky I really need to double check who OP is before writing a comment like that! :-) (Collin presented this beautiful result in Kyoto earlier this year). $\endgroup$ Commented May 5, 2023 at 11:43
  • $\begingroup$ @Carl-FredrikNybergBrodda Oh, ha, no worries, I viewed your first comment as more of a shout-out than an FYI anyway. $\endgroup$ Commented May 5, 2023 at 14:18
4
$\begingroup$

I thought of some finitely presented simple groups with (at least) exponential Dehn function. I wrote it up here: https://arxiv.org/abs/2305.15176, and let me explain the broad strokes. The simple groups in question are certain commutator subgroups of Roever-Nekrashevych groups $V_d(G)$, which can be thought of as a machine that inputs a self-similar group $G$ of tree automorphisms, and outputs a group $V_d(G)$ of homeomorphisms of the boundary of the tree. If $G$ is cleverly chosen you can ensure that $V_d(G)$ is finitely presented, the commutator subgroup is finite index, and (most importantly) $G$ is a "quasi-retract" of $V_d(G)$ (this only works for very specifically calibrated self-similar representations of $G$). Quasi-retracts provide lower bounds on Dehn functions, so at this point it "just" remains to find examples of $G$ with exponential Dehn function that admit self-similar representations satisfying all the properties I didn't explain here ("cleverly chosen" and "specifically calibrated"). And, it just so happens that Baumslag-Solitar groups work!

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .