betaFeedback

WorksMathematics

A Chebyshev bound for the constant in the Prouhet-Tarry-Escott problem

Abstract

Let (A,B) be an ideal solution of size n of the Prouhet-Tarry-Escott problem, with constant C defined by prod_i (x - a_i) - prod_i (x - b_i) = C, and let L be the diameter of A u B. We prove |C| <= 4 (L/4)^n, with equality exactly for the configuration given by the roots of T_n -/+ 1, where T_n is the Chebyshev polynomial of the first kind. Equality is attained by integer solutions for n <= 3 and, by Niven's theorem, is impossible for n >= 4; for n = 4, n = 5 and n = 6, however, we exhibit infinite families of integer solutions, governed by a Pell equation, along which the ratio 4^(n-1)|C|/L^n tends to 1, so that the constant 4^(n-1) cannot be improved. The bounds on C in the standard references are p-adic throughout: they determine which prime powers divide C, and the present inequality appears to be the first of archimedean type. Two further consequences are recorded: an unconditional lower bound for the height of any ideal solution, in terms of the known divisors of the universal constant C_n, which yields the first such statements for sizes 17 <= n <= 20, where no search has been published; and the observation that the extremal configuration is exactly the trigonometric configuration of Chen Shuwen, for which the analogous extremality statement for the individual variables is an open conjecture. The present result is its proven counterpart for the constant.

Introduction

For n≥2n\ge2, two multisets of integers A={a1,…,an}A=\{a_1,\ldots,a_n\} and B={b1,…,bn}B=\{b_1,\ldots,b_n\} with A≠BA\ne B form an ideal solution of size nn of the Prouhet–Tarry–Escott (PTE) problem if

∑i=1naik=∑i=1nbik,k=1,2,…,n−1.(1)\sum_{i=1}^{n}a_i^k=\sum_{i=1}^{n}b_i^k,\qquad k=1,2,\ldots,n-1. \tag*{(1)}

Throughout, nn denotes the size; the degree is n−1n-1. Ideal solutions are known for n≤10n\le10 and n=12n=12; none is known for n=11n=11 or n≥13n\ge13. We refer to [1, 5, 6, 9] for background.

Writing F(x)=∏i(x−ai)F(x)=\prod_i(x-a_i) and G(x)=∏i(x−bi)G(x)=\prod_i(x-b_i), condition (1) is equivalent to F−GF-G being a nonzero constant,

F(x)−G(x)=C.(2)F(x)-G(x)=C. \tag*{(2)}

The arithmetic of CC has been studied since Kleiman [7], who proved (n−1)!∣C(n-1)!\mid C, and Rees and Smyth [8]; the survey of Borwein and Ingalls [3] and the search of Borwein, Lisoněk and Percival [4] record the state of the question at the turn of the century; the current state of the divisibility conditions, for n≤20n\le20, is tabulated by Coppersmith, Mossinghoff, Scheinerman and VanderKam [6 Table 1], and the analogous questions over imaginary quadratic rings are treated by Caley [5]. These references are pp-adic in nature: they assert that certain prime powers divide CC. The only archimedean information in them is the trivial bound ∣C∣≤Ln|C| \le L^n, immediate from the product formula ∣C∣=∏i∣bj−ai∣|C| = \prod_i |b_j-a_i|, valid for every jj [1 E5]; no bound limiting the size of CC beyond it appears.1

Our result is such a bound. Set

L=max⁡(A∪B)−min⁡(A∪B),L=\max(A\cup B)-\min(A\cup B),

the diameter of the solution; note that LL is invariant under the translations x↦x+tx\mapsto x+t under which (1) is invariant, and scales linearly under x↦λxx\mapsto\lambda x, exactly as ∣C∣1/n|C|^{1/n} does.

Theorem 1. Let (A,B)(A,B) be an ideal solution of size nn of the PTE problem, with constant CC and diameter LL. Then

∣C∣≤4(L4)n(3)|C|\le4\left(\frac{L}{4}\right)^n \tag*{(3)}

or equivalently, in integral form, 4n−1∣C∣≤Ln4^{n-1}|C|\le L^n.

The bound is sharp. Equality holds precisely when

F(x)=T~(x)+∣C∣2,G(x)=T~(x)−∣C∣2F(x)=\widetilde{T}(x)+\frac{|C|}{2},\qquad G(x)=\widetilde{T}(x)-\frac{|C|}{2}

(or with FF and GG interchanged), where T~\widetilde{T} is the monic Chebyshev polynomial of degree nn for the interval [min⁡(A∪B),max⁡(A∪B)][\min(A\cup B),\max(A\cup B)]. After normalising that interval to [0,1][0,1], the 2n2n elements of A∪BA\cup B then take the n+1n+1 values

cos⁡2(jπ2n),j=0,1,…,n,(4)\cos^2\left(\frac{j\pi}{2n}\right),\qquad j=0,1,\ldots,n, \tag*{(4)}

the extreme ones simply and the others doubly. For n≤3n\le3 these values are rational and equality is attained by genuine integer solutions: for n=2n=2 by {0,2}\{0,2\} versus {1,1}\{1,1\} with ∣C∣=1=4(2/4)2|C|=1=4(2/4)^2, and for n=3n=3 by {0,3,3}\{0,3,3\} versus {1,1,4}\{1,1,4\} with ∣C∣=4=4(4/4)3|C|=4=4(4/4)^3. For n≥4n\ge4 equality is impossible over Q\mathbb{Q}: it would force cos⁡(π/n)\cos(\pi/n) to be rational, which by Niven’s theorem happens only for n∈{1,2,3}n\in\{1,2,3\}. Thus (3) is strict for every ideal solution of size n≥4n\ge4, although, as the numerical table of Section 6 shows, it can be approached closely.

