Лемма Бернсайда - Burnside's lemma

Лемма Бернсайда , иногда также называемая теоремой Бернсайда о подсчете , леммой Коши – Фробениуса , теоремой о подсчете орбит или леммой, не принадлежащей Бернсайду , является результатом теории групп, который часто бывает полезен при учете симметрии при подсчете математических объектов. Его различные эпонимы основаны на произведениях Уильяма Бернсайда , Джорджа Полиа , Огюстена Луи Коши и Фердинанда Георга Фробениуса . Результат не из-за самого Бернсайда, который просто цитирует его в своей книге «О теории групп конечного порядка», вместо этого приписывая это Фробениусу (1887) .

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

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

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

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

Пример приложения

Число вращательно различных раскраски граней куба с использованием трех цветов можно определить по этой формуле следующим образом.

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

• один элемент идентичности, который оставляет все ^3-6 элементов X без изменений
• шесть поворотов лица на 90 градусов, каждый из которых оставляет 3 ³ элемента X без изменений
• три 180-градусное лицо вращения, каждый из которых оставляет 3 ⁴ из элементов X неизмененном
• восемь вращений вершин на 120 градусов, при каждом из которых 3 ² элемента X остаются неизменными
• шесть поворотов краев на 180 градусов, каждый из которых оставляет 3 ³ элемента X без изменений

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

Таким образом, средний размер исправления

${\ displaystyle {\ 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 цветов определяется как

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

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

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

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

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

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

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

Поэтому нашу сумму по множеству X можно переписать в виде

${\ displaystyle \ 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 , что означает, что сумма по X может быть разбита на отдельные суммы по каждой отдельной орбите.

${\ displaystyle \ sum _ {x \ in X} {\ frac {1} {| G \ cdot x |}} = \ sum _ {A \ in X / G} \ sum _ {x \ in A} {\ гидроразрыв {1} {| A |}} = \ sum _ {A \ in X / G} 1 = | X / G |.}$

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

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

Это доказательство, по сути, также является доказательством формулы уравнения классов , просто считая действие G на себя ( X = G ) сопряжением, g . х = GXG ^-1 , и в этом случае G _х инстанцирует централизатору х в G .

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

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

Смотрите также

• Перечислительная теорема Полиа

Примечания

использованная литература

• Бернсайд, Уильям (1897) Теория групп конечного порядка , Cambridge University Press , Project Gutenberg и здесь, на Archive.org . (Это первое издание; введение ко второму изданию содержит знаменитый поворот лица Бернсайда относительно полезности теории представлений .)
• Фробениус, Фердинанд Георг (1887), «Ueber die Congruenz nach einem aus zwei endlichen Gruppen gebildeten Doppelmodul», журнал Crelle , 101 (4): 273–299, doi : 10.3931 / e-rara-18804.
• Нойман, Питер М. (1979), «Лемма, не принадлежащая Бернсайду», The Mathematical Scientist , 4 (2): 133–141, ISSN  0312-3685 , MR  0562002.
• Ротман, Джозеф (1995), Введение в теорию групп , Springer-Verlag, ISBN 0-387-94285-8.

• Ченг, Юанью Ф. (1986), Обобщение леммы Бернсайда на кратно транзитивные группы , журнал Технологического университета Хубэй, ISSN  1003-4684.