mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

, the Skolem problem is the problem of determining whether the values of a

constant-recursive sequence In mathematics, an sequence, infinite sequence of numbers s_0, s_1, s_2, s_3, \ldots is called constant-recursive if it satisfies an equation of the form :s_n = c_1 s_ + c_2 s_ + \dots + c_d s_, for all n \ge d, where c_i are constant (mathemat ...

include the number zero. The problem can be formulated for recurrences over different types of numbers, including

integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...

rational number In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example, The set of all ...

s, and

algebraic number In mathematics, an algebraic number is a number that is a root of a function, root of a non-zero polynomial in one variable with integer (or, equivalently, Rational number, rational) coefficients. For example, the golden ratio (1 + \sqrt)/2 is ...

s. It is not known whether there exists an

algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...

that can solve this problem.. A linear recurrence relation expresses the values of a

sequence In mathematics, a sequence is an enumerated collection of objects in which repetitions are allowed and order matters. Like a set, it contains members (also called ''elements'', or ''terms''). The number of elements (possibly infinite) is cal ...

of numbers as a linear combination of earlier values; for instance, the

Fibonacci number In mathematics, the Fibonacci sequence is a Integer sequence, sequence in which each element is the sum of the two elements that precede it. Numbers that are part of the Fibonacci sequence are known as Fibonacci numbers, commonly denoted . Many w ...

s may be defined from the recurrence relation : together with the initial values and . The Skolem problem is named after

Thoralf Skolem Thoralf Albert Skolem (; 23 May 1887 – 23 March 1963) was a Norwegian mathematician who worked in mathematical logic and set theory. Life Although Skolem's father was a primary school teacher, most of his extended family were farmers. Skole ...

, because of his 1933 paper proving the Skolem–Mahler–Lech theorem on the zeros of a sequence satisfying a linear recurrence with constant coefficients. This

theorem In mathematics and formal logic, a theorem is a statement (logic), statement that has been Mathematical proof, proven, or can be proven. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to esta ...

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 A root is the part of a plant, generally underground, that anchors the plant body, and absorbs and stores water and nutrients. Root or roots may also refer to: Art, entertainment, and media * ''The Root'' (magazine), an online magazine focusin ...

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 degree at most four. However, these solutions do not apply to recurrences of degree five or more. For integer recurrences, the Skolem problem is known to be

NP-hard In computational complexity theory, a computational problem ''H'' is called NP-hard if, for every problem ''L'' which can be solved in non-deterministic polynomial-time, there is a polynomial-time reduction from ''L'' to ''H''. That is, assumi ...

References

External links

*{{citation, url=https://terrytao.wordpress.com/2007/05/25/open-question-effective-skolem-mahler-lech-theorem/, first=Terence, last=Tao, authorlink=Terence Tao, title=Open question: effective Skolem–Mahler–Lech theorem, date=May 25, 2007, work=What's new Recurrence relations Unsolved problems in mathematics

See also

References

External links