Section 2 contains the proof, Section 3 discusses the extremal configuration and its relation to a conjecture of Chen Shuwen, Section 4 shows that the bound is approached arbitrarily closely by integer solutions, Section 5 records the resulting height bounds, and Section 6 the numerical verification.

Proof of Theorem 1

Write m0=min⁡(A∪B)m_0=\min(A\cup B) and M0=max⁡(A∪B)M_0=\max(A\cup B), so L=M0−m0L=M_0-m_0, and set

H=12(F+G),so thatF=H+C2,G=H−C2(5)H=\frac{1}{2}(F+G),\qquad\text{so that}\qquad F=H+\frac{C}{2},\qquad G=H-\frac{C}{2} \tag*{(5)}

by (2). Thus HH is monic of degree nn, and both H+C2H+\frac{C}{2} and H−C2H-\frac{C}{2} split over R\mathbb{R} with all their roots in [m0,M0][m_0,M_0]. Also F′=G′=H′F'=G'=H'.

Lemma 2. Let PP be a monic polynomial of degree nn with all roots real, and let c1≤⋯≤cn−1c_1\le\cdots\le c_{n-1} be the roots of P′P'. Then (−1)n−jP(cj)≥0(-1)^{n-j}P(c_j)\ge0 for 1≤j≤n−11\le j\le n-1. Moreover, if rr denotes the largest root of PP then P(x)≥0P(x)\ge0 for x≥rx\ge r, and if ss denotes the smallest root then (−1)nP(x)≥0(-1)^nP(x)\ge0 for x≤sx\le s.

Proof. Let r1≤⋯≤rnr_1 \le\cdots\le r_n be the roots of PP. By Rolle’s theorem and a count of multiplicities, rj≤cj≤rj+1r_j \le c_j \le r_{j+1} for 1≤j≤n−11 \le j \le n-1. On the open interval (rj,rj+1)(r_j,r_{j+1}), exactly n−jn-j roots of PP lie to the right, so PP has constant sign (−1)n−j(-1)^{n-j} there; at the endpoints PP vanishes. Hence (−1)n−jP(cj)≥0(-1)^{n-j}P(c_j) \ge0. The two final assertions are immediate.

Lemma 3. Let c1≤⋯≤cn−1c_1 \le\cdots\le c_{n-1} be the roots of H′H' and put x0=m0x_0=m_0, xj=cjx_j=c_j for 1≤j≤n−11 \le j \le n-1, and xn=M0x_n=M_0. Then x0≤x1≤⋯≤xnx_0 \le x_1 \le\cdots\le x_n, all xjx_j lie in [m0,M0][m_0,M_0], and

(−1)n−jH(xj)≥∣C∣2,j=0,1,…,n.(6)(-1)^{n-j}H(x_j) \ge\frac{\lvert C\rvert}{2}, \qquad j=0,1,\ldots,n. \tag*{(6)}

Proof. The roots of H′=F′H'=F' lie in the convex hull of the roots of FF by the Gauss–Lucas theorem, hence in [m0,M0][m_0,M_0]; this gives the ordering.

For 1≤j≤n−11 \le j \le n-1, Lemma 2 applied to FF and to GG — which have the same derivative, hence the same critical points — gives, with σ=(−1)n−j\sigma=(-1)^{n-j},

σF(cj)≥0,σG(cj)≥0.\sigma F(c_j) \ge0, \qquad\sigma G(c_j) \ge0.

Since F−G=CF-G=C we have σF−σG=σC\sigma F-\sigma G=\sigma C. If σC≥0\sigma C \ge0 then σC=∣C∣\sigma C=\lvert C\rvert and σF(cj)=σG(cj)+∣C∣≥∣C∣\sigma F(c_j)=\sigma G(c_j)+\lvert C\rvert\ge\lvert C\rvert; if σC<0\sigma C<0 then σG(cj)=σF(cj)+∣C∣≥∣C∣\sigma G(c_j)=\sigma F(c_j)+\lvert C\rvert\ge\lvert C\rvert. In either case σF(cj)+σG(cj)≥∣C∣\sigma F(c_j)+\sigma G(c_j) \ge\lvert C\rvert, that is, σH(cj)≥∣C∣/2\sigma H(c_j) \ge\lvert C\rvert/2 by (5).

At xn=M0x_n=M_0 one of F,GF,G vanishes and the other, being monic and evaluated at a point at least as large as all of its roots, is nonnegative by Lemma 2; its value there is ±C\pm C, hence equals ∣C∣\lvert C\rvert. Therefore H(M0)=∣C∣/2H(M_0)=\lvert C\rvert/2, which is (6) for j=nj=n. Symmetrically, at x0=m0x_0=m_0 one of F,GF,G vanishes and the other has sign (−1)n(-1)^n and absolute value ∣C∣\lvert C\rvert, so H(m0)=(−1)n∣C∣/2H(m_0)=(-1)^n\lvert C\rvert/2 and $(-1)^nH(m_0)=\lvert C\rvert/2.

Proof of Theorem 1. Let

