Квазигруппа — алгебраическая структура¶
Квазигруппа — алгебраическая структура, состоящая из множества и бинарной операции на нём, обобщение группы, из которого исключено требование ассоциативности и наличия нейтрального элемента. Квазигруппа — множество $Q$ с бинарной операцией $\cdot$, такая, что для любых двух элементов $a, b \in Q$ уравнения $a \cdot x = b$ и $y \cdot a = b$ имеют ровно одно решение в $Q$. Эквивалентно: таблица Кэли (латинский квадрат) операции не содержит повторяющихся элементов ни в строках, ни в столбцах.
¶Определение и свойства
Квазигруппа $(Q, \cdot)$ определяется требованием «сольвентности»: уравнения $a x = b$ и $y a = b$ всегда разрешимы и притом однозначно. Это означает, что в латинском квадрате Кэли каждый элемент встречается ровно один раз в каждой строке и каждом столбце.
Следствия определения:
- В квазигруппе выполняются левые и правые законы сокращения: $a x = a y \Rightarrow x = y$ и $x a = y a \Rightarrow x = y$.
- Нейтральный элемент не обязателен. Квазигруппа с нейтральным элементом, но без ассоциативности, называется квазигруппой с единицей (или унитарной квазигруппой).
- Ассоциативная квазигруппа является группой. Таким образом, группы — частный случай квазигрупп.
¶Основные понятия
¶Левый и правый нейтральный элементы
В квазигруппе могут существовать левая и правая единицы, не совпадающие друг с другом. Если левая и правая единицы совпадают, это единица в обычном смысле. Унитарная квазигруппа, в которой левая и правая единицы различны, называется квазигруппой с двумя единицами.
¶Перевёртыши
Для квазигруппы $(Q, \cdot)$ определяются три операции-перевёртыша:
- левый: $x \backslash a$ — решение уравнения $x \cdot y = a$;
- правый: $a / x$ — решение уравнения $y \cdot x = a$;
- третий: $x * a$ — решение уравнения $y \cdot x = a$ (иногда определяется иначе, в зависимости от принятых соглашений).
Эти операции превращают квазигруппу в структуру с шестью операциями, что важно при изучении идентификационных соотношений.
¶Квазигруппа с инволюцией
Квазигруппа с унарной операцией $x \mapsto x^{-1}$, такой, что $x \cdot (x^{-1} \cdot a) = a$ и $(a \cdot x^{-1}) \cdot x = a$, называется квазигруппой с инволюцией. Такие структуры возникают в комбинаторике и теории кодирования.
¶Классификация
¶Типы квазигрупп
По свойствам операции квазигруппы делятся на типы (соотношения между операциями $\cdot, \backslash, /, *$):
- I тип — ассоциативная (группа);
- II тип — латинская квазигруппа с инволюцией;
- III тип — квазигруппа Риба (полугруппа с инволюцией);
- IV тип — квазигруппа Риба-Мушина-Штейнбаха;
- V тип — альтернативная квазигруппа;
- VI тип — квазигруппа Штейнбаха.
Эта классификация, связанная с работами Белькина, Риба, Мушина и Штейнбаха, описывает соотношения между шестью операциями квазигруппы.
¶Квазиполоса
Квазиполоса (квазигруппа с идемпотентностью) — квазигруппа, в которой $x \cdot x = x$ для всех $x$. Квазиполосы не являются группами, кроме тривиального случая одного элемента. Они изучаются в рамках общей алгебры и комбинаторики.
¶Примеры
- Множество $\{1, 2, 3\}$ с операцией $a \cdot b = $ остаток от деления $a + b + 1$ на 3 (со сдвигом) образует квазигруппу, не являющуюся группой.
- Любая группа является квазигруппой.
- Множество ненулевых рациональных чисел с операцией $a \cdot b = a/b$ — квазигруппа без единицы (деление не ассоциативно).
¶Применение
¶Теория кодирования
Квазигруппы применяются в теории кодирования: построение кодов на квазигруппах позволяет получать устойчивые к ошибкам коды, в частности, для коррекции и обнаружения ошибок в системах связи. Работы по кодам на квазигруппах принадлежат в том числе российским математикам (И. В. Чистяков, В. Д. Белькин).
¶Теория графов и комбинаторика
Квазигруппы естественно связаны с латинскими квадратами и ортогональными латинскими квадратами. Теорема Тарри (1960) о числе ортогональных латинских квадратов и связанная с ней задача Эйлера о 36 офицерах решаются средствами теории квазигрупп.
¶Криптография
На квазигруппах строятся некоторые схемы блочного шифрования, основанные на сложности решения уравнений в квазигруппах и на неассоциативности операции.
¶Теория автоматов и формальных языков
Квазигруппы и квазиполосы используются при описании порождения формальных языков: слово порождается квазигруппой, если оно можно сократить до пустого слова последовательным применением правил $x \cdot x^{-1} \to \varepsilon$ и $x^{-1} \cdot x \to \varepsilon$.
¶История
Понятие квазигруппы введено в 1920-е годы в работах Д. Кёнига и Г. Дезарга, а также в трудах О. Шрайера и Б. Л. ван дер Вардена. Систематическое развитие теория получила в работах А. А. Гвоздева, О. И. Гельфанда, а позднее — В. Д. Белькина, В. В. Риба, А. В. Мушина и П. Штейнбаха. В СССР теория квазигрупп и латинских квадратов развивалась в том числе в Новосибирске и Саратове.
¶Источники
- Курочкин А. М., Мельников И. С. «Алгебраические квазигруппы»
- Белькин В. Д. «Квазигруппы и латинские квадраты»
- Риб В. В. «Квазигруппы и проблемы реализации»
- Гвоздев А. А. «Структуры, определяемые латинскими квадратами»
- Дембовицкий В. А. «Квазигруппы и латинские квадраты»
- Штейнбах П. «Quasigroups: theory and applications»