загадочная сложность теории чисел

[avva]

The enigmatic complexity of number theory

Вопрос, который я сам себе не раз задавал, но насчет которого я тем не менее не уверен в том, насколько он осмыслен и интересен. Теория чисел - часть математики, которая изучает свойства целых чисел - вроде бы выделяется на фоне всех других математических дисциплин феноменальным количеством задач, которые просто сформулировать, но сложно решить. Сюда конечно относятся теорема Ферма и другие очень простые по формулировке и еще не решенные проблемы (гипотеза Гольдбаха: любое четное число можно представить в виде суммы двух простых; гипотеза о простых числах-близнецах, гипотеза Коллатца). Но по-моему дело не только в нерешенных или супер-тяжелых проблемах; теория чисел поражает также тем, как очень простые по формулировке утверждения требуют для своего доказательства "тяжелой артиллерии" из казалось бы, наивно говоря, более продвинутых областей математики.

В обсуждении по ссылке Скотт Ааронсон предлагает следующий ответ: арифметических действий с целыми числами достаточно, чтобы воплотить любой возможный алгоритм; отсюда следует, что уже даже относительно простые утверждения о целых числах могут упираться в фундаментальные ограничения типа "это невозможно доказать в принципе": теоремы Геделя о неполноте, неразрешимость проблемы остановки итп. Таким образом, в теории чисел неразрешимые задачи лежат буквально за углом, и расстояние о тривиальных фактов до них относительно невелико. Поэтому быстро приходят к сложным вопросам, которые еще разрешимы (скорее всего), но уже близки к неразрешимым.

Не уверен, что мне нравится этот ответ: то, что диофантовы уравнения упираются в неразрешимость в общем виде, это одно; а то, что мы не знаем, как решать даже очень просто выглядящие такие конкретные уравнения (пример из обсуждения: x^3+y^3 = z^3+33, неизвестно, есть ли решение у этого уравнения в целых числах) - другое, и мне не кажется очевидным, что эти две сложности друг с другом связаны. Но другого ответа у меня нет. Более того, нет даже уверенности, что этот вопрос осмыслен - возможно, это артефакт того, как мы определяем различные дисциплины в математике и то, что в них считается базисным-тривиальным?

Comments

[randomisator.livejournal.com]

На днях шарился по лурку, набрёл на статью о простых числах, где предложен другой ответ: теория чисел так сложна, потому что она очень плохо сводится к геометрии. Лурк конечно не источник, но видимо тот, кто туда это написал, видел что-то более авторитетное на эту тему.

[shultz-flory.livejournal.com]

Что-то в этом есть. К примеру, все доказательства основной теоремы алгебры используют геометрические представления.

[thrasymedes.livejournal.com]

У меня такая версия: теория чисел похожа на естественные науки, так как ее предмет - целые числа - не создан математиками, а "реально существует" . В то же время методы естественных наук применять нельзя.

[yoksel-moksel.livejournal.com]

Существуют ли реально два одинаковых яблока? Нет. Одно больше другого.

[webface.livejournal.com]

Числа в природе не существуют :)

[shultz-flory.livejournal.com]

Добавлю, что всё считающееся «доказательством» в естественных науках, с т.з. математики таковым не является.

[gul-kiev.livejournal.com]

Целых чисел в реальности нет, это абстракция, к одной из интерпретаций которой, впрочем, все привыкли.

А электрики при вычислении цепей привыкли индуктивные и ёмкостные сопротивления измерять комплексными числами. Значит, и комплексные числа "реально существуют"? Это даже если не затрагивать квантовую механику, где вообще всё на комплексных функциях строится.
Как насчёт реального существования неевклидовых геометрий и многомерных пространств? Особенно в ракурсе теории относительности и теории струн?

Отличить математическую абстракцию от физической не так уж сложно. Можно придумать виртуальную реальность (сон или компьютерную симуляцию) с произвольными законами, там "реально существовать" может всё совсем не так, как в нашем мире. Но математические законы не зависят от реальности, и в любом виртуальном мире дважды два всё равно будет четыре - это не зависит от окружающего нас мира. Никакой дефект масс или релятивистское сложение скоростей не может опровергнуть арифметику. С остальной математикой то же самое.

