Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
2  
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
2  
@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
show 3 more comments

3 Answers 3

up vote 11 down vote accepted

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.

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

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

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.

share|improve this answer
    
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
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.