# Computing the Density of the Positivity Set for Linear Recurrence Sequences

Edon Kelmendi  Max Planck Institute for Software SystemsGermany

(2022)

###### Abstract.

The set of indices that correspond to the positive entries of a sequence of
numbers is called its positivity set. In this paper, we study the density of
the positivity set of a given linear recurrence sequence, that is the question
of how much more frequent are the positive entries compared to the non-
positive ones. We show that one can compute this density to arbitrary
precision, as well as decide whether it is equal to zero (or one). If the
sequence is diagonalisable, we prove that its positivity set is finite if and
only if its density is zero. Lastly, arithmetic properties of densities are
treated, in particular we prove that it is decidable whether the density is a
rational number, given that the recurrence sequence has at most one pair of
dominant complex roots.

linear recurrence sequences, positivity set, density

††journalyear: 2022††copyright: acmlicensed††conference: 37th Annual ACM/IEEE
Symposium on Logic in Computer Science (LICS); August 2–5, 2022; Be’er Sheva,
Israel††booktitle: 37th Annual ACM/IEEE Symposium on Logic in Computer Science
(LICS) (LICS ’22), August 2–5, 2022, Be’er Sheva, Israel††price: 15.00††doi:
10.1145/3531130.3532399††isbn: 978-1-4503-9351-5/22/08††ccs: Theory of
computation Logic and verification

##  1\. Introduction

Linear recurrence sequences (lrs) are infinite sequences of rational numbers
$\langle u_{n}\rangle_{n\in\mathbb{N}}$, whose every entry is a linear
combination of the $k$ preceding entries. That is, a sequence that satisfies a
recurrence relation:

(1) $\displaystyle u_{n}=a_{1}u_{n-1}+\cdots+a_{k}u_{n-k},$

for all $n>k$, where $a_{1},\ldots,a_{k}$ are rationals and $a_{k}\neq 0$. The
constants $a_{1},\ldots,a_{k}$, and $u_{1},\ldots,u_{k}$ uniquely identify the
sequence.

Firmly grounded as one of the fundamental families of finitely represented
number sequences, they are ubiquitous in mathematics and computer science;
their importance is evident. A basic object of study in modern number theory,
they appear in the investigation of pseudo-random number generators, in
cellular automata, as solutions of some Diophantine equations, as the number
of $\mathbb{F}_{q}$-points on varieties, to name just a few examples.
Furthermore, they are intrinsically related to linear dynamical systems, and
the field of dynamical systems as a whole.

From another point of view, a linear recurrence sequence can be seen as a kind
of restricted Turing machine, namely one that has a single loop inside which
the variables are updated by a linear function. As such programs permeate any
larger piece of software, verifying their correctness has become increasingly
important in recent years. This motivation has driven further interest in
algorithmic questions regarding these sequences.

This field has been a rather active area of research in the past few decades —
a considerable body of work has amassed. The wide-scoped monograph (recseq) by
Everest, van der Poorten, Shparlinski, and Ward is a place where one can find
central results, their applications, as well as a taste of techniques that
have proven useful. Here we recount only a brief summary of the theorems that
are directly relevant to the present work.

We start with a basic question: What does the zero set of a linear recurrence
sequence $\\{n\ :\ u_{n}=0\\}$ look like? The wonderfully simple answer,
provided in 1934 by Thoralf Skolem (skolem1934verfahren) using $p$-adic
analysis, is that the zero set of a linear recurrence sequence is a finite
union of arithmetic progressions and a finite set. In other words, the zero
set is ultimately periodic. This theorem was soon after generalised to
sequences of algebraic numbers by Mahler (mahler1935arithmetische), and then
later on by Lech, to sequences of members of any ring of characteristic zero
(lech1953note). An elementary proof of Skolem’s theorem can be found in
(hansel1985simple), see also the discussion in Chapter 2.1 of (recseq).
Unfortunately, even though we know the form of zero sets, we do not know how
to decide if it is empty. Every known proof of this result uses, in some way
or other, $p$-adic analysis, resulting in a non-constructive argument. The
question of whether one can decide if there exists some $n$, such that
$u_{n}=0$, known as Skolem’s problem, remains to this day, the central open
problem for lrs.

However, there are some partial results for sequences of low order111The order
of the sequence is the smallest $k$ for which the sequence satisfies a
recurrence like (1).: With the help of Baker’s theorem for linear forms in
logarithms of algebraic numbers, Mignotte, Shorey, and Tijdeman
(84_distan_between_terms_algeb_recur_sequen, Theorem 2), and in parallel
Vereshchagin (vereshchagin, Theorem 4), proved that for sequences of order at
most four, one can decide whether their zero set is empty. In the direction of
hardness, Skolem’s problem is known to be NP-hard
(blondel02_presen_zero_integ_linear_recur).

One can raise the same questions about the positivity set $\\{n\ :\
u_{n}>0\\}$. This set, however, unlike the zero set, does not admit a clean
description. In fact the positivity problem (is there some $n$ such that
$u_{n}>0$) is more general than the Skolem problem. That is, there is a
polynomial reduction from Skolem’s problem to the positivity problem (with a
quadratic increase in the order). The positivity problem is known to be
decidable for lrs of order at most five
(ouaknine13_posit_probl_low_order_linear_recur_sequen), where Baker’s theorem
plays a crucial role again. In the direction of hardness, a decision procedure
for the positivity problem for lrs of order six would allow one to compute the
homogeneous Diophantine approximation type of a large class of transcendental
numbers (ouaknine13_posit_probl_low_order_linear_recur_sequen, Theorem 5.2).
Which suggests that such a procedure must come hand-in-hand with a deeper
understanding — than hitherto exists — of Diophantine approximations of
transcendental numbers.

Questions of asymptotic nature seem to be slightly more approachable. For
example, one can decide if a sequence has infinitely many zeros
(berstel76_deux_des_suites, Theorem 2). The corresponding problem for the
positivity set, i.e. are there infinitely many $n$, for which $u_{n}>0$ is not
known to be decidable, however. This problem is called the ultimate positivity
problem222Ultimate positivity is the question: “is it true that after some
point every entry of the sequence is positive?”. If we ignore the zeros,
ultimate positivity does not hold if and only if the negativity set is
infinite, or the positivity set of $\langle-u_{n}\rangle_{n\in\mathbb{N}}$ is
infinite.. In fact, as for positivity, a similar link to Diophantine
approximations exists (ouaknine13_posit_probl_low_order_linear_recur_sequen,
Theorem 5.1). Nevertheless, there is an important positive result: namely that
the ultimate positivity problem is decidable for _diagonalisable_ lrs
(ouaknine14_ultim_posit_decid_simpl_linear_recur_sequen). A sequence is
diagonalisable if its characteristic polynomial, which for a sequence that
satisfies (1) is

(2) $\displaystyle x^{k}-a_{1}x^{k-1}-\cdots-a_{k-1}x-a_{k},$

has no repeated roots. In fact, it is possible to go much further for
diagonalisable sequences (almagor2021deciding): One can decide any asymptotic
$\omega$-regular property, even when the property itself is part of the input.
For example, one can ask whether the sign pattern “-+-” occurs infinitely
often in the sequence.

For the general case not much progress has been made however, it remains a
long standing, difficult, open problem to decide anything about the positivity
set of a general lrs, in particular whether this set is empty, or whether it
is finite. In the present paper, we prove that it is possible to decide some
things about another notion of size of a subset of naturals: its _density_.

Recall that the density of a set $S\subseteq\mathbb{N}$ is

$\displaystyle\lim_{n\to\infty}\frac{\lvert\\{1,2,\ldots,n\\}\cap
S\rvert}{n},$

where the vertical bars denote cardinality (note that the limit need not
exist). The density is a notion used to measures how _large_ an infinite
subset of natural numbers is.

###### Example 1.1.

Here is a trivial lrs: $u_{1}=1$ and $u_{n}=-u_{n-1}$. Clearly its positivity
set are the odd numbers, and its density is equal to $1/2$.

###### Example 1.2.

It is possible to construct linear recurrence sequences that are equal to
$\cos(n\theta)$, $n\in\mathbb{N}$. If $\theta$ is a rational multiple of
$\pi$, the positivity set of these sequences will have some rational density,
if however $\theta$ is not a rational multiple of $\pi$ then, we will later
see, that the density is equal to $1/2$.

The density of the positivity set of any linear recurrence sequence always
exists. This fact was proved by Bell and Gerhold
(bell05_posit_set_recur_sequen, Theorem 1), and is our principal starting
point. With the exception of the paper above, to the best of our knowledge
there is no other work that deals with the density of the positivity set. The
paper (berstel76_deux_des_suites) can however be interpreted as providing an
algorithm to compute the density of the zero set.

We now describe the results of this paper. The first one is of a qualitative
nature:

######  Theorem 1.3.

There is a procedure that inputs a lrs and decides whether the density of its
positivity set is equal to 1.

The same procedure can be used to decide whether the density is equal to 0,
after a trivial pre-processing step.

Bell and Gerhold have observed, by using a uniformity theorem in Cassels’s
book (cassels59_introd_to_dioph_approx), that the density is equal to the
Lebesgue measure of a certain set. We proceed along the same path and go
further by constructing this set, for which it is necessary to explicitly
describe the multiplicative relations among the roots of the polynomial (2).
Afterwards, the problem is reduced to checking the emptiness of a
semialgebraic set, which can be done using the decidability of the theory of
real closed fields, i.e. Tarski’s algorithm. These tools have been
successfully employed by Ouaknine, Worrell, and others on a number of related
problems, it is not surprising that they prove useful to bear on the problems
of this paper as well.

The procedure in Theorem 1.3 runs in pspace, but when the order of the
sequence is fixed, the complexity drops to ptime.

Although we do not yet know how to decide whether the sequence has infinitely
many positive entries, we can decide whether there are _many_ of them, in the
sense of having non-zero density, using Theorem 1.3. Another point of view is
that the question “is the density 0?” over-approximates the question “is the
positivity set finite?”, because a positive answer to the latter implies the
same for the former. However, for the family of diagonalisable sequences, the
implication becomes an equivalence — the two questions are the same:

######  Theorem 1.4.

In a diagonalisable sequence the positivity set is finite if and only if its
density is zero.

Theorem 1.3 and Theorem 1.4 together imply the main theorem of
(ouaknine14_ultim_posit_decid_simpl_linear_recur_sequen), that ultimate
positivity is decidable for diagonalisable lrs. However the proof has the same
ingredients, in particular a result on the growth of lrs by Evertse, van der
Poorten and Schlickewei, which is based on a lower bound for sums of
$S$-units, itself based on the deep “subspace theorem” of Schmidt.

The main theorem of this paper says that we can compute densities to arbitrary
precision:

######  Theorem 1.5.

There is a procedure that inputs a lrs $\langle u_{n}\rangle_{n\in\mathbb{N}}$
and a rational number $\epsilon\in\mathbb{Q}$, and computes some
$\delta^{\prime}$, such that $|\delta-\delta^{\prime}|<\epsilon$, where
$\delta$ is the density of the positivity set of $\langle
u_{n}\rangle_{n\in\mathbb{N}}$.

The complexity is the same as for the density 1 problem; the problem is in
pspace in the input and $\lceil\epsilon^{-1}\rceil$, but it drops to
polynomial time when the order of the sequence is fixed.

