Proof Fix a model $(G; \mathscr {U}^G, \mathscr {P}^G)$ of $\mathrm {Sf}^*_{\mathbb {Z}}$ . It follows from (Z2) that the same first-order formula defines both $U^G_{p,l}$ in G and $U^{\mathbb {Z}}_{p,l}$ in $\mathbb {Z}$ . Then using (Z1), we get $\mathrm {(i)}$ . The first assertion of $\mathrm {(ii)}$ is immediate from $\mathrm {(i)}$ . Using this, (Z3), and (Z4), we get the second assertion of $\mathrm {(ii)}$ for the case $m=1$ . For $m \neq 1$ , we reduce to the case $m=1$ using property (Z5). Statement $\mathrm {(iii)}$ is an immediate consequence of $\mathrm {(i)}$ . We only prove below the cases $m = 1$ of $\textrm{(iv--vi)}$ as the remaining cases of the corresponding statements can be reduced to these using (Z5). Statement $\mathrm {(iv)}$ is immediate for the case $m=1$ using (Z2) and (Z4). The case $m=1$ of $\mathrm {(v)}$ is precisely the statement of (Z4) when h is prime, and then the proof proceeds by induction. For the case $m=1$ of $\mathrm {(vi)}$ , ( $\rightarrow $ ) follows from (Z5), and ( $\leftarrow $ ) follows through a combination of Z5, $\mathrm {(v)}$ , and induction on the number of prime divisors of h.⊣

Proof We first prove that any integer k is a sum of two elements from $\mathrm {SF}^{\mathbb {Z}}$ . As $\mathrm {SF}^{\mathbb {Z}} =\kern3pt {-}\mathrm {SF}^{\mathbb {Z}}$ and the cases where $k=0$ or $k=1$ are immediate, we assume that $k>1$ . It follows from [Reference Rogers13] that the number of square-free positive integers less than k is at least $\frac {53k}{88}$ . Since $\frac {53}{88}> \frac {1}{2}$ , this implies k can be written as a sum of two positive square-free integers which gives us $\mathrm {SF}^{\mathbb {Z}}+\mathrm {SF}^{\mathbb {Z}} = \mathbb {Z}$ . Using this, the other two equalities follow immediately.⊣

Proof As $U^{\mathbb {Q}}_{p, l+n} = p^nU^{\mathbb {Q}}_{p, l}$ for all l and n, it suffices to show the statement for $l=0$ . Fix a prime p. We have for all $a \in \mathrm {SF}^{\mathbb {Q}}$ that

$$ \begin{align*}v_p(a) \geq 0 \ \text { if and only if } p^2 a \notin \mathrm{SF}^{\mathbb{Q}}.\end{align*} $$

Using Lemma 2.2, for all $a \in \mathbb {Q}$ , we have that $v_p(a) \geq 0$ if and only if there are $a_1, a_2 \in \mathbb {Q}$ such that

$$ \begin{align*}\big(a_1\in \mathrm{SF}^{\mathbb{Q}} \wedge v_p(a_1) \geq 0\big) \wedge \big(a_2\in \mathrm{SF}^{\mathbb{Q}} \wedge v_p(a_2) \geq 0\big) \ \text{ and } \ a =a_1+a_2.\end{align*} $$

Hence, the set $U^{\mathbb {Q}}_{p, 0} = \{a \in \mathbb {Q} : v_p(a) \geq 0 \} $ is existentially definable in $(\mathbb {Q}; \mathrm {SF}^{\mathbb {Q}})$ . The desired conclusion follows.⊣

