возникла пауза в компьютерной математике, но попробуем постепенно продолжить

начинал уже ( https://news.1rj.ru/str/compmathweekly/45 ) разговор про подсчет количеств решений mod p

базовый пример здесь — плоские кривые: пишем уравнение на x и y с целыми коэффициентами и смотрим как растет количество решений mod p с ростом p

для линейных уравнений ничего интересного не происходит: сколько есть остатков, столько и точек на прямой

рациональная параметризация учит, что и для квадратных уравнений ничего особенно интересного не происходит (если только правильно учесть «точки на бесконечности»)

дальше последовательность выглядит как «один, два, много» — кубические кривые уже скрывают бесконечную сложность… но чтобы с чего-то начать:

если мы смотрим на число N(p) решений y²=x³+ax²+bx+c mod p (и всё гладко, что бы это ни значило… напр., кривая y²=x³ не подходит), то можно ожидать, что правая часть примерно с одинаковой вероятностью квадратичный вычет и квадратичный невычет… и если воспринимать здесь идею про случайность всерьез, то можно ожидать, что |N(p)-p| имеет порядок примерно √p

из (доказанных) гипотез Вейля следует, что |N(p)-p|⩽2√p, в частности, N(p)/p→1… а дальше можно посмотреть на произведение N(p)/p (по p⩽x) — и ожидается, что эта штука растет примерно как log(x)^r, где r — ранг нашей кривой (рациональные точки на кривой образуют коммутативную группу, речь идет про ее ранг)

последнее утверждение — это форма гипотезы BSD (такая… более рабоче-крестьянская форма: без L-функций)

хотел проверить это экспериментально на каких-то примерах, но пока выходит не очень (нужно считать количества точек для больших p, а это лучше делать не в лоб, а быстро считать символ Лежандра… все преодолимо, но пока пусть останется планом)

#видеозаписи #ТяжелыйПонедельник

Открываем новую видеозапись выступления:
Иван Дианов — Алгоритмическая графика: JS для дизайна и искусства

YouTube | VK Видео

1.
сколько коник проходят через 5 фиксированных точек общего положения на плоскости?

с точки зрения перечислительной геометрии в таких задачах полезно думать про пространство всех рассматриваемых объектов и про то, что там высекают условия

в данном случае, коника в P^2 задается 6 коэффициентами ее уравнения, все коники образуют проективное пространство P^5

каждое условие “проходить через точку” — гиперплоскость в этом пространстве

5 гиперплоскостей общего положения в 5-мерном пространстве пересекаются ровно по одной точке

(упражнение к части 1: сколько рациональных кубик проходит через 8 точек общего положения на плоскости?)


2.
продолжим разминку: сколько прямых пересекают 4 фиксированные прямые общего положения в пространстве?

(дальше будут когомологии и характеристические классы, простите… если это пугает, посмотрите вместо этого на Шуховские башни — https://book.etudes.ru/articles/shuhov/ — и поймите ответ на вопрос про прямые без всякий когомологий)

теперь нас интересует пространство PGr(1,3) всевозможных прямых в P^3 (оно же Gr(2,4), пространство 2-мерных линейных подпространств в 4-мерном); каждое условие «пересекаться с данной прямой» задает в этом пространстве гиперповерхность — и мы хотим посчитать число точек пересечения 4 таких гиперповерхностей

в проективном пространстве теорема Безу говорит, что (в хорошей ситуации) достаточно перемножить степени интересующих нас гиперповерхностей

замена этому для более общих пространств — вычисление в кольце когомологий, в данном случае — в кольце H(Gr(2,4))

а классы, которые мы будем там перемножать, — это обычно хар. классы каких-то естественных расслоений, в данном случае — все прямые, пересекающие данную, представляют c_1(E^*), где E тавтологическое расслоение (упражнение для тех, кому понятна формулировка: убедить себя в этом)

в качестве (аддитивного) базиса в H(Gr(n,n+m)) можно взять многочлены Шура, которые нумеруются диаграммами Юнга внутри прямоугольника n×m



то есть в принципе можно пропустить все разговоры про когомологии и т.п. как страшный сон — операционально всё сводится к элементарной алгебре многочленов и/или элементарной комбинаторике диаграмм Юнга

и соответствующие манипуляции вполне можно поручить компьютеру — это дальше и попробуем сделать (на примере сначала этой задачи, а потом подсчета прямых на кубической поверхности… или еще на каком)

3.
итак, симметрические функции в sage-101:

Sym = SymmetricFunctions(QQ)
Sym.inject_shorthands()

теперь можно сказать, например,

s[1].expand(2)

и посмотреть как выглядит многочлен Шура для одной клеточки (как сумма всех переменных — в данном случае, двух: x0+x1)

можно и, наоборот, взять какой-то симметрический многочлен и разложить по многочленам Шура (надо только сначала проговорить небольшое заклинание, потому что в самом кольце симметрических многочленов никаких переменных x0 и x1 нет):

R = PolynomialRing(QQ,'x',2)
R.inject_variables()
s.from_polynomial(x0^2+x1^2)

-s[1, 1] + s[2]

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

s[1]^4

s[1, 1, 1, 1] + 3*s[2, 1, 1] + 2*s[2, 2] + 3*s[3, 1] + s[4]

(ну конкретно это вычисление можно сделать и в уме — если помнить, что умножение на s[1] всевозможными способами добавляет клетку… но не будем отвлекаться)


4.
когомологии Gr(n,n+m) — это фактор кольца симметрических функций по многочленам Шура диаграмм, не помещающихся в прямоугольник n×m

(хотел бы sage попросить делать вычисления прямо в этом факторкольце, но не справился — мб кто-нибудь в комментариях научит?)

базис в H(Gr(n,n+m))— это многочлены Шура от диаграмм, помещающихся в прямоугольник m×n, причем многочлен Шура столбца длины k — это k-й класс Черна двойственного тавтологическому расслоения E* (т.е. виртуальные переменные, от которых все многочлены симметрические, можно отождествлять с корнями Черна для E*), а единственная образующая максимальной степени, многочлен Шура для прямоугольника n×m — это класс точки в старших когомологиях

то есть, например, в когомологиях PGr(1,3)=Gr(2,4) мы посчитали, что c_1(E*)^4 = 2[pt]

с точки зрения геометрии полученная двойка, напомню, — это как раз количество прямых, пересекающих 4 прямые общего положения в пространстве

и на разные другие вычисления с многочленами Шура можно смотреть геометрически в духе Шуберта… скажем, s[1]²=s[1,1]+s[2] — это утверждение о том, что гомологически [прямые, пересекающие две фиксированные]=[прямые в фиксированной плоскости]+[прямые через фиксированную точку] — и геометрически это можно увидеть, если две фиксированные прямые сделать пересекающимися


5.
попробуем что-то немного посерьезнее: посчитаем количество прямых на кубической поверхности в P^3 общего положения

уравнение кубической поверхности дает сечение расслоения Sym^3 E* на том же PGr(1,3); нули этого сечения соответствуют прямым, ограничение на которые нашего уравнения тождественно равно 0, — т.е. в точности прямые, лежащие в нашей поверхности

итак, прямые на (типичной) кубической поверхности представляют класс Эйлера (он же старший класс Черна) расслоения Sym^3 E*

если корни Черна расслоения E* — x0 и x1, то у расслоения Sym^3 E* это 3x0, 2x0+x1, x0+2x1, 3x1; осталось их перемножить и понять, кто получился в терминах образующих нашего кольца — то есть операционально достаточно спросить

s.from_polynomial( 3*x0*(2*x0+x1)*(x0+2*x1)*3*x1 )

и в ответе

81*s[1, 1, 1, 1] - 63*s[2, 1, 1] + 27*s[2, 2] + 18*s[3, 1]

посмотреть на коэффициент при s[2,2] — вот они, 27 прямых

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

аналогичным образом можно посчитать количество прямых на типичной гиперповерхности степени 5 в P^4

s.from_polynomial( 5*x0*(4*x0+x1)*(3*x0+2*x1)*(2*x0+3*x1)*(x0+4*x1)*5*x1 )

15625*s[1, 1, 1, 1, 1, 1] … + 2875*s[3, 3] - …

(но конечно здесь [снова] заметено под ковер, почему мы считаем то, что надо: пересечения трансверсальны и т.п.)

давайте на этот раз что-нибудь более приземленное

знаете ли вы, чему равна сумма

a²/(a-b)(a-c) + b²/(b-c)(b-a) + c²/(c-a)(c-b)?

если никогда этого не делали, то лучше всего перед чтением дальше (или даже вместо него ) взять и упростить выражение

предлагаю поставить реакцию
«ok», если знаете,
«✓», если сделали упражнение


можно дальше менять количество переменных и степень числителя… считать всё руками быстро становится утомительным, но можно воспользоваться компьютером

у sage внутри живет питон и синтаксис функций, циклов и т.п. довольно интуитивный (для знакомых хоть чуть-чуть с питоном) — можно написать, скажем,

def sum1(n,k):
    R = PolynomialRing(QQ, 'x', n+1)
    x = R.gens()
    return sum(
            x[i]^k / prod(x[i] - x[j] for j in range(n+1) if j != i)
            for i in range(n+1)
        )

и дальше смотреть на разные значения, формулировать гипотезы и доказывать их


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

P.S.
на самом деле, этот сюжет связан из предыдущим: например, самое верхнее выражение — это подсчет прямых через две точки плоскости при помощи формулы локализации Атьи-Ботта на P²

5 лет назад был отличный математический флэшмоб #12equations — в т.ч. как раз в этот день пять лет назад писал про тангенс

…Очень люблю цитату из интервью Гельфанда, «я считал, что есть две математики — алгебраическая и геометрическая, и что геометрическая математика принципиально “трансцендентна” для алгебраической. (…) Когда я обнаружил, что синус можно записать алгебраически в виде ряда, барьер обрушился, математика стала единой».

В отличие от синуса и косинуса ряд для тангенса на первый взгляд выглядит хаотично:
x+x^3/3+2x^5/15+17x^7/315+…
Оказывается, за этим хаосом скрывается отличная комбинаторика…

сейчас описание комбинаторики опущу, а вместо этого приведу код, при помощи которого на эти коэффициенты можно посмотреть (потому что в лоб на бумажке это делать утомительно):

x = var('x')
taylor = tan(x).taylor(x,0,21)
E = [ taylor.coefficient(x,n)*factorial(n) for n in range(1,22,2) ]
print(E)

если не знаете ответа, то можно подумать про то, как на эти целые числа написать рекурренту, например (тут возможны разные ответы!)

или вот такой листок для курса Е.Смирнова про этот сюжет делал: https://dev.mccme.ru/~merzon/ium-combi/combi20-05-bernoulli.pdf

в продолжение, если угодно, темы про L-системы ( https://news.1rj.ru/str/compmathweekly/25 & https://news.1rj.ru/str/compmathweekly/33 ) —

генерировал картинки, где прямоугольники случайным образом делятся на два прямоугольника (и потом покрашены в соответствии с отношением сторон)

(в качестве интермедии — никакой математики, просто картинки)

геометрия пи в экселе

выше обсуждались разные способы вычисления π, в т.ч. 1-1/3+1/5-1/7+… = π/4 ( https://news.1rj.ru/str/compmathweekly/42 )

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

π — это площадь круга радиуса 1, поэтому среди точек квадрата 0⩽X,Y⩽1 доля точек, попадающих в (четвертинку) круга радиуса 1 с центром в начале координат, равна π/4

теперь можно вычислять π геометрически хоть в экселе — по методу Монте-Карло: берем 100500 строк, в каждой пишем по паре случайных чисел X и Y, считаем в скольких строках X²+Y²⩽1, полученную долю умножаем на 4

конечно, способ не особо эффективный — для 1000 строк получается приближение уровня π≈3,1

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

P.S.
сумма из начала поста на самом деле получается, если думать про те же площади — но брать не случайные точки, а все точки достаточно мелкой сетки… про это есть отличный ролик 3Blue1Brown, если кто не видел, https://youtu.be/NaL_Cb42WyY

6.
попробуем еще чуть-чуть продвинуться в подсчетах кривых

в прошлый раз ( https://news.1rj.ru/str/compmathweekly/72 ) посчитали количество прямых на гиперповерхности степени 5 в P^4

теперь попробуем посчитать на ней же коники

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

каждая коника в P^4 лежит в какой-то плоскости и высекается там квадратным уравнением... то есть пространство C всех коник — это P(Sym^2 E), где E — двойственное¹ тавтологическому трехмерное расслоение на Gr(3,5)=PGr(2,4)

¹ прошу прощения за смену обозначений, но надоело таскать кучу звездочек

уравнение f нашей квинтики задает сечение расслоения Sym^5 E, а условие «данная коника лежит на квинтике» значит, что f [в ограничении на плоскость коники] = (уравнение коники)⋅(что-то кубическое) — т.е. нас интересуют точки, для которых сечение попадает в подрасслоение (Sym^3 E)⊗O(-1) — другими словами, нас интересует старший класс Черна фактора F := Sym^5 E / (Sym^3 E)(-1)

(проверка: dim C=11, т.к. оно расслаивается над 6-мерным грассманианом с 5-мерным слоем; dim F=7⋅6/2-5⋅4/2=11 — размерности сходятся)

осталось реализовать компьютерное вычисление интеграла c_11(F) по C

(
прямолинейно-алгебраическое вычисление вот какое:

пусть x0, x1, x2 — корни Черна E, тогда у Sym^n E корни Черна — это i⋅x0+j⋅x1+k⋅x2 | i+j+k=n

H(C) = H(Gr)[t] / prod(t-x), где t — класс Черна O(1), а произведение берется по корням Ч. для Sym^2 E

нам нужно взять произведение 1+x по корням Ч. для Sym^5 E, разделить на произведение 1+x-t по корням Ч. для Sym^3 E, разложить t в степени 6 и выше по соотношению выше, найти коэффициент при s[2,2,2]⋅t^5

вроде как раз задача для компутера — руками это убьешься считать — но пока не закодил… надеюсь, дальше либо справлюсь, либо посчитаю все-таки по локализации
)

слушал мини-курс Батырева про дискриминант, где рассказывалось в т.ч. про такое

как выглядит дискриминант многочлена a_0+a_1x+…+a_nx^n?

уже для n=4 ответ sage выглядит несколько устрашающе:

n = 4

R = PolynomialRing(QQ, 'a', n+1)
a = R.gens()
S.<x> = PolynomialRing(R)
f = sum(a[i]*x^i for i in range(n+1))
D = f.discriminant()

print(D)

a1^2*a2^2*a3^2 - 4*a0*a2^3*a3^2 - 4*a1^3*a3^3 + 18*a0*a1*a2*a3^3 - 27*a0^2*a3^4 - 4*a1^2*a2^3*a4 + 16*a0*a2^4*a4 + 18*a1^3*a2*a3*a4 - 80*a0*a1*a2^2*a3*a4 - 6*a0*a1^2*a3^2*a4 + 144*a0^2*a2*a3^2*a4 - 27*a1^4*a4^2 + 144*a0*a1^2*a2*a4^2 - 128*a0^2*a2^2*a4^2 - 192*a0^2*a1*a3*a4^2 + 256*a0^3*a4^3

но кое-что интересное можно увидеть, если этот многочлен нарисовать — а точнее нарисовать его многогранник Ньютона (для каждого входящего в дискриминант монома П a_i^{k_i} отмечаем точку с координатами (…,k_i,…) и берем выпуклую оболочку)

буквально как написано уже для n=4 будет что-то в 5-мерном пространстве, но это иллюзия: ∑ k_i = const и ∑ i k_i = const, то есть реально всё лежит в обычном 3-мерном пространстве

support = [m.exponents()[0] for m in D.monomials()]

M = matrix(QQ, n+1, n-1)
for i in range(n-1):
    M[i,i], M[i+1,i], M[i+2,i] = 1, -2 ,1
def exponent_map(x):
    v = vector(x) - vector([0]+[2]*(n - 1)+[0])
    return tuple(M.solve_right(v))

projected_support_b = [exponent_map(x) for x in support]
poly_b = Polyhedron(vertices=projected_support_b)
poly_b.plot()

вот на картинке видно, что получается такой кубоид — и для любой степени, говорят, получается кубоид (соответствующей размерности)

на этом история не заканчивается — n! копий такого кубоида складываются в пермутаэдр; если брать сумму мономов, попавшие в одну грань кубоида, то получившийся многочлен хорошо раскладывается на множители… хотел бы это всё компьютерно увидеть

конспект первой лекции есть по ссылке mccme.ru/dubna/2025/notes/batyrev-notes.pdf

если уж зашла речь про дискриминант — два слова про то, как его нарисовать

любое уравнение степени 4 нетрудно привести к виду x^4+px^2+qx+r=0

у каких из уравнений такого вида есть кратные корни?

можно посчитать в sage (или даже на бумажке) дискриминант такого уравнения… тут слагаемых поменьше, но всё равно выглядит страшновато:

-4*p^3*q^2 + 16*p^4*r - 27*q^4 + 144*p*q^2*r - 128*p^2*r^2 + 256*r^3

если в лоб спросить ту же геогебру нарисовать, где в трехмерном пространстве такое выражение обращается в 0, то ничего не получится — лучше действовать не настолько в лоб

можно начать с совсем вырожденных уравнений — у которых есть корень кратности 3: если коэффициент при x^3 нулевой, то сумма всех корней 0, то есть корни должны быть (t,t,t,-3t), а значит, (p,q,r)=(-6t^2,8t^3,-3t^4) — такую кривую нарисовать несложно

а произвольное уравнение с кратным корнем t (и нулевым коэффициентом при x^3) можно записать в виде (x-t)²(x²+2tx+s)

ну уже не раскрывая скобки видно, что выражения для (p,q,r) будут линейными по s, правда? то есть наша поверхность линейчатая (состоит из прямых — а именно, как можно понять, из касательных к описанной выше кривой!)

а если скобки все-таки раскрыть, то с получающимся параметрическим заданием поверхности справится любая геогебра — получается замечательная поверхность “ласточкин хвост”, вот можно на это посмотреть: www.geogebra.org/m/ftjewyex

больше разговоров и много красивых картинок есть на сайте Математических этюдов: etudes.ru/etudes/swallow-tail/

возьмем какой-нибудь многочлен (от одной переменной с натуральными коэффициентами) и возведем в большую степень

ну будет непонятное море мономов с большими коэффициентами… но тут уже обсужалось, что полезно сделать в таком случае: построить график

что мы увидим? почему?

под спойлером скрыт пример картинки (конкретно — list_plot(((2+7*x+x^4+5*x^5)^57).coefficients(),plotjoined=True) в sage)

(такой иллюстрацией ЦПТ поделился Александр Ч. в комментариях у «Кроссворда Тьюринга»)

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

а вот картинка для list_plot(((1+3*x-x^2+x^3)^100).coefficients(),plotjoined=True)

почему «горбов» в данном случае два (рядом с x=N и x=2N, с одинаковым порядком величины)? что будет происходить для произвольного многочлена? другими словами, какой аналог ЦПТ для ситуации, когда разрешены не только неотрицательные (а произвольные… пускай даже комплексные) вероятности?

(думал, разберусь и напишу… это не сложилось, но мб кто-то в комментариях объяснит — upd: indeed, см. комментарии)

треугольник Серпинского как график функции

Никита Медведь рассказал забавное

рассмотрим для k-битовых чисел функцию, переводящее N в N&Nrev, и нарисуем её график — оказывается, он выглядит как треугольник Серпинского

читателям предлагается этот эффект объяснить

===

Nrev — строка из нулей и единиц, прочитанная в обратном порядке, & — побитовое И

источник: https://www.reddit.com/r/askmath/comments/1mvxrjn/if_you_reverse_the_bits_of_a_number_n_and_then/

для желающих развлекаться — код оставлю в комментариях

чему равен НОД(n^5+5,(n+1)^5+5)? первое впечатление, возможно, что это глупый вопрос типа того, чему равен НОД(n,n+1)… и действительно, для небольших n легко проверить, что всё время получается единица, но ———

желающим предлагается разобраться

в комментарии положу эксель-табличку для экспериментов (на скрытой под спойлером картинке — что она дает для НОД(n^3+3,(n+1)^3+3) при n=1..150), но буквально для исходной задачи в экселе ничего кроме единиц не увидишь

( комментарий к https://news.1rj.ru/str/compmathweekly/84 )

пусть НОД(f(n),g(n))>1 — и, соответственно, делится на какое-то простое p

это значит, что по модулю p у многочленов f и g есть общий корень (а именно, n), то есть Res(f,g) = 0 mod p

в данном случае результант равен¹ простому числу p=1968751, поэтому если НОД не 1, то он равен этому числу (и это уже намекает, что пример вряд ли найдется среди небольших n… а, скажем, для n^17+9 и (n+1)^17+9 получается простое число порядка 10^50)

остается найти² корни пятой степени из -5 по этому модулю (96502, 533360, 533361, 1066696, 1707583) и поискать среди них³ отличающиеся на 1

окончательно получаем, что НОД равен 1968751 для n=533360+1968751m (и 1 иначе)

(можно обойтись и без слова 'результант': шагами a la алгоритм Евклида (f,g)→(af+bg,f) нетрудно получить, что в идеале (f,g) лежит число (паразитический множитель)×1968751 — см. код в комментариях — и плясать от этого)

в комментариях М.Алексеев поделился еще ссылкой arxiv.org/abs/1608.07936 (опубликовано в AMM) — там объясняется, что если результант свободен от квадратов, то все его делители возникают как значения НОДа

¹ если хочется посчитать это в sage, то синтаксис не совсем очевидный: f.resultant(g,x)

² R.<x> = PolynomialRing(GF(1968751)); (x^5-5).factor()

³ что такие найдутся — понятно, кстати, заранее: p=5k+1, поэтому если хотя бы один корень лежит в поле, то лежат и остальные (и из обращения в 0 результанта какие-то два отличаются на 1); а если x и x+1 — корни в расширении, то из Галуа-инвариантности прибавлять единицу можно к любому корню и сразу противоречие

склеим стороны 2n-угольника попарно 'с сохранением ориентации' (без перекрутки) — какие поверхности могут при этом получиться?

если у квадрата склеивать соседние стороны, то (топологически) получится сфера, если противоположные — тор

если не думали никогда, как склеить подобным образом 'сферу с 2 ручками' (крендель), то полезно, конечно, задуматься



но еще можно задать вопрос про количества: сколькими способами можно склеить из 2n-угольника сферу с g ручками?

для g=0 после склейки граница превратится в плоское дерево (и наоброт, если обойти вокруг дерева, то можно увидеть границу многоугольника, приклееную к этому дерево — по две стороны у каждого ребра)

то есть в роде 0 получаются милые многим числа Каталана — а интересно, что происходит дальше

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



в следующий раз напишу, думаю, как это перебрать на компутере (ну… для небольших n — всего склеек (2n-1)!!, так что особо далеко так не уйдешь)

давно уже хотел это сделать, а тут нашелся повод

пусть мы как-то склеили стороны многоугольники (попарно, с сохранением ориентации) — как понять, что за поверхность получается?

самый простой способ (по крайней мере, для лишенного геометрического воображения компьютера) — посчитать Эйлерову характеристику: с одной стороны, она равна 2-2g, а с другой стороны, из 2n-угольника получается карта с 1 гранью, n ребрами и… надо только как-то посчитать количество вершин

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

вообще книжка Звонкина и Ландо учит, что про ленточный (вложенный в поверхность) граф бывает удобно думать как про тройку перестановок… но я отвлекся, а пора переходить к реализации


перебор инволюций реализовал в том же духе, как перебирал в https://news.1rj.ru/str/compmathweekly/9 разбиения на доминошки:

def involutions(n,state=[]):
    if state == []:
        state = [-1]*(2*n)
    for i in range(2*n):
        if state[i] == -1:
            for j in range(i+1,2*n):
                if state[j] == -1:
                    newst = state.copy()
                    newst[i], newst[j] = j, i
                    yield from involutions(n,newst)
            return
    yield state

осталось добавить вычисление рода через подсчет количества циклов:

def genus(perm):
    N = len(perm)
    state = [(perm[i]+1) % N for i in range(N)]
    v = 0 
    for i in range(N):
        j = state[i]
        if j != -1:
            v += 1
            while j != i:
                state[j], j = -1, state[j]
    return (N//2-v+1)//2
    # v-n+1 = 2-2g => g = (n-v+1)/2

for n in range(1,6+1):
    counts = [0]*(n//2+1)
    for perm in involutions(n):
        counts[genus(perm)] += 1
    print(f"n={n}:",*counts)

n=1: 1
n=2: 2 1
n=3: 5 10
n=4: 14 70 21
n=5: 42 420 483
n=6: 132 2310 6468 1485

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

Intermission

Разгребал недавно завал на гугл-диске, нашел прикольное. Рубрика "эксперименты, упаси господи", релевантное message passingу в графовых нейронках.

Гугл-таблицы - идеальный инструмент для демонстрации дискретной диффузии с граничными условиями типа Дирихле.

0. Разрешаем в настройках таблицы циклические вычисления, выкручиваем число итераций на дофига, точность на эпсилон.
1. Рисуем из клеточек область.
2. На границе ставим вещественные чиселки.
3. Во внутренних клетках области ставим везде формулу =среднее арифметическое четырех соседей (легко задать в одной клетке и автоматически скопипастить).
4. Чтобы было красиво, делаем внутри области conditional formatting с градиентной расцветкой.

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

Можете вот скопировать, там еще на прогрев тора можно позалипать

Но что если заполнять таблицу каким-нибудь более интересным типом данных? Если в качестве типа данных выбрать фиксированную решетку, то получится наука про лапласиан Тарского. А если категорию, обогащенную над кванталями (свят-свят-свят), то будет лапласиан Ловера.

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

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

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

знаете ли вы, как выглядит график синуса?

если да, то подумайте, какую картинку должен выдать код ниже… а потом посмотрите под спойлером на реальный результат

import numpy as np
import matplotlib.pyplot as plt

x = np.arange(-10, 10, 0.001)
y = np.sin(314*x)

plt.plot(x,y, marker='.', linestyle='none')
plt.show()

// из статьи П.Панова «Как выглядит график синуса?» в Кванте №3 за 2020 год (via С.Дориченко); см. также статью Е.Бакаева «Еще раз о графике синуса» в №4