таксебемысль 35 про вещественные числа

Задача хоть и неожиданная, но довольно простая. Прямо вот без дураков, можно давать на кружке детям почти любого возраста.

Докажите, что в любом вещественном отрезке [a,b] найдется ровно одно рациональное число p/q с минимальным |p|+|q|.

Однако забавно, какое неожиданное применение есть у этого факта. В области компьютерной проверки математических результатов бывает полезно иметь точный тип вещественных чисел. Не float'ы какие-то поганые, а вот именно точное представление R. Например, вещественные числа можно определять функциональным образом.

Для этого можно использовать функциональный аналог последовательностей Коши: регулярные функции (термин overused, но увы, не я его придумал). Регулярная функция - это функция f : Q_+ —> Q. Мы говорим, что такая функция представляет вещественное число a, если f(e)∈[a-e,a+e] для любого e. Иными словами, функция хранит рациональные приближения вещественного числа с любой наперед заданной точностью.

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

Поскольку сложность точной арифметики с дробями растет очень быстро относительно размера числителей и знаменателей, осмысленно у рац.чисел минимизировать |p|+|q|. Поэтому полезно на все регулярные функции навесить "аппроксиматор", который не просто выдает рац.число f(e)∈[a-e,a+e], а именно то рац. число, на котором минимизируется |p|+|q| в указанном интервале. С точки зрения функционально-символьной это не сильно усложняет жизнь, процедура вычислимая. Зато упрощает реальные вычисления.

Например, математически было бы естественно хранить вещественное число 6000000/3000001 в виде постоянной регулярной функции, которая выдает его самое при любом e. Но с точки зрения оптимизации, при e>0.000001, можно положить f(e)=2/1, - при грубых округлениях и так сойдет.

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

Подробности см. O'Connor, A Monadic, Functional Implementation of Real Numbers.

PS. Мне вк написали, что числа, которые получаются описанным образом - это наилучшие рац.приближения. Видимо, так оно и есть.

таксебемысль 34 про упаковку шаров

Тут можно было бы написать про результаты Вязовской, - филдсовской лауреатки 2022 - о всюду плотной упаковке в евклидовых пространствах размерности 8 и 24. А можно было про размерность 3: история с гипотезой Кеплера на мой взгляд достаточно иллюстративна, потому что точку в этой истории поставило использование прувера на основе теории типов (хоть и не гомотопической).

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

Оригами. В оригами есть метод дизайна моделей, который называется circle packing. Не уверен, кто придумал идею, и тем более термин, но за подробностями - прошу в книгу Роберта Лэнга Origami Design Secrets: Mathematical Methods for an Ancient Art, где метод впервые был явно объяснен широкой аудитории. 

Забавна предыстория: в Японии в 90-х стала популярна идея математического моделирования оригами - взамен творческому наитию, что породило такую активность как "жучьи войны". Оригамисты соревновались, кто сделает более забористых жучков-паучков с бОльшим числом конечностей. Полагаю, что circle packing был своего рода фольклором в Японии в то время. Лэнг дистанционно участвовал в японских жучьих войнах. В 00-х он окончательно переключился с оригами-как-хобби на оригами-как-профессию, и на английском объяснил суть метода в своей книге.

Суть такова. Желаемую финальную оригами-модель мы представляем себе в виде метрического дерева Г. Это сразу отсекает многие модели: например бегемот или автомобиль - это так себе граф. Но вот богомол, скорпион или паук - это графы. И вот допустим у нашего паука есть какая-нибудь хелицера длины a (= висячее ребро длины a). Тогда бумага, которая уйдет на эту хелицеру - это как минимум круг радиуса a на исходном листе.

[Суперфомальная формализация, которую вы не просили, но заслужили. Процесс складывания - это 1-липшицево отображение F:S-->M, где S - это исходный лист бумаги с римановой метрикой, а М - это итоговая модель - полиэдр в R^3 с внутренней метрикой. Очевидно, что метрика не увеличивается, потому что в оригами рвать бумагу нельзя. Если F(x)=y, а B_r(x) и B_r(y) - шары в S и M соответственно, то из липшицевости очевидно, что полный прообраз B_r(y) содержит B_r(x). Поскольку в метрическом дереве висячее ребро - это шар с центром в висячей вершине, получаем то, что написано в предыдущем абзаце.]

Итак, если у нашего планируемого паука есть конечности длин a1, a2,..., an, то нам на квадратном листе бумаги надо упихнуть попарно непересекающиеся круги радиусов a1, a2,..., an. И сделать при этом так, чтобы лист бумаги был как можно меньше. Ну или при фиксированном листе бумаги, чтобы круги были как можно больше - с сохранением пропорций. Вся бумага вне кругов скорее всего уйдет не в конечности, и мы обычно заинтересованы в том, чтобы ее было как можно меньше. Короче надо решить задачу оптимальной упаковки.

[Вообще-то именно упаковка кругов возникает только если наш паук Г - это граф-звезда. Для более сложных деревьев возникают не только круги, но еще и криволинейные полоски между кругами - как на картинке. Но это все равно хорошо формализуется через условие липшицевости, и возникает оптимизационная задача похожая на упаковку кругов. Задача NP-трудная - как и почти всё в оригами. 

Упаковка кругов и реки между ними.

Да и вообще, сама формализация оригами - дальше соображений липшицевости - уже вопрос, на мой взгляд, открытый. Демэйны - это такая пара геометров из MIT - много в этой области сделали, но их аксиоматика мне кажется плохо алгоритмизуемой. Не существует такой структуры данных как "оригами-модель" (если что, полиэдры в R^3 не учитывают накладывающиеся слои бумаги). В этом смысле оригами гораздо сложнее музыки, картинок и 3d-графики. Корректно определить тип Оригами и формально доказать какую-нибудь базовую теорему - это реально челлендж. Например, хорошая тестовая теорема: любую модель можно сложить, то есть непрерывно изотопировать из плоского листа.]

После оптимальной упаковки надо задизайнить саму модель - с учетом, что модель - это все же не совсем граф. Тут начинается уже разная жесткая геометрия, отчасти эвристическая. Частично все механизируется, см. например https://langorigami.com/article/treemaker/ Но это отдельная история.

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

Вайфай. Второй сюжет - он про фантазию, которая пока явно не применяется. Но, в принципе, наверное зря и наверное в будущем может. 

Вряд ли открою страшную тайну, сказав, что не все, что называют цифровыми технологиями, реально цифровое. В мире по прежнему много чего завязано на аналоговых устройствах. Например, (почти) любая беспроводная связь. Биты по воздуху передаются не по принципу "есть сигнал/нет сигнала", а кодируются в непрерывных характеристиках волн. И вот при переводе из цифры в аналог и обратно возникает довольно любопытная геометрия.

Для финальных пользователей прогресс в беспроводных технологиях измеряется скоростью соединения. В цепочке gsm-3g-4g-5g-6g она растет прямо ощутимо. Достигается это, помимо улучшения передатчиков и приемников, увеличением окна частот, да и самой частоты. Тут все примерно понятно: чем больше частота, тем больше пакетов можно напихать в единицу времени, а чем больше окно - тем больше пакетов распихивается по частотам. Разрабатываемый 6g движется куда-то в сторону терагерцевого диапазона. 

Все это в целом очень круто, но до бесконечности увеличивать частоту вряд ли получится. Поэтому надо параллельно думать об увеличении пространственной плотности пакетов. И тут, помимо возможности поплотнее запихивать пакеты в частотный диапазон, возникает такой замечательный сюжет как оптимизация сигнального созвездия.

Сигнальное созвездие https://ru.wikipedia.org/wiki/Сигнальное_созвездие - это способ кодировать бинарный сигнал в аналоговом пространстве. Зафиксируем пока что частоту. Рассмотрим плоскость с полярными координатами (амплитуда, сдвиг фазы). На этой плоскости изображается сигнальное созвездие - это облако из 2^k точек, соответствующих битовым строчкам длины k. Если нам надо передать битовую строчку, то мы смотрим, какая точка (r,alpha) созвездия ей соответствует, генерируем сигнал амплитуды r со сдвигом alpha (и фиксированной частоты). Передаем его. Приемник получает сигнал с аналоговыми характеристиками (r',alpha'), находит ближайшую к нему точку сигнального созвездия - по Евклиду. И декодирует ее в битовую строчку. 

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

Квадратурная амплитудная модуляция, спертая из википедиев

Очевидно, что чем больше точек мы напихаем в сигнальное созвездие, тем больше битов мы можем передать в одной частоте. Но есть и минусы: при пересылке полученный сигнал (r',alpha') может не совпадать с посланным (r,alpha) из-за белого шума. Тогда при декодировании есть риск получить неправильную битовую строчку, и этот риск тем больше, чем более плотно мы напихали точек в созвездие. Ошибку можно детектировать на стороне получателя при помощи стандартной дискры - но не исправить. Если при передаче словили баг, то весь пакет просто пересылается заново. Поэтому геометрические ошибки - это для скорости передачи прямо вот совсем не круто.

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

Тут, казалось бы, делов-то.

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

- На основании эллипсоидов нормальных распределений задать на плоскости риманову метрику.

- В этой метрике решить задачу оптимальной упаковки шаров.

- Для полученного сигнального созвездия подобрать линейное разрешающее дерево для диаграммы Вороного.

- Спаять это разрешающее дерево из демодуляторов.

- Пропихнуть это в качестве стандарта для 7G.

- Profit!

Можно сразу работать не с 2-мерным пространством, а с 3-хмерным, где третья координата - частота. И уплотнять шары сразу в трехмерном римановом многообразии, построенном из эмпирических соображений.

Сделал бы, да только вот не паял с начальной школы) Причем вот такое впечатление, что люди про нечто подобное и думали, и статьи писали, красивые картинки сигнальных созвездий гуглятся. Но широкого применения пока нет.

таксебемысль 33 о геометрической топологии

В одном из наших лабных чатов обсуждался наивный вопрос, индуцировавший у меня некий поток сознания. Кмк, можно все это вынести на более широкое обозрение/обсуждение. Вопрос:

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

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

Ответ, очевидно, зависит от того, что понимается под словом карта.

Вариант 1, который, считался дефолтным в обсуждении. Карта - это что-то стягиваемое, типа диска. Тогда это как будто вопрос о категории Люстерника-Шнирельмана (кстати, а это правда?). Хочется сказать, что категория = 2 только у гладких многообразий гомеоморфных сфере, в том числе у экзотических. 

В размерности 2 это так: у всех поверхностей кроме сферы слишком большая когомологическая длина. В размерности 3 тоже так: например, см.  https://www.sciencedirect.com/science/article/pii/0040938392900097 + Пуанкаре/Перельман. В общей размерности из cat=2 вытекает что когомологическая длина равна 1, а значит многообразие - гомологическая сфера. Что делать с зазором между гомологическими сферами и настоящей сферой - я не знаю, нужны специалисты. Чую, что у нетривиальной гомологической сферы не может быть атласа из двух стягиваемых карт, но доказать не умею.

Вариант 2. Карта - это любое открытое множество U нашего Mⁿ, гомеоморфное области в Rⁿ. Формальное определение атласа именно такое, на самом деле. 

Тут имею сказать интересную вещь. 

