По историческим причинам и для того, чтобы иметь приложение к решению диофантовых уравнений , результаты теории чисел были изучены больше, чем в других разделах математики, чтобы увидеть, можно ли эффективно вычислить их содержание . Когда утверждается, что некоторый список целых чисел является конечным, вопрос заключается в том, можно ли в принципе распечатать этот список после машинного вычисления.
Результат Литтлвуда [ править ]
Ранним примером неэффективного результата была теорема Дж. Э. Литтлвуда 1914 г. [1] о том, что в теореме о простых числах разности ψ ( x ) и π ( x ) с их асимптотическими оценками меняют знак бесконечно часто. [2] В 1933 году Стэнли Скьюз получил эффективную верхнюю границу для первой смены знака, [3] теперь известную как число Скьюза .
Более подробно, записывая числовую последовательность f ( n ), эффективным результатом об изменении ее знака бесконечно часто будет теорема, включающая для каждого значения N такое значение M > N , что f ( N ) и f ( M ) имеют разные знаки и такие, что M может быть вычислено с указанными ресурсами. На практике M можно было бы вычислить, взяв значения n из Nи далее, и вопрос в том, «как далеко вы должны зайти?» Особый случай - обнаружение первой смены знака. Интерес к вопросу заключался в том, что известное числовое свидетельство не показало изменения знака: результат Литтлвуда гарантировал, что это свидетельство было просто эффектом небольшого числа, но «малый» здесь включал значения от n до миллиарда.
Требование вычислимости отражает и контрастирует с подходом, используемым в аналитической теории чисел для доказательства результатов. Это, например, ставит под сомнение любое использование обозначений Ландау и подразумеваемых констант: являются ли утверждения чистыми теоремами существования таких констант, или можно восстановить версию, в которой 1000 (скажем) заменяет подразумеваемую константу? Другими словами, если бы было известно, что существует M > N со сменой знака и такое, что
- М = О ( G ( N ))
для некоторой явной функции G , скажем, построенной из степеней, логарифмов и экспонент, это означает только
- М < А . G ( N )
для некоторой абсолютной постоянной А . Значение A , так называемая подразумеваемая константа , также может потребоваться явным образом для вычислительных целей. Одна из причин Ландау нотация была популярное введение в том , что она скрывает , что именно есть. В некоторых косвенных формах доказательства может быть вовсе не очевидным, что подразумеваемая константа может быть сделана явной.
«Период Зигеля» [ править ]
Многие из основных результатов аналитической теории чисел, доказанных в период 1900–1950 гг., На самом деле оказались неэффективными. Основными примерами были:
- Теорема Туэ – Зигеля – Рота.
- Теорема Зигеля о целых точках , с 1929 г.
- Теорема 1934 года Ганса Хейльбронна и Эдварда Линфута о проблеме класса 1 [4]
- Результат 1935 года о нуле Зигеля [5]
- Теорема Зигеля – Вальфиша, основанная на нуле Зигеля.
Конкретная информация, которая осталась теоретически неполной, включала нижние оценки для чисел классов ( идеальные группы классов для некоторых семейств числовых полей растут); и оценки наилучших рациональных приближений алгебраических чисел в знаменателях . Последние могут быть прочитаны совершенно прямо как результаты по диофантовым уравнениям после работы Акселя Туэ . Результат, использованный для чисел Лиувилля в доказательстве, эффективен в том смысле, что он применяет теорему о среднем значении : но улучшения (к тому, что сейчас является теоремой Туэ – Зигеля – Рота) - нет.
Поздняя работа [ править ]
Более поздние результаты, особенно Алана Бейкера , изменили позицию. С качественной точки зрения теоремы Бейкера выглядят слабее, но они имеют явные константы и могут фактически применяться вместе с машинными вычислениями, чтобы доказать, что списки решений (предположительно полные) на самом деле являются полным набором решений.
Теоретические вопросы [ править ]
Здесь с трудностями удалось справиться с помощью радикально иных методов доказательства, гораздо больше внимания уделяя доказательству от противоречия. Используемая логика ближе к теории доказательств, чем к теории вычислимости и вычислимых функций . Предполагается, что трудности могут быть связаны с теорией вычислительной сложности . Неэффективные результаты все еще доказываются в форме A или B , где мы не можем сказать, какая именно.
Заметки [ править ]
- Перейти ↑ Littlewood, JE (1914). "Sur la distribution des nombres premiers". Comptes Rendus . 158 : 1869–1872. JFM 45.0305.01 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Феферман, Соломон (1996). «Разматывающая» программа Крейзеля (PDF) . Kreiseliana . Уэллсли, Массачусетс: А.К. Петерс. С. 247–273. Руководство по ремонту 1435765 . CS1 maint: обескураженный параметр ( ссылка )См. Стр. 9 препринта.
- ^ Skewes, S. (1933). «О разности π ( x ) - Li ( x )». Журнал Лондонского математического общества . 8 : 277–283. DOI : 10,1112 / jlms / s1-8.4.277 . JFM 59.0370.02 . Zbl 0007.34003 . CS1 maint: обескураженный параметр ( ссылка )
- ^ Хайльбронн, Х .; Линфут, EH (1934). «О воображаемых квадратичных корпусах первого класса». Ежеквартальный математический журнал . Оксфордская серия. 5 (1): 293–301. DOI : 10.1093 / qmath / os-5.1.293 ..
- ^ * Спринджук, В.Г. (2001) [1994], "Диофантовы приближения, проблемы эффективных" , Энциклопедия математики , EMS Press - комментирует неэффективность привязки.
Внешние ссылки [ править ]
- Спринджук, В.Г. (2001) [1994], "Диофантовы приближения" , Энциклопедия математики , EMS Press
