А ещё j-инвариант оказывается связан с группой-Монстром, самой большой из спорадических (т.е. "не включённых в серии") простых групп. Например, наименьшая размерность, в которой Монстр умеет действовать нетривиальными линейными преобразованиями (размерность наименьшего нетривиального представления) — это 196883. Если сравнить с рядом для j-инварианта, то видно, что от коэффициента при q это отличается на 1. И опять-таки, "таких совпадений не бывает" — но если одно это совпадение кажется недостаточно убедительным, то есть ещё простое соотношение между следующей размерностью и коэффициентом при q^2 у j-инварианта. А ещё размерность представления — это след тождественного преобразования в ней, а можно посмотреть, какие следы будут у действий других элементов, и обнаружить там сходство с некоторыми аналогами j-инварианта...

И всё это — Monstrous Moonshine; вот кусочек из статьи Конвея и Нортона, "Monstrous Moonshine" (Bulletin of the London Mathematical Society, 11:3 (1979), pp. 308--339)

Давайте я закончу этот рассказ ссылкой на посвящённое Monstrous Moonshine (более сложное!) видео Борчердса — https://youtu.be/5Mg25JK31wE?t=1433 — и покажу ещё один кадр из него.

И на этом эту нашу "прогулку", начавшуюся со скатерти Улама и на которой мы "прошли" через многочлен Эйлера n^2+n+41, константу Рамануджана exp(π\sqrt{163}), разложение на простые в кольце целых O(\sqrt{-163}), через j-инвариант, через ряды Эйзенштейна E_{2k}, и где возникли группа-Монстр и Monstrous Moonshine, — так вот, на этом нашу сегодняшнюю прогулку, кажется, можно завершить.

В прошлый раз мы прошли по одной тропинке, начинающейся с этого вопроса; а в этот раз давайте пройдём по другой, начинающейся со слов "простые числа" и "значения многочлена".

Не-постоянный многочлен одной переменной, как мы видели, не может принимать в целых точках только простые значения. То же самое правда для многочлена нескольких переменных — иначе можно просто выбрать какое-нибудь направление и рассмотреть P(n,n,n) или P(n,2n,3n), и т. д. — сведя эту невозможность к уже доказанной невозможности для многочлена одной переменной.

Ну или можно перенести одномерное доказательство: сказать, что если для многочлена P с целыми коэффициентами выполнено
P(n_1,...,n_k)=p,
то для любых a_1,...,a_k значение
P(n_1+a_1 p,...,n_k+ a_k p) делится на p,
и почти ни при каких a_j простым поэтому быть не может.

Но — если нас интересуют простые числа, то можно автоматически отбрасывать неположительные значения. Для многочленов одной переменной тогда уже можно получить больше одного простого значения: 17-10*n^2 принимает положительные значения 17 и 7 — и все положительные значения простые. Но вот все простые числа (и даже просто бесконечное их число) получить так, чтобы все положительные значения были простыми, у многочлена одной переменной не получится.

А что, если переменных много? Оказывается, тогда такой многочлен существует!

И вот на картинке выше явный пример такого многочлена — которому посвящена статья James P. Jones, Daihachiro Sato, Hideo Wada and Douglas Wiens, "Diophantine Representation of the Set of Prime Numbers", The American Mathematical Monthly, 83 :6 (1976), pp. 449-464 ; https://www.tandfonline.com/doi/abs/10.1080/00029890.1976.11994142

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

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

Да — можно смотреть значения многочленов в точках с целыми координатами, а можно в точках с неотрицательными целыми. И хотя для конкретного многочлена это могут быть разные множества — на то, какие множества так вообще получается представить, этот выбор не влияет: если искомое множество X уже представлено как множество положительных значений P на Z^n, то оно же будет множеством положительных значений Q на (Z_+)^n, где
Q(a_1,b_1,...,a_n,b_n) = P(a_1-b_1,...,a_n-b_n).
И наоборот, если искомое множество X уже представлено как множество положительных значений P на (Z_+)^n, то оно же будет множеством положителных значений Q на Z^4n, где
Q(a_1,b_1,c_1,d_1,...,a_n,b_n,c_n,d_n) =
P(a_1^2+b_1^2+c_1^2+d_1^2,...,a_n^2+b_n^2+c_n^2+d_n^2).
Так что я дальше буду считать, что нас интересуют значения на Z_+^n.

Например, множество составных чисел диофантово, и это совсем просто увидеть: достаточно взять
P(a,b)=(a+2)(b+2).
Как раз множество положительных значений P на Z_+^2 все составные числа и даст.
Но — а будет ли диофантовым, например, множество совершенных чисел? А множество простых делителей чисел вида 2^{2^n}+1 ?

