Let's create a free group with Python

What is a group?

A non-empty set $ G $ that can perform some "binary operation" (That is, if $ g, h \ in G $, there is a binary operation $ g \ cdot h $, and the operation result is also the element of G, that is, $ g \ cdot h \ in G $) Those that meet the following conditions are called groups.

-(Identity element) There is an element $ e \ in G $ called an identity element, and $ e \ cdot a = a \ cdot e = a $ holds for any element $ a \ in G $. -(Inverse element) For any element $ a \ in G $, a certain element $ b \ in G $ exists, and $ a \ cdot b = b \ cdot a = e $ holds. $ b $ is called the inverse element of $ a $ and is written as $ a ^ {-1} $ -(Associative law) For any element $ a, b, c \ in G $, $ (a \ cdot b) \ cdot c = a \ cdot (b \ cdot c) $ holds.

Group example

--The integers that can be added are groups (identity element → $ 0 $, inverse element of $ a $ → $ -a $, associative law → addition is known to hold the associative law) --There are also groups of rational numbers that can be added (same as above). There are also groups of rational numbers minus 0 that can be multiplied. (If it is a rational number including 0, it is not a group because the inverse element of 0 cannot be defined.)

Free group

Free groups have no restrictions other than the definition of groups.

Here, we consider $ F_2 $ generated from two elements in the free group. In other words, from the identity element, the two elements $ a, b \ in F_2 $, and the inverse element $ a ^ {-1}, b ^ {-1} $, choose the one you like and calculate, and you like Think of something that can be repeated as many times as possible.

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\\}

What is the inverse element?

I understand that the inverse element of $ a $ is $ a ^ {-1} $, but what about the inverse element of a combination such as $ ab ^ {-1} aab $? Actually, this is the inverse element of each element, and the order is reversed, that is, $ b ^ {-1} a ^ {-1} a ^ {-1} ba ^ {-in this case. 1} $ is the inverse element. In fact, when I try to calculate these

\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}

You can see that it is the inverse element.

Let's do it with Python

Python is easy to do because operator overloading is easy. I will try it immediately.

As an implementation policy, we will have $ a $ and $ ab $ as strings. Also, the inverse element will be held by uppercase letters A and B.

For the inverse element calculation, use the str.swapcase method to flip the string. I've been using Python for many years, but this is the first time I've used swapcase in my life. This method is to make uppercase letters lowercase and lowercase letters uppercase.

'heLLo woRLd,ゎ ゎ ゎ ωπ'.swapcase() # =>The result is next
'HEllO WOrlD,ゎ ゎ ΩΠ'

Unfortunately (?), Small hiragana does not grow, but it seems that Greek letters are converted even if they are not ASCII letters. Well, I don't care about that, so let's implement it.

I've thought about the important things, so let's write the code.

from collections import namedtuple

FreeGroupBase = namedtuple('FreeGroupBase', 's')
class FreeGroup(FreeGroupBase):
    def __init__(self, s: str):
        if s.lower().replace('a', '').replace('b', ''):
            # a,Check if it is generated only from b
            raise ValueError('Unexpected element is contained')

    #Inverse element~I will take it like a
    def __invert__(self) -> 'FreeGroup':
        return FreeGroup(self.s.swapcase()[::-1])

    #Arithmetic*I will do it in
    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:
        'Implementation of arithmetic'
        if not lhs: #lhs is the identity element
            return rhs
        if not rhs: #rhs is the identity element
            return lhs
        if lhs[-1].swapcase() == rhs[0]: # ...a * ~a...In the form of, a* ~can cancel a
            return cls._mul_impl(lhs[:-1], rhs[1:])
        return lhs + rhs #Otherwise, it's just a string attached

    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)

Yeah, it feels good.

Recommended Posts

Let's create a free group with Python
Create a directory with python
Let's make a GUI with python.
Create a virtual environment with Python!
Let's make a graph with python! !!
Let's create a script that registers with Ideone.com in Python.
Let's create a PRML diagram with Python, Numpy and matplotlib.
Let's make a shiritori game with Python
Create a dummy image with Python + PIL.
Let's create a virtual environment for Python
Let's make a voice slowly with Python
Create a word frequency counter with Python 3.4
Let's make a web framework with Python! (1)
Let's make a Twitter Bot with Python!
Let's make a web framework with Python! (2)
Create a Python environment
Create a frame with transparent background with tkinter [Python]
Create a LINE BOT with Minette for Python
Create a virtual environment with conda in Python
Create a page that loads infinitely with python
[Note] Create a one-line timezone class with python
You can easily create a GUI with Python
Create a python3 build environment with Sublime Text3
Create a color bar with Python + Qt (PySide)
Steps to create a Twitter bot with python
Let's replace UWSC with Python (5) Let's make a Robot
Create a decision tree from 0 with Python (1. Overview)
Create a new page in confluence with Python
Create a color-specified widget with Python + Qt (PySide)
Try to make a dihedral group with Python
Create a Photoshop format file (.psd) with python
Create a Python console application easily with Click
Create a Wox plugin (Python)
Create a function in Python
Create a dictionary in Python
Let's run Excel with Python
Create 3d gif with python3
[Python] Create a ValueObject with a complete constructor using dataclasses
Create a homepage with django
[Let's play with Python] Make a household account book
Why not create a stylish table easily with Python?
Create a python development environment with vagrant + ansible + fabric
Let's make a simple game with Python 3 and iPhone
Create a chatbot that supports free input with Word2Vec
Create a python numpy array
Make a fortune with Python
Let's write python with cinema4d.
Create a Layer for AWS Lambda Python with Docker
Create a heatmap with pyqtgraph
[python] Create a date array with arbitrary increments with np.arange
[Python] How to create a 2D histogram with Matplotlib
[Python] Create a Tkinter program distribution file with cx_Freeze
Let's build git-cat with Python
Create a fake Minecraft server in Python with Quarry
[Piyopiyokai # 1] Let's play with Lambda: Creating a Python script
[Super easy] Let's make a LINE BOT with Python.
Create a company name extractor with python using JCLdic
Create a 2d CAD file ".dxf" with python [ezdxf]
Let's make a websocket client with Python. (Access token authentication)
[Python] Create a file & folder path specification screen with tkinter
Create a list in Python with all followers on twitter