#!/usr/bin/env python3 # orthoduals.py -- Proposition 10.x (group duals are easy over O_N, at low levels) of "On the maximality conjecture for # quantum permutation groups" (Claude and Teo), Section 10.3. # # python3 orthoduals.py all five rows of the table (about 10-20 minutes); log in orthodualsout.txt # python3 orthoduals.py 1 1 6 8 one row: a involutions, b rotation pairs, permutations in S_2..S_n, levels <= kmax # # Setting (Proposition 10.x). A group dual in O_N^+ is given, up to O_N-conjugation, by a involutions s_i and b elements # g_j of a group Gamma, N = a + 2b, acting on a basis f_1..f_N: the alphabet A has the letters s_i (self-inverse) and # g_j, g_j^{-1}. The category of at level k is the set of x in Br(k) supported on the trivial words, # where xi_pi = sum of f_w over the words w compatible with pi (w_t = conj(w_s) on each pair). So # dim C(k) = dim span{xi_pi} - rank(M_nt), M_nt = (coefficient of xi_pi on w)_{w nontrivial, pi in P_2(k)}, # both computed exactly as ranks of integer Gram matrices (words grouped by their compatibility pattern). # "Easy over O_N" means dim C(k) equals dim Br_N(k), dim HL_N(k) or dim TL_N(k) = C_{k/2}, according to whether Gamma is # abelian, half-abelian (xyz = zyx for all letters) or neither. Gamma runs over the subgroups of S_n generated by the # letters; law sets (sets of trivial words of even length <= kmax) are conjugation invariant, so the first letter is # taken up to conjugacy and the others are arbitrary, and the tuples are grouped by law set. import sys, time, itertools, numpy as np from fractions import Fraction as Fr from math import comb log = open('orthodualsout.txt', 'a') def out(s): print(s, flush=True); log.write(s + '\n'); log.flush() def pairings(k): if k == 0: return [()] res = [] for j in range(1, k): rest = [i for i in range(1, k) if i != j] for p in pairings(k - 2): res.append(((0, j),) + tuple((rest[a], rest[b]) for a, b in p)) return res def noncrossing(p): return not any(a < c < b < d or c < a < d < b for (a, b) in p for (c, d) in p) def halflib(p): return all((a - b) % 2 for a, b in p) def rank_mod(G, p): M = np.array(G, dtype=np.int64) % p; n, m = M.shape; r = 0 for c in range(m): nz = np.flatnonzero(M[r:, c]) if len(nz) == 0: continue pr = r + nz[0]; M[[r, pr]] = M[[pr, r]] M[r] = (M[r] * pow(int(M[r, c]), p - 2, p)) % p others = np.flatnonzero(M[:, c]); others = others[others != r] if len(others): M[others] = (M[others] - (M[others, c][:, None] * M[r][None, :]) % p) % p r += 1 if r == n: break return r def exact_rank(G): """rank over Q of an integer matrix: the maximum of the ranks modulo two large primes (a lower bound in general, equal to the rank over Q unless both primes divide the same minors, which we treat as negligible)""" return max(rank_mod(G, 2147483647), rank_mod(G, 1000000007)) class Level: """words of length k over the alphabet of a involutions and b pairs, grouped by compatibility pattern""" def __init__(self, a, b, k): self.k = k; N = a + 2 * b; self.N = N # letters: 0..a-1 involutions, then g_1, g_1^-1, g_2, g_2^-1, ...; conj = index of the inverse letter conj = list(range(a)) for j in range(b): conj += [a + 2 * j + 1, a + 2 * j] self.conj = np.array(conj) self.P = pairings(k); P = self.P; m = len(P) words = np.array(list(itertools.product(range(N), repeat=k)), dtype=np.int8) if k > 0 else np.zeros((1, 0), np.int8) self.words = words # compatibility: for each pairing, all pairs (s,t) have w_t = conj(w_s) comp = np.ones((len(words), m), dtype=bool) cw = self.conj[words] for pi_, p in enumerate(P): for s, t in p: comp[:, pi_] &= words[:, t] == cw[:, s] self.comp = comp # patterns keys = np.packbits(comp, axis=1); _, inv, cnt = np.unique(keys, axis=0, return_inverse=True, return_counts=True) self.pattern = inv.ravel(); self.npat = len(cnt) rows = np.zeros((self.npat, m), dtype=np.int64) rows[self.pattern] = comp.astype(np.int64) self.rows = rows self.G_all = (comp.astype(np.int64).T @ comp.astype(np.int64)) self.dim_span = exact_rank(self.G_all) hl = [i for i, p in enumerate(P) if halflib(p)]; nc = [i for i, p in enumerate(P) if noncrossing(p)] self.dim_hl = exact_rank(self.G_all[np.ix_(hl, hl)]); self.dim_tl = exact_rank(self.G_all[np.ix_(nc, nc)]) def joint_dim(self, trivial): """trivial: boolean array over the words; returns dim C(k)""" cnt = np.bincount(self.pattern[trivial], minlength=self.npat) G_triv = (self.rows * cnt[:, None]).T @ self.rows return self.dim_span - exact_rank(self.G_all - G_triv) def compose(p, q): return p[q] # (p o q)(i) = p[q[i]] def row(a, b, nmax, kmax): N = a + 2 * b; levels = {k: Level(a, b, k) for k in range(2, kmax + 1, 2)} out(f' letters: {a} involution(s), {b} rotation pair(s), N = {N}; span dims by level ' f'{ {k: (L.dim_span, L.dim_hl, L.dim_tl) for k, L in levels.items()} } (Brauer, half-liberated, Temperley-Lieb)') lawsets = {}; ntuples = 0; t0 = time.time() for n in range(2, nmax + 1): perms = list(itertools.permutations(range(n))); perms = [np.array(p) for p in perms] invs = [p for p in perms if np.array_equal(p[p], np.arange(n))] def classes(ps): # one representative per conjugacy class (by cycle type) seen = {}; for p in ps: ct = cycle_type(p) if ct not in seen: seen[ct] = p return list(seen.values()) first = classes(invs) if a > 0 else classes(perms) rest_inv = [invs] * (a - 1 if a > 0 else 0); rest_rot = [perms] * (b - (0 if a > 0 else 1)) for f0 in first: for others in itertools.product(*(rest_inv + rest_rot)): letters_inv = ([f0] + list(others[:a - 1])) if a > 0 else [] letters_rot = list(others[a - 1:]) if a > 0 else [f0] + list(others) # the alphabet, in the order: involutions, then g, g^-1 for each pair alph = letters_inv[:] for g in letters_rot: alph += [g, np.argsort(g)] ntuples += 1 # products of all words of each even length, iteratively key = []; prods = {} W1 = np.array(alph) # (N, n): images of each letter prev = W1 # words of length 1 for length in range(2, kmax + 1): # new word = old word followed by letter: product p_old o letter? We read words left to right as # group elements w_1 w_2 ... acting on the left, so prod(w) = w_1 o w_2 o ... : prod(w x) = prod(w) o x prev = prev[:, None, :] # (N^{L-1}, 1, n) nxt = np.take_along_axis(np.broadcast_to(prev, (prev.shape[0], N, n)), np.broadcast_to(W1[None, :, :], (prev.shape[0], N, n)), axis=2) prev = nxt.reshape(-1, n) if length % 2 == 0: prods[length] = np.all(prev == np.arange(n), axis=1) key.append(np.packbits(prods[length]).tobytes()) key = tuple(key) if key not in lawsets: ab = all(np.array_equal(compose(x, y), compose(y, x)) for x in alph for y in alph) hab = ab or all(np.array_equal(compose(compose(x, y), z), compose(compose(z, y), x)) for x in alph for y in alph for z in alph) lawsets[key] = (prods, 'abelian' if ab else ('half-abelian' if hab else 'free-ish'), n, [p.tolist() for p in alph]) out(f' {ntuples} tuples, {len(lawsets)} distinct law sets ({time.time()-t0:.0f}s)') bad = 0; kinds = {} for key, (prods, kind, n, alph) in lawsets.items(): dims = {k: levels[k].joint_dim(prods[k]) for k in levels} target = {k: (levels[k].dim_span if kind == 'abelian' else levels[k].dim_hl if kind == 'half-abelian' else levels[k].dim_tl) for k in levels} kinds[kind] = kinds.get(kind, 0) + 1 if dims != target: bad += 1; out(f' NOT EASY: {kind}, generators {alph} in S_{n}: dims {dims}, expected {target}') out(f' kinds: {kinds}; law sets not easy over O_N: {bad} ({time.time()-t0:.0f}s)') def cycle_type(p): n = len(p); seen = [False] * n; ct = [] for i in range(n): if not seen[i]: l = 0; j = i while not seen[j]: seen[j] = True; j = p[j]; l += 1 ct.append(l) return tuple(sorted(ct)) if __name__ == '__main__': out(time.strftime('%d %b %H:%M') + ' orthoduals.py') if len(sys.argv) == 5: row(*map(int, sys.argv[1:])) else: for a, b, nmax, kmax in [(1, 1, 6, 8), (0, 2, 6, 8), (2, 1, 5, 8), (1, 2, 5, 6), (3, 1, 4, 6)]: row(a, b, nmax, kmax) out(' (paper: 31, 305, 595, 2339, 917 law sets, all easy over O_N)')