[revoltp.livejournal.com]

Приведенный аргумент можно чуть видоизменить.

Все на свете можно сосчитать. Значит вопрос о целых числах не проще вопроса "о всем". поэтому естественно ожидать, что ответ часто будет сложен.

[yoksel-moksel.livejournal.com]

Отлично сказано.

[livelight]

Континуум сосчитать нельзя

[yoksel-moksel.livejournal.com]

Машина Тьюринга проста, но на ней можно реализовать алгоритм обработки входных данных любой сложности.
Видимо, так же и с целыми числами — это элементарный уровень сложного мира.

[livelight]

ИМХО, алгоритмы гораздо интереснее, чем "просто" числа, потому что предполагают многократное применение правил к результатам предыдущих применений этих правил, то есть, в пределе мы можем получать транзитивные замыкания по сложным многооперандным операциям. Для простейшей иллюстрации можно хотя бы на конвеевскую "жизнь" посмотреть, какие там сложные и расползающиеся узоры иногда получаются из простейших начальных условий. А в теории чисел бесконечен разве что перебор вариантов, но правила/уравнения не применяются сами к себе, так что там нет места "узорам" сложнее эратосфенова решета, которое получается всего лишь однократным применением некого правила (правда, ко всем натуральным числам).

[gul-kiev.livejournal.com]

Мне кажется, простых (разумных) ответов меньше, чем простых вопросов. Поэтому в любой области можно просто (в смысле, коротко) сформулировать сложную задачу, будь то геометрия, топология, теория множеств, алгоритмы или что угодно другое. Теория чисел тут выделяется, потому что её базовые понятия (в "дефолтной" интерпретации) понятны даже ребёнку, поэтому и задачи понятны. В отличие, например, от тензорного анализа, где даже короткое утверждение вряд ли будет понятно школьнику.

Вообще, в школе меня всегда удивляло, что большинство задач "хорошо" решались. Дают задачу, получается длинная формула, которая после упрощения сворачивается в какой-нибудь красивый ответ типа "x=3". получил хороший ответ - значит, нигде не ошибся, а если получилось что-то типа корня из семидесяти трёх минут двенадцать разделить на семь - значит, где-то ошибся. И казалось, что "в жизни" ответы обычно будут второго типа, просто в школе специально подбирают коэффициенты. Сейчас понимаю, что бывает и так, и так. Промежуточная сложность может быть "мнимой", наподобие импликативного порядка, скрывающегося за кажущимся беспорядком. Но может и "не свернуться". Удачная теория должна давать по возможности однозначное соответствие между простыми понятиями и короткими формулами. Если короткое условие таит в себе сложную проблему - значит, теория не очень хороша. Ещё хуже, если наоборот - простое понятие опиывается длинной формулой.

С этой точки зрения теория чисел не идеальна, раз бывают короткие сложные задачи. Все ли простые понятия описываются короткими формулами в теории чисел - трудно сказать, потому что разум уже привык считать простыми понятия, которые коротко формулируются, и сложными - которые формулируются длинно.

[xgrbml.livejournal.com]

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

[(Anonymous)]

В изначально аналитических разделах математики тоже крайне мало задач имеют явное аналитическое решение. Ситуацию спасает то, что в таких задачах можно строить аппроксимации, находить асимптотики и прочие интересные свойства решения.

В теории чисел обычно вопрос ставится явно. Например: имеет ли уравнение x^3+y^3=z^3+33 решение в целых числах.

Если вопрос чуть изменить, например попросить оценить сверху "плотность" таких решений - задача сразу упрощается на много порядков и часто становится вполне решаемой.

В этом смысле теория чисел ничуть не сложнее других разделов математики.

[(Anonymous)]

Upd. Еще пример. Доказать трансцендентность какого-то числа обычно задача невероятно сложная.

А вот вычислить тоже самое число с любой заданной наперед точностью - задача более чем тривиальная. И требует только машинного времени, если точность - триллионы знаков после запятой.

[avva.livejournal.com]

Интересная точка зрения, спасибо.

