# -*- coding: ascii -*- # CHAINES_pLC_B12.py # Verification arithmetique, disjointe de l'automate de VERIF_pLC_B12.py, des listes de # discriminants obstruants pour sup_{k>=0} B(2**k alpha) <= C, C = 1..11. # Python pur. Aucune dependance externe (ni numpy ni scipy). Aucun fichier intermediaire. # Aucun caractere de disjonction binaire dans ce fichier ; les puissances s'ecrivent **. # Parametres FIXES ci-dessous : lancer sans argument (double-clic ou bouton Executer). # # David Niedbala Giraudin, ORCID 0009-0009-1526-1178 # Technical assistance: Claude (Anthropic) # # Principe. Pour une forme primitive (a,b,c) de discriminant D, de racine # beta = (-b + sqrt D)/(2a), les nombres beta/2 et (beta+1)/2 sont racines des formes # (4a, 2b, c) et (4a, 2b-4a, a-b+c), divisees par leur contenu. La chaine descendante garde # a chaque pas l'enfant de discriminant D (unique apres le premier pas). Le long de la chaine on note le maximum des # quotients partiels PERIODIQUES (B est une limite superieure). m(D) = minimum sur les classes. # # Partie A : pour tout D = 1 mod 8 non carre, D <= DMAX, on calcule m(D) et on compare # {D : m(D) <= C} aux discriminants impairs <= DMAX des noyaux (listes ci-dessous, # imprimees par VERIF_pLC_B12.py). Accord exact = verification dans les deux sens. # Partie B : pour les discriminants impairs > DMAX des noyaux, la chaine part de la classe # d'un mot de cycle du noyau ; on verifie qu'elle se ferme et que son maximum est # exactement le plus petit C ou le discriminant apparait. # Partie C : ordre de [p_2] (periode de la suite des classes le long de la chaine), C = 8. from math import gcd, isqrt import time # ----------------------------------------------------------------------------- PARAMETRES DMAX = 100000 # borne de la partie A CMAX = 11 # niveaux compares PAS = 60 # nombre de demi-pas de chaque chaine (les ordres observes sont <= 6) # ----------------------------------------------------------------------------- # discriminants impairs des noyaux K_{N(C)} (sortie de VERIF_pLC_B12.py avec MAX_C = 11) NOYAU = { 1: [], 2: [], 3: [17], 4: [17], 5: [17, 33, 41], 6: [17, 33, 41, 1241], 7: [17, 33, 41, 57, 65, 73, 561, 1241, 1649, 2993, 7913], 8: [17, 33, 41, 57, 65, 73, 561, 697, 1241, 1649, 1881, 2993, 3977, 4097, 4257, 7913, 9425, 29993, 52849], 9: [17, 33, 41, 57, 65, 73, 89, 97, 105, 113, 561, 697, 969, 1241, 1649, 1881, 2409, 2465, 2993, 3977, 4097, 4257, 7353, 7913, 8217, 9425, 17177, 17225, 27233, 29801, 29993, 49601, 52849, 82337, 155513, 175593, 223737, 1042457, 2555553, 1625460497], 10: [17, 33, 41, 57, 65, 73, 89, 97, 105, 113, 561, 697, 969, 1105, 1241, 1649, 1881, 2409, 2465, 2993, 3201, 3281, 3977, 4097, 4257, 5945, 6273, 6497, 7353, 7913, 8217, 9425, 9673, 10081, 13737, 13817, 15665, 17177, 17225, 21641, 27233, 29801, 29993, 36993, 46217, 49601, 52849, 62033, 62561, 81209, 82337, 155513, 175593, 223737, 606713, 1042457, 2555553, 4076353, 1625460497], 11: [17, 33, 41, 57, 65, 73, 89, 97, 105, 113, 129, 137, 145, 153, 161, 561, 697, 969, 1105, 1241, 1353, 1649, 1881, 2409, 2465, 2993, 3201, 3281, 3465, 3689, 3977, 4097, 4257, 5945, 6273, 6497, 6633, 6953, 7353, 7913, 8217, 9425, 9673, 10081, 11457, 13737, 13817, 15665, 17153, 17177, 17225, 18177, 18737, 21641, 23001, 24153, 27233, 29801, 29993, 36993, 41697, 44897, 45713, 46217, 49601, 52849, 55193, 62033, 62561, 80081, 81209, 82337, 93425, 115433, 116289, 145673, 155513, 175593, 216193, 223737, 263177, 269297, 271697, 606713, 1042457, 1216865, 2555553, 4076353, 16916705, 44125353, 417320009, 1625460497], } # discriminants impairs > DMAX : (D, plus petit C d'apparition, mot de cycle du noyau) GRANDS = [ (115433, 11, [3, 1, 2, 7, 1, 1, 5, 4, 2, 2, 3, 2, 2, 4, 5, 1, 1, 7, 2, 1, 3, 1, 10, 5, 1, 3, 3, 1, 7, 1, 1, 11, 5, 2, 1, 1, 5, 3, 1, 3, 2, 1, 1, 1, 1, 2, 2, 1, 1, 4, 1, 8, 2, 1, 3, 3, 1, 2, 8, 1, 4, 1, 1, 2, 2, 1, 1, 1, 1, 2, 3, 1, 3, 5, 1, 1, 2, 5, 11, 1, 1, 7, 1, 3, 3, 1, 5, 10, 1]), (116289, 11, [3, 10, 1, 2, 1, 7, 5, 2, 1, 2, 3, 1, 1, 2, 5, 2, 1, 1, 3, 2, 1, 2, 5, 7, 1, 2, 1, 10, 3, 1, 6, 1, 4, 1, 1, 1, 2, 3, 2, 2, 3, 5, 1, 1, 2, 2, 1, 1, 11, 5, 1, 3, 1, 5, 11, 1, 1, 2, 2, 1, 1, 5, 3, 2, 2, 3, 2, 1, 1, 1, 4, 1, 6, 1]), (145673, 11, [2, 4, 1, 4, 2, 2, 2, 5, 1, 5, 3, 4, 1, 5, 2, 1, 9, 1, 1, 1, 2, 2, 2, 1, 2, 2, 2, 1, 1, 1, 9, 1, 2, 5, 1, 4, 3, 5, 1, 5, 2, 2, 2, 4, 1, 4, 2, 1, 11, 1, 1, 1, 1, 1, 11, 1]), (155513, 9, [1, 1, 4, 6, 2, 7, 1, 1, 2, 2, 3, 3, 1, 2, 1, 2, 1, 1, 1, 1, 4, 1, 3, 1, 3, 4, 3, 9, 3, 4, 3, 1, 3, 1, 4, 1, 1, 1, 1, 2, 1, 2, 1, 3, 3, 2, 2, 1, 1, 7, 2, 6, 4, 1, 1, 1, 8, 1, 1, 8, 1]), (175593, 9, [1, 9, 4, 1, 3, 3, 3, 2, 7, 2, 8, 2, 4, 4, 4, 3, 1, 2, 1, 1, 6, 1]), (216193, 11, [3, 1, 2, 5, 2, 1, 1, 1, 1, 2, 5, 2, 1, 3, 1, 6, 1, 5, 11, 5, 1, 6, 1]), (223737, 9, [1, 1, 3, 1, 4, 3, 3, 8, 1, 1, 1, 1, 1, 6, 4, 3, 4, 1, 2, 1, 1, 1, 1, 1, 1, 9, 2, 4, 4, 1, 4, 4, 2, 9, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 4, 6, 1, 1, 1, 1, 1, 8, 3, 3, 4, 1, 3, 1, 1, 1, 6, 2, 2, 1, 1, 4, 1, 2, 1, 2, 2, 3, 2, 2, 1, 2, 1, 4, 1, 1, 2, 2, 6, 1]), (263177, 11, [6, 1, 5, 10, 1, 2, 1, 11, 5, 2, 1, 2, 5, 1, 1, 2, 5, 2, 1, 2, 3, 2, 1, 2, 5, 2, 1, 1, 5, 2, 1, 2, 5, 11, 1, 2, 1, 10, 5, 1, 6, 1, 4, 1, 1, 2, 2, 3, 2, 2, 3, 2, 2, 1, 1, 4, 1]), (269297, 11, [5, 8, 1, 1, 1, 2, 9, 2, 2, 2, 2, 1, 4, 5, 3, 4, 11, 1]), (271697, 11, [2, 5, 5, 5, 2, 1, 5, 5, 1, 7, 1, 2, 2, 2, 2, 1, 7, 1, 5, 5, 1]), (606713, 10, [6, 2, 5, 2, 1, 1, 3, 1, 2, 5, 4, 10, 1, 2, 1, 2, 1, 2, 5, 8, 2, 1, 2, 8, 5, 2, 1, 2, 1, 2, 1, 10, 4, 5, 2, 1, 3, 1, 1, 2, 5, 2, 6, 1, 4, 1, 1, 1, 1, 1, 2, 5, 1, 1, 3, 2, 1, 2, 4, 3, 2, 2, 3, 4, 2, 1, 2, 3, 1, 1, 5, 2, 1, 1, 1, 1, 1, 4, 1]), (1042457, 9, [1, 1, 4, 3, 3, 1, 2, 2, 3, 4, 1, 3, 4, 1, 3, 1, 4, 3, 1, 4, 3, 2, 2, 1, 3, 3, 4, 1, 1, 1, 6, 4, 1, 4, 6, 1]), (1216865, 11, [6, 1, 3, 1, 2, 5, 2, 1, 3, 1, 6, 1, 4, 1, 1, 2, 3, 2, 1, 2, 5, 4, 2, 1, 2, 5, 11, 5, 2, 1, 2, 4, 5, 2, 1, 2, 3, 2, 1, 1, 4, 1]), (2555553, 9, [1, 3, 4, 1, 4, 4, 1, 1, 1, 1, 1, 4, 4, 1, 4, 3, 1, 1, 6, 2, 9, 2, 6, 1]), (4076353, 10, [5, 2, 6, 2, 10, 1, 2, 4, 3, 4, 5, 2, 1, 8, 1, 1, 1, 1, 1, 1, 2, 5, 1, 3, 1, 4, 4, 2, 1, 2, 2, 1, 1, 9, 2, 5, 2, 2, 3, 4, 1, 2, 1, 2, 4, 1, 6, 2, 2, 1, 2, 1, 9, 1, 2, 1, 2, 2, 6, 1, 4, 2, 1, 2, 1, 4, 3, 2, 2, 5, 2, 9, 1, 1, 2, 2, 1, 2, 4, 4, 1, 3, 1, 5, 2, 1, 1, 1, 1, 1, 1, 8, 1, 2, 5, 4, 3, 4, 2, 1, 10, 2, 6, 2, 5, 1, 4, 1, 2, 1, 2, 1, 2, 1, 2, 2, 2, 2, 1, 2, 1, 2, 1, 2, 1, 4, 1]), (16916705, 11, [2, 3, 1, 3, 1, 6, 1, 5, 3, 1, 2, 1, 8, 3, 3, 1, 1, 1, 10, 2, 4, 3, 1, 10, 1]), (44125353, 11, [4, 1, 10, 5, 2, 1, 10, 5, 2, 2, 2, 2, 1, 2, 1, 4, 1, 4, 2, 1, 1, 4, 1, 5, 2, 1, 1, 4, 1, 10, 1, 2, 4, 5, 3, 5, 1, 1, 2, 2, 2, 5, 1, 1, 2, 2, 1, 2, 5, 1, 3, 1, 2, 4, 1, 5, 11, 1, 1, 1, 2, 8, 1, 2, 5, 2, 2, 3, 2, 1, 2, 2, 2, 3, 2, 1, 1, 1, 10, 2, 5, 1]), (417320009, 11, [4, 1, 9, 1, 1, 9, 1, 1, 9, 1, 4, 1, 5, 1, 1, 1, 4, 3, 2, 1, 2, 2, 2, 5, 1, 1, 1, 1, 1, 4, 1, 2, 2, 2, 2, 4, 1, 3, 4, 1, 3, 4, 1, 10, 1, 2, 3, 9, 1, 1, 2, 5, 1, 4, 2, 1, 4, 3, 2, 2, 1, 4, 1, 4, 2, 2, 1, 1, 1, 1, 1, 7, 2, 2, 5, 2, 1, 6, 4, 1, 3, 1, 11, 1, 1, 1, 2, 9, 1, 1, 2, 2, 10, 1, 1, 1, 2, 2, 4, 3, 3, 1, 2, 2, 1, 2, 5, 1, 2, 1, 1, 1, 1, 8, 1, 5, 3, 5, 4, 1, 3, 1, 4, 5, 3, 5, 1, 8, 1, 1, 1, 1, 2, 1, 5, 2, 1, 2, 2, 1, 3, 3, 4, 2, 2, 1, 1, 1, 10, 2, 2, 1, 1, 9, 2, 1, 1, 1, 11, 1, 3, 1, 4, 6, 1, 2, 5, 2, 2, 7, 1, 1, 1, 1, 1, 2, 2, 4, 1, 4, 1, 2, 2, 3, 4, 1, 2, 4, 1, 5, 2, 1, 1, 9, 3, 2, 1, 10, 1, 4, 3, 1, 4, 3, 1, 4, 2, 2, 2, 2, 1, 4, 1, 1, 1, 1, 1, 5, 2, 2, 2, 1, 2, 3, 4, 1, 1, 1, 5, 1]), (1625460497, 9, [1, 9, 1, 1, 1, 1, 1, 1, 3, 1, 4, 3, 3, 1, 4, 3, 4, 8, 1, 1, 1, 1, 1, 7, 1, 1, 1, 1, 1, 8, 4, 3, 4, 1, 3, 3, 4, 1, 3, 1, 1, 1, 1, 1, 1, 9, 1, 1, 6, 2, 2, 1, 1, 4, 4, 1, 4, 3, 1, 2, 1, 2, 2, 3, 2, 9, 1, 1, 1, 1, 1, 2, 1, 2, 1, 4, 1, 1, 2, 1, 4, 3, 4, 2, 6, 1, 1, 1, 3, 1, 2, 2, 6, 2, 4, 3, 3, 8, 2, 2, 1, 2, 1, 2, 1, 1, 1, 1, 1, 6, 4, 4, 1, 2, 1, 2, 1, 3, 4, 1, 2, 1, 1, 1, 1, 1, 1, 1, 6, 2, 7, 2, 2, 1, 3, 4, 3, 3, 4, 3, 1, 2, 2, 7, 2, 6, 1, 1, 1, 1, 1, 1, 1, 2, 1, 4, 3, 1, 2, 1, 2, 1, 4, 4, 6, 1, 1, 1, 1, 1, 2, 1, 2, 1, 2, 2, 8, 3, 3, 4, 2, 6, 2, 2, 1, 3, 1, 1, 1, 6, 2, 4, 3, 4, 1, 2, 1, 1, 4, 1, 2, 1, 2, 1, 1, 1, 1, 1, 9, 2, 3, 2, 2, 1, 2, 1, 3, 4, 1, 4, 4, 1, 1, 2, 2, 6, 1]), ] ORDRES_C8 = {65: 2, 697: 3, 2993: 3, 4097: 5, 4257: 3, 9425: 2} # les 13 autres : 1 def pq_max_periodique(a, b, c, D): P, Q = -b, 2 * a r = isqrt(D) vus = {} suite = [] while (P, Q) not in vus: vus[(P, Q)] = len(suite) if Q > 0: q = (P + r) // Q else: q = -((P + r) // (-Q) + 1) suite.append(q) P = q * Q - P Q = (D - P * P) // Q return max(suite[vus[(P, Q)]:]) def cle_classe(a, b, c, D): P, Q = -b, 2 * a r = isqrt(D) vus = {} suite = [] while (P, Q) not in vus: vus[(P, Q)] = len(suite) suite.append((P, Q)) if Q > 0: q = (P + r) // Q else: q = -((P + r) // (-Q) + 1) P = q * Q - P Q = (D - P * P) // Q return min(suite[vus[(P, Q)]:]) def primitive(a, b, c): g = gcd(gcd(abs(a), abs(b)), abs(c)) return (a // g, b // g, c // g) def disc(f): return f[1] * f[1] - 4 * f[0] * f[2] def enfants(f, D): a, b, c = f return [g for g in (primitive(4 * a, 2 * b, c), primitive(4 * a, 2 * b - 4 * a, a - b + c)) if disc(g) == D] def enfant(f, D, premier): # Parmi beta/2, (beta+1)/2 et 2 beta, exactement deux ont le discriminant D (2 decompose). # Apres le premier pas, 2 beta (le parent, a une translation pres) est l'un d'eux : l'enfant # est alors unique. Au premier pas les deux enfants conviennent ; on prend le premier. e = enfants(f, D) if premier and len(e) == 2: return e[0] return e[0] if len(e) == 1 else None def formes_reduites(D): r = isqrt(D) out = [] for b in range(1, r + 1): if (b - D) % 2: continue n = (b * b - D) // 4 for a in range((r - b) // 2 + 1, (r + b) // 2 + 1): if n % a == 0 and gcd(gcd(a, b), abs(n // a)) == 1: out.append((a, b, n // a)) out.append((-a, b, -(n // a))) return out def chaine(f, D, cap): mx = pq_max_periodique(*f, D) if mx > cap: return None g = f for i in range(PAS): g = enfant(g, D, i == 0) if g is None: return None mx = max(mx, pq_max_periodique(*g, D)) if mx > cap: return None return mx def forme_du_mot(w): p, pp, q, qp = 1, 0, 0, 1 for a in w: p, pp, q, qp = p * a + pp, p, q * a + qp, q return primitive(q, qp - p, -pp) def main(): t0 = time.time() print("CHAINES_pLC_B12 -- verification arithmetique des listes de discriminants", flush=True) ok_global = True # auto-test : [3;1,1] periodique est racine de x**2 - 3x - 2 (D = 17, maximum 3), et sa # chaine se ferme a C = 3 (Lemmes 15-16 de Vitorino-Vukusic). f17 = forme_du_mot([3, 1, 1]) if (f17 != (1, -3, -2) or pq_max_periodique(*f17, 17) != 3 or chaine(f17, 17, 3) != 3 or chaine(f17, 17, 2) is not None): print("AUTO-TEST ECHOUE : arret.", flush=True) return print("auto-test : OK", flush=True) print("", flush=True) print("Partie A : D <= %d" % DMAX, flush=True) m = {} for D in range(9, DMAX + 1, 8): if isqrt(D) ** 2 == D: continue best = None for f in formes_reduites(D): x = chaine(f, D, CMAX) if x is not None and (best is None or x < best): best = x if best is not None: m[D] = best if D % 20000 == 1: print(" ... D = %d (%.0f s)" % (D, time.time() - t0), flush=True) for C in range(1, CMAX + 1): calc = sorted(d for d in m if m[d] <= C) att = sorted(d for d in NOYAU[C] if d <= DMAX) etat = "OK" if calc == att else "ECART" if etat != "OK": ok_global = False print(" C=%2d : %3d discriminants par les chaines, %3d dans le noyau %s" % (C, len(calc), len(att), etat), flush=True) print("", flush=True) print("Partie B : discriminants > %d" % DMAX, flush=True) for (D, Cmin, mot) in GRANDS: f = forme_du_mot(mot) x = chaine(f, D, CMAX) if disc(f) == D else None etat = "OK" if (x == Cmin and D % 8 == 1) else "ECART" if etat != "OK": ok_global = False print(" D=%11d : maximum le long de la chaine = %s, apparition a C = %d %s" % (D, x, Cmin, etat), flush=True) for C in range(1, CMAX + 1): tous = sorted(NOYAU[C]) if any(d % 8 != 1 for d in tous): ok_global = False print(" C=%d : discriminant impair non congru a 1 mod 8 : ECART" % C, flush=True) print("", flush=True) print("Partie C : ordre de [p_2] le long de la chaine, C = 8", flush=True) for D in NOYAU[8]: ordres = set() for f in formes_reduites(D): if chaine(f, D, 8) is None: continue cles = [cle_classe(*f, D)] g = f for i in range(PAS): g = enfant(g, D, i == 0) cles.append(cle_classe(*g, D)) j = len(cles) - 2 while cles[j] != cles[-1]: j -= 1 ordres.add(len(cles) - 1 - j) att = ORDRES_C8.get(D, 1) etat = "OK" if ordres == {att} else "ECART" if etat != "OK": ok_global = False print(" D=%6d : ordre %s (attendu %d) %s" % (D, sorted(ordres), att, etat), flush=True) print("", flush=True) print("CONCLUSION : %s" % ("toutes les verifications sont OK" if ok_global else "AU MOINS UN ECART"), flush=True) print("temps total %.1f s" % (time.time() - t0), flush=True) if __name__ == "__main__": main()