# -*- coding: utf-8 -*- # ============================================================================= # VERIF_MOD9.py # Author: David Niedbala Giraudin (ORCID 0009-0009-1526-1178) # Technical assistance: Claude (Anthropic) # Ancillary file to: "Hecke eigenvalues in level 1 modulo powers of 2 and 3: # Hatada's question (1981) and the Coleman-Stein conjecture", Section 3 # (Theorems G and H) and Section "Verification". # ----------------------------------------------------------------------------- # Conjecture 9.1 of N. Rustom (Res. Number Theory 5, 2019, Paper 10): # for every eigenform f of level 1 and weight k, # a_2(f) == 3 or 6 (mod 9) if k == 0, 2 (mod 6); a_2(f) == 0 (mod 9) if k == 4 (mod 6), # congruences in the ring of integers of the algebraic closure of Q_3. # # RUN WITH PLAIN PYTHON 3. No library (no numpy, no scipy, no sympy). # No input needed. Clean stop before the time budget is exhausted. # With the values of KMAX and BUDGET below: weights 12 to 400, about 3 minutes. # Larger ranges: raise KMAX and BUDGET (the cost grows quickly with the weight). # # Also checks a_3(f) == 0 (mod 9): together with Conjecture 9.1, Theorem 7.2 and # Proposition 9.3 of Rustom, every eigenform of weight k is then congruent mod 9 # to one of the five forms of the Coleman-Stein table (weights 12, 16, 20, 24, 32). # # Certificate, for each weight k (d = dim S_k): # P = characteristic polynomial of T_2 on S_k (exact, integers), reduced mod 3**(2d+2); # k == 4 (mod 6): the Newton polygon of P at 3 has its d slopes >= 2; # k == 0, 2 (mod 6): (number of slopes >= 2 of P(x+3)) + (number of slopes >= 2 of P(x+6)) = d; # Q = characteristic polynomial of T_3 on S_k: its d slopes at 3 are >= 2. # ============================================================================= import sys import time KMAX = int(400) # target maximal weight BUDGET = float(480.0) # seconds: clean stop beyond def dire(*a): print(*a, flush=True) # ---------------------------------------------------------------- series --- def serie_delta_sur_q(N): """prod_{n>=1} (1-q**n)**24 up to q**N : n f_n = -24 sum sigma_1(j) f_{n-j}.""" s1 = [0] * (N + 1) for d in range(1, N + 1): for m in range(d, N + 1, d): s1[m] += d f = [0] * (N + 1) f[0] = 1 for n in range(1, N + 1): acc = 0 for j in range(1, n + 1): acc += s1[j] * f[n - j] acc = -24 * acc f[n] = acc // n return f def serie_eisenstein(N, c, e): s = [0] * (N + 1) for d in range(1, N + 1): de = d ** e for m in range(d, N + 1, d): s[m] += de return [1] + [c * s[n] for n in range(1, N + 1)] def mul(A, B, N): R = [0] * (N + 1) for i, a in enumerate(A): if a == 0 or i > N: continue for j in range(0, N + 1 - i): if B[j]: R[i + j] += a * B[j] return R def puissance(A, e, N): R = [1] + [0] * N for _ in range(e): R = mul(R, A, N) return R # ---------------------------------------------------- matrix of T_2 on S_k --- def matrice_Tp(k, p): d = k // 12 - (1 if k % 12 == 2 else 0) N = p * d + 2 F = serie_delta_sur_q(N) Delta = [0] + F[:N] # q * prod(1-q**n)**24 E4 = serie_eisenstein(N, 240, 3) E6 = serie_eisenstein(N, -504, 5) base = [] for i in range(1, d + 1): r = k - 12 * i b = 0 if r % 4 == 0 else 1 a = (r - 6 * b) // 4 f = mul(mul(puissance(Delta, i, N), puissance(E4, a, N), N), puissance(E6, b, N), N) base.append(f) # C[i][j] = coefficient of q**(i+1) in f_j (lower triangular, diagonal 1) C = [[base[j][i + 1] for j in range(d)] for i in range(d)] # D[i][j] = coefficient of q**(i+1) in T_p f_j = a_j(p(i+1)) + p**(k-1) a_j((i+1)/p) D = [[base[j][p * (i + 1)] + ((p ** (k - 1)) * base[j][(i + 1) // p] if (i + 1) % p == 0 else 0) for j in range(d)] for i in range(d)] # C M = D by back-substitution (exact, C unitriangular) M = [[0] * d for _ in range(d)] for j in range(d): for i in range(d): v = D[i][j] - sum(C[i][t] * M[t][j] for t in range(i)) M[i][j] = v # C[i][i] = 1 return d, M def polycar(A): """Exact Faddeev-Le Verrier: c[0..n], det(xI - A) = sum c[i] x**i.""" n = len(A) c = [0] * (n + 1) c[n] = 1 Mk = [[0] * n for _ in range(n)] for k in range(1, n + 1): AM = [[sum(A[i][t] * Mk[t][j] for t in range(n)) for j in range(n)] for i in range(n)] for i in range(n): AM[i][i] += c[n - k + 1] Mk = AM tr = sum(sum(A[i][t] * Mk[t][i] for t in range(n)) for i in range(n)) if tr % k != 0: raise ValueError("non-exact division in Le Verrier") c[n - k] = -(tr // k) return c # -------------------------------------------------------- Newton polygon --- def v3(x, M3): x = x % M3 if x == 0: return None v = 0 while x % 3 == 0: x //= 3 v += 1 return v def nb_pentes_ge2(co, M3): """co[i] = coefficient of x**i (monic). Number of roots of valuation >= 2.""" d = len(co) - 1 pts = [] for i in range(d + 1): v = v3(co[i], M3) if v is not None: pts.append((i, v)) pts.sort() h = [] for p in pts: while len(h) >= 2: (ox, oy), (ax, ay) = h[-2], h[-1] if (ax - ox) * (p[1] - oy) - (ay - oy) * (p[0] - ox) <= 0: h.pop() else: break h.append(p) n = h[0][0] # roots of valuation >= M/... (>= 2 guaranteed) for (x1, y1), (x2, y2) in zip(h, h[1:]): if (y1 - y2) >= 2 * (x2 - x1): # slope (valuation) >= 2 n += x2 - x1 return n def translate(co, a): """coefficients of P(x + a).""" d = len(co) - 1 out = [0] * (d + 1) for i in range(d + 1): if co[i] == 0: continue # (x+a)**i = sum_j C(i,j) a**(i-j) x**j binom = 1 for j in range(0, i + 1): out[j] += co[i] * binom * (a ** (i - j)) binom = binom * (i - j) // (j + 1) return out def verdict_poids(k): d, M = matrice_Tp(k, 2) co = polycar(M) M3 = 3 ** (2 * d + 2) co = [c % M3 for c in co] if k % 6 == 4: ok2 = nb_pentes_ge2(co, M3) == d else: n3 = nb_pentes_ge2([c % M3 for c in translate(co, 3)], M3) n6 = nb_pentes_ge2([c % M3 for c in translate(co, 6)], M3) ok2 = (n3 + n6) == d d3, M3m = matrice_Tp(k, 3) q3 = [c % M3 for c in polycar(M3m)] ok3 = nb_pentes_ge2(q3, M3) == d return d, ok2, ok3 # ------------------------------------------------------------- self-test --- def auto_test(): connus = {12: (-24, 252), 16: (216, -3348), 18: (-528, -4284), 20: (456, 50652), 22: (-288, -128844), 26: (-48, -195804)} for k, (a2, a3) in connus.items(): if polycar(matrice_Tp(k, 2)[1]) != [-a2, 1]: return False if polycar(matrice_Tp(k, 3)[1]) != [-a3, 1]: return False if polycar(matrice_Tp(24, 2)[1]) != [-20468736, -1080, 1]: return False if polycar(matrice_Tp(36, 2)[1]) != [-1467625047588864, -59208339456, -139656, 1]: return False if polycar(matrice_Tp(36, 3)[1]) != [-21175292105104984004394432, -144593891972573904, 104875308, 1]: return False M3 = 3 ** 10 piege = [-18, -6, 1] # (x-3)**2 - 27 : must be REJECTED if nb_pentes_ge2([c % M3 for c in translate(piege, 3)], M3) + \ nb_pentes_ge2([c % M3 for c in translate(piege, 6)], M3) == 2: return False temoin = [252, -33, 1] # (x-12)(x-21) : must be ACCEPTED if nb_pentes_ge2([c % M3 for c in translate(temoin, 3)], M3) + \ nb_pentes_ge2([c % M3 for c in translate(temoin, 6)], M3) != 2: return False return True dire("VERIF_MOD9 : Rustom's Conjecture 9.1 and a_3 mod 9, weights 12 to %d, budget %.0f s" % (KMAX, BUDGET)) t0 = time.time() if not auto_test(): dire("SELF-TEST FAILED: stop (results not reliable).") sys.exit(1) dire("Self-test OK (a_2 and a_3 of the 6 forms, weights 24 and 36 for T_2 and T_3, trap rejected, witness accepted).") nok = 0 dernier = None for k in range(12, KMAX + 1, 2): if k == 14: continue if time.time() - t0 > BUDGET: dire("Budget reached: clean stop before weight %d." % k) break d, ok2, ok3 = verdict_poids(k) if not ok2: dire("VIOLATION of Conjecture 9.1 at weight %d (dimension %d)" % (k, d)) sys.exit(2) if not ok3: dire("FAILURE of a_3 == 0 mod 9 at weight %d (dimension %d)" % (k, d)) sys.exit(3) nok += 1 dernier = k if k % 20 == 0: dire(" weights <= %d : %d spaces checked, %.0f s" % (k, nok, time.time() - t0)) dire("") dire("RESULT: weights 12..%s (%d spaces): Conjecture 9.1 and a_3 == 0 mod 9 verified, no exception." % (dernier, nok)) dire("With [Rustom 2019, Thm 7.2 and Prop 9.3], every eigenform of these weights is congruent mod 9") dire("to one of the five forms of the Coleman-Stein table (weights 12, 16, 20, 24, 32).")