# Expansions of the Group of Integers by Beatty Sequences

Ayhan Günaydın  Department of Mathematics, Boğaziçi University, Bebek,
Istanbul, Turkey<EMAIL_ADDRESS>and  Melissa Özsahakyan
Department of Mathematics, Boğaziçi University, Bebek, Istanbul, Turkey
<EMAIL_ADDRESS>
###### Abstract.

We study the model theoretic structure $(\mathbb{Z},+,P_{r})$ where $r>1$ is
an irrational number and the elements of $P_{r}$ are of the form $\lfloor
nr\rfloor$ for some $n\in\mathbb{Z}\setminus\\{0\\}$. We axiomatize of this
structure and prove a quantifier elimination result. As a consequence, we get
that definable subsets are not sparse unless they are finite. We also prove
that there are no reducts of this structure expanding $(\mathbb{Z},+)$.

##  1\. Introduction

We investigate the expansion of the abelian group of integers by the following
subset:

$P_{r}:=\Big{\\{}\lfloor nr\rfloor:n\in\mathbb{Z}\setminus\\{0\\}\Big{\\}},$

where $r>1$ is an irrational number. The number $0$ is taken out for some
technical reasons and of course it has no effect on our results. There is a
considerable difference between this expansion and the expansion by
$P_{r}^{+}:=P_{r}\cap\mathbb{N}$, because $(\mathbb{Z},+,P_{r}^{+})$ defines
the ordering of $\mathbb{Z}$, whereas we show in Corollary 5.11 that
$(\mathbb{Z},+,P_{r})$ does not define the ordering. We also know that $P_{r}$
is not definable in $(\mathbb{Z},+,<)$, since it is shown in [3] that the only
reduct of $(\mathbb{Z},+,<)$ defining addition is $(\mathbb{Z},+)$.

There have been some work on expansions of $(\mathbb{Z},+)$ by a predicate by
Poizat , Palacín-Sklinos, and Lambotte-Point ([8, 7, 6]). In all these, the
predicate is _sparse_ , with certain different but similar meanings of the
word sparse. Later those results were generalized by Conant (in [2]), who
proved that the expansion of $(\mathbb{Z},+)$ by an infinite subset $A$ of a
submonoid of $(\mathbb{N}_{+},\cdot)$ is superstable of $U$-rank $\omega$.
Hence in that setting, sparsity comes from the multiplicative structure.

Our study of the expansion $(\mathbb{Z},+,P_{r})$ is complimentary to the work
mentioned above, as the set $P_{r}$ is certainly not sparse: If $k\in P_{r}$,
then the next element in $P_{r}$ is either $k+\lfloor r\rfloor$ or $k+\lfloor
r\rfloor+1$. (This is also the reason of $(\mathbb{Z},+,P_{r}^{+})$ defining
the ordering.) Actually, we prove that no infinite subset of $\mathbb{Z}$
definable in $(\mathbb{Z},+,P_{r})$ is sparse in the following sense:

######  Theorem 1.1.

Let $X\subseteq\mathbb{Z}$ be infinite and definable in
$(\mathbb{Z},+,P_{r})$. Then there is $N=N(X)\in\mathbb{N}_{+}$ such that for
any $x\in X$, one of the integers $x+1,x+2,\dots,x+N$ is in $X$.

The proof of this result goes through a quantifier elimination result. In
order to state that, let $L_{\pm}$ be the extension of the language
$\\{+,-,0,1\\}$ of abelian groups with a distinguished element by unary
predicate symbols $D_{m,+}$ and $D_{m,-}$ for each $m\geq 1$. We interpret the
new symbols in $\mathbb{Z}$ as follows:

$D_{m,+}^{\mathbb{Z}}:=\\{x\in\mathbb{Z}:x=my\text{ for some }y\in P_{r}\\},$

and

$D_{m,-}^{\mathbb{Z}}:=\\{x\in\mathbb{Z}:x=my\text{ for some }y\notin
P_{r}\\}.$

Note that $D_{1,+}^{\mathbb{Z}}=P_{r}$ and that $D_{m,+}^{\mathbb{Z}}\cup
D_{m,-}^{\mathbb{Z}}=m\mathbb{Z}$.

######  Theorem 1.2.

The structure $\Big{(}\mathbb{Z},+,0,1,(D_{m,+}^{\mathbb{Z}})_{m\geq
1},(D_{m,-}^{\mathbb{Z}})_{m\geq 1}\Big{)}$ has quantifier elimination.

A particular formula with quantifiers is

$\exists y\left(\bigwedge_{i\in I}x_{i}+k_{i}y\in P\wedge\bigwedge_{j\notin
I}x_{j}+k_{j}y\notin P\right),$

where $k_{1},\dots,k_{n}\in\mathbb{Z}$ and $I\subseteq\\{1,\dots,n\\}$. So we
have a quantifier-free $L_{\pm}$-formula $\psi_{\vec{k},I}(\vec{x})$ such that

$(\star)\forall x_{1}\cdots\forall x_{n}\left(\exists y\left(\bigwedge_{i\in
I}x_{i}+k_{i}y\in P\wedge\bigwedge_{j\notin I}x_{j}+k_{j}y\notin
P\right)\leftrightarrow\psi_{\vec{k},I}(\vec{x})\right).$

holds in $\Big{(}\mathbb{Z},+,0,1,(D_{m,+}^{\mathbb{Z}})_{m\geq
1},(D_{m,-}^{\mathbb{Z}})_{m\geq 1}\Big{)}$. As a matter of fact,
$\psi_{\vec{k},I}$ can be chosen to be a formula in the language
$L_{P}=\\{+,-,0,1,P\\}$.

With this notation at hand, we have the following axiomatization.

######  Theorem 1.3.

Let $\mathcal{M}=\big{(}M,+,-,0,1,P^{\mathcal{M}}\big{)}$ be an
$L_{P}$-structure. Then $\mathcal{M}$ is elementarily equivalent to
$(\mathbb{Z},+,-,0,1,P_{r})$ if and only if the following hold

  1. (1)

$(M,+,-,0,1)\equiv(\mathbb{Z},+,-,0,1)$,

  2. (2)

for every $k_{1},\dots,k_{n}\in\mathbb{Z}$ and $I\subseteq\\{1,\dots,n\\}$ the
sentence $(\star)$ holds in $\mathcal{M}$,

  3. (3)

$k\in P_{r}$ if and only if $k\in P^{\mathcal{M}}$ for every $k\in\mathbb{Z}$.

The technical parts of the proofs are done in an isomorphic structure: Let

$\Gamma_{r}:=\left\\{\exp(\frac{n2\pi
i}{r})\in\mathbb{C}:n\in\mathbb{Z}\right\\}.$

So $\Gamma_{r}=h(\mathbb{Z})$ where $h$ is the group isomorphism sending $n$
to $\exp(\frac{n2\pi i}{r})$. Being a subgroup of the unit circle,
$\Gamma_{r}$ has an _orientation_ on it; the precise definition is given in
the next section. Then the image of $P_{r}$ under $h$ becomes an _orientation
interval_ ; see Lemma 3.1. This makes it easier to work in $\Gamma_{r}$ and
the notations get simpler. For this reason, in Section 2, we recall some facts
about the circle and its subgroups.

In Section 3, we introduce Beatty Sequences and prove a few results about them
to be used in the model theoretic arguments.

A back-and-forth system constructed in Section 4 is used to prove the theorems
mentioned above in the rest of that section and Section 5.

The paper [9] by Tran-Walsberg has quite a bit of overlap with our work. The
authors consider $\mathbb{Z}$ equipped with a ‘cyclic ordering’; which in turn
is the same as considering an infinite cyclic subgroup of the circle equipped
with the orientation. We elaborate on this in Section 5.

In the last section, we prove a result analogous to the main result of [3]:
there are no intermediate structures between $(\mathbb{Z},+)$ and
$(\mathbb{Z},+,P_{r})$.

_Notations and Conventions._ The set $\mathbb{N}$ of natural numbers contains
$0$ and $\mathbb{N}_{+}=\mathbb{N}\setminus\\{0\\}$. We let the letters
$m,n,k,l$ vary in $\mathbb{Z}$, and if $m$ is in $\mathbb{N}$ (or
$\mathbb{N}_{+}$), we simply write $m\geq 0$ (or $m>0$).

For $n>0$, we denote the set $\\{1,\dots,n\\}$ as $[n]$.

For a real number $a$, we use the notation $\lfloor a\rfloor$ for the largest
integer smaller than or equal to $a$ and $\\{a\\}$ denotes the difference
$a-\lfloor a\rfloor$. (There will not be any occasions where this could be
confused with the singleton containing $a$.)

##  2\. The Circle and Its Subgroups

In the next section, we work with an infinite cyclic subgroup of the unit
circle $\mathbb{S}:=\\{\beta\in\mathbb{C}:|\beta|=1\\}$. One may study such a
group in the generality of _oriented abelian groups_ as defined in [4],
however there is no need to do so for our purposes.

Here we recall some generalities about $\mathbb{S}$ and at the end we say a
few words about its subgroups. Let

$e:\mathbb{R}\to\mathbb{S},\quad e(x):=\exp(2\pi ix).$

This is a surjective group homomorphism with kernel $\mathbb{Z}$.

We equip $\mathbb{S}$ with the _counter-clockwise orientation_ : Given
$\alpha,\beta,\gamma\in\mathbb{S}$, the relation
$\mathcal{O}(\alpha,\beta,\gamma)$ holds if and only if there are
$x,y,z\in\mathbb{R}$ such that $\alpha=e(x),\beta=e(y),\gamma=e(z)$, $x<y<z$,
and $z-x<1$.

If we fix $\alpha\in\mathbb{S}$, then we get a linear ordering
$\mathcal{O}_{\alpha}(\cdot,\cdot):=\mathcal{O}(\alpha,\cdot,\cdot)$ on
$\mathbb{S}\setminus\\{\alpha\\}$. For $\alpha=1$, we denote the ordering of
$\mathbb{S}\setminus\\{1\\}$ by the usual ordering sign:

$\beta<\gamma\Longleftrightarrow\mathcal{O}(1,\beta,\gamma).$

Clearly, if $\alpha<\beta$ and $\beta<\gamma$, then
$\mathcal{O}(\alpha,\beta,\gamma)$. So there is no harm in writing

$\alpha_{1}<\alpha_{2}<\cdots<\alpha_{n-1}<\alpha_{n}$

when
$\alpha_{1}<\alpha_{2},\alpha_{2}<\alpha_{3},\dots,\alpha_{n-1}<\alpha_{n}$.

We extend the definition of $<$ to all of $\mathbb{S}$ by setting $1<\alpha$
for $\alpha\neq 1$.

The relation of orientation and the group operation is as follows:

$\mathcal{O}(\alpha,\beta,\gamma)\Longleftrightarrow\mathcal{O}(\alpha\delta,\beta\delta,\gamma\delta)$

and

$\mathcal{O}(\alpha,\beta,\gamma)\Longleftrightarrow\mathcal{O}(\gamma^{-1},\beta,^{-1}\alpha^{-1})$

for every $\alpha,\beta,\gamma,\delta\in\mathbb{S}$ .

The circle $\mathbb{S}$ has the topology induced by the Euclidean topology on
$\mathbb{C}$ and a basis for this topology consists of _orientation intervals_
: Given $\alpha,\beta\in\mathbb{S}$ we define the orientation interval
determined by $\alpha$ and $\beta$ to be

$(\alpha,\beta):=\big{\\{}\gamma\in\mathbb{S}:\mathcal{O}(\alpha,\gamma,\beta)\big{\\}}.$

We do not assume $\alpha<\beta$ for this definition. So both $(\alpha,\beta)$
and $(\beta,\alpha)$ are orientation intervals and they are disjoint. Such an
interval is empty only when $\alpha=\beta$.

We define the _length_ of an orientation interval $I=(\alpha,\beta)$ to be

$l(I):=\beta\alpha^{-1}.$

So if $\alpha=e(a)$ and $\beta=e(b)$, then the length of $(\alpha,\beta)$ is
$e(b-a)$. In particular, the length of an orientation interval is $1$ if and
only if it is empty.

Below, we use the word _interval_ to mean _orientation interval_. We also use
the notations $[\alpha,\beta)$, $(\alpha,\beta]$, and $[\alpha,\beta]$ with
the obvious meanings, and we call them _intervals_ as well.

######  Proposition 2.1.

Let $\alpha_{1},\dots,\alpha_{m},\beta_{1},\dots,\beta_{m}$ be distinct
elements of $\mathbb{S}$. Then the following conditions are equivalent:

  1. (1)

$\displaystyle{\bigcap_{i=1}^{m}}(\alpha_{i},\beta_{i})\neq\emptyset$.

  2. (2)

there is $i_{0}\in[m]$ such that $\alpha_{i_{0}}\in(\alpha_{i},\beta_{i})$ for
every $i\neq i_{0}$.

  3. (3)

there is $j_{0}\in[m]$ such that $\beta_{j_{0}}\in(\alpha_{i},\beta_{i})$ for
every $i\neq j_{0}$.

Moreover, if one of these conditions hold, then

$\bigcap_{i=1}^{m}(\alpha_{i},\beta_{i})=(\alpha_{i_{0}},\beta_{j_{0}}).$

###### Proof.

Suppose $\gamma\in(\alpha_{i},\beta_{i})$ for every $i\in[m]$. Then
$\mathcal{O}_{\gamma}(\beta_{i},\alpha_{i})$ for each $i\in[m]$. Choose
$i_{0}$ such that $\alpha_{i_{0}}$ is maximal among $\alpha_{i}$ with respect
to $\mathcal{O}_{\gamma}$. Clearly, $\alpha_{i_{0}}\in(\alpha_{i},\beta_{i})$
for each $i\neq i_{0}$. Similarly, taking $\beta_{j_{0}}$ to be minimum among
$\beta_{i}$ with respect to $\mathcal{O}_{\gamma}$ we see that
$\beta_{j_{0}}\in(\alpha_{i},\beta_{i})$ for each $i\neq j_{0}$. So the first
condition implies the others.

Conversely, assume that $\alpha_{i_{0}}\in(\alpha_{i},\beta_{i})$ for each
$i\neq i_{0}$. Then

$(\alpha_{i_{0}},\beta_{j_{0}})\subseteq\bigcap_{i=1}^{m}(\alpha_{i},\beta_{i}),$

