mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-11-05, 07:01   #1
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32·5·7·19 Posts
Default Sums of three squares

There's a well-known formula for the number of ways that a number can be expressed as the sum of two squares: the product of one more than the exponents of the primes = 1 mod 4, assuming that all primes = 3 mod 4 appear to an even power (and 0 if any appear to an odd power).

Is there a similarly nice formula for sums of three squares? I was trying to do some calculations with them but the inefficiency of my current program makes that difficult. I'm able to use some properties of such numbers (removing factors of 4, checking mod 8, using an efficient sum of two primes subroutine to remove some cases) but it's still slow -- getting to ten million will take all night, where with sums of two primes that would take 25 seconds.
CRGreathouse is offline   Reply With Quote
Old 2009-11-05, 12:47   #2
R.D. Silverman
 
R.D. Silverman's Avatar
 
Nov 2003

22·5·373 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
There's a well-known formula for the number of ways that a number can be expressed as the sum of two squares: the product of one more than the exponents of the primes = 1 mod 4, assuming that all primes = 3 mod 4 appear to an even power (and 0 if any appear to an odd power).

Is there a similarly nice formula for sums of three squares? I was trying to do some calculations with them but the inefficiency of my current program makes that difficult. I'm able to use some properties of such numbers (removing factors of 4, checking mod 8, using an efficient sum of two primes subroutine to remove some cases) but it's still slow -- getting to ten million will take all night, where with sums of two primes that would take 25 seconds.
I don't know. I would write to Bob Vaughan. He would know the answer.

Last fiddled with by R.D. Silverman on 2009-11-05 at 12:52 Reason: typo
R.D. Silverman is offline   Reply With Quote
Old 2009-11-06, 13:46   #3
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

See formula (35) at http://mathworld.wolfram.com/SumofSquaresFunction.html
maxal is offline   Reply With Quote
Old 2009-11-06, 14:39   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Let me look at that formula and see if there is a good way to translate between it and my problem (essential solutions, not including sign and ordering).


Since this formula applies only for squarefrees, how do I solve r_3(n * s^2)?


Is there a good upper bound on the number of representations? Even a weak one like r_3(n) < n would be nice.

Last fiddled with by CRGreathouse on 2009-11-06 at 14:55
CRGreathouse is offline   Reply With Quote
Old 2009-11-06, 17:48   #5
flouran
 
flouran's Avatar
 
Dec 2008

11010000012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Is there a good upper bound on the number of representations? Even a weak one like r_3(n) < n would be nice.
This should be a common application of sieve theory. Have you tried Halberstam and Richert's text? If that doesn't work, then I would take Bob's advice on contacting Vaughan (although he may be too busy to respond).

I should note that the methods used to achieve an upper bound on the number of representations as the sum of three squares of primes can be modified without much difficulty to provide a corresponding estimate (of the same quality, at worst) for the sum of three squares. The reason for this is that the situation becomes harder if we restrict some variables to primes. Thus, I am sure that the problem of the sum of three squares of primes (or a variant of this problem, at best) is treated in the H-R text.

Last fiddled with by flouran on 2009-11-06 at 17:49
flouran is offline   Reply With Quote
Old 2009-11-06, 17:53   #6
maxal
 
maxal's Avatar
 
Feb 2005

22×32×7 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
Let me look at that formula and see if there is a good way to translate between it and my problem (essential solutions, not including sign and ordering).
Consider different cases depending on the number of nonzero squares in the expansion. If the number of nonzero squares is k, then this expansion is counted 2^k times if signs are taken into account.
Ordering is also possible to take into account by considering cases with distinct/equal squares.
maxal is offline   Reply With Quote
Old 2009-11-06, 19:20   #7
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

32×5×7×19 Posts
Default

Quote:
Originally Posted by maxal View Post
Consider different cases depending on the number of nonzero squares in the expansion. If the number of nonzero squares is k, then this expansion is counted 2^k times if signs are taken into account.
Ordering is also possible to take into account by considering cases with distinct/equal squares.
Of course I'm not enumerating the cases, so telling properties of each isn't obvious. I'll assume n is a positive integer.

If n is a square, there are 6 representations (1 unique) of the number as 0^2 + 0^2 + a^2. If n is twice a square, there are 12 representations (1 unique) of the number as 0^2 + a^2 + b^2, |a| = |b|.

So I guess I can use these and the algorithm for unique representations as two squares to determine the number of unique and nonunique representations as the sum of three squares, the least of which must be 0. So using the formula for r_3 I can determine the number of nonunique representations of n as the sum of three nonzero squares (and the corresponding number of unique representations skipped).

The number of representations as a^2 + b^2 + c^2 with |a| = |b| but |c| distinct from |a| and |b| can be counted directly. The number of representations as a^2 + b^2 + c^2 with |a| = |b| = |c| is 8 if n is thrice a square and 0 otherwise. The total can be subtracted from the above and divided by 48 to get the number of unique representations of the form a^2 + b^2 + c^2 with 0 < a < b < c; the skipped totals can be added on and I'm done.

Computational analysis:
r_3(n) can be computed in time O(n^.25) with Shanks' method. r_2(n) can be computed in time O(n^o(1)). The case with two equal squares can be computed in time O(sqrt(n) log(n)^2) -- the log term is improvable but realistically at the small sizes this is practical at the square root is likely to be quadratic rather than Karatsuba or Toom. So this case dominates the analysis. Is there a better way to count this case?
CRGreathouse is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Sums of all Squares davar55 Puzzles 183 2019-12-12 22:31
Regarding Squares a1call Miscellaneous Math 42 2017-02-03 01:29
Basic Number Theory 12: sums of two squares Nick Number Theory Discussion Group 0 2016-12-11 11:30
squares or not squares m_f_h Puzzles 45 2007-06-15 17:46
Fibonacci sums? TTn Math 2 2002-10-25 21:47

All times are UTC. The time now is 02:41.

Mon Apr 19 02:41:45 UTC 2021 up 10 days, 21:22, 0 users, load averages: 1.67, 1.63, 1.68

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.