Skip to main content
added 176 characters in body
Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

The answer is yes. This follows

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 first such theorem wasconnection pointed out in the comment of @Carl-FredrikNybergBrodda, I didn't know the connection was so precise.

The answer is yes. This follows from theorems 1.2. The first such theorem was pointed out in the comment of @Carl-FredrikNybergBrodda, I didn't know the connection was so precise.

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.

added 9 characters in body
Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

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 (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$.

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$.

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^4$$t(n)^4$ is superadditive.

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$.

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^4$ is superadditive.

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$.

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.

Source Link
Ville Salo
  • 6.7k
  • 1
  • 17
  • 40

The answer is yes. This follows from theorems 1.2. The first such theorem was pointed out in the comment of @Carl-FredrikNybergBrodda, I didn't know the connection was so precise.

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^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.