Structure of finite Abel group (1)

Copyright Statement：This article is the blogger's window(Colin Cai)Original，Welcome to repost。If you want to repost，The original website must be indicated

 /Colin-Cai/p/

author：window

QQ/WeChat：6679072

E-mail：6679072@

I am going to talk about the finite Abel group, and I always feel that for a programmer, the various subjects of discrete mathematics are good, both from a training mindset and from a practical perspective. I always feel that programmers should pay attention to theoretical learning, which naturally includes mathematics. Of course, there are also some programs in the explanation process, after all, programs are the root of programmers.

Mapping

Sequence(pair), is to tie two things together, we can remember them as $<a, b>$

We can define $<a,b>=\{\{a\},\{a,b\}\}$

Why is this definition meant the order of a/b? Think about it yourself and pay attention to the above definition.

$<a,a>=\{\{a\}\}$

Of course, you can use other definition methods as long as uniqueness is guaranteed.

The set $A$ and set $B$Cartesian product(Cartesian Product), defined as follows:

$A\times B=\{<a,b>|a\in A,b\in B\}$

That is, iterates through all the possibilities of elements of $A$ and elements of $B$ to form a sequence.

For example, the Cartesian product of $\{1,2\}$ and $\{a,b,c\}$ is $\{<1,a>,<1,b>,<1,c>,<2,a>,<2,b>,<2,c>\}$

Mapping(mapping), also calledfunction(function), this concept is well known to everyone, and we still need to formally describe it here

The mapping $f$ from the set $A$ to the set $B$ refers to a subset of $A\times B$, satisfying the

 $\forall a\in A \exists!b\in B:<a,b>\in f$

To put it simply, for any element $a$ in $A$, $f(a)$ are elements in $B$, existing and unique.

Where $A$ is the definition domain of $f$ and $B$ is the value domain of $f$.

Half group

Later, we look at a special function, for the set $A$,

Its definition domain is $A\times A$, and the value domain is $A$

We call this function on the set $A$Binary operation, such as our common addition, subtraction, multiplication, and division (of course, whether it is for integer sets, rational number sets, real number sets, complex sets)...

If the binary operation $f$ on the set $A$ satisfies the law of association, that is

$\forall a,b,c\in A:f(<<a,b>,c>) = f(<a,<b,c>>)$

Then the set $A$ is called a binary operation $f$.Half group(semigroup)

This is not what we are used to writing. We generally call binary operations that satisfy the law of combination multiplication. We are more used to using infix expressions. If multiplication satisfies the law of commutation, then the method of multiplication satisfies the law of commutation is

$\forall a,b,c\in A:(a\cdot b)\cdot c=a\cdot (b\cdot c)$

There are many such semi-group examples in reality, such as integer sets forming semi-groups under multiplication, and non-0 integer sets forming semi-groups under multiplication.

For example, the set of second-order real numbers matrixes form a semi-group under matrix multiplication.

Of course, integers also form semigroups under addition, but they may be a little confused, adding, multiplication...

In fact, in mathematics, we need to pay attention to the invariance of form. As for what we call it, it doesn’t matter, it really doesn’t matter.

group

If a half group meets the following two points:

(1) There is a dollar $e$ in the semi-group, and for any dollar $x$ in the semi-group, there is a dollar $x$.

      $x=x\cdot e=e\cdot x$

(2) For any dollar $x$ in the semi-group, there is a $x'$, so

      $x\cdot x' = x' \cdot x = e$

Then, let's call this semi-groupgroup(group)。

Among them, $e$ that meets the first condition is theNo. 1, orUnits;The $x$ and $x'$ in the second condition are each otherInverse。

Let’s give some practical examples of groups:

The set of real numbers is a group on addition, where the unit is 0 (any number plus 0 value remains unchanged), and the inverse of each element is its opposite number (any number and its opposite number are added equal to 0);

The set of non-zero real numbers is a group in multiplication, where the unit is 1 (any number is multiplied by 1 and the value remains unchanged), and the inverse of each element is its reciprocal (any number and its reciprocal are equal to 1). Note here that the set of real numbers is not a group in multiplication, because 0 does not have inverse;

For a specific positive integer n, the set composed of a non-singular matrix of real n order (that is, the determinant value is not 0) is a group in matrix multiplication, where the unit is $I_{n}$ and the inverse of each element is its inverse matrix.

The number of elements in a group is called the order of the group.

Groups of the same order

