Teorema de Cobham

El teorema de Cobham es un teorema de combinatoria sobre palabras que tiene importantes conexiones con la teoría de números , en particular con los números trascendentales y la teoría de autómatas . De manera informal, el teorema establece la condición para que los miembros de un conjunto S de números naturales escritos en bases b ₁ y b ₂ sean reconocidos por autómatas finitos . Específicamente, considere bases b ₁ y b ₂ tales que no sean potencias del mismo entero. El teorema de Cobham establece que S escrito en bases b ₁ y b ₂ es reconocido por autómatas finitos si y solo si S difiere en un conjunto finito de una unión finita de progresiones aritméticas . El teorema fue demostrado por Alan Cobham en 1969 ^[1] y desde entonces ha dado lugar a muchas extensiones y generalizaciones. ^{[2] [3]}

Definiciones

Sea un número entero. La representación de un número natural en base es la sucesión de dígitos tal que ${\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}}$

donde y . La palabra a menudo se denota , o más simplemente, . ${\displaystyle 0\leq n_{0},n_{1},\ldots ,n_{h}<b}$ ${\displaystyle n_{h}>0}$ ${\displaystyle n_{0}n_{1}\cdots n_{h}}$ ${\displaystyle \langle n\rangle _{b}}$ ${\displaystyle n_{b}}$

Un conjunto de números naturales S es reconocible en base o más simplemente -reconocible o -automático si el conjunto de las representaciones de sus elementos en base es un lenguaje reconocible por un autómata finito en el alfabeto . ${\textstyle b}$ ${\textstyle b}$ ${\textstyle b}$ ${\displaystyle \{n_{b}\mid n\in S\}}$ ${\displaystyle b}$ ${\displaystyle \{0,1,\ldots ,b-1\}}$

Dos números enteros positivos y son multiplicativamente independientes si no hay números enteros no negativos y tales que . Por ejemplo, 2 y 3 son multiplicativamente independientes, pero 8 y 16 no lo son ya que . Dos números enteros son multiplicativamente dependientes si y solo si son potencias de un mismo tercer número entero. ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle p}$ ${\displaystyle q}$ ${\displaystyle k^{p}=\ell ^{q}}$ ${\displaystyle 8^{4}=16^{3}}$

Enunciados del problema

Planteamiento original del problema

Se han dado enunciados más equivalentes del teorema. La versión original de Cobham es la siguiente: ^[1]

Teorema (Cobham 1969)  :  Sea un conjunto de números enteros no negativos y sean y números enteros positivos multiplicativamente independientes. Entonces es reconocible por autómatas finitos tanto en notación -aria como -aria si y solo si es en última instancia periódico. ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle S}$ ${\displaystyle m}$ ${\displaystyle n}$

Otra forma de expresar el teorema es mediante secuencias automáticas . El propio Cobham las llama "secuencias de etiquetas uniformes". ^[4] La siguiente forma se encuentra en el libro de Allouche y Shallit: ^[5]

Teorema  —  Sean y dos números enteros multiplicativamente independientes. Una sucesión es a la vez -automática y -automática sólo si es -automática ^[6] ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle 1}$

Podemos demostrar que la secuencia característica de un conjunto de números naturales S reconocibles por autómatas finitos en base k es una secuencia k -automática y que, a la inversa, para todas las secuencias k -automáticas y todos los números enteros , el conjunto de números naturales tales que es reconocible en base . ${\displaystyle u}$ ${\displaystyle 0\leq i<k}$ ${\displaystyle S_{i}}$ ${\displaystyle s}$ ${\displaystyle u_{s}=i}$ ${\displaystyle k}$

Formulación en lógica

El teorema de Cobham se puede formular en lógica de primer orden utilizando un teorema demostrado por Büchi en 1960. ^[7] Esta formulación en lógica permite extensiones y generalizaciones. La expresión lógica utiliza la teoría ^[8]

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

de números enteros naturales dotados de adición y la función definida por y para cualquier entero positivo , si es la mayor potencia de que divide a . Por ejemplo, , y . ${\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}$

