前の記事：Pythonで直積群を実装する：2つの群から新しい群を構成する

前の記事では、2つの群から直積群を構成しました。今回は、生成元の集合から自由群を構成し、その普遍性をPythonで観察します。

自由群は、生成元の間に余分な関係式を課さない群です。単に「生成元から群を作る」だけでなく、任意の群への写像を生成元上で指定すると、自由群全体への準同型へ一意に拡張できる点が重要です。

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

自由群の定義

集合 $X$ から作る自由群 $F(X)$ は、$X$ の元とその逆元からなる有限列を、隣接する逆元の組を消去して得られる既約語で表せます。

F(X) = \text{生成元と逆元からなる既約語の集合}

生成元 $x$ と逆元 $x^{-1}$ は、(x, False) と (x, True) の組で表します。

自由群を実装する

free_group.py

from __future__ import annotations

from collections.abc import Hashable, Iterable
from dataclasses import dataclass

from group import Group


def reduce_letters[T: Hashable](
    letters: Iterable[tuple[T, bool]],
) -> tuple[tuple[T, bool], ...]:
    stack: list[tuple[T, bool]] = []
    for letter in letters:
        if stack and stack[-1][0] == letter[0] and stack[-1][1] != letter[1]:
            stack.pop()
        else:
            stack.append(letter)
    return tuple(stack)


@dataclass(frozen=True, slots=True)
class FreeWord[T: Hashable]:
    letters: tuple[tuple[T, bool], ...] = ()

    def __post_init__(self) -> None:
        if self.letters != reduce_letters(self.letters):
            raise ValueError("word must be reduced")


def free_group[T: Hashable](
    generators: frozenset[T],
) -> Group[FreeWord[T]]:
    def validate(word: FreeWord[T]) -> None:
        if any(generator not in generators for generator, _ in word.letters):
            raise ValueError("word contains an unknown generator")

    def inverse(word: FreeWord[T]) -> FreeWord[T]:
        validate(word)
        return FreeWord(
            tuple(
                (generator, not is_inverse)
                for generator, is_inverse in reversed(word.letters)
            )
        )

    def operation(left: FreeWord[T], right: FreeWord[T]) -> FreeWord[T]:
        validate(left)
        validate(right)
        return FreeWord(reduce_letters((*left.letters, *right.letters)))

    return Group(
        identity=FreeWord(),
        inv=inverse,
        op=operation,
    )

自由群の要素は既約語として正規化されています。積では2つの語を連結してから、隣接する逆元の組を消去します。逆元では語を逆順にし、各文字の is_inverse を反転します。

普遍性

自由群の普遍性は、次のように表せます。任意の群 $G$ と写像 $f : X \to G$ に対して、次の図式を可換にする準同型 $\hat{f}$ が一意に存在します。

\begin{array}{ccc}
X & \xrightarrow{\iota} & F(X) \\
\downarrow{f} & & \downarrow{\hat{f}} \\
G & = & G
\end{array}

図式の要点は、生成元 $x$ の行き先 $f(x)$ を決めると、任意の語の値が積と逆元によって決まることです。

\hat{f}(x_1^{\varepsilon_1}\cdots x_n^{\varepsilon_n})
=
f(x_1)^{\varepsilon_1}\cdots f(x_n)^{\varepsilon_n}

写像を拡張する

free_group_extension.py

from __future__ import annotations

from collections.abc import Callable, Hashable

from free_group import FreeWord
from group import Group


def extend_generator_map[T: Hashable, G](
    free: Group[FreeWord[T]],
    target: Group[G],
    generator_map: Callable[[T], G],
) -> Callable[[FreeWord[T]], G]:
    def evaluate(word: FreeWord[T]) -> G:
        result = target.identity
        for generator, is_inverse in word.letters:
            image = generator_map(generator)
            if is_inverse:
                image = target.inv(image)
            result = target.op(result, image)
        return result

    return evaluate

evaluate() は、語の各文字を順番に対象群へ写します。既約語の中で逆元の組が消去されても、対象群でも元と逆元の積が単位元になるため、評価結果は変わりません。

`Z/5Z` への拡張

生成元 $x$ と $y$ から自由群を作り、$x$ を $1$、$y$ を $2$ へ写します。

free_group_example.py

from cyclic import Cyclic, cyclic_group
from free_group import FreeWord, free_group
from free_group_extension import extend_generator_map


generators = frozenset({"x", "y"})
free = free_group(generators)
target = cyclic_group(5)
evaluate = extend_generator_map(
    free,
    target,
    generator_map=lambda generator: {
        "x": Cyclic(5, 1),
        "y": Cyclic(5, 2),
    }[generator],
)

x = FreeWord((("x", False),))
y = FreeWord((("y", False),))
x_inverse = free.inv(x)

assert evaluate(x) == Cyclic(5, 1)
assert evaluate(y) == Cyclic(5, 2)
assert evaluate(free.op(x, y)) == Cyclic(5, 3)
assert evaluate(free.op(x, x_inverse)) == target.identity

この例では、生成元上の写像を指定しただけで、$x y$ や $x x^{-1}$ のような語の値も決まります。自由群の普遍性を、語の評価関数として具体的に観察できます。

一意性をどう観察するか

Pythonでは、任意の群と任意の写像について「拡張が一意である」ことを証明できません。しかし、生成元を保ち、群演算を保つ写像であれば、語の値は次の再帰で決まることをコードから確認できます。

evaluate(free.identity) == target.identity
evaluate(free.op(left, right)) == target.op(evaluate(left), evaluate(right))
evaluate(free.inv(word)) == target.inv(evaluate(word))

これは、自由群から対象群への準同型が生成元上の値によって決まることに対応します。群準同型の一般的なデータ構造と核・像については、シリーズ前半の記事で扱っています。

まとめ

自由群の要素は生成元と逆元からなる既約語である
free_group(X) は Group[FreeWord[T]] を返す
生成元上の写像は、語全体への写像へ拡張できる
拡張された写像は群演算と逆元を保つ
この拡張の存在と一意性が自由群の普遍性である