Компьютерная математика Weekly

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

8 1/2. после такой разминки без проблем разобрался с тем, с чем не справился в прошлый заход https://t.me/compmathweekly/77 — посчитал коники на гиперповерхности степени 5 в P^4 писать еще раз развернуто про локализацию не буду, приведу только код целиком:

from math import prod
from fractions import Fraction
from itertools import combinations, combinations_with_replacement

w = [0, 1, 4, 9, 16]
ans = 0

for X in combinations(range(5), 3):
    e_base = prod(w[y] - w[x] for x in X for y in range(5) if y not in X)
    for q in combinations_with_replacement(X, 2):
        e = e_base * prod(
            sum(w[i] for i in q) - sum(w[i] for i in p)
            for p in combinations_with_replacement(X, 2) if p != q
        )
        c_top = prod(
            -sum(w[i] for i in p)
            for p in combinations_with_replacement(X, 5)
            if not all(p.count(i) >= q.count(i) for i in X)
        )
        ans += Fraction(c_top, e)

print(ans)

а вот рассказ человека, который только что побил несколько рекордов по упаковке квадратиков в квадрат: https://slightlysupervised.substack.com/p/improving-25-square-packing-upper

8. Q: а можно посчитать количество коник, пересекающих 8 фиксированных прямых, без вычислений в какой-то сложной алгебре? A: да, формула локализации Атьи-Ботта сводит всё просто к сложению нескольких дробей не пытаясь гнаться за максимальной общностью, будем пользоваться такой формой пусть мы хотим посчитать интеграл по многообразию M какого-то выражения от классов Черна — и пусть на M действует окружность с конечным числом неподвижных точек, и все расслоения эквивариантные. формула локализации вычисляет этот интеграл как сумму по этим самым неподвижным точкам вклад неподвижной точки — дробь, которая получается так. слой эквивариантного расслоения в неподвижной точке распадается (как представление тора) в сумму одномерных… ну вот корени Черна заменим на возникающие веса, это будет числитель. а в знаменатель запишем класс Эйлера (т.е. произведение весов) касательного пространства в этой точке например, если мы хотим посчитать ∫h² на P², то можно взять покоординатное действие окружности с весами (a,b,c) и для h=c_1(O(L*)) получить в точке (1:0:0) числитель a² и (помня, что TP^n = Hom(L,L^perp)) знаменатель (a-b)(a-c)… короче, получается https://t.me/compmathweekly/73 в нашей задаче вычисление выглядит похожим образом: неподвижные точки в пространстве коник — это «x[i]x[j]=0 в плоскости x[a]=0» (всего 4×6=24 неподвижные точки), касательное пространство состоит из касательного к базе (его класс Эйлера мы только что считали) и касательного к слою (т.е. тоже касательного к проективному пространству, надо только помнить, что веса на Sym² — попарные суммы весов исходного действия) получается совсем короткая программа:

for a in range(4):
    e_base = prod(w[a]-w[b] for b in range(4) if b != a)
    for i in range(4):
        for j in range(i, 4):
            if a in (i, j): continue
            e = e_base * prod(
                w[i]+w[j]-w[k]-w[l]
                for k in range(4) for l in range(k,4)
                if a not in (k,l) and (k,l) != (i,j)
            )
            ans += Fraction((w[i]+w[j]+2*w[a])**8, e)

и в качестве w достаточно взять почти любые числа (нужно только чтобы никакие знаменатели не обращались в ноль)

