Tyler and Foxy's Scientific and Mathematical Adventure Land

Integer Partitionings: 3-Partitions

2008-04-04T18:51:00.003-04:00

This will be, I think, a relatively gentle treatment of what could be a rather complicated matter.

The problem came up in problem seminar this week, the matter of integer partitioning. Specifically, given an integer n, how many different ways can you write it as the sum of smaller integers? More specifically, and a notably easier problem, how many different ways can you write it as the sum of three smaller integers?

For example, 6 can be written as 1 + 4 + 1, 3 + 2 + 1, and 2 + 2 + 2. Notice that we're counting 1 + 4 + 1 as the same as 4 + 1 + 1. 5 can be written as 1 + 1 + 3, 1 + 2 + 2. So the number of 3-partitions for 6 is 3, and the number of 3-partitions for 5 is 2. Clearly 0, 1, and 2 all have no 3-partitions, and 3 has one, 1 + 1 + 1. But for a general n, how many are there?

The basic approach is going to be to come up with a method of constructing all 3-partitions of a given number, and then the formula for the total number falls out almost automatically. What follows then is a reduction from the initially simple to understand but difficult to compute formula to a relatively difficult to understand but surprisingly simple formula. It's interesting.

So, we have an integer n, and we want to construct a 3-partition of it. Constructing a partition basically amounts to choosing 3 integers i, k, j such that i + k + j = n.

Notice though, that we want to, in picking our numbers, avoid duplication. For example, when n = 6, we want to avoid choosing 1, 1, 4 and also 1, 4, 1. To avoid this, we're going to make sure to pick our numbers in sorted order. That is, we're going to make sure that the first number we pick will be the smallest of the three, and that the second number we pick will be at least as big as the first, and that the third is at least as big as the second. We'll call them, in order, i, k, j.

So, how many values can we pick for i, the smallest of the three? Clearly the smallest value we can have for i is 1. But what is the largest? i can be, at most, n/3. Think about it. If i is greater than n/3, then what is left of n to partition between k and j? Something less than n - n/3, or 2n/3. Partitioning 2n/3 between two numbers, one of them is going to have a value less than n/3 - but this contradicts our definition of i as the smallest of the three. Therefore, i is at most n/3.

But, since we're dealing with integers, i is really at most n/3, rounded down to the nearest integer. In math speak, this is the floor of n/3, or . So, for example with n = 5, n/3 is 1 and 2/3rds, which rounds down to 1. Looking back up at the introduction, you'll see that in the two partitions I give for n = 5, the smallest number in each case is 1.

So, we declare a value for i between 1 and . Notice though, that since k and j are at least as big as i, in deciding the value of i, we've 'pre-partitioned' 3*i of the total n. We know that the sum of the partition is going to be at least i + i + i. So really, in choosing k and j, what we're doing is partitioning n - 3*i between k and j, each of which is already at least i.

So, having picked a value for i, and thus set a minimum value of k, how can we partition n - 3*i between k and j such that j is greater than or equal to k? Similar to before, we can add, at most, half the remaining value to be partitioned to k. If we add any more, we'll end up adding less value to j, and k will be greater than j - which violates how we're setting things up. Remembering the fact that k must be an integer though, we can add at most to k. That gives us the upper bound. For the lower, remember that it's perfectly acceptable for i to equal k, but k cannot be less than i, so i is a lower bound for k.

To summarize,

We have that i is between 1 and .
We have that k is between i and i + .

Now what of j?

This is largely a trick question. Remember that we're after i + k + j = n. If we've chosen values for i and k, then j = n - (i + k). There's only one choice for j. And, by the way we've bounded our choices for i and k, it guarantees that j is the largest of the three numbers.

And that's it : ) This gives us a method for constructing all the partitions of n into 3 integers, such that no partition is constructed twice.

Now, as to counting the number of such partitions, it amounts to counting every possible choice of i and k. So, we basically count through every i, and for each i count through every possible k, and sum the number of times we do this Counting amounts to adding 1 a certain number of times. Thus we have our partition counting function,

That's the easy to understand formula, because you can see where every part of it comes from. Now to simplify : ) Notice though that it is difficult to compute, because it basically amounts to running through every possible partition, though in a convenient way, and counting them. If there are 10000000 bajillion partitions, that double sum will take a long time to compute.

Firstly, summing 1 over a given range is just equal to the number of numbers in that range. So we can reduce the double sum to a single sum of the form

Now instead of summing over all possible i and then all possible k, we've reduced it to a sum over all possible i. But we can do better. Notice, for example, that the floor function isn't very ... managable. There's not a lot you can do with it algebraically. But we can replace it with something just as good.

First, think about . If n - 3*i is even, then it is divisible by 2, and floor of half that is an integer, equal to (1/2)(n - 3 i). If n - 3*i is odd, then half that equals an integer plus 1/2. Rounding that down will yield, in effect, (1/2)(n - 3 i) - (1/2).

So, think about that behavior. For even values of n - 3*i, we want a function that returns (1/2)(n - 3 i), and for odd values of n - 3*i, we want one that returns (1/2)(n - 3 i) - (1/2). The only thing that really changes is the subtracting of one half.

So notice that (-1)^m equals 1 for even m, and -1 for odd m. Then 1 - (-1)^m equals 0 for even m, and -2 for odd m. Then, (1/4)(1 - (-1)^m) equals 0 for even m, and -1/2 for odd m.

That being so, we can rewrite our floor function as

We can then reform our summation as

The rest is just a matter of algebra and series formulae. Expanding everything,

And then I could step through each step of simplifying the sum, but that would be even more tedious than everything I've done so far, so I'll skip straight to the punchline,

And that is awesome. Because we've reduced a function that was a multiple summation to a function that requires a fixed number of compuations, -dramatically- easier to calculate. Plugging in n = 0, 1, and 2, we get P₃ is 0 for each. For n = 3, when = 1, we get

So there is only one partition of n = 3, which we know is true since the only partition is 1 + 1 + 1.

I don't really feel like doing any more examples, since I've gone on well long enough. I think it is very interesting though that the resulting function turned out to be (effectively) quadratic in terms of n. Honestly, I find it interesting the formula reduced half as nicely as it did anyway : )

So that's our final result for the number of ways of partitioning an integer n into three pieces. I've gone on long enough at this point though, and it's time enough for me to get back to work.

Progress on Riemann?

2008-04-01T21:00:00.002-04:00

The Riemann Hypothesis is one of the greatest unsolved math problems in the world today - probably. If not, it's easily one of the most famous.

It centers on the Riemann Zeta Function, given by

The function being defined over the complex plane. The Hypothesis is, in its most basic form, that if , then s = 1/2 + t*i, for some real number t. That any zero of the zeta function has a real part of one half.

Why this is interesting though is the connection with prime numbers. There's a function called the prime counting function, pi(x), and it basically gives the number of prime numbers between 0 and n. As the distribution of primes is so bizarre, being able to calculate pi(x) correctly, without just counting all the prime numbers from 1 to x, would be a very neat trick. We have some very nice approximations for pi(x), involving integrals of relatively simple functions, but the question is the, how good are these approximations?

So enters the Riemann Hypothesis. Basically, it's been shown that the Riemann Hypothesis, as stated above, is equivalent to saying, for our best approximation of pi(x), pi(x) differs from this approximation by no more than some constant times , for x sufficiently large.

Which is a very interesting result.

But a proof was proposed a few months ago, and it seems really quite promising, and at the very least opens up some new avenues for further inquiry. As usual for such things, I don't have the background to explain fully, but I think I can break down a couple of the key points to an understandable level. Maybe Mark can pick this up? More below the fold.

Read more »

Quantum Computers: Math and Time Travel

2008-03-14T09:54:00.002-04:00

I'm currently half way through my Spring Break, so the math is slow/non-existent. I've got an interesting math problem half written up, but I'm trying to decide if there's a better way to reach my final conclusion. It's still nice to get a break from the insanity, though.

In the mean time, in this months Scientific American, there was an article on the Limits of Quantum Computers. You'll need to register/pay to read the online version, so that's sort of a bum deal. But it's a very interesting read. But it draws together two of my favoritest things, math and time travel. And a big heap of quantum computing to boot.

