# Reachability in Injective Piecewise Affine Maps

Faraz Ghahremani111Sharif University of Technology, Iran.
<EMAIL_ADDRESS>Edon Kelmendi222Queen Mary University of London,
UK<EMAIL_ADDRESS>Joël Ouaknine333Max Planck Insitute for Software
Systems, Saarland University Campus, Germany. Also affiliated with Keble
College, Oxford as emmy.network Fellow, and supported by DFG grant 389792660
as part of TRR 248 (see https://perspicuous-computing.science). joel@mpi-
sws.org.

###### Abstract

One of the most basic, longstanding open problems in the theory of dynamical
systems is whether reachability is decidable for one-dimensional piecewise
affine maps with two intervals. In this paper we prove that for injective
maps, it is decidable.

We also study various related problems, in each case either establishing
decidability, or showing that they are closely connected to Diophantine
properties of certain transcendental numbers, analogous to the positivity
problem for linear recurrence sequences. Lastly, we consider topological
properties of orbits of one-dimensional piecewise affine maps, not necessarily
with two intervals, and negatively answer a question of Bournez, Kurganskyy,
and Potapov, about the set of orbits in expanding maps.

###### Contents

  1. 1 Introduction
    1. 1.1 Contributions
  2. 2 Reachability for Injective Maps
    1. 2.1 Negative Slopes
    2. 2.2 Bijections
    3. 2.3 Maps with Gaps
  3. 3 Related Decision Problems
    1. 3.1 Shrinking Interval Problem
  4. 4 Orbits of Expanding pam

##  1 Introduction

A piecewise affine map (abbreviated pam) is a map from the half-open unit
interval to itself

$\displaystyle f\ :\ [0,1)\to[0,1),$

with the property that there exist half-open intervals $I_{1},\ldots,I_{\ell}$
partitioning $[0,1)$ such that the restriction of $f$ to any of these
intervals $I_{k}$ is affine:

$\displaystyle f\raisebox{-2.15277pt}{$|$}_{I_{k}}(x)\equiv a_{k}x+b_{k},$

where the constants $a_{k},b_{k}$ are rational.

Here is an example of a pam with two intervals:

$\displaystyle f(x)=\begin{cases}\frac{2}{3}x+\frac{2}{3}&\text{ if }0\leq
x<\frac{1}{2},\\\ \frac{4}{3}x-\frac{2}{3}&\text{ if }\frac{1}{2}\leq
x<1.\end{cases}$

The basic decision problem about orbits of these maps is the reachability
problem: Given a pam $f$, an initial point $x_{0}$, and a target point $t$ in
the unit interval, does there exist some natural number $n\in\mathbb{N}$ such
that

$\displaystyle f^{n}(x_{0})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\underbrace{f(f(\cdots f}_{n\text{ times }}(x_{0})\cdots)=t,$

in other words, can we reach $t$ from $x_{0}$ by repeatedly applying $f$? It
is a longstanding open question whether there is a procedure to decide
reachability for piecewise affine maps, even when there are only two intervals
$I_{1},I_{2}$.

Although such maps have long been studied in the dynamical systems community,
to the best of our knowledge the first explicit mention of the reachability
decision problem appeared in the 1994 paper of Koiran, Cosnard, and Garzon
[1]. In that paper the authors prove that _two-dimensional_ piecewise affine
maps (where instead of intervals, a bounded region of the plane is partitioned
into polytopes) have an undecidable reachability problem (Theorem 3.1);
however they leave the one-dimensional problem open.

Why is this simple problem is considered interesting? There are two main
reasons. One, it is arguably the simplest type of dynamical system that can
have immensely complicated behaviour, and two, the reachability problem for
pam is related to numerous problems in mathematics and computer science.

We mention two families of piecewise affine maps that have been studied in
some depth and possess a rich theory with connections to many parts of
mathematics: interval exchange transformations and $\beta$-expansions. The
former are maps that permute the intervals, and are related to Abelian
differentials, continued fraction expansions, polygonal billiards etc., see
[2], and have had recent resurgence in interest due to a number of
breakthroughs. The latter are expansions of numbers in nonintegral bases, and
still shrouded in mystery (except from the metrical point of view), see [3,
Chapter 9], [4, Section 5], [5, Section 7].

From a computer-science perspective, pam are related to recurrent neural
networks and cellular automata [1]. The target discounted-sum problem [5] is
reducible to reachability for one dimensional pam, and so are a plethora of
open problems about discounted automata and games, inclusion in a generalised
Cantor set etc. Furthermore, pam play a central role in the study of hybrid
systems, and the literature is replete with reductions from the reachability
problem for pam to establish hardness or openness of various decision
problems. See e.g. [6, 7].

Finally, another important motivation for studying such maps is the following.
pam reachability is equivalent to the halting problem for a simple family of
programs, namely loops of the following kind:

$x\leftarrow x_{0}$ while $x\neq t$ do if $x<c$ then $x\leftarrow
a_{1}x+b_{1}$ else $x\leftarrow a_{2}x+b_{2}$ end if end while

Algorithms able to decide the halting problem for these simple loops have
potential utility in the wider framework of software verification.

What is known about the reachability problem for piecewise affine maps? Here
are two results directly related to the present paper: First, for purely
affine maps, the correponding reachability question is known as the _orbit
problem_ and has been shown in the 1980s by Kannan and Lipton to be decidable
in all dimensions [8]. Second, as mentioned above, for two-dimensional pam the
reachability problem is undecidable [1, Theorem 3.1], hence the present
restriction to one-dimensional maps. Moreover, several problems related to
reachability have been considered by Koiran and co-authors, see for example
[9, 10, 11].

More recently, Bournez, Kurganskyy, and Potapov [4, 12], using $p$-adic
valuations, proved (among other things) that complete pam with two intervals
have a decidable reachability problem. A pam with two intervals is said to be
complete if the image of each affine component is the unit interval, that is:

$\displaystyle\mathrm{Im}(f\raisebox{-2.15277pt}{$|$}_{I_{1}})=\mathrm{Im}(f\raisebox{-2.15277pt}{$|$}_{I_{2}})=[0,1).$

There have also been various important results on the dynamics of pam from
researchers in the ergodic-theory, number-theory, and dynamical-systems
communities, but none—to the best of our knowledge—enabling us to design
algorithms for the decision problems that concern us.

###  1.1 Contributions

The main contribution of this paper is the following:

######  Theorem 1.1.

The reachability problem is decidable for injective piecewise affine maps with
two intervals.

It is interesting to compare and contrast our result to that of Bournez,
Kurganskyy, and Potapov [4, Corollary 10]: their theorem solves the case of
complete pam, which are the extreme opposite of injective pam that we consider
(for every point $y$ in the image, there are two distinct points that are
mapped to $y$). One might hope that the accumulation of techniques for
handling these two extreme families can lead to a better understanding of the
general problem.

The proof of Theorem 1.1 makes use of two main tools. We begin by a number of
observations that reduce the general problem to reachability in two families
of pam: bijections, and certain injective maps that have positive slopes and
are not surjective. For the former, we utilise a topological conjugacy idea of
Boshernitzan [13] to reduce the reachability problem to one in a much simpler
dynamical system. For the latter, we crucially apply the recent detailed
analysis of orbits of certain pam due to Laurent and Nogueira in [14], which
uses Hecke-Mahler series.

We then present a couple additional results in Section 3; these include
natural extensions, such as poin-to-interval and interval-to-interval
reachability, as well as deciding whether the orbit of a given point
$x_{0}\in[0,1)$ is periodic, i.e. are there distinct positive integers $n,m$
such that

$\displaystyle f^{n}(x_{0})=f^{m}(x_{0})?$

In Section 3 we also prove, perhaps surprisingly, that even for injective maps
with two intervals, there are some natural problems that are rather difficult,
due to their connection with Diophantine approximation. More precisely, we
consider the question of whether there exists some $n\in\mathbb{N}$ such that

$\displaystyle nf^{n}(x_{0})<c,$

where $c\in\mathbb{Q}$ is given as input. A hypothetical procedure to decide
this problem could also be used to compute the Lagrange constants of certain
transcendental numbers. An analogous correspondence holds for the positivity
problem for linear recurrence sequences [15, Section 5], however for a
different set of transcendental numbers.

In the last part of this paper, Section 4, we study topological properties of
orbits. This is inspired by a question of Bournez _et al._ (see Hypothesis 1
in [4] and in [12]). They ask whether all expanding pam (i.e. maps comprising
affine components all of whose slopes are $>1$) have orbits that are either
periodic, or dense in the whole unit interval. We answer this question
negatively by exhibiting a counterexample, and also prove a weaker statement
(which can likely be strengthened): namely that expanding pam have orbits that
are either periodic or have infinitely many accumulation points.

##  2 Reachability for Injective Maps

In this section we prove our main result, Theorem 1.1: the reachability
problem is decidable for injective pam with two intervals. To this end, we
give a couple of definitions and establish some properties of general
piecewise affine maps.

It is sometimes convenient to depict pam pictorially as:

The picture has the following semantics: the two intervals are $[0,1/2)$ and
$[1/2,1)$; the first one is mapped to $[2/3,1)$, and the second one is mapped
to $[0,2/3)$. More precisely we have $f(0)=2/3$, $\lim_{x\to(1/2)^{-}}f(x)=1$,
and for the second interval, $f(1/2)=0$, $\lim_{x\to 1^{-}}f(x)=2/3$. Note
that this information is sufficient to specify the affine functions; the pam
depicted in the picture above is in fact exactly that given as an example in
the introduction.

Denote the half-open unit interval by $U:=[0,1)$. Let $f$ be a pam and
$x_{0}\in U$. We denote the orbit of $x_{0}$ under $f$ by

$\displaystyle\mathcal{O}(f,x_{0})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\left\\{f^{n}(x_{0})\ :\ n\in\mathbb{N}\right\\}.$

There is nothing special about the unit interval $U$ in the definition of
piecewise affine maps. Indeed, when given a pam $f$ mapping some general
interval $[a_{1},a_{2})$ to itself, we can reduce its reachability problem to
that of a pam from $U$ to $U$ (and _vice-versa_). To see this, consider the
bijection $h$ from $[a_{1},a_{2})$ to $U$ defined as:

$\displaystyle h(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{x-a_{1}}{a_{2}-a_{1}},$

and define the function $g\ :\ U\to U$, as

$\displaystyle g\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}h^{-1}\circ f\circ h.$

Clearly $g^{n}=h^{-1}\circ f^{n}\circ h$, so $t\in[a_{1},a_{2})$ is reached
from $x_{0}\in[a_{1},a_{2})$ by applying $f$, if and only if the same is true
for $h(t)$ and $h(x_{0})$ by applying $g$.

Now we identify a few cases of pam where reachability is easy. For this we
need the following definition.

Let $f$ be a pam with intervals $I_{1},\ldots,I_{\ell}$. The interval
reachability graph of $f$ is a directed graph $G_{f}=(V,E)$, where the
vertices are

$\displaystyle V\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\left\\{0,1,\ldots,\ell\right\\},$

and there is an edge from vertex $k$ to vertex $j$ if and only if

$\displaystyle\mathrm{Im}(f\raisebox{-2.15277pt}{$|$}_{I_{k}})\cap
I_{j}\neq\emptyset.$

In other words, we put an edge from $k$ to $j$, if there is a point in
interval $I_{k}$ that can be mapped, via $f$, to a point in the interval
$I_{j}$. When the interval reachability graph is particularly simple, we can
decide reachability:

######  Lemma 2.1.

Let $f$ be a pam and $G_{f}$ its interval reachability graph. Suppose moreover
that $G_{f}$ has at least one of the following properties:

  1. 1.

the only loops in $G_{f}$ are self-loops,

  2. 2.

every vertex in $G_{f}$ has a unique outgoing edge.

Then there exists a procedure to decide reachability for $f$.

###### Proof.

Let $g(x):=ax+b$ be an affine map, where $a,b\in\mathbb{Q}$. Note that if
$a\neq 1$, then by a geometric-series argument, for all $n\in\mathbb{N}$,

$\displaystyle g^{n}(x)=a^{n}x+\frac{a^{n}-1}{a-1}b.$

As a consequence, given $x_{0},t\in\mathbb{R}$ and an interval
$I\subset\mathbb{R}$, we can easily decide the following two questions:

  1. (i)

Does there exist $n\in\mathbb{N}$ such that $g^{n}(x_{0})=t$?

  2. (ii)

Does there exist $n\in\mathbb{N}$ such that $g^{n}(x_{0})\in I$?

Let now $f$ be a pam, $x_{0},t\in U$ the initial and target points
respectively, and $G_{f}$ its interval reachability graph. Suppose that the
only loops in $G_{f}$ are self-loops. This means that once the trajectory of
$x_{0}$ leaves some interval it will never go back to it again. Let
$I_{1},\ldots,I_{\ell}$ be the intervals of $f$, and $f_{1},\ldots,f_{\ell}$
the corresponding affine maps. Suppose that $x_{0}\in I_{k}$, for some $k$.
Using (ii), for the map $f_{k}$, we can decide whether the trajectory of
$x_{0}$ always stays in $I_{k}$ or whether it leaves and reaches another
interval $I_{k^{\prime}}$. If it stays forever in $I_{k}$, we decide
reachability with (i), if it reaches $I_{k^{\prime}}$, then we repeat this
process, and hence identify an interval, say $I_{j}$, that contains the tail
of the trajectory, i.e. all but finitely many members of
$\mathcal{O}(f,x_{0})$ belong to $I_{j}$. Now to decide whether $t$ is
reachable it suffices to check if it appears in the trajectory before $I_{j}$
is reached and if not, to use (i) for the affine map $f_{j}$.

Suppose now that every vertex in $G_{f}$ has a unique outgoing edge. This
implies that there exists a loop of length $p$ in $G_{f}$ of the form:

$\displaystyle k=k_{0}\to k_{1}\to\cdots\to k_{p-1}\to k,$

and that

$\displaystyle f^{p}(I_{k_{i}})\subset I_{k_{i}},$

for all $i\in\left\\{0,1,\ldots,p-1\right\\}$. The function $f^{p}$ is itself
a pam, and since from every interval of $f$ we can go to a unique successor
interval, we have that the intervals of $f^{p}$ coincide with those of $f$. In
particular $I_{k_{0}},I_{k_{1}},\ldots,I_{k_{p-1}}$ are intervals of $f^{p}$;
let $g_{k_{0}},\ldots,g_{k_{p-1}}$ be their corresponding affine maps. To
decide whether $t$ is reachable, first check whether it belongs to one of the
intervals $I_{k_{0}},\ldots,I_{k_{p-1}}$, if it does not, then $t$ is not
reachable, if it does belong to, say, the interval $I_{j}$, then the problem
is reduced to the question of whether $t$ is reachable from $f^{j}(x_{0})\in
I_{j}$, using the affine map $g_{j}$, for which we can use (i). ∎

In the rest of this section, for the proof of Theorem 1.1, we assume that $f$
is an _injective_ pam with two intervals:

$\displaystyle I_{1}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}[0,c),\qquad\qquad
I_{2}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}[c,1),$

