Foxmaths! 2.0

July 11, 2009

Open to Interpretation

Filed under: Maths — Fox @ 5:32 pm

This is a more open ended thing. I’m trying to cram and finish a presentation in these last couple of days, so I don’t have much time for my own maths. But, looking at this picture, lifted from Mathworld,

PolygonCircumscribing_1000

What are some questions that immediately spring to mind? One in particular springs out at me.

Increasingly, I find that being able to ask interesting questions is as important a skill, if not more so, than being able to answer them.

So, interesting math questions – go.

July 6, 2009

Questionable Integration: An Interesting Calculation

Filed under: Maths — Fox @ 6:06 pm

As I was walking home from lunch today, burdened by thoughts of simulated annealing, and cross-entropy minimization, I happened to look down as I was crossing a bridge. And on the road below, a pair of boys, side by side, in matching uniforms and backpacks, looked to be walking toward school. But, right as I looked, a telephone pole stood right between us, blocking my few of the inner half of each boy – it looked like one boy, stretched to the point of absurdity. And yet still realistic. Then the moment passed.

I love moments like that. Tiny, fleeting things. Seeing the world, slightly skewed. I remember one time, riding my bike, coming up behind a bird sitting in the middle of the road. The bird took off, flying away from me. But, for a moment, my eyes fixed on his tail, and I imagine we hit the exact same velocity for that one second. It was like the entire world blurred away, leaving me and the bird moving as one. And then it was over.

And that has absolutely nothing to do with what I’d like to talk about today.

Consider the function frac(x). frac removes the integer part of x, leaving the fractional part. So frac(5.25) = 0.25. Of course, frac(0.25) = 0.25, as well. frac(pi) = pi – 3, giving the fractional part by just subtracting off the integer part. Clearly, frac(n) = 0, for any integer n. This becomes important.

For x from 0 to 10 looks like this,

FracX

The problem today is to evaluate the following integral.

F = \int_{0}^{1} frac(\frac{1}{x}) dx

I love naming constants F. F, for fox. There is supposedly a physicist who, in all his papers, names all his constants variations on ‘k’.

frac(1/x) looks like the following.

Frac1OverX

As x gets bigger, 1/x goes from one integer to the next faster and faster – hence the faster transitions in frac(1/x) seen as x goes to 0. But, can we calculate the area under these multitudinous curves? And is it anything nice at all?

And the answer is, interestingly – yes. The first step is to divide the curve up into more managable parts.

Just as with frac(x), there is a discontinuity every time 1/x is an integer – these discontinuities define each of the individual curves in the graph. We can thus break the integral around these discontinuities. Integrating for when 1/x is between 1 and 2, between 2 and 3, 3 and 4, etc. In each of these intervals, frac(1/x) is a continuous curve.

In terms of x then, this breaks the integral into the intervals 1/2 to 1, 1/3 to 1/2, 1/4 to 1/3, etc.

Thus, the first transformation of the integral is this.

\int_{0}^{1} frac(\frac{1}{x}) dx = \sum_{n = 1}^\infty \int_{\frac{1}{n+1}}^{ \frac{1}{n} } frac(\frac{1}{x}) dx

So, let’s consider just the integral over one of the intervals.

\int_{\frac{1}{n+1}}^{ \frac{1}{n} } frac(\frac{1}{x}) dx

What is frac(1/x) over one of these intervals? If int(x) is the integer part of a number, int(pi) = 3, for example, we have the relation that x = int(x) + frac(x). Or, in this case, 1/x = int(1/x) + frac(1/x). Over one of these intervals, 1/x goes from n to n+1, but the integer part of 1/x is simply n. We conveniently can ignore what happens exactly at the endpoints. This gives us, using the previous relation, 1/x = n + frac(1/x), or frac(1/x) = 1/x – n, which we can immediately put to good use.

\int_{\frac{1}{n+1}}^{ \frac{1}{n} } (\frac{1}{x} - n) dx = ln(n+1) - ln(n) - \frac{1}{n+1}

So we get,

F = \sum_{n = 1}^\infty ( ln(n+1) - ln(n) - \frac{1}{n+1} )

