コブハムの定理

コブハムの定理は、単語の組合せ論における定理であり、数論、特に超越数、オートマトン理論と重要な関係がある。非公式には、この定理は、基数b ₁および基数b ₂で書かれた自然数の集合Sのメンバーが有限オートマトンによって認識されるための条件を与える。具体的には、基数b ₁とb ₂が同じ整数のべき乗ではないとしよう。コブハムの定理は、基数b ₁およびb ₂で書かれたS が有限オートマトンによって認識されるのは、S が等差数列の有限和と有限集合だけ異なる場合のみであると述べている。この定理は1969 年にアラン コブハムによって証明され^[1]、それ以来多くの拡張と一般化が行われた。^{[2] [3]}

を整数とする。自然数の基数による表現は、次の数字の列である。 ${\displaystyle n>0}$${\textstyle n}$ ${\textstyle b}$${\displaystyle n_{0}n_{1}\cdots n_{h}}$

${\displaystyle n=n_{0}+n_{1}b+\cdots +n_{h}b^{h}}$

ここで、および です。この単語は、あるいはもっと簡単に と表記されることが多いです。 ${\displaystyle 0\leq n_{0},n_{1},\ldots ,n_{h}}$${\displaystyle n_{h}>0}$${\displaystyle n_{0}n_{1}\cdots n_{h}}$${\displaystyle \langle n\rangle _{b}}$${\displaystyle n_{b}}$

自然数集合Sは、その要素の基数での表現の集合がアルファベット上の有限オートマトンによって認識可能な言語である場合、基数 で認識可能 、またはもっと簡単に言えば-認識可能または-自動的である。 ${\textstyle b}$${\textstyle b}$${\textstyle b}$${\displaystyle \{n_{b}\mid n\in S\}}$${\displaystyle b}$${\displaystyle \{0,1,\ldots ,b-1\}}$

2 つの正の整数およびは、となる非負の整数およびが存在しない場合に乗法的に独立です。たとえば、2 と 3 は乗法的に独立ですが、 であるため 8 と 16 は独立ではありません。2 つの整数は、3 つ目の同じ整数の累乗である場合に限り乗法的に従属します。 ${\displaystyle k}$${\displaystyle \ell}$${\displaystyle p}$${\displaystyle q}$${\displaystyle k^{p}=\ell^{q}}$${\displaystyle 8^{4}=16^{3}}$

この定理には、より同等の記述がいくつかある。コブハムによるオリジナルのバージョンは以下の通りである: ^[1]

定理を述べる別の方法は、自動シーケンスを使用することです。コブハム自身はそれを「均一タグシーケンス」と呼んでいます。^[4]次の形式は、アルーシュとシャリットの本に記載されています。^[5]

有限オートマトンがk を底として認識できる自然数集合Sの特性列はk自動列であり、逆に、すべてのk自動列とすべての整数に対して、 となる自然数集合はを底として認識できることを示すことができます。 ${\displaystyle u}$${\displaystyle 0\leq i<k}$${\displaystyle S_{i}}$${\displaystyle s}$${\displaystyle u_{s}=i}$${\displaystyle k}$

コブハムの定理は、1960年にビュッヒによって証明された定理を用いて一階論理で定式化することができる。^[7]この論理の定式化は拡張と一般化を可能にする。論理式は理論^{[8]を使用する。}

${\displaystyle \langle N,+,V_{r}\rangle }$

任意の正の整数に対して、が を割り切れる最大の のべき乗である場合、 とによって定義される関数を備えた自然整数 の です。たとえば、、 です。 ${\displaystyle V_{r}}$${\displaystyle V_{r}(0)=1}$${\textstyle n}$${\displaystyle V_{r}(n)=r^{m}}$${\displaystyle r^{m}}$${\displaystyle r}$${\textstyle n}$${\displaystyle V_{2}(20)=4}$${\displaystyle V_{3}(20)=1}$

整数の集合は、等式、加算、を含む一階述語論理で記述できる場合、一階述語論理で定義可能です。 ${\displaystyle S}$ ${\displaystyle \langle N,+,V_{r}\rangle }$${\displaystyle V_{r}}$

例:

• 奇数の集合は（ を使わずに）次の式で定義できる。${\displaystyle V_{r}}$${\displaystyle (\exists y)(x=y+y+1)}$
• 2 の累乗の集合は簡単な式で定義できます。${\displaystyle \{2^{n}\mid n\geq 0\}}$${\displaystyle V_{2}(x)=x}$

Sがプレスブルガー算術で一階定義可能であるのは、それが最終的に周期的である場合に限ることに注目することで、論理との類似性をさらに推し進めることができます。したがって、集合S は、プレスブルガー算術で定義可能である場合に限り、論理で定義可能です。 ${\displaystyle \langle N,+,V_{k}\rangle }$${\displaystyle \langle N,+,V_{\ell }\rangle }$

自動シーケンスは、射が一様である特定のモルフィックワードであり、入力アルファベットの各文字に対して射によって生成される画像の長さは同じです。したがって、整数の集合がk認識可能であるのは、その特性シーケンスが一様射とそれに続くコーディングによって生成される場合のみです。コーディングとは、入力アルファベットの各文字を出力アルファベットの文字にマッピングする射です。たとえば、 2 の累乗の特性シーケンスは、次で定義される アルファベット上の 2 一様射 (つまり、各文字が長さ 2 のワードにマッピングされる) によって生成されます。${\displaystyle B=\{a,0,1\}}$