for some cutpoint $c\in\mathbb{Q}$, $0<c<1$, and

$\displaystyle f_{1}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}a_{1}x+b_{1},\qquad\qquad
f_{2}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}a_{2}x+b_{2},$

the corresponding affine maps. By injectivity, $f(I_{1})$ is disjoint from
$f(I_{2})$. If $f(I_{1})<f(I_{2})$, then it is not difficult to see that
$G_{f}$ cannot have any loops that are not self-loops. In this case, we can
decide reachability with Lemma 2.1. So then, let us assume that:

$\displaystyle f(I_{2})<f(I_{1}).$ (1)

###  2.1 Negative Slopes

The next step towards the proof of Theorem 1.1 is to treat the case when at
least one of the slopes is negative, i.e. at least one of the $a_{1},a_{2}$,
defined above, is negative. We proceed with the following two lemmas:

######  Lemma 2.2.

Suppose that $a_{2}<0$, and furthermore $c\in f_{2}(I_{2})$. Then we can
decide reachability for $f$.

###### Proof.

If $c$ is in the endpoint of $f_{2}(I_{2})$, i.e. if $f_{2}(c)=c$, then except
for this fixed point, which can be handled separately, the interval
reachability graph of $f$, $G_{f}$, in this case looks like:

$\displaystyle 1\rightleftarrows 2$

and reachability can be decided by applying the second part of Lemma 2.1. So
assume that $c$ is in the interior of $f_{2}(I_{2})$, and set

$\displaystyle c^{\prime}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}f_{2}^{-1}(c).$

We define the following pam:

$\displaystyle g(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}f_{2}(x)&\text{ if }x\in[c,c^{\prime})\\\
f_{1}(f_{2}(x))&\text{ if }x\in[c^{\prime},1).\end{cases}$

Observe that $g$ is a pam from $I_{2}=[c,1)$ to itself. Indeed, since $f_{2}$
has a negative slope, $a_{2}<0$, we have:

$\displaystyle f_{2}([c,c^{\prime}))$ $\displaystyle>c,\text{and}$
$\displaystyle f_{2}([c^{\prime},1))$ $\displaystyle\leq c.$

And since we assumed (1), it follows that

$\displaystyle f_{1}\bigg{(}f_{2}\big{(}[c^{\prime},1)\big{)}\bigg{)}\geq
f_{2}\big{(}[c,c^{\prime}]\big{)}>c,$ (2)

so both components of $g$ are mapping to $I_{2}$.

The idea of this new pam $g$ is that reachability questions of $f$ can be
reduced to those of $g$: Indeed if both $x_{0}$ and $t$ belong to the second
interval $I_{2}$, then by construction of the map $g$, the point $t$ can be
reached from $x_{0}$ by applying $f$ if and only if, it can be reached by
applying $g$. If $x_{0}$ does not belong to $I_{2}$, then by injectivity of
$f$, we can simply consider whether $t$ is reached from $f(x_{0})$ which is
guaranteed to be in $I_{2}$. The same holds when $t\notin I_{2}$.

Finally we show that reachability for the map $g$ is easy to decide. To see
this, observe that (2) implies that $G_{g}$ can have one of the two following
forms:

$\displaystyle\lcirclearrowright 1\to 2\rcirclearrowleft\qquad\qquad
or\qquad\qquad\lcirclearrowright 1\leftarrow 2\rcirclearrowleft,$

in either case the only loops are self-loops, so we can decide reachability by
appealing to Lemma 2.1. ∎

The proof of the next lemma is similar to the one above, except that the
process of identifying the simplified pam $g$ is repeated a (finite) number of
times.

######  Lemma 2.3.

Suppose that $a_{2}<0<a_{1}$, and furthermore $c\in f_{1}(I_{1})$. Then we can
decide reachability for $f$.

###### Proof.

Define the following two quantities:

$\displaystyle c_{1}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}f_{1}^{-1}(c),\qquad\qquad
m_{0}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\min
f_{1}(I_{1}),$

and consider the piecewise affine map $g_{1}$, defined as:

$\displaystyle g_{1}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}g_{1,1}(x):=f_{1}(x)&\text{ if }x\in[0,c_{1}),\\\
g_{1,2}(x):=f_{2}(f_{1}(x))&\text{ if }x\in[c_{1},c).\end{cases}$

Using Assumption (1), we see that $g_{1}$ is a pam from the interval $[0,c)$
to itself, with intervals $J_{1,1}:=[0,c_{1})$ and $J_{1,2}:=[c_{1},c)$. As in
the proof of the preceding lemma, if we can decide reachability for $g_{1}$,
then we can do the same for $f$. To see this, note that if $x_{0},t\in[0,c)$,
then we clearly have:

$\displaystyle\exists n\ f^{n}(x_{0})=t\qquad\Leftrightarrow\qquad\exists m\
g_{1}^{m}(x_{0})=t$

If $t$ does not belong to $[0,c)$ then by injectivity of $f$ we can simply
consider the problem of reaching $f_{2}(t)$, starting from $f_{2}(x_{0})$ or
$x_{0}$, depending on whether $x_{0}\in[0,c)$ or not.

The new pam $g_{1}$ inherits most properties from $f$; indeed, the slope of
$g_{1,1}$ is positive, while that of $g_{1,2}$ is negative, the cutpoint of
$g_{1}$ is $c_{1}$, and crucially

$\displaystyle m_{0}=m_{1}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\min g_{1,1}(J_{1,1}),$

due to $f_{1}$ having a positive slope. The only property it might not inherit
is if $c_{1}$ does not belong to $g_{1,1}(J_{1,1})$. If it does not belong to
$g_{1,2}(J_{1,2})$ either, then the interval reachability graph of $g_{1}$,
$G_{g_{1}}$ has the form:

$\displaystyle 1\rightleftarrows 2$

and reachability in $g_{1}$ (and hence also in $f$) can be decided in this
case due to the second part of Lemma 2.1. If $c_{1}\in g_{1,2}(J_{1,2})$, then
$g_{1}$ satisfies all the conditions of Lemma 2.2, as a consequence of which,
we can again decide reachability in $g_{1}$.

So suppose that $g_{1}$ also inherits the property that the cutpoint $c_{1}$
falls in the image of the first affine map $g_{1,1}$, i.e. $c_{1}\in
g_{1,1}(J_{1,1})$. Now we iterate the process, and define
$c_{2}:=g_{1,1}^{-1}(c_{1})$ and the new pam $g_{2}$ as

$\displaystyle g_{2}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}g_{2,1}(x):=g_{1,1}(x)&\text{ if }x\in[0,c_{2}),\\\
g_{2,2}(x):=g_{1,2}\big{(}g_{1,1}(x)\big{)}&\text{ if
}x\in[c_{2},c_{1}).\end{cases}$

which maps $[0,c_{1})$ to itself. If again $c_{2}\in g_{2,2}(J_{2,2})$, we
define $g_{3}$ and so on. We summarise the relevant properties of the sequence
$f,g_{1},g_{2},\ldots$ of pam. For all $k\in\mathbb{N}$ we have:

$\displaystyle g_{k,1}=g_{k-1,1}=\cdots=g_{1,1}=f_{1},$ (3) $\displaystyle
c_{k}=f_{1}^{-1}(c_{k-1})=f^{-k}(c),$ (4) $\displaystyle
m_{0}=\cdots=m_{k}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny def}}}{=}}\min
g_{k,1}(J_{k,1}).$ (5)

Property (3) is by definition, (4) follows from (3) and the fact that in the
sequence $g_{1},g_{2},\ldots$ of pam we have assumed that the cutpoint belongs
to the image of the first map. Property (5) follows from (3) and the fact that
this minimum is reached at $0$.

We claim that this iterative process halts, i.e. there exists $K\in\mathbb{N}$
such that $c_{K}$ does not belong to the image of the first map $g_{K,1}$,

$\displaystyle c_{K}\notin g_{K,1}(J_{K,1}).$

Indeed as a consequence of (5) we have:

$\displaystyle g_{k,1}(J_{k,1})\geq m_{0}.$ (6)

Since the function $f_{1}$ is monotone increasing in $[0,c)$ and $f_{1}(0)>0$,
$f_{1}(c)>c$, it follows that for any $x\in f_{1}([0,c))$ there is some
$N_{x}\in\mathbb{N}$ such that

$\displaystyle f_{1}^{-N_{x}}(x)<f_{1}(0)=m_{0}.$

Due to (4), this means that there is some $K\in\mathbb{N}$, such that
$c_{K}<m_{0}$, and from (6), $c_{K}$ does not belong to the image of
$g_{K,1}$, i.e. $c_{K}\notin g_{K,1}(J_{K,1})$. The claim is proved.

As before, deciding reachability in $g_{K}$ is easy, since either the interval
reachability graph $G_{g_{K}}$ is of the form that allows us to apply Lemma
2.1, or the conditions of Lemma 2.2 are fulfilled. And if we can decide
reachability in $g_{K}$, then we can do the same in $g_{K-1}$, and so on, for
all the maps in the sequence $f,g_{1},g_{2},\ldots,g_{K}$. In particular this
means that we can decide reachability in $f$. ∎

The two lemmas above, in fact, cover all the cases where at least one of the
slopes is negative. This claim can be proved as follows. Suppose that both
$f_{1}$ and $f_{2}$ have negative slopes. If the cutpoint $c$ is not in the
image of either $f_{1}$ or $f_{2}$ (i.e. $c\notin f_{1}(I_{1})$, and $c\notin
f_{2}(I_{2})$) then in the interval reachability graph every vertex has a
unique outgoing edge, hence we can use Lemma 2.1. If $c$ belongs to the image
of $f_{2}$ then we use Lemma 2.2. If $c$ belongs to the image of $f_{1}$ on
the other hand, we apply the bijection from $[0,1)$ to $(0,1]$, given by the
map $h(x)=1-x$, to define a new pam $f^{\prime}:=h^{-1}\circ f\circ h$, whose
cutpoint belongs to the image of the second map $f^{\prime}_{2}$, and hence
Lemma 2.2 is applicable.

Similarly, if $f_{1}$ has a negative slope, but $f_{2}$ a positive one, we
turn things around with the function $1-x$ and apply the two lemmas above. We
have proved:

######  Proposition 2.4.

The reachability problem is decidable for injective pam with two intervals,
such that at least one of the affine maps has a negative slope.

Having dealt with this case, in the rest of the current section we assume that
both slopes are positive. We split the proof into the two cases, depending on
whether $f$ is surjective or not.

###  2.2 Bijections

In [13], Boshernitzan considers the question of whether there are pam in whose
definition only rational numbers figure, whose orbit is dense in $U$? The
question in answered positively by exhibiting a family of such examples, that
are shown to be topologically similar to rotations of $\mathbb{R}/\mathbb{Z}$
by an angle that is not a rational multiple of $\pi$. In this subsection, by
utilising Boshernitzan’s approach, we demonstrate that it not only helps with
investigating topological properties of orbits, but it also aids us to decide
reachability.

We are given the injective pam $f$ with intervals $I_{1},I_{2}$, such that
$f(I_{2})<f(I_{1})$, i.e. (1), and furthermore, thanks to the previous
subsection, we assume that the slopes of the two affine components
$f_{1},f_{2}$ are both positive. In this subsection, let us further suppose
that $f$ is surjective. Such maps are characterised by exactly two rational
numbers in $(0,1)$; indeed they map some interval $[0,c)$ to some interval
$[d,1)$, and they map $[c,1)$ to $[0,d)$, so they are characterised by the
rationals $c,d\in(0,1)$. They look as follows:

Explicitly, they can be defined as:

$\displaystyle f(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}\frac{1-d}{c}x+d&\text{ if }x\in[0,c),\\\
\frac{d}{1-c}x-\frac{cd}{1-c}&\text{ if }x\in[c,1),\end{cases}$

for any rationals $c,d$ in $(0,1)$.

For any $\tau>0$, denote by $R_{\tau}$ the rotation by $\tau$ in
$\mathbb{R}/\mathbb{Z}$, that is:

$\displaystyle R_{\tau}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}x+\tau\ \mathrm{mod}\ \mathbb{Z},$ (7)

where by the expression on the right-hand side we mean: add $\tau$ to $x$ and
then take the fractional part of the result.

To begin with, consider a pam as defined above, where $c+d=1$. We claim that
$f=R_{d}$. Indeed, replacing $1-d$ by $c$ and $1-c$ by $d$ in the definition
of $f$ we see that the first affine component is $x+d$ while the second one is
$x-c=x+d-1$, therefore $f=R_{d}$. So reachability from $x_{0}$ to $t$, in this
case, is asking whether there exists some $n$ such that

$\displaystyle x_{0}+nd\equiv t\qquad(\mathrm{mod}\ \mathbb{Z}),$

or equivalently whether there are positive integers $n,m$ such that

$\displaystyle x_{0}+nd=t+m,$

which is easily seen to be decidable.

If $c+d>1$, we define a new pam by applying the bijection $h(x)=1-x$, so that
everything is rotated around, and in particular for the corresponding
rationals $c^{\prime},d^{\prime}$ we have $c^{\prime}+d^{\prime}<1$. So assume
that $c+d<1$, and define the quantity:

