Математическая эссенция

Абсолютная иерархия Позволим себе небольшую фантазию. Представим мир, в котором принцип иерархии проведён абсолютно последовательно. Никаких исключений, пересечений и неформальных связей. Каждый элемент входит в одну группу, та — в одну более крупную группу, и так далее до самого верха — как в предельно строгой партийной, церковной, военной или административной иерархии. Получается дерево. Теперь определим близость двух людей исключительно их положением в этом дереве: чем ниже находится их последний общий узел, тем они ближе. Два человека из одной небольшой группы очень близки. Из разных групп одного отдела — дальше. Из разных отделов одного управления — ещё дальше. А если их ветви разошлись почти у самого корня, никакое сходство характеров, взглядов или интересов уже не может сделать их ближе. В абсолютной иерархии всё это просто не входит в определение расстояния. Такой мир естественным образом приобретает ультраметрическую геометрию. В нём невозможен обычный треугольник с тремя разными сторонами. Если A и B близки, а C принадлежит другой ветви, то d(A, C) = d(B, C). Для C различия между A и B, происходящие где-то глубоко внутри чужой ветви, вообще неразличимы. Группы становятся ультраметрическими шарами. Любые две группы либо не пересекаются, либо одна целиком вложена в другую. Более того, ультраметрический шар одновременно открыт и замкнут. Абсолютная иерархия не знает пограничной принадлежности: относительно данного уровня ты либо внутри, либо снаружи. Нет и настоящих горизонтальных связей. Близость двух элементов определяется только уровнем, на котором расходятся их ветви. Всё, что происходит ниже этого уровня, может уточнять положение внутри каждой ветви, но уже не способно изменить расстояние между ними. Поэтому различие, возникшее выше в иерархии, полностью перекрывает любые совпадения снизу. Два человека могут иметь одинаковые взгляды, привычки и интересы, но если структура развела их на высоком уровне, для этой геометрии они остаются далёкими. Здесь вообще нет привычного «накопления» сходств и различий. Решает самый высокий уровень, на котором обнаружилось расхождение. Всё предыдущее, относящееся к более низким уровням, перестаёт влиять на итог. И наоборот: принадлежность к более крупной общей группе перевешивает всю историю различий внутри неё. Если два элемента сходятся на высоком уровне, то всё, что различает их ниже, лишь уточняет их положение внутри общей ветви. Получается почти идеальный мир для бюрократии. У каждого есть своё единственное место. Каждая группа имеет строго определённые границы. Любые две группы либо вложены, либо разделены. Вся близость заранее задана деревом. К счастью, реальность устроена несколько иначе. Один человек одновременно принадлежит семье, профессии, кругу друзей, организации, культурному или профессиональному сообществу. Эти классификации пересекаются и не складываются в одно дерево. Между далёкими ветвями возникают прямые связи. Иногда именно они оказываются важнее официальной иерархии. Люди переходят из одной группы в другую, создают новые, принадлежат нескольким сразу и вообще упорно нарушают правила идеального дерева. Свобода предполагает право самому выбирать связи, менять принадлежность и не сводиться к одному назначенному месту. Абсолютная иерархия требует обратного: место и связи определяет система. Поэтому абсолютная иерархия несовместима со свободой.

