The Unapologetic Mathematician

Polynomials, take 2

As I said before, if we take the free commutative monoid on $n$ generators, then build the semigroup ring from that, the result is the ring of polynomials in $n$ variables. I hinted at a noncommutative analogue, which today I’ll construct from the other side.

Instead of starting with a set of $n$ generators and getting a monoid, let’s start by building the free abelian group $\mathbb{Z}^n$. This consists of ordered $n$-tuples of integers, and we add them component by component. We can pick out the $n$ generators $x_k=(0,...,0,1,0,...,0)$, where the $1$ shows up in slot $k$. Then every element can be written $a_1x_1+a_2x_2+...+a_nx_n$, where the $a_k$ is entry $k$ in the $n$-tuple form of the element.

So how do we build the tensor product $\mathbb{Z}^n\otimes\mathbb{Z}^n$? First we take all pairs
$(a_1x_1+...+a_nx_n,b_1x_1+...+b_nx_n)$
and use them to generate a free abelian group. Then we impose the linearity relations $(a+a',b)=(a,b)+(a',b)$ and $(a,b+b')=(a,b)+(a,b')$. What does that mean here? Well for one thing we can apply it to the collection of pairs:
$(a_1x_1+...+a_nx_n,b_1x_1+...+b_nx_n)=$
$a_1(x_1,b_1x_1+...+b_nx_n)+...+a_n(x_n,b_1x_1+...+b_nx_n)=$
$a_1b_1(x_1,x_1)+...+a_1b_n(x_1,x_n)+a_2b_1(x_2,x_1)+...a_nb_n(x_n,x_n)$
So we could just as well write the tensor product as the group generated by $x_i\otimes x_j=(x_i,x_j)$.

This same argument goes through as we tensor in more and more copies of $\mathbb{Z}^n$. The tensor power $(\mathbb{Z}^n)^{\otimes d}$ is the free abelian group generated by the elements $x_{i_1}\otimes...\otimes x_{i_d}$, where each index runs from ${}0$ to $n$.

Now we take all of these tensor powers and throw them together. We get formal linear combinations
$\sum\limits_{d=1}^\infty\sum\limits_{i_1,...,i_d=1}^n a_{i_1,...,i_d}x_{i_1}\otimes...\otimes x_{i_d}$
where all but finitely many of the “coefficients” $a_{i_1,...,i_d}$ are zero. These look an awful lot like polynomials, don’t they? In fact, if we only had a commutative property that $x_i\otimes x_j=x_j\otimes x_i$ then these would be exactly (isomorphic to) the polynomials we came up with last time.

To be explicit about the universal properties, any function from the $n$ generators to the underlying abelian group of a ring $R$ with unit has an unique extension to a linear function from $\mathbb{Z}^n$ to $R$. Then this has a unique extension to a ring homomorphism from $R(\mathbb{Z}^n)$ to $R$. From the other side, there is a unique extension of the original function to a monoid homomorphism from the free monoid $M_n$ to the underlying monoid of $R$. Then this has a unique extension to a ring homomorphism from $\mathbb{Z}[M_n]$ to $R$. Since both $R(\mathbb{Z}^n)$ and $\mathbb{Z}[M_n]$ satisfy this same universal property they must be isomorphic. We commonly write this universal ring as $\mathbb{Z}\{x_1,...,x_n\}$, and call it the ring of noncommutative polynomials in $n$ variables.

April 20, 2007 Posted by | Ring theory | 1 Comment

The Carnival is back

This time it’s over at Modulo Errors. Enjoy.

The Free Ring on an Abelian Group

Last week I talked about how to make a ring out of a semigroup by adding an additive structure. Now I want to do the other side. Starting with an abelian group we’ll build a ring by adding a “free” multiplication.

The main tools will be what I was saying about tensor products and abelian groups. Specifically, we have isomorphisms
$(A\otimes B)\otimes C\cong A\otimes(B\otimes C)$
$\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes\left(\bigoplus\limits_{j\in\mathcal{J}}B_j\right)\cong\bigoplus\limits_{(i,j)\in\mathcal{I}\times\mathcal{J}}\left(A_i\otimes B_j\right)$