T~(x)=2(L4)nTn(2x−m0−M0L)\widetilde{T}(x)=2\left(\frac{L}{4}\right)^n T_n\left(\frac{2x-m_0-M_0}{L}\right)

be the monic Chebyshev polynomial of degree nn for [m0,M0][m_0,M_0], where TnT_n is the Chebyshev polynomial of the first kind; it satisfies

max⁡x∈[m0,M0]∣T~(x)∣=μ:=2(L4)n.(7)\max_{x\in[m_0,M_0]}\lvert\widetilde{T}(x)\rvert=\mu:=2\left(\frac{L}{4}\right)^n. \tag*{(7)}

Assume, for contradiction, that ∣C∣/2>μ\lvert C\rvert/2>\mu. Put Q=H−T~Q=H-\widetilde{T}; since both HH and T~\widetilde{T} are monic of degree nn, deg⁡Q≤n−1\deg Q\le n-1. Let σj=(−1)n−j\sigma_j=(-1)^{n-j}. By Lemma 3 and (7), for each j=0,…,nj=0,\ldots,n,

σjQ(xj)=σjH(xj)−σjT~(xj)≥∣C∣2−μ>0.\sigma_jQ(x_j)=\sigma_jH(x_j)-\sigma_j\widetilde{T}(x_j)\ge\frac{\lvert C\rvert}{2}-\mu>0.

In particular Q(xj)≠0Q(x_j)\ne0 for every jj, and consecutive values Q(xj),Q(xj+1)Q(x_j),Q(x_{j+1}) have opposite signs; this forces x0<x1<⋯<xnx_0<x_1<\cdots<x_n and produces nn sign changes of QQ on [m0,M0][m_0,M_0]. Hence QQ has at least nn distinct real roots, while Q≢0Q\not\equiv0 and deg⁡Q≤n−1:a contradiction. Therefore\deg Q\le n-1: \text{a contradiction. Therefore}\lvert C\rvert/2\le\mu$, which is (3).

Remark 4. Equality in (3) forces H=T~H=\widetilde{T}. Indeed, if ∣C∣/2=μ\lvert C\rvert/2=\mu then σjQ(xj)≥0\sigma_jQ(x_j)\ge0 for j=0,…,nj=0,\ldots,n, and the standard uniqueness argument in Chebyshev’s equioscillation theorem (see e.g. [2 Ch. 2]) shows that a polynomial of degree at most n−1n-1 with a weakly alternating sign pattern at n+1n+1 points of an interval must vanish identically. Then F=T~+C2F=\widetilde{T}+\frac{C}{2} and G=T~−C2G=\widetilde{T}-\frac{C}{2} with ∣C∣/2=μ\lvert C\rvert/2=\mu, so A∪BA\cup B is the set of solutions of Tn(u)=±1T_n(u)=\pm1 transported to [m0,M0][m_0,M_0], which after normalisation to [0,1][0,1] is (4).

Remark 5. Only the real-rootedness of FF and GG and the constancy of F−GF-G were used; the integrality of AA and BB played no role. Theorem 1 therefore holds verbatim for ideal PTE solutions over any subring of R\mathbb{R}.

The extremal configuration

The configuration (4) is not new to the subject. In 2021 Chen Shuwen discovered a trigonometric identity attached to the PTE problem which, in the notation of [9 Identity 10], reads as follows: if (A,B)(A,B) is an ideal solution of size nn normalised so that min⁡(A∪B)=0\min(A\cup B)=0, and if max⁡A>max⁡B\max A>\max B, then

max⁡Bmax⁡A≥sin⁡2((n−1)π2n)=cos⁡2(π2n)(8)\frac{\max B}{\max A}\ge\sin^2\left(\frac{(n-1)\pi}{2n}\right)=\cos^2\left(\frac{\pi}{2n}\right) \tag*{(8)}

the right-hand side being exactly the second node in (4). The statement is restated in [9 Conjecture 2] together with an explicit description of the minimising configuration, which is precisely the pattern of double roots of Tn+1T_n+1. Inequality (8) has been verified on millions of numerical solutions; no proof is available.

Thus the configuration (4) is conjecturally extremal for the individual variables and, by Theorem 1, provably extremal for the constant. The two statements concern different functionals of the same solution, and they are tight at the same place: for the ideal solution of size 5

{0,664,701,1787,1788}versus{188,189,1275,1312,1976}\{0,664,701,1787,1788\}\quad\text{versus}\quad\{188,189,1275,1312,1976\}

quoted in [9 (4.4)] — with AA the second set, so that max⁡A>max⁡B\max A>\max B as (8) requires — the left-hand side of (8) exceeds the right-hand side by a factor 1.000387, while ∣C∣|C| reaches 0.9981 times the bound (3).

Sharpness over the integers

Equality in (3) requires the configuration (4), which is irrational for n≥4n\ge4. It is therefore natural to ask how closely integer solutions can approach the bound. The answer is: arbitrarily closely, at least for n=4n=4, n=5n=5 and n=6n=6.

The four examples of Table 1 were supplied by Chen Shuwen, who verified Theorem 1 on them independently.

