News You Can Bruise

See, the first talk, by Brian Hayes, covered the amazing history leading up to the publication of Markov's seminal paper. He's now turned his talk into an article in American Scientist. The first few pages of that article are a basic introduction to Markov chains; the history starts on page four. Basically, Markov was a cranky old man who liked picking fights.

Markov’s pugnacity extended beyond mathematics to politics and public life. When the Russian church excommunicated Leo Tolstoy, Markov asked that he be expelled also. (The request was granted.) In 1902, the leftist writer Maxim Gorky was elected to the Academy, but the election was vetoed by Tsar Nicholas II. In protest, Markov announced that he would refuse all future honors from the tsar... In 1913, when the tsar called for celebrations of 300 years of Romanov rule, Markov responded by organizing a symposium commemorating a different anniversary: the publication of Ars Conjectandi 200 years before.

As acts of political protest go, the well-timed symposium is pretty great. At that symposium Markov revealed the Markov chain, which he'd invented as a way to smack down the dumb theological arguments of rival mathematician Pavel Nekrasov. His paper wasn't called "Markov Chains: Future Basis for Art and Scientific Discovery, Named After Me, A. A. Markov." It was called called "An Example of Statistical Investigation of the Text 'Eugene Onegin' Concerning the Connection of Samples in Chains".

Markov had manually gone through the first 20,000 characters of Pushkin's "Eugene Onegin", looking at every pair of letters, writing down whether the letters were both vowels, both consonants, vowel-consonant, or consonant-vowel. Then he'd modelled the transitions between those four states with a Markov chain. The result disproved an assumption about the law of large numbers, an assumption crucial to Nekrasov's mathematical argument for free will. There's something about this mindset that always gets me--inventing the sledgehammer so you can use it to kill a fly.

The other two talks were a lot more technical. I was mostly able to follow them, but I don't think I got much out of them. Here's a summary of all three talks from someone else who was there. But I strongly recommend Hayes's article to anyone who reads this weblog.

The 313-degree Shaa compass had no zero coordinate, but began instead with one, the odd number left over after factoring the prime number.

I guess that's true. Maybe the Shaa could help Bill Gates factor those large prime numbers.

Apart from prime number weirdness (and species essentialism), this is a really fun book. There was a lot of boring clan politics at the beginning, but it turns out that was setup for an examination of how totally dysfunctional is a society based on clan politics. I often suspect these authors of being secretly enamored of the petty intrigues of clan politics, but it's clearly not the case here.

Insta-update: Before posting this entry I asked Adi about the compass thing. His response:

I don't understand that statement at all. Do the Shaa simply relabel their compass? Instead of using labels of 0,1,...,360, their compass uses the labels 1,2,..,313? (i.e., their compass has a full range of motion, but simply a different scale)

If this is in fact true, then I wonder what additive identity the Shaa have chosen. From the statement you wrote, it seems as though the additive identity is 1... which can't of course be consistent with 1 working as a remainder after division by prime numbers. And the "odd number left over after factoring the prime number" does not make sense to me... Why one would use the multiplicative identity [ie. 1] as an additive identity is beyond me.

Unfortunately, by this point in the book the Shaa are all dead, so we can't ask them, and it's clear that a bad compass is the least element of their legacy of incompetence.

And forty-one, a prime number, was a significant number for the Shaa, who loved primes and multiples of primes.

--Walter Jon Williams, The Praxis

Number forty-seven said to number three
"Hey, we're both prime!"

1/2 < |_mod(|_y/17_| 2^{-17|_x_|-mod(|_y_|,17)},2)_|

#!/usr/bin/python
from dmath import getcontext, Decimal, floor
getcontext().prec = 550

# Tweak these to get a larger or smaller-scale graph.
X_STEP = Decimal("1")
Y_STEP = X_STEP

# Don't mess with these.
X_MIN = Decimal(0)
X_MAX = X_MIN + 105
Y_MIN = Decimal("96093937991895888497167296212785275471500433" +
                "96601293066515055192717028023952664246896428" +
                "42174350718121267153782770623355993237280874" +
                "14430789132596394133772348785773574982392662" +
                "97155171737169951652328905382216124032388558" +
                "66184013235585136048828693337902491454229288" +
                "66708109618449609170518345406782773155170540" +
                "53816273809676025656250169814820834187831638" +
                "49115590225610003652351370343874461848378737" +
                "23819822484986346503315941005497470059313833" +
                "92264972494617515457283667023697454610146559" +
                "97933798537483143786841806593422227898388722" +
                "980000748404719")
Y_MAX = Y_MIN + 16