$\displaystyle\alpha\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{1-c-d}{cd}>0,$ (8)

and the function $h$,

$\displaystyle h(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{\log(\alpha x+1)}{\log(\alpha+1)}.$ (9)

Since $\alpha>0$, $h(x)$ is well-defined for any real $x\geq 0$. We prove that
$h$ is a continuous bijection from $U$ to itself, that has an inverse that is
itself continuous, in other words $h$ is a homeomorphism. Indeed we see that
$h(0)=0$ and $h(1)=1$, and since the derivative

$\displaystyle h^{\prime}(x)=\frac{\alpha}{(\alpha x+1)\log(\alpha+1)}$

is positive in $[0,1]$, due to the fact that $\alpha>0$, we conclude that $h$
is a bijection, and clearly both $h$ and its inverse are continuous. Define
now the angle $\tau$ as:

$\displaystyle\tau\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}h(d)=\frac{\log(\alpha d+1)}{\log(\alpha+1)}.$

We show that $f$ is _topologically similar_ to a rotation by $\tau$, that is:

######  Lemma 2.5.

$f=h^{-1}\circ R_{\tau}\circ h.$

###### Proof.

Define first:

$\displaystyle
R^{\prime}_{\tau}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}x+\tau,\qquad
R^{\prime\prime}_{\tau}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}x+\tau-1,$

and note that

$\displaystyle h^{-1}(x)=\frac{e^{x\log(\alpha+1)}-1}{\alpha}.$

Let $x\in[0,c)$, we show that $h\circ R^{\prime}_{\tau}(x)<1$. We have

$\displaystyle h\circ
R^{\prime}_{\tau}(x)=R^{\prime}_{\tau}(h(x))=h(x)+\tau=h(x)+h(d)=\frac{\log[(\alpha
x+1)(\alpha d+1)]}{\log(\alpha+1)}.$

To prove that the quantity above is strictly smaller than $1$, observe that
$(\alpha x+1)(\alpha d+1)>1$ and $\alpha+1>1$, so since $\log$ is monotone
increasing in $[1,\infty)$ it suffices to show that:

$\displaystyle(\alpha x+1)(\alpha d+1)<\alpha+1.$

One can prove that the inequality above holds by noting that the left-hand
side is strictly smaller than $(\alpha c+1)(\alpha d+1)$, which is equal to
the right hand side. Now since $h\circ R^{\prime}_{\tau}(x)<1$ we see that
$h\circ R_{\tau}=h\circ R^{\prime}_{\tau}$ for $x\in[0,c)$. Finally, a simple
computation shows that for $x\in[0,c)$ we have

$\displaystyle h\circ R_{\tau}\circ h^{-1}(x)=\frac{(\alpha x+1)(\alpha
d+1)-1}{\alpha}=\frac{1-d}{c}x+d,$

which proves that the statement of the lemma holds for $x$ in $[0,c)$. If
$x\in[c,1)$, from the same argument as above we can see that $h\circ
R^{\prime}_{\tau}(x)\geq 1$, so $h\circ R_{\tau}(x)=h\circ
R^{\prime\prime}_{\tau}(x)$. Hence

$\displaystyle h\circ R_{\tau}(x)=\frac{\log(\alpha
x+1)}{\log(\alpha+1)}+\frac{\log(\alpha
d+1)}{\log(\alpha+1)}-1=\frac{\log\left[\frac{(\alpha x+1)(\alpha
d+1)}{\alpha+1}\right]}{\log(\alpha+1)}$

After applying $h^{-1}$ to the quantity above, a simple calculation shows that

$\displaystyle h\circ R_{\tau}\circ h^{-1}(x)=\frac{d}{1-c}x-\frac{cd}{1-c},$

for $x\in[c,1)$. ∎

Now we show how this lemma can be used to decide whether $t\in U$ is reached
from $x_{0}\in U$ by applying $f$. As a consequence of the lemma and $h$ being
a bijection we have that for all $n\in\mathbb{N}$

$\displaystyle f^{n}(x_{0})=h^{-1}\circ R_{\tau}^{n}\circ h(x_{0}),$

whence, the quantity above is equal to $t$ if and only if there exists some
$n\in\mathbb{N}$ such that

$\displaystyle h(t)=R_{\tau}^{n}\big{(}h(x_{0})\big{)}.$

Which is equivalent to the question of whether there exists some
$n\in\mathbb{N}$ such that

$\displaystyle h(t)\equiv h(x_{0})+n\tau\qquad(\mathrm{mod}\ \mathbb{Z}),$

which amounts to asking whether there are positive integers $n,m$ such that

$\displaystyle m+h(t)=h(x_{0})+n\tau.$

The equation above, through a simple calculation, is shown to hold if and only
if one can find positive integers $n,m$ such that

$\displaystyle m=\frac{\log\left[\frac{(\alpha x_{0}+1)(\alpha
d+1)^{n}}{(\alpha t+1)}\right]}{\log(\alpha+1)}.$

Since $\alpha>1$ and $\log$ is injective, the equation above holds if and only
if

$\displaystyle(\alpha+1)^{m}=\frac{\alpha x_{0}+1}{\alpha t+1}(\alpha
d+1)^{n}.$

Every factor in the equation above is a rational number, and consequently we
can decide if there are positive integers $n,m$ such that the equation holds.
This terminates the proof of decidability when $f$ is a bijective pam with two
intervals whose slopes are positive. Now we treat the case in which $f$ is not
surjective.

###  2.3 Maps with Gaps

Suppose that the injective pam $f$ with two intervals and positive slopes is
_not_ surjective, so it maps $[0,c)$ to some $[a_{1},b_{1})$ and $[c,1)$ to
some $[a_{2},b_{2})$. By injectivity and (1), $b_{2}\leq a_{1}$.

Since it is not surjective, at least one of the following strict inequalities
has to hold: $0<a_{2}$ (there is a gap to the left of the first image),
$b_{2}<a_{1}$ (a gap between the two images), $b_{1}<1$ (a gap to the right of
the second image). If there is a gap on the sides, i.e. if at least one of the
inequalities $0<a_{2}$, $b_{1}<1$, hold, we proceed as follows.

If $c$ does not belong to the interval $I:=[a_{2},b_{1})$ then the interval
reachability graph $G_{f}$ is such that every vertex has a single outgoing
edge, and hence we can decide reachability thanks to Lemma 2.1. Suppose that
$c\in I$, and consider $f^{\prime}$ the restriction of $f$ to the set $I$.
Since the slopes are positive, clearly we see that $f^{\prime}$ is a pam from
the interval $I$ to itself. If the target $t$ is not in $I$, then it clearly
cannot be reached. If the starting point $x_{0}$ is not in $I$, then
$f(x_{0})$ is in $I$. So the question of whether $t$ is reachable from $x_{0}$
via $f$, can be reduced to the question of whether $t$ is reachable from
$f(x_{0})$ via the new map $f^{\prime}$. As in the beginning of the present
section, we can scale $I$ to the unit interval $U$ and define another pam
$f^{\prime\prime}$, which will not have any side gaps.

The only remaining case is of a pam that maps $[c,1)$ to some $[0,a)$ and
$[0,c)$ to some $[b,1)$. This family of pam has been studied by Laurent and
Nogueira in the recent paper [14]. There the authors give a rather explicit
description of the dynamics of these maps, which we will exploit to decide
reachability.

Clearly, the pam under consideration are characterised by the three rationals
$a,b$ and $c$. In order to unify the notation with that of [14], we note that
the same family can be characterised by three different rationals, namely the
slope of the first affine component, denoted $\lambda>0$, the translation of
the same denoted $\delta$ and a positive real $\mu>0$ involved in the
definition of the second component. To be more precise, the family of pam that
we consider in this last subsection can be defined by three real numbers
$\lambda,\mu,\delta$ with the following properties:

$\displaystyle 0<\lambda<1,$ $\displaystyle 0<\mu,$ $\displaystyle
1-\lambda<\delta<d_{\lambda,\mu}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}1&\text{ if }\lambda\mu<1,\\\
\frac{\mu-\lambda\mu}{\mu-1}&\text{ if }\lambda\mu\geq 1.\end{cases}$

So that a pam $f_{\lambda,\mu,\delta}$ from $U$ to $U$ is defined as follows,
let $c:=(1-\delta)/\lambda$ and

$\displaystyle
f_{\lambda,\mu,\delta}(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}\lambda x+\delta&\text{ if }x\in[0,c),\\\ \mu(\lambda
x+\delta-1)&\text{ if }x\in[c,1).\end{cases}$

Note that we have not lost any generality by assuming that $\lambda<1$ due to
the following reason. Since $f$ is injective but not surjective, one of the
affine components must be contracting, i.e. it must have slope $<1$. If it is
not the first affine component (as we have assumed here with $\lambda<1$),
then we can permute the components by applying the bijection $h(x)=1-x$ as was
done above.

Briefly, the dynamics look as follows. There is a unique cyclic orbit
$C=\left\\{c_{0},\ldots,c_{k-1}\right\\}$ [14, Theorem 3], so $f$ sends
$c_{i}$ to $c_{i+1\ \mathrm{mod}\ k}$. All other orbits are infinite, but they
have $k$ accumulation points, namely the points in $C$. In other words, all
other orbits approximate the unique cyclic orbit $C$.

Our first step is to decide whether the starting point $x_{0}$ or the target
$t$ belong to $C$. For this we need to effectively determine an upper bound on
the length of the cycle, which can be done by computing the _rotation number_
of $f$. The rotation number $\rho$ of $f$ is rational when the constants
$\lambda,\mu,\delta$ are rational, due to a classical transcendence result
[14, Theorem 3]. Furthermore the rotation number $\rho$ is equal to $\rho=p/q$
for some positive and co-prime integers $p,q$ if and only if

$\displaystyle
F_{1}(\lambda,\mu,\frac{p}{q})\leq\delta<F_{2}(\lambda,\mu,\frac{p}{q}),$

where $F_{1},F_{2}$ are a pair of algebraic functions given explicitly in [14,
Theorem 3]. From these facts, it is plain that we can compute $\rho$. Indeed,
take any enumeration of $\mathbb{Q}$ and for each element decide whether the
inequalities above hold; such a procedure must halt, because we know that
there exists a rational $\rho=p/q$ for which the inequalities above hold. To
speed up this process, we may search among the Farey sequence and use the
following upper bound on $\rho$:

$\displaystyle r_{\lambda,\mu}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\begin{cases}1&\text{ if }\lambda\mu<1,\\\
\frac{\log\frac{1}{\lambda}}{\log\mu}&\text{ if }\lambda\mu\geq 1.\end{cases}$

Let $\rho=p/q$ be the computed rotation number, then part (ii) of [14, Theorem
3] implies that the unique cycle $C$ has length $q$. Compute the rational
numbers:

$\displaystyle f(x_{0}),f^{2}(x_{0}),\ldots,f^{q}(x_{0}).$

If one of the entries in this finite sequence is equal to $x_{0}$, then
$x_{0}$ belongs to $C$. Similarly compute

$\displaystyle f(t),f^{2}(t),\ldots,f^{q}(t),$

and see whether one of the entries is equal to $t$ to ascertain whether $t\in
C$. If both the starting point $x_{0}$ and the target are in $C$, then clearly
the target can be reached. If one of them is in $C$ but the other one is not,
then $t$ cannot by reached from $x_{0}$, due to injectivity of $f$. In the
case when neither $x_{0}$ or $t$ is in $C$, we will effectively compute a
threshold $N\in\mathbb{N}$ after which the target $t$ cannot be reached.

######  Lemma 2.6.

If neither the starting point $x_{0}$ nor the target $t$ belong to the cycle
$C$ then we can effectively determine a threshold $N\in\mathbb{N}$ such that
for all $n>N$ we have

$\displaystyle t\neq f^{n}(x_{0}).$

###### Proof.

Let $\rho=p/q$ be the rotation number computed above. We explain how we can
compute this threshold. To do that, we need to first have a better
understanding of the points that are in the cycle $C$. They are given via the
Hecke-Mahler series; more precisely the cycle $C$ is equal to the set of
points $\Phi(k/q)$, $0\leq k\leq q-1$, where the function $\Phi$ is given by
the series:

$\displaystyle\Phi(x)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\lfloor x\rfloor+\frac{1-\delta}{\lambda}+\sum_{n\geq
0}\lambda^{n}\mu^{\lfloor x\rfloor-\lfloor
x-n\rho\rfloor}\bigg{(}\frac{\lambda+\delta-1}{\lambda}+\lfloor
x-(n+1)\rho\rfloor-\lfloor x-n\rho\rfloor\bigg{)}.$

This function converges when $\lambda\mu^{\rho}<1$, which holds for our case.
Immediately, we see that given any $\epsilon>0$ and any positive rational
number $r\in\mathbb{Q}$, $r>0$, we can compute an interval $I$ of length
$\epsilon$ such that $\Phi(r)\in I$. In other words, we can approximate
$\Phi(r)$ to arbitrary additive precision. Compute an $\epsilon>0$ (by e.g.
trying $2^{-n}$ for larger and larger $n$) with the following properties. For
$\epsilon$ and $\Phi(k/q)$, $0\leq k\leq q-1$, using the approximation above
compute the interval $J_{k}$ of length $\epsilon$, such that the distance from
the target $t$ and any interval $J_{k}$, $0\leq k\leq q-1$, is at least
$2\epsilon$. Such an $\epsilon$ exists due to the fact that $t$ is not equal
to any $\Phi(k/q)$ since it does not belong to the cycle $C$. Note that by
construction of $\epsilon$, if we take _any_ other intervals $J^{\prime}_{k}$
of length $\epsilon$ containing $\Phi(k/q)$, $0\leq k\leq q-1$, $t$ will be
outside all of them.

Now the following two facts will conclude the proof of the lemma:

$\displaystyle f^{n}(U)\text{ has measure smaller than
}(\lambda^{q}\mu^{p})^{\lfloor n/q\rfloor},\text{ and }$ (10) $\displaystyle
f^{n}(U)=\biguplus_{k=0}^{q-1}H_{k},$ (11)

