Representing a number as a sum of at most $k$ squares

Question

Fix an integer $k >0 $ and would like to know the maximum number of different ways that a number $n$ can be expressed as a sum of $k$ squares, i.e. the number of integer solutions to $$ n = x_1^2 + x_2^2 + \dots + x_k^2$$ with $x_1 \ge x_2 \ge \dots \ge x_k$ and $x_i \ge 0$ for every $i$.

What I'd really like to know about is the asymptotics as $n \to \infty$.

I asked a number theorist once about the case $k=2$, and if I remember correctly, he said that there are numbers $n$ which can be expressed as a sum of two squares in at least $$n^{c/\log \log n}$$ different ways, for some constant $c > 0$, and this is more-or-less best possible. This is the kind of answer I am seeking for larger $k$.

Clarification:

What I mean by maximum is the following. I want functions $f_k(x)$, as large as possible, such that there exists some sequence of integers $\{ a_i \}$ with $a_i \to \infty$, and such that $a_i$ can be written as the sum of $k$ squares in at least $f_k(a_i)$ ways.

Answer 1

This is an example of "Waring's problem" - expressing integers as the sum of $k$ $p$th powers of integers. In the case of squares, when $k\ge5$ the asymptotics of the number of representations (as a function of $n$) have been known for some time (I believe Hua proved this in the 1930s). When $k\ge5$, the number of ways to write $n$ as the sum of $k$ squares of positive integers is asymptotic to $$ \frac{\Gamma(3/2)^k}{\Gamma(k/2)}n^{k/2-1} S(n), $$ where $\Gamma$ is the Gamma function that interpolates the values of factorials, and $S(n) = S_k(n)$ is the "singular series" that depends upon $n$ but is bounded above and below.

One can find expositions of Waring's problem and the "circle method" (aimed at many different levels) in various places on the web, such as here and here.

Answer 2

The leading term of the asymptotics will be $r_k(n)/k!$ where $r_k(n)$ is the unconstrained number of representations of $n$ as a sum of squares of $k$ integers. For specific $k$ such as 4 or 8 there are classical formulas as sums of arithmetic functions (proofs use modular forms). For fixed $k>4$ the leading term is on average equal to $An^b$ with $A$ and $b$ calculable from volumes of spheres, but as explained in the answer by Greg Martin, the "constant" $A$ is in fact a quasiperiodic function of $n$, the singular series (the product of p-adic densities of solutions to the equation).

Answer 3

This is not an answer to your question. But here's some things I vaguely know.

The introduction of Ila Varma's master thesis

http://www.math.leidenuniv.nl/scripties/VarmaMaster.pdf

written under the supervision of Bas Edixhoven might have some things relevant to what you need. As she says in the introduction, there are closed formulas for even integers $n\geq 12$. She proves that there aren't any formulas for $n > 12$. (This has to do with cusp forms.)

Anyway, there aren't formulas, but there ARE polynomial algorithms. See this paper by P. Bruin.

http://pmb.univ-fcomte.fr/2011/Bruin.pdf

You might want to look at the end of the introduction to his article right after Remark 1.6.

At the end of his article he shows that it's possible to compute these numbers in polynomial time.

Answer 4

Well, unless I missunderstood the problem, it is enough to solve it for $k=2$.

Indeed, if $n$ can be written as $x_1^2+x_2^2$ in $m$ different ways, then

$$n+(k-2)= x_1^2+x_2^2 +1+1+..+1 \,.$$

Solution for $k=2$

Fix an $m$. We will produce infinitelly many $n$ which can be written as a sum of 2 squares in $m$ ways:

Let $a_i^2+b_i^2=c_i^2$ forall $1 \leq i \leq m$. It is easy to produce such triplets with all the numbers to be distinct. Let $n=c_1^2c_2^2...c_m^2$.

Then

$$n=(a_1^2+b_1^2)c_2^2...c_m^2=c_1^2(a_2^2+b_2^2)c_3^2...c_m^2=.....=c_1^2c_2^2...c_{m-1}^2(a_m^2+b_m^2) \,.$$