The idea of the proof of Theorem 1.5 is straightforward. We have to
approximate the Lebesgue measure of a certain subset of the $d$-dimensional
unit cube. To this end, we draw a grid of $N^{d}$ points and count how many of
these points fall in the set. It then remains to prove that we can decide
whether a given rational point is a member of the set, and to upper bound the
error term. For the latter we use a result of Koiran (koiranil_approx). We
note that it is possible, instead of testing for every point whether it
belongs to the set, to test it for fewer points that are picked randomly,
resulting in a faster Monte-Carlo type algorithm.

Let us give a simple example that illustrates some of the ideas behind the
theorems above.

###### Example 1.6.

Consider the following simple program:

x=0; y=6; z=4;

while  _true_ do

x=4x+3y;

y=4y-3x;

z=5z;

if  _y+z¿0_ then

Region A

else

Region B

end if

end while

It is not immediately evident from looking at this program that, for example,
Region A is entered infinitely often. The algorithm from Theorem 1.5 can be
used to conclude not only Region A is entered infinitely often, but that it is
entered with frequency:

$\displaystyle 0.732279\ldots=\frac{\cos^{-1}(-2/3)}{\pi}.$

At first sight, it might seem strange to see notions related to circles and
triangles such as $\pi$ and $\cos$ appearing in the answer of a simple
question about a simple program, but the reality is that only through them can
we understand the program above. Let us explain the answer in more detail. The
value of $y+z$ in the $n$-th iteration of the loop is clearly equal to

$\displaystyle\begin{pmatrix}0&6&4\end{pmatrix}\cdot\begin{pmatrix}4&-3&0\\\
3&4&0\\\ 0&0&5\end{pmatrix}^{n}\cdot\begin{pmatrix}0\\\ 1\\\ 1\end{pmatrix}.$

Multiplying this quantity with $5^{-n}$ will not change its sign and we see
that after the multiplication, the update matrix is a rotation in the first
two coordinates:

$\displaystyle\begin{pmatrix}4/5&-3/5&0\\\ 3/5&4/5&0\\\
0&0&1\end{pmatrix}^{n}=\begin{pmatrix}\cos n\phi&-\sin n\phi&0\\\ \sin
n\phi&\cos n\phi&0\\\ 0&0&1\end{pmatrix},$

where the angle $\phi$ is $\cos^{-1}(4/5)$. Multiplying this matrix with the
row vector and the column vector above, we see that the variable $y+z$ in the
$n$-th iteration of the loop has the same sign as $6\cos(n\phi)+4$. So now the
question: with what frequency does the loop enter Region A? has been reduced
to the question: for how many $n$ is $\cos(n\phi)>-2/3$? When the angle $\phi$
is not a rational multiple of $\pi$ (which is the case here), by Weyl’s
equidistribution theorem, $n\phi$ is uniformly recurrent modulo $\pi$, meaning
that for any interval $I$ in $[0,\pi]$, the frequency with which
$n\phi\mod\pi$ enters $I$ is proportional to the size of $I$ (that is length
of the interval divided by $\pi$). As a consequence, since $\cos(n\phi)>-2/3$
if and only if $n\phi$ modulo $\pi$ belongs to the interval
$[0,\cos^{-1}(-2/3)]$, the answer follows.

Example 1.6 and Example 1.2 show that density can be both a rational and an
irrational quantity. Therefore, the algorithm in Theorem 1.5 cannot _a priori_
be used to decide quantitative questions, such as whether the density is
larger than some given rational. We give a partial result in this direction
but leave the general case open:

######  Theorem 1.7.

There is a procedure that inputs a lrs that has at most one pair of dominant
complex roots, and decides whether the density of its positivity set is
rational, and if it is, computes it exactly.

We also prove that when there are no (non-trivial) multiplicative relations
among the dominant roots, the density is a _period_ , as defined by Kontsevich
and Zagier (kontsevich01_period). We note that conjectures by Kontsevich and
Zagier, and of Grothendieck predict the transcendence degree of field
extensions of $\mathbb{Q}$ generated by a finite set of intervals, but we do
not pursue this conjectural direction further.

The rest of this paper is organised as follows. Section 2 contains the
principal definitions and generalities. Section 3 is a technical section where
we define a strong non-degeneracy condition and split the sequence into
subsequences that satisfy it, as a pre-processing step for the algorithms that
follow. Section 4 deals with the density 1 problem, as well as the analysis
for diagonalisable sequences. In the section that follows we give the
procedure to compute the density. In the end, in Section 6, we give the proof
of Theorem 1.7, deciding when the density is a rational number.

##  2\. Sequences and Densities

A sequence $\langle u_{n}\rangle_{n\in\mathbb{N}}$ that satisfies a recurrence
relation (1) for all $n>k$, but does not satisfy any linear recurrence with
fewer terms, is called a lrs of order $k$. The characteristic polynomial of
such sequence is the polynomial (2), whose roots are, say

$\displaystyle\Lambda_{1},\Lambda_{2},\ldots,\Lambda_{l},$

assumed to be distinct, with respective multiplicities $m_{1}\ldots,m_{l}$,
where $1\leq l\leq k$. The sequence $\langle u_{n}\rangle_{n\in\mathbb{N}}$
can be written as a generalised power sum (see (recseq, Section 1.1.6)):

(3) $\displaystyle u_{n}=\sum_{i=1}^{l}f_{i}(n)\ \Lambda_{i}^{n},$

where the polynomials $f_{i}$ have algebraic coefficients,
$f_{i}\in\overline{\mathbb{Q}}[x]$, and the degree of $f_{i}$ is $m_{i}-1$.
The converse also holds, any sequence $\langle u_{n}\rangle_{n\in\mathbb{N}}$
that can be written in the form (3) is a lrs over algebraic numbers. The
sequences whose roots all have multiplicity 1, i.e. there are no repeated
roots, are called diagonalisable (or simple) sequences.

A lrs is given by the numbers $a_{1},\ldots,a_{k}$ and $u_{1},\ldots,u_{k}$.
From which, it is possible to compute descriptions of the constants in (3) in
polynomial time in the bitlength of the input. By a description of an
algebraic number we mean333There are other encodings of an algebraic number
$\alpha$. Mostly one uses the fact that a number field $\mathbb{Q}(\alpha)$ is
a vector space of finite dimension. For our purposes however, it is more
convenient to define algebraic numbers by first-order formulas over the reals
(defined below). a first-order formula that defines it, typically this is the
number’s minimal polynomial together with intervals specifying where its real
and imaginary parts lie. To compute the descriptions of the roots, one runs a
root isolation algorithm on the characteristic polynomial (to compute the
approximating intervals), see for example (yap11) and (06_real_roots).
Afterwards, for the computation of polynomials $f_{i}$, one solves a system of
linear equations of polynomial size in the input. All this can be done in
polynomial time. As a consequence, we assume that we have computed the
descriptions every constant in (3), and that the roots are ordered by their
modulus, i.e.

$\displaystyle|\Lambda_{i}|\geq|\Lambda_{i+1}|.$

Density (also referred to as natural density, or asymptotic density in the
literature) is a notion that measures how large a subset
$S\subseteq\mathbb{N}$ of natural numbers is. It is defined as:

(4) $\displaystyle\mathcal{D}(S)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\lim_{n\to\infty}\frac{\lvert\\{1,2,\ldots,n\\}\cap S\rvert}{n},$

where by the vertical bars we denote the cardinality of the set. Not every set
has a density; the limit might not exist. However they do have lower and upper
density, which are defined by replacing limit with $\liminf$ and $\limsup$
respectively.

###### Example 2.1.

Here is the density of some simple subsets of natural numbers.

  1. (1)

An (infinite) arithmetic progression, with common differences $d$, has density
$1/d$. If the set $S\subseteq\mathbb{N}$ is such that the difference between
consecutive elements of $S$ is at most $d$, then the lower density of $S$ is
larger than $1/d$.

  2. (2)

The squares $\\{n^{2}\ :\ n\in\mathbb{N}\\}$ have density zero. To prove this,
it suffices to observe that the cardinality of the squares in
$\\{1,2,\ldots,n\\}$ is $O(\sqrt{n})$.

  3. (3)

The primes have density zero due to the prime number theorem.

The principal object of study in this paper is the density of the positivity
set:

$\displaystyle\mathcal{D}\left(\\{n\ :\ u_{n}>0\\}\right)$

of a given lrs $\langle u_{n}\rangle_{n\in\mathbb{N}}$. Bell and Gerhold
proved that it always exists:

######  Theorem 2.2 ((bell05_posit_set_recur_sequen, Theorem 1)).

The positivity set of any linear recurrence sequence has a density.

The negativity set is just the positivity set of the sequence $\langle-
u_{n}\rangle_{n\in\mathbb{N}}$ (which is plain, from (3) and the discussion
above, that it can be computed). Therefore in the rest of this paper, we only
deal with the density of the positivity set, which is simply referred to as
the density of the sequence.

We will make ample use of procedures for deciding the first-order theory of
real closed fields, proved by Tarski (tarski1951decision). In this logic the
atomic formulas are

$\displaystyle f(x_{1},\ldots,x_{n})\geq 0,$

where $f\in\mathbb{Z}[x_{1},\ldots,x_{n}]$ is a polynomial with integer
coefficients. The atomic formulas can be connected with Boolean connectives,
and one is allowed to quantify over real numbers. Subsets of $\mathbb{R}^{n}$
defined by such formulas are called semialgebraic sets. In the paper cited
above, Tarski proved that there exists a procedure that inputs a first-order
formula and decides whether it is true when interpreted over the reals.

We can also interpret such formulas over the complex numbers instead of the
reals, using the embedding of $\mathbb{C}^{n}$ to $\mathbb{R}^{2n}$, handling
the real and imaginary parts individually.

Note that our definition of descriptions of algebraic numbers is a simple
formula in Tarski’s logic. Other formulas that we will construct will be
equally simple in the following sense: they will belong to the existential
fragment, i.e. formulas of the type

$\displaystyle\exists x_{1}\exists x_{2}\cdots\exists
x_{n}\qquad\Phi(x_{1},\ldots,x_{n}),$

where $\Phi$ is quantifier-free. The complexity of this fragment is relatively
low:

######  Theorem 2.3 ((Canny_1988, Theorem 3.3) and (renegar1992computational,
Theorem 1.1), respectively).

The existential theory of reals is decidable in pspace. When the number of
variables is fixed, the complexity drops to ptime 444The ptime upper bound
holds for the full logic, when the number of variables is fixed..

The theorems above expect the polynomials in the input to be written as a
sequence of coefficients, each encoded in binary. Hence the exponents are
assumed to be encoded in unary.

##  3\. Strongly Non-Degenerate Subsequences

Let $P\in\mathbb{N}$, and consider subsequences of the form:

(5) $\displaystyle\left\\{\langle u_{nP+\ell}\rangle_{n\in\mathbb{N}}\ :\
0\leq\ell<P\right\\}.$

Each one is itself a lrs ((recseq, Theorem 1.3)). One can easily observe this
fact from the equality (3): the roots of the subsequence are $\Lambda_{i}^{P}$
and the polynomials $f_{i}(nP+\ell)$ are multiplied by the constant
$\Lambda_{i}^{\ell}$.

The purpose of this section is a crucial preprocessing step that splits the
sequence into subsequences (5), for a particular $P\in\mathbb{N}$, which we
will compute. The subsequences have a number of properties (enumerated in a
lemma at the end of the section) that make them more amenable. Effectively
dividing the initial problem into easier sub-problems, we can recombine
answers of the sub-problems to get answers for the initial problem. For
example, if we know the densities of the $P$ subsequences, then the density of
the original sequence is equal to their sum divided by $P$. Or for the density
1 problem: the original sequence has density 1 if and only if all the
subsequences have density 1.

