Newsgroups: sci.math Subject: Density of sums-of-2-squares ? From: wft@math.canterbury.ac.nz (Bill Taylor) Date: 5 Jun 92 16:47:27 +1200 We were looking at integers which are expressible as the sums of two perfect squares. It is well known that these are numbers whose prime factors are EITHER 2 or primes of type 4n+1 (any multiplicity), OR primes of type 4n+3, (even powers only). Of particular interest is the density of these, i.e. lim #( sum-2-squares < N ) / N n->inf A colleague here has a convincing-looking pseudoproof that this limiting density should be 0; yet computer searches seem to show that the density is almost constant as N increases, at roughly 1/2 . Probably we haven't really searched far enough. Can anyone tell us if the limiting density is known theoretically ? ---- Bill Taylor wft@math.canterbury.ac.nz ============================================================================== From: A.H.Osbaldestin@lut.ac.uk Newsgroups: sci.math Subject: Re: Density of sums-of-2-squares ? Date: 15 Jun 92 14:25:41 GMT In article <3841@seti.UUCP> flajolet@margaux.inria.fr (Philippe Flajolet) writes: >In article <1992Jun5.164729.5369@csc.canterbury.ac.nz> >wft@math.canterbury.ac.nz (Bill Taylor) writes: > >>We were looking at integers which are expressible as the sums of two perfect >>squares. It is well known that these are numbers whose prime factors are >>EITHER 2 or primes of type 4n+1 (any multiplicity), >>OR primes of type 4n+3, (even powers only). >> >>Of particular interest is the density of these, i.e. >> >> lim #( sum-2-squares < N ) / N >> n->inf >> >>A colleague here has a convincing-looking pseudoproof that this limiting >>density should be 0; yet computer searches seem to show that the density is >>almost constant as N increases, at roughly 1/2 . > >The number of integers to > K. N/sqrt(log(N)). >From the algebraic characterisation of these numbers, a Dirichlet >series involving L-functions is easily found. It behaves near s=1 like >a square root of the zeta function, and by techniques from analytic >number theory (Perron's formula) the result follows. The interesting >thing is the analysis of a Dirichlet series with a branch point. >(K is expressible by a product over primes 4m+3.) Hardy's discussion >of this (as well as the rest of the book for all those that did not >get a chance of reading it!) is extremely nice. > >Ramanujan stated this in a letter to Hardy but the result had been >proved a little earlier by Landau in 1908. See G. H. Hardy, "Ramanujan" >(Chelsea Pub. Co.), p. 60--63. > >The number of integers interesting. The asymptotic form is 5N/6 with an error term that involves a >fractal function (see e.g. Obaldestin and Shiu, Bull. London Math. >Soc. 21 (1989), 369--374). > > Greetings! > > Philippe Flajolet In the article "Counting Sums of Two Squares: The Meissel-Lehmer Method", Mathematics of Computation 47 (1986), 351-360, my colleague Peter Shiu calculates the constant K to be 0.764223653589220... The definition of K is a very slowly convergent product, but Shiu devises an acceleration scheme which enables high accuracy to be easily obtained. In the same article he also gave the exact count of the number of numbers up to 10^12 that are sums of two squares, namely 148736629005. Regards Andy Osbaldestin ============================================================================== From: jenkinsj@blowfish.taligent.com (John H. Jenkins) Newsgroups: rec.puzzles,sci.math Subject: Re: More on pythagorian triples (long) Date: 5 Jun 92 16:17:03 GMT There are well-known forumlae to calculate the number of ways a number can be written as the sum of two squares. Gauss gives one as a footnote to section 182 of the Disquisitiones Arithmeticae. Hardy and Wright have an extensive discussion of the problem (sections 16.9-10 of the fifth edition). I prefer Gauss' way of doing it, personally. Basically, you write N as 2**k * (p1 ** 2e1) * (p2 ** 2e2) * ... * (pn ** 2en) * (q1 ** f1) * ... * (qn ** fn), where the pi are all primes congruent to 3 (mod 4) and the qi are all primes congruent to 1 (mod 4). (If p is a prime congruent to 3 (mod 4) and the highest power of p dividing N is odd, then N cannot be written as the sum of two squares. That's why we have "2ei" instead of "ei".) Gauss' formula for the number of ways N can then be written as the sum of two squares is [(f1 + 1) * (f2 + 1) * ... * (fn + 1)] / 2 if at least one of the fi is odd, and [1 + (f1 + 1) * ... * (fn + 1)] / 2 if they are all even. In this case, since we want to restrict our solutions to squares, we are more interested in the latter case. Thus 65 = 5 * 13 can be written as the sum of squares (1 + 1)(1 + 1)/2 = 2 ways and 65 ** 2 = 5 ** 2 * 13 ** 2 [1 + (2 + 1)(2 + 1)] / 2 = 5 ways. (The original poster only listed four because one of them is trivial: 0 ** 2 + 65 ** 2, which does not make a terribly interesting right triangle.) To find a square that can be written as the sum of squares 7 ways (including the trivial one), we want [1 + (f1 + 1) * ... * (fn + 1)] / 2 = 7, so (f1 + 1) * ... * (fn + 1) = 13, where all the fi are even. 13 is prime, so we have f1 = 12. The smallest number that fits this bill is 5 ** 12, so 5 ** 6 = 15625 should be the smallest number that can serve as the hypoteneuse of a right triangle in 6 non-trivial ways. This whole process is easily automated. I used it to get a list of the smallest number that can be written as the sum of squares exactly N ways for N = 1 to 512. It is also relatively trivial to explicitly list all ways n can be written as the sum of squares ways once you have its factorization. John H. Jenkins jenkinsj@blowfish.taligent.com Disclaimer: Any errors in the above are the fault of my news software and not me.