Goodbye Blogger ...

So, as you may or may not have noticed, I've shifted pretty much exclusively over to wordpress. So if you haven't updated bookmarks/links do so. And come on over. I've got some good stuff, I think.

It's been real, it's been fun. Sometimes it's even been real fun. So here's to bigger and better things in the future.

Into the Future

A change is in the air. I'm considering shifting my base of operations to here. I haven't really decided anything yet, and it's all experimental right now to see how I like it. I'm probably going to be posting things here and there as I see how I like it.

Nothing We Haven't Missed Before...

Tyler darted and tagged me, so here we go.

1. Will you be looking for a new job?

I have a job. And that job is to be awesome. I do it well - I do it very well. I see no need to change.

2. Will you be looking for a new relationship?

... Possibly the worst question anyone's asked me in a while. It's like asking Doc Holliday if he wants to be shot in the face.

3. New house?

Unlikely.

4. What will you do differently in 08?

Going by past experience, precious little. What I would like to do differently ... is probably best answered in question 5.

5. New Years resolution?

Be more organized. Do more math. Be more silly. Further obfuscate my true motives and desires. Confuse and confound my enemies. Stay out of trouble. Steal fewer TVs (long story). Do more math : ) Watch some Doctor Who.

6. What will you not be doing in 08?

Most of the things I listed in answer to #5.

7. Any trips planned?

Back to school, soon enough.

8. Wedding plans?

Unlikely.

9. Major thing on your calendar?

Start of classes for the spring term ... My life does tend to revolve around such things.

10. What can’t you wait for?

Nothing I won't have to wait for anyway.

11. What would you like to see happen differently?

Most of all, I'd like to be less busy and do more recreational math. Spend time with more people I like, suffer through less time with people I don't.

12. What about yourself will you be changing?

As little as possible. Got myself into enough trouble last time I tried that.

13. What happened in 07 that you didn’t think would ever happen?

Things many years in the making.

14. Will you be nicer to the people you care about?

Certainly not. Who do you think I am?

15. Will you dress differently this year than you did in 07?

See #12.

16. Will you start or quit drinking?

Sometimes, I am rather tempted.

17. Will you better your relationship with your family?

As if such a thing were possible.

18. Will you do charity work?

Had I but world and time enough.

19. Will you go to bars?

See #18.

20. Will you be nice to people you don’t know?

Certainly, right up until I do know them, at which point #14 and #16 kick in.

21. Do you expect 08 to be a good year for you?

Never.

22. How much did you change from this time last year till now?

More than I'd ever let on.

23. Do you plan on having a child?

Yes. And I'm going to name her Bombshell. Bombshell Fox. If ever there was someone born to be a superhero, it will be her.

24. Will you still be friends with the same people you are friends with now?

Our relationship will certainly be more like it is then, than it ever will have been prior to that.

25. Major lifestyle changes?

I'm going to give up maths and sciences, moving instead into the humanities with a focus in philosophy and theology. I'm also going to lie less.

26. Will you be moving?

Into the future!

27. What will you make sure doesn’t happen in 08 that happened in 07?

Nothing good, I can tell you that right now.

28. What are your New Years Eve plans?

To hurtle onward, ever onward, falling through space and time at millions of miles an hour, gone in all but a blink. As usual.

29. Will you have someone to kiss at midnight?

Less a matter of means, more a matter of execution.

30. One wish for 08?

I wish you nutters everything wonderful.

Well, Foxy. That's just maddeningly unhelpful.

I tag anyone who reads this.

Merry Christmas : )

Happy Christmas

The title about says it all. All my many and varied readers, I wish you all well this holiday season.

And most especially, to you.

Pascal's Triangle: An Update!

So, in the previous post, I discussed Pascal's Triangle, and specifically how many digits it takes to write out a given row in the triangle. If DL(n) is the number of digits it takes (not counting spaces and things), it has an explicit formula as



However, that is an extremely problematic function. Floors? Logs? It gets ridiculous. So it becomes necessary to determine useful bounds to approximate the function with. In the previous post, I was able to determine the following lower bound, that



And I just discovered that Mathematica has a LaTeX copy function : ) That is quite handy.

Now, that lower bound was actually determined relatively carefully, while the upper bound I determined basically by making stuff up.

