Loading article…
数学において、スコレム問題（スコレム・ピゾー問題とも呼ばれる[ 1 ] ）は、定数再帰数列の値にゼロが含まれるかどうかを判定する問題である。この問題は、整数、有理数、代数的数など、さまざまな種類の数に対する漸化式に対して定式化することができる。この問題を解決できるアルゴリズムが存在するかどうかは不明である。[ 2 ]
線形漸化式は、数列の値をそれ以前の値の線形結合として表します。例えば、フィボナッチ数は漸化式から定義できます。
初期値F (0) = 0およびF (1) = 1とともに。 スコレム問題は、定数係数を持つ線形漸化式を満たす数列の零点に関するスコレム-マーラー-レヒ定理を証明した1933 年の論文でトーラルフ・スコレムにちなんで名付けられました。[ 3 ]この定理は、そのような数列に零点がある場合、有限個の例外を除いて零点の位置が規則的に繰り返されると述べています。スコレムはこれを有理数上の漸化式について証明し、マーラーとレヒはそれを他の数体系に拡張しました。しかし、この定理の証明では零点が存在するかどうかをテストする方法は示されていません。
定数再帰数列に無限個のゼロがあるかどうかをテストし、ある場合は、与えられた再帰の特性多項式の根の代数的性質に基づいて、それらのゼロの位置を周期的な部分列に分解するアルゴリズムが存在する。 [ 4 ]スコレム問題の残りの難しい部分は、非反復ゼロの有限集合が空集合であるかどうかを判定することである。[ 2 ]
スコレム問題の部分的な解法は知られており、次数が最大で4の再帰に関する問題の特殊なケースをカバーしている。しかし、これらの解法は次数が5以上の再帰には適用されない。[ 2 ] [ 5 ] [ 6 ]