вернемся к перечислительной геометрии; сразу продолжить то, что перестало получаться, тяжело, поэтому сначала будет новая (полу)разминка 7. в начале этой серии обсуждалось ( https://t.me/compmathweekly/71 ), сколько прямых в пространстве пересекают 4 фиксированные прямые (общего положения) — теперь посчитаем в таком же духе коники, пересекающие фиксированные 8 прямых (общего положения) в пространстве стандартная схема: есть пространство всех коник, надо пересечь в нем 8 гиперповерхностей, задаваемых условиями «пересекать фиксированную прямую» — и для этого имеет смысл описать «умножение условий» (кольцо когомологий) для этого пространства каждая коника лежит в какой-то плоскости и задается там каким-то уравнением — ну вот всевозможные плоскости образуют P³, а коники в данной плоскости образуют P⁵ (в частности, пространство всех коник 8-мерно и разумно ожидать конечного числа коник именно для 8 прямых) но можно (и нужно) сказать и точнее: если обозначить E двойственное к тавтологическому трехмерное расслоение, то уравнение коники — элемент Sym² E, а буквально пространство коник есть P(Sym² E) когомологии проективизации расслоения порождаются когомологиями базы и еще одним классом t=с₁(O(1)) с единственным соотношением П(t+tₖ)=0, где tₖ — корни Черна этого расслоения в нашем случае когомологии базы, H(P³) — это Z[h]/h⁴, а корни Черна для Sym² E суть суммы корней Черна x_i+x_j (i⩽j) расслоения E то есть чтобы найти соотношение нужно написать prod(t+x[i]+x[j] for i in range(3) for j in range(i,3)) переписать все через элементарные симметрические многочлены от иксов, после чего заменить e₁, e₂, e₃ на классы Черна расслоения E, т.е. на h, h², h³ — Sage легко посчитает, что возникающее соотношение имеет вид t^6 + 4*t^5*h + 10*t^4*h^2 + 20*t^3*h^3 = 0 *** как выражается класс X коник, пересекающих фиксированную прямую, через h (класс всех коник, плоскость которых проходит через фиксированную точку) и t? это класс в H², поэтому X=at+bh, вопрос в том, как найти коэффициенты можно умножить X на h³ — это ограничит задачу на плоскость — и увидеть, что коэффициент при t равен 1 теперь возьмем в пространстве квадрику и пошинкуем ее пучком плоскостей на коники — в ограничении на эту кривую в пространстве коник * h=[pt] (одна плоскость в пучке проходит через точку), * t=0 (уравнение квадрики дает в каждой из плоскостей выбор конкретного уравнение для соответствующей коники — т.е. тривиализацию тавтологогического расслоения на Sym² E), * ну а X=2[pt] (квадрика пересекает прямую в двух точках), то есть b=2 итак, X=t+2h, осталось посчитать¹ в Sage, что в нашем кольце (t+2h)^8 = 92*t^5*h^3 (недлинный код положу в комментарии) ¹ как и раньше, опускаю проверку того, что в общем положении все 92 полученные коники гладкие (простой подсчет параметров), а все пересечения трансверсальны (не знаю, как это проверять, сорри)

краткий апдейт на тему t.me/compmathweekly/141

just for fun на каникулах: purplesyringa.moe/blog/log-is-non-monotonic-in-php-and-lua/ — реализация логарифма иногда оказывается немонотонной функцией (и не по той причине, по которой вы, возможно, подумали)

история про Rowland'а и Sinkhorn limit немного повисла в воздухе — вернемся ненадолго матрица 2×2, у которой суммы по строкам и столбцам единицы, имеет вид [x 1-x\\ 1-x x] чтобы понять, к какой из матриц такого вида мы сойдемся, нужно еще найти инвариант процесса — ну вот он такой соверешнно в духе мат. кружка: произведение чисел на черных клетках делить на произведение чисел на белых, ad/bc — получается уравнение на x, из которого x = √ad/(√ad+√bc) — вот эти квадратные корни и были видны в эксперименте конечно аналогичные инварианты можно писать для 2×2 подматриц матрицы 3×3 — и в итоге на элементы предельной матрицы получаются алгебраические уравнения степени 6 ну на этом история не заканчивается, можно почитать дальше доклад

будем переходить от многоугольника к новому многоугольнику с вершинами в серединах сторон исходного («отображение Бюффона») все вершины при это стремятся к одной точке… но что при этом происходит с формой N-угольника? оказывается, он становится аффинно правильным (это, кстати, достаточно просто доказать); в приземленных терминах: после нескольких итераций он практически становится «параллельником» — (практически) параллельны те же стороны и диагонали, что у правильного N-угольника (для 4-угольников уже после первой итерации получается параллелограмм… ну вот Бюффона можно считать таким обобщением Вариньона) можно посмотреть пример на гифке или попробовать разные многоугольника по ссылке dev.mccme.ru/~merzon/compmath/midpoints.html (услышал про это в начале лекции А.П.Веселова на ЛШСМ-2026 — где дальше обсуждался трехмерный случай, где все сложнее)

во время ЛШСМ на компьютерные развлечения не хватает энергии, так что вот пока вместо моего поста — пост Тао: terrytao.wordpress.com/2026/07/14/visualizing-the-gilbreath-expectation-sequence/

упомянутый в прошлом посте Rowland (относительно) недавно рассказывал, оказывается, на семинаре по экспериментальной математике вот про что возмьем квадратную матрицу неотрицательных чисел. и будем нормировать строки-столбцы: разделим каждую строку на сумму чисел в ней, потом каждый столбец, потом снова каждую строку… к чему это сойдется («Sinkhorn limit»)? вот, например, для матрицы [4 1\\ 2 1] можете сообразить, что это за числа получаются? можно посмотреть на приближенные значения:

import numpy as np
A = np.array([[4,1],[2,1]])
for _ in range(5):
    A = A / A.sum(axis=1, keepdims=True)
    A = A / A.sum(axis=0, keepdims=True)
    print(A)

рассмотрим последовательность a(1) = 7 a(n) = a(n-1)+НОД(n, a(n-1)) Rowland доказал, что каждый раз число увеличивается либо на 1, либо на простое число (но появляются ли так все нечетные простые, неизвестно) коллега Медведь поделился забавным родственником этой последовательности, который (гипотетически) генерирует простые числа-близнецы: https://math.stackexchange.com/q/5142627/152

рассказывал сегодня про треугольник Серпинского — и хотелось показать, как он возникает в «игре в хаос» это такая конструкция: кузнечик стартует в какой-то из точек внутри треугольника, на каждом шаге прыгает в середину отрезка, соединяющего его с одной из вершин (какой именно, выбираем случайно) — тогда через k шагов он будет внутри k-й стадии построения треугольника Серпинского а если запустить много кузнечиков, то треугольник Серпинского постепенно появляется на экране позапускать кузнечиков можно по ссылке dev.mccme.ru/~merzon/compmath/sierpinski.html

возьмем теперь не конкретные многочлены, а что-то более случайное… ну например, будем брать многочлены степени 200 со старшим коэффициентом 1, а остальные к-ты будем выбирать равномерно… ну скажем из отрезка [-10;10] можно попробовать угадать, как будут выглядеть соотвествующие картинки на комплексной плоскости, а потом заглянуть под спойлер см. также: mathoverflow.net/q/182412/1556

возьмем теперь не конкретные многочлены, а что-то более случайное… ну например, будем брать многочлены степени 100 со старшим коэффициентом 1, а остальные к-ты будем выбирать равномерно… ну скажем из отрезка [-10;10] можно попробовать угадать, как будут выгляеть эти многочлены (на комплексной плоскости), а потом заглянуть под спойлер обсуждение (примерно) этого: https://mathoverflow.net/q/182412/1556

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

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

в квадратную коробку какого наименьшего размера можно положить N единичных кругов? если N большое, то известно что примерно мы увидим… или если N какое-нибудь круглое, типа 4 или 9… а если N какое-нибудь дурное, типа 11? как найти оптимум, блуждая по пространству конфигураций? есть два радикально разных подхода: 1) двигаться в случайном направлении, если получилось поставить рекорд — записать его в книжечку; 2) сдвигаться в новую точку только если в ней лучше, чем в старой первый подход не может работать потому что оптимальные конфигурации очень конкретные, случайно туда не попадаешь; второй подход не может работать, потому что есть много локальных экстремумов (жестких конфигураций) и из первого же нам не уйти в simulated annealing эти две идеи смешаны: сначала температура высокая и мы делаем достаточно случайные переходы, потом температура понижается и ухудшающие ситуацию переходы становятся всё менее вероятными… и всё магическим образом работает это оказалось не особо сложно реализовать… но в зависимости от параметров магия либо работает, либо не работает, и надо как-то подбирать их либо наобум (долго и мучительно), либо из опыта, либо из глубокого понимания происходящего… мне, увы, доступен только первый вариант вот, собственно, практически весь код:

