A Generalization of Dirichlet’s Theorem

Sunday, July 13, 2008 in Uncategorized | Tags: | | No comments

The following is a well-known result:

Theorem: If a and m are integers, with (a,m)=1, then there are infinitely many primes congruent to a\pmod m.

It turns out that Dirichlet’s Theorem is actually a special case of Artin’s Reciprocity Law. So, we’ll discuss how this works.

Let L/K be an extension of number fields. (That is, L and K are finite extensions of \mathbb{Q}.) Let A and B be the rings of integers of K and L, respectively. (This means that A and B are the integral closures of \mathbb{Q} in K and L, respectively.) Now, let \mathfrak{p} be a nonzero prime ideal in A. Then \mathfrak{p}B=\prod_{i=1}^g \mathfrak{P}_i^{e_i} for some primes \mathfrak{P}_i of B and some positive integers e_i. If e_i>1, we say that \mathfrak{P}_i is ramified over \mathfrak{p}. We call e_i the ramification index. The primes \mathfrak{P}_i are said to lie above \mathfrak{p}.

Since A and B are Dedekind domains, \mathfrak{p} and \mathfrak{P}_i are maximal ideals. Hence k=A/\mathfrak{p} and \ell=B/\mathfrak{P}_i are finite fields, and \ell/k is a field extension. Let f_i=[\ell:k]. We call f_i the residue degree.

It is not too difficult to show that if n=[L:K], then n=\sum_{i=1}^g e_if_i. If L/K is a Galois extension, then e_i and f_i are independent of i (since the Galois group of L over K acts transitively on the \mathfrak{P}_i), so we can write n=efg.

Now, let’s define a few subgroups of Gal(L/K). We’ll assume from now on that L/K is a Galois extension. Furthermore, we fix a prime \mathfrak{p} of A, and some prime \mathfrak{P} of B lying above \mathfrak{p}. Now, define D_{\mathfrak{P}}=\{\sigma\in Gal(L/K):\sigma(\mathfrak{P})=\mathfrak{P}\}. We call D_{\mathfrak{P}} the decomposition group. We now have a homomorphism \phi : D_{\mathfrak{P}}\to Gal(\ell/k). To define \phi, we note that an element of D_{\mathfrak{P}} permutes cosets of B/\mathfrak{P} and thus gives the desired homomorphism. Furthermore, this homomorphism is surjective. The kernel T_{\mathfrak{P}} of \phi is called the inertia group. Hence D_{\mathfrak{P}}/T_{\mathfrak{P}}\cong Gal(\ell/k).

It is not hard to determine the sizes of D_{\mathfrak{P}} and T_{\mathfrak{P}} in terms of quantities we already understand: |D_{\mathfrak{P}}|=ef and |T_{\mathfrak{P}}|=e. In particular, if \mathfrak{p} is an unramified prime, then D_{\mathfrak{P}}\cong Gal(\ell/k).

That’s particularly nice, because Galois groups of extensions of finite fields are always cyclic, generated by the Frobenius automorphism. Thus in the unramified case, D_{\mathfrak{P}} is cyclic and generated by an automorphism \sigma satisfying the congruence \sigma(x)\cong x^{|k|} \pmod{\mathfrak{P}} for all x\in B. (We can extend \sigma to all of L by multiplicativity.) Furthermore, this element \sigma is unique. The common notation for \sigma is (\mathfrak{P},L/K).

If \mathfrak{P} and \mathfrak{Q} are two primes lying above \mathfrak{p}, then there is some element \sigma\in Gal(L/K) so that \sigma(\mathfrak{P})=\mathfrak{Q}. It is easy to verify that (\mathfrak{Q},L/K)=\sigma(\mathfrak{P},L/K)\sigma^{-1}. Therefore, if Gal(L/K) is abelian, then (\mathfrak{P}/L/K) depends only on \mathfrak{p}. In this case, we may write (\mathfrak{p},L/K) for this element.

Finally, we’re ready to state (part of) the Artin reciprocity theorem.

Let L/K be an abelian Galois extension of number fields, and let \sigma\in Gal(L/K) be fixed. Then there are infinitely many primes \mathfrak{p} of A that are unramified and so that \sigma=(\mathfrak{p},L/K).

