Your browser **doesn't support the features required** by impress.js, so you are presented with a simplified version of this presentation.

For the best experience please use the latest **Chrome**, **Safari** or **Firefox** browser.

Sweeping up Zeta

Nathan Williams

LaCIM

March 7, 2016

Two stories with the same answer.

1. Understanding the orbit structure of a subdivided simplex.

Two stories with the same answer.

2. Inverting a map on lattice paths.

2002

Dihedral Symmetry in Young's Lattice

$\mathbb{Y}_0$

$\mathbb{Y}_1$

$\mathbb{Y}_2$

$\mathbb{Y}_3$

$\mathbb{Y}_4$

Suter's cyclic action

Suter's cyclic action

Suter's cyclic action

<1993

Abelian Ideals of a Borel Subalgebra

Fix $\mathfrak{g}$ a complex simple Lie algebra and $\mathfrak{b}$ a Borel subalgebra.

An *abelian ideal* $\mathfrak{a} \subseteq \mathfrak{b}$ is a subspace of $\mathfrak{b}$ such that
$[\mathfrak{a},\mathfrak{a}] = 0$ and
$[\mathfrak{g},\mathfrak{a}] \subseteq \mathfrak{a}.$

(Using the root-space decomposition \[\mathfrak{b} = \mathfrak{h} \oplus \bigoplus_{\alpha \in \Phi^+} \mathfrak{g_\alpha},\] these biject with certain order filters of "the" positive root poset.)

Why such a clean answer?

Weyl Groups

\[\mathfrak{S}_{n+1} = \left \langle s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]

- $s_i$ acts on $\mathbb{R}^{n+1}$ by reflecting in the hyperplane $x_i-x_{i+1}=0.$
- The lattice $Q = \{(x_1,x_2,\ldots,x_{n+1})\in \mathbb{Z}^{n+1} : \sum_{i=1}^{n+1}x_i = 0\}.$

Affine Weyl Groups

\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]

Why such a clean answer? Abelian ideals of $\mathfrak{b}$ specify inversion sets in the 2-fold dilation of the fundamental alcove $2A_0$:

\[\begin{align*}\mathfrak{a}&=\bigoplus_{\alpha \in \Psi \subseteq \Phi^+} \mathfrak{g}_\alpha \mapsto w \in \widetilde{W}, \text{ where}\\
\mathrm{inv}(w) &= \bigsqcup_{\alpha \in \Psi \subseteq \Phi^+} \{\delta-\alpha\}.\end{align*}\]
2004

Symmetries of the Fundamental Alcove

Why does $\mathbb{Y}_n$ have $2^n$ elements and $(n+1)$-fold cyclic symmetry?

The partitions in $\mathbb{Y}_n$ *are* abelian ideals of $\mathfrak{b}$ in type $A_n$. (So the elements of $\widetilde{A}_n$ "contained" in $2A_0$ are indexed by $\mathbb{Y}_n$.)

Why does $\mathbb{Y}_n$ have $2^n$ elements and $(n+1)$-fold cyclic symmetry?

The $(n+1)$-fold cyclic symmetry of $\mathbb{Y}_n$ comes from the symmetry of the fundamental alcove in $\widetilde{A}_n$ (the poset structure is weak order).

This symmetry has many interesting manifestations:

- Symmetry of the affine Dynkin diagram;
- Fundamental group of the Lie group $G$;
- Minuscule weights/representations;
- Index of connection;
- Weyl's formula $|W|=f n! a_1 \cdots a_n$;
- ...

This symmetry has many interesting manifestations.
**Cycle Lemma.** For $a$ and $b$ relatively prime, there are \[\frac{1}{a+b}\binom{a+b}{a}\] Dyck paths from $(0,0)$ to $(a,b)$.

2007

Cyclic Sieving Phenomenon

The Cyclic Sieving Phenomenon

In 2004, D. Reiner, D. Stanton, D. White defined the *cyclic sieving phenomenon*, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.

\[1100 \to 1001 \to 0011 \to 0110\]
\[1010 \to 0101\]
The Cyclic Sieving Phenomenon

In 2004, D. Reiner, D. Stanton, D. White defined the *cyclic sieving phenomenon*, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.

\[1100 \to 1001 \to 0011 \to 0110\]
\[1010 \to 0101\]
The Cyclic Sieving Phenomenon

In 2004, D. Reiner, D. Stanton, D. White defined the *cyclic sieving phenomenon*, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.

The Cyclic Sieving Phenomenon

\[1100 \xrightarrow{{c}} 1001 \xrightarrow{{c}} 0011 \xrightarrow{{c}} 0110\]

\[1010 \xrightarrow{{c}} 0101\]

\[\begin{align*}f(q)=\sum_{\mathcal{D} \in \binom{[4]}{2}} q^{\mathrm{area}(\mathcal{D})} &= 1+q+2q^2+q^3+q^4\\ f(\sqrt{-1}^4) &= 6 \hspace{1ex} \text{ elements fixed by } c^4, \\ f(\sqrt{-1}^2)&=2 \hspace{1ex} \text{ elements fixed by } c^2, \\ f(\sqrt{-1})&=0 \hspace{1ex} \text{ elements fixed by } c.\end{align*}\]
2010

