загадочная сложность теории чисел
Oct. 7th, 2017 12:53 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
avvaThe enigmatic complexity of number theory
Вопрос, который я сам себе не раз задавал, но насчет которого я тем не менее не уверен в том, насколько он осмыслен и интересен. Теория чисел - часть математики, которая изучает свойства целых чисел - вроде бы выделяется на фоне всех других математических дисциплин феноменальным количеством задач, которые просто сформулировать, но сложно решить. Сюда конечно относятся теорема Ферма и другие очень простые по формулировке и еще не решенные проблемы (гипотеза Гольдбаха: любое четное число можно представить в виде суммы двух простых; гипотеза о простых числах-близнецах, гипотеза Коллатца). Но по-моему дело не только в нерешенных или супер-тяжелых проблемах; теория чисел поражает также тем, как очень простые по формулировке утверждения требуют для своего доказательства "тяжелой артиллерии" из казалось бы, наивно говоря, более продвинутых областей математики.
В обсуждении по ссылке Скотт Ааронсон предлагает следующий ответ: арифметических действий с целыми числами достаточно, чтобы воплотить любой возможный алгоритм; отсюда следует, что уже даже относительно простые утверждения о целых числах могут упираться в фундаментальные ограничения типа "это невозможно доказать в принципе": теоремы Геделя о неполноте, неразрешимость проблемы остановки итп. Таким образом, в теории чисел неразрешимые задачи лежат буквально за углом, и расстояние о тривиальных фактов до них относительно невелико. Поэтому быстро приходят к сложным вопросам, которые еще разрешимы (скорее всего), но уже близки к неразрешимым.
Не уверен, что мне нравится этот ответ: то, что диофантовы уравнения упираются в неразрешимость в общем виде, это одно; а то, что мы не знаем, как решать даже очень просто выглядящие такие конкретные уравнения (пример из обсуждения: x^3+y^3 = z^3+33, неизвестно, есть ли решение у этого уравнения в целых числах) - другое, и мне не кажется очевидным, что эти две сложности друг с другом связаны. Но другого ответа у меня нет. Более того, нет даже уверенности, что этот вопрос осмыслен - возможно, это артефакт того, как мы определяем различные дисциплины в математике и то, что в них считается базисным-тривиальным?
Вопрос, который я сам себе не раз задавал, но насчет которого я тем не менее не уверен в том, насколько он осмыслен и интересен. Теория чисел - часть математики, которая изучает свойства целых чисел - вроде бы выделяется на фоне всех других математических дисциплин феноменальным количеством задач, которые просто сформулировать, но сложно решить. Сюда конечно относятся теорема Ферма и другие очень простые по формулировке и еще не решенные проблемы (гипотеза Гольдбаха: любое четное число можно представить в виде суммы двух простых; гипотеза о простых числах-близнецах, гипотеза Коллатца). Но по-моему дело не только в нерешенных или супер-тяжелых проблемах; теория чисел поражает также тем, как очень простые по формулировке утверждения требуют для своего доказательства "тяжелой артиллерии" из казалось бы, наивно говоря, более продвинутых областей математики.
В обсуждении по ссылке Скотт Ааронсон предлагает следующий ответ: арифметических действий с целыми числами достаточно, чтобы воплотить любой возможный алгоритм; отсюда следует, что уже даже относительно простые утверждения о целых числах могут упираться в фундаментальные ограничения типа "это невозможно доказать в принципе": теоремы Геделя о неполноте, неразрешимость проблемы остановки итп. Таким образом, в теории чисел неразрешимые задачи лежат буквально за углом, и расстояние о тривиальных фактов до них относительно невелико. Поэтому быстро приходят к сложным вопросам, которые еще разрешимы (скорее всего), но уже близки к неразрешимым.
Не уверен, что мне нравится этот ответ: то, что диофантовы уравнения упираются в неразрешимость в общем виде, это одно; а то, что мы не знаем, как решать даже очень просто выглядящие такие конкретные уравнения (пример из обсуждения: x^3+y^3 = z^3+33, неизвестно, есть ли решение у этого уравнения в целых числах) - другое, и мне не кажется очевидным, что эти две сложности друг с другом связаны. Но другого ответа у меня нет. Более того, нет даже уверенности, что этот вопрос осмыслен - возможно, это артефакт того, как мы определяем различные дисциплины в математике и то, что в них считается базисным-тривиальным?
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2017-10-07 10:07 am (UTC)no subject
Date: 2017-10-07 10:17 am (UTC)no subject
Date: 2017-10-07 10:24 am (UTC)Все на свете можно сосчитать. Значит вопрос о целых числах не проще вопроса "о всем". поэтому естественно ожидать, что ответ часто будет сложен.
no subject
Date: 2017-10-07 10:25 am (UTC)Видимо, так же и с целыми числами — это элементарный уровень сложного мира.
no subject
Date: 2017-10-07 10:27 am (UTC)no subject
Date: 2017-10-07 10:31 am (UTC)no subject
Date: 2017-10-07 10:54 am (UTC)no subject
Date: 2017-10-07 10:59 am (UTC)no subject
Date: 2017-10-07 11:27 am (UTC)no subject
Date: 2017-10-07 11:39 am (UTC)[Показываю пять спичек: это — число 5]
no subject
Date: 2017-10-07 11:47 am (UTC)Вообще, в школе меня всегда удивляло, что большинство задач "хорошо" решались. Дают задачу, получается длинная формула, которая после упрощения сворачивается в какой-нибудь красивый ответ типа "x=3". получил хороший ответ - значит, нигде не ошибся, а если получилось что-то типа корня из семидесяти трёх минут двенадцать разделить на семь - значит, где-то ошибся. И казалось, что "в жизни" ответы обычно будут второго типа, просто в школе специально подбирают коэффициенты. Сейчас понимаю, что бывает и так, и так. Промежуточная сложность может быть "мнимой", наподобие импликативного порядка, скрывающегося за кажущимся беспорядком. Но может и "не свернуться". Удачная теория должна давать по возможности однозначное соответствие между простыми понятиями и короткими формулами. Если короткое условие таит в себе сложную проблему - значит, теория не очень хороша. Ещё хуже, если наоборот - простое понятие опиывается длинной формулой.
С этой точки зрения теория чисел не идеальна, раз бывают короткие сложные задачи. Все ли простые понятия описываются короткими формулами в теории чисел - трудно сказать, потому что разум уже привык считать простыми понятия, которые коротко формулируются, и сложными - которые формулируются длинно.
no subject
Date: 2017-10-07 12:06 pm (UTC)no subject
Date: 2017-10-07 12:11 pm (UTC)no subject
Date: 2017-10-07 12:24 pm (UTC)no subject
Date: 2017-10-07 12:26 pm (UTC)no subject
Date: 2017-10-07 01:14 pm (UTC)no subject
Date: 2017-10-07 01:33 pm (UTC)В теории чисел обычно вопрос ставится явно. Например: имеет ли уравнение x^3+y^3=z^3+33 решение в целых числах.
Если вопрос чуть изменить, например попросить оценить сверху "плотность" таких решений - задача сразу упрощается на много порядков и часто становится вполне решаемой.
В этом смысле теория чисел ничуть не сложнее других разделов математики.
no subject
Date: 2017-10-07 01:44 pm (UTC)А вот вычислить тоже самое число с любой заданной наперед точностью - задача более чем тривиальная. И требует только машинного времени, если точность - триллионы знаков после запятой.
no subject
Date: 2017-10-07 01:55 pm (UTC)А его нет.
no subject
Date: 2017-10-07 02:25 pm (UTC)no subject
Date: 2017-10-07 03:24 pm (UTC)no subject
Date: 2017-10-07 03:31 pm (UTC)no subject
Date: 2017-10-07 03:41 pm (UTC)no subject
Date: 2017-10-07 04:10 pm (UTC)no subject
Date: 2017-10-07 04:11 pm (UTC)Действительно, очень удобно, иногда, для иллюстрации математического доказательства использовать двумерные чертежи. На них можно очень просто показать неравенство треугольника и тому подобные штуки, не отвлекаясь от основного доказательства. И доказательство основной теоремы алгебры, которое вы имеете в виду, скорее всего, чертежи использует для простоты понимания студентами.