#!/usr/bin/env python3 """Exact certificates for the K3 applications in Section 6 and Proposition 7.9. The quartic characteristic polynomials are verified over Z[m], including the level-N identity by polynomial interpolation. Integer matrices and a Rabin certificate over F_13 verify the degree-ten example. """ from fractions import Fraction from functools import reduce import json class Zm: """A deliberately small exact implementation of Z[m].""" def __init__(self, coefficients=0): if isinstance(coefficients, Zm): self.c = coefficients.c return if isinstance(coefficients, int): coefficients = (coefficients,) a = list(coefficients) while len(a) > 1 and a[-1] == 0: a.pop() self.c = tuple(a or [0]) def __add__(self, other): b = Zm(other).c return Zm([(self.c[i] if i < len(self.c) else 0) + (b[i] if i < len(b) else 0) for i in range(max(len(self.c), len(b)))]) __radd__ = __add__ def __neg__(self): return Zm([-x for x in self.c]) def __sub__(self, other): return self + (-Zm(other)) def __rsub__(self, other): return Zm(other) + (-self) def __mul__(self, other): b = Zm(other).c a = [0] * (len(self.c) + len(b) - 1) for i, x in enumerate(self.c): for j, y in enumerate(b): a[i + j] += x * y return Zm(a) __rmul__ = __mul__ def __pow__(self, exponent): assert exponent >= 0 result, base = Zm(1), self while exponent: if exponent & 1: result *= base base *= base exponent >>= 1 return result def __eq__(self, other): return self.c == Zm(other).c def exact_div(self, divisor): assert all(x % divisor == 0 for x in self.c) return Zm([x // divisor for x in self.c]) def __repr__(self): return str(list(self.c)) def exact_div(x, n): if isinstance(x, Zm): return x.exact_div(n) assert x % n == 0 return x // n def eye(n): return [[int(i == j) for j in range(n)] for i in range(n)] def transpose(a): return [list(row) for row in zip(*a)] def mm(a, b): bt = transpose(b) return [[sum(x * y for x, y in zip(row, col)) for col in bt] for row in a] def mv(a, v): return [sum(x * y for x, y in zip(row, v)) for row in a] def dot(g, a, b): return sum(x * y for x, y in zip(a, mv(g, b))) def eichler(g, f, z): assert dot(g, f, f) == 0 and dot(g, f, z) == 0 h = exact_div(dot(g, z, z), 2) gf, gz = mv(g, f), mv(g, z) n = len(g) return [[int(i == j) + z[i] * gf[j] - f[i] * gz[j] - h * f[i] * gf[j] for j in range(n)] for i in range(n)] def characteristic_polynomial(a): """Faddeev--LeVerrier; output is [1,c1,...,cn].""" n = len(a) b, coefficients = eye(n), [1] for k in range(1, n + 1): b = mm(a, b) c = exact_div(-sum(b[i][i] for i in range(n)), k) coefficients.append(c) for i in range(n): b[i][i] += c assert all(x == 0 for row in b for x in row) return coefficients def inverse(a): n = len(a) b = [[Fraction(x) for x in row] + [Fraction(int(i == j)) for j in range(n)] for i, row in enumerate(a)] for k in range(n): pivot = next(i for i in range(k, n) if b[i][k]) b[k], b[pivot] = b[pivot], b[k] t = b[k][k] b[k] = [x / t for x in b[k]] for i in range(n): if i != k: t = b[i][k] b[i] = [x - t * y for x, y in zip(b[i], b[k])] return [row[n:] for row in b] def determinant(a): b = [[Fraction(x) for x in row] for row in a] n, d = len(a), Fraction(1) for k in range(n): pivot = next(i for i in range(k, n) if b[i][k]) if pivot != k: b[k], b[pivot] = b[pivot], b[k] d = -d t = b[k][k] d *= t for i in range(k + 1, n): s = b[i][k] / t b[i] = [x - s * y for x, y in zip(b[i], b[k])] return d # F_p[X], with coefficient lists in ascending degree order. def trim(a, p): a = [x % p for x in a] while len(a) > 1 and a[-1] == 0: a.pop() return a or [0] def padd(a, b, p): return trim([(a[i] if i < len(a) else 0) + (b[i] if i < len(b) else 0) for i in range(max(len(a), len(b)))], p) def pneg(a, p): return trim([-x for x in a], p) def pmul(a, b, p): c = [0] * (len(a) + len(b) - 1) for i, x in enumerate(a): for j, y in enumerate(b): c[i + j] += x * y return trim(c, p) def pdivmod(a, b, p): a, b = trim(a, p), trim(b, p) assert b != [0] q = [0] * max(1, len(a) - len(b) + 1) inv_leading = pow(b[-1], -1, p) while a != [0] and len(a) >= len(b): k, c = len(a) - len(b), a[-1] * inv_leading % p q[k] = c for j, y in enumerate(b): a[k + j] = (a[k + j] - c * y) % p a = trim(a, p) return trim(q, p), a def pmodpow(a, exponent, modulus, p): result = [1] while exponent: if exponent & 1: result = pdivmod(pmul(result, a, p), modulus, p)[1] a = pdivmod(pmul(a, a, p), modulus, p)[1] exponent >>= 1 return result def pxgcd(a, b, p): old_r, r = a, b old_s, s, old_t, t = [1], [0], [0], [1] while r != [0]: q, remainder = pdivmod(old_r, r, p) old_r, r = r, remainder old_s, s = s, padd(old_s, pneg(pmul(q, s, p), p), p) old_t, t = t, padd(old_t, pneg(pmul(q, t, p), p), p) inverse_leading = pow(old_r[-1], -1, p) scale = lambda v: trim([inverse_leading * x for x in v], p) return scale(old_r), scale(old_s), scale(old_t) def verify_quartic(): m = Zm([0, 1]) g = [[0, 1, 0, 0], [1, 0, 0, 0], [0, 0, -4*m, 0], [0, 0, 0, -4*m]] e, f = [1, 0, 0, 0], [m, 2, 1, 0] u, v = [2*m, 0, 1, 0], [0, 0, 0, 1] t, s = eichler(g, e, u), eichler(g, f, v) t_displayed = [[1, 2*m, 4*m, 0], [0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1]] s_displayed = [[4*m**2+1, 2*m**3, -8*m**3, 4*m**2], [8*m, 4*m**2+1, -16*m**2, 8*m], [4*m, 2*m**2, 1-8*m**2, 4*m], [2, m, -4*m, 1]] assert t == t_displayed and s == s_displayed assert mm(mm(transpose(t), g), t) == g assert mm(mm(transpose(s), g), s) == g expected = [1, -(16*m**2+4), 6-32*m**2, -(16*m**2+4), 1] assert characteristic_polynomial(mm(t, s)) == expected # Each powered Eichler matrix is quadratic in the level. The entries of # their product have degree at most 4, so its characteristic coefficients # have degree at most 16. Equality at 17 levels proves the identity in Z[m,N]. for level in range(17): t_level = eichler(g, e, [level * entry for entry in u]) s_level = eichler(g, f, [level * entry for entry in v]) term = 16 * m**2 * level**4 expected_level = [1, -(term + 4), 6 - 2 * term, -(term + 4), 1] assert characteristic_polynomial(mm(t_level, s_level)) == expected_level print("PASS: quartic family matrices are the stated Eichler maps in Z[m].") print("PASS: both isometry identities and the characteristic polynomial hold in Z[m].") print("PASS: levels 0 through 16 and the degree bound verify P_{m N^2}(X) in Z[m,N].") print("Quartic characteristic coefficients [descending X; ascending m internally]:") print([list(Zm(c).c) for c in expected]) def verify_degree_ten(): n = 10 diag = [2, -4] + [-2] * 8 g = [[diag[i] if i == j else 0 for j in range(n)] for i in range(n)] z = [0, 1] + [0] * 8 word = [(0, 1), (0, -1)] + [(i, 1) for i in range(1, 8)] product = eye(n) for i, sign in word: f = [2, 0] + [2*sign if j == i else 0 for j in range(8)] t = eichler(g, f, z) indices = [0, 1, i+2] block = [[t[a][b] for b in indices] for a in indices] assert block == [[17, 8, -16*sign], [4, 1, -4*sign], [16*sign, 8*sign, -15]] assert mm(mm(transpose(t), g), t) == g assert determinant(t) == 1 product = mm(product, t) assert mm(mm(transpose(product), g), product) == g coefficients = characteristic_polynomial(product) expected = [1, -531713972298, 1239885808173, -2475101071224, 3369426357970, -3754750059132, 3369426357970, -2475101071224, 1239885808173, -531713972298, 1] assert coefficients == expected assert sum(product[i][i] for i in range(n)) == 531713972298 # Actual lattice basis: <2> + <-4> + D_8(-2), not Z^10. basis = [[0] * n for _ in range(n)] basis[0][0] = basis[1][1] = 1 for j in range(7): basis[j+2][j+2] = 1 basis[j+3][j+2] = -1 basis[8][9] = basis[9][9] = 1 assert abs(determinant(basis)) == 2 lattice_g = mm(mm(transpose(basis), g), basis) lattice_product = mm(mm(inverse(basis), product), basis) assert all(x.denominator == 1 for row in lattice_product for x in row) assert mm(mm(transpose(lattice_product), lattice_g), lattice_product) == lattice_g difference = [[lattice_product[i][j] - int(i == j) for j in range(n)] for i in range(n)] discriminant_test = mm(difference, inverse(lattice_g)) assert all(x.denominator == 1 for row in discriminant_test for x in row) assert determinant(lattice_g) == -8192 p = 13 modulus = trim(list(reversed(coefficients)), p) expected_mod = trim([1, -2, -1, -2, -3, 6, -3, -2, -1, -2, 1], p) assert modulus == expected_mod x, current = [0, 1], [0, 1] remainders, bezout = {}, {} for j in range(1, 11): current = pmodpow(current, p, modulus, p) remainders[j] = current assert remainders[10] == x for j in [2, 5]: residue = padd(remainders[j], pneg(x, p), p) gcd, a, b = pxgcd(modulus, residue, p) assert gcd == [1] assert padd(pmul(a, modulus, p), pmul(b, residue, p), p) == [1] bezout[j] = {"a": a, "b": b} print("PASS: degree-ten word has determinant 1 and preserves the Lorentz form.") print("PASS: it preserves the actual D8 lattice and is trivial on its discriminant group.") print("PASS: determinant of the actual lattice is -8192.") print("PASS: the degree-ten characteristic polynomial has the stated coefficients.") print("PASS: modulo 13, X^(13^10)=X and gcd(P,X^(13^j)-X)=1 for j=2,5.") print("PASS: Rabin's criterion proves irreducibility over F13, hence over Q.") print("Degree-ten coefficients, descending X:") print(coefficients) print("Finite-field certificate (all coefficient lists are ascending degree):") print(json.dumps({"prime": p, "modulus": modulus, "frobenius_remainders": remainders, "bezout": bezout}, indent=2)) if __name__ == "__main__": verify_quartic() verify_degree_ten()