where $H_{k}$ is an interval containing $\Phi(k/q)$, and the measure is the
Lebesgue measure.

The statement (10) is from Proposition 6 in [14], while statement (11) is in
the succeeding corollary. Choose an $N\in\mathbb{N}$ such that

$\displaystyle(\lambda^{q}\mu^{p})^{\lfloor N/q\rfloor}<\epsilon.$

From (11) we see that for all $n>N$, $f^{n}(U)$ is made out of $q$ disjoint
intervals $H_{k}$, each one of length smaller than $\epsilon$, consequently by
construction of $\epsilon$, we have

$\displaystyle t\notin f^{n}(U).$

∎

Thus we have concluded the proof of the main theorem, Theorem 1.1.

##  3 Related Decision Problems

A more careful examination of the proof of Theorem 1.1 shows that the same can
be used to demonstrate decidability of certain variants of the reachability
problem. For example, the point-to-interval reachability: given an interval
$I\subset U$ and $x_{0}$ decide whether there exists some $n\in\mathbb{N}$
such that $f^{n}(x_{0})\in I$. First, we observe that for general pam this
problem is no harder than the point-to-point reachability considered in the
prequel.

######  Proposition 3.1.

Point-to-interval reachability problem can be effectively reduced to the
point-to-point reachability problem.

###### Proof.

Let $f$ be a pam and $I_{1},\ldots,I_{\ell}$ its intervals. Let $x_{0}$ be the
initial point and $I$ the given target interval. We effectively construct
another pam $f^{\prime}$ as follows. The intervals $I_{j}$ of $f$ that do not
intersect the target interval $I$ are also intervals of $f^{\prime}$ with the
same associated affine map. For all intervals $I_{j}$ that intersect $I$ but
are not contained in it, $f^{\prime}$ has the interval $I_{j}\setminus I$ with
the affine map corresponding to $I_{j}$. For $I$ the associated affine map is
the constant map $g(x)=t$ for some rational $t>1$.

It follows that the orbit of $x_{0}$ under $f$ intersects the target interval
$I$ if and only if the point $t$ belongs to the orbit of $x_{0}$ under
$f^{\prime}$. We can now scale the pam $f^{\prime}$ to make it a map from the
unit interval to itself. ∎

We cannot directly use Proposition 3.1 to prove that point-to-interval
reachability in injective pam with two intervals is decidable, because in the
reduction the number of intervals is increasing. However we can show that a
procedure exists by applying the analysis that was done in the preceding
section. Here is a sketch of the proof.

######  Theorem 3.2.

Point-to-interval reachability problem is decidable for injective pam with two
intervals.

###### Proof Sketch.

Let $f$ be the given pam, $x_{0}\in U$ the initial point, and $I$ the target
interval. When the interval reachability graph of $f$ is particularly simple,
as we saw in Lemma 2.1, the reachability problem reduces to that of a single
affine map. Deciding whether it is possible to reach an interval, in this
case, is trivial. The case of negative slopes in Section 2.1 was essentially
reduced to that of pam covered in Lemma 2.1.

It remains to consider pam that are bijections (of Section 2.2) and those that
have a gap in the middle (of Section 2.3). For the former, we proved that such
pam are topologically conjugate to rotations in the circle by a quantity:

$\displaystyle\tau=\frac{\log(q_{1})}{\log(q_{2})},$

where $q_{1},q_{2}$ are rational numbers depending on $f$. It is a basic
theorem that

$\displaystyle\left\\{n\tau\ \mathrm{mod}\ \mathbb{Z}\ :\
n\in\mathbb{N}\right\\}$

is dense in $U$ if and only if $\tau$ is irrational. If $\tau$ is rational, on
the other hand, the set above is finite. Hence, if $\tau\notin\mathbb{Q}$ then
every orbit of $f$ is dense in $U$, therefore every interval is reached from
every point. If $\tau\in\mathbb{Q}$ however, then every orbit of $f$ is
periodic, so we would only need to compute finitely many iterations of $f$ and
check whether any of them send $x_{0}$ to $I$. Finally to decide whether
$\tau$ is rational we proceed as follows. We observe that $\tau\in\mathbb{Q}$
if and only if there are integers $a,b$ such that

$\displaystyle q_{1}^{a}=q_{2}^{b},$

which one can decide easily by looking at the prime factorisation of
$q_{1},q_{2}$.

In maps that have gaps in the middle, from [14], we know that there is a
single periodic orbit with points $c_{0},\ldots,c_{k-1}$ whose length $k$ we
can compute. First we check whether the initial point $x_{0}$ belongs to this
unique periodic orbit, by simply computing the first $k$ entries of the orbit.
If it does, then clearly $I$ is reached if and only if one of the first $k$
entries belongs to $I$. Similarly, then check whether one of the endpoints of
$I$ belongs to the unique periodic orbit. If not, one can proceed as in Lemma
2.6, by approximating $c_{i}$ to either find one that sits inside the interior
of $I$, or to compute some threshold $N\in\mathbb{N}$, after which we know
that $f^{n}(x_{0})$ is not in the target $I$.

The remaining case is when one of the endpoints of $I$ (call it $c$) belongs
to the periodic orbit, but none of the $c_{i}$ are in the interior of $I$. It
follows from (10) and (11) that $f^{nk}(x_{0})$, $n\in\mathbb{N}$ is a Cauchy
sequence tending to $c$, and that $c$ is a fixed point of the pam
$f^{\prime}:=f^{k}$. If $c$ belongs to the interior of one of the intervals
defining $f^{\prime}$, then the problem reduces to a question about a single
affine map, and is easily dealt with. If $c$ is the point between the adjacent
intervals $J_{1},J_{2}$ in the definition of $f^{\prime}$, by looking at the
corresponding affine maps, one can decide whether both $J_{1}$ and $J_{1}$ are
visited infinitely often or the orbit stays in only one of them, and decide
accordingly. ∎

Since in the two more complicated families of pam the initial point does not
play a big role, meaning that most orbits look the same, bar a few small
modifications, one can use the proof above to also show that interval-to-
interval reachability is decidable for injective pam with two intervals. That
is the decision question where one is given a pam $f$ with two intervals that
is injective, a starting interval $J_{0}$ and a target interval $J_{1}$ and is
asked to decide whether there exists some $x_{0}\in J_{0}$ and natural
$n\in\mathbb{N}$ such that $f^{n}(x_{0})$ is in $J_{1}$.

Another interesting problem whose decidability comes as a corollary from
Section 2, is to decide whether the orbit is periodic. More precisely, given a
pam $f$ and $x_{0}\in U$ decide whether there exists two distinct naturals
$n,m\in\mathbb{N}$ such that $f^{n}(x_{0})=f^{m}(x_{0})$.

######  Theorem 3.3.

The periodic orbit problem is decidable for injective pam with two intervals.

###### Proof Sketch.

In cases that were covered by Lemma 2.1 the orbit can be periodic only if the
fixed point of one of the affine maps $g(x)=ax+b$ is reached (when every
vertex of $G_{f}$ has a unique outgoing edge, a slight variation of this idea
applies). That fixed point, if it exists, is equal to $b/(1-a)$. So the
problem reduces to deciding whether there exists some $n\in\mathbb{N}$ such
that

$\displaystyle
g^{n}(x_{0}^{\prime})=a^{n}x_{0}^{\prime}+\frac{a^{n}-1}{a-1}b=\frac{b}{1-a},$

where $x_{0}^{\prime}$ can be effectively computed.

When $f$ is a bijection, in the proof of Theorem 3.2 we saw that the orbit is
finite if and only if the quantity $\tau$ is rational, and that this can be
decided. When $f$ has a gap in the middle of the two images, we saw in Section
2.3 that there is a unique periodic orbit, whose length we can compute. ∎

We conclude this section with a surprising result; we show that a problem
related to reachability is expected to be rather difficult to decide, even for
injective pam with two intervals. This is the problem of deciding whether
there exists some $n\in\mathbb{N}$ such that $nf^{n}(x_{0})<c$ for some given
$c\in U$. So it is asking whether the orbit ever goes inside an interval that
is shrinking with time, i.e. the interval $[0,c/n)$. Let us call it the
shrinking interval problem. The reason we believe this problem should be
difficult to decide is because such a procedure would expose a lot of
information about the Diophantine approximation properties of certain
transcendental numbers, and would consequently answer a number of open
problems.

###  3.1 Shrinking Interval Problem

Understanding how well an irrational number $\mu$ can be approximated by
rationals is important for the solving Diophantine equations, and other
central problems in number theory. That is the question of how small can the
quantity

$\displaystyle\left|\mu-\frac{p}{q}\right|$

be as a function of $q$, when $p,q$ range over integers. As a consequence of
the classical theory of continued fractions (see [16, Chapter II, Section 8]),
it is known that for every real number $\mu$, there are integers
$p,q\in\mathbb{Z}$ such that

$\displaystyle\left|\mu-\frac{p}{q}\right|\leq\frac{1}{q^{2}}.$

With what smaller constant can we replace $1$ and have the inequality above
hold? In other words what can we say about:

$\displaystyle L(\mu)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\inf\left\\{c\in\mathbb{R}\ :\
\left|\mu-\frac{p}{q}\right|\leq\frac{c}{q^{2}},\text{ for some
}p,q\in\mathbb{Z}\right\\}.$

This number is sometimes called the Lagrange constant of $\mu$, and it
measures in a sense how well can the number $\mu$ be approximated by
rationals; numbers that have $L(\mu)>0$ are called badly approximable. We
still do not know almost anything about the Lagrange constants of specific
numbers; most results we have are of metric nature (e.g. almost all real
numbers have Lagrange constant $0$), [16, Chapter III].

In this subsection we will show that a procedure for the shrinking interval
problem, could be used to approximate $L(\mu)$, not for all reals $\mu$, but
for a family of reals; namely those that belong to the following set:

$\displaystyle S\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\left\\{\frac{1}{1+\frac{\log{\frac{1-c}{d}}}{\log\frac{1-d}{c}}}\
:\ c,d\in\mathbb{Q}\cap(0,1),c+d<1\right\\}.$

The positivity problem for linear recurrence sequences (i.e. is there a
positive term in the given sequence) has the same property [15, Section 5],
namely that a procedure to decide the positivity problem could be used to
approximate $L(\mu)$, however, for a $\mu$ in a different set (the arguments
of algebraic numbers in the unit interval).

We find it surprising that the same phenomenon occurs even for one-
dimensional, injective pam with two intervals; one would expect that every
natural problem is decidable for these systems.

######  Theorem 3.4.

If the shrinking interval problem is decidable for injective pam with two
intervals, then there exists a procedure that inputs $\mu\in S$, $\epsilon>0$
and computes an interval $I\subset[0,1]$ of length $\epsilon$ such that
$L(\mu)\in I$.

###### Proof.

We define the pam whose shrinking interval problem exposes information about
$L(\mu)$. To that end, let $c,d$ be two rationals in $(0,1)$, such that
$c+d<1$ and $\mu\in S$ the corresponding real number (see the definition of
$S$ above). Let $f$ be the bijective pam with two intervals defined by the
rationals $c$ and $d$ as in Section 2.2. In that section we saw that $f$ is
topologically similar to a rotation by an angle $\tau$, which in our case a
short calculation shows that $\mu=\tau$. Therefore, due to Lemma 2.5, we have

$\displaystyle f=h\circ R_{\mu}\circ h^{-1},$

where $R_{\mu}$ and $h$ are defined in (7) and (9) respectively. From this
equivalent definition of $f$, for any real $\gamma\in(0,1)$ and
$n\in\mathbb{N}$, we have

$\displaystyle nf^{n}(0)<\gamma\qquad\Leftrightarrow\qquad n\mu\ \mathrm{mod}\
\mathbb{Z}<h(\gamma/n),$

because $h$ is a monotone increasing homeomorphism. That statement holds if
and only if there is a positive integer $m\in\mathbb{N}$ such that

$\displaystyle\left|\mu-\frac{m}{n}\right|<h\left(\frac{\gamma}{n}\right)\frac{1}{n}.$
(12)

Denote by $\mathbb{A}$ the hypothetical algorithm for deciding the shrinking
interval problem. If $\mathbb{A}(f,\gamma)$ returns _yes_ , then there exists
natural numbers $n,m$ such that (12) holds. If $\mathbb{A}(f,\gamma)$ returns
_no_ on the other hand, that implies that for all naturals $n,m$ we have

$\displaystyle\left|\mu-\frac{m}{n}\right|\geq
h\left(\frac{\gamma}{n}\right)\frac{1}{n}.$ (13)

Observe that if $\mathbb{A}(f,\gamma)=\text{\emph{yes}}$ then for any larger
$\gamma^{\prime}$, again we have
$\mathbb{A}(f,\gamma^{\prime})=\text{\emph{yes}}$; and symmetrically if
$\mathbb{A}(f,\gamma)=\text{\emph{no}}$ then for any smaller $\gamma^{\prime}$
we have $\mathbb{A}(f,\gamma^{\prime})=\text{\emph{no}}$. It plainly follows
that for all $\delta>0$ we can compute an interval $J\subset U$ of length at
most $\delta$, such that if $\mathbb{A}(f,\cdot)$ changes answer from _yes_ to
_no_ , it does so for some real $\gamma$ in the interval $J$. This computation
is performed by making multiple calls to $\mathbb{A}(f,\gamma)$ for different
$\gamma$.

Furthermore, unfolding the definition of the homeomorphism $h$, using the
Maclaurin series for $\log(x+1)$, and performing a simple calculation we see
that

$\displaystyle\frac{\alpha\gamma}{2n^{2}}\leq
h\left(\frac{\gamma}{n}\right)\frac{1}{n}\leq\frac{2\alpha\gamma}{n^{2}},$

where $\alpha$ is defined as in (8), hence e.g., if
$\mathbb{A}(f,\gamma)=\text{\emph{yes}}$ then we have an upper bound for the
Lagrange constant, namely $L(\mu)\leq 2\alpha\gamma$. More generally, one can
show that for any $\epsilon^{\prime}>0$, and all $n$ sufficiently large we
have