Un conjunto de números enteros se puede definir en lógica de primer orden si se puede describir mediante una fórmula de primer orden con igualdad, suma y . ${\displaystyle S}$ ${\displaystyle \langle N,+,V_{r}\rangle }$ ${\displaystyle V_{r}}$

Ejemplos:

• El conjunto de números impares es definible (sin ) mediante la fórmula ${\displaystyle V_{r}}$ ${\displaystyle (\exists y)(x=y+y+1)}$
• El conjunto de las potencias de 2 se define mediante la sencilla fórmula . ${\displaystyle \{2^{n}\mid n\geq 0\}}$ ${\displaystyle V_{2}(x)=x}$

Teorema de Cobham reformulado  :  Sea S un conjunto de números naturales y sean y dos enteros positivos multiplicativamente independientes. Entonces S es definible en primer orden en y en si y solo si S es en última instancia periódico. ${\displaystyle k}$ ${\displaystyle \ell }$ ${\displaystyle \langle N,+,V_{k}\rangle }$ ${\displaystyle \langle N,+,V_{\ell }\rangle }$

Podemos llevar la analogía con la lógica más allá, observando que S es definible en primer orden en la aritmética de Presburger si y solo si es en última instancia periódico. Por lo tanto, un conjunto S es definible en la lógica y si y solo si es definible en la aritmética de Presburger . ${\displaystyle \langle N,+,V_{k}\rangle }$ ${\displaystyle \langle N,+,V_{\ell }\rangle }$

Generalizaciones

Aproximación por morfismos

Una secuencia automática es una palabra mórfica particular , cuyo morfismo es uniforme , lo que significa que la longitud de las imágenes generadas por el morfismo para cada letra de su alfabeto de entrada es la misma. Por lo tanto, un conjunto de números enteros es k -reconocible si y solo si su secuencia característica es generada por un morfismo uniforme seguido de una codificación , donde una codificación es un morfismo que asigna cada letra del alfabeto de entrada a una letra del alfabeto de salida. Por ejemplo, la secuencia característica de las potencias de 2 se produce por el morfismo 2-uniforme (lo que significa que cada letra se asigna a una palabra de longitud 2) sobre el alfabeto definido por ${\displaystyle B=\{a,0,1\}}$

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

que genera la palabra infinita

${\displaystyle a11010001\cdots }$,

seguido de la codificación (es decir, letra a letra) que asigna y deja y sin cambios, dando ${\displaystyle a}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$

${\displaystyle 011010001\cdots }$.

La noción se ha ampliado de la siguiente manera: ^[9] una palabra mórfica es - sustitutiva de un cierto número si cuando se escribe en la forma ${\displaystyle s}$ ${\displaystyle \alpha }$ ${\displaystyle \alpha }$

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

donde el morfismo , prolongable en , tiene las siguientes propiedades: ${\displaystyle f:B^{*}\to B^{*}}$ ${\textstyle b}$

• todas las letras de aparecen en , y ${\displaystyle B}$ ${\displaystyle f^{\omega }(b)}$
• ${\displaystyle \alpha >1}$es el valor propio dominante de la matriz de morfismo , es decir, la matriz , donde es el número de ocurrencias de la letra en la palabra . ${\displaystyle f}$ ${\displaystyle M(f)=(m_{x,y})_{x\in B,y\in A}}$ ${\displaystyle m_{x,y}}$ ${\displaystyle x}$ ${\displaystyle f(y)}$

Un conjunto S de números naturales es - reconocible si su secuencia característica es - sustitutiva. ${\displaystyle \alpha }$ ${\displaystyle s}$ ${\displaystyle \alpha }$

Una última definición: un número de Perron es un número algebraico tal que todos sus conjugados pertenecen al disco . Éstos son exactamente los valores propios dominantes de las matrices primitivas de los números enteros positivos. ${\displaystyle z>1}$ ${\displaystyle \{z'\in \mathbb {C} ,|z'|<z\}}$

Tenemos entonces la siguiente afirmación: ^[9]

Teorema de Cobham para sustituciones  :  Sean α y β dos números de Perron multiplicativamente independientes. Entonces, una sucesión x con elementos pertenecientes a un conjunto finito es tanto α -sustitutiva como β -sustitutiva si y solo si x es en última instancia periódica.