Во-первых, любая ориентируемая 2-поверхность имеет атлас из двух карт (например, тор можно склеить из двух аннулюсов, - всратое видео с китайской фабрики не даст соврать https://www.youtube.com/watch?v=QkPqGnXD-yA ). У неориентируемых: атлас из 2 карт есть у поверхностей четного рода, а у неориентируемых нечетного рода как будто нет (задача). 

Во-вторых, у любого трехмерного многообразия есть атлас из двух карт. Возьмем разбиение Хегора и каждую из двух компонент немного утолстим, чтобы получить открытое множество. Получили два множества, каждое из которых - открытый шар с ручками - вполне себе вкладывается в R³. Чем не карты.

В-третьих, кажется, что фокус с разбиением Хегора работает с любым многообразием нечетной размерности >1. Возьмем у (2n+1)-мерного многообразия M триангуляцию K, двойственное ей клеточное разбиение L, и разобьем M в объединение окрестностей n-мерного остова K и n-мерного остова L. Оба остова вкладываются в R²ⁿ⁺¹, уж наверное, их окрестности тоже вложатся. Опять же получили атлас из двух карт.

(про высокомерного Хегора тут обсуждают https://mathoverflow.net/questions/81041/higher-dimensional-heegaard-splittings правда вложимость окрестностей аккуратно проверять надо, например через индуктивное приклеивание ручек. Есть ощущение, что ручки малого индекса, а объемлющее пространство большой размерности. Места для приклейки ручек вроде должно хватить, но это не точно.) 

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

Такая вот задача внезапная.

таксебемысль 32 тропическая

Подумалось, довольно странно, я тут много чего пишу, а вот про тропические штуки ни разу не писал. Надо исправляться. 

Этакие туристические наброски: немного о происхождении видов, об особенностях продажи фруктов, о деревьях, об отличиях тропиков Рака и Козерога, об особенностях работы таксистов и о венгерских мигрантах. Небольшое экзотическое путешествие.

0) Интро. 

Тропическая математика - это тропическая арифметика и тропическая геометрия. Про другие дисциплины, например, тропическую топологию или тервер, никогда не слышал.

Тропическая арифметика - это множество вещественных чисел, на которых определены две арифметических операции: тропическое сложение a⊕b=min(a,b) и тропическое умножение a⊙b=a+b. Приятно проверить, что тропические операции удовлетворяют базовым школьным законам коммутативности, ассоциативности и дистрибутивности.

Алгебраическая мотивация за этим такая. Есть многочлены от одной переменной, их довольно полезно складывать и умножать, в обычном смысле. Можно от многочлена F оставить только младшую степень k(F) входящих в него мономов. Тогда легко заметить, что при умножении многочленов числа k(F) складываются, а при сложении/вычитании - от них берется минимум (*за исключением ситуации, когда младшие члены сокращаются, но такого почти никогда не бывает, и этим пока можно пренебречь). Если вместо k(F) брать порядок нуля в какой-то фиксированной точке, - не только в 0, - то арифметика таких порядков тоже получается тропической. Вместо многочленов F можно брать формальные степенные ряды, многочлены или ряды Лорана, ряды Пюизо, ряды Хана или ряды Новикова - во всех случаях тропикализация состоит во взятии младшего порядка.

В соответствии с общей идеологией, если обычный моном от нескольких переменных - это выражение вида a⋅x^k⋅y^l⋅z^m..., то тропический моном - это a+kx+ly+mz+..., то есть просто линейная функция (с целыми коэффициентами ). Тропический многочлен - это тропическая сумма набора мономов, то есть, говоря по человечески, минимум от конечного числа линейных функций. Можно заметить, что это всегда непрерывная выпуклая вверх кусочно линейная функция.

В обычной математике мы называем алгебраической (гипер)поверхностью в R^n множество нулей некоторого многочлена от переменных x1,...,xn. Вот здесь при тропикализации происходит неочевидный сюжетный твист. Тропической гиперповерхностью в R^n называется множество точек излома тропического многочлена - рассматриваемого как кусочно-линейная функция. То есть, если 

P(x1,...,xn)=⊕{ak⊙x1^k1⊙...⊙xn^kn}=min{ak+k1⋅x1+...+kn⋅xn}

- тропический многочлен, то множество его "нулей" - это множество всех таких x=(x1,...,xn), для которых минимум в правой части достигается хотя бы на двух выражениях одновременно.

Пример. Ноль линейного тропического многочлена P(x)=2⊕(3⊙x) - это точка излома функции min(2,3+x), то есть точка x0=-1 (при которой 2=3+x0).

Аффинное тропическое многообразие - это пересечение конечного числа тропических гиперповерхностей. Это какая-то странная неограниченная кусочно линейная штука в R^n. 

Аффинная тропическая кривая (какая-то, не суть важно)

Почему нули тропических многочленов нужно определять именно так (как множество точек излома) - вопрос довольно естественный. Если вкратце, то история такая. Допустим, что у нас изначально система обычных алгебраических уравнений определена не над полем R или C, а над полем рядов Пюизо от одной переменной. 

Ряды Пюизо - это формальные ряды Лорана от дробных степеней переменной. Ряды Пюизо образуют алгебраически замкнутое поле, - это на самом деле алгебраическое замыкание поля обычных рядов Лорана. Поэтому, в принципе, на ряды Пюизо можно смотреть как на некий функциональный аналог поля C - вся университетская интуиция тут работает, но появляется бонус: у рядов Пюизо можно брать младшую степень k(F), - чего не бывает в C. Так вот, если определить множество настоящих нулей многочлена P(x1,...,xn) над полем рядов Пюизо, и взять у каждого решения F младшую степень k(F), то полученное множество как раз и будет множеством тропических решений соответствующего тропикализованного многочлена.

Пример. Найдем решение уравнения (5t^2-3t^4-t^7)+x(4t^3+8t^5-t^9)=0 относительно x в поле рядов Пюизо от t. Тут даже рядов Пюизо не надо, все решается в обычных степеных рядах x=-(5t^2-3t^4-t^7)/(4t^3+8t^5-t^9)=-(5/4)t^{-1}+[члены старших степеней]. Если от всех формальных выражений оставить только младшие порядки, то останется тропическое уравнение 2⊕(3⊙x)=0 из прошлого примера. То, что мы в прошлом примере получили тропическое решение x0=-1 полностью согласуется с тем фактом, что честное решение исходного уравнения начинается с члена t^{-1}.

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

1) Философия.

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

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

Позитивный супер-пример: можно определить тропические когомологии проективных тропических многообразий (как обобщение когомологий Дольбо обычных комплексных многообразий). И можно попробовать доказать тропический аналог гипотезы Ходжа (не-тропическая гипотеза Ходжа - это одна из гипотез тысячелетия, на всякий случай). Это содержательно, см. 

I.Itenberg, L.Katzarkov, G.Mikhalkin, I.Zharkov, Tropical Homology, Mathematische Annalen 374 (2019) и прочий свежачок.

А негативные примеры тут будут мелькать ниже.

2) История.

Сейчас тропическую математику обычно упоминают в контексте геометрии, именно в том смысле, что тропическая геометрия - это эрзац-алгебраическая геометрия. Исторически, однако, тропические штуки возникли как удобный язык для работы с алгоритмами.

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

Пусть дан "метрический" граф на n вершинах, то есть фиксирована матрица расстояний D=(d[i,j]) где d[i,j] - расстояние от i-й вершины до j-й вершины (расстояния могут быть бесконечными, несимметричными и не удовлетворять неравенству треугольника). Тогда тропический квадрат D⊙D матрицы - это матрица расстояний-за-два-шага в исходном графе (упражнение на осознать). А тропическая k-ая степень матрицы D - это матрица расстояний за k шагов.

Название "тропическая" произошло в честь Имре Симона, который работал в Сан-Паулу, Бразилия, и занимался как раз-таки алгоритмами. Впрочем, сам он был венгром, поэтому не будет большой ошибкой сказать, что тропическая математика - это часть венгерской математики, несмотря на географический диссонанс такого утверждения.

3) Определители.

Обычный определитель матрицы A=(a[i,j]) размера n - это сумма по всем перестановкам s:[n]-->[n] произведений вида a[1,s(1)]⋅a[2,s(2)]⋅...⋅a[n,s(n)] с какими-то знаками. В интернете есть многочисленные треды, где обсуждается, есть ли какая-то польза от определителей больших матриц. Ну то есть для математики, понятно, что есть абстрактная польза, иначе зачем бы мы это учили. Но вот возникает ли где-то на практике необходимость быстро посчитать определитель размера хотя бы 20? Уже вопрос. Ни одного интересного примера я не нашел, как ни странно.

Тем не менее, если мы все же праздно зададимся вопросом об алгоритмической сложности вычисления определителя, то получится такая история. Вычисление определителя по определению занимает O(n!) операций, в формуле одних слагаемых уже n! штук. Многовато. 

К счастью для нас, в курсе линала есть весьма фундаментальная штука - алгоритм Гаусса. В его прикладной ценности сомнений гораздо меньше. Его же можно приспособить для вычисления определителя. Вычисление по Гауссу займет O(n^3) арифметических операций. 

Если долго и целеустремленно копать, то можно отрыть алгоритм вычисления определителя, основанный на константе матричного умножения. Он теоретически работает за O(n^2.37188), но там настолько неописуемо ужасная O-константа, что на практике это не слишком полезно. 

Теперь следите за руками. 

Что такое тропический определитель? Заменим в формуле определителя сумму на минимум, а произведения на суммы, про знаки перестановок просто забудем. Получим, что тропический определитель матрицы A=(a[i,j]) - это минимум по всем перестановкам s:[n]-->[n] сумм вида a[1,s(1)]+a[2,s(2)]+...+a[n,s(n)].

Оказывается, что вычисление тропического определителя - это офигенно важная задача, которая каждый день решается агрегаторами такси, службами доставки и прочими провайдерами услуг. Это задача об оптимальном назначении.

Допустим у нас есть n клиентов и n такси, и известно, что отправить i-го таксиста к j-му клиенту стоит a[i,j] денег. Назначение - это биективное соответствие между клиентами и таксистами, то есть попросту перестановка s:[n]-->[n]. Стоимость назначения - это (внезапно) сумма a[1,s(1)]+a[2,s(2)]+...+a[n,s(n)]. Нам надо назначить таксистов клиентам так, чтобы минимизировать стоимость. То есть тропический определитель - это буквально стоимость оптимального назначения.

Априори не очевидно, почему оптимальное назначение можно вычислить менее чем за n! операций. Есть, однако, знаменитое решение за полиномиальное время, так называемый Венгерский алгоритм. На самом деле, это целый класс алгоритмов, основанный более-менее на симплекс-методе. 

Лучшая известная реализация Венгерского алгоритма имеет сложность O(n^3). Она довольно хитрая, там вообще ни разу не понятно, почему алгоритм сходится, почему имеет такую сложность и т.д. Однако идеологически все не так уж хитро. Алгоритм Гаусса для обычного определителя ведь работает за O(n^3), так сфигали в тропиках будет по-другому?

В первом приближении вполне можно считать Венгерский алгоритм тропикализацией алгоритма Гаусса. Во втором приближении, правда, возникает

Нюанс. Наивная тропикализация всей программы первого курса линала не работает. Например, элементарная формула TropDet(A⊙B)=TropDet(A)⊙TropDet(B) попросту не верна. What a disgrace!

Вопрос существования Венгерского алгоритма сложности O(n^2.37188) открыт. Возможно, тропическая интуиция тут как-то поможет.

(-) Интерлюдия: тропики Рака и Козерога

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

Разница не существенная: минимум и максимум меняются местами, если все переменные умножить на -1.

4) Коциклы

Начнем с обычного, не тропического сеттинга. Рассмотрим полный граф на n вершинах, и на каждое его ребро {i,j} посадим вещественную переменную d[i,j]. Можно для полноты картины добавить фиктивные переменные d[i,i]=0 и d[j,i]=-d[i,j]. Множество нефиктивных переменных - это вещественное пространство M размерности n(n-1)/2.

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

d[i,j]+d[j,k]+d[k,i]=0

для любой тройки {i,j,k}. Нехитро показать, что в этом случае d[i,j]=x[j]-x[i] для некоторого набора вещественных чисел x[1],...,x[n]. То есть набор чиселок d[i,j] при i<j - это просто расстояния между набором точек на прямой, с учетом знака. Если вы доказали этот факт, то можете смело хвастаться, что знаете, почему 1-е когомологии симплекса нулевые. 

В итоге условие коцикла выделяет в M векторное подпространство размерности n-1. 