Proof Fix a model $(G; \mathscr {U}^G, \mathscr {P}^G)$ of $\mathrm {Sf}^*_{\mathbb {Q}}$ . From (Q2) we have that $U_{p,0}^G$ is a subgroup of G for all p. It follows from (Q4) that $U^G_{p,l'} \subseteq U^G_{p,l} $ are subgroups of G for all p and $l\leq l'$ . With $U^G_{p, l} / U^G_{p, l'}$ being interpreted as an L-structure with 1 being $p^l+U^G_{p, l'}$ , we get an L-embedding of $ \mathbb {Z}/ (p^{l'-l}\mathbb {Z})$ into $U^G_{p, l} / U^G_{p, l'}$ using (Q3) and (Q4). Further, we see that $|U^G_{p, l} / U^G_{p, l'}|=p^{(l'-l)}$ using (Q2)–(Q5) and induction on $l'-l$ together with the third isomorphism theorem; and so the aforementioned embedding must be an isomorphism, finishing the proof for $\mathrm {(i)}$ . The first assertion of $\mathrm {(ii)}$ follows easily from (Q2)–Q(4). The second assertion for the case $m=1$ follows from the first assertion, (Q6), and (Q7). Finally, the case with $m\not =1$ follows from the case $m=1$ using (Q8). The proof for the replica of $\mathrm {(iii)}$ from Lemma 2.1 is a consequence of $\mathrm {(i)}$ and (Q4). The proofs for replicas of $\textrm{(iv--vi)}$ from Lemma 2.1 are similar to the proofs for $\textrm{(iv--vi)}$ of Lemma 2.1.⊣

Proof Let $\psi (x, z, z')$ be the special formula corresponding to a parameter choice $(k,m,\Theta )$ , and B, $(G; \mathscr {U}^G, \mathscr {P}^G)$ as in the statement of the lemma. Suppose $\psi (x, c, c')$ is a G-system, $p>B$ , and $\psi _p(x,z,z')$ is the associated p-condition of $\psi (x,z,z')$ . Then $\psi _p(x, c, c')$ is equivalent to

$$ \begin{align*}\bigwedge_{i=1}^n (kx+c_i \notin U_{p, 2+v_p(m)})\ \text{ in } (G; \mathscr{U}^G, \mathscr{P}^G).\end{align*} $$

We will show a stronger statement that there is a $a_p\in \mathbb {Z}$ satisfying the latter. Note that for all $d\notin U_{p,0}^G$ , we have that $(ka+d \notin U_{p, 0})$ for all $a\in \mathbb {Z}$ . From Lemma 2.5, we have that $U_{p,l}^G \subseteq U_{p,k}^G$ whenever $k<l$ , so we can assume that $c_i \in U_{p,0}^G$ for $i \in \{1, \ldots , n\}$ . In light of Lemmas 2.1 $\mathrm {(i)}$ and 2.5 $\mathrm {(i)}$ , we have that

$$ \begin{align*}U^G_{p, 0}/ U^G_{p, 2+v_p(m)} \cong_{L} \mathbb{Z} / (p^{2+v_p(m)}\mathbb{Z}).\end{align*} $$

It is easy to see that k is invertible $\mathrm {mod}\ p^{2+v_p(m)}$ and that $p^{2+v_p(m)}>n$ . Choose $a_p$ in $\{0, \ldots , p^{2+v_{p}(m)}-1\}$ such that the images of $ka_p+c_1, \ldots , ka_p+c_n$ in $\mathbb {Z} / (p^{2+v_p(m)}\mathbb {Z})$ are not $0$ . We check that $a_p$ is as desired.⊣

Proof Let B, $\Theta $ , and c be as stated. Fix $h\neq 0$ such that $\mathrm {gcd}(h,B!)=1$ . Hence, $v_p(h)=0$ for $p\leq B$ , and so the p-condition $\theta _p^h(x,z)$ is obtained from the p-condition $\theta _p(x,z)$ by replacing any atomic formula $kx +t(z) \in U_{p, l}$ appearing in $\theta _p(x,z)$ with $kx +t^h(z) \in U_{p, l}$ . Now for $p\leq B$ , let $l_p$ be the largest value of l occurring in an atomic formula in $\theta _p(x,z)$ . Set

$$ \begin{align*}D = \prod_{p \leq B} p^{l_p}.\end{align*} $$

Obtain $a_p \in \mathbb {Z}$ such that $\theta _p(a_p, c)$ holds in $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ . Equivalently, we have $\theta ^h_p(ha_p, hc)$ holds in $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ . By the Chinese remainder theorem, we get r in $\{0, \ldots , D-1\}$ such that

$$ \begin{align*}r\equiv_{p^{l_p}} a_p\quad \text{ for all } p \leq B.\end{align*} $$

We check that r is as desired. Suppose $a \in \mathbb {Z}$ is such that $a \equiv _D hr$ . By construction, if $p\leq B$ , $l \leq l_p$ , and $kx+t(z) \in U_{p,l }$ is any atomic formula, then $ka +t^h(hc) \in U^{\mathbb {Z}}_{p, l}$ if and only if $k(ha_p) +t^h(hc) \in U^{\mathbb {Z}}_{p, l}$ . It follows that $\theta ^h_p( a, hc)$ is equivalent to $\theta ^h_p( ha_p, hc)$ in $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ . Thus $\theta ^h_p( a, hc)$ holds for all $p \leq B$ .⊣

Proof Throughout this proof, let $\psi (x,z,z')$ , $\psi (x,c,c')$ , and $\Psi ^h(hs,ht)$ be as stated. We first make a number of observations. Suppose $\psi (x,z,z')$ corresponds to the parameter choice $(k,m,\Theta )$ and has a boundary B, and $\psi _p(x,z,z')$ is the associated p-condition of $\psi (x,z,z')$ . Then $\psi ^h(x,z,z')$ corresponds to the parameter choice $(k,hm,\Theta ^h)$ , and B is also a boundary of $\psi ^h(x,z,z')$ by Lemma 2.9. Moreover $\psi ^h_p(x,z,z')$ is the associated p-condition of $\psi ^h(x,z,z')$ . Since $\psi (x,c,c')$ is locally satisfiable in $\mathbb {Z}$ , we can use Lemma 2.10 to fix $D\in \mathbb {N}^{>0}$ and $r\in \{0,\ldots , D-1\}$ such that for each $h> 0$ with $\mathrm {gcd}(h,B!)=1$ , we have

$$ \begin{align*}a\equiv_{D} hr \text{ implies } \bigwedge_{p \leq B} \psi^h_p(a,hc, hc')\ \ \text{ for all } a \in \mathbb{Z}.\end{align*} $$

We note that D here is independent of the choice of h for all h with $\mathrm {gcd}(h,B!)=1$ .

We introduce a variant of $\Psi ^h(hs,ht)$ which is needed in our estimation of $|\Psi ^h(hs,ht)|$ . Until the end of the proof, set $l_p =2 + v_p(m)$ . Fix primes $p_1, \ldots , p_{n'}$ such that $p_1> c_i$ for all $i \in \{1, \ldots , n\}$ , $p_1> c^{\prime }_{i'}$ for all $i' \in \{1, \ldots , n'\}$ , and

$$ \begin{align*}B<p_1 < \cdots < p_{n'}.\end{align*} $$

For $M>p_{n'}$ , $h> 0$ with $\mathrm {gcd}(h,B!)=1$ , define $\Psi ^h_{M}(hs,ht)$ to be the set of $a \in \mathbb {Z}$ such that $hs<a<ht$ and

$$ \begin{align*}(a\equiv_{D} hr) \wedge\bigwedge_{B< p \leq M}\left( \bigwedge_{i=1}^{n}(ka+hc_i \not \equiv_{p^{l_{p}+v_p(h)}} 0)\right)\wedge\bigwedge_{i'=1}^{n'}(ka+hc^{\prime}_{i'} \notin P_{hm}^{\mathbb{Z}}).\end{align*} $$

It is not hard to see that $\Psi ^h(hs,ht)\cap \{a\in \mathbb {Z}: a\equiv _D hr\}\subseteq \Psi ^h_{M}(hs,ht)$ , and the latter is intended to be an upper approximation of the former. The desired lower bound for $|\Psi ^h(hs,ht)|$ will be obtained via a lower bound for $|\Psi ^h_{M}(hs,ht)|$ and an upper bound for $|\Psi ^h_{M}(hs,ht)\setminus \Psi ^h(hs,ht)| $ .

Now we work towards establishing a lower bound on $|\Psi ^h_{M}(hs,ht))|$ in the case where $M> p_{n'} $ , $h> 0$ , and $\text {gcd}(h, M!)=1$ . The latter assumption implies in particular that $p^{l_p + v_p(h)} = p^{l_p}$ for all $p \leq M$ . For $p>B $ , we have that $p>|k|$ and so k is invertible $\mathrm {mod}\ p^{l_p}$ . Set

$$ \begin{align*}\Delta = \{p : B < p \leq M\}\setminus \{ p_{i'} : 1 \leq i' \leq n' \}.\end{align*} $$

For $p\in \Delta $ , as k is invertible $\mathrm {mod}\ p^{l_p}$ , there are at least $p^{l_{p}}- n$ (note we have $p>B>n$ ) choices of $r_p$ in $\{0, \ldots , p^{l_{p}}-1 \}$ such that if $ a \equiv _{p^{l_p}} r_{p}$ , then

$$ \begin{align*}\bigwedge_{i=1}^n (ka+hc_i \not \equiv_{p^{l_p}} 0).\end{align*} $$

Suppose $p = p_{i'}$ for some $i' \in \{1, \ldots , n'\}$ . By the assumption that $\psi (x,c,c')$ is nontrivial, c has no common components with $c'$ . Since $\text {gcd}(h, M!)=1$ , h and p are coprime, and so the components of $hc$ and $hc'$ are pairwise distinct $\mathrm {mod}\ p^{l_p}$ . As k is invertible $\mathrm {mod}\ p^{l_p}$ , there is exactly one $r_p$ in $\{ 0, \ldots , p^{l_{p}}-1 \}$ such that if $a \equiv _{p^{l_p}} r_p$ , then

$$ \begin{align*}\bigwedge_{i=1}^n (ka+hc_i \not \equiv_{p^{l_p}} 0) \wedge (ka+hc^{\prime}_{i'} \equiv_{p^{l_p}} 0) \ \text{ and consequently }\ ka+hc^{\prime}_{i'} \notin P_{hm}^{\mathbb{Z}} .\end{align*} $$

Now it follows by the Chinese remainder theorem that,

$$ \begin{align*}|\Psi^h_{M}(hs,ht)|\geq \left\lfloor \frac{ht-hs}{D\prod_{B<p\leq M} p^{l_p}} \right\rfloor \prod_{p \in \Delta}\left(p^{l_p}-n\right).\end{align*} $$

Then it follows that,

$$ \begin{align*}|\Psi^h_{M}(hs,ht)|\geq \frac{ht-hs}{D}\prod_{p \leq p_{n'}}\frac{1}{p^{l_p}}\prod_{p> p_{n'}}^{\leq M} \left(1-\frac{n}{p^{l_p}}\right) - \prod_{p\leq M} p^{l_p}.\end{align*} $$

Set

$$ \begin{align*}\varepsilon = \frac{1}{2D}\prod_{p \leq p_{n'}}\frac{1}{p^{l_p}}\prod_{p> p_{n'}} \left(1-\frac{n}{p^{l_p}}\right).\end{align*} $$

Now as $l_p \geq 2$ , for $U \in \mathbb {N}^{>0}$ with $U>\max \{p_{n}',n^2\}$ we have that

$$ \begin{align*}\prod_{p> U} \left(1-\frac{n}{p^{l_p}}\right)>\prod_{p>U}\left(1-\frac{1}{p^{\frac{3}{2}}}\right).\end{align*} $$

Hence, it follows from Euler’s product formula that $\varepsilon>0$ . We now have

$$ \begin{align*}|\Psi^h_{M}(hs,ht)| \geq 2\varepsilon(ht-hs) - \prod_{p\leq M} p^{l_p}.\end{align*} $$

We note that $\varepsilon $ is independent of the choice of M and h, and will serve as the promised $\varepsilon $ in the statement of the lemma.

Next we obtain an upper bound on $|\Psi ^h_{M}(s,t)\setminus \Psi ^h(s,t)|$ for $M> p_{n'} $ , $h> 0$ , and $\text {gcd}(h, M!)=1$ . We arrange that $k>0$ by replacing c by $-c$ and $c'$ by $-c'$ if necessary. Note that an element $a \in \Psi ^h_{M}(s,t) \setminus \Psi ^h(s,t)$ must be such that

$$ \begin{align*}hks+hc_i < ka+hc_i < hkt+hc_i \quad \text{for all } i \in \{1, \ldots, n\}\end{align*} $$

and $ka+hc_i$ is a multiple of $p^{l_p}$ for some $p>M$ and $i \in \{1, \ldots , n\}$ . For each p and $i \in \{1, \ldots , n\}$ , the number of non-zero multiples of $p^{l_p}$ in $(hks+hc_i, hkt+hc_i)$ is

$$ \begin{align*}\lfloor hk(t \kern1pt{-}\kern1pt s) p^{-l_p}\rfloor \kern1pt{-}\kern1pt 2, \ \text{or}\ \lfloor hk(t \kern1pt{-}\kern1pt s) p^{-l_p}\rfloor \kern1pt{-}\kern1pt 1, \ \text{or}\ \lfloor hk(t -s) p^{-l_p}\rfloor, \ \text{or}\ \lfloor hk(t -s) p^{-l_p} \rfloor \kern1.2pt{+}\kern1.2pt 1.\end{align*} $$

In the last case, as $l_p \geq 2$ we moreover have

$$ \begin{align*}p^2\leq |hks+hc_i| \quad \text{ or }\quad p^2\leq |hkt+hc_i|,\end{align*} $$

and so

$$ \begin{align*}p\leq \sqrt{|hks+hc_i|} + \sqrt{|hkt+hc_i|}.\end{align*} $$

As $l_p \geq 2$ , we have $ \lfloor hk(t -s) p^{-l_p}\rfloor \leq hk(t-s)p^{-2}$ . Therefore we have that

$$ \begin{align*}|\Psi^h_{M}(s,t)\setminus \Psi^h(s,t)|\leq h(t-s)\sum_{p>M}\frac{nk}{p^2} + \left(\sum_{i=1}^{n}\sqrt{|hks+hc_i|} + \sqrt{|hkt+hc_i|}\right) +1 .\end{align*} $$

We now obtain N and C as in the statement of the lemma. Note that

$$ \begin{align*}\sum_{p>T}p^{-2} \leq \sum_{n>T}n^{-2} = O( T^{-1}).\end{align*} $$

Using this, we obtain $N \in \mathbb {N}^{>0}$ such that $N>p_{n'}$ and $ \sum _{p>N}knp^{-2}< \varepsilon $ where $\varepsilon $ is from the preceding paragraph. Set $C = - \prod _{p\leq N} p^{l_p} -1 $ . Combining the estimations from the preceding two paragraphs for $M=N$ it is easy to see that $\varepsilon , N, C$ are as desired.⊣

Proof We have that for all $c\in \mathbb {Z}$ , $\psi (x,c)=(x+c\in \mathrm {SF}^{\mathbb {Z}})\wedge (x+c+1\in \mathrm {SF}^{\mathbb {Z}})$ is a locally satisfiable $\mathbb {Z}$ -system. Applying Lemma 2.11 for $h=1$ , $s=0$ , and t sufficiently large we see there is a solution $a\in \mathbb {Z}$ for $\psi (x,c)$ .⊣

Proof We get the first part of the theorem by applying Lemma 2.11 for $h =1$ , $s =0$ , and t sufficiently large. As the second part of the theorem follows easily from the third part, it will be enough to show that the $\mathrm {OSf}^*_{\mathbb {Q}}$ -model $(\mathbb {Q}; <, \mathscr {U}^{\mathbb {Q}}, \mathscr {P}^{\mathbb {Q}})$ is generic. Throughout this proof, suppose $\psi (x,z,z)$ is a special formula and $\psi (x, c, c')$ is a $\mathbb {Q}$ -system which is nontrivial and locally satisfiable in $\mathbb {Q}$ . Our job is to show that the $\mathbb {Q}$ -system $\psi (x, c, c')$ has a solution in the $\mathbb {Q}$ -interval $(b, b')^{\mathbb {Q}}$ for an arbitrary choice of $b, b' \in \mathbb {Q}$ such that $b<b'$ .

We first reduce to the special case where $\psi (x, c, c')$ is also a $\mathbb {Z}$ -system which is nontrivial and locally satisfiable in $\mathbb {Z}$ . Let B be the boundary of $\psi (x,z,z')$ and for each p, let $\psi _p(x,z,z')$ be the associated p-condition of $\psi (x,z,z')$ . Using the assumption that $\psi (x, c, c')$ is locally satisfiable $\mathbb {Q}$ -system, for each $p<B$ we obtain $a_p \in \mathbb {Q}$ such that $\psi _p(a_p,c,c')$ holds. Let $h>0$ be such that

$$ \begin{align*}hc \in \mathbb{Z}^n, hc' \in \mathbb{Z}^{n'}, \text{ and } ha_p \in \mathbb{Z} \text{ for all } p<B.\end{align*} $$

Then by the choice of h, and Lemmas 2.7 and 2.9, the h-conjugate $\psi ^h(x,hc,hc')$ of $\psi (x, c, c')$ is a $\mathbb {Z}$ -system which is nontrivial and locally satisfiable in $\mathbb {Z}$ . On the other hand, $\psi (x,c,c')$ has a solution in an interval $(b,b')^{\mathbb {Q}}$ if and only if

$$ \begin{align*}\psi^h(x,hc,hc') \text{ has a solution in } (hb,hb')^{\mathbb{Q}}.\end{align*} $$

Hence, by replacing $\psi (x,z,z')$ with $\psi ^h(x,z,z')$ , $\psi (x, c, c')$ with $\psi ^h(x,hc,hc')$ , and $(b, b')^{\mathbb {Q}}$ with $(hb, hb')^{\mathbb {Q}}$ if necessary we get the desired reduction.

We show $\psi (x, c, c')$ has a solution in the $\mathbb {Q}$ -interval $(b, b')^{\mathbb {Q}}$ for the special case in the preceding paragraph. By an argument similar to the preceding paragraph, it suffices to show that for some $h\neq 0$ , $\psi ^h(x, hc, hc')$ has a solution in $(hb, hb')^{\mathbb {Q}}$ . Applying Lemma 2.11 for $s =b$ , $t=b'$ , and h sufficiently large satisfying the condition of the lemma, we get the desired conclusion.⊣

Proof Let $\varphi (x, y)$ be a quantifier-free $L^*_{\mathrm {u}}$ -formula. We will use the following disjunction observation several times in our proof: If $\varphi (x,y)$ is a finite disjunction of quantifier-free $L^*_{\mathrm {u}}$ -formulas and we have proven the desired statement for each of those, then the desired statement for $\varphi (x,y)$ follows. In particular, it allows us to assume that $\varphi (x, y)$ is the conjunction

$$ \begin{align*}\rho(y) \wedge \varepsilon(x, y) \wedge \bigwedge_p \eta_p(x, y) \wedge \bigwedge_{i=1}^n (k_ix+t_i(y) \in P_{m_i}) \wedge \bigwedge_{i=1}^{n'} (k^{\prime}_ix+t^{\prime}_{i}(y) \notin P_{m^{\prime}_i}),\end{align*} $$

where $\rho (y)$ is a quantifier-free $L^*_{\mathrm {u}}$ -formula, $\varepsilon (x, y)$ is an equational condition, $k_1, \ldots , k_n$ and $k_1', \ldots , k^{\prime }_{n'}$ are in $\mathbb {Z}\setminus \{0\}$ , $m_1, \ldots , m_n$ and $m^{\prime }_1, \ldots , m^{\prime }_{n'}$ are in $\mathbb {N}^{\geq 1}$ , $t_1(y), \ldots , t_n(y)$ and $t^{\prime }_1(y), \ldots , t^{\prime }_n(y)$ are $L^*_{\mathrm {u}}$ -terms with variables in y, $\eta _p(x,y)$ is a p-condition for each p, and $\eta _p(x,y)$ is trivial for all but finitely many p.

We make further reductions to the form of $\varphi (x,y)$ . Set $t(y) =(t_1(y), \ldots , t_n(y))$ and $t'(y)=(t^{\prime }_1(y), \ldots , t^{\prime }_{n'}(y))$ . Using the disjunction observation and the fact that

$$ \begin{align*}(x+ y_j \in P_1) \vee (x + y_j \notin P_1)\end{align*} $$

is a tautology for every component $y_j$ of y, we can assume that either $x+ y_j \in P_1$ or $x + y_j \notin P_1$ are among the conjuncts of $\varphi (x, y)$ , and so $y_j$ is among the components of $t(y)$ or $t'(y)$ . Then we obtain for each prime p a p-condition $\theta _p(x, z, z')$ such that $\theta _p(x, t(y), t'(y))$ is logically equivalent to $\eta _p( x, y)$ . Let $\xi (x, z, z')$ be the formula

$$ \begin{align*}\bigwedge_p \theta_p(x, z, z') \wedge \bigwedge_{i=1}^n (k_ix+z_i\in P_{m_i}) \wedge \bigwedge_{i=1}^{n'} (k^{\prime}_ix+z^{\prime}_i \notin P_{m^{\prime}_i}).\end{align*} $$

Clearly, $\varphi (x,y)$ is equivalent to the formula $\rho (y) \wedge \varepsilon (x, y) \wedge \xi (x, t(y), t'(y))$ , so we can assume that $\varphi (x,y)$ is the latter.

We need a small observation. For a p-condition $\theta _p(z)$ and $h \neq 0$ , we will show that there is another p-condition $\eta _p(z)$ such that modulo $\mathrm {Sf}^*_{\mathbb {Z}}$ and $\mathrm {Sf}^*_{\mathbb {Q}}$ ,

$$ \begin{align*}\eta_p(z_1, \ldots, z_{i-1}, hz_i, z_{i+1}, \ldots, z_n) \ \text{ is equivalent to } \ \theta_p(z).\end{align*} $$

For the special case where $\theta _p(z)$ is $t(z) \in U_{p, l}$ , the conclusion follows from Lemmas 2.1(iii) and 2.5(iii) and the fact that there is an $L^*_{\mathrm {u}}$ -term $t'(z)$ such that $t'(z, \ldots , z_{i-1}, hz_i, z_{i+1}, \ldots , z_n) = ht(z).$ The statement of the paragraph follows easily from this special case.

With $\varphi (x,y)$ as in the end of the second paragraph, we further reduce the main statement to the special case where there is $k\neq 0$ such that $k_i = k^{\prime }_{i'} =k$ for all $i\in \{1, \ldots , n\}$ and $i' \in \{ 1, \ldots , n'\}$ . Choose $k\neq 0 $ to be a common multiple of $k_1, \ldots , k_n$ and $k^{\prime }_1, \ldots k^{\prime }_{n'}$ . Then by Lemmas 2.1(vi) and 2.5(iii), we have for each $i \in \{1, \ldots , n\} $ that

$$ \begin{align*}k_ix+z_i \in P_{m_i}\ \text{ is equivalent to }\ (kx+kk^{-1}_iz_i \in P_{kk^{-1}_im_i}) \text{ modulo either } \mathrm{Sf}^*_{\mathbb{Z}} \text{ or }\mathrm{Sf}^*_{\mathbb{Q}}.\end{align*} $$

We have a similar observation for k and $k^{\prime }_{i'}$ with $i' \in \{1, \ldots , n'\}$ . The desired reduction easily follows from these observations and the preceding paragraph.

Continuing with the reduction in the preceding paragraph, we next arrange that there is $m> 0$ such that $m_i = m^{\prime }_{i'} =m$ for all $i\in \{1, \ldots , n\}$ and $i' \in \{ 1, \ldots , n'\}$ . Let m be a common multiple of $m_1, \ldots , m_n$ and $m^{\prime }_1, \ldots m^{\prime }_{n'}$ . By Lemmas 2.1(v,vi) and 2.5(iii), we have for $i \in \{ 1, \ldots , n\}$ that modulo either $\mathrm {Sf}^*_{\mathbb {Z}}$ or $\mathrm {Sf}^*_{\mathbb {Z}}$ or $\mathrm {Sf}^*_{\mathbb {Q}}$

$$ \begin{align*}kx+z_i \in P_{m_i} \ \text{ is equivalent to }\ kx+z_i \in P_{m} \wedge \bigwedge_{p \mid \frac{m}{m_i}} kx+z_i \notin U_{p, 2+ v_p(m_i)}\end{align*} $$

and for $i' \in \{ 1, \ldots , n'\}$ that modulo either $\mathrm {Sf}^*_{\mathbb {Z}}$ or $\mathrm {Sf}^*_{\mathbb {Q}}$

$$ \begin{align*}kx+z^{\prime}_{i'} \notin P_{m^{\prime}_{i'}} \ \text{ is equivalent to }\ kx+z^{\prime}_{i'} \notin P_{m} \vee \bigvee_{p \mid \frac{m}{m^{\prime}_{i'}}} kx+z^{\prime}_{i'} \in U_{p,2+ v_p(m^{\prime}_{i'})} .\end{align*} $$

It follows that $\varphi (x, y)$ is equivalent to a disjunction of formulas of the form we are aiming for. The desired conclusion of the lemma follows from the disjunction observation.⊣

Proof If $\varphi (x,z)$ is a p-condition, then by Lemma 2.1 $(\mathrm {i})$ , modulo $\mathrm {Sf}^*_{\mathbb {Z}}$ , it is a Boolean combination of atomic formulas of the form $kx +t(z) \in U_{p, l}$ where $t(z)$ is an $L^*_{\mathrm {u}}$ -term, and $l>0$ . Let $l_p$ be the largest value of l occurring in such atomic formulas, and set

$$ \begin{align*}S=\{(m_1,\ldots,m_n): 0 \leq m_i < p^{l_p} \text{ for each }i, \text{ and } (\mathbb{Z}; \mathscr{U}^{\mathbb{Z}}) \models \exists x \varphi(x,m_1,\ldots,m_n)\}.\end{align*} $$

Then by Lemma 2.1 $(\mathrm {i})$ , modulo $\mathrm {Sf}^*_{\mathbb {Z}}$ , $\exists x \varphi (x,z)$ is equivalent to the p-condition $\bigvee _{(m_1,\ldots ,m_n)\in S} (\bigwedge _{i=1}^{n} (z_i\equiv _{p^{l_p}} m_i))$ .

Now, we proceed to prove the statement for models of $\mathrm {Sf}^*_{\mathbb {Q}}$ . Throughout the rest of the proof, suppose $\varphi (x,z)$ is a p-condition, k, $k'$ , l, $l'$ are in $\mathbb {Z}$ , and $t(z), t'(z)$ are $L_{\mathrm {u}}^*$ -terms. First, we consider the case where $\varphi (x,z)$ is a p-condition of the form $kx+t(z) \in U_{p,l}$ . The case $k=0$ is trivial. If $k \neq 0$ , then $\exists x (kx+t(z) \in U_{p,l})$ is tautological modulo $\mathrm {Sf}^*_{\mathbb {Q}}$ following from (Q1) in the definition of $\mathrm {Sf}^*_{\mathbb {Q}}$ and Lemma 2.5(i).

We next consider the case where $\varphi (x,z)$ is a finite conjunction of p-conditions in $L^*_{\mathrm {u}}(x, z)$ such that one of the conjuncts is $kx+t(z) \in U_{p,l}$ with $k \neq 0$ and the other conjuncts are either of the form $k'x+t'(z) \in U_{p,l'}$ or of the form $k'x+t'(z) \notin U_{p,l'}$ where we do allow $l'$ to vary. It follows from Lemma 2.5(i) that if $k = k'$ , $l\geq l'$ , then

$$ \begin{align*}k'x + t'(z)\in U_{p, l'} \ \text{ if and only if } \ t(z)-t'(z) \in U_{p, l'}.\end{align*} $$

So we have means to replace conjuncts of $\varphi (x,z)$ by terms independent of the variable x. However, the above will not work if $k \neq k'$ or $l<l'$ . By Lemma 2.5(iii), across models of $\mathrm {Sf}^*_{\mathbb {Q}}$ , we have that

$$ \begin{align*}kx+ t(z) \in U_{p, l} \text{ if and only if } hkx + ht(z) \in U_{p, l+ v_p(h)} \ \ \text{ for all } h \neq 0.\end{align*} $$

From this observation, it is easy to see that we can resolve the issue of having $k \neq k'$ , and moreover arrange that $l\geq 0$ which will be used in the next observation. By Lemma 2.5(i,ii), across models of $\mathrm {Sf}^*_{\mathbb {Q}}$ , we have that

$$ \begin{align*}kx + t(z) \in U_{p, l} \ \text{ if and only if } \ \bigvee_{i=1}^{p^m} kz + t(z) + ip^{l} \in U_{p, l+m} \text{ for all } l\geq 0 \text{ and all } m.\end{align*} $$

Using the preceding two observations we resolve the issue of having $l<l'$ . The statement of the lemma for this case then follows from the second paragraph.

We now prove the full lemma. It suffices to consider the case where $\varphi (x,z)$ is a conjunction of atomic formulas. In view of the preceding paragraph, we reduce further to the case where $\varphi (x,z)$ is of the form

$$ \begin{align*}\bigwedge_{i=1}^m kx+t_i(z) \notin U_{p,l_i}.\end{align*} $$

We now show that $\exists x\varphi (x,z)$ is a tautology over $\mathrm {Sf}^*_{\mathbb {Q}}$ and thus complete the proof. Suppose $(G; \mathscr {U}^G, \mathscr {P}^G) \models \mathrm {Sf}^*_{\mathbb {Q}} $ and $c \in G^n$ . It suffices to find $a \in G$ such that the p-condition $ka+t_i(c) \notin U^G_{p,l_i}$ holds for all $i \in \{1, \ldots , m\}$ . Without loss of generality, we assume that $t_1(c), \ldots , t_{m'}(c)$ are not in $U^G_{p,l}$ for all l and that $t_{m'+1}(c), \ldots , t_{m}(c)$ are in $U^G_{p,l_0}$ for some $l_0 $ such that $l_0 < l_i$ for all $i \in \{1, \ldots , m\}$ . Using Lemma 2.5(ii), choose a such that $ka \in U^G_{p,l_0-1} \setminus U^G_{p,l_0}$ . It follows from Lemma 2.5(i) that a is as desired.⊣

Proof As the three situations are very similar, we will only present here the proof that $\mathrm {OSF}^*_{\mathbb {Q}}$ admits quantifier elimination. The proof for $\mathrm {SF}^*_{\mathbb {Z}}$ and $\mathrm {SF}^*_{\mathbb {Q}}$ are simpler as there is no ordering involved. Along the way we point out the necessary modifications needed to get the proof for $\mathrm {SF}^*_{\mathbb {Z}}$ and $\mathrm {SF}^*_{\mathbb {Q}}$ . Fix $\mathrm {OSF}^*_{\mathbb {Q}}$ -models $(G; <, \mathscr {U}^G, \mathscr {P}^G)$ and $(H; <, \mathscr {U}^H, \mathscr {P}^H)$ such that the latter is $|G|^+$ -saturated. Suppose

$$ \begin{align*}f \text{ is a partial } L_{\mathrm{ou}}^*\text{-embedding from } (G; <, \mathscr{U}^G, \mathscr{P}^G) \text{ to } (H; <, \mathscr{U}^H , \mathscr{P}^H ),\end{align*} $$

in other words, f is an $L_{\mathrm {ou}}^*$ -embedding of an $L_{\mathrm {ou}}^*$ -substructure of $(G; <, \mathscr {U}^G, \mathscr {P}^G)$ into $(H; <, \mathscr {U}^H , \mathscr {P}^H)$ . By a standard test, it suffices to show that if $\text {Domain}(f) \neq G$ , then there is a partial $L_{\mathrm {ou}}^*$ -embedding from $(G; <, \mathscr {U}^G, \mathscr {P}^G)$ to $(H; <, \mathscr {U}^H, \mathscr {P}^H)$ which properly extends f. For the corresponding statements with $\mathrm {SF}^*_{\mathbb {Z}}$ or $\mathrm {SF}^*_{\mathbb {Q}}$ , we need to consider instead $(G; \mathscr {U}^G, \mathscr {P}^G)$ and $(H; \mathscr {U}^H, \mathscr {P}^H)$ depending on the situation.

We remind the reader that our choice of language includes a symbol for additive inverse, and so $\text {Domain}(f)$ is automatically a subgroup of G. Suppose $\text {Domain}(f)$ is not a pure subgroup of G, that is, there is an element $\text {Domain}(f)$ which is n-divisible in G but not n-divisible in $\text {Domain}(f)$ for some $n>0$ . Then there is prime p and a in $G \setminus \text {Domain}(f)$ such that $pa \in \text {Domain}(f) $ . Using divisibility of H, we get $b \in H$ such that $pb = f(pa)$ . Let g be the extension of f given by

$$ \begin{align*}ka + a' \mapsto kb + f(a') \quad \text { for } k\in \{ 1, \ldots, p-1\} \text{ and } a' \in \text{Domain}(f).\end{align*} $$

It is routine to check that g is an ordered group isomorphism from $\langle \text {Domain}(f), a\rangle $ to $\langle \text {Image}(f), b\rangle $ . It is also easy to check using Lemma 2.5(iii) that $ka + a' \in U^G_{p',l}$ if and only if $kb + f(a') \in U^G_{p',l}$ and $ka + a' \in P^G_{m}$ if and only if $kb + f(a') \in U^G_{m}$ for all k, l, m, primes $p'$ , and $a' \in \text {Domain}(f)$ . Hence,

$$ \begin{align*}g \text{ is a partial } L_{\mathrm{ou}}^*\text{-embedding } \text{ from } (G; <, \mathscr{U}^G, \mathscr{P}^G) \text{ to } (H; <, \mathscr{U}^H , \mathscr{P}^H ).\end{align*} $$

Clearly, g properly extends f, so the desired conclusion follows. The proof for $\mathrm {SF}^*_{\mathbb {Q}}$ is the same but without the verification that the ordering is preserved. The situation for $\mathrm {SF}^*_{\mathbb {Z}}$ is slightly different as H is not divisible. However, for all primes $p'$ , $p'a$ is in $p'G = U^G_{p', 1}$ , and so $f(p'a)$ is in $ U^H_{p', 1} = p'H$ . The proof proceeds similarly using Lemma 2.1(iv–vi).

The remaining case is when $\text {Domain}(f) \neq G$ is a pure subgroup of G. Let a be in $G \setminus \text {Domain}(f)$ . We need to find b in $H \setminus \text {Image}(f)$ such that

$$ \begin{align*}\text{qftp}_{L_{\mathrm{ou}}^*}(a / \text{Domain}(f)) = \text{qftp}_{L_{\mathrm{ou}}^*}(b / \text{Image}(f)).\end{align*} $$

By the fact that $\text {Domain}(f)$ is pure in G, and Corollary 3.2, $\text {qftp}_{L_{\mathrm {ou}}^*}(a \mid \text {Domain}(f))$ is isolated by formulas of the form

$$ \begin{align*}\rho(b) \wedge \lambda(x,b) \wedge \psi(x, t(b), t'(b)),\end{align*} $$

where $\rho (y)$ is a quantifier-free $L^*_{\mathrm {ou}}$ -formula, $\lambda (x,y)$ is an order condition, $\psi (x, z, z')$ is a special formula, $t(y)$ and $t'(y)$ are tuples of $L_{\mathrm {ou}}^*$ -terms of suitable length, b is a tuple of elements of $\text {Domain}(f)$ of suitable length, and $\psi (x, t(b), t'(b))$ is a nontrivial $\text {Domain}(f)$ -system. As $\text {Domain}(f)$ is a pure subgroup of G, we can moreover arrange that $\lambda (x,b)$ is simply the formula $b_1 < x <b_2$ . Since f is an $L_{\mathrm {ou}}^*$ -embedding, $\rho (f(b))$ holds, $f(b_1) < f(b_2)$ , and $\psi \big (x, t(f(b)), t'(f(b))\big ) $ is a nontrivial $\text {Image}(f)$ -system. Using the fact that $(H; <, \mathscr {U}^H , \mathscr {P}^H )$ is $|G|^+$ -saturated, the problem reduces to showing that

$$ \begin{align*}\psi\Big(x, f\big(t(b)\big), f\big(t'(b)\big)\Big) \ \text{ has a solution in the interval } (f(b_1), f(b_2))^H.\end{align*} $$

As $\psi (x, t(b), t'(b))$ is satisfiable in G, it is locally satisfiable in G by Lemma 2.6. For each p, let $\psi _p(x, z, z')$ be the associated p-condition of $\psi (x, z, z')$ . By Lemma 3.3, for all p, the formula $\exists x \psi _p(x, z, z')$ is equivalent modulo $\mathrm {Sf}^*_{\mathbb {Q}}$ to a quantifier free formula in $L^*_{\mathrm {u}}(z, z')$ . Hence, $\exists x \psi _p\Big (x, f\big (t(b)\big ), f\big (t'(b)\big )\Big )$ holds in $(H;<, \mathscr {U}^H, \mathscr {P}^H)$ for all p. Thus,

$$ \begin{align*}\text{the } \text{Image}(f)\text{-system }\psi\Big(x, f\big(t(b)\big), f\big(t'(b)\big)\Big) \text{ is locally satisfiable in } H.\end{align*} $$

The desired conclusion follows from the genericity of $(H; <, \mathscr {U}^H, \mathscr {P}^H)$ . The proofs for $\mathrm {SF}^*_{\mathbb {Z}}$ and $\mathrm {SF}^*_{\mathbb {Q}}$ are similar. However, we have there the formula $\bigwedge _{i =1}^k x \neq b_i$ with $k \leq |b|$ instead of the formula $b_1< x< b_2$ , Lemma 3.1 instead of Corollary 3.2, and the corresponding notion of genericity instead of the current one.⊣

Proof By Lemma 2.1(ii), the subgroup generated by $1$ in an arbitrary model $(G; \mathscr {U}^G, \mathscr {P}^G)$ of $\mathrm {SF}^*_{\mathbb {Z}}$ is an isomorphic copy of $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ . Hence by Theorem 3.4, $\mathrm {SF}^*_{\mathbb {Z}}$ is complete, and on the other hand $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}}) \models \mathrm {SF}^*_{\mathbb {Z}} $ by Theorem 2.14. The first statement of the corollary follows. The justification of the second statement is obtained in a similar fashion.⊣

Proof of Theorem 1.1, part 1 We show that the $L_{\mathrm {u}}$ -theory of $(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ is model complete and decidable. For all p, $l\geq 0$ , $m>0$ , and all $a \in \mathbb {Z}$ , we have the following:

1. (1) $a \in U^{\mathbb {Z}}_{p, l}$ if and only there is $b\in \mathbb {Z}$ such that $p^lb =a$ ;

2. (2) $a \notin U^{\mathbb {Z}}_{p, l}$ if and only if for some $i \in \{1, \ldots , p^l-1\}$ , there is $b\in \mathbb {Z}$ such that $p^lb =a+i$ ;

3. (3) $a \in P^{\mathbb {Z}}_m$ if and only if for some $d \mid m$ , there is $b\in \mathbb {Z}$ such that $a =bd$ and $b\in \mathrm {SF}^{\mathbb {Z}}$ ;

4. (4) $a \notin P^{\mathbb {Z}}_m$ if and only if for all $d \mid m$ , either for some $i \in \{1, \ldots , d-1\}$ , there is $b\in \mathbb {Z}$ such that $db =a+i$ or there is $b \in \mathbb {Z}$ such that $a =bd$ and $b \notin \mathrm {SF}^{\mathbb {Z}}$ .

As $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}}) \models \mathrm {SF}^*_{\mathbb {Z}}$ , it then follows from Theorem 3.4 and the above observation that every $0$ -definable set in $(\mathbb {Z}, \mathrm {SF}^{\mathbb {Z}})$ is existentially $0$ -definable. Hence, the theory of $(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ is model complete. The decidability of $\text {Th}(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ is immediate from the preceding corollary.⊣

Proof Suppose a is as stated. If $a \in \mathrm {SF}^{\mathbb {Q}}$ we can choose $\varepsilon =0$ , so suppose a is in $\mathbb {Q} \setminus \mathrm {SF}^{\mathbb {Q}}$ . We can also arrange that $a>0$ . Then there are $m, n, k \in \mathbb {N}^{\geq 1}$ such that

$$ \begin{align*}a = \frac{m}{np^k},\ (m, n)=1,\ (m, p)=1, \text{ and } (n, p)=1.\end{align*} $$

It suffices to show there is $b \in \mathbb {Z}$ such that $m+ p^kb$ is a square-free integer as then

$$ \begin{align*}a+ \frac{b}{n} = \frac{m+ p^kb}{np^k} \in \mathrm{SF}^{\mathbb{Q}}.\end{align*} $$

For all prime l, $p^kb_l+m \notin U^{\mathbb {Q}}_{l,2}$ for $b_l=0$ or $1$ . The conclusion then follows from the genericity of $( \mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ as established in Theorem 2.14.⊣

Proof We will instead show that $\mathbb {Q}\setminus U^{\mathbb {Q}}_{p, l} = \{ a : v_p(a) < l \}$ is existentially $0$ -definable for all p and l. As $\mathbb {Q} \setminus U^{\mathbb {Q}}_{p, l+n} = p^n( \mathbb {Q} \setminus U^{\mathbb {Q}}_{p, l})$ for all p, l, and n, it suffices to show the statement for $l=0$ . Fix a prime p. By the preceding lemma we have that for all $ a$ , $v_p(a)<0$ if and only if

$$ \begin{align*}\text{ there is } \varepsilon \text{ such that } v_p(\varepsilon) \geq 0, a+\varepsilon \in \mathrm{SF}^{\mathbb{Q}} \text{ and } v_p(a+\varepsilon) <0.\end{align*} $$

We recall that $\{\varepsilon : v_p(\varepsilon ) \geq 0 \}$ is existentially $0$ -definable by Lemma 2.3. Also, for all $a' \in \mathrm {SF}^{\mathbb {Q}}$ , we have that $v_p(a')< 0$ is equivalent to $p^2a' \in \mathrm {SF}^{\mathbb {Q}}$ . The conclusion hence follows.⊣

Proof of Theorems 1.3 and 1.4, part 1 We show that the $L_{\mathrm {u}}$ -theory of $(\mathbb {Q}; \mathrm {SF}^{\mathbb {Q}})$ and the $L_{\mathrm {ou}}$ -theory of $(\mathbb {Q}; <, \mathrm {SF}^{\mathbb {Q}} )$ are model complete and decidable. The proof is almost exactly the same as that of part 1 of Theorem 1.1. It follows from Lemma 2.3 and Corollary 3.7 that for all p and l, the sets $U^{\mathbb {Q}}_{p, l}$ are existentially and universally $0$ -definable in $(\mathbb {Q}; \mathrm {SF}^{\mathbb {Q}})$ . For all m, $P^{\mathbb {Q}}_m = m\mathrm {SF}^{\mathbb {Q}}$ and $\mathbb {Q} \setminus P^{\mathbb {Q}}_m = m( \mathbb {Q} \setminus \mathrm {SF}^{\mathbb {Q}})$ are clearly existentially $0$ -definable. The conclusion follows.⊣

Proof Suppose $c_1, \ldots , c_n$ are as given. Let $c^{\prime }_1, \ldots , c^{\prime }_{n'}$ be the listing in increasing order of elements in the set of $c \in \mathbb {N}$ such that $c_1 \leq c \leq c_n$ and $c \neq c_i$ for $i \in \{1, \ldots , n\}$ . The conclusion that there are infinitely many a such that

$$ \begin{align*}\bigwedge_{i=1}^n (a+c_i \in \mathrm{SF}^{\mathbb{Z}}) \wedge \bigwedge_{i=1}^{n'} (a+c^{\prime}_i \notin \mathrm{SF}^{\mathbb{Z}})\end{align*} $$

follows from the assumptions about $c_1, \ldots , c_n$ and the genericity of $( \mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ as established in Theorem 2.14.⊣

Proof For each p, we can obtain $a\in \{1,2,\ldots ,p^2-1\} $ such that

$$ \begin{align*}a\not\equiv_{p^2}-m^2 \text{ for all } m.\end{align*} $$

Hence, for any given $n>0$ and p, the p-condition $\bigwedge _{i=1}^{n}(x+i^2\notin U^{\mathbb {Z}}_{p,2})$ has a solution. The result now follows immediately from the preceding lemma.⊣

Proof of Theorem 1.2 It suffices to show that $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$ interprets multiplication on $\mathbb {N}$ . Let T be the set of $(a, b) \in \mathbb {N}^2$ such that for some $n \in \mathbb {N}^{\geq 1},$

$$ \begin{align*}b= a+n^2 \text{ and } a+1, a+4, \ldots, a+n^2 \text{ are consecutive square-free integers}.\end{align*} $$

The set T is definable in $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$ as $(a, b) \in T$ and $b\neq a+1$ if and only if $a+4\leq b$ , $a+1$ , and $a+4$ are consecutive square-free integers, b is square-free, and whenever c, d, and e are consecutive square-free integers with $a< c <d< e \leq b$ , we have that

$$ \begin{align*}(e-d)-(d-c) =2.\end{align*} $$

Let S be the set $\{ n^2 : n \in \mathbb {N}\}$ . If $c=0$ or there are $a, b$ such that $(a, b) \in T$ and $b-a =c$ , then $c=n^2$ for some n. Conversely, if $c =n^2$ , then either $c=0$ or by Corollary 3.9,

$$ \begin{align*}\text{ there is } (a,b) \in T \text{ with } b-a =c.\end{align*} $$

Therefore, S is definable in $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$ . The map $n \mapsto n^2$ in $\mathbb {N}$ is definable in $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$ as $b =a^2$ if and only if $b\in S$ and whenever $c\in S$ is such that $c>b$ and $b, c$ are consecutive in S, we have that $c-b = 2a+1$ . Finally, $c =ba$ if and only if $2c= (b+a)^2-b^2-a^2$ . Thus, multiplication on $\mathbb {N}$ is definable in $(\mathbb {Z}; <, \mathrm {SF}^{\mathbb {Z}})$ .⊣

Proof Recall that every p-condition is equivalent modulo $\mathrm {SF}^*_{\mathbb {Z}}$ to a formula in the language L of groups, and the reduct of $\mathrm {SF}^*_{\mathbb {Z}}$ to L is simply $\text {Th}(\mathbb {Z})$ . Hence, the desired conclusion is an immediate consequence of the well-known fact that $\text {Th}(\mathbb {Z})$ is superstable of U-rank $1$ ; see for example [Reference Belegradek, Peterzil and Wagner3].⊣

Proof of Theorem 1.1, part 2 We first show that $\text {Th}(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ is supersimple of U-rank $1$ ; see [Reference Kim10, p. 36] for a definition of U-rank or SU-rank. By the fact that $(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ has the same definable sets as $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ and Corollary 3.5, we can replace $\text {Th}(\mathbb {Z}; \mathrm {SF}^{\mathbb {Z}})$ with $\mathrm {SF}^*_{\mathbb {Z}}$ . Suppose $(\mathbb {G}; \mathscr {U}^{\mathbb {G}}, \mathscr {P}^{\mathbb {G}}) \models \mathrm {SF}^*_{\mathbb {Z}}$ . Our job is to show that every $L^*_{\mathrm {u}}(\mathbb {G})$ -formula $\varphi (x,b)$ which forks over a small subset A of $\mathbb {G} $ must define a finite set in $\mathbb {G}$ . We can easily reduce to the case that $\varphi (x,b)$ divides over A. Moreover, we can assume that $\varphi (x,b)$ is quantifier free by Theorem 3.4 which states that $(\mathbb {G}; \mathscr {U}^{\mathbb {G}}, \mathscr {P}^{\mathbb {G}})$ admits quantifier elimination. Using Lemma 3.1, we can also arrange that $\varphi (x, b)$ has the form

$$ \begin{align*}\rho(b) \wedge \varepsilon(x, b) \wedge \psi(x, t(b), t'(b)),\end{align*} $$

where $\rho (y)$ is a quantifier-free formula, $\varepsilon (x,y)$ is an equational condition, $t(y)$ and $t'(y)$ are tuples of $L^*_{\mathrm {u}}$ -terms with length n and $n'$ respectively, and $\psi (x, z, z')$ is a special formula.

Suppose to the contrary that $\varphi (x,b)$ divides over A but $\varphi (x,b)$ defines an infinite set in $\mathbb {G}$ . From the first assumption, we get an infinite ordering I and a family $(\sigma _i)_{i \in I}$ of $L^*_{\mathrm {u}}$ -automorphisms of $(\mathbb {G}; \mathscr {U}^{\mathbb {G}}, \mathscr {P}^{\mathbb {G}})$ such that $(\sigma _i (b))_{i \in I}$ is indiscernible over A and $\bigwedge _{i \in I} \varphi (x, \sigma _i (b))$ is inconsistent. As $\varphi (x,b)$ defines an infinite set in $\mathbb {G}$ , we get from the second assumption that $\rho (b)$ holds in $\mathbb {G}$ , $\varepsilon (x, b)$ defines a cofinite set in $\mathbb {G}$ , and $\psi (x,t(b), t'(b))$ defines an infinite hence non-empty set in $\mathbb {G}$ . As $(\sigma _i (b))_{i \in I}$ is indiscernible, we have that $\rho (\sigma _i (b))$ holds in $\mathbb {G}$ and $\varepsilon (x, \sigma _i (b))$ defines a cofinite set in $\mathbb {G}$ for all $i \in I$ . Using the saturation of $\mathbb {G}$ , we get a finite set $\Delta \subseteq I$ such that

$$ \begin{align*}\theta_{\Delta}(x):= \bigwedge_{i \in \Delta} \psi\big(x, t(\sigma_i (b)), t'(\sigma_i (b))\big) \text{ defines a finite set in } \mathbb{G}.\end{align*} $$

As $\theta _{\Delta }(x)$ is a conjunction of $\mathbb {G}$ -systems given by the same special formula, it is easy to see that $\theta _{\Delta }(x)$ is also a $\mathbb {G}$ -system.

We will show that $\theta _{\Delta }(x)$ defines an infinite set and thus obtain the desired contradiction. As $(\mathbb {G}; \mathscr {U}^{\mathbb {G}}, \mathscr {P}^{\mathbb {G}})$ is a model of $ \mathrm {SF}^*_{\mathbb {Z}}$ and hence generic, it suffices to show that $\theta _{\Delta }(x)$ is non-trivial and locally satisfiable. As $\varphi (x,b)$ is consistent, $t(b)$ has no common components with $t'(b)$ . The assumption that $(\sigma _i(b))_{i \in I}$ is indiscernible gives us that $t(\sigma _i(b))$ has no common components with $t'(\sigma _j (b))$ for all i and j in I. It follows that $\theta _{\Delta }(x)$ is non-trivial. For each p, let $\psi _p(x, z, z')$ be the associated p-condition of $\psi (x,z, z')$ . For all p, we have that $\psi _p(x, t(b), t(b'))$ defines a nonempty set and consequently by Lemma 4.1,

$$ \begin{align*}\bigwedge_{i \in \Delta}\psi_p\big(x, t(\sigma_i(b)), t'(\sigma_i(b))\big) \text{ defines a nonempty set in } \mathbb{G}.\end{align*} $$

We easily check that the above means $\theta _\Delta (x)$ is p-satisfiable for all p. Thus $\theta _{\Delta }(x)$ is locally satisfiable which completes our proof that $\text {Th}(\mathbb {Z}, \mathrm {SF}^{\mathbb {Z}})$ has U-rank $1$ .

We will next prove that $\text {Th}(\mathbb {Z}, \mathrm {SF}^{\mathbb {Z}})$ is k-independent for all $k>0$ ; see [Reference Chernikov, Palacin and Takeuchi5] for a definition of k-independence. The proof is almost the exact replica of the proof in [Reference Kaplan and Shelah9] except the necessary modifications taken in the current paragraph. Suppose $l>0$ , and S is an arbitrary subset of $\{ 0, \ldots , l-1\}$ . Our first step is to show that there are $a, d \in \mathbb {N}$ such that for $t \in \{0, \ldots , l-1\}$ ,

$$ \begin{align*}a +td \text{ is square-free }\ \text{ if and only if }\ t \text{ is in } S.\end{align*} $$

Let $n= |S|$ and $n' = l -n$ , and let $c \in \mathbb {Z}^n$ be the increasing listing of elements in S and $c' \in \mathbb {Z}^{n'}$ the increasing listing of elements in $\{0, \ldots , l-1\}\setminus S$ . Choose $d = (l!)^2$ . We need to find a such that

$$ \begin{align*}\bigwedge_{i=1}^n (a+ c_id \in \mathrm{SF}^{\mathbb{Z}}) \wedge \bigwedge_{i=1}^{n'} (a+ c^{\prime}_id \notin \mathrm{SF}^{\mathbb{Z}}).\end{align*} $$

For $p\leq l$ , if $a_p \notin p^2\mathbb {Z} = U_{p,2}^{\mathbb {Z}}$ , then $a_p + c_id \notin p^2\mathbb {Z}$ for all $i \in \{1, \ldots , n\}$ . For $p>l$ , it is easy to see that $ 0+ c_id \notin p^2\mathbb {Z}$ for all $i \in \{1, \ldots , n\}$ . The desired conclusion follows from the genericity of $(\mathbb {Z}; \mathscr {U}^{\mathbb {Z}}, \mathscr {P}^{\mathbb {Z}})$ .

Fix $k>0$ . We construct an explicit $L_{\mathrm {u}}$ -formula which witnesses the k-independence of $\text {Th}(\mathbb {Z}, \mathrm {SF}^{\mathbb {Z}})$ . Let $y =(y_0, \ldots , y_{k-1})$ and let $\varphi (x, y)$ be a quantifier-free $L^*_{\mathrm {u}}$ -formula such that for all $a \in \mathbb {Z}$ and $b \in \mathbb {Z}^k$ ,

$$ \begin{align*}\varphi(a, b) \ \text{ if and only if }\ a+ b_0+\cdots+b_{k-1} \in \mathrm{SF}^{\mathbb{Z}} \quad\text{ where } b =(b_0, \ldots, b_{k-1}).\end{align*} $$

We will show that for any given $n>0$ , there are families $(a_\Delta )_{ \Delta \subseteq \{ 0, \ldots , n-1\}^k}$ and $(b_{ij})_{0\leq i < k, 0 \leq j < n }$ of integers such that

$$ \begin{align*}\varphi(a_\Delta, b_{0,j_0}, \ldots, b_{k-1,j_{k-1}} ) \ \text{ if and only if }\ (j_0, \ldots, j_{k-1}) \in \Delta.\end{align*} $$

Let $f: \mathscr {P}(\{0,\ldots , n-1\}^k) \to \{0,\ldots , 2^{(n^k)}-1\}$ be an arbitrary bijection. Let g be the bijection from $\{ 0, \ldots , n-1\}^k$ to $\{ 0, \ldots , n^k-1\}$ such that if b and $b'$ are in $\{ 0, \ldots , n-1\}^k $ and $b<_{\text {lex}}b'$ , then $g(b)<g(b')$ . More explicitly, we have

$$ \begin{align*}g(j_0, \ldots, j_{k-1}) =j_0n^{k-1} + j_1n^{k-2} + \cdots + j_{k-1} \text{ for } (j_0, \ldots, j_{k-1}) \in \{ 0, \ldots, n-1\}^k.\end{align*} $$

It follows from the preceding paragraph that we can find an arithmetic progression $(c_i)_{ i \in \{0, \ldots , n^k 2^{(n^k)} -1 \} }$ such that for all $\Delta \subseteq \{0, \ldots , n-1\}^k$ and $(j_0, \ldots , j_{k-1})$ in $\{ 0, \ldots , n-1\}^k$ , we have that

$$ \begin{align*}c_{f(\Delta)n^k+ g(j_0, \ldots, j_{k-1})} \in \mathrm{SF}^{\mathbb{Z}}\ \text{ if and only if } \ (j_0, \ldots, j_{k-1}) \in \Delta.\end{align*} $$

Suppose $d = c_1-c_0$ . Set $b_{ij} = djn^{k-i-1} $ for $i \in \{0, \ldots , k-1\}$ and $j \in \{0, \ldots , n-1\}$ , and set $a_{\Delta } = c_{f(\Delta )n^k}$ for $\Delta \subseteq \{ 0, \ldots , n-1\}^k$ . We have

$$ \begin{align*}c_{f(\Delta)n^k+ g(j_0, \ldots, j_{k-1})} = c_{f(\Delta)n^k} + d g(j_0, \ldots, j_{k-1}) = a_\Delta + b_{0,j_0}+ \cdots+ b_{k-1,j_{k-1}}.\end{align*} $$

The conclusion thus follows.⊣