The magic of cyclic sieving and q-analogs

In my previous post the 14 possible triangulations of hexagons were arranged by Whitehead moves. But if asked, most people would probably group them in this way:

Triangulations of hexagon
Triangulations of hexagon

Well, some may decide to put the S- and Z-shapes together since they are mirror images of each other. But I won’t. It’s easy to rotate a piece of paper with a triangulation on it; it’s not nearly as easy to fetch a mirror and study triangulations through it. So let it be recorded that the cyclic group \mathbb Z_6 acts on triangulations by rotating the hexagon. The orbits have lengths 6,3,3,2.

In the previous post I also mentioned that the number of triangulations of an (n+2)-gon is the Catalan number C_n=\frac{1}{n+1}\binom{2n}{n}. With n=4 we get

\displaystyle C_4=\frac{1}{5}\,\frac{8\cdot 7\cdot 6\cdot 5}{4\cdot 3\cdot 2}=\frac{8\cdot 7\cdot 6}{4\cdot 3\cdot 2} \qquad (*)

Amazingly, the formula (*) does not just count triangulations: it also knows how they behave under rotations of the hexagons. But it will only tell us if we don’t rush to its evaluation. Instead, replace each number on the right of (*) by its q-analog

\displaystyle [n]_q=\frac{1-q^n}{1-q}  =1+q+q^2+\dots+q^{n-1}

The result is

\displaystyle C_4(q) = \frac{(1-q^8)(1-q^7)(1-q^6)}{(1-q^4)(1-q^3)(1-q^2)} =1+q^2+q^3+2q^4+q^5+2q^6+q^7+2q^8+q^9+q^{10}+q^{12}\qquad (**)

The fact that we get a polynomial can be explained: since the Catalan number is an integer, every prime divisor of the denominator in (*) also appears in the numerator (to equal or higher power), and this can be translated into the order of vanishing of polynomials in (**) at the roots of unity. It’s not as easy to explain why the coefficients end up nonnegative.

Now, both the cyclic group \mathbb Z_6 and the roots of unity were mentioned. Let’s bring them together by introducing \zeta=\exp(2\pi i/6) which generates \mathbb Z_6 by multiplication. The cyclic sieving phenomenon (in this special case) is the following: C_4(\zeta^d) is the number of triangulations fixed by the action of \zeta^d. Indeed, evaluating C_4(q) at q=\zeta,\zeta^2,\dots,\zeta^6 we get 0,2,6,2,0,14. So, no triangulations are invariant under rotation by \zeta, two are invariant under rotation by \zeta^2, etc. It’s easy to read the entire orbit structure from this:

  • there are no fixed points
  • 2 elements of order 2 form a single orbit of size 2
  • 6 elements of order 3 form two orbits of size 3
  • there are no elements of order 4, since their number is C_4(\zeta^4)-C_4(\zeta^2)=2-2=0
  • there are C_4(\zeta^6)-C_4(\zeta^2)-C_4(\zeta^3)=6 elements of order 6, which form a single orbit of size 6

And it’s not just triangulations. Consider noncrossing matchings of 2n points — these can be observed experimentally by sitting 2n people at a round table and asking them all to shake hands with someone with no arms crossing.

Handshake patterns, 8 people
Handshake patterns, 8 people

The number of such matchings is also the Catalan number C_n (hence 14 matchings for 8 people). But the orbit structure is completely different! How can the same polynomial C_4(q) work here? It can because we now act by \mathbb Z_8 and therefore take \zeta=\exp(2\pi i/8). Evaluation of C_4(q) at the powers of \zeta yields 0,2,0,6,0,2,0,14. As above, we see the orbit structure in these numbers:

  • 2 elements of order 2 form a single orbit
  • 4 elements of order 4 form a single orbit
  • 8 elements of order 8 form a single orbit

And it’s not just the Catalan numbers. Suppose that among those 8 guests at the round table are 2 men and 6 women. The number of seating arrangements is \displaystyle \binom{8}{2}=\frac{8\cdot 7}{2}. Don’t evaluate to 28 just yet. Replace each integer with its q-analog and you’ll get the polynomial \displaystyle 1+q+2q^2+2q^3+3q^4+3q^5+4q^6+3q^7+3q^8+2q^9+2q^{10}+q^{11}+q^{12}, which will tell you that under rotation, 4 arrangements form an orbit of size 4, while the other 24 form 3 orbits of size 8.

And there is much more. The cyclic sieving phenomenon was established recently (in 2004) by three mathematicians from Minnesota (Reiner, Stanton, and White), and there are still paths waiting to be explored.

1 thought on “The magic of cyclic sieving and q-analogs”

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s