Algoritmo de relación de enteros
De Wikipedia, la enciclopedia libre
  (Redirigido desde el algoritmo PSLQ )
Saltar a navegación Saltar a búsqueda

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 de números enteros encontrará una relación de números enteros entre ellos o determinará que no existe una relación de números enteros con coeficientes cuyas magnitudes sean menores que un cierto límite superior . [1]

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 . [2] 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. [3]
  • El algoritmo HJLS , desarrollado por Johan Håstad, Bettina Just, Jeffrey Lagarias y Claus-Peter Schnorr en 1986. [4] [5]
  • El algoritmo PSOS , desarrollado por Ferguson en 1988. [6]
  • El algoritmo PSLQ , desarrollado por Ferguson y Bailey en 1992 y sustancialmente simplificado por Ferguson, Bailey y Arno en 1999. [7] [8] En 2000, el algoritmo PSLQ fue seleccionado como uno de los "Diez mejores algoritmos del siglo" por Jack Dongarra y Francis Sullivan [9] a pesar de que se considera esencialmente equivalente a HJLS. [10] [11]
  • 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 cerradapara la serie original, producto o integral. Esta conjetura puede luego validarse mediante métodos algebraicos formales. Cuanto mayor sea la precisión con la que se conocen las entradas del 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 entera 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 . [12] [13]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ísticos en aplicaciones como la calculadora simbólica inversa o el inversor de Plouffe .

La búsqueda de relaciones enteras se puede utilizar para factorizar polinomios de alto grado. [14]

Referencias

  1. ^ Dado que el conjunto de números reales sólo se puede especificar hasta una precisión finita, un algoritmo que no pone límites al tamaño de sus coeficientes siempre encontrará una relación entera para coeficientes suficientemente grandes. Los resultados de interés ocurren cuando el tamaño de los coeficientes en una relación entera es pequeño en comparación con la precisión con la que se especifican los números reales.
  2. ^ Weisstein, Eric W. "Relación de enteros" . MathWorld .
  3. ^ Weisstein, Eric W. "Algoritmo LLL" . MathWorld .
  4. ^ Weisstein, Eric W. "Algoritmo HJLS" . MathWorld .
  5. ^ Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: Algoritmos de tiempo polinomial para encontrar relaciones enteras entre números reales. Versión preliminar: STACS 1986 ( Symposium Theoret. Aspects Computer Science ) Notas de la conferencia Computer Science 210 (1986), p. 105-118. SIAM J. Comput. , Vol. 18 (1989), págs. 859–881
  6. ^ Weisstein, Eric W. "Algoritmo de PSOS" . MathWorld .
  7. ^ Weisstein, Eric W. "Algoritmo PSLQ" . MathWorld .
  8. ^ Un tiempo polinomial, algoritmo de relación de enteros numéricamente estable por Helaman RP Ferguson y David H. Bailey; Informe técnico RNR RNR-91-032; 14 de julio de 1992
  9. ^ Cipra, Barry Arthur . "Lo mejor del siglo XX: los editores nombran los 10 algoritmos principales" (PDF) . Noticias SIAM . 33 (4).
  10. ^ Jingwei Chen, Damien Stehlé, Gilles Villard: una nueva visión de HJLS y PSLQ: sumas y proyecciones de celosías. , ISSAC'13
  11. ^ Helaman RP Ferguson, David H. Bailey y Steve Arno, ANÁLISIS DE PSLQ, UNA RELACIÓN INTEGRADA QUE ENCUENTRA ALGORITMO: [1]
  12. ^ David H. Bailey y David J. Broadhurst, "Detección de relaciones enteras paralelas: técnicas y aplicaciones", Matemáticas de la computación, vol. 70, no. 236 (octubre de 2000), págs. 1719-1736; LBNL-44481.
  13. ^ IS Kotsireas y K. Karamanos, "Cálculo exacto del punto de bifurcación B4 del mapa logístico y las conjeturas de Bailey-Broadhurst", IJ Bifurcation and Chaos 14 (7): 2417–2423 (2004)
  14. ^ M. van Hoeij: Factorizar polinomios y el problema de la mochila. J. of Number Theory, 95, 167–189, (2002).

enlaces externos

  • Reconocimiento de constantes numéricas por David H. Bailey y Simon Plouffe
  • Diez problemas en matemáticas experimentales por David H. Bailey, Jonathan M. Borwein , Vishaal Kapoor y Eric W. Weisstein
Obtenido de " https://en.wikipedia.org/w/index.php?title=Integer_relation_algorithm&oldid=934836430 "
Contribute a better translation