(In fact, only finitely many primes ramify, since primes ramify if and only if they divide the discriminant, which can be easily verified. The other part of the statement is more interesting.)

Let’s look at one example. Take K=\mathbb{Q} and L=\mathbb{Q}(\zeta_n), where \zeta_n=e^{2\pi i/n}. Then Gal(L/K)\cong(\mathbb{Z}/n\mathbb{Z})^\times, where the isomorphism is as follows: if (m,n)=1, then there is an automorphism \sigma_m\in Gal(L/K) defined by \sigma_m(\zeta_n)=\zeta_n^m. Now, if (p,n)=1, then ((p),L/K)=\sigma_p. In particular, this case of the theorem is equivalent to Dirichlet’s Theorem on primes in arithmetic progressions.

It turns out that the theorem isn’t too much more general than this, since any abelian extension is contained in a cyclotomic extension (this is the Kronecker-Weber Theorem), and it’s not hard to see what happens to Frobenius elements when we pass to sub-extensions.

All this material can be found (with many more details included) in Serre’s Local Fields.

Projective and Injective Modules

Tuesday, June 17, 2008 in homological algebra, ring theory | No comments

Let’s fix a ring R. A module (assumed to be a left module, I suppose, but it doesn’t really matter as long as we’re consistent) M is said to be projective if the functor Hom(M,-) is exact. (That is, if 0\to A\to B\to C\to 0 is a short exact sequence of R-modules, then 0\to Hom(M,A)\to Hom(M,B)\to Hom(M,C)\to 0 is also exact.) Dually, M is said to be injective if the functor Hom(-,M) is exact.

There are various equivalent conditions for projectives and injectives. One particularly useful result is that projective modules are exactly the direct summands of free modules. Another one is that injective modules satisfy a certain extension property: A module J is injective if and only if for any map \phi:A\to J and any injective map f:A\to B, there exists a map (not necessarily unique) \theta:B\to J so that \phi=\theta\circ f.

Actually, we didn’t need to start with a ring R at all; it would make just as much sense to allow M to be an object in an arbitrary abelian category \mathcal{C}. We say that \mathcal{C} has enough projectives if for every object A of \mathcal{C}, there is an epimorphism (or, a surjective map, in the case of many interesting categories) P\to A, where P is projective. Dually, \mathcal{C} has enough injectives if for every object A of \mathcal{C}, there is a monomorphism (or, an injective map, in the case of many interesting categories) A\to J, where J is injective.

It is easy to see that the category of modules over a ring R has enough projectives: if A is an R-module, just take the free module on all the elements of A, and then quotient out by the submodule consisting of all relations in A. Hence A is isomorphic to a quotient of a free (and hence projective) module.

It is also true that the category of modules over a ring R has enough injectives, but this is a bit trickier to prove. To begin, we note that an arbitrary product of injective objects is injective. This follows from the isomorphism Hom(A,\prod_{i\in I} B_i)\cong\prod_{i\in I} Hom(A,B_i). We also note (although I’m not going to prove it here) that in the category of abelian groups (or \mathbb{Z}-modules), injective modules are the same as divisible modules (i.e. modules M so that the maps m\mapsto nm for n\neq 0 are all surjective).

Let’s first show that the category of abelian groups has enough injectives. The abelian group that plays the most important role here is \mathbb{Q}/\mathbb{Z}. Let A be any abelian group, and let I(A) be the product of copies of \mathbb{Q}/\mathbb{Z}, indexed by the set Hom(A,\mathbb{Q}/\mathbb{Z}). Then I(A) is injective, and there is a canonical map e_A:A\to I(A). We now check that e_A is actually an injective map. To do this, pick 0\neq a\in A. It is easy to find some nontrivial map a\mathbb{Z}\to\mathbb{Q}/\mathbb{Z}. By the extension property for injective modules, this map extends to a map on all of A. This is enough to show that e_A is an injective map.

