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

Лемма Бернсайда , иногда также называемая теоремой Бернсайда о подсчете , леммой Коши-Фробениуса или теоремой о подсчете орбит , является результатом теории групп , который часто полезен при учете симметрии при подсчете математических объектов. Он был открыт Огюстеном Луи Коши и Фердинандом Георгом Фробениусом и стал широко известен после того, как Уильям Бернсайд . его процитировал ^{[ 1 ]} Результат перечисляет орбиты группы симметрии, действующей на некоторые объекты: то есть он подсчитывает отдельные объекты, считая объекты, симметричные друг другу, одинаковыми; или подсчет различных объектов с точностью до симметрии отношения эквивалентности ; или считать только объекты в канонической форме . Например, при описании возможных органических соединений определенного типа их рассматривают с точностью до симметрии пространственного вращения: разные повернутые изображения данной молекулы химически идентичны. (Однако зеркальное отражение может дать другое соединение .)

Формально, G — конечная группа , действующая на множестве X. пусть Для каждого g из G пусть X ^г обозначают набор элементов в X , которые зафиксированы g ( инвариант слева g ): то есть X ^г знак равно { Икс ∈ Икс | г . х = х }. Лемма Бернсайда утверждает следующую формулу для числа орбит , обозначаемого | Х / Г |: ^{[ 2 ]}

$|X/G|={\frac {1}{|G|}}\sum _{g\in G}|X^{g}|.$

Таким образом, количество орбит ( натуральное число или +∞ ) равно среднему количеству точек, зафиксированных элементом G . Для бесконечной группы G все еще существует биекция :

$G\times X/G\ \longleftrightarrow \ \coprod _{g\in G}X^{g}.$

Примеры приложений к перечислению

Ожерелья

Существует 8 возможных битовых строк длиной 3, но соединение концов строки дает только четыре различных двухцветных ожерелья длины 3, заданных каноническими формами 000, 001, 011, 111: остальные строки 100 и 010 эквивалентны 001 путем вращения, а 110 и 101 эквивалентны 011. То есть эквивалентность вращения разбивает набор X строк на четыре орбиты:

$X=\{{\texttt {000}}\}\cup \{{\texttt {001}},{\texttt {010}},{\texttt {100}}\}\cup \{{\texttt {011}},{\texttt {101}},{\texttt {110}}\}\cup \{{\texttt {111}}\}.$

Формула Бернсайда использует количество вращений, равное 3, включая нулевое вращение, и количество битовых строк, остающихся неизменными при каждом вращении. Все 8-битные векторы не изменяются при нулевом вращении, а два (000 и 111) не изменяются при двух других вращениях. Таким образом, количество орбит равно:

$4={\frac {1}{3}}(8+2+2).$

Для длины 4 существует 16 возможных битовых строк; 4 вращения; нулевой поворот оставляет все 16 строк неизмененными; при первом и третьем поворотах две строки остаются неизменными (0000 и 1111); 2-кратное вращение оставляет неизменными 4 битовые строки (0000, 0101, 1010, 1111). Таким образом, количество различных ожерелий составляет: $6={\tfrac {1}{4}}(16+2+4+2)$ , представленный каноническими формами 0000, 0001, 0011, 0101, 0111, 1111.

Общий случай n битов и k цветов определяется полиномом ожерелья .

Раскраски куба

Лемма Бернсайда позволяет вычислить количество различных по вращению раскрасок граней куба, используя три цвета.

Пусть X — набор из 3 ⁶ возможные комбинации цветов граней, которые можно применить к фиксированному кубу, и пусть группа вращения G куба действует на X , перемещая цветные грани: две раскраски в X принадлежат одной и той же орбите именно тогда, когда одна из них является вращением другой. Различные вращательные раскраски соответствуют групповым орбитам и могут быть найдены путем подсчета размеров фиксированных наборов для 24 элементов G , причем раскраски остаются неизменными при каждом вращении:

элемент идентификации фиксирует все 3 ⁶ раскраски
шесть поворотов лица на 90 градусов каждый, исправление 3 ³ раскраски
три поворота лица на 180 градусов каждый исправить 3 ⁴ раскраски
восемь поворотов вершин на 120 градусов каждый, исправление 3 ² раскраски
шесть поворотов кромки на 180 градусов каждый исправить 3 ³ раскраски.

Подробное обследование можно найти здесь .

Таким образом, средний размер фиксированного набора составляет:

|X/G|={\frac {1}{24}}\left(3^{6}+6\cdot 3^{3}+3\cdot 3^{4}+8\cdot 3^{2}+6\cdot 3^{3}\right)=57.

Существует 57 вращательно различных раскрасок граней куба в три цвета. В общем случае количество различных по вращению раскрасок граней куба в n цветов равно:

{\frac {1}{24}}\left(n^{6}+3n^{4}+12n^{3}+8n^{2}\right).

