Number of ways to express $n$ as a sum of squares of integers

Question

Let $n$ be a positive integer.

The question is, how many ways are there, to write $n$ as $\sum_i a_i^2$, where $a_i$ are some positive integers.

The lenght of $a_i$ is irrelevant so that one could formulate this abstractly as follows. Let $$P_n := \{ a = (a_i)_{i\in \mathbb{N}} \in \mathbb{N}^{(\mathbb{N})} | \sum_{i} a_i^2 = n \text{ and } a_j = 0 \implies a_k = 0 \ \forall \ k \geq j \}.$$ Then, what is the size of $P_n$?

(I write $\mathbb{N}^{(\mathbb{N})}$ for sequences with values in $\mathbb{N}$ that are eventually $0$).

So far, I have a recursive formula:

$P_n = \coprod_{x \leq \sqrt{n}} P_{n - x^2}$

With this, one could compute the exact value for a given number, but the number of terms gets large quickly. (I wrote a basic program but the results neither enable me to find a formula, nor to reach numbers greater than ~60).

If a closed formula for the size of $P_n$ seems to be difficult, I would also be interested in upper bounding it, such that the upper bound is not to far off.

I couldn't find anything in literature (e.g. by using Google) but maybe I am missing the correct words, so I would also appreciate any hints on that direction.

Answer 1

If $p_n$ is the cardinality of $P_n$ then $\log_2 p_n$ is approximately $\frac n2$. I wrote a little python script to compute the values and graph them.

from math import log2
from matplotlib import pyplot as plt

P = [1, 1]
for n in range(2,1001):
    a = 0
    k = 1
    while k*k <= n:
        a += P[n-k*k]
        k += 1
    P.append(a)
y = [log2(x) for x in P[1:]]
x = list(range(1,1001))

plt.plot(x,y)
plt.show()

This produced

This looks like a good starting point to me.

Answer 2

I computed the first few terms and looked this up in the Encyclopedia of Integer Sequences: https://oeis.org/A006456 . Two of the references there are:

• N. Robbins, On compositions whose parts are polygonal numbers, Annales Univ. Sci. Budapest., Sect. Comp. 43 (2014) 239-243. See p. 242. (http://ac.inf.elte.hu/Vol_043_2014/239_43.pdf and

• J. Bohman et al., Partitions in squares, Nordisk Tidskr. Informationsbehandling (BIT) 19 (1979), 297-301. (Annotated scanned copy), https://oeis.org/A001156/a001156.pdf)

and these both give the asymptotic relation $P_n \sim C \lambda^n$, where (following Bohman's notation)

• $\lambda \approx 1.417742546$ is the reciprocal of the unique positive root $\mu \approx 0.705$ of $x + x^4 + x^9 + x^{16} + \cdots = 1$
• $C = (\mu + 4 mu^4 + 9 \mu^9 + \cdots) \ \approx 0.46542113$

This follows from standard results in the theory of linear recurrences. The constant $\lambda$ is close to $\sqrt{2}$ so this agrees with saulspatz's numerical work. I don't expect that there's an exact formula.