Простые числа — насколько велико наше бессилие?

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

    image

    Эту метафору будет проще понять, если провести аналогию с черной дырой: мы не знаем, что находится под ее горизонтом событий, и чтобы это узнать нам нужно придумать способ, как туда добраться. Нечто подобное существует в мире математики. Данное уравнение — это настоящая «формула» простого числа, но чтобы ею пользоваться, нам нужно придумать, как искать подходящие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}.

    Черная дыра и данное уравнение — это предельные состояния чего-то реального и абстрактного. И, если о первом существует достаточно догадок и представлений, то о втором, практически ничего не известно. Но, что если это действительно «математическая» черная дыра? Разве вам не интересно что может произойти, если мы попадем под горизонт?

    Из чего состоит стена?


    Числа — их нет в реальном мире. Бывает семь игральных костей, семь атомов, семь смертных грехов, но самой по себе семерки не существует — это абстракция. Да, мы бы могли сказать, что числа — это просто множество абстрактных объектов, однако, это целый мир. Мир, в котором, как и в мире реальном, существуют свои законы. Сама мысль об этом кажется очень странной. Тем не менее, существование такого раздела математики, как теория чисел, говорит о том, что эта «странность» очень важна для нас.

    Самым волнительным является то, что среди этих воображаемых объектов есть особенные — простые числа. Они как детерминированный хаос — предсказуемы и непредсказуемы одновременно, в зависимости от масштаба их рассмотрения. Например, находясь рядом с ними, мы можем заметить, что их количество перед некоторым произвольным числом n, не превзойдет:

    image

    Меняя масштаб, мы начинаем замечать очень много намеков на какие-то внутренние правила их поведения. Постепенно этих намеков становится слишком много. Все чаще и чаще звучат вопросы «Откуда они вообще могли взяться?», «А что если существует некий алгоритм получения простых чисел?», «А что если каждое простое число может быть получено с помощью одного и того же алгоритма?»

    Как появилась стена


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

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

    С задачей представления множества диофантовым уравнением, частично или полностью, может справиться компьютер. Но здесь появляется другая проблема — диофантовы уравнения не решаются в общем виде, т.е. какой-то единый алгоритм их решения отсутствует. Это не кажется большой проблемой, потому что мы знаем, что некоторые уравнения выделяются в отдельные виды, для решения которых уже найдены эффективные методы.

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

    Как же так получилось, что простые числа оказались перечислимы? Сам процесс создания уравнений, представляющих перечислимые множества, опирается на основания математики — арифметику и логику. И если мы имеем достаточно знаний о свойствах объектов некоторого множества, то, опираясь на эти знания, мы можем делать предположения об алгоритме, который позволяет их получать. И, как оказалось, знаний о свойствах простых чисел было накоплено достаточно для этой цели. Уравнение было получено, и теперь все вопросы, связанные с простыми числами, сводятся к нему одному.

    Но мы не можем его решить.

    Толщина и прочность стены


    Фактически, нам брошен вызов. И нам заранее известно о неизбежном поражении. Возможно, отступление было бы самым благоразумным решением. Но разве нам не нужны эти поражения, чтобы превзойти себя? Давайте хоть чуть-чуть попытаемся его решить.

    Взглянем на уравнение еще раз:

    image

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

    image

    Если решить эту систему уравнений и прибавить 2 к найденному значению k, то мы получим простое число. Но мы можем пойти и другим путем. Взять некоторое простое число, вычесть из него 2, получив таким образом значение k, затем подставить это значение в систему и попытаться найти значения остальных переменных относительно него. Именно этим путем мы и пойдем — попытаемся найти хоть одно решение данного полинома.

    На все переменные накладывается два строгих ограничения, они должны быть целыми и не могут быть отрицательными. Если мы примем k=0, то первое простое число, которое мы сможем получить — это 2. Это и будет нашей отправной точкой. После подстановки этого значения в систему уравнений она примет следующий вид:

    image

    Уравнения (1)-(5) — это линейные уравнения, т.е. степени всех переменных равны 1. Уравнения (6)-(11) имеют очень схожую структуру. Ну и, наконец, уравнения (12)-(14) тоже выделяются в отдельную группу, причем уравнения (13) и (14) похожи друг на друга, как две капли воды.

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

    Уравнения (6)-(11) являются модификациями уравнения Пелля:

    image

    В самом деле, если переписать их вот так:

    image

    то сходство становится очевидным. Это очень обнадеживающе, так как решать уравнения Пелля мы умеем довольно неплохо. Мы можем попробовать решать эту систему примерно так: сначала решаем какое-нибудь одно уравнение, его решения подставляем в другое, которое тоже решаем и так далее, до самого конца. Звучит довольно просто, но не мешало бы нарисовать что-то вроде графа подстановок, чтобы хоть примерно знать, в каком порядке решать уравнения:
    image

    Вроде, все просто.

    Удар по стене


    Мы начнем с уравнений Пелля. Для их решения напишем небольшой скрипт:

    from decimal import *
    getcontext().prec = 50
    
    def peq_dec(N):
        n = Decimal(N).sqrt()
    
        a = int(n)
        x = n - a
        p0, q0 = 1, 0
        p1, q1 = int(a), 1
    
        while True:
            a = int(1/x)
            x = 1/x - a
            p_i = a*p1 + p0
            q_i = a*q1 + q0
            if p_i**2 - N*q_i**2 == 1:
                return p_i, q_i
                break
            p0, q0 = p1, q1
            p1, q1 = p_i, q_i


    Благодаря ему мы можем сразу найти решение уравнения (10) n = 2, f = 17. Однако, прежде чем двигаться дальше, мы должны кое-что знать об уравнении Пелля.

    image

    Начнем с того, что n не может быть полным квадратом. К тому же у любого уравнения Пелля существует бесконечное количество решений, среди которых всегда есть тривиальное: x = 1 и y = 0. Каждое последующее решение может быть получено на основе предыдущих, по следующей рекуррентной формуле:

    image

    Получается, что нам достаточно найти минимальное нетривиальное решение, а все остальные мы можем получить, пользуясь простым алгоритмом. Например, для n = 2 мы можем легко найти такое решение, это x = 3 и y = 2, тогда последующие решения будут выглядеть так:

    17, 12
    99, 70
    577, 408
    3363, 2378
    19601, 13860
    114243, 80782
    665857, 470832
    3880899, 2744210
    22619537, 15994428
    131836323, 93222358
    768398401, 543339720
    4478554083, 3166815962
    26102926097, 18457556052
    152139002499, 107578520350
    886731088897, 627013566048


    Стоит ли продолжать дальнейшее решение? Конечно, стоит, но… мы можем попытаться предугадать, что нас ждет впереди.

    Давайте пока просто представим, что мы решаем систему уравнений из трех уравнений Пелля следующего вида:

    image

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

    image

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

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

    Но давайте вернемся к нашей «формуле» простых чисел. Что нас может ждать впереди?

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

    В определенный момент мы почувствуем некоторую уверенность в решении каждого отдельного уравнения системы. Но не всей системы. Мы постараемся применить какие-нибудь эвристические методы оптимизации, например, алгоритм отжига, или алгоритм муравья. Но и здесь мы потерпим неудачу. Для того, чтобы хоть как-то понять причины этих неудач, нам придется немного погрузиться в алгебраическую геометрию и топологию. Постепенно мы получим какое-то представление о «кристаллизуемой субстанции». Сможем отдаленно представить структуру гиперповерхности, на которую выпускаем муравьев.

    Опираясь на эти представления мы постараемся улучшить наши алгоритмы. Чтобы сделать это, мы будем брать самые лучшие достижения из многих разделов математики. Постепенно, в алгоритмах будет меньше случайности, но избавиться от нее все равно не получится. Что произойдет потом? Мы вдруг обнаружим, что множество подходящих кандидатов на истинное решение в некоторых местах является парадоксально плотным. Каждая такая плотность будет дарить надежду на то, что где-то в ее центре и спрятан заветный ответ. Муравьям такие плотности будут «казаться» чем-то вроде перевернутой гиперворонки. Мы будем стараться «бить» по их центрам и максимумам. Но что произойдет потом?

    Что за стеной?


    Наверное, не знаю как, но мы решим это уравнение. Может быть, нам помогут квантовые или (!) кварковые компьютеры. Но и это не станет дырой в стене. Наверное, дальше нас будут ждать Гауссовы простые числа и еще более сложное уравнение, которое будет представлять их множество. Потом, возможно, среди других гиперкомплексных чисел мы снова наткнемся на какое-то подобие «простого» поведения. Может это, в конце концов, и будет пределом, своеобразным горизонтом событий математической черной дыры.

    Что может быть под этим горизонтом? Наверное, какая-то математическая сингулярность. Наверное, мы будем знать абсолютно все обо всех множествах, сможем решать любые уравнения и любые задачи. А может новых вопросов и задач больше вообще не будет?

    Возникают именно такие мысли. Ну в самом деле, задайте любой вопрос о простых числах и благодаря данному уравнению вы можете получить на него ответ. Бесконечно ли количество простых чисел-близнецов? Решите данное уравнение, сделайте парочку алгебраических выкладок и получите ответ. Каких простых чисел больше, оканчивающихся на 1, 3, 7 или 9? Тот же самый алгоритм: пара-тройка выкладок и подстановка уравнения. Хотите быстро раскладывать числа на простые множители?..

    В заключение


    Впервые с этим уравнением я познакомился в 2008 году, к тому времени я уже сходил с ума по криптографии и теории чисел, в частности по схеме RSA и задаче факторизации. Конечно же, полином, генерирующий простые числа, показался мне очень интересной темой, но слишком сложной. Однако, все задачи, которые удавалось или не удавалось решить, так или иначе были связаны с диофантовыми уравнениями. Поэтому, уже в 2014 году я вновь обратился к этому полиному, решив просто исследовать все разделы математики подряд и искать то, что могло бы пригодиться в его решении. Конечно, ни о какой академической культуре всех моих трудов не может быть и речи — я никогда не вел систематических записей, никогда не агрегировал создаваемый код. Это просто мое хобби.

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

    Этой статьей я хотел показать, что к любой, самой сложной, даже непосильной задаче можно хоть чуть-чуть подступиться. Таких задач очень много, и можно выбрать ту, что по душе и ближе всего к интересуемой сфере деятельности. Конечно, чрезмерная сложность и гарантированное поражение лишат малейшего желания в этом начинании. Но весь парадокс в том, что самые интересные путешествия и приключения, даже в «не существующем» мире математики, чаще всего, начинаются именно так.
    Share post
    AdBlock has stolen the banner, but banners are not teeth — they will be back

    More
    Ads

    Comments 79

      +8
      Вы бы уравнение это назвали что ли… А то как его гуглить?
        +2
        Честно говоря я даже не знаю как его назвать… как «полином Мятисевича» что-то гуглится. Но это не полином Мятисевича.
          +3
          То есть это какое-то безвестное уравнение взятое непонятно откуда?
          +5
          Потому что он Матиясевич.
            +10
            Судя по всему, что бы сегодня больше не делать опечаток мне надо либо вообще перестать печатать, либо пойти и наконец-то выспаться. Сейчас параллельно печатаю текст для подготовки к ЕГЭ по математике: html, latex, русский и английский язык. Русские слова печатаются английскими буквами и наоборот, 2 \цдот 13 вместо 2 \cdot 13 и легкое недоумение от того что emmet не хочеть делать тег <б></б>.

            Всем кто ложится спать — спокойного сна.
            +4
            Про эту формулу (и множество смежных тем) написано в книге Манина и Панчишкина «Введение в современную теорию чисел». В электронном виде её как бы нет, но она ищется в Library Genesis (и я вам этого не говорил ;)). А автору статьи огромное спасибо, тема (особенно так хорошо представленная этой «вводной» публикацией) действительно захватывающая! (uchitel, а вы не читали эту книгу?)
              +1
              Не читал, к сожалению. Но теперь обязательно займусь ею. Спасибо.
              +1
              Вот исходная статья (Jones, J., Sato, D., Wada, H., & Wiens, D. (1976). Diophantine Representation of the Set of Prime Numbers), где приведен явный вид этой формулы (всё это основано на идеях Юрия Матиясевича).

              Статья в Википедии.
              +3
              Уравнение (1 — олицетворением данной стены является вот это уравнение:) и уравнение (2 — Взглянем на уравнение еще раз:) — разные уравнения, в первом (wz+h+i-q)^2, а в втором (wz+h+j-q)^2. Где правильное?
                +4
                Досадная опечатка. Правильно во втором: переменная j вместо i.

                УЖАСНАЯ ОПЕЧАТКА!!!
                  +3
                  Спасибо, что заметили. Самое обидное, что несколько раз, при написании скриптов, я пользовался именно этой неправильной записью.

                  Сейчас Постараюсь исправить.
                    +2
                    Исправил.
                    +1
                    Числа — их нет в реальном мире

                    Мы начинаем замечать очень много намеков на какие-то внутренние правила их поведения

                    Мы зря отрывает числа от «реального мира» — ибо движок, обеспечивающий соблюдение правил поведения чисел может быть только «реальным миром». В реальном мире мы можем разобрать вещество на молекулы, молекулы на атомы и установить причинно-следственную связь. Простые числа делятся только на единицу и на само себя — и все? Если мы знаем, что вещество твердое и хрупкое — много нам это даст? Алхимики городили классификацию веществ на столь узкой основе — толку было мало.
                      +1
                      Действительно, это ещё тот философский вопрос: а что является физическим представлением простого числа?
                        +2

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

                        +5
                        Числа — это абстракции, скажем так, самого низкого уровня, которые пригодны для подсчета реальных объектов и их частей, т.е. числа — это предмет арифметики. Буквенные обозначения чисел — это уже абстракции второго уровня, так как позволяют обобщить какие-то правила и закономерности арифметики. Группы, кольца и поля — это абстракции еще более высокого уровня, которые позволяют обобщать правила и закономерности алгебры (чем то похоже на языки программирования, не находите?).

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

                        Возможно, ваше негодование упирается в другой вопрос: распространяется ли антропный принцип на математику? Но мне кажется, что этот вопрос из каких-то глубин философии, на который я не осмелюсь даже пробовать ответить.
                          +2
                          Возможно, простота числа появляется не выше, а ниже арифметики в уровнях абстракции и какие-то важные ее свойства просто затираются абстрагированием. И чем выше уровень абстракции — тем выше бессилие.
                            –2
                            Изначально числа не были чем-то абстрактным, а применялись в быту. У одного было нечто, чего не было у другого и в соответствии с затраченным трудом на добычу того или иного ресурса и были придуманы числа. И вначале числа были, разумеется, только целыми и положительными. Потом появились всякие прохиндеи, банкиры и экономисты, которые стали паразитировать на людях и числах. Вы по-ближе к реальности будьте, по-меньше этих абстракций над абстракциями над абстракциями. Смысл жизни то в чем? Жить в своих фантазиях и абстракциях?

                            uchitel, например, пользоваться математикой, в которой существуют лишь положительные числа.

                            to panvartan, если было наоборот, то было странно. Бессилие — это пытаться разобраться в чужих фантазиях и абстракциях. я сейчас бабахну абстракцию, а другие 100500 человек пусть головы ломают, может того кто наабстрагировался, отпустить домой?:) он и так слишком далек от реального мира.
                              0

                              Не было числа 7, было 7 яблок. Даже числа сами по себе уже абстракция.

                            +5
                            это называется «спор о природе универсалий», и тянется этот спор с античности. Идея о том, что «универсалии» (например, числа) в каком-то смысле реально существуют в реальном мире (хотя, возможно, и отдельном от нашего — в какой-нибудь параллельной вселенной? Платон называл это миром идей) называется платонизмом. Другая идея — что они не существуют ни в каком виде, а являются просто соглашениями — называется номинализмом. В современной научной среде платонистов откровенно недолюбливают…
                              +2
                              И имеют все основания на это недолюливание. Но платонизм гораздо легче романтизировать, чем я и воспользовался при написании статьи. Однако, старался не забывать использовать кавычки при каждом словосочетании со словом «мир».
                                0
                                В современной научной среде платонистов откровенно недолюбливают…

                                А откуда такая информация? Ультрафинитистов, например, есть за что недолюбливать: зачем-то тащат физические ограничения в математику (по результатам оценок на текущий момент, которые вполне могут измениться). Что с платонизмом не так? Если два математика докажут взаимоисключающие утверждения в одной аксиоматике, один из них будет не прав (или система аксиом противоречива). Правильность доказательства не зависит от субъективных ощущений конкретного математика или даже всего математического сообщества, так что предположение о независимом существовании математических структур ничему не противоречит.

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

                                  Если сказать, что число существует, то неизбежно начнутся насмешки, тапа: «тогда, оно может и нагреваться и охлаждаться, а может оно еще и гнется?». Хотя в действительности, есть математические структуры, которым присущи свойства реальных физических объектов и процессов.
                                    +1
                                    Мне просто кажется, что если всерьез относиться к тому, что математические структуры могут реально существовать, то шансы на потерю умственного здоровья очень сильно возрастают.

                                    Занятно. Мы всю жизнь имеем дело со структурами, которые отражают физический мир, но не тождественны ему — с нашими ощущениями. Но многие предпочитают отказаться от очевидного и утвержают, что ощущения "на самом деле"(тм) не существуют, а единственный способ существования — способ существования физических тел.


                                    Я не понимаю, что может быть такого с-ума-сводящего в возможности разных способов существования, но, видимо, что-то есть.

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

                                      Иногда появляются вполне физические ощущения, от работы с этими абстракциями.

                                      Со временем, я даже выработал правило, что если тебя отвлекают от работы, то надо отвлекаться.
                                      +3
                                      Рекомендую книгу Макса Тегмарка «Наша математическая Вселенная», в которой утверждается, что что реальны только математические структуры.
                                        +2

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

                                  +7
                                  Почему Вы полином называете уравнением? Да, я согласен что это не полином Мятисевича, потому что это полином Матиясевича(см. Википедию). Что значить решить полином? Решают уравнение. А здесь что с чем уравнивается?

                                  Данное уравнение — это настоящая «формула» простого числа, но чтобы ею пользоваться, нам нужно придумать, как искать подходящие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}.


                                  Что такое подходящие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}?
                                  Вот что говорит Википедия:
                                  "… существуют многочлены, множество положительных значений которых при неотрицательных значениях переменных совпадает с множеством простых чисел" И, далее приводится, как пример такого многочлена, полином Матиясевича. Отсюда следует, что нужно только брать неотрицательные значения переменных {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}, вычислять значение полинома и если оно положительно, то это значение и есть простое число. Так в чем проблема? Почему она четко не обозначена вначале, а обрисовывается только при углублении в текст?
                                  Черная дыра и данное уравнение — это предельные состояния чего-то реального и абстрактного. И, если о первом существует достаточно догадок и представлений, то о втором, практически ничего не известно. Но, что если это действительно «математическая» черная дыра. Разве вам не интересно что может произойти, если мы попадем

                                  Куда попадем? «Практически ничего не известно» — кому не известно и не обидятся ли математики?
                                  Ну, если уж этот полином черная дыра, то что мы скажем об этальных когомологиях, о многообразиях Колаби-Яу, о программе Ленглендса т.д.?
                                  Да это не черная дыра, а просто дырочка в наших знаниях.

                                    +12
                                    Называю, потому что имею на это полное право, т.к. я нисколько не отрицаю, того что у меня нет академической культуры и того что это мое хобби, а не предмет профессиональной деятельности.

                                    Обидятся ли математики? Обидятся только те, чье ЧСВ видно из космоса. С остальными всегда можно найти общий язык и даже выпить пива.

                                    Да и собственно, что вас так сильно смутило: метафоры, аналогии, преувеличения? Это Хабр, а не научный журнал. Я поделился тем, что мне интересно и поделился так, как посчитал нужным.
                                      +4

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

                                        +3
                                        Если честно, я не понимаю, что такого страшного в этом приравнивании понятия «полином» к понятию «уравнение». Для меня это абсолютно равнозначные понятия. Перечислимые множества описываются полиномами, конкретные элементы этих множеств получаются только если рассматривать данные полиномы, как уравнения. Скорее всего, это вопрос моей математической неграмотности. Но если это было бы так фатально, то я бы обязательно об это споткнулся в ходе работы.

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

                                        А потом просто подумал: «Да какого черта! Мне не надо знать что такое ямб и литота что бы наслаждаться поэзией. Мне никого не нужно учить поэтическим приемам, перед тем, как кому-то читать свое стихотворение. Я кое где был, кое что видел, и вернулся вот с такими впечатлениями. Все.»
                                          +1
                                          Понимаете, в статьях обычно есть вещи, которые я знаю заранее, и вещи, которые для меня новы. Но если в понятных мне вещах я вижу некорректные формулировки, определения, «шероховатости», то возникает подозрение — вероятно, и в новой для меня части есть эти же огрехи? Возможно, эта статья не так уж полезна, если новые знания из нее будут (не совсем) корректны?

                                          Что касается некорректных определений — я 6 лет проучился на мехмате и все эти 6 лет меня приучали к тому, что неточность, неоднозначность, некорректность определений и формулировок в математике недопустима — это та область, где объекты зачастую непонятны «на интуитивном уровне» и для хоть как-то продуктивной дискуссии необходимо, чтобы участники говорили на одном языке. Приводили большое количество примеров, когда это правильно было нарушено, с комичными последствиями.

                                          Конкретно про уравнения — вот без пояснений, на «интуитивном уровне», кажется, что если называть полином уравнением, это будет означать, что есть уравнение вида «полином == 0» (в статье не так), если говорить, что уравнение является формулой для каких-то чисел, то это означает, что числа являются решениями этого уравнения (в статье не так). По-моему, можно было сразу написать, что простые числа являются значениями этого полинома при некоторых значениях переменных, и проблемой является нахождение этих чисел (для чего нужно решить уравнение «полином от переменных==простое число), было бы понятно с самого начала, а не с середины статьи.
                                            +2
                                            Вот теперь согласен на все 100%

                                            Мне реально не хватает образования, что сильно сказывается на моем «математическом языке». Цель статьи состояла в том, что бы показать нечто интересное, поделиться какими-то мыслями и впечатлениями. И конечно же ее можно было написать гораздо лучше. Но здесь срабатывает как раз парадокс «интуитивного» понимания: «Интуитивно понимаю, а объяснить словами не могу.» А еще сложно уловить момент в котором надо заметить, что «раз это понятно тебе, то это вовсе не означает, что это понятно остальным.»

                                            Изначально, негативные комментарии показались очень язвительными. Но опять же — я сам виноват, в том что не понимаю некоторых вещей.

                                            Спасибо, что разъяснили.
                                      0

                                      Ваш комментарий был для меня информативнее, чем вся статья, спасибо.

                                      +2
                                      Простые числа — насколько велико наше бессилие?
                                      Какое же тут бессилие, просто посмотрите как приближает формула используя всего 35 нулей дзета функции — Источник.
                                      График приближения


                                      График приближения 2

                                        0
                                        В одном из своих интервью, которое я никак не могу найти, Матиясевичь говорил о своих попытках выразить нули дзета функции через диофантовы уравнения и по моему даже приводил примеры уравнения в котором только коэфициенты были математическими константами. Что как бы намекает, на существование возможности исследовать эти нули не только аналитическими методами, но и алгебраическими.

                                        Хотя возможно, я что-то путаю, так как не могу найти это интервью.
                                        +4
                                        Спасибо вам за статью, это всего третья или четвёртая статья о математике, которую я прочёл полностью, потому что она более-менее понятно написана.

                                        Сравнения с чёрной дырой оставлю на вашей совести, тем более аналогия лично мне вполне понятна =)

                                        Вы сумели заинтересовать. Ток «уравнение» на «полином» всё-таки замените и автора его укажите, а то как-то не очень уважительно к его трудам выходит.
                                          +2
                                          У работы, где этот полином впервые появляется четыре автора и сами они его никак не называют. Точно так же как и не попадались названия в других отечественных и иностранных источниках. Однако, попадались упоминания некоторых авторов оригинальной работы о переписке с другими математиками, которые помогали им в работе. Судя по всему, много людей прилагали усилия к созданию данного полинома.

                                          Называть его «Полином Матиясевича» (а такие упоминания встречались) тоже неверно, так как сам полином является частным случаем выдвинутого Матиясевичем доказательства диофантовости перечислимых множеств.

                                          А по поводу «уравнений» и «полиномов»… почему-то мое сознание любителя-самоучки решило, что это настолько близкие понятия, что перестало делать между ними различия :) Позвольте, я оставлю все — как есть, хоть и понимаю, что это неправильно.

                                          Я очень рад, что статья вам понравилась и вроде бы вообще «неплохо зашла». Но в тоже время, прекрасно понимаю, что статью можно было бы улучшить. Однако, времени на все это к сожалению нет, поэтому и был выбран такой своеобразный «НаучПоп».

                                          Ну и конечно же я надеюсь, что кто-нибудь и правда заинтересуется математикой и сможет извлечь из этого интереса какую-нибудь пользу: начнет программировать гораздо раньше чем я, гораздо раньше чем я познакомится с системами символьных вычислений и визуализации данных. Гораздо раньше чем я поймет, что нужно учить английский язык и получить качественное образование. В общем, у меня очень много надежд, связанных с молодым поколением :)
                                          +3
                                          Смотрел как раз недавно youtu.be/EK32jo7i5LQ вот это видео — Почему простые числа создают спирали. Они тут использовали круговые координаты. На мой взгляд это немного другой взгляд на проблему простых чисел.
                                            0
                                            Потрясающий ролик. Хорошее дополнение к статье.
                                              0
                                              Потрясающий канал! Спасибо!
                                                0
                                                У меня даже мурашки побежали когда увидел эту спираль при изменении масштаба. Спасибо за ссылку.
                                                0
                                                Интересно, а как ведут себя простые числа в других системах исчисления?
                                                  0
                                                  Наверное, точно так же. Но может быть, что-то новое там и найдется, ведь основание системы может быть любым, так что можно писать скрипты и проверять — дело нехитрое :)
                                                    +3
                                                    Ну, во всяком случае, там подобный вопрос:
                                                    Каких простых чисел больше, оканчивающихся на 1, 3, 7 или 9?

                                                    не будет иметь смысла, а будет другой вопрос, и может быть там будет что-то интересное.
                                                  0
                                                  А вы Оливера Сакса не читали? Он описывает случай из своей практики, когда близнецы с повреждением мозга играли друг с другом в простые числа и доходили в этой игре до очень многозначных… не умея при этом элементарных математических операций… Я когда-то про этот рассказ тут писал: habr.com/ru/post/192038
                                                    0
                                                    Не читал, зато читал вашу статью :)

                                                    Это действительно очень любопытный факт, с точки зрения нейробиологии. Я конечно могу заблуждаться, но мне кажется что нейросетевой подход к криптографии и теории чисел вполне обоснован и перспективен.
                                                      +1
                                                      Некоторые авторы попробовали проверить детали рассказа Сакса и нашли нестыковки. Детали я не помню, но что-то было там сомнительное (вроде не было справочников по которым можно было проверить или что-то такое)
                                                      0
                                                      как искать подходящие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}.
                                                      Я прошу прощения, может, не глубоко вник в решения, но s, t и u уже известны?
                                                        0
                                                        Некоторые переменные, даже не знаю как выразиться… некоторые переменные являются независимыми и по сути могут быть либо произвольными, например, как v в третьем уравнении, либо быть произвольными, но удовлетворять равенству. Например, переменная t в 12-ом уравнении может быть любой, но что бы решить это уравнение, значение переменной должно быть подходящим. Если не найти подходящее значение переменной t, то не получится отыскать значения переменной z. В дальнейшем переменная t больше нигде не понадобится, а вот значение переменной z будет подставлено в другие уравнения.
                                                        0
                                                        100 пунктов к карме за популярную статью, почему перечислимое множество можно задать диофантовым уравнением. Я вроде даже как немного логикой увлекался, и даже знаю, сколько смекалки пришлось Геделю задействовать, чтобы произвольные k начальных чисел отрезка уравнением задать, но здесь — вообще что-то космическое.
                                                          0

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

                                                            0
                                                            Я вас прекрасно понимаю. Какое-то время я серьезно считал, что данное уравнение связано с гипотезой Терстона, пока не понял, что вообще ничего не понимаю в этом вопросе :) Но в самой математике, можно встретить очень много любопытных связей. Например определитель матрицы может быть вычислен с помощью комбинаторики, а сами матрицы могут быть использованы в создании дифференциальных уравнений. Казалось бы совершенно отдельные разделы математики, но точки соприкосновения все равно имеют.
                                                            +1
                                                            Бывает семь игральных костей, семь атомов, семь смертных грехов, но самой по себе семерки не существует — это абстракция

                                                            WAT?

                                                              +1
                                                              То общее, что между всеми этими множествами находит наше сознание. «Семерка» не физична и вопрос, будет ли она существовать там, куда не дотягивается сознание ни одного существа, — открытая проблема философии.
                                                                +1
                                                                добро пожаловать в реальность. семерки не существует нигде, кроме как у тебя в голове.
                                                                  +3

                                                                  А грехи значит объективно существуют?

                                                                  0
                                                                  Аниме такое есть. Точно существует. И даже манга.
                                                                    +1
                                                                    Как символический намек, на то, что к религиям я отношусь вообще несерьезно. Во многом, благодаря математике.
                                                                      +1

                                                                      Скорее наоборот. Противопоставляете реальные вещи абстрактным и в качестве реальной вещи, которая существует, называете "грех".

                                                                        0
                                                                        Формально, так и есть. Но если бы я вместо этого указал 7 баллов кармы на Хабре — суть одна и та же но реакция может быть другой.
                                                                    0
                                                                    Совершенно прекрасная статья, большое спасибо, особенно меня взбудоражила мысль, что решение уравнения настолько сильно задевает все разделы математики, что выведя его мы выведем все важные формулы математики. Не буду спать ночью.

                                                                    P.S. А что все так нашли в интерстелларе? Я помню выходил из кино и плевался, и плевалась моя жена, весьма далекая на тот момент от инженерии и тем паче науки. Как примерно выглядит черная дыра (точнее, аккреционный диск) все давно представляли — ну как воронка вокруг черного шара. Что масса искривляет пространство я узнал от отца-физика в 5 лет. Художественно снят неплохо, спасибо что нет лазеров и чубаки, но после того как Макконахи попал внутрь книжной полки, мне захотелось уйти из зала. При всем уважении к Кипу Торну, его научная, даже научно-популярная ценность не сильно отошла от темной стороны силы и чубак.

                                                                    P.P.S Кстати, даже если не все, можно вспомнить теорему Ферма — вроде ее недавно доказали — сколько прекрасного было открыто в поисках ее решения.
                                                                      0
                                                                      Больше всего, на самом деле, меня удивило, то что «они» сбрасывали бомбы на голодающих из стратосферы. А потом «они» поняли, что выхода нет и начали спонсировать NASA. Я немало размышлял, о том кто такие «они».

                                                                      Фильм очень глубокомысленный, если задаваться вопросами, которыми обычно задаваться не очень хочется.
                                                                      0
                                                                      Данное уравнение — это настоящая «формула» простого числа, но чтобы ею пользоваться, нам нужно придумать, как искать подходящие {a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p, q, w, v, x, y, z}

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

                                                                        0
                                                                        Подходящие, означает, что они должны быть целыми, неотрицательными и а после их подстановки в уравнение должно получится положительное значение. Найти такие подходящие значения переменных на самом деле очень сложно.
                                                                          0
                                                                          Спасибо, теперь понятно. Но как это связано с решением диофантовых уравнений? Кажется решение уравнения подразумевает поиск множества корней. Но тут речь идет о поиске таких x при которых F(x) > 0. Положим я знаю все y, для которых F(y) = 0, неочевидным кажется переход от этих у к x.
                                                                            0
                                                                            Фактически, получается, что если вам известно при каких y, F(y) = 0, то это означает, что вы можете обладать достаточным знанием решения уравнения. А это может значить, что вы можете обобщить этот метод, для поиска какого-нибудь класса решений, например x при которых F(x) > 0.

                                                                            В диофантовых уравнениях, как правило речь идет не о каких-то конкретных значениях переменных, а о свойствах переменных, например при каких y F(y) будет полным квадратом или при каких x F(x)/x< = n, т.е. будет делиться нацело. Это может сбивать с толку.
                                                                        +1

                                                                        Про теорему Матиясевича весьма интересно, как раз читал недавно статью A Computability Proof of Gödel’s First Incompleteness Theorem где показывалось как теорему Гёделя вывести из утверждения о том что любое вычислимое множество соответствует диофантовому уравнению. А также о том что не существует общего алгоритма для определения, есть ли у заданного диофантового уравнения решение (что тоже было доказано Матиясевичем).


                                                                        В последнее время интересуюсь криптографией, и там сейчас «на острие прогресса» конструкции вроде ZK-SNARK и ZK-STARK, где произвольные вычисления (программы) кодируются в виде полиномов (для того чтобы производить криптографические доказательства их свойств). Это позволяет делать безумные вещи, типа краткого (~1 KB) доказательства, что определенное (сколь угодно сложное) вычисление над данными было проделано корректно, не предъявляя самих данных.


                                                                        К сожалению, мне не хватает математического бэкграунда чтобы понять, связано ли это как-то с работами Матиясевича о соответствии между вычислимыми множествами и полиномами, было бы круто если бы кто-нибудь «в теме» мог разъяснить!


                                                                        Вот тут некоторые референсы:


                                                                        1. Quadratic Arithmetic Programs: From Zero To Hero
                                                                        2. vnTinyRAM: Continuing the zkSNARK tutorials
                                                                        3. ZK-SNARKS: Under The Hood
                                                                          0
                                                                          В вопросе получения полиномов я вообще не силен. Но сложилось такое представление, что сам процесс представления множества полиномом, связан с большим количеством доказательств теорем, отражающих свойства объектов этого множества. Т.е. выдвигается гипотеза, о том что среди значений какого-нибудь простенького полинома есть все значения интересующего множества. Если гипотеза доказана, то выдвигаются более конкретные гипотезы, снова доказываются и т.д. пока не получится «исчерпывающее описание».

                                                                          В дистрибутиве python Anaconda есть даже какой-то модуль для автоматизированной проверки и доказательства теорем.

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

                                                                          Однако, я могу и заблуждаться.
                                                                            +2
                                                                            Про представление перечислимого множества в виде полинома можно почитать Ю. В. Матиясевич, «Диофантовы множества». Там автор приводит конструктивное доказательство, алгоритм, как из математического выражения, описывающего перечислимое множество (язык Я5 в терминологии автора), можно получить полином, его описывающий (язык Я0). Я лично целиком весь этот путь не проделывал, но автор пишет
                                                                            Такой „перевод" с Я5 на Я0 требует чисто механической, нетворческой работы и в принципе может быть поручен вычислительной машине.

                                                                            И с виду написано оно очень понятно и здорово, не нужно быть на 100% в теме всех тонкостей.

                                                                            Во всём этом для меня лично особенно круто то, что для доказательства неразрешимости 10 проблемы Гильберта был проложен мост из математики в информатику, чтобы свести проблему в итоге к проблеме остановки. А ещё, имхо, нам очень повезло, что автор разговаривает на одном с нами языке, т.к. мы можем свободно послушать его лекции об этом всём на ютубе в оригинале.
                                                                              0
                                                                              Спасибо за ссылки.
                                                                          +2
                                                                          Автор зря уравнением называет то, что уравнением не является.
                                                                            0
                                                                            Вот тоже сразу глаз резануло.
                                                                            +2
                                                                            Вспомнил школьную историю про зёрна на шахматной доске и думаю Бездна ещё очень долго будет смеяться над попытками вчерашней обезьяны заглянуть в неё.

                                                                            Only users with full accounts can post comments. Log in, please.