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 , two multisets of integers and with form an ideal solution of size of the Prouhet–Tarry–Escott (PTE) problem if
Throughout, denotes the size; the degree is . Ideal solutions are known for and ; none is known for or . We refer to [1, 5, 6, 9] for background.
Writing and , condition (1) is equivalent to being a nonzero constant,
The arithmetic of has been studied since Kleiman [7], who proved , 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 , 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 -adic in nature: they assert that certain prime powers divide . The only archimedean information in them is the trivial bound , immediate from the product formula , valid for every [1 E5]; no bound limiting the size of beyond it appears.1
Our result is such a bound. Set
the diameter of the solution; note that is invariant under the translations under which (1) is invariant, and scales linearly under , exactly as does.
Theorem 1. Let be an ideal solution of size of the PTE problem, with constant and diameter . Then
or equivalently, in integral form, .
The bound is sharp. Equality holds precisely when
(or with and interchanged), where is the monic Chebyshev polynomial of degree for the interval . After normalising that interval to , the elements of then take the values
the extreme ones simply and the others doubly. For these values are rational and equality is attained by genuine integer solutions: for by versus with , and for by versus with . For equality is impossible over : it would force to be rational, which by Niven’s theorem happens only for . Thus (3) is strict for every ideal solution of size , 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 and , so , and set
by (2). Thus is monic of degree , and both and split over with all their roots in . Also .
Lemma 2. Let be a monic polynomial of degree with all roots real, and let be the roots of . Then for . Moreover, if denotes the largest root of then for , and if denotes the smallest root then for .
Proof. Let be the roots of . By Rolle’s theorem and a count of multiplicities, for . On the open interval , exactly roots of lie to the right, so has constant sign there; at the endpoints vanishes. Hence . The two final assertions are immediate.
Lemma 3. Let be the roots of and put , for , and . Then , all lie in , and
Proof. The roots of lie in the convex hull of the roots of by the Gauss–Lucas theorem, hence in ; this gives the ordering.
For , Lemma 2 applied to and to — which have the same derivative, hence the same critical points — gives, with ,
Since we have . If then and ; if then . In either case , that is, by (5).
At one of 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 , hence equals . Therefore , which is (6) for . Symmetrically, at one of vanishes and the other has sign and absolute value , so and $(-1)^nH(m_0)=\lvert C\rvert/2.
Proof of Theorem 1. Let
be the monic Chebyshev polynomial of degree for , where is the Chebyshev polynomial of the first kind; it satisfies
Assume, for contradiction, that . Put ; since both and are monic of degree , . Let . By Lemma 3 and (7), for each ,
In particular for every , and consecutive values have opposite signs; this forces and produces sign changes of on . Hence has at least distinct real roots, while and \lvert C\rvert/2\le\mu$, which is (3).
Remark 4. Equality in (3) forces . Indeed, if then for , and the standard uniqueness argument in Chebyshev’s equioscillation theorem (see e.g. [2 Ch. 2]) shows that a polynomial of degree at most with a weakly alternating sign pattern at points of an interval must vanish identically. Then and with , so is the set of solutions of transported to , which after normalisation to is (4).
Remark 5. Only the real-rootedness of and and the constancy of were used; the integrality of and played no role. Theorem 1 therefore holds verbatim for ideal PTE solutions over any subring of .
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 is an ideal solution of size normalised so that , and if , then
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 . 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
quoted in [9 (4.4)] — with the second set, so that as (8) requires — the left-hand side of (8) exceeds the right-hand side by a factor 1.000387, while reaches 0.9981 times the bound (3).
Sharpness over the integers
Equality in (3) requires the configuration (4), which is irrational for . It is therefore natural to ask how closely integer solutions can approach the bound. The answer is: arbitrarily closely, at least for , and .
The four examples of Table 1 were supplied by Chen Shuwen, who verified Theorem 1 on them independently.
| solution | dev. | ||
| 4 | vs. | 0.99996996 | 0.5 |
| 5 | vs. | 0.99998656 | 0.5 |
| 6 | vs. | 0.99995635 | 2.0 |
| 7 | vs. | 0.95984029 | 45.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 to .
Their structure is visible once is normalised to : the two simple nodes 0 and 1 of (4) are hit exactly, and each of the double nodes is straddled by a pair of elements. For and 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 the largest deviation is two units, and for 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 be positive integers with and , and put and . Then
is an ideal solution of size 4 with diameter .
(ii) Let be integers with and , and put . Then
is an ideal solution of size 5 with diameter .
(iii) Let be positive integers with odd, and , and put and . Then
is a symmetric ideal solution of size 6 with diameter , and
In all three cases the defining equation has infinitely many solutions, and along any of the families
Proof. That each displayed pair satisfies (1) is a direct computation. For (i), Pell’s equation has infinitely many solutions. For (ii), solving the defining conic for gives discriminant , so its integer points correspond to the solutions of with ; these are indexed by the Fibonacci numbers, with even, and the integrality of selects . There are infinitely many.
For (iii), both sides are symmetric about 0, so the odd power sums vanish identically and only and remain. Writing , which is an integer because is odd, those two conditions read
so that and are the roots of . Its discriminant is , a square by the defining equation, and substituting turns the two roots into and , which are perfect squares; the only remaining condition is the Pell equation. For its infinitude, the map , multiplication by in , preserves and the parities of and of ; when is odd the map already serves, since it interchanges those two parities and both are then odd. Admissible seeds are for , and and for . The seeds themselves give and only start the orbits; for the two orbits under the first map give and . Identity (9) is a direct computation, and it gives the limit for (iii) at once, being fixed.
For the limit, note that in both cases, so and
a continuous function of the normalised configuration . Along family (i) one has , and along family (ii) the conic gives ; in either case the normalised configuration converges to (4), with 0 still in the part corresponding to . The displayed quantity is therefore continuous at the limit and takes there the value 1, by the equality case of Theorem 1.
Corollary 7. For , and , the supremum of over all ideal solutions of that size over equals , and is not attained. In particular the constant in Theorem 1 cannot be replaced by any larger one.
| size , from | |||
| size , from | |||
| size , from | |||
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 then .
Lemma 8. Let be an ideal solution of size . If is symmetric about its mean, then so is , about the same point.
Proof. Translate the mean to , so that . For any four quantities of zero sum,
If is symmetric then , hence by (1), so one of the three pairings of has a vanishing pair sum; the complementary pair then sums to zero as well.
Not every ideal solution of size is symmetric: against is ideal, and neither side is symmetric about its mean.
Theorem 9. Let be an ideal solution of size which is symmetric about its mean. Translate that mean to and, if it is a half-integer, scale by , and write and with integers and , the two sides being labelled so that . Then , , and
with equality if and only if ; when this equality is impossible, and the ratio equals with . Consequently every ideal solution of size that is symmetric about its mean, of diameter and in lowest terms, satisfies
and equality holds precisely for
where . For these, , so that and the ratio equals exactly.
Proof. Both sides being symmetric, the odd power sums vanish and (1) reduces to its instance, . Interchanging and changes only the sign of , so the labelling costs no generality, and . From we get , and because . On the function is strictly decreasing and takes the value at ; since forces , we obtain . Next , so . Finally , with equality if and only if , so
which gives the bound.
If , the right-hand side is at most , with equality exactly when ; together with that is .
If , which can only happen when the mean is an integer, then would give , which is impossible, so ; also . Since and ,
The function is increasing on and , so the ratio is at most , with equality exactly when ; for instance against gives .
In both cases the ratio is at most . A solution symmetric about a half-integer has in lowest terms, which is (10); a solution symmetric about an integer has and satisfies the sharper . So (10) holds in both cases and only the half-integer case attains it.
| 7 | 0.959600166597 | ||
| 41 | 0.998810585892 | ||
| 239 | 0.999964986914 | ||
| 1393 | 0.999998969311 | ||
| 8119 | 0.999999969659 |
Table 3. The extremal family of Theorem 9; every entry attains (10) with equality. The first member has , which is the universal constant 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 , with , the second is , with . Their diameters interleave, and at equal diameter the second is the better of the two: its ratio is against .
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 , 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 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 , which takes about a gigabyte of memory; at its default range 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 , at and at ; 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 of the third. That should behave so well is explained by the nodes (4) lying in , a field of degree : that degree is 1 for , where the nodes are rational and equality is attained outright, and equals 2 exactly for , where the simultaneous approximation required reduces to a single Pell equation. For 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 remains open.
Remark 14. The constant 4 in (3) is the capacity normalisation: an interval of length has logarithmic capacity , and the monic Chebyshev polynomial of degree on it has supremum norm , which is the quantity of (7). This is why the base 4 does not depend on .
Lower bounds for the height
Let denote the universal constant of the PTE problem of size , that is, the greatest common divisor of over all ideal solutions of size , and let denote the corresponding quantity restricted to symmetric solutions. Divisors of and of are tabulated in [6 Table 1] for . Since for every ideal solution, Theorem 1 inverts to:
Corollary 15. Every ideal solution of size satisfies
For a symmetric solution, whose elements may be taken symmetric about 0 so that with , this reads .
The resulting values are listed in Table 4. They are weaker than the exhaustive searches of [6] wherever those have been carried out. For 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 .
| searched to | |||||
| 3 | 4 | 2 | — | ||
| 4 | 7 | 4 | — | ||
| 5 | 17 | 9 | — | ||
| 6 | 14 | 7 | — | ||
| 7 | 29 | 22 | — | ||
| 8 | 39 | 20 | — | ||
| 9 | 38 | 19 | 7000 | ||
| 10 | 42 | 21 | 2500 | ||
| 11 | 52 | 35 | 3500 | ||
| 12 | 41 | 27 | 1511 | ||
| 13 | 64 | 95 | 2000 | ||
| 14 | 64 | 53 | 900 | ||
| 15 | 63 | 85 | 1100 | ||
| 16 | 53 | 83 | 850 | ||
| 17 | 77 | 142 | — | ||
| 18 | 65 | 92 | — | ||
| 19 | 91 | 126 | — | ||
| 20 | 90 | 96 | — |
Table 4. Lower bounds from Corollary 15. The columns and give the product of the divisors listed in [6 Table 1], displayed to two decimals; and are computed from the exact integer products and rounded up, being the diameter and 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 , the ratio of 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.
| solution | ||||
| 2 | vs | 1 | 2 | 1.0000 |
| 3 | vs | 4 | 4 | 1.0000 |
| 3 | vs | 12 | 6 | 0.8889 |
| 3 | vs | 36 | 9 | 0.7901 |
| 5 | Chen Shuwen [9 (4.4)] | 117449348889600 | 1976 | 0.9981 |
| 6 | Gloden 1944 | 216770400 | 86 | 0.5487 |
| 7 | Escott 1910 | 13967553600 | 102 | 0.4981 |
| 7 | symmetric, | 37604952000 | 110 | 0.7904 |
| 7 | symmetric, | 11722885574400 | 246 | 0.8807 |
| 8 | Chen Shuwen 1997 | 207048441600 | 96 | 0.4702 |
| 8 | Tarry 1913 | 1210809600 | 50 | 0.5079 |
| 9 | Letac 1942 (I) | 3377425033382400 | 198 | 0.4732 |
| 9 | Letac 1942 (II) | 554721467677977600 | 348 | 0.4857 |
| 10 | Borwein–Lisoněk–Percival (a) | 5687272703608009113600 | 626 | 0.1613 |
| 10 | Borwein–Lisoněk–Percival (b) | 2628768883410597915187200 | 1030 | 0.5128 |
| 12 | Kuosa–Meyrignac–Chen | 67440294559676054016000 | 302 | 0.4915 |
Table 5. The bound (3) on classical ideal solutions of size , in the integral form . 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 ; the columns and 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]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]P. Borwein and T. Erdélyi, Polynomials and Polynomial Inequalities, Graduate Texts in Mathematics 161, Springer, 1995.DOI
- [3]P. Borwein and C. Ingalls, The Prouhet–Tarry–Escott problem revisited, Enseign. Math. (2) 40 (1994), 3–27.DOI
- [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]T. Caley, The Prouhet–Tarry–Escott problem, PhD thesis, University of Waterloo, 2012.
- [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]H. Kleiman, A note on the Tarry–Escott problem, J. Reine Angew. Math. 278/279 (1975), 48–51.DOI
- [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]Chen Shuwen, A survey of the Prouhet–Tarry–Escott problem and its generalizations, arXiv:2506.11429 (2025).