Help us understand the problem. What is going on with this article?

Pythonで自由群を作ってみる

More than 1 year has passed since last update.

群とは

なにか「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)

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

gyu-don
来世はパンダになりたい。
https://github.com/gyu-don/
mdrft
量子コンピュータのアプリケーション、ミドルウェア、ハードウェアをフルスタックで開発
https://blueqat.com/
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away