Standard Young tableaux and Robinson-Schensted-Knuth

Earlier I mentioned that the theory of Young tableaux is the source of one of my favorite proofs. Today I’d like to present, again from the theory of Young tableaux, one of my favorite pairs of proofs.

A standard Young tableau is a chain in Young’s lattice; equivalently, it is a sequence of Young diagrams, each of which has exactly one more box than the previous. One can succinctly write down such a chain by taking the last Young diagram in the chain and recording the “path” traced out by the rest of the chain: write down a 1 in the box corresponding to the first Young diagram, a 2 in the box added by the next Young diagram, and so forth. In other words, a standard Young tableau is a Young tableau filled with positive integers which is strictly increasing across rows and columns.

Given a Young diagram , let denote the number of standard Young tableaux of shape ; equivalently, one can define to be the poset of Young diagrams fitting inside , and then is equal to the number of maximal chains of .

Finally, one last bit of notation. If is a Young diagram for a partition of , we will write either or . Then we have the following beautiful result.

Theorem: .

Read Full Post »

IMO 2009 and proof systems

The problems from IMO 2009 are now available. I haven’t had much time to work on them, though.

There are two classical geometry problems, which I already know I won’t attempt. While I am well aware that classical geometry often requires a great deal of ingenuity, I am also aware of the existence of the field of automatic geometric theorem proving. On this subject I largely agree with Doron Zeilberger: it is more interesting to find an algorithm to prove classes of theorems than to prove individual theorems. The sooner we see areas like classical geometry as “low-level,” the sooner we can work on the really interesting “high-level” stuff. (Plus, I’m not very good at classical geometry.)

Zeilberger’s typical example of a type of theorem with a proof system is the addition or multiplication of very large numbers: it is more interesting to prove symbolically than it is to prove individual “theorems” such as . Zeilberger himself played a significant role in the creation of another proof system, but for the far less trivial case of hypergeometric identities (which includes binomial identities as a special case).

But so I can make my point concretely, I’d like to discuss some examples based on the types of problems most of us had to deal with in middle or high school.

Read Full Post »

Some examples of graded algebras

Often in mathematics we work in an algebra with the property that the “degree” of an element has a multiplicative property. For example, in a polynomial ring in variables we can define the degree of a monomial to be the vector of its degrees with respect to each variable, and the product of monomials corresponds to the sum of vectors. More typically we can define the degree of a monomial to be its total degree (the sum of the components of the above vector); this degree is also multiplicative.

Algebras with this additional property are called graded algebras, and they show up surprisingly often in mathematics. As Alexandre Borovik notes, when schoolchildren work with units such as “apples” and “people” they are really working in a -graded algebra, and one could argue that the study of homogeneous elements (that is, elements of the same degree) in -graded algebras is the entire content of dimensional analysis.

At this point, I should give some definitions.

Read Full Post »

Exceptional structures

Recently Isabel Lugo asked about problems that are hard for intermediate values of some parameter, and in discussing the question I got to thinking about exceptional structures in mathematics such as the sporadic groups. In 2006 David Corfield asked about how “natural” the sporadic simple groups are at the n-Category cafe. In that discussion and more generally there seem to be approximately two extremes in perspective:

• Exceptional structures represent a lack of room for asymptotic behavior to occur; thus they are distractions from the “generic” case. This seems to be the case for certain exceptional isomorphisms; there are only so many groups of a particular small order. It also seems to be a good way to think about objects that behave fine in characteristic zero or high characteristic but behave badly in low characteristic, characteristic usually being the worst offender.
• Exceptional structures represent the deepest part of a theory, and the exceptional structures in different fields are often related; thus understanding exceptional structures is crucial. This seems to be the case for the octonions, which can be thought of as an underlying cause of Bott periodicity. It also seems to be a good way to think about objects related to the number ; John Baez tells a great story about connections between the Leech lattice, the Dedekind eta function, string theory, and elliptic curves all centered around this mysterious number.

So what do you think? Are exceptional structures accidents or miracles? (Or, as a third option: am I failing to distinguish carefully enough between interesting and uninteresting exceptional structures?)

Read Full Post »

Mathematical historical fiction

Bill Gasarch is right – writing technical posts is tiring! (I’ve been trying to finish the next GILA post for days.) So I’ll share some more thoughts instead. Today’s thought was triggered by David Corfield:

In the first of the above posts I mention Leo Corry’s idea that professional historians of mathematics now write a style of history very different from older styles, and those employed by mathematicians themselves. …

To my mind a key difference is the historians’ emphasis in their histories that things could have turned out very differently [emphasis mine], while the mathematicians tend to tell a story where we learn how the present has emerged out of the past, giving the impression that things were always going to turn out not very dissimilarly to the way they have, even if in retrospect the course was quite tortuous.

This in turn reminded me of something else Rota wrote about his Walter Mitty fantasies:

Read Full Post »

Square roots have no unexpected linear relationships

IMO medalist Iurie Boreico has an article in an issue of the Harvard College Mathematics Review about his favorite problem:

Let be distinct squarefree integers. Show that if are not all zero, then the sum is nonzero.

In other words, the problem is to show that there are no “unexpected” linear relationships between the fractions . This is one of those nice problems that justifies an intuition without being amenable to the obvious attacks. Iurie gives several ingenious Olympiad-style arguments, i.e. arguments that don’t require much machinery, including a clearly motivated argument that serves as a good way to motivate the definition of a Galois group.

Today I want to share a different argument that generalizes a simple argument for special cases, but it has the unfortunate property that in full generality it is severe overkill.

Read Full Post »