The first of these lets us unambiguously talk about “the” tensor product of any finite list of abelian groups. The particular case we’re interested in here is when all of them are the same group. We define the $n$th “tensor power” $A^{\otimes n}=A\otimes...\otimes A$ with $n$ copies of $A$ tensored together on the right. In the case $n=0$ we define $A^{\otimes0}=\mathbb{Z}$. Then we see that for all natural numbers $m$ and $n$ we have $A^{\otimes m}\otimes A^{\otimes n}\cong A^{\otimes(m+n)}$.

Now we can take all these tensor powers of $A$ indexed by $\mathbb{N}$ and form the direct sum
$R(A)=\bigoplus\limits_{n\in\mathbb{N}}A^{\otimes n}$
I claim that this abelian group carries the structure of a ring. Remember that a multiplication on an abelian group $R$ that distributes over addition is equivalent to a linear function $R\otimes R\rightarrow R$. So I want to exhibit such a function for $R(A)$.

This is where the second isomorphism comes in. We consider the tensor product
$\left(\bigoplus\limits_{m\in\mathbb{N}}A^{\otimes m}\right)\otimes\left(\bigoplus\limits_{n\in\mathbb{N}}A^{\otimes n}\right)$
which is isomorphic to
$\bigoplus\limits_{(m,n)\in\mathbb{N}\times\mathbb{N}}\left(A^{\otimes m}\otimes A^{\otimes n}\right)$
which is isomorphic to
$\bigoplus\limits_{(m,n)\in\mathbb{N}\times\mathbb{N}}A^{\otimes(m+n)}$
Let’s change how we index these. Here we’re direct summing up over all pairs of natural numbers, but the abelian group we’re summing only depends on $m+n$. So let’s first index by the sum of the natural numbers.
$\bigoplus\limits_{k\in\mathbb{N}}\bigoplus\limits_{m+n=k}A^{\otimes k}$

Okay, now we’ve got a single infinite direct sum over $k$, and each term is direct sum of $k+1$ copies of $A^{\otimes k}$. For each of these finite direct sums we can just add up the elements of $A^{\otimes k}$ from each copy. This gives a linear function $(k+1)A^{\otimes k}\rightarrow A^{\otimes k}$. We can apply the right one to each direct summand to get a linear function
$R(A)\otimes R(A)\cong\bigoplus\limits_{k\in\mathbb{N}}\bigoplus\limits_{m+n=k}A^{\otimes k}\rightarrow\bigoplus\limits_{k\in\mathbb{N}}A^{\otimes k}=R(A)$
This is our ring structure.

As usual, there’s a universal property floating around. Any linear function $f$ from an abelian group $A$ to a ring $R$ extends uniquely to a ring homomorphism $\bar{f}$ from $R(A)$ to $R$. Just define $\bar{f}(a_1\otimes...\otimes a_n)=f(a_1)...f(a_n)$ and extend linearly to find how $\bar{f}$ acts on a given direct summand of $R(A)$. This justifies calling $R(A)$ the free ring on the abelian group $A$.

April 19, 2007 Posted by | Ring theory | 1 Comment

Coloring knots (again)

A few weeks ago I mentioned the knot coloring problem, and left you to play with it. Now I’m going to say what’s going on.

First let’s remember what it means to color a knot. We take a knot and draw a knot diagram to represent it. Then we color each arc of the diagram — from the undercrossing at one end to the undercrossing at the other — either red, green, or blue. At every crossing three arcs come together, and we require that either all three get the same color or all three get different colors. We can always just give every arc the same color, but we’re interested in when we can use all three colors.

Of course you’re now screaming (or you should be) that we had to choose a diagram for the knot, so how do we know that the answer doesn’t depend on which choice we made? Luckily we have a way to tell if two knot diagrams represent the same knot: Reidemeister moves! So how do colorings behave when we do a Reidemeister move?

Let’s go through them one at a time. The first move looks like this:

Of course, it doesn’t have to be red. There’s a similar diagram for green and blue. So, if we have a strand colored red we can twist it, coloring both arcs red. On the other hand, if we have a twisted strand, both arcs have to be the same color. Otherwise the crossing wouldn’t be colored right. We can then untwist the strand.

Here’s the second move:

On the left we have two strands of different colors. After performing the move we can give the new arc the third color. If the strands were both the same color we could give the new arc that same color again. On the other side, any coloring of the right side of the move will give the same color to the top and bottom ends of each strand. We can then undo the move and still have a valid coloring.

Finally the third move:

Any coloring of the ends of the three strands that can be extended to a valid coloring of the middle on the left side can be extended to a valid coloring on the right side, and vice versa. For example, both sides require that the strand running through the middle get the same color at both ends.

