Posted by: Steven Sam | December 21, 2009

Groups of size less than 60

My girlfriend is taking an abstract algebra course this year, and they had the following “longterm project” to think about for the term: Show that every group of size less than 60 is either Abelian or not simple. If we assume Burnside’s theorem that a group of order p^aq^b (p and q are primes) is solvable, this gives every case except for 30 and 42. (A proof of Burnside’s theorem can be found here on p.19, Exercise 6 of one my old solution manuals, but you’ll need Serre’s book to see what the cited theorems are). But since I had never done this exercise, I wanted to write a post about how to do this using only techniques from a first course in algebra (i.e., Sylow theorems).

Let’s recall what the Sylow theorems say. First, let G be a finite group of order n. Let p be a prime and write n = p^km where p does not divide m. A maximal subgroup of G whose order is a power of p is a Sylow p-subgroup. Let n_p be the number of Sylow p-subgroups. Then we have the following theorem.

Theorem. 1. The size of a Sylow p-subgroup is p^k.
2. All Sylow p-subgroups are conjugate to one another via inner automorphisms of G.
3. The index of the normalizer of any Sylow p-subgroup is n_p. In particular, n_p divides m and is congruent to 1 modulo p.

The third statement is usually enough. If we can show that n_p = 1 for some p, then the corresponding Sylow p-subgroup (assuming p divides n) must be normal since any conjugate of it must have the same size. There were three general facts that have relatively short proofs that take care of most of the cases. Then the rest was a (quick) case-by-case analysis. If the reader knows of another quick general fact that makes the problem more efficient, leave a comment!
Read More…

Posted by: yanzhang | December 17, 2009

M-3: Coins and Low-Knowledge Proofs

This puzzle was presented by Tanya Khovanova at a casual combinatorial meeting, apparently from some Russian olympiad for middle/high-schoolers. I really like this type of problem since I haven’t seen it before (also, it starts in a way that makes most people think “oh I’ve seen this before…” only to be wrong). Before I present the problem, we will look at a “baby version” to see how the problem works (this is also another excuse to make a Matryoshka problem).

We have 100 coins. Both Cecil and Lisa know the fact that “there are either 1 or 2 counterfeit coins.” Counterfeit coins have the same weight and are lighter than real coins. Given that Lisa knows that there are actually 2 counterfeit coins instead of 1 (and knows exactly which coins they are), find a way for Lisa to prove this fact to Cecil, aided with just a balance, such that at the end of the proof Cecil now knows there are 2 counterfeit coins but does not know the identity of any particular coin.

Read More…

Posted by: Steven Sam | December 7, 2009

Set-valued tableaux and Grothendieck polynomials

Last time, I discussed a bit about the relationship between the Chow groups of a nonsingular variety X and its K-theory. In this post, I want to specialize to the case when X is a Grassmannian and explain some of the combinatorics behind this relationship.

Set-valued tableaux

For a partition \lambda, we let D(\lambda) denote its Young diagram, i.e., we draw \lambda_i boxes in the ith row (counting from top to bottom) all left-justified. Also |\lambda| denotes the sum of its parts. Given two partitions \lambda, \mu, with \lambda \supseteq \mu (i.e., \lambda_i \ge \mu_i for all i), we set D(\lambda/\mu) = D(\lambda) \setminus D(\mu) denote its Young diagram.

Given two finite subsets A and B of positive integers, denote A<B if max(A) < min(B) and A \le B if \max(A) \le \min(B). This is not meant to define a partial order.

A set-valued tableau of D(\lambda) is an assignment T of a finite subset of positive integers to each cell in such a way that T(i,j) \le T(i,j+1) and T(i,j) < T(i-1,j) using the notation for subsets defined above. Given a set-valued tableau T, we associate to it a monomial x^T = x_1^{T_1} x_2^{T_2} \cdots where T_i is the number of times that the integer i appears in a cell of T. Also, let |T| denote the total degree of this monomial. We define the (single stable) Grothendieck polynomial to be

\displaystyle G_{\lambda/\mu}(x) = \sum_T (-1)^{|T|-|\lambda|-|\mu|} x^T

where the sum is over all set-valued tableaux of D(\lambda/\mu). Then G_{\lambda/\mu}(x) is a symmetric function in the x_i. This is not obvious, but one can prove it to be true purely combinatorially in the same way one can prove that Schur functions are symmetric purely combinatorially (it is enough to show that it is invariant under switching x_i and x_{i+1}, and this can be shown by directly switching the number of i’s and (i+1)’s within any given set-valued tableau).
Read More…