Достаточно одного условия В обычном анализе необходимое условие сходимости ряда — aₙ → 0. Но его недостаточно. Например, 1 + 1/2 + 1/3 + 1/4 + … расходится, хотя его слагаемые стремятся к нулю. В p-адическом анализе всё иначе. Рассмотрим некоторый хвост ряда: aₘ₊₁ + aₘ₊₂ + … + aₙ. Из сильного неравенства треугольника следует |aₘ₊₁ + … + aₙ|ₚ ≤ max(|aₘ₊₁|ₚ, …, |aₙ|ₚ). Если aₙ → 0 в p-адической метрике, то начиная с некоторого места все |aₙ|ₚ становятся сколь угодно малыми. Но тогда сколь угодно малым становится сразу и весь хвост суммы. Значит, частичные суммы образуют последовательность, члены которой становятся сколь угодно близкими друг к другу. Поле ℚₚ устроено так, что такая последовательность имеет предел: ℚₚ полно. Поэтому в ℚₚ выполняется удивительно простое правило: Σaₙ сходится тогда и только тогда, когда aₙ → 0. Есть и другое характерное следствие ультраметрии. Если |a|ₚ ≠ |b|ₚ, то |a + b|ₚ = max(|a|ₚ, |b|ₚ). Слагаемое с меньшей нормой, конечно, не исчезает из суммы. Но оно не меняет её p-адический масштаб. Это снова удобно видеть на дереве. Если одно различие возникло на высоком уровне, изменения, происходящие значительно глубже, не могут перенести результат на более высокую ветвь. В обычной арифметике множество малых слагаемых может постепенно дать большую сумму. В ультраметрической геометрии действует другая логика: размер суммы контролируется крупнейшим из присутствующих масштабов.

…666₇ = −1 Рассмотрим частичные суммы: Sₙ = 6 + 6·7 + 6·7² + … + 6·7ⁿ. По формуле суммы геометрической прогрессии Sₙ = 7ⁿ⁺¹ − 1. В обычной метрике эти числа стремительно растут: 6, 48, 342, 2400, … Но в 7-адической метрике важно не то, насколько велико число, а на какую степень 7 делится разность. Разность между Sₙ и −1 равна Sₙ − (−1) = 7ⁿ⁺¹. Поэтому |Sₙ − (−1)|₇ = 7⁻ⁿ⁻¹ → 0. Значит, Sₙ → −1 в 7-адической метрике. Получаем 6 + 6·7 + 6·7² + 6·7³ + … = −1. В позиционной записи это выглядит особенно необычно: …666666₇ = −1. В привычной записи вещественных чисел бесконечными могут быть разряды справа от запятой: 0,333333… У p-адических целых чисел бесконечно продолжаются разряды в другую сторону — к всё более высоким степеням p: a₀ + a₁p + a₂p² + a₃p³ + … Причём это не особенность числа −1. Любая бесконечная последовательность цифр a₀, a₁, a₂, …, где каждая цифра принимает значения от 0 до p−1, определяет p-адическое целое число. В геометрии дерева это просто бесконечный путь: каждая следующая цифра выбирает очередную ветвь. Никакого противоречия с обычной арифметикой здесь нет. Конечные суммы остались теми же. Изменилось понятие расстояния — а вместе с ним и понятие предела. Последовательность 7ⁿ⁺¹ − 1 в обычной метрике уходит в бесконечность, а в 7-адической всё ближе подходит к −1.

