Normal Subgroups и Factor Groups: Нормальные подгруппы и фактор-группы

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

В главе про cosets мы увидели, что подгруппа N разбивает группу G на left cosets:

aN = {an | n ∈ N}

и right cosets:

Na = {na | n ∈ N}

В Abelian group никакой разницы между ними нет, потому что:

an = na

Но в non-Abelian group порядок операции важен, поэтому generally:

aN != Na

Иногда, однако, left и right cosets всё-таки совпадают для каждого элемента группы. Именно такие подгруппы называются normal subgroups / нормальными подгруппами.

Определение normal subgroup

Пусть:

N ≤ G

То есть N — подгруппа группы G.

Подгруппа N называется normal in G, если для любого:

a ∈ G

выполняется:

aN = Na

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

N ◁ G

Читается:

N is normal in G

Что именно означает aN = Na

Важно не перепутать условие:

aN = Na

с более сильным условием:

an = na

Normality не требует, чтобы каждый элемент n ∈ N коммутировал с каждым элементом a ∈ G.

Речь идёт о равенстве двух множеств:

aN = {an | n ∈ N}

и:

Na = {na | n ∈ N}

То есть для каждого:

n ∈ N

существует, возможно, другой элемент:

n' ∈ N

такой что:

an = n'a

Элемент n' не обязан совпадать с исходным n.

Смысл на маленьком примере

Допустим:

N = {e, n1, n2}

Тогда:

aN = {a, an1, an2}

И:

Na = {a, n1a, n2a}

Чтобы N была normal, эти множества должны содержать одни и те же элементы.

Но необязательно:

an1 = n1a

Вполне может быть:

an1 = n2a

и:

an2 = n1a

Элементы внутри coset просто переставились.

Normal не означает Abelian

Это важный момент:

normal subgroup не обязана состоять из элементов, которые коммутируют со всей группой.

Normality означает только, что при переносе элементов подгруппы через элементы G мы остаёмся внутри той же подгруппы.

То есть подгруппа может внутренне “перемешиваться”, но не разваливается и не превращается в другое множество.

Пример в Abelian group

Рассмотрим:

G = Z12

и подгруппу:

N = {0, 4, 8}

Операция в Z12 — addition modulo 12.

Для любого a ∈ Z12:

a + N = N + a

потому что сложение коммутативно:

a + n = n + a

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

N ◁ Z12

Вообще в любой Abelian group каждая подгруппа является normal.

Все подгруппы Abelian group нормальны

Если G Abelian, то для любых:

a ∈ G
n ∈ N

выполняется:

an = na

Поэтому:

aN = Na

для любого a ∈ G.

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

every subgroup of an Abelian group is normal.

Normality становится отдельной проблемой только в non-Abelian groups.

Conjugation / сопряжение

Проверять равенство:

aN = Na

напрямую не всегда удобно. Поэтому normality обычно проверяют через conjugation / сопряжение.

Для элемента:

x ∈ G

и подгруппы N определим:

xNx^-1 = {xnx^-1 | n ∈ N}

То есть каждый элемент n ∈ N заменяется на:

xnx^-1

Интуиция conjugation

Выражение:

xnx^-1

можно понимать как тот же group action, рассмотренный после внутренней смены “контекста”.

Conjugation может переставить элементы группы, но сохраняет их group-theoretic properties:

  • порядок элемента;
  • отношения между элементами;
  • структуру сгенерированных подгрупп.

Normal subgroup — это подгруппа, которая остаётся той же самой после любого такого внутреннего преобразования.

Normal Subgroup Test

Подгруппа N ≤ G является normal тогда и только тогда, когда для каждого:

x ∈ G

выполняется:

xNx^-1 ⊆ N

В elementwise form это означает:

xnx^-1 ∈ N

для любых:

x ∈ G
n ∈ N

Часто это условие записывают сразу как равенство:

xNx^-1 = N

Почему из inclusion получается equality

Допустим, для каждого x ∈ G:

xNx^-1 ⊆ N

Это условие верно и для элемента x^-1:

x^-1Nx ⊆ N

Умножим последнее inclusion слева на x, а справа на x^-1:

N ⊆ xNx^-1

Но у нас уже было:

xNx^-1 ⊆ N

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

xNx^-1 = N

Почему conjugation test связан с cosets

Начнём с normality:

xN = Nx

