定数再帰シーケンス

数学では、無限の数列が次の式を満たす場合、その 数列は 定数再帰的であると呼ばれる。${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}$$

すべての に対して、 は定数です。この方程式は線形再帰関係と呼ばれます。この概念は、線形再帰列、線形再帰列、線形再帰列、またはC 有限列としても知られています。^[1]${\displaystyle n\geq d}$${\displaystyle c_{i}}$

例えば、フィボナッチ数列

${\displaystyle 0,1,1,2,3,5,8,13,\ldots }$、

は定数再帰的です。なぜなら、数列の各数は前の2つの数の合計である線形回帰を満たしているからです。 ^[2] 他の例としては、各数が前の数の2倍の合計である2のべき乗数列や、平方数列などがあります。すべての等差数列、すべての等比数列、およびすべての多項式は定数再帰的です。ただし、すべての数列が定数再帰的であるわけではありません。たとえば、階乗数列は定数再帰的ではありません。 ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle 1,2,4,8,16,\ldots }$${\displaystyle 0,1,4,9,16,25,\ldots }$${\displaystyle 1,1,2,6,24,120,\ldots }$

定数再帰列は、組合せ論と有限差分理論で研究されています。また、代数的整数論では、列と多項式の根の関係から、アルゴリズムの解析では単純な再帰関数の実行時間として、形式言語の理論では正規言語で指定された長さまでの文字列を数えることからも、定数再帰列は生じます。定数再帰列は、項ごとの加算、項ごとの乗算、コーシー積などの重要な数学演算に対して閉じています。

スコーレム・マーラー・レヒの定理は、定数再帰列の零点は規則的に繰り返される（最終的には周期的な）形式を持つことを述べています。スコーレム問題とは、線形再帰に零点が少なくとも 1 つあるかどうかを判断するアルゴリズムを求める数学の未解決問題です。

定数再帰列とは、次の式を満たす 整数、有理数、代数的数、実数、複素数 （省略形として と表記）の列である。${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$${\displaystyle (s_{n})_{n=0}^{\infty }}$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}$$

すべてに対して、数列と同じ定義域にわたるいくつかの固定係数（整数、有理数、代数的数、実数、または複素数）に対して成り立つ。この方程式は、次数dの定数係数を持つ線形回帰式と呼ばれる。数列の次数は、数列が次数dの回帰式を満たす最小の正の整数、またはどこでもゼロの数列に対してである。^{[引用が必要]}${\displaystyle n\geq d,}$ ${\displaystyle c_{1},c_{2},\dots ,c_{d}}$${\displaystyle d}$${\displaystyle d=0}$

上記の定義では、やなどの最終的に周期的なシーケンスが許容されます。 一部の著者は を要求しており、そのようなシーケンスは除外されます。^{[3] [4] [5]}${\displaystyle 1,0,0,0,\ldots }$${\displaystyle 0,1,0,0,\ldots }$${\displaystyle c_{d}\neq 0}$

