Целочисленное соотношение между набором вещественных чисел ${\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.}$

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

История

Для случая n = 2 расширение алгоритма Евклида может определить, существует ли целочисленное соотношение между двумя вещественными числами ${\displaystyle x_{1}}$ и ${\displaystyle x_{2}}$ . Алгоритм образует последовательность элементов разложения ${\displaystyle 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 , ${\displaystyle \pi }$ и ln(2), что приводит к выражению x в виде линейной комбинации этих констант.

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

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

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

Примечания

Литература

Ссылки

• by David H. Bailey and Simon Plouffe
• от 10 июня 2011 на Wayback Machine by David H. Bailey, Jonathan M. Borwein, Vishaal Kapoor, and Eric W. Weisstein

Для улучшения этой статьи желательно : Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии . После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.