Posted by: yanzhang | November 30, 2009

M-2: Forcing properties onto integer pairs

Steven greeted me with a puzzle when I entered the office today. I got it after thinking a bit, though I definitely have seen this a long time ago:

Given 51 numbers between 1 and 100, show that you can find two of them that are relatively prime Read More…

Posted by: Steven Sam | November 23, 2009

Finite field counts and the Grothendieck ring of varieties

Lately some of us at MIT have been thinking about counting \mathbf{F}_q-rational points on some classes of varieties related to linear algebra that provide natural q-analogues for various classes of permutations. One thing we came across was some classes that have the same counts over every finite field. Yan wanted me to post about the following, so I’ll delay my post on the K-theory of the Grassmannian until next time.

We’ll consider varieties defined over a fixed field K. Form the free Abelian group on the isomorphism classes of such varieties. If Z is a closed subvariety of X, then we impose the relation

[X] = [Z] + [X \setminus Z].

We can put a product structure on this group via

[X] \cdot [Y] = [X \times Y]

though it will not be relevant for this post. Related to this product structure is a paper by Bjorn Poonen which shows that if the characteristic is 0, then this ring is not an integral domain. And presumably the result is true over positive characteristic also, but the paper uses the existence of resolution of singularities. This is the Grothendieck ring of varieties. This is at least one way to make sense of statements of the form: \mathbf{P}^2 = \mathbf{A}^2 + \mathbf{P}^1 = \mathbf{A}^2 + \mathbf{A}^1 + \mathbf{A}^0.
Read More…

Posted by: Steven Sam | November 9, 2009

Chow rings and K-theory

I want to write a post about the set-valued tableaux of Buch and how they are related to Schur polynomials. But since these two things are related to the K-theory and Chow ring, respectively, of the Grassmannian, I thought I would write a post explaining some basic generalities between the Chow ring and K-theory. Let X be a variety over an algebraically closed field K.

First let’s define the Chow groups. We first form the k-cycles Z_k(X) to be the free Abelian group spanned by the k-dimensional subvarieties of X. Let [V] be the basis element corresponding to a subvariety V. Pick a subvariety W of X of dimension k+1, and a nonzero rational function f/g defined on W. If V is a codimension 1 subvariety of W, let \mathcal{O}_{W,V} be the ring obtained by taking the ring of polynomial functions on W and inverting all polynomial functions which are not identically zero on V. We define the order {\rm ord}_V(f/g) to be \dim_K \mathcal{O}_{W,V}/(f) - \dim_K \mathcal{O}_{W,V}/(g), where the dimension is as K-vector spaces. The divisor of f/g is given by {\rm div}(f/g) = \sum_{\dim V = k} {\rm ord}_V(f/g) [V]. We say these divisors are rationally equivalent to 0, and define the Chow group {\rm A}_k(X) to be the group of k-cycles modulo rational equivalence.
Read More…

Posted by: Steven Sam | October 26, 2009

Exceptional sequences for the Grassmannian

Let K be a field of characteristic 0, and let V be a vector space over K of dimension n, and pick k < n. Let X be the Grassmannian Grass(k, V). We’ll briefly explore the (bounded) derived category of coherent sheaves of X, denoted {\bf D}^b(X).

1. Derived category review

For those unfamiliar with derived categories, here’s a quick summary. If A is any Abelian category, set K(A) to be the category of (co)chain complexes of A with the morphisms being chain maps modulo homotopy equivalence. Chain maps which induce isomorphisms are formally inverted, and the result is the derived category {\bf D}(A) of A. Usually we only want to consider bounded complexes, or at least complexes with finitely many nonzero (co)homology groups, and in this case we denote the category {\bf D}^b(A). The category is equipped with a shift functor, which just shifts the degrees of a given complex.

