UNDEFINABILITY OF MULTIPLICATION IN PRESBURGER ARITHMETIC WITH SETS OF POWERS

Abstract

We begin by proving that any Presburger-definable image of one or more sets of powers has zero natural density. Then, by adapting the proof of a dichotomy result on o-minimal structures by Friedman and Miller, we produce a similar dichotomy for expansions of Presburger arithmetic on the integers. Combining these two results, we obtain that the expansion of the ordered group of integers by any number of sets of powers does not define multiplication.

1 Introduction

In this paper, we consider expansions of Presburger arithmetic, the structure $\mathcal {Z} = (\mathbb {Z}, <, +)$ , ¹ by sets of the form $a^{\mathbb {N}} = \{a^i : i \in \mathbb {N}\}$ , where $a \in \mathbb {Z}_{>1}$ .

Expansions of $\mathcal {Z}$ occupy a great many possibilities in terms of tameness. On the one hand, $\mathcal {Z}$ itself is well-understood to be quite tame: it admits effective quantifier elimination upon expansion by the (definable) relations $\equiv _{n}$ of equivalence modulo n for each integer $n> 1$ and thus has a decidable theory, and additionally it satisfies model-theoretic tameness conditions like Shelah’s NIP [13]. On the other hand, the expansion of $\mathcal {Z}$ by the multiplication function, i.e., the ring of integers, ² is sufficiently complex to perform Gödel coding and hence defines any arithmetical set. In a previous paper, Hieronymi and Schulz [9] show that $(\mathbb {Z}, <, +, a_1^{\mathbb {N}}, a_2^{\mathbb {N}})$ does not have a decidable theory provided that $a_1$ and $a_2$ are multiplicatively independent, i.e., their powers are all distinct except in the trivial case $a_1^0 = a_2^0$ . Here we will show that these structures however do not define the multiplication function.

Theorem A. Let $a_1, \dots , a_n \in \mathbb {Z}_{>1}$ . Then $(\mathbb {Z}, <, +, a_1^{\mathbb {N}}, \dots , a_n^{\mathbb {N}})$ does not define multiplication.

Theorem A has been open since 1996; it is part of Question 9 in [10]. The context behind the consideration of this particular class of structures deserves several paragraphs of explanation, as Theorem A is only the latest in a long trail of results about the arithmetic of sets of powers in $\mathbb {Z}$ . We note that without the ordering relation, $(\mathbb {Z}, +, a_1^{\mathbb {N}}, \dots , a_n^{\mathbb {N}})$ is superstable of U-rank $\omega $ , as shown by Conant [5]; hence, without $<$ there can be no definition of multiplication. Conant’s methods, however, do not readily transfer to the case where ordering is included. The introduction of $<$ instead places us within the realm of k-automatic expansions of $\mathcal {Z}$ , which usually do not satisfy NIP or NTP $_2$ as defined in [13] but may still enjoy decidable theories.

A k-automatic set (of arity $d \in \mathbb {N}$ ) is a subset of $\mathbb {Z}^d$ whose base-k representations form a regular language. ³ It is shown by Bruyère et al. [2] that a set is k-automatic if and only if it is definable in $\mathcal {Z}_k = (\mathbb {Z}, <, +, V_k)$ , where $V_k : \mathbb {Z} \to k^{\mathbb {N}}$ maps n to the largest power of k dividing n, or $0$ if $n = 0$ . The expansion $\mathcal {Z}_k$ is known as Büchi arithmetic. Moreover, it is shown by Bès [1] that if $S \subseteq \mathbb {Z}^d$ is a k-automatic set not definable in $\mathcal {Z}$ , then $(\mathbb {Z}, <, +, S)$ defines the set $k^{\mathbb {N}}$ . This set is not definable in $\mathcal {Z}$ , ⁴ so these results taken together establish the status of $V_k$ as a “maximal” k-automatic set and $k^{\mathbb {N}}$ as a “minimal” (non-Presburger-definable) k-automatic set.

By Büchi’s theorem, the theory of $\mathcal {Z}_k$ is decidable. Hence, so is the theory of any expansion of $\mathcal {Z}$ by k-automatic sets for a fixed k. Let $a_1, a_2 \in \mathbb {Z}_{>1}$ be multiplicatively independent. A natural next step is then to examine the properties of $(\mathbb {Z}, <, +, S_{a_1}, S_{a_2})$ where $S_{a_i}$ for $i = 1, 2$ is an $a_i$ -automatic set not definable in $\mathcal {Z}$ . The first major result in this direction is the Cobham–Semënov theorem, which states that this expansion is always nontrivial, i.e., it is never the case that $S_{a_2}$ is definable in $\mathcal {Z}_{a_1}$ . This was proven by Cobham [4] for the case where $S_{a_1}, S_{a_2} \subseteq \mathbb {N}$ and extended to the more general case $S_{a_1}, S_{a_2} \subseteq \mathbb {N}^d$ by Semënov [12].

It is also known that the theory of $(\mathbb {Z}, <, +, S_{a_1}, S_{a_2})$ is never decidable. For the case $S_{a_1} = V_{a_1}, S_{a_2} = V_{a_2}$ this was proven by Villemaire [14], and the more general case where $S_{a_1} = V_{a_1}$ was shown by Bès [1]. Both of these authors also show that in the respective cases, the resulting structure defines the multiplication function on $\mathbb {N}$ and hence cannot have a decidable theory. However, in [9], multiplication is not shown to be definable in $(\mathbb {Z}, <, +, S_{a_1}, S_{a_2})$ . Theorem A thus demonstrates that a departure from Villemaire and Bès’ method is required for the most general result by exhibiting for the first time a structure, namely $(\mathbb {Z}, <, +, a_1^{\mathbb {N}}, a_2^{\mathbb {N}})$ , that defines non-Presburger $a_1$ -automatic and $a_2$ -automatic sets and has an undecidable theory but does not define the multiplication on $\mathbb {Z}$ . We will leave mostly open the question of intermediate expansions, i.e., of characterizing for precisely which $S_{a_1}, S_{a_2}$ the structure $(\mathbb {Z}, <, +, S_{a_1}, S_{a_2})$ defines multiplication, for future work.

