# Showing representation numbers are at most on the order of polynomial growth

If $Q$ is the sum of squares quadratic form $\sum_1^n x_i^2$ over some lattice, then $r_Q(m)$, the number of representations of an integer $m$ by $Q$ (order/sign matter) is sometimes given in a nice formula, as in the case with Jacobi's formula in the case of $n=4$. Can we say something moderate about how $r_Q$ grows? It seems like it shouldn't grow faster than polynomially, but I am struggling to see why in a rigorous way. Since $\sum_1^n x_i^2=m$ is the equation of a sphere (or I suppose an ellipsoid if we transform our lattice to $Z^n$ under a change of variable?), we should be able to bound such solutions by some function of the surface area since there should be some small upper bound for the proportion of lattice points over the surface area and the surface area is a polynomial function of the radius.

I would like to make the argument a bit more rigorous, any advice?

Edit: To be clear, I'm interested in how $r_Q(m)$ grows with $m$.

-
Are you interested in how $r_Q$ grows with $r$ or with $Q$? – Ross Millikan Feb 21 '13 at 5:22
$r_Q$ is a function. I'm interested in how it grows with $n$. – user21725 Feb 21 '13 at 5:25
OK, I was thinking of it as a function of $r$ or $Q$, but a function of $n$ is a fine question. It will top out at $n=Q$ unless you count different orders as different. Do you? – Ross Millikan Feb 21 '13 at 5:31
I should have written "grows with $m$", rather than $n$ (assume $n$ is fixed, fixed by $Q$ in fact).Different orders are the same, though signs matter. – user21725 Feb 21 '13 at 5:34
Sorry, scratch that. Order DOES matter. The point is that we are looking at the distinct number of points on a lattice that map to $m$ under $r_Q$. – user21725 Feb 21 '13 at 5:46

For each solution to $\sum_{i=1}^n x_i^2 = m$, you can place an open cube of side-length $1$ centered on that solution. Doing so, you obtain a family of disjoint open cubes covering the solutions, with each open cube having volume $1$. So your next move should be to bound the volume that you can possibly cover with those cubes, polynomially in $m$.

Since every cube centered on $x$ is included in the open ball of radius $\sqrt n/2$ centered on $x$ (using the euclidean metric), and $d(0,x) = \sqrt m$ whenever $x$ is a representation of $m$, you obtain with the triangular inequality that all those cubes are included in $\{y \in \Bbb R^n, \sqrt m - \sqrt n/2 < d(0,y) < \sqrt m + \sqrt n/2 \} = B(0,\sqrt m + \sqrt n/2) - B(0,\sqrt m - \sqrt n/2)$

Since the volume of a ball of radius $R$ is $k_nR^n$ for some constant $k_n$, you get that the volume of this domain is $k_n((\sqrt m + \sqrt n/2)^n - (\sqrt m - \sqrt n/2)^n) \sim k_n(n^{3/2}m^{(n-1)/2})$ (you can also argue intuitively that this should behave like $\sqrt n$ times the area of the sphere of radius $\sqrt m$, and again find a volume bounded by a $K_n m^{(n-1)/2}$).

Since the number of representations of $m$ is bounded by the volume of this domain, and since this volume is a $O(m^{(n-1)/2})$, that number $r_n(m)$ grows polynomially at worst.

You can also use this reasoning with volumes to show that the degree $(m-1)/2$ is the smallest possible for this kind of result : if it wasn't, then putting cubes around every solution of $\sum x_i < R^2$ would tell you that the volume of the sphere of radius $R$ would grow smaller than $R^n$, which is absurd.

-

If order and signs matter, I strongly suspect that for large $n$ it will be dominated by sums of $\pm 1$ and $0$. We have to select $Q$ spots for a non-zero and $2^Q$ signs, so we have ${n \choose Q}2^Q$ expressions. There will be a few more with summands greater than $1$, but for large $n$ they will be insignificant. This is exponential in $n$ and $Q$.

-
So you don't like my ellipsoid argument? – user21725 Feb 21 '13 at 5:58
@EricGregor: not if some of the $x_i$ can be zero. If not, when $n \gt Q$there are no representations. That is a small growth rate. – Ross Millikan Feb 21 '13 at 6:00
Ross, I think the interest is in fixing $n$ and asking about large $m$. – Gerry Myerson Feb 21 '13 at 6:03
@GerryMyerson: for fixed $n$ and large $m$ the surface area argument is a good one. There can't be more than $O(m^2)$ lattice points on the ellipsoid. Most of them won't have a representation with exactly $n$ terms. A few will have more than one, like $25^2=7^2+24^2=15^2+20^2$ but it seems likely not enough to matter. – Ross Millikan Feb 21 '13 at 6:11