フィボナッチ数列 0, 1, 1, 2, 3, 5, 8, 13, ... はで再帰性を満たすため、次数 2 の定数再帰です。たとえば、および です。ルーカス数列 2, 1, 3, 4, 7, 11, ... はフィボナッチ数列と同じ再帰性を満たしますが、初期条件が およびです。より一般的には、すべてのルーカス数列は次数 2 の定数再帰です。 ^[2]${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle F_{0}=0,F_{1}=1}$${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$${\displaystyle F_{6}=F_{5}+F_{4}=5+3=8}$${\displaystyle L_{0}=2}$${\displaystyle L_{1}=1}$

任意のおよび任意のに対して、等差数列はを満たすため、次数 2 の定数再帰です。これを一般化するには、以下の多項式列を参照してください。^{[引用が必要]}${\displaystyle a}$${\displaystyle r\neq 0}$ ${\displaystyle a,a+r,a+2r,\ldots }$${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$

任意のおよびに対して、 を満たすので、等比数列は 1 次定数再帰です。これには、たとえば、数列 1、2、4、8、16、... や有理数数列 が含まれます。^[要出典]${\displaystyle a\neq 0}$${\displaystyle r}$ ${\displaystyle a,ar,ar^{2},\ldots }$${\displaystyle s_{n}=rs_{n-1}}$${\textstyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...}$

最終的に周期長で周期的になるシーケンスは、すべての に対してを満たすため、定数再帰的です。ここで、順序は最初の繰り返しブロックを含む初期セグメントの長さです。このようなシーケンスの例には、1、0、0、0、... (順序 1) や 1、6、6、6、... (順序 2) などがあります。^{[引用が必要]}${\displaystyle \ell }$${\displaystyle s_{n}=s_{n-\ell }}$${\displaystyle n\geq d}$${\displaystyle d}$

多項式によって定義される数列は定数再帰的である。数列は次数の再帰式を満たす（ここでは多項式の次数）が、係数は二項変換の対応する要素によって与えられる。^{[7] [8]}このような方程式の最初のいくつかは、 ${\displaystyle s_{n}=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{d}n^{d}}$${\displaystyle d+1}$${\displaystyle d}$

${\displaystyle s_{n}=1\cdot s_{n-1}}$0次（つまり定数）多項式の場合、

${\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}}$1次以下の多項式の場合、

${\displaystyle s_{n}=3\cdot s_{n-1}-3\cdot s_{n-2}+1\cdot s_{n-3}}$2次以下の多項式の場合、

${\displaystyle s_{n}=4\cdot s_{n-1}-6\cdot s_{n-2}+4\cdot s_{n-3}-1\cdot s_{n-4}}$3 次以下の多項式の場合。

d次方程式に従う数列は、すべての高次方程式にも従います。これらの恒等式は、有限差分理論を含むさまざまな方法で証明できます。^[9]整数、実数、複素数値 の任意の数列は、次数 の定数再帰数列の初期条件として使用できます。初期条件が 次以下の多項式上にある場合、定数再帰数列はより低次の方程式にも従います。 ${\displaystyle d+1}$${\displaystyle d+1}$${\displaystyle d-1}$

を正規言語とし、を の長さの単語の数とします。すると は定数再帰的です。^[10]たとえば、すべてのバイナリ文字列の言語 、すべての単項文字列の言語 、連続する 2 つの文字列を持たないすべてのバイナリ文字列の言語 は定数再帰的です。より一般的には、半環(実際には環、さらには体)上の単項アルファベット上の重み付きオートマトンによって受け入れられる関数はすべて定数再帰的です。^[要出典]${\displaystyle L}$${\displaystyle s_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=2^{n}}$${\displaystyle s_{n}=1}$${\displaystyle s_{n}=F_{n+2}}$${\displaystyle \Sigma =\{a\}}$ ${\displaystyle (\mathbb {R} ,+,\times )}$

ヤコブスター数、パドヴァン数、ペル数、ペラン数^[2]の列は定数再帰的である。

階乗シーケンスは定数再帰的ではありません。より一般的には、すべての定数再帰関数は指数関数によって漸近的に制限され (「#閉形式の特徴付け」を参照)、階乗シーケンスはこれよりも速く増加します。 ${\displaystyle 1,1,2,6,24,120,720,\ldots }$

カタラン数列は 定数再帰的ではありません。これは、カタラン数の生成関数が有理関数ではないためです(「同等の定義」を参照)。 ${\displaystyle 1,1,2,5,14,42,132,\ldots }$

シーケンスが定数再帰的であるかそれ以下の順序である場合、そしてそのシーケンスが次のように記述できる場合のみ、 ${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle d}$

${\displaystyle s_{n}=uA^{n}v}$

ここで、はベクトル、は行列、はベクトルであり、要素は元のシーケンスと同じドメイン（整数、有理数、代数的数、実数、または複素数）から取得されます。具体的には、はシーケンスの最初の値、から計算される線形変換、およびベクトルとしてとらえることができます。^[11]${\displaystyle u}$${\displaystyle 1\times d}$${\displaystyle A}$${\displaystyle d\times d}$ ${\displaystyle v}$${\displaystyle d\times 1}$${\displaystyle v}$${\displaystyle d}$${\displaystyle A}$${\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}}$${\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}}$${\displaystyle u}$${\displaystyle [0,0,\ldots ,0,1]}$

非同次再帰とそれと同等の同次バージョンを使用した自然数列 の定義。${\displaystyle s_{n}=n}$

非同次線形回帰は、次の形式の方程式である。