Enfoque lógico

El equivalente lógico permite considerar situaciones más generales: las sucesiones automáticas sobre los números naturales o conjuntos reconocibles se han extendido a los números enteros , a los productos cartesianos , a los números reales y a los productos cartesianos . ^[8] ${\displaystyle \mathbb {N} }$ ${\displaystyle \mathbb {Z} }$ ${\displaystyle \mathbb {N} ^{m}}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} ^{m}}$

Extensión a ${\displaystyle \mathbb {Z} }$

Codificamos los números enteros base anteponiendo a la representación de un número entero positivo el dígito , y representando los números enteros negativos con seguido del complemento del número . Por ejemplo, en base 2, el número entero se representa como . Las potencias de 2 se escriben como , y sus negativos (ya que es la representación de ). ${\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}$

Extensión a ${\displaystyle \mathbb {N} ^{m}}$

Un subconjunto de es reconocible en base si los elementos de , escritos como vectores con componentes, son reconocibles sobre el alfabeto resultante. ${\displaystyle X}$ ${\displaystyle N^{m}}$ ${\displaystyle k}$ ${\displaystyle X}$ ${\displaystyle m}$

Por ejemplo, en base 2, tenemos y ; el vector se escribe como . ${\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}}}$

Teorema de Semenov (1977) ^[10]  —  Sean y dos enteros positivos multiplicativamente independientes. Un subconjunto de es -reconocible y -reconocible si y solo si es descriptible en aritmética de Presburger. ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle S}$ ${\displaystyle N^{m}}$ ${\displaystyle r}$ ${\displaystyle s}$ ${\displaystyle S}$

Muchnik dio una prueba elegante de este teorema en 1991 por inducción en . ^[11] ${\displaystyle m}$

Se han dado otras extensiones a los números reales y a los vectores de números reales. ^[8]

Pruebas

Samuel Eilenberg anunció el teorema sin demostración en su libro ^[12] ; dice: "La demostración es correcta, larga y difícil. Es un desafío encontrar una demostración más razonable de este excelente teorema". Georges Hansel propuso una demostración más simple, publicada en las actas de una conferencia, que no son de fácil acceso. ^[13] La demostración de Dominique Perrin ^[14] y la del libro de Allouche y Shallit ^[15] contienen el mismo error en uno de los lemas, mencionado en la lista de erratas del libro. ^[16] Este error fue descubierto en una nota de Tomi Kärki ^[17] y corregido por Michel Rigo y Laurent Waxweiler. ^[18] Esta parte de la demostración ha sido escrita recientemente. ^[19]

En enero de 2018, Thijmen JP Krebs anunció, en Arxiv, una prueba simplificada del teorema original, basada en el criterio de aproximación de Dirichlet en lugar del de Kronecker; el artículo apareció en 2021. ^[20] El método empleado ha sido refinado y utilizado por Mol, Rampersad, Shallit y Stipulanti. ^[21]

Notas y referencias