Что такое тропикализация этого подпространства? В соответсвии с общей идеологией, заменим каждое уравнение d[i,j]+d[j,k]+d[k,i]=0 условием 

"max(d[i,j], d[j,k], d[k,i]) достигается одновременно хотя бы на двух аргументах"

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

Заметим, что такое тропикализованное условие для тройки эквивалентно набору условий d[i,j]≤max(d[j,k], d[k,i]), каждый элемент тройки не больше максимума двух других. И это выполнено для каждой тройки {i,j,k}.

Это же определение ультраметрики! Ну окей, при условии, что d[i,j]>0, это точно определение ультраметрики. Получили 

Тезис. В пространстве всех положительных вещественных функций на ребрах полного графа, тропическое условие коцикла задает множество ультраметрик.

От этой конструкции есть потенциальная польза народному хозяйству. Допустим, у нас есть некое конечное множество биологических видов, и стоит задача построить по ним филогенетическое дерево, то есть определить кто с кем имел общего предка, когда этот предок жил, и как все эти предки друг из друга происходили. 

Мы не можем заглянуть в прошлое, но у нас есть текущий временной срез, в котором можно проводить любые эксперименты, допустимые нашим уровнем технологий, и предлагать любые интерпретации, допустимые подвешенностью языка экспериментатора. Например, можно взять любые два вида из нашей выборки и оценить их "похожесть", скажем, на основании геномов. Мы получим эмпирический набор положительных чисел. Из общих соображений понятно, что похожие геномы <=> недалекий общий предок. Но как из этого филогенетическое дерево сделать?

Поехали. Заметим, что любое (гипотетическое) филогенетическое дерево задает метрику: d[i,j]="сколько лет назад жил общий предок i-го и j-го вида". И это на самом деле ультраметрика. И наоборот, любая ультраметрика происходит из некоторого филогенетического дерева, упражнение.

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

Да и вообще бывает полезно метрику приближать ультраметрикой. Я в прошлый раз ?? писал, что это, как минимум, используется в производстве графония. Не то, чтобы у меня был для вас явный алгоритм, как надо проецировать на тропические коциклы. Но, согласитесь, наука-то получилась прикольная.

5) Грассманиан

Историю про связь "Происхождения видов" с тропической математикой я, конечно, не сам выдумал, а взял из статьи 

D.Speyer, B.Sturmfels, The tropical Grassmannian, Adv.Geom.4:3, 2004.

Но там написано несколько другое. Я в прошлом пункте немного упростил картину для первичной ясности. А сейчас справедливость будет восстановлена.

Подход с ультраметрикой биолог смог бы покритиковать вот каким образом. Если у нас есть филогенетическое дерево с указанием, когда жил общий предок каждых двух видов, то мы можем распространить нашу метрику и на самих этих предков. То есть, если общий предок человека и крокодила, - крокочел, - жил 250 млн лет назад, то расстояние и от человека до крокочела и от крокодила до крокочела одинаково и равно 250/2. Но это как-то тупо с точки зрения генома: человек за это время эволюционировал как ненормальный, а крокодил - он, сука, крокодилом и остался, ибо совершенство не требует изменений. 

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

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

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

Так вот, оказывается, что древесные метрики - это тоже тропическое многообразие. Причем не абы какое, а просто прелесть что за многообразие. Но обо всем по порядку.

Обычный грассманиан Gr(q,n) - это многообразие q-мерных подпространств в n-мерном пространстве. Если каждому подпространству П∊Gr(q,n) сопоставить прямую старших внешних форм Λ^qП в Λ^q(R^n) то получим вложение Gr(q,n) в проективное пространство какой-то большой размерности. Образ этого вложения описывается соотношениями Плюккера.

В общем виде нам соотношения Плюккера не понадобятся. В случае Gr(2,n), то есть грассманиана 2-плоскостей, образ вложения задается координатами d[i,j] для всех пар {i,j} из множества {1,..,n}, а соотношения Плюккера имеют вид

+/- d[i,j]d[k,l] +/- d[i,k]d[j,l] +/- d[i,l]d[j,k] = 0

для любой четверки индексов {i,j,k,l}. Знаки в этой формуле нам не особо важны. Но если вам очень надо, - то они такие же, как в теореме Птолемея https://ru.wikipedia.org/wiki/Неравенство_Птолемея . Вообще это отдельная креативная задача (https://vk.com/id3973145?w=wall3973145_1506%2Fall): вывести Плюккера из Птолемея. Или хотя бы наоборот.

 

Давайте тропикализуем соотношения Плюккера. Формула выше превращается в условие

"max(d[i,j]+d[k,l], d[i,k]+d[j,l], d[i,l]+d[j,k]) достигается хотя бы на двух аргументах для любой четверки {i,j,k,l}."

Как и в прошлом пункте, это условие эквивалентно такому

d[i,j]+d[k,l] ≤ max(d[i,k]+d[j,l], d[i,l]+d[j,k]).

Последнее условие хорошо известно, оно называется Four Point Condition. И оно в точности характеризует все древесные метрики. Получили

Тезис. Множество всех древесных метрик на [n] - это тропикализация стандартного плюккерова вложения грассманиана Gr(2,n).

Соответственно, если мы хотим восстановить филогенетическое дерево с учетом скорости эволюции, то надо проецировать нашу функцию генетических похожестей на тропический грассманиан. 

6) Аукционы

Десертом нашего сегодняшнего тропического пиршества будет менее серьезный сюжет, о котором мне три года назад рассказал Никита Калинин. Это история про то, "как тропическая геометрия спасла Банк Англии от финансового кризиса". 

Тропические геометры спасают Англию от экономического кризиса. (с)перто из интернетов.

Отличная иллюстрация тезиса, что лучшая реклама микроскопа - та, в которой им забивают гвозди. Если вы, читая предыдущие пункты, не могли избавиться от ощущения, что сову натягивают на глобус, то, чтож... Hold my beer!

Рассказ следует работе, P.Klemperer, The Product-Mix Auction: a New Auction Design for Differentiated Goods, Journal of the European Economic Association, 2010. 

Кризис 2008 ударил по разным направлениям. Одной из конкретных проблем Банка Англии было отсутствие внятного протокола кредитования более мелких банков. Имеющиеся практики последовательных аукционов давали банкам много возможностей налюбить систему, что часто приводило к "как бы равновесным" решениям, от которых реально страдал как центробанк, так и сами мелкие банки. Никогда такого не было, и вот опять. 

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

Поскольку всякие умные банковские слова из работы Клемперера я не понимаю, попробую объяснить механику по рабоче-крестьянски. 

Допустим, есть аукционер, который хочет продать апельсины А и бананы Б. Он заранее объявляет сколько всего фруктов продается в этом раунде. Тут есть варианты. В простейшем варианте - он говорит, сколько А и сколько Б продается. В более сложных вариантах он объявляет сколько в сумме фруктов будет распродаваться, и рисует кривую соотношения А/Б в зависимости от отношения итоговых цен на то и другое.

Дальше участники аукциона делают ставки. Каждая ставка имеет вид "готов купить А по цене x, B по цене y, всего куплю v фруктов". Каждый участник может сделать таких ставок сколько угодно. Ставки публичны. Каждую ставку можно изобразить на плоскости с координатами А-Б точкой (x,y) с весом v.

Когда прием ставок заканчивается, аукционер выбирает реальную стоимость продажи (x0,y0) апельсинов и бананов. Через некоторое время станет понятно, как он это делает. Допустим пока, что стоимость выбрана. Какой алгоритм выбора покупателей: 

1) Выкинем все ставки из прямоугольника (x<x0)&(y<y0). Это лузеры, которые не угадали.

2) Оставшуюся область разделим пополам прямой x-x0=y-y0. Если для данной ставки выполнено x-x0>y-y0, скажем, что этот чувак будет покупать только апельсины, а если y-y0>x-x0 - только бананы. Ну типа логично, если чувак установил цену на апельсины сильно выше, чем их реальная цена продажи (которую он, впрочем, не знает), то наверное апельсинов ему больше хочется...

3) Продаем бананы и апельсины по цене (x0,y0) в количестве указанном во всех отобранных ставках.

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

Алгоритм отбора покупателей, и что именно они будут покупать вроде нехитрый. Теперь как выбирается стоимость (x0,y0). А очень просто: на основании изначально озвученных ограничений аукционера. 

Допустим аукционер сказал, что продаст 1000 фруктов. Он посчитал сколько всего фруктов во всех ставках и получилось 5000 фруктов. Это значит, что в первом пункте алгоритма нужно отсечь ставок суммарно на 4000 фруктов. То есть аукционер подбирает (x0,y0) так, чтобы прямоугольник (x<x0)&(y<y0) содержал ставок ровно на 4000, ну или чуть больше. 

Заметим, что таких прямоугольников аж однопараметрическое семейство, что-то вроде угловатой гиперболы, см. скопипащенный рис. из статьи ??. Чтобы однозначно выбрать на этой кривой точку, надо вспомнить о нашей договоренности по соотношению А/Б. Утверждается, что найдется ровно одна точка, для которой выполнено требуемое соотношение. Это такое базовое упражнение на непрерывность, по типу теоремы о бутерброде с колбасой. Вот эту точку аукционер и берет в качестве (x0,y0).

*Точка, конечно, может быть не единственной. Но единственным будет выбор - кого отсекать, кому продавать апельсины, а кому бананы.

Хорошая геометро-экономическая разминка на вечер: придумать спекуляцию, чтобы накупить на таком аукционе бананов подешевле. И понять, в чем риск для спекулянта. И еще: насколько всем экономистам было бы веселее, если бы ставки было разрешено размазывать по плоскости произвольным равномерным распределением, а не только дельта-мерами.

А причем тут тропическая геометрия? Да тупо при том, что линия, по которой аукционер разделяет лузеров, которые уйдут ни с чем, покупателей апельсинов и покупателей бананов - это тропическая прямая max(0, x-x0, y-y0), т.е. множество точек, где максимум принимается дважды.

Если бы фруктов было не 2, а n, то абсолютно аналогично можно было бы провести аукцион, используя в качестве критерия отбора разделение пространства R^n на (n+1) камеру тропической гиперплоскостью. 

Аукцион прикольный, но ничего математически содержательного тут, как будто, нет. Однако математики смекнули, что надо к этому делу пристроиться. Вот в работе

E.Baldwin, P.Klemperer, Tropical geometry to analyse demand

тропическим матаном аж на 83 страницы обмазываются. Вдруг кому интересны подробности.

таксебемысль 31 о комбинаторике производства.

Недавно узнал одну красивую и, на мой взгляд, уникальную историю, спешу поделиться. Эта история о том, что модель, придуманная для нужд сугубо прикладных, оказалась глубже, чем кажется с первого взгляда, и в некоторый момент обогатила математику занятным результатом. Который можно взять и использовать где-нибудь еще. А уникальность истории в том, что это не про какую-нибудь физику с зеркальной симметрией, где все очень увлекательно, но малопонятно. Тут будет короткий рассказ, доступный людям с базовым знанием линала: про экономику и многогранники.

Рассмотрим систему линейных уравнений Ax=b с вещественными коэффициентами, где число уравнений g меньше чем число неизвестных f. Решение такой системы - аффинное подпространство V в R^g. Давайте посмотрим на множество P всех решений, у которых все координаты неотрицательны (пишут x≥0). То есть P - это пересечение V с неотрицательным конусом в R^g. Будем предполагать, что это множество непустое, чтобы не делать каждый раз об этом оговорку. Множество P  - это какой-то выпуклый полиэдр, может быть, ограниченный, а может и нет.

Определение. Система Ax=b и соответствующий полиэдр решений называется моделью Леонтьева с замещением, если любой столбец матрицы A содержит не более одного положительного элемента, и, кроме того, b≥0. 

