3
$\begingroup$

Are there any algorithms to find the size of an algebraic quotient of a free group? It would take the generators as input and output the size. For example, an input could be something like {a,b: a^8=b^2=1, ab=ba^3} (a quasidihedral group), and the output would be the integer 16, since there are 16 different ways to write a string formed of a's and b's if you treat aaaaaaaa and bb as the empty string, and the string ab as the same as the string baaa.

Ideally the algorithm would also be able to say if a group was infinite. It's not obvious by looking at the presentation what the size of the group is, and I think it's a fairly interesting question that I've comes across a few times in my algebra class, so I was surprised that I couldn't find a tool to solve it for me or any papers talking about it, it seems that computers should be good at this. Wondering if anyone has any good ideas.

$\endgroup$
2
$\begingroup$

I think you're asking: given a group presentation $\langle X | R \rangle$, determine the size of the group.

Unfortunately, it is undecidable to determine whether the group is finite or infinite. See the Adian-Rabin theorem.

For some additional references, see also https://math.stackexchange.com/a/606/14578, https://math.stackexchange.com/q/3106606/14578, https://math.stackexchange.com/q/2756802/14578, https://math.stackexchange.com/q/1516849/14578, or the following lecture notes: Presentation of Groups. Derek Holt.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.