Практические способы представления конечной группы

[B@R5uk]

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

Наиболее очевидный метод (что называется "в лоб") — это представление в виде таблицы умножения. С одной стороны очень удобно: сразу известен порядок группы, каждый элемент нумеруется от нуля до порядка не включая, групповая операция над элементами выполняется элементарно просто и в одну примитивную операцию: взятие элемента по двум индексам из двумерного массива. Недостаток тоже очевиден: представление занимает много памяти. Даже у группы порядка 2500 при использовании типа shot в два байта таблица умножения займёт

$$\frac{2\cdot 2500^2}{2^{20}}\approx 11,9\;\text{МБайт}$$

Это за пределами не только кэша 1-го и 2-го уровня, но и 3-го тоже (для современных процессоров, у меня старенький, только первые два есть: 64 КБ / 1 МБ). Это значит, что программа будет работать с оперативной памятью, которая, как известно, очень медленная.

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

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

Используется синтаксис Java

public class CyclicGroup implements Group {
    
    private int order;
    private int [] productFunc, inverseFunc;
    
    public CyclicGroup (int argOrder) {
        int k, l;
        if (1 > argOrder) {
            throw new IllegalArgumentException ("\n\nIllegal group order.\n");
        }
        order       = argOrder;
        l           = argOrder * 2 - 1;
        productFunc = new int [l];
        inverseFunc = new int [order];
        for (k = 1; order > k; ++k) {
            productFunc [k] = k;
            inverseFunc [k] = order - k;
        }
        for (++k; l > k; ++k) {
            productFunc [k] = k - order;
        }
    }
    
    @Override
    public int order () {
        return order;
    }
    
    @Override
    public int product (int argLeft, int argRight) {
        if (0 > argLeft || 0 > argRight || order <= argLeft || order <= argRight) {
            throw new IllegalArgumentException ("\n\nIllegal element index.\n");
        }
        //return order > argLeft + argRight ? argLeft + argRight : argLeft + argRight - order;
        return productFunc [argLeft + argRight];
    }

    @Override
    public int inverse (int arg) {
        if (0 > arg || order <= arg) {
            throw new IllegalArgumentException ("\n\nIllegal element index.\n");
        }
        //return 0 == arg ? 0 : order - arg;
        return inverseFunc [arg];
    }
    
    @Override
    public int [] generators () {
        return new int [] {1};
    }
}

Используется синтаксис Java

import java.util.Arrays;

public class CartesianGroupProduct implements Group {
    
    private int order, subOrder;
    private int [] gens, inverseFunc, subFunc1, subFunc2;
    private Group group1, group2;
    
    public CartesianGroupProduct (Group argGroup1, Group argGroup2) {
        int k, l, m;
        int [] gens1, gens2;
        Group .checkIntegrity (argGroup1);
        Group .checkIntegrity (argGroup2);
        order    = argGroup1 .order () * argGroup2 .order ();
        subOrder = argGroup2 .order ();
        group1   = argGroup1;
        group2   = argGroup2;
        gens1    = argGroup1 .generators ();
        gens2    = argGroup2 .generators ();
        gens     = new int [gens1 .length + gens2 .length];
        k = 0;
        for (l = 0; gens1 .length > l; ++k, ++l) {
            gens [k] = gens1 [l] * subOrder;
        }
        for (l = 0; gens2 .length > l; ++k, ++l) {
            gens [k] = gens2 [l];
        }
        Arrays .sort (gens);
        subFunc1    = new int [order];
        subFunc2    = new int [order];
        inverseFunc = new int [order];
        for (k = 1; order > k; ++k) {
            subFunc1 [k] = k / subOrder;
            subFunc2 [k] = k % subOrder;
        }
        for (k = 1; order > k; ++k) {
            l = 0;
            while (true) {
                m = product (k, l);
                if (0 == m) {
                    break;
                }
                l = m;
            }
            inverseFunc [k] = l;
        }
    }
    
    @Override
    public int order () {
        return order;
    }
    