However, using the same approach to the upper bound I used on the lower bound, you work out the following, that



Plotting the two bounds, they look quite pretty.



Looking at that graph, two things are relatively clear. One, the plot of DL(n) in the middle demonstrates that the function would be relatively difficult to calculate explicitly, jumping and bumping about like that. Two though, it's interesting the extent to which DL(n) seems pegged relatively right in the middle of the two bounds. Looking at a plot of DL(n) and the average of the two bounds, it becomes even more interesting.



Just looking at that plot, it's clear that the average of the two bounds is a REALLY good approximation of the function itself. That plot goes out n = 40. Going out to n = 300, it's practically impossible to tell the two functions apart.



And, even better, if we call this function J(n), it has a really nice form!



Given how nasty DL(n) is by itself, J(n) is indeed -quite- nice.

And here's a plot of the error, J(n) - DL(n),

Which is all kinds of interesting. It grows exceptionally slowly. The error for the 300th line is only 60 or so digits, which is quite impressive considering that DL(300) = 19329. Notice too, that it seems exceptionally linear, and also seems to have some kind of embedded periodic activity.

Very very interesting.

Pascal's Triangle and Interesting Questions

This is likely to be a long post, touching on a couple of interesting topics and coming to head in an interesting result. Hopefully : ) Warning - past a certain point, it's going to get kind of intense.

So, there's this thing called Pascal's Triangle. It looks something like

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
...

The rows are numbered starting at 0 and going down, and the elements of each row are numbered starting at 0 and going across. The nth row has n + 1 elements.

Just straight up, the most obvious pattern is the method of construction. Each number is the sum of the two numbers above it.

There is an actual formula to it, namely that the kth number of the nth row is given by




Now, this thing has a lot of nice properties to it. Pascal actually came up with it in reference to probability. The idea is, given a coin and flipping it, say 3 times, there is (1) way of getting 3 heads, (3) ways of getting 2 heads and a tail, (3) ways of getting a head and 2 tails, and (1) way of getting 3 tails. 1 - 3 - 3 - 1. The other rows give similar results all down the rows. Notice that flipping a coin three times, there are 2³ many ways it can happen. 1 + 3 + 3 + 1 = 8. In general, the sum across the nth row is 2ⁿ.

Now, the question we would like to address is how /long/ is a given row of Pascal's triangle. Clearly a given row has n + 1 many elements, but what I'm interested in is, if you were to write out the nth row, literally how many characters would it take. The reason this is interesting to me, at the very least, is that I've always found it incredibly difficult to write out Pascal's triangle, because the length of the rows grows so fast it's difficult to keep the spacing nice and orderly and triangle like.

Look, for example, at the first 16 rows.

1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1
1 6 15 20 15 6 1
1 7 21 35 35 21 7 1
1 8 28 56 70 56 28 8 1
1 9 36 84 126 126 84 36 9 1
1 10 45 120 210 252 210 120 45 10 1
1 11 55 165 330 462 462 330 165 55 11 1
1 12 66 220 495 792 924 792 495 220 66 12 1
1 13 78 286 715 1287 1716 1716 1287 715 286 78 13 1
1 14 91 364 1001 2002 3003 3432 3003 2002 1001 364 91 14 1
1 15 105 455 1365 3003 5005 6435 6435 5005 3003 1365 455 105 15 1
1 16 120 560 1820 4368 8008 11440 12870 11440 8008 4368 1820 560 120 16 1

Look how fast that grows. That's quite fast.

The question is then, exactly how fast.

But how to calculate the length of a row? We have the formula for each element of the row. If we can calculate the length of an element, and sum across the elements of the row and that gives the total length of the row.

But what is the length of the number? In general, the number of digits it takes to write a number n is Floor[log₁₀(n)] + 1, where Floor[x] rounds x down to the nearest integer. A few examples.

Floor[log₁₀(13)] + 1 = Floor[1.1139] + 1 = 1 + 1 = 2

Floor[log₁₀(10000)] + 1 = Floor[4] + 1 = 4 + 1 = 5

Floor[log₁₀(999)] + = Floor[2.99957] + 1 = 2 + 1 = 3

