ideal.py
Checks: FLATTEN: The shortest vector is an ideal solution property.
Cited on: FLATTEN.
To run it: save ideal.py, with bandend.py, flatten.py, prunerr.py beside it; needs mpmath, numpy, sympy.
"""ideal.py -- the shortest vector of the flattened lattice as an ideal
Prouhet-Tarry-Escott solution: an exact sweep, symmetric or not, of the
repeat-free ideal solutions of size J and small span.
QUESTION. An ideal solution of size J is two disjoint multisets A, B of
J integers with equal power sums of every degree below J. Is there one
at J = 11, and how small can the span of one be at each J?
THE OBJECTS. L(M, J) is the lattice (x - 1)^J Z[x] cut at degree < M,
rank M - J (flatten.py's lattice). A vector c is the polynomial
sum c_i x^i; read as exponents, A holds i with multiplicity c_i > 0
and B holds i with multiplicity -c_i > 0.
THE HAND ATTACK.
(1) l1 >= 2J. A nonzero c in L(M, J) has c(1) = 0, so it is
sum_A x^a - sum_B x^b with A, B disjoint multisets of one size n,
l1 = 2n. Flattening to J is equal power sums for every degree
below J (flatten.py's moment identity), so by Newton's identities
the elementary symmetric functions e_1 .. e_(J-1) agree; n <= J - 1
would give prod(x - a) = prod(x - b), A = B, c = 0. So n >= J.
(2) l2^2 >= 2J. sum c^2 >= sum |c| >= 2J, equality iff every |c_i| <= 1
and n = J. So the least Euclidean norm^2 of L(M, J) is >= 2J
(flatten.py's least height reads the sup norm), with equality iff an
ideal solution of size J with no repeated element and span
<= M - 1 exists (property). The Euclidean ball of radius sqrt(2J)
holds exactly those solutions, at every shift that fits, one sign
each (the walk's sign symmetry): the sweep is exact for the
repeat-free class, and blind to solutions with a repeated element
(each element of multiplicity m adds m^2 - m >= 2 to l2^2).
(3) THE BOUNDARY. R^2 = 2J sits on the ball's boundary. Every squared
norm in L is an integer, so the walk prunes at R2 = 2J + 1/2,
which admits no further lattice vector, and prunerr.err_bound's
E (relative, independent of R) proves no vector lost where
(3E + 2E^2 + 4u) R2 < 1/2 and X R < 2^53 (prunerr's condition
(b)): printed per run as SAFE.
(4) THE DIVISORS. Write C = prod(x - a) - prod(x - b), a constant for
an ideal solution. A prime p | C makes A and B equal as multisets
modulo p, so P = sum x^a - sum x^b vanishes modulo x^p - 1 and
Phi_p | P. At a prime power q = p^u, P(zeta_q) is divisible by
(1 - zeta_q)^J, of norm p^J, while its norm is at most
(2J)^phi(q), each conjugate at most l1 = 2J; so p^J > (2J)^phi(q)
forces Phi_q | P (the FLOOR, which needs no solution's constant).
With the primes known to divide C for every solution of size J
(Table 1 of Coppersmith, Mossinghoff, Scheinerman and VanderKam,
arXiv 2304.11254, after Kleiman, Rees and Smyth, and Caley),
every ideal solution of size J lies in F_J Z[x], F_J the product
of (x - 1)^J, those Phi_p and the floor's Phi_q. At J = 11 the
primes are 2 .. 19 and the floor adds q = 4: deg F_11 = 82, so
every ideal solution of size 11, repeats or not, spans at least
82, and the RESTRICTED lattice F_J Z[x] cut at degree < M (rank
M - deg F_J) holds every solution L(M, J) holds.
(5) THE PLACE CONDITIONS, at J = 11: mod p > 11 the condition
(x - 1)^11 | c is the local ideal condition mod p, the
incumbent's; mod p <= 11 every layer is implied by the integer
moments, the deepest block (x^(p^k) - 1, p^k <= 11 largest) weaker
than the pairing p | C forces at 5, 7 and 11 and incomparable
with it at 2 and 3 (x^8 - 1, x^9 - 1). Neither is used here.
(6) THE CORNER. The restricted L at J = 11 holds vectors of squared
norm 28 (its reduced basis's: l1 28, every |c| = 1, flattened to
exactly 11, so size-14 multigrade, not ideal). L is shift-
invariant: a vector of span s sits in L(M, J) at exactly M - s
shifts, one sign each, so ball(28) on the kill's own basis, E and
X has a known answer at every shift: a vector lost at some but
not all of its form's shifts shows as a short count, and a form
lost at every shift only if the reduced basis holds it. The
count's PLANT: the walk rerun with the middle level's Gram-Schmidt
length inflated 1.5 times, a coarse emulated float loss (about
1e4 E), must come back short; it prints what it lost.
(7) THE REPEATS. With m_i = |c_i|, l2^2 = 2n + sum (m_i^2 - m_i),
the EXCESS the sum. A vector of l1 2J is an ideal solution of
size J by (1), so among the l1-2J vectors of the ball of squared
radius 2J + 2t are exactly the ideal solutions of size J, span
< M and excess <= 2t, each at all M - span shifts, one sign. Every
squared norm is even (c^2 = |c| mod 2). At t = 3: one, two or
three doubled elements, or one tripled; ball(28) at J = 11 is the
corner's. Witness: {0, 3, 3} = {1, 1, 4}, size 3, excess 4.
PREDICTIONS (fixed before the code).
CONTROL: least span 22 at J = 6 (M = 30) and 50 at J = 8 (M = 56),
the known {0,5,6,16,17,22} = {1,2,10,12,20,21} and
{0,4,9,23,27,41,46,50} = {1,2,11,20,30,39,48,49} among the
vectors, each rebuilt and checked by clears() with l1 = 2J.
A miss voids the run. Least spans at J = 2..5: 3, 6, 11, 18.
KILL: "J=11 M=140 ball(22): N vectors" with SAFE true. N = 0 answers
no for "a repeat-free ideal solution of size 11 exists at span
< 140" (expected: the least known spans at sizes 9, 10, 12, 198,
626 and 302, all symmetric, sit near 2n^2 or above).
SIDE ARMS: J = 9 and 10 at M = 100, under the least known 198 and 626.
NODES: growth near x1.25 per width at J = 11 (680 at M = 80, 4.5e6 at
M = 120 in pricing).
ARM R (fixed before its code): CONTROL R1, every solution read is
divisible by its F_J, and a prime planted in a C_J list misses;
CONTROL R2, the restricted ball prints what the full one does.
SCALE: every form found at all its M - span shifts, the span-50
solution at M - 50, the reduced basis's forms present, a dropped
vector caught; first frozen at J = 8 restricted M = 141, full
M = 137 and J = 9 restricted M = 199 (Letac's span-198 solution),
moved before its code onto the corner (6), the frozen arms priced
out of reach. A failure voids the J = 11 negatives.
REPEATS (7), fixed before its code. BRUTE, every ideal solution of
size J (repeats allowed) of span < M by power-sum signature, its
control the least spans at J = 2..6 and the witness. SMALL,
ball(2J + 6) on the full L(M, J), J = 3..6 (M = 12, 16, 22, 24),
and the restricted at J = 6: its l1-2J forms equal brute's of
excess <= 6, every form complete, every J = 6 brute solution
divisible by F_6; a form dropped prints equal False. KILL: an
l1-22 vector in the corner's ball(28) at M = 140, 150, 160;
expected none (seen unfrozen before: a recording).
CHANGED IN PREDICTIONS: the boundary was first a widening (1 + 1e-9)
R^2 + 1e-9, which failed its own bound at J = 8, M = 56, E 7.7e-10;
the integer gap (3) replaced it. Letac's smaller size-9 span was
first quoted as 197, it is 198 (-99..99). The KILL first read "an
ideal solution of size 11": the ball sees only repeat-free ones.
SCALE's dropped vector was caught by construction; the
inflated-length plant (6) replaced it after the run.
prunerr's condition (b), X R < 2^53, was added after the KILL's
run, and the KILL rerun under it. REPEATS: the frozen J = 6 width
30 became 24 (the brute's memory) before the code, 24 still
holding the least span 22; the frozen plant dropped one vector,
the code a whole form, either caught by construction once the
unplanted arm is equal: SMALL's control is the brute.
FINDINGS (copied from the prints).
CONTROL passed: least spans 3, 6, 11, 18, 22 at J = 2..6 and 50 at
J = 8, each solution checked by clears() and l1 = 2J; the frozen
two among them. SAFE true at every run.
KILL (as predicted): J = 11, M = 140, 0 vectors in the ball of squared
radius 22, SAFE (E 5.79e-03, X 9.00e+09), 2.3e8 nodes, 170.2 s.
SIDE ARMS: 0 vectors at J = 9 and 10, M = 100: none of span <= 99.
NODES: 2.3e8 at J = 11, M = 140 (the pricing's x1.25 per width was
not this walk's).
ARM R. R1, 0 misses: the six solutions read (size 8: the span-50 one;
9: Letac's two; 10: two of Borwein, Lisonek and Percival; 12: the
span-302 one) are each divisible by its F_J (deg F 43, 46, 75,
71); a planted 19 in C_9's list misses both of Letac's (PLANT 9
19: "R1: 2 misses", exit 1); a planted 29 in C_12's does not
fire, rightly (the solution read is symmetric, where 29 is
required; PLANT 12 29: 0 misses). R1 cannot read C_11's list (no
size-11 solution is known): that list rests on the table's read,
past 7 (the floor forces Phi_p for p <= 7 at J = 11 by itself).
R2: J = 8, M = 56 restricted (rank 13, 88 nodes) prints the same
one solution; J = 11, M = 140 restricted (rank 58) the same 0.
THE REACH: J = 11 restricted, 0 vectors at M = 140, 160, 180 (ranks
58, 78, 98; nodes 1.3e5, 7.0e6, 1.7e8; 117.6 s at 180; SAFE, E
2.45e-3 at 180): no repeat-free ideal solution of size 11 spans
179 or less. M = 200 passed a 300 s clock unread.
SCALE, 0 failures:
J = 8 restricted, M = 100 (rank 57, E 1.27e-07): span 50 at 50 of
50 shifts, 7 forms all complete, spans 50, 67, 68, 96, 96, 96,
97; M = 120 (rank 77, E 5.41e-05, 1.96e8 nodes): span 50 at 70
of 70, 9 forms all complete, adding 100, 100.
CORNER J = 11 restricted ball(28), M = 140, 150, 160 (ranks 58,
68, 78; E 3.41e-08, 5.20e-07, 7.92e-06): 107, 147, 187 vectors,
4 forms (spans 95, 98, 124, 136) all complete, the basis's 3
present, 0 wrong. Full, M = 110, 120 (ranks 99, 109; E 2.38e-06,
3.15e-05): 27, 47 vectors, 2 forms (95, 98) all complete.
SAFE at every arm. The DROP plant (one vector removed) was caught
by construction and read nothing; rerun with the inflated-length
plant (6) in its place, every line the same and "plant caught" at
all seven arms; what it lost printed from the bare run on: 19 and
23 vectors at M = 140 and 150, no form lost whole.
So the walk is controlled on the kill's own basis to M = 160 and
on the J = 11 lattices to rank 109, E 3.15e-05 (the J = 8 arm to
5.4e-05); the reach at M = 180 (E 2.45e-03), the full run at M =
140 (E 5.79e-03) and the side arms at J = 9, 10 rest on prunerr's
bound alone.
J = 9 restricted priced 6.5e7 nodes at M = 120, past 3e8 at 140;
J = 8 restricted x48 per 20 of width.
REPEATS. BRUTE passed: least repeat-free spans 3, 6, 11, 18, 22, the
witness found. SMALL equal and all complete at J = 3..6 full and
J = 6 restricted; brute forms of excess <= 6 by excess: J = 3
{0: 4, 2: 2, 4: 2}, J = 4 {0: 3, 2: 1, 4: 2}, J = 5 {0: 2}, J = 6
{0: 1, 6: 1}. Among excess <= 6 at those widths repeats shorten
the least span at J = 3, 4, 6 (observation): 4 against 6, 7
against 11 ({0, 3, 4, 7} = {1, 1, 6, 6}), 16 against 22 ({0, 3,
5, 11, 13, 16} = {1, 1, 8, 8, 15, 15}); none at J = 5 below 22.
Both J = 6 brute solutions divisible by F_6. PLANT: equal False
at J = 4 and 6. THE KILL: 0 l1-22 vectors at M = 140, 150, 160
(nodes 1.42e6, 1.76e7, 1.70e8; 160 in SCALE, whose full-lattice
corners at M = 110, 120 print 0 too), every form of the corner l1 28,
l2^2 28, flattened to 11 (spans 95, 98, 124) or 12 (136): no ideal
solution of size 11 with excess <= 6 spans 159 or less in
F_11 Z[x], and the ball holds no vector of l2^2 24 or 26.
RUN RECORD. Bare run (the claims' light arms): the CONTROL, R1,
REPEATS' BRUTE and SMALL, the reach at M = 140 and 160, the corner at
M = 140 and 150 (SCALE's adds 160). Frozen full
runs: 221.8 s, peak commit 14.8 MB. SCALE: 635.1 s with the plant's
walks, peak commit 16.6 MB.
Usage: python ideal.py (the light arms; exit 1 on a failure)
python ideal.py FULL (the frozen full runs, J = 9..11)
python ideal.py R J M ... (the restricted ball; R1 first)
python ideal.py SCALE (the control at scale)
python ideal.py PLANT J p (R1 with the prime p planted in C_J)
"""
import os
import sys
import time
from itertools import combinations_with_replacement
os.environ.setdefault("OPENBLAS_NUM_THREADS", "1")
from flatten import lll, basis, clears, phi, pdivmod, pow_xm1 # noqa: E402
from prunerr import err_bound, U # noqa: E402
CAP = 2 * 10 ** 9
# THE DIVISORS (4): known primes of the constant C for every ideal
# solution of size J (2304.11254 Table 1), each forcing Phi_p | P; the
# floor's prime powers q (p^J > (2J)^phi(q)) are floor_powers'.
CPRIMES = {6: (2, 3, 5), 8: (2, 3, 5, 7, 11, 13), 9: (2, 3, 5, 7, 11, 13),
10: (2, 3, 5, 7, 13, 17, 23), 11: (2, 3, 5, 7, 11, 13, 17, 19),
12: (2, 3, 5, 7, 11, 17, 19)}
KNOWN = { # ideal solutions read off 2304.11254 (3)-(7) and the controls
8: [([0, 4, 9, 23, 27, 41, 46, 50], [1, 2, 11, 20, 30, 39, 48, 49])],
9: [([-98, -82, -58, -34, 13, 16, 69, 75, 99],
[98, 82, 58, 34, -13, -16, -69, -75, -99]),
([-174, -148, -132, -50, -8, 63, 119, 161, 169],
[174, 148, 132, 50, 8, -63, -119, -161, -169])],
10: [([s * a for a in (99, 100, 188, 301, 313) for s in (1, -1)],
[s * a for a in (71, 131, 180, 307, 308) for s in (1, -1)]),
([s * a for a in (103, 189, 366, 452, 515) for s in (1, -1)],
[s * a for a in (18, 245, 331, 471, 508) for s in (1, -1)])],
12: [([s * a for a in (22, 61, 86, 127, 140, 151) for s in (1, -1)],
[s * a for a in (35, 47, 94, 121, 146, 148) for s in (1, -1)])],
}
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 floor_powers(J, top=64):
"""Prime powers q = p^u, u >= 2, with p^J > (2J)^phi(q)."""
out = []
for p in (2, 3, 5, 7):
q = p * p
while q <= top:
if p ** J > (2 * J) ** (q - q // p):
out.append(q)
q *= p
return out
def factor_F(J):
"""F_J = (x - 1)^J prod Phi_p (p | C_J known) prod Phi_q (floor)."""
F = pow_xm1(J)
for n in tuple(CPRIMES[J]) + tuple(floor_powers(J)):
F = pmul(F, phi(n))
return F
def divides(F, A, B):
lo = min(A + B)
P = [0] * (max(A + B) - lo + 1)
for a in A:
P[a - lo] += 1
for b in B:
P[b - lo] -= 1
_, r = pdivmod(P, F)
return all(c == 0 for c in r), max(A + B) - lo
def rbasis(M, F):
rows = []
for i in range(M - len(F) + 1):
v = [0] * M
v[i:i + len(F)] = F
rows.append(v)
return rows
class Cap(Exception):
pass
def ball(b, d, lam, M, R2, cap=CAP, inflate=None):
"""Every nonzero lattice vector of squared norm <= R2, one sign each,
by flatten.enumerate_min's Schnorr-Euchner walk at a fixed radius.
inflate=(k, f): the PLANT, level k's Gram-Schmidt length scaled by f,
an emulated float loss."""
n = len(b)
Bs = [d[i + 1] / d[i] for i in range(n)]
if inflate:
Bs[inflate[0]] *= inflate[1]
mu = [[lam[k][j] / d[j + 1] for j in range(k)] for k in range(n)]
R = R2 + 0.5
out, nodes, x = [], [0], [0] * n
def rec(i, partial, top):
c = 0.0
if not top:
for j in range(i + 1, n):
if x[j]:
c -= mu[j][i] * x[j]
x0 = round(c)
s = 1 if c >= x0 else -1
t = 0
while True:
if top:
xi = t
elif t == 0:
xi = x0
elif t % 2 == 1:
xi = x0 + s * ((t + 1) // 2)
else:
xi = x0 - s * (t // 2)
t += 1
nodes[0] += 1
if nodes[0] > cap:
raise Cap
y = xi - c
p = partial + y * y * Bs[i]
if p > R:
break
x[i] = xi
if i == 0:
if not (top and xi == 0):
v = [0] * M
for k in range(n):
if x[k]:
bk, xk = b[k], x[k]
for tt in range(M):
v[tt] += xk * bk[tt]
out.append(v)
else:
rec(i - 1, p, top and xi == 0)
x[i] = 0
rec(n - 1, 0.0, True)
return out, nodes[0]
def sides(v):
A = [i for i, c in enumerate(v) for _ in range(max(c, 0))]
B = [i for i, c in enumerate(v) for _ in range(max(-c, 0))]
return A, B
def normal(v):
"""The solution up to shift and sign: (A - min, B - min), A holding 0."""
A, B = sides(v)
lo = min(A + B)
A, B = [a - lo for a in A], [b - lo for b in B]
if 0 not in A:
A, B = B, A
return tuple(A), tuple(B)
def sweep(J, M, cap=CAP, restrict=False):
t0 = time.time()
rows = rbasis(M, factor_F(J)) if restrict else basis(M, J)
tag = f"R deg F {len(factor_F(J)) - 1} rank {len(rows)}" if restrict else ""
if not rows:
print(f"J={J} M={M} {tag}: rank 0, no vector")
return [], [], [], True
b, d, lam = lll(rows)
E, X = err_bound(d, lam, len(b))
safe = ((3 * E + 2 * E * E + 4 * U) * (2 * J + 0.5) < 0.5
and X * (2 * J + 0.5) ** 0.5 < 2 ** 53) # prunerr's (b)
try:
out, nodes = ball(b, d, lam, M, 2 * J, cap)
except Cap:
print(f"J={J} M={M} {tag} ball({2 * J}): CAP {cap} nodes, "
f"{time.time() - t0:.1f} s")
return None
ok = [v for v in out if sum(abs(c) for c in v) == 2 * J
and sum(c * c for c in v) == 2 * J and clears(v, J)]
sols = sorted({normal(v) for v in ok}, key=lambda s: (max(s[0] + s[1]), s))
print(f"J={J} M={M} {tag} ball({2 * J}): {len(out)} vectors, {len(ok)} checked "
f"ideal, {len(sols)} up to shift; nodes {nodes}; "
f"SAFE {safe} (E {float(E):.2e}, X {float(X):.2e}); {time.time() - t0:.1f} s")
if sols:
print(f" least span {max(sols[0][0] + sols[0][1])}")
for A, B in sols[:6]:
print(f" span {max(A + B)}: {list(A)} = {list(B)}")
return out, ok, sols, safe
def shifts(M, ok):
"""Per solution up to shift and sign: (span, vectors found, M - span).
A solution of span s sits in L(M, J) at exactly M - s shifts, one sign
each, so a vector the walk lost shows as a short count."""
cnt = {}
for v in ok:
f = normal(v)
cnt[f] = cnt.get(f, 0) + 1
return {f: (max(f[0] + f[1]), c, M - max(f[0] + f[1])) for f, c in cnt.items()}
SPAN50 = ((0, 4, 9, 23, 27, 41, 46, 50), (1, 2, 11, 20, 30, 39, 48, 49))
def complete(M, tab):
return sorted((s, c, e) for s, c, e in tab.values() if c != e)
def planted(b, d, lam, M, R2, out, cap=CAP):
"""The plant: the walk with the middle level's Gram-Schmidt length
inflated 1.5 times must come back short at some shift. Against the
unplanted walk's out: (caught, vectors lost, forms lost whole), a
form lost at every shift being one the count cannot see."""
tab = shifts(M, out)
out2, _ = ball(b, d, lam, M, R2, cap, (len(b) // 2, 1.5))
tab2 = shifts(M, out2)
return (bool(complete(M, tab2)), len(out) - len(out2),
len(set(tab) - set(tab2)))
def said(pl):
return (f"plant {'caught' if pl[0] else 'MISSED'} ({pl[1]} lost, "
f"{pl[2]} forms whole)")
def corner(J, M, R2, cap=CAP, restrict=True):
"""The positive control on the kill's own lattice: the restricted
L(M, J) at squared radius R2, where vectors exist, on the same basis,
E and X. The lattice is shift-invariant, so every vector found must
show at all M - span shifts, and the reduced basis's own vectors of
squared norm <= R2 must be among them. restrict=False: the full
L(M, J)."""
t0 = time.time()
tag = "R" if restrict else "full"
b, d, lam = lll(rbasis(M, factor_F(J)) if restrict else basis(M, J))
E, X = err_bound(d, lam, len(b))
safe = ((3 * E + 2 * E * E + 4 * U) * (R2 + 0.5) < 0.5
and X * (R2 + 0.5) ** 0.5 < 2 ** 53)
known = {normal(v) for v in b if sum(c * c for c in v) <= R2}
try:
out, nodes = ball(b, d, lam, M, R2, cap)
except Cap:
print(f"CORNER J={J} M={M} {tag} ball({R2}): CAP {cap} nodes, "
f"{time.time() - t0:.1f} s")
return None
wrong = [v for v in out if sum(c * c for c in v) > R2 or not clears(v, J)]
kill = [v for v in out if sum(abs(c) for c in v) == 2 * J] # (7)
tab = shifts(M, out)
bad = complete(M, tab)
miss = known - set(tab)
pl = planted(b, d, lam, M, R2, out, cap)
print(f"CORNER J={J} M={M} {tag} ball({R2}) rank {len(b)}: l1-{2 * J} vectors "
f"{len(kill)}; {len(out)} vectors, {len(tab)} forms, "
f"{'all complete' if not bad else f'INCOMPLETE {bad[:5]}'}; "
f"basis forms {len(known) - len(miss)} of {len(known)} present; "
f"{len(wrong)} wrong; {said(pl)}; "
f"nodes {nodes}; SAFE {safe} (E {float(E):.2e}, X {float(X):.2e}); "
f"{time.time() - t0:.1f} s")
rep = {}
for v in out:
rep.setdefault(normal(v), v)
for f, v in sorted(rep.items(), key=lambda kv: max(kv[0][0] + kv[0][1])):
print(f" form span {max(f[0] + f[1])}: l1 {sum(abs(c) for c in v)}, "
f"l2^2 {sum(c * c for c in v)}, flattened to {depth(v)}, "
f"at {tab[f][1]} of {tab[f][2]} shifts")
for v in kill:
print(f" KILL: {sides(v)}")
return int(bool(bad) or bool(miss) or bool(wrong) or not pl[0] or not safe
or bool(kill))
CORNERS = [(140, True), (150, True), (160, True), (110, False), (120, False)]
def scale(corners=CORNERS, cap=CAP):
"""The control at scale: J = 8 restricted at M = 100 and 120, every
solution at all its shifts and the span-50 one at M - 50; then the
corner, ball(28) on the J = 11 lattice, restricted or full, at each
(M, restrict)."""
fail = 0
for M in (100, 120):
r = sweep(8, M, restrict=True)
if r is None:
fail += 1
continue
_, ok, _, safe = r
tab = shifts(M, ok)
n50 = tab.get(SPAN50, (50, 0, M - 50))[1]
bad = complete(M, tab)
b, d, lam = lll(rbasis(M, factor_F(8)))
pl = planted(b, d, lam, M, 16, ok)
print(f"SCALE J=8 M={M} R: span 50 at {n50} of {M - 50} shifts; "
f"{len(tab)} forms, "
f"{'all complete' if not bad else f'INCOMPLETE {bad[:5]}'}; "
f"{said(pl)}; SAFE {safe}")
print(f" spans of the forms: {sorted(s for s, _, _ in tab.values())}")
fail += bool(bad) or n50 != M - 50 or not pl[0] or not safe
for M, restrict in corners:
r = corner(11, M, 28, cap, restrict)
fail += 1 if r is None else r
return fail
FROZEN = [(2, 12), (3, 12), (4, 20), (5, 26), (6, 30), (8, 56),
(9, 100), (10, 100), (11, 140)]
def control_r1(plant=None):
"""Every known solution divisible by its F_J (arm R's CONTROL R1);
plant=(J, p) adds the prime p to C_J's list, the PLANT."""
bad = 0
for J, sols in sorted(KNOWN.items()):
F = factor_F(J)
if plant and plant[0] == J:
F = pmul(F, phi(plant[1]))
for A, B in sols:
ok, span = divides(F, A, B)
bad += not ok
print(f"R1 J={J} span {span} deg F {len(F) - 1} "
f"floor {floor_powers(J)}: F_J divides {ok}")
print(f"R1: {bad} misses")
return bad
LEAST = {2: 3, 3: 6, 4: 11, 5: 18, 6: 22, 8: 50}
LIGHT = [(2, 12), (3, 12), (4, 20), (5, 26), (6, 30), (8, 56)]
NONE = {9: 100, 10: 100, 11: 180} # the widths the claims read empty
def verdict(J, M, restrict=False):
"""1 on a failure: the least span not LEAST[J] where it is below M,
any vector where the claims read none (J in NONE, M at most its
width), SAFE false, or the cap; elsewhere the run is unchecked."""
r = sweep(J, M, restrict=restrict)
if r is None:
return 1
_, ok, sols, safe = r
got = max(sols[0][0] + sols[0][1]) if sols else None
if J in LEAST:
return int(got != (LEAST[J] if LEAST[J] < M else None) or not safe)
if J in NONE and M <= NONE[J]:
return int(bool(r[0]) or not safe)
print(f" J={J} M={M}: unchecked")
return 0
# ----------------------------------------------- the repeats (7)
def excess(A, B):
m = {}
for a in A + B:
m[a] = m.get(a, 0) + 1
return sum(k * k - k for k in m.values())
def vec(A, B, M):
v = [0] * M
for a in A:
v[a] += 1
for b in B:
v[b] -= 1
return v
def depth(v):
k = 0
while clears(v, k + 1):
k += 1
return k
def brute(J, M):
"""Every ideal solution of size J, repeats allowed, span < M, up to
shift and sign, by power-sum signature: normal forms."""
groups = {}
for S in combinations_with_replacement(range(M), J):
key = tuple(sum(a ** k for a in S) for k in range(1, J))
groups.setdefault(key, []).append(S)
out = set()
for L in groups.values():
for i in range(len(L)):
for j in range(i + 1, len(L)):
S, T = L[i], L[j]
if not set(S) & set(T) and min(S + T) == 0:
out.add(normal(vec(S, T, M)))
return out
def brute_control():
"""BRUTE's control: the repeat-free least spans and the witness."""
fail = 0
for J, M in ((2, 8), (3, 10), (4, 14), (5, 20), (6, 24)):
sols = brute(J, M)
free = [s for s in sols if excess(list(s[0]), list(s[1])) == 0]
least = min(max(A + B) for A, B in free) if free else None
ok = least == LEAST[J]
if J == 3:
ok = ok and ((0, 3, 3), (1, 1, 4)) in sols
print(f"BRUTE J={J} M={M}: {len(sols)} solutions, {len(free)} "
f"repeat-free, least repeat-free span {least}"
f"{', witness found' if J == 3 and ok else ''}: "
f"{'ok' if ok else 'FAIL'}")
fail += not ok
return fail
def small(J, M, restrict=False, plant=False):
"""ball(2J + 6) on L(M, J): its l1-2J forms against brute's of
excess <= 6. plant=True drops a form and must break the equality."""
b, d, lam = lll(rbasis(M, factor_F(J)) if restrict else basis(M, J))
out, nodes = ball(b, d, lam, M, 2 * J + 6)
got_v = [v for v in out if sum(abs(c) for c in v) == 2 * J]
if plant and got_v:
f0 = normal(got_v[0])
got_v = [v for v in got_v if normal(v) != f0]
tab = shifts(M, got_v)
bad = complete(M, tab)
sols = brute(J, M)
want = {s for s in sols if excess(list(s[0]), list(s[1])) <= 6}
eq = set(tab) == want
print(f"SMALL J={J} M={M} {'R' if restrict else 'full'}"
f"{' PLANT' if plant else ''} ball({2 * J + 6}) rank {len(b)}: "
f"l1-{2 * J} forms {len(tab)}, brute's of excess <= 6 {len(want)}, "
f"equal {eq}; {'all complete' if not bad else f'INCOMPLETE {bad[:3]}'}; "
f"nodes {nodes}")
if plant:
return int(eq)
byx = {}
for A, B in want:
x = excess(list(A), list(B))
byx[x] = byx.get(x, 0) + 1
print(f" by excess: {dict(sorted(byx.items()))}")
for A, B in sorted(want, key=lambda s: (max(s[0] + s[1]), s))[:1]:
print(f" least span {max(A + B)}, excess {excess(list(A), list(B))}: "
f"{list(A)} = {list(B)}")
r1 = 0
if J == 6:
r1 = sum(not divides(factor_F(6), list(A), list(B))[0] for A, B in sols)
print(f" R1: {r1} of {len(sols)} brute solutions not divisible by F_6")
return int(not eq or bool(bad) or bool(r1))
def repeats():
fail = brute_control()
for J, M in ((3, 12), (4, 16), (5, 22), (6, 24)):
fail += small(J, M)
fail += small(6, 24, restrict=True)
fail += small(4, 16, plant=True) + small(6, 24, plant=True)
return fail
def light():
"""The claims' light arms: the CONTROL's least spans, R1, the
repeats' BRUTE and SMALL, the reach at M = 140 and 160, and the
corner at M = 140 and 150."""
fail = sum(verdict(J, M) for J, M in LIGHT)
fail += bool(control_r1())
fail += repeats()
fail += sum(verdict(11, M, True) for M in (140, 160))
for M in (140, 150):
r = corner(11, M, 28)
fail += 1 if r is None else r
return fail
if __name__ == "__main__":
sys.setrecursionlimit(10000)
args = sys.argv[1:]
if args == ["SCALE"]:
f = scale()
elif args == ["FULL"]:
f = sum(verdict(J, M) for J, M in FROZEN)
elif args and args[0] == "PLANT":
f = control_r1((int(args[1]), int(args[2])))
elif args and args[0] == "R":
f = control_r1()
a = [int(t) for t in args[1:]]
f += sum(verdict(J, M, True) for J, M in zip(a[::2], a[1::2]))
else:
f = light()
print(f"ideal: {f} failures")
sys.exit(1 if f else 0)