where $\beta_{j_{0}}$ is minimum among $\beta_{i}$ with respect to
$\mathcal{O}_{\alpha_{i_{0}}}$.

If $\beta_{j_{0}}\in(\alpha_{i},\beta_{i})$ for each $i\neq i_{0}$. Then we
take $\alpha_{i_{0}}$ to be maximum among $\alpha_{i}$ with respect to
$\mathcal{O}_{\beta{j_{0}}}$ in order to get

$(\alpha_{i_{0}},\beta_{j_{0}})\subseteq\bigcap_{i=1}^{m}(\alpha_{i},\beta_{i}).$

The last sentence of the proposition follows from the rest of the proof above.
∎

For $k\in\mathbb{N}_{+}$, let $\zeta_{k}$ denote the primitive $k^{\text{th}}$
root of unity $e(\frac{1}{k})$.

######  Proposition 2.2.

Let $\alpha,\beta,\gamma\in\mathbb{S}$ and $k\in\mathbb{N}_{+}$ such that
$l\big{(}(\alpha,\gamma)\big{)}<\zeta_{k}$. Then
$\beta^{k}\in(\alpha^{k},\gamma^{k})$ if and only if
$\beta\in(\zeta_{k}^{s}\alpha,\zeta_{k}^{s}\gamma)$ for some $s\in\mathbb{Z}$.

###### Proof.

Note that if $\alpha=\gamma$, then the result is clear; so we assume
$\alpha\neq\gamma$. We may also assume that $\alpha<\gamma$; if that is not
the case, then multiply $\alpha$ and $\gamma$ by $\zeta_{k}$. So let $0\leq
a<c<1$ be such that $\alpha=e(a)$ and $\gamma=e(c)$. Note that
$c-a<\frac{1}{k}$ by assumption. Also let $\beta=e(b)$ for some $0\leq b<1$.

Suppose $\beta^{k}\in(\alpha^{k},\gamma^{k})$ and take $b^{\prime}$ such that
$\beta^{k}=e(b^{\prime})$ and $ka<b^{\prime}<kc$. Then
$s:=kb-b^{\prime}\in\mathbb{Z}$ and we get

$ka+s<kb<kc+s.$

Dividing by $k$, we have

$a+\frac{s}{k}<b<c+\frac{s}{k}.$

Applying $e$, we get that $\beta\in(\zeta_{k}^{s}\alpha,\zeta_{k}^{s}\gamma)$.

Conversely, let $\beta\in(\zeta_{k}^{s}\alpha,\zeta_{k}^{s}\gamma)$ for some
$s\in\mathbb{Z}$. In other words, $\beta\zeta_{k}^{-s}\in(\alpha,\gamma)$.
Take $b^{\prime\prime}$ such that $\beta\zeta_{k}^{-s}=e(b^{\prime\prime})$
and $a<b^{\prime\prime}<c$. Then
$t:=b-b^{\prime\prime}-\frac{s}{k}\in\mathbb{Z}$ and

$a+t<b-\frac{s}{k}<c+t.$

Now multiplying by $k$ and applying $e$ we get
$\beta^{k}\in(\alpha^{k},\gamma^{k})$. ∎

Note that the $s$ in this proposition can be chosen among $0,1,\dots,k-1$.

Given $\alpha=e(x)$ with $0\leq x<1$ and $k\in\mathbb{N}_{+}$, we let
$\alpha^{1/k}$ denote $e(\frac{x}{k})$; so $\alpha^{1/k}$ is the
$k^{\text{th}}$ root of $\alpha$ with the smallest argument. Note that
$1^{1/k}=1$ and that for $x\in\mathbb{R}$ we have
$e(x)^{1/k}=e(\frac{x}{k})\zeta_{k}^{-\lfloor x\rfloor}$. In particular, if
$\alpha=e(a)$, then $(\alpha^{k})^{1/k}=\alpha\zeta_{k}^{-\lfloor ak\rfloor}$.
However, we always have $(\alpha^{1/k})^{k}=\alpha$. The following observation
will be useful.

######  Lemma 2.3.

Let $\alpha,\beta\in\mathbb{S}$, $k,l\in\mathbb{Z}$. Suppose that
$\alpha^{k}=\beta$. Then $\alpha=\beta^{1/k}\zeta_{k}^{l}$ if and only if
$\alpha\in(\zeta_{k}^{l},\zeta_{k}^{l+1})$.

###### Proof.

Clear. ∎

Using this new notation, the previous proposition has the following
consequences.

######  Corollary 2.4.

Let $\alpha,\beta,\gamma\in\mathbb{S}$ and $k\in\mathbb{N}_{+}$. Suppose that
$\gamma\not<\alpha$. Then $\beta^{k}\in(\alpha,\gamma)$ if and only if there
is $s\in\\{0,1,\dots,k-1\\}$ such that
$\beta\in\big{(}\zeta_{k}^{s}\alpha^{1/k},\zeta_{k}^{s}\gamma^{1/k}\big{)}$.

######  Corollary 2.5.

Let $\alpha,\beta,\gamma\in\mathbb{S}$ and $k\in\mathbb{N}_{+}$. Suppose that
$\gamma<\alpha$. Then $\beta^{k}\in(\alpha,\gamma)$ if and only if there is
$s\in\\{0,1,\dots,k-1\\}$ such that
$\beta\in\big{(}\zeta_{k}^{s}\alpha^{1/k},\zeta_{k}^{s+1}\gamma^{1/k}\big{)}$.

Regularly Dense Groups. Let $\Gamma\leq\mathbb{S}$. Then $\Gamma$ is either
finite or dense in $\mathbb{S}$. When it is finite, it consists of
$m^{\text{th}}$ roots of unity for some $m>0$. When $\Gamma$ is dense, it is
indeed _regularly dense_ in the following sense.

######  Proposition 2.6.

Let $\Gamma\leq\mathbb{S}$ be infinite. Then for any distinct
$\alpha,\beta\in\Gamma$ and prime $p$, there is $\gamma\in\Gamma$ such that
$\gamma^{p}\in(\alpha,\beta)$.

For the proof of this, we refer the reader to Definition 8.1.7 in [4] and the
remark succeeding it. Note that the conclusion of the proposition above is
slightly different than the original definition of regularly dense, but it is
easy see that they are indeed equivalent. It follows that for any $n>0$ and
distinct $\alpha,\beta\in\Gamma$, there is $\gamma\in\Gamma$ such that
$\gamma^{n}\in(\alpha,\beta)$.

##  3\. Beatty Sequences

Let $r>1$ be an irrational number. The _Beatty Sequence generated by $r$_ is
$\mathcal{B}_{r}=\left(\lfloor mr\rfloor\right)_{m>0}$; we put $b_{m}=\lfloor
mr\rfloor$. This is an increasing sequence and we let $P_{r}^{+}$ denote the
set whose elements are the terms of $\mathcal{B}_{r}$.

A related sequence is
$\mathcal{S}_{r}=\left(\lfloor\frac{n+1}{r}\rfloor-\lfloor\frac{n}{r}\rfloor\right)_{n>0}$;
we put $s_{n}=\lfloor\frac{n+1}{r}\rfloor-\lfloor\frac{n}{r}\rfloor$. Note
that $s_{n}\in\\{0,1\\}$ for each $n>0$. Actually, it is better to think of
$\mathcal{S}_{r}$ as an infinite word in the alphabet $\\{0,1\\}$. As such, it
is called _the Characteristic Sturmian Word of Slope $\frac{1}{r}$_. It has
the property that for every $m$, it has exactly $m+1$ many different subwords
of length $m$.

Both Beatty Sequences and Sturmian Words have rich theories that we do not get
into here, and we refer the interested reader to [1]. We only need the
following connection between $\mathcal{B}_{r}$ and $\mathcal{S}_{r}$ which is
Lemma 9.1.3 of [1], but we include a proof for completeness.

######  Lemma 3.1.

Let $n\in\mathbb{N}_{+}$. Then $n\in P_{r}^{+}$ if and only if $s_{n}=1$.

###### Proof.

Let $n\in P_{r}^{+}$. Then $n=\lfloor kr\rfloor$ for some
$k\in\mathbb{N}_{+}$. So $kr-1<n<kr$ and after diving by $r$ we have

$k-\frac{1}{r}<\frac{n}{r}<k.$

Therefore $\lfloor\frac{n}{r}\rfloor=k-1$ and $\lfloor\frac{n+1}{r}\rfloor=k$.
Thus $s_{n}=\lfloor\frac{n+1}{r}\rfloor-\lfloor\frac{n}{r}\rfloor=1$. As all
the implications are reversible we get the desired result. ∎

We would like to consider the negative elements as well; so we define

$P_{r}=\big{\\{}\lfloor nr\rfloor:n\in\mathbb{Z}\setminus\\{0\\}\big{\\}}.$

For $m>0$, we have $-m\in P_{r}$ if and only if $m-1\in P_{r}^{+}$. So

$P_{r}=P_{r}^{+}\cup(-P_{r}^{+}-1).$

We also extend the definitions of $b_{n}$ and $s_{n}$ to all integers $n$.

Lemma 3.1 is actually correct for all $n\in\mathbb{Z}$:

(3.1) $n\in P_{r}\Longleftrightarrow s_{n}=1.$

It is easy to see that $s_{n}=1$ if and only if
$\\{\frac{n}{r}\\}>1-\frac{1}{r}$. Putting this together with (3.1), for every
$n\in\mathbb{Z}$, we get

(3.2) $n\in
P_{r}\Longleftrightarrow\big{\\{}\frac{n}{r}\big{\\}}>1-\frac{1}{r}.$

Since $r$ is irrational, the image of $\mathbb{Z}\frac{1}{r}$ under $e$ is not
finite, hence it is a dense subgroup of $\mathbb{S}$. Let $\Gamma_{r}$ be that
subgroup, and let $h$ denote the map $n\mapsto e(\frac{n}{r})$. So we have an
isomorphism of abelian groups with a distinguished element:

$h:\big{(}\mathbb{Z},+,-,0,1\big{)}\simeq\big{(}\Gamma_{r},\cdot,^{-1},1,h(1)\big{)}.$

By (3.2), the image of $P_{r}$ under $h$ is
$\big{(}h(-1),1\big{)}\cap\Gamma_{r}$. Therefore expanding $\mathbb{Z}$ by
$P_{r}$ is the same as expanding $\Gamma_{r}$ by
$\big{(}h(-1),1\big{)}\cap\Gamma_{r}$.

Using Proposition 2.2 and its corollaries, we give a criterion for certain
linear combinations of integers being in $P_{r}$ in terms of intervals in
$\mathbb{S}$.

######  Proposition 3.2.

Let $k\in\mathbb{N}_{+}$ and $a,c\in\mathbb{Z}$. Then $a+kc\in P_{r}$ if and
only if there is $s\in\mathbb{Z}$ such that

$h(c)\in\big{(}h(-a-1)^{1/k}\zeta_{k}^{s},h(-a)^{1/k}\zeta_{k}^{s+s_{a}}\big{)}.$

###### Proof.

First, note that $a\in P_{r}$ if and only if $h(-a)<h(-a-1)$.

By (3.2) we have

$a+kc\in P_{r}\Longleftrightarrow
h(a)h(c)^{k}\in\big{(}h(-1),1\big{)}\Longleftrightarrow
h(c)^{k}\in\big{(}h(-a-1),h(-a)\big{)}.$

Now combining Corollaries 2.4 and 2.5 and using the first sentence of this
proof, we get that

$h(c)^{k}\in\big{(}h(-a-1),h(-a)\big{)}$

if and only if there is $s\in\mathbb{Z}$ with

$h(c)\in\big{(}h(-a-1)^{1/k}\zeta_{k}^{s},h(-a)^{1/k}\zeta_{k}^{s+s_{a}}\big{)}.$

This gives the desired equivalence. ∎

######  Corollary 3.3.

Let $k\in\mathbb{N}_{+}$ and $a,c\in\mathbb{Z}$. Then $a+kc\notin P_{r}$ if
and only if there is $s\in\mathbb{Z}$ such that

$h(c)\in\big{[}h(-a)^{1/k}\zeta_{k}^{s+s_{a}},h(-a-1)^{1/k}\zeta_{k}^{s+1}\big{]}.$

###### Proof.

Clear from the previous proposition. ∎

Next result will be useful in handling the cases when $k$ is negative.

######  Lemma 3.4.

Let $a,c\in\mathbb{Z}$ and $k<0$. Then $a+kc\in P_{r}$ if and only if
$-a-1-kc\in P_{r}$.

###### Proof.

Clear from the fact that $\lfloor-x\rfloor=-\lfloor x\rfloor-1$ for
$x\notin\mathbb{Z}$. ∎

######  Definition 3.5.

For $a\in\mathbb{Z}$, $k\in\mathbb{N}_{+}$, and $s\in\\{0,1,\dots,k-1\\}$, let

$U_{a,k,s}:=\big{(}h(-a-1)^{1/k}\zeta_{k}^{s},h(-a)^{1/k}\zeta_{k}^{s+s_{a}}\big{)},$
$V_{a,k,s}:=\big{[}h(-a)^{1/k}\zeta_{k}^{s+s_{a}},h(-a-1)^{1/k}\zeta_{k}^{s+1}\big{]}.$

Also let

$U_{a,k}:=\bigcup_{s=0}^{k-1}U_{a,k,s}\quad\text{ and }\quad
V_{a,k}:=\bigcup_{s=0}^{k-1}V_{a,k,s}.$

We extend the definitions to $k=0$ as follows:

$U_{a,0}:=\begin{cases}\mathbb{S}&:\text{if }a\in P_{r}\\\ \emptyset&:\text{if
}a\notin P_{r}\end{cases}\quad\text{ and }\quad
V_{a,0}:=\begin{cases}\emptyset&:\text{if }a\in P_{r}\\\ \mathbb{S}&:\text{if
}a\notin P_{r}\end{cases}$

Finally, we let $\tilde{V}_{a,k}$ denote the interior of $V_{a,k}$.

With this notation in hand, Proposition 3.2 and Corollary 3.3 translate as
follows: Given $k\in\mathbb{N}$ and $a,c\in\mathbb{Z}$ we have

(3.3) $a+kc\in P_{r}\Longleftrightarrow h(c)\in U_{a,k},$

and

(3.4) $a+kc\notin P_{r}\Longleftrightarrow h(c)\in V_{a,k}.$

######  Lemma 3.6.

