Oregon Curriculum Network

# Group Theory¶

Group Theory is usually presented as a branch of exploration that started with Galois Theory, which in turn traces to searching for all roots of a polynomial, or at least knowing in principle how many one has.

The concept of a Group only makes sense in connection with other concepts: Ring and Field.

The School of Tomorrow does not aim to provide exhaustive treatment of topics touched on. You're in a web of windows, frames of reference. The School of Tomorrow is a hub of hyperlinks, floating in cyberspace (Cyberia).

## Permutations¶

One of the most abstract ways to understand Finite Groups, in a way that exercises coding skills, is to use permutations. A permutation is a reordering of elements. Think of pairing every lowercase letter with every other lowercase letter, throwing in a space.

In [1]:
from string import ascii_lowercase as letters
from random import shuffle
members = list(letters + " ")
mem_copy = members[:]
shuffle(mem_copy)
p = {key:value for key, value in zip(members, mem_copy)}
p
Out[1]:
{'a': 'p',
'b': 'j',
'c': 'f',
'd': 'r',
'e': 's',
'f': 't',
'g': 'b',
'h': 'm',
'i': 'x',
'j': 'y',
'k': ' ',
'l': 'c',
'm': 'd',
'n': 'o',
'o': 'i',
'p': 'e',
'q': 'q',
'r': 'n',
's': 'u',
't': 'l',
'u': 'a',
'v': 'h',
'w': 'v',
'x': 'z',
'y': 'w',
'z': 'k',
' ': 'g'}

For a more complete implementation of a Permutation type, you might want to check these other resources:

In Group Theory, we'll visit the idea of totatives, as we do in Number Theory as well. The totatives of N, multiplied modulo N, form a group. The totative of N module N when N is prime, form a field.

The properties of a Group are often summarized with the acronym CAIN, which is somewhat a worplay on Abel, one of the founders of Group Theory.

CAIN:

• Closure: given an operation *, every $a * b$ is in the group
• Associativity: $(a * b) * c == a * (b * c)$ Abelian groups commutative
• Inverse: every element has an inverse such the e * ~e = 1
• Neutral element: one element serves as an identity (call it 1)

Here's a simple integer-like class that builds in the modulus, so we can use the standard operators yet have the operation carried out modulo N.

We could flesh this out more. Subtracting is adding the additive inverse. Division is multiplying by the multiplicative inverse. That's why these two operations are, in a sense, "syntactic sugar" once we've defined an inverse vis-a-vis each of these operations.

In [2]:
class Mod:

_modulus = 12

def __init__(self, n):
self.value = n % self._modulus

def __eq__(self, other):
return self.value == other.value % self._modulus

def __repr__(self):
return "({} mod {})".format(self.value, self._modulus)

return type(self)(self.value + other.value)

def __mul__(self, other):
return type(self)(self.value * other.value)

def __pow__(self, n):
return type(self)(pow(self.value, n, self._modulus))

You'll find more details on the code below in Number Theory.

In [3]:
def gcd(a, b):
while b:
b, a = a % b, b
return a

def totatives(n):
return [totative for totative in range(1, n)
if gcd(totative, n) == 1]
In [4]:
totatives(12)
Out[4]:
[1, 5, 7, 11]
In [5]:
group_12 = map(Mod, totatives(12))
In [6]:
list(group_12)
Out[6]:
[(1 mod 12), (5 mod 12), (7 mod 12), (11 mod 12)]

The itertools module (Standard Library) gives us a Cartesian Product, meaning we may quickly construct a Cayley Table for our group.

In [7]:
from itertools import product
In [8]:
group_12 = map(Mod, totatives(12))
n = list(group_12)
In [9]:
n
Out[9]:
[(1 mod 12), (5 mod 12), (7 mod 12), (11 mod 12)]

Iterators get "used up" in Python, meaning once you've traversed an iterator, you need to recreate it from scratch. The name table points to a listing of every member paired both with itself, and every other member of the group.

The list comprehension makes multiplication the operator for this Cayley Table, and shows Closure, meaning every outcome, every product, is a member of the Group.

In [10]:
table = product(n, n)
In [11]:
[a * b for a, b in table]  # closure
Out[11]:
[(1 mod 12),
(5 mod 12),
(7 mod 12),
(11 mod 12),
(5 mod 12),
(1 mod 12),
(11 mod 12),
(7 mod 12),
(7 mod 12),
(11 mod 12),
(1 mod 12),
(5 mod 12),
(11 mod 12),
(7 mod 12),
(5 mod 12),
(1 mod 12)]
In [12]:
table
Out[12]:
<itertools.product at 0x10f5b1820>
In [13]:
list(table)
Out[13]:
[]

What happens if the modulus N is prime? Then by definition, every number from 1 up to N-1 is a totative of N. The totient of N, where N is prime, is N-1.

In this case, addition joins multiplication as an operator with group properties, while the distributive property connects the two operations thusly:

$$A * (B + C) = (A * B) + (A * C)$$

That means we have a Field.

A Ring is between a Group and a Field in that it features two operations, but without inverses and/or closure for one of them.

In [14]:
Mod._modulus = 13
In [15]:
group_13 = map(Mod, totatives(13))
n = list(group_13) + [Mod(0)] # 0 is added yet has no multiplicative inverse
In [16]:
table = product(n, n)                   # Cayley Table
sums = [a + b for a, b in table]        # check addition this time
all([the_sum in n for the_sum in sums]) # closure
Out[16]:
True