This by itself is relatively nice, but we can do better. Consider the partial summation,

F_N = \sum_{n = 1}^{N-1} ( ln(n+1) - ln(n) - \frac{1}{n+1} )

We can then calculate F as the limit of FN, letting N go to infinity. But, expressing the partial sum, we can rearrange it in a nice way, noting the presence of a telescoping sum, and grouping the sums of reciprocals, in a nice way.

F_N = ln(N)  - \sum_{n=2}^{N} \frac{1}{n}

F_N = 1 + ln(N)  - \sum_{n=1}^{N} \frac{1}{n}

Note the addition of the 1+, to make the harmonic sum complete from 1 to N. Thus, jumping back to F, we have,

F = lim_{N \rightarrow \infty} F_N

F = 1 + lim_{N \rightarrow \infty} ( ln(N) - \sum_{n=1}^N \frac{1}{n} )

And … that’s pretty much all you can do. Except for one more very nice thing. As N goes to infinity, ln(N) and the harmonic sum to N become very close, their difference approaching a constant. This constant was first noticed, and given a name, a very long time ago – the Euler-Mascheroni Constant. I find it fascinating that ln(n) and the harmonic sum grow almost equivalently like that, and that constant has long been of interest to me, because I can never find a satisfying way of calculating it. But, this gives us

\gamma = lim_{N \rightarrow \infty} \sum_{n=1}^N \frac{1}{n} - ln(N) \approx 0.577215664...

And this lets us bring everything together nicely,

F = \int_{0}^{1} frac(\frac{1}{x}) dx = 1 - \gamma

An interesting calculation.

And now, I must study.

July 5, 2009

Real Number Picking: An Interesting Calculation

Filed under: Maths — Fox @ 6:30 am

Let x be a random real number, uniformly distributed between 0 and 1. For sanity’s sake, and since it does not effect the calculations, we’ll say that x is never 0.

x defined as such, it has a very nice property. Given two numbers a and b in the interval (0,1], assuming that a is less than b, the probability that a < x < b is given by P(a < x < b) = b – a. For example, the probability that x is less than 0.5 is clearly 0.5, since half the interval is less than 0.5 – but also because P(0 < x < 1/2) = 1/2 – 0 = 1/2. This is me trying to explain probability theory, without explaining probability theory.

Given such a random number x, let [1/x] be 1/x rounded to the nearest integer. Now, the question is this: What is the probability that [1/x] is even?

To calculate the probability of something, we first have to break it down into a convenient set of events. If [1/x] is even, then one of the following must happen: It must equal 0, or 2, or 4, or … any even integer.

P = P( [\frac{1}{x}] = 0 ) + P( [\frac{1}{x}] = 2 ) + ... =  \sum_{n = 0}^\infty P( [\frac{1}{x}] = 2*n )

So, let’s analyze those terms. First, it’s interesting to note that on x in (0,1], 1/x minimizes at 1. Thus, 1/x can never be rounded to 0. We’ve simplified our computation, at the very least by a single term.

P = \sum_{n = 1}^\infty P( [\frac{1}{x}] = 2*n )

Second, what does it take for [1/x] = 2*n? 1/x must be within a half of 2*n, on either side. In other words, an equivalent event is 2*n – 1/2 < 1/x < 2*n + 1/2. If 1/x is in that range, it will be rounded to 2*n.

P = \sum_{n = 1}^\infty P( 2*n - \frac{1}{2} < \frac{1}{x} < 2*n + \frac{1}{2} )

Taking the inequality and inverting it, we can re-express it in terms of x by itself – convenient, given our previous discussion of inequalities involving x.

P = \sum_{n = 1}^\infty P( \frac{1}{2*n - \frac{1}{2}} > x > \frac{1}{2*n + \frac{1}{2}} )

We can now use the stated formula for P(a < x < b) on this interval!

P = \sum_{n = 1}^\infty \frac{1}{2*n - \frac{1}{2}} - \frac{1}{2*n + \frac{1}{2}} )

And from there, the rest is algebra.