In our case the period $P$ is a product:

$\displaystyle P\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}P_{1}\cdot P_{2},$

where $P_{1}$ comes from degeneracy, and $P_{2}$ from multiplicative relations
among the roots. Let $N$ be the bitlength of the input and $k$ the order of
the sequence, later in this section we will prove that $P$ will have the upper
bound:

(6) $\displaystyle P\in 2^{\mathcal{O}(k^{5}\log\log N)}.$

Before we give the definitions of the periods $P_{1}$ and $P_{2}$, let us
first discuss the description of the roots $\Lambda_{i}^{P}$, as this is
important for the complexity upper bounds when $P$ is large. Let
$r\in\mathbb{N}$, and let $z\in\overline{\mathbb{Q}}$ be an algebraic number
with description $\phi(x)$ (i.e. the formula $\phi(x)$ holds if and only if
$x=z$). There are two ways to describe the number $z^{r}$:

  1. (1)

The _trivial way_ : saying that there exists some $x$ such that $\phi(x)$ and

$\displaystyle y=\underbrace{x\cdot x\cdots x}_{r\text{ times}}.$

Resulting in a constant increase on the number of variables, and a linear
increase in $r$ on the size of the formula.

  2. (2)

The _repeated squaring way_ : saying that there exist a roughly $s:=\log r$
number of variables $x_{1},\ldots,x_{s}$ such that

$\displaystyle\phi(x_{1})\text{ and }y=x_{s}\text{ and }x_{i+1}=x_{i}\cdot
x_{i},\,1\leq i\leq s.$

Resulting in a $\log r$ increase in both the number of variables and the size
of the formula.

We will use both methods, depending on which complexity bound we want to
derive.

######  Proposition 3.1.

For a given constant $P$, bounded by (6), the description of any
$\Lambda_{i}^{P}$ can be computed in polynomial time. Furthermore, such a
description grows both in the number of variables and in size by a term in
$\mathcal{O}(k^{5}\log\log N)$.

When the order of the sequence is fixed, the size of the description grows by
a term in $\mathcal{O}(\log N)$ while the number of variables by a constant.

###### Proof.

Using the repeated squaring method results in a formula that grows both in
size and in the number of variables by a $\log P$ term, hence the first
statement of the proposition.

When $k$, the order of the sequence is fixed however, it makes more sense to
use the trivial way of constructing the formula, because this will result in a
constant increase in the number of variables, and a linear in $P$ increase in
the size of the formula. Since for fixed $k$, $P$ is in $\mathcal{O}(\log N)$
the second statement of the proposition follows. ∎

Now we define $P_{1}$ and $P_{2}$, as well as show how to compute them. In the
end of this section we summarise the properties that every subsequence
$\langle u_{nP+\ell}\rangle_{n\in\mathbb{N}}$ has.

###  3.1. Period $P_{1}$

We begin with the standard notion of degeneracy. A lrs is said to be
degenerate if it has two distinct roots $\Lambda_{i}$ and $\Lambda_{j}$, whose
ratio $\Lambda_{i}/\Lambda_{j}$ is a root of unity. One can test in ptime
whether a given sequence is degenerate by checking whether any of its ratios
of distinct roots satisfies a cyclotomic polynomial of appropriate degree.
Consult Section 3 in (yokoyama95_findin). If the sequence is degenerate,
taking the least common multiple of all the orders of roots of unity that can
occur in this way, we get a quantity $P_{1}$, such that all the subsequences
with period $P_{1}$ are either identically zero, or non-degenerate. The
quantity $P_{1}$ is upper bounded only by the order of the sequence:

######  Theorem 3.2 ((recseq, Theorem 1.2)).

Let $\langle u_{n}\rangle_{n\in\mathbb{N}}$ be a lrs of order $k$. Then there
is a constant

$\displaystyle M_{k}\in 2^{\mathcal{O}(k\sqrt{\log k})},$

such that for some $P_{1}\leq M_{k}$, each subsequence

$\displaystyle\langle u_{nP_{1}+\ell}\rangle_{n\in\mathbb{N}},$

$0\leq\ell<P_{1}$ is either identically zero, or is non-degenerate.

###  3.2. Period $P_{2}$

The definition of $P_{2}$ requires a little bit more work. We have assumed
that the roots are ordered by their modulus:
$|\Lambda_{i}|\geq|\Lambda_{i+1}|$, suppose that the first $j$ ones are
dominant, i.e.,

$\displaystyle|\Lambda_{1}|=\cdots=|\Lambda_{j}|>|\Lambda_{j+1}|.$

Let $d$ be the maximal degree of the polynomials $f_{1},\ldots,f_{j}$ from
(3), and suppose, without loss of generality, that it is exactly the
polynomials $f_{1},\ldots,f_{m}$ that are of degree $d$, for some $m\leq j$.
Define the normalised roots:

$\displaystyle\lambda_{i}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{\Lambda_{i}^{P_{1}}}{\left|\Lambda_{i}^{P_{1}}\right|}\qquad
1\leq i\leq m.$

We are interested in the multiplicative relations:

$\displaystyle\mathcal{M}(\lambda_{1},\ldots,\lambda_{m})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{\vec{r}\in\mathbb{Z}^{m}\ :\
\lambda_{1}^{r_{1}}\lambda_{2}^{r_{2}}\cdots\lambda_{m}^{r_{m}}=1\\}.$

This set with addition forms a subgroup of $\mathbb{Z}^{m}$. Since the latter
is a free abelian group with a basis of $m$ elements, by (lang02_algeb,
Theorem 7.3, Chapter I) the subgroup $\mathcal{M}$ is a free abelian group
with some basis

(7) $\displaystyle\vec{b}_{1},\ldots,\vec{b}_{v}\in\mathbb{Z}^{m},$

where $v\leq m$. Define

(8) $\displaystyle P_{2}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}2\prod_{1\leq s\leq v\atop{1\leq t\leq m}}|b_{s,t}|.$

######  Lemma 3.3.

The integer $P_{2}$ is effective. It can be computed in pspace. When the order
of the sequence is fixed, the computation can be performed in ptime.

###### Proof.

We argue that we can compute the basis (7) and hence also $P_{2}$.

It follows from (poorten77_multip_relat_number_field, Theorem 1), that there
is an effective upper bound on the absolute value of the coordinates of the
basis (7) of size:

$\displaystyle 2^{\mathcal{O}(k^{2})}\prod_{i=2}^{m}\log H(\lambda_{i}),$

where $H$ is the Mahler measure, defined as follows. For an algebraic number
$z\in\overline{\mathbb{Q}}$, with minimal polynomial

$\displaystyle
a_{0}x^{d}+a_{1}x^{d-1}+\cdots+a_{d}=a_{0}(x-z_{1})\cdots(x-z_{d}),$

we say that its Mahler measure is:

$\displaystyle H(z)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}|a_{0}|\prod_{i=1}^{d}\max\\{1,|z_{i}|\\}\leq\sqrt{d}\max_{0\leq
i\leq d}|a_{i}|,$

where the upper bound comes from (poorten77_multip_relat_number_field, Lemma
1). Using the fact that for any algebraic number $z\in\overline{\mathbb{Q}}$
and $r\in\mathbb{N}$, $H(z^{r})=H(z)^{r}$, whose proof can be found in
(waldschmidt00_dioph_approx_linear_algeb_group, Chapter 3), via a
straightforward computation, we can derive the following upper bound:

(9) $\displaystyle\max_{1\leq s\leq v\atop{1\leq t\leq m}}|b_{s,t}|\in
2^{\mathcal{O}(k^{3}\log\log N)},$

where $k$ is the order of the sequence and $N$ is the bitlength of the input.
For any $\vec{b}\in\mathbb{Z}^{m}$ with the same upper bound, the assertion

$\displaystyle\vec{b}\in\mathcal{M}(\lambda_{1},\ldots,\lambda_{m}),$

is an existential first-order formula of polynomial size in $N$, due to
Proposition 3.1. Which means that by brute force, we can compute a basis (7)
in pspace by using the algorithm from Theorem 2.3. When the order $k$ is
fixed, the number of variables is constant. As a consequence of the second
statement of Theorem 2.3, in this scenario, the basis can be computed in
ptime. ∎

From the definition of $P_{2}$, (8), the estimate (9) and Theorem 3.2 one can
derive the upper bound (6).

###  3.3. Properties of the Subsequences

Let $0\leq\ell<P$, we list a number of properties of the subsequence

(10) $\displaystyle\langle u_{nP+\ell}\rangle_{n\in\mathbb{N}},$

which we assume is not identically zero. We start by replacing the dependent
roots as follows.

The only case when the group $\mathcal{M}(\lambda_{1},\ldots,\lambda_{m})$ is
trivial is when $m=1$, which implies that $\lambda_{1}=1$, because complex
roots come as conjugate pairs (of the same multiplicity), and being a
conjugate pair is a multiplicative relation. In this case, every problem that
we treat becomes trivial. Therefore suppose that $m>1$. Then there exists some
member of the basis (7) — say $\vec{b}_{1}$ without loss of generality — that
has at least two non-zero coordinates. By definition,

$\displaystyle\lambda_{1}^{b_{1,1}}\cdots\lambda_{m}^{b_{1,m}}=1.$

Suppose that $b_{1,m}\neq 0$. By using Euler’s formula we see that we can
write:

(11)
$\displaystyle\lambda_{m}=\varrho\lambda_{1}^{-b_{1,1}/b_{1,m}}\cdots\lambda_{m-1}^{-b_{1,m-1}/b_{1,m}},$

where $\varrho$ is a $b_{1,m}$-th root of unity (and hence also a $P_{2}$-th
root of unity, by definition of $P_{2}$), and at least one of the exponents
$b_{1,1},\ldots,b_{1,m-1}$ is nonzero. Replacing $\lambda_{m}$ in the other
equations, and continuing in this manner, making at most $v$ replacements, one
for every member of the basis, we conclude that the set of indices
$\\{1,\ldots,m\\}$ can be partitioned into the indices corresponding to the
independent roots and depended roots of the form (11), more precisely it can
be partitioned into subsets:

  * •

$I$ \- a non-empty subset, with independent $\lambda_{i}$, i.e. that do not
have multiplicative relations among themselves,

  * •

$D$ \- a subset with dependent $\lambda_{i}$, i.e. those that can be written
in the form (11), where in the right-hand side only members of $I$ appear, and
there is a factor $\varrho$ which is a $P_{2}$-th root of unity (perhaps not
primitive)555Here we see the reason behind the definition of $P_{2}$: In
subsequences with the period $P_{2}$ we can directly write the dependent roots
as a function of the independent ones; the factor $\varrho$ disappears because
it is a $P_{2}$-th root of unity., and

  * •

$U$ \- an empty set or a singleton containing some $i$ for which
$\lambda_{i}=1$.

The reason why $U$ has cardinality at most $1$ is as follows. By the process
described above, we cannot obtain more than one equation of the type
$\lambda_{i}^{r}=1$, because among $\lambda_{1},\ldots,\lambda_{m}$, the only
root of unity that can appear is the number $1$. Indeed, if there were some
complex $\lambda_{i}$ that is $r$-th root of unity, then its complex conjugate
$\overline{\lambda_{i}}$ will also appear among the dominant roots
$\lambda_{1},\ldots,\lambda_{m}$ (with the same multiplicity), and
$(\lambda_{i}/\overline{\lambda_{i}})^{r}=\lambda_{i}^{2r}=1$, meaning that
the sequences $\langle u_{nP_{1}+\ell}\rangle_{n\in\mathbb{N}}$ are
degenerate, a contradiction of Theorem 3.2.