Геометрия дерева Мы привыкли считать 3 гораздо более близким к 1, чем 33. Но попробуем измерять близость иначе. Сначала разделим все целые числа на две группы — по остатку при делении на 2. Каждую группу разделим ещё раз — теперь по остатку при делении на 4. Затем — по остатку при делении на 8, 16, 32 и так далее. Получается бесконечное двоичное дерево. Чем дольше два числа идут по одной ветви, тем ближе мы будем их считать. Например, 3 − 1 = 2, а 33 − 1 = 32 = 2⁵. Числа 1 и 3 совпадают только по модулю 2, а 1 и 33 — по модулям 2, 4, 8, 16 и 32. Поэтому в этой геометрии 33 гораздо ближе к 1, чем 3. Для простого числа p, если x−y делится на pᵏ, но не делится на pᵏ⁺¹, положим d(x, y) = p⁻ᵏ, а d(x, x)=0. Это p-адическое расстояние. Его удобно видеть на дереве. На первом уровне выбирается остаток по модулю p, на втором — уточняется остаток по модулю p², затем — p³ и так далее. Расстояние между двумя числами определяется уровнем, на котором их пути впервые расходятся. Если x и y идут вместе k уровней, а y и z — l уровней, то x и z обязательно идут вместе хотя бы min (k, l) уровней. Поэтому d(x, z) ≤ max (d(x, y), d(y, z)). Это сильное неравенство треугольника. Пространства с таким расстоянием называются ультраметрическими. Их геометрия совсем не похожа на евклидову. В любом треугольнике две наибольшие стороны равны. Любая точка шара может служить его центром. Два шара либо не пересекаются, либо один целиком содержится в другом. Более того, каждый шар одновременно открыт и замкнут. На дереве всё это почти очевидно. Замкнутый шар радиуса p⁻ᵏ — это множество всех ветвей, имеющих общий начальный участок длины k. Теперь вспомним позиционную запись: x = a₀ + a₁p + a₂p² + a₃p³ + … Цифра a₀ выбирает первую ветвь дерева, a₁ — следующую, a₂ — следующую и так далее. Поэтому каждой бесконечной ветви соответствует p-адическое целое число, а каждому p-адическому целому числу — бесконечная ветвь. Обычная система счисления неожиданно приобрела геометрию: цифры задают путь по дереву, а расстояние измеряет глубину общей части этого пути. Само такое дерево можно строить и для других оснований. Простое p становится особенно важным для арифметики: p-адическая норма тогда согласуется с умножением, а пополнение рациональных чисел даёт поле ℚₚ. Ультраметрика возникает не только из p-адической арифметики. Если объекты организованы в строгую вложенную иерархию, расстояние можно определить высотой их последнего общего узла. p-адические числа — особенно красивый случай: дерево здесь не строится после вычислений, а уже содержится в арифметике делимости.

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

Двоичная система на плоскости Положим β = −1 + i. Тогда β² = −2i, β³ = 2 + 2i. Следовательно, (1100)ᵦ = β³ + β² = (2 + 2i) − 2i = 2. Запись выглядит двоичной, но её разряды уже не лежат на числовой прямой. Умножение на β делает сразу две вещи: увеличивает длину в √2 раз и поворачивает направление на 135°. Поэтому последовательные веса 1, β, β², β³, … можно представить как векторы разных длин и направлений. И приписывание нуля справа теперь имеет геометрический смысл: оно поворачивает соответствующую точку на 135° и удаляет её от начала координат в √2 раз. Например, 1 → 10ᵦ = −1+i → 100ᵦ = −2i → 1000ᵦ = 2+2i → 10000ᵦ = −4. За четыре сдвига мы умножили число на β⁴ = −4: масштаб увеличился в 4 раза, а направление развернулось на 180°. Но система умеет гораздо больше. Каждое гауссово целое a+bi,  a, b ∈ ℤ, имеет единственную конечную запись без ведущих нулей цифрами 0 и 1 в системе с основанием −1+i. Например, 11ᵦ = β+1 = i, 111ᵦ = β²+β+1 = −i, 1110ᵦ = β³+β²+β = 1+i. Результат опроса показывает, как здесь устроен перенос при сложении. Поскольку 2 = 1100ᵦ = β³+β², то если в каком-то разряде при сложении появилась цифра 2, её можно заменить двумя единицами в более старших разрядах: 2βⁿ = βⁿ⁺³+βⁿ⁺². Например, в младшем разряде 1+1 = 1100ᵦ. В обычной двоичной системе две единицы дают перенос на один разряд влево. Здесь они порождают сразу две единицы — через два и через три разряда. Сложение остаётся поразрядным, но «перенос» уже совсем не похож на обычный. Эту комплексную двоичную систему описал Уолтер Пенни в 1965 году. Есть у неё и неожиданная геометрическая сторона. Рассмотрим все бесконечные дробные хвосты 0,a₁a₂a₃…ᵦ, где каждая aₖ равна 0 или 1. Если разрешать всё более длинные дробные хвосты из нулей и единиц, их значения заполняют фрактальную область twindragon — «двойной дракон». На гифке видно, как возникают её последовательные конечные приближения. Получается, что одна и та же система одновременно задаёт арифметику гауссовых целых и фрактальную геометрию их дробных частей. Ещё раньше, в 1960 году, Дональд Кнут предложил другую комплексную систему: с основанием 2i и цифрами 0, 1, 2, 3. После комплексных чисел естественно спросить: нельзя ли тем же способом перейти к кватернионам? В прямом аналоге системы Пенни — нельзя. Любой кватернион можно записать как β = a + v, где v — его векторная часть. Поскольку v² = −|v|², любая степень β имеет вид A + Bv. Значит, все числа a₀ + a₁β + a₂β² + … с обычными вещественными цифрами остаются в одной двумерной плоскости внутри четырёхмерного пространства кватернионов. Одного кватернионного основания с вещественными цифрами недостаточно, чтобы охватить всё пространство. Кватернионные системы счисления построить можно, но приходится усложнять саму конструкцию. Красивый трюк Пенни — одно основание и всего две обычные цифры — в четырёх измерениях уже не переносится напрямую.

