A better yodeling contest

Since I can recall having any opinion on the subject, I have considered myself a mathematical formalist: "Doing math" means formal symbol manipulation, and its relevance lies solely in the utility or beauty of the maths. Formalism can be contrasted with platonism, since a platonist believes that a statement, like the axiom of choice, undecideable in a given system may still have an objective truth value, and it is reasonable to discuss whether such a statement is true or false, even though it cannot be proved either way. A formalist laughs at such assertions, and simply explores all the possibilities available: and in this case an axiomatic system which rejects the axiom of choice may be just as interesting as one which accepts.

I considered myself a formalist until Thursday. On that day, the BBC online published an article entitled 1200-year-old problem 'easy' which celebrated a crank's solution to the problem of dividing by zero. Reading his papers, it was obvious that he was mostly assigning the symbol $Phi$ to mean "undefined", and any operation which is not closed under the reals goes to $Phi$. To a formalist, thiskind of thing is fine, if useless. We can create whatever symbols we want, and assign whatever meanings we want, and then see what happens. Granted, it is frustrating that someone could be regarded as a "genius" by doing this, even if only by a journalist for an online newspaper.

Actually, outrage is an appropriate response to him hoodwinking a local school to teach children this kind of nonsense.

I was disturbed, though, by a thought that gripped me as I read his papers, though: $1/0=infty$? $-1/0=-infty$? Wait, he defines $0^0=Phi$ instead of 1? It's not only useless, it's wrong.

I had to sit back and recollect myself. How could it be wrong? How can any consistent mathematical statment really be wrong? Surely, I'm not having such platonist thoughts, am I?

Then I remembered an experience I had reading through Sierpinski's Cardinal and Ordinal Numbers earlier in the week. Why is he spending so much time on philosophy of the Axiom of Choice when it is obviously true? It can't be "obviously true" to a formalist, since it is well known that its negation is consistent with the relevant axioms in set theory.

And the, the most damning evidence. I had written up a brief note on a particular product on posets, which seemed more useful than the one given in Harzheim's Ordered Sets. One point being that it could be seen as a generalization of both cardinal and ordinal exponentiation, and so by introducing a bit of notation to distinguish finite cardinals (as antichains) and finite ordinals (as chains) we can remove some of the ambiguity of the exponentiation notation. The paper's working title? The correct poset product.

I'd like to use some of my newfound freedom in making pronouncements about concepts I know I can't prove, but I don't know where to start. I will begin by re-affirming that the axiom of choice is obviously true, and $0^0$ is obviously 1. I wish I could weigh in on the continuum hypothesis, but I find I can't. It seems clear that we cannot take it as an axiom, but I simply don't know yet whether it is true or false; although I rather suspect it to be false.

And so I must be off to find some more mathematical statements to believe in the absence of proof. (I know this is ridiculous, but not nearly so ridiculous as the lengths some constructivists will go to.)

Currently listening:
Specular Highlights
By Plint
Release date: 3 January 1992

I really pity
Schroedinger's kitty

Paul McEvoy

One of my current side projects is an over-the-top article on a kind of anthropic computing problem on sending information back in time. In a nutshell, anthropic computing involves computing a random piece of data - if this meets our specifications, then good! Otherwise we destroy the universe (or perhaps just ourselves). Therefore an experimenter never observes any world-state in which the "wrong" random choice was chosen. In most formulations of this concept (see the Jargon File for example) the device is assumed to be "perfect" and so an infinite amount of information can be sent back in time. However this doesn't seem physically feasible since it seems it assumes the device has zero probability of error, whereas common failure modes (such as accidental deactivation or nuclear war) have probabilities relatively high compared to many computational problems, and therefore despite the canonical paper's opinion on the subject, it doesn't look like this kind of computing provides a loophole to compute NP-complete problems in polynomial time.

