数学の構造をPythonで実装し、具体例に対して性質を検証するシリーズの一つです。

今回は群を扱います。群は、集合と一つの二項演算からなる構造です。整数の加法や、可逆な行列の積など、異なる対象を同じ公理で扱えます。

この記事では、群の要素と群構造を分けて表現し、置換群を Hypothesis で検証します。

この記事で行うのは数学的な証明ではありません。Pythonで群のモデルを実装し、有限個または生成した具体例について公理が成り立つことをテストします。

コード例は Python 3.12 以降を前提にしています。検証には hypothesis を使います。

python -m pip install hypothesis

群の定義

集合 $G$ と二項演算 $\cdot$、単位元 $e \in G$ の組 $(G, \cdot, e)$ が群であるとは、次の公理を満たすことです。

結合則: $(a \cdot b) \cdot c = a \cdot (b \cdot c)$
単位元: $e \cdot a = a$ かつ $a \cdot e = a$
逆元: 任意の $a$ に対して、$a^{-1} \in G$ が存在し、$a \cdot a^{-1} = e$ かつ $a^{-1} \cdot a = e$

特に、可換性 $a \cdot b = b \cdot a$ を満たす群を可換群と呼びます。

群の要素と群構造を分ける

群の要素を表すクラスに群の演算や単位元を持たせる設計もできます。しかし、群のパラメータがある場合や、同じ要素型に複数の群構造を与える場合は、群構造を別のオブジェクトとして持つほうが自然です。

例えば、整数には加法群の構造を与えられます。また、同じ要素の集合に別の演算を定義することもできます。要素の型と群構造を分けておけば、群の演算を要素クラスへ後付けしたり、クラス全体を書き換えたりする必要がありません。

group.py

from __future__ import annotations

from collections.abc import Callable
from dataclasses import dataclass


@dataclass(frozen=True, slots=True)
class Group[G]:
    identity: G
    inv: Callable[[G], G]
    op: Callable[[G, G], G]

    def assert_associative(self, a: G, b: G, c: G) -> None:
        assert self.op(self.op(a, b), c) == self.op(a, self.op(b, c))

    def assert_left_identity(self, a: G) -> None:
        assert self.op(self.identity, a) == a

    def assert_right_identity(self, a: G) -> None:
        assert self.op(a, self.identity) == a

    def assert_inverse(self, a: G) -> None:
        inverse = self.inv(a)
        assert self.op(a, inverse) == self.identity
        assert self.op(inverse, a) == self.identity


int_additive_group = Group[int](
    identity=0,
    inv=lambda a: -a,
    op=lambda a, b: a + b,
)

identity は単位元、inv は逆元を返す関数、op は二項演算です。Group のインスタンスを作っただけでは公理は検査されません。assert_* メソッドへ具体的な要素を渡したときに、その要素について各公理を確認します。

有限巡回群を表す

整数を5で割った余りの加法群 $\mathbb{Z}/5\mathbb{Z}$ を、Enum で表します。

cyclic_group.py

from enum import Enum

from group import Group


class Z5Z(Enum):
    ZERO = 0
    ONE = 1
    TWO = 2
    THREE = 3
    FOUR = 4


z5z_group = Group[Z5Z](
    identity=Z5Z.ZERO,
    inv=lambda a: Z5Z((-a.value) % 5),
    op=lambda a, b: Z5Z((a.value + b.value) % 5),
)

Z5Z 自体へ群構造を後付けしていない点に注目してください。Z5Z は要素の集合を表し、どの演算を群構造として使うかは z5z_group が表します。

Enumや要素クラスへ群構造を動的に追加する方法は避けます。台集合である要素クラスと群構造である Group の組が群を表すという、数学的な特徴づけに自然に対応させるためです。

Groupのインスタンスメソッドで公理を検証する

群構造と公理の検証を同じインスタンスにまとめると、検証対象の群が明確になります。例えば group.assert_associative(a, b, c) は、group が持つ演算について結合則を確認します。

assert は式をそのまま読めるため、数学的な性質を記述する例として便利です。ただし、Pythonを -O オプションで実行すると assert 文は取り除かれます。実際のテストでは pytest のアサーションや Hypothesis と組み合わせます。

置換群を実装する

有限集合 $\{0, 1, \ldots, n-1\}$ から自分自身への全単射は、置換です。置換の合成を演算とすると、置換全体は群になります。これは $S_n$ と書かれます。

置換は、k の行き先を values[k] に記録する不変オブジェクトとして実装します。演算と逆元は、要素クラスではなく symmetric_group() が返す Group に登録します。

permutation.py

from __future__ import annotations

from dataclasses import dataclass

from group import Group


@dataclass(frozen=True, slots=True)
class Permutation:
    values: tuple[int, ...]

    def __post_init__(self) -> None:
        n = len(self.values)
        if set(self.values) != set(range(n)):
            raise ValueError("values must be a permutation of range(n)")


def compose(left: Permutation, right: Permutation) -> Permutation:
    if len(left.values) != len(right.values):
        raise ValueError("permutations must have the same degree")
    # (left * right)(k) = left(right(k))
    return Permutation(
        tuple(left.values[right.values[k]] for k in range(len(left.values)))
    )


def inverse(permutation: Permutation) -> Permutation:
    result = [0] * len(permutation.values)
    for source, target in enumerate(permutation.values):
        result[target] = source
    return Permutation(tuple(result))


def symmetric_group(n: int) -> Group[Permutation]:
    identity = Permutation(tuple(range(n)))
    return Group(identity=identity, inv=inverse, op=compose)

Group[Permutation] を返す関数に n を渡すため、$S_3$ と $S_4$ を別の群構造として表現できます。要素クラスのクラスメソッドへ次数を渡す必要はありません。

Hypothesisで群の公理を検証する

$S_3$ の要素は有限個なので、st.permutations で生成できます。

test_permutation_group.py

from hypothesis import given, strategies as st

from permutation import Permutation, symmetric_group


group = symmetric_group(3)
permutations = st.permutations(range(3)).map(Permutation)


@given(permutations, permutations, permutations)
def test_associativity(
    a: Permutation, b: Permutation, c: Permutation
) -> None:
    group.assert_associative(a, b, c)


@given(permutations)
def test_identity(a: Permutation) -> None:
    group.assert_left_identity(a)
    group.assert_right_identity(a)


@given(permutations)
def test_inverse(a: Permutation) -> None:
    group.assert_inverse(a)

このテストは、$S_3$ の要素からHypothesisが例を生成し、各性質を繰り返し確認します。有限群なので全要素を列挙することもできますが、ここでは後で無限集合のモデルへ拡張しやすい形にしています。

Pythonで群を扱うときの境界

この実装で型が表すのは、Group[G] が G 上の要素を返す関数を持つことまでです。次のことは型だけでは分かりません。

演算結果が同じ集合に戻ること
結合則が成り立つこと
指定した単位元が本当に単位元であること
すべての要素に逆元が存在すること

Group は群の公理を証明する型ではなく、群構造を一つの値としてまとめるデータ構造です。公理の確認は、具体的なモデルとテストに分担させます。

まとめ

群の要素と群構造を別々に表現した
Group[G] に単位元、逆元、二項演算、公理の検証をまとめた
同じ要素型に複数の群構造を持たせられるようにした
置換群 $S_3$ の公理を Hypothesis で検証した

次の記事では、群準同型を定義し、具体例で核と像を観察します。

次の記事：Pythonで群準同型を表す：写像・核・像