# Why are there usually an even number of representations as a sum of 11 squares

Question: Why do so few $n\equiv 3 \bmod 8$ have an odd number of representations in the form $$n=x_0^2 + x_1^2 + \dots + x_{10}^2$$ with $x_i \geq 0$?

Note that $x_i\geq 0$ spoils the symmetry enough that this is not the usual "number of representations as a sum of squares" question. The question may be ill-posed, too: I do not know that there are few such $n$, but computations suggest that their counting function is $\sim cx/\log x$.

The question I'd like to answer is this: which $n$ have an odd number of representations of the form $$n=x_0^2+2x_1^2+4x_2^2+ \dots = \sum_{i=0}^\infty 2^i x_i^2,$$ where $x_i \geq 0$? Does the set of such $n$ have 0 density? The motivation for this question is that it is nontrivially the same as this question.

If $n$ is even and has an odd number of reps, then (nice exercise) $n$ has the form $2k^2$. If $n\equiv 1\pmod4$ and has an odd number of reps, then (challenging but elementary) $n$ has a special sort of factorization, and there are very few such $n$.

The question I'm asking here is for $n\equiv 3 \bmod 8$. Reducing modulo 8 reveals that $x_2$ must be even. If it isn't a multiple of 4, then we can pair off the two reps: $$(x_0,x_1,x_2,x_3,x_4,x_5,\dots) \leftrightarrow (x_0,x_1,2x_4,x_3,x_2/2,x_5,\dots).$$ If $x_2$ is a multiple of 4 but not 8, then we can make a similar pairing with $x_2$ and $x_5$, and so on. This only leaves the situation when $x_2$ and $x_4,x_5,\dots$ are all zero.

This leaves us at: Which $n\equiv 3\bmod 8$ have an odd number of representations in the form: $$n = x_0^2 + 2x_1^2 + 8 x_3^2 \; , \; \; \mbox{with} \; \; x_0, x_1, x_3 \geq 0 \;?$$ Some play with the parities of binomial coefficients reduces this to the question I led with.

-
Are you assuming that $x_i$ is non-increasing? –  Sune Jakobsen Jun 17 '10 at 6:02
What do you mean by "so few"? Numerically, I find 6,802 of the first 20,000 $n \equiv 3 \bmod 8$ have an odd number of representations as $x_0^2+2x_1^2+8x_3^2$. Are you asking why this is 34% rather than 50%, or am I misunderstanding the question? –  Hugo van der Sanden Jun 17 '10 at 10:26
@Sune: I am not assuming $x_i$ non-increasing. So, for example, 3 has $\binom{11}{3}=165$ representations as a sum of 11 squares. –  Kevin O'Bryant Jun 17 '10 at 11:48
@Hugo: You are understanding the question correctly. As you go out further and further, that percentage keeps falling, albeit slowly. I'm asking if it gets to zero, and if so, why. –  Kevin O'Bryant Jun 17 '10 at 11:50
If I am not mistaken, the odd number of representations as $a^2+2b^2+8c^2$ can only happen for $n$ of the form $a^2+2b^2$ or $a^2+2pb^2$ where $a,b$ are positive integers and $p$ is a prime number which is 1 mod 4. Is there any chance that the set of $n$'s representable this way has zero density? –  Sergei Ivanov Jun 18 '10 at 18:30

Throughout $N>0,$ and $N \equiv 3 \pmod 8.$ Let $I$ be the number of ordered triples $(a,d,e) \;\mbox{with} \; a,d,e \geq 0,$ such that $$a^2+2 d^2+8 e^2=N.$$ I'll use a result of Gauss on sums of 3 squares to show that if there are 3 or more primes whose exponent in the prime factorization of $N$ is odd, then $I$ is even. As a consequence those $N$ for which $I$ is odd form a set of density 0; in fact the number of such $N < x$ for positive real $x$ is $$O \left( \frac{x \; \log \log x}{\log x} \right).$$
Let $R = R(N)$ be the number of triples $(a,b,c) \; \mbox{with} \; a,b,c > 0$ and
$$a^2+b^2+c^2=N,$$ and let $r(N)$ be the number of such triples with the $\gcd(a,b,c) = 1.$ Then $R$ is the sum of
the $r(N/k^2),$ the sum running over all $k>0$ for which $k^2 | N.$ Now in Disquisitiones, Gauss shows that if
$N>3, \mbox{then} \; r(N)/3$ is the number of classes (under proper equivalence) of positive primary binary forms of discriminant $- N.$ (Or if you prefer, the number of classes of invertible ideals in the quadratic order of discriminant $- N$). Now these classes form a group, and Gauss uses genus theory to show that the order of this group is divisible by $2^{M-1}$ where $M$ is the number of primes that divide $N.$ So if 3 or more primes have odd exponent in the prime factorization of $N,$ then all these primes divide $N/k^2,$ the corresponding group has order divisible by $2^{3-1}=4,$ so 4 divides each $r(N/k^2),$ and 4 divides $R.$  Now let $S=S(N)$ be the number of pairs $(a,d) \; \mbox{with} \; a,d > 0$ and
$$a^2+2 d^2=N,$$ and $s(N)$ be the number of such pairs with $\gcd(a,d) = 1.$ Then $S$ is the sum of the $s(N/ k^2).$ Using the fact that $\mathbb{Z} \left[ \sqrt{-2} \right]$ is a UFD we can calculate $s(N/k^2);$ it is zero when some prime $p \equiv 5,7 \pmod 8$ divides $N/k^2.$ When this doesn't happen there are 3 or more
primes $q \equiv 1,3 \pmod 8$ dividing $N/k^2,$ so 4 divides each $s(N/ k^2)$ and 4 divides $S$ as well as $R.$ We conclude the proof by showing that $$2I=R+S.$$

