Группы: первые шаги в абстрактную алгебру

Рубик - 43 квинтиллиона состояний ($4.3 \times 10^{19}$), но любое решается за 20 ходов. Почему? Это группа. Объект, открытый Эваристом Галуа - в 21 год, за ночь до дуэли на которой его убьют. Он написал теорию группы за несколько часов и оказался прав. Сегодня группа $SU(3)$ описывает кварки в Большом Адронном Коллайдере.

• RSA-шифрование работает в группе $(\mathbb{Z}/n\mathbb{Z})^*$, AES - в поле $GF(2^8)$. Каждый HTTPS-запрос использует теорию групп
• Группа $SU(3)$ описывает сильное взаимодействие (кварки), $SU(2) \times U(1)$ - электрослабое. Стандартная модель физически и есть теория симметрийных групп
• Свёрточные нейросети (CNN) инвариантны к сдвигу именно потому, что пространственные сдвиги образуют группу - трансляционная симметрия встроена в архитектуру
• God's Algorithm нашёл все 20-ходовые решения кубика, полностью перебрав группу порядка $4.3 \times 10^{19}$ с помощью теории Шрайера-Симса

Эварист Галуа и рождение теории групп

Май 1832. Париж. Двадцатилетний Галуа знает, что завтра умрёт на дуэли. Всю ночь пишет. За несколько часов формулирует теорию, объясняющую почему уравнения пятой степени нельзя решить в радикалах - ответ в симметриях корней, которые он называет группами. Утром отдаёт другу: «Нет времени». На следующий день смертельно ранен. 20 лет. Его заметки лежат нечитанными 14 лет - пока Лиувилль не публикует их в 1846. С этого момента абстрактная алгебра перестаёт быть математической экзотикой.

Что такое группа: четыре аксиомы

Эварист Галуа в 1832 году задал один вопрос: что общего у симметрий корней уравнения? Ответ оказался универсальным. Одна и та же абстракция описывает ходы кубика Рубика, повороты кристалла, перестановки нуклеотидов и преобразования в квантовой механике. Эта абстракция - группа.

**Группа** $(G, *)$ - это множество $G$ с бинарной операцией $*$, удовлетворяющей четырём аксиомам: замкнутость, ассоциативность, существование нейтрального элемента и существование обратных.

Важная деталь: коммутативности $a*b = b*a$ в определении нет. Это необязательное свойство. Группы, где она выполняется, называются **абелевыми** - в честь Нильса Абеля. Группы, где нет - неабелевыми. Ходы кубика Рубика образуют неабелеву группу: сначала повернуть верхний слой, потом правый - это не то же, что сначала правый, потом верхний.

$(\mathbb{N}, +)$ - не группа: у натурального числа $5$ нет обратного в $\mathbb{N}$. $(\mathbb{Z}, \cdot)$ - не группа: у $2$ нет обратного в целых числах ($1/2 \notin \mathbb{Z}$). Операция - неотъемлемая часть структуры. Одно множество с разными операциями - разные алгебраические объекты.

Примеры групп: от часов до кварков

Теория групп могла остаться абстрактной игрой. Вместо этого оказалось, что группы - везде. AES-шифрование работает в поле $GF(2^8)$, мультипликативная часть которого - циклическая группа. Группа $SU(3)$ - это не метафора для кварков, это буквально математика, предсказывающая их свойства. CNN-свёртки инвариантны к сдвигу именно потому, что пространственные сдвиги образуют группу.

**Абелева vs неабелева**: $(\mathbb{Z}, +)$, $(\mathbb{Z}_n, +)$, $(\mathbb{Q}^*, \cdot)$ - абелевы. $D_4$, $S_n$ при $n \geq 3$, группа ходов кубика Рубика - неабелевы. Большинство «интересных» групп в физике и криптографии - неабелевы.

Порядок элемента и изоморфизм

Ход кубика, повторённый снова и снова, всегда возвращает кубик в исходное положение. Число повторений - порядок элемента. Это понятие проникает везде: порядок элемента в $(\mathbb{Z}/p\mathbb{Z})^*$ - основа теорем Ферма и Эйлера, которые лежат в фундаменте RSA.

**Порядок элемента** $g \in G$ - наименьшее натуральное $n$ такое, что $g^n = e$. Обозначение: $\text{ord}(g)$ или $|g|$. Если такого $n$ не существует - порядок бесконечен. **Порядок группы** $|G|$ - количество элементов. Для бесконечных групп - $\infty$.

Две группы могут выглядеть совершенно по-разному, но иметь одинаковую структуру. Группа вращений правильного шестиугольника и $\mathbb{Z}_6$ - одно и то же, просто записанное разным языком. Это фиксирует понятие изоморфизма.

**Изоморфизм групп** $(G, *) \cong (H, \circ)$ - биекция $\varphi: G \to H$ такая, что $\varphi(a * b) = \varphi(a) \circ \varphi(b)$. Изоморфные группы неразличимы с алгебраической точки зрения - это «одна и та же группа в разных обозначениях».

**Быстрый тест на неизоморфизм**: если порядки элементов не совпадают - группы неизоморфны. В $\mathbb{Z}_4$ есть элемент порядка 4. В $\mathbb{Z}_2 \times \mathbb{Z}_2$ все ненейтральные элементы имеют порядок 2. Значит $\mathbb{Z}_4 \not\cong \mathbb{Z}_2 \times \mathbb{Z}_2$, хотя обе имеют 4 элемента.

Ключевые идеи

• Группа $(G, *)$ - четыре аксиомы: замкнутость, ассоциативность, нейтральный элемент $e$, обратные $a^{-1}$. Коммутативность - необязательна
• Абелева группа: $a*b = b*a$ для всех элементов. $(\mathbb{Z}, +)$ - абелева. $D_4$, $S_n$ при $n \geq 3$ - неабелевы
• Порядок элемента $\text{ord}(g)$ - минимальное $n$ с $g^n = e$. В $\mathbb{Z}_n$: $\text{ord}(k) = n/\gcd(k,n)$
• Изоморфизм $G \cong H$ - биекция, сохраняющая операцию. Изоморфные группы - одна структура в разных обозначениях
• Теорема Кэли: любая конечная группа вложена в $S_n$. Теория групп - единый язык для кубика Рубика, кристаллов и кварков

Что дальше

Группы - только начало. Внутри групп живут подгруппы, между группами - гомоморфизмы. Из этого вырастает вся современная алгебра.

• Подгруппы и смежные классы — Теорема Лагранжа: порядок подгруппы делит порядок группы - это ключ к RSA
• Гомоморфизмы и изоморфизмы — Структуросохраняющие отображения между группами - язык классификации

Вопросы для размышления

• Кубик Рубика имеет порядок группы $4.3 \times 10^{19}$, но любое состояние решается за 20 ходов. Как это возможно - какое свойство структуры группы это обеспечивает?
• Группа $SU(3)$ описывает кварки. Что значит, что элементарные частицы соответствуют неприводимым представлениям группы?
• Перемешивание карт - перестановка из $S_{52}$. Сколько раз нужно применить идеальное перемешивание (riffle shuffle), чтобы колода вернулась в исходный порядок?

Связанные уроки

• nt-03