Отрицательный перенос В двоичной системе 1 + 1 = 10₂: пишем 0 и переносим 1 в следующий разряд. В системе с основанием −2 так нельзя: 10₋₂ = −2, а нам нужно получить +2. Что происходит при переполнении разряда? Пусть в нём получилось 2. Пишем 0, а перенос должен удовлетворять равенству 2 = 0 + (−1)·(−2). Значит, в следующий разряд нужно перенести −1. Но и цифры −1 у нас нет. Если в некотором разряде получилось −1, то −1 = 1 + 1·(−2). Поэтому пишем 1, а дальше переносим уже +1. Получаются два необычных правила: 2 → пишем 0, переносим −1; −1 → пишем 1, переносим +1. Именно они дают уже знакомую запись 1 + 1 = 110₋₂. Теперь сложим 111₋₂ + 111₋₂. Мы знаем, что это 3 + 3 = 6, но попробуем получить результат непосредственно по разрядам. В первом разряде: 1 + 1 = 2. Пишем 0, переносим −1. Во втором: 1 + 1 − 1 = 1. Пишем 1, переноса нет. В третьем снова: 1 + 1 = 2. Пишем 0, переносим −1. Следующего разряда в исходных числах уже нет. Там оказалось −1, поэтому пишем 1 и переносим +1 ещё на один разряд. Получаем 111₋₂ + 111₋₂ = 11010₋₂. Проверка: 11010₋₂ = 16 − 8 − 2 = 6. Внешне это всё ещё обычное сложение по разрядам. Но перенос теперь может быть как положительным, так и отрицательным. Причина в том, что переход на один разряд влево означает умножение не на 2, а на −2. Отрицательное основание меняет не только запись чисел, но и саму арифметику переноса.

Без знака минус В обычной позиционной системе веса разрядов равны 1, 2, 4, 8, … если основание равно 2. А если взять основание −2, веса станут 1, −2, 4, −8, 16, … Поэтому 1101₋₂ = (−2)³ + (−2)² + 1 = −8 + 4 + 1 = −3. Никакого знака минус в самой записи нет. Это не случайный фокус: каждое целое число — положительное, отрицательное или ноль — имеет единственную конечную запись в системе с основанием −2 с цифрами 0 и 1. Например, 1 = 1₋₂, 2 = 110₋₂, 3 = 111₋₂, 4 = 100₋₂, а −1 = 11₋₂, −2 = 10₋₂, −3 = 1101₋₂, −4 = 1100₋₂. Есть одна необычная особенность. В любой позиционной системе приписать справа ноль — значит умножить число на основание. Здесь основание отрицательное. Поэтому 111₋₂ = 3, 1110₋₂ = −6, 11100₋₂ = 12, 111000₋₂ = −24. Каждый сдвиг на один разряд не только удваивает модуль, но и меняет знак числа. Более того, знак можно определить уже по длине записи. Если старшая единица стоит при (−2)ⁿ, её абсолютный вклад равен 2ⁿ. Все младшие разряды вместе по абсолютной величине дают не больше 1 + 2 + 4 + … + 2ⁿ⁻¹ = 2ⁿ−1. Поэтому они не способны изменить знак старшего слагаемого. Значит, запись нечётной длины представляет положительное число, а чётной — отрицательное. В обычной системе знак приходится добавлять к записи отдельно. Здесь знак зашит в саму структуру разрядов: один дополнительный разряд способен превратить положительное число в отрицательное. Эта система не осталась математической игрушкой. Польский компьютер UMC-1, серийно выпускавшийся с 1962 года, использовал нега-двоичную арифметику, разработанную Здиславом Павляком.

