17218 LABEL:LastPageFeb. 12, 2020May 26, 2021

# Theories of real addition with and without a predicate for integers

Alexis Bèsa  aUniv. Paris Est Creteil, LACL, F-94010 Creteil, France
<EMAIL_ADDRESS>and  Christian Choffrutb  bIRIF (UMR 8243), CNRS and Université
Paris 7 Denis Diderot, France<EMAIL_ADDRESS>
###### Abstract.

We show that it is decidable whether or not a relation on the reals definable
in the structure $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ can be defined in
the structure $\langle\mathbb{R},+,<,1\rangle$. This result is achieved by
obtaining a topological characterization of
$\langle\mathbb{R},+,<,1\rangle$-definable relations in the family of
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relations and then by
following Muchnik’s approach of showing that the characterization of the
relation $X$ can be expressed in the logic of
$\langle\mathbb{R},+,<,1,X\rangle$.

The above characterization allows us to prove that there is no intermediate
structure between $\langle\mathbb{R},+,<,\mathbb{Z}\rangle$ and
$\langle\mathbb{R},+,<,1\rangle$. We also show that a
$\langle\mathbb{R},+,<,\mathbb{Z}\rangle$-definable relation is
$\langle\mathbb{R},+,<,1\rangle$-definable if and only if its intersection
with every $\langle\mathbb{R},+,<,1\rangle$-definable line is
$\langle\mathbb{R},+,<,1\rangle$-definable. This gives a noneffective but
simple characterization of $\langle\mathbb{R},+,<,1\rangle$-definable
relations.

###### Key words and phrases:

first-order logic, definability, decidability, reals with addition and order

##  1\. Introduction

Consider the structure $\langle\mathbb{R},+,{<},1\rangle$ of the additive
ordered group of reals along with the constant $1$. It is well-known that the
subgroup $\mathbb{Z}$ of integers is not first-order-definable in this
structure. Add the predicate $x\in\mathbb{Z}$ resulting in the structure
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$. Our main result shows that given
a $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation it is
decidable whether or not it is $\langle\mathbb{R},+,{<},1\rangle$-definable.

The structure $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ is a privileged area
of application of algorithmic verification of properties of reactive and
hybrid systems, where logical formalisms involving reals and arithmetic
naturally appear, see e.g [BDEK07, FQSW20, Boi]. It admits quantifier
elimination and is decidable as proved independently by Miller [Mil01] and
Weisfpfenning [Wei99]. The latter’s proof uses reduction to the theories of
$\langle{\mathbb{Z},+,<}\rangle$ and $\langle\mathbb{R},+,{<},1\rangle$.

There are many ways to come across the structure
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$, which highlights its
significance. One approach is through automata. Cobham considers a fixed base
$r$ and represents integers as finite $r$-digit strings. A subset $X$ of
integers is $r-$recognizable if there exists a finite automaton accepting
precisely the representations in base $r$ of its elements. Cobham’s theorem
says that if $X$ is $r$\- and $s$-recognizable for two multiplicatively
independent values $r$ and $s$ (i.e., for all $i,j>0$ it holds
$r^{i}\not=s^{j}$) then $X$ is definable in Presburger arithmetic, i.e., in
$\langle\mathbb{N},+\rangle$ [Cob69, Pre27]. Conversely, each Presburger-
definable subset of $\mathbb{N}$ is $r$-recognizable for every $r$. This
result was extended to integer relations of arbitrary arity by Semënov
[Sem77].

Now consider recognizability of sets of reals. As early as 1962 Büchi
interprets subsets of integers as characteric functions of reals in their
binary representations and shows the decidability of a structure which is
essentially an extension of $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$,
namely $\langle{\mathbb{R}_{+},<,P,\mathbb{N}}\rangle$ where $P$ if the set of
positive powers of $2$ [Büc62, Thm 4]. Going one step further, Boigelot & al.
[BRW98] consider reals as infinite strings of digits and use Muller automata
to speak of $r$-recognizable subsets and more generally of $r$-recognizable
relations of reals. In the papers [BB09, BBB10, BBL09] the equivalence was
proved between (1) $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definability,
(2) $r$\- and $s$-recognizability where the two bases have distinct primes in
their factorization [BBL09, Thm 5] and (3) $r$\- and $s$-weakly
recognizability for two independently multiplicative bases, [BBL09, Thm 6] (a
relation is $r$-weakly recognizable if it is recognized by some deterministic
Muller automaton in which all states in the same strongly connected component
are either final or nonfinal). Consequently, as far as reals are concerned,
definability in $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ compared to
recognizability or weak recognizability by automata on infinite strings can be
seen as the analog of Presburger arithmetic for integers compared to
recognizability by automata on finite strings.

A natural issue is to find effective characterizations of subclasses of
$r-$recognizable relations. In the case of relations over integers, Muchnik
proved that for every base $r\geq 2$ and arity $k\geq 1$, it is decidable
whether a $r$-recognizable relation $X\subseteq\mathbb{N}^{k}$ is Presburger-
definable [Muc03] (see a different approach in [Ler05] which provides a
polynomial time algorithm). For relations over reals, up to our knowledge, the
only known result is due to Milchior who proved that it is decidable (in
linear time) whether a weakly $r-$recognizable subset of $\mathbb{R}$ is
definable in $\langle\mathbb{R},+,{<},1\rangle$ [Mil17]. Our result provides
an effective characterization of $\langle\mathbb{R},+,{<},1\rangle$-definable
relations within $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
relations. Our approach is inspired by Muchnik’s one, which consists of giving
a combinatorical characterization of $\langle\mathbb{N},+\rangle$-definable
relations that can be expressed in $\langle\mathbb{N},+\rangle$ itself.

Our result has two interesting corollaries. The first one is that there is no
intermediate structure between $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ and
$\langle\mathbb{R},+,{<},1\rangle$, i.e., if an
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation $X$ is not
$\langle\mathbb{R},+,{<},1\rangle$-definable, then $\mathbb{Z}$ is definable
in the structure $\langle{\mathbb{R},+,<,1,X}\rangle$. Along with the property
that $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ is the “common” substructure
of all recognizable and weakly recognizable relations this indicates that this
structure is central. The second corollary is a noneffective but simple
characterization: an $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
relation is $\langle\mathbb{R},+,{<},1\rangle$-definable if and only if every
intersection with a rational line is
$\langle\mathbb{R},+,{<},1\rangle$-definable. By rational we mean any line
which is the intersection of hyperplanes defined by equations with rational
coefficients.

The reader will be able to observe that, while our results are obviously
related to automata questions, proofs do not use automata at all.

### Other related works.

Muchnik’s approach, namely expressing in the theory of the structure a
property of the structure itself, can be used in other settings. We refer the
interested reader to the discussion in [SSU14, Section 4.6] and also to [PW00,
Bès13, Mil17] for examples of such structures. A similar method was already
used in 1966, see [GS66, Thm 2.2.] where the authors were able to express in
Presburger theory whether or not a Presburger subset is the Parikh image of a
context-free language.

Let us mention a recent series of results by Hieronymi which deal with
expansions of $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$, and in particular
with the frontier of decidability for such expansions, see, e.g., [Hie19] and
its bibliography. Finally, in connection with our result that there is no
intermediate structure between $\langle\mathbb{R},+,{<},1\rangle$ and
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$, Conant recently proved [Con18]
that there is no intermediate structure between $\langle{\mathbb{Z},+}\rangle$
and $\langle{\mathbb{Z},+,<}\rangle$. Concerning these two theories, it is
decidable whether or not a $\langle{\mathbb{Z},+,<}\rangle$-definable relation
is actually $\langle{\mathbb{Z},+}\rangle$-definable, see [CF10].

Now we give a short outline of our paper. Section 2 gathers all the basic on
the two specific structures $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ and
$\langle\mathbb{R},+,{<},1\rangle$, taking advantage of the existence of
quantifier elimination which allows us to work with simpler formulas. Section
3 introduces topological notions. In particular we say that the neighborhood
of a point $x\in\mathbb{R}^{n}$ relative to a relation
$X\subseteq\mathbb{R}^{n}$ has _strata_ if there exists a direction such that
the intersection of all sufficiently small neighborhoods around $x$ with $X$
is the trace of a union of lines parallel to the given direction. This
reflects the fact that the relations we work with are defined by finite unions
of regions of the spaces delimited by hyperplanes of arbitrary dimension. In
Section 4 we show that when $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable all points (except finitely many
which we call singular) have at least one direction which is a stratum.
Section 5 studies relations between neighborhoods. In Section 6 we give a
necessary and sufficient condition for a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation to be
$\langle\mathbb{R},+,{<},1\rangle$-definable, namely 1) it has finitely many
singular points and 2) all intersections of $X$ with arbitrary hyperplanes
parallel to $n-1$ axes and having rational components on the remaining axis
are $\langle\mathbb{R},+,{<},1\rangle$-definable. Then we show that these
properties are expressible in $\langle{\mathbb{R},+,<,1,X}\rangle$. In Section
7 we show that there is no intermediate structure between
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ and
$\langle\mathbb{R},+,{<},1\rangle$. Section 8 is devoted to the proof that a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation is
$\langle\mathbb{R},+,{<},1\rangle$-definable if and only if every intersection
with a rational line is $\langle\mathbb{R},+,{<},1\rangle$-definable.

##  2\. Preliminaries

Throughout this work we assume the vector space $\mathbb{R}^{n}$ is provided
with the metric $L_{\infty}$ (i.e., $|x|=\max_{1\leq i\leq n}|x_{i}|$). The
open ball centered at $x\in\mathbb{R}^{n}$ and of radius $r>0$ is denoted by
$B(x,r)$. Given $x,y\in\mathbb{R}^{n}$ we let $[x,y]$ (resp. $(x,y)$) denote
the closed segment (resp. open segment) with extremities $x,y$. Also we use
notations such as $[x,y)$ or $(x,y]$ for half-open segments.

Let us specify our logical conventions and notations. We work within first-
order predicate calculus with equality. We confuse formal symbols and their
interpretations, except in subsection 6.2 where the distinction is needed. We
are mainly concerned with the structures $\langle\mathbb{R},+,{<},1\rangle$
and $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$. In the latter structure,
$\mathbb{Z}$ should be understood as a unary predicate which is satisfied by
reals belonging to $\mathbb{Z}$ only - in other words, we deal with one-sorted
structures. Given a structure $\mathcal{M}$ with domain $D$ and $X\subseteq
D^{n}$, we say that $X$ is definable in $\mathcal{M}$, or
$\mathcal{M}$-definable, if there exists a formula
$\varphi(x_{1},\dots,x_{n})$ in the signature of $\mathcal{M}$ such that
$\varphi(a_{1},\dots,a_{n})$ holds in $\mathcal{M}$ if and only if
$(a_{1},\dots,a_{n})\in X$.

The $\langle\mathbb{R},+,{<},1\rangle$-theory admits quantifier elimination in
the following sense, which can be interpreted geometrically as saying that a
$\langle\mathbb{R},+,{<},1\rangle$-definable relation is a finite union of
closed and open polyhedra.

[[FR75, Thm. 1]] Every formula in $\langle\mathbb{R},+,{<},1\rangle$ is
equivalent to a finite Boolean combination of inequalities between linear
combinations of variables with coefficients in $\mathbb{Z}$ (or, equivalently,
in $\mathbb{Q}$).

######  Corollary 1.

  1. (1)

A subset of $\mathbb{R}$ is $\langle\mathbb{R},+,{<},1\rangle$-definable if
and only if it is a finite union of intervals whose endpoints are rational
numbers. In particular $\mathbb{Z}$ is not
$\langle\mathbb{R},+,{<},1\rangle$-definable.

  2. (2)

For every $n\geq 1$, if $X\subseteq\mathbb{R}^{n}$ is nonempty and
$\langle\mathbb{R},+,{<},1\rangle$-definable then $X$ contains an element of
$\mathbb{Q}^{n}$.

######  Proof 2.1.

$(1)$ is an immediate consequence of Theorem 2. For $(2)$ we proceed by
induction over $n$. The case $n=1$ follows from $(1)$. For $n>1$, consider the
set $Y=\\{x_{n}\ |\ \exists x_{1},\dots,x_{n-1}\ (x_{1},\dots,x_{n})\in X\\}$.
The set $Y$ is nonempty and $\langle\mathbb{R},+,{<},1\rangle$-definable by
our hypothesis on $X$, thus by the base case of the induction $Y$ contains a
rational $q$. Then it suffices to apply the induction hypothesis to the
$(n-1)-$ary relation $\\{(x_{1},\dots,x_{n-1})\ |\ (x_{1},\dots,x_{n-1},q)\in
X\\}$.

In the larger structure $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ it is
possible to separate the integer (superscript ‘$I$’) and fractional
(superscript ‘$F$’) parts of the reals as follows.

[[BFL08],[BBL09, p. 7]] Let $X\subseteq\mathbb{R}^{n}$ be definable in
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$. Then there exists a unique finite
union

$X=\bigcup^{K}_{k=1}(X_{k}^{(I)}+X_{k}^{(F)})$ (1)

where

  * •

the relations $X_{k}^{(I)}$ are pairwise disjoint subsets of $\mathbb{Z}^{n}$
and are $\langle{\mathbb{Z},+,<}\rangle$-definable

  * •

the relations $X_{k}^{(F)}$ are distinct subsets of $[0,1)^{n}$ and are
$\langle\mathbb{R},+,{<},1\rangle$-definable

There is again a geometric interpretation of
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relations as a regular
(in a precise technical way) tiling of the space by a finite number of tiles
which are themselves finite unions of polyhedra. As a consequence, the
restriction of a $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
relation to a bounded subset is $\langle\mathbb{R},+,{<},1\rangle$-definable,
as stated in the following lemma.

######  Lemma 2.

For every $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$, its restriction to a bounded domain
$[a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}]$ where the $a_{i}$’s and the
$b_{i}$’s are rationals, is $\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Proof 2.2.

By Theorem 2.1 the relation $X$ is a finite union of the form
$\displaystyle\bigcup^{K}_{k=1}(X_{k}^{(I)}+X_{k}^{(F)})$ where each
$X_{k}^{(I)}\subseteq\mathbb{Z}^{n}$ is
$\langle{\mathbb{Z},<,+}\rangle$-definable and each
$X_{k}^{(F)}\subseteq[0,1)^{n}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