Rearrange the the roots $\lambda_{i}$ such that for some $\eta$

$\displaystyle I=\\{1,\ldots,\eta\\},\qquad D=\\{\eta+1,\ldots,m-1\\},\qquad
U=\\{m\\}.$

The case when $D$ or $U$ is empty is omitted, as it can be treated in
essentially the same way. It is convenient to define for all $i$, $1\leq i\leq
m$:

$\displaystyle\alpha_{i}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\lambda_{i}^{P_{2}}=\frac{\Lambda_{i}^{P}}{|\Lambda_{i}^{P}|},$

and the rationals $q_{i,j}\in\mathbb{Q}$, $i\in D$, $j\in I$, such that:

$\displaystyle\alpha_{i}=\prod_{j\in I}\alpha_{j}^{q_{i,j}}.$

The generalised power sum form of the sequence (10) is:

$\displaystyle
u_{nP+\ell}=\sum_{i=1}^{l}\Lambda_{i}^{\ell}f_{i}(nP+\ell)(\Lambda_{i}^{P})^{n}.$

Dividing by $n^{d}|\Lambda_{1}^{P}|^{n}$ does not change the sign, where $d$
is the largest degree of polynomials multiplying the dominant roots. We get
the sequence:

(12) $\displaystyle v_{n}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\sum_{i=1}^{m}c_{i}\alpha_{i}^{n}+R(n)$ $\displaystyle=\sum_{i\in
I}c_{i}\alpha_{i}^{n}+\sum_{i\in D}c_{i}\prod_{j\in
I}\alpha_{j}^{q_{i,j}}+c_{m}+R(n),$

where $c_{i}\in\overline{\mathbb{Q}}$, and $R(n)$ is some residue that tends
to zero exponentially, i.e.

(13) $\displaystyle|R(n)|\in\mathcal{O}(\xi^{n}),\text{ for some $0<\xi<1$}.$

Furthermore there are no multiplicative relations among the roots
$\alpha_{i}$, for $i\in I$, that is:

(14)
$\displaystyle\mathcal{M}(\alpha_{1},\ldots,\alpha_{\eta})=\\{\vec{0}\\}.$

A non-degenerate lrs whose signs are the same as some sequence that can be
written like $v_{n}$ above is what we call strongly non-degenerate. We
summarise the properties of subsequences $\langle
u_{nP+\ell}\rangle_{n\in\mathbb{N}}$.

######  Lemma 3.4.

For any $\ell$, $0\leq\ell<P$, the following statements are true for the
sequence $\langle u_{nP+\ell}\rangle_{n\in\mathbb{N}}$ that is not identically
zero:

  1. (1)

is non-degenerate,

  2. (2)

has finitely many zeros,

  3. (3)

its entries have the same sign as the entries of $\langle
v_{n}\rangle_{n\in\mathbb{N}}$ defined in (12),

  4. (4)

the description of the algebraic numbers $c_{i}$, $\alpha_{i}$, and $q_{i,j}$
are of polynomial size, have polynomial many variables, and can be computed in
pspace,

  5. (5)

when the order of the sequence is fixed, the descriptions of the numbers above
are of polynomial size, with a constant number of variables, and can be
computed in ptime.

###### Proof.

Property 1 comes from the fact that $P_{1}$ divides $P$ and Theorem 3.2. Any
non-degenerate sequence that is not identically zero has finitely many zeros
(recseq, Section 2.1), hence Property 2. The third property holds because we
have obtained the sequence $\langle v_{n}\rangle_{n\in\mathbb{N}}$ by dividing
with positive numbers.

To see that Property 4 holds for the roots $\alpha_{i}$, first observe that
$P$ can be computed in pspace, as a consequence of Lemma 3.3, and the
discussion in Section 3.1. Then applying Proposition 3.1 gives the wanted
conclusion. A similar argument holds for the constants $c_{i}$. As for the
rationals $q_{i,j}$, a combination of two facts is used. First, note that in
the proof of Lemma 3.3 the basis (7) is being computed in pspace. Second, in
the procedure that computes these rationals, described above, we do at most
$v^{2}$ many replacements where $v\leq m$ is the size of the basis. Each such
replacement can be done in ptime.

One can do a similar analysis for the case where the order of the sequence is
fixed, resulting in Property 5. ∎

##  4\. The Density 1 Problem

In this section we prove that it is decidable whether the density of a given
sequence is equal to $0$. The procedure expects a strongly non-degenerate
sequence as input, i.e. a sequence of the form in (12) with the properties
that are listed in Lemma 3.4. Suppose that we are given such a sequence and
let $\delta$ be its density.

Note that the density of the _negativity_ set of the sequence (which is the
same as the density of $\langle-v_{n}\rangle_{n\in\mathbb{N}}$) is equal to
$1-\delta$, because the zeros $\langle v_{n}\rangle_{n\in\mathbb{N}}$ do not
affect the density, being finitely many; a consequence of Property 2 in Lemma
3.4. Hence the density of the sequence $\langle v_{n}\rangle_{n\in\mathbb{N}}$
is $0$ if and only if the density of $\langle-v_{n}\rangle_{n\in\mathbb{N}}$
is $1$. Thus the two problems, “is the density 1?” and “is the density 0?” are
inter-reducible.

The argument for decidability of the density 0 problem is as follows. We
define two open and measurable sets $\mathcal{P}$ and $\mathcal{Q}$ such that

(15)
$\displaystyle\mathcal{P}=\emptyset\qquad\Leftrightarrow\qquad\mathcal{Q}=\emptyset,$

and furthermore

(16) $\displaystyle\mathcal{Q}\text{ is
semialgebraic}\qquad\text{and}\qquad\delta=\mu(\mathcal{P}),$

where $\mu$ denotes the Lebesgue measure. Being open sets, it follows that
$\delta>0$ if and only if the semialgebraic set $\mathcal{Q}$ is nonempty,
which can be decided, in particular because of Theorem 2.3. In this way
decidability of the density 1 problem, i.e. Theorem 1.3, will follow from (15)
and (16), as well as the reduction from the density 1 to the density 0
problem.

We proceed with the definitions of the sets $\mathcal{P}$ and $\mathcal{Q}$.
Let $\mathbb{T}$ be the unit circle, i.e. the set of complex numbers
$z\in\mathbb{C}$, for which $|z|=1$. Define the auxiliary functions $F$ and
$G$ which are $v_{n}-R(n)$ but the roots $\alpha_{i}$ are replaced by
variables; more precisely $F$ is a map from $[0,1]^{\eta}$ to the reals, and
$G$ a map from $\mathbb{T}^{\eta}$ to the reals, defined as:

$\displaystyle F(\vec{\varphi})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\sum_{i=1}^{\eta}c_{i}\exp(2\pi\mathbf{i}\
\varphi_{i})+\sum_{i=\eta+1}^{m-1}c_{i}\exp\left(2\pi\mathbf{i}\sum_{j=1}^{\eta}q_{i,j}\varphi_{j}\right)+c_{m},$
$\displaystyle G(\vec{z})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\sum_{i=1}^{\eta}c_{i}z_{i}\qquad\ \ \ \ \ \ \ \
+\sum_{i=\eta+1}^{m-1}c_{i}\prod_{j=1}^{\eta}z_{i}^{q_{i,j}}\qquad\qquad\ \ \
\ +c_{m}.$

Now the sets $\mathcal{P}$ and $\mathcal{Q}$ are defined as:

$\displaystyle\mathcal{P}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{\vec{\varphi}\in[0,1]^{\eta}\ :\ F(\vec{\varphi})>0\\},$
$\displaystyle\mathcal{Q}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{\vec{z}\in\mathbb{T}^{\eta}\ \ \ \ \ \ \ :\ G(\vec{z})>0\\}.$

As one can obtain $\mathcal{P}$ by applying $\log z/2\pi\mathbf{i}$ component-
wise to elements of $\mathcal{Q}$, it is plain that $\mathcal{P}$ is non-empty
if and only if $\mathcal{Q}$ is non-empty. Since $\mathcal{P}$ is open, it has
non-zero measure if and only if it is non-empty. Furthermore, $\mathcal{Q}$ is
semialgebraic, thus it only remains to show that $\delta=\mu(\mathcal{P})$.

The proof follows closely the proof of the main theorem of
(bell05_posit_set_recur_sequen), and is crucially based on the following
theorem of Cassels, a higher-dimensional version of Weyl’s equidistribution
theorem.

######  Theorem 4.1 ((cassels59_introd_to_dioph_approx, Theorem 1, page 64)).

Let $\theta_{1},\ldots,\theta_{k},1\in\mathbb{R}$ be linearly independent over
$\mathbb{Q}$, and $S\subseteq[0,1]^{k}$ a measurable set, then

$\displaystyle\mathcal{D}\big{(}\\{n\ :\ (n\theta_{1}\ \ \mathrm{mod}\ \
1,\ldots,n\theta_{k}\ \ \mathrm{mod}\ \ 1)\in S\\}\big{)}=\mu(S).$

It says that the fractional parts of $n\vec{\theta}$ fall in the set $S$ with
frequency that is equal to the measure of the set $S$, in other words they are
uniformly distributed in the $k$-dimensional cube.

For $i\in\\{1,\ldots,\eta\\}$, define the arguments of the roots:

$\displaystyle\theta_{i}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{\log\alpha_{i}}{2\pi\mathbf{i}}\in[0,1].$

Since there are no multiplicative relations among the
$\alpha_{1},\ldots,\alpha_{\eta}$, from (14), we have that
$\theta_{1},\ldots,\theta_{\eta},1$ are linearly independent over
$\mathbb{Q}$. To see this, write $\alpha_{i}=\exp(2\pi\mathbf{i}\theta_{i})$
and observe that there are no multiplicative relations among the $\alpha_{i}$
if and only if there is no linear combination over $\mathbb{Q}$ of
$\theta_{i}$ that is equal to an integer. As a consequence, we note that
Theorem 4.1 is applicable to the tuple $\theta_{1},\ldots,\theta_{\eta}$.

The proof of $\delta=\mu(\mathcal{P})$ is preceded by two lemmas. The first
one says that the set of points that $F$ maps to $0$ has measure $0$.

######  Lemma 4.2.

$\mu\big{(}\\{\vec{\varphi}\ :\ F(\vec{\varphi})=0\\}\big{)}=0.$

###### Proof.

Since any generalised power sum is a lrs over $\overline{\mathbb{Q}}$ (recseq,
Section 1.1.6), the sequence

$\displaystyle\langle F(n\vec{\theta})\rangle_{n\in\mathbb{N}}=\langle
v_{n}-R(n)\rangle_{n\in\mathbb{N}}$

is a non-degenerate lrs. As a corollary of the Skolem-Mahler-Lech theorem
(recseq, Section 2.1), this sequence has finitely many zeros, so

$\displaystyle\mathcal{D}\big{(}\\{n\ :\ F(n\vec{\theta})=0\\}\big{)}=0.$

As noted above, we can apply Theorem 4.1 to $\vec{\theta}$, which implies

$\displaystyle\mathcal{D}\big{(}\\{n\ :\
F(n\vec{\theta})=0\\}\big{)}=\mu\big{(}\\{\vec{\varphi}\ :\
F(\vec{\varphi})=0\\}\big{)},$