nnsolution4n−1∣C∣/Ln4^{n-1}|C|/L^ndev.
4{0,288,289,577}\{0,288,289,577\} vs. {84,85,492,493}\{84,85,492,493\}0.999969960.5
5{0,421,422,1103,1104}\{0,421,422,1103,1104\} vs. {116,117,798,799,1220}\{116,117,798,799,1220\}0.999986560.5
6{0,466,467,1399,1400,1866}\{0,466,467,1399,1400,1866\} vs. {124,126,931,935,1740,1742}\{124,126,931,935,1740,1742\}0.999956352.0
7{0,344,431,1227,1270,1923,1966}\{0,344,431,1227,1270,1923,1966\} vs. {80,123,776,819,1615,1702,2046}\{80,123,776,819,1615,1702,2046\}0.9598402945.8

Table 1. Integer ideal solutions supplied by Chen Shuwen. The last column is the largest deviation, in units of the original scale, of an element from the nearest node of (4) after normalisation of A∪BA\cup B to [0,1][0,1].

Their structure is visible once A∪BA\cup B is normalised to [0,1][0,1]: the two simple nodes 0 and 1 of (4) are hit exactly, and each of the n−1n-1 double nodes is straddled by a pair of elements. For n=4n=4 and n=5n=5 that pair is consecutive and the node is its exact midpoint, so the deviation from (4) is half a unit of the original scale; for n=6n=6 the largest deviation is two units, and for n=7n=7 it is close to 46, which is why that example is markedly less tight.

This is not an accident, and the first three cases extend to infinite families.

Proposition 6. (i) Let u,wu,w be positive integers with u2−2w2=1u^2-2w^2=1 and u>3u>3, and put m=(u−1)/2m=(u-1)/2 and a=(u−w−1)/2a=(u-w-1)/2. Then

A={0,m,m+1,u},B={a,a+1,2m−a,2m+1−a}A=\{0,m,m+1,u\},\qquad B=\{a,a+1,2m-a,2m+1-a\}

is an ideal solution of size 4 with diameter L=uL=u.

(ii) Let v,wv,w be integers with w>v>0w>v>0 and 2w2−6vw+2v2−v−w−1=02w^2-6vw+2v^2-v-w-1=0, and put u=2(w−v)u=2(w-v). Then

A={0,u−v−1,u−v,u+w,u+w+1},B={2u−x:x∈A}A=\{0,u-v-1,u-v,u+w,u+w+1\},\qquad B=\{2u-x:x\in A\}

is an ideal solution of size 5 with diameter L=2uL=2u.

(iii) Let d,h,ed,h,e be positive integers with hh odd, e≡d(mod2)e\equiv d\pmod{2} and e2−3h2=1−3d2e^2-3h^2=1-3d^2, and put a=(h−1)/2a=(h-1)/2 and b=(e−d)/2b=(e-d)/2. Then

A={±a,±(a+1),±h},B={±d,±b,±(b+d)}A=\{\pm a,\pm(a+1),\pm h\},\qquad B=\{\pm d,\pm b,\pm(b+d)\}

is a symmetric ideal solution of size 6 with diameter L=2hL=2h, and

45∣C∣L6=(1−1h2)2−d2(3h2+1−4d2)2h6=1−2+9d2h2+O(h−4).(9)\frac{4^5|C|}{L^6}=\left(1-\frac{1}{h^2}\right)^2-\frac{d^2(3h^2+1-4d^2)^2}{h^6}=1-\frac{2+9d^2}{h^2}+O(h^{-4}). \tag*{(9)}

In all three cases the defining equation has infinitely many solutions, and along any of the families

4n−1∣C∣Ln⟶1.\frac{4^{n-1}|C|}{L^n}\longrightarrow1.

Proof. That each displayed pair satisfies (1) is a direct computation. For (i), Pell’s equation u2−2w2=1u^2-2w^2=1 has infinitely many solutions. For (ii), solving the defining conic for ww gives discriminant 20v2+20v+9=5(2v+1)2+420v^2+20v+9=5(2v+1)^2+4, so its integer points correspond to the solutions of y2−5X2=4y^2-5X^2=4 with X=2v+1X=2v+1; these are indexed by the Fibonacci numbers, X=FmX=F_m with mm even, and the integrality of ww selects m≡2(mod6)m\equiv2\pmod{6}. There are infinitely many.

For (iii), both sides are symmetric about 0, so the odd power sums vanish identically and only k=2k=2 and k=4k=4 remain. Writing S=(3h2+1)/2S=(3h^2+1)/2, which is an integer because hh is odd, those two conditions read

b2+(b+d)2=S−d2,b4+(b+d)4=12S2−d4,b^2+(b+d)^2=S-d^2,\qquad b^4+(b+d)^4=\frac{1}{2}S^2-d^4,

so that b2b^2 and (b+d)2(b+d)^2 are the roots of z2−(S−d2)z+(12S−d2)2z^2-(S-d^2)z+(\frac{1}{2}S-d^2)^2. Its discriminant is d2(3h2+1−3d2)=d2e2d^2(3h^2+1-3d^2)=d^2e^2, a square by the defining equation, and substituting 3h2=e2+3d2−13h^2=e^2+3d^2-1 turns the two roots into ((e−d)/2)2((e-d)/2)^2 and ((e+d)/2)2((e+d)/2)^2, which are perfect squares; the only remaining condition is the Pell equation. For its infinitude, the map (e,h)↦(7e+12h,4e+7h)(e,h)\mapsto(7e+12h,4e+7h), multiplication by (2+3)2(2+\sqrt{3})^2 in Z[3]\mathbb{Z}[\sqrt{3}], preserves e2−3h2e^2-3h^2 and the parities of ee and of hh; when dd is odd the map (e,h)↦(2e+3h,e+2h)(e,h)\mapsto(2e+3h,e+2h) already serves, since it interchanges those two parities and both are then odd. Admissible seeds are (e,h)=(1,1)(e,h)=(1,1) for d=1d=1, and (e,h)=(4,3)(e,h)=(4,3) and (8,5)(8,5) for d=2d=2. The seeds themselves give A=BA=B and only start the orbits; for d=2d=2 the two orbits under the first map give h=37,515,7173,…h=37,515,7173,\ldots and h=67,933,12995,…h=67,933,12995,\ldots. Identity (9) is a direct computation, and it gives the limit for (iii) at once, dd being fixed.

