Fundamental Theorem of Finite Abelian Groups

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

Мы уже знаем, как собирать новые группы с помощью external direct product:

G1 ⊕ G2 ⊕ ... ⊕ Gk

Например:

Z4 ⊕ Z2

или:

Z3 ⊕ Z5

Теперь возникает естественный вопрос:

можно ли любую finite Abelian group разобрать на простые cyclic components?

Оказывается, да. Более того, такое разложение по существу единственно.

Именно это утверждает Fundamental Theorem of Finite Abelian Groups / фундаментальная теорема о конечных абелевых группах.

Что именно классифицирует теорема

Теорема относится к группам, которые одновременно finite и Abelian. То есть:

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

Если группа non-Abelian, эта теорема к ней не применяется.

Формулировка теоремы

Каждая finite Abelian group изоморфна direct product cyclic groups, порядки которых являются степенями простых чисел.

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

G ≅ Z_(p1^a1) ⊕ Z_(p2^a2) ⊕ ... ⊕ Z_(pk^ak)

где каждый:

pi

— prime number, а каждый:

ai >= 1

При этом простые числа pi не обязаны быть различными.

Например, допустимо разложение:

Z8 ⊕ Z4 ⊕ Z9 ⊕ Z3

потому что:

8 = 2^3
4 = 2^2
9 = 3^2
3 = 3^1

Все компоненты имеют prime-power order.

Что означает prime-power order

Prime power — это число вида:

p^k

где:

p

— prime number, а:

k >= 1

Например:

2, 4, 8, 16

— powers of prime 2.

3, 9, 27

— powers of prime 3.

5, 25, 125

— powers of prime 5.

Поэтому следующие cyclic groups имеют prime-power order:

Z2
Z8
Z9
Z25
Z27

А:

Z6

не имеет prime-power order, потому что:

6 = 2 · 3

Однако:

Z6 ≅ Z2 ⊕ Z3

поэтому Z6 всё равно можно разложить на prime-power components.

Почему используются именно prime powers

Любое positive integer имеет единственное prime factorization:

n = p1^a1 p2^a2 ... pk^ak

В finite Abelian groups происходит похожая история. Часть группы, связанная с одним prime p, можно отделить от частей, связанных с другими primes.

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

|G| = 72

то:

72 = 2^3 · 3^2

Структура G складывается из:

  • компоненты порядка 2^3;
  • компоненты порядка 3^2.

Сначала можно отдельно классифицировать Abelian groups порядка 8, потом отдельно groups порядка 9, а затем соединить результаты direct product.

Что значит уникальность разложения

Теорема утверждает не просто существование какого-то разложения. Она говорит, что набор cyclic prime-power components определяется группой uniquely, с точностью до:

  • перестановки компонентов;
  • замены компонента на isomorphic group.

Например:

Z4 ⊕ Z2

и:

Z2 ⊕ Z4

считаются одним и тем же разложением с точностью до isomorphism.

Но:

Z4

и:

Z2 ⊕ Z2

— разные структуры.

У обеих групп порядок 4, но:

  • в Z4 есть элемент порядка 4;
  • в Z2 ⊕ Z2 все non-identity elements имеют порядок 2.

Поэтому:

Z4 not ≅ Z2 ⊕ Z2

Isomorphism class

Когда мы записываем finite Abelian group как direct product cyclic prime-power groups, мы определяем её:

isomorphism class

То есть описываем не конкретные названия элементов, а саму group structure.

Например, если удалось доказать:

G ≅ Z4 ⊕ Z2

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

Abelian groups порядка p^k

Сначала удобно рассматривать случай:

|G| = p^k

где p — prime number.

Каждому способу записать k как сумму positive integers соответствует одна Abelian group порядка p^k.

Такая запись называется:

partition of k / разбиением числа k

Порядок p

У числа 1 только одно partition:

1

Поэтому существует только одна Abelian group порядка p:

Z_p

Порядок p²

Partitions числа 2:

2

и:

1 + 1

Им соответствуют группы:

Z_(p²)

и:

Z_p ⊕ Z_p

Поэтому любая group порядка p² изоморфна одной из этих двух групп.

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

p = 2

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

Z4

и:

Z2 ⊕ Z2

Порядок p³

Partitions числа 3:

3

2 + 1

1 + 1 + 1

Получаем три isomorphism classes:

Z_(p³)

Z_(p²) ⊕ Z_p

Z_p ⊕ Z_p ⊕ Z_p

Например, Abelian groups порядка 8:

Z8

Z4 ⊕ Z2

Z2 ⊕ Z2 ⊕ Z2

Порядок p⁴

Partitions числа 4:

4

