3
$\begingroup$

Suppose $\langle S| R \rangle$ is a presentation of a group. Let’s define its length (denoted by $\operatorname{len}(\langle S| R \rangle)$) as the sum of lengths of all its relators.

Now for any finitely presented group $G$ we can define its presentation length as:

$$\operatorname{len}(G) = \min\{\operatorname{len}(\langle S|R \rangle)| \langle S|R \rangle \cong G\}$$

Now, as all finite groups are finitely presented, we can define the following integer function:

$$LG(n) = \max \{\operatorname{len}(G)| |G| \leq n\}$$

What is the asymptotic of $LG$?

I managed to find a following asymptotic bound:

$$LG(n) = O(n \log^2n)$$

To get this, we can use Erdos-Renyi Generator Theorem, which states:

Suppose $G$ is a finite group, $t = \lfloor \log_2 |G| + \log_2 \log_2 |G| \rfloor + 2$. Then $\exists S \in G$, such that $|S| = t$ and $(S \cup S^{-1})^t = G$.

Now, suppose $S$ is the generating set from that theorem, and $\forall g \in G$, $w_g$ is a word over $S$ of length $t$ representing $g$. Then for $G$ we have the following presentation of appropriate length (it has $|G|t$ relators of length $2t + 1$ each):

$$\langle S | w_g s w_{gs}^{-1} \forall s \in S, g \in G \rangle $$

On the other hand, the following lower bound can be derived from pigeonhole principle:

$$LG(n) = \Omega(\log^2 n)$$

Indeed, knowing that every generator of a finite group must be present in some relation and that any finite group $G$ is at most $k$-generated we can use $B_k (2\log(n) + 1)^k$ ($B_k$ stands for $k$-th Bell number) as an upper bound for the number of distinct presentations of groups with order at most $n$ of length at most $k$. At the same time, for the number of groups of order at most $n$ we can find lower bound $2^{C \log^3(n)}$ for some constant $C$. Thus, if $k \geq LG(n)$, then

$$B_k (2log(n) + 1)^k \geq 2^{C \log^3(n)}$$

from that it follows, that

$$k (\log(k) + 2\log(n) + 1) \geq C \log^3(n)$$

from which it follows that $k = \Omega(\log^2(n))$, Q.E.D.

However, there is a large gap between those two bounds, and I do not know, whether any of them is tight...

$\endgroup$
4
  • 4
    $\begingroup$ A more standard definition of presentation length is number of generators + total relator length. There has been a lot of research recently on presentation lengths of finite simple groups, partly motivated by computational applications. It is known that, with the possible exception of the groups $^2G_2(q)$, the simple groups of Lie rank $n$ over the field of order $q$ have presentarions of length $(\log n + \log q)$. $\endgroup$ – Derek Holt Sep 13 '20 at 20:22
  • 1
    $\begingroup$ @Derek: I think all of the relevant presentations will have at most logarithmically many generators in the order of the group, so this shouldn't affect the asymptotics Yanior is asking about too much... $\endgroup$ – Qiaochu Yuan Sep 13 '20 at 20:26
  • 3
    $\begingroup$ For a finite group the number of relators is $\ge$ the number of generators, the length counting generators is at most twice the length without them, so the (rough) asymptotics are the same. $\endgroup$ – YCor Sep 13 '20 at 20:33
  • 4
    $\begingroup$ Oh sure, it doesn't affect the asymptotics, but I was just pointing out that there is a standard definition of presentation length. $\endgroup$ – Derek Holt Sep 13 '20 at 21:39
4
$\begingroup$

Nice question! This isn't an answer, just some noodling. I am mostly curious about lower bounds since you gave such a nice upper bound. Here's a warmup question whose answer is already not obvious to me:

What is the length $\text{len}(C_n)$ of the cyclic group of order $n$?

Of course there's a presentation $\langle x \mid x^n = e \rangle$ of length $n$. When $n$ is composite we can give a shorter presentation as follows. Consider a chain of proper divisors $1 \mid d_1 \mid d_1 d_2 \mid \dots \mid d_1 d_2 \dots d_k = n$ which is as long as possible; this means each $d_k$ is prime and corresponds to a composition series for $C_n$. Then $C_n$ has a presentation

$$\langle x_1, \dots x_k \mid x_1^{d_1} = x_2, x_2^{d_2} = x_3, \dots x_{k-1}^{d_{k-1}} = x_k, x_k^{d_k} = e \rangle$$

of length $(d_1 + 1) + \dots + (d_{k-1} + 1) + d_k$. So if $n = \prod p_i^{e_i}$ then the length of this presentation is $\left( \sum e_i (p_i + 1) \right) - 1$.

I thought this was best possible for a bit but it turns out to be possible to do much better than this! We can consider abelian presentations, namely presentations in abelian groups, where we assume implicitly that the generators already commute. Such a presentation describes a finite abelian group as the cokernel of an integer matrix $M : \mathbb{Z}^r \to \mathbb{Z}^s$ (of full rank over $\mathbb{Q}$, which implies in particular that $r \ge s$), and which abelian group we get can be read off from the Smith normal form of $M$.

