k-正規列

数学および理論計算機科学において、k正則シーケンスは、整数のk を底とする表現を反映する線形再帰方程式を満たすシーケンスです。k 正則シーケンスのクラスは、 k自動シーケンスのクラスを無限サイズのアルファベットに一般化します。

k正則シーケンスにはいくつかの特徴付けが存在し、それらはすべて同等です。一般的な特徴付けのいくつかを以下に示します。それぞれについて、R ′ を可換 ネーター環とし、 R をR ′ を含む環とします。

k  ≥ 2とする。シーケンスのkカーネルは部分シーケンスの集合である。 ${\displaystyle s(n)_{n\geq 0}}$

${\displaystyle K_{k}(s)=\{s(k^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq k ^{e}-1\}.}$

K _k ( s )によって生成される - 加群が有限生成R ′-加群である場合、その数列は( R ′, k )-正則 (しばしば単に「k -正則」と略される)である。 ^[1]${\displaystyle s(n)_{n\geq 0}}$${\displaystyle R'}$

の特別な場合において、 が上の有限次元ベクトル空間に含まれる場合、その数列は-正則です。 ${\displaystyle R'=R=\mathbb {Q} }$${\displaystyle s(n)_{n\geq 0}}$${\displaystyle k}$${\displaystyle K_{k}(s)}$${\displaystyle \mathbb {Q} }$

シーケンスs ( n ) がk正則であるとは、すべてのe _j > Eかつ0 ≤ r _j ≤ k ^{e _j} − 1 に対して、 sの形式s ( k ^{e _j} n  +  r _j ) のすべての部分シーケンスがR ′-線形結合として表現できるような整数 E が存在する場合です。ここで、c _ijは整数、f _ij ≤ E、および 0 ≤ b _ij ≤ k ^{f _ij}  − 1です^。[2] ${\displaystyle \sum _{i}c_{ij}s(k^{f_{ij}}n+b_{ij})}$

あるいは、整数rと部分列s ₁ ( n )、...、s _r ( n )が存在し、すべての1 ≤ i ≤ rおよび0 ≤ a ≤ k − 1に対して、 kカーネルK k ( s )内の すべての列s _i ( kn  +  a )が部分列s _i ( n )のR ′-線形結合である場合_、列s ( n )はk-正則である。^[2]

x ₀ , ..., x _{k  − 1 を}k 個の非可換変数の集合とし、 τ をある自然数n を文字列x _{a 0} ... x _{a e  − 1}に写像するとする。ここで、 xのk進数表現は文字列a _{e  − 1} ... a ₀である。すると、数列s ( n ) がk正則となるのは、形式級数が-有理数である場合に限ります。^[3] ${\displaystyle \sum _{n\geq 0}s(n)\tau (n)}$${\displaystyle \mathbb {Z} }$

k正則列の形式的な級数定義は、シュッツェンベルガーの行列マシンに似たオートマトンの特徴付けにつながる。 ^{[4] [5]}

k正則列の概念は、AlloucheとShallitによる2つの論文で初めて研究されました。^{[6]これに先立ち、BerstelとReutenauerは}k正則列と密接に関連する有理級数の理論を研究しました。^[7]

を の-進値とします。ルーラシーケンス( OEIS : A007814 ) は-正則であり、-カーネル ${\displaystyle s(n)=\nu _{2}(n+1)}$ ${\displaystyle 2}$${\displaystyle n+1}$${\displaystyle s(n)_{n\geq 0}=0,1,0,2,0,1,0,3,\dots }$${\displaystyle 2}$${\displaystyle 2}$

${\displaystyle \{s(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

は、定数列によって生成される2次元ベクトル空間に含まれます。これらの基底要素は、再帰関係につながります。 ${\displaystyle s(n)_{n\geq 0}}$${\displaystyle 1,1,1,\dots }$

${\displaystyle {\begin{aligned}s(2n)&=0,\\s(4n+1)&=s(2n+1)-s(n),\\s(4n+3)&=2s(2n+1)-s(n),\end{aligned}}}$

これらは初期条件およびとともに、シーケンスを一意に決定する。^[8]${\displaystyle s(0)=0}$${\displaystyle s(1)=1}$

Thue -Morse 列 t ( n ) ( OEIS : A010060 ) は、 0 → 01, 1 → 10 の射の不動点である。Thue-Morse 列は 2 自動であることが知られている。したがって、2 正則でもあり、その 2 核は

${\displaystyle \{t(2^{e}n+r)_{n\geq 0}:e\geq 0{\text{ and }}0\leq r\leq 2^{e}-1\}}$

部分列とから構成されます。 ${\displaystyle t(n)_{n\geq 0}}$${\displaystyle t(2n+1)_{n\geq 0}}$

カントール 数列c ( n )( OEIS :A005823 )は、三進展開で1を含まない 数から構成される。

${\displaystyle {\begin{aligned}c(2n)&=3c(n),\\c(2n+1)&=3c(n)+2,\end{aligned}}}$

したがって、カントール数列は2正則である。同様に、スタンレー数列

0、1、3、4、9、10、12、13、27、28、30、31、36、37、39、40、...（OEISのシーケンスA005836）

三進法展開で2を含まない数も2正則である。^[9]

k正則性の概念をより広範なアルゴリズムの研究に応用した興味深い例は、マージソートアルゴリズムの分析である。n 個の値のリストが与えられた場合、マージソートアルゴリズムによって行われる比較の数はソート数であり、再帰関係によって決まる。

${\displaystyle {\begin{aligned}T(1)&=0,\\T(n)&=T(\lfloor n/2\rfloor )+T(\lceil n/2\rceil )+n-1,\ n\geq 2.\end{aligned}}}$

その結果、マージソートの再帰関係によって定義されるシーケンスT ( n )は2正規シーケンスを構成する。^[10]

が整数値多項式である場合、 は任意の に対してk正則です。 ${\displaystyle f(x)}$${\displaystyle f(n)_{n\geq 0}}$${\displaystyle k\geq 2}$

Glaisher –Gould列は 2 正則です。Stern–Brocot 列は 2 正則です。

アルーシュとシャリットは論文の中でk正則列の例をいくつか挙げている。 ^[6]

k正則シーケンスはいくつかの興味深い特性を示します。

• すべてのk自動シーケンスはk正則シーケンスである。^[11]
• すべてのk同期シーケンスはk正規です。
• k -正規列は、k -自動列である場合にのみ有限個の値を取ります。[12] これは、k -正規列^のクラスがk -自動列のクラスの一般化であることから直接生じる結果です。
• k正則数列のクラスは項ごとの加算、項ごとの乗算、畳み込みに対して閉じている。k 正則数列のクラスはまた、数列の各項を整数 λ でスケーリングした場合にも閉じている。[ ^{12] [13] [14] [15]}特に、k正則冪級数の集合は環を形成する。^[16]
• がk-正則ならば、すべての整数に対して、はk-自動的である。しかし、その逆は成り立たない。^[17]${\displaystyle s(n)_{n\geq 0}}$${\displaystyle m\geq 1}$${\displaystyle (s(n){\bmod {m}})_{n\geq 0}}$
• 乗法的に独立なk、  l  ≥ 2に対して、あるシーケンスがk-正則かつl-正則である場合、そのシーケンスは線形回帰を満たします。^{[18]これは、} k-自動かつl-自動であるシーケンスに関するコブハムの結果の一般化です。^[19]
• k正則な整数列のn番目の項はnについて最大でも多項式的に増加する。^[20]
• が体で の場合、冪の列がk正則となるのは、または が1 の根である場合に限ります。 ^[21]${\displaystyle F}$${\displaystyle x\in F}$${\displaystyle (x^{n})_{n\geq 0}}$${\displaystyle x=0}$${\displaystyle x}$

k正則かどうかわからない候補シーケンスが与えられた場合、k正則性は通常、 のカーネルの要素を計算し、が十分に大きい の形式のすべての要素が、の代わりにより小さい指数を持つカーネル要素の線形結合として表せることを証明することによって、定義から直接証明できます。これは通常、計算上は簡単です。 ${\displaystyle s=s(n)_{n\geq 0}}$${\displaystyle s}$${\displaystyle (s(k^{r}n+e))_{n\geq 0}}$${\displaystyle r}$${\displaystyle 0\leq e<2^{r}}$${\displaystyle r}$

一方、候補シーケンスのk正則性を反証するには、通常、のカーネル内で -線形独立なサブセットを生成する必要がありますが、これは通常より困難です。次に、そのような証明の一例を示します。 ${\displaystyle s}$${\displaystyle \mathbb {Z} }$${\displaystyle s}$

の二進展開におけるの数を で表します。の二進展開におけるの数を で表します。 数列は2 正則であることが示されます。しかし、数列は、次の議論により 2 正則ではありません。 が 2 正則であると仮定します。の 2 核の および の要素はに対して線形独立であると主張します。関数は整数に射影的であるため、となる最小の整数を とします。 の 2 正則性により、の各 に対して となる定数とが存在し、 ${\displaystyle e_{0}(n)}$${\displaystyle 0}$${\displaystyle n}$${\displaystyle e_{1}(n)}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle f(n):=e_{0}(n)-e_{1}(n)}$${\displaystyle g=g(n):=|f(n)|}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle g(2^{k}n)}$${\displaystyle n\geq 1}$${\displaystyle k\geq 0}$${\displaystyle g}$${\displaystyle \mathbb {Z} }$${\displaystyle n\mapsto e_{0}(n)-e_{1}(n)}$${\displaystyle x_{m}}$${\displaystyle e_{0}(x_{m})-e_{1}(x_{m})=m}$${\displaystyle (g(n))_{n\geq 0}}$${\displaystyle b\geq 0}$${\displaystyle c_{i}}$${\displaystyle n\geq 0}$

${\displaystyle \sum _{0\leq i\leq b}c_{i}g(2^{i}n)=0.}$

を となる最小の値とします。すると、任意の に対して、 ${\displaystyle a}$${\displaystyle c_{a}\neq 0}$${\displaystyle n\geq 0}$

${\displaystyle g(2^{a}n)=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})g(2^{i}n).}$

この式を で評価すると、... ${\displaystyle n=x_{m}}$${\displaystyle m=0,-1,1,2,-2}$

${\displaystyle g(2^{a}x_{m})=|e_{0}(x_{m})-e_{1}(x_{m})+a|=|m+a|,}$

そして右側には

${\displaystyle \sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

任意の整数に対して、 ${\displaystyle m}$

${\displaystyle |m+a|=\sum _{a+1\leq i\leq b}-(c_{i}/c_{a})|m+i|.}$

しかし については、方程式の右辺はいくつかの定数 に対して の形をとるため単調であるが、左辺は単調ではない。これは 、 、 を順に代入することで確認できる。したがって、は2-正則ではない。^[22]${\displaystyle m\geq -a-1}$${\displaystyle Am+B}$${\displaystyle A,B}$${\displaystyle m=-a-1}$${\displaystyle m=-a}$${\displaystyle m=-a+1}$${\displaystyle (g(n))_{n\geq 0}}$

• Allouche, Jean-Paul; Shallit, Jeffrey (1992)、「 k正則シーケンスのリング」、 Theoret. Comput. Sci.、98 (2): 163–197、doi : 10.1016/0304-3975(92)90001-v。
• Allouche, Jean-Paul; Shallit, Jeffrey (2003)、「 k正則シーケンスのリング、II」、 Theoret. Comput. Sci.、307 : 3–29、doi : 10.1016/s0304-3975(03)00090-2。
• アルーシュ、ジャン=ポール、シャリット、ジェフリー(2003)。自動シーケンス: 理論、アプリケーション、一般化。ケンブリッジ大学出版局。ISBN 978-0-521-82332-6.ZBL1086.11015  。​