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

несколько пренебрегая принципом «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 i