An Interesting Picture

An interesting picture I found, courtesy of wikipedia. A spent nuclear fuel store.

Pi Day

March 14. Pi Day! We could hardly let such a day pass without a mention.

People have always been interested in . Well, of course that isn’t true, but they’ve certainly been interested for a very long time. People love to calculate digits of pi, memorize and recite digits of pi … the mathematical sort tends to get very excited about pi. Possibly because we have so little to get excited about in general. But the actual digits themselves, calculating and memorizing them, aren’t half as interesting as the methods of calculation and the math behind them.

Pi is generally understood to be the ratio of the circumference of a circle to the diameter. This is constant, approximately 3.14159 and a bit. Of course, some people argue that a more ‘natural’ value for a circle is the radius, not the diameter, and as such the ‘more important’ or more natural value to be interested in is . Whatever floats your mathematical boat.

And it’s certainly the circle interpretation that is at the heart of most methods of calculating pi. For example, taking a purely geometric approach, you can approximate a circle figure and from that, approximate pi. I think the Chinese were the first to use that particular method I use there, a long time ago. The Chinese are good for that sort of thing. Archimedes approximated pi by fitting circles in polygons, and calculating perimeters. Interesting fellow, Archimedes.

The natural extension of the geometric approach is to use trigonometry. The basic trig functions give us easy access to . For example, consider the following

This gives us the relation

Now, recall the usual geometric series

Manipulating this, we have

Thus,

Power terms are easy to integrate, and the integral of a sum is the sum of the integrals. Applying that, the above yields the formula

Or, more clearly,

This is the Leibniz Series for pi. It’s sort of notorious, in that it converges incredibly slowly. It’s rather useless for actually calculating pi, but I find it to be one of the simplest formulae there is. The simplicity, it would seem, comes at a price.

Other trigonometric approaches are considerably more advanced. For example, Euler considered Machin-Like relations such as the following (which he apparently gave without proof).

To use this for computation, you use an expansion of ArcTan like I just demonstrated, except evaluating it at 1/2 and 1/3.

Notice that the denominators of the terms in these two formulae grow much faster than in the previous formula. Thus, convergence is much faster. Those two series, combined with Euler’s relation, give a much more efficient means for calculating pi. Euler goes on to derive far more impressive formulae for pi which I will not share here, but the techniques are all related.

You can see from the form of the series for ArcTan that the smaller the argument, the faster it converges. Evaluating it 1/3 converges much faster than evaluating it at 1, because of the exponential growth of the denominator. So it make sense then that better formulae could be achieved by using smaller arguments for ArcTan. At some point in time that I forget, someone I don’t remember calculated some large number of digits of pi using

By approximating one formula from above, and the other formula from below, you can compare the common digits that result, and be sure they are correct. This is a nice way of dealing with the fact that we don’t actually know the value of pi, and thus can’t, in a single approximation by itself, tell how good it is.

Most trigonometric approaches are just variants on the same theme, clever approximations of curious trigonometric relations. Of course, some are more interesting than others. the Wallis Formula for Sin(x) yields the interesting formula pi, a product instead of a sum.

I find things like this formula interesting because, for me at least, pi in the denominator seems positively unnatural. A curious preconception, well tested by the efforts of S. Ramanujan, a noted mathematician who, the story goes, would often erase all the work he did leading up to a result, because he just didn’t have the space to save it. And it is with Ramanujan, we start to leave the well tested waters of geometry and trigonometry to what some people might call deeper maths. This is very exciting to me, because it begins to suggest that pi is something more than the fundamental geometric constant most people consider it to be.

From him, we get the incredibly bizarre formula, based in number theory, that

Please don’t ask for a derivation of that. I have no idea. But it is really very good – each new term adds eight correct digits to the result. That is impressive. I’m impressed. Notice, again with the . Very interesting.

Pi also shows up much more tractably in number theory. consider the following function,

This is the Riemann Zeta function. I don’t want to get into the details of it, but the distribution of prime numbers is related to the location of the zeros of that function. But of interest here is the fact that , for s = 2n, a positive even integer, evaluates to for some constant . For example,

In terms of computing pi, this formula doesn’t really contribute much. Many formula converge much faster. But what’s interesting about the above formula is how it connects to the formula below, tying pi interestingly to prime numbers and factorizations. If represents the k-th prime number (),

Roughly translated, the product on the left is the probability of any two integers being relatively prime. That is to say, given two integers, the probability that they share a factor other than 1 is , or about 0.6079. Pi, out of prime numbers and factorizations. Fascinating. Though I’m sure if I could understand Ramanujan’s formula, I’d find it fascinating as well. As it stands, he just boggles me.

From here, there are several other areas and approaches I could talk about. For example, there are elliptic integrals – a sort of generalization or extension of trigonometric functions, with connections to number theory as well. There are a number of rather inelegant formula for pi using elliptic integral techniques, one of which quadruples the number of correct digits in your approximation with each new iteration, which, I don’t mind saying, is quite impressive.

The last thing I’d like to mention is something near and dear to my heart, the BBP Formula for pi.

As pi formulae go, this is pretty good – you can tell by the factor that the terms go to zero very vast, and thus it converges relatively quickly. But what makes this formula special is that it allows you to calculate the n-th digit of pi, without calculating all the previous digits. You can effectively jump to any digit you like and start calculating there.

