"""realrace.py -- cubrace.py's race read at the totally real cubic fields: whether the F_2 place loses the top over one with d_K <= 3000, and the least where it does. QUESTION. cubtop.py's bound decides every column of every cubic configuration but the column of norm 3 at 675 failing ones, whatever the signature; cubrace.py read the race at the complex fields alone. Does a totally real cubic field with d_K <= 3000 lie in a failing configuration and lose, and which is the least real loss? THE ARGUMENT. The race reads only finite places: zeta_K's Euler product and the columns' local depths (cubrace.py's argument). So a real field races exactly as cubrace.py's Race reads it, once its places over every p < 10^6 are known. DESIGN. (1) FIELDS. Hunter's theorem as in cubic.py's (1), the same bound T2 <= Tr^2/3 + (2/3) sqrt(d_K), every root real: T2 = s1^2 - 2 s2, so s2 <= s1^2/3 and |s3| <= (T2/3)^(3/2). Each minimal polynomial passes through cubic.py's maximal_form. (2) ONE KEY PER FIELD. A form with three real roots has a positive definite Hessian H = (b^2 - 3ac, bc - 9ad, c^2 - 3bd), of discriminant -3 disc(f), and f -> det(g)^-1 f((x, y)g) carries H to H((x, y)g). H is Gauss-reduced in integers, exactly. A move between two reduced forms sends (1, 0) to a least vector and (0, 1) to a second least, each with entries in {-1, 0, 1}, so the forms of the class with reduced Hessian are f's images under the moves of that set keeping H reduced; the key is their least. (3) THE SPLITTING. For a form maximal at p, p factors in O_K as f factors mod p (Delone and Faddeev). Maximality at each p | d_K is asserted (no move puts p^2 | a, p | b); then p | d_K is 1^2 1 or 1^3 as f has two or one distinct roots on P^1(F_p), and any other p is 111, 12, 3 as it has three, one, none (cubrace.py's roots_mod where p does not divide a, a count on P^1 where it does). (4) THE RACE: cubrace.py's Race on the places, its verdict as cubrace.py prints it; the fields in a failing configuration found as cubrace.py's hunt finds them. (5) THE PROPORTION (proof). Race reads a field only through the splitting type of each p < 10^6. Below 10^6, zeta_K's product and both columns' places are functions of the types. Past it, each local factor of zeta_K is a product over places with sum e f = 3, so it lies in [1, (1 - p^-b)^-3] at EVERY cubic field, ramified or not, and m = 0, 3 bracket zeta_K there; the column of norm 3 takes its places past 10^6 through missed_mass, which bounds them at every field (such a place has prime norm M = 2 3^a + 1, at most three over M: at f = 2, 8 divides M - 1 but not 2 3^a, and at f = 3, p^3 - 1 = 2 3^a has no solution); the F_2 column drops only places of Fermat norm past 65537, and dropping them lowers sigma_2 and so raises the root of zeta_K = 1 + sigma_2: its upper end stays an upper end. No real place is read. Each end is bisected in floats to 1e-9, against a gap between the brackets of 2e-3 at the least, and (6) certifies the LOSS at 30 digits at -1420 and 1940. So a LOSS printed at a field is a LOSS at every cubic field of either signature with the same type at every p < 10^6. Bhargava, Shankar and Tsimerman (On the Davenport-Heilbronn theorems and second order terms, Invent. Math. 193 (2013), Theorem 7) count the cubic fields of a given signature with |d_K| < X whose ring at each p lies in a set Sigma_p of maximal orders, Sigma_p all of them past a bound: c X + o(X), c a product of local masses, positive when each Sigma_p is nonempty. With Sigma_p the maximal orders of -1420's type at each p < 10^6, the F_2 place loses at a positive proportion of the complex cubic fields, and of the totally real ones, ordered by |d_K|. A configuration the bound decides tops at every field in it, so the F_2 place tops at a positive proportion too. (6) THE FLOAT. (5) bounds the bisection, not the float evaluation of zeta_K, the tail and the sigmas over the primes below 10^6. At -1420 and 1940, each of the four ends' functions h(b) = zeta_K(b, m) - sigma(b) - 1 is evaluated again at its printed root in mpmath at 30 digits, and the root's shift read as |h_float - h_mp| / |h'(b)|, h' a float central difference: a measurement. The certificate: at b* midway between the F_2 upper end and the N=3 lower end, the F_2 upper end's h, at 30 digits, is negative and the N=3 lower end's positive. With Psi = zeta_K - sigma at a column's true zeta_K and sigma, its point where Psi = 1, the F_2 end's h is at least the F_2 column's Psi - 1 (zeta_K at the tail's cube, at least the true tail; sigma_2 short of the dropped places) and the N=3 end's h at most the norm-3 column's Psi - 1 (zeta_K with no tail, at most the true one; sigma_3 times exp of three M^-b at every M = 2 3^a + 1 past 10^6, at least its places there, the loop's remainder past M^-b < 1e-40 below 1e-39), and each Psi is a sum of m^-b over a fixed set, so decreases: the F_2 point lies below b* and the column of norm 3's above it. 30 digits against margins of 2.6e-3. CONTROLS, read before any verdict. CX the reader of (3) on the complex side: its places equal cubrace.py's cubic_places at the ten complex FIELDS, to 10^6; its hunt over cubic.py's enumerate_fields(3000) returns those FIELDS, their discriminants and forms; the race at -1420 reprints cubrace.py's brackets [1.59661, 1.59670] and [1.59889, 1.59897]. CF (6) reads a shift: mpmath at the root plus 1e-6 against floats at the root prints a shift within 1e-8 of 1e-6. CS (6)'s certificate can refuse: at -1420 the F_2 upper end's h at its root minus 1e-4 is positive, and the N=3 lower end's at its root plus 1e-4 negative. CR (1)-(2): the real fields d_K <= 3000 are 96, their discriminants LMFDB's (degree 3, signature [3,0]), one field each; every key unchanged under 30 random GL2(Z) moves of its form, the Hessian covariant under each. PREDICTIONS, fixed before the first run. (p1) between 3 and 10 real fields with d_K <= 3000 in a failing configuration, 940 among them (4 | 940 and 5 || 940, so 2 ramifies and 5 = P^2 Q). (p2) no LOSS below 1420 (TRANSPLANT from the complex side, where -460 and -940 top). (p3) no OPEN. KILL of (p2): the RACE line prints LOSS at a d_K < 1420. Fixed before (6)'s code: (p4) every shift of (6) below 1e-8. KILL of the proof's float step: a shift of 1e-4 or more, against a gap of 2e-3. Gated after the first run, the record it reprints: RL, the RACE line's LOSS at exactly 1940 and 2804 with none OPEN, so (6) certifies 1940 beside -1420. FINDINGS. CX: places equal at the ten FIELDS; the complex hunt returns them; with CX1's places, -1420 reprints F2 [1.59661, 1.59670], N=3 [1.59889, 1.59897]. CR: 96 fields, opening 49, 81, 148, 169, 229, 257, 316, 321, 361, 404, = LMFDB's list; every key held under 30 moves. HUNT: 96 fields, 64 with an F_2 place, 2 in a failing configuration, each failing at the column of norm 3 alone (complex: 419 fields, 324 with an F_2 place, 10 failing). RACE: LOSS 2 [1940, 2804], TOP 0, OPEN 0. d_K 1940 (form (-1, 0, 8, -2), 2 = Q^3, configuration qrsiq, least ratio 0.960832): F2 [1.56119, 1.56134], N=3 [1.56351, 1.56364], central gap -0.00232. The F_2 column holds places of norm 3, 5, 5, 9, 17, 17, 17, 65537; the column of norm 3 holds Q to depth 2 and places of norm 19, 163, 487. d_K 2804 (form (-1, -1, 9, -1), 2 = Q^3, configuration qsiiq, least ratio 0.930575): F2 [1.60468, 1.60476], N=3 [1.62816, 1.62821], central gap -0.02347; F_2 column 3, 5, 5, 5, 9, 65537; held 487, 487, 487, 1459, 39367, 39367, 39367. FLOAT: CF reads the planted 1e-6 as 1.0000e-06 (h' -2.3964). At the eight ends, h_float - h_mp lies within 2.7e-15, h' from -2.394 to -2.784, and the largest shift is 9.394e-16 (1940, N=3 upper). CS: h +2.397e-04 at -1420's F2 upper end less 1e-4, -2.778e-04 at its N=3 lower end plus 1e-4. The certificate: at b* 1.597795 (-1420) the F2 upper end's h is -2.628e-03 and the N=3 lower end's +3.060e-03; at b* 1.562428 (1940), -2.601e-03 and +3.024e-03. (p1) fails: 2 fields, not 3 to 10, and 940 is not one: 940 has 2 = P^2 Q and 5 = P^2 Q but 3 inert (2 r, configuration irqii), so no place of norm 3 and no failing column. cubtop.py's failures have 3 of type 12, 1^3 or 1^2 1 besides 2 and 5, never 111 or 3. (p2) holds: the least real loss is 1940. (p3) holds. (p4) holds: the float evaluation moves no end by 1e-15, twelve orders below the gap, and both losses are certified at 30 digits. READING. With the complex hunt, every cubic field with |d_K| <= 3000 in a failing configuration is read, both signatures: the F_2 place loses at -1420, 1940, -2764 and 2804, so -1420 is the least |d_K| cubic field where it loses, and 4 of the 388 fields with an F_2 place lose; by (5) a positive proportion does. 1940 shares -1420's configuration, its least ratio and its F_2 column, and loses by as much (central gap -0.00232 against -0.00228); 2804 shares -2956's configuration, which tops, and loses. RUN RECORD. `python realrace.py`: 9 of 9 checks, 100.4 s, peak commit 117.5 MB; 940's line prints 2 r, configuration irqii. With RL: 10 of 10, 100.2 s, 118.1 MB, RACE LOSS 2 [1940, 2804]. """ import os import random import sys from collections import Counter from math import exp, sqrt os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") sys.path.insert(0, os.path.dirname(os.path.abspath(__file__))) import numpy as np # noqa: E402 from mpmath import mp, mpf # noqa: E402 import cubrace # noqa: E402 import cubtop # noqa: E402 from cubic import (_SMALL, _irreducible_monic, disc, enumerate_fields, # noqa: E402 maximal_form, subst) # LMFDB, number fields of degree 3 and signature [3,0], 1 <= d_K <= 3000 LMFDB = [49, 81, 148, 169, 229, 257, 316, 321, 361, 404, 469, 473, 564, 568, 621, 697, 733, 756, 761, 785, 788, 837, 892, 940, 961, 985, 993, 1016, 1076, 1101, 1129, 1229, 1257, 1300, 1304, 1345, 1369, 1373, 1384, 1396, 1425, 1436, 1489, 1492, 1509, 1524, 1556, 1573, 1593, 1620, 1708, 1765, 1772, 1825, 1849, 1901, 1929, 1937, 1940, 1944, 1957, 2021, 2024, 2057, 2089, 2101, 2177, 2213, 2228, 2233, 2241, 2292, 2296, 2300, 2349, 2429, 2505, 2557, 2589, 2597, 2636, 2673, 2677, 2700, 2708, 2713, 2777, 2804, 2808, 2836, 2857, 2917, 2920, 2941, 2981, 2993] CHECKS = [] def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" ({detail})" if detail else "")) def hessian(f): a, b, c, d = f return (b * b - 3 * a * c, b * c - 9 * a * d, c * c - 3 * b * d) def hsubst(H, al, be, ga, de): """H(al X + be Y, ga X + de Y).""" A, B, C = H return (A * al * al + B * al * ga + C * ga * ga, 2 * A * al * be + B * (al * de + be * ga) + 2 * C * ga * de, A * be * be + B * be * de + C * de * de) def real_key(f): """(2): the least form of f's class whose Hessian is reduced.""" H = hessian(f) assert H[0] > 0 and H[1] ** 2 - 4 * H[0] * H[2] < 0 while True: A, B, C = H k = (A - B) // (2 * A) # B + 2kA in (-A, A] if k: f, H = subst(f, 1, k, 0, 1), hsubst(H, 1, k, 0, 1) if H[2] < H[0]: f, H = subst(f, 0, -1, 1, 0), hsubst(H, 0, -1, 1, 0) continue break best = None for g in _SMALL: A2, B2, C2 = hsubst(H, *g) if abs(B2) <= A2 <= C2: F = subst(f, *g) if best is None or F < best: best = F return best def enumerate_real(cap): """(1): every totally real cubic field with d_K <= cap, {key: d_K}.""" fields = {} for s1 in (0, 1): t2max = s1 * s1 / 3 + (2 / 3) * sqrt(cap) + 1e-9 s2lo = -int((t2max - s1 * s1) // 2) - 1 s3max = int((t2max / 3) ** 1.5) + 1 for s2 in range(s2lo, 1): if s1 * s1 - 2 * s2 > t2max: continue for s3 in range(0 if s1 == 0 else -s3max, s3max + 1): if s3 == 0 or disc((1, s1, s2, s3)) <= 0: continue if not _irreducible_monic(s1, s2, s3): continue f = maximal_form((1, s1, s2, s3)) dk = disc(f) if dk > cap: continue key = real_key(f) if key not in fields: fields[key] = dk return fields def value(f, x, y): a, b, c, d = f return a * x ** 3 + b * x * x * y + c * x * y * y + d * y ** 3 def p1_roots(f, p): """The distinct roots of f mod p on P^1(F_p).""" rs = [(r, 1) for r in range(p) if value(f, r, 1) % p == 0] if f[0] % p == 0: rs.append((1, 0)) return rs def maximal_at(f, p): """No move puts p^2 | a, p | b: f's ring is maximal at p.""" if all(x % p == 0 for x in f): return False a, b = f[0], f[1] if a % p == 0 and b % p == 0: return a % (p * p) != 0 for r in range(p): if value(f, r, 1) % p == 0 and (3 * f[0] * r * r + 2 * f[1] * r + f[2]) % p == 0: F = subst(f, r, 1, 1, 0) return not (F[0] % (p * p) == 0 and F[1] % p == 0) return True def ptype(f, dk, p): """(3): p's splitting type in cubtop.py's codes.""" if dk % p == 0: assert maximal_at(f, p), (f, p) return {2: "r", 1: "t"}[len(p1_roots(f, p))] if f[0] % p: n = cubrace.roots_mod(p, f[0], f[1], f[2], f[3]) else: n = len(p1_roots(f, p)) return {3: "s", 1: "q", 0: "i"}[n] PLACES = {"s": [(1, 1)] * 3, "q": [(1, 1), (2, 1)], "i": [(3, 1)], "r": [(1, 2), (1, 1)], "t": [(1, 3)]} def places(f, dk): """[(p, f, e)] for every place over p < 10^6.""" assert disc(f) == dk return [(p, fd, e) for p in cubrace.PRIMES for fd, e in PLACES[ptype(f, dk, p)]] def hunt(fields, G, top): """cubrace.py's hunt through (3): {(d_K, form): configuration}.""" found, n2 = {}, 0 for form, dk in fields.items(): t2 = ptype(form, dk, 2) if t2 not in "srqt": continue n2 += 1 ty = "".join(ptype(form, dk, p) for p in cubtop.REL) bad, _, least = cubtop.sweep( G, [((t2, ty), cubtop.cubic_profile(t2, ty))], top) if bad: found[(dk, form)] = ty print(f" d_K {dk}: 2 {t2}, config {ty}, least ratio " f"{least[0]:.6f}, failing {[b[1] for b in bad]}") print(f" {len(fields)} fields, {n2} with an F_2 place, {len(found)} " f"in a failing configuration") return found def random_move(rng): g = (1, 0, 0, 1) for _ in range(rng.randint(1, 6)): e = rng.choice([(1, rng.randint(-3, 3), 0, 1), (1, 0, rng.randint(-3, 3), 1), (0, -1, 1, 0), (0, 1, 1, 0), (-1, 0, 0, 1)]) al, be, ga, de = g g = (al * e[0] + be * e[2], al * e[1] + be * e[3], ga * e[0] + de * e[2], ga * e[1] + de * e[3]) return g def control_complex(G, top): print("CONTROL CX: the reader of (3) on the complex side") same = all(sorted(places(form, dk)) == sorted(cubrace.cubic_places( form, dk)) for dk, form in cubrace.FIELDS.items()) check("CX1 places equal cubic_places at the ten FIELDS, to 10^6", same) found = hunt(enumerate_fields(3000), G, top) check("CX2 the complex hunt returns FIELDS", set(found) == set(cubrace.FIELDS.items())) r = cubrace.Race(places(cubrace.FIELDS[-1420], -1420), 3).read() f2, n3 = r["F2"], r["N3"] print(f" -1420: F2 [{f2[0]:.5f}, {f2[2]:.5f}], N=3 [{n3[0]:.5f}, " f"{n3[2]:.5f}]") check("CX3 the race at -1420 reprints cubrace.py's brackets", [round(x, 5) for x in (f2[0], f2[2], n3[0], n3[2])] == [1.59661, 1.59670, 1.59889, 1.59897]) def control_real(fields): print("CONTROL CR: the real enumeration") dks = sorted(fields.values()) print(f" {len(dks)} fields, opening {dks[:10]}") check("CR1 96 fields to 3000, the discriminants LMFDB's", dks == LMFDB, f"{len(dks)}") rng = random.Random(1597) ok = True for form in fields: for _ in range(30): g = random_move(rng) F = subst(form, *g) ok &= hessian(F) == hsubst(hessian(form), *g) ok &= real_key(F) == form check("CR2 every key unchanged under 30 random moves, H covariant", ok) def h_float(R, sig, m, b): return R.zeta_K(b, m) - sig(R)(b) - 1 def h_mp(R, which, m, b): """(6): h(b) at 30 digits.""" mp.dps = 30 b = mpf(b) norms = Counter(p ** f for p, f, e in R.places) zK = mp.exp(-mp.fsum(k * mp.log1p(-mpf(N) ** -b) for N, k in norms.items())) tail = mp.zeta(b) * mp.exp(mp.fsum(mp.log1p(-mpf(p) ** -b) for p in cubrace.PRIMES)) x = mpf(2) ** -b if which == "F2": s = (1 - x) ** -(R.g - 1) for N in R.fermat: s *= 1 + mpf(N) ** -b else: s = mpf(1) for f, e in R.two: if f == 1: s *= mp.fsum(x ** j for j in range(4 if e == 1 else 3)) elif f == 2: s *= 1 + mpf(4) ** -b + mpf(16) ** -b s /= (1 - mpf(3) ** -b) ** (R.n3 - 1) for M in R.held: s *= 1 + mpf(M) ** -b if which == "N3lo": mm, a = mpf(0), 0 while True: M = 2 * 3 ** a + 1 if M > cubrace.X: mm += 3 * mpf(M) ** -b if mpf(M) ** -b < mpf(10) ** -40: break a += 1 s *= mp.exp(mm) return zK * tail ** m - s - 1 ENDS = [("F2", "F2 lower", 0), ("F2", "F2 upper", 3), ("N3lo", "N=3 lower", 0), ("N3", "N=3 upper", 3)] def sig(which): return {"F2": lambda R: R.sigma2, "N3": lambda R: R.sigma3, "N3lo": lambda R: (lambda b: R.sigma3(b) * exp(cubrace.missed_mass(b)))}[which] def shift(R, which, m, b, plant=0.0): hf = h_float(R, sig(which), m, b) hm = float(h_mp(R, which, m, b + plant)) d = (h_float(R, sig(which), m, b + 1e-5) - h_float(R, sig(which), m, b - 1e-5)) / 2e-5 return hf, hf - hm, d, abs(hf - hm) / abs(d) def float_check(fields): print("\nFLOAT (6): each end's h re-evaluated in mpmath at 30 digits") R = cubrace.Race(places(cubrace.FIELDS[-1420], -1420), 3) b = R.root(R.sigma2, 3) _, _, d, s = shift(R, "F2", 3, b, plant=1e-6) print(f" CF -1420 F2 upper, mpmath at the root + 1e-6: h' {d:.4f}, " f"shift {s:.4e}") check("CF the shift of a planted 1e-6 read within 1e-8", abs(s - 1e-6) < 1e-8, f"{s:.4e}") worst, cert = 0.0, [] for dk, form in fields: R = cubrace.Race(places(form, dk), 3) f2hi, n3lo = R.root(R.sigma2, 3), R.root(sig("N3lo")(R), 0) if dk == -1420: hc = float(h_mp(R, "F2", 3, f2hi - 1e-4)) hd = float(h_mp(R, "N3lo", 0, n3lo + 1e-4)) print(f" CS -1420 F2 upper end's h at its root - 1e-4: " f"{hc:+.3e}; N=3 lower end's at its root + 1e-4: " f"{hd:+.3e}") check("CS the certificate refuses a point past either end", hc > 0 > hd, f"{hc:+.3e}, {hd:+.3e}") bs = (f2hi + n3lo) / 2 hF, hN = float(h_mp(R, "F2", 3, bs)), float(h_mp(R, "N3lo", 0, bs)) cert.append(hF < 0 < hN) print(f" d_K {dk} at b* {bs:.6f}: F2 upper end's h {hF:+.3e}, " f"N=3 lower end's h {hN:+.3e}") for which, name, m in ENDS: fn = sig(which)(R) b = R.root(fn, m) hf, dh, d, s = shift(R, which, m, b) worst = max(worst, s) print(f" d_K {dk} {name}: b {b:.9f}, h_float {hf:+.3e}, " f"h_float - h_mp {dh:+.3e}, h' {d:.4f}, shift {s:.3e}") print(f"FLOAT the largest shift {worst:.3e}") check("F every shift of (6) below 1e-4, the kill", worst < 1e-4, f"{worst:.3e}") check("FC each LOSS certified at 30 digits: F2 below b*, N=3 above", all(cert)) def main(): G = cubtop.Grid(1.0001 + cubtop.STEP * np.arange(29999)) top = cubtop.top_index(G, 3) control_complex(G, top) fields = enumerate_real(3000) control_real(fields) if not all(CHECKS): print("a control failed: no verdict") sys.exit(1) print("\nHUNT: the real cubic fields d_K <= 3000 in a failing " "configuration") found = hunt(fields, G, top) for form, dk in fields.items(): if dk == 940: print(f" (p1)'s candidate 940: 2 {ptype(form, dk, 2)}, config " f"{''.join(ptype(form, dk, p) for p in cubtop.REL)}") tally = {"LOSS": [], "TOP": [], "OPEN": []} for (dk, form), ty in sorted(found.items()): R = cubrace.Race(places(form, dk), 3) r = R.read() f2, n3 = r["F2"], r["N3"] v = ("LOSS" if n3[0] > f2[2] else "TOP" if n3[2] < f2[0] else "OPEN") tally[v].append(dk) two = "".join(f"f{f}e{e} " for f, e in R.two) print(f" d_K {dk} {form}: 2 = {two}| F2 [{f2[0]:.5f}, " f"{f2[2]:.5f}] | N=3 [{n3[0]:.5f}, {n3[2]:.5f}] | central " f"gap {f2[1] - n3[1]:+.5f} | {v}") print(f" Fermat places {sorted(R.fermat)}, norm-3 places " f"{R.n3}, held {sorted(R.held)}") print("RACE " + ", ".join(f"{k} {len(v)} {v}" for k, v in tally.items())) check("RL the real race: LOSS exactly at 1940 and 2804, none OPEN", tally["LOSS"] == [1940, 2804] and not tally["OPEN"]) float_check([(-1420, cubrace.FIELDS[-1420])] + [(dk, form) for (dk, form) in found if dk == 1940]) print(f"{sum(CHECKS)} of {len(CHECKS)} checks pass") sys.exit(0 if all(CHECKS) else 1) if __name__ == "__main__": main()