¿Existe un algoritmo para probar si una secuencia constante recursiva tiene cero?
En matemáticas, el problema de Skolem es el problema de determinar si los valores de una secuencia constante-recursiva incluyen el número cero. El problema se puede formular para recurrencias sobre diferentes tipos de números, incluidos números enteros , números racionales y números algebraicos . No se sabe si existe un algoritmo que pueda solucionar este problema. [1]
Una relación de recurrencia lineal expresa los valores de una secuencia de números como una combinación lineal de valores anteriores; por ejemplo, los números de Fibonacci pueden definirse a partir de la relación de recurrencia
- F ( norte ) = F ( norte - 1) + F ( norte - 2)
junto con los valores iniciales F (0) = 0 y F (1) = 1 . El problema de Skolem lleva el nombre de Thoralf Skolem , debido a su artículo de 1933 que demuestra el teorema de Skolem-Mahler-Lech sobre los ceros de una secuencia que satisface una recurrencia lineal con coeficientes constantes. [2] Este teorema establece que, si dicha secuencia tiene ceros, entonces, con un número finito de excepciones, las posiciones de los ceros se repiten regularmente. Skolem demostró esto para las recurrencias sobre los números racionales , y Mahler y Lech lo extendieron a otros sistemas de números. Sin embargo, las demostraciones del teorema no muestran cómo probar si existen ceros.
Existe un algoritmo para probar si una secuencia constante-recursiva tiene infinitos ceros, y si es así para construir una descomposición de las posiciones de esos ceros en subsecuencias periódicas, basado en las propiedades algebraicas de las raíces del polinomio característico del dado. reaparición. [3] La parte difícil restante del problema de Skolem es determinar si el conjunto finito de ceros no repetidos está vacío o no. [1]
Se conocen soluciones parciales al problema de Skolem, cubriendo el caso especial del problema de las recurrencias de grado cuatro como máximo. Sin embargo, estas soluciones no se aplican a las recurrencias de grado cinco o más. [1] [4] [5]
Para las recurrencias enteras, se sabe que el problema de Skolem es NP-difícil . [6]
Referencias
- ^ a b c Ouaknine, Joël; Worrell, James (2012), "Problemas de decisión para secuencias de recurrencia lineal", Problemas de accesibilidad: sexto taller internacional, RP 2012, Burdeos, Francia, 17-19 de septiembre de 2012, Actas , Lecture Notes in Computer Science, 7550 , Heidelberg: Springer -Verlag, págs. 21-28, doi : 10.1007 / 978-3-642-33512-9_3 , MR 3040104.
- ^ Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akad. Skrifter , yo (6). Ouaknine y Worrell (2012) en cambio citan un artículo de 1934 de Skolem para este resultado.
- ^ Berstel, Jean; Mignotte, Maurice (1976), "Deux propriétés décidables des suites récurrentes linéaires" , Bulletin de la Société Mathématique de France (en francés), 104 (2): 175-184, doi : 10.24033 / bsmf.1823 , MR 0414475.
- ^ Mignotte, M .; Shorey, TN ; Tijdeman, R. (1984), "La distancia entre términos de una secuencia de recurrencia algebraica", Journal für die Reine und Angewandte Mathematik , 349 : 63-76, MR 0743965.
- ^ Vereshchagin, NK (1985), "El problema de la aparición de un cero en una secuencia lineal recursiva", Matematicheskie Zametki (en ruso), 38 (2): 177-189, 347, MR 0808885.
- ^ Blondel, Vincent D .; Portier, Natacha (2002), "La presencia de un cero en una secuencia recurrente lineal entera es NP-difícil de decidir", Álgebra lineal y sus aplicaciones , 351/352: 91–98, doi : 10.1016 / S0024-3795 (01 ) 00466-9 , MR 1917474.
enlaces externos
- Tao, Terence (25 de mayo de 2007), "Pregunta abierta: teorema de Skolem-Mahler-Lech efectivo" , Novedades