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

Целочисленное соотношение между набором вещественных чисел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, x\textsuperscript2, ...,x\textsuperscriptn\}. Второе приложение — поискцелочисленной связи между вещественным числом x и наборомматематических констант, таких как e, π и ln(2), что приводитк выражению x в виде линейной комбинации этих констант.
 Типичным подходом в экспериментальной математике является применениечисленных методов и арифметики произвольной точности для поискаприближённого значения бесконечного ряда, бесконечного произведения илиинтеграла с большой точностью (обычно берётся по меньшей мере 100значащих цифр), а затем используется алгоритм поиска целочисленногосоотношения для определения целочисленной связи между этим значением инабором математических констант. Если целочисленное соотношение найдено,оно говорит о возможном исходного ряда, произведения или интеграла.Полученная гипотеза затем может быть проверена с помощью формальныхалгебраических методов. Чем выше используемая точность вычислений, темвыше уверенность, что найденное целочисленное соотношение не являетсяпросто .
 Заметным успехом такого подхода было использование алгоритма PSLQ дляпоиска целочисленного соотношения, которое привело к формуле Бэйли —Боруэйна — Плаффа для числа π. Алгоритм PSLQ также помог найтиновые тождества, в которые входит , и их появление в квантовой теорияполя. Алгоритм PSLQ помог в распознании точек бифуркации логистическогоотображения. Например, если B4 является четвёртой точкойбифуркации логистического отображения, константаα=-B4(B4-2) является корнем многочлена120-й степени с максимальным коэффициентом 257\textsuperscript30.Алгоритмы поиска целочисленных соотношений комбинируются с таблицамиматематических констант высокой точности и эвристическими методамипоиска, такими как или .
 Поиск целочисленных соотношений может быть использован для разложениямногочленов высокой степени.