Алгоритм цілочисельного відношення

Алгоритм цілочисельного відношення — це алгоритм знаходження цілочисельного відношення. Цілочисельне відношення між набором дійсних чисел x ₁, x ₂, …, x _n — це набір цілих чисел a ₁, a ₂, …, a _n, з яких не всі дорівнюють 0, такий, що

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

Зокрема, коли заданий набір дійсних чисел, відомих із заданою точністю, алгоритм цілочисельного відношення або знайде цілочисельне відношення між ними, або визначить, що не існує цілочисельного відношення з коефіцієнтами, величини яких менші за певну верхню межу.[1]

Історія

Для випадку n = 2 розширений алгоритм Евкліда може знайти будь-яке ціле відношення, яке існує між будь-якими двома дійсними числами x ₁ і x ₂ . Алгоритм генерує послідовні члени неперервного дробу x ₁ / x ₂ ; якщо між числами існує ціле відношення, то їх співвідношення є раціональним і алгоритм врешті-решт припиняє роботу.

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

Застосування

Алгоритми цілочисельних відношень мають численні застосування. Перше застосування полягає в тому, щоб визначити, чи ймовірно дане дійсне число x є алгебраїчним, шляхом пошуку цілочисельного відношення між набором степенів x {1, x, x ^2, …, x ^n }. Друге застосування полягає в пошуку цілочисельного відношення між дійсним числом x і набором математичних констант, таких як e, π і ln(2), що призведе до виразу для x як лінійної комбінації цих констант.

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

Помітним успіхом цього підходу було використання алгоритму PSLQ для знаходження цілочисельного відношення, яке призвело до формули Бейлі–Борвейна–Плуффа^[en] для значення π . PSLQ також допоміг знайти нові ідентичності, що включають множинні дзета-функцій^[en] та їхню появу в квантовій теорії поля; а також у визначенні точок біфуркації логістичної карти. Наприклад, якщо B₄ — четверта точка біфуркації логістичної карти, константа α = − B₄(B₄ − 2) є коренем многочлена 120-го степеня, найбільший коефіцієнт якого дорівнює 257^30 .[12][13] Алгоритми цілочисельних відношень поєднуються з таблицями високоточних математичних констант і евристичними методами пошуку в таких програмах, як Inverse Symbolic Calculator^[en] або Інвертор Плуффа .

Знаходження цілочисельного відношення можна використовувати для розкладання поліномів високого степеня.[14]

Примітки

1. Since the set of real numbers can only be specified up to a finite precision, an algorithm that did not place limits on the size of its coefficients would always find an integer relation for sufficiently large coefficients. Results of interest occur when the size of the coefficients in an integer relation is small compared to the precision with which the real numbers are specified.
2. Weisstein, Eric W. Integer Relation(англ.) на сайті Wolfram MathWorld.
3. Weisstein, Eric W. LLL Algorithm(англ.) на сайті Wolfram MathWorld.
4. Weisstein, Eric W. HJLS Algorithm(англ.) на сайті Wolfram MathWorld.
5. Johan Håstad, Bettina Just, Jeffrey Lagarias, Claus-Peter Schnorr: Polynomial time algorithms for finding integer relations among real numbers.
6. Weisstein, Eric W. PSOS Algorithm(англ.) на сайті Wolfram MathWorld.
7. Weisstein, Eric W. PSLQ Algorithm(англ.) на сайті Wolfram MathWorld.
8. A Polynomial Time, Numerically Stable Integer Relation Algorithm [Архівовано 2007-07-17 у Wayback Machine.] by Helaman R. P. Ferguson and David H. Bailey; RNR Technical Report RNR-91-032; July 14, 1992
9. Cipra, Barry Arthur. The Best of the 20th Century: Editors Name Top 10 Algorithms (PDF). SIAM News. 33 (4). Архів оригіналу (PDF) за 24 квітня 2021. Процитовано 20 липня 2022. [Архівовано 2021-04-24 у Wayback Machine.]
10. Jingwei Chen, Damien Stehlé, Gilles Villard: A New View on HJLS and PSLQ: Sums and Projections of Lattices., ISSAC'13
11. Helaman R. P. Ferguson, David H. Bailey and Steve Arno, ANALYSIS OF PSLQ, AN INTEGER RELATION FINDING ALGORITHM:
12. David H. Bailey and David J. Broadhurst, "Parallel Integer Relation Detection: Techniques and Applications, " [Архівовано 2011-07-20 у Wayback Machine.] Mathematics of Computation, vol. 70, no. 236 (October 2000), pp. 1719—1736; LBNL-44481.
13. I. S. Kotsireas, and K. Karamanos, «Exact Computation of the bifurcation Point B4 of the logistic Map and the Bailey–Broadhurst Conjectures», I. J. Bifurcation and Chaos 14(7):2417–2423 (2004)
14. M. van Hoeij: Factoring polynomials and the knapsack problem.

Посилання

• Recognizing Numerical Constants by David H. Bailey^[en] and Simon Plouffe^[en]
• Ten Problems in Experimental Mathematics by David H. Bailey, Jonathan M. Borwein, Vishaal Kapoor, and Eric W. Weisstein^[en]