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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .