wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Counting Pythagorean Quadruples
        
(Message started by: JocK on Dec 24^th, 2007, 1:57pm)

Title: Counting Pythagorean Quadruples
Post by JocK on Dec 24^th, 2007, 1:57pm

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 A_n be the number of nodes whose distance* to a given node is integer and not exceeding n. Give an asymptotic expression for A_n.

* Distance is the normal Euclidian (straight line) distance.

Title: Re: Counting Pythagorean Quadruples
Post by towr on Dec 24^th, 2007, 2:22pm

[hide]Doesn't it tend to the volume of the sphere with radius n?[/hide]

Title: Re: Counting Pythagorean Quadruples
Post by JocK on Dec 25^th, 2007, 1:46am

on 12/24/07 at 14:22:30, towr wrote:

[hide]Doesn't it tend to the volume of the sphere with radius n?[/hide]

For larger n increasingly smaller fractions of the nodes within distance n are at integer distance. As a result, A_n isn't proportional the cube of n.

Title: Re: Counting Pythagorean Quadruples
Post by towr on Dec 25^th, 2007, 2:01am

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. :-[

Title: Re: Counting Pythagorean Quadruples
Post by Hippo on Dec 25^th, 2007, 12:30pm

First observations ... the ratio A_n/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 a²+b²+c²=k²
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(a²+b²))

Title: Re: Counting Pythagorean Quadruples
Post by Barukh on Dec 26^th, 2007, 9:01am

Welcome back, JocK! :D

This (http://en.wikipedia.org/wiki/Pythagorean_quadruple) may help, if taken carefully.

Title: Re: Counting Pythagorean Quadruples
Post by Hippo on Dec 26^th, 2007, 11:09am

on 12/26/07 at 09:01:17, Barukh wrote:

Welcome back, JocK! :D

This (http://en.wikipedia.org/wiki/Pythagorean_quadruple) 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 ... :(

Title: Re: Counting Pythagorean Quadruples
Post by Eigenray on Jan 8^th, 2008, 12:22am

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 m²+n², p²+q², and np-mq, which is quite possible.

This may help: Let f(k) = r₃(k²) be the number of solutions to x² + y² + z² = k². Then

f(k) = 6*oddpart(k)*http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif[1 + 2(1-p^-e)/(p-1)],

where the product is over all primes p = 3 mod 4, with p^e the largest power of p dividing k. [Follows from equation (3) in [link=http://citeseer.ist.psu.edu/hirschhorn99representations.html]M. D. Hirschhorn and J. Sellers, On representations of a number as a sum of three squares, Discrete Math. 199 (1999), 85--101[/link], found via Google]

Then

A_n = 1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif_k=1ⁿ f(k).

Numerically:

A₁₀₀₀₀₀ = 26937841441
A_1000000 = 2693774806225
A_10000000 = 269377071159793,

so it looks like A_n ~ 2.69377 n². 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 A_n ~ C/2 n². 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 p^e with probability (p-1)/p^e+1. So the expected value of each term is

1 + http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/sum.gif(p-1)/p^e+1*2(1-1/p^e)/(p-1) = 1 + 2/(p²-1).

Therefore we feel somewhat justified in putting

C = 6*2/3 * http://www.ocf.berkeley.edu/~wwu/YaBBImages/symbols/prod.gif(1 + 2/(p²-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?