An Idelic Life

Arthur-Merlin Games

Thursday, May 31, 2007 in computational complexity | Leave a comment

We consider the graph isomorphism problem: Given two graphs $G_1$ and $G_2$ , are they isomorphic? If you solve this problem and find that the two graphs are indeed isomorphic, it is very easy for you to convince me of this fact: We assume that $|G_1|=|G_2|=n$ (since if they have different numbers of vertices, they clearly cannot be isomorphic). For me to believe you, you can simply find an element $\pi\in S_n$ that induces an isomorphism of the two graphs.

What if they aren’t isomorphic? You could try to find an invariant that differs. But that’s a rather ad hoc technique, and maybe you aren’t able to find one, but you still know that the two graphs are nonisomorphic (somehow). We can play a game that will help you convince me that the two graphs are nonisomorphic. I create a list of (say) 50 numbers $a_1,a_2,\ldots,a_{50}$ , with each $a_i=1,2$ . Then I randomly choose permutations $\pi_i\in S_n$ and construct the graphs $\pi_i G_{a_i}$ and give you this list. Now you have to tell me whether each $a_i$ is equal to 1 or 2. If the the two graphs are isomorphic, you’ll only get the graphs right half the time (since you’re just guessing in this case), so it’s very unlikely that you’ll always get it right. However, if they’re nonisomorphic, then you can (somehow) figure out which graphs on my list are isomorphic to $G_1$ and which to $G_2$ and get them all right.

The class of problems (such as the graph nonisomorphism problem) that can be solved with this sort of interaction is called the Arthur Merlin (or AM) complexity class.

Lexicographic Codes, Nim, and Simple Groups

Wednesday, May 30, 2007 in coding theory, combinatorial game theory, group theory | Leave a comment

We first consider integral lexicographic codes (henceforth lexicodes). We enumerate all (infinite to the left) sequences of nonnegative integers that differ in at least $m$ positions from any previous sequence. The first few of these (with $m=3$ ) are the following:

…00000

…00111

…00222

…00333

…00444

…00555

…00666

and so forth. But after all those are done, we can continue with:

…01012

…01103

…01230

…01321

…01456

…01547

…01674

…01765

and so forth. After we have finished with all these, we can continue with

…02023

and so forth.

I think one of the nicest possible properties a code can have is linearity (i.e. it forms a vector space over some field). However, it might not appear that this lexicographic code is linear. First of all, there is no obvious field of scalars (since $\mathbb{N}$ is certainly not a field). Furthermore, the addition and multiplication don’t work out correctly. If we add …00222 and …01012, we get …01234, but this is not in our lexicode. Multiplication doesn’t work either: if we multiply …01012 by 2, we get …02024, which is also not in our lexicode.

However, this lexicode is linear! It forms a vector space over the field of (finite) nimbers! So lexicographic codes are mysteriously connected to combinatorial games.

So that’s one kind of lexicode. We can also consider binary lexicodes. In this case, we will restrict ourselves to 24-bit binary lexicodes with $m=8$ . The first few sequences are

000000000000000000000000

000000000000000011111111

000000000000111100001111

000000000000111111110000

000000000011001100110011

and so forth. The list will ultimately contain 4096 sequences. There are 759 of them that contain exactly 8 1’s. These 759 have a very interesting property: for any five-element subset of $\{1,2,3,\ldots,24\}$ , there is exactly one (of the 759) sequences that has 1’s in exactly those five positions. In other words, these sequences form the Steiner system $S(5,8,24)$ .

Now for the simple groups. Well, the Mathieu group $M_{24}$ is the automorphism group of $S(5,8,24)$ . $M_{24}$ is one of the 26 sporadic finite simple groups.

Surface areas of spheres

Monday, May 14, 2007 in calculus, geometry | Leave a comment

We compute the “surface areas” of $n$ -dimensional spheres. Of course, we know that $\int_{-\infty}^\infty e^{-t^2}\; dt=\sqrt{\pi}$ . Raising this to the $d^\text{th}$ power gives $\int_{\mathbb{R}^d} e^{-|x|^2}\; dx=\pi^{d/2}$ . Making the substitution $dx=r^{d-1}\; dr\; d\omega$ gives $\int_{S^{d-1}} d\omega\int_0^\infty e^{-r^2}r^{d-1}\; dr=|S^{d-1}|\int_0^\infty e^{-u}u^{d/2-1}\;\frac{du}{2}=\frac{|S^{d-1}|}{2}\Gamma\left(\frac{d}{2}\right)$ . Hence $|S^{d-1}|=\frac{2\pi^{d/2}}{\Gamma(d/2)}$ .

Taking the limit as $d\to\infty$ yields a surprising consequence: the surface areas of spheres of radius 1 tend to 0 as the dimension increases!

Nim and direct limits of finite fields

Thursday, April 12, 2007 in combinatorial game theory, finite fields | 2 comments

