Подгруппы и теорема Лагранжа

2022 год. DeepMind публикует AlphaFold2 - модель, решившую задачу свёртки белков, над которой биологи работали 50 лет. Пресса писала про нейросети. Тихо за кулисами стояла другая математика: группа SE(3) и её подгруппы. Модель буквально не могла предсказать физически невозможную конфигурацию - не потому что «обучена не делать», а потому что архитектура сама живёт в пространстве, где такая конфигурация не существует. Это и есть сила подгрупп.

• SE(3)-эквивариантные сети в молекулярном ML - симметрии белков как подгруппы вращений
• Diffie-Hellman и ECDSA: безопасность опирается на структуру подгрупп в $\mathbb{Z}_p^*$ и эллиптических кривых
• Свёрточные нейросети: разделение весов = факторизация по подгруппе сдвигов $\mathbb{Z}^2$
• Теорема Лагранжа объясняет, почему хеш-таблицы размером $p$ (простого) имеют лучшую структуру

Предварительные знания

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

Подгруппа: группа внутри группы

AlphaFold2 предсказывает структуру белка с атомарной точностью - погрешность меньше ширины атома. За этим стоит не только нейросеть, но и математика: специальная евклидова группа SE(3) вращений и переносов в 3D-пространстве. Допустимые конфигурации аминокислот - это **подгруппы** SE(3). Модель знает физически допустимые формы именно потому, что обучена уважать эти подгруппы.

Подмножество $H \subseteq G$ называется **подгруппой** группы $G$ (запись $H \leq G$), если $H$ само является группой с той же операцией. Формально достаточно трёх условий: $H$ непусто, замкнуто относительно операции, и содержит обратный к каждому своему элементу.

**Одношаговый критерий подгруппы.** $H \leq G$ тогда и только тогда, когда $H$ непусто и для любых $a, b \in H$ выполняется $a \cdot b^{-1} \in H$. Один критерий заменяет три аксиомы: нейтральный элемент получается подстановкой $a = b$, а обратный - подстановкой $a = e$.

В любой группе $G$ всегда есть две подгруппы - $\{e\}$ и сама $G$. Их называют **тривиальными**. Остальные - **собственные**. Интересный факт: если $|G| = p$ (простое), собственных подгрупп нет вообще. Именно это свойство эксплуатирует криптография.

Смежные классы: разбиение без остатка

Свёрточные сети не замечают сдвига изображения. Кошка слева - та же кошка справа. Это не магия и не эвристика - это **эквивариантность** к группе сдвигов $\mathbb{Z}^2$. Разделение весов в Conv-слое математически эквивалентно разбиению пространства признаков на смежные классы по подгруппе сдвигов. Понять смежные классы - понять, почему CNN работает.

**Левый смежный класс** элемента $a$ по подгруппе $H$ - это множество $aH = \{a \cdot h \mid h \in H\}$. Правый класс - $Ha = \{h \cdot a \mid h \in H\}$. В абелевых группах они совпадают. Ключевое свойство: любые два смежных класса либо совпадают, либо не пересекаются.

**Левый класс $\neq$ правый класс** в общем случае. Если $aH = Ha$ для всех $a \in G$, подгруппа называется **нормальной** ($H \trianglelefteq G$). Нормальные подгруппы - это именно те, по которым можно строить факторгруппы. Пример ненормальной подгруппы: подгруппа вращений $\{e, r\}$ в группе симметрий треугольника $S_3$.

Теорема Лагранжа: порядок делит порядок

Почему в Diffie-Hellman выбирают простое $p$? Ответ - теорема Лагранжа. В группе $\mathbb{Z}_p^*$ порядка $p-1$ порядок любого элемента делит $p-1$. Если выбрать элемент $g$ простого порядка $q$ - получится подгруппа из $q$ элементов. Злоумышленнику придётся перебирать $q$ вариантов, и никакого «срезания угла» нет: нет нетривиальных подгрупп порядка, не делящего $q$.

**Теорема Лагранжа.** Если $G$ - конечная группа и $H \leq G$, то $|H|$ делит $|G|$. Точнее: $|G| = |H| \cdot [G:H]$, где $[G:H]$ - число смежных классов (**индекс** подгруппы $H$ в $G$). Доказательство элегантно: все смежные классы имеют одинаковый размер $|H|$ и не пересекаются - они буквально складываются в $G$.

**Обратное утверждение неверно.** Если $d$ делит $|G|$, подгруппы порядка $d$ может не существовать. Контрпример: $A_4$ - группа чётных перестановок четырёх элементов, $|A_4| = 12$, но подгруппы порядка $6$ нет, хотя $6 \mid 12$. Теорема Лагранжа - это ограничение сверху, а не гарантия существования.

В теории групповой эквивариантности для нейросетей (Geometric Deep Learning, Cohen et al., 2016) именно подгруппы определяют допустимые симметрии. E(3)-эквивариантные сети - те, что уважают подгруппы трёхмерной группы Евклида: вращения SO(3), отражения, переносы. AlphaFold2 использует SE(3)-эквивариантный модуль Invariant Point Attention. Теорема Лагранжа гарантирует, что дискретные симметрии белка образуют подгруппу с предсказуемой структурой.

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

• $H \leq G$ - подгруппа: непустое подмножество, замкнутое по операции и взятию обратного. Критерий: $a, b \in H \Rightarrow ab^{-1} \in H$
• Тривиальные подгруппы - $\{e\}$ и $G$. Группа простого порядка не имеет других
• Смежный класс $aH = \{ah \mid h \in H\}$ - сдвиг подгруппы на элемент $a$
• Смежные классы разбивают $G$ на непересекающиеся части одинакового размера $|H|$
• **Теорема Лагранжа**: $|H|$ делит $|G|$, индекс $[G:H] = |G|/|H|$
• Следствия: порядок элемента делит $|G|$; группа простого порядка - циклическая; малая теорема Ферма

Что дальше

Подгруппы - фундамент. На нём строятся гомоморфизмы, факторгруппы и в конечном счёте теория Галуа, объясняющая, почему уравнение пятой степени не решается в радикалах.

• Гомоморфизмы и изоморфизмы — Ядро гомоморфизма - нормальная подгруппа; образ - подгруппа
• Факторгруппы — Факторгруппа G/H строится из смежных классов H
• Теоремы Силова — Частичное обращение теоремы Лагранжа для подгрупп простой степени
• Алгебра и криптография — Структура подгрупп напрямую определяет безопасность протоколов

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

• Почему смежные классы не могут пересекаться? Попробуйте доказать это от противного: если $a \in xH \cap yH$, что можно сказать о $xH$ и $yH$?
• Если $|G| = 12$, какие порядки могут иметь элементы $G$? Какие порядки невозможны - и почему?
• В SE(3)-эквивариантных сетях предсказания не меняются при повороте молекулы. Что играет роль подгруппы в этой конструкции?

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

• aa-03-homomorphisms — Ядро гомоморфизма - нормальная подгруппа; без этого урока нет смысла
• aa-06-quotient — Факторгруппа строится именно по смежным классам
• aa-07-sylow — Теоремы Силова - глубокое обобщение теоремы Лагранжа
• aa-21-algebra-crypto — Diffie-Hellman и ECDSA прямо используют структуру подгрупп
• aa-30-algebra-ml — SE(3)-эквивариантность в AlphaFold2 - подгруппы 3D-симметрий
• nt-03