# Number of ways to sum square numbers to yield a given number

I would like to know how many choices of $x_i$ there are such that $$\sum_{i=1}^{n}x_i^2=m$$ where $n$, $m$ are given. The $x_i$ can be any nonnegative integer and need not be unique and the order is relevant. $k=\lfloor \sqrt{m} \rfloor$ is also given and may or may not be useful, I don't know. So basically I'm asking for the integer partition, but with square numbers instead of integers. The 'square partition', I presume?

An example: $n = 3, m =4$ has $3$ solutions, namely $x_1$ = 2, $x_2 = x_3 = 0$ and $2$ permutations. Another example $n = 4, m =4$ has $5$ solutions, namely $x_1$ = 2, $x_2 = x_3 = x_4 = 0$ and $3$ permutations and the solution $x_1 = x_2 = x_3 = x_4 = 1$.

If no exact solution exists, does someone know how to approximate this when $1 << n$ and $1 << m$?

Thank you

-
This general topic is usually called "sums of squares" and is actually a fairly sophisticated number-theoretic topic for fixed $n$. See mathworld.wolfram.com/SumofSquaresFunction.html . –  Qiaochu Yuan Jul 17 '11 at 0:02
An interesting question is then what is the total number of positive square partitions. Ie. do we have an asymptotic for the partition function for squares? (Usual partition function: mathworld.wolfram.com/PartitionFunctionP.html) –  Eric Naslund Jul 17 '11 at 1:18

Let $r_{n}(m)$ denote the number of ways to write $m$ as a sum of $n$ squares. (Order included. Also, we could $-n$ and $n$ when looking at $n^2$) It is fairly simple to give a very nice generating series in terms of a well known modular function. Consider the Jacobi Theta Function $$\vartheta_{3}(x)=\sum_{n=-\infty}^{\infty}x^{n^{2}}.$$ Notice that $$\sum_{m=0}^{\infty}r_{1}(m)x^{m}=\vartheta_{3}(x)=1+2x+2x^{4}+2x^{9}+2x^{16}+\cdots.$$ (Note, we are counting both positive and negative solutions, i.e. $4=(-2)^2$ and $4=2^2$) Also, $$\sum_{m=0}^{\infty}r_{2}(m)x^{m}=\vartheta_{3}(x)^{2}$$ since when we square $\vartheta_{3}(x)$ the only exponents that appear are those which are the sum of two squares. The number of times they appear is the number of different ways to create that sum. Similarly, $$\sum_{m=0}^{\infty}r_{n}(m)x^{m}=\vartheta_{3}(x)^{n}.$$
(Again, the only exponents that appear are those which can be written as the sum of $n$ squares, and the coefficients gives exactly the number of ways to make that sum)