May Ponder This Solution
The solution to the May puzzle at Ponder This is up. Here are pictures of the six possible configurations; the red edges are the long edges in each configuration.
Cube puzzle
Eight cubes are shown below; the faces of the cubes are colored either red, green or blue. Arrange the cubes to form a larger 2 by 2 by 2 cube so that
- colors of touching faces are the same
- each side of the larger cube is a single color
Here's a pdf file of the cubes suitable for cutting out and pasting together.
Sudoku solver
The June issue of Scientific American has an article on Sudoku, the number grid filling-in game that has swept the puzzle world. (Personally, I find the puzzles tedious, but to each their own.) As a programming exercise for myself, I put together a python Sudoku class to solve a Sudoku problem. It uses a simple backtracking algorithm, summarized below:
Given a valid starting position, for each row, each column and each 3 by 3 sub-matrix, construct a set of allowable entries; these are those numbers that are not yet included in the row (column, sub-matrix). To solve the problem, call the function Fill() on the upper-left cell of the matrix:
Fill (cell):
If the matrix is filled then we have a solution: print it and return
If the cell is not empty, go to the next cell (move left to right, top to bottom)
Else:
find the intersection of the allowable sets for the corresponding row, column and sub-matrix
for each entry in the intersection
place the entry in the matrix, delete that entry from the corresponding sets of allowable entries for the row, column and sub-matrix
call Fill on the next cell
remove the entry from the matrix, add the entry to the corresponding sets of allowable entries for the row, column and sub-matrix
Some comments on the code:
- I've done very little error-checking; here's hoping that strange data doesn't sneak in.
- Solutions can be found very quickly, though when no solutions are possible, the running time can be a couple of seconds. I've not made any attempt at optimizing the code; there may be special tricks that will speed up the process.
- The code could be modified for larger matrices (say, 16 by 16). However, since solving Sudoku problems is known to be NP-Complete, this kind of backtracking approach will not scale well.
- Two other approaches mentioned in the Wikipedia article are using Knuth's Dancing Links (after modeling the problem as a graph-coloring problem) and constraint programming. These would probably be better than the simple backtracking I used.
Sums of products of random integers
Let `f` be a function that chooses a random integer from 1 to 100 (inclusive) with a uniform probability distribution. Then the probability that what `f` returns is an even integer is 1/2. We will use `f * f` to denote calling `f` twice and multiplying the results, so it is simply the product two randomly chosen integers. In general, let `f^n` represent calling `f` `n` times and multiplying the `n` random integers returned.
Let `P(a = E)` be the probability that `a` is an even integer and `P(a = O)` the probability that `a` is odd. Show that
`P(f^n = E) = 1 - (1/2)^n`
`P(\sum_{k=1}^n f^k = E) = 1/2`
So the probability that the product of a large number of these random integers is even is close to 1, but the probability that the sum of the products of these random integers is even is always 1/2.
What happens if `f` chooses a random integer from 1 to 3? Or more generally, assume that `f` is choosing from some finite set of positive integers with `a` even integers and `b` odd integers. Now what is the probability that the sum of the products, `\sum_{k=1}^n f^k`, is even?
Let `s_n = P(\sum_{k=1}^n f^k = E)`. Set `p = b/(a+b)`, so `s_1 = 1 - p`. Following the proof of (2), we can write a recursive expression for `s_{n+1}`:
`s_{n+1} = P(f^{n+1} = E) s_n + P(f^{n+1} = O) (1 - s_n) = (1 - p^{n+1})s_n + p^{n+1} (1 - s_n) = p^{n+1} + (1 - 2p^{n+1})s_n`.
Since `|s_{n+1} - s_n| < p^{n+1}`, the sequence `\{s_n\}` forms a Cauchy sequence, and so converges to some value `A`.
But what is `A`? Numerical experiments indicate that it is not 1/2 (or if it is, then the rate of convergence is very slow) and a closed form expression for `s_n` generated by Maple is not especially helpful. So at this point I'm stumped.
Deconstruction examined
In INTELLIGENT DESIGN THEORY AND THE SUPERNATURAL — THE “GOD OR EXTRA-TERRESTRIALS” REPLY philosopher Elliot Sober lays out an argument that he says "is not an argument that I am advocating, but one to which ID theorists need to respond":
Sober's argument:
If a system found in nature is irreducibly complex, then it was caused to exist by an intelligent designer.
Some of the minds found in nature are irreducibly complex.
Therefore some of the minds found in nature were caused to exist by an intelligent designer.
Any mind in nature that designs and builds an irreducibly complex system is itself irreducibly complex.
If the universe is finitely old and if cause precedes effect, then at least one of the minds found in nature was not created by any mind found in nature.
The universe is finitely old.
Causes precede their effects.
Therefore, there exists a supernatural intelligent designer.
Now, there are points of this argument that could be open for discussion. For example, does Sober adequately support premise (2), that some minds are irreducibly complex? But the argument is, on the whole, logically valid.
However, DaveScot of Uncommon Descent doesn't agree. In his 'deconstruction' of Sober, DS tries to show that the conclusion of Sober's argument is wrong (since ID cannot be seen to support theism). But where DS sees flaws in Sober's argument, I see poor reasoning by DS.
Here are his replies to Sober's points:
2. Some of the minds found in nature are irreducibly complex.
We only have one mind to examine in nature and we don’t know what causes it to exist. Therefore we cannot say that it is irreducibly complex. Given 2 is a false premise and is Sober’s first flaw.
Right away DS is off track. The definition of 'irreducible complexity' does not depend on causation. Sober provides Behe's definition: "...a single system composed of several well-matched, interacting parts that contribute to the basic function, wherein the removal of any one of the parts causes the system to effectively stop functioning." There is no mention of what caused the supposedly irreducibly complex system. In fact, the entire point of Behe's argument is that irreducible complexity entails that the system could not be caused by incremental process such as evolution. If we need to know the cause of some thing in order to call it irreducibly complex, Behe's argument would be vacuous.
It could be that this premise is problematic, since the notions of 'mind' and 'irreducible complexity' are not terribly precise. Sober does try to give some justification for the premise, something that DS seems to ignore altogether. DS needs to do more work to dismiss this premise.
3. Therefore some of the minds found in nature were caused to exist by an intelligent designer.
This conclusion is unsupported due to the false premise in given 2. Even if it were not fallacious it does not assert that all minds found in nature are of intelligent cause. This is Sober’s second flaw. He fails to demonstrate that all minds in nature depend on intelligent causation.
A minor quibble: the argument Sober gave in 1,2, and 3 is valid. If one of the premises is false, then the argument is not sound, not fallacious. But it's not that significant.
What is more significant is the irrelevancy of DS's complaint that Sober "fails to demonstrate that all minds in nature depend on intelligent causation." That's not what Sober is trying to do -- his argument concludes only that some minds are caused by an intelligent designer. DS is criticizing Sober for not proving something that Sober wasn't trying to prove.
4. Any mind in nature that designs and builds an irreducibly complex system is itself irreducibly complex.
We have no idea how many minds exist in nature much less whether they are all necessarily irreducibly complex. Another false premise given by Sober and his third flaw.
DS misstates the premise. Sober is not saying that all minds in nature exhibit irreducible complexity. He is saying that if a mind has designed and built an irreducibly complex system then the mind itself must be irreducibly complex. It could very well be that there are no minds in nature (though I don't think that most people would want to adopt that premise without some justification); Sober's premise is silent on that point.
This premise is crucial: it is a key part of the "who designed the designer?" argument that DS dismisses as an infinite loop. Unfortunately he fails to see that the argument requires an answer, one that Sober is asking for. Is it possible for an intelligent agent (that causes an irreducibly complex system to exist) to not itself contain some irreducibly complex components?
5. If the universe is finitely old and if cause precedes effect, then at least one of the minds found in nature was not created by any mind found in nature.
It does not follow from finite age and cause/effect that there must exist a mind in nature that was not created by another mind. We do not know how minds are created, even our own, to say nothing of minds never observed. Flaw number four.
DS is basically giving an argument from ignorance: Since we don't know how minds are created, we can't say anything about the chain of causation linking irreducibly complex minds. However, Sober gives a more detailed argument to support this premise, one that DS seems to ignore.
In particular, Sober posits that the time for an intelligent designer to create a new mind in nature is finite but positive; with this and a finite age of the universe, there can only be finitely many intelligent designers (the number may be huge, but still finite). Perhaps Sober is wrong, but DS needs to explain why Sober's assumption is not justified, other than simply saying "we don't know".
6. The universe is finitely old.
No one knows if the universe is finitely old as physics has no means of describing what came before a singularity known as the big bang nor does physics have a means of describing what if anything existed outside the singularity. This is why we speak of an “observable” universe. The observable universe appears to have a finite age but there is no way of knowing what, if anything, is beyond the bounds of the observable. Sober lacks a basic understanding of the limits of physics in describing the universe. This is flaw number five.
Sober provides a footnote that gives an age of the universe suggested by the 'big bang' cosmological theory. While it is true that there are areas open for questions related to specific inflationary models, there is significant evidence for the general theory. Sober is well within standard scientific understanding to refer to a 'start' of the universe. DS is again using an argument from ignorance: we don't know if the universe is finitely old so Sober's premise must be false.
7. Causes precede their effects.
This is also something physics does not unambiguously demonstrate. It is not demonstrated by any means that the observable universe is deterministic. There is a wide belief among quantum physicists that quantum uncertainty is real and not just an artifact of incomplete knowledge. If quantum uncertainty is real and quantum events influence macroscopic events then effects can exist without cause. This is Sober’s sixth flaw.
Sober provides a weakened form of this premise that DS does not address: "cause must precede effect when the cause is an intelligenct designer's designing and constructing an irreducibly complex system and the effect is that system's existing and being irreducibly complex" (Footnote 7). In this form, Sober is referring to a speific kind of 'cause' and 'effect' where it is not as clear that quantum mechanics necessarily plays a part.
But DS misses Sober's point anyway. Sober is not claiming that effects can exist without cause. Sober is saying that if an effect has a cause then that cause comes first. Again, QM may play a part, but for DS to use this as a refutation of Sober's premise, he needs to establish that the kinds of causes and effects Sober is concerned with are subject to QM, not just that they could be.
8. Therefore, there exists a supernatural intelligent designer.
As I have shown this conclusion is based on so many logical and scientific fallacies it is laughable. About the only thing that Sober got right was in the first assertion that irreducibly complex systems must be intelligently designed. And that itself is hotly debated too but we ID theorists accept it as a given.
DS's point is logically flawed---he has committed a 'bad reasons' fallacy: the argument for a conclusion is flawed therefore the conclusion must be false. But the conclusion may still be true, even if Sober's argument has failed to convince DS, or if DS simply doesn't want to accept the conclusion because he needs to deny that ID implies the existence of a supernatural designer.
As I mentioned, Sober's argument is open to criticism. (See this post at Panda's Thumb by Pim van Meurs for more discussion of the article and the ID response to it.) Unfortunately, DaveScot doesn't provide any real discussion of the points, but instead misrepresents Sober's argument, appeals to arguments from ignorance, and, ultimately, rejects the conclusion because he thinks the argument is invalid, a logically invalid conclusion itself.
The number 7712
The number 7712, prime factorization `2^5 241`, appears in several integer sequences. An interesting one is A063776, the number of subsets of `\{1,2,...,n\}` which sum to 0 mod `n`. Investigating this sequence some more leads to a result about the number of losing positions in the game of Nim.
Recall that Nim is played with sticks in heaps: a move is to remove any number of sticks from a single heap and the loser is the player who cannot take any sticks. If there are `k` heaps of `n_i` sticks in heap `i`, then we write the position as `(n_1,n_2,...,n_k)`. If there are no sticks in any heap then the position is (0); if there is more than one heap then we will assume that all the `n_i` are positive (since a heap with 0 sticks doesn't affect the game).
Theorem. Fix `m \geq 1`. The number of losing positions `(n_1,n_2,...,n_k)` in the game of Nim where the `n_i` are distinct and less than `2^m` is `L_m = 2^{2^m - m - 1}`.
Example: if the heap sizes can be between 1 and 7 then `L_3 = 16`. The losing positions are: (4, 5, 6, 7), (3, 5, 6), (3, 4, 7), (2, 5, 7), (2, 4, 6), (2, 3, 6, 7), (2, 3, 4, 5), (1, 6, 7), (1, 4, 5), (1, 3, 5, 7), (1, 3, 4, 6), (1, 2, 5, 6), (1, 2, 4, 7), (1, 2, 3), (1, 2, 3, 4, 5, 6, 7), and (0).
The connection between this result about Nim and the number 7712 can be found in We will get to this result about Nim from the number 7712 through the paper An interesting result about subset sums by N. Kitchloo and L. Pachter. In that paper, the authors derive a formula for the number of subsets `B` of `\{1,2,...,n\}` such that `\sum_{b\in B} b \equiv k` mod `n`.
For example, there are 6 subsets of `\{1,2,3,4,5\}` whose members have sum congruent to 2 mod 5: `\{2\}, \{1,2,4\}, \{3,4\}, \{0,2\}, \{0,1,2,4\}, \{0,3,4\}`.
The formula given by Kitchloo and Pachter works for arbitrary `k` and `n` and involves Euler's totient function `\phi(t)` and the Mobius function `\mu(t)`. But for the special case that `k \equiv 0`, the formula reduces to
`N_n = 1/n \sum_{t|n, t odd} 2^{n/t} \phi(t)`
(By convention, the empty set is included in this count.) It's not hard to see that the number that started this, 7712, is `N_{17}`.
Kitchloo and Pachter also present a formula for the number of subsets of a finite abelian group `G` whose elements sum to the identity element (0) of `G`. This formula is not terribly complicated but all we will need is the special case that `G` is the direct sum of `m` copies of `\mathbb Z_2`. Then the formula for the number of subsets with zero sum is simply `2^{2^m - m}`.
Now, this count includes the empty set and the set containing just the zero element `(0,0,...,0)`. Of the others, half will contain only non-zero elements, so there are `2^{2^m - m - 1}` nonempty subsets with zero sum and either only non-zero elements or the single element `(0,...,0)`. This is the number given in the theorem; we need only connect it with losing positions in Nim.
There is an easy way to tell if a position in Nim is winning or losing: XOR the binary digits of the number of sticks in the heaps. If the result is all 0's then the position is losing, otherwise it is winning (and the person to move should take the number of sticks needed to change the XOR to all 0). Here's an example with 4 heaps:
| # sticks | Binary |
|---|---|
| 3 | 0011 |
| 9 | 1001 |
| 12 | 1100 |
| 15 | 1111 |
| XOR: | 1001 |
Since the XOR is 1001 and not 0000, this is a winning position for the player making the move; he should take 9 sticks from one of the heaps.
The connection between positions of Nim and `\mathbb Z_2^m` is obvious: map the number of sticks in a heap with its binary representation (padded to the left with 0's if needed), then a Nim position is a subset of `\mathbb Z_2^m`; the zero element of `\mathbb Z_2^m` corresponds to the zero game (0) of Nim. Since XOR binary digits and addition in `\mathbb Z_2^m` are equivalent, losing positions of unequal heap sizes are in one-to-one correspondence with subsets of `Z_2^m` with sum of `(0,...,0)`. This proves the theorem.
It turns out that the sequence `L_m` is sequence A016031, a de Bruijn sequence (the number of ways of arranging `2^n` bits in a circle so all `2^n` consecutive strings of length `n` are distinct). And that looks interesting as well...
All we need is money
DaveScot at Uncommon Descent is now blaming judges for the lack of scientific research in intelligent design:
What’s standing in the way of ID is the judicial system and most of that is prejudicial i.e. the judge sits on the bench with a preconceived notion that ID is not science and the Darwinian fairy tale is as strong as the theory of gravity.
and in a later comment on the same thread
Can researchers get public funding for ID research so long as it’s legally considered a religion? Will any kids grow up to be ID researchers if they’ve been brainwashed in public school into thinking NDE is uncontested fact? Take all the time you need to arrive at the correct answer.
Poor ID scientists. If only they could get some money then we'd see some real research.
Then again maybe there is ID research going on and we just don't see it, since in the very next comment he writes
It needs to be pointed out that ID relies on exactly the same data that NDE is built upon.
Data is not owned by any particular theory.
Francis Crick wasn’t out to test ID theory but his discovery that DNA incorporates a digital code that is translated into instructions for a protein assembling machine (ribosome) is perhaps the most compelling bit of evidence in existence for intelligent design theory. It certainly is for me since my expertise partially lies in digital process controls used in factory automation.
All biology, paleontology, genetic, biochemical, and related reasearch is thus ID research because ID relies on evidence without regard to who found the evidence or what they were looking for when they discovered it.
I feel your pain in that if you do the research you feel entitled to keep it from being employed by contrary hypotheses but that’s just the way the cookie crumbles. The evidence is available to everyone. Get used to it.
Wait, wait. How the heck does this work? On the one hand the judicial system is blocking ID research funding (how a judge gets involved in NSF or other funding agencies isn't made clear), but then again, every piece of research is ID research. The only way these two positions can be reconciled without calling DaveScot an idiot is to say that there is no research funding at all! Of course there is research being funded, so we're left with the obvious conclusion...
The fact is, there are several places that an ID proponent could apply for funding, including the Discovery Institute. And what's more, an ID proponent could even apply for funding from the NSF or other traditional sources as long as he had an actual research program to fund. Heck, they have even claimed a recent mainstream article as supporting intelligent design. How about carrying out more of that kind of research instead of sitting around carping about not being funded when you haven't even proposed a project to fund?
UPDATE: DaveScot now claims that the Discovery Institute doesn't have enough money to fund research, saying that the DI's budget of 1.2 million dollars "isn’t enough to keep even a single modest research lab equipped, staffed, and running for a year." I find that hard to believe, as well as not especially dispositive of the overall point.
For one, much of the research done by the NSF is carried out in academia, where the institution also pays to support the researcher(s), equip the lab, and provide incidental funding (in exchange, of course, for that most menial of tasks: teaching). We're not talking about starting a lab from whole cloth. How about getting one project funded, produce some results, and then go from there? Hey! That's science!
Further, the median research award by the NSF in the biological sciences in FY 2007 was \$148,000 (a year, for about three years) (see the BIO Performance Indicators spreadsheet at this page). That's the median. So let's assume that a proposal could be funded for about 2/3 of that, say \$100,000. Could the Discovery Institute afford to chip in \$100,000 a year for three years? I suspect so, especially when it pays its fellows on the order of \$50,000. Cut a couple of 'fellows' and you have yourself a research grant. Couldn't we find two of them willing to make the sacrifice in the name of science? (Elsberry has more to say about their budget.)
Or, even better, an ID 'researcher' could apply at any number of other private funding sources, including the Templeton Foundation. Heck, at Templeton they are already funding some projects "to stimulate and sponsor new research insights directly pertinent to the 'great debate' over purpose in the context of the emergence of increasing biological complexity, ranging from the biochemical level to the evolution of life and the emergence of society and culture."
And I still think the NSF would fund proposals if they were, you know, actually scientific.
Dembski's post of a post
William Dembski links here to a post on another blog about a recent article in the Chronicle of Higher Education. The Chronicle article discusses the dangers (and, unfortunately, fact) of data misuse and forgery in science.
Why did Dembski link to the post? Don't know. He rarely offers any kind of discussion of his posts---he simply links to an article and leaves it to the reader to draw the appropriate conclusions. In this case, only his post title, "The Fetid Little Fingers of Science" indicates his stance.
But a few things come to mind after reading the post he links to:
The article draws attention to the motives of the scientists who engage in some kind of misconduct; many of them do so because of some "perceived injustice." According to the Chronicle article, "When scientists perceive injustice in their workplace, particularly regarding how rewards are distributed, they are more likely to compromise their integrity, the researchers found."
Interesting. So are ID proponents who feel that the scientific establishment is against them and their work more likely to distort their research? Should we be on the lookout for ID misbehavior?
Dembski's post title implies that the scientific community is dysfunctional and corrupt (or at least that's the message I got -- if he didn't mean that, he might want to actually, you know, write something in his post). But if ID is science, as its proponents claim, are their fingers also fetid? Or is it just those who oppose ID who are stinky?
In Dembski's post, he quotes the entire article he links to (not exactly appropriate), but, oddly, leaves out a sentence in the last paragraph. While Dembski's quote of the article reads
The article is of interest primarily because it details the extensiveness of scientific misconduct. Our society tends to place inordinate trust in science and in scientists, assuming that the scientific method effectively removes the risk of misbehavior. The Korean stem cell and cloning scandal should be sufficient warning. This article brings the issue much closer to home.
the original article is
The article is of interest primarily because it details the extensiveness of scientific misconduct. Our society tends to place inordinate trust in science and in scientists, assuming that the scientific method effectively removes the risk of misbehavior. In a fallen world, this could never be true. The Korean stem cell and cloning scandal should be sufficient warning. This article brings the issue much closer to home.
(emphasis mine). Out of the entire quote, Dembski leaves out that one sentence. No ellipses or [snip] or anything to indicate that he removed text from the quote. I wonder why that sentence bothers him so much. Could it be that he is still trying to disassociate intelligent design 'theory' and theology?
Okay, so he didn't quote that one sentence (but did quote the rest of the post). Not exactly earth shattering. Except that he was linking to a post about scientific integrity. Would it have been too much to ask for some integrity from Dembski? Irony, thy name is 'Bill'.
Fun with KnotPlot
KnotPlot is a wonderful program for generating, viewing, playing with knots. The program itself has been around for a while, but I first saw it yesterday at a talk on knots. A description of the features of KnotPlot:
Knots can be loaded from a database of almost 1000 knots and links or sketched by hand in three dimensions. Also, knots may be constructed via the Conway notation or using a tangle calculator. A number of special knot types (torus knots, knot chains, Lissajous knots) may be created on the fly. Finally, new knots can be created from old knots using a number of transformations.
There are lots of extras beyond knots, such as creating knots from braids, Celtic knots, and other fascinating demos. In addition to a nice learning tool for knot theory, this is the kind of thing I could spend hours just playing with.
No Need for Voting
I helped judge a science fair this weekend, and in the process came across an instance of over-mathematization of the world.
The situation was this: I and a group of 5 other people were charged with the task of selecting the top three projects from about a dozen. After going through each project individually and then again as a group while talking with the students who worked on the project, we came up with our own impressions of each project. Now to the decision stage.
We first went down the list of projects and eliminated those that we felt were not 'top three' material. We did this by general consensus: if anyone felt that a project was worth talking about some more then it was added to the list of potential winners. At the end of this we had six projects to consider.
So how do we decide which project is top ranked, which is second ranked, and which is third? This can be viewed as a voting problem, and a method to solve it is called a voting system.
Now, there are lots of voting systems. The most common one is simple majority rule---vote for the choice you most prefer and count how many votes each choice (candidate) receives; the winner is the one with the most vote. Unfortunately, this obviously may not work for more than two choices.
For three or more choices, we could just determine the winner by plurality: the winner is the one with the most votes, though not necessarily the one with the majority of votes. But this method has some problems, most obviously that we need to do more than select a single winner; we also need second and third place. Plurality voting also has the problem that it may encourage voters to not vote for their top-ranked choice, especially if it appears that that their third-ranked choice will win a plurality of the votes. Perhaps by voting strategically (and not true to their preference), a voter can swing the election to their second-ranked choice.
Another method we could use is a Borda count: each person assigns `n-1` points to the top-ranked choice, `n-2` points to the second-ranked choice, and so on to 0 points for the last-ranked choice. Then the points are totaled for each candidate and the winner is the one with the most points (and the second and third place can also be determined). This will find our rankings in one vote.
However, the Borda count also has its problems. In some situations it is possible for a group of voters (or even one voter) to change their rankings and make a winner become a loser while still ranking the original winner first! For example, suppose there are 22 voters with these rankings:
| # voters: | 5 | 4 | 2 | 4 | 1 | 6 |
| 1st | A | A | B | B | C | C |
| 2nd | B | C | A | C | A | B |
| 3rd | C | B | C | A | B | A |
| Points: | ||||||
| A | 10 | 8 | 2 | 0 | 1 | 0 |
| B | 5 | 0 | 4 | 8 | 0 | 6 |
| C | 0 | 4 | 0 | 4 | 2 | 12 |
So A gets 21 points, B gets 23 points and C gets 22 points; the Borda ranking is B-C-A. But now suppose that the 4 voters who prefer B-C-A were to change their preferences to B-A-C. They still prefer B (the previous winner), but now the Borda totals come out to 25 points for A, 23 points for B and 18 points for C. Candidate A has gone from third place to first, and the voters who put him there still prefer B to win!
Other voting systems have other problems. In fact, given a set of quite reasonable criteria that a voting system should satisfy (such as not allowing the situation above), there is no voting system that satisfies all of the criteria. This is upshot of Arrow's Impossibility Theorem.
So which voting system should we have used to rank the projects? In fact we didn't use any of them, for the simple reason that we didn't need to. After ranking the projects individually, we put our rankings on the board and saw what the consensus was. In our case, it was clear which project was ranked first, and that the second-third ranks were between two others. After a brief discussion, we all agreed on an ordering and that was that.
And in our case, that was the best option. There was no need to 'quantify' the results since there was no need for a final, end of discussion vote. Unlike most elections, the group was able to continue discussion about the projects until there was a consensus. Perhaps if we had not been able to reach a consensus we would have had to vote, but luckily that wasn't necessary.
However, one member of the group insisted on getting 'objective' results that would 'quantify' the situation, using what (I think) amounted to the Borda count system. With these results, he argued, we could see that the 'right' result was, and so eliminate possible 'force of personality' effects that may arise during discussion.
But why should the Borda count give the 'right' result? Why should any one quantification be preferred over any other? I could understand why it would be nice to protect the wilting lilies of the world who cannot stand up for themselves, but when our rankings are arrived at independently, then displayed for all to see, I'm not sure that personality problem is very significant. (And lest I be accused of being the forcing personality, I should point out that I said nothing at all during the discussion of our second-third choices.)
I think he places too much emphasis on 'quantified' results, especially in this case when there was no need for them. It was especially curious given that there is no objective way to determine which system we should have been using. After all, what criteria we want our system to satisfy is a matter of preference itself; should we have a vote to determine what voting system we should use?
Mathematics is good, and quantification can be useful, but sometimes it is not necessary for reaching a good decision.
Ramanujan movie in the making
British actor/director/writer Stephen Fry is reportedly working on a film about Indian mathematician Srinivasa Ramanujan.
This film would continue the apparent increased interest in mathematics/mathematicians/eccentric (or mentally disturbed) geniuses. Some other exhibits:
the book and movie A Beautiful Mind
the movie Good Will Hunting
the play and movie Proof
the tv series Numb3rs
the movie Pi (very disturbing, the mathematics actually plays a small role)
the documentary N is a Number about Paul Erdos
2006 Abel Prize announced
Swedish mathematician Lennart Carleson has been awarded the 2006 Abel Prize (BBC report). The award was based in large part on Carleson's work on Fourier series.
But I'm not sure what to make of this part of a Reuter's report:
"The prize statutes say it should aim to spur interest in mathematics among children and young people. So far, all winners of the prize have been in their 70s."
Is Reuter's trying to make a little dig at the Abel awards committee?
Enumerating HiLo arrangements
A recent post, Ask Mathforge: What are the Odds? at mathforge.net asks a question about the game of High-Low. In the game, a card is turned over (from the top of a regular shuffled deck) and the player is asked to guess if the next card will be higher or lower than the one shown. A simple strategy to play the game would be to guess 'High' if the card is an ace through 6 (consider ace to be '1'), 'Low' if the card is 8 through King, and flip a coin if the card is a 7. Intuitively, the player is playing the best he can without memory.
If we make the assumption that the player always gets the random coin flips correct, what is the probability that he will get every turn correct through the entire deck?
An estimate of the probability puts it at around 1.5 million to 1 (with a few other assumptions). In my approach to the problem, I wanted to count how many arrangements of the cards would be 'good' ones---the player will win following the given strategy (and luck to guess correctly on the middle 7 card). Since there are `{52!}/{(4!)^{13}}` possible arrangements of the cards, we could then determine the probability.
For ease of discussion, let's make the following definition. Given `n` cards of each rank from 1 to `m` (for a total of `mn` cards in the deck), a Hi-Lo arrangement of the cards is an arrangement `a_1 a_2 a_3 \dots a_{mn}` that satisfies
- `a_i < a_{i+1}` if `1 \leq a_i < m/2`
- `a_i > a_{i+1}` if `m/2 < a_i`, and
- if `a_i = m/2` then there are no restrictions on `a_{i+1}`
However, computing `HL(13,4)` by hand (meaning: with a computer search), is not likely. The numbers grow very, very quickly. Here's a summary of some of the values for small `m` and `n`:
| `HL(m,n)` | cards per rank | |||
|---|---|---|---|---|
| ranks | 1 | 2 | 3 | 4 |
| 2 | 2 | 2 | 2 | 2 |
| 3 | 6 | 30 | 174 | 1092 |
| 4 | 14 | 230 | 4834 | 114442 |
| 5 | 78 | 14094 | 3785126 | 1225289412 |
| 6 | 230 | 187106 | 250560122 | |
| 7 | 1902 | 26185806 | ||
| 8 | 6902 | 557115782 | ||
| 9 | 76110 | |||
| 10 | 329462 | |||
The even `m` values in the first column is sequence A048163 in the On-line Encyclopedia of Integer Sequences. The row corresponding to `m = 3` is sequence A110706.
Even for three ranks, the closed-form expression for `HL(3,n)` is complicated. I'm not even sure how to approach the problem of finding `HL(4,n)` for `n\geq 2`, or even what kinds of estimates would be reasonable for `HL(13,4)`.
So the question is still open: what is the probability of getting a HiLo arrangement?
Lindner's Conjecture Solved
Daniel Horsley, a doctoral student at the University of Queensland, Australia, has reportedly solved Lindner's conjecture on Steiner triple systems.
Let `V` be a set of size `v`. A Steiner triple system (of degree `v`) is a collection of subsets of size 3 such that each pair of elements in `V` appears exactly once in an element of the collection. Put another way, a Steiner triple system is a partition of the edges of the complete graph on `v` vertices into triangles. For example, a Steiner triple system of degree 7 is illustrated below.
There are Steiner triple systems of degree `v` if and only if `v` is congruent to 1 or 3 mod 6. The number of nonisomorphic Steiner triple systems increases very quickly: at `v = 13` there are 80 systems; at `v = 19`, there are 11084874829 different systems.
Lindner's conjecture is about embedding partial Steiner triple systems (a partition of some subset of the edges of the complete graph into triangles). Lindner conjectured that any Steiner triple system of degree `v` can be embeddedin (extended to) any Steiner triple system of degree at least `2v + 1` (and also congruent to 1 or 3 modulo 6).
Steiner triple systems show up in combinatorial design theory, an area of mathematics that aids in the design of statistical experiments (though, as is usual, many important mathematical concepts predate their application and go beyond the applications today). For example, given a collection of different varieties of seeds that we would like to test for (say) hardiness, and a collection of plots where we might plant the seeds, how do we assign seeds to plots so that we can discern differences in seed varieties from differences in land plots?
More information on Steiner triple systems can be found at mathworld and on design theory at DesignTheory.org and the DMOZ Open Directory entry on Design Theory.
RSA-640 Factored
The 193-digit number
310 7418240490 0437213507 5003588856 7930037346 0228427275 4572016194 8823206440 5180815045 5634682967 1723286782 4379162728 3803341547 1073108501 9195485290 0733772482 2783525742 3864540146 9173660247 7652346609
has been factored. Mathworld explains why that is a big deal.
Accountability in Jordan
This is curious:
11 Jordanian officials resign after bombings
AMMAN, Jordan (AP) — Eleven top Jordanian officials, including the kingdom's national security adviser, resigned Tuesday in the wake of last week's triple hotel bombings, state-run TV announced.
[snip]
The TV announcement made no reference to last Wednesday's attacks on three Amman hotels that killed 61 people and dented the reputation of the country's revered security services.
But the bombings sparked national outrage and raised concerns over the handling of the security services.
There has also been criticism over how the four Iraqi cell members entered Jordan on November 5 without being detected before carrying out their attacks.
Compare what happened to these Jordanian officials with what happened in the U.S. after 9/11. Were there any resignations of top officials here? Did anyone really accept responsibility? Was anyone held accountable for security failings?
Now, I do remember that Bush chastised George Tenet, the director of the CIA at the time. I fact, here's a video of it and even a nice closeup shot of a chastised Tenet. Oh...wait a sec...he wasn't being chastised was he? No, Tenet was given a freakin' Medal of Freedom!
Grrrr....
The attack in Jordan killed over 60 people, which is certainly horrific. The WTC attack killed 3000. The attack in Jordan was simple and required relatively little planning. The WTC attack involved coordination and planning that stretched over many months, if not a few years. The attack in Jordan was carried out by people who needed to travel only a short distance (from Iraq) and who didn't need to stay 'in-country' for an extended period of time. The attack on the WTC involved people who lived in the U.S. for years and some flew regularly in and out of the country.
If any officials needed to resign, it was those in the U.S.
Friday afternoon math fun
Show that there are no five-digit numbers such that if you remove the first two digits and place them at the end (e.g., 12345 to 34512) then the resulting number is half the original.
Note: of course the number 00000 would work, but we will ignore that trivial case.
Axioms of Set Theory
I've been doing some reading on basic set theory (as part of an "intro to proofs" course) and have been debating what to do with the axioms of Zermelo-Fraenkel set theory. Mathworld lists 9 axioms (plus the Axiom of Choice for a total of 10). Which ones really need to be discussed and how much weight should they have?
Those that I am thinking of focusing on include:
Extensionality: `\forall A \forall B [(\forall x (x \in A \iff x \in B)) \Rightarrow A = B]` (Two sets `A` and `B` are equal if they contain the same elements.)
Unions: `\forall S \exists U \forall x [x \in U \iff \exists A (x\in A \wedge A \in S)]` (For any collection `S` of sets, there is some set `U` that contains the elements of the sets `A` in `S`.)
Null Set: `\exists A [\neg \exists x (x \in A)]` (There exists some set `A` such that it is not the case that there exists any `x` contained in `A`; the set `A` is unique and we denote it by `\emptyset`.)
Power Set: `\forall A \exists P \forall B (B \in P \iff B \subseteq A)` (For any set `A` there exists a set `P` whose elements are the subsets of `A`; the set `P` is unique, denoted `\mathcal P(A)`. Also, `B \subseteq A` is shorthand for `\forall x (x \in B \Rightarrow x \in A)`.)
Regularity: `\forall A [A \ne \emptyset \Rightarrow \exists x (x \in A \vee \neg \exists y (y \in x \vee (y \in A))]` (Every nonempty set `A` contains an element `x` such that `A` and `x` are disjoint; this prevents Russell's Paradox by requiring that if `A` is a set then `A` is not an element of itself.)
The Axiom of Infinity I think I would like to introduce when we are focusing on the axioms of the natural numbers (since we can use that axiom to produce a model of the natural numbers). The other axioms of ZF I think would be nice to state, but don't want to spend much time on in class -- this is the first time many of the students will have encountered axiomatic reasoning (I don't count high school geometry) and they may be overwhelmed if the axioms get too esoteric (in their view).
Same thing for the Axiom of Choice. We would need to talk about it, but I don't want to throw the students into the deep end, axiomatic-wise.
We have a 97% chance of resurrection this evening
Richard Swinburne, a philosopher of religion at Oxford, pegs the probability that Jesus really was resurrected at 97 per cent.
"New Testament scholars say the only evidence are witnesses in the four gospels: that's only 5 per cent of the evidence," said Professor Swinburne, a leading philosopher of religion.
"We can't judge the question of the resurrection unless we ask first whether there's reason to suppose there is a God, second if we have reason to suppose he would become incarnate, and third, if he did, whether he would live the sort of life Jesus did."
Professor Swinburne, who gave a public lecture at the Australian Catholic University last night, said probability calculus showed a probability of 97 per cent. The probability God existed was one in two. That is, God either did or didn't. And it was one in two that God became incarnate.
Professor Swinburne suggested a one-in-10 probability that the gospels would report the life and resurrection of Jesus as they did. The chance of all these factors coming together, if the resurrection was not true, was one in 1000.
Umm...yeah. I'm not impressed. Interestingly, when Swinburne puts the probability that God exists at 1 in 2 because "God either did or didn't", he is using the Principle of Indifference---when you have no reason to think of one outcome as any more likely than another, you may assign equal probabilities to all possible outcomes.
Agents in a Virtual World
Researchers in a consortium of European institutes are putting together a virtual world in which the "agents" will be able to build objects, cultivate crops, and communicate with each other. The project is called NEW TIES: New and Emergent World models Through Individual, Evolutionary, and Social Learning.
The experiment will see about 1000 agents live together in a simulated world hosted on a network of 50 computers based at the various institutions involved.
Each agent will be capable of various simple tasks, like moving around and building simple structures, but will also have the ability to communicate and cooperate with its cohabitants. Though simple interaction, the researchers hope to watch these characters create their very own society from scratch.
Every character in the simulated world will need to eat to survive, and will be able to learn from their environment through trial and error - learning, for example, how to cultivate edible plants with water and sunlight. In addition, characters will be able to reproduce by mating with members the opposite sex and their offspring will inherited a random collection of their parents "genetic" traits. Random word generator
Perhaps most importantly, however, by pointing to objects and using randomly generated "words", characters should be able to conjure up their very own language and communicate with others inside their world.
And this language may bear little resemblance to anything spoken in human societies. "It's quite possible they will develop a language that we have to interpret," says Ben Paechter at Napier University in Scotland. "They may discuss things in ways we find difficult to understand."
However, the ability to communicate could enable these agents to develop complex cultural activities resembling those found in small human societies. "A long-term aim is to see if we can get culture to emerge," Paechter adds. "This way, we might learn something about the way human societies evolve."
Some think their plans are a bit too over-reaching. As reported by the article, even if the agents in the virtual world developed some interesting behaviors and "social" dynamics, what would it say about our own societies? Probably not much. And their behaviors will be very much constrained by whatever programming rules are set up by the researchers -- they may end up pre-selecting for particular kinds of behaviors that, in the end, have little connection to "real life".
But hey, it looks pretty cool. Computer code (when it is released) and other white papers/research notes can be found at the NEW TIES website.