University of Warsaw,
Polandclementelorenzo@gmail.comhttps://orcid.org/0000-0003-0578-9103partially
supported by the ERC grant INFSYS, agreement no. 950398. University of Warsaw,
Polandm.donten@mimuw.edu.plhttps://orcid.org/0000-0002-2138-4109partially
supported by the National Science Center, Poland, project 2017/26/E/ST1/00231.
University of Warsaw<EMAIL_ADDRESS>supported by
the ERC grant INFSYS, agreement no. 950398. University of Warsaw,
<EMAIL_ADDRESS>supported by the ERC grant BOBR,
agreement no. 948057. Lorenzo Clemente, Maria Donten-Bury, Filip Mazowiecki
and Michał Pilipczuk [100]Replace ccsdesc macro with valid one

###### Acknowledgements.

I want to thank …John Q. Open and Joan R. Access 2 42nd Conference on Very
Important Topics (CVIT 2016) CVIT 2016 CVIT 2016 December 24–27, 2016 Little
Whinging, United Kingdom 42 23

# On Rational Recursive Sequences

Lorenzo Clemente  Maria Donten-Bury  Filip Mazowiecki  Michał Pilipczuk

###### Abstract

We study the class of rational recursive sequences (ratrec) over the rational
numbers. A ratrec sequence is defined via a system of sequences using mutually
recursive equations of depth 1, where the next values are computed as rational
functions of the previous values. An alternative class is that of simple
ratrec sequences, where one uses a single recursive equation, however of depth
$k$: the next value is defined as a rational function of $k$ previous values.

We conjecture that the classes ratrec and simple ratrec coincide. The main
contribution of this paper is a proof of a variant of this conjecture where
the initial conditions are treated symbolically, using a formal variable per
sequence, while the sequences themselves consist of rational functions over
those variables. While the initial conjecture does not follow from this
variant, we hope that the introduced algebraic techniques may eventually be
helpful in resolving the problem.

The class ratrec strictly generalises a well-known class of polynomial
recursive sequences (polyrec). These are defined like ratrec, but using
polynomial functions instead of rational ones. One can observe that if our
conjecture is true and effective, then we can improve the complexities of the
zeroness and the equivalence problems for polyrec sequences. Currently, the
only known upper bound is Ackermanian, which follows from results on
polynomial automata. We complement this observation by proving a PSPACE lower
bound for both problems for polyrec. Our lower bound construction also implies
that the Skolem problem is PSPACE-hard for the polyrec class.

###### keywords:

recursive sequences, polynomial automata, zeroness problem, equivalence
problem

###### category:

##  1 Introduction

The topic of this paper are recursively defined sequences of rational numbers
$\mathbb{N}\to\mathbb{Q}$. There are two natural ways to define such
sequences. In a _simple recursion of depth $k$_ one fixes $k$ initial values
and defines the next value as a function of the previous $k$ values. This is
how the Fibonacci sequence is usually defined (with $k=2$): $f_{0}=0$,
$f_{1}=1$, and $f_{n+2}=f_{n+1}+f_{n}$. In a _mutual recursion of width $k$_
one defines a system of $k$ sequences such that every sequence has its initial
value and the update function can access the immediately previous value of all
$k$ sequences, but no older value. For example, we can define $a_{n}=n^{2}$
with an extra sequence $b_{n}=n$ as follows: $a_{0}=b_{0}=0$ and
$a_{n+1}=a_{n}+2b_{n}+1$, $b_{n+1}=b_{n}+1$. Both styles allow to define
various classes of sequences depending on what operations are allowed in the
equations, and in general mutual recursion of width $k$ can simulate simple
recursion of depth $k$ (by adding sufficiently many auxiliary sequences).

One of the most well-known classes of sequences is the class of _linear
recursive sequences_ , which is obtained by allowing the update function to
use addition and multiplication with constants. These are usually defined with
a simple recursion, like in the Fibonacci example, but in fact, as a
consequence of the Cayley-Hamilton theorem, one obtains the same class when
using mutual recursion [19, Lemma 1.1]. In particular, all the example
sequences $f_{n}$, $a_{n}$ and $b_{n}$ are linear recursive.

Another natural class of sequences are the _polynomial recursive sequences_
(_polyrec_), which are defined with mutual recursion and updates from the ring
of polynomial functions $\mathbb{Q}[x_{1},\dots,x_{k}]$. An example sequence
from this class is $c_{n}=n!$, where one can use the already defined sequence
$b_{n}$ and define $c_{0}=1$ and $c_{n+1}=c_{n}\cdot(b_{n}+1)$. To see the
polynomials behind this definition, let $x$ and $y$ be variables corresponding
to $b_{n}$ and $c_{n}$, respectively. The polynomial to define $b_{n+1}$ is
$P_{b}(x,y)=x+1$, and the polynomial to define $c_{n+1}$ is
$P_{c}(x,y)=y(x+1)$. The class of _simple polynomial recursive sequences_ is
obtained by using polynomial updates and a simple recursion (instead of mutual
recursion) and it is known to be strictly included in the class of all polyrec
sequences. In particular, the sequence $c_{n}$ is polyrec but not simple
polyrec [12, Theorem 3.1].

The definition via mutual recursion appears in the area of control theory
(under the name _implicit representation_ of the space of states), and, in
computer science, in the context of _weighted automata_ over $\mathbb{Q}$.
Such automata output a rational number for every word over a finite alphabet
$\Sigma$, and they are defined by linear updates [16]. Linear recursive
sequences are thus equivalent to weighted automata with a $1$-letter alphabet
$\Sigma=\\{a\\}$ [3]. Similarly, polyrec sequences are equivalent to
_polynomial automata_ [4] (also known as _cost-register automata_ [1]) with a
$1$-letter alphabet [12].

We are interested in two classical decision problems for such automata.
_Equivalence_ : Given two automata $\mathcal{A}$ and $\mathcal{B}$ do they
output the same number for every word, and _zeroness_ : Does the input
automaton $\mathcal{A}$ output $0$ for every word. These problems are well-
known to be efficiently equivalent to each other: Zeroness is clearly a
special case of equivalence (just take $\mathcal{B}$ to output zero for every
word), and equivalence of $\mathcal{A},\mathcal{B}$ reduces to zeroness of the
difference automaton $\mathcal{A}-\mathcal{B}$ with the expected semantics.
Therefore, we will consider only the zeroness problem. From the seminal work
of Schützenberger on minimisation of weighted automata it follows that the
zeroness problem for weighted automata is in PTIME [30] (in fact even in
$\textsf{NC}^{\text{2}}$ [34]). For polynomial automata over a binary
alphabet, zeroness is known to be Ackermann-complete [4]. Using the connection
between sequences and automata one immediately obtains
$\textsf{NC}^{\text{2}}$ and Ackermann upper bounds for the zeroness problem
of linear recursive sequences, resp., polyrec sequences.

Let us take a closer look at the zeroness problem for recursive sequences,
i.e., given a sequence $u_{n}$ is it the case that $u_{n}=0$ for all
$n\in\mathbb{N}$? The zeroness problem is a fundamental problem for number
sequences. It is a basic building block in computer algebra, e.g., in proving
identities involving recursively defined sequences. It is also important from
a theoretical point of view as a yardstick of the well-behavedness of classes
of number sequences, i.e., interesting classes of sequences should at least
have a decidable zeroness problem. The difficulty of solving the zeroness
problem in general depends on how the sequence is presented. If the sequence
is defined with a simple recursion of depth $k$ such as
$u_{n+k}=f(u_{n+k-1},\dots,u_{n})$, then zeroness trivially reduces to
checking that the first $k$ values are $0$ and that the recursive update $f$
is well-defined and needs to output $0$ when the previous values are $0$,
i.e., $f(0,\dots,0)=0$. However, this simple reasoning is flawed in the case
of mutual recursion, because the auxiliary sequences employed in the mutual
recursion need not be zero. However, for linear recursive sequences the
zeroness problem is easily solved even in the case of mutual recursion,
because the reduction to simple recursion [19, Lemma 1.1] implies that $a_{n}$
is zero if, and only if, its first $k+1$ values $a_{0}=\cdots=a_{k}$ are zero.
For polyrec sequences we cannot apply this argument since mutual recursion
cannot be simulated by simple recursion in the case of polynomial updates.

#### Our results

In this paper we introduce the class of _rational recursive sequences_
(_ratrec_). This class is defined with mutual recursion and updates from the
field of rational functions $\mathbb{Q}(x_{1},\dots,x_{k})$. For example, the
Catalan numbers $C_{n+1}=\frac{2(2n+1)}{n+2}C_{n}$ can be defined using
$b_{n}$ as an auxiliary sequence. Namely, $C_{0}=1$ and
$C_{n+1}=\frac{2(2b_{n}+1)}{b_{n}+2}C_{n}$, where the rational function used
to define $C_{n+1}$ is $R(x,y)=\frac{2(2x+1)}{x+2}y$. By definition, the class
of polyrec sequences is included in the class of ratrec sequences, and in fact
the inclusion is strict as witnessed by the fact that the Catalan numbers
$C_{n}$ are not polynomialy recursive [12, Corollary 4.1]. Moreover, ratrec
sequences also include the well-known and wide-spread _P-recursive sequences_
111 Sometimes P-recursive sequences are also called _holonomic sequences_ ,
due to a connection with holonomic generating functions.  [21], which
according to a 2005 estimate comprise at least 25% of the OEIS archive [29].

A natural question is whether the class of ratrec sequences semantically
collapes to the class of _simple rational recursive sequences_ obtained by
adopting simple recursion. Unlike in the case of polynomial updates, we
conjecture that for rational updates we do have such a collapse.

######  Conjecture 1.1.

The class of rational recursive sequences coincides with the class of simple
rational recursive sequences.

To see the power of ratrec sequences recall that $c_{n}=n!$ is not a simple
polyrec sequence. However, when in the recursion we allow rational functions,
then $c_{n}$ can be defined with a simple recursion, namely:
$c_{n+2}=\frac{(c_{n+1})^{2}}{c_{n}}+c_{n+1}$. Thus $c_{n}$ is simple ratrec.

We introduce a technique towards proving 1.1, which comes from commutative
algebra. Instead of looking at the elements of a ratrec sequence as numbers in
the field of rationals $\mathbb{Q}$, we symbolically view them as elements of
the field of rational functions $\mathbb{Q}(x_{1},\dots,x_{k})$. More
precisely, we assume that the sequences
$\mathbf{F}^{(1)},\ldots,\mathbf{F}^{(k)}$ are initialised by setting
$F_{0}^{(i)}=x_{i}$ for all $i\in\\{1,\ldots,k\\}$; then, a system of
recursive equations governed by rational functions defines further entries of
the sequences. Thus, the recursive definition will output elements in
$\mathbb{Q}(x_{1},\dots,x_{k})$ rather than $\mathbb{Q}$. Intuitively, this
corresponds to treating the initial conditions of a system of ratrec sequences
symbolically, rather than instantiating them with actual rational values.

Informally speaking, we prove 1.1 for symbolic ratrec sequences, as explained
above. Here is a semi-formal statement of our main result, see Theorem 4.1 for
a formalization.

######  Theorem 1.2.