For the limit, note that 0∈A0\in A in both cases, so ∏iai=0\prod_i a_i=0 and

4n−1∣C∣Ln=4n−1∏i=1nbiL,\frac{4^{n-1}|C|}{L^n}=4^{n-1}\prod_{i=1}^{n}\frac{b_i}{L},

a continuous function of the normalised configuration (A∪B−min⁡)/L(A\cup B-\min)/L. Along family (i) one has w/u→2−1/2w/u\to2^{-1/2}, and along family (ii) the conic gives w/v→(3+5)/2w/v\to(3+\sqrt{5})/2; in either case the normalised configuration converges to (4), with 0 still in the part corresponding to AA. The displayed quantity is therefore continuous at the limit and takes there the value 1, by the equality case of Theorem 1. □\square

Corollary 7. For n=4n=4, n=5n=5 and n=6n=6, the supremum of 4n−1∣C∣/Ln4^{n-1}|C|/L^n over all ideal solutions of that size over Z\mathbb{Z} equals 11, and is not attained. In particular the constant 4n−14^{n-1} in Theorem 1 cannot be replaced by any larger one.

LLAABB4n−1∣C∣/Ln4^{n-1}|C|/L^n
size n=4n=4, from u2−2w2=1u^2-2w^2=1
1717{0,8,9,17}\{0,8,9,17\}{2,3,14,15}\{2,3,14,15\}0.9655056812060.965505681206
9999{0,49,50,99}\{0,49,50,99\}{14,15,84,85}\{14,15,84,85\}0.9989797896410.998979789641
577577{0,288,289,577}\{0,288,289,577\}{84,85,492,493}\{84,85,492,493\}0.9999699636470.999969963647
33633363{0,1681,1682,3363}\{0,1681,1682,3363\}{492,493,2870,2871}\{492,493,2870,2871\}0.9999991158090.999999115809
size n=5n=5, from 2w2−6vw+2v2−v−w−1=02w^2-6vw+2v^2-v-w-1=0
6868{0,23,24,61,62}\{0,23,24,61,62\}{6,7,44,45,68}\{6,7,44,45,68\}0.9956777337440.995677733744
12201220{0,421,422,1103,1104}\{0,421,422,1103,1104\}{116,117,798,799,1220}\{116,117,798,799,1220\}0.9999865627810.999986562781
2189221892{0,7563,7564,19801,19802}\{0,7563,7564,19801,19802\}{2090,2091,14328,14329,21892}\{2090,2091,14328,14329,21892\}0.9999999582690.999999958269
size n=6n=6, from e2−3h2=1−3d2e^2-3h^2=1-3d^2
2222{0,5,6,16,17,22}\{0,5,6,16,17,22\}{1,2,10,12,20,21}\{1,2,10,12,20,21\}0.9103835543910.910383554391
8282{0,20,21,61,62,82}\{0,20,21,61,62,82\}{5,6,40,42,76,77}\{5,6,40,42,76,77\}0.9934629979840.993462997984
306306{0,76,77,229,230,306}\{0,76,77,229,230,306\}{20,21,152,154,285,286}\{20,21,152,154,285,286\}0.9995301299350.999530129935
7474{0,18,19,55,56,74}\{0,18,19,55,56,74\}{4,6,35,39,68,70}\{4,6,35,39,68,70\}0.9724347815290.972434781529
134134{0,33,34,100,101,134}\{0,33,34,100,101,134\}{8,10,65,69,124,126}\{8,10,65,69,124,126\}0.9915527676850.991552767685
10301030{0,257,258,772,773,1030}\{0,257,258,772,773,1030\}{68,70,513,517,960,962}\{68,70,513,517,960,962\}0.9998567305540.999856730554

Table 2. The three families of Proposition 6. The examples of Table 1 are the third entry of the first block and the second of the second, and the third block is the family of part (iii), with d=1d=1 then d=2d=2.

Lemma 8. Let (A,B)(A,B) be an ideal solution of size 44. If AA is symmetric about its mean, then so is BB, about the same point.

Proof. Translate the mean to 00, so that ∑ai=∑bi=0\sum a_i=\sum b_i=0. For any four quantities of zero sum,

∑iai3=3(a1+a2)(a1+a3)(a1+a4).\sum_i a_i^3=3(a_1+a_2)(a_1+a_3)(a_1+a_4).

If AA is symmetric then ∑iai3=0\sum_i a_i^3=0, hence ∑ibi3=0\sum_i b_i^3=0 by (1), so one of the three pairings of BB has a vanishing pair sum; the complementary pair then sums to zero as well.

Not every ideal solution of size 44 is symmetric: {0,18,18,35}\{0,18,18,35\} against {3,8,30,30}\{3,8,30,30\} is ideal, and neither side is symmetric about its mean.

