Predicting pi: pretty graphs and convergents

Recall the challenge I posed in a previous post: given the sequence of integers $\lfloor \pi \rfloor, \lfloor 2\pi \rfloor, \lfloor 3\pi \rfloor, \ldots$ , what can you learn about $\pi$ (assuming you didn’t know anything about it before)? The answer, as explained in another post, is that you can learn $\pi$ to whatever precision you like, if you wait long enough. Not only that, but you can do better than is initially obvious. You can learn n digits of the decimal expansion of $\pi$ if you wait for $\lfloor 10^n \pi \rfloor$ , but this is throwing away too much information: instead, noting that $\lfloor n \pi \rfloor \leq n\pi < \lfloor n \pi \rfloor + 1$ , we get upper and lower bounds on $\pi$ from each term in the sequence:

$\displaystyle\frac{\lfloor n\pi \rfloor}{n} \leq \pi < \frac{\lfloor n\pi \rfloor + 1}{n}.$

Let’s graph these upper and lower bounds for various values of n:

Neato! We can view this in a slightly different way by graphing the error (the amount under or over $\pi$ ) of the approximations instead of the approximations themselves:

So, that looks pretty cool… but the best approximations quickly get so close to $\pi$ that it’s hard to see what’s really going on. So now we’re going to (a) zoom way out—the graph will go to n = 50000 instead of just 200, and (b) use a log-log scale—that is, we’ll graph the logarithm of both the error and n.

Cool! Now we can see some more interesting structure at the bottom of the graph (in the previous graph, the approximations quickly got so close to the axis that it was impossible to tell what was going on; this is why plotting the logarithm of the error helps). We can see that most of the approximations are in that big mass sloping gently down and to the right. This represents about how well we would do at approximating pi if we just looked at the $10^n$ th elements of the sequence. But the interesting thing is the approximations which are not part of that big mass. At several places—most notably at around n=5, n=100, and n=30000—there are downward spikes, representing approximations which jump out as being way better than most of the other ones at that point. These are precisely the convergents of $\pi$ , which are (in a specific technical sense) the best rational approximations to $\pi$ . This is why, by looking at all the approximations and choosing the best ones, we can do much better than just looking at the $10^n$ th elements of the sequence (imagine a line drawn through the bottommost points in the graph; it’s much steeper than the average slope of the big mass of approximations above it). In a future post I hope to write a bit more about these so-called “convergents” and where they come from; I’ve actually written a bit about them before, but didn’t point it out at the time!

About Brent

Associate Professor of Computer Science at Hendrix College. Functional programmer, mathematician, teacher, pianist, follower of Jesus.

View all posts by Brent →

5 Responses to Predicting pi: pretty graphs and convergents

Michael Lugo says:

January 17, 2009 at 8:40 am

What’s more, the downward spikes (in general) converge about twice as fast as the big mass of approximations. That is, the best approximation of a real number x by rationals with denominator less than n is good to about 1/n^2. (This result is known as “X’s Theorem” for some name X that I can’t remember now.)
Brent says:

January 17, 2009 at 11:49 am

Yes, X = Dirichlet if I recall correctly. =)
Pingback: Carnival of Mathematics 47, where no, well… « JD2718
Michael Lugo says:

January 17, 2009 at 6:49 pm

Armed with that knowledge, I poked around a bit. Dirichlet’s theorem says the exponent is at least 2; the Thue-Siegel-Roth theorem says it’s at most 2.
Brent says:

January 17, 2009 at 7:27 pm

Ah, thanks, I hadn’t remembered the Thue-Siegel-Roth results, although now that you mention it I think it was mentioned (but not proved) in my undergrad number theory course.

Comments are closed.