#!/usr/bin/env python3 """jalabert.py - honeycomb, kagome and Eisenstein integers at index 6 (Section 5). 1. Generic F_2 x_Q F_3: exact word counts in the group Gamma = Z^2 x| Z_3 (formula (3.9)), closed walks on the kagome lattice, closed walks on the honeycomb lattice, and the formula with the numbers W_3(2j) = sum_k binom(j,k)^2 binom(2k,k), all compared. Same for F_2 x_Q F_4 with the diamond lattice and the Domb numbers. 2. Theorems 5.10 and 5.11: for every element b + c*zeta of the Eisenstein integers with norm <= 60, the row (1, p, q) of the theorem gives a phase group K_Q of order b^2 + bc + c^2, whose annihilator is the ideal generated by b + c*zeta. All root-of-unity rows of order <= 36 give ideals. The rooted law separates the ideals up to conjugation, for the norms <= 400. 3. The coset graphs for the first ideals are identified (K_33, cube, Heawood, Pappus, Nauru); this part needs networkx, and is skipped if networkx is missing. 4. Theorem 5.15: the density of the 3-step walk, in its hypergeometric and elliptic forms, against the moments W_3(2j); this part needs scipy. 5. The group p3 and the finite limits of the Karlsson matrices (end of Section 5.3): the relations a^3 = b^3 = (ab)^3 = 1 for a = 1^(0), b = 1^(1), and the exact moments and annular multiplicities for the 3 limits discussed in the text, namely the limit of order 24 (cube), the limits with c_4 = 90 (K_33), and the limit of order 72 (Nauru). Output: terminal, and jalabert.log. """ from math import comb, gcd, cos, pi, sqrt from fractions import Fraction as Fr from collections import defaultdict import sys LOG = open(__file__.replace('.py', '.log'), 'w') def out(*a): s = ' '.join(str(x) for x in a) print(s); LOG.write(s + '\n'); LOG.flush() # ------------------------------------------------------------------ 1. generic laws, lattices def W(N, j, memo={}): """E|s|^(2j) for the N-step planar walk: sum of squared multinomial coefficients.""" if (N, j) in memo: return memo[(N, j)] r = 1 if N == 1 else sum(comb(j, a)**2*W(N-1, j-a) for a in range(j+1)) memo[(N, j)] = r; return r def c_generic_two_rows(N, n): return sum(comb(n, 2*j)*N**(n-2*j)*W(N, j) for j in range(n//2+1))//N def word_counts_two_rows(N, nmax): """c_n = (1/2) #{words of length n in the letters b^(i), i in Z_2, b in Z_N, equal to 1 in Gamma = I_Y x| Y}. Elements (t, c), t in Z[Z_N] modulo nothing, product (t,c)(t',c') = (t + y^(-c) t', c+c'); letters c^(0) = (0, c) and c^(1) = (1 - y^(-c), c).""" def shift(t, c): # multiplication by y^(-c) return tuple(t[(k + c) % N] for k in range(N)) letters = [] for c in range(N): letters.append((tuple([0]*N), c)) t = [0]*N; t[0] += 1; t[(-c) % N] -= 1 letters.append((tuple(t), c)) state = {(tuple([0]*N), 0): 1}; res = [] for _ in range(nmax): new = defaultdict(int) for (t, c), m in state.items(): for (t2, c2) in letters: s2 = shift(t2, c) new[(tuple(a + b for a, b in zip(t, s2)), (c + c2) % N)] += m state = new res.append(state.get((tuple([0]*N), 0), 0)//2) return res def lattice_returns(neigh, start, nmax): state = {start: 1}; res = [] for _ in range(nmax): new = defaultdict(int) for v, m in state.items(): for w in neigh(v): new[w] += m state = new; res.append(state.get(start, 0)) return res def kagome(v): m, n, s = v if s == 0: return [(m, n, 1), (m+1, n, 1), (m, n, 2), (m, n+1, 2)] if s == 1: return [(m, n, 0), (m-1, n, 0), (m, n, 2), (m-1, n+1, 2)] return [(m, n, 0), (m, n-1, 0), (m, n, 1), (m+1, n-1, 1)] def honeycomb(v): m, n, s = v return [(m, n, 1), (m+1, n, 1), (m, n+1, 1)] if s == 0 else [(m, n, 0), (m-1, n, 0), (m, n-1, 0)] def diamond(v): a, b, c, s = v return [(a, b, c, 1), (a+1, b, c, 1), (a, b+1, c, 1), (a, b, c+1, 1)] if s == 0 else \ [(a, b, c, 0), (a-1, b, c, 0), (a, b-1, c, 0), (a, b, c-1, 0)] def part1(): ok = True; NM = 9 words = word_counts_two_rows(3, NM) formula = [c_generic_two_rows(3, n) for n in range(1, NM+1)] # kagome: c_n = (1/2) <(2+A)^n delta, delta> kag = lattice_returns(kagome, (0, 0, 0), NM); kag = [1] + kag viak = [sum(comb(n, k)*2**(n-k)*kag[k] for k in range(n+1))//2 for n in range(1, NM+1)] hon = lattice_returns(honeycomb, (0, 0, 0), 2*NM) good = (words == formula == viak) and all(hon[2*j-1] == W(3, j) for j in range(1, NM+1)) \ and all(W(3, j) == sum(comb(j, k)**2*comb(2*k, k) for k in range(j+1)) for j in range(NM+1)) ok &= good out('index 6, generic: c_1..c_%d =' % NM, formula) out(' words in Gamma = kagome walks = honeycomb/W_3 formula:', good) out(' honeycomb returns W_3(2j), j = 0..8:', [W(3, j) for j in range(9)]) words = word_counts_two_rows(4, 7); formula = [c_generic_two_rows(4, n) for n in range(1, 8)] dia = lattice_returns(diamond, (0, 0, 0, 0), 14) domb = [sum(comb(j, k)**2*comb(2*k, k)*comb(2*(j-k), j-k) for k in range(j+1)) for j in range(8)] good = (words == formula) and all(dia[2*j-1] == W(4, j) == domb[j] for j in range(1, 8)); ok &= good out('index 8, generic: c_1..c_7 =', formula) out(' words in Gamma = diamond lattice/Domb formula:', good) out(' diamond returns W_4(2j), j = 0..7:', domb) return ok # ------------------------------------------------------------------ 2. Eisenstein ideals def hnf(v1, v2): a, b = v1; c, d = v2 while c != 0: q = a//c; a, b, c, d = c, d, a - q*c, b - q*d if a < 0: a, b = -a, -b if d < 0: d = -d return (a, b % d if d else b, d) def ideal(k, h): """the ideal generated by k + h*zeta, as a lattice in the coordinates (k, h); zeta*(k,h) = (-h, k+h)""" return hnf((k, h), (-h, k + h)) def phase_group(al, be, L): """K_Q for alpha = e(al/L), beta = e(be/L): generated by (beta alpha^-2, (alpha beta)^-1), ((alpha beta)^-1, alpha beta^-2)""" g1 = ((be - 2*al) % L, (-al - be) % L); g2 = ((-al - be) % L, (al - 2*be) % L) K = {(0, 0)}; todo = [(0, 0)] while todo: x = todo.pop() for g in (g1, g2): y = ((x[0] + g[0]) % L, (x[1] + g[1]) % L) if y not in K: K.add(y); todo.append(y) return K def annihilator(K, L): """lattice of the (k, h) with Z_2^k Z_1^h = 1 on K, that is, of the elements k t_11 + h t_12 of N_Q""" vecs = [(k, h) for k in range(L) for h in range(L) if all((h*z1 + k*z2) % L == 0 for z1, z2 in K)] lat = None; basis = [(L, 0), (0, L)] + vecs cur = hnf(basis[0], basis[1]) for v in basis[2:]: a, b, d = cur # lattice spanned by (a,b), (0,d), v : reduce by repeated hnf r1 = hnf((a, b), v); a1, b1, d1 = r1 cur = (a1, b1 % gcd(d1, d) if gcd(d1, d) else b1, gcd(d1, d)) return cur def law_of_ideal(k, h): """multiset of the numbers |1 + Z_1 + Z_2|^2 over the dual of Z[omega]/(k + h zeta)""" a, b, d = ideal(k, h); n = a*d # lattice basis (a, b), (0, d) in coordinates (k, h) vals = [] # characters: (s, t) with chi(k,h) = e(s k + t h), trivial on the lattice: a s + b t in Z, d t in Z for j in range(d): t = Fr(j, d) for i in range(a): s = (Fr(i) - b*t)/a z2, z1 = 2*pi*float(s), 2*pi*float(t) # Z_2 = chi(t_11), Z_1 = chi(t_12) vals.append(round(3 + 2*cos(z1) + 2*cos(z2) + 2*cos(z1 - z2), 8)) assert len(vals) == n return tuple(sorted(vals)) def part2(): ok = True # (a) the recipe of Theorem 5.10 count = 0 for k in range(-8, 9): for h in range(-8, 9): n = k*k + k*h + h*h if not 0 < n <= 60: continue L = 3*n; al = (-(h + 2*k)) % L; be = (h - k) % L # alpha = p^2, beta = q^2 K = phase_group(al, be, L) good = (len(K) == n) and (annihilator(K, L) == ideal(k, h)); ok &= good; count += 1 if not good: out(' FAILURE at', (k, h)) out('Theorem 5.10, recipe: %d elements k + h*zeta of norm <= 60 tested:' % count, ok) # (b) all root-of-unity rows give ideals seen = set(); stable = True for L in range(1, 37): for a in range(L): for b in range(L): K = phase_group(2*a % L, 2*b % L, L) k0, b0, d0 = annihilator(K, L) for v in ((k0, b0), (0, d0)): w = (-v[1], v[0] + v[1]) # multiplication by zeta # w must belong to the lattice (k0, b0), (0, d0) stable &= (w[0] % k0 == 0) and ((w[1] - (w[0]//k0)*b0) % d0 == 0) seen.add(len(K)) ok &= stable loeschian = sorted({k*k + k*h + h*h for k in range(8) for h in range(8)} - {0}) out('all rows (1, p, q) with p, q roots of unity of order <= 36 give ideals:', stable) out(' orders of K_Q found, up to 40:', sorted(x for x in seen if x <= 40)) out(' norms of Eisenstein integers, up to 40:', [x for x in loeschian if x <= 40]) ok &= set(x for x in seen if x <= 40) <= set(loeschian) # (c) the law separates ideals up to conjugation ideals = {} R = 24 for k in range(-R, R+1): for h in range(-R, R+1): n = k*k + k*h + h*h if 0 < n <= 400: ideals.setdefault(ideal(k, h), (k, h)) bynorm = defaultdict(list) for I, (k, h) in ideals.items(): bynorm[k*k + k*h + h*h].append((I, (k, h))) bad = 0; classes = 0 for n, lst in bynorm.items(): laws = defaultdict(set) for I, (k, h) in lst: laws[law_of_ideal(k, h)].add(I) for lw, grp in laws.items(): classes += 1 I0 = next(iter(grp)); k, h = ideals[I0] conj = ideal(h, k) # conjugation exchanges k and h, up to a unit if not grp <= {I0, conj}: bad += 1 ok &= (bad == 0) out('%d ideals of norm <= 400, %d different laws, coincidences other than conjugation: %d' % (len(ideals), classes, bad)) # (d) the examples of the paper for name, al, be, L in (('K_33 p=1, q=e(1/3)', 0, 2, 3), ('cube p=1, q=i', 0, 2, 4), ('Fano p=e(1/7), q=e(3/7)', 2, 6, 7), ('Nauru p=1, q=e(1/12)', 0, 2, 12)): K = phase_group(al, be, L); a, b, d = annihilator(K, L) out(' %-28s |K_Q| = %2d, annihilator lattice (%d,%d),(0,%d)' % (name, len(K), a, b, d)) return ok # ------------------------------------------------------------------ 3. coset graphs def part3(): try: import networkx as nx except Exception: out('networkx missing: identification of the coset graphs skipped'); return True def torus(k, h): a, b, d = ideal(k, h) def red(u): x, y = u; q = x//a; return (x - q*a, (y - q*b) % d) G = nx.Graph() for x in range(a): for y in range(d): for t in ((0, 0), (1, 0), (0, 1)): # left vertex u joined to u, u + t_11, u + t_12 G.add_edge(('L', (x, y)), ('R', red((x + t[0], y + t[1])))) return G def gp(n, k): G = nx.Graph() for i in range(n): G.add_edge(('o', i), ('o', (i+1) % n)); G.add_edge(('o', i), ('i', i)); G.add_edge(('i', i), ('i', (i+k) % n)) return G named = {(1, 1): ('K_33', nx.complete_bipartite_graph(3, 3)), (2, 0): ('cube', nx.hypercube_graph(3)), (2, 1): ('Heawood', nx.heawood_graph()), (3, 0): ('Pappus', nx.pappus_graph()), (2, 2): ('Nauru = GP(12,5)', gp(12, 5))} ok = True for (b, c), (name, H) in named.items(): G = torus(b, c); good = nx.is_isomorphic(G, H); ok &= good out(' {6,3}_(%d,%d): %2d vertices, girth %d, isomorphic to %s: %s' % (b, c, G.number_of_nodes(), nx.girth(G), name, good)) for (b, c) in ((3, 1), (4, 0), (3, 2), (4, 1)): G = torus(b, c) out(' {6,3}_(%d,%d): %2d vertices, girth %d, cubic: %s' % (b, c, G.number_of_nodes(), nx.girth(G), all(dg == 3 for _, dg in G.degree()))) return ok # ------------------------------------------------------------------ 4. density def part4(): try: from scipy.special import ellipkm1, hyp2f1 from scipy.integrate import quad except Exception: out('scipy missing: density checks skipped'); return True def p_hyp(r): return 2*sqrt(3)*r/(pi*(3 + r*r))*hyp2f1(1/3, 2/3, 1, r*r*(9 - r*r)**2/(3 + r*r)**3) def p_ell(r): # K(k) with k^2 = 16r/((1+r)^3(3-r)) for r < 1, and k^2 = (1+r)^3(3-r)/(16r) for r > 1; # ellipkm1 takes 1 - k^2, which is known in closed form: (1-r)^3(3+r) over the larger of the 2 numbers if r < 1: hi = (1 + r)**3*(3 - r); return 4*r/(pi*pi*sqrt(hi))*ellipkm1((1 - r)**3*(3 + r)/hi) return sqrt(r)/(pi*pi)*ellipkm1((r - 1)**3*(r + 3)/(16*r)) ok = True for name, p in (('hypergeometric', p_hyp), ('elliptic', p_ell)): mom = [] for j in range(6): v = quad(lambda r: r**(2*j)*p(r), 0, 1, limit=400)[0] + quad(lambda r: r**(2*j)*p(r), 1, 3, limit=400)[0] mom.append(v) good = all(abs(mom[j] - W(3, j)) < 1e-6*W(3, j) for j in range(6)); ok &= good out('density p_3, %-14s form: moments of order 0, 2, .., 10 = %s match W_3: %s' % (name, [round(m, 5) for m in mom], good)) pts = [0.3, 0.9, 1.1, 2.0, 2.9] good = all(abs(p_hyp(r) - p_ell(r)) < 1e-9 for r in pts); ok &= good out(' the 2 forms agree at r = %s: %s; p_3(3) = %.8f, sqrt(3)/(2 pi) = %.8f' % (pts, good, p_ell(3 - 1e-12), sqrt(3)/(2*pi))) # moments of mu_H = (2/3) delta_0 + (1/6) p_3(|x-3|) dx cs = [] for n in range(1, 7): v = sum(quad(lambda x: x**n*p_ell(abs(x - 3))/6, lo, hi, limit=400)[0] for lo, hi in ((0, 2), (2, 3), (3, 4), (4, 6))) cs.append(v) good = all(abs(cs[n-1] - c_generic_two_rows(3, n)) < 1e-6*cs[n-1] for n in range(1, 7)); ok &= good out(' moments of (2/3) delta_0 + (1/6) p_3(|x-3|) dx:', [round(v, 4) for v in cs], 'match c_n:', good) return ok # ------------------------------------------------------------------ 5. p3, Karlsson limits def moments_exact(al, be, L, nmax): """exact c_n for alpha = e(al/L), beta = e(be/L), from mu_H = (2/3) delta_0 + (1/3) law(3 + eps|S|), S = 1 + Z_1 + Z_2 on K_Q: c_n = (1/3) sum_j binom(n,2j) 3^(n-2j) E|S|^(2j), where E|S|^(2j) is the number of pairs of monomials of S^j whose quotient is a character trivial on K_Q.""" K = phase_group(al, be, L) triv = {(u, v) for u in range(L) for v in range(L) if all((u*z1 + v*z2) % L == 0 for z1, z2 in K)} ES = [] for j in range(nmax//2 + 1): mono = [(u, v, comb(j, u)*comb(j - u, v)) for u in range(j + 1) for v in range(j + 1 - u)] ES.append(sum(m1*m2 for (u1, v1, m1) in mono for (u2, v2, m2) in mono if ((u1 - u2) % L, (v1 - v2) % L) in triv)) cs = [] for n in range(1, nmax + 1): tot = sum(comb(n, 2*j)*3**(n - 2*j)*ES[j] for j in range(n//2 + 1)) assert tot % 3 == 0 cs.append(tot//3) return len(K), cs def annular(cs): """the multiplicities a_k of formula (1.1): c_n = Catalan_n + sum_k binom(2n, n-k) a_k""" a = [] for n in range(1, len(cs) + 1): a.append(cs[n-1] - comb(2*n, n)//(n + 1) - sum(comb(2*n, n - k)*a[k-1] for k in range(1, n))) return a def part5(): ok = True out('5. The group p3 and the finite limits of the Karlsson matrices') # (a) the relations of p3, in the model of word_counts_two_rows with N = 3 N = 3 def mul(g, h): (t, c), (t2, c2) = g, h s2 = tuple(t2[(k + c) % N] for k in range(N)) return (tuple(x + y for x, y in zip(t, s2)), (c + c2) % N) one = ((0, 0, 0), 0) a = ((0, 0, 0), 1); b = ((1, 0, -1), 1) # 1^(0) and 1^(1) = (1 - y^(-1), 1) def power(g, n): r = one for _ in range(n): r = mul(r, g) return r ab = mul(a, b) rel = power(a, 3) == one and power(b, 3) == one and power(ab, 3) == one free = mul(a, b) != mul(b, a) and power(mul(a, power(b, 2)), 3) != one out(' a^3 = b^3 = (ab)^3 = 1:', rel, ' ab != ba, and a b^-1 has infinite order (a translation):', free) ok &= rel and free # (b) the 3 limits gen = [c_generic_two_rows(3, n) for n in range(1, 9)] data = [('order 24, cube', 2, 4, [1, 4, 18, 88, 456, 2464, 13728], [1, 10, 29, 114, 419], lambda n: (3*2**n + 3*4**n + 6**n)//24), ('c_4 = 90, K_33', 0, 8, [1, 4, 18, 90], [1, 12, 39, 152, 559], lambda n: (4*3**n + 6**n)//18), ('order 72, Nauru', 2, 8, gen[:7], None, None)] for name, al, be, first, ann, closed in data: size, cs = moments_exact(al, be, 12, 8) a_k = annular(cs) good = cs[:len(first)] == first if closed: good &= all(cs[n-1] == closed(n) for n in range(1, 9)) if ann: good &= a_k[2:7] == ann out(' %-16s alpha = e(%d/12), beta = e(%d/12): |K_Q| = %2d, |G_H| = %2d' % (name, al, be, size, 6*size)) out(' c_n =', cs) out(' a_k =', a_k, ' as expected:', good) ok &= good size, cs = moments_exact(2, 8, 12, 8) same = annihilator(phase_group(2, 8, 12), 12) == annihilator(phase_group(0, 2, 12), 12) == ideal(2, 2) late = cs[:7] == gen[:7] and cs[7] == 58986 and gen[7] == 58974 and size == 12 out(' the limit of order 72 has the ideal (2 + 2 zeta) of Example 5.14:', same, ' generic moments up to n = 7, then c_8 = 58986 against 58974:', late) ok &= same and late return ok def main(): ok = part1(); out('-'*90) ok &= part2(); out('-'*90) ok &= part3(); out('-'*90) ok &= part4(); out('-'*90) ok &= part5() out('ALL CHECKS PASSED' if ok else 'SOME CHECK FAILED') return 0 if ok else 1 if __name__ == '__main__': sys.exit(main())