Алгоритм поиска целочисленных соотношений

Целочисленное соотношение между набором вещественных чисел ${\displaystyle x_{1},x_{2},...,x_{n}}$ — это набор целых чисел ${\displaystyle a_{1},a_{2},...,a_{n}}$, не все из которых равны нулю, таких, что

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

Алгоритм поиска целочисленных соотношений — это алгоритм поиска целочисленных соотношений между числами. В частности, если заданы вещественные числа с определённой точностью, алгоритм либо находит целочисленное соотношение между ними, либо определяет, что такой связи нет для коэффициентов, абсолютная величина которых меньше некоторой верхней границы^{[англ.] [1]}.

Для случая n = 2 расширение алгоритма Евклида может определить, существует ли целочисленное соотношение между двумя вещественными числами ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$. Алгоритм образует последовательность элементов разложения ${\displaystyle x_{1}/x_{2}}$ в непрерывную дробь. Если существует целочисленная взаимосвязь между числами, то их частное рационально и алгоритм, в конечном счёте, завершится.

• Алгоритм Фергюсона — Форкейда опубликовали в 1979 Фергюсон^[англ.] и Форкейд^[2]. Хотя в статье идёт речь о любом n, не совсем ясно, решает ли статья полностью задачу, поскольку в ней отсутствуют некоторые детали алгоритма, нет доказательств и точных границ, что существенно для достоверной имплементации.
• Первым алгоритмом с полным доказательством был ЛЛЛ-алгоритм, который разработали Арьен Ленстра, Хендрик Ленстра и Ласло Ловас в 1982^[3].
• Юхан Хостад, Беттина Джаст, Джефри Лагариас и Клаус-Петер Шнорр разработали алгоритм HJLS в 1986^[4][5].
• Фергюсон разработал в 1988 алгоритм PSOS^[6]
• Фергюсон и Бейли разработали алгоритм PSLQ в 1992 и в 1999 в значительной степени упростили (вместе с Арно)^[7][8]. В 2000 Джек Донгарра и Фрэнсис Салливан ^[9] включили алгоритм PSLQ в «Первую десятку алгоритмов столетия», хотя и признано, что большей частью он эквивалентен алгоритму HJLS^[10][11].
• Алгоритм ЛЛЛ улучшали множество авторов. Современная имплементация алгоритма ЛЛЛ может решать задачи поиска целочисленных соотношений с n, большим 500.

Алгоритм поиска целочисленных соотношений имеет многочисленные приложения. Первое приложение — определение, не является ли заданное вещественное число x алгебраическим, для чего производится поиск целочисленного соотношения между множеством степеней числа x {1, x, x², ..., xⁿ}. Второе приложение — поиск целочисленной связи между вещественным числом x и набором математических констант, таких как e, ${\displaystyle \pi }$ и ln(2), что приводит к выражению x в виде линейной комбинации этих констант.

Типичным подходом в экспериментальной математике является применение численных методов и арифметики произвольной точности для поиска приближённого значения бесконечного ряда, бесконечного произведения или интеграла с большой точностью (обычно берётся по меньшей мере 100 значащих цифр), а затем используется алгоритм поиска целочисленного соотношения для определения целочисленной связи между этим значением и набором математических констант. Если целочисленное соотношение найдено, оно говорит о возможном выражении в замкнутой форме^[англ.] исходного ряда, произведения или интеграла. Полученная гипотеза затем может быть проверена с помощью формальных алгебраических методов. Чем выше используемая точность вычислений, тем выше уверенность, что найденное целочисленное соотношение не является просто числовым артефактом^[англ.].

Заметным успехом такого подхода было использование алгоритма PSLQ для поиска целочисленного соотношения, которое привело к формуле Бэйли — Боруэйна — Плаффа для числа ${\displaystyle \pi }$. Алгоритм PSLQ также помог найти новые тождества, в которые входит многомерная дзета-функция^[англ.], и их появление в квантовой теория поля. Алгоритм PSLQ помог в распознании точек бифуркации логистического отображения. Например, если B₄ является четвёртой точкой бифуркации логистического отображения, константа α=-B₄(B₄-2) является корнем многочлена 120-й степени с максимальным коэффициентом 257^30[12][13]. Алгоритмы поиска целочисленных соотношений комбинируются с таблицами математических констант высокой точности и эвристическими методами поиска, такими как обратный символьный калькулятор^[англ.] или инвертор Плуффера^[англ.].

Поиск целочисленных соотношений может быть использован для разложения многочленов высокой степени^[14].

• Recognizing Numerical Constants by David H. Bailey and Simon Plouffe
• Ten Problems in Experimental Mathematics Архивная копия от 10 июня 2011 на Wayback Machine by David H. Bailey, Jonathan M. Borwein, Vishaal Kapoor, and Eric W. Weisstein