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