Theorem 9. Let (A,B)(A,B) be an ideal solution of size 44 which is symmetric about its mean. Translate that mean to 00 and, if it is a half-integer, scale by 22, and write A={−p,−q,q,p}A=\{-p,-q,q,p\} and B={−r,−s,s,r}B=\{-r,-s,s,r\} with integers p>q≥0p>q\ge0 and r≥s≥1r\ge s\ge1, the two sides being labelled so that p=max⁡(A∪B)p=\max(A\cup B). Then r2+s2=p2+q2r^2+s^2=p^2+q^2, r2s2>p2q2r^2s^2>p^2q^2, and

43∣C∣L4=4(r2s2−p2q2)p4≤(1−q2p2)2,\frac{4^3|C|}{L^4}=\frac{4(r^2s^2-p^2q^2)}{p^4}\le\left(1-\frac{q^2}{p^2}\right)^2,

with equality if and only if r=sr=s; when q=0q=0 this equality is impossible, and the ratio equals 1−δ2(2p2−δ2)/p41-\delta^2(2p^2-\delta^2)/p^4 with δ=r−s≥1\delta=r-s\ge1. Consequently every ideal solution of size 44 that is symmetric about its mean, of diameter LL and in lowest terms, satisfies

43∣C∣L4≤(1−1L2)2(10)\frac{4^3|C|}{L^4}\le\left(1-\frac{1}{L^2}\right)^2 \tag*{(10)}

and equality holds precisely for

A={0,L−12,L+12,L},B={c,c,d,d},c=L−w2,d=L+w2,A=\left\{0,\frac{L-1}{2},\frac{L+1}{2},L\right\},\qquad B=\{c,c,d,d\},\qquad c=\frac{L-w}{2},\quad d=\frac{L+w}{2},

where L2+1=2w2L^2+1=2w^2. For these, cd=(L2−1)/8cd=(L^2-1)/8, so that ∣C∣=((L2−1)/8)2|C|=((L^2-1)/8)^2 and the ratio equals (1−1/L2)2(1-1/L^2)^2 exactly.

Proof. Both sides being symmetric, the odd power sums vanish and (1) reduces to its k=2k=2 instance, r2+s2=p2+q2=:Tr^2+s^2=p^2+q^2=:T. Interchanging AA and BB changes only the sign of CC, so the labelling p=max⁡(A∪B)p=\max(A\cup B) costs no generality, and L=2pL=2p. From r≥sr\ge s we get r2≥T/2r^2\ge T/2, and p2≥T/2p^2\ge T/2 because p>qp>q. On [T/2,T][\sqrt{T/2},\sqrt{T}] the function r↦rT−r2r\mapsto r\sqrt{T-r^2} is strictly decreasing and takes the value pqpq at r=pr=p; since {r,s}≠{p,q}\{r,s\}\ne\{p,q\} forces r<pr<p, we obtain rs>pqrs>pq. Next C=p2q2−r2s2C=p^2q^2-r^2s^2, so 43∣C∣/L4=4(r2s2−p2q2)/p44^3|C|/L^4=4(r^2s^2-p^2q^2)/p^4. Finally rs≤T/2rs\le T/2, with equality if and only if r=sr=s, so

r2s2−p2q2≤T24−p2q2=(p2−q2)24.r^2s^2-p^2q^2\le\frac{T^2}{4}-p^2q^2=\frac{(p^2-q^2)^2}{4}.

which gives the bound.

If q≥1q\ge1, the right-hand side is at most (1−1/p2)2(1-1/p^2)^2, with equality exactly when q=1q=1; together with r=sr=s that is p2+1=2r2p^2+1=2r^2.

If q=0q=0, which can only happen when the mean is an integer, then r=sr=s would give p2=2r2p^2=2r^2, which is impossible, so δ=r−s≥1\delta=r-s\ge1; also δ<r<p\delta<r<p. Since (r+s)2=2p2−δ2(r+s)^2=2p^2-\delta^2 and pq=0pq=0,

43∣C∣L4=4r2s2p4=(r2+s2)2−(r2−s2)2p4=1−δ2(2p2−δ2)p4.\frac{4^3|C|}{L^4}=\frac{4r^2s^2}{p^4}=\frac{(r^2+s^2)^2-(r^2-s^2)^2}{p^4}=1-\frac{\delta^2(2p^2-\delta^2)}{p^4}.

The function t↦t(2p2−t)t\mapsto t(2p^2-t) is increasing on [0,p2][0,p^2] and 1≤δ2<p21\le\delta^2<p^2, so the ratio is at most 1−(2p2−1)/p4=(1−1/p2)21-(2p^2-1)/p^4=(1-1/p^2)^2, with equality exactly when δ=1\delta=1; for instance {0,5,5,10}\{0,5,5,10\} against {1,2,8,9}\{1,2,8,9\} gives 576/625576/625.

In both cases the ratio is at most (1−1/p2)2(1-1/p^2)^2. A solution symmetric about a half-integer has L=pL=p in lowest terms, which is (10); a solution symmetric about an integer has L=2pL=2p and satisfies the sharper (1−4/L2)2(1-4/L^2)^2. So (10) holds in both cases and only the half-integer case attains it.

