stringtranslate.com

Algoritmo de relación entera

Relación entera entre un conjunto de números reales x 1 , x 2 , ..., x n y un conjunto de números enteros a 1 , a 2 , ..., a n , no todos 0, tales que

Un algoritmo de relación entera es un algoritmo para encontrar relaciones enteras. 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 sean menores que un cierto límite superior . [1]

Historia

Para el caso n = 2, una extensión del algoritmo euclidiano puede hallar 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 existe una relación entera entre los números, entonces su proporción es racional y el algoritmo eventualmente termina.

Aplicaciones

Los algoritmos de relación entera tienen numerosas aplicaciones. La primera aplicación es determinar si es probable que un número real x 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 , π y ln(2), lo que dará lugar a una expresión para x como una combinación lineal de estas constantes.

Un enfoque típico en matemáticas experimentales es utilizar 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 utilizar un algoritmo de relación entera 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 en forma cerrada para la serie, el producto o la 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 del algoritmo, mayor será el nivel de confianza de que cualquier relación entera que se encuentre no sea 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 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 entera 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.

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 solo se puede especificar con una precisión finita, un algoritmo que no impusiera límites al tamaño de sus coeficientes siempre encontraría una relación entera para coeficientes suficientemente grandes. Los resultados de interés se producen 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 entera". MundoMatemático .
  3. ^ Weisstein, Eric W. "Algoritmo LLL". MathWorld .
  4. ^ Weisstein, Eric W. "Algoritmo HJLS". MundoMatemático .
  5. ^ Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: Algoritmos de tiempo polinomial para hallar relaciones enteras entre números reales. Versión preliminar: STACS 1986 ( Symposium Theoret. Aspects Computer Science ) Lecture Notes Computer Science 210 (1986), págs. 105–118. SIAM J. Comput. , vol. 18 (1989), págs. 859–881
  6. ^ Weisstein, Eric W. "Algoritmo PSOS". MundoMatemático .
  7. ^ Weisstein, Eric W. "Algoritmo PSLQ". MundoMatemático .
  8. ^ Algoritmo de relación entera numéricamente estable y en tiempo polinomial Archivado el 17 de julio de 2007 en Wayback Machine por Helaman RP Ferguson y David H. Bailey; Informe técnico RNR-91-032; 14 de julio de 1992
  9. ^ Cipra, Barry Arthur . "Lo mejor del siglo XX: los editores nombran los 10 mejores algoritmos" (PDF) . SIAM News . 33 (4). Archivado desde el original (PDF) el 24 de abril de 2021. Consultado el 17 de agosto de 2012 .
  10. ^ Jingwei Chen, Damien Stehlé, Gilles Villard: Una nueva visión de HJLS y PSLQ: sumas y proyecciones de redes., ISSAC'13
  11. ^ Helaman RP Ferguson, David H. Bailey y Steve Arno, ANÁLISIS DE PSLQ, UN ALGORITMO DE ENCUENTRO DE RELACIONES ENTERAS: [1]
  12. ^ David H. Bailey y David J. Broadhurst, "Detección de relaciones enteras paralelas: técnicas y aplicaciones", archivado el 20 de julio de 2011 en Wayback Machine, Mathematics of Computation, vol. 70, núm. 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: Factorización de polinomios y el problema de la mochila. J. of Number Theory, 95, 167–189, (2002).

Enlaces externos