$\displaystyle(1-\epsilon^{\prime})\frac{\alpha\gamma}{n^{2}}\leq
h\left(\frac{\gamma}{n}\right)\frac{1}{n}\leq(1+\epsilon^{\prime})\frac{\alpha\gamma}{n^{2}}.$

Since both $\delta$ and $\epsilon^{\prime}$ can be taken to be arbitrarily
small, the theorem follows. ∎

##  4 Orbits of Expanding pam

In [4, Hypothesis 1], [12, Hypothesis 1], the authors conjecture that
expanding pam (i.e. those whose affine maps all have slope $>1$) have the
property that for all $x_{0}\in U$,

$\displaystyle\mathcal{O}(f,x_{0})\text{ is finite, or is dense in }U.$ (14)

For a subclass of expanding pam, namely for $\beta$-expansions, Adamczewski
and Bugeaud make the same conjecture [17, Hypothesis 2]. Even for this
subclass proving this conjecture is considered out of reach, and no recent
progress has been made [18].

However, as we will now show, the property in (14) does not hold for general
expanding pam.444The property probably holds for $\beta$-expansions, as
conjectured by Adamczewski and Bugeaud, as well as for some other classes of
pam, e.g. complete maps; however it is too strong for general expanding pam.

######  Example 4.1.

Define the pam $f$ as:

$\displaystyle f(x)=\begin{cases}\frac{4}{3}x&\text{ if }0\leq
x<\frac{1}{2},\\\ \frac{4}{3}x-\frac{1}{3}&\text{ if }\frac{1}{2}\leq
x<1.\end{cases}$

This is an expanding map as both slopes are $4/3>1$. Consider the orbit
$\mathcal{O}(f,1/5)$. It is clear that it cannot be dense in all of $U$,
because the first affine map, $4/3x$, is monotone increasing, and the infimum
of the image of the second affine map is:

$\displaystyle\frac{4}{3}\cdot\frac{1}{2}-\frac{1}{3}=\frac{1}{3}.$

Therefore the orbit $\mathcal{O}(f,1/5)$ cannot be dense in $U$, because e.g.
the interval $[0,1/5)$ does not intersect it. So it suffices to show that the
orbit is infinite, in order to falsify claim (14). We will show this by
observing that $f$ decreases the $3$-adic valuation by at least one.

Let $p$ be a prime number, and recall that the $p$-adic valuation of an
integer $a$, denoted $v_{p}(a)$, is defined to be the largest positive integer
$n$ such that

$\displaystyle a=p^{n}a^{\prime},$

for some $a^{\prime}\in\mathbb{Z}$. Then one extends this function to the
rationals by defining $v_{p}(p/q)$ as $v_{p}(p)-v_{p}(q)$. We claim that for
all $n\in\mathbb{N}$

$\displaystyle
v_{3}\left(f^{n}\left(\frac{1}{5}\right)\right)>v_{3}\left(f^{n+1}\left(\frac{1}{5}\right)\right).$

This claim plainly implies that the orbit $\mathcal{O}(f,1/5)$ is infinite.

To prove the claim, observe that when the first affine map, $4/3\ x$, is
applied, the $3$-adic valuation $v_{3}$ always decreases by $1$. As for the
second affine map, let $p/q\in\mathbb{Q}$ be such that $q\equiv 0\
(\mathrm{mod}\ 3)$ and $p\not\equiv 0\ (\mathrm{mod}\ 3)$. Then when the
second affine map is applied we have:

$\displaystyle\frac{4}{3}\cdot\frac{p}{q}-\frac{1}{3}=\frac{4p-q}{3q}.$

Since $4p-q\not\equiv 0\ (\mathrm{mod}\ 3)$, we see that when the second
affine map is applied to an irreducible rational whose denominator is
divisible by $3$, then the $3$-adic valuation, $v_{3}$, decreases by $1$.
Finally, since every rational in the orbit, with the exception of $1/5$, has
this property, the claim follows. ∎

To complete this section, we prove a weaker property of expanding pam, but
along the lines of (14). Let $X$ be a subset of $\mathbb{R}$. We say that $p$
is an accumulation point of $X$ if every open neighbourhood of $p$ also
contains some $p^{\prime}\in X$, $p\neq p^{\prime}$.

######  Theorem 4.2.

Let $f$ be an expanding pam. For all $x_{0}\in U$, we have that either
$\mathcal{O}(f,x_{0})$ is finite, or it has infinitely many accumulation
points.

###### Proof.

Let $x_{0}\in U$ be such that $\mathcal{O}(f,x_{0})$ is infinite, and towards
a contradiction, assume that it has finitely many accumulation points:
$p_{1},\ldots,p_{k}$. Define the set $A$ as follows.555We are doing this
refinement in order to take care of the cases when one of $p_{1},\ldots,p_{k}$
is also an endpoint of an interval in the definition of $f$. Put the symbol
$p_{i}^{-}$ in $A$, $1\leq i\leq k$, if and only if for every $\epsilon>0$ the
orbit $\mathcal{O}(f,x_{0})$ intersects the interval $(\epsilon,p_{i})$.
Similarly, put $p_{i}^{+}$ in the set $A$ if and only if for all $\epsilon>0$,
the orbit intersects $(p_{i},\epsilon)$.

Now, for all $i\in\left\\{1,\ldots,k\right\\}$ and $s\in\left\\{-,+\right\\}$,
such that $p_{i}^{s}\in A$, it is clear that there exists some $p_{j}^{t}\in
A$ such that

$\displaystyle\lim_{x\to p_{i}^{s}}f(x)=p_{j}^{t},$

since $p_{1},\ldots,p_{k}$ are the only accumulation points of the orbit and
$f$ is a pam. Hence there is a graph structure with vertices $A$, and in fact
this graph is a cycle. Consequently, there exists some $\ell\in\mathbb{N}$ and
$s\in\left\\{-,+\right\\}$ such that

$\displaystyle\lim_{x\to p_{1}^{s}}f^{\ell}(x)=p_{1}^{s}.$ (15)

We argue that this is impossible. Indeed, it follows from (15) that all but
finitely many elements of $\mathcal{O}(f^{\ell},x_{0})$ belong to a single
interval in the definition of the pam $f^{\ell}$. Therefore, after some
threshold, the same affine map $g(x):=ax+b$ is being applied. But applying
this affine map $n$ times is the same as applying

$\displaystyle g^{n}(x)=a^{n}x+\frac{a^{n}-1}{a-1}b,$

as we saw in the proof of Lemma 2.1. The orbit under $g$ cannot be Cauchy when
$a>1$, yet in our case the latter holds, since $f$ is expanding and therefore
so is $f^{\ell}$. ∎

## References

  * [1] P. Koiran, M. Cosnard, and M. Garzon, “Computability with low-dimensional dynamical systems,” _Theoretical Computer Science_ , vol. 132, no. 1-2, pp. 113–128, 1994. [Online]. Available: https://doi.org/10.1016/0304-3975(94)90229-1
  * [2] M. Viana, “Ergodic theory of interval exchange maps,” _Revista Matemática Complutense_ , vol. 19, no. 1, 2006. [Online]. Available: https://doi.org/10.5209/rev_rema.2006.v19.n1.16621
  * [3] Y. Bugeaud, “Distribution modulo one and diophantine approximation,” 2012. [Online]. Available: http://dx.doi.org/10.1017/cbo9781139017732
  * [4] O. Bournez, O. Kurganskyy, and I. Potapov, “Reachability problems for one-dimensional piecewise affine maps,” _International Journal of Foundations of Computer Science_ , vol. 29, no. 04, pp. 529–549, 2018. [Online]. Available: https://doi.org/10.1142/s0129054118410046
  * [5] U. Boker, T. A. Henzinger, and J. Otop, “The target discounted-sum problem,” in _2015 30th Annual ACM/IEEE Symposium on Logic in Computer Science_ , 7 2015\. [Online]. Available: https://doi.org/10.1109/lics.2015.74
  * [6] E. Asarin and G. Schneider, _Widening the Boundary between Decidable and Undecidable Hybrid Systems*_ , ser. CONCUR 2002 - Concurrency Theory. Springer Berlin Heidelberg, 2002, pp. 193–208. [Online]. Available: https://doi.org/10.1007/3-540-45694-5_14
  * [7] E. Asarin, V. P. Mysore, A. Pnueli, and G. Schneider, “Low dimensional hybrid systems–decidable, undecidable, don’t know,” _Information and Computation_ , vol. 211, pp. 138–159, 2012.
  * [8] R. Kannan and R. J. Lipton, “Polynomial-time algorithm for the orbit problem,” _Journal of the ACM_ , vol. 33, no. 4, pp. 808–821, 1986. [Online]. Available: https://doi.org/10.1145/6490.6496
  * [9] P. Koiran, “The topological entropy of iterated piecewise affine maps is uncomputable,” _Discrete Mathematics & Theoretical Computer Science_, vol. 4, 2001.
  * [10] V. D. Blondel, O. Bournez, P. Koiran, and J. N. Tsitsiklis, “The stability of saturated linear dynamical systems is undecidable,” _Journal of Computer and System Sciences_ , vol. 62, no. 3, pp. 442–462, 2001.
  * [11] V. D. Blondel, O. Bournez, P. Koiran, C. H. Papadimitriou, and J. N. Tsitsiklis, “Deciding stability and mortality of piecewise affine dynamical systems,” _Theoretical computer science_ , vol. 255, no. 1-2, pp. 687–696, 2001.
  * [12] O. Kurganskyy and I. Potapov, “Reachability problems for pams,” in _International Conference on Current Trends in Theory and Practice of Informatics_. Springer, 2016, pp. 356–368.
  * [13] M. D. Boshernitzan, “Dense orbits of rationals,” _Proceedings of the American Mathematical Society_ , vol. 117, no. 4, pp. 1201–1201, 1993. [Online]. Available: https://doi.org/10.1090/s0002-9939-1993-1134622-6
  * [14] M. Laurent and A. Nogueira, “Dynamics of 2-interval piecewise affine maps and Hecke-Mahler series,” _CoRR_ , 2019. [Online]. Available: http://arxiv.org/abs/1907.08655v1
  * [15] J. Ouaknine and J. Worrell, “Positivity problems for low-order linear recurrence sequences,” in _Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms_ , 12 2014. [Online]. Available: https://doi.org/10.1137/1.9781611973402.27
  * [16] A. Y. Khinchin, “Continued fractions,” _The Mathematical Gazette_ , vol. 21, no. 245, p. 308, 1937. [Online]. Available: https://doi.org/10.2307/3607737
  * [17] B. Adamczewski and Y. Bugeaud, “Dynamics for $\beta$-shifts and diophantine approximation,” _Ergodic Theory and Dynamical Systems_ , vol. 27, no. 6, pp. 1695–1711, 2007. [Online]. Available: https://doi.org/10.1017/s0143385707000223
  * [18] B. Adamczewski, personal communication.


# On compact subsets of the reals

Wojciech Bielas  Institute of Mathematics, University of Silesia in Katowice,
Bankowa 14, 40-007 Katowice<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>,  Mateusz Kula  and  Szymon Plewik

###### Abstract.

Motivated by results of J. R. Kline and R. L. Moore (1919) that a compact
subset of the plane, homeomorphic to a subset of the reals, lies on the arc,
we give a purely topological characterisation of compact sets of the reals.
This allows us to reduce investigations of Cantorvals to properties of
countable linear orders and to show, applying the Mazurkiewicz–Sierpiński
Theorem (1920), that there exist continuum many non-homeomorphic
$L$-Cantorvals.

###### Key words and phrases:

Cantorval, $L$-Cantorval, gaps, intervals

###### 2010 Mathematics Subject Classification:

Primary: 54F65; Secondary: 26A03, 54F05

##  1\. Introduction

If $X$ is a compact subset of the reals, then

$(\star)$. Each non-trivial component of $X$ is an arc $[a,b]$ and the set
$(a,b)=[a,b]\setminus\\{a,b\\}$ is open.

J. R. Kline and R. L. Moore [10, Theorem 1] showed that a compact subset of
the plane $\mathbb{R}^{2}$ that satisfies condition $(\star)$, lies on an arc.
We are impressed by this achievement, more than 100 years old, and we have
decided to continue this. While Kline and Moore dealt only with compact
subsets of the plane, their results had been generalised, for example [16] and
[17]. Here, we present a variation that gives an internal characterisation of
compact subsets of the reals. Also, we have found some applications to
Cantorvals. As far as we know, the name Cantorval has been introduced by P.
Mendes and F. Oliveira [6]. The first characterization of Cantorvals was given
by J. A. Guthrie and J. E. Nymann [4]. As it is noted by S. Głąb and J.
Marchwicki [3], a few authors pointed out the existence of some concrete
Cantorvals before Guthrie and Nymann.

By an _arc_ we understand a closed interval $[a,b]\subseteq\mathbb{R}$, or a
homeomorphic image of a closed interval $[a,b]$, which also will be denoted by
$[a,b]$. In both cases, points $a$ and $b$ are called _endpoints_ of the arc
$[a,b]$. Metric notions, which are described in [2, pp. 248–254], we
supplement with

$B^{*}(Y,\varepsilon)=\operatorname{int}_{X}Y\cup
B(Y\setminus\operatorname{int}_{X}Y,\varepsilon),$

where $B(Y\setminus\operatorname{int}_{X}Y,\varepsilon)$ is the
$\varepsilon$-ball around the set $Y\setminus\operatorname{int}_{X}Y$. If $Y$
is a compact subset of the reals $\mathbb{R}$, then any component of
$\mathbb{R}\setminus Y$ is called a $Y$-gap and any non-trivial component of
$Y$ is called a $Y$-interval. When the set $Y$ is fixed, we say gap and
interval instead of $Y$-gap and $Y$-interval, respectively. Let us recall the
following well-known facts.

######  Fact 1.

If $X$ is a compact Hausdorff space, then any component $S\subseteq X$ is the
intersection of the family of all clopen sets containing $S$.

###### Proof.

In compact Hausdorff spaces, components coincide with quasi-components, see
[2, Theorem 6.1.23]. ∎

######  Fact 2.

