Archive for the ‘GILA’ Category

Another small example I noticed awhile ago and forgot to write up.

Prime numbers, as one of the most fundamental concepts in mathematics, have a way of turning up in unexpected places. For example, the life cycles of some cicadas are either 13 or 17 years. It’s thought that this is a response to predation by predators with shorter life cycles; if your life cycle is prime, a predator with any shorter life cycle can’t reliably predate upon you.

A month or so ago I noticed a similar effect happening in the card game BS. In BS, some number of players (usually about four) are dealt the same number of cards from a standard deck without jokers. Beginning with one fixed card, such as the two of clubs, players take turns placing some number of cards face-down in the center. The catch is that the players must claim that they are placing down some number of a specific card; Player 1 must claim that they are placing down twos, Player 2 must claim that they are placing down threes, and so forth until we get to kings and start over. Any time cards are played, another player can accuse the current player of lying. If the accusation is right, the lying player must pick up the pile in the center. If it is wrong, the accusing player must pick up the pile in the center. The goal is to get rid of all of one’s cards.

I’ve been playing this game for years, but I didn’t notice until quite recently that the reason the game terminates in practice is that 13, the number of types of cards in a standard deck, is prime. If, for example, we stopped playing with aces and only used 12 types of cards, then a game with 4 | 12 people need not terminate. Consider a game in which Player 1 has only cards 2, 6, 10, Player 2 has only cards 3, 7, J, Player 3 has only cards 4, 8, Q, and Player 4 has only cards 5, 9, K, and suppose that Player 1 has to play threes at some point in the game. Then no player can get rid of their cards without lying; since the number of players divides the number of card types, every player will always be asked to play a card they don’t have. Once every player is aware of this, every player can call out every other player’s lies, and it will become impossible to end the game reasonably.

More generally, such situations can occur if 13 is replaced by a composite number n such that the number of players is at least the smallest prime factor of n. This is because people who get rid of their cards will leave the game until the number of players is equal to the smallest prime factor of n, at which point the game may stall. But because 13 is prime, any game played with less than 13 people has the property that each player will eventually be asked to play a card that they have.

Read Full Post »

Mathematics in real life

A small example, but I thought it was funny.

I am currently at Logan waiting for my flight to Heathrow. An hour or so ago, one of my friends asked me how long my flight is. I knew that my flight would depart at about 7:30pm and arrive at about 7:30am, but both times are local. So the actual length of the flight is about 12 hours minus the time difference – which I didn’t know!

But then I realized I could compute the time difference because I knew two other things – the average ground speed of a commercial airplane, and the circumference of the Earth. The average ground speed of a commercial airplane is about 600 miles per hour, which I know from idly staring at that one channel that monitors the airspeed of a plane. The circumference of the Earth is 4 \times 10^4 kilometers (to an accuracy of better than one percent!), which I know from preparing for the Fermi Questions event at Science Olympiad. (This is a very handy number to know for certain types of estimates, such as this one.) Given this number, it follows that the velocity of the surface of the Earth is about 1600 kilometers per hour, or about 1000 miles per hour.

Now, suppose the flight takes x hours. Then I have traveled a distance of 600x miles, but at the same time I have crossed approximately \frac{3}{5} x time zones. So the difference in local times should be approximately \frac{8}{5} x. Setting this equal to 12 and rounding \frac{3}{5} x to the closest integer, it follows that the time difference between Boston and London is 5 hours (which it is) and that my flight will take 7 hours (which it will).

An interesting idea this computation illustrates is that if you can estimate an integer (in this case, the number of time zones my flight will cross) with enough precision, you know it exactly. A more sophisticated variant of this idea is that a continuous function from a connected space to a discrete space must be constant.

(Full disclosure: I messed up the last step when I did this calculation the first time.)

Read Full Post »

In the previous post we used the Polya enumeration theorem to give a sneaky, underhanded proof that

\displaystyle \sum_{m \ge 0} Z(S_m) t^m = \exp \left( z_1 t + \frac{z_2 t^2}{2} + \frac{z_3 t^3}{3} + ... \right).

If you’ve never seen the exponential function used like this, you might be wondering how it can be “explained.”

To explore this question, I’d like to give three other proofs of this result, the last of which will be “direct.” Along the way I’ll be attempting to describe some basic principles of species theory in an informal way. I’ll also give some applications, including to a Putnam problem.


Read Full Post »

I ended the last post by asking whether the proof of baby Polya extends to the multi-parameter setting where we want to keep track of how many of each color we use. In fact, it does. First, we should specify what exactly we’re trying to compute. Recall the setup: we have colors 1, 2, ... n (represented by variables r_1, r_2, ... r_n), and we have a set of slots S with |S| = m acted on by a group G where each slot will be assigned a color. Define f_G(t_1, ... t_n) to be the number of orbits of functions S \to \{ 1, 2, ... n \} under the action of G where color i is used t_i times. (Since the action of G only permutes slots, it doesn’t change the multiset of colors used.) What we want to compute is the generating function

