evenarm.py

"""evenarm.py -- at the takeover theorem's depth J*, is every non-champion
pure product above height(F_e) at the even ranks r = 26..50?

QUESTION. At even r, J* = (4e - 1) l - 1, l = r - 2, e = floor(sqrt(l)/2):
e = 2 at r = 26..36, e = 3 at r = 38..50. The cell (J* + r, J*) fails, and
J_hi(r) >= J*, once every non-champion pure product is above height(F_e)
(the champion is: the takeover rule's integer read, here C4). Is it, at
every even r = 26..50?

BY HAND (re-derived before the code). J* = 167 .. 237 at e = 2, 395 ..
527 at e = 3. (4e - 1) l is even at even l, so J* is odd: a k = 0 shape
takes p odd (p = J + k mod 2), never the single central coefficient; its
least test is the middle pair (p = 1); a k = 1 shape takes p = 0. The cell
fails when h < ph, and h <= height(F_e) < ph suffices: the bar is
height(F_e), exact;
the mean is above it, a stronger test. Every stage is a valid lower bound
on a shape's height: compbound's LB (its C1), exacttest's X (its C1
equality; log_x, the function the verdict runs, its C4), the exact
height. TRANSPLANT (Gaussian concentration):
height(F_e)/H_ch ~ E|1 - 4eU| falls as l^(-1/2) at fixed e while the
part-5 shape's ph/H_ch falls slowly, so ph/height(F_e) rises in r inside
an e.

METHOD. e = 2: takeph.read_cell, the exact ph, timed at r = 26 (stops past
60 s). Every rank (frozen at e = 3 only; widened before the run to read
the e = 2 ranks against the scan): the pipeline, (1) compbound's bound against max(mean,
bar), (2) exacttest's best X on the shapes it misses, read against the
mean, (3) X against the bar, (4) the exact height of every shape still at
or below it. A shape passing (1) is above max(mean, bar).

PREDICTIONS (frozen before the code). P1 e = 2: ph is the part-5 shape
k=0 2^(r-5) 5 at every rank, ph/H_ch falling from 0.8109 (r = 24) to
0.80 .. 0.70. P2 e = 2: ph/height(F_e) >= 1.9, rising in r. P3 e = 3: the
bound misses some shapes (the part 5 as at odd r); P4 the exact test's
least X/mean >= 1.2, lower than the odd arm's 2.66 (no single central
coefficient at k = 0); stage 4 reached at no rank.
KILL. Printed per rank: the least, over every non-champion shape, of its
final lower bound over height(F_e), with the shape. Any <= 1 + 1e-9 fires:
F_e does not fail the cell there by this route, and that rank owes the
lattice route.
CONTROLS, read first. C1 compbound.c1 and exacttest.c1 at even r = 12, 24
(their shipped controls ran odd ranks only); exacttest.c4 at even r =
12, 14 (the verdict runs log_x, which C1 does not). C2 read_cell at r = 18, 20,
22, 24 reproduces takeph's ph/H_ch 0.8621, 0.8403, 0.8236, 0.8109 at the
part-5 shape. C3 the pipeline at r = 18..24 against read_cell: its least
final LB <= ph and the verdict ph > height(F_e) the same. PLANT: the bar
raised to ph (1 + 1e-9) at r = 18..24 must route read_cell's ph shape
through every stage to stage 4, print it at exactly ph, and trip the
kill's line. C4 mean >=
height(F_e) and H_ch > height(F_e) at every rank run.

FINDINGS (copied from the printed output).
  (1) C1 holds at even r = 12, 24: compbound's LB <= height at every
      shape, its T = 0 equality 0 of 231 and 897 off, the m plant caught
      77 of 77 and 299 of 299; exacttest 0 of 1620 and 73371 (shape, p)
      differ, the odd plant caught 179 of 179 and 14837 of 14837, the even
      plant 279 of 279 and 18163 of 18163; exacttest's C4 at r = 12, 14
      matches log X to the exact pairing at 5094 (shape, p), 10 zero, max
      |difference| 2.5e-14 (with log_x's Horner factor off by one it reads
      inf). C2 holds: ph/H_ch 0.8621,
      0.8403, 0.8236, 0.8109 at k=0 2^(r-5) 5, r = 18..24. C3 holds: the
      pipeline's least <= ph/height(F_e) (2.1988 .. 2.4092) with the same
      verdict; the bar planted at ph routes ph's shape to stage 4 at
      exactly ph and trips the kill's line at every rank (5 to 8 shapes
      there). C4 holds at every
      rank run.
  (2) The KILL misses: every non-champion pure product is above
      height(F_e) at every even r = 26..50, so with the champion (H_ch/
      height(F_e) 3.1223 .. 3.6174 at e = 2, 2.3510 .. 2.7234 at e = 3) the
      cell (J* + r, J*) fails and J_hi(r) >= J* there, computed. At e = 2
      the least final lower bound over height(F_e) is 1.0802, 1.3787,
      1.0112, 1.1676, 1.0213, 1.3282 (r = 26..36; at 28 and 36 the bound's
      floor, mean/height(F_e)), the exact test's X on shapes with a part 5
      and parts 3; stage 4 holds 1, 2, 1, 1, 0, 1 shapes. At e = 3 the
      floor binds: 1.3140 .. 1.3227, stage 4 empty.
  (3) The direct scan at e = 2: ph/height(F_e) 2.5017, 2.6094, 2.7126,
      2.7128, 2.6778, 2.6637 (r = 26..36, 0.7 .. 11.0 s), ph/H_ch 0.8012,
      0.7963, 0.7999, 0.7840, 0.7573, 0.7364; ph is k=0 2^(r-5) 5 at r =
      26..30 and k=0 2^(r-7) 5 3 at r = 32..36.
  (4) P1 fails: the part-5 shape gives way to 5 3 from r = 32, and
      ph/H_ch neither falls throughout (0.7963 at r = 28, 0.7999 at 30)
      nor stays in range (0.8012 at r = 26). P2's bar holds (>= 1.9); its
      rise, the BY HAND TRANSPLANT, fails from r = 34 (2.7128, 2.6778,
      2.6637 at r = 32, 34, 36), once ph changes shape. P3 holds: the bound misses 1443 .. 18148
      shapes at e = 3. P4 holds: least X/mean 2.1747, 2.1925, 2.2109,
      2.2299, 2.2499, 2.2713, 2.2927 (r = 38..50), below the odd arm's
      2.66, always at k=0 2^(r-5) 5, and stage 4 holds no e = 3 shape.
      At e = 2 the exact test falls below the mean (least X/mean 0.3935 ..
      0.7629) but not below height(F_e).
READS. The e = 3 least X/mean rises steadily at even r (2.17 .. 2.29),
where the odd arm's stays flat (2.66 .. 2.71): at J* odd a k = 0 shape
has no single central coefficient, and its best p is odd.

RUN RECORD. 91.8 s (controls 6.7 s), peak commit 66.1 MB.
"""
import math
import os
import sys
import time