Now the first and third moves don’t change the number of colors that appear. The second one seems like it might, though. If we have a coloring on the right using all three colors, maybe the left only has two? If we’re dealing with a knot (rather than a link with more than one loop) then eventually the red and green strands will have to meet up. When they do, it’s at a crossing, and then we’ll need to use blue. So if any diagram of a knot has a coloring with all three colors then all of them do. “Three-colorability” is a property of the knot itself, not just of a diagram.

Actually, we can do even better. Pick a diagram on one side of a Reidemeister move and color the ends of each strand. Either this coloring can be extended to a valid coloring of the interior of the diagram or it can’t, and if it can there’s only one way to do it. The extendible colorings of the ends of one side of a move are exactly the same as the extendible colorings of the other side.

The upshot is that we can ask about how many colorings a knot has, or even a multi-loop link. Some of them may not use all three colors, but every diagram of the same link has the same number of valid colorings. Every knot has at least three (monochromatic) colorings, so a knot is three-colorable (using all three colors) if and only if the number of valid colorings of any diagram is bigger than 3.

April 18, 2007 Posted by | Knot theory | 1 Comment

More on tensor products and direct sums

We’ve defined the tensor product and the direct sum of two abelian groups. It turns out they interact very nicely.

One thing we need is another fact about the tensor product of abelian groups. If we take three abelian groups $A$, $B$, and $C$, we can form the tensor product $A\otimes B$, and then use that to make $(A\otimes B)\otimes C$. On the other hand, we could have started with $B\otimes C$ and then built $A\otimes(B\otimes C)$. If we look at the construction we used to show that tensor products actually exist we see that these two groups are not the same. However, they are isomorphic.

To see this, let’s make a bilinear function from $(A\otimes B)\times C$ to $A\otimes(B\otimes C)$. By our construction, any element of $A\otimes B$ can be represented as a sum $\sum\limits_i a_i\otimes b_i$, so linearity says we just need to consider elements of the form $a\otimes b$. Define $f(a\otimes b,c)=a\otimes(b\otimes c)$. This induces a unique linear function given by $\bar{f}((a\otimes b)\otimes c)=a\otimes(b\otimes c)$ and extending to sums of such elements. Similarly we get a linear function $\bar{f}^{-1}(a\otimes(b\otimes c))=(a\otimes b)\otimes c)$, so we have an isomorphism of abelian groups. We can thus (somewhat) unambiguously talk about “the” tensor product $A\otimes B\otimes C$.

Now let’s take a collection of abelian groups $A_i$ with $i$ running over an index set $\mathcal{I}$, and let $B$ be any other abelian group. We want to consider the tensor product
$\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes B$

Since the direct sum is a direct product of groups, it comes with projections $\pi_k:\bigoplus_i A_i\rightarrow A_k$. Since the free product is in general a subgroup of the direct sum (a proper subgroup when the index set is infinite), we also have injections $\iota_k:A_k\rightarrow\bigoplus_i A_i$ coming from the free product. We can use these to build homomorphisms
$\iota_i\otimes1_B:A_i\otimes B\rightarrow\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes B$
applying $\iota_i$ to $A_i$ and the identity to $B$. By the universal property of direct sums (the one it gets from free products of groups) this gives us a homomorphism
$\alpha:\bigoplus\limits_{i\in\mathcal{I}}(A_i\otimes B)\rightarrow\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes B$

On the other hand, for each $k$ we have a bilinear function sending $(a,b)$ in $\left(\bigoplus_i A_i\right)\times B$ to $\pi_k(a)\otimes b$ in $A_k\otimes B$. By the universal properties of tensor products this gives a linear function $\left(\bigoplus_i A_i\right)\otimes B\rightarrow A_k\otimes B$. The universal property of direct sums (the one it gets from direct products of groups) gives us a linear function
$\beta:\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes B\rightarrow\bigoplus\limits_{i\in\mathcal{I}}(A_i\otimes B)$

Now there’s a lot of juggling of functions and injections and projections here that I really don’t think is very illuminating. The upshot is that $\alpha$ and $\beta$ are inverses of each other, giving us an isomorphism of the two abelian groups. There’s nothing really special about the left side of the tensor product either. A similar result holds if the direct sum is the right tensorand. We can even put them together to get the really nice isomorphism:

$\left(\bigoplus\limits_{i\in\mathcal{I}}A_i\right)\otimes\left(\bigoplus\limits_{j\in\mathcal{J}}B_j\right)\cong\bigoplus\limits_{(i,j)\in\mathcal{I}\times\mathcal{J}}(A_i\otimes B_j)$

Neat!

April 17, 2007

Polynomials

Now we come to a really nice example of a semigroup ring. Start with the free commutative monoid on $n$ generators. This is just the product of $n$ copies of the natural numbers: $\mathbb{N}^n$. Now let’s build the semigroup ring $\mathbb{Z}[\mathbb{N}^n]$ on this monoid.

First off, an element of the monoid is an ordered $n$-tuple of natural numbers $(e_1,e_2,...,e_n)$. Let’s write it in the following, more suggestive notation: $x_1^{e_1}x_2^{e_2}...x_n^{e_n}$. We multiply such “monomials” just by adding up the corresponding exponents, as we know from the composition rule for the monoid. Now we build the semigroup ring by taking formal linear combinations of these monomials. A generic element looks like

$\sum\limits_{(e_1,e_2,...,e_n)\in\mathbb{N}^n}c_{(e_1,e_2,...,e_n)}x_1^{e_1}x_2^{e_2}...x_n^{e_n}$

where the $c_{(e_1,e_2,...,e_n)}$ are integers, and all but finitely many of them are zero.

Assuming everyone’s taken high school algebra, we’ve seen these before. They’re just polynomials in $n$ variables with integer coefficients! The addition and multiplication rules are just what we know from high school algebra. The only difference is here we specifically don’t think of $x_i$ as a “placeholder” for a number, but as an actual element of our ring.

But we can still use it as a placeholder. Let’s consider any other commutative ring $R$ with unit and pick $n$ elements of $R$. Call them $r_1$, $r_2$, and so on up to $r_n$. Since $R$ is a commutative monoid under multiplication there is a unique homomorphism of monoids from $\mathbb{N}^n$ to $R$ sending $x_i$ to $r_i$. That’s just what it means for $\mathbb{N}^n$ to be a free commutative monoid. Now there’s a unique homomorphism of rings from $\mathbb{Z}[\mathbb{N}^n]$ to $R$ sending $x_i$ to $r_i$, because $\mathbb{Z}[\mathbb{N}^n]$ is the semigroup ring of $\mathbb{N}^n$.

The upshot is that $\mathbb{Z}[\mathbb{N}^n]$ is the free commutative ring with unit on $n$ generators. Because of this, we’ll usually omit the intermediate step of constructing $\mathbb{N}^n$ and just write this ring as $\mathbb{Z}[x_1,x_2,...,x_n]$.

There are similar constructions to this one that I’ll leave you to ponder on your own. What if we just constructed the free monoid on $n$ generators (not commutative)? What about the free semigroup? What sort of rings do we get, and what universal properties do they satisfy?

April 16, 2007 Posted by | Ring theory | 6 Comments

Character Tables and the Atlas of Lie Groups

I’ve posted my notes from Zuckerman’s second lecture. Again, there’s a lot to unpack here, so it goes after the jump.

April 14, 2007 Posted by | Atlas of Lie Groups | 2 Comments

Cardinal numbers

I’ve said a bunch about natural numbers, but I seem to have ignored what we’re most used to doing with them: counting things! The reason is that we actually don’t use natural numbers to count, we use something called cardinal numbers.

So let’s go back and think about sets and functions. In fact, for the moment let’s just think about finite sets. It seems pretty straightforward to say there are three elements in the set $\{a,b,c\}$, and that there are also three elements in the set $\{x,y,z\}$. Step back for a moment, though, and consider why there are the same number of elements in these two sets. Try to do it without counting the numbers first. I’ll wait.

The essential thing that says there’s something the same about these two sets is that there is a bijection between them. For example, I could define a function $f$ by $f(a)=x$, $f(b)=z$, and $f(c)=y$. Every element of $\{x,y,z\}$ is hit by exactly one element of $\{a,b,c\}$, so this is a bijection. Of course, it’s not the only one, but we’ll leave that alone for now.

So now let’s move back to all (possibly infinte) sets and define a relation. Say that sets $X$ and $Y$ are “in bijection” — and write $X\leftrightarrow Y$ — if there is some bijection $f:X\rightarrow Y$. This is an equivalence relation! Any set is in bijection with itself, using the identity function. If $X$ is in bijection with $Y$ then we can use the inverse function to see that $Y\leftrightarrow X$. Finally, if $f:X\rightarrow Y$ and $g:Y\rightarrow Z$ are bijections, then $g\circ f:X\rightarrow Z$ is a bijection.

