"""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)