Algoritmo de relación de enteros - Integer relation algorithm

Una relación entera entre un conjunto de números reales x 1 , x 2 , ..., x n es un conjunto de números enteros a 1 , a 2 , ..., a n , no todos 0, tal que

Un algoritmo de relación de enteros es un algoritmo para encontrar relaciones de enteros. Específicamente, dado un conjunto de números reales conocidos con una precisión dada, un algoritmo de relación entera encontrará una relación entera entre ellos o determinará que no existe una relación entera con coeficientes cuyas magnitudes son menores que un cierto límite superior .

Historia

Para el caso n = 2, una extensión del algoritmo euclidiano puede encontrar cualquier relación entera que exista entre dos números reales cualesquiera x 1 y x 2 . El algoritmo genera términos sucesivos de la expansión fraccionaria continua de x 1 / x 2 ; si hay una relación entera entre los números, entonces su relación es racional y el algoritmo finalmente termina.

  • El algoritmo de Ferguson-Forcade fue publicado en 1979 por Helaman Ferguson y RW Forcade . Aunque el artículo trata la n general , no está claro si el artículo resuelve completamente el problema porque carece de los pasos detallados, las pruebas y un encuadernado de precisión que son cruciales para una implementación confiable.
  • El primer algoritmo con pruebas completas fue el algoritmo LLL , desarrollado por Arjen Lenstra , Hendrik Lenstra y László Lovász en 1982.
  • El algoritmo HJLS , desarrollado por Johan Håstad, Bettina Just, Jeffrey Lagarias y Claus-Peter Schnorr en 1986.
  • El algoritmo PSOS , desarrollado por Ferguson en 1988.
  • El algoritmo PSLQ , desarrollado por Ferguson y Bailey en 1992 y sustancialmente simplificado por Ferguson, Bailey y Arno en 1999. En 2000, el algoritmo PSLQ fue seleccionado como uno de los "Diez mejores algoritmos del siglo" por Jack Dongarra y Francis Sullivan incluso aunque se considera esencialmente equivalente a HJLS.
  • Numerosos autores han mejorado el algoritmo LLL. Las implementaciones modernas de LLL pueden resolver problemas de relaciones enteras con n por encima de 500.

Aplicaciones

Los algoritmos de relación de enteros tienen numerosas aplicaciones. La primera aplicación es determinar si un número real x dado es probable que sea algebraico , buscando una relación entera entre un conjunto de potencias de x {1, x , x 2 , ..., x n }. La segunda aplicación es buscar una relación entera entre un número real x y un conjunto de constantes matemáticas como e , π e ln (2), lo que conducirá a una expresión para x como una combinación lineal de estas constantes.

Un enfoque típico en matemáticas experimentales es usar métodos numéricos y aritmética de precisión arbitraria para encontrar un valor aproximado para una serie infinita , un producto infinito o una integral con un alto grado de precisión (generalmente al menos 100 cifras significativas) y luego usar un número entero algoritmo de relación para buscar una relación entera entre este valor y un conjunto de constantes matemáticas. Si se encuentra una relación entera, esto sugiere una posible expresión de forma cerrada para la serie, producto o integral original. Esta conjetura puede luego validarse mediante métodos algebraicos formales. Cuanto mayor sea la precisión con la que se conocen las entradas al algoritmo, mayor será el nivel de confianza de que cualquier relación de enteros que se encuentre no es solo un artefacto numérico .

Un éxito notable de este enfoque fue el uso del algoritmo PSLQ para encontrar la relación de enteros que condujo a la fórmula de Bailey-Borwein-Plouffe para el valor de π . PSLQ también ha ayudado a encontrar nuevas identidades que involucran múltiples funciones zeta y su aparición en la teoría cuántica de campos ; y en la identificación de puntos de bifurcación del mapa logístico . Por ejemplo, donde B 4 es el cuarto punto de bifurcación del mapa logístico, la constante α = - B 4 ( B 4  - 2) es una raíz de un polinomio de grado 120 cuyo coeficiente más grande es 257 30 . Los algoritmos de relación de números enteros se combinan con tablas de constantes matemáticas de alta precisión y métodos de búsqueda heurística en aplicaciones como la calculadora simbólica inversa o el inversor de Plouffe .

El hallazgo de relaciones enteras se puede utilizar para factorizar polinomios de alto grado.

Referencias

enlaces externos