One thing we can do is reformulate derived functors. Given a left exact functor F \colon A \to B, we define its right derived functor {\bf R}f \colon {\bf D}^b(A) \to {\bf D}^b(B) as follows. Given an object X in A, an injective resolution X \to I^\bullet of X becomes an isomorphism in {\bf D}^b(A) (considering X as a complex with one nonzero term), so we define {\bf R}F(X) to be the complex obtained by applying F to I^\bullet. Actually, we don’t need an injective resolution, we only need a resolution consisting of F-acyclic objects (i.e., the usual right derived functors of F vanish for them). To define {\bf R}F on a general complex C^\bullet, we need to find a double complex C^\bullet \to I^{\bullet, \bullet} which is term by term an injective resolution for each C^i (these are called Cartan–Eilenberg resolutions). Then we apply F to the total complex of I^{\bullet, \bullet}. A similar story is true for right exact functors G, so we get left derived functors {\bf L}G. For notation, the left derived functor of the tensor product is denoted \stackrel{\bf L}{\otimes}.
Read More…

Posted by: Steven Sam | October 12, 2009

GLFq III: characteristic map

In the last post of this series, I gave some definitions and facts regarding the Hall–Littlewood functions. I also sketched the relationship between symmetric functions and representations of the symmetric group. Now we’ll see how this works for the finite general linear groups.

We want to imitate the Frobenius character that is used to relate the characters of the symmetric group to the ring of symmetric functions. But since the description of the conjugacy classes of the finite general linear group (and hence the parametrization of its irreducible characters) are more complicated than the description for the symmetric group, we’ll need a bigger ring to work with.
Read More…

Posted by: yanzhang | October 2, 2009

A Free Association On Basic Adjoints

I’ve been betraying the title of this blog and doing some abstract nonsense lately, mostly to relearn algebraic geometry for the n-th time for some embarrassingly large n. With the memory capabilities of a muffin, I am practically starting over each time. Luckily, each adventure feels slightly more beatable (exp points?), since I have a few more examples I can use for myself. Masnevets and I had a good discussion about a few basic examples of adjoint functors (recall the definition here: basically, we need a pair of functors F \colon C \to D and G \colon D \to C such that we have a natural isomorphism \hom_D(X, F(Y)) \cong \hom_C(G(X), Y)), and thus we have a new Concrete Nonsense post.

Before we start, I want to state that I’m trying something new. This post is not intended to be an introduction to adjoints as I originally envisioned – I realized that there are many better sources for that. Instead, I’ll try to do a free association that juxtoposes a few elementary concepts. You don’t even have to know the definitions of adjoints to start seeing what I’m getting to, since I’ll be namedropping algebraic structures like Kanye West.

My first introduction to adjoints was from algebraic topology, where you naturally bump into the functors \otimes_R and \hom(R, -). It was unnecessary at the time (for the scope of the course, at least) to know that they were adjoints, but now I know them as the “tensor-hom adjunction pair” (saying “tensor-hom” a lot helps me remember tensor as the left adjoint and hom as the right). Furthermore,  knowing this relationship allows me to remember some other things – in particular, knowing the left- and right- exactness of these functors, which I used to always mix up. Left adjoints are always right-exact, and right adjoints are always left-exact. Combined with knowing that tensoring is a left-adjoint, I now know that tensoring is right-exact and adjoints are left-exact.

Read More…

Posted by: Steven Sam | September 28, 2009

GLFq II: Hall–Littlewood functions

Last time, I discussed how to parametrize the conjugacy classes of the general linear group G over a finite field. In a sense, this group is a q-analogue of the symmetric group, so we might try to imitate the constructions for the symmetric group to get information about G. There’s a nice construction that Frobenius worked out which connects the characters of the symmetric group with the combinatorics of the Schur functions. I’ll briefly summarize the statement. The conjugacy classes of the symmetric group on n letters are parametrized by partitions of n. So we can also parametrize the irreducible characters by partitions as well (though it is not clear how to do this in a “canonical” way a priori). Ignoring the indexing issue (which can be dealt with) and letting \chi^\lambda(\mu) be the irreducible character indexed by \lambda evaluated at the conjugacy class consisting of permutations whose cycle lengths are given by the parts of \mu, then one has s_\lambda(x) = \sum_\mu z_\mu^{-1} \chi^\lambda(\mu) p_\mu(x) where s_\lambda(x) is a Schur function, p_\mu(x) is a power sum (Newton) symmetric function, and z_\mu = 1^{m_1} m_1! 2^{m_2} m_2! \cdots where m_i is the number of times that i appears as a part of \mu (the meaning of z_\mu is that n! z_\mu^{-1} is the size of the conjugacy class index by \mu.)

So the question to ask might be “can we find a similar interpretation for the characters of G?” The answer is yes, but becomes a bit more involved.
Read More…

Older Posts »

Categories