${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d}+c}$

ここで は追加の定数です。非同次線形回帰を満たす任意のシーケンスは定数回帰です。これは、の方程式から の方程式を引くとの同次回帰が得られるためであり、これを について解くと^{[引用が必要]}が得られます。${\displaystyle c}$${\displaystyle s_{n-1}}$${\displaystyle s_{n}}$${\displaystyle s_{n}-s_{n-1}}$${\displaystyle s_{n}}$

${\displaystyle {\begin{aligned}s_{n}=&(c_{1}+1)s_{n-1}\\&+(c_{2}-c_{1})s_{n-2}+\dots +(c_{d}-c_{d-1})s_{n-d}\\&-c_{d}s_{n-d-1}.\end{aligned}}}$

シーケンスが定数再帰的であるのは、その生成関数が

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}=s_{0}+s_{1}x^{1}+s_{2}x^{2}+s_{3}x^{3}+\cdots }$

は有理関数であり、 およびは多項式、 である。^[3] さらに、数列の位数は、およびとなるような形を持つ最小のものである。^[12]${\displaystyle p(x)\,/\,q(x)}$${\displaystyle p}$${\displaystyle q}$${\displaystyle q(0)=1}$${\displaystyle d}$${\displaystyle {\text{deg }}q(x)\leq d}$${\displaystyle {\text{deg }}p(x)<d}$

分母は補助多項式の係数の順序を逆にして得られる多項式であり、分子は数列の初期値によって決定される: ^{[13] [14]}

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}},}$

どこ

${\displaystyle b_{n}=s_{n}-c_{1}s_{n-1}-c_{2}s_{n-2}-\dots -c_{d}s_{n-d}.}$^[15]

上記から、分母はで割り切れない多項式（特にゼロ以外）でなければならないことがわかります。 ${\displaystyle q(x)}$${\displaystyle x}$

シーケンスによって生成されるシーケンスの2 次元ベクトル空間。${\displaystyle s_{n}=n}$

シーケンスが定数再帰的であるのは、シーケンスの集合が ${\displaystyle (s_{n})_{n=0}^{\infty }}$

${\displaystyle \left\{(s_{n+r})_{n=0}^{\infty }:r\geq 0\right\}}$

は有限次元のシーケンス空間（シーケンスのベクトル空間）に含まれます。つまり、左シフト演算子で閉じた有限次元の部分空間に含まれます。^{[16] [17]}${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle \mathbb {C} ^{\mathbb {N} }}$

この特徴付けは、順序と線形再帰関係が のシーケンス間の線形従属の証明として理解できるためである。この議論を拡張すると、シーケンスの順序は、すべての に対してによって生成されるシーケンス空間の次元に等しいことが示される。^{[18] [17]}${\displaystyle d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r=0,\ldots ,d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r}$

定数再帰列は指数多項式を用いて次のような一意の閉形式の特徴付けが可能である。すべての定数再帰列は次のような形式で表すことができる。

${\displaystyle s_{n}=z_{n}+k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n},}$

すべての に対して、ここで ${\displaystyle n\geq 0}$

• 項は、すべてに対してゼロとなるシーケンスです（シーケンスの順序はここで）。${\displaystyle z_{n}}$${\displaystyle n\geq d}$${\displaystyle d}$
• 項は複素多項式であり、${\displaystyle k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)}$
• これらの項はそれぞれ異なる複素定数である。^{[19] [3]}${\displaystyle r_{1},r_{2},\ldots ,r_{k}}$

この特徴付けは正確である。つまり、上記の形式で記述できる複素数列はすべて定数再帰的である。^[20]

例えば、フィボナッチ数はビネの公式を使って次のように表される：^[21]${\displaystyle F_{n}}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\varphi ^{n}-{\frac {1}{\sqrt {5}}}\psi ^{n},}$

ここで、 は黄金比、 です。これらは方程式 の根です。この場合、すべての に対して、は定数多項式、、です。 ${\displaystyle \varphi =(1+{\sqrt {5}})\,/\,2\approx 1.61803\ldots }$${\displaystyle \psi =-1\,/\,\varphi }$${\displaystyle x^{2}-x-1=0}$${\displaystyle e=2}$${\displaystyle z_{n}=0}$${\displaystyle n}$${\displaystyle k_{1}(n)=k_{2}(n)=1\,/\,{\sqrt {5}}}$${\displaystyle r_{1}=\varphi }$${\displaystyle r_{2}=\psi }$

