Алгоритм поиска целочисленных соотношений (Glikjnmb hknvtg eylkcnvlyuud] vkkmukoyunw)

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

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

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

История

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

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

Приложения

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

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

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

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

Ссылки

• 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