Эффективные результаты в теории чисел

По историческим причинам и для того, чтобы иметь применение к решению диофантовых уравнений , результаты в теории чисел были изучены более тщательно, чем в других разделах математики, чтобы увидеть, является ли их содержание эффективно вычислимым ^{[ требуется ссылка ]} . Когда утверждается, что некоторый список целых чисел конечен, вопрос заключается в том, можно ли в принципе распечатать этот список после машинного вычисления.

Ранним примером неэффективного результата была теорема Дж. Э. Литтлвуда 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 , скажем, построенной из степеней, логарифмов и экспонент , это означает только

М < А . Г ( Н )

для некоторой абсолютной константы A . Значение A , так называемая подразумеваемая константа , также может потребовать явного указания для вычислительных целей. Одна из причин, по которой обозначение Ландау стало популярным введением, заключается в том, что оно скрывает, что именно такое A. В некоторых косвенных формах доказательства может быть совсем не очевидно, что подразумеваемая константа может быть сделана явной.

Многие из основных результатов аналитической теории чисел, доказанных в период 1900–1950 гг., на самом деле оказались неэффективными. Главными примерами были:

• Теорема Туэ –Зигеля–Рота
• Теорема Зигеля о целых точках , 1929 г.
• Теорема 1934 года Ганса Хейльбронна и Эдварда Линфута о проблеме класса номер 1 ^[4]
• Результат 1935 года по зеро Зигеля ^[5]
• Теорема Зигеля–Вальфиша, основанная на нуле Зигеля.

Конкретная информация, которая осталась теоретически неполной, включала нижние оценки для чисел классов ( идеальные группы классов для некоторых семейств числовых полей растут); и оценки для наилучших рациональных приближений к алгебраическим числам в терминах знаменателей . Последние можно было бы прочитать совершенно напрямую как результаты по диофантовым уравнениям, после работы Акселя Туэ . Результат, использованный для чисел Лиувилля в доказательстве, эффективен в том смысле, как он применяет теорему о среднем значении : но улучшений (к тому, что сейчас является теоремой Туэ–Зигеля–Рота) не было.

Более поздние результаты, особенно Алана Бейкера , изменили позицию. С качественной точки зрения теоремы Бейкера выглядят слабее, но они имеют явные константы и могут быть фактически применены в сочетании с машинными вычислениями для доказательства того, что списки решений (предположительно полные) на самом деле являются всем набором решений.

Трудности здесь были преодолены радикально иными методами доказательства, уделяя гораздо больше внимания доказательствам от противного . Задействованная логика ближе к теории доказательств, чем к логике теории вычислимости и вычислимых функций . Довольно свободно предполагается , что трудности могут лежать в области теории вычислительной сложности . Неэффективные результаты все еще доказываются в форме A или B , где мы не можем сказать, в какой именно.

• Спринджук, В.Г. (2001) [1994], "Диофантовы приближения", Энциклопедия математики , Издательство ЭМС