<figure><img src="image_1.png" /></figure>

HAL
open science

# On Robustness for the Skolem and Positivity Problems

S Akshay, Hugo Bazille, Blaise Genest, Mihir Vahanwala

► To cite this version:

S Akshay, Hugo Bazille, Blaise Genest, Mihir Vahanwala. On Robustness for the Skolem and Positivity Problems. STACS 2022 - 39th International Symposium on Theoretical Aspects of Computer Science, May 2022, Marseille, France. pp.1-20, 10.4230/LIPIcs.STACS.2022.5 . hal-03695798

HAL Id: hal-03695798

https://hal.science/hal-03695798

Submitted on 15 Jun 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# On Robustness for the Skolem and Positivity Problems

S. Akshay

Indian Institute of Technology Bombay, Mumbai, India

Hugo Bazille

Laboratoire de Recherche et Développement de l'Epita (LRDE), Rennes, France

Blaise Genest

Univ Rennes, CNRS, IRISA, France

Mihir Vahanwala

Indian Institute of Technology Bombay, Mumbai, India

## Abstract

The Skolem problem is a long-standing open problem in linear dynamical systems: can a linear recurrence sequence (LRS) ever reach 0 from a given initial configuration? Similarly, the positivity problem asks whether the LRS stays positive from an initial configuration. Deciding Skolem (or positivity) has been open for half a century: The best known decidability results are for LRS with special properties (e.g., low order recurrences). On the other hand, these problems are much easier for "uninitialized" variants, where the initial configuration is not fixed but can vary arbitrarily: checking if there is an initial configuration from which the LRS stays positive can be decided by polynomial time algorithms (Tiwari in 2004, Braverman in 2006).

In this paper, we consider problems that lie between the initialized and uninitialized variant. More precisely, we ask if 0 (resp. negative numbers) can be avoided from every initial configuration in a neighborhood of a given initial configuration. This can be considered as a robust variant of the Skolem (resp. positivity) problem. We show that these problems lie at the frontier of decidability: if the neighborhood is given as part of the input, then robust Skolem and robust positivity are Diophantine-hard, i.e., solving either would entail major breakthrough in Diophantine approximations, as happens for (non-robust) positivity. Interestingly, this is the first Diophantine-hardness result on a variant of the Skolem problem, to the best of our knowledge. On the other hand, if one asks whether such a neighborhood exists, then the problems turn out to be decidable in their full generality, with PSPACE complexity. Our analysis is based on the set of initial configurations such that positivity holds, which leads to new insights into these difficult problems, and interesting geometrical interpretations.

**2012 ACM Subject Classification** Theory of computation → Logic and verification

**Keywords and phrases** Skolem problem, verification, dynamical systems, robustness

**Digital Object Identifier** 10.4230/LIPIcs.STACS.2022.5

**Funding** This work was partly supported by the DST/CEFIPRA/INRIA associated team EQuaVE, DST/SERB Matrices grant MTR/2018/00074, and ANR-20-CE25-0012 MAVeriQ.

## 1 Introduction

A linear recurrence relation (LRR) is a relation $u_{n+\kappa} = \sum_{j=0}^{\kappa-1} a_j \cdot u_{n+j}$ for all $n, \kappa \in \mathbb{N}, \kappa \ge 1$, defined by a tuple of non-negative, rational coefficients $(a_0, \dots, a_{\kappa-1})$. Given the first $\kappa$ entries of the recurrence $u_0, \dots, u_{\kappa-1}$ (called the initial configuration), the LRR uniquely defines an infinite sequence $(u_n)_{n \in \mathbb{N}}$, called a Linear Recurrence Sequence (LRS). The Skolem problem asks, given an LRS, i.e., a recurrence relation and an initial configuration, whether the sequence ever hits 0, i.e. does there exist $n \in \mathbb{N}$ with $u_n = 0$. The positivity problem is a

<figure><img src="image_3.png" /></figure>

© S. Akshay, Hugo Bazille, Blaise Genest, and Mihir Vahanwala;
licensed under Creative Commons License CC-BY 4.0

39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022).

Editors: Petra Berenbrink and Benjamin Monmege; Article No. 5; pp. 5:1–5:20

<figure><img src="image_4.png" /></figure>

LIPICS

Leibniz International Proceedings in Informatics

Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_5.png" /></figure>
5:2 On Robustness for the Skolem and Positivity Problems

variant where the question asked is whether for all $n \in \mathbb{N}$, $u_n \ge 0$. Both these problems have
applications in software verification, probabilistic model checking, discrete dynamic systems,
theoretical biology, economics.

While the statements seem simple, the decidability of these problems remains open since
their introduction in the 1930's. Only partial decidability results are known, e.g., when the
dimension is <5 [29]. For a subclass of LRS called simple, positivity is decidable for order
<10 [23]. On top of the inability to provide an algorithm to decide Skolem or positivity in
the general case, the authors of [24] prove an important hardness result: solving positivity
would entail a major breakthroughs in Diophantine approximations. More precisely, one
would be able to approximate the type of many transcendental numbers *t*, i.e., how close one
can approximate *t* with rational numbers with small denominators.

This hardness result contrasts with positive results obtained for relaxations of the problems.
First, the continuous relaxation, where instead of considering discrete steps for the recurrence,
Chonev et al [13] considers a continuous process, and some corresponding questions turn out
to be decidable subject to Schanuel's Conjecture. Second, instead of considering a fixed initial
configuration, [28, 12] consider every possible configuration as initial, i.e., they ask if there
exists an initial configuration starting from which ensures that all entries of the sequence
remain positive (this is sometimes called the uninitialized positivity problem). Surprisingly
they show that this problem can be decided in PTIME. More recently, this result has been
extended to processes with choices [5].

In this paper, we consider a natural variant that lies between the hard question of fixed
initial configuration [24], and the easy question when the initial configuration is totally
unconstrained [28, 12]. More precisely, we ask whether starting from an initial configuration
in a neighborhood, all entries of the recurrence sequence remain positive (we call this the
*robust positivity problem*) or away from zero (we call this the *robust Skolem problem*). An
immediate question that arises is whether the neighborhood is part of the input or not
and it turns out that this has a significant impact on decidability, as we discuss next. Our
motivation to look at these problems comes from their role in capturing a powerful and
natural notion of robustness, where the exact initial configuration cannot be fixed with
arbitrarily high precision (which is often the case with real systems).

Since we need to tackle multiple initial configurations, we reason about the set of initial
configurations from which positivity holds, which is sufficient to answer robustness questions.
For that, we revisit the usual algebraic equations in a more graphical manner, which forms
the crux of our approach. This allows us to reinterpret and generalize the hardness result of
[23], giving our first main contribution: if the neighborhood is given as a fixed ball, then
the problems remain hard: both robust Skolem and robust positivity are Diophantine-hard.
Interestingly, this holds regardless of whether the ball is open or closed.

We then turn to the problems where the ball is not fixed, and ask if there exists a radius
$\psi > 0$ such that 0 or negative numbers can be avoided from every initial configuration in
the $\psi$ ball around a given initial configuration. Our second main contribution is to show
that this robust version of the Skolem and positivity problems are both decidable in full
generality, with PSPACE complexities.

**Related work.** As mentioned earlier, the Skolem problem and its variants have received a
lot of attention. Given the hardness of these problems, $\varepsilon$-approximate solutions have been
considered, e.g., in [9, 1] with different definitions of approximations. In comparison with
our work, these are designed towards allowing approximate model checking. More recently
the notion of imprecision in Skolem and related problems was considered in [6, 15]. In [6],
the authors consider rounding functions at every step of the trajectory. In [15], the so called Pseudo-Skolem problem is defined, where imprecisions up to $\epsilon$ are allowed at every step of the trajectory, which is shown to be decidable in PTIME. These are quite different from our notion of robustness, which faithfully considers the trajectories generated from a ball representing $\epsilon$-perturbations around the initial configuration. Lastly, [22] considers real numbers as input (instead of rational numbers). This allows one to consider the set of initial configurations for which decidability of Skolem is not known, and show that this set has Lebesgue measure 0.

## 2 Preliminaries

Let $\kappa$ be any non-negative integer (which will be used to denote the order of the LRS). Let $\mathbf{c}, \mathbf{d}$ be two vectors of $\mathbb{R}^\kappa$ that can be seen as one dimensional matrices of $\mathbb{R}^{\kappa \times 1}$. The distance between $\mathbf{c}, \mathbf{d}$ is defined as $||\mathbf{c} - \mathbf{d}|| = \sqrt{(\mathbf{c} - \mathbf{d})^T (\mathbf{c} - \mathbf{d})}$, the standard $L_2$ distance. In this paper, we will consider two norms on vectors: the first is the standard $L_2$ norm $||\mathbf{c}||$. The second is size($\mathbf{c}$), denoting the size of its bit representation i.e., number of bits needed to write down $\mathbf{c}$ (for complexity). We use the same notation for scalar constants with size($a$) denoting the number of bits to represent a real/rational constant $a$. An algebraic number $\alpha$ is a root of a polynomial $p$ with integer coefficients. It can be represented uniquely [20] by a 4-tuple $(p, a, b, r)$ as the only root of $p$ at distance $< r$ of $a + ib$, with $a, b, r \in \mathbb{Q}$ (also see Appendix A.1). We define size($\alpha$) as the size of the bit representation of $(p, a, b, r)$.

### 2.1 Linear Recurrence Sequences

We start by defining linear recurrence relations and sequences over rationals.

**► Definition 1.** A linear recurrence relation $(u_n)_{n \in \mathbb{N}}$ of order $\kappa$ is specified by a tuple of coefficients $\mathbf{a} = (a_0, \dots, a_{\kappa-1}) \in \mathbb{Q}^\kappa$. Given an initial configuration $\mathbf{c} = (c_0, \dots, c_{\kappa-1}) \in \mathbb{Q}^\kappa$, the LRR uniquely defines a linear recurrence sequence (LRS henceforth), which is the sequence $(u_n(\mathbf{c}))_{n \in \mathbb{N}}$, inductively defined as $u_j(\mathbf{c}) = c_j$ for $j \le \kappa - 1$, and

$$u_{n+\kappa}(\mathbf{c}) = \sum_{j=0}^{\kappa-1} a_j u_{n+j}(\mathbf{c}) \text{ for all } n \in \mathbb{N}.$$

The companion matrix associated with the LRR/LRS (it does not depend upon the initial configuration $\mathbf{c}$) is:

$$M = \begin{bmatrix} 0 & 1 & 0 & \dots & 0 \\ 0 & 0 & 1 & \dots & 0 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & 0 & \dots & 1 \\ a_0 & a_1 & a_2 & \dots & a_{\kappa-1} \end{bmatrix}.$$

The characteristic polynomial of the LRR/LRS is $X^\kappa - \sum_{j=0}^{\kappa-1} a_j X^j$. The LRS is said to be simple if every root of the characteristic polynomial has multiplicity one. The size $s$ of the LRS is the size of its bit representation and is given by $s = \sum_{j=0}^{\kappa-1} (\text{size}(a_j) + \text{size}(c_j))$.

Notice that given an initial configuration $\mathbf{c} \in \mathbb{Q}^\kappa$, we have that $M^n \mathbf{c} = (u_n(\mathbf{c}), \dots, u_{n+\kappa-1}(\mathbf{c}))$. Reasoning in the $\kappa$ dimensions $(u_n, \dots, u_{n+\kappa-1})$ is a very useful technique that we will use throughout the paper as it displays the LRR as a linear transformation $M$.
5:4 On Robustness for the Skolem and Positivity Problems

The characteristic roots of an LRR/LRS are the roots of its characteristic polynomial, and also the eigenvalues of the companion matrix. Let $\gamma_1, \dots, \gamma_r \in \mathbb{C}$ be the characteristic roots of the LRR/LRS. An eigenvalue $\gamma_i$ is called dominant if it has maximal modulus $|\gamma_i| = \max_{j \le r} |\gamma_j|$, and residual otherwise. For all $j \le r$, $\gamma_j$ is algebraic and size($\gamma_j$) = $s^{\mathcal{O}(1)}$. We denote by $m_j$ the multiplicity of $\gamma_j$. We have $\sum_{j=1}^r m_j = \kappa$.

**Proposition 2 (Exponential polynomial solution [16]).** Given an initial configuration **c**, there exists a unique tuple of coefficients $(\alpha_{ij}(\mathbf{c}))_{i \le r, j < m_r}$ such that for all $n$,

