#!/usr/bin/env python3 # Verifier for the numerical assertions of the odd-size sections of # "The 2-adic valuation of the constant for symmetric ideal Prouhet-Tarry-Escott solutions" # David Niedbala Giraudin, ORCID 0009-0009-1526-1178. # Technical assistance: Claude (Anthropic). # Pure Python 3, no dependency. Runs in a few seconds. # No command-line argument. No intermediate file. Prints as it goes. PASS_N = 0 FAIL_N = 0 def OK(b): global PASS_N, FAIL_N if b: PASS_N += 1 else: FAIL_N += 1 return "PASS " if b else "FAIL " def v2(x, cap=500): if x == 0: return cap v = 0 while x % 2 == 0: x //= 2; v += 1 return v def vfact(n): s = 0; p = 2 while p <= n: s += n // p; p *= 2 return s def sval(n): s = 0 for k in range(3, n - 1, 2): s = max(s, min(2 + v2(k - 1), k)) return s print("=" * 72, flush=True) print("1. THE SOLUTIONS CITED ARE INDEED SYMMETRIC IDEAL SOLUTIONS") print("=" * 72) for nm, A, n, texp, prof in ( ("(9,5,1,-7,-8)", [9,5,1,-7,-8], 5, 3, (3,)), ("n=7", [-50,-38,-13,-7,24,33,51], 7, 5, (3,1,1)), ("Letac I", [-98,-82,-58,-34,13,16,69,75,99], 9, 8, (4,1,1,1,1))): good = all(sum(a**k for a in A) == 0 for k in range(1, n - 1, 2)) E = [a for a in A if a % 2 == 0]; t = sum(v2(a) for a in E) pr = tuple(sorted((v2(a) for a in E), reverse=True)) print(" %s %-16s odd moments vanish=%s t=%d profile=%s v_2(C)=%d" % (OK(good and t == texp and pr == prof), nm, good, t, pr, t + 1), flush=True) print() print("=" * 72) print("2. THE TWO QUADRATIC WITNESSES OF SIZE 11") print("=" * 72) def sqrt2(d, P): s = 1 for m in range(3, P): if (s * s - d) % (1 << (m + 1)): s += 1 << (m - 1) return s % (1 << P) K = 60; M = 1 << K for nm, d, root, mk in ( ("A1", 26601, lambda s: (s - 163) // 2, lambda a: [-95, -68 - a, -52, -48, -13, -9, 30, 34, 61, 65, 95 + a]), ("A2", 400569, lambda s: (633 - s) // 2, lambda a: [-589, -546 + a, -363, -185, -170, 41, 87 - a, 234, 355, 548, 588])): print(" %s : discriminant %d = %d mod 8, so 2 splits" % (nm, d, d % 8), flush=True) s0 = sqrt2(d, K + 8) for sg in (1, -1): a = root(sg * s0) % M; A = [x % M for x in mk(a)] cong = [sum(pow(x, k, M) for x in A) % M for k in (1, 3, 5, 7, 9)] O = [x for x in A if x % 2]; E = [x for x in A if x % 2 == 0] t = sum(v2(x) for x in E) pr = tuple(sorted((v2(x) for x in E), reverse=True)) rO = [sum(v2(O[i] + O[j]) for j in range(len(O)) if j != i) for i in range(len(O))] rE = [sum(v2(E[i] + E[j]) if i != j else v2(2 * E[i]) for j in range(len(E))) for i in range(len(E))] good = (not any(cong)) and len(O) == 6 and len(E) == 5 and t == 10 \ and pr == (4,2,2,1,1) and all(r == 10 for r in rO) and all(r == 11 for r in rE) print(" %s embedding %+d : w=%d u=%d t=%d tau=%d profile=%s v_2(C)=%d" % (OK(good), sg, len(O), len(E), t, t - (len(O) - 1), pr, t + 1), flush=True) print() print("=" * 72) print("3. THE TWO CONGRUENCES THAT KILL THE PROFILE (5,1,1) AT n=11") print("=" * 72) # a1 = 32 b1, a2 = 2 b2, a3 = 2 b3, v_2(a2 + a3) = 5. Delta^m E (m = 3, 4) depends on the # a_i modulo 2**12 only, so b1 runs over the odd residues modulo 2**7 and b2, b3 over the odd # residues modulo 2**11: this is exhaustive. Matching is done through a table. g = lambda a, m, M: (a * pow((a * a - 1) % M, m, M)) % M M3, M4 = 8**3, 8**4 tab, t3, t4 = {}, {}, {} for b3 in range(1, 2048, 2): a3 = 2 * b3 tab.setdefault((g(a3, 3, M3), g(a3, 4, M4)), []).append(b3) t3.setdefault(g(a3, 3, M3), []).append(b3) t4.setdefault(g(a3, 4, M4), []).append(b3) tot = n3 = n4 = both = 0 for b1 in range(1, 128, 2): a1 = 32 * b1 for b2 in range(1, 2048, 2): a2 = 2 * b2 k3 = (-g(a1, 3, M3) - g(a2, 3, M3)) % M3 k4 = (-g(a1, 4, M4) - g(a2, 4, M4)) % M4 tot += sum(1 for b3 in range(1, 2048, 2) if v2(b2 + b3) == 4) if b1 == 1 else 0 n3 += sum(1 for b3 in t3.get(k3, []) if v2(b2 + b3) == 4) n4 += sum(1 for b3 in t4.get(k4, []) if v2(b2 + b3) == 4) both += sum(1 for b3 in tab.get((k3, k4), []) if v2(b2 + b3) == 4) print(" %s %d triples (b1 mod 2**7, b2, b3 mod 2**11) with v_2(b2+b3)=4 : m=3 : %d ; m=4 : %d ; both : %d" % (OK(both == 0 and n3 > 0 and n4 > 0), tot * 64, n3, n4, both), flush=True) print() print("=" * 72) print("3b. THE SAME TWO CONGRUENCES KILL THE PROFILE (3,2,2) AT n=11") print("=" * 72) # a1 = 8 b1, a2 = 4 b2, a3 = 4 b3, v_2(a2 + a3) = 3. Delta^m E depends on the a_i modulo 2**12 # only, so b1 runs over the odd residues modulo 2**9 and b2, b3 over the odd residues modulo # 2**10: this is exhaustive. Matching is done through a table indexed by the residues. g = lambda a, m, M: (a * pow((a * a - 1) % M, m, M)) % M M3, M4 = 8**3, 8**4 tab = {} t3, t4 = {}, {} for b3 in range(1, 1024, 2): a3 = 4 * b3 tab.setdefault((g(a3, 3, M3), g(a3, 4, M4)), []).append(b3) t3.setdefault(g(a3, 3, M3), []).append(b3) t4.setdefault(g(a3, 4, M4), []).append(b3) tot = hit3 = hit4 = both = 0 for b1 in range(1, 512, 2): a1 = 8 * b1 for b2 in range(1, 1024, 2): a2 = 4 * b2 k3 = (-g(a1, 3, M3) - g(a2, 3, M3)) % M3 k4 = (-g(a1, 4, M4) - g(a2, 4, M4)) % M4 tot += 512 hit3 += sum(1 for b3 in t3.get(k3, []) if v2(b2 + b3) == 1) hit4 += sum(1 for b3 in t4.get(k4, []) if v2(b2 + b3) == 1) for b3 in tab.get((k3, k4), []): if v2(b2 + b3) == 1: both += 1 print(" %s %d triples (b1 mod 2**9, b2, b3 mod 2**10) with v_2(b2+b3)=1 : m=3 : %d ; m=4 : %d ; both : %d" % (OK(both == 0 and hit3 > 0 and hit4 > 0), tot // 2, hit3, hit4, both), flush=True) print() print("=" * 72) print("4. THE 2-ADIC WITNESS OF SIZE 13 AND ITS CERTIFICATE") print("=" * 72) ints = [-1827, -989, -715, -405, 64, 902, 1330, 1640] c = [0, -4278125, 0, 3664306448884, -975527373189600] e = [1] + [((-1)**i) * c[i-1] for i in range(1, 6)]; p = [] for k in range(1, 12): if k <= 5: s_ = sum(((-1)**(i-1)) * e[i] * p[k-i-1] for i in range(1, k)) + ((-1)**(k-1)) * k * e[k] else: s_ = sum(((-1)**(i-1)) * e[i] * p[k-i-1] for i in range(1, 6)) p.append(s_) tot13 = [sum(a**k for a in ints) + p[k-1] for k in (1,3,5,7,9,11)] print(" %s moment identities p_1,p_3,...,p_11 : %s" % (OK(not any(tot13)), tot13), flush=True) f = lambda x: (((((x + c[0]) * x + c[1]) * x + c[2]) * x + c[3]) * x + c[4]) fp = lambda x: ((((5 * x + 4 * c[0]) * x + 3 * c[1]) * x + 2 * c[2]) * x + c[3]) cert = [2723974027, 1263895509, 3276945658, 3386758734, 2233327960] for r in cert: a_, b_ = v2(f(r)), v2(fp(r)); h = a_ > 2 * b_ print(" %s r=%-11d v_2(f(r))=%-3d v_2(f'(r))=%-2d Hensel=%s v_2(r)=%d" % (OK(h), r, a_, b_, h, v2(r)), flush=True) dist = all(v2(cert[i] - cert[j]) < 32 for i in range(5) for j in range(i+1, 5)) t13 = sum(v2(a) for a in ints) + sum(v2(r) for r in cert) print(" %s roots pairwise distinct mod 2 to the 32 ; t = %d so v_2(C) = %d" % (OK(dist and t13 == 16), t13, t13 + 1), flush=True) print() print("=" * 72) print("5. THE CHAIN : 2-ADIC MINIMUM BY ODD SIZE") print("=" * 72) def partitions(t, u, mx=None): if mx is None: mx = t if u == 0: if t == 0: yield () return for cc in range(min(t - (u - 1), mx), 0, -1): for r in partitions(t - cc, u - 1, cc): yield (cc,) + r def rowbal(pr, t): for j in range(len(pr)): L = pr[j] + 1 for i in range(len(pr)): if i != j: L += min(pr[i], pr[j]) if pr[i] != pr[j] else pr[j] + 1 if L > 1 + t: return False return True def chain(n): s = sval(n); mm = (n - 3) // 2 for t in range(1, 5 * n): for w in range(2, n, 2): u = n - w if u < 1 or u % 2 == 0: continue tau = t - (w - 1) if tau < 0: continue h = w // 2 ok = (tau >= max(2, s - 1)) if w == 2 else \ ((tau == 0 and w % 4 == 0) or (tau == h and h % 2 == 0) or tau >= h + (-(-h // 2))) if not ok: continue if u >= 2 and t < u: continue for pr in partitions(t, u): if pr.count(1) % 2: continue cm = min(pr) if pr.count(cm) % 2 and cm < 3 * mm: continue if rowbal(pr, t): return t return None EXP = {5:4, 7:6, 9:9, 11:8, 13:12, 15:12, 17:12, 19:12, 21:16} print(" n chain expected Kleiman") for n in sorted(EXP): v = chain(n) + 1 note = " (the two remaining slots (5,1,1), (3,2,2) are killed in 3 and 3b : 11)" if n == 11 else "" print(" %s %-4d %-7d %-8d %-7d%s" % (OK(v == EXP[n]), n, v, EXP[n], vfact(n - 1), note), flush=True) print() print("=" * 72) print("SUMMARY : %d PASS, %d FAIL" % (PASS_N, FAIL_N)) print("=" * 72)