P = \sum_{n = 1}^\infty \frac{2}{4*n - 1} - \frac{2}{4*n + 1} )

P = 2*(\frac{1}{3} - \frac{1}{5} + \frac{1}{7} - \frac{1}{9} + \frac{1}{11} - ...)

I might’ve lied when I said it was simple algebra. The above series of fractions, alternating in sign, and with numerators of the odd numbers, is very close to being the Leibniz, or Gregory, formula for Pi.

1 - \frac{1}{3} + \frac{1}{5} - \frac{1}{7} + ... = \frac{\pi}{4}

Applying that, we can reduce our summation, in a most incredible way,

P = 2*(1 - \frac{\pi}{4})

P = 2 - \frac{\pi}{2}

How about that? Pi showing up, in interesting places, yet again. I invite you to try to explain, heuristically, what that pi is doing here, because it is certainly there, no mistake. A quick experiment on a million random numbers gives an experimental probability of 0.49224. The above calculated value is approximately 0.429204. Very good agreement!

And, an interesting calculation.

July 4, 2009

Fourth of July, and the State of Mathematics

Filed under: Administration, Maths, Personal — Fox @ 10:01 pm

With everything that’s been going on lately, first Farrah Fawcett dying, then Michael Jackson died, then Billy Mays. Then Jeff Goldblum died, then Sarah Palin died. And Michael Jackson is still dead!

I know you must be thinking – Where did he go? Where has that Fox run off to? Where is that fantastic Mr. Fox?

In what is not a non-sequitur, Roald Dahl hosted a TV show in the early 1960’s called Way Out. Sci-Fi, Fantasy, Horror, it was very much in the spirit of The Twilight Zone. I remember it most clearly for the opening sequence, which involved a hand coming up out of a grave and bursting into flames.

Actually, I don’t remember that at all – but I do remember my father describing that to me. Or, at the very least, that’s how I remember him describing it to me. One of those many things he’s said, almost in passing – but it all adds up over time. Building this image of a time, a world. Important things, small things. James Burke. TV shows. People, places. The Wounded Lion statue in Switzerland. So many things.

Important things.

And, I meant to write something about that on Father’s Day, and didn’t. Sorry, DadFox. You are best.

Of course, I’ve been meaning to write so much lately.

Which in turn begs the question – just what is it I -have- been doing?

I’m still in Pittsburgh right now, finishing off some math for the summer. Most notably a course in Calculus of Variations – which is some very interesting and exciting stuff – and a research project/experiment in using Monte Carlo techniques (as well as the Cross-Entropy Method, new exciting stuff) to try and solve ‘hard’ graph theory problems. I will probably write about some of that, soon enough.

But, I would like to get back into the habit of writing. There are so many interesting things that need to be shared and explored.

For instance, consider the following game. Player A and Player B both have a die, and they are rolling them, each with a goal in mind. Player A wants to roll a 1, and then another 1, in order. Player B wants to roll a 1, and then a 2, in that order. They will continue to roll until they get their sequence, 11 and 12 respectively. The winner is whoever gets their sequence first. The question is – who is more likely to win? The obvious answer is that they are equally likely. Various arguments can be made, for example that the probability of rolling a 1 is equal to the probability of rolling a 2. However, since I’m asking the question, you should assume the obvious answer is wrong – and in fact, it is. On average, Player B needs 35 rolls to win, but Player A needs 42. Another reason I like this problem, aside from it being non-obvious, is that the answer is (in part, at least) 42.

One thing I’ve been thinking about a lot lately – and I think is a good starting point to get back into writing about maths – is this: Just what is math? I’ve been ‘doing math’ for an awfully long time, and I’m still not sure I know what it is. I know I’ve gone through phases of knowing, thinking I’ve known … but certainty always fades, leaving the question, “But what do you doooooo?”

At first, math is taught as a tool. Basic arithmetic. Algebra. Calculus. Tools to solve certain kinds of problems. To answer certain kinds of questions. How many sheep to I have? How many sheep do I need? What is the interest on this investment going to be? At this rate of increase, how long until our coastal cities are submerged in water? How much fuel do I need to put a man on the moon?

