Геометрия данных 6. Граф-звезда

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



    Граф минимальной связности


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

    Формулируем задачу. Надо определить топологию графа, для которого: 1) все вершины одинаковы и 2) общая связность минимальна. Первому условию удовлетворяет, например, полный граф, в котором все вершины связаны со всеми. Но такая связность в природе редко встречается, такой граф не удовлетворяет 2-му условию.

    С другой стороны минимальную связность (2-е условие) имеет цепочка — каждый узел связан только с соседними, но тут не выполняется 1-е условие. С какими именно соседями надо связывать узлы, если они все равноценны?

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

    Базис пространства целых чисел


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

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

    Грамиан базиса-звезды


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

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

    $g(A, B) = -q(A, B)/2 \quad(6.1) $

    Для полного грамиана добавляем в базовый набор нормаль $\mathbf{z}$. В нашем случае базис состоит из элементов, поэтому произведения элементов и нормали равны 1. В итоге получаем вид грамиана графа-звезды для базиса простых чисел:
    \begin{array}{c | c c c с c c c}
    Gm & * & 1 & 2 & 3 & 5 & 7 & 11 &… \\
    \hline
    * & & 1 & 1 & 1 & 1 & 1 & 1 &… \\
    1 & 1 & &-0.5 &-0.5 & -0.5 &-0.5 &-0.5 &… \\
    2 & 1 & -0.5 & & -1 & -1 & -1 & -1 &… \\
    3 & 1 & -0.5 &-1 & & -1 & -1 & -1 &… \\
    5 & 1 & -0.5 &-1 & -1 & & -1 & -1 &… \\
    7 & 1 & -0.5 &-1 & -1 & -1 & & -1 &… \\
    11 & 1 & -0.5 &-1 & -1 & -1 & -1 & &… \\
    … &… &… &… &… &… &… &… & \\
    \end{array}

    Лапласиан звезды


    Обращая грамиан, получаем лапласиан: $Gm \cdot Lm = I$
    \begin{array}{c | c c c с c c c}
    Lm & * & 1 & 2 & 3 & 5 & 7 & 11 &… \\
    \hline
    * & m/4 & 1-m/2 & 0.5 & 0.5 & 0.5 & 0.5 & 0.5 &… \\
    1 & 1-m/2 & m & -1 &-1 & -1 &-1 & -1 &… \\
    2 & 0.5 & -1 & 1 &&&&& \\
    3 & 0.5 & -1 && 1 &&&& \\
    5 & 0.5 & -1 &&& 1 &&& \\
    7 & 0.5 & -1 &&&& 1 && \\
    11 & 0.5 & -1 &&&&& 1 & \\
    … &… &… &&&&&&… \\
    \end{array}
    В углу — норма ортоцентра базиса $rs$, зависит от мерности пространства $m $, которое здесь равно количеству лучей звезды: $rs=m/4$.

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

    Лапласиан и грамиан базиса являются метрическими тензорами пространства. Теперь обратимся к координатам элементов.

    Би-координаты элементов


    Составное число $X$ может быть выражено как линейная комбинация элементов базиса $A_i$:

    $X = bm^i(X) \ A_i \quad(6.2)$

    Коэффициенты разложения $bm(X)$ — это би-координаты элемента.
    Коэффициенты разложения при простых числах известны. Например, число 12 — это две двойки и одна тройка ($12 = 2^2 \cdot 3^1$). То есть $b^2(e12) = 2, b^3(e12) = 1$.

    Мы используем перед числами префикс $e$, чтобы подчеркнуть, что это не скаляры, а элементы пространства.

    Помимо простых чисел в базисе присутствует также единица и нормаль. Выделим их в явном виде из разложения (6.2):

    $X = w(X) \ \mathbf{z} + b^1(X) e1 + b^i(X) \ P_i \quad(6.3)$

    Здесь $P_i$ означает множество из простых чисел базиса.

    Для определения двух неизвестных коэффициентов (орбитали числа $w(X)$ и би-компоненты при единице $b^1(X)$) воспользуемся двумя требованиями.

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

    $b^1(X) = 1 - b^p \ 1_p = 1 - s1(X) \quad(6.4)$

    Здесь $s1(X) = b^p \ 1_p $ — сумма коэффициентов при простых числах.
    Поскольку для целых чисел коэффициенты $b^p$ положительны, то коэффициент при единице будет либо нулевым, либо отрицательным.

    Второе условие — это требование локальности. Все числа должны иметь нулевую норму. Тогда

    $n(X) = (w(X) \ \mathbf{z} + b^i(X) \ A_i)^2 = 2 w(X) + (b^i(X) \ A_i)^2 = 0$

    Откуда после раскрытия суммы $(b^i(X) \ A_i)^2$ с учетом свойств скалярных произведений элементов базиса $Gm$ получаем простое соотношение:

    $w(X) = (s1(X) - s2(X))/2 \quad(6.5)$

    $s2(X) = (b^p)^2 \ 1_p $ — сумма квадратов коэффициентов при простых числах. $s1(X)$, $s2(X)$ — это агрегаты числа.

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

    Примеры разложения чисел на компоненты


    Зная коэффициенты разложения числа на простые сомножители, мы можем определить его би-координаты в пространстве — коэффициенты разложения (6.3).

    В качестве примера рассчитаем би-координаты 6-ки.
    Ее разложение на простые множители имеет вид: $6 = 2 \cdot 3$. То есть есть два единичных коэффициента при двойке и тройке. Тогда сумма коэффициентов равна $s1(e6) = 2$, и сумма квадратов — $s2(e6) = 2$.
    Оставшиеся би-компоненты теперь можно получить из формул (6.4), (6.5).
    $b^1(e6) = 1 - s1(e6) = -1, \quad w(e6) = (2 - 2)/2 = 0$.
    Видим, что орбиталь 6-ки равна нулю. Вид разложения:

    $e6 = -e1 + e2 + e3$

    Значения агрегатов и их разности для первых 17 чисел:
    \begin{array}{c | c}
    a & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\
    \hline
    s1 & 0 & 1 & 1 & 2 & 1 & 2 & 1 & 3 & 2 & 2 & 1 & 3 & 1 & 2 & 2 & 4 & 1 \\
    s2 & 0 & 1 & 1 & 4 & 1 & 2 & 1 & 9 & 4 & 2 & 1 & 5 & 1 & 2 & 2 & 16 & 1 \\
    s2 — s1 & 0 & 0 & 0 & 2 & 0 & 0 & 0 & 6 & 2 & 0 & 0 & 2 & 0 & 0 & 0 & 12 & 0 \\
    \end{array}
    Би-координаты первых (составных) чисел (колонки таблицы):
    \begin{array}{c | c}
    Bm & 4 & 6 & 8 & 9 & 10 & 12 & 14 & 15 & 16 & 18 & 20 & 21 & 22 & 24 & 25 \\
    \hline
    \mathbf{z} & -1 & 0 & -3 & -1 & 0 & -1 & 0 & 0 & -6 & -1 & -1 & 0 & 0 & -3 & -1 \\
    1 & -1 & -1 & -2 & -1 & -1 & -2 & -1 & -1 & -3 & -2 & -2 & -1 & -1 & -3 & -1 \\
    \hline
    2 & 2 & 1 & 3 & & 1 & 2 & 1 & & 4 & 1 & 2 & & 1 & 3 & \\
    3 & & 1 & & 2 & & 1 & & 1 & & 2 & & 1 & & 1 & \\
    5 & & & & & 1 & & & 1 & & & 1 & & & & 2 \\
    7 & & & & & & & 1 & & & & & 1 & & & \\
    \end{array}
    В названиях строк — элементы базиса, в названии колонок — составные числа.
    Коэффициент разложения при нормали $\mathbf{z}$ — это орбиталь числа $w$. Не надо быть специалистом в теории чисел, чтобы понять, что орбиталь должна играть не последнюю роль в описании свойств чисел.

    Ди-координаты чисел


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

    Таким образом для получения значения компоненты ди-координат достаточно (скалярно) умножить линейное разложение числа (6.3) на соответствующий элемент базиса. Умножение на нормаль пространства не очень интересно — дает единицу, то есть число является элементом пространства.

    Найдем значение ди-компоненты при единице. Умножая (6.3) на $e1$, получаем с учетом (6.4) и (6.5):

    $dm_1(X) = -s2(X)/2 \quad(6.6)$

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

    Аналогично можно выразить остальные ди-компоненты (соответствующие простым числам):

    $dm_p(X) = b^p(X) - (s2(X) + 1)/2 \quad(6.7)$

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

    $b^p(X) - dm_p(X) = 1/2 - dm_1(X) \quad(6.7.1)$

    Расстояния между числами


    Норма разности элементов соответствует дистанции между ними. Если известны координаты, то дистанция между числами может быть рассчитана через свертку координат, так как нормы чисел равны нулю:

    $q(X, Y)=-2 g(X, Y) = -2 bm^i(X) \ dm_i(Y) \quad(6.8) $

    В данном базисе взаимные координаты можно на основе тождества (6.7), то есть без использования метрических тензоров.

    Рассчитаем в качестве примера дистанцию между 9-кой и 8-кой:

    $q(e8, e9)=-2 g(e8, e9) = -2 bm^i(e8) \ dm_i(e9) = [-3, -2, 3] \ [-2, 4, 5] = 6 - 8 + 15 = 13$

    Вид дистанционной матрицы для первых 11 чисел
    \begin{array}{c | c c c с c c c c c с c}
    Q & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 \\
    \hline
    1 & — & 1 & 1 & 4 & 1 & 2 & 1 & 9 & 4 & 2 & 1 \\
    2 & 1 & — & 2 & 1 & 2 & 1 & 2 & 4 & 5 & 1 & 2 \\
    3 & 1 & 2 & — & 5 & 2 & 1 & 2 & 10 & 1 & 3 & 2 \\
    4 & 4 & 1 & 5 & — & 5 & 2 & 5 & 1 & 8 & 2 & 5 \\
    5 & 1 & 2 & 2 & 5 & — & 3 & 2 & 10 & 5 & 1 & 2 \\
    6 & 2 & 1 & 1 & 2 & 3 & — & 3 & 5 & 2 & 2 & 3 \\
    7 & 1 & 2 & 2 & 5 & 2 & 3 & — & 10 & 5 & 3 & 2 \\
    8 & 9 & 4 & 10 & 1 & 10 & 5 & 10 & — & 13 & 5 & 10 \\
    9 & 4 & 5 & 1 & 8 & 5 & 2 & 5 & 13 & — & 6 & 5 \\
    10 & 2 & 1 & 3 & 2 & 1 & 2 & 3 & 5 & 6 & — & 3 \\
    11 & 1 & 2 & 2 & 5 & 2 & 3 & 2 & 10 & 5 & 3 & — \\
    \end{array}

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



    Серия завершена. Мы рассказали все, что планировали (и даже немного больше). Даны основные понятия и соотношения, связанные с системами координат на базисе из элементов. Полученные выражения применимы к любым линейным пространствам, к любым данным.
    Share post

    Comments 0

    Only users with full accounts can post comments. Log in, please.