Let $a,b\in\mathbb{Z}$ and $k,l\in\mathbb{N}_{+}$. Suppose $g=\gcd(k,l)$ and
write $k=gk^{\prime}$ and $l=gl^{\prime}$. Then the following hold.

  1. (1)

Suppose $\zeta_{k^{\prime}}<h(1)$. Then there is $s\in\mathbb{Z}$ such that
$h(a)^{1/k}\zeta_{k}^{s}\in U_{b,l}$.

  2. (2)

Suppose $h(1)<\zeta_{k^{\prime}}$. Then there is $s\in\mathbb{Z}$ such that
$h(a)^{1/k}\zeta_{k}^{s}\in U_{b,l}$ if and only if

$h(l^{\prime}a+k^{\prime}b)\in\big{(}h(-k^{\prime}),1\big{)}.$

###### Proof.

Using Corollaries 2.4 and 2.5, $h(a)^{1/k}\zeta_{k}^{s}\in U_{b,l}$ if and
only if

$h(l^{\prime}a)^{1/k^{\prime}}\zeta_{k^{\prime}}^{\lfloor\frac{la}{r}\rfloor-l\lfloor\frac{a}{r}\rfloor+sl^{\prime}}\in\big{(}h(-b-1),h(-b)\big{)}.$

Since $\gcd(k^{\prime},l^{\prime})=1$, there is $s\in\mathbb{Z}$ with
$h(a)^{1/k}\zeta_{k}^{s}\in U_{b,l}$ if and only if there is $t\in\mathbb{Z}$
with
$h(l^{\prime}a)^{1/k^{\prime}}\zeta_{k^{\prime}}^{t}\in\big{(}h(-b-1),h(-b)\big{)}$.

If $\zeta_{k^{\prime}}<h(1)$, then there is such a $t$, regardless of what
$a,b,l$ are.

If $h(1)<\zeta_{k^{\prime}}$, then we may use Proposition 2.2 to conclude that
there is $s\in\mathbb{Z}$ with $h(a)^{1/k}\zeta_{k}^{s}\in U_{b,l}$ if and
only if

$h(l^{\prime}a)\in\big{(}h(-k^{\prime}b-k^{\prime}),h(-k^{\prime}b)\big{)}.$

After simplification, this means
$h(l^{\prime}a+k^{\prime}b)\in\big{(}h(-k^{\prime}),1\big{)}$.

∎

This proof can be modified to prove the next analogous result.

######  Lemma 3.7.

Let $a,b\in\mathbb{Z}$ and $k,l\in\mathbb{N}_{+}$. Suppose $g=\gcd(k,l)$ and
write $k=gk^{\prime}$ and $l=gl^{\prime}$. Then the following hold.

  1. (1)

Suppose $\zeta_{k^{\prime}}<h(-1)$. Then there is $s\in\mathbb{Z}$ such that
$h(a)^{1/k}\zeta_{k}^{s}\in V_{b,l}$.

  2. (2)

Suppose $h(-1)<\zeta_{k^{\prime}}$. Then there is $s\in\mathbb{Z}$ such that
$h(a)^{1/k}\zeta_{k}^{s}\in V_{b,l}$ if and only if

$h(l^{\prime}a+k^{\prime}b^{\prime})\in\big{[}1,h(-k^{\prime})\big{]}.$