項はの場合にのみ必要です。の場合、この項は、一部の初期値が一般的な再発の例外となる可能性があるという事実を修正します。特に、すべての に対して です。^[要出典]${\displaystyle z_{n}}$${\displaystyle c_{d}\neq 0}$${\displaystyle c_{d}=0}$${\displaystyle z_{n}=0}$${\displaystyle n\geq d}$

複素数は、再帰 特性多項式の根です。${\displaystyle r_{1},\ldots ,r_{n}}$

${\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}$

その係数は再帰式の係数と同じである。^[22]再帰式の固有根 と呼ばれる。数列が整数または有理数からなる場合、根は代数的数となる。根がすべて異なる場合、多項式はすべて定数であり、数列の初期値から決定できる。固有多項式の根が異なり、が重複度の根である場合、式の は次数 となる。たとえば、固有多項式が として因数分解され、同じ根rが3 回出現する場合、番目の項は次の形式となる^{[23] [24]}${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle d}$${\displaystyle r_{1},r_{2},\dots ,r_{d}}$${\displaystyle k_{i}(n)}$${\displaystyle r_{i}}$ ${\displaystyle m}$${\displaystyle k_{i}(n)}$${\displaystyle m-1}$${\displaystyle (x-r)^{3}}$${\displaystyle n}$${\displaystyle s_{n}=(a+bn+cn^{2})r^{n}.}$

2つの定数再帰列の和も定数再帰的である。^{[25] [26]}例えば、との合計は（ ）であり、これは再帰式を満たしている。新しい再帰式は、各列の生成関数を追加することで見つけることができます。 ${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=2^{n}+n}$${\displaystyle 1,3,6,11,20,\ldots }$${\displaystyle u_{n}=4u_{n-1}-5u_{n-2}+2u_{n-3}}$

同様に、2つの定数再帰列の積も定数再帰的である。^[25]例えば、との積は( )であり、これは再帰性 を満たしている。 ${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=n\cdot 2^{n}}$${\displaystyle 0,2,8,24,64,\ldots }$${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$

左シフトシーケンスと右シフトシーケンス( ) は、同じ再帰関係を満たすため、定数再帰的です。たとえば、は定数再帰的であるため、 も定数再帰的です。 ${\displaystyle u_{n}=s_{n+1}}$${\displaystyle u_{n}=s_{n-1}}$${\displaystyle u_{0}=0}$${\displaystyle s_{n}=2^{n}}$${\displaystyle u_{n}=2^{n+1}}$

一般に、定数再帰列は以下の演算に対して閉じている。ここで、は定数再帰列を表し、はそれらの生成関数、はそれらの順序をそれぞれ表す。^[27]${\displaystyle s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }}$${\displaystyle f(x),g(x)}$${\displaystyle d,e}$

項ごとの加算と乗算の閉包は、指数多項式による閉形式の特徴付けから導かれる。コーシー積の閉包は、生成関数の特徴付けから導かれる。^[27]コーシー逆関数の要件は、整数列の場合に必要であるが、列が任意の体（有理数、代数、実数、複素数）上にある場合は、に置き換えることができる。^[27]${\displaystyle s_{0}=1}$${\displaystyle s_{0}\neq 0}$

単純な局所的公式を満たしているにもかかわらず、定数再帰列は複雑な全体的動作を示すことがある。定数再帰列の零点をとなる非負の整数として定義する。スコーレム・マーラー・レヒの定理は、列の零点は結局繰り返されることを述べている。つまり、 であればかつその場合に限り、すべての に対して となる定数およびが存在する。この結果は、複素数上、またはより一般的には、特性0の任意の体上の定数再帰列に対して成り立つ。^[30]${\displaystyle n}$${\displaystyle s_{n}=0}$${\displaystyle M}$${\displaystyle N}$${\displaystyle n>M}$${\displaystyle s_{n}=0}$${\displaystyle s_{n+N}=0}$