Теорема, получающаяся из объединения работ Мартина Дэвиса, Юрия Владимировича Матиясевича, Хилари Патнема и Джулии Робинсон, утверждает, что перечислимость — единственное(!) необходимое условие:

Теорема [M. Davis, Ю. В. Матиясевич, H. Putnam, J. Robinson]
Любое перечислимое множество диофантово. Более того, порождающий его многочлен P может быть построен по алгоритму перечисления алгоритмическим образом.

Всё это восходит к десятой проблеме Гильберта:
Пусть дано полиномиальное уравнение от нескольких переменных с целыми коэффициентами. Проверить алгоритмически, есть ли у него решения в целых числах.

(На картинке выше — соответствующий абзац из книги "Проблемы Гильберта", издания 1969 года)

Если бы такой способ проверки существовал — например, его применение позволяло бы для любого фиксированного n>2 доказать теорему Ферма (потому что это вопрос о разрешимости полиномиального уравнения x^n+y^n-z^n=0). Было бы возможно за конечное время (и без дополнительных идей) как-то проверять, представимо ли число в виде суммы трёх кубов целых чисел (которые могут быть и отрицательными, так что это не конечная проверка), например, представимы ли 33 (https://www.quantamagazine.org/sum-of-three-cubes-problem-solved-for-stubborn-number-33-20190326 , https://people.maths.bris.ac.uk/~maarb/papers/cubesv1.pdf ) или 42 (https://www.youtube.com/watch?v=ASoz_NuIvP0 ).
Позволять проверить существование решения в натуральных числах у уравнения
x/(y+z) + y/(z+x) + z/(x+y) = 4
(если вы не видели, то это совершенно прекрасная история — см. https://news.1rj.ru/str/cme_channel/198 + https://habr.com/ru/post/335248/ + https://www.quora.com/How-do-you-find-the-integer-solutions-to-frac-x-y+z-+-frac-y-z+x-+-frac-z-x+y-4/answer/Alon-Amit?share=1 ).
И так далее.

Так вот — теорема Дэвиса, Матиясевича, Патнема и Робинсон даёт отрицательное решение проблемы Гильберта — утверждая, что такого алгоритма в принципе существовать не может.

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

Ну и прежде, чем обсуждать, почему это так, давайте ещё чуть-чуть посмотрим на эту формулу. И заметим, что эта формула для простых чисел... для удобства пользователя разложена на множители!

Но если присмотреться, то видно, что вторая скобка это 1 минус сумма квадратов. Поэтому, если значение P положительное, то вторая скобка должна быть равна 1, а каждый квадрат внутри неё должен обращаться в ноль.
Поэтому эту теорему можно переформулировать так: число k+2 простое тогда и только тогда, когда существуют (все остальные переменные), для которых выполняется (система полиномиальных уравнений):

Поэтому более правильно определять диофантовость так: подмножество A в Z_+^k называется диофантовым, если существует многочлен P(a_1,...,a_k,x_1,...,x_n), такой, что
(a_1,...,a_k) из A <=> существуют (x_1,...,x_n) из Z_+^n, для которых
P(a_1,...,a_k,x_1,...,x_n)=0.

(а систему из нескольких диофантовых уравнений можно свернуть в одно взятием суммы их квадратов)

Ну и — на идейном уровне теперь можно понять, как именно должен работать тот порождающий простые числа многочлен: остальные переменные это "сертификат простоты" для искомого k+2 (спасибо А. Горденко за рисунок!).

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

Для начала вообще представим себе, что мы имеем право использовать ещё операцию "факториал". Как тогда можно задать простоту числа p?
Во-первых, нужно попросить, чтобы p было не меньше 2. Ну, тут мы уже видели, как это сделать: одно из уравнений системы будет
p=k+2.
А как проверить, что p не делится ни на что, кроме 1 и себя? Цикл использовать нельзя — но можно вместо него воспользоваться факториалом. А именно — давайте посмотрим на (p-1)! ; число p простое тогда и только тогда, когда оно взаимно просто с (p-1)!, а это проверяется алгоритмом Евклида:
a*(p-1)!-b*p=1.
На самом деле, теорема Валлиса утверждает, что простота p равносильна сравнимости (p-1)! с (-1) по модулю p, так что одну переменную можно сэкономить, и написать просто
(p-1)!+1-b*p=0.

И пара (k,b) тут — "сертификат простоты" числа p, который есть для всех простых p и только для них.

А как быть, если наш бюрократ не понимает факториалы? Нужно "соотношение факториальности" как-нибудь выразить:
p=k+2
c+1-b*p=0
//а тут какие-нибудь уравнения, задающие c=(p-1)! //

А через что мы можем факториал выразить, где он появляется? Первое, что приходит в голову — биномиальные коэффициенты. И действительно, если нам нужно r!, а число M очень большое, то посмотрим на
C_M^r = M(M-1)...(M-r+1) / r!