КОЛЬЦА И ИДЕАЛЫ



Hadamard matrix family catalogue and on-line algorithms

© Nickolay A. Balonin, 1.05.2016


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

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

Группы. И конечное поле GF(p) и кольцо R = Zv порождают группы GF(p)* и Z*v (символ * – обозначение перехода к группе) исключением не нужного для мультипликативных групп нулевого элемента.

Поля, это частные случаи колец, например, Zv при v – простое число. Сложение и умножение в поле всегда можно пустить вспять, перейдя к вычитанию и делению. В отличие от теории групп (где берется одна операция), для элементов кольца определены дополнительные операции.

В группе GF(p)* последовательные степени некоторого элемента, т.е. продукты умножения некоторого примитивного элемента x на самого себя, образуют, как известно, циклическую подгруппу x0, x1, x2, ..., xv–1, где v – количество элементов подгруппы.

В кольце R последовательные произведения некоторого элемента g (генератора) на элемент кольца x, образуют циклическое подкольцо gx0, gx1, gx2, ..., gxv–1 (в полиномиальной арифметике соответствует, например, циклическому сдвигу коэффициентов полинома g вправо).

Циклические подгруппы xk и подкольца, называемые орбитами, позволяют изучить состав и характер множеств элементов входящих в мультипликативную группу кольца Z*v.


Орбиты. Орбитой элемента m кольца Z*v называется итог масштабирования подгруппы H (подкольцо): Orb(m)=mH. Умножение на m=0 дает частную орбиту {0} (орбиту элемента 0), умножение на m=1 дает саму подгруппу H в качестве тривиальной орбиты, на m=2 – следующую частную орбиту и т.п. Частные орбиты описывают циклические подкольца кольца.

Масштабирование на элементы Z*v подгруппы H называется также действием подгруппы на кольцо. Орбита подгруппы Orb(H) – обозначение совокупности элементов всех частных орбит, ее и называют для большей простоты, орбитой H.



Подгруппы в Z*v=13, т.е. орбиты m=1 и орбиты m=2



Мы видим, что умножение на разные множители меняет значения элементов mH (элементов строк рисунков). Как обычно, интересуются неподвижными точками mh=m, h – элемент H.

Равные между собой hm=m точки (инварианты действия) можно считать по разному, в подгруппе H (замораживая m) или на множестве Z*v (замораживая h): получая элементы стабилизатора и фиксатора.

Стабилизатор. Равные в результате действия hm=m между собой элементы H образуют подгруппу в H, называемую стабилизатор Stab(m).

Фиксатор. Равные в результате действия hm=m между собой элементы Z*v образуют фиксатор элемента подгруппы Fix(h).



Классы эквивалентности H={8k} в Zv=13


Если орбиты двух элементов Z*v пересекаются, то они тождественны между собой (орбиты разбивают H на классы эквивалентности). Число классов эквивалентности (на рисунке 4) равно сумме числа стабилизаторов (их 16, если посчитать) по всем элементам группы, делённой на размер этой группы (на рисунке 4), согласно лемме Бернсайда.

Идеалы. Для кольца R идеалом называется подкольцо, замкнутое относительно умножения на элементы всего кольца. Более крупные, чем элементы, составляющие кольца, образованные с помощью некоторого элемента или множества, называют идеалами. Например, с помощью числа 2 (умножением на него) мы легко образуем подкольцо четных чисел.

Применение. Масштабированные показательные функции (орбиты) выходят за пределы множества четных чисел. Умножение на 2 устраняет их разноголосицу. Множество всех четных чисел образует идеал с идентификатором 2 (совокупность подколец кольца с общим свойством делимости элементов на 2) в кольце целых чисел.

Абстрактные алгебраические структуры: кольца, идеалы и модули популяризировал Дедекинд, принявший кафедру Гаусса. Исследования Дедекинда были изданы в виде приложения к «Теории чисел» Дирихле. Понятие идеала сформировалось не сразу, можно заметить различие трактовок идеалов. Идеалы, по смыслу, тесно связаны с порождающими их элементами (генераторами), со специфическими метками идеалов – идентификаторами. Основная идея, ради чего были введены идеалы, – если не сами алгебраические числа, определенные в расширенных полях, то хотя бы идеалы, более аморфные числовые конструкции, могут быть однозначно выражены через "произведение" простых идеалов. Что позволяет ввести некоторое осмысленное абстрактное деление. Впервые понятие идеалов (вкладывая несколько иное содержание) предложил Кумер, работавший над обобщением целых чисел Гауссом – комплексных чисел с целочисленными составляющими. В теории чисел аналогами идентификаторов идеалов являются взаимно простые числа.