Поймем, откуда такое берется. Допустим, что у нас есть g товаров - они же ресурсы, они же goods. И f фабрик - они же производства. Каждая фабрика умеет за единицу времени, рабочий цикл, преобразовать какой-то набор ресурсов, в определенных количествах, в новый ресурс, в каком-то количестве. Или просто потребить какой-то набор ресурсов и нихрена не произвести. Не очень понятно, зачем такое может быть нужно, - но нам не жалко, пусть будет. Таким образом, рабочий цикл каждой фабрики характеризуется вектор-столбцом (a[1,j],a[2,j],...,a[g,j])^t, где a[i,j] - количество i-го ресурса, произведенного фабрикой. Видно, что все эти числа, кроме, быть может, одного, неположительны: фабрика же их тратит, а не производит. Составим из этих столбцов матрицу A.

Теперь должно быть понятно, что решить систему Ax=b с неотрицательными x, - это означает найти, сколько должна работать каждая фабрика, чтобы по итогу вся наша экономика произвела заданный вектор-столбец b ресурсов. Мы хотим (ну наверное), чтобы был профицит, поэтому условие b≥0 тоже кажется довольно естественным.

Окей, вот вам модель, можете ее использовать например в разработке экономических игрушек, по типу Зельеварения. Хотя так с нуля придумать "правила размена ресурсов", чтобы хоть одно решение было, - это уже не вполне очевидно. Интуитивно понятно, что производиться должно примерно больше, чем потребляться, поэтому положительный элемент в столбце должен мажорировать сумму модулей отрицательных - ну в среднем по палате, по крайней мере. История, которая написана ниже, она в каком-то смысле про то, что это "усреднение по столбцам" не так много качественно различных комбинаций может давать.

Модель придумал Василий Леонтьев (нобелевский лауреат по экономике, между прочим) в книге 

W.W.Leontief, Structure of the American Economy, 1919-1939. An Empirical Application of Equilibrium Analysis, 1951.

Книгу не читал, про что там - не знаю. Но как я понял по всяким статьям, изначально в модели предполагалось, что каждый товар можно производить только одним способом, - грубо говоря, только на одной фабрике, - поэтому в матрице A все положительные элементы в столбцах появлялись на попарно разных позициях. Вот модель Леонтьева с замещением (Leontief substitution model) - это как раз без этого условия. Слово "замещение" в названии - оно про то, что какой-нибудь сахар, например, можно производить разными способами из разного сырья на разных фабриках.

Что дальше с моделью Леонтьева делать - это уже вопрос практического интереса. Например, можно попытаться среди всех решений найти такое, которое минимизирует какие-нибудь косты, - то есть погонять на полиэдре решений P симплекс-метод. Или можно прокачать модель, чтобы она включала время: смотреть, чего происходит с производством раз в квартал, и где надо подкрутить, чтобы не было кризиса перепроизводства: получается какая-то динамика на полиэдре. И это только в экономике. А ведь можно примерно ту же модель допилить для оптимизации каких-нибудь информационных потоков, распараллеливания программ, бизнес-администрирования и бог знает чего еще. 

Наверняка это всё уже делают, но сейчас не о том. Вернемся к математике.

Напомню для тех кто не знал, что полиэдр называется простым, если в любой его вершине сходится ровно столько гиперграней, какова его размерность. Будем говорить, что система Ax=b находится в общем положении, если ее полиэдр простой. Если брать коэффициенты уравнений наобум, всегда получается система в общем положении: потому что вероятность того, что более чем n случайных гиперплоскостей в R^n пересекаются в одной точке, равна нулю.

И-и-и, дамы и господа, барабанная дробь... 

Теорема. Если система Леонтьева с замещением в общем положении, то 

1) если полиэдр решений ограничен (= тотальная система Леонтьева), то он комбинаторно эквивалентен произведению симплексов 

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

Этот замечательный факт доказан в статье

L.J.Billera, J.S.Provan, Leontief Substitution Systems and Matroid Complexes, Mathematics of Operations Research 7:1 (1982),

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

И когда это утверждение впервые видишь, то думаешь: да лааадно, быть такого не может. Щас производство в виде пятиугольника наладим. Не получается. Потом думаешь, ок, ну раз так, то должно как-то концептуально доказываться. Жахнуть двойственность Гейла: очень удачно, что столбцы матрицы A двойственны к нормалям многогранника, условие на столбцы что-то должно говорить о Гейл-двойственной конфигурации. Но вот нифига: двойственность Гейла позволяет доказать, что любой полиэдр можно реализовать матрицей А с не более одним положительным числом в каждом столбце. Цимес в правой части системы: неотрицательность b очень сильные дополнительные ограничения накладывает. Биллера-Прован по существу ссылаются на технический результат другой работы, и там какое-то злое вуду с двойственностью задач выпуклой оптимизации. Без хорошего знания линейного программирования и соответствующей интуиции не вкурить. Короче, мои отношения с этой теоремой сейчас на стадии депрессии: вроде вот же оно доказательство, и слова какие-то знакомые. Но целиком непонятно.

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

Чем теорема хороша для теории? Я бы сказал, парой лемм, которые используются для доказательства. Рассмотрим симплициальный комплекс Леонтьева - симплициальный комплекс, двойственный к простому полиэдру решений для системы Леонтьева в общем положении.

Лемма 1. Тотальный комплекс Леонтьева (ограниченная ситуация) является матроидом (симплициальным комплексом независимых подмножеств матроида).

Тут можно вспомнить, что матроиды - это, вообще говоря, какие-то штуковины, гомотопные букетам сфер одной размерности. Но комплекс Леонтьева - это ведь симплициальная сфера если полиэдр ограниченный. То есть это псевдомногообразие. Ясно, что не абы какой матроид является псевдомногообразием.

Лемма 2. Если матроидный комплекс является псевдомногообразием, то он изоморфен джойну границ симплексов. Если матроидный комплекс является псевдомногообразием с границей, то он изоморфен джойну симплекса и границ симплексов.

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

А еще можно задавать какие-то осмысленные вопросы. Например, насколько разнообразной может быть комбинаторика производства, если разрешить фабрикам производить одновременно не один товар, а, например, два? То есть ослабить условие на матрицу до двух положительных значений в столбце. 

Надеюсь, заинтриговал.

таксебемысль 30 об ультраметриках, кластеризации и маркетинговых успехах видеокарт

Настало время для еще одной комбинированной истории про математику и модные плюшки. А именно про то, что спрятано под капотом у плашки "RTX on", которую можно увидеть в современных игрушках, вернее даже в и их рекламе. А там спрятаны прелюбопытные вещи: заполняющие пространство кривые, кластеризация, одноканальное кодирование, и множество Кантора.

Давайте по порядку. 2018 год запомнился ценителям неким знаменательным событием: Nvidia с большой помпой выкатила первое поколение видеокарт, которые могут в рэйтрейсинг (RT) в реальном времени. Они даже какую-то дурацкую характеристику придумали: "гигалучи в секунду", которых вот типа у них теперь 10, и это гораздо больше, чем было раньше. Но, как по мне, чисто маркетинговый трюк: никаких 10 миллиардов лучей в общем случае их карты как тогда не считали, так и сейчас не считают. Если бы это в принципе было возможно, то мы бы уже имели фотореалистичную виртуальную реальность на автономных шлемах. 

Жызнь с бородой / Жызнь без бороды

Итак, что такое рэйтрейсинг (трассировка лучей, если по человечески). Это один из способов рендеринга. 

Рендеринг - это процесс перевода 3d-сцены в 2-мерное изображение на плоском экране. Базовая единица экрана - пиксель, базовая единица сцены - треугольник. Рендеринг состоит в построении соответствия между треугольниками и пикселями. Пусть первых П штук, а вторых - T, обе величины квадратично растут относительно уровня детализации. Можно помыслить себе гигантскую матрицу размера ПxТ, в которой по одному измерению перечислены пиксели, а по другому треугольники. В этой матрице на (i,j)-месте стоит цвет i-го пикселя, который дает j-й треугольник. Эта матрица очень разреженная: если взять наобум треугольник, то он мало пикселей на экране занимает, если вообще занимает. Для вычисления цвета нужно знать нормаль к поверхности и световой фон, - это отдельная история, о которой я писал раньше.

Есть два типа рендеринга: растеризация и рэйтрейсинг. Они в некотором смысле двойственны друг другу по Даукеру. 

При растеризации мы проходим по всем треугольникам сцены, и каждый из них проецируем из точки наблюдателя на экран - начиная от дальних и заканчивая ближними, - чтобы ближние перекрывали дальние. При растеризации одного треугольника мы проходим ровно по тем пикселям, которые задевает треугольник, - и ни по каким больше. То есть мы в итоге перебираем все непустые ячейки нашей ПхТ матрицы, и только их. Число операций, которые для этого требуются, близко к теоретическому минимуму, - а значит этот метод очень шустрый, и практически неулучшаемый. А потому это дефолтный метод в игрушках и 3d-редакторах.

При рэйтрейсинге мы проходим по всем пикселям, через каждый из них от наблюдателя пускаем луч, и проверяем, какие треугольники он пересекает. Берем самый ближний, и его цветом закрашиваем пиксель. Математически как будто то же, что и раньше. Спроецировать треугольник на плоскость так же просто, как и проверить, пересекает ли луч треугольник (про концептуальный взгляд на последнее см. заметку о двойственности Гейла). Но есть нюанс. При наивном рэйтрейсинге надо проверить на пересечение ВСЕ треугольники сцены. Мы же априори не знаем какие из них попадают на камеру, а какие нет. Поэтому при наивном рэйтрейсинге требуется ПхТ операций. Это получается 4-ая степень от детализированности, что убер-дофига. Даже не только для игрушек, но и для какого-нибудь Кэмерона с его "Аватаром".

Казалось бы, на черта нам тогда этот рэйтрейсинг поганый? Потому что он в принципе похож на то, как свет себя ведет в геометрической оптике, а значит с помощью него можно хорошо симулировать физические эффекты: отражения, преломления, да и в целом распространение света. Если мы пустили луч в сцену и он наткнулся на треугольник со свойством зеркальности, то нам достаточно отразить луч (используя значение из карты нормалей): проитерируем пуск луча уже из новой точки и в новом направлении, и посмотрим, на что он наткнется дальше. Или например, если мы хотим понять освещенность какой-то точки сцены, то мы пустим в эту точку луч из источника света - и поймем, натыкается он на пути на препятствие или нет. Вообще отрисовка теней от объектов - это отдельная проблема, которую кое-как решать научились: например, Doom3 прославился довольно эстетичным новым алгоритмом для этого дела. Но вот если бы рэйтрейсинг хорошо работал - то он бы и проблему с тенями автоматом решал.

Остается оптимизировать рэйтрейсинг, так чтобы он работал за разумное время. Первый шаг к решению: засунуть каждый отдельный объект сцены в виртуальный контейнер: под контейнером дальше всегда понимается параллелепипед со сторонами параллельными координатным осям. Допустим, у нас по коридору бежит толпа орков. Прежде чем проверять луч на пересечение с треугольниками одного орка - проверим: а пересекает ли он контейнер, содержащий этого орка? Если пересекает, то да, проверяем треугольники этого орка. Если нет, - не проверяем. Это нам дает приличную оптимизацию: бОльшая часть экранных лучей контейнер не пересекает и мы сэкономили на них кучу вычислений. 

Однако мы по прежнему потратим много времени напрасно, когда луч пересекает контейнер. Уважающие себя орки состоят из десятков тысяч треугольников, и все это добро придется обсчитывать. Поэтому идею с контейнером надо довести до совершенства. Разобъем наш контейнер с орком на две половинки: одна содержит одну половину орка (лучшую), другая - оставшуюся. Если луч наткнулся на контейнер, то мы проверим два отдельных подконтейнера. Если мы наткнулись на какую-то из половинок, то проверим четвертинки. И так далее: будем резать нашего орка в контейнере по заветам Больцано, пока не дойдем до отдельных атомов, ой, то есть треугольников. Получаем бинарное дерево из контейнеров: если его высота h, то оно имеет 2^h листьев, и это число примерно сравнимо с числом треугольников n. Для проверки на пересечение лучом нам надо пройтись по дереву и проверить порядка C*h=С*log n контейнеров, а это весьма приятнее чем n, которое было изначально.