Now let’s return to the category of modules over an arbitrary ring R. It can be shown that if J is an injective abelian group, then Hom(R,J) has the structure of an injective R-module. Now, let M be an arbitrary R-module. Then let I(M) be the product of copies of I_0=Hom(R,\mathbb{Q}/\mathbb{Z}), indexed by the set Hom_R(M,I_0). Then, just as before, there is a canonical injective map M\to I(M). This completes the proof that the category of R-modules has enough injectives.

Martingale Monkeys

Friday, February 8, 2008 in probability theory | 5 comments

A friend told me about an interesting problem that can be solved easily using martingales. I’ll start with the problem and solution, and then I’ll talk a bit about martingales in general. (That’s all I can do; I don’t know much about them.)

Problem: A monkey is sitting at a typewriter, typing a letter (A-Z) independently and with uniform distribution each minute. What is the expected amount of time that passes before ABRACADABRA is spelled?

Solution: Suppose that, before every keystroke is made, a new monkey enters and wagers $1 on the next keystroke being an A fairly (so that if the keystroke is indeed an A, then the payoff is $26). If the keystroke is an A, the monkey stays and wagers everything (in this case $26) on the next letter being B, and so on. If the monkey ever loses a wager, then it leaves. Now let’s analyze what happens when ABRACADABRA is finally spelled out. The monkey who kept making correct wagers all the way through won $ 26^{11}. But another monkey who got in on the second ABRA won $ 26^4, and a third monkey who got in on the final A got $26. Hence the total payoff is $ 26^{11}+26^4+26. But all the wagers are fair, and the house gets $1 on every turn from the new monkey, so the expected time before ABRACADABRA is spelled is 26^{11}+26^4+26.

I’m trying to figure out intuitively why the expected time should be longer than 26^{11}. Here’s my best understanding of it: if a lot of random letters are typed, then on average ABRACADABRA will be about as common as any other 11-letter string. However, they’ll be clumpier than some other strings, since we’ll see some instances of ABRACADABRACADABRA, which contain ABRACADABRA twice. But we can never clump, say, AAAAAAAAAAB more densely. Therefore, although the number of occurrences should be roughly equal in the limiting case, one can clump more easily than the other, so it should take more time to the first occurrence of ABRACADABRA than to the first occurrence of AAAAAAAAAAB.

In fact, we can make this clumping relationship even clearer with the following question: Suppose we have only two letters, A and B, and a monkey randomly types them. What is the probability that BA occurs before AA? The answer is 3/4 for a rather simple reason: if the sequence does not begin with AA, then there will be a B before the first occurrence of A, so BA will occur before AA unless the sequence starts with AA, which happens only 1/4 of the time.

Now on to martingales.  A martingale is a sequence of random variables X_1,X_2,X_3,\ldots so that the expectation E(X_{n+1}\mid X_1,\ldots,X_n)=X_n (and E(|X_n|)<\infty). In this case, the random variables X_n for each monkey are the payoffs after n wagers by that particular monkey. If the (n+1)^\text{th} wager is going to be made, then X_n=26^n, and X_{n+1} is going to be 26^{n+1} with probability 1/26 and 0 with probability 25/26. Thus E(X_{n+1}\mid X_1,\ldots,X_n)=26^{n+1}/26=26^n=X_n. Hence this chain is a martingale.

A Mathematician’s Take on Challah Braiding

Wednesday, September 12, 2007 in food, group theory | 1 comment

For many years, my mother has baked a challah nearly every Friday for Shabbat. Occasionally, however, she asks me to do some portion of the challah making, possibly including the braiding. For reasons we’ll see later, I don’t like her braiding algorithm. This post includes several algorithms, written in a way that someone who knows what a braid group is can understand. (I never had much success following those series of diagrams I sometimes see; I always wished someone would write out the braiding process in terms of generators of the braid group, so that’s what I’m going to do here after I give the preliminary definitions.)

Wikipedia’s page on braid groups has lots of interesting things, so I’ll only write a few essential points here, leaving the reader to explore Wikipedia at eir leisure. I’m finding it a bit tricky to give a good informal definition of braids, so I’ll just assume that my reader knows roughly what a braid is and skip to the formal definition.

