Author |
Topic: Counting Pythagorean Quadruples (Read 1709 times) |
|
JocK
Uberpuzzler
Gender: 
Posts: 877
|
 |
Counting Pythagorean Quadruples
« on: Dec 24th, 2007, 1:57pm » |
 Quote  Modify
|
rehi all, a math problem for all of you to work on during your Christmas break:
Imagine an infinite cubic grid of unit spacing. Let An be the number of nodes whose distance* to a given node is integer and not exceeding n. Give an asymptotic expression for An.
* Distance is the normal Euclidian (straight line) distance.
|
| « Last Edit: Dec 24th, 2007, 2:12pm by JocK » |
 IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Counting Pythagorean Quadruples
« Reply #1 on: Dec 24th, 2007, 2:22pm » |
Quote Modify
|
Doesn't it tend to the volume of the sphere with radius n?
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
JocK
Uberpuzzler
Gender:
Posts: 877
|
|
Re: Counting Pythagorean Quadruples
« Reply #2 on: Dec 25th, 2007, 1:46am » |
Quote Modify
|
on Dec 24th, 2007, 2:22pm, towr wrote:| Doesn't it tend to the volume of the sphere with radius n? |
|
For larger n increasingly smaller fractions of the nodes within distance n are at integer distance. As a result, An isn't proportional the cube of n.
|
|
IP Logged |
solving abstract problems is like sex: it may occasionally have some practical use, but that is not why we do it.
xy - y = x5 - y4 - y3 = 20; x>0, y>0.
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Counting Pythagorean Quadruples
« Reply #3 on: Dec 25th, 2007, 2:01am » |
Quote Modify
|
Hmm, I can't quite see now why I thought it would. It's like I thought every point on the grid was at integer distance from the center. 
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Counting Pythagorean Quadruples
« Reply #4 on: Dec 25th, 2007, 12:30pm » |
Quote Modify
|
First observations ... the ratio An/n would be "assymptotically" increasing ... with each point at distance n there are points at distances kn for an integer k. There is 6n+1 trivial solutions with 2 cordinates equal zero, with each pythagorian triangle there are 24 solutions, but there wolud be other solutions to a2+b2+c2=k2
with integer k.
If we are thinking about assymptotics, we are asking for probability a randomly choosen a,b,c gives interer k. (Monte Carlo ... choose a,b,c in [0,n], compute k=a++b++c and if k<=n add 1 to p iif k is integer and add 1 to q for such k<=n ... p/q would approximate the ratio to the ball volume. And if we compute the probability exactly ...)
(a++b denotes sqrt(a2+b2))
|
|
IP Logged |
|
|
|
Barukh
Uberpuzzler
Gender:
Posts: 2276
|
|
Re: Counting Pythagorean Quadruples
« Reply #5 on: Dec 26th, 2007, 9:01am » |
Quote Modify
|
Welcome back, JocK! 
This may help, if taken carefully.
|
|
IP Logged |
|
|
|
Hippo
Uberpuzzler
Gender:
Posts: 919
|
|
Re: Counting Pythagorean Quadruples
« Reply #6 on: Dec 26th, 2007, 11:09am » |
Quote Modify
|
on Dec 26th, 2007, 9:01am, Barukh wrote:Welcome back, JocK!
This may help, if taken carefully. |
|
From the link ... so we start from quadruples m,n,p,q such that m++n++p++q <= N (the original n). And count them with all symmetries and multiply by N/(m++n++p++q) ... but there is no note how many times we can generate the same tuple ... 
|
| « Last Edit: Dec 26th, 2007, 1:19pm by Hippo » |
IP Logged |
|
|
|
Eigenray
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 1948
|
|
Re: Counting Pythagorean Quadruples
« Reply #7 on: Jan 8th, 2008, 12:22am » |
Quote Modify
|
Another problem is that the parameterization generates non-primitive solutions too, even if gcd(m,n,p,q)=1. For if r is a prime 1 mod 4, then r will divide gcd(a,b,c,d) when it divides m2+n2, p2+q2, and np-mq, which is quite possible.
This may help: Let f(k) = r3(k2) be the number of solutions to x2 + y2 + z2 = k2. Then
f(k) = 6*oddpart(k)* [1 + 2(1-p-e)/(p-1)],
where the product is over all primes p = 3 mod 4, with pe the largest power of p dividing k. [Follows from equation (3) in M. D. Hirschhorn and J. Sellers, On representations of a number as a sum of three squares, Discrete Math. 199 (1999), 85--101, found via Google]
Then
An = 1 +  k=1n f(k).
Numerically:
A100000 = 26937841441
A1000000 = 2693774806225
A10000000 = 269377071159793,
so it looks like An ~ 2.69377 n2. I'm not even going to try making this rigorous, but I have a formula for what I'm sure must be the above constant.
Suppose we could approximate f(k)/k by some constant C. Then An ~ C/2 n2. So here goes:
The 'expected value' of oddpart(k)/k is:
1/2*1 + 1/4*1/2 + 1/8*1/4 + .... = 2/3.
For each term in the product, k is divisible exactly by pe with probability (p-1)/pe+1. So the expected value of each term is
1 + (p-1)/pe+1*2(1-1/pe)/(p-1) = 1 + 2/(p2-1).
Therefore we feel somewhat justified in putting
C = 6*2/3 * (1 + 2/(p2-1)),
where the product is over all primes p=3 mod 4, and numerically, indeed,
C/2 ~ 2.69377.
Jock, how did you come upon this result?
|
| « Last Edit: Jan 8th, 2008, 12:40am by Eigenray » |
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print