This is just a roundabout way of explaining why I happened to run across the cool webcomic/puzzle Meanwhile, which is an exploration of sorts into time travel, mindreading, and destroying the universe. Definitely worth a look (even if you didn't get that last paragraph).

Oh, and FYI the amount of information that can be sent back to the present is
\[\frac{1}{\log2}\left(\frac{\log\alpha}{\alpha-1}-1-\log\left(\frac{\log\alpha}{\alpha-1}\right)\right)\]
bits, where $\alpha$ is the ratio between the probability that the universe survives when our "gun" is fired, vs. the probability the universe survives if the gun is not fired.

Information given survival ratio $\alpha$

Recently Friedman and Landsberg's experimental results on certain scaling properties in the game chomp has been featured in Science News. (See another take on their work at bit-player.) It has been noted that the classic combinatorial game nim seems to have a "rougher", easier to analyze structure than the "smooth" structure of more complicated games like chomp. In a similar vein, an interesting tidbit is that the limit
\[
\lim_{n\to\infty}\frac{f(\lambda^nx,\lambda^ny)}{\lambda^n}
\]
exists for all integer choices of $\lambda$, $x$, and $y$ if $f$ is the function giving the value of two-rowed chomp positions; whereas if $f$ is the value of two nim heaps, the only values of $\lambda$ which work for all $x$, $y$ are the powers of two.

So, I thought it would be interesting to graph the difference between $f(\lambda x,\lambda y)$ and $\lambda f(x,y)$ for these different functions. There are at least two different ways of taking the difference between two nim-values: simply interpret them as integers and subtract one from the other, or use what is here the more natural operation of nim addition, conveniently provided directly by most CPU's and implemented in C-style languages as the operator "^" - that's right: binary XOR.

Of course, what would be really interesting is whether this kind of scaling behavior extends to more than two dimensions, but I figured that as long as I am getting pretty pictures for 2D scaling, I have a duty to share them.

First up is a look at two heap nim, compared using XOR. Click on the image to download a MPEG movie (warning: each is 3Mb for just a few seconds of video) showing the box with x and y up to 256, for $\lambda<512$. Here black is zero difference, and white is maximum difference in that frame. Notice the many scaling properties associated with the powers of two in both space and time. I believe I have seen this basic idea used in screensavers before, which is appropriate since it is extremely fast.

view - download

Next, comparison using simple subtraction. If the quanitities are equal, they are displayed as black, grayscale representing the absolute difference between them, up to white as the maximum difference.

view - download

Chomp in general exhibits much smoother behavior in terms of time and space. However, the qualitative behavior is quite different depending on whether $\lambda$ is even or odd, so I've separated the data into two movies - the first has all even frames up to 1024 (with unfortunate compression artifacts: the vertical stripes), the second has all odd ones. Notice how the image seems to retract smoothly towards (0,0). (Technical note: I prefer to use "absolute" coordinates for chomp, since these generalize readily to arbitrary poset games, whereas the relativized ones which are frequently encountered in the literature do not do so in any obvious way. Thus, each horizontal line in the top right of the images below actually represents only one distinct position.)

view - download

view - download

When comparing using subtraction for chomp, the scaling is so smooth we don't even need videos! There are only two qualitatively distinct frames depending on whether $\lambda$ is even or odd:

The fact of the matter is most of this is mathematically trivial, even if cool-looking. The next step is to take a look at scaling behaviors on different poset games and for dimensions 3 and more.

Well, Grigory Perelman officially turned down the Fields Medal today, becoming the first person to refuse it. If he refuses the Millennium Math Prize of $1 million it will firmly establish his reputation in the lore of mathematics for centuries to come. Geniuses are remembered, for sure, but geniuses with stories are remembered better.

On the other side, talented Canadian math student Robert Barrington Leigh's body was found yesterday in the N. Saskatchewan River in Edmonton. The last anyone had seen him, he was cycling to the Edmonton Folk Festival. I did not meet him, but he did spend some time this summer hanging out at the University of Calgary with Alex Fink and Richard Guy.

Somebody actually put together a computer that calculates primes — put together, that is, using the wireworld CA rule. It is complete with an LED-like display.
(By way of Good Math Bad Math)

Ah, good ol'd decimal notation. Every week or so, some student/crank/provocateur argues on sci.math that it can't be possible that 1=0.9999… However, the truth is that if we look at things a certain way, there are actually infinitely many representations of 1 (and every other real number) in base 10. We need to start with possible representations of zero. To this end, we quickly review that in base-$b$ notation we can write any real number as \[\sum_{n=-\infty}^m k_nb^n\] for $k_n\in\{0,1,…,b-1}$ and some finite $m\in{\mathbb Z}$. We would like to extend this for arbitrary base $x$ and set of digits $K$, and let $R(x,K)$ be those numbers representable by \[\sum_{n=-\infty}^\infty k_nx^n.\] In general, this series diverges unless $k_n=0$ for sufficiently large $n$. But assuming we are working in the standard metric, we can assign meaning to the divergent series at least as long as $k_n$ repeats for high $n$. This is because \[\sum_{n=-\infty}^\infty x^n=-1+\sum_{n=0}^\infty x^n+\sum_{n=0}^\infty x^{-n}=-1+\frac{1}{1-x}+\frac{1}{1-x^{-1}}=0.\] Therefore, any sequence of digits repeating infinitely to the left or right is a representation of zero; for example, the following are zero representations in base 10:

• …000000000.000000000
• …888888888.888888888…
• …999999999.999999999…
• …123123123.123123123…

Then the following are representations of 1:

• …000000001.000000000
• …888888889.888888888…
• …000000000.999999999…
• …123123124.123123123…

(As can be readily seen, $R(x,aK+b)=aR(x,K)$, so the set of digits can change rather dramatically without changing the set $R$ much.) Notice that due to the carrying rule in base 10, the zero representations of all nines becomes the 1 representation 0.999… In fact, using 9's complement we can get some different representations for -1 from these above without using a sign bit:

• …999999998.999999999
• …111111110.111111111…
• …999999999.000000000…
• …876876875.876876876…

But the fact that we have infinitely many representations of each number suggests that perhaps we don't really need all those digits in the first place. It turns out, for instance, that $R(3,\{0,1\})$ contains all the integers; the first few follow with the repeating sections in parentheses:

1. (0)1.(0)
2. (01)10.(01)
3. (0)10.(0)

(0)11.(0)

4. (011)100.(011)
5. (010)100.(010)
6. (010)101.(010)
7. (001)100.(001)
8. (0)100.(0)
9. (0)101.(0)
10. (001)110.(001)
11. (0)110.(0)
12. (0)111.(0)
13. (0111)1000.(0111)

Since it contains all the integers, it actually contains all the ternary rationals (rationals with power-of-3 denominators) so we can get arbitrarily close to any rational number (or 3-adic, for that matter). However, the set is not complete, nor even closed under addition or multiplication, since 1/2=0.11111… but 5/2 cannot be represented exactly.

Some additional interesting stuff comes in when one places additional restrictions on where various digits can be used, and these sets typically have interesting self-similarity. I'm still trying to figure out what problem (if any) I'm trying to solve here, just sharing something interesting.

This explains a lot. Be sure to check out the full illustration of the process. Of course, such a process would only be a boon to math texts, which are seemingly written by calculator manufacturers. Hence, one of my students today needed a calculator to find 3 - 1.

My information theory professor recently pointed out to us an article about a 2003 analysis of the number of "ideal" justices on the supreme court. The thinking being, ideal justices should rule basically independently. If two justices were to rule identically in every decision, there would only be 8 effective justices. So, I assume he just looked at a database of votes and calculated the entropy, and then claimed that there were 4.68 "ideal justices" on the court.

A more meaningful way to look at this number would be to say that on average, one would need to ask 4.68 yes-no questions per each ruling to discover exactly which way the justices voted. Since some justices vote very similarly, we don't always need a question per justice - one can ask "Did Scalia and Thomas both rule FOR?" and about half the time, the answer will be "yes", and the rest of the time, it's a good bet that they both ruled AGAINST. The researcher figured that 4.68 ideal justices was pretty good under the circumstances.

However, there's a bit of a problem with this. Suppose that the justices merely vote according to their ordering on a conservative-liberal axis. One could hardly consider this an optimal arrangement. And yet it turns out that if one assumes the justices rule according to such an ordering, and different rulings are equally likely, one finds the entropy is log 18 = 4.17 bits. This means it's possible that only half a bit of information in each ruling is not explained by a conservative-liberal ordering, which doesn't sound so "ideal" after all.

I was thinking that some dimensional analysis would be necessary to discover what is really going on here, but fortunately someone's already done it for me. It turns out the Breyer and O'Connor were the worst fits from a linear fit to the data. With O'Connor gone it seems the court may be even more one-dimensional, but it's probably too early to tell. Despite the second law of thermodynamics, there's really no reason to expect the entropy of Supreme Court rulings to be increasing with respect to time.

Every Thursday the department holds a general coloquium to hear speakers on various mathematical subjects. I started attending regularly when my advisor berated a seminar full of grad students for missing an apparently fascinating talk on Erdös. Last week Dr. Cunningham, my field theory professor, gave a lecture on some arcane conjecture in higher algebra. Although I have no idea about what the conjecture was about, nor did I follow the general arguments presented, I at least did learn about some new, interesting things. There's apparently an object called the "Adels" which contain the reals and all p-adics as subfields, so you can work in all the completions of the rationals at once. Cool. Anyway, I was still recovering from this talk, so I was happy enough that yesterday's would be given by a non-mathematician.

I didn't know who Stuart Kauffman was, but the crowd seemed pretty energetic before the lecture. Partly this was because there was going to be a meeting about the deanship afterwards, and so they had moved the free donut time up to before the meeting (though I learned this too late). A doctoral student gave a testimonial about how he converted from driving schoolbuses to doing graduate work after reading one of Kaufmann's books.

This is pretty understandable, given his talk. Kaufmann gave us a low-level overview of molecular biology with the stated goal of recruiting mathematicians to beat the Americans in deciphering gene regulation in humans.

Anyway, here's the deal. The activity of certain genes can act to promote or repress the action of other genes through several mechanisms. A significant amount of non-coding DNA is actually used for proteins to attach to in order to regulate expression. An example of this is a gene responsible for digesting lactose. There are 4 areas nearby which act as promoters. If all of these have the proper proteins attached, then the gene becomes active. However, there is also a repressor site. If a repressor is attached, then the gene is inactive regardless of what promoters are present. So, one can (perhaps over-simply) treat the expression of this gene as a boolean function of 5 inputs. The first 4 must be on, and the last off, for the gene to be active.

In general certain genes may both be regulated and regulate other genes. For example, one could imagine a system with two genes: A and B. Suppose A acts as a repressor for B, and likewise B acts as a repressor for A. Then if A is on, its activity will tend to shut off B, and vice-versa, so we should expect to see only two states: A on, B off; or A off, B on. In general these networks could be extremely complicated, involving periodic activity: A then B, then back to A again and so on. You know your computer is constructed of binary logic gates which act like the boolean functions in this model of gene activity. And just like your computer can get stuck in an endless loop of activity, forcing a reboot, barring external input cells must get caught in an endless loop of some sort. These states which cells must eventually end up in are called attractors of the dynamical system.

The canonical explanation of attractors is as follows. Suppose you let loose a marble on some kind of warped surface. The marble will roll around for awhile, but eventually end up in a valley or divot of some kind. These divots are called the attractors of the systems, because they "attract" the marble from less stable areas of the surface. As another example, there is a point in Glacier National Park in which mere inches determine whether a drop of water will end up in the Pacific Ocean, the Gulf of Mexico, or Hudson Bay. These bodies of water can be considered attractors of water in North America.

Now here's the point. When the embryo begins to divide, its cells are undifferentiated, but after some 50 divisions the full organism has developed into roughly 260 distinct cell types. Kaufmann's idea was maybe these different cell types represent different attractors for the genetic system. If so, he figured they would probably be relatively stable and simple, with low periodic behavior. This hypothesis would make the most sense if random boolean networks had these desireable traits, so he decided to test this using the means available to him: renting a computer to run the program he had typed up on punch cards. Of course, he wanted to test a random network so just prior to handing over his program to be run, he riffle-shuffled the lower half of the deck. The computer's operator was amazed.

It was actually something of a bet with himself, since if the periodicities were fairly long he could easily have gone broke considering the cost of computation at the time. Fortunately ten minutes later the computer spat out the answer, giving periodicities of lengths no greater than four.

So then we flash forward to today, when the mathematics behind such systems are somewhat better understood, and we have a wealth of biological knowledge including the human genome. The full regulatory patterns of cells are not well known, but we can see that the number of inputs per gene follows a power law distribution, and we can state given such a random distribution about how many attractors are expected. Using the model developed here and a couple parameters one comes up with an estimated 150 attractors, which is not too far off (in the engineering sense) from the number of distinct cell types, 260.

Of course, it also indicates that there is much work to do to discover all the regulatory mechanisms at play and the exact patterns of gene expression in every cell type, but Kauffman reminds us it is our responsibility to help Canada beat the United States to such discoveries.

Great talk. I leave and head to the department lounge. There are still three plain donuts left. I take one and head up to field theory.

Solve for $y$:
\[x+2y=6\]
Please post your answers and opinions on whether this should be a prerequisite for calculus.