10
$\begingroup$

(This question comes from a friend who works in sofic group theory.)

Consider the function $f: \mathbb{N} \to \mathbb{N}$, defined, for any $n \in \mathbb{N}$, by putting $f(n)$ to be the largest cardinal of a finite group which has at least one presentation of length at most $n$ (I think any "natural" definition of length works.)

Is $f$ computable? If yes, is there a simple description of it? If not, is it "equivalent" to the busy beaver function or is it of higher growth?

Improve this question
$\endgroup$
12
  • $\begingroup$ Small note: I suspect it is not computable, but at least the obvious analogue of the proof of uncomputability of the Busy Beaver function fails here. The difference is that while it is decidable if a Turing machine halts in at most $n$ steps for any fixed $n$, it is undecidable whether a group has at most $n$ elements by Adian-Rabin. $\endgroup$
    – Carl-Fredrik Nyberg Brodda
    Commented Oct 14 at 15:11
  • $\begingroup$ Very nice question! It would suffice for us to provide, for any Turing machine program $p$, a group presentation (of about the same size as $p$), which presented a group at least as large as the running time of $p$, if it halts, otherwise infinite. If that were possible, then your function would essentially majorize the busy beaver function. But is this possible? $\endgroup$
    – Joel David Hamkins
    Commented Oct 14 at 16:05
  • $\begingroup$ @JoelDavidHamkins: Something like this should be possible. For instance, there is a recursive sequence of finite presentations $H_n$ such that $|H_n|$ is either infinite or $n$, and the set of $n$ for which $|H_n|$ is finite is r.e. but not recursive. (And probably we could also make $|H_n|$ the running time of the $n$th Turing machine.) The idea is simple. The Adyan--Rabin theorem produces a sequence of presentations for groups $G_n$ such that $\{G_n\cong 1\}$ is r.e. but not recursive. Now set $H_n=C_n\times (G_n*G_n)$. $\endgroup$
    – HJRW
    Commented Oct 15 at 8:16
  • 1
    $\begingroup$ @HJRW I don't think the $C_n\times(G_n*G_n)$ presentation idea is going to work, since the $C_n$ factor is what makes it size $n$, but we need this to be the (unknown) running time at the time we form the presentation. The size of the program $p$ is going to be typically far smaller than the running time, and we can't afford to find out what the running time is, since we don't know whether it halts. $\endgroup$
    – Joel David Hamkins
    Commented Oct 15 at 12:05
  • 1
    $\begingroup$ Does "the sum of word length of relators" qualify as acceptable "length"? $\endgroup$
    – YCor
    Commented Oct 22 at 10:30

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .