Friday Random Ten 4/28

1. Spock's Beard, "the Planet's Hum". Another one of those neo-progressive bands I love.
2. Flook, "On One Beautiful Day". Very cool Irish.
   
3. Dream Theater, "Honor thy Father". Neo-progressive/prog metal by a great band.
4. Philip Glass, "Les Enfants Terrible, Scenes 10/11". Part of an opera by Phil Glass. Magnificent.
5. Bela Fleck, "Katmandu". The master of the banjo.
6. David Sylvian and Robert Fripp, "20th Century Dreaming". Fripp and Sylvian did one album together a few years ago. If you like Sylvian's crooning vocal style and Fripps bizzare tonalities, this is great, great stuff.
7. Trout Fishing in America, "It's a Puzzle". The song with my favorite lyrics of all time: "Is is till it isn't, then it was; was was till it wasn't anymore; maybe might be an is in a second".
8. Lunasa, "Bolton St/The Millstream/Loophead Lighthouse". The best traditional Irish band that you'll ever hear.
9. King Crimson, "Dangerous Curves". Highly bizzare and wonderful instrumental by that great band of lunatics, KC.
10. Kaipa, "Sonic Pearls". Really great neo-progressive from the first band that the founder of the Flower Kings performed with.
    
    

The ABCs

This seems to be circulating around the geekish blogs, so I figured why not?

Accent: New York. Not the Brooklyn NY. But I definitely say "bawl" for ball, and "cawfee" for coffee.

Booze: Grappa. I positively adore grappa. (Terrifyingly, it was one of my daughters first words. We were in Italy on vacation when she cut her first molars, and everyone says that rubby a little bit of brandy on the kids gums helps. She loved it, and tried to get more.)

Chore I hate: folding laundry.

Dog or Cat: Both; one small tuxedo cat, and one large golden retriever. I prefer dogs, but do adore both.

Essential Electronics: My powerbook. My ipod. Who could live without those?

Favorite Cologne: I despise all colognes, perfumes, and other stinky things that people put on themselves. Ech.

Gold or Silver: gold. I don't really care much, they're both pretty, but silver is so hard to take care of.

Hometown: I was born in Bound Brook, NJ; grew up mostly in Bridgewater, NJ; four-year stint in Findlay, Ohio in between.

Insomnia: when my wife snores. Also known as "most nights".

Job title: Research staff member.

Kids: Two, one girl 5yo, one boy 3yo.

Living arragements: House on a cliff in Westchester county, NY.

Most admirable traits: wait, I'm supposed to have admirable traits? No fair!

Not going to cop to:

Overnight hospital stays: As an adult, just one, for a nissen fundoplication to fix a pretty-much nonexistent sphincter at the top of my stomach. Not fun, not recommended; but people like me used to die of esophageal cancer; now I just have horrible cramps and trouble swallowing.

Phobias: Crowds.

Quote: "I'm not dumb; I just have a command of thoroughly useless information" -- Bill Watterston.

Religion: Judaism, particularly the Reconstructionist branch.

Siblings: One brother (older), one sister (younger).

Time I wake up: Around 7am.

Unusual talent or skill: Wait, doesn't this sort of connect to that "most admirable trait" thing? Oh, wait, it doesn't need to be admirable, just unusual. Ok. Let's see. I can trip over nothing, is that a skill?

Vegetable I love: Hard to pick one. Either chinese brocolli or snow pea greens.

Worst habit: procrastination. Why do you think I'm doing this?

X-rays: Too many. Mostly abdominal, related to the problem that led to the surgery mentioned above.

Yummy foods I make: Another one with a lot. At one point when I was in grad school, I seriously thought about dropping out and opening a restaurant. A few of my favorite things: rare seared duck breast with ancho-honey sauce; hong-kong style braised fish with tofu; catfish with dashi sauce and soy syrup; brandied chicken risotto w/portabello mushrooms.

Zodiac sign: Leo.

Cyclic Groups

There's an interesting kind of group called a cyclic group. Cyclic groups are interesting buggers: they express the symmetry of rotation in 2 dimensions, and the symmetric properties of addition in integers. They even tie together the idea of an exponential power series with the basic structure of the integers.

So what is a cyclic group?

A cyclic group of size N (often written Z_N) is a set of N values with a "circular" relationship. The reason for the scare-quotes is that there is an infinite cyclic group, which doesn't close - it's the set of integers. If the cyclic group is finite, then you can see it as a circle of values. You can draw a cyclic group very easily: here's the cyclic group of size 5:

To really explain what a cyclic group is, we can formulate it in two ways: modulo arithmetic, and power series. They're quite different formulations at first glance, but they are entirely isomorphic, and the correspondance is quite easy to see.

Cyclic Groups as Modulo-Arithmetics

The first way is something called modulo arithmetic. Modulo arithmetic a kind of arithmetic that uses a finite number of positive integers. For each positive integer N, there is a modulo N arithmetic (sometimes called modN for short). In modN, N=0=identity; if you add two numbers in modN, and the result is greater than N-1, you wrap back around zero.

Since that sounds confusing, here are a few examples in mod5:

1+2=3
2+2=4
2+3=0 (2+3 = 5 in non-modulo; in mod5, it wraps back to 0)
3+3=1 (3+3 = 6 in non-modulo; in mod5, it's 3+2+1=0+1=1)
4+4=3 (4+4=8 in non-modulo; in mod5, it's 4+1+3=0+3=3)

Another way of thinking of modulo-N arithmetic is that after every addition, you do an integer divide by N, and take the remainder. The remainder is the result in modulo arithmetic.

And finally, the easiest way to think of modulo-N arithmetic: remember the idea of a number line from elementary school? Take the number line starting at zero. Cut it at N. Take what's left, and curl it around so that it forms a circle.

Just like you can do addition by stepping on the number line (3+4 is start on three, and take four steps forward), you can do addition by stepping around the modulo-N number circle: 3+4 is start on 3, and take four steps forward along the circle.

Cyclic Groups as Generated Power Series

The other way of viewing a cyclic groups is as a power series generated by a single value. For a number X, there is a cyclic group of size N whose values are X^0 (the identity value), X^1, X^2, X^3, ... , X^(N-1). (note: this was corrected based on comments: the last entry was originally X^N, which is a group of size N+1, not N.)

The group operator in this formulation is basically just multiplication; the identity is thus X^0. The one little catch is: if we're looking at a finite cyclic group, then the multiplication operation "rolls back" in a manner exactly like modulo arithmetic. Again, it will get clearer with some examples. For a cyclic group of size 5:

N^0 * N^4 = N^4
N^3 * N^1 = N^4
N^3 * N^3 = N^1 (N^3*N^3 = N^6, which "rolls over" to N^1.)
N^4 * N^3 = N^2 (N^3*N^4 = N^7 which rolls over to N^2.)

As you can see, if you look at the members in terms of exponents, then the multiplication operation behaves as modulo arithmetic on the exponents.

Cyclic Groups and Rotational Symmetry

If you look at my corrected explanation of group operations from the other day, you should be able to see how a cyclic group expresses rotational symmetries. For example, if you take a set of the vertices of a pentagon, and look at Z_5 as a group operation, then the values in Z5 correspond to the five possible symmetric rotations of the pentagon. For example, the member of Z_5 labeled as "1" in the diagram above is the permutation function:

{v1->v2, v2->v3, v3->v4, v4->v5, v5->v1}.


Concluding Note

Today's going to be my last post on group theory for a while. There's plenty more to say about it, but group theory isn't my specialty, and since the next couple of weeks are going to be very busy for me, both at work and at home, so I'm not going to have the time to write about something that requires so much background reading. So I'll be moving on to other things for a while after today, and I'll get back to more group theory at some point.

Britain has a very cool judge

Just saw this over on slashdot and BBC news:

As you may have heard, the author of the dreadful book "The DaVinci Codes" was sued in a British court for plagiarism of an earlier non-fiction book. The judge who wrote the ruling on the case embedded an encrypted message into the decision, by italicising letters scattered through the text.

I haven't seen the solution yet; according to Slashdot, the italicized letters in the judgement are (corrected from my original post, which already contained a correction from the original slashdot posting): "smithycodeJaeiextostpsacgreamqwfkadpmqv". (Thanks to the anonymous commenter who pointed out the missing "v".)

I doubt that I'll have time to look at this before someone comes up with a solution, but I thought the people who read this blog might be interested in this little puzzler.

Groups, Subgroups, and Group Actions, Oh my! (REVISED)

Sorry for the bad title. While I was working on this, it popped into my head, and it won't go away. If I'm going to go crazy hearing that in my head, you can too.

Today's a bit of a definition day. To be able to really show how some of the stuff I've talked about informally works, you need to know some terminology. Don't worry - it's not entirely dull! (I'm also rather overtired this evening, so don't be surprised if some typos slip through; please let me know if you notice any.)

(Update: as the comment above indicated, I originally wrote this in a hurry while overtired. This was a very bad idea. As a result, it has been substantially rewritten to fix it up.)

Subgroups

I've mentioned subgroups briefly once or twice; it's worth pulling it out and making it first class here.

A subgroup S of a group G is a group with the same group operator as G, and whose members are a subset of the members of G. Because the subgroup is also a group, that means that it needs to be closed under the group operation and inverse. To be precise:

A group S is a subgroup of G iff:

members(S) subset members(G)
all x,y in S : x*y in S
all x in S : x^-1 in S

There is a particular kind of subgroup that is interesting, called a normal subgroup. A subgroup S of a group G is a normal subgroup of G if/f:

all x in G : (all y in S : x * y * x^-1 in S)

Another way of writing that is:

all x in G : x * S * x^-1 is a subset of S

It happens to be provable for normal subgroups that the "is a subset of" up there can actually be replaced by "=".

A group is an Abelian Group if/f the group operator is commutative:

all x,y in G : x * y = y * x

If a group is abelian, then all of its subgroups are normal.

A trivial group is a group containing only the identity value.

A simple group is a group whose only normal subgroups are the trivial group and the group itself.

Group actions

We're getting closer to being able to talk about the fun stuff. But we need to talk about group actions.

A group action is something that you can create by treating the members of the group as mappings. The way that you can do this is related to the symmetric groups.

The other day, when I talked about the symmetric groups. I defined the symmetric group of order N as a group over the integers from 1 to N. You can also define the symmetric groups in another way: the symmetric group over a set A is the set of all permutations of the members of the set. The symmetric group over a set A is written S_{A} The two are just different ways of expressing the same basic thing: the group of all permutations over a set of values.

Now, also remember that every group is isomorphic to a subgroup of some symmetry group. What this means is that given an appropriate set A, any group is equivalent to a permutation group over the set. Each member of the group is a function mapping A to A. The group action of a group G is a homomorphism from G to the symmetric group over A, S_{A}.

If you have a group G and a set A, then a group action of G on A is a function f such that:

• all g,h in G : (all a in A : f(g*h,a) = f(g,f(h,a)))
  
• all a in A : f(1,a) = a. (where 1 is the group identity element).
  

That's really a hairy way of saying:

1. There's a mapping from elements of the group to functions over the set;
   
2. Performing the group operation on the elements of set according to the mapping applies a symmetric transformation to the set.
   

Remember when I talked about the symmetries of a pentagon? Rotation, mirroring, etc. Well - for each of those symmetries, there is a group whose operation defines the particular kind of symmetry; and we can define the symmetry on the pentagon figure by applying the group to the set of vertices of the pentagon. For example, there's one group which describes rotational symmetries; for a pentagon, it's a cyclic group (I'll talk about what cyclic groups are later) with 5 elements; each element corresponds to one of the five possible symmetric rotations of the pentagon.

Dembski and Displacement

I've been requested to comment on a relatively recent paper by Dembski,
Searching Large Spaces : Displacement and the No Free Lunch Regress, in which he essentially attempts to use his "No Free Lunch" theorem to show that something like evolution requires an intelligent guide.

Frankly, I'm pretty tired of talking about Dembski; but I think this paper is interesting in a few ways: it's blatantly dishonest in a way that's unusual even for Dembski; it demonstrates some classic creationist misdirections; and it demonstrates what the ultimate point of NFL is for Dembski.

The Blatant Dishonesty: Uniformity

As usual, Dembski is using his No Free Lunch (NFL) theorems as a way of arguing that evolution couldn't possibly have produced life as it exists on earth. But it's got the same problem as all of this other NFL stuff; in fact, it's got the same problem in an even more extreme form. Dembski's argument models evolution as a search function; and it treats the search space as perfectly uniform.

Yeah, if you've got a perfectly uniform search space, and you want to search it with a fixed search function, then guess what: the probability of your search finding its target is damn poor. Yippee. Not exactly a profound statement.

The "novelty" of this paper is that it also considers various kinds of meta-searches: that is, searches where instead of just choosing a search function, you use a search to find a search function well-suited to the search space.

Guess what? If you've got a uniform search space, then searching for a good search function that can find the target doesn't work well: the probability of finding a search function that will find the target even lower than the probability of a random search function finding the target. Going blindly meta on the search isn't better than just doing a blind search; in fact, it's worse.

This is not a profound result.

But the real problem here, the real fundamental dishonesty, is that Dembski continues to use a deliberately ridiculous model - one whose errors have been pointed out to him numerous times, and which he continues to ignore. He models evolution as a search for a specific target in a uniform search space using a single fixed search function. His concession to the criticisms of this model is to allow the search function to be stochastic - which is really no concession at all. (A stochastic search function doesn't pick a direction for the next step of the search; it assigns probabilities to the various directions that you could progress in, where the probabilities are its guesses about how likely you are to find the target in that direction.

Evolution is not a search using a fixed search function over an arbitrary uniform space. The search space is not uniform; the "search function" is not fixed; there is no specific target. It's the same old nonsense: if you create a model of the evolutionary process which eliminates the properties that make evolution work, then you can use that model to show that evolution doesn't work.

Dembski even pulls out that favorite creationist canard: the old "probability of a protein 100 amino acids in length". Dembski knows full well that this is garbage - it's been pointed out to him numerous times. But he doesn't let that stop him - and it's a perfect demonstration of exactly what's wrong with his entire argument:

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^100, or approximately 1.27x10^130.

No process in evolution searches for a specific protein. Not every chain of amino acids is even possible. The "probability space" of protein chains is very non-uniform: because of geometric constraints, some chains are very likely; some are very unlikely; and some are impossible. So if you want to model a search for a protein, the search space is not a search for 1 in 20^100; it's a search for some protein which is suited to some purpose (which is likely a family of similar proteins) in a non-uniform search space in which some things are far more likely to appear than others.

This is exactly the problem with all of Dembski's NFL arguments: the insistence for uniform search spaces; the insistence on a single fixed target; and the insistence on a single fixed search function.

Misdirections

The fundamental point of this paper is to try to turn NFL into some kind of support for intelligent design: it wants to argue that blind searches can't work, and that directed searches can work, but only if they have intelligent guidance.

It's a total misdirection. He's structured things so that no search can work unless you know how to get to the target in advance, and then argues that you can't get to the target unless you know it in advance. Phrased in simple english, this is incredibly obvious. But Dembski plays the standard trick of creationists: dazzle you with so much verbose nonsense and impressive-looking math that the tautological nature of the basic argument is hidden.

Here's an example:



What the heck does this mess say? If you used a meta-search to add information to a search function, then you used a meta-search to add information to a search function.

The Point: Dembski's Agenda

This paper is by far the clearest demonstration of exactly what the point of all of Dembski's NFL stuff is about. Dembski wants to argue for intelligent design. He's trying to create a mathematical argument for why there must be an intelligent guide for evolution to work. His agenda for this is to argue that first, there's no way that simple unguided evolution can possibly work. That's the basic NFL stuff. This paper augments that: it tries to show that it can work if the process is guided - but only if the guide has the property that its guidance adds information to a search through its guidance; and finally, he wants to argue that no random process can create a "guide" for search that adds information - the guide must be an intelligent being.

It's intelligent design expressed through mathematical misdirection. By carefully structuring things, and throwing lots of math around, he builds the assumption that an intelligent designer is needed into his framework, and then uses that framework to show that an intelligent designer is needed.

Permutations and Symmetry Groups

One group that's particularly interesting to CS guys like me is called the symmetric group. The symmetric group is, in one view, the first step towards something called Category Theory, which has become very trendy in theoretical CS circles lately.

There isn't one symmetric group; the symmetric groups are finite groups, and for any given size N, there is a symmetric group of that size, called the symmetric group of degree N.

Symmetric groups are the "master" groups of something called permutation groups. Permutation groups are groups whose members are mappings between elements of sets of size N.

Just as a reminder: permutations are rearrangements of a set. The permutations of a set S are every ordering of all of the members of S. The number of permutations of a set of size S is S! (the factorial of S).

There are two ways of looking at a permutation group. One is sort of what you might expect from the name: for a permutation group over the set of numbers from 1 to N, the possible members are all of the ways you can re-order the numbers. For example, if you've got the set of integers from 1 to 3, the possible members of the permutation groups are:

{ (1->1, 2->2, 3->3), (1->1, 2->3, 3->2), (1->2, 2->1, 3->3), (1->2, 2->3, 3->1), (1->3, 2->1, 3->2), and (1->3, 2->2, 3->1) }

The other way of looking at the possible values in a permutation group over 1 to N is as the set of all total, one-to-one functions from (1..N) to (1..N). If you look at that list up above, it does include every possible total one-to-one function from {1, 2, 3} to {1, 2, 3}.

The set of pemutation values become a group when we assign the group operation, and show that it has identity elements and inverses.

The group operation is straightforward: composition of the permutations. I think it's easiest to understand that if you think of the group members as functions; then the operator is just function composition: given two members f(x) and g(x), then f*g = f(g(x)).

So, for example, let's look at two members, F=(1->2,2->3,3->1) and G=(1->1,2->3,3->2).

• G(1)=1; F(1)=2, so F*G(1)=2.
  
• G(2)=3; F(3)=1, so F*G(2)=1.
  
• G(3)=2; F(2)=3, so F*G(3)=3.
  

So the composition F*G=(1->2,2->1,3->3).

The identity value should be pretty obvious - it's the identity function, which for all i maps i -> i. So for a the permutation group of order 3, the identity value is {(1->1),(2->2),(3->3)}.
And finally, inverses: just reverse the direction of the arrows in the mappings: for example, the inverse of (1->3,2->1,3->2) is (3->1,1->2,2->3), which can also be written (1->2,2->3,3->1) - and which is one of the members of the group.

The symmetric group of degree N is the permutation group containing all of the possible permutations over 1..N.

The symmetric group has a lot of really interesting properties. This is getting long, so for today, I'll just mention one really amazing one: every finite group is isomorphic to a subgroup of a symmetric group. (To remind you: a subgroup of a group G is a group whose members are a subset of the members of G.) The symmetric groups are a supergroup of every finite group!

That's exactly why they're so important: every possible symmetry property of a finite group is embedded in the structure of the symmetric group!

(Note: this post was corrected to remove a terminology error pointed out by poster Ivan M. I originally erroneously used the term "symmetry group" for "symmetric group". The error was a mistake dating all the way back to my group theory notebook from school! Thanks, Ivan, for catching it and being persistent about correcting me.)

A Sunday Snack: Finishing Up the PEAR

Finishing up on other incomplete stuff, I started discussing the PEAR survey paper. As a quick reminder, PEAR is a group at Princeton University that is studying "the interaction of human consciousness with sensitive physical devices, systems, and processes common to contemporary engineering practice". There's not a huge amount to say about the rest of it, but there are a few good points worth taking the time to discuss.

Overall, the problem with PEARs publications as a whole is that they've gathered a huge amount of data, which contains no statistically significant anomalies of any kind. But they keep trying to show how various properties of their data, despite being statistically insignificant, show anomalous features. This is a totally meaningless thing to do: any set of data, if you slice and dice it enough, will contain subsets that have apparently anomalous features; the whole point of statistical significance is that it's a way of measuring whether or not apparent trends in the data are strong enough to be considered as more than just random patterning or noise.

Section 3C is typical. Here's what they say in the introduction to the section:

Any structural details of the trial count distributions that compound to the observed anomalous mean shifts may hold useful implications for modeling such correlations. While no statistically significant departures of the variance, skew, kurtosis, or higher moments from the appropriate chance values appear in the overall data, regular patterns of certain finer scale features can be discerned.

This is an incredibly damning statement. Translated into simple english: there is nothing statistically significant in this data to indicate anything other than randomness. But by taking carefully selected subsets, we can discover interesting patterns.

Let me give an extreme example of what this means, in practice. If I take a set of data containing random numbers, and I slice it so that it contains only multiples of two and three, then I'll find that my data contains a subset which has an anomalously high proportion of even numbers. Is it a meaningful anomaly? Only in the sense that I selected the subset with the property that interested me - I created the anomaly by my data selection - the "anomaly" is a property of my selection process, not of the underlying data.

Section 3D is more of exactly the same thing:

Given the correlation of operator intentions with the anomalous mean shifts, it is reasonable to search the data for operator-specific features that might establish some pattern of individual operator contributions to the overall results. Unfortunately, quantitative statistical assessment of these is complicated by the unavoidably wide disparity among the operator database sizes, and by the small signal-to-noise ratio of the raw data, leaving graphical and analytical representations of the distribution of individual operator effects only marginally enlightening.

This is interesting for a couple of reasons. First - this is the most direct admission thus far in the paper of how thoroughly invalid their data is. They're combining results from signicantly different experimental protocols: some of the testers have done significantly more experiments with the apparatus than others; but the results are intermixed as if it was all consistent data.

Second, they're openly admitting that the data is invalid, and that any conclusions drawn from it are pretty much meaningless because of the problems in the data - but they're going to proceed to draw conclusions anyway, even though in their best assessment, the results can be only "marginally enlightening". (And even that is a ridiculous overstatement. "Meaningless" is the correct term.)

Section four starts with another thoroughly amusing statement:

Possible secondary correlations of effect sizes with a host of technical, psychological, and environmental factors, e.g. the type of random source; the distance of the operator from the machine; operator gender; two or more operators attempting the task together; feedback modes; the rate of bit generation; the number of bits sampled per trial; the number of trials comprising a run or series; the volitional/instructed protocol options; the degree of operator experience; and others have been explored to various extents within the course of these experiments, and in many other related studies not discussed here. Very briefly, qualitative inspection of these data, along with a comprehensive analysis of variance [40], indicates that most of these factors do not consistently alter the character or scale of the combined operator effects from those outlined above, although some may be important in certain individual operator performance patterns.

De-obfuscated, that translates to: "Pretty much every property of the experiment has been varied in all sorts of ways; the results of the experiment have been shown to be statistically insignificant; and then when we tried to piece out single factors as influencing the results, we couldn't find anything statistically significant."

One last quote, and I'll be done with PEAR once and for all. PEAR has been frequently criticized by, among others, James Randi (aka the Amazing Randi) for the bogosity of their experiments. One of the recurring criticisms is, quite appropriately, the replicability of the experiment: that is, can they reproduce these kinds of supposedly anomalous results in a controlled trial set up and observed by someone outside of PEAR?

Here's their response:

From time to time, the experiments reported here have been assessed, both formally and informally, by a number of critical observers, who have generally agreed that the equipment, protocols, and data processing are sound [49]. Frequently, however, the caveat is added that such results must be “replicated” before they can be fully accepted, with the replication criteria variously defined to require strict preservation of all technical and procedural details, or to allow more flexible similarities in equipment and protocols. It is our opinion that for experiments of this sort, involving as they clearly do substantial psychological factors and therefore both individual and collective statistical behaviors, to require that any given operator, on any given day, should produce identical results, or that any given operator group should quantitatively replicate the results of any other, is clearly unreasonable. Rather more apt would be such criteria as might be applied to controlled experiments in human creativity, perception, learning, or athletic achievement, where broad statistical ranges of individual and collective performance must be anticipated, and results therefore interpreted in statistically generic terms.

"We can't reproduce our results, because that would be unfair."

Of course, people have done carefully controlled trials of perception, learning, and athletic achievement, with reproduceable results. (I don't know of any in creativity, but that's because I don't know of any definition of "creativity" that's sufficiently quantifiable to be measured.) But hey, PEAR doesn't let that stand in their way. It's just unreasonable to ask them to be able to reproduce them.

Misc: Answering Questions and Sources

There's a bunch of questions that I've been asked about the group theory stuff I've been talking about lately. Since things are always slow on the weekend, I thought it would be a good time to go through and answer.

I also just want to take a moment and say thanks to all of the people who are reading the blog, and who've sent me kind words about how much they enjoy it. I can't tell you how happy I am that people are enjoying my writing. I'm having a great time writing this, and it really means a lot to me that people are enjoying reading it. So thank you all!

1. Onto? What's that? When I was defining transformations of groups, I used a bunch of terms "onto", "total", "one-to-one", etc. Lots of people didn't know the terms - and they're right, I should have defined them. So here we go:
1. Total/Partial: a function from A to B is total if f(a) is defined for all members of A. It's partial if there are members of A for which f(a) is not defined.
   
2. Onto: a function from A to B is onto if for every member b of B, there is at least one member of A where f(a)=b. It's basically the reverse of total. An onto function is also called a surjection.
   
3. One-to-one: a function from A to B is one-to-one if every member of A maps to one member of B; and no member of B is mapped to by more than one member of A. Note that in this definition of one-to-one, the function does not need to be onto. (Some definitions of "one-to-one" require that the function be onto; that's not the way I was taught.) By this definition, a one-to-one function is also called an injection.
   
   
2. Symmetry means reflection around a mirror. Shouldn't you use a different term? A lot of people have asked this. The thing is, symmetry doesn't mean reflection around a mirror. That's the simplest common example of it, but the term symmetry does mean much more than just "unchanged by reflection". I know that most english dictionaries definitions are, unfortunately, the reflective definition, because that's the common usage. But the origin of the word in greek, and it's use in mathematics is broader than that. Mathematicians use the word in it's broader sense, and if I were to use a different term for it on my blog, all I'd do is end up confusing things, because every other mathematician in the world will continue to use the word symmetry.
   
   
3. Why aren't you using MathML? After all of the discussion about whether or not to use MathML, I've ended up not using it, at least not for now. After experimenting with some tools for it, I've found that Blogger is very unfriendly to MathML. I really appreciate the fact that Blogger is free and all, but it's very frustrating at times. The only way I've found to make MathML work would require me to change a blogger setting which, in turn, would require me to go back and reformat all of the earlier posts to blog, or they'd become illegible.
   
   
4. What are your sources? For the group theory stuff, I'm using my old class notes, Wolfram's Mathworld, and Wikipedia. In particular, Mathworld is a really fun source - there's a ton of great stuff up there. The writing quality varies from mediocre to fantastic; the group theory stuff tends towards the mediocre, but it's thorough, so it makes a good reference, if not a good place to go to learn the material.
   
   I've also been reading "The Equation that Couldn't be Solved" by Livio; lots of people think it's a great book. Personally, I find it a very frustrating read; Livio tries to write like Hofstadter or Gardner, with a lot of places where it goes off on semi-related tangents. When Hofstadter does that, I tend to enjoy it; his tangents are interesting and relevant. I find that Livio's tangents are often too unrelated to the basic material. I think it's mostly a matter of personal taste, but I find Livio a very difficult read; I can't get myself to read more than a few pages at a sitting. (Whereas when I read, say, Brian Greene, I read 50 pages at a sitting.) Given how many people seem to really love the book, if you're interested in this kind of stuff, it's probably worth getting a copy and reading; but it's not like "Godel, Escher, Bach" where I think it's an absolute essential to have in your library.
   
   
5. When are you going to write about X? I'm amazed and flattered how many mails like this I've gotten. People have asked me to write about topography, recursive function theory, language families, rings, set theory, discrete vs continuous math, statistics, music theory, and more. My only answer is: give me a chance! Please do keep sending requests for what you'd be interested in seeing on the blog; I'll do my best to get to it all. The more requests I get for a topic, the sooner I'll get to it. But please be patient!
   
   
6. Can I reprint articles from your blog? As long as it's not for profit, sure, as long as you put in an attribution identifying where you got it, and don't edit it other than for formatting. If you want to edit it, or you want to include it in something where you're going to charge for copies, get in touch with me by email, and we can talk about it.
   
   

Mind-numbingly stupid math

An alert reader just forwarded me a link to this mind-bogglingly stupid article. This is one of the dumbest pseudo-mathematical arguments that I've ever seen - and that's a mighty strong statement. This Oxford University Professor! argues that he can mathematically prove the resurrection of Jesus. Get a load of this:

This stunning conclusion was made based on a series of complex calculations grounded in the following logic:
(1) The probably of God's existence is one in two. That is, God either exists or doesn't.
(2) The probability that God became incarnate, that is embodied in human form, is also one in two.
(3) The evidence for God's existence is an argument for the resurrection.
(4) The chance of Christ's resurrection not being reported by the gospels has a probability of one in 10.
(5) Considering all these factors together, there is a one in 1,000 chance that the resurrection is not true.

Where to start with shredding this? Is it even worth the effort?

By a similar argument, I can say that probability of pink winged monkeys flying out of my butt is one in two: that is, either they will fly out of my butt, or they won't. The probability that those monkeys will fly to the home of this Oxford professor and pelt it with their feces is one in two. If pink winged monkeys fly out of my butt, that's an argument for the likelyhood of a fecal attack on his home by flying pink monkeys.

Do I really need to continue this? I don't think so; I'd better go stock up on monkey food in my bathroom.

Group Isomorphism: Defining Symmetry Transformations

Yesterday, I explained the idea of multiple kinds of symmetry intuitively, by describing symmetry as immunity to transformation. Today I'm going to try to explain what, in group theory transformation means, and how symmetry is defined in terms of transformation.

What it comes down to is a concept called group isomorphism.

Group Homomorphisms and Isomorphisms

Before I can describe a group isomorphism, I need to explain a group homomorphism. A homomorphism between two groups A and B is a function that maps members of A to members of B in a way that preserves the group property.

So - suppose we have group A, and we call its operation "+"; and we have a group B, and we call its operation "*". A function f from A to B (written f : A -> B) is a homomorphism if and only if:

all x,y in A : f(x+y) = f(x)*f(y)

So a homomorphism is a mapping in one direction from A to B. It guarantees that for every element of A, we can map it onto an element of B; and that that mapping is guaranteed to preserve the group property on the mapped elements.

What do I mean by the group property is preserved? Mostly that the statement up above is true: all x,y in A: f(x+y) =f(x)*f(y). But that implies a couple of important things:

• (1) f maps the identity element of A onto the identity element of B: f(1_A) = 1_B.
  
• (2) f's mapping preserves inverses: f(x^-1) = f(x)^-1.
  

A homomorphism does not have to be a total function onto B - meaning that non every member of B has an element of A mapped onto it. It does not have to be one-to-one, meaning that multiple elements of A could be mapped onto a single element of B, so long as the group property was preserved.

A group isomorphism is a group homomorphism f, where f is a bijection. That means that f maps each element of A onto exactly one element of B; and every element of B is mapped to by exactly one element of A. (Another way of saying that is f : A -> B is total, one-to-one, and onto.)

If f : A -> B is a group isomorphism, then it describes a symmetric transformation from group A to group B. If we take a set of values from A; and we map each of those values to B using f, we get as a result a set which is equivalent or indistinguishable from the original set.

Permutation Symmetry

One particularly interesting kind of symmetry is called permutation symmetry. Permutation symmetry is a kind of symmetry created by a group isomorphism from a group to itself. Reflection symmetry between the real numbers is a permutation symmetry: it is a total, one to one, onto map from all real values (omitting zero) to all real values (omitting zero) which preserves the group property of multiplication.

The rotational symmetry of a pentagon is also a permutation symmetry; if we label the five vertices of the pentagon as A, B, C, D, and E, then the function: { (A->B), (B->C), (C->D), (D->E), (E->A) } is an isomorphism; when you apply it, you rotate the pentagon (or the labeling of the pentagon), but you end up with a pentagon that is indistinguishable from the one you started with.

Friday Random Ten 4/21

1. Steven Reich and Maya Beiser: Cello Counterpoint. A truly amazing modern classical composition by Steven Reich, played by Maya Beiser. Beiser is tracked 16 times on this: she's the only performer, but there are 16 different parts overlayed. This is a seriously spectacular piece of music. I love Reich as a composer, and I think this is one of his finest short works. Just wow.
2. The Flower Kings, Monkey Business. Neo-progressive rock, by a great band. Definitely not for people with no patience - FK songs tend to average around 15 minutes each.
3. Harry Bradley, The Merrymaker's Club/The Acrobat. My favorite Irish flutist.
4. Dave Matthew Band, Don't Drink the Water. DMB with Bela Fleck on banjo. What more could you ask?
5. Continental Divide, Andersonville March. Very traditional bluegrass from a great, unfortunately defunct band. Scott Vestal on banjo - Vestal is one of the true greats on the banjo; the man can play anything from Yes to Bach to Scruggs. I don't care for the singer in CD (or in fact nearly any bluegrass vocalist), but this tune is instrumental.
   
6. Broadside Electric, Babylon. A truly gruesome old folksong about a robber who accidentally murders his own sisters. Broadside is a great local band (NY/Philadelphia area) with a particular fondness for gruesome ballads.
7. Deanta, Ready for the Storm. Beautiful song from a great Irish band.
8. Miles Davis, Well You Needn't. I am not worthy to comment on Miles Davis.
9. Steven Hackett, Man Overboard. Latest work by the great guitarist from the old days of Genesis. Good, but not great.
10. King Crimson, Starless. Very old KC, from the "Red" album. Proof that a guitar solo doesn't need to have a lot of notes to be amazing.
    

Group Theory 3: Expanding on Symmetry

Yesterday, I talked about the basic intuitive idea of what symmetry means. Today, I'm going to try to take it a bit further. I will eventually get to the point of explaining how groups express this; but this stuff really fried my brain the first time I saw it, so I'm trying to take small steps, with as much intuition as I can muster at each step.

Intuitively, when we talk about symmetry, we think about reflection - like we could pick out a line, or a plane, and switch things around the sides of it. In normal english usage, that's all that symmetry means: reflective symmetry around a line or plane. The standard real number multiplication symmetry fits that nicely: it's reflective symmetry around the line "x=y".

In math, and in group theory in particular (since group theory is what defines symmetry), symmetry means something more than that. Mathematically, symmetry means something more like "immunity to transformation" - where the exact transformation could be almost anything. Immunity to transformation means that after the transformation is applied, there is no way to distinguish between before and after the transformation.

The familiar symmetry, reflective symmetry, means that if you mirror-reflect what's on each side of the line, and switch it to the other side of the line, you'll end up with something indistinguishable from what you started with.

There are other kinds of symmetry, which mean that you can do some other kind of transformation without having any distinguishable effect.

Translational symmetry means that something can be moved in some way without having any distinguishable effect; rotational symmetry means that something can be rotated in some way without having and distinguishable effect.

For example, if you have an infinite sheet of graph paper, and you move it one square in any direction, you can't tell that you moved it: it is symmetric with respect to translation by integral unit translations.

If you have a pentagon, you can reflect it five along five different lines:



You can also rotate it; it has rotational symmetry around the angles produced by the five reflective symmetry lines:



Finally, a particularly cool example: this Escher image has six reflective symmetries; 3 rotational symmetries; translational symmetries in 8 directions,
and a 3-way reflective symmetry (meaning you can divide it into three sections and mirror-swap each section separately). Instead of marring such a beautiful image, I'll leave it alone and let you puzzle those out.

The Bad Math of Paranormal Research: PEAR

Reading some stuff on Orac's site, I discovered a website run by a professor at Princeton who runs a lab called the "Princeton Engineering Anomalies Research Center", aka PEAR. They're part of the department of Engineering and Applied Science at Princeton. As a Rutgers alumni, I've always been loyally snooty about Princeton engineering; but I never would have dreamed that garbage like this would fly there.

What PEAR studies is allegedly how human beings can influence random number generators. Their experiments consist of a fairly elaborate rig that generates a random sequence; the subject have no physical access to the generator, but tries to influence the "direction" of the random numbers generated, either up or down. I'm looking at one of their papers: a review of 12 years of experiements with this experimental apparatus.

It's an interesting example of bad math, because it's quite subtle. There are, of course, warning signs even from the beginning that the authors are crackpots. One of the common warning signs that the authors know that they're doing nonsense is when they start the paper with a long list of famous people (usually dead) who allegedly support their ideas. This one starts with a list of eighteen people who they allege supported their ideas, ranging from Francis Bacon to Einstein. They even include an alleged conversation between Einstein and an unnamed "important theoretical physicist" about how paranormal powers were a legitimate area of study in physics.

After a detailed description of their experimental apparatus and testing protocol, they finally get the alleged math.

There's a couple of tricks that they pull right away as they get into the math. They have 91 different test subjects; 522 test series; and close to 2 1/2 million "trials". This is intended to give an appearance of a fair, balanced study; but later in the paper, it becomes clear that the different operators ran different numbers of tests in somewhat different settings. They do not indicate how the trials were selected, how they were distributed among the subjects, or whether these are the only subjects that every did the experiment. This is absolutely unacceptable - in statistical mathematics, ensuring fair samples is critical.

Next, we come to a table presenting a summary of their results; I had to flip back and forth between the page with the table and the previous page at least half a dozen times, making notes, in order to be able to make any sense out of this table. While I can't prove it, I strongly suspect that this obfuscatory presentation of data is quite deliberate: it's a classic bad math maneuver: dazzle the readers with lots of complicated looking numbers, equations, and tables, in order to give them the idea that there's a depth to your analysis that isn't really there. This really is a dreadful way of presenting this information: there is not particularly complex data in this table - it's basically means and standard deviations for a fairly straightforward experiment protocol - but it manages to astonishingly confusing.

On the next page - we get a wonderful statement:

The anomalous correlations also manifest in the fraction of experimental series in which the terminal results confirm the intended directions. For example, 57% of the series display HI-LO score separations in the intended direction (zs = 3.15, ps = 8 * 10^-4). In contrast, the anomaly is not statistically evident in the 52% of individual operators producing databases in the intended directions (z0 = 0.31, p0 = 0.38), a feature having possible structural implications, as discussed below.

Yes, 57% of experiments, performed by 52% of the operators: this is an admission that the sample is biased!

And better "the anomaly is not statistically evident"; another way of saying that it's a statistically insignificant result. Yes, the fact that their results are not statistically significant is a feature "having possible structural implications". Pardon me, I need to go roll on the floor and giggle for a few minutes.

.
.
.


Ok. I'm better now. One last thing, and then I'm goint to take a break from this monstrosity. Here's a copy of their graph of the "cumulative deviation over time" of their trials:



Just take a look at that graph: the distance of the lines from the parabolic curve is the cumulative deviation. "HI" accumulates some deviation early, and then stays roughly parallel to the curve; baseline wanders all the heck over the place, ending up right on the upper branch of the curve; "LO" meanders around the curve, approximating it pretty well.

What does that tell us?

Absolutely nothing of value. The deviation of the baseline is extremely close to the deviation of "LO" - i.e., their deviations aren't significant. In fact, if their "HI" didn't have an early bump, which doesn't seem to persist very well, the curves would have been pretty much staying within the 95% confidence interval. (As a side note, if you take a look at their website, they have a whole bunch of different versions of that graph. Amazing how you can get different results by using different samples of your data, isn't it?)

The information they take from this graph is that the "anomalous correlations" - you know, the anomalous correlations that they admitted weren't statistically significant? - they amount to a shift of 10^-4/bit - or 1 bit in 10,000 deviating from the expected norm.

I'll have more to say about this crud later - because it's a fine example of how to use bad math to obscure bad work - but this is enough for now; I can only plow through so much slop in one session.

Group Theory: What is symmetry? Why do I care?

When I started talking about group theory on monday, I said that ultimately, groups are a way of capturing symmetry: multiplication over the real numbers (if you omit zero) has an amazing symmetry about it, and group theory abstracts away the details of multiplication to home in on that symmetry concept.

The problem that a lot of non-mathematicians have when you talk about Groups is that it's kind of hard to grasp what that symmetry is, what it means, and why they should care. The list of applications that commenters came up with is impressive, and is a pretty compelling argument to me for why this stuff is interesting; but it's important to grasp the intuition behind the symmetry of groups before you can really get group theory.

So - what does symmetry mean?

Let's start by looking at multiplication. Think about multiplication with non-zero real numbers. Forget about the fact that we can add numbers - just focus on multiplication.

If I were to have you take the real numbers, and come up with some funny way of writing them, so that I don't know which numbers are which, and then you ask me to tell you which number is which, only by using multiplication and testing equality, would I be able to do it?

Well, I could certainly tell which number was 1: it's the only number where anytime I pick some other number and multiply it by one, I get the other number.

What else could I work out? Given enough time, could I figure out which number was two? Well, two is interesting in its way, because if I could figure out which numbers were integers, then I could recognize two because every other integer is a multiple of it - so if I tested enough numbers, I could at least make a pretty good guess which number was two - that is, if I could figure out which numbers were integers. But I can't do that - there's no way for me to tell the difference between an integer and any other real number.

Now, here's where it gets a bit subtle: Suppose I were to give you the integers from 1 to 1000, and their reciprocals. So you've got a bunch of numbers which you know are 1, 2, 1/2, 3, 1/3, 4, 1/4, 5, 1/5, 6, 1/6, etc, but you don't know which is which. Now, could you tell me which of them was the number 2?

The answer is no. You could narrow it down to being one of *two* numbers, and you could tell that those numbers were each others inverses - but you couldn't tell which was which. You can't tell apart 1/2 and 2 - because the group is symmetric around 1.

Think about it: how could you tell the difference between "x*y=z" where x=1/2, y=1/3, and z=1/6, and "x*y=z" where x=2, y=3, and z=6?

Or to be visual for a moment: look at this graph of the equation y=1/x in the first quadrant (that is, the part that we normally draw on the upper right, where x and y are both positive).



Without the axes being labeled, which is X and which is Y?

It doesn't matter - you can call either one X and the other one Y, and that's still the right graph. What that means goes beyond that one graph: any statement that you can make about numbers using only multiplication is also true if you replace every value with its reciprocal.

For a more concrete and practical example of this kind of symmetry: the symmetry property works in electronics. You can analyze a circuit two different ways: you can look at any circuit, work out what it does, what current, voltage, amperage, resistance, etc., exists at what point in the circuit; and you can do that under the assumption that the positive charges are moving, or that the negative charges are moving - and the answers will come out exactly the same. In fact, for years (and maybe even still now), electrical engineers were trained to do the computations with the assumption that it was the positive charge that moved! (It's a historical error".)

Symmetry is a fascinating property, which allows you to recognize similarities, and discover ways in which properties can't change even though they've been twisted around somehow.

Remember that great quote from Newman? "The theory of groups is a branch of mathematics in which one does something to something and then compares the results with the result of doing the same thing to something else, or something else to the same thing." Group theory lets you see the similarities between different things, or the ways in which things can't be different, by expressing the fundamental symmetries.

Some Applications of Group Theory, promoted from comments

A bunch of people posted some really great descriptions of applications of group theory in the comments; I thought they were good enough that they deserved to be promoted to the front page.

Groups and Relativity

Blake Stacey wrote an excellent comment explaining how group theory applies in relativity.

Take two observers, Joe and Moe, who are watching some mechanical system -- say a star system with planets and moons spinning around -- and testing if the motions they see follow Newton's laws. To describe motion mathematically, they use coordinates, which might be the Cartesian x-y-z system: locate an object at a particular time by specifying how far it is above some plane, how far in front and how far to the left (with negative numbers to describe positions in the opposite directions).

Joe and Moe do not have to use the same coordinate systems to agree upon the laws of motion. If Moe is standing 10 million kilometers to Joe's left, say, then Moe's coordinates for each planet will be offset by that amount, but Moe will still see the motion as obeying Newton's laws. Likewise if Moe is turned with respect to Joe: a point which lies on Joe's x-axis will to Moe be some mixture of x and y, but the physical laws will be the same.

In Newtonian mechanics, it is even true that Joe and Moe can be in motion relative to each other. Joe believes he is standing still and sees Moe moving past with a constant speed in a straight line; Moe believes he is standing still and sees Joe going past in a straight line. Uniform motion in a straight line is indistinguishable from a state of rest, or put another way, there is no "gold standard" absolute state of rest from which all speeds should be measured. (Think of riding in an airplane on a smooth flight: when can you tell you're not sitting on the ground without looking outside?)

Einstein's revision of Newtonian mechanics says that the same principle holds true for all physical laws. Even if Joe and Moe try to determine who is "really" moving by measuring the speed of a light beam, they will measure the same speed, 300,000 km/s. One would expect that if Joe measures light going at 300,000 km/s and sees Moe flying past at 100,000 km/s, Moe will measure the light traveling at 200,000 km/s, but such is not the case.

This all comes down to group theory because we can consider these transformations -- translation by a fixed distance, rotation by an angle, movement at a uniform velocity -- as symmetry operations on the physical laws. Just like a vase or a starfish is symmetrical if we can rotate it around and it looks the same as it did before, a physical law is symmetrical if we can change the coordinates we use and it still takes the same form.

The magic buzzword to give a search engine is "Lorentz group".

In a very similar vein, an anonymous poster (email me if you want me to put your name here!) commented on how group theory within the framework of relativity explains the basic laws of conservation:

The interesting thing about the application of group theory to space time is that the conservation laws of physics can be shown to be equivalent to the invarience of physics under space time transformations. For example
1. conservation of angular momentum can be shown to be equivalent to the statement that the laws of physics are invarient under static rotations (the rotation group in three dimensions);
2. conservation of linear momentum can be shown to be ewuivalent to the statement that the laws of physics are invarient ulnder static space translations (the translation group in three dimensions);
3. conservation of energy can be shown to be equivalent to the statement that the laws of physics are invarient under static time translations (the one dimensional translation group).

Other Applications in Physics

Another nifty example of how group theory has been used in physics; eulerfx explains:

To mention an example of how group theory is used in particle physics, Paul Dirac discovered the existence of the positron through manipulation of complex valued matricies in the general linear group, GL.

Music Theory

Steve added some detail to my comment about how group theory can be applied to music theory:

The music theory applications center around mod-12 arithmetic. There are 12 notes in the chromatic scale & rather than refer to them as C, C# etc. they can be numbered 0 through 11. The two basic operations are then:

Transposition by n semitones: x + n (mod 12)

Inversion: 12 - X (mod 12)

All possible chords with n notes can be classified by sets where the notes are placed in the form that minimizes through the operations of transposition and inversion the sum of the intervals. If two chords can be made identical by either transposition or inversion they are considered identical. By this classification, for instance, there are 12 possible 3 note chords (interestingly enough, a major and minor triad are the same entity under this system)

Big thanks to you guys, and all of the other commenters!

Finite Groups and the Greatest Math Song Ever!

I'm busy tonight, and in a strange mood, so I'm not going to say too much; but I need to get to one point, so that I can link to something wonderful.

So, yesterday, I posted an introduction to group theory.

Well, it turns out (naturally), that there are many groups with finite numbers of members. And they are, quite imaginatively, called finite groups. Most finite groups can be illustrated quite beautifully with a diagram, but that's a topic for another day.

Within a finite group, the number of elements in the group is called the order of the group. So, for example, a group with 10 elements is called a finite group of order 10.

There also a notion, too complex to really get into tonight, called a simple group. A simple group is, essentially, one that has a kind of minimality about it; its only normal subgroups (basically groups formed by subsets of the values in the group) are trivial. (Note: the word "normal" was originally omitted from this sentence, because I forgot that there are plenty of non-simple subgroups; only the normal ones need to be trivial. This error was pointed out by commenter Ivan M.)

So - the point of this: here is a link to the greatest a-capella math song of all time: Finite Simple Group of Order Two, by the Klein 4 at Northwestern University.

Yes, I am a dork.

Brain Development and Learning Math

Just a quick pointer to something neat: there's an interesting article about how are brains are wired for doing mathematics over at MindHacks.

Fun Stuff: Group Theory (Corrected)

One of the things that you can do in math that's really interesting is to play games with abstracting things. What I mean by that is that you can look at things that are part of everyday math, and strip them down to their bare essentials, and see what happens. Some fascinating theories have come out of this, and they're not just theoretical math - they have concrete, practical applications: mathematical structure is part of the world, and playing with abstraction is one way of seeing that.

In Algebra, one of the abstraction games that people like to play is called Group Theory, and I'm going to write a bunch of posts talking about it, because there's so many fascinating things hiding inside of it. Today, I'm just going to give you a very brief introduction; later in the week, I'll build on that.

Group theory comes from looking at the idea of multiplication, and asking: what are the real essential properties of multiplication? If I get rid of numbers, so that I'm just talking about multiplication as a bare operation, what are its essential properties?

What you wind up with is something called a group. A group Gis a set of values, along with a binary "multiplication" operation, which meets a set of properties, all of which should be familiar from working with multiplication on real numbers:

Closure

Closure says that for any two values a and b are in G, then their product "a * b" must be in G. In other words, there is no way that you can multiply any two values in G, and end up with a value that isn't in G.

Associativity

If a, b, and c are in G, then (a*b)*c = a*(b*c).

Identity

There is an element, "1" in G, such that for all a in G, a * 1 = a, and 1 * a = a.

Inverse

G contains an inverse (reciprocal) for each of its members. The inverse of an element "a" in G is written "a^-1"; and for all a, a * a^-1 = 1 and a^-1 * a = 1.

What this comes down to is that a group is a structured set of values that has an interesting kind of symmetry expressed in its multiplication operation.

An interesting to note is that group theory is an abstraction of a set with a multiplication operation; but the Real numbers with the normal real multiplication operation are not a group (because 0 breaks the identity and inverse properties); on the other hand, real numbers using the addition operation are a group!

A very famous mathematician, James Newman, who was particularly famous for writing books that explained mathematics to laymen, describe group theory in a wonderful way:

The theory of groups is a branch of mathematics in which one does something to something and then compares the results with the result of doing the same thing to something else, or something else to the same thing.

What kinds of things can be expressed as groups?

1. Music: There's a way of looking at music theory using groups: natural "operations" that occur in music and chords, like inversion, transposition, etc., all exhibit group symmetries.
   
2. Chemistry: you can determine the polarity of a molecule by using group theory to identify the symmetries in the structure of the molecule.
   
3. Physics: group theory is apparently used in special relativity, although I don't pretend to understand how.

(Update note: in the original version of this, I forgot that Group Theory does not assume that multiplication is commutative; I've corrected it since the error was pointed out in the comments.)

Q&A roundup: No Free Lunch

I've been receiving a bunch of email over the last couple of weeks with similar questions about my critique of Dembski's "no free lunch". Rather than answering the emails individually, I've been gathering them up, and I'll try to answer the questions here.

1. What does "averaged over all landscapes" mean?
   
   In a NFL setting, we're talking about doing something like a search over a landscape, where we have "fitness functions" which provide the search algorithm with its directions: the search moves in the direction that the fitness function tells it to.
   
   One of the properties of the fitness functions is that they don't get to see the real landscape: their job is to try to approximate the landscape in a good way, so the search will wind up at a good destination.
   
   When we average over all landscapes - what that means is that instead of considering how a particular fitness function matches a particular landscape, we're saying "Let's look at every possible landscape, and run the fitness function, and see what kind of results it gets".
   
   NFL says that if we do that, that no matter how carefully we design the fitness function, it can't possibly do better than random for all landscapes. What this means is that if we don't know which landscape we're going to be confronted with, we can't pick a fitness function that's guaranteed to do well. This is interesting, for example, when applied to things like financial derivatives markets: if we don't have information about what the markets are going to do, then on average, we can't beat the market.
   
   
2. NFL works for operations research tasks; why doesn't it work for evolution?
   
   Receiving multiple emails with this question surprised the heck out of me. It's an odd question, one which is both deep and shallow at the same time. I suspect that someone somewhere put folks up to asking this one as a response to my argument, but I have no proof of that. Anyway - on to the answer:
   
   One of the key properties of NFL is that it uses blind fitness functions. That is, the fitness function doesn't get to change itself depending on what landscape you're running it on. The fitness function in NFL is also deterministic: for any point in the landscape, looking at where it can go next, it can only choose one path as the best.
   
   Evolution is an adaptational process: modelled as a function, it's more like the learning functions in Case's computational learning theory than like the fitness functions in NFL; an evolutionary process doesn't have a fixed path built in to it; it doesn't even have a real fitness function built in to it. In effect, an evolutionary process is modifying its fitness function as it goes. The landscape that it traverses gets built into the function, so that the longer it runs, the more adapted to the landscape it gets.
   
   Evolution is also not deterministic: it tries multiple paths. Remember that evolution is working on a species, not on individuals. Within a species, multiple adaptations can occur in different sub-populations. That is effectively trying multiple paths. In fact, that's exactly how speciation occurs: different subpopulations adapt to the environment in different ways.
   
   
3. NFL is a probability argument; why do you keep babbling about landscapes?
   
   There are a lot of different ways that you can describe NFL-type problems; landscapes is the one I think is intuitively easiest. The idea of things like NFL is to look at a state-space with transitions, and see how algorithms can perform in different state spaces. You can describe that as a probability space, a landscape, a weighted graph, a state table, or any number of other things. The "probability" piece comes from comparing the fitness function (or fitness landscape, or whatever abstraction you choose) with the landscape it's supposed to by trying to fit. By doing that comparison, you can find the probability of a given type of fitness function performing well on a given type of landscape.
   
   
4. NFL doesn't say evolution can't do better than randomness; it says that evolution must have some knowledge of the landscape to do better than randomness. Where does evolution get that knowledge?
   
   As I said above, NFL relies on deterministic, fixed fitness functions for searching landscapes. Evolution is effectively non-deterministic, because it tries multiple paths; the successful paths persist and keep going; the unsuccessful ones die out.
   
   Non-determinism is a big deal. The ability to try multiple paths and keep the ones that work is an incredibly powerful notion - and that's exactly where evolution gets its ability to adapt and perform well in any fitness landscape. Mathematically, you can't model evolution as a fixed deterministic function; it's an adaptive non-deterministic one. And an adaptive non-deterministic algorithm will not fall into the NFL trap. (See the Case citation above for some great work about what non-deterministic adaptive functions can do.)
   
   

Friday Random Ten, April 14th

Yes, it's friday again.

1. King Crimson, "Fallen Angel"
   
2. Porcupine Tree, ".3": an instrumental track by a fantastic, hard to categorize band. PT started as a joke, and has straddled the lines between neo-progressive, alt-rock, and pop.
   
3. Marillion, "Market Square Heroes". Very old track off of Marillion's first album. They sounded a lot like Genesis in those days.
   
4. Deanta, "The Party". Traditional Irish music from a wonderful band. What could be better than traditional Irish, with one of the best wooden flautists in the world (Deirdre Havlin), Irish lap harp, bouzouki, and bohdran?
5. Genesis, "In the Cage". A track off Genesis' "The Lamb Lays Down on Broadway", the magnum opus from the Peter Gabriel days.
6. Bela Fleck, "The Legend". Newgrass from one of the gods of newgrass banjo. Bela's truly an unbelievable musician - the guy can play anything on a five-string banjo. I've seen him live performing traditional old-school bluegrass, newgrass, bop jazz, classical, rock... There's just nothing the guy can't do with a banjo.
7. Yes, "Yours is No Disgrace". My iPod seems to like old prog-rock today.
8. Moxy Fruvous, "Spiderman". Moxy is a goofy canadian band which specializes in silly songs with four-part vocal harmony. This is their take-off on the theme to the old spiderman cartoon. Imagine that trashy song with lyrics like "Spidermans master plan, build his own little spider clan. In the woods, now they're troops, fighting for special interest groups".
9. Nightingale, "Ma Commere, Ma Mie / Retour De Montaignac". French canadian folk music from a wonderful three-part band. The singer for Nightingale, Keith Murphy, has one of the most beautiful quiet voices I've heard.
10. The Clogs, "Pitasi". The Clogs are impossible to classify. The music is mostly classical sounding, but with an improvisational edge, and bits of rock-style rythym mixed in. Definitely an acquired taste, but I like 'em.

Vaccines and Geniuses

As Orac points out today, Vox Day, one of the most obnoxious assholes that I've encountered on the net, is an anti-vaccine guy, who's been using the recent outbreak of mumps in Iowa (discussed by Tara here) to argue that vaccines must not work.

It's quite sad in its way: Vox is a self-proclaimed genius and member of Mensa. And yet, this is typical of his idea of argument. The "math" is so poor that it's laughable, and the rest of the reasoning is no better.

So, here's Vox:

From the Star & Sickle:

A mumps vaccine was introduced in 1967. Iowa law requires schoolchildren to be vaccinated against measles and rubella, and the mumps vaccine is included in the same shot. The state's last major outbreak was in 1987, when 476 people were infected.

Of the 245 patients this year, at least 66 percent had had the recommended two-shot vaccination, while 14 percent had received one dose, the Public Health Department said.

"The vaccine is working," Quinlisk said. "The vaccine certainly was made to cover this particular strain, because it's a fairly common strain of mumps." Quinlisk said the vaccine overall is considered about 95 percent effective.

So, the question is this: if the vaccine, not improved hygiene or some other factor, is primarily responsible for preventing transmission of the disease it is supposed to prevent, how is it possible that 80 percent of the infected in this latest outbreak are at least partially vaccinated against it?

And isn't it at least somewhat doubt-inspiring that the health authorities continue to insist that the vaccine is working in the face of direct evidence that, at least in some cases, it is not?

So, Vox wants to argue that vaccines don't really work, because there's a mumps outbreak in Iowa. And 80% of the cases are people who received at least one dose of the MMR vaccine.

Let's look at some numbers, to get an idea of what the infection rates mean. We'll be charitable, and stack all of the numbers in Vox's favor - so whatever we come up with is going to make the infection rates seem much higher than they are.

So - let's start by coming up with an estimate of the number of people in the pool of potentially infectable. Playing the numbers in Vox's favor, we'll assume that all of the mumps cases came from people born in the same year. The birth rate in Iowa is is pretty consistent, acording to the official statistics: around 38,000/year. Of those, the number vaccinated is around 81%, again according to the official statistics. So, the pool of vaccinated people born in that year is around 30,700.

Now, the cited effectiveness rate of the MMR against mumps is 95%. What that number means is that 95% of the people who receive the vaccine will develop an effective immunity to mumps. So - the expected number of vaccinated people who would not be immune would be around 1500 people (rounding down).

There are 245 infections this year, according to the article Vox cited. That would mean that 15% of the non-immune population of vaccinated people had become infected. That's a damned high number, but not completely beyond reason for something as contagious as mumps.

But then, remember that all of the numbers are stacked heavily in favor of making the vaccines look bad: in particular, these numbers are based on reducing the pool of potential infectables by several orders of magnitude (because we assume all cases were born in the same year, and all of them were born in Iowa) - we find that the number of infections with mumps is entirely possible. It makes for a pretty serious outbreak for sure - but not something that calls into question the effectiveness of vaccines.

Now, to put the nail in the coffin: back to some official statistics. How many cases of mumps were there before vaccines became mandatory in Iowa? Official statistics are here: during the decade before mumps vaccines became mandatory in Iowa, the number of infections per year ranged from 2000 to 12000 per year. Now, during a dramatic outbreak, described as an epidemic, we've got a couple of hundred cases. Does that look to you like the vaccines are not working?

Nah. Me neither.

Off topic, but I can't resist: clarinet stuff!

This is way off the normal topic of the blog, but I just can't resist.

One of the things that I do for fun is play music. I'm a bit of a dabbler; I play a ton of different woodwinds. But my first instrument is clarinet; I was classically trained, and I've played in for about 25 years now. As much as I like the other instruments I play, particularly my Irish flute, there's still nothing as close to my heart as the clarinet.

There's been a lot of exciting stuff happening in the clarinet world. There are now synthetic reeds that are very close to the quality of the best natural reeds, only they need less maintenance, they're harder to damage, and they last much longer. (I'm particularly fond of Harry Hartman's fiberreeds; in a box of 10 of the very best hand-made natural reeds, maybe one will sound better than a fiberreed.)

In a different vein, I just discovered a very strange new ligature. The ligature is the little thing that holds the reed to the mouthpiece. The shape of the ligature, the way it contacts the reed and the mouthpiece can have a huge impact on the way the instrument plays and sounds. There are dozens of different ligatures, but until recently, there were three main variations:

• (1) Rigid ligature (generally metal), open loop with screws fastening over the reed. Here's a pic of a mouthpiece with one of those:
  
  
• (2) Rigid ligature, either metal or plastic, with screws fastening over the back of the mouthpiece. (These generally use some trick to reduce the area of contact between the ligature and the reed, and sometimes the ligature and the mouthpiece.):
  
  
• (3) Fabric ligature with a single screw over the back of the mouthpiece. Fabric ligatures use a shaped metal plate to contact the reed, shaped to minimize its impact on the vibration of the reed:
  

There've been variations on these three for last long as I've played the clarinet, but I've never seen anything else.

I just got something new, called the Bois Delrin ligature. This little bugger is a simple ring of delrin (an very interesting plastic), it's not flexible, it doesn't stretch, and it it has no screws at all. It just slides down over the reed and mouthpiece until it's tight. Here's a pic; the ligature is the little ring piece, the other thing is just a reed protector to fit over the mouthpiece when you're not playing.



This little bugger is the most amazing thing that I've ever tried. It has more impact on the ease of playing than any other clarinet accessory I've ever seen. It's just absolutely stunning. I'm in love! I never dreamed that anything could be such a huge improvement over the giggliotti that I've been using for the last 15 years. Wow, wow, wow!

(The links up there are to Music123 where I bought it; I'm not affiliated with them or with Bois in any way, I get absolutely nothing if you buy one of these little wonders. I just think it's so amazing that I've had to rave.)

Correcting my models post; or, why MarkCC is a dummy

As someone pointed out in the comments, I really blew it in my logic models post on monday: the error in the logic relied on the mis-definition of "predecessor"; but the way that I demonstrated the error didn't use predecessor at all. :-(

This is a great example of what happens when you try to rush. I knew I wasn't going to be around monday afternoon or all day tuesday, due to a combination of work and family stuff, so I wanted to get a post out monday morning, and I rushed it. I knew what I wanted to write; unfortunately, that's not what I actually wrote.

Anyway - to make up for it, I'll explain the correction here, and answer a few of the questions that came up in the comments.

The model that I presented for numbers using logic actually contains two errors - the one that I included deliberately (the definition of "predecessor"), and one that I included accidentally (an error in the definition of successor). What I find impressive in my own warped way is that when I demonstrated how an error in the model can create invalid results, I did it using the model error that I did not include on purpose!

So - let's start by going back and looking at the successor definition:

all x in Natural : exists y : Successor(x,y)

I said that what this statement says in english is: every number has a successor. Alas, that is not what it actually says. What is says is that every natural number is the successor of some other natural number. And that's not true - zero is not the succesor of any natural numbers, which is the fact that I took advantage of in my demonstration of the bad conclusions you can reach using an invalid model.

That statement should read:

all x in Natural : exists y : Successor(y,x)

That is, the parameters of the successor predicate were in the wrong order - so it said "x is the successor of y" rather than "y is the successor of x". With that corrected, the problem goes away. But in fact, I think that the accidental error in that definition is a better example than the one I created deliberately: it's the same general sort of problem, but it involves fewer definitions, and it's subtler. With that error, we don't need the error in "predecessor" which, to be honest, is rather contrived. You generally see predecessor defined as:

all x, y in Natural : Predecessor(x,y) iff Successor(y,x)

The error in predecessor was created by adding an extra, unnecessary statement about predecessor.

Moving on to the comments, there was an interesting question about "one": Molybdenum1 asked:

This is just nitpicky, but didn't you also assume that the number 1 exists? You claim that we take one of the natrual numbers and call it zero and then define sucessor as a natural number plus 1. But we don't know that 1 exists, or that it is a natural number, unless you define it to be the sucessor of zero, which is circular.

The trick to how we defined the natural numbers in logic is that we only need to define zero and a successor function. The natural number one does not need to be defined beyond the fact that it's the successor to zero. In an informal description of what the successor of a natural number means means, we'll often say that it means the result of adding one to that number. But that's really an informal handwave. In fact, the fundamental property of the natural numbers is that they are a totally ordered sequence of numbers starting at zero.

The "totally ordered" bit there means that for any two numbers x and y, one of three things is true: either x > y, y < x, or x and y are the same. (There are a lot of sets which don't have that property - where you can have an x and y where neither x < y, nor y < x, but they're different. But that's a discussion for another day.)

"Successor" really just advances from one member of the set of naturals to the next in the ordering. Defining one isn't necessary - it's just the number that comes after zero.

One other thing from the comments: Thomas Winwood asked:

For completion's sake, could you prove using your flawed model that 1 > 1 and that 0 + 0 = 23?

DouglasG did a great job answering the question, so I want to promote his answer up here to the font page:

If you have two exact opposite assertions in a system, then any assertion you make must be true. In this case, we have the assertions:

There are no natural numbers less than zero

-and-

There exist a natural number less than zero.

Sometimes the proofs of some statements are not trivial...

Here would be a brief sketch of how 1 > 1 would look.

From the above proof, we know there exists a k where k+1=0. Since 0 < 1, k < 1. Suppose k does NOT equal 1. We know there are no numbers less than zero by definition, so k must be greater than 1 or equal to 0. k cannot be zero because k+1=0. Thus, k must be greater than 1. However, k cannot be greater than 1 because we showed that k < 1. Thus, k=1. Hence, 1 < 1.

More logic: models and why they matter

If you haven't read my earlier posts on logic, and you have trouble understanding this one, you might one to go back and take a look at them:

1. A Bit of Logic
   
2. Calculus - no not that calculus
   
3. Quick Logic: Reasoning and Semantics
   

As I said quite a while ago, when you want to use logic to describe something, it's crucial to have a valid model. A model is a way of showing that the meaning of statements in your logic are valid, by demonstrating the connection between your logic, and something concrete that your logic is talking about. The reason that models are so important is because it's easy to build logical systems that look correct, but which will allow you to prove invalid statements.

Today, I'm going to show you how that works. I'm going to build a logic for talking about the natural numbers - that is, integers greater than or equal to zero. Then I'll show you how invalid results can be inferred using it; and finally show you how it fails by using the model.

One quick thing, to make the notation easier to read: I'm going to use a simple notion of types. A type is a set of atoms for which some particular one-parameter predicate is true. For example, if P(x) is true, I'll say that x is a member of type P. In a quantifier, I'll say things like "all x in P: foo" to mean "all x : P(x) implies foo". Used this way, we can say that P is a type predicate.

How do we define natural numbers using logic?

First, we need an infinite set of atoms, each of which represents one number. We pick one of them, and call it zero. To represent the fact that they're natural numbers, we define a predicate "Natural(x)", which is true if and only if x is one of the atoms that represents a natural number.

Now, we need to start using predicates to define the fundamental properties of numbers. The most important property of natural numbers is that they are a sequence. We define that idea using a predicate, successor(x,y), where successor(x,y) is true if and only if x = y + 1. To use that to define the ordering of the naturals, we can say:

all x in Natural : exists y : Successor(x,y)

Or in english: every natural number has a successor - you can always add one to a natural number and get another natural number.

We can also define predecessor:
all x in Natural : exists y in Natural : Predecessor(y,x)
all x,y in Natural : Predecessor(y,x) iff Successor(x,y)

To be able to define things like addition and subtraction, we can use successor. Let's define addition using a predicate Sum(x,y,z) which means "z = x + y".

all x,y in Natural : exists z in Natural : Sum(x,y,z)

all x,y in Natural : Sum(x, zero, x)

all x,y,z in Natural : (exists a,b in Natural : (Sum(a,b,z) and Successor(a,x) and Successor(y,b) implies Sum(x,y,z)))


Again, in english: for any two natural numbers, there is a natural number that it their sum; x + 0 always = x; and for any natural number, x + y = z is true if (x + 1) + (y - 1) = z.

Once we have addition, subtraction is easy:

all x,y,z in Natural : Difference(x,y,z) iff Sum(z,y,x)

That's: x-y=z if and only if x=y+z.

We can also define greater than using addition:

all x,y in Natural : Greater(x,y) iff Successor(x,y) or (exists z in Natural : Successor(x,z) and Greater(z,y))

That's x > y if you can get to x from y by adding one repeatedly.

So, we've got a nice definition of natural numbers here, right?

Almost. There's one teeny little mistake.

1. We said: all x in Natural : exists y : Successor(x,y)
2. And we also said: all x,y in Natural : Greater(x,y) iff Successor(x,y) or (exists z in Natural : Successor(x,z) and Greater(z,y))
3. We can instantiate (1) with x = 0, as "exists k : Successor(0,k)".
4. And then we can instantiate (2) with x=0 and the k from (3): Greater(0,k) iff Successor(0,k) or ..."
5. Because we know that Successor(0,k), we can conclude Greater(0,k)
6. So, exists k in natural : Greater(0,k)
   

We just proved that there's a natural number smaller than 0.

That doesn't work. The problem is all the way back in the definition of predecessor. It includes: "all x in Natural : exists y in Natural : Predecessor(y,x)", or every number has a predecessor. Zero doesn't have a predecessor. Our logical statements assert something which is not true of the things we're modeling the logic: our logic is invalid. And once we have that error, that there's a natural number less that zero, we can use it to prove anything: 1 > 1, 0 + 0 = 23, anything. All because of one little error in the model.

That's why mathematicians are so particular about proving the validity of their models: because the tiniest error can mean that anything you proved with the logic might not be true - your proofs are worthless.