ТЕОРИЯ РЕГУЛЯРНЫХ БЕСПОРЯДКОВ

 

АННОТАЦИЯ

Цель статьи заключается в исследовании структуры множества регулярных беспорядков. На сегодняшний день это практически не исследованное множество перестановок играющее важную роль в теории конечных групп , так как из регулярных беспорядков состоят строки и столбцы матриц умножения элементов в группах. В статье представлены результаты исследования  множества регулярных беспорядков в симметрической группе перестановок. Получены формулы подсчета количества регулярных беспорядков. Передложен алгоритм формирования всех образующих для множества регулярных беспорядков. Доказано, что для любой группы из n элементов найдется изоморфная ей группа пересекающаяся с циклом циркулянта <>  и для поиска всех типов конечных групп мощности n достаточно проводить их поиск в окрестностях циркулянтной группы <> . Рассмотрены примеры формирования конечных групп из циклов регулярных беспорядков. 

ABSTRACT

The purpose of the article is to study the structure of a set of regular derangements. To date, this is a practically unexplored set of permutations that plays an important role in the theory of finite groups, since the rows and columns of the multiplication matrices of elements in groups consist of regular derangements. The article presents the results of a study of a set of regular derangements in the symmetric group of permutations. Formulas for calculating the number of regular derangements are obtained. An algorithm for the formation of all generators for a set of regular derangements is proposed. It has been proven that for any group of n elements there is a group isomorphic to it and intersecting with a circulant cycle and to search for all types of finite groups with n elements it is enough to search for them in the neighborhood of a circulant group . Examples of the formation of finite groups from cycles of regular derangements are considered.

 

Ключевые слова: перестановка, беспорядок, конечная группа, циркулянт, изоморфизм.

Keywords: Permutation, derangement, finite group, circulant, isomorphism.

 

Введение

Беспорядки в математике сегодня мало иссследованы (в отличие от перестановок). Интерес к ним возникает по той причине, что строки и столбцы матриц умножения групповых элементов (матриц Кэли) в группах перестановок представлены именно беспорядками. В статье [1] введено понятие регулярных беспорядков. Регулярным беспорядком при этом называется перестановка из n элементов у которой все степени кроме n являются беспорядками. В статье показано, что только регулярные беспорядки могут присутствовать в матрицах Кэли.

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

2. Количество регулярных беспорядков в симметрической группе

2.1 Понятие регулярного беспорядка и циркулянта

В математике перестановками называются списки чисел от 1 до n . Обычно перестановки обозначаются символом  .Для дальнейших исследований мы будем использовать понятие единичной перестановки

 =(1,…,n) представляющей собой список последовательных чисел от 1 до n. Элемент с номером i любой перестановки  будем обозначать как [i] .

Циклом перестановки  называется множество всех степеней этой перестановки. Обозначается такой цикл в виде <> и перестановка  называется образующей. При этом в цикле <> может быть несколько образующих (их количество равно функции Эйлера φ(|<>|) ) [3]. Эти образующие формируют один и тот же цикл.

Спектром перестановки   будем называть мощность  множества <> которую мы будем обозначать как ω()=|< >| .

Беспорядками называются перестановки в которых ни один элемент не стоит на своем месте [2]. Формально беспорядок b определяется следующим образом :

b=({|})      

Например b=(4,1,2,3) беспорядок из четырех элементов , b[3]=2 .

Регулярным беспорядком b называется беспорядок у которого все элементы цикла <b> кроме единичной перестановки являются  беспорядками.

Примером регулярного беспорядка является циркулянт  .

 =(2,3,…,n-1,1)                                                                       (1)

Циркулянтным циклом <> называется множество перестановок образованное степенями  циркулянта .  Циркулянт  при этом является образующим.

<>={ |=  }                                                           (2)

Не сложно показать прямым вычислением, что все степени циркулянта   

кроме  = являются регулярными беспорядками.

Так же не сложно подсчитать спектр циркулянта

ω()=n                                                                                (3)