$$u_n(\mathbf{c}) = \sum_{i=1}^{r} \left( \sum_{j=0}^{m_r-1} \alpha_{ij}(\mathbf{c}) n^j \right) \gamma_i^n.$$

The coefficients $\alpha_{ij}(\mathbf{c})$ can be solved for from the initial state $\mathbf{c}$ [17]. It is implicit in the solution that for all $i, j$, both $\alpha_{ij}$ and $\frac{1}{\alpha_{ij}}$ are algebraic with values and norms upper bounded by $2^{s^{\mathcal{O}(1)}}$. A formal proof of this claim can be found in [2, Lemmas 4, 5, 6].

If the LRS is simple, then by definition $m_i = 1$ for all $i$, and $u_n = \sum_{i=1}^r \alpha_i(\mathbf{c})\gamma_i^n$, with $\alpha_i(\mathbf{c})$ linear in $\mathbf{c}$, ie $\alpha_i(\lambda\mathbf{c} + \lambda'\mathbf{c}') = \lambda\alpha_i(\mathbf{c}) + \lambda'\alpha_i(\mathbf{c}')$.

**Example 3.** Consider the Linear Recurrence Relation of order 6 with $\mathbf{a} = (-1, 4, -8, 10, -8, 4)$, i.e. $u_{n+6} = 4u_{n+5} - 8u_{n+4} + 10u_{n+3} - 8u_{n+2} + 4u_{n+1} - u_n$. The roots of the characteristic polynomial are $1, e^{i2\pi\theta}, e^{-i2\pi\theta}$, with $\theta = \frac{1}{3}$, each with multiplicity 2, and all dominant (they have the same modulus 1). The exponential polynomial solution is of the form $u_n(\mathbf{c}) = z(\mathbf{c})n + z'(\mathbf{c}) + (x(\mathbf{c})n + x'(\mathbf{c}))e^{i2\pi n\theta} + (y(\mathbf{c})n + y'(\mathbf{c}))e^{-i2\pi n\theta}$. As $u_n(\mathbf{c})$ is real, we must have that $x(\mathbf{c}), y(\mathbf{c})$ are conjugates, as well as $x'(\mathbf{c}), y'(\mathbf{c})$, and thus:

$$u_n(\mathbf{c}) = z(\mathbf{c})n + z'(\mathbf{c}) + 2(\mathrm{Re}(x(\mathbf{c}))n + \mathrm{Re}(x'(\mathbf{c}))) \cos(2\pi n\theta) + 2(\mathrm{Im}(x(\mathbf{c}))n + \mathrm{Im}(x'(\mathbf{c}))) \sin(2\pi n\theta).$$

## 2.2 Skolem and positivity problems

**Definition 4 (Skolem problem).** Let $(u_n)_{n \in \mathbb{N}}$ an LRR and $\mathbf{c} \in \mathbb{Q}^\kappa$. The Skolem problem is to determine if there exists $n \in \mathbb{N}$ such that $u_n(\mathbf{c}) = 0$. The positivity (resp. strict positivity) problem is to determine if for all $n \in \mathbb{N}$, $u_n(\mathbf{c}) \ge 0$ (resp. $u_n(\mathbf{c}) > 0$).

In this work, we will be more interested in the complement problem of Skolem: namely, whether $u_n(\mathbf{c}) \ne 0$ for all $n$. This is of course equivalent in terms of decidability, but this formulation is more meaningful in terms of robustness, where we want to robustly avoid 0.

The famous Skolem-Mahler-Lech theorem states that the set $\{i \mid u_i(\mathbf{c}) = 0\}$ is the union of a finite set $F$ and finitely many arithmetic progressions [27, 18, 8]. These arithmetic progressions can be computed but the hard part lies in deciding if the set $F$ is empty: although we know that there is $N$ such that for all $n > N$, $n \notin F$, we do not have an effective bound on this $N$ in general. The Skolem problem has been shown to be decidable for LRS of order up to 4 [21, 29] and is still open for LRS of higher order. Also, only an NP-hardness bound is known if the order is unrestricted [10, 3].

For simple LRS, positivity has been shown to be decidable up to order 9 [23]. In [25], it is proved that positivity for simple LRS is hard for $co\exists\mathbb{R}$, the class of problems whose complements are solvable in the existential theory of the reals. A last result, from [24], shows the difficulty of positivity, linking it to Diophantine approximation: how close one can approximate a transcendental number with a rational number with small denominator. We will follow the reasoning from [24]. The *Diophantine approximation type* of a real number $x$ is defined as:

$$L(x) = \inf \left\{ c \in \mathbb{R} \mid \left|x - \frac{n}{m}\right| < \frac{c}{m^2}, n, m \in \mathbb{Z} \right\}.$$
As mentioned in [24], the Diophantine approximation type of most transcendental numbers is unknown. Let $\mathcal{A} = \{p + qi \in \mathbb{C} | p, q \in \mathbb{Q} \setminus \{0\}, p^2 + q^2 = 1\}$, i.e., the set of points on the unit circle of $\mathbb{C}$ with rational real and imaginary parts, excluding $1, -1, i$ and $-i$. The set $\mathcal{A}$ consists of algebraic numbers of degree 2, none of which are roots of unity [24]. In particular, writing $p + qi = 2^{i2\pi\theta} = (-1)^{2\theta}$, we have that $\theta \notin \mathbb{Q}$ [24]. We denote:

$$ \mathcal{T} = \{\theta \in (-1/2, 1/2] \mid e^{2\pi i \theta} \in \mathcal{A}\}. $$

As argued in [24], the set $\mathcal{T}$ is dense in $(-\frac{1}{2}, \frac{1}{2}]$, and is made only of transcendental numbers. In general, we don't have a method to compute $L(\theta)$ for $\theta \in \mathcal{T}$ (or approximate it with arbitrary precision):

**Definition 5.** We say that a problem is $\mathcal{T}$-Diophantine hard if its decidability entails that for all $\theta \in \mathcal{T}$ and $\varepsilon > 0$, one can compute a number $\ell$ such that $|\ell - L(\theta)| \le \varepsilon$.

Remarkably, in [24], it is shown that if one can solve the positivity problem in general, then one can also approximate $L(\theta)$. That is,

**Theorem 6 ([24]).** Positivity for LRS of order 6 is $\mathcal{T}$-Diophantine hard.

### 3 Robust Skolem and Robust Positivity

Both Skolem and Positivity consider a single initial configuration $\mathbf{c}$. In this article, we investigate the notion of robustness, that is, whether the property is true in a neighborhood of $\mathbf{c}$, which is important for real systems, where setting $\mathbf{c}$ with an arbitrary precision is not possible. We will consider two variants. The first one fixes the neighborhood as a ball $B_{\psi}$ of radius $\psi > 0$ around an initial configuration $\mathbf{c}$, while the second one asks for the existence of an $\psi > 0$ such that for every initial configuration in $B_{\psi}$, the respective condition is satisfied.

**Definition 7 (Robustness for Skolem and Positivity).** Let $(u_n)_{n \in \mathbb{N}}$ be a linear recurrence relation (specified by the coefficient $\mathbf{a} \in \mathbb{Q}^{\kappa}$), and $\mathbf{c} \in \mathbb{Q}^{\kappa}$ an initial configuration.

Given $\psi > 0$, the robust Skolem (resp. robust positivity) problem is to determine if for all $\mathbf{c}'$ with $||\mathbf{c}' - \mathbf{c}|| < \psi$ (open balls), or $||\mathbf{c}' - \mathbf{c}|| \le \psi$ (closed balls), we have $u_n(\mathbf{c}') \ne 0$ (resp. $u_n(\mathbf{c}') \ge 0$) for all $n \in \mathbb{N}$.

The $\exists$-robust Skolem (resp. $\exists$-robust positivity) problem is to determine if there exists $\psi > 0$ such that for all $||\mathbf{c}' - \mathbf{c}|| < \psi$ we have $u_n(\mathbf{c}') \ne 0$ (resp. $u_n(\mathbf{c}') \ge 0$) for all $n \in \mathbb{N}$.

Notice that we do not consider explicitly the case of closed balls for $\exists$-robust Skolem (resp. positivity), because there exists an open ball of radius $\psi > 0$ for which robust Skolem (resp. positivity) holds iff there exists a closed ball of radius $\psi' > 0$ (e.g. $\psi' = \frac{\psi}{2}$) for which it holds.

Our main results investigate the decidability and complexity of these problems.

**Theorem 8.** Robust Skolem and robust positivity are $\mathcal{T}$-Diophantine hard, even restricted to recurrence relations of order 6 for open or closed balls of rational radius $\psi$.

Our first result means that uninitialized positivity really needs the initial configuration to take a value possibly anywhere in the space rather than in a fixed neighborhood to obtain decidability via [28, 12]. We remark that Diophantine-hardness is known for the non-robust variant of positivity [24], but to the best of our knowledge, it was not known for any variant of the Skolem problem.

Surprisingly, by relaxing the neighborhood to be as small as desired, one obtains decidability in full generality, as stated by our second main result:
5:6 On Robustness for the Skolem and Positivity Problems

► Theorem 9. ∃-robust Skolem and ∃-robust positivity are decidable in PSPACE.

The main difference between our techniques and several past work (except [4] which is restricted to eigenvalues being roots of unity) is as follows: given an LRR ($u_n$)$_{n \in \mathbb{N}}$, our intuition and proofs hinge on representing the set $P$ of initial configurations $\mathbf{d}$ from which positivity holds. Formally:

$$P = \{ \mathbf{d} \in \mathbb{R}^k \mid u_n(\mathbf{d}) \ge 0 \text{ for all } n \in \mathbb{N} \}.$$

We may note that the set $P$ is convex. To see this, observe that for $d, d' \in P$, for all $\alpha, \beta > 0$ with $\alpha + \beta = 1$, we have $\alpha \mathbf{d} + \beta \mathbf{d}' \in P$ as $u_n(\alpha \mathbf{d} + \beta \mathbf{d}') = \alpha u_n(\mathbf{d}) + \beta u_n(\mathbf{d}') \ge 0$ for all $n$. We also remark that a definition similar to $P$ is possible for the set $S$ of initial configurations from which $0$ is avoided. But it turns out that that set is much harder to represent (e.g., it is not convex in general). Using $P$ surprisingly suffices to deal with robust Skolem as well.

In Section 4, we provide the geometric intuitions behind our ideas as well as set up the notations for the proofs of the above theorems. We exploit the geometric intuitions from Section 4 in Section 5, to prove Theorem 8 and in Section 6, to prove Theorem 9.

4 Geometrical representation of an LRR for Diophantine-hardness

We will show that, as for the non-robust variant, hardness starts at order 6. Hence, in this section and the next, we will focus on a particular LRR of order $\kappa = 6$, sufficient for the proof of hardness, i.e. Theorem 8. In Section 6, we will generalize some of the constructions explored here to obtain decidability of ∃-robust Skolem.

Let $\theta \in \mathcal{T}$, i.e. $e^{i2\pi\theta} = p + qi \in \mathcal{A}$, with both $p, q$ rational and $p^2 + q^2 = 1$. We want to approximate $L(\theta)$ (indeed this is the problem that is “Diophantine-hard”). Consider the Linear Recurrence Relation of order 6 defined by $\mathbf{a} = (-1, 4p+2, -(4p^2+8p+3), 8p^2+8p+4, -(4p^2+8p+2), 4p+2)$. The roots of the characteristic polynomial are $1, e^{i2\pi\theta}, e^{-i2\pi\theta}$, each with multiplicity 2, and all dominant (they have the same modulus 1). Example 3 is a particular case of this $\mathbf{a}$, with $p = \frac{1}{2} = \cos(\frac{\pi}{3})$. However, notice that $\theta = \frac{1}{3} \notin \mathcal{T}$ as it corresponds to $q = \sin(\frac{\pi}{3}) = \frac{\sqrt{3}}{2} \notin \mathbb{Q}$. Now, since $u_n(\mathbf{c})$ is a real number for any $n$ and real initial configuration $\mathbf{c}$, we can write the exponential polynomial solution in the form:

$$u_n(\mathbf{c}) = z_{dom}(\mathbf{c})n - x_{dom}(\mathbf{c})n \cos(2\pi n\theta) - y_{dom}(\mathbf{c})n \sin(2\pi n\theta) \\ + z_{res}(\mathbf{c}) - x_{res}(\mathbf{c}) \cos(2\pi n\theta) - y_{res}(\mathbf{c}) \sin(2\pi n\theta).$$

The coefficients $z_{dom}(\mathbf{c}), x_{dom}(\mathbf{c}), y_{dom}(\mathbf{c})$ and $z_{res}(\mathbf{c}), x_{res}(\mathbf{c}), y_{res}(\mathbf{c})$ are associated with the initial configuration $\mathbf{c}$ of the LRS. In the following, we reason in the basis of vectors $z_{dom} \to x_{dom} \to y_{dom} \to z_{res} \to x_{res} \to y_{res}$, as the geometrical interpretation is simpler in this basis. We will eventually get back to the original coordinate vector basis at the end of the process. From e.g., [17, Section 2], we know that we can transform from one basis to the other using an invertible Matrix $C$ with $C \cdot \mathbf{c} = (z_{dom}(\mathbf{c}), x_{dom}(\mathbf{c}), y_{dom}(\mathbf{c}), z_{res}(\mathbf{c}), x_{res}(\mathbf{c}), y_{res}(\mathbf{c}))$.

We study the positivity of $u_n$ by studying the positivity of $v_n = \frac{u_n}{n}$, for all $n \ge 1$. We denote $v_n^{dom}(z_{dom}, x_{dom}, y_{dom}) = z_{dom} - x_{dom} \cos(2\pi n\theta) - y_{dom} \sin(2\pi n\theta)$, which we call the dominant part of $v_n$, while we denote $v_n^{res}(z_{res}, x_{res}, y_{res}) = \frac{1}{n}(z_{res} - x_{res} \cos(2\pi n\theta) - y_{res} \sin(2\pi n\theta))$, which we call the residual part of $v_n$. The residual part tends towards 0 when $n$ tends towards infinity because of the coefficient $\frac{1}{n}$.
<figure><img src="image_6.png" /><figcaption>Figure 1 Visual representation of the cone $P_{(0,0,0)}$.</figcaption></figure>

## 4.1 High-Level intuition and Geometrical Interpretation

We provide a geometrical interpretation of set $P$. We cannot characterize it exactly, even in this particular LRR of order $κ = 6$ (else we could decide positivity for this case which is known to be Diophantine hard). To describe $P$, we define its “section” over $(z_{dom}, x_{dom}, y_{dom})$ given $(z_{res}, x_{res}, y_{res})$:

$$P_{(z_{res}, x_{res}, y_{res})} = \{(z_{dom}, x_{dom}, y_{dom}) \mid v_n(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \ge 0 \text{ for all } n\}.$$

It suffices to characterize $P_{(z_{res}, x_{res}, y_{res})}$ for all $(z_{res}, x_{res}, y_{res})$ in order to characterize $P$, as $P = \{(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \mid (z_{dom}, x_{dom}, y_{dom}) \in P_{(z_{res}, x_{res}, y_{res})}\}$. Among these sets, one is particularly interesting: $P_{(0,0,0)}$, as it is the set of tuples $(z_{dom}, x_{dom}, y_{dom})$ such that $v_n^{dom}(z_{dom}, x_{dom}, y_{dom}) \ge 0$ for all $n \in \mathbb{N}$. Our reason for focussing on this representation of $P$ is three-fold. First, unlike $P$, the set $P_{(0,0,0)}$ can be characterized exactly, as a cone depicted in Figure 1 (this will be formally shown in Lemma 10 below). Second, the set $P_{(z_{res}, x_{res}, y_{res})}$ is in 3 dimensions that we can represent more intuitively than a 6 dimensional set. Last but not least, we can show that $P_{(z_{res}, x_{res}, y_{res})} \subseteq P_{(0,0,0)}$ for all $(z_{res}, x_{res}, y_{res})$ (Lemma 12).

On the other hand, we also consider a related set in 6 dimensions:

$$P_{dom} = \{(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \mid \forall n, v_n^{dom}(z_{dom}, x_{dom}, y_{dom}) \ge 0\}.$$

We note that $P_{(0,0,0)}$ is the projection of $P_{dom}$ over the 3 dimensions $(z_{dom}, x_{dom}, y_{dom})$. Also, characterizing $P_{(0,0,0)}$ is sufficient to characterize $P_{dom}$ as $(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \in P_{dom}$ iff $(z_{dom}, x_{dom}, y_{dom}) \in P_{(0,0,0)}$. As $P_{(z_{res}, x_{res}, y_{res})} \subseteq P_{(0,0,0)}$ for all $(z_{res}, x_{res}, y_{res})$, we have $P \subseteq P_{dom}$.

We are now ready to represent $P_{(z_{res}, x_{res}, y_{res})}$ given some value $(z_{res}, x_{res}, y_{res})$. We can interpret $P_{(z_{res}, x_{res}, y_{res})}$ in terms of half spaces: $P_{(z_{res}, x_{res}, y_{res})} = \bigcap_{m=1}^{\infty} H_m^{+}(z_{res}, x_{res}, y_{res})$, with $H_m^{+}(z_{res}, x_{res}, y_{res}) = \{(z_{dom}, x_{dom}, y_{dom}) \mid v_m(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \ge 0\}$. The half space $H_m^{+}(z_{res}, x_{res}, y_{res})$ is delimited by hyperplane

$$H_m(z_{res}, x_{res}, y_{res}) = \{(z_{dom}, x_{dom}, y_{dom}) \mid v_m(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) = 0\}$$

which is a vector space $(\cos(2\pi m\theta)$ and $\sin(2\pi m\theta)$ are constant when $m$ is fixed).

Consider the case of $(z_{res}, x_{res}, y_{res}) = (0, 0, 0)$. We denote $H_m^+ = H_m^+(0, 0, 0)$ and $H_m = H_m(0, 0, 0)$ for all $m$. For instance, $H_0 = \{(z_{dom}, x_{dom}, y_{dom}) \mid z_{dom} = x_{dom}\}$, as $v_0^{dom}(z_{dom}, x_{dom}, y_{dom}) = z_{dom} - x_{dom}$.

Let $M_{dom}$ be the matrix associated with LRS $(v_n^{dom})_{n \in \mathbb{N}}$. We have $H_m = M_{dom}H_{m-1} = M_{dom}^m H_0$. We characterize $M_{dom}$ in Lemma 11 as a rotation around $\vec{z}_{dom}$ of angle $-2\pi\theta$, which allows to characterize $H_m$ as the hyperplane which is the rotation of $H_0$ of angle $2m\pi\theta$ around $\vec{z}_{dom}$. That is, the cone shape for $P_{(0,0,0)}$ is obtained by cutting away chunk of the 3D space delimited by hyperplanes ($H_m$), the rotation $2n\pi\theta$ being dense in $[-\pi, \pi]$.
5:8 On Robustness for the Skolem and Positivity Problems

<figure><img src="image_7.png" /><figcaption>■ **Figure 2** Sections of $P_{(0,0,0)}$ (in black) and $P_{(z_{res},x_{res},y_{res})}$ (in dashed red), carved out by hyperplanes $(H_i)$ (in black) and $(H_i(z_{res}, x_{res}, y_{res}))$ (in red) respectively.</figcaption></figure>

Coming back to some value $(z_{res}, x_{res}, y_{res}) \neq (0,0,0)$, we have that the hyperplane $H_n(z_{res}, x_{res}, y_{res})$ is parallel to the hyperplane $H_n$ (which is tangent to the cone $P_{(0,0,0)}$), because for $H_n$ of the form $uz_{dom}+vx_{dom}+wy_{dom} = 0$, we have $H_n(z_{res}, x_{res}, y_{res})$ is defined by $\{(z_{dom}, x_{dom}, y_{dom}) | uz_{dom}+vx_{dom}+wy_{dom} = C\}$, for $C = \frac{z_{res}+x_{res} \cos(2\pi n\theta)+y_{res} \sin(2\pi n\theta)}{n}$ a constant as $n$ is fixed.

Thus, with this idea in mind, we can visualize $P_{(z_{res},x_{res},y_{res})}$ as depicted in Figure 2, using $P_{(0,0,0)}$ and the hyperplanes $H_n(z_{res}, x_{res}, y_{res})$ parallel to $H_n$, with an explicit bound on the distance from $H_n(z_{res}, x_{res}, y_{res})$ to $H_n$, which further tends towards 0 as $n$ tends towards infinity. Next, we formalize the above intuition/picture into lemmas.

4.2 Characterization of $P_{(0,0,0)}$ and representing $P_{(z_{res},x_{res},y_{res})}$

We now formalize some of the ideas in the above subsection. First, we start with Lemma 10 which shows that $P_{(0,0,0)}$ describes a cone, as displayed on Figure 1.

► **Lemma 10.** $P_{(0,0,0)} = \{(z_{dom}, x_{dom}, y_{dom}) | z_{dom} \geq \sqrt{x_{dom}^2 + y_{dom}^2}\}$.

**Proof.** We have $\cos(2\pi n\theta)^2 + \sin(2\pi n\theta)^2 = 1$ and $\cos(2\pi n\theta)$ is dense in $[-1, 1]$ as $\theta \notin \mathbb{Q}$. Denote $X = \cos(2\pi n\theta)$, and study the function $f(X) = x_{dom}X + y_{dom}\sqrt{1-X^2}$. Its derivative is $f'(X) = x_{dom} - \frac{y_{dom}X}{\sqrt{1-X}\sqrt{1+X}}$. We have $f'(X) = 0$ iff $X = X_0 = \frac{x_{dom}}{\sqrt{x_{dom}^2+y_{dom}^2}}$. This gives a maximum for $f(X_0) = \frac{x_{dom}^2+y_{dom}^2}{\sqrt{x_{dom}^2+y_{dom}^2}} = \sqrt{x_{dom}^2+y_{dom}^2}$. Thus, for all $(z_{dom}, x_{dom}, y_{dom})$ with $z_{dom} \geq \sqrt{x_{dom}^2+y_{dom}^2}$, we have $z_{dom} \geq \max(f(X))$ and $v_n((z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) \geq z_{dom} - f(X) \geq 0$ for all $n$. On the other hand, if $z_{dom} < \sqrt{x_{dom}^2+y_{dom}^2}$, then there exists $n$ such that $f(\cos(2\pi n\theta))$ is arbitrarily close to $\max f(X) > z_{dom}$, and in particular $v_n = z_{dom} - f(\cos(2\pi n\theta)) < 0$. ◇

We show in Appendix A.2 the following lemma which states the linear function $M_{dom}$ associated with the LRR $(v_n^{dom})_{n \in \mathbb{N}}$ is actually a rotation of angle $-2\pi\theta$.

► **Lemma 11.** $M_{dom}(z_{dom}, x_{dom}, y_{dom}) = (z_{dom}, x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$, that is $M_{dom}$ is a rotation around axis $\vec{z}$ of angle $-2\pi\theta$.
Finally, the following lemma implies that $P \subseteq P_{dom}$.

**Lemma 12.** For all $z_{res}, x_{res}, y_{res}$, we have $P_{(z_{res}, x_{res}, y_{res})} \subseteq P_{(0,0,0)}$.

**Proof.** We use the following simple but important observation. Let $(u_n)_{n \in \mathbb{N}}$ be an LRS where all roots have modulus 1, i.e., each root is of the form $\gamma = e^{i\theta}$, with distinct values of $\theta$. Let $u_j$ be the $j^{th}$ element of the LRS, with $j \in \mathbb{N}$. Then for all $\varepsilon, N$, there exists $n > N$ with $|u_n - u_j| < \varepsilon$. That is, for each value visited, the LRS will visit arbitrarily close values an infinite number of times. This is the case in particular of $v_n^{dom}$.

Now, assume for contradiction that there is a configuration $(z_{dom}, x_{dom}, y_{dom})$ in $P_{(z_{res}, x_{res}, y_{res})} \setminus P_{(0,0,0)}$. Since $(z_{dom}, x_{dom}, y_{dom}) \notin P_{(0,0,0)}$, there exists $m$ with $v_m^{dom}(z_{dom}, x_{dom}, y_{dom}) < 0$. We let $\varepsilon = \frac{|v_m^{dom}(z_{dom}, x_{dom}, y_{dom})|}{3}$ and $N$ such that for all $n > N$, $|v_n^{res}| < \varepsilon$ (because it converges towards 0 when $n$ tends towards infinity). From the above observation, we obtain an $n > N$ such that $|v_n^{dom}(z_{dom}, x_{dom}, y_{dom}) - v_m^{dom}(z_{dom}, x_{dom}, y_{dom})| < \varepsilon$. Thus:

$$v_n(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res}) < v_n^{dom}(z_{dom}, x_{dom}, y_{dom}) + v_n^{res}(z_{res}, x_{res}, y_{res}) \\ < v_m^{dom}(z_{dom}, x_{dom}, y_{dom}) + \varepsilon + \varepsilon < 0.$$

A contradiction with $(z_{res}, x_{dom}, y_{dom}) \in P_{(z_{res}, x_{res}, y_{res})}$.

<figure><img src="image_8.png" /></figure>

# 5 Proof of Theorem 8

## 5.1 Intuition for hardness of (robust) positivity

Consider a vector $\mathbf{d} = (z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res})$ on the surface of $P_{dom}$, that is, $(z_{dom}, x_{dom}, y_{dom}) \in P_{(0,0,0)}$. Consider the subset of $P_{(0,0,0)}$ which consists of points whose first coordinate $z_{dom}$ is the same as that of $\mathbf{d}$. For all $n$, let $\mathbf{e}_n$ be the point of this section where hyperplane $H_n$ is tangent to $P_{(0,0,0)}$. Let $\tau$ be the angle made between the center $b$ of the section, $\mathbf{e}_0$ and $\mathbf{d}$. Hence, $\mathbf{e}_0$ is at angle 0 and $\mathbf{e}_n$ at angle $2\pi n\theta$ mod $2\pi$. We depict this pictorially in Figure 3.

We have that $u_n(\mathbf{d}) \ge 0$ for all $n$ iff $\mathbf{d}$ is in the intersection of all half spaces defined by $H_i(z_{res}, x_{res}, y_{res})$. As $2\pi n\theta$ mod $2\pi$ is dense in $[0, 2\pi)$, for all $\beta > 0$, there is a $n$ such that $\mathbf{e}_n$ is at angle $\alpha_n \in [\tau - \beta, \tau + \beta]$, hence $H_n$ will be $\varepsilon$-close to $\mathbf{d}$. To know whether $\mathbf{d}$ is in the half space defined by $H_n(z_{res}, x_{res}, y_{res})$, we need to compare the distance $\varepsilon$ between $H_n$ and $\mathbf{d}$, with the value of $n$. If the value of $n$ is too large, then the distance between $H_n(z_{res}, x_{res}, y_{res})$ and $H_n$ is smaller than $\varepsilon$, and $\mathbf{d}$ is in the half space $H_n^+(z_{res}, x_{res}, y_{res})$.

In other words, for $(u_n(\mathbf{d}))_{n \in \mathbb{N}}$ not to be positive, $n$ needs to be both small enough and such that $2\pi n\theta$ mod $2\pi$ is close to $\tau$. This is similar to $L(\theta)$ being small, as shown in Lemma 13.

Now, for robust positivity (Theorem 8), we consider a ball $\mathcal{B}$ entirely in $P_{dom}$, tangent to the surface of $P_{dom}$ only on point $\mathbf{d}$. The ball will be positive iff the curvature of the ball is steeper than the curvature from hyperplanes $H_n(z_{res}, x_{res}, y_{res})_{n \in \mathbb{N}}$ around $\mathbf{d}$, as shown in Lemma 14. This will correspond again to computing $L(\theta)$, thus showing hardness.

## 5.2 Formalizing the proof for closed balls and robust positivity

In this section, we formalize the intuition given above, in the case of a closed ball and for robust positivity. We will extend this to the full proof of Theorem 8 in the next subsection.
5:10 On Robustness for the Skolem and Positivity Problems

<figure><img src="image_9.png" /><figcaption>Figure 3 Representation of a section of $P_{(0,0,0)}$, with hyperplanes $H_0, H_{10}$ being represented.</figcaption></figure>

We start by picking $L(\theta) = \inf(c \in \mathbb{R} \mid |\theta - \frac{k}{n}| \le \frac{c}{n^2}, k, n \in \mathbb{N} \setminus \{0\})$, i.e., $L(\theta) = \inf(c \in \mathbb{R} \mid |2\pi n\theta - 2\pi k| \le \frac{2\pi c}{n}, k, n \in \mathbb{N} \setminus \{0\})$. Denoting $L^+(\theta) = \inf(c \in \mathbb{R} \mid 2\pi n\theta \bmod 2\pi \le \frac{2\pi c}{n}, n \in \mathbb{N})$ and $L^-(\theta) = \inf(c \in \mathbb{R} \mid |-2\pi n\theta \bmod 2\pi| \le \frac{2\pi c}{n}, n \in \mathbb{N})$, we get $L(\theta) = \min(L^+(\theta), L^-(\theta))$.

We show how to $\varepsilon$-approximate $L^+(\theta)$ in the following, using an oracle for robust positivity, following ideas in [24]. To compute some $\ell$ that is $\varepsilon$-close to $L^+(\theta)$ for a given $\varepsilon > 0$, we perform a binary search on $\ell$. An old observation of Dirichlet shows that every real number has Diophantine approximation type at most 1. Further, $L(\theta) \ge 0$ by definition. So, for the binary search, we start with a lower bound $\ell_{min} = 0$ and an upper bound $\ell_{max} = 1$. For $\ell := \frac{\ell_{min}+\ell_{max}}{2}$, we want to know if $\ell \ge L^+(\theta) - \varepsilon$ (and then we set $\ell_{min} := \ell$) or whether $\ell \le L^+(\theta) + \varepsilon$ (and then we set $\ell_{max} := \ell$). Approximating $L^-(\theta)$ is done in a symmetric way, and $L(\theta)$ can be approximated accordingly.

For an interval $I$ of $\mathbb{N}$, we denote $L_I^+(\theta) = \inf(c \in \mathbb{R} \mid 2\pi n\theta \bmod 2\pi \le \frac{2\pi c}{n}, n \in I)$. For instance, we have $L_\mathbb{N}^+(\theta) = L^+(\theta)$. We will denote $> n_1$ for the interval $I = \{n_1+1, n_1+2, \dots\}$.

Let $\varepsilon > 0$ and $\ell$ be a guess to check against $L^+(\theta)$. Consider the closed ball $B_\psi^\ell$ of radius $\sqrt{2}\psi$, centered at $\mathbf{c} = (2+\psi, 2-\psi, 0, 0, 0, 2\pi\ell)$, with $\psi < \frac{1}{3}$ and $\psi < \pi\ell$. Notice that $\mathbf{d} = (2, 2, 0, 0, 0, 2\pi\ell) \in B_\psi^\ell$, on its surface, as $||\mathbf{c} - \mathbf{d}|| = \sqrt{2}\psi$. The ball $B_\psi^\ell$ is entirely in $P_{dom}$ (see Lemma 20 in Appendix A.3, which is not necessary for the rest of the proofs, it is a sanity check because of Lemma 12). Further, the surface of the ball is tangent to the surface of $P_{dom}$ in $\mathbf{d}$ as $2^2 = 4 = (2+0)^2$ satisfies the equation of Lemma 10. In other words, this the only point where the ball $B_\psi^\ell$ intersects the surface of $P_{dom}$.

We first explain the relationship between the positivity of $(u_n(\mathbf{d}))$ and $L(\theta)$, which is the crux of the proof of Theorem 6 by [24].

**Lemma 13.** *There is a computable $n_1 > 0$ such that for all $n_2 \ge n_1$, we have $(u_n(\mathbf{d}))_{n>n_2}$ positive implies $L_{>n_2}^+(\theta) > \ell - \varepsilon$ and $(u_n(\mathbf{d}))_{n>n_2}$ not positive implies $L_{>n_2}^-(\theta) < \ell + \varepsilon$.*

**Proof.** Let $\alpha_n = 2\pi n\theta \bmod 2\pi \ge 0$. Considering the Taylor development for $\alpha_n > 0$ close to 0 of $(1 - \cos(\alpha_n))$ and $\sin(\alpha_n)$, we get $u_n(\mathbf{d}) = \frac{2}{n}\alpha_n^2 - \frac{2\pi\ell\alpha_n}{n} + f(\alpha_n)$, with $f(\alpha_n) = O(\alpha_n^3)$. We have $u_n(\mathbf{d}) \le 0$ iff $\frac{2\pi\ell\alpha_n}{n}$ is larger than $\alpha_n^2(1 + \frac{f(\alpha_n)}{\alpha_n^2})$, that is iff $\alpha_n \le \frac{2\pi\ell}{n(1+\frac{f(\alpha_n)}{\alpha_n^2})}$.
There exists a value $\alpha_0 > 0$ such that $\alpha_n < \alpha_0$ implies $1 - \frac{\varepsilon}{\ell} \le \frac{1}{(1 + \frac{\ell(\alpha_n)}{\alpha_n^2})} \le 1 + \frac{\varepsilon}{\ell}$. That is, if $u_n(\mathbf{d}) \le 0$ and $\alpha_n < \alpha_0$, then $L^+(\theta) \le \ell + \varepsilon$. Let $n_0 = \lfloor \frac{\pi\ell}{1-\cos(\alpha_0)} \rfloor + 1$. As $|\sin(\alpha)| \le 1$, if $\alpha_n > \alpha_0$, then for all $n > n_0$, $u_n(\mathbf{d}) > 2(1 - \cos(\alpha_0)) - 2\pi\ell \frac{1-\cos(\alpha_0)}{\pi\ell} = 0$ is positive. We define $n_1 = \max(n_0, \lfloor \frac{2\pi(\ell-\varepsilon)}{\alpha_0} \rfloor + 1)$.

That is, if $u_n(\mathbf{d}) \le 0$ with $n > n_1$, then $n > n_0$ and $\alpha_n < \alpha_0$, and thus $L_{>n_1}^+(\theta) \le \ell + \varepsilon$.

Otherwise, for all $n > n_1$, we have $u_n(\mathbf{d})$ is positive and $2\pi n\theta \bmod 2\pi > \ell - \varepsilon$. Thus we have $L_{>n_1}^+(\theta) \ge \ell - \varepsilon$. ◀

The ball $\mathcal{B}_{\psi}^{\ell}$ is chosen to have the following crucial Lemma to approximate $L^+(\theta)$:

**Lemma 14.** If $L^+(\theta) \ge \ell + \varepsilon$, there exists an explicitly computable $\psi$ such that $u_n(\mathbf{d}') \ge 0$ for all $n > n_1$ and all $\mathbf{d}' \in \mathcal{B}_{\psi}^{\ell}$, for the $n_1$ from Lemma 13.

The proof of Lemma 14 uses Lemmas 10, 11 and the description of $H_n(z_{res}, x_{res}, y_{res})$ as parallel and at a bounded distance to $H_n$.

**Proof.** Let $\mathbf{e} = (2 + \psi + z'_{dom}, 2 - \psi + x'_{dom}, y_{dom}, z_{res}, x_{res}, 2\pi\ell + y'_{res}) \in \mathcal{B}_{\psi}^{\ell}$, and use the same notation $\lambda_1, \lambda_2, \lambda_3$ as in the proof of Lemma 20. We write $\lambda_3 = \cos(\beta)$, and we get $x'_{dom} = \sqrt{2} \cos(\beta) \lambda_2 \lambda_1 \psi$ and $y'_{dom} = \sqrt{2} \sin(\beta) \lambda_2 \lambda_1 \psi$.

Consider the Circle $C_{dom}$, section of $P_{(0,0,0)}$ over $\overrightarrow{x_{dom}}, \overrightarrow{y_{dom}}$ for $z_{dom} = 2+\psi+z'_{dom}$. It is of diameter $2+\psi+z'_{dom}$. Let $\alpha$ the angle $(\mathbf{bd}', \mathbf{be})$ with $\mathbf{b} = (2+\psi+z'_{dom}, 0, 0, z_{res}, x_{res}, 2\pi\ell+y'_{res})$ and $\mathbf{d}' = (2+\psi+z'_{dom}, 2+\psi+z'_{dom}, 0, z_{res}, x_{res}, 2\pi\ell+y'_{res})$.

Consider $r$ the distance between $\mathbf{b}$ and $\mathbf{e}$. We have $\cos(\alpha) = \frac{2-(1-\sqrt{2}\cos\beta|\lambda_2|\lambda_1)\psi}{r}$. Hence $x \ge 2 - \psi \ge 1$. We also have $\sin\alpha = \frac{\sqrt{2}|\lambda_2|\lambda_1\psi\sin\beta}{r} \le \psi$. Thus $\alpha$ is small wrt 1, and $r = \frac{2-(1-\sqrt{2}\cos\beta|\lambda_2|\lambda_1)\psi}{\cos(\alpha)} = (1+\mathcal{O}(\alpha^2))(2 - (1 - \sqrt{2}\cos\beta|\lambda_2|\lambda_1)\psi)$.

We want to know whether $\mathbf{e}$ is in $P_{(z_{res}, x_{res}, 2\pi\ell+y'_{res})}$. It is not the case iff there exists an half space $H_n^+(z_{res}, x_{res}, 2\pi\ell+y'_{res})$ such that $\mathbf{e} \notin H_n^+(z_{res}, x_{res}, 2\pi\ell+y'_{res})$. Take $n$ with $n\theta \mod 2\pi < \alpha$. As $L^+(\theta) \ge \ell + \varepsilon$, we have $n > \frac{2\pi(\ell+\varepsilon)}{\alpha} > \frac{2\pi\ell}{\alpha}$. That is, the remainder for this $\alpha$ is bounded by $\frac{\psi\sqrt{2-2\lambda_1^2}}{n} + \frac{2\pi\ell}{n} \sin\alpha < \alpha(\sin\alpha + \frac{\psi\sqrt{2-2\lambda_1^2}}{2\pi\ell})$. The diameter of the $C_{dom}$ circle is $2+\psi+z'_{dom}$. By Lemma 10 and the description of $H_n(z_{res}, x_{res}, y_{res})$ as parallel to $H_n$,

<figure><img src="image_10.png" /><figcaption>■ **Figure 4** Representation of $\mathcal{B}$ in the section over $\overrightarrow{x_{dom}}, \overrightarrow{y_{dom}}$ at height $\ell = 2+\psi+z'_{dom}$ over $\overrightarrow{z_{dom}}$.</figcaption></figure>
**5:12 On Robustness for the Skolem and Positivity Problems**

characterized by Lemma 11, and at a distance from $H_n$ which we can effectively bound for all $n \in \mathbb{N}$, we obtain that if $r$ is smaller than $2 + \psi \pm \sqrt{2\sqrt{1 - \lambda_2^2}\lambda_1\psi - \alpha(\sin\alpha + \frac{\psi\sqrt{2-2\lambda_1^2}}{2\pi\ell})}$, then $\mathbf{e}$ is in $P_{(z_{res}, x_{res}, 2\pi\ell+y'_{res})}$.

That is, we want $2+\psi\pm\sqrt{2\sqrt{1-\lambda_2^2}\lambda_1\psi-\alpha(\sin\alpha+\frac{\psi\sqrt{2-2\lambda_1^2}}{2\pi\ell})}-r = \psi(2\pm\sqrt{2\sqrt{1-\lambda_2^2}\lambda_1-\sqrt{2\cos\beta|\lambda_2|\lambda_1}-\alpha\frac{\sqrt{2-2\lambda_1^2}}{2\pi\ell}})+O(\alpha^2)>0$. Now remark that $|\sqrt{2}\sqrt{1-\lambda_2^2}\lambda_1\psi + \sqrt{2\cos\beta|\lambda_2|\lambda_1|} \le \lambda_1(\sqrt{2+2\cos^2\beta})$. And also $|\lambda_1(\sqrt{2+2\cos^2\beta}) + \alpha\frac{\psi\sqrt{2-2\lambda_1^2}}{2\pi\ell})| \le \sqrt{2+2\cos^2\beta+\alpha^2\frac{\psi^2}{\pi\ell}}$, applying twice the same reasoning as in the proof of Lemma 15.

We now prove that we have $\psi(1 - \cos^2 \beta) = \psi \sin^2 \beta$ dominates any $O(\alpha^2)$ for $\psi$ small, i.e., we prove that for any $f = O(\alpha^2)$, we have $\frac{f}{\psi(\sin^2 \beta)}$ tends to 0 as $\psi$ tends to 0. In particular, for all $\psi$ small enough, the fraction is below 1, i.e., $(\sin^2 \beta)\psi > f$. We have $(\sin^2 \beta)\psi \ge \frac{r^2 \sin^2(\alpha)}{\psi} \ge \frac{\sin^2(\alpha)}{\psi}$ as $r \in [1, 3]$. This indeed dominates any function $O(\alpha^2)$, as $\frac{\alpha}{\sin\alpha}$ is bounded in $[-\frac{\pi}{2}, \frac{\pi}{2}]$. In particular, $\sin^2 \beta > \alpha^2 \frac{\psi^2}{2\pi\ell})$ for $\psi$ small enough.

Now, we write $\sqrt{2+2\cos^2\beta+\alpha^2\frac{\psi^2}{\pi\ell}} = 2\sqrt{1-\frac{1}{2}(\sin^2\beta-\alpha^2\frac{\psi^2}{2\pi\ell})} \le 2(1-\frac{1}{4}(\sin^2\beta-\frac{1}{4}\alpha^2\frac{\psi^2}{2\pi\ell}))$ using the Taylor development of $\sqrt{1-r}$, and the fact that $(\sin^2\beta - \alpha^2\frac{\psi^2}{2\pi\ell}) > 0$ because $\psi$ is small enough. Thus, we obtain $\psi(2-2(1-\frac{1}{4}(\sin^2\beta))+O(\alpha^2)) = \frac{\psi}{4}(\sin^2\beta)+O(\alpha^2)$, which is positive for $\psi$ small enough, and $\mathbf{e}$ is in $P_{(z_{res}, x_{res}, 2\pi\ell+y'_{res})}$.

Notice that the function in $O(\alpha^2)$ is well defined and well known, and thus $\Psi$ small enough can be effectively computed. $\quad$

<figure><img src="image_11.png" /></figure>

Let us explain why these two Lemmas suffice, provided that we have an oracle for $\psi$-robust positivity, to answer either $L^+(\theta) \le \ell + \varepsilon$ or $L^+(\theta) \ge \ell - \varepsilon$, which proves Theorem 8 for robust positivity and closed balls. Intuitively, if the ball $B_\psi^\ell$ is positive, then in particular $(u_n(\mathbf{d}))$ is positive since $\mathbf{d} \in B_\psi^\ell$ and we have $L_{>n_1}^+(\theta) > \ell - \varepsilon$ by Lemma 13. Otherwise, the ball is not positive and Lemma 14 shows that $L^+(\theta) < \ell + \varepsilon$, granted that the radius of the ball is small enough.

**Proof of Theorem 8 for robust positivity and closed balls.** Let $\varepsilon > 0$. Assume that an $\ell$ has been fixed, such that we want to know either $L^+(\theta) < \ell + \varepsilon$ or $L^+(\theta) > \ell - \varepsilon$. First, we fix $\psi$ given by Lemma 14. We remark that $B_\psi^\ell$ corresponds to a ball in the coordinates $(z_{dom}, x_{dom}, y_{dom}, z_{res}, x_{res}, y_{res})$ (which are not necessarily orthonormal), not in the original coordinates $(v_0, v_1, v_2, v_3, v_4, v_5)$. Taking the transformation from the latter to the former, which is a linear operator $H$, the ball $B_\psi^\ell$ corresponds to an ovaloid $O$ in the original coordinates. We can explicitly define a ball $B' \subseteq O$ in the original coordinates, with $\mathbf{d} \in B'$. Notice that we can choose $B'$ with an arbitrarily small radius, so in particular we can choose this radius to be rational without loss of generality.

We first compute $L_{\le n_1}^+(\theta)$, which is easy as it only involves a bounded number of indices $n$. If $L_{\le n_1}^+(\theta) < \ell + \varepsilon$, then we know $L^+(\theta) \le L_{\le n_1}^+(\theta) < \ell + \varepsilon$ and we stop.

Otherwise $L_{\le n_1}^+(\theta) \ge \ell + \varepsilon$, and we check whether $u_n(\mathbf{d}') \ge 0$ for all $n > n_1$ and all $\mathbf{d}' \in B'$, using the robust positivity oracle (by starting from $M^{n_1}(v_0, \dots, v_k)$ rather than $(v_0, \dots, v_k)$). If it is positive, then in particular it is for $\mathbf{d}' = \mathbf{d}$, and applying Lemma 13, we obtain $L_{>n_1}^+(\theta) > \ell - \varepsilon$. Combined with $L_{\le n_1}^+(\theta) \ge \ell + \varepsilon$, we obtain $L^+(\theta) > \ell - \varepsilon$.

The last case means that there is $u_n(\mathbf{d}') < 0$ for some $n > n_1$ and $\mathbf{d} \in B' \subseteq B_\psi^\ell$. Applying the contrapositive of Lemma 14, we obtain that $L^+(\theta) < \ell + \varepsilon$. $\quad$
## 5.3 Case of Open Balls and robust Skolem

In this subsection, we extend the proof of Theorem 8 to show that considering open or closed balls does not make a difference for the Diophantine-hardness. Further, there is also no difference whether we consider the robust Skolem problem (0 is avoided), the robust positivity problem (negative numbers are avoided), or the robust strict positivity problem (negative and 0 are avoided).

Let $B$ be an open ball and $cl(B)$ its topological closure, which is the closed ball consisting of $B$ and its surface. Consider the following statements:

1. Robust Positivity holds for the closed ball $cl(B)$

2. Robust Positivity holds for the open ball $B$

3. Robust Strict Positivity holds for the open ball $B$

4. Robust Skolem holds for the open ball $B$

5. Robust Strict Positivity holds for the closed ball $cl(B)$

6. Robust Skolem holds for the closed ball $cl(B)$

We show that equivalence results between these statements. This allows us to conclude that having open or closed balls does not make a difference for $\mathcal{T}$-Diophantine hardness of Skolem and (strict) positivity. Formally, we have the following.

**Lemma 15.** (1), (2) and (3) are equivalent. Further, for balls $B$ containing at least one initial configuration $\mathbf{d}_0$ in its interior that is strictly positive, i.e. $u_n(\mathbf{d}_0) > 0$ for all $n$, both (3) and (4) are equivalent and (5) and (6) are equivalent.

**Proof.** (1) implying (2) is trivial. (2) implies (1): we show the contrapositive. Suppose there exists an initial configuration $\mathbf{d}$ on the surface of the ball $B$ and an integer $n$ such that $u_n(\mathbf{d}) = y < 0$. Recall that $M$ is the companion matrix, and $u_n(\mathbf{d})$ is the first component of $(M^n \cdot d)$, so $u_n(x)$ is a continuous function. Thus, there exists a neighbourhood of $\mathbf{d}$, such that for all $\mathbf{d}'$ in the neighbourhood, $u_n(\mathbf{d}') < y/2 < 0$. This neighbourhood intersects the open ball $B$ enclosed by the surface, and picking $d'$ in this intersection shows that Robust Positivity does not hold in the open ball.

(3) implying (2) is trivial. (2) implies (3): Assume for the sake of contradiction that there is an initial configuration $\mathbf{c}'$ in the open ball $B$ such that $u_n(\mathbf{c}') = 0$. Consider any open $O$ around $\mathbf{c}'$ entirely in the open ball $B$. We have that $\mathbf{c}'$ is on hyperplane $H_n$ by definition. That is, there are initial configurations in $O$ on both sides of $H_n$. In particular, there is an initial configuration $\mathbf{c}''$ in $O$, hence in $B$, with $\mathbf{c}'' \notin H_n^+$, i.e. $u_n(\mathbf{c}'') < 0$, a contradiction with $B$ being robustly positive.

(3) implies (4) is trivial. (4) implies (3): We consider the contrapositive: if we have an initial configuration $\mathbf{d}_1$ of $B$ which is not strictly positive, then $u_n(\mathbf{d}_1) \le 0$ for some $n$, and there is a barycenter $\mathbf{d}_2$ between $\mathbf{d}_0$, $\mathbf{d}_1$ which satisfies $u_n(\mathbf{d}_2) = 0$, i.e. negation of (4). To be more precise, we can choose $\mathbf{d}_2 = \frac{-u_n(\mathbf{d}_1)}{u_n(\mathbf{d}_1)-u_n(\mathbf{c})} \mathbf{d}_0 + \frac{u_n(\mathbf{d}_1)}{u_n(\mathbf{d}_1)-u_n(\mathbf{d}_0)} \mathbf{d}_1$.

Now, (5) and (6) are equivalent for balls containing at least one initial configuration $\mathbf{d}_0$ that is strictly positive in its interior (same proof as for the equivalence between (3) and (4) above). However, notice that (5,6) are not equivalent with (1,2,3,4) in general. ◀

We are now ready to prove Theorem 8 for open balls $B$. It suffices to remark that the center $\mathbf{c}$ of $B_\psi^\ell$ is strictly in the interior of $P_{dom}$, and thus it will be eventually strictly positive by Lemma 10, that is there exists $n_2 > n_1$ such that $u_n(\mathbf{c}) > 0$ for all $n > n_2$, and we can choose $\mathbf{d}_0 = \mathbf{c}$. Hence by Lemma 15, robustness (for $n > \max(n_1, n_2)$) of positivity, strict positivity and Skolem are equivalent on $\mathcal{B}$, and these are equivalent with robust positivity of $cl(\mathcal{B})$ which was proved $\mathcal{T}$-Diophantine hard in the previous section.
5:14 On Robustness for the Skolem and Positivity Problems

It remains to prove Theorem 8 for robust Skolem for closed balls B. For that, it suffices
to easily adapt Lemma 13, replacing $(u_n(\mathbf{d}))_{n>n_2}$ positive by strictly positive, and obtain the
T-Diophantine hardness for robust strict positivity of closed balls. We again apply Lemma
15 ((5) and (6) are equivalent) to obtain hardness for robust Skolem of closed balls.

6 Proof of Theorem 9

We now turn to the proof of Theorem 9, generalizing elements from Section 4.

**6.1 Intuitions for the proof of Theorem 9**

Let $(u_n)_{n \in \mathbb{N}}$ be a recurrence relation defined by coefficients $\mathbf{a} \in \mathbb{Q}^{\kappa}$. As before, we will consider $(v_n)_{n \in \mathbb{N}} = (\frac{u_n}{f_n})_{n \in \mathbb{N}}$, for $f_n$ such that the dominant coefficients of $(v_n)_{n \in \mathbb{N}}$ are of the form $\alpha e^{in\theta}$. We will then decompose the exponential solution of $(v_n)_{n \in \mathbb{N}}$ as a dominant term $(v_n^{dom})_{n \in \mathbb{N}}$ made of coefficients $\alpha e^{in\theta}$, and a residue $(v_n^{res})_{n \in \mathbb{N}}$ with $(v_n^{res})_{n \in \mathbb{N}} \xrightarrow{n \to +\infty} 0$. For an initial distribution $\mathbf{a}$, we denote by $\mathbf{a}^{dom}$ its projection on dominant space. As before, we define $P_{dom} = \{\mathbf{a} \mid \forall n, v_n^{dom}(\mathbf{a}^{dom}) \ge 0\}$.

To solve $\exists$-robust Skolem and $\exists$-robust positivity, the reasoning is based on the range of the dominant term. For $\exists$-robust Skolem, we consider the minimum *absolute value* $\nu$ of the dominant term $|v_n^{dom}(\mathbf{c}_0)|$ obtained for the center of the neighborhood $\mathbf{c}_0$.

- $\nu > 0$. Then as the residue has negligible contribution to $(v_n)_{n \in \mathbb{N}}$ for large $n$, we show that the LRS will ultimately avoid zero beyond a threshold index $n_{thr}$. Having assured ourselves of the long run behaviour, it suffices to check the value of the LRS up to $n_{thr}$, where the residue can have significant contribution, to see whether the LRS satisfies robust Skolem.

- $\nu = 0$. Then we show in Proposition 18 that the LRS does not satisfy robust Skolem: no matter how small we pick a neighbourhood around $\mathbf{c}_0$, there will always exist a $\mathbf{c}$ in that neighbourhood that hits zero at some iteration.

- Further, Proposition 17 states that $\nu$ can be computed effectively.

For robust positivity, we let $\mu$ be the minimum value of the dominant term (and not of its
absolute value). Thus, $\mu$ can take three kinds of values: $\mu > 0$ ($\mathbf{c}_0 \in P_{dom}$) and we proceed
as for $\nu > 0$; $\mu < 0$ ($\mathbf{c}_0 \notin P_{dom}$) and then there exists a $n$ such that the LRS from $\mathbf{c}_0$ is
negative; and $\mu = 0$ ($\mathbf{c}_0$ is at the surface of $P_{dom}$), and then we can show that there exists a
configuration arbitrarily close to $\mathbf{c}$ such that the LRS from that configuration is negative.

**6.2 Range of the Dominant Term**

We first define the normalized exponential polynomial solution $(v_n)_{n \in \mathbb{N}}$:

**Definition 16.** Let $(u_n)_{n \in \mathbb{N}}$ be an LRS of general term $u_n(\mathbf{c}) = \sum_{i=1}^{r} \sum_{j=0}^{m_r-1} p_{ij} n^j \gamma_i^n$, with $\rho$ being the modulus of the dominant roots and $m+1$ the maximal multiplicity of a dominant root. Define $v_n(\mathbf{c}) = \frac{u_n(\mathbf{c})}{n^m \rho^n}$ for $n > 0$, and $v_0(\mathbf{c}) = u_0(\mathbf{c})$.

We call every term of $v_n$ which converges towards 0 as $n$ tends towards infinity residual, while the other terms, of the form $\alpha e^{i\theta}$ are dominant. We denote $\{\theta_j | j = 1, \dots, k\}$ the set of $\theta$ in dominant terms, and $\alpha_j(\mathbf{c})$ the associated coefficient. We define:

$$
v_n^{dom}(\mathbf{c}) = \sum \alpha_j(\mathbf{c}) e^{in\theta_j} \quad \text{and} \quad v_n^{res}(\mathbf{c}) = v_n(\mathbf{c}) - v_n^{dom}(\mathbf{c}) = \mathcal{O}(\frac{1}{n}) \xrightarrow{n \to \infty} 0.
$$
As we explained in Section 6.1, knowing the range of $(v_n^{dom})_{n \in \mathbb{N}}$ is crucial in order to solve $\exists$-robust Skolem and positivity. In Section 4 and 5, we dealt with hardness via an example which had 3 dominant roots, and it was rather simple to determine the min/max value (computed in the proof of Lemma 10). The general case is not so easy however, because there may be relationships between the $\theta_j$ which may alter the range of $(v_n^{dom})_{n \in \mathbb{N}}$.

A tedious but now rather classical way to compute the range of $(v_n^{dom})_{n \in \mathbb{N}}$ is by invoking Masser's theorem [19] (Theorem 21 in Appendix A.4), to describe the set of tuples that can be reached (at least arbitrarily close) by $s^n = (e^{in\theta_1}, \dots, e^{in\theta_k})$ for $n \in \mathbb{N}$, as used in [23, Theorem 4]. We can describe a continuous relaxation of $\{s^n | n \in \mathbb{N}\}$ as a set $T$ of tuples $t = (t_1, \dots, t_k)$ of complex numbers with $|t_j| = 1$ for all $j$. The set $T$ is the set of linear combinations of the finite basis given by Theorem 21, which describes a Torus, independent of the initial configuration $c$. Notice that $T$ may be discrete and have finitely many points (the case where $\frac{\theta_j}{2\pi} \in \mathbb{Q}$), else, it is continuous and has uncountably many points.

We have $s^n \in T$ for all $n \in \mathbb{N}$. Further, Kronecker [11] (Theorem 22 in Appendix A.4) implies that for all $t = (t_1, \dots, t_k) \in T$ and $\varepsilon > 0$, there exists an $n$ such that $|t_j - e^{in\theta_j}| \le \varepsilon$ for all $j \le k$. For every initial configuration $c$ and element of the torus $t \in T$, we denote dominant$(c, t) = \sum_j \alpha_j(c)t_j$. Thus, for all $n$ and all $c$, we have $v_n^{dom}(c) = \text{dominant}(c, s^n)$. Conversely, for all $t \in T$, $\varepsilon > 0$, there exists $n$ with $|v_n^{dom}(c) - \text{dominant}(c, t)| \le \varepsilon$, for all $c$.

Using Renegar's result [26], one can compute effectively the range of dominant$(c, t)$ over $T$, and thus of $(v_n^{dom})_{n \in \mathbb{N}}$. A simple adaptation allows to compute the range of $|\text{dominant}(c, t)|$. In the following, we fix $c_0$ to be the center of the neighborhood and define

$$ \mu = \min_{t \in T}(\text{dominant}(c_0, t)) \quad \text{and} \quad \nu = \min_{t \in T} |\text{dominant}(c_0, t)|. $$

**Proposition 17.** $\mu$ and $\nu$ are algebraic and can be efficiently computed. Further, we have $|\mu|, |\nu| < 2^{s^{O(1)}}$ and $\frac{1}{|\mu|}, \frac{1}{|\nu|} < 2^{s^{O(1)}}$

*Proof.* The statement for $\mu$ comes directly from Renegar [26], stating that we can compute the min and max values $\mu = \min_{t \in T}(\text{dominant}(c_0, t))$ and $\mu' = \max_{t \in T}(\text{dominant}(c_0, t))$ over $t$ in the torus $T$. The statement for $\nu$ is a corollary obtained as follows:

- If $\mu > 0$ ($u_n(c_0) \ge \mu > 0$ for all $n \in \mathbb{N}$), then $\nu = \mu$ and we are done.

- If $\mu' < 0$ ($u_n(c_0) \le \mu' < 0$ for all $n$), then $\nu = -\mu'$.

- If $T$ is discrete, we enumerate the polynomially many values of $t$ (noting that they all correspond to $\lambda^{th}$ roots of unity, and Masser polynomially bounds $\lambda$) to compute $\nu$ as the minimum of the absolute values.

- Otherwise, we have $\mu < 0 < \mu'$, that is there exist two elements $t, t' \in T$ with $\text{dominant}(c_0, t) < 0 < \text{dominant}(c_0, t')$. As $x \mapsto \text{dominant}(c_0, x)$ is continuous over $T$, there is a $t'' \in T$ with $\text{dominant}(c_0, t'') = 0$, that is $\nu = 0$. $\quad \blacksquare$

We now state that if $\mu \le 0$, then $\exists$-robust positivity does not hold, while if $\nu = 0$, then $\exists$-robust Skolem does not hold.

**Proposition 18.** If $\mu \le 0$, then $\forall \varepsilon > 0$, $\exists n, c_\varepsilon$ with $|c_0 - c_\varepsilon| \le \varepsilon$ such that $v_n(c_\varepsilon) < 0$.

If $\nu = 0$, then $\forall \varepsilon > 0$, $\exists n, c_\varepsilon$ with $|c_0 - c_\varepsilon| \le \varepsilon$ such that $v_n(c_\varepsilon) = 0$.

To prove Proposition 18, we reason as follows. For every $n$, let $\text{distance}(c, H_n)$ be the distance between an initial configuration $c$ and the hyperplane $H_n = \{c' | v_n(c') = 0\} = \{c' | u_n(c') = 0\}$. If $\text{distance}(c_0, H_n) < \varepsilon$, then there exists a $c_\varepsilon$ with $|c_0 - c_\varepsilon| \le \varepsilon$ such that $v_n(c_\varepsilon) = 0$ ($\exists$-robust Skolem does not hold). It also implies the existence of a $c'_\varepsilon$ with $|c_0 - c'_\varepsilon| \le \varepsilon$ and $v_n(c'_\varepsilon) < 0$, as there will be initial configurations in the $\varepsilon$ neighborhood of $c_0$ on both sides of $H_n$, thus some will be outside of $H_n^+ = \{c' | v_n(c') \ge 0\}$, thus with $v_n(c_\varepsilon) < 0$ ($\exists$-robust positivity does not hold).
► **Lemma 19.** *There exists* $C$ *such that for all n, distance(c, $H_n$) ≤ C · $|v_n(c)|$.*

Lemma 19, proved in Appendix A.4, implies that if for all $\alpha > 0$, there exists $n_\alpha$ with $|v_{n_\alpha}(\mathbf{c})| < \alpha$, then there exists $n$ with $\text{distance}(\mathbf{c}, H_n) < \varepsilon$ (choose $n = n_\alpha$ for $\alpha = \frac{\varepsilon}{2C}$).

**Proof of Proposition 18.** Consider the first statement. If $\mu < 0$, then there exists $n$ with $|v_n^{res}(\mathbf{c}_0)| \le \frac{\mu}{2}$ as $v_n^{res}(\mathbf{c}_0) \to_{n \to \infty} 0$. Thus $v_n(\mathbf{c}_0) = v_n^{dom}(\mathbf{c}_0) + v_n^{res}(\mathbf{c}_0) < \frac{\mu}{2}$. That is, $\mathbf{c}_\varepsilon = \mathbf{c}_0$ satisfies the statement. Otherwise, $\mu = 0$. We prove that for all $\alpha > 0$, we have a $n_\alpha$ such that $|v_{n_\alpha}(\mathbf{c}_0)| \le \alpha$, which suffices by Lemma 19. Let $\alpha > 0$ arbitrarily small, and let $N$ such that for all $n > N$, $|v_n^{res}(\mathbf{c}_0)| \le \frac{\alpha}{2}$. This $N$ exists as $v_n^{res}(\mathbf{c}_0) \to_{n \to \infty} 0$. By Kronecker, as $\mu = 0$, there exists $n_\alpha > N$ with $|v_{n_\alpha}^{dom}(\mathbf{c}_0)| < \frac{\alpha}{2}$. Thus $|v_{n_\alpha}(\mathbf{c}_0)| \le |v_{n_\alpha}^{dom}(\mathbf{c}_0)| + |v_{n_\alpha}^{res}(\mathbf{c}_0)| \le \alpha$.

We now prove the second statement in the same way. Assume $\nu = 0$, and let $\varepsilon > 0$. We again prove that for all $\alpha > 0$, we have a $n_\alpha$ such that $|v_{n_\alpha}(\mathbf{c}_0)| \le \alpha$, which suffices by Lemma 19. Let $\alpha > 0$ arbitrarily small, and let $N$ such that for all $n > N$, $|v_n^{res}(\mathbf{c}_0)| \le \frac{\alpha}{2}$. This $N$ exists as $v_n^{res}(\mathbf{c}_0) \to_{n \to \infty} 0$. By Kronecker, as $\nu = 0$, there exists $n_\alpha > N$ with $|v_{n_\alpha}^{dom}(\mathbf{c}_0)| < \frac{\alpha}{2}$. Thus $|v_{n_\alpha}(\mathbf{c}_0)| \le |v_{n_\alpha}^{dom}(\mathbf{c}_0)| + |v_{n_\alpha}^{res}(\mathbf{c}_0)| \le \alpha$. ◀

## 6.3 Decidability and complexity for ∃-robust Skolem and ∃-robust positivity

We now turn to deciding ∃-robust Skolem and positivity as stated in Theorem 9, using Proposition 18. The algorithm for ∃-robust Skolem is as follows (as detailed in Algorithm 1 in Appendix A.4). First, we compute $\nu \leftarrow \min_{t \in T} |\text{dominant}(\mathbf{c}, t)|$ using Proposition 17, for $\mathbf{c}$ the initial configuration around which we are looking for a neighborhood. If $\nu = 0$, then ∃-robust Skolem does not hold. Otherwise, we compute $N$ such that $v_n^{res}(\mathbf{c}_0) < \frac{\nu}{2}$ for all $n > N$. Then we check if $v_n(\mathbf{c}_0) = 0$ for some $n \le N$. If yes, then ∃-robust Skolem does not hold, otherwise it holds. This algorithm can readily be adapted to provide an $\varepsilon > 0$ such that for all $\mathbf{c}$ with $|\mathbf{c} - \mathbf{c}_0| \le \varepsilon$, we have $u_c \ne 0$, as well as to decide robust positivity.

The correctness of the above algorithm follows from Proposition 18, because if $\nu > 0$, then for all $n > N$, $v_n(\mathbf{c}_0) > \nu - \frac{\nu}{2} \ge \frac{\nu}{2} > 0$, and this remains $> 0$ in a neighborhood of $\mathbf{c}_0$. Denoting $\nu'(\mathbf{c}) = \min_{n \le N} |v_n(\mathbf{c})|$, if $\nu'(\mathbf{c}_0) > 0$, then also $\nu'(\mathbf{c})$ for $\mathbf{c}$ in a neighborhood of $\mathbf{c}_0$.

We now argue about the complexity. Both $\mu$ and $1/\mu = 2^{s^{O(1)}}$ are bounded (Proposition 17). We thus have $n_{thr} = 2^{s^{O(1)}}$ because $v_n^{res}(\mathbf{c}_0) = O(1/n)$. This is the number of iterates we have to explicitly check, which gives the PSPACE complexity. This finally completes the proof of Theorem 9.

# 7 Conclusion

We have formulated a natural notion of robustness for the Skolem and positivity problems and shown several results: for a given neighborhood around an initial configuration $\mathbf{c}_0$, we show Diophantine-hardness for both problems. Interestingly, this is the first Diophantine-hardness result for a variant of Skolem as far as we know. This implies that for uninitialized positivity, the fact that the initial configuration $\mathbf{c}_0$ is arbitrary is crucial to decidability [28, 12], as having a fixed ball around $\mathbf{c}_0$ is not sufficient.

On the other hand, we proved decidability of ∃-robust Skolem/Positivity around an initial configuration in full generality, hence this problem is simpler. It is also more practical because in a real system, it is often impossible to determine the initial configuration with absolute accuracy. Our results can provide a precision with which it is sufficient to set the initial configuration. Beyond these results, we provided geometrical reinterpretations of Skolem/positivity, shedding a new light on this hard open problem.
References

1. Manindra Agrawal, S. Akshay, Blaise Genest, and P. S. Thiagarajan. Approximate verification of the symbolic dynamics of Markov chains. *J. ACM*, 62(1):2:1-2:34, 2015.

2. S. Akshay, Nikhil Balaji, Aniket Murhekar, Rohith Varma, and Nikhil Vyas. Near-Optimal Complexity Bounds for Fragments of the Skolem Problem. In *37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020)*, volume 154, pages 37:1-37:18, 2020.

3. S. Akshay, Nikhil Balaji, and Nikhil Vyas. Complexity of restricted variants of skolem and related problems. In Kim G. Larsen, Hans L. Bodlaender, and Jean-François Raskin, editors, *42nd International Symposium on Mathematical Foundations of Computer Science, MFCS 2017, August 21-25, 2017 - Aalborg, Denmark*, volume 83 of LIPIcs, pages 78:1-78:14. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2017.

4. S. Akshay, Blaise Genest, Bruno Karelovic, and Nikhil Vyas. On regularity of unary probabilistic automata. In *STACS'16*, pages 8:1-8:14. LIPIcs, 2016.

5. S. Akshay, Blaise Genest, and Nikhil Vyas. Distribution-based objectives for Markov Decision Processes. In *33rf Symposium on Logic in Computer Science (LICS 2018)*, volume IEEE, pages 36-45, 2018.

6. Christel Baier, Florian Funke, Simon Jantsch, Toghrul Karimov, Engel Lefaucheux, Joël Ouaknine, Amaury Pouly, David Purser, and Markus A. Whiteland. Reachability in dynamical systems with rounding. In Nitin Saxena and Sunil Simon, editors, *40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, FSTTCS 2020*, volume 182 of LIPIcs, pages 36:1-36:17, 2020.

7. S. Basu, R. Pollack, and M. F. Roy. *Algorithms in Real Algebraic Geometry*. Springer, 2nd edition, 2006.

8. Jean Berstel and Maurice Mignotte. Deux propriétés décidables des suites récurrentes linéaires. *Bulletin de la Société Mathématique de France*, 104:175-184, 1976.

9. Manuel Biscaia, David Henriques, and Paulo Mateus. Decidability of approximate Skolem problem and applications to logical verification of dynamical properties of markov chains. *ACM Trans. Comput. Logic*, 16(1), December 2014.

10. Vincent Blondel and Natacha Portier. The presence of a zero in an integer linear recurrent sequence is NP-hard to decide. *Linear algebra and its Applications*, 351:91-98, 2002.

11. N. Bourbaki. *Elements of Mathematics: General Topology (Part 2)*. Addison-Wesley, 1966.

12. Mark Braverman. Termination of integer linear programs. In *International Conference on Computer Aided Verification*, pages 372-385. Springer, 2006.

13. Ventsislav Chonev, Joël Ouaknine, and James Worrell. On the Skolem problem for continuous linear dynamical systems. In *43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)*, pages 100:1-100:13. LIPIcs, 2016.

14. H. Cohen. *A Course in Computational Algebraic Number Theory*. Springer-Verlag, 1993.

15. Julian D'Costa, Toghrul Karimov, Rupak Majumdar, Joël Ouaknine, Mahmoud Salamati, Sadegh Soudjani, and James Worrell. The pseudo-Skolem problem is decidable. In Filippo Bonchi and Simon J. Puglisi, editors, *46th International Symposium on Mathematical Foundations of Computer Science, MFCS 2021*, volume 202 of LIPIcs, pages 34:1-34:21. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021.

16. Graham Everest, Alfred J. van der Poorten, Igor E. Shparlinski, and Thomas Ward. Recurrence Sequences. In *Mathematical surveys and monographs*, 2003.

17. Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki. Skolem's problem - on the border between decidability and undecidability. Technical Report 683, Turku Centre for Computer Science, 2005.

18. Kurt Mahler. *Eine arithmetische Eigenschaft der Taylor-koeffizienten rationaler Funktionen*. Noord-Hollandsche Uitgevers Mij, 1935.

19. David W. Masser. Linear relations on algebraic groups. In *New Advances in Transcendence Theory*. Cambridge University Press, 1988.
5:18 On Robustness for the Skolem and Positivity Problems

20 M. Mignotte. Some useful bounds. In *Computer Algebra*, 1982.

21 Maurice Mignotte, Tarlok Nath Shorey, and Robert Tijdeman. The distance between terms of an algebraic recurrence sequence. *Journal für die reine und angewandte Mathematik*, 349:63–76, 1984.

22 Eike Neumann. Decision problems for linear recurrences involving arbitrary real numbers. *Logical Methods in Computer Science*, 17(3), 2021.

23 Joël Ouaknine and James Worrell. On the positivity problem for simple linear recurrence sequences. In *International Colloquium on Automata, Languages, and Programming*, pages 318–329. Springer, 2014.

24 Joël Ouaknine and James Worrell. Positivity problems for low-order linear recurrence sequences. In *Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2014, Portland, Oregon, USA, January 5-7, 2014*, pages 366–379. SIAM, 2014.

25 Joël Ouaknine and James Worrell. Ultimate positivity is decidable for simple linear recurrence sequences. In *International Colloquium on Automata, Languages, and Programming*, pages 330–341. Springer, 2014.

26 James Renegar. On the Computational Complexity and Geometry of the First-Order Theory of the Reals, Part I: Introduction. Preliminaries. The Geometry of Semi-Algebraic Sets. The Decision Problem for the Existential Theory of the Reals. *J. Symb. Comput.*, 13:255–300, 1992.

27 Thoralf Skolem. Ein Verfahren zur Behandlung gewisser exponentialer Gleichungen, 8de Skand. mat. Kongr. Forh. Stockholm, 1934.

28 Ashish Tiwari. Termination of linear programs. In *Computer-Aided Verification, CAV*, volume 3114 of LNCS, pages 70–82. Springer, July 2004.

29 Nikolai Vereshchagin. The problem of appearance of a zero in a linear recurrence sequence. *Mat. Zametki*, 38(2):609–615, 1985.

A Appendix

A.1 Regarding algebraic numbers and their bit representation

A complex number $\alpha$ is said to be algebraic if it is a root of a polynomial with integer coefficients. For an algebraic number $\alpha$, its defining polynomial $p_{\alpha}$ is the unique polynomial of least degree of $\mathbb{Z}[X]$ such that the GCD of its coefficients is 1 and $\alpha$ is one of its roots. Given a polynomial $p \in \mathbb{Z}[X]$, we denote the length of its representation size($p$), its height $H(p)$ the maximum absolute value of the coefficients of $p$ and $d(p)$ the degree of $p$. When the context is clear, we will only use $H$ and $d$.

A separation bound provided in [20] has established that for distinct roots $\alpha$ and $\beta$ of a polynomial $p \in \mathbb{Z}[x]$, $|\alpha - \beta| > \frac{\sqrt{6}}{d(d+1)/2H^d-1}$. This bound allows one to represent an algebraic number $\alpha$ as a 4-tuple $(p, a, b, r)$ where $\alpha$ is the only root of $p$ at distance $\le r$ if $a + ib$, and we denote size$\alpha$ the size of this representation, i.e., number of bits needed to write down this 4-tuple.

Further, we note that two distinct algebraic numbers $\alpha$ and $\beta$, are always roots of $p_{\alpha}p_{\beta}$, and we have that

$$ \frac{1}{|\alpha - \beta|} = 2^{(|\alpha| + |\beta|)^{\alpha}}. \qquad (1) $$

Given a polynomial $p \in \mathbb{Z}[X]$, one can compute its roots in polynomial time wrt size($p$) [7]. Since algebraic numbers form a field, given $\alpha, \beta$ two algebraic numbers, one can always compute the representations of $\alpha + \beta, \alpha\beta, \frac{1}{\alpha}, \mathrm{Re}(\alpha), \mathrm{Im}(\alpha)$ in polynomial time wrt size($\alpha$) + size($\beta$) [7, 14].
## A.2 Proofs for Section 4

**Lemma 11.** $M_{dom}(z_{dom}, x_{dom}, y_{dom}) = (z_{dom}, x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$, that is $M_{dom}$ is a rotation around axis $\vec{z}$ of angle $-2\pi\theta$.

**Proof.** We use the formulas $\cos(a+b) = \cos(a)\cos(b) - \sin(a)\sin(b)$ and $\sin(a+b) = \sin(a)\cos(b) + \cos(a)\sin(b)$.

Matrix $M_{dom}$ transforms $v_n^{dom}(z_{dom}, x_{dom}, y_{dom})$ into $v_{n+1}^{dom}(z_{dom}, x_{dom}, y_{dom})$. Using the formulas above with $a = 2\pi n\theta, b = 2\pi\theta$, we have that for all $n \ge 1$, $v_{n+1}^{dom}(z_{dom}, x_{dom}, y_{dom}) = v_n^{dom}(z_{dom}, x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$ for all $n$, and thus $M_{dom}$ transforms $(z_{dom}, x_{dom}, y_{dom})$ into $(z_{dom}, x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$.

Now, consider a point $p$ in 2D space at cartesian coordinates $(x_{dom}, y_{dom})$. Its polar coordinates are $(r, \alpha)$, with $r = \sqrt{x_{dom}^2 + y_{dom}^2}$ the distance between $(0,0)$ and $p$. Consider the point at polar coordinates $(r, \alpha - 2\pi\theta)$. Thus it is at cartesian coordinates $(r \cos(\alpha - 2\pi\theta), r \sin(\alpha - 2\pi\theta)) = (r \cos(\alpha) \cos(2\pi\theta) + r \sin(\alpha) \sin(2\pi\theta), r \sin(\alpha) \cos(2\pi\theta) - r \cos(\alpha) \sin(2\pi\theta)) = x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$. Hence the rotation of angle $-2\pi\theta$ transforms $(x_{dom}, y_{dom})$ into $(x_{dom} \cos(2\pi\theta) + y_{dom} \sin(2\pi\theta), y_{dom} \cos(2\pi\theta) - x_{dom} \sin(2\pi\theta))$. ◀

## A.3 Proofs for Section 5

We now show that $B_{\psi}^{\ell}$ is fully in $P_{dom}$, tangent to the surface of $P_{dom}$, for $\mathbf{d} = (2, 2, 0, 0, 0, 2\pi\ell)$.

**Lemma 20.** Let $\mathbf{d} = (2, 2, 0, 0, 0, 2\pi\ell)$. For all $\mathbf{d}' \neq \mathbf{d}$ with $\mathbf{d}' \in B_{\psi}^{\ell}$, we have $\mathbf{d}'$ is strictly in $P_{dom}$, ie for all $n \in \mathcal{N}(\mathbf{d}') > 0$.

**Proof.** Let $\mathbf{d}' = (2 + \psi + z'_{dom}, 2 - \psi + x'_{dom}, y_{dom}, z_{res}, x_{res}, 2\pi\ell + y'_{res}) \in B_{\psi}^{\ell} \setminus \{\mathbf{d}\}$. We now show that $\mathbf{d}'$ is strictly in $P_{dom}$, i.e. $(2 + \psi + z'_{dom}) - \sqrt{(2 - \psi + x'_{dom})^2 + y_{dom}^2} > 0$.

We have $z_{dom}^{\prime 2} + x_{dom}^{\prime 2} + y_{dom}^2 \le 2\psi^2$, and we write $z_{dom}^{\prime 2} + x_{dom}^{\prime 2} + y_{dom}^2 = 2\lambda_1^2\psi^2$, with $\lambda_1 \in [0, 1]$ and $\lambda_1 = 1$ iff $(z_{res}, x_{res}, y'_{res}) = (0, 0, 0)$. We also write $x_{dom}^{\prime 2} + y_{dom}^2 = 2\lambda_2^2\lambda_1^2\psi^2$ with $\lambda_2^2 \in [0, 1]$, i.e. $z_{dom}^{\prime 2} = 2(1 - \lambda_2^2)\lambda_1^2\psi$. We write $x_{dom}^{\prime 2} = 2\lambda_3^2\lambda_2^2\lambda_1^2\psi^2$, with $\lambda_3 \in [0, 1]$ and $\lambda_3 = 1$ iff $y_{dom} = 0$. We write $x_{dom}^{\prime} = \sqrt{2}\lambda_3\lambda_2\lambda_1\psi$ and $z_{dom}^{\prime} = \pm\sqrt{2}\sqrt{1 - \lambda_2^2}\lambda_1\psi$. That is, $\mathbf{d}$ is the configuration with $\lambda_1 = \lambda_3 = 1$ and $\lambda_2 = \frac{\sqrt{2}}{2}$.

We have $(2 - \psi + x'_{dom})^2 + y_{dom}^2 = (2 - \psi)^2 + x'_{dom}^2 + y_{dom}^2 + 2(2 - \psi)x'_{dom} = (2 - \psi)^2 + 2\lambda_2^2\lambda_1^2\psi^2 + 2\sqrt{2}(2 - \psi)\lambda_3\lambda_2\lambda_1\psi \le (2 - \psi)^2 + 2\lambda_2^2\lambda_1^2\psi^2 + 2\sqrt{2}(2 - \psi)|\lambda_2|\lambda_1\psi = (2 - \psi + \sqrt{2}|\lambda_2|\lambda_1\psi)^2$, with equality iff $\lambda_3 = 1$, ie when $y_{dom} = 0$. Given that $\psi < \frac{1}{3}$, we have $2 - \psi + \sqrt{2}|\lambda_2|\lambda_1\psi > 0$.

Thus $(2 + \psi + z'_{dom}) - \sqrt{(2 - \psi - x'_{dom})^2 + y_{dom}^2} \ge 2 + \psi \pm \sqrt{2\sqrt{1 - \lambda_2^2}\lambda_1\psi - (2 - \psi + \sqrt{2}|\lambda_2|\lambda_1\psi)^2} = 2\psi - \sqrt{2}(|\lambda_2| \pm \sqrt{1 - \lambda_2^2})\lambda_1\psi \ge 2\psi - 2\lambda_1\psi \ge 0$ as $(|\lambda_2| \pm \sqrt{1 - \lambda_2^2}) \le \sqrt{2}$, with equality iff $\lambda_2 = \pm\frac{\sqrt{2}}{2}$. That is, for all $\mathbf{d}' \in B_{\psi}^{\ell}$, $\mathbf{d}' \in P_{dom}$, and it is strictly inside whenever $\mathbf{d}' \neq \mathbf{d}$ (one can check that $\lambda_1 = \lambda_3 = 1$ and $\lambda_2 = -\frac{\sqrt{2}}{2}$ does not yield the overall equality). ◀

## A.4 Results and Proofs for Section 6

A deep result of Masser [19] shows that integer multiplicative relationships between algebraic numbers can be elicited efficiently.
**▶ Theorem 21 (Masser [19]).** Let $k$, be fixed, and let $e^{i\theta_1}, \dots, e^{i\theta_k}$ be complex algebraic numbers of unit modulus. Consider the free abelian group $L$ under addition given by $L = \{(\lambda_1, \dots, \lambda_k) \in \mathbb{Z}^k : e^{i\lambda_1\theta_1} \cdots e^{i\lambda_k\theta_k} = 1\}$. $L$ has a basis $\{\mathbf{1}_1, \dots, \mathbf{1}_p\} \subset \mathbb{Z}^k$ with $p \le k$. The basis can be computed in time polynomial and each entry in the basis vector is polynomially bounded in size($e^{i\theta_1}$), ..., size($e^{i\theta_k}$).

Kronecker theorem [11] states that each linear combination $\mathbf{t}$ of the basis given by Masser theorem can be approximated by a power $\mathbf{s}^n$ of $\mathbf{s} = (e^{i\theta_1}, \dots, e^{i\theta_k})$.

**▶ Theorem 22 (Kronecker [11]).** Let $\theta_1, \dots, \theta_k, \phi_1, \dots, \phi_k \in [0, 2\pi)$. The following two statements are equivalent:

- For any $\epsilon' > 0$, there exist $n, m_1, \dots, m_k \in \mathbb{Z}$ such that for $1 \le j \le k$ we have $|n\theta_j - \phi_j - 2m_j\pi| \le \epsilon'$

- For every tuple $(\lambda_1, \dots, \lambda_k)$ of integers such that $\sum_{j=1}^k \lambda_j \theta_j \in 2\pi\mathbb{Z}$ we have $\sum_{j=1}^k \lambda_j \phi_j \in 2\pi\mathbb{Z}$

Finally, we provide the reasoning why constant $C$ independent of $n$ exists which bounds the distance, i.e., we prove Lemma 19.

**▶ Lemma 19.** There exists $C$ such that for all $n$, $\text{distance}(\mathbf{c}, H_n) \le C \cdot |v_n(\mathbf{c})|$.

**Proof.** Let $n \in \mathbb{N}$. We have $\text{distance}(\mathbf{c}, H_n) = \frac{|u_n(\mathbf{c})|}{\|\mathbf{y}\|}$ for $\mathbf{y}$ the first row of $\mathbf{M}^n$ by basic geometry. Let $H$ be the transformation matrix between the basis of initial configurations and the basis of the exponential polynomial solution of $(u_n)_{n \in \mathbb{N}}$. Let $\mathbf{x} = (x_1, \dots, x_\kappa)$ with $x_i = n^k \rho_j^n$ so that to cover every root $\rho_j$ and multiplicities $k = 1, \dots, m_j$. We have $u_n(\mathbf{c}) = \mathbf{y} \cdot \mathbf{c} = \mathbf{x} \cdot (H \cdot \mathbf{c})$ for all initial configurations $\mathbf{c}$, i.e., $\mathbf{y} = \mathbf{x} \cdot H$. That is, there exists a constant $D > 0$ depending upon $H$ with $\|\mathbf{y}\| \ge Dn^m \rho^n$ for $\rho$ the modulus of a dominant root and $m+1$ the highest multiplicity of a root of modulus $\rho$. We obtain $\text{distance}(\mathbf{c}, H_n) \le \frac{|u_n(\mathbf{c})|}{Dn^m \rho^n} = \frac{|v_n(\mathbf{c})|}{D}$.

Finally, we provide Algorithm 1 for $\exists$-robust Skolem.

**Algorithm 1 Robust Skolem.**

**Data:** Companion matrix $\mathbf{M} \in \mathbb{Q}^{\kappa \times \kappa}$ of $(u_n)_{n \in \mathbb{N}}$ and center of ball $\mathbf{c}_0 \in \mathbb{Q}^{\kappa}$
1. $\{\gamma_j\}_j \leftarrow \text{eigenvalues of } \mathbf{M}$, $\rho \leftarrow \max_j |\gamma_j|$, $\{e^{i\theta_j}\}_{j=1}^k \leftarrow \{\gamma_i/\rho \mid |\gamma_i| = \rho\}$
2. Determine $T$ Torus obtained by applying Masser's result (Theorem 21) to $\{\theta_j\}_{j=1}^k$
3. $\nu \leftarrow \min_{t \in T} |\text{dominant}(\mathbf{c}, t)|$ (Proposition 17)
4. **if** $\nu = 0$ **then**
5. **return** NO (Proposition 18)
6. **else**
7. Compute $N$ such that $v_n^{\text{res}}(\mathbf{c}_0) < \nu/2$ for all $n > N$
8. **foreach** $n \in \{0, 1, \dots, N\}$ **do**
9. &nbsp;&nbsp;&nbsp;&nbsp;**if** $v_n(\mathbf{c}_0) = 0$ **then**
10. &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;**return** NO
11. &nbsp;&nbsp;&nbsp;&nbsp;**end**
12. **end**
13. **return** YES
14. **end**