""" flatlin.py -- core library for "Flat linearity of uniform groups". A uniform group is a finite quotient Z_K^{*M} -> Gamma -> Z_K^M, given here by M generators g_1,...,g_M, as permutations. A flat representation is a unitary representation rho : Gamma -> U_K such that each rho(g_i) has every K-th root of unity as eigenvalue, with multiplicity 1. For a finite group, the flat representations are, up to conjugation, the sums of irreducibles whose eigenvalue data on the generators form an exact cover of the K x M grid (one eigenvalue slot per root of unity and per generator). This module computes: * the elements, conjugacy classes, power maps of Gamma, * the character table, numerically (Burnside's algorithm), rounded where only integers are used (dimensions, eigenvalue multiplicities, kernels), * all flat exact covers, * flat linearity: the irreducibles occurring in flat covers jointly separate the points of Gamma, * stationarity: the vector (K dim(rho)/|Gamma|)_rho is a convex combination of indicator vectors of flat covers; decided with an LP and certified exactly with rational arithmetic (a feasible point, or a Farkas certificate). Only numpy and scipy are needed. Python >= 3.8. """ import itertools from fractions import Fraction import numpy as np from scipy.optimize import linprog # --------------------------------------------------------------------------- # finite permutation groups # --------------------------------------------------------------------------- class FiniteGroup: """Finite group generated by permutations of {0,...,n-1}. Product convention: (g*h)(x) = g(h(x)). """ def __init__(self, gens, max_order=20000): gens = [tuple(int(a) for a in g) for g in gens] self.n = len(gens[0]) ident = tuple(range(self.n)) elems = [ident] index = {ident: 0} frontier = [ident] while frontier: new = [] for x in frontier: for g in gens: y = tuple(g[x[i]] for i in range(self.n)) if y not in index: index[y] = len(elems) elems.append(y) new.append(y) if len(elems) > max_order: raise ValueError("group too large") frontier = new self.elems = elems self.index = index self.order = len(elems) self.gens = [index[g] for g in gens] E = np.array(elems, dtype=np.int64) self.E = E self._build_keys() self._build_table() self._build_classes() # fast lookup of permutations through the images of a base def _build_keys(self): E = self.E base = [] for p in range(self.n): base.append(p) keys = np.zeros(self.order, dtype=np.int64) for b in base: keys = keys * self.n + E[:, b] if len(np.unique(keys)) == self.order: break self.base = base self.keys = keys self.sorter = np.argsort(keys) self.sorted_keys = keys[self.sorter] def lookup(self, P): """Indices of the permutations given as rows of P.""" keys = np.zeros(P.shape[0], dtype=np.int64) for b in self.base: keys = keys * self.n + P[:, b] pos = np.searchsorted(self.sorted_keys, keys) return self.sorter[pos] def _build_table(self): E = self.E T = np.empty((self.order, self.order), dtype=np.int32) for i in range(self.order): T[i] = self.lookup(E[i][E]) # row i: e_i * e_j self.T = T ident = 0 inv = np.empty(self.order, dtype=np.int64) rows, cols = np.nonzero(T == ident) inv[rows] = cols self.inv = inv def mul(self, a, b): return int(self.T[a, b]) def power(self, a, m): r = 0 for _ in range(m): r = self.mul(r, a) return r def elem_order(self, a): k, x = 1, a while x != 0: x = self.mul(x, a) k += 1 return k def _build_classes(self): G = self.order cls = -np.ones(G, dtype=np.int64) classes = [] allgens = list(range(G)) if G <= 64 else self.gens for a in range(G): if cls[a] >= 0: continue c = len(classes) orbit = [a] cls[a] = c k = 0 while k < len(orbit): x = orbit[k] k += 1 for g in allgens: y = int(self.T[self.T[g, x], self.inv[g]]) if cls[y] < 0: cls[y] = c orbit.append(y) classes.append(orbit) self.cls = cls self.classes = classes self.nclasses = len(classes) self.class_sizes = np.array([len(c) for c in classes]) self.reps = [c[0] for c in classes] def class_power(self, c, m): """Class of g^m, for g in class c.""" return int(self.cls[self.power(self.reps[c], m)]) # --------------------------------------------------------------------------- # character table (Burnside) # --------------------------------------------------------------------------- def character_table(G, seed=1): """Irreducible characters of G, as an array X[rho, class] (complex).""" r = G.nclasses cls = G.cls C = cls[G.T] # class of e_i e_j N = np.zeros((r, r, r), dtype=np.int64) ci = np.repeat(cls, G.order) cj = np.tile(cls, G.order) np.add.at(N, (ci, cj, C.ravel()), 1) sizes = G.class_sizes a = N / sizes[None, None, :] # a[j,k,l] structure consts rng = np.random.default_rng(seed) coef = rng.normal(size=r) + 1j * rng.normal(size=r) A = np.tensordot(coef, a, axes=(0, 0)) # A[k,l] vals, vecs = np.linalg.eig(A) X = [] for t in range(r): v = vecs[:, t] v = v / v[0] # class 0 = identity d2 = G.order / np.sum(np.abs(v) ** 2 / sizes) d = np.sqrt(d2.real) X.append(d * v / sizes) X = np.array(X) dims = np.rint(X[:, 0].real).astype(int) order = np.lexsort((np.round(-X.real.sum(axis=1), 6), dims)) X, dims = X[order], dims[order] # sanity: orthogonality and sum of squares gram = (X * sizes) @ X.conj().T / G.order assert np.allclose(gram, np.eye(r), atol=1e-6), "character table failed" assert int(np.sum(dims ** 2)) == G.order return X, dims def eigen_multiplicities(G, X, g, K): """For each irreducible, multiplicities of w^0,...,w^{K-1} as eigenvalues of rho(g), with w = exp(2 pi i / K); requires g^K = 1.""" w = np.exp(2j * np.pi / K) pc = [G.class_power(int(G.cls[g]), m) for m in range(K)] out = [] for row in X: mult = [] for j in range(K): s = sum(row[pc[m]] * w ** (-j * m) for m in range(K)) / K mj = int(np.rint(s.real)) assert abs(s - mj) < 1e-6 mult.append(mj) out.append(mult) return np.array(out, dtype=int) # --------------------------------------------------------------------------- # uniform groups and flat covers # --------------------------------------------------------------------------- class FlatProblem: """The integer data of a finite uniform group, and the flat questions. dims : irreducible degrees eig : nirr x (M K) integer array, eigenvalue multiplicities of w^0..w^{K-1} for g_1, then for g_2, etc. kers : for each irreducible, the list of classes in its kernel (class indices start at 0, class 0 being the identity) sizes : class sizes """ def __init__(self, dims, eig, kers, sizes, K, M, cover_cap=400000): self.dims = np.array(dims, dtype=int) self.eig = np.array(eig, dtype=int) self.kers = [set(k) for k in kers] self.sizes = np.array(sizes, dtype=int) self.K, self.M = K, M self.order = int(self.sizes.sum()) self.nirr = len(self.dims) self.cover_cap = cover_cap assert int(np.sum(self.dims ** 2)) == self.order assert self.eig.shape == (self.nirr, M * K) assert all((self.eig[r].reshape(M, K).sum(axis=1) == self.dims[r]).all() for r in range(self.nirr)) self.admissible = [r for r in range(self.nirr) if self.dims[r] <= K and self.eig[r].max() <= 1] self.covers = None self.covers_complete = None self._used = None def all_admissible(self): return len(self.admissible) == self.nirr # -- flat covers -------------------------------------------------------- def _search(self, forced=None, limit=None): """Exact cover search; yields covers (tuples of irreducibles). If forced is given, only covers containing it.""" width = self.M * self.K rows = {r: [c for c in range(width) if self.eig[r][c] == 1] for r in self.admissible} bycol = {c: [r for r in self.admissible if self.eig[r][c] == 1] for c in range(width)} out = [] start_cov = set() start = [] if forced is not None: start_cov = set(rows[forced]) start = [forced] def rec(covered, chosen): if limit is not None and len(out) >= limit: return free = [c for c in range(width) if c not in covered] if not free: out.append(tuple(sorted(chosen))) return col = min(free, key=lambda c: len(bycol[c])) for r in bycol[col]: if any(c in covered for c in rows[r]): continue rec(covered | set(rows[r]), chosen + [r]) rec(start_cov, start) return out def flat_covers(self): if self.covers is None: cov = self._search(limit=self.cover_cap + 1) self.covers_complete = len(cov) <= self.cover_cap self.covers = sorted(set(cov))[:self.cover_cap] return self.covers def ncovers(self): self.flat_covers() return len(self.covers) if self.covers_complete else None def used_irreducibles(self): if self._used is None: self.flat_covers() if self.covers_complete: used = set() for S in self.covers: used.update(S) else: used = set(r for r in self.admissible if self._search(forced=r, limit=1)) self._used = sorted(used) return self._used # -- flat linearity ------------------------------------------------------- def flat_kernel_order(self): common = set(range(len(self.sizes))) for r in self.used_irreducibles(): common &= self.kers[r] return int(sum(self.sizes[c] for c in common)) def is_flat_linear(self): return self.flat_kernel_order() == 1 # -- stationarity ------------------------------------------------------- def target(self): return [Fraction(self.K * int(d), self.order) for d in self.dims] def stationarity(self): """('stationary', weights) / ('not stationary', certificate) / ('undecided', reason) when the covers could not all be listed.""" n = self.nirr used = set(self.used_irreducibles()) missing = [r for r in range(n) if r not in used] if missing: return "not stationary", {"missing irreducible": missing[0]} covers = self.flat_covers() if not self.covers_complete: return "undecided", {"reason": "more than %d covers" % self.cover_cap} lam = self.target() A = np.zeros((n, len(covers))) for s, S in enumerate(covers): for r in S: A[r, s] = 1 b = np.array([float(x) for x in lam]) res = linprog(np.zeros(len(covers)), A_eq=A, b_eq=b, bounds=(0, None), method="highs-ds") if res.status == 0: support = [s for s in range(len(covers)) if res.x[s] > 1e-9] sol = exact_solve([[Fraction(int(A[r, s])) for s in support] for r in range(n)], lam) if sol is not None and all(v >= 0 for v in sol): return "stationary", {covers[s]: v for s, v in zip(support, sol) if v} raise RuntimeError("could not certify LP solution exactly") res2 = linprog(-b, A_ub=A.T, b_ub=np.zeros(len(covers)), bounds=(-1, 1), method="highs-ds") y = [Fraction(v).limit_denominator(10 ** 6) for v in res2.x] ok = all(sum(y[r] for r in S) <= 0 for S in covers) val = sum(yi * li for yi, li in zip(y, lam)) if ok and val > 0: return "not stationary", {"y": y} raise RuntimeError("could not certify infeasibility exactly") class UniformGroup: """Finite uniform group with generators g_1..g_M of common order K, given by permutations; computes its FlatProblem numerically.""" def __init__(self, gens, K, name=""): self.name = name self.K = K self.M = len(gens) self.G = FiniteGroup(gens) G = self.G for g in G.gens: assert G.elem_order(g) == K, "generators must have order K" self.X, self.dims = character_table(G) self.nirr = len(self.dims) blocks = [eigen_multiplicities(G, self.X, g, K) for g in G.gens] self.eig = np.concatenate(blocks, axis=1) # nirr x (M K) kers = [[c for c in range(G.nclasses) if abs(self.X[r][c] - self.dims[r]) < 1e-6] for r in range(self.nirr)] self.problem = FlatProblem(self.dims, self.eig, kers, G.class_sizes, K, self.M) def has_symmetric_action(self): G = self.G M = self.M tests = [] if M >= 2: tests.append([1, 0] + list(range(2, M))) tests.append(list(range(1, M)) + [0]) for p in tests: if not extends_to_automorphism(G, [G.gens[i] for i in p]): return False return True def diagonal_kernel_is_abelian(self): """Lambda = elements whose image in Z_K^M has coordinate sum 0; computed as the closure of the derived subgroup and g_i g_1^{-1}.""" G = self.G lam = diagonal_kernel(G, self.K) for a in lam: for b in lam: if G.mul(a, b) != G.mul(b, a): return False return True def gap_style_line(self, n_id=0, e=1): """The data line in the format written by the GAP census scripts (1-based class indices), for testing census.py.""" P = self.problem kers = [[c + 1 for c in sorted(k)] for k in P.kers] return "U|%d|%d|%d|%d|%d|%d|%d|%s|%s|%s|%s" % ( P.order, n_id, e, self.K, self.M, int(self.has_symmetric_action()), int(self.diagonal_kernel_is_abelian()), [int(d) for d in P.dims], [[int(x) for x in row] for row in P.eig], kers, [int(x) for x in P.sizes]) # delegation def flat_covers(self): return self.problem.flat_covers() def is_flat_linear(self): return self.problem.is_flat_linear() def stationarity(self): return self.problem.stationarity() def report(self): P = self.problem lines = [] lines.append("== %s : |Gamma| = %d, K = %d, M = %d" % (self.name, P.order, self.K, self.M)) lines.append(" classes: %d, irreducible dims: %s" % (len(P.sizes), {int(a): int(b) for a, b in zip( *np.unique(P.dims, return_counts=True))})) lines.append(" S_M symmetric: %s" % self.has_symmetric_action()) lines.append(" diagonal kernel abelian: %s" % self.diagonal_kernel_is_abelian()) lines.append(" admissible irreducibles: %d of %d" % (len(P.admissible), P.nirr)) lines.append(" flat covers (iso classes of flat reps): %s" % P.ncovers()) lines.append(" irreducibles used by flat covers: %d" % len(P.used_irreducibles())) lines.append(" common kernel of flat reps: order %d -> flat linear: %s" % (P.flat_kernel_order(), P.is_flat_linear())) verdict, data = P.stationarity() lines.append(" stationarity: %s" % verdict) if verdict == "stationary": if len(data) <= 40: lines.append(" exact weights (cover dims -> weight):") for S, v in sorted(data.items(), key=lambda t: t[0]): lines.append(" %s %s" % ( [int(P.dims[r]) for r in S], v)) else: lines.append(" exact weights: %d covers in the support" % len(data)) elif verdict == "not stationary": if "missing irreducible" in data: r = data["missing irreducible"] lines.append(" irreducible #%d (dim %d) occurs in no flat " "representation" % (r, P.dims[r])) else: lines.append(" Farkas certificate y = %s" % [str(v) for v in data["y"]]) return "\n".join(lines) def diagonal_kernel(G, K): """Elements of the diagonal kernel: subgroup generated by commutators of the generators' closure and g_i g_1^{-1}.""" gens = G.gens seeds = set() for a in gens: for b in gens: # [a,b] = a b a^-1 b^-1 c = G.mul(G.mul(a, b), G.mul(int(G.inv[a]), int(G.inv[b]))) seeds.add(c) for g in gens[1:]: seeds.add(G.mul(g, int(G.inv[gens[0]]))) # normal closure of the seeds = subgroup generated by all conjugates elems = {0} frontier = [0] gen_set = set() for s in seeds: for x in range(G.order): gen_set.add(G.mul(G.mul(x, s), int(G.inv[x]))) gen_set = list(gen_set) while frontier: new = [] for x in frontier: for s in gen_set: y = G.mul(x, s) if y not in elems: elems.add(y) new.append(y) frontier = new assert len(elems) * K == G.order, "diagonal kernel has wrong index" return sorted(elems) # --------------------------------------------------------------------------- # helpers # --------------------------------------------------------------------------- def extends_to_automorphism(G, images): """Does g_i -> images[i] extend to an automorphism of G? Checked by building the graph of the map on all elements via words.""" phi = {0: 0} frontier = [0] while frontier: new = [] for x in frontier: for g, h in zip(G.gens, images): y = G.mul(g, x) z = G.mul(h, phi[x]) if y in phi: if phi[y] != z: return False else: phi[y] = z new.append(y) frontier = new if len(set(phi.values())) != G.order: return False # homomorphism check on generators suffices with the word construction for x in range(G.order): for g, h in zip(G.gens, images): if phi[G.mul(x, g)] != G.mul(phi[x], h): return False return True def exact_solve(A, b): """Solve A x = b exactly (Fractions); A has full column rank. Returns x or None if inconsistent.""" m = len(A) n = len(A[0]) if m else 0 M = [list(A[i]) + [b[i]] for i in range(m)] piv_cols = [] row = 0 for col in range(n): p = next((i for i in range(row, m) if M[i][col] != 0), None) if p is None: continue M[row], M[p] = M[p], M[row] pv = M[row][col] M[row] = [v / pv for v in M[row]] for i in range(m): if i != row and M[i][col] != 0: f = M[i][col] M[i] = [a - f * c for a, c in zip(M[i], M[row])] piv_cols.append(col) row += 1 for i in range(row, m): if M[i][n] != 0: return None x = [Fraction(0)] * n for i, col in enumerate(piv_cols): x[col] = M[i][n] # verify for i in range(m): if sum(A[i][j] * x[j] for j in range(n)) != b[i]: return None return x def perm_from_function(f, points): idx = {p: i for i, p in enumerate(points)} return tuple(idx[f(p)] for p in points)