Лемма Бёрнсайда

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

В теории групп лемма Бёрнсайда (иногда встречается название «лемма Коши-Фробениуса») связывает количество орбит в подгруппе симметрической группы с цикловой структурой элементов этой подгруппы. Существует несколько вариантов леммы: упрощенный, весовой, ограниченный и т. д. Лемма Бёрнсайда лежит в основе доказательства теоремы Редфилда — Пойа.

Упрощенный вид[править | править вики-текст]

Пусть G — конечная группа подстановок, действующая на множестве X. Для любого элемента g из G будем обозначать через X^g множество элементов X, оставляемых на месте g. Лемма Бёрнсайда даёт формулу числа орбит группы G, обозначаемого |X/G|:

|X/G|=\frac{1}{|G|}\sum_{g\in G}|X^g|.

Число орбит (натуральное число или бесконечность) равно среднему количеству точек, оставляемых на месте элементом из G.

Доказательство[править | править вики-текст]

Доказательство основано на подсчёте числа элементов одного множества двумя способами:

\sum_{g \in G}|X^g| = |\{(g,x)\in G\times X \mid g\cdot x = x\}| = \sum_{x \in X} |G_x| =
= \sum_{x \in X} \frac{|G|}{|Gx|} = |G| \sum_{x \in X}\frac{1}{|Gx|} = |G|\sum_{A\in X/G}\sum_{x\in A} \frac{1}{|A|} =
= |G| \sum_{A\in X/G} 1 = |G| \cdot |X/G|.


Весовой вид[править | править вики-текст]

\sum_{j=1}^{N(G)}W({O}^j)=|G|^{-1}\sum_{\pi\in G}\sum_{a=\pi(a)}\omega(a),

где W({O}^j) — вес орбиты O^j (вес любого её представителя), \omega(a) — вес элемента.

История открытия[править | править вики-текст]

Уильям Бёрнсайд сформулировал и доказал эту лемму (без указания авторства) в одной из своих книг (1897 год), но историки математики обнаружили, что он не был первым, кто открыл её. Коши в 1845 году и Фробениусу в 1887 году также была известна эта формула. По-видимому, лемма была столь хорошо известна, что Бёрнсайд просто опустил указание авторства Коши. Поэтому эта лемма иногда называется леммой не Бёрнсайда. Это название не столь туманно, как кажется: работа Бёрнсайда была столь плодотворной, что большинство лемм в этой области принадлежит ему.

Литература[править | править вики-текст]

  • Burnside, William Theory of groups of finite order. — Cambridge University Press, 1897.