Why are there usually an even number of representations as a sum of 11 squares - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T00:44:31Z http://mathoverflow.net/feeds/question/28462 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares Why are there usually an even number of representations as a sum of 11 squares Kevin O'Bryant 2010-06-17T05:32:00Z 2010-07-10T17:44:02Z <p>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$?</p> <p>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$.</p> <p>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 <a href="http://mathoverflow.net/questions/26839/how-thick-is-the-reciprocal-of-the-squares" rel="nofollow">this question</a>.</p> <p>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$.</p> <p>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.</p> <p>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.</p> http://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares/28567#28567 Answer by Will Jagy for Why are there usually an even number of representations as a sum of 11 squares Will Jagy 2010-06-17T21:00:51Z 2010-07-10T17:44:02Z <p>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}$$</p> <p>I do not know how to keep this in columns.</p> <pre><code> 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 </code></pre> http://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares/28711#28711 Answer by paul Monsky for Why are there usually an even number of representations as a sum of 11 squares paul Monsky 2010-06-19T01:51:24Z 2010-06-19T20:58:17Z <p>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 &lt; x$ for positive real $x$ is $$O \left( \frac{x \; \log \log x}{\log x} \right).$$<br> Let $R = R(N)$ be the number of triples $(a,b,c) \; \mbox{with} \; a,b,c > 0$ and<br> $$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<br> the $r(N/k^2),$ the sum running over all $k>0$ for which $k^2 | N.$ Now in Disquisitiones, Gauss shows that if<br> $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<br> $$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<br> 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.$$</p> <p>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$<br> respectively, with $(q | p ) = -1$ it can be shown that $R \equiv 2 \pmod 4,$ so that $I$ is odd. This should<br> allow one to get a lower bound for the number of $N &lt; x$ with $I$ odd that's a constant multiple of the upper<br> 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.</p> http://mathoverflow.net/questions/28462/why-are-there-usually-an-even-number-of-representations-as-a-sum-of-11-squares/28783#28783 Answer by Greg Kuperberg for Why are there usually an even number of representations as a sum of 11 squares Greg Kuperberg 2010-06-19T22:27:23Z 2010-06-19T22:27:23Z <p>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$.</p> <p>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.</p>