Когда период может не появиться В основании φ стандартная запись любой рациональной дроби в конце концов становится периодической. Но для произвольного иррационального основания это уже неверно. Посмотрим, чем в этом отношении отличаются φ и √2. Минимальный многочлен для φ —  x² − x − 1. Его корни: φ = (1+√5)/2 и (1−√5)/2 = −1/ φ. Второй корень по модулю меньше 1. Числа с таким свойством выделяют в особый класс. Число Пизо — это вещественное число β > 1, минимальный многочлен которого имеет целые коэффициенты и старший коэффициент 1, а все остальные его корни имеют модуль меньше 1. Золотое сечение — число Пизо. Для любого основания β, являющегося числом Пизо, стандартная β-запись каждой рациональной дроби x, 0 ≤ x < 1, в конце концов становится периодической. Более того, это верно для всех чисел из ℚ(β). Теперь возьмём β = √2. Его минимальный многочлен —  x² − 2, а корни равны √2 и −√2. У второго корня модуль тоже равен √2, то есть больше 1. И здесь действует обратное ограничение: если у минимального многочлена основания есть другой корень с модулем больше 1, то не каждая рациональная дробь может иметь в итоге периодическую стандартную запись. Значит, существуют рациональные дроби, стандартные записи которых в основании √2 не становятся периодическими. Почему вообще важны остальные корни многочлена? Смысл этого условия можно увидеть так. При построении β-записи возникают последовательные остатки. В доказательстве те же выражения рассматривают и при остальных корнях минимального многочлена. Если их модули меньше 1, эти величины остаются ограниченными. После умножения на общий знаменатель соответствующие состояния образуют точки дискретной решётки. В ограниченной области таких точек лишь конечное число. Значит, какое-то состояние повторится — и вслед за ним начнут повторяться цифры. У φ этот механизм работает, а у √2 условие нарушается: второй корень по модулю больше 1. Любопытно, что обычные целые основания тоже укладываются в эту картину. Например, минимальный многочлен числа 10 — это x − 10. Других корней у него нет, поэтому 10 тоже является числом Пизо. Действительно, любое целое число больше 1 формально относится к числам Пизо. Получается, привычная периодичность рациональных дробей в десятичной системе и периодичность в основании φ связаны одним общим свойством основания. А иррациональность сама по себе периода вовсе не гарантирует.

Почему ½ не заканчивается Основание φ иррационально, но натуральные числа в этой системе могут иметь конечные записи: 2 = 10,01ᵩ, 3 = 100,01ᵩ, 4 = 101,01ᵩ. А что будет с самым обычным рациональным числом ½? Оказывается, оно не имеет конечной записи цифрами 0 и 1. Причина довольно неожиданная. Из φ² = φ + 1 следует φ⁻¹ = φ − 1. Поэтому любая целая степень φ имеет вид a+bφ, где a и b — целые числа. Значит, любая конечная запись в основании φ тоже имеет такой вид. Но φ иррационально. Если число a+bφ рационально, то b = 0. А тогда оно просто целое. Отсюда следует: если рациональное число имеет конечную запись в основании φ с цифрами 0 и 1, то оно обязательно целое. Поэтому ½ записывается бесконечно: ½ = 0,010010010010…ᵩ, то есть блок 010 повторяется бесконечно. Единицы стоят при степенях φ⁻², φ⁻⁵, φ⁻⁸, … Поэтому значение записи равно φ⁻² + φ⁻⁵ + φ⁻⁸ + … . Это геометрическая прогрессия: φ⁻²/(1−φ⁻³). Но из φ³ = 2φ + 1 получаем 1 − φ⁻³ = 2φ⁻². Следовательно, φ⁻²/(1−φ⁻³) = ½. В десятичной системе мы привыкли к другому: дробь ½ = 0,5 заканчивается, а ⅓ = 0,333… является периодической. В основании φ граница проходит иначе: уже ½ не имеет конечной записи, зато его стандартная запись оказывается периодической. Иррациональное основание позволяет целым числам заканчиваться, а простейшую дробь заставляет повторяться бесконечно.

