# -*- coding: utf-8 -*- # ============================================================================= # VERIF_A2.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 5 (Lemmas 5 to 8, Theorems I and K) and Section "Verification". # ----------------------------------------------------------------------------- # Theorem I: for every even weight k >= 12, on Hatada's lattice L_k, # T_2 o T_2 == 9 (k-1)**2 (mod 27). # Theorem K: on L_k, modulo 81, # T_2 o T_2 == s**2 if k == 0 or 2 (mod 6), s = 1 + 2**(k-1), # T_2 o T_2 + 9 T_2 == 0 if k == 4 (mod 6). # Consequences: for every eigenform f of level 1 and weight k, # a_2(f) == +s or -s (mod 27) if k == 0 or 2 (mod 6), # a_2(f) == 0 (mod 9) if k == 4 (mod 6), # without any ramification hypothesis (Conjecture 9.1 of Rustom). # # RUN WITH PLAIN PYTHON 3. No library (no numpy, no scipy, no sympy). # No input needed: everything is fixed below. Clean stop before the time budget # is exhausted. Running time: under a minute. Memory: a few tens of MB at most. # # Part A: finite certificate of Lemma 6. In the group ring Z/9[PG], # PG = {g in GL_2(Z/9) : det g = +1 or -1} / {+I, -I} (648 elements), # x = T (1 + T' + T'**2) (1 + T + T**2) equals an explicit combination # (290 terms) of elements (1+S)g, (1+U+U**2)g, (1+eps)g and of elements # of the square C**2 of the congruence ideal C = (3, k - 1 : k == +-I mod 3). # Part B: direct check on the lattice L_k, 12 <= k <= KMAX_B: # T_2(L_k) in 3 L_k, Theorem I modulo 27, Theorem K modulo 81; # known eigenvalues in dimension 1. # Part C: identity of Lemma 5, in characteristic 3, on all solutions modulo 3 # of the period relations, 12 <= k <= KMAX_C. # Part D: linear condition of Lemma 6 on L_k reduced modulo 3. # Part E: PROOF of Theorem K (finite exact computation, valid in every weight): # three certificates (Lemma 8) and the vanishing criterion of Lemma 7. # Part G: check of part E by direct action on polynomials of degree w # (w in the right class, and out-of-class witnesses). # ============================================================================= import sys import time from fractions import Fraction from math import comb, gcd KMAX_B = int(100) # Part B: weights up to KMAX_B KMAX_C = int(40) # Parts C and D: weights up to KMAX_C BUDGET = float(480.0) # seconds: clean stop beyond this PARTIE_C = True # switch: False to skip Parts C and D PARTIE_G = True # switch: False to skip Part G (check) W_G_MAX = int(60) # Part G: degrees w <= W_G_MAX T0 = time.time() def dire(*a): print(*a, flush=True) def v3(n): n = abs(int(n)) if n == 0: return 10 ** 9 v = 0 while n % 3 == 0: n //= 3 v += 1 return v # ============================================================================= # Part A: the group ring Z/9[PG] # ============================================================================= M9 = int(9) def canon(g): a, b, c, d = [int(t) % M9 for t in g] h = tuple((-t) % M9 for t in (a, b, c, d)) return min((a, b, c, d), h) def mul(g, h): a, b, c, d = g e, f, p, q = h return canon((a * e + b * p, a * f + b * q, c * e + d * p, c * f + d * q)) def det9(g): return (g[0] * g[3] - g[1] * g[2]) % M9 I_ = canon((1, 0, 0, 1)) S_ = canon((0, -1, 1, 0)) U_ = canon((1, -1, 1, 0)) U2_ = mul(U_, U_) E_ = canon((-1, 0, 0, 1)) T_ = canon((1, 1, 0, 1)) TP_ = canon((1, 0, 1, 1)) K1 = canon((1, 3, 0, 1)) K2 = canon((1, 0, 3, 1)) K3 = canon((4, 0, 0, 7)) KS = {1: K1, 2: K2, 3: K3} PAIRES = {'d': (1, 1), 'e': (1, 2), 'f': (1, 3), 'g': (2, 2), 'h': (2, 3), 'i': (3, 3)} def ajoute(acc, g, c): acc[g] = (acc.get(g, 0) + c) % M9 def generateur(code, g): """element of the ideal I + C**2 designated by the code, multiplied on the right by g""" out = {} if code == 'S': for h in (I_, S_): ajoute(out, mul(h, g), 1) elif code == 'U': for h in (I_, U_, U2_): ajoute(out, mul(h, g), 1) elif code == 'E': for h in (I_, E_): ajoute(out, mul(h, g), 1) elif code in 'abc': k = KS['abc'.index(code) + 1] ajoute(out, mul(k, g), 3) ajoute(out, g, -3) else: i, j = PAIRES[code] ki, kj = KS[i], KS[j] ajoute(out, mul(mul(ki, kj), g), 1) ajoute(out, mul(ki, g), -1) ajoute(out, mul(kj, g), -1) ajoute(out, g, 1) return out CERTIFICAT = ( "S01103 U01106 S01113 E01116 S01816 U01818 S01826 U01826 S01834 S01871 " "U01875 S01887 U01882 S10116 S10187 E10185 S10211 U10283 S10314 U10311 " "S10412 U10411 S10617 U10617 S10686 U10714 S10786 U10783 S11121 E11126 " "S11216 S11234 U11237 U11323 S11348 U11343 E11343 U11678 U11873 S12135 " "U12257 U12768 S13143 S17186 E17186 U17263 E18268 S18461 U18468 E18464 " "S18623 S21316 E21313 S21326 E21326 S21538 U21533 E21534 U21682 S23354 " "S25133 U28626 S34232 S35123 E35126 S37565 S38484 S42617 E43116 S43712 " "E43716 S46378 E46376 S46678 E46673 S47784 E47783 E48101 a01123 a01814 " "a01837 a10286 a10415 a10783 a11213 a11237 a12133 a12255 a18371 a18467 " "a25136 a28386 a41312 a42618 b31781 b32432 b38713 b46673 c10816 c11126 " "c11876 c12236 c12253 c16176 c18016 c18264 c18283 d01123 d01186 d01817 " "d01838 d01873 d10286 d10412 d11216 d11237 d12252 d12887 d13873 d17816 " "d18265 d18374 d18461 d25136 d41318 d42615 e01123 e01883 e10014 e10113 " "e10213 e10318 e10414 e10683 e10814 e11013 e11086 e11323 e12113 e12255 " "e12861 e13018 e13141 e17813 e18012 e18086 e18108 e18265 e18283 e18376 " "e18468 e18713 e18808 e18828 e21102 e21116 e21323 e21807 e21883 e23116 " "e23357 e26181 e28102 e28183 e28386 e28621 e31783 e32436 e35123 e38713 " "e41311 e42616 e46678 f10086 f10683 f10711 f10813 f11216 f11341 f11671 " "f12231 f12253 f12865 f12886 f13015 f16178 f17266 f18173 f18285 f18716 " "f18824 f21684 f23352 f23882 f25136 f37186 f41313 f42613 f43711 f46374 " "g01183 g11216 g11233 g12861 g13011 g13146 g16086 g17086 g17813 g18173 " "g18374 g18626 g18822 g21676 g21886 g23354 g23881 g28107 g32431 g34237 " "g37281 g38482 g38716 g41316 g43718 h10111 h10216 h10314 h10615 h10686 " "h10718 h10816 h11216 h11873 h12231 h12761 h12862 h13014 h13876 h16086 " "h16171 h18013 h18173 h18288 h18374 h18716 h18824 h21116 h21316 h21676 " "h28383 h28622 h31521 h31786 h31808 h32113 h34238 h37281 h37561 h38105 " "h38485 h41315 h42613 h43718 h46676 i10012 i10315 i10411 i11346 i12253 " "i12886 i13148 i13876 i17013 i18016 i18266 i18374 i23358 i23888 i25136 " "i26183 i28388 i31786 i31804 i37183 i37281 i37564 i38102 i43114 i46371 " ) def partie_A(): dire('') dire('Part A: certificate of Lemma 6 in Z/9[PG]') groupe = set() for a in range(M9): for b in range(M9): for c in range(M9): for d in range(M9): if (a * d - b * c) % M9 in (1, M9 - 1): groupe.add(canon((a, b, c, d))) dire(' order of PG: %d (expected 648)' % len(groupe)) if len(groupe) != 648: return False # left-hand side: x = T (1 + T' + T'**2)(1 + T + T**2), expanded into 9 terms x = {} for i in range(3): for j in range(3): g = T_ for _ in range(i): g = mul(g, TP_) for _ in range(j): g = mul(g, T_) ajoute(x, g, 1) # right-hand side: the certified combination somme = {} toks = ''.join(CERTIFICAT).split() ok_elts = True for t in toks: code = t[0] g = canon((int(t[1]), int(t[2]), int(t[3]), int(t[4]))) c = int(t[5]) if g not in groupe or det9(g) not in (1, M9 - 1): ok_elts = False for h, e in generateur(code, g).items(): ajoute(somme, h, c * e) x = {g: c for g, c in x.items() if c % M9} somme = {g: c for g, c in somme.items() if c % M9} egal = (x == somme) dire(' %d terms read; elements in PG: %s; equality with x modulo 9: %s' % (len(toks), 'yes' if ok_elts else 'NO', 'YES' if egal else 'NO')) # C acts by 0 modulo 3 on Sym w (hence C**2 by 0 modulo 9): check for w <= 20 ok_c = True for w in range(2, 21, 2): for k in (K1, K2, K3): a, b, c, d = k for j in range(w + 1): im = image_monome(w, j, a, b, c, d) im[j] -= 1 if any(t % 3 for t in im): ok_c = False dire(' sigma_k - 1 == 0 (mod 3) on Sym w for k = k1, k2, k3, w <= 20: %s' % ('yes' if ok_c else 'NO')) return egal and ok_elts and ok_c # ============================================================================= # Common tools: substitutions, period relations, Hatada lattice # ============================================================================= def image_monome(w, j, a, b, c, d): """coefficients of F(ax + cy, bx + dy) for F = x**j y**(w-j)""" A = [comb(j, s) * (a ** s) * (c ** (j - s)) for s in range(j + 1)] B = [comb(w - j, t) * (b ** t) * (d ** (w - j - t)) for t in range(w - j + 1)] out = [0] * (w + 1) for s, x in enumerate(A): if x: for t, y in enumerate(B): if y: out[s + t] += x * y return out def lignes_relations(w): rows = [] for j in range(w + 1): imS = image_monome(w, j, 0, -1, 1, 0) imU = image_monome(w, j, 1, -1, 1, 0) imU2 = image_monome(w, j, 0, -1, 1, -1) imE = image_monome(w, j, -1, 0, 0, 1) rS = imS[:] rS[j] += 1 rU = [imU[i] + imU2[i] for i in range(w + 1)] rU[j] += 1 rE = imE[:] rE[j] += 1 rows += [rS, rU, rE] return rows def noyau_rationnel(rows, n): M = [[Fraction(x) for x in r] for r in rows if any(r)] piv_cols = [] r = 0 for c in range(n): p = None for i in range(r, len(M)): if M[i][c] != 0: p = i break if p is None: continue M[r], M[p] = M[p], M[r] inv = 1 / M[r][c] M[r] = [x * inv for x in M[r]] for i in range(len(M)): if i != r and M[i][c] != 0: f = M[i][c] M[i] = [M[i][k] - f * M[r][k] for k in range(n)] piv_cols.append(c) r += 1 if r == len(M): break libres = [c for c in range(n) if c not in piv_cols] base = [] for fcol in libres: v = [Fraction(0)] * n v[fcol] = Fraction(1) for i, pc in enumerate(piv_cols): v[pc] = -M[i][fcol] den = 1 for x in v: den = den * x.denominator // gcd(den, x.denominator) vi = [int(x * den) for x in v] g = 0 for x in vi: g = gcd(g, x) base.append([x // g for x in vi]) return base def elimination_mod3(vecs, n): """reduced row echelon form modulo 3; returns (rows, pivot columns)""" M = [[x % 3 for x in v] for v in vecs] r = 0 piv = [] for c in range(n): p = None for i in range(r, len(M)): if M[i][c]: p = i break if p is None: continue M[r], M[p] = M[p], M[r] inv = 1 if M[r][c] == 1 else 2 M[r] = [(x * inv) % 3 for x in M[r]] for i in range(len(M)): if i != r and M[i][c]: f = M[i][c] M[i] = [(M[i][k] - f * M[r][k]) % 3 for k in range(n)] piv.append(c) r += 1 return M[:r], piv def dependance_mod3(base): d = len(base) n = len(base[0]) M = [[base[i][k] % 3 for k in range(n)] + [1 if t == i else 0 for t in range(d)] for i in range(d)] r = 0 for c in range(n): p = None for i in range(r, d): if M[i][c] % 3: p = i break if p is None: continue M[r], M[p] = M[p], M[r] inv = 1 if M[r][c] == 1 else 2 M[r] = [(x * inv) % 3 for x in M[r]] for i in range(d): if i != r and M[i][c] % 3: f = M[i][c] M[i] = [(M[i][k] - f * M[r][k]) % 3 for k in range(n + d)] r += 1 for i in range(r, d): if all(M[i][k] % 3 == 0 for k in range(n)): return M[i][n:] return None def sature_en_3(base): base = [b[:] for b in base] while True: c = dependance_mod3(base) if c is None: return base i0 = next(i for i in range(len(c)) if c[i] % 3) v = [sum(c[i] * base[i][k] for i in range(len(base))) for k in range(len(base[0]))] base[i0] = [x // 3 for x in v] def reseau_hatada(w): return sature_en_3(noyau_rationnel(lignes_relations(w), w + 1)) MAN2 = [(1, 0, 0, 2), (1, 1, 0, 2), (2, 0, 0, 1), (2, 0, 1, 1)] def matrice_T2(w): """rows: m_l(T_2 P) = sum_i Mt[l][i] m_i""" Mt = [[0] * (w + 1) for _ in range(w + 1)] for (a, b, c, d) in MAN2: for l in range(w + 1): im = image_monome(w, l, a, b, c, d) for i, x in enumerate(im): if x: Mt[l][i] += x return Mt def applique(Mt, m): return [sum(r[i] * m[i] for i in range(len(m)) if r[i] and m[i]) for r in Mt] # ============================================================================= # Part B: the Hatada lattice # ============================================================================= A2_CONNUS = {12: -24, 16: 216, 18: -528, 20: 456, 22: -288, 26: -48} def partie_B(): dire('') dire('Part B: Theorems I (mod 27) and K (mod 81) on the lattice L_k, weights 12 to %d' % KMAX_B) echecs = 0 for k in range(12, KMAX_B + 1, 2): if k == 14: continue t1 = time.time() w = k - 2 base = reseau_hatada(w) Mt = matrice_T2(w) cible = 9 * (k - 1) * (k - 1) s = 1 + pow(2, k - 1) ok3 = ok27 = ok81 = True vals = [] for m in base: t = applique(Mt, m) ok3 = ok3 and all(x % 3 == 0 for x in t) tt = applique(Mt, t) ok27 = ok27 and all((tt[i] - cible * m[i]) % 27 == 0 for i in range(w + 1)) if k % 6 == 4: ok81 = ok81 and all((tt[i] + 9 * t[i]) % 81 == 0 for i in range(w + 1)) else: ok81 = ok81 and all((tt[i] - s * s * m[i]) % 81 == 0 for i in range(w + 1)) if len(base) == 1: l = next(j for j in range(w + 1) if m[j]) vals.append(Fraction(t[l], m[l])) okv = True if len(base) == 1 and k in A2_CONNUS: okv = (vals[0] == A2_CONNUS[k]) if not (ok3 and ok27 and ok81 and okv): echecs += 1 dire(' k=%3d d=%2d T_2(L) in 3L: %s Thm I (mod 27): %s Thm K (mod 81, %s): %s%s (%.1f s)' % (k, len(base), 'ok' if ok3 else 'FAILED', 'ok' if ok27 else 'FAILED', 'T2 o T2 + 9 T2' if k % 6 == 4 else 'T2 o T2 - s**2', 'ok' if ok81 else 'FAILED', (' a_2 = %s' % vals[0]) if vals else '', time.time() - t1)) if time.time() - T0 > BUDGET * 0.7: dire(' Part B budget reached after k = %d' % k) break dire(' weights failing: %d (expected: 0)' % echecs) return echecs == 0 # ============================================================================= # Parts C and D: identity of Lemma 5 (characteristic 3) and condition of Lemma 6 # ============================================================================= def derivee_x(F, w): return [((a + 1) * F[a + 1]) % 3 for a in range(w)] def derivee_y(F, w): return [((w - a) * F[a]) % 3 for a in range(w)] def subst3(F, w, a, b, c, d): out = [0] * (w + 1) for j, cf in enumerate(F): if cf % 3: im = image_monome(w, j, a, b, c, d) for i, x in enumerate(im): if x % 3: out[i] = (out[i] + cf * x) % 3 return out def fois_lineaire(G, p, q): """(p x + q y) G""" out = [0] * (len(G) + 1) for a, g in enumerate(G): if g: out[a + 1] = (out[a + 1] + p * g) % 3 out[a] = (out[a] + q * g) % 3 return out def A_etoile(F, w): """A* F = y F_y(x,-y) + y F_y(x,x-y) + x F_x(-x,y) + x F_x(y-x,y) (mod 3)""" Fx = derivee_x(F, w) Fy = derivee_y(F, w) s1 = subst3(Fy, w - 1, 1, 0, 0, -1) s2 = subst3(Fy, w - 1, 1, 1, 0, -1) s3 = subst3(Fx, w - 1, -1, 0, 0, 1) s4 = subst3(Fx, w - 1, -1, 0, 1, 1) t1 = fois_lineaire([(s1[i] + s2[i]) % 3 for i in range(w)], 0, 1) t2 = fois_lineaire([(s3[i] + s4[i]) % 3 for i in range(w)], 1, 0) return [(t1[i] + t2[i]) % 3 for i in range(w + 1)] def cond_lineaire(F, w): """y d/dx [ (sigma_T - 1)**2 F ] (mod 3)""" t1 = subst3(F, w, 1, 1, 0, 1) t2 = subst3(F, w, 1, 2, 0, 1) G = [(t2[i] - 2 * t1[i] + F[i]) % 3 for i in range(w + 1)] return fois_lineaire(derivee_x(G, w), 0, 1) def noyau_mod3(rows, n): R, piv = elimination_mod3([r for r in rows if any(x % 3 for x in r)], n) libres = [c for c in range(n) if c not in piv] base = [] for fc in libres: v = [0] * n v[fc] = 1 for i, pc in enumerate(piv): v[pc] = (-R[i][fc]) % 3 base.append(v) return base def partie_CD(): dire('') dire('Parts C and D: Lemma 5 on the solutions modulo 3, Lemma 6 on L_k mod 3, weights 12 to %d' % KMAX_C) echecs = 0 for k in range(12, KMAX_C + 1, 2): if k == 14: continue w = k - 2 n = w + 1 mono = [[1 if i == j else 0 for i in range(n)] for j in range(n)] AF = [A_etoile(F, w) for F in mono] AAF = [A_etoile(G, w) for G in AF] CF = [cond_lineaire(F, w) for F in mono] sols = noyau_mod3(lignes_relations(w), n) okC = True for mu in sols: for j in range(n): g = sum(mu[i] * (AAF[j][i] + AF[j][i]) for i in range(n)) % 3 d = (w * (w + 2) * mu[j] - w * sum(mu[i] * CF[j][i] for i in range(n))) % 3 if g != d: okC = False L = reseau_hatada(w) okD = all(sum(m[i] * CF[j][i] for i in range(n)) % 3 == 0 for m in L for j in range(n)) if not (okC and okD): echecs += 1 dire(' k=%3d solutions mod 3: %2d Lemma 5: %s lattice: %2d Lemma 6: %s' % (k, len(sols), 'ok' if okC else 'FAILED', len(L), 'ok' if okD else 'FAILED')) if time.time() - T0 > BUDGET: dire(' budget reached after k = %d' % k) break dire(' weights failing: %d (expected: 0)' % echecs) return echecs == 0 # ============================================================================= # Parts E and G: Theorem K (modulo 81) # ============================================================================= M81 = int(81) def mul81(g, h): a, b, c, d = g e, f, p, q = h return ((a * e + b * p) % M81, (a * f + b * q) % M81, (c * e + d * p) % M81, (c * f + d * q) % M81) def el81(g, c=1): return {tuple(int(t) % M81 for t in g): int(c) % M81} def somme81(*termes): out = {} for c, X in termes: for g, x in X.items(): out[g] = (out.get(g, 0) + c * x) % M81 return {g: x for g, x in out.items() if x} def prod81(X, Y): out = {} for g, x in X.items(): for h, y in Y.items(): k = mul81(g, h) out[k] = (out.get(k, 0) + x * y) % M81 return {g: x for g, x in out.items() if x} # representatives of GL_2(F_3)/{+I,-I}: lexicographic order, keeping the first of each pair REPS24 = [] _vus = set() for _a in range(3): for _b in range(3): for _c in range(3): for _d in range(3): if (_a * _d - _b * _c) % 3 == 0: continue _t = (_a, _b, _c, _d) _n = tuple((-x) % 3 for x in _t) if _t in _vus or _n in _vus: continue _vus.add(_t) REPS24.append(_t) CLASSE = {} for _i, _r in enumerate(REPS24): CLASSE[_r] = _i CLASSE[tuple((-x) % 3 for x in _r)] = _i REPINV = [] for _r in REPS24: _a, _b, _c, _d = _r _di = pow((_a * _d - _b * _c) % M81, -1, M81) REPINV.append(((_d * _di) % M81, (-_b * _di) % M81, (-_c * _di) % M81, (_a * _di) % M81)) UN81 = el81((1, 0, 0, 1)) _U81 = (1, M81 - 1, 1, 0) GEN81 = {'S': somme81((1, UN81), (1, el81((0, -1, 1, 0)))), 'U': somme81((1, UN81), (1, el81(_U81)), (1, el81(mul81(_U81, _U81)))), 'E': somme81((1, UN81), (1, el81((-1, 0, 0, 1))))} KAPPA81 = [(4, 0, 0, 1), (1, 3, 0, 1), (1, 0, 3, 1), (1, 0, 0, 4)] BFAC81 = [somme81((1, el81(k)), (-1, UN81)) for k in KAPPA81] MAN2_81 = somme81(*[(1, el81(g)) for g in MAN2]) def terme81(tok): """c . gen . h~ . (k1-1)**a1 (k2-1)**a2 (k3-1)**a3 (k4-1)**a4""" code = tok[0] h = ord(tok[1]) - ord('a') al = [int(tok[2 + t]) for t in range(4)] c = int(tok[6:8]) X = el81(REPS24[h]) for t in range(4): for _ in range(al[t]): X = prod81(X, BFAC81[t]) return prod81(GEN81[code], X), c def zeta_certificat(texte): acc = {} toks = ''.join(texte).split() for tok in toks: X, c = terme81(tok) for g, x in X.items(): acc[g] = (acc.get(g, 0) + c * x) % M81 return {g: x for g, x in acc.items() if x}, len(toks) def coord_kappa(k): """sigma_k (x**i y**j) = (p x + r y)**i (q x + s y)**j, k = (p, q; r, s) == I (mod 3); modulo 81: sum over delta of [ sum c(delta, A, B) C(i, A) C(j, B) ] x**(i+delta) y**(j-delta)""" p, q, r, s = k out = {} for a in range(4): for b in range(4 - a): for m in range(4 - a - b): for m2 in range(4 - a - b - m): val = (r ** a) * (q ** b) * ((p - 1) ** m) * ((s - 1) ** m2) * comb(a + m, a) * comb(b + m2, b) cle = (b - a, a + m, b + m2) out[cle] = (out.get(cle, 0) + val) % M81 return out def decompose81(g): i = CLASSE[tuple(t % 3 for t in g)] k = mul81(REPINV[i], g) if k[0] % 3 != 1: k = tuple((-t) % M81 for t in k) if not ((k[0] - 1) % 3 == 0 and k[1] % 3 == 0 and k[2] % 3 == 0 and (k[3] - 1) % 3 == 0): raise ValueError('decomposition impossible') return i, k def binom_entier(z, k): num = 1 for t in range(k): num *= (z - t) return num // comb_fact(k) def comb_fact(k): f = 1 for t in range(2, k + 1): f *= t return f def critere_nul(X, r): """Lemma 7: true if the Mahler coefficients (in i and t, j = 3t + r - i) of all the polynomials f(h, delta) vanish modulo 81; then X acts by 0 modulo 81 on the forms of even degree w, w == r (mod 3).""" blocs = {} for g, x in X.items(): h, k = decompose81(g) for (dl, A, B), v in coord_kappa(k).items(): bl = blocs.setdefault((h, dl), {}) bl[(A, B)] = (bl.get((A, B), 0) + x * v) % M81 for bl in blocs.values(): vals = [[sum(c * comb(i, A) * binom_entier(3 * t + r - i, B) for (A, B), c in bl.items()) for t in range(4)] for i in range(4)] for A in range(4): for B in range(4 - A): tot = 0 for u in range(A + 1): for v in range(B + 1): tot += (-1) ** (A - u + B - v) * comb(A, u) * comb(B, v) * vals[u][v] if tot % M81: return False, len(blocs) return True, len(blocs) CERT_K4 = ( "Sa000057 Sa000164 Sa000229 Sa001008 Sa001147 Sa001202 Sa002030 Sa010051 " "Sa010116 Sa010273 Sa011027 Sa011106 Sa020074 Sa100006 Sa100126 Sa101032 " "Sa110042 Sb000068 Sb000152 Sb000204 Sb000315 Sb001073 Sb001162 Sb001242 " "Sb010015 Sb010162 Sb010244 Sb011073 Sb020006 Sb020109 Sb100079 Sb100113 " "Sb101015 Sb110044 Sc000059 Sc000105 Sc000259 Sc000305 Sc001047 Sc001111 " "Sc001242 Sc002015 Sc010007 Sc010174 Sc010268 Sc011056 Sc012072 Sc020035 " "Sc021011 Sc100072 Sc100172 Sc101065 Sc110024 Sd000077 Sd000136 Sd000261 " "Sd000334 Sd001019 Sd001126 Sd001246 Sd002071 Sd010071 Sd010151 Sd011059 " "Sd020069 Sd100018 Sd100127 Sd101023 Sd110056 Se000072 Se000127 Se000260 " "Se000328 Se001064 Se001180 Se001235 Se002023 Se010069 Se010178 Se010238 " "Se011048 Se012044 Se020055 Se020151 Se100075 Se100126 Se101024 Se110012 " "Se200072 Sf000021 Sf000105 Sf001052 Sf001180 Sf002011 Sf010072 Sf010161 " "Sf011034 Sf020034 Sf021029 Sf100024 Sf101059 Sf110066 Sg010030 Sh010066 " "Si000029 Si000143 Si000210 Si000359 Si001073 Si001154 Si001203 Si002035 " "Si010049 Si010111 Si010206 Si011031 Si011121 Si020069 Si100028 Si100147 " "Si101068 Si110074 Sj000073 Sj000110 Sj000261 Sj001024 Sj001124 Sj002067 " "Sj010006 Sj010150 Sj010238 Sj011061 Sj020047 Sj100009 Sj100160 Sj101027 " "Sj110076 Sk000036 Sk000161 Sk000215 Sk001055 Sk001120 Sk002073 Sk010032 " "Sk010101 Sk011031 Sk020027 Sk100080 Sk100111 Sk101023 Sk110066 Sl000049 " "Sl000168 Sl000205 Sl001056 Sl001112 Sl002071 Sl010073 Sl010180 Sl011042 " "Sl020071 Sl100074 Sl101072 Sl110032 Sm000077 Sn010029 Sp000045 Sp000149 " "Sp000279 Sp000348 Sp001028 Sp001139 Sp002027 Sp010009 Sp010110 Sp011035 " "Sp020041 Sp021042 Sp100058 Sp101016 Sp110023 Sq010060 Sr000033 Sr000176 " "Sr001009 Sr001109 Sr002069 Sr010011 Sr010105 Sr011044 Sr020037 Sr021006 " "Su010007 Sw010005 Sx000029 Ua000041 Ua001007 Ua001173 Ua002077 Ua010063 " "Ua010158 Ua011031 Ua020021 Ua100062 Ua101069 Ua110036 Ub000071 Ub000109 " "Ub000279 Ub001047 Ub001133 Ub002065 Ub010008 Ub010178 Ub011005 Ub020042 " "Ub100071 Ub101042 Ub110053 Uc000032 Uc000125 Uc000266 Uc001030 Uc001148 " "Uc001213 Uc002023 Uc010053 Uc010154 Uc010254 Uc011062 Uc020060 Uc020110 " "Uc100067 Uc101002 Uc110079 Ud000041 Ud000102 Ud001012 Ud001154 Ud002003 " "Ud010004 Ud010144 Ud010239 Ud020029 Ud100060 Ud101016 Ud110016 Ue000038 " "Ue000180 Ue001001 Ue001142 Ue002006 Ue010003 Ue010136 Ue020008 Ue101045 " "Ue110050 Uf000026 Uf000163 Uf001021 Uf001118 Uf002072 Uf010062 Uf010150 " "Uf010279 Uf020047 Ug020144 Ug102009 Ug200075 Uh000080 Uh000263 Uh010047 " "Ui110140 Ui200018 Uj000250 Uj010006 Uj010254 Uj100239 Uk110157 Uk200066 " "Ul000027 Ul000232 Ul003006 Ul010042 Ul010263 Ul100251 Um110179 Um200038 " "Um300043 Un000073 Un000224 Un001033 Uo110121 Uo200018 Uo200123 Uo300059 " "Up000033 Up000272 Up001066 Up010059 Up010279 Up100263 Up300077 Uq200043 " "Uq300073 Ur000001 Ur000203 Ur001019 Ur010058 Us200057 Ut000047 Ut000246 " "Ut001019 Ut010258 Uu110179 Uu200046 Uu300019 Uw110132 Uw200039 Uw300048 " "Ux000064 Ux000214 Ux001056 Ux010065 Ux010235 Ux020029 Ux020129 Ux021029 " "Ux030029 Ux100039 Ux100139 Ux101044 Ux101144 Ux102044 Ux110044 Ux110144 " "Ux111044 Ux120044 Ux200044 Ux200144 Ux201044 Ux210044 Ea000044 Ea000144 " "Ea000244 Ea000344 Ea001044 Ea001144 Ea001244 Ea002044 Ea002144 Ea003044 " "Ea010044 Ea010144 Ea010244 Ea011044 Ea011144 Ea012044 Ea020044 Ea021044 " "Ea030044 Ea100044 Ea100144 Ea100244 Ea101044 Ea110044 Ea111044 Ea120044 " "Ea201044 Ea210044 Eb000077 Eb000144 Eb000208 Eb000344 Eb001002 Eb001144 " "Eb001244 Eb002044 Eb002144 Eb010018 Eb010144 Eb011044 Eb011144 Eb012044 " "Eb020044 Eb020144 Eb021044 Eb030044 Eb100044 Eb100144 Eb101044 Eb101144 " "Eb102044 Eb110044 Eb110144 Eb111044 Eb120044 Eb200044 Eb200144 Eb201044 " "Eb210044 Ec000044 Ec000144 Ec000244 Ec000344 Ec001044 Ec001144 Ec001244 " "Ec002044 Ec002144 Ec003044 Ec010044 Ec010144 Ec010244 Ec011044 Ec011144 " "Ec012044 Ec020044 Ec020139 Ec021044 Ec030044 Ec100044 Ec100144 Ec100244 " "Ec101044 Ec110044 Ec111044 Ec120044 Ec200001 Ec201044 Ec210044 Ed000027 " "Ed000144 Ed000266 Ed000344 Ed001051 Ed001144 Ed001244 Ed002044 Ed002144 " "Ed010013 Ed010144 Ed010248 Ed011044 Ed011144 Ed012044 Ed020044 Ed020144 " "Ed021044 Ed030044 Ed100044 Ed100144 Ed101044 Ed101144 Ed102044 Ed110044 " "Ed110144 Ed111044 Ed120044 Ed200044 Ed200144 Ed201044 Ed210044 Ee000044 " "Ee000144 Ee000244 Ee000344 Ee001044 Ee001144 Ee001244 Ee002044 Ee002144 " "Ee003044 Ee010044 Ee010144 Ee010244 Ee011044 Ee011144 Ee012044 Ee020044 " "Ee021044 Ee030044 Ee100044 Ee100144 Ee100244 Ee101044 Ee110044 Ee111044 " "Ee120044 Ee201044 Ee210044 Ef000028 Ef000144 Ef000344 Ef001049 Ef001144 " "Ef001244 Ef002044 Ef002144 Ef010004 Ef010144 Ef011044 Ef011144 Ef012044 " "Ef020044 Ef020144 Ef021044 Ef030044 Ef100044 Ef100144 Ef101044 Ef101144 " "Ef102044 Ef110044 Ef110144 Ef111044 Ef120044 Ef200044 Ef200144 Ef201044 " "Ef210044 Eg000044 Eg000144 Eg000244 Eg000344 Eg001044 Eg001144 Eg001244 " "Eg002044 Eg002144 Eg003044 Eg010044 Eg010144 Eg010244 Eg011044 Eg011144 " "Eg012044 Eg020044 Eg021044 Eg030044 Eg100044 Eg100144 Eg100244 Eg101044 " "Eg110044 Eg111044 Eg120044 Eg201044 Eg210044 Eh000027 Eh000144 Eh000344 " "Eh001144 Eh001244 Eh002044 Eh002144 Eh010075 Eh010144 Eh011044 Eh011144 " "Eh012044 Eh020044 Eh020144 Eh021044 Eh030044 Eh100044 Eh100144 Eh101044 " "Eh101144 Eh102044 Eh110044 Eh110144 Eh111044 Eh120044 Eh200044 Eh200144 " "Eh201044 Eh210044 Ei000044 Ei000144 Ei000244 Ei000344 Ei001044 Ei001144 " "Ei001244 Ei002044 Ei002144 Ei003044 Ei010044 Ei010144 Ei010244 Ei011044 " "Ei011144 Ei012044 Ei020044 Ei020129 Ei021044 Ei030044 Ei100044 Ei100144 " "Ei100244 Ei101044 Ei110044 Ei111044 Ei120044 Ei200030 Ei200139 Ei201044 " "Ei210044 Ei300039 Ej000047 Ej000144 Ej000238 Ej000344 Ej001048 Ej001144 " "Ej001244 Ej002044 Ej002144 Ej010017 Ej010144 Ej010210 Ej011044 Ej011144 " "Ej012044 Ej020044 Ej020144 Ej021044 Ej030044 Ej100044 Ej100144 Ej100206 " "Ej101044 Ej101144 Ej102044 Ej110044 Ej110144 Ej111044 Ej120044 Ej200044 " "Ej200144 Ej201044 Ej210044 Ek000044 Ek000144 Ek000244 Ek000344 Ek001044 " "Ek001144 Ek001244 Ek002044 Ek002144 Ek003044 Ek010044 Ek010144 Ek010244 " "Ek011044 Ek011144 Ek012044 Ek020044 Ek021044 Ek030044 Ek100044 Ek100144 " "Ek100244 Ek101044 Ek110044 Ek111044 Ek120044 Ek200038 Ek201044 Ek210044 " "Ek300068 El000068 El000144 El000257 El000344 El001073 El001144 El001244 " "El002044 El002144 El010053 El010144 El010266 El011044 El011144 El012044 " "El020044 El020144 El021044 El030044 El100044 El100144 El101044 El101144 " "El102044 El110044 El110144 El111044 El120044 El200044 El200144 El201044 " "El210044 Em000044 Em000144 Em000244 Em000344 Em001044 Em001144 Em001244 " "Em002044 Em002144 Em003044 Em010044 Em010144 Em010244 Em011044 Em011144 " "Em012044 Em020044 Em020152 Em021044 Em030044 Em100044 Em100144 Em100244 " "Em101044 Em110044 Em111044 Em120044 Em200075 Em201044 Em210044 En000053 " "En000144 En000276 En000344 En001036 En001144 En001244 En002044 En002144 " "En010075 En010144 En010257 En011044 En011144 En012044 En020044 En020144 " "En021044 En030044 En100044 En100144 En100251 En101044 En101144 En102044 " "En110044 En110144 En111044 En120044 En200044 En200144 En201044 En210044 " "En300053 Eo000044 Eo000144 Eo000244 Eo000344 Eo001044 Eo001144 Eo001244 " "Eo002044 Eo002144 Eo003044 Eo010044 Eo010144 Eo010244 Eo011044 Eo011144 " "Eo012044 Eo020044 Eo020114 Eo021044 Eo030044 Eo100044 Eo100144 Eo100244 " "Eo101044 Eo110044 Eo110120 Eo111044 Eo120044 Eo200047 Eo201044 Eo210044 " "Eo300010 Ep000043 Ep000144 Ep000243 Ep000344 Ep001038 Ep001144 Ep001244 " "Ep002044 Ep002144 Ep010066 Ep010144 Ep011044 Ep011144 Ep012044 Ep020044 " "Ep020144 Ep021044 Ep030044 Ep100044 Ep100144 Ep100241 Ep101044 Ep101144 " "Ep102044 Ep110044 Ep110144 Ep111044 Ep120044 Ep200044 Ep200144 Ep201044 " "Ep210044 Ep300042 Eq000044 Eq000144 Eq000244 Eq000344 Eq001044 Eq001144 " "Eq001244 Eq002044 Eq002144 Eq003044 Eq010044 Eq010144 Eq010244 Eq011044 " "Eq011144 Eq012044 Eq020044 Eq021044 Eq030044 Eq100044 Eq100144 Eq100244 " "Eq101044 Eq110044 Eq111044 Eq120044 Eq200063 Eq201044 Eq210044 Er000031 " "Er000144 Er000246 Er000344 Er001059 Er001144 Er001244 Er002044 Er002144 " "Er010013 Er010144 Er011044 Er011144 Er012044 Er020044 Er020144 Er021044 " "Er030044 Er100044 Er100144 Er101044 Er101144 Er102044 Er110044 Er110144 " "Er111044 Er120044 Er200044 Er200144 Er201044 Er210044 Es000044 Es000144 " "Es000244 Es000344 Es001044 Es001144 Es001244 Es002044 Es002144 Es003044 " "Es010044 Es010144 Es010244 Es011044 Es011144 Es012044 Es020044 Es021044 " "Es030044 Es100044 Es100144 Es100244 Es101044 Es110044 Es111044 Es120044 " "Es201044 Es210044 Et000070 Et000144 Et000344 Et001057 Et001144 Et001244 " "Et002035 Et002135 Et010056 Et010135 Et011035 Et011135 Et012035 Et020035 " "Et020135 Et021035 Et030035 Et100035 Et100135 Et101035 Et101135 Et102035 " "Et110035 Et110135 Et111035 Et120035 Et200035 Et200135 Et201035 Et210035 " "Eu000035 Eu000135 Eu000235 Eu000335 Eu001035 Eu001135 Eu001235 Eu002035 " "Eu002135 Eu003035 Eu010035 Eu010135 Eu010235 Eu011035 Eu011135 Eu012035 " "Eu020035 Eu020162 Eu021035 Eu030035 Eu100035 Eu100135 Eu100235 Eu101035 " "Eu110035 Eu110143 Eu111035 Eu120035 Eu200035 Eu200126 Eu201035 Eu210035 " "Eu300080 Ev000030 Ev000135 Ev000217 Ev000335 Ev001034 Ev001135 Ev001235 " "Ev002035 Ev002135 Ev010015 Ev010135 Ev010244 Ev011035 Ev011135 Ev012035 " "Ev020035 Ev020135 Ev021035 Ev030035 Ev100035 Ev100135 Ev101035 Ev101135 " "Ev102035 Ev110035 Ev110135 Ev111035 Ev120035 Ev200035 Ev200135 Ev201035 " "Ev210035 Ev300074 Ew000035 Ew000135 Ew000235 Ew000335 Ew001037 Ew001137 " "Ew001237 Ew002037 Ew002137 Ew003037 Ew010037 Ew010137 Ew010237 Ew011037 " "Ew011137 Ew012037 Ew020020 Ew021020 Ew030020 Ew100009 Ew100109 Ew100209 " "Ew101009 Ew110075 Ew111075 Ew120075 Ew201075 Ew210075 Ex000066 Ex000175 " "Ex000375 Ex001053 Ex001175 Ex001275 Ex002075 Ex002175 Ex010067 Ex010175 " "Ex010213 Ex011075 Ex011175 Ex012075 Ex020075 Ex020175 Ex021075 Ex030075 " "Ex100075 Ex100175 Ex100276 Ex101075 Ex101175 Ex102075 Ex110075 Ex110175 " "Ex111075 Ex120075 Ex200075 Ex200175 Ex201075 Ex210075 Ex300045 " ) CERT_S0 = ( "Sa001104 Sa002039 Sa010104 Sb000050 Sb000146 Sb000229 Sb001051 Sb001178 " "Sb002015 Sb010022 Sb010152 Sb011068 Sb020038 Sb100004 Sb100167 Sb101049 " "Sb110020 Sb200038 Sc000047 Sc000174 Sc000249 Sc001049 Sc001171 Sc002075 " "Sc010059 Sc010152 Sc011028 Sc020074 Sc100048 Sc100169 Sc101070 Sc110011 " "Sc200053 Sd000241 Sd020018 Sd100003 Sd101065 Se000069 Se000118 Se000279 " "Se001072 Se001164 Se002061 Se010037 Se010126 Se011070 Se020017 Se100024 " "Se100178 Se101027 Se110044 Se200017 Sf000051 Sf000108 Sf000232 Sf001014 " "Sf001112 Sf002024 Sf010060 Sf011033 Sf100020 Sf110061 Sg020031 Sh101004 " "Si000038 Si000177 Si000204 Si001077 Si001118 Si002011 Si010033 Si011041 " "Si020058 Si100048 Si100170 Si110028 Si200031 Sj000006 Sj000129 Sj000244 " "Sj001007 Sj001162 Sj002055 Sj010053 Sj010109 Sj011068 Sj020004 Sj100007 " "Sj100154 Sj110063 Sj200012 Sk000035 Sk000140 Sk000241 Sk001017 Sk001173 " "Sk002046 Sk010050 Sk010152 Sk011070 Sk020062 Sk100030 Sk100114 Sk101078 " "Sk110031 Sk200056 Sl000002 Sl000145 Sl000238 Sl001071 Sl001112 Sl002060 " "Sl010017 Sl010160 Sl011062 Sl020060 Sl100064 Sl100160 Sl101060 Sl110072 " "Sl200060 Sm000060 Sm000160 Sm000260 Sm001060 Sm001160 Sm002060 Sm010060 " "Sm010149 Sm011060 Sm020060 Sm100060 Sm100160 Sm101060 Sm110060 Sn000008 " "Sn000160 Sn000277 Sn001060 Sn001160 Sn010064 Sn010160 Sn011060 Sn020053 " "Sn100071 Sn100160 Sn110060 Sn200043 So000060 So000160 So000260 So001060 " "So001148 So002039 So010060 So010171 So011060 So020060 So100060 So100160 " "So101060 So110060 So200060 Sp000036 Sp000120 Sp000243 Sp001046 Sp001145 " "Sp002047 Sp010079 Sp010125 Sp011026 Sp020056 Sp100002 Sp100147 Sp101073 " "Sp110019 Sp200004 Sq000060 Sq000160 Sq000260 Sq001060 Sq001160 Sq002060 " "Sq010050 Sq010160 Sq011060 Sq020060 Sq100060 Sq100160 Sq101060 Sq110060 " "Sq200060 Sr000004 Sr000168 Sr000209 Sr001043 Sr001102 Sr002060 Sr010060 " "Sr010168 Sr011064 Sr020068 Sr100026 Sr100160 Sr101001 Sr110028 Sr200060 " "Ss000041 Ss000231 Ss001060 Ss010060 Ss011060 Ss020032 Ss100060 Ss100160 " "Ss101060 Ss110060 St000017 St000160 St001060 St001160 St002060 St010060 " "St010160 St011060 St020060 St100060 St100160 St101015 St110060 St200060 " "Su000060 Su000160 Su000260 Su001060 Su001160 Su002060 Su010011 Su010160 " "Su011060 Su020051 Su100060 Su100160 Su101060 Su110060 Su200060 Sv000060 " "Sv000160 Sv000260 Sv001060 Sv001160 Sv002060 Sv010060 Sv010160 Sv011060 " "Sv020060 Sv100060 Sv100160 Sv101080 Sv110060 Sv200060 Sw000060 Sw000160 " "Sw000260 Sw001060 Sw010077 Sw011060 Sw020060 Sw101060 Sw110060 Sx000025 " "Sx000160 Sx000219 Sx001060 Sx002060 Sx010060 Sx010160 Sx011060 Sx020063 " "Sx100160 Sx110060 Sx200060 Ua000060 Ua000160 Ua000260 Ua001060 Ua001160 " "Ua002060 Ua010012 Ua010109 Ua011012 Ua020012 Ua100012 Ua100112 Ua101012 " "Ua110012 Ua200012 Ub000012 Ub000112 Ub000212 Ub001012 Ub001112 Ub002012 " "Ub010012 Ub010112 Ub011012 Ub020012 Ub100012 Ub100112 Ub101012 Ub110012 " "Ub200012 Uc000012 Uc000112 Uc000212 Uc001012 Uc001112 Uc002012 Uc010012 " "Uc010153 Uc011012 Uc020012 Uc100012 Uc100112 Uc101012 Uc110012 Uc200021 " "Ud000015 Ud000112 Ud000222 Ud001012 Ud001112 Ud002021 Ud010051 Ud010112 " "Ud011012 Ud020065 Ud100112 Ud101011 Ud110012 Ue000012 Ue000112 Ue000212 " "Ue001012 Ue001165 Ue002021 Ue010012 Ue010160 Ue011012 Ue020012 Ue100012 " "Ue100112 Ue101012 Ue110012 Ue200012 Uf000065 Uf000108 Uf000244 Uf001012 " "Uf001112 Uf002012 Uf010012 Uf010112 Uf011012 Uf020012 Uf100012 Uf100112 " "Uf101012 Uf110012 Uf200021 Ug000012 Ug000160 Ug000260 Ug001060 Ug001160 " "Ug002060 Ug010040 Ug010140 Ug011040 Ug020040 Ug100040 Ug100140 Ug101040 " "Ug110040 Ug200040 Uh000040 Uh000140 Uh000207 Uh001040 Uh001140 Uh002040 " "Uh010048 Uh010148 Uh011048 Uh020049 Uh100049 Uh100148 Uh101061 Uh110048 " "Uh200048 Ui000029 Ui000112 Ui000248 Ui001048 Ui001104 Ui010048 Ui010134 " "Ui011048 Ui020036 Ui100048 Ui100148 Ui101048 Ui110048 Ui200033 Uj000065 " "Uj000148 Uj001048 Uj001148 Uj002048 Uj010048 Uj010148 Uj011048 Uj020048 " "Uj100048 Uj100148 Uj101066 Uj110048 Uj200048 Uk000048 Uk000148 Uk000248 " "Uk001048 Uk001148 Uk002048 Uk010048 Uk010148 Uk011048 Uk020065 Uk100048 " "Uk100148 Uk101048 Uk110048 Uk200048 Ul000048 Ul000148 Ul000248 Ul001048 " "Ul001148 Ul002048 Ul010048 Ul010148 Ul011048 Ul020048 Ul100048 Ul100148 " "Ul110048 Ul200048 Um000048 Um000148 Um000248 Um001048 Um010048 Um010169 " "Um011048 Um020048 Um101048 Um110048 Un000055 Un000148 Un000243 Un001048 " "Un001147 Un002048 Un010048 Un010148 Un011048 Un020007 Un100080 Un100148 " "Un101041 Un110048 Un200048 Uo000048 Uo000148 Uo000248 Uo001043 Uo001143 " "Uo002043 Uo010038 Uo010147 Uo011038 Uo020038 Uo100038 Uo100138 Uo101038 " "Uo110038 Uo200032 Up000032 Up000132 Up000232 Up001032 Up002032 Up010032 " "Up010132 Up011032 Up020032 Up100032 Up100132 Up101032 Up110032 Up200032 " "Uq000032 Uq000132 Uq000232 Uq001032 Uq001132 Uq002032 Uq010032 Uq010121 " "Uq011032 Uq020032 Uq100032 Uq100132 Uq101032 Uq110032 Uq200077 Ur000009 " "Ur000132 Ur000267 Ur001032 Ur001132 Ur002060 Ur010074 Ur010132 Ur011032 " "Ur020065 Ur100049 Ur100132 Ur101024 Ur110032 Ur200046 Us000032 Us000132 " "Us000232 Us001032 Us001137 Us002021 Us010032 Us010146 Us011032 Us020032 " "Us100032 Us100132 Us101032 Us110032 Us200019 Ut000048 Ut000147 Ut000224 " "Ut001018 Ut001118 Ut002018 Ut010042 Ut010142 Ut011012 Ut020012 Ut100012 " "Ut100112 Ut101012 Ut110057 Ut200021 Uu000073 Uu000158 Uu000258 Uu001066 " "Uu001166 Uu002038 Uu010065 Uu010165 Uu011042 Uu020016 Uu100074 Uu100174 " "Uu101074 Uu110055 Uu200003 Uv000076 Uv000176 Uv000231 Uv001047 Uv001147 " "Uv002057 Uv010020 Uv010120 Uv011020 Uv020004 Uv100016 Uv100120 Uv101069 " "Uv110014 Uv200067 Uw000069 Uw000127 Uw000267 Uw001067 Uw001121 Uw002027 " "Uw010067 Uw010124 Uw011067 Uw020016 Uw100067 Uw100167 Uw101067 Uw110067 " "Uw200047 Ux000066 Ux000167 Ux000213 Ux001067 Ux001167 Ux002067 Ux010067 " "Ux010167 Ux011067 Ux020067 Ux100067 Ux100167 Ux101063 Ux110006 Ux200006 " "Ea000070 Ea000114 Ea000214 Ea001014 Ea001114 Ea002014 Ea010014 Ea010114 " "Ea011014 Ea020045 Ea100012 Ea100112 Ea101012 Ea110056 Ea200056 Eb000056 " "Eb000156 Eb000256 Eb001056 Eb001156 Eb002056 Eb010056 Eb010156 Eb011056 " "Eb020056 Eb100056 Eb100156 Eb110027 Eb200027 Ec000027 Ec000127 Ec000227 " "Ec001027 Ec010027 Ec011027 Ec020027 Ec101027 Ec110027 Ed000131 Ed001022 " "Ed002019 Ed010037 Ed010163 Ed011006 Ed100103 Ed110050 Ed200009 Ee000009 " "Ee000109 Ee000209 Ee001009 Ee001109 Ee002009 Ee010009 Ee011009 Ee020009 " "Ee100009 Ee100109 Ee101009 Ee110009 Ee200009 Ef000029 Ef000129 Ef000229 " "Ef001029 Ef002029 Ef010009 Ef010109 Ef011009 Ef020036 Ef100036 Ef100136 " "Ef101001 Ef110001 Ef200001 Eg000013 Eg000163 Eg000263 Eg001036 Eg001136 " "Eg002063 Eg010003 Eg010165 Eg011037 Eg020037 Eg100053 Eg100153 Eg101003 " "Eg110052 Eg200065 Eh000049 Eh000140 Eh000265 Eh001019 Eh001147 Eh002049 " "Eh010049 Eh010150 Eh011056 Eh020065 Eh100049 Eh100108 Eh101065 Eh110012 " "Eh200065 Ei000012 Ei000112 Ei000212 Ei001012 Ei001165 Ei002007 Ei010012 " "Ei010165 Ei011012 Ei020012 Ei100012 Ei100112 Ei101042 Ei110042 Ei200042 " "Ej000042 Ej000142 Ej000223 Ej001042 Ej001142 Ej002042 Ej010043 Ej010143 " "Ej011043 Ej020043 Ej100043 Ej100143 Ej101043 Ej110043 Ej200065 Ek000043 " "Ek000143 Ek000243 Ek001043 Ek001143 Ek002043 Ek010043 Ek010143 Ek011043 " "Ek020043 Ek100043 Ek100143 Ek101043 Ek110043 Ek200043 El000043 El000143 " "El000221 El001043 El001143 El002043 El010043 El010143 El011043 El020021 " "El100021 El100143 El101021 El110043 El200043 Em000021 Em000121 Em000243 " "Em001007 Em001116 Em002021 Em010055 Em010121 Em011055 Em020021 Em100038 " "Em100120 Em101021 Em110039 Em200021 En000021 En000110 En000221 En001027 " "En001122 En002036 En010073 En010117 En011037 En020028 En100067 En100157 " "En101021 En110072 En200068 Eo000034 Eo000134 Eo000234 Eo001034 Eo001134 " "Eo002034 Eo010004 Eo010166 Eo011007 Eo020021 Eo100005 Eo100105 Eo101005 " "Eo110074 Eo200061 Ep000061 Ep000161 Ep000261 Ep001061 Ep001161 Ep002061 " "Ep010061 Ep010161 Ep011061 Ep020061 Ep100061 Ep100161 Ep101076 Ep110061 " "Ep200066 Eq000047 Eq000113 Eq000231 Eq001007 Eq001154 Eq002068 Eq010067 " "Eq010122 Eq011071 Eq020054 Eq100011 Eq100149 Eq101039 Eq110072 Eq200061 " "Er000073 Er000172 Er000228 Er001072 Er001156 Er002045 Er010045 Er010145 " "Er011045 Er020054 Er100050 Er100145 Er101065 Er110045 Er200045 Es000045 " "Es000154 Es000254 Es001060 Es001125 Es002025 Es010025 Es010155 Es011025 " "Es020025 Es100027 Es100127 Es101029 Es110050 Es200050 Et000042 Et000121 " "Et000207 Et001080 Et001165 Et002050 Et010019 Et010157 Et011010 Et020012 " "Et100024 Et100176 Et101039 Et110011 Et200033 Eu000033 Eu000133 Eu000233 " "Eu001033 Eu001133 Eu002054 Eu010054 Eu010120 Eu011054 Eu020054 Eu100054 " "Eu100154 Eu101038 Eu110049 Eu200021 Ev000009 Ev000149 Ev000260 Ev001049 " "Ev001149 Ev002033 Ev010059 Ev010149 Ev011049 Ev020019 Ev100047 Ev100149 " "Ev101062 Ev110076 Ev200044 Ew000018 Ew000177 Ew000277 Ew001029 Ew001145 " "Ew002021 Ew010029 Ew010130 Ew011046 Ew020053 Ew100021 Ew100135 Ew101033 " "Ew110040 Ew200054 Ex000027 Ex000104 Ex000264 Ex001003 Ex001127 Ex002027 " "Ex010027 Ex010125 Ex011005 Ex020070 Ex100049 Ex100148 Ex101048 Ex110020 " "Ex200052 " ) CERT_S1 = ( "Sa001117 Sa002076 Sa010152 Sb000052 Sb000165 Sb000269 Sb001018 Sb001132 " "Sb002040 Sb010013 Sb010127 Sb011016 Sb020063 Sb100002 Sb100174 Sb101028 " "Sb110060 Sb200072 Sc000045 Sc000142 Sc000208 Sc001078 Sc001124 Sc002066 " "Sc010016 Sc010170 Sc011002 Sc020042 Sc100025 Sc100137 Sc101037 Sc110072 " "Sc200062 Sd000211 Sd020065 Sd101016 Se000063 Se000138 Se000244 Se001020 " "Se001161 Se002004 Se010056 Se010152 Se011074 Se020012 Se100061 Se100162 " "Se101036 Se110044 Se200061 Sf000039 Sf000113 Sf000267 Sf001079 Sf002012 " "Sf010021 Sf010165 Sf011031 Sf100049 Sf101028 Sf110033 Sg002043 Sg010043 " "Sg010143 Sg011043 Sg020021 Sg100043 Sg100143 Sg101043 Sg110043 Sg200043 " "Sh000043 Sh000143 Sh000243 Sh001043 Sh001143 Sh002043 Sh010043 Sh010143 " "Sh011043 Sh020043 Sh100043 Sh100143 Sh101027 Sh110043 Sh200043 Si000003 " "Si000132 Si000256 Si001009 Si001120 Si002063 Si010072 Si010173 Si011080 " "Si020060 Si100008 Si100132 Si101065 Si110012 Sj000080 Sj000162 Sj000206 " "Sj001004 Sj001129 Sj002034 Sj010077 Sj010129 Sj011073 Sj020073 Sj100054 " "Sj100134 Sj101030 Sj110018 Sj200066 Sk000071 Sk000118 Sk000239 Sk001004 " "Sk001180 Sk002025 Sk010039 Sk010103 Sk011018 Sk020069 Sk100035 Sk100173 " "Sk101027 Sk110077 Sk200046 Sl000075 Sl000149 Sl000246 Sl001070 Sl001166 " "Sl002046 Sl010054 Sl010146 Sl011010 Sl020046 Sl100046 Sl100146 Sl101046 " "Sl110050 Sl200046 Sm000046 Sm000146 Sm000246 Sm001046 Sm001146 Sm002046 " "Sm010046 Sm010150 Sm011046 Sm020046 Sm100046 Sm100146 Sm101046 Sm110046 " "Sm200038 Sn000146 Sn000215 Sn001046 Sn001146 Sn010034 Sn010146 Sn011046 " "Sn020071 Sn100035 Sn100146 Sn110046 Sn200041 So000046 So000146 So000246 " "So001046 So001170 So002075 So010046 So010118 So011046 So020046 So100046 " "So100146 So101046 So110046 So200046 Sp000104 Sp000260 Sp001062 Sp001139 " "Sp002060 Sp010011 Sp010158 Sp011069 Sp020017 Sp100050 Sp100114 Sp101019 " "Sp110055 Sp200038 Sq000046 Sq000146 Sq000246 Sq001046 Sq001146 Sq002046 " "Sq010018 Sq010146 Sq011046 Sq020046 Sq100046 Sq100146 Sq101046 Sq110046 " "Sq200046 Sr000071 Sr000159 Sr000203 Sr001040 Sr001108 Sr002042 Sr010009 " "Sr010169 Sr011046 Sr020055 Sr100146 Sr101001 Sr110062 Sr200046 Ss000080 " "Ss000246 Ss001046 Ss002029 Ss010046 Ss011046 Ss100046 Ss100146 Ss101046 " "Ss110046 St000065 St000146 St001046 St001146 St002046 St010046 St010146 " "St011046 St020046 St100046 St100146 St101069 St110046 St200046 Su000046 " "Su000146 Su000246 Su001046 Su001146 Su002046 Su010070 Su010146 Su011046 " "Su020044 Su100046 Su100146 Su101046 Su110046 Su200046 Sv000046 Sv000146 " "Sv000246 Sv001046 Sv001146 Sv002046 Sv010046 Sv010146 Sv011046 Sv020046 " "Sv100046 Sv100146 Sv101038 Sv110046 Sv200046 Sw000046 Sw000146 Sw000246 " "Sw001046 Sw010031 Sw010152 Sw011046 Sw020046 Sw100139 Sw101046 Sw110046 " "Sx000146 Sx000276 Sx001046 Sx002046 Sx010046 Sx010146 Sx011046 Sx020037 " "Sx100146 Sx110046 Sx200046 Ua000046 Ua000146 Ua000246 Ua001046 Ua001146 " "Ua002046 Ua010024 Ua010116 Ua011024 Ua020024 Ua100024 Ua100124 Ua101024 " "Ua110024 Ua200024 Ub000024 Ub000124 Ub000224 Ub001024 Ub001155 Ub002024 " "Ub010024 Ub010124 Ub011024 Ub020024 Ub100024 Ub100124 Ub101024 Ub110024 " "Ub200024 Uc000024 Uc000124 Uc000224 Uc001024 Uc001124 Uc002024 Uc010024 " "Uc010105 Uc011024 Uc020024 Uc100024 Uc100124 Uc101024 Uc110024 Uc200035 " "Ud000124 Ud000212 Ud001024 Ud001124 Ud002035 Ud010015 Ud010124 Ud011024 " "Ud020019 Ud100124 Ud101038 Ud110024 Ud200038 Ue000024 Ue000124 Ue000224 " "Ue001024 Ue001138 Ue002035 Ue010024 Ue010145 Ue011024 Ue020024 Ue100024 " "Ue100124 Ue101024 Ue110024 Ue200024 Uf000024 Uf000164 Uf000248 Uf001024 " "Uf001124 Uf002024 Uf010024 Uf010124 Uf011024 Uf020024 Uf100024 Uf100124 " "Uf101024 Uf110024 Uf200035 Ug000024 Ug000124 Ug000224 Ug001024 Ug001124 " "Ug002024 Ug010047 Ug010147 Ug011047 Ug020047 Ug100047 Ug100147 Ug101047 " "Ug110047 Ug200047 Uh000047 Uh000147 Uh000236 Uh001060 Uh001160 Uh002060 " "Uh010012 Uh010112 Uh011012 Uh020018 Uh100042 Uh100112 Uh101038 Uh110012 " "Uh200012 Ui000006 Ui000126 Ui000212 Ui001012 Ui001158 Ui002002 Ui010012 " "Ui010166 Ui011012 Ui020065 Ui100012 Ui100112 Ui101012 Ui110012 Ui200007 " "Uj000032 Uj000112 Uj000236 Uj001012 Uj001112 Uj002012 Uj010012 Uj010112 " "Uj011012 Uj020012 Uj100012 Uj100112 Uj110012 Uj200012 Uk000012 Uk000112 " "Uk000212 Uk001012 Uk001112 Uk002012 Uk010012 Uk010112 Uk011012 Uk020005 " "Uk100012 Uk100112 Uk101012 Uk110012 Uk200012 Ul000012 Ul000112 Ul000212 " "Ul001012 Ul001112 Ul002012 Ul010012 Ul010112 Ul011012 Ul020012 Ul100012 " "Ul100112 Ul101038 Ul110012 Ul200012 Um000012 Um000112 Um000212 Um001001 " "Um001138 Um002006 Um010001 Um010129 Um011001 Um020001 Um100038 Um100138 " "Um101001 Um110031 Un000053 Un000131 Un000227 Un001031 Un001159 Un002031 " "Un010031 Un010131 Un011031 Un020011 Un100042 Un100131 Un101038 Un110031 " "Un200031 Uo000031 Uo000131 Uo000231 Uo001013 Uo001113 Uo002013 Uo010040 " "Uo010168 Uo011040 Uo020040 Uo100040 Uo100140 Uo101040 Uo110023 Uo200023 " "Up000023 Up000123 Up000223 Up001023 Up001164 Up002023 Up010023 Up010123 " "Up011023 Up020023 Up100023 Up100123 Up101023 Up110023 Up200023 Uq000023 " "Uq000123 Uq000223 Uq001023 Uq001123 Uq002023 Uq010023 Uq010120 Uq011023 " "Uq020023 Uq100023 Uq100123 Uq101023 Uq110023 Uq200021 Ur000029 Ur000123 " "Ur000232 Ur001023 Ur001123 Ur002014 Ur010011 Ur010123 Ur011023 Ur020022 " "Ur100057 Ur100123 Ur101079 Ur110023 Ur200052 Us000023 Us000123 Us000223 " "Us001023 Us001135 Us002035 Us010023 Us010144 Us011023 Us020023 Us100023 " "Us100123 Us101023 Us110023 Us200023 Ut000023 Ut000180 Ut000248 Ut001071 " "Ut001171 Ut002071 Ut010067 Ut010180 Ut011044 Ut020044 Ut100044 Ut100144 " "Ut101044 Ut110040 Ut200035 Uu000076 Uu000177 Uu000272 Uu001168 Uu002042 " "Uu010042 Uu010161 Uu011061 Uu020037 Uu100071 Uu100172 Uu101048 Uu110057 " "Uu200053 Uv000053 Uv000153 Uv000204 Uv001031 Uv001131 Uv002021 Uv010031 " "Uv010131 Uv011031 Uv020049 Uv100049 Uv100131 Uv101028 Uv110072 Uv200037 " "Uw000065 Uw000161 Uw000237 Uw001037 Uw001174 Uw002035 Uw010037 Uw010126 " "Uw011037 Uw020077 Uw100037 Uw100137 Uw101037 Uw110037 Uw200050 Ux000068 " "Ux000137 Ux001037 Ux001137 Ux002037 Ux010037 Ux010137 Ux011037 Ux020037 " "Ux100037 Ux100137 Ux101024 Ux110070 Ux200070 Ea000054 Ea000154 Ea000215 " "Ea001015 Ea001115 Ea002015 Ea010015 Ea010115 Ea011015 Ea100033 Ea100133 " "Ea101030 Ea110060 Ea200060 Eb000060 Eb000160 Eb000260 Eb001029 Eb001129 " "Eb002029 Eb010029 Eb010129 Eb011029 Eb020029 Eb100029 Eb100129 Eb110029 " "Eb200029 Ec000029 Ec000129 Ec000229 Ec001029 Ec010029 Ec011029 Ec020029 " "Ec101029 Ec110029 Ed000125 Ed001029 Ed002061 Ed010058 Ed010151 Ed011066 " "Ed100151 Ed110002 Ed200019 Ee000019 Ee000119 Ee000219 Ee001019 Ee001119 " "Ee002019 Ee010019 Ee011019 Ee020019 Ee100019 Ee100119 Ee101019 Ee110019 " "Ee200019 Ef000020 Ef000120 Ef000220 Ef001020 Ef002020 Ef010018 Ef010118 " "Ef011018 Ef020001 Ef100001 Ef100101 Ef101001 Ef110001 Ef200001 Eg000063 " "Eg000146 Eg000214 Eg001075 Eg001175 Eg002022 Eg010008 Eg010115 Eg011008 " "Eg020040 Eg100016 Eg100163 Eg101048 Eg110048 Eg200015 Eh000035 Eh000157 " "Eh000215 Eh001061 Eh001109 Eh002035 Eh010035 Eh010174 Eh011068 Eh020015 " "Eh100015 Eh100108 Eh101015 Eh110012 Eh200015 Ei000012 Ei000112 Ei000212 " "Ei001012 Ei001135 Ei002024 Ei010012 Ei010115 Ei011012 Ei020012 Ei100012 " "Ei100112 Ei101012 Ei110012 Ei200012 Ej000012 Ej000112 Ej000211 Ej001012 " "Ej001112 Ej002012 Ej010067 Ej010167 Ej011067 Ej020067 Ej100067 Ej100167 " "Ej101067 Ej110067 Ej200015 Ek000067 Ek000167 Ek000267 Ek001067 Ek001167 " "Ek002067 Ek010067 Ek010167 Ek011067 Ek020067 Ek100067 Ek100167 Ek101067 " "Ek110067 Ek200067 El000067 El000167 El000235 El001045 El001145 El002045 " "El010008 El010104 El011004 El020070 El100035 El100104 El101035 El110004 " "El200004 Em000035 Em000135 Em000246 Em001046 Em001135 Em002035 Em010019 " "Em010135 Em011019 Em020035 Em100012 Em100130 Em101075 Em110076 Em200035 " "En000035 En000120 En000235 En001023 En001120 En002017 En010057 En010128 " "En011079 En020057 En100052 En100180 En101035 En110051 En200005 Eo000005 " "Eo000105 Eo000205 Eo001005 Eo001105 Eo002005 Eo010005 Eo010105 Eo011005 " "Eo020035 Eo100005 Eo100105 Eo101005 Eo110040 Eo200040 Ep000040 Ep000140 " "Ep000240 Ep001040 Ep001140 Ep002040 Ep010040 Ep010140 Ep011040 Ep020040 " "Ep100040 Ep100145 Ep101038 Ep110045 Ep200045 Eq000024 Eq000113 Eq000215 " "Eq001034 Eq001180 Eq002014 Eq010017 Eq010140 Eq011008 Eq020046 Eq100001 " "Eq100120 Eq101075 Eq110029 Eq200033 Er000043 Er000129 Er000271 Er001029 " "Er001169 Er002036 Er010036 Er010136 Er011036 Er020042 Er100043 Er100136 " "Er101046 Er110036 Er200052 Es000052 Es000152 Es000252 Es001016 Es001116 " "Es002035 Es010035 Es010138 Es011035 Es020035 Es100065 Es100165 Es101065 " "Es110065 Es200067 Et000025 Et000147 Et000280 Et001022 Et001138 Et002027 " "Et010003 Et010124 Et011005 Et020022 Et100030 Et100157 Et101010 Et110071 " "Et200017 Eu000017 Eu000117 Eu000217 Eu001017 Eu001117 Eu002011 Eu010011 " "Eu010135 Eu011011 Eu020019 Eu100010 Eu100156 Eu101045 Eu110064 Eu200035 " "Ev000039 Ev000164 Ev000220 Ev001064 Ev001164 Ev002056 Ev010061 Ev010164 " "Ev011078 Ev020045 Ev100005 Ev100117 Ev101060 Ev110017 Ev200016 Ew000012 " "Ew000132 Ew000275 Ew001066 Ew001141 Ew002035 Ew010007 Ew010116 Ew011014 " "Ew020006 Ew100031 Ew100151 Ew101062 Ew110046 Ew200047 Ex000047 Ex000134 " "Ex000252 Ex001040 Ex001142 Ex002042 Ex010023 Ex010106 Ex011076 Ex020016 " "Ex100052 Ex100148 Ex101048 Ex110014 Ex200047 " ) def cibles81(): M2 = prod81(MAN2_81, MAN2_81) sg = somme81((1, UN81), (2, el81((2, 0, 0, 2)))) # 1 + 2 Lam_2 acts by 1 + 2**(w+1) = s xi_s = somme81((1, M2), (-1, prod81(sg, sg))) # T_2 o T_2 - s**2 xi_4 = somme81((1, M2), (9, MAN2_81)) # T_2 o T_2 + 9 T_2 return xi_s, xi_4 def controle_taylor(): """the coord_kappa formula reproduces the direct substitution, modulo 81""" essais = [(4, 3, 6, 7), (7, 0, 3, 1), (1, 6, 0, 4), (79, 3, 78, 1), (10, 9, 3, 73), (25, 78, 9, 13)] for k in essais: cf = coord_kappa(k) for i in range(7): for j in range(7): direct = image_monome(i + j, i, k[0], k[1], k[2], k[3]) formule = [0] * (i + j + 1) for (dl, A, B), v in cf.items(): e = i + dl if 0 <= e <= i + j: formule[e] += v * comb(i, A) * comb(j, B) if any((direct[e] - formule[e]) % M81 for e in range(i + j + 1)): return False return True CERTIFICATS = [('k == 4 (mod 6), w == 2 (mod 3) : T_2 o T_2 + 9 T_2', 'K4', 2), ('k == 2 (mod 6), w == 0 (mod 3) : T_2 o T_2 - s**2', 'S0', 0), ('k == 0 (mod 6), w == 1 (mod 3) : T_2 o T_2 - s**2', 'S1', 1)] def partie_E(): dire('') dire('Part E: proof of Theorem K (Lemmas 7 and 8), valid for every weight') ok_t = controle_taylor() dire(' internal check: expansion of sigma_kappa modulo 81 agrees with the substitution: %s' % ('yes' if ok_t else 'NO')) xi_s, xi_4 = cibles81() textes = {'K4': CERT_K4, 'S0': CERT_S0, 'S1': CERT_S1} ok_tout = ok_t restes = {} for nom, code, r in CERTIFICATS: t1 = time.time() zeta, nt = zeta_certificat(textes[code]) cible = xi_4 if code == 'K4' else xi_s reste = somme81((1, cible), (-1, zeta)) restes[code] = (reste, r) ok, nb = critere_nul(reste, r) temoin = not critere_nul(cible, r)[0] dire(' %s' % nom) dire(' %d terms; remainder j = target - zeta: %d matrices, %d blocks; criterion of Lemma 7: %s' % (nt, len(reste), nb, 'VERIFIED' if ok else 'FAILED')) dire(' witness: the target alone does not satisfy the criterion: %s (%.1f s)' % ('yes' if temoin else 'NO', time.time() - t1)) ok_tout = ok_tout and ok and temoin return ok_tout, restes def action_directe(X, f, w): """coefficients of sum_g c_g F(a x + c y, b x + d y) modulo 81, F = sum f_i x**i y**(w-i)""" tot = [0] * (w + 1) for g, cg in X.items(): a, b, c, d = g vp = [[1] + [0] * w] for m in range(1, w + 1): p = vp[-1] vp.append([(d * p[0]) % M81] + [(b * p[e - 1] + d * p[e]) % M81 for e in range(1, w + 1)]) R = [f[w] % M81] + [0] * w for i in range(w - 1, -1, -1): V = vp[w - i] fi = f[i] R = [(c * R[0] + fi * V[0]) % M81] + [(a * R[e - 1] + c * R[e] + fi * V[e]) % M81 for e in range(1, w + 1)] for e in range(w + 1): tot[e] = (tot[e] + cg * R[e]) % M81 return tot def partie_G(restes): dire('') dire('Part G: direct check, action of the remainder j on the forms of degree w <= %d' % W_G_MAX) ok_tout = True for nom, code, r in CERTIFICATS: reste, r = restes[code] temoins = [w for w in range(W_G_MAX - 5, W_G_MAX + 1) if w % 2 == 0 and w % 3 != r] for w in range(2, W_G_MAX + 1, 2): if w % 3 == r or w in temoins: f = [(7 * i * i + 3 * i + 5) % M81 for i in range(w + 1)] t1 = time.time() nul = not any(action_directe(reste, f, w)) attendu = (w % 3 == r) if attendu: ok_tout = ok_tout and nul dire(' %s w=%2d (w mod 3 = %d): j acts by 0: %s %s (%.1f s)' % (code, w, w % 3, 'yes' if nul else 'no', '(expected: yes)' if attendu else '(out-of-class witness)', time.time() - t1)) if time.time() - T0 > BUDGET: dire(' budget reached') return ok_tout return ok_tout # ============================================================================= # Self-test # ============================================================================= def auto_test(): if pow(2, 11) != 2048 or comb(10, 3) != 120 or v3(252) != 2: return False for n in range(1, 40, 2): # 2**n == -1 + 3n (mod 9), n odd if (pow(2, n) - (-1 + 3 * n)) % 9: return False base = reseau_hatada(10) if len(base) != 1: return False m = base[0] if [m[j] for j in range(1, 10, 2)] not in ([48, -25, 20, -25, 48], [-48, 25, -20, 25, -48]): return False t = applique(matrice_T2(10), m) if not all(t[j] == -24 * m[j] for j in range(11)): return False return len(REPS24) == 24 and len(CLASSE) == 48 dire('=' * 76) dire('VERIF_A2: T_2 on the Hatada lattice, modulo 27 and modulo 81') dire('Budget %.0f s; Part B: k <= %d; Parts C, D: k <= %d; Part G: w <= %d' % (BUDGET, KMAX_B, KMAX_C, W_G_MAX)) dire('=' * 76) if not auto_test(): dire('SELF-TEST FAILED: stop (environment not as expected).') sys.exit(1) dire('Self-test: OK (period of Delta, tau(2) = -24, 2**n == -1+3n mod 9, 24 classes).') rA = partie_A() rE, restes = partie_E() rB = partie_B() rCD = partie_CD() if PARTIE_C else True rG = partie_G(restes) if PARTIE_G else True dire('') dire('SUMMARY: Part A %s, Part E (proof of Theorem K) %s, Part B %s, Parts C-D %s, Part G %s' % ('OK' if rA else 'FAILED', 'OK' if rE else 'FAILED', 'OK' if rB else 'FAILED', 'OK' if rCD else 'FAILED', 'OK' if rG else 'FAILED')) dire('Total time: %.1f s' % (time.time() - T0))