This section is to write a program to see which groups of given orders are there.

As an important branch of abstract algebra, group theory cannot be explained clearly in just a few simple sentences. In fact, this series will only talk about a small part of group theory. So this section is mainly about violent solutions.

We want to violently find out which groups are given an n-order group (that is, the number of elements in the group is n). Then we set these elements to $S_0, S_1,...S_{n-1}$. When there is no misunderstanding, we can use $0,1,...S_{n-1}$ to represent $S_0, S_1,...S_{n-1}$. Well, all of them have reached the level of abstract algebra, and the symbols are not necessarily important.

We use a square matrix $A$ of $n\times n$ to represent this group, which is actually the multiplication table on this group.

$S_a\cdot S_b = S_{A_{a,b}}$

Let's use Python to implement it, and use the built-in array library to simulate a square array using the one-dimensional array ${B}$.

$A_{a,b} = B_{a*n+b}$

First establish a high-level brute force solution framework, as follows:

def make_search_all_groups_func(get_all_maybe_groups, is_group, print_group):
    def f(n):
        for s in get_all_maybe_groups(n):
            if is_group(n, s):
                print_group(n, s)
    return f

get_all_maybe_groups is used to generate binary operations that may be a group, because there may be many objects to be selected, and gen_all_maybe_groups should generally be a generator.

is_group is used to determine whether this binary operation can be used as a multiplication table for the group.

If so, print out the group. Of course, this group can be represented by a multiplication table.

So, we can write this print group like this:

def print_group(n, s):
    a = 0
    b = 0
    print('group:')
    for r in s:
        print('S%d x S%d = S%d' % (a, b, r))
        if b < n - 1:
            b += 1
        else:
            a += 1
            b = 0
    print('', end='', flush=True)

The above is not difficult, so the next question is how to traverse all possible binary operations. Just think about it, this should be $n\times n$$\{0,1...n-1\}$ to do Cartesian product.

Fortunately, Python has itertools library that can do Cartesian product.

(range(n), range(n) ...)

Unfortunately, it is a call with no fixed parameters, but Python can support it. The supported method is this *, expand the parameters, which is very similar to Lisp's apply function.

import array
import itertools as it
def get_all_maybe_groups_v1(n):
    return map(lambda s:('i', s), (*[range(n)]*(n**2)))

Adding a map before converts each element into an array. The reason why it becomes an array is that the array addressing efficiency is high.

Then, it is necessary to determine whether it is a group. If it is a group, three steps are required:

(1) Determine whether binary operations meet the binding law

(2) Determine whether there is a unit

(3) Determine whether each element has an inverse element

Then the code can be written as follows:

def is_group_v1(n, s):
    if not assoc_low(n, s): #Combined law test
        return False
    e = get_ident_element(n, s) #Find a yaoyuan
    if e is None:
        return False
    if not each_can_inverse(n, s, e): #See if each element has an inverse element
        return False
    return True

Implement three functions respectively.

The law of combination is also a Cartesian product to traverse all possibilities, and test it separately

def assoc_low(n, s):
    mul = lambda a, b : s[a * n + b] #multiplication
    for a, b, c in (range(n), range(n), range(n)):
        if mul(mul(a, b), c) != mul(a, mul(b, c)):
            return False
    return True

Let’s look for the yaoyuan again to see if there is a yuan. All yuan and its multiplication left and right will not change.

def get_ident_element(n, s):
    mul = lambda a, b : s[a * n + b] #multiplication
    for i in range(n):
        flag = True
        for j in in range(n):
            if mul(i, j) != j or mul(j, i) != j:
                flag = False
                break
        if flag:
            return i
    return None

Finally, let’s see if each element has an inverse element, and it is still traversal.

def each_can_inverse(n, s, e):
    mul = lambda a, b : s[a * n + b] #multiplication
    for i in range(n):
        flag = False
        for j in range(n):
            if mul(i, j) == e and mul(j, i) == e:
                flag = True #Found the inverse element, mark it and find it
                break
        if not flag:
            return False #No inverse element was found at present
    return True

In this way, we implement a search version

search_all_groups_v1 = make_search_all_groups_func(get_all_maybe_groups_v1, is_group_v1, print_group)

As a result, we called search_all_groups_v1(4) and hoped to search for the 4th order group, and found that the calculation was very slow.

Can we be faster?

Many times, we find some theorems to speed up the search.

Let's prove a proposition first:

For any group $<G,\cdot>$,