Ура, мы придумали идею, которая называется Bounding Volume Hierarchy (BVH). Но конкретная реализация пока не очень хороша вот по какой причине. Треугольная поверхность орка 2-мерная, а больцановское подразбиение работает с 3-мерным пространством. Поэтому большинство кирпичиков, на которые мы нарезали орка, никаких треугольников вообще не содержит. Но луч многие из них все равно пересечет. Поэтому мы в нашем дереве будем ходить не по одной ветке, а по целой куче, и никакого логарифма от числа треугольников на практике не получится.

Наше все. Сперто из презентации (любой) NVidia

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

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

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

Те, кто понимает, что наука об устойчивых гомологиях в размерности 0 решает задачу иерархической кластеризации в произвольном конечном метрическом пространстве, могут в этом месте начать придумывать, как бы продать эту мысль компании Nvidia. Но у меня есть скепсис на этот счет: даже с крутыми tda-шными свистелками скорее всего устойчивые гомологии будут слишком долго считаться. И на gpu вряд ли параллелятся. И дерево там вряд ли получится сбалансированное: не забываем, что наша цель логарифм. Так что тут прямо реально постараться придется.

3d-шники, однако, придумали весьма экстравагантный подход к задаче иерархической кластеризации, - я такого в статьях по анализу данных не встречал. Прежде чем вдаваться в детали, опишу математическую философию, которую я за ним вижу.

Допустим, что облако точек D, которое надо иерархически кластеризовать, сэмплируется из некоторого метрического пространства X. В нашем случае это R^3 с евклидовой метрикой (ну или с чебышевской, если вам хочется, чтобы это лучше согласовывалось с контейнерами-кирпичами и быстрее считалось). Можем даже считать, что все точки лежат в единичном кубе X=[0,1]^3 со стандартной метрикой. Сделаем такой фокус: подберем метрическое пространство Y и отображение f:Y-->X так чтобы выполнялись условия

(1) f сюръективное и липшицево (ну или хотя бы равномерно непрерывное).

(2) задача кластеризации в пространстве Y решается быстро и просто.

Тогда вы можете сделать следующий финт ушами. 

- Поднимаете датасет D до датасета D' в пространстве Y. 

- Кластеризуете D' в пространстве Y. 

- Переносите кластеризацию на исходный датасет. 

- Вы великолепны!

Свойство липшицевости гарантирует что любой скученный кластер в Y отображается в скученный кластер в X, поэтому то, что мы получили, - это действительно решение исходной задачи, ну плюс-минус.

Осталось разобраться с таинственной фразой "задача кластеризации в пространстве Y решается быстро". Что это за пространства такие? Тезис: это пространства со старой доброй ультраметрикой. Например, множество Кантора подойдет. 

Ультраметрические пространства сами по себе представляют из себя иерархическую структуру. Посмотрите на множество Кантора или канторову пыль: там довольно очевидно, что такое кластеры. Для произвольных ультраметрик есть свойство: если два шара пересекаются, то один лежит внутри другого. Это нас избавляет от ненужных переживаний по поводу (не)транзитивности отношения близости: в ультраметрическом пространстве если x близко к y, а y близко к z, то то x близко к z. В евклиде такое, конечно, не работает, из-за этого теория пространств толерантности - это действительно теория, а не хрен собачий.

Итак, мы понимаем, что надо делать. Накроем отрезок [0,1] множеством Кантора - прямо как в предыдущей заметке, только чуть аккуратнее. Рассмотрим канторовское множество C. Для нас сейчас это множество битовых строчек x=0.x1x2x3... (на практике конечной длины, но теоретически можно и бесконечных). Введем на нем 2-адическую метрику d(x,y) = 2^{-L}, где L - длина максимального общего префикса строчек x и y. Рассмотрим отображение g:C-->[0,1], которое отправляет строчку x в нее же, но рассматриваемую как вещественное число в бесконечной двоичной записи. Отображение g, как нетрудно видеть, не увеличивает расстояния (хотя может сильно сжимать, например, строчки 0.0(1) и 0.1(0) далеки друг от друга в 2-адической метрике, но склеиваются в одно и то же вещественное число). 

Для нашей 3d-задачи, стало быть, подойдет отображение f=g^3: C^3 --> [0,1]^3. Мы просто координаты точек нашего орка интерпретируем в 2-адической метрике, и кластеризовать будем именно в этой метрике.

Теперь как это работает на практике. Тут уже пойдет пересказ с использованием слов, более близких к оригинальным работам. Суть в том, чтобы развернуть наше 3-мерное орочье облако точек на прямую. Лю Цысинь оценил бы. 

Никаких ненужных ассоциаций не предполагалось

Рассмотрим заполняющую пространство кривую, а именно Z-кривую (aka кривая Мортона) h:[0,1]-->[0,1]^3. Она определяется так: 

h(0.x1x2x3...)=(0.x1x4x7..., 0.x2x5x8..., 0.x3x6x9...). 

Расселили, короче, постояльцев отеля Гильберта по трем отелям. Тут есть некая беда с точками вида 0.A0(1)=0.A1(0): точка одна, а последовательности разные. Из-за этой беды кривая получается разрывной, но вы это и на картинке можете увидеть. Но важно, что мы можем сделать обратное построение: точку

(x,y,z) = (0.x1x2..., 0.y1y2..., 0.z1z2...)  

из 3-мерного куба свернуть в одно число 0.x1y1z1x2y2z2... Уплотнили постояльцев трех отелей Гильберта в один отель. Такой способ кодирования трех вещественных каналов в один канал называется кодом Мортона. Это довольно известная вещь, используется в том числе для кодирования адресов в базах данных; да и вообще каждый раз, когда физическая размерность памяти меньше, чем размерность данных, которые вы в нее пытаетесь запихнуть.

На практике у нас все вещественные координаты - это конечные двоичные дроби, поэтому код Мортона каждой точки орка - это конечная битовая строка какой-то фиксированной длины, например, 60 бит. Имея конечный набор битовых строчек, можно построить сжатое префиксное дерево (оно же radix tree, оно же Patricia trie). Вот оно и объявляется искомой иерархической кластеризацией для точек орка. 

Префиксное дерево, спертое из статьи Карраса

Итак что мы по сути сделали? Мы посмотрели на кривую Мортона как на отображение не из отрезка, а из множества Кантора h:C-->[0,1]^3. Оно мало того что непрерывное (тут нет проблемы с 0.A0(1) и 0.A1(0), это уже разные точки), так еще и липшицево. То есть мы реально наш датасет поднимаем на множество Кантора, ну а ноды префиксного дерева - это и есть кластеры на множестве Кантора.  

Если у вас все написанное до сих пор не сложилось в голове воедино, попробуйте решить такое упражнение по элементарной топологии. Докажите, что декартов куб множества Кантора гомеоморфен множеству Кантора. То есть вообще-то не важно, поднимаете ли вы ваш датасет в трехмерное 2-адическое пространство (покоординатно) или в одномерное. Так что эта история про разворачивание 3-мерного пространства на 1-мерную прямую к сути происходящих феноменов отношения реально не имеет: ваша цель - бинарное дерево, а дерево - это нечто 2-адическое, а в адическом пространстве размерности вообще нет. Однако 3d-шники любят везде затирать про упорядочивание объектов вдоль заполняющей кривой. Не ну а чё, звучит фантастично. 

А если же написанное все-таки сложилось воедино, то вы имеете полное право мне сказать: "Ба, так очевидно, иерархическая кластеризация - это дерево, а дерево - это ультраметрика, поэтому решить задачу иерархической кластеризации - это и означает удачно подменить заданную метрику ультраметрикой. Так что весь написанный выше текст - это пересыпание слов из миски теор.информатики в миску топологии". Окей, математики обычно тем и занимаются, что сводят содержательные утверждения к банальным тавтологиям. Таков путь.

Вообще говоря, в алгоритме с префиксным деревом тоже нет гарантии, что результат получится сбалансированным. Его еще надо бы оптимизировать, и для этого тоже куча классных идей используется. Важно, однако, что вычисление префиксного дерева от кодов Мортона можно параллелить на видеокарте. Есть такой крутой чувак Теро Каррас, он лет 10 назад очень активно писал статьи на эту тему, см. например https://research.nvidia.com/publication/2012-06_maximizing-parallelism-construction-bvhs-octrees-and-k-d-trees У меня такое впечатление, что текущие успехи Nvidia на ниве рэйтрейсинга во многом основаны на его наработках, - хотя, конечно, понять, какие конкретно алгоритмы там гоняются, нам не дано. Есть открытые презентации, например https://www.anandtech.com/show/13282/nvidia-turing-architecture-deep-dive/5 из которых ясно, что BVH - это действительно ключевая для них тема, их RT-ядра специально заточены именно на работу с иерархией объемов. Если объект в сцене движется, то перестраивать иерархию для него в каждом кадре надо заново: отсюда и возникают очень высокие требования к производительности. Удивительно, однако, что эта байда в итоге заработала!

Даже несмотря на всё написанное, пускать в реальном времени луч для каждого пикселя люди пока не умеют. Пускают только часть лучей, а остальное достраивают с помощью нейросеток. Инференс нейросетки - это умножение матриц, и вот для последнего в RTX-карты насыпали тензорных ядер, которые до этого в игрушках были особо не нужны. Подробности про нейронки я не изучал, однако сомневаюсь, что там что-то геометрически интересное происходит. Если кто-то в теме, change my mind. 

Чего по итогу. Рэйтрейсинг - математически интересная тема, и замечательно, что ее стали раскручивать маркетологи. Нужен ли реально этот рейтрейсинг в тех играх, где он есть сейчас, - ну как-то хз. Технология есть, хорошие примеры использования (в смысле лучше чем "зацените нашу мокрую лужу, и черную темноту") пока не созрели. Вот на Portal 3, где фокусы со светом были бы инкорпорированы в игровую механику, я бы посмотрел. Жаль, что игра с таким названием и номером никогда не выйдет.

таксебемысль 29 про топологические аспекты цифровой демократии

Сегодня расскажу о том, где в блокчейне сидит топология. Заодно будет какая-то база про эту самую топологию, про этот самый блокчейн и разные смежные сюжеты и мысли. Это дофига длинный текст, наверное, самый длинный из всех, что были под этим тегом. Традиционно без картинок. Возможно, я заморочусь и подготовлю блог-версию с картинками когда-нибудь позже.

Содержание

1.1. Консенсус и топология (про честное деление платы за квартиру и лемму Кнастера-Куратовского-Мазуркевича).

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

2.1. Блокчейн (общее введение в тему, независимое от первых двух историй).

2.2. Форки и прочее (поговорим где в крипте топология и что общего у крипты с квантовыми системами).

Вероятно, п.2.1 и 2.2 имеют самостоятельную ценность. Если вам нужен текст, где объясняется механика блокчейна с умеренным количеством технических деталей - то это именно он. Надеюсь, будет понятно, по крайней мере людям с каким-то математическим бэкграундом. Я старался обойтись без стандартных для этой темы восторженных соплей, путающих аналогий, притягивания всякого нерелевантного модного говна (вроде метаверсов, свят-свят!), и переворачивания всей этой темы с ног на голову. Про то, как пользоваться криптобиржами, покупать за битки кофеёк, и не злить государство, где вы живете, - тут тоже ничего не будет, потому что такое сейчас много где хорошо написано. Только математика, только хардкор. 

Итак, поехали!

1.1. Есть консенсус и топология.

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

Лемма (или теорема, чего уж) ККМ. Пусть симплекс ∆ на n вершинах покрыт n замкнутыми множествами A1,...,An, так что i-ая гипергрань симплекса не пересекается с Ai, при всех i. Тогда у множеств Ai непустое пересечение.