Theorem A follows from the conjunction of two new results, one number-theoretic and one model-theoretic. The first is an application of a proposition of Schlickewei and Schmidt [11]. Its full statement is quite technical, so we will defer discussion of the exact proposition until Section 3, but in essence it provides a bound for solutions to a particular form of equation involving a finitely generated multiplicative subgroup of a number field that lie outside one of a finite number of hyperplanes. We are able to use this result by noting that $a_1^{\mathbb {N}} \cup \dots \cup a_n^{\mathbb {N}}$ is a subset of such a subgroup, namely the subgroup whose generators are $\{a_1, \dots , a_n\}$ . From that, we derive:

Theorem B. Let $E = \bigcup _i a_i^{\mathbb {N}}$ , where $a_i \in \mathbb {Z}_{>1}$ for $1 \leq i \leq n$ , and let $f : \mathbb {Z}^M \to \mathbb {Z}$ be a Presburger-definable function. Then $f(E^M)$ has zero natural density.

In order to utilize Theorem B, we build on previous work by Friedman and Miller [6]. There, they prove that when we add a predicate to the signature of an o-minimal expansion $\mathcal {R}$ of the ordered real additive group, representing a set E such that the image of E under any function definable in $\mathcal {R}$ has a small closure, then every set definable in the resulting structure either has interior or is small. Here “small” can refer to any of several sparseness conditions on subsets of the real line: nowhere dense, Lebesgue-null, etc. In this paper, we produce a corresponding result for expansions of the ordered group of integers. Here, by $(\mathbb {Z}, <, +, E)^\#$ , we mean $(\mathbb {Z}, <, +, (S))$ where S ranges over all subsets of powers of E.

Theorem C. Let $\mathcal {I}$ be any set-theoretic ideal on $\mathbb {Z}$ . Let $E \subseteq \mathbb {Z}$ be such that, for every $M \in \mathbb {N}$ and $h : \mathbb {Z}^M \to \mathbb {Z}$ Presburger-definable, the image $h(E^M)$ is in $\mathcal {I}$ . Then every subset of $\mathbb {Z}$ definable in $(\mathbb {Z}, <, +, E)^\#$ either contains arbitrarily long pieces of some arithmetic progression or lies in $\mathcal {I}$ .

Theorem C is a significant result in its own right, and it merits elaboration. Here “ $S \subseteq \mathbb {Z}$ contains arbitrarily long pieces of some arithmetic progression” means that there exists $N \in \mathbb {Z}^+$ such that for any $\ell \in \mathbb {Z}^+$ , there exist elements $n_1, \dots , n_\ell $ of S such that $n_i = n_1 + (i-1)N$ for all $1 \leq i \leq \ell $ . This condition is a simultaneous strengthening of two more common largeness conditions used in number-theoretic literature. In particular, a set S satisfying the above contains arbitrarily long arithmetic progressions, and it is piecewise syndetic. We additionally note that our “arbitrarily long pieces of some arithmetic progression” condition is equivalent to stating that for some $S' \subseteq S$ , there exists a unary affine function $f : \mathbb {Z} \to \mathbb {Z}$ such that $f(S')$ is a thick set (hence, it is also a weakening of thickness).

On the other hand, note that we need not assume much about the particular sparseness condition we wish to use; any set-theoretic ideal on $\mathbb {Z}$ will do. We need only assume that subsets and finite unions of sparse sets are sparse. The obvious choice is to use zero natural density, but there are other useful notions of sparseness that give rise to the same dichotomy. The reason we are able to give such a general statement instead of listing specific sparseness conditions as Friedman and Miller did has to do with the fact that in the discrete setting, we have no reason to take the topological closure of the image of E.

Theorem C has broader applications within the model theory of expansions of Presburger arithmetic, but within our paper its application will be in proving Theorem A. We will thus state here the proof of Theorem A using Theorems B and C, with the rest of the paper devoted to proving Theorems B and C.

Proof of Theorem A

Let $E = a_1^{\mathbb {N}} \cup \dots \cup a_n^{\mathbb {N}}$ . By Theorem B, the image of $E^M$ under any Presburger function h has zero natural density. Let $\mathcal {I}$ be the collection of sets of zero natural density; this is a set-theoretic ideal. Thus, we may apply Theorem C and conclude that every subset of $\mathbb {Z}$ definable in $(\mathbb {Z}, <, +, E)^\#$ either contains arbitrarily long pieces of some arithmetic progression or has zero natural density. Note that $(\mathbb {Z}, <, +, E)^\#$ defines the sets $a_i^{\mathbb {N}}$ for $1 \leq i \leq n$ . Then it suffices to show that $(\mathbb {Z}, <, +, \cdot )$ defines some set that does not contain arbitrarily long pieces of any arithmetic progression yet has positive natural density.

Let $S \subseteq \mathbb {Z}$ contain arbitrarily long pieces of the same arithmetic progression; then as mentioned previously, S is piecewise syndetic. Thus it suffices to give an example of a subset of $\mathbb {Z}$ (or $\mathbb {N}$ ) that is arithmetical and has positive natural density but is not piecewise syndetic. The squarefree integers form such a set: it is not piecewise syndetic (folklore), its natural density is $\frac {6}{\pi ^2}$ by a famous 1885 theorem of Gegenbauer [8], and it is defined by the formula $\neg \exists y, z : 1 < y \wedge y \cdot y \cdot z = x$ .

2 Preliminaries

Throughout, $\mathbb {N}$ denotes the natural numbers, which by our convention comprise all nonnegative integers including zero. “Defines” refers to definability by a first-order formula without parameters, although note that this makes little difference in our scope; in the structures we will consider, any constant is definable. We denote the cardinality of set A by $|A|$ .

One of our main results uses the concept of the natural density of a subset of $\mathbb {Z}$ . Natural density is typically defined for subsets of $\mathbb {N}$ , so it is worth explaining our definition:

Definition 2.1. The upper natural density of a subset $A \subseteq \mathbb {Z}$ is the limit superior:

$$ \begin{align*} \limsup_{n \to \infty} \frac{|A \cap \{-n, -n+1, \dots, n-1, n\}|}{2n + 1}. \end{align*} $$

The lower natural density of A is the limit inferior:

$$ \begin{align*} \liminf_{n \to \infty} \frac{|A \cap \{-n, -n+1, \dots, n-1, n\}|}{2n + 1}. \end{align*} $$

If these two expressions are equal, we refer to both as simply the natural density of A, denoted $d(A)$ .

