Algoritmo de relación entera

Una relación entera entre un conjunto de números reales x ₁ , x ₂ , ..., x _n es un conjunto de enteros a ₁ , a ₂ , ..., a _n , no todos 0, tales que

${\displaystyle a_{1}x_{1}+a_{2}x_{2}+\cdots +a_{n}x_{n}=0.\,}$

Un algoritmo de relaciones enteras 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 relaciones enteras encontrará una relación entera entre ellos o determinará que no existe ninguna relación entera con coeficientes cuyas magnitudes sean menores que un cierto límite superior . ^{[ 1 ]}

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 ₁ y x ₂ . El algoritmo genera términos sucesivos de la expansión en fracción continua de x ₁ / x ₂ ; si existe una relación entera entre los números, entonces su cociente 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 un n general , no está claro si resuelve completamente el problema porque carece de los pasos detallados, las demostraciones y una cota 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 ] [ 9 ] [ 10 ]} En 2000, el algoritmo PSLQ fue seleccionado como uno de los "Diez mejores algoritmos del siglo" por Jack Dongarra y Francis Sullivan ^{[ 11 ]} aunque se considera esencialmente equivalente a HJLS. ^{[ 12 ] [ 13 ]}
• El algoritmo LLL ha sido mejorado por numerosos autores. Las implementaciones modernas de LLL pueden resolver problemas de relaciones enteras con n superior a 500.

Los algoritmos de relaciones enteras tienen numerosas aplicaciones. La primera consiste en determinar si un número real dado x es probable que sea algebraico , buscando una relación entera entre un conjunto de potencias de x {1, x , x ² , ..., x ⁿ }. La segunda aplicación consiste en 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á como resultado una expresión para x como una combinación lineal de estas constantes.

Un enfoque típico en matemáticas experimentales consiste en utilizar métodos numéricos y aritmética de precisión arbitraria para hallar 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). Posteriormente, se utiliza un algoritmo de relaciones enteras 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 analítica para la serie, el producto o la integral originales. Esta conjetura puede validarse mediante métodos algebraicos formales. Cuanto mayor sea la precisión con la que se conocen las entradas del algoritmo, mayor será la confianza en que cualquier relación entera encontrada no sea simplemente 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 ₄ es el cuarto punto de bifurcación del mapa logístico, la constante α  =  − B ₄ ( B ₄  −  2) es una raíz de un polinomio de grado 120 cuyo coeficiente más grande es 257 ³⁰ . ^{[ 14 ] [ 15 ]} 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 puede utilizarse para factorizar polinomios de alto grado. ^{[ 16 ]}

• Cómo reconocer constantes numéricas, por David H. Bailey y Simon Plouffe.
• Diez problemas de matemáticas experimentales. Archivado el 10 de junio de 2011 en Wayback Machine por David H. Bailey, Jonathan M. Borwein , Vishaal Kapoor y Eric W. Weisstein.