This question follows the article discussed here


Suppose we're trying to bound the number of integral solutions to a system of multi-variable polynomials, say

$$ \sum_{i=1}^n x_i^t = \sum_{i=1}^n y_i^t, $$ where each $x_i,y_i \in \mathbb N$ and for each $t < c$ for some constant $c$.

If we do not put any constrains on the solution, there are infinitely many possible solutions even when $n=C=1$. So if we put some constrains on {$x_i,y_i$} like $x_i,y_i \in$ {$0,1,\ldots,n$}, then how many possible solutions can we get? Naively there are $O(n^n)$ choices, but it seems highly unlikely that there are many solutions to the system of equations. Is there any exist bound on the number of solutions, say $O(n^k)$ for fixed $k$ or even better bounds? Are there some well-known approaches to bound the number of solutions of an equation?


This question arose when I'm trying to come up with some reasonable constrains with the equation in Prouhet-Tarry-Escott Problem. It seems like if we restrict the maximum value of variables, there aren't many solutions to the equation. I tried to add more constrains to get rid of the already few solutions, but it seems that there is no direct way making the solution set empty, that is, no possible solutions under such constrains.

So I turn to find some existing bounds for the equation, but sadly nothing occurred. Can it be still hard to find such results, or there are some theorems like the Fundamental Theorem of Algebra, concerning the number of solutions to a multi-variable equation? Any information is useful. Thank you all!


According to Felipe Voloch (Thanks!), the general approach to the question is the Hardy-Littlewood method, which considers the number of solutions to an equal-power Diophantine equation. But it seems that the method gives a lower bound on the number of solutions (is this correct?), rather than an upper bound. Or there are some ways to give upper bounds by the same method?

One more question: How about further restricting the solutions to be prime numbers? Does this make any difference?

  • $\begingroup$ In its most general form, this problem is undecidable; en.wikipedia.org/wiki/Diophantine_set#Matiyasevich.27s_theorem . Any substantive answer to a question of this type therefore has to be very sensitive to the type of equations considered. $\endgroup$ Apr 17, 2010 at 18:58
  • $\begingroup$ @Qiaochu: He has a very specific equation in mind, sums of equal powers. I don't think undecidability is relevant here. $\endgroup$ Apr 17, 2010 at 21:26
  • $\begingroup$ The question is stated in quite some generality. I think information about what level of generality is appropriate is relevant. $\endgroup$ Apr 17, 2010 at 21:44
  • $\begingroup$ Thank you for all your comments! If I cannot provide any bounds on n (since the number of terms is generated by a combinatorial problem, which cannot guarentees the size of n), but I can restrict the solutions lie in prime numbers < n log n (since there are about n prime numbers in this range), and the solution must satisfies the equation above SIMULTANEOUSLY for every t<c for a constant c, say, c=100, can we do better than O(n^n)? $\endgroup$ Apr 18, 2010 at 8:52

1 Answer 1


People studying Waring's problem via the Hardy-Littlewood method often consider this kind of problem. You could start by looking at Vaughan's book, "The Hardy-Littlewood method".

  • $\begingroup$ The original problem itself is a part of Waring's problem: to estimate the number of solutions to $\sum_{i=1}^nx_i^t=N$ as $N\to\infty$. So, any monograph with emphasise on Waring's problem could be a good source. $\endgroup$ Apr 17, 2010 at 23:48
  • $\begingroup$ Thank you for this wonderful method!! I'm trying to read it but since I'm not familiar with this topic, it may take me for a while to understand the context. But still thanks very much for the reference! @Wadim: Since I have to estimate the number of solutions when N is small (say O(n^t) for some constant t), is this method still works? $\endgroup$ Apr 18, 2010 at 8:56
  • $\begingroup$ I found out that in Chapter 6 of the book you provide solved the problem for a single equation fixing the exponent t, and the work by Davenport can be extended to a system of equations. Thank you very much!!! $\endgroup$ Apr 20, 2010 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.