fl = floor
# Performance speedup
FLOORS_DIV_17 = {}
def fl17(n):
  "A memoized floor(n/17) function."
  f = FLOORS_DIV_17.get(n)
  if not f:
    f = fl(n/17) 
    FLOORS_DIV_17[n] = f
  return f    

half = Decimal(".5")
def f(x,y):
  return half < fl((((fl17(y))*(2**((-17*fl(x)) - (fl(y) % 17)))) % 2))

y = Y_MIN
while y <= Y_MAX:
  x = X_MAX
  while x >= X_MIN:
    if f(x,y):
      print "*",
    else:
      print " ",
    x = x - X_STEP
  print
  y = y + Y_STEP

It uses the dmath library so I can call the floor function on an arbitrary-precision decimal. Anyway, you can run that program yourself or you can see my premade ASCII graph of the function If you graph the function over other ranges you can see other patterns, but none so striking.

Lots more interesting empirical math in this paper.

A lesser known fact is that pre-Socratic philosophy is freaking hilarious. Both phases yield funny results (Everything is made of water! No, earth and water! No, air!). They sound ridiculous now but "everything is made of air" was actually a pretty sophisticated model; it supposed that you got other materials by compressing air to greater or lesser densities. Occasionally the book gives out kudos: "[Anaximenes's] view that the stars give no warmth because of their great distance contradicts Anaximander's theory that the stars are closer to earth than the moon and sun are. It is also true." I believe this author was the first to discover that Anaximenes and Anaximander were actually different people.

I just got to the chapter on Pythagoras, who is portrayed as an L. Ron Hubbard/Paul Bunyan/Chuck Norris figure of folklore and Internet meme. Here are some useful Pythagoras Facts (p79):

His followers were devoted to his sayings, which they collected, memorized, and passed down. He was a charismatic figure who became the subject of legends: he killed a poisionous snake by biting it; a river hailed him by name; he made predictions; he appeared simultaneously in two different places; he had a golden thigh. The people of Croton addressed him as Hyperborean Apollo. Pythagoreans identified three types of rational beings: gods, humans, and beings like Pythagoras.

1. You are pretentious (Super Bowls, titles of movie sequels, dates carved into buildings, names of people).
2. You are desperate for visually distinct ways of representing the counting numbers (outlines, page numbering for prefaces).
3. You want to obfuscate a number (movie copyright dates).

Actually, Pete Peterson II makes me add another item, since he's not named that for pretentious reasons. Lousy heuristic! In a sinister twist of fate, it's now become as complicated as Roman numbers themselves!

Incidentally, you can do base conversion in Python by passing in the base as the second argument to the int() function. Pretty neat, huh?

Well, I thought, I'll encode the numbers x,y as a product of powers of primes 2^x*3^y, just like you would to encode a formula into Gödel numbering. Then I'll have one number that, by the Fundamental Theorem of Arithmetic, uniquely represents some list of numbers. On the other side I'll "just" decode the list from that number.

Then I figured out that the real answer was to put the numbers in a list and pass in the list.

Good tabloid-science headline: Origin of Enigmatic Galactic-center Filaments Revealed!

Accuracy not guaranteed.

We also talked about making Nethack trendier by adding an Atkins diet conduct. To keep this conduct you could eat all the animal corpses you wanted, but not vegetable-based foods, or potions of booze or fruit juice. Alternatively, there might be a vegetable timeout.

Also check out newCROP, which has an enormous list of food crops, as well as the disturbing list of Famine Foods.

Incidentally, I am trying to write a science fiction story about the revision theory of truth, a story I think you would love. Too bad I am not very good at writing stories.

Anyway, I've long maintained that there should be a mathematical cop show about Alfred Tarski and Alonzo Church, called "Tarski and Church". My proposal has been met by stony silence by major television networks, or at least by the large statues outside their office buildings, which I took to be the receptionists. However, I'm nothing if not a team player, and I'm willing to sweeten the deal with a lighthearted sitcom, entitled "Everybody Loves Riemann". Who'll take a chance on the pilot?

Now, Mark Wooding of Cambridgeshire has written Quine, a C program capable of transforming any C program into a quine. This makes me happy because I don't think I've ever written any quines, except in made-up languages in which such things were trivial. Now there's a quine transformation program and I can scoff and say "Oh, quine is a solved problem."

(Found via the humbling sweetcode, which for every "Well, that's out of the way now" generates ten "Man, I wish I {had thought of that, could have written} that"s.)

def probablyPrime(n):
    if n > 1 and n <= 7:
        return 1
    else:
        return 0

"Math documents, for example, should run through a math compiler that not only verified that the documents can run but that they are true..."

Nuh-uh-uh.