bandfamily.py
Checks: FLATTEN: Past the last failure the champion attains the least height rule; rule; property; pattern.
Cited on: FLATTEN.
To run it: save bandfamily.py, with band.py, bandend.py, flatten.py beside it; needs numpy, sympy.
"""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)