Войти
По историческим причинам и для того, чтобы иметь приложение к решению диофантовых уравнений, результаты в теории чисел были изучены больше, чем в других разделы математики, чтобы проверить, эффективно ли вычислимо их содержание. Когда утверждается, что некоторый список целых чисел является конечным, вопрос заключается в том, можно ли в принципе распечатать этот список после машинного вычисления.
Ранним примером неэффективного результата был Дж. Теорема Э. Литтлвуда от 1914 года о том, что в теореме о простых числах разности ψ (x) и π (x) с их асимптотическими оценками меняют знак бесконечно часто. В 1933 году Стэнли Скьюз получил эффективную верхнюю границу для первой смены знака, теперь известную как число Скьюза.
. Более подробно, запись для числовой последовательности f (n), эффективный результат о том, что его знак меняется бесконечно часто, будет теорема, включающая для каждого значения N такое значение M>N, что f (N) и f (M) имеют разные знаки и такое, что M можно вычислить с указанными ресурсами. На практике M можно вычислить, взяв значения n начиная с N, и вопрос в том, «как далеко вы должны зайти?» Особый случай - обнаружение первой смены знака. Интерес к вопросу заключался в том, что известные числовые свидетельства не меняли знака: результат Литтлвуда гарантировал, что это свидетельство было всего лишь эффектом малых чисел, но «малые» здесь включали значения от n до миллиарда.
Требование вычислимости отражает и контрастирует с подходом, используемым в аналитической теории чисел для доказательства результатов. Это, например, ставит под сомнение любое использование нотации Ландау и ее подразумеваемых констант: утверждения являются чистыми теоремами существования для таких констант, или можно восстановить версию, в которой 1000 (скажем) принимает место подразумеваемой константы? Другими словами, если бы было известно, что существует M>N с изменением знака и такое, что
для некоторой явной функции G, скажем, построенной из степеней, логарифмов и экспоненты, что означает только
для некоторой абсолютной константы A. Значение A, так называемая подразумеваемая константа, может также потребоваться явным образом для вычислительных целей. Одна из причин, по которой нотация Ландау стала популярным введением, состоит в том, что она скрывает именно то, что такое A. В некоторых косвенных формах доказательства может быть вовсе не очевидным, что подразумеваемая константа может быть сделана явной.
Многие из основных результатов аналитической теории чисел, доказанных в период 1900–1950 гг., На самом деле оказались неэффективными. Основными примерами были:
Конкретная информация, которая осталась теоретически неполной, включала нижние границы для номеров классов (идеальные группы классов для некоторых семейств числовых полей растут); и оценки наилучших рациональных приближений к алгебраическим числам в терминах знаменателей. Последние могут быть прочитаны совершенно прямо как результаты по диофантовым уравнениям после работы Акселя Туэ. Результат, использованный для чисел Лиувилля в доказательстве, эффективен в том смысле, как он применяет теорему о среднем значении : но улучшения (к нынешней теореме Туэ – Зигеля – Рота) не производились..
Более поздние результаты, особенно Алан Бейкер, изменили позицию. Говоря качественно, теоремы Бейкера выглядят слабее, но они имеют явные константы и могут фактически применяться вместе с машинными вычислениями, чтобы доказать, что списки решений (предполагаемые как полные) на самом деле являются полным набором решений.
На трудности здесь были решены совершенно другие методы доказательства, гораздо больше внимания уделяется доказательству от противоречия. Используемая логика ближе к теории доказательства, чем к логике теории вычислимости и вычислимых функций. Предполагается, что трудности могут быть связаны с теорией сложности вычислений. Неэффективные результаты все еще подтверждаются в форме A или B, где мы не можем сказать, какая именно.
