6.3. ТЕОРИЯ ГРУПП

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

Группой называется множество элементов с операцией, обозначаемой символом, обладающей следующими свойствами.

1. Для любых элементов принадлежащих множеству, также принадлежит множеству.

2. Выполняется ассоциативный закон, т. е. для любых принадлежащих множеству,

3. В множестве имеется нейтральный элемент такой, что а для всех а, принадлежащих множеству.

4. Для любого элемента а из множества существует принадлежащий множеству обратный элемент удовлетворяющий соотношениям

Абелева (или коммутативная) группа определяется как группа, для которой также выполняется коммутативный закон:

Ниже наибольший интерес будут представлять абелевы группы.

Введенная выше операция во многом подобна обычному умножению, и нетрудно убедиться, что множество обычных ненулевых действительных чисел с операцией обычного умножения удовлетворяет всем аксиомам группы. С равным успехом, однако, операцией в группе может быть сложение или любая другая произвольным образом введенная операция. Например, целые числа с операцией сложения образуют группу. В этом случае О является нейтральным элементом, а обратным элементом для а служит —а. Аналогично, элементы О и 1 образуют группу, в которой операцией является сложение по модулю 2. Во всех случаях, когда операция в группе обозначается знаком или 0, условимся обозначать нейтральный элемент знаком О, а элемент, обратный для элемента а, через —а.

Следующие свойства полезно знать при работе с группами. Пусть нейтральный элемент, определяемый соотношением (6.3.2), а — произвольный элемент группы и обратный элемент для элемента а [см. (6.3.3)]. Первые два приведенных ниже свойства утверждают единственность элементов

1. Единственным элементом х, для которого является

2. Единственным х, для которого а является

3. Если то с.

4. Уравнение а имеет единственное решение

Чтобы проверить свойство 1, умножим обе части равенства на получим или или Свойства 2, 3 и 4 доказываются аналогично.

Подгруппы

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

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

Порядком группы или подгруппы называется число элементов в группе или подгруппе. Следующая теорема Лагранжа содержит важный результат.

Теорема 6.3.1. (Лагранж.) Порядок группы, если он конечен, кратен порядку каждой подгруппы.

Нам потребуется несколько вспомогательных результатов. Правым смежным классом (левым смежным классом) группы по подгруппе называется подмножество элементов где а — произвольный заданный элемент группы все элементы Непосредственно можно убедиться, что для подгруппы конечного порядка число элементов в смежном классе равно числу элементов в подгруппе, так как если то Кроме того, если два правых смежных класса (левых смежных класса) одной и той же подгруппы имеют какой-либо общий элемент, то эти два подмножества совпадают. Чтобы доказать это, предположим, что одно подмножество порождается элементом а, а другое — элементом Если то принадлежит смежному классу, порождаемому а. Поэтому для любого принадлежащего а и любой элемент смежного класса, порождаемого принадлежит смежному классу, порождаемому а.

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

Теперь можно доказать теорему 6.3.1. Предположим, что группа порядка содержит подгруппу порядка Если то выберем элемент группы не принадлежащий и образуем правый смежный класс. Подгруппа и смежный класс вместе содержат элементов; если то можно выбрать другой элемент в не принадлежащий ни подгруппе, ни смежному классу, и образовать новый правый смежный класс, что даст нам в совокупности элементов. Продолжая таким образом, в конце концов достигнем того, что все элементы будут принадлежать либо либо одному из смежных классов; если кроме подгруппы существуют и смежных классов, то получим что завершает доказательство,

Циклические подгруппы

Пусть а — элемент конечной группы Рассмотрим последовательность элементов

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

Согласно (6.3.5) отсюда следует, что Порядком элемента а группы называется наименьшее положительное целое число для которого Приведенные выше рассуждения показывают, что каждый элемент конечной группы имеет конечный порядок. Более того, элементы должны быть различными, поскольку равенство где может выполняться лишь при Поэтому последовательность (6.3.9) степеней элемента а имеет следующее циклическое свойство:

Из (6.3.11) следует, что тогда и только тогда, когда кратно

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

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

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

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

Лемма. Пусть а — элемент порядка элемент порядка в абелевой группе. Тогда, если тип взаимно простые, то порядок элемента а равен

Доказательство. Имеем

Поэтому, обозначив порядок элемента а через получим Кроме того,

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

Теорема 6.3.3. Пусть максимальный порядок элементов конечной абелевой группы. Тогда кратно порядку каждого элемента группы.

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

где целые неотрицательные числа. Если не кратно то для некоторого должно выполняться Пусть далее для любого через обозначен элемент порядка (такой элемент равен а в степени Аналогично, пусть есть элемент порядка Рассмотрим теперь элемент Последовательно применяя предыдущую лемму при каждом включении нового сомножителя в это произведение, убеждаемся, что с имеет порядок Это привело к противоречию, поскольку равно наибольшему порядку элементов; поэтому кратно .