[math-fun] Now for something completely different
I found this problem someone had posed, and after having fun solving it, I thought it might amuse some folks on math-fun: ------------------------------------------------------------------ Let f(N) be the probability that 4 random integers i,j,k,m in the range 1 <= i,j,k,m <= N satisfy gcd(i,j) = gcd(k,m) . Find the limit of f(N) as N -> oo. ------------------------------------------------------------------ (No fair posting an answer if you've seen it before!) --Dan
On Sunday 03 December 2006 18:35, Daniel Asimov wrote:
Let f(N) be the probability that 4 random integers i,j,k,m in the range 1 <= i,j,k,m <= N satisfy
gcd(i,j) = gcd(k,m) .
Find the limit of f(N) as N -> oo.
[The question that follows contains an implicit mild hint, so I'm inserting some blank lines. If you want to solve Daniel's problem without any clues at all, stop reading now; otherwise, scroll down as needed.] Question: is there a (sane) solution that gets to the correct answer without any instances of pi^2 and pi^4 along the way? -- g
On 12/3/06, Daniel Asimov <dasimov@earthlink.net> wrote:
... ------------------------------------------------------------------ Let f(N) be the probability that 4 random integers i,j,k,m in the range 1 <= i,j,k,m <= N satisfy
gcd(i,j) = gcd(k,m) .
Find the limit of f(N) as N -> oo. ------------------------------------------------------------------ ...
Very nice. I suppose I'd better put in some blank lines as well, before I continue ... I have to admit I've still no idea why \sum \mu(k) / k^2 = 6 / \pi^2 --- what's more neither has Maple, which makes me feel a little better. WFL
[Blank lines to avoid giving things away] On Sunday 03 December 2006 23:08, Fred lunnon wrote:
I have to admit I've still no idea why
\sum \mu(k) / k^2 = 6 / \pi^2
I'm not sure whether "no idea why" means "no idea how to prove" or "no brief argument making it obvious that". I'll assume the former, because if you mean the latter then I "have no idea" either :-). I'd get there via sum 1/k^2 = pi^2/6, and I guess you would too. I'm not sure which portion is troubling you. There's no really short self-contained proof for sum 1/k^2 = pi^2/6, but if you don't mind assuming a bit of the theory of Fourier series then you can get there quite quickly via Parseval's theorem. To get from there to sum mu(k)/k^2 = 6/pi^2, note that it's enough to prove [sum mu(k)/k^2][sum 1/k^2] = 1. This is standard Dirichlet series stuff (LHS is the case s=2 of the product of the Dirichlet series for mu(k) and for 1, which is the "Dirichlet convolution" of those series, etc.), but it's easy enough from first principles: expand the product in the LHS to get sum {k,l} of mu(k)/(k^2.l^2); change variable via n=kl to get sum {n} of 1/n^2 . sum {k|n} mu(k); the inner sum is well known (and easily proved) to be 1 when n=1 and 0 otherwise. -- g
On 12/3/06, Gareth McCaughan <gareth.mccaughan@pobox.com> wrote:
[Blank lines to avoid giving things away]
... but it's easy enough from first principles: expand the product in the LHS to get sum {k,l} of mu(k)/(k^2.l^2); change variable via n=kl to get sum {n} of 1/n^2 . sum {k|n} mu(k); the inner sum is well known (and easily proved) to be 1 when n=1 and 0 otherwise.
Right, that's the bit I (along with Maple) had trouble with. On 12/4/06, Daniel Asimov <dasimov@earthlink.net> wrote:
I may be mistaken, but I have the impression that someone is solving a similar but different question (What is the probability that two random integers are relatively prime?)
Sounds as if Dan has figured out the answer to Gareth's earlier question, if not how the rest of us tackled the problem! Maybe it's time he came clean (after the statutory 40 blank lines, of course). WFL
On 12/3/06, Daniel Asimov <dasimov@earthlink.net> wrote:
... ------------------------------------------------------------------ Let f(N) be the probability that 4 random integers i,j,k,m in the range 1 <= i,j,k,m <= N satisfy
gcd(i,j) = gcd(k,m) .
Find the limit of f(N) as N -> oo. ------------------------------------------------------------------
Well, if Dan does have a \pi-free argument, I'll be interested to see it. But I now have a \mu-free one, so here it is [a long way down, to be sure]. Let S(p, q) denote the subset of the lattice S of integer vectors [i,j,k,l], such that hcf(i,j) = p and hcf (k,l) = q; and let c denote the density of S(1, 1). Then S is the direct union of the S(p,q), so 1 = \sum_{p,q} c / p^2 q^2 = c \zeta(2)^2 = c \pi^2 / 36; the problem demands the density of the direct union of the S(p,p), = \sum_{p} c / p^4 = c \zeta(4) = c \pi^2 / 90, = (c \pi^2 / 36) 2/5 = 2/5 by the above. Fred Lunnon
On Monday 04 December 2006 07:52, Fred lunnon wrote:
Well, if Dan does have a \pi-free argument, I'll be interested to see it. But I now have a \mu-free one, so here it is [a long way down, to be sure].
Let S(p, q) denote the subset of the lattice S of integer vectors [i,j,k,l], such that hcf(i,j) = p and hcf (k,l) = q; and let c denote the density of S(1, 1).
Then S is the direct union of the S(p,q), so 1 = \sum_{p,q} c / p^2 q^2 = c \zeta(2)^2 = c \pi^2 / 36; the problem demands the density of the direct union of the S(p,p), = \sum_{p} c / p^4 = c \zeta(4) = c \pi^2 / 90, = (c \pi^2 / 36) 2/5 = 2/5 by the above.
Substantially the same as my argument, for what it's worth, but WFL's is more neatly expressed and implicitly includes a proof that P(p,q coprime) = zeta(2), which I took for granted. On the other hand, the more banal way in which mine's expressed *may* make it easier to follow: 1/N^4 # { p,q,r,s in [1,N] : (p,q) = (r,s) } = 1/N^4 sum over d of # { p,q,r,s in [1,N] : (p,q) = (r,s) = d } = 1/N^4 sum over d of (# { p,q in [1,N] : (p,q) = d })^2 = 1/N^4 sum over d of (# { p,q in [1,N/d] : (p,q) = 1 })^2 ~ 1/N^4 sum over d of (6/pi^2 (N/d)^2)^2 = 36/pi^4 sum over d of 1/d^4 = 36/pi^4 pi^4/90 = 2/5 -- g
participants (3)
-
Daniel Asimov -
Fred lunnon -
Gareth McCaughan