Note that for many $A \subseteq \mathbb {N}$ , the natural density of A as a subset of $\mathbb {N}$ is not equal to its natural density as a subset of $\mathbb {Z}$ ; rather, in general, the natural density of such an $A \subseteq \mathbb {N}$ is equal to the natural density of $A\, \cup\, {-}A$ as a subset of $\mathbb {Z}$ . This choice of convention is so that the natural density on $\mathbb {Z}$ may act as a finitely additive probability measure. We thus check that the appropriate properties are satisfied, as well as some other convenient properties.

Lemma 2.2. Let $A, B, C \subseteq \mathbb {Z}$ . Then all of the following hold:

1. (i) $d(\varnothing ) = 0$ .

2. (ii) $d(\mathbb {Z}) = 1$ .

3. (iii) Let $A, B$ be disjoint, with $C = A \cup B$ . If any two of $A, B, C$ have a natural density, so does the remaining set, and $d(A) + d(B) = d(C)$ .

4. (iv) If $d(A) = 0$ and $B \subseteq A$ , then $d(B) = 0$ .

5. (v) If $d(A)$ exists, then for all $k \in \mathbb {Z}$ , $d(A + k) = d(A)$ , where $A + k = \{a + k : a \in A\}$ .

6. (vi) If $d(A)$ exists, then for all $0 \neq k \in \mathbb {Z}$ , $d(kA) = \frac {d(A)}{k}$ , where $kA = \{ka : a \in A\}$ .

7. (vii) If A is Presburger-definable, then $d(A)$ exists.

8. (viii) For $k> 1$ , $d(k^{\mathbb {N}}) = 0$ .

Proofs of these results are elementary and not qualitatively different from the corresponding proofs over $\mathbb {N}$ . As such, they have been omitted.

We will make key use of a result of Schlickewei and Schmidt [11], so we use some of their notational conventions in algebraic number theory. In particular, we will let $\ast $ denote the elementwise product of two tuples, i.e., $(x_1, \dots , x_n) \ast (y_1, \dots , y_n) = (x_1 y_1, \dots , x_n y_n)$ .

Schlickewei and Schmidt make key use of a height function for tuples of numbers in an arbitrary number field. In this paper our only number field is $\mathbb {Q}$ , so we will define the absolute and logarithmic height for $\mathbb {Q}$ only:

Definition 2.3. Let $x = (\frac {a_1}{b}, \dots , \frac {a_n}{b}) \in \mathbb {Q}^n$ be a tuple of rational numbers such that $a_1, \dots , a_n, b \in \mathbb {Z}$ , with $b> 0$ and $\gcd (a_1, \dots , a_n, b) = 1$ . Then the absolute multiplicative height H is given by $H(x) = \max \{|a_1|, \dots , |a_n|, b\}$ . The logarithmic height $h(x)$ is equal to $\log H(x)$ .

3 A sparseness result on sets of powers

We begin by recalling (viii) in Lemma 2.2, namely that for any $k \in \mathbb {Z}_{>1}$ , we have $d(k^{\mathbb {N}}) = 0$ . Moreover, (v), (vi), and (iii) give us that if we shift, scale, or take the union of multiple such sets, respectively, the result will still have zero natural density. The goal of this section is to extend this result to general Presburger-definable images of unions of sets of powers.

Note that this property is nontrivial; in fact, a set may be very sparse indeed yet have a Presburger-definable image that is all of $\mathbb {Z}$ . One example: consider the set S containing, for each $i \in \mathbb {N}$ , the numbers $10^{10^i}$ and $10^{10^i} + i$ . Clearly S has zero natural density, and hence the observations of the previous paragraph also apply to S. But the Minkowski difference $S - S$ , i.e., the image of $S^2$ under the function $(x, y) \mapsto x - y$ , contains every integer and hence has natural density $1$ . To state that any Presburger-definable image of a set has zero density is a strictly stronger sparseness condition. The remainder of this section will be focused on proving that unions of sets of powers satisfy this sparseness condition.

We will use the following, which is Proposition A of [11] as applied to the rational case:

Proposition 3.1. Let $\Gamma \subseteq (\mathbb {Q^*})^n$ be the subgroup of elements of $(\mathbb {Q^*})^n$ where each component is a power of the corresponding $a_i$ . Then the set of all points $y = x \ast z \in \mathbb {Q}^n$ with $x \in \Gamma $ , $z \in \mathbb {Q}^n$ , $y \cdot (1, \dots , 1) = 1$ , and $H(z)^{4n^2} \leq H(x)$ is contained in the union of not more than $2^{30n^2} (32n^2)^n$ proper linear subspaces of $\mathbb {Q}^n$ .

Using this proposition, we will now prove the following number-theoretic result:

Lemma 3.2. Let $k_1, \dots , k_n$ be nonzero rational numbers, and let $a_1, \dots , a_n \in \mathbb {Z}_{>1}$ . Then the set C of integers c for which there exist $e_1, \dots , e_n \in \mathbb {N}$ satisfying:

(1) $$ \begin{align} k_1 a_1^{e_1} + \dots + k_n a_n^{e_n} = c \end{align} $$

has zero natural density.

Proof We will prove this claim via strong induction; first, assume $n = 1$ . Then C is simply the set $\{k_1 a_1^e : e \in \mathbb {Z}, e \geq 0\}$ , which clearly has zero natural density. For the remainder of this proof we then assume $n> 1$ and assume the lemma is true with n replaced by any smaller positive integer.

Let S be the set of all tuples $(x, c)$ such that x is of the form $(a_1^{e_1}, \dots , a_n^{e_n})$ for $e_1, \dots , e_n \in \mathbb {N}$ and such that (1) holds. For $S' \subseteq S$ we write $\pi (S')$ for the projection of $S'$ onto the last coordinate, which is a subset of $\mathbb {Z}$ ; in particular, $\pi (S) = C$ . We will cover S by subsets and show that the projection of each subset has upper natural density zero.

In particular, let $S_1$ be the set of pairs $(x, c) \in S$ such that $H((\frac {k_1}{c}, \dots , \frac {k_n}{c}))^{4n^2} \leq H(x)$ , and let $S_2 = S \setminus S_1$ . Proposition 3.1 gives us that there exist finitely many proper linear subspaces of $\mathbb {Q}^n$ such that for each $(x, c) \in S_1$ , $x \ast (\frac {k_1}{c}, \dots , \frac {k_n}{c})$ lies in one of these subspaces. For each such subspace P we let $S_P$ denote the subset containing $(x, c) \in S_1$ such that $x \ast (\frac {k_1}{c}, \dots , \frac {k_n}{c}) \in P$ .