We can consider nim as a countably infinite-dimensional vector space over $\mathbb{F}_2$ , the field with two elements. To do this, we write out a nim heap in binary, and then we make the digits into an element of $V=\bigoplus_{n=0}^\infty \mathbb{F}_2$ by putting the least significant bit in the first entry, the second-least significant bit in the second entry, and so forth. In this case, the operation of nim sum is simply vector space addition on $V$ .

But we can do even better: we can turn this vector space into a field of characteristic 2. We define multiplication as follows (I will use $\otimes$ for nim product): $1\otimes n=n$ for any $n$ , $2^{2^n}\otimes 2^{2^n}=3\times 2^{2^n-1}$ , and a nim product of distinct Fermat 2-powers (numbers of the form $2^{2^n}$ ) is their ordinary product. Then we can use distributivity to compute any nim product. For example, $19\otimes 14=233$ . (Note that, unlike nim addition, nim multiplication does not preserve parity.)

In fact, we can say even more. Suppose we limit our game of nim game to piles of size at most $2^{2^n}-1$ . Then nim addition and multiplication are closed in this subclass of games. Therefore we have $\mathbb{F}_{2^{2^n}}$ canonically(?) embedded in our nim field. (I am not so sure about the canonical part, because I don’t know if we could define multiplication in some other natural way that would still give us a field.) This tells us that $\varinjlim_{n\to\infty} \mathbb{F}_{2^{2^n}}$ is isomorphic to the field of finite nimbers.

So here’s a question for myself or my (possibly nonexistent) audience: what does nim multiplication tell us about actually playing games? Anything? Nothing at all? I would like to believe that it has some implication as far as playing games goes, but at the moment, I don’t see anything.

If we extend nim to ordinal piles, we can do something similar and end up with an algebraically closed Field (Conwayese for something that would be a field except that its elements form a proper class). Ordinal nim piles make sense as far as game play goes because the ordinals are (very conveniently!) well-ordered, so games cannot last forever.

Elliptic and modular functions

Monday, March 19, 2007 in elliptic curves, modular forms | Leave a comment

Suppose that $\omega_1,\omega_2\in\mathbb{C}$ with $\Im\omega_1/\omega_2>0$ . Then consider the lattice $\Lambda=\mathbb{Z}\omega_1+\mathbb{Z}\omega_2$ . We can form a torus as $\mathbb{C}/\Lambda$ . We call meromorphic functions on $\mathbb{C}/\Lambda$ elliptic functions with respect to $\Lambda$ .

Now suppose that $f(u;\omega_1,\omega_2)$ is an elliptic function with the additional property that we can almost scale the arguments: $f(\lambda u;\lambda\omega_1,\lambda_2)=\lambda^{-k} f(u;\omega_1,\omega_2)$ for $\lambda\in\mathbb{C}\setminus\{0\}$ . Then in particular we can scale $\omega_2$ to 1: $f(u;\omega_1,\omega_2)=\omega_2^{-k}f\left(\frac{u}{\omega_2};\frac{\omega_1}{\omega_2}\right)$ , where now $f(v;z)$ is defined on $\mathbb{C}\times\mathbb{H}$ . If we fix $v$ and consider $f$ as a function on $\mathbb{H}$ , then we have $f(v;\gamma z)=(cz+d)^k f(v;z)$ for any $\gamma\in SL_2(\mathbb{Z})$ . (If $\gamma=\begin{pmatrix} a & b \\ c & d\end{pmatrix}\in SL_2(\mathbb{Z})$ , then we define $\gamma z=\frac{az+b}{cz+d}$ .)

We call a function $f:\mathbb{H}\to\mathbb{C}$ satisfying $f(\gamma z)=(cz+d)^k f(z)$ for all $\gamma\in SL_2(\mathbb{Z})$ a modular function.

The point of all that is the elliptic functions can be naturally turned into modular functions.

The Poisson Summation Formula

Sunday, March 18, 2007 in Fourier analysis | Leave a comment

Theorem: Let $f:\mathbb{R}\to\mathbb{C}$ be a function of rapid decay. Then $\sum_{n=-\infty}^\infty f(n)=\sum_{n=-\infty}^\infty \hat{f}(n)$ , where $\hat{f}(\xi)=\int_{-\infty}^\infty f(x)e^{-2\pi i\xi x}\; dx$ is the Fourier transform of $f$ .

Proof: Write $g(x)=\sum_{n=-\infty}^\infty f(x+n)$ . The Fourier coefficients of $g$ are $a_n=\int_0^1\sum_{m=-\infty}^\infty f(x+m)e^{-2\pi inx}\; dx=\int_{-\infty}^\infty f(x)e^{-2\pi inx}\; dx=\hat{f}(n)$ . Therefore the Fourier expansion of $g$ is $g(x)=\sum_{n=-\infty}^\infty \hat{f}(n)e^{2\pi inx}$ . Substituting $x=0$ gives $\sum_{n=-\infty}^\infty f(n)=\sum_{n=-\infty}^\infty \hat{f}(n)$ , as desired.