# Group size as a function of presentation length?

Given a presentation of a group, together with the promise that the group is finite, is there a computable upper bound on the size of the group? Edited to add: by "presentation" we mean a set of generators and relations. See e.g. Wikipedia.

Define the length of a presentation as the number of generators plus the length of each of the relations in terms of the number of letters. For example, the standard presentation of the cyclic group on $N$ elements has length $N+1$.

It's easy to see that the group can be exponentially larger than its presentation. For example, the cyclic group of size $2^n$ has the following presentation of size about $4n$:

$$\mathbb Z_{2^n} = \left\langle a_1, \ldots a_n | a_1a_1 = a_2, a_2a_2 = a_3, \ldots a_{n-1}a_{n-1} = a_n, a_na_n = 1\right\rangle.$$

It's plausible to conjecture that exponential is as good as you can do. So a good subquestion is:

Is there a family of finite group presentations for which the size of the group grows super-exponentially in the length of the description of the presentation?

• I suppose the length of a relation is the number of generators in a fully expanded expression? So e.g. the length of $x^{2^{2^n}} = e$ would be $2^{2^n}$ rather than $O(\log_{10} n)$? :) – Daniel Schepler Apr 27 '18 at 23:30
• @DanielSchepler That may make for a better question. I'll edit to update. – Jalex Stark Apr 27 '18 at 23:46

I found a paper here: https://www.math.auckland.ac.nz/~obrien/research/an-sn-present.pdf in which the authors prove that the symmetric group $S_n$ (of order $n!$) has a presentation of length $O(\log n)$.

The answer to the question is negative. We'll use the fact that the problem "given a presentation, decide whether it presents a finite group" is undecidable. This follows from the Adian-Rabin theorem.

Now suppose that there were a computable function $f$ so that every presentation of length at most $r$ either presents a finite group of size at most $f(r)$ or presents an infinite group. Then we have a decision procedure for the undecidable problem above, as follows.

Given a presentation of length $r$, iterate through all finite groups of size at most $f(r)$. Check whether the presentation presents the group. If one does, declare the group finite. If none does, declare the group infinite.