Fix some P. Then there exists a nontrivial linear dependence that all points in P satisfy; i.e., there exists a nonzero vector $d = (d_1, \dots , d_n)$ such that for all $p \in P$ we have $d \cdot p = 0$ . For each $(x, c) \in S_P$ we thus have that:

(2) $$ \begin{align} d_1 \frac{k_1}{c} a_1^{e_1} + \dots + d_n \frac{k_n}{c} a_n^{e_n} = 0. \end{align} $$

Without loss of generality (reordering coordinates), we now assume $d_n \neq 0$ . Letting $k^{\prime }_i = k_i - \frac {d_i k_i}{d_n}$ gives us:

(3) $$ \begin{align} k^{\prime}_1 a_1^{e_1} + \dots + k^{\prime}_{n-1} a_{n-1}^{e_{n-1}} = c. \end{align} $$

If any $k^{\prime }_i$ equals zero, that term may be disregarded; (3) then either simplifies to $0 = c$ (in which case there are no solutions) or else satisfies the conditions of the lemma for fewer terms than n, allowing us to apply the inductive hypothesis and conclude that $\pi (S_P)$ has zero natural density. Because $\pi (S_1)$ is a finite union of $\pi (S_P)$ , $\pi (S_1)$ also has zero natural density.

We now consider $S_2$ and let $h \in \mathbb {Z}^+$ ; assume $h> \max a_i$ . Let b be the smallest positive integer such that $k_1 b, \dots , k_n b$ are all integers, let $m = \max \{|k_1|, \dots , |k_n|\}$ , and let $S_h \subseteq S_2$ contain only those $(x, c)$ where $h \geq |c|> m$ .

Let $(x, c) \in S_h$ . Then $\frac {|k_i|}{c}$ is at most $1$ for each i, so $H((\frac {k_1}{c}, \dots , \frac {k_n}{c}))$ is the lowest common denominator of the $\frac {k_i}{c}$ . Because $\frac {bk_i }{bc}$ is a ratio of two integers, we must have that $H((\frac {k_1}{c}, \dots , \frac {k_n}{c})) \mid bc$ , in particular, $H((\frac {k_1}{c}, \dots , \frac {k_n}{c})) \leq |bc|$ . Therefore $|bc|^{4n^2}> H(x)$ , and hence,

(4) $$ \begin{align} (bh)^{4n^2}> H(x). \end{align} $$

Because x has positive integer components, $H(x)$ is the maximum of these components. Then (4) tells us that no component in x exceeds $(bh)^{4n^2}$ .

To summarize, if $(x, c) \in S_h$ , then no component in x can exceed $(bh)^{4n^2}$ . Let N be the number of such x; then by counting and noting that $h> \max a_i$ , we achieve:

$$ \begin{align*} N \leq \prod_{i=1}^n \left\lceil \log_{a_i} (bh)^{4n^2} \right\rceil \leq (5n^2 \log_2 (bh))^n. \end{align*} $$

Now note that by (1), c may be uniquely determined by x, so it follows that $|S_h| \leq (5n^2 \log _2 (bh))^n$ . Therefore $|\pi (S_h)| \leq (5n^2 \log _2 (bh))^n$ as well. Thus,

$$ \begin{align*} & \limsup_{h \to \infty} \frac{|\pi(S_2) \cap \{-h, \dots, h\}|}{2h+1} \\ &= \limsup_{h \to \infty} \frac{|\pi(S_h)|}{2h+1} \\ &\leq \limsup_{h \to \infty} \frac{(5n^2 \log_2 (bh))^n}{2h+1} \\ &= \; 0. \end{align*} $$

We conclude that the upper natural density of $\pi (S_2)$ is zero (it cannot be negative).

Therefore $C = \pi (S) = \pi (S_1) \cup \pi (S_2)$ also has zero natural density, concluding the proof.

This is not difficult to generalize to the condition on Presburger images that is the goal of this section.

Theorem B. Let $E = \bigcup _i a_i^{\mathbb {N}}$ , where $a_i \in \mathbb {Z}_{>1}$ for $1 \leq i \leq n$ , and let $f : \mathbb {Z}^M \to \mathbb {Z}$ be a Presburger-definable function. Then $f(E^M)$ has zero natural density.

Proof By (iii) in Lemma 2.2, it will suffice to cover the image of f by sets of zero natural density.

By Theorem 4.1 of [15], any Presburger-definable f is piecewise linear, in the sense that its domain $E^M$ can be partitioned into finitely many sets such that the restriction of f to each may be written as an affine function with rational coefficients. Thus it suffices to show that the image of $E^M$ under an affine function with rational coefficients has zero natural density, i.e., without loss of generality we may assume f is affine with rational coefficients. In fact, we may further assume that the coefficients are integers and that the constant term is zero, because multiplication or translation by a constant integer does not affect whether the natural density of a set is zero by (v) and (vi) of Lemma 2.2. Lastly, we may assume f actually depends on every argument, as otherwise we may simply treat f as having a lower-dimensional domain.

The only case we need to consider in depth, then, is the case where f is a linear function (with zero constant term) with nonzero integer coefficients. We write $f(x) = k_1 x_1 + \dots + k_M x_M$ (here $x = (x_1, \dots , x_M)$ ). Let $(j_i)_i$ be a sequence of M integers with $1 \leq j_i \leq n$ . We note that there are only finitely many such sequences ( $n^M$ precisely). Then consider the subset S of the domain of f in which $x_i \in (a_{j_i})^{\mathbb {N}}$ for each i. We note that the domain of f, $E^M$ , is the union of these subsets over each sequence $(j_i)_i$ .

It suffices to show that $f(S) = \{k_1 x_1 + \dots + k_M x_M : x \in S\}$ has zero natural density; but this is Lemma 3.2.

4 A dichotomy for certain expansions of Presburger arithmetic

In this section, we aim to adapt a result of [6], in which the authors prove that an expansion of the real ordered group (or any o-minimal expansion thereof) by a set E with sufficiently sparse images gives rise to a dichotomy in the sparseness of its definable sets. Here we will show a similar result for expansions of Presburger arithmetic on the integers. Let $E \subseteq \mathbb {Z}$ .

