Let $n$ be an integer. I'm interested in upper bounding the number of integer solutions of \begin{equation*} x_1^2+x_2^2+\ldots+x_p^2=y_1^2+y_2^2+\ldots+y_p^2, \end{equation*} where for all $i\in\{1,2,\ldots,p\}$ $x_i$ and $y_i$ are integers obeying

\begin{equation*} 0\le x_i\le n-1\\ 0\le y_j\le n-1 \end{equation*}

Alternatively stated I'm interested in upper bounding the sum \begin{equation*} \sum_{x_1,x_2,\ldots,x_p=0}^{n-1}\sum_{y_1,y_2,\ldots,y_p=0}^{n-1}\delta\Big(x_1^2+x_2^2+\ldots+x_p^2-\big(y_1^2+y_2^2+\ldots+y_p^2\big)\Big) \end{equation*} where $\delta(t)$ is the Kronecker delta function with has value $1$ at $t=0$ and zero everywhere else.

FYI, the reason I'm interested in this is because I would like to bound the following quantity. Let $\mathbf{z}\in\mathbb{C}^n$ with entries $z_1,z_2,\ldots,z_n$. I would like to bound the following quantity

\begin{equation*} f(\mathbf{z})=\sum_{x_1,x_2,\ldots,x_p=0}^{n-1}\sum_{y_1,y_2,\ldots,y_p=0}^{n-1}\big(\prod_{i=1}^p z_{x_i}\big)\big(\prod_{j=1}^p\bar{z}_{y_j}\big)\delta\Big(x_1^2+x_2^2+\ldots+x_p^2-\big(y_1^2+y_2^2+\ldots+y_p^2\big)\Big) \end{equation*} where $\bar{z}$ denotes the conjugate of $z$. I was thinking of using the bound \begin{align*} |f(\mathbf{z})|\le\|\mathbf{z}\|_{\ell_\infty}^{2p}\Big(\sum_{x_1,x_2,\ldots,x_p=0}^{n-1}\sum_{y_1,y_2,\ldots,y_p=0}^{n-1}\delta\Big(x_1^2+x_2^2+\ldots+x_p^2-\big(y_1^2+y_2^2+\ldots+y_p^2\big)\Big)\Big) \end{align*} If anybody has any ideas on bounding $|f(\mathbf{z})|$ in terms of $\|\mathbf{z}\|_{\ell_2}^{2p}$ that would be perfect. Here $\|\mathbf{z}\|_{\ell_\infty}$ and $\|\mathbf{z}\|_{\ell_2}$ denotes the maximum absolute value of the entries of $\mathbf{z}$ and the Euclidean norm of $\mathbf{z}$ respectively.

  • 4
    $\begingroup$ Did you try any of the circle method techniques? Vinogradov's method for instance. $\endgroup$
    – Spock
    Sep 20, 2014 at 6:33
  • $\begingroup$ Thanks for the comment. If you mean the original question on bounding the number of equations. The result mentioned below uses related techniques. $\endgroup$
    – mohi
    Sep 20, 2014 at 19:48
  • 2
    $\begingroup$ I'm voting to close this question as off-topic because it has been answered. $\endgroup$ Jun 17, 2015 at 8:04

1 Answer 1


I found an answer to this question. For $p\ge 3$ the bound is \begin{equation*} c_0 n^{2p-2} \end{equation*} with $c_0$ a fixed numerical constant

  • $\begingroup$ This a bound, but not a very strong one. The number of ways to pick $2p-1$ values $x_1,y_1,x_2,y_2,\cdots,x_p$ all in $[0,n-1]$ with no further conditions is $n^{2p-1}.$ Then at most one choice $y^p$ will make the equality you want hold. However usually there is no choice. On the other hand, for $n$ much greater than $p$, there are on order of $p!n^p$ ways to have the $x_i$ distinct and the $y_i$ simply a rearrangement. $\endgroup$ Sep 19, 2014 at 22:18
  • $\begingroup$ actually there is a lower bound so that this is tight up to a constant. I read it a long with the proof of the upper bound but can not find the article right now $\endgroup$
    – mohi
    Sep 19, 2014 at 23:05
  • 5
    $\begingroup$ For fixed $p\ge 3$ the answer is correct and the bound is tight, as you note. But for $p=2$ you need an extra $\log n$ factor. $\endgroup$
    – Lucia
    Sep 19, 2014 at 23:41

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.