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

Целочисленное соотношение между набором вещественных чисел x1,x2,...,xn — это набор целых чисел a1,a2,...,an, не все из которых равны нулю, таких, что
a1x1+a2x2+...+anxn=0.

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

История


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

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

Приложения


Алгоритм поиска целочисленных соотношений имеет многочисленные приложения. Первое приложение — определение, не является ли заданное вещественное число x алгебраическим, для чего производится поиск целочисленного соотношения между множеством степеней числа x \{1, x, x2, ..., xn\}. Второе приложение — поиск целочисленной связи между вещественным числом x и набором математических констант, таких как e, π и ln(2), что приводит к выражению x в виде линейной комбинации этих констант.
 Типичным подходом в экспериментальной математике является применение численных методов и арифметики произвольной точности для поиска приближённого значения бесконечного ряда, бесконечного произведения или интеграла с большой точностью (обычно берётся по меньшей мере 100 значащих цифр), а затем используется алгоритм поиска целочисленного соотношения для определения целочисленной связи между этим значением и набором математических констант. Если целочисленное соотношение найдено, оно говорит о возможном исходного ряда, произведения или интеграла. Полученная гипотеза затем может быть проверена с помощью формальных алгебраических методов. Чем выше используемая точность вычислений, тем выше уверенность, что найденное целочисленное соотношение не является просто .
 Заметным успехом такого подхода было использование алгоритма PSLQ для поиска целочисленного соотношения, которое привело к формуле Бэйли — Боруэйна — Плаффа для числа π. Алгоритм PSLQ также помог найти новые тождества, в которые входит , и их появление в квантовой теория поля. Алгоритм PSLQ помог в распознании точек бифуркации логистического отображения. Например, если B4 является четвёртой точкой бифуркации логистического отображения, константа α=-B4(B4-2) является корнем многочлена 120-й степени с максимальным коэффициентом 25730. Алгоритмы поиска целочисленных соотношений комбинируются с таблицами математических констант высокой точности и эвристическими методами поиска, такими как или .
 Поиск целочисленных соотношений может быть использован для разложения многочленов высокой степени.