The braid group on n strands is the group B_n=\langle a_1,\ldots,a_{n-1}\mid a_ia_{i+1}a_i=a_{i+1}a_ia_{i+1} \text{ for } 1\le i\le n-2, \ a_ia_j=a_ja_i \text{ for } |i-j|>1\rangle. In terms of actually playing with braid strands, a_i means interchanging strand i with strand i+1 by putting strand i over strand i+1. It is pretty simple to see that these generators do indeed induce all possible braids (although I haven’t yet said what a braid is), and that the relations ought to hold. Now, of course, a braid is an element of the braid group.

The braid groups become rather complicated quite quickly. While B_0=B_1=0 and B_2=\mathbb{Z}, already B_3 is nonabelian, and it’s isomorphic to the fundamental group of the complement of a trefoil knot in \mathbb{R}^3.

Note also that there is a natural homomorphism \pi:B_n\to S_n that tells us where the strand that started in the i^\text{th} position ends up.

Okay, now it’s time for some challah braiding algorithms. My mother’s usual challah has four strands on the bottom and three on the top. The algorithm for the top braid is pretty natural: (a_1a_2^{-1})^n, where n is decided by the length of the dough ropes.

I’m more concerned about the element of B_4 used for the bottom braid. She uses (a_1a_2^{-1}a_3^{-1}a_2)^n.  If n=1, we have \pi(a_1a_2^{-1}a_3^{-1}a_2)=(142)(3) (in cycle notation). This is already bad news to me: one step of the algorithm produces a single fixed point! I think one step of the algorithm ought to give an n-cycle (here a 4-cycle) or else a pure braid (i.e. a braid in the kernel of \pi). But it gets worse: the strand that starts in position 3 has no undercrossings. So when we’re done, it sits on top of every other strand.

It turns out not to be so bad because the three-strand braid sits on top of the four-strand braid, so the central portion of the four-strand braid is not visible in the finished bread. But aesthetically (and mathematically), this feels like a serious flaw to me.

Fortunately, I found an alternate algorithm for four-strand braiding that lacks these flaws: (a_2a_1a_3^{-1})^n. If n=1, \pi(a_2a_1a_3^{-1})=(1243), which is nice. Furthermore, every strand has both overcrossings and undercrossings. So this is my new preferred braid.

Sometimes, however, it is preferable to braid with six strands. There was an article in the newspaper that explained how to do it, but I was unable to follow it. Fortunately, I found a YouTube video that shows someone doing it (possibly the same way; I can’t tell). I was able to transcribe this method in terms of generators of the braid group. However, I’m not quite sure where it is supposed to end, so my braid may be slightly different from the one shown in the video. The braid is the video is (e^{-1}d^{-1}c^{-1}b^{-1}a^{-1}(bcdeabd^{-1}c^{-1}b^{-1}a^{-1}e^{-1}d^{-1})^n, except that it might stop somewhere in the middle of the (\cdot)^n. I don’t really want to calculate \pi of this braid (computations like this have never been that easy for me), but I would guess that it is a 6-cycle if it stops at an appropriate moment. (Also, it’s not as complicated as the formula would make it seem, since there’s a lot of stuff like moving the strand on the right all the way over to the left, and it takes a lot of generators to express that, even though it’s not complicated when you’re actually braiding dough.)

The Eilenberg Swindle

Tuesday, August 28, 2007 in K-theory, ring theory | No comments

Recall from the last post that if R is a commutative ring, we define K_0(R) to be the Grothendieck group of the isomorphism classes of finitely generated projective R-modules. It is natural to ask what happens if we replace finitely generated projective modules with countably generated projective modules. Let us write \mathfrak{K}_0(R) for this group. It turns out that understanding \mathfrak{K}_0(R) is extremely easy.

Theorem: For any commutative ring R, \mathfrak{K}_0(R)=0.

Proof: We have to show that if A, B, C, and D are countably generated projective R-modules, there is some countably generated projective R-module E so that A\oplus D\oplus E\cong B\oplus C\oplus E. Define E=\bigoplus_{i=1}^\infty (A\oplus B\oplus C\oplus D). Hence \mathfrak{K}_0(R)=0.

A similar construction shows up in the theory of group rings. Here’s an exercise from T.Y. Lam’s Exercises in Classical Ring Theory:

Exercise 8.16: Let G and H be any two groups. Show that there is some ring R so that R[G]\cong R[H]. (Here R[G] is the ring of finite R-linear combinations of elements of G, and multiplication is defined by the group multiplication of G.)

Solution: Let K=(G\times H)\times(G\times H)\times\cdots, and set R=\mathbb{Z}[K]. Then R[G]\cong R[H].

Lam makes the comment that, although consideration of the group rings \mathbb{Z}[G] and K[G] are very useful for determining properties of G (for instance, the modules over these rings are the objects of study in group cohomology and representation theory, respectively), the group ring R[G] for an arbitrary ring R might not give us much information about G.

There’s an interesting article I found on more general Eilenberg swindles, but the authors don’t define progenerators, so I’ll include that here.

Let R be a ring and M a right R-module. Define M^\ast=Hom_R(M,R) and S=Hom_R(M,M). Then M and M^\ast are S-R and R-S bimodules, respectively. Furthermore, we can define multiplications M^\ast M\subseteq R by m^\ast m=m^\ast(m) and MM\ast\subseteq S by mm^\ast(m')=m(m^\ast m'). We say that M is a progenerator if MM^\ast=S and M^\ast M=R.

New objects from old using equivalence classes of pairs

Tuesday, August 14, 2007 in K-theory, ring theory | No comments

In many places in mathematics, we see some variant of the following simple construction. The first time we see it is in constructing the integers from the natural numbers:

Consider pairs (a,b) of elements of \mathbb{N} (which includes zero for our purposes, but it doesn’t really matter this time). We form equivalence classes out of these pairs by saying that (a,b)\sim(c,d) if a+d=b+c. We can create a group structure on these pairs by setting (a,b)+(c,d)=(a+c,b+d). The resulting group is isomorphic to \mathbb{Z}. So that’s how to construct the integers from the natural numbers.

We see a similar construction when we discuss localizations of rings. Let R be a commutative ring and S a multiplicative subset containing 1. (If R is noncommutative, you can still localize provided that S is an Ore set, but I don’t feel like going there now.) We now consider pairs (r,s)\in R\times S under the equivalence relation (r_1,s_1)\sim(r_2,s_2) if there is some t\in S so that tr_1s_2=tr_2s_1. The set of equivalence classes has the structure of a ring, called the localization of R at S, and denoted by R_S. This construction is generally seen with S=R\setminus\mathfrak{p}, where \mathfrak{p} is a prime ideal of R. The resulting ring is then local (meaning that it has a unique maximal ideal, namely \mathfrak{p}R_S. (We generally write R_{\mathfrak{p}} rather than R_S in this situation.) Anyway, this construction is really useful because localizations at prime ideals are frequently principal ideal domains, and we know all sorts of interesting theorems about finitely generated modules over principal ideal domains. And then we can use some Hasse principle-type result to transfer our results back to the original ring.

Notice that I allowed the multiplicative set of localization to contain zero. However, in this case, the localization becomes the trivial ring (or not a ring, if you require that 0\neq 1 in your definition of a ring, as many people do). More generally, allowing zero divisors in the multiplicative set causes various elements in R to become zero in the localization.

A similar construction shows up in K-theory. Suppose A is any commutative semigroup. We consider pairs (a,b)\in A\times A under the equivalence relation (a,b)\sim(c,d) if there is some e\in A so that a+d+e=b+c+e. (This is necessary since we do not assume that A satisfies the cancellation property.) The resulting equivalence classes form a group called the Grothendieck group of A and denoted by K_0(A).

The Grothendieck group satisfies the following universal property. Let \phi be the map sending a\in A to (a+b,b) for any b\in A. (This is easily seen to be well-defined.) Now let G be any abelian group and \psi:A\to G any semigroup homomorphism. Then there is a (unique) map \theta:K_0(A)\to G so that \theta\phi=\psi.

Grothendieck groups can be very helpful for studying rings. Let R be a commutative ring, and let A denote the semigroup of isomorphism classes of projective R modules (under the operation of direct sum). Then K_0(A) (or K_0(R), as people often write) is an important object of study. If R is a field, for instance, then K_0(R)\cong\mathbb{Z}. However, if R is the ring of integers of a number field K, then K_0(R)\cong\mathbb{Z}\oplus C(K), where C(K) is the ideal class group.

Perhaps more interesting is Swan’s Theorem, which relates vector bundles over a compact topological space to the projective modules over its ring of continuous functions: they have isomorphic Grothendieck groups. But that’s probably the subject of another post, especially if I can manage to understand my notes from Max Karoubi’s lecture series in Edmonton.

Tschirnhaus Transformations

Monday, August 13, 2007 in Galois theory | No comments

This is based on a talk by Zinovy Reichstein from the PIMS Algebra Summer School in Edmonton.

The motivation comes from looking at ways to simplify polynomials. For example, if we start with a quadratic equation x^2+ax+b, we can remove the linear term by setting y=x+\frac{a}{2}; our equation then becomes y^2+b'.

We can do something similar with any degree polynomial. Consider the polynomial x^n+a_1x^{n-1}+a_2x^{n-2}+\cdots+a_n. We may make the substitution y=x+\frac{a_1}{n} to remove the (n-1)-degree term.

We can also make the coefficients of the linear and constant terms equal with the substitution z=\frac{b_n}{b_{n-1}}y (where the b’s are the coefficients of the polynomial expressed in terms of y).

Enough for motivation. Suppose f(x)=x^n+a_1x^{n-1}+\cdots+a_n is a polynomial, and let K=\mathbb{C}(a_1,\ldots,a_n). (So, in particular, a_1,\ldots,a_n form a transcendence basis for K over \mathbb{C}.) Let L=K[x]/(f(x)). A Tschirnhaus transformation is an element y\in L so that L=K(y).

Applying a Tschirnhaus transformation to a polynomial of degree n gives us another polynomial of degree n with different coefficients. They also allow us to simplify polynomial expressions in various senses. We will use the following two criteria of simplification:

1) A simplification involves making as many coefficients as possible 0.

2) A simplification involves making the transcendence degree of \mathbb{C}(b_1,\ldots,b_n) over \mathbb{C} as small as possible. (For a polynomial of degree n, we will write d(n) for this number.)

Suppose n=5. Hermite showed that it is possible to make b_1=b_3=0 and b_4=b_5. Therefore d(5)\le 2. Klein showed that d(5) is in fact equal to 2.

Now suppose n=6. Joubert showed that again we can make b_1=b_3=0 and b_5=b_6. Therefore d(6)\le 3.

It is unknown whether we can make b_1=b_3=0 when n=7. However, it is known that we cannot do so if n is of the form n=3^r+3^s for r>s\ge 0 or n=3^r for r\ge 0. It is also known (Buhler and Reichstein) that d(n)\ge\left\lfloor\frac{n}{2}\right\rfloor.

Dynamical Systems in Number Theory and Linear Algebra

Thursday, July 5, 2007 in algebraic number theory, dynamical systems, linear algebra | 1 comment

I have been reading Joseph Silverman’s new book on arithmetic dynamics lately. There’s a lot of really fascinating stuff in there, including a large number of potential research problems that are currently way beyond me, but I’ll continue thinking about them! Most interesting so far is the Uniform Boundedness Conjecture:

Let d\ge 2, N\ge 1, and D\ge 1 be integers. Then there exists a constant C=C(d,N,D) such that for any number field K with [ K : \mathbb{Q} ] \le D and any morphism \phi:\mathbb{P}^N(K)\to\mathbb{P}^N(K) of degree d, the number of preperiodic points of \phi in \mathbb{P}^N(K) is at most C.

Not much is known about this conjectures; even the case d=2, N=1, and D=1 is open. It’s even open if we restrict to morphisms of the form \phi_c(z)=z^2+c. Bjorn Poonen has shown, however, that these maps have no rational periodic points of exact period 4 or 5; it is conjectured that they have no rational periodic points of exact period greater than 3.