The approach in [6], which we will largely replicate, is to perform quantifier elimination in a certain infinitary logic by defining a collection of sets $\mathcal {S}_n$ . The Boolean algebra generated by $\mathcal {S}_n$ is called $\mathcal {T}_n$ , and the union of these algebras across all $n \in \mathbb {N}$ is closed under projections, the heart of the quantifier elimination argument. Once this is proven, we note that a dichotomy for $\mathcal {S}_1$ , after quantifiers are eliminated, gives rise to a corresponding dichotomy for all sets definable in $(\mathbb {Z}, <, +, E)$ , the main theorem of this section.

Because our approach is largely similar to that of [6], we will not waste too much time rehashing their approach and will mainly discuss the parts in which our proofs differ. Our approach deviates from theirs in two places. One, as our result is over $\mathbb {Z}$ instead of an o-minimal structure, we need to use the cell decomposition over Presburger arithmetic given in [3]. Two, the proof of one lemma is significantly different due to the discrete setting.

The collections $\mathcal {S}_n$ and $\mathcal {T}_n$ , as in [6], are defined to satisfy four simultaneous claims, from which Theorem C will follow:

1. 1. $\mathcal {T}_n$ is a Boolean algebra.

2. 2. Every element of $\mathcal {T}_n$ is a finite union of elements of $\mathcal {S}_n$ .

3. 3. The projection of a set in $\mathcal {S}_{n+1}$ onto the first n coordinates is a set in $\mathcal {T}_n$ .

4. 4. Suppose that $A \in \mathcal {S}_{1}$ does not contain arbitrarily long pieces of the same arithmetic progression. Then there exist M and $h : \mathbb {Z}^{M} \to \mathbb {Z}$ Presburger such that $A \subseteq h(E^M)$ .

We will first define some notation previously used in [6]. For $X \subseteq \mathbb {Z}^{m+n}$ and $u \in \mathbb {Z}^m$ , we let $X_u$ denote the fiber $\{x \in \mathbb {Z}^n : (u, x) \in X\}$ . We will also make use of the diamond product of two sets of integers:

Definition 4.1. Given $A \subseteq \mathbb {Z}^l \times \mathbb {Z}^n$ and $B \subseteq \mathbb {Z}^m \times \mathbb {Z}^n$ , we let

$$ \begin{align*} A \diamond B = \{(x, y, z) \in \mathbb{Z}^{l+m+n} : (x, z) \in A \wedge (y, z) \in B\}.\end{align*} $$

Let $u \in \mathbb {Z}^{l+n}$ and $v \in \mathbb {Z}^{m+n}$ be such that their last n coordinates agree; then $\langle u, v \rangle $ denotes the tuple $(u_1, \dots , u_l, v) \in \mathbb {Z}^{l+m+n}$ .

Finally, we define a notation for certain expansions of first-order structures on the integers:

Definition 4.2. Given an integer subset $E \subseteq \mathbb {Z}$ , the notation $(\mathbb {Z}, <, +, E)^\#$ denotes $(\mathbb {Z}, <, +, (S))$ , where S ranges over all subsets of $E^k$ for $k \in \mathbb {N}$ .

Now we define $\mathcal {T}_n$ :

Definition 4.3. Given $A \subseteq \mathbb {Z}^n$ , we say $A \in \mathcal {T}_n$ iff there exist $m \in \mathbb {N}$ , $X \subseteq \mathbb {Z}^{m + n}$ Presburger, and an indexed family $(P_\alpha )_{\alpha \in I}$ of subsets of $E^m$ such that $A = \bigcup _{\alpha \in I} \bigcap _{u \in P_\alpha } X_u$ .

Every Presburger subset of $\mathbb {Z}^n$ is in $\mathcal {T}_n$ . Moreover, given $m \in \mathbb {N}, P \subseteq E^m,$ and Presburger functions $f_1, \dots , f_m : \mathbb {Z}^n \to \mathbb {Z}$ , the set

$$ \begin{align*} \{x \in \mathbb{Z}^n : (f_1(x), \dots, f_m(x)) \in P\}\end{align*} $$

is in $\mathcal {T}_n$ , because it is the union of all sets of the form

$$ \begin{align*} \{x \in \mathbb{Z}^n : f_1(x) = u_1 \wedge \dots \wedge f_m(x) = u_m\}\end{align*} $$

for $(u_1, \dots , u_m) \in P$ .

Claim 4.4. $\mathcal {T}_n$ is a Boolean algebra.

Proof Analogous to that of [6].

We will need the concept of a weak cell in order to construct $\mathcal {S}_n$ . This concept was introduced by [6] for the o-minimal case; the conversion to Presburger arithmetic is straightforward.

Definition 4.5. A weak cell in $\mathbb {Z}^{n+1}$ is a set of one of the following forms:

1. (i) $S \times \{t \in \mathbb {Z} : t \equiv k \ \pmod {N}\},$

2. (ii) $\{(x, t) \in \mathbb {Z}^{n+1} : x \in S, f(x) \leq t, t \equiv k \ \pmod {N}\},$

3. (iii) $\{(x, t) \in \mathbb {Z}^{n+1} : x \in S, t \leq g(x), t \equiv k \ \pmod {N}\},$

4. (iv) $\{(x, t) \in \mathbb {Z}^{n+1} : x \in S, f(x) \leq t \leq g(x), t \equiv k \ \pmod {N}\},$

where $S \subseteq \mathbb {Z}^n$ and $f, g : \mathbb {Z}^n \to \mathbb {Z}$ are Presburger and $k, N \in \mathbb {Z}$ .

Lemma 4.6. Let $A, B \subseteq \mathbb {Z}^m \times \mathbb {Z}^{n+1}$ be weak cells. Then $A \diamond B$ is a weak cell in $\mathbb {Z}^{2m+n+1}$ .

Proof As in [6], the proof is elementary and left to the reader.

Now that weak cells have been defined, we define $\mathcal {S}_n$ analogously to $\mathcal {T}_n$ but with the supposition that the Presburger set that gives rise to each member of $\mathcal {S}_n$ be a weak cell.