    @Override
    public int product (int argLeft, int argRight) {
        if (0 > argLeft || 0 > argRight || order <= argLeft || order <= argRight) {
            throw new IllegalArgumentException ("\n\nIllegal element index.\n");
        }
        return  group1 .product (subFunc1 [argLeft], subFunc1 [argRight]) * subOrder +
                group2 .product (subFunc2 [argLeft], subFunc2 [argRight]);
        //return  group1 .product (argLeft / subOrder, argRight / subOrder) * subOrder +
        //        group2 .product (argLeft % subOrder, argRight % subOrder);
    }
    
    @Override
    public int inverse (int arg) {
        if (0 > arg || order <= arg) {
            throw new IllegalArgumentException ("\n\nIllegal element index.\n");
        }
        return inverseFunc [arg];
    }
    
    @Override
    public int [] generators () {
        return Arrays .copyOf (gens, gens .length);
    }
}

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

Пока единственный способ (который я знаю) получения групп в таком представлении — это случай, когда они естественным образом вычисляются сразу в этом виде. Я имею в виду группы автоморфизмов других групп. Не уверен, что группа автоморфизмов порядка 98784 от группы порядка 147 на много лучше случая выше (в плане расхода памяти), но хотя бы в теории с ней можно будет хоть как-то работать, потому что таблица умножения для неё займёт 18 ГБ! (С моими 3-мя явно запредельная величина). И тут можно пытаться делать всякие оптимизации, например, сгруппировать элементы по величине порядка, сделать списки перестановок внутри каждого порядка, а полную перестановку задавать как комбинацию перестановок для каждого из порядков. Тогда память будет ещё больше экономиться, правда производительность пострадает.

Я ничего не забыл? Буду рад любым интересным и необычным предложениям.

[dgwuqtj]

Ещё есть задание группы через представление, скажем, над $\mathbb Q^{\mathrm{alg}}$, в виде набора образующих матриц (обычных или разреженных). Вообще можно задавать группы как подгруппы в любых уже известных группах наборами образующих, но через перестановки и через линейные представления — это самые удобные варианты.

Группы типа универсальных центральных расширений $\mathrm S_n$ и через представления задавать не очень удобно (у спинорного представления размерность около $2^n$), их удобнее представлять просто как абелево расширение уже известной группы с данным 2-коциклом. Не забывайте и про другие групповые конструкции, которые дают новые группы: прямые произведения, полупрямые произведения, амальгамы (для бесконечных групп), факторгруппы.

Не знаю насчёт работы с группами на компьютере, но с точки зрения математики всё это время от времени удобно. Задание образующими и соотношениями тоже бывает алгоритмически эффективным, хотя бы для групп Кокстера типа $\mathsf E_8$.

[B@R5uk]

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

$$O(rn)$$

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

$$O(wn)$$

где w — средняя длина слова. Трудоёмкость групповой операции при этом будет всего

$$O(w)$$

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

$$w_m\sim\min\limit_{w_m}^{}\left(n\le\sum\limit_{k=0}^{w_m}r^k=\frac{r^{w_m+1}-1}{r-1}\right)\sim\frac{\ln n}{\ln r}$$

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

$$w_m\sim\sqrt[r]{n}$$

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

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

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

$$O(rn+wn)$$

[B@R5uk]

B@R5uk в сообщении #1647438 писал(а):

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

$$w_m\sim\sqrt[r]{n}$$

Это не верно. Во всяком случае, для циклической группы

$$\mathbb{Z}_n=\left\langle\;a,\;|\;a^n=I\;\right\rangle$$

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

$$b_k=a^{2^{k-1}},\quad 1\le k\le r,\quad r=1+\left\lfloor\log_2{(n-1)}\right\rfloor$$

то длина слова будет не больше

$$w\le r=O(\ln n)$$

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

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

[dgwuqtj]

Про память для хранения произвольной конечной группы порядка $n$ как будто всё известно, нужно $\Theta(n)$ машинных слов. Есть препринт про достаточность, там внутри ссылка на необходимость. Заодно умножение считается за постоянное время. Правда, результат теоретический (использующий CFSG) и мне, как неспециалисту, не очень понятно, насколько это вообще реалистично запрограммировать и насколько там разумная константа в асимптотике.

[B@R5uk]

dgwuqtj, спасибо! Щас попытаюсь ознакомиться, надеюсь, матан мне будет по зубам.

[B@R5uk]

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

$$H\subseteq G:\quad|H|\sim\sqrt{|G|}$$

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

-- 27.07.2024, 13:52 --

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