Bijactions

Bijactions

For each partition in an orbit of $\mathbb{Y}_n$: is the first part repeated?
By construction, this gives an equivariant map from $\mathbb{Y}_n$ to The image turns out to be binary words of odd sum.

The inverse is computed by *partitioning* the word, and then "bouncing around" (starting in the block labeled by the sum).

\[1011\mathbf{0} \rightarrow \mathbf{0} (1)(1+0)(1+0+1)(1+0+1+1) \rightarrow 01101\]
The inverse is computed by *partitioning* the word, and then "bouncing around" (starting in the block labeled by the sum).

\[1010\mathbf{1} \rightarrow \mathbf{0} (1)(1+0)(1+0+1)(1+0+1+0) \rightarrow 01100\]
There is only one partition of the word for which "bouncing around" eats up all of the letters!

It is easy to find the partition for binary words...

There is only one partition of the word for which "bouncing around" eats up all of the letters!

It is easy to find the partition for binary words...

...but I generalized the combinatorics to words on $[m]$.

Finding the (*unique*) successful partitioning becomes less obvious. (It isn't even obvious such a partitioning *exists*.)

...but I generalized the combinatorics to words on $[m]$.

Finding the (*unique*) successful partitioning becomes less obvious. (It isn't even obvious such a partitioning *exists*.)

Mike Hardy and Wikipedia

Mike Hardy and Wikipedia

2011

Cores and Canada

M. Zabrocki and C. Berg generalized Suter's symmetry using the affine symmetric group $\widetilde{S}_{n+1}$ by replacing $2A_0$ with $mA_0$.

Although this gave a beautiful geometric picture, it did not help when trying to find the inverse of my map.

2012

The Inverse

Hugh Thomas and I published the general inverse in 2012.

1988

Macdonald Polynomials

The $\widetilde{H}_\mu$ generalize Hall-Littlewood polynomials, which generalize Schur and monomial symmetric polynomials.

1996

$(q,t)$-Catalan numbers

$(q,t)$-Catalan polynomials

Applying $\nabla$ to symmetric functions is a favorite past-time.

\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]

$(q,t)$-Catalan polynomials

\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]

$(q,t)$-Catalan polynomials

\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]

2001

Bounce, dinv, and Zeta

James Haglund and Mark Haiman

\[\mathrm{Cat}(n;q,t)\stackrel{?}{=}\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{???}(\mathcal{D})}\]

James Haglund and Mark Haiman

found *bounce* and *dinv*

\[\zeta: (\mathrm{dinv},\mathbf{area})\mapsto (\mathbf{area},\mathrm{bounce}).\]

\[\mathrm{Cat}(n;q,t)=\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{area}(\zeta(\mathcal{D}))}.\]

\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]

2012

The Sweep Map

The Sweep Map

- Loehr, N., 2005,
**Conjectured statistics for the higher q; t-Catalan sequences**.*Electronic Journal of Combinatorics*. - Lee, K., Li, L., and Loehr, N., 2013.
**Combinatorics of certain higher $(q,t)$-Catalan polynomials: chains, joint symmetry, and the Garsia-Haiman formula**.*Journal of Algebraic Combinatorics*. - Armstrong, D., Loehr, N. and Warrington, G., 2014.
**Sweep maps: A continuous family of sorting algorithms**.*arXiv:1406.1196*. - Gorsky, E. and Mazin, M., 2014.
**Compactified Jacobians and $(q,t)$-Catalan numbers II**.*Journal of Algebraic Combinatorics*. - Gorsky, E., Mazin, M., and Vazirani, M., 2014.
**Affine permutations and rational slope parking functions**.*Transactions of the American Mathematical Society*. - Ceballos, C., Denton, T. and Hanusa, C., 2015.
**Combinatorics of the zeta map on rational Dyck paths**.*arXiv:1504.06383*. - Sulzgruber, R., 2015.
**Rational Shi tableaux and the skew length statistic**.*arXiv:1512.04320*. - Thiel, M., 2015.
**From Anderson to Zeta: A uniform bijection between Shi regions and the finite torus**.*arXiv:1504.07363*. - Xin, G., 2015.
**An efficient search algorithm for inverting the sweep map on rational Dyck paths**.*arXiv:1505.00823*.

2015

The Inverse

CMS Sectional

Sweep Map Combinatorics

This is the same as the previous inverse, as long as we take $m$ "large enough".

Details

A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
**Definition**. An *equitable partition* has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.

For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.

A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
**Definition**. An *equitable partition* has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.

For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.

A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
**Definition**. An *equitable partition* has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.

For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.

The correctly partitioned word is the maximal element of this lattice.

The correctly partitioned word is the maximal element of this lattice.

Step 1: Get in the Lattice

Start with the partition with all letters in the leftmost block. Find the leftmost column that fails the equitable condition and move its rightmost element to the next column over. Repeat.

Step 1: Get in the Lattice

Step 2: Move to the Top

Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top

Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top

Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top

Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top

Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Thank you!

Use a spacebar or arrow keys to navigate