But, as you continue on – it’s the questions themselves that become important. Asked in slightly different ways, perhaps – what if we want to land on Mars, instead of the moon? What is the square root of negative sheep? Sometimes, the questions come, almost naturally, from the math itself – given a function, is there another function that has the first as a derivative? This leads, naturally, to the entirety of differential equations. Again, more tools to answer more questions. But, the questions continue – even in a branch of math as well studied as differential equations, it’s well known that most interesting differential equations cannot be solved analytically at all. Questions questions questions – always new questions. Bring your differential equation tools to bear on this little gem, which I may discuss sometime. I dare you.

y''(x) = 2*y(x)*e^{y'(x)}, y(0) = 0, y(1) = 1

The questions come faster than our ability to answer them, for the most part. Higher level math seems to be, from what I can tell, developing new ways of thinking about these questions – new tools, and frameworks to phrase them in, to try to get at an answer. But these new tools create more questions still.

After a while, it seems as though what math is isn’t the tools, it isn’t the arithmetic or the formulae, it’s the questions themselves. But, I feel as though it’s a symptom of something larger. The mere act of asking a question is a product of thinking about something in a certain way – expressing it in a certain framework. Processing an object, concept, or idea, in a way that allows the question to be asked.

And that, I think, is the core of mathematics. It’s a way of thinking about the world and processing it. And in my mind, it’s a fundamentally scientific way of thinking. Testing, exploring, and questioning.

A drunken physicist once told me that I wasn’t a scientist – I was a philosopher! Gauss, however, declared math to be the Queen of Sciences. I imagine it’s clear who I agree with.

But, at this point, I have veered so far off track it should be clear – I don’t know what math is. There is something I am very excited about. It’s … it’s thinking, it’s exploring. It’s fundamentally creative, inquisitive, and incredibly human. I identify it with math, but, as I think we can all agree, anyone who declares math to be anyone single thing is probably wrong.

I do not know what math is – but I will continue to do whatever it is I do do, because I have an excellent time doing it.

Next up! When I get a chance, several interesting calculations.

Happy Fourth of July!

May 29, 2009

Significant Maths

Filed under: Maths — Fox @ 3:29 am

We’re interested in numbers. Calculating things. That sort of thing. Here’s a brief bit of something, trying to get back in the habit of writing.

Gelfand’s Question essentially asks interesting thing about the first (leading) digit of numbers of the form dn for d from 2 to 9. Suppose we wanted to calculate the leading digit of 250000000. One way would be to, of course, calculate out the full number, all 15051500 digits of it. But that is inelegant, hardly practical, and not very interesting. Alternately, you could look at the sequence produced by looking at the first digit of powers of 2. It goes something like: 2, 4, 8, 1, 3, 6, 1, 2, 5, 1, 2, 4, 8, 1, 3, 6, 1, 2, 5, 1… There are some immediate patterns. For example, each digit is twice the previous … except when it’s not. And there seem to be groupings of three: (2,4,8), (1,2,5), (1,3,6), … except when they’re not: (1,2,4,8). Interestingly, the occurrences of groups of 3 or 4 is connected to the continued fraction representation of log(2). But … nothing immediately useful presents itself. We could fiddle with number-theoretic ideas for a while. But it is late and my eyes are tired.

More interestingly, consider the log (in base 10), of the number.

log(2^{50000000}) = 50000000*log(2) \approx 15051499.7832...

Writing that as 15051499 + 0.7832…, we can then do the following.

2^{50000000} = 10^{15051499 + 0.7832...}

2^{50000000} = 10^{0.7832...}*10^{15051499}

2^{50000000} \approx 6.07016*10^{15051499}

Now, not exact, certainly, but the calculation is good enough to give us the first few digits, specifically that the first digit is a 6. In general, the fractional part of the log is going to be a number at least 0 and strictly less than 1. Taking 10 raised to that power will always give a number at least 1 and less than 10, yielding the first digit of our desired number, rendering the thing into scientific notation.

But, notice we’ve significantly decreased the amount of work, in comparison to actually calculating out the full number. We merely have to multiply the exponent by log(2), calculated out to sufficiently many digits. And if there’s one thing that we can do efficiently, it’s calculate log(2). Mathematica gives 10000 digits in a fraction of a second, more than enough to calculate what we needed for this calculation!

I like this – it feels like we’re short circuiting the computation, jumping right past the mass of middle digits, and straight to the leading term, carrying and long multiplication be damned!

Next, we look at the last digits of some very, very large numbers. Very large. Bigger than you can imagine. And yet, mathematics lets us discuss and handle such numbers with near ease. I don’t know about you, but I find that fascinating.

May 6, 2009

Erdős Number – Of Sőrts

Filed under: Administration, Personal — Fox @ 3:14 am

Finals are winding down. Graph theory was Monday, Thermal was today – the end of my woes will be PDE on Friday.

But, however badly graph theory might have gone, I did come out of it with something few others have.

Paul Erdős is a peculiar character in the world of Mathematics. Possibly one of the most noted mathematicians of modern times. He did some brilliant and incredible things, that are worthy of several posts each. But he was also one of the most notably prolific mathematicians, writing around 1475 different mathematical articles, with 511 different people. To commemorate such prodigious work, friends created the Erdős number – your distance away from Erdős in terms of publications. People who co-authored a paper -with- Erdős have an Erdős number of 1. People who co-authored papers with them have a number 2. Etc, etc. Most active mathematicians, I read somewhere, have an Erdős number of no more than 8. Anyone who hasn’t published a paper with someone with an Erdős number is then said to have an Erdős number of infinity.

And, while I have yet to publish anything at all, and thus find an Erdős number out of my reach, I do have something almost as good.

Consider.

Paul Erdos, and Various Epsilons

This is Paul Erdős, in 1952, with the children (epsilons) of some colleagues. In his lap is Barbie Benzer, now Barbie Freidin. We therefore give her an Erdős-Lap number of 1.

Therefore, Oleg Pikhurko has an Erdős-Lap number of 2, as he is shown here sitting in Barbie’s lap.

Oleg Pikhurko and Barbie Freidin, Lap-Step 2

Therefore, while I wish it were a more flattering picture, I have an Erdős-Lap number of 3.

Wesley Cowan and Oleg Pikhurko, Lap-Step 3

It is surprisingly difficult to ask your professor if you can sit in his lap.

April 27, 2009

Just Resting….

Filed under: Administration — Fox @ 12:33 am

I’m still here … somewhere. With any luck, the math will resume shortly. Not this week, due to projects and things. Not next week, due to finals and things, but soon enough, and plentifully so. With any luck : )

