Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
3  
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
add comment

1 Answer

Generating Series:

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)

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.