Vacation Vacation

I’m taking a vacation from my vacation … going to Alaska for a week or so! No maths until I get back, and hopefully some new maths then. Feel free to leave any interesting math problems. Or, perhaps, where you would go and what you would do if you could travel through time and space. I’ll see you all on the other side! With pictures.

Many Integrations By Parts

In the spirit of the previous post, one thing that you do in calculus of variations – a lot – is integration by parts. It’s incredible how useful that one trick is. See, they teach you these things in calculus for a reason!

But, I was fiddling around yesterday, and got this nice result, applying many integrations by parts. For integers n, m,

Which I thought was kind of nice.

Calculus of Variations and the Italian Challenge

One thing I did this summer was a course on the so called ‘Calculus of Variations’. A good example question would go something like this.

Consider the set of all functions y, continuous with continuous derivatives, such that y(0) = 0, and y(1) = 1. Find the function y that minimizes the value of

J is called a functional, taking a function and returning a real number.

Taking, for example, y(x) = x (notice that it satisfies the smoothness requirements, and the boundary conditions), the above integral comes out to 4/3. So we know that the minimum value of the integral is, at most, 4/3.

Suppose you thought that the minimzing function were a quadratic polynomial, . The smoothness conditions are necessarily satisfied. For y(0) = 0, that requires c = 0. y(1) = a + b, so y(1) = 1 requires b = 1 – a. So we’re looking for a function of the form . If you evaluate the integral for that function, you get

If you minimize the above expression with respect to a, you find that the minimum value occurs when a = 5/22, and that J(y) = 347/264, or approximately 1.314, ever so slightly less than 4/3. So,

performs slightly better than y(x) = x … but that isn’t enough to show it’s an absolute minimizer.

You could continue on in this way, checking other functions but – let’s be honest. You’re really shooting blindly, because you don’t know the form of the function. Expanding out polynomial minimizers, it may lead you to the taylor expansion of the actual minimizer, but it would be messy and unsatisfying.

Using techniques in the Calculus of Variations, you can solve the problem with some degree of elegance. Elegance that I won’t put forth in detail here – I really just meant for this to be a brief introduction. But you can turn such a minimization problem into an associated differential equation problem. The nice thing about this is that, in comparison to these beasts, differential equations are relatively well understood. The associated problem is as follows. If y(x) minimizes J(y), then y(x) must satisfy this differential eqation problem, with boundary conditions y(0) = 0, y(1) = 1,

You can solve that using your favorite technique to yield the function,

Evaluating J(y), this yields

And this, you can show, is the absolute minimizer of J. Notice, interestingly, the quadratic solution was actually quite close to being the real minimizer. Neat!

Now, you can do all kinds of nice things with this. For example, describing shapes with functions, you can find the shape a hanging cable of fixed length assumes. You can find the curve that minimizes the amount of time it takes to slide a bead along a wire of that curve (the assumption here is, sliding under gravity). And suppose you were an ancient African queen, promised howevermuch land you could encompass with a bull hide, you might be interested in maximizing the total area you could encompass with a fixed amount of material. Many many things.

Of course, Mathematicians always have to go and take things to the next level, which brings me to the Italian Challenge. Now, as the story was presented to me, in Italy, they have these tests for professorships at universities. However, if the administration has a particular candidate in mind, they’ll tailor the test for their strengths. Some candidate must’ve been an expert at calculus of variations, because we have the following problem.

Consider the set of functions, continuous with a continuous first derivative, over the range of x from 0 to 1. We also have the restriction that y(0) = 0, and y(1) = 1. Given

Prove that J(y) has no minimizer of that set of functions.

I’m fascinated. In essence, given any function y(x), you can always find a function w(x) such that J(y) is greater than J(w).

This is interesting on a number of levels. Notice, for instance, that each term of the integrand is positive. Thus we know that, for any function y(x), J(y) is strictly greater than 0. So the values of J are bound from below, but have no minimum! Very interesting.

The associated differential equation problem goes as follows. If y(x) minimizes J(y), y(x) must satisfy y(0) = 0, y(1) = 1, and

Notice, interestingly, you’re not guaranteed that y”(x) exists or is continuous.

But, if J(y) has no mimimizer, and we know that if y(x) minimizes J(y) it satisfies that differential equation, there must be something wrong with that differential equation. It can’t have a solution – because then J(y) has a minimizer. But why?

I don’t know…

A Nice Substitution

I wasn’t always a math person. I used to be much more into reading books. I would read just about anything. Fast, too. But then … I stopped. I remember, the first book I bought but distinctly didn’t read was P.D. James’ Death of an Expert Witness. I picked it up again yesterday, years after the fact, and so far … it’s not bad. Maybe I will get into this ‘reading’ thing again.

But, a small calculation is in order, one that has been bothering me.

Consider the function,

An infinite power tower of x’s. I’ve done some things with this function before, but not this, I believe.

It is certainly questionable, what such a power tower actually means. For the purpose of this calculation, we imagine taking a number x, then raising x to that power, then raising x to the resulting power, then raising x again, etc. This creates a sequence of finite power towers, and we define f(x) to be the limit of that sequence, as the height of the tower goes to infinity.

For some values of x, clearly this sequence diverges to infinity. 2 to the 2nd, etc, etc, etc, rapidly becomes unmanagable. 2^2^2^2^2 has 19729 digits. f(x) for values such as these can be taken as infinite.

But! Over some x, f(x) is actually well defined, finite, seemingly smooth, and many other nice things as well. Consider f(1), which equals 1. f(0) is another matter all together…

That being so, what is the maximal x for which f(x) is finite, and what is f(x) at that point?

My thinking went something like this: I have no idea. But it might be kind of cool to calculate the derivative of f(x).

Looking at the definition of f(x), there’s one substitution that’s just itching to be made.

If we have an infinite power tower of x’s, and drop one off (the bottom most), we still have an infinite power tower of x’s, and the substitution can be made. The rest is standard implicit differentiation.

While the above isn’t really a nice looking function, it’s certainly much more reasonable that having infinitely tall towers flopping about.

And it does suggest something interesting. Notice, being a rational function, if the denominator goes to zero, f’(x) is going to explode to infinity. If that happens, f(x) is going to, effectively, explode as well.

At the very least, if the denominator goes to zero … it would be bad. This all suggests it might have some bearing on our problem. Letting the denominator go to zero, we can solve for f(x) at that point as

This, along with our initial definition of f(x), gives us something to work with.

So, at the above x value, the derivative blows up, and the function goes to infinity. Interestingly, our condition on the denominator of f’(x) also gives us an easy way of calculating f(x) at that point.

And, fiddling with Mathematica seems to confirm all this.

But … what’s bothering me is that I feel like I did too much work. The first time I saw this problem, this quiet little Asian kid whipped out the e^(1/e) like it was a trivial and self evident result. Was he seeing something that I’m not seeing? I don’t know…

I think it’s worth thinking about, in any case. Not too long, perhaps, but worth thinking about. And now, back to murder and mayhem. After all, isn’t that what summer is all about?

Open to Interpretation

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,

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.

Questionable Integration: An Interesting Calculation

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,

The problem today is to evaluate the following integral.

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.

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.

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

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.

So we get,

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

We can then calculate F as the limit of F_N, 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.

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

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

And this lets us bring everything together nicely,

An interesting calculation.

And now, I must study.

Real Number Picking: An Interesting Calculation

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.

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.

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.

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.

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

And from there, the rest is algebra.

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.

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

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.

Fourth of July, and the State of Mathematics

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.

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!