Something to ponder.

“The key to why things change is the key to everything. How easy is it for knowledge to spread? In the past, the people who made change happen were the people who had that knowledge, whether they were craftsmen or kings. Today, the people who make things change, who have that knowledge, are the scientists and the technologists, who are the true driving force of humanity. And before you say, what about the Beethovens and the Michelangelos, let me suggest something with which you may disagree violently. That, at best, the products of human emotion – art, philosophy, politics, literature – are interpretations of the world that tell you more about the guy who’s talking than the world he’s talking about. Second hand views of the world, made third hand, by your interpretation of them.”
- James Burke

March 17, 2009

An Interesting Picture

Filed under: Physics — Fox @ 3:58 am

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

March 14, 2009

Pi Day

Filed under: Maths — Fox @ 8:20 pm

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

People have always been interested in \pi . 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 2 \pi . 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 \pi . For example, consider the following

ArcTan(1) = \frac{\pi}{4}

ArcTan(0) = 0

\frac{d}{dx} ArcTan(x) = \frac{1}{1+x^2}

This gives us the relation

\int_0^1 \frac{1}{1 + x^2} = \frac{\pi}{4}

Now, recall the usual geometric series

\frac{1}{1 - x} = 1 + x + x^2 + x^3 + ... = \sum_{n = 0}^\infty x^n

Manipulating this, we have