Definition 4.7. For $A \subseteq \mathbb {Z}^{n+1}$ , $A \in \mathcal {S}_{n+1}$ iff there exist $m \in \mathbb {N}$ , a weak cell $C \subseteq \mathbb {Z}^{m+n+1}$ , and an indexed family $(P_\alpha )_{\alpha \in I}$ of subsets of $E^m$ such that $A = \bigcup _{\alpha \in I} \bigcap _{u \in P_\alpha } C_u$ . (We let $\mathcal {S}_0 = \mathcal {P}(\mathbb {Z}^0)$ .)

We will refer to the sets in $\mathcal {S}_{n+1}$ arising from each of the four different types of weak cell as being of types (i) through (iv) accordingly.

The result that sets in $\mathcal {T}_n$ can be decomposed into sets in $\mathcal {S}_n$ is now trivial but tedious; the main obstacle is to translate a basic syntactic notion into the corresponding set-theoretic statement. This is called Lemma 2 in [6], and for completeness we will state our version:

Lemma 4.8. Let $C_1, \dots , C_{k+1} \subseteq \mathbb {Z}^m \times \mathbb {Z}^n$ , and let $(P_\alpha )_{\alpha \in I}$ be a family of subsets of $\mathbb {Z}^m$ . Then $\bigcup _{\alpha \in I} \bigcap _{u \in P_\alpha } (C_1 \cup \dots \cup C_{k+1})_u$ is equal to the union:

$$ \begin{align*} \bigcup_{\alpha \in I} \bigcap_{u \in P_\alpha} (C_1 \cup \dots \cup C_k)_u\end{align*} $$

$$ \begin{align*} \cup \bigcup_{\alpha \in I} \bigcap_{u \in P_\alpha} (C_{k+1})_u \end{align*} $$

$$ \begin{align*} \cup \bigcup_{\alpha \in I} \bigcup_{P_{\alpha, 1}, P_{\alpha, 2}} \bigcap_{(v, w) \in P_{\alpha, 1} \times P_{\alpha, 2}} ((C_1 \diamond C_{k+1}) \cup \dots \cup (C_k \diamond C_{k+1}))_{(v,w),}\end{align*} $$

where, for $\alpha \in I$ , $\{P_{\alpha , 1}, P_{\alpha , 2}\}$ are the partitions of $P_\alpha $ into two sets.

Proof As mentioned above, the proof is purely a tedious technicality.

We can now establish:

Claim 4.9. Every element of $\mathcal {T}_n$ is a finite union of elements of $\mathcal {S}_n$ .

Proof As in [6], the result follows from Lemmas 4.6 and 4.8 via induction and the cell decomposition of Cluckers given in [3]. Presburger cells in Cluckers’s paper are weak cells by our definition, so any Presburger set may be partitioned into weak cells.

Next, we aim to show the following. Combined with the previous claim, this will show that the collection of finite unions of sets in $\mathcal {S}_n$ is closed under projection:

Claim 4.10. The projection of a set in $\mathcal {S}_{n+1}$ onto the first n coordinates is a set in  $\mathcal {T}_n$ .

Proof This proof is significantly different from the corresponding portion of [6], so we give it in full.

Let $A \in \mathcal {S}_{n+1}$ . Then there exist $m \in \mathbb {N}$ , a weak cell $C \subseteq \mathbb {Z}^{m+n+1}$ , and an indexed family $(P_\alpha )_{\alpha \in I}$ of subsets of $E^m$ such that $A = \bigcup _{\alpha \in I} \bigcap _{u \in P_\alpha } C_u$ . In other words, $x' \in \mathbb {Z}^{n+1}$ is in A if and only if $\exists \alpha \in I : \forall u \in P_\alpha : (u, x') \in C$ . Therefore, $x \in \mathbb {Z}^n$ is in $\pi A$ , the projection of A onto its first n coordinates, when $\exists y \in \mathbb {Z} : \exists \alpha \in I : \forall u \in P_\alpha : (u, x, y) \in C$ .

