[sympy][python] generate galois-groups of nth-root of unity

galois-rou.py

import math, itertools
# pip install sympy
import sympy.combinatorics as symg

def coprimes(n):
    return [i for i in range(n) if math.gcd(n, i) == 1]

# tuple of a normalized cycle of "rx % n"
def cycle(n, r, x):
    g = (r ** i * x % n for i in itertools.count())
    single = [next(g)] + list(itertools.takewhile(lambda v: v != x, g))
    minidx = single.index(min(single))
    return tuple(single[minidx:] + single[:minidx])

def permutation(n, r):
    cycles = [cycle(n, r, x) for x in range(n)]
    return symg.Permutation(list(set(cycles)))

# galois group of the field of n-th root of unity from rational
def nth_root_galois(n):
    return symg.PermutationGroup(*(permutation(n, r) for r in coprimes(n)))

# check permutation is automophism in field of n-th root of unity
def is_aut(n, p):
    # number tuple (a0, a1, ...an-1) as a0 + a1r + a2r^2 +...+ (an-1)r^(n-1)
    f = lambda a: tuple(a[p(i)] for i in range(n))
    a = b = tuple(range(n)) # tuple of indexes
    return f(mul(a, b)) == mul(f(a), f(b))

# multiple for field of n-th root of unity
def mul(a, b):
    # return as: ([(0,0), ...], [(0,1), (1,0), ...], [(0,2), (1,1), ...], ...)
    n = len(a)
    ipairs = [((i + j) % n, (a[i], b[j])) for i in range(n) for j in range(n)]
    return tuple(sorted(p for idx, p in ipairs if i == idx) for i in range(n))

# galois group of root of unity filtered by is_aut() from symmetric group
def nth_root_galois_(n):
    # NOTE: very slow because n! permutations filtered
    sg = symg.named_groups.SymmetricGroup(n)
    return symg.PermutationGroup(*(p for p in sg.generate() if is_aut(n, p)))

assert(nth_root_galois(4) == nth_root_galois_(4))
assert(nth_root_galois(5) == nth_root_galois_(5))
assert(nth_root_galois(6) == nth_root_galois_(6))

def print_table(n):
    cps = coprimes(n)
    g = nth_root_galois(n)
    ps = list(g.generate())
    muls = [[cps[ps.index(l * r)] for r in ps] for l in ps]
    
    title = f"### [Galois-Group of {n}-root of unity (extended from rational)]"
    terms = zip(range(n), ["", "r"] + [f"r^{i}" for i in range(2, n)])
    num = "Element: `" + " + ".join(f"a{i}{r}" for i, r in terms) + "`"

    morphs = [f"- `f{cp}(x) = {cp}*x % {n} => {p}`" for cp, p in zip(cps, ps)]
    validity = f"Automorphisms: {all(is_aut(n, p) for p in ps)}"
    solvable = f"Solvable Group: {g.is_solvable}"
    
    r = range(len(ps))
    h1 = "|       |" + "|".join(f" {cps[i]} " for i in r) + "|"
    h2 = "|-------|" + "|".join("---" for i in r) + "|"
    lines = [f"| **{cps[i]}** |" + "|".join(f" {muls[i][j]} " for j in r) + "|"
             for i in r]
    
    out = (["", title, "", num, ""] + morphs + 
           ["", validity, "", h1, h2] + lines + ["", solvable, ""])
    return print("\n".join(out))

# print 
print_table(2)
print_table(3)
print_table(4)
print_table(5)
print_table(6)
print_table(7)
print_table(8)
print_table(9)

result.md

[Galois-Group of 2-root of unity (extended from rational)]

Element: a0 + a1r

• f1(x) = 1*x % 2 => (1)

Automorphisms: True

	1
1	1

Solvable Group: True

[Galois-Group of 3-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2

• f1(x) = 1*x % 3 => (2)
• f2(x) = 2*x % 3 => (1 2)

Automorphisms: True

	1	2
1	1	2
2	2	1

Solvable Group: True

[Galois-Group of 4-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3

• f1(x) = 1*x % 4 => (3)
• f3(x) = 3*x % 4 => (1 3)

Automorphisms: True

	1	3
1	1	3
3	3	1

Solvable Group: True

[Galois-Group of 5-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3 + a4r^4

• f1(x) = 1*x % 5 => (4)
• f2(x) = 2*x % 5 => (1 2 4 3)
• f3(x) = 3*x % 5 => (1 3 4 2)
• f4(x) = 4*x % 5 => (1 4)(2 3)

Automorphisms: True

	1	2	3	4
1	1	2	3	4
2	2	4	1	3
3	3	1	4	2
4	4	3	2	1

Solvable Group: True

[Galois-Group of 6-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3 + a4r^4 + a5r^5

• f1(x) = 1*x % 6 => (5)
• f5(x) = 5*x % 6 => (1 5)(2 4)

Automorphisms: True

	1	5
1	1	5
5	5	1

Solvable Group: True

[Galois-Group of 7-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3 + a4r^4 + a5r^5 + a6r^6

• f1(x) = 1*x % 7 => (6)
• f2(x) = 2*x % 7 => (1 2 4)(3 6 5)
• f3(x) = 3*x % 7 => (1 3 2 6 4 5)
• f4(x) = 4*x % 7 => (1 4 2)(3 5 6)
• f5(x) = 5*x % 7 => (1 5 4 6 2 3)
• f6(x) = 6*x % 7 => (1 6)(2 5)(3 4)

Automorphisms: True

	1	2	3	4	5	6
1	1	2	3	4	5	6
2	2	4	6	1	3	5
3	3	6	2	5	1	4
4	4	1	5	2	6	3
5	5	3	1	6	4	2
6	6	5	4	3	2	1

Solvable Group: True

[Galois-Group of 8-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3 + a4r^4 + a5r^5 + a6r^6 + a7r^7

• f1(x) = 1*x % 8 => (7)
• f3(x) = 3*x % 8 => (1 3)(2 6)(5 7)
• f5(x) = 5*x % 8 => (1 5)(3 7)
• f7(x) = 7*x % 8 => (1 7)(2 6)(3 5)

Automorphisms: True

	1	3	5	7
1	1	3	5	7
3	3	1	7	5
5	5	7	1	3
7	7	5	3	1

Solvable Group: True

[Galois-Group of 9-root of unity (extended from rational)]

Element: a0 + a1r + a2r^2 + a3r^3 + a4r^4 + a5r^5 + a6r^6 + a7r^7 + a8r^8

• f1(x) = 1*x % 9 => (8)
• f2(x) = 2*x % 9 => (1 2 4 8 7 5)(3 6)
• f4(x) = 4*x % 9 => (1 4 7)(2 8 5)
• f5(x) = 5*x % 9 => (1 5 7 8 4 2)(3 6)
• f7(x) = 7*x % 9 => (1 7 4)(2 5 8)
• f8(x) = 8*x % 9 => (1 8)(2 7)(3 6)(4 5)

Automorphisms: True

	1	2	4	5	7	8
1	1	2	4	5	7	8
2	2	4	8	1	5	7
4	4	8	7	2	1	5
5	5	1	2	7	8	4
7	7	5	1	8	4	2
8	8	7	5	4	2	1

Solvable Group: True