В общем множестве беспорядков существуют как регулярные так и нерегулярные беспорядки. Например беспорядок (3,5,1,2,4) не является регулярным . Квадрат этого беспорядка не является беспорядком ,так как у него элементы 1 и 3 стоят на своих местах. (3,5,1,2,4)*(3,5,1,2,4)=(1,4,3,5,2).

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

2.2 Образующие регулярные беспорядки со спектром n

Будем обозначать количество беспорядков со спектром ω в множестве как .  В [3] получена формула для количества беспорядков  .

=n!/( *(n/)!)                                                                     (4)

В соответствии с этой формулой можно посчитать количество беспорядков со спектром n в

=(n-1)!                                                                                 (5)

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

Обозначим множество беспорядков со спектром n в  как  и назовем его множеством образующих (генераторов).

={,…,}                                                                      (6)

Так как каждый генератор  имеет спектр n то в соответствии с формулой (5) можно сформировать (n-1)! циклов <>  . Каждый цикл при этом имеет n элементов . Все элементы каждого цикла <>  являются регулярными беспорядками. Некоторые циклы могут иметь общие элементы . Одним из генераторов в множестве  является циркулянт  .

Возникает вопрос - покрывает ли множество циклов  < >  все множество регулярных беспорядков  ?

Положительный ответ на этот вопрос следует из того, что все циклы перестановок одинаковой длины изоморфны друг другу.

Теорема 1 Объединение циклов < >   полностью покрывает все множество регулярных беспорядков .

Доказательство

Рассмотрим регулярный беспорядок b со спектром  ω(b) в множестве и цикл образованный этим беспорядком <b>. В цикле  <>  есть регулярный беспорядок степени n/ ω(b)  . Этот беспорядок очевидно имеет спектр ω(b) и образует цикл изоморфный циклу <b>. Это значит найдется перестановка x такая , что

b=**x

Рассмотрим цикл *<>*x . Беспорядок b и весь цикл <b> входят в этот цикл.  Этот цикл имет мощность n и значит образован одним из генераторов .

Таким образом <>=

3. Алгоритм формирования множества генераторов/образующих 

Рассмотрим множество

={**}                                                               (7)

Здесь  это симметрическая группа перестановок  порядка n у которых

[n]=n.   это то же множество но перестановки в нем расположены в другом порядке так , что перестановке  из   соответствует перестановка .

Членами множества  являются (n-1)! перестановок вида

**                                                                    (8).

Рассмотрим перестановку которая получится в результате реализации выражения 8.  Пусть  =[,…,,n]. В виде подстановки  будет выглядеть как

1	.	.	.	n-1	n
	.	.	.		n

Циркулянт  в виде подстановки будет выглядеть как

1	.	.	.	n-1	n
2	.	.	.	n	1

Обратная перестановка  в виде подстановки будет выглядеть как

	.	.	.		n
1	.	.	.	n-1	n

Произведя умножение трех подстановок в результате получим

	.	.	.
	.	.	.

 

То есть результирующая перестановка это беспорядок с внутренним циклом

-...- .Спектр этого беспорядка равен n . Значит это один из генераторов/образующих множества  .

Так как все (n-1)! перестановок  различны то в результате множество   из формулы (7) будет содержать (n-1)! различных беспорядков  со спектром n. Это значит , что =

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

=    <>                                                              (9)

В каждом цикле <> имеется (n) образующих (где  (n) это функция Эйлера). Каждая их этих образующих формирует один и тот же цикл поэтому в множестве имеется (n-1)!/ (n) разных циклов длины n которые могут частично пересекаться.

4. Примеры множества генераторов 

n=2

Очевидно, что ==(2,1)

n=3  =(2,3,1)

={(2,3,1),(3,1,2)}

n=4  =(2,3,4,1)

={(2,3,4,1),(3,1,4,2),(4,1,2,3),(2,4,1,3),(3,4,2,1),(4,3,1,2)}

5. Структура некоторых множеств

Как следует из формулы (9) множество  может быть представлено в виде объединения циклов <> . Каждый цикл имеет длину (мощность) n. Циклы <> могут пересекаться по подциклам меньшего размера.

Рассмотрим для примера структуры множеств , и  .

5.1 Структура множества

