Stat 134 Fall 2011: A note on 6/π2Michael LugoSeptember 9, 2011Attention conservation notice: this note is devoted to proving some of the paren-thetical comments I made after the question about random integers on the homework. Youdon’t need to read this. But if the claim that “the probability that two random integers arerelatively prime is 6/π2interests you, read on.In problem P7, from the second homework assignment, you were asked to compute theprobability that if we choose two integers x and y uniformly at random from {1, 2, . . . , 6n},then they are both divisible by 2 or they are both divisible by 3. This is 1/4 + 1/9 − 1/36 =1/3.The reason for having 6n here, instead of n, is to simplify the calculation. If we pick twointegers x, y uniformly at random from {1, 2, . . . , n}, where n is not necessarily divisible by6, then this probability will not always be 1/3. However, it will be near 1/3. In the tablebelow I put an X in row x, column y if either x and y are both divisible by 2 (for example,x = 2, y = 4) or both are divisible by 3 (for example, x = 3, y = 6).1 2 3 4 5 6 7 8 9 10 11 1212 X X X X X X3 X X X X4 X X X X X X56 X X X X X X X X78 X X X X X X9 X X X X10 X X X X X X1112 X X X X X X X XSo, for example, if we pick two integers between 1 and 3 uniformly at random, theprobability that both are divisible by 2 or that both are divisible by 3 is 2/9 – there are ninepossible choices, of which only (2, 2) and (3, 3) satisfy the condition.The probability p(n) that a random pair (x, y) with 1 ≤ x, y ≤ n satisfies this conditionis, for 1 ≤ n ≤ 12:1n 1 2 3 4 5 6 7 8 9 10 11 12f(n) 014295165251236124919642481331003312148144As you can see these seem to approach 1/3, although not very quickly.When we talk about independence, it will make sense to say that the probability thattwo random integers are both divisible by 2 is independent of the probability that they’reboth divisible by 3. In particular the probability that neither of these events happens can becalculated as (1−1/4)(1− 1/9) = 2/3, consistent with the answer to the homework problem.Similarly, the probability that x and y are not both divisible by a prime number p is(1 − 1/p2), and we might expect these events to be independent. (Why primes? Well, theevent “x and y are both divisible by 4”, for example, has probability 1/42= 1/16; the event“x and y are both divisible by 6” has probability 1/62= 1/36; but the intersection of theseevents is the event “x and y are both divisible by 12”, which has probability 1/122, showingthat divisibility by 4 and by 6 are not independent. Working just with the primes avoidsthis problem.)The probability that x and y do not have any prime factor in common, then, mightreasonably be thought to be1 −1221 −1321 −152· · · =Yp prime1 −1p2and we want to show that this is 6/π2. This is related to a famous problem known asthe “Basel problem”, which is to show that1 +122+132+142+ · · · =π26.So at this point we need to do two things: show that the two problems have answerswhich are the reciprocals of each other, and do the sum.To show the claim about reciprocals, notice that1 −1p2−1=p2p2− 1=11 − p−2= 1 +1p2+1(p2)2+1(p3)2+ · · ·where the last equality comes from the formula 1 + r + r2+ · · · = 1/(1 − r) for the sumof a convergent geometric series. Therefore we have11 −1221 −1321 −152· · ·(1)=1 +122+142+182+ · · ·1 +132+192+1272+ · · ·1 +152+1252+11252+ · · ·· · ·(2)Now consider doing the multiplication here. I claim that this product is just 1 +122+132+142+ · · · , the sum of the reciprocals of the squares. To see this, consider how the processof multiplication works, and recall that every integer has a unique prime factorization. The2number 12, for example, is 22× 3, or 4 × 3. So we will get the term1122in the product bytaking the142from the first factor, the132from the second factor, and the 1 from every otherfactor. Since factorizations are unique we’ll get 1/n2exactly once in doing this expansion.So now it only remains to show thatPn≥11n2=π26. This is the famous “Basel problem”,posed by Mengoli in 1644 and solved by Euler in 1735. I first learned about this solutionfrom William Dunham’s book Journey through Genius.Recall that sin(x) = x−x3/6+x5/120−· · · . Therefore sin(x)/x = 1−x2/6+x4/120+· · · .Now consider that sin(x)/x has zeroes at ±π, ±2π, ±3π, and so on – all the multiples of π,except 0. At x = 0, sin(x)/x = 1. (Formally speaking, this is a limit.) It turns out that thisis enough information to write sin(x)/x as an infinite product.To motivate this, let’s say you have an unknown function g, with g(0) = 1, g(2) =0, g(3) = 0. The “simplest” such function is (1 − x/2)(1 − x/3); each factor is 1 at x = 0,and at 2 and 3 the first and second factors, respectively, are zero. Euler’s stroke of genius(well, one of them) was to assume that a function like sin(x)/x works the same way, and sohe guessedsin(x)x=1 −xπ1 +xπ1 −x2π1 +x2π· · ·and combined pairs of factors to getsin(x)x=1 −x2π21 −x24π21 −x29π2· · ·Now, take the coefficient of x2on both sides. The coefficient of x2on the left-hand sideis −1/6, from the Taylor series for sine. The coefficient of x2on the right-hand side is−1π2−14π2−19π2+ · · · = −1π2Xn≥11n2.Setting these equal gives−16= −1π2Xn≥11n2and solving for the sum givesPn≥11n2=π26, which is what we wanted.This trick similarly givesPn≥11n4,Pn≥11n6, and so on for any even power, although ittakes a bit more work. In general ζ(2n) is a rational multiple of π2n. These are values of theso-called Riemann zeta function, which is important in analytic number theory: we writeXn≥11ns= ζ(s).But no nice form is known for ζ(3) ≈ 1.202; in particular it’s known that ζ(3) is irrational butit’s not known if ζ(3)/π3is irrational. (It seems quite likely that it is; if ζ(3)/π3is rational itwould have to have quite large numerator and denominator, just based on numerical work.Compare ζ(2)/π2=
View Full Document