Перенос в обе стороны В обычной системе счисления сложение устроено очень локально: если в некотором разряде получилось 10 единиц, перенос уходит на один разряд влево. С основанием φ всё интереснее. Запись числа здесь вообще говоря не единственна: например, 2 = 1,11ᵩ = 10,01ᵩ. Будем приводить результат к стандартной записи без соседних единиц. Мы знаем, что φ² = φ + 1, поэтому соседние единицы можно объединять: 011ᵩ → 100ᵩ. Но что делать, если при сложении в одном разряде появилась цифра 2? Из равенства φ² = φ + 1 можно получить 2 = φ + φ⁻². А значит, для любого n 2φⁿ = φⁿ⁺¹ + φⁿ⁻². Иными словами, вместо двойки при весе φⁿ появляются две единицы при весах φⁿ⁺¹ и φⁿ⁻². Посмотрим на сложение: 2 = 10,01ᵩ, 3 = 100,01ᵩ. Складываем коэффициенты: 2 + 3 = 110,02ᵩ. Но в стандартной записи разрешены только цифры 0 и 1, поэтому двойку нужно устранить. Используем правило 2φ⁻² = φ⁻¹ + φ⁻⁴. Получаем 110,02ᵩ → 110,1001ᵩ. Теперь в целой части стоят две соседние единицы: 110ᵩ → 1000ᵩ. Поэтому 2 + 3 = 1000,1001ᵩ. Проверим: 1000,1001ᵩ = φ³ + φ⁻¹ + φ⁻⁴ = 5. Получилась обычная пятёрка — но путь к ней совсем не похож на школьное сложение столбиком. Здесь работают два правила нормализации: соседние единицы объединяются благодаря φⁿ + φⁿ⁻¹ = φⁿ⁺¹, а появившаяся цифра 2 распадается по правилу 2φⁿ = φⁿ⁺¹ + φⁿ⁻². Поэтому перенос уже не движется только справа налево. Он может одновременно породить разряды по обе стороны от исходного — и даже перескочить через запятую. В системе с целым основанием правила переноса задаются самим основанием. Здесь их задаёт алгебраическое равенство φ²=φ+1. Поэтому перенос здесь может идти не только влево: соотношение φ²=φ+1 заставляет его распространяться сразу по нескольким разрядам.

Одна двойка — много записей В системе с основанием φ запись числа может быть не единственной. Например, из φ² = φ+1 следует φ⁻¹+φ⁻² = 1, поэтому 2 = 1,11ᵩ. Но верно и 2 = φ+φ⁻² = 10,01ᵩ. Более того, конечных записей числа 2 бесконечно много. Поскольку 100 ⟷ 011, можно заменять в любых трёх соседних разрядах, не меняя числа, получаем: 2 = 10,01ᵩ = = 10,0011ᵩ = = 10,001011ᵩ = = 10,00101011ᵩ = = … Чтобы выбрать одну запись, вводят правило: две единицы не должны стоять рядом. Тогда стандартная запись двойки — 10,01ᵩ. Дополнительное правило возвращает системе то, чего у неё не было изначально: единственность записи.