Proof. Let G be a subgroup of $\mathbb {Q}^n$ of full rank. Consider an n-tuple $\bar {a}$ in G that is linearly independent over $\mathbb {Z}$ , and let S be the set of $\mathbb {Q}$ -linear expressions $\lambda (\bar {x})$ such that $\lambda (\bar {a})$ is present in G. The Scott sentence says that G is a torsion-free abelian group ( $\Pi _1$ ), and that there is a tuple $\bar {x}$ that is independent and such that the $\mathbb {Q}$ -linear combinations present are just those in S. To say that $\bar {x}$ is independent, we take the conjunction of formulas $m_1x_1 + \cdots + m_nx_n\not = 0$ , for integers $m_1,\ldots ,m_n$ not all $0$ . This is computable $\Pi _1$ . To say that $y = \lambda (\bar {x})$ for $\lambda (\bar {x}) = q_1x_1 + \cdots + q_nx_n$ , where $q_i = \frac {m_i}{m}$ , we write $my = m_1x_1 + \cdots + m_nx_n$ . This is quantifier-free. To say that the $\mathbb {Q}$ -linear combinations present are just those in S, we write $\bigwedge _{\lambda \in S}(\exists y) y = \lambda (\bar {x})\ \&\ (\forall y)\bigvee _{\lambda \in S}y = \lambda (\bar {x})$ . This is $\Pi _2$ . With a G-oracle we can enumerate S and compute the $\Pi _2$ sentence, making the whole Scott sentence G-computable $\Sigma _3$ .