The class of rational recursive sequences over
$\mathbb{Q}(x_{1},\ldots,x_{k})$, with the system initialised by
$F_{0}^{(i)}=x_{i}$, coincides with the class of simple rational recursive
sequences.

The proof proceeds as follows. From the functions defining the ratrec system
we build a sequence of field extensions

$\mathbb{Q}\subseteq\mathbb{F}_{0}\subseteq\mathbb{F}_{1}\subseteq\mathbb{F}_{2}\subseteq\ldots\subseteq\mathbb{Q}(x_{1},\ldots,x_{k})$

and translate the problem of belonging to the class of simple ratrec sequences
to the question of whether this sequence of field extensions eventually
stabilises. In order to estimate at which level the stabilisation occurs we
use certain results on basic algorithms for rational function fields [23]. We
believe that this technique could be extended to prove 1.1, but we also show
an example why our current results are not strong enough.

Note that if 1.1 is moreover efficient, it gives a simple algorithm to check
zeroness for polyrec. Indeed, since polyrec is a particular case of ratrec,
then once a sequence is expressed as a simple ratrec it suffices to check
whether the first elements of the sequence are 0. This would improve the
Ackermann upper bound inherited from polynomial automata from [4]. This
suggests that for polyrec sequences the natural object of study are rational
function fields, which are of more algebraic nature and could provide better
complexity bounds than the order-theoretic techniques based on sequences of
polynomial ideals and Hilbert’s finite basis theorem [4].

Our final result is a complexity lower bound for the zeroness problem of
polyrec sequences.

######  Theorem 1.3.

The zeroness problem for polynomial recursive sequences is PSPACE-hard.

As far as we know, prior to this work nothing was known about the complexity
of zeroness for polyrec sequences, except for the Ackermann upper bound
following from polynomial automata [4]. The lower bound is proved by reducing
from the QBF validity problem.

Given 1.1 it seems natural to investigate the zeroness problem for ratrec
sequences. The issue is that it is not clear what would be the input for such
a decision problem. Recall that to define ratrec sequences we allow for
rational functions in the recursion, which means that we have to deal with
division in order to compute the elements of the sequences. Then either one
would require that the input sequence comes with a promise that all elements
are well-defined and no division by $0$ occurs; or one would need to verify
whether division by $0$ occurs in the input sequence. We find the former
solution unnatural, and the latter is at least as hard as the so-called Skolem
problem (c.f. below), which is not known to be decidable even for linear
recursive sequences.

#### Related work

The zeroness problem has been extensively studied. In the field of automata
theory, we can mention applications to the equivalence problem of several
classes of automata and grammars, starting from weighted finite automata [30]
and polynomial automata [4] already mentioned above, and including context-
free grammars [13], multiplicity equivalence of finite automata [34] and
multitape finite automata [20, 35], unambiguous context-free grammars [28,
Theorem 5.5] (c.f. [18, 14] for a PSPACE upper bound), polynomial grammars
(which generalise polynomial automata) [8, Chapter 11], deterministic top-down
tree-to-string transducers [31], MSO transductions on unordered forests [6,
7], MSO transductions of bounded treewidth under a certain equivalence
relation [9], Parikh automata [10], and unambiguous register automata [2]. By
replacing (pointwise) multiplication with convolution in the definition of
polyrec sequences we obtain the so-called _convolution recursive sequences_ ,
for which the zeroness problem can be solved in PSPACE [14, Theorem 4].

The zeroness problem of D-finite [36] and, more generally, D-algebraic power
series [15, 33] is known to be decidable, but its computational complexity has
not been investigated.

A natural problem related to the zeroness problem is the so-called _Skolem
problem_ , which asks whether a given sequence $a_{n}$ has a zero, i.e.,
whether for some $n$ we have $a_{n}=0$. As a corollary of the constructions
used to prove Theorem 1.3, it follows that the Skolem problem for polyrec
sequences is PSPACE-hard. Only NP-hardness was formerly known, and already for
linear recursive sequences [5, Corollary 2.1]. Decidability of the Skolem
problem for linear recursive sequences is a long-standing open problem (c.f.
the survey paper [25]). It is interesting to notice that those lower bounds
are obtained already on the fixed field with two elements $\\{0,1\\}$, and are
thus of a combinatorial rather than numerical nature. The Skolem problem for
weighted automata over $\mathbb{Q}$ (that generalise linear recursive
sequences) is undecidable [27].

##  2 Preliminaries

By $\mathbb{N}$ we denote the set of nonnegative integers. We denote an
arbitrary field by $\mathbb{F}$, and we use $0$ and $1$ to denote the zero,
resp., one elements thereof. Example fields of interest in this paper are:
rationals $\mathbb{Q}$; and the two-element field $\mathbb{F}_{2}$. A sequence
over a _domain_ $\mathbb{D}$ is a function $u\colon\mathbb{N}\to\mathbb{D}$.
The sequences considered in this work are over domains that have a field
structure, like rationals $\mathbb{Q}$. We use bold-face letters as a short-
hand for sequences, e.g., $\mathbf{u}=\langle u_{n}\rangle_{n\in\mathbb{N}}$.

In this paper we work with multivariate polynomials and rational functions.
The _(combined) degree_ of a monomial $x_{1}^{d_{1}}\cdots x_{k}^{d_{k}}$ is
$d_{1}+\cdots+d_{k}$ and the degree of a polynomial
$P\in\mathbb{Q}(x_{1},\dots,x_{k})$, written $\deg P$, is the maximum degree
of monomials appearing in it. A rational function is a formal fraction of two
polynomials, where the denominator is required to be non-zero. The degree of a
rational function is the maximum of the degrees of the numerator and the
denominator. Recall that for any field $\mathbb{F}$ and a set of variables
$x_{1},\ldots,x_{n}$, polynomials over $x_{1},\ldots,x_{n}$ form the ring
$\mathbb{F}[x_{1},\ldots,x_{n}]$, while rational functions over
$x_{1},\ldots,x_{n}$ form the field $\mathbb{F}(x_{1},\ldots,x_{n})$. We also
write $\mathbb{F}[\mathbf{x}]$ and $\mathbb{F}(\mathbf{x})$, where
$\mathbf{x}=(x_{1},\ldots,x_{n})$.

The computational aspects of multivariate polynomials, in particular their
representation on input to algorithms, are explained in Appendix A, as they
will be of no concern in Sections 3 and 4.

##  3 Rational recursive sequences

We start with the central definitions, which were already discussed in Section
1.

######  Definition 3.1.

A sequence $\mathbf{u}^{(1)}$ over a field $\mathbb{F}$ is rationally
recursive (or ratrec for short) of _dimension_ $k$ and _degree_ $D$ if there
exist auxiliary sequences $\mathbf{u}^{(2)},\ldots,\mathbf{u}^{(k)}$ over
$\mathbb{F}$ and rational functions
$P_{1},\ldots,P_{k}\in\mathbb{F}(x_{1},\ldots,x_{k})$ of degree at most $D$
such that for all $n\in\mathbb{N}$, we have

$\displaystyle\left\\{\begin{array}[]{lcl}u^{(1)}_{n+1}&=&P_{1}(u^{(1)}_{n},\ldots,u^{(k)}_{n}),\\\
&\vdots&\\\
u^{(k)}_{n+1}&=&P_{k}(u^{(1)}_{n},\ldots,u^{(k)}_{n}).\end{array}\right.$ (4)

A sequence $\mathbf{u}$ over a field $\mathbb{F}$ is polynomially recursive
(or polyrec for short) if it satisfies the same definition above, where
$P_{1},\ldots,P_{k}$ are taken as polynomials in
$\mathbb{F}[x_{1},\ldots,x_{k}]$. We refer to
$(\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)})$ as the system defining
$\mathbf{u}^{(1)}$.

In what follows we assume that whenever $\mathbf{u}$ is a ratrec sequence, say
defined by a system $(\mathbf{u}=\mathbf{u}^{(1)},\ldots,\mathbf{u}^{(k)})$,
for all $n\in\mathbb{N}$ all the right hand sides of equations (4) are well-
defined, that is, no denominator of any rational expression contained in the
right hand side is zero.

For instance, the sequence of _Catalan numbers_
$C_{n}=\frac{1}{n+1}\cdot{2n\choose n}$ is ratrec. This can be seen in several
ways. For example, they satisfy the recurrence
$C_{n+1}=\frac{2(2n+1)}{n+2}\cdot C_{n}$, giving rise to the following ratrec
system:

$\displaystyle\left\\{\begin{array}[]{ll}u_{n+1}&=\frac{2(2v_{n}+1)}{v_{n}+2}\cdot
u_{n},\\\ v_{n+1}&=v_{n}+1.\end{array}\right.$

More generally, any P-recursive sequence $a_{n}$ is ratrec. A sequence is _P-
recursive_ [32, Sec. 6.4] if it satisfies a single recursion of the form

$\displaystyle P_{0}(n)\cdot a_{n}+P_{1}(n)\cdot a_{n+1}+\cdots+P_{d}(n)\cdot
a_{n+d}=0,$ (5)

for every $n$ large enough, where $P_{0},\dots,P_{d}\in\mathbb{Q}[n]$ are
polynomials of the index variable $n$. This is readily transformed into the
ratrec system

$\displaystyle\left\\{\begin{array}[]{lcl}u^{(d)}_{n+1}&=&-\frac{P_{0}(v_{n})}{P_{d}(v_{n})}\cdot
u^{(0)}_{n}-\cdots-\frac{P_{d-1}(v_{n})}{P_{d}(v_{n})}\cdot u^{(d-1)}_{n},\\\
u^{(d-1)}_{n+1},&=&u^{(d)}_{n},\\\ &\vdots&\\\ u^{(0)}_{n+1}&=&u^{(1)}_{n},\\\
v_{n+1}&=&v_{n}+1.\end{array}\right.$

Assuming $v_{0}=0$ and $u^{(0)}_{0}=a_{0},\dots,u^{(d)}_{0}=a_{d}$, it is
immediate to verify $v_{n}=n$ and
$u^{(0)}_{n}=a_{n},\dots,u^{(d)}_{n}=a_{n+d}$ for every $n\in\mathbb{N}$.

The family of ratrec sequences strictly includes both P-recursive sequences
and polyrec sequences. As an example consider the sequence
$u_{n}=2^{2^{n}}+C_{n}$. On the one hand, this sequence is certainly ratrec
because it is the sum of a polyrec and a P-recursive sequence (which are
ratrec) and ratrec sequences are closed under sum. On the other hand, $u_{n}$
is not P-recursive since it grows asymptotically faster than any P-recursive
sequence (every P-recursive sequence is in $O((n!)^{\gamma})$ for some
constant $\gamma\in\mathbb{R}$ [22, Proposition 3.11]). Further, $u_{n}$ is
also not polyrec, because $2^{2^{n}}$ is polyrec, $C_{n}$ is not [12,
Corollary 4.1], and polyrec sequences are closed under sum and subtraction.

In [12, Theorem 7.1], the following property of ratrec sequences is proved: if
$\mathbf{u}$ is ratrec, then there exists $m\in\mathbb{N}$ and a cancelling
polynomial $P\in\mathbb{Q}[y_{0},\ldots,y_{m}]$, that is, a non-zero
polynomial such that

$P(u_{n},u_{n+1},\ldots,u_{n+m})=0\qquad\textrm{for all }n\in\mathbb{N}.$

######  Theorem 3.2 (Theorem 7.1 in [12]).

Every ratrec sequence admits a cancelling polynomial.

In [12, Theorem 5.3] it is shown that the sequence $u_{n}=n^{n}$ has no
cancelling polynomial, and hence is not polyrec and not ratrec.

##  4 Transcendence degrees

In this section we consider ratrec sequences as in Definition 3.1 over the
field $\mathbb{Q}(\mathbf{x})$. Let
$(\mathbf{F}^{(1)},\ldots,\mathbf{F}^{(k)})$ be a system defining
$\mathbf{F}^{(1)}$. In this section we will consider sequences with the
following fixed initial conditions: $F_{0}^{(i)}=x_{i}$. Note that this
technical assumption is important, in particular we cannot initialise
$F_{0}^{(i)}$ with elements in $\mathbb{Q}$. (If we could, this class would
generalise ratrec over the field $\mathbb{Q}$.)

Theorem 4.1 below formalises Theorem 1.2 and is the main result of this paper.
In essence, we show that a ratrec definition over $\mathbb{Q}(\mathbf{x})$ can
be translated to a simple ratrec over $\mathbb{Q}(\mathbf{x})$ with a
polynomial recursion depth. We hope that this insight might lead towards a
resolution of 1.1.

######  Theorem 4.1.

Let $\mathbf{F}^{(1)}$ be a ratrec sequence over the field
$\mathbb{Q}(\mathbf{x})$, defined by a system
$(\mathbf{F}^{(1)},\ldots,\mathbf{F}^{(k)})$, with the initial conditions:
$F_{0}^{(i)}=x_{i}$ for $i=1,\ldots,k$. Then there exists a rational function
$R\in\mathbb{Q}(y_{0},\ldots,y_{m})$ such that

$\displaystyle
F^{(1)}_{n+m+1}=R(F^{(1)}_{n},F^{(1)}_{n+1},\ldots,F^{(1)}_{n+m}),\text{ for
all }n\in\mathbb{N}.$

Moreover, if $F_{n}^{(1)}$ is of dimension $k$ and degree $D$, then $m$ can be
bounded from above by $k+k^{3}\log(kD)$.

Before we proceed to the proof, let us note that if we write
$R(y_{0},\ldots,y_{m})=\frac{A(y_{0},\ldots,y_{m})}{B(y_{0},\ldots,y_{m})}$,
where $A,B\in\mathbb{Q}[y_{0},\ldots,y_{m}]$, then Theorem 4.1 shows that the
following polynomial is cancelling for $\mathbf{u}^{(1)}$:

$P(y_{0},\ldots,y_{m},y_{m+1})=y_{m+1}\cdot
B(y_{0},\ldots,y_{m})-A(y_{0},\ldots,y_{m}).$

Thus, Theorem 4.1 shows (and in fact, is equivalent to) that every ratrec
sequence over $\mathbb{Q}(\mathbf{x})$ admits a cancelling polynomial that is
linear in the last variable (here $y_{m+1}$), improving upon Theorem 3.2.

The remainder of this section is devoted to the proof of Theorem 4.1 and to a
discussion related to it. In particular, the first part of the theorem
(existence) will be proved in Section 4.1 and the concrete bound on the depth
$m$ will be proved in Section 4.2.

Let us make a few observations about the sequences
$F_{n}^{(1)},\ldots,F_{n}^{(k)}$. First, a straightforward estimation shows
that the degrees of functions $F_{n}^{(1)},\ldots,F_{n}^{(k)}$ grow at most
single-exponentially in $n$.

######  Lemma 4.2.

For $n\in\mathbb{N}$, let $d_{n}$ be the maximum degree of
$F_{n}^{(1)},\dots,F_{n}^{(k)}$. Then $d_{n}\leqslant(k\cdot D)^{n}$.

######  Proof 4.3.

We proceed by induction on $n$. Initially we have $d_{0}=1$ by definition. By
Definition 3.1 $F_{n+1}^{(i)}$ is obtained by substituting rational functions
$F_{n}^{(1)},\ldots,F_{n}^{(k)}$ of degree at most $d_{n}$ into a rational
function $P_{i}$ of degree at most $D$. Let $P_{i}=\frac{A}{B}$ be the ratio
of two polynomials $A,B\in\mathbb{Q}[\mathbf{x}]$ of degree at most $D$. Let
$C\in\mathbb{Q}[\mathbf{x}]$ be the least common multiple of all denominators
of $F_{n}^{(1)},\ldots,F_{n}^{(k)}$, and thus of degree at most $k\cdot
d_{n}$. We can then write
$F_{n}^{(1)}=\frac{G^{(1)}}{C},\dots,F_{n}^{(k)}=\frac{G^{(k)}}{C}$, where the
numerators $G^{(1)},\dots,G^{(k)}\in\mathbb{Q}[\mathbf{x}]$ are polynomials of
degree also at most $k\cdot d_{n}$. It follows that both
$A(F_{n}^{(1)},\ldots,F_{n}^{(k)})$ and $B(F_{n}^{(1)},\ldots,F_{n}^{(k)})$
can be written as rational functions of the form $\frac{\hat{A}}{C^{D}}$,
resp., $\frac{\hat{B}}{C^{D}}$, where the numerators are polynomials
$\hat{A},\hat{B}\in\mathbb{Q}[\mathbf{x}]$ of degree at most $D\cdot k\cdot
d_{n}$ and the same holds for the common denominator
$C^{D}\in\mathbb{Q}[\mathbf{x}]$. It follows that $F_{n+1}^{(i)}$ is a
rational function of degree $d_{n+1}\leqslant k\cdot D\cdot d_{n}$, as
required.

The next lemma is a key property implied by the recurrence: if several
consecutive elements of the sequence $F_{n}^{(i)}$ satisfy some algebraic
constraint, then this constraint is also satisfied at every step later in the
sequence.

######  Lemma 4.4 (Substitution lemma).

Suppose $Z(y_{0},\dots,y_{m})\in\mathbb{Q}[y_{0},\dots,y_{m}]$ is a polynomial
such that $Z(F_{0}^{(i)}(\mathbf{x}),\dots,F_{m}^{(i)}(\mathbf{x}))=0$. Then
$Z(F_{n}^{(i)}(\mathbf{x}),\dots,F_{n+m}^{(i)}(\mathbf{x}))=0$ for all
$n\in\mathbb{N}$.

######  Proof 4.5.

By assumption we have

$\displaystyle Z(F_{0}^{(i)}(\mathbf{x}),\dots,F_{m}^{(i)}(\mathbf{x}))=0.$
(6)

Consider the ring homomorphism
$h\colon\mathbb{Q}[\mathbf{x}]\to\mathbb{Q}(\mathbf{x})$ that maps the
variables $x_{1},\ldots,x_{k}$ to rational functions
$F_{1}^{(1)},\ldots,F_{1}^{(k)}$, respectively. For a rational function $P/Q$
such that $h(Q)\neq 0$, by $h(P/Q)$ we understand the rational function
$h(P)/h(Q)$. (Note that such an extension of $h$ to $\mathbb{Q}(\mathbf{x})$
does not have to be a field homomorphism.) From the definition of the sequence
$F_{n}^{(i)}$ it readily follows that

$\displaystyle h(F_{n}^{(i)})=F_{n+1}^{(i)},\quad\text{for all
}n\in\mathbb{N}.$

Thus, by applying $h$ to both sides of (6), we infer that

$\displaystyle Z(F_{1}^{(i)}(\mathbf{x}),\dots,F_{m+1}^{(i)}(\mathbf{x}))=0.$

We conclude by repeating this reasoning $n$ times.

In the following we introduce some basic terminology about (commutative)
fields (c.f. [24, Sec. II.1], [11, Sec. V.3], or [17, Sec. 13.1 and 13.2] for
more details). Let $\mathbb{E},\mathbb{F}$ be two fields. When
$\mathbb{E}\subseteq\mathbb{F}$ we say that $\mathbb{F}$ is a _field
extension_ of $\mathbb{E}$, which is called the _base field_. The _degree_ of
$\mathbb{F}$ over $\mathbb{E}$, written $\deg_{\mathbb{E}}\mathbb{F}$, is the
dimension of $\mathbb{F}$ as a vector space over the base field $\mathbb{E}$.
For instance, $\mathbb{Q}(\sqrt{2})$ has degree 2 over $\mathbb{Q}$ (its
elements can be put in the form $a+b\cdot\sqrt{2}$) and
$\mathbb{Q}(\sqrt[3]{2})$ has degree 3 (its elements can be put in the form
$a+b\cdot\sqrt[3]{2}+c\cdot(\sqrt[3]{2})^{2}$). Field extensions need not have
finite degree. For instance, $\mathbb{Q}(\pi)$ and $\mathbb{Q}(x)$ are two
field extensions of $\mathbb{Q}$ of infinite degree. The degree is
multiplicative:

######  Lemma 4.6 (c.f. [17, Theorem 14]).

Consider field extensions $\mathbb{E}\subseteq\mathbb{F}\subseteq\mathbb{G}$.
Then,
$\deg_{\mathbb{E}}\mathbb{G}=\deg_{\mathbb{E}}\mathbb{F}\cdot\deg_{\mathbb{F}}\mathbb{G}$
(even for infinite degrees).

An element $f\in\mathbb{F}$ is _algebraic_ over the base field $\mathbb{E}$ if
there is a nonzero polynomial $P(x)\in\mathbb{E}[x]$ s.t. $P(f)=0$. The field
extension $\mathbb{F}$ is _algebraic_ over the base field $\mathbb{E}$ if
every element in $\mathbb{F}$ is algebraic over $\mathbb{E}$.

Let $\mathbb{F}$ be a field extension of $\mathbb{E}$. A subset
$\\{f_{1},\dots,f_{n}\\}\subseteq\mathbb{F}$ of elements of $\mathbb{F}$ is
_algebraically independent_ over $\mathbb{E}$ if there is no nonzero
polynomial $P(x_{1},\dots,x_{n})\in\mathbb{E}[x_{1},\dots,x_{n}]$ such that
$P(f_{1},\dots,f_{n})=0$. The _transcendence degree_ of $\mathbb{F}$ over
$\mathbb{E}$, denoted $\operatorname{tr\,deg}_{\mathbb{E}}\mathbb{F}$, is the
largest number of elements of $\mathbb{F}$ which are algebraically independent
over $\mathbb{E}$. Note that $\mathbb{F}$ is algebraic over $\mathbb{E}$ if
and only if $\operatorname{tr\,deg}_{\mathbb{E}}\mathbb{F}=0$. Like the
algebraic degree is multiplicative, the transcendence degree is additive:

######  Lemma 4.7 (c.f. [11, Corollary to Theorem 4, A.5.111]).

Consider field extensions $\mathbb{E}\subseteq\mathbb{F}\subseteq\mathbb{G}$.
Then,
$\operatorname{tr\,deg}_{\mathbb{E}}\mathbb{G}=\operatorname{tr\,deg}_{\mathbb{E}}\mathbb{F}+\operatorname{tr\,deg}_{\mathbb{F}}\mathbb{G}$.

In the following we will always take as the base field
$\mathbb{E}=\mathbb{Q}$, in which case we will write just
$\operatorname{tr\,deg}\mathbb{F}$ instead of
$\operatorname{tr\,deg}_{\mathbb{Q}}\mathbb{F}$. For example,
$\operatorname{tr\,deg}\mathbb{Q}(\sqrt{2})=0$ because $\sqrt{2}$ is an
algebraic number over $\mathbb{Q}$,
$\operatorname{tr\,deg}\mathbb{Q}(\sqrt{2},\pi)=1$ because $\pi$ is a
transcendental number, and
$\operatorname{tr\,deg}\mathbb{Q}(x_{1},\dots,x_{n})=n$.

Given a field extension $\mathbb{F}$ over $\mathbb{E}$ and elements
$f_{1},\dots,f_{n}\in\mathbb{F}$, let $\mathbb{E}(f_{1},\dots,f_{n})$ be the
smallest field extension over $\mathbb{E}$ containing $f_{1},\dots,f_{n}$. If
$\mathbb{F}=\mathbb{E}(f_{1},\dots,f_{n})$, then we say that $\mathbb{F}$ is
_finitely generated over $\mathbb{E}$_ (with _generators_
$f_{1},\dots,f_{n}$).

The motivation to look at field extensions is that a ratrec system naturally
defines the following sequence of field extensions

$\displaystyle\mathbb{Q}\subseteq\mathbb{F}_{0}\subseteq\mathbb{F}_{1}\subseteq\ldots\subseteq\mathbb{Q}(\mathbf{x}),$
(7)

where $\mathbb{F}_{0}=\mathbb{Q}(x_{1})$ and
$\mathbb{F}_{n+1}=\mathbb{F}_{n}(F_{n+1}^{(1)}(\mathbf{x}))$ for
$n\in\mathbb{N}$.

###  4.1 Ascending sequences of field extensions

In this section we prove the following Noether-like result.

######  Theorem 4.8.

Consider any ascending sequence of field extensions of the form

$\displaystyle\mathbb{Q}\subseteq\mathbb{F}_{0}\subseteq\mathbb{F}_{1}\subseteq\ldots\subseteq\mathbb{Q}(x_{1},\ldots,x_{k}).$

Then the sequence eventually stabilises: there exists $n_{0}$ such that
$\mathbb{F}_{n_{0}}=\mathbb{F}_{n_{0}+1}=\mathbb{F}_{n_{0}+2}=\ldots$.

The crucial reason for the result above is that the number $k$ of variables is
fixed. In the proof of Theorem 4.8 we use the following result on finitely
generated extensions.

######  Lemma 4.9 (c.f. [11, A.5.118, Cor. 3]).

If $\mathbb{G}$ is a finitely generated extension over $\mathbb{E}$, then
every subextension $\mathbb{E}\subseteq\mathbb{F}\subseteq\mathbb{G}$ of
$\mathbb{G}$ over $\mathbb{E}$ is also finitely generated.

######  Proof 4.10 (Proof of Theorem 4.8).

First of all, observe that

$\displaystyle\operatorname{tr\,deg}\mathbb{F}_{n}\leqslant\operatorname{tr\,deg}\mathbb{Q}(x_{1},\ldots,x_{k})=k,\quad\textrm{for
all }n.$

Hence, there is $n_{1}$ such that
$\operatorname{tr\,deg}\mathbb{F}_{n_{1}}=\operatorname{tr\,deg}\mathbb{F}_{n_{1}+1}=\cdots$.
Let $\mathbb{F}_{\infty}\coloneqq\bigcup_{n=0}^{\infty}\mathbb{F}_{n}$ and
consider the ascending sequence

$\displaystyle\mathbb{F}_{n_{1}}\subseteq\mathbb{F}_{n_{1}+1}\subseteq\cdots\subseteq\mathbb{F}_{\infty}.$
(8)

We have
$\operatorname{tr\,deg}\mathbb{F}_{n_{1}}=\operatorname{tr\,deg}\mathbb{F}_{n_{1}+i}$
for all $i>0$, and, by Lemma 4.7,
$\operatorname{tr\,deg}_{\mathbb{F}_{n_{1}}}\mathbb{F}_{n_{1}+i}=0$, i.e.,
$\mathbb{F}_{n_{1}+i}$ is algebraic over $\mathbb{F}_{n_{1}}$. Moreover,
$\mathbb{F}_{\infty}$ is also algebraic over $\mathbb{F}_{n_{1}}$ because any
element of $\mathbb{F}_{\infty}$ belongs to some $\mathbb{F}_{n_{1}+i}$. Since
$\mathbb{F}_{n_{1}}\subseteq\mathbb{Q}(x_{1},\ldots,x_{k})$ is a finitely
generated extension of $\mathbb{F}_{n_{1}}$ and
$\mathbb{F}_{n_{1}}\subseteq\mathbb{F}_{\infty}\subseteq\mathbb{Q}(x_{1},\ldots,x_{k})$
is a subextension of $\mathbb{F}_{n_{1}}$, by Lemma 4.9 we have that
$\mathbb{F}_{\infty}$ is also a finitely generated extension of
$\mathbb{F}_{n_{1}}$. In other words, there are generators
$f_{1},\dots,f_{m}\in\mathbb{F}_{\infty}$ such that

$\displaystyle\mathbb{F}_{\infty}=\mathbb{F}_{n_{1}}(f_{1},\dots,f_{m}).$

Since the generators $f_{1},\ldots,f_{m}$ are algebraic over
$\mathbb{F}_{n_{1}}$, $\mathbb{F}_{\infty}$ is an algebraic extension of
finite degree over $\mathbb{F}_{n_{1}}$ by Lemma 4.6. (Concretely, an upper
bound for the degree is the product of the degrees of minimal polynomials of
the generators $f_{1},\dots,f_{n}$.) It follows that the sequence in (8) is an
ascending sequence of vector subspaces of $\mathbb{F}_{\infty}$, where we
treat $\mathbb{F}_{\infty}$ as a vector space over $\mathbb{F}_{n_{1}}$. Since
the dimension of $\mathbb{F}_{\infty}$ as a vector space over
$\mathbb{F}_{n_{1}}$ is finite, this sequence must eventually stabilize at
$\mathbb{F}_{n_{0}}$ for some $n_{0}\geqslant n_{1}$.

We now prove the existence part of Theorem 4.1 using Theorem 4.8.

######  Proof 4.11 (Proof (of the first part of Theorem 4.1)).

By Theorem 4.8, the sequence in (7) stabilizes at some $\mathbb{F}_{m}$, that
is,

$\mathbb{F}_{m}=\mathbb{F}_{m+1}=\mathbb{F}_{m}(F_{m+1}^{(1)}(\mathbf{x})).$

Therefore, we have $F_{m+1}^{(1)}(\mathbf{x})\in\mathbb{F}_{m}$. Noting that
$\mathbb{F}_{m}=\mathbb{Q}(F_{0}^{(1)}(\mathbf{x}),\ldots,F_{m}^{(1)}(\mathbf{x}))$,
we see that $F_{m+1}^{(1)}(\mathbf{x})$ can be expressed as a rational
function of the generators: There exists a rational function
$R\in\mathbb{Q}(y_{0},\dots,y_{m})$ such that

$F_{m+1}^{(1)}(\mathbf{x})=R(F_{0}^{(1)}(\mathbf{x}),\dots,F_{m}^{(1)}(\mathbf{x})).$

We may now apply Lemma 4.4 to the numerator of the rational function
$R(y_{0},\ldots,y_{m})-y_{m+1}$, thus obtaining that

$\displaystyle
F_{n+m+1}^{(1)}(\mathbf{x})=R(F_{n}^{(1)}(\mathbf{x}),\dots,F_{n+m}^{(1)}(\mathbf{x})),\quad\textrm{for
every }n\in\mathbb{N}.$

###  4.2 Upper bound

We now move to the second, quantitative part of the proof of Theorem 4.1: we
need to prove that $m$ is bounded from above by $k+k^{3}\log(kD)$. For this,
we inspect the proof of Theorem 4.8 in the special case of the chain of
extensions (7) given by a ratrec system. The first observation is that the
sequence of transcendence degrees stabilises very quickly.

######  Lemma 4.12.

The transcendence degrees $\operatorname{tr\,deg}\mathbb{F}_{n}$ of the
sequence (7) stabilise after at most $k$ steps.

######  Proof 4.13.

As argued,
$\operatorname{tr\,deg}\mathbb{F}_{n}\leqslant\operatorname{tr\,deg}\mathbb{Q}(x_{1},\ldots,x_{k})=k$
for all $n$. The next extension $\mathbb{F}_{n+1}$ is obtained by adding a new
rational function $F_{n+1}^{(1)}(x_{1},\dots,x_{k})$ to the previous extension
$\mathbb{F}_{n}$. This immedately shows that
$\operatorname{tr\,deg}\mathbb{F}_{n}\leqslant\operatorname{tr\,deg}\mathbb{F}_{n+1}\leqslant\operatorname{tr\,deg}\mathbb{F}_{n}+1$.
We argue that if
$\operatorname{tr\,deg}\mathbb{F}_{m+1}=\operatorname{tr\,deg}\mathbb{F}_{m}$
for some $m$, then the transcendence degree cannot change anymore:
$\operatorname{tr\,deg}\mathbb{F}_{m}=\operatorname{tr\,deg}\mathbb{F}_{m+1}=\operatorname{tr\,deg}\mathbb{F}_{m+2}=\cdots$.
Note that this will conclude the proof, because then the transcendence degree
can increase at most $k$ times before eventually stabilizing.

Since
$\operatorname{tr\,deg}\mathbb{F}_{m+1}=\operatorname{tr\,deg}\mathbb{F}_{m}$,
it follows that $F_{m+1}^{(1)}(\mathbf{x})$ is algebraic over
$\mathbb{F}_{m}$, which means that it satisfies
$P(F_{m+1}^{(1)}(\mathbf{x}))=0$ for some nonzero polynomial
$P(x)\in\mathbb{F}_{n}[x]$. By clearing out denominators, there is a nonzero
polynomial $Z(y_{0},\dots,y_{m+1})\in\mathbb{Q}[y_{0},\dots,y_{m+1}]$ such
that

$\displaystyle Z(F_{0}^{(1)}(\mathbf{x}),\dots,F_{m+1}^{(1)}(\mathbf{x}))=0.$
(9)

By Lemma 4.4 we have

$\displaystyle
Z(F_{n}^{(1)}(\mathbf{x}),\dots,F_{n+m+1}^{(1)}(\mathbf{x}))=0\quad\textrm{for
every }n\in\mathbb{N}.$

This means that $F_{n+m+1}^{(1)}(\mathbf{x})$ is algebraic over
$\mathbb{F}_{n+m}$, implying

$\operatorname{tr\,deg}\mathbb{F}_{n+m+1}=\operatorname{tr\,deg}\mathbb{F}_{n+m}(F^{(1)}_{n+m+1}(\mathbf{x}))=\operatorname{tr\,deg}\mathbb{F}_{n+m}.$

This concludes the proof.

Note that even when the transcendence degrees of the fields in (7) stabilise,
it may still take several further steps until the fields themselves eventually
stabilise. We will later give an example that this may indeed happen.

We are left with estimating the degrees of field extensions after the
transcendence degree in the chain (7) stabilises. For this, we use the
following two results.

######  Lemma 4.14 (c.f. [23, Lemma 3.4]).

Let $f\in\mathbb{Q}(x_{1},\dots,x_{k})$ be algebraic over

$\mathbb{F}_{n}=\mathbb{Q}(F_{0}(x_{1},\dots,x_{k}),\dots,F_{n}(x_{1},\dots,x_{k})).$

Then there is a polynomial $Z(x)\in\mathbb{F}_{n}[x]$ of degree at most $\deg
F_{0}\cdots\deg F_{n}$ s.t. $Z(f)=0$.

######  Lemma 4.15 (c.f. [24, Exercise III.A.2]).

Let $\mathbb{Q}\subseteq\mathbb{F}\subseteq\mathbb{Q}(x_{1},\dots,x_{k})$ be a
subextension of $\mathbb{Q}(x_{1},\dots,x_{k})$ over $\mathbb{Q}$ of
transcendence degree
$r\coloneqq\operatorname{tr\,deg}_{\mathbb{Q}}\mathbb{F}$. Then there are
(algebraically independent) rational functions
$f_{1},\dots,f_{r}\in\mathbb{Q}(x_{1},\dots,x_{k})$ such that
$\mathbb{F}\subseteq\mathbb{Q}(f_{1},\dots,f_{r})$.

######  Lemma 4.16.

The sequence (7) eventually stabilizes after at most $k+k^{3}\log(kD)$ steps.

######  Proof 4.17.

By Lemma 4.12, there exists $j_{1}\leqslant k$ such that

$r\coloneqq\operatorname{tr\,deg}\mathbb{F}_{j_{1}}=\operatorname{tr\,deg}\mathbb{F}_{j}\quad\textrm{for
all }j\geqslant j_{1}.$

In particular, all field extensions $\mathbb{F}_{j}$ for $j\geqslant j_{1}$
are algebraic over $\mathbb{F}_{j_{1}}$. As in the proof of Theorem 4.8,
consider the field extension
$\mathbb{F}_{\infty}=\bigcup\limits_{j=0}^{\infty}\mathbb{F}_{j}$ over
$\mathbb{F}_{j_{1}}$, which is algebraic. In particular,
$\operatorname{tr\,deg}\mathbb{F}_{\infty}=r$. By Lemma 4.15, there are
rational functions $f_{1},\dots,f_{r}\in\mathbb{Q}(x_{1},\dots,x_{k})$ s.t.
$\mathbb{F}_{\infty}\subseteq\mathbb{Q}(f_{1},\dots,f_{r})$. Since
$\mathbb{Q}(f_{1},\dots,f_{r})$ has the same transcendence degree
$\operatorname{tr\,deg}\mathbb{Q}(f_{1},\dots,f_{r})=r$ as
$\mathbb{F}_{j_{1}}$, it follows that the $f_{i}$’s are algebraic over
$\mathbb{F}_{j_{1}}$. By Lemma 4.14, each $f_{i}$ is algebraic of degree at
most $\deg F_{0}\cdots\deg F_{j_{1}}$ over $\mathbb{F}_{j_{1}}$. It follows
that $\mathbb{Q}(f_{1},\dots,f_{r})$ is an algebraic extension of degree at
most $d=(\deg F_{0}\cdots\deg F_{j_{1}})^{r}$ over $\mathbb{F}_{j_{1}}$. Thus
the chain

$\displaystyle\mathbb{F}_{j_{1}}\subseteq\mathbb{F}_{j_{1}+1}\subseteq\mathbb{F}_{j_{1}+2}\subseteq\cdots$

is such that the degree of any $\mathbb{F}_{j_{1}+t}$ over
$\mathbb{F}_{j_{1}}$ is at most $d$. In particular, all extensions in this
chain are algebraic. We show that it stabilizes after at most $d$ steps.
Assume that for some $t\geqslant 0$ we have
$\mathbb{F}_{j_{1}+t}=\mathbb{F}_{j_{1}+t+1}$, that is
$F^{(1)}_{j_{1}+t+1}(\mathbf{x})\in\mathbb{F}_{j_{1}+t}$. Thus, there is a
rational function $R\in\mathbb{F}_{j_{1}}(y_{1},\ldots,y_{t})$ such that
$F^{(1)}_{j_{1}+t+1}(\mathbf{x})=R(F^{(1)}_{j_{1}+1}(\mathbf{x}),\ldots,F^{(1)}_{j_{1}+t}(\mathbf{x}))$.
Then by applying Lemma 4.4 to the numerator of
$R(y_{1},\ldots,y_{t})-y_{t+1}$, we may express
$F^{(1)}_{j_{1}+n+t+1}(\mathbf{x})$ as a rational function of
$F^{(1)}_{j_{1}+n+1}(\mathbf{x}),\ldots,F^{(1)}_{j_{1}+n+t}(\mathbf{x})$,
i.e., elements of $\mathbb{F}_{j_{1}+n+t}$. Hence an equality in the field
chain implies stabilization at this point.

Since the degree grows at each step before stabilization and the degree is
multiplicative, the chain stabilizes after at most $\log d$ steps, at
$\mathbb{F}_{j_{0}}$ for some $j_{0}\leqslant j_{1}+\log((\deg F_{0}\cdots\deg
F_{j_{1}})^{r})$. By Lemma 4.2 and since $j_{1}\leqslant k$ and $r\leqslant
k$, we have, as required,

$\displaystyle j_{0}$ $\displaystyle\leqslant j_{1}+r\log(\deg F_{0}\cdots\deg
F_{j_{1}})$ $\displaystyle\leqslant k+k\log((kD)^{0}\cdots(kD)^{k})$
$\displaystyle\leqslant k+k^{3}\log(kD).$

We are ready to provide the proof of the quantitative bound promised in
Theorem 4.1.

######  Proof 4.18 (Proof (of the second part of Theorem 4.1)).

It suffices to observe that $m$ in the proof the first part of Theorem 4.1 can
be bounded by $k+k^{3}\log(kD)$ thanks to Lemma 4.16.

We finish this section by giving an example that shows that in the proof of
Lemma 4.16, it may happen that $j_{1}<j_{0}$, that is, after the stabilisation
of the transcendence degree, there can be several non-trivial algebraic
extensions until the fields themselves stabilise. Consider the poly-rec system

$\displaystyle\left\\{\begin{array}[]{lcl}u^{(1)}_{n+1}&=&(u_{n}^{(1)})^{2}+(u_{n}^{(2)})^{2},\\\
u^{(2)}_{n+1}&=&u_{n}^{(1)}+u_{n}^{(2)}.\end{array}\right.$

We have $F^{(1)}_{0}=x_{1},F^{(2)}_{0}=x_{2}$, then
$F^{(1)}_{1}=x_{1}^{2}+x_{2}^{2},F^{(2)}_{1}=x_{1}+x_{2}$ and
$F^{(1)}_{2}=(x_{1}^{2}+x_{2}^{2})^{2}+(x_{1}+x_{2})^{2}$. The chain (7)
starts with

$\mathbb{Q}\subseteq\mathbb{F}_{0}=\mathbb{Q}(x_{1})\subseteq\mathbb{F}_{1}=\mathbb{F}_{0}(x_{1}^{2}+x_{2}^{2})=\mathbb{Q}(x_{1},x_{2}^{2})\subseteq\mathbb{F}_{2}.$

Note that $\operatorname{tr\,deg}\mathbb{F}_{0}=1$ and
$\operatorname{tr\,deg}\mathbb{F}_{1}=2$, which is the maximum value. However,
the next extension
$\mathbb{F}_{1}\subseteq\mathbb{F}_{2}=\mathbb{F}_{1}(F^{(1)}_{2})=\mathbb{F}_{1}(x_{1}x_{2})$
is non-trivial, because $x_{1}x_{2}$ does not belong to
$\mathbb{Q}(x_{1},x_{2}^{2})$. In fact, it is algebraic of degree 2.

###  4.3 Obstacles towards the zeroness problem for polyrec sequences

Theorem 4.1 suggests the following algorithm for deciding zeroness of a
polyrec sequence $\mathbf{u}$. Suppose the dimension of $\mathbf{u}$ is $k$
and the degree is $D$. We compute the first $p+2$ entries of $\mathbf{u}$,
where $p=k+k^{3}\lceil\log(kD)\rceil$, and we verify whether all of them are
zero. Obviously, if one of them is non-zero, then $\mathbf{u}$ is non-zero.
Otherwise, by Theorem 4.1, we expect that there is a rational function
$R(y_{0},\ldots,y_{m})$ for some $m\leqslant p$ such that

$u_{n+m+1}=R(u_{n},u_{n+1},\ldots,u_{n+m})\qquad\textrm{for all
}n\in\mathbb{N}.$ (10)

In particular,

$0=u_{m+1}=R(u_{0},\ldots,u_{m})=R(0,\ldots,0).$

Consequently,

$u_{m+2}=R(u_{1},\ldots,u_{m+1})=R(0,\ldots,0)=0,$

and a straightforward induction shows that $u_{n}=0$ for all $n\in\mathbb{N}$.
So we can declare that $\mathbf{u}$ is the zero sequence.

The reasoning above is incorrect for the following reason. By Theorem 4.1,
there is a rational function $R\in\mathbb{Q}(y_{0},\ldots,y_{m})$ such that
(10) holds when both sides are treated symbolically, as rational functions
over a set of $k$ variables $\mathbf{x}$ that denote the vector of initial
entries of the polyrec system defining $\mathbf{u}$. However, $R$ is a
rational function, hence when the variables are substituted with actual
entries of the sequence $\mathbf{u}$, we may get an accidental $0$ in the
denominator of the right hand side. In other words, assertion (10) may be
incorrect due to the right hand side being ill-defined, which renders the
remainder of the reasoning flawed. To exemplify the problem we now present an
example where this situation actually occurs.

Fix some $d\in\mathbb{N}$, and let

$P(x)=x(x-1)\dots(x-d+1).$

Define the sequence $\mathbf{u}$ by setting

$u_{n}=P(n)\qquad\text{for all }n\in\mathbb{N}.$

It is straightforward to see that $\mathbf{u}$ is polyrec of dimension $2$ and
degree $d$: one can simply use one auxiliary sequence $\mathbf{v}$ with
$v_{n}=n$.

Observe that if instead of setting $v_{0}=0$, we set $v_{0}=x$ for a formal
variable $x$, the same polyrec system defines a sequence of polynomials
$\widehat{\mathbf{u}}$ over $x$ defined as

$\widehat{u}_{n}=P(x+n)\qquad\text{for all }n\in\mathbb{N}.$

(Here, we also set initial condition $\widehat{u}_{0}=P(x)$.) Now, we may
apply the reasoning behind Theorem 4.1 to find the rational function
$R(y_{0},y_{1})\in\mathbb{Q}(y_{0},y_{1})$, defined as

$R(y_{0},y_{1})=y_{1}\cdot\frac{(d+1)\cdot y_{1}-y_{0}}{y_{1}+(d-1)\cdot
y_{0}},$

such that

$\widehat{u}_{n+2}=R(\widehat{u}_{n},\widehat{u}_{n+1})\qquad\textrm{for all
}n\in\mathbb{N}.$

This, however, should be regarded as an equality of two rational functions
over the variable $x$, which means that we cannot infer that

$u_{n+2}=R(u_{n},u_{n+1})\qquad\textrm{for all }n\in\mathbb{N},$

because the right hand side can be undefined for specific values; and indeed,
$R(0,0)$ is undefined. The flawed reasoning from the beginning of this section
would suggest that in order to verify the zeroness of $\mathbf{u}$, it
suffices to check that the first three entries of $\mathbf{u}$ are zero.
However, we have $u_{0}=u_{1}=\dots=u_{d-1}=0$ and $u_{d}=d!\neq 0$, so the
algorithm would provide an incorrect answer.

Notice that if we had a promise that we never encounter a division by zero
when recursively applying (10) from the given initial conditions, then the
naïve zeroness algorithm presented at the beginning of the section would be
sound. (The naïve algorithm is complete even without the promise.) However,
deciding whether no division by zero occurs is essentially the Skolem problem
for polyrec sequences, which, as mentioned in the introduction, is a long-
standing open problem.

We are hopeful that the problem with accidentally hitting a singularity of $R$
when starting from a polyrec sequence, as present in the example above, can
somehow be circumvented, hence we state the following conjecture.

######  Conjecture 4.19.

There is an elementary function $g\colon\mathbb{N}\to\mathbb{N}$ such that the
following holds. Suppose $\mathbf{u}$ is a polyrec sequence of dimension at
most $N$ and degree at most $N$ such that $u_{n}=0$ for all $n\leqslant g(N)$.
Then $u_{n}=0$ for all $n\in\mathbb{N}$.

Note that a positive resolution to 4.19 would immediately imply that the
complexity of the zeroness problem for polyrec sequences is elementary.

##  5 Conclusion

We believe that ratrec is a natural class of sequences with various promising
questions deserving further investigation. Questions about decision problems
are more natural for polyrec sequences due to their connection to polynomial
automata and the issues with division by $0$ in ratrec discussed in the
introduction. Nevertheless, as discussed in this paper, understanding the
properties of ratrec might lead to concrete complexity results for polyrec.
The most natural problem for future work is to overcome the obstacles
discussed in Section 4.3.

## References

  * [1] Rajeev Alur, Loris D’Antoni, Jyotirmoy V. Deshmukh, Mukund Raghothaman, and Yifei Yuan.  Regular functions and cost register automata.  In 28th Annual ACM/IEEE Symposium on Logic in Computer Science, LICS 2013, New Orleans, LA, USA, June 25-28, 2013, pages 13–22, 2013\.  doi:10.1109/LICS.2013.65.
  * [2] Corentin Barloy and Lorenzo Clemente.  Bidimensional linear recursive sequences and universality of unambiguous register automata.  In Markus Bläser and Benjamin Monmege, editors, Proc. of STACS’21, volume 187 of Leibniz International Proceedings in Informatics (LIPIcs), pages 8:1–8:15, Dagstuhl, Germany, 2021. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
  * [3] Corentin Barloy, Nathanaël Fijalkow, Nathan Lhote, and Filip Mazowiecki.  A robust class of linear recurrence sequences.  In 28th EACSL Annual Conference on Computer Science Logic, CSL 2020, January 13-16, 2020, Barcelona, Spain, pages 9:1–9:16, 2020.  doi:10.4230/LIPIcs.CSL.2020.9.
  * [4] M. Benedikt, T. Duff, A. Sharad, and J. Worrell.  Polynomial automata: Zeroness and applications.  In Proc. of LICS’17, pages 1–12, June 2017.  doi:10.1109/LICS.2017.8005101.
  * [5] Vincent D. 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–352:91–98, 2002.  Fourth Special Issue on Linear Systems and Control.  URL: http://www.sciencedirect.com/science/article/pii/S0024379501004669, doi:https://doi.org/10.1016/S0024-3795(01)00466-9.
  * [6] Adrien Boiret, Radoslaw Piórkowski, and Janusz Schmude.  Reducing transducer equivalence to register automata problems solved by “Hilbert Method”.  In Sumit Ganguly and Paritosh Pandya, editors, Proc. of FSTTCS’18, volume 122 of Leibniz International Proceedings in Informatics (LIPIcs), pages 48:1–48:16, Dagstuhl, Germany, 2018. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik.  URL: http://drops.dagstuhl.de/opus/volltexte/2018/9947, doi:10.4230/LIPIcs.FSTTCS.2018.48.
  * [7] Mikołaj Bojańczyk.  The Hilbert method for transducer equivalence.  ACM SIGLOG News, 6(1):5–17, February 2019.  URL: http://doi.acm.org/10.1145/3313909.3313911, doi:10.1145/3313909.3313911.
  * [8] Mikołaj Bojańczyk and Wojciech Czerwiński.  An automata toolbox, Feb 2018.  URL: https://www.mimuw.edu.pl/~bojan/paper/automata-toolbox-book.
  * [9] Mikołaj Bojańczyk and Janusz Schmude.  Some remarks on deciding equivalence for graph-to-graph transducers.  In Javier Esparza and Daniel Kráľ, editors, Proc. of MFCS’20, volume 170 of LIPIcs, pages 19:1–19:14, Dagstuhl, Germany, 2020\. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2020/12752, doi:10.4230/LIPIcs.MFCS.2020.19.
  * [10] Alin Bostan, Arnaud Carayol, Florent Koechlin, and Cyril Nicaud.  Weakly-unambiguous parikh automata and their link to holonomic series.  In Artur Czumaj, Anuj Dawar, and Emanuela Merelli, editors, Proc. of ICALP’20, volume 168 of LIPIcs, pages 114:1–114:16, Dagstuhl, Germany, 2020. Schloss Dagstuhl–Leibniz-Zentrum für Informatik.  URL: https://drops.dagstuhl.de/opus/volltexte/2020/12521, doi:10.4230/LIPIcs.ICALP.2020.114.
  * [11] N. Bourbaki.  Algebra II.  Elements of Mathematics. Springer Verlag Berlin Heidelberg, 2003.
  * [12] Michaël Cadilhac, Filip Mazowiecki, Charles Paperman, Michał Pilipczuk, and Géraud Sénizergues.  On polynomial recursive sequences.  Theory of Computing Systems, pages 1–22, 2021.
  * [13] N. Chomsky and M. P. Schützenberger.  The algebraic theory of context-free languages.  In P. Braffort and D. Hirschberg, editors, Computer Programming and Formal Systems, volume 35 of Studies in Logic and the Foundations of Mathematics, pages 118–161. Elsevier, 1963.  URL: http://www.sciencedirect.com/science/article/pii/S0049237X08720238, doi:10.1016/S0049-237X(08)72023-8.
  * [14] Lorenzo Clemente.  On the complexity of the universality and inclusion problems for unambiguous context-free grammars.  In Laurent Fribourg and Matthias Heizmann, editors, Proceedings 8th International Workshop on Verification and Program Transformation and 7th Workshop on Horn Clauses for Verification and Synthesis, Dublin, Ireland, 25-26th April 2020, volume 320 of EPTCS, pages 29–43. Open Publishing Association, 2020.  doi:10.4204/EPTCS.320.2.
  * [15] J. Denef and L. Lipshitz.  Decision problems for differential equations.  Journal of Symbolic Logic, 54(3):941–950, 1989.  doi:10.2307/2274755.
  * [16] Manfred Droste, Werner Kuich, and Heiko Vogler.  Handbook of Weighted Automata.  Springer, 1st edition, 2009.
  * [17] David S. Dummit and Richard M. Foote.  Abstract Algebra.  Wiley, 3rd edition, 2003.  URL: http://gen.lib.rus.ec/book/index.php?md5=36e6532b72807b9ef6b27e52e8c62ccc.
  * [18] Vojtěch Forejt, Petr Jančar, Stefan Kiefer, and James Worrell.  Language equivalence of probabilistic pushdown automata.  Information and Computation, 237:1–11, 2014.
  * [19] Vesa Halava, Tero Harju, Mika Hirvensalo, and Juhani Karhumäki.  Skolem’s problem - on the border between decidability and undecidability, 2005.
  * [20] T. Harju and J. Karhumäki.  The equivalence problem of multitape finite automata.  Theoretical Computer Science, 78(2):347–355, 1991.  URL: http://www.sciencedirect.com/science/article/pii/0304397591903567, doi:http://dx.doi.org/10.1016/0304-3975(91)90356-7.
  * [21] Manuel Kauers and Peter Paule.  The Concrete Tetrahedron - Symbolic Sums, Recurrence Equations, Generating Functions, Asymptotic Estimates.  Texts & Monographs in Symbolic Computation. Springer, 2011.  doi:10.1007/978-3-7091-0445-3.
  * [22] Leonard Lipshitz.  D-finite power series.  Journal of Algebra, 122(2):353–373, 1989.  URL: http://www.sciencedirect.com/science/article/pii/0021869389902226, doi:https://doi.org/10.1016/0021-8693(89)90222-6.
  * [23] J. Müller-Quade and R. Steinwandt.  Basic algorithms for rational function fields.  Journal of Symbolic Computation, 27(2):143–170, 1999.  URL: http://www.sciencedirect.com/science/article/pii/S0747717198902462, doi:https://doi.org/10.1006/jsco.1998.0246.
  * [24] Masayoshi Nagata.  Theory of Commutative Fields.  Translations of Mathematical Monographs, Vol. 125. American Mathematical Society, 1993.  URL: http://gen.lib.rus.ec/book/index.php?md5=249c3cba331671e0fd3c692d01b54b94.
  * [25] Joël Ouaknine and James Worrell.  On linear recurrence sequences and loop termination.  ACM SIGLOG News, 2(2):4–13, April 2015.  URL: http://doi.acm.org/10.1145/2766189.2766191, doi:10.1145/2766189.2766191.
  * [26] Christos H. Papadimitriou.  Computational Complexity.  Addison-Wesley, 1994.
  * [27] Azaria Paz.  Introduction to probabilistic automata.  Academic Press, 1971.
  * [28] Arto Salomaa and Marti Soittola.  Automata-theoretic aspects of formal power series.  Texts and Monographs in Computer Science. Springer, 1978.  URL: http://gen.lib.rus.ec/book/index.php?md5=1E7B3DCFFFC7F6146062637382E5067D, doi:10.1007/978-1-4612-6264-0.
  * [29] Bruno Salvy.  D-finiteness: Algorithms and applications.  In Proc. of ISAAC’05, pages 2–3, New York, NY, USA, 2005. ACM.  doi:10.1145/1073884.1073886.
  * [30] Marcel Paul Schützenberger.  On the definition of a family of automata.  Information and Control, 4(2–3):245–270, 1961.
  * [31] Helmut Seidl, Sebastian Maneth, and Gregor Kemper.  Equivalence of deterministic top-down tree-to-string transducers is decidable.  J. ACM, 65(4):21:1–21:30, April 2018.  URL: http://doi.acm.org/10.1145/3182653, doi:10.1145/3182653.
  * [32] Richard P. Stanley and Sergey Fomin.  Enumerative combinatorics, volume 2 of Cambridge studies in advanced mathematics.  Cambridge University Press, 1 edition, 2001.
  * [33] Joris van der Hoeven.  Computing with d-algebraic power series.  Applicable Algebra in Engineering, Communication and Computing, 30(1):17–49, 2019.  doi:10.1007/s00200-018-0358-y.
  * [34] Tzeng Wen-Guey.  On path equivalence of nondeterministic finite automata.  Information Processing Letters, 58(1):43–46, 1996.  URL: http://www.sciencedirect.com/science/article/pii/0020019096000397, doi:10.1016/0020-0190(96)00039-7.
  * [35] James Worrell.  Revisiting the equivalence problem for finite multitape automata.  In Fedor V. Fomin, Rūsiņš Freivalds, Marta Kwiatkowska, and David Peleg, editors, Proc. of ICALP’13, pages 422–433, Berlin, Heidelberg, 2013. Springer Berlin Heidelberg.
  * [36] Doron Zeilberger.  A holonomic systems approach to special functions identities.  Journal of Computational and Applied Mathematics, 32(3):321–368, 1990.  URL: http://www.sciencedirect.com/science/article/pii/037704279090042X, doi:10.1016/0377-0427(90)90042-X.

##  Appendix A Zeroness for polyrec is PSPACE-hard

In order to speak about computational aspects of poly-rec sequences, we need
to fix how they are encoded on input. For robustness, we choose to use
arithmetic circuits. Formally, for a fixed field $\mathbb{F}$, a polynomial
$P\in\mathbb{F}[x_{1},\ldots,x_{k}]$ is encoded by a circuit $C$ that may use
the following gates:

  * •

binary addition and multiplication gates;

  * •

nullary input gates, bijectively labelled with variables $x_{1},\ldots,x_{k}$;
and

  * •

nullary constant gates, each labelled with an element of $\mathbb{F}$.

Note that subtraction can be emulated using addition and multiplication by the
constant $-1$. One of the gates is designated as the output gate. Given a
valuation of variables with elements of $\mathbb{F}$, the values of the gates
can be computed as expected, and the value yielded by the circuit $C$ is the
one computed for the output gate.

In this section we prove the following lower bound.

######  Theorem A.1.

For every fixed field $\mathbb{F}$, the zeroness problem for polyrec sequences
over $\mathbb{F}$ is PSPACE-hard.

The lower bound claimed in the introduction follows from the theorem above by
taking $\mathbb{F}=\mathbb{Q}$. Note also that together with Theorem A.2
below, we can conclude that the problem is actually PSPACE-complete for every
fixed finite field $\mathbb{F}$.

######  Theorem A.2.

For every fixed finite field $\mathbb{F}$, the zeroness problem for polyrec
sequences over $\mathbb{F}$ is in PSPACE.

######  Proof A.3.

Let $m$ be the cardinality of $\mathbb{F}$; note that $m$ is a fixed constant.
A standard periodicity argument, e.g. as in the proof of [12, Theorem 4.1],
shows that if $\mathbf{u}$ is a polyrec sequence of dimension $k$, then it is
zero if, and only if, it is zero for the first $m^{k}$ steps. We can check the
latter condition by storing in memory a $k$-tuple of values and computing the
first $m^{k}$ values of the sequence, which takes an amount of space which is
polynomial in $k$.

###  A.1 Extended polyrec sequences

In the reductions leading to the lower bound of Theorem A.1 it is convenient
to construct polyrec sequences according to a definition slightly more general
than what we allowed in Definition 3.1. Namely, the definition of an _extended
polyrec system_ is the same as before, except that we generalize the format of
the $i$th equation $u^{(i)}_{n+1}=P_{i}(\cdots)$ by allowing $u^{(i)}_{n+1}$
to additionally depend on $u^{(1)}_{n+1},\dots,u^{(i-1)}_{n+1}$. Thus, the
$i$th equation takes the form:

$u^{(i)}_{n+1}=P_{i}(u^{(1)}_{n},\dots,u^{(k)}_{n},u^{(1)}_{n+1},\dots,u^{(i-1)}_{n+1}),$
(11)

where now $P_{i}$ is a polynomial in $k+i-1$ variables. This more relaxed
definition will help focus on the important aspects of the reduction presented
in the rest of this section. The following lemma shows that the modification
does not affect the complexity of the zeroness problem.

######  Lemma A.4.

Suppose $\mathbf{u}$ is a sequence defined by an extended polyrec system $S$
of dimension $k$, where each polynomial $P_{i}$ is represented by circuit
$C_{i}$. Then given the circuits $C_{i}$, one can in polynomial time construct
a circuit $C$ that represents a polyrec system $S^{\prime}$ of dimension $k$
that also defines $\mathbf{u}$ (with the same initial condition as $S$).

######  Proof A.5.

Let the input gates of circuit $C_{i}$ be labelled with
$x_{1},\ldots,x_{k},z_{1},\ldots,z_{i-1}$, where variables
$z_{1},\ldots,z_{i-1}$ respectively correspond to the values
$u^{(1)}_{n+1},\dots,u^{(i-1)}_{n+1}$ in (11). Construct the circuit $C$ from
the union of circuits $C_{1},\ldots,C_{k}$ by performing the following
operations for each $i\in\\{1,\ldots,k\\}$:

  * •

Fuse all input gates labelled $x_{i}$ in circuits $C_{1},\ldots,C_{k}$ into a
single input gate labelled $x_{i}$.

  * •

Fuse the output gate of $C_{i}$ with all input gates labelled $z_{i}$ in
circuits $C_{i+1},\ldots,C_{k}$.

The output gates of $C$ are the output gates of $C_{1},\ldots,C_{k}$.
(Formally, we assumed that output gates must have fan-out $0$, but this can be
easily obtained by making a copy of each output gate.) It is straightforward
to verify that the polyrec system $S^{\prime}$ that $C$ represents defines the
same $k$-tuple of sequences as $S$ under the same initial condition.

###  A.2 Reduction

We now proceed to the proof of Theorem A.1. Let us fix the field $\mathbb{F}$;
in the reduction we will use only two constants from $\mathbb{F}$, namely $0$
and $1$. We reduce from the validity problem for Quantified Boolean Formulas
(QBF), which is known to be PSPACE-complete (see, e.g., [26, Theorem 19.1]).
Recall that the QBF validity problem amounts to determine whether a given QBF
of the form

$\displaystyle\psi=\exists x_{1}\ \forall x_{2}\ \ldots\ Q_{k}x_{k}\
\varphi(x_{1},\ldots,x_{k})$ (12)

is true, where $\varphi(x_{1},\ldots,x_{k})$ is quantifier-free, the variables
with odd indices are quantified existentially, the remaining variables are
quantified universally, and $Q_{k}$ is either $\exists$ or $\forall$ depending
on the parity of $k$. Hence, we are given a QBF $\psi$ and we wish to
construct, in polynomial time, a polyrec system $S$ and its initial condition
that define a sequence $\mathbf{u}$ over $\mathbb{F}$ such that the zeroness
of $\mathbf{u}$ is equivalent to the invalidity of $\psi$. By Lemma A.4, it
suffices to construct an extended polyrec system $S$ with this property, where
each polynomial $P_{i}$ involved is represented by a separate circuit. In the
following, the size of an extended polyrec system is the total size of its
representation through circuits, which is constructed implicitly.

In the reduction it will be convenient to consider formulas obtained by fixing
the truth values of a subset of the bound variables of $\psi$. For every
$i\in\\{0,\ldots,k\\}$ and $c_{i+1},\ldots,c_{k}\in\\{0,1\\}$ we define the
formula

$\displaystyle\psi|_{c_{i+1},\ldots,c_{k}}=\exists x_{1}\forall x_{2}\cdots
Q_{i}x_{i}\;\varphi(x_{1},\ldots,x_{i},c_{i+1},\ldots,c_{k}),$

where $Q_{i}$ is either $\exists$ or $\forall$ depending on the parity of $i$.
In particular, for $i=k$ we get back $\psi$, and for $i=0$ the formula
$\psi|_{c_{1},\ldots,c_{k}}$ reduces to the truth value of
$\varphi(c_{1},\ldots,c_{k})$. We encode a quantifier Boolean formula
$\varphi$ into a polynomial $P_{\varphi}$ using the following simulation of
Boolean operators $\neg$, $\wedge$ and $\vee$ by arithmetic operations:

$\displaystyle\begin{split}P_{x}&=x,\\\ P_{\neg\varphi}&=1-P_{\varphi},\\\
P_{\varphi\land\psi}&=P_{\varphi}\cdot P_{\psi},\\\
P_{\varphi\lor\psi}&=P_{\neg(\neg\varphi\land\neg\psi)}.\end{split}$ (13)

For example, $\tau(x,y)=(x\wedge y)\vee\neg y$ is encoded as
$P_{\tau}(x,y)=1-(1-xy)y$. The following straightforward claim shows that with
the standard interpretation of $1$ and $0$ representing true, resp., false,
such polynomials evaluate as expected. Note that this claims holds in any
fixed field.

######  Claim 1.

Let $\tau(x_{1},\ldots,x_{k})$ be a Boolean formula and
$P_{\tau}(x_{1},\ldots,x_{k})$ its corresponding polynomial. For every
$c_{1},\ldots,c_{k}\in\\{0,1\\}$ we have
$P_{\tau}(c_{1},\ldots,c_{k})\in\\{0,1\\}$ and

$(c_{1},\ldots,c_{k})\models\tau\iff P_{\tau}(c_{1},\ldots,c_{k})=1.$

To ease the notation we will directly write formulas as polynomials; for
instance, $P_{\tau}(x,y)=(x\wedge y)\vee\neg y$. All sequences in this section
will be over $\\{0,1\\}$ and the involved polynomials will be of the form
$P_{\tau}$.

#### Sequences $\mathbf{c}^{1},\ldots,\mathbf{c}^{k}$

The truth valuations of variables $x_{1},\dots,x_{k}$ will be encoded by
sequences $\mathbf{c}^{1},\ldots,\mathbf{c}^{k}$, where for every $i$ and $n$
we have

$\displaystyle\begin{split}c^{i}_{n}=\begin{cases}0&\text{ if }n\bmod
2^{i}\text{ is less than }2^{i-1},\\\ 1&\text{
otherwise.}\end{cases}\end{split}$ (14)

For example, the first eight values of
$\mathbf{c}^{1},\mathbf{c}^{2},\mathbf{c}^{3}$ are

$\mathbf{c}^{1}$ | = | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
---|---|---|---|---|---|---|---|---|---|---
$\mathbf{c}^{2}$ | = | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
$\mathbf{c}^{3}$ | = | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | .

######  Claim 2.

For every $i\geqslant 1$, the sequence $\mathbf{c}^{i}$ is definable by an
extended polyrec system over $\mathbb{F}$ of size polynomial in $i$.

We proceed by induction on $i$. For $i=1$, by definition we have
$c^{1}_{n}=1-c^{1}_{n-1}$, and thus we let

$\displaystyle c^{1}_{n}=P(c^{1}_{n-1}),\text{ with }P(x)=\neg x.$ (15)

Now, suppose $i>1$ and we have defined $\mathbf{c}^{i-1}$. We start by proving
the following equality for every $n>1$

$\displaystyle c^{i}_{n}=\begin{cases}1-c^{i}_{n-1}&\text{ if
}c^{i-1}_{n-1}=1\text{ and }c^{i-1}_{n}=0;\\\ c^{i}_{n-1}&\text{
otherwise.}\end{cases}$ (16)

Notice that $\mathbf{c}^{i}$ is periodic with period $2^{i}$, i.e.,
$c^{i}_{n}=c^{i}_{n+2^{i}}$ for all $n$. Thus it suffices to prove (16) for
$n\in\\{1,\ldots,2^{i}\\}$. By definition, $c^{i-1}_{n-1}=1$ and
$c^{i-1}_{n}=0$ hold precisely for two values of $n\in\\{1,\ldots,2^{i}\\}$,
namely for $n=2^{i-1}$ and $n=2^{i}$. Thus (16) is proved since $c^{i}_{n}=0$
for $0\leqslant n<2^{i-1}$; $c^{i}_{n}=1$ for $2^{i-1}\leqslant n<2^{i}$; and
$c^{i}_{2^{i}}=0$.

Using (16) one can determine $c^{i}_{n}$ given $c^{i}_{n-1}$, $c^{i-1}_{n-1}$,
and $c^{i-1}_{n}$:

$\displaystyle c^{i}_{n}=Q(c^{i}_{n-1},c^{i-1}_{n-1},c^{i-1}_{n}),$ (17)

where $Q(x,y,z)=\left(\neg x\wedge(y\wedge\neg z)\right)\vee\left(x\wedge(\neg
y\vee z)\right)$. This follows from (16) and from the fact that $y\wedge\neg
z$ and $\neg y\vee z$ are mutually exclusive formulas encoding the “if”
condition in (16). It is clear that the constructed extended polyrec system is
of size polynomial in $i$.

#### Sequences $\mathbf{d}^{0},\ldots,\mathbf{d}^{k}$

We define sequences $\mathbf{d}^{0},\ldots,\mathbf{d}^{k}$, where for any
$i\geqslant 0$ we have:

$\displaystyle\begin{split}d^{i}_{0}=0,\quad d^{i}_{n}=\begin{cases}0&\text{
if }2^{i}\not\divides\ n\\\
\left\llbracket\psi|_{c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}\right\rrbracket&\text{
otherwise,}\end{cases}\end{split}$ (18)

where for a closed formula $\xi$ (i.e., with no free variables)
$\left\llbracket\xi\right\rrbracket$ is $1$ if $\xi$ is true and $0$
otherwise. Notice that the formula depends on $\mathbf{c}^{1}$, …,
$\mathbf{c}^{k}$. Since $\mathbf{d}^{k}$ is the zero sequence if, and only if,
$\psi$ is false, it suffices to show that each $\mathbf{d}^{i}$ can be defined
by an extended polyrec system of polynomial size.

We proceed by induction on $i$. In the base case $i=0$,

$\displaystyle d_{n}^{0}=P_{\varphi}(c^{1}_{n-1},\ldots,c^{k}_{n-1}),$ (19)

where $P_{\varphi}$ is the polynomial obtained from the quantifier-free
formula $\varphi$ according to the rules in (13). (Notice that $P_{\varphi}$
can be represented by an arithmetic circuit of size polynomial in the size of
$\varphi$—this is where we use the conciseness of representation using
circuits.) This fulfills the conditions in (18) since, for $n>0$,
$d_{n}^{0}=1$ if $(c^{1}_{n-1},\ldots,c^{k}_{n-1})\models\varphi$ and
$d_{n}^{0}=0$ otherwise.

Now, fix $i\geqslant 1$ and suppose that $\mathbf{d}^{i-1}$ is defined. The
goal is to define $\mathbf{d}^{i}$. Recall that if $i$ is odd then $x_{i}$ is
quantified existentially, and otherwise $x_{i}$ is quantified universally.

######  Claim 3.

Let $\circledast_{i}=\vee$ if $i$ is odd and $\circledast_{i}=\wedge$ if $i$
is even. For every $n>0$ and $0<i\leqslant k$, we have

$\displaystyle\begin{split}d^{i}_{n}=\begin{cases}d^{i-1}_{n}\circledast_{i}d^{i-1}_{n-2^{i-1}}&\text{
if }2^{i}\divides n\\\ 0&\text{ otherwise.}\end{cases}\end{split}$ (20)

We may focus only on the case $2^{i}\divides n$. Since $x_{i}$ is quantified
according to the parity of $i$, we have

$\displaystyle\psi|_{c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}=\psi|_{0,c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}\;\circledast_{i}\;\psi|_{1,c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}.$

We claim that

$\displaystyle d^{i-1}_{n}=\psi|_{1,c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}\ \text{
and }\ d^{i-1}_{n-2^{i-1}}=\psi|_{0,c^{i+1}_{n-1},\ldots,c^{k}_{n-1}}.$

By (14) and the fact that $2^{i}\divides n$, we get
$c^{i}_{n-1}=c^{i}_{2^{i}-1}=1$, which proves the first equation. For the
second equation, we observe that $c^{i}_{(n-1)-2^{i-1}}=c^{i}_{2^{i-1}-1}=0$
and that $c^{j}_{(n-1)-2^{i-1}}=c^{j}_{n-1}$ for all $j>i$. The latter
assertion readily follows from $2^{i}\divides n$ and (14).

As an immediate consequence of Claim 3, we can write

$\displaystyle
d^{i}_{n}=S(d^{i-1}_{n},d^{i-1}_{n-2^{i-1}},c^{i-1}_{n-1},c^{i-1}_{n}),$ (21)

where $S(x,y,z,t)=(x\circledast_{i}y)\wedge(z\wedge\neg t)$ (by recalling that
$c^{i-1}_{n-1}=1,c^{i-1}_{n}=0$ holds if, and only if, $2^{i}\divides n$,
where $n>0$). The issue with this recursive definition is that it requires
access to the value $d^{i-1}_{n-2^{i-1}}$, which in general is not allowed in
a polyrec system for $i\geqslant 2$ (not even in the extended variant). This
will be addressed in the next section by introducing the last family of
recursive sequences.

#### Sequences $\mathbf{f}^{0},\dots,\mathbf{f}^{k-1}$

For every $1\leqslant i\leqslant k$, the sequence $\mathbf{f}^{i-1}$ is
defined as

$\displaystyle f_{n}^{i-1}=\begin{cases}0&\text{ if }n\bmod 2^{i}\text{ is
less than }2^{i-1}\\\ d^{i-1}_{m}&\text{ otherwise,}\end{cases}$

where $m\leqslant n$ is the unique number such that $n-m<2^{i-1}$ and
$2^{i-1}\divides m$. Thus, $\mathbf{f}$ is divided into blocks of length
$2^{i-1}$ of equal elements, where every other block is either filled with
zeros, or its value is determined by the value of an appropriate entry
$d^{i-1}_{m}$. Observe that in particular, if $2^{i}\divides n$ then
$f_{n-1}^{i-1}=d^{i-1}_{n-2^{i-1}}$. Thus, intuitively, the sequence
$\mathbf{f}^{i-1}$ is a “memory” that allows us to store the relevant value of
$\mathbf{d}^{i-1}$ from $2^{i-1}-1$ steps back.

We now proceed to defining sequences $\mathbf{f}^{0},\ldots,\mathbf{f}^{k-1}$
using polyrec systems. Observe that $f_{0}^{i-1}=0$ and for $n>0$, we can
write

$\displaystyle\begin{split}f_{n}^{i-1}=\begin{cases}d^{i-1}_{n}&\text{ if
}c^{i-1}_{n-1}=0\text{ and }c^{i-1}_{n}=1;\\\ 0&\text{ if
}c^{i-1}_{n-1}=1\text{ and }c^{i-1}_{n}=0;\\\ f_{n-1}^{i-1}&\text{
otherwise.}\end{cases}\end{split}$ (22)

Notice that the value of $f_{n}^{i-1}$ is copied from $f_{n-1}^{i-1}$ unless
$c^{i-1}_{n-1},c^{i-1}_{n}$ differ. To conclude, recall from (14) that this
happens if, and only if, $2^{i-1}\divides n$.

######  Claim 4.

For every $i\geqslant 1$, the sequences $\mathbf{d}^{i}$ and
$\mathbf{f}^{i-1}$ are definable by extended polyrec systems over $\mathbb{F}$
of size polynomial in $i$ and the size of $\varphi$.

Using (22), we may write $\mathbf{f}^{i-1}$ as an extended polyrec sequence
$f_{0}^{i-1}=0$ and, for $n>0$,

$\displaystyle
f^{i-1}_{n}=R(c^{i-1}_{n-1},c^{i-1}_{n},d^{i-1}_{n},f^{i-1}_{n-1}),$ (23)

where

$R(x,y,z,t)=(z\wedge(\neg x\wedge y))\vee(t\wedge((x\wedge y)\vee(\neg
x\wedge\neg y)).$

In turn, this allows us to rewrite (21) as

$\displaystyle
d^{i}_{n}=S(d^{i-1}_{n},f^{i-1}_{n-1},c^{i-1}_{n-1},c^{i-1}_{n}),$ (24)

where $S$ was defined in (21). Note that (23) and (24) are in the extended
polyrec format provided that we write the equations for the $\mathbf{f}^{i}$’s
after the equations for the $\mathbf{d}^{i}$’s, and the latter after the
equations for $\mathbf{c}^{i}$’s (in order to avoid creating a cyclic
dependency). In other words, the final extended polyrec system consists of
equations (17), followed by (24), and followed by (23), where each set of
equations is numbered naturally according to the indices of sequences.

The involved polynomials $P_{\varphi}$, $R$ and $S$ are all of size polynomial
in the input size when represented as arithmetic circuits ($R$ and $S$ are
even of constant size), and we have a polynomial number of equations. Thus,
the definition above is an extended polyrec system of polynomial size.

As discussed, Claim 4 finishes the proof of Theorem A.1.

In the end, we discuss the Skolem problem: given a sequence $\mathbf{u}$ to
determine whether there is $n$ such that $u_{n}=0$. This problem was
extensively studied for the class of linear recursive sequences (see e.g.
[25]). For linear recursive sequences it is open whether the Skolem problem is
decidable, but only NP-hardness is known [5, Corollary 2.1]. For polyrec
sequences, decidability of the Skolem problem is also open, but we can improve
the lower bound.

######  Corollary A.6.

The Skolem problem is PSPACE-hard for polyrec sequences.

######  Proof A.7.

Notice that in the proof of Theorem A.1 we define a system of sequences over
$\\{0,1\\}$. It remains to observe that for such sequences the zeroness
problem and the Skolem problem reduce to each other. Indeed, the nonzeroness
problem of a sequence $\mathbf{u}$ over $\\{0,1\\}$ is equivalent to the
Skolem problem of $\mathbf{v}$ defined as $v_{n}=1-u_{n}$.

We conclude this section by noting that the reduction from QBF that we have
presented produces a polyrec sequence which is identically zero if and only if
the first exponentially many initial values thereof are zero. We are not aware
of examples requiring longer witnesses of zeroness for polyrec sequences.