This is a very striking property. Unfortunately, it only allows you to calculate digits in base 16, and in all likelihood there is no related base 10 formula. However, what really makes this formula significant in my book is that it was discovered experimentally. The discoverers considered summations of this form

For k = 0, 1, 2, 3, 4, 5, 6, 7. They calculated each summation to several hundred digits of accuracy, and then ran a computer algorithm on the results that discovered a way to combine the calculated values of each summation into a value that closely resembled pi. And, using that same combination on the full series, they were able to show that the above formula converged to pi exactly. The digit extraction property arose due to the form of the summation, and holds for all summations of the same form. But experimental math! I find that very exciting.

And life continues on. So far as I know, the record computations for pi (upwards of 1.24 trillion digits in 2002) are generally done using Machin-esque formulae like the ones discussed, but BBP-esque formulae are used for calculating various digits of pi, such as the quadrillionth, which happened to be a zero. There are clearly far more steps in the history and math behind pi, but in writing something like this, just as in computing the digits of pi, eventually you just have to say it’s time to stop.

Happy Pi Day!

Kempner Sums

I remember reading, some time ago, an article questioning the worth of a mathematical proof in comparison to simply a convincing argument. I have absolutely no recollection what the author’s point was.

But, in the realm of proof and proving things, there are a number of ways of going about proving something to be true. You might, for example, derive a proposition from first principles – simpler statements you take to be true. You might show that if what you’re trying to prove isn’t true, it must follow that something ridiculous, and therefore wrong, must occur. You might reduce a problem to something previously solved or something else previously proved. To prove something exists, you might construct such a thing, or show how to find it – the constructive approach. In my opinion, the best kinds of proofs are constructive proofs, and very very clever proofs.

I prefer constructive proofs because, for the most part, they directly demonstrate properties of the desired object or proposition and it gives you a more intuitive feel for how or why something works. I saw a proof once of the Hoffman-Singleton Theorem, that was really quite slick. The details are irrelevant, but it basically proved that several types of graphs could exist, by turning the problem into a problem in matrix theory. But it didn’t construct a graph-theoretic reason as to why these graphs could exist. Even though it proved they could exist, the proof itself contributed nothing to actually finding the graphs or understanding their properties beyond that their potential existence. The proof was incredibly clever – one of my favorites, but you come out of it with little more understanding than what you went in with.

Of course, all this is irrelevant for this post – I don’t actually have a proof to offer, but the idea of a proof that explains the how and why of something is very important.

Consider the harmonic series, the sum of the reciprocals of the natural numbers.

As you take the limit of the sum, as n goes to infinity, the sum diverges, increasing at basically ln(n).

But here is an interesting exercise. Take the sum, and remove all terms that include a 1 in the denominator.

That sum actually converges as you take the limit. I’ve always found this very surprising, but it can be proved that the sum converges.

Consider this. Take all the terms with n-many digits in the denominator. Of these terms, the values in the denominator must all be greater than . This means that each of those terms must be strictly less than . The next question is, how many such terms are there? Each denominator is an n-digit number. For the highest place, we have 8 choices for that digit – it cannot be 1, since we exclude 1, and it cannot be 0, since we’re dealing with n-digit numbers. For all other places, we have 9 of the 10 possible digits to choose from. This gives, in total, such numbers. This means that the sum of all the terms with n digits in the denominator is strictly less than . If we break the total sum into groups of n-digit denominator terms, we can calculate the entire sum by summing over all the groups. In a short, we construct the bound,

But the bound on the right is easily calculable. It’s a standard geometric series.

Thus we get the bound, , and an increasing sequence bound from above must converge. Therefore this curious summation must converge, and it must converge to something less than 80!

I find this fascinating. I think it’s because the condition, dropping all numbers with the digit 1, seems almost ‘unmathematical’.

So, it’s an interesting proof of an interesting property – but it troubles me. Even though it proves conclusively that the summation converges, it doesn’t really explain ‘why’ it converges. Why does dropping those terms sufficiently reduce the summation to allow it to converge? What was it about those terms, the ones that contain the digit 1, that made H diverge that K lacks? Is it the size of the terms? The distribution? The proof sheds no immediate light on this.

And I don’t really have a proof that does. But I find the following very interesting. Consider the question, how many natural numbers contain the digit 1? Of course it’s nonsense phrased like that, there are infinitely many, but consider all numbers from 1 to n many digits. We can represent each number as a string of n-characters. 00003, representing 3 in the set of 5 digit numbers. How many such numbers at there? Clearly, , 10 choices for each of n places. But, of those numbers, how many do not contain the digit 1? Same calculation, except now with 9 choices for each place – .

This means that, considering all numbers less than , do not contain the digit 1. Thus, as n goes to infinity, the fraction of numbers below that do not contain 1 goes to zero. And in turn, the fraction that do contain the digit 1 goes to 100%. In effect, by throwing away all the denominators that contain the digit 1, you are leaving a vanishingly small fraction of the original number of terms. You’re throwing away, in the limit, effectively all of the terms. Given that, it begins to make sense to me why the summation K converges the way it does.

It isn’t a proof, certainly, but I think it does point suggestively and waggle its eyebrows.

Another interesting problem to consider is how best to calculate the sum. The proof I give bounds K by 80, but in fact it is much closer to 16. And given the roughly harmonic nature of the summation, it converges very slowly. So how best to calculate K to a high degree of accuracy? I don’t know … but someone does.