User:GaseousButter/sandbox

Unsolved problem in mathematics:

Is there an algorithm to test whether a linear recurrence sequence has a zero?

(more unsolved problems in mathematics)

In mathematics, the Skolem problem is the problem of determining whether the values of a linear recurrence sequence include the number zero. The problem can be formulated for recurrences over different types of numbers, including integers, rational numbers, and algebraic numbers. It is not yet known whether there exists an algorithm that can solve this problem, with only special cases and conditional results known. The Skolem problem is named after Thoralf Skolem, due to his 1933 paper proving the Skolem–Mahler–Lech theorem for rational sequences, which describes the structure of the set of zeroes of a linear recurrence sequence.

There does exist an algorithm to test whether a linear recurrence sequence has infinitely many zeros, and if so to construct a decomposition of the positions of those zeros into periodic subsequences, based on the algebraic properties of the roots of the characteristic polynomial of the given recurrence. The remaining difficult part of the Skolem problem is determining whether the finite set of non-repeating zeros is empty or not.

Partial solutions to the Skolem problem are known, covering the special case of the problem for recurrences of order at most four. However, these solutions do not apply to recurrences of order five or more.

The Skolem Problem can be seen as a linear version of the Halting problem, which is known to be undecidable. It has been said by Terrence Tao that it is "faintly outrageous that this problem is still open", as we do not yet know how to decide the Halting problem for even "linear" automata.

For integer recurrences, the Skolem problem is known to be NP-hard.

Motivation

A linear recurrence sequence (often shortened to LRS) is a sequence $\mathbf {u} =\langle u_{n}\rangle _{n=0}^{\infty }$ satisfying a recurrence relation $$u_{n+d}=a_{d-1}u_{n+d-1}+\dots +a_{0}u_{n}$$and defined by initial values $u_{0},\dots ,u_{d-1}$. If $d$ is the smallest integer such that $\mathbf {u}$ satisfies a recurrence relation of the form above then we say $\mathbf {u}$ has order $d$. If the initial values and the coefficients $a_{0},\dots ,a_{d-1}$ lie in a ring $R$ then we call $\mathbf {u}$ an $R$-LRS (for example, an integer-valued linear recurrence sequence is called a $\mathbb {Z}$-LRS). The Skolem problem asks whether a given LRS $\mathbf {u}$ has a zero, that is, whether there is an integer $n$ such that $u_{n}=0$.

As an example, consider the Fibonacci sequence $\langle F_{n}\rangle _{n=0}^{\infty }$ defined by the the recurrence relation$$F_{n+2}=F_{n+1}+F_{n}$$and the initial values $F_{0}=F_{1}=1$. This defines a $\mathbb {Z}$-LRS which starts $1,1,2,3,5,8,13\dots$ and is order 2. In this case, the solution to the Skolem Problem is clear - the values of the sequence are increasing and so never reach 0, so there is no zero in the sequence. However, if we had different initial values, the problem could be less clear. For the general case, a helpful fact is the well known result that any sequence $\langle F_{n}\rangle _{n=0}^{\infty }$ which satisfies the recurrence relation above takes the general form$$F_{n}=A\left({\frac {1+{\sqrt {5}}}{2}}\right)^{n}+B\left({\frac {1-{\sqrt {5}}}{2}}\right)^{n}$$for some constants $A,B$ depending on the initial values, and where we call ${\frac {1+{\sqrt {5}}}{2}},{\frac {1-{\sqrt {5}}}{2}}$ the characteristic roots of the characteristic polynomial $g(X)=X^{2}-X-1$ that arises from the recurrence relation. It is relatively straightforward to see that (if $A,B\neq 0$) the first term of the general form will dominate as $n$ increases, so when $n$ is large enough, $F_{n}$ is large and guaranteed to be non-zero. This provides an idea for an algorithm for the Skolem problem - check the first few values of $F_{n}$ for zeroes until $n$ is large enough that $F_{n}$ is guaranteed to be non-zero. This idea is used in the proof of decidability for low orders.

Decidability for low orders

Terminology and background

If $\mathbf {u} =\langle u_{n}\rangle _{n=0}^{\infty }$ is an algebraic LRS satisfying the recurrence relation$$u_{n+d}=a_{d-1}u_{n+d-1}+\dots +a_{0}u_{n}$$then we define its characteristic polynomial by $g(X)=X^{d}-a_{d-1}X^{d-1}-\dots -a_{0}$. We call the roots $\lambda _{1},\dots ,\lambda _{s}$ of $g$ the characteristic roots of $\mathbf {u}$. The $n$th term of the sequence admits the following exponential polynomial representation:$$u_{n}=\sum _{n=1}^{s}P_{i}(n)\lambda _{i}^{n}$$where each $P_{i}$ is a polynomial with degree one less than the multiplicity of $\lambda _{i}$ as a root of $g$. If $|\cdot |_{v}$ is some absolute value (non-Archimedean or Archimedean) and (after reordering the characteristic roots) we have$$|\lambda _{1}|_{v}=\dots =|\lambda _{r}|_{v}>|\lambda _{r+1}|\geq \dots \geq |\lambda _{s}|$$then we say that $\lambda _{1},\dots \lambda _{r}$ are dominant with respect to $|\cdot |_{v}$. If any ratio $\lambda _{i}/\lambda _{j}$ for some $i\neq j$ is a root of unity then we say $\mathbf {u}$ is degenerate. It is a known result that, given an algebraic LRS $\mathbf {u}$ we may compute a constant $M$ such that each subsequence $\langle u_{Mn+\ell }\rangle _{n=0}^{\infty }$ for $\ell =0,\dots ,M-1$ is either identically zero or non-degenerate. Therefore, since finding zeroes of a sequence is equivalent to finding them in its subsequences, analysis of the Skolem problem can largely be restricted to non-degenerate sequences.

Decidability up to order 4

The Skolem problem is known to be decidable for algebraic sequences of order at most 4.

PLACEHOLDERPLACEHOLDER

on the zeros of a sequence satisfying a linear recurrence with constant coefficients. This theorem states that, if such a sequence has zeros, then with finitely many exceptions the positions of the zeros repeat regularly. Skolem proved this for recurrences over the rational numbers, and Mahler and Lech extended it to other systems of numbers. However, the proofs of the theorem do not show how to test whether there exist any zeros (i.e. if any of these finite exceptions exist).

PLACEHOLDERPLACEHOLDER