Предпосылку можно ослабить, можете в вики посмотреть общую формулировку https://en.wikipedia.org/wiki/Knaster–Kuratowski–Mazurkiewicz_lemma и понять, почему теорема выше оттуда следует. Верна также версия теоремы, в которой все Ai одновременно открытые, см. L.Zhou, A Theorem on Open Coverings of a Simplex and Scarf's Core Existence Theorem through Brouwer's Fixed Point Theorem, Economic Theory 4:3. Можете оценить название журнала, где опубликована топологическая статья. В ней, на самом деле, доказана более общая теорема К-К-М-Шепли, которая особо нужна экономистам, но нам в текущем контексте - не особо.

Пример, как это можно использовать на практике, - задача о справедливом делении арендной платы между студентам, - был описан в The New York Times в 2014 году https://www.nytimes.com/2014/04/29/science/to-divide-the-rent-start-with-a-triangle.html Возможно, это единственная статья в Таймс, как-то связанная с топологией. То есть история, безусловно, довольно знаменательная. С меня, честно говоря, журнал просит подписку, если с вас тоже, - то вам придется поверить моему приблизительному пересказу, который является, в свою очередь, пересказом части лекции Олега Мусина на нашей позапрошлогодней школе.

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

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

Формализуем нашу задачу. Рассмотрим все возможные способы разделить оплату. Если i-й студент вносит xi, то имеем xi≥0 и ∑xi=1. Это стандартное уравнение симплекса ∆. Давайте обозначим за Bi множество всех способов оплаты, которые устраивают i-го студента. Введем три ограничения

1) Все Bi открыты в топологии симплекса. Ну это какое-то техническое условие, но в целом звучит разумно: если способ оплаты устраивает студента, то достаточно маленькое изменение этого способа тоже сгодится.

2) Bi покрывают симплекс. То есть любой способ оплаты хотя бы одному студенту нравится. С чисто человеческой точки зрения это довольно сильное условие: мало ли какие там тараканы у людей в голове бывают. Но математически мы его все же потребуем, без него, понятно, науки не построишь.

3) i-ая грань симплекса лежит в множестве Bi. Это как раз с человеческой точки самое естественное условие. Заметим, что i-ая грань симплекса - это как раз те способы оплаты, при которых i-й студент платит xi=0 (ноль рублей ноль копеек). Еще бы бедного студиозуса такое не устраивало!

И вот этих предпосылок достаточно для существования точки xi, которая принадлежит всем Bi. То есть существует способ оплаты, который удовлетворяет всех студентов. 

Доказательство. Допустим противное, пусть ⋂Bi=∅. Перейдем от множеств Bi к их дополнениям Ai=∆\Bi, они замкнуты. Противное допущение по правилам де Моргана влечет, что Ai покрывают симплекс. Раз уж Bi содержит i-ую грань, то Ai ее не пересекает. Мы находимся в условиях Теоремы К-К-М: значит пересечение Ai непусто. Но это противоречит тому, что Bi покрывают симплекс, - опять же по правилам де Моргана.

Для того, чтобы алгоритмически построить точку консенсуса, нужно достаточно мелко триангулировать наш симплекс состояний и жахнуть лемму Шпернера. Это такая дискретная версия ККМ-теоремы, которая используется и в доказательстве ККМ, и, если надо, напрямую в де Морган-двойственном утверждении про студентов. Таймс дает возможность поиграться с этим делом https://www.nytimes.com/interactive/2014/science/rent-division-calculator.html Вдруг вам с соседями и впрямь надо прийти к консенсусу, теперь вы знаете, куда обращаться.

Вообще надо отметить, что лемма ККМ, помимо того что решает проблемы студентов с арендной платой, используется и во всяких фундаментальных вещах. В книге П.С.Александрова "Комбинаторная топология", например, она используется для доказательства того факта, что n-мерный симплекс имеет размерность n. Топологов старой закалки подобные вещи довольно сильно волновали. 

Описанная история про справедливое деление, а также всякие там результаты Нэша, о которых вы не могли не слышать, создает впечатление, что в экономике все всегда радужно: все договариваются, деньги в карман засовывают, в губы целуют, предлагают породниться. Это, однако, не всегда так: как минимум в одной области есть конкретная математическая теорема об отсутствии консенсуса. Эта область - по существу, наука про протоколы в распределенных системах, а по сути, - что-то на стыке теор.информатики, логики, мат.экономики и топологии, местами комбинаторной, а местами - общей (sic!). Звучит достаточно киберпанково, чтобы попытаться это заботать.

1.2. Нет консенсуса и топология.

Чтобы не тянуть, начнем с ссылок. Я хочу рассказать о работе

M.Saks, F.Zaharoglou, Wait-free k-set agreement is impossible: the topology of public knowledge. SIAM J Comput 29:5 (2000).

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

M.Herlihy, D.Kozlov, S.Rajsbaum, Distributed Computing Through Combinatorial Topology, 2013.

Хотя я не то, чтобы все прочитал и осмыслил. Обсуждать мы будем такие утверждения.

Теорема 1 (слабая, Херлихи). В асинхронной мультипроцессорной системе с общей памятью невозможен сильный консенсус.

Теорема 2 (сильная, Сакс-Захароглу). В асинхронной мультипроцессорной системе с общей памятью невозможен слабый консенсус.

Поймем смысл всех слов из формулировки. 

Мультипроцессорная система с общей памятью.

Допустим, у нас есть n компьютеров, и есть общая память, разбитая на n кусков, называемых регистрами. Каждый регистр принадлежит своему компьютеру. Любой компьютер может читать все, что написано во всех регистрах, а писать - только в свой регистр. Писать в свои регистры компьютеры могут одновременно. Но ни один компьютер не знает, пишет ли в этот момент другой компьютер. В некотором роде, акт записи - это одномоментный акт, если момент совпал для нескольких компьютеров, то они о таком совпадении не знают. Будем считать для простоты модели, что у каждого компьютера акты чтения и записи чередуются. Пишет-читает-пишет-читает-... Будем также считать, что любая запись в регистр - это элементы какого-то множества, допустим, просто натуральные числа, и каждый раз, когда компьютер пишет, - он реально что-то пишет. То есть нельзя притвориться шлангом и скипнуть ход. Мне это кажется существенным условием, но авторы утверждают, что их модель в смысле доказываемых утверждений не слабее чем любая другая разумная модель вычислений с общей памятью. Поверим им на слово. 

Асинхронная...

Это означает, что в компьютерах нет синхронизированных часов. Поэтому при написании программ нельзя использовать условия в духе "в 00:13:47 записать в регистр максимум из уже записанных чисел" или "написать в регистр '1', ждать 10 секунд, проверить, что другие написали". Это выглядит довольно надуманным ограничением: ну у кого в компьютере нет часов? Но на практике это не так уж тупо. Имеется в виду следующее. Считайте, что у вас компы находятся по всему земному шару, но обращаются к одной памяти. Даже если комп думает, что сделал запись в 00:13:47, - далеко не факт, что до памяти эта информация дойдет именно в такое время. Конечность скорости света и задержки при пересылке пакетов никто не отменял. Ну и бывают в сети непредсказуемые обстоятельства непреодолимой силы, вроде Роскомнадзора или "грозой провода оборвало".

Консенсус.

Поставим нашей асинхронной системе такую задачу. Сообщим втайне каждому процессору какое-нибудь натуральное число, пусть p-й процессор получил на вход число xp. Скажем, что система пришла к сильному консенсусу за t шагов, если на t-м шаге в регистре каждого компьютера записано одно и то же число x - и это одно из чисел x1,...,xn. Короче говоря, компам надо проголосовать за одно из входных чисел, прийти к консенсусу. Можно пользоваться общей памятью, нельзя - часами. 

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

Теперь что такое слабый консенсус. Это когда на t-м шаге в каждом регистре k записано какое-то число yk с условиями: (1) каждое yk - это какое-то из входных значений xp (не обязательно с тем же номером), (2) среди yk есть хотя бы два повторящихся. То есть это когда хотя бы два компьютера смогли договориться, грубо говоря. 

Ну и так вот теоремы про то, что не смогут они договориться ни в сильном смысле, ни в слабом смысле. 

Представьте, что вы с друзьями в чатике пытаетесь решить, куда и когда пойти бухать. Каждый строчит по 10 сообщений в минуту, сообщения от разных людей выскакивают в неправильной последовательности, какой-нибудь чёрт кидает смайлики, а другой - голосовые. Вы пытаетесь одновременно понять то, что вам скинули, и написать на основании этого рациональный вариант, но его обгоняет чужое рац.предложение. Жиза? Не договорились? То-то же. Даже полностью рациональные компьютеры не могут.

Слабая теорема про невозможность сильного консенсуса - вроде бы без топологии доказывается. А сильная про невозможность слабого консенсуса - это про топологию. 

Чтобы как-то подступиться к доказательству, наложим чуть больше формализьму на описанный сеттинг. Во-первых, избавимся от непрервыного времени: будем считать, что все акты чтения-записи происходят в моменты времени 1,2,3,... Во-вторых, будем считать, что наши компы работают до бесконечности, и регистры тоже бесконечно большие. В-третьих, для удобства будем воспринимать эту историю про подбор консенсуса как соревнование двух неравноценных игроков. 

Первый игрок, Система - это наша мультипроцессорная система, она пытается решить задачу консенсуса. Второй игрок, назовем его Хроносом, - это оппонент. Он пытается сделать так, чтобы у Системы не получилось. Какая свобода действий дана Хроносу? Он может на свое усмотрение в каждый момент времени допускать или не допускать каждый компьютер до работы с регистром. Обозначим через σj⊆[n] множество компьютеров, допущенных в j-й момент к работе с регистром, будем считать, что это множество всегда непусто. Таким образом Хронос властен над последовательностью подмножеств σ={σ1,σ2,σ3,...}, которая называется расписанием. А во власти Системы - загрузить заранее на каждый компьютер детерминированный алгоритм. Совокупность этих алгоритмов называется протоколом, назовем его П. Имея протокол П и расписание σ, независимый наблюдатель может написать состояние всех регистров до бесконечности. Это называется публичной записью, обозначим ее R(П,σ). 

Надо подчеркнуть, что каждый раз, когда компьютер допущен до работы с регистром, он пишет в следующую свободную ячейку своего регистра. То есть у компьютера нет информации о том, на каком временном шаге он сейчас находится - в этом смысл асинхронности. И наконец мы хотим избавиться от привязки к конкретному номеру шага, на котором компьютеры Системы должны выдать ответ. Если система хочет указать, что значение ans и есть ответ (а не просто очередная запись в регистре), то пусть она запишет "My answer is: "+ans. В статье предлагают более короткую запись "@."+ans. Таких ответов можно писать сколь угодно много, но учитываться будет только самый первый, появившийся в регистре.

Коль скоро мы все это поняли, то теоремы, написанные выше, можно переформулировать таким образом:

Каким бы ни был протокол Системы, Хронос может подобрать такое расписание, при котором Система не придет к слабому консенсусу.

А в доказательстве начинается магия. Рассмотрим множество Σ всех возможных расписаний (напомню, что расписание - это последовательность из подмножеств процессоров). Это какое-то дикое континуальное множество, естественно. На нем можно, однако, естественным образом ввести топологию, которая называется канторовской. Базу этой топологии образуют подмножества расписаний, имеющих общий префикс. В общем, это буквально p-адическая топология, если вы знаете, что это такое. При p=2 получилось бы канторово множество, ну а на нашем Σ в качестве p по сути берется 2^n-1.

Дальше нам надо провести некоторые отождествления. Скажем, что два расписания σ и σ' неразличимы, если для любого протокола П выполнено R(П,σ)=R(П,σ'). То есть по публичным записям нельзя понять, какое из двух расписаний предложил Хронос. Получается отношение эквивалентности, легко видеть. Можно покопаться в этом немного и конструктивно описать полный набор операций, который позволяет получить из расписания все эквивалентные ему, их оказывается лишь конечное число. Рассмотрим пространство Σ^ = Σ/~ с естественной фактортопологией. Точки этого пространства называются сжатыми расписаниями.