Let $\vec{a}=(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$,
$\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{N}^{n}$, $I\subseteq[n]$ and
$J\subseteq[n]\setminus I$ be given. We define

$V_{\vec{a},\vec{k},J}=\bigcap_{j\in
J}(V_{a_{j},k_{j}}\setminus\tilde{V}_{a_{j},k_{j}})\cap\bigcap_{j\in[n]\setminus(I\cup
J)}\tilde{V}_{a_{j},k_{j}}.$

Note that $V_{a_{j},k_{j}}\setminus\tilde{V}_{a_{j},k_{j}}$ has $2k_{j}$ many
points. Therefore $V_{\vec{a},\vec{k},J}$ is finite for $J\neq\emptyset$ and
$V_{\vec{a},\vec{k},\emptyset}$ is an open subset of $\mathbb{S}$.

We record the following without proof.

######  Lemma 3.8.

Let $\vec{a}=(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$,
$\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{N}_{+}^{n}$, and $\emptyset\neq
J\subseteq[n]$. Then $h(c)\in V_{\vec{a},\vec{k},J}\cap\Gamma_{r}$ if and only
if there is a subset $J^{\prime}$ of $J$ such that $c=\frac{-a_{j}}{k_{j}}$
for every $j\in J^{\prime}$, $c=\frac{-a_{j}-1}{k_{j}}$ for every $j\in
J\setminus J^{\prime}$, and $h(c)\in\bigcap_{j\in[n]\setminus
J}\tilde{V}_{a_{j},k_{j}}$.

######  Definition 3.9.

Let $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{Z}^{n}$ and $I\subseteq[n]$. We say
that $(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$ realize $(\vec{k},I)$-pattern  if
there is $c\in\mathbb{Z}$ such that

$a_{i}+k_{i}c\in P_{r}\Longleftrightarrow i\in I.$

For $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{Z}^{n}$, let
$|\vec{k}|=(|k_{1}|,\dots,|k_{n}|)$. Then using Lemma 3.4,
$(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$ realizes the $(\vec{k},I)$-pattern if
$(a_{1}^{\prime},\dots,a_{n}^{\prime})$ realizes the $(|\vec{k}|,I)$-pattern
where $a_{i}^{\prime}=a_{i}$ for $k_{i}\geq 0$ and $a_{i}^{\prime}=-a_{i}-1$
for $k_{i}<0$. Therefore, we may focus on the case that
$\vec{k}\in\mathbb{N}^{n}$.

By $(\ref{5})$ and $(\ref{6})$, if $\vec{k}\in\mathbb{N}^{n}$, then
$(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$ realize $(\vec{k},I)$-pattern if and
only if

$\bigcap_{i\in I}U_{a_{i},k_{i}}\cap\bigcap_{j\notin
I}V_{a_{j},k_{j}}\cap\Gamma_{r}\neq\emptyset.$

We may decompose the intersection above as

$\left(\bigcap_{i\in I}U_{a_{i},k_{i}}\cap\bigcap_{j\notin
I}\tilde{V}_{a_{j},k_{j}}\cap\Gamma_{r}\right)\cup\left(\bigcap_{i\in
I}U_{a_{i},k_{i}}\cap\bigcup_{\emptyset\neq J\subseteq[n]\setminus
I}V_{\vec{a},\vec{k},J}\cap\Gamma_{r}\right).$

Using Lemma 3.8, the finite component is under control.

Let’s focus on $\bigcap_{i\in I}U_{a_{i},k_{i}}\cap
V_{\vec{a},\vec{k},\emptyset}\cap\Gamma_{r}$. Since $\Gamma_{r}$ is dense in
$\mathbb{S}$, this set is nonempty if and only if the open set

$\bigcap_{i\in I}U_{a_{i},k_{i}}\cap\bigcap_{j\notin
I}\tilde{V}_{a_{j},k_{j}}$

is nonempty.

Using Proposition 2.1, it is easy to see that this intersection is nonempty if
and only if one of the following holds:

  1. (1)

there are $i_{0}\in I$ and $s\in\mathbb{Z}$ such that

$h(-a_{i_{0}}-1)^{1/k_{i_{0}}}\zeta_{k_{i_{0}}}^{s}\in\bigcap_{i\in I,i\neq
i_{0}}U_{a_{i},k_{i}}\cap\bigcap_{j\notin I}\tilde{V}_{a_{j},k_{j}},$

  2. (2)

there are $j_{0}\in[n]\setminus I$ and $s\in\mathbb{Z}$ such that

$h(-a_{j_{0}})^{1/k_{j_{0}}}\zeta_{k_{j_{0}}}^{s}\in\bigcap_{i\in
I}U_{a_{i},k_{i}}\cap\bigcap_{j\notin I,j\neq j_{0}}\tilde{V}_{a_{j},k_{j}}.$

In order to summarize these observations, we make the following definitions:
let $k,l\in\mathbb{N}$ with $g=\gcd(k,l)$ and $k^{\prime}:=k/g$,
$l^{\prime}:=l/g$

$A_{k,l}:=\begin{cases}\mathbb{Z}\times\mathbb{Z}&:\text{if
}\zeta_{k^{\prime}}<h(1)\\\
\left\\{(a,b)\in\mathbb{Z}\times\mathbb{Z}:h(l^{\prime}a+k^{\prime}b)\in\big{(}h(-k^{\prime}),1\big{)}\right\\}&:\text{if
}h(1)<\zeta_{k^{\prime}}\end{cases}$

$B_{k,l}:=\begin{cases}\mathbb{Z}\times\mathbb{Z}&:\text{if
}\zeta_{k^{\prime}}<h(-1)\\\
\left\\{(a,b)\in\mathbb{Z}\times\mathbb{Z}:h(l^{\prime}a+k^{\prime}b)\in\big{(}1,h(-k^{\prime})\big{)}\right\\}&:\text{if
}h(-1)<\zeta_{k^{\prime}}\end{cases}$

Combining Lemmas 3.6 and 3.7 with the observations above, we obtain the
following.

######  Proposition 3.10.

Let $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{N}^{n}$ and $I\subseteq[n]$. Then
$\vec{a}=(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$ realizes the
$(\vec{k},I)$-pattern if and only if one of the following conditions holds:

  1. (1)

$\bigcap_{i\in I}U_{a_{i},k_{i}}\cap\bigcup_{\emptyset\neq
J\subseteq[n]\setminus I}V_{\vec{a},\vec{k},J}\cap\Gamma_{r}\neq\emptyset$.

  2. (2)

there is $i_{0}\in I$ with $(-a_{i_{0}}-1,a_{i})\in A_{k_{i_{0}},k_{i}}$ for
every $i\in I\setminus\\{i_{0}\\}$ and $(-a_{i_{0}}-1,a_{j})\in
B_{k_{i_{0}},k_{j}}$ for every $j\in[n]\setminus I$.

  3. (3)

there is $j_{0}\in I$ with $(-a_{j_{0}},a_{i})\in A_{k_{j_{0}},k_{i}}$ for
every $i\in I$ and $(-a_{j_{0}},a_{j})\in B_{k_{j_{0}},k_{j}}$ for every
$j\in[n]\setminus(I\cup\\{j_{0}\\})$.

The final result of this section expresses the interval $\big{(}h(k),1\big{)}$
in terms of $P_{r}$ when $h(1)<\zeta_{k}$.

######  Lemma 3.11.

Let $k>0$ be such that $h(1)<\zeta_{k}$. Then $\alpha\in\big{(}1,h(k)\big{)}$
if and only if

$\alpha^{-1}\in\bigcup_{i=0}^{k-1}h(-i)P_{r}\cup\\{h(-1),h(-2),\dots,h(-(k-1))\\}.$

_(Here $h(i)P_{r}$ is short for the interval $\big{(}h(-i-1),h(-i)\big{)}$.)_

###### Proof.

The assumption $h(1)<\zeta_{k}$ gives $h(i-1)<h(i)$ for every $i\in[k]$. So we
have the decomposition

$\displaystyle\big{(}1,h(k)\big{)}$
$\displaystyle=\big{(}1,h(1)\big{]}\cup\big{(}h(1),h(2)\big{]}\cup\cdots\cup\big{(}h(k-1),h(k)\big{)}$
$\displaystyle=\big{(}1,h(1)\big{)}\cup\cdots\cup\big{(}h(k-1),h(k)\big{)}\cup\\{h(1),\dots,h(k-1)\\}$
$\displaystyle=\bigcup_{i=0}^{k-1}h(i)\big{(}1,h(1))\cup\\{h(1),\dots,h(k-1)\\}$

This finishes the proof, since $\beta\in\big{(}1,h(1))$ if and only if
$\beta^{-1}\in P_{r}$. ∎

##  4\. Expanding the Group of Integers

We would like to consider the model theoretic structure obtained by expanding
the abelian group of integers by the subset $P_{r}$. We have seen above that
$\mathbb{Z}$ is isomorphic as an abelian group with a subgroup $\Gamma_{r}$ of
$\mathbb{S}$ that happens to be dense in $\mathbb{S}$. The work in the
previous section was mostly done in $\Gamma_{r}$, but it is straightforward to
pull those results back to $\mathbb{Z}$ via the map $h$.

Let $L:=\\{+,-,0,c\\}$ be the language of abelian groups with a distinguished
element $c$. Let $T$ be the theory of the $L$-structure
$(\mathbb{Z},+,-,0,1)$.

We extend $L$ to $L_{P}:=L\cup\\{P\\}$ where $P$ is a unary relation symbol.
Our main objective is to study the $L_{P}$-structure

$\mathfrak{Z}:=\Big{(}\mathbb{Z},+,-,0,1,P_{r}\Big{)}.$

For $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{Z}^{n}$ and $I\subseteq[n]$, we
define $\phi_{\vec{k},I}(x_{1},\dots,x_{n})$ to be the following
$L_{P}$-formula:

$\exists y\left(\bigwedge_{i\in I}x_{i}+k_{i}y\in P\wedge\bigwedge_{j\notin
I}x_{j}+k_{j}y\notin P\right).$

Therefore for $(a_{1},\dots,a_{n})\in\mathbb{Z}^{n}$, we have
$\mathfrak{Z}\models\phi_{\vec{k},I}(a_{1},\dots,a_{n})$ if and only if
$(a_{1},\dots,a_{n})$ realizes the $(\vec{k},I)$-pattern. Then using
Proposition 3.10 and Lemma 3.11, there is a quantifier-free $L_{P}$-formula
$\psi_{\vec{k},I}(x_{1},\dots,x_{n})$ such that

$\mathfrak{Z}\models\forall x_{1}\cdots\forall
x_{n}\big{(}\phi_{\vec{k},I}(x_{1},\dots,x_{n})\leftrightarrow\psi_{\vec{k},I}(x_{1},\dots,x_{n})\big{)}$

Let $T_{r}$ be the $L_{P}$-theory extending $T$ by the condition above; namely
for every $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{Z}^{n}$ and $I\subseteq[n]$,
we add the following sentence as an axiom:

$\forall x_{1}\cdots\forall
x_{n}\left(\phi_{\vec{k},I}(x_{1},\dots,x_{n})\leftrightarrow\psi_{\vec{k},I}(x_{1},\dots,x_{n})\right)$

We shall construct a back-and-forth system between certain substructures of
models of $T_{r}$.

Let $\mathcal{M}$ and $\mathcal{N}$ be $\aleph_{0}$-saturated models of
$T_{r}$. Let $S_{\mathcal{M}}$ be the collection of countable
$L_{P}$-substructures $\mathcal{M}^{\prime}$ of $\mathcal{M}$ such that
$M^{\prime}$ is a pure subgroup of $M$. We define $S_{\mathcal{N}}$ in a
similar way.

Note that the group $\mathbb{Z}$ has a copy in each member of
$S_{\mathcal{M}}$ and $S_{\mathcal{N}}$ as the subgroup generated by the
constant $c$. However, those copies may not be isomorphic as
$L_{P}$-substructures of $\mathcal{M}$ and $\mathcal{N}$.

Let $\mathfrak{B}(\mathcal{M},\mathcal{N})$ be the collection of
$L_{P}$-isomorphisms $f:\mathcal{M}^{\prime}\to\mathcal{N}^{\prime}$, where
$\mathcal{M}^{\prime}\in S_{\mathcal{M}}$ and $\mathcal{N}^{\prime}\in
S_{\mathcal{N}}$.

######  Proposition 4.1.

For $\aleph_{0}$-saturated models $\mathcal{M}$ and $\mathcal{N}$ of $T_{r}$,
the collection $\mathfrak{B}(\mathcal{M},\mathcal{N})$ is a back-and-forth
system.

###### Proof.

Let $f:\mathcal{M}^{\prime}\to\mathcal{N}^{\prime}$ be in
$\mathfrak{B}(\mathcal{M},\mathcal{N})$ and $\alpha\in M\setminus M^{\prime}$.
By symmetry, it suffices to extend $f$ to an element of
$\mathfrak{B}(\mathcal{M},\mathcal{N})$ that contains $\alpha$ in its domain.

Let $M^{\prime\prime}$ be the pure subgroup of $M$ generated by $M^{\prime}$
and $\alpha$; namely:

$M^{\prime\prime}=\langle M^{\prime}\cup\\{\alpha\\}\rangle_{M}:=\\{\gamma\in
M:m\gamma\in M^{\prime}\oplus\mathbb{Z}\alpha\text{ for some }m>0\\}.$

Also let $\mathcal{M}^{\prime\prime}$ be the $L_{P}$-substructure of
$\mathcal{M}$ with the underlying set $M^{\prime\prime}$. We would like to
extend $f$ to $\mathcal{M}^{\prime\prime}$. That amounts to finding $\beta\in
N$ with the following property:

$(*)$ For every $a\in M^{\prime}$, $k\in\mathbb{Z}$, $n>0$, and $\gamma\in M$
if $a+k\alpha=n\gamma$, then

there is $\delta\in N$ such that $f(a)+k\beta=n\delta$, and

$\gamma\in P\Longleftrightarrow\delta\in P.$

This condition without the last part just means that $\langle
M^{\prime}\cup\\{\alpha\\}\rangle_{M}$ and $\langle
N^{\prime}\cup\\{\beta\\}\rangle_{N}$ are isomorphic as groups. Since the
reducts of $\mathcal{M}$ and $\mathcal{N}$ to $L$ are models of $T$, there is
certainly such an element $\beta$ in $N$. So the point is to find $\beta$ in a
way that that isomorphism of groups is indeed an $L_{P}$-isomorphism.

By saturation, it suffices to find $\beta\in N$ satisfying a given finite
fragment of $(*)$. So let $a_{1},\dots,a_{m}\in M^{\prime}$,
$k_{1},\dots,k_{m}\in\mathbb{Z}$, $n_{1},\dots,n_{m}\in\mathbb{N}_{+}$, and
$\gamma_{1},\dots,\gamma_{m}\in M$ be such that
$a_{i}+k_{i}\alpha=n_{i}\gamma_{i}$ for each $i$. Then we need to find
$\beta,\delta_{1},\dots,\delta_{m}\in N$ such that
$f(a_{i})+k_{i}\beta=n_{i}\delta_{i}$ and $\delta_{i}\in P$ if and only if
$\gamma_{i}\in P$ for every $i$.

Let $\nu=\operatorname{lcm}(n_{1},\dots,n_{m})$, and let
$d\in\\{0,\dots,\nu-1\\}$ and $\alpha^{\prime}\in M$ be such that
$\alpha=d+\nu\alpha^{\prime}$. Then
$\gamma_{i}=a_{i}^{\prime}+k_{i}^{\prime}\alpha^{\prime}$, where
$n_{i}a_{i}^{\prime}=a_{i}+k_{i}d$ and $k_{i}^{\prime}=\frac{k\nu}{n_{i}}$.
Since $M^{\prime}$ is pure in $M$, it contains $a_{i}^{\prime}$. Therefore it
suffices to find $\beta^{\prime}\in N$ such that for every $i$:

$a_{i}^{\prime}+k_{i}^{\prime}\alpha^{\prime}\in P\Longleftrightarrow
f(a_{i}^{\prime})+k_{i}^{\prime}\beta^{\prime}\in P$

Taking $\vec{k}=(k_{1}^{\prime},\dots,k_{n}^{\prime})$ and
$I=\\{i:a_{i}^{\prime}+k_{i}^{\prime}\alpha^{\prime}\in P\\}$, we have

$\mathcal{M}\models\phi_{\vec{k},I}(a_{1}^{\prime},\dots,a_{n}^{\prime}).$

Hence

$\mathcal{M}\models\psi_{\vec{k},I}(a_{1}^{\prime},\dots,a_{n}^{\prime})\text{
and
}\mathcal{M}^{\prime}\models\psi_{\vec{k},I}(a_{1}^{\prime},\dots,a_{n}^{\prime}).$

Thus

$\mathcal{N}^{\prime}\models\psi_{\vec{k},I}\left(f(a_{1}^{\prime}),\dots,f(a_{n}^{\prime})\right)\text{
and
}\mathcal{N}\models\psi_{\vec{k},I}\left(f(a_{1}^{\prime}),\dots,f(a_{n}^{\prime})\right).$

As a result
$\mathcal{N}\models\phi_{\vec{k},I}(f(a_{1}^{\prime}),\dots,f(a_{n}^{\prime}))$
and hence there is $\beta^{\prime}\in N$ with the desired property:

$f(a_{i}^{\prime})+k_{i}^{\prime}\beta^{\prime}\in P\Longleftrightarrow i\in
I\Longleftrightarrow a_{i}^{\prime}+k_{i}^{\prime}\alpha^{\prime}\in P.$

∎

###  4.1. Quantifier Elimination and Axiomatization

The theory $T_{r}$ does not have quantifier elimination for the obvious reason
that for any $n>1$, the definable subgroup consisting of elements divisible by
$n$ is not quantifier-free definable. However, we still do not get quantifier
elimination after adding predicate symbols to represent those subgroups,
because we also need to know whether the element obtained by dividing by $n$
is in $P$ or not. So for every $n\geq 1$ we add two new unary predicate
symbols $D_{n,+}$ and $D_{n,-}$ to the language $L_{P}$ to obtain $L_{\pm}$
and let $T_{\pm}$ be the definitional extension of $T_{r}$ to an
$L_{\pm}$-theory by adding the following for each $n\geq 1$:

$\forall x\big{(}D_{n,+}(x)\leftrightarrow\exists y(x=ny\wedge y\in P)\big{)}$
$\forall x\big{(}D_{n,-}(x)\leftrightarrow\exists y(x=ny\wedge y\notin
P)\big{)}$

Therefore, every model $\mathcal{M}$ of $T_{r}$ expands to a model of
$T_{\pm}$; we still denote this extension by $\mathcal{M}$. Note that for a
model $\mathcal{M}$ of $T_{\pm}$, we have $D_{n,+}(\mathcal{M})\cup
D_{n,-}(\mathcal{M})=nM$ for every $n\geq 1$ and
$D_{1,+}(\mathcal{M})=P(\mathcal{M})$.

Now we are ready to prove Theorem 1.2 in a stronger form.

######  Theorem 4.2.

The theory $T_{\pm}$ has quantifier elimination.

###### Proof.

It suffices to prove the following:

$(\dagger)$ Let $\mathcal{M}$ and $\mathcal{N}$ be models of $T_{\pm}$ and
$\mathcal{A}$ a common finitely generated

$L_{\pm}$-substructure of $\mathcal{M}$ and $\mathcal{N}$. Then
$\mathcal{M}\equiv_{A}\mathcal{N}$. (This means that

$\mathcal{M}$ and $\mathcal{N}$ are elementarily equivalent as
$L_{\pm}(A)$-structures )

(For why this is enough, see, for instance, Proposition 18.2 of [5].)

We may assume that $\mathcal{M}$ and $\mathcal{N}$ are $\aleph_{0}$-saturated.
Let

$M^{\prime}=\langle A\rangle_{M}\text{ and }N^{\prime}=\langle A\rangle_{N}.$

Clearly, $M^{\prime}$ and $N^{\prime}$ are isomorphic as abelian groups via a
map extending the identity map on $A$. If $n\alpha=a$ for some $a\in A$ and
$\alpha\in M$, then there is $\beta\in N$ with $n\beta=a$. Then the
isomorphism sends $\alpha$ to $\beta$. But we also have $\alpha\in
P(\mathcal{M})$ if and only if $\beta\in P(\mathcal{N})$, since either both
$\mathcal{M}$ and $\mathcal{N}$ satisfy $D_{n,+}(a)$ or they both satisfy
$D_{n,-}(a)$. Therefore $M^{\prime}$ and $N^{\prime}$ are underlying sets of
$L_{\pm}$-substructures $\mathcal{M}^{\prime}$ and $\mathcal{N}^{\prime}$ of
$\mathcal{M}$ and $\mathcal{N}$ respectively, and they are isomorphic. Since
$M^{\prime}$ and $N^{\prime}$ are countable and pure in $M$ and $N$, that
isomorphism is in $\mathfrak{B}(\mathcal{M},\mathcal{N})$. It follows that
$\mathcal{M}\equiv_{M^{\prime}}\mathcal{N}$ and in particular
$\mathcal{M}\equiv_{A}\mathcal{N}$. ∎

Given $\aleph_{0}$-saturated models $\mathcal{M}$ and $\mathcal{N}$ of
$T_{r}$, we may still have that
$\mathfrak{B}(\mathcal{M},\mathcal{N})=\emptyset$. So in order to get
completeness we extend $T_{\pm}$ to $T_{r}^{*}$ by adding _$\mathbb{Z}$
-axioms_: Given $k\in\mathbb{N}_{+}$ if $k\in P_{r}$, then we add the axiom
$k\in P$, otherwise we add the axiom $k\notin P$. (Recall that $1$ is in the
language, so $k=1+\dots+1$.) Clearly, $T_{r}^{*}$ still has quantifier
elimination.

With this extension, we get Theorem 1.3.

######  Theorem 4.3.

The theory $T_{r}^{*}$ is complete.

###### Proof.

Clearly, $\mathfrak{Z}$ is an algebraically prime model of $T_{r}^{*}$ . Since
$T_{r}^{*}$ has quantifier elimination, we get that $T_{r}^{*}$ is complete. ∎

Question. According to this theorem each $T_{r}^{*}$ is a completion of
$T_{r}$. Is it correct that each completion of $T_{r}$ is given as the theory
of an expansion of the group of integers by a Beatty Sequence?

##  5\. Definable Sets

When dealing with the definable sets, we constantly switch between
$\mathfrak{Z}$ and the isomorphic structure

$\mathfrak{G}:=\big{(}\Gamma_{r},\cdot,^{-1},1,h(1),P_{r}\big{)},$

where $P_{r}$ denotes the interval $\big{(}h(-1),1\big{)}\cap\Gamma_{r}$ of
$\Gamma_{r}$.

For a subset $X$ of $\Gamma_{r}^{n}$ and $m>0$ we let

$X^{(m)}:=\big{\\{}(x_{1}^{m},\dots,x_{n}^{m}):\vec{x}\in X\big{\\}},\text{
and}$ $X^{1/m}:=\\{\vec{y}\in\Gamma_{r}^{n}:(y_{1}^{m},\dots,y_{n}^{m})\in
X\\}.$

For a subset $A$ of $\mathbb{S}$, we define $[A]$ to be the subgroup of
$\mathbb{S}$ generated by $A$ and

$\langle A\rangle:=\left\\{\alpha\in\mathbb{S}:\alpha^{m}\in[A]\text{ for some
}m>0\right\\}.$

We collect some easy facts about these notions.

######  Lemma 5.1.

Let $X,Y\subseteq\Gamma_{r}^{n}$ and $m>0$.

  1. (1)

$D_{m,+}^{1/m}=P_{r}$ and $P_{r}^{(m)}=D_{m,+}$.

  2. (2)

$(X^{(m)})^{1/m}=X$ and $(X^{1/m})^{(m)}=X\cap(\Gamma_{r}^{n})^{(m)}$

  3. (3)

$(X\cap Y)^{1/m}=X^{1/m}\cap Y^{1/m}$, $(X\cup Y)^{1/m}=X^{1/m}\cup Y^{1/m}$,
and $(\Gamma_{r}^{n}\setminus X)^{1/m}=\Gamma_{r}^{n}\setminus X^{1/m}$.

  4. (4)

For $\vec{a}\in(\\{0,\dots,m-1\\})^{n}$, let
$X_{\vec{a}}=h(\vec{a})X\cap(\Gamma_{r}^{n})^{(m)}$. Then

$X=\bigcup_{\vec{a}}h(-\vec{a})X_{\vec{a}}.$

Before analyzing definable sets in detail, we would like to clarify the
connection with the paper [9].

######  Lemma 5.2.

Let $m>0$ and let $X=(\alpha,\beta)\cap\Gamma_{r}^{(m)}$. Then any set
$(\alpha\gamma_{1},\beta\gamma_{2})\cap\Gamma_{r}^{(m)}$ with
$\gamma_{1},\gamma_{2}\in\Gamma_{r}^{(m)}$ is definable in
$(\Gamma_{r},\cdot,X)$.

###### Proof.

It suffices to show that $Y=(\alpha,\beta\gamma)\cap\Gamma_{r}^{(m)}$ is
definable in $(\Gamma_{r},\cdot,X)$, where $\gamma=\gamma_{2}\gamma_{1}^{-1}$.

Let $\lambda=\beta\alpha^{-1}$ and take
$\delta\in(\lambda^{1/2},\lambda)\cap\Gamma_{r}^{(m)}$. Suppose that $n$ is
the largest natural number such that $\gamma\delta^{-n}<\lambda$.

Then $Y$ is the following union:

$Y=X\cup\delta
X\cup\dots\cup\delta^{n}X\cup((\alpha\delta^{n+1},\beta\gamma)\cap\Gamma_{r}^{(m)}),$

Note that

$(\alpha\delta^{n+1},\beta\gamma)\cap\Gamma_{r}^{(m)}=\delta^{n+1}(X\cap\gamma(\delta^{n+1})^{-1}X).$

So $Y$ is definable in $(\Gamma_{r},\cdot,X)$. ∎

Letting $X=P_{r}$ in this lemma, we have the following consequence.

######  Corollary 5.3.

Any interval of $\Gamma_{r}$ is definable in $\mathfrak{G}$.

Therefore, the structures $\mathfrak{G}$ and
$\big{(}\Gamma_{r},\cdot,\mathcal{O}\big{)}$ are interdefinable, where
$\mathcal{O}$ is the restriction of the orientation of $\mathbb{S}$ to
$\Gamma_{r}$. In [9], the authors study the latter structure; or rather the
pull-back of it under $h$. Even though some of our results are slightly finer
than theirs, they also work out some stability theoretic properties of this
structure. Most notably, they show that it is dp-minimal.

We appeal to the topology on $\Gamma_{r}^{n}$ induced from $\mathbb{S}^{n}$ in
order to study definable sets. An open basis for that topology on $\Gamma_{r}$
consists of sets of the form $I\cap\Gamma_{r}$ where $I$ is an open interval
of $\mathbb{S}$; below we refer to these sets as _convex_ sets. From now on we
use the word _interval_ to mean _open interval of $\Gamma_{r}$_; so an
interval is a convex set whose end points are in $\Gamma_{r}$.

The quantifier elimination result in the previous section gives a very simple
characterization of definable sets in a model $\mathcal{M}$ of $T_{r}^{*}$:
They are Boolean combinations of sets defined by formulas of the form

$a+\vec{k}\vec{x}=0,D_{m,+}(a+\vec{k}\vec{x})\text{,and
}D_{m,-}(a+\vec{k}\vec{x})$

where $\vec{x}=(x_{1},\dots,x_{n})$ is a tuple of variables, $a\in M$ and
$\vec{k}\in\mathbb{Z}^{n}$.

It is simpler in the sense that the negations of formulas
$D_{m,+}(a+\vec{k}\vec{x})$ and $D_{m,-}(a+\vec{k}\vec{x})$ define sets that
are finite unions of sets defined by the same kind of formulas. Also we would
like to consider the formula

$D_{m,-}(a+\vec{k}\vec{x})\wedge a+\vec{k}\vec{x}\neq 0\wedge
a+\vec{k}\vec{x}\neq-m$

in the place of $D_{m,-}(a+\vec{k}\vec{x})$.

So any definable set in $\mathfrak{G}$ is of the form

($*$) $\bigcup_{i=1}^{s}\bigcap_{j=1}^{t_{i}}X_{ij},$

where each $X_{ij}$ is one of the following forms

(A) $\\{\vec{x}\in\Gamma_{r}^{n}:\vec{x}^{\vec{k}}h(a)=1\\}$

(B) $\\{\vec{x}\in\Gamma_{r}^{n}:\vec{x}^{\vec{k}}h(a)\neq 1\\}$

(C) $\\{\vec{x}\in\Gamma_{r}^{n}:\vec{x}^{\vec{k}}h(a)\in P_{r}^{(m)}\\}$

(D) $\\{\vec{x}\in\Gamma_{r}^{n}:\vec{x}^{\vec{k}}h(a)\in Q_{r}^{(m)}\\}$

where $\vec{k}=(k_{1},\dots,k_{n})\in\mathbb{Z}^{n}\setminus\\{\vec{0}\\}$,
$a\in\mathbb{Z}$, $m>0$, $\vec{x}^{\vec{k}}:=x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots
x_{n}^{k_{n}}$, and $Q_{r}=(1,h(-1))\cap\Gamma_{r}$.

Note that a set of the form (A) is nonempty if and only if $\kappa|a$ where
$\kappa$ is the greatest common divisor of the integers $k_{i}$. We refer to a
finite intersection of sets of the form (A) as an _affine subset_ of
$\Gamma_{r}^{n}$ provided that it is nonempty. Affine subsets of $\Gamma_{r}$
are singletons, and if $Y$ is an affine subset of $\Gamma_{r}^{n}$ with $n>1$,
then there is a projection $\pi:\Gamma_{r}^{n}\to\Gamma_{r}^{d}$ with $d<n$
such that $\pi|_{Y}$ is injective. Also for an affine subset $Y$,
$\vec{b}\in\mathbb{Z}^{n}$, and $N>0$, the set $(h(\vec{b})Y)^{1/N}$ is either
empty or an affine subset.

Suppose that $Y$ is a set of the form (C) or (D), $\vec{b}\in\mathbb{Z}^{n}$,
and let $N\in\mathbb{N}_{+}$ be a multiple of $m$. Then the set
$(h(\vec{b})Y)^{1/N}$ is nonempty if and only if $m|a-\vec{k}\vec{b}$, and in
that case

$(h(\vec{b})Y)^{1/N}=\Big{\\{}\vec{y}:(\vec{y}^{\vec{k}})^{N/m}\in
h(\frac{\vec{k}\vec{b}-a}{m})I\Big{\\}},$

where $I$ is one of $P_{r}$ or $Q_{r}$. As a result, it is an open subset of
$\Gamma_{r}^{n}$.

Putting these together we have the following result.

######  Proposition 5.4.

Let $X$ be definable in $\mathfrak{G}$. Then there is $N\in\mathbb{N}_{+}$
such that for every $\vec{b}\in\mathbb{Z}^{n}$ the set $(h(\vec{b})X)^{1/N}$
is a union of an open set and finitely many subsets of affine sets.

###### Proof.

Write $X$ as in ($*$), and let $N$ be the lowest common multiple of the
integers $m$ appearing in the formulas defining the sets $X_{ij}$. Given
$i\in\\{1,\dots,s\\}$, if one of the sets $X_{ij}$ is of the form (A), then
the set

$(h(\vec{b})\bigcap_{j}X_{ij})^{1/N}=\bigcap_{j}(h(\vec{b})X_{ij})^{1/N}$

is contained in an affine set. Otherwise this set is open as noted above. ∎

Now we focus on unary definable sets with the aim of proving Theorem 1.1.
Combined with Proposition 2.2, Proposition 5.4 gives the following for unary
subsets of $\Gamma_{r}$.

######  Corollary 5.5.

Suppose that $X\subseteq\Gamma_{r}$ is definable in $\mathfrak{G}$. Then there
is $N\in\mathbb{N}_{+}$ such that for every $n\in\\{0,1,\dots,N-1\\}$, the set
$(h(n)X)^{1/N}$ is a finite union of convex sets and singletons. Moreover, the
end points of the convex sets are in $\langle\Gamma_{r}\rangle$.

###### Proof.

Affine subsets of $\Gamma_{r}$ are singletons and the open set appearing in
$(h(n)X)^{1/N}$ is a certain positive Boolean combination of sets of the form:

$\Big{\\{}y\in\Gamma_{r}:y^{kN}\neq h(-n)\Big{\\}}.$

and

$\Big{\\{}y\in\Gamma_{r}:y^{kN/m}\in h(\frac{kb-n}{m})I\Big{\\}}$

where $I$ is one of $P_{r}$ or $Q_{r}$.

Using Proposition 2.2, if such a combination is not empty, then it is a finite
union of convex sets whose end points are in $\langle\Gamma_{r}\rangle$. ∎

######  Definition 5.6.

Let $X\subseteq\mathbb{Z}$. We say that $X$ has the _uniform gaps property_ if
there is $M\in\mathbb{N}_{+}$ such that

$X\cap\\{x+1,\dots,x+M\\}\neq\emptyset$

for every $x\in X$.

Clearly, $\emptyset$ has the uniform gaps property and it is the only finite
set that has the uniform gaps property. The following is also clear.

######  Lemma 5.7.

If $X,Y\subseteq\mathbb{Z}$ have the uniform gaps property. Then $X\cup Y$ has
the uniform gaps property.

######  Lemma 5.8.

If $C\subseteq\Gamma_{r}$ is a convex set, then $X=h^{-1}(C)$ has the uniform
gaps property.

###### Proof.

Let $C=(\alpha,\beta)\cap\Gamma_{r}$ and let $\gamma:=l(C)$. Take
$m,n\in\mathbb{N}_{+}$ such that $h(m)<\gamma^{1/2}$ and $h(-n)<\gamma^{1/2}$.
We claim that $M=\max\\{m,n\\}$ witnesses that $X$ has the uniform gaps
property.

Suppose that $x\in X$. If $h(x)<\alpha\gamma^{1/2}$, then $h(x)h(m)\in C$ and
hence $x+m\in X$, and if $\alpha\gamma^{1/2}<h(x)$, then $h(x)h(n)\in C$ and
hence $x+n\in X$. ∎

_Remark._ This proof does not work for larger models of $T_{r}^{*}$, because
the length of $C$ might be infinitesimal with respect to $\Gamma_{r}$ and
hence we cannot find suitable $m$ and $n$.

The following is Theorem 1.1 from the Introduction.

######  Theorem 5.9.

Every infinite subset of $\mathbb{Z}$ definable in $\mathfrak{Z}$ has the
uniform gaps property.

###### Proof.

Let $X\subseteq\mathbb{Z}$ be definable in $\mathfrak{Z}$ and let $Y:=h(X)$.

By Corollary 5.5, there is $N>0$ such that $(h(n)Y)^{1/N}$ is a finite union
of convex sets and singletons for each $n\in\\{0,1,\dots,N-1\\}$.

Using the second and the last part of Lemma 5.1

$Y=\bigcup_{n=0}^{N-1}h(-n)((h(n)Y)^{1/N})^{(N)}.$

Therefore by Lemma 5.7, it suffices to show that
$h^{-1}\big{(}((h(n)Y)^{1/N})^{(N)}\big{)}$ has the uniform gaps property for
each $n$. Since $y\in((h(n)Y)^{1/N})^{(N)}$ if and only if $y=z^{N}$ for some
$z\in(h(n)Y)^{1/N}$, it suffices to show that
$h^{-1}\big{(}(h(n)Y)^{1/N}\big{)}$ has the uniform gaps property. It is
indeed the case using Lemmas 5.7 and 5.8. ∎

######  Corollary 5.10.

Let $X$ be an infinite subset of $\mathbb{Z}$ that is definable in
$\mathfrak{Z}$. Then there is $M\in\mathbb{N}_{+}$ such that for every $x\in
X$, the intersection $X\cap\\{x-1,x-2,\dots,x-M\\}$ is nonempty.

###### Proof.

The set $-X:=\\{y\in\mathbb{Z}:-y\in X\\}$ is also definable in $\mathfrak{Z}$
and hence has the uniform gaps property. That translates to $X$ as the
conclusion of the corollary. ∎

######  Corollary 5.11.

Ordering of $\mathbb{Z}$ is not definable in $\mathfrak{Z}$.

###### Proof.

If the ordering were definable in $\mathfrak{Z}$, then so would be the set of
positive elements. However, $\mathbb{N}_{+}$ does not satisfy the conclusion
of Corollary 5.10. ∎

######  Corollary 5.12.

Multiplication is not definable in $\mathfrak{Z}$.

###### Proof.

If multiplication on $\mathbb{Z}$ is definable, then the ordering of
$\mathbb{Z}$ is also definable using Lagrange’s four-square theorem. ∎

We need the following lemma to show that $\mathfrak{Z}$ is unstable.

######  Lemma 5.13.

Let $n>0$, then there is $m>0$ such that $m,2m,\dots,nm\in P_{r}$ and
$-m,-2m,\dots,-nm\notin P_{r}$.

###### Proof.

Let $\alpha=\min\\{h(1),h(-1)\\}$ and $\beta=\alpha^{\frac{1}{n+1}}$. By
regular density of $\Gamma_{r}$ take $m\in\mathbb{N}_{+}$ such that
$\beta^{-1}<h(m)$. Clearly, this $m$ satisfies the conclusion of the lemma. ∎

######  Proposition 5.14.

The theory $T_{r}^{*}$ is not stable.

###### Proof.

Let $\phi(x;y)$ be the $L_{P}$-formula $y-x\in P$. We show that this formula
is unstable. For this, it suffices to prove the following: For every $n>0$,
there are $a_{1},\dots,a_{n}\in\mathbb{Z}$ such that

$\mathfrak{Z}\models\phi(a_{i},a_{j})\Longleftrightarrow i<j.$

So let $n>0$ be given. Take $a_{i}=im$ where $m=m(n)$ is as in the lemma
above. Now $a_{j}-a_{i}=(j-i)m$ and hence $\phi(a_{i},a_{j})$ holds in
$\mathfrak{Z}$ if and only if $i<j$.

∎

(We would like to thank Haydar Göral for the idea of this proof.)

##  6\. No Reducts

We prove that there are no intermediate structures between $(\mathbb{Z},+)$
and $(\mathbb{Z},+,P_{r})$; actually we prove the same result for
$(\Gamma_{r},\cdot)$ and $(\Gamma_{r},\cdot,P_{r})$.

We first consider a subset $X$ of $\Gamma_{r}$ that is definable in
$\mathfrak{G}$.

######  Proposition 6.1.

Let $X\subseteq\Gamma_{r}$ be definable in $\mathfrak{G}$. Suppose that $X$ is
not definable in $(\Gamma_{r},\cdot)$. Then there is $N>0$ and
$L\in\\{0,1,\dots,N-1\\}$ such that both the set $(h(L)X)^{1/N}$ and its
complement contain a convex set.

###### Proof.

By Corollary 5.5, there is $N>0$ such that for each $n$, the set
$(h(n)X)^{1/N}$ is a finite union of convex sets with end points in
$\langle\Gamma_{r}\rangle$, and singletons. Write

$X=\bigcup_{n=0}^{N-1}h(-n)(h(n)X\cap\Gamma_{r}^{(N)}).$

For each $n$, raising to power $N$ is a bijection between the sets
$(h(n)X)^{1/N}$ and $h(n)X\cap\Gamma_{r}^{(N)}$. Since $X$ is not definable in
$(\Gamma_{r},\cdot)$, there is $L\in\\{0,\dots,N-1\\}$ such that
$(h(L)X)^{1/N}$ is infinite. If $(h(L)X)^{1/N}$ is cofinite in $\Gamma_{r}$,
then so is $h(L)X\cap\Gamma_{r}^{(N)}$. Once again, since $X$ is not definable
in $(\Gamma_{r},\cdot)$, $h(L)X\cap\Gamma_{r}^{(N)}$ cannot be cofinite in
$\Gamma_{r}$. Therefore both $(h(L)X)^{1/N}$ and its complement contains a
convex set. ∎

So if $N$ and $L$ are as in this proposition, both $(h(L)X)^{1/N}$ and its
complement are finite unions of convex sets and singletons, but neither is
finite. Moreover, by Corollary 5.5, the end points of the convex sets
appearing in either union are in $\langle\Gamma_{r}\rangle$. Therefore there
is a finite union of convex sets with end points in $\langle\Gamma_{r}\rangle$
that is definable in $(\Gamma_{r},\cdot,X)$ and is not cofinite in
$\Gamma_{r}$.

######  Lemma 6.2.

Let $X=(\alpha,\beta)\cap\Gamma_{r}^{(m)}$ and suppose that
$\gamma:=\alpha\beta\in\Gamma_{r}$. Then a convex set is definable in
$(\Gamma_{r},\cdot,X)$. Moreover, the end points of that convex set are in
$\langle\Gamma_{r}\cup\\{\alpha,\beta\\}\rangle$.

###### Proof.

Let $0\leq n<m$ be such that $\gamma\in h(n)\Gamma_{r}^{(m)}$.

We first consider the case that $n\neq 0$. Let $k:=\gcd(n,m)$,
$n^{\prime}=n/k$, and $m^{\prime}=m/k$. So
$\gamma=h(n)\gamma_{0}^{m}=(h(n^{\prime})\gamma_{0}^{m^{\prime}})^{k}$ for
some $\gamma_{0}\in\Gamma_{r}$.

Let $l\in\mathbb{Z}$ be such that
$h(n^{\prime})\gamma_{0}^{m^{\prime}}\in(\zeta_{k}^{l},\zeta_{k}^{l+1})$. Also
let

$\delta_{0}\in((\beta^{1/k})^{-1}\zeta_{k}^{-l},(\beta^{1/k})^{-1}\zeta_{k}^{-l+1})\cap\gamma_{0}^{-m^{\prime}}\Gamma_{r}^{(m)}\text{,
and }\delta=\delta_{0}^{k}.$

By Lemma 5.2, the set $Y:=(\alpha,\beta\delta)\cap\Gamma_{r}^{(m)}$ is
definable in $(\Gamma_{r},\cdot,X)$ and using Lemma 2.3 we have that
$\gamma_{Y}:=\alpha^{1/k}(\beta\delta)^{1/k}\in
h(n^{\prime})\Gamma_{r}^{(m)}$. In particular,
$\\{1,\gamma_{Y},\gamma_{Y}^{2},\dots,\gamma_{Y}^{m-1}\\}$ is a full set of
representatives of cosets of $\Gamma_{r}^{(m)}$ in $\Gamma_{r}$.

By Proposition 2.2

$Y^{1/k}=\bigcup_{s=0}^{k-1}\zeta_{k}^{s}(\alpha^{1/k},(\beta\delta)^{1/k})\cap\Gamma_{r}^{(m^{\prime})}.$

Take $\tau_{1},\tau_{2}\in\Gamma_{r}^{(m)}$ such that
$(\alpha^{1/k},(\beta\delta)^{1/k})\subseteq(\alpha\tau_{1},\beta\tau_{2})$
and $l((\alpha\tau_{1},\beta\tau_{2}))<\zeta_{k}$. The set
$(\alpha\tau_{1},\beta\tau_{2})\cap\Gamma_{r}^{(m)}$ is definable in
$(\Gamma_{r},\cdot,X)$ by Lemma 5.2 and hence

$Z:=((\alpha\tau_{1},\beta\tau_{2})\cap\Gamma_{r}^{(m)})\cap
Y^{1/k}=(\alpha^{1/k},(\beta\delta)^{1/k})\cap\Gamma_{r}^{(m)}.$

is also definable in $(\Gamma_{r},\cdot,X)$.

Let $f:\Gamma_{r}\to\Gamma_{r}$ be defined as $f(x)=x^{-1}\gamma_{Y}$. It is
clear that

$x\in(\alpha^{1/k},(\beta\delta)^{1/k})\Longleftrightarrow
f(x)\in(\alpha^{1/k},(\beta\delta)^{1/k}).$

Therefore
$f^{i}(Z)=(\alpha^{1/k},(\beta\delta)^{1/k})\cap\gamma_{Y}^{i}\Gamma^{(m)}$
for $i=0,1,\dots,m-1$. Hence the proper convex set

$(\alpha^{1/k},(\beta\delta)^{1/k})\cap\Gamma_{r}=Z\cup f(Z)\cup\dots\cup
f^{m-1}(Z)$

is definable in $(\Gamma_{r},\cdot,X)$.

Now let $n=0$ and take $k>0$ maximum such that
$\gamma\in\Gamma_{r}^{(m^{k})}$; say $\gamma=\gamma_{0}^{m^{k}}$ with
$\gamma_{0}\in(\zeta_{m^{k}}^{l},\zeta_{m^{k}}^{l+1})\cap\Gamma_{r}$.

Let

$\delta_{0}\in((\beta^{1/m^{k}})^{-1}\zeta_{m^{k}}^{-l},(\beta^{1/m^{k}})^{-1}\zeta_{m^{k}}^{-l+1})\cap(\Gamma_{r}\setminus\gamma_{0}^{-1}\Gamma_{r}^{(m)})\text{
and }\delta:=\delta_{0}^{m^{k}}.$

As in the previous case, we have $Y=(\alpha,\beta\delta)\cap\Gamma_{r}^{(m)}$
is definable in $(\Gamma_{r},\cdot,X)$ and

$Y^{1/m^{k}}=\bigcup_{s=0}^{m^{k}-1}\zeta_{m^{k}}^{s}(\alpha^{1/m^{k}},(\beta\delta)^{1/m^{k}})\cap\Gamma_{r}.$

Again, there are $\tau_{1},\tau_{2}\in\Gamma^{(m)}$ such that

$Z:=((\alpha\tau_{1},\beta\tau_{2})\cap\Gamma_{r}^{(m)})\cap
Y^{1/m^{k}}=(\alpha^{1/m^{k}},(\beta\delta)^{1/m^{k}})\cap\Gamma_{r}^{(m)}.$

Now we have
$\gamma^{*}:=\alpha^{1/m^{k}}(\beta\delta)^{1/m^{k}}=\gamma_{0}\delta_{0}$ is
not in $\Gamma_{r}^{(m)}$. Therefore using the previous case a proper convex
set is definable in $(\Gamma_{r},\cdot,Z)$, hence in $(\Gamma_{r},\cdot,X)$.

It follows from the proof that the end points of the proper convex set are in
$\langle\Gamma_{r}\cup\\{\alpha,\beta\\}\rangle$.

∎

######  Lemma 6.3.

Let $X=(\alpha,\beta)\cap\Gamma_{r}$ and $m>0$ with
$l(\alpha,\beta)<\zeta_{m}$. Then for $0<k\leq m$:

$\\{x_{1}x_{2}\cdots x_{k}:x_{1},x_{2},\dots,x_{k}\in
X\\}=(\alpha^{k},\beta^{k})\cap\Gamma_{r}$

###### Proof.

Let

$Y_{k}:=\\{x_{1}x_{2}\cdots x_{k}:x_{1},x_{2},\dots,x_{k}\in X\\}.$

It is clear from the assumptions that
$Y_{k}\subseteq(\alpha^{k},\beta^{k})\cap\Gamma_{r}$. We prove equality by
induction on $k$.

The case $k=1$ is trivial, so let $k>1$ and suppose that
$Y_{k-1}=(\alpha^{k-1},\beta^{k-1})\cap\Gamma_{r}$. Then

$\displaystyle Y_{k}$ $\displaystyle=\bigcup_{x_{k}\in X}Y_{k-1}\,x_{k}$
$\displaystyle=\bigcup_{x_{k}\in
X}((\alpha^{k-1},\beta^{k-1})\cap\Gamma_{r})x_{k}$
$\displaystyle=\bigcup_{x_{k}\in
X}(x_{k}\alpha^{k-1},x_{k}\beta^{k-1})\cap\Gamma_{r}.$

Clearly, the last union is a convex set. Since $\alpha^{k}$ and $\beta^{k}$
are limit points of $Y_{k}$ (in $\mathbb{S}$), we get

$Y_{k}=(\alpha^{k},\beta^{k})\cap\Gamma_{r}.$

∎

######  Corollary 6.4.

Let $X=(\alpha,\beta)\cap\Gamma_{r}$, where
$\alpha,\beta\in\langle\Gamma_{r}\rangle$. Then an interval is definable in
$(\Gamma_{r},\cdot,X)$.

###### Proof.

Let $N\in\mathbb{N}_{+}$ such that $\alpha^{N},\beta^{N}\in\Gamma_{r}$, and
take $\gamma\in\Gamma_{r}$ such that $l((\alpha,\beta\gamma))<\zeta_{N}$. Then
$(\alpha^{N},\beta^{N}\gamma^{N})\cap\Gamma_{r}$ is an interval and is
definable in $(\Gamma_{r},\cdot,X)$ by Lemma 6.3. ∎

######  Lemma 6.5.

Let $X$ be a finite union of convex sets whose end points are in
$\langle\Gamma_{r}\rangle$. If $X$ is not cofinite in $\Gamma_{r}$, then an
interval is definable in $(\Gamma_{r},\cdot,X)$.

###### Proof.

After translating, we may assume that $1\notin X$.

Let $X=\bigcup_{i=1}^{m}C_{i}$ where
$C_{i}=(\alpha_{i},\beta_{i})\cap\Gamma_{r}$ with

$\alpha_{1}<\beta_{1}\leq\alpha_{2}<\beta_{2}\leq\dots\leq\alpha_{m}<\beta_{m}.$

We prove the result by induction on $m$. If $m=1$, then there is nothing to
do. So suppose $m>1$.

Put $\lambda_{j}=\beta_{j}\alpha_{j}^{-1}$ for all $j$, and
$\delta_{j}=\alpha_{j+1}\beta_{j}^{-1}$ for $j=1,\dots,m$, where
$\alpha_{m+1}:=\alpha_{1}$.

Below we consider three cases and in each one we construct a convex set
definable in $(\Gamma_{r},\cdot,X)$. Moreover the end points of those convex
sets will still be in $\langle\Gamma_{r}\rangle$. Hence by using Corollary
6.4, we will be done.

Case 1: The set $\\{\delta_{1},\dots,\delta_{m}\\}$ is not a singleton.

Let $\delta_{j_{0}}$ and $\delta_{j_{1}}$ be the two smallest elements of this
set and let
$\lambda=\min\\{\delta_{j_{1}}\delta_{j_{0}}^{-1},\lambda_{1},\dots,\lambda_{m}\\}$.
Take $\gamma\in(\lambda^{1/2},\lambda)\cap\Gamma_{r}$ and let $N>0$ be such
that

$\gamma<\gamma^{2}<\cdots<\gamma^{N-1}<\delta_{j_{0}}<\gamma^{N}.$

Note that $\gamma^{N}<\delta_{j_{1}}$ and hence the union

$Y:=X\cup\gamma X\cup\gamma^{2}X\cup\dots\cup\gamma^{N}X$

is a union of at most $m-1$ convex sets, yet it has infinite complement in
$\Gamma_{r}$. So by induction hypothesis, there is a nonempty proper convex
subset $C$ of $\Gamma$ that is definable in $(\Gamma_{r},\cdot,Y)$. Since $Y$
is definable in $(\Gamma_{r},\cdot,X)$, the set $C$ is definable in
$(\Gamma_{r},\cdot,X)$.

Case 2: The set $\\{\delta_{1},\dots,\delta_{m}\\}$ is a singleton, but the
set $\\{\lambda_{1},\dots,\lambda_{m}\\}$ is not a singleton.

The set $Z=\Gamma_{r}\setminus X$ is a set as in Case 1. So a nonempty proper
convex subset of $\Gamma$ is definable in $(\Gamma_{r},\cdot,Z)$, hence in
$(\Gamma_{r},\cdot,X)$.

Case 3: Both $\\{\delta_{1},\dots,\delta_{m}\\}$ and
$\\{\lambda_{1},\dots,\lambda_{m}\\}$ are singletons.

Note that we need to have $\delta_{j}\lambda_{j}=\zeta_{m}$ for each $j$.
Hence $\alpha_{j+1}=\zeta_{m}\alpha_{j}$ and $\beta_{j+1}=\zeta_{m}\beta_{j}$
for each $j=1,\dots,m-1$. Therefore

$X=\big{(}\bigcup_{j=0}^{m-1}\zeta_{m}^{j}(\alpha_{1},\beta_{1})\big{)}\cap\Gamma_{r}.$

So $X^{(m)}=(\alpha_{1}^{m},\beta_{1}^{m})\cap\Gamma^{(m)}$. Therefore a
convex set is definable in $(\Gamma_{r},\cdot,X)$ by Lemma 6.2. ∎

Putting Proposition 6.1 and Lemma 6.5 together, we get the desired result for
unary definable sets.

######  Proposition 6.6.

Let $X\subseteq\Gamma_{r}$ be definable in $\mathfrak{G}$, but not in
$(\Gamma_{r},\cdot)$. Then $(\Gamma_{r},\cdot,X)$ is interdefinable with
$\mathfrak{G}$.

Now we handle the general case.

######  Theorem 6.7.

Let $X\subseteq\Gamma_{r}^{n}$ be definable in $\mathfrak{G}$, but not in
$(\Gamma_{r},\cdot)$. Then $(\Gamma_{r},\cdot,X)$ is interdefinable with
$\mathfrak{G}$.

###### Proof.

We proceed by induction on $n$. Proposition 6.6 serves as the case $n=1$. So
let’s assume that $n>1$ and that the result holds for $m<n$.

So let $X\subseteq\Gamma_{r}^{n}$ be definable in $\mathfrak{G}$, and take
$N\in\mathbb{N}_{+}$ such that for every $\vec{a}\in\mathbb{Z}^{n}$, the set
$(h(\vec{a})X)^{1/N}$ is a union of an open set and finitely many sets
contained in affine sets. Write

$X=\bigcup_{\vec{a}\in A}h(-\vec{a})(h(\vec{a})X\cap(\Gamma_{r}^{(N)})^{n}),$

where $A$ is a finite subset of $\mathbb{Z}^{n}$. It is easy to see that for
each $\vec{a}$, the set $(h(\vec{a})X)^{1/N}$ has empty interior if and only
if $h(\vec{a})X\cap(\Gamma_{r}^{(N)})^{n}$ is contained in a finite union of
affine sets.

First suppose that $(h(\vec{a})X)^{1/N}$ has empty interior for each
$\vec{a}\in A$. Then $(h(\vec{a})X)^{1/N}$ is a finite union of sets contained
in an affine set and each of those sets is in bijection with a subset of
$\Gamma_{r}^{d}$ for some $d<n$ via a projection. If all of those subsets of
$\Gamma_{r}^{d}$ are definable in $(\Gamma_{r},\cdot)$, then so is
$(h(\vec{a})X)^{1/N}$. This cannot be correct for all $\vec{a}$, because $X$
is not definable in $(\Gamma_{r},\cdot)$. Hence we obtain a subset of
$\Gamma_{r}^{d}$ that is not definable in $(\Gamma_{r},\cdot)$, but is
definable in $(\Gamma_{r},\cdot,X)$. So we obtain the result using the
induction hypothesis.

So we assume that the set $A^{*}$ of $\vec{a}\in A$ such that
$(h(\vec{a})X)^{1/N}$ has nonempty interior is nonempty. Hence the set

$X^{*}=X\bigcup_{\vec{a}\in
A^{*}}{h(-\vec{a})(h(\vec{a})X\cap(\Gamma^{(N)})^{n})}$

is definable in $(\Gamma_{r},\cdot,X)$ and $(h(\vec{a})X^{*})^{1/N}$ has
nonempty interior for each $\vec{a}\in A^{*}$. Put $Y:=\Gamma_{r}\setminus
X^{*}$. If $(h(\vec{a})Y)^{1/N}$ has empty interior for each $\vec{a}\in
A^{*}$, then we may proceed as in the previous case. Therefore we may assume
that $(h(\vec{a})Y)^{1/N}$ has nonempty interior for some $\vec{a}\in A^{*}$.

For $\vec{\gamma}\in\Gamma_{r}^{n-1}$, consider the sets

$X^{*}_{\vec{\gamma}}:=\\{\delta\in\Gamma_{r}:(\vec{\gamma},\delta)\in(h(\vec{a})X^{*})^{1/N}\\},$
$Y_{\vec{\gamma}}:=\\{\delta\in\Gamma_{r}:(\vec{\gamma},\delta)\in(h(\vec{a})Y)^{1/N}\\}$

For each $\vec{\gamma}$, these sets are either empty or has nonempty interior.
If there is $\vec{\gamma}\in\Gamma_{r}^{n-1}$ such that both
$X^{*}_{\vec{\gamma}}$ and $Y_{\vec{\gamma}}$ have nonempty interior, then
$X^{*}_{\vec{\gamma}}$ is not definable in $(\Gamma_{r},\cdot)$, and we are
done using the induction hypothesis. Otherwise for each
$\vec{\gamma}\in\Gamma_{r}^{n-1}$, the set $X^{*}_{\vec{\gamma}}$ is either
empty or is $\Gamma_{r}$. Then the set
$Z:=\\{\vec{\gamma}:X^{*}_{\vec{\gamma}}=\Gamma_{r}\\}$ is a subset of
$\Gamma_{r}^{n-1}$ definable in $(\Gamma_{r},\cdot,X)$. If $Z$ is definable in
$(\Gamma_{r},\cdot)$, then so are $(h(\vec{a})X^{*})^{1/N}$ and $X$. Therefore
$Z$ is not definable in $(\Gamma_{r},\cdot)$ and once again we are done by the
induction hypothesis.

∎

## References

  * [1] Jean-Paul Allouche and Jeffrey Shallit.  Automatic sequences.  Cambridge University Press, Cambridge, 2003.  Theory, applications, generalizations.
  * [2] Gabriel Conant.  Multiplicative structure in stable expansions of the group of integers.  Illinois J. Math., 62(1-4):341–364, 2018.
  * [3] Gabriel Conant.  There are no intermediate structures between the group of integers and Presburger arithmetic.  J. Symb. Log., 83(1):187–207, 2018.
  * [4] Ayhan Günaydın.  Model Theory of Fields with Multiplicative Groups.  PhD thesis, University of Illinois at Urbana-Champaign, 2008.
  * [5] Jonathan Kirby.  An invitation to model theory.  Cambridge University Press, Cambridge, 2019.
  * [6] Quentin Lambotte and Françoise Point.  On expansions of $({\bf Z},+,0)$.  Ann. Pure Appl. Logic, 171(8):102809, 36, 2020.
  * [7] Daniel Palacín and Rizos Sklinos.  On superstable expansions of free Abelian groups.  Notre Dame J. Form. Log., 59(2):157–169, 2018.
  * [8] Bruno Poizat.  Supergénérix.  J. Algebra, 404:240–270, 2014.  À la mémoire d’Éric Jaligot. [In memoriam Éric Jaligot].
  * [9] M.C. Tran and E. Walsberg.  A family of $d_{p}$-minimal expansions of the additive group of integers.  Preprint.


# A Couple of Transcendental Prime-Representing Constants

Juan Luis Varona

###### Abstract

It is well known that the arithmetic nature of Mills’ prime-representing
constant is uncertain: we do not know if Mills’ constant is a rational or
irrational number. In the case of other prime-representing constants,
irrationality can be proved, but it is not known whether these constants are
algebraic or transcendental numbers. By using Liouville or Roth’s theorems
about approximation by rationals, we find a couple of prime-representing
constants that can be proved to be transcendental numbers.

00footnotetext: MSC: Primary 11A41, Secondary 11J81.00footnotetext: This paper
has been accepted for publication in Amer. Math. Monthly, 2020/12/17.

##  1 Introduction

A prime-representing constant is a constant that, by means of some process,
generates infinitely many prime numbers, sometimes all the prime numbers.

The first and best known result about prime-representing constants was
established by Mills in 1947 [6]. He proved that there exists a real number
$\theta$ such that $\lfloor\theta^{3^{n}}\rfloor$ is a prime for every
positive integer $n$ (and where the so-called floor function
$\lfloor\cdot\rfloor$ is used to denote the integer part). The proof of this
fact depends on a result of Ingham that is not elementary [5]: if $p_{n}$
denotes the $n$th prime, then there is a constant $K$ such that
$p_{n+1}-p_{n}<Kp_{n}^{5/8}$ for $n=1,2,\dots$. Assuming Ingham’s theorem,
finding Mills’ constant $\theta$ is not difficult.

There is no closed-form formula known for such $\theta$ and, actually, there
are uncountably many possible values of $\theta$ with the prime-representing
property. Hence, if one wants to define Mills’ constant, a good approach is to
look for the least $\theta$ such that $\lfloor\theta^{3^{n}}\rfloor$ is prime
for $n=1,2,\dots$. In this way, and by making some unproved but reasonable
assumptions (in particular, the Riemann hypothesis), Mills’ constant can be
computed with precision. For instance, [1] shows a method that gives
$\theta=1.3063778838\dots$ to over 6850 decimal places. But it is not known
whether $\theta$ is a rational number.

The primes generated using Mills’ procedure grow very fast. If we denote
$M_{n}=\lfloor\theta^{3^{n}}\rfloor$, one has

$M_{1}=2,\quad M_{2}=11,\quad M_{3}=1361,\quad M_{4}=2\,521\,008\,887,$

and $M_{5}$ has $29$ digits (OEIS sequence A051254, see [7]).

In 1951, Wright [10] found another prime-representing constant using a method
that, instead of relying on Ingham’s theorem, depends on Bertrand’s postulate,
a much more elementary result: $p_{n+1}-p_{n}<p_{n}$ (or, as usually stated,
there is always a prime between $N$ and $2N$). Using this, Wright proves the
existence of a constant $\alpha\in(1,2)$ such that, if we recursively define
$\alpha_{0}=\alpha$ and $\alpha_{n+1}=2^{\alpha_{n}}$, then
$\lfloor\alpha_{n}\rfloor$ is prime for $n=1,2,\dots$ (said more compactly,
$\big{\lfloor}2^{2^{\rotatebox{8.0}{\ldots}^{\raisebox{-0.7pt}{$\scriptscriptstyle
2^{\alpha}$}}}}\\!\big{\rfloor}$ is a prime for any number of iterations of
the exponential). Again, the method to obtain $\alpha$ is not unique, and, in
this case, for historical reasons (it is the example proposed by Wright), it
is customary to take the biggest $\alpha$ with that property; this gives
$\alpha=1.928780\dots$. In any case, the primes generated using Wright’s
procedure are much larger than in Mills’ procedure; with the above mentioned
$\alpha$, if we denote $W_{n}=\lfloor\alpha_{n}\rfloor$, the first values are
$W_{1}=3$, $W_{2}=13$, and $W_{3}=16381$, while $W_{4}$ has about $5000$
digits (OEIS sequence A016104, [8]). If we try to find the smallest $\alpha$,
the corresponding primes are $W_{1}=3$, $W_{2}=11$, and $W_{3}=2053$, while
$W_{4}$ has $618$ digits, but this sequence is not included in the OEIS.

The proofs of Mills’ and Wright’s results and references to some similar ones
can be found in [2].

There are also some prime-representing constants that allow us to find all the
primes; here we show two examples that can be found in [4, § 22.3, p. 345].
The first example takes $\beta=\sum_{k=1}^{\infty}p_{k}/10^{2^{k}}$, where
$p_{k}$ is the $k$th prime number; then we have

$p_{n}=\lfloor{10^{2^{n}}\beta}\rfloor-10^{2^{n-1}}\lfloor{10^{2^{n-1}}\beta}\rfloor.$
(1)

For the second example, let us assume that we have previously proved that, for
a positive integer $r$, the primes satisfy $p_{n}\leq r^{n}$ for any $n$; this
is true for $r=2$ due to Bertrand’s postulate, but yet more elementary for
$r=4$, as we can see in [4, Theorem 20, p. 17]. Then the number
$\beta=\sum_{k=1}^{\infty}p_{k}/r^{k^{2}}$ gives the following method to
generate the primes:

$p_{n}=\lfloor{r^{n^{2}}\beta}\rfloor-r^{2n-1}\lfloor{r^{(n-1)^{2}}\beta}\rfloor.$
(2)

In both cases, checking the expressions (1) and (2) is easy; in particular,
the first one is a simple manipulation of the decimal expansion of
$\beta=\sum_{k=1}^{\infty}p_{k}/10^{2^{k}}$ and has the primes embedded in it.

It may seem like a dirty trick to use the primes to define $\beta$ and then
manipulate $\beta$ to recover the primes but, actually, the same idea appears
in Mills’ and Wright’s procedures. For instance, Wright starts by taking the
prime $W_{1}=3$; then, using Bertrand’s postulate, there exists a prime
$W_{2}$ between $2^{W_{1}}$ and $2\cdot 2^{W_{1}}$ (we can take $W_{2}=11$ or
$W_{2}=13$), and the method continues, always taking a prime $W_{n+1}$ between
$2^{W_{n}}$ and $2\cdot 2^{W_{n}}$. Then the primes $W_{n}$ are used to define
Wright’s constant $\alpha$, and the manipulation of $\alpha$ recovers the
primes. Something similar happens in the case of Mills’ constant $\theta$
(with an additional difficulty due to the fact that the constant $K$ in
Ingham’s theorem is not made explicit). Actually, this is already remarked in
[4, § 22.3, p. 345]: “Any one of these formulae (or any similar one) would
attain a different status if the exact value [of the prime-representing
constant] which occurs in it could be expressed independently of the primes.
There seems no likelihood of this, but it cannot be ruled out as entirely
impossible.”

In 2019, a group of students from Buenos Aires University discovered another
nice prime-representing constant; see [3]. They took

$\lambda=\sum_{k=1}^{\infty}\frac{p_{k}-1}{\prod_{i=1}^{k-1}p_{i}},$

a series whose convergence can be proved using Bertrand’s postulate. It is not
difficult to check that $\lambda=2.920050977316\dots$. Starting with the
“Buenos Aires constant” $\lambda$, we recursively define $\lambda_{1}=\lambda$
and
$\lambda_{n}=\lfloor\lambda_{n-1}\rfloor(\lambda_{n-1}-\lfloor\lambda_{n-1}\rfloor+1)$,
and then we have $\lfloor\lambda_{n}\rfloor=p_{n}$, for $n=1,2,\dots$.
Moreover, it can be seen that $\lambda$ is an irrational number (as we have
already remarked, this is not known for Mills’ constant).

Just as we have wondered about the irrationality of $\lambda$, we may be
interested in knowing whether it is an algebraic or a transcendental number.
Let us recall that a real number is algebraic of degree $n$ if it is the root
of a nonzero irreducible polynomial in $\mathbb{Z}[x]$ of degree $n$ (in
particular, the rational numbers are the algebraic numbers of degree $1$), and
a number is said to be transcendental if it is not algebraic of degree $n$ for
any positive integer $n$.

It is not known if $\lambda$ or any other of the above-mentioned prime-
representing constants are algebraic or transcendental numbers. Is it possible
to find a prime-representing constant that is a transcendental number?

Only a few classes of transcendental numbers are known, in part because it can
be extremely difficult to show that a given number is transcendental. In 1844,
Liouville gave the first construction of a transcendental number using the
idea of very fast rational approximation, a property shared by only a very
thin class of transcendental numbers (known as Liouville numbers). The work of
Roth in 1955 allows one to identify a wider class of transcendental numbers,
but again relying on very fast rational approximation (although not
necessarily as fast as in the case of Liouville numbers). We will recall both
Liouville’s theorem and Roth’s theorem in Section 3 of this article.

The idea for finding a transcendental prime-representing constant is to define
it by means of a series, as in the construction of the numbers $\beta$ used in
(1) and (2), but in such a way that the series converges to a transcendental
number. This happens when the series converges fast enough to allow an
approximation by rationals that, according to Liouville’s or Roth’s theorems,
generates a transcendental number. Liouville’s theorem is much more elementary
than Roth’s, while, on the other hand, Roth’s theorem is more powerful. Later
we are going to give two prime-representing constants that are transcendental
numbers. For the first one, its transcendence will be proved using Liouville’s
theorem; to prove the transcendence of the second constant, we will use Roth’s
theorem.

Of course, this does not imply that the constants $\beta$ used in (1) and (2)
are algebraic numbers, only that the series that define them are not useful in
proving transcendence using Liouville’s or Roth’s theorems. It is possible
that these $\beta$ are transcendental numbers (actually, we think that this is
likely, because, in the sense of cardinality, almost all real numbers are
transcendental), although different arguments would be necessary to prove
this, and finding them does not seem to be an easy task. But, actually, this
already happens with $e=\sum_{k=0}^{\infty}1/k!$, which is a transcendental
number (proved by Hermite in 1873), although the series is not useful in
proving transcendence.

Thus, the main theorems of this article are the following.

######  Theorem 1.

Let $a\geq 2$ be an integer, let $\\{p_{k}\\}$ be the sequence of prime
numbers, and define

$\mu=\sum_{k=1}^{\infty}\frac{p_{k}}{a^{k+k!}}.$

Then $\mu$ is a transcendental number and it generates the primes by means of
$p_{1}=\lfloor a^{2}\mu\rfloor$ and

$p_{n}=\lfloor a^{n+n!}\mu\rfloor-a^{1+n!-(n-1)!}\lfloor
a^{(n-1)+(n-1)!}\mu\rfloor\quad\text{for }n=2,3,\dots.$ (3)

######  Theorem 2.

Let $a\geq 2$ and $m\geq 3$ be two integers, let $\\{p_{k}\\}$ the sequence of
prime numbers, and define

$\nu=\sum_{k=1}^{\infty}\frac{p_{k}}{a^{k+m^{k}}}.$

Then $\nu$ is a transcendental number and it generates the primes by means of
$p_{1}=\lfloor a^{1+m}\nu\rfloor$ and

$p_{n}=\lfloor a^{n+m^{n}}\nu\rfloor-a^{1+m^{n}-m^{n-1}}\lfloor
a^{(n-1)+m^{n-1}}\nu\rfloor\quad\text{for }n=2,3,\dots.$ (4)

The structure of the article is as follows. In Section 2 we give a lemma that
will be used to prove that a constant defined as a series is a prime-
representing constant. Finally, we prove Theorems 1 and 2 in Section 3.

##  2 A preliminary lemma

Here we show a general scheme to find prime-representing constants defined by
means of series. In the proof, we only need to use Bertrand’s postulate, a
consequence of which is that the $k$th prime is at most $2^{k}$. It would not
be very difficult to weaken the hypotheses in the lemma and give a very
similar proof, but the following statement is enough for the purposes of this
article.

######  Lemma.

Let $f:\mathbb{N}\to\mathbb{N}$ be a function that satisfies $f(k)\geq
2^{k+1}f(k-1)$ and $f(k-1)\mid f(k)$ for $k\geq 2$, and define

$S=\sum_{k=1}^{\infty}\frac{p_{k}}{f(k)}$

with $\\{p_{k}\\}$ the sequence of prime numbers. Then $p_{1}=\lfloor
f(1)S\rfloor$ and

$p_{n}=\lfloor f(n)S\rfloor-\frac{f(n)}{f(n-1)}\lfloor
f(n-1)S\rfloor\quad\text{for }n=2,3,\dots.$

###### Proof.

Take

$f(n)S=\sum_{k=1}^{n}\frac{f(n)}{f(k)}\,p_{k}+\sum_{k=n+1}^{\infty}\frac{f(n)}{f(k)}\,p_{k}.$

Since $f(k-1)\mid f(k)$, it follows that the first sum gives an integer; let
us analyze the second sum. Recall that, as a consequence of Bertrand’s
postulate, we have $p_{k}\leq 2^{k}$. For the first summand $k=n+1$, we have

$\frac{f(n)}{f(k)}\,p_{k}=\frac{f(k-1)}{f(k)}\,p_{k}\leq 2^{-k-1}\cdot
2^{k}=2^{-1},$

and, for $k>n+1$,

$\displaystyle\frac{f(n)}{f(k)}\,p_{k}$
$\displaystyle=\frac{f(n)}{f(n+1)}\frac{f(n+1)}{f(n+2)}\cdots\frac{f(k-2)}{f(k-1)}\frac{f(k-1)}{f(k)}\,p_{k}$
$\displaystyle\leq 2^{-n-2}\cdot 2^{-n-3}\cdots 2^{-k-2}\cdot 2^{-k-1}\cdot
2^{k}\leq 2^{-k-3},$

so

$0\leq\sum_{k=n+1}^{\infty}\frac{f(n)}{f(k)}\,p_{k}\leq\frac{1}{2}+\sum_{k=n+2}^{\infty}\frac{1}{2^{k+3}}=\frac{1}{2}+\frac{1}{2^{n+4}}<1.$

As a consequence,

$\lfloor f(n)S\rfloor=\sum_{k=1}^{n}\frac{f(n)}{f(k)}\,p_{k}.$

Then, for $n>1$ we have

$\displaystyle\lfloor f(n)S\rfloor-\frac{f(n)}{f(n-1)}\lfloor f(n-1)S\rfloor$
$\displaystyle\qquad\qquad=f(n)\sum_{k=1}^{n}\frac{p_{k}}{f(k)}-\frac{f(n)}{f(n-1)}f(n-1)\sum_{k=1}^{n-1}\frac{p_{k}}{f(k)}=p_{n},$

and the case $n=1$ is trivial. ∎

The smallest $f$ that satisfies the hypotheses of the lemma is $f(1)=1$ and
$f(k)=2^{3+4+\cdots+(k+1)}$ for $k>1$. Other examples (that correspond to (2)
and (1), respectively) are $f(k)=r^{k^{2}}$ for any $r\geq 2$, and
$f(k)=10^{2^{k}}$.

Here we will use functions $f$ that grow still faster, such as

$f(k)=r^{k}a^{k!}\qquad\text{or}\qquad f(k)=r^{k}a^{m^{k}}$

for $r,a,m\geq 2$, and that also satisfy the hypothesis of the lemma, but we
will restrict some of the parameters to prove transcendence (in particular, we
will use $a=r$ and we will take $m\geq 3$).

##  3 Proofs of the theorems

For the sake of completeness, let us reproduce Liouville and Roth’s theorems
on approximation of rationals.

Liouville’s theorem was proved in 1844 and was used to prove that the number
$\sum_{k=1}^{\infty}1/10^{k!}$ (or $\sum_{k=1}^{\infty}1/a^{k!}$ for $a\geq
2$) that is not rational because its decimal expansion (respectively, its
expansion in base $a$) is neither finite nor periodic, cannot be algebraic of
degree $n$ for any $n\geq 2$. Thus it is a transcendental number. Prior to
this result, the existence of transcendental numbers was uncertain.

######  Liouville’s theorem (1844).

Let $\xi$ be an algebraic number of degree $n\geq 2$. Then, for any fixed
arbitrary constants $\varepsilon>0$ and $K$, there are only finitely many
rational approximations $p/q$ (with $q>0$) for which

$\left|\xi-\frac{p}{q}\right|<\frac{K}{q^{n+\varepsilon}}.$

Roth’s theorem was proved in 1955 after some previous results on the order of
approximation by rationals for algebraic numbers were established by Thue and
Siegel; for this reason, it is sometimes known as the Thue–Siegel–Roth
theorem. It can be used to prove that some series such as
$\sum_{k=1}^{\infty}{1}/{a^{m^{k}}}$ for $a\geq 2$ and $m\geq 3$ converge to a
transcendental number.

######  Roth’s theorem (1955, [9]).

Let $\xi$ be an irrational algebraic number. Then, for any arbitrary fixed
$\varepsilon>0$, there are only finitely many rational approximations $p/q$
(with $q>0$) for which

$\left|\xi-\frac{p}{q}\right|<\frac{1}{q^{2+\varepsilon}}.$

Now we have all that we need to prove our theorems.

###### Proof of Theorem 1.

It is clear that, expressed in base $a$, the digital expansion of $\mu$ is not
finite or periodic, so it is not a rational number. Let us see that $\mu$
cannot be algebraic of degree $n$ for any $n\geq 2$.

For fixed $n$, let us denote the partial sums of $\mu$ by

$\mu_{j}=\sum_{k=1}^{n+j-1}\frac{p_{k}}{a^{k}a^{k!}}=\frac{r_{j}}{s_{j}},$

where $s_{j}=a^{(n+j-1)+(n+j-1)!}$. By Bertand’s postulate, $p_{k}\leq
2^{k}\leq a^{k}$, so we can write

$\displaystyle\left|\mu-\frac{r_{j}}{s_{j}}\right|$
$\displaystyle=\sum_{k=n+j}^{\infty}\frac{p_{k}}{a^{k}a^{k!}}\leq\sum_{k=n+j}^{\infty}\frac{1}{a^{k!}}\leq\sum_{k=(n+j)!}^{\infty}\frac{1}{a^{k}}$
$\displaystyle=\frac{1}{a^{(n+j)!}}\bigg{(}1+\frac{1}{a}+\frac{1}{a^{2}}+\cdots\bigg{)}=\frac{1}{a^{(n+j)!}}\frac{a}{a-1}.$

Moreover, $s_{j}^{n+j}=a^{(n+j-1)(n+j)+(n+j)!}$, so

$\displaystyle\left|\mu-\frac{r_{j}}{s_{j}}\right|$
$\displaystyle\leq\frac{a^{(n+j-1)(n+j)}}{s_{j}^{n+j}}\frac{a}{a-1}=\frac{a^{(n+j-1)(n+j)+1}}{(a-1)s_{j}^{j-1}}\frac{1}{s_{j}^{n+1}}$
$\displaystyle=\frac{a^{(n+j-1)(n+j)}}{(a-1)a^{(j-1)(n+j-1)+(j-1)(n+j-1)!}}\leq\frac{K_{a,n}}{s_{j}^{n+1}}$

for a constant $K_{a,n}$ that does not depend on $j$. Thus, we have infinitely
many rational approximations $r_{j}/s_{j}$ and then Liouville’s theorem with
$\varepsilon=1$ shows that $\mu$ cannot be an algebraic number of orden $n$.

Now, the prime representation (3) is a direct consequence of the lemma. ∎

###### Proof of Theorem 2.

Expressed in base $a$, the digital expansion of $\nu$ is not finite or
periodic, so it is not a rational number.

To prove transcendence, let us denote the partial sums of $\nu$ by

$\nu_{j}=\sum_{k=1}^{j}\frac{p_{k}}{a^{k}a^{m^{k}}}=\frac{r_{j}}{s_{j}},$

where $s_{j}=a^{j+m^{j}}$. By Bertand’s postulate, $p_{k}\leq 2^{k}\leq
a^{k}$, so we can write

$\displaystyle\left|\nu-\frac{r_{j}}{s_{j}}\right|$
$\displaystyle=\sum_{k=j+1}^{\infty}p_{k}a^{-k}a^{-m^{k}}\leq\sum_{k=j+1}^{\infty}a^{-m^{k}}=\sum_{i=1}^{\infty}\big{(}a^{m^{j}}\big{)}^{-m^{i}}$
$\displaystyle=\sum_{i=1}^{\infty}\big{(}s_{j}/a^{j}\big{)}^{-m^{i}}\leq\sum_{i=1}^{\infty}\big{(}s_{j}/a^{j}\big{)}^{-mi}=\frac{1}{(s_{j}/a^{j})^{m}-1}.$

Moreover, observe that $(s_{j}/a^{j})^{m}\geq s_{j}^{m-1/2}$ if and only if
$s_{j}\geq a^{2jm}$, and this inequality holds for $j\geq 2$ because
$j+m^{j}\geq 2jm$ (recall that $m\geq 3$). Then, for $j\geq 2$,

$\left|\nu-\frac{r_{j}}{s_{j}}\right|\leq\frac{1}{s_{j}^{m-1/2}-1}\leq\frac{1}{s_{j}^{m-3/4}}\leq\frac{1}{s_{j}^{2+1/4}},$

where in the last step we have used $m\geq 3$. By applying Roth’s theorem with
$\varepsilon=1/4$, this implies that $\nu$ is a transcendental number.

Finally, to find (4) it is enough to apply the lemma. ∎

### Acknowledgment.

The research of the author is partially supported by grant
PGC2018-096504-B-C32 of MINECO/FEDER (Spanish Government).

## References

  * [1] C. K. Caldwell, Y. Cheng, Determining Mills’ constant and a note on Honaker’s problem, J. Integer Seq. 8 (2005), no. 4, article 05.4.1.
  * [2] U. Dudley, History of a formula for primes, Amer. Math. Monthly 76 (1969), no. 1, 23–28.
  * [3] D. Fridman, J. Garbulsky, B. Glecer, J. Grime, M. Tron Florentin, A prime-representing constant, Amer. Math. Monthly 126 (2019), no. 1, 70–73.
  * [4] G. H. Hardy, E. M. Wright, An Introduction to the Theory of Numbers, 5th ed., Oxford Univ. Press, New York, 1979.
  * [5] A. E. Ingham, On the difference between consecutive primes, Quart. J. Math. Oxford (2) 8 (1937), no. 1, 255–266.
  * [6] W. H. Mills, A prime-representing function, Bull. Amer. Math. Soc. 53 (1947), no. 6, 604.
  * [7] OEIS Foundation Inc., Sequence A051254. The On-Line Encyclopedia of Integer Sequences, 2020; http://oeis.org/A051254
  * [8] OEIS Foundation Inc., Sequence A016104, The On-Line Encyclopedia of Integer Sequences, 2020; http://oeis.org/A016104
  * [9] K. F. Roth, Rational approximation of algebraic numbers, Mathematika 2 (1955), no. 3, 1–20; Corrigendum, Mathematika 2 (1955), no. 4, 168.
  * [10] E. M. Wright, A prime-representing function, Amer. Math. Monthly 58 (1951), no. 9, 616–618.

Juan Luis Varona
Departamento de Matemáticas y Computación, Universidad de La Rioja,
26006 Logroño, Spain
<EMAIL_ADDRESS>