Twierdzenie Cobhama

Nie mylić z tezą Cobhama .

Twierdzenie Cobhama jest twierdzeniem w kombinatoryce o słowach , które ma ważne powiązania z teorią liczb , zwłaszcza z liczbami przestępnymi i teorią automatów . Nieformalnie twierdzenie b2 _{to daje warunek} b1 _, aby elementy zbioru S liczb naturalnych zapisanych w podstawach i były rozpoznawane przez automaty skończone . W szczególności rozważ podstawy b ₁ i b ₂ takie, że nie są one potęgami tej samej liczby całkowitej. Twierdzenie Cobhama mówi, że S zapisane w podstawach b ₁ i b ₂ jest rozpoznawane przez automaty skończone wtedy i tylko wtedy, gdy S jest skończoną sumą postępów arytmetycznych . Twierdzenie zostało udowodnione przez Alana Cobhama w 1969 roku i od tego czasu dało początek wielu rozszerzeniom i uogólnieniom.

Definicje

Niech ${\ displaystyle n> 0}$ będzie liczbą całkowitą. Reprezentacją liczby naturalnej $\ textstyle$ podstawie b $b}$ jest ciąg cyfr ${\ Displaystyle n_ {0} n_ {1} \ cdots n_ {h}}$ taki To

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

gdzie ${\ Displaystyle 0 \ równoważnik n_ {0}, n_ {1}, \ ldots, n_ {h}<b}$ i ${\ Displaystyle n_ {h} >0}$ . Słowo ${\ Displaystyle n_ {0} n_ {1} \ cdots n_ {h}}$ jest często oznaczane lub prościej ${\ Displaystyle \ langle n \ rangle _ {b}}$ n ${\ displaystyle n_ {b}$ .

Zbiór liczb naturalnych S jest rozpoznawalny w podstawie lub prościej ${\ textstyle$$b}$ -rozpoznawalny lub ${\ textstyle b}$ -automatyczny , jeśli zbiór b ${\$ reprezentacji jego elementów w bazie $językiem$ rozpoznawalnym przez automat skończony na alfabecie ${\ Displaystyle \ {0,1, \ ldots, b-1 \}}$ .

Dwie dodatnie liczby ${\ Displaystyle$ i $\ ell}$ są multiplikatywnie niezależne , jeśli nie ma nieujemnych liczb całkowitych i takich, że ${\ displaystyle p}$ i ${\ displaystyle q}$${\ styl wyświetlania k^{p}=\ell ^{q}}$ . Na przykład 2 i 3 są multiplikatywnie niezależne, ale 8 i 16 nie są, ponieważ ${\ Displaystyle 8 ^ {4} = 16 ^ {3}}$ . Dwie liczby całkowite są multiplikatywnie zależne wtedy i tylko wtedy, gdy są potęgami tej samej trzeciej liczby całkowitej.

Stwierdzenia dotyczące problemów

Oryginalne stwierdzenie problemu

Podano więcej równoważnych stwierdzeń twierdzenia. Oryginalna wersja autorstwa Cobhama jest następująca:

Twierdzenie (Cobham 1969) $-$ Niech będzie zbiorem nieujemnych liczb całkowitych i $niech$$multiplikatywnie$ niech niezależnymi dodatnimi liczbami całkowitymi Wtedy jest rozpoznawalny przez automaty $skończone zarówno w notacji -ary, jak i -ary$$tylko$ i wtedy $gdy$ jest ostatecznie okresowy

Innym sposobem sformułowania twierdzenia jest użycie ciągów automatycznych . Sam Cobham nazywa je „jednolitymi sekwencjami znaczników”. Następująca forma znajduje się w książce Allouche i Shallit:

Twierdzenie — Niech $i będą$ dwiema multiplikatywnie $całkowitymi$ . Sekwencja jest zarówno $i$$jak$ -automatyczna $wtedy,$ gdy jest automatyczna .

$,$ że sekwencja charakterystyczna zbioru liczb naturalnych S rozpoznawalnych przez automaty skończone o podstawie k jest sekwencją k -automatyczną i odwrotnie, dla wszystkich sekwencji k i wszystkich liczb całkowitych ${\ Displaystyle 0 \ równoważnik i <k}$ , zbiór liczb naturalnych takich, że $S_ {i}}$$Displaystyle$ jest rozpoznawalny u $i$ w bazie ${\ displaystyle k}$ .

Sformułowanie w logice

Twierdzenie Cobhama można sformułować w logice pierwszego rzędu przy użyciu twierdzenia udowodnionego przez Büchiego w 1960 r. To sformułowanie w logice pozwala na rozszerzenia i uogólnienia. Wyrażenie logiczne wykorzystuje teorię

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

naturalnych liczb całkowitych wyposażonych w dodawanie i funkcję ${\ Displaystyle V_ {r} (0) = 1}$ przez $i$ dla dowolnej dodatniej liczby całkowitej $n }$ , ${\ Displaystyle V_ {r} (n) = m}$ jeśli ${\ Displaystyle r ^ {m}}$ jest największą potęgą ${\ displaystyle r}$ , która dzieli ${\ styl tekstu n}$ . Na przykład ${\ Displaystyle V_ {2} (20) = 4}$ i ${\ Displaystyle V_ {3} (20) = 1}$ .