Доказательство

В доказательстве леммы Бернсайда первым шагом является перевыражение суммы по элементам группы g ∈ G как эквивалентной суммы по множеству элементов x ∈ X :

\sum _{g\in G}|X^{g}|=\#\{(g,x)\in G\times X\mid g\cdot x=x\}=\sum _{x\in X}|G_{x}|.

Здесь Х ^г знак равно { Икс ∈ Икс | gx = x } — множество точек X , фиксированных g ∈ G , тогда как G _x = { g ∈ G | gx = x } — подгруппа стабилизатора группы G, симметрии, фиксирующие точку x ∈ X .)

Теорема о стабилизаторе орбиты утверждает, что для каждого x ∈ X существует естественная биекция между орбитой G·x = { g·x | g ∈ G } и множество левых смежных классов G/G _x . Теорема Лагранжа подразумевает:

|G\cdot x|=[G\,:\,G_{x}]=|G|/|G_{x}|.

Таким образом, сумму можно переписать как:

\sum _{x\in X}|G_{x}|=\sum _{x\in X}{\frac {|G|}{|G\cdot x|}}=|G|\sum _{x\in X}{\frac {1}{|G\cdot x|}}.

Записывая X как непересекающееся объединение его орбит в X/G :

|G|\,\sum _{x\in X}{\frac {1}{|G\cdot x|}}\ =\ |G|\!\sum _{A\in X/G}\,\sum _{x\in A}{\frac {1}{|A|}}\ =\ |G|\!\sum _{A\in X/G}1\ =\ |G|\,|X/G|.

Собрав все вместе, вы получите желаемый результат:

\sum _{g\in G}|X^{g}|=|G|\cdot |X/G|.

Это похоже на доказательство уравнения класса сопряженности , которое рассматривает действие сопряжения G на самого себя: X = G и g . х = гхг ⁻¹, так что стабилизатор x является централизатором : G _x = Z _G ( x ).

Перечисление против генерации

Лемма Бернсайда учитывает отдельные объекты, но не создает их. В общем, комбинаторная генерация с отклонением изоморфа рассматривает симметрии g на объектах x . Но вместо проверки того, что gx = x , он проверяет, что gx еще не был сгенерирован. Один из способов добиться этого — проверить, что gx лексикографически не меньше x , используя лексикографически наименьший член каждого класса эквивалентности в качестве канонической формы класса. ^{[ 3 ]} Подсчет объектов, созданных с помощью такого метода, может подтвердить правильность применения леммы Бернсайда.

История: лемма, которая не принадлежит Бернсайду

Уильям Бернсайд сформулировал и доказал эту лемму в своей книге о конечных группах 1897 года, приписав ее Фробениусу (1887) . Но еще до Фробениуса формула была известна Коши в 1845 году. Следовательно, эту лемму иногда называют леммой, не являющейся леммой Бернсайда . ^{[ 4 ]} Неправильное наименование научных открытий называется законом эпонимии Стиглера .

См. также

Примечания

^ Бернсайд 1897 , §119
^ Ротман 1995 , Глава 3
^ Калл, Пол; Панди, Раджив (1994). «Изоморфизм и проблема N-ферзей» . Бюллетень ACM SIGCSE . 26 (3): 29–36. дои : 10.1145/187387.187400 . S2CID 207183291 .
^ Нойманн, Питер М. (1979). «Лемма, которая не принадлежит Бернсайду». Ученый-математик . 4 (2): 133–141. ISSN 0312-3685 . МР 0562002 . .

Ссылки

Бернсайд, Уильям (1897). Теория групп конечного порядка . Издательство Кембриджского университета – через Project Gutenberg . Также доступно здесь, на Archive.org . Бернсайда (Это первое издание; во введении ко второму изданию содержится знаменитый резкий поворот относительно полезности теории представлений .)
Фробениус, Фердинанд Георг (1887), «О сравнении согласно двойному модулю, образованному из двух конечных групп», Crelle's Journal , 101 (4): 273–299, doi : 10.3931/e-rara-18804 .
Ченг, Юанью (1986). «Обобщение леммы Бернсайда на умножение транзитивных групп». Журнал Технологического университета Хубэй . ISSN 1003-4684 . .
Ротман, Джозеф (1995), Введение в теорию групп , Springer-Verlag, ISBN 0-387-94285-8 .

[1] Бернсайд 1897 , §119

[2] Ротман 1995 , Глава 3

[3] Калл, Пол; Панди, Раджив (1994). «Изоморфизм и проблема N-ферзей» . Бюллетень ACM SIGCSE . 26 (3): 29–36. дои : 10.1145/187387.187400 . S2CID 207183291 .

[4] Нойманн, Питер М. (1979). «Лемма, которая не принадлежит Бернсайду». Ученый-математик . 4 (2): 133–141. ISSN 0312-3685 . МР 0562002 . .

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]