Without getting into the nitty gritty of complexity theory (I'll leave that to Kurt, I think) there are several classes of math problems, which could best be described as 'hard' and 'easy'. Easy problems are ones for which we have developed highly efficient algorithms for solving, sorting a list of data, for example. For hard problems, however, any algorithm we've developed for solving them runs incredibly inefficiently, quickly needing unmanageable amounts of time or space to arrive at the solution.

In a relatively simplified version of things, suppose a problem's size can be represented by some variable n. For example, n cities you're trying to find a shortest path between, or trying to determine whether or not a number is in a list of size n. For easy problems, the number of steps needed to solve the problem grows proportionate to some polynomial of n, like n². Hard problems, however, the number of steps needed grows exponentially, like 2ⁿ. As n increases, it becomes vastly more resource intensive to solve the hard problems than the easy ones.

The million dollar question, literally, is whether or not 'hard' problems are actually 'easy', but we just haven't found a good way of solving them yet.

The point of the article is that there is a massive hoopla surrounding quantum computation, based on the idea that quantum computers will be able to solve hard problems easily. The best way of describing how they might do such a thing is that, theoretically, quantum computers would be able to check every possible solution to a given problem simultaneously, whereas modern computers currently have to construct solutions, or check possible solutions some small number at a time. So these unfathomably difficult problems could be felled easily, by even simple quantum computers. In theory.

Except, according to the author, the excitement is relatively unfounded.

The main problem is that the constructive and destructive interference of waveforms that represent superimposed solutions in quantum computers are incredibly difficult to handle without interference from outside the computer, never mind the fact that if you actually measure the state of the computer while some number of possible solutions are in superposition, you can only ever measure one solution at a time. Any algorithm for using quantum computers to solve such problems must not only overcome these difficulties, but exploit them in solving the problem.

But aside from the physical difficulties of handling such a machine, there seem to be mathematical issues as well.

We need to abstract. Imagine a completely general problem, with some number of potential solutions, S. Using a usual computer, trying to find the actual solution, in the worst case we would have to check each of the S many solutions. In computer science, we always assume the worst. So that is, we anticipate, S many steps to find the actual solution.

Now, imagine you had a quantum computer. We'll disregard the actual construction and innerworkings of such a computer, but assume that it has the capacity to take a potential solution and verify it. Now, in the optimal case, as described, we could superimpose every single solution of the S many at once in the computer, and verify them all at the same time. Effectively solving the problem in one step. But that makes many assumptions about the structure and nature of the problem and its solutions. In this abstract, general case we are assuming, it has actually been proven that using a quantum computer, the best speedup you can hope for is to solve the problem in S^1/2 many steps. It's the absolute best case scenario. Of course, best case scenario the first solution you check is the correct one and you solve the problem in one step, but again assuming the absolute worst, it's been shown that the worst case number of steps to solve the problem is S^1/2.

As my friend Dan would say, we proved it using math.

Now, going from a worst case of S to a worst case of S^1/2 is a significant speed up, yes. But in these hard problems, as I described, the solution space, S, grows exponentially. As such, S^1/2 also grows exponentially, and again we're in a situation where as the size of the problem grows, it rapidly becomes unmanageable.

Does this show that quantum computers won't be able to solve these hard problems? Not necessarily. At best, what this shows is that any solution to such problems can't be 'general'. A solution algorithm to a given problem will have to be specific to that problem, exploiting its nature in some way that we don't yet understand.

But here's where the article got very interesting.

The author then goes on to describe theoretic computers, above and beyond quantum computers, that might be able to tackle such problems. One in particular that caught my attention approached this problems by manipulating time. In layman's terms, it solved the problem using time travel - possibly my favorite subject. The fellow who conceived of such things devised a computer which, in theory, could solve these 'hard' problems easily through the use of time travel, through what are known as Closed Timelike Curves. Not to be confused with Closed Timely Curves.

Of course, no one knows if such things are physically possible.

Now, this is my favorite part. The question of whether these hard problems are in fact easy basically boils down to a math problem. Can it be proved, one way or the other. However hard it may be, it is a math problem. And if it is proved that these hard problems are -not- easy, any method by which they could be solved easily becomes impossible. As such, given the above discussion, it would serve as a mathematical disproof to the possibility of time travel.

Of course, if it is proven that hard problems are in fact, easy, it wouldn't say a single thing about whether or not time travel is possible. The implication is one way, but still interesting.

Very exciting. Very exciting.

The Carnival of Mathematics: No. 28

2008-03-07T07:46:00.000-05:00

Tyler and Foxy's Scientific and Mathematical Adventure Land is proud to present the 28th. Carnival of Mathematics! According to the treasured tradition of this fine event, I will exposit something interesting about the number 28. Fortunately, I got the perfect number to do so, literally. 28 is a perfect number, such a thing being defined as the sum of its positive divisors that are not equal to the number itself. That is, 28 is the sum of 1, 2, 4, 7 and 14. The next guy who gets to talk about perfect numbers will be the guy who happens to be doing the 496th. Carnival of Mathematics. Good luck, whoever you end up being!

And now, on to the good stuff...

Over at The Universe of Discourse, Mark Dominus provides us with three interesting posts. The first concerns an interesting property in the world of coding theory known as "unique decodability", or whether particular strings are the result of unique encodings. The second is on rational roots of polynomial equations. The third concerns techniques of algebraic manipulation that work...sometimes.

From the website Old-Wizard dot com, we have this list of the top 10 Mathematicians of All Time. In my mind, they get it mostly right. The only serious problem I can see is that Leibniz is nowhere to be found. Seriously, WTF?

My esteemed blogmate Foxy over at Foxmaths 2.0! provides us with this post on an interesting geometric question: can you divide a cube into a finite number of smaller cubes, all of different sizes? The answer is....just kidding, I'm not a spoiler. Go read!

Charles Daney at Science and Reason sends us this post on important concepts in algebraic number theory, in particular concepts from ring theory. The key concept is that of the "Dedekind domain", a specific type of commutative ring in which every nonzero ideal can be uniquely factored into a product of prime ideals.

Over at The Number Warrior, Jason Dyer provides us with this fascinating historical discussion of the ancient Egyptian calculation of pi. It even has tables of Egyptian numeric characters showing the development of the quantity over the years, I think that's pretty damn neat.

Julie Rehmeyer provides us with two posts on Sophie Germain, the first person ever to lay out a realistic plan for rigorously proving Fermat's Last Theorem, one of the peskiest little assertions in the history of number theory.

In the math education and pedagogy category, Mr K. over at Math Stories sends us this entry on how overemphasis on mechanical shortcuts over conceptual understanding harms long term learning in mathematics.

Over at Wild About Math!, we have a probability puzzle, apparently the first in a regular series untitled "Monday Math Madness".

In the aesthetics of mathematics category, we recieve this entry from Art Black, which compares the perception of beauty of mathematics to the perception of beauty of music.

The winner in the terms of sheer volume of material for this edition of the Math Carnival is Blake Stacey, who sends us a series of five posts on supersymmetric quantum mechanics! [1, 2, 3, 4, 5]

And finally, at the Teaching College Math Technology Blog, we recieve this entry from Maria Andersen on software for teaching math courses online.

And that's all, folks! It has been a pleasure to host this event, and I hope I have done so to your satisfaction. Good luck, and godless speed.

Carnival of Mathematics Submission Guidelines

2008-02-19T15:11:00.005-05:00

I'm proud to say that the Carnival of Mathematics is going to hosted here on March 7th. To help potential authors I've decided to provide this set of submission guidlines:

1. The submission deadline is set to 10:00PM EST on March 5, no submissions will be accepted after that. I plan on finalizing the entry selection that night, writing up the carnival on Thursday and posting it on Friday morning, for purposes of work schedule compatibility.

2. Include a brief (2-5 sentence-long) description of what your entry is about. I'm a reasonably math savvy person, but there is no way I'll be able to fully capture the content of all the entries without a bit of assistance. Help a fellow geek out!

3. Send all the entries to my personal email (tylerofmanyminds AT gmail dot com).

Good luck, and godless speed.

Probabilistic Chess Coloring

2008-02-07T07:35:00.000-05:00

Now isn't that an inviting title.

So, the idea is that in general, you have an NxN chessboard, with all white squares, and you're going to go through each square and color it black with a probability p. So ideally, you're left with p*N*N many black squares and (1 - p)*N*N many white squares. Consider the 20x20 board below. I hope this comes out formatted properly.

X__X_XXXX________XX____X_X__XX
_X_____XXX____X_X_XXX___X_X__X
_______X___X_XX_____XXXX_X__X_
X__XX____XXX__X_X__X_____X_X__
X___XX__X__XXXXXX____XXX__X__X
___________XXXXX__XX__X_XX__XX
XX__XX___X__X___X___X_____X__X
X_X_X_XXX_______X___X_____XX_X
_XXX__X_X___XX_X__XXX__X___XX_
X___X__X_XX_X_XXX____X_____X_X
X_X_X_X____X_X_______________X
_XXXX_X__X_____XX_X_X___X___X_
____XX_XX_X___XX____XX_X____X_
X_X_XXXXXX____XX_X_____X____X_
X___X_X_XX______XX_X____XX_XXX
X_X__X__X___XX_XXX____X___XXX_
_X_X_XX_X____X_______XXX__XX_X
_X_XXX_______XX__XXX__XX__X_XX
____X_______X_XXX_XX_X_X______
__XX_X__XX_X_X___XX_XX_X__XX_X
X___XX_XXXXX__X____XXX_X______
__X_XX__XX_X__________XX__XX_X
______XXXXX_______X_X________X
X__X_X__XX__XX_XX_XX_____XXXX_
X___XX_XXXXX_XXX_X_XX___XXX_X_
_XX_____X_XX_X___X_X___XXXXXX_
__XX_X_X____X_X__X_______X_X__
X__X_X___X_XXX_XXX_X__XX_X__X_
___X_X__X_XXX_____XX__XX______
_X_XX_X__X___XXX_X__X_X_______

The question I would like to consider then is, what is the size, in number of squares, of the largest continuous black section? We'll say that two black squares are touching only if they share a side - no diagonals. So, for a given value of p on a given board, what is the largest number of black squares you expect to find all touching each other?

This is a variant of a problem in graph theory known as looking for the largest connected component of a random graph. Analysis of that problem yields some interesting results, but I'm not sure how to extend it to here, where the geometry of the graph is modified.

However, we can approximate, test, and simulate. Using p from 0 to 1, at increments of 0.01, I generated such boards (I think it was a 70x70 board), filled them, and determined the maximum connected component on the board. And then I repeated this multiple times, averaging them all together with a convenient ruby script. Here is a plot of the results, in terms of the probability p along the x, and the maximum size as a fraction of the whole board along the y.

Notice that for p less than about 1/2, the size of the maximum component is ridiculously small. Which means that if you color only half or less of the squares, you can expect, on average, very tiny connected blobs of black. But soon after that, the behavior of the curve changes drastically, practically exponentially. A dramatic increase in the expected size of the maximum component. It is as though the board reaches a sort of carrying capacity for the smaller blobs, after which point (increasing p and adding more black squares), it becomes necessary to begin connecting smaller blobs into larger. There's no way to fit any more smaller blobs onto the board, and as you continue to add black squares, the smaller blobs become connected at an increasing rate.

It's very interesting, I think.

And makes me think, abstractly, of Blokus.

Average-Case Complexity

2008-01-22T11:04:00.000-05:00

(Cross-posted at PowerUp)

Analysis of algorithms is important at just about all levels of computer science as well as software engineering. When analyzing algorithms, we usually have in mind the property of running-time complexity, a measure of the efficiency of the algorithm by how many steps it takes. In addition, we often must also take into account unavoidable costs by invoking constant terms. Unavoidable costs show up in many practical areas, an example from my main interest (computer graphics) is the draw call cost associated with rendering objects to a screen or to a memory buffer. Here, we primarily take a look at the techniques of average case analysis through the common, though instructive, example of the hiring problem.

The hiring problem is defined as such. You are given the task of hiring an office assistant, and the task itself is a two pronged process of interviewing and hiring from a list of n candidates. Both interviewing and hiring have associated costs. Interviewing has a low cost, which we will denote by ci. However, actually hiring an assistant has a much higher cost, which we will denote by ch. After interviewing an assistant, if they are superior to the currently operating office assistant, the candidate becomes the office assistant. All candidates must be interviewed, so the lower cost is guaranteed to be incurred for each candidate. However, hiring is not a guaranteed for each candidate. We add to this the assumption that the candidates are offered for interviews according to uniform distribution, i.e., they come in a statistically random order. And to simplify, we also assume that the quality of the candidates represents of a total order, i.e., all candidates yield to hard inequality (either > or <).

Essentially, the algorithm for computing this problem can be defined as such.


1. set current_assist to 1
2. for candid(2-N)
3.     if candid > current_assist
4.        do current_assist <-- candid

Essentially, all we really need to determine in the running time for the algorithm is how often we execute step 4. We know we incur the heavy cost of hiring at least once, as per step 1, and we have to go through interviewing each candidate as per steps 2 and 3. Trivially, the best case running time is $ O(nci\ +\ ch) $, since you only incur the cost of hiring once and no candidate inteviewed is superior to your first hiree. In the worst case, the candidates are interviewed in a perfect ascending order of quality, meaning you must execute the hiring operation a total of n times, yielding a running-time of $ O(nci\ +\ nch) $. Clearly, neither the best or worst case is representative of the expected running-time of the algorithm. What we are looking for is the average case, or the expected running-time when all inputs are considered.

Usually, average-case analysis is done through an enumeration of all possible inputs and a derivation of the expectation or variance of the inputs. For many algorithms this can be a cumbersome operation to perform. For the hiring problem, this actually isn't too difficult. Cormen, et al. do so in Introduction to Algorithms. In short, since the candidates are interviewed according to uniform distribution, the probability that any candidate i in the list of all n candidates is superior is 1/i. The expected running-time thus coincides with the harmonic series $ \sum_{i=1}^n\frac{1}{i} $, which converges to $ lg\ n\ +\ O(1) $. Thus the average case running-time of the algorithm is on the order of $ O(nci\ +\ ch\ lg\ n) $.

That would be an example of the obtaining the result via the probabilistic method. An alternative method for average case analysis is known as the incompressibility method. The latter takes advantage of a well acknowledged fact from the theory of Kolmogorov complexity: very few strings have short descriptions. In other words, the vast majority of members of any given set of objects will be Kolmogorov random. This gives us a way to determine the average-case running time by examining one input that is guaranteed to be representative of the ensemble of inputs. To demonstrate this, we take an arbitrary permutation p of the list of n candidates and fix a universal partial recursive function f to compute p given n. Given n inputs, there are a total of n! possible permutations. Assuming uniform distribution of inputs and thus equidistributed hirees in the hiring assistant algorithm, most strings would contain $ O(lg\ n) $ hirees. Assume the contrary, that most strings contain significantly more or fewer than $ O(lg\ n) $ hirees. Then there would be a short description of the majority of the inputs, being highly regular sequences. This however would contradict the well known fact that for every set A of cardinality n:

$ K_f(p\ |\ n)\ \ge\ lg\ n\ -\ c $

For all but about $ n(1\ -\ 2^{-c})\ +\ O(1) $ elements. Here, $ K_f(p\ |\ n) $ represents the Kolmogorov complexity of the permutation p given n (that is, the quantity n is known in advance to us and is encoded by the partial recursive function), and c is an arbitrary positive integer. A string x is said to be c-incompressible if $ K(x)\ \ge\ l(x)\ -\ c $, where $ l(x) $ is the length of the sequence. Since most strings are incompressible, the contradiction shows that most permutations p of n inputs can't have short descriptions. The average case running time is thus, as it was before, $ O(nci\ +\ ch\ lg\ n) $.

Further reading: I kind of handwaved on some of the stuff here, especially definitions of Kolmogorov complexity. For that, you should consult either Li and Vitanyi's An Introduction to Kolmogorov Complexity and Its Applications (the entirety of chapter 6 is on the incompressibility method) or Peter Gacs' lecture notes on Algorithmic Information Theory. Probabilistic analysis is covered by Cormen, et al. in chapter five of Introduction to Algorithms.

Recursive Grab Bag

2008-01-14T20:30:00.000-05:00

A rather interesting topic in math (what a general way to start a post) is the matter of recursive functions. These are functions that are expressed in terms of themselves. A fairly traditional example would be factorial. n! is defined to be

Now, a nicely concise way to write this, not to mention computationally convenient, is to define the following

So, the operation is defined, effectively, with respect to itself. There are a lot of operations that can be defined very nicely in this way. Consider the following, for example.

Calling f(2, 3) then, it unwraps to give

In general, it's clear that f(x, n) returns n*x. In effect, this is a recursive definition of multiplication. So, many nice things can be expressed very nicely using recursion.

But, many interesting things can be expressed with recursion that can't be expressed nicely otherwise. Consider, for example, the Ackermann Function, A(m, n) defined as

If m = 0:
If m > 0 and n = 0:
If m > 0 and n > 0:

A(m, n) has no non-recursive definition, no closed-form expression, or anything near as nice as the two recursive examples I already showed you have. The above is the best you're going to get. Interestingly, it is the simplest function for which that is the case. The other point of interest about the Ackermann Function is how incredibly fast it grows, even for small m and n. In fact, A(4,2) has 19729 digits, which is far more than I am comfortable writing out here. The full number can be found here, if you're interested. A very, very large number. In fact, at that magnitude, I'd argue that the full text of the number is next to meaningless, when compared with the much more concise description of the same number as merely A(4,2).

Alternately, there are things that are expressed very nicely with recursion, that become much less nice when unraveled. Take, for example, the Fibonacci Sequence. Starting with a 1 and a 1, the sequence is formed by taking the sum of the two previous terms. This produces 1, 1, 2, 3, 5, 8, ... and so on. More concisely, it can be written as

A very clean and elegant description of the sequence. Unraveling the recursion, with all due care, it can be shown that the following definition is equivalent.

Hardly the most elegant of formulae. Somehow, the recursive definition captures the relationship between the terms of the sequence far better. However, and this becomes more clear with more complicated recursive definitions, it is increasingly difficult for humans to fully grasp the shape and form of the sequence - something that becomes much simpler even in the more complicated form. In that way, the goal of unraveling these recursive definitions is a markedly human endeavor. The whole of the sequence or function is defined through the recursion, and the act of unraveling it merely serves to make it understandable to us. To make the full implications of the levels of self reference clear. In many ways, I think this is indicative of the goals of mathematics as a whole. In general, you start with a concise set of axioms and assumptions, and tease out some conclusion or theorem from them. The conclusion or theorem of course already existed as truth, through the statement of the axioms, but the act of proof teased out a bit of comprehensible meaning that was otherwise unclear from the statement of the axioms themselves. The whole of math exists in the statement of the axioms - the point of math is to bring the full weight and import of those simple statements to a understandable level. As much as I am loathe to admit it ... it's all a very human enterprise.

But I digress. That is a topic for another time.

So, in general, given a recursive function or sequence, it's an interesting mathematical question of whether the recursion can be unwrapped to give some form of closed-form, non-recursive description of the same function or sequence. In my next post, or something soon at least, I'll discuss generating functions, a neat tool used to such ends.

The Necessity of Relativity

2008-01-14T20:23:00.000-05:00

Relativity holds a rather curious place in physics, as I see it. Other branches - nuclear, mechanics, E&M, so forth, all seem firmly based in the study of physical objects, systems, and principles. Relativity is, in point of fact, much more of a math than a physics. It starts with simple axioms about our understanding of the universe and derives conclusions from them about the way the universe must work. The tools of relativity are not physical laws, but rather logic.

Now, as I said, relativity starts with simple axioms, and works from them to derive its conclusions. The axiom in question in this case is that the speed of light is finite, and constant. No matter who is measuring it, how fast they are going, what they are doing, who else is measuring, all observers always measure the same speed of light. That speed we'll call c here, though more traditionally it is 299 792 458 meters per second.Now to the experiment.

Alice Cooper is riding in a train which is moving at speed v. At some time, which we'll call even one, a flash of light is emitted from the floor of the train, straight up towards the ceiling, being absorbed by the ceiling at event two. If we say that the train is of height h, then the entire transit time of the flash, from the floor to the ceiling, as seen by Alice, is h/c. And needless to say, the length of the path of the light flash, from the floor to the ceiling, as seen by Alice, is simply h.

At the same time, a man with no distinguishing characteristics, code named 'Observer' is standing at a station watching Alice Cooper's train pass. He sees the light emitted, watches it travel, and watches it be absorbed by the ceiling of the train. Below is a diagram of what he sees.

The problem should begin to be clear. Once the light is emitted, some time passes before it is absorbed by the ceiling. During this time, the train continues forwards, so the point of absorption is no longer directly above the point the light was emitted from. As such, there is now a horizontal component to the path of the light that was not present in the first case. As such, the light travels further for the station observer than it does for Alice Cooper.And -that- is ridiculous! How could someone measure something as one length, and someone else measure it as another? To make matters worse, since as we said, they both measure the speed of light to be the same thing, c, if they measure the paths as having different lengths, then they must measure the time between the two events as different as well, the station observer measuring a longer time since it takes longer for light to travel along that path.

Clearly a contradiction. Nevertheless - nothing in this thought experiment is strange or alien or impossible. There are no buses going the speed of light, no perfect spheres. If we wanted to, we could put Alice Cooper on a train, we could speed it up to some velocity, and some man could be observing the train. Everything is doable, and the contradiction is simply a logical result of what we know to be true. This is the essence of relativity - it is a mathematical description of how the -must- universe work. It is a necessity.

Let us ask then, exactly what the station observer measures between the two events in terms of distance and time. Let the distance between the emission and the absorption be L, and the time be T. Because the speed of light is constant, we know that the time the station observer measures must be T = L/c.

But what of L? Notice the diagram below, with the conveniently drawn right triangle.

The hypotenuse of the diagrammed triangle is the path the light takes, so it is of length L. The vertical leg of the triangle is simply the height of the train, which is h. The horizontal leg is the distance the point of emission travels during the time interval between events. In other words, v*T. Using the Pythagorean theorem and that T = L/c,

Notice that L, the distance the station observer measures the path to be, is simply h, the distance Alice Cooper measured, scaled by a curious factor. Now look at the time.

Notice that T, the time the station observer measures the path to take, is simply h/c, the time Alice Cooper measured, scaled by the same curious factor. Length and time have been dilated. The conclusion is inescapable, bizarre, completely logical, and utterly fascinating.

So we have two observers, measuring ostensibly the same thing, but each getting markedly different results in their measurements of time and distance. This is a drive by introduction to special relativity.

The important thing to note here is this - many people object to the conclusions of relativity as bizarre, counter intuitive, nonsensical, and downright impossible. However, the problem is not with relativity. Relativity is simply a precise, mathematical description of what -must be true- about the universe based on what we know to be true. There are no special forces at work here - no magic, no hand waving. Each step of the derivation follows logically from the rest. Relativity is simply a mathematical necessity based on our understanding of the universe.

A mathematical necessity. And there's really little more to say than that.

Uncomputable and Probabilistic Quantities

2008-01-11T22:43:00.000-05:00

(Cross-posted over at PowerUp)

One of the things that has always intrigued me about computer science is that, from the perspective of theory at least, you have extensive uses of probabilistic reasoning in a field where that superficially looks to be entirely deterministic. We all know about the undecidability of the halting problem, but an even more interesting result is that of Gregory Chaitin, who derived an uncomputable number from said problem by compactly quantifying it as a probability. Here we have the famous halting probability $$\Omega$$, which represents the probability that a reference machine U will halt if its program is provided by a sequence of fair coin flips.

$$\Omega\ =\ \sum_{U(p)<\infty}\ 2^{-l(p)}$$

Where p represents all inputs for which the reference machine halts, and l(p) is the length of the binary description of all such programs. Since the sum is taken over all such inputs, we know that $$\Omega\ >\ 0$$. However, since U(p) doesn't always halt, we also know that $$\Omega\ <\ 1$$. From there, it gets more difficult to narrow down the quantity. The halting probability is a random infinite binary sequence, random of course meaning that its digits are equidistributed and infinite meaning it extends without termination, i.e., a real number. And more interestingly, an uncomputable real number. To understand this, define a function $$\ f(x)\ =\ \Omega_{1:x}$$, that is, the digits of $$\Omega$$ computed to an arbitrary precision represented by x. There is no partial recursive function that can coincide with f(x) on its entire domain of definition. You have a literally unknowable quantity, and probability gives us a way to rigorously quantify the famously unsolvable problem in computer science.

The above seems abstract, but uncomputable quantities like the halting probability play both theoretical and practical roles in computer science. Another similarly uncomputable quantity in computer science, and more specifically the theory of Kolmogorov complexity, is in fact known as the "universal probability distribution". Usually talk of "universality" in computer science entails objects that emulate the behavior of any other in its general class. The idea of general purpose machines, functions, etc. is in fact a central notion of the entire field, and the one which makes it a worthwhile field of study in the first place. For the universal distribution, however, "universality" entails a quantity that is guaranteed to be greater than all others in its general class. In technical language, this "universal" probability distribution, usually denoted by m as a matter of pure convention, is an enumerable distribution that multiplicatively dominates all others. "Enumerable" meaning "semicomputable", which in turn essentially means that the quantity is not necessarily itself computable but can be approximated computationally (that is, the set of computable quantities is a proper subset of that of all enumerable quantities). The universal distribution is defined thusly:

Given an enumeration $$\ M$$ of all probability distributions $$\ P_1,\ P_2,\ \ldots,\ P_n $$, there exists a $$\ P_0 $$ which given a constant $$\ cp$$ returns $$\ cpP_0\ \geq\ P_i$$ for all $$\ P_i\ \in\ M$$.

The constant invoked above is a general variable for a multiplicative factor dependent on P but not on the possible arguments taken by P.

The uses of the above quantity are manifold. Since "probability" is usually operationally defined as "expectation among a set of conditions", the universal distribution often makes an extremely useful prior in machine learning applications. Given that it (multiplicatively) dominates all other enumerable distributions, it maximizes ignorance by assigning the highest possible probability to all events in a given sample space. It also has some unique consequences for average case complexity analysis regarding specific algorithms, as well as their resource-constrained counterparts. For further reading on the universal distribution, the entirety of chapter 4, as well as sections 7.4-7.6, of Li and Vitanyi's An Introduction to Kolmogorov Complexity and its Applications should be consulted. The halting probability is mentioned in passing in section 3.6 of the aforementioned, as well as sporadically brought to bear throughout the text. However, for a more explicit and thorough derivation, I'd consult Gregory Chaitin's Algorithmic Information Theory.

Pascal's Triangle: And you hoped it was over...

2007-12-17T20:07:00.000-05:00

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.

You've Probably Wondered, But Were Afraid to Ask

2007-12-17T15:20:00.000-05:00

As well you should've been, by the looks of things.

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.

My First Encounter With a Relativity Denier, Verdict: Stupid

2007-12-06T14:26:00.000-05:00

(Cross-Posted at PowerUp)

Earlier on, PZ pointed to an article by some whack-job claiming to refute the theory of relativity. I'm not very familiar with relativity denial, so I didn't actually read the article. I picked it up again courtesy of Blake, and now I wish I hadn't. Take a look at his descriptions here:

MATHEMATICAL MODELS are abstract, idealized, imaginary models which contain characteristics and assumptions which cannot exist in reality (such as points, lines, triangles, spheres, etc.) These models can be purely logical, purely mathematical, geometric, kinematic, dynamic or electromagnetic. All of these models are based on the LAWS OF MATHEMATICS (symbols, equations, formulas etc.) which only approximate the physical LAWS OF NATURE. These mathematical models produce deductive conclusions which only apply to the idealized mathematical models.

PHYSICAL MODELS are real models composed of physical objects which are used in empirical experiments. By repeating identical (as far as possible) testing with these models, inductive conclusions can be made. These inductive conclusions, because they are the results of physical experiments, are the fundamental method used by science in an attempt to understand the LAWS OF NATURE. Knowledge about the real Universe must come from physics and not from mathematics. Experience has always been the primary guide in human reasoning concerning physical facts.

METAPHYSICAL MODELS are sophistic models which contain both mathematical characteristics and physical characteristics. These are mingled or mixed models. Neither mathematical deductions nor physical inductive conclusions can be produced from these models because they cannot exist in reality. These are pseudoscience models which result from “thought experiments”. These are purely imaginary mental creations. Any conclusions whatsoever that these models produce are completely irrelevant to anything. They cannot produce any valid understanding of reality. A sophist is someone who deceives people based on clever-sounding, but flawed arguments or explanations. However, these fallacious theories do produce popular imaginary science fiction tales about time travel (Back to the Future, motion picture) and spaceships that travel at the speed of light (Star Trek, motion picture).

We obviously lack a rigorous definition of what I'll call the "Pauli threshold", the point where an argument just gets so absurd that it's not even wrong. But I think it's clear that this particular nonsense is off the charts regardless of any metric we could possibly come up with.

For someone who is supposedly a "mathematics graduate" it is stunning how ignorant those three paragraphs alone manage to be. Even the most superficial look at the history of physics and it's relationship to math deflates his claims easily. The differential and integral calculus were developed in large part as a framework for early classical mechanics, in addition to providing the basis of analytic function theory. Successive developments in latter include Fourier analysis, which gave us the Fourier transform and allows physicists to use such idealized objects as phase-shifted sinusoids to describe otherwise inaccessible quantum behavior. Need we bring up super-abstract Group Theory, which is pretty much indispensible in describing spacetime symmetries? Need we point out that the complex vector space, which includes those seemingly perfectly abstract "imaginary numbers", is an essential notion in quantum physics? For some generic thing's sake, you have no physics without mathematics! Mathematics and physics, far from being "inherently different", are so conceptually intertwined and contiguous as to be inseparable.

In addition to being ignorant of the history of science, it appears that he's behind on every development in the philosophy of science since, uh...Bacon? Science isn't purely inductive, it employs a combination of hypothetical, deductive and axiomatic reasoning at multiple levels. And for another thing, constructing a physical model necessarily employs mathematical reasoning within an axiomatic framework. The purpose of tests is to see if these abstract models accurately predict reality.

I don't think I can bother with the rest of the article, the stupid is already burning through my skull. I'll leave to rest to other bloggers, Dave Bacon and "gg" have already tackled much of it.

Erdos-Szekeres, and The Mathematical Certainty of Structure

2007-12-01T14:55:00.000-05:00

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 Sequence Of Interest

2007-11-10T11:16:00.000-05:00

This is just an interesting problem that came up the other day, and I rather enjoyed my solution to it.

We have a sequence,

Our goal is the value of as n goes to infinity.

For those interested, the first few values are approximately 1, 1.414, 1.848, 2.294, 2.749, ... The exact form of the values quickly becomes a mess of nested roots I wouldn't want to subject anyone to.

The first thing to do is a rather nice substitution, putting in the definition of to achieve

Several things become obvious right away. Most importantly, perhaps, is that the sequence is increasing. This is pretty clear from the numeric values I gave for the sequence, but this verifies it since

Giving

That in hand, I would like to generalize a bit and look at the function

Specifically, I want to think about its behavior as x goes to infinity. Just straight up plugging in infinity is rather unhelpful, since you get infinity - infinity, but with some cunning manipulation ... observe.

When I first wrote up this problem to turn it (it's for a class), once I got to the fraction representation, I was able to use L'Hopital's rule to solve this. As such, I titled my proof for Captain Bohman 'A Sequence of Interest : or How I Learned to Stop Worrying and Love L'Hopital'. Unfortunately, I then came up with the much nicer substitution you see above, which removes the need for L'Hopital, and thus ruins what is otherwise a great title. Just a personal side note.

But now we have a much nicer form of the expression, and we can do many things with it. For example,

Thus,

Which I find is a fascinating limit. Really it's why I like this problem so much.

But before we go back to the sequence, a couple of things to note. As x increases, is strictly decreasing, which means that is strictly increasing. Since at x = 0 the function has the value 0, it is strictly increasing, and the limit as x goes to infinity is 1/2, the function increases from 0, continuously passes through all values from 0 to 1/2, finally reaching 1/2 very far from now. Just keep that in mind.

And why is all this important? Because if we jump back to our sequence, and look at successive differences of terms, we get

Since, as we discussed, is increasing, the limit can be applied to say

And we can use facts about the limit to say nice things about those differences. For example, the successive differences are strictly increasing, and increase to 1/2. This is important, because it means that every difference is bounded from above by 1/2.

And that is what we can use do the following. Because 1/2 is greater than every successive difference, not that we can do the following

Since , we have a rather nice upper bound on ,

This will come in handy. Remember that one.

Now we want to bound from below. This gets a little trickier. Remember how increased smoothly from 0 to 1/2? As I pointed out, the successive differences do the same thing, though much less smoothly. That is to say, given some value between 0 and 1/2, we'll call it f, I can find an N such that for any n greater than N,

That is, any successive differences after N will be bound from below by f. We can then bound the sequence from below, like so. For convenience, I'm going to say that f equals p*(1/2), for some value of p between 0 and 1. Though obviously p is less than 1. So, given a value of p, I can find an N such that

Or, more nicely,

But remember, all successive differences there on are also bound by p*(1/2), so

Extrapolating outward, we get, for any positive integer k

And that gives us a lower bound, starting from N and going onwards.

Now we can combine our bounds to say, for a given value of p and the appropriately chosen value of N,

Now things start falling into place. We just just follow our noses. Start by dividing through by N + k.

With that in hand, we can start discussing what happens as k increases. Note that N is constant, so as k increases, is a constant divided by a larger and larger value, and it goes to 0. Related, as k goes to infinity, is essentially k/k, and will go to 1. On the other side, is a constant divided by an increasing value, so it will go to 0 as well. So as k increases to infinity, you're left with

Which is the same as saying, for exceptionally large n,

Which is quite nice! Basically we've squeezed the ratio between the ratios of the upper and lower bounds of the sequence, and squeezed the limit of the ratio to something between p*(1/2) and 1/2. Note though that p was said to be less than 1, so p*(1/2) is less than 1/2. So the limit in the bound above could actually be less than 1/2. However, notice that this derivation is valid for any value of p less than 1, and so the inequality above must be valid for any value of p less than 1. So I can essentially take the above bound, and squeeze p towards 1 as close as I want, which pushes the ratio closer and closer to 1/2 before finally nailing it there.

And we get

And so it's done.

Probably much more loquacious than need be, but I'd hate to think I lost anyone. Hope you enjoyed that as much as I.

*wag*

The Probabilistic Method

2007-10-28T14:15:00.000-04:00

Now here is something quite cool. The probabilistic method.

The idea is this, in glib summary, that you prove something exists by proving that the probability of it existing is greater than 0, or that the probability of it not existing is less than one.

There are many different ways to approach this really, though they all amount to the same thing. You consider a distribution of mathematical objects, and you're interested in one with a particular property. You imagine picking one of those objects from that random distribution, and show that the probability of picking the one your after, or one of the type your after, is greater than zero, or the probability of not picking it is less than one. The idea is that if there is a probability of you picking it, then it must exist /somewhere/ in the set. You don't know where, but it's got to be there somewhere or you would have no probability of finding it.

It's rather silly in many ways. For example, even though you prove that something exists, especially in this way, gives you no insight into how to find it. It's completely non-constructive, but the logic of the approach is irrefutable.

But I suppose it is best taught by example.

First off, a bit on graph theory.

A graph is a collection of things. Objects. They can be ... most anything really. These are called vertices. The important part of the graph is that it also contains connections, or edges between the vertexes. A good example is a map. A map can be modeled as a graph, were the vertices are cities and edges the roads between them. But the idea of a graph can be extended and used to apply to many things. As such, it's useful to study the abstract model of a graph, because any insights can then be applied to anything you can model with graphs.

There are many nice questions you can ask about graphs. For example, graph colorings. Suppose you are going give each vertex of a graph a color. However, you don't want to connect any vertex to be connected to a vertex of the same color. For a given graph, what is the minimum number of colors needed to color it?

That's actually a really interesting example. A quite famous ... issue ... in mathematics is the four color theorem. The idea is that given a map, any map, you can color the countries on the map such that no country is touching a country of the same color, with no more than four colors. This is actually a graph coloring question. The idea is you model each country as a vertex in your graph, and create edges between countries that touch each other. The problem is completely generalizable to graph theory. The nice thing about this is that you've taken a problem that can be overly complicated due to borders of countries being strange shapes, and all kinds of bizarre geometries, and turned it into something much more straight forward, a set of vertexes and connections between them. That is the beauty of abstract mathematics.

For those interested in reading further, MarkCC has an excellent set of posts on graph theory. Unfortunately the link lists them in reverse chronological orders, so for introductory graph theory posts you have to scroll all the way to the bottom and work your way up. Have at it :)

But the problem I would like to address, with the probabilistic method, is that of dominating sets.

Here we have a graph. Please excuse the crudeness.

Notice how one of the edges in this graph overlaps another, without a vertex between. This ok. The only think that matters about edges is the two vertices they connect. The more complicated the graph, the harder it is to draw sensibly on a surface like that.

However, a dominating set is a set of vertices such that anything not in the set is connected to something in the set. For example, the set of all vertices in the graph is a dominating set because anything not in the set (which is nothing) is connected to something in the set. Below, I've circled vertices that compose a dominating set.

A given graph can have multiple dominating sets. A interesting question then is what is the size of the smallest dominating set for a given graph?

For this exercise, I'm going to limit myself to r-regular graphs. An r-regular graph is a subtype of graph such that any vertex is necessarily connected to r many other vertexes. So, the question is this:

Given an r-regular graph, what is the size of the smallest dominating set?

And we're going to use the probabilistic method! The one you've been waiting for.

Consider a random graph. That is to say, we have n vertices, and we are, at random, going to construct edges between them, with no restriction other than that the resultant graph is r-regular.

Next we're going to perform an experiment. We're going to consider each of the n vertices, and with probability p, we are going to add them to set S1. After this is done, there should be, on average, p*n many elements in set S1, and (1 - p)*n vertexes remaining.

Next, we go through the remaining (1 - p)*n vertexes. Considering each vertex, if there is /not/ an edge connecting it to something in S1, we add it to S2. After this, all the remaining vertices not in S1 or S2 will be connected to something in S1.

So then consider the set S as the union of sets S1 and S2. S is a dominating set of the graph.

Note that any dominating set of the graph can be constructed in this way. Assume that the graph has a given dominating set. In the first step of our experiment, there is every possibility that every vertex in that dominating set will be added to S1. On average, there will be n*p elements in S1, but it can happen that exactly the vertices of a dominating set are added to S1. In that case, since everything else is connected to S1, S2 will be empty, and S = S1, a dominating set.

What we are going to look at though is, performing this experiment, on average how big will the resultant dominating set be?

So we want to consider what the expected size of S is. We know that S1 and S2 share no elements, because S2 taken from the vertices not in S1. As such, we know that the size of S is the size S1 plus the size of S2.

S1 will contain, on average, n*p vertices.

But what's the expected size of S2? It's chosen from a population of (1 - p)*n vertices. But, given an element from that population, we'll call it w, what is the probability that it is added to S2? That is, the probability that it is not connected to anything in S1.

So, given a single vertex w, what is the probability that it is not connected to S1?

A given element of S1, u, what is the probability that u is not connected to w? We know that u is connected to r many things. The probability that any one of them is w is 1/(n - 1), because w is one out of the n - 1 remaining vertices. So the probability that u connects to w is r/(n - 1). Therefore the probability that u is /not/ connected to w is 1 - r/(n - 1).

But that is for one element of S1. We want all elements of S1 not connected to w. The probability of this occurring is given by

Therefore, the expected size of S, the generated dominating set, is given by

That expression there is the fruit of our probabilistic labors. But now what can we do with it? Suppose for example we have that p = 1/2, so elements are inserted into S1 initially with a 50% chance. Then we have

Looking at the above expression, is going to be consistently greater than one, so with p = 1/2, you will expect on average a dominating set of size slightly greater than n/2.

What does this mean? If the expected size is a given value, then there must be a dominating set with size less than that which has some probability of occuring. What this says then is that there exists a dominating set whose size is at most n/2*(all that stuff). What this shows then is that, for any r-regular graph with n vertices, the minimum dominating set will have size less than or equal to n/2*(stuff).

Can we improve this, though? The idea is, can we modify our experiment to produce a better result. The only parameter we have to play with, without changing the actual structure of our experiment, is p. By choosing appropriate values of p, we can minimize the expression for the expected value of the size of the dominating set. Minimizing that, as before, since that is the expected size of the dominating set, there must be dominating sets with size less than or equal that.

But how do we know that this approach is valid, really? Well, we can test it for known cases. For example, consider a graph of r + 1 vertices, where each vertex is connected to every other vertex. Clearly this fits the r-regular restriction. In this case also, a single vertex is a dominating set, because all vertices are connected to every other vertex. But what does our expression give in that case? Letting n = r + 1,

Note, if we had chosen that p = 1/(r + 1), the expected size of the dominating set would be 1, which confirms what we already knew, the graph has a dominating set of size 1.

So ideally, we want to strictly minimize our expression with respect to p. One way to do this would be the typical calculus approach, finding the zeros of the derivative with respect to p. Unfortunately this produces an absolutely unintelligible, unsimplifiable mess, albeit a very nice upper bound on the size of the minimum dominating set. Given actual values of r and n, one can use that formula to calculate an explicit upper bound, but the general formula is rather ugly and uninteresting.

However, in general, choosing a near optimal p value,

Which gives a much nicer upper bound, though not quite as tight as I would like. I'll leave that as an exercise to the interested reader.

But what have we accomplished here, really? If you take the above inequality as true, and I do think it is, we've shown that for any r-regular graph with n vertices, it contains a dominating set of size less than or equal to (1 + Ln(r))/r*n. Because we started our experiment with a general r-regular graph, this holds true across all r-regular graphs. Notice though, we have made no assumptions or declarations about that dominating set, except proving that it exists.

And that is the probabilistic method. Given a random distribution of objects, you prove that the probability of getting it is greater than 0. Therefore it must exist in the distribution, and it must exist period.

I really like this. I often think of myself as a math experimentalist, and this kind of approach, setting up an 'experiment' and looking at the implications of the outcomes rather appeals to me.

Anyway. I hope that was informative. And that I didn't muck anything up.

Cranks Cluedo: The Murder of Science with Pseudomathematically Enhanced Ignorance.

2007-10-26T22:04:00.001-04:00

(Cross Posted at PowerUp.)

[Okay folks, this is the neat thing I mentioned from a while back. The blogger with whom I am collaborating on it is Blake Stacey. The basic idea is to provide a series of posts debunking specific misuses of science among cranks, in a way that is analogous to the Hoofnagle's Denialist Deck of Cards. For our game, we go with a Clue Format, and we call this series Cranks Cluedo. The Dossier has three parameters: "Who?", describing the perpetrating crank; "What Fallacy?" describing the rhetorical device or logical fallacy involved; and finally, "What Field?", describing the field of science the perpetrating crank abuses. Blake will be doing quantum woo for his first post in the series, I focus on creationists in abuses of probability and related concepts.]

DOSSIER

Who?: Creationists.

What Fallacy?: The Argument from Augmented Ignorance.

What Field?: Probability and Optimization Theory.

Ignorance, though much maligned, is a natural aspect of the human condition. We are all ignorant of more subjects than we can ever hope to be knowledgeable in. As the saying goes, “ask me how to fix my car, and I'm completely in the dark.” But it is equally true that ignorance is by no means a reason to declare something a priori impossible. For instance, if my car mechanic informs me that my car is not starting because of a loose spark plug, I cannot dismiss this simply because I do not understand how such a small part can disrupt the functioning of such a complex device. But this utterly fallacious argument, or at least something similar to it, underlies the claims of many varieties of creationist when they assert that evolution involves prohibitively improbable events.

Creationists use a special case of the argument from ignorance. Here, I informally denote it as the argument from augmented ignorance. Whereas the garden variety appeal to ignorance exploits genuine (which is not to say necessarily excusable) ignorance in a given instance, appeals to augmented ignorance use a myriad of clever rhetorical ploys to amplify ignorance beyond proportion. When creationists appeal to the “low probability” of evolutionary outcomes, they typically use unnecessarily turgid mathematical jargon and notation to gloss over important details of evolution. Nowhere is this better illustrated than in the classical creationist appeal to probability, conveniently provided by the TalkOrigins Index to Creationist Claims:

The proteins necessary for life are very complex. The odds of even one simple protein molecule forming by chance are 1 in 10¹¹³, and thousands of different proteins are needed to form life.

Setting aside the usual conflation of evolution and abiogenesis, even this concise assertion manages to replicate every fallacy in the creationist probability playbook. It is nothing but a regurgitation of numbers without any consideration of whether the mathematical model that contextualizes them provides accurate predictions in the physical world. Unfortunately, it doesn't. The two basic false assumptions that render it moot are as follows:

The Assumption of Uniformly Distributed Outcomes: Or less formally, assuming that all outcomes in the sample space of a random experiment are equally likely. The process of assembling proteins above is assumed to be a completely unguided and effectively random process, thus ignoring its underlying physics and chemistry. An analogous but more basic scenario in high school level chemistry would be to “randomly” pop balloons of hydrogen and oxygen and calculate the odds of them “randomly” assembling the same molecule (H2O). Such an assumption is patently absurd, as the probability density is clearly concentrated in a specific outcome.

The Assumption of Strictly Sequential, Unweighted Trials: The assumption that the process of creating the proteins is a one-dimensional sequence of unweighted trials. In a realistic biological scenario, concurrency would have to play a significant role, as would contingency and building on past successes.

Expanding on the invocation of these fallacies in more refined instances of the argument from augmented ignorance helps to illuminate its problematic nature. In one form or another, almost all creationist probability arguments replicate them.

Uniformity is a Force That Gives Us Meaning

Probability theory uses methods analogous to measuring the dispersal and concentration of physical objects. This is enabled by the important concept of a “random variable”, which is a function X that maps each outcome in a random experiment S to the real numbers. Two broad classes of random variables are discrete random variables, where X is conceived of as a stepwise function, and continuous random variables, where X is conceived of as a continuous function able to assume any real numbered value. In the continuous case (chosen here because of its intuitive value) a uniform probability distribution in an arbitrary interval [a, b] assumes a value 1/x for all a \<= x \<= b (and a value of 0 for any argument outside the interval). A more substantial statement to this effect would be that a probability distribution function of 1/b-a represents a uniform distribution if it yields a derivative of unity across the entire interval. The latter bit is known as the probability density function. Intuitively, it should be obvious that a continuous function assuming a constant value of 1 represents no mass concentrations of probability in favor of any outcome, as illustrated by the second graph below.

(Images Courtesy of Wikimedia Commons.)

Uniformity is a useful assumption in many scenarios encountered in probability theory, but as a concept it often fails to accurately map the real world. Usually it is tantamount to assuming pure randomness, while it should be obvious that many measurable processes can be constrained to a large degree. One can always describe an arbitrary non-uniform distribution function, and several recur often enough to be given names of their own (e.g., binomial distributions, Poisson distributions, etc.). In an example considered above, the outcomes of the experiment wherein one pops balloons of hydrogen and oxygen are certainly not uniformly distributed. One could in the abstract conceive of individual atoms as discrete objects whose combinatorial outcomes are uniformly distributed across all possible combinations of n atoms. This would be absurd, for obvious reasons. A mathematical model which has no predictive value in its specialized scenario fails, and ignoring known principles of physics and chemistry is guaranteed to engender such a failure.

However, whereas such a thing would be meaningless to scientists interested in accurately describing reality, the crank often uses it as a tactic in declaring that the scenarios postulated by mainstream science are impossible. This is usually a perfect replication of the argument from augmented ignorance, because it uses unfounded assumptions to amplify doubts and give a semi-convincing aura of legitimacy to their own notions. Consider this bit of pablum from one William Dembski:

Most searches that come up in scientific investigation occur over spaces that are far too large to be searched exhaustively. Take the search for a very modest protein, one that is, say, 100 amino acids in length (most proteins are at least 250 to 300 amino acids in length). The space of all possible protein sequences that are 100 amino acids in length has size 20¹⁰⁰, or approximately 1.27×10¹³⁰. Exhaustively searching a space this size to find a target this small is utterly beyond not only present computational capacities but also the computational capacities of the universe as we know it. Seth Lloyd (2002), for instance, has argued that 10¹²⁰ is the maximal number of bit operations that the known, observable universe could have performed throughout its entire multi-billion year history.

Dembski implicitly invokes uniform distribution in the above paragraph, but if you follow the link you will see that he explicitly invokes the concept for much of the paper, in addition to rambling on about searches and optimization problems (which we'll get to soon). But even setting aside the assumptions of computational searches, one doesn't have to assume that the space of proteins 100 amino acids in length is a uniformly distributed space of combinations. Biochemistry, like all chemistry, is not random but constrained by the physics underlying its operation. In addition, there is no reason to assume an exhaustive traversal of such a space is necessary at all. In evolution, what you want is a functional protein, which hardly requires an exhaustive evaluation of all possible forms that said protein can take.

The latter flaw alludes to our discussion of flaws in the equivalence drawn by Dembski between real world evolutionary biology and the various algorithms inspired by that process in solving optimization problems. His reasoning is fundamentally flawed on several levels.

Searching For an Accurate Analogy

Since the 2002 publication of No Free Lunch, Dembski has been harping on a particular invocation of optimization theoretic concepts. His claim is essentially that the results known as the No Free Lunch (NFL) theorems, originally derived by David Wolpert and William Macready, show that evolutionary processes do not perform better than randomness. The actual result of the NFL theorems is that given the task of optimizing (i.e., locating minima or maxima in) an arbitrary function f(x), the space of potential domains where any particular technique outperforms another is less than or equal to the potential domains where it does not. Thus, averaged over all possible domains, no optimization technique will ever be guaranteed to perform better than a random walk.

While the technical statement above may seem haughty, it can actually be understood as relatively mundane statement of mathematical reality. As Olle Haggastrom has pointed out in his own review of Dembski, an intuitive way of understanding the NFL theorems is through the following process: shuffle a deck of cards and spread them face down on a table. The NFL theorems are essentially another way of saying that, when completely ignorant of the structure or layout of the cards on the table, no sequential, deterministic process is guaranteed to find the ace of spades in fewer steps than randomly checking the cards manually.

Even assuming that evolution can be reasonably modeled as a search as considered by the NFL theorems, the analogy ignores one of the principal reasons that, despite the NFL results being well established, research in optimization theory is still incredibly lucrative. In most practical optimization problems, there is some degree of known structure than can be exploited to produce a useful optimization method. In the case of evolution, almost all scenarios involve existing templates and highly constrained criteria for selection (at least, more highly than randomness). For instance, in an environment where food is scarce, organisms that rely on the ubiquity of energy sources are almost automatically winnowed out. The environment is simply unfavorable to populations containing such organisms, weighting particular outcomes in favor of smaller, more resilient organisms.

It is also worth noting that the analogy between evolutionary algorithms and real world evolution is in a sense itself faulty. While evolutionary algorithms are usually specialized for optimization scenarios where a global optimum must be approximated, the results of real world evolution are far more analogous to what would be expected through traditional local search and hill-climbing methods. Biological and ecological scenarios only require a functional solutions, which in optimization theoretic terms can at best be described locally optimal. There is no necessity for a global optimum in biological evolution. While this doesn't in itself negate the applicability of NFL (this will become obvious in the next section), it does show that the two scenarios are not always as conceptually contiguous as it would seem.

However, the first flaw is far more instructive when stated in a more mathematical fashion. When uprooted it becomes obvious just how absurd Dembski's claims regarding NFL and real world evolution are.

Uniformity Revisited: Pure Noise

Olle Haggastrom provides us with this keen insight in a later reply to Dembski (with the latter being joined at the time by Robert Marks): the NFL is only applicable when the “Pure Noise” condition is met. “Pure Noise” stipulates that for each function f: V --\> S, each element v of V is chosen randomly according to uniform distribution on V, and each f(v) is chosen randomly according to uniform distribution on S. In search specific lingo, this is another way of saying that all permutations of an evaluation function are equally likely. The core assumption in both statements is that of pure randomness, under which it would be correct to say that no algorithm outperforms another.

The retort to Dembski is thus obvious, and one that often has been made to less sophisticated creationists: evolution is not randomness, and thus NFL is not applicable (at least no directly). But just to take the argument further, when taking Dembski's logic to its proper conclusion we would have to toss away more than simply evolution. The “Pure Noise” model is applicable to all algorithms designed to operate over search spaces, and evolution isn't the only natural process to inspire an algorithm of this sort. Two more that come to mind are simulated annealing, which simulates a thermodynamic system (more specifically, cooling and crystallization) and ACO, which simulates the behavior of ant-colonies.

In the most general form, simulated annealing used an initially high parameter T which gradually decreases upon successive evaluations of better solutions to an optimization problem. T here is usually used to represent temperature, and the goal of simulated annealing is to reach an abstract analogue of the “ground state” in a thermodynamic system (i.e., the global optimum). Its counterpart in local search problems is often called “rapid quenching”, an analogy to the fact that rapid cooling of crystals usually preserves irregularities in the structure (i.e., you only get a local optimum). Ant-Colony Optimization (ACO) uses simulated populations of ants which leave simulated pheromone trails to narrow down the space of feasible solutions (analogous to how real ant-colonies narrow down supply routes). If “Pure Noise” were satisfied in either case, you lose all structure. Temperature never decreases and pheromone trails never accumulate. Everything would “melt” in your simulated annealing algorithm, and your abstract ants would all lose their way and die in the absence of mutual support from the nest. Or, if we're considering all algorithms, it would seem that the universe has no structure whatsoever.

Behold, the power of unfounded assumptions.

Shermer Howler

2007-10-07T02:35:00.001-04:00

(Cross-Posted from PowerUp.)

Michael Shermer's latest column in Scientific American deals with artificial rankings of importance among the sciences from "hard" to "soft", and science writing from "technical" to "popular". I have to say I agree with the overall thesis that these rankings are rather artificial and not totally necessary. But that said, I don't agree with the way Shermer challenged the notion. When given the choice of how to do so, I can imagine two broad classes of options:

1. Make the modest, non-grandiose and largely accurate suggestion that the ranking system is flawed because all scientific knowledge is important and all disciplines deal with problems of varying complexity and difficulty; Or,

2. Propose a new ranking system that makes the extravagant, grandiose and gobsmackingly stupid claim to "precisely reverse" the order, making the social sciences the hard sciences and the physical sciences total weaksauce. (Giving lip-service to option #1 is also optional.)

Now to unveil Shermer's decision:

I have always thought that if there must be a rank order (which there mustn’t), the current one is precisely reversed. The physical sciences are hard, in the sense that calculating differential equations is difficult, for example. The variables within the causal net of the subject matter, however, are comparatively simple to constrain and test when contrasted with, say, computing the actions of organisms in an ecosystem or predicting the consequences of global climate change. Even the difficulty of constructing comprehensive models in the biological sciences pales in comparison to that of modeling the workings of human brains and societies. By these measures, the social sciences are the hard disciplines, because the subject matter is orders of magnitude more complex and multifaceted.

I'm sure that Blake and the rest of his physics friends will be glad to hear how “simple” constraining and testing a theory of quantum gravity is. But in the field of my pursuits, computer science, one would think it would be even easier. After all, physicists have to deal much more directly with the constraints of physical systems. We deal with abstract problems, abstract units of reduction and abstract models within which said problems are subordinated to feasible computations. Yet we still lack a rigorous proof that P != NP, that there exist one-way functions, or even that NP-complete problems would be approximately as hard for quantum computers as they are for classical computers. We don't even know how we would go about rigorously proving any of these assertions. Even the central principle of computer science, the Church-Turing thesis, lacks a rigorous axiomatization from which we could prove it, leaving it at least somewhat open to revision. A stronger version of the CT thesis, which posits that any Turing equivalent computing device generates the same problem classes as any other, is strongly called into question by the existence of polynomial-time quantum algorithms for factoring integers and solving various hidden subgroup problems (e.g., discrete logarithms).

“Simple”, indeed.

And not to nitpick, but Shermer's use of calculating differential equations as an example of a hard problem is in my mind exceedingly poor. You encounter differential equations by second semester calculus at the latest, so I would call them an intermediate topic. Or if I could have some wiggle-room, I'd call them a topic of varying difficulty. We still haven't proven the universality of Navier-Stokes in three dimensions, nor global regularity (e.g., no jumps of discontinuity) in the case that solutions in such dimensions always exist.

Dembski's Gremlin Theory of Induction

2007-10-05T00:43:00.000-04:00

(Foxy's latest here reminded me that this should have been cross-posted from PowerUp, but I forgot. Oh well, better late than never.)

Abbie has her latest post up describing her experience of Dembski. This is pretty much the first post in the series that has any relevance to my particular area of study (I'm not a biophreak, unlike most of those who post at ERV). You'll likely not be surprised that Dembski managed to bend over and fart out some pseudomathematical silliness before the day was done. But this pseudomath is extra special, as it doesn't even approach the level of coherence. Quoth Dembski (or ERV quoting Dembski):

Dembski-- Whe whe whe we can do a Bayesian analysis! Ahhh, your and my probabilities of a designer are very different. So it would be better to have a methodology that didnt require probabilities for a designer.

*audience laughs again*

Dembski-- Weh we can do a Bayesian sort of thing, given to me it is infinitesimally small I mean, you know, I mean... Here is a standard example.. weeh ehhh beyhh... we need to do this for the sake of the audience. Eeeh you hear some sound up in the attic, you know? Sounds like gremlins, ehh, bowling. Bowling. Gremlins bowling. Thats ahh, would be ahhh, you know, that would explain it. Eh eh, highly unlikely that you know. If there are gremlins up there, bowling, then that would explain the sound. But whats the prior likelihood of there being gremlins? Its highly improbable. So even though if there were gremlins it would explain that, the high improbability that there are gremlins means dont give that explanation a second thought. I think thats how the design hypothesis works for you. For others it doesnt work that way. Okay? So in a sense, if were going to decide this issue, its not going to be on the basis of assigning some sort of prior probability of design. You have to look at the actual improbabilities of this evolutionary system. The thing is, nobody that I see has been trying to do that sort of move. I mean, Richard Dawkins does not try to look at the prior improbability of god, hes trying to say "Look, its highly probable you get these systems because when you do the analysis, Darwinism is a strategy that can climb Mount Improbable", thats his whole point!

Okay, so he's doing a Bayesian analysis without assigning a prior probability to what is (presumably) the "design hypothesis". Let us recapitulate elementary statistics and probability. Here is Bayes rule.

Pr(H_i|D) = Pr(D|H_i)P(H_i)/Pr(D)

That P(H_i) thing in that little relation is known as the "prior" probability. It is typically understood as the probability of H_i being true before the observation of any data. The "posterior" probability, however, is the conditional probability Pr(H_i|D) of H_i being true after the observation of data set D. So you may find yourself wondering how the hell Dembski is doing a Bayesian analysis when the hypothesis he obviously favors (design) lacks the assignment of something fundamental to Bayesian analysis. ERV hit it in her post:

What I liked about this exchange is that it once again demonstrates that IDC is a negative argument. THEY dont have to provide probabilities of a designer. They just have to declare an evolutionary system impossible and declare victory.

It's what I and several other people have been saying all along about Dembski and his charlatanry. What he intends to do is eliminate other existing and mutually exclusive hypotheses so that he can assert that "design" is an alternative. If you take a course in logic, rhetoric and exposition, you'll learn that this little shuffle is known as an "argument from ignorance". In theological circles, the same tactic is known as a "god in the gaps" argument. Either way, it's an elementary fallacy. Unfortunately for the cause of reason Dembski has been able to make a career out of dressing this fallacy up to look like unimpeachable mathematics to the faithful.

I also find it funny that he tacitly admitted that the "designer" was comparable to gremlins. Funny little man, that Dembski.

Dembski Money Quote

2007-10-02T18:21:00.000-04:00

Bill Dembski is of course one of the guiding lights of intelligent design. Such as it is. And in a recent Q&A that ERV is reporting on, he let loose with this one comment that really, absolutely, I think, must be highlighted and shared with everyone. On discussing the probability of there being a designer versus the probability that we don't know everything, and how to weigh these probabilities, Dembski offered

So it would be better to have a methodology that didn't require probabilities for a designer.

...

Yes.

Fortunately Bill, we've got one all ready for you.

If these people refuse to listen to what they themselves are saying, I don't see why anyone listens to them at all.

A New Candidate for a One-Way Function

2007-09-23T14:33:00.000-04:00

(Cross-Posted at PowerUp)

One-way functions are one of the most interesting and perplexing phenomena in theoretical computer science. We haven't yet proven they exist, but we're pretty sure that they do on an empirical basis (in much the same way we believe, tentatively and on empirical grounds, that P != NP). Simply put, a one-way function is a function with an output for which a reversal is "hard", i.e., cannot be accomplished in polynomial time. If the existence of one-way functions were proven, we could analytically deduce that P != NP (because it would entail a problem that has no polynomial time solution, i.e, function reversal) as well as the existence of many "primitive" objects in cryptography. Current candidates for one-way functions include discrete logarithms, integer factorization and modular exponentiation.

Well, I believe I have discovered a new candidate for a one-way function. I call it "wishful thinking exponentiation", and it computes the increase in intellectual dishonesty that occurs when one attempts to synthesize religious pablum with science and mathematics. I consider it likely that this function is one way, since locating the preimage (sanity) is a problem for which I am unable to deduce a feasible solution.

For those curious about what I am talking about, look here. Jeffrey Shallit has done his part in dismantling a bit of religious and pseudomathematical silliness called "The Faith Equation", a book by a fellow named Marvin Bittinger. To see a sample of the idiocy, look at this pdf, where he spills a lot of pixels explaining a conditional probability model for the "fulfillment" of Biblical "prophecies". This is pretty much a classic case of the "argument from meaningless numbers". If you build enough unfounded assumptions into a probability model, you can get any desired result. This is however at the expense of your model having any capability to produce a quantity with any plausible analogue in reality. In this case, Bittinger appears to make the usual Christian apologist assumption that there are lots of fulfilled Biblical prophesies (and that these apparent fulfillments are not the product of retrofitting) and attach numbers to it, giving it that all important veneer of mathematical erdution.

Probability is a popular tool among pseudomathematical charlatans precisely because it is that easy to hide your assumptions and make it look like you are making meaningful statements when you have an audience without a sufficient background in the subject matter. We've long been familiar with Dembski's charades that purport to show "Intelligent Design" through codswallop such as "Specified Complexity", as well as classical creobot attempts with less refined pseudomathematical jargon. We can now add Bittinger to our list.

Why Knowing Sorting Algorithms is Still Useful: Broad-Phase Collision Detection

2007-09-20T15:16:00.000-04:00

(Cross Posted over at PowerUp.)

One of the most interesting things about programming is the ephemeral nature of the techniques used. Just look at languages, for instance; C falls out of favor to C++ and C#, functional languages take followers from object-oriented languages, procedural languages make a comeback because of their ability to reduce computational overhead, and on and on. These sorts of sifting sands are also quite visible in the world of algorithms. Ask just about any code monkey about sorting algorithms and they are likely to respond with something to the effect of "OMG U N00B, NO 1 WRITEZ SORTING ALGORITHMS ANY MOAR LOL!!!" Which is largely true, just about every language in widespread use (e.g., Java, C#, the C++ STL, etc.) incorporates native support for the most common sorting algorithms, saving you the trouble of actually writing them yourself.

Studying sorting algorithms in detail is often justified with the Knuthian philosophy that the best way to gain an appreciation of computations is to see them being implemented as close to the machine as possible. While I am myself a proponent of this philosophy, I have my own practical justification: knowing sorting algorithms is best for problems that require sorting "on the fly". An instance of such a problem lies in real-time physics simulation, i.e., broad-phase collision detection that uses "sort and sweep" methods.

Broad-phase collision detection (henceforth, BPCD) is the first part of most methods for collision detection (the other being, predictably, narrow-phase collision detection). The idea of BPCD is that you want to be able to exclude or "cull" objects from iterations of collision detection procedures to reduce overhead. So, essentially, you have a computational meataxe that hacks off those objects that have no realistic chance of colliding. Then narrow-phase collision detection does the dirty work with the remaining objects to find out which ones actually do collide.

Sort and sweep (henceforth, S&S) is one method for doing this. In the simplest form I can think of, S&S involves assigning "bounding volumes" to all objects in a scene and projecting them onto the x, y or z axis. One then assigns a one-dimensional interval [b_i, e_i] to each object that consists of the beginning and end of the bounding volume on the chosen axis. The values of each b_i and e_i are then inserted into a list of 2n elements and sorted into ascending order (based upon their value along the chosen axis). The entire list is then traversed, with each b_i leading to the object being included and each subsequent e_i leading to the object being excluded. The result of the algorithm is that only those objects with overlapping bounding volumes are included in the list of "active objects" for narrow-phase collision detection.

I can think of two very big reasons why an intricate knowledge of sorting algorithms would be very helpful in this area:

1. Collision detection on GPU's is attractive because the superior flop performance and data-parallelism of GPU's as opposed to CPU's (this is generally true of all forms of physics simulation, really). Using an S&S algorithm for BPCD on a GPU can take advantage of sorting networks due to the fact that they are, much like raytracing and scan-conversion, embarrassingly parallelizable processes. This could have many applications to collision detection in larger scenes, perhaps with the added benefit of some means of interpolation for approximately similar comparisons in the sorting network.

2. External sorting algorithms, originally invented for scenarios in which input and output targets for sorted data exceeded the internal memory of the system doing the sorting, could possibly have some applications for overcoming bandwidth limitation in sharing data between the CPU and the GPU. CPU's are still inherently superior devices for handling AI, game logic and other procedures that involve a large amount of branching logic. The problem is that the BUS capacity is not increasing at the same rate as either GPU's or CPU's are, leading to scenarios in which the conduit for data is dwarfed by the input and output targets. Whereas you'd have entire lists of collision data to be fed to the AI engine, for scenes exceeding BUS capacity it may be an attractive option to generate "runs" of data and merge them in caches (e.g., in either system memory or video memory for the CPU and GPU, respectively).

Just a few ideas.

Centroidal Nonsense: Purple Haze

2007-09-20T00:32:00.000-04:00

So ...

... I've been busy ...

Anyway.

Take a set of points. Jumping in for a little random Mathematica-ness, we get

{19, 24, 32, 42, 55, 63, 69, 75, 85, 99}

What we're interested in is the one number that is closest to all those numbers.

Intuitively, you may suggest the average of those numbers. The average, being right in the middle, should be as close as possible to all the numbers right?

The average is 56.3. If we take the sum of the absolute value of the differences between 56.3 and the numbers, we get that the 'total distance' is 219. Check that. So, we want to know if we can do better than that.

To begin with, let's look at a plot of, given a value x, the 'total distance' of the set to x. The points were chosen from 0 to 100, so we're really only interested over that interval. The entire plot appears below.

Notice that the plot has a clear minimum, which occurs somewhere between 50 and 70. So we replot, looking more at that section. Notice though the apparent linearity of the graph right there, seeming to suggest a range of solutions.

Now we get a better idea of what's going on. The line across the bottom seems to represent a clear minimum. Notice however that it seems to occur in a line from 55 to 63. The average, 56.3 falls right in this range, suggesting that 219 is in fact the minimum value. But the line, going from 55 to 63, suggests that any value on that range would've produced the same distance of 219. Indeed, if we look at the 'total distance' of 60, it also produces 219.

Now, there are two things of note here. Number one, the predicted distance minimizing point, the average, did produce the minimum distance. Is that always the case? Secondly, the minimizing values occurred between 55 and 63. Note that 55 and 63 are the two middle values of our set of numbers. Suppose we change the set of numbers to

{1, 2, 3, 42, 55, 63, 69, 75, 85, 99}

That shifts the average to 49.4, which gives a 'total distance' of 299.2. Notice though, that the 'middle two' numbers, 55 and 63 haven't changed. If we look at a plot of the new distance function for this new set of numbers,

Notice the minimum distance still occurs from 55 to 63. Selecting 60 as a trial number again, we get 288 as the minimum distance, which certainly beats 299.2.

So it seems that, at least given an even number of numbers, the distance minimizing points occur on a range between the middle two. If we think about this, discarding our original intuition about the average, it should make sense, since between those two points, moving left or right will increase the distance to all the points on one side the same amount it decreases the distance to the points on the other side.

For the case of an odd number of numbers, the distance minimizing point should be the middle number itself. Were that number not included, we know that the distance minimizing point of the resulting even numbered set would be between the two 'middle points'. The middle number of the odd set occurs between those two, so it is a minimizing value of the smaller set. If we choose it, the distance to itself is 0, so it doesn't contribute anything more. Taking our set of numbers from above and adding 60 as a middle number, we plot the new distance function.

So the middle point is now exactly at 60, which is the middle value of the set.

So now we have an approach for the one dimensional case. Tomorrow, if I have time, I'm going to try to expand this into the two dimensional case, which should allow a solution to be constructed for points in any dimension. It's all experimental though, so we'll see what happens.

Late now though. More tomorrow, if I'm lucky.

Fibonacci, You Complete Me

2007-08-26T14:34:00.001-04:00

Suppose you have a sequence of values, a₀, a₁, a₂, a₃, ... so on. That sequence is thought of as 'complete', if any positive integer can be expressed as the sum of unique members of that sequence.

For example, let's consider the set of Fibonacci numbers.

1, 2, 3, 5, 8, 13, 21, ....

And so on. Taking 42, for example, we can write that as a sum of Fibonacci numbers.

42 = 21 + 13 + 8

Note that each Fibonacci number used in the sum is used only once. The question then is whether or not the Fibonacci set is complete. Can all positive integers be expressed as a Fibonacci sum?

So, let's consider a number N. We'll assume it is expressible as the sum of some number of Fibonacci numbers. Now, look at the used Fibonacci numbers, from greatest to least. Any time a pair of consecutive Fibonacci numbers occurs, we will substitute in their sum, which is also a Fibonacci number. And we go down the line of the sum for N, replacing all Fibonacci pairs (from greatest to least), with the next Fibonacci number. We do this until there are no more pairs left in the sum. Now, in doing so, we have transformed one sum of Fibonacci numbers into a sum of different Fibonacci numbers, but the value the numbers sum to remains the same, N. Also of note is the fact that doing it this way, pairs from greatest to least, removes the possibility of using the same Fibonacci number twice. Imagine if the sum included 21, 13, and 8, all consecutive Fibonacci numbers. Replacing pairs from greatest to least, 21 + 13 + 8 = 34 + 8. Replacing pairs from least to greatest would give you 21 + 21. From greatest to least removes the possibility of overlap.

Now, we have N as the sum of some number of Fibonacci numbers, none of which are consecutive pairs. Now, there are two cases to consider. In the first case, the Fibonacci numbers that sum to N includes the number 1. In that case, we know that the numbers can't include 2. If they did, then {1,2} would be a pair, and we know that the Fibonacci numbers are pair-less. So if the sum for N contains 1, then it does not contain 2. In that case, we can express N+1 as the sum of Fibonacci numbers, by taking 1 away from the sum for N, and replacing it with 2.

In the second case, the sum for N does not contain 1. In that case, we can construct a sum of Fibonacci number for N+1 by merely adding 1 to the sum.

So, if there exists a Fibonacci sum that sums to N, we can construct a Fibonacci sum that sums to N+1. Since there exists a Fibonacci sum for 1 (namely 1 = 1), this implies there exist sums for all positive integers. Therefore the set of Fibonacci numbers is complete.

Not the most glamorous or well written of proofs, but I think it works : )

I'll leave it to the interested reader to prove the set of powers of 2 is complete.

What the Hand Dare Seize the Fire?

2007-08-21T13:13:00.000-04:00

Sometimes, I'm afraid I'm not a good blogger, as much as I hate that word. Afraid is probably the wrong word, but at the very least, I often ignore comments. Don't take that the wrong way, I just often don't know what to say ^.^

But, a couple of times now, I've been asked how I do LaTeX on blogger. Tyler showed me this one. If you're running Firefox, install the add-on Greasemonkey. Then install this guy's script. In Blogger, in the 'Compose' frame, you then get a new button that says 'LaTeX'. Clicking on that then auto converts any LaTeX expressions into properly formatted ... whatevers.

$$ \sqrt{2 + \sqrt{2 + \sqrt{2 + ... \sqrt{2} } } } $$

Becomes

Of course, if this fellow's script ever goes down, I will lose a large portion of the work I've done here. Oh well. Nothing gold can stay.

Other programs I use include, of course, Mathematica. Mathematica is an excellent program for anyone serious about mathematics. Seriously - it's awesome. The only problem is it's a little pricey. Registered students can get it for $150 (I think, it's been a while since I checked), but the non-student version costs $2500. This is going to make me impossibly sad in a few years. They're currently at Mathematica 6, which definitely has it's perks, especially in the graphics department. For example, you can rotate 3D plots with your mouse, while you can't in 5.2. Generally though, I think I prefer the feel of 5.2 Mathematica, though, is simply fantastic.

Here's something nice I stole from the helpfile on Mathematica 6.

ParametricPlot3D[ {Sin[u] Sin[v] + 0.05 Cos[20 v],
Cos[u] Sin[v] + 0.05 Cos[20 u], Cos[v]}, {u, -Pi, Pi}, {v, -Pi, Pi},
MaxRecursion -> 4, PlotStyle -> {Orange, Specularity[White, 10]},
Axes -> None, Mesh -> None]

Producing

Something else that has been of special use lately is the Geometer's Sketchpad. It's basically a program that let's you do geometric constructions. And I do enjoy my geometric constructions. This is the program I used to illustrate van Aubel's theorem, and here's a quick sketch of a triangle's circumcenter. Like, 10 steps total.

One of the nice things about this program is that it's dynamic. You can, for example, grab one of the points and drag it around, and watch how the changing position effects the whole construction. In the case of van Aubel, you can watch how changing the quadrilateral has no effect on the perpendicular segments of interest. It really demonstrates the flexibility of the theorem, which was verified in the proof. This program is also a little pricey, at 130$ for the regular version. However, according to the website, students can get it for $40 dollars. I got it for free about 6 years ago (a kind geometry teacher in a summer school program). So I'm running version 3.0 while they're up to 4.07.

Other than those, a lot of what I do I just program for myself. Graphics I do especially in Java, because Java just makes it so easy, as much as I hate the stupid language. For my Java work, I'm generally partying in Eclipse. Other languages I use include C++ and Ruby. Ruby is nice, I feel, because it's quick and fun and readable. C++ is for the heavy duty stuff, mainly the data-intensive jobs. Fortunately I don't do those often.

Of course, actually looking at all this stuff, it can be quite an investment unless you're lucky or a pirate (Arr!). Looking for open source (read -free-) alternatives, I came across this list of computer algebra systems. Of them, the most Mathematica-esque seems to be
Maxima, though Axiom seems quite exciting as well. I'll have to investigate those.

Anyway, back to work now. Leaving in a few days, so I have to pack up my main computer and ship it back. This will impede me a little, but I hope to have at least one interesting math post before I go. Probably a geometry post. And, with any luck, Dean won't be a problem.

Soddy Sequence Properties

2007-08-19T04:15:00.000-04:00

That is an exciting title.

I'm not exactly sure where to begin with this post. So ... I'll start with numbers of the following form.

Such that a and b are integers. Note though, that I've used root 2 rather than any other root because root 2 is best. Not the nicest of expressions. However, for some values of a and b, you can transform that expression into the following form.

Where A and B are functions of a and b. For example, you have the following.

If we take that in the general case, and assume a, b, A, and B are integers, we can do the following.

Collecting then gives you

Solving those two equations for A and B yields some nasty nested roots, which don't necessarily help anything. However, if anything, the equation does tell is that, assuming all integers as we did, a must be positive. Note that the integer assumption is valid, because in the case of fractions we could simply add a coefficient to each side of the equations sufficient for canceling out denominators. So, integers suffice.

What these equations do allow us to do, though, is to get an idea of how many nested root expressions there are. For example, consider every combination of A and B, over the values 1, 2, and 3. Applying the formula above, we get

Producing a maximum value of 27 for a and 18 for b. This means that of 27*18, or 486 possible pairs of a and b, only 9 of which are reducible in form. It should be clear then that only a tiny fraction of all nested root expressions will be reducible in this way.

So ... it's a rare thing. Interestingly so.

Now, take the following recursive formula.

Generating the first couple of values of that function and simplifying them with Mathematica, we get the following.

And so on. But, this is the cool part. If you continue on down the sequence, every single value I've calculated has the form . Every one of them. Now, we'll assume that the previous term has that form, and calculate the next term in the sequence. Simplifying, we get

Now, it is a bit messy, but the important think is that big nested root in the denominator. To reduce the whole expression into something of the form we're looking for, that nested root will have to be simplified as well. However, there is nothing about that formula that lends itself to simplification. For some values of A and B, it can't be simplified that way. So, the question is, what is it about the sequence, as it is defined, that seems to guarantee that each term will not contain a nested root?

I think it's an interesting problem, but I'm not sure.

Taking a Hiatus From Blogging

2007-08-17T06:31:00.000-04:00

I have to take a break from blogging. As is usual for someone in my position, the end of summer has dumped a shitload of work onto my plate at once. I'm going to be very busy in meat space in the coming weeks, and won't have much time for quality updates anyway. So I figure that instead of constantly dumping filler into these spaces (my personal blog and TaFSaMAL, whichever you're reading) I'll just give a notice of absence and leave Foxy to do what he wishes with his posting privileges in the meantime.

Of course, I'm not going to make the same stupid mistake I made the last time I got overwhelmed with work and delete my blog(s) altogether. I have the foresight now to know I can't say away from the blogging scene forever, and the best case scenario is that I'll be back in around a month and a half. I'll probably also have time for occasional comments as well.

Until then, have yourselves a good summer/fall transition.

Evolution and Mathematics

2007-08-12T18:10:00.000-04:00

Having followed the "homepage" link left by a commenter by the name of "Jon" I came across this interesting post on the intrinsic-nature of mathematics (or rather the lack of it). An interesting point of his:

Certainly some things are entirely invented, such as notation and other things. But my position is a more evolutionary one. Consider a simple bacterium wandering on a two-dimensional substrate. It doesn’t really have any need for cognizance of the larger three-dimensional world because its motility is limited to that substrate. (And by cognizance I don’t mean consciousness, I just mean its ability to interact with its environment). And so, evolution plunks away giving the bacteria only what it needs to survive and reproduce. It may give it a way to sense the direction of polarized light, or a way to sense the chemicals of would-be competitors, or other beneficial attributes.

......

So my point is, mathematics really is intrinsic to how we work, because our brains obviously utilize it at some level. But the caveat to that is that this mathematics is still just an approximation. It’s the best solution given finite resources that evolution has provided to us. Like the bacterium, we, being three-dimensional creatures, only need a certain kind of software to operate in that three-dimensional world. So when I say mathematics isn’t intrinsic to the universe, I’m saying that the logical system that evolution provided to our brains to preform those subconscious computations is one based upon the trials and errors of our ancestors.

In essence I agree. Mathematics as a form of symbolic reasoning about the universe of course isn't intrinsic to it. This is why I generally think that the Platonist/Nominalist dichotomy in metamathematics is pretty useless. We invent mathematical concepts to solve some given problem that corresponds to intrinsic properties of the universe. Think of things like "dimensionality". Of course, certain things are more contrived than others, but they are all a means of quantifying some aspect of something or other.

One interesting question is why we envision mathematics the way we do in the first place. While we're all familiar with the questions of mathematics, the main way we think about those questions is algebraic. We generalize mathematical objects in terms of classes, subclasses, groups, fields, Galois extensions, etc. I remember Roger Penrose (I think) once chose to speculate on how an alien race evolving in different conditions would find some different way to be "mathematical". Could you understand those same algebraic truths in a more combinatorial fashion, for instance? Maybe there is something we simply aren't familiar with.

Radiance Caching: A Technique for Rendering Fog

2007-08-12T16:21:00.000-04:00

I just happened across this intriguing story in Science Daily about a new computational technique for rendering smoke and fog in real time. Doing so is one of those instances where it would seem that the amount of vector data you'd have to compute to render the scene, particularly for how the lighting reflects off the fog/smoke, was pretty much intractable. Typically fog and smoke scenes are rendered using minimal lighting data and instead using occlusion culling to approximate the visibility limitations induced by the fog/smoke. What some researchers at UC San Diego came up with, however, was a caching technique that allows you to compute a small amount of vector data for one point in the scene, and then interpolate that data into the surrounding area to save resources. That way, the vector data for how the light interacts with the fog doesn't have to be computed for all members of a set of fine, granular points in the scene. Some quotes from the story:

“This is a huge computational savings. It lets you render explosions, smoke, and the architectural lighting design in the presence these kinds of visual effects much faster,” said Wojciech Jarosz, the UC San Diego computer science Ph.D. candidate who led the study.

Today, rendering realistic computer generated images with smoke, fog, clouds or other “participating media” (some of the light is actually absorbed or reflected by the material, thus the term “participating”) generally requires a lot of computational heavy lifting, time or both.

......

With some existing computer graphics approaches, the system has to compute the lighting at every point along the smoky line of sight between your eyes and the person at the bar – and this leads to computational bottlenecks. The new approach from Wojciech Jarosz and colleagues from the UCSD Computer Science and Engineering Department of the Jacobs School avoids this problem by taking computational short cuts. Jarosz’s method, called “radiance caching,” makes it easier to actually create realistic images of smoky bars and other images where some material hanging in the air interacts with the light.

With the new approach, when smoke, clouds, fog or other participating media vary smoothly across a scene, you can compute the lighting accurately at a small set of locations and then use that information to interpolate the lighting at nearby points. This approach, which is an extension of “irradiance caching,” cuts the number of computations along the line of sight that need to be done to render an image.

Very interesting. I'll definitely have to see if I can get my hands on the technical write ups of the SIGGRAPH conference where they present this thing.

At the same time, it all kind of pisses me off. A while back I had some ideas floating around of a means of rendering water caustics. Water caustics are similar to fog and smoke in this instance, as the amount of vector-data for how the light interacts with the water to produce those pretty reflexive effects is usually astoundingly complex. The first idea I had was to find a way to interpolate a small amount of cached or otherwise precomputed data to save some time. What I figured was that I could store topological k-adjacency data in a decque-like data structure through vertex/fragment shaders in GLSL. That way I figured I could pull out smaller values from one end and larger values from the other as necessary. I never finished developing the idea (hell, I never even really developed it that far), but maybe I was onto something.

More Geometry from the Foxen

2007-08-11T18:20:00.000-04:00

So, with as little to do as I do do, I frequently find myself making use of the Random Maths script at Mathworld, and perusing varied and interesting maths. One of the problems with Mathworld though is that it frequently presents things as fact, with little to no indication of the proof or method of proof, as is the case with their page on van Aubel's Theorem.

van Aubel's Theorem concerns the diagram below.

Given a random quadrilateral abcd, draw squares on all four sides of the figure. Connecting the centers of opposite squares, as done above, you produce two segments, BC and AD. van Aubel's theorem says that BC and AD will always be of equal length and perpendicular to each other.

To prove this, you can do some neat things with complex numbers. For example, you can represent any point on a plane as a complex number. So the complex number b = x + i*y could be taken as the point (x,y). Using complex numbers in this way, you can use them as substitute vectors. Rotations also becomes very easy. For example, if you multiply a number by i, b*i for example, you get -y + i*x. This is a 90 degree counter clockwise rotation of the original number around the origin. So take the number 1. That can be viewed as the vector {1, 0}. Multiplying by i, you get i, which can be thought of as the vector {0, 1}. {0, 1} is a 90 degree rotation of {1,0}. And of course, when something is rotated, it maintains its original length. Keep that in mind.

So, instead of points in the diagram above, imagine four random complex numbers, a, b, c, and d. In the case of a and b, the segment between them can be thought of b - a, a complex number pointing from a towards b. We can then represent the midpoint of segment ab as

The addition of (b - a)/2 shifts a half way in the direction of b. What we want is the value of A, the center of that square. So, having gone halfway down the side of the square, we want to move into the square by the same amount. Multiplying (b - a)/2 by i, we get an imaginary number of the same length, rotated 90 degrees counter clockwise to the original direction we moved. Adding that will peg us right in the middle of the square. Thus we get, in the diagram above,

Applying that same formula on all four sides, we get the positions of all the centers of the squares.

Now, the theorem says that AC and DB are equal in length, and at 90 degrees to each other. This is the same as saying that one is a 90 degree rotation of the other. If that is true, then (B - D) is a rotation of (C - A), which means that

And to prove that, just start substituting.

And, as you can see, the same terms exist on each side, and the equation reduces to 0 = 0, true, verifying that one is the rotation of the other. Which in turn verifies that they are at 90 degrees to each other, and that they are of equal length. And because a, b, c, and d were general complex numbers, the same applies to any quadrilateral on the plane.

Neat things, complex numbers. I am a fan.

Soddy Circle Derivation

2007-08-08T19:10:00.001-04:00

Today we concern ourselves with the image below.

We have three main circles, all tangent to each other, forming a sort of triangle thing. Now, for any three circles in that configuration, there is one circle that can be placed on the inside of the three, tangent to each, and one on the outside tangent to each.

The question then is what are the radii of those circles in terms of the radii of the three original circles? One tool we'll need is the Law of Cosines. Consider the triangle below,

The Law of Cosines gives us the following

So, consider this.

This is a closeup of the inner circle, with a triangle drawn through the centers of the three circles, and segments from the centers of those circles to the center of the inner Soddy circle. The radii of the circles are labeled a, b, and c. The radius of the inner circle I've attempted to label x. Now, the three segments from the vertexes of the triangle to the center triangle divide the circle into 3 arcs, which I've labeled A, B, and C.

So, the main triangle is divided up into three obtuse triangles, with obtuse angles of A, B, and C. Applying the Law of Cosines to each triangle there, we get the following.

We want to solve for x. Note too that we also have the fact that , thinking in radians. So, one approach would be to solve each of the LoC equations for A, B, and C, and then set the sum of those to 2 pi. The problem with this is that, in solving for A, B, and C, you'd be taking the ArcCos of huge expressions in terms of x, and then manipulating the sum of several ArcCos values. ArcCos is difficult to manipulate algebraically, which makes that route overly complicated, and not likely to bear anything useful.

A better approach would be to solve for the cosine values themselves, and try to manipulate those into something useful.

So, let's think about Cos(A), Cos(B), Cos(C), and . Suppose we solve for A, , and take the cosine of that? We need to make use of an identity I don't think I'll justify for now,

We take that and run with it.

We're getting there. We now have Cos(A) completely in terms of trigonometric values of B and C. However, we aren't out of the woods yet. What we have is in terms of the sine of B and C as well. But, with the trigonometric identity , we can do the following.

Now we have one equation, strictly in terms of the cosine values of the angle, which is what we know. I'll spare you a lot of the algebraic manipulations, but plugging the cosine values we have in and simplifying somewhat for a first step, we get

Dropping all the common denominators and things, expanding and simplifying and grouping, we can change that to the following.

Now, we want to solve for x. x = -a is a solution to the above equation, due to the far left factor. But it is clearly not a useful solution, as the radius of the inner circle is much smaller than any of the three circles. So we can just toss that factor, as well as the negative sign, leaving a simple quadratic equation. Well ... simple is relative.

At this point it should be noted that one of the reasons I'm skipping so many steps and not showing all my work is that the expressions involved are too large to conveniently displayed within the bounds of this website. Nevertheless, using the traditional quadratic formula and simplifying, we get the following.

And that's pretty much it. Everything else is just simplification.

And there you have it. Plugging in the radii of the three circles will give you the radius of the inner circle. However, notice that there are two solutions for x, depending on whether you do plus or minus the root on bottom. Remarkably, while one solution is the radius of the inner circle, the other solution is the radius of the outer circle. I say remarkable because I cannot justify the geometry of it, but there is no doubt a straightforward explanation for it. But as I think this post has established, my geometric intuition is rather stunted. From what I can make out, the positive root on the bottom leads to the inner circle radius, and the negative root leads to the outer circle radius.

Just to strip things down as much as possible, I like to recombine that solution into a single equation that doesn't have messy plus-minuses.

Which you can take as a general Soddy equation, the same equation I posted last night.

Well ... I found it exciting, anyway : )

Soddy

2007-08-08T03:29:00.000-04:00

An interesting equation, the derivation of which was quite exciting. This is to encourage me to write it up on the morrow.

Don't Support the ESA

2007-08-07T14:29:00.000-04:00

Last week came some disturbing news about raids conducted by the ICE against sellers of mod chips. 32 places in 16 states were targeted for selling devices used to modify video game consoles. Now, you'd think that personal modification of a device bought legitimately on the free market would easily fall under fair use, especially when the purposes of such modifications include the ability to use import games (which are unfairly locked by regional codes) and expanding the functionality of the device (such as the ability to use it as a media center). Think again. You can't use them because such devices can potentially be used in the act of piracy. At least, that's what the ESA thinks:

“Plain and simple, selling and distributing products to illegally bypass game consoles’ piracy protections is a crime with real-life consequences. This is not a game; we’re talking jail time. Enforcement initiatives of this scope send a clear message to both the public and pirate community that this illegal activity will not be tolerated," said Michael D. Gallagher, president of ESA, the trade association representing U.S. computer and video game publishers. "We commend Immigration and Customs Enforcement (ICE), the U.S. Department of Justice, and the participating U.S. Attorneys’ offices for targeting individuals and groups selling ‘mod-chips’ and pirated game software.”

Never mind that making backup copies of games is a perfectly legal activity and those that wish to modify their consoles so as to be capable of doing so would also be engaging in a legitimate instance of fair use. No way, we must be able to stop the use of such devices in toto because they can potentially be used in some nominally illegal activity. Next up, we shall lobby for legislation banning the sale and/or use of soldering irons used to install the chips (can't take any chances).

Folks, honestly, you really do have to worry about this sort of odious action. What's happening is our government, despite a myriad of legitimate "Homeland Security" measures it could be taking, using violence against it's own citizenry on behalf of the corporate establishment. That is the very definition of fascism. Those who assured us that we wouldn't have to worry about the DMCA and it's effective squashing of fair use rights should be eating a lot of crow about now.

But the most important thing is that gamers all across America should know that the ESA is not their friend in any way, shape or form. Thus they should in no way lend their support to the organization. Simply put, they are propping up the obsolete legal construct of "copyright" and exploiting it for the creation of a protection racket, and are doing so no less than other big media fronts like the MPAA and the RIAA. They have no interest in protecting the rights and civil liberties of their customers. There are many other organizations out there that fight for consumers rights and software freedom, such as the Electronic Frontier Foundation, The Center for Digital Democracy and the Free Software Foundation. Corporate lobbying organizations don't deserve our support merely because of our nominal agreement on issues pertaining to the regulation of game content.

IFS Source Code

2007-08-07T02:11:00.000-04:00

import java.awt.Color;
import java.awt.Graphics2D;
import java.awt.RenderingHints;
import java.awt.image.BufferedImage;
import java.io.BufferedOutputStream;
import java.io.FileOutputStream;

import com.sun.image.codec.jpeg.JPEGCodec;
import com.sun.image.codec.jpeg.JPEGEncodeParam;
import com.sun.image.codec.jpeg.JPEGImageEncoder;
// Necessary and vital packages for image manipulation
// The body of code relating to image manipulation in
// this program I merely jacked from
// http://schmidt.devlib.org/java/image-faq/example-image-io-code.html
// Very nice site

public class IFSD2
{
public static void main(String[] banana) throws Exception
{
int width = 500, height = 500;
double xmin = -0.75, xmax = 0.75, ymin = -0.75, ymax = 0.75;
double dx = (xmax - xmin)/width, dy = (ymax - ymin)/height;
// Various things, width and height of image to be saved
// The range over which the system will be graphed
// dx and dy are useful for computing pixel locations from point values
// on the graphed plane

String fileName = "RandomFractal.jpg";
int points = 5000000;
// Name to be saved under, points to be plotted

BufferedImage newImage = new BufferedImage(width, height, BufferedImage.TYPE_INT_RGB);
// Create a new image with the specified dimensions
// and colour encoding

Graphics2D graphics2D = newImage.createGraphics();
// the graphics object is what you use to actually draw
// on the image

graphics2D.setRenderingHint(RenderingHints.KEY_INTERPOLATION, RenderingHints.VALUE_INTERPOLATION_BILINEAR);
// No idea what this does, but it seems important

graphics2D.setColor(Color.white);
graphics2D.fillRect(0, 0, width, height);
graphics2D.setColor(Color.black);
// This, in order, sets the paint colour to white
// whites out the body of the image, and then
// resets the color to black

double px = 0, py = 0, nx, ny;
// the current point of the system will be
// saved in (px, py). The default is that
// you always start at (0,0)

double p1a = r(), p1b = r(), p1c = r(), p1d = r(), p1e = r(), p1f = r();
double p1g = r(), p1h = r(), p1i = r(), p1j = r(), p1k = r(), p1l = r();

double p2a = r(), p2b = r(), p2c = r(), p2d = r(), p2e = r(), p2f = r();
double p2g = r(), p2h = r(), p2i = r(), p2j = r(), p2k = r(), p2l = r();

double p3a = r(), p3b = r(), p3c = r(), p3d = r(), p3e = r(), p3f = r();
double p3g = r(), p3h = r(), p3i = r(), p3j = r(), p3k = r(), p3l = r();

double p4a = r(), p4b = r(), p4c = r(), p4d = r(), p4e = r(), p4f = r();
double p4g = r(), p4h = r(), p4i = r(), p4j = r(), p4k = r(), p4l = r();

// For this IFS, I'm using 4 sets of rules of the form
// xnew = a*x^2 + b*x*y + c*y^2 + d*x + e*y + f
// ynew = g*x^2 + h*x*y + i*y^2 + j*x + k*y + l
// This generates as many necessary coefficients with random
// values, as defined by the function r(). Of course, in a
// pinch, you can make these linear by setting a, b, c, g, h, i
// in each case to 0. And you can do a specific IFS by
// specifying the coefficients you need.

int x, y;

double mark;

// Loops the specified number of times to
// plot that many points
for(int i = 0; i < points; i++)
{
x = (int)((px - xmin)/dx);
y = (int)((py - ymin)/dy);
// x and y hold the pixel location on the image file
// calculated from the point values

graphics2D.drawLine(x, y, x, y);
// this draws a single black dot at that location

mark = Math.random();
// select a random number between 0 and 1
// for choosing which rule to use

nx = px; ny = py;
// store the point values to temporary variables

// depending on the value of mark, between 0 and 1,
// one of the four rules is selected to calculate
// the new point value. Note that each rule has
// an equal probability of being chosen. You can
// change that as you see fit.
if( mark <= 0.25 )
{
px = (p1a)*nx*nx + (p1b)*nx*ny + (p1c)*ny*ny + (p1d)*nx + (p1e)*ny + (p1f);
py = (p1g)*nx*nx + (p1h)*nx*ny + (p1i)*ny*ny + (p1j)*nx + (p1k)*ny + (p1l);
}
else if( mark <= 0.50 )
{
px = (p2a)*nx*nx + (p2b)*nx*ny + (p2c)*ny*ny + (p2d)*nx + (p2e)*ny + (p2f);
py = (p2g)*nx*nx + (p2h)*nx*ny + (p2i)*ny*ny + (p2j)*nx + (p2k)*ny + (p2l);
}
else if( mark <= 0.75 )
{
px = (p3a)*nx*nx + (p3b)*nx*ny + (p3c)*ny*ny + (p3d)*nx + (p3e)*ny + (p3f);
py = (p3g)*nx*nx + (p3h)*nx*ny + (p3i)*ny*ny + (p3j)*nx + (p3k)*ny + (p3l);
}
else
{
px = (p4a)*nx*nx + (p4b)*nx*ny + (p4c)*ny*ny + (p4d)*nx + (p4e)*ny + (p4f);
py = (p4g)*nx*nx + (p4h)*nx*ny + (p4i)*ny*ny + (p4j)*nx + (p4k)*ny + (p4l);
}
}

// Everything below merely writes the image object to a file and saves it
BufferedOutputStream out = new BufferedOutputStream(new FileOutputStream(fileName));
JPEGImageEncoder encoder = JPEGCodec.createJPEGEncoder(out);
JPEGEncodeParam param = encoder.getDefaultJPEGEncodeParam(newImage);
param.setQuality(1.0f, false);
encoder.setJPEGEncodeParam(param);
encoder.encode(newImage);
out.close();
System.out.println("DONE");
System.exit(0);
}

public static double r(){ return (2*Math.random() - 1)/2; }
// Math.random() returns a random number between 0 and 1
// 2*Math.random() returns a random number between 0 and 2
// 2*Math.random() - 1 returns a random number between -1 and 1
// And I divide by 2 to give a range between -0.5 and 0.5 for all
// coefficients. This generally prevents the system from
// running too far off the range of the graph.
}

Mixing Number Theories

2007-08-06T14:41:00.000-04:00

One of my favourite algorithms of all time is probably the Euclidean Algorithm. I've discussed this algorithm a few times before. It's excellent. Unlike Euler's Algorithm, which is horrible.

Basically, it's a method for finding the greatest common divisor of two numbers. Take two numbers, for example 42 and 28. Divide one by the other and take the remainder. Toss the larger number, and keep the remainder. And repeat until the remainder is 0.

42 = 1*28 + 14

28 = 2*14 + 0

When you reach a remainder of 0, whatever number you divided by last is your greatest common divisor. So 14 is the GCD of 42 and 28. Seeing as 42 = 14*3 and 28 = 14*2, that is clearly correct.

So, very slick, very fast. Easy to implement.

An interesting historical note though, and I don't recall where I learned this, is that in his Elements, Euclid expressed this algorithm in terms of subtraction of line segments. In this case here, imagine you have a line segment of length 42, and a line segment of length 28. You take away the shorter length from the longer, until you can't anymore. Consider instead here ... 42 and 38. You keep taking shorter lengths from longer lengths until you reach 0. The last length is the greatest common divisor.

42 - 38 = 4

38 - 4 = 34
34 - 4 = 30
...
10 - 4 = 6
6 - 4 = 2

4 - 2 = 2
2 - 2 = 0

So the GCD of 42 and 38 is 2. And this was computed 'geometrically' for lack of a better word. I find that interesting.

I only bring this up because it's always struck me that Euclid's Algorithm, in the geometric sense, is of limited use, because of the difficulty of achieving exact integer length segments in reality. Mathematical abstractions of it are nice, but in practicality ... *shrug*

Which of course leads me to wonder, what happens if you weren't to use integer lengths? That is, if you were to perform the algorithm on non-integer values. Now, it strikes me as obvious that if there is an exact whole number ratio between your values, even if they are non-integers, you have no issues. For example, consider 3/5 and 7/5. Neither are integer values, but you might as well just consider them as 3 and 7. But what if there is no whole number ratio? What results?

So, let's consider 1 and .

Since root 2 is the larger value, we subtract 1 from root 2 until the result is smaller than 1.

That took one subtraction. Now that we have a value smaller than 1, we subtract that value from 1 until we get an even smaller value. While the value we have now is 0.414214..., I'm going to use the exact form, for convenience.

And with two subtractions, we now have a new smaller value.

And again, we drop our largest value, 1, and take this new value. And we start subtracting again.

Two subtractions, and we have our smaller value again.

Now, if you continue in this vein, you'll find that each new step takes two subtractions, producing a smaller value each time. I should probably prove that. One can well imagine that you'd take two subtractions each time until the new value reduced down to 0, well far in the future. Looking at the number of subtractions we've produced at each step, that would give 1, 2, 2, 2, 2... so on. This by itself is an interesting result, which I think will probably explain in a moment.

But what is it we're doing really?

We have a sequence of numbers.

Let's call this sequence of numbers C_n, so C₀ = , and so on. Notice that because of the way we're computing C_n, as n increases, C_n must approach 0. Notice too that all C_n are positive. Because of that pattern we had, subtracting twice one number from the previous to get the next, we get the formula

It gets a little funky at first, because the first subtraction just occurs once, but as every subtraction after occurs twice, that pattern is established.

Next, imagine two sequences of integers, A_n and B_n. And we'll say that the following equation always holds.

Looking at it that way, C_n is the sequence, in order, of positive linear combinations of 1 and root 2.

Now, remember that as n increases, C_n goes to 0. This means that, at some distant future, we effectively have

Manipulating, that gives us, as n increases

So if we can determine the sequences A_n and B_n, the limit of the ratio of those two values is the square root of 2.

Neat.

So, we have the formula

We can substitute in the A and B definition of C and do the following.

Grouping then gives us

Familiar :) So now we have a formula for producing A's and B's. But to really calculate them, we need initial values as well. Looking at the C's we calculated, we can grab the first few values of A and B from the coefficients in C's. However, for those formula for A and B to apply, the similar formula needs to apply for C. This means we can only use values of C after the point where the double subtraction was already established, which occurs after . So we'll call that C₀ for convenience.

So now we have initial values! A₀ = 1, A₁ = -2. B₀ = -1, B₁ = 3. Using those initial values and the recurrence formula we worked out, we can now calculate successive values of each sequence. Here are the first ten of each.

A_n = 1, -2, 5, -12, 29, -70, 169, -408, 985, -2378, 5741, ...

B_n = -1, 3, -7, 17, -41, 99, -239, 577, -1393, 3363, -8119, ...

Notice how the third values, 5 and -7, correspond to the next values we'd already worked out. Validation!

And now the test, we look at -B_n/A_n.

= 1., 1.5, 1.4, 1.41667, 1.41379, 1.41429, 1.4142, 1.41422, 1.41421, ...

And that clearly is approaching the square root of two. Very neat. Very neat.

One might even say ... fantastic :)

Iterated Function Teaser

2007-08-05T00:33:00.000-04:00

After MarkCC talked about iterated function systems, my curiosity was naturally piqued, as it usually is by pretty things. I'd read his post, though I think I'm going to make one of my own. Anyway, below is the traditional fern fractal produced by an IFS. Simple mathematical formula, very neat result.

I worked out a small java generator to dish out similar pictures based on random parameters. The one above is derived from very specific values, which makes me a little skeptical of its implications, but that's a thought for a later post.

Here is another one I thought was kind of neat.

Generated at random, there's much less specific structure as with the leaf fractal. However, there seems to be a definite star pattern. Also, if you examine the picture, the star pattern seems to be repeated, at different orientations in the picture. To me, it almost looks like there are several similar 'stars' in space, and this picture is a projection of the three dimensional figure. Which is interesting.

Now, none of this ought to make sense just yet, but the above images were generated with /linear/ iterated function systems. I'm much more of a non-linear sort of fox, so below is a randomly generated non-linear system, with degree two polynomials.

But it looks neat, and that's the important thing.

Notice the way that in the linear cases as above, we largely are dealing with lines. Go figure. But introduce a non-linear, specifically quadratic element, and we get those neat curves.

Anyway. Maybe I'll do some real math with this.

Time for a Math Problem

2007-08-02T23:48:00.000-04:00

4 + 2 = 8

7 + 3 = 3

7 + 4 = 9

6 + 7 = 8

1 + 1 = 1

Sultan's Dowry

2007-07-31T00:02:00.000-04:00

So, a sultan has 100 daughters. When telling this problem to your friends, be sure to enunciate properly, lest they think the sultan has 100 'dollars'. What kind of sultan only has 100 dollars? A rather puny one, I must say.

But he has 100 daughters, and he is going to allow a commoner to marry one of them. Of course, as always is the case in such things, there is a catch. The commoner is shown each daughter, one at a time. Each time he has the option of choosing that daughter, or moving on to the next one. Once he passes a daughter, he cannot go back and pick her. Now, each daughter has a randomly assigned dowry, and the catch is this. Each time the commoner is presented with a daughter, he is told the value of her dowry, and the commoner can only marry the daughter of his choice if he choses the daughter with the highest dowry. Elsewise, he is tortured to death.

So the question is, what can the commoner do to increase his probability of choosing the correct daughter, and what is the best probability he can achieve?

And if that doesn't float your boat, here's a video of a puppy fighting a kitten.

Now, the commoner could just randomly stop and pick a daughter. In that case, he has a 1/100 chance of getting the correct daughter and not dying. Which sucks. What you need is more information, and the only information to be had is by finding out the values of successive daughter's dowries. That being so, the best strategy seems to be allowing some number of daughters to pass and /not/ choose from them. This gives you a pool of dowry values to compare from. Once you let that many daughters by, choose the next daughter with the dowry higher than all the dowries you've seen. We'll assume that this is the strategy you go with.

That being so, we need to determine the number of daughters to let pass to achieve the maximum probability of winning. If you let too many daughters pass, that increases the chance you let the daughter with the highest dowry pass. But too few daughters let by, and you will decrease the probability of seeing a high enough dowry to make a difference. So, how many daughters do you let by?

We'll say he lets n many daughters by. Of those n, he has seen the m'th highest dowry. This means that there are 100 - n dowries remaining, but only 100 - m /higher/ dowries, one of which will be the 100th, the highest dowry. However many dowries are left, the only thing that matters is the order in which the higher dowries are presented, because the commoner will pick the first of those he sees. The probability that the 100th, highest, dowry will be presented first is 1/(100 - m). But, that requires that m be the highest dowry seen. So, what is the probability that m is the highest dowry seen?

For m to be the highest dowry seen, a number of things must happen. One, m must be seen. Two, no dowry higher than m can be seen. Now, the probability that any one number is seen is n/100. That means the probability that a number is not seen is 1 - n/100. So the probability that m is the highest seen is the product of the probabilities that m is seen and all higher dowries are not seen. There are 100 - m higher dowries, so the total probability that m is the highest dowry seen is

Now, the probability that m is the highest dowry seen and the 100th dowry is presented first of the remaining higher dowries (thus letting the commoner win) is

However, m could be many values. For any value of m, the formula above gives the probability of winning. The total probability of winning, though, is going to be the sum of that formula for all possible values of m. The probability of at least one of two events occurring is the sum of the probability of each individual event occurring. We know at least one value of m will occur, so we sum over all possible values of m.

But the possible values of m depend on n. If n many daughters are chosen, the least 'maximum' dowry seen is the 'nth' dowry. The greatest 'maximum' dowry is the 100th dowry. So possible values of m run from n to 100. However, if m = 100, you have no chance of winning, so that would be like adding 0 to your sum, and we can just discard it. This gives us a total probability function in terms of n, the number of daughters you allow to pass.

That right there is enough to solve the problem. Jumping into Mathematica and plotting the function for all n from 1 to 99,

Clearly the function reaches a maximum around n = 40. Calculating p(n) for n = 35, 36, 37, 38, 39, 40, we get

{0.367438, 0.367794, 0.367873, 0.367682, 0.367227, 0.366516}

Clearly the maximum is reached at n = 37, giving a maximum probability of winning of 36.79%.

And I think that is quite cool. You've raised your probability of winning and not being tortured to death from 1/100 to greater than 1/3, which I find quite neat.

However, that was all a little aproximatura there. The problem is that the probability function, as a summation, doesn't really converge to anything convenient. What this means is that we can't really calculate the 'exact' maximum, at least not by traditional means, because it's not an analytic function. But, with a little goofing around ...

First, let's be a little more precise. I would like to do is clean up that function a little. For example, we can change the bounds of the summation. Also, the n/100 factor does not depend on m, so we can pull it out of the summation.

Next thing, instead of thinking in terms of how many daughters I want to let pass, I would rather think of in terms of what fraction of the whole population of the daughters I would like to let pass. So, we'll replace n/100 with a general value 'a' between 0 and 1, and replace all values of n with a.

And for maximum generality, let's not limit ourselves to a population of 100 daughters. We'll say the sultan has N many daughters.

Now, this part is a little fuzzy. Consider two different values of N. The total number of daughters you let pass in each case is different, but it's clear to me at least that the fraction you let pass is the same. All cases are really 'proportional' to each other. You wouldn't let 37% of 100 daughters pass, but let 56% of 1000 daughters pass. My point is that the value of optimal value of a, the fraction you let pass, remains the same for all values of N.

So let's think about what happens as N approaches infinity. In that case, the upper limit of the summation, N*(1 - a), also approaches infinity, as long as a does not equal 1, which we know would be silly. So in the case of an infinite number of daughters, we have the following.

And that is a power series. Specifically, it's a series of the form

Which is the Maclaurin Series for -Log(1 - x). Performing the substitution,

And that is quite the neat little function! Plotting it below,

Notice the similarity between this curve and the points we plotted above. Finite population sizes, like N = 100 far above, all approximate the infinite case shown here.

And now that we have a smooth function, we can differentiate it, and find the maximum point. To refresh, the maxima and minima of functions occur when the derivative of the function is 0. Clearly above, we have no minima. Differentiating,

And there you have it. You should allow 1/e of the daughters to pass. 1/e = 0.367879... Going back to the 100 daughter example, this means we should let 36.7 daughters, or rather 37 daughters to pass, which is what we determined. And plugging 1/e into the probability function, P(1/e) = -(1/e)Log(1/e) = -(1/e)(-1) = 1/e. So, the maximum probability of winning you can achieve is 1/e, which means that, at best, you have a 36.7879% chance of winning. Which is interesting. It's all very interesting.

And there you have it. 1/e. Go figure.

An interesting problem.

Software Innovation and MegaTexture

2007-07-29T16:44:00.000-04:00

(Cross-posted at PowerUp.)

John Carmack has always been a fascinating figure to me. As a kid I'd eat up interviews with him in publications like PC Gamer, as I was a huge FPS phreak who was intensely interested in programming. He was the kind of guy I'd look up to and say "man, I want HIS job!"

For those who need an introduction, Carmack is the legendary game developer behind Wolfenstein, Doom and Quake (among other titles). He's not only an interesting figure because of his role in inventing the first person shooter, but for his role in pioneering or even inventing graphics algorithms and rendering techniques for his games. A great example would be his surface caching technique, which was what made rendering fully polygonal real-time graphics possible on the original Pentium chips (back before they had even reached the 100 MHz mark). Before hardware rendering (back then extraneous enough to be referred to as "acceleration") and libraries like the now defunct Glide were in widespread use, real-time 3D rendering was only considered possible with "pseudo-3D" techniques. If you're familiar with the old FPSs like Doom and Duke Nukem 3D, you'll notice that almost all the secondary objects in the maps were actually 2D, which included the enemies. This was because rendering in true-3D involved some pretty significant resource overhead. Two of the biggest hurdles Carmack faced when developing Quake were calculating what polygons on the character models were visible to the player and how surfaces would be lighted.

Surface caching was a technique Carmack invented to solve the latter. In traditional real-time rendering models, the lighting of surfaces was calculated from the vantage point of the player. That meant that everytime the player changed their position with respect to a visible surface, all the lighting data would have to be recalculated and rendered again. That sort of resource expenditure adds up, and would have been impossible to achieve on most desktop-level hardware in 1995. So what did Carmack do? He simply used a static lighting model, where the lighting of the surface would be pre-configured and the data would be stored in a cache for retrieval whenever the surface was visible from the player's vantage point. Yes, it's simple. So simple that it makes you go "Man, why didn't I think of that?"

It's kind of funny, because Carmack's new technique, which debuted in Enemy Territory: Quake Wars, gives you that same reaction. ET: Quake Wars uses the Doom 3 engine for a mostly outdoor Team Fortress/Counterstrike style multiplayer FPS. Now, one of the technical hurdles was obvious to anyone familiar with the Doom 3 engine: it simply was not well suited to rendering large outdoor environments. If you play Doom 3, you'll notice that all of the outdoor environments were small, enclosed canyon-style spaces. The Doom 3 engine was quite a technical accomplishment in it's own right, and was really the first to develop a true global illumination model (i.e., unite how lighting and shadows interacted with all the surfaces in the game). But rendering large outdoor environments would have been extremely taxing with the typical methods, almost all of which involve fragmenting the mesh and swapping out low-res and high-res versions depending on where the player is located. So what does John Carmack do? He invents MegaTexture:

MegaTexture technology is something that addresses resource limitations in one particular aspect of graphics. The core idea of it is that when you start looking at outdoor rendering and how you want to do terrain and things in general, people almost always wind up with some kind of cross-fade blended approach where you tile your textures over and blend between them and add little bits of detail here and there. A really important thing to realize about just generally tiling textures, that we’re so used to accepting it in games, is that when you have one repeated pattern over a bunch of geometry, the texture tiling and repeating is really just a very, very specialized form of data compression where it’s allowing you to take a smaller amount of data and have it replicated over multiple surfaces, or multiple parts of the same surface in a game since you generally don’t have enough memory to be able to have the exact texture that you’d like everywhere.

......

So when Splash Damage was starting on, really early with Enemy Territory: QUAKE Wars, they were looking at some of these different ways to render the outdoor scenes with different blends and things like that. And one of my early suggestions to them was that they consider looking at an approach where you just use one monumentally large texture, and that turned out to be 32,000 by 32,000. And I – rather then doing it by the conventional way that you would approach something like this (i.e. – chopping up the geometry into different pieces and mapping different textures on to there and incrementally swapping them for low res versus high res versions), just let them treat one uniform geometry mesh and have this effectively unbounded texture side on there, and use a more complicated fragment program to go ahead and pick out exactly what should be on there, just as if the graphics hardware and the system really did support such a huge texture.

It's simple, really. Take a huge texture and stick on the hard-drive, and use your freed up memory resources to create a more complex fragmenting program to spool it as needed. Not only does it allow the game to overcome the limitations of the Doom 3 engine, it makes outdoor environments look better and generate more variety than what would be possible in the standard model.

This is really an example of how in-the-box thinking often harms software innovation. Another good example is the file-system. Just about every operating system uses the descending hierarchical subclass system that originated in BSD Unix in the 70's, and files themselves are almost treated as prime-numbers are in mathematics. Most people are surprised to learn that files were once controversial, because of the obvious issue of incompatible file formats that would inevtitably lead to technology driven monopolies. But files became the standard model because, well, everyone started using them. Not only BSD and System V, but DOS, GNU/Linux and then Windows. Is there a better model? I'm not sure, but most seem to simply accept it as a given.

I Hate Statistics

2007-07-29T11:37:00.001-04:00

Ed Brayton and Mike Dunford recently picked up a little tidbit you might not have noticed. Apparently the big thing now is to compare military deaths under Clinton to military deaths under Bush. As one blog does, we get the following.

Active duty deaths during Clinton's first four years (1993 - 1996): 4302

Active duty deaths during Bush's first four years (2001 - 2004): 5187

See, nothing serious right? Only 885 more deaths under Bush, and Clinton didn't even have to fight two wars!

Of course, there are a multitude of things wrong with this. Number one, it doesn't discuss causes of deaths. You're comparing natural/accidental deaths to combat deaths. More importantly though, it doesn't take into account the size of the military at the time - the deaths need to be viewed as a proportion to the whole population.

Mike Dunford does all the hard work, research and recalculation, and produces the following graph from this pentagon source.

This includes everything, combat deaths, even deaths deaths during annual training, since that is counted as an active duty death. As you can clearly see, we've been having a massive decline in the military death rate from the 1980's to about 2000. I'm not really up on my history, but a brief visit to Wikipedia seems to indicate the bump around 1991 is probably attributable to the gulf war - understandable. And right around the time Bush took office up to now, we see a massive surge in the death rate, unlike anything in the last 20 years.

Now, this surge can no doubt be attributed to the wars we are currently fighting. There's little mystery there. It is understandable that a war will lead to increased casualties - few would argue that. What makes this significant is the way people will and apparently have used these numbers to lie in support of the president and his policies. I find this absolutely reprehensible. And we've seen this sort of thing before. About a year ago, I believe it was Rush Limbaugh who ran a graphic on his website, comparing the number of deaths in Iraq to the number of deaths by automobile accidents in the US. Of course the number of automobile deaths was staggeringly high in comparison - until you look at the deaths in comparison to the size of the population. With 250 million Americans, the number of soldiers in Iraq is minuscule in comparison, and the death rate in Iraq was revealed to be almost 22 times greater than the automobile related death rate. Again we see the right's willingness to lie and distort and take advantage of the deaths of Americans to support their cause.

Is it hyperbole to say they are taking advantage of these deaths for their own means? Perhaps. But this is one of the things that most rubs me the wrong way, bad math aside - whatever the cause, soldiers are dying. And instead of trying to address that, the people in charge and their supporters are manipulating the data to try to maintain their control and the status quo. Soldiers are dying. Soldiers are being killed and wounded, mentally and physically, every day, and they quibble over numbers and blame. Yes accidents occur, and yes casualties are expected in war time. However ... I don't think I can end this any better than Mike Dunford himself, who's wife is in the army.

We have a responsibility to do our best to keep the active duty troops from dying unnecessarily. During peacetime, that means making sure that training and day-to-day operations are as safe as they can reasonably be, and that accidents are prevented whenever possible. During wartime, it means that we should do our best to make sure that the fight is necessary, that the goals are achievable, and that there is a well-thought-out and feasible strategy in place.

The current battle in Iraq meets exactly none of those criteria.

Dog Bites Man; Michael Reagan Bleats Inanely

2007-07-29T01:43:00.000-04:00

(Cross-posted over at my new solo blog, PowerUp.)

Science Avenger takes conservative flak Michael Reagan to task for a particularly inane column at Townhall dot com. Now, "inane column" and "Townhall dot com" are two phrases that can seldom be separated, but this one reaches some uncharted lows. Just look at the opening paragraph:

If anybody doubts America is engaged in a culture war and losing it they need only to take a look at the series of concerts promoting Al Gore’s global warming hoax last weekend. They would have learned that the war is being waged in the sewers.

I don't get this kind of rhetoric. I see it a lot, but I don't get how can it even make sense to anyone. America is engaged in a culture war, and losing it. So American culture is fighting itself, and losing? Is this like that Monty Python sketch with the guy who wrestles himself?

In reality conservatives are simply whining and complaining that cultural mores in America are changing and further chipping away at the hegemony they've enjoyed over said culture for so long. For a long time in this country, cultural supremacy was considered the birthright of Anglo-American Christian males. Traversing the timeline from slavery to Native American genocide to Woodrow Wilson's delirious rants against "hyphenated Americans" to segregation to womens' liberation and beyond, there has been a constant struggle for societal underclasses to achieve equality. Conservatives look with nostalgia at their Norman Rockwell caricature of America because they see all the right colors: white family, white picket fence and not a single distrubance to any of that unformity in sight.

And as for the ridiculous ejaculation about "Al Gore's global warming hoax", well, the stupidity of that should speak for itself (hint to the tards: Al Gore had virtually nothing to do with hashing out the consensus of global warming, climate researchers did that over decades). I think Al Gore has effectively cemented his position as the Rachel Carson of anthropogenic global warming. Wouldn't be surprised 20 years down the road to hear how Al Gore was worse than Hitler from the same folks currently spouting such frenzied silliness about Carson.

Reagan then goes on a long rant about the use of the "F word" by the "Whole Earth" concert performers. His argument only gets more incomprehensibly stupid and myopic. Just look at this paragraph:

I went to a lot of concerts years ago. I never heard Frank Sinatra or any other performer use a single obscenity during their performances. Moreover, if any of them had uttered anything as foul as the “F” word, they would have been driven off the stage.

I can't do any better at disposing of this little bit of nonsense than Science Avenger himself:

Let's remind him that back in the "good ol days", instead of hearing "fuck" on the stage, what many heard was "get these niggers to their proper seats away from the decent white folks". Pardon us for preferring things the way they are now.

Bingo. If Michael Reagan is so nostalgic for the "civility" he sees in his Ozzy and Harriet version of post-war America, maybe we can find some way for him to assume the role of a Black man, or an Italian or Irish immigrant, or anyone who was known to have Native American ancestry, or many others. He might not be so convinced that the "civility" he envisions wasn't vaslty overrated.

Along the way, we come across this little gem:

That’s no longer true. Comedians vie with each other to use the most extreme obscenities and sexual innuendos. What was once called “street language” is now considered normal discourse. Things once considered sacred are now seen as commonplace. Sex is no longer an expression of love between a man and a woman – today it’s seen as recreation, like a game of golf, to be portrayed on stage and screen without restraint.

Oh please, not this nonsense again! It's kind of funny how the first instinct among pedestrian conservatives like Reagan is to completely exclude the middle. Almost everyone recognizes that rampant sex with no restraint is probably an unhealthy activity and generally a bad idea. What most sexual liberals would argue, however, is that someone shouldn't feel ashamed for enjoying what is one of the most natural and fulfilling aspect of the human condition: their sexuality. To use an analogy, everyone knows binge-eating is unhealthy, but that doesn't mean one can't take pleasure in tasty dishes in moderation. And the analogy is quite apt, since many ascetic religious traditions forbid their adherents from enjoying food in addition to sex. Self-denial in matters of sex can be just as damaging as unrestrained promoscuity.

As well, I love how he only allows it to be "an expression of love between a man and a woman". That's a very recent notion that Mikey Reagan is trying to shoehorn into his own antebellum American fanatsy-land. Back when women were essentially considered property, sex was usually an expression of the man's ownership of the woman. Sex almost never had anything to do with a woman's own pleasure or emotional satisfaction. And I needn't mention, but will do so regardless, that sex can express love between two men and/or women just as well as between a scalar man and woman.

And here's the grand finale:

That’s what’s at stake in the culture wars. A society bereft of standards that demand civilized behavior among its people is a society where the individual is deemed worthless as being anything but a consumer for the degraded wares of the smut peddlers and a source of income to pay for the schemes of those who sell Marxist snake oil such as global warming as a means of subjugating the populace.

Kind of funny, that. America is known for it's excessive consumerism, yet is also by far the most laissez-faire among the Western nations and the developed aspects of the Orient. Simply put, consumerism is a result of the capitalist free enterprise system that conservatives have been ideologically boosting since the New Deal spawned the original reactionaries from whom they are descended (that's when America began it's long decline into socialism, a result that has strangely failed to come to fruition). And you have to love the bit about "Marxist snake oil" in reference to global warming. It's a ~~JEWISH~~ SOCIALIST CONSPIRACY. Classic crankey from a long-time crank.

Putting the Ixnay on the Blog Move

2007-07-25T22:06:00.001-04:00

Well, it's been a while now that I've been looking at hosting plans for the blog. The only problem is that I've gradually lost my enthusiasm for it. So for now the basic plan to move it to my own host is nixed.

Among other reasons for losing my general enthusiasm for the move has been the fact that I haven't even been managing to make regular updates lately, so paying monthly charges started to seem more and more like overkill.

Blogger is good for now, so I'm staying here. And I'll try harder to post interesting content.

That is all.

Lazy Fox

2007-07-19T12:09:00.000-04:00

That damnably lazy fox is running off again. I swear, it's like ... Zoom! Doosh! Bwee! Moople! with him. Tyler's good to put up with it!

Until he's back then ... I shall leave these three to entertain you.

Yerf ^.^

LoopBrot

2007-07-18T02:04:00.000-04:00

Now this is just beautiful. Fantastic. Check it out. We've taken the Mandelbrot Fractal, and overlaid on it in white the FoxelBrot image. To refresh, the FoxelBrot is composed only of the values in the Mandelbrot Set that form loops in Mandelbrot Function. It's all very clever.

But, overlaying the two, we can see what significance those points play in the larger scheme of the fractal!

Click for a larger image! The looping points are the white dots amidst the black. They may not show up on the shrunken version, so click for the larger. It's quite clear what the looping points are - the centers of all the lobes, everywhere :) What a fascinating result. Just beautiful.

Fantastic!

Can't Keep My Eyes Open

2007-07-17T19:11:00.000-04:00

I said I'd do some things here after I got home from work, but it turns out that from work I had to do a bunch of bullshit at Lowe's that had me out for an extra hour. Now I'm tired, groggy and most importantly I don't the full presence of mind. So for now, here are a couple of montages of Mortal Kombat fatalities. The first spans the first and second iterations of the game, the second spans the third as well as Trilogy. Mortal Kombat is serious w00tsauce.

UPDATE: I've removed the filler I initially put in this post out of respect to Foxy (it was probably inappropriate). A loved one has died, and I think he'd appreciate your condolences.

Latest Comments on the Atheism Wars

2007-07-16T18:25:00.000-04:00

John Wilkins has a characteristically very interesting post up on the science versus religion kerfuffle on SciBlogs, and of course I have to give my objections. I'll start with this statement:

Science is a process undertaken by human beings. Religion is also a process undertaken by human beings. They are conceptually distinct, but human beings are not driven by conceptual niceties. Rather than seeing religion and science as isolated endeavours, or as the same thing, it is best to expect that science and religion will have their own domains but that these domains will occasionally overlap.

Of course we can all agree that humans are not driven by conceptual niceties. Hashing them out is a difficult and often tedious process that hardly comes "naturally" to primates of the homo sapiens sapiens variety. But even acknowledging that, we can see that there is really a flaw in using this fact to argue John's case: even if humans are not by nature (or more precisely, cognitive architecture) driven by abstraction and conceptualism, in principle, we should be. If we can agree that science is more reliable when it comes to rendering an objective picture of reality than religion, we also agree by consequence that our innate cognitive propensities to the contrary are insufficient and should be resisted.

I also take issue with John's statements about religion's proper role. People constantly speak of such a thing, but I have yet to see someone expound a useful application of religion that cannot be fulfilled at least equally well by a secular institution. I think the religion that John has in mind when making arguments of these sorts is very different from the religion in my mind or the majority of the religious. At least in it's predominant varieties around the world, religion is useless unless certain postulates it claims as canonical are true. Christianity is nothing but a reformed Judaism without the ressurection, and Judaism in turn is nothing but deism without certain assumptions regarding covenants and other things. John, as someone non-religious, seems to boil it down to banal mundanities like creativity, ingenuity and a sense of connection and belonging. If one wants to argue that religion is great in part because of the art it has historically inspired, I'll partially agree. Burning away the entire influence of religion in culture would result in most of the Western literary canon being tossed on to the ash-heap. But religion is much more than artistic inspiration, and such requirements are often just as effectively fulfilled by entheogenic drugs as supernaturalism and mysticism.

But still, discussion over the proper role of religion and superaturalism is what is desperately needed right now. Up until recently the general attitude was that religion automatically deserved respect and deference. And whatever John's position on these matters is, I suspect he'll find himself far closer to the side of the "New Atheists" than the theological reactionaries trying to carve some relevance out for their pet institutions and dogmas.

Greasin' Up The Engines

2007-07-16T06:58:00.000-04:00

Hey all (four of you)! I haven't exactly been on a posting rampage recently, but I find myself in another monday morning (which I have completely off) with a bunch of new ideas. And for once, I've thought about these new ideas for more than five seconds and have come to the conclusion that they genuinely good. Usually when this happens have a swirling mass of ephemera in my mind that I try to cull down to a manageable workload, and end up with about 1% of what I initially wanted on the blog. It sucks, so here's my plan for changing it:

I plan to develop a bit of a personal literature base that I can use as reference material for more advanced posts. Often times I junk posts because I have to work in a shitload of background subject matter that makes the post, while nominally accessible, extraordinarily long-winded and tedious. Okay, I'll admit it: when it comes to math writing, I'm no Mark Chu-Carrol and certainly no Martin Gardner or Greg Chaitin. So I need to circumvent my limitations in a more innovative way.

I'll be hashing out the details over private email with Foxy over what we should write for the reference base. I'm certainly not going to be covering elementary algebra, but where to start and how far to go are fuzzy. Nonetheless, it shall be done! For today, however, I plan on writing a couple of non-math posts and changing things up a bit visually. I'm going to rework the blogroll, dividing it into more specific categories. I also plan on adding some new graphics to make things feel a bit new.

About the new blog, yes, it's still going up and will be up within the next couple of months at most. But for now I want to make the most of this space. I'm also shopping around for a good deal on hosting. An experience with a certain hosting company made me a bit weary of being quick to sign on to long-term deals without a thorough trial period.

That is all.

(P.S., if you were reading GM/BM recently and saw my colossal gaffe in the comments, please don't rape me in the ass over it. I know that stuff is typically a valid justification for mathematical honor killing, but please spare me!)

Math Video

2007-07-11T13:02:00.000-04:00

This is an excellent mathematical introductory video.

Apparently there was some trouble with the embedded version ^.^

I Beat MarkCC!

2007-07-11T12:34:00.001-04:00

I beat MarkCC to the punch by a day!

Of course, he sort of outshines my own work. Neat post on the Mandelbrot Set. Take a look.

Envious Scientists

2007-07-11T05:06:00.000-04:00

[Editor's Note: I changed some of the wording in paragraph three (below the blockquote) to better suit what I was trying to say. - Ed]

The SciBloggers periodically swap blogmemes from place to place concerning some scientific or academic topic. The latest one concerns whether scientists have a certain "envy" of another discipline, prompted by these questions from Dave at The World's Fair in response to an article repudiating the idea that biologists specifically had "physics envy":

1. What's your current scientific specialty?

2. Were you originally pursuing a different academic course? If so, what was it?

3. Do you happen to wish you were involved in another scientific field? If so, what one?

There were several interesting responses. PZ Myers claims that physicists should have biology envy, MartinR from Aardvarchaeology says he's only envious of the funding, and RPM admits he has math and CS envy (something which Foxy and I can completely understand, LOL!).

I really don't have anything to contribute to with regard to the flame war between biologists and physicists specifically. My only comment is that this meme, despite it's somewhat flippant nature, highlights an intellectual blindspot that has plagued science and related intellectual inquiries pretty much since their modern inception. There is often a "my discipline is better" attitude between practitioners and various fields. One memorable manifestation of this was when, at the height of the DWave controversy, Scott Aaronson lashed out some frustrations with physicists, caustically deriding them as "The Headmasters of Handwaving" (among other things).

Of course, if you read the post, what prompted it was a bit of "science projection". As CS has come into it's own as a scientific discipline over the last several decades, it has started to encounter more and more objections to it's status. Some charge that CS is really more engineering and mathematics than it is a field of empirical science. Scott's post itself illustrates this, as he shows that one of the consequences of the unsolved "P versus NP" problem is that we can't yet prove, in a non-empirical and a priori way, that NPC problems are hard for classical computers, so deriving conclusions about quantum computers is really putting the cart before the horse. Such a thing certainly sounds like a concern more akin to the world of abstract mathematics than empirical science, much like searching for a disconfirming instance of the Riemann Zeta Conjecture before jumping to results on the distribution of primes.

I think it's these sorts of back and forths that should remind us that sciences are usually discrete disciplines with tools fashioned to specific problems. Physicists can always respond to the challenge of CS theorists like Scott that their subject matter isn't susceptible to the same techniques as resource-bounded complexity analysis. And in turn, biologists can scold any demands that they apply a physics-style reductionism to their discipline, a la was Razib calls the Fisherian "ideal gas law".

And for a concluding remark, it's also important to note that this is why I'm generally skeptical of strict demarcationist efforts at defining science, such as those of Popper. Attempting to boil down disparate fields of study to a single abstract model can be regarded as somewhat misguided, but that's a topic for a separate and more complete post.

Magical World of Torblednam

2007-07-10T18:03:00.000-04:00

MarkCC over at Good Math, Bad Math has started talking about Fractals, which are fun and interesting things. I recommend checking it out.

I'd like to talk about one specific fractal though, the Mandelbrot Set.

Neat, eh? Notice the self-similarity. If you zoom in on any one of the tiny lobes, you come up with more fine structure similar to the main structure shown here. And you can keep zooming in forever, and always find similar structures. It's all very clever. Lot's of neat properties therein. It's hypothesized for example that the area of the Mandelbrot set is

An interesting value.

The way they generate the image is like this. Consider the sequence z_i defined in the following way for i = 0, 1, 2, 3... so on. Take some complex number c. Then,

This gives rise to the following.

And so on.

Now, the idea is this - if, for a given c, goes to infinity, then c is not in the Mandelbrot set. If converges to a value, or cycles between values, then c is in the Mandelbrot set. The image is produced by putting black points at all the values of c that are in the set on the complex plane. It's basically just a graph of the convergence of that iterated function.

Now, for some values of c, it is obvious that the sequence is not going to converge. Consider c = 1, for example.

...

It's relatively clear that is increasing without bound. Now 1 is really the complex number 1 + 0*i, which means that the point (1, 0) is not black in the image.

But for other values of c it's less obvious. You can keep iterating, and the sequence might not clearly diverge for a long time. One approach is to pick a boundary, like 4 and say that, considering , if is ever greater than 4, then the sequence most likely does not converge, and that value of c is not in the Mandelbrot set, and move on. Of course, it may take certain values of c many steps to exceed the boundary value. It can be tiresome.

So, I wonder if the points in the Mandelbrot set could not be calculated explicitly. Just give a formula and say, BAM, that's in the set. Of course, for some points, I don't think it's practical, but ... stick with me a second.

A value c is in the set if the sequence does not diverge. However, if it does not diverge, that means one of two things has happened. Either the sequence converges to a single value, or the sequence has set into some kind of loop or cycle. Determining the convergent values I think would be difficult, nigh impossible. However, determining the values of c in loops and cycles could actually be relatively straight forward.

If cycles, then for some value of n, . So then, we want to solve for all values of c that make that equation true.

So, what we're really interested in, when we say , what we really mean is . Consider , which solves for c = 0. Going back to the original scheme, clearly c = 0 is in the Mandelbrot set. Now, any , expanded out, is simply a polynomial in terms of c, and the equation can be solved to get all the possible values of c. We can generate a table of those values with the Mathematica nonsense below.

z[c_, 0] = c

z[c_, n_] := z[c, n - 1]^2 + c

ptIze[z_] := {Re[z], Im[z]}

values = Union[ Flatten[ Table[ Table[ Root[z[#1, n]&, i], {i, 1, 2^n} ], {n,0,8}] ] ];

pts = Table[ ptIze[ values[[i]] ], {i, 1, Length[values]}];

And then, plotting all that, we achieve the picture below.

Not bad :) It's sort of like a skeletal version of the real thing. Neat. I should calculate a similar image of the real set, and see how those points correlate to anything significant. It almost looks like the vertexes or endpoints of the figure. Which makes for an interesting hypothesis. Project for later, perhaps?

Anyway. Moving on.

Some Updates on the New Blog

2007-07-09T03:15:00.000-04:00

Some people may remember that I announced my plans a while back to move the blog to my own host. That plan hasn't changed, but unfortunately is going to have to be pushed back. It's a long story, but suffice to say that I'm never going to do any business with 1&1 or any affilliated companies ever again, for as long as I live.

I also plan on starting-up a new personal blog for myself. Since this blog Foxy and I run has essentially become a generic math and science blog with a little politics tossed in for flavor here and there, I changed the name from "Greedy, Greedy Algorithms" (a play on "Hungry, Hungry Hippos", don't know how many got that) to what it is currently. That's the nature of the blog from here on out. But I also notice that I'm not writing as much about theoretical/applied computer science as I should be. So for that I'm starting a separate blog devoted exclusively to it. No politics, anti-religious rants or what have you, just straight comp sci and highly contiguous subject matter.

And since I'm buying a host that will allow me to install multiple blogs, I figured I'd also offer Foxy to move his blog to my host. No charge involved, at the very worst I'll just try to rebound some cash on the traffic I pay for by setting up ads.

That is all.

Four Reasons DNA is Not Computer Code

2007-07-08T00:27:00.000-04:00

This has been one of the most persistently annoying creationist and IDist talking-points for at least several decades. As someone whose involved himself in programming and computing theory in some form or another since I was around 11 years old, I find it particularly annoying. And there is an obvious reason why the argument has the resiliance and longevity that it has. That is, much like the ancient Paleyan "watchmaker" analogy, it has intuitive appeal and usually reinforces what most people (since most people are at least vaguely religious) already want to hear.

The only problem is, it's wrong, and it's level of wrongness is somewhere in between "I bought into the Y2K hysteria" and "I heeded Goerge Gilder's investment advise during the dot com boom". Not only is it wrong, but it's wrong in the most irritating way: it exploits superficial similarities to obscure the important and profound differences that render the analogy fundamentally flawed. So with that in mind, I've decided to elucidate what I see as the four most important differences between the two phenomena.

1. Most importantly, DNA is not a computer code: DNA's function is a structured chemical process that synthesizes proteins (and furthermore, this structure is very weak and ad hoc, see point no. 2 below). Any analogies to computational processes are only superficial, because DNA does not meet the technical definition that qualifies something as a computer, i.e., Turing equivalence. A Turing equivalent computing device is a device that can perform any of the computations in the repotoire of a Universal Turing Machine. The most common model that fulfills this definition is the serial von Neumann machine, a general class of models that includes abstract RAM and register machines. Since extant cell DNA is not, as far as well know, capable of doing performing the aforementioned tasks, it doesn't qualify as a computing device.

2. DNA is incredibly messy and ad hoc: Computer code in high level algebraic languages (e.g., FORTRAN, Lisp, Algol, Haskell, etc.) is typically built around well structured mathematical relationships. Procedural programming, for instance, is built around sequential instructions and imperative looping commands, while functional programming is built around recursive functions (this is simplified for brevity). In DNA, however, the structure is far more ad hoc. Mere sequential similarities in nucleotides between genes correlate very weakly in terms of genomic function, and sometimes sequential similarity between genes with the same function is nonexistent. This ad hocness makes gene-clustering in bioinformatics, for instance, incredibly difficult, as even the best clustering techniques for gene-function harbor limitations in dealing with the evolutionary factors that affect genomic expression. And aside from that, it certainly doesn't indicate good programming practices.

3. DNA has no other layer of implemenation beyond the cell: There are no high level compilers, assemblers, interpreters or what have you that allow the effective passing of instructions to the cell. Genetic function is of course mutable, but manually doing so has, as far I understand, highly unpredictable results. Simply put, if DNA is a code, it's certainly not user friendly for those who wish to tinker with it.

4. DNA is wasteful, highly error-prone with regard to copying-fidelity and is incredibly susceptible to post-hoc substitution and modification: Large portions of functional redundancy, (relative) non-functional redundancy, randomly accumulated transposable elements and vestigial coding sections ("fossil genes"), among other things, do not indicate good design, much less deliberately coded software architecture. Much like phenotypic traits, viewing DNA through the lens of engineering doesn't portray it in a very good light.

Swarm Behavior

2007-07-05T10:48:00.000-04:00

A neat article in National Geographic discusses the intelligence exhibited by animals in swarms, such as herds or ant colonies, and applications to human problems. It's all very slick. I recommend it.

MIT's Department of Systems, Communication, Control and Signal Processing

2007-07-04T04:26:00.000-04:00

Here is a description of a sub-area within MIT's department of Electrical Engineering and Computer Science. I'm not going to say anything about what it has to do with evolutionary biology but I'm sure it sounds designy enough to rile people's adolescent fantasies about the inevtible triumph of their ideas against 150 years of scientific investigation:

Area I research concerns itself with a broad spectrum of problems of communication and coding, systems theory and control, optimization, statistical inference and decision theory, and signal processing, as well as the shared methodological underpinnings of — and increasingly the interactions between — these different fields. Research topics range from fundamental principles to application, from analysis to synthesis, and from theory to experiment and simulation. Thesis research can involve different combinations of the above, depending on the student's interests and the nature of the problem. A list of several recent Area I graduate theses is provided at the end of this document as examples.

BOOYAH DARWINISTS!

(For those scratching their heads, I give you this bonus link to some extra special UD IDiocy.)

Salvador Cordova is Pathetic

2007-07-04T03:08:00.000-04:00

By now everyone is familiar with slimy Sal Cordova, a man whose penchant for tossing around technical terms with little or no understanding of the concepts behind them serves primarily to make the standard IDiot liturgy appear as grand poobahs of science by comparison. Now he's taken it upon himself to attack Dawkins review of Behe's The Edge of Evolution. And oh boy, is it ever a pathetic display. Opening up, of course, with the classic ID creationist equivocation:

Dawkins is a master of rhetoric. Only he could take a clear example of intelligently designed evolution (dog breeding) and offer it as a convincing “proof” of Darwinian evolution...

......

But this is misleading. In fact, for varieties of dogs to emerge, there has to be a relative absence, not presence of natural selection. The kind of selection in play in Dawkins example is intelligently designed, it is not natural whatsoever. Deliberate dog breeding is an example of intelligently designed selection, not natural selection. But Dawkins masterfully conceals this inconvenient fact and leads the reader into thinking natural selection works like an intelligent designer, when in reality it does not.

Well, we at least know we're dealing with good old fashioned creationist nonsense here. Sal's argument essentially boils down to saying that any conscious configuration whatsoever negates anything the process we're enacting could possibly tell us about similar processes in nature. He may not explicitly claim it, but the innuendo is certainly strong, aside from his argument in general being nonsense. It would be as if someone claimed that experiments on elementary particles using colliders were not "natural whatsoever", or an example of a natural process, due to the fact that the conditions were configured beforehand.

And furthermore, Sal goes quite a long way in displaying the inherent vacuity of "intelligent design". Along with the myriad of other deficiencies that have been pointed out over time, "intelligent design" seems to stuck on a black and white proposition that something is either "designed" or not. Judging by the rhetoric, it appears that anything from architectural drafting to software design to scientific experiment construction is lumped into the category of "design" without any meaningful differentiation, despite the manifold and important differences between them. It may be a convenient "get out of falsification free" card for the conjecture's apologists, but it's certainly not something that is indicative of good science.

And proceeding from there, one can remove themselves from the muddled thinking of the IDiots and realize that Cordova's "Intelligently Designed selection" is a meaningless catch-phrase. What artificial selection demonstrates has little to do with "intelligent design" and a lot to do with what can be accomplished by changing selection pressures. The natural selective pressures obviously wanted specimens that could survive and reproduce in non-domestic conditions, while the artifical selection pressures imposed by humans gradually opted for cooperative specimens more conductive to an agricultural civilization. Calling that "design" is sort of like calling the gradual development of culinary techniques and cultural food preferences "baking".

Moving on, Sal engages in his usual pseudoscientific techno-babble wanking by sputtering about a concept from mathematical biology:

Dawkins is surely familiar with the consequences of The Fundamental Theorem of Natural Selection by Fisher. The theorem implies that traits under extreme pressure from selection cannot be very variable. They can only be variable if natural selection is weak or non-existent.

This is easy to see. If selection is strongly favors dark colored individuals of a species, eventually most if not all of the individuals will be dark colored. Any future mutations that don’t yield dark colored individuals will be weeded out by selection. Natural selection is the enemy of diversity. Selection is the enemy of innovation. Not the friend of it.

That would be pretty impressive if the Wiki-page that Sal links to didn't provide an almost antithetical description of the concept than he did: "The rate of increase in the mean fitness of any organism at any time ascribable to natural selection acting through changes in gene frequencies is exactly equal to its genic variance in fitness at that time". Essentially, it states that those with greater variation tend to experience greater increases in fitness. However, that being said, I wouldn't bet my life (or my revolutionary new biological theory that gets me persecuted like Galileo) on the idea, as from my understanding it's relevance is disputed within biology (with some decrying it as overly reductionist).

But even so, what Sal says about intense selection pressures is trivially true. All things being equal, a strong selection pressure will winnow out variations from a well adapted population. What Sal overlooks is that selection pressures change, and often change drastically. In such conditions natural selection is indeed a "friend of innovation", as it culls down the pool of biological populations to those with traits most adaptive to the surrounding environment.

And, not to interrupt Sal's exercise in deliberate distortion or anything, but Dawkins actually wasn't speaking of the role of selection at all in his review. He was using dog-breeding to argue against Behe's claims to the limitations imposed on evolution by variation (more specifically, mutation).

After quoting a couple of signatories to the "Dissent from Darwin" list repeating what he said, he misquotes a paper on the selective pressures involved in dog domestication. Here's Sal's except:

The domestication of dogs caused a dramatic change in their way of life compared with that of their ancestor, the gray wolf.

....

a major consequence of domestication in dogs was a general relaxation of selective constraint [weakening of Natural Selection] on their mitochondrial genome. If this change also affected other parts of the dog genome, it could have facilitated the generation of novel functional genetic diversity.

And here's what it says exactly before the jump indicated by the ellipses:

The domestication of dogs caused a dramatic change in their way of life compared with that of their ancestor, the gray wolf. We hypothesize that this new life style changed the selective forces that acted upon the species, which in turn had an effect on the dog’s genome. We sequenced the complete mitochondrial DNA genome in 14 dogs, six wolves, and three coyotes. Here we show that dogs have accumulated nonsynonymous changes in mitochondrial genes at a faster rate than wolves, leading to elevated levels of variation in their proteins.

So, you see from my emphasized portion, Sal's quotation was a wee-bit selective. While making it look like the authors of the paper were downplaying the role of selection, they were really only investigating the change in selection pressures on the ancestors of modern domestic dog breeds. And also, I'll freely admit to being no expert on the matter, but it would appear that the correlation of the increase in genetic variation of dog breeds with the increase in fitness would be at least somewhat similar to what we expect to observe from Fisher's theorem.

Before engaging in self-congratulatory auto-fellatio for his amazing debunking of Dawkins, Cordova squeezes off this turb, which I leave only for your amusement:

Finally, consider the evolution of flight: an arm evolving into a wing. The arm must go through several stages of being a bad arm first before becoming a good wing. Thus, clearly, selection would be a rather nasty barrier to the development of an arm into a wing.

Have a nice day!

Evolving Hardware

2007-07-02T12:32:00.000-04:00

(Version 2 of this post! It's evolving.)

Of late, two news stories have come to my attention, involving an evolutionary approach to hardware design. In the first case, a scientist was attempting to develop a chip that would respond certain ways to certain auditory input. In the second case, though from 2002, scientists were trying to design a circuit that would produce a sine wave varying voltage, an oscillator.

The approach was pretty much the same in each case. They started with just a set of transistors, basically just an electrically controlled switch. However, the way the transistors were connected to each other, was modifiable, and could be controlled by a computer. Changing the configuration of the transistors changed the way the circuit behaved, and thus what it did.

So, you start out with a set of random configurations, and test each configuration against what you're hoping to achieve. In the first case, the scientist was looking for a specific voltage output in response to a certain frequency sound, and a different voltage output in response to another. The sounds were inputted to each configuration of transistors. The configurations that produced an output most like the responses the scientist was looking for were judged 'fit', and the others 'unfit'. The fit configurations were then bred, producing more configurations that were like the parent configurations but different. Occasionally, a certain configuration might change some aspect at random in the breeding process, as if it had mutated. As the generations progressed, and the 'fit' configurations were selected over the 'unfit', eventually a configuration was found that exactly matched the desired voltage outputs to the sound inputs. Similarly, in the case of the oscillator group, eventually a configuration was found that generated a smooth sine wave of voltage.

Which is neat in and of itself. But it gets cooler. The real surprises happened when they tried to determine why each configuration worked the way it did.

In the case of the auditory input experiment experiment, only 37 of the transistors were connected to each other, a fraction of the amount available. The most interesting aspect was a group of five, wired in a loop, not connected to the other 32 in the 'main' group. As such, these 5 couldn't really influence the behavior of the main circuit. However, if any one of these five were removed, the circuit ceased to function. Also, if this same configuration were loaded onto any other chip with reconfigurable transistors, the circuit would not work the same way. What seems to have happened is that, through natural selection, the configurations developed a way to exploit minute imperfections of the circuit, maybe on a quantum level. Small fluctuations in local electromagnetic fields that affected the behavior of the circuit. In that way, the disconnected loop of five could affect the other transistors, and the configuration would not work on other circuits, because they would have different impurities and imperfections.

In the case of the oscillator experiment, when the scientists analyzed the circuit, they found that the circuit was not generating the oscillation voltage wave at all. A nearby computer was producing a wave, and the circuit had actually configured itself to be a radio receiver, picking up that wave, and outputting it as the voltage. The circuit had developed in such a way that the circuit board itself functioned as the radio antenna. That is just so incredibly awesome to me.

So, what's the point here, really? First, these evolutionary means produced incredibly innovative ways of answering the scientists' questions. And most interestingly, in each case, the final solution made use of everything the circuit had available to it. The quantum properties of the chip, or the structure the board, and even things in the immediate surroundings, whatever is available. The adaptation here is absolutely incredible. Just imagine if these experiments were capable of self-configuration? Like a bio-chemical system capable of self-replication, grabbing whatever is available, proteins that function as chemical channels for example, and constructing something amazing like a flagellum. How is that beyond the realm of possibility?

The applications of this kind of problem solving, and the results attained, just astound me. Maybe a project for later.

Haaaaapy Biiirthday tooo Meeeee

2007-07-02T02:19:00.000-04:00

Well, I remarked in my iteration of the "8 Random Facts" post that I was 21, but that was actually a bit of a premature approximation. Well, today's the day, as 21 years ago on July 2nd., 1986, I was born. Just thought I'd let you all know!

Post Gone Due to Suckage Difficulties

2007-06-30T02:38:00.000-04:00

Yeah, there was a blog entry here. But it sucked, so I took it down.

Time Traveling DiffEq

2007-06-30T02:00:00.000-04:00

(I do go on a bit, don't I)

For myself, I tend to think of differential equations best when thinking about them in terms of systems over time. Also, the notation bothers me, so refers to the derivative of the function f, evaluated at some value t.

So, the typical differential equation, sort of the standard you get in most differential equation courses, relates the rate of change of a function over time to the value of the function at that point in time. This relates to most systems. For example, the gravitational force experienced by a falling object is directly related to the height of that object at that time.

But, it seems more realistic in many cases that the rate of change of a system or function will be more related to the value of the function at some time in the past. For example, the rate of change of a population a certain time is related to the number of members in the population who got pregnant some amount of time ago. So instead of , associating the rate of change of the function with the function at that time, which leads to exponential growth, for some constant a you have , so the rate of change at time t is related to the function at some amount of time a ago.

We could consider , for example. But that's not really interesting, to me at least.

I'd much rather consider

This is interesting for a couple of reasons. What we have here is a function y(t). y(t+1) - y(t - 1) gives the difference of values over an interval of t of width 2. Dividing by 2 then gives the average change in the value of the function over that interval. However, y'(t) is the exact rate of change. So, what we're doing here is setting the exact rate of change equal to the approximate rate of change. What does that do, I wonder?

The other reason this is interesting is that we've got a function whose rate of change is dependent not only on the past behavior of the function, y(t - 1), but also the /future/ behavior of the function, y(t + 1). It's awesome. It's like a time traveling function. I like to think of this as the TARDIS function.

So, the question is, how do we solve for the TARDIS function, based on that differential equation?

Honestly, I have no idea. It's crazy. My calc TA last semester had no idea. He broke out all kinds of crazy integration tricks, but it all reduced to things like 0 = 0. I busted it out on my calc teacher next, who is incredibly slick when it comes to math, and he wanted nothing to do with it. So, we're going to play with it.

We're going to assume that the function is analytic. For you, this means that the function can be represented as a power series. For example, consider Cos(x). Cos(x) is an analytic function because it can be represented as the sum of powers of x.

More concisely, we can write this in terms of a summation.

So, we're going to /assume/ that we can write y(t) in the same sort of way. Imagine an infinite sequence of numbers

for i = 0, 1, 2 ...

So we're going to try to use that assumed form of y(t) to solve for the function itself, by using the differential equation to solve for the sequence of

's.

The first thing is to find y'(t). y(t), as we have it, is just a straight up polynomial, though an infinite one, and can be differentiated as such.

So now let's consider y(t - 1). Just plugging into the formula, we get

is not very nice, though. Ideally, we want to get t alone, by itself. And to do so, we will use the binomial theorem.

And then we can rearrange, for our convenience.

By rearranging the summations, the indexes and the bounds, we include all of the same terms, but put them in a more convenient order, allowing us to pull the term out by itself. Which is nice.

What is also nice is that we can go straight to y(t + 1) from that formula. Simply substitute +1 for -1.

And now, having y(t - 1) and y(t + 1), we can do the following, fractoring all kinds of nice things together, moving things about, and blah!

What's nice about is that for even values of n, , which means that when n is even. When n is odd, it equals 1. Which means that in the internal summation for n, we can automatically cancel all the even terms, and drop that factor on the remaining terms. To cancel all the even n terms, we can substitute 2n+1, which will always be odd, for any value of n.

Now we can return to the original differential equation.

Substituting...

Now, notice how on each side, it opens with a summation in terms of k, starting at k = 0 and going to infinity. Also, each term in each summation on either side is a t^k term. Now, there's some theorem I'm forgetting that says that two functions are equal if the coefficients on the powers of t are identical. So, for any given value of k, grabbing the coefficient on the power of t from each side, we get the following equation

We can move the k! to the other side, producing the nicer

Now, to simplify things a little ... watch this. We pull out the n = 0 term from the summation.

And so we have it. If the differential equation is to hold true, the above equation must be true for any value of k, from 0 to infinity. Remember, our goal is to derive the values of , and thus get y(t).

So, the first equation we can generate is to let k = 0. That gives us the following.

It's nice the way that (2n + 1)! cancels. Expanding out, that gives us

In otherwords, the sum of the odd terms of the sequence must be 0. Now, a clear solution to this would be to let all the odd terms equal 0 themselves. Then the sum must equal 0. But that quickly leads to all the other terms being 0 as well, which leads to y(t) = 0. While that is a valid solution, it is trivial and uninteresting!

But there is something important to note here. This equation was for the smallest case, k = 0. And the smallest term of the sequence used is . Because the sequence terms used in the equations increase with k and n, is the smallest term /any/ of them will use. This means that are completely independent to the problem. They can have any value. For example, they could have ... whatever value, and through could all be 0. In that case, y(t) = . And, if you check for yourself, that general quadratic function is a solution to the differential equation.

Boom.

Of course, it's mildly uninteresting, so I wonder if there are other solutions that don't require setting all the other terms of the sequence to 0.

This is where the really interesting part begins, I think.

What we have is a formula for generating equations we want to be true. We want to use those equations to solve for all the for i = 3, 4, whatever. Now, all these equations are linear, since all the variables exist in single powers. An infinite number of linear equations, with an infinite number of variables to solve for.

In the typical case, you have a finite number of equations and a finite number of variables. In the special case of having the same number of equations as variables, you can solve for a single value for each variable. You can do this using linear algebra and something called Gaussian Elimination.

An example is in order, I think. Consider the pair of equations, 3x + 2y = 1 and x - y = 2, and we want to solve for x and y. Take the second equation, and multiply each side by 2, to get 2x - 2y = 4. Now we combine the equations through addition.

(3x + 2y) + (2x - 2y) = 1 + 4

5x = 5

x = 1

By combining the two equations, multiplying one of them by a constant coefficient, and simplifying, we produce a new equation that is the solution for x. It's very handy. You can use this to solve systems of however many variables you want. I do enjoy linear algebra.

That's all well and good, but what I'm interested in is an infinite set of equations, and as many variables. Can I use the same kind of trick to solve for all my

's? Infinite Gaussian Elimination!

I don't know if it works in the general case, but I believe it works here, and it's relatively slick.

Take a look at the first few equations. As I showed earlier, for k = 0, you get

For k = 1, 2, 3,

And so on. The important thing here is that the first term's index keeps moving over. This means that every term appears as the first term of one of these equations somewhere.

Now, I'm getting tired, as it is late, so I'm probably not going to be as rigorous as I should be. As rigorous as I ever am ...

Take the first equation, for k = 0, and multiply each side of the equation by -20. Now, each term of the equation has a -20 in front, but the sum of all those terms (or difference now, really), is still 0. Now, as we did before in the example, add this equation to the k=2 equation, the one with as the first term. The and the cancel, leaving an equation with , and so on, but no . And the equation still comes out to 0. Now, take the equation for k = 4, which has a first term of . We can combine that equation with the one previous, to eliminate the term. And we can keep going, eliminating term after term, except for . Carrying this to its logical conclusion, we eliminate every term but , and the equation still equals 0. Therefore, /must/ equal 0!

In the same way, we can work the equations to isolate every term of the sequence. Use the k=3 equation which starts with to eliminate from the k = 1 equation which starts with . Carrying on again, we get that equals 0! Because of the structure of the equations, the way the first term keeps moving to the right, we will be able to cancel all terms but the first in any equation, and thus show them equal to 0.

By this logic, it would seem that they would all have to be 0. Now, I am sort of making all this up, but in the same way that in the finite case, with a finite number of variables and equations, if there are the same number of variables and equations, there is a unique solution to each variable, in this case we have an infinite number of each, but it's the 'same' infinity, countably many equations and variables. So, does that guarantee that any solution is unique? It would certainly depend on the values of the coefficients on the variables, but here everything seems sound. I really don't know.

The final result seems to be that, assuming y(t) is analytic, it must be of the form . Which is interesting.

So there you have it.

8 Random Facts About a Tyler

2007-06-28T18:35:00.000-04:00

Foxy's already obliged Abbiegenous Retrovirus' blog-tag and posted his entry on this, and now it's about time for me to do the same. Here are the rules:

We have to post these rules before we give you the facts.

Players start with eight random facts/habits about themselves.

People who are tagged need to write their own blog about their eight things and post these rules.

At the end of your blog, you need to choose eight people to get tagged and list their names.

Don’t forget to leave them a comment telling them they’re tagged, and to read your blog.

And here are the facts:

1. People almost invarably assume I'm older than I really am when I meet them. I'm 21, and some people's estimates of my age go into the mid-thirties. Some people go so far as to casually ask whether my dad is my brother when we converse with them out in public, which I guess is either really good for him or really bad for me in the future. And even if people chalk it up to the fact that I usually wear a goatee, his happens even when I don't have any facial hair! It's unreal, and I have a hard time believing I really look that old.

2. The overwhelmingly most frequent pretext for which I've been fired from jobs is "insubordination". Curiously, my dad also bears this distinction.

3. Like Foxy, I haven't always been a math-nut. In fact I was well into high school before I discovered my niche subject. High school math classes are a surefire way to make anyone hate math, and it wasn't until I acquired an interest independently that I decided to pursue serious study and eventually become obsessed.

4. I left high school with an attitude and reputation 180 degrees from the one I entered with. When I got into high school I was disillusioned, antisocial and developed a reputation for being hotheaded. That led to a pretty rocky relationship with my teachers, most of whom though I was more or less "wasting my intelligence". Events proceeding from teachers discovering some "disturbing" writing in my notebooks up to a hospitalization (don't really want to go into the details) changed things. My teachers and parents really intervened to help steer me straight, and my interaction on that level made me realize how skewed my perspective of the world was from the years of ostracism and harrassment I endured from my peers from my first day of school (due to my "eccentric behavior", as is typical in such cases).

5. I play a lot of Japanese video games, and even import a game or two occasionally (I have Japanese copies of Ikaruga and Power Stone 2 for the Dreamcast). Old-school is the best, with game-legacies like Contra, Gunstar Heroes, Metal Slug, Castlevania, and Radiant Silvergun coming out way above modern stuff like Grand Theft Auto III+.

6. Every computer I've owned from the second onward (excluding the one Mac workstation I've owned) has been built from off the shelf parts, and every one from the fourth onward has had GNU/Linux in some form either exclusively or with other operating systems. My first computer, which to date is the only one I've ever owned that was bought from a white-box manufacturer, was a K-Pro IBM compatible from the late 80's, given to me by my dad.

7. I love Italian food in all of it's forms, but you could probably already guess that. I hate any kind of tomato with meat in it, however (I don't hate meat, just meat sauce). IMO the best kind of sauce involves fire-roasted tomato, with a strong garlic flavor.

8. I'm addicted to reading. Often times I get so wrapped-up in reading things and get lost in time the same way I (and many others) get lost in video games.

Well, that's done. For tagging, I'm just going tag anyone who reads the blog, which he is correct in saying is probably around 8 people. :)

Time Traveling Sequence

2007-06-28T16:19:00.000-04:00

I should be very interested in a sequence of numbers for k = 1, 2, 3, ... such that

is true for any k.

Webster Trolls My Blog

2007-06-28T14:23:00.000-04:00

Well, well well. I go to my Haloscan account to delete a spam message and I find that Webster, who made an appearance at ERV receently, has now trolled my blog under the radar. Well, he's just as stupid and ill informed here as he was there, so on the fisking:

"The "no useful solutions" mention was to show that Dawkins's model is likely to get at least something right even without figuring in any selection."

No, he's not. The selective mechanism is what winnows down the solution. Random iterations across 29 character spaces without any selection from the results isn't likely to give you "METHINKS IT IS LIKE A WEASEL".

"It is far from meaningless to point out that Dawkins's little program is deterministic. The evolution portrayed therein does not merely have a purpose, it has an *end* already built in from the beginning -- in other words, it only models design! Remember Michelangelo's description of how he sculpted Moses? Paraphrased, it went like this: "I chisel away whatever does not look like Moses." In this program, the computer "chisels away" whatever does not look like the weasel words."
b(x = 3) = 6.48 %
…
prob(x = 2 = 8.35 x 10^(-41) (exp notation added)"

Dude, have you even taken a basic probability course? What they gave were not the space of all possible outcomes of a random iteration that completely discounts selection but the probability of finding a solution given Dawkins selection criteria. One is a combinatorial calculation (one often used to give misleading ideas on the probability of evolutionary outcomes) one is statistical. They were, in other words, dishonestly claiming some discrepency between Dawkins "deterministic" program and "random" evolution. In the latter they usually discount selection to present ridiculously low probabilities for "randomly" getting a protein or some other feature. Evolution is not random, it is selective.

And that is why the sculptor analogy is flawed. A culptor doesn't operate by randomly poking away at a stone and only keeping those changes that look like a given target, he winnows dows a static target. Evolution operates by tossing up concepts and culling the pool down through differential reproductive success.

Bzzzzzt. You're the one wrong again! Have you ever heard of extinction? That's when no organism in the evolving population remains sufficiently viable to carry on. As far as I know, it still happens, even in an evolutionary paradigm, right? OK, so Dr. Batten's point is that few (if any) GAs account for that possibility."

Then he knows even less about GA's than I took him for, as extinction (or at least a rough analog for solutions to common mathematical or engineering hurdles) happens in your garden variety GA's as a matter of configuration (that's how they work). GA's maintain populations of solutions to given problems (often NP-hard problems as heuristic solutions) and those that get out-performed are killed off. However, if you don't take into account heredity/retention, which Batten blatantly ignores, you don't have any evolutionary process.

"Actually, the selection coefficient is *highly* relevant, and it relates to much more than the speed of the algorithm. Even a favorable mutation, if the selection coefficient is reasonable, is unlikely to propagate more than a few generations, due to genetic drift. A selection coefficient of 1 (or anything like that) distorts the model beyond any hope of utility."

I never said it only "related" to the speed of the algorithm, and I didn't say that selection coefficients themselves weren't relevant to GA's. I said it was increased to make the algorithm operate at a faster speed. Really, have you ever heard of running-time complexity analysis? A computer algorithm that took, oh say, an interval on geological time scale to operate wouldn't exactly be considered "efficient". It's an irrelevant observation to say that selection coefficients have to be higher for something that has to find a solution exponentially more quickly.

"And your precious AVIDA is a red herring, since the results were, once again, programmed in from the beginning, though more subtly than in the Dawkins example."

Point out exactly where the results were "programmed from the beginning" in AVIDA.

"Of course, there is no purpose in evolution, just random mutations within DNA," according to NOVA. MIT Professor Manolis Kellis: "Evolution doesn't have a purpose." Individual creatures may have purposes, but evolution is a description of an impersonal process, not an anthropomorphized Force."

Setting aside the probability that this is a serious quote-mine, it looks like he's talking about purpose in a teleological sense (judging by his use of impersonal) rather than a mechanistic sense. This is nothing but flagrant equivocation.

8 Random Things About A Fox

2007-06-28T00:07:00.000-04:00

Tagged by ERV, that sly vixen. Eight Random Things about me.

First the rules.

We have to post these rules before we give you the facts.

Players start with eight random facts/habits about themselves.

People who are tagged need to write their own blog about their eight things and post these rules.

At the end of your blog, you need to choose eight people to get tagged and list their names.

Don’t forget to leave them a comment telling them they’re tagged, and to read your blog.

Eight things. Eight is a good number. 8 is 2³. Consider too, 3² = 9. I do believe I've read somewhere that 2³ and and 3² are the only non-trivial integer powers separated by 1. Which is neat. Anyway.

Favourite number is 4 - the only number that is both the sum and product of its prime factors.

The fox was not my first form, and it shall not be my last. And whoever shall live and believe in me shall receive eternal life.

I loooove turning left. It's like a really good stretch.

I run Windows XP on my laptop. And have never had an issue with it. Never. Blue Screens, Freezeups, nothing. No security problems ... it's just ... it works.

Heroes include, in no particular order, the Doctor and DadFox.

I have two memories that I can't really explain, from my childhood. In each case, I was flying.

I've seen absolutely loads of movies. Loads. I can name over 600 actors. I've seen all kinds of movies. I've seen all eight Halloween movies. Don't see number five - it's so not worth it. I've seen movies that made me want to stop watching. The original When A Stranger Calls. The new Texas Chainsaw Massacre. I've seen movies that I never want to see again. This includes, but is not limited to Nymphoid Barbarian in Dinosaur Hell, Jesus Christ: Vampire Hunter, Werewolf in a Girl's Dormitory, and Monster. However - HOWEVER - the only movie I recall consciously not finishing is Python II. No reason. Just ... I didn't finish it. Huh.

Up until about ... 5th or 6th grade, I was not a math sort. I read. I read loads. We used to keep reading logs, and every Monday I would bring in just a huge stack of books that I'd read. I read everything. So many books. So many. I can barely remember them now. Nothing stands out. Then ... I just stopped. I remember the first book I bought that I didn't read. P.D. James' Death of an Expert Witness. I'll get to it someday. And then, shortly after I stopped ... math - BAM. And here I am.

I tag ... anyone who reads this blog. Which has to be at least eight people. And Dick Cheney.

Flying Blind

2007-06-27T13:45:00.000-04:00

100 people are waiting to board a plane, each with an assigned seat. The plane has 100 seats, so the plane is to be completely filled. One of the passengers is blind, and thus boards first. The rest of the people have queued up in a random order, to enter the plane one at a time. Now, being blind, the man cannot find his own seat, and thus selects a seat at random. It may be his seat, but of course it is much more likely that it is not. As the next person boards, he tries to take his assigned seat. If the blind man took his seat, he chooses a seat at random and sits there. Each person boards the plane in the same way, taking there assigned seat, or choosing one of the remaining seats at random.

All that being so, what are the chances the very last person to board gets his own seat?

Bonus points for brevity, creativity of solution, and drawing in as much esoteric math as possible. 10+ automatic bonus for each transcendental number you use. Points will be deducted for reliance on supernatural entities.

Neat Recursive Function

2007-06-26T10:47:00.000-04:00

I have to say, one of my favourite things about the banner is that it looks like I have a little 'i' on my nose. I wonder what that means, philosophically.

But, take the function P(n). We'll define P(1) = 1, and P(n) is defined as the sum of the products P(a)*P(b) such that a + b = n, for all a, b. More succinctly,

So, P(2) = P(1)P(1). P(3) = P(1)P(2) + P(2)P(1). P(4) = P(1)P(3) + P(2)P(2) + P(3)P(1). And on and on and on. Actually calculating each value, you produce the sequence

1, 1, 2, 5, 14, 42, 132, 429, 1430, ...

The function itself interests me in a number of ways. First, theres the matter of what the function means. It seems like there's an interesting combinatorial interpretation I'm just not getting. For example, suppose P(n) is the number of ways of grabbing n many objects in two grabs. Take P(4), for example. In the first grab, you could get 3 objects, then 1 in the second. Or 2, then 2, or 3 and 1. And the total number of ways is the sum of the products of the number of ways to grab things in each grab. I'm not sure how well that kind of interpretation holds up though, since recursively you would come out with 'half grabs', or something like that. However, combinatorics has never been a strong suit of mine.

But what we're interested in is deriving a non-recursive form of the function. Consider, for example, f(n) = n*f(n-1) and f(1) = 1. A simple recursive function. Unwrapping it, we get, for f(4) for example, f(4) = 4*f(3) = 4*3*f(2) = 4*3*2*f(1) = 4*3*2*1. That is, of course, 4!. For any n, you can show that f(n) = n!. We want a similar non-recursive formula for P(n).

Now, like I said, combinatorics has not been my strong suit. So this is very much more 'math experimentation' than any kind of logical working out and problem solving. Which of course makes me despair for my mathematical ability. I'm such an insecure fox. But the function definition, as it stands, is simply ridiculously complicated. To solve for a non-recursive form, we would want some way of unwrapping it, making it less recursive, or separating one term from all the other terms before it. As it stands now, because of the ridiculous amount of self-reference, it's very hard to do anything with that function in the form it is. So ... we're going to try a different approach.

First off, it's interesting to note how fast the values grow in the sequence. In 'standard' sequences, this would normally be indicative of some kind of exponential or factorial growth. In either case, it is interesting to look at the ratio of successive terms in the sequence. Doing so with the first 15 P(n), and plotting them, we get

Now, I don't know about you, but it certainly looks like a familiar shape. At the very least, it looks like it's going into a horizontal asymptote, though I admit it could be logarithmic. It looks like it's growing too slowly for logarithmic, though.

Because of the high level of recursion in the function definition, it becomes impractical to calculate more than about P(16) in Mathematica, since the number of recursive calls and subrecursive calls grows so rapidly for P(n) as n increases. This is because when P(n) is calculated, P(n) depends on every value of P from 1 to n-1, and each of those must be calculated, but each of those depends on other values of P, which also must be calculated. It's absolutely titanic.

A much better approach is to save each value of P(n) as it is calculated, using to calculate further terms. Writing up a quick ruby program,

vals = [1.0]
2.upto(200) do |n|
total = 0
1.upto(n - 1) do |i|
total += vals[i - 1]*vals[n - i - 1]
end
puts total/vals.last
vals.push(total)
end

Several hundred terms can be calculated in a snap (though the size of the terms rapidly exceeds the largest allowable number in Ruby). Looking at the ratios of successive terms, it appears that P(n+1)/P(n) approaches 4. The program gets into the 3.98 range before crashing because the numbers are so titanic.

So we'll assume that the ratio limits itself to 4. In that case, it is interesting to consider 4 - P(n+1)/P(n). The first 15 or so terms are calculated and plotted below.

Now it looks even more familiar. I'd say that function is something related to 1/n or something similar. 1/n², some sort of rational function. Whatever it is, though, it would be interesting to look at the reciprocal. Plotting the reciprocal would give us an idea of what the denominator of that function looks like.

And so we plot 1/(4 - P(n+1)/P(n)) for the first few values of n. And we get the following.

And that is awesome. It's so linear, it's ridiculous. And looking at the values, it's easy enough to calculate the formula of the line. 1/2 - 1/3 = 1/6. 2/3 - 1/2 = 1/6. The difference between any two terms is 1/6, just going by that list. So we're looking that (1/6)*n + A, where A is some constant. The first term is when n = 1, so (1/6)*1 + A = 1/3, gives A = 1/6. So we have the formula of the line, (1/6)n + (1/6), or, much more better, (n + 1)/6. BOOM.

Now we can go crazy.

Because we have a tentative formula,

Which is awesome, when we do the following.

And that is awesome. Because now we can do something like this.

Where 'stuff' is recursively nesting the factorial term, until reaching a call to P(1), which is 1. Now, all these terms can be grouped together. On the bottom, we have n*(n-1)*(n-2)*...*2*1, which is clearly just n!. On the top, we have a bunch of factors of 2. Each term in the main product carries a factor of 2. There are n-1 terms (since the nth term is P(1)), so there is a factor of 2^n-1. Now, the numerators of the fractions ... consider n = 4. Then as we combine the numerators, we'd get (2(4 - 1) - 1)(2(4 - 2)-1)(2(4 - 3)-1) or (5)(3)(1), or 5!!. You remember the double factorial ^.^ In general then, the numerator of the combined fractions will be the product of some sequence of odd numbers (since they all have the form 2*N - 1), and specifically, they will form an odd double factorial, (2n - 3)!!. And thus we have

Check that out for yourself. It works.

Now, I haven't yet 'proved' this is the non-recursive definition of the recursive function. It was only a complete guess that 4 was the value of the asymptote. If it had been some strange number, this certainly would not have worked. But, now that I have, tentatively, what the form is, it should make it that much easier to prove that it is equal to the recursive function.

A project for later, I guess. Things to do, things to do.

Shorter Dan Riehl and Misha

2007-06-26T02:28:00.000-04:00

Slut had it comin'.

When I first caught wind of the murder of Jessie Davis and heard the details, the first thought that entered my mind was along the lines of "Jesus tap-dancin Christ on a stick, the media's found another Simpson/Peterson/Halloway case to obsess over in lieu of real news!" After the initial reaction, I realized that this incident was more or less ripe for misogynistic victim-blaming from the usual suspects. Right blogistan did not dissappoint.

A Specified Persecution Complex

2007-06-26T01:16:00.000-04:00

Recently some figures in the science blogopshere have commented on the case of Dr. Johannes Lerle, a recently jailed German pastor. Some religious nuthouses in right blogistan have donned the cross and claimed it was due to persecution of him for his pro-life views. Now (Hat Tip: RWP) we see that Bill Dembski, the venerated mathematicial prodigy of the Intelligent Design movement (at least in the eyes of his sympathizers) has chimed in with the real cause of his arrest: his advocacy of Intelligent Design Creationism.

Except for one teeny-tiny problem: he was arrested for denial of Holocaust.

The lengths that a significant portion of Christians will go to justify their paranoia of persecution are nothing short of staggering. Just look at the comments to the turd that Dembski dropped over at UD, not even a hint of skepticism or the need for further investigation. After all, these are ID (and more specifically, Dembski) flaks, and they don't need further investigation because they already possess THE TRUTH: that there is a gigantic secularist conspiracy to jail them. The only effective response to such a persecution complex is as follows: "no, I'm not putting the nails in, come off the damn cross already."

As for Holocaust denial prohibitions themselves, I harbor some ambivalence. On the one hand my American free speech absolutist sensibilities would never welcome such laws here, and I think that such laws have outlived their purpose and are now counterproductive in Germany. On the other hand I can certainly understand the political context in which they were instituted, and it would certainly be presumptuous of me, as a non-German, to attempt to dictate politics to those in a foreign socio-political culture. But even so, to claim that this is all a manifestation of a coordinated secularist effort to suppress Christianity is nothing but conspiratorial claptrap, and is quite indicative of the sort of political foes we are dealing with in our fight against the religious right.

Reg Golb Medalion: George Gilder

2007-06-25T02:40:00.000-04:00

In all the blogginess I've found myself engaging in over the past month or so, I've managed to neglect my semi-regular "super duper idiot" award. These sorts of awards are common on other blogs, examples are Ed Brayton with the Robert O'Brien Trophy and PZ Myers with the Pastor Ray Mummert Award. Mine is named after a rather pernicious and exceptionally stupid troll I encountered on Scientia Natura going by the hangle "Reg Golb". However, through the fog of blogging, writing code, sitting on my ass playing video games, working out and even occasionally doing social thingies, I've found a moron sanctimonious enough to warrant my personal accolate.

Behold George Gilder, a Renaissance huckster whose developed a reputation in manifold disciplines as one of the most loathsome con-artists ever. As an economic pundit he's famous for wildly grandiose techno-utopianism that caused just about everybody taking his investment advise during the dot com boom to go broke. As a politico-economic pundit he's famous for inspiring Reaganomics. And nowadays we find him gibbering on about evolution and braying his ignorance far and wide on issues involving "intelligent design". But this interview, courtesy of the incomparable PZ Myers, collects all of his ignorance and stupidity into one, big, steaming and certainly RG Medalion worthy pile of shit:

I believe that the universe is hierarchical, with creation at the top - the idea that there's a creator and that we, at our best, act in his image. This top-down model is what all of my work has in common. I sensed that the basic flaw and failure of feminism was its gradient toward pure animal passion with no procreative purpose. In economics, I believed that it was the supply that created the demand. In my examination of computers and telecom, and subsequently biology, I saw the same thing. That's really how I came into the intelligent design movement - through the recognition of this same structure that I'd previously examined in sexuality and economics, information theory, computer science and network theory.

I have no idea what he means when the universe is "hierachical" with "creation at the top". I would think, being the creationist loon that he is, would see everything as "creation". I get the sense that what he really intends to convey is the classical religious notion of god on top, angels below, man below them, women steeply down the ladder with animals and children slightly below them. And indeed, his view seems to be nostalgic for the 18th. century in every way, shape and form. For one thing, his knowledge of economics seems to have stopped somewhere before Pareto and Marshall, both of whom (especially Marshall) would have scoffed at Gilder's horrendously economically innumerate claim that "supply creates demand". Hell, in viewing economics through the prism of "hierarchy", Gilder is far closer to Marx, Engels, and Weber than he is to Friedman or even Keynes. He may not even have gotten past Jean-Baptiste Say and Adam Smith, who pioneered the idea of the "invisible hand" that did not require direct government intervention to function.

And his views on feminism are nothing short of the classic case of a white-male patriarch threatened by the fact that a substantial portion of the female population refuses to subordinate itself to the role of the baby factory. Shunning sex without "procreative purpose" is more or less another way of saying "you shall neither display nor feel enthusiasm for sex without male approval".

And as for his view on evolution, well, let's just say you'll probably need some padding to make sure you do not attempt to smash your head against a monitor:

I'm a religious person. So are the Darwinians religious people: They believe in an anti-religion of materialism that liberates them to pursue pleasure any way they wish. It's the highest purpose of their existence. They thus believe in a random, futilitarian universe where - if they're existentialists - they might imagine that occasionally a heroic human being could assert some purpose above the froth of randomness, but in general, we're all doomed to decay and destruction. That's pretty much the philosophy, and it's debauched a whole century of intellect. I think we're going to transcend it in the 21st century

Hmmm...let's see. The 20th. century not only saw tremendous achievements like the discovery of DNA, the sequencing of the human genome, the formulation of relativity and quantum theory, the transition of cosmology to a hard science, the rapid advance of computing and information theory, leading to mass communications and the internet, breaking the sonic-speed barrier in flight, the exploration of space, and the development of a true global economy, but has seen countless medical and other technological advancements that have doubled lifespans and eliminated previously devastating diseases. All the while, Gilder's intellectual hobgoblin of "Darwinism" has clearly been ascendent among the intelligentsia. That's more than I'd expect from a pradigm that had "debauched a whole century of intellect". Perhaps, much like the designer, such debachery is simply invisible and unknowable (and naturally, any elucidation of such is avoided at all costs by IDiots like Gilder).

So congrats, Georgie, you are the recipient of my latest iteration of "The Reg Golb Medalion". Stand tall and proud.

A Preview

2007-06-22T21:12:00.000-04:00

I want to give a preview of the aesthetic direction we're taking on the next blog Foxy and I are working at. The blog itself will have much the same subject matter, of course, but the theme and style will be different. The art direction is heavily inspired by the Korean cartoon franchise Pucca and Nintendo games (primarily the various Mario incarnations). But that does not mean we're going kid-friendly, quite the opposite. My object is to mix cartoony cuteness with our usual enthusiasm for math and abrasive denunciation of teh stupid. I delegated the artistic responsibilities to my incomparably talented sister, Nio DiPietro. And since a picture is worth a thousand words, here is her first work on the project: our new banner.

What Would Mulder Say?

2007-06-22T13:24:00.000-04:00

According to the BBC, the CIA (I love three letter abbreviations) is going to be airing out its secrets, releasing several hundred pages worth of documented abuse from the 1950's through the 1970's. You'll be happy to know that this is part of the CIA's past. Nothing like the present, no.

Not that I hate America or anything. I'm just fascinated by the way the CIA works. Somewhere around the FoxDen, I have this little green book that documents various CIA assassination attempts of various world leaders. Two of my favourites were the plan to put itching power in Castro's wet suit, and another attempt in which some little rebellious fellow was given a machine gun and sent into the room where the World Leader in question was having a conference. Managed to kill everyone - except the target. What a bunch of geniuses.