DISCRETE SETS DEFINABLE IN STRONG EXPANSIONS OF ORDERED ABELIAN GROUPS

Abstract

We study the structure of infinite discrete sets D definable in expansions of ordered Abelian groups whose theories are strong and definably complete, with a particular emphasis on the set $D'$ comprised of differences between successive elements. In particular, if the burden of the structure is at most n, then the result of applying the operation $D \mapsto D'\ n$ times must be a finite set (Theorem 1.1). In the case when the structure is densely ordered and has burden $2$, we show that any definable unary discrete set must be definable in some elementary extension of the structure $\langle \mathbb{R}; <, +, \mathbb{Z} \rangle $ (Theorem 1.3).

1. Introduction

In this article we will present new results on the structure of infinite discrete sets definable in ordered Abelian groups whose theories are strong with a special emphasis on the case when the structure has finite dp-rank. Suppose that $\mathcal {R} = \langle R; +, <, \ldots \rangle $ is a divisible ordered Abelian group (possibly with additional structure) and $D \subseteq R$ is a definable set which is discrete according to the order topology. Recall that by a result of [9], if the theory of $\mathcal {R}$ is dp-minimal (that is, of dp-rank $1$ ), then D must be finite, but there are examples of $\mathcal {R}$ of dp-rank $2$ in which an infinite discrete set is definable: for instance, $\langle \mathbb{R}; +, <, \mathbb{Z} \rangle $ , the expansion of the additive group of the reals by a predicate for the set of integers (see [3] for details). On the other hand, when the theory of $\mathcal {R}$ is strong (in particular, when it has finite dp-rank), then by general results from [3], D cannot have accumulation points, and furthermore there must exist a $\delta \in R$ such that for any $a \in D$ , we have $|(a-\delta , a + \delta ) \cap D|> 1$ (that is, the points in D cannot be “too spread out”).

The present article presents stronger results on definable discrete sets D when $\mathcal {R}$ has finite burden. The first set of results (in Section 2) concerns the “difference set” $D'$ of D. Assuming that $\mathcal {R}$ is definably complete (see Definition 1.4 just below), for every non-maximal $a \in D$ there is a next largest element $S_D(a)$ in D, and we define $D' = \{S_D(a) - a \, : \, a \in D \setminus \max (D)\}$ . By Fact 2.4 below, $D'$ is also a discrete definable set. We will show that when $\mathcal {R}$ has burden at most $2$ , then $D'$ is finite. More generally, we can iterate the operation of taking difference sets, letting $D^{(0)} = D$ and $D^{(k+1)} = (D^{(k)})'$ , and we show the following:

Theorem 1.1. Suppose that $\mathcal {R}$ is a definably complete ordered Abelian group, $D \subseteq R$ is definable and discrete, and $D^{(n)}$ is infinite. Then the burden of $\mathcal {R}$ is at least $n+1$ . If $\mathcal {R}$ is densely ordered, then the burden is greater than $n+1$ .

Question 1.2. Suppose that $\mathcal {R}$ is a definably complete ordered Abelian group of finite dp-rank. Are there only finitely many Archimedean classes represented in $D'$ ?

We conjecture that the answer to the Question above is “yes,” but we were not able to show this.

The second part of the article (Section 3) focuses on the fine structure of a discrete set $D \subseteq R$ definable in $\mathcal {R}$ under the stronger hypothesis that $\mathcal {R}$ has burden $2$ and is definably complete. We will show the following:

Theorem 1.3. Suppose that $\mathcal {R}=\langle R; +,<, \dots \rangle $ is a densely ordered Abelian group of burden $2$ which is definably complete and in which there is an infinite discrete subset of R definable. There is $G \subseteq R$ with $\langle R; +, <, G\rangle \equiv \langle \mathbb{R}; +, <, \mathbb {Z}\rangle $ so that any discrete $D \subseteq R$ definable in $\mathcal {R}$ is definable in $\langle R; +, <, G\rangle $ . Furthermore if $\mathcal {R}$ is of dp-rank $2$ then there is such a G so that any definable $X \subseteq R$ is definable in $\langle R; +, <, G\rangle $ .

Notice that this is very similar to a result from [3] which has an analogous conclusion in the case when the divisible ordered Abelian group is Archimedean but under the more general hypothesis that the theory is strong.

