splitsharp.py
Checks: THERMAL: A loss exists exactly at degree 16 to 732 where 2 splits theorem; rule; observation.
Cited on: THERMAL.
To run it: save splitsharp.py, with fieldtop.py, growth.py, memory.py, spectrum.py, splitend.py, splitloss.py beside it; needs mpmath, numpy, scipy.
"""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()