where the set on the right-hand side is clearly measurable. Combining these
two equations yields the statement of the lemma. ∎

This lemma can be proved without appealing to the Skolem-Mahler-Lech theorem,
by directly showing that the set that is being measured has empty interior.

The second lemma says that the indices in which the residue $R(n)$ is larger
in absolute value than the dominating terms of the sequence, have upper
density $0$. This means that it is only the dominant part that plays any role
on the density $\delta$. Denote by $\hat{\mathcal{D}}$ the upper density (same
as density except that the limit is replaced by $\limsup$): for all
$S\subset\mathbb{N}$,

$\displaystyle\hat{\mathcal{D}}(S)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\limsup_{n\to\infty}\frac{\lvert\\{1,2,\ldots,n\\}\cap S\rvert}{n}.$

######  Lemma 4.3.

$\hat{\mathcal{D}}\big{(}\\{n\ :\ |F(n\vec{\theta})|<|R(n)|\\}\big{)}=0$.

###### Proof.

For $\epsilon>0$, define:

$\displaystyle\mathcal{P}_{\epsilon}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{\vec{\varphi}\in[0,1]^{\eta}\ :\
|F(\vec{\varphi})|\leq\epsilon\\},$ $\displaystyle\mathcal{R}_{\epsilon}$
$\displaystyle\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{n\in\mathbb{N}\qquad\ :\ |F(n\vec{\theta})|\leq\epsilon\\}.$

The residue $|R(n)|$ tends to zero as $n$ gets larger (13), hence for all
$\epsilon>0$,

(17) $\displaystyle\hat{\mathcal{D}}\big{(}\\{n\ :\
|F(n\vec{\theta})|<|R(n)|\\}\big{)}\leq\mathcal{D}(\mathcal{R}_{\epsilon}).$

The set $\mathcal{R}_{\epsilon}$ has density as a consequence of Theorem 4.1,
also

$\displaystyle\mathcal{D}(\mathcal{R}_{\epsilon})=\mu(\mathcal{P}_{\epsilon})=\int_{[0,1]^{\eta}}\mathds{1}_{\mathcal{P}_{\epsilon}}d\mu,$

where by $\mathds{1}_{\mathcal{P}_{\epsilon}}$ we have denoted the indicator
function of the set $\mathcal{P}_{\epsilon}$. Almost everywhere the function
$\mathds{1}_{\mathcal{P}_{\epsilon}}$ tends to $\mathds{1}_{\mathcal{P}_{0}}$
as $\epsilon\to 0$, hence by Lebesgue’s dominated convergence theorem
(billingsleyprob, Theorem 16.4) we have

$\displaystyle\int_{[0,1]^{\eta}}\mathds{1}_{\mathcal{P}_{\epsilon}}d\mu\to\int_{[0,1]^{\eta}}\mathds{1}_{\mathcal{P}_{0}}d\mu=0,$

where the equality to zero comes from Lemma 4.2. Since (17) holds for all
$\epsilon>0$, the statement of the lemma follows. ∎

A consequence of Lemma 4.3 is that,

$\displaystyle\delta=\mathcal{D}\big{(}\\{n\ :\
v_{n}>0\\}\big{)}=\mathcal{D}\big{(}\\{n\ :\ F(n\vec{\theta})>0\\}\big{)}.$

The density on the right-hand side is equal to $\mu(\mathcal{P})$ by again
applying Theorem 4.1.

Thus we have proved Theorem 1.3, that it is possible to decide whether the
density is equal to 0 (or to 1). The complexity of the procedure is in pspace:
the formula for non-emptiness of $\mathcal{Q}$ is of polynomial size due to
Property 4 of Lemma 3.4, and hence whether it is true can be decided in
pspace, Theorem 2.3.

The procedure runs in ptime if the order of the sequence is fixed. This
follows from Property 5 of Lemma 3.4 and Theorem 2.3.

###  4.1. The Case of Diagonalisable Sequences

If the given lrs has only finitely many positive entries then the density of
the sequence is $0$. The converse, however, does not always hold, as it can be
seen from the following example:

###### Example 4.4.

One can construct an lrs $\langle w_{n}\rangle_{n\in\mathbb{N}}$ that is equal
to

$\displaystyle w_{n}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\frac{n}{2}\lambda^{n}+\frac{n}{2}\overline{\lambda}^{n}+(1-n),$

where $\lambda\in\mathbb{T}$ is some algebraic number in the unit circle, that
is not a root of unity. Let $\theta=\log\lambda/2\pi\mathbf{i}$. Then, by
writing $\lambda^{n}=\cos(2\pi n\theta)+\mathbf{i}\sin(2\pi n\theta)$, we see
that

$\displaystyle w_{n}>0\qquad\Leftrightarrow\qquad\cos(2\pi
n\theta)>1-\frac{1}{n}.$

The sequence $\langle w_{n}\rangle_{n\in\mathbb{N}}$ has infinitely many
positive entries (almagor2021deciding, Proposition 4.1), however it has
density $0$. Indeed if it had density $\delta>0$, then we could have chosen
some $n$ large enough such that the interval of $\varphi$ for which
$\cos(2\pi\mathbf{i}\ \varphi)>1-1/n$, is smaller than $\delta$, at which
point, by applying Theorem 4.1 one can derive a contradiction. The Cassels’s
theorem is applicable because $\lambda$ is not a root of unity, which means
that $\theta$ is irrational, by definition.

The direction “density 0” implies “positivity set is finite”, does however
hold for an important class of lrs, namely the diagonalisable sequences. These
are sequences $\langle t_{n}\rangle_{n\in\mathbb{N}}$ whose characteristic
polynomial has no repeated roots, as a consequence of which, its generalised
power sum is of the following form:

$\displaystyle t_{n}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\sum_{i=1}^{k}a_{i}\Lambda_{i}^{n},$

where $a_{i}$ are some algebraic constants and $\Lambda_{i}$ are the roots.

######  Theorem 1.4.

In a diagonalisable sequence the positivity set is finite if and only if its
density is zero.

###### Proof.

We prove the contrapositive, i.e. we show that if $\langle
t_{n}\rangle_{n\in\mathbb{N}}$ has infinitely many positive entries then it
also has positive density. Assume that the roots are ordered by modulus, i.e.
$|\Lambda_{i}|\geq|\Lambda_{i+1}|$, and assume that the first $j$ roots have
maximal modulus. Write

$\displaystyle
t_{n}=\underbrace{\sum_{i=1}^{j}a_{i}\Lambda_{i}^{n}}_{D(n)}+\underbrace{\sum_{i=j+1}^{k}a_{i}\Lambda_{i}^{n}}_{r(n)}.$

Suppose that $|\Lambda_{1}|>1$, indeed if it is not, we can always multiply
the sequence with $\langle K^{n}\rangle_{n\in\mathbb{N}}$ for $K\in\mathbb{N}$
large enough, without changing the sign. Without loss of generality, we can
also assume that the sequence is non-degenerate.

The proof hinges on a lower bound on the growth of lrs that was proved
Evertse, and in parallel by van der Poorten and Schlickewei, using the
subspace theorem. See the discussion in (recseq, Section 2.4) as well as the
appendix of (fuchs20_growt_linear_recur_funct_field). Applying this theorem to
our case, we have that for all $\epsilon>0$ there exists some threshold
$n_{0}\in\mathbb{N}$ such that:

$\displaystyle|D(n)|\geq|\Lambda_{1}|^{(1-\epsilon)n}\text{ for all $n\geq
n_{0}$}.$

Since $|r(n)|$ can be upper bounded by some $c|\Lambda|^{n}$, with
$c\in\mathbb{R}$ a constant, and $|\Lambda|<|\Lambda_{1}|$, it follows that we
can pick some $\epsilon>0$ for which we know that there exists some
$n_{0}\in\mathbb{N}$ such that:

$\displaystyle|D(n)|>|r(n)|\text{ for all $n\geq n_{0}$}.$

This is a stronger version of Lemma 4.3, signifying that asymptotically the
sign depends only on that of the dominant terms666This inequality holds for
general lrs. The difference is that for diagonalisable lrs, the dominant part
$D(n)$ is easier to analyse.. As a consequence of the inequality above, since
the sequence $\langle t_{n}\rangle_{n\in\mathbb{N}}$ has infinitely many
positive terms, so does the sequence $\langle D(n)\rangle_{n\in\mathbb{N}}$.

We sketch the rest of the proof. As in Section 3 we can define the
multiplicative relations among $\Lambda_{1},\ldots,\Lambda_{j}$, and define a
set $\mathcal{P}^{\prime}$ analogous to the set $\mathcal{P}$, defined in the
previous page. One can then prove that the set $\mathcal{P}^{\prime}$ is open
and furthermore it is non-empty as a consequence of the fact that $\langle
D(n)\rangle_{n\in\mathbb{N}}$ has infinitely many positive entries. Non-
emptiness implies that $\mathcal{P}^{\prime}$ has non-zero measure, and
finally, by applying Theorem 4.1, one concludes that the density of the
sequence is positive. ∎

The algorithm that we have presented in this section is not the same, but it
is quite similar to the algorithm of
(ouaknine14_ultim_posit_decid_simpl_linear_recur_sequen) for deciding ultimate
positivity for diagonalisable sequences. We have shown that this algorithm can
be used for deciding a different problem, namely whether the density of the
sequence is zero, and that when the sequence is diagonalisable, the density 0
question is equivalent to the question of whether the sequence has only
finitely many positive entries. The complexity lower bound of
(ouaknine14_ultim_posit_decid_simpl_linear_recur_sequen, Section 5) applies to
our case as well.

##  5\. Computing the Density

One method of approximating the density $\delta$, which is the same as
approximating the volume $\mu(\mathcal{P})$ of the set $\mathcal{P}$ is
conceptually simple: draw a grid and count the points that belong to
$\mathcal{P}$. We summarise this in the picture below.

From the grid of $M^{\eta}$ points (in the example $9^{2}$ points), we count
how many are in $\mathcal{P}$, and denote this number by $C(M)$ (in the
example this is equal to 11 red points). Since $\mathcal{P}$ is a measurable
subset of the unit cube,

$\displaystyle\frac{C(M)}{M^{\eta}}\to\mu(\mathcal{P}),$

as $M$ tends to infinity.

For this scheme to work, we need to be able to do two things. First, for any
rational $\vec{q}\in[0,1]^{\eta}$, to be able to decide whether
$\vec{q}\in\mathcal{P}$. And second, to upper bound

(18) $\displaystyle\left|\frac{C(M)}{M^{\eta}}-\mu(\mathcal{P})\right|,$

by a function in $M$. We prove that both are feasible.

######  Lemma 5.1.

Given any rational $\vec{q}\in[0,1]^{\eta}$, it is decidable whether
$\vec{q}\in\mathcal{P}$.

###### Proof.

Let $0\leq k/n\leq 1$ be a rational number. The complex number
$\exp(2\pi\mathbf{i}/n)$ is a primitive $n$-th root of unity, which we can
isolate as a root of $x^{n}-1$. It follows that
$\exp(2\pi\mathbf{i}k/n)=\exp(2\pi\mathbf{i}/n)^{k}$ is an algebraic number
that we can easily define. Consequently the assertion $\vec{q}\in\mathcal{P}$,
which is equivalent to $F(\vec{q})>0$, is a first-order formula whose truth
can be decided by Tarski’s algorithm, Theorem 2.3. ∎