os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
import flatten  # noqa: E402
import circlemean  # noqa: E402
import takeph  # noqa: E402
import compbound  # noqa: E402
import exacttest  # noqa: E402


def shape_height(J, k, parts):
    c = flatten.pow_xm1(J + k)
    for g in parts:
        c = takeph.mul_block(c, g)
    return flatten.height(c)


def pipeline(r, bar=None):
    """The four stages against the integer bar (default height(F_e)).
    Returns the stage counts, the least X/mean over stage 2, the least
    final LB over the bar among stages 2..4 with its shape, the floor
    max(mean, bar)/bar of the shapes passing stage 1, and the stage-4
    shapes with their heights."""
    J, e = takeph.theorem_J(r), takeph.theorem_e(r)
    hf = circlemean.exact_height_F(r, J, e)
    bar = hf if bar is None else bar
    lmean = float(circlemean.log_mean(r, J, e))
    lbar = math.log(bar)
    l1 = max(lmean, lbar)
    _, _, _, _, fs = exacttest.failing_shapes(r, l1)
    nall = sum(1 for k in range(r) for _ in exacttest.shapes(r, k))
    least_mean = (math.inf, None)
    least = (math.inf, None)
    st4 = []
    for k, parts, s, o, pi, t6, plb in fs:
        v, p = exacttest.best_x(J, k, parts)
        if v - lmean < least_mean[0]:
            least_mean = (v - lmean, takeph.name(k, parts))
        if v > lbar + math.log(1 + 1e-9):
            q = v - lbar
        else:
            h = shape_height(J, k, parts)
            st4.append((h, k, parts))
            q = math.log(h / bar)
        if q < least[0]:
            least = (q, takeph.name(k, parts))
    return {"J": J, "e": e, "hf": hf, "lmean": lmean, "all": nall,
            "st2": len(fs), "st4": st4,
            "least_mean": (math.exp(least_mean[0]), least_mean[1]),
            "least": (math.exp(least[0]), least[1]),
            "floor": math.exp(l1 - lbar)}


