15
$\begingroup$

While I’m aware (and as it was pointed out in the comments) it is generally undecidable whether a given presentation represents a free group, I’m interested in criteria that nevertheless ensure that the represented group is free (the most obvious one being, that there are no relations for example). In other words: Given a presentation of some group, what are nice criteria to conclude that the presentation describes a free group?

Even stronger is there a subclass of presentations (where one easily checks whether the presentation is in that class), for which it is algorithmically decidable whether a presentation yields a free group?

Improve this question
$\endgroup$
6
  • 9
    $\begingroup$ Given a presentation, there are no nice criteria even for deciding whether it describes the trivial group. $\endgroup$
    – Dave Benson
    Commented Dec 3, 2023 at 21:57
  • 3
    $\begingroup$ More precisely: there is no algorithm that inputs a finite presentation $P$ on finitely generators and outputs whether the group $G_P$ it defines is trivial. Hence if there were an algorithm do determine whether it defines a free group. Otherwise, applying it to a presentation $P\sqcup P$ (which defines the group $G_P^2$) it outputs whether $G_P$ is trivial, contradiction (because for a group $G$, $G\times G$ is free iff $G$ is trivial). $\endgroup$
    – YCor
    Commented Dec 3, 2023 at 22:23
  • 7
    $\begingroup$ I think what ThorbenK is asking about is whether there are interesting sufficient criteria. Undecidability dictates that there aren't necessary and sufficient ones, but that doesn't mean that each individual case is undecidable, or even that there aren't algorithmically decidable families of presentations. $\endgroup$
    – Steven Stadnicki
    Commented Dec 3, 2023 at 22:52
  • $\begingroup$ And one (semi)trivial answer to the latter question: the family of one-relator groups, where it's relatively straightforward to decide if the presented group is free. $\endgroup$
    – Steven Stadnicki
    Commented Dec 4, 2023 at 0:02
  • $\begingroup$ @YCor You can just apply the Adian-Rabin Theorem directly (you already apply it once). Freeness is a Markov property. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Dec 4, 2023 at 0:31

1 Answer 1

Reset to default
24
$\begingroup$

As indicated in the comments, it's undecidable in general to take as input a finite presentation of a group and try to output whether or not this group is free or not. This is a direct consequence of the Adian-Rabin Theorem: freeness is a Markov property.

But there is a beautiful sufficient condition, and a large subclass:

Theorem. There exists an algorithm that, given as input a presentation for a group $G$ and a solution to the word problem in $G$, determines whether or not $G$ is free.

This is Corollary 4.3 of Groves-Wilton [1].

I confess I do not know quite how complicated this algorithm is in practice: as far as I know, it uses Makanin's algorithm for deciding the universal theory of free groups, which is quite impractical in many cases (but perhaps there are better alternatives). In many cases, there are better approaches, like for one-relator groups (as mentioned by @StevenStadnicki in the comments) where one can use Whitehead's very practical algorithm to decide freeness in polynomial time.

${}$

[1] Groves, Daniel; Wilton, Henry, Enumerating limit groups., Groups Geom. Dyn. 3, No. 3, 389-399 (2009). ZBL1216.20029.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ That result is indeed the strongest known result in that direction, and to my knowledge the algorithm isn't known to be primitive recursive. It's also worth observing that there is a uniform algorithm for deciding the word problem for residually finite groups. $\endgroup$
    – NWMT
    Commented Dec 4, 2023 at 16:43

You must log in to answer this question.

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