For an upper bound on the error (18), we use the work of Koiran
(koiranil_approx, Theorem 3). To introduce his theorem we need to define the
parameter $\kappa(\mathcal{P})$ first, and estimate it.

Let $S\subseteq[0,1]^{\eta}$ be a measurable set, define $\kappa(S)$ to be the
maximal number of connected components of the intersection $L\cap S$ where $L$
is an axis-parallel line. In other words, draw a line parallel to any one of
the axes, and count how many times it goes in and out of the set. To estimate
$\kappa(\mathcal{P})$, in our case, this translates to fixing all but one
parameter of function $F$ and counting how many times it will change its sign.
More precisely, consider the function that we get by fixing all but one
parameter of $F$, it will be of the form:

$\displaystyle H(\varphi)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}z_{0}\exp(2\pi\mathbf{i}\
\varphi)+\sum_{i=1}^{\ell}z_{i}\exp(2\pi\mathbf{i}\ r_{i}\varphi)+c,$

defined for $\varphi\in[0,1]$, where $\ell\leq m$, $c$,$z_{i}$ are some
algebraic numbers, and $r_{i}$ are taken among the $q_{i,j}$, $\eta<i<m$,
$1\leq j\leq\eta$. The nature of the constants is such that $H$ is a real-
valued function. How many times does $H$ change its sign in its domain
$[0,1]$? By continuity, the answer is upper bounded by the number of zeros of
$H$, which we will estimate. To this end, let $r_{i}=a_{i}/b_{i}$, for co-
prime integers $a_{i},b_{i}$, and define

$\displaystyle b\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\mathrm{lcm}\\{b_{1},\ldots,b_{\ell}\\}.$

Set $a^{\prime}_{i}\in\mathbb{N}$ to be such that $r_{i}=a_{i}^{\prime}/b$.

######  Lemma 5.2.

The function $H$ has at most

$\displaystyle\hat{q}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\max\\{b,a^{\prime}_{1},\ldots,a^{\prime}_{\ell}\\}$

zeros in the unit interval $[0,1]$.

###### Proof.

We can write $H$ as

$\displaystyle z_{0}\left(\exp(2\pi\mathbf{i}\
\varphi/b)\right)^{b}+\sum_{i=1}^{\ell}z_{i}\left(\exp(2\pi\mathbf{i}\
\varphi/b)\right)^{a^{\prime}_{i}}+c,$

which is a polynomial of degree at most $\hat{q}$, and hence can have at most
that many zeros. ∎

Having estimated thus the parameter $\kappa(\mathcal{P})$, we have the
following upper bound on the error:

######  Theorem 5.3 ((koiranil_approx, Theorem 3)).

For all $M\in\mathbb{N}$,

$\displaystyle\left|\frac{C(M)}{M^{\eta}}-\mu(\mathcal{P})\right|\leq\frac{\eta\kappa(\mathcal{P})}{M}\leq\frac{\eta\hat{q}}{M}.$

Now Theorem 1.5 follows from Lemma 5.1 and Theorem 5.3. Indeed if we want to
compute the density $\delta$ up to precision $\epsilon$, it suffices to choose
$M\geq\eta\hat{q}/\epsilon$, then for every member of

(19)
$\displaystyle\left\\{\left(\frac{k_{1}}{M},\ldots,\frac{k_{\eta}}{M}\right)\
:\ 0\leq k_{i}\leq M,1\leq i\leq\eta\right\\},$

test whether it is in $\mathcal{P}$, and in this way compute the quantity
$C(M)/M^{\eta}$ which by the proposition above is guaranteed to differ from
the density by no more than $\epsilon$.

Even though $M$ is exponential in the input, by using the repeated squaring
way of expressing the exponents in the formulas, as in Section 3, it is
possible to construct formulas of polynomial size for testing whether points
of the grid (19) belong to $\mathcal{P}$. In particular to define
$\exp(2\pi\mathbf{i}/M)$, the formula says that it is a root of $x^{M}-1$
(which is of polynomial size), and that both the real and imaginary parts are
positive and minimal. It follows that the algorithm for approximating the
density is making exponentially many calls to a pspace algorithm (due to
Theorem 2.3), each of which is used to decide whether to increment a counter
that is upper bounded by $M^{\eta}$. Hence this algorithm is running in pspace
on $\lceil\epsilon^{-1}\rceil$ and $N$, the bitlength of the description of
the sequence. A similar analysis yields a ptime upper bound in $N$ and
$\lceil\epsilon^{-1}\rceil$ when the order of the sequence is fixed.

Instead of testing whether _every_ point in the grid belongs to $\mathcal{P}$,
intuitively, we could test it for a smaller number $M^{\prime}<M$, but choose
the points uniformly at random. This is the Monte-Carlo integration method
(koiranil_approx). It results in a number of points in the set
$C^{\prime}(M^{\prime})$ for which it is known that for all $\epsilon>0$,

$\displaystyle\frac{1}{M^{\eta}}\left|C^{\prime}(M^{\prime})-C(M)\right|\leq\epsilon$

holds with probability at least $1-2e^{-2M^{\prime}\epsilon^{2}}$. This can be
demonstrated using Hoeffding’s inequality.

##  6\. When is the Density a Rational Number?

We have proved that it is possible to decide whether the density of a given
sequence is equal to 0, or to 1. Can we also decide whether the density is
larger than some $q\in\mathbb{Q}$? The approximating scheme of the previous
section is _a priori_ of no help: since it might be the case that it outputs
the estimates $\delta_{1},\delta_{2},\ldots$, for error bounds
$\epsilon_{1}>\epsilon_{2}>\cdots$ such that $q$ belongs to all intervals
$(\delta_{i}-\epsilon_{i},\delta_{i}+\epsilon_{i})$. A natural approach to
tackling this difficulty is to ask whether the density itself is an irrational
number. If the density is irrational then it has some $\epsilon$-neighbourhood
which does not contain $q$, which means that for a sufficiently small
$\epsilon_{i}$, $q$ does not belong in the interval
$(\delta_{i}-\epsilon_{i},\delta_{i}+\epsilon_{i})$.

In this section we report some progress of this direction. We begin by showing
that when there are no non-trivial multiplicative relations among the roots,
density is a _period_ as defined by Kontsevich and Zagier
(kontsevich01_period), i.e. an integral of an algebraic function over a
semialgebraic set. Afterwards, we prove that when there is at most one pair of
dominant complex roots, it is decidable whether the density is rational, in
which case we can compute it exactly.

###  6.1. Density as a Period

The complex roots of a sequence $u_{n}=\sum f_{i}(n)\Lambda_{i}^{n}$ come in
conjugate pairs. Furthermore if $\Lambda_{j}=\overline{\Lambda_{i}}$ then also
$f_{j}(n)=\overline{f_{i}(n)}$. See (halava2005skolem, Proposition 2.13) for a
proof. The multiplicative relations due to complex conjugacy, i.e.
$\lambda_{j}\lambda_{i}=1$, where $\lambda_{i}=\Lambda_{i}/|\Lambda_{i}|$ is
the normalised root, we call trivial relations. Here we study sequences that
do not have any non-trivial multiplicative relations among the roots. Under
this restriction, the function $F$, defined in Section 4, has the following
form:

$\displaystyle F(\vec{\varphi})=\sum_{i=1}^{\eta}c_{i}\exp(2\pi\mathbf{i}\
\varphi_{i})+\sum_{i=1}^{\eta}\overline{c_{i}}\exp(-2\pi\mathbf{i}\
\varphi_{i})+c_{m},$

since the only dependent roots are the complex conjugates of the independent
ones. Using Euler’s formula, and a trigonometric identity, we see that this
function can also be written as:

$\displaystyle
F(\vec{\varphi})=c+\sum_{i=1}^{\eta}r_{i}\cos\left(2\pi(\varphi_{i}+\tau_{i})\right),$

where $c=c_{m}\in\mathbb{R}$, $r_{i}=|c_{i}|$, and $\tau_{i}$ is the argument
of $c_{i}$.

We proceed by getting rid of the translation by $\tau_{i}$. Define:

$\displaystyle
F^{\prime}(\vec{\varphi})\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}F(\vec{\varphi}-\vec{\tau}).$

Recall that $\mathcal{P}$ was defined as the set of $\vec{\varphi}$ for which
$F(\vec{\varphi})>0$, and observe that

$\displaystyle\mathcal{P}^{\prime}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\\{\vec{\varphi}\ :\
F^{\prime}(\vec{\varphi})>0\\}=\mathcal{P}+\vec{\tau}.$

Since $\mathcal{P}^{\prime}$ is obtained from $\mathcal{P}$ by a translation,
they have the same measure. Furthermore, as a consequence of symmetry of
cosine we have:

$\displaystyle\mu(\mathcal{P}^{\prime})=2^{\eta}\mu\big{(}\underbrace{\mathcal{P}^{\prime}\cap[0,1/2]^{\eta}}_{\hat{\mathcal{P}}}\big{)}.$

So the density of the sequence can be derived from the volume of
$\hat{\mathcal{P}}$. We write the latter as a certain integral. To this end,
define the set $\mathcal{L}$ as,

$\displaystyle\mathcal{L}\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\left\\{\vec{x}\in[-1,1]^{\eta}\ :\
c+\sum_{i=1}^{\eta}r_{i}x_{i}>0\right\\}.$

Observe that the function $\cos^{-1}(\vec{x})/2\pi$, denoted $g(\vec{x})$, is
a continuously differentiable bijection from $[-1,1]^{\eta}$ to
$[0,1/2]^{\eta}$, and that furthermore:

$\displaystyle g(\mathcal{L})=\hat{\mathcal{P}}.$

Denote by $g^{\prime}$ the Jacobian of $g$, then a variable change (see
(spivak18_calcul_manif, Theorem 3-13)) leads to:

$\displaystyle\mu(\hat{\mathcal{P}})=\int_{g(\mathcal{L})}d\vec{\varphi}=\int_{\mathcal{L}}|\det
g^{\prime}|d\vec{x}=\frac{1}{(2\pi)^{\eta}}\int_{\mathcal{L}}\prod_{i=1}^{\eta}\frac{1}{\sqrt{1-x_{i}^{2}}}d\vec{x}.$

From here it follows that $\mu(\mathcal{P})$ is rational if and only if

(20)
$\displaystyle\int_{\mathcal{L}}\prod_{i=1}^{\eta}\frac{1}{\sqrt{1-x_{i}^{2}}}d\vec{x}\
\ \ \in\ \ \ \mathbb{Q}\ \pi^{\eta}.$

The class of numbers that can be expressed as integrals of algebraic functions
over semialgebraic sets are known as periods (kontsevich01_period). They
contain all algebraic numbers, as well as their logarithms, and some
transcendental numbers like $\pi$; they are exceedingly commonplace however
not well understood.

We do not know how to decide (20), but we point out to some work that might
prove to be helpful. One is Conjecture 1 in (kontsevich01_period), that says
that if one period has two different representations as integrals, one can
obtain one from the other through three simple operations: additivity, change
of variables and Stokes’s formula. It is not clear however, even if the
conjecture were to be true, how one can calculate a sequence of such
operations. A more direct conjecture is one made by Grothendieck that predicts
the transcendence degree of field extension of $\mathbb{Q}$ that are generated
by a finite set of periods. See (ayoub2014periods) for definitions and a
discussion about these two conjectures. More seems to be known about the
special case of curves (huber2018transcendence), but in this case, for our
purposes, we can give a more satisfactory answer by simpler means.

###  6.2. One Pair of Dominant Complex Roots