1. Cobham, Alan (1969). "Sobre la dependencia de bases de conjuntos de números reconocibles por autómatas finitos". Teoría de sistemas matemáticos . 3 (2): 186–192. doi : 10.1007/BF01746527 . MR  0250789.
2. Durand, Fabien; Rigo, Michel (2010) [Capítulo escrito originalmente en 2010]. "Sobre el teorema de Cobham" (PDF) . En Pin, J.-É. (ed.). Autómatas: de las matemáticas a las aplicaciones . Sociedad Matemática Europea.
3. Adamczewski, Boris; Bell, Jason (2010) [Capítulo escrito originalmente en 2010]. "Automata in number theory" (PDF) . En Pin, J.-É. (ed.). Autómatas: de las matemáticas a las aplicaciones . Sociedad Matemática Europea.
4. Cobham, Alan (1972). "Secuencias de etiquetas uniformes". Teoría de sistemas matemáticos . 6 (1–2): 164–192. doi : 10.1007/BF01706087 . MR  0457011.
5. Allouche, Jean-Paul [en francés] ; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge: Cambridge University Press . p. 350. ISBN 0-521-82332-3.
6. Una secuencia "1-automática" es una secuencia que es en última instancia periódica
7. Büchi, JR (1990). "Aritmética débil de segundo orden y autómatas finitos". Obras completas de J. Richard Büchi . Z. Math. Logik Grundlagen Math. Vol. 6. pág. 87. doi :10.1007/978-1-4613-8928-6_22. ISBN 978-1-4613-8930-9.
8. Bruyère, Véronique (2010). "Alrededor del teorema de Cobham y algunas de sus extensiones". Aspectos dinámicos de las teorías de autómatas y semigrupos . Taller satélite de aspectos destacados de AutoMathA . Consultado el 19 de enero de 2017 .
9. Durand, Fabien (2011). "Teorema de Cobham para sustituciones". Revista de la Sociedad Matemática Europea . 13 (6): 1797–1812. arXiv : 1010.4009 . doi : 10.4171/JEMS/294 .
10. Semenov, Alexei Lvovich (1977). "Los predicados regulares en dos sistemas numéricos son de Presburger". Sib. Mat. Zh. (en ruso). 18 : 403–418. doi :10.1007/BF00967164. MR  0450050. S2CID  119658350. Zbl  0369.02023.
11. Muchnik (2003). "El criterio definible para la definibilidad en la aritmética de Presburger y sus aplicaciones" (PDF) . Ciencias Informáticas Teóricas . 290 (3): 1433–1444. doi : 10.1016/S0304-3975(02)00047-6 .
12. Eilenberg, Samuel (1974). Autómatas, lenguajes y máquinas, vol. A. Matemáticas puras y aplicadas. Nueva York: Academic Press . págs. xvi+451. ISBN. 978-0-12-234001-7..
13. Hansel, Georges (1982). "A propósito de un teoría de Cobham". En Perrin, D. (ed.). Actes de la Fête des mots (en francés). Ruán: Greco de programación, CNRS. págs. 55–59.
14. Perrin, Dominique (1990). "Autómatas finitos". En van Leeuwen, Jan (ed.). Manual de informática teórica . Vol. B: Modelos formales y semántica. Elsevier. págs. 1–57. ISBN. 978-0444880741.
15. Allouche, Jean-Paul [en francés] ; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge: Cambridge University Press . ISBN 0-521-82332-3.
16. Shallit, Jeffrey; Allouche, Jean-Paul (31 de marzo de 2020). "Errata de secuencias automáticas: teoría, aplicaciones, generalizaciones" (PDF) . Consultado el 25 de junio de 2021 .
17. Tomi Kärki (2005). "Una nota sobre la demostración del teorema de Cobham" (PDF) . Rapport Technique n° 713. Universidad de Turku . Consultado el 23 de enero de 2017 .
18. Michel Rigo; Laurent Waxweiler (2006). "Una nota sobre sindeticidad, conjuntos reconocibles y el teorema de Cobham" (PDF) . Boletín de la EATCS . 88 : 169–173. arXiv : 0907.0624 . MR  2222340. Zbl  1169.68490 . Consultado el 23 de enero de 2017 .
19. Paul Fermé, Willy Quach y Yassine Hamoudi (2015). "El teorema de Cobham" (PDF) (en francés). Archivado desde el original (PDF) el 2 de febrero de 2017. Consultado el 24 de enero de 2017 .
20. Krebs, Thijmen JP (2021). "Una prueba más razonable del teorema de Cobham". Revista internacional de fundamentos de la informática . 32 (2): 203207. arXiv : 1801.06704 . doi :10.1142/S0129054121500118. ISSN  0129-0541. S2CID  39850911.
21. Mol, Lucas; Rampersad, Narad; Shallit, Jeffrey; Stipulanti, Manon (2019). "Teorema de Cobham y automaticidad". Revista internacional de fundamentos de la ciencia de la computación . 30 (8): 1363–1379. arXiv : 1809.00679 . doi :10.1142/S0129054119500308. ISSN  0129-0541. S2CID  52156852.

Bibliografía

• Allouche, Jean-Paul [en francés] ; Shallit, Jeffrey (2003). Secuencias automáticas: teoría, aplicaciones, generalizaciones . Cambridge: Cambridge University Press . ISBN 0-521-82332-3.