Can you completely determine a finitely presented finite group?

Question

Let $G = \langle S \mid R \rangle$ be a finitely presented group. Suppose you know $G$ is finite. Can you completely construct the group multiplication table?

I feel like the answer is yes. My first thought is to construct homomorphisms into symmetric groups, but I am not quite sure how to go about it.

Answer 1

In fact, in this case you can determine the group! Finiteness is absolutely crucial here, however.

Let's say our generators are $a_1,...,a_n$, our relators are $R_1,...,R_m$, and every element of our group is represented by a word of length $\le l$. Then any word of length $l+1$ can be transformed into a word of length $\le l$ by applying an appropriate (perhaps extremely long) sequence of relations. Once we see this phenomenon we know we've found all the elements of the group. Since for any $l$ there are only finitely many words of length $l+1$, via appropriate brute-force search we can eventually find and recognize such an $l$ if it exists, so there's no need for us to be given an upper bound on the lengths of the words at the outset. (Of course the first such $l$ we find might not be the smallest such $l$, since by using longer sequences of relations it may turn out that a shorter value of $l$ would have sufficed, but that's fine.)

• EDIT: Here's a bit more detail on the brute-force detection of $l$. Say that a pair of numbers $(l,m)$ is stable iff every word of length $l+1$ can be converted to a word of length $\le l$ by applying a sequence of relations of length at most $m$. Since there are only finitely many generators and relations, we can check whether $(l,m)$ is stable in finite time. Now just cycle through all possible pairs of numbers as follows: $$(1,1), (1,2), (2,2), (1,3), (2,3), (3,3),..., (1,n),...,(n,n),...$$ (this is a trick called dovetailing). As long as the group is in fact finite a stable pair must exist, and so our search will eventually halt. Now note that the first stable pair we run into may have first coordinate much larger than optimal; e.g. maybe $(10,100)$ is stable but so is $(9,1000)$. That's fine! This process isn't guaranteed to find the smallest such $l$, just some working $l$.

Once we have found such a sufficiently large $l$, we can just try to greedily build the multiplication table (my original idea with graphs did not work, as pointed out by Eric Wofsey and Adayah below). At any given stage, we'll have a guess at an equivalence relation on the set $L$ of words of length $\le 2l$. At each stage we check whether the multiplication/inverse tables this equivalence relation generates on the set of words of length $\le l$ (we need to go up to length $2l$ to deal with multiplications) satisfies the group axioms and our relations; if it doesn't, then we add the appropriate pairs to our equivalence relation and rinse-and-repeat. Eventually we wind up with the smallest equivalence relation which satisfies our constraints, which gives our group.

Note that nothing here relies on groups per se; the same basic idea would work for any sort of algebraic structure.