When there is at most one pair of dominant complex roots, we have $\eta=1$ and
the function $F$ can be written as:

$\displaystyle F(\varphi)=c+r\cos(2\pi(\varphi+\tau)).$

Clearly when $|c|\geq|r|$ the density is either $1$ or $0$ depending on the
sign of $c$, so assume that $|c|<|r|$. As we explained above, we can do away
with the translation by $\tau$ when solely interested in density, and
furthermore we can restrict $\varphi$ to the interval $[0,1/2]$.

Since the sequence is non-degenerate, the ratio $\lambda/\overline{\lambda}$
is not a root of unity, which implies that $\varphi$ is not a rational number.
In this case Cassels’s theorem (Theorem 4.1) is applicable. As a consequence
of that theorem, to calculate the density, it suffices to calculate the length
of the interval in $[0,1/2]$ which includes all $\varphi$ for which:

$\displaystyle\cos(2\pi\varphi)>\frac{-c}{r}.$

Depending on the sign of $-c/r$, the length of this interval is

$\displaystyle\text{either}\ \ \ \ \frac{\cos^{-1}(-c/r)}{2\pi}\ \ \ \text{ or
}\ \ \ 1-\frac{\cos^{-1}(-c/r)}{2\pi},$

in both cases it is rational if and only if $cos^{-1}(-c/r)$ is a rational
multiple of $\pi$. In the remainder of this section we prove that we can
decide whether the inverse cosine of a real algebraic number is a rational
multiple of $\pi$.

######  Proposition 6.1.

Given a real algebraic number $\alpha\in[-1,1]$ of degree $d$, it is decidable
whether

$\displaystyle\cos^{-1}(\alpha)\in\mathbb{Q}\pi.$

###### Proof.

Clearly $\cos^{-1}(\alpha)$ is a rational multiple of $\pi$ if and only if
there is a rational $a/b\in\mathbb{Q}$, $b>0$, such that
$a\cos^{-1}(\alpha)=b\pi$. Which, in turn, holds if and only if there exists
$a/b\in\mathbb{Q}$ (possibly different), $b>0$, such that:

$\displaystyle\cos\left(a\cos^{-1}(\alpha)\right)=(-1)^{b}.$

To proceed we need the definition of the Chebyshev polynomials of the first
kind of order $n$. These are univariate polynomials $T_{n}$, for
$n\in\mathbb{N}$ that are characterised by the equation:

$\displaystyle T_{n}(\cos\theta)\mathrel{\overset{\makebox[0.0pt]{\mbox{\tiny
def}}}{=}}\cos(n\theta).$

One can also define them via a recurrence relation. We see that:

$\displaystyle
T_{a}(\alpha)=T_{a}(\cos\cos^{-1}(\alpha))=\cos(a\cos^{-1}(\alpha))=(-1)^{b}.$

As a consequence $\cos^{-1}(\alpha)$ is a rational multiple of $\pi$ if and
only if there is some $n\in\mathbb{N}$, such that $\alpha$ is a root of

$\displaystyle T_{n}(x)-1\qquad\text{or}\qquad T_{n}(x)+1.$

The roots of these polynomials are straightforward to describe:

######  Observation 6.2.

Let $n\in\mathbb{N}$. All the roots of $T_{n}(x)+1$ and of $T_{n}(x)-1$ come
from the set

$\displaystyle\big{\\{}\pm\cos(k\pi/n)\ :\ 0\leq k\leq n\big{\\}}.$

The proof of this observation follows plainly from the fact that for all
$x\in\mathbb{R}$ such that $|x|\leq 1$, we have

$\displaystyle T_{n}(x)=T_{n}(\cos\cos^{-1}x)=\cos(n\cos^{-1}x)$

and the fact that we can write $-\cos(k\pi/n)$ as $\cos(k\pi/n+\pi)$.

From 6.2 and the discussion preceding it we conclude that $\cos^{-1}(\alpha)$
is a rational multiple of $\pi$ if and only if it is equal to
$\pm\cos(k\pi/n)$ for some $k,n\in\mathbb{N}$, $k\leq n$. The numbers
$\pm\cos(k\pi/n)$ are algebraic, indeed they satisfy the Chebyshev polynomial
of order $n$, furthermore if $\gcd(k,n)=1$ then $\cos(2k\pi/n)$ is an
algebraic integer of degree $\Phi(n)/2$ (lehmer1933note, Theorem 1), where
$\Phi$ is the Euler’s totient function.

Now, since $\alpha$ has degree $d$, we take some $N\in\mathbb{N}$ such that
$\Phi(N)\geq 2d$. By testing (with the algorithms from Theorem 2.3 say)
whether $\alpha$ is a root of any $T_{n}(x)\pm 1$, for $n\leq N$ we can decide
whether $\cos^{-1}(\alpha)$ is a rational multiple of $\pi$. ∎

###### Acknowledgements.

I am grateful to James Worrell for many helpful discussions.


# A note on local uniqueness of equilibria: How isolated is a local
equilibrium?

Stefano Matta.
Correspondence to S. Matta, Dipartimento di Economia, University of Cagliari,
viale S. Ignazio 17, 09123 Cagliari, Italy, tel. 00390706753340, Fax
0039070660929 E-mail<EMAIL_ADDRESS>The author was supported by STAGE,
funded by Fondazione di Sardegna and Regione Autonoma della Sardegna.
(University of Cagliari)

Abstract: The motivation of this note is to show how singular values affect
local uniqueness. More precisely, Theorem 3.1 shows how to construct a
neighborhood (a ball) of a regular equilibrium whose diameter represents an
estimate of local uniqueness, hence providing a measure of how isolated a
(local) unique equilibrium can be. The result, whose relevance in terms of
comparative statics is evident, is based on reasonable and natural assumptions
and hence is applicable in many different settings, ranging from pure exchange
economies to non-cooperative games.

Keywords: Comparative statics, regularity, singular values, local uniqueness.

JEL Classification: C60, C62, D51.

##  1 Introduction

Consider an equilibrium equation $f(p,q)=0$, where $p$ and $q$ denote the
unknowns and parameters, respectively. Local uniqueness and continuous
(smooth) dependence of the unknowns on the parameters are at the heart of
comparative statics. This means that, roughly speaking, the (locally unique)
solution $p$ changes continuously (smoothly) as the parameter $q$ varies under
a continuous (smooth) perturbation.

More precisely, at a point $p$ belonging to the solution set of $q$, there
exists a neighborhood $N$ of $(p,q)$ such that the projection onto the second
factor, $pr:(p,q)\to q$, restricted to $N$, is an homeomorphism
(diffeomorphism).

This regularity property has been extensively studied in the literature in
different settings, in particular after the introduction of the differentiable
viewpoint in the seminal paper by [7]. The study of the equilibrium set
$E=\\{(p,q)|\,f(p,q)=0\\}$ and the properties of the projection $pr:E\to Q$,
$(p,q)\mapsto q$, allows to establish natural connections between economic and
mathematical properties: e.g., the surjectivity of $pr$ (existence), the
cardinality of the set $\\{pr^{-1}(q)\\}$ (uniqueness/multiplicity), the
continuity of the correspondence of $pr^{-1}$ (structural stability).

Under the very restrictive hypothesis of global uniqueness, i.e. when the set
$pr^{-1}(q)$ is a single-tone set for every parameter $q$, the whole solution
set $E$ is homeomorphic (diffeomorphic) to the parameter set.

Multiplicity, on the other hand, is deeply related to the set of singular
values of the projection. Even if this set has measure zero in $Q$ under
certain assumptions, its components of codimension-one and codimension-two can
be relevant. Consider, for example, redistribution policies, represented by
continuous perturbations of the parameters. In such an instance, it is crucial
not to cross the singular set to avoid catastrophes and undesiderable welfare
effects, that can be determined by prices multiplicity. For example, Figure 1,
taken from [8], shows an example of two policies sharing the same target, but
whose (different) outcomes depend on the order of use of resources.

Figure 1: Two policies sharing the same target but with different outcomes
(taken from [8]).

The codimension-two components also play a key role, as highlighted in this
note, since they have an impact on the topology of the parameter set. The
intuition behind this is that they can be seen as holes inside $Q$. The
consequences of this property have not, to the best of my knowledge, been
analyzed in the literature, which has traditionally focused on the
codimension-one component, the only one that can disconnect $Q$.

The motivation of this short note is to highlight how the singular values can
affect the size of local uniqueness. This information can be used to estimate
how isolated a (local) unique equilibrium can be. More precisely, Theorem 3.1
shows a sufficient condition that enables to construct a neighborhood $N$ such
that the projection restricted to $N$ is injective. This means that local
uniqueness is satisfied in $N$.

This result can be applied to different settings, characterized by
multiplicity and multiple roots associated to critical solutions. For example,
one can appraise potential distorsive effects (e.g. transfer paradox [1]) of
redistributive policies [9] in exchange and production economies [5]. This is
due to the fact that a common geometric structure is present. The same
structure, with suitable changes, can be found, e.g., in the case of infinite
economies [4, 6] or non-cooperative game theory [10].

This paper is organized as follow. Section 2 recalls the main definitions and
tools. Section 3 is devoted to the proof of the main result.

##  2 Definitions

In this section the main definitions and properties are outlined for the
reader’s convenience. For an introduction to covering spaces, the reader is
referred to [13].

The analysis is focused on the projection map $pr:E\to Q$. The set $Q$ denotes
the parameter set and $E$ is the equilibrium set, i.e.
$E=\\{(p,q)|\,f(p,q)=0\\}$, where $f(p,q)=0$ represents an equilibrium
condition to be satisfied by the unknowns $p$, given the constraints and the
primitives of the model.

Suppose that both $E$ and $Q$ are smooth manifolds where we can measure the
length of curves and the distance between points. More precisely, given a
piecewise differentiable curve $\tilde{\gamma}:[0,1]\rightarrow E$ joining two
points $\tilde{x}_{1}$ and $\tilde{x}_{2}$ in $E$, namely
$\tilde{\gamma}(0)=\tilde{x}_{1}$ and $\tilde{\gamma}(1)=\tilde{x}_{2}$, we
can compute the length of $\tilde{\gamma}$ denoted by $L_{E}(\tilde{\gamma})$
and the distance

$d_{E}(\tilde{x}_{1},\tilde{x}_{2})=\mathop{\hbox{inf}}_{\tilde{\gamma}\in\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}}L_{E}(\tilde{\gamma}).$
(1)

between $\tilde{x}_{1}$ and $\tilde{x}_{2}$, where
$\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}$ denotes the set of piecewise
differentiable curves with endpoints $\tilde{x}_{1}$ and $\tilde{x}_{2}$.
Similarly, we can compute the length $L_{Q}(\gamma)$ of a piecewise
differentiable curve $\gamma:[0,1]\rightarrow Q$ joining two points $x_{1}$
and $x_{2}$ of $Q$ and their distance $d_{Q}(x_{1},x_{2})$.

In this paper we assume that the following properties are satisfied:

  * (i)

$pr$ is smooth;

  * (ii)

$pr$ is proper;

  * (iii)

$pr$ is a length decreasing map, i.e.

$L_{E}(\tilde{\gamma})\geq L_{Q}(pr\circ\tilde{\gamma}),\
\forall\tilde{\gamma}:[0,1]\to E.$ (2)

Consequently, by (1), $pr$ is distance decreasing, namely