log₁₀x gives you the exponent on 10 needed to calculate x. By rounding it down, you're effectively calculating the exponent on 10 needed to calculate the largest power of 10 smaller than x. (13 gives you 10, 10000 gives you 10000, and 999 gives you 100). And the number of digits in 10ⁿ is n + 1.

So then, using the formula for the k'th element of the n'th row, the number of characters (excluding spaces) needed to write out that row is



However, that is a very uncomfortable looking function. It's going to be very hard to get that in terms of anything sensible, due to all the rounding that must occur, and the inanities involved with taking the log base 10 of things. A closed form expression for that summation is almost out of the question. However, we can still get some good approximations on it, which will tell us how fast the function grows with n.

Now, with a really cool exercise, you can show that the function grows with order less than or equal to n². What this means is that whatever the function actually turns out to be, for large n, the function behaves like, or less than, a*n²ⁿ. We know this to be true, since the sum of all the elements of the row is 2ⁿ. As there are n + 1 many elements in the row then, the number of digits it takes to write out the whole row is less than the number of digits it takes to write out 2ⁿ, n + 1 many times. So we can do the following. Notice that, for any x, Floor[x] is less than or equal to x.



Bounding that bound,



And simplifying,







We get the final result, bounding the function in question by a quadratic



From that now, we know that the function is bound from above by a quadratic function of n, since is a constant. So we know that, whatever the exact form of the summation is, it grows with order of less than or equal to n² Which is very interesting.

But, the actual growth rate of the function could still be something silly like n*log(n), or n^1.5, both of which of are order less than n². How can we figure it out precisely?

Unfortunately I haven't found an equally cool trick to bounding it from below. So what we must do is return to the definition of the function itself, and play with it as best we can.

Notice, due to the definition of Floor, we have the following inequality.



Making use of this, we can bound the summation as follows



Just looking at that, it's clear that getting a grip on



Would be pretty useful. Note that, following the rules of summations and logarithms, we can do the following.





So, all we really need to think about is



Which is convenient for me, since I don't want to write out all those 10's. This next part takes some finagling, but it comes out very nicely.

Now, following the rules of logarithms, log(a) + log(b) = log(a*b). Applying that to the summation above, we get that the sum of the logarithms equals the logarithm of the products of the terms.



But, expanding out that product, it has a rather nice form.





Then, using the rules of logarithms again, like log(a/b) = log(a) - log(b), and log(aⁿ) = n*log(a), we can simplify that further...





It becomes convenient to note though, that 0! = 1, and can hence be dropped to give



Now :) The expression 1!2!3!....n! is actually very interesting. Because it can be factored very nicely. Remember that j! = 1*2*3*...*j. So, writing out the product...

1!2!3!....n! = (1)*(1*2)*(1*2*3)*...*(1*2*3*...*(n-1)*n)

1!2!3!....n! = 1ⁿ*2^n-1*3^n-2*...*n¹


In general, what you get is that



Substituting that in, we now have



Then, using logarithms again, we can use the substitutions





And it becomes...



Which we can simplify, grouping the summations, to a rather neat



To summarize then, plugging that back in as above, what we've established is that



This lower bound is really nice because it looks exceedingly well behaved. We have no factorials to deal with, no crazy functions defined in terms of god knows what ... it seems relatively normal.

But it is still difficult to calculate, and doesn't give us a good, usable bound on the function we're looking for. So what we're going to do is approximate the summation by integrals.

At this point, I've been writing out the mechanics of the work pretty explicitly, because I thought that it involved a couple of neat mechanizations and substitutions. It really gets rather dry from here on, so I'm going to gloss over the worst of the details.

So, we want to approximate the sum by integrals. This is quite reasonable. Indeed, integrals were originally approximated by sums, and we're just doing the reverse, since things can be nicer to integrate than to sum explicitly.

First, we break the function up like so,



We want to approximate the summation from below, so as to produce a lower bound on our lower bound. Through a judicious use of integration, we have that





Applying these, we have






So, if DL(n) is the length of the nth row (I'm naming this function now because I don't want to have to keep typing out the stupid summation), we've now produced the bounds



