# -*- coding: utf-8 -*- """ SELF-CONTAINED VERIFIER -- Prouhet-Tarry-Escott problem, symmetric ideal solutions over the 2-adic integers, SIZES n = 13 AND n = 15: the minimum of v_2(C) is EXACTLY 13 at n = 13 and EXACTLY 14 at n = 15. David Niedbala Giraudin, ORCID 0009-0009-1526-1178. Research and writing carried out with Claude (Anthropic). Pure Python 3 standard library: no numpy, no scipy, no sympy. No command-line argument. No intermediate file. Prints as it goes. Exponentiation is written with a double star; the file contains no circumflex. Run it in plain Python (not in a Sage cell). WHAT IS CHECKED 0 arithmetic self-test (refuses to start if a control value is wrong) 1 the two necessary conditions used by the search, on known witnesses: (R) row identity prod_i (a_j + a_i) = 2 prod_i a_i for EVERY j (F) odd power sums p_1 = p_3 = ... = p_{n-2} = 0 2 CALIBRATION, negative side: for n = 5, 7, 9, 11 every valuation profile below the published value is killed by the exhaustive lifting 3 CALIBRATION, positive side: the profiles of real witnesses are NOT killed 4 THE LOWER BOUND: for n = 13 all 98 profiles with t <= 11 are killed, hence v_2(C) >= 13; for n = 15 all 135 profiles with t <= 12 are killed, hence v_2(C) >= 14 5 THE UPPER BOUNDS: explicit 2-adic solutions with v_2(C) = 13 at n = 13 and v_2(C) = 14 at n = 15, certified by the multivariate Hensel lemma SETTINGS -- change nothing but these """ BUDGET_SECONDS = 540 # heavy positive calibrations are SKIPPED past it POSITIVE_LEVEL = 6 # level to which real witness profiles must survive import time T0 = time.time() PASS = [0] FAIL = [0] SKIP = [0] INF = 10 ** 9 def say(s=""): print(s, flush=True) def dit(nom, ok, detail=""): if ok: PASS[0] += 1 say(" PASS %-56s %s" % (nom, detail)) else: FAIL[0] += 1 say(" FAIL %-56s %s" % (nom, detail)) def saute(nom, why): SKIP[0] += 1 say(" SKIP %-56s %s" % (nom, why)) def reste(): return BUDGET_SECONDS - (time.time() - T0) def v2(x): if x == 0: return INF x = abs(int(x)) k = 0 while x % 2 == 0: x //= 2 k += 1 return k def check(a, L, n, V): """a: entries known mod 2**L (ints in [0, 2**L)). V = 1 + t. Returns False if a row is provably inconsistent.""" M = 1 << L units = [] for j in range(n): tot = 0 known = True vmax = 0 u = 1 for i in range(n): s = (a[j] + a[i]) % M if s == 0: known = False tot += L # lower bound continue v = v2(s) tot += v if v > vmax: vmax = v u = u * (s >> v) if tot > V: return False # valuation already too big (known part + lower bounds) if known: if tot != V: return False prec = L - vmax if prec > 0: units.append((u % (1 << prec), prec)) # pairwise unit agreement for x in range(len(units)): ux, px = units[x] for y in range(x + 1, len(units)): uy, py = units[y] p = min(px, py) if (ux - uy) % (1 << p): return False return True def setup(n, profile): u = len(profile) w = n - u val = list(profile) + [0] * w # entries 0..u-1 even, u..n-1 odd return val def children(a, L, n, val, norm_idx): """all extensions to level L+1 respecting valuations; entry norm_idx fixed to 1.""" free = [] base = list(a) for i in range(n): if i == norm_idx: continue # stays 1 if val[i] > 0 and L <= val[i]: if L == val[i]: base[i] = a[i] + (1 << L) continue free.append(i) nf = len(free) for mask in range(1 << nf): b = list(base) for q, i in enumerate(free): if (mask >> q) & 1: b[i] += 1 << L yield b def initial(n, val): # level 1: even entries 0, odd entries 1 return [0 if val[i] > 0 else 1 for i in range(n)] def Fok(b, L, n): M = 1 << L for j in range((n - 1) // 2): if sum(pow(x, 2 * j + 1, M) for x in b) % M: return False return True def canon(b, blocks): out = list(b) for idx in blocks: for i, x in zip(idx, sorted(b[i] for i in idx)): out[i] = x return tuple(out) def exhaust(n, profile, t, Lstop, budget): """Exhaustive lifting of ALL n entries, level by level, up to permutation inside each block of equal valuation. One odd entry is fixed to 1 (scaling by a 2-adic unit). Returns ('EMPTY', level) if no residue class survives.""" val = setup(n, profile) V = 1 + t norm = val.index(0) blocks = {} for i in range(n): if i != norm: blocks.setdefault(val[i], []).append(i) blocks = list(blocks.values()) front = {canon(initial(n, val), blocks)} L = 1 t1 = time.time() while L < Lstop: new = set() for a in front: for b in children(list(a), L, n, val, norm): if Fok(b, L + 1, n) and check(b, L + 1, n, V): new.add(canon(b, blocks)) if time.time() - t1 > budget: return 'BUDGET', L L += 1 if not new: return 'EMPTY', L front = new return 'ALIVE', L def parts(tt, u, mx=None): if mx is None: mx = tt if u == 0: if tt == 0: yield () return for c in range(min(tt - (u - 1), mx), 0, -1): for r in parts(tt - c, u - 1, c): yield (c,) + r def profiles(n, t): out = [] for u in range(1, n, 2): out.extend(parts(t, u)) return out say("=" * 78) say("VERIFIER -- PTE, 2-adic valuation, symmetric solutions, sizes 13 and 15") say("=" * 78) # ------------------------------------------------------------------ 0 say("0. ARITHMETIC SELF-TEST") ok0 = (v2(96) == 5 and v2(-40) == 3 and pow(3, 5, 16) == 3 and (7 * 7) % 8 == 1 and (1 << 10) == 1024 and 2 ** 10 == 1024 and v2(2 ** 40) == 40) dit("control values", ok0) if not ok0: say("Arithmetic is not what it should be (Sage preparser?). Run in plain Python.") input("Appuyez sur Entree pour fermer...") raise SystemExit # ------------------------------------------------------------------ 1 say() say("1. THE TWO CONDITIONS ON KNOWN INTEGER WITNESSES") say(" F(x) = prod (x - a_i) = x H(x**2) - c with c = prod a_i, so") say(" prod (x + a_i) - prod (x - a_i) = 2c; at x = a_j the second product") say(" vanishes: every row product equals 2 prod a_i. Conversely, equal row") say(" products at n distinct points force the degree <= n-1 difference to be") say(" constant, i.e. an ideal symmetric solution.") for nom, A in (("n=5 (9,5,1,-7,-8)", [9, 5, 1, -7, -8]), ("n=7", [-50, -38, -13, -7, 24, 33, 51]), ("Letac n=9", [-98, -82, -58, -34, 13, 16, 69, 75, 99])): n = len(A) P = 1 for a in A: P *= a rows = [] for j in range(n): r = 1 for i in range(n): r *= (A[j] + A[i]) rows.append(r) ps = [sum(a ** (2 * k + 1) for a in A) for k in range((n - 1) // 2)] dit("%s : rows all equal 2 prod a_i, odd power sums 0" % nom, all(r == 2 * P for r in rows) and all(p == 0 for p in ps), "v_2(C) = %d" % v2(2 * P)) # ------------------------------------------------------------------ 2 say() say("2. NEGATIVE CALIBRATION : below the published values everything dies") KNOWN = {5: 4, 7: 6, 9: 9, 11: 11} for n in (5, 7, 9, 11): tmax = KNOWN[n] - 2 tot = 0 morts = 0 t1 = time.time() for t in range(1, tmax + 1): for p in profiles(n, t): tot += 1 r = exhaust(n, p, t, 20, 60) if r[0] == 'EMPTY': morts += 1 else: say(" survivor n=%d t=%d %s : %s" % (n, t, list(p), r)) dit("n = %2d : all %3d profiles with t <= %2d killed" % (n, tot, tmax), morts == tot, "=> v_2(C) >= %d, published %d (%.1f s)" % (tmax + 2, KNOWN[n], time.time() - t1)) # ------------------------------------------------------------------ 3 say() say("3. POSITIVE CALIBRATION : real witness profiles are NOT killed") for n, t, p, nom in ((5, 3, (3,), "n=5"), (7, 5, (3, 1, 1), "n=7"), (9, 8, (4, 1, 1, 1, 1), "Letac n=9"), (11, 10, (4, 2, 2, 1, 1), "CMSV n=11"), (13, 16, (6, 3, 3, 1, 1, 1, 1), "known witness n=13, v_2 = 17"), (13, 12, (4, 2, 2, 1, 1, 1, 1), "new solution n=13, v_2 = 13")): if reste() < 90: saute(nom, "budget") continue r = exhaust(n, p, t, POSITIVE_LEVEL, min(150, reste() - 60)) dit("%s : survives to level %d" % (nom, POSITIVE_LEVEL), r[0] in ('ALIVE', 'BUDGET'), "%s at level %d" % r) # ------------------------------------------------------------------ 4 say() say("4. THE LOWER BOUND AT n = 13 : every profile with t <= 11 dies") tot = 0 morts = 0 pire = 0 t1 = time.time() for t in range(1, 12): for p in profiles(13, t): tot += 1 r = exhaust(13, p, t, 20, 120) if r[0] == 'EMPTY': morts += 1 pire = max(pire, r[1]) else: say(" SURVIVOR t=%d %s : %s" % (t, list(p), r)) say(" t = %2d : done" % t) dit("n = 13 : all %d profiles with t <= 11 killed" % tot, morts == tot and tot == 98, "deepest level needed %d (%.1f s)" % (pire, time.time() - t1)) # ------------------------------------------------------------------ 4b say() say("4b. THE LOWER BOUND AT n = 15 : every profile with t <= 12 dies") tot = 0 morts = 0 pire = 0 t1 = time.time() for t in range(1, 13): for p in profiles(15, t): tot += 1 r = exhaust(15, p, t, 20, 120) if r[0] == 'EMPTY': morts += 1 pire = max(pire, r[1]) else: say(" SURVIVOR t=%d %s : %s" % (t, list(p), r)) dit("n = 15 : all %d profiles with t <= 12 killed" % tot, morts == tot and tot == 135, "deepest level needed %d (%.1f s)" % (pire, time.time() - t1)) def certificate(n, SOL, PREC, expected_vals, expected_vC): MM = 1 << PREC m = (n - 1) // 2 A = [a % MM for a in SOL] ps = [sum(pow(a, 2 * k + 1, MM) for a in A) % MM for k in range(m)] dit("n = %d : odd power sums vanish modulo 2**%d" % (n, PREC), all(p == 0 for p in ps)) vals = sorted(v2(a) for a in SOL) dit("n = %d : valuations of the entries" % n, vals == expected_vals, str(vals)) prod = 1 for a in SOL: prod *= a rows = set() for j in range(n): r = 1 for i in range(n): r = (r * (A[j] + A[i])) % MM rows.add(r) dit("n = %d : all row products equal 2 prod a_i mod 2**%d" % (n, PREC), rows == {(2 * prod) % MM}) odd = [i for i in range(n) if SOL[i] % 2] best = None # the m odd entries giving the smallest Vandermonde valuation from itertools import combinations for S in combinations(odd, m): d = sum(v2(SOL[S[y]] ** 2 - SOL[S[x]] ** 2) for x in range(m) for y in range(x + 1, m)) d += sum(v2(2 * k + 1) for k in range(m)) if best is None or d < best: best = d d = best dit("n = %d : Hensel condition %d > 2 v(det) = %d" % (n, PREC, 2 * d), PREC > 2 * d, "v(det) = %d, exact root agrees mod 2**%d" % (d, PREC - d)) dit("n = %d : v_2(C) = v_2(2 prod a_i) = %d" % (n, expected_vC), v2(2 * prod) == expected_vC and 1 + sum(vals) == expected_vC) dit("n = %d : A and -A disjoint" % n, 0 not in rows) say() say("5. THE UPPER BOUNDS : explicit 2-adic solutions, certified by Hensel") say(" Jacobian of (p_1, p_3, ...) in m = (n-1)/2 odd entries, the others fixed:") say(" det = prod (2k+1) * prod_{x 2 v(det) the multivariate Hensel lemma gives a unique exact root") say(" congruent modulo 2**(PREC - v(det)), far above every valuation.") SOL13 = [ 577075787611596081614222155372426040086481465776, 265953577306952178338489589177580562983020965508, 131844351701341484814150568458050156618022128204, 1280983666965658343179028553570568857824066087430, 1111357347544673131043374849529370808195047159170, 5945734006198880350153664125161751583947444626, 729824892796177830967671866309321370181259428966, -295606039749444636222973364887069376307092653844137039397298797043478418364948140617080854826174410440441075859455, 133881368801340725118995005471855513819704553139956693148686041665774136658191351260121074081319474303767027581579, -559830736947530922471901056736421566040671073605571285050191575524104925271935270906525434113530067032917515968089, 547971526170149977909137256485642958618832173337683156948721524347597101217746859040285759434282626776065205898297, 1103377660538892703285348903421438096997844834761671629841270324235113894209351862536994395859387245643286144143327, -929793778813407847618606743755445627088617833789603155491187517685004773806339259244102031681827348797231630475339 ] certificate(13, SOL13, 380, [0] * 6 + [1, 1, 1, 1, 2, 2, 4], 13) SOL15 = [ 486131536110585306794145989522493624420798132133919680566092320, 641077421292785356989455606174730390497747765670397884932705636, 1514835295453770602743373124896796497083572517033388878280961404, 785605475230154278631457892119782778418496499092958126612268042, 987492714751724283508312642762196410753505561265738851591881746, 137947084724007694009256573140371665152036731501818460252165382, 30542077703875959027901474349289346376620257673786320020604382, -432576089284963532720312963739332093140196895081151809691843073448346224243750438682972823137853086437797735066056554928262784824665425575935999, -924490517696523758679924329321189677500445641389928140745340146506375681381754748661907086288125380436484260400610146075563032032094702412248329, -15227726953870218532987511455746214253205263412626610475657719236458273025884938647981083982935995252059590645552295983400883776089243756919883, -442714124538525168954140135411793864380562647166427209159609815434491376026790598709998390573867846678105143316209491982252307976499584407692587, 136849449137836210048993627603763422608071649382103962969636119921037016102988683536585467194881715512764118766575025060114072562816449536625127, 1248834608173654711027758141367764795214530958946338295700213351535600925219727744647015004472636514051390213494025473536880747004864914616957875, 667012321766849042959367329630240076907999439238723512083723841, 429324401162391757810613170956533631451807838721691511402601283169033613355464291268614985281511554577021764571927200761707285430935877658811043 ] certificate(15, SOL15, 480, [0] * 8 + [1, 1, 1, 1, 2, 2, 5], 14) # ------------------------------------------------------------------ summary say() say("=" * 78) say("SUMMARY: %d PASS, %d FAIL, %d SKIPPED (%.1f s)" % (PASS[0], FAIL[0], SKIP[0], time.time() - T0)) say("=" * 78) say(" n = 13 : min v_2(C) over symmetric ideal 2-adic solutions = 13") say(" (previous: lower bound 12, best witness 17)") say(" n = 15 : min v_2(C) over symmetric ideal 2-adic solutions = 14") say(" (previous: lower bound 14 in hexagon:2611.00058, no witness recorded)") input("Appuyez sur Entree pour fermer...")