$d_{E}(\tilde{x},\tilde{y})\geq d_{Q}(pr(\tilde{x}),pr(\tilde{y})),\
\forall\tilde{x},\tilde{y}\in E.$ (3)

  * (iv)

the ball centered at a point $\tilde{x}\in E$ (resp. $x\in Q$) of radius
$\tilde{r}$ (resp. $r$), namely $B_{\tilde{r}}(\tilde{x})=\\{\tilde{y}\in E\
|\ d_{E}(\tilde{y},\tilde{x})<\tilde{r}\\}$ (resp. $B_{r}(x)=\\{y\in Q\ |\
d_{Q}(y,x)<r\\}$ ) is connected.

All these are reasonable and natural assumptions. Smoothness is an
approximation of continuity under suitable topologies, properness also has a
nice economic meaning: for example, it represents the idea of scarcity and
desirability. Assumption (iii) and (iv) have a very intuitive meaning. Indeed
it is expected that a projection does not increase the length of curves and
that the metrics chosen satisfy the connectedness property. As a specific and
natural example, one can take a Riemannian metric $g_{Q}$ on $Q$ (if $Q$ is a
subset of some Euclidean space, $g_{Q}$ can be the flat metric as is the case,
e.g., in literature related to the Edgeworth box) and the pull-back metric
$g_{E}=pr^{*}g_{Q}$ on $E$. Then $pr$ is length decreasing if we endow $Q$ and
$E$ with the length functions associated to these metrics.

In this setting, the application of the inverse function theorem (IFT) and
Sard’s theorem to $pr$ leads to standard regularity properties enjoyed by an
open and dense subset of the parameter space, denoted by $\cal R$. More
precisely, it is not hard to prove that $pr_{|pr^{-1}(\cal R)}:pr^{-1}(\cal
R)\rightarrow{\cal R}$ is a covering map (see [11, Proposition 2.2]). Indeed
the properness of $pr$ is a sufficient condition to turn a surjective local
diffeomorphism into a covering map. We recall that a covering map between two
topological spaces $\tilde{X}$ and $X$ is a continuous surjective map such
that each $x\in X$ admits a well-covered neighborhood, i.e., each $x\in X$ has
an open neighborhood $U$ such that $p^{-1}(U)$ is a disjoint union of open
sets in $\tilde{X}$, each of which is mapped by $p$ homeomorphically onto $U$.

The economic meaning behind the covering property is that it represents the
well-known property of smooth selection of equilibria. This is crucial for
comparative statics analysis and characterizes the regular values ${\cal R}$
of the projection. Its complement $Q\setminus\cal R$ represents the projection
of the critical equilibria, denoted by $\Sigma=\cup\Sigma^{k}$. It is the
union of closed sets of codimension $k$, with $k$ greater or equal to $1$.
Hence $\Sigma^{1}$ denotes the component which disconnects the parameter set.
For a deep analysis of the set of singular and critical equilibra in a general
equilibrium framework, the reader is referred to [2, 3, 5, 12]. Literature is
usually focused on $\Sigma^{1}$ as the main cause of catastrophes. But
$\Sigma^{2}$ affects ${\cal R}$’s topology in a relevant way as we will see in
Theorem 3.1 (see also Remark 3.3 below).

##  3 Main result

Let $x\in{\cal R}$ and let $\Gamma_{x}$ be the set of non contractible loops
$\gamma:[0,1]\to{\cal R}$, $\gamma(0)=\gamma(1)=x$. Notice that the image of
$\gamma$ lies in a connected component $K_{x}$ of ${\cal R}$ containing $x$.
Let

$m_{x}=\mathop{\hbox{inf}}_{\gamma\in\Gamma_{x}}L_{d_{Q}}(\gamma)\geq 0$ (4)

be the nonnegative number which measures the length of the minimal loop of all
the non contractible closed curves in $K_{x}$ based at $x$. If no $\Sigma^{2}$
component belongs to the connected component of $Q\setminus\Sigma^{1}$
containing $x$, then $m_{x}=0$. It could be said in a suggestive way that
$\Sigma^{2}$ are “holes” in $K_{x}$ iff $m_{x}\neq 0$.

Let us also define

$d_{x}=d_{Q}(x,\Sigma^{1})=\mathop{\hbox{inf}}_{\sigma\in\Sigma^{1}}d_{Q}(x,\sigma).$
(5)

The positive number $d_{x}$ measures the distance between $x$ and the boundary
of $K_{x}$, which corresponds to $\Sigma^{1}$. This distance is well-defined
since $\Sigma^{1}$ is closed in $Q$, being the projection of a closed set via
a proper map.

The following theorem uses the information so far to construct a neighborhood
$N$ of $\tilde{x}$ such that $pr_{|N}$ is injective, i.e. where one has local
uniqueness.

###### Theorem 3.1

Let us assume assumptions (i)-(iv) above are satisfied. Let $x\in{\cal R}$ and
$\tilde{x}\in pr^{-1}(x)$. Let $r_{x}$ be the positive real number defined as

$r_{x}=\begin{cases}3d_{x}&\mbox{if}\ m_{x}=0\\\ \min(m_{x},d_{x})&\mbox{if}\
m_{x}\neq 0.\end{cases}$

where $m_{x}$ and $d_{x}$ are given by (4) and (5) respectively. Then
$pr_{|_{B_{\frac{r_{x}}{3}}(\tilde{x})}}$ is injective.

Proof: Denote by $\tilde{K}_{x}$ the connected component of $pr^{-1}({\cal
R})$ containing $\tilde{x}$. Then, being $E$ and $Q$ smooth manifolds, by [13,
Ch. 5, Lemma 2.1] $pr_{|\tilde{K}_{x}}:\tilde{K}_{x}\to K_{x}$ is a covering
map. If $m_{x}=0$ then $K_{x}$ is simply-connected and hence
$pr_{|\tilde{K}_{x}}$ [13, Ch. 5, Exercise 6.1] is a diffeomorphism. Notice
that by (iv) $B_{d_{x}}(x)$ is connected and hence $B_{d_{x}}(x)\subset
K_{x}$. Moreover since by (3) $pr$ is distance decreasing one gets that
$pr\left(B_{d_{x}}(\tilde{x})\right)\subset B_{d_{x}}(x)\subset K_{x}$ and
hence $B_{d_{x}}(\tilde{x})\subset\tilde{K}_{x}$. It follows that
$pr_{|_{B_{\frac{r_{x}}{3}}(\tilde{x})}}=pr_{|B_{d_{x}}(\tilde{x})}$ is
injective.

Let $m_{x}\neq 0$. Assume, by contradiction, that $\tilde{x}_{1}$ and
$\tilde{x}_{2}$ are two distinct points in $B_{\frac{r_{x}}{3}}(\tilde{x})$,
$r_{x}=\min(m_{x},d_{x})$, such that $pr(\tilde{x}_{1})=pr(\tilde{x}_{2})=x$.
Let $\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}$ denote the set of piecewise
differentiable curves $\tilde{\gamma}:[0,1]\to B_{\frac{r_{x}}{3}}(\tilde{x})$
with endpoints $\tilde{x}_{1}$ and $\tilde{x}_{2}$. Notice that
$\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}\neq\emptyset$ by assumption
(iv). Then, for each
$\tilde{\gamma}\in\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}$, the curve

$\gamma=pr\circ\tilde{\gamma}:[0,1]\to K_{x}$

is a piecewise differentiable loop based on $x$. By [13, Ch. 5, Theorem 4.1]
each of these loops is non-contractible and hence by (4) one has
$L_{d_{Q}}(\gamma)\geq m_{x}$. It follows, by (1) and (2), that

$d_{E}(\tilde{x}_{1},\tilde{x}_{2})=\mathop{\hbox{inf}}_{\tilde{\gamma}\in\tilde{\Gamma}_{\tilde{x}_{1},\tilde{x}_{2}}}L_{d_{E}}(\tilde{\gamma})\geq\mathop{\hbox{inf}}_{\gamma\in\Gamma_{x}}L_{d_{Q}}(\gamma)=m_{x}\geq
r_{x}.$

On the other hand, by the triangle inequality,

$d_{E}(\tilde{x}_{1},\tilde{x}_{2})\leq
d_{E}(\tilde{x}_{1},\tilde{x})+d_{E}(\tilde{x},\tilde{x}_{2})=\frac{r_{x}}{3}+\frac{r_{x}}{3}=\frac{2}{3}r_{x}<r_{x},$

yielding the desired contradiction. $\Box$

###### Remark 3.2

The key idea behind the proof of the theorem is, roughly speaking, as follows.
If $K_{x}$ is the connected component of ${\cal R}$ containing $x$, the set
$\Sigma^{2}$ are “holes” inside $K_{x}$. If $K_{x}$ did not contain holes,
then it would be simply connected and hence the solution set would be single-
tone (global uniqueness) for every parameter in $K_{x}$, if one restricts $pr$
to the connected component $\tilde{K}_{x}$ of $pr^{-1}({\cal R})$ containing
$\tilde{x}$. On the other hand, if $K_{x}$ contains holes then $m_{x}\neq 0$,
namely one has to be careful with the non-contractible loops by taking the
ball centered at $\tilde{x}$ of radius $\min(d_{x},m_{x})$.

###### Remark 3.3

The diameter of the ball $\frac{r_{x}}{3}(\tilde{x})$ represents a sufficient
condition that ensures injectivity but it is does not maximize the size of the
ball (if $m_{x}\neq 0$). It can be seen as an estimate of local uniqueness and
a measure of how isolated is a local equilibrium, providing us with a possible
answer to the question raised in the title the paper.

## References

  * Balasko [1978] Balasko, Y., 1978, The transfer problem and the theory of regular economies, International Economic Review 19, 687-694.
  * Balasko [1978] Balasko, Y., 1978, Equilibrium analysis and envelope theory, Journal of Mathematical Economics 5, 153-72.
  * Balasko [1992] Balasko, Y., 1992, The set of regular equilibria, Journal of Economic Theory 58, 1-8.
  * Balasko [1997] Balasko, Y., 1997, The natural projection approach to the infinite-horizon model, Journal of Mathematical Economics, 27, 251-265.
  * Balasko [2011] Balasko, Y., 2011, General Equilibrium Theory of Value, Princeton University Press, NJ.
  * Chichilnisky and Zhou [1998] Chichilnisky, G., Zhou, Y., 1998, Smooth infinite economies, Journal of Mathematical Economics, 28, 27-42.
  * Debreu [1970] Debreu, G. 1970, Economies with a finite set of equilibria, Econometrica 38, 387-92.
  * Dierker [1989] Dierker, E., 1989, Regular Economies, in The New Palgrave General Equilibrium, edited by J. Eatwell, M. Milgate and P. Newman, The Macmillan Press Limited, London.
  * Garrat and Goenka [1995] Garratt, R., Goenka, A., 1995, Income redistributions without catastrophes, J. Econ. Dyn. Control 19, 441-455.
  * Govindan and Wilson [2001] Govindan, S., Wilson, R., 2001, Direct Proofs of Generic Finiteness of Nash Equilibrium Outcomes, Econometrica, 69, 3, 765-769.
  * Loi and Matta [2010] Loi, A. and S. Matta, 2010, A note on the structural stability of the equilibrium manifold, Journal of Mathematical Economics 46, 591-594.
  * Loi and Matta [2016] Loi, A. and S. Matta, 2016, On the topology of the set of critical equilibria, International Journal of Economic Theory 12, 107-126.
  * Massey [1991] Massey, W.S., 1991, A Basic Course in Algebraic Topology. Springer-Verlag, New York.