Moments, Hankel determinants, orthogonal polynomials, Motzkin paths, and continued fractions

Previously we described all finite-dimensional random algebras with faithful states. In this post we will describe states on the infinite-dimensional -algebra . Along the way we will run into and connect some beautiful and classical mathematical objects.

A special case of part of the following discussion can be found in an old post on the Catalan numbers.

Read Full Post »

Lower bounds on off-diagonal Ramsey numbers

The goal of this post is to prove the following elementary lower bound for off-diagonal Ramsey numbers (where is fixed and we are interested in the asymptotic behavior as gets large):

The proof does not make use of the Lovász local lemma, which improves the bound by a factor of ; nevertheless, I think it’s a nice exercise in asymptotics and the probabilistic method. (Also, it’s never explicitly given in Alon and Spencer.)

Read Full Post »

The Schrödinger equation on a finite graph

One of the most important discoveries in the history of science is the structure of the periodic table. This structure is a consequence of how electrons cluster around atomic nuclei and is essentially quantum-mechanical in nature. Most of it (the part not having to do with spin) can be deduced by solving the Schrödinger equation by hand, but it is conceptually cleaner to use the symmetries of the situation and representation theory. Deducing these results using representation theory has the added benefit that it identifies which parts of the situation depend only on symmetry and which parts depend on the particular form of the Hamiltonian. This is nicely explained in Singer’s Linearity, symmetry, and prediction in the hydrogen atom.

For awhile now I’ve been interested in finding a toy model to study the basic structure of the arguments involved, as well as more generally to get a hang for quantum mechanics, while avoiding some of the mathematical difficulties. Today I’d like to describe one such model involving finite graphs, which replaces the infinite-dimensional Hilbert spaces and Lie groups occurring in the analysis of the hydrogen atom with finite-dimensional Hilbert spaces and finite groups. This model will, among other things, allow us to think of representations of finite groups as particles moving around on graphs.

Read Full Post »

Ramsey theory and Fermat’s Last Theorem

In the first few lectures of Graph Theory, the lecturer (Paul Russell) presented a cute application of Ramsey theory to Fermat’s Last Theorem. It makes a great introduction to the general process of casting a problem in one branch of mathematics as a problem in another and is the perfect size for a blog post, so I thought I’d talk about it.

The setup is as follows. One naive way to go about proving the nonexistence of nontrivial integer solutions to (that is, solutions such that are not equal to zero) is using modular arithmetic; that is, one might hope that for every it might be possible to find a modulus such that the equation has no nontrivial solution . To simplify matters, we’ll assume that are relatively prime to , or else there is some subtlety in the definition of “nontrivial” (e.g. we might have not divisible by but .) Note that it might be the case that is not relatively prime to a particular nontrivial solution in the integers, but if we can prove non-existence of nontrivial solutions for infinitely many (in particular, such that any integer is relatively prime to at least one such ) then we can conclude that no nontrivial integer solutions exist.

By the Chinese Remainder Theorem, this is possible if and only if it is possible with a prime power, say . If is relatively prime to , this is possible if and only if it is possible with . This is because given a nontrivial solution we can use Hensel’s lemma to lift it to a nontrivial solution for any (and even to ), and the converse is obvious. (Again to simplify matters, we’ll ignore the finitely many primes that divide .) So we are led to the following question.

For a fixed positive integer do there exist infinitely many primes relatively prime to such that has no nontrivial solutions?

As it turns out, the answer is no. In 1916 Schur found a clever way to prove this by proving the following theorem.

Theorem: For every positive integer there exists a positive integer such that if is partitioned into disjoint subsets , then there exists such that there exist with . In other words, the Schur number exists. (Note that I am using a convention which is off by .)

If we let be a prime greater than and let the be the cosets of the subgroup of powers in , which has index at most , we obtain the following as a corollary.

Corollary: Fix a positive integer . For any sufficiently large prime , there exists a nontrivial solution to .

Read Full Post »

The McKay correspondence I

Today we’re going to relate the representation graphs introduced in this blog post to something I blogged about in the very first and second posts in this blog! The result will be a beautiful connection between the finite subgroups of , the Platonic solids, and the ADE Dynkin diagrams. This connection has been written about in several other places on the internet, for example here, but I don’t know that any of those places have actually gone through the proof of the big theorem below, which I’d like to (as much for myself as for anyone else who is reading this).

Let be a finite subgroup of . Since any inner product on can be averaged to a -invariant inner product, every finite subgroup of is conjugate to a finite subgroup of , so we’ll suppose this without loss of generality. The two-dimensional representation of coming from this description is therefore faithful and self-dual. Consider the representation graph , whose vertices are the irreducible representations of and where the number of edges between and is the multiplicity of in . We will see that is a connected undirected loopless graph whose spectral radius is . Today our goal is to prove the following.

Theorem: The connected undirected loopless graphs of spectral radius are precisely the affine Dynkin diagrams .

