Действия групп и орбиты

Сколько существует различных ожерелий из 10 бусин 4 цветов? Или различных раскрасок граней куба? Без теории действий групп это трудная комбинаторная задача. С ней - элегантная формула. Действия групп - язык, на котором природа описывает симметрию.

• Теория Пойа (расширение леммы Бёрнсайда) используется в химии для подсчёта числа структурных изомеров молекул
• В компьютерной графике и игровом дизайне: генерация уникальных тайлов, карт, паттернов с учётом симметрий - прямое применение теоремы об орбитах

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

• Subgroups and Cosets

Действия групп: определение и примеры

**Действие группы G на множестве X** - это отображение G × X → X, обозначаемое (g, x) ↦ g·x, удовлетворяющее: 1. **Единица:** e·x = x для всех x ∈ X 2. **Ассоциативность:** (gh)·x = g·(h·x) для всех g,h ∈ G, x ∈ X Каждый g ∈ G определяет перестановку σ_g: X → X, x ↦ g·x. Это даёт гомоморфизм G → Sym(X) - **представление группы перестановками**.

**Три канонических действия:** 1. Действие G на себе левым умножением - верное (Теорема Кэли: каждая группа изоморфна подгруппе Sₙ). 2. Действие G на себе сопряжением - орбиты суть классы сопряжённости, стабилизаторы суть централизаторы. 3. Действие G на смежных классах - используется в доказательстве теорем Силова.

**Орбита** элемента x ∈ X: Orb(x) = {g·x | g ∈ G}. **Стабилизатор** элемента x: Stab(x) = {g ∈ G | g·x = x} - это подгруппа G! Множество X разбивается на орбиты (эквивалентность: x ~ y ⟺ ∃g: g·x = y).

Теорема об орбитах и стабилизаторах

**Теорема об орбитах и стабилизаторах:** Для действия G на X и любого x ∈ X: |Orb(x)| × |Stab(x)| = |G| Эквивалентно: |Orb(x)| = [G : Stab(x)] (индекс стабилизатора). Доказательство: отображение G/Stab(x) → Orb(x), gStab(x) ↦ g·x - биекция.

**Следствие: формула числа классов сопряжённости.** При действии G на себе сопряжением: Orb(x) = Cl(x), Stab(x) = C_G(x). Теорема даёт |Cl(x)| = [G : C_G(x)]. Из этого следует уравнение классов: |G| = Σ [G : C_G(xᵢ)], суммируя по представителям классов.

**Транзитивное действие** - когда есть только одна орбита (вся X). В этом случае: |G| = |X| × |Stab(x)| для любого x. Нетранзитивные действия разбивают X на несколько орбит; теорема применяется к каждой орбите отдельно.

Лемма Бёрнсайда: подсчёт с симметрией

**Лемма Бёрнсайда (теорема Пойа-Бёрнсайда):** Число орбит действия конечной группы G на конечном множестве X равно: |X/G| = (1/|G|) × Σ_{g∈G} |Fix(g)| где Fix(g) = {x ∈ X | g·x = x} - множество **неподвижных точек** g.

**Алгоритм подсчёта ожерелий:** 1. Определить группу симметрий G и множество раскрасок X. 2. Для каждого g ∈ G найти |Fix(g)| - число раскрасок, не изменяющихся при действии g. 3. Применить формулу: число различных узоров = (1/|G|) × Σ |Fix(g)|. Ключевое наблюдение: Fix(g) - это раскраски, константные на каждом цикле перестановки g. Если g имеет c(g) циклов при действии на X, то |Fix(g)| = k^{c(g)}, где k - число цветов.

**Историческая путаница:** Лемма называется именем Бёрнсайда, хотя Бёрнсайд сам приписывал её Фробениусу (1887). Настоящее авторство - Фробениус. Это один из самых известных случаев «закона Стиглера»: научные открытия редко называют именем первооткрывателя.

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

• Действие G на X: (g,x) ↦ g·x с условиями e·x=x и (gh)·x=g·(h·x)
• Орбита x: Orb(x) = {g·x | g ∈ G}; Стабилизатор x: Stab(x) = {g | g·x = x} ≤ G
• Теорема об орбитах: |Orb(x)| × |Stab(x)| = |G|
• Лемма Бёрнсайда: |X/G| = (1/|G|) × Σ_{g∈G} |Fix(g)|
• Действие сопряжением: орбиты = классы сопряжённости, стабилизаторы = централизаторы

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

Действия групп - основа для доказательства теорем Силова и для теории представлений. В теории представлений группы действуют на векторных пространствах линейными преобразованиями.

• Теоремы Силова — Доказательство теорем Силова - это искусное применение действия группы на множестве смежных классов
• Разрешимые группы — Уравнение классов (из действия сопряжением) - ключевой инструмент в теории разрешимых групп

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

• Докажите из теоремы об орбитах: если G действует транзитивно на X, то |G| = |X| × |Stab(x)|. Как это связано с теоремой Лагранжа?
• Сколько различных ожерелий из 4 бусин 2 цветов с учётом поворотов и отражений? Используйте лемму Бёрнсайда для D₄.
• Что означает «транзитивное действие» с точки зрения орбит? Приведите пример транзитивного и нетранзитивного действия S₃.

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

• crypto-04-algebraic-structures