"""Exact checks for Spectral measure blowup for Hadamard subfactors. Compare return-word counts, the finite quotient lattice and Gram traces for seven finite phase matrices and their transposes. Also check the index-six atomic laws, the index-nine moments and the first exceptional cyclic moment. Run: python3 wordgram.py Requires SymPy. All arithmetic is integral or rational. """ from collections import Counter from fractions import Fraction from functools import lru_cache from itertools import product from math import comb, factorial, gcd, prod from sympy import Matrix, ZZ from sympy.matrices.normalforms import smith_normal_form def subtraction_table(shape): """Return the subtraction table of a product of cyclic groups. Elements use lexicographic order, with the identity at index zero. """ elements = list(product(*(range(order) for order in shape))) indices = {element: index for index, element in enumerate(elements)} return [ [ indices[tuple((a - b) % order for a, b, order in zip(left, right, shape))] for right in elements ] for left in elements ] def compare_word_and_gram_counts(x_shape, y_shape, modulus, phases, depth): """Use Q[i,b] = exp(2*pi*i*phases[i][b]/modulus). Block phases are reduced modulo constants on each block E_k. Thus the identity state means that the return word belongs to N_Q. The Gram calculation uses character orthogonality on the group generated by g[k,e]. """ x_subtract = subtraction_table(x_shape) y_subtract = subtraction_table(y_shape) rows, columns = len(x_subtract), len(y_subtract) positions = list(product(range(rows), range(columns))) zero_phase = (0,) * (rows * columns) def remove_block_constants(values): return tuple( (values[k * columns + e] - values[k * columns]) % modulus for k, e in positions ) @lru_cache(None) def next_states(state): degree, block_phase = state targets = [] for i, b in positions: new_degree = y_subtract[degree][y_subtract[0][b]] new_phase = [] for k, e in positions: shifted_e = y_subtract[e][degree] shifted_b = y_subtract[shifted_e][b] value = ( block_phase[k * columns + e] + phases[i][shifted_b] + phases[x_subtract[i][k]][shifted_e] - phases[i][shifted_e] - phases[x_subtract[i][k]][shifted_b] ) new_phase.append(value % modulus) targets.append((new_degree, remove_block_constants(new_phase))) return targets origin = (0, zero_phase) seen, frontier = {origin}, [origin] while frontier: state = frontier.pop() for target in next_states(state): if target not in seen: seen.add(target) frontier.append(target) paths = Counter({origin: 1}) word_moments = [] for _ in range(depth): following = Counter() for state, count in paths.items(): for target in next_states(state): following[target] += count paths = following assert paths[origin] % rows == 0 word_moments.append(paths[origin] // rows) def ratio_exponent(i, k, e): return ( phases[i][e] + phases[x_subtract[0][k]][e] - phases[x_subtract[i][k]][e] - phases[0][e] ) def generator_coordinate(i, j): return tuple( ( ratio_exponent(i, k, y_subtract[e][y_subtract[0][j]]) + ratio_exponent(i, k, 0) - ratio_exponent(i, k, e) - ratio_exponent(i, k, j) ) % modulus for k, e in positions ) coordinates = [ [generator_coordinate(i, j) for j in range(columns)] for i in range(rows) ] integer_matrix = Matrix([ coordinates[i][j] for i, j in positions if i != 0 and j != 0 ]) smith = smith_normal_form(integer_matrix, domain=ZZ) lattice_index = prod(modulus // gcd(modulus, int(entry)) for entry in smith.diagonal()) assert len(seen) == columns * lattice_index # Each Gram entry is a sum of phase characters Z[i,j]/Z[h,j]. increments = [ [ [ tuple((a - b) % modulus for a, b in zip(coordinates[i][j], coordinates[h][j])) for j in range(columns) ] for h in range(rows) ] for i in range(rows) ] gram_traces = [0] * depth for root in range(rows): paths = {(root, zero_phase): 1} for step_number in range(depth): following = Counter() for (i, character), count in paths.items(): for h in range(rows): for increment in increments[i][h]: target = tuple((a + b) % modulus for a, b in zip(character, increment)) following[h, target] += count gram_traces[step_number] += following[root, zero_phase] paths = following assert gram_traces == [value * rows * columns for value in word_moments] return word_moments, lattice_index def contents(length, alphabet_size): """Nonnegative integer contents of a word of fixed length.""" if alphabet_size == 1: yield (length,) return for first in range(length + 1): for rest in contents(length - first, alphabet_size - 1): yield (first,) + rest def multinomial(content): return factorial(sum(content)) // prod(factorial(value) for value in content) def walk_moment(length, alphabet_size): return sum(multinomial(content) ** 2 for content in contents(length, alphabet_size)) def check_explicit_moments(): atomic_laws = [ ({0: 13, 3: 4, 6: 1}, 18, [1, 4, 18, 90]), ({0: 17, 2: 3, 4: 3, 6: 1}, 24, [1, 4, 18, 88]), ({0: 49, 1: 6, 2: 3, 3: 4, 4: 3, 5: 6, 6: 1}, 72, [1, 4, 18, 86]), ] for weights, denominator, expected in atomic_laws: assert sum(weights.values()) == denominator moments = [ Fraction(sum(weight * atom ** n for atom, weight in weights.items()), denominator) for n in range(1, 9) ] assert all(value.denominator == 1 for value in moments) assert moments[:4] == expected print('Index-six atomic law, denominator', denominator, 'moments', list(map(int, moments))) generic_eighth = Fraction(sum(comb(8, 2*j) * 3 ** (8-2*j) * walk_moment(j, 3) for j in range(5)), 3) assert generic_eighth == 58974 and moments[7] - generic_eighth == 12 ninth_index = [Fraction(walk_moment(n, 3), 3) for n in range(1, 8)] assert ninth_index == [1, 5, 31, 213, 1551, 11723, 90945] print('Index-nine slice moments', list(map(int, ninth_index))) for order in range(1, 5): for length in range(2 * order + 1): generic = 0 grouped = Counter() for content in contents(length, 4): count = multinomial(content) generic += count ** 2 key = (content[1] + content[2], content[2] + content[3], content[2] % order) grouped[key] += count excess = sum(count ** 2 for count in grouped.values()) - generic expected = 2 * comb(2 * order, order) ** 2 if length == 2 * order else 0 assert excess == expected print('First exceptional moment checked for orders 1, 2, 3, 4') def main(): cases = [ ((2,), (2,), 4, [[0, 0], [0, 1]], 5), ((2,), (2,), 8, [[0, 0], [0, 1]], 5), ((2,), (3,), 12, [[0, 0, 0], [0, 0, 1]], 8), ((2,), (3,), 7, [[0, 0, 0], [0, 1, 3]], 5), ((2,), (2, 2), 3, [[0, 0, 0, 0], [0, 1, 2, 2]], 4), ((3,), (3,), 6, [[0, 0, 0], [0, 1, 0], [0, 0, 5]], 5), ((2, 2), (2,), 4, [[0, 0], [0, 1], [0, 2], [0, 3]], 4), ] for x_shape, y_shape, modulus, phases, depth in cases: moments, index = compare_word_and_gram_counts(x_shape, y_shape, modulus, phases, depth) transpose_moments, transpose_index = compare_word_and_gram_counts( y_shape, x_shape, modulus, list(zip(*phases)), depth ) assert moments == transpose_moments and index == transpose_index print(x_shape, y_shape, 'modulus', modulus, 'lattice index', index, 'moments', moments, flush=True) check_explicit_moments() print('All exact word, Gram and moment checks passed.') if __name__ == '__main__': main()