={(2,3,4,1),(3,1,4,2),(4,1,2,3),(2,4,1,3),(3,4,2,1),(4,3,1,2)}

Так как по формуле Эйлера  (4)=2 то в множестве   имеется всего три цикла длины 4 в каждом из которых имеется по две образующих.

<>=<(2,3,4,1)> , <>=<(4,1,2,3)>=<>

<>=<(3,1,4,2)> , <>=< (2, 4, 1, 3)>=<>

<>=<(3,4,2,1)>,  <>=<(4, 3, 1, 2)>=<>

Общим элементом во всех трех циклах очевидно является единичная перестановка =(1,2,3,4). Других общих элементов в циклах <>, <>,<> нет.

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

Граф множества  представлен на рис 1.

 

Рисунок 1. Графовое представление множества

 

В графе имеются четыре кластера каждый из которых состоит из трех вершин . Три кластера это беспорядки из циклов <>, <>,<>  . Четвертый кластер , расположенный в центре,  образован из элементов , ,  . Смысл кластеров достаточно очевиден. Условие непересечения беспорядков является необходимым условием для вхождения их в матрицу Кэли в виде строк и столбцов.

Из структуры графа можно сделать вывод, что в множестве содержится три изоморфных циклических группы мощности 4 и возможно одна нециклическая группа {,,,}. Как показывает проверка множество

{,,,} действительно образует нециклическую диэдральную группу мощности 4 .

5.2 Структура множества

Так как число 5 простое то (5)=4 и в множестве  в соответствии с формулой (5) должно содержаться 4!=24 образующих/генераторов. Каждый генератор формирует цикл длины 5 в котором все элементы кроме  являются образующими. То есть в такой цикл входит 4 беспорядка из множества . Таким образов в множестве  имеется 24/4 =6 циклов длины 5 (с учетом элемента ).

На рис. 2 показано графовое представление множества  .

 

Рисунок 2. Структура множества

 

На рис. 2  не показаны соединения не входящие в кластеры длины 4. В множестве нет кластеров с длиной 4 кроме кластеров образованных циклами генераторов. То есть в этом множестве имеются только циклические группы. Структура множества  характерна для групп в которых n и (n) взаимно простые числа . Это следует из знаменитой теоремы Диксона [6] .

5.3 Структура множества

Так как (6)=2 то в соответствии с формулой (5) множество должно содержать 5!=120 образующих/генераторов и 60 циклов длины 6. Компьютерный анализ показывает, что это множество состоит из 5 блоков. Структура каждого блока показана на рис 3.

Каждый блок сформирован из 12 пересекающихся циклов длины 6 (учитывая общий для всех циклов элемент  который на рисунке не показан).

 

Рисунок 3. Структура блока множества

 

В блок входит 4 структуры . Каждая структура имеет 24 образующих (показаны маленькими кружками) у которых спектр равен 6.  В нижней правой части рисунка показана структура из 3 циклов, раскрашенных разными цветами и имеющих общие элементы  и  со спектром 3. В состав структуры также входят два образующих беспорядка (для красного цикла это ,  ) и один беспорядок со спектром 2 (для красного цикла это  ). Остальные три структуры построены аналогичным образом.

Компьютерный анализ показывает, что в множестве  имеется:

120 образующих со спектром 6;

40 беспорядков со спектром 3;

15 беспорядков со спектром 2;

Всего 175 регулярных беспорядков.

Эти данные можно получить и из формулы (4) подсчитав число элементов с разными спектрами в блоке на рис. 3 и умножив на количество блоков.

6. Примеры построения конечных групп из регулярных беспорядков

6.1 Нециклические конечные группы в симметрической группе

Как показано на рис.1 единственной нециклической группой мощности 4 в множестве  может быть только множество {,,,} которое действительно является диэдральной группой

6.2 Конечные группы в симметрической группе

Как показано на рис 2 множество состоит из 6 циклов длины 5 (с учетом общего элемента ). Все элементы циклов являются образующими. Нециклических групп в этом множестве нет.

6.3 Нециклические конечные группы в симметрической группе