$\forall a,b,c\in G:a\cdot b=a\cdot c \rightarrow b = c$

$\forall a,b,c\in G:b\cdot a=c\cdot a \rightarrow b = c$

actually,

 $a \cdot b = a \cdot c$
 $\rightarrow a^{-1}\cdot(a \cdot b) = a^{-1}\cdot(a \cdot c)$
 $\rightarrow (a^{-1}\cdot a) \cdot b = (a^{-1}\cdot a) \cdot c$
 $\rightarrow e \cdot b = e \cdot c$
 $\rightarrow b = c$
Among them, $a^{-1}$ is the inverse element of $a$, and $e$ is the unitary element of the group.

Similarly,

$b \cdot a = c \cdot a$
$\rightarrow (b \cdot a) \cdot a^{-1} = (c \cdot a) \cdot a^{-1}$
$\rightarrow b \cdot (a \cdot a^{-1}) = c \cdot (a \cdot a^{-1})$
$\rightarrow b \cdot e = c \cdot e$
$\rightarrow b = c$

So we know that for any element in the group, the result obtained by multiplying by different elements is different.

Then think about it carefully, for any element $a$ in the group, multiply by $S_{0}, S_{1}...S_{n-1}$ to obtain $a \cdot S_{0}, a \cdot S_{1}...a \cdot S_{n-1}$ is an arrangement of $S_0, S_1...S_{n-1}$,

The $S_0 obtained by multiplying $S_{0}, S_{1}...S_{n-1}$ \cdot a ,S_1 \cdot a ...S_{n-1} \cdot a $ is also an arrangement of $S_0, S_1...S_{n-1}$.

Each number in a matrix such as a multiplication table is unique in the row and column to which it belongs.

Using this property, when we screen binary operations, we can avoid using Cartesian products, so that most binary operations that cannot be group multiplication can be easily screened out.

In addition, we can let $S_0$ be the unit of the group as soon as we come up, so the multiplication table of $n\times n$ has fixed the $2n-1$ term in it.

def get_all_maybe_groups_v2(n):
    #0 is a unit, first fix 2n-1 item
    arr = ('i', n * n * [0])
    for i in range(n):
        arr[i] = i
        arr[n * i] = i
    #Start traversal from 1 row and 1 column
    row, col = 1, 1
    FORWARD, BACKWARD = True, False
    while True:
        #At the beginning, the search direction is defaulted to backward, and only if a value is successfully found can it be changed to forward.
        direction = BACKWARD
        #Search the smallest value from the current value in turn, satisfying rows/columns without duplication
        for i in range(arr[row * n + col], n):
            flag = True
            for j in (range(row * n, row * n + col), range(col, row * n + col, n)):
                if arr[j] == i:
                    #If there is a duplication in the ranks, the error flag will be set
                    flag = False
                    break
            if flag:
                #The new value was successfully found, and the flag was set to true to indicate that it was found
                direction = FORWARD
                arr[row * n + col] = i
                break
        if direction == FORWARD:
            #After finding the current value, you can continue to move forward and coordinates forward one
            col += 1
            if col >= n:
                col = 1
                row += 1
                if row == n:
                    #At this time, it is full and a new candidate binary operation has been obtained
                    yield arr
                    #Retreat two lines and add two elements
                    #Why can we back so much? Actually, we need to prove it. If you are interested, think about how to prove it.
                    #Because there is no other possible solution when only the last two lines are moved
                    #Intuition can back a little more, but I didn't even think about it myself
                    row = n - 3
                    col = n - 2
                    #Since it is dictionary order, the current search value must start at least from the next one.
                    arr[row * n + col] += 1
                    #The other values ​​afterwards are clear to 0, so that the dictionary order is the order and candidates will not be missed.
                    arr[row * n + col + 1] = 0
                    for i in range((n - 2)*n+1, (n - 1)*n):
                        arr[i] = 0
                    for i in range((n - 1)*n+1, n*n):
                        arr[i] = 0
        else: #direction == BACKWARD
            #The current value was not found, so you can only take a step forward
            #In dictionary order, the current value is clear to 0, and the position after taking a step back must be added to 1, which is the next dictionary order immediately
            arr[row * n + col] = 0
            col -= 1
            if col == 0:
                col = n - 1
                row -= 1
                #There is no way to retreat, and all the values ​​fixed on line 0 have been retreated, which means that the traversal has been completed.
                if row == 0:
                    return
            arr[row * n + col] += 1