# Number of integral solutions to multi-variable polynomials

This question follows the article discussed here

## Problem

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?

## Motivation

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!

## Edited

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?

-
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. –  Qiaochu Yuan Apr 17 '10 at 18:58
@Qiaochu: He has a very specific equation in mind, sums of equal powers. I don't think undecidability is relevant here. –  Felipe Voloch Apr 17 '10 at 21:26
The question is stated in quite some generality. I think information about what level of generality is appropriate is relevant. –  Qiaochu Yuan Apr 17 '10 at 21:44
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)? –  Hsien-Chih Chang 張顯之 Apr 18 '10 at 8:52
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. –  Wadim Zudilin Apr 17 '10 at 23:48