LLAABB43∣C∣/L44^3|C|/L^4
7{0,3,4,7}\{0,3,4,7\}{1,1,6,6}\{1,1,6,6\}0.959600166597
41{0,20,21,41}\{0,20,21,41\}{6,6,35,35}\{6,6,35,35\}0.998810585892
239{0,119,120,239}\{0,119,120,239\}{35,35,204,204}\{35,35,204,204\}0.999964986914
1393{0,696,697,1393}\{0,696,697,1393\}{204,204,1189,1189}\{204,204,1189,1189\}0.999998969311
8119{0,4059,4060,8119}\{0,4059,4060,8119\}{1189,1189,6930,6930}\{1189,1189,6930,6930\}0.999999969659

Table 3. The extremal family of Theorem 9; every entry attains (10) with equality. The first member has ∣C∣=36|C|=36, which is the universal constant C4C_4 itself.

Remark 10. The size 4 family of Proposition 6(i) and the extremal family of Theorem 9 are the two branches of one Pell equation: the first is u2−2w2=1u^2-2w^2=1, with u=17,99,577,3363,…u=17,99,577,3363,\ldots, the second is u2−2w2=−1u^2-2w^2=-1, with u=7,41,239,1393,…u=7,41,239,1393,\ldots. Their diameters interleave, and at equal diameter the second is the better of the two: its ratio is 1−2/L2+O(L−4)1-2/L^2+O(L^{-4}) against 1−10/L2+O(L−4)1-10/L^2+O(L^{-4}).

Remark 11. Theorem 9 is proved for solutions symmetric about their mean. An exhaustive enumeration of the ideal solutions of size 4 with all entries in [0,100][0,100], of which there are 30161, confirms that (10) holds for every one of them, symmetric or not, and that for each diameter the maximum of 43∣C∣/L44^3|C|/L^4 is attained by a symmetric solution. For non-symmetric solutions the bound is therefore verified, not proved. The ancillary file reproduces this enumeration when its range is set to [0,100][0,100], which takes about a gigabyte of memory; at its default range [0,60][0,60] it finds 4878 solutions and the same two statements hold for all of them.

Remark 12 (priority). Formulas of this kind for the sizes 4, 5 and 6 were obtained by Chen Shuwen in 2024, before the present work; the relevant results are in [9]. The three families of Proposition 6 were found independently, and the earlier work was learned of only afterwards, by personal communication.

Remark 13. The three families begin at (u,w)=(17,12)(u,w)=(17,12), at (v,w)=(10,27)(v,w)=(10,27) and at (d,h,e)=(1,11,19)(d,h,e)=(1,11,19); the examples of sizes 4, 5 and 6 in Table 1 are the third member of the first, the second of the second, and the member (d,h,e)=(2,933,1616)(d,h,e)=(2,933,1616) of the third. That n≤6n \le6 should behave so well is explained by the nodes (4) lying in Q(cos⁡(π/n))\mathbb{Q}(\cos(\pi/n)), a field of degree ϕ(2n)/2\phi(2n)/2: that degree is 1 for n≤3n \le3, where the nodes are rational and equality is attained outright, and equals 2 exactly for n=4,5,6n=4,5,6, where the simultaneous approximation required reduces to a single Pell equation. For n=7n=7 the degree is 3 and the approximation is genuinely harder, which is what the last line of Table 1 records. Whether the supremum is 1 for every nn remains open.

Remark 14. The constant 4 in (3) is the capacity normalisation: an interval of length LL has logarithmic capacity L/4L/4, and the monic Chebyshev polynomial of degree nn on it has supremum norm 2(L/4)n2(L/4)^n, which is the quantity μ\mu of (7). This is why the base 4 does not depend on nn.

Lower bounds for the height

Let CnC_n denote the universal constant of the PTE problem of size nn, that is, the greatest common divisor of CC over all ideal solutions of size nn, and let Cn′C'_n denote the corresponding quantity restricted to symmetric solutions. Divisors of CnC_n and of Cn′C'_n are tabulated in [6 Table 1] for n≤20n \le20. Since Cn∣CC_n \mid C for every ideal solution, Theorem 1 inverts to:

Corollary 15. Every ideal solution of size nn satisfies

L≥4(Cn4)1/n.L \ge4\left(\frac{C_n}{4}\right)^{1/n}.