Как показано на рис 3 множество  имеет сложную структуру состоящую из 5 блоков. Поиск конечных групп в множестве можно вести используя необходимое свойство групп – непересечение входящих в группу регулярных беспорядков и приведенную далее теорему о пересечении всех типов групп мощности n с циркулянтной группой <> .

Компьютерная программа сначала строит циркулянтную группу <> . Затем перебирает ее подгруппы <> , <>  и формирует для этих подгрупп множества непересекающихся с этими подгруппами беспорядков . Для построения этих множеств используем понятие расстояния между перестановками .

 =                                                 (10)

Две перестановки (беспорядка) считаются соседями если  >0 .

То есть ищутся непересекающиеся беспорядки π из  для которых >0  и в этом множестве ищутся кластеры мощности 5 которые затем проверяются на замкнутость входящих в них беспорядков.

Аналогично ищутся беспорядки π из  для которых >0  и в этом множестве ищутся кластеры мощности 5 которые затем проверяются на замкнутость входящих в них беспорядков.

Найденные замкнутые кластеры являются группами.

В множестве соседей для цикла <> найдена одна диэдральная группа  показанная в таблице 1.

Таблица 1. 

Диэдральная группа в окрестности <>

 

В множестве соседей для цикла  <> найдены 4 группы изоморфные диэдральной группе

Таблица 2.

Диэдральные группы в окрестности <>

ω	Элементы перестановки
1	1	2	3	4	5	6
2	2	1	4	3	6	5
3	3	6	5	2	1	4
2	4	5	6	1	2	3
3	5	4	1	6	3	2
2	6	3	2	5	4	1

 

ω	Элементы перестановки
1	1	2	3	4	5	6
2	2	1	5	6	3	4
2	3	6	1	5	4	2
2	4	5	6	1	2	3
3	5	4	2	3	6	1
3	6	3	4	2	1	5

 

ω	Элементы перестановки
1	1	2	3	4	5	6
3	2	3	1	6	4	5
3	3	1	2	5	6	4
2	4	5	6	1	2	3
2	5	6	4	3	1	2
2	6	4	5	2	3	1

 

7. Пересечение конечных групп с группой циркулянта

Исследование структуры множества регулярных беспорядков  показало, что для любой конечной группы из n элементов найдется изоморфная ей конечная группа пересекающаяся по элементам с циркулянтной группой

<>. Это следует из того , что любая матрица Кэли конечной группы построчно состоит из регулярных беспорядков (кроме единичной строки) и является обьединением циклов регулярных беспорядков. Тогда в соответствии с формулами (7,9)

={<**x>}                                                         (11)

где **x  k-я степень некоторого генератора  .

Очевидно, что любой цикл < **x > изоморфным преобразованием можно привести к циклу <>. Этим же изоморфным преобразованием группа  приводится к группе пересекающейся с циркулянтным циклом.

Таким образом для поиска всех типов конечных групп мощности n достаточно проводить их поиск в окрестностях циркулянтной группы <> .

8. Заключение.

В статье описан алгоритм формирования образующих регулярных беспорядков множества  и примеры использования этого алгоритма для поиска конечных групп в . Представленный алгоритм по существу описывает циклическую структуру множества  состоящего из (n-1)!/(n) циклов длины n , которые могут иметь общие элементы. Представлены примеры поиска конечных групп с использованием этого алгоритма.

 

Список литературы:

1. Г.П. Гаврилов, А.Д. Сапоженко Сборник задач по дискретной математике // Москва Наука. 1977
2. Э.Б. Винберг Курс алгебры // Москва Факториал. 1999
3. Р. Стенли Перечислительная комбинаторика// Москва Мир. 1990
4. Richard J. Mathar PLOTS OF CYCLE GRAPHS OF THE FINITE GROUPS UP TO ORDER 32//  https://vixra.org/pdf/1406.0183v2.pdf
5. Sami H. Assaf Cyclic Derangements // Department of Mathematics MIT, Cambridge, MA 02139, USA
6. Dieter Jungnickel, On the uniqueness of the cyclic group of order n//  Amer. Math. Monthly, 1992, June–July, p.545–547.