чему равен НОД(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

еще немного повозимся с тождествами — следующая серия начинается с того, что

(a+b)²/(a-c)(b-c)+(b+c)²/(b-a)(c-a)+(c+a)²/(c-b)(a-b) = 1

дальше

(a+b)⁴/(a-c)(b-c)(a-d)(b-d) + … = 2

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

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

for n in range(2,6+1): print(n,sum2(n))

понятно ли, что за последовательность возникает? можете ли это доказать?

(бонус для любителей геометрии: на самом деле, sum2(2) считает количество прямых через 2 точки на плоскости, sum2(3) — через 4 прямые общего в положения в пространстве… и так далее)

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

как проверить формулу на картинке?

самая понятная формула, выражающая объем тетраэдра через его ребра, дается определителем Кэли–Менгера:

CM = matrix([
    [0,    1,    1,    1,    1],
    [1,    0, U**2, V**2, w**2],
    [1, U**2,    0, W**2, v**2],
    [1, V**2, W**2,    0, u**2],
    [1, w**2, v**2, u**2,   0 ]
])
V2_CM = det(CM)/288

для полиномиальности здесь сразу вычисляется не объем, а его квадрат… но формуле от Маркелова и этого недостаточно, так как в определение «переменных третьего поколения» (a, b, c, d) через «переменные второго поколения» входят квадратные корни

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

X, x = (w-U+v)*(U+v+w), (U-v+w)*(v-w+U)
Y, y = (u-V+w)*(V+w+u), (V-w+u)*(w-u+V)
Z, z = (v-W+u)*(W+u+v), (W-u+v)*(u-v+W)

a2   = x*Y*Z
b2   = y*Z*X
c2   = z*X*Y
d2   = x*y*z
abcd = X*Y*Z*x*y*z 

num2 = (
    2*(a2*b2+a2*c2+a2*d2+b2*c2+b2*d2+c2*d2)
    - (a2**2+b2**2+c2**2+d2**2)
    + 8*abcd
    )
V2_markelov = num2/(192*u*v*w)**2

после этих ухищрений V2_CM - V2_markelov.expand() действительно дает ноль



но вопрос, что всё это значит — можно ли выражениям типа b+c+d-a придать какой-то геометрический смысл, скажем, как это происходит в формуле Герона — остается

мб кто-то в комментариях научит

контекст для предыдущего — такого рода как выше объяснение (неполное, текст на картинке взят из книги Блинкова «Учимся на чужих ошибках») формулы Герона

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

например, в формуле для площади нет сомножителя abc — разве площадь не обращается в ноль, когда одна из сторон становится нулевой? а вот, у прямоугольного треугольника с катетами 1 и i площадь ненулевая, но гипотенуза имеет нулевую длину

что хуже, длина отрезка в этом комплексном мире вообще не определена (чему равна длина отрезка от -i/2 до +i/2: +i или -i?), определен только ее квадрат (то же можно сказать и про саму площадь, кстати)

похожая вещь происходит с формулой для объема тетраэдра — казалось бы, если для площадей граней тетраэдра выполняется равенство S1=S2+S3+S4, то он вырождается, так что формула для объема должна раскладываться на кучу множителей… а в реальности определитель Кэли-Менгера представляет собой неприводимый многочлен!

но всё-таки чего-то в духе рассуждения на картинке для объема тетраэдра хотелось бы… и в этом смысле формула им. Маркелова привлекает наличием факторизации

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

в такой “нумерологии” нередко помогает обращать внимание на делимости

вот например если посмотреть на первую колонку, то бросается в глаза, что 14 и 42 делятся на 7, 132 и 429 на 11… раз у соседних чисел есть большой общий делитель, можно попробоват посмотреть на их частные

получаем 1, 2, 2 1/2, 2 4/5, 3, 3 1/7, 3 1/4, 3 1/3, 3 2/5, 3 5/11, 3 1/2… — видно, что числа не очень далеки от целых, а именно становятся целыми при умножении на n+1 (тут тоже особенно помогает обратить внимания на числа типа 7, 11)

если на n+1 домножить, то получится… ну сами попробуйте — мб со школьниками — после этого легко придумать гипотезу про формулу

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

а можно посмотреть по-другому: когда в колонках рядом стоят числа 5 и 10, 14 и 70, 42 и 420, 132 и 2310, то естественно попробовать одно на другое поделить — и если это сделать (и еще умножить на 2 для целочисленности), получается 1, 4, 10, 20, 35, 56… (думаю, и без спойлера понятно, что это ; )


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

1001 = 7.11.13, а значит, 225225 = 15².1001 = 3.5.7.11.13.15 недалеко ушло от двойного факториала… как и, например, 21… в общем, тоже закономерность нетрудно распознать


если замечаете в такой таблице что-то еще — пишите

вчера на уроке хотел быстренько показать как выглядят слагаемые в det(AB) по сравнению с det(A)det(B)

но не смог заставить sage раскрыть скобки не сокращая одинаковые члены

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

from itertools import permutations
from functools import reduce

def sgn(perm):
    inv = sum(perm[i] > perm[j] for i in range(len(perm)) for j in range(i+1, len(perm)))
    return -1 if inv % 2 else 1

def mult_terms(A, B):
    for As, Ams in A:
        for Bs, Bms in B:
            yield (As*Bs,Ams+Bms)

def mtrx(label, n):
    return [ [ [ (1, [f"{label}{i+1}{j+1}"]) ] for j in range(n) ] for i in range(n) ]

def mtrxAB(l1,l2, n):
    return [ [ [ (1, [f"{l1}{i+1}{s+1}", f"{l2}{s+1}{j+1}"]) for s in range(n) ] for j in range(n) ] for i in range(n) ]

def det_terms(mtrx):
    n = len(mtrx)
    for sigma in permutations(range(n)):
        for inner_sign, factors in reduce(mult_terms, [ mtrx[i][sigma[i]] for i in range(n) ]):
            yield (sgn(sigma)*inner_sign, factors)

def print_terms(terms):
    for s, ms in terms:
        print(f"{'+' if s>0 else '-'} {'.'.join(sorted(ms))}")

N = 3
detA = list(det_terms(mtrx("a", N)))
detB = list(det_terms(mtrx("b", N)))
print_terms(mult_terms(detA, detB))
print("---")
print_terms(det_terms(mtrxAB("a","b", N)))

можно запустить — и посмотреть, что как с чем сокращается

***

понравилось, что вот все эти определения «многочлен — это формальная сумма мономов…» и т.п. здесь реально работают

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

class Monomial:
    def __init__(self, vars, sgn=1):
        self.vars = tuple(vars)
        self.sgn = sgn
    def __mul__(self, other):
        return Monomial(self.vars + other.vars,self.sgn * other.sgn)
    def __repr__(self):
        return f"{'-+'[self.sgn > 0]} {'.'.join(sorted(map(repr,self.vars))) or '1'}"
    def __eq__(self, other):
        return repr(self) == repr(other)

у такого умножения мономов есть нейтральный элемент и оно (операционально) коммутативно

> print(Monomial(("y",))*Monomial(("x",))*Monomial() == Monomial(("x","y")))
True

тут занятно, что хотя изначальная идея была класть в vars набор строк (имен переменных) — в коде от этого осталось мало следов, можно пользоваться и любыми другими типами, print(Monomial((2,1))) работает без проблем

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

теорема Виета говорит, что Monomials<ComplexNumbers> (буду дальше писать тип vars в угловых скобках; и давайте считать, что разрешен только sgn=1) — это по сути то же, что упорядоченные наборы чисел (т.е. чтобы это увидеть, можно попросить repr печатать значения элементарных симметических многочленов от vars)

любителям геометрии приятнее смотреть не на ℂ, а на ℂ с добавленной точкой '∞' — и примерно то же рассуждение говорит, что Monomials от такого образования суть точки комплексных проективных пространств

если еще отождествить Monomial(0) с нейтральным элементом Monomial(), то все эти проективные пространства склеятся в одно большое красивое ℂP∞

в ту же игру можно играть не только с ℂP¹ aka S², но и с другими топологическими пространствами — если в качестве меток разрешить точки топологического пространства X (и одну из точек объявить нейтральным элементом), то получается определение групп гомологий без всяких комплексов и т.п.: просто H_n(X) = π_n ( Monomials<X> )

называется теорема Дольда–Тома

упражнение для любителей геометрии: разобраться, как выглядит пространство Monomials<RP²>

смотрел видео ниже

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

попробовать сделать что-то своё можно на twigl.app (например)

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

Ютуб youtu.be/zblepnHHCSA
ВК vkvideo.ru/video-230304511_456239017

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

подумал, что это повод попробовать что-то сделать в manim — вот так примерно получилось

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

код наверное положу в комментарии

но лучше посмотреть не на код, а на то, как (визуально) расположены кружки одного цвета — получается похоже на прогулки на торе из статьи Гаянэ Паниной в новом Квантике, вот можно в kvantik.com/issue/pdf/2025-11_sample.pdf посмотреть

(в порядке лытдыбра)

пытался разобраться с применениями тождества тройного произведения Якоби — вот можно посмотреть, как оно выглядит:

from sage.all import *
N = 10
q, Z = var('q'), var('Z')
J = prod((1-q**(2*m))*(1+q**(2*m-1)*Z**2)*(1+q**(2*m-1)*Z**(-2))
         for m in range(1, N+1))
print(J.series(q,2*N+1))

его можно применять к товарищам типа θ(q):=Σq^{n^2} — а степени такой суммы считают представления чисел в виде суммы квадратов и т.д.

но это пока с трудом идет



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

// ранее про разбиения: https://news.1rj.ru/str/compmathweekly/40

про этот сюжет можно прочитать в брошюре «Диаграммы Юнга, плоские разбиения и знакочередующиеся матрицы» Е.Смирнова, https://mccme.ru/free-books/dubna/smirnov-asm.pdf

для разминки написал соответствующее вычисление:

penta = concat [[(p,s), (p+m,s)] | m <- [1..],
                let (p,s) = (m*(3*m-1) `div` 2, (-1)^(m+1))]

partn = 1 : [sum [s*(partn !! (n-p)) | (p,s) <- pents] | n <- [1..],
             let pents = takeWhile ((<= n) . fst) penta]

(и действительно, partn !! 500, скажем, мгновенно отвечает 2300165032574323995027)

(продолжая предыдущее)

положим φ(q)=(1-q)(1-q²)(1-q³)…

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

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

дальше жизнь усложняется, но кое-что еще заметить можно

скажем, для 8-й степени
коэффициенты при q^{4k+3} сразу обращаются в ноль, а коэффициенты при q^{4k+1} делятся на 8, причем если разделить, то получится последовательность -1, 8, -20, 0, 70, -64, -56, 0, 125, которую мы уже видели… (понятно где, да?)

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

Как численно найти корни многочлена?

Если корни сильно разной величины, x₁≫x₂≫x₃≫…, то k-й элементарный симметрический многчлен неотличим от произведения k самых больших иксов, так что любой корень — это примерно отношение соседних коэффициентов многочлена.

Если числа изначально разные по модулю, то чтобы их «раздвинуть» достаточно возвести все их в большую степень. Если P(x) многочлен, то P(√x) конечно не многочлен… зато P(√x)P(-√x) — вполне себе многочлен, а его корни суть квадраты корней исходного. После нескольких таких итераций корни становятся достаточно различными, чтобы работала идея из предыдущего абзаца.

Такой способ предлагал Лобачевский (впрочем до него видимо Данделен), а мне про это рассказал коллега Бахарев.

На коленке реализовал это так:

def absroots(poly,N=5):
    poly, d = np.array(poly,dtype=np.float64), len(poly)-1
    signs = np.ones(d+1)
    signs[1::2] *= -1
    for _ in range(N):
        poly *= 1/poly[-1]
        poly = np.convolve(poly,poly*signs)[::2]
    return np.array([(-poly[k]/poly[k+1])**(1/(2**N))
                     for k in range(d)])

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

Впрочем, уже грубая оценка для всех корней видимо полезна — метод Ньютона, наоборот, сходится очень быстро, но если начинать итерации рядом с корнем (и действительно, пара итераций Лобачевского + пара итераций Ньютона для каких-то многочленов у меня работает прекрасно).

// Ранее здесь про метод Ньютона: https://news.1rj.ru/str/compmathweekly/27 (и далее по ссылкам)

несколько достаточно доступных сюжетов для недавно присоединившихся:

* экспериментальное вычисление пи в экселе
https://news.1rj.ru/str/compmathweekly/76

* что будет, если возвести многочлен в большую степень?
https://news.1rj.ru/str/compmathweekly/81

* знаете ли вы, как выглядит график синуса?
https://news.1rj.ru/str/compmathweekly/89

( предыдущий выпуск: https://news.1rj.ru/str/compmathweekly/64 )

можно ли сравнить две функции за конечное время?

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



функции мы будем рассматривать на множестве Кантора, т.е. на бесконеных последовательностях 0 и 1

т.к. мы пишем программу — и функции на последовательностях, и сами последовательности у нас будут, конечно, только вычислимые; кроме того, они будут всюду определенные (можно написать type Cantor = Natural -> Bit, но надо иметь в виду, что если такая функция для числа 17 не определена, то она не задает элемент множества Кантора)

мы хотели бы сравнить две функции из Cantor, т.е., если угодно, написать функцию equal :: Eq y => (Cantor -> y) -> (Cantor -> y) -> Bool (здесь написано, что если для типа y определено сравнение, то equal сравнивает две функции Cantor→y)

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

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

и всё же можно за конечное время установить не только неравенство, но и равенство:

data Bit = Zero | One
         deriving (Eq)
type Natural = Integer
type Cantor = Natural -> Bit
(#) :: Bit -> Cantor -> Cantor 
x # a = \i -> if i == 0 then x else a(i-1)
forsome :: (Cantor -> Bool) -> Bool
find :: (Cantor -> Bool) -> Cantor
forsome p = p(find p)
find p = first # find(p . (first #))
       where first = if forsome(p . (Zero #)) then Zero else One
equal :: Eq y => (Cantor -> y) -> (Cantor -> y) -> Bool
equal f g = not(forsome(\a -> f a /= g a))

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

при этом определение find через forsome крайне прямолинейное: «если существует пример с первым битом 0, то первый бит равен 0, иначе первый бит равен 1 (а дальше применяем find для определения оставшихся битов)»… и кажется, что пока ничего особо не сделано — но вот такое короткое (и вроде бы тоже довольно тавтологичное) определение forsome чудесным образом позволяет “вытянуть себя за волосы из болота”

мб позже будет комментарий, как это работает — но сразу оставлю ссылку на источник — Martin Escardo по диссертации Ulrich Berger'а; и спасибо коллеге Раскину за объяснения

хочу еще отметить, что это история не про хаскелл, можно напрячься и на питоне (например) переписать — но тут приятно, что синтаксис хорошо соответствует (некоторой) математике