In addition to proving Theorem 1.3, we obtain a fairly precise description of discrete sets definable in $\mathcal {R}$ , showing that they are unions of finitely many points and “pseudo-arithmetic” sets (that is, sets E such that $|E'| = 1$ ). Note that this has a natural analogue for discrete sets definable in strong Archimedean ordered Abelian groups, which were shown to be finite unions of points and arithmetic progressions in [3], and in fact part of the proof strategy from that previous paper is adapted here to the non-Archimedean context.

In the remainder of this introduction we will briefly recall the definitions of the central concepts of the article (especially dp- and inp-rank, burden, and definable completeness). For a more thorough background on the various notions involved and their importance the reader is referred to the book of Simon [17]. This article continues the work begun in [3, 9, 16] and especially the recent note [4] in which the tame topological properties of sets definable in burden- $2$ ordered Abelian groups are studied.

1.1. Notations and convention

Most of our notation and terminology is standard for model theory, but for convenience we recall here some concepts which are not universally well-known, such as burden and dp-rank.

Structures will be named by calligraphic capital letters such as $\mathcal {R}$ and $\mathcal {U}$ , with block letters (like R and U) used to denote their underlying universes. For example, $\mathcal {R} = \langle R; +, <, \ldots \rangle $ denotes a structure $\mathcal {R}$ with universe R, a function symbol $+$ , a binary relation symbol $<$ , and possibly other basic predicates and functions.

We will work with ordered Abelian groups, or Abelian groups $\langle R; + \rangle $ endowed with a strict linear ordering $<$ which is invariant under the group operation ( $x < y$ implies that $x + z < y + z$ ). We abbreviate “ordered Abelian group” as OAG. Note that an OAG can be discretely ordered (having a least positive element, such as $\langle \mathbb{Z}; <, +\rangle $ ) or densely ordered (such as $\langle \mathbb{R}; <, + \rangle $ ). Recall that an Abelian group $\langle R; + \rangle $ is divisible if for every $g \in R$ and every positive integer n, there is an $h \in R$ such that $nh = g$ . Every divisible OAG is densely ordered, but there are densely ordered OAGs which are not divisible.

The ordering on an OAG $\langle R; <, + \rangle $ naturally defines an order topology on R whose basic open sets are open intervals, and by default any topological concepts (being open, closed, discrete, et cetera) refers to this order topology, or to the corresponding product topology on $R^n$ .

Throughout, we will use “definable” to mean “definable by some first-order formula, possibly using extra parameters.”

Whenever we talk about “intervals” in a densely ordered structure, by default we mean nonempty open intervals unless specified otherwise.

Definition 1.4. If $\mathcal {R} = \langle R; <, +, \ldots \rangle $ is an expansion of an OAG, then $\mathcal {R}$ is definably complete if every nonempty definable subset $X \subseteq R$ which has an upper bound in R has a least upper bound in R.

The following observation [13, Proposition 2.2] will sometimes be useful in what follows:

Fact 1.5. If $\mathcal {R}$ is an expansion of a densely ordered OAG which is definably complete, then $\mathcal {R}$ is divisible.

Finally, we recall the definitions of burden and dp-rank. These notions are originally due to Shelah [15], but the form of the definition which we give is due to Adler as outlined in [18]. In the definitions below, we work in some fixed complete first-order theory T. Our theories are always $1$ -sorted, since in $T^{eq}$ there will always be sorts of dp-rank greater than $1$ (assuming there are infinite models).

Definition 1.6. An inp-pattern of depth $\kappa $ is a sequence $\{ \varphi _i(\overline {x}; \overline {y}) \, : \, i < \kappa \}$ of formulas, a sequence $\{k_i \, : \, i < \kappa \}$ of positive integers, and a sequence $\{\overline {a}_{i,j} \, : \, i < \kappa , j < \omega \}$ of tuples from some model $\mathcal {M} \models T$ such that:

$\bullet $ for each $i < \kappa $ , the “i-th row”

(1) $$ \begin{align} \{\varphi_i(\overline{x}; \overline{a}_{i, j}) \, : \, j < \omega \} \end{align} $$

is $k_i$ -inconsistent; and

$\bullet $ for each function $\eta \, : \, \kappa \rightarrow \omega $ , the set of formulas

(2) $$ \begin{align} \{ \varphi_i(\overline{x}; \overline{a}_{i, \eta(i)}) \, : \, i < \kappa\} \end{align} $$

is consistent.

If $p(\overline {x})$ is a partial type, an inp-pattern as above is in $p(\overline {x})$ if every partial type as in (2) is consistent with $p(\overline {x})$ .

The partial type $p(\overline {x})$ has burden less than $\kappa $ if there is no inp-pattern of depth $\kappa $ in $p(\overline {x})$ . If the least $\kappa $ such that the burden of $p(\overline {x})$ is less than $\kappa $ is a successor cardinal, say $\kappa = \lambda ^+$ , then we say that the burden of $p(\overline {x})$ is $\lambda $ .

If the burden of the partial type $x=x$ (in a single free variable x) exists in the theory T and is equal to $\kappa $ then we say that the burden of T is $\kappa $ . The theory T is inp-minimal if its burden is $1$ .

The theory T is strong if every inp-pattern in T has finite depth.

Following Adler (see, [18]), the notion of dp-rank is usually defined in terms of arrays of formulas known as ict-patterns (or randomness patterns, in [14]) which are similar to the inp-patterns above. However, for the arguments in the present paper, we will not need to work with ict-patterns, preferring to use inp-patterns combined with the following fact:

Fact 1.7.

1. (1) (See [17, Observation 4.13]) The dp-rank of a theory T is less than $|T|^+$ if and only if T is NIP.

2. (2) (See [14, Lemma 2.11(iv)]) In case T is NIP, the dp-rank of any partial type in T is equal to its burden. In particular, T is dp-minimal (that is, of dp-rank $1$ ) if, and only if, T is both NIP and inp-minimal.

2. Difference sets for discrete sets in strong OAGs

In this section we provide a detailed analysis of discrete sets definable in a definably complete expansion of an ordered Abelian group whose theory is strong. The hypothesis of definable completeness is useful for defining a “successor function” on definable discrete sets (see the definition of $S_D$ below). The principal result of this section is Theorem 1.1 showing that if $\mathcal {R}$ has burden at most $n+1$ and D is a discrete set definable in $\mathcal {R}$ , then the n-fold difference set $D^{(n)}$ (as defined below) must be finite.

Note that for the case when $\mathcal {R}$ has burden $2$ , the conclusion of Theorem 1.1 is that if $D \subseteq R$ is definable and discrete, then $D'$ is finite. In a previous paper, we derived the same conclusion under the assumption that the universe of $\mathcal {R}$ is Archimedean and the complete theory of $\mathcal {R}$ is strong (see Corollary 2.29 of [3]). In the current paper, we generally work in $\omega $ -saturated models, so the results of [3] for Archimedean OAGs cannot be applied. The motivation of many of the lemmas here and in the following section was to generalize our earlier results to the non-Archimedean context, compensating with stronger assumptions on the theory (finite burden or burden $2$ ).

Assumption 2.1. Throughout the remainder of this section

$$\begin{align*}\mathcal{R} = \langle R; +, <, \ldots \rangle\end{align*}$$

denotes an expansion of an OAG which is definably complete, strong, and sufficiently saturated (generally $\omega $ -saturated will be enough), and $D \subseteq R$ is a definable set which is discrete. T denotes the complete first-order theory of $\mathcal {R}$ .

Remark 2.2. In this section, we do not generally assume that $\mathcal {R}$ is densely ordered, though in a couple of places (notably Theorem 1.1) we can achieve slightly stronger conclusions when $\mathcal {R}$ is not discrete. In case $\mathcal {R}$ is a discretely ordered group, a “discrete subset of R” will simply mean any subset of R, and thus many of our results apply generally to all unary definable sets of a discretely ordered Abelian group.

We first recall a couple of useful facts about families of discrete definable sets from [3].

Fact 2.3. [3, Corollary 2.13].

No definable discrete subset D of R can have an accumulation point. In particular, any definable discrete set $D \subseteq R$ is closed. As a consequence, the union of finitely many definable discrete sets is also closed and discrete.

Fact 2.4. [3, Corollary 2.17].

If $D \subseteq R$ is discrete and definable and $f: R^n \rightarrow R$ is any definable function, then the image set $f[D^n]$ is also discrete.

Next we set some basic definitions which will be used throughout the remainder of the paper: the successor function $S_D$ , $\mathbb {Z}$ -chains in a discrete set, and Archimedean equivalence.

Definition 2.5. Let D be a discrete set definable in $\mathcal {R}$ .

1. (1) If $a \in D$ is not maximal, set $S_D(a)=\min \{b \in D : a <b\}$ . ¹ For $n \in \mathbb {N}^{>0}$ we let $S_D^{n}$ be the n-th iterate of $S_D$ (when defined). Similarly if a is not minimal in D we let $S_D^{-1}(a)=\max \{b \in D : b<d\}$ and for $n \in \mathbb {N}^{>0}$ we let $S_D^{-n}$ be the n-th iterate (when defined). Finally let $S_D^{0}(a)=a$ for any $a \in D$ .

2. (2) If a is not maximal in D we let $\gamma _D(a)=S_D(a)-a$ , which we call the difference at a.

3. (3) $D'=\{\gamma _D(a) : a \in D \text { is not maximal}\}$ , the difference set of D.

4. (4) Note that $D'$ is the image of D under the definable map $a \mapsto \gamma _D(a)$ , so by Fact 2.4, the set $D'$ is also discrete. Hence we may define the n-th difference set $D^{(n)}$ by recursion on $n \in \mathbb{N} $ : $D^{(0)} = D$ , and $D^{(n+1)} = (D^{(n)})'$ .

Definition 2.6. Let D be a discrete definable set in $\mathcal {R}$ and let $a \in D$ . The $\mathbb {Z}$ -chain of a is the set:

$$\begin{align*}\mathcal{Z}(a)=\{S_D^{n}(a) : n \in \mathbb{Z} \text{ and } S_D^{n}(a) \text{ exists}\}.\end{align*}$$

Any subset of D of the form $\mathcal {Z}(a)$ for some $a \in D$ will be referred to as a $\mathbb {Z}$ -chain of D. We also write:

$$\begin{align*}\mathcal{Z}_{\geq}(a)=\{S_D^n(a): n \geq 0 \text{ and } S_D^n(a) \text{ exists}\}\end{align*}$$

and

$$\begin{align*}\mathcal{Z}_{\leq}(a)=\{S_D^n(a): n \leq 0 \text{ and } S_D^n(a) \text{ exists}\}.\end{align*}$$

Any subset of D of the form $\mathcal {Z}_{\geq }(a)$ is called an $\omega $ -chain of D, and any subset of the form $\mathcal {Z}_{\leq }(a)$ is called an $\omega ^*$ -chain of D.

Definition 2.7. For $a \in \mathcal {R}^{>0}$ the Archimedean class of a is the set:

$$\begin{align*}[a]=\{b \in R : b < na \text{ and } a<nb \text{ for some } n \in \mathbb{N}\}.\end{align*}$$

Note that the collection of Archimedean classes partitions $\mathcal {R}^{>0}$ . We write $a \ll b$ if $[a]<[b]$ and for sets $X,Y \subseteq \mathcal {R}^{>0}$ we write $X \ll Y$ if for all $x \in X$ and $y \in Y$ we have $x \ll y$ . Two elements a and b of R are called Archimedean equivalent if they belong to the same Archimedean class.

We record the following fact about definable families of discrete sets which we believe is interesting, even though it will not be necessary in proving our main results.

Proposition 2.8. Suppose that $D \subseteq R$ is discrete and definable and that $D_a$ is a uniformly definable family of discrete sets for $a \in D$ . Then $\bigcup _{a \in D}D_a$ is discrete.

Proof. We may assume that $\mathcal {R}$ is densely ordered as otherwise the statement is trivial.

For each $a \in D$ and $b\in D_a$ there is $\varepsilon>0$ so that $(b-\varepsilon , b+\varepsilon ) \cap D_a =\{b\}$ . For $b \in D_a$ let $f_a(b)=\sup \{\varepsilon>0 : (b-\varepsilon , b+\varepsilon ) \cap D_a = \{b\}\}$ (which exists in R by definable completeness). This yields a definable function $f_a: D_a \to R$ . Observe that $f_a[D_a]$ is discrete (by Fact 2.4), hence $f_a[D_a]$ is closed (Fact 2.3), and $f_a[D_a]>0$ . Hence for every $a \in D$ there is $\varepsilon>0$ so that $\varepsilon < f_a[D_a]$ . Define $g: D \to R$ by the rule

$$ \begin{align*}g(a)=\sup\{\varepsilon : \varepsilon<f_a[D_a]\}\end{align*} $$

(so by definable completeness, $g(a) = \min ( f_a[D_a])$ ). This is a definable function, so $g[D]$ is discrete (by Fact 2.4) and $g[D]>0$ . Pick $\varepsilon ^*>0$ so that $2\varepsilon ^*<g[D]$ . Thus for any $a \in D$ and any $b \in D_a$ we have that $(b-2\varepsilon ^*, b+2\varepsilon ^*) \cap D_a=\{b\}$ .

Now suppose that b is an accumulation point of $\bigcup _{a\in D}D_a$ . By our choice of $\varepsilon ^*$ , for any fixed $a \in D$ , there cannot be more than one point of $D_a$ in an open interval of length $2 \varepsilon ^*$ , so in particular there is at most one point of $D_a$ in $(b - \varepsilon ^*, b + \varepsilon ^*)$ . Thus we can define a function $h: D \to R$ such that $h(a)$ is the unique element of $D_a \cap (b-\varepsilon ^*,b+\varepsilon ^*)$ , if this exists, and otherwise $h(a) = b$ . Since h is a definable function, its image $h[D]$ is discrete by Fact 2.4 again. But b must be an accumulation point of $h[D]$ , contradicting Fact 2.3. Therefore $\bigcup _{a\in D}D_a$ is discrete.

Our next goal is to prove Theorem 2.14 below, which says that the existence of definable discrete sets $D_0, \ldots , D_n$ with certain properties implies the existence of an inp-pattern of depth $n+1$ ; our main result, Theorem 1.1, will follow rather quickly from this. Before proving Theorem 2.14, we will need the next definition below and a pair of technical lemmas (Lemmas 2.11 and 2.13) which will be useful in the eventual construction of an inp-pattern.

Definition 2.9. If $D_0, D_1, \ldots , D_n$ are subsets of R, then

$$ \begin{align*}D_0 + D_1 + \cdots + D_n = \{c_0 + c_1 + \cdots + c_n \, : \, \forall i \leq n \, \left[ c_i \in D_i \right] \}.\end{align*} $$

Lemma 2.10. If $D_0, \ldots , D_n$ are definable discrete sets, then $D_0 + \cdots + D_n$ is discrete.

Proof. This Lemma could be quickly deduced from Proposition 2.8 above, but it can also be proved directly, as follows. Let $D = D_0 \cup \cdots \cup D_n$ , which is discrete as it is a finite union of discrete sets. Fix some arbitrary point $b \in D_0 + \cdots + D_n$ and define $f \, : \, D^{n+1} \rightarrow R$ by the rule

$$ \begin{align*} f(c_0, \ldots, c_n) = \begin{cases} c_0 + \cdots + c_n, & \text{if}\ c_i \in D_i\ \text{for all}\ i, \\ b, & \text{otherwise}. \end{cases} \end{align*} $$

Then $D_0 + \cdots + D_n$ is the image of D under f, and hence by Fact 2.4 it is discrete.

Lemma 2.11. Suppose that $\widetilde {D}_0, \ldots , \widetilde {D}_n$ are definable infinite discrete sets such that:

1. (1) for every $i \in \{0, \ldots , n\}$ , the set $\widetilde {D}_i$ is bounded above, and $0 < \widetilde {D}_i$ ; and

2. (2) for every i such that $i \in \{0, \ldots , n-1\}$ ,

   $$ \begin{align*}\max(\widetilde{D}_{i+1}) + \min(\widetilde{D}^{\prime}_{i+1}) < \min(\widetilde{D}^{\prime}_i).\end{align*} $$

Then the ordering on $\widetilde {D}_0 + \cdots + \widetilde {D}_n$ as a subset of R is isomorphic to the lexicographic ordering on $\widetilde {D}_0 \times \cdots \times \widetilde {D}_n$ under the natural map sending the tuple $(c_0, \ldots , c_n) \in \widetilde {D}_0 \times \cdots \times \widetilde {D}_n$ to the sum $c_0 + \cdots + c_n.$

In particular, if $c_n$ is a non-maximal element of $\widetilde {D}_n$ , then

$$ \begin{align*}S_{\widetilde{D}_0 + \cdots + \widetilde{D}_n}(c_0 + \cdots + c_{n-1} + c_n) = c_0 + \cdots + c_{n-1} + S_{\widetilde{D}_n}(c_n).\end{align*} $$

Proof. First, we establish the following:

Claim 2.12. If $0 \leq i < n$ , $c_i \in \widetilde {D}_i$ , and $c_i \neq \max (\widetilde {D}_i)$ , then for any tuple $(c_{i+1}, c_{i+2}, \ldots , c_n) \in \widetilde {D}_{i+1} \times \widetilde {D}_{i+2} \times \cdots \times \widetilde {D}_n$ ,

$$ \begin{align*}\gamma_{\widetilde{D}_i}(c_i)> c_{i+1} + \cdots + c_n.\end{align*} $$

Proof of Claim 2.12.

Fix some $i \in \{0, \ldots , n-1\}$ and fix some $(c_i, \ldots , c_n) \in \widetilde {D}_i \times \cdots \times \widetilde {D}_n$ such that $c_i \neq \max (\widetilde {D}_i)$ . Then

$$ \begin{align*} \gamma_{\widetilde{D}_i}(c_i) \geq \min (\widetilde{D}_i') &> \max(\widetilde{D}_{i+1}) + \min(\widetilde{D}^{\prime}_{i+1}), \qquad\qquad\quad\qquad\! \text{by hypothesis (2)} \\& \geq c_{i+1} + \min(\widetilde{D}^{\prime}_{i+1}) \\& > c_{i+1} + \max(\widetilde{D}_{i+2}) + \min(\widetilde{D}^{\prime}_{i+2}), \qquad\qquad \text{by hypothesis (2)}\\& \geq c_{i+1} + c_{i+2} + \min(\widetilde{D}^{\prime}_{i+2}) \\& \vdots \\& \geq c_{i+1} + \cdots + c_{n-1} + \min(\widetilde{D}^{\prime}_{n-1}) \\& > c_{i+1} + \cdots + c_{n-1} + \max(\widetilde{D}_n) + \min(\widetilde{D}^{\prime}_n) \quad \text{by hypothesis (2)}\\&> c_{i+1} + \cdots + c_{n-1} + \max(\widetilde{D}_n)\\&\geq c_{i+1} + \cdots + c_{n-1} + c_n, \end{align*} $$

proving the Claim.

To prove Lemma 2.11, consider any two tuples $(c_0, \ldots , c_n)$ and $(d_0, \ldots , d_n)$ from $\widetilde {D}_0 \times \cdots \times \widetilde {D}_n$ , and we must show that

$$ \begin{align*}c_0 + \cdots + c_n < d_0 + \cdots + d_n\end{align*} $$

if and only if the tuple $(c_0, \ldots , c_n)$ comes before $(d_0, \ldots , d_n)$ in the lexicographic order. Without loss of generality, the tuples are distinct and $(c_0, \ldots , c_n)$ comes before $(d_0, \ldots , d_n)$ in the lexicographic order. Let $i \in \{0, \ldots , n\}$ be minimal such that $c_i \neq d_i$ , so that $c_i < d_i$ . We can further assume that $i < n$ , since if $i = n$ the conclusion we want is trivial. Note that

(3) $$ \begin{align} d_i \geq c_i + \gamma_{\widetilde{D}_i}(c_i). \end{align} $$

Hence

$$ \begin{align*} \sum_{j=0}^n (d_j - c_j) &= d_i - c_i + \sum_{j=i+1}^n (d_j - c_j),& \text{ by minimality of } i\\&\geq \gamma_{\widetilde{D}_i}(c_i) + \sum_{j=i+1}^n (d_j - c_j),& \text{ by (3)}\\&> \sum_{j=i+1}^n d_j,& \text{ by Claim }2.12\\&> 0,& \text{ by Hypothesis (1).} \end{align*} $$

Therefore $\sum _{j=0}^n c_j < \sum _{j=0}^n d_j$ , as we wanted.

Lemma 2.13. If there are definable infinite discrete sets $D_0, \ldots , D_n$ such that

(a) $0 < D_0$ , and

(b) for every i such that $0 \leq i < n$ ,

$$ \begin{align*}0 < D_{i+1} < D^{\prime}_i,\end{align*} $$

then there are definable infinite discrete sets $\widetilde {D}_0, \ldots , \widetilde {D}_n$ satisfying hypotheses (1) and (2) of Lemma 2.11.

Proof. Note that hypothesis (b) implies that $D_1, \ldots , D_n$ are all bounded above. In case $D_0$ is not bounded above, we may (using $\omega $ -saturation) replace it with an infinite subset which is bounded above, which will not affect hypothesis (b); so without loss of generality, every $D_i$ is bounded above.

Now for each $i \in \{1, \ldots , n\}$ , let $d_i$ be the largest element of $D_i$ , let $c_i$ be the second largest element of $D_i$ , and let $b_i$ be the third largest element of $D_i$ , and we define

$$\begin{align*}\widetilde{D}_i :=\begin{cases} (D_i \setminus \{c_i, d_i\}) \cup \{ d_i - c_i + b_i \}, & \text{ if } b_i < 2 c_i - d_i, \\ D_i \setminus \{d_i\}, & \text{ if } b_i \geq 2 c_i - d_i .\end{cases}\end{align*}$$

Finally, we let

$$ \begin{align*}\widetilde{D}_0 := D_0.\end{align*} $$

Note that when $b_i < 2 c_i - d_i$ , we have

$$ \begin{align*}d_i - c_i + b_i = c_i - (2 c_i - d_i - b_i) < c_i,\end{align*} $$

while if $b_i \geq 2 c_i - d_i$ , then $\max (\widetilde {D}_i) = c_i$ ; thus in either case, for any $i \in \{1, \ldots , n\}$ ,

(4) $$ \begin{align} \max(\widetilde{D}_i) \leq c_i. \end{align} $$

Also, since $b_i \in D_i> 0$ and $c_i < d_i$ , it follows that $d_i - c_i + b_i>0$ , and so in either case of the definition of $\widetilde {D}_i$ , we have

(5) $$ \begin{align} \widetilde{D}_i> 0. \end{align} $$

Next we will verify that for any $i \in \{0, \ldots , n\}$ ,

(6) $$ \begin{align} \widetilde{D}_i' \subseteq D^{\prime}_i. \end{align} $$

The relation (6) is trivial when $i = 0$ and immediate from the definition when $b_i \geq 2 c_i - d_i$ , so say $i> 0$ and $b_i < 2 c_i - d_i$ . Since

$$ \begin{align*}d_i - c_i + b_i = b_i + (d_i-c_i)> b_i,\end{align*} $$

it follows that $d_i - c_i + b_i$ is the largest element of $\widetilde {D}_i$ and $b_i$ is the second largest element of $\widetilde {D}_i$ . Hence

$$ \begin{align*} \widetilde{D}_i' &\subseteq D_i' \cup \{d_i - c_i + b_i - b_i \}\\ &= D_i' \cup \{d_i - c_i \}\\ &= D^{\prime}_i, \end{align*} $$

as desired.

Now from (6) we immediately deduce that for any $i \in \{0, \ldots , n\}$ ,

(7) $$ \begin{align} \min(D^{\prime}_i) \leq \min(\widetilde{D}^{\prime}_i). \end{align} $$

Finally, we will show that for any $i \in \{0, \ldots , n-1\}$ ,

(8) $$ \begin{align} \min(\widetilde{D}_{i+1}') \leq d_{i+1} - c_{i+1}. \end{align} $$

To prove (8), we divide into two cases depending on the definition of $\widetilde {D}_{i+1}$ . On the one hand, if $b_{i+1} < 2 c_{i+1} - d_{i+1}$ , then, as noted above, $b_{i+1}$ and $d_{i+1} - c_{i+1} + b_{i+1}$ are the two largest elements of $\widetilde {D}_{i+1}$ , so that

$$ \begin{align*} \gamma_{\widetilde{D}_{i+1}}(b_{i+1}) &= S_{\widetilde{D}_{i+1}}(b_{i+1}) - b_{i+1}\\ &= d_{i+1} - c_{i+1} + b_{i+1} - b_{i+1}\\ &= d_{i+1} - c_{i+1}, \end{align*} $$

so that

$$ \begin{align*}\min(\widetilde{D}_{i+1}') \leq \gamma_{\widetilde{D}_{i+1}}(b_{i+1}) = d_{i+1} - c_{i+1},\end{align*} $$

as desired.

On the other hand, suppose that $i \in \{0, \ldots , n-1\}$ and $b_{i+1} \geq 2 c_{i+1} - d_{i+1}$ . Then

$$ \begin{align*}\widetilde{D}_{i+1} = D_{i+1} \setminus \{d_{i+1}\},\end{align*} $$

so in particular $c_{i+1} - b_{i+1} \in \widetilde {D}_{i+1}'$ , and

$$ \begin{align*} \min(\widetilde{D}_{i+1}') &\leq c_{i+1} - b_{i+1}\\ &\leq c_{i+1} - (2 c_{i+1} - d_{i+1})\\ &= d_{i+1} - c_{i+1}, \end{align*} $$

and again we have the desired conclusion (8).

We will now check that hypotheses (1) and (2) of Lemma 2.11 hold for $\widetilde {D}_i$ . First, hypothesis (1) of Lemma 2.11 simply says that $\widetilde {D}_i$ is bounded above and $0 < \widetilde {D}_i$ for each $i \in \{0, \ldots , n\}$ , which is (5). As for hypothesis (2) of that Lemma, suppose $i \in \{0, \ldots , n-1\}$ . Hence

$$ \begin{align*} \max(\widetilde{D}_{i+1}) + \min(\widetilde{D}_{i+1}') &\leq c_{i+1} + \min(\widetilde{D}_{i+1}'), \, \, \, \, \text{by (4)}\\ &\leq c_{i+1} + (d_{i+1} - c_{i+1}), \, \, \, \, \text{by (8)}\\ &= d_{i+1}\\ &= \max(D_{i+1})\\ & < \min(D^{\prime}_i), \, \, \, \, \text{by hypothesis (b) of Lemma~2.13}\\ &\leq \min(\widetilde{D}^{\prime}_i), \, \, \, \, \text{by (7)}. \end{align*} $$

This shows that both hypotheses of Lemma 2.11 hold with the $\widetilde {D}_i$ in place of $D_i$ , as desired.

Theorem 2.14. If there are definable infinite discrete sets $D_0, \ldots , D_n$ such that

(a) $0 < D_0$ , and

(b) for every i such that $0 \leq i < n$ ,

$$ \begin{align*}0 < D_{i+1} < D^{\prime}_i,\end{align*} $$

then the burden of $\mathcal {R}$ is at least $n+1$ . If we additionally assume that $\mathcal {R}$ is densely ordered, then its burden is at least $n+2$ .

Proof. First, by Lemma 2.13, there are infinite definable discrete sets $\widetilde {D}_0, \ldots , \widetilde {D}_n$ satisfying the conclusions of Lemma 2.11. We will use the sets $\widetilde {D}_0, \ldots , \widetilde {D}_n$ to construct an inp-pattern of depth $n+1$ , and at the last step explain how the construction can be extended to add an extra row to the pattern in case $\mathcal {R}$ is densely ordered.

First we will describe the formulas $\varphi _i(x; \overline {y}_i)$ of Row i for each $i \in \{0, \ldots , n+1\}$ , and afterwards we will explain how to select parameters $\overline {a}_{i,j}$ so that the $\varphi _i(x;\overline {a}_{i,j})$ form an inp-pattern.

$\underline{\mathrm{Row}\,\, 0}$ : The formula $\varphi _0(x; \overline {y})$ for the first row (Row $0$ ) has variables x and ${\overline {y} = (y_0, y_1)}$ and is

$$ \begin{align*}\varphi_0(x; \overline{y}) = y_0 < x < y_1,\end{align*} $$

asserting that x lies in a certain open interval.

$\underline{\mathrm{Rows}\,\, 1\ \mathrm{through}\ n+1{:}}$ If $1 \leq i \leq n$ , the formula $\varphi _i(x; \overline {y})$ has variables x and $\overline {y} = (y_0, y_1)$ in addition to the parameters used to define the sets $\widetilde {D}_0, \ldots , \widetilde {D}_n$ (which we hold constant and never state explicitly). The formula for Row i is

$$ \begin{align*}\varphi_i(x; \overline{y}) = y_0 < \min \left\{ x - z \, : \, z \in \widetilde{D}_0 + \ldots + \widetilde{D}_{i-1} \text{ and } z < x \right\} < y_1,\end{align*} $$

observing that the minimum above exists for any value of x (by definable completeness) and is definable. Also note that this formula makes sense for i up to and including $n+1$ , although we will only use $\varphi _{n+1}(x;\overline {y})$ in our inp-pattern in the case when $\mathcal {R}$ is densely ordered.

Selecting the parameters: Finally, we will explain how to select parameters $\overline {a}_{i,j}$ for the formulas $\varphi _i(x;\overline {y})$ so that

$$ \begin{align*}\{\varphi_i(x; \overline{a}_{i,j}) \, : \, i < n+1, j < \omega\}\end{align*} $$

forms an inp-pattern (and in case $\mathcal {R}$ is densely ordered, we include $i = n+1$ ). We will assume without loss of generality that $\mathcal {R}$ is $\omega $ -saturated and we will select all $\overline {a}_{i,j}$ from R.

First we will pick the parameters for Rows $0$ through n, and at the end we will explain how to pick parameters for Row $n+1$ in case $\mathcal {R}$ is densely ordered.

Recall that for Rows $0$ through n to form an inp-pattern, it suffices to pick the parameters $\overline {a}_{i,j}$ such that:

1. (1) for every $i \in \{0, \ldots , n\}$ , the formulas $\{\varphi _i(x; \overline {a}_{i,j}) \, : \, j < \omega \}$ of Row i are $2$ -inconsistent; and

2. (2) for every function $\eta \, : \, \{0, \ldots , n\} \rightarrow \omega $ , the formula

   $$ \begin{align*}\varphi_0(x; \overline{a}_{0, \eta(0)}) \wedge \cdots \wedge \varphi_n(x; \overline{a}_{n, \eta(n)})\end{align*} $$
   is consistent.

Given that each set $\widetilde {D}_i$ is infinite and discrete, we can pick pairs $\overline {a}_{i,j} = (a^0_{i,j}, a^1_{i,j})$ such that the open intervals $I(a^0_{i,j}, a^1_{i,j})$ which they define are pairwise disjoint, and each such interval contains two consecutive elements of $\widetilde {D}_i$ . For definiteness, we fix elements $c_{i,j} \in \widetilde {D}_i$ for each $i \in \{0, \ldots , n\}$ and each $j < \omega $ such that

(9) $$ \begin{align} a^0_{i,j} < c_{i,j} < S_{\widetilde{D}_i}(c_{i,j}) < a^1_{i,j}. \end{align} $$

From the definition of the formulas $\varphi _i(x; \overline {y})$ and the fact that the intervals $I(a^0_{i,j}, a^1_{i,j})$ are pairwise disjoint condition (1) above is immediate.

To show (2), fix some $\eta \, : \, \{0, \ldots , n\} \rightarrow \omega $ , and we will show that

$$ \begin{align*}e := c_{0, \eta(0)} + \cdots + c_{n, \eta(n)}\end{align*} $$

satisfies the formula $\varphi _i(x; \overline {a}_{i, \eta (i)})$ for each $i \in \{0, \ldots , n\}$ .

In case $i = 0$ , note that by the conclusion of Claim 2.12,

$$ \begin{align*}\gamma_{\widetilde{D}_0}(c_{0, \eta(0)})> c_{1, \eta(1)} + \cdots + c_{n, \eta(n)}\end{align*} $$

so that

$$ \begin{align*}c_{0, \eta(0)} < c_{0, \eta(0)} + \cdots + c_{n, \eta(n)} < S_{\widetilde{D}_0}(c_{0, \eta(0)}).\end{align*} $$

By the inequality (9) and the definition of e, the element e is in the interval $I(a^0_{0, \eta (0)}, a^1_{0, \eta (0)})$ defined by $\varphi _0(x; \overline {a}_{0, \eta (0)}),$ as we wanted.

If $i \in \{1, \ldots , n\}$ , we argue similarly: by the conclusion of Claim 2.12 again,

$$ \begin{align*}\sum_{k=0}^{i-1} c_{k, \eta(k)} < e < \sum_{k=0}^{i-2} c_{k, \eta(k)} + S_{\widetilde{D}_{i-1}}(c_{i-1, \eta(i-1)}),\end{align*} $$

and thus, by Lemma 2.11, the greatest element of $\widetilde {D}_0 + \cdots + \widetilde {D}_{i-1}$ below e is $\sum _{k=0}^{i-1} c_{k, \eta (k)}$ ; therefore,

(10) $$ \begin{align} \min \left\{ e - z \, : \, z \in \widetilde{D}_0 + \cdots + \widetilde{D}_{i-1} \text{ and } z < e \right\} = c_{i, \eta(i)} + \cdots + c_{n, \eta(n)}. \end{align} $$

If $i = n$ , then this reduces to

$$ \begin{align*}\min \left\{ e - z \, : \, z \in \widetilde{D}_0 + \cdots + \widetilde{D}_{n-1} \text{ and } z < e \right\} = c_{n, \eta(n)},\end{align*} $$

and by (9) we have

$$ \begin{align*}a^0_{n, \eta(n)} < \min \left\{ e - z \, : \, z \in \widetilde{D}_0 + \cdots + \widetilde{D}_{n-1} \text{ and } z < e \right\} < a^1_{n, \eta(n)}\end{align*} $$

so that e satisfies $\varphi _n(x; \overline {a}_{n, \eta (n)})$ as desired.

If $i \in \{1, \ldots , n-1\}$ , then once again by Claim 2.12,

$$ \begin{align*}\gamma_{\widetilde{D}_i}(c_{i, \eta(i)})> c_{i+1, \eta(i+1)} + \cdots + c_{n, \eta(n)}\end{align*} $$

so that

$$ \begin{align*}c_{i, \eta(i)} < c_{i, \eta(i)} + c_{i+1, \eta(i+1)} + \cdots + c_{n, \eta(n)} < S_{\widetilde{D}_i}(c_{i, \eta(i)}).\end{align*} $$

By Equation (10), this implies that

$$ \begin{align*}c_{i, \eta(i)} < \min \left\{ e - z \, : \, z \in \widetilde{D}_0 + \cdots + \widetilde{D}_{i-1} \text{ and } z < e \right\} < S_{\widetilde{D}_i}(c_{i, \eta(i)}).\end{align*} $$

By the inequalities in (9), we again deduce that e satisfies $\varphi _i(x; \overline {a}_{i, \eta (i)})$ .

Finally, suppose that $\mathcal {R}$ is densely ordered. Then by $\omega $ -saturation, we can pick parameters $\overline {a}_{n+1,j} = (a^0_{n+1,j}, a^1_{n+1,j})$ from R such that for every $j \in \omega $ ,

$$ \begin{align*}0 < a^0_{n+1,j} < a^1_{n+1,j} < a^0_{n+1,j+1} < a^1_{n+1,j+1} < \min (\widetilde{D}^{\prime}_n).\end{align*} $$

By density of $\mathcal {R}$ , we can pick elements $c_{n+1, j} \in I(a^0_{n+1,j}, a^1_{n+1,j})$ . Now if $\eta \, : \, \{0, \ldots , n+1\} \rightarrow \omega $ is any function, let

$$ \begin{align*}e = c_{0, \eta(0)} + \cdots + c_{n+1, \eta(n+1)}.\end{align*} $$

Arguing just as before, we have that e satisfies $\varphi _i(x; \overline {a}_{i, \eta (i)})$ for every $i \in \{0, \ldots , n+1\}$ , and we are done.

At last, we can prove Theorem 1.1.

Proof of Theorem 1.1.

Let D be an infinite definable discrete set such that $D^{(n)}$ is infinite, and we must show that the burden of $\mathcal {R}$ is at least $n+1$ (or at least $n+2$ , in case $\mathcal {R}$ is densely ordered). By passing to an elementary extension as needed, we assume $\mathcal {R}$ is $\omega $ -saturated.

First we note:

Claim 2.15. There is a definable discrete set $\widetilde {D} \subseteq R$ such that $0 < \widetilde {D}$ and $\widetilde {D}^{(n)}$ is infinite.

Proof. If $n = 0$ , there is some a such that $(D + a) \cap (0, \infty )$ is infinite, ² and we can take $\widetilde {D} = (D + a) \cap (0, \infty )$ . If $n \geq 1$ , first take some bounded interval $(b,c)$ such that $(D \cap (b,c))^{(n)}$ is infinite; then, noting that for any $a \in R$ ,

$$ \begin{align*}(a + D \cap (b,c))^{(n)} = (D \cap (b,c))^{(n)},\end{align*} $$

we may let $\widetilde {D}$ be a translation of $(D \cap (b,c))^{(n)}$ such that $\widetilde {D}> 0$ .

To prove Theorem 1.1, by Theorem 2.14, it is sufficient to construct a new sequence of infinite discrete sets $E_0, \dots , E_n$ such that

1. (1) $0 < E_0$ , and

2. (2) for every $i \in \{0, \ldots , n-1\}$ ,

   $$ \begin{align*}0 < E_{i+1} < E^{\prime}_i.\end{align*} $$

To this end, we will build an $(n+1) \times (n+1)$ matrix of infinite discrete sets $\{E_{i,j} \, : \, 0 \leq i, j \leq n\}$ such that:

1. (3) $E_{0,j} = \widetilde {D}^{(j)}$ for each $j \in \{0, \ldots , n\}$ .

2. (4) $E_{i,j} \subseteq E_{i-1,j}$ for all $0 \leq j \leq n$ and all $1 \leq i \leq n$ .

3. (5) If $0 \leq i \leq n$ then $0 < E_{i,j}<E_{i,j-1}'$ for all $n-i +1\leq j \leq n$ .

4. (6) If $0 \leq i \leq n$ and $j < n - i$ , then $E_{i, j} = \widetilde {D}^{(j)}$ .

The sets $E_{i,j}$ will be defined recursively, starting with the first row (when $i = 0$ ). For $i=0$ , we simply observe that each set $E_{0,j} = \widetilde {D}^{(j)}$ is discrete by Fact 2.4, and (4)–(6) are trivial.

Now suppose we have constructed $E_{i,0}, \dots , E_{i,n}$ satisfying (3)–(6), and we show how to define $E_{i+1, 0}, \ldots , E_{i+1,n} $ . We will define the sets $E_{i+1, j}$ by four different cases according to how j relates to $n-i$ .

In the first case, when $j \geq n-i+1$ , we set $E_{i+1,j}=E_{i,j}$ .

For the second case, we must define $E_{i+1, j}$ when $j = n-i$ . As $E_{i,n-i}$ is an infinite discrete set, by $\omega $ -saturation of $\mathcal {R}$ there is a $c \in R$ so that both sets

$$ \begin{align*}F_0=\{x \in E_{i,n-i}: x<c\}\end{align*} $$

and

$$ \begin{align*}F_1=\{x \in E_{i,n-i} :x>c\}\end{align*} $$

are infinite. Let

$$ \begin{align*}E_{i+1,n-i}=F_0\end{align*} $$

and note that, in case $i> 0$ , we have $E_{i+1,n-i+1}<E_{i+1,n-i}'$ by (5) for $j = n - i + 1$ .

For the third case, when $j = n-i-1$ , we set

$$ \begin{align*}E_{i+1, n-i-1}=\{x \in \widetilde{D}^{(n-i-1)} : \gamma_{\widetilde{D}^{(n-i-1)}}(x) \in F_1\}.\end{align*} $$

This is an infinite discrete subset of $\widetilde {D}^{(n-i-1)} = E_{i, n-i-1}$ since $F_1 \subseteq E_{i,n-i} \subseteq \widetilde {D}^{(n-i)}$ , and if $a \in E_{i+1, n-i-1}$ , then $\gamma _{E_{i+1,n-i-1}}(a)>c$ and hence $E_{i+1, n- i-1}'>E_{i+1, n-i}$ .

Finally, for $j<n-i-1$ , we define $E_{i+1,j}=E_{i,j} = \widetilde {D}^{(j)}$ .

Now letting $E_j = E_{n,j}$ , we have a sequence of sets satisfying (1) and (2) above, and we are done.

3. Fine structure for discrete sets in the burden $2$ case

In this section, we will prove Theorem 1.3.

Throughout this section $\mathcal {R}$ will be an expansion of a divisible ordered Abelian group of burden $2$ which is definably complete and presented in a language $\mathcal {L}$ , and D will always be an infinite discrete set definable in such a structure. Recall that by Theorem 1.1 if $E \subset R$ is any $\mathcal {R}$ -definable discrete set (in particular D) then $E'$ is finite.

Theorem 1.3 will follow from a result that such a D must be a finite union of sets which locally resemble arithmetic sequences. To make this more precise, we give the following definition.

Definition 3.1. A discrete set E is called pseudo-arithmetic if it is infinite and $|E'|=1$ . If $E'=\{\eta \}$ we will call E $\eta $ -pseudo-arithmetic. A definable set X is called piecewise pseudo-arithmetic if it is a finite union of points and definable pseudo-arithmetic sets.

The bulk of this section is dedicated to proving:

Theorem 3.2. If $\mathcal {R}=\langle R; +, <, \dots \rangle $ is a definably complete expansion of a divisible ordered Abelian group of burden 2 and $D \subseteq R$ is definable and discrete then D is piecewise pseudo-arithmetic.

In order to establish Theorem 3.2 we first prove a weaker result with more assumptions on the discrete set D and then later show how the general result can be deduced from this weaker version. In order to state our desired weakening of Theorem 3.2 we need a definition.

Definition 3.3. D is narrow if any two elements of $D'$ are Archimedean equivalent.

We may now state our weaker version of Theorem 3.2.

Proposition 3.4. If $\mathcal {R}=\langle R; +, <, \dots \rangle $ is an $\omega $ -saturated, definably complete expansion of a divisible ordered Abelian group of burden 2 and D is definable, discrete, narrow, and bounded below, then D is piecewise pseudo-arithmetic.

We begin by proving Proposition 3.4. Then in turn we show how we may reduce Theorem 3.2 to this weaker proposition. Once we have established Theorem 3.2 we then show how our main result,Theorem 1.3, follows. We finish the section with an example showing the limits of Theorem 1.3.

Before we continue we note that in order to establish Theorem 3.2 we may assume that the structure $\mathcal {R}$ is $\omega $ -saturated.

Proposition 3.5. For any infinite cardinal $\kappa $ , to prove Proposition 3.2 in general, it is sufficient to prove it under the assumption that the structure $\mathcal {R}$ is $\kappa $ -saturated.

Proof. Suppose that $\mathcal {R}=\langle R; +, <, \dots \rangle $ is any definably complete expansion of a divisible ordered Abelian group (not necessarily $\kappa $ -saturated) of burden 2 and D is an infinite definable discrete set. Let $\mathcal {R}_1$ be a $\kappa $ -saturated elementary extension of $\mathcal {R}$ , and let $D_1 \subseteq R_1$ be the subset definable by the same formula that defines D in R. Then $D_1$ is also discrete. Applying Proposition 3.2 for $\kappa $ -saturated structures, we conclude that $D_1$ is piecewise pseudo-arithmetic. Thus we find formulas $\varphi _1(x, \overline {a}_1), \dots , \varphi _m(x, \overline {a}_m)$ and elements $b_1, \dots , b_l \in R_1$ so that $D=E_1 \cup \cdots \cup E_m \cup \{b_1, \dots , b_l\}$ where each $E_i$ is a pseudo-arithmetic set defined by $\varphi _i(x, \overline {a}_i)$ . But then we can find $\overline {a}_1^*, \dots \overline {a}_m^* \in R$ and $c_1, \dots c_l \in R$ so that $D=E_1^*\cup \dots \cup E_m^* \cup \{c_1, \dots , c_l\}$ where each $E_i^*$ is a discrete subset of R defined by $\varphi _i(x, \overline {a}_i^*)$ with $|(E_i^*)'|=1$ . Not all of the $E_i^*$ are necessarily pseudo-arithmetic as some may be finite, but nonetheless we have written D as union of finitely many points and pseudo-arithmetic sets as desired.

Note that Proposition 3.4 is only an intermediate step in establishing Theorem 3.2, and thus we include the hypothesis that $\mathcal {R}$ is $\omega $ -saturated in the statement of Proposition 3.4.

Finally the following definition will occur throughout the following sections:

Definition 3.6. We will say that $X \subseteq D$ is D-convex if whenever $a,b \in D \cap X$ and $a<c<b$ for some $c \in D$ then $c \in X$ .

3.1. Establishing Proposition 3.4

In this subsection we prove Proposition 3.4. Thus in this subsection we will maintain:

Assumption 3.7. D is a definable discrete set which is narrow and bounded below, and $\mathcal {R}$ is $\omega $ -saturated.

In order to prove Proposition 3.4 we first need to establish a sequence of preliminary results. The first of these is a statement describing definable subsets of D.

Proposition 3.8. Let $E \subseteq D$ be definable. Then there are $M \in \mathbb {N}$ and finitely many closed intervals or closed rays $C_1, \dots , C_n$ in R such that:

1. (1) $E\subseteq (C_1 \cap D) \cup \dots \cup (C_n \cap D)$ .

2. (2) The $C_i$ are pairwise disjoint.

3. (3) If $C_i = [b,b] = \{b\}$ , then $b \in E$ .

4. (4) If $C_i$ is an infinite closed interval, then $C_i \cap E$ is infinite.

5. (5) If $C_i$ is an infinite interval and $C_i$ is bounded above, then $C_i$ is of the form $[a_i, b_i]$ with $b_i \in E$ and $a_i \in E$ , and otherwise it is of the form $[a_i, \infty )$ with $a_i \in E$ .

6. (6) If $C_i$ is an infinite interval and Z is a $\mathbb {Z}$ -chain with $Z \subseteq C_i$ then E is both cofinal and coinitial in Z, and moreover for all $b \in Z$ , $\{b, S_D(b), \dots ,S_D^M(b)\} \cap E \not = \emptyset $ .

7. (7) If $C_i$ is an infinite interval of the form $[a_i,b_i]$ or $[a_i, \infty )$ then E is cofinal in $\mathcal {Z}(a_i)$ , and moreover for all $b \in \mathcal {Z}(a_i)$ with $b \geq a_i$ ,

   $$\begin{align*}\{b, S_D(b), \dots, S_D^M(b)\} \cap E \not= \emptyset.\end{align*}$$

8. (8) If $C_i$ is an infinite interval of the form $[a_i, b_i]$ then E is coinitial in $\mathcal {Z}(b_i)$ , and moreover for all $a \in \mathcal {Z}(b_i)$ with $a \leq b_i$ ,

   $$\begin{align*}\{a, S_D^{-1}(a), \dots, S_D^{-M}(a)\} \cap E \not= \emptyset.\end{align*}$$

We begin with an essential lemma and some useful corollaries.

Lemma 3.9. Suppose that $\{D_a: a \in X\}$ is a definable family of subsets of D and $\delta = \max (D')$ . Then there is an $l \in \omega $ such that for any $a \in X$ , the set $\{d \in D_a \, : \, \gamma _{D_a}(d) \geq l \cdot \delta \}$ is finite.

Proof. Suppose that no such l exists. Then by compactness we find $a \in X$ such that there are infinitely many $d \in D_a$ with $\gamma _{D_a}(d) \gg \delta $ . Let $\{d_i \, : \, i \in \omega \}$ list the first $\omega $ elements of D. By $\omega $ -saturation of $\mathcal {R}$ , there is an element $\varepsilon \in R$ such that

1. (1) for every $i \in \omega $ , $d_i < \varepsilon $ ; and

2. (2) there are infinitely many $d \in D_a$ such that $\gamma _{D_a}(d)> \varepsilon $ .

Let $F=\{x \in D_a : \gamma _{D_a}(x)\geq \varepsilon \}$ and notice that $F' \geq \varepsilon $ . Thus F and $D \cap [0, \varepsilon )$ are infinite discrete sets such that $D \cap [0,\varepsilon ]<F'$ , violating Theorem 2.14.

If $E \subseteq D$ is definable, then we can apply Lemma 3.9 to the family of sets $D_a = E$ to immediately deduce the following:

Corollary 3.10. If $E \subseteq D$ is definable and $\delta = \max (D')$ , then there can be only finitely many $b \in E$ with $\gamma _E(b) \gg \delta $ .

Let $\equiv $ be the convex equivalence relation on D so that $a \equiv b$ for $a, b \in D$ if and only if $|a-b|<l \cdot \max {(D')}$ for some $l \in \omega $ . Notice as D is narrow we also have $a \equiv b$ if and only if $|a-b|<l \cdot \min {(D')}$ for some $l \in \omega $ . Or to state things more simply, $a \equiv b$ if and only if a and b lie on the same $\mathbb {Z}$ -chain of D. By saturation is a dense linear ordering.

Corollary 3.11. If $E \subseteq D$ is definable then has finitely many convex components in .

Proof. Suppose otherwise and let $C_i$ for $i \in \omega $ be distinct convex components of in . As $\mathcal {R}$ is assumed to be $\omega $ -saturated we may assume by compactness that $C_i<C_{i+1}$ for all $i \in \omega $ . We may find $a_i \in D \setminus E$ for $i \in \omega $ so that and so that $a_i \not \equiv e$ for any $e \in E$ .

Now let $b_i =\max \{e \in E : e<a_i\}$ for $i \in \omega $ . As and $\mathcal {R}$ is definably complete, $b_i$ exists; and as E is closed (by Fact 2.3), $b_i \in E$ . Note that $b_i$ is not maximal in E for any $i \in \omega $ as . We claim that $\gamma _E(b_i)>l \cdot \max {(D')}$ for all $i, l \in \omega $ . Suppose otherwise and that $\gamma _E(b_i) \leq l \cdot \max {(D)}$ for some $i,l \in \omega $ . But by choice of $b_i$ we must have that $S_E(b_i)>a_i$ . Hence $|a_i-b_i| \leq l \cdot \max {(D')}$ and so $a_i \equiv b_i$ but this violates our choice of $a_i$ . Thus for all $i, l \in \omega $ we have that $\gamma _E(b_i)>l \cdot \max {(D')}$ . But this violates Corollary 3.10.

Corollary 3.12. Let $E \subseteq D$ be definable. Then there is $M_0(E) \in \omega $ so that:

1. (1) If E is cofinal in a $\mathbb {Z}$ -chain Z then

   $$\begin{align*}\{b, S_D(b), \dots, S_D^{M_0(E)}(b)\} \cap E \not=\emptyset\end{align*}$$
   for all sufficiently large $b \in Z$ .

2. (2) If E is coinitial in a $\mathbb{Z} $ -chain Z then

   $$\begin{align*}\{b, S_D(b), \dots, S_D^{-M_0(E)}(b)\} \cap E \not=\emptyset\end{align*}$$
   for all sufficiently small $b \in Z$ .

3. (3) If E is both cofinal and coinitial in a $\mathbb{Z} $ -chain Z then

   $$\begin{align*}\{b, S_D(b), \dots, S_D^{M_0(E)}(b)\} \cap E \not=\emptyset\end{align*}$$
   for all $b \in Z$ .

Proof. First suppose that (1) fails. Let $N \in \omega $ . For $i \in \omega $ we may find $a_i \in D$ all lying on a single $\mathbb {Z}$ -chain so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

and $b_i \in E$ with $a_i<b_i<a_{i+1}$ for all $i \in \omega $ .

Then by compactness we find $a_i^* \in D$ for $i \in \omega $ so that $\{S^M_D(a_i^*) : M \in \mathbb {Z}\} \cap E = \emptyset $ and $b_i^* \in E$ so that $a_i^*<b_i^*<a_{i+1}^*$ . For each $i \in \omega $ we have that $|a_i^*-c|>l \cdot \min {(D')}$ for all $l \in \omega $ and any $c \in E$ . As D is narrow $a_i^* \not \equiv c$ for any $c \in E$ . Thus and furthermore but for all $i \in \omega $ . In particular each is in a distinct convex component of in violating Corollary 3.11

The proof of (2) is identical to that of (1) except that for each $N \in \omega $ we find $c_i \in E$ and $a_i \in D$ for $i \in \omega $ so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

with $a_i>c_i>a_{i+1}$ .

Now assume that (3) fails. As (1) and (2) hold, for each $N \in \omega $ we can find pairwise distinct $\mathbb {Z}$ -chains $Z_i$ of D and $ a_i \in Z_i$ for $i \in \omega $ so that

$$\begin{align*}\{S_D^{-N}(a_i), \dots, S^{-1}_D(a_i), a_i, S_D(a_i), \dots, S^N_D(a_i)\}\cap E = \emptyset\end{align*}$$

together with $b_i, c_i \in E \cap Z_i$ so that $c_i<a_i<b_i$ . We can assume that either the $Z_i$ are ordered so that $Z_i<Z_{i+1}$ for all $i \in \omega $ or that $Z_i>Z_{i+1}$ for all $i \in \omega $ . In the case that $Z_i<Z_{i+1}$ argue with $a_i, b_i$ exactly as in the proof of (1). In the case that $Z_i>Z_{i+1}$ argue with $a_i, c_i$ exactly as in the proof of (2).

We may now prove Proposition 3.8. Recall that we always assume that D is bounded below, thus any interval or ray $C_i$ occurring in the statement of Proposition 3.8 may be assumed to be bounded below.

Proof. For the purposes of this proof let us call a definable $E \subseteq D$ neat if we may find $M \in \mathbb {N}$ and $C_1, \dots , C_n$ closed intervals or rays satisfying conditions (1)–(8) of Proposition 3.8.

Notice that for clauses (6)–(8) in the statement of Proposition 3.8 the “moreover” portion will follow from the initial statements and Corollary 3.12. Hence to establish that a set is neat we need only produce the intervals or rays $C_1, \dots , C_n$ witnessing (1)–(8) in the definition of neat without the “moreover” clauses.

It is immediate that if $E=E_1 \cup \dots \cup E_l$ where the $E_i$ are definable, pairwise disjoint, and neat then E is neat.

Let $E \subseteq D$ be definable. By Corollary 3.11, has finitely many convex components. Let $H_j$ for $1 \leq j \leq k$ be the convex components of . We may pick $e_j,f_j \in D \cup \{\infty \}$ so that . Setting $E_j=[e_j,f_j) \cap E$ , to establish that E is neat it suffices to show that each $E_j$ is neat.

Thus fix $1 \leq j \leq k$ . If $E_j$ is finite then the result is immediate, hence we may assume that $E_j$ is infinite. Let $a =\min (E_j)$ , which exists as $E_j$ is bounded below. If $E_j$ is bounded above let $b=\max (E_j)$ . Let Z be any $\mathbb {Z}$ -chain so that $E_j \cap Z\not =\emptyset $ and $\mathcal {Z}(a)<Z<\mathcal {Z}(b)$ (if b exists). We claim that $E_j$ must be both cofinal and coinitial in Z. Suppose otherwise, then for any $N \in \omega $ we can find $c \in Z$ so that $\{S^{l}_D(c) : -N \leq l \leq N\} \cap E_j =\emptyset $ . By compactness we can then find another $\mathbb {Z}$ -chain $Z_0$ so that $\mathcal {Z}(a)<Z_0<\mathcal {Z}(b)$ (if b exists) and $Z_0 \cap E_j= \emptyset $ . But this violates the fact that is convex in . Hence $E_j$ is cofinal and coinitial in Z. Similarly we can conclude that $E_j$ is cofinal in $\mathcal {Z}(a)$ and coinitial in $\mathcal {Z}(b)$ (if b exists). Thus $C_1=[a,b]$ if b exists, or $C_1=[a, \infty )$ otherwise is a closed interval or ray witnessing that $E_j$ is neat.

To continue our proof of Proposition 3.4 we proceed with a combinatorial analysis of $\mathbb{Z} $ -chains in D much like that in [3] to establish that $\mathbb{Z} $ -chains in D are approximately periodic. To make this precise we need a definition.

Definition 3.13. Suppose that $\tau $ is an infinite sequence $\{a_i \, : \, i \in I\}$ of elements from the set $D'$ where the index set I is either $\mathbb{Z} $ , $\omega $ , or $\omega ^*$ (that is, $\omega $ with the reverse ordering). In case $I = \omega ^*$ , we use $i+k$ to denote the k-th successor of i if such an element exists, thus whenever we write $i+k$ we are presuming the k-th successor of i exists.

1. (1) The sequence $\tau $ is m-periodic if whenever i and $i+m$ belong to I, we have $a_{i+m} = a_i$ .

2. (2) If $I = \omega $ , the sequence $\tau $ is eventually m-periodic if there is some $N \in I$ such that for every $k \geq N$ , we have $a_{k+m} = a_k$ .

3. (3) If $I = \omega ^*$ , the $\tau $ is eventually m-periodic if there is some $N \in \omega ^*$ such that for every $k \leq N$ , we have $a_{k+m} = a_k$ .

4. (4) If $I = \mathbb{Z} $ , the sequence $\tau $ is eventually m-periodic if both of the subsequences $\{a_i \, : \, i \geq 0\}$ and $\{a_i \, : \, i \leq 0\}$ are eventually m-periodic, according to (2) and (3) above.

5. (5) If $I = \omega $ or $\omega ^*$ and $\sigma \in (D')^m$ , the sequence $\tau $ is $\sigma $ -periodic if it is m-periodic and the first m elements of $\tau $ (or the last m elements, in case $I = \omega ^*$ ) are a cyclic permutation of $\sigma $ . The notion of eventually $\sigma $ -periodic are defined analogously.

6. (6) The sequence $\tau $ is (eventually) periodic if it is (eventually) m-periodic for some $m \in \omega \setminus \{0\}$ .

7. (7) A $\mathbb {Z}$ -chain Z from D is (eventually) m-periodic if for some $a \in Z$ , the corresponding sequence of elements $\langle \gamma _D^i(a) \, : \, i \in \mathbb{Z} \rangle $ is (eventually) m-periodic. Similarly for subsets of D of the form $\mathcal {Z}_{\geq }(b)$ or $\mathcal {Z}_{\leq }(b)$ .

For the next Proposition and its consequences the following definition is convenient.

Definition 3.14. If E is an infinite definable discrete set and $\{\sigma _1, \dots , \sigma _k\}$ is a finite set of finite sequences from $E'$ we call $\{\sigma _1, \dots , \sigma _k\}$ a characteristic set for E if every $\omega $ -chain of E and every $\omega ^*$ -chain of E is eventually $\sigma _i$ -periodic for some $1 \leq i \leq k$ .

Our next goal is to show:

Proposition 3.15. D has a characteristic set.

In order to establish Proposition 3.15 we need some preliminary definitions and lemmas.

Definition 3.16. For $a, b, c, d \in D$ such that $a<b$ and $c < d$ , we define $(a,b) \sim (c,d)$ if and only if $b-a=d-c$ and for all e in the interval $(a,b)$ we have that $e \in D$ if and only if $e+c-a \in D$ . For any pair $(a,b) \in D^2$ such that $a<b$ , let $P_{(a,b)}=\{c \in D : (a,b) \sim (c, c+(b-a))\}$ .

Roughly speaking $(a,b) \sim (c,d)$ if these two intervals are “isomorphic” as far as D is concerned.

Definition 3.17. For a finite sequence $\sigma =\langle c_1, \dots , c_m\rangle $ of elements from $D'$ , let $P_{\sigma }$ be the set of all $d \in D$ so that $S^l(d)-S^{l-1}(d)=c_l$ for all $ l \in \{1, \ldots , m\}$ .

Notice that if ${\sigma }$ is any finite sequence from $D'$ with $P_{{\sigma }}$ non-empty then $P_{{\sigma }}$ is equal to $P_{(a,b)}$ for some $a, b \in D$ . In particular the family of all $P_{{\sigma }}$ is part of a uniformly definable family of subsets of D.

Lemma 3.18. There is some fixed $m_0 \in \omega $ such that for any $\omega $ -chain C in D and any $k \in \omega $ , there are at most $m_0$ sequences ${\sigma }$ of length k so that $P_{{\sigma }}$ is not bounded above in C. Similarly, there is a fixed $m_1 \in \omega $ such that for every $\omega ^*$ -chain C in D and any $k \in \omega $ , there are at most $m_1$ sequences ${\sigma }$ of length k so that $P_{{\sigma }}$ is not bounded below in C.

Proof. Say $D' = \{\delta _1, \ldots , \delta _n\}$ where the $\delta _i$ are listed in increasing order. First we will give the proof of the existence of $m_0$ . By Lemma 3.9, there is some $l_0 \in \omega $ such that for any $a, b \in D$ , there are only finitely many $c \in P_{(a,b)}$ with $\gamma _{P_{(a,b)}}(c)\geq l_0 \cdot \delta _n$ . Since $\delta _1$ is Archimedean equivalent to $\delta _n$ , there is some $l \in \omega $ such that $l \cdot \delta _1 \geq l_0 \cdot \delta _n$ , and hence:

$(*)$ For any $a, b \in D$ , there are only finitely many $c \in P_{(a,b)}$ with $\gamma _{P_{(a,b)}}(c)\geq l \cdot \delta _1$ .

We claim that $m_0 = l$ works. Fix an $\omega $ -chain C and a natural number k and suppose that there are m distinct sequences ${\sigma }_1 \dots , {\sigma }_m$ of length k from $D'$ so that no $P_{{\sigma }_i}$ is bounded above in C. If there is a $\sigma _i$ such that the set

$$ \begin{align*}\{ a \in C \, : \, P_{{\sigma}_i} \cap \{a, S_D(a), \ldots, S_D^{l-1}(a)\} = \emptyset\}\end{align*} $$

is cofinal in C, then $P^{\prime }_{\sigma _i}$ contains infinitely many elements which are greater than or equal to $l \cdot \delta _1$ , contradicting statement $(*)$ above. Therefore for all sufficiently large $a \in C$ , each set $P_{{\sigma }_i}$ must intersect $\{a, S_D(a), \dots , S_D^{l-1}(a)\}$ . Since the sets $P_{\sigma _1}, \ldots , P_{\sigma _m}$ are pairwise disjoint, this implies that $m \leq l$ , as we wanted.

The same proof, mutatis mutandis, shows the existence of $m_1$ .

At this point, we can repeat some arguments from our paper [3] (specifically, Lemma 2.33 and Proposition 2.35) to conclude that every $\omega $ -chain is eventually periodic. In the interest of making the current paper self-contained, we now present a simplified version of the combinatorial argument found there. Suppose that $\tau $ is an infinite sequence $a_0, a_1, \ldots $ of elements from the set $D' = \{\delta _1, \ldots , \delta _n\}$ , and recall the definition of “eventually m-periodic” from Definition 3.13 above. Say that a finite sequence $\sigma $ from $D'$ is infinitely recurring in $\tau $ in case it occurs infinitely often as a subsequence $a_i, a_{i+1}, \ldots , a_{i+k}$ of $\tau $ . Let $f_\tau \, : \, \omega \rightarrow \omega $ be the function defined by the rule that $f_\tau (k)$ is the number of infinitely-recurring sequences of length k in $\tau $ .

The crucial fact about $f_\tau $ is the following:

Lemma 3.19. If $M \in \omega $ and $f_\tau (k) \leq M$ for every $k \in \omega $ , then the sequence $\tau $ is eventually m-periodic for some $m \leq M$ .

Proof. Suppose that $f_\tau (k) \leq M$ for every $k \in \omega $ . Note that since $D'$ is finite, it follows from the Pigeonhole Principle that every infinitely-recurring sequence of length k in $\tau $ can be extended to at least one infinitely-recurring sequence of length $k+1$ in $\tau $ . Hence

$$ \begin{align*}f_\tau(k) \leq f_{\tau}(k+1),\end{align*} $$

that is, the function $f_\tau $ is nondecreasing. By the hypothesis that values of $f_\tau $ are bounded above by some M, there is $k \in \omega $ for which $f_\tau (k) = f_\tau (k+1)$ .

Claim 3.20. Without loss of generality, there is $k \in \omega $ such that $f_\tau (k) = f_{\tau }(k+1)$ and furthermore every subsequence of $\tau $ of length k or $k+1$ is infinitely recurring.

Proof. First pick some k such that $f_\tau (k) = f_\tau (k+1)$ , which exists by the argument just above. If $\sigma $ is a subsequence of $\tau $ which is not infinitely recurring, then there is some point $p_\sigma \in \omega $ such that $\sigma $ never occurs past $p_\sigma $ . Let p be the maximum of $p_\sigma $ for all subsequences $\sigma $ of length k or $k+1$ which occur only finitely often in $\tau $ (of which there can be only finitely many, since $D'$ is finite). Then every subsequence of length k or $k+1$ which occurs past the point p must be infinitely recurring.

Now fix some k as in the conclusion of the Claim above. Hence if $\sigma $ is any length-k subsequence of $\tau $ , it has a unique length- $(k+1)$ end extension $\sigma ^+$ which occurs as a subsequence of $\tau $ , and we define $\sigma '$ to be the sequence formed by the last k elements of $\sigma ^+$ . Let $\sigma $ be the first k elements of $\tau $ and form the sequence

$$ \begin{align*}\sigma, \sigma', \sigma", \ldots, \sigma^{(i)}, \ldots\end{align*} $$

by recursively applying this operation. By the Pigeonhole Principle, there must be $i < j$ such that $\sigma ^{(i)} = \sigma ^{(j)}$ , and we may pick j so that $j-i \leq f_\tau (k) \leq M$ . Thus $\tau $ is $(j-i)$ -periodic past the first instance of $\sigma ^{(i)}$ , and we are done.

From the previous Lemma, we can quickly deduce Proposition 3.15:

Proof. We will show that there are finitely many finite sequences $\sigma _1, \ldots , \sigma _k$ such that any $\omega $ -chain of D is eventually $\sigma _i$ -periodic for some $i \in \{1, \ldots , k\}$ , and the same argument, with only notational changes, applies to $\omega ^*$ -chains of D, yielding the conclusion of Proposition 3.15.

So fix some $\omega $ -chain C of D. Pick $a\in C$ arbitrarily and let $\tau $ be the $\omega $ -chain $(\gamma _D(a), \gamma _D(S_D(a)) \dots \gamma _D(S_D^l(a)), \dots )$ . By Lemma 3.18, $f_\tau (n) \leq m_0$ for all $n \in \omega $ . Applying Lemma 3.19 we conclude that $\tau $ , and hence C, is eventually m-periodic for some $m \leq m_0$ . Since $D'$ is finite, there are only finitely many sequences of length at most $m_0$ from $D'$ , and the conclusion of Proposition 3.15 follows.

We need one final intermediate proposition elucidating the structure of D which will allow us to deduce Proposition 3.4. In order to state this result we need a definition.

Definition 3.21. Let $\sigma $ be any finite sequence of elements of $D'$ . A closed interval $I \subseteq R^{\geq 0}$ is a $\sigma $ -interval if:

1. (1) $I=[a,b]$ or $[a, \infty )$ with $a,b \in D$ .

2. (2) $I \cap D$ is infinite.

3. (3) If Z is a $\mathbb {Z}$ -chain and $Z \subset I $ then Z is $\sigma $ -periodic.

4. (4) If $I=[a,b]$ or $[a, \infty )$ then $\mathcal {Z}_{\geq }(a)$ is $\sigma $ -periodic.

5. (5) If $I=[a,b]$ then $\mathcal {Z}_{\leq }(b)$ is $\sigma $ -periodic.

Given this definition we aim to prove:

Proposition 3.22. Assume $\{\sigma _1, \dots , \sigma _k\}$ is a characteristic set for D. There is a finite collection of pairwise disjoint intervals $\mathcal {C}$ so that each $I \in \mathcal {C}$ is a $\sigma _i$ -interval for some $1 \leq i \leq k$ and $D \setminus \bigcup _{I \in \mathcal {C}}I$ is finite.

Fix $\{\sigma _1, \dots , \sigma _k\}$ , a characteristic set for D.

To establish Proposition 3.22 we need a key preliminary Lemma:

Lemma 3.23. All but finitely many $\mathbb {Z}$ -chains in D are periodic.

Proof. Suppose toward a contradiction that there are infinitely many non-periodic $\mathbb {Z}$ -chains in D. If there are sequences in $\{\sigma _1, \ldots , \sigma _k\}$ of different lengths, then if m is a common multiple of the lengths of all the $\sigma _i$ ’s, we may replace each $\sigma _i$ with a suitable number of concatenations with itself which has length m, and thus without loss of generality each $\sigma _i$ has the same length m. There is also no harm in assuming that the set $\{\sigma _1, \ldots , \sigma _k\}$ is closed under cyclic permutations.

Fix some $\mathbb {Z}$ -chain Z which is not periodic. Then there is some $a \in Z$ such that $\mathcal {Z}_{\geq }(a)$ is not periodic. By Proposition 3.15, $\mathcal {Z}_{\geq }(a)$ is eventually periodic. We may assume that a is maximal in the sense that if $a' \in Z$ and $a'> a$ , then $\mathcal {Z}_{\geq }(a')$ is periodic. Let $\tau $ be the $\omega $ -chain $\gamma _D(a), \gamma _D(S_D(a)), \gamma _D(S_D^2(a)), \ldots $ of successive elements of $D'$ beginning at $\gamma _D(a)$ . Then there is some $d_Z \in D'$ and some $i_Z \in \{1, \ldots , k\}$ such that $\tau = d_Z \sigma _{i_Z}^\omega $ (the concatenation of $d_Z$ followed by $\omega $ copies of $\sigma _{i_Z}$ ), since by our maximality assumption on a, the $\omega $ -chain of successive elements of $D'$ which begins at $\gamma _D(S_D(a))$ must be periodic.

By the assumption that there are infinitely many non-periodic $\mathbb {Z}$ -chains and the Pigeonhole Principle, there is a single $d \in D'$ and a single $i \in \{1, \ldots , k\}$ such that there are infinitely many non-periodic $\mathbb {Z}$ -chains Z such that $d_Z = d$ and $i_Z = i$ . Let $\sigma _i = \sigma _i^- e$ where $\sigma _i^-$ is the prefix consisting of the first $m-1$ elements of $\sigma _i$ and e is the final element of $\sigma _i$ . Then $e \neq d$ , since otherwise

$$ \begin{align*}d \sigma_i^\omega = d \sigma_i^- e \sigma_i^- e \ldots\end{align*} $$

would be an m-periodic sequence, contrary to our assumption.

Now let $\sigma = d \sigma _i$ . Since $d \neq e$ , the sequence $\sigma $ cannot be a subsequence of any m-periodic $\omega $ -chain. Thus there are infinitely many $a \in P_{\sigma }$ such that a is the last element of its $\mathbb {Z}$ -chain which intersects $P_{\sigma }$ . Therefore $P_{\sigma }$ is an infinite definable discrete subset of D and there are infinitely many elements $a \in P_{\sigma }$ such that $S_{P_\sigma }(a) - a \gg D'$ , but this contradicts Corollary 3.10.

Proof of Proposition 3.22.

By Proposition 3.15, for every narrow definable discrete set D which is bounded below, there is some $k \in \omega $ and finite sequences $\sigma _1, \dots , \sigma _k$ from $D'$ so that $\{\sigma _1, \dots , \sigma _k\}$ is a characteristic set for D. Let $k(D)$ be the minimum number such that there is a characteristic set $\{\sigma _1, \ldots , \sigma _{k(D)}\}$ for D. Without changing the number $k(D)$ of sequences in such a set, we may further assume that all the sequences $\sigma _i$ have the same length (arguing as in the first paragraph of the proof of Lemma 3.23). We also note that by minimality of $k(D)$ , no two sequences $\sigma _i$ and $\sigma _j$ for $1 \leq i < j \leq k(D)$ are cyclic permutations of one another. In case D is finite, we define $k(D) = 0$ , and whenever D is infinite, $k(D)> 0$ .

Our proof is by induction on $k(D)$ . We assume that the conclusion of Proposition 3.22 holds for all narrow discrete sets E which are bounded below and for which $k(E) < k(D)$ . We prove the conclusion of Proposition 3.22 for D. Note that the base case is when $k(D) = 0$ , which holds if and only if D is finite, in which case the conclusion of Proposition 3.22 is trivial.

Now suppose that $k(D)> 0$ . Fix a characteristic set $\{\sigma _1, \ldots , \sigma _{k(D)}\}$ for D with all $\sigma _i$ of the same length, none of which is a cyclic permutation of the other. We apply Proposition 3.8 to the subset of D defined by $P_{\sigma _1}$ to obtain a finite collection of closed, pairwise-disjoint intervals $\mathcal {C}_0 = \{C_1, \ldots , C_n\}$ such that $P_{\sigma _1} \subseteq \bigcup {1 \leq i \leq n} C_i$ and for each $i \in \{1, \ldots , n\}$ ,

1. (1) $P_{\sigma _1}$ is cofinal and coinitial in every $\mathbb{Z} $ -chain contained in $D \cap C_i$ ,

2. (2) $P_{\sigma _1}$ is cofinal in every $\omega $ -chain contained in $D \cap C_i$ , and

3. (3) $P_{\sigma _1}$ is coinitial in every $\omega ^*$ -chain contained in $D \cap C_i$ .

Since the $\mathbb{Z} $ -, $\omega $ -, and $\omega ^*$ -chains in (1)–(3) must be eventually $\sigma _i$ -periodic for some i, and by our assumptions that the $\sigma _i$ ’s are all of the same length and not cyclic permutations of one another, it follows that the chains in (1)–(3) are all eventually $\sigma _1$ -periodic.

The conclusion of Proposition 3.8 allows for some intervals $C_i$ which intersect $P_{\sigma _1}$ in only one point; by discarding such $C_i$ , we may further assume that every set $C_i \cap P_{\sigma _1}$ is infinite, and that

1. (4) $P_{\sigma _1} \setminus \bigcup _{C_i \in \mathcal {C}_0} C_i$ is finite.

The intervals in $\mathcal {C}_0$ may not be $\sigma _1$ -intervals for either one of two reasons. First, it may be the case that for some W, an eventually $\sigma _1$ -periodic but not $\sigma _1$ -periodic $\mathbb{Z} $ -chain of D, we have that $W \subseteq I$ for some $I \in \mathcal {C}_0$ . But by Lemma 3.23 there are only finitely many such chains. Thus we can rectify this problem by partitioning the elements of $\mathcal {C}_0$ into subintervals so that no such W is contained in any of the intervals. Secondly for some $J \in \mathcal {C}_0$ with $J=[a,b]$ or $J=[a, \infty )$ it may be the case that either $Z_{\geq }(a)$ or $Z_{\leq }(b)$ are only eventually $\sigma _1$ -periodic and not $\sigma _1$ -periodic. But this is easily fixed by replacing a by a suitably chosen $S^l(a)$ or replacing b by a suitably chosen $S^{-l}(b)$ . With these adjustments $\mathcal {C}_0$ is a finite collection of $\sigma _1$ -intervals.

Next let $D_1, \dots , D_r$ be the finitely many infinite D-convex components of $D \setminus \bigcup _{C_i \in \mathcal {C}_0} C_i$ (we may ignore any finite D-convex components). For each $i \in \{1, \ldots , r\}$ , any $\omega $ -chain of $D_i$ is also an $\omega $ -chain of D, and by construction it is not eventually $\sigma _1$ -periodic, hence it is $\sigma _j$ -periodic for some $j \in \{2, \ldots , k(D)\}$ , and likewise for $\omega ^*$ -chains; thus $\{\sigma _2, \dots , \sigma _{k(D)}\}$ is a characteristic set for each $D_i$ , and so $k(D_i) < k(D)$ . By the induction hypothesis we may find finite collections of intervals $\mathcal {C}_i$ for $1 \leq i \leq r$ so that each $I \in \mathcal {C}_i$ is a $\sigma _j$ -interval for some $2 \leq j \leq k(D)$ and so that $D_i \setminus \bigcup _{I \in \mathcal {C}_i}I$ is finite. Then setting $\mathcal {C}=\bigcup _{i =0}^r\mathcal {C}_i$ yields the desired collection of intervals.

Now at last we are in a position to prove Proposition 3.4.

Proof. Let D be definable, discrete, narrow, and bounded below. By Proposition 3.22, there are finitely many finite sequences $\sigma _1, \ldots , \sigma _k$ from $D'$ such that D is the union of a finite set F plus finitely many sets of the form $D \cap I$ where I is a $\sigma $ -interval for some $\sigma \in \{\sigma _1, \ldots , \sigma _k\}$ . Without loss of generality we may assume $D = D \cap I$ for some $\sigma $ -interval I.

Also without loss of generality, $\sigma $ is of minimal length—that is, for any finite sequence $\sigma '$ from $D'$ which is shorter than $\sigma $ , the interval I is not a $\sigma '$ -interval. Let k be the length of $\sigma $ , and for $i \in \{0, 1, \ldots , k-1\}$ , let

$$ \begin{align*}D_i = \{a \in D \, : \, S_D^i(a) \in P_\sigma\}.\end{align*} $$

Then $D = D_0 \cup \cdots \cup D_{k-1}$ , so it suffices to show that each set $D_i$ is pseudo-arithmetic.

Claim 3.24. if $i \in \{0, \ldots , k-1\},$ then $S_{D_i}(a) = S^k_D(a).$

Proof. Suppose that $0 \leq i < k$ , $a \in D$ , $S^i_D(a) \in P_\sigma $ , and $j \in \omega $ is minimal such that $j> i$ and $S^j_D(a) \in P_\sigma $ . Since $|\sigma | = k$ , it follows that $S^{i+k}_D(a) \in P_\sigma $ , so $j \leq i + k$ . If $j - i < k$ , then the infinite sequence $\gamma _D(a), \gamma _D(S_D(a)), \ldots , \gamma _D(S^\ell _D(a)), \ldots $ would be $(j-i)$ -periodic, and thus $D \cap I$ would be $\sigma '$ -periodic where $\sigma '$ is a subsequence of $\sigma $ of length $j-i$ , contradicting the minimality of k. Therefore $j = i + k$ , and the Claim follows.

By the Claim, if $\sigma = (d_1, \ldots , d_k)$ and $\eta = \sum _{i=1}^k d_i$ , then $D_i$ is $\eta $ -pseudo-arithmetic, as we wanted.

3.2. Deducing Theorem 3.2 from Proposition 3.4

In this section we show how Theorem 3.2 follows from Proposition 3.4. This will be achieved by showing that after partitioning and performing simple definable transformations on the discrete set D we may reduce to the situation of discrete sets of the type occurring in Proposition 3.4.

Throughout the subsection we fix $D\subseteq R$ a definable discrete set. Note that Assumption 3.7 of the previous subsection is no longer in effect, so D is not necessarily bounded below. But as noted in Proposition 3.5 in this subsection we still maintain:

Assumption 3.25. $\mathcal {R}$ is $\omega $ -saturated.

The following two Lemmas are immediate. Recall that if D is discrete and $a \in R$ then $D-a=\{b-a : b \in D\}$ and ${-}D=\{{-}b: b \in D\}$ .

Lemma 3.26.

1. (1) If D is a definable discrete set and $a \in R$ then $\gamma _D(b)=\gamma _{D-a}(b-a)$ for any $b \in D$ and hence $D'=(D-a)'$ . In particular if D is narrow so is $D-a$ . Also if D is $\eta $ -pseudo-arithmetic then so is $D-a$ .

2. (2) If D is definable and discrete, $a \in D$ , and $S_D(a)=b$ then $S_{{-}D}({-}b)=-a$ and $\gamma _{{-}D}({-}b)=\gamma _D(a)$ . Hence $D'=({-}D)'$ . In particular if D is narrow so is ${-}D$ and if D is $\eta $ -pseudo-arithmetic then so is ${-}D$ .

Lemma 3.27.

1. (1) If D is the finite union of points and definable discrete sets each of which is piecewise pseudo-arithmetic then D is piecewise pseudo-arithmetic.

2. (2) If D is piecewise pseudo-arithmetic and $a \in R$ then $D-a$ is also piecewise pseudo-arithmetic.

3. (3) D is piecewise pseudo-arithmetic then so is ${-}D$ .

Proposition 3.28. To show that D is piecewise pseudo-arithmetic it suffices to show that any definable discrete E which is bounded below is a finite union of points and definable discrete sets $E_i$ which are narrow.

Proof. Let D be an arbitrary definable discrete set. Let $D_0=D \cap R^{\geq 0}$ and let $D_1=D\setminus D_0$ . By Lemma 3.27(1) it suffices to show that $D_0$ and $D_1$ are piecewise pseudo-arithmetic. By Lemma 3.27(3) to show that $D_1$ is piecewise pseudo-arithmetic if suffices to show that ${-}D_1$ is piecewise pseudo-arithmetic. Thus we may assume that D is bounded below. By assumption D is a finite union of points and definable discrete sets $E_i$ for $1 \leq i \leq r$ each of which is narrow. By Lemma 3.27(1) it suffices to show that $E_i$ is piecewise pseudo-arithmetic for each $1 \leq i \leq r$ . Fix $1 \leq i \leq r$ . But Proposition 3.4 applies to $E_i$ and so $E_i$ is piecewise pseudo-arithmetic. Hence D is piecewise pseudo-arithmetic.

Thus for the rest of this subsection we work with:

Assumption 3.29. D is bounded below.

We aim to show that D is a finite union of definable subsets $D_i$ which are narrow. In order to establish this we first show that D can be decomposed into finitely many definable subsets which can be considered highly “uniform.” To this end we need some definitions (recall the definition of D-convex–see Definition 3.6).

Definition 3.30. A finite convex partition of D is a finite partition $D = D_0 \cup \ldots \cup D_m$ such that each $D_i$ is D-convex. We say that the partition is definable if each  $D_i$  is.

Definition 3.31. A definable discrete set D is uniformized if either D is a singleton or D is infinite and there is $N(D) \in \omega $ so that if $C \subseteq D$ is D-convex and of size at least $N(D)$ then for all $\delta \in D'$ there is $a \in C$ with $\gamma _D(a)=\delta $ .

Our first goal is to prove:

Proposition 3.32. If D is a definable discrete set which is bounded below, then D has a definable finite convex partition into subsets $D_1, \dots , D_n$ so that each $D_i$ is uniformized.

We begin by establishing the necessary results to show that D is a finite union of uniformized sets. The following is immediate:

Lemma 3.33. Given $D = D_1 \cup \ldots \cup D_m$ a finite convex partition of D. If $a \in D_i$ for some $i \in \{1, \ldots , m\}$ and a is not maximal in $D_i$ then $\gamma _{D_i}(a)=\gamma _D(a)$ . In particular we have that $D^{\prime }_i \subseteq D'$ .

Notice that if $E \subseteq D$ is definable and D-convex it is potentially the case that $\gamma _E(\max (E))$ is not defined while $\gamma _D(\max (E))$ is defined and thus it may not be the case that $E'=\{\gamma _D(e) : e \in E\}$ .

To begin with, if $\delta \in D'$ and $\gamma _D^{-1}(\delta )$ is finite then we can take a definable finite convex partition of D so that if $\gamma _D(a)=\delta $ then $a \notin D_i$ for any infinite $D_i$ in the partition. Thus by Lemma 3.33 $\delta \notin D_i'$ for any infinite $D_i$ in the partition. Thus, as $D'$ is finite, we may make the following assumption:

Assumption 3.34. For each $\delta \in D'$ , there are infinitely many elements $a \in D$ with $\gamma _D(a) = \delta $ .

We need a definition.

Definition 3.35. For $X \subseteq D$ and $\delta _1 \dots \delta _l \in D'$ we say that X is an anti- $\{\delta _1, \dots , \delta _l\}$ set if for no $a \in X$ is $\gamma _D(a)=\delta _i$ for $1 \leq i \leq l$ . If $l = 1$ , we omit the braces and call this an anti- $\delta _1$ set. A subset $E \subseteq D$ is called an anti- $\{\delta _1, \ldots , \delta _l\}$ -component if E is a D-convex, anti- $\{\delta _1, \dots , \delta _l\}$ set, and if $F \subseteq D$ is D-convex with $E \subset F$ then F is not an anti- $\{\delta _1, \ldots , \delta _l\}$ set.

To establish Proposition 3.32 we first show that for any $\{\delta _1, \dots , \delta _l\} \subseteq D'$ there is a finite bound on the size of any finite anti- $\{\delta _1, \dots , \delta _l\}$ component (Lemma 3.37). In turn we will use this to establish that after potentially partitioning D into definable D-convex subsets we can reduce to the case that for any $\delta \in D'$ there are no infinite anti- $\delta $ components (Lemma 3.39). Once these two facts are established Proposition 3.32 is immediate.

For the finite case we need a simple fact.

Lemma 3.36. Let $\mathcal {R}$ be an OAG and let $\delta _1, \dots , \delta _l \in R^{>0}$ . If $Z \subseteq \mathbb{N} ^l$ is infinite then

$$\begin{align*}S=\left\{ m_1 \delta _1 + \dots + m_l\delta_l : (m_1, \dots, m_l) \in Z\right\}\end{align*}$$

is infinite.

Proof. We induct on l. If $l=1$ the result is immediate. Thus suppose we have $\delta _1 < \dots <\delta _{l+1}$ . Let $\pi _{l+1} : \mathbb{N} ^{l+1} \to \mathbb{N} $ be the projection onto the last coordinate and first suppose that $\pi _{l+1}[Z]$ is finite. Let $\pi _{(1 \dots l)}: \mathbb{N} ^{l+1} \to \mathbb{N} ^l$ be the projection onto the first l coordinates. There is $m^* \in \pi _{l+1}[Z]$ whose pre-image is infinite. Let $Z_0:=\pi _{(1\dots l)}[\pi _{l+1}^{-1}(m^*)]$ . Then by induction

$$\begin{align*}\{ m_1 \delta _1 + \dots + m_l\delta_l+m^*\delta_{l+1} : (m_1 \dots m_l) \in Z_0\} \subseteq S\end{align*}$$

is infinite.

Therefore we may assume that $\pi _{l+1}[Z]$ is infinite. As $\delta _{l+1}$ is maximal among the $\delta _i$ ’s any sum of the form $m_1\delta _1 + \cdots + m_{l+1}\delta _{l+1}$ with $m_{l+1} \not = 0$ is Archimedean equivalent to $\delta _{l+1}$ (recall all the $\delta _i$ ’s are positive and $Z \subseteq \mathbb{N} ^{l+1}$ ). As $\pi _{l+1}[Z]$ is infinite, the set S must be cofinal in the Archimedean class $[\delta _{l+1}]$ of $\delta _{l+1}$ and thus infinite.

We note in passing that by a theorem of Levi, an Abelian group is orderable just in case it is torsion-free [12], and thus the conclusion of the previous lemma holds for any torsion-free Abelian group.

Lemma 3.37. For any $\delta _1 \dots \delta _l \in D'$ there is $N \in \omega $ so that if $X \subseteq D$ is a finite anti- $\{\delta _1\dots \delta _l\}$ -component, then $|X|< N$ .

Proof. Suppose the lemma is false and take $\delta _1, \ldots , \delta _l$ so that D has arbitrarily large finite anti- $\{\delta _1, \ldots , \delta _l\}$ -components. Also let $D' = \{\delta _1, \ldots , \delta _n\}$ for $n \geq l$ (recalling that $D'$ must be finite). Let

$$\begin{align*}D_0=\{x \in D: \gamma_D(x) \in \{\delta_1, \ldots, \delta_l\} \}.\end{align*}$$

Let E be a finite anti- $\{\delta _{1} \dots \delta _{l}\}$ -component of D and further assume that $\min {(E)}>\min (D)$ . Let $M=|E|$ and let a be the minimal element of E. Now note that $\gamma _{D_0}(S^{-1}_D(a))=m_1\delta _1 + \cdots +m_n\delta _n$ where $m_1 + \cdots +m_n=M+1$ . As the size of finite anti- $\{\delta _{1} \dots \delta _{l}\}$ -components of D is unbounded there must be an infinite $Z \subseteq \mathbb{N} ^n$ so that if $(m_1 \dots m_n) \in Z$ then $m_1 \delta _1 + \dots + m_n\delta _n \in D_0'$ . By the previous lemma $D_0'$ is infinite, which is impossible since $D_0$ is a definable discrete set.

Thus we have a uniform bound on finite anti- $\{\delta _1, \dots , \delta _l\}$ components. To establish the fact on infinite anti- $\delta $ components we need a simple consequence of Theorem 2.14.

Lemma 3.38. If $D_0$ and $D_1$ are infinite discrete definable sets, then it cannot be the case that $D_0' \ll D_1'$ .

Proof. Suppose otherwise. By Lemma 3.26 we may without loss of generality assume that $D_i \subseteq R^{\geq 0}$ and $0 \in D_i$ for $i \in \{0,1\}$ . Set $D_0'=\{\eta _1, \dots , \eta _m\}$ . As ${D_0' \ll D_1'}$ and $0$ is the minimal element of $D_0$ it follows that if d is among the first $\omega $ many elements of $D_0$ then $d=l_1 \eta _1 + \cdots +l _m\eta _m$ for some $l_1 \dots l_m \in \mathbb {N}$ . In particular $d<D_1'$ . Hence by compactness find $\varepsilon \in R$ with $\varepsilon < D_1'$ so that $[0, \varepsilon ) \cap D_0$ is infinite. Then $(0, \varepsilon ) \cap D_0 < D_1'$ , violating Theorem 2.14.

Lemma 3.39. There is a definable finite convex partition $D_0 \cup \cdots \cup D_m$ of D so that for every $D_i$ and every $\delta \in D_i'$ the set $D_i$ has no infinite anti- $\delta $ -component.

Proof. We proceed by induction on $n=|D'|$ . If $n = 1$ then the result is trivial. Assume that $D'=\{\delta _1, \dots , \delta _{n+1}\}$ where the $\delta _i$ ’s are listed in increasing order, and suppose that we have established the lemma for all definable discrete sets which are bounded below and whose difference sets have size at most n.

We will do a sub-induction on $i \in \{1, \ldots , n+1\}$ , in reverse order (beginning with $i = n+1$ ), to show the following:

$(*)_i$ There is a definable finite convex partition of $D = D_0 \cup \cdots \cup D_m$ such that for every $1 \leq \ell \leq m$ and every $j \in \{i, i+1, \ldots , n+1\}$ , either $\delta _j \notin D^{\prime }_l$ , or else $D_l$ has no infinite anti- $\delta _j$ -component.

Notice that $(*)_1$ is our desired result.

First we will establish the base case, that is, $(*)_{n+1}$ . If there are only finitely many infinite anti- $\delta _{n+1}$ -components in D, then $(*)_{n+1}$ follows quickly: there is a definable finite convex partition $D = D_0 \cup \cdots \cup D_m$ such that for each $i,$ either (i) $D_i$ is an infinite anti- $\delta _{n+1}$ -component, or else (ii) $D_i$ has no infinite anti- $\delta _{n+1}$ -components.

Thus we may assume that there are infinitely many infinite anti- $\delta _{n+1}$ -components.

Let

$$\begin{align*}E=\{a \in D : a \text{ lies in an infinite anti-}\delta_{n+1} \text{-component}\}\end{align*}$$

which is definable by Lemma 3.37. Let

$$\begin{align*}E_0=\{a \in E : \gamma_D(S^{-1}_D(a))=\delta_{n+1}\},\end{align*}$$

or in other words, $E_0$ is the set of all initial points of infinite anti- $\delta _{n+1}$ -components. Notice that as we assume that there are infinitely many infinite anti- $\delta _{n+1}$ -components $E_0$ is infinite.

By our assumptions we may find $k \in \{1, \dots , n+1\}$ minimal so that there are infinitely many infinite anti- $\{\delta _k \dots \delta _{n+1}\}$ -components. Notice that $k = 1$ is impossible and thus $k \geq 2$ .

Pick $c,d \in D$ such that $F:=[c,d] \cap D$ is infinite and $F' \subseteq \{\delta _1, \dots , \delta _{k-1}\}$ . Notice that by the minimality of k and the saturation of $\mathcal {R}$ , for infinitely many anti- $\{\delta _k \dots \delta _{n+1}\}$ -components C, there are infinitely many $a \in C$ with $\gamma _D(a)=\delta _{k-1}$ .

Thus there are infinitely many $a \in E_0$ such that $S_{E_0}(a) - a \gg \delta _{k-1}$ , so by compactness we can pick $\zeta \gg \delta _{k-1}$ such that there are infinitely many $a \in E_0$ satisfying $S_{E_0}(a)-a>\zeta $ . Let

$$\begin{align*}E_1=\{a \in E_0 : S_{E_0}(a)-a>\zeta\}.\end{align*}$$

F and $E_1$ are infinite discrete sets so that $F' \ll E_1'$ , contradicting Lemma 3.38. This concludes the proof of $(*)_{n+1}$ .

Now assume that $(*)_i$ holds for $i> 1$ , and for the inductive step we need to show $(*)_{i-1}$ . After partitioning as in $(*)_i$ , we may assume that in D itself there are no infinite anti- $\delta _j$ -components for any $j \geq i$ . As in the proof of $(*)_{n+1}$ , the case where D has only finitely many infinite anti- $\delta _{i-1}$ -components is straightforward. Thus we assume that D has infinitely many infinite anti- $\delta _{i-1}$ -components. By further partitioning D as necessary and applying induction on $|D'|$ we may assume that in any infinite anti- $\delta _{i-1}$ -component of D, there are infinitely many points a with $\gamma _D(a)=\delta _{n+1}$ . Now set

$$\begin{align*}E=\{ a \in D : a \text{ lies in an infinite anti-}\delta_{i-1} \text{-component}\}\end{align*}$$

which, again, is definable by Lemma 3.37. Set

$$\begin{align*}E_0=\{a \in E : S^{-1}_D(a) \notin E\}.\end{align*}$$

Notice that $E_0$ is infinite and if $a \in E_0$ is not maximal then $S_{E_0}(a)-a\gg \delta _{n+1}$ . Now D and $E_0$ are infinite discrete sets such that $D' \ll E_0'$ , contradicting Lemma 3.38. This completes the sub-induction and hence establishes the Lemma.

Proof Of Proposition 3.32.

Partition D into $D_1 \dots D_m$ as in Lemma 3.39. Now by Lemma 3.37 for each $1 \leq j \leq m$ there is $N_j \in \omega $ so that for any $\delta _1 \ldots \delta _l \in D_j'$ if X is an anti- $\{\delta _1 \ldots \delta _l\}$ component then $|X|<N_j$ . It follows that $D_j$ is uniformized.

Next we need to establish that we may partition a discrete set, D, into finitely many definable subsets $D_i$ each of which is narrow.

To achieve this we first show:

Proposition 3.40. Suppose that D is a uniformized then D is a finite union of definable discrete sets $D_1, \dots , D_m$ each of which is narrow.

Proof. First we set some notation. If E is a definable discrete set, let $l(E)$ be the (finite) number of distinct Archimedean classes represented in $E'$ . For ease of notation let $l=l(D)$ for our fixed discrete set D. Let $K_1 < \cdots < K_l$ list all the Archimedean classes in $D'$ and let $M(D)$ be the cardinality of the largest D-convex subset of D of the form $[a,b) \cap D$ with $a,b \in D$ so that for no $c \in [a,b) \cap D$ is $\gamma _D(c) \in K_l$ . As D is uniformized $M(D)$ is finite.

We prove the Proposition by induction on $l=l(D)$ . If $l=1$ the result is trivial, so suppose that $l>1$ and the conclusion of the Proposition holds for all discrete sets E which are bounded below and for which $l(E)<l(D)$ . We proceed by a sub-induction on $M(D)$ . Note that $M(D)=0$ is impossible if $l> 1$ , so suppose that $M(D)\geq 1$ and the proposition is true for all uniformized discrete sets E which are bounded below, for which the Archimedean classes in $E'$ are among $K_1 \dots K_l$ , and are such that $M(E)<M(D)$ .

Now define

$$\begin{align*}D_1=\{a \in D : \gamma_D(a) \in K_l\} \cup \{\max(D)\}.\end{align*}$$

(Where $\max (D)$ is added if and only if it exists.)

Since $M(D)$ is finite and $K_l$ is the maximal Archimedean class every element $\delta \in D_1'$ must lie in $K_l$ . Thus $D_1$ is a definable subset of D so that all elements of $D_1'$ lie in the same Archimedean class.

Now let $\tilde {D}=D \setminus D_1$ . If $a \in \tilde {D}$ and $\gamma _D(S_D(a)) \notin K_l$ then $\gamma _{\tilde {D}}(a)=\gamma _D(a)$ and so $\gamma _{\tilde {D}}(a) \in K_1 \cup \dots \cup K_l$ . Next suppose that $\gamma _D(S_D(a))\in K_l$ . As D is uniformized and $l>1$ there is some $r \in \mathbb {N}$ so that $\gamma _D(S_D^r(a)) \notin K_l$ . In particular as $K_l$ is the maximal Archimedean class it follows that $\gamma _{\tilde {D}}(a) \in K_l$ . Thus the Archimedean classes represented in $\tilde {D}'$ are among $K_1, \dots , K_l$ .

We may apply Proposition 3.32 to $\tilde {D}$ and work within one of the $\tilde {D}$ -convex pieces, so without loss of generality $\tilde {D}$ is uniformized and the Archimedean classes represented in $\tilde {D}'$ are still among $K_1 \dots K_l$ (which follows from Lemma 3.33). If $l(\tilde {D}) < l(D)$ , we are done by induction. Thus we may assume that all Archimedean classes $K_1 \dots K_l$ are represented in $\tilde {D}'$ .

Suppose that $M(\tilde {D}) \geq M(D)$ and let this be witnessed by ${[a,b) \cap \tilde {D}}$ with ${a,b \in \tilde {D}}$ . Then $\gamma _D(b) \notin K_l$ and b is not maximal in D. Next suppose that $c\in [a,b) \cap D$ and $\gamma _D(c) \in K_l$ . As D is uniformized and $l>1$ there is some minimal $r\in \mathbb {N}$ so that $S_D^{-r}(c) \in [a, b) \cap \tilde {D}$ . But then $S_{\tilde {D}}(S^{-r}(c)) \in K_l$ contradicting the definition of $M(\tilde {D})$ . Hence for every $c \in [a,b) \cap D$ we have $\gamma _D(c) \notin K_l$ . But then $[a,S_D(b))$ is of size at least $M(D)+1$ and $\gamma _D(c) \notin K_l$ for all $c \in [a,S_D(b))$ , a contradiction. Thus $M(\tilde {D})<M(D)$ and we are done by induction.

The final remaining element needed in order to establish Theorem 3.2 is:

Proposition 3.41. If D is a definable discrete set which is bounded below then D is a finite union of definable, narrow, discrete sets.

Proof. First apply Proposition 3.32 to D. Thus we can write $D=\bigcup _{i=1}^nD_i$ where the $D_i$ form a definable convex partition of D and each $D_i$ is uniformized. Fix i, as $D_i$ is bounded below apply Proposition 3.40 to write $D_i$ as a finite union of definable sets which are narrow. But then D is a finite union of definable, narrow, discrete sets.

Proof Of Theorem 3.2.

The theorem follows immediately from Proposition 3.28 and Proposition 3.41.

3.3. Proof of Theorem 1.3 and an example

In this final subsection we prove Theorem 1.3 and finish the subsection highlighting this theorem’s limits. As in the previous section we work in a structure $\mathcal {R}=\langle R, +, <, \dots \rangle $ , but we no longer assume any saturation for $\mathcal {R}$ .

We need some basic results about the structure of pseudo-arithmetic sets.

Lemma 3.42. Suppose that $E_0$ and $E_1$ are both definable $\eta $ -pseudo-arithmetic sets and that $0$ is the least element of both $E_0$ and $E_1$ . Then either $E_0$ is an initial segment of $E_1$ or $E_1$ is an initial segment of $E_0$ .

Proof. We first show that either $E_0 \subseteq E_1$ or $E_1 \subseteq E_0$ . Suppose that $E_0 \not \subseteq E_1$ . Let $\alpha $ be the least element of $E_0 \setminus E_1$ . Note that $\alpha $ must have a predecessor, $\alpha -\eta $ , in $E_0$ (and hence $\alpha -\eta $ is also in $E_1$ ). If $S_{E_1}(\alpha -\eta )$ is defined then $S_{E_1}(\alpha -\eta )=\alpha -\eta +\eta =\alpha $ and $\alpha \in E_1$ . Hence $\alpha -\eta $ must be the maximal element of $E_1$ . If $E_1$ is not a subset of $E_0$ pick $\gamma $ maximal in $E_1$ not in $E_0$ . Then $\gamma <\alpha -\eta $ and so $\gamma +\eta \in E_1$ and notice that also $\gamma +\eta \in E_0$ . But then immediately $\gamma \in E_0$ , a contradiction. Hence $E_1 \subseteq E_0$ .

Suppose that $E_1 \subseteq E_0$ , we show that $E_1$ is an initial segment of $E_0$ . Let $\alpha \in E_0$ and $\alpha \leq \max {E_1}$ . If $\alpha =0$ then $\alpha \in E_1$ otherwise pick $\beta \in E_1$ with $\beta $ maximal so that $\beta < \alpha $ . Notice that $\beta $ is not maximal in $E_1$ . As both $E_0$ and $E_1$ are $\eta $ -pseudo-arithmetic $S_{E_1}(\beta )\leq \alpha $ but $S_{E_1}(\beta )<\alpha $ violates the maximality of $\beta $ and hence $S_{E_1}(\beta )=\alpha $ and so $\alpha \in E_1$ . So $E_1$ is an initial segment of $E_0$ .

As an immediate consequence of Lemma 3.38 we have:

Lemma 3.43. If $E_1$ is a definable $\eta _1$ -pseudo-arithmetic set and $E_2$ is a definable $\eta _2$ -pseudo-arithmetic set then $\eta _1$ and $\eta _2$ are Archimedean equivalent.

Lemma 3.44. Suppose that $E_1$ is a definable $\eta _1$ -pseudo-arithmetic set and $E_2$ is a definable $\eta _2$ -pseudo-arithmetic set then there is $q \in \mathbb{Q} $ so that $\eta _2=q\eta _1$ .

Proof. For each $E_i$ at least one of $E_i \cap [0, \infty )$ or $E_i \cap (-\infty , 0]$ is $\eta _i$ -pseudo-arithmetic, hence we may assume that for each i either $E_i \subseteq R^{\geq 0}$ or $E_i \subseteq R^{\leq 0}$ . By Lemma 3.26 we may without loss of generality assume that $0 \in E_i$ and $E_i \subseteq R^{\geq 0}$ for $i \in \{1,2\}$ . Also by Lemma 3.43 $\eta _1$ and $\eta _2$ are Archimedean equivalent. Notice that the first $\omega $ many elements of $E_i$ are of the form $n \eta _i$ for $n \in \mathbb {N}$ . If $n\eta _1=m\eta _2$ for some $m,n \in \mathbb {N}^{>0}$ then we are done. Let $F=E_1 \cup E_2$ , which is also discrete. As $\eta _1$ and $\eta _2$ are Archimedean equivalent it must be the case that for infinitely many $n_i \in \mathbb {N}$ that the successor of $m_i \eta _1$ in F is $n_i \eta _2$ for some $m_i, n_i \in \mathbb {N}$ . Also as $F'$ is finite we can find $\gamma \in R$ and infinitely many pairs $(m_i, n_i) \in \mathbb {N}^2$ so that $S_F(m_i\eta _1)=m_i\eta _1+\gamma =n_i\eta _2$ . Thus working with $(m_0,n_0)$ and $(m_1,n_1)$ we have that $m_0\eta _1+\gamma =n_0\eta _2$ and $m_1\eta _1+\gamma =n_1\eta _2$ . Eliminate $\gamma $ and solve for $\eta _2$ to get: $\eta _2=\frac {(m_0-m_1)}{(n_0-n_1)}\eta _1$ as desired.

Theorem 3.45. Let $\mathcal {R}=\langle R; +, <, \dots \rangle $ be a definably complete expansion of a divisible ordered Abelian group of burden $2$ . Let D be a definable infinite discrete set. There is a definable pseudo-arithmetic set $E \subseteq R^{\geq 0}$ with minimal element $0$ so that D is definable in $\langle R; +, <, E\rangle $ .

Proof. By Theorem 3.2 D is a finite union of definable pseudo-arithmetic sets, $D_1 \dots D_n$ . Clearly, D is definable in any structure in which $D_1, \dots , D_n$ are definable. As each $D_i$ is definable in any structure where $D_i \cap (-\infty , 0]$ and $D_i \cap [0, \infty )$ are both definable we may replace each $D_i$ by $D_i \cap (-\infty , 0]$ and $D_i \cap [0, \infty )$ and thus we find pseudo-arithmetic sets $E_1 \dots E_l$ so that for each $1 \leq i \leq l$ either $E_i \subseteq R^{\geq 0}$ or $E_i \subseteq R^{\leq 0}$ and D is definable in $\langle R; +, <, E_1, \dots E_l\rangle $ . Further each $E_i$ is interdefinable with its image under a non-zero $\mathbb{Q} $ -linear map and hence after translating and possibly multiplying by $-1$ we may replace $E_i$ by pseudo-arithmetic sets $F_i$ so that $\min (F_i)=0$ for each i and so that D is definable in $\langle R; +, <, F_1, \dots F_l\rangle $ .

As $F_i$ is interdefinable with $qF_i$ for any $q \in \mathbb{Q} ^{\not =0}$ we may further assume by Lemma 3.44 that all of the $F_i$ are $\eta $ -psuedo-arithmetic for one fixed $\eta $ . By Lemma 3.42 for each i and j either $F_j$ is an initial segment of $F_i$ or vice versa. Thus for some F among the $F_i$ , each $F_i$ is an initial segment of F. Hence each $F_i$ and thus also D is definable in $\langle R; +,<,F\rangle $ .

Notice that it follows from Theorem 3.45 and Lemma 3.44 that we can fix a single $\eta \in R$ so that if D is any discrete set definable in $\mathcal {R}$ then there is an $\eta $ -pseudo-arithmetic set E so that D is definable in $\langle R; +, <, E \rangle $ .

Now we work towards showing that all infinite discrete sets D definable in $\mathcal {R}$ are definable in a model of $\text {Th}(\langle \mathbb{R}; +, <, \mathbb {Z}\rangle )$ . We recall some basic facts about $T_{\mathbb {Z}}=\text {Th}(\langle \mathbb{R}; +, <, \mathbb {Z}\rangle )$ .

Fact 3.46.

1. (1) [13] The complete theory of the structure

   $$\begin{align*}\langle \mathbb{R}; +, <, 0, 1, \lfloor \,\, \rfloor, \lambda \, : \, \lambda \in \mathbb{Q} \rangle\end{align*}$$
   has quantifier elimination, where $0$ and $1$ are constants, $\lfloor x \rfloor $ is the unary “floor” function giving the greatest integer less than or equal to x, and $\lambda $ denotes the unary function sending x to $\lambda \cdot x$ . Notice that this structure has the same definable sets as $\langle \mathbb{R}; +, <, \mathbb{Z} \rangle $ and is definably complete. Furthermore in this language the structure is universally axiomatizable and hence all definable functions are given piecewise by terms.

2. (2) [3, Section 3.1] The theory $T_{\mathbb{Z} }$ has dp-rank $2$ .

We work towards identifying a discrete subgroup of $\mathcal {R}$ which will act as our copy of “ $\mathbb{Z} $ .”

Lemma 3.47. Suppose that $E \subseteq R$ is a definable $\eta $ -pseudo-arithmetic set with smallest element $0$ . Let $\mathcal {H}$ be the convex hull of E.

1. (1) If $a,b \in E$ and $a+b \in \mathcal {H}$ , then $a+b \in E$ .

2. (2) If $a, b \in E$ and $a\leq b$ , then $b-a \in E$ .

Proof. (1): Suppose this fails. Let $a \in E$ be least so that there is $b \in E$ with $a+b \in \mathcal {H}$ but $a+b \notin E$ . Notice that $0<a$ , and let $a^*$ be the predecessor of a in E. Then $a^*+b \in \mathcal {H}$ so $a^*+b \in E$ . Also $a^*+b$ cannot be maximal in E as $a^*+b<a+b$ and $a+b$ is in the convex hull of E. Thus $a^*+b+\eta \in E$ . But $a^*+b+\eta =a+b$ , a contradiction.

(2) Suppose this fails. Let $a \in E$ be minimal so that $b-a \notin E$ for some $b \in E$ with $b\geq a$ . Notice that $a>0$ , and if $a^* = S_E^{-1}(a)$ , we must have that $b-a^* \in E$ . Also $b-a^*>0$ and thus $b-a^*-\eta \in E$ , but $b-a^*-\eta = b-a$ , a contradiction.

Definition 3.48. Let $\eta \in R^{>0}$ . A subgroup $G \subseteq R$ is $\eta $ -integer-like if G is a discrete subgroup of R, $\eta $ is the smallest positive element of G, and for any $a \in R$ in the convex hull of G there is $b \in G$ with $b \leq a \leq b+\eta $ . G is integer-like if it is $\eta $ -integer-like for some $\eta $ .

If a definable, discrete, $\eta $ -pseudo-arithmetic set $E \subseteq R^{\geq 0}$ is unbounded and has minimal element $0$ then by Lemma 3.47 $E \cup -E$ is an $\eta $ -integer-like subgroup of R. Furthermore if F is any other definable $\eta $ -pseudo-arithmetic set with smallest element $0$ then F is an initial segment of E by Lemma 3.42. We aim to show that in general there is an unbounded $\eta $ -integer-like subgroup $G \subseteq R$ so that for all E, an $\eta $ -pseudo-arithmetic set with smallest element $0$ , E is an initial segment of $G^{\geq 0}$ . Of course G will typically not be definable.

Lemma 3.49. Suppose that $\eta \in R$ and there is a definable $\eta $ -pseudo-arithmetic set. Then there is an unbounded $\eta $ -integer-like subgroup, G, so that for all $\eta $ -pseudo-arithmetic definable sets E with smallest element $0$ , E an initial segment of $G^{\geq 0}$ .

Proof. First suppose there is a definable unbounded $\eta $ -pseudo-arithmetic set E. By Lemma 3.26(1) we may translate E to assume $0 \in E$ . Then by Lemma 3.47 $(E \cap [0, \infty )) \cup -(E \cap [0, \infty ))$ is the desired group. Also notice that by Lemma 3.42 $(E \cap [0, \infty ) \cup -(E \cap [0,\infty ))$ must be the unique subgroup with the desired properties. Hence we assume that any definable $\eta $ -pseudo-arithmetic set is bounded. Again by Lemma 3.26 if there is a definable $\eta $ -pseudo-arithmetic set then there is one with least element $0$ .

Let

$$\begin{align*}F_0=\bigcup\{E : E \text{ definable, } \eta\text{-pseudo-arithmetic, and}\min(E)=0\}.\end{align*}$$

Note that by Lemma 3.42 $F_0=\bigcup _{i \in \alpha } E_i$ where $\alpha $ is an ordinal, each $E_i$ is definable and $\eta $ -pseudo-arithmetic with minimal element $0$ , and if $i<j \in \alpha $ then $E_i$ is an initial segment of $ E_j$ . Furthermore, again by Lemma 3.42 if E is any definable $\eta $ -pseudo-arithmetic set then E is an initial segment of $F_0$ .

We claim that if $x,y \in F_0$ then $x+y \in F_0$ . Pick i so that $x,y \in E_i$ by Lemma 3.47 $x+y \in E_i \cup (E_i+c)$ where $c=\max {E_i}$ . Note that c exists as $E_i$ is bounded by assumption and also that $E_i \cup (E_i+c)$ is again $\eta $ -pseudo-arithmetic. But $E_i \cup (E_i+c) \subseteq F_0$ . Similarly if $x,y \in F_0$ and $x<y$ then $y-x \in F_0$ . Thus $F=F_0 \cup -F_0$ is a subgroup of R. We claim that F is $\eta $ -integer-like. To show that F is discrete is suffices to show if $f_1<f_2 \in F_0$ then $f_2-f_1 \geq \eta $ . But this is immediate as $f_1, f_2 \in E_i$ for some $i \in \alpha $ and $E_i$ is an initial segment of $F_0$ by Lemma 3.42. Also clearly $\eta $ is the smallest positive element of F as each $E_i$ is $\eta $ -pseudo-arithmetic. Finally suppose that u is in the convex hull of F and first assume that $u\geq 0$ . Then u is in the convex hull of $E_i$ for some $i \in \alpha $ . Let $b=\max \{e \in E_i : e \leq u\}$ , then b is an element of F so that $b \leq u \leq b+\eta $ . If $u<0$ , find $b \in F$ so that $b\leq -u\leq b+\eta $ , then $-(b+\eta ) \in F$ is so that $-(b+\eta ) \leq u \leq -(b+\eta )+\eta $ .

If F is unbounded we are done. Otherwise let U be the convex hull of F in R. As F is a subgroup of R it follows that U is a rational vector subspace of R. Let H be the subspace of R so that $R=U\oplus H$ as rational vector spaces. Then H is a discrete subset of R since if $h_1<h_2 \in H$ and $h_2-h_1<u$ for some non-zero $u \in U$ then, as U is convex, $h_2-h_1=v$ for some non-zero $v \in U$ which is impossible. Also H is clearly unbounded in R.

Finally let $G=F+H$ . Clearly G is an unbounded subgroup of R. We need to verify that G is $\eta $ -integer-like. Let $f+h \in G$ and note that $(f+\eta )+h \in G$ as F has minimal element $\eta $ . We claim there is no $f'+h' \in G$ so that $f+h<f'+h'<(f+\eta )+h$ . If $h=h'$ then it must be the case that $f'>f$ but we must also have $f'-f<\eta $ which is impossible. Thus $h \not = h'$ , but then $(f'+h')-(f+h) \notin U$ (since otherwise $h'-h \in U$ ) and so $(f'+h')-(f+h)>\eta $ which is also impossible. Hence G is a discrete group and $\eta $ must be the smallest element of G. Now suppose that $a \in R$ . Write $a=u+h$ where $u \in U$ and $h \in H$ . As F is $\eta $ -integer-like there is $b \in F$ so that $b \leq u \leq b+\eta $ but then $b+h \in G$ is so that $b+h \leq u+h \leq b+\eta +h$ .

By construction if E is any definable $\eta $ -pseudo-arithmetic subset of R with minimal element $0$ then $E $ is an initial segment of $F^{\geq 0}$ and hence of $G^{\geq 0}$ .

Now we may provide a proof of Theorem 1.3.

Proof. By Lemma 3.44 we find $\eta \in R$ so that if $F\subseteq R$ is any pseudo-arithmetic set then there is $q \in \mathbb{Q} $ so that $qF$ is $\eta $ -pseudo-arithmetic. Fix such an $\eta $ . For any infinite definable discrete set D, by Theorem 3.45 there is a definable pseudo-arithmetic set $E(D)\subseteq R^{\geq 0}$ with minimal element $0$ so that D is definable in $\langle R; +, <, E(D)\rangle $ . By our choice of $\eta $ we may assume that all such $E(D)$ are $\eta $ -pseudo-arithmetic. As we assume that there is a definable infinite discrete subset of R then there is a definable $\eta $ -pseudo-arithmetic set. By Lemma 3.49 there is an unbounded $\eta $ -integer-like group G so that $E(D)$ is an initial segment of $G^{\geq 0}$ for every infinite definable discrete set D. Notice that all such $E(D)$ (and hence all D) are definable in $\langle R; +, <, G\rangle $ . Finally by the Appendix of [13] $\langle R; +, <, G\rangle $ is a model of $T_{\mathbb {Z}}$ .

For the “furthermore” we show that under the additional assumption that $\mathcal {R}$ is of dp-rank $2$ there is $G \subseteq R$ an integer-like subgroup so that all $\mathcal {R}$ -definable $X \subseteq R$ are definable in $\langle R; +, <, G \rangle $ . Thus suppose that $\mathcal {R}$ is of dp-rank $2$ . By [4, Corollary 2.10] any set definable in $\mathcal {R}$ is either discrete or has interior. By the first part of the theorem we may fix $G \subseteq R$ an integer-like subgroup so that all $\mathcal {R}$ -definable discrete subsets $D \subset R$ are definable in $\langle R; +, < G \rangle $ . It suffices to show that any open set definable in $\mathcal {R}$ is definable in $\langle R; +, < , G\rangle $ . Thus let U be an open $\mathcal {R}$ -definable subset of R and without loss of generality assume that $U \not = R$ . As $\mathcal {R}$ is definably complete, U is a disjoint union of open intervals. Let $D_0$ be the set of all left endpoints of open intervals in U and let $D_1$ be the set of all right endpoints of intervals in U. Note that $D_0$ and $D_1$ are definable in $\mathcal {R}$ and as we are assuming that $U \not =R$ at least one of $D_0$ or $D_1$ is non-empty. The sets $D_0$ and $D_1$ are discrete and definable in $\mathcal {R}$ and hence also definable in $\langle R; +, <, G \rangle $ .

Thus U may be defined in $\langle R; +, <, G \rangle $ as:

$$\begin{align*}\{x \in R : \exists d_0 \in D_0 \exists d_1 \in D_1(d_0<x<d_1 \wedge (d_0, d_1) \cap (D_0 \cup D_1)=\emptyset)\}\end{align*}$$

$$\begin{align*}\cup \{x \in R : \exists d_1 \in D_1 ( x<d_1 \wedge (-\infty, d_1) \cap (D_0 \cup D_1)=\emptyset)\}\end{align*}$$

$$\begin{align*}\cup \{x \in R: \exists d_0 \in D_0(d_0<x \wedge (d_0, \infty) \cap (D_0 \cup D_1)=\emptyset)\}.\\[-33pt]\end{align*}$$

At this stage we provide a more detailed description of the definable subsets of R by simply developing a precise description of the definable subsets in models of $T_{\mathbb{Z} }$ . We recall the following definition.

Definition 3.50. A structure $\mathcal {R}=\langle R; <, \dots \rangle $ with $<$ a dense linear ordering without endpoints is called locally o-minimal if for every definable $X \subseteq R$ and every $x \in X$ there is an open interval I with $x \in I$ so that $X \cap I$ is a finite union of points and intervals.

Proposition 3.51. If $\mathcal {M}=\langle M; +, <, Z \rangle \models T_{\mathbb{Z} }$ and $X \subseteq M$ is definable then X is a finite union of sets of the form

• • $\bigcup _{w \in W}\{w+\lambda \}$ where W is definable in the structure $\langle Z; +, < \rangle $ and $\lambda \in [0,1)$ (where $1$ denotes the minimum positive element of Z);or

• • $\bigcup _{w \in W}(w+\lambda _0, w+\lambda _1)$ where W is definable in the structure $\langle Z; +, < \rangle $ , $\lambda _0<\lambda _1$ , and $\lambda _0,\lambda _1 \in [0,1]$ .

Proof. By [3, Lemma 3.3(i)] and compactness there is $N \in \mathbb {N}$ so that if $l \in Z$ then $X \cap (l,l+1)=X_1 \cup \dots \cup X_N$ where each $X_i$ is either empty, a single point, or an open interval, and the $X_i$ are pairwise disjoint. We proceed by induction on N.

By [11, Theorem 19] $T_{\mathbb{Z} }$ is locally o-minimal and as noted in Fact 3.46 it is definably complete. These two facts together imply that if $X \subseteq M$ is definable then X is a union of a closed discrete set and an open set (see [7, Lemma 2.3]). Furthermore by definable completeness any open subset is a union of open intervals.

Thus without loss of generality we may assume that X is either a union of open intervals or closed and discrete. If $Y \subseteq Z$ is definable then Y is definable in $\langle Z; +, < \rangle $ by [3, Lemma 3.3(ii)]. Thus $X \cap Z$ is a set of the first form in the statement of the Lemma and we may without loss of generality assume that $X \cap Z = \emptyset $ .

Suppose that $N=1$ and also that X is open. Thus X consists of at most one open subinterval of $(l,l+1)$ for each $l \in Z$ . Let $X_l$ be the set of left endpoints of intervals in X and let $X_r$ be the right endpoints. Note that $X_l$ and $X_r$ are closed and discrete and thus so is $X_l \cup X_r$ . Let $f: X_l \cup X_r \to [0,1]$ be given by $x \mapsto x-\lfloor x \rfloor $ if $x \in X_l$ or $x \in X_r \setminus Z$ and $x \mapsto 1$ otherwise. As noted in Fact 3.46 $T_{\mathbb{Z} }$ is of dp-rank $2$ and thus is strongly dependent. Hence by [3, Corollary 2.17] in models of $T_{\mathbb{Z} }$ forward images of discrete sets under definable functions must be discrete. Thus $f[X_l \cup X_r] \subseteq [0,1]$ is discrete and so by [3, Lemma 3.3(i)] it is finite.

Let $\xi _1< \dots < \xi _s$ list all the elements of $f[X_l \cup X_r]$ . For $1 \leq i < j \leq s$ let

$$\begin{align*}W_{ij}=\{z \in Z : (z+\xi_i, z+\xi_j) \subseteq X\}.\end{align*}$$

By [3, Lemma 3.3(ii)] $W_{ij}$ is definable in $\langle \mathbb{Z}; +, < \rangle $ . Let

$$\begin{align*}X_{ij}=\{x : \exists z (z \in W_{ij} \wedge z+\xi_i < x < z+\xi_j)\}.\end{align*}$$

Thus $X=\bigcup _{1 \leq i,j \leq s}X_{ij}$ and each $X_{ij}$ is of the second form given in the statement of the proposition.

Now suppose X is discrete. Let $\tilde {X}=\bigcup _{x \in X}(\lfloor x \rfloor ,x)$ , which is a union of open intervals with at most one interval in each $(l, l+1)$ for $l \in Z$ . Thus the previous case applies and $\tilde {X}$ is a finite union of sets $X_i= \bigcup _{w \in W_i}(w+\lambda ^i_0, w+\lambda ^i_1)$ with W definable in $\langle Z; +, < \rangle $ , $\lambda ^i_0<\lambda ^i_1$ , and $\lambda ^i_0, \lambda ^i_1 \in [0,1)$ . (Note that $\lambda _1^i<1$ as $X \cap Z=\emptyset $ .) For each i let $W^{\prime }_i=\{w \in W_i : w+\lambda ^i_1 \in X\}$ , which again is definable in $\langle Z; +, < \rangle $ by [3, Lemma 3.3(ii)]. Then X is the union of $\bigcup _{w \in W^{\prime }_i}\{w + \lambda ^i_1\}$ which are of the first form in the statement of the Lemma.

Now suppose that $N>1$ . Let

$$\begin{align*}X_0=\{x \in X : \neg \exists y,z (\lfloor x \rfloor<y<z<x \wedge z \notin X \wedge y \in X)\}.\end{align*}$$

Then $X_0$ is a set so that $(l, l+1) \cap X_0$ consists of at most one point or interval for each $l\in Z$ and so the $N=1$ case applies to $X_0$ . Also $(X \setminus X_0) \cap (l, l+1)$ must consist of at most $N-1$ points or intervals for all $l \in Z$ so the induction hypothesis applies to $X \setminus X_0$ and we are done.

Note that by the cell decomposition result of Cluckers for sets definable in models of the theory of $\langle \mathbb{Z}; +, < \rangle $ [2], we can describe the sets W in the conclusion of Proposition 3.51 even more explicitly: Each such W is a finite union of points and infinite intervals intersected with a coset of $nZ$ for some $n \in \mathbb{N} $ .

Recall that by [3] $\langle \mathbb{R}; +, <, \mathbb{Z} \rangle $ has dp-rank $2$ and is clearly definably complete. In light of Theorem 1.3 it is reasonable to ask if for any $\mathcal {R}=\langle R; +, <, \dots \rangle $ which is a definably complete and dp-rank $2$ expansion of a divisible ordered Abelian group there is a group G so that $\langle R; +, <, G\rangle \models T_{\mathbb{Z} }$ and $\mathcal {R}$ is a reduct of $\langle R; +, <, G \rangle $ . We give an example to show this is not the case.

To construct our example of a divisible dp-rank $2$ expansion of an OAG with definable completeness which is not simply a reduct of a model of $T_{\mathbb {Z}}$ , we will use the simple product construction as defined in [11], in particular the standard simple product as elaborated by Fujita in [8], whose definition we now recall.

Definition 3.52. (See [8, Definition 2.5])

Suppose that $\mathcal {L}_0$ and $\mathcal {L}_1$ are two disjoint languages with only relation and constant symbols, and we assume that each language contains at least one constant symbol. Further suppose that $\mathcal {M}_0$ and $\mathcal {M}_1$ are structures in the languages $\mathcal {L}_0$ and $\mathcal {L}_1$ respectively. The standard simple product of $\mathcal {M}_0$ and $\mathcal {M}_1$ is the structure $\mathcal {N}$ in a new language $\mathcal {L}_{sim}$ , defined as follows:

1. (1) The universe N of $\mathcal {N}$ is the Cartesian product $M_0 \times M_1$ .

2. (2) For each constant symbol $c_0 \in \mathcal {L}_0$ and each constant symbol $c_1 \in \mathcal {L}_1$ , there is a constant symbol $C_{c_0, c_1} \in \mathcal {L}_{sim}$ , which is interpreted in $\mathcal {N}$ as

   $$ \begin{align*}C_{(c_0, c_1)}^{\mathcal{N}} = (c_0^{\mathcal{M}_0}, c_1^{\mathcal{M}_1}).\end{align*} $$

3. (3) For $k \in \{0, 1\}$ and for each n-ary relation symbol $R \in \mathcal {L}_k$ , there is an identically named relation symbol $R \in \mathcal {L}_{sim}$ . Letting $\pi _k \, : \, N \rightarrow M_0 \times M_1$ be the projection onto the k-th coordinate, we define the interpretation $R^{\mathcal {N}}$ of R in $\mathcal {N}$ as

   $$ \begin{align*}R^{\mathcal{N}} = \{ (a_1, \ldots, a_n) \in N^n \, : \, (\pi_k(a_1), \ldots, \pi_k(a_n)) \in R^{\mathcal{M}_k} \}.\end{align*} $$

4. (4) Finally, $\mathcal {L}_{sim}$ contains two additional binary relation symbols $\sim _0$ and $\sim _1$ interpreted as equality of the corresponding coordinate projections: for each $k \in \{0,1\}$ ,

   $$ \begin{align*}\sim_k^{\mathcal{N}} = \{(a,b) \in N^2 \, : \, \pi_k(a) = \pi_k(b)\}.\end{align*} $$

As shown by Fujita [8], the complete theory of the standard simple product $\mathcal {N}$ can be naturally axiomatized in terms of the complete theories of each $\mathcal {M}_k$ .

Proposition 3.53. ³ If $\mathcal {M}_0$ and $\mathcal {M}_1$ are structures such that $\text {dp-rk}(\mathcal {M}_k) \leq \kappa _k$ for $k \in \{0,1\}$ , then if $\mathcal {N}$ is the standard simple product of $\mathcal {M}_0$ and $\mathcal {M}_1$ ,

$$ \begin{align*}\text{dp-rk}(\mathcal{N}) \leq \kappa_0 + \kappa_1.\end{align*} $$

Proof. We will use the following characterization of dp-rank found in [17, Proposition 4.17] (though the idea goes back to [10]):

Fact 3.54. If $\mathcal {M} \models T$ is sufficiently saturated, $\text {dp-rk}(T) < \kappa $ if and only if for every $b \in M$ and every family of infinite, mutually indiscernible sequences $(I_t \, : \, t \in X)$ , there is some $X' \subseteq X$ such that $|X'| < \kappa $ and the family $(I_t \, : \, t \in X \setminus X')$ is mutually indiscernible over b.

We will apply this criterion to the standard simple product $\mathcal {N}$ . By [8, Theorem 2.8], we may replace our original model $\mathcal {N}$ by a sufficiently saturated extension and the result will still be a standard simple product of models of $\text {Th}(\mathcal {M}_k)$ . Now fix any $b = (b^0, b^1) \in N$ and let $(I_t \, : \, t \in X)$ be mutually indiscernible sequences of finite tuples from N, say $I_t = \{ \overline {a}_{i, t} \, : \, i \in \omega \}$ . Each $\overline {a}_{i,t}$ can be written as $(\overline {a}^0_{i,t}, \overline {a}^1_{i,t})$ where $\overline {a}^k_{i,t}$ is the tuple from $M^k$ obtained by coordinate projection, and let $I^k_t = \{\overline {a}^k_{i,t} \, : \, i \in \omega \}$ . By [8, Lemma 3.4], each family $(I^k_t \, : \, t \in X)$ for $k \in \{0,1\}$ is mutually indiscernible, so by the characterization of dp-rank given in the Fact, there are sets $X^k \subseteq X$ such that $|X^k| < \kappa _k^+$ such that $(I^k_t \, : \, t \in X \setminus X^k)$ are mutually indiscernible over $b^k$ . Hence $|X^k| \leq \kappa _k$ , and thus if $X' = X^0 \cup X^1$ , we have $|X'| \leq \kappa _0 + \kappa _1$ , or equivalently, $|X'| < (\kappa _0 + \kappa _1)^+$ . By [8, Lemma 3.4], we have $(I_t \, : \, t \in X \setminus X')$ are mutually indiscernible over b, so applying the Fact again, we conclude that $\text {dp-rk}(T) < (\kappa _0 + \kappa _1)^+$ , as desired.

Proposition 3.55. Let $\mathcal {R}=\langle \mathbb{R}; +, <, \sin {x} \rangle $ . If $T=\text {Th}(\mathcal {R})$ then T is definably complete and has dp-rank $2$ .

Proof. By [9, Lemma 3.3] the dp-rank of T is at least $2$ as no infinite discrete set can be definable in a dp-minimal expansion of a divisible OAG.

T is definably complete as $\mathcal {R}$ has universe $\mathbb{R} $ . We establish that T has dp-rank $2$ by showing that it may be realized as a reduct of a simple product which we can verify has dp-rank $2$ via Proposition 3.53.

Let $\mathcal {M}_0=\langle \mathbb {Z}; +_{Z}, <_{Z}, 0_{Z}\rangle $ where $+_Z, <_Z,$ and $0_Z$ are just the usual addition, order, and $0$ except that we think of $+_Z$ as a relation. Let $\mathcal {M}_1=\langle [0, 2\pi ); +_s, <_s, \sin _s{x}, E_s, 0_s\rangle $ where $<_s$ and $0_s$ are just the usual order and $0$ , $\sin _s{x}$ is the sine function restricted to $[0, \pi ]$ thought of as a relation, $E_s$ is a binary relation that holds of $a,b$ if and only if $a+b<2\pi $ , and $+_s$ is addition modulo $2\pi $ thought of as a relation. Note that $\mathcal {M}_0$ is quasi-o-minimal with definable bounds (see [1, Example 2 and Remark after Theorem 3]); thus, by [5, Corollary 3.3] $\mathcal {M}_0$ is dp-minimal. By [6, Example 1.6] $\mathcal {M}_1$ is o-minimal, and thus by [5, Corollary 3.3] it is dp-minimal. Let $\mathcal {M}$ be the standard simple product of $\mathcal {M}_0$ and $\mathcal {M}_1$ . Recall that $\mathcal {M}$ has universe $M_0 \times M_1$ .

We think of each point $(n, x) \in M_0 \times M_1$ as representing $2\pi n + x \in \mathbb{R} $ and the operations $\sin _2$ , $+_2$ , as defined below, will correspond to the usual operations of $\sin (\cdot )$ and addition on $\mathbb{R} $ . Set $\sin _2 : M \to M$ to be the $\mathcal {M}$ -definable function given by

$$\begin{align*}\sin_2((n,x))= \begin{cases} (0, \sin{x}), & \text{ if } 0 \leq x \leq \pi, \\ (-1, 2\pi-\sin(x-\pi)), & \text{ if }\pi < x < 2\pi.\end{cases}\end{align*}$$

Similarly $+_2$ be the $\mathcal {M}$ -definable binary operation given by

$$\begin{align*}(m, x) +_2 (n,y)=\begin{cases} (m+n, x+ y), & \text{ if } x+y<2\pi, \\ (m+n+1, x+ y-2\pi), & \text{ if } x+y \geq 2\pi. \end{cases}\end{align*}$$

Note that the relation $E_s$ is used in defining $+_s$ . Also, the lexicographic ordering $<_{lex}$ on $M_0 \times M_1$ is $\mathcal {M}$ -definable.

Notice that $\langle M, +_2, <_{lex}, \sin _2{x}\rangle $ is isomorphic to $\langle \mathbb{R}; +, <, \sin {x} \rangle $ via the map $(n, x) \mapsto 2\pi n+x$ .

By Proposition 3.53, the dp-rank of $\mathcal {M}$ is at most $2$ , and as $\mathcal {R}$ is isomorphic to a reduct of $\mathcal {M}$ we conclude that T has dp-rank $2$ .

Finally we point out that the above example is not a reduct of a model of $T_{\mathbb {Z}}$ .

Proposition 3.56. Let $\mathcal {R}=\langle \mathbb{R}; +, <, \sin {x}\rangle $ . For no $Z \subseteq \mathbb{R} $ with $\mathcal {R}_Z=\langle \mathbb{R}; +, <, Z\rangle \models T_{\mathbb {Z}}$ is $\mathcal {R}$ a reduct of $\mathcal {R}_Z$ .

Proof. Fix $Z \subseteq \mathbb{R} $ so that $\mathcal {R}_Z \models T_{\mathbb {Z}}$ . By the first part of Fact 3.46 and [3, Lemma 3.2] if $(a,b) \subset \mathbb{R} $ is a bounded interval and $f: (a,b) \to \mathbb{R} $ is definable in $\mathcal {R}_Z$ then f is piecewise linear. But clearly $\sin : (0,1) \to \mathbb{R} $ is not piecewise linear; hence, $\mathcal {R}$ is not a reduct of $\mathcal {R}_Z$ .