Умножим обе части справа на x^-1:

xNx^-1 = Nxx^-1

Так как:

xx^-1 = e

получаем:

xNx^-1 = N

Поэтому условия:

xN = Nx

и:

xNx^-1 = N

описывают одну и ту же идею.

Пример: rotations в D4

Рассмотрим группу симметрий квадрата D4. Обозначим: r — rotation на 90°, а s — некоторое reflection.

Тогда:

r^4 = e
s^2 = e

и:

srs = r^-1

Возьмём подгруппу всех rotations:

R = {e, r, r^2, r^3}

Покажем, что:

R ◁ D4

Conjugation rotation элементом

Если conjugate rotation другим rotation:

r^i r^k r^-i

то rotations коммутируют между собой, поэтому:

r^i r^k r^-i = r^k

Результат снова лежит в R.

Conjugation reflection элементом

Используя:

srs = r^-1

получаем:

sr^k s = r^-k

Но:

r^-k

тоже rotation и также лежит в R.

Следовательно, conjugation любым элементом D4 не выводит нас за пределы R.

Значит:

R ◁ D4

Но rotations не коммутируют со всеми reflections

Например:

sr = r^-1s

Generally:

sr != rs

Поэтому подгруппа rotations normal, но её элементы не обязаны коммутировать со всеми элементами D4.

Это хороший пример того, что:

normal != central

Пример ненормальной подгруппы в D4

Теперь возьмём подгруппу, состоящую из identity и одного reflection:

K = {e, s}

Сравним left и right cosets для элемента r.

Left coset:

rK = {r, rs}

Right coset:

Kr = {r, sr}

Но:

sr = r^-1s = r^3s

Поэтому:

Kr = {r, r^3s}

Generally:

rs != r^3s

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

rK != Kr

Поэтому:

K

не является normal subgroup of D4.

Center группы всегда normal

Center группы обозначается:

Z(G)

и состоит из элементов, которые коммутируют со всеми элементами G:

Z(G) = {z ∈ G | zg = gz for all g ∈ G}

Если:

z ∈ Z(G)

то для любого x ∈ G:

xzx^-1 = zxx^-1 = z

Поэтому conjugation вообще не меняет элементы center.

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

Z(G) ◁ G

Unique subgroup данного порядка является normal

Пусть в группе G есть ровно одна подгруппа N порядка m.

Тогда:

N ◁ G

Почему?

Для любого:

x ∈ G

множество:

xNx^-1

также является подгруппой G.

Кроме того, conjugation является bijection, поэтому:

|xNx^-1| = |N| = m

Но по условию в G существует только одна подгруппа порядка m.

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

xNx^-1 = N

для любого x ∈ G.

Значит:

N ◁ G

Произведение normal subgroup и другой подгруппы

Пусть:

N ◁ G

а:

K ≤ G

Тогда множество:

NK = {nk | n ∈ N, k ∈ K}

является подгруппой G.

Это важно, потому что произведение двух произвольных подгрупп не обязано быть подгруппой. Normality N позволяет переставлять элементы N и K с небольшой корректировкой внутри N.

Почему normality помогает

Пусть:

n1k1 ∈ NK

и:

n2k2 ∈ NK

Чтобы использовать subgroup test, рассмотрим:

(n1k1)(n2k2)^-1

Получаем:

(n1k1)(k2^-1n2^-1)
=
n1(k1k2^-1)n2^-1

Нужно перенести n2^-1 влево от элемента k1k2^-1.

Так как N normal, существует некоторый:

n' ∈ N

такой что:

(k1k2^-1)n2^-1 = n'(k1k2^-1)

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