Во всяком кольце идеалами являются само кольцо и нуль-идеал (нулевой элемент). Идеал, который не совпадает со всем кольцом, называется собственным, а совпадающий – главным идеалом. Кольцо, не содержащее других идеалов, кроме этих двух, называется простым. Все поля (и тела) являются простыми кольцами. Кольцо, которое не образует поле, содержит помимо главного, некоторые собственные идеалы. Определение и роль идеала кольца сходны с определением нормальной подгруппы в теории групп.

Обозначения. Используемое для полиномиальных колец обозначение R = A[x]/(xn–1) берет начало в практике образования расширенных полей. Например, поле комплексных чисел обозначают так C = R(X)/(X2–1). Это означает то, что для образования такого поля используется внешний по отношению к полю вещественных чисел R(X) элемент i, корень неразрешимого уравнения X2–1=0. Уравнение неразрешимо, ну, что же. Его корень мы вовлекаем в игру, получаем расширенное поле с элементами a+ib (или кольцо).

Пример 1. Попытка построить поле GF(22)=GF(4) из A=0, B=1, C=2, D=3 дает таблицы, из которых видно, что для элемента 2 по операции умножения отсутствует обратный (в таблице умножения отличных от нуля элементов появился нулевой элемент A). Таким образом, кольцо Zn является полем только тогда, когда n – простое число.

+
A
B
C
D
A
A
B
C
D
B
B
A
D
C
C
C
D
A
B
D
D
C
B
A
A
B
C
D
A
A
A
A
A
B
A
B
C
D
C
A
B
A
B
D
A
D
C
B


Таблицу умножения поля GF(4) можно исправить. Над полем GF(2) есть только один неприводимый многочлен X2+X+1, соответственно, GF(4) = GF(2)[X]/X2+X+1 (см. поля Галуа).

Напомним, что поле Галуа A=GF(p) с элементами вида C=[c0, c1, ..., cn–1], коэффициентами полиномов, конструируют при помощи дополнительного полинома, позволяющего "замкнуть операции на себя". После чего можно пользоваться привычными нотациями арифметических операций над элементами – полиномами. Операции нижнего уровня над коэффициентами, например, бинарными, соотносят с более просто устроенным обслуживающим поле верхнего уровня конечным полем. В работе участвуют одновременно два поля. В качестве генератора рассматривается обычно некоторый многочлен минимальной степени подкольца – он же делитель многочлена xn–1.

Если кольцо не содержит элемент поля, то этот элемент содержится в другом кольце. Все они вложены в главное кольцо R = A[x]/(p), p(x) – неприводимый полином. Элементы коммутативного кольца – линейные комбинации степеней x с коэффициентами c0, c1, ..., cn–1, определенными, как ранее отмечалось, в обслуживающем операции верхнего уровня поле. Неприводимость – невозможность выразить*) корни полинома элементами обслуживающего операции поля.

*) Неприводимость не означает, что не выражаемый непосредственно корень никак не связан связан с элементами обслуживающего поля и для него нельзя написать пусть формальной, но формулы. Пример у нас перед глазами, когда мы вкладываем некоторое содержание в формулу i = sqrt(–1). С четверкой 2=sqrt(4) функция возвращает вполне себе не выходящее за пределы поля значение. Квадрат мнимой единицы равен вещественному числу. Корень квадратный – это функция (гомоморфизм), содержание которой зависит от элементов, к которой она прилагается.

Показательные функции конечных наборов чисел исследовал Ферма. Разместим в нижнем ряду значения квадратов a2 чисел верхнего ряда по модулю p = 3

0
1
2
3
4
5
6
7
8
9
 ... 
0
1
1
0
1
1
0
1
1
0
 ... 


Уже тут видна закономерность: единицы нижнего ряда. Ферма доказал, что это свойство справедливо для любого простого числа p и любого a (не сравнимого с нулем): ap – 1 = 1 (mod p).

Эйлер привел теорему в более общей формулировке, для любого числа p в условиях прежней теоремы aφ(p) = 1 (mod p), где φ(p) – функция Эйлера: количество чисел, меньших p и взаимно простых с p. Так p = 20 взаимно просто с 1, 3, 7, 9, 11, 13, 17, 19, т.е. φ(20) = 8.

В теореме Ферма φ(p) = p – 1. Пусть a=5 и p=11 взаимно просты, p – простое, φ(p) = p – 1 = 10. Тогда 510 = 1 (mod 11). Среди показателей степени с аналогичными свойствами есть минимальный, его называют порядком числа a.

Циклические коды, последовательности (элементы циклического кольца), в общем, не ортогональны. Это в особенности касается кодов, оперирующих на нижнем уровне переменными {1, –1}, так как есть гипотеза Ризера об отсутствии циклических матриц Адамара степени, большей 4. В теории кодирования для классификации кодов вводится понятие кодового расстояния Хэмминга. В зависимости от расстояний между элементами, выделяют коды информирующие об ошибках или коды исправляющие одну, две и более ошибок.

ЦИКЛИЧЕСКИЕ КОДЫ | КОЛЬЦА

Rambler's Top100