3 + 1

2 + 2

2 + 1 + 1

1 + 1 + 1 + 1

Поэтому существует пять Abelian groups порядка p⁴:

Z_(p⁴)

Z_(p³) ⊕ Z_p

Z_(p²) ⊕ Z_(p²)

Z_(p²) ⊕ Z_p ⊕ Z_p

Z_p ⊕ Z_p ⊕ Z_p ⊕ Z_p

Общая связь с partitions

Число isomorphism classes Abelian groups порядка:

p^k

равно количеству partitions числа k.

Например:

k = 4

имеет пять partitions, поэтому существует пять Abelian groups порядка:

p^4

Важно: порядок слагаемых в partition не учитывается.

Например:

3 + 1

и:

1 + 3

— одно partition, потому что:

Z_(p³) ⊕ Z_p ≅ Z_p ⊕ Z_(p³)

Как классифицировать Abelian groups произвольного порядка

Пусть нужно найти все Abelian groups порядка:

n

Сначала раскладываем n на prime powers:

n = p1^a1 p2^a2 ... pk^ak

Дальше:

  1. находим все Abelian groups порядка p1^a1;
  2. находим все Abelian groups порядка p2^a2;
  3. продолжаем для каждого prime;
  4. берём все возможные direct products полученных компонентов.

Количество isomorphism classes равно произведению количеств partitions показателей:

number of classes
=
P(a1)P(a2)...P(ak)

где P(a) — количество partitions числа a.

Большой пример: Abelian groups порядка 1176

Разложим:

1176 = 2^3 · 3 · 7^2

Теперь рассматриваем каждую prime-power part отдельно.

Компонента порядка 2³

Partitions числа 3:

3
2 + 1
1 + 1 + 1

Поэтому возможны:

Z8

Z4 ⊕ Z2

Z2 ⊕ Z2 ⊕ Z2

Компонента порядка 3

Здесь только один вариант:

Z3

Компонента порядка 7²

Partitions числа 2:

2

и:

1 + 1

Поэтому возможны:

Z49

и:

Z7 ⊕ Z7

Соединяем варианты

  • Для 2³ есть 3 варианта.
  • Для 3 есть 1 вариант.
  • Для 7² есть 2 варианта.

Поэтому всего:

3 · 1 · 2 = 6

isomorphism classes.

Полный список:

Z8 ⊕ Z3 ⊕ Z49

Z4 ⊕ Z2 ⊕ Z3 ⊕ Z49

Z2 ⊕ Z2 ⊕ Z2 ⊕ Z3 ⊕ Z49

Z8 ⊕ Z3 ⊕ Z7 ⊕ Z7

Z4 ⊕ Z2 ⊕ Z3 ⊕ Z7 ⊕ Z7

Z2 ⊕ Z2 ⊕ Z2 ⊕ Z3 ⊕ Z7 ⊕ Z7

Любая finite Abelian group порядка 1176 изоморфна ровно одной группе из этого списка.

Как понять, какая именно структура перед нами

Знать порядок группы недостаточно. Например, все следующие группы имеют порядок 16:

Z16

Z8 ⊕ Z2

Z4 ⊕ Z4

Z4 ⊕ Z2 ⊕ Z2

Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2

Чтобы понять, к какой isomorphism class относится конкретная группа, можно исследовать порядки её элементов.

Есть элемент порядка 16

Если в группе порядка 16 есть элемент порядка 16, то этот элемент порождает всю группу.

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

G ≅ Z16

Максимальный порядок равен 8

Тогда возможна структура:

Z8 ⊕ Z2

Другие группы из списка не содержат элементов порядка 8.

Максимальный порядок равен 4

Тогда остаются:

Z4 ⊕ Z4

или:

Z4 ⊕ Z2 ⊕ Z2

Их можно различить по количеству элементов порядка 2.

В:

Z4 ⊕ Z4

есть три non-identity elements порядка 2.

В:

Z4 ⊕ Z2 ⊕ Z2

таких элементов семь.

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

Тогда:

G ≅ Z2 ⊕ Z2 ⊕ Z2 ⊕ Z2

То есть распределение порядков элементов позволяет определить структуру группы.

Порядок элемента в direct product

Напомним, что:

|(a1, a2, ..., ak)|
=
lcm(|a1|, |a2|, ..., |ak|)

Поэтому наличие элементов определённых порядков зависит от cyclic components.

Например, в:

Z8 ⊕ Z3 ⊕ Z7

элемент, компоненты которого имеют порядки:

8, 3, 7

имеет порядок:

lcm(8, 3, 7) = 168

Это помогает различать direct products.

Две формы записи разложения