def simulated_annealing(N, max_iter, T=0.2, cooling=0.9975):
    centers = np.random.uniform(0, 1, (N, 2))
    best_centers = centers.copy()
    best_R = R = max_radius(centers)
    history = [R]

    for step in range(max_iter):
        i = step%N
        old_pos = centers[i].copy()
        old_dist = point_dist(i, centers)

        step_size = min(T**0.5,0.04)
        centers[i] += np.random.normal(0, step_size, 2)
        centers[i] = np.clip(centers[i], 0.0, 1.0)

        delta = point_dist(i, centers) - old_dist
        if delta > 0 or np.random.random() < np.exp(delta / T):
            R = max_radius(centers)
            if R > best_R:
                best_R = R
                best_centers = centers.copy()
        else:
            centers[i] = old_pos

        T *= cooling
        history.append(R)

    return best_centers, best_R, history

(кто дочитал досюда, может заметить, что реализован не буквально отжиг… но если двигать точки по одной, работает лучше — и даже интуитивно понятно, почему) на наилучшие известные упаковки можно посмотреть на странице erich-friedman.github.io/packing/ — мб кто-то из читателей сможет что-то из рекордов улучшить ;

про сложение точек на кубике и последовательности Сомоса — уточню до конкретного кода для точки P=(3,5) на кривой y²=x³-2 считали координаты точек nP. можно заметить, что знаменатели иксов все время оказывались точными квадратами… ну вот найдем, чьи именно это квадраты:

