Cosets (смежные классы в группах) и теорема Лагранжа

#абстрактная алгебра #cs

В этой главе мы плавно перейдём к одной из главных теорем конечной теории групп: Lagrange’s Theorem. Но перед этим нужно понять новый инструмент: coset / смежный класс. Грубо говоря, cosets позволяют разбить группу на одинаковые блоки, построенные из одной подгруппы.

Это потом приводит к важнейшему факту:

порядок подгруппы делит порядок группы.

Но сначала надо понять сами cosets.

Определение: Coset of H in G

Пусть G — группа, и:

H ⊆ G

— непустое подмножество.

Если взять элемент:

a ∈ G

то можно построить множество:

aH = {ah | h ∈ H}

Это значит:

берём все элементы h из H и умножаем каждый из них слева на a.

Такое множество называется left coset / левый смежный класс.

Right coset

Аналогично можно умножать справа:

Ha = {ha | h ∈ H}

Это называется right coset / правый смежный класс

Representative

Элемент a называется coset representative (представитель).

Например aH — это coset, построенный с помощью представителя a.

Иными словами

Если H — подгруппа внутри G, то coset aH — это как “копия” H, сдвинутая элементом a.

В additive notation это выглядит особенно просто. Вместо aH пишут:

a + H

То есть:

a + H = {a + h | h ∈ H}

Это буквально “сдвинуть все элементы H на a”.

Пример в Z9

Рассмотрим группу:

Z9 = {0, 1, 2, 3, 4, 5, 6, 7, 8}

с операцией addition modulo 9.

Пусть:

H = {0, 3, 6}

Это подгруппа Z9.

Теперь построим cosets.

Coset 0 + H

0 + H = {0 + 0, 0 + 3, 0 + 6}

То есть:

0 + H = {0, 3, 6}

Это сам H.

Coset 1 + H

1 + H = {1 + 0, 1 + 3, 1 + 6}

Считаем modulo 9:

1 + H = {1, 4, 7}

Coset 2 + H

2 + H = {2 + 0, 2 + 3, 2 + 6}

Получаем:

2 + H = {2, 5, 8}

Все cosets в Z9

Получилось:

0 + H = {0, 3, 6}
1 + H = {1, 4, 7}
2 + H = {2, 5, 8}

И всё, больше новых cosets тут не будет.

Например:

3 + H = {3, 6, 0} = {0, 3, 6} = 0 + H

4 + H = {4, 7, 1} = {1, 4, 7} = 1 + H

5 + H = {5, 8, 2} = {2, 5, 8} = 2 + H

То есть разные representatives могут давать один и тот же coset.

Coset — это обычно не подгруппа

Важно:

coset обычно не является подгруппой.

Например:

1 + H = {1, 4, 7}

Это не подгруппа Z9, потому что там нет identity element 0, а любая подгруппа additive group должна содержать 0.

Зато:

0 + H = H = {0, 3, 6}

— это подгруппа.

Главная мысль:

из всех cosets подгруппой является только сам H.

Почему разные representatives могут давать один coset

В примере выше:

0 + H = 3 + H = 6 + H

Потому что 0, 3, 6 лежат в одном и том же coset.

Также:

1 + H = 4 + H = 7 + H

и:

2 + H = 5 + H = 8 + H

То есть coset можно представлять любым своим элементом.

Если элемент уже лежит в coset, он может быть его representative.

Cosets разбивают группу на блоки

В Z9 мы получили три блока:

{0, 3, 6}
{1, 4, 7}
{2, 5, 8}

Они:

  • не пересекаются;
  • вместе дают всю группу Z9;
  • имеют одинаковый размер.

То есть cosets разбили группу на равные куски. Это ключевая идея.

Left cosets и right cosets

В non-Abelian groups важно различать:

aH

и:

Ha

Потому что операция может быть некоммутативной. То есть может быть:

aH != Ha

В Abelian groups такой проблемы нет, потому что:

ah = ha

Поэтому left cosets и right cosets совпадают.

Например в Z9 группа Abelian, поэтому можно спокойно писать:

a + H

и не париться про left/right.

Пример в D4

В группе симметрий квадрата D4 есть элементы:

R0, R90, R180, R270, H, V, D, D'

