rank2.py
Checks: FLATTEN: At rank 2 the least height is the row's largest step theorem; FLATTEN: At rank 2 the two minima part by a factor growing as √J rule.
Cited on: FLATTEN.
To run it: save rank2.py, with flatten.py beside it; standard library only.
"""rank2.py -- the rank-2 flattening lattice: its least height, its
second minimum, and the gap between them.
QUESTION. At width M = J + 2 the integer polynomials of degree < M that
vanish to order J at 1 are exactly (a + b x)(x - 1)^J, a lattice of
rank 2. What is its least height (sup norm of the coefficients), what
attains it, how far above it does the next independent vector sit, and
is the least height the height of a product of factors x^d - 1?
THE OBJECTS. c_k = C(J, k), zero outside 0 <= k <= J. The coefficient
of x^k in (a + b x)(x - 1)^J is (-1)^(J-k) (a c_k - b c_{k-1}), so the
height is H(a, b) = max_k |a c_k - b c_{k-1}|, k = 0..J+1. N = c_m with
m = floor(J/2) is the row's largest entry, attained first at m, and
D = max_k |c_k - c_{k-1}| is the largest adjacent difference.
THE PROOF, written before the engine (theorem, every J >= 2).
(i) Symmetries. H(a, b) = H(-a, -b), and the row's palindrome
c_k = c_{J-k} sends index k to J + 1 - k and gives
H(a, b) = H(b, a).
(ii) D <= N - 1. For 1 <= k <= J the difference c_k - c_{k-1} is
below max(c_k, c_{k-1}) <= N in absolute value because both are
at least 1, and the end terms are c_0 = 1 and c_J = 1; N >= 2 at
J >= 2 finishes it. (At J = 1, N = 1 and (1, 0) ties (1, 1).)
(iii) Opposite signs or a zero coordinate. At k = m,
|a c_m - b c_{m-1}| = |a| N + |b| c_{m-1} >= N when a != 0, and
when a = 0 the index k = m + 1 gives |b| N >= N.
(iv) Same sign, a != b. By (i) take a > b >= 1. At k = m the row is
still strictly rising, c_{m-1} < c_m, so
a c_m - b c_{m-1} = (a - b) N + b (c_m - c_{m-1}) >= N + 1.
(v) a = b = t. H = |t| D.
So H >= N > D off the line a = b, H = |t| D on it, and the least
height is D, attained only at +-(1, 1): h(J + 2, J) = D with the
unique minimiser +-(1 + x)(x - 1)^J. Among vectors independent of
(1, 1), (iv) gives at least N + 1 and (iii) gives exactly N only
when |a| N + |b| c_{m-1} = N, i.e. (a, b) = +-(1, 0), or when a = 0
and |b| = 1; so the second minimum is lambda_2 = N, attained there
and nowhere else among independent vectors (a multiple t(1, 1) of
the minimiser reaches N too whenever tD = N).
(vi) The pure products at rank 2 with at least J parts and degree at
most J + 1 are (x - 1)^J, (x - 1)^(J+1) and (x - 1)^(J-1)(x^2 - 1),
cofactors 1, x - 1 and 1 + x, of heights N, C(J+1, floor((J+1)/2))
and D; so ph = D = h and no rank-2 cell fails.
THE SLATE (predictions, fixed before the run).
P1 A complete search of every (a, b) with H(a, b) <= N, at J = 2..16,
finds the minimum D at +-(1, 1) only, and the independent vectors
at height N exactly +-(1, 0), +-(0, 1).
P2 The general lattice route (flatten.py) prints h(J + 2, J) = D at
J = 2..30.
P3 (TRANSPLANT from an older record) The ratio
lambda_2 / lambda_1 = (sqrt(e)/2) sqrt(J + 1) (1 + eps_J) with
-1/(J + 1) < eps_J <= 5/(2(J + 1)) at every J = 2..4000, eps at
J = 10 near 0.0241 and at J = 2000 near 0.000075.
KILLS. K1: a pair other than +-(1, 1) at height <= D, or an
independent pair at height N other than the four. K2: an eps_J outside
its band. K3: the lattice route off D.
THE SEARCH (why it is complete). |a| = |a c_0| <= H, so |a| <= N; and
at k = m, |a N - b c_{m-1}| <= H confines b to an interval of length
2N / c_{m-1} around a N / c_{m-1}. Every pair in the box so cut is
scored.
CONTROL. The search at J = 2..16 must also find every multiple t(1, 1)
with tD <= N (a positive control on the search's reach).
FINDINGS (copied from the printed output).
F1 THE SEARCH (P1 holds, K1 never fired). At every J = 2..16 the
least height is D at +-(1, 1) alone and the independent vectors at
height N are exactly +-(1, 0), +-(0, 1): D, N = 1, 2 at J = 2;
90, 252 at J = 10; 3640, 12870 at J = 16. The control found every
multiple t(1, 1) with tD <= N; with the four independent vectors
they make the 6, 8 or 10 pairs at height <= N each depth prints.
F2 THE ROUTE (P2 holds, K3 never fired). The general lattice route
prints h(J + 2, J) = D at every J = 2..30.
F3 THE RATIO (P3 holds, K2 never fired). Over J = 2..4000,
(J + 1) eps_J lies in [-0.4166, 1.2022], inside (-1, 5/2]; eps is
+0.400723 at J = 2, +0.024105 at J = 10, -0.004146 at J = 99,
+0.008928 at J = 100 (the parity swing), +0.000075 at J = 2000
and +0.000038 at J = 4000, where (J + 1) eps reads 0.1504.
F4 THE HILL CLIMB equals the full row scan at every J = 2..300.
RUN RECORD. A first run walked the whole row at every depth and cost
389.5 s (peak working set 14.9 MB); the unimodal hill climb replaced it
with every figure unchanged, 2.2 s, peak 11.9 MB, under a memory guard.
"""
import sys
import time
from math import comb
from decimal import Decimal, getcontext
import flatten
getcontext().prec = 50
def row(J):
return [comb(J, k) for k in range(J + 1)]
def H(a, b, c):
J = len(c) - 1
best = 0
for k in range(J + 2):
ck = c[k] if k <= J else 0
ck1 = c[k - 1] if k >= 1 else 0
best = max(best, abs(a * ck - b * ck1))
return best
def step(n, k):
"""c_k - c_{k-1} for the row of J = n - 1, as C(n, k)(n - 2k)/n."""
return comb(n, k) * (n - 2 * k) // n
def minima(J):
"""(D, N). The step g(k) = C(n, k)(n - 2k)/n, n = J + 1, has
g(k+1)/g(k) = ((n - k)/(k + 1)) ((n - 2k - 2)/(n - 2k)) on
0 <= k < n/2 - 1, a product of two factors decreasing in k, so it is
unimodal on the rising half and a hill climb from any start finds
its maximum; the falling half mirrors it."""
n = J + 1
top = (n - 1) // 2 if n % 2 else n // 2 - 1
k = min(top, max(0, int(n / 2 - n ** 0.5 / 2)))
g = step(n, k)
while k < top and step(n, k + 1) > g:
k += 1
g = step(n, k)
while k > 0 and step(n, k - 1) > g:
k -= 1
g = step(n, k)
return max(g, 1), comb(J, J // 2)
def search(J):
"""Every (a, b) != (0, 0) with H(a, b) <= N, by the strip."""
c = row(J)
m = J // 2
N, cm1 = c[m], c[m - 1]
out = []
for a in range(-N, N + 1):
lo = (a * N - N) // cm1 - 1
hi = (a * N + N) // cm1 + 1
for b in range(lo, hi + 1):
if (a, b) != (0, 0):
v = H(a, b, c)
if v <= N:
out.append((v, a, b))
return out
def main():
t0 = time.time()
k1 = ctrl = 0
for J in range(2, 17):
D, N = minima(J)
found = search(J)
mins = [(a, b) for (v, a, b) in found if v == D]
low = [(a, b) for (v, a, b) in found if v < D]
indep = sorted((a, b) for (v, a, b) in found if a != b and v == N)
below = [(a, b) for (v, a, b) in found if a != b and v < N]
mult = sorted(a for (v, a, b) in found if a == b)
want = sorted(t for t in range(-N, N + 1) if t and abs(t) * D <= N)
if (low or sorted(mins) != [(-1, -1), (1, 1)] or below
or indep != [(-1, 0), (0, -1), (0, 1), (1, 0)]):
k1 += 1
if mult != want:
ctrl += 1
print("J=%2d D=%5d N=%5d pairs at height <= N: %3d minimisers %s"
" independent at N %s" % (J, D, N, len(found), sorted(mins),
indep))
print("P1: K1 fired %d times; control (multiples t(1,1), tD <= N) off %d"
% (k1, ctrl))
off = 0
for J in range(2, 301):
c = row(J)
full = max(abs(c[k] - (c[k - 1] if k else 0)) for k in range(J + 1))
if (full, c[J // 2]) != minima(J):
off += 1
print("control: the hill climb equals the full row scan at J = 2..300,"
" %d off" % off)
k3 = 0
for J in range(2, 31):
h, v, _ = flatten.least_height(J + 2, J)
if h != minima(J)[0]:
k3 += 1
print("K3 at J=%d: %d against %d" % (J, h, minima(J)[0]))
print("P2: the lattice route at J = 2..30, K3 fired %d times" % k3)
k2 = 0
lo_w = hi_w = None
c0 = Decimal(1).exp().sqrt() / 2
for J in range(2, 4001):
D, N = minima(J)
n = J + 1
eps = (Decimal(N) / Decimal(D)) / (c0 * Decimal(n).sqrt()) - 1
ne = float(eps * n)
if not (-1 < ne <= 2.5):
k2 += 1
print("K2 at J=%d: n eps = %.4f" % (J, ne))
lo_w = ne if lo_w is None else min(lo_w, ne)
hi_w = ne if hi_w is None else max(hi_w, ne)
if J in (2, 10, 99, 100, 2000, 4000):
print(" J=%4d eps=%+.6f (J+1) eps=%+.4f" % (J, eps, ne))
print("P3: J = 2..4000, K2 fired %d times; (J+1) eps in [%.4f, %.4f]"
% (k2, lo_w, hi_w))
print("wall %.1f s" % (time.time() - t0))
return k1 + ctrl + off + k3 + k2
if __name__ == "__main__":
sys.exit(1 if main() else 0)