def main():
    t0 = time.time()
    ok = True
    for r in (12, 24):
        worst, planted, eq, eqbad, off, offc = compbound.c1(r)
        n, bad, (pon, po), (pen, pe), (walked, enum) = exacttest.c1(r)
        good = (worst <= 1e-9 and eqbad == 0 and offc == off and planted > 0
                and bad == 0 and pon == po and pen == pe and po and pe
                and walked == enum)
        print("C1 r = %d: compbound max log(LB/height) %.4f, T = 0 equality"
              " %d of %d off, m plant %d of %d, Pi plant %d; exacttest %d of"
              " %d differ, odd plant %d of %d, even plant %d of %d, shapes"
              " %d walked %d: %s  [%.1f s]"
              % (r, worst, eqbad, eq, offc, off, planted, bad, n, pon, po,
                 pen, pe, enum, walked, "holds" if good else "FAILS",
                 time.time() - t0), flush=True)
        ok &= good
    n, zero, worst = exacttest.c4((12, 14))
    print("C1 r = 12, 14: exacttest's C4, log X by Horner against the exact"
          " pairing at %d (shape, p), %d of them zero, max |difference| %.1e"
          % (n, zero, worst), flush=True)
    ok &= worst < 1e-9 and n > 0
    want = {18: 0.8621, 20: 0.8403, 22: 0.8236, 24: 0.8109}
    for r in (18, 20, 22, 24):
        J, e = takeph.theorem_J(r), takeph.theorem_e(r)
        best, hch, by_s = takeph.read_cell(J, r)
        hf = circlemean.exact_height_F(r, J, e)
        nm = takeph.name(best[1], best[2])
        c2 = abs(best[0] / hch - want[r]) < 6e-5 and nm == \
            "k=0 2^%d 5" % (r - 5)
        res = pipeline(r)
        lo = min(res["least"][0], res["floor"])
        c3 = lo <= best[0] / hf + 1e-12 and (lo > 1 + 1e-9) == (best[0] > hf)
        pl = pipeline(r, bar=best[0] + best[0] // 10 ** 9 + 1)
        hit = [h for h, k, parts in pl["st4"] if (k, parts) == best[1:]]
        caught = hit == [best[0]] and min(h for h, _, _ in pl["st4"]) == \
            best[0] and min(pl["least"][0], pl["floor"]) <= 1 + 1e-9
        print("C2 r = %d: ph/H_ch %.4f at %s (takeph %.4f) %s; C3 pipeline"
              " least %.4f, ph/height(F_e) %.4f %s; PLANT bar at ph: stage 4"
              " holds %d shapes, ph's shape at %s %s"
              % (r, best[0] / hch, nm, want[r], "holds" if c2 else "FAILS",
                 lo, best[0] / hf, "holds" if c3 else "FAILS",
                 len(pl["st4"]), hit, "caught" if caught else "MISSED"),
              flush=True)
        ok &= c2 and c3 and caught
    print("C1, C2, C3 %s  [%.1f s]" % ("hold" if ok else "FAIL",
                                       time.time() - t0), flush=True)
    kill = []
    c4bad = 0
    for r in range(26, 51, 2):
        t1 = time.time()
        res = pipeline(r)
        J, e, hf = res["J"], res["e"], res["hf"]
        hch = circlemean.exact_Hch(r, J)
        c4 = math.exp(res["lmean"]) >= hf and hch > hf
        c4bad += not c4
        lo = min(res["least"][0], res["floor"])
        at = res["least"][1] if res["least"][0] <= res["floor"] else \
            "(the bound's floor)"
        print("r = %d e = %d J* = %d: H_ch/height(F_e) %.4f, mean/height(F_e)"
              " %.4f; shapes %d, past the bound %d, at stage 4 %d; least"
              " X/mean %.4f at %s; least final LB/height(F_e) %.4f at %s"
              "  [%.1f s]"
              % (r, e, J, hch / hf, math.exp(res["lmean"]) / hf, res["all"],
                 res["st2"], len(res["st4"]), res["least_mean"][0],
                 res["least_mean"][1], lo, at, time.time() - t1), flush=True)
        if lo <= 1 + 1e-9:
            kill.append(r)
        if e == 2:
            t2 = time.time()
            best, hch2, by_s = takeph.read_cell(J, r)
            dt = time.time() - t2
            print("        SCAN ph/H_ch %.4f at %s; ph/height(F_e) %.4f;"
                  " pipeline least <= it %s  [%.1f s]"
                  % (best[0] / hch2, takeph.name(best[1], best[2]),
                     best[0] / hf, lo <= best[0] / hf + 1e-12, dt),
                  flush=True)
            if r == 26 and dt > 60:
                print("SCAN stops: r = 26 ran over 60 s", flush=True)
                break
    print("C4 mean >= height(F_e) and H_ch > height(F_e): %d ranks off"
          % c4bad)
    print("KILL %s" % ("fires at %s" % kill if kill else "misses"))
    print("%.1f s" % (time.time() - t0))
    return not ok or c4bad > 0 or bool(kill)


if __name__ == "__main__":
    sys.exit(1 if main() else 0)