где:

  • R0, R90, R180, R270 — rotations;
  • H — horizontal reflection;
  • V — vertical reflection;
  • D, D' — diagonal reflections.

Чтобы не путать букву H с horizontal reflection, подгруппу назовём не H, а K. Возьмём подгруппу:

K = {R0, R180}

Теперь left coset элемента a относительно K — это:

aK = {ak | k ∈ K}

То есть мы берём элемент a и умножаем его слева на каждый элемент из K.

Так как:

K = {R0, R180}

то:

aK = {aR0, aR180}

Считаем cosets

Coset R0K

R0K = {R0R0, R0R180}

Получаем:

R0K = {R0, R180}

То есть:

R0K = K

Coset R90K

R90K = {R90R0, R90R180}

Получаем:

R90K = {R90, R270}

Coset HK

Здесь H — это НЕ подгруппа, а элемент группы: horizontal reflection.

HK = {HR0, HR180}

Получаем:

HK = {H, V}

То есть horizontal reflection вместе с R180 даёт vertical reflection.

Coset DK

DK = {DR0, DR180}

Получаем:

DK = {D, D'}

Итого

Разные left cosets подгруппы:

K = {R0, R180}

в D4:

K      = {R0, R180}
R90K   = {R90, R270}
HK     = {H, V}
DK     = {D, D'}

Они разбивают всю группу D4 на блоки одинакового размера:

D4 = {R0, R180} ∪ {R90, R270} ∪ {H, V} ∪ {D, D'}

Каждый блок имеет размер 2, как и сама подгруппа K.

Что тут важно

Запись:

aK

не означает, что K — операция. K — это множество.

aK означает:

aK = {ak | k ∈ K}

То есть “умножить элемент a на каждый элемент из множества K”.

Ещё раз главная идея:

coset — это подгруппа, сдвинутая элементом группы.

Основные свойства cosets

Пусть H — подгруппа группы G, и:

a, b ∈ G

Тогда для left cosets выполняются важные свойства.

1. Элемент a лежит в своём coset

a ∈ aH

Почему? По определению:

aH = {ah | h ∈ H}

То есть элемент лежит в aH, если его можно записать как ah для какого-то h ∈ H.

Так как H — подгруппа, в ней есть identity element:

e ∈ H

Берём именно этот элемент:

h = e

Тогда:

ah = ae = a

Значит a действительно лежит в aH.

Идея простая:

coset aH всегда содержит свой representative a.

2. Когда coset совпадает с самой подгруппой

aH = H iff a ∈ H

Читается так:

left coset aH равен самой подгруппе H тогда и только тогда, когда representative a уже лежит в H.

Иными словами

Если a уже находится внутри подгруппы H, то умножение всех элементов H на a не создаёт новый блок. Оно просто переставляет элементы внутри H. То есть H как множество остаётся тем же самым:

aH = H

Почему так

Coset определяется так:

aH = {ah | h ∈ H}

Если:

a ∈ H

то для любого h ∈ H произведение:

ah

тоже лежит в H, потому что H замкнута относительно операции.

Значит:

aH ⊆ H

А обратно элементы H тоже можно получить из aH, потому что у a есть inverse внутри H.

Если:

x ∈ H

то:

x = a(a^-1x)

и так как:

a^-1x ∈ H

получаем:

x ∈ aH

Значит:

H ⊆ aH

Итого:

aH = H

Пример в Z9

Пусть:

H = {0, 3, 6}

в группе Z9.

Так как:

3 ∈ H

то:

3 + H = H

Проверим:

3 + H = {3 + 0, 3 + 3, 3 + 6}

Считаем modulo 9:

3 + H = {3, 6, 0}

То есть:

3 + H = {0, 3, 6} = H

Главное

Если representative лежит в H, то он не создаёт новый coset:

a ∈ H => aH = H

А если:

aH = H

то representative a обязательно лежит в H, потому что любой coset содержит свой representative.

3. Два cosets либо одинаковые, либо не пересекаются

Это одно из главных свойств. Для любых двух left cosets:

aH
bH

возможны только два варианта:

aH = bH

или:

aH ∩ bH = ∅

То есть cosets не могут “частично пересекаться”. Если у двух cosets есть хотя бы один общий элемент, значит это один и тот же coset.

Пример

В Z9:

0 + H = {0, 3, 6}

1 + H = {1, 4, 7}

Они не пересекаются.

А вот:

1 + H = {1, 4, 7}

и:

4 + H = {4, 7, 1}

имеют общие элементы.

Значит они одинаковые:

1 + H = 4 + H

4. Любой элемент coset может быть representative

Если:

aH = bH

то a и b представляют один и тот же coset.

Также:

aH = bH iff a ∈ bH

Смысл:

если a лежит в coset bH, то a может представлять тот же самый coset.

Например:

1 + H = {1, 4, 7}

Поэтому representatives этого coset:

1, 4, 7

И правда:

1 + H = 4 + H = 7 + H

5. Все cosets имеют одинаковый размер

Для любых a, b ∈ G:

|aH| = |bH|

То есть все left cosets of H имеют одинаковое количество элементов.

Более того, каждый coset имеет столько же элементов, сколько сама подгруппа H.

|aH| = |H|

Интуиция простая:

умножение на a просто переносит элементы H в другое место, но не склеивает их.

6. aH является подгруппой iff a ∈ H

aH is a subgroup of G iff a ∈ H

То есть coset будет подгруппой только тогда, когда он на самом деле равен H.

Иными словами: единственный coset of H, который является подгруппой, — это сам H.

Что значит “cosets partition G”

Говорят, что cosets partition group G. Это значит, что cosets разбивают G на блоки:

  1. каждый элемент G попадает в какой-то coset;
  2. разные cosets не пересекаются;
  3. все cosets имеют одинаковый размер.

Например:

Z9 = {0,1,2,3,4,5,6,7,8}

разбивается на:

{0, 3, 6}
{1, 4, 7}
{2, 5, 8}

Каждый элемент Z9 находится ровно в одном блоке.

Почему это важно

Это главный мост к Lagrange’s Theorem.

Если finite group G разбивается на cosets подгруппы H, и каждый coset имеет размер |H|, то размер всей группы должен быть:

|G| = number_of_cosets * |H|

А значит:

|H| divides |G|

Это и есть “сердце” теоремы Лагранжа.

Как находить distinct cosets на практике

Чтобы найти все разные cosets подгруппы H в конечной группе G:

  1. Начинаем с самого H.
  2. Берём элемент a ∈ G, который ещё не встретился.
  3. Строим coset aH.
  4. Повторяем, пока все элементы G не окажутся в каком-то coset.

Почему это работает? Потому что cosets либо одинаковые, либо disjoint. Значит если элемент уже был в старом coset, он не даст нового coset.

Пример: найдём все distinct cosets в Z12

Рассмотрим группу:

Z12 = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11}

с операцией addition modulo 12.

Возьмём подгруппу:

H = {0, 4, 8}

Теперь хотим найти все разные cosets вида:

a + H

Шаг 1. Начинаем с самой подгруппы

0 + H = {0, 4, 8}

Запомнили элементы:

0, 4, 8

Шаг 2. Берём элемент, которого ещё не было

Например 1. Строим coset:

1 + H = {1 + 0, 1 + 4, 1 + 8}

Получаем:

1 + H = {1, 5, 9}

Запомнили новые элементы:

1, 5, 9

Шаг 3. Берём следующий элемент, которого ещё не было

Элемент 2 ещё не встречался.

2 + H = {2 + 0, 2 + 4, 2 + 8}

Получаем:

2 + H = {2, 6, 10}

Шаг 4. Берём следующий новый элемент

Элемент 3 ещё не встречался.

3 + H = {3 + 0, 3 + 4, 3 + 8}

Получаем:

3 + H = {3, 7, 11}

Всё, группа закончилась

Теперь все элементы Z12 уже появились:

{0, 4, 8}
{1, 5, 9}
{2, 6, 10}
{3, 7, 11}

Это и есть все distinct cosets подгруппы H в Z12.

Почему дальше новых cosets не будет

Например, если взять 4, то:

4 + H = {4, 8, 0}

Это тот же coset, что и:

0 + H

Если взять 5, то:

5 + H = {5, 9, 1}

Это тот же coset, что и:

1 + H

То есть элементы, которые уже лежали в старых cosets, не дают новых cosets.

Итого

Distinct cosets:

0 + H = {0, 4, 8}
1 + H = {1, 5, 9}
2 + H = {2, 6, 10}
3 + H = {3, 7, 11}

Каждый coset имеет размер 3, как и H.

Всего cosets: 4. И действительно:

|Z12| / |H| = 12 / 3 = 4

Это уже прямо ведёт к Lagrange’s Theorem.

Теорема Лагранжа

Если видишь незнакомую теорему и она названа чьим-то именем, то это наверняка Лагранж, Эйлер, Гаусс или Ньютон. Если нет, то, скорее всего, Эйнштейн. Шутка.

Предисловие

В прошлой части мы увидели, что cosets разбивают группу на равные непересекающиеся блоки.

Если H — подгруппа G, то left cosets aH разбивают G на блоки одинакового размера.

Причём каждый такой блок имеет столько же элементов, сколько сама подгруппа H:

|aH| = |H|

Из этого почти сразу получается одна из главных теорем конечной group theory.

Суть теоремы

Пусть G — finite group, а H — subgroup of G.

Тогда:

|H| divides |G|

То есть порядок подгруппы делит порядок всей группы.

Кроме того, количество distinct left cosets of H in G равно:

|G| / |H|

То же самое верно для right cosets.

Почему это правда

Cosets разбивают G на непересекающиеся блоки одинакового размера. Каждый блок имеет размер:

|H|

Если таких блоков m, то вся группа имеет размер:

|G| = m · |H|

Значит:

|H| divides |G|

А число блоков равно:

m = |G| / |H|

Вот и вся главная идея Lagrange’s Theorem.

Index of a Subgroup

Количество left cosets подгруппы H в группе G называется index of H in G.

Обозначение:

|G : H|

или иногда:

[G : H]

По Lagrange’s Theorem:

|G : H| = |G| / |H|

Пример

Пусть:

|G| = 12

и:

|H| = 3

Тогда:

|G : H| = 12 / 3 = 4

То есть G разбивается на 4 cosets подгруппы H.

Каждый coset имеет по 3 элемента.

Следствие 1: формула для index

Если G — finite group, а H ≤ G, то:

|G : H| = |G| / |H|

То есть index — это количество cosets.

Следствие 2: порядок элемента делит порядок группы

В finite group порядок любого элемента делит порядок всей группы.

То есть если:

a ∈ G

то:

|a| divides |G|

Почему

Элемент a порождает cyclic subgroup <a>. Порядок этой подгруппы равен порядку элемента:

|<a>| = |a|

А по Lagrange’s Theorem порядок любой подгруппы делит порядок группы.

Значит:

|a| divides |G|

Пример

Пусть:

|G| = 12

Тогда порядок любого элемента может быть только делителем 12.

Возможные порядки:

1, 2, 3, 4, 6, 12

Невозможные порядки:

5, 7, 8, 9, 10, 11

То есть в группе порядка 12 не может быть элемента порядка 5.

Следствие 3: группы простого порядка циклические

Если группа имеет prime order, то она cyclic.

То есть если:

|G| = p

где p — prime number, то:

G is cyclic

Почему

Возьмём любой элемент:

a ∈ G

такой что:

a != e

Тогда порядок a не равен 1.

Но по Lagrange’s Theorem:

|a| divides |G|

А если:

|G| = p

и p — prime, то делители только:

1, p

Так как a != e, порядок a не может быть 1.

Значит:

|a| = p

То есть a порождает всю группу:

G = <a>

Значит группа cyclic.

Пример

Любая группа порядка 7 cyclic. Почему? Потому что 7 — prime.

Если взять любой non-identity element a, то его порядок обязан делить 7. Варианты:

1 или 7

Но a != e, значит:

|a| = 7

Следовательно:

G = <a>

Следствие 4: a^|G| = e

Пусть G — finite group, и:

a ∈ G

Тогда:

a^|G| = e

Почему

По предыдущему следствию:

|a| divides |G|

Значит существует positive integer k, такой что:

|G| = |a| · k

А так как:

a^|a| = e

получаем:

a^|G| = a^(|a|k) = (a^|a|)^k = e^k = e

Пример

Пусть:

|G| = 12

и элемент a имеет порядок:

|a| = 3

Тогда:

a^3 = e

А значит:

a^12 = a^(3·4) = (a^3)^4 = e

Следствие 5: Fermat’s Little Theorem

Для любого integer a и любого prime p:

a^p ≡ a (mod p)

Это называется малая теорема Ферма.

Частая форма теоремы

Если p — prime и a не делится на p, то:

a^(p-1) ≡ 1 (mod p)

Это та же идея, только записанная для multiplicative group U(p).

Группа U(p) состоит из ненулевых элементов modulo p:

U(p) = {1, 2, ..., p-1}

Её порядок:

|U(p)| = p - 1

Поэтому для любого a ∈ U(p):

a^(p-1) = e

А identity в multiplicative group modulo p — это 1.

Значит:

a^(p-1) ≡ 1 (mod p)

Пример

Возьмём:

p = 7
a = 3

Так как 7 prime и 3 не делится на 7, должно быть:

3^6 ≡ 1 (mod 7)

Проверим:

3^2 = 9 ≡ 2 (mod 7)
3^3 ≡ 6 (mod 7)
3^6 ≡ 6^2 = 36 ≡ 1 (mod 7)

Сработало.

Обратное утверждение теоремы Лагранжа неверно

Lagrange’s Theorem говорит:

если H ≤ G, то |H| divides |G|

Но обратное утверждение неверно.

Нельзя сказать:

если d divides |G|, то в G обязательно есть subgroup порядка d

Это не всегда правда.

Смысл

Если у группы есть подгруппа, её порядок обязан делить порядок группы.

Но не каждый делитель порядка группы обязан быть порядком какой-то подгруппы.

Пример: вращения тетраэдра

Рассмотрим группу всех вращений правильного тетраэдра. У правильного тетраэдра есть 12 вращательных симметрий.

То есть группа имеет порядок:

|G| = 12

Число 6 делит 12:

6 divides 12

Но в этой группе нет подгруппы порядка 6.

То есть:

6 divides |G|

но subgroup of order 6 не существует.

Теорема: размер произведения двух подгрупп

Пусть H и K — finite subgroups некоторой группы.

Определим множество:

HK = {hk | h ∈ H, k ∈ K}

То есть HK состоит из всех произведений элемента из H на элемент из K.

Тогда:

|HK| = |H||K| / |H ∩ K|

Интуиция

Если бы элементы из H и K вообще не пересекались по структуре, можно было бы ожидать:

|HK| = |H||K|

Но если у H и K есть общие элементы, то при умножении появляются повторы.

Эти повторы учитываются размером пересечения:

|H ∩ K|

Поэтому формула такая:

|HK| = |H||K| / |H ∩ K|

Примерная логика

  • |H||K| считает все пары (h, k);
  • разные пары могут давать один и тот же элемент hk;
  • количество повторов связано с общими элементами H ∩ K.

Поэтому делим на:

|H ∩ K|

Зачем это нужно

Эта формула помогает ограничивать возможную структуру finite groups.

Например, можно доказывать, что некоторые подгруппы не могут существовать одновременно, потому что иначе множество HK стало бы слишком большим для самой группы.

Пример: group of order 75

Группа порядка 75 может иметь не больше одной подгруппы порядка 25. Почему?

Пусть есть две подгруппы:

H
K

и:

|H| = 25
|K| = 25

Если они слишком мало пересекаются, то по формуле:

|HK| = |H||K| / |H ∩ K|

множество HK получится слишком большим.

Например если:

|H ∩ K| = 1

то:

|HK| = 25 · 25 / 1 = 625

Но вся группа имеет только:

75

элементов.

Невозможно.

Если:

|H ∩ K| = 5

то:

|HK| = 25 · 25 / 5 = 125

Тоже больше 75.

Значит остаётся только:

|H ∩ K| = 25

То есть:

H = K

Значит двух разных подгрупп порядка 25 быть не может.

Теорема: группы порядка 2p

Сформулируем классификацию групп порядка 2p, где p — prime greater than 2.

Теорема говорит:

если |G| = 2p, то G ≅ Z_2p или G ≅ D_p

То есть группа порядка 2p либо cyclic, либо dihedral.

Смысл

Для prime p > 2 группы порядка 2p имеют очень ограниченную структуру. Возможны только два типа:

Z_2p

или:

D_p

Например при:

p = 3

получаем группы порядка 6:

Z6
D3