"""splitsharp.py -- are the ends of the band of losing degrees attained, over the fields where 2 splits completely? QUESTION. splitend.py: at every number field K of degree d where 2 splits completely, log(1 + margin) >= min(0, h(x*(d))), and h(x*) <= 0 at exactly d = 16..732; so a loss needs 16 <= d <= 732. Is there, at d = 16 and at d = 732, a field where 2 splits completely and the F_2 place loses to infinitely many columns? At which d in 16..732 is a loss attained, at which is it excluded, and which are left open? THE DERIVATION (by hand, before any engine). REALIZATION (Krasner and weak approximation). Let S be a finite set of primes and, for p in S, A_p an etale Q_p-algebra of degree d. Take f_p in Z_p[t] monic separable with Q_p[t]/f_p = A_p, and one more prime q0 not in S with f_q0 monic of degree d irreducible mod q0. By the Chinese remainder theorem there is f in Z[t] monic, as close as wanted to f_p at each p in S and congruent to f_q0 mod q0. Then f is irreducible over Q (it is mod q0), K = Q[t]/f has degree d, and by Krasner's lemma (each root of f is nearer one root of f_p than any other, which then generates the same field over Q_p, and the match commutes with Gal(Q_p-bar/Q_p), so f and f_p factor alike over Q_p) K (x) Q_p = A_p at every p in S. Put into S three primes q1, q2, q3, each at or above Y (every prime below Y is the law's), with A = the unramified field of degree d, of degree d - 1 times Q, the unramified quadratic times Q^(d-2): the Galois group of the closure holds a d-cycle (transitive), a (d-1)- cycle (so 2-transitive) and a transposition, so it is S_d (a 2- transitive group with a transposition holds every transposition). THE HYPOTHESIS. The sill (fieldtop.py) decides a loss given a prime s = 3 mod 4 split completely with s != 1 mod every odd ramified prime. With every prime below Y > 5 in S and unramified there, every ramified prime l is above Y, and 2 unramified makes disc(K) = D (squarefree part) = 1 mod 4. The closure's abelian part is Q(sqrt D) (S_d's commutator is A_d), so with E the closure times Q(zeta_4M), M the odd ramified primes, Gal(E/Q) holds (1, a) for every a in (Z/4M)* with chi_D(a) = prod over l | D of (a/l) = 1. Pick a = 3 mod 4 and, mod each l | M, a != 0, 1, the last l | D taking a residue != 0, 1 of the sign that makes the product 1 (l >= 5 has both signs among them: 4 is a square != 1, and a non- square exists). Chebotarev gives infinitely many s with Frobenius (1, a): the hypothesis holds. So at such a field a negative sill margin at the F_2 point is a loss. A LAW is a choice of local algebras at 3, 5, 17, 257, 65537 with 2 split completely and every other prime below Y unramified of degree d (one place, of norm p^d). Its IDEAL field has those places alone; S3, W over the column's places of norm 3 and of norm 5, 9, 17, 257, 65537; Z'_L the product over its odd places; 1 + rho_L = Z'_L/(S3 W). Writing (E) as d l + log Z' + log(1 - (1 - x)/(1 + rho)) = 0 (since log S3 + w = log Z' - log(1 + rho)), every field K with the law's algebras below Y has Z'_K <= Z'_L T and 1 + rho_K <= (1 + rho_L) T (W_K >= W_L: a place of Fermat norm above Y brings 1/(1 - n^-b) to Z' and only 1 + n^-b to W). Z'_L holds the law's places below Y, the inert ones of norm p^d among them, and log T(x) = d (Y^-b + Y^(1-b)/(b - 1))/(1 - Y^-b) bounds d sum_{p >= Y} -log(1 - p^-b) (at most d places over p, each of norm >= p; the sum over n >= Y by its integral). Every term of the bound G_up(x) = d l + log Z'_L + log T + log(1 - (1 - x)/((1 + rho_L) T)) increases with x, so the field's point x_f >= x_low, the root of G_up. And w_K >= w_L, so log(1 + margin_K) = l - d l4 - w_K <= M_L(x_f), M_L = l - d l4 - w_L. M_L rises then falls on (0, 0.4) (splitend.py, STEP 1), and x_f <= x0(d) <= 0.382 (splitend.py, STEP 2), so if M_L'(x_low) < 0 then M_L(x_f) <= M_L(x_low): THE CERTIFICATE C(L) = M_L(x_low) bounds log(1 + margin) above at every field with the law's algebras, and those fields exist. C(L) < 0 is a loss attained at degree d. THE LAWS. Even d: E = 2, 5, 17, 257, 65537 split, 3 as d/2 places of norm 9 (splitend.py's ideal). Odd d: A = (d - 1)/2 of norm 9 and one of norm 3 (splitend.py's odd ideal); B = (d - 3)/2 of norm 9 and one of norm 27, S3 = 1. A loss is attained at odd d if min(C(A), C(B)) < 0. THE ODD BOUND (excluding a loss at odd d). Over 3 the places' e f sum to d. If n9 = (d - 1)/2 the degree left is 1, one place of norm 3, so S3 >= 1 + x^a3 (a3 = log2 3); the ceiling solves d l + log(1 + x^a3) + w_c + log x = 0, where M_c = h + log(1 + x^a3), increasing in x, so as in splitend.py's STEP 3 every count lowers it: case (i) is h(x_i) + log(1 + x_i^a3), x_i the root with the worst law's counts at N9 = (d - 1)/2. Else n9 <= (d - 3)/2 and S3 >= 1: case (ii) is h(x_ii), the worst law at N9 = (d - 3)/2. Every field of odd degree d where 2 splits completely has log(1 + margin) >= min(0, case (i), case (ii)): no loss at odd d where both are positive. SIZES (by hand). At d = 16, x ~ 0.17, b ~ 2.5: the tail term is 16 * 10^(-7.5)/1.5 ~ 3e-7 at Y = 10^5, the inert terms ~ 7^-40; against splitend.py's ideal -7.29e-4, so C(E) at 16 ~ -7.29e-4. At d = 732, b ~ 7.3: tail ~ 732 * 10^-32, C(E) ~ the ideal's -8.12e-7. The odd ideal at 17 is +6.37e-4; B at 17 drops one norm-9 place (raising the margin) and adds 27^-b to rho (raising it): C(B) > 0 at 17, TRANSPLANT of the first-order picture, re-read by the run. THE WITNESS ARM. K(m, 16), m < 10^8 prime, 2, 5, 17 sixteenth powers mod m, f(3) = 2: about 1 in 65536 of the primes = 1 mod 16, so about ten fields. Each other small prime p with f(p) <= 2 adds about (16/f) p^(-f b) to rho, 8 * 49^-2.5 ~ 5e-4 at p = 7, f = 2, as large as the ideal's margin; P(f(p) >= 4) = 7/8 per prime. Their margins by splitloss.py's bracket; a field below -1e-4 is raced by splitloss.py's race. DESIGN. ENGINE. A law as a list of (norm, count, in-column) at its odd places; Z'_L, S3, W, rho_L in logs; x_low by brentq on G_up; M_L and M_L' at x_low. Y = 10^5 (every prime below it read, 65537 among them). PRINTS. C(E) at d = 16 and 732 with the ideal beside it, M_L'(x_low) and x_low; C(E) at every even d in 16..732, C(A), C(B) at every odd d in 17..731, cases (i), (ii) at every odd d in 15..733: the degrees where a loss is attained, those where it is excluded, and the open ones, each as a list of ranges; the witness arm's fields, their f at the primes below 50, their brackets, and the race at any below -1e-4. CONTROLS, read before any verdict. C1 the certificate on a real field: K(6082471, 18) (splitloss.py's first loss, bracket about -0.000527), its own places below Y from splitloss.py's Light, the place over m in the tail: C >= the bracket's top, and within 1e-5 of it. C2 C(E), C(A) with log T = 0 equal splitend.py's ideal(d) to 1e-10 at d = 16, 17, 732, 733. C3 PLANT: C1's field at Y = 50 with the tail term dropped from log T prints below its bracket's bottom (the tail term is what makes C an upper bound; a plant that cannot fire reads nothing). C4 every certificate printed is >= min(0, h(x*(d))) of splitend.py (a field's margin is), and at odd d >= min(0, (i), (ii)). PREDICTIONS, frozen before the run. (p1) THE ENDS: C(E) < 0 at d = 16 (within 1e-5 of -7.29e-4) and at d = 732 (within 1e-9 of -8.12e-7), M_L'(x_low) < 0 at both: both ends are attained. (p2) EVEN d: C(E) < 0 at every even d in 16..732. (p3) ODD d: C(A) > 0 and C(B) > 0 at 17; the least odd d with min(C(A), C(B)) < 0 lies in 19..31, and from it on every odd d to 731 attains a loss; C(A) < 0 at 731. (p4) THE ODD BOUND is positive at 17 and at no odd d in 33..731. (p5) THE WITNESS ARM: 5 to 20 fields; at most 3 below 0. KILL, written as what the script prints: an end is NOT shown attained if its C(E) prints >= 0 or its M_L'(x_low) prints >= 0 (the bar on the certificate, the upper side the tail inflates); the certificate is dead if C1 prints C below the field's bracket top or C4 prints a certificate below a lower bound, and then nothing is claimed. FINDINGS. CONTROLS. C1: K(6082471, 18) has log(1 + margin) in [-5.274515186e-04, -5.274514803e-04] at b 3.188991, and C = -5.274514784e-04, 1.95e-12 above the top, M' = -1.444. C3: at Y = 50 with the tail dropped C = -5.283874003e-04, 9.36e-07 below the bottom: the tail term is what makes C an upper bound. C2: C with log T = 0 equals ideal(d) to 1e-15 at 16, 17, 732, 733. THE ENDS: C(E) = -7.291172e-04 at d = 16 (1.25e-10 above the ideal), M' = -1.4916, x_low = 0.117933812 (b 3.084, not the 2.5 the SIZES used); C(E) = -8.119395e-07 at d = 732, M' = -1.3300. Both ends are attained: at d = 16 and 732 there is a field where 2 splits completely and the F_2 place loses to infinitely many columns. EVERY d: a certificate is below 0 with M' < 0 at every even d from 16 to 732 (C(E)) and every odd d from 17 to 731 (C(B) below C(A) at all 360 odd d of 15..733: at 17 C(A) = +6.3714e-04, C(B) = -2.7452e-04); the lower bound is positive at 15 and 733 alone of 15..733; open: none. C4: no certificate below its degree's lower bound. So, with splitend.py's bound: a field of degree d >= 2 where 2 splits completely and the F_2 place loses exists exactly at d = 16..732. The odd bound is negative at 17 (case (i) -4.9566e-05, case (ii) -5.8699e-04) and at every odd d to 731; it decides nothing the certificates leave open. THE WITNESS ARM: 720006 primes = 1 mod 16 below 10^8, 15 fields; 13 have a negative margin, from -2.97e-04 to -7.26e-04 (K(73318849, 16), its log(1 + margin) 2.6e-6 above the ideal's), the other two +3.03e-03 (11 split) and +1.13e-02 (7 and 31 split). At each of the 13 the race is read outright: a column raced tops the F_2 point, the first raced at 11 of them and the second at K(32462929, 16) and K(56743441, 16), where the column at 23 falls short (and at the first, 419's too); the winners by 0.00039 to 0.00163 in b, Psi from 1.0013 to 1.0054. So d = 16 is attained by explicit fields too, e.g. K(73318849, 16), with no approximation. PREDICTIONS. (p1) holds; (p2) holds; (p3) fails: C(B) < 0 at 17, so the least odd d attaining a loss is 17, not 19..31 (the TRANSPLANT read B's dropped place of norm 9 as the larger term; the place of norm 3 that A keeps, 3^-b ~ 0.034 in (E), is what holds A up, and B has none); (p4) fails at 17, where the odd bound is negative; (p5) fails: 13 of 15 lose, not at most 3 (b ~ 3.08 makes 7^-2b small, the SIZES' b ~ 2.5 a TRANSPLANT of the wrong point). The kill missed: both ends are attained and the certificate stands. RUN RECORD. `python splitsharp.py` under a 2048 MB cap: 7 of 7 checks, 9.4 s, peak commit 187.5 MB, after the C(B) < C(A) count was printed (every other line the same as the first run's). Nothing else changed after the freeze but the helper that prints ranges. """ import math import os import sys import time os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") sys.path.insert(0, os.path.join(os.path.dirname(os.path.dirname( os.path.abspath(__file__))), "code")) import numpy as np # noqa: E402 from scipy.optimize import brentq # noqa: E402 import splitend as se # noqa: E402 import splitloss as sl # noqa: E402 CHECKS = [] Y = 10 ** 5 A3 = math.log2(3) LAWPRIMES = (2, 3, 5, 17, 257, 65537) def check(name, ok, detail=""): CHECKS.append(bool(ok)) print(f" [{'PASS' if ok else 'FAIL'}] {name}" + (f" ({detail})" if detail else "")) def lf(x): return -math.log1p(-x) def l4(x): return -math.log1p(-x ** 4) class Law: """A field's odd places below Yc as (log2 norm, count, kind), kind 3 (norm 3, in S3), 1 (in W) or 0 (rho alone); the places over primes at or above Yc are bounded by the tail term of log T.""" def __init__(self, d, places, Yc=Y, tail=True): self.d, self.Yc, self.tail = d, Yc, tail self.a = np.array([p[0] for p in places], float) self.c = np.array([p[1] for p in places], float) self.k = np.array([p[2] for p in places], int) def parts(self, x): """log Z', log S3 + w, w, and log T at x.""" b = -math.log2(x) u = np.exp(-b * self.a * math.log(2)) lz = float((self.c * -np.log1p(-u)).sum()) col = self.k > 0 sw = float((self.c[col] * np.log1p(u[col])).sum()) ww = self.k == 1 w = float((self.c[ww] * np.log1p(u[ww])).sum()) lt = 0.0 if self.tail: yb = self.Yc ** -b lt = self.d * (yb + self.Yc ** (1 - b) / (b - 1)) / (1 - yb) return lz, sw, w, lt def g_up(self, x, use_t=True): lz, sw, w, lt = self.parts(x) lt = lt if use_t else 0.0 lr = lz - sw # log(1 + rho_L) return (self.d * lf(x) + lz + lt + math.log1p(-(1 - x) * math.exp(-lr - lt))) def m(self, x): return lf(x) - self.d * l4(x) - self.parts(x)[2] def dm(self, x): ww = self.k == 1 aa = self.a[ww] dw = float((self.c[ww] * aa * x ** (aa - 1) / (1 + x ** aa)).sum()) return 1 / (1 - x) - 4 * self.d * x ** 3 / (1 - x ** 4) - dw def cert(self, use_t=True): """(C, M'(x_low), x_low): log(1 + margin) bounded above.""" x = brentq(lambda t: self.g_up(t, use_t), 1e-9, 0.45, xtol=1e-18, rtol=1e-15, maxiter=500) return self.m(x), self.dm(x), x PR_Y = sl.primes_to(Y) INERT = [p for p in PR_Y.tolist() if p not in LAWPRIMES] def law(d, kind): """E (even d), A or B (odd d), with every other prime below Y of residue degree d.""" W = [(math.log2(n), d, 1) for n in (5, 17, 257, 65537)] if kind == "E": W.append((math.log2(9), d // 2, 1)) elif kind == "A": W += [(math.log2(9), (d - 1) // 2, 1), (A3, 1, 3)] else: W += [(math.log2(9), (d - 3) // 2, 1), (3 * A3, 1, 0)] W += [(d * math.log2(p), 1, 0) for p in INERT] return Law(d, W) def field_law(m, d, Yc, tail=True): """K(m, d)'s own odd places below Yc, from splitloss.py's Light.""" K = sl.Light(m, d, Yc, sl.primes_to(Yc)) out = [] for p, f in zip(K.P.tolist(), K.fv.tolist()): if p == 2: assert f == 1 continue n = p ** f kind = 3 if n == 3 else (1 if sl.pow2plus1(n) else 0) out.append((f * math.log2(p), d // f, kind)) return Law(d, out, Yc, tail) def odd_bound(d): """(case (i), case (ii)) at odd d, both rho = 0 ceilings.""" ci = se.counts(d) # N9 = (d - 1)/2 def gi(x): return (d * lf(x) + math.log1p(x ** A3) + se.wlog(x, ci) + math.log(x)) xi = brentq(gi, 1e-14, 0.4, xtol=1e-18, rtol=1e-15, maxiter=500) vi = se.h(d, xi) + math.log1p(xi ** A3) cii = se.counts(d) cii[1] = (d - 3) // 2 xii = se.root(d, cii) return vi, se.h(d, xii) def runs(ds, step): out = [] for d in sorted(ds): if out and d == out[-1][1] + step: out[-1][1] = d else: out.append([d, d]) return ", ".join(f"{a}" if a == b else f"{a}..{b}" for a, b in out) # ------------------------------------------------------------ controls def control_c1_c3(): m, d = 6082471, 18 K = sl.Light(m, d, 10 ** 5, PR_Y) lo, hi, b0 = sl.bracket(K) lo, hi = math.log1p(lo), math.log1p(hi) C, dm, x = field_law(m, d, Y).cert() print(f"=== C1: K({m}, {d}): log(1 + margin) in [{lo:+.9e}, " f"{hi:+.9e}] at b {b0:.6f}; C {C:+.9e}, M' {dm:+.3f} at x_low " f"{x:.9f} (b {-math.log2(x):.6f})") check("C1: the certificate at or above the field's bracket top, " "within 1e-5", hi <= C <= hi + 1e-5 and dm < 0, f"C - top {C - hi:+.2e}") Cp, _, _ = field_law(m, d, 50, tail=False).cert() print(f"=== C3 PLANT: Y = 50, the tail dropped: C {Cp:+.9e}") check("C3 PLANT: the tailless certificate falls below the bracket's " "bottom", Cp < lo, f"{Cp - lo:+.2e}") def control_c2(): print("=== C2: C with log T = 0 against splitend.py's ideal") for d in (16, 17, 732, 733): L = law(d, "E" if d % 2 == 0 else "A") C, _, _ = L.cert(use_t=False) ref = se.ideal(d) check(f"C2 d={d}: C(log T = 0) = ideal(d) to 1e-10", abs(C - ref) < 1e-10, f"{C:+.12e} | {ref:+.12e}") # ------------------------------------------------------------ the run def witnesses(): print("\n=== THE WITNESS ARM: K(m, 16), m < 10^8, 2, 5, 17 split, " "f(3) = 2") t0 = time.time() s = np.ones(10 ** 8, bool) s[:2] = False for i in range(2, 10 ** 4): if s[i]: s[i * i::i] = False ms = (np.nonzero(s[1::16])[0] * 16 + 1).tolist() del s found = [] for m in ms: e = (m - 1) // 16 if pow(2, e, m) != 1 or pow(5, e, m) != 1 or pow(17, e, m) != 1: continue t = pow(3, e, m) if t != 1 and t * t % m == 1: found.append(m) print(f" {len(ms)} primes = 1 mod 16; {len(found)} fields " f"({time.time() - t0:.1f} s)") rows = [] for m in found: K = sl.Light(m, 16, 10 ** 5, PR_Y) lo, hi, b0 = sl.bracket(K) fs = [K.f(p) for p in (7, 11, 13, 19, 23, 29, 31, 37, 41, 43, 47)] rows.append((hi, lo, m, fs)) print(f" m={m}: margin [{lo:+.6e}, {hi:+.6e}] b {b0:.4f}; f at " f"7..47 {fs}") neg = [r for r in rows if r[0] < -1e-4] if neg: PR6 = sl.primes_to(10 ** 6) for hi, lo, m, _ in sorted(neg): bF, inst, rr, _, _, win = sl.race(m, 16, PR6) print(f" RACE m={m}: b_F2 {bF:.6f}; {' '.join(rr)}; winner " f"{win}") print(f" below 0: {sum(r[0] < 0 for r in rows)} of {len(rows)}") def main(): t0 = time.time() control_c1_c3() control_c2() if not all(CHECKS): print("a control failed: no verdict") sys.exit(1) print(f"controls read ({time.time() - t0:.1f} s)") print("\n=== THE ENDS") for d in (16, 732): C, dm, x = law(d, "E").cert() ide = se.ideal(d) print(f" d={d}: C(E) {C:+.6e} (ideal {ide:+.6e}, C - ideal " f"{C - ide:+.2e}), M'(x_low) {dm:+.4f}, x_low {x:.9f}") print("\n=== EVERY d IN 15..733") att, exc, opn, low, ba = [], [], [], [], [] for d in range(15, 734): hw = se.worst(d)[0] extra = "" if d % 2 == 0: cs = {"E": law(d, "E").cert()[:2]} lb = min(0.0, hw) else: cs = {k: law(d, k).cert()[:2] for k in "AB"} vi, vii = odd_bound(d) ba.append(cs["B"][0] < cs["A"][0]) lb = min(0.0, vi, vii) extra = f" | odd bound (i) {vi:+.4e} (ii) {vii:+.4e}" if any(c < lb - 1e-12 for c, _ in cs.values()): low.append(d) if any(c < 0 and dm < 0 for c, dm in cs.values()): att.append(d) elif lb >= 0: exc.append(d) else: opn.append(d) if d <= 33 or d in (36, 100, 731, 732, 733) or d % 100 == 0: print(f" d={d}: " + ", ".join(f"C({k}) {c:+.4e}" for k, (c, _) in cs.items()) + f" | h(x*) {hw:+.4e}" + extra) print(f" ATTAINED (a certificate < 0, M' < 0): even " f"{runs([d for d in att if d % 2 == 0], 2)}; odd " f"{runs([d for d in att if d % 2], 2)}") print(f" EXCLUDED (the lower bound >= 0): {runs(exc, 1)}") print(f" OPEN: {runs(opn, 2) if opn else 'none'}") print(f" C(B) < C(A) at {sum(ba)} of the {len(ba)} odd d") check("C4: no certificate below its degree's lower bound", not low, f"{low[:10]}") witnesses() print(f"\n{sum(CHECKS)} of {len(CHECKS)} checks, " f"{time.time() - t0:.1f} s") if __name__ == "__main__": main()