Suppose $N \equiv 3 \pmod 8$ and $a^2+b^2+c^2=N,$ with $a,b,c>0.$ Of course $a,b, c$ are odd. If $b \equiv c \pmod 4,$ let $d=(b+c)/2$ and $e = | (b-c)/4 |.$ Otherwise let $d = | (b-c)/2 |$ and $e=(b+c)/4.$ Then $$a^2+2 d^2+8 e^2=a^2+b^2+c^2=N.$$ Furthermore $(a,b,c)$ and $(a,c,b)$ map to the same $(a,d,e).$ The fiber of the map $(a,b,c) \mapsto (a,d,e)$ has 1 element when $e=0$ and 2 elements otherwise. So $2I=R+S.$  If $N = p q$ where $p$ and $q$ are primes congruent to 5 and 7 $\pmod 8$
respectively, with $(q | p ) = -1$ it can be shown that $R \equiv 2 \pmod 4,$ so that $I$ is odd. This should
allow one to get a lower bound for the number of $N < x$ with $I$ odd that's a constant multiple of the upper
bound mentioned above. But whether the number is asymptotic to a constant multiple of $x \; \log \log(x)/ \log (x)$ as Jagy's calculations suggest isn't clear.

-
I wrote a program to print things out when I is odd, here are some good examples ( N= 315 = 3^2 * 5 * 7, N_0 = 35 = 5 * 7, I = 9 ) ( N= 23275 = 5^2 * 7^2 * 19, N_0 = 19, I= 53 ) ( N= 33075 = 3^3 * 5^2 * 7^2, N_0 = 3, I= 99) ( N= 33275 = 5^2 * 11^3, N_0 = 11, I= 91 ) ( N = 38115 = 3^2 * 5 * 7 * 11^2, N_0 = 35 = 5 * 7, I= 99 ) All the N_0 were indeed prime or the product of two distinct primes, all N up to 43027. I'm beginning to get it. –  Will Jagy Jun 19 '10 at 4:27
If N=pq with p=5 mod 8, q=7 mod 8 and q not a square mod p, then I is odd. Since S=0, it's enough to show that the number of invertible ideal classes in the quadratic order of discriminant -pq is congruent to 2 mod 4; to see this note that the non-trivial ambiguous ideal class is represented by an ideal of norm q, and so is not in the principal genus. I suspect this can be used to show that there is a c>0 such that the number of N<x with I odd is >cxloglog(x)/log(x) for large x. Will's calculations suggest a precise asymptotic but this looks hard to prove. –  paul Monsky Jun 19 '10 at 12:24
A precise asymptotic looks to me not so hard to prove. The number of N<x with I odd ought to be asymptotic to cxloglog(x)/log(x) with c= (p1)^2/64. That's because all the following N are in the set, and the remaining N in the set make a contribution that is O(x/log(x)). (a) All N<x of the form (pq)*y^2 with p and q as in my last comment and y prime to pq. (b) A similar set but now p is 3 mod 8, q is 1 mod 8 and q is a square mod p. The factor of 1/8 in c comes from the restrictions on p and q, while the extra (pi)^2/8 comes from the y^2 term. –  paul Monsky Jun 21 '10 at 5:58
In Hardy and Wright, An Introduction to the Theory of Numbers, chapter 22, section 22.18, (pages 368-370 in my paperback Fifth Edition), we have Theorem 437: the count of numbers up to some positive real $x$ that are the product of exactly $k$ (distinct) prime factors is $$\pi_k(x) \; \; \sim \; \; \frac{x \; (\log \log x)^{k-1} }{ (k-1)! \; \log x}$$ They show the same asymptotic behavior for $\tau_k(x),$ exactly $k$ prime factors when these are no longer required to be distinct. It appears that analogous results with an arithmetic progression specified for each prime are known. –  Will Jagy Jun 22 '10 at 17:28

