DOC PREVIEW
Berkeley STAT 134 - Lecture Notes

This preview shows page 1 out of 3 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 3 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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 be1 −1221 −1321 −152· · · =Yp prime1 −1p2and 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 that1 −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 have11 −1221 −1321 −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π21 −x24π21 −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

Berkeley STAT 134 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?