Задача по теории групп

B@R5uk · 26/05/12 1700 приходит весна?

mihaild в сообщении #1491177 писал(а):

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

Это следует из того, что $aC\ne Ac$ для правого верхнего элемента матрицы-произведения.

mihaild в сообщении #1491185 писал(а):

Миниммальное (из которого нельзя ничего выкинуть) или наименьшее (содержащее минимально возможное число элементов)?

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

mihaild в сообщении #1491185 писал(а):

Возьмем $S_3$ - ваш алгоритм возьмет сначала цикл длины $3$ , потом еще цикл длины $3$ ...

Не может такого быть! В $S_3$ всего один цикл длины 3. Мы точно под циклом понимаем одно и то же? Я имею в виду циклическую группу, или, в данном случае, подгруппу. Циклические подгруппы — это то, что порождается всего одним элементом.

vpb · 18/01/15 3244

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

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

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

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

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

Позвольте обратить ваше внимание, что вычислительные методы в теории групп --- это хорошо разработанная область. См, например, Holt ea., Handbook of computational group theory. Почему бы Вам не почитать её, и просто учебники по теории групп ? А то вы тратите время и энергию неизвестно на что ... (Хотя, конечно, дело хозяйское, на что их тратить.)

mihaild · 16/07/14 9215 Цюрих

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

Вот интересно, что существует такое различие.

Совершенно стандартная ситуация. Есть много задач, где минимальные множества имеют разные размеры.

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

Эти два понятия для конечных групп точно не совпадают?

Точно. Например для $S_4$ - $\{(12), (23), (34)\}$ и $\{(12), (1234)\}$ .

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

Не может такого быть!

Да, это я хотел упростить и доупрощался. Но всё равно - в $S_6$ можно взять $(123456)$ а потом либо сразу $(1)(23)(456)$ , либо сначала взять $(1)(246)(35)$ и уже потом $(1)(23)(456)$ .

B@R5uk · 26/05/12 1700 приходит весна?

mihaild в сообщении #1491270 писал(а):

Но всё равно - в $S_6$ можно взять $(123456)$ а потом либо сразу $(1)(23)(456)$ , либо сначала взять $(1)(246)(35)$ и уже потом $(1)(23)(456)$ .

Спасибо. То есть простой жадный алгоритм работать не будет. Забавный получился пример с образующими одного порядка. Как вы так легко их подобрали? Мне только чтобы проверить корректность примера пришлось накатать программку:

код: [ скачать ] [ спрятать ]

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

import java.util.*;

class ArrayComparator implements Comparator <int []> {

    @Override

    public int compare (int [] arg1, int [] arg2) {

        int k;

        if (arg1 .length != arg2 .length) {

            if (arg1 .length > arg2 .length) {

                return 1;

            }

            return -1;

        }

        for (k = 0; arg1 .length > k; ++k) {

            if (arg1 [k] == arg2 [k]) {

                continue;

            }

            if (arg1 [k] > arg2 [k]) {

                return 1;

            }

            return -1;

        }

        return 0;

    }

}

public class Group_from_Permutations {

    private static final int sizeLimit = 1000;

    private static final int [] [] seedPermutations = {{1, 2, 3, 4, 5, 0}, {0, 3, 4, 5, 2, 1}};

//    private static final int [] [] seedPermutations = {{1, 2, 3, 4, 5, 0}};

//    private static final int [] [] seedPermutations = {{0, 3, 4, 5, 2, 1}};

//    private static final int [] [] seedPermutations = {{1, 2, 3, 4, 5, 0}, {0, 2, 1, 4, 5, 3}};

    private static Set <int []> elementsList;

    private static Queue <int []> queue;

    public static void main (String [] args) {

        int k;

        int [] currentElement, newElement;

        Iterator <int []> iterator;

        elementsList = new TreeSet <> (new ArrayComparator ());

        queue = new ArrayDeque <> ();

        queue .add (new int [] {1, 2, 3, 4, 5, 6});

        while (0 != queue .size ()) {

            currentElement = queue .poll ();

            for (k = 0; seedPermutations .length > k; ++k) {

                newElement = permutate (currentElement, seedPermutations [k]);

                if (elementsList .add (newElement)) {

                    queue .add (newElement);

                }

            }

            if (sizeLimit == elementsList .size ()) {

                System .out .println ("Size limit have been reached.");

                break;

            }

        }

        iterator = elementsList .iterator ();

        k = 0;

        while (iterator .hasNext ()) {

            System .out .println (String .format("%4d: %s", k, Arrays .toString (iterator .next ())));

            ++k;

        }

    }

    private static int [] permutate (int [] arg1, int [] arg2) {

        int k;

        int [] result = new int [arg1 .length];

        for (k = 0; arg1 .length > k; ++k) {

            result [k] = arg1 [arg2 [k]];

        }

        return result;

    }

}

Вообще, это потрясающе, как с помощью перестановок можно порождать группы. При этом, чтобы умножать элементы совершенно не нужна таблица умножения! Для больших групп это невероятная экономия памяти ( $N\log N$ вместо $N^2$ ). Перемножаемые элементы, представленные в виде массивов с перестановками просто подставляются один в другой и всё:

код: [ скачать ] [ спрятать ]

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

    
    private static int [] permutate (int [] arg1, int [] arg2) {

        int k;

        int [] result = new int [arg1 .length];

        for (k = 0; arg1 .length > k; ++k) {

            result [k] = arg1 [arg2 [k]];

        }

        return result;

    }

Правда, сразу встаёт вопрос: как простым известным мне группам сопоставить "перестановочное" представление? Например, как будут задаваться группы, образованные прямым произведением двух циклических групп или группы диэдра?

В любом случае, предложенный мной алгоритм не верен. Однако, его можно улучшить: на каждом шаге выбирать такой новый элемент группы, чтобы при добавлении к уже имеющимся образующим он давал подгруппу максимального порядка. Это всё ещё жадный алгоритм: он принимает локально оптимальное для каждого шага решение; и он всё ещё гораздо быстрее самого общего перебора в лоб. Но выбор делается более осознанный. Неужели и к нему найдётся контрпример?

mihaild · 16/07/14 9215 Цюрих