(n1k1)(n2k2)^-1
=
(n1n')(k1k2^-1)

Причём:

n1n' ∈ N

и:

k1k2^-1 ∈ K

Значит результат снова лежит в:

NK

Поэтому NK является подгруппой.

Зачем вообще нужны normal subgroups

Главная причина появляется в следующей части. Cosets normal subgroup можно рассматривать как отдельные элементы новой группы.

Эта новая группа называется:

factor group

или:

quotient group

и обозначается:

G / N

Её элементы — не отдельные элементы G, а целые cosets:

aN

Как хочется перемножать cosets

Естественно определить:

(aN)(bN) = abN

Но здесь возникает проблема.

Один и тот же coset можно записать через разных representatives:

aN = a'N

и:

bN = b'N

Нужно, чтобы результат не зависел от того, какие representatives мы выбрали:

abN = a'b'N

Именно normality гарантирует, что такое умножение корректно определено.

Без normality операция над cosets может зависеть от выбора representative, и группы не получится.

Главная мысль norma subgroup

Normal subgroup — это подгруппа, которая не меняется при conjugation элементами всей группы:

xNx^-1 = N

Эквивалентно:

xN = Nx

для любого:

x ∈ G

Normality не означает, что все элементы коммутируют. Она означает, что при внутреннем “перемешивании” элементы подгруппы остаются внутри неё.

Именно normal subgroups позволяют построить factor groups:

G / N

Поэтому они являются одним из центральных объектов group theory.

Factor Groups: как превратить cosets в новую группу

В предыдущей части мы ввели normal subgroups.

Пусть:

N ◁ G

Это означает, что для любого:

a ∈ G

left и right cosets совпадают:

aN = Na

Теперь становится понятно, зачем вообще понадобилось это условие.

Если N normal in G, то cosets подгруппы N сами образуют новую группу.

Эта группа называется:

factor group

или:

quotient group

По-русски обычно говорят фактор-группа или группа частных.

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

G / N

Главная идея factor group

Обычные элементы G объединяются в cosets:

aN

После этого каждый coset рассматривается как один элемент новой группы.

То есть вместо отдельных элементов:

a, an1, an2, ...

мы видим один большой объект:

aN

Все элементы одного coset становятся неразличимыми на уровне quotient group.

Можно представлять это как систематическое сжатие группы:

отдельные элементы G
        ↓
блоки одинакового размера
        ↓
элементы новой группы G/N

Определение factor group

Пусть:

N ◁ G

Тогда factor group определяется как множество всех cosets подгруппы N:

G / N = {aN | a ∈ G}

Операция задаётся так:

(aN)(bN) = abN

То есть:

  1. берём representatives a и b;
  2. перемножаем их в исходной группе;
  3. берём coset результата.

В additive notation

Если операция в группе — сложение, пишут:

G / N = {a + N | a ∈ G}

А операция выглядит так:

(a + N) + (b + N) = (a + b) + N

Например:

(2 + N) + (5 + N) = 7 + N

Это не обычное деление

Запись:

G / N

не означает, что мы буквально делим одну группу на другую как числа.

Смысл другой:

мы объединяем элементы G в cosets подгруппы N и считаем каждый такой coset одним элементом.

Количество элементов factor group равно количеству distinct cosets:

|G / N| = |G : N|

Если G finite, то по Lagrange’s Theorem:

|G / N| = |G| / |N|

Почему здесь необходима normality

Мы хотим определить:

(aN)(bN) = abN

Но один и тот же coset можно записать через разных representatives.

Например:

aN = a'N

и:

bN = b'N

Значит нужно гарантировать, что результат не изменится:

abN = a'b'N

Иначе операция зависела бы не от самих cosets, а от того, какие случайные representatives мы выбрали. Такая операция была бы not well-defined / некорректно определённой.

Именно normality гарантирует, что:

(aN)(bN)

всегда даёт один и тот же coset независимо от representatives.

Что делает normality внутри вычисления

Возьмём элементы:

an1 ∈ aN
bn2 ∈ bN

где:

n1, n2 ∈ N

Их произведение:

(an1)(bn2)

имеет вид:

an1bn2

Чтобы собрать это в coset abN, нам нужно перенести n1 через b. Так как N normal, conjugation элементом b не выводит нас за пределы N.

Поэтому существует некоторый:

n3 ∈ N

такой что:

n1b = bn3

Тогда:

an1bn2 = abn3n2

А поскольку:

n3n2 ∈ N

получаем:

an1bn2 ∈ abN

Поэтому произведение двух cosets действительно является coset:

(aN)(bN) = abN

Теорема: Factor Groups

Если:

N ◁ G

то множество:

G / N = {aN | a ∈ G}

является группой относительно операции:

(aN)(bN) = abN

Group properties в G/N

Identity

Identity element quotient group — это сама подгруппа N:

N = eN

Почему?

(aN)(N) = (aN)(eN) = aeN = aN

То есть:

identity of G/N = N

Inverse

Inverse элемента:

aN

равен:

a^-1N

Потому что:

(aN)(a^-1N)
=
aa^-1N
=
eN
=
N

Associativity

Associativity наследуется от исходной группы:

((aN)(bN))(cN)
=
(ab)cN

и:

(aN)((bN)(cN))
=
a(bc)N

Так как в G:

(ab)c = a(bc)

результаты совпадают.

Когда два cosets считаются одним элементом

Для normal subgroup N:

aN = bN

тогда и только тогда, когда:

a^-1b ∈ N

В additive notation:

a + N = b + N

тогда и только тогда, когда:

b - a ∈ N

То есть два элемента G становятся одним элементом quotient group, если они отличаются на элемент из N.

Пример: Z / 4Z

Рассмотрим additive group всех целых чисел:

Z

и её подгруппу:

4Z = {..., -8, -4, 0, 4, 8, ...}

Это множество всех чисел, кратных 4.

Так как Z Abelian:

4Z ◁ Z

Теперь построим:

Z / 4Z

Cosets подгруппы 4Z

Первый coset:

0 + 4Z
=
{..., -8, -4, 0, 4, 8, ...}

Это все числа с остатком 0 при делении на 4.

Далее:

1 + 4Z
=
{..., -7, -3, 1, 5, 9, ...}

Это все числа с остатком 1.

2 + 4Z
=
{..., -6, -2, 2, 6, 10, ...}

Это все числа с остатком 2.

3 + 4Z
=
{..., -5, -1, 3, 7, 11, ...}

Это все числа с остатком 3.

Других cosets нет.

Например:

5 + 4Z = 1 + 4Z

потому что:

5 - 1 = 4 ∈ 4Z

Элементы quotient group

Получаем:

Z / 4Z
=
{
  0 + 4Z,
  1 + 4Z,
  2 + 4Z,
  3 + 4Z
}

Операция:

(a + 4Z) + (b + 4Z)
=
(a + b) + 4Z

Например:

(2 + 4Z) + (3 + 4Z)
=
5 + 4Z

Но:

5 + 4Z = 1 + 4Z

Поэтому:

(2 + 4Z) + (3 + 4Z)
=
1 + 4Z

Это ровно addition modulo 4.

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

Z / 4Z ≅ Z4

Общий результат для Z

Для любого positive integer n:

nZ = {..., -2n, -n, 0, n, 2n, ...}

Тогда:

Z / nZ ≅ Z_n

То есть modular arithmetic можно понимать как factor group целых чисел по подгруппе кратных n.

Запись:

a ≡ b (mod n)

означает именно:

a + nZ = b + nZ

потому что:

a - b ∈ nZ

Пример: Z18 / <6>

Рассмотрим:

G = Z18

и подгруппу:

N = <6> = {0, 6, 12}

Так как Z18 Abelian:

N ◁ Z18

Порядки:

|Z18| = 18

|N| = 3

Поэтому quotient group имеет:

|Z18 / N| = 18 / 3 = 6

элементов.

Находим cosets

0 + N = {0, 6, 12}

1 + N = {1, 7, 13}

2 + N = {2, 8, 14}

3 + N = {3, 9, 15}

4 + N = {4, 10, 16}

5 + N = {5, 11, 17}

Поэтому:

Z18 / N
=
{
  0 + N,
  1 + N,
  2 + N,
  3 + N,
  4 + N,
  5 + N
}

Как складываются cosets

Возьмём:

(5 + N) + (4 + N)

Складываем representatives:

5 + 4 = 9

Значит:

(5 + N) + (4 + N)
=
9 + N

Но:

9 + N = {9, 15, 3}

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

3 + N = {3, 9, 15}

Поэтому:

(5 + N) + (4 + N)
=
3 + N

По структуре эта quotient group работает как:

Z6

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

Z18 / <6> ≅ Z6

Размер coset и порядок coset — разные вещи

Здесь легко запутаться, потому что запись:

|a + N|

может использоваться в двух смыслах.

Размер coset как множества

В предыдущем примере:

3 + N = {3, 9, 15}

Поэтому coset содержит 3 элемента. То есть его размер как множества:

|3 + N| = 3

Порядок coset как элемента quotient group

Но теперь рассмотрим:

3 + N

как один элемент группы:

Z18 / N

Складываем его с самим собой:

(3 + N) + (3 + N)
=
6 + N

Но:

6 ∈ N

поэтому:

6 + N = N = 0 + N

Значит элемент:

3 + N

возвращается в identity после двух сложений.

Его порядок в quotient group равен 2.

Итак:

3 + N

имеет:

  • размер 3 как множество;
  • порядок 2 как элемент quotient group.

Смысл всегда определяется контекстом.

Как находить порядок элемента aN

В multiplicative notation порядок coset:

aN

— это наименьшее positive integer k, для которого:

a^k ∈ N

Потому что:

(aN)^k = a^kN

А identity quotient group — это:

N

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

a^kN = N

ровно тогда, когда:

a^k ∈ N

В additive notation

Порядок:

a + N

— это наименьшее positive integer k, для которого:

ka ∈ N

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

a = 3

и:

2 · 3 = 6 ∈ N

Поэтому:

|3 + N| = 2

как элемента quotient group.

Non-Abelian пример: D4 / K

Рассмотрим группу симметрий квадрата D4.

В ней есть восемь элементов:

R0, R90, R180, R270,
H_ref, V_ref, D, D'

Чтобы не путать horizontal reflection с названием подгруппы, обозначим подгруппу буквой K:

K = {R0, R180}

Эта подгруппа normal in D4.

Построим quotient group:

D4 / K

Cosets

Первый coset:

K = {R0, R180}

Далее:

R90K = {R90, R270}

H_refK = {H_ref, V_ref}

DK = {D, D'}

Поэтому:

D4 / K
=
{
  K,
  R90K,
  H_refK,
  DK
}

Вместо восьми отдельных симметрий теперь осталось четыре блока.

Пример операции

Возьмём:

(R90K)(R90K)

По определению:

(R90K)(R90K)
=
R180K

Но:

R180 ∈ K

поэтому:

R180K = K

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

(R90K)^2 = K

То есть coset R90K имеет порядок 2.

Аналогично:

(H_refK)^2 = K

и:

(DK)^2 = K

Все три non-identity elements имеют порядок 2.

Поэтому:

D4 / K ≅ Z2 ⊕ Z2

Quotient group как сжатая версия исходной группы

При переходе:

G → G/N

все элементы одного coset сжимаются в один элемент.

Например, в D4 / K:

R0

и:

R180

становятся одним элементом:

K

А:

R90

и:

R270

становятся одним элементом:

R90K

Factor group “забывает” различия между элементами, которые отличаются на элемент из N.

Что значит “сделать N identity”

В quotient group сама подгруппа:

N

становится identity element.

Все элементы N оказываются внутри identity coset:

N = eN

Поэтому можно сказать:

при переходе к G/N мы объявляем все элементы N эквивалентными identity.

Например, в:

Z / 4Z

все числа, кратные 4, становятся нулём:

... = -8 + 4Z = -4 + 4Z = 0 + 4Z = 4 + 4Z = 8 + 4Z = ...

А в:

Z18 / {0,6,12}

элементы:

0, 6, 12

становятся одним identity element:

N

“Killing” a subgroup

Иногда говорят, что при создании quotient group мы:

kill N

то есть “убиваем подгруппу N”.

Это не означает, что её просто удаляют. На самом деле все её элементы отождествляются с identity.

n ∈ N

становится:

nN = N

для любого n ∈ N.

А элементы, отличающиеся на элемент из N, становятся одинаковыми:

aN = anN

Зачем нужны factor groups

Factor group позволяет намеренно забыть часть структуры группы.

Мы выбираем normal subgroup N, объявляем её элементы identity и смотрим, какая структура останется.

Это полезно, когда:

  • исходная группа слишком большая;
  • нас не интересуют различия внутри cosets;
  • нужно изучить структуру группы по слоям;
  • нужно понять kernel of a homomorphism;
  • нужно применить First Isomorphism Theorem.

Дальше окажется, что kernels homomorphisms всегда являются normal subgroups, а quotient groups естественно описывают результат homomorphism.

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

Factor group:

G / N

состоит не из элементов исходной группы, а из cosets:

aN

Операция задаётся так:

(aN)(bN) = abN

Normality гарантирует, что результат не зависит от выбора representatives.

При переходе к quotient group:

  • все элементы N становятся identity;
  • элементы одного coset становятся одним элементом;
  • группа G сжимается до более простой структуры.

Factor group — это группа, полученная после того, как все элементы normal subgroup объявлены identity, а элементы каждого coset склеены в один новый элемент.