Для фиксированного протокола П и ответа d, рассмотрим множество A(П,d) всех сжатых расписаний σ, для которых публичная запись R(П,σ) содержит ответ d хотя бы в одном из регистров. Назовем подмножество A⊆Σ^ познавающим, если оно имеет вид  A(П,d) для некоторого протокола П и ответа d. Теперь два мозговыносящих факта:

I. Познающие множества образуют топологию на Σ^.

II. Эта топология совпадает с фактортопологией, введенной раньше.

И идея статьи Сакса-Захароглу в том, что пространство Σ^ - это что-то типа симплекса на n вершинах, только он какой-то такой частично p-адический. И для него выполнен аналог теоремы Кнастера-Куратовского-Мазуркевича. 

 

Я тут вижу такую картинку: она, кажется, с историей про процессоры не связана, но позволяет убедить себя в разумности происходящего. 

Возьмем 2-адическую топологию - это стандартное множество Кантора. Точки этого пространства можно отождествить с вещественными числами из отрезка [0;1], у которых в троичной записи содержатся только '0' и '2'. Теперь каждое число, имеющее постфикс '0(2)' отождествим с числом, полученным заменой постфикса на '2(0)'. В каждом классе эквивалентности оказалось лишь конечное число точек. Если перейти к факторпространству, то получится обычный отрезок: потому что ну реально двойки можно мысленно заменить на единицы, и получится представление чисел в виде бесконечных двоичных дробей со стандартными правилами отождествления. Так мы из канторова множества получили вполне разумный отрезок.

Вернемся к тезису о том, что Σ^ - это типа симплекс. Назовем i-й гипергранью множества Σ^ совокупность всех (сжатых) расписаний, в которых вообще не участвует i-й процессор. 

Теорема ККМ для асинхронных систем. Пусть множество Σ^ покрыто познающими множествами A1,...,An, и пусть Ai не пересекает i-ую гипергрань пространства Σ^. Тогда множества Ai имеют непустое пересечение.

Доказательство - что-то типа аналога леммы Шпернера, только там уже не триангуляции используются, а какая-то эзотеричная комбитопологическая трава. За сим прошу в оригинальную статью. 

Нам важно применить эту теорему к доказательству невозможности слабого консенсуса. От противного: допустим, что есть протокол П, который решает задачу слабого консенсуса. В частности, он сможет решить задачу и при условии, что 1-му процессору загадали число 1, 2-му - число 2, и т.д. Рассмотрим множество Di, состоящее из всех сжатых расписаний σ, для которых в публичной записи R(П,σ) хотя бы один процессор принял решение i. Имеем:

I. По построению все Di познающие, то есть открыты.

II. Множества Di покрывают Σ^. Какое бы дурацкое расписание не предложил Хронос, хотя бы один компьютер к какому-то решению да приходит, так что это почти тавтология.

III. Di не пересекает i-ую гипергрань пространства Σ^. Это тоже почти очевидно. Пусть это не так, для определенности i=1: тогда есть расписание, в котором не задействован первый процессор, и в результате выполнения которого кто-то дал ответ 1. Но мы могли бы устроить подставу: загадать первому процессору в самом начале вместо 1 слово 'Попався!'. Никто бы об этом не узнал, потому что 1-й комп не допускают до регистра. Но ответ ответ 1, который дал кто-то в Системе, уже будет неверным, потому что в списке загаданных значений ['Попався!',2,3,..,n] значения 1 уже нет.

Итого мы в позиции применить теорему ККМ к множествам D1,...,Dn. Теорема гласит, что они пересекаются. Значит есть расписание σ при котором какой-то из n компьютеров дает ответ 1, какой-то дает ответ 2, ..., какой-то дает ответ n. Среди этих ответов нет повторов, значит на таком расписании слабый консенсус не достигается. 

Хронос победил. Ура, с матчастью закончили.

2.1 Блокчейн

Я буду использовать биткоин в качестве примера, история про любую другую крипту аналогична или почти аналогична.

Что такое биткоин, если конкретно? 

Биткоин - это огромный текстовый файл (в настоящее время около половины терабайта), копии которого, полные или частичные, хранятся на нескольких тысячах компьютеров, связанных по P2P сети. Вот тут https://bitnodes.io/ можно посмотреть, где находятся узлы сети биткоина, включенные в настоящий момент. Этот дикий текстовый файл называется блокчейном или цепочкой. 

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

И наконец биткоин - это виртуальная монетка.

Но самое важное - правила. Конкретно для биткоина они таковы. Примерно раз в 10 минут в файл дописывается кусок текста, который называется блоком. В блоке записано некоторое количество содержательной информации, плюс какая-то абракадабра из символов, и про то и про другое ниже написано подробно. Записью новых блоков в файл занимаются компьютеры, которые называются майнерами. Майнер, которому удалось записать очередной блок в цепочку, автоматически получает награду. Сейчас награда составляет 6.25 биткоина за блок, запись об этой награде и его счастливом обладателе включена в записанный блок. Изначально награда была равна 50 биткоинов, но в правилах написано, что раз в 210000 блоков - примерно раз в 4 года, как легко посчитать, - награда должна уменьшаться вдвое. Просуммировав бесконечную геометрическую прогрессию, нехитро получаем, что всего в мире может быть максимум 21 миллион битков. Сейчас их существует чуть больше 19 миллионов. Также понятно, что лет этак через 30 автоматическая награда за блок станет весьма скромной и майнеров надо будет стимулировать другими способами.

Содержательная информация в блоке. В принципе, это может быть все, что угодно. Например, можно написать в блок слово "хуй". Зачем? Затем же, зачем оно написано в подъезде, - чтобы было. Только в подъезде его рано или поздно закрасят, а в блокчейне оно будет гарантированно храниться на нескольких тысячах компьютеров по всему миру. Пока сеть блокчейна и входящие в нее узлы физически существуют, этой информации ничего не грозит. И это, вроде как, надежнее, чем хранить информацию на сервере (или двух, или десяти серверах) какой-нибудь компании. Довольно бедная статистика показывает, что Александрийская библиотека сгорает чаще, чем глобальная информационная сеть. Поэтому, типа, считается, что блокчейн - это полезная технология даже и вне привязки к виртуальным деньгам. Хотя тут можно поспорить: никто не будет долго хранить всякую фигню, если в этом нет финансовой выгоды. 

А вообще, если вы прониклись возможностью высечь что-то неприличное в анналах истории, то вы уже почти поняли, что такое NFT-токены. Это тот же "хуй", только с цифровой подписью автора и возможностью приписывать ему владельца и перепродавать. 

Говоря про биткоин, бОльшая часть содержательной информации в блоке - это лог транзакций монеток. Что-то в духе "Петя послал Маше 0.378478272 биткоина, Катя послала Васе 0.000232329 биткоина,...". Только вместо имен - обновляемые коды кошельков. И на все это навешивается некоторое количество криптографии (в случае битка - криптографии на эллиптических кривых) с приватными и публичными ключами. Тут криптография позволяет подтвердить, что Петя послал именно Маше, так сказать, в здравом уме и твердой памяти. Защита нужна, чтобы какой-нибудь условный Ваня не смог написать в блок "Петя послал Ване мильон битков", и поиметь нечестный гешефт. Но эти методы защиты довольно стандартные для банковских переводов, особого крипто-ноу-хау в этой части истории нет, потому и останавливаться на этом мы не будем. 

Важный take-home message предыдущего абзаца, однако, в том, что все ваши транзакции биткоинов абсолютно прозрачны - если известны коды, генерируемые вашим кошельком. Любой человек может открыть блокчейн, поискать в нем нужные коды, и найти всю историю ваших переводов, а по истории восстановить сколько битков у вас на балансе. Вот тут https://www.blockchain.com/explorer/blocks/btc можете посмотреть, кто кому сколько деньжищ переводит прямо сейчас (и поплакать). Анонимизация происходит на этапе "личность-коды кошелька". Но очевидно, что эта связка в одном направлении легко ломается методом паяльника в жопе, - видимо, поэтому американское правительство считает биток не самым удобным способом злодеям делать свои темные дела. Как бы в обычных банках метод паяльника работает точно так же, но банк информацию о транзакциях шифрует, - с банком еще по судам тягаться придется. А битки довольно прозрачные по построению. Поэтому, вроде как, их и не запрещают. 

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

В борьбе со спамом помимо "высокотехнологичных" методов вроде байесовских фильтров (благодаря противодействию которым со стороны спамеров, в нулевых годах мы частенько получали весьма сюрреалистичные послания) и более современных распознавателей, используется одна железобетонная технология: hashcash. Смысл последней в том, чтобы сделать отправку большого числа бестолковых писем экономически нецелесообразной. Если заставить отправителя письма делать при отправке некую работу гарантированной сложности, например, занимающую гигагерцевый процессор на 1 секунду, - то обычный юзер ничего не заметит, а у спамера, отправляющего 1000 писем, комп повиснет на 1000 секунд.

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

Хэш-функция - это детерминированная булева функция f, которая принимает на вход битовую строчку произвольной длины, а выдает битовую строчку фиксированной длины, скажем 256 бит. Результат, значение функции, называется хэш-суммой. Эквивалентно, можно считать, что хэш-сумма - это целое число от 0 до 2^256-1, записанное в двоичной системе. С одной стороны, хэш-функция должна быть достаточно хаотичная в том смысле, что для фиксированного значения y вы ничего не можете сказать об x с условием f(x)=y, т.е. зная хэш-сумму, невозможно ни угадать от чего она была посчитана, ни предсказать какие-либо свойства входа. С другой стороны, хэш-функция должна "сохранять меру" в том смысле, что посылая на вход строчки из равномерного распределения (если длину входа зафиксировать), мы получим равномерное же распределение хэш-сумм, ну примерно. И наконец, однократное вычисление хэш-функции должно быть шустрым. 

Короче говоря, хэш - это такой аналог арнольдовской окрошки из кошки, только необратимый и нелинейный. Пример хэша (который сидит в биткоине) - SHA-256, можете почитать, как она определяется, тут https://blog.boot.dev/cryptography/how-sha-2-works-step-by-step-sha-256/ . Весьма медитативное чтиво, скажу я вам. 

Итак, что происходит, когда вы отправляете электронное письмо? Ваш почтовый клиент берет из письма какую-то мета-информацию: адрес отправителя, дату и время отправки, пакует это в булеву строчку, - и приписывает к ней абракадабру: некоторое количество случайных битов. И после этого вычисляет от полученной строчки хэш-сумму. Если хэш-сумма начинается с 20 нулей, то это считается победой. В этом случае письмо вместе с абракадаброй отправляется на сервер. Если получить 20 нулей не получилось, то увеличиваем абракадабру на единицу, снова считаем хэш, и смотрим, получилось ли 20 нулей. И так далее - инкрементируем абракадабру, считаем хэш, - делаем, пока не получим в результате 20 нулей. Из-за свойства сохранения меры вероятность получить 20 нулей за один подсчет равна 1/2^20. Поэтому в среднем, чтобы получить результат с 20 нулями, нужно вычислить хэш-функцию 2^20 раз, примерно миллион.

Что происходит на сервере? Сервер получает письмо плюс строчку "метаинформация"+"абракадабра". Сервер проверяет, что метаинформация соответствует письму, и вычисляет хэш от строчки. Если сервер видит в начале хэш-суммы 20 нулей, - то для него это подтверждение того, что клиент проделал вычисление хэша ~2^20 раз. Тогда все ок, письмо летит дальше куда надо. Но если сервер проверяет хэш-сумму, и не видит 20 нулей, то письмо удаляется. Ну там есть еще такая техническая заморочка, что строка "метаинформация"+"абракадабра" должна быть уникальной, все дубли автоматически стираются. Это вынуждает клиента выбирать начальное значение абракадабры каждый раз заново, - даже если метаинформация в наборе писем одна и та же.

