# -*- coding: utf-8 -*- # ============================================================================= # verif_all.py -- verification de TOUTE la chaine de la note # "Old and new Drinfeld cusp forms of level t in characteristic 2: # the weights k = 2^m + 1" (D. Niedbala Giraudin) # Python pur + numpy. Ni Sage, ni scipy. Lancer par double-clic. # Aucun parametre a taper : les bornes sont fixees ci-dessous. # Aucun operateur circonflexe : XOR par operator.xor / np.bitwise_xor. # Duree prevue : environ une minute. Memoire : quelques Mo. # ============================================================================= import sys, time, operator from math import comb import numpy as np XOR = operator.xor M_ALG = 9 # blocs algebriques sur F_2 : m = 1 .. M_ALG (n = 512 au plus) M_POLY = 5 # polynomes caracteristiques sur F_2[t] : m = 2 .. M_POLY N_COUPL = 16 # comptage direct des couplages parfaits : N = 0 .. N_COUPL N_TROIS = 160 # observation sur les poids voisins : n = 1 .. N_TROIS def say(s): print(s, flush=True) assert XOR(3, 1) == 2 and 2**3 == 8 and 7 // 2 == 3, "auto-test arithmetique" say("[0] auto-test arithmetique : OK") T0 = time.time(); BILAN = [] def note(nom, ok): BILAN.append((nom, ok)); return ok def J(k): return (2**k - (-1)**k) // 3 def mats(m): n = 1 << m p = np.arange(n)[:, None]; q = np.arange(n)[None, :] U = (np.bitwise_and(p, q) == p).astype(np.uint8) V = U.T.copy() T = (np.bitwise_and(p, q) == 0).astype(np.uint8) Pi = np.zeros((n, n), np.uint8); Pi[np.arange(n), (n - 1) - np.arange(n)] = 1 return n, U, V, T, Pi, np.eye(n, dtype=np.uint8) def mul(*X): R = X[0].astype(np.int64) for Y in X[1:]: R = (R @ Y.astype(np.int64)) % 2 return R.astype(np.uint8) def add(*X): R = X[0].copy() for Y in X[1:]: R = np.bitwise_xor(R, Y) return R def rang(A): A = (A % 2).astype(np.uint8).copy(); r = 0; R, C = A.shape for c in range(C): if r == R: break piv = np.nonzero(A[r:, c])[0] if len(piv) == 0: continue i = r + piv[0] if i != r: A[[r, i]] = A[[i, r]] rows = np.nonzero(A[:, c])[0]; rows = rows[rows != r] A[rows] = np.bitwise_xor(A[rows], A[r]); r += 1 return r def noyau(A): # base du noyau a droite sur F_2 A = (A % 2).astype(np.uint8).copy(); R, C = A.shape; piv = []; r = 0 for c in range(C): if r == R: break p = np.nonzero(A[r:, c])[0] if len(p) == 0: continue i = r + p[0] if i != r: A[[r, i]] = A[[i, r]] rows = np.nonzero(A[:, c])[0]; rows = rows[rows != r] A[rows] = np.bitwise_xor(A[rows], A[r]); piv.append(c); r += 1 libres = [c for c in range(C) if c not in piv]; B = [] for f in libres: v = np.zeros(C, np.uint8); v[f] = 1 for i, c in enumerate(piv): if A[i, f]: v[c] = 1 B.append(v) return np.array(B, dtype=np.uint8).reshape(len(B), C) def M_formule11(n): # Bandini-Valentino, formule (11), q = 2, j = 0 A = np.zeros((n, n), np.uint8) for a in range(1, n + 1): for b in range(1, n + 1): if a == b: A[a-1, b-1] = comb(n-a, a-1) % 2 if 0 <= a-1 <= n-a else 0 else: x = comb(n-a, n-b) % 2 if 0 <= n-b <= n-a else 0 y = comb(n-a, b-1) % 2 if 0 <= b-1 <= n-a else 0 A[a-1, b-1] = (x + y) % 2 return A # --------------------------------------------------------------------------- say("\n[1] Section 2 : identification de M, structure de groupe, identites") for m in range(1, M_ALG + 1): n, U, V, T, Pi, I = mats(m); M = add(I, T, U); S = add(T, U, V) c = [] if m <= 6: c.append(np.array_equal(M, M_formule11(n))) # M = formule (11) c.append(np.array_equal(mul(U, U), I) and np.array_equal(mul(V, V), I)) c.append(np.array_equal(T, mul(V, U)) and np.array_equal(mul(T, T, T), I)) c.append(np.array_equal(mul(Pi, U, Pi), V) and np.array_equal(mul(U, Pi), T)) c.append(np.array_equal(mul(M, M, M), M) and np.array_equal(mul(M, M), mul(Pi, M))) c.append(np.array_equal(S, S.T) and np.array_equal(M, mul(V, S))) c.append(all(V[p, p] == 1 for p in range(n)) and not np.triu(V, 1).any()) c.append(np.array_equal(np.diag(S), (np.arange(n) == 0).astype(np.uint8))) note("Sec.2 m=%d" % m, all(c)) say(" m=%d n=%4d : %s" % (m, n, "OK" if all(c) else "ECHEC " + str(c))) # --------------------------------------------------------------------------- say("\n[2] Proposition 3.1 (cas dyadique) : reduction de rang et Clebsch-Gordan") for m in range(1, M_ALG): n, U, V, T, Pi, I = mats(m); S = add(T, U, V) n2, U2, V2, T2, P2, I2 = mats(m + 1); S2 = add(T2, U2, V2) X = mul(Pi, add(I, U), add(I, Pi)) c1 = np.array_equal(np.block([[S, add(T, U)], [add(T, V), add(U, V)]]), S2) c2 = np.array_equal(X, add(I, V, mul(T, T), Pi)) # X = 1+V+T^2+Pi c3 = rang(S2) == n + rang(X) # Lemme 3.2 fixUPi = n - rang(np.vstack([add(I, U), add(I, Pi)])) c4 = rang(X) == n // 2 - fixUPi fixT = n - rang(add(I, T)) c5 = (fixT == 2 * J(m - 1)) and (fixUPi == J(m - 1)) c6 = (rang(S) == J(m + 1)) and (rang(S2) == J(m + 2)) ok = c1 and c2 and c3 and c4 and c5 and c6 note("Prop3.1 m=%d" % m, ok) say(" m=%d : bloc %s, X=1+V+T2+Pi %s, rg S_{m+1}=2^m+rg X %s, rg X=2^{m-1}-dimFix %s, dimFix(T)=2J_{m-1} %s, rg S=J_{m+1} %s" % (m, c1, c2, c3, c4, c5, c6)) # --------------------------------------------------------------------------- say("\n[3] Theoreme 3.2 : ker(S_m) inter W_{J_{m+1}} = 0, et la descente") for m in range(0, M_ALG + 1): n = 1 << m; Jm1 = J(m + 1) if m == 0: ok = True else: n_, U, V, T, Pi, I = mats(m); S = add(T, U, V) K = noyau(S) ok = rang(K[:, Jm1:]) == len(K) if len(K) else True # aucun vecteur du noyau porte par [0,J_{m+1}) note("Thm3.2 m=%d" % m, ok) say(" m=%d : %s" % (m, "OK" if ok else "ECHEC")) for m in range(2, M_ALG + 1): # isomorphisme de l'etape 3 : Fix(S_3) niveau n -> ker S niveau n-1 nlev = m - 1; n, U, V, T, Pi, I = mats(nlev); h = n // 2 F = noyau(np.vstack([add(I, U), add(I, Pi)])) ok = True if nlev >= 1: n1, U1, V1, T1, P1, I1 = mats(nlev - 1); S1 = add(T1, U1, V1) A_ = F[:, :h] ok = (not mul(A_, S1.T).any()) and rang(A_) == len(F) == (n1 - rang(S1)) note("etape3 n=%d" % nlev, ok) say(" etape 3 (restriction Fix(S_3)_n -> ker S_{n-1}, injective, dimensions egales) : %s" % all(ok for nm, ok in BILAN if nm.startswith("etape3"))) # --------------------------------------------------------------------------- say("\n[4] Corollaire 3.3 : corang S[0:i] = dist(i, Jacobsthal)") Js = [J(r) for r in range(0, 2 * M_ALG + 6)] n, U, V, T, Pi, I = mats(M_ALG); S = add(T, U, V) ok = all((i - rang(S[:i, :i])) == min(abs(i - x) for x in Js) for i in range(1, n + 1)) note("Cor3.3", ok); say(" i = 1 .. %d : %s" % (n, "OK" if ok else "ECHEC")) say("\n[5] Remarque 3.4 : couplages parfaits du graphe disjoint-ou-emboite") def couplages_mod2(N): if N % 2: return 0 adj = {a: set(b for b in range(1, N + 1) if b != a and (a & b in (0, a, b))) for a in range(1, N + 1)} memo = {} def rec(rest): if not rest: return 1 if rest in memo: return memo[rest] a = rest[0]; s = 0 for i in range(1, len(rest)): if rest[i] in adj[a]: s += rec(rest[1:i] + rest[i+1:]) memo[rest] = s; return s return rec(tuple(range(1, N + 1))) % 2 ok = all((couplages_mod2(N) == 1) == ((N + 1) in Js) for N in range(0, N_COUPL + 1)) note("Rem3.4", ok); say(" N = 0 .. %d : %s" % (N_COUPL, "OK" if ok else "ECHEC")) # --------------------------------------------------------------------------- say("\n[6] Section 4 : niveau 1. W_0 = ker(M^T) Pi-invariant, miroir, Theoreme 4.3") for m in range(1, M_ALG + 1): n, U, V, T, Pi, I = mats(m); M = add(I, T, U); MP = add(M, Pi); Jm = J(m) W0 = noyau(M.T) c1 = rang(np.vstack([W0, mul(W0, Pi)])) == len(W0) == Jm f = lambda i: i - (rang(M[:i, :]) if i else 0) g = lambda i: (n - i) - (rang(M[i:, :]) if i < n else 0) c2 = all(g(i) == f(n - i) for i in range(n + 1)) if m <= 6 else (g(Jm) == f(n - Jm)) c3 = f(J(m + 1)) == 0 and g(Jm) == 0 c4 = np.array_equal(MP, mul(V, add(add(T, U, V), mul(T, T)))) c5 = (not mul(MP, M).any()) and rang(MP) == Jm and rang(M) == J(m + 1) c6 = rang(MP[:Jm, :Jm]) == Jm c7 = np.array_equal(add(I, mul(M, Pi)), MP) # trace T = I + M A = M + Pi ok = c1 and c2 and c3 and c4 and c5 and c6 and c7 note("Sec4 m=%d" % m, ok) say(" m=%d : PiW0=W0 %s, miroir %s, f(J_{m+1})=g(J_m)=0 %s, M+Pi=V(S+T2) %s, ker(M+Pi)=im M %s, det(M+Pi)[0:J_m]!=0 %s, I+M.Pi=M+Pi %s" % (m, c1, c2, c3, c4, c5, c6, c7)) # --------------------------------------------------------------------------- say("\n[7] Theoreme principal : polynomes caracteristiques exacts sur F_2[t]") def pmul(a, b): r = 0 while a: if a & 1: r = XOR(r, b) a >>= 1; b <<= 1 return r def val(a): return None if a == 0 else (a & -a).bit_length() - 1 def charpoly(W, n): p = [1] for r in range(1, n + 1): a = W[r-1][r-1]; Rw = [W[r-1][j] for j in range(r-1)]; C = [W[i][r-1] for i in range(r-1)] col = [1, a]; vec = C[:] for _ in range(r - 1): s = 0 for j in range(r - 1): s = XOR(s, pmul(Rw[j], vec[j])) col.append(s); nv = [0] * (r - 1) for i in range(r - 1): acc = 0 for j in range(r - 1): if W[i][j]: acc = XOR(acc, pmul(W[i][j], vec[j])) nv[i] = acc vec = nv newp = [0] * (r + 1) for i in range(r + 1): s = 0 for j in range(min(i, r - 1) + 1): if i - j < len(col) and col[i-j] and p[j]: s = XOR(s, pmul(col[i-j], p[j])) newp[i] = s p = newp return p def polmul(A, B): C = [0] * (len(A) + len(B) - 1) for i, a in enumerate(A): for j, b in enumerate(B): if a and b: C[i+j] = XOR(C[i+j], pmul(a, b)) return C def hull(pts): H = [] for P in pts: while len(H) >= 2: (x1, y1), (x2, y2) = H[-2], H[-1]; x3, y3 = P if (x2-x1)*(y3-y1) - (y2-y1)*(x3-x1) <= 0: H.pop() else: break H.append(P) return H def pentes(E): nz = max(j for j in range(len(E)) if E[j]) H = hull([(j, val(E[j])) for j in range(nz + 1) if E[j]]) out = [] for a in range(len(H) - 1): dy = H[a+1][1] - H[a][1]; dx = H[a+1][0] - H[a][0]; g_ = np.gcd(dy, dx) out.append(("%d/%d" % (dy // g_, dx // g_)) if dx // g_ != 1 else "%d" % (dy // g_)) out[-1] += "(x%d)" % dx return H, out PREV = None BILAN_R56 = [] for m in range(2, M_POLY + 1): t0 = time.time() n, U, V, T, Pi, I = mats(m); M = add(I, T, U); MP = add(M, Pi); Jm = J(m); k = n + 1 EU = charpoly([[int(M[i][j]) << (j + 1) for j in range(n)] for i in range(n)], n) ET = charpoly([[int(MP[i][j]) << (j + 1) for j in range(n)] for i in range(n)], n) Tt = ET[:Jm + 1] c1 = all(ET[j] == 0 for j in range(Jm + 1, n + 1)) and val(Tt[Jm]) == Jm * (Jm + 1) // 2 HT, sT = pentes(Tt) c2 = all(2 * (HT[a+1][1] - HT[a][1]) <= 2 * Jm * (HT[a+1][0] - HT[a][0]) for a in range(len(HT) - 1)) and 2 * Jm < k F = [1] for _ in range(J(m - 1)): F = polmul(F, [1, 0, 1 << k]) # (X^2 + t^k)^{J_{m-1}} c3 = EU == polmul(Tt, F) + [0] * Jm # char U = X^{J_m} char(T_t) F HU, sU = pentes(EU) c4 = sU[-1] == "%d/2(x%d)" % (k, 2 * J(m - 1)) and all(2 * (HU[a+1][1] - HU[a][1]) < k * (HU[a+1][0] - HU[a][0]) for a in range(len(HU) - 2)) ok = c1 and c2 and c3 and c4 note("Thm m=%d" % m, ok) co = [Tt[Jm - d] for d in range(Jm + 1)] imp = [co[d] for d in range(1, Jm + 1, 2)]; pai = [co[d] for d in range(0, Jm + 1, 2)] c5 = Tt[1] == 2 and len(imp) == len(pai) and all(pmul(2, imp[i]) == pai[i] for i in range(len(imp))) if m == M_POLY: note("Rem5.6", all(BILAN_R56 + [c5])) else: BILAN_R56.append(c5) say(" m=%d k=%d : v(det T_t)=J_m(J_m+1)/2 %s ; pentes T_t <= J_m=%d < k/2 %s ; char U_t = X^J_m char(T_t)(X^2+t^k)^J_{m-1} %s ; derniere pente k/2 de mult 2J_{m-1}, autres < k/2 %s [%.1fs]" % (m, k, c1, Jm, c2, c3, c4, time.time() - t0)) say(" [observation] char(T_t) = (X + t) Q(X^2) : %s" % c5) say(" pentes de T_t (niveau 1) : %s" % " ".join(sT)) say(" pentes de U_t (niveau t) : %s" % " ".join(sU)) if PREV is not None: same = (" ".join(sT) == PREV) say(" [observation, non demontree] pentes de T_t au poids 2^m+1 == pentes de U_t au poids 2^{m-1}+1 : %s" % same) PREV = " ".join(sU) # --------------------------------------------------------------------------- say("\n[8] Remarque : le critere du mineur de tete hors de la tour (observation)") reussis = [] for n in range(1, N_TROIS + 1): M = M_formule11(n); Pi = np.eye(n, dtype=np.uint8)[::-1]; MP = add(M, Pi); r = rang(MP) if (r == 0 or rang(MP[:r, :r]) == r) and 2 * r < n + 1: reussis.append(n) attendu = sorted(set(x for e in range(1, 9) for x in (2**e - 1, 2**e, 2**e + 1) if 1 <= x <= N_TROIS)) ok = reussis == attendu note("Rem n<=%d" % N_TROIS, ok) say(" le critere tient exactement pour n = %s" % reussis) say(" (= les n de la forme 2^e - 1, 2^e, 2^e + 1 : %s)" % ok) # --------------------------------------------------------------------------- say("\n" + "=" * 72) nb_ok = sum(1 for _, o in BILAN if o) say(" RECAPITULATIF : %d controles sur %d au vert (%.0f s)" % (nb_ok, len(BILAN), time.time() - T0)) for nm, o in BILAN: if not o: say(" ECHEC : " + nm) say(" " + ("TOUT EST VERT" if nb_ok == len(BILAN) else "AU MOINS UN CONTROLE A ECHOUE")) say("=" * 72) try: input("Appuyez sur Entree pour fermer...") except Exception: pass