Proof. By a result of Montalbán [Reference Montalbán23], there is a $\Pi _3$ Scott sentence if and only if the orbits of all tuples are defined by $\Sigma _2$ formulas. We describe G with a basis whose orbit is not defined by a $\Sigma _2$ formula. Take $G\subseteq \mathbb {Q}$ generated by all $\frac {1}{p}$ (for all primes p). For a basis, take $a = 1$ . This is divisible, just once, by each prime. Suppose $(\exists \bar {u})\psi (x,\bar {u})$ defines the orbit of $1$ in G, where $\psi (x,\bar {u})$ is $\Pi _1$ , and take $\bar {c}$ such that $G\models \psi (1,\bar {c})$ . Each $c_i$ has form $\frac {m_i}{n_i}$ , where $m_i,n_i$ are relatively prime and $n_i$ is a product of primes, each occurring at most once. Take a prime q not a factor of any $m_i$ or $n_i$ . Let $a' = \frac {1}{q}$ and let $c_i' = \frac {m_i}{qn_i}$ . We have an isomorphism $x\rightarrow \frac {x}{q}$ from G onto the extension $G'$ generated by $\frac {1}{q^2}$ and the elements of G. All formulas true in G of $a,\bar {c}$ are true in $G'$ of $a',\bar {c}'$ . Since $G\subseteq G'$ , the $\Pi _1$ formulas true in $G'$ of $a',\bar {c}'$ are also true in G of $a',\bar {c}'$ . So, we have $G\models (\exists \bar {u})\psi (a',\bar {u})$ . However, $a = 1$ is divisible by q in G, while $a' = \frac {1}{q}$ is not. So $a'$ is not in the orbit of a. Thus, this orbit does not have a $\Sigma _2$ definition.

Proof. As in the proof of Proposition 3.2, it suffices to produce $F\in \operatorname {FD}_1$ with a basis a whose orbit is not defined by a $\Sigma _2$ formula. Let $F \subseteq \overline {\mathbb {Q}(t)}$ be the subfield generated by the set of elements $t^{1/p}$ , for $p>2$ prime, and let $a = t$ . (For definiteness: within $\overline {\mathbb {Q}(t)}$ , fix a real closed subfield containing t, and choose each $t^{1/p}$ to be the unique pth root of t within that subfield.) Suppose $(\exists \bar {u})\psi (x,\bar {u})$ defines the orbit of t in F, where $\psi (x,\bar {u})$ is $\Pi _1$ , and take $\bar {c}$ such that $F\models \psi (t,\bar {c})$ . Each $c_i$ is given by an algebraic expression in some finite collection of the generators $t^{1/p_{i,j}}$ . Take a prime q different from all of these $p_{i,j}$ , and let $a' = t^{1/q}$ . Let $F'$ be the extension of F by $t^{1/q^2}$ . Then there is an isomorphism $f:F \to F'$ that fixes $\mathbb {Q}\subset F$ and sends t to $t^{1/q}$ . Let $c_i' = f(c_i)$ . Since f is an isomorphism and $F\models \psi (t,\bar {c})$ , we have $F'\models \psi (t^{1/q},\bar {c'})$ . On the other hand, since $F\subseteq F'$ , any $\Pi _1$ formulas that are true in $F'$ of $a',\bar {c}'$ are also true in F of $a',\bar {c}'$ . So, we have $F\models (\exists \bar {u})\psi (a',\bar {u})$ . However, $a = t$ has a qth root in F, while $a' = t^{1/q}$ does not. So $a'$ is not in the orbit of a. Thus, this orbit does not have a $\Sigma _2$ definition.

Proof. The input to the operator $\Phi $ consists of a rank $r>0$ and the atomic diagram (denoted G) of a group from $\operatorname {TFAb}_r$ . Now, $\Phi $ is required to compute the atomic diagram of a field in $\operatorname {FD}_r$ . To avoid confusion, we write $\oplus $ for addition in G, and $+$ and $\cdot $ for the field operations in the output. Given a group G with universe $\omega $ , $\Phi $ names a corresponding collection of field elements $\langle Y_n\rangle _{n\in \omega }$ that we will call monomials. The multiplicative structure of the field on these elements is exactly that given by the group: $Y_i\cdot Y_j = Y_k$ if and only if $i\oplus j=k$ in G. We therefore view the indices i, j, and k as elements of G. (If $e\in G$ is the group identity element, then $Y_e$ will be the element $1$ ; i.e., the multiplicative identity of the field.)

The elements of the field $\Phi (G)$ represent quotients

$$ \begin{align*}\frac{\sum a_n Y_n}{\sum b_nY_n}\end{align*} $$

of finite $\mathbb {Q}$ -linear combinations of these monomials (including $Y_e=1$ ) for which some $b_n\neq 0$ . Addition of two $\mathbb {Q}$ -linear combinations is done by treating the monomials as indeterminates. Multiplication uses the structure on the monomials:

(1) $$ \begin{align} \left(\sum a_m Y_m\right)\cdot\left(\sum b_nY_n\right) = \sum_k \left(\sum_{m\oplus n =k} a_mb_n\right)Y_k. \end{align} $$

This makes the $\mathbb {Q}$ -linear combinations into a ring R, and Lemma 4.2 below shows it to be an integral domain.

We define addition and multiplication on the formal quotients of ring elements $\frac {A}{B}$ (for $B\not = 0$ ) in the obvious way. We also define the obvious congruence relation $\sim $ , where $\frac {A}{B} \sim \frac {A'}{B'}$ iff $AB' = A'B$ . Everything is computable in G. In this way, we obtain the quotient field of the integral domain, whose elements are the $\sim $ -equivalence classes of formal quotients $\frac {A}{B}$ . We build an isomorphic copy $F = \Phi (G)$ with universe $\omega $ , and computable in G. More precisely, as each field element is a pair of rational polynomials in $Y_n$ , they can be computably identified with $\omega $ . And with $\sim $ being computable, we may build a computable copy of F by representing each $\sim $ -equivalent class by its least member, and addition and multiplication of F are computable in (the multiplication of) G.

To see that the field F has transcendence degree r, let $U=\{ u_1,\ldots ,u_r\}$ once again be the fixed linearly independent set in G. Set $X_i=Y_{u_i}$ for each $i\leq r$ . Now each $v\in G$ is a $\mathbb {Q}$ -linear combination of the elements of U, say $dv=\bigoplus _{i} c_iu_i$ using integers $c_i$ and $d\neq 0$ , so the corresponding $Y_v^d = Y_{u_1}^{c_1}\cdots Y_{u_r}^{c_r}=\prod X_i^{c_i}$ . Expressing every $Y_v$ in this form, we see that the field is generated by rational powers of $X_1,\ldots ,X_r$ , and thus has transcendence degree $\leq r$ . (This also explains why we refer to the $Y_i$ ’s as monomials: they are actual monomials in the roots of the basis elements  $X_i$ .)

We also claim that $\{ X_1,\ldots ,X_r\}$ is algebraically independent in F. Suppose some polynomial relation holds on these elements. We may re-express each term in the relation as a single $Y_i$ , e.g., $cX_1^2X_2^5 = cY_{u_1}^2Y_{u_2}^5=cY_{2u_1}Y_{5u_2}=cY_{2u_1\oplus 5u_2}$ , so that the entire polynomial equation becomes linear (over $\mathbb {Q}$ ) in the $Y_i$ ’s. We have

$$\begin{align*}0 = \sum c_iY_i ,\end{align*}$$

which implies that every $c_i=0$ . However, since U is independent in G, distinct terms $X_1^{p_1}\cdots X_r^{p_r}$ yield distinct monomials $Y_k$ under this process, with $k=\sum p_iu_i$ . (Otherwise, we would have a nontrivial $\mathbb {Q}$ -linear relation on U.) Therefore, there were no repeated terms to combine when the polynomial equation was re-expressed as the $\mathbb {Q}$ -linear equation $0 = \sum c_iY_i$ , and so the coefficients $c_i$ (which must all be zero) are the original coefficients from the polynomial equation on $X_1,\ldots ,X_r$ . Thus, these elements are indeed algebraically independent.

It may now be helpful to view $X_1,\ldots ,X_r$ as algebraically independent positive real numbers, and to assume that all roots $X_i^{\frac 1d}$ used here are positive and real as well. Then the entire field F can be considered as a subfield of the real numbers. It is clear that this construction is functorial, and that the functor is computable. Indeed, if $\Phi _*$ is given a group isomorphism $g:G_0\to G_1$ , then $\Phi _*^{G_0\oplus g\oplus G_1}$ simply maps each $Y_n\in F_0=\Phi (G_0)$ to $Y_{g(n)}\in F_1=\Phi (G_1)$ , and then extends this map to all $\mathbb {Q}$ -linear combinations of the monomials $Y_n$ in $F_0$ and finally to their quotients. Since the monomials generate $F_0$ , this is entirely effective, and it preserves the identity and composition.

Functors must preserve the isomorphism relation on structures, of course, since they map isomorphisms to isomorphisms. However, the theorem also requires the map $\Phi $ to preserve non-isomorphism:

$$ \begin{align*}G_0\cong G_1 \iff \Phi(G_0)\cong\Phi(G_1),\end{align*} $$

so that $\Phi $ will be a Turing-computable embedding of $\operatorname {TFAb}_r$ into $\operatorname {FD}_r$ as well as being functorial.

So, it remains to show that when $G\not \cong \widetilde {G}$ , we must get non-isomorphic fields $F=\Phi (G)$ and $\widetilde {F}=\Phi (\widetilde {G})$ as outputs. From here on, let $f:F \to \widetilde {F}$ be a field isomorphism. We need to show $G\cong \widetilde {G}$ . We continue to use the transcendence basis $X_1,\ldots ,X_r$ of F built from a basis U for G, and the transcendence basis $\tilde {X}_1,\ldots ,\tilde {X}_r$ for $\widetilde {F}$ built in the analogous manner from some basis of $\widetilde {G}$ . The basis U of G naturally induces an embedding from G to $\mathbb {Q}^r$ , so we consider G as a subgroup of $\mathbb {Q}^r$ from now on (and similarly for $\widetilde {G}$ ).

Noting that monomials in F correspond to elements in G, if f sends monomials in F to monomials in $\widetilde {F}$ and vice versa, then it will induce a map from G to $\widetilde {G}$ , which can be shown to be a bijection. However, not every isomorphism $f: F\to \widetilde {F}$ sends monomials to monomials. For example, when $G = \widetilde {G}= \mathbb {Z}$ , we have $F = \widetilde {F} = \mathbb {Q}(X)$ and the map $f: F \to \widetilde {F}$ with $f(X) = \frac {X+1}{X+2}$ is an isomorphism that maps the monomial X to some non-monomial. While it is still true that $F\cong \widetilde {F}$ implies $G\cong \widetilde {G}$ (both in this case and in general), the proof is more delicate and requires us to consider the set of monomials that are sent to monomials by f.

Recall that a subgroup H of an additive group G is said to be pure if for every $g\in G$ and $k\in \mathbb {Z}$ , if $kg$ is in H, then g is in H.

The previous proposition shows that the monomials that are sent to monomials by f indeed induce an isomorphism on the corresponding subgroup H and $\widetilde {H}$ . However, as we have seen previously, not all monomials need to be sent to monomials. Instead, we will show the previous example with $G = \widetilde {G} = \mathbb {Z}$ is essentially the “only” example where a monomial can be sent to a non-monomial. Namely, we will show that $G\cong H\oplus \mathbb {Z}^k$ and $\tilde G\cong \tilde H\oplus \mathbb {Z}^k$ , for $k = r - j$ where j is the rank of H and $\widetilde {H}$ . This will establish that $G \cong \widetilde {G}$ . We will need a lemma by Schinzel.

As a warm-up example, letting $G =\mathbb {Q}$ , we will show that f must send monomials to monomials. Let $X\in F$ be the element corresponding to $1\in \mathbb {Q}$ . Since G has rank 1, F and $\widetilde {F}$ have transcendence degree 1, so $\widetilde {G}$ also has rank 1. Let $\tilde X$ be a monomial of $\widetilde {F}$ , so every other monomial of $\widetilde {F}$ is a rational power of $\tilde X$ . Suppose $f(X) = \alpha /\beta $ is reduced and such that $\alpha $ and $\beta $ are polynomials in some $\tilde X^t$ with $t\in \mathbb {Q}$ , and $\alpha $ and $\beta $ are not both monomials. Let T be the sum of the numbers of terms in $\alpha $ and $\beta $ . Then $1/T \in \mathbb {Q}$ so $X^{1/T}\in F$ . Suppose $m(X^{1/T}) = \alpha '\beta '$ is reduced. We have $m(X) = m(X^{1/T})^T$ , so $\alpha ^{\prime T} = \alpha $ . If $\alpha '$ is a monomial, then $\alpha = \alpha ^{\prime T}$ must also be a monomial, a contradiction. However, if $\alpha '$ is not a monomial, then it must have a non-zero root. So $\alpha = \alpha ^{\prime T}$ must have a nonzero root of multiplicity at least T, and by the previous lemma, must have at least $T+1$ terms, also a contradiction. So $m(X)$ must be a monomial, and since the other monomials in F are all rational powers of X, they are also sent to monomials.

We generalize this argument to higher rank to obtain the following key technical lemma, which in shows that G must be a direct sum of H and some $\mathbb {Z}^k$ (Lemma 4.7). In particular, the above argument is used in Step 0.5 and Step 1.5 to achieve condition (3). Item (2) is a technical condition that we need to maintain in order to apply Lemma 4.5.

We will use the following notation. For an element $g\in G$ , let $|g|$ be the usual r-dimensional Euclidean norm of $g\in \mathbb {Q}^r$ , and endow G with the topology induced by the Euclidean distance. Let $\bar H$ be the $\mathbb {Q}$ -span of H in $\mathbb {Q}^r$ . Since H is a pure subgroup of G, we have that $\bar H\cap G = H$ . Let $\pi :\mathbb {Q}^r \to \mathbb {Q}^r/\bar H$ be the natural quotient map.

Proof. If $G = H$ , then the statement is vacuously true. Thus, we assume that $G \neq H$ . Toward a contradiction, assume that for every $\epsilon> 0$ there is some nonzero $g\in G\setminus H$ such that $|g| < \epsilon $ . We claim that there are some $k\in \mathbb {N}$ and a sequence of elements $g_1, g_2, \ldots , g_k\in G\setminus H$ such that:

1. (1) $\pi (g_1), \ldots , \pi (g_{k-1})$ is linearly independent and $\pi (g_k)$ is a $\mathbb {Q}$ -linear combination of them.

2. (2) Let $\pi (g_k) = \sum _{j=1}^{k-1} q_j\pi (g_j)$ . For every $1 \le i \le k$ , let $f(m(g_i)) = \alpha _i/\beta _i$ and $T_i$ be the sum of the numbers of terms in $\alpha _i$ and $\beta _i$ . Then $\sum _{j=1}^{k-1}|q_j|T_j < 1$ .

3. (3) For each $1\le i\le k$ , $g_i$ is not divisible by any $n> 1$ in G. Namely, for each $n> 1$ , there exists no x with $n x = g_i$ .

We construct the sequence by the following process.

Step 0: Pick any $g_1\in G\setminus H$ .

Step 0.5: We claim that there is a largest $n\ge 1$ so that $g_1$ is divisible by n, so that we can replace $g_1$ by $\frac 1n g_1$ to achieve (3). Since $g_1$ is not in H, we know $f(m(g_1))$ is not a monomial. Thus, we write $f(m(g_1)) = \alpha _1/\beta _1$ and let $T_1$ be the sum of the numbers of terms in $\alpha _1$ and $\beta _1$ . Suppose there is some g and $n> 1$ with $g_1 = ng$ . Since H is a subgroup and $g_1 = ng\notin H$ , we also have $g\notin H$ . We claim that then $n < T_1$ . Let $f(m(g)) = \alpha /\beta $ , so $\alpha _1/\beta _1 = (\alpha /\beta )^n$ . By replacing each $\tilde X_1, \ldots , \tilde X_r$ by $X^{t_1}, \ldots , X^{t_r}$ with $1 \ll t_1 \ll \cdots \ll t_r \in \mathbb {N}$ , we may assume $\alpha (X^{t_1},\ldots , X^{t_r})$ , $\alpha _1(X^{t_1},\ldots , X^{t_r})$ , $\beta (X^{t_1},\ldots ,X^{t_r})$ , $\beta _1(X^{t_1},\ldots ,X^{t_r})$ have the same number of terms as $\alpha , \alpha _1, \beta , \beta _1$ , respectively, and $\alpha (X^{t_1},\ldots , X^{t_r})$ does not divide $\beta (X^{t_1},\ldots ,X^{t_r})$ . Since $g \notin H$ , without loss of generality, assume $\alpha $ is not a monomial and choose a root $\xi $ of $\alpha (X^{t_1},\ldots , X^{t_r})$ that is not a root of $\beta (X^{t_1},\ldots , X^{t_r})$ . Then $\xi $ is a root of $\alpha _1(X^{t_1},\ldots , X^{t_r})$ of multiplicity at least n. Thus, by Lemma 4.5, $\alpha _1$ has at least $n+1$ terms, which establishes $n+1 < T_1$ . Hence there must be a largest n that divides $g_1$ .

Step 1: If the current tuple $\pi (g_1), \pi (g_2), \dots , \pi (g_{i-1})$ is linearly independent, we proceed to find $g_i$ . Define $\alpha _j, \beta _j, T_j$ as in (2) and $Q_j = 1/(iT_j)$ . Let S be the pure subgroup of $G/H$ generated by $\pi (g_1),\ldots , \pi (g_{i-1})$ and let $S_0 = \{\sum q_j\pi (g_j) : (\forall j) |q_j| < Q_j\}$ . Then $S_0$ is an open set in S, so its preimage $\pi ^{-1}(S_0)$ is also an open set in $\pi ^{-1}(S)$ . Thus, there is some $\epsilon _i$ such that the ball B of radius $\epsilon _i$ around the origin satisfies $B \cap \pi ^{-1}(S)\subset \pi ^{-1}(S_0)$ . By assumption, there is some $g_i \in G \setminus H$ with $|g_i| < \epsilon _i$ . Use this as our next $g_i$ .

Step 1.5: If $g_i$ is divisible by some $n> 1$ , repeat the argument in Step 0.5: let $n>1$ be the largest number dividing $g_i$ , and replace $g_i$ by $\frac 1n g_i$ .

Step 2: If the current tuple $\pi (g_1), \pi (g_2), \dots , \pi (g_i)$ is linearly independent, return to Step 1 and find the next $g_{i+1}$ . If $\pi (g_1), \pi (g_2), \dots , \pi (g_i)$ is linearly dependent, then set $k = i$ and return the tuple. As the range of $\pi $ is a quotient of $\mathbb {Q}^r$ , it is finite-dimensional. Thus $\pi (g_1), \pi (g_2), \dots , \pi (g_i)$ must eventually be linearly dependent, for some i, so the process will halt.

Note that the Step 1 and 2 loop guarantees (1), and Step 0.5 and 1.5 guarantee (3). Thus, we only need to check that the constructed sequence satisfies (2). As $\pi (g_1), \cdots , \pi (g_{k-1})$ is linearly independent and $\pi (g_1), \ldots , \pi (g_{k})$ is linearly dependent, there is a unique way to write $\pi (g_k) = \sum _{j=1}^{k-1} q_j\pi (g_j)$ . By the choice in Step 1 (and the fact that Step 1.5 will only decrease the norm of $g_k$ so will not affect the containment), we have $g_k \in B \cap \pi ^{-1}(S)\subset \pi ^{-1}(S_0)$ , so $\pi (g_k) \in S_0$ . This means that $\pi (g_k)$ can be written as a linear combination of $\pi (g_j)$ where the jth coefficient is less than $Q_j$ . However, such a linear combination is unique, so we must have $|q_j| < Q_j$ for every j (by the choice of $S_0$ ) and $\sum _{j=1}^{k-1}|q_j|T_j < \sum _{j=1}^{k-1}Q_jT_j < \sum _{j=1}^{k-1}1/k < 1$ .

Now, we have a sequence of nonzero $g_1, g_2, \ldots , g_k\in G\setminus H$ satisfying (1) to (3). By clearing denominators in the $q_i$ , we can find some $n_i\in \mathbb {Z}$ such that $n_k \neq 0$ and $\sum n_i\pi (g_i) = 0$ . By replacing $g_i$ with $-g_i$ if necessary, we will assume each $n_i \ge 0$ for simplicity. From (2), we have $\sum _{i=1}^{k-1}(n_i/n_k)T_j < 1$ .

Define $h = \sum n_ig_i$ . We have $\pi (h) = 0$ , so $h \in \bar H$ , but also $h \in G$ , so we have $h\in H$ . Thus, $f(m(h))$ is a monomial. Now working in the field, we have

$$ \begin{align*}m(h) = m(\sum n_ig_i) = \prod m(n_ig_i) = \prod(m(g_i))^{n_i}.\end{align*} $$

Applying f, we then have

$$ \begin{align*}f(m(h)) = \prod (\alpha_i/\beta_i)^{n_i}.\end{align*} $$

Recall that $\alpha _i$ and $\beta _i$ are quotients of polynomials in $\tilde X_1, \ldots , \tilde X_r$ , potentially with rational exponents. Take $1 \ll t_1 \ll \cdots \ll t_r \in \mathbb {N}$ such that $t_i$ is a common multiple of all the denominators of powers of $\tilde X_i$ in $\alpha _i$ and $\beta _i$ . Consider $\alpha _i(X^{t_1},\ldots , X^{t_r})$ and $\beta _i(X^{t_1},\ldots ,X^{t_r})$ . Since $1 \ll t_1 \ll \cdots \ll t_r \in \mathbb {N}$ , we have that $\alpha _i(X^{t_1},\ldots , X^{t_r})$ and $\beta _i(X^{t_1},\ldots ,X^{t_r})$ have the same number of terms as $\alpha _i$ and $\beta _i$ , respectively. Furthermore, since $t_i$ is a common multiple of all denominators of powers of $\tilde X_i$ in $\alpha _i$ and $\beta _i$ , we have that $\alpha _i(X^{t_1},\ldots , X^{t_r})$ and $\beta _i(X^{t_1},\ldots ,X^{t_r})$ have integral exponents, thus are in $\mathbb {Q}[X]$ . For notational simplicity, we will from now on write $\alpha _i = \alpha _i(X^{t_1},\ldots , X^{t_r}) \in \mathbb {Q}[X]$ , etc.

Since $\alpha _k/\beta _k \neq 1 $ and they are not both monomials, by taking the reciprocal if necessary, there must be some root $0 \neq \xi \in \mathbb {C}$ of $\alpha _k$ that is not a root of $\beta _k$ . We give a lower bound on the multiplicity of $\xi $ as a root of $\prod (\alpha _i/\beta _i)^{n_i}$ . First, $\xi $ is a root of $\alpha _k$ and not a root of $\beta _k$ , so $(\alpha _k/\beta _k)^{n_k}$ contributes at least $n_k$ to the multiplicity of $\xi $ (as a root of $\prod (\alpha _i/\beta _i)^{n_i}$ ). We then consider $(\alpha _i/\beta _i)^{n_i}$ for $i < k$ , which could potentially contribute negatively to the multiplicity of $\xi $ (as a root of $\prod (\alpha _i/\beta _i)^{n_i}$ ) if $\xi $ is a root of $\beta _i$ . However, since each $\beta _i$ has at most $T_i$ terms, by Lemma 4.5, if $\xi $ is a root of $\beta _i$ , its multiplicity is at most $T_i$ . Thus, the contribution of each $(\alpha _i/\beta _i)^{n_i}$ to the multiplicity of $\xi $ (as a root of $\prod (\alpha _i/\beta _i)^{n_i}$ ) is at least $-n_iT_i$ .

Thus, as a root of $\prod (\alpha _i/\beta _i)^{n_i}$ , $\xi $ has multiplicity at least $n_k-\sum _{i = 1}^{k-1} n_iT_i$ . Note that $n_k-\sum _{i = 1}^{k-1} n_iT_i = n_k(1-\sum _{i = 1}^{k-1} (n_i/n_k)T_i)> 0$ by condition (2). Thus, $\xi $ is a root of $f(m(h)) = \prod (\alpha _i/\beta _i)^{q_i}$ . However, $f(m(h)) = f(m(h))(X^{t_1},\ldots , X^{t_r})$ is a monomial and has no nonzero root, a contradiction. Thus, the lemma follows.

Combining Lemmas 4.6 and 4.7, we see that $G= H\oplus \mathbb {Z}^k$ . On the other hand, $\widetilde {G}$ satisfies exactly the same conditions with $f^{-1}:\widetilde {F} \to F$ a field isomorphism, so $\widetilde {G} = \widetilde {H}\oplus \mathbb {Z}^{\tilde {k}}$ . Since H and $\widetilde {H}$ are pure groups, we have $\operatorname {rank}(G) = \operatorname {rank}(H)+k$ and $\operatorname {rank}(\widetilde {G}) = \operatorname {rank}(\widetilde {H})+\tilde k$ . We also have $H \cong \widetilde {H}$ by Proposition 4.4, so $k = \tilde k$ . Finally, we have that if $F\cong \widetilde {F}$ , then $G= H\oplus \mathbb {Z}^k \cong \widetilde {H}\oplus \mathbb {Z}^{\tilde k}= \widetilde {G}$ . This completes the proof of Theorem 4.1.

Question 4.8. If $G, H\in \operatorname {TFAb}_r$ and $g: \Phi (G) \to \Phi (H)$ is an isomorphism, then $G\cong H$ by Theorem 4.1, and by relative computable categoricity there must exist a $(G\oplus H)$ -computable isomorphism $f:G \to H$ . Can we compute such an isomorphism uniformly from G, H, and g?

Proof of Proposition 5.1.

Consider a Turing operator $\Phi $ that takes $A\in \operatorname {FD}_0$ to a purely transcendental extension $A(t)$ . For this, we need to know when one rational function $f(t)$ (with coefficients in A) is equal to another $g(t)$ . It is enough to know when one polynomial $p(t)$ is equal to another $q(t)$ . This happens just when the difference is equal to $0$ . In the purely transcendental extension, this happens exactly when each coefficient is 0.

To complete the proof of Proposition 5.1, we need the following lemma.

Conversely, it is clear that if $A\cong A'$ , then $A(t)\cong A'(t')$ . Moreover, whenever $f:A\to A'$ is an isomorphism, we can extend f to an isomorphism $\overline {f}:A(t)\to A'(t')$ by defining $f(t)=t'$ . Since $A(t)$ is constructed so that its subset A of constant rational functions is uniformly decidable within $A(t)$ , this $\overline {f}$ is computable uniformly from f, A, and $A'$ . The choice of $\overline {f}$ respects composition and preserves the identity, so we have a computable functor from $\operatorname {FD}_0$ to $\operatorname {FD}_1$ .

Proof. Existential sentences, saying which polynomials over $\mathbb {Q}$ have roots, are enough to distinguish non-isomorphic elements of $\operatorname {FD}_0$ . We will use the Pullback theorem [Reference Knight, Miller and Vanden Boom15]. First, we show that there are non-isomorphic elements of $\operatorname {FD}_1$ with the same existential theory. For this, consider a chain of three fields. The first, $A_0$ , is the algebraic closure of $\mathbb {Q}$ . The second, $A_1$ , is $A_0(t)$ , a purely transcendental extension of $A_0$ . The third, $A_2$ , is the algebraic closure of $A_1$ . Now, $A_0$ and $A_2$ satisfy the same theory—that of algebraically closed fields of characteristic $0$ . Existential sentences are preserved under extension, so those true in $A_0$ are true in $A_1$ and those true in $A_1$ are true in $A_2$ , matching those true in $A_0$ . Then $A_1$ and $A_2$ are non-isomorphic elements of $\operatorname {FD}_1$ with the same existential theory. If $\Phi $ were a $tc$ -reduction to $\operatorname {FD}_0$ , we would have $\Phi (A_1)\not \cong \Phi (A_2)$ , so there would be an existential sentence $\varphi $ true in just one of the two. The pullback $\varphi ^*$ is a computable $\Sigma _1$ sentence true in just one of $A_1$ and $A_2$ . Now, $\varphi ^*$ is a disjunction of existential sentences, one of which is true in just one of $A_1,A_2$ . This is a contradiction.

Proof. Suppose $\Phi $ is a Borel embedding of $\operatorname {FD}_1$ in $\operatorname {FD}_0$ .

Claim 1: There is a Borel reduction of isomorphism on $\operatorname {FD}_0$ to $=$ (equality on sets). (In fact, the output set is $\Sigma ^0_1$ uniformly relative to the input field.)

Recall that $E_0$ (Vitali equivalence) is the equivalence relation on $2^\omega $ such that $fE_0 g$ just if f and g differ finitely; i.e., for all sufficiently large n, $f(n) = g(n)$ .

Claim 2: There is a Borel reduction, even a $tc$ -reduction, of $E_0$ to isomorphism on $\operatorname {TFAb}_1$ .

We have shown that $\operatorname {TFAb}_1\leq _{tc} \operatorname {FD}_1$ . Composing the known reductions from $E_0$ to $\operatorname {TFAb}_1$ , from $\operatorname {TFAb}_1$ to $\operatorname {FD}_1$ , the purported reduction from $\operatorname {FD}_1$ to $\operatorname {FD}_0$ , and the known reduction from $\operatorname {FD}_0$ to $=$ , we would get a Borel reduction from $E_0$ , a properly $\Sigma ^0_2$ relation, to $=$ . It is well-known that there is no such reduction.

Proof. For $F\in \operatorname {FD}_r$ , we let $\Phi (F)$ be the henselization of $F(t)$ ; i.e., $\Phi (F) = F(t)^h$ . More precisely, we first apply a uniform effective procedure to pass from F to the valued field $(F(t),v_t)$ , where $v_t(p)$ is defined by $v_t(p) = \max \{n : t^n \mid p\}$ for a polynomial $p\in F[t]$ , and $v_t(r) = v_t(p)-v_t(q)$ for $r = p/q\in F(t)$ . By [Reference Harrison-Trainor9, Proposition 4], there is a computable embedding of $(F(t),v_t)$ into a computable copy of $(F(t)^h,v_t^h)$ . We take $\Phi (F)$ to be $F(t)^h$ . It is clear that if $F \cong E$ , then we have $\Phi (F) \cong \Phi (E)$ .

Now, suppose $\Phi (F) \cong \Phi (E)$ . By construction, $v_t$ is a discrete valuation of $F(t)$ , so $v_t^h$ is also discrete [Reference Engler and Prestel5, Theorem 5.2.5]. Thus, by Lemma 5.7, we may let v and u be the unique Henselian valuations of $\Phi (E)$ and $\Phi (F)$ , respectively. Therefore, $(\Phi (F),v) \cong (\Phi (E),u)$ as valued fields. In $\Phi (F) = F(t)^h$ , $F \cong v^{-1}[0,\infty ]/v^{-1}(0,\infty ]$ . Similarly, in $\Phi (E) = E(t)^h$ , $E \cong u^{-1}[0,\infty ]/u^{-1}(0,\infty ]$ . Thus, we have $F \cong E$ . This shows that $\Phi $ is a Turing computable embedding.

To show that $\Phi $ is functorial, for some $f: F\cong E$ , we take $\Phi _*(F\oplus f\oplus E)$ to be the map that takes $a\in F$ to $f(a) \in E$ , and takes t to t. Since $F(t)^h$ and $E(t)^h$ are algebraic over $F(t)$ and $E(t)$ , respectively, we may construct an isomorphism $\Phi ^*(F\oplus f\oplus E) = \tilde f$ from $F(t)^h$ to $E(t)^h$ by mapping roots of polynomials to corresponding roots. However, by [Reference Engler and Prestel5, Theorem 5.2.2], there is a unique isomorphism between any two henselizations of a field, which must be the isomorphism $\tilde f$ we constructed. Thus, $\Phi ^*$ is functorial and $(\Phi ,\Phi _*)$ form a computable functor from $\operatorname {FD}_r$ into $\operatorname {FD}_{r+1}$ .

Question 5.9. For which $r\in \omega $ is there a Turing computable embedding (possibly functorial?) from $\operatorname {FD}_{r+1}$ to $\operatorname {FD}_r$ ? And for each $r=1,\ldots , 12$ , is there a Borel embedding from $\operatorname {FD}_{r+1}$ to $\operatorname {FD}_r$ ?