stringtranslate.com

Problema de Skolem

Problema sin resolver en matemáticas :
¿Existe un algoritmo para probar si una secuencia recursiva constante tiene un cero?
(más problemas sin resolver en matemáticas)

En matemáticas , el problema de Skolem es el problema de determinar si los valores de una secuencia recursiva constante incluyen el número cero. El problema se puede formular para recurrencias sobre diferentes tipos de números, incluidos los números enteros , los números racionales y los números algebraicos . No se sabe si existe un algoritmo que pueda resolver 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 ( n ) = F ( n  − 1) + F ( n  − 2)

junto con los valores iniciales F (0) = 0 y F (1) = 1 . El problema de Skolem recibe su 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 recurrencias sobre los números racionales, y Mahler y Lech lo extendieron a otros sistemas de números . Sin embargo, las pruebas del teorema no muestran cómo comprobar si existen ceros.

Existe un algoritmo para comprobar si una secuencia recursiva constante tiene infinitos ceros y, en caso afirmativo, para construir una descomposición de las posiciones de esos ceros en subsecuencias periódicas, basándose en las propiedades algebraicas de las raíces del polinomio característico de la recurrencia dada. [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, que cubren el caso especial del problema para recurrencias de grado cuatro como máximo. Sin embargo, estas soluciones no se aplican a recurrencias de grado cinco o más. [1] [4] [5]

Para recurrencias de números enteros, se sabe que el problema de Skolem es NP-duro . [6]

Véase también

Referencias

  1. ^ abc Ouaknine, Joël; Worrell, James (2012), "Problemas de decisión para secuencias de recurrencia lineal", Reachability Problems: 6th International Workshop, RP 2012, Burdeos, Francia, 17-19 de septiembre de 2012, Actas , Lecture Notes in Computer Science, vol. 7550, Heidelberg: Springer-Verlag, págs. 21-28, doi :10.1007/978-3-642-33512-9_3, MR  3040104.
  2. ^ Skolem, Th. (1933), "Einige Sätze über gewisse Reihenentwicklungen und exponentiale Beziehungen mit Anwendung auf diophantische Gleichungen", Oslo Vid. Akád. Skrifter , yo (6)En cambio, Ouaknine y Worrell (2012) citan un artículo de Skolem de 1934 para este resultado.
  3. ^ 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 , SEÑOR  0414475.
  4. ^ Mignotte, M.; Shorey, Tennessee ; 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, SEÑOR  0743965.
  5. ^ Vereshchagin, NK (1985), "El problema de la aparición de un cero en una secuencia recursiva lineal", Matematicheskie Zametki (en ruso), 38 (2): 177–189, 347, MR  0808885.
  6. ^ Blondel, Vincent D.; Portier, Natacha (2002), "La presencia de un cero en una secuencia lineal recurrente de números enteros 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