[dims12.livejournal.com]

Иными словами. Мы знаем, что любое целочисленное уравнение можно решить путём перебора, но перебрать надо бесконечное количество чисел. Предположение о том, что ВСЕГДА можно сократить эту задачу до конечного числа шагов, имеет, скорее всего, отрицательный ответ. Соответственно, ДОЛЖНО существовать сколько угодно много целочисленных задач, которые можно решить ТОЛЬКО бесконечным перебором. По теореме Геделя, распознать такую ситуацию нельзя, то есть, если мы такую задачу найдём, то будем над ней биться и либо в какой-то момент будем находить более короткий путь, либо не будем.

[(Anonymous)]

Ну знаете, количество разрешимых задач вообще счетное.

Каждая разрешимая задача имеет ответом конструктивное число, которых тоже счетное количество.

Так что любую разрешимую задачу "можно решить перебором, ТОЛЬКО бесконечным".

И что нам это дает в качестве добавленной стоимости?

[dims12.livejournal.com]

P.S. Но я уверен, что все целочисленные задачи можно свести к вероятностным, то есть, можно оценить вероятность того или иного решения и эта вероятность вычислима.

Возможно, из-за "фальшивости" целых чисел

[old-leon.livejournal.com]

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

Целые числа по своей природе порядковые. Когда у нас есть несколько однородных предметов, мы можем их пронумеровать: первый, второй, третий... В этом смысле целые числа имеют однозначный и простой смысл. Если же пойти дальше и использовать порядковый номер последнего элемента как меру их количества, то это уже содержит некоторую натяжку, дополнительное неявное предположение о дискретности и идентичности предметов. И на этом мы строим всю систему счисления, не важно десятичную ли, или другую.

Такая натяжка может до поры до времени прекрасно работать в очень многих областях, не приводя к трудностям и противоречиям. Для каких-то классов задач это даже может быть никакой не натяжкой. Но в других случаях "незаконное" отождествление порядкового с количественным может вернуться бумерангом, и вместо упрощения - всё запутать. Вероятно, теория чисел как раз такая область, где подмена работает против нас. Подозреваю, что в теоремах о бесконечных рядах тоже.

[rednyrg721.livejournal.com]

Видели, чем там дело кончилось по ссылке?

"put on hold as off-topic by Andy Putman, Daniel Loughran, Joseph Van Name, Stefan Kohl, Chris Godsil 7 hours ago

This question appears to be off-topic. The users who voted to close gave this specific reason:

"This question does not appear to be about research level mathematics within the scope defined in the help center." – Andy Putman, Daniel Loughran, Joseph Van Name"


"I regret to say I'm ending my participation in MathOverflow, for the same reason I decided a decade ago never again to edit Wikipedia. It's hard to express how disheartening it is to spend hours of volunteer labor explaining stuff---in this case, in a way that at least 19 MO users apparently found useful---only to have your work overridden by a smaller set of users, for being (part of something larger that's) "off-topic" or whatever it is. Who the hell has time for that? From now on, if I have math questions, I'll post them on my own blog. Was nice being here for 6 years; thanks everyone. – Scott Aaronson 6 hours ago"

[avva.livejournal.com]

Жалко, да.

[bntr.livejournal.com]

Представим себе, что мы продвигаемся вперед вдоль последовательности натуральных чисел
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12,...
и время от времени встречаем пары близнецов:
(3,5), (5,7), (11,13), (17,19), (29,31), (41,43),...
Существует ведь только две возможности: а) мы доходим до последней пары близнецов и больше их не встречаем (в этом случае гипотеза оказывается ложной), б) пары близнецов появляются все время (тогда гипотеза истинна).
Рассуждая таким образом, Вы демонстрируете свой платонизм. Вы привыкли оперировать натуральными числами так, как будто они составляют некий специфический "мир", который очень похож на мир повседневных вещей. Вы привыкли думать, что на практике любое достаточно определенное утверждение должно быть либо истинным, либо ложным. Поэтому Вы не в состоянии представить третью возможность: количество пар близнецов не является ни конечным, ни бесконечным. Однако такая возможность не будет нас удивлять, если мы осознаем, что система натуральных чисел содержит не только некоторую информацию о действительном мире, но и множество элементов фантазии. Почему Вы полагаете, что этот фантастический мир людям удалось "сфантазировать" так идеально правильно, что на вопрос о количестве близнецов обязательно будет существовать ответ?