ORIGINAL:The counting function looks better with an extra factor of $\log \log n$ in the numerator. That is, the cumulative count of numbers $\equiv 3 \pmod 8$ up to some $x$ that have an odd number of your representations resembles $$\frac{ C \;x \; \log \log x}{\log x}$$

I do not know how to keep this in columns.

        n      odd    even    n / odd      / log n     * log log n
3       1       0    3           2.73071768   0.256818066
7995     405     595   19.7407407   2.1966932    4.82334827
15995     775    1225   20.6387097   2.13209118   4.83998588
23995    1147    1853   20.9197908   2.07422357   4.79375621
31995    1495    2505   21.4013378   2.06311065   4.826108
39995    1831    3169   21.8432551   2.06136319   4.86589867
47995    2166    3834   22.1583564   2.05572506   4.88766328
55995    2509    4491   22.3176564   2.041308     4.88237466
63995    2860    5140   22.3758741   2.02193578   4.86058798
71995    3177    5823   22.6613157   2.02616261   4.89220133
79995    3524    6476   22.7000568   2.01068387   4.87368161
87995    3848    7152   22.8677235   2.00857731   4.88546218
95995    4179    7821   22.9708064   2.00232771   4.88550694
103995    4499    8501   23.1151367   2.00094706   4.89605147
111995    4831    9169   23.1825709   1.99399218   4.89178523
119995    5142    9858   23.3362505   1.99536902   4.90696952
127995    5472   10528   23.3908991   1.98906491   4.90241326
135995    5782   11218   23.5204082   1.98981939   4.91450488
143995    6107   11893   23.5786802   1.98514948   4.9125476
151995    6432   12568   23.6310634   1.98054391   4.91014581

-
I think for reasonable numbers one cannot distinguish between $\log\log$ and $\log\log\log$. Perhaps $li(x)$ (or $\pi(x)$) would smooth the numbers enough already. –  Kevin O'Bryant Jun 17 '10 at 21:42

This is not an answer to your stated question, but a relevant remark. Suppose that $a(x)$ is a unipotent formal power series in the formal power series ring $(\mathbb{Z}/p)[[x]]$. (Here unipotent just means constant term 1, so you could say topologically or adically unipotient.) Then obviously $a(x)^n$ is well-defined for any integer $n$. What is somewhat less obvious, but not hard and an interesting general principle, is that $a(x)^d$ is well-defined for any $p$-adic integer $d$. Namely, if $d$ has digits $\ldots d_2d_1d_0$, then $$a(x)^d := a(x)a(x^{d_1p})a(x^{d_2p^2})\cdots$$ It's not hard to check that this formula is (a) correct when $d$ is an integer using the Frobenius map, (b) convergent when $a(x)$ unipotent, and (c) continuous in $d$ and $a$. Therefore (d) it satisfies $a^{d+e} = a^d a^e$ and $(ab)^d = a^db^d$.

You use this formula twice in your question. You use it with $d=-1$ when you call your power series "nontrivially the same" as your other question. You use it again with $d=11$ with the phrase "some play with parities of binomial coefficients". Of course in both cases you're using the power series from your paper, $$a(x) = 1+x+x^4+x^9 + x^{16} + \cdots \in (\mathbb{Z}/2)[[x]].$$ I hadn't thought of this style of $p$-adic exponentiation and I think that it's cute, and it could be a unifying principle for some of what you are doing.

-
This sort of exponentiation arises in Lubin-Tate theory. Here, it seems to be applied to a theta function. –  S. Carnahan Jun 19 '10 at 23:43
I'd have to learn more about Lubin-Tate theory, but I was going to mention this generalization: If $a$ is a unipotent element of any complete local ring $R$ whose residue field is algebraic over $\mathbb{Z}/p$, then exponentiation $a^d$ extends continuously to $p$-adic values of $d$. So, among many other examples, $R$ could be formal power series or the $p$-adic integers. –  Greg Kuperberg Jun 19 '10 at 23:54
Well, the special case $d=-1$ is already there in Kevin's paper as lemma 2.1, and the proof is similar to my remark. I still think that it's an interesting point, but it might not be all that newsworthy. –  Greg Kuperberg Jun 20 '10 at 1:47
We referred to that (amongst ourselves) as the "golden lemma", and it carries quite a bit of the load. –  Kevin O'Bryant Jun 20 '10 at 14:42