Геометрия дерева
Мы привыкли считать 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-адические числа — особенно красивый случай: дерево здесь не строится после вычислений, а уже содержится в арифметике делимости.
Мы привыкли считать 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-адические числа — особенно красивый случай: дерево здесь не строится после вычислений, а уже содержится в арифметике делимости.