# w48_cayley.py
# Author: David Niedbala Giraudin, ORCID 0009-0009-1526-1178
# Technical assistance: Claude (Anthropic)
#
# Builds the Cayley graph of SD16 x C3 with respect to
#     S = { x, a, a**-1, a x c, a**5 x c**2, a**6 x c, a**6 x c**2 },
# where SD16 = < a, x | a**8 = x**2 = 1, x a x**-1 = a**3 > and C3 = < c >,
# and checks that it has 48 vertices, is 7-regular and contains no cycle of length 4.
# Pure Python, no arguments.  Writes w48.csv in the current directory.
import itertools

def mul(p, q):
    # element (i, j, k) stands for a**i x**j c**k
    i, j, k = p
    i2, j2, k2 = q
    if j == 1:
        i2 = (3 * i2) % 8          # x a**i2 = a**(3 i2) x
    return ((i + i2) % 8, (j + j2) % 2, (k + k2) % 3)

G = [(i, j, k) for i in range(8) for j in range(2) for k in range(3)]
e = (0, 0, 0)
# group axioms (associativity checked on all triples)
for p, q, r in itertools.product(G, repeat=3):
    assert mul(mul(p, q), r) == mul(p, mul(q, r))
inv = {g: next(h for h in G if mul(g, h) == e) for g in G}
S = [(0, 1, 0), (1, 0, 0), (7, 0, 0), (1, 1, 1), (5, 1, 2), (6, 1, 1), (6, 1, 2)]
assert len(set(S)) == 7 and e not in S
assert all(inv[s] in S for s in S), "S is not inverse-closed"

index = {g: n for n, g in enumerate(G)}
edges = set()
for g in G:
    for s in S:
        h = mul(g, s)
        edges.add((min(index[g], index[h]), max(index[g], index[h])))
n = len(G)
adj = [set() for _ in range(n)]
for u, v in edges:
    adj[u].add(v)
    adj[v].add(u)

print("vertices", n, "edges", len(edges), flush=True)
print("degrees", sorted(set(len(a) for a in adj)), flush=True)
bad = [(u, v) for u, v in itertools.combinations(range(n), 2) if len(adj[u] & adj[v]) >= 2]
print("pairs with two common neighbours (4-cycles):", len(bad), flush=True)
tri = sorted(set(sum(1 for y, z in itertools.combinations(adj[x], 2) if z in adj[y]) for x in range(n)))
print("edges inside a neighbourhood, values:", tri, flush=True)
ok = n == 48 and all(len(a) == 7 for a in adj) and not bad
print("RESULT:", "7-regular C4-free graph on 48 vertices" if ok else "FAILED", flush=True)
with open("w48.csv", "w") as f:
    for u, v in sorted(edges):
        f.write("%d,%d\n" % (u, v))