For a symmetric solution, whose elements may be taken symmetric about 0 so that L=2hL=2h with h=max⁡∣ai∣h=\max|a_i|, this reads h≥2(Cn′/4)1/nh \ge2(C'_n/4)^{1/n}.

The resulting values are listed in Table 4. They are weaker than the exhaustive searches of [6] wherever those have been carried out. For 17≤n≤2017 \le n \le20 no search has been published, and Corollary 15 provides, as far as we are aware, the first unconditional lower bound on the magnitude of a hypothetical ideal solution for those nn.

nnCn≥C_n \geL≥L \geCn′≥C'_n \geh≥h \gesearched to
3100.6010^{0.60}4100.6010^{0.60}2—
4101.5610^{1.56}7101.5610^{1.56}4—
5103.7010^{3.70}17103.7010^{3.70}9—
6103.8610^{3.86}14103.8610^{3.86}7—
7106.5210^{6.52}29107.8010^{7.80}22—
8108.4810^{8.48}39108.4810^{8.48}20—
9109.3810^{9.38}38109.3810^{9.38}197000
101010.8110^{10.81}421010.8110^{10.81}212500
111012.7710^{12.77}521014.2610^{14.26}353500
121012.7010^{12.70}411014.1610^{14.16}271511
131016.2510^{16.25}641022.3910^{22.39}952000
141017.3610^{17.36}641020.4210^{20.42}53900
151018.5110^{18.51}631025.0010^{25.00}851100
161018.4610^{18.46}531026.4610^{26.46}83850
171022.3510^{22.35}771032.0610^{32.06}142—
181022.3110^{22.31}651030.4910^{30.49}92—
191026.3310^{26.33}911034.7410^{34.74}126—
201027.6110^{27.61}901034.2110^{34.21}96—

Table 4. Lower bounds from Corollary 15. The columns Cn≥C_n \ge and Cn′≥C'_n \ge give the product of the divisors listed in [6 Table 1], displayed to two decimals; LL and hh are computed from the exact integer products and rounded up, LL being the diameter and hh the height of a symmetric solution. The last column is the height to which an exhaustive search has been published [6 Table 2].

Numerical verification

Table 5 lists, for classical ideal solutions of size n≤12n \le12, the ratio of ∣C∣|C| to the bound (3). The defining identities (1) are checked exactly for each entry. The computation is reproduced by the ancillary file verify_pte_chebyshev.py, which uses exact integer arithmetic and requires only the Python standard library. The same file replays the families of Proposition 6, the extremal family of Theorem 9, and the enumeration of Remark 11.

nnsolution∣C∣|C|LL4n−1∣C∣/Ln4^{n-1}|C|/L^n
2{0,2}\{0,2\} vs {1,1}\{1,1\}121.0000
3{0,3,3}\{0,3,3\} vs {1,1,4}\{1,1,4\}441.0000
3{1,5,6}\{1,5,6\} vs {2,3,7}\{2,3,7\}1260.8889
3{1,8,8}\{1,8,8\} vs {2,5,10}\{2,5,10\}3690.7901
5Chen Shuwen [9 (4.4)]11744934888960019760.9981
6Gloden 1944216770400860.5487
7Escott 1910139675536001020.4981
7symmetric, h=55h=55376049520001100.7904
7symmetric, h=123h=123117228855744002460.8807
8Chen Shuwen 1997207048441600960.4702
8Tarry 19131210809600500.5079
9Letac 1942 (I)33774250333824001980.4732
9Letac 1942 (II)5547214676779776003480.4857
10Borwein–Lisoněk–Percival (a)56872727036080091136006260.1613
10Borwein–Lisoněk–Percival (b)262876888341059791518720010300.5128
12Kuosa–Meyrignac–Chen674402945596760540160003020.4915

Table 5. The bound (3) on classical ideal solutions of size n≤12n \le12, in the integral form 4n−1∣C∣≤Ln4^{n-1}|C| \le L^n. The first two rows are the equality cases.

Status of the statements. Theorem 1, its equality case, Proposition 6, Corollary 7, Lemma 8, Theorem 9 and Corollary 15 are PROVED. The bound (10) is proved for solutions symmetric about their mean and, for the others, VERIFIED by the enumeration recorded above. The entries of Table 4 rest on the divisibility data of [6 Table 1], which we have VERIFIED independently for n=7,9,11,13n=7,9,11,13; the columns LL and hh there are computed from the exact integer products. Inequality (8) is OPEN and is quoted here as a conjecture of [9].

Acknowledgements and declaration. The integer examples of Table 1 were provided by Chen Shuwen, who also verified Theorem 1 on them independently, and he supplied copies of several of the sources consulted for Section 2. Formulas of this kind for ideal solutions of sizes 4, 5 and 6 were obtained by him in 2024 [9]; the families of Proposition 6 were found independently, and I learned of his earlier work by personal communication. I thank him for his generous help and correspondence. Prepared with Claude (Anthropic), which carried out the computations and drafted the proofs under the author’s direction; the author is responsible for the content.

References

  1. [1]P. Borwein, The Prouhet–Tarry–Escott problem, Chapter 11 of Computational Excursions in Analysis and Number Theory, Springer, New York, 2002, pp. 85–95.DOI
  2. [2]P. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, Graduate Texts in Mathematics 161, Springer, 1995.DOI
  3. [3]P. Borwein and C. Ingalls, The Prouhet–Tarry–Escott problem revisited, Enseign. Math. (2) 40 (1994), 3–27.DOI
  4. [4]P. Borwein, P. Lisoněk and C. Percival, Computational investigations of the Prouhet–Tarry–Escott problem, Math. Comp. 72 (2003), no. 244, 2063–2070.DOI
  5. [5]T. Caley, The Prouhet–Tarry–Escott problem, PhD thesis, University of Waterloo, 2012.
  6. [6]D. Coppersmith, M. J. Mossinghoff, D. Scheinerman and J. M. VanderKam, Ideal solutions in the Prouhet–Tarry–Escott problem, preprint, arXiv:2304.11254.arxiv.org/abs/2304.11254
  7. [7]H. Kleiman, A note on the Tarry–Escott problem, J. Reine Angew. Math. 278/279 (1975), 48–51.DOI
  8. [8]E. Rees and C. J. Smyth, On the constant in the Tarry–Escott problem, in: Cinquante Ans de Polynômes — Fifty Years of Polynomials, Lecture Notes in Mathematics 1415, Springer, 1990, pp. 196–208.DOI
  9. [9]Chen Shuwen, A survey of the Prouhet–Tarry–Escott problem and its generalizations, arXiv:2506.11429 (2025).

Paper details

vlnc:W_wzz6fwps
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Anthropic Claude Opus

View statement
Looking for related papers…
Contents