Let $A_{k},B_{k}\in\mathbb{Z}$ be such that

$[a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}]\subseteq[A_{1},B_{1}]\times\cdots\times[A_{n},B_{n}].$

The $a_{i}$’s and the $b_{i}$’s are rational thus
$\langle\mathbb{R},+,{<},1\rangle$-definable, and the relation
$[a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}]$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable as well. Now the finite subset

$T_{k}=X_{k}^{(I)}\cap([A_{1},B_{1}]\times\cdots\times[A_{n},B_{n}])\subseteq\mathbb{Z}\times\cdots\times\mathbb{Z}$

is $\langle\mathbb{R},+,{<},1\rangle$-definable, therefore so is the sum
$T_{k}+X_{k}^{(F)}$, and also the finite union
$S=\displaystyle\bigcup^{K}_{k=1}(T_{k}+X_{k}^{(F)})$. Finally the restriction
$X\cap([a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}])=S\cap([a_{1},b_{1}]\times\cdots\times[a_{n},b_{n}])$
is also $\langle\mathbb{R},+,{<},1\rangle$-definable.

By considering the restriction of the
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-relation to a ball containing all
possible tiles with their closest neighbors, we get that the neighborhoods of
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$\- and
$\langle\mathbb{R},+,{<},1\rangle$-definable relations are indistinguishable.

######  Lemma 3.

For every $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$ there exists a
$\langle\mathbb{R},+,{<},1\rangle$-definable relation
$Y\subseteq\mathbb{R}^{n}$ such that for all $x\in\mathbb{R}^{n}$ there exists
$y\in\mathbb{R}^{n}$ and a real $r>0$ such that the translation $u\mapsto
u+y-x$ is a one-to-one mapping between $B(x,r)\cap X$ and $B(y,r)\cap Y$.

######  Proof 2.3.

Let $X$ be a $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation

$X=\bigcup^{K}_{k=1}(X_{k}^{(I)}+X_{k}^{(F)})$

as in expression (1). Set $C=[-1,2)^{n}\subseteq\mathbb{R}^{n}$. Observe that
the set

${\mathcal{P}}=\\{-a+((a+C)\cap X)\mid a\in\mathbb{Z}^{n}\\}$

is finite and contains at most $K^{3^{n}}$ elements, all of which being
subsets of $C$. Thus there exists an integer $N$ such that for all
$P\in{\mathcal{P}}$ there exists $z\in B(0,N-1)\cap\mathbb{Z}^{n}$ such that

$P=-z+((z+C)\cap X).$

We prove the statement by defining $Y$ as the restriction of $X$ to $B(0,N)$.
Indeed, consider an arbitrary $x\in\mathbb{R}^{n}$ and let $x=w+t$ where
$w_{i}=\lfloor x_{i}\rfloor$ for $i=1,\ldots,n$. Then the translation
$u\mapsto-w+u$ defines a one-to-one correspondence between $(w+C)\cap X$ and
$-w+((w+C)\cap X)$ which is some $P\in{\mathcal{P}}$. By definition of $N$
there exists $z\in B(0,N-1)\cap\mathbb{Z}^{n}$ such that $z+P=(z+C)\cap
X=(z+C)\cap Y$. Then the translation $\tau(u)=-w+z+u$ is a one-to-one
correspondence between $(w+C)\cap X$ and $(z+C)\cap Y$. Since $x$ is interior
to $w+C$, the point $\tau(x)=y$ is interior to $z+C\subseteq B(0,N)$, thus for
sufficiently small $r>0$ the ball $B(x,r)$ is included in $w+C$ and the ball
$B(y,r)$ is included in $z+C$. Consequently $\tau$ defines a one-to-one
mapping between $B(x,r)\cap X$ and $B(y,r)\cap Y$.

##  3\. Strata

The aim is to decide, given $n\geq 1$ and a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$, whether $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable. Though the relations defined in
the two structures have very specific properties (see e.g [BN88, BBD12] for
$\langle\mathbb{R},+,{<},1\rangle$-definable relations) we define properties
that make sense in a setting as general as possible. The following clearly
defines an equivalence relation.

Given $x,y\in\mathbb{R}^{n}$ we write $x\,{\sim_{X}}\,y$ or simply $x\sim y$
when $X$ is understood, if there exists a real $r>0$ such that the translation
$w\mapsto w+y-x$ is a one-to-one mapping from $B(x,r)\cap X$ onto $B(y,r)\cap
X$.

Consider a closed subset of the plane delimited by a square. There are 10
equivalence classes: the set of points interior to the square, the set of
points interior to its complement, the four vertices and the four open edges.

  1. (1)

Given $v\in\mathbb{R}^{n}$ and a point $y\in\mathbb{R}^{n}$, let
$L_{v}(y)=\\{y+\alpha v\ |\ \alpha\in\mathbb{R}\\}$. When $v\not=0$ we say
that $L_{v}(y)$ is the line passing through $y$ in the direction $v$. More
generally, if $X\subseteq\mathbb{R}^{n}$ we let $L_{v}(X)$ denote the set
$\bigcup_{x\in X}L_{v}(x)$.

  2. (2)

A vector $v\in\mathbb{R}^{n}$ is an $X$-_stratum_ at $x$ (or simply a
_stratum_ when $X$ is understood) if there exists a real $r>0$ such that

$B(x,r)\cap L_{v}(X\cap B(x,r))\subseteq X.$ (2)

If $v\not=0$ this can be seen as saying that inside the ball $B(x,r)$, the
relation $X$ is a union of lines parallel to $v$.

  3. (3)

The set of $X$-strata at $x$ is denoted by $\text{Str}_{X}(x)$ or simply
$\text{Str}(x)$.

######  Proposition 4.

For all $X\subseteq\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$ the set $\text{\em
Str}{(}x)$ is a vector subspace of $\mathbb{R}^{n}$.

######  Proof 3.1.

We start with a lemma.

######  Lemma 5.

Let $v_{1},v_{2}$ be two strata at $x$ and let $r>0$ be such that

$B(x,r)\cap L_{v_{1}}(X\cap B(x,r))\subseteq X\quad\text{ and }\quad
B(x,r)\cap L_{v_{2}}(X\cap B(x,r))\subseteq X$

Then

$B(x,r)\cap L_{v_{1}+v_{2}}(X\cap B(x,r))\subseteq X.$

######  Proof 3.2.

Let $v=v_{1}+v_{2}$. The case when one of the vectors $v,v_{1},v_{2}$ is null
is trivial so we assume $v,v_{1},v_{2}\not=0$. We must prove that a point
$y\in B(x,r)$ belongs to $X$ if and only if all points of $B(x,r)\cap
L_{v}(y)$ do. Consider $z=y+\lambda v\in B(x,r)$ with $\lambda\neq 0$. Let
$\epsilon>0$ be such that for every point $t\in[y,z]$ the ball $B(t,\epsilon)$
is included in $B(x,r)$ (such a real exists because the segment $[y,z]$ is
compact). Let $n$ be an integer such that $|\frac{1}{n}\lambda
v_{1}|<\epsilon$. Then the points $y_{i}=y+\frac{i}{n}\lambda(v_{1}+v_{2})$
for $0\leq i\leq n$ belong to $B(x,r)$ because they lay in the segment
$[y,z]$, and due to the choice of $\epsilon$ the points
$y_{i}+\frac{1}{n}\lambda v_{1}$ for $0\leq i<n$ also belong to $B(x,r)$.
Since the vectors $v_{1}$ and $v_{2}$ are strata at $x$, for $0\leq i<n$ we
have

$y_{i}\in X\leftrightarrow y_{i}+\frac{\lambda}{n}v_{1}\in X\leftrightarrow
y_{i}+\frac{\lambda}{n}v_{1}+\frac{\lambda}{n}v_{2}=y_{i+1}\in X.$

Therefore in particular $z\in X\leftrightarrow y\in X$.

Now we turn to the proof of Proposition 4. By definition $v$ is a stratum if
and only if $\lambda v$ is a stratum for some $\lambda\not=0$. Thus it
suffices to verify that $\text{Str}{(}x)$ is closed under addition. If $v_{1}$
(resp. $v_{2}$) is a stratum then there exist $r_{1},r_{2}>0$ such that

$B(x,r_{1})\cap L_{v_{1}}(X\cap B(x,r_{1}))\subseteq X\quad\text{ and }\quad
B(x,r_{2})\cap L_{v_{2}}(X\cap B(x,r_{2}))\subseteq X.$

Thus for $r\leq\min\\{r_{1},r_{2}\\}$ we have

$B(x,r)\cap L_{v_{1}}(X\cap B(x,r))\subseteq X\quad\text{ and }\quad
B(x,r)\cap L_{v_{2}}(X\cap B(x,r))\subseteq X.\ $

It then suffices to apply Lemma 5.

Let $X\subseteq\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$. The _dimension_
dim$(x)$ of $x$ is the dimension of the subspace $\text{Str}{(}x)$.

Given $X\subseteq\mathbb{R}^{n}$, a point $x\in\mathbb{R}^{n}$ is
$X$-_singular_ , or simply _singular_ , if $\text{Str}{(}x)$ is trivial, i.e.,
reduced to the null vector, otherwise it is _nonsingular_.

[(Example 3 continued)] Let $x\in\mathbb{R}^{2}$. If $x$ belongs to the
interior of the square or of its complement, then
$\text{Str}{(}x)=\mathbb{R}^{2}$. If $x$ is one of the four vertices of the
square then we have $\text{Str}{(}x)=\\{0\\}$, i.e $x$ is singular. Finally,
if $x$ belongs to an open edge of the square but is not a vertex, then
$\text{Str}{(}x)$ has dimension 1, and two points of opposite edges have the
same one-dimensional subspace, while two points of adjacent edges have
different one-dimensional subspaces.

Note that even non-$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
relations may have no singular points. Indeed consider in the plane the set
$X$ defined as the union of vertical lines at abscissa $\frac{1}{n}$ for all
positive integers $n$. In this case any vertical vector is a stratum at any
point of the plane.

Now it can be shown that all strata at $x$ can be defined with respect to a
common value $r$ in expression (2).

######  Proposition 6.

Let $X\subseteq\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$. There exists a real
$r>0$ such that for every $v\in\text{\em Str}{(}x)$ we have

$B(x,r)\cap L_{v}(X\cap B(x,r))\subseteq X.$

######  Proof 3.3.

The case when $\text{Str}{(}x)$ is reduced to $0$ is trivial so we assume that
for some $p>0$ the vectors $v_{1},\ldots,v_{p}$ form a basis of the vector
space $\text{Str}{(}x)$. There exist $r_{1},\ldots,r_{p}>0$ such that

$B(x,r_{i})\cap L_{v_{i}}(X\cap B(x,r_{i}))\subseteq X.$

Then for $r=\min\\{r_{1},\ldots,r_{p}\\}$ we have

$B(x,r)\cap L_{v_{i}}(X\cap B(x,r))\subseteq X.$

Consider an arbitrary vector of $\text{Str}{(}x)$, say
$v=\lambda_{1}v_{1}+\cdots+\lambda_{p}v_{p}$. It suffices to apply Lemma 5
successively to $\lambda_{1}v_{1}+\lambda_{2}v_{2}$,
$\lambda_{1}v_{1}+\lambda_{2}v_{2}+\lambda_{3}v_{3}$, …,
$\lambda_{1}v_{1}+\cdots+\lambda_{p}v_{p}$.

Let $X\subseteq\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$. A _safe radius_ (for
$x$) is a real $r>0$ satisfying the condition of Proposition 6. Clearly if $r$
is safe then so are all $0<s\leq r$. Observe that every real is a safe radius
if $\text{Str}{(}x)$ is trivial.

[(Example 3 continued)] For an element $x$ of the interior of the square or
the interior of its complement, let $r$ be the (minimal) distance from $x$ to
the edges of the square. Then $r$ is safe for $x$. If $x$ is a vertex then
$\text{Str}{(}x)$ is trivial and every $r>0$ is safe for $x$. In all other
cases $r$ is the minimal distance of $x$ to a vertex.

######  Lemma 7.

Let $X\subseteq\mathbb{R}^{n}$ and $x,y\in\mathbb{R}^{n}$. If $x\sim y$ then
$\text{\em Str}(x)=\text{\em Str}(y)$.

######  Proof 3.4.

For some $r>0$, the translation $u\mapsto u+y-x$ is a one-to-one
correspondence between $B(x,r)\cap X$ and $B(y,r)\cap X$. Thus every stratum
of $X$ at $x$ is a stratum of $X$ at $y$ and vice versa.

The converse of Lemma 7 is false in general. Indeed consider, e.g.,
$X=\\{(x,y)\mid y\leq 0\\}\cup\\{(x,y)\mid y=1\\}$ in $\mathbb{R}^{2}$. The
points $(0,0)$ and $(0,1)$ have the same subspace of strata, namely that
generated by $(1,0)$, but $x\not\sim y$.

Now we combine the notions of strata and of safe radius.

######  Lemma 8.

Let $X\subseteq\mathbb{R}^{n}$, $x\in\mathbb{R}^{n}$ and $r$ be a safe radius
for $x$. Then for all $y\in B(x,r)$ we have $\text{\em
Str}{(x)}\subseteq\text{\em Str}{(y)}$.

######  Proof 3.5.

Indeed, consider $v\in\text{Str}{(x)}$. For all $s>0$ such that
$B(y,s)\subseteq B(x,r)$ we have

$\begin{array}[]{ll}B(y,s)\cap L_{v}(X\cap B(y,s))&=B(y,s)\cap L_{v}(X\cap
B(y,s)\cap B(x,r))\\\ &\subseteq B(x,r)\cap L_{v}(X\cap B(x,r))\subseteq
X.\end{array}$

[(Example 3 continued)] Consider a point $x$ on an (open) edge of the square
and a safe radius $r$ for $x$. For every point $y$ in $B(x,r)$ which is not on
the edge we have $\text{Str}{(}x)\subsetneq\text{Str}{(}y)=\mathbb{R}^{2}$.
For all other points we have $\text{Str}{(}x)=\text{Str}{(}y)$.