定数再帰シーケンス内のゼロのパターンは、計算可能性理論の観点からも調査することができます。そのためには、シーケンスの記述に有限の記述を与える必要があります。これは、シーケンスが整数または有理数、あるいは代数的数上にある場合に行うことができます。^[11] シーケンスのこのようなエンコードが与えられれば、次の問題を研究することができます。 ${\displaystyle s_{n}}$${\displaystyle s_{n}}$

定数再帰シーケンスの平方は依然として定数再帰であるため (閉包特性を参照)、上の表のゼロの存在問題は正値に還元され、無限個のゼロは最終的な正値に還元されます。他の問題も上の表の問題に還元されます。たとえば、いくつかについて がシーケンス のゼロの存在に還元されるかどうかなどです。2 番目の例として、実数のシーケンスについて、弱正値性 (すべてについて は?) はシーケンスの正値性に還元されます(答えは否定される必要があるため、これはチューリング還元です)。 ${\displaystyle s_{n}^{2}}$${\displaystyle s_{n}=c}$${\displaystyle n}$${\displaystyle s_{n}-c}$${\displaystyle s_{n}\geq 0}$${\displaystyle n}$${\displaystyle -s_{n}}$

スコーレム・マーラー・レヒの定理は、これらの質問のいくつかに答えを提供しますが、その証明は非構成的であるということです。この定理は、すべての に対して、ゼロが繰り返されることを述べています。しかし、 の値が計算可能であるかどうかはわかっていないため、これはゼロの存在問題の解決にはつながりません。^[11]一方、 の後に繰り返される正確なパターンは計算可能です。^{[11] [32]}これが、無限に多くのゼロの問題が決定可能である理由です。無限に繰り返されるパターンが空かどうかを判定するだけです。 ${\displaystyle n>M}$${\displaystyle M}$${\displaystyle n>M}$

決定可能性の結果は、シーケンスの順序が小さい値に制限されている場合に知られています。たとえば、スコーレム問題は、順序が4までの代数シーケンスに対して決定可能です。^{[33] [34] [35]}また、順序が7までの可逆な整数シーケンス、つまり整数内で逆方向に継続できるシーケンスに対しても決定可能であることが知られています。^[31]

決定可能性の結果は、数論における特定の未証明の予想を仮定した場合にも知られている。例えば、スコーレム予想（指数局所大域原理としても知られる）に従うと、5次の有理数列の決定可能性が知られている。また、スコーレム予想と弱いp進シャヌエル予想に従うと、すべての単純な有理数列（単純な特性多項式を持つもの）の決定可能性も知られている。 ^[36]

を定数回帰列 の特性根とします。 に対して任意の比が 1 の根である場合、列は退化しているといいます。 退化していない列を調べる方が簡単な場合が多く、ある意味では、次の定理を使用してこれを簡約できます。 が順序を持ち、上の次数の数体に含まれる場合、定数${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle s}$${\displaystyle r_{i}/r_{j}}$${\displaystyle i\neq j}$${\displaystyle s}$${\displaystyle d}$${\displaystyle K}$${\displaystyle k}$${\displaystyle \mathbb {Q} }$${\displaystyle M(k,d)\leq {\begin{cases}\exp(2d(3\log d)^{1/2})&{\text{if }}k=1,\\2^{kd+1}&{\text{if }}k\geq 2\end{cases}}}$

ある部分列は、それぞれが同一にゼロであるか非退化であるかのいずれかである。 ^[37]${\displaystyle M\leq M(k,d)}$${\displaystyle s_{Mn+\ell }}$

D有限列またはホロノミック列は、再帰の係数が定数ではなく多項式関数であることが許される自然な一般化である。^[38]${\displaystyle n}$

-正則シーケンスは定数係数の線形再帰を満たしますが、再帰の形式は異なります。に近い整数に対するの線形結合ではなく、 -正則シーケンスの各項は、 の基数表現が の基数表現に近い整数に対するの線形結合です。^{[39]定数再帰シーケンスは、 の}基数 1 表現が数字 のコピーで構成される-正則シーケンスと考えることができます。^[要出典]${\displaystyle k}$${\displaystyle s_{n}}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle s_{n}}$${\displaystyle k}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle k}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 1}$

• 「OEIS インデックス レック」。 OEIS は、数千の線形回帰の例を、順序 (項の数) とシグネチャ (定数係数の値のベクトル) でソートしたインデックスです。