Note though that the upper bound was very crudely arrived at, and is no where close to the accuracy of the lower bound. But I'd like to return to a moment to the discussion of order. From the upper bound, we determined that the function DL(n) grew with order of at most n². Looking at the lower bound now, there are a couple of terms to consider. Remember that the order of a function is going to be the term that grows the fastest as n increases. Looking at the terms of the lower bound, the one that stands out first and foremost is n². But there is also this curious n²log(n/(n+1)). What to make of that, though? Note however that as n increases, n/(n+1) becomes very close to 1. As it approaches 1, log(n/(n+1)) actually approaches 0, and that term is effectively canceled. So as n becomes very large, the main contributing term of the lower bound is the n² term. As DL(n) is bound from above and below by functions of order n², DL(n) must be of order n².

So, as you write out more and more of the triangle, the sides are going to grow outwards in roughly parabolic fashion, moreso as you get further and further down.

For fun, here's a plot of the upper and lower bounds, and the actual function.



That's all I've got : ) Anyway, moving on.

Firefly

Simon: Are you always this sentimental?

Mal: Had a good day.

Simon: You had the Alliance on you, criminals and savages... half the people on the ship have been shot or wounded including yourself, and you're harboring known fugitives.

Mal: We're still flying.

Simon: That's not much.

Mal: It's enough.

That kind of day : )

Shhhh.

Finals.

Checklist.

[x] Combinatorics
[x] Math Software
[x] Biology
[x] Physical Analysis
[x] Physics III
[x] Math Studies
[x] Getting the hell out of here

On a side note, blogger hasn't been emailing me about recent comments, so if you've been ignored, speak up :) Guess I'll just have to check on the main page now.

Done here. Headed home. Catch you all on the flipside.

Erdos-Szekeres, and The Mathematical Certainty of Structure

So, a couple of interesting results have come to light over the past week or so, and I'd like to discuss them here.

First off, consider the following 101 random integers, generated using Mathematica, between 0 and 1000 for convenience to me.

{458, 22, 856, 736, 354, 348, 843, 722, 112, 389, 790, 84, 154, 672, 263, 226, 185, 706, 985, 123, 161, 679, 349, 132, 562, 484, 576, 593, 503, 413, 895, 415, 227, 325, 791, 453, 386, 53, 772, 688, 765, 576, 644, 621, 404, 379, 5, 51, 684, 731, 286, 933, 111, 308, 758, 343, 664, 959, 659, 703, 817, 247, 817, 892, 923, 734, 305, 127, 340, 779, 412, 999, 264, 56, 825, 85, 477, 502, 603, 960, 496, 751, 363, 403, 419, 738, 670, 778, 271, 715, 932, 597, 899, 249, 228, 430, 891, 185, 23, 612, 544}

Going through in order, without even looking, I guarantee that there is a subsequence in that sequence of at least length 11 that is monotonic, either each term is greater than or equal to the next, or each term is less than or equal to the next.

Starting with 22, we can pick out, as convenient

{22, 112, 123, 132, 227, 325, 386, 404, 502, 670, 715, 932}

Even better, we managed to get a 12 length sequence.

At this point, you're probably wondering what it all means.

The point is that, repeat the experiment with any such sequence of 101 random numbers, and the result will always be the same. You will /always/ be able to find a monotonic subsequence of length 11. No matter what.

In general, this result is the Erdos-Szekeres Theorem. The idea is that given an arbitrary sequence of integers of length n² + 1, there always exists a monotonic subsequence of length n + 1.

And now, proof. This is kind of technical, so don't feel poorly if you'd like to skip to the end, where I finally make my point. The point is actually independent of the proof, but whatever :)

Proof

To begin with, we have a sequence,

{a₁, a₂, ..., a_n², a_n²+1}


So take each a_i in the sequence, in order. For each, consider the longest monotonic increasing subsequence that starts at a_i. We'll refer to this subsequence as L(a_i). Note that if L(a_i) is of length greater than or equal to n, for any a_i, this gives us a monotonic increasing subsequence of length at least n + 1, and we're done. So we have to assume that L(a_i) is of length less than or equal to n for all i.

This means that each subsequence L(a_i) has a length between 1 and n. Note too, that because each subsequence is different (each starts at a different a_i), there are n² + 1 many subsequences. So imagine sorting the sequences by length. Distributing n² + 1 many sequences over n many lengths, there must be some length such that at least n + 1 many subsequences have that length. We'll call that length t.