Finite Abelian group можно записать двумя стандартными способами.

Elementary divisor form

Это форма из самой теоремы:

Z_(p1^a1) ⊕ Z_(p2^a2) ⊕ ... ⊕ Z_(pk^ak)

Каждый компонент имеет prime-power order.

Например:

Z4 ⊕ Z2 ⊕ Z9 ⊕ Z3

Invariant factor form

Компоненты взаимно простых порядков можно объединять.

Так как:

gcd(4, 9) = 1

получаем:

Z4 ⊕ Z9 ≅ Z36

А так как:

gcd(2, 3) = 1

получаем:

Z2 ⊕ Z3 ≅ Z6

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

Z4 ⊕ Z2 ⊕ Z9 ⊕ Z3
≅
Z36 ⊕ Z6

Обычно invariant factors располагают так, чтобы каждый порядок делил следующий:

6 divides 36

Поэтому можно написать:

Z6 ⊕ Z36

Обе записи описывают одну и ту же group structure:

Z4 ⊕ Z2 ⊕ Z9 ⊕ Z3
≅
Z6 ⊕ Z36

Как находить internal direct product конкретной группы

Пусть дана конкретная finite Abelian group G порядка:

p^n

Идея алгоритма такая:

  1. найти element of maximum order;
  2. взять порождённую им cyclic subgroup;
  3. найти независимую cyclic subgroup, пересекающуюся с первой только в identity;
  4. продолжать, пока произведение подгрупп не даст всю G.

Схематично:

G = <a1> × <a2> × ... × <ak>

где каждый:

<ai>

— cyclic subgroup prime-power order.

Первый шаг

Выбираем элемент:

a1 ∈ G

максимального возможного порядка.

Тогда:

<a1>

становится первым cyclic factor.

Следующий шаг

Если:

<a1> != G

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

Нужно, чтобы:

<a1> ∩ <a2> = {e}

Тогда:

<a1> × <a2>

становится более крупной частью G.

Процесс продолжается, пока порядок произведения компонентов не станет равен:

|G|

Почему greedy algorithm вообще работает

Для произвольной finite group такой алгоритм может сломаться. Но для finite Abelian p-groups существует важный результат:

cyclic subgroup, порождённую элементом максимального порядка, можно выделить как direct factor.

То есть если a имеет максимальный порядок, существует подгруппа K, для которой:

G = <a> × K

После этого тот же процесс можно применить к K.

Именно поэтому группу удаётся постепенно разобрать на cyclic components.

Следствие: подгруппы всех допустимых порядков

По Lagrange’s Theorem, если:

H ≤ G

то:

|H| divides |G|

Для произвольной finite group обратное утверждение неверно:

из того, что m делит |G|, не всегда следует существование subgroup порядка m.

Но для finite Abelian groups обратное утверждение верно.

Если:

m divides |G|

и G — finite Abelian group, то в G существует subgroup порядка:

m

Почему

Разложим:

G ≅ Z_(p1^a1) ⊕ ... ⊕ Z_(pk^ak)

В каждой cyclic component существуют subgroups всех порядков, делящих порядок этой компоненты.

Выбирая подходящие subgroups внутри компонентов и беря их direct product, можно получить subgroup любого порядка, делящего |G|.

Пример

Пусть:

G = Z8 ⊕ Z9

Тогда:

|G| = 8 · 9 = 72

Число:

12

делит 72.

Разложим:

12 = 4 · 3

В Z8 есть subgroup порядка 4:

<2> = {0, 2, 4, 6}

В Z9 есть subgroup порядка 3:

<3> = {0, 3, 6}

Их direct product имеет порядок:

4 · 3 = 12

Следовательно, в G есть subgroup порядка 12.

Что теорема даёт на практике

До этой теоремы вопрос:

какие вообще finite Abelian groups существуют?

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

После теоремы задача превращается в алгоритм:

  1. разложить порядок группы на primes;
  2. выписать partitions показателей;
  3. построить соответствующие direct products;
  4. при необходимости исследовать element orders и определить нужную isomorphism class.

Вместо поиска неизвестных operations мы работаем с хорошо знакомыми cyclic groups:

Z_n

Главное ограничение

Теорема классифицирует только:

finite Abelian groups

Она не утверждает, что любая finite group является direct product cyclic groups. Например, non-Abelian groups требуют совершенно других методов классификации.

Даже если две группы имеют одинаковый порядок, одна может быть Abelian, а другая — non-Abelian.

Главная идея

Конечные абелевы группы полностью строятся из cyclic prime-power blocks. Порядок группы говорит, какие блоки возможны, а порядки элементов помогают определить, какие именно блоки присутствуют.