A detail about busy beaverly behavior of distortion functions in graph groups

Question

Say a function $\phi : \mathbb{N} \to \mathbb{N}$ is weakly superrecursive if for any total recursive $\phi : \mathbb{N} \to \mathbb{N}$ we have $\phi(n) > \psi(n)$ for infinitely many $n$. Say it is strongly superrecursive if for any total recursive $\phi : \mathbb{N} \to \mathbb{N}$ we have $\phi(n) > \psi(n)$ for all large enough $n$. Not every weakly superrecursive function is strongly superrecursive.

Let $H \leq G$ be groups with finite generating sets $S \subset T$, respectively. Define the distortion function of $H$ inside $G$ as $$ \Delta^T_S(\ell) = \max \{|w|_S \;|\; w \in H, |w|_T \leq \ell\}, $$ defined up to the equivalence relation $f \approx g$ if for some $C > 0$, $C^{-1}f(n) \leq g(n) \leq Cf(n)$ for large enough $n$, where $|w|_N$ is the word norm of $w$ under generators $N$.

By a result of Mihajlova, $G = F_2 \times F_2$ has undecidable generalized word problem, and from this it follows that there is a finitely-generated subgroup $H \leq G$ with weakly superrecursive distortion function.

Does this group, or at least some other graph group (i.e. right-angled Artin group), have strongly superrecursive distortion function?

Might follow from computability principles directly (if so, feel free to ignore groups in the answer), but I don't see this. Might also follow from Mihajlova's construction, but while I know the construction I haven't reconstructed a proof, and I don't know the details of how the word problem of f.p. groups is proved undecidable well enough either. Might also be well-known about graph groups, but I didn't find such a statement.

Mikhajlova, K. A., The occurrence problem for free products of groups, Math. USSR, Sb. 4(1968), 181-190 (1969); Translation from Mat. Sb., n. Ser. 75(117), 199-210 (1968). ZBL0214.27403.

Answer 1

The answer is yes.

Theorem. There exists a finitely-presented group with strongly superrecursive Dehn function.

Theorem. (Therefore) there exists a finitely-generated subgroup of $F_2 \times F_2$ with strongly superrecursive distortion.

These follow from theorems 1.2. The connection pointed out in the comment of @Carl-FredrikNybergBrodda.

Theorem 1.2 (Olshanskii-Sapir '98). The set of distortion functions of finitely generated subgroups of the direct product of two free groups $F_2 \times F_2$ coincides (up to equivalence) with the set of all Dehn functions of finitely presented groups.

Theorem 1.2 (Sapir-Birget-Rips, '08). Let $D_4$ be the set of all Dehn functions $d(n) \geq n^4$ of finitely presented groups. Let $T_4$ be the set of time functions $t(n) \geq n^4$ of arbitrary Turing machines. Let $T^4$ be the set of superadditive functions which are fourth powers of time functions. Then $T^4 \subset D_4 \subset T_4$.

The time function of a (not necessarily deterministic) Turing machine $M$ is $t : \mathbb{N} \to \mathbb{N}$ where $t(n)$ is the smallest number such that for every acceptable word $w$ with $|w| \leq n$ there exists a computation of length $\leq t(n)$ which accepts $w$. A function $f$ is superadditive if $f(m+n) \geq f(m) + f(n)$. All we need to do is find a function in $T^4$ which is strongly superrecursive.

Let $M$ be a Turing machine that on input $0^n 1^k 2^h$ performs the following $2^{n+k+h}$ times, in a loop: simulate the $n$th Turing machine $M'$ (i.e. the machine with Gödel number $n$) on all unary inputs $1^0, 1^1, ..., 1^{2k}$, until $M'$ has halted on all of them. (And $M$ does not halt on inputs not of this form.) Let $t$ be the Time function of $M$. Letting $a = \max(a,b)$, we have $t(a + b)^4 \geq t(a + 1)^4 \geq (2t(a))^4 \geq t(a)^4 + t(b)^4$, where $t(a + 1) \geq 2t(a)$ follows because if $t(a)$ is given by input $0^n 1^k 2^h$, then the computation on $0^n 1^k 2^{h+1}$ takes at least twice as long. Therefore, $t(n)^4$ is superadditive.

(The justification of $t(a + 1) \geq 2t(a)$ is not completely precise, since there's a lot of bookkeeping going on and kept implicit. To be more exact without going into Turing machine details, you could replace the $2^{n+k+h}$-length loop on $0^n 1^k 2^h$ by two recursive calls of $M$ on $0^n 1^k 2^{h-1}$, when $h > 0$, or alternatively replace $2^{n+k+h}$ by something that grows much faster.)

For a Turing machine $M'$, write $\alpha(M')$ for some Gödel number of it. Let $f$ be any total recursive function, computed by some Turing machine $M'$, let $\alpha(M') = \ell$. Total recursive functions are the same if we restrict to unary, so we may suppose that on input $1^k$, $M'$ computes $1^{f(k)}$ and halts (and does whatever on other inputs). We may assume $M'$ takes at least $f(k)$ steps to halt on input $1^k$ (indeed this is automatic since it has to write its output).

Now, on input $0^{\ell} 1^k$ our machine $M$ halts (because $M'$ halts on all unary inputs), and takes (much more than) $\max_{i=0}^{2k} f(i)$ steps to do so. In particular, as soon as $n \leq 2(n-\ell)$, we have $t(n)^4 \geq t(n) \geq f(n)$. Therefore $t(n)^4$ is strongly superrecursive.

Since $n^4$ is recursive, we also have $t(n)^4 \geq n^4$ (up to equivalence).

Ol’shanskij, Alexander Yu.; Sapir, Mark V., Length and area functions on groups and quasi-isometric Higman embeddings, Int. J. Algebra Comput. 11, No. 2, 137-170 (2001). ZBL1025.20030.

Sapir, Mark V.; Birget, Jean-Camille; Rips, Eliyahu, Isoperimetric and isodiametric functions of groups, Ann. Math. (2) 156, No. 2, 345-466 (2002). ZBL1026.20021.