A bit of notation. We have a sequence of length n²+1, which we could refer to an arbitrary element of as a_i. Suppose we wanted to refer to a specific subsequence. For example, {a₃, a₅, a₁₂}. A way to think of this more compactly is to refer to the elements of the subsequence as a_k(j), where k(1) = 3, k(2) = 5, k(3) = 12. In general then, I can refer to subsequences of the main sequence as a_k(j), where j goes from 1 to the length of the subsequence.

Consider all the i's such that L(a_i) is of length t. As I said, there are at least n + 1 of these. Consider k(j) such that k(1) is the smallest i, k(2) is the next largest, and so on to k(n+1). a_k(j) is then an a subsequence of the original sequence of length n + 1.

I argue that {a_k(j)} is monotonically decreasing, which is to say that a_k(1) > = a_k(2) >= ... >= a_{k(n + 1)}.

Assume not, that we have k(j) < k(i) such that a_k(j) < a_k(i). We know that L(a_k(j)) and L(a_k(i)) are both of length t. But since L(a_k(j)) is the longest monotonically increasing subsequence starting at position k(j), as a_k(j) < a_k(i), a_k(i) must be included in L(a_k(j)). Further, all of L(a_k(i)) must be included in L(a_k(j)). This gives us then that L(a_k(j)) is actually longer than L(a_k(i)), since L(a_k(j)) includes all of L(a_k(i)), and L(a_k(i)) at the very least cannot include a_k(j). This contradicts the fact that both L sequences are of length t.

Therefore, we have that for all k(j), {a_k(j)} is in fact monotonically decreasing.

Therefore we have a monotonic sequence of length n + 1. And we are done.

So, the point is that Erdos-Szekeres guarantees that, independent of the sequence itself, any n² + 1 length sequence has a monotonic subsequence of length n.

This is is quite exceptional to me. The point of it all is that, within the sea of randomness that is ever possible sequence of a given length, there is a mathematical guarantee of order.

This shows up other places as well. For example, Ramsey theory guarantees that, if you invite 6 people to a party, no matter what people you invite, at least three of them will all know each other or all not know each other. Similarly, in a 49 person party, you are guaranteed a group of five people that all know or all don't know each other.

Islands of guaranteed stability within realms of what can only be described as chaos.

The reason all this interests me is that of late, on several fronts, there has been a question of order. Order in nature and the physical world, for example. Intelligent Design people maintain that order cannot arise from nothing. There's the question of the seeming order of the physical laws of the universe. Where does all this order come from? I don't claim to know the answer, but what this seems to suggest is that in any mathematical system, order might well be unavoidable. Even in a system that is consistently unpredictable, that behavior itself by the fact of it being described, has some degree of order. The Mathematical Certainty of Order.

I don't know if that's valid at all, but it certainly sounds nice.

Discuss.

A Few Things Worth Mentioning

• It seems to be Woody Allen's birthday today. Happy Birthday, Mr. Allen.


• Only one week of classes left, which strikes me as very interesting.


• Two related stories. This Thanksgiving, I'm rushing through the airport, and accidentally bump into a man's suitcase. I turn and say, "I'm terribly sorry." He turns around, sharply, and says, "Well you should be." Rather at a loss, I shrug and reply, "Well ... I am." We each go our separate ways.
  
  Similarly, one of my teachers had an outburst in class, declaring that we had the most attitude of any class he'd ever seen. The man was clearly quite furious, and trying to contain it. Shortly after, when a demonstration he attempted failed, one of the more irritating students in class made a comment, to which this professor replied, "What I need is a polite class." The student apologized, saying he was sorry, to which the professor replied, "Well you should be."
  
  What is it with these people? What do they expect. We've already apologized. Well, you should be sorry! How convenient for everyone that we are, then.
  
  Seriously -.-


• A friend was telling me about this boy she knew, who was considering coming to Carnegie Mellon. After taking some summer courses here though, he bowed out, deciding it was too hard. Now, my question is, what does it say about me, and more importantly what impact does it have on my well being that I tend to view such things as a challenge rather than a deterrent? Nothing good, I imagine. I'm so tired. Can't wait for this semester to be over.


• Varied Comments and Complaints

Some very interesting math stuff coming later this afternoon, if I can get around to it : ) Very good stuff.