The abelian length of this presentation is the sum $\sum |M_{ij}|$ of the absolute values of the entries of $M$, and we can transform an abelian presentation into a presentation by adding relations saying that the generators commute, so an abelian presentation with $s$ generators of abelian length $\ell$ gives a presentation of length $\ell + 4{s \choose 2}$. On the other hand, every presentation abelianizes to an abelian presentation, so the shortest presentation gives an upper bound on the shortest abelian presentation.

So for any finite abelian group $A$, define $\text{alen}_s(A)$ to be the minimal abelian length of an abelian presentation with $s$ generators, and define $\text{alen}(A) = \min_s \text{alen}_s(A)$ to be the minimal abelian length of an abelian presentation. Then we have

$$\text{alen}(A) \le \text{len}(A) \le \min_s \left( \text{alen}_s(A) + 4{s \choose 2} \right).$$

An abelian presentation for $A \times B$ is just given by putting together a presentation for $A$ and a presentation for $B$, so $\text{alen}$ behaves better with respect to direct products than $\text{len}$ does: we have

$$\text{alen}(A \times B) \le \text{alen}(A) + \text{alen}(B)$$

and even

$$\text{alen}_{s_1 + s_2}(A \times B) \le \text{alen}_{s_1}(A) + \text{alen}_{s_2}(B).$$

Both of these, together with a variation on the composition series construction above, suggest (and it shouldn't be hard to turn this into a proof) that the largest length of a finite abelian group of order $\le n$ will be attained for a cyclic group $C_p$ of prime order, so let's now consider only that case.

If we make the further simplifying assumption $r = s$ (which I think should always be satisfied by a presentation of minimal length but who knows), then, if $M$ is an $s \times s$ integer matrix, its cokernel presents the cyclic group $C_p$ of order $p$ iff $\det(M) = \pm p$. So in this case we are trying to find a square integer matrix of determinant $\pm p$ such that $\sum |M_{ij}|$ is as small as possible.

Let's now further specialize to the case that $r = s = 2$, so we're now looking for $2 \times 2$ integer matrices $M = \left[ \begin{array}{cc} a & b \\ c & d \end{array} \right]$ such that $|ad - bc| = p$ and such that $|a| + |b| + |c| + |d|$ is as small as possible. This already seems tricky! At least one of $a, b, c, d$ must have size at least $\sqrt{ \frac{p}{2} }$ and it is sometimes possible to get them this small but I have no idea whether it's always possible to get them this small.

To be really explicit, if we can find a prime of the form $p = 2n^2 - 1 = n^2 + (n^2 - 1)$ then we can take $a = d = n, b = n-1, c = -(n+1)$. Some messing around in WolframAlpha gives that this is prime when $n = 102$ (I want $n$ to be big enough that we can see the $\sqrt{p}$ asyptotic behavior); we get $p = 20807$. So we get an abelian presentation of $C_{20807}$ of length $408$ and hence, after adding the single relation that the two generators commute, a presentation

$$\langle x, y \mid x^{102} = y^{103}, x^{102} = y^{-101}, xy = yx \rangle$$

of $C_{20807}$ of length $412$! This only gives an upper bound $\text{len}(C_{20807}) \le 412$ on the length of a single group so it doesn't give a lower bound on $LG(n)$ (for which we'd need to find a lower bound on the length of some group of order $\le n$), but it does mean I no longer even know whether to conjecture that we should have $LG(n) = (1 - o(1)) n$ or $\sqrt{n}$ or what! Are there infinitely many primes $p$ which can be written $p = ad - bc$ for integers $a, b, c, d$ such that $|a|, |b|, |c|, |d| \le \sqrt{p}$? I have no idea!

Edit: Here's an even wackier example showing how small presentations of $C_p$ can be. There are these things called continuants that are determinants of certain tridiagonal matrices. A particular specialization of them, corresponding to a determinant of a tridiagonal matrix whose nonzero entries are $\pm 1$, gives Fibonacci numbers. Any Fibonacci number $p = F_{s+1}$ that's prime produces an $s \times s$ tridiagonal matrix $M$ with determinant $F_{s+1}$ such that $\sum |M_{ij}| = 3s-2$ and hence a presentation of the cyclic group $C_p$ of length $3s-2 + 4{s \choose 2}$, which is $O(\log^2 p)$! Many Fibonacci primes are known but it's an open question whether there are infinitely many.

Unfortunately, as amusing as this is, to lower bound $LG(n)$ we need to go the opposite way: we need primes $p \le n$ which are as hard to represent as the determinant of an integer matrix with small entries as possible... (or perhaps I am even wrong about reducing to the $r = s$ case!)

$\endgroup$
0

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.