\frac{1}{1 + x^2} = \sum_{n = 0}^\infty (-x^2)^n = \sum_{n = 0}^\infty (-1)^n x^{2n}

Thus,

\int_0^1 \sum_{n = 0}^\infty (-1)^n x^{2n} = \frac{\pi}{4}

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

\frac{\pi}{4} = \sum_{n = 0}^\infty \frac{(-1)^n}{2n + 1}

Or, more clearly,

\frac{\pi}{4} = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ...

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).

\frac{\pi}{4} = ArcTan(1) = ArcTan(1/2) + ArcTan(1/3)

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

ArcTan(1/2) = \frac{1}{2} - \frac{1}{3*2^3} + \frac{1}{5*2^5} - \frac{1}{7*2^7} + ...

ArcTan(1/3) = \frac{1}{3} - \frac{1}{3*3^3} + \frac{1}{5*3^5} - \frac{1}{7*3^7} + ...

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

\frac{\pi}{4} = 12 ArcTan(1/49) + 32 ArcTan(1/57) - 5 ArcTan(1/239) + 12 ArcTan(1/110443)

\frac{\pi}{4} = 44 ArcTan(1/57) + 7 ArcTan(1/239) - 12 ArcTan(1/682) + 24 ArcTan(1/12943)

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.

\frac{2}{\pi} = \prod_{n = 1}^\infty (1 - \frac{1}{(2n)^2})

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

\frac{1}{\pi} = \frac{2 \sqrt{2}}{9801} \sum_{k = 0}^\infty \frac{ (4k)!(1103 + 26390k) }{ (k!)^4*(396)^{4k} }

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 1/\pi . Very interesting.

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

\zeta (s) = \sum_{k = 1}^\infty \frac{1}{k^s}

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 \zeta (s) , for s = 2n, a positive even integer, evaluates to C_n*\pi^{2n} for some constant C_n . For example,

\zeta (2) = 1 + \frac{1}{2^2} + \frac{1}{3^2} + \frac{1}{4^2} + ... = \frac{\pi^2}{6}

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 p_k represents the k-th prime number (p_1 = 2),

\prod_{k = 1}^\infty (1 - \frac{1}{p_k^2} ) = \frac{6}{\pi^2}

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 6/\pi^2 , 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.

\pi = \sum_{n = 0}^\infty (\frac{1}{16})^n ( \frac{4}{8n+1} - \frac{2}{8n+4} - \frac{1}{8n+5} - \frac{1}{8n+6} )

As pi formulae go, this is pretty good – you can tell by the (1/16)^n 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

\sum_{n = 0}^\infty (\frac{1}{16})^n*\frac{1}{8n + k}

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!

March 13, 2009

Kempner Sums

Filed under: Maths — Fox @ 9:42 pm

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.

H = \frac{1}{1} + \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} +\ ...\ + \frac{1}{n} +\ ...

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.

K = \frac{1}{2} + \frac{1}{3} + \frac{1}{4} + \frac{1}{5} + \frac{1}{6} + \frac{1}{7} + \frac{1}{8} + \frac{1}{9} + \frac{1}{22} + \frac{1}{23} +\ ...

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 10^{n-1} . This means that each of those terms must be strictly less than 1/10^{n-1} . 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, 8*9^{n-1} such numbers. This means that the sum of all the terms with n digits in the denominator is strictly less than 8*9^{n-1}/10^{n-1} . 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,

K < \sum_{n = 1}^\infty \frac{ 8*9^{n-1} }{ 10^{n-1} }

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

\sum_{n = 1}^\infty \frac{ 8*9^{n-1} }{ 10^{n-1} }

8 \sum_{n = 1}^\infty (\frac{ 9 }{ 10 })^{n-1}

8 \sum_{n = 0}^\infty 0.9^n

8* \frac{1}{1 - 0.9}

80

Thus we get the bound, K < 80 , 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^n , 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 – 9^n .

This means that, considering all numbers less than 10^n , 9^n/10^n = (9/10)^n do not contain the digit 1. Thus, as n goes to infinity, the fraction of numbers below 10^n 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.

Older Posts »

Blog at WordPress.com.