Zbiór liczb całkowitych $można$ w logice pierwszego rzędu w ${\ Displaystyle \ langle N, +, V_ {r} \ rangle},$ jeśli można go opisać pierwszym -formuła porządku z równością, dodawaniem i ${\ displaystyle V_ {r}}$ .

Przykłady:

• Zbiór liczb nieparzystych można zdefiniować (bez $)$ za pomocą wzoru $y +1)}$
• Zbiór potęg liczby 2 można zdefiniować za pomocą prostego wzoru: $V_{2}(x)=x$${2 ^ {n} \ mid n \ geq$.

Twierdzenie Cobhama przeformułowane $.$ Niech S będzie zbiorem liczb naturalnych i niech będą $całkowitymi$ multiplikatywnie niezależnymi dodatnimi liczbami Wtedy S jest definiowalne pierwszego rzędu w ${\ Displaystyle \ langle N, +, V_ {k} \ rangle}$ i w ${\ Displaystyle \ langle N, + ,V_{\ell }\rangle }$ wtedy i tylko wtedy, gdy S jest ostatecznie okresowe.

Możemy posunąć analogię z logiką dalej, zauważając, że S jest definiowalne pierwszego rzędu w arytmetyce Presburgera wtedy i tylko wtedy, gdy jest ostatecznie okresowe. Tak więc zbiór S jest definiowalny w logice i ${\ Displaystyle \ langle N, +, V_ {k} \ rangle}$ i ${\ Displaystyle \ langle N, +,V_{\ell }\rangle }$ wtedy i tylko wtedy, gdy jest definiowalny w arytmetyce Presburgera .

Uogólnienia

Podejście przez morfizmy

Sekwencja automatyczna to określone słowo morficzne , którego morfizm jest jednolity , co oznacza, że ​​długość obrazów generowanych przez morfizm dla każdej litery alfabetu wejściowego jest taka sama. Zbiór liczb całkowitych jest zatem k -rozpoznawalny wtedy i tylko wtedy, gdy jego sekwencja charakterystyczna jest generowana przez jednolity morfizm, po którym następuje kodowanie , gdzie kodowanie jest morfizmem, który odwzorowuje każdą literę alfabetu wejściowego na literę alfabetu wyjściowego. Na przykład charakterystyczna sekwencja potęg liczby 2 jest tworzona przez morfizm 2-jednolity (co oznacza, że ​​​​każda litera jest odwzorowana na słowo o długości 2) w alfabecie $\ Displaystyle B = \ { a,0,1\}}$ zdefiniowane przez

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

który generuje nieskończone słowo

${\ Displaystyle a11010001 \ cdots}$ ,

po którym następuje kodowanie (to znaczy litera do litery), które odwzorowuje $displaystyle$ { \ $0}$ i pozostawia niezmienione, dając ${\ displaystyle 0}$ i ${\ displaystyle 1}$

${\ Displaystyle 011010001 \ cdots}$ .

Pojęcie zostało rozszerzone w następujący sposób: słowo morficzne jest zamiennikiem określonej liczby, jeśli jest zapisane w formie . $alpha$${$$}$

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

$\ Displaystyle f: B ^ {*} \ do B ^ {$ morfizm , przedłużalny w , ma następujące właściwości: * $}$