We’ll describe these graphs later; for now, just keep in mind that they are graphs with a number of vertices which is one greater than their subscript. In a later post we’ll see how these give us a classification of the Platonic solids, and we’ll also discuss other connections.

Read Full Post »

Walks on graphs and tensor products

Recently I asked a question on MO about some computations I’d done with Catalan numbers awhile ago on this blog, and Scott Morrison gave a beautiful answer explaining them in terms of quantum groups. Now, I don’t exactly know how quantum groups work, but along the way he described a useful connection between walks on graphs and tensor products of representations which at least partially explains one of the results I’d been wondering about and also unites several other related computations that have been on my mind recently.

Let be a compact group and let denote the category of finite-dimensional unitary representations of . As in the finite case, due to the existence of Haar measure, is semisimple (i.e. every unitary representation decomposes uniquely into a sum of irreducible representations), and via the diagonal action it comes equipped with a tensor product with the property that the character of the tensor product is the product of the characters of the factors.

Question: Fix a representation . What is the multiplicity of the trivial representation in ?

Read Full Post »

Newton’s sums, necklace congruences, and zeta functions

The goal of this post is to give a purely combinatorial proof of Newton’s sums which would have interrupted the flow of the previous post. Recall that, in the notation of the previous post, Newton’s sums (also known as the first Newton-Girard identity) state that

.

One way to motivate a combinatorial proof is to recast the generating function interpretation appropriately. Given a polynomial with non-negative integer coefficients and , let be the reciprocals of the roots of . Then

.

The left hand side of this identity suggests a particular interpretation in terms of the combinatorial species described by . Today we’ll describe this species when is a polynomial with non-negative integer coefficients and then describe it in the general case, which will handle the extension to the symmetric function case as well.

The method of proof used here is closely related to a post I made previously about the properties of the Frobenius map, and at the end of the post I’ll try to discuss what I think might be going on.

Read Full Post »

The magic of the Frobenius map II

Once upon a time I discussed some interesting uses of the Frobenius map to solve some Putnam-style problems. Unfortunately, I wrote that post before becoming really interested in combinatorics, so I neglected to develop that particular side of the story, which I’d like to do now.

The beginning of this story is the folklore combinatorial proof of Fermat’s little theorem: for any positive integer and prime , we have

.

The proof is simple but powerful. Consider the set of possible ways to color beads with colors. The cyclic group acts on this set in the obvious way. (One says that the beads are “on a necklace.”) The great thing about actions of a prime cyclic group is that elements arrange themselves into two kinds of orbits: fixed points and orbits of size . (This is just a special case of the orbit-stabilizer theorem.) The total number of colorings is , but if we only want to work it suffices to count the number of fixed points under the action of . These are precisely the colorings using only one color, of which there are , and the result follows.

The standard generalization of this result to finite fields is as follows: and is generated by the Frobenius map . Does this result also have a combinatorial proof?

Read Full Post »

The Catalan numbers, regular languages, and orthogonal polynomials

I’ve been inspired by The Unapologetic Mathematician (and his pages and pages of archives!) to post more often, at least for the remainder of the summer. So here is a circle of ideas I’ve been playing with for some time.

Let be the ordinary generating function for the ordered rooted trees on vertices (essentially we ignore the root as a vertex). This is one of the familiar definitions of the Catalan numbers. From a species perspective, ordered rooted trees are defined by the functional equation

.

The generating function describes the species of sequences. So what this definition means is that, after tossing out the root, an ordered rooted tree is equivalent to a sequence of ordered rooted trees (counting their roots) in the obvious way; the roots of these trees are precisely the neighbors of the original root. Multiplying out gets us a quadratic equation we can use to find the usual closed form of , but we can instead recursively apply the above to obtain the beautiful continued fraction

.

Today’s discussion will center around this identity and some of its consequences.

Read Full Post »

Dynkin diagrams and the Mahler measure problem

Funnily enough, a few days after I wrote the previous post, I was linked to a graph theory paper where one of the first results cited, which was clearly well-known to the authors, is the following remarkable generalization of what I tried to do:

Theorem: The only connected simple graphs with spectral radius less than or equal to are the induced subgraphs of the Dynkin diagrams .

I have to admit, I really didn’t suspect that the classification result I was going after was both so simple and so interesting! Certainly there are heuristic reasons why the above classification makes sense: as I forgot to note in the previous post, there really can’t be too many vertices of degree in a graph with . But I really can’t fathom why spectral radius can be used to define the Dynkin diagrams, considering their relationship to

- simply laced Lie groups,

- binary polyhedral groups and the Platonic solids,

- quiver representations, or

- the octonions (okay, this one is stretching it a little).

Anyone know any good references?

In any case, I’d like to discuss the McKee-Smyth paper because it has some interesting ideas I’d thought about independently.

Read Full Post »