из ВОКРУГ ТЕОРЕМЫ ГЕДЕЛЯ
https://dspace.lu.lv/dspace/bitstream/handle/7/1453/Podnieks_Vokrug_Teoremi_Gedela.pdf

[livelight]

Мощность множества между любыми конечными и любыми же бесконечными мощностями - это посильнее мощности между счётной и континуальной :)

[certus.livejournal.com]

Я бы сказал, что легко формулируемые и трудные для решения задачи лежат «за углом» более-менее в любой отрасли математики, и многие просто формулируемые конкретные вопросы типа «есть ли решение у такого-то уравнения?» именно таковы.

Волшебство скорее именно в том, что для некоторых из этих вопросов неожиданно находится подходящая «тяжёлая артиллерия» в других областях математики, и тут у вопросов про целые числа за счёт фундаментальности этого объекта есть серьёзные шансы на то, что «тяжёлая артиллерия» из других областей даст на них ответ.

[gaz-v-pol.livejournal.com]

Для меня волшебством в теории чисел является теорема Гудстейна (https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%93%D1%83%D0%B4%D1%81%D1%82%D0%B5%D0%B9%D0%BD%D0%B0).

Как известно, по ссылкам мало кто кликает, поэтому напишу рекламу. Описывается некоторый процесс, как можно формировать последовательность (не очень сложный, его вполне можно понять и реализовать самому). Теорема состоит в том, что с какого бы числа мы не начинали, всегда рано или поздно в последовательности появится 0 (и тогда все следующие члены также будут равны 0). Сама по себе теорема такого рода не выглядит чем-то специфическим -- ну есть какой-то итеративный процесс, ну сходится он всегда к 0, ну и что?

Красота в том, что эта теорема верна, но ее невозможно доказать (оставаясь в рамках аксиоматики Пеано). Мне трудно вместить это в голову. Как так может быть?!

После этого возникает мысль -- кто его знает, может быть гипотеза о конечности числа пар простых числел-близнецов тоже верна, но ее невозможно доказать? Или неверна, и это невозможно доказать? Может так быть, или есть какие-то основания считать, что именно для этой теоремы так быть не может? Мистика какая-то.

[(Anonymous)]

Полез в английскую вики почитать, как же ее доказывают (я не математик, так что сразу простите за святотатство); споткнулся об "replace ... with the first infinite ordinal number ω" -- имеется в виду, что омега- мощность счетных множеств, что ли, или как?

[nsinreal.livejournal.com]

Мне кажется, что это лживая простота задачи.
Задача выглядит так:
- найти решения уравнения какого-то сложного уравнения (например "x^3 + y^3 = z^3 + 33")
- но при этом x,y,z должны удовлетворять какому-то условию
Весьма легко найти условие, которое повысит сложность решения задачи до убер-сложной. И для меня удивительным является то, что почему-то считается, мол целые числа - это тривиальное условие.

Весь аппарат математики и геометрии весьма хорош в вещественных числах (или даже комплексных числах). И тут мы накладываем условие на числа - оно должно быть целым. Увы, я не знаю как это условие формулируется математически. Но мне почему-то кажется, что оно нетривиально

Ничего подобного....

[андрей лощинин (from livejournal.com)]

Всё очень просто. Когда ты решаешь такую уравняшку - ему как то всё равно какой вид и форму будут иметь решения.
Получив ответ мы сами даже можем выбрать потом нужную нам форму.
Тут дело в другом... Очень часто народ банально не понимает как надо их решать.
Вместо этого пишет всякий алгебрагеометрический бред...
Эти методы со скрипом работали когда уравняшки были крайне просты. Когда их чуток усложнили они вообще не работают.
Тогда они вместо того, чтоб усовершенствовать методы решили объявить на весь мир о алгоритмической не разрешимости....
Какой к чёрту алгоритм???
Их надо решать, а не болтать!