""" verify_pte_chebyshev.py -- ancillary file for "A Chebyshev bound for the constant in the Prouhet-Tarry-Escott problem" David Niedbala Giraudin, ORCID 0009-0009-1526-1178. Technical assistance: Claude (Anthropic). Replays, in exact integer arithmetic and with no external dependency, every numerical statement of the note except the divisibility data of Table 4, which is quoted from the literature. Part 1 classical ideal solutions of size at most 12 (Table 5) Part 2 the integer solutions supplied by Chen Shuwen (Table 1) Part 3 the three infinite families of Proposition 6 (Table 2) Part 4 Theorem (sharp bound at size 4): the extremal family of Table 3, and an exhaustive enumeration of the ideal solutions of size 4 with all entries in [0, ENUM_LIMIT], checking the bound and the claim that for each diameter the maximum is attained by a symmetric solution For each solution it checks the defining power-sum identities and the inequality 4**(n-1) * abs(C) <= L**n, where n is the size, C the constant and L the diameter of the union of the two multisets. Just run the file. """ from fractions import Fraction from math import isqrt, cos, pi from itertools import combinations_with_replacement # Part 4 enumerates every 4-multiset drawn from [0, ENUM_LIMIT]. The cost is # about ENUM_LIMIT**4 / 24 multisets and the same order in memory. The value # below runs in a few seconds within a few hundred megabytes; raising it to 100 # reproduces the count of 30161 solutions quoted in the note, and needs roughly # one gigabyte. ENUM_LIMIT = 60 def pm(v): return [x for a in v for x in (a, -a)] KNOWN = [ ("{0,2} vs {1,1}", [0, 2], [1, 1]), ("{0,3,3} vs {1,1,4}", [0, 3, 3], [1, 1, 4]), ("{1,5,6} vs {2,3,7}", [1, 5, 6], [2, 3, 7]), ("{1,8,8} vs {2,5,10}", [1, 8, 8], [2, 5, 10]), ("Chen Shuwen, eq. (4.4)", [0, 664, 701, 1787, 1788], [188, 189, 1275, 1312, 1976]), ("Gloden 1944", [0, 19, 25, 57, 62, 86], [2, 11, 40, 42, 69, 85]), ("Escott 1910", [0, 18, 27, 58, 64, 89, 101], [1, 13, 38, 44, 75, 84, 102]), ("symmetric, h=55", [-51, -49, -19, -6, 30, 40, 55], [51, 49, 19, 6, -30, -40, -55]), ("symmetric, h=123", [-116, -104, -36, -19, 75, 77, 123], [116, 104, 36, 19, -75, -77, -123]), ("Chen Shuwen 1997", [0, 7, 23, 50, 53, 81, 82, 96], [1, 5, 26, 42, 63, 72, 88, 95]), ("Tarry 1913", [0, 4, 9, 23, 27, 41, 46, 50], [1, 2, 11, 20, 30, 39, 48, 49]), ("Letac 1942 (I)", [-98, -82, -58, -34, 13, 16, 69, 75, 99], [98, 82, 58, 34, -13, -16, -69, -75, -99]), ("Letac 1942 (II)", [-174, -148, -132, -50, -8, 63, 119, 161, 169], [174, 148, 132, 50, 8, -63, -119, -161, -169]), ("Borwein-Lisonek-Percival (a)", pm([99, 100, 188, 301, 313]), pm([71, 131, 180, 307, 308])), ("Borwein-Lisonek-Percival (b)", pm([103, 189, 366, 452, 515]), pm([18, 245, 331, 471, 508])), ("Kuosa-Meyrignac-Chen", pm([22, 61, 86, 127, 140, 151]), pm([35, 47, 94, 121, 146, 148])), ] SHUWEN = [ ("size 4", [0, 288, 289, 577], [84, 85, 492, 493]), ("size 5", [0, 421, 422, 1103, 1104], [116, 117, 798, 799, 1220]), ("size 6", [0, 466, 467, 1399, 1400, 1866], [124, 126, 931, 935, 1740, 1742]), ("size 7", [0, 344, 431, 1227, 1270, 1923, 1966], [80, 123, 776, 819, 1615, 1702, 2046]), ] def data(A, B): """power-sum check, then the constant C and the diameter L.""" n = len(A) assert len(B) == n for k in range(1, n): if sum(a ** k for a in A) != sum(b ** k for b in B): raise AssertionError("not an ideal solution") pa, pb = 1, 1 for a in A: pa *= a for b in B: pb *= b C = (-1) ** n * (pa - pb) if C == 0: raise AssertionError("trivial solution") return n, C, max(A + B) - min(A + B) def deviation(A, B): """largest distance, in units of the original scale, from an element to the nearest node cos**2(j.pi/2n) after normalising A u B to [0,1].""" n = len(A) U = sorted(A + B) lo, L = U[0], U[-1] - U[0] nodes = [cos(j * pi / (2 * n)) ** 2 for j in range(n + 1)] return max(min(abs((x - lo) / L - q) for q in nodes) for x in U) * L def check(label, A, B, show_dev=False): n, C, L = data(A, B) lhs, rhs = 4 ** (n - 1) * abs(C), L ** n ok = lhs <= rhs line = "n={0:2d} {1:26s} L={2:<8d} ratio={3:.12f} {4}".format( n, label, L, float(Fraction(lhs, rhs)), "OK" if ok else "FAILED") if show_dev: line += " dev={0:.1f}".format(deviation(A, B)) print(line, flush=True) return ok def pell_family_4(count): """u**2 - 2w**2 = 1, u > 3.""" out, u, w = [], 3, 2 for _ in range(count): u, w = 3 * u + 4 * w, 2 * u + 3 * w m, a = (u - 1) // 2, (u - w - 1) // 2 out.append(("u=%d" % u, [0, m, m + 1, u], [a, a + 1, 2 * m - a, 2 * m + 1 - a])) return out def conic_family_5(count): """2w**2 - 6vw + 2v**2 - v - w - 1 = 0, via y**2 - 5(2v+1)**2 = 4, m = 2 mod 6.""" out, f, g, m = [], 0, 1, 0 # f = F_m, g = F_{m+1} while len(out) < count: f, g, m = g, f + g, m + 1 if m % 6 != 2: continue v = (f - 1) // 2 if v <= 0: continue D = 20 * v * v + 20 * v + 9 s = isqrt(D) assert s * s == D and (6 * v + 1 + s) % 4 == 0 w = (6 * v + 1 + s) // 4 u = 2 * (w - v) A = [0, u - v - 1, u - v, u + w, u + w + 1] out.append(("v=%d" % v, A, [2 * u - x for x in A])) return out def extremal_family_4(count): """the equality case: L**2 + 1 = 2w**2, A = {0,(L-1)/2,(L+1)/2,L}, B = {c,c,d,d} with c = (L-w)/2 and d = (L+w)/2.""" out, L, w = [], 1, 1 for _ in range(count + 1): L, w = 3 * L + 4 * w, 2 * L + 3 * w if L <= 3: continue assert L * L + 1 == 2 * w * w c, d = (L - w) // 2, (L + w) // 2 out.append(("L=%d" % L, [0, (L - 1) // 2, (L + 1) // 2, L], [c, c, d, d])) if len(out) == count: break return out def enumerate_size_4(limit): """every ideal solution of size 4 with entries in [0, limit], grouped by the first three elementary symmetric functions.""" groups = {} for A in combinations_with_replacement(range(limit + 1), 4): a, b, c, d = A key = (a + b + c + d, a * b + a * c + a * d + b * c + b * d + c * d, a * b * c + a * b * d + a * c * d + b * c * d) groups.setdefault(key, []).append((a * b * c * d, A)) out = [] for lst in groups.values(): for i in range(len(lst)): for j in range(i + 1, len(lst)): if lst[i][0] != lst[j][0]: out.append((lst[i][1], lst[j][1])) return out def is_symmetric(A): """A is symmetric about its mean (the mean may be a half-integer).""" T = [4 * x - sum(A) for x in A] return sorted(T) == sorted(-x for x in T) def pell_family_6(count): """e**2 - 3h**2 = 1 - 3d**2, h odd, e = d mod 2; a = (h-1)/2, b = (e-d)/2.""" out = [] for d in (1, 2): got = 0 h = 3 while got < count: t = 1 - 3 * d * d + 3 * h * h r = isqrt(t) if t >= 0 else -1 if r >= 0 and r * r == t and (r - d) % 2 == 0: a, b = (h - 1) // 2, (r - d) // 2 A = [0, h - a - 1, h - a, h + a, h + a + 1, 2 * h] B = [h - b - d, h - b, h - d, h + d, h + b, h + b + d] if sorted(A) != sorted(B): out.append(("d=%d, h=%d" % (d, h), A, B)) got += 1 h += 2 return out if __name__ == "__main__": good = True print("Part 1 : classical ideal solutions of size at most 12", flush=True) for label, A, B in KNOWN: good = check(label, A, B) and good print("", flush=True) print("Part 2 : integer solutions communicated by Chen Shuwen", flush=True) for label, A, B in SHUWEN: good = check(label, A, B, show_dev=True) and good print("", flush=True) print("Part 3 : the three families of Proposition 6", flush=True) for label, A, B in pell_family_4(5): good = check("n=4 family, " + label, A, B) and good for label, A, B in conic_family_5(4): good = check("n=5 family, " + label, A, B) and good for label, A, B in pell_family_6(3): good = check("n=6 family, " + label, A, B) and good print("", flush=True) print("Part 4 : the sharp bound at size 4", flush=True) for label, A, B in extremal_family_4(5): n, C, L = data(A, B) r = Fraction(4 ** 3 * abs(C), L ** 4) eq = (r == (1 - Fraction(1, L * L)) ** 2) good = check("extremal, " + label, A, B) and good print(" equality in (1 - 1/L**2)**2 : {0}".format(eq), flush=True) if not eq: good = False # Theorem 9, case q = 0 (doubled centre): ratio (1 - 4/L**2)**2 exactly A0, B0 = [0, 5, 5, 10], [1, 2, 8, 9] n, C, L = data(A0, B0) r = Fraction(4 ** 3 * abs(C), L ** 4) eq0 = (r == (1 - Fraction(4, L * L)) ** 2) and (r == Fraction(576, 625)) good = check("case q=0, {0,5,5,10} vs {1,2,8,9}", A0, B0) and good print(" ratio 576/625 = (1 - 4/L**2)**2 : {0}".format(eq0), flush=True) if not eq0: good = False print("", flush=True) print(" exhaustive enumeration, entries in [0,{0}]".format(ENUM_LIMIT), flush=True) sols = enumerate_size_4(ENUM_LIMIT) best, nviol = {}, 0 for A, B in sols: n, C, L = data(list(A), list(B)) r = Fraction(4 ** 3 * abs(C), L ** 4) if r > (1 - Fraction(1, L * L)) ** 2: nviol += 1 if L not in best or r > best[L][0]: best[L] = (r, A) nsym = sum(1 for L in best if is_symmetric(list(best[L][1]))) print(" solutions found : {0}".format(len(sols)), flush=True) print(" exceeding (1 - 1/L**2)**2 : {0}".format(nviol), flush=True) print(" diameters whose maximum is attained by a symmetric solution" " : {0} of {1}".format(nsym, len(best)), flush=True) if nviol or nsym != len(best): good = False print("", flush=True) print("all cases satisfy 4**(n-1)*abs(C) <= L**n :", good, flush=True)