Any time we have an equivalence relation we can split things up into equivalence classes. Now I define a cardinal number to be an bijection class of sets — every set in the class is in bijection with every other, and with none outside the class.

So what does this have to do with natural numbers? Well, let’s focus in on finite sets again. There’s only one empty set $\{\}$, so let’s call its cardinal number ${}0$. Now given any finite set $X$ with cardinal number — bijection class — $c$, there’s something not in $X$. Pick any such something, call it $x$, and look at the set $X\cup\{x\}$. If I took any other set $Y$ in bijection with $X$ and anything $y$ not in $Y$ then there is a bijection between $x\cup\{x\}$ and $Y\cup\{y\}$. Just apply the bijection from $X$ to $Y$ on those elements from $X$, and send $x$ to $y$. This shows that the bijection class — the cardinal number — doesn’t depend on what choices we made along the way. Since it’s well-defined we can call it the successor $S(c)$.

We look at the set of all bijection classes of finite sets. We’ve got an identified element ${}0$, and a successor function. In fact, this satisfies the universal property for natural numbers. The set of cardinal numbers of finite sets is (isomorphic to) the set of natural numbers!

And that’s how we count things.

April 13, 2007 Posted by | Fundamentals, Numbers | 3 Comments

Semigroup rings

Today I’ll give another great way to get rings: from semigroups.

Start with a semigroup $S$. If it helps, think of a finite semigroup or a finitely-generated one, but this construction doesn’t much care. Now take one copy of the integers $\mathbb{Z}_s$ for each element $s$ of $S$ and direct sum them all together. There are two ways to think of an element of the resulting abelian group, as a function $f:S\rightarrow\mathbb{Z}$ that sends all but finitely many elements of $S$ to zero, or as a “formal finite sum” $c_1e_{s_1}+c_2e_{s_2}+...+c_ne_{s_n}$ where each $c_i$ is an integer and $e_s$ is “$1$” from the copy of $\mathbb{Z}$ corresponding to $s$.

I’ll try to talk in terms of both pictures since some people find the one easier to understand and some the other. We can go back and forth by taking a valid function and using its nonzero values as the coefficients of a formal sum: $f=\sum\limits_{s\in S}f(s)e_s$. This sum is finite because most of the values of $f$ are zero. On the other hand, we can use the coefficients of a formal sum to define a valid function.

So we’ve got an abelian group here, but we want a ring. We use the semigroup multiplication to define the ring multiplication. In the formal sum picture, we define $e_{s_1}e_{s_2}=e_{s_1s_2}$, and extend to sums the only way we can to make the multiplication satisfy the distributive law. In the function picture we define $\left[fg\right](s)=\sum\limits_{xy=s}f(x)g(y)$ where we take the sum over all pairs $(x,y)$ of elements of $S$ whose product is $s$. This takes the product of all nonzero components of $f$ and $g$ and collects the resulting terms whose indices multiply to the same element of the semigroup.

The ring we get is called the “semigroup ring” of $S$, written $\mathbb{Z}[S]$. There are a number of easy variations on the same theme. If $S$ is actually a monoid we sometimes say “monoid ring”, and note that the ring has a unit given by the identity of the monoid. If $S$ is a group we usually say “group ring”. If in any of these cases we start with a commutative semigroup (monoid, group) we get a commutative ring.

So here’s the really important thing about semigroup rings. If we take any ring $R$ and forget its additive structure we’re left with a semigroup. If we take any semigroup homomorphism from $S$ to this “underlying semigroup” of $R$ we can uniquely extend it to a ring homomorphism from $\mathbb{Z}[S]$ to $R$. This is just like what we saw for free groups, and it’s just as important.

As a side note, I want to mention something about the multiplication in group rings. Since $xy=s$ only if $y=x^{-1}s$ we can rewrite the product formula in the function case $\left[fg\right](s)=\sum\limits_{x\in S}f(x)g(x^{-1}s)$. This way of multiplying two functions on a group is called “convolution”, and it shows up all over the place.

April 12, 2007 Posted by | Ring theory | 9 Comments

I’m going to Faro

The organizers want me to give my 30-minute talk on bracket extensions. Nice way to go out, if it turns out I’m going out of the tower.