Let $X$ be a compact Hausdorff space. If a component $S$ is contained in an
open set $U$, then there exists a clopen set $V$ such that $S\subseteq
V\subseteq U$.

###### Proof.

In view of Fact 1, choose a family $\mathcal{V}$ of clopen sets such that
$S=\bigcap\mathcal{V}$. Choose a finite subfamily
$\mathcal{V}^{*}\subseteq\mathcal{V}$ such that
$X\setminus\bigcap\mathcal{V}^{*}\supseteq X\setminus U$. Therefore
$\bigcap\mathcal{V}^{*}\subseteq U$. ∎

Our notation is standard, in particular, a closed and open set is called
_clopen_. For notions not defined here, see [2] and [13].

##  2\. The Kline–Moore theorem revisited

If a compact metric space $X$ satisfies condition $(\star)$, then there are at
most countably many non-trivial components. Indeed, each non-trivial component
of $X$ has non-empty interior, different components are disjoint and $X$ is
separable.

Let $\mathcal{B}_{n}$ be the family of all clopen sets $V\subseteq X$ for
which there exists a component $S$ of $X$ such that

$\textstyle S\subseteq V\subseteq B^{*}(S,\frac{1}{n}).$

Clearly, families $\mathcal{B}_{n}$ are defined for any metric space $X$ and
$\mathcal{B}_{n+1}\subseteq\mathcal{B}_{n}$. We say that a family
$\mathcal{B}$ of clopen sets of $X$ is a base for components, whenever any
component of $X$ can be obtained as the intersection of a family contained in
$\mathcal{B}$. If $X$ is a compact metric space, then the family
$\mathcal{B}_{n}$ is a base for components, for each $n>0$. Indeed, if $S$ is
a component of $X$, then $S=\bigcap\mathcal{V}$, where $\mathcal{V}$ is a
family of clopen sets. For each $V\in\mathcal{V}$, by Fact 2, there exists a
clopen set $U_{V}$ such that

$\textstyle S\subseteq U_{V}\subseteq V\cap B^{*}(S,\frac{1}{n}).$

Therefore $S=\bigcap\\{U_{V}\colon V\in\mathcal{V}\\}$ and all $U_{V}$ belong
to $\mathcal{B}_{n}$.

Let $X$ be a metric space and $V\subseteq X$ be compact and clopen. Each of
the following facts is more or less obvious.

  * •

If $V$ is the sum of finitely many components, then each such component is
open and belongs to $\mathcal{B}_{n}$.

  * •

If $V$ contains infinitely many components and the diameter $\delta(V)$ is
less than $\frac{1}{n}$, then $V\in\mathcal{B}_{n}$. Indeed, by compactness of
$V$ one of the components contained in $V$ is not open, so there is a
component $S\subseteq V$ and a point $x\in S\setminus\operatorname{int}_{X}S$,
and

$\textstyle S\subseteq V\subseteq B(x,\frac{1}{n})\subseteq
B^{*}(S,\frac{1}{n}).$

  * •

If $S$ is a component of $X$ such that $S\subseteq V\subseteq
B^{*}(S,\frac{1}{n})$ and $W\subseteq X\setminus S$ is a clopen set, then
$S\subseteq V\setminus W\in\mathcal{B}_{n}$.

######  Proposition 3.

Let $(X,d)$ be a compact metric space. If each $\mathcal{P}_{n}$ is a cover
consisting of clopen sets and each $\mathcal{P}_{n}$ is a refinement of
$\mathcal{B}_{n}$, then $\bigcup\\{\mathcal{P}_{n}:n>0\\}$ is a base for
components.

###### Proof.

Let $S\subseteq X$ be a component and, for each $n>0$, take the clopen set
$V_{n}$ such that $S\subseteq V_{n}\in\mathcal{P}_{n}$. So, there exists
components $S_{n}$ such that

$\textstyle S\subseteq V_{n}\subseteq W_{n}\subseteq
B^{*}(S_{n},\frac{1}{n})\subseteq B(S_{n},\frac{1}{n}),$

where each $W_{n}\in\mathcal{B}_{n}$ witnesses that $\mathcal{P}_{n}$ is a
refinement of $\mathcal{B}_{n}$ and each $S_{n}$ witnesses that
$W_{n}\in\mathcal{B}_{n}$. We get $S=\bigcap\\{V_{n}:n>0\\}$. Indeed, suppose

$a\in\bigcap\\{V_{n}\colon n>0\\}\setminus S.$

Choosing a clopen set $U\supseteq S$ such that $a\notin U$, we have

$\varepsilon=d(S,X\setminus U)>0.$

Let points $b_{n}\in S_{n}$ be such that $d(a,b_{n})<\frac{1}{n}$, therefore
$\lim_{n\to\infty}b_{n}=a$. For all but finitely many $n$, we have $b_{n}\in
S_{n}\subseteq X\setminus U$ and $B(S,{\varepsilon})\cap S_{n}=\emptyset$, and
consequently $S\cap B(S_{n},\varepsilon)=\emptyset$. On the other hand, for
sufficiently large $n$, we get

$\textstyle S\subseteq V_{n}\subseteq B(S_{n},\frac{1}{n})\subseteq
B(S_{n},\varepsilon);$

a contradiction. ∎

Recall that a family $\mathcal{P}$ of subsets of $X$ is called a partition,
whenever $\bigcup\mathcal{P}=X$ and $\mathcal{P}$ consists of non-empty
pairwise disjoint sets.

######  Lemma 4.

If $X$ is a compact metric space, a set $V\subseteq X$ is clopen and $n>0$,
then there exists a family $\mathcal{P}$, consisting of pairwise disjoint
clopen sets, that is a refinement of $\mathcal{B}_{n}$ and
$V=\bigcup\mathcal{P}$. In addition, if $X$ satisfies condition $(\star)$,
then $\mathcal{P}$ can be chosen such that
$\mathcal{P}\subseteq\mathcal{B}_{n}$.

###### Proof.

Fix $n>0$. For each component $S\subseteq V$, using Fact 2, choose a clopen
set $V(S)$ such that

$\textstyle S\subseteq V(S)\subseteq B^{*}(S,\frac{1}{n})\cap V.$

Thus sets $V(S)$ constitute a cover of $V$, so there exists a finite cover
$\\{V(S_{1}),\ldots,V(S_{k})\\}\subseteq\mathcal{B}_{n}$. If

$W_{i}=V(S_{i})\setminus\bigcup\\{V({S_{j}})\colon j<i\\},$

then sets $W_{i}\neq\emptyset$ form a partition of $V$ that is a refinement of
$\mathcal{B}_{n}$.

Assume that condition $(\star)$ is fulfilled. For each non-trivial component
$S$ let the sets $V(S)$ be such that

$\textstyle S\subseteq V(S)\subseteq B^{*}(S,\varepsilon)\cap V,$

where $\varepsilon<\frac{1}{2n}$ is smaller than half the distance between the
endpoints of $S$. Let the sets $W_{i}$ be defined as above. If $S_{i}\subseteq
W_{i}$, then $W_{i}\in\mathcal{B}_{n}$. Otherwise $S_{i}\cap W_{i}=\emptyset$
and $W_{i}$ is a union of at most two disjoint clopen sets, each one of
diameter less than $\frac{1}{n}$. Any clopen set of diameter less than
$\frac{1}{n}$ with infinitely many components belongs to $\mathcal{B}_{n}$.
But, if a clopen set has finitely many components, then these components are
open and belong to $\mathcal{B}_{n}$. Whatever the case is, there exists a
partition of $W_{i}$ contained in $\mathcal{B}_{n}$. ∎

######  Lemma 5.

In a compact metric space $X$, there exists a sequence $(\mathcal{P}_{n})$ of
finite partitions of clopen sets such that each $\mathcal{P}_{n}$ is a
refinement of $\mathcal{B}_{n}$ and $\mathcal{P}_{n+1}$ is a refinement of
$\mathcal{P}_{n}$. In addition, if $X$ satisfies condition $(\star)$, then
$\mathcal{P}_{n}$ can be chosen such that
$\mathcal{P}_{n}\subseteq\mathcal{B}_{n}$.

###### Proof.

Using Lemma 4, define inductively partitions
$\mathcal{P}_{1},\mathcal{P}_{2},\ldots$ such that $\mathcal{P}_{n}$ refines
$\mathcal{B}_{n}$ and $\mathcal{P}_{n}$ refines $\mathcal{P}_{n-1}$, while
$\mathcal{P}_{0}=\\{X\\}$. If $X$ fulfils condition $(\star)$, then we apply
the second part of Lemma 4. ∎

######  Lemma 6.

Let $X$ be a compact metric space and $(\mathcal{P}_{n})$ be a sequence of
partitions as in Lemma 5. If $S\subseteq X$ is a component and $S\subseteq
V_{n}\in\mathcal{P}_{n}$ always hold, then $S=\bigcap\\{V_{n}:n>0\\}$.

###### Proof.

Let $S\subseteq X$ be a component and $S\subseteq V_{n}\in\mathcal{P}_{n}$ for
each $n$. Then the family $\mathcal{U}=\\{V_{n}:n>0\\}$ consists of exactly
those elements of $\bigcup\\{\mathcal{P}_{n}\colon n>0\\}$ that contain $S$.
We have $\bigcap\mathcal{U}=S$, since $\bigcup\\{\mathcal{P}_{n}\colon n>0\\}$
is a base for components. ∎

If a compact metric space $(X,d)$ and $W\subseteq X$ is a clopen set, then an
arc $[a,b]\subseteq W$ is said to be a _core_ of $W$, whenever $[a,b]$ is a
non-trivial component such that

$\textstyle[a,b]\subseteq W\subseteq B^{*}([a,b],\frac{1}{2}d(a,b))\mbox{ and
}(a,b)\mbox{ is open}.$

Not every clopen set has a core, but if it is the case, then such a core is
unique. Indeed, if $S_{1}=[a_{1},b_{1}]$ and $S_{2}=[a_{2},b_{2}]$ are
different cores of $W$, then $S_{2}\subseteq
B(a_{1},\frac{1}{2}d(a_{1},b_{1}))$ or $S_{2}\subseteq
B(b_{1},\frac{1}{2}d(a_{1},b_{1}))$, which implies
$d(a_{2},b_{2})<d(a_{1},b_{1})$. The interchange of $S_{1}$ and $S_{2}$ gives
$d(a_{1},b_{1})<d(a_{2},b_{2})$; a contradiction.

######  Theorem 7.

If a compact and metric space $(X,d)$ satisfies condition $(\star)$, then $X$
is homeomorphic to a subset of the reals.

###### Proof.

For each non-trivial component $[a,b]$ of $X$, choose a homeomorphism
$f_{[a,b]}\colon[a,b]\rightarrow[0,1]$ such that $f_{[a,b]}(a)=0$. Let
$(\mathcal{P}_{n})$ be a sequence of finite partitions of $X$ such that
$\mathcal{P}_{n}\subseteq\mathcal{B}_{n}$ and $\mathcal{P}_{n}$ is a
refinement of $\mathcal{P}_{n-1}$. Without loss of generality, by modifying
the construction of partitions $\mathcal{P}_{n}$ used in Lemma 5, assume that
if $W\in\mathcal{P}_{n-1}$ has the core $[a,b]$, then for any
$V\in\mathcal{P}_{n}$ such that $V\subseteq W$, we have $V\subseteq
B(a,\frac{1}{n})$ or $V\subseteq B(b,\frac{1}{n})$, or $[a,b]\subseteq V$.
Define (linear) strict ordering $\sqsubset_{n}$, each one on the family
$\mathcal{P}_{n}$, such that the following conditions hold.

  1. (1)

$V_{1}\sqsubset_{n}V_{2}$, whenever $V_{1},V_{2}\in\mathcal{P}_{n}$,
$V_{1}\subseteq W_{1}\in\mathcal{P}_{n-1}$, $V_{2}\subseteq
W_{2}\in\mathcal{P}_{n-1}$ and $W_{1}\sqsubset_{n-1}W_{2}$.

  2. (2)

If $W\in\mathcal{P}_{n-1}$ has the core $[a,b]\subseteq
V^{*}\in\mathcal{P}_{n}$, then for any $V\in\mathcal{P}_{n}$, such that
$V\subseteq W$, we have: if $V\subseteq B(a,\frac{1}{n})$, then
$V\sqsubset_{n}V^{*}$; if $V\subseteq B(b,\frac{1}{n})$, then
$V^{*}\sqsubset_{n}V$.

Assume inductively that the order $\sqsubset_{n}$ is already defined. Given
two sets $V_{1},V_{2}\in\mathcal{P}_{n+1}$ the order $\sqsubset_{n+1}$ between
them is determined by condition (1) unless they are subsets of the same set
$W\in\mathcal{P}_{n}$. In such a case, define an arbitrarily linear order on
$\\{V\in\mathcal{P}_{n+1}\colon V\subseteq W\\}$, maintaining condition (2).

Given orders $\sqsubset_{n}$ we order linearly the family $\mathcal{C}$ of all
components of $X$ as follows. Let $S$, $S^{\prime}$ be two different
components of $X$. Consider sequences of clopen sets
$(W_{n}),(W_{n}^{\prime})$ such that $W_{n},W_{n}^{\prime}\in\mathcal{P}_{n}$
and $\bigcap_{n}W_{n}=S$, and $\bigcap_{n}W_{n}^{\prime}=S^{\prime}$. If $n$
is the smallest number such that $W_{n}\neq W_{n}^{\prime}$, then let
$\sqsubset$ order $S$ and $S^{\prime}$ in the same manner as $\sqsubset_{n}$
orders sets $W_{n}$ and $W_{n}^{\prime}$. If $\mathcal{C}^{*}$ is the union of
sets $\\{(S,0)\colon S\text{ is a trivial component}\\}$ and $\\{(I,x)\colon
I\text{ is a non-trivial component and }x\in[0,1]\\}$, then equip it with the
lexicographic order $\prec$ induced by $\sqsubset$ and the standard inequality
$<$.

The space $X$ is homeomorphic to $\mathcal{C}^{*}$ with the order topology.
Indeed, for any $x\in X$, put

