スコーレム問題

数学上の未解決問題:

定数係数回帰数列に0が含まれるかを判定するアルゴリズムは存在するか？

スコーレム問題とは、定数係数回帰数列（constant-recursive sequence）に 0 が含まれるかを判定する数学上の問題である。この問題は、整数、有理数、代数的数など、さまざまな種類の数に対して定式化される。この問題を解くアルゴリズムが存在するかは未解決である^[1]。

線形回帰関係は、各項をそれ以前の項の線形結合として定義し、例えば、フィボナッチ数は、以下の漸化式

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

と初期値 F(0) = 0、F(1) =1で定義される。スコーレム問題は1933年に数列上の 0 についてのスコーレム・マーラー・レッヒ定理を証明したトアルフ・スコーレムにちなんで名付けられた^[2]。この定理は、数列に 0 が含まれる場合、非常に多くの例外を除いて、0 は規則的に繰り返されるという定理である。スコーレムはこれを有理数上の回帰数列について証明し、マーラーは代数的数上で、レッヒは標数が 0 の体で成り立つことを証明した。しかし、定理の証明は、0 が存在するかどうかを判断する方法を示していない。

定数係数回帰数列が無限に多くの 0 を含むかを判断するアルゴリズムは存在し、もし無限に多くの 0 を含むのであれば、漸化式の特性多項式の根の代数的性質に基づいて、0 の位置の「分解」を周期的な部分列として示すことができる^[3]。スコーレム問題の難しい部分は、0 が有限個である（したがって周期的でない）場合に、0 が存在するかを判定する部分である。

スコーレム問題に対する部分的な解は知られており、4項以下の漸化式の特殊な場合については解かれている。しかし、この解決法は5項以上の漸化式には適用できない^[4]^[5]。

整数回帰におけるスコーレム問題はNP困難に属する^[6]。

参考文献

^ 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, 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, MR 3040104
^ Skolem, Th. (1933), “Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen”, Oslo Vid. akad. Skrifter I (6)
^ Berstel, Jean; Mignotte, Maurice (1976), “Deux propriétés décidables des suites récurrentes linéaires” (French), Bulletin de la Société Mathématique de France 104 (2): 175–184, MR0414475
^ 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, MR743965
^ Vereshchagin, N. K. (1985), “The problem of the appearance of a zero in a linear recursive sequence” (Russian), Matematicheskie Zametki 38 (2): 177–189, 347, MR808885
^ 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, MR1917474

外部リンク

Tao, Terence (May 25, 2007), “Open question: effective Skolem–Mahler–Lech theorem”, What's new

[ow-1] 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, 7550, Heidelberg: Springer-Verlag, pp. 21–28, doi:10.1007/978-3-642-33512-9_3, 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)

[3] Berstel, Jean; Mignotte, Maurice (1976), “Deux propriétés décidables des suites récurrentes linéaires” (French), Bulletin de la Société Mathématique de France 104 (2): 175–184, MR0414475

[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, MR743965

[5] Vereshchagin, N. K. (1985), “The problem of the appearance of a zero in a linear recursive sequence” (Russian), Matematicheskie Zametki 38 (2): 177–189, 347, MR808885

[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, MR1917474

[1]

[2]

[3]

[4]

[5]

[6]