However, there is a positive result of the above type that doesn’t depend that much on some of the above quantities:

Let K be a number field and \phi:\mathbb{P}^1\to\mathbb{P}^1 be a rational map over K. Let \mathfrak{p} and \mathfrak{q} be prime ideals of \mathfrak{o}_K so that \phi has good reduction at \mathfrak{p} and \mathfrak{q} (meaning that when we reduce \phi modulo \mathfrak{p} and \mathfrak{q}, we end up with a map \tilde\phi of the same degree as \phi) and whose residue characteristics are distinct. Then the period n of any periodic point of \phi in \mathbb{P}^1(K) satisfies n\le (N\mathfrak{p}^2-1)(N\mathfrak{q}^2-1), where N denotes the (absolute) norm.

(See, for instance, my algebraic number theory notes for definitions of some of these terms.)

Anyway, that wasn’t really the point of this post, as you may have guessed from the title. I meant to talk about theorems that pretend not to be related to dynamical systems but actually are. First we need to discuss height functions a bit; there’s a lot more about them in Silverman’s book and in my elliptic curve notes.

We let K be a number field and M_K the set of standard absolute values on K (These are the absolute values on K whose restriction to \mathbb{Q} is either the standard absolute value or one of the p-adic absolute values.) We write n_v=[K_v:\mathbb{Q}_v] (where F_v denotes the completion of F with respect to the absolute value v). Suppose P\in\mathbb{P}^N(K); we can then write P=[x_0,\ldots,x_N] for some x_0,\ldots,x_N\in K. We then define the height of P with respect to K to be H_K(P)=\prod_{v\in M_K} \max\{|x_0|_v,\ldots,|x_N|_v\}^{n_v}. One can check that this is well-defined, and that if L/K is a finite extension of number fields and P\in K, then H_L(P)=H_K(P)^{[L:K]}. Hence it is possible to define the absolute height of P by H(P)=H_K(P)^{1/[K:\mathbb{Q}]}.

One of the key facts about heights is the following: If B and D are constants, then \{P\in\mathbb{P}^N(\overline{\mathbb{Q}}):H(P)\le B \text{ and } [\mathbb{Q}(P):\mathbb{Q}]\le D\} is finite. A corollary is the following well-known result of Kronecker:

Let \alpha\in\overline{\mathbb{Q}} be nonzero. Then H(\alpha)=1 if and only if \alpha is a root of unity.

Proof: If \alpha is a root of unity, then H(\alpha)=1 is clear. Now suppose that H(\alpha)=1. For any \beta and n, we have H(\beta^n)=H(\beta)^n, so H(\alpha^n)=H(\alpha)^n=1, so \{\alpha,\alpha^2,\alpha^3,\ldots\} is a set of bounded height and is therefore finite. Therefore there are integers i>j>0 such that \alpha^i=\alpha^j, so \alpha is a root of unity.

And now for linear algebra. Sheldon Axler has a well-known book on linear algebra without determinants. He therefore uses dynamical systems to show the following familiar result:

Theorem: Every operator on a finite-dimensional nonzero complex vector space has an eigenvalue.

Proof: Let V be such a vector space of dimension n. Let T be an operator on V, and let v\in V be nonzero. Then \{v,Tv,T^2v,\ldots,T^nv\} cannot be a linearly independent set. Hence there exist a_0,\ldots,a_n\in\mathbb{C}, not all zero, so that a_0v+a_1Tv+\cdots+a_nT^nv=0. Suppose m is maximal with respect to a_m\neq 0. Then a_0v+a_1Tv+\cdots+a_mT^mv=0. Since we’re working over \mathbb{C}, the polynomial a_0+a_1z+\cdots+a_mz^m factors as a_m(z-\lambda_1)\cdots(z-\lambda_m). We then have 0=a_0v+a_1Tv+\cdots+a_mT^mv=a_m(T-\lambda_1I)\cdots(T-\lambda_mI)v. Hence some T-\lambda_jI is not injective. This \lambda_j is an eigenvalue for T.

Arthur-Merlin Games

Thursday, May 31, 2007 in computational complexity | No comments

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 | No comments

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.