onsdag 27 januari 2016

The distribution of the binomial coefficients modulo p (a layman's review)

Once, I was pretty decent in mathematics. Using an almanac as temporal verification, it wasn't even that many years ago.

You get unfamiliar with your tools if you don't use them. I'm sure there's fortune cookie wisdom in there somewhere. But avoiding this excellent excuse to write Haiku, I'll just state that if someone asks me about functional analysis, measure theory or reading some paper in French today, I'm sure to nod nostalgically. I might hold up a conversation about the subjects when I'm drunk, but I have no real working skill in graduate level mathematics anymore.

Anyway, Magic. This is still somehow related to the history of Magic. Very old school stuff though. Like before Alpha playtest cards old school. Like Richard Garfield January 1991 old school.
There have been a bunch of articles out there about most aspects of the good doctor's life and the early days of Magic. How the company got founded, how he proposed to his wife, his struggles with getting funding for RoboRally and all that. But I haven't really seen anyone looking up the 'PhD' part of Pheddalgrif. So tonight, with a six-pack of beers in hand, we'll take a look at Richard Garfield's PhD thesis. If Frank Karsten gets to write about math at ChannelFireball, it's not weird for us to read a thesis here. Buckle up mofos!
So, The distribution of the binomial coefficients modulo p. Hardcore stuff. I think I might understand the title, which is always a very good sign. Binomial coefficients are the family of integers that e.g. shows up when you want to pick some objects from a collection of said objects. Like if you want to pick three players for a deck-check in a tournament with 40 players, in how many ways can you do that? That's a binomial coefficient. Or if I want to calculate the odds of getting this particular FTK hand from my grossly unfair Power Monolith deck:
Assuming that I really want the #MtgForLife-land and want the Juzam Sol Ring rather than another Mox or similar, but that I don't care which of my four-of Basalt Monoliths, Power Artifacts or Fireballs I get, what are the odds for drawing this exact First Turn Kill on the play? Well, the number of possible hands I can draw from a 60 card deck, assuming each card is unique, is commonly pronounced "60 choose 7", and calculated as 60!/(7!(60-7)!) = 386 million give or take a few hundred thousand. As I have four-ofs of three of the cards I want in my opener, I get to improve the odds for this particular hand to about one in six million.

Modulo p then. Slightly simplified, the modulo operation typically finds the remainder after division of one integer by another. So for example 16 modulo 12 asks for the remainder of 16/12, i.e. 4. If two numbers give the same remainder when divided by a given number, they are said to be congruent. So 16 is congruent with 4 (and 28, 40, 52, etc) modulo 12.

There are many cases when modular arithmetic comes up in everyday life. The hour of the day is modulo 24. If it's 20:00 and you wait six hours, it's not 26:00 o'clock but rather 02:00. The months of the year is modulo 12; after December we get back to January again. So let's say that we would pick five different months since the start of the current calendar in England in 1752 (when they decided to start the year with January over there). That's 3169 months ago. What are the odds that all the five months we picked were October? If we pick five random numbers from 1 to 3169, each one of them need to be congruent with 10 modulo 12 to represent the tenth month of the year, and we can pick the months in 3169 choose 5 different ways. So far so easy.
From the title, the thesis appears to cover how to assign a probability to each measurable subset of binomial coefficients modulo some prime number. So we're not looking at modulo 12 here for sure, as 12=2*2*3. Lets say that we look at modulo 7 instead, which we could think of as weekdays instead of months. If we pick a few of the almost 100 000 days since 1752, how many of them will be Wednesdays? Not that hard to find out, as it's a 1 in 7 chance for each day. But instead, lets look at how many different ways we can pick the days. These are the binomial coefficients. Let's call the number of days k. If we want to pick k=5 days, we can do it in about 6.96*10^22 different ways. If we want to pick k=30 we can do it in 1.27*10^117 ways, and for say k=25 000 we can do it in 7.05*10^23966 different ways. For a fairly large number of days to chose from, and picking many days, the number of possibilities gets unwieldy large quickly. But if we look at the number of possibilities in in terms of residue classes instead - that is how many are congruent with 1, 2, 3, 4, 5, 6 or 0 modulo 7 - we still get a lot of information. How many of the binomial coefficients will end up in each residue class? Can we say something about this distribution for different values of k? This is a simplified way of looking at it, but I think that these kind of distributions is what the paper is about.


Hm. Thinking about it, this could be the least user friendly topic even remotely related to the history of Magic one could write about. If I were writing on a commercial site, odds are that my editor would reject this with a vengeance. Well, I'm in too deep now. And lucky me, I have no editor. Here's a picture of Land Leeches:
For those of you still here, lets move from the title to the abstract to get a better idea of what we're reading.
Ouch. The more times I read this the more I realize that it would take me months to properly understand the context. In particular the sentence "The proof uses the fact that a certain mapping of p-ary digit strings to polynomials modulo (x^(p-1)-1) is a homomorphism" is beyond me. I understand the words per say, but I have no opinion on the sentence they form. Is everyone OK with taking the easy route skipping the proof and calculations, and just move on to the results? Both of you are? Thanks Frank Karsten and Martin Lindström.

So, the end result is used "to study how the the values of the binomial coefficients sit in the quadratic residues modulo p." What's a quadratic residue then? Lets look it up in my Introduction to modern algebra:
An integer a is called a quadratic residue modulo m if it is congruent to a square modulo m. In the example, they note that
  • 1² ≡ 1 mod 5
  • 2² ≡ 4 mod 5
  • 3² ≡ 4 mod 5
  • 4² ≡ 1 mod 5
So 1 and 4 are quadratic residues of 5, while 2 and 3 are quadratic nonresidues.

Lets take a quick step back and look at just how large numbers we're working with when talking about binomial coefficients. This is not related to the results in the thesis, but to get a better idea of what we would be dealing with without the modulo operation. In the introduction of the thesis, Garfield has a brief discussion where he uses n=10^9 as an example. That's about the size of the population of India in 1998. So say that you want to pick 1% of that population to do some survey on their living standards or similar. In how many ways could we pick out this one percent? I can't really write that binomial coefficient here, as it has well over 24 million digits. We would have to use all the characters of eight Bibles to write that number down. And if we go a little further, say picking 10% of the population rather than 1%, the binomial coefficient gets too big for most scientific calculators to handle. And we're still looking at, in a sense, small numbers here; 1 billion is a number we can relate to and picking 10% of that isn't that big a chunk.

So how do the values of binomial coefficients for different values of k sit in the residue groups modulo p? And why is it interesting? Well, paraphrasing Black Knight, math is its own purpose. It's the poetry of logical ideas. As Bertrand Russel so eloquently put it, "Mathematics, rightly viewed, possesses not only truth, but supreme beauty -- a beauty cold and austere, like that of sculpture, without appeal to any part of our weaker nature, without the gorgeous trappings of painting or music, yet sublimely pure, and capable of a stern perfection such as only the greatest art can show. The true spirit of delight, the exaltation, the sense of being more than Man, which is the touchstone of the highest excellence, is to be found in mathematics as surely as poetry."

I can't say I understand the proof. But dismissing its potential beauty because of my inept insight in the field would be ignorant. It's like someone calling from the Louvre to describe Mona Lisa on the phone and the respondent dismissing the painting as they wont get get a proper understanding of its nuances ("It's some chick with a weird smile and dark hair, with slightly tilted landscape in the background for flavor").
Something like this?
Many of the frequently used tools in modern mathematics started out as purely academic topics, years or centuries later finding a "real world use". Fields like conic sections, group theory, complex analysis and fractal geometry were all mainly studied for academic curiosity and beauty once upon a time. Later they proved instrumental in forming the modern world as we know it. Quadratic residues was originally an abstract mathematical concept from a branch of number theory known as modular arithmetic. But today it seems like there are quite a few tangible real-world applications for it. According to Wikipedia its applications "are ranging from acoustical engineering to cryptography and the factoring of large numbers." Pretty sweet. A diamond is nice to look at by itself, but once you realize you can also use it to build drills that cut through stone like butter or knives sharp enough for eye surgery it gets more value.
So now we have a basic idea of what Garfield was doing while carving out the ideas that eventually became Magic. Maybe you learned something. Maybe a slightly bigger picture of the man who became the world's arguably best game designer will help us better appreciate the craftsmanship. Or maybe I lost you seven paragraphs ago. Regardless, I'm glad to see that you made it all the way down here. And I got to go full nerd and write about math on a Magic blog. Achievement unlocked. Might write about dicks and explosions next time to compensate.

9 kommentarer:

  1. Just great .... you really combine two of my most loved subjects in here. That is just awesome!


  2. Thanks a lot for the positive comments! Didn't expect for this one to be that well received to be honest. Clearly underestimated the audience ;)

  3. Amazing article...I understood barely any of it; though I'm a MTG guy, I'm far from a quant in every respect of the word (I'm a licensed psychotherapist).

    Thank you for trying to explain the matrix to an agent.

  4. Is it just me or did the blog somehow get even better?

    /Martin Lindström

  5. Not just you, Martin. :)

    I miss the math sometimes, and this brings back the memories. I was never much into number theory, or even algebra in general, but this post was a very interesting read nevertheless.

  6. Epic!

    Martin Berlin

  7. I liked the Land Leeches.