${\displaystyle a\mapsto a1\ ,\quad 1\mapsto 10\ ,\quad 0\mapsto 00}$

無限語を生成する

${\displaystyle a11010001\cdots }$、

続いて、とをマッピングするコーディング（つまり、文字から文字へのマッピング）が続き、とを変更せずに、 ${\displaystyle a}$${\displaystyle 0}$${\displaystyle 0}$${\displaystyle 1}$

${\displaystyle 011010001\cdots }$。

この概念は次のように拡張されている。^[9]形態語は、ある数に代用できる語であり、 ${\displaystyle s}$${\displaystyle \alpha}$${\displaystyle \alpha}$

${\displaystyle s=\pi (f^{\omega }(b))}$

ここで、において延長可能な射 には、次の性質があります。 ${\displaystyle f:B^{*}\to B^{*}}$${\textstyle b}$

• のすべての文字は に出現し、${\displaystyle B}$${\displaystyle f^{\omega }(b)}$
• ${\displaystyle \alpha >1}$は、射の行列、つまり行列の優勢な固有値です。ここで、 は単語 における文字の出現回数です。 ${\displaystyle f}$${\displaystyle M(f)=(m_{x,y})_{x\in B,y\in A}}$${\displaystyle m_{x,y}}$${\displaystyle x}$${\displaystyle f(y)}$

自然数の集合Sは、その特性列が- 置換可能である場合、 -認識可能である。 ${\displaystyle \alpha}$${\displaystyle s}$${\displaystyle \alpha}$

最後の定義:ペロン数とは、その共役がすべて円板に属する代数数 です。これらはまさに正の整数の原始行列の支配的な固有値です。 ${\displaystyle z>1}$${\displaystyle \{z'\in \mathbb {C} ,|z'|<z\}}$

すると次のような記述が出てきます。^[9]

論理的に同等なことは、より一般的な状況を考慮することを可能にする。自然数または認識可能な集合上の自動シーケンスは、整数、直積、実数、直積に拡張されている。^[8]${\displaystyle \mathbb {N} }$${\displaystyle \mathbb {Z} }$${\displaystyle \mathbb {N} ^{m}}$${\displaystyle \mathbb {R} }$${\displaystyle \mathbb {R} ^{m}}$

拡張${\displaystyle \mathbb {Z} }$

基数整数は、正の整数の表現の前に数字 を付加してコード化し、負の整数は、その数の補数を続けて表します。たとえば、基数 2 では、整数 はと表されます。2 の累乗は、その負数はと表されます(は の表現であるため)。 ${\displaystyle k}$${\displaystyle 0}$${\displaystyle k-1}$${\displaystyle k}$${\displaystyle -6=-8+2}$${\displaystyle 1010}$${\displaystyle 010^{*}}$${\displaystyle 110^{*}}$${\displaystyle 11000}$${\displaystyle -16+8=-8}$

拡張${\displaystyle \mathbb {N} ^{m}}$

のサブセットは、 の要素が、その要素を持つベクトルとして表され、結果として得られるアルファベット上で認識可能である 場合、基数 で認識可能です。${\displaystyle X}$${\displaystyle N^{m}}$${\displaystyle k}$${\displaystyle X}$${\displaystyle m}$

たとえば、基数 2 では、 および となり、ベクトルは と表記されます。${\displaystyle 3=11_{2}}$${\displaystyle 9=1001_{2}}$${\displaystyle {\begin{pmatrix}3\\9\end{pmatrix}}}$${\displaystyle {\begin{pmatrix}0011\\1001\end{pmatrix}}={\begin{pmatrix}0\\1\end{pmatrix}}{\begin{pmatrix}0\\0\end{pmatrix}}{\begin{pmatrix}1\\0\end{pmatrix}}{\begin{pmatrix}1\\1\end{pmatrix}}}$

この定理のエレガントな証明は、1991年にMuchnikによって帰納法によって与えられました。^[11]${\displaystyle m}$

実数と実数のベクトルには他の拡張も与えられている。^[8]

サミュエル・アイレンベルグは、彼の著書^[12]で証明なしで定理を発表しました。彼は「証明は正確で、長く、難しい。この素晴らしい定理のより合理的な証明を見つけるのは困難です。」と述べています。ジョルジュ・ハンセルは、簡単には入手できない会議の議事録で発表された、より単純な証明を提案しました。^[13]ドミニク・ペランの証明^[14]とアルーシュとシャリットの著書^[15]の証明には、本の正誤表に記載されている補題の1つに同じ誤りが含まれています。^[16]この誤りはトミ・カーキのメモで発見され、^[17]ミシェル・リゴとローラン・ワックスワイラーによって修正されました。^[18]この部分の証明は最近書かれたものです。^[19]

2018年1月、ティメン・JP・クレブスは、クロネッカーの近似基準ではなくディリクレの近似基準に基づいて、元の定理の簡略化された証明をArxivで発表しました。この論文は2021年に発表されました^。[20]採用された方法は、モル、ランパーサド、シャリット、スティプルアンティによって改良され、使用されています。^[21]

• Allouche, Jean-Paul [フランス語] ; Shallit, Jeffrey (2003)。自動シーケンス：理論、アプリケーション、一般化。ケンブリッジ：ケンブリッジ大学出版局。ISBN 0-521-82332-3。