$F(x)=\begin{cases}([a,b],f_{[a,b]}(x)),&\mbox{ if
}x\in[a,b]\in\mathcal{C};\\\ (S,0),&\mbox{ if
}S=\\{x\\}\in\mathcal{C}.\end{cases}$

Clearly $F\colon X\rightarrow\mathcal{C}^{*}$ is a bijection.

Fix $x\in X$ and a sequence of sets $(W_{n})$ such that $x\in
W_{n}\in\mathcal{P}_{n}$. If $\\{x\\}$ is a trivial component or is the right
endpoint of a non-trivial component $[a,b]$, then

$F^{-1}[(F(x),\to)]=\bigcup\\{V\colon V\in\mathcal{P}_{n}\mbox{ and
}W_{n}\sqsubset_{n}V\mbox{ and }n>0\\}$

is open, being a union of open sets.

But if $I=[a,b]\subseteq X$ is a non-trivial component and $x\in[a,b)$, then
we have that the set

$F^{-1}[(\leftarrow,F(x)]]=[a,x]\cup\bigcup\\{W\in\mathcal{P}_{n}\colon
W\sqsubset_{n}W_{n}\mbox{ and }n>0\\}$

is closed. Thus, $F$ is continuous and since the domain of $F$ is compact,
hence $F$ is a homeomorphism.

In the space $\mathcal{C}^{*}$ there exist at most countably many gaps, i.e.
points with immediate successors with respect to $\prec$. Filling these gaps
with copies of the interval $(0,1)$, we obtain an arc that contains a copy of
$X$. ∎

######  Remark 8.

In the proof of the above theorem the ordering of endpoints of non-trivial
components did not matter.

##  3\. Some remarks on Cantorvals

Authors of the paper [6] considered the arithmetic sum of two Cantor sets on
the reals. For some classes of such sets the arithmetic sum can be of the form
which they called: M-Cantorval, L-Cantorval or R-Cantorval. Each of these
notions represents a compact subset of the reals with given properties. Also,
nowadays it is common to call what they meant by M-Cantorval simply Cantorval
or sometimes symmetric Cantorval, see [7, p. 16] or compare [8]. There are a
few approaches to the definition of a Cantorval. For example, a Cantorval is a
nonempty compact subset $K\subseteq\mathbb{R}$ such that $K$ is the closure of
its interior and endpoints of any non-trivial component of $K$ are limit
points of trivial components of $K$, see [7, Definition 13]. Let us describe a
specific Cantorval, compare [1, p. 354]. Consider the classical ternary Cantor
set and let $G_{n}$ be the union of $2^{n-1}$ open intervals removed at the
$n$-th step of its construction, i.e.

$\textstyle
G_{1}=\left(\frac{1}{3},\frac{2}{3}\right)\subseteq\mathbb{R}\mbox{ and
}G_{n+1}=\frac{1}{3}G_{n}\cup\left(\frac{1}{3}G_{n}+\frac{2}{3}\right).$

The set

$C=[0,1]\setminus\bigcup_{k\in\mathbb{N}}G_{2k}$

is a Cantorval and we will call it model Cantorval. As it was shown, see [6,
p. 343], [7, p. 16], [1, p. 355], [11, Theorem 1.3] or [15, Wniosek 26.], any
two Cantorvals are homeomorphic. Topological characterizations of a Cantorval
are given in [1, Theorem 21.18.] and [6, pp. 330/331]. Another
characterization can be also extracted from the proofs of Guthrie–Nymann’s
classification theorem on sets of subsums of a convergent series of real
numbers, see [4, Theorem 1.(iii)].

Following the paper [6], a subset $X$ of the reals is an _L-Cantorval_
[respectively _R-Cantorval_] whenever it is nonempty, compact and any gap has
an interval adjacent to its right [left] and is accumulated on the left
[right] by infinitely many intervals and gaps. Thus, if $X$ is an L-Cantorval,
then $\min X$ is the endpoint of the $X$-interval. Directly from the
definition, we get that the map $x\mapsto-x$ carries an L-Cantorval onto the
R-Cantorval and vice versa. Also, if $[a,b]$ is an interval in an L-Cantorval,
then $b$ cannot be an endpoint of any gap, but $a$ is not necessarily an
endpoint of a gap, i.e. $a$ can be accumulated by infinitely many gaps and
intervals. It is known that there exist non-homeomorphic L-Cantorvals, see the
last paragraph of Appendix in [6]. As we show, there exist continuum many non-
homeomorphic L-Cantorvals, see Theorem 9.

We say that an endpoint $e$ of a non-trivial component $I\subseteq X$ is free,
whenever $X$ satisfies condition $(\star)$ and $e\in\operatorname{int}_{X}I$.
A set $X\subseteq\mathbb{R}$ is called left-oriented, whenever any
$X$-interval with exactly one free endpoint has the left endpoint free. If
$(a,b)$ is an $X$-gap such that the point $b$ is a limit point of free left
endpoints of $X$-intervals, then $(a,b)$ is called an _inappropriate_ $X$-gap.
If $X$ is left-oriented, each non-empty clopen subset of $X$ contains a non-
trivial component with exactly one free endpoint, $\\{b\\}$ is a trivial
component and $b$ is the right endpoint of an $X$-gap $(a,b)$, then $(a,b)$ is
an inappropriate gap. If $X\subseteq\mathbb{R}$, then we say that a clopen
subset $W\subseteq X$ is segment-like with respect to $X$, if $W=X\cap I$
where $I$ is a closed interval and $\min W$ belongs to an $X$-interval.

Assume that $X\subseteq\mathbb{R}$ is a compact set and $(a,b)$ is an
inappropriate $X$-gap. We say that a pair consisting of a function $f\colon
X\rightarrow f[X]$ and a family $\mathcal{P}=\\{V_{k}\colon k\geqslant 0\\}$
of non-empty clopen sets is a correction of $(a,b)$ with respect to
$\varepsilon>0$, if the following conditions are fulfilled.

  * •

$\bigcup\\{V_{k}\colon{k\geqslant 0}\\}=X\cap(b,b+\eta)$ where
$\eta<\min\\{b-a,\varepsilon\\}$.

  * •

$\max V_{k+1}<\min V_{k}$ and each $V_{k}$ is segment-like.

  * •

$f(x)=\begin{cases}x-\delta_{k},&x\in V_{k};\\\ x,&x\in
X\setminus\bigcup\\{V_{k}\colon{k>0}\\},\end{cases}$

where $\delta_{k}=\max V_{k}+\min V_{k}-2b$.

Clearly, if $f$ is a correction of $(a,b)$ with respect to $\varepsilon$, then
$f$ is a homeomorphism, for any $x\in X$, we have $0\leqslant
x-f(x)<2\varepsilon$ and if $X$ is left-oriented, then $f[X]$ is left-
oriented. Also, the $f[X]$-gap $(b,\min V_{0})$ is not inappropriate.

######  Theorem 9.

Let $(X,d)$ be a compact metric space that satisfies condition $(\star)$. If
each non-empty clopen subset of $X$ contains a non-trivial component with
exactly one free endpoint, then $X$ is homeomorphic to an L-Cantorval.

###### Proof.

By Theorem 7 and Remark 8, we can assume that $X\subseteq\mathbb{R}$ and $X$
is left-oriented. Assume that $(a_{1},b_{1}),(a_{2},b_{2}),\ldots$ is an
enumeration of all inappropriate $X$-gaps. Let $f_{1}\colon X\to X_{1}$ and
$\mathcal{P}_{1}^{*}=\\{V_{k}\colon k\geqslant 0\\}$ be a correction of the
$X$-gap $(a_{1},b_{1})$ with respect to $\varepsilon=1$. Put
$\mathcal{P}_{1}=\\{f_{1}[V_{k}]\colon k>0\\}\cup\\{(-\infty,a_{1}]\cap
X,[\min V_{0},+\infty)\cap X\\}$.

For $i<n$, assume inductively, that there are already defined families
$\mathcal{P}_{i}$ of clopen sets in $X_{i}$ and homeomorphisms $f_{i}\colon
X_{i-1}\to X_{i}\subseteq\mathbb{R}$. Let $f_{n}\colon X_{n-1}\to X_{n}$ and a
family $\mathcal{P}^{*}=\\{V_{k}\colon k\geqslant 0\\}$ be a correction of an
$X_{n-1}$-gap $(p_{n},q_{n})$ with respect to $2^{-n}$, where

$(p_{n},q_{n})=(f_{n-1}\circ\ldots\circ f_{1}(a_{n}),f_{n-1}\circ\ldots\circ
f_{1}(b_{n})).$

Choose a family $\mathcal{P}_{n}$, which consists of:

  1. (1)

all sets from $\mathcal{P}_{n-1}\setminus\\{W\\}$, where $p_{n}\in
W\in\mathcal{P}_{n-1}$;

  2. (2)

the set $W\cap[\min V_{0},\max W]$;

  3. (3)

the set $W\cap[\min W,p_{n}]$;

  4. (4)

sets $f_{n}[V_{k}]\subseteq(p_{n},q_{n})$, for $k>0$.

Since each $f_{n}$ is a correction of the $X_{n-1}$-gap $(p_{n},q_{n})$ with
respect to $\varepsilon=2^{-n}$, then the sequence $(f_{n}\circ\ldots\circ
f_{1})$ is uniformly convergent to the continuous surjection $h\colon X\to
X_{\infty}$.

Suppose $x_{0},x_{1}\in X$, $x_{0}\neq x_{1}$ and $h(x_{0})=h(x_{1})$. Without
loss of generality, we can assume that $f_{n}\circ\ldots\circ f_{1}(x_{0})\in
V\in\mathcal{P}_{n}$ and $f_{n}\circ\ldots\circ f_{1}(x_{1})\notin V$, where
$n>0$. Therefore $f_{m}\circ\ldots\circ f_{1}(x_{0})\in[\min V,\max V]$ and
$f_{m}\circ\ldots\circ f_{1}(x_{1})\notin[\min V,\max V]$ for each $m\geqslant
n$, which is in conflict with $h(x_{0})=h(x_{1})$. Thus, $h$ is a continuous
bijection, i.e. $h\colon X\to h[X]=X_{\infty}\subseteq\mathbb{R}$ is a
homeomorphism.

If $J$ is an arbitrary $X$-interval, then $f_{n+1}\circ\ldots\circ
f_{1}|_{J}=f_{n}\circ\ldots\circ f_{1}|_{J}$ for sufficiently large $n$.
Therefore $X_{\infty}$ is left-oriented, since each $f_{n}\circ\ldots\circ
f_{1}$ preserves this property.

Suppose that $(c,d)$ is an inappropriate $X_{\infty}$-gap. If

$d_{n}=f_{n}\circ\ldots\circ f_{1}(h^{-1}(d)),$

then the sequence $(d_{n})$ converges to $d$ and there exists $n$ such that
$d_{n+1}<d_{n}$, since $h^{-1}(d)$ cannot be the right endpoint of an
inappropriate $X$-gap. Then $d_{n}\in V_{k}$, where the set $V_{k}$ is
segment-like and is moved to the left by $f_{n}$. If $2^{-n}<d-c$, then we get
$d<\min V_{k}<d_{m}$ for each $m\geqslant n$, a contradiction. Hence the proof
is finished, since we show that $X_{\infty}$ is an $L$-Cantorval. ∎

For a compact set $X\subseteq\mathbb{R}$, we adopt the notation from [15].
Namely, let $\mathcal{A}_{X}$ be the family of all $X$-gaps and
$\mathcal{B}_{X}$ be the family of all $X$-intervals. Thus $\mathcal{A}_{X}$
consists of pairwise disjoint open intervals, $\mathcal{B}_{X}$ consists of
pairwise disjoint closed intervals and both families are countable. Note that
$\bigcup(\mathcal{A}_{X}\cup\mathcal{B}_{X})$ is a dense subset of
$\mathbb{R}$. Indeed, if
$x\in\mathbb{R}\setminus\bigcup(\mathcal{A}_{X}\cup\mathcal{B}_{X})$, then
$\\{x\\}$ is a component of $X$, so $x$ is the limit point of
$\bigcup\mathcal{A}_{X}$. The union $\mathcal{A}_{X}\cup\mathcal{B}_{X}$ can
be naturally equipped with an order, namely $I<J$ whenever $x<y$ for all $x\in
I$ and $y\in J$.

######  Proposition 10.

Let $X$ and $Y$ be compact subsets of the reals. There exists an increasing
homeomorphism $f\colon\mathbb{R}\to\mathbb{R}$ such that $f[X]=Y$ if and only
if there exists an order isomorphism
$F\colon\mathcal{A}_{X}\cup\mathcal{B}_{X}\rightarrow\mathcal{A}_{Y}\cup\mathcal{B}_{Y}$
such that $F[\mathcal{A}_{X}]=\mathcal{A}_{Y}$.

###### Proof.

If $f\colon\mathbb{R}\to\mathbb{R}$ is an increasing homeomorphism such that
$f[X]=Y$, then $F(I)=f[I]$ is a required homeomorphism.

Conversely, assume
$F\colon\mathcal{A}_{X}\cup\mathcal{B}_{X}\to\mathcal{A}_{Y}\cup\mathcal{B}_{Y}$
is an isomorphism that carries $\mathcal{A}_{X}$ onto $\mathcal{A}_{Y}$. If
$I\in\mathcal{A}_{X}\cup\mathcal{B}_{X}$, then let $f_{I}\colon I\to F(I)$ to
be an increasing homeomorphism. For each $x\in I$, put $f(x)=f_{I}(x)$. Sets
$\bigcup(\mathcal{A}_{X}\cup\mathcal{B}_{X})$ and
$\bigcup(\mathcal{A}_{Y}\cup\mathcal{B}_{Y})$ are dense in $\mathbb{R}$, so
already defined function $f$ is na increasing bijection between dense subsets
of the reals. This bijection can be uniquely extended to a desired
homeomorphism. ∎