from fractions import Fraction
import math

N = 20

x, y = x0, y0 = 3, 5
u = [0]*(N+1)
u[1] = x0.denominator
for n in range(2,N+1):
    k = Fraction(y-y0, x-x0) if (x,y) != (x0,y0) \
            else Fraction(3*x0*x0, 2*y0)
    x = k*k-x0-x 
    y = -(k*(x-x0)+y0)
    b = math.isqrt(b2 := x.denominator)
    assert b**2 == b2
    u[n] = b

получается последовательность 1, 10, 171, 7660, 12660211, 22652313570… так вот, можно рядом написать рекурренту типа «Сомос-4» (v[n+2]·v[n-2] = c₁·v[n+1]·v[n-1]+c₂·v[n]² — и рекуррентам именно такого вида удовлетворяют также числа Фибоначчи или количества замощений ацтекского брильянта):

v = [0]*(N+1)
v[:5] = [0, 1, 10, 171, -7660]
c1, c2 = v[2]**2, -v[3],
for n in range(5,N+1):
    b = c1*v[n-1]*v[n-3]+c2*v[n-2]**2
    assert b%v[n-4] == 0
    v[n] = b//v[n-4]

    print(f"n = {n:2d}: {u[n] == v[n] or u[n] == -v[n]} ({len(str(u[n])):3d} digits)")

и убедиться, что всё сходится как введение в последовательности Сомоса в hands-on стиле — был проект на ЛКТГ-2023 и статья А.Устинова в Кванте №№8-9 за 2023 год

несколько пренебрегая принципом «show, don't tell», хотел кратко написать про связи (местами пунктирные) между некоторыми из сюжетов здесь начнем с конца. для рациональной точки P на эллиптической кривой знаменатель nP растет примерно как c^{n²} раньше обсуждались замощения доминошками области на плоскости… и там часто количество растет с той же асимптотикой, c^{площадь} например, для обсуждавшегося ацтекского брильянта ответ — 2^{n(n+1)/2}. этот ответ можно «сконденсировать», доказав рекурренту M(n+1)M(n-1)=2M(n)² бывают разные квадратичные рекурренты в таком духе, в т.ч. упоминавшиеся здесь мельком знаменитые последовательности Сомоса… и, скажем, Сомос-4, действительно, кодирует сложение на эллиптической кривой у этого всего есть игрушечные версии: можно мостить не по настоящему двумерную фигуру, а прямоугольник 2×N (или 3×N и т.п. — такого рода вещи где-то в начале обсуждались), тогда ответы получаются типа Фибоначчи, которые удовлетворяют [не только квадратичным, но и] линейным рекуррентам, имеют более простую асимптотику c^n расставляя на доминошках веса, можно добиться, чтобы комбинаторика считала вещи типа sin(nx) — т.е. nP не на эллиптической кривой, а просто на окружности (кажется не писал про тригонометрию доминошек здесь, только рассказывал на семинаре учителей) хотелось бы конечно это поднять на эллиптический уровень, чтобы nP считали доминошки… кажется по кр мере про Сомоса что-то такое известно… в этом тоже не разобрался разные более конкретные вещи тоже можно пытаться переносить: скажем, F_n | F_{nm} — и вот для последовательности знаменателей nP (скажем, сгенерированных кодом из предыдущего поста конкретно) верно буквально то же… и т.п. незаконченное обсуждение арифметико-геометрического среднего конечно тоже связано со сложением на кубике, AGM реализует «эллиптический логарифм» (это наоборот, как имея точку xP найти x… вещественное или даже комплексное) но пока step into the elliptic realm не выходит, только трогаю пальцами холодную воду