En la teoría de números aditivos , el teorema de Skolem-Mahler-Lech establece que si una secuencia de números se genera mediante una relación de recurrencia lineal , entonces, con un número finito de excepciones, las posiciones en las que la secuencia es cero forman un patrón que se repite regularmente. Más precisamente, este conjunto de posiciones se puede descomponer en la unión de un conjunto finito y un número finito de progresiones aritméticas completas . Aquí, una progresión aritmética infinita es completo si existen enteros a y b tales que la progresión se compone de todos los números enteros positivos iguales a b modulo una .
Este resultado lleva el nombre de Thoralf Skolem (que probó el teorema para secuencias de números racionales ), Kurt Mahler (que lo probó para secuencias de números algebraicos ) y Christer Lech (que lo probó para secuencias cuyos elementos pertenecen a cualquier campo de característica 0). ). Sus demostraciones utilizan análisis p-ádico .
Ejemplo
Considere la secuencia
- 0, 0, 1, 0, 1, 0, 2, 0, 3, 0, 5, 0, 8, 0, ...
que alterna entre ceros y los números de Fibonacci . Esta secuencia puede ser generada por la relación de recurrencia lineal
(una forma modificada de la recurrencia de Fibonacci), comenzando desde los casos base F (1) = F (2) = F (4) = 0 y F (3) = 1. Para esta secuencia, F ( i ) = 0 si y solo si i es uno o par. Por tanto, las posiciones en las que la secuencia es cero se pueden dividir en un conjunto finito (el conjunto singleton {1}) y una progresión aritmética completa (los números pares positivos ).
En este ejemplo, solo se necesitaba una progresión aritmética, pero otras secuencias de recurrencia pueden tener ceros en posiciones que forman múltiples progresiones aritméticas.
Resultados relacionados
El problema de Skolem es el problema de determinar si una secuencia de recurrencia dada tiene un cero. Existe un algoritmo para probar si hay un número infinito de ceros, [1] y, de ser así, encontrar la descomposición de estos ceros en conjuntos periódicos cuya existencia se garantiza según el teorema de Skolem-Mahler-Lech. Sin embargo, se desconoce si existe un algoritmo para determinar si una secuencia de recurrencia tiene ceros no periódicos ( Ouaknine & Worrell 2012 ).
Referencias
- Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter , yo (6), citado en Lech 1953.
- Mahler, K. (1935), "Eine arithmetisehe Eigenschaft der Taylor-koeffizienten ralionaler Funktionen", Akad. Wetensch. Amsterdam, Proc. , 38 : 50–60, citado en Lech 1953.
- Lech, C. (1953), "A Note on Recurring Series", Arkiv för Matematik , 2 : 417–421, doi : 10.1007 / bf02590997.
- Mahler, K. (1956), "Sobre los coeficientes de Taylor de funciones racionales", Proc. Cambridge Philos. Soc. , 52 : 39–48, doi : 10.1017 / s0305004100030966.
- Mahler, K. (1957), "Anexo al artículo" Sobre los coeficientes de Taylor de funciones racionales " ", Proc. Cambridge Philos. Soc. , 53 : 544, doi : 10.1017 / s0305004100032552.
- Ouaknine, Joël; Worrell, James (2012), "Problemas de decisión para secuencias de recurrencia lineal", Problemas de accesibilidad: 6º Taller Internacional, RP 2012, Burdeos, Francia, 17-19 de septiembre de 2012, Actas , Notas de conferencias en Ciencias de la Computación, 7550 , Heidelberg: Springer -Verlag, págs. 21-28, doi : 10.1007 / 978-3-642-33512-9_3 , MR 3040104.
enlaces externos
- ^ Berstel, Jean; Mignotte, Maurice (1976). "Deux propriétés décidables des suites récurrentes linéaires" . Boletín de la SMF . 104 : 175-184.