We relativize the notion of singularity and strata to an affine subspace
$P\subseteq\mathbb{R}^{n}$. The next definition should come as no surprise.

Given an affine subspace $P\subseteq\mathbb{R}^{n}$, a subset
$X\subseteq\mathbb{R}^{n}$ and a point $x\in P$, we say that a nonzero vector
$v$ parallel to $P$ is an $(X,P)$-_stratum for the point_ $x$ if for all
sufficiently small $r>0$ it holds

$B(x,r)\cap L_{v}(X\cap B(x,r)\cap P)\subseteq X.$

A point $x\in P$ is $(X,P)$-_singular_ if it has no $(X,P)$-stratum. For
simplicity when $P$ is the space $\mathbb{R}^{n}$ we keep the previous
terminology and speak of $X$-strata and $X$-singular points. Singularity and
nonsingularity do not go through restriction to affine subpaces. In the real
plane, let $X=\\{(x,y)\ |\ y<0\\}$ and $P$ be the line $x=0$. Then the origin
is not $X-$singular but it is $(X,P)-$singular. All other elements of $P$
admit $(0,1)$ as an $(X,P)-$stratum thus they are not $(X,P)-$singular. The
opposite situation may occur. In the real plane, let $X=\\{(x,y)\ |\
y<0\\}\cup P$ where $P=\\{(x,y)\mid x=0\\}$. Then the origin is $X-$singular
but it is not $(X,P)-$singular.

##  4\. Local properties

###  4.1. Local neighborhoods

In this section we recall that if $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable then the equivalence relation
$\sim$ (introduced in Definition 3) has finite index. This extends easily to
the case where $X$ is $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable.
The claim for $\langle\mathbb{R},+,{<},1\rangle$-definable relations can be
found, e.g., in [BN88, Thm 1] (see also [BBD12, Section 3]) but we revisit it
to some extent because of the small modifications needed to use it in our
setting.

We define what we mean by “cones”.

Let $\xi=(\xi_{1},\dots,\xi_{n})\in\mathbb{R}^{n}$. A _cone with apex $\xi$_
is an intersection of finitely many halfspaces defined by conditions of the
form $u(x-\xi)\triangleleft b$ where $\triangleleft\in\\{<,\leq\\}$,
$b\in\mathbb{Q}$, and $u$ denotes a linear expression with rational
coefficients, i.e., $u(x-\xi)=\sum_{1\leq i\leq n}a_{i}(x_{i}-\xi_{i})$ where
$a_{i}\in\mathbb{Q}$.

In particular the set reduced to the origin, and the empty set, are specific
cones in our sense (on the real line they can be described respectively by
$x\leq 0\wedge-x\leq 0$ and $x<0\wedge-x<0$).

Let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},1\rangle$-definable. By Theorem 2 we may assume that
$X$ is defined by a formula

$\phi(x)=\bigvee_{i\in I}C_{i}\text{ where }C_{i}=\bigwedge_{j\in
J_{i}}u_{i,j}(x)\triangleleft_{i,j}b_{i,j}$ (3)

where for all $(i,j)\in I\times J_{i}$ we have
$\triangleleft_{i,j}\in\\{<,\leq\\}$, $b_{i,j}\in\mathbb{Q}$ and $u_{i,j}$ is
a linear expression with rational coefficients.

Now we associate with $\phi$ a finite collection of cones.

Consider all formulas obtained from expression (3) by replacing in all
possible ways each predicate $u_{i,j}(x)\triangleleft_{ij}b_{i,j}$ by one of
the three options $u_{i,j}(x)\triangleleft_{ij}0$ or false or true. Use the
routine simplifications so that the resulting formulas are reduced to false or
true or are disjunctions of conjunctions with no occurrence of false or true.

Let $\Theta$ be the (finite) set of formulas thus obtained, and let us call
_local neighborhood_ any relation defined by some formula in $\Theta$. In
particular each formula in $\Theta$ defines a finite union of cones of which
the origin is an apex.

In the terminology of [BN88, Thm 1] the following says that an
$\langle\mathbb{R},+,{<},1\rangle$-definable relation has finitely many
“faces” which are what we call local neighborhoods.

######  Proposition 9.

Consider an $\langle\mathbb{R},+,{<},1\rangle$-definable relation $X$. There
exists a finite collection $\Theta$ of
$\langle\mathbb{R},+,{<},1\rangle$-formulas defining finite unions of cones
with apex the origin such that for all $\xi\in\mathbb{R}^{n}$ there exist some
$\theta$ in $\Theta$ and some real $s>0$ such that for all
$t\in\mathbb{R}^{n}$ we have

$(\theta(t)\wedge|t|<s)\leftrightarrow(\phi(\xi+t)\wedge|t|<s).$ (4)

######  Proof 4.1.

Let $\Theta$ be defined as in Definition 4.1. Consider the expression (3). For
all $(i,j)\in I\times J_{i}$ let $A_{i,j}$ denote the hyperplane with equation
$u_{i,j}(x)=b_{i,j}$. Let $s>0$ be such that $B(\xi,s)$ intersects only the
hyperplanes $A_{i,j}$ which contain $\xi$. For all $(i,j)\in I\times J_{i}$,
if $\xi\in A_{i,j}$ then $u_{i,j}(\xi)=b_{i,j}$ thus for every
$t\in\mathbb{R}$ we have $u_{i,j}(\xi+t)\triangleleft_{i,j}b_{i,j}$ if and
only if $u_{i,j}(t)\triangleleft_{i,j}0$. Otherwise if $\xi\not\in A_{i,j}$
then $u_{i,j}(\xi+t)\triangleleft_{i,j}b_{i,j}$ is either always true or
always false for $0<t<|s|$. This shows that for $0<t<|s|$ the formula
$\phi(\xi+t)$ is equivalent to a Boolean combination of formulas of the form
$u_{i,j}(t)\triangleleft_{i,j}0$, true or false.

######  Corollary 10.

Let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},1\rangle$-definable.

  1. (1)

The equivalence relation $\sim$ has finite index.

  2. (2)

The set of (distinct) spaces $\text{\em Str}{(}x)$ is finite when $x$ runs
over $\mathbb{R}^{n}$.

  3. (3)

There exists a fixed finite collection $\mathcal{C}$ of cones (in the sense of
Definition 4.1) satisfying the following condition. With each $\sim$-class $E$
is associated a subset ${\mathcal{C^{\prime}}}\subseteq\mathcal{C}$ such that
for every $x\in E$ there exists $r>0$ such that for every $t\in\mathbb{R}^{n}$
we have

$(x+t\in X)\wedge|t|<r\ \leftrightarrow\
\big{(}t\in\bigcup_{C\in\mathcal{C^{\prime}}}C\big{)}\wedge|t|<r.$

######  Proof 4.2.

Point 1 follows from the fact that $\Theta$ is finite and that two points
$x,y$ which are associated with the same formula $\theta$ in Proposition 9
satisfy $x\sim y$ by definition of $\theta$. Point 2 is a straightforward
consequence of Point 1 and Lemma 7. For Point 3 observe that all elements of
$E$ must be associated with equivalent formulas $\theta$ in Proposition 9 and
that each formula $\theta\in\Theta$ is a disjunction of formulas which define
cones.

Because of Lemma 3 we have

######  Corollary 11.

The statements of Corollary 10 extend to the case where $X$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable.

Combining Corollaries 10 and 11 allows us to specify properties of singular
points for $\langle\mathbb{R},+,{<},1\rangle$\- and
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relations.

######  Proposition 12.

Let $X\subseteq\mathbb{R}^{n}$. If $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable then it has finitely many
singular points and their components are rational numbers. If $X$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable then it has a countable
number of singular points and their components are rational numbers.

######  Proof 4.3.

By Proposition 9, if $\xi$ is not interior to $X$ or its complement, for small
enough $r>0$ the subset $X$ coincides on $B(\xi,r)$ with a finite nonempty
union of open or closed cones of which $\xi$ is an apex. The boundaries of
these cones are hyperplanes $H_{1},\ldots,H_{p}$ defined by equations of the
form $u_{h,k}(x)=b_{h,k}$ as in the proof of Proposition 9. If their normals
scan a subspace of dimension $p<n$ then the space of strata has dimension at
least $n-p$: indeed along all such directions, the expressions $u_{h,k}(x)$
are constant. Therefore a point is singular only if these normals scan the
space $\mathbb{R}^{n}$. There are finitely many hyperplanes $H_{i}$, and $n$
hyperplanes whose normals are linearly independent intersect in exactly one
point, thus the number of singular points is finite and their intersections
have rational components.

The fact that the set of singular points in an
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation is countable is
a direct consequence of the following observation. Let
$x\in[a_{1},a_{1}+1)\times\cdots\times[a_{n},a_{n}+1)$ with
$a_{1},\ldots,a_{n}\in\mathbb{Z}$. Then $x$ is $X$-singular if and only if it
is $Y$-singular in the restriction

$Y=X\cap([a_{1}-1,a_{1}+1)\times\cdots\times[a_{n}-1,a_{n}+1))$

because for $r>0$ small enough we have $B(x,r)\cap X=B(x,r)\cap Y$. By Lemma 2
each set $Y$ is $\langle\mathbb{R},+,{<},1\rangle$-definable thus has finitely
many singular points, and there is a countable number of such $Y$’s.

###  4.2. Strata in $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$

In Proposition 4 we proved that the set of strata at a given point is a vector
subspace. Here we show more precisely that this subspace has a set of
generators consisting of vectors with rational coefficients.

######  Proposition 13.

Let $X\subseteq\mathbb{R}^{n}$ be a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation and
$\xi\in\mathbb{R}^{n}$. There exists a set of linearly independent vectors
with rational coefficients generating $\text{\em Str}{(}\xi)$.

######  Proof 4.4.

Because of Lemma 3 the collection of local neighborhoods in an
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation is identical to
the collection of local neighborhoods in some
$\langle\mathbb{R},+,{<},1\rangle$-definable relation, thus it suffices to
treat the case of $\langle\mathbb{R},+,{<},1\rangle$-definable relations.

By Proposition 9 for all points $\xi\in\mathbb{R}^{n}$ there exists a
$\langle\mathbb{R},+,{<},1\rangle$-formula $\theta$ defining a finite union of
cones with apex $0$ such that for some real $s>0$ and for all
$t\in\mathbb{R}^{n}$ the following condition is satisfied.

$(\theta(t)\wedge|t|<s)\leftrightarrow(\phi(\xi+t)\wedge|t|<s)$ (5)

We give the proof for the case $\xi=0$. The argument can easily be generalized
to any $\xi\in\mathbb{R}^{n}$ using Expression (5). Given an hyperplane $H$
defined by a linear equation $u(x)=0$, we set

