Эффективные результаты в теории чисел - Effective results in number theory

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

Результат Литтлвуда

Одним из первых примеров неэффективного результата был Дж. Э. Литтлвуд теорема 1914 г.,[1] что в теорема о простых числах различия обоих ψ (Икс) и π (Икс) с их асимптотическими оценками бесконечно часто меняют знак.[2] В 1933 г. Стэнли Скьюс получена эффективная верхняя оценка первой смены знака,[3] теперь известен как Число Скьюза.

Более подробно запись для числовой последовательности ж(п), эффективный результат о его смене знака бесконечно часто будет теоремой, в том числе для каждого значения N, ценность M > N такой, что ж(N) и ж(M) имеют разные знаки и такие, что M можно вычислить с указанными ресурсами. В практическом плане M будет вычисляться путем принятия значений п из N и далее, и вопрос в том, как далеко вы должны зайти? Особый случай - обнаружение первой смены знака. Интерес к вопросу заключался в том, что известные числовые свидетельства не меняли знака: результат Литтлвуда гарантировал, что это свидетельство было всего лишь эффектом небольшого числа, но «малые» здесь включали значения п до миллиарда.

Требование вычислимости отражает и контрастирует с подходом, используемым в аналитическая теория чисел чтобы доказать результаты. Это, например, ставит под сомнение любое использование Обозначения Ландау и его подразумеваемые константы: утверждения чистые теоремы существования для таких констант, или можно восстановить версию, в которой 1000 (скажем) занимает место подразумеваемой константы? Другими словами, если бы было известно, что M > N со сменой знака и такой, что

M = O (грамм(N))

для некоторой явной функции грамм, скажем, построенный из степеней, логарифмов и экспонент, это означает только

M < А.грамм(N)

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

"Период Зигеля"

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

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

Позже работа

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

Теоретические вопросы

С трудностями здесь справились радикально иные методы доказательства, гораздо больше внимания уделяя доказательству от противоречия. Используемая логика ближе к теория доказательств чем к теория вычислимости и вычислимые функции. Предполагается, что трудности могут заключаться в сфере теория сложности вычислений. Неэффективные результаты все еще подтверждаются в форме А или же B, где мы не можем сказать, какой именно.

Примечания

  1. ^ Литтлвуд, Дж. Э. (1914). "Sur la distribution des nombres premiers". Comptes Rendus. 158: 1869–1872. JFM  45.0305.01.
  2. ^ Феферман, Соломон (1996). "Разматывающая" программа Крейзеля " (PDF). Kreiseliana. Уэллсли, Массачусетс: А. К. Питерс. С. 247–273. МИСТЕР  1435765. См. Стр. 9 препринта.
  3. ^ Скьюс, С. (1933). «О разности π (Икс) - Ли (Икс)". Журнал Лондонского математического общества. 8: 277–283. Дои:10.1112 / jlms / s1-8.4.277. JFM  59.0370.02. Zbl  0007.34003.
  4. ^ Хайльбронн, Х.; Линфут, Э. (1934). «О воображаемых квадратичных корпусах первого класса». Ежеквартальный журнал математики. Оксфордская серия. 5 (1): 293–301. Дои:10.1093 / qmath / os-5.1.293..
  5. ^ *Спринджук, В. (2001) [1994], «Диофантово приближение, проблемы эффективного», Энциклопедия математики, EMS Press - комментирует неэффективность привязки.

внешняя ссылка