Our goal is to show that $\pi A$ is in $\mathcal {T}_n$ . To do this, we need to show that $x \in \pi A$ if and only if $\exists \alpha \in I' : \forall u \in P^{\prime }_\alpha : \phi (u, x)$ for some natural number $m'$ , index set $I'$ , indexed collection $(P^{\prime }_\alpha )_{\alpha \in I'}$ of subsets of $E^{m'}$ , and Presburger formula $\phi $ with arity $m' + n$ .

We split into cases based on the type of C (hence of A).

1. (i) In this case, $C = B \times \{t \in \mathbb {Z} : t \equiv k \ \pmod {N}\}$ where $B \subseteq \mathbb {Z}^{m+n}$ is Presburger and $k, N$ are constant integers. Then

   $$ \begin{align*} x \in \pi A \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \\ & \forall u \in P_\alpha : (u, x, y) \in C \wedge y \equiv k \quad\pmod{N}\\ \iff& \exists y \in \mathbb{Z} : \\ & y \equiv k \quad\pmod{N} \wedge \exists \alpha \in I : \forall u \in P_\alpha : (u, x) \in B. \end{align*} $$
   We no longer need to quantify over y, because this modular congruence can always be satisfied:
   $$ \begin{align*} \iff& \exists \alpha \in I : \forall u \in P_\alpha : (u, x) \in B. \end{align*} $$
   This condition is now in the required form.

2. (ii) In this case, $C = \{(x, t) \in \mathbb {Z}^{n+1} : x \in B, f(x) \leq t, t \equiv k \ \pmod {N}\}$ where $B \subseteq \mathbb {Z}^{m+n}$ and $f : \mathbb {Z}^{m+n} \to \mathbb {Z}$ are Presburger and $k, N \in \mathbb {Z}$ . Then

   $$ \begin{align*} x \in \pi A \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : (u, x, y) \in C \\ \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge f(u, x) \leq y \wedge y \equiv k \quad\pmod{N} \\ \iff& \exists \alpha \in I : \exists y \in \mathbb{Z} : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge f(u, x) \leq y \wedge y \equiv k \quad\pmod{N}. \end{align*} $$
   We claim that the condition $y \equiv k \ \pmod {N}$ is unnecessary. Note that if there is some y with $\forall u \in P_\alpha : f(u, x) \leq y$ , we can merely add $1$ to y until it satisfies the modular equivalence condition, without affecting the order condition. Therefore, the above is equivalent to
   $$ \begin{align*} \iff& \exists \alpha \in I : \exists y \in \mathbb{Z} : \forall u \in P_\alpha : (u, x) \in B \wedge f(u, x) \leq y\\ \iff& \exists \alpha \in I : [\forall u \in P_\alpha : (u, x) \in B] \wedge \\ & [f(u, x) \text{ is bounded above for } u \in P_\alpha]. \end{align*} $$
   Because the values of f are integers, f is bounded above iff it has a maximum value on the given domain:
   $$ \begin{align*} \iff& \exists \alpha \in I : [\forall u \in P_\alpha : (u, x) \in B] \wedge \\ & [\exists v \in P_\alpha : \forall u \in P_\alpha : f(u, x) \leq f(v, x)]\\ \iff& \exists \alpha \in I : \exists v \in P_\alpha : \\ & \forall u \in P_\alpha : (u, x) \in B \wedge f(u, x) \leq f(v, x). \end{align*} $$
   Now, note that we may let $I' = \{(\alpha , v) : \alpha \in I \wedge v \in P_\alpha \}$ and let $P^{\prime }_{(\alpha , v)} = P_\alpha \times \{v\}$ :
   $$ \begin{align*} \iff& \exists (\alpha, v) \in I' : \forall (u, v) \in P^{\prime}_{(\alpha, v)} :\\ & (u, x) \in B \wedge f(u, x) \leq f(v, x). \end{align*} $$
   This condition is now in the required form.

3. (iii) In this case, $C = \{(x, t) \in \mathbb {Z}^{n+1} : x \in B, t \leq g(x), t \equiv k \ \pmod {N}\}$ where $B \subseteq \mathbb {Z}^{m+n}$ and $g : \mathbb {Z}^{m+n} \to \mathbb {Z}$ are Presburger and $k, N \in \mathbb {Z}$ . Then

   $$ \begin{align*} x \in \pi A \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : (u, x, y) \in C\\ \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge y \leq g(u, x) \wedge y \equiv k \quad\pmod{N}\\ \iff& \exists \alpha \in I : \exists y \in \mathbb{Z} : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge y \leq g(u, x) \wedge y \equiv k \quad\pmod{N}. \end{align*} $$
   As in (ii), the condition $y \equiv k \ \pmod {N}$ is unnecessary, this time because we can always decrease y until it is satisfied:
   $$ \begin{align*} \iff& \exists \alpha \in I : \exists y \in \mathbb{Z} : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge y \leq g(u, x)\\ \iff& \exists \alpha \in I : [\forall u \in P_\alpha : (u, x) \in B] \wedge \\ & [g(u, x) \text{ is bounded below for } u \in P_\alpha]. \end{align*} $$
   Because the values of f are integers, f is bounded below iff it has a minimum value on the given domain:
   $$ \begin{align*} \iff& \exists \alpha \in I : [\forall u \in P_\alpha : (u, x) \in B] \wedge \\ & [\exists v \in P_\alpha : \forall u \in P_\alpha : g(u, x) \geq g(v, x)]\\ \iff& \exists \alpha \in I : \exists v \in P_\alpha : \forall u \in P_\alpha : \\ & (u, x) \in B \wedge g(u, x) \geq g(v, x). \end{align*} $$
   We can now apply the same technique as in (ii) to put this condition in the required form.

4. (iv) In this case, $C = \{(x, t) \in \mathbb {Z}^{n+1} : x \in B, f(x) \leq t \leq g(x), t \equiv k \ \pmod {N}\}$ where $B \subseteq \mathbb {Z}^{m+n}$ and $f, g : \mathbb {Z}^{m+n} \to \mathbb {Z}$ are Presburger and $k, N \in \mathbb {Z}$ . Then

   $$ \begin{align*} x \in \pi A \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : (u, x, y) \in C\\ \iff& \exists y \in \mathbb{Z} : \exists \alpha \in I : \forall u \in P_\alpha : (u, x) \in B\\ &\wedge f(u, x) \leq y \wedge y \leq g(u, x) \wedge y \equiv k \quad\pmod{N}\\ \iff& \exists \alpha \in I : \exists y \in \mathbb{Z} : \forall u \in P_\alpha : (u, x) \in B\\ &\wedge f(u, x) \leq y \wedge y \leq g(u, x) \wedge y \equiv k \quad\pmod{N}. \end{align*} $$

   This is the most complex case. To fully analyze it, we introduce a predicate $\psi $ :

   $$ \begin{align*} \psi_{k, N}(a, b) \iff \exists y \in \mathbb{Z} : a \leq y \wedge y \leq b \wedge y \equiv k \quad\pmod{N}. \end{align*} $$

   The condition $\psi $ is Presburger (given constant k and N). Now, again, the above condition implies that f is bounded above and that g is bounded below on the given domain. Therefore, f has a maximum and g a minimum on the given domain, so the above condition is equivalent to

   $$ \begin{align*} x \in \pi A \iff& \exists \alpha \in I : \psi_{k, N}(\max_{u \in P_\alpha} f(u, x), \min_{u \in P_\alpha} g(u, x)) \\ \iff& \exists \alpha \in I : \exists v, w \in P_\alpha : [\forall u \in P_\alpha : f(u, x) \leq f(v, x)] \wedge \\ & [\forall u \in P_\alpha : g(u, x) \geq g(w, x)] \wedge \\ & [\psi_{k, N}(f(v, x), g(w, x))] \\ \iff& \exists \alpha \in I : \exists v, w \in P_\alpha : \forall u \in P_\alpha : f(u, x) \leq f(v, x) \wedge \\ & g(u, x) \geq g(w, x) \wedge \\ & \psi_{k, N}(f(v, x), g(w, x)). \end{align*} $$
   Now let $I' = \{(\alpha , v, w) : \alpha \in I \wedge v, w \in P_\alpha \}$ and let $P^{\prime }_{\alpha , v, w} = P_\alpha \times \{v\} \times \{w\}$ :
   $$ \begin{align*} \iff& \exists (\alpha, v, w) \in I' : \forall (u, v, w) \in P^{\prime}_{\alpha, v, w} : f(u, x) \leq f(v, x)\\ &\wedge g(u, x) \geq g(w, x) \wedge \psi_{k, N}(f(v, x), g(w, x)). \end{align*} $$
   This condition is now in the required form.

Now that we have proven the claims that give quantifier elimination, we introduce the dichotomy for $\mathcal {S}_1$ .

Claim 4.11. Let $A \in \mathcal {S}_{1}$ . Suppose that A does not contain arbitrarily long pieces of the same arithmetic progression $;$ in other words, suppose that given $N', k'$ there exists $\ell $ such that no $\ell $ consecutive terms of the sequence $(N'i+k')_i$ lie in A. Then there exist M and $h : \mathbb {Z}^{M} \to \mathbb {Z}$ Presburger such that $A \subseteq h(E^M)$ .

Proof Let A be as given. By definition there exist $m \in \mathbb {N}$ , a weak cell $C \subseteq \mathbb {Z}^{m+1}$ , and an indexed family $(P_\alpha )_{\alpha \in I}$ of subsets of $E^m$ such that $A = \bigcup _{\alpha \in I} \bigcap _{u \in P_\alpha } C_u$ . Assume that for each $\alpha $ the set $\bigcap _{u \in P_\alpha } C_u$ is nonempty (otherwise we may remove it from I without affecting A). Moreover assume I is nonempty, as otherwise A is empty and the claim trivially follows.

If A is of type (i), then A can be written as $\{t \in \mathbb {Z} : t \equiv k \ \pmod {N}\}$ . But then A fails our additional assumption for $(N', k') = (N, k)$ . If A is of type (ii), A is a union of intersections of sets of the form $\{t \in \mathbb {Z} : x \leq t, t \equiv k \ \pmod {N}\}$ for the same $k, N$ and varying numbers x; again, this is impossible because A will contain all sufficiently high elements of the arithmetic progression for $N' = N, k' = k$ . The case where A is of type (iii) is analogous.

Then A must be of type (iv); hence,

$$ \begin{align*} A =& \bigcup_{\alpha \in I} \bigcap_{u \in P_\alpha} \{(x, t) \in \mathbb{Z}^{m+1} : x \in B, \\ & \hskip6em f(x) \leq t \leq g(x), t \equiv k \quad\pmod{N}\}_u\\ =& \bigcup_{\alpha \in I} \bigcap_{u \in P_\alpha} \{t \in \mathbb{Z} : u \in B, f(u) \leq t \leq g(u), t \equiv k \quad\pmod{N}\} \end{align*} $$

for some $B, f, g$ Presburger and $k, N \in \mathbb {Z}$ . We may remove the $u \in B$ condition by assuming each $P_\alpha $ is a subset of B. Then this is equivalent to

$$ \begin{align*}A = \bigcup_{\alpha \in I} \{t \in \mathbb{Z} : \max_{u \in P_\alpha} f(u) \leq t \leq \min_{u \in P_\alpha} g(u), t \equiv k \quad\pmod{N}\}.\end{align*} $$

We denote the set $\{t \in \mathbb {Z} : \max _{u \in P_\alpha } f(u) \leq t \leq \min _{u \in P_\alpha } g(u), t \equiv k \ \pmod {N}\}$ in this cover by $A_\alpha $ .

Now note that there exists $\ell $ such that no $\ell $ consecutive terms of $(Ni+k)_i$ may lie in A, hence in any $A_\alpha $ . Therefore $\min _{u \in P_\alpha } g(u) < \max _{u \in P_\alpha } f(u) + \ell N$ . By the well-ordering principle, $\max _{u \in P_\alpha } f(u)$ exists in the image $f(E^m)$ . Therefore every element of A is equal to an element of $f(E^m)$ plus a nonnegative integer less than $\ell N$ .

Let $M = m+1$ , and let $e_0, \dots , e_{\ell N - 1}$ be $\ell N$ distinct elements of E. Define $h : \mathbb {Z}^M \to \mathbb {Z}$ as

$$ \begin{align*}h(x_1, \dots, x_{m+1}) = \left\{ \begin{array}{cc} f(x_1, \dots, x_m) + 0, & \text{if } x_{m+1} = e_0, \\ f(x_1, \dots, x_m) + 1, & \text{if } x_{m+1} = e_1, \\ \vdots & \vdots \\ f(x_1, \dots, x_m) + \ell N - 1, & \text{if } x_{m+1} = e_{\ell N - 1,} \\ 0, & \text{otherwise.} \end{array} \right.\end{align*} $$

(Note that h is Presburger, because it is a composition of f with piecewise linear functions.) Then h has the required property; i.e., as proven above, every element of A is in $h(E^M)$ .

Using this dichotomy, we are now at last able to prove Theorem C.

Theorem C. Let $\mathcal {I}$ be any set-theoretic ideal on $\mathbb {Z}$ . Let $E \subseteq \mathbb {Z}$ be such that, for every $M \in \mathbb {N}$ and $h : \mathbb {Z}^M \to \mathbb {Z}$ Presburger-definable, the image $h(E^M)$ is in $\mathcal {I}$ . Then every subset of $\mathbb {Z}$ definable in $(\mathbb {Z}, <, +, E)^\#$ either contains arbitrarily long pieces of some arithmetic progression or lies in $\mathcal {I}$ .

Proof Consider $(\mathbb {Z}, (Y))$ where Y ranges over all elements of all $\mathcal {S}_k$ for $k \in \mathbb {N}$ . We demonstrated earlier that preimages of subsets of $E^k$ under Presburger functions are in $\mathcal {T}_n$ , so in particular every such subset S is also in some $\mathcal {T}_n$ and thus by Claim 4.9 is a finite union of sets in $\mathcal {S}_n$ . We also demonstrated earlier that Presburger sets are also in $\mathcal {T}_n$ . Therefore, every set definable in $(\mathbb {Z}, <, +, E)^\#$ is also definable in $(\mathbb {Z}, (Y))$ . By combining Claims 4.4, 4.9, and 4.10, we see that in fact any subset of $\mathbb {Z}^n$ definable in $(\mathbb {Z}, (Y))$ is a finite union of sets in $\mathcal {S}_n$ . We deduce that every subset S of $\mathbb {Z}$ definable in $(\mathbb {Z}, <, +, E)^\#$ is a finite union of elements of $\mathcal {S}_1$ . Call these elements $S_1$ through $S_r$ .

Assume that such an S does not contain arbitrarily long pieces of the same arithmetic progression. Then neither do $S_1$ through $S_r$ ; by Claim 4.11, each $S_i$ is a subset of the image of $E^M$ for some M under some Presburger function h. Said images, by assumption, lie in $\mathcal {I}$ ; hence, so do any subsets thereof, and any finite unions of subsets thereof. We conclude that $S \in \mathcal {I}$ .