band.py
Checks: FLATTEN: Read by rank, the failures sit in a band of depths rule; FLATTEN: Past the last failure seen the champion attains the least height rule.
Cited on: FLATTEN.
To run it: save band.py, with flatten.py beside it; standard library only.
"""band.py -- at a fixed rank, which depths of flattening make the
least-height polynomial beat every product of factors x^d - 1, and the
single product that takes over past them.
QUESTION. flatten.py finds the chart's failing cells (h < ph) at ranks
r = M - J from 5 to 18 only. Is that range a fact about the rank, or
the chart's width M <= 40 crossing something that moves with the depth?
Read one rank at a time over unbounded depth: where does the rank first
fail, where does it last fail, and what attains h past the last
failure?
THE OBJECTS (flatten.py's senses). h(M, J) is the least height of a
nonzero multiple of (x - 1)^J of degree < M; ph(M, J) the least height
of an admissible pure product prod (x^{g_i} - 1), at least J parts and
degree < M; the cell FAILS when h < ph. At rank r the pure products
admissible are exactly (x - 1)^J q with q = (x - 1)^t prod_{d in E}
[d]_x, [d]_x = 1 + x + ... + x^(d-1), over multisets E of parts >= 2
with t + sum (d - 1) <= r - 1 and |E| <= J + t -- a list that depends
on the rank and not on the depth, so ph at a fixed rank costs the same
at every depth.
THE CHAMPION. CHAMP(r, J) = (1 + x)^(r-1) (x - 1)^J, the pure product
(x^2 - 1)^(r-1) (x - 1)^(J-r+1), admissible from J = r - 1.
THE BAND at rank r: J_lo(r), the least failing depth, and J_hi(r),
the greatest one the scan reaches; J_ch(r), the least depth from
which CHAMP attains h at every depth the scan reaches.
THE HAND ATTACK, on paper before the engine.
(1) THE ROOT AT -1 (a heuristic, carrying no tier). The row of
(x - 1)^J is a Gaussian of width about sqrt(J)/2 in absolute
value, and a factor 1 + x of the cofactor differences it, which
costs a factor of order 1/sqrt(J) in the height. So s = ord_{-1} q
buys about J^(-s/2), the most a cofactor of degree <= r - 1 can
carry is s = r - 1, attained only by c(1 + x)^(r-1), and at fixed
rank and large depth the champion should be the minimiser. It says
nothing at small depth, where r - 1 differences of a narrow row are
not smooth.
(2) RANK 1 AND RANK 2. At rank 1 no cell fails (the lattice is one
pure product). At rank 2 the least height is the champion's at
every J >= 2, a theorem (rank2.py). So the scan's ranks 1 and 2
re-measure proved facts and are controls, not evidence.
(3) THE RANGE'S DERIVATION. A rank can fail on the chart only if
J_lo(r) <= min(30, 40 - r); inside 5..18 that is the chart's own
census restated, so the content is at the ranks outside it.
(4) THE STOPPING RULE IS NOT A PROOF. A scan that stops after STOP
clean depths with the champion attaining h cannot rule out a
failure further out; J_hi and J_ch are the scan's, and four
further depths past each stop are read out of sample.
THE SLATE, frozen before the engine ran. The figures are TRANSPLANTS
from an older enumeration of the same question.
P1 THE LOW EDGE. Ranks 1..4 never fail at J = 2..140.
P2 THE HIGH EDGE IS THE CHART'S. Ranks 19..22 fail, first at J = 26, 23,
25 and 30, all past the chart's widths.
P3 THE RANGE. {r : J_lo(r) <= min(30, 40 - r)} over r = 1..22 is
{5, ..., 18}.
P4 THE TAKEOVER. At ranks 5..10, J_ch = J_hi + 1 (the older values
J_ch = 31, 34, 59, 61 at ranks 5..8), and the champion attains h
at the four out-of-sample depths past each stop.
P5 THE LOW RANKS. At ranks 2, 3 and 4 the champion attains h from
J = 2, 7 and 13 through J = 140.
P6 THE BAND HAS HOLES. Some rank in 5..10 is clean at a depth
strictly between J_lo and J_hi (older: ranks 6, 7, 8).
KILLS, as prints.
K1 A failing cell at rank 1..4 (P1 dies).
K2 A rank in 19..22 with no failure up to its scan ceiling (P2 dies
at that rank).
K3 The derived range printed different from {5, ..., 18}.
K4 J_ch != J_hi + 1 at a rank of 5..10, or an out-of-sample depth
where the champion does not attain h.
K5 At rank 2, 3 or 4, a printed start other than 2, 7 and 13 (the
start opens the last unbroken run, so no later depth can fail; P5
is read off its print, and only rank 2's start is gated, by C2).
KB (bugs) h > ph; a witness not cleared (its length and height hold
by construction); the champion's height below h; ph above the
champion's height where the champion is admissible.
CONTROLS, run before any verdict is read.
C1 (POSITIVE, THE CHART) At every cell of ranks 1..22 at J = 2..min(30,
40 - r) the per-rank ph equals flatten.py's multiset ph.
C2 (POSITIVE, THE THEOREM) At rank 2 the champion attains h at every
J scanned, as rank2.py proves.
THE DESIGN. h is flatten.least_height's. ph at rank r is the least
height over the admissible cofactors, enumerated once per rank. Ranks
1..4 are scanned over J = 2..140. Ranks 5..10 are scanned upward from
J = 2 until STOP = 8 consecutive depths past the last failure have the
champion attaining h, with a ceiling of J = 140, then read at four
further depths. Ranks 11..22 are scanned upward only to their first
failure, with a ceiling of J = 60.
RESOURCE NOTE. Estimated before any run: a few minutes, the deepest
cells (rank 10 near J = 100, width 110) under a second each; under
a 512 MB memory guard.
FINDINGS (copied from the printed output).
F1 THE CONTROLS PASS. C1: the per-rank ph equals flatten.py's
multiset ph at all 560 cells of ranks 1..22 at J = 2..min(30,
40 - r), the 559 chart cells and (M, J) = (3, 2). C2: at rank 2 the
champion attains h from J = 2 through 140.
F2 THE LOW EDGE (P1 holds, K1 never fired). Ranks 1..4 are clean at
every depth 2..140, widths to 144.
F3 THE HIGH EDGE IS THE CHART'S (P2 holds). Ranks 19..22 first fail at
J = 26, 23, 25, 30, widths 45, 43, 46, 52, all past 40. Ranks
11..18 first fail at J = 14, 15, 10, 19, 17, 23, 19, 20.
F4 THE RANGE (P3 holds). {r : J_lo(r) <= min(30, 40 - r)} is
5..18, the chart's failing ranks.
F5 THE TAKEOVER (P4 holds at six ranks). Ranks 5..10:
rank J_lo J_hi J_ch holes
5 18 30 31 none
6 22 33 34 23
7 26 58 59 55, 57
8 19 60 61 20, 25, 27..31
9 12 88 89 17 depths, 13..35 and 87
10 24 106 107 105
J_ch = J_hi + 1 at every one, and the champion attains h (with
h = ph) at all 24 out-of-sample depths.
F6 THE LOW RANKS (P5 holds). The champion attains h from J = 2, 7
and 13 at ranks 2, 3, 4 through J = 140.
F7 THE HOLES (P6 holds). Ranks 6..10 each carry clean depths inside
their band; rank 5 alone fails at an unbroken run of depths.
RUN RECORD. 27.4 s against an estimate of a few minutes, peak working
set 26.1 MB, under a 512 MB memory guard; KB 0.
"""
import sys
import time
from flatten import (pow_xm1, height, clears, least_height, pure_table,
ph_of)
STOP = 8
def pmul(a, b):
out = [0] * (len(a) + len(b) - 1)
for i, x in enumerate(a):
if x:
for j, y in enumerate(b):
out[i + j] += x * y
return out
def cofactors(r):
"""[(q, t, |E|)] over the pure cofactors of rank r, independent of J:
q = (x - 1)^t prod_{d in E} [d]_x, t + sum (d - 1) <= r - 1."""
out = []
def walk(q, E, budget, last):
qt = q
for t in range(0, budget + 1):
out.append((qt, t, len(E)))
qt = pmul(qt, [-1, 1])
for d in range(max(last, 2), budget + 2):
E.append(d)
walk(pmul(q, [1] * d), E, budget - (d - 1), d)
E.pop()
walk([1], [], r - 1, 2)
return out
def ph_rank(cof, J):
base = pow_xm1(J)
best = None
for q, t, e in cof:
if e <= J + t:
hq = height(pmul(q, base))
if best is None or hq < best:
best = hq
return best
def champ(r, J):
q = [1]
for _ in range(r - 1):
q = pmul(q, [1, 1])
return height(pmul(q, pow_xm1(J)))
def cell(r, J, cof):
M = r + J
h, v, _ = least_height(M, J)
p = ph_rank(cof, J)
c = champ(r, J) if J >= r - 1 else None
kb = (len(v) != M or height(v) != h or not clears(v, J) or h > p
or (c is not None and (c < h or p > c)))
return h, p, c, kb
def controls():
table = pure_table(39)
off = n = 0
for r in range(1, 23):
cof = cofactors(r)
for J in range(2, min(30, 40 - r) + 1):
n += 1
off += ph_rank(cof, J) != ph_of(table, r + J, J)[0]
print("C1 per-rank ph against the multiset ph: %d chart cells, %d off"
% (n, off))
return off
def main():
t0 = time.time()
bad = controls()
kb = 0
rows = {}
for r in range(1, 23):
cof = cofactors(r)
fails, att = [], {}
J = 1
ceiling = 140 if r <= 10 else 60
while J < ceiling:
J += 1
h, p, c, b = cell(r, J, cof)
kb += b
if h < p:
fails.append(J)
if r >= 11:
break
att[J] = c == h
if 5 <= r <= 10 and J - (fails[-1] if fails else 0) >= STOP \
and fails and all(att[j] for j in range(J - STOP + 1,
J + 1)):
break
jlast = J
jch = None
for j in range(jlast, 1, -1):
if not att.get(j):
break
jch = j
oos = []
if 5 <= r <= 10:
for j in range(jlast + 1, jlast + 5):
h, p, c, b = cell(r, j, cof)
kb += b
oos.append(c == h and h == p)
rows[r] = (fails, jch, jlast, oos)
holes = ([j for j in range(fails[0], fails[-1] + 1)
if j not in fails] if fails else [])
print("rank %2d: J_lo %s, J_hi %s, J_ch %s, scanned to %d; holes %s;"
" out of sample %s (%.1f s)"
% (r, fails[0] if fails else None,
fails[-1] if fails else None, jch, jlast, holes,
oos or "-", time.time() - t0))
k1 = [r for r in range(1, 5) if rows[r][0]]
k2 = [r for r in range(19, 23) if not rows[r][0]]
ranks = [r for r in range(1, 23)
if rows[r][0] and rows[r][0][0] <= min(30, 40 - r)]
k4 = [r for r in range(5, 11)
if rows[r][1] != (rows[r][0][-1] + 1 if rows[r][0] else None)
or not all(rows[r][3])]
print("P1 low edge: failing ranks among 1..4 %s (K1 %s)" % (k1, bool(k1)))
print("P2 ranks 19..22 first fail at %s (K2 %s)"
% ([rows[r][0][0] if rows[r][0] else None for r in range(19, 23)],
k2))
print("P3 derived range %s (K3 %s)" % (ranks,
ranks != list(range(5, 19))))
print("P4 J_ch = J_hi + 1 with the out-of-sample depths at ranks 5..10:"
" off at %s" % k4)
print("P5 champion start at ranks 2, 3, 4: %s"
% [rows[r][1] for r in (2, 3, 4)])
print("C2 rank 2: champion attains h from J = %s through %d"
% (rows[2][1], rows[2][2]))
print("KB %d; wall %.1f s" % (kb, time.time() - t0))
return bad + kb + (rows[2][1] != 2)
if __name__ == "__main__":
sys.exit(1 if main() else 0)