群とは

なにか「2項演算」ができる、空集合でない集合$G$であって、
(つまり、$g, h \in G$とすると、2項演算$g\cdot h$があり、演算結果もGの元、つまり$g\cdot h\in G$となるものであって)
次の条件を満たすもののことを群といいます。

(単位元) 単位元と呼ばれる元$e\in G$があり、任意の元$a \in G$に対し、$e\cdot a = a \cdot e = a$が成り立つ
(逆元) 任意の元$a\in G$に対し、ある元$b \in G$が存在し、$a\cdot b = b \cdot a = e$が成り立つ。$b$は$a$の逆元と呼ばれ、$a^{-1}$と書く
(結合法則) 任意の元$a, b, c \in G$に対し、$(a\cdot b)\cdot c = a \cdot (b \cdot c)$が成り立つ

群の例

足し算ができる整数は、群です(単位元→$0$, $a$の逆元→$-a$, 結合法則→足し算は結合法則が成り立つことが知られている)
足し算ができる有理数も群です(同上)。また、掛け算ができる、有理数から0を除いたもの、も群です。(0も含む有理数だと、0の逆元が定義できないので群ではありません)

自由群

群の定義以外、何も制約がないのが自由群です。

ここでは、自由群の中でも2つの元から生成される$F_2$について考えます。つまり、単位元と、2つの元$a, b \in F_2$と、その逆元$a^{-1}, b^{-1}$から、好きなのを選んで演算して、を好きなだけ繰り返してできるものを考えます。

$F_2 = \{e, a, b, a^{-1}, b^{-1}, aa, ab, ab^{-1}, ba, ba^{-1}, bb, a^{-1}b, a^{-1}a^{-1}, a^{-1}b^{-1}, \dots\}$

逆元は?

$a$の逆元が$a^{-1}$なのは分かりましたが、では、$ab^{-1}aab$など、組み合わさったものの逆元はどうなるでしょう?
実はこれは、それぞれの元の逆元を取って、さらに、順番を逆転させたもの、つまりこの場合は$b^{-1}a^{-1}a^{-1}ba^{-1}$が逆元になります。
実際、これらを演算してみると

\begin{eqnarray}
ab^{-1}aab\cdot b^{-1}a^{-1}a^{-1}ba^{-1} & = & ab^{-1}aa \cdot a^{-1}a^{-1}ba^{-1}\\
& = & ab^{-1}a \cdot a^{-1}ba^{-1}\\
& = & ab^{-1} \cdot ba^{-1}\\
& = & a \cdot a^{-1}\\
&=&e\\
\\
b^{-1}a^{-1}a^{-1}ba^{-1}\cdot ab^{-1}aab & = & b^{-1}a^{-1}a^{-1}b\cdot b^{-1}aab\\
& = & b^{-1}a^{-1}a^{-1}\cdot aab\\
& = & b^{-1}a^{-1}\cdot ab\\
& = & b^{-1}\cdot b\\
& = & e
\end{eqnarray}

確かに、逆元になっていることが分かります。

Pythonでやってみよう

Pythonは演算子オーバーロードが簡単なのでやりやすいですね。
早速やってみます。

実装方針として、$a$とか$ab$とかを、文字列で持つことにします。
また、逆元は大文字のA, Bで持つことにします。

逆元計算のためには、str.swapcaseメソッドを使い、文字列をひっくり返します。
長年Pythonを使っていましたが、swapcaseを使ったのは人生で初めてです。
なんと、このメソッドは、大文字は小文字に、小文字は大文字にする、というメソッドです。

'heLLo woRLd, ゎぃゎ ヵッォ ゃ ωπ'.swapcase() # => 結果は次行
'HEllO WOrlD, ゎぃゎ ヵッォ ゃ ΩΠ'

残念ながら(?)、小さいひらがなは大きくなりませんが、ASCII文字じゃなくてもギリシャ文字は変換されるらしいです。まぁ、そんなことはどうでもいいので実装しましょう。

大事なことは大体考えたので、コードをガーッと書きましょう。

from collections import namedtuple

FreeGroupBase = namedtuple('FreeGroupBase', 's')
class FreeGroup(FreeGroupBase):
    def __init__(self, s: str):
        if s.lower().replace('a', '').replace('b', ''):
            # a, bのみから生成されているか確認
            raise ValueError('Unexpected element is contained')

    # 逆元を ~a のように取ることにします
    def __invert__(self) -> 'FreeGroup':
        return FreeGroup(self.s.swapcase()[::-1])

    # 演算を * で行うことにします
    def __mul__(self, other: 'FreeGroup') -> 'FreeGroup':
        return FreeGroup(self._mul_impl(self.s, other.s))

    @classmethod
    def _mul_impl(cls, lhs: str, rhs: str) -> str:
        '演算の実装'
        if not lhs: # lhsが単位元
            return rhs
        if not rhs: # rhsが単位元
            return lhs
        if lhs[-1].swapcase() == rhs[0]: # ...a * ~a... の形だと、a * ~aを打ち消せる
            return cls._mul_impl(lhs[:-1], rhs[1:])
        return lhs + rhs # そうでなければ、文字列を単にくっつけたもの

    def __repr__(self) -> 'str':
        if not self.s:
            return 'e'
        return ' * '.join(e if e.lower() else '~' + e.tolower() for e in self.s)

a = FreeGroup('a')
b = FreeGroup('b')
e = FreeGroup('')

g = a * b * b * a * ~b * ~b * ~a * a * b * (a * a * b)
print(g)
print(g * ~g)
print(~g * g)

うん、なんかいい感じにできてますね。

Pythonで自由群を作ってみる

群とは

群の例

自由群

逆元は?

Pythonでやってみよう