Skolem problem

Last updated
Unsolved problem in mathematics:
Is there an algorithm to test whether a constant-recursive sequence has a zero?
(more unsolved problems in mathematics)

In mathematics, the Skolem problem is the problem of determining whether the values of a constant-recursive 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 known whether there exists an algorithm that can solve this problem. [1]

Contents

A linear recurrence relation expresses the values of a sequence of numbers as a linear combination of earlier values; for instance, the Fibonacci numbers may be defined from the recurrence relation

F(n) = F(n − 1) + F(n − 2)

together with the initial values F(0) = 0 and F(1) = 1. The Skolem problem is named after Thoralf Skolem, because of his 1933 paper proving the Skolem–Mahler–Lech theorem on the zeros of a sequence satisfying a linear recurrence with constant coefficients. [2] 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.

There does exist an algorithm to test whether a constant-recursive 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. [3] The remaining difficult part of the Skolem problem is determining whether the finite set of non-repeating zeros is empty or not. [1]

Partial solutions to the Skolem problem are known, covering the special case of the problem for recurrences of degree at most four. However, these solutions do not apply to recurrences of degree five or more. [1] [4] [5]

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

See also

Related Research Articles

<span class="mw-page-title-main">Diophantine equation</span> Polynomial equation whose integer solutions are sought

In mathematics, a Diophantine equation is an equation, typically a polynomial equation in two or more unknowns with integer coefficients, for which only integer solutions are of interest. A linear Diophantine equation equates to a constant the sum of two or more monomials, each of degree one. An exponential Diophantine equation is one in which unknowns can appear in exponents.

In mathematics, the factorial of a non-negative integer , denoted by , is the product of all positive integers less than or equal to . The factorial of also equals the product of with the next smaller factorial: For example, The value of 0! is 1, according to the convention for an empty product.

In mathematics, a polynomial is a mathematical expression consisting of indeterminates and coefficients, that involves only the operations of addition, subtraction, multiplication and exponentiation to nonnegative integer powers, and has a finite number of terms. An example of a polynomial of a single indeterminate x is x2 − 4x + 7. An example with three indeterminates is x3 + 2xyz2 − yz + 1.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In mathematics, a transcendental number is a real or complex number that is not algebraic: that is, not the root of a non-zero polynomial with integer coefficients. The best-known transcendental numbers are π and e. The quality of a number being transcendental is called transcendence.

<span class="mw-page-title-main">Linear programming</span> Method to solve optimization problems

Linear programming (LP), also called linear optimization, is a method to achieve the best outcome in a mathematical model whose requirements and objective are represented by linear relationships. Linear programming is a special case of mathematical programming.

In mathematics, a Diophantine equation is an equation of the form P(x1, ..., xj, y1, ..., yk) = 0 (usually abbreviated P(x, y) = 0) where P(x, y) is a polynomial with integer coefficients, where x1, ..., xj indicate parameters and y1, ..., yk indicate unknowns.

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.

In mathematics, a recurrence relation is an equation according to which the th term of a sequence of numbers is equal to some combination of the previous terms. Often, only previous terms of the sequence appear in the equation, for a parameter that is independent of ; this number is called the order of the relation. If the values of the first numbers in the sequence have been given, the rest of the sequence can be calculated by repeatedly applying the equation.

<span class="mw-page-title-main">Diophantine approximation</span> Rational-number approximation of a real number

In number theory, the study of Diophantine approximation deals with the approximation of real numbers by rational numbers. It is named after Diophantus of Alexandria.

Transcendental number theory is a branch of number theory that investigates transcendental numbers, in both qualitative and quantitative ways.

In mathematics, and more specifically in analysis, a holonomic function is a smooth function of several variables that is a solution of a system of linear homogeneous differential equations with polynomial coefficients and satisfies a suitable dimension condition in terms of D-modules theory. More precisely, a holonomic function is an element of a holonomic module of smooth functions. Holonomic functions can also be described as differentiably finite functions, also known as D-finite functions. When a power series in the variables is the Taylor expansion of a holonomic function, the sequence of its coefficients, in one or several indices, is also called holonomic. Holonomic sequences are also called P-recursive sequences: they are defined recursively by multivariate recurrences satisfied by the whole sequence and by suitable specializations of it. The situation simplifies in the univariate case: any univariate sequence that satisfies a linear homogeneous recurrence relation with polynomial coefficients, or equivalently a linear homogeneous difference equation with polynomial coefficients, is holonomic.

In additive and algebraic number theory, the Skolem–Mahler–Lech theorem states that if a sequence of numbers satisfies a linear difference equation, then with finitely many exceptions the positions at which the sequence is zero form a regularly repeating pattern. This result is named after Thoralf Skolem, Kurt Mahler, and Christer Lech. Its known proofs use p-adic analysis and are non-constructive.

The graph realization problem is a decision problem in graph theory. Given a finite sequence of natural numbers, the problem asks whether there is a labeled simple graph such that is the degree sequence of this graph.

<span class="mw-page-title-main">Constant-recursive sequence</span> Infinite sequence of numbers satisfying a linear equation

In mathematics, an infinite sequence of numbers is called constant-recursive if it satisfies an equation of the form

<span class="mw-page-title-main">Moser–de Bruijn sequence</span> Number, sum of distinct powers of 4

In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4. Equivalently, they are the numbers whose binary representations are nonzero only in even positions.

In mathematics a P-recursive equation is a linear equation of sequences where the coefficient sequences can be represented as polynomials. P-recursive equations are linear recurrence equations with polynomial coefficients. These equations play an important role in different areas of mathematics, specifically in combinatorics. The sequences which are solutions of these equations are called holonomic, P-recursive or D-finite.

References

  1. 1 2 3 Ouaknine, Joël; Worrell, James (2012), "Decision problems for linear recurrence sequences", Reachability Problems: 6th International Workshop, RP 2012, Bordeaux, France, September 17–19, 2012, Proceedings, Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, ISBN   978-3-642-33511-2, MR   3040104 .
  2. ↑ Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter, I (6). Ouaknine & Worrell (2012) instead cite a 1934 paper of Skolem for this result.
  3. ↑ Berstel, Jean; Mignotte, Maurice (1976), "Deux propriétés décidables des suites récurrentes linéaires", Bulletin de la Société Mathématique de France (in French), 104 (2): 175–184, doi: 10.24033/bsmf.1823 , MR   0414475 .
  4. ↑ Mignotte, M.; Shorey, T. N.; Tijdeman, R. (1984), "The distance between terms of an algebraic recurrence sequence", Journal für die Reine und Angewandte Mathematik , 349: 63–76, MR   0743965 .
  5. ↑ Vereshchagin, N. K. (1985), "The problem of the appearance of a zero in a linear recursive sequence", Matematicheskie Zametki (in Russian), 38 (2): 177–189, 347, MR   0808885 .
  6. ↑ Blondel, Vincent D.; Portier, Natacha (2002), "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, doi:10.1016/S0024-3795(01)00466-9, MR   1917474 .
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.