#!/usr/bin/env python3 # projective.py -- the computational statements of Section 12 ("Projective versions, liberation") of "On the maximality # conjecture for quantum permutation groups" (Claude and Teo), and the unitary group duals of Section 10.3. # # python3 projective.py duals unitary group duals: 119 law sets at N = 3 (generators in S_2..S_5) and 611 at N = 4 # (generators in S_2..S_4), levels 4, 6, 8, several positions M = U^t U # python3 projective.py det the U_4^2 check: span{eps_A (x) eps_B} meets span{xi_pi : pi in NC(8)} only in 0 # python3 projective.py hyper = O_N^+ at levels 4, 6, 8 for N = 3, 4 # python3 projective.py all three; log in projectiveout.txt # # Unitary group duals. G = U (dual Gamma) U^* with dual Gamma = diag(g_1, ..., g_N) in U_N^+, U in U_N. The fixed vectors # of (u (x) ubar)^{(x) m} for PG are (U (x) Ubar)^{(x) m} applied to the span of the words f_w with # g_{w_1} g_{w_2}^{-1} g_{w_3} g_{w_4}^{-1} ... = 1 (odd legs carry u, even legs ubar). Those of PO_N are Br(2m), which is # O_N-invariant, so only depends on M = U^t U: dim = dim Br - rank of the matrix of the vectors # (U^* (x) U^t)^{(x) m} xi_pi restricted to the nontrivial words, and (U^* (x) U^t)^{(x) m} xi_pi is the tensor product # over the pairs (s,t) of pi of the matrix I (one odd and one even leg), conj(M) (two odd legs), M (two even legs). # PG is classical iff the subgroup generated by the g_i g_j^{-1} is abelian; then is PO_N or PU_N, and # otherwise it should be PO_N^+ = PU_N^+, of dimension C_m. Floating point (SVD), exact Gram ranks for the reference dims. import sys, time, itertools, numpy as np log = open('projectiveout.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_pairs(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 set_partitions(k): def rec(l): if l == 0: yield []; return for q in rec(l - 1): for i in range(len(q)): yield q[:i] + [q[i] + [l - 1]] + q[i + 1:] yield q + [[l - 1]] return [sorted(sorted(b) for b in q) for q in rec(k)] def noncrossing(q): for A, B in itertools.permutations(q, 2): for a1, a2 in itertools.combinations(A, 2): for b1, b2 in itertools.combinations(B, 2): if a1 < b1 < a2 < b2: return False return True P_MOD = 2147483647 def rank_mod(M, p=P_MOD): M = np.array(M, 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 gram(A, B=None): """exact integer Gram matrix A^T B through float64 products (entries are small integers, sums < 2^53)""" B = A if B is None else B; return np.rint(A.astype(np.float64).T @ B.astype(np.float64)).astype(np.int64) def rank_float(M, tol=1e-8): s = np.linalg.svd(M, compute_uv=False); return int((s > tol * s[0]).sum()) if len(s) else 0 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)) # ------------------------------------------------------------------ unitary group duals def pair_vectors(N, k): P = pairings(k); words = np.array(list(itertools.product(range(N), repeat=k)), dtype=np.int64) X = np.ones((len(words), len(P)), dtype=np.int64) for a, p in enumerate(P): for s, t in p: X[:, a] &= (words[:, t] == words[:, s]).astype(np.int64) return P, words, X def twisted_pair_vectors(P, words, N, M): """columns (U^* (x) U^t)^{(x) m} xi_pi in the word basis, as functions of M = U^t U""" Mc = np.conj(M); V = np.zeros((len(words), len(P)), dtype=complex) for a, p in enumerate(P): v = np.ones(len(words), dtype=complex) for s, t in p: if (s % 2) != (t % 2): v *= (words[:, s] == words[:, t]) # legs 0-indexed: even index = odd leg elif s % 2 == 0: v *= Mc[words[:, s], words[:, t]] # two odd legs (indices even): conj(M) else: v *= M[words[:, s], words[:, t]] # two even legs: M V[:, a] = v return V def duals(N, nmax, levels=(4, 6, 8)): rng = np.random.default_rng(5) def haar(n): Z = (rng.standard_normal((n, n)) + 1j * rng.standard_normal((n, n))) / np.sqrt(2); Q, R = np.linalg.qr(Z) return Q * (np.diag(R) / np.abs(np.diag(R))) Ms = [('I', np.eye(N, dtype=complex))] + [(f'random {i+1}', (lambda U: U.T @ U)(haar(N))) for i in range(2)] data = {k: pair_vectors(N, k) for k in levels} ref = {} for k in levels: P, words, X = data[k]; G = gram(X) hl = [i for i, p in enumerate(P) if halflib(p)]; nc = [i for i, p in enumerate(P) if noncrossing_pairs(p)] ref[k] = {'Br': rank_mod(G), 'HL': rank_mod(G[np.ix_(hl, hl)]), 'TL': rank_mod(G[np.ix_(nc, nc)])} out(f' N={N}, generators in S_2..S_{nmax}; reference dims {ref}; positions M: {[m for m, _ in Ms]}') lawsets = {}; ntuples = 0; t0 = time.time() for n in range(2, nmax + 1): perms = [np.array(p) for p in itertools.permutations(range(n))] reps = {} for p in perms: reps.setdefault(cycle_type(p), p) for g0 in reps.values(): for rest in itertools.product(perms, repeat=N - 1): gens = [g0] + list(rest); ntuples += 1 G1 = np.array(gens); Ginv = np.array([np.argsort(g) for g in gens]) prev = G1; key = []; prods = {} for length in range(2, max(levels) + 1): L = Ginv if length % 2 == 0 else G1 # alternating: g, g^-1, g, g^-1, ... prev = np.take_along_axis(np.broadcast_to(prev[:, None, :], (prev.shape[0], N, n)), np.broadcast_to(L[None, :, :], (prev.shape[0], N, n)), axis=2).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: hh = [gens[i][np.argsort(gens[j])] for i in range(N) for j in range(N) if i != j] # g_i g_j^-1 # closure of and its commutativity: generate the subgroup elems = {tuple(np.arange(n))}; frontier = [np.arange(n)] while frontier: x = frontier.pop(); for h in hh: y = x[h] if tuple(y) not in elems: elems.add(tuple(y)); frontier.append(y) el = [np.array(e) for e in elems] classical = all(np.array_equal(x[y], y[x]) for x in el for y in el) lawsets[key] = (prods, classical, n, [g.tolist() for g in gens]) out(f' {ntuples} tuples, {len(lawsets)} distinct law sets ({time.time()-t0:.0f}s)') bad = 0; ncl = 0 for key, (prods, classical, n, gens) in lawsets.items(): ncl += classical for mname, M in Ms: dims = {} for k in levels: P, words, X = data[k]; V = twisted_pair_vectors(P, words, N, M) dims[k] = ref[k]['Br'] - rank_float(V[~prods[k]]) okk = (all(dims[k] == ref[k]['TL'] for k in levels) if not classical else all(dims[k] in (ref[k]['Br'], ref[k]['HL']) for k in levels)) if not okk: bad += 1; out(f' UNEXPECTED: {"classical" if classical else "non-classical"} PG, generators {gens} in S_{n}, M = {mname}: dims {dims}') out(f' classical PG: {ncl} law sets, non-classical: {len(lawsets) - ncl}; unexpected outcomes: {bad} ({time.time()-t0:.0f}s)') # ------------------------------------------------------------------ the U_4^2 check def det_check(): N, k = 4, 8; t0 = time.time() words = np.array(list(itertools.product(range(N), repeat=k)), dtype=np.int64) def eps(idx): # sign of the 4-tuple of indices, 0 if repeated a = words[:, idx]; sgn = np.ones(len(words), dtype=np.int64) for i in range(4): for j in range(i + 1, 4): d = a[:, j] - a[:, i]; sgn *= np.sign(d) return sgn cols = [] for A in itertools.combinations(range(k), 4): B = tuple(i for i in range(k) if i not in A); cols.append(eps(list(A)) * eps(list(B))) E = np.array(cols).T NC = [q for q in set_partitions(k) if noncrossing(q)] X = np.ones((len(words), len(NC)), dtype=np.int64) for a, q in enumerate(NC): for b in q: for l in b[1:]: X[:, a] &= (words[:, l] == words[:, b[0]]).astype(np.int64) rE = rank_mod(gram(E)); rX = rank_mod(gram(X)); Y = np.hstack([E, X]); rY = rank_mod(gram(Y)) out(f' U_4^2 at the color pattern of 8 white legs: {E.shape[1]} vectors eps_A (x) eps_B of rank {rE}, ' f'{len(NC)} noncrossing vectors of rank {rX}, joint rank {rY}: intersection of dimension {rE + rX - rY} ({time.time()-t0:.0f}s)') # ------------------------------------------------------------------ def hyper(): for N in (3, 4): res = {} for k in (4, 6, 8): words = np.array(list(itertools.product(range(N), repeat=k)), dtype=np.int64) cnt = np.zeros(len(words), dtype=np.int64) for s in range(k): for t in range(s + 1, k): cnt += (words[:, s] < words[:, t]).astype(np.int64) theta = np.where(cnt % 2 == 0, 1, -1) P = pairings(k); X = np.ones((len(words), len(P)), dtype=np.int64) for a, p in enumerate(P): for s, t in p: X[:, a] &= (words[:, t] == words[:, s]).astype(np.int64) NCe = [q for q in set_partitions(k) if noncrossing(q) and all(len(b) % 2 == 0 for b in q)] H = np.ones((len(words), len(NCe)), dtype=np.int64) for a, q in enumerate(NCe): for b in q: for l in b[1:]: H[:, a] &= (words[:, l] == words[:, b[0]]).astype(np.int64) TX = theta[:, None] * X rH = rank_mod(gram(H)); rT = rank_mod(gram(TX)); Y = np.hstack([H, TX]); rY = rank_mod(gram(Y)) nc = [i for i, p in enumerate(P) if noncrossing_pairs(p)]; rTL = rank_mod(gram(X[:, nc])) res[k] = (rH + rT - rY, rTL) out(f' N={N}: dim C_(k) (and dim TL(k)) for k = 4, 6, 8: {res} ' f'{"= O_N^+" if all(a == b for a, b in res.values()) else "DIFFERS"}') if __name__ == '__main__': what = sys.argv[1] if len(sys.argv) > 1 else 'all' out(time.strftime('%d %b %H:%M') + f' projective.py {what}') if what in ('det', 'all'): det_check() if what in ('hyper', 'all'): hyper() if what in ('duals', 'all'): duals(3, 5); duals(4, 4) out(' (paper: 119 and 611 law sets; PO_N^+ whenever PG is non-classical)')