#!/usr/bin/env python3 """Exact finite certificates for exceptional_lattices.tex. Run: python3 verify_rank27.py Only Python's standard library is used. This checks the finite algebraic certificates; the manuscript proves the unbounded coset and cusp assertions. """ from collections import Counter from fractions import Fraction as F from itertools import combinations from pathlib import Path import json def inverse(matrix): n = len(matrix) rows = [[F(x) for x in row] + [F(i == j) for j in range(n)] for i, row in enumerate(matrix)] for col in range(n): pivot = next(i for i in range(col, n) if rows[i][col]) rows[col], rows[pivot] = rows[pivot], rows[col] d = rows[col][col] rows[col] = [x/d for x in rows[col]] for i in range(n): if i == col: continue q = rows[i][col] rows[i] = [a-q*b for a, b in zip(rows[i], rows[col])] return [row[n:] for row in rows] def determinant(matrix): rows = [[F(x) for x in row] for row in matrix] n = len(rows) value = F(1) for col in range(n): pivot = next((i for i in range(col, n) if rows[i][col]), None) if pivot is None: return F(0) if pivot != col: rows[col], rows[pivot] = rows[pivot], rows[col] value = -value d = rows[col][col] value *= d for i in range(col+1, n): q = rows[i][col]/d rows[i] = [a-q*b for a, b in zip(rows[i], rows[col])] return value def cartan(name): typ, n = name[0], int(name[1:]) C = [[2*int(i == j) for j in range(n)] for i in range(n)] if typ == 'A': edges = [(i, i+1) for i in range(n-1)] marks = [1]*n elif typ == 'D': edges = [(i, i+1) for i in range(n-3)] + [(n-3, n-2), (n-3, n-1)] marks = [1]+[2]*(n-3)+[1, 1] elif typ == 'E': edges = [(0, 2), (1, 3)] + [(i, i+1) for i in range(2, n-1)] marks = {6: [1, 2, 2, 3, 2, 1], 7: [2, 2, 3, 4, 3, 2, 1]}[n] else: raise ValueError(name) for i, j in edges: C[i][j] = C[j][i] = -1 return C, marks def check_weights(): data = json.loads(Path(__file__).with_name('weight_certificates.json').read_text()) expected = {f'A{i}' for i in range(1, 9)} | {f'D{i}' for i in range(4, 9)} | {'E6', 'E7'} assert set(data) == expected summary = {} for name, certs in data.items(): C, marks = cartan(name) n = len(C) assert len(certs) == n assert all(determinant([row[:k] for row in C[:k]]) > 0 for k in range(1, n+1)) assert sum(marks[i]*C[i][j]*marks[j] for i in range(n) for j in range(n)) == 2 assert all(sum(C[i][j]*marks[j] for j in range(n)) >= 0 for i in range(n)) ci = inverse(C) for entry in certs: b, c = entry['b'], entry['weight'] assert len(c) == n and all(isinstance(x, int) and x >= 0 for x in c) coordinates = [sum(ci[i][j]*c[j] for j in range(n)) for i in range(n)] assert all(x.denominator == 1 for x in coordinates) assert coordinates == entry['coords'] norm = sum(c[i]*coordinates[i] for i in range(n)) level = sum(c[i]*marks[i] for i in range(n)) assert norm == entry['norm'] and level == entry['level'] assert 0 < level <= b assert norm in {2: {2, 4, 6, 8}, 3: {6, 8, 10, 12}, 4: {12, 14}}[b] if b == 2 and norm == 8: assert any(x.numerator % 2 for x in coordinates) det = determinant([entry['weight'] for entry in certs]) assert det != 0 summary[name] = {'rank': n, 'weight_matrix_determinant': str(det)} print('PASS: all 79 weights; 15 full-rank ADE bases; integrality, norms, levels and divisibility.') return summary def golay_code(): g = sum(1 << i for i in (0, 1, 5, 6, 7, 9, 11)) words = {0} for j in range(12): words |= {w ^ (g << j) for w in tuple(words)} return {w | ((w.bit_count() & 1) << 23) for w in words} CODE = golay_code() def member(v): p = v[0] % 2 if len(v) != 24 or any(x % 2 != p for x in v) or sum(v) % 8 != 4*p: return False word = sum((((x-p)//2) % 2) << i for i, x in enumerate(v)) return word in CODE def dot(v, w): return F(sum(x*y for x, y in zip(v, w)), 8) def padded(values): return tuple(values)+(0,)*(24-len(values)) def check_leech(): distribution = Counter(w.bit_count() for w in CODE) assert distribution == {0: 1, 8: 759, 12: 2576, 16: 759, 24: 1} assert len(CODE) == 4096 octad = {0, 1, 2, 3, 4, 15, 17, 20} assert sum(1 << i for i in octad) in CODE g = sum(1 << i for i in (0, 1, 5, 6, 7, 9, 11)) polynomial_product = 0 for i in (0, 2, 4, 6, 7, 9): polynomial_product ^= g << i assert polynomial_product == sum(1 << i for i in octad) norm_vectors = {4: padded((4, 4)), 8: padded((8,)), 12: padded((8, 4, 4)), 20: padded((12, 4))} outside = sorted(set(range(24))-octad) for k in (1, 3, 7): z = [2*int(i in octad) for i in range(24)] z[min(octad)] = -2 for i in outside[:k]: z[i] = 4 norm_vectors[4+2*k] = tuple(z) for norm, z in norm_vectors.items(): assert member(z) and dot(z, z) == norm v = padded((8, 4, 4, 4, 4)) assert member(v) and dot(v, v) == 16 xs = [] for i in range(1, 5): z = [0]*24 z[0] = z[i] = 4 xs.append(tuple(z)) for signs in ((1, 1, 1), (1, -1, -1), (-1, 1, -1), (-1, -1, 1)): z = [2*int(i <= 4) for i in range(24)] for i, s in zip((15, 17, 20), signs): z[i] = 2*s xs.append(tuple(z)) assert all(member(x) and dot(x, x) == 4 for x in xs) assert all(dot(x, y) == 2 for x, y in combinations(xs, 2)) assert tuple(sum(x[i] for x in xs) for i in range(24)) == tuple(3*z for z in v) shortest = [v]+[tuple(z-3*y for z, y in zip(v, x)) for x in xs] assert all(dot(x, x) == 16 for x in shortest) assert all(dot(x, y) == -2 for x, y in combinations(shortest, 2)) assert all(sum(x[i] for x in shortest) == 0 for i in range(24)) assert determinant([[dot(x, y) for x in shortest[:8]] for y in shortest[:8]]) != 0 print('PASS: Golay code, all required Leech vectors, octad identity, eight-vector configuration.') print('PASS: nine-vector Gram matrix 18 I - 2 J, rank exactly 8.') return {'leech_norms': sorted(norm_vectors), 'special_coset_minimum': 16, 'special_coset_representatives': 9, 'special_coset_span_rank': 8} if __name__ == '__main__': from verify_coordinate_cusps import verify_coordinate_cusps, readable_results weights = check_weights() leech = check_leech() coordinate_cusps = verify_coordinate_cusps() supplied = json.loads(Path(__file__).with_name('coordinate_cusp_certificates.json').read_text()) assert supplied == json.loads(json.dumps(coordinate_cusps)) print(readable_results(coordinate_cusps), end='') print('PASS: supplied coordinate-cusp certificate matches the recomputed identities.') coordinate_summary = {key: value for key, value in coordinate_cusps.items() if key not in {'norm_eight_vectors', 'cusps', 'coordinate_convention'}} result = {'weights': weights, 'leech': leech, 'coordinate_cusps': coordinate_summary} print(json.dumps(result, indent=2)) print('ALL EXACT FINITE CERTIFICATES PASSED.')