• wszystkie litery $)$ występują w i ${\ Displaystyle f ^ {\ omega} (b$ }
• ${\ Displaystyle \ alpha > 1}$ jest dominującą wartością własną macierzy morfizmu ${\ Displaystyle f}$ , a mianowicie macierzą ${ \ Displaystyle M (f) = (m_ {x, y}) _ {x \ w B, y \ w A}} ,$ gdzie ${\ Displaystyle m_ {x, y}}$ to liczba wystąpień litera w słowie ${\ displaystyle x} .$${\ displaystyle f (y)}$ .

Zbiór S $liczb$ naturalnych jest , jeśli jego $.$$-podstawiająca$ jest

Ostatnia definicja: $koniugaty$ Perrona jest liczbą algebraiczną taką ${\ Displaystyle \ {z '\ in \ mathbb {C}, | z' | <z \}}$ należą do dysku . Są to dokładnie dominujące wartości własne pierwotnych macierzy dodatnich liczb całkowitych.

Mamy wtedy następujące stwierdzenie:

Twierdzenie Cobhama o podstawieniach — Niech α i β będą dwiema multiplikatywnie niezależnymi liczbami Perrona. Wtedy ciąg x z elementami należącymi do skończonego zbioru jest zarówno α -podstawialny, jak i β -podstawczy wtedy i tylko wtedy, gdy x jest ostatecznie okresowe.

Podejście logiczne

Odpowiednik logiczny pozwala na rozważenie bardziej ogólnych sytuacji: automatyczne sekwencje nad liczbami naturalnymi $lub$ zbiorami zostały rozszerzone na liczby całkowite , na kartezjański ${\ displaystyle \ mathbb {Z}}$ produkty ${\ Displaystyle \ mathbb {N} ^ {m}}$ , do liczb rzeczywistych i do iloczynów kartezjańskich $Displaystyle$$\ mathbb {R} ^ {m$ .

Rozszerzenie do ${\ displaystyle \ mathbb {Z}}$

Kodujemy podstawowe $po$ całkowite, poprzedzając reprezentację dodatniej liczby całkowitej cyfrą i reprezentując ujemne liczby całkowite przez $k-1},$$displaystyle$ którym następuje k {\ displaystyle $} \displaystyle k}$ -dopełnienie . $1010$ przykład w podstawie 2 liczba 1010 $displaystyle$ . Potęgi 2 są zapisywane jako , a ich negatywy ${$ ponieważ $11000$$jest$ reprezentacją ${\ Displaystyle -16 + 8 = -8}$ ).

Rozszerzenie do ${\ Displaystyle \ mathbb {N} ^ {m}}$

Podzbiór ${\ Displaystyle X}$ z ${\ Displaystyle N ^ {m}}$ jest rozpoznawalny w bazie $,$ jeśli elementy ${\ Displaystyle X}$ zapisane jako wektory z ${\ displaystyle m} }$ , są rozpoznawalne na wynikowym alfabecie.

Na przykład w podstawie 2 mamy ${\ Displaystyle 3 = 11_ {2}}$ i ${\ Displaystyle 9=1001_ {2}}$ ; wektor ${\ Displaystyle {\ rozpocząć {pmatrix} 3 \\ 9 \ koniec {pmatrix}}}$ jest zapisany jako ${\ 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}}}$ .

Twierdzenie Semenova (1977) $niezależnymi$$multiplikatywnie$ i będą dwiema dodatnimi liczbami całkowitymi. Podzbiór z $\ Displaystyle$$N ^ {m}}$ jest $i$ rozpoznawalny i rozpoznawalny wtedy i tylko wtedy, gdy ${$ opisać $\ displaystyle S}$ w arytmetyce Presburgera.

Elegancki dowód tego twierdzenia podaje Muchnik w 1991 roku przez indukcję po ${\ displaystyle m}$ .

Liczbom rzeczywistym i wektorom liczb rzeczywistych nadano inne rozszerzenia.

Dowody

Samuel Eilenberg ogłosił twierdzenie bez dowodu w swojej książce; mówi: „Dowód jest poprawny, długi i trudny. Znalezienie bardziej rozsądnego dowodu tego wspaniałego twierdzenia jest wyzwaniem”. Georges Hansel zaproponował prostszy dowód, opublikowany w niełatwo dostępnych materiałach z konferencji. Dowód Dominique'a Perrina oraz książki Allouche'a i Shallita zawiera ten sam błąd w jednym z lematów, wymienionych na liście errat w tej książce. Ten błąd został odkryty w notatce Tomi Kärki i poprawiony przez Michela Rigo i Laurenta Waxweilera. Ta część dowodu została niedawno napisana.

W styczniu 2018 r. Thijmen JP Krebs ogłosił na Arxiv uproszczony dowód pierwotnego twierdzenia, oparty na kryterium aproksymacji Dirichleta zamiast kryterium Kroneckera; artykuł ukazał się w 2021 roku. Zastosowana metoda została udoskonalona i wykorzystana przez Mol, Rampersada, Shallita i Stipulanti.

Bibliografia

•   Allouche, Jean-Paul [po francusku] ; Szallit, Jeffrey (2003). Sekwencje automatyczne: teoria, zastosowania, uogólnienia . Cambridge: Cambridge University Press . ISBN 0-521-82332-3 .