"""bandfamily.py -- does the integer family (1 + x)^J (1 - x)^(r-3) (x + e (1 - x)^2) beat the champion out to each band's end, at every rank, so that its height alone could bound J_hi(r) from below? QUESTION. At rank r, depth J (after x -> -x) the lattice is {c(x)(1 + x)^J : deg c <= r - 1}, the champion (1 - x)^(r-1)(1 + x)^J of height H_ch. F_e = (1 + x)^J (1 - x)^(r-3) (x + e (1 - x)^2), e an integer, lies in it. J_F(r) is the last depth at which min_e height(F_e) < H_ch. Does J_F track J_hi at ranks 5..14 and the class least height's Gaussian crossing J_hi* (bandheight.py) at large r? BY HAND. (a) The class s = r - 3 has a self-reciprocal real minimiser: reversal keeps heights and maps the class with c'(1) = 1 to itself up to the sign (-1)^s, the sup norm is convex, and a self-reciprocal c' of degree <= 2 with c'(1) = 1 is x + a (1 - x)^2. So the real-e family's least height is the class's real least height. (b) Under x -> -x the cofactor is e + (2e - 1) x + e x^2: e = 1 the cyclotomic 1 + x + x^2, e = 2 and 3 the traded factors 2 + 3x + 2x^2 and 3 + 5x + 3x^2. (c) F_e < H_ch at J makes the champion miss h, so J_F <= J_hi (J_ch = J_hi + 1, gap.py, bandgrowth.py); F_e < ph(J) makes the cell fail, a witness for J_hi >= J. (d) The real optimum sits near e* = J/(4(r - 1)). (e) max_i |V_i + e U_i| (V = x Q, U = Q (1 - x)^2, Q = (1 + x)^J (1 - x)^(r-3)) is convex piecewise-linear in e, so the integer loss is first order, about |e - e*|/e*, and the integer crossing sits below the real one by up to about 1/(2 e*): ~25% at rank 5, ~4% at rank 100. THE ARMS. (S) ranks 5..14, exact in integers, every depth r - 1 .. J_c - 1: the least height over integer e by a binary search on the convex function's forward difference, the real least by golden section in floats from the exact columns; J_F, J_F^R, e at J_F; ph (band.ph_rank) at the top 20 depths where F beats H_ch. (L) Q carried exactly in integers, V and U rounded to floats over H_ch at each depth; ranks 5..14 (C3) over r - 1 .. J_c - 1, and r = 20, 30, 40, 50, 100 over the window 0.6 J_hi* .. 1.1 J_hi*, J_F there the last beat in the window, none at or past 0.9 of its top; J_F's beat rechecked exactly in integers and every near-tie |ratio - 1| < 1e-9 too. PREDICTIONS (frozen before the engine). P1 J_F = J_hi at ranks 5, 10, 14, and J_F/J_hi >= 0.85 at every rank 5..14. P2 at J_F, F also beats ph at every rank 5..14. P3 the alternate-depth tail (rank 13 even 156..168, rank 14 odd 189..195) shows in F's beats of ph: read, not gated. P4 J_F/J_hi* in [0.85, 1.0] at r = 20..100, rising with r; J_F^R/J_hi* in [0.93, 1.0]. KILLS. K1 J_F/J_hi* < 0.75 at some r in {20, 30, 40, 50, 100}. K2 J_F(100)/J_hi*(100) < 0.85. CONTROLS, read first. C1 J_F^R = bandheight.py's J_hi^R = 34, 35, 60, 68, 88, 109, 130, 156, 170, 199 at ranks 5..14. C2 J_F <= J_hi at ranks 5..14. C3 (L) against (S) at ranks 5..14: the same J_F and J_F^R. C4 the integer search against a brute e = -3..40 at ranks 5..8, every depth. INSTRUMENT, before the counted run. A first run carried Q in floats by Q <- Q (1 + x), renormalised: its rounding noise has no zero of order s at 1 and outgrew the signal by about J^(s/2), so (L) read J_F^R/J_hi* = 0.40, 0.22, 0.06 at r = 40, 50, 100 and fired K1, K2. An exact check at r = 30, 40 (the class's real least by the full LP and by the self-reciprocal family, equal) read a beat at r = 40, J = 1000 (0.934) the float scan had missed. Q is now carried in integers; (S) and every rank 5..14 of (L) read the same in both runs (C3 passed in both: s <= 11 there). FINDINGS (copied from the printed output). (1) Controls: C1 J_F^R = 34, 35, 60, 68, 88, 109, 130, 156, 170, 199, bandheight.py's J_hi^R at every rank; C2, C3, C4 hold; every (L) beat at J_F rechecked exactly, no near-tie. (2) P1 holds past its prediction: J_F = J_hi at every rank 5..14, at e = 2, 2, 3, 2, 3, 3, 3, 4, 4, 4 (J/(4(r - 1)) = 1.65 .. 3.75), F/H_ch = 0.924, 0.964, 0.985, 0.994, 0.991, 0.973, 0.990, 0.991, 0.996, 0.995 there, against the real class's 0.887 .. 0.982. (3) P2 holds: at J_F F also beats ph at every rank, so the family alone witnesses J_hi; ph equals H_ch at every top-20 beat depth of ranks 7 and 9..14 (rank 8 but J = 41). (4) P3 holds: F's beats reproduce the alternate-depth tails, rank 13 at 156, 158, .., 168 and rank 14 at 189, 191, 193, 195, and show the same at rank 7 (54, 56, 58), 9 (86, 88) and 10 (104, 106). (5) K1, K2 miss; P4's bands hold, its rise does not (0.9613 at r = 100 below 0.9855 at 50): J_F/J_hi* = 0.9529, 0.9756, 0.9817, 0.9855, 0.9613 and J_F^R/J_hi* = 0.9841, 0.9968, 0.9863, 0.9906, 0.9906 at r = 20, 30, 40, 50, 100; J_F/r^1.5 = 3.757, 4.211, 4.233, 4.313, 4.391; e at J_F = 5, 6, 7, 8, 11 against J/(4(r - 1)) = 4.42, 5.97, 6.87, 7.78, 11.09; the integer loss F/real at J_F 1.0002 .. 1.0272; no beat at or past 0.9 of any window's top. Above rank 14 F beats H_ch only (ph is not read): the champion misses h at J_F, so J_ch(r) > J_F there. RUN RECORD. 23.1 s, peak commit 35.5 MB under a 512 MB guard. """ import os import sys import time os.environ.setdefault("OPENBLAS_NUM_THREADS", "1") import numpy as np # noqa: E402 import band # noqa: E402 import bandend # noqa: E402 JHI = {5: 30, 6: 33, 7: 58, 8: 60, 9: 88, 10: 106, 11: 122, 12: 152, 13: 168, 14: 195} # gap.py, bandgrowth.py JC = {5: 47, 6: 57, 7: 97, 8: 108, 9: 157, 10: 170, 11: 227, 12: 241, 13: 305, 14: 319} # bandend.py, bandgrowth.py JHIR = {5: 34, 6: 35, 7: 60, 8: 68, 9: 88, 10: 109, 11: 130, 12: 156, 13: 170, 14: 199} # bandheight.py (3) JSTAR = {20: 352.6, 30: 709.3, 40: 1091.0, 50: 1547.5, 100: 4568.0} # bandheight.py's (G) and (A) prints TIE = 1e-9 def int_min(f, lo=-3, hi=None): """least f over integers in [lo, hi], f convex: the first m whose forward difference f(m + 1) - f(m) is >= 0.""" a, b = lo, hi while a < b: m = (a + b) // 2 if f(m + 1) - f(m) >= 0: b = m else: a = m + 1 return a, f(a) def golden(f, lo, hi, it=80): g = (5 ** 0.5 - 1) / 2 a, b = lo, hi c, d = b - g * (b - a), a + g * (b - a) fc, fd = f(c), f(d) for _ in range(it): if fc < fd: b, d, fd = d, c, fc c = b - g * (b - a) fc = f(c) else: a, c, fc = c, d, fd d = a + g * (b - a) fd = f(d) return min(fc, fd) def exact_cols(Qc): """V = x Q, U = Q (1 - x)^2, as integer lists of one length.""" U = bandend.pmul(Qc, [1, -2, 1]) V = [0] + Qc + [0] return V, U def exact_least(Qc, hi): V, U = exact_cols(Qc) Hc = max(abs(u) for u in U) def f(e): return max(abs(v + e * u) for v, u in zip(V, U)) e, h = int_min(f, -3, hi) Vf = np.array([v / Hc for v in V]) Uf = np.array([u / Hc for u in U]) hr = golden(lambda t: float(np.max(np.abs(Vf + t * Uf))), e - 1, e + 1) return e, h, Hc, hr, f def arm_s(): print("(S) exact, ranks 5..14", flush=True) t0 = time.time() out, c1, c2, c4 = {}, True, True, True for r in range(5, 15): s = r - 3 Qc = bandend.Q(r - 1, s) rows = {} for J in range(r - 1, JC[r]): if J > r - 1: Qc = bandend.pmul(Qc, [1, 1]) e, h, Hc, hr, f = exact_least(Qc, J + 2) rows[J] = (e, h, Hc, hr) if r <= 8: be = min(range(-3, 41), key=f) c4 &= f(be) == h beats = [J for J, v in rows.items() if v[1] < v[2]] jf = max(beats) if beats else None rbeats = [J for J, v in rows.items() if v[3] < 1 - TIE] jfr = max(rbeats) if rbeats else None ties = [J for J, v in rows.items() if abs(v[3] - 1) < TIE] c1 &= jfr == JHIR[r] c2 &= jf is not None and jf <= JHI[r] cof = band.cofactors(r) top = sorted(beats)[-20:] php = {} for J in top: php[J] = band.ph_rank(cof, J) fph = [J for J in top if rows[J][1] < php[J]] phch = [J for J in top if php[J] < rows[J][2]] e, h, Hc, hr = rows[jf] print(" r = %2d J_F = %d (J_hi %d, J_F/J_hi %.3f), e = %d" " (J/(4(r-1)) = %.2f), F/H_ch %.5f, real %.5f; J_F^R = %s;" " real near-ties %s [%.1f s]" % (r, jf, JHI[r], jf / JHI[r], e, jf / (4 * (r - 1)), h / Hc, hr, jfr, ties, time.time() - t0), flush=True) print(" F beats H_ch at the depths %s (of the last 20 such);" " F beats ph at %s; ph < H_ch at %s" % (top, fph, phch), flush=True) out[r] = (jf, jfr, jf in fph) print("C1 J_F^R = bandheight.py's J_hi^R at every rank 5..14: %s" % c1) print("C2 J_F <= J_hi at every rank 5..14: %s" % c2) print("C4 the integer search against brute e = -3..40, ranks 5..8: %s" % c4, flush=True) return out, c1, c2, c4 def arm_l(r, jlo, jmax): """{J: (e, F/H_ch, real/H_ch)} for J = jlo .. jmax: Q carried exactly in integers, V and U rounded to floats over H_ch at each depth (a float recursion Q <- Q (1 + x) loses the zero of order s at 1: its rounding noise outgrows the signal by about J^(s/2)).""" s = r - 3 Qc = bandend.Q(jlo, s) rows = {} for J in range(jlo, jmax + 1): if J > jlo: Qc = [a + b for a, b in zip(Qc + [0], [0] + Qc)] Vc, Uc = exact_cols(Qc) Hi = max(abs(u) for u in Uc) U = np.array([u / Hi for u in Uc]) V = np.array([v / Hi for v in Vc]) def f(e): return float(np.max(np.abs(V + e * U))) e, h = int_min(f, -3, J + 2) hr = golden(f, e - 1, e + 1) rows[J] = (e, h, hr) return rows def exact_check(r, J, e0): Qc = bandend.Q(J, r - 3) V, U = exact_cols(Qc) Hc = max(abs(u) for u in U) h = min(max(abs(v + e * u) for v, u in zip(V, U)) for e in range(e0 - 2, e0 + 3)) return h < Hc def main(): t0 = time.time() S, c1, c2, c4 = arm_s() print("(L) exact columns, float ratios", flush=True) c3, exact_ok = True, True res = {} for r in list(range(5, 15)) + sorted(JSTAR): jmax = JC[r] - 1 if r in JC else int(1.1 * JSTAR[r]) jlo = r - 1 if r in JC else int(0.6 * JSTAR[r]) rows = arm_l(r, jlo, jmax) beats = [J for J, v in rows.items() if v[1] < 1 - TIE] jf = max(beats) jfr = max(J for J, v in rows.items() if v[2] < 1 - TIE) ties = [J for J, v in rows.items() if abs(v[1] - 1) < TIE] ok = exact_check(r, jf, rows[jf][0]) for J in ties: ok &= exact_check(r, J, rows[J][0]) == (J in beats) exact_ok &= ok if r in S: c3 &= (jf, jfr) == S[r][:2] continue top = jmax >= 1.1 * JSTAR[r] - 1 and jf < 0.9 * jmax res[r] = (jf, jfr) print(" r = %3d J_F = %d, J_F/J_hi* = %.4f, J_F^R = %d," " J_F^R/J_hi* = %.4f, e = %d (J/(4(r-1)) = %.2f), F/real at" " J_F %.4f; J_F/r^1.5 = %.3f; clear past 0.9 of the top %s; near-ties" " %s [%.1f s]" % (r, jf, jf / JSTAR[r], jfr, jfr / JSTAR[r], rows[jf][0], jf / (4 * (r - 1)), rows[jf][1] / rows[jf][2], jf / r ** 1.5, top, ties, time.time() - t0), flush=True) print("C3 (L) against (S) at ranks 5..14: %s" % c3) print("every (L) beat at J_F and near-tie rechecked exactly: %s" % exact_ok) p1 = [r for r in JHI if S[r][0] != JHI[r]] p1b = [r for r in JHI if S[r][0] / JHI[r] < 0.85] p2 = [r for r in JHI if not S[r][2]] p4 = [r for r in res if not 0.85 <= res[r][0] / JSTAR[r] <= 1.0 or not 0.93 <= res[r][1] / JSTAR[r] <= 1.0] k1 = [r for r in res if res[r][0] / JSTAR[r] < 0.75] k2 = res[100][0] / JSTAR[100] < 0.85 print("P1 ranks with J_F != J_hi: %s; with J_F/J_hi < 0.85: %s" % (p1, p1b)) print("P2 ranks where F does not beat ph at J_F: %s" % p2) print("P4 r off P4's bands: %s" % p4) print("K1 r with J_F/J_hi* < 0.75: %s (K1 %s)" % (k1, "fires" if k1 else "misses")) print("K2 J_F(100)/J_hi*(100) = %.4f (K2 %s)" % (res[100][0] / JSTAR[100], "fires" if k2 else "misses")) print("%.1f s" % (time.time() - t0)) return not (c1 and c2 and c3 and c4 and exact_ok) or bool(k1) or k2 if __name__ == "__main__": sys.exit(1 if main() else 0)