Таким образом получается железобетонная гарантия, что каждое успешно доставленное письмо съело у отправителя контролируемо-случайное число процессорных тактов. Описанная концепция называется Proof-of-Work (PoW) и ровно на ней основан майнинг крипты. Такая вот шокирующая новость для людей, которые считают майнеров гнидами, просирающими электричество на бессмысленные операции. Все мы немного майнеры, когда пользуемся электронной почтой, или когда строчим комменты в бложеки. В блогах тоже используется hashcash, только там он нужен для защиты от DDoS-атак, принцип немного модифицирован. Это тот же спам по существу, только с другими целями.

Возвращаемся к биткоину. Как было написано выше, раз в 10 минут кто-то из майнеров должен приписать к блокчейну биткоина новый блок. Как это происходит с точки зрения майнера? В сети биткоина разбросана куча коротких текстов, вроде: "Петя послал Маше 0.378478272 биткоина", "хуй", ссылки на какую-нибудь запрещенку, результаты муниципальных выборов (заранее заботливо подтасованные, например). Эти сообщения накопились за последние 10 минут. Майнер делает следующее:

(*) Быстро тралит всю эту рыбешку, проверяет правильность транзакций, и сбивает их в блок. Причем, если информации оказалось слишком много, то майнер отдает предпочтение тем сообщениям, в которых ему пообещают наибольший откат. Откат официально называется комиссией. Рыночек, все дела. Не пообещаешь комиссию при переводе - рискуешь долго ждать своей очереди.

(*) Далее майнер, допустим его зовут Вова, записывает в блок что-то в духе "Вова<тут стоит код его кошелька> создал этот блок, и получил в награду 6.25 биткоина из великой пустоты небытия". Вот этот вот вброс новой деньги в рынок называется минт, ковка. Через сто лет, когда минт не будет приносить профит, майнеры будут зарабатывать чисто на комиссиях за переводы.

(*) Вова дописывает в свой конструируемый блок хэш от последнего блока, висящего в блокчейне. Этим он как бы чтит историю, обеспечивая связность блокчейна. Если какой-нибудь редиска захотел бы поменять информацию в блоке, появившемся 5 лет назад, то ему пришлось бы переписать и все последующие блоки, потому что они все последовательно связаны через хэши. А это астрономически сложная работа, - поэтому никому не выгодно менять старые блоки.

(*) Наконец, Вова приписывает к блоку абракадабру. Начальное значение абракадабры по научному называется nonce (это латиницей, если что). 

Теперь Вова расчехляет свою RTX-4090, или что там у него, и начинает яростно считать на ней хэш-функцию от всего вышеперечисленного, - пока результат не будет начинаться на чертову уйму нулей. Сейчас, кажется, надо 77 нулей, но вообще это число со временем растет. То есть Вова считает хэш, если не получилось, то инкрементирует абракадабру, снова считает, и так далее. Все эти вычисления очевидным образом параллелятся, а потому хорошо ложатся на GPU. То есть успех настигнет Вову, если он посчитает хэш 2^77 раз, ну в среднем. Это число прямо дохрена больше, чем 2^20. Но так и получить 6.25 биткоина - это вам не котика запостить, за такие деньги можно однушку у МКАДа купить. Если бы в России это было разрешено, хе-хе.

В истории выше замято под ковер некоторое количество технических фактов. Например, в хэш-сумме важно не количество нулей, а чтобы она была меньше наперед заданного числа. Это позволяет регулировать сложность плавно: если бы мы смотрели только на число нулей, то его корректировка усложняла бы задачу майнеров скачкообразно в два раза: было бы трудно добиться, чтобы на генерацию блока уходило 10 минут. А еще информация о транзакциях внутри блока оформляется не в виде кучи, а в виде бинарного дерева с промежуточными хэшированиями. Но это просто потому что бинарное дерево более емкая структура данных. В любой непонятной ситуации используйте бинарное дерево.

Итак, что мешает Вове по описанной выше схеме получать нахаляву 6.25 биткоина раз в 10 минут? Еще примерно стопицот майнеров, которые тоже собирают блоки и подбирают абракадабру, хэш от которой начинается на 77 нулей. Кто первый получил правильный хэш, тот и записывает свой блок в цепочку, остальные работали напрасно. Вероятность того, что выиграет Вова, а не какой-нибудь китаец с фермой из тысячи специально заточенных на это вычислителей, - трындец какая маленькая. Хоть и ненулевая. 

Вова, конечно, человек рациональный, поэтому он договаривается с другими майнерами о распределенном доходе, это называется пул. Грубо говоря, в пуле состоят несколько майнеров, и если один из них срывает джек-пот, - то награда делится между участниками соразмерно мощам, которые они использовали. При выборе пула Вове, очевидно, очень пригодится знание матана и тервера: оценить, выгодно ли ему вообще в этот пул вступать. Я глубоко не копал, но вот прямо нутром чую, что пулы стригут нубов за счет каких-нибудь статистических приколов. 

В итоге, PoW в биткоине гарантирует, что блок записывается раз в 10 минут. И одновременно гарантирует, что майнер не налажает в записи блока. Потому что, если налажал, то это быстро вскроется другими участниками сети - валидаторами, и блок банят, - выходит, что майнер работал напрасно.

Если задуматься, то это все очень похоже на механики ЛМШовых игрушек: если тебе надо занять ребенка на станции на 5-10 минут и дать ему по итогу какую-нибудь ачивку - заставляешь его собирать самолетики, распрямлять фольгу, или факторизовать трехзначные числа. Это немного тупо, конечно, - в продуманных игрушках должны быть более изящные протоколы. 

Так и криптовалюты бывают разные. Вот эфир недавно переключился с PoW на PoS: Proof-of-Stake (*на самом деле, форкнулся). В этом протоколе блок записывает не самый везучий майнер, а, грубо говоря, участник сети, поставивший на кон больше всего валюты - и рискующий ее потерять, если налажает или попытается смухлевать. Мы же помним, что информация, у кого сколько валюты, открытая: поэтому условие соответствия легко проверить. Чисто технически переписать блокчейн эфира теперь не сложно, хэши там если и есть, то слабенькие. Фишка в том, что теперь писатели блоков расписываются на них своими сбережениями: если уж ты можешь валидно переписать миллион блоков, то значит на твоих кошельках столько дохрена баблища, что ломать систему тебе вроде бы и невыгодно. Ну как-то так я это понимаю.

2.2 Форки и прочее

В п.1.2 мы говорили про отсутствие консенсуса в асинхронных системах, каковой, например, является P2P сеть биткоина. Косвенным образом невозможность консенсуса порождает слабое место любой крипты, основанной на блокчейне: форки. Или, говоря по-русски, вилки. 

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

а) Суровые вилки (hard forks). Это когда меняются представления игроков о прекрасном, причем меняются существенно, на уровне основных правил игры. Часть компьютеров в сети сознательно поддерживает эти изменения, а часть - нет. В итоге часть игроков продолжает играть по старым правилам, а часть - переключается на новую игру, и образует новую сеть. Такое бывает не очень часто, и иногда в результате суровой вилки рождается новая криптовалюта. 

Take away message в том, что если какая-то сеть объявляет запланированный hard fork, то вы можете вложиться в эту крипту, и тогда после вилки с какой-то вероятностью получите вместо одной коллекции фантиков - две коллекции фантиков. Принесет ли вам это счастье - вопрос уже отдельный.

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

б) Мягкие вилки (soft forks). Это когда в рамках общих правил меняются какие-то игровые частности. Например, число нулей, которые нужно сгенерить для валидного блока. Технически все узлы сети продолжают работать на тех алгоритмах, которые у них есть, и принадлежат той же сети. Но если они не подкрутят у себя нужные константы, то это быстро вскроют другие валидаторы, и метафорически закидают ретрограда шапками: то есть блок в итоге не примут, - а значит работа ретроградных майнеров/валидаторов окажется напрасной. Тут, конечно, важно, чтобы мелкие изменения принимались большей частью игроков. Содержательно мягкая вилка - это и не вилка-то вовсе.

в) Внутренние вилки. На самом деле, такого термина нет: описанный ниже феномен существует, но вилкой формально не называется. Эти вилки, на мой взгляд, самые интересные, потому что возникают из-за асинхронности, а значит отсутствия консенсуса математического, - а не социального.

Может так случиться, что Вова из России и Хелен из Австралии смайнили правильный блок почти одновременно, ну либо валидация произошла почти одновременно. Назовем такую ситуацию паритетом. У P2P сети биткоина нет никакого объективного способа выбрать победителя - об этом нам говорят топологическая теорема из п.1.2 этой заметки. Никакие суперточные timestamps для определения, кто был первым, нас не спасут, потому что timestamps можно подделать. 

Чего делать в такой ситуации? А ничего не делать. В whitepaper Сатоси Накамото (это такой Николя Бурбаки в мире крипты) написано, что надо принимать оба блока. Но в дальнейшем, все майнеры и валидаторы пользуются общим правилом: истинной цепочкой считается цепочка наибольшей длины в нашем ветвящемся дереве, и приписывать блоки нужно именно к ней. Как the elder rule в устойчивых гомологиях.

Как я понимаю, на практике это работает так. Допустим, возник паритет Вовы и Хелен. Сейчас обе цепочки - и с концом в блоке Вовы, и с концом в блоке Хелен - имеют одинаковую длину, поэтому обе считаются истинными. В следующие 10 минут каждый майнер выбирает одну из них: как мы помним, майнер использует хэш от предыдущего блока, - поэтому усидеть сразу на двух стульях он не может. Допустим, что майнер Цзинь, выигравший очередной раунд, работал с цепочкой Хелен. Теперь цепочка "предыстория-Хелен-Цзинь" стала длиннее, чем цепочка "предыстория-Вова", а значит именно она является истинной. Блок Вовы объявляют сиротой, с этим блоком теперь никто не будет работать. Система проверяет, все ли транзакции из блока Вовы были учтены в блоке Хелен. Если какие-то транзакции оказались не осуществлены, то их кидают обратно в сеть, - они будут ждать, пока следующий майнер включит их в блок.

Чем это все чревато для игроков? Во-первых, Вове должно быть чертовски обидно: в течение 10 минут он был гордым обладателем однушки у МКАДа, а потом перестал, - потому что какой-то Цзинь выбрал чужой блок. Во-вторых, такая же неопределенность возникает у обычных юзеров: если ваш перевод биткоина был в блоке Вовы, но не Хелен, то ваш получатель как бы и получил деньги и не получил одновременно - вы это не узнаете, пока не напишут следующий блок.

Такое бабло Шрёдингера в реальном мире. Пока случайный Цзинь не проведет наблюдение квантовой системы, мы не узнаем кто прав: Вова или Хелен. Поэтому, конечно, при валидации переводов надо учитывать все возможные альтернативные блоки. Вова/Хелен/ваш получатель не может тратить свое бабло, пока нет подтверждения, что оно записано в единственном истинном префиксе. Из-за этого фактически перевод биткоина может занимать больше 10 минут. Ну либо вы предложили откат достаточно аппетитный, чтобы все возможные майнеры включили вашу транзакцию в свои блоки:)

Самое веселое - риск, что паритет будет повторяться. Если вместе с Цзинем правильный блок сгенерила Ума, и если она выбрала за основу блок Вовы, то у нас получились две цепочки: "предыстория-Хелен-Цзинь" и "предыстория-Вова-Ума". Обе истинные, но не очень полезные. Больше ветвления, больше квантового бабла!

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

Но пофантазировать о математической возможности применять p-адическую теорему Кнастера-Куратовского-Мазуркевича к бесконечно ветвящемуся квантовому блокчейну на протоколе Proof-of-Useful-Work с нейросетками вместо хэшей - довольно приятное занятие для благородных умов. 

За сим кончаю, надеюсь, это было познавательно.