If $C\subseteq\mathbb{R}$ is a Cantor set, then $\mathcal{B}_{C}=\emptyset$
and $\mathcal{A}_{C}$ is densely ordered. Any two countable densely ordered
sets with the first and the last elements are isomorphic, since they are
isomorphic to $\mathbb{Q}\cap[0,1]$. From Proposition 10 it follows that any
compact set $X\subseteq\mathbb{R}$ such that $\mathcal{B}_{X}=\emptyset$ and
$\mathcal{A}_{X}$ is densely ordered, is an image of the Cantor set by a
homeomorphism of $\mathbb{R}$. In other words, we get a well-known property of
the Cantor set, i.e. if a non-empty compact set $X\subseteq\mathbb{R}$ is
dense in itself and $\operatorname{int}_{\mathbb{R}}X=\emptyset$, then $X$ is
the image of the Cantor set by an autohomeomorphism of $\mathbb{R}$.

Let $\mathbb{Q}\cap[0,1]=A_{\mathbb{Q}}\cup B_{\mathbb{Q}}$ be a partition
such that $A_{\mathbb{Q}}$ and $B_{\mathbb{Q}}$ are dense in
$\mathbb{Q}\cap[0,1]$ and $\\{0,1\\}\subseteq A_{\mathbb{Q}}$.

######  Lemma 11.

If $(X,\sqsubset)$ is a countable linear order such that $X=A_{X}\cup B_{X}$
and $\min X\in A_{X}$, and $\max X\in A_{X}$, and the sets $A_{X},B_{X}$ are
disjoint and dense in $X$, then there exists an isomorphism $F$ between
$(X,\sqsubset)$ and $(\mathbb{Q}\cap[0,1],\leqslant)$ such that
$F[A_{X}]=A_{\mathbb{Q}}$.

###### Proof.

Adopt the well-known back-and-forth method. ∎

The next corollary is a variant of a result by Marta Walczyńska, compare [15,
Wniosek 26].

######  Corollary 12.

If a set $X\subseteq\mathbb{R}$ is non-empty, compact and regularly closed
such that no $X$-interval has a free endpoint, then there exists a
homeomorphism $f\colon\mathbb{R}\to\mathbb{R}$ such that the image $f[X]$ is
the model Cantorval.

###### Proof.

Clearly, the interior $\operatorname{int}_{\mathbb{R}}X$ is dense in $X$ and
no $X$-gap and $X$-interval have a common endpoint. Also, between any two
$X$-gaps lies an $X$-interval, between an $X$-gap and an $X$-interval lies an
$X$-gap, and also between any two $X$-intervals there is an $X$-gap. Therefore
sets $\mathcal{A}_{X}$ and $\mathcal{B}_{X}$ are dense in
$\mathcal{A}_{X}\cup\mathcal{B}_{X}$, i.e. between any two elements of
$\mathcal{A}_{X}\cup\mathcal{B}_{X}$ lie an element of $\mathcal{A}_{X}$ and
an element of $\mathcal{B}_{X}$. By Lemma 11 there exists an order isomorphism
$F\colon\mathcal{A}_{X}\cup\mathcal{B}_{X}\rightarrow\mathcal{A}_{C}\cup\mathcal{B}_{C}$
such that $F[\mathcal{A}_{X}]=\mathcal{A}_{C}$, where $C$ is the model
Cantorval. By Proposition 10 there exists a homeomorphism $f$ such that the
image $f[X]$ is the model Cantorval. ∎

We say that $L$-Cantorval $X\subseteq\mathbb{R}$ is _special_ , whenever each
$X$-interval has the left endpoint free.

######  Corollary 13.

Let $X$ be a compact metric space that fulfills condition $(\star)$. If the
union of all non-trivial components of $X$ is dense and each non-trivial
component has exactly one free endpoint, then $X$ is homeomorphic to the
special $L$-Cantorval.

###### Proof.

The union of all non-trivial components of $X$ is dense, hence each clopen
subset of $X$ contains a non-trivial component. By Theorem 9, $X$ is
homeomorphic to a special $L$-Cantorval. ∎

Suppose that $X\subseteq\mathbb{R}$ is a special $L$-Cantorval and
$(\mathcal{A}_{X}\cup\mathcal{B}_{X},\leqslant)$ is the linear space assigned
to $X$. We have the following.

  * (I).

If $I\in\mathcal{A}_{X}$ and $I$ is not the greatest element of
$\mathcal{A}_{X}\cup\mathcal{B}_{X}$, then there exists $J\in\mathcal{B}_{X}$
such that $J$ is the immediate successor of $I$.

  * (II).

If $J\in\mathcal{B}_{X}$, then there exists $I\in\mathcal{A}_{X}$ such that
$I$ is the immediate predecessor of $J$.

  * (III).

The ordered space $(\mathcal{A}_{X},\leqslant)$ is isomorphic to the set of
rational numbers contained in the interval $[0,1]$ with the natural ordering.

Indeed, by the definition the right endpoint of an $X$-gap belongs to the
$X$-interval, which implies (I). The condition of an $L$-Cantorval being
special implies (II). Suppose $I,J\in\mathcal{A}_{X}$ and $I<J$. Let $K$ be an
$X$-interval containing the right endpoint of $I$. Since $\max K<\inf J$,
therefore there exists an $X$-gap that lies between $I$ and $J$. So,
$\mathcal{A}_{X}$ is densely ordered, hence isomorphic to
$\mathbb{Q}\cap[0,1]$.

Conditions (III) and (II) imply that no $I\in\mathcal{A}_{X}$ has an immediate
predecessor in $(\mathcal{A}_{X}\cup\mathcal{B}_{X},\leqslant)$. Indeed, let
$I\in\mathcal{A}_{X}$ and suppose $J\in\mathcal{B}_{X}$ is the immediate
predecessor of $I$. According to (II) there exists $K\in\mathcal{A}_{X}$ which
is the immediate predecessor of $J$. Consequently, no element from
$\mathcal{A}_{X}$ lies between $I$ and $K$, which contradicts (III).

######  Lemma 14.

Let $(A_{1}\cup B_{1},\leqslant)$ and $(A_{2}\cup B_{2},\leqslant)$ be
infinite countable ordered spaces, where $A_{i}\cap B_{i}=\emptyset$ for
$i\in\\{1,2\\}$. If the pairs $(A_{i},B_{i})$ fulfill conditions (I)–(III),
where $A_{i}$ is substituted for $\mathcal{A}_{X}$ and $B_{i}$ for
$\mathcal{B}_{X}$, then there exists an order isomorphism $F\colon A_{1}\cup
B_{1}\to A_{2}\cup B_{2}$ such that $F[A_{1}]=A_{2}$.

###### Proof.

Using (III), fix an order isomorphism $F:A_{1}\to A_{2}$. If $J\in B_{1}$ and
$I\in A_{1}$ is an immediate predecessor of $J$, them let $F(J)$ be an
immediate successor of $F(I)$. Thus, $F\colon A_{1}\cup B_{1}\to A_{2}\cup
B_{2}$ is a well defined increasing bijection, because of conditions (I) and
(II). ∎

######  Corollary 15.

If $X$ and $Y$ are special $L$-Cantorvals, then there exists an increasing
homeomorphism $f\colon\mathbb{R}\to\mathbb{R}$ such that $f[X]=Y$.

###### Proof.

Let $(\mathcal{A}_{X}\cup\mathcal{B}_{X},\leqslant)$ and
$(\mathcal{A}_{Y}\cup\mathcal{B}_{Y},\leqslant)$ be linear orders assigned to
$X$ and $Y$, respectively. Both spaces
$(\mathcal{A}_{X}\cup\mathcal{B}_{X},\leqslant)$ and
$(\mathcal{A}_{Y}\cup\mathcal{B}_{Y},\leqslant)$ fulfill conditions (I)–(III).
By Lemma 14, there exists an isomorphism
$F\colon\mathcal{A}_{X}\cup\mathcal{B}_{X}\to\mathcal{A}_{Y}\cup\mathcal{B}_{Y}$
such that $F[\mathcal{A}_{X}]=\mathcal{A}_{Y}$. Proposition 10 gives a desired
homeomorphism. ∎

##  4\. Non-homeomorphic $L$-Cantorvals

Let $X$ be a topological space and $\mathcal{C}_{X}$ be the family of all
components of $X$. If $V$ is clopen in $X$, then put
$V^{*}=\\{C\in\mathcal{C}_{X}\colon C\subseteq V\\}$. The family
$\\{V^{*}\colon V\mbox{ is a clopen subset of }X\\}$ is a base for the
topology $\mathcal{T}_{X}$ it generates. If $f\colon X\to Y$ is a
homeomorphism, then $F\colon\mathcal{C}_{X}\to\mathcal{C}_{Y}$ is given by the
formula $F(C)=f[C]$. Clearly, if $V$ is a clopen subset of $X$, then
$F[V^{*}]=f[V]^{*}$. Hence, $F$ is a homeomorphism and if
$Z\subseteq\mathcal{C}_{X}$, then $F|_{Z}$ is a homeomorphism between $Z$ and
$F[Z]$ with respect to inherited topologies. Moreover, if $f\colon X_{0}\to
X_{1}$ is a homeomorphism between $L$-Cantorvals and
$\mathcal{Z}_{i}=\\{C\in\mathcal{C}_{X_{i}}\colon C\mbox{ has no free
endpoint}\\}$, then subspaces $\mathcal{Z}_{0}\subseteq\mathcal{C}_{X_{0}}$
and $\mathcal{Z}_{1}\subseteq\mathcal{C}_{X_{1}}$ are homeomorphic.

######  Lemma 16.

Let $\alpha$ be a countable ordinal and $A\subseteq\alpha$. There exists an
$L$-Cantorval $X$ such that the set $\\{C\in\mathcal{C}_{X}\colon C\mbox{ has
no free endpoint}\\}$ with the topology inherited from $\mathcal{C}_{X}$ is
homeomorphic to $A$ with the topology inherited from linear topology on
$\alpha$.

###### Proof.

We may assume that $\alpha\subseteq[0,1]$ is equipped with the topology
inherited from $[0,1]$ is compact. Let $a_{0},a_{1},\ldots$ be an enumeration
of $A$. The set

$\textstyle\mathcal{I}=([0,1]\times\\{0\\})\cup\bigcup\\{\\{a_{n}\\}\times[0,\frac{1}{2^{n}}]\colon
n<\omega\\}$

equipped with the lexicographic ordering is order isomorphic to $[0,1]$, in
particular $\mathcal{I}$ with the order topology is homeomorphic to $[0,1]$.
The set

$A^{*}=([0,1]\setminus\alpha)\times\\{0\\}$

is an open subset of $\mathcal{I}$. Replacing each component of $A^{*}$ by a
special $L$-Cantorval such that its minimum an maximum are its trivial
components, we obtain the desired $L$-Cantorval. ∎

######  Theorem 17.

There exists continuum many non-homeomorphic $L$-Cantorvals.

###### Proof.

There exists continuum many countable metric spaces which are scattered and
non-homeomorphic, see [9] or compare [12]. Each such space is a copy of a
subset of some countable ordinal number, see [5] or compare [12], [14].
Applying the previous lemma, we are done. ∎

## References

  * [1] A. Bartoszewicz, M. Filipczak, F. Prus-Wiśniowski, Topological and algebraic aspects of subsums of series. Traditional and present-day topics in real analysis, 345–366, Faculty of Mathematics and Computer Science. University of Łódź, Łódź, 2013.
  * [2] R. Engelking, General topology. Translated from the Polish by the author. Second edition. Sigma Series in Pure Mathematics, 6. Heldermann Verlag, Berlin, 1989. viii+529 pp.
  * [3] S. Głąb, J. Marchwicki, _Set of uniqueness for Cantorvals_ , Results Math.78(2023), no.1, Paper No. 9, 24 pp.
  * [4] J. A. Guthrie, J. E. Nymann, The topological structure of the set of subsums of an infinite series. Colloq. Math. 55 (1988), no. 2, 323–327.
  * [5] B. Knaster, K. Urbanik, _Sur les espaces complets séparables de dimension 0_ , Fund. Math. 40(1953), 194–202.
  * [6] P. Mendes, F. Oliveira, On the topological structure of the arithmetic sum of two Cantor sets. Nonlinearity 7 (1994), no. 2, 329–343.
  * [7] Z. Nitecki, Subsum Sets: Intervals, Cantor Sets, and Cantorvals. ArXiv:1106.3779v2 [math.HO] (8 July 2013).
  * [8] Z. Nitecki, Cantorvals and Subsum Sets of Null Sequences. Amer. Math. Monthly 122(9), 862-870, 2015.
  * [9] St. Mazurkiewicz, W. Sierpiński, Contribution à la topologie des ensembles dénombrables. Fundamenta Mathematicae 1, 17-27 (1920).
  * [10] R. L. Moore, J. R. Kline, On the most general plane closed point-set through which it is possible to pass a simple continuous arc. Annals of Mathematics (2) 20 (1919) no. 3, 218–223.
  * [11] Prus-Wiśniowski, F.: Beyond the sets of subsums. Preprints of the Faculty of Mathematics and Informatics, Lodz University (2013)
  * [12] Sz. Plewik, M. Walczyńska, On metric $\sigma$-discrete spaces. Algebra, logic and number theory, 239–253, Banach Center Publ., 108, Polish Acad. Sci. Inst. Math., Warsaw, (2016).
  * [13] L. A. Steen, J. A. Seebach, Jr. Counterexamples in topology. Dover Publications, Inc., Mineola, NY, 1995. xii+244 pp.
  * [14] R. Telgársky, Total paracompactness and paracompact dispersed spaces. Bull. Acad. Polon. Sci. Sér. Sci. Math. Astronom. Phys. 16 (1968), 567–572.
  * [15] M. Walczyńska, Zastosowania teorii kategorii w topologii ogólnej. Ph. D. Thesis (2018), http://hdl.handle.net/20.500.12128/4979.
  * [16] L. Zippin, The Moore–Kline problem. Trans. Amer. Math. Soc. 34 (1932), no. 3, 705–721.
  * [17] L. Zippin, Correction to a paper: “The Moore–Kline problem” [Trans. Amer. Math. Soc. 34 (1932), no. 3, 705–721; 1501658]. Trans. Amer. Math. Soc. 35 (1933), no. 4, 972.