$H^{\varepsilon}=\left\\{\begin{array}[]{lll}\\{x\mid u(x)=0\\}&\text{ if
}\varepsilon&\text{is the symbol }=\\\ \\{x\mid u(x)<0\\}&\text{ if
}\varepsilon&\text{is the symbol }<\\\ \\{x\mid u(x)>0\\}&\text{ if
}\varepsilon&\text{is the symbol }>\\\ \end{array}\right.$

######  Lemma 14.

Let $y,z\in\mathbb{R}^{n}$ and let $H_{1},\dots,H_{q}$ be hyperplanes in
$\mathbb{R}^{n}$ containing the origin. For all nonzero vectors
$v\in\mathbb{R}^{n}$ which are parallel with no $H_{i}$, there exists
$\alpha\in\mathbb{R}$ and $\varepsilon_{1},\dots,\varepsilon_{q}$ such that
the points $y^{\prime}=y+\alpha v$ and $z^{\prime}=z+\alpha v$ belong to
$\bigcap_{1\leq i\leq q}H_{i}^{\varepsilon_{i}}$.

######  Proof 4.5.

Since $v$ is not parallel with $H_{i}$, for sufficiently large $\alpha_{i}\geq
0$ the points $y+\alpha_{i}v$ and $z+\alpha_{i}v$ belong to the same halfspace
defined by $H_{i}$. It suffices to set $\alpha=\max(\alpha_{i})$.

We return to the proof of Proposition 13. Expression (5) can be viewed as
saying that the relation $Y=\\{x\in\mathbb{R}^{n}\mid\theta(x)\\}$ satisfies
the following condition: there exist $q$ rational hyperplanes
$H_{1},\dots,H_{q}$ such that $Y$ is a finite union of subsets of the form
$\bigcap_{1\leq i\leq q}H_{i}^{\varepsilon_{i}}$ with
$\varepsilon_{i}\in\\{<,>,=\\}$. Among all possible expressions defining $Y$
and involving the hyperplanes $H_{1},\dots,H_{q}$, choose one where the
minimum subset of such hyperplanes occurs. Rename if necessary the hyperplanes
as $H_{1},\dots,H_{p}$ with $p\leq q$. We want to show that

$\text{Str}{(}0)=\bigcap_{1\leq i\leq p}H_{i}.$

Clearly, every vector $v$ parallel with all $H_{i}$ is a stratum for all cones
so that $\text{Str}{(}0)\supseteq\bigcap_{1\leq i\leq p}H_{i}$ holds. We prove
the opposite inclusion. If $\text{Str}{(}0)$ is trivial or $p=0$ we are done.
We assume by way of contradiction that for some vector $v\in\text{Str}{(}0)$,
the subset $J\subseteq\\{1,\ldots,p\\}$ of indices $j$ such that $v$ belongs
to $H_{j}$ is proper. If $J=\emptyset$, by Lemma 14 for all points
$y,z\in\mathbb{R}^{n}$ there exist $\alpha\in\mathbb{R}$ and
$\varepsilon_{1},\dots,\varepsilon_{p}$ such that the points
$y^{\prime}=y+\alpha v$ and $z^{\prime}=z+\alpha v$ belong to $\bigcap_{1\leq
i\leq p}H_{i}^{\varepsilon_{i}}$. This implies $y^{\prime}\in Y\leftrightarrow
z^{\prime}\in Y$, and since $v$ is a stratum, we get

$y\in Y\leftrightarrow y^{\prime}\in Y\leftrightarrow z^{\prime}\in
Y\leftrightarrow z\in Y$

thus $Y=\mathbb{R}^{n}$ which is defined by $\theta(x)=\texttt{true}$ and
violates the minimality of $p$.

Now we deal with $J\not=\emptyset$. By possibly renaming the hyperplanes we
assume $J=\\{r+1,\ldots,p\\}$ with $r\geq 1$. We will show that the
hyperplanes $H_{1},\ldots,H_{r}$ are useless, i.e., that $Y$ can be written as
a finite union of subsets of the form $\bigcap_{r<i\leq
p}H_{i}^{\varepsilon_{i}}$. Given a subset $A=\bigcap_{r<i\leq
p}H_{i}^{\varepsilon_{i}}$ we show that for all points $y,z\in A$ we have
$y\in Y\leftrightarrow z\in Y$. We apply again Lemma 14: there exist
$\alpha\in\mathbb{R}$ and $\varepsilon_{1},\ldots,\varepsilon_{r}$ such that
$y^{\prime}=y+\alpha v$ and $z^{\prime}=z+\alpha v$ belong to $\bigcap_{1\leq
i\leq r}H_{i}^{\varepsilon_{i}}$. Since $y,z\in A$ and $v\in\bigcap_{r<i\leq
p}H_{i}$, we get $y^{\prime},z^{\prime}\in A$ thus
$y^{\prime},z^{\prime}\in\bigcap_{1\leq i\leq p}H_{i}^{\varepsilon_{i}}$. By
definition of $\theta$ we get $y^{\prime}\in Y\leftrightarrow z^{\prime}\in
Y$, and since $v$ is a stratum we obtain $y\in Y\leftrightarrow z\in Y$. This
contradicts the minimality of $p$.

###  4.3. Application: expressing the singularity of a point in a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation

The singularity of a point $x$ is defined as the property that no intersection
of $X$ with a ball centered at $x$ is a union of lines parallel with a given
nonzero direction. This property is not directly expressible within
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ since the natural way would be to
use multiplication on reals, which is not
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. In order to be able to
express the property, we give an alternative characterization of singularity
which relies on the assumption that $X$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable.

######  Lemma 15.

Given an $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$ and $x\in\mathbb{R}^{n}$ the following two
conditions are equivalent:

  1. (1)

$x$ is singular.

  2. (2)

for all $r>0$, there exists $s>0$ such that for all nonzero vectors $v$ of
norm less than $s$, there exist two points $y,z\in B(x,r)$ such that $y=z+v$
and $y\in X\leftrightarrow z\not\in X$.

Observe that when $X$ is not
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable, the two assertions are
no longer equivalent. E.g., $\mathbb{Q}$ has only singular points but
condition 2 holds for no point in $\mathbb{R}$.

######  Proof 4.6.

In order to prove the equivalence of the two conditions, we write them
formally

$\begin{array}[]{rl}(1)&\forall r>0\ \forall
v\in\mathbb{R}^{n}\setminus\\{0\\}\ \exists s>0\ \exists y,z\ (y,z\in
B(x,r)\wedge y=sv+z\wedge(y\in X\leftrightarrow z\not\in X))\\\ (2)&\forall
r>0\ \exists s>0\ \forall v\ (0<|v|<s\rightarrow\exists y,z\ (y,z\in
B(x,r)\wedge y=v+z\wedge(y\in X\leftrightarrow z\not\in X))\end{array}$

The implication $(2)\rightarrow(1)$ is shown by contraposition, i.e.,
$\neg(1)\rightarrow\neg(2)$ and is a simple application of the rule $\exists
u\forall v\psi(u,v)\rightarrow\forall v\exists u\psi(u,v)$. Indeed, if $v_{0}$
satisfies $\neg(1)$ then for every $s$ the condition $\neg(2)$ is satisfied
with any vector $v$ colinear with $v_{0}$ of modulus less than $s$.

Now we prove $(1)\rightarrow(2)$. We must prove that if the point $x$ is
singular, then for all $r>0$ there exists $s>0$ such that for every vector
$|v|\leq s$ there exist two points $y,z$ satisfying

$y,z\in B(x,r)\wedge y=z+v\wedge(y\in X\leftrightarrow z\not\in X).$ (6)

Let $k$ be the number of disjuncts in the formula defining $X$ (cf. expression
(3)), which is also an upper bound on the number of cones composing the local
neighborhoods at a given point. In order to simplify the notation we also
assume that the point $x$ is the origin. Also, it is clear that condition
$(2)$ is satisfied if and only if it is satisfied for $r$ small enough which
means that we may assume that the following holds

$B(0,r)\cap X=B(0,r)\cap{\mathcal{C}}$ (7)

where ${\mathcal{C}}$ is the union of the cones at $0$ as defined in Corollary
11. We claim that expression (6) holds when $s$ is set to ${r\over 2k+1}$.
Since $0$ is singular, for every direction $u$ there exists a line $L_{u}(w)$
with $w\in B(0,r)\cap{\mathcal{C}}$ which contains points in $X$ and points in
the complement of $X$, that is

$\emptyset\subsetneq B(0,r)\cap{\mathcal{C}}\cap L_{u}(w)\subsetneq B(0,r)\cap
L_{u}(w).$

Because ${\mathcal{C}}$ is closed under the mappings $z\mapsto\alpha z$ for
all $\alpha>0$, for all $0<\beta\leq 1$ we have

$\emptyset\subsetneq B(0,r)\cap{\mathcal{C}}\cap L_{u}(\beta w)\subsetneq
B(0,r)\cap L_{u}(\beta w).$

By choosing $\beta$ small enough if necessary, it is always possible to assume
that the length of $B(0,r)\cap L_{u}(\beta w)$ equals some $t\geq r$. The
intersection of $L_{u}(\beta w)$ with $X$ inside $B(0,r)$ defines $p$
segments, some possibly of length $0$, successively included in and disjoint
from the cones in ${\mathcal{C}}$, with $2\leq p\leq 2k+1$. Let
$x_{0},x_{1},\ldots,x_{p}$ be the endpoints of these segments in the order
they appear along the line, with $x_{0}$ and $x_{p}$ being the intersections
with the frontier of the ball $B(0,r)$. Their projections over any of the axes
of $\mathbb{R}^{n}$ for which the coordinate of $u$ is maximal determines a
nondecreasing sequence of reals $a_{0}\leq a_{1}\leq\cdots\leq a_{p}$ such
that $a_{p}-a_{0}=t$. If $p=2$ then either $a_{1}-a_{0}\geq\frac{t}{2}\geq s$
or $a_{2}-a_{1}\geq\frac{t}{2}\geq s$ and then for all $s^{\prime}<s$ we can
choose two points $y\in(x_{0},x_{1})$ and $z\in(x_{1},x_{2})$ such that
$|y-z|=s^{\prime}$. Now assume $p>2$. We have $a_{p}-a_{0}=t\geq r$ thus there
exists $0\leq i<p$ such that
$a_{i+1}-a_{i}\geq\frac{r}{p}\geq\frac{r}{2k+1}=s$. If $i<p-1$ and
$x_{i+1}=x_{i+2}$, i.e., $a_{i+1}=a_{i+2}$ then for all
$s^{\prime}<a_{i+1}-a_{i}$, and hence for every $s^{\prime}<s$, there exists a
point $z\in(x_{i},x_{i+1})$ such that $|x_{i+1}-z|=s^{\prime}$, and we can set
$y=x_{i+1}$. The case where $i>0$ and $x_{i-1}=x_{i}$ is similar. In all other
cases, for all $s^{\prime}<s$ we can find $z\in(x_{i},x_{i+1})$ and
$y\in(x_{i+1},x_{i+2})$ such that $|y-z|={s^{\prime}}$.

##  5\. Relations between neighborhoods

We illustrate the purpose of this section with a very simple example. We start
with a cube sitting in the horizontal plane with only one face visible. The
rules of the game is that we are given a finite collection of vectors such
that for all $6$ faces and all $12$ edges it is possible to choose vectors
that generate the vector subspace of the smallest affine subspace in which
they live. Let the point at the center of the upper face move towards the
observer (assuming that this direction belongs to the initial collection). It
will eventually hit the upper edge of the visible face. Now let the point move
to the left along the edge (this direction necessarily exists because of the
assumption on the collection). The point will hit the upper left vertex.
Consequently, in the trajectory the point visits three different
$\sim$-classes: that of the points on the open upper face, that of the points
on the open edge and that of the upper left vertex. Here we investigate the
adjacency of such equivalence classes having decreasing dimensions. Observe
that another finite collection of vectors may have moved the point from the
center of the upper face directly to the upper left vertex.

Since two $\sim$-equivalent points have the same subspace of strata, we let
$\text{Str}{(}E)$ denote the common subspace of all points of a $\sim$-class
$E$. Similarly, dim($E$) is the common dimension of all the points in $E$.

###  5.1. Adjacency

Consider the backwards trajectory on the cube as discussed above: the point
passes from an $\sim$-equivalence class of low dimension into an
$\sim$-equivalence class of higher dimension along a direction that is proper
to this latter class. This leads to the notion of adjacency. For technical
reasons we allow a class to be adjacent to itself.

Let $E$ be a nonsingular $\sim$\- class and let $v$ be one of its nonzero
strata. Given a $\sim$\- class $F$, a point $y\in F$ is $v-$_adjacent_ _to_
$E$ if there exists $\epsilon>0$ such that for all $0<\alpha\leq\epsilon$ we
have $y+\alpha v\in E$.

A $\sim$\- class $F$ is $v$-_adjacent_ _to_ $E$ if there exists a point $y\in
F$ which is $v$-adjacent with $E$.

######  Lemma 16.

If the $\sim$\- class $F$ is $v$-adjacent to the $\sim$\- class $E$, all
elements of $F$ are $v$-adjacent to $E$.

There exists at most one $\sim$-class $E$ such that $F$ is $v$-adjacent to
$E$.

######  Proof 5.1.

We must show that if $y$ and $z$ belong to $F$ and if $y$ is $v$-adjacent to
$E$ then there exists a real $\alpha>0$ such that for all $0<\beta<\alpha$ we
have $y+\beta v\sim z+\beta v$. Indeed, by definition of $\sim$ there exists
$r$ such that the translation $t\mapsto t+z-y$ maps $B(y,r)\cap X$ onto
$B(z,r)\cap X$. For all $\alpha$ satisfying $|\alpha v|<r$ consider any $s$
satisfying $|\alpha v|+s<r$. Then the above translation maps $B(y+\alpha
v,s)\cap X$ onto $B(z+\alpha v,s)\cap X$, i.e., $y+\alpha v\sim z+\alpha v$ .

The second claim easily follows from the very definition of $v-$adjacency.

Observe that for any nonsingular $\sim$-class $E$ and one of its nonzero
strata $v$ there always exists a $\sim$-class $v$-adjacent to $E$, namely $E$
itself, but there might be different classes $v$-adjacent to $E$.

Let $X$ be the union of the two axes of the 2-dimensional plane and $v=(1,1)$
which we assume is one of the chosen strata of the $\sim$-class $\\{(x,y)\mid
x\not=0,y\not=0\\}$. The different classes are: the complement of $X$, the
origin $\\{0\\}$ which is a singular point, the horizontal axis deprived of
the origin, and the vertical axis deprived of the origin. The two latter
$\sim$-classes are both $v-$adjacent to the class $\mathbb{R}^{2}\setminus X$.

###  5.2. Intersection of a line and equivalence classes

In this section we describe the intersection of a $\sim$-class $E$ with a line
parallel to some $v\in\text{Str}{(}E)$.

With the example of the cube discussed at the beginning of Section 5, a line
passing through a point $x$ on the upper face along any of the directions of
$\text{Str}{(}x)$ of dimension $2$ intersects an open edge or a vertex at
point $y$. In the former case dim$(y)=1$ and in the latter dim$(y)=0$, and in
both cases $\text{Str}{(}y)\subsetneq\text{Str}{(}x)$.

######  Lemma 17.

Let $X\subseteq\mathbb{R}^{n}$, $E,F$ be two $\sim$-classes, and
$v\in\text{\em Str}{(}E)\setminus\\{0\\}$. Let $y$ be an element of $F$ which
is topologically adherent to $L_{y}(v)\cap E$. Then $\text{\em
Str}{(}F)\subseteq\text{\em Str}{(}E)$.

If $E,F$ are different, then $\text{\em Str}{(}F)\subseteq\text{\em
Str}{(}E)\setminus\\{v\\}$ and therefore $\text{dim}(F)<\text{dim}(E)$ .

######  Proof 5.2.

If $E=F$ then clearly $\text{Str}{(}F)=\text{Str}{(}E)$. Thus it suffices to
consider the case $F\not=E$. By hypothesis $B(y,r)$ intersects $E$ for every
$r>0$, which yields $\text{Str}{(}F)\subseteq\text{Str}{(}E)$ by Lemma 8. It
remains to prove that $v\not\in\text{Str}{(}F)$. We show that for every $r>0$
we can find in $B(y,r)$ two elements $z_{1},z_{2}$ such that $z_{1}\in
X\leftrightarrow z_{2}\not\in X$ and $z_{1}-z_{2}$ is parallel to $v$.

Let $r$ be a safe radius for $y$. By hypothesis there exists $y^{\prime}\in
B(y,r)\cap L_{y}(v)\cap E$. Let $s>0$ be a safe radius for $y^{\prime}$ such
that $B(y^{\prime},s)\subseteq B(y,r)$. We have $y\not\sim y^{\prime}$, thus
there exists $u$ with $|u|<s$ such that $y+u\in X\leftrightarrow
y^{\prime}+u\not\in X$. We set $z_{1}=y+u$ and $z_{2}=y^{\prime}+u$. Both
$z_{1}$ and $z_{2}$ belong to $B(y,r)$ by our hypothesis on $u,s$ and $y$.
Moreover $z_{1}-z_{2}=y-y^{\prime}$ and $y^{\prime}\in L_{v}(y)$ thus
$z_{1}-z_{2}$ is parallel to $v$.

######  Lemma 18.

Let $X\subseteq\mathbb{R}^{n}$, $x\in\mathbb{R}^{n}$ a nonsingular point and
$v\in\text{\em Str}{(x)}\setminus\\{0\\}$. There exist $y,z\in L_{v}(x)$ such
that $x\in(y,z)$ and every element $w$ of $(y,z)$ satisfies $w\sim x$.

######  Proof 5.3.

Indeed, let $r$ be a safe radius for $x$ and $(y,z)$ be an open segment on
$L_{v}(x)\cap B(x,r)$ containing $x$. Let $w\in(y,z)$ and let $t>0$ be any
real such that $B(w,t)\subseteq B(x,r)$. We show that the translation
$u\mapsto u+w-x$ defines a one-to-one correspondence from $B(x,t)\cap X$ to
$B(w,t)\cap X$. Indeed, let $z^{\prime}\in B(x,t)\cap X$. Since $B(x,r)\cap X$
is a union of lines parallel with $v$, we have $L_{v}(z^{\prime})\cap
B(w,t)\subseteq L_{v}(z^{\prime})\cap B(x,r)\subseteq X$ implying
$z^{\prime}+w-x\in B(w,t)\cap X$. Conversely, for every element $u\in
B(w,t)\cap X$ we have $u-w+x\in B(x,t)\cap X$.

Lemmas 17 and 18 lead to the following.

######  Corollary 19.

Let $X\subseteq\mathbb{R}^{n}$, $x\in\mathbb{R}^{n}$ a nonsingular point, $E$
its $\sim$-class and let $v\in\text{\em Str}{(}x)\setminus\\{0\\}$. The set
$L_{v}(x)\cap E$ is a union of disjoint open segments (possibly unbounded in
one or both directions) of $L_{v}(x)$, i.e., of the form $(y-\alpha v,y+\beta
v)$ with $0<\alpha,\beta\leq\infty$ and $y\in E$.

If $\alpha<\infty$ (resp. $\beta<\infty$) then the point $y-\alpha v$ (resp.
$y+\beta v$) belongs to a $\sim$-class $F\not=E$ where $F$ is $v$-adjacent
(resp. $(-v)$-adjacent ) to $E$, and $\text{dim}(F)<\text{dim}(E)$.

######  Proof 5.4.

In order to prove the first claim it suffices to show that for every $y\in
L_{v}(x)\cap E$, the maximal segment of $L_{v}(x)$ which contains $y$ and is
included in $E$ is an open segment. Let $0<\alpha,\beta\leq\infty$ be maximal
such that $(y-\alpha v,y+\beta v)\subseteq E$. There exist such values
$\alpha,\beta$ by Lemma 18 (applied to $y$). Now if $\alpha<\infty$ then by
maximality of $\alpha$ and Lemma 18 (applied to $y-\alpha v$) we have
$y-\alpha v\not\in E$. Similarly if $\beta<\infty$ then $y+\beta v\not\in E$.

The second claim of the corollary follows from Lemma 17.

##  6\. Characterization and decidability

###  6.1. Characterization of $\langle\mathbb{R},+,{<},1\rangle$ in
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$

In this section we give a characterization of
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relations which are
$\langle\mathbb{R},+,{<},1\rangle$-definable. A _rational section_ of a
relation $X\subseteq\mathbb{R}^{n}$ is a relation of the form

$X^{(i)}_{c}=X\cap(\mathbb{R}^{i}\times\\{c\\}\times\mathbb{R}^{n-i-1})\quad\text{for
some }c\in\mathbb{Q},\ 0\leq i<n$

######  Theorem 20.

Let $n\geq 1$ and let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. Then $X$ is
$\langle{\mathbb{R},+,<,1}\rangle$-definable if and only if the following two
conditions hold

  1. (1)

There exist finitely many $X-$singular points.

  2. (2)

Every rational section of $X$ is $\langle\mathbb{R},+,{<},1\rangle$-definable.

Observe that both conditions $(1)$ and $(2)$ are needed. Indeed, the relation
$X=\mathbb{R}\times\mathbb{Z}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. It has no singular
point thus it satisfies condition $(1)$, but does not satisfy $(2)$ since,
e.g., the rational section $X_{0}^{(0)}=\\{0\\}\times\mathbb{Z}$ is not
$\langle\mathbb{R},+,{<},1\rangle$-definable. Now, consider the relation
$X=\\{(x,x)\ |\ x\in\mathbb{Z}\\}$ which is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. It does not satisfy
condition $(1)$ since every element of $X$ is singular, but it satisfies $(2)$
because every rational section of $X$ is either empty or equal to the
singleton $\\{(x,x)\\}$ for some $x\in\mathbb{Z}$, thus is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

The necessity of point 1 follows from Proposition 12. That of point 2 results
from the fact that all rational constants are
$\langle\mathbb{R},+,{<},1\rangle$-definable by Theorem 2, and moreover that
$\langle\mathbb{R},+,{<},1\rangle$-definable relations are closed under direct
product and intersection.

Now we prove that conditions 1 and 2 are sufficient. We start with some
informal discussion. Since $X$ possesses finitely many $\sim$-classes,
Corollary 19 suggests that we prove the
$\langle\mathbb{R},+,{<},1\rangle$-definability of the $\sim$-classes by
induction on their dimension. The case of classes of dimension $0$ is easy to
handle using condition $1$. For the induction step, we use the same corollary
which asserts that the intersection of a nonsingular class $E$ with a line
passing through a point $x$ in the class and parallel to a direction of the
class is a union of open segments. If the segment containing $x$ is finite or
semifinite then one of its adherent point belongs to a class $F$ of lower
dimension and we can define $E$ relatively to $F$ via the notion of adjacency.
However the segment may be infinite and thus may intersect no other
equivalence class. So we consider the canonical subspaces defined below, and
will use the fact that every line has an intersection with one of these.

Formally we define

$\begin{array}[]{l}H_{i}=\\{(x_{1},\ldots,x_{n})\in\mathbb{R}^{n}\mid
x_{i}=0\\}\quad i\in\\{1,\ldots,n\\}\\\ \displaystyle Q_{I}=\bigcap_{i\in
I}H_{i},\quad\displaystyle
Q^{\prime}_{I}=(Q_{I}\setminus\bigcup_{i\in\\{1,\ldots,n\\}\setminus
I}H_{i})\text{ for all }\emptyset\subset
I\subseteq\\{1,\ldots,n\\}.\end{array}$ (8)

In particular $Q_{\\{1,\ldots,n\\}}=\\{0\\}$,
$Q^{\prime}_{\\{1,\ldots,n\\}}=\emptyset$ and by convention
$Q_{\emptyset}=\mathbb{R}^{n}$. The $Q^{\prime}_{i}$’s are not vector
subspaces but with some abuse of language we call them _canonical subspaces_
and write $\text{dim}(Q^{\prime}_{I})$ to mean $\text{dim}(Q_{I})=n-|I|$.
Moreover for every $I\neq\\{1,\ldots,n\\}$ the set $Q^{\prime}_{I}$ is open in
$Q_{I}$, that is

$\forall x\in Q^{\prime}_{I}\ \exists\epsilon\ \forall v\ (v\in
Q_{I}\wedge|v|<\epsilon\rightarrow x+v\in Q^{\prime}_{I})$ (9)

(indeed, it suffices to assume $|v_{j}|<|x_{j}|$ for all $j\not\in I$).
Observe that point 2 of the theorem implies that for every $I$ the
intersection $X\cap Q_{I}$ (resp. $X\cap Q^{\prime}_{I}$) is
$\langle\mathbb{R},+,{<},1\rangle$-definable. Furthermore the sets
$Q_{I}^{\prime}$ define a partition of the space. We also have a trivial but
important property which is implicit in the proof of Lemma 22.

######  Remark 21.

If $x\in Q_{I}^{\prime}$ and $v$ is a vector in the subspace $Q_{I}$ then for
all points on $y\in L_{v}(x)$ we have $y\in Q_{J}^{\prime}$ for some
$J\supseteq I$.

Using the canonical subspaces, the proof below can be seen as describing a
trajectory starting from a point $x$ in a $\sim$-class $E$, traveling along a
stratum of $E$ until it reaches a class of lower dimension $F$ (by Corollary
19) or some canonical subspace. In the first case it resumes the journey from
the new class $F$ on. In the second case it is trapped in the canonical
subspace: it resumes the journey by choosing one direction of the subspace
until it reaches a new $\sim$\- class or a point belonging to a proper
canonical subspace. Along the journey, either the dimension of the new class
or the dimension of the canonical subspace decreases. The journey stops when
the point reaches a $(X,Q_{I})-$singular point, or the origin which is the
least canonical subspace.

Given an $\langle\mathbb{R},+,{<},1\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$, a set of _principal directions_ (for $X$) is any
finite subset $V$ of vectors such that for all nonsingular points
$x\in\mathbb{R}^{n}$ and all canonical spaces $Q^{\prime}_{I}$, there exists a
subset $V^{\prime}\subseteq V$ which generates the space $\text{Str}{(}x)\cap
Q_{I}$. Observe that by Proposition 13 there is no loss of generality to
assume that $V\subseteq\mathbb{Q}^{n}$.

By Corollary 11 there exist finitely many distinct spaces $\text{\em
Str}{(}x)$ when $x$ runs over $\mathbb{R}^{n}$, thus there exists a set $V$ of
principal directions for $X$.

For every $I\subseteq\\{1,\dots,n\\}$ and every $\sim$-class $E$ we define
$E^{(I)}=E\cap Q^{\prime}_{I}$. Observe that
$E=\bigcup_{I\subseteq\\{1,\dots,n\\}}E^{(I)}$ which is a disjoint union. We
know that $X$ is a union of finitely many $\sim$-classes, see Corollary 11.
Thus in order to prove that $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable it suffices to prove that all
sets $E^{(I)}$ are $\langle\mathbb{R},+,{<},1\rangle$-definable. Consider the
(height) function $h$ which assigns to every set $E^{(I)}$ the pair of
integers

$h(E^{(I)})=(\dim(\text{Str}{(}E)\cap Q_{I}),\dim(Q^{\prime}_{I})).$

Given two $\sim$-classes $E,F$ and $I,J\subseteq\\{1,\dots,n\\}$ we define the
(partial) ordering $F^{(J)}<E^{(I)}$ if $h(F^{(J)})=(a^{\prime},b^{\prime})$
and $h(E^{(I)})=(a,b)$ with either ($a^{\prime}<a$ and $b^{\prime}\leq b$) or
($a^{\prime}\leq a$ and $b^{\prime}<b$).

We prove by induction on $(a,b)$ that each $E^{(I)}$ is definable from smaller
classes $F^{(J)}$, i.e., that $E^{(I)}$ is definable in the expansion of
$\langle\mathbb{R},+,{<},1\rangle$ obtained by adding a predicate for each
smaller class $F^{(J)}$.

Let $h(E^{(I)})=(a,b)$. If $a=0$ then the elements of $E^{(I)}$ have no
nonzero $X-$stratum in $Q_{I}$, thus they are $(X,Q_{I})-$singular, see
Definition 3. By point 2, $X\cap Q_{I}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable thus it has finitely many such
points and they are $\langle\mathbb{R},+,{<},1\rangle$-definable. The same
holds for $E^{(I)}$ which is a finite union of such points.

If $b=0$ then $Q_{I}=\\{0\\}$, thus $E^{(I)}$ is either empty or equal to the
singleton $\\{0\\}$, and in both cases $E^{(I)}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

Now assume that $a,b>0$. The following details a single step of the journey
explained above.

######  Lemma 22.

Let $I\subseteq\\{1,\dots,n\\}$ and $x\in Q^{\prime}_{I}$. Then $x\in E^{(I)}$
if and only if there exists a principal direction $v\in
V\cap\text{Str}{(x)}\cap Q_{I}$, elements $y,z\in\mathbb{R}^{n}$, some
$\sim$-class $F$ and some $J\supseteq I$ such that the following holds:

  1. (1)

$x\in(y,z)$ and $y-x=\alpha v$ for some positive real $\alpha$

  2. (2)

$(y,z)$ does not intersect any class $G^{(K)}$ such that $G^{(K)}<E^{(I)}$

  3. (3)

    1. (a)

either ($y\in F^{(J)}$ where $F^{(J)}<E^{(I)}$ and $F$ is $v-$adjacent to $E$)

    2. (b)

or ($z\in F^{(J)}$ where $F^{(J)}<E^{(I)}$ and $F$ is $(-v)-$adjacent to $E$).

######  Proof 6.1.

We first prove that the conditions are sufficient. We assume w.l.o.g. that
condition 3 holds for the case (a). By hypothesis $x\in Q^{\prime}_{I}$ and
$x\in(y,z)$, thus it suffices to prove that $(y,z)\subseteq E^{(I)}$. Set
$z=y-\gamma v$ and consider the union $U$ of all open segments $(y,y-\beta
v)$, $\beta>0$, included in $E$. Observe that $U$ is nonempty since $y$ is
$v$-adjacent to $E$. If $U$ contains $(y,z)$ we are done so we assume
$U=(y,t)$ with $t=y-\gamma^{\prime}v$ and $\gamma^{\prime}<\gamma$ and we let
$G^{(K)}$ be the class of $t$. We set $h(G^{(K)})=(a^{\prime},b^{\prime})$. By
Lemma 17 and Corollary 19 we have
$\text{Str}{(}G)\subseteq\text{Str}{(}E)\setminus\\{-v\\}$, and because of
Remark 21 it holds $K\supseteq I$.

If $K\supsetneq I$ then $b^{\prime}<b$, which leads to the inclusions

$\text{Str}{(G)}\cap Q_{K}\subseteq\text{Str}{(E)}\cap
Q_{K}\subsetneq\text{Str}{(E)}\cap Q_{I}.$

This implies $a^{\prime}\leq a$ and thus $G^{(K)}<E^{(I)}$.

If $I=K$ then $b=b^{\prime}$ and we show that $a^{\prime}<a$. The inclusion
$\text{Str}{(G)}\subseteq\text{Str}{(E)}\setminus\\{-v\\}$ along with the fact
that $v\in Q_{I}=Q_{K}$ implies $\text{Str}{(G)}\cap
Q_{K}\subsetneq\text{Str}{(E)}\cap Q_{K}$ which leads to $a^{\prime}<a$. This
implies again $G^{(K)}<E^{(I)}$ contradicting point 2.

Now we prove that the conditions are necessary. By hypothesis we have
$a\not=0$ thus $\text{Str}{(E)}\cap Q_{I}\neq\\{0\\}$, and by Definition 6.1
the set $V$ contains a basis of $\text{Str}{(E)}\cap Q_{I}$. We can choose
$v\neq 0$ as any element of this basis.

By Corollary 19 and Property (9) there exists an open segment of the line
$L_{v}(x)$ containing $x$ and only points in $E^{(I)}$. Consider the union $U$
of all such open segments. The hypothesis $b>0$ implies $\dim(Q_{I})\geq 1$
which means that $L_{v}(x)$ intersects some hyperplane $H_{j}$ with $j\not\in
I$. This implies that $L_{v}(x)$ is not a subset of $Q^{\prime}_{I}$, and a
fortiori not a subset of $E^{(I)}$, hence $U$ is not equal to $L_{v}(x)$.
Assume without loss of generality that $U$ has an extremity of the form
$x-\alpha v$ for some $\alpha>0$. We set $y=x-\alpha v$, and $z=x+\beta v$
where $\beta$ is any positive real such that $[x,x+\beta v)\subseteq E^{(I)}$.

We prove that $y,z$ satisfy the conditions of the lemma. Conditions $(1)$ and
$(2)$ are easy consequences of the very definition of $y$ and $z$. We show
that condition $(3a)$ holds. We set $y\in F^{(J)}$ and
$h(F^{(J)})=(a^{\prime},b^{\prime})$. By Remark 21 we have $I\subseteq J$ thus
$b^{\prime}\leq b$, and by Lemma 17 we have
$\text{Str}{(}F)\subseteq\text{Str}{(}E)$ thus $\text{Str}{(}F)\cap
Q_{J}=\text{Str}{(}E)\cap Q_{I}$, hence $a^{\prime}\leq a$.

If $a=a^{\prime}$, i.e $y\in E$, then $y\not\in Q_{I}$ by definition of $y$
and Property (9). It follows that $I\subsetneq J$ i.e. $b^{\prime}<b$, thus
$h(F^{(J)})<h(E^{(I)})$.

If $b=b^{\prime}$, i.e $I=J$, then by definition of $y$ and Corollary 19 we
have $E\neq F$, and using again Lemma 17 we obtain
$\text{Str}{(}F)\subseteq\text{Str}{(}E)\setminus\\{v\\}$, and this yields
$v\in(\text{Str}{(}E)\cap Q_{I})\setminus(\text{Str}{(}F)\cap Q_{J})$ i.e.
$a^{\prime}<a$, which shows that $h(F^{(J)})<h(E^{(I)})$.

We can conclude the proof of Theorem 20. By our induction hypothesis, every
set $F^{(J)}$ such that $F^{(J)}<E^{(I)}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable, thus it suffices to prove that
$E^{(I)}$ is definable in $\langle\mathbb{R},+,<,1,{\mathcal{F}}\rangle$ where

${\mathcal{F}}=\\{F^{(J)}\mid F\text{ is }v\text{ adjacent to }E\text{ for
some }v\in V\text{, and }F^{(J)}<E^{(I)}\\}.$

We use the characterization of $E^{(I)}$ given by Lemma 22 and build a formula
which expresses the conditions of this lemma. Set $Z=\\{F^{(J)}\mid
F^{(J)}<E^{(I)}\\}$ and let $V^{\prime}$ be the set of vectors $v\in V$ for
which there exist some class $F$ and some subset $J$ such that
$F^{(J)}<E^{(I)}$. A defining formula for $E^{(I)}$ is

$\chi(x):x\in Q^{\prime}_{I}\wedge\bigvee_{v\in V^{\prime}}\chi_{v}(x)$

where $\chi_{v}(x)$ is defined as follows. Denote by $A$ (resp. $B$) the set
of classes $F^{(J)}$ such that $F^{(J)}<E^{(I)}$ and $F$ is $v-$adjacent to
$E$ (resp $(-v)-$adjacent to $E$). Then

$\begin{array}[]{ll}\chi_{v}(x):&\exists y,z,\alpha,\beta\
(\alpha<0\wedge\beta>0\wedge(y=x+\alpha v\wedge z=x+\beta v)\\\
&\wedge\displaystyle\forall\gamma(\alpha<\gamma<\beta\rightarrow\bigwedge_{F^{(J)}\in
Z}\neg F^{(J)}(x+\gamma v))\wedge\\\ &\displaystyle\wedge(\bigvee_{F^{(J)}\in
A}F^{(J)}(y)\vee\bigvee_{F^{(J)}\in B}F^{(J)}(z))\big{)}.\end{array}$

###  6.2. Decidability

In this section we prove that it is decidable whether a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$ is $\langle\mathbb{R},+,{<},1\rangle$-definable.
The main idea is to construct in $(\mathbb{R},+,<,1,X)$ a sentence $\psi_{n}$
which expresses the conditions of Theorem 20, then use the
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definability of $X$ to re-write
$\psi_{n}$ as a $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-sentence, and
conclude thanks to the decidability of
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$. This is an adaptation of
Muchnik’s technique for Presburger Arithmetic [Muc03, Theorems 2 and 3]. In
order to simplify the task of constructing $\psi_{n}$ we re-formulate Theorem
20. We extend the notion of section by allowing to fix several components. A
generalized section of $X$ is a relation of the form

$X_{s,a}=\\{(x_{1},\ldots,x_{n})\in X\mid
x_{s_{1}}=a_{s_{1}}.\ldots,x_{s_{r}}=a_{s_{r}}\\}$ (10)

where $r>0$, $(s)_{1,\ldots,r}=1\leq s_{1}<\cdots<s_{r}\leq n$ is an
increasing sequence, and $a(=a_{s_{1}}.\ldots,a_{s_{r}})$ is a $r-$tuple of
reals. When $r=0$ we define $X_{s,a}=X$ by convention. If all elements of $a$
are rationals then $X_{s,a}$ is called a rational generalized section of $X$.

######  Proposition 23.

Let $n\geq 1$ and let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. Then $X$ is
$\langle{\mathbb{R},+,<,1}\rangle$-definable if and only if every rational
generalized section of $X$ has finitely many singular points.

######  Proof 6.2.

If $X$ is $\langle\mathbb{R},+,{<},1\rangle$-definable so is every rational
restriction which therefore has finitely many singular points by point 1 of
Theorem 20.

We show the opposite direction by decreasing induction of the number $r$ of
frozen components of the rational restriction. We use the fact that all
rational restrictions are
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. If $r=n-1$ the rational
generalized section is an
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable subset of $\mathbb{R}$
with finitely many singular points which implies that it consists of finitely
many intervals with rational endpoints and we are done by Corollary 1.

Fix $r>1$ and assume that all rational restrictions $X_{s,a}$ as in 10 with
$r$ frozen components are $\langle\mathbb{R},+,{<},1\rangle$-definable.
Consider a rational generalized section $X_{t,b}$ with $r-1$ frozen
components, say

$\begin{array}[]{l}(t)_{1,\ldots,r-1}=1\leq t_{1}<\cdots<t_{r-1}\leq n\\\
b=(b_{t_{1}},\ldots,b_{t_{r-1}})\quad
b_{i}\in\mathbb{Q},i=1,\ldots,r-1.\end{array}$

It has finitely many singular points by hypothesis. A rational section of
$X_{t,b}$ is defined by some increasing sequence $(s)_{1,\ldots,r}=1\leq
s_{1}<\cdots<s_{r}\leq n$ and an $r$-tuple $a=(a_{s_{1}},\ldots,a_{s_{r}})$ of
rational numbers such that for some $0\leq u\leq r-1$ we have

$\begin{array}[]{l}s_{k}=t_{k},\ k<u,\quad s_{k+2}=t_{k+1},\ u\leq k\\\
a_{k}=b_{k},\ k<u,\quad a_{k+2}=b_{k+1},\ u\leq k\end{array}$

But then all $X_{t,b}$ are $\langle\mathbb{R},+,{<},1\rangle$-definable by
induction and so is $X_{s,a}$ by Theorem 20.

So far we did not distinguish between formal symbols and their interpretations
but here we must do it if we want to avoid any confusion. In order to express
that a $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable $n-$ary relation
$X$ is actually $\langle\mathbb{R},+,{<},1\rangle$-definable we proceed as
follows. Let $\\{{\mathcal{X}}_{n}(x_{1},\dots,x_{n})\ |\ n\geq 1\\}$ be a
collection of relational symbols. We construct a
$\\{+,<,1,{\mathcal{X}}_{n}\\}-$sentence $\psi_{n}({\mathcal{X}}_{n})$ such
that $\psi_{n}(X_{n})$ holds if and only $X_{n}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Proposition 24.

Let $\\{{\mathcal{X}}_{n}(x_{1},\dots,x_{n})\ |\ n\geq 1\\}$ denote a set of
relational symbols. For every $n\geq 1$ there exists a
$\\{+,<,1,{\mathcal{X}}_{n}\\}-$sentence $\psi_{n}$ such that for every
$\\{+,<,1,{\mathcal{X}}_{n}\\}-$structure
${\mathcal{M}}=(\mathbb{R},+,<,1,X_{n})$, if $X_{n}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable then we have
$\mathcal{M}\models\psi_{n}$ if and only if $X_{n}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Proof 6.3.

For each $I\subseteq\\{1,\ldots,n\\}$ we let $\mathbb{R}^{I}$ denote the
Cartesian product of copies of $\mathbb{R}$ indexed by $I$ and for all nonzero
reals $r$ and all $x\in\mathbb{R}^{I}$ we set
$B_{I}(x,r)=\\{y\in\mathbb{R}^{I}\mid|x-y|<r\\}$. Using Lemma 15 we can
construct the following $\\{+,<,1,{\mathcal{X}}_{n}\\}-$formula which
expresses the fact that a point $x+y$ where $x\in\mathbb{R}^{I}$ and
$y\in\mathbb{R}^{[n]\setminus I}$ is singular, when seen as a point of the
generalized section of $X_{n}$ obtained by freezing to $y$ the components of
$[n]\setminus I$ (with some abuse of notation we write $x+y$ for
$x\in\mathbb{R}^{I}$ and $y\in\mathbb{R}^{[n]\setminus I}$):

$\begin{array}[]{l}\texttt{Sing}_{n,I}(x,y,{\mathcal{X}}_{n})\equiv\forall
r\in\mathbb{R}\exists s\in]0,r[\ \forall q\in\mathbb{R}^{I}\
|q|<s\rightarrow\\\ \ \ \ \exists z\in\mathbb{R}^{I}((z,z+q\in
B_{I}(x,r))\wedge(y+z\in{\mathcal{X}}_{n}\leftrightarrow
y+z+q\notin{\mathcal{X}}_{n})).\\\ \end{array}$ (11)

Now we construct a $\\{+,<,1,{\mathcal{X}}_{n}\\}-$sentence $\psi_{n}$ which
expresses the condition of Proposition 23. Some difficulty arises from the
fact that we have to express that every rational generalized section of $X$
has finitely many singular points, but the set $\mathbb{Q}$ is not
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. In order to overcome
this issue, we construct $\psi_{n}$ in such a way that it expresses that every
generalized section of $X$ has finitely many singular points. We define
$\psi_{n}$ as

$\psi_{n}\equiv\bigwedge_{I\subseteq[n]}\forall y\in\mathbb{R}^{[n]\setminus
I}\ \varphi_{n,I}(y)$

where

$\begin{array}[]{lll}\varphi_{n,I}(y)&\equiv&\exists M>0\ \forall
x\in\mathbb{R}^{I}\
(\texttt{Sing}_{n,I}(x,y,{\mathcal{X}}_{n})\rightarrow|x|<M)\\\ &&\wedge\
\exists m>0\ \forall x,x^{\prime}\in\mathbb{R}^{I}\\\ &&\quad((x\neq
x^{\prime}\wedge\texttt{Sing}_{n,I}(x,y,{\mathcal{X}}_{n})\wedge\texttt{Sing}_{n,I}(x^{\prime},y,{\mathcal{X}}_{n}))\rightarrow|x-x^{\prime}|>m).\\\
\end{array}$ (12)

The formula $\varphi_{n,I}(y)$ expresses that the generalized section of
$X_{n}$ obtained by freezing to $y$ the components of $[n]\setminus I$ has
finitely many singular points.

We prove first that if $X_{n}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable and satisfies the
formula $\psi_{n}$, then it is $\langle{\mathbb{R},+,<,1}\rangle$-definable.
Consider a rational generalized section $X_{s,a}$ of $X$ with
$(s)_{1,\ldots,r}=1\leq s_{1}<\cdots<s_{r}\leq n$ and
$a=(a_{1},\dots,a_{r})\in\mathbb{Q}^{r}$. Let $I=\\{s_{1},\dots,s_{r}\\}$. The
sentence $\psi_{n}$ holds, thus in particular the formula $\varphi_{n,I}(y)$
holds when we assign the $r-$tuple $a$ to the $r$ components of $y$. It
follows that $X_{s,a}$ has finitely many singular points, and the result
follows from Proposition 23.

Conversely assume that the
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation $X_{n}$ is also
$\langle\mathbb{R},+,{<},1\rangle$-definable. Then we show that the formula
$\psi_{n}(X_{n})$ holds. Indeed, if this were not the case, then for some
$I\subseteq[n]$ the predicate $\forall y\in\mathbb{R}^{[n]\setminus I}\
\varphi_{n,I}(y)$ would be false, i.e $\varphi_{n,I}(y)$ would be false for
some assignment of $y$. This implies that the formula
$\gamma_{n}(y)\equiv\neg\varphi_{n,I}(y)$ (in which the only free variables
are the $(n-|I|)$ variables constituting $y$) defines a nonempty subset $Y$ of
$\mathbb{R}^{n-|I|}$. Now $\gamma_{n}$ is a
$\\{+,<,1,{\mathcal{X}}_{n}\\}-$formula, and $X_{n}$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable, thus $Y$ is also
$\langle\mathbb{R},+,{<},1\rangle$-definable. By Corollary 1(2), $Y$ contains
a $(n-|I|)-$tuple $q$ of rational elements. Therefore the formula
$\neg\varphi_{n,I}(y)$ holds when we assign the value $q$ to $y$, and this
implies that there exists a rational generalized section of $X$ which has
infinitely many singular points, and by Proposition 23 this leads to a
contradiction.

######  Theorem 25.

For every $n\geq 1$ and every
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$, it is decidable whether $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Proof 6.4.

Assume that $X$ is $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable by
the formula $\phi(x)$. In Proposition 24, if we substitute $\phi(x)$ for every
occurrence of $x\in{\mathcal{X}}_{n}$ in $\psi_{n}$, then we obtain a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-sentence $\Gamma_{n}$ which holds
in $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ if and only if $X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable. The result follows from the
decidability of $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ [Wei99].

Let us give a fair estimate of the complexity of the decision problem of
Theorem 25. One can derive from [Wei99, Section 5] that the known triply-
exponential upper bound for the deterministic time complexity of deciding
Presburger Arithmetic sentences [Opp78] still holds for
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$. We proved that given $n\geq 1$
and a relation $X\subseteq\mathbb{R}^{n}$ which is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable by $\phi$, the question
of whether $X$ is $\langle\mathbb{R},+,{<},1\rangle$-definable amounts to
decide whether the sentence $\Gamma_{n}$ holds in
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$.

It is easy to check that the length of $\Gamma_{n}$ is of the order of $2^{n}$
times the length of $\phi$. Consequently, for fixed $n$, the length of
$\Gamma_{n}$ is linear with respect to the one of $\phi$, thus we also get a
triply-exponential upper bound for the deterministic time complexity of our
decision problem.

##  7\. Non-existence of an intermediate structure between
$\langle\mathbb{R},+,{<},1\rangle$ and
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$

Our aim is to prove the following result.

######  Theorem 26.

If $X\subseteq\mathbb{R}^{n}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable but not
$\langle\mathbb{R},+,{<},1\rangle$-definable then the set $\mathbb{Z}$ is
definable in $\langle{\mathbb{R},+,<,1,X}\rangle$.

In other words, for every $X\subseteq\mathbb{R}^{n}$ which is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable, then
$\langle{\mathbb{R},+,<,1,X}\rangle$ is inter-definable with either
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ or
$\langle\mathbb{R},+,{<},1\rangle$.

###  7.1. Periodicity in $\mathbb{R}$

Consider $X\subseteq\mathbb{R}$ and $p\in\mathbb{R}\setminus\\{0\\}$.

Then $X$ is periodic of _period_ $p$ (or $p-$periodic) if for every real $x$
we have $x\in X\leftrightarrow x+p\in X$.

It is ultimately right $p-$periodic if there exists $m\in\mathbb{R}$ such that
for every real $x$ with $x\geq m$, we have $x\in X\leftrightarrow x+p\in X$.
We say that $p$ is a _right ultimate period_.

It is ultimately left $p-$periodic if there exists $m\in\mathbb{R}$ such that
for every real $x$ with $x\leq m$, we have $x\in X\leftrightarrow x+p\in X$.
We say that $p$ is a _left ultimate period_.

Observe that the empty set is $p-$periodic, ultimately right $p-$periodic,
ultimately left $p-$periodic for every $p\not=0$. We apply these notions and
results concerning $\langle\mathbb{R},+,{<},1\rangle$\- and
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable subsets of $\mathbb{R}$.

######  Proposition 27.

  1. (1)

A $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable set
$A\subseteq\mathbb{R}$ is periodic if and only if it is of the form
$p\mathbb{Z}+B$ where $p\in\mathbb{Q}$ and $B\subseteq[0,p)$ is a finite union
of intervals with rational endpoints.

  2. (2)

For every $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable set
$A\subseteq\mathbb{R}$ there exist two periodic sets
$A_{1},A_{2}\subseteq\mathbb{R}$ and two reals $m_{1},m_{2}$ such that
$A\cap[m_{1},+\infty)=A_{1}\cap[m_{1},+\infty)$ and
$A\cap(-\infty,m_{2}]=A_{2}\cap(-\infty,m_{2}]$111Theorem 6.1 of [Wei99]
misses the case where the subset $A$ has different right and left ultimate
periods such as $-2\mathbb{N}\cup 3\mathbb{N}$..

######  Proof 7.1.

$(1)$ Assume that $A$ is periodic of period $p$. Let $B=A\cap[0,p)$. Then
$A=p\mathbb{Z}+B$. Since $B$ is $\langle\mathbb{R},+,{<},1\rangle$-definable
it is a finite union of intervals included in $[0,p)$ with rational endpoints.
The converse is trivial.

$(2)$ Let $A\subseteq\mathbb{R}$ be
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable. We prove the existence
of $A_{1}$ and $m_{1}$ (the proof for $A_{2}$ and $m_{2}$ is similar). By
Theorem 2.1 we have

$A=\bigcup^{K}_{k=1}(B_{k}+C_{k})$ (13)

where all $B_{k}\subseteq\mathbb{Z}$ are disjoint
$\langle\mathbb{Z},+,<\rangle$-definable subsets and all $C_{k}\subseteq[0,1)$
are distinct $\langle\mathbb{R},+,{<},1\rangle$-definable subsets.

By [Pre27] for every $k$ there exist two integers $n_{k},p_{k}\geq 0$ such
that

$\forall x\geq n_{k}\ x\in B_{k}\leftrightarrow x+p_{k}\in B_{k}.$ (14)

Observe that if (14) holds for $n_{k},p_{k}$ then it still holds for the pair
of integers $m_{1},p\geq 0$ where $p=\text{lcm}\\{n_{j}\mid 1\leq j\leq K\\}$
and $m_{1}$ is a sufficiently large a multiple of $p$. Therefore for every
$k\in\\{1,\dots,K\\}$ we have

$\forall x\geq m_{1}\ x\in B_{k}\leftrightarrow x+p\in B_{k}.$ (15)

This implies that there exist $K$ disjoint sets
$S_{k}\subseteq\\{0,\ldots,p-1\\}$ such that for every $k\in\\{1,\dots,K\\}$
we have

$B_{k}\cap[m_{1},\infty)=(p\mathbb{Z}+S_{k})\cap[m_{1},\infty).$

The claim of the proposition follows by setting $A_{1}=p\mathbb{Z}+B$ where
$B=\displaystyle\bigcup^{K}_{k=1}S_{k}+C_{k}\subseteq[0,p)$.

######  Lemma 28.

With the notations of Proposition 27$(2)$, a real $q$ is a right (resp. left)
ultimate period of the $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
subset $A$ if and only if it is a period of $A_{1}$ (resp. $A_{2}$).

######  Proof 7.2.

We only give the proof for $A_{1}$ (the proof for $A_{2}$ can be handled
similarly). It follows from the equivalences

$\begin{array}[]{ll}\forall y\geq m_{1}&y\in A\leftrightarrow y\in
A_{1}\leftrightarrow y+q\in A_{1}\leftrightarrow y+q\in A\\\ \forall y\geq
m_{1}&y\in A_{1}\leftrightarrow y\in A\leftrightarrow y+q\in A\leftrightarrow
y+q\in A_{1}.\end{array}$

######  Lemma 29.

With the notations of Proposition 27 $(2)$, if $A=p\mathbb{Z}+B$ with
$\emptyset\subsetneq B\subsetneq[0,p)$, then the set of periods of $A$ is a
discrete cyclic subgroup of $\mathbb{R}$ whose elements are rational. It is
generated by its element of minimal positive absolute value.

######  Proof 7.3.

The set $P$ of periods of $A$ is clearly a subgroup. Let us prove that $P$ is
discrete, i.e. that there cannot be arbitrarily small periods. Indeed, set
$A=p\mathbb{Z}+B$ where $p\geq 0$, $B$ is a finite union of intervals in
$[0,p)$ and $\emptyset\subsetneq B\subsetneq[0,p)$. Let $q>0$ be a period of
$A$. We consider three exclusive cases:

  1. (1)

if $B=\\{0\\}$ or $B=(0,p)$, then the condition $q=0+q\in A$ implies $q\geq
p$.

  2. (2)

if both $B$ and $[0,p)\setminus B$ consist of a unique interval, then we have
either $B=[a,p)$ with $a>0$ or $B=[0,b)$ with $b<p$. In the first case we have
$q\geq a$ and in the latter case $q\geq p-b$.

  3. (3)

if $B$ or $[0,p)\setminus B$ consist of at least two intervals: since a set
and its complement have the same periods, we can assume without loss of
generality that $B$ contains two disjoint and consecutive intervals with
respective extremities $a_{1},b_{1}$ and $a_{2},b_{2}$ (the proof for the
other case is similar). If $b_{1}=a_{2}$ then $(a_{1},b_{1})$ is right open
and $(a_{2},b_{2})$ is left open. Then the fact that $q$ is a period and the
equality $b_{1}=a_{2}\in A$ imply $b_{1}-q,a_{2}+q\in A$ thus
$q\geq\max\\{b_{1}-a_{1},b_{2}-a_{2}\\}$. Now if $b_{1}<a_{2}$ then for all
$a_{1}<y<b_{1}$ we have $y+q\in A$ which implies $q\geq a_{2}-b_{1}$.

We proved that $P$ admits a minimal positive element, say $p_{0}$. The fact
that $P$ is cyclic and generated by $p_{0}$ is well-known. In order to prove
that $P\subseteq\mathbb{Q}$, it suffices to prove that $p_{0}\in\mathbb{Q}$.
Now the $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-formula

$\phi(p)=p>0\wedge\forall x\ (x\in A\leftrightarrow x+p\in A)$

defines the set $P^{+}$ of positive elements of $P$, thus $p_{0}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable as the minimal element
of $P^{+}$, and the result follows from Corollary 1(2).

As a consequence of Lemmas 28 and 29, and Proposition 27 we obtain the
following result.

######  Lemma 30.

If $A\subseteq\mathbb{R}$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable but not
$\langle\mathbb{R},+,{<},1\rangle$-definable then $A$ has either a minimal
ultimate right or a minimal ultimate left period.

######  Proof 7.4.

Either $A\cap(-\infty,0]$ or $A\cap[0,\infty)$ is not
$\langle\mathbb{R},+,{<},1\rangle$-definable. Assume that the latter case
holds, and let us prove that $A$ admits a minimal ultimate right period. By
Proposition 27 there exist a periodic subset $A_{1}$ and a real $m$ such that
$A\cap[m,\infty[=A_{1}\cap[m,\infty[$. With the notations of Proposition 27 we
have $A_{1}=p\mathbb{Z}+B$ where $B\subseteq[0,p)$. Now the set
$A\cap[0,\infty)$ is $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable but
not $\langle\mathbb{R},+,{<},1\rangle$-definable, thus by Lemma 2 it cannot
have an upper bound, and the same holds for $A_{1}$. It follows that
$B\neq\emptyset$. Using a similar argument with the complement of $A$ leads to
$B\neq[0,p)$. Thus by Lemmas 28 and 29, $A_{1}$ admits a minimal period which
is also a minimal ultimate right period of $A$.

Similarly if $A\cap(-\infty,0]$ is not
$\langle\mathbb{R},+,{<},1\rangle$-definable then $A$ admits a minimal
ultimate left period.

######  Lemma 31.

If $A\subseteq\mathbb{R}$ is ultimately right periodic and admits a minimal
ultimate right period $p>0$, then

  1. (1)

For all reals $x,y$, if

$\forall u\geq 0\ (x+u\in A\leftrightarrow y+u\in A)$ (16)

then $p$ divides $x-y$.

  2. (2)

Conversely for every $z$ multiple of $p$ there exist $x,y$ satisfying (16) and
$x-y=z$.

######  Proof 7.5.

$(1)$ It suffices to prove that $x-y=q$ is an ultimate right period. We have

$\begin{array}[]{ll}\forall v\geq x\quad v=x+(v-x)\in A\leftrightarrow
y+(v-x)\in A\leftrightarrow v+q\in A.\\\ \end{array}$

$(2)$ Let $m$ be such that

$\forall t\geq m\ (t\in A\leftrightarrow t+p\in A).$

This condition implies that for all positive multiples $q$ of $p$ we have

$\forall t\geq m\ (t\in A\leftrightarrow t+q\in A).$

Set $x=m,y=m+q$ and $u=t-m$. The above condition is equivalent to

$\forall u\geq 0\ (x+u\in A\leftrightarrow y+u\in A).$

###  7.2. Proof of Theorem 26

Now we proceed by induction on the dimension $n$. Assume $n=1$. If $X$ is
definable in $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ but not in
$\langle\mathbb{R},+,{<},1\rangle$ then by Lemma 30, the set $X$ has either a
minimal ultimate left or a minimal ultimate right period. Assume w.l.o.g that
the latter case holds, i.e that $X$ has an ultimate right period $p>0$. By
Lemma 29, $p$ is a rational number, say $p=\frac{a}{b}$.

Applying Lemma 31 the subset $\mathbb{Z}$ can be defined in
$\langle\mathbb{R},+,<,1,X\rangle$ by the formula

$\phi_{X}(x)=\exists y,z\ \forall u\geq 0\ ((y+u\in X\leftrightarrow z+u\in
X)\wedge ax=b(y-z)).$

Now we pass to the general case $n\geq 2$. Let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable but not
$\langle\mathbb{R},+,{<},1\rangle$-definable. By Theorem 20, either some
rational section of $X$ is not $\langle\mathbb{R},+,{<},1\rangle$-definable,
or $X$ admits infinitely many singular points. In the first case, the result
follows from the induction hypothesis and the fact that every rational section
of $X$ is definable in $\langle{\mathbb{R},+,<,1,X}\rangle$ thus also in
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$.

In the second case, by Proposition 12 the set $X$ contains a countably
infinite number of singular points. The set $S$ of singular points is
$\langle\mathbb{R},+,<,1,X\rangle$-definable by the formula (11) thus it is
also $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable and the same holds
for any projection of $S$ over a component. Therefore some of the $n$
projections over the $n$ components is a
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable subset of $\mathbb{R}$
and contains a countably infinite number of singular points thus is not
$\langle\mathbb{R},+,{<},1\rangle$-definable, and we may apply case $n=1$. ∎

##  8\. Yet another characterization

We provide in this section an alternative characterization of
$\langle\mathbb{R},+,{<},1\rangle$-definability for
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relations.

A line in $\mathbb{R}^{n}$ is rational  if it is the intersection of
hyperplanes defined by equations with rational coefficients. Every rational
line is $\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Theorem 32.

A $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation
$X\subseteq\mathbb{R}^{n}$ is $\langle\mathbb{R},+,{<},1\rangle$-definable if
and only if the intersection of $X$ with every rational line is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

######  Proof 8.1.

The condition is necessary because every rational line is
$\langle\mathbb{R},+,{<},1\rangle$-definable and the set of
$\langle\mathbb{R},+,{<},1\rangle$-definable relations is closed under
intersection.

Now we prove the converse. By Proposition 23 it suffices to prove that all
rational restrictions have finitely many singular points. Since all rational
restrictions of $X$ are $\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable
the result will follow from the next Lemma.

######  Lemma 33.

Let $X\subseteq\mathbb{R}^{n}$ be
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable relation and assume the
intersection of $X$ with every rational line is
$\langle\mathbb{R},+,{<},1\rangle$-definable. Then $X$ has finitely many
singular points.

######  Proof 8.2.

We prove that if $X$ has infinitely many singular points then there exists
some rational line $l$ such that $l\cap X$ is not a finite union of segments,
which contradicts the fact that $l\cap X$ is
$\langle\mathbb{R},+,{<},1\rangle$-definable.

Let us first prove that the set of singular points is unbounded. Assume for a
contradiction that there exists a rational number $M>0$ such that
$X\cap[0,M)^{n}$ contains all $X-$singular points. The set
$X^{\prime}=X\cap[0,M]^{n}$ is $\langle\mathbb{R},+,{<},1\rangle$-definable by
Proposition 2, and moreover by definition every $X-$singular element of
$[0,M)^{n}$ is also $X^{\prime}-$singular, thus there exist infinitely many
$X^{\prime}-$singular points, which contradicts Theorem 20.

An hypercube of the form $[a_{1},a_{1}+1]\times\cdots\times[a_{n},a_{n}+1]$
with $a_{1},\ldots,a_{n}\in\mathbb{Z}$ is called _elementary_. All
$X$-singular points which belong to the interior of some elementary hypercube
$H$ are $(X\cap H)$-singular and the converse is true. Observe that a point
may be $X$-singular without being $(X\cap H)$-singular if it belongs to the
boundary of the hypercube. In order to avoid this problem we consider an
elementary cube surrounded by its $3^{n}-1$ neighbours. Then a point in a
elementary cube is $X$-singular if and only if it is singular in this enlarged
hypercube.

Formally, we start by extending the notion of integer part to vectors in
$\mathbb{R}^{n}$ by setting for every point $x\in\mathbb{R}^{n}$

$\lfloor x\rfloor=(\lfloor x_{1}\rfloor,\ldots,\lfloor x_{n}\rfloor).$

Set $\mathcal{S}=\\{-1,0,1\\}^{n}$. For all $\sigma\in\mathcal{S}$ and
$a\in\mathbb{Z}^{n}$ define

$\begin{array}[]{l}D_{\sigma}=\overbrace{[0,1]\times\cdots\times[0,1]}^{n\text{
times}}+\sigma,\ H_{\sigma}(a)=(a+D_{\sigma})\cap X,\
L_{\sigma}(a)=-a+H_{\sigma}(a)\end{array}$

and

$H(a)=\bigcup_{\sigma\in\mathcal{S}}H_{\sigma}(a),\
L(a)=\bigcup_{\sigma\in\mathcal{S}}L_{\sigma}(a).$

Because of the decomposition of Theorem 2.1, the set $\mathcal{L}$ of distinct
subsets $L(a)$, called _elementary neighborhood_ , is finite when $a$ ranges
over $\mathbb{Z}^{n}$ since each $-\sigma+L_{\sigma}(a)$ is equal to some
$X^{(F)}_{k}$. Furthermore, say that $H(a)$ _contains a singular point_ $x$ if
$x$ is $X$-singular and $x\in H_{(0,\ldots,0)}(a)$. Since the set of singular
points is unbounded, there exist a fixed $L\in\mathcal{L}$ and infinitely many
$a$’s such that $a+L_{(0,\ldots,0)}(a)$ contains a singular point.
Furthermore, in each $L_{(0,\ldots,0)}(a)$ there exist at most finitely many
$X$-singular points. Consequently, there exists a fixed element
$z\in\mathbb{Q}^{n}\cap[0,1]\times\cdots\times[0,1]$ and a fixed elementary
neighborhood $L$ such that for infinitely many $a\in\mathbb{Z}^{n}$ the point
$a+z$ is $X$-singular and $L_{a}=L$. Consider the integer $K$ as defined in
Theorem 2.1, and the mapping $\iota:\mathcal{S}\mapsto\\{1,\ldots,K\\}$ such
that

$L=\bigcup_{\sigma\in\mathcal{S}}\sigma+X^{(F)}_{\iota(\sigma)}.$

The set of elements $a$ satisfying $L_{a}=L$ is the intersection

$\displaystyle\bigcap_{\sigma\in\mathcal{S}}-\sigma+X^{(I)}_{\iota(\sigma)}\subseteq\mathbb{Z}^{n}$

which is infinite and semilinear. Now, all infinite semilinear subsets contain
a subset of the form $A=u+\mathbb{N}v$ where $u,v\in\mathbb{Z}^{n}$ with
$v\not=0$.

For some sufficiently small positive real $r$, for all $w\in A$ the sets
$-w+(B(w,r)\cap X)$ are identical. Consider any element $w^{\prime}\in A$, and
assume further that $r\in\mathbb{Q}$. Since $w^{\prime}$ is singular,
$B(w^{\prime},r)\cap X$ is not a union of lines parallel to any direction and
in particular to the direction $v$. Thus the set $Y_{r}$ of points
$t\in\mathbb{R}^{n}$ such that $|t|<r$ and $B(w^{\prime},r)\cap
L_{v}(w^{\prime}+t)$ intersects both $X$ and its complement is not empty. Now
both $w^{\prime}$ and $r$ have rational components, and $X$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable, thus $Y_{r}$ is also
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable, and since it is bounded
it is also $\langle\mathbb{R},+,{<},1\rangle$-definable by Lemma 2. By
Corollary 1(2), $Y_{r}$ contains an element $t\in\mathbb{Q}^{n}$. Now for all
$w\in A$ the sets $-w+(B(w,r)\cap X)$ are identical, and $|t|<r$, thus for
every $w\in A$ the segment $B(w,r)\cap L_{v}(w+t)$ intersects both $X$ and its
complement. It follows that the line $\ell=L_{v}(w^{\prime}+t)$ (which
coincides with all lines $L_{v}(w+t)$ for $w\in A$) is such that $l\cap X$ is
not a finite union of segments, and thus by Corollary 1(1) cannot be
$\langle\mathbb{R},+,{<},1\rangle$-definable.

This concludes the proof of Theorem 32.

##  9\. Conclusion

We discuss some extensions and open problems.

It is not difficult to check that the main arguments used to prove Theorems
25, 26 and 32, still hold if one replaces $\mathbb{R}$ with $\mathbb{Q}$.
Observe that by [Mil01], $\langle{\mathbb{Q},+,<,\mathbb{Z}}\rangle$ and
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ are elementary equivalent
structures.

Is it possible to remove our assumption that $X$ is
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$-definable in Theorem 20? We
believe that the answer is positive222we proved this claim after the present
paper was written (preprint available at https://arxiv.org/abs/2102.06160)..
Note that even if one proves such a result, the question of providing an
effective characterization is more complex. Indeed the sentence $\psi_{n}$ of
Proposition 24 expresses a variant of the criterion of Theorem 20, and we use
heavily the fact that we work within
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ to ensure that this variant is
actually equivalent to the criterion.

In particular the construction of $\psi_{n}$ relies on Lemma 15 to express
that a point is $X-$singular. However if we consider, e.g., $X=\mathbb{Q}$
then every element $x$ of $X$ is singular while no element $x$ of $X$
satisfies the condition stated in Lemma 15.

Another question is the following. In Presburger arithmetic it is decidable
whether or not a formula is equivalent to a formula in the structure without
$<$, cf. [CF10]. What about the case of the structure
$\langle\mathbb{R},+,{<},\mathbb{Z}\rangle$ ?

## Acknowledgment

We wish to thank the anonymous referee and Erich Grädel for useful
suggestions.

## References

  * [BB09] Bernard Boigelot and Julien Brusten.  A generalization of Cobham’s theorem to automata over real numbers.  Theoretical Computer Science, 410(18):1694–1703, 2009.
  * [BBB10] Bernard Boigelot, Julien Brusten, and Véronique Bruyère.  On the sets of real numbers recognized by finite automata in multiple bases.  LMCS, 6(1):1–17, 2010.
  * [BBD12] Bernard Boigelot, Julien Brusten, and Jean-François Degbomont.  Automata-based symbolic representations of polyhedra.  In Adrian-Horia Dediu and Carlos Martín-Vide, editors, Language and Automata Theory and Applications - 6th International Conference, LATA 2012, A Coruña, Spain, March 5-9, 2012. Proceedings, volume 7183 of Lecture Notes in Computer Science, pages 3–20. Springer, 2012.
  * [BBL09] Bernard Boigelot, Julien Brusten, and Jérôme Leroux.  A generalization of Semenov’s theorem to automata over real numbers.  In Renate A. Schmidt, editor, Automated Deduction – CADE-22. Springer Berlin Heidelberg, 2009.
  * [BDEK07] Bernd Becker, Christian Dax, Jochen Eisinger, and Felix Klaedtke.  Lira: Handling constraints of linear arithmetics over the integers and the reals.  In Werner Damm and Holger Hermanns, editors, Computer Aided Verification. Springer Berlin Heidelberg, 2007.
  * [Bès13] Alexis Bès.  Expansions of MSO by cardinality relations.  Logical Methods in Computer Science, 9(4), 2013.
  * [BFL08] Florent Bouchy, Alain Finkel, and Jérôme Leroux.  Decomposition of decidable first-order logics over integers and reals.  In 2008 15th International Symposium on Temporal Representation and Reasoning, pages 147–155. IEEE, 2008.
  * [BN88] Hanspeter Bieri and Walter Nef.  Elementary set operations with d-dimensional polyhedra.  In Workshop on Computational Geometry, pages 97–112. Springer, 1988\.
  * [Boi] Bernard Boigelot.  The Liege automata-based symbolic handler (LASH).  available at http://www.montefiore.ulg.ac.be/~boigelot/research/lash/.
  * [BRW98] Bernard Boigelot, Stéphane Rassart, and Pierre Wolper.  On the expressiveness of real and integer arithmetic automata.  In Kim G. Larsen, Sven Skyum, and Glynn Winskel, editors, Automata, Languages and Programming, pages 152–163. Springer Berlin Heidelberg, 1998.
  * [Büc62] J. Richard Büchi.  On a decision method in the restricted second-order arithmetic.  In Proc. Int. Congress Logic, Methodology and Philosophy of Science, Berkeley 1960, pages 1–11. Stanford University Press, 1962.
  * [CF10] Christian Choffrut and Achille Frigeri.  Deciding whether the ordering is necessary in a Presburger formula.  DMTCS, 12(1):20–38, 2010.
  * [Cob69] Alan Cobham.  On the base-dependence of sets of numbers recognizable by finite automata.  Mathematical systems theory, 3(2):186–192, 1969.
  * [Con18] Gabriel Conant.  There are no intermediate structures between the group of integers and presburger arithmetic.  J. Symb. Log., 83(1):187–207, 2018.
  * [FQSW20] Martin Fränzle, Karin Quaas, Mahsa Shirmohammadi, and James Worrell.  Effective definability of the reachability relation in timed automata.  Inf. Proc. Letters, 153:105871, 2020.
  * [FR75] Jeanne Ferrante and Charles Rackoff.  A decision procedure for the first order theory of real addition with order.  SIAM Journal on Computing, 4(1):69–76, 1975.
  * [GS66] Seymour Ginsburg and Edwin Spanier.  Semigroups, Presburger formulas, and languages.  Pacific journal of Mathematics, 16(2):285–296, 1966.
  * [Hie19] Philipp Hieronymi.  When is scalar multiplication decidable?  Annals of Pure and Applied Logic, 170(10):1162 – 1175, 2019.
  * [Ler05] Jérôme Leroux.  A polynomial time Presburger criterion and synthesis for number decision diagrams.  In Proc. LICS’05, pages 147–156. IEEE, 2005.
  * [Mil01] Chris Miller.  Expansions of dense linear orders with the intermediate value property.  The Journal of Symbolic Logic, 66(4):1783–1790, 2001.
  * [Mil17] Arthur Milchior.  Büchi automata recognizing sets of reals definable in first-order logic with addition and order.  In International Conference on Theory and Applications of Models of Computation, pages 440–454. Springer, 2017.
  * [Muc03] An. A. Muchnik.  The definable criterion for definability in Presburger arithmetic and its applications.  Theoretical Computer Science, 290(3):1433–1444, 2003.
  * [Opp78] Derek C Oppen.  A $2^{2^{2^{pn}}}$ upper bound on the complexity of Presburger arithmetic.  Journal of Computer and System Sciences, 16(3):323–332, 1978.
  * [Pre27] Mojesz Presburger.  Über die Vollstandigkeit eines gewissen Systems der Arithmetic ganzer Zahlen, in welchem die Addition als einzige Operation hervortritt.  In C.R. du Premier Congrès des Mathématiciens des Pays Slaves, pages 92–101, 395, Warsaw, 1927.
  * [PW00] Françoise Point and Frank O Wagner.  Essentially periodic ordered groups.  Annals of Pure and Applied Logic, 105(1-3):261–291, 2000.
  * [Sem77] Alexei L. Semenov.  Presburgerness of predicates regular in two number systems.  Siberian Mathematical Journal, 18(2):289–300, Mar 1977.
  * [SSU14] Alexei L. Semenov, Sergey Soprunov, and Vladimir A. Uspensky.  The lattice of definability. Origins, recent developments, and further directions.  In Computer Science - Theory and Applications - 9th International Computer Science Symposium in Russia, CSR 2014, Moscow, Russia, June 7-11, 2014. Proceedings, pages 23–38, 2014.
  * [Wei99] Volker Weispfenning.  Mixed real-integer linear quantifier elimination.  In Proceedings of the 1999 International Symposium on Symbolic and Algebraic Computation, ISSAC ’99, pages 129–136, New York, NY, USA, 1999\. ACM.