Cauchy’s Theorem

The famous Lagrange’s Theorem states that, in any finite group G, the order of any element g\in G divides the order of G. A natural follow up to this theorem is whether or not the converse holds. That is, if k\in \mathbb{N} divides the order of G, does there exist an element g\in G of order k? Unfortunately the converse is, in general, false. Examples are easy to come by; take, for instance, (\mathbb{Z}/2\mathbb{Z})^j and look for an element of order 2^i, i>1.

While the converse to Lagrange’s Theorem is false in general, Cauchy’s Theorem tells us that there are special circumstances in which the converse is true. Namely, if G is a finite group and p is a prime number dividing |G|, then we can guarantee that some element in G has order p. This means, for example, that in  the symmetric group S_n we can find an element of order p for all p\leq n (it is easy to come up with the elements here, just take a p-cycle. In general Cauchy’s Theorem does not tell you how to find such elements).

There are several proofs of Cauchy’s Theorem available. The standard first proof uses induction on the size of G, and while it is instructive, I find it to be a bit messy. Below I reproduce a (in my opinion) more elegant proof using group actions. The original version of this proof is due to James McKay.

Proof of Cauchy’s Theorem: Let G be a finite group, p a prime with p dividing |G|. Consider the set

S=\{(g_1,g_2,\dots,g_p):g_i\in G, g_1g_2\dots g_p=1\}.

In other words, S consists of tuples from G whose ordered product equals the identity. Note that once we choose g_1,\dots,g_{p-1}, the element g_p is forced to equal (g_1\cdot\dots\cdot g_{p-1})^{-1}, and thus |S|=|G|^{p-1}.

Now we make the following observation: if g_1g_2\dots g_p=1, then any cyclic permutation of the product must also yield the identity (to see this, use the relation that if ab=1 then ba=1 and induct). Thus S admits an action by the cyclic group C_p. If s\in S, then by the Orbit-Stabilizer Theorem the orbit of s must have size 1 or p. What does it mean for s to have an orbit of size 1? If this is the case, then it must be that s=(g_1,\dots,g_p) with g_1=\dots=g_p; in otherwords, s represents an element g with g^p=1. As p is prime, if we can find such a g which is not the identity element, we will have found our element of order p.

To finish, we use the fact that the orbits of a group action partition the set on which the group is acting. Thus we have

|S|=\sum_{\text{orbits}}|O|.

We know that (1,\dots,1) is contained in S since 1^p=1, and thus there is one orbit of size 1. Thus

|S|=1+\sum |O|.

Now |O|\in \{1,p\} as mentioned previously. Further, |S|=|G|^{p-1} is divisible by p, and thus the right hand side above is divisible by p. It follows immediately that the number of orbits of size 1 is a multiple of p, and as we have already found one, there must be at least p. Thus we can guarantee an element of order p as desired.

As always, thanks for reading!

Posted in Group Theory | Leave a comment

What are Permutation Patterns?

Today we examine a topic known as combinatorial pattern avoidance. There has been an explosion of interest in this field of late; see, for instance, the international permutation patterns conference, or any recent issues of your favorite discrete mathematics journal. I was first introduced to this field by Bruce Sagan at Michigan State’s SURIEM, an outstanding research program for undergraduate mathematicians.

We start from the ground up. For a positive integer n, let [n]=\{1,2,3\dots, n\}. A permutation \pi is a bijection from {}[n] to itself. So, for instance, we could have \pi: [4]\to[4] with \pi(1)=2, \pi(2)=1,\pi(3)=4,\pi(4)=3. Writing a permutation in this form is incredibly unwieldy, and hence we will use the one line notation \pi=\pi_1\pi_2\dots\pi_n, where \pi_i=\pi(i). Continuing our example from above, we would have \pi=2143. (Those familiar with these constructs may ask why we are not using the cycle notation; we will be using permutations purely as combinatorial strings and disregarding their group structure, hence the form). Given a permutation \pi=\pi_1\dots\pi_n, we say that \pi has length n.

Now given any string of positive integers w=w_1\dots w_k, we may standardize w to create st(w) by replacing the smallest letter in w with a 1, the second smallest letter in w with a 2, and in general the ith smallest letter with i. For instance, w=3581 standardizes to st(w)=2341. Two words which have the same standardization are said to be order isomorphic or in the same relative ordering, for reasons which become clear upon some thought. (Really what we are doing here is choosing a standard representative for strings based on their relative ordering; for instance, we want all three letter strings which go Small, Big, Medium to be considered the same, as they all standardize to 132.

We may now define containment and avoidance. Given a permutation \pi of length n and a permutation \sigma of length k, with k\leq n, we say that \pi contains \sigma if there exist indices i_1<i_2<\dots<i_k such that \pi_{i_1}\pi_{i_2}\dots\pi_{i_k} standardizes to \sigma. If this is not the case, then we say \pi avoids \sigma. When we ask questions such as “does \pi contain \sigma?” we will refer to \sigma as the pattern, hence the name of the field.  

Let’s have a few examples. Let \pi=43521, \tau=123, and \sigma = 231. Then I claim \pi contains \sigma but avoids \tau. I would encourage you to try and verify this for yourself before reading on. For verification, note that \pi contains the  subsequence 452, which standardizes to \sigma = 231. However, \pi does not contain any increasing subsequence of length 3, and hence \pi cannot contain \tau = 123. There are a couple remarks to be made following this example. First, note that \pi contains several subsequences which standardize to \sigma, namely 452, 451, 352, and 351. For now, we won’t worry too much about counting how many subsequences standardize to our pattern, and just focus on whether or not the pattern is contained at all. The second pedagogical remark is simply to reinforce that the subsequences taken above need not be adjacent in the original permutation, they just need to be taken in their original ordering. The subject of vincular pattern avoidance deals with placing additional restrictions on the containment, such as forcing the subsequence to be consecutive. But that is a topic for another day.

Now that we have defined the notion of permutation patterns and their containment, I would like to briefly end by listing some questions that are studied in this field, and some reasons for why this field is of interest in the first place. The list is in no particular order. I have denoted reasons of interest by “ROI” and questions by “Q”

  •  ROI: A stack is a data storage unit studied and used frequently in computer science. One operation you can try to use them for is to sort a string into increasing order; it turns out that the stack sortable permutations are exactly those which avoid the pattern 231. This is a result due to Knuth, and this result is largely credited for the explosion of interest in this area.
  • Q: Fix a permutation \sigma of length k. As an explicit function of n, how many permutations of length n avoid sigma? Remarkably, if \sigma is any permutation of length 3, then the answer is given by the Catalan numbers.
  • Q: If we cannot give an explicit formula to the question above, can we give asymptotics? One of the biggest open problems in the field currently is to find a tight growth rate for the number of permutations avoiding the pattern 1324.
  • ROI: Permutation patterns are beginning to be used in dynamical modeling. See, for instance, “The Frequence of Pattern Occurrence in Random Walks” by S. Elizalde and M. Martinez.
  • Q: What is the computational complexity of determining whether or not a given permutation contains another permutation? What if we restrict the class of permutations we examine?
  • Q: Let \Pi denote the set of all permutations of any arbitrary (finite) length, and put an ordering on \Pi by \sigma\leq \pi if and only if \pi contains \sigma as a pattern. Then this can readily be checked to be a partially ordered set (poset) known as the permutation pattern poset. This has been an object of intense study recently; a large open problem is finding the Mobius function of this poset.

I think that this is a good list for now. If you are interested in more, here is a decent place to start. Alternatively, come back to my blog in a week or so! I will plan on proving some more results from this area, starting with the Catalan result in the second bullet point above.

As always, thanks for reading!

Posted in Combinatorics, Patterns | Tagged | Leave a comment

On the geometric mean of the binomial coefficients

Today we prove a remarkable asymptotic result regarding the binomial coefficients. Namely, let G_n=\left(\prod_{k=1}^n\binom{n}{k}\right)^{\tfrac{1}{n+1}}. We will show

\displaystyle \lim_{n\to\infty}G_n^{\frac{1}{n}}=\sqrt{e}.

Before getting to the proof, I should say that this is most definitely not my creation; I believe the first publication of this proof may be credited to Polya (but I am not sure). In any case, I was shown this proof at MSU in my Putnam training seminar. It was presented by Dr. Ignacio Uriarte-Tuero. Any unintended errors introduced are mine alone.

To start, we use the definition of \binom{n}{k} to write

\begin{aligned} G_n^{n+1}&=\prod_{k=1}^n\binom{n}{k}\\&=\frac{(n!)^{n+1}}{\prod_{k=1}^n(k!)^2}\end{aligned}

Now for 1\leq j\leq n, we want to examine the power of j which appears in the fraction. So, for instance, n appears n+1 times in the numerator and twice in the denominator from (n!)^2, n-1 appears n+1 times in the numerator and four times in the denominator from (n!)^2 and ((n-1)!)^2, etc. We get the formula

G_n^{n+1}=\prod_{k=1}^n(n+1-k)^{n+1-2k}

We now multiply by 1 in a clever way. Noting that \sum_{k=1}^n(n+1-2k)=0 we obtain

G_n^{n+1}=\prod_{k=1}^n(n+1-k)^{n+1-2k}=\prod_{k=1}^n\left(\frac{n+1-k}{n+1}\right)^{n+1-2k}

as the denominator has total exponent 0. We can now write

G_n=\prod_{k=1}^n\left(\frac{n+1-k}{n+1}\right)^{1-\frac{2k}{n+1}}=\prod_{k=1}^n\left(1-\frac{k}{n+1}\right)^{1-\frac{2k}{n+1}}

We want to examine G_n^{\frac{1}{n}}. Taking logarithms, we get

\frac{1}{n}\ln(G_n)=\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})

We now recognize this expression as a Riemann sum of the function g(x)=(1-2x)\ln(1-x) on the interval {}[0,1]. (Ok, it is not exactly a Riemann sum; we should be dividing by n+1, not n. But in the limit this will not matter.) Taking limits, it follows that

\lim_{n\to\infty}\frac{\ln(G_n)}{n}=\lim_{n\to\infty}\frac{1}{n} \sum_{k=1}^n(1-\frac{2k}{n+1})\ln(1-\frac{k}{n+1})=\int_0^1(1-2x)\ln(1-x)dx

Evaluating the integral is now easy via integration by parts; it turns out that

 \int_0^1(1-2x)\ln(1-x)dx=\frac{1}{2}

and thus \lim_{n\to\infty}\ln(G_n^{\frac{1}{n}})=\frac{1}{2} and \lim_{n\to\infty} G_n^{\frac{1}{n}}=\sqrt{e}.

And we’re done! As always, thanks for reading!

Posted in Asymptotics, Combinatorics, Contest Math | Leave a comment