\displaystyle F_G(r_1, r_2, ... r_n) = \sum_{t_1 + ... + t_n = m} f_G(t_1, t_2, ... t_n) r_1^{t_1} r_2^{t_2} ... r_n^{t_n}.

Note that setting r_1 = r_2 = .... = r_n = 1 we recover F_G(n), which doesn’t contain information about particular color combinations. By the orbit-counting lemma, this is equivalent to computing

\displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |(r_1, r_2, ... r_n)

where we must now count fixed points in a weighted manner, recording the multiset of colors in each fixed point. How do we go about doing this?


Read Full Post »

We’ve got everything we need to prove the Polya enumeration theorem. To state the theorem, however, requires the language of generating functions, so I thought I’d take the time to establish some of the important ideas. It isn’t possible to do justice to the subject in one post, so I’ll start with some references.

Many people recommend Wilf’s generatingfunctionology, but the terminology is non-standard and somewhat problematic. Nevertheless, it has valuable insight and examples.

I cannot recommend Flajolet and Sedgewick’s Analytic Combinatorics highly enough. It is readable, includes a wide variety of examples as well as very general techniques, and places a great deal of emphasis on asymptotics, computation, and practical applications.

If you can do the usual computations but want to learn some theory, Bergeron, Labelle, and Laroux’s Combinatorial Species and Tree-like Structures is a fascinating introduction to the theory of species that requires fairly little background, although a fair amount of patience. It also contains my favorite proof of Cayley’s formula.

Doubilet, Rota, and Stanley’s On the idea of generating function is part of a fascinating program for understanding generating functions with posets as the fundamental concept. I may have more to say about this perspective once I learn more about it.

While it is by no means comprehensive, this post over at Topological Musings is a good introduction to the basic ideas of species theory.

And a shameless plug: the article I wrote for the Worldwide Online Olympiad Training program about generating functions is available here. I tried to include a wide variety of examples and exercises taken from the AMC exams while focusing on techniques appropriate for high-school problem solvers. There are at least a few minor errors, for which I apologize. You might also be interested in this previous post of mine.

In any case, this post will attempt to be a relatively self-contained discussion of the concepts necessary for understanding the PET.


Read Full Post »

The orbit-stabilizer theorem implies, very immediately, one of the most important counting results in group theory. The proof is easy enough to give in a paragraph now that we’ve set up the requisite machinery. Remember that we counted fixed points by looking at the size of the stabilizer subgroup. Let’s count them another way. Since a fixed point is really a pair (g, x) such that gx = x, and we’ve been counting them indexed by x, let’s count them indexed by g. We use \text{Fix}(g) to denote the set of fixed points of g. (Note that this is a function of the group action, not the group, but again we’re abusing notation.) Counting the total number of fixed points “vertically,” then “horizontally,” gives the following.

Proposition: \displaystyle \sum_{x \in S} |\text{Stab}(x)| = \sum_{g \in G} | \text{Fix}(g) |.

On the other hand, by the orbit-stabilizer theorem, it’s true for any orbit O that \displaystyle \sum_{x \in O} | \text{Stab}(x) | = |G|, since the cosets of any stabilizer subgroup partition |G|. This immediately gives us the lemma formerly known as Burnside’s, or the Cauchy-Frobenius lemma, which we’ll give a neutral name.

Orbit-counting lemma: The number of orbits in a group action is given by \displaystyle \frac{1}{|G|} \sum_{g \in G} | \text{Fix}(g) |, i.e. the average number of fixed points.

In this post we’ll investigate some consequences of this result.


Read Full Post »

Now that we’ve discussed group actions a bit, it’s time to characterize them. In this post I’d like to take a leaf from Tim Gowers’ book and try to make each step taken in the post “obvious.” While the content of the proofs is not too difficult, its motivation is rarely discussed.

First, it’s important to note that there is a way to take direct sums or disjoint unions (category theorists would say coproducts) of group actions: given a group G acting on two sets S, T, one defines an action on their disjoint union S \sqcup T in the obvious way: pick one action or the other. (Disjoint unions differ from unions in the usual sense because we relabel the elements of the sets so that they cannot intersect.) There’s a great reason to do this, and cycle decomposition showed us a special case: every group action is a direct sum or disjoint union of the action on its orbits.

This is the first step toward a structure theorem. Since the group action cannot “mix” between two orbits, it acts “independently” on orbits, and any question we might want to ask about the group action can be answered by looking at each orbit separately. A group action with a single orbit is called transitive, which means that for every x, y in the underlying set there exists G such that gx = y. So to classify group actions it suffices to classify transitive group actions.


Read Full Post »

Older Posts »


Get every new post delivered to your Inbox.

Join 316 other followers