Свободные группы

Git - это свободный моноид: история коммитов - последовательность слов без соотношений. Группы кос - криптография без квантовых уязвимостей. Проблема слов связывает алгебру с неразрешимостью Тьюринга. Свободные группы - не абстракция, а фундамент.

• Пост-квантовая криптография: протоколы на группах кос B_n, где проблема слова вычислительно сложна
• Теория типов: свободные моноиды = списки; свободные группы = группы инвертируемых слов в языках программирования
• Топология: фундаментальная группа поверхности задаётся как <S | R>; проблема гомеоморфизма многообразий связана с проблемой слов

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

• Subgroups and Cosets

Свободная группа: слова без лишних соотношений

Linux kernel: 1.4 миллиона коммитов, формирующих единый свободный моноид. Git - это свободный моноид над операциями коммитов. Каждый merge - конкатенация путей в дереве. Формальные языки, типы в функциональном программировании, протоколы обмена ключами в криптографии на группах кос - везде одна структура: слова с сокращениями.

**Свободная группа** F(S) над множеством S - группа, элементами которой служат все конечные слова из символов S ∪ S⁻¹, с одним правилом сокращения: ss⁻¹ = e и s⁻¹s = e. Никаких других соотношений.

F({a}) ≅ Z: элементы ..., a⁻², a⁻¹, e, a, a², a³, ... Это бесконечная циклическая группа - минимальная свободная группа. F({a, b}) уже содержит слова вроде aba⁻¹b⁻¹, abab⁻²a⁻¹ - все различные, никакого сокращения.

Это **универсальное свойство**: любое отображение порождающих в любую группу G единственным образом продолжается до гомоморфизма из F(S). То есть F(S) - самая большая группа, порождённая S.

Теорема Нильсена-Шрайера: каждая подгруппа свободной группы тоже свободна. Если H <= F_n имеет индекс k, то H ≅ F_{1+k(n-1)}. Подгруппа индекса 2 в F₂ является F₃ - больше порождающих, чем у всей группы!

Представления группы: факторгруппы свободных

**Представление группы** <S | R> - запись вида 'порождающие | соотношения'. Группа G = <S | R> является факторгруппой F(S) по нормальному замыканию R: G ≅ F(S) / <<R>>. Чем больше соотношений - тем меньше группа.

Диэдральная группа Dₙ - симметрии правильного n-угольника: r - поворот на 2π/n, s - отражение. Соотношение srsr = e означает srs⁻¹ = r⁻¹: отражение инвертирует поворот.

Теорема: любая группа G имеет представление <S | R>. Группы, имеющие конечное S и конечное R, называются конечно представленными. Большинство «классических» групп конечно представлены. Но существуют конечно порождённые группы, не являющиеся конечно представленными.

Проблема слов: математика встречает вычислимость

**Проблема слов**: для представления <S | R> и слова w - равно ли w единице в G? В свободной группе разрешимо за линейное время: сократить и проверить пустоту. Но для произвольных конечно представленных групп...

**Теорема Новикова-Бунтинга (1955)**: существуют конечно представленные группы с **неразрешимой** проблемой слов - не существует алгоритма, который всегда правильно отвечает на вопрос 'w = e?'. Это прямая связь с неразрешимостью проблемы остановки Тьюринга.

Это не философия - строгий математический результат. Существуют конкретные конечно представленные группы, в которых нет программы для проверки w = e. Связь: 'машина Тьюринга M останавливается на x' ↔ 'слово w_{M,x} = e в группе G_M'. Теория групп и теория вычислимости пересекаются глубже, чем кажется.

Практическое применение: группы кос B_n используются в пост-квантовой криптографии. Проблема слова в B_n разрешима (алгоритм Гарсайда), но сложность достаточно высока для криптографических задач. Протоколы на основе групп кос предложены как замена RSA.

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

• F(S) = слова над S ∪ S⁻¹ с единственным сокращением ss⁻¹ = e
• Универсальное свойство: любое f: S → G продолжается до φ: F(S) → G - F(S) максимальна
• Любая группа G ≅ F(S)/N(R) - факторгруппа свободной
• <S | R>: больше соотношений = меньше группа (F₂ → D₃ при добавлении r³=e, s²=e, srs=r⁻¹)
• Нильсен-Шрайер: подгруппа F_n свободна; H <= F₂ индекса 2 изоморфна F₃
• Проблема слов неразрешима для некоторых конечно представленных групп - связь с Тьюрингом

Дальнейшие пути

Свободные группы - ключевой объект в геометрической теории групп (действие на деревьях Кэли, гиперболические группы Громова). Представления через <S|R> используются в алгоритмической теории групп.

• Простые группы — Любая группа - факторгруппа F(S); простые группы - 'неразложимые' факторгруппы
• Факторгруппы — G = <S | R> = F(S) / <<R>> - прямое применение конструкции факторгруппы

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

• dm-01