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.

Fixed Points of
Parking Functions
Nathan Williams
University of Texas at Dallas
October 16, 2019
Joint with Jon McCammond and Hugh Thomas
Outline
1. Puzzle
2. Invariants and Coinvariants
3. Diagonal Coinvariants
4. Sweep Maps
5. GMV's Map
6. Puzzle Revisited
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Acting on (-8,9,5)
by 0 gives
(-8+3,9,5)=(-5,9,5)=(-6,8,4)
Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue.
I'm going to keep the sum at 6.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Acting on (-8,9,5)
by 0 gives
(-8+3,9,5)=(-5,9,5)=(-6,8,4)
Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Acting on (-6,8,4)
by 1 gives
(-6,8,4+3)=(-6,8,7)=(-7,7,6)
Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.
A word in $[n]^m$ acts on $\mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $(i+1)$st smallest entry of $\mathbf{x}$. Continue, repeat.

This example fell into a periodic orbit...what about ties?
A word in $[n]^m$ acts on $\mathfrak{S}_n \backslash \mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $i$th largest entry of $\mathbf{x}$ and sort.
The point $(0,2,4)$ is a fixed point for the word 01020:
$024 \xrightarrow{0} 123 \xrightarrow{1} 024 \xrightarrow{0} 123 \xrightarrow{2} 015 \xrightarrow{0} 024$
So which words have fixed points?

Parking Functions

Invariants and Coinvariants

Invariants

The Fundamental Theorem of Symmetric Functions.
For $G=\mathfrak{S}_n$ acting on $\mathbb{C}^n$, we have $\mathbb{C}[x_1,\ldots,x_n]^{\mathfrak{S}_n}=\mathbb{C}[p_1,\ldots,p_n].$

Any choice of homogeneous generators gives the same set of degrees: $\{1,2,\ldots,n\}.$ monomial,
elementary,
homogenous,
power,
Schurs,
...
forgotten
Invariants of complex reflection groups

Theorem (Shephard-Todd, Chevalley).
A finite group $G \leq \mathrm{GL}(V)$ is a complex reflection group if and only if $\mathbb{C}[V]^G$ is again a polynomial ring.

Any choice of homogeneous generators gives the same set of degrees: $\{d_1,\ldots,d_n\}.$
Coinvariants

\begin{align}\text{Let }\mathfrak{S}_n\text{ act on } \mathbb{C}[\mathbf{x}]&=\mathbb{C}[x_1,\ldots,x_n] \text{ and define} \\ \mathcal{R}_n&=\mathbb{C}[\mathbf{x}]/\langle\mathbb{C}[\mathbf{x}]^{\mathfrak{S}_n}_+\rangle,\end{align}
where $\langle\mathbb{C}[\mathbf{x}]^{\mathfrak{S}_n}_+\rangle$ is the ideal generated by $\mathfrak{S}_n$-invariants with no constant term. $\mathcal{R}_n=\bigoplus_{i\geq 0} \mathcal{R}_n^{(i)}$ is graded by degree and
Theorem. $\mathrm{Hilb}(\mathcal{R}_n,q)=\sum_{i\geq 0} \mathrm{dim}\left(\mathcal{R}_n^{(i)}\right) q^i = \sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}=[n]!_q$
Garsia-Stanton basis (major index)

Theorem. $\mathrm{Hilb}(\mathcal{R}_n,q)=\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}.$

For a permutation $\pi \in \mathfrak{S}_n$, $D(\pi)=\{ i : \pi_i>\pi_{i+1}\}$ $\pi=\color{blue}{7}4\color{blue}{9}2\color{blue}{6}15\color{blue}{8}3 \hspace{2em} D(\pi)=\{\color{blue}{1},\color{blue}{3},\color{blue}{5},\color{blue}{8}\}$ $\pi \mapsto (\color{blue}{x_{7}})(x_7 x_4 \color{blue}{x_{9}})(x_7 x_4 x_9 x_2 \color{blue}{x_{6}}) (x_7 x_4 x_9 x_2 x_6x_1 x_5 \color{blue}{x_{8}})$ $\mathcal{R}_n = \mathrm{span}_\mathbb{C}\left\{\prod_{i \in D(\pi)} x_{\pi_1}x_{\pi_2}\cdot\cdots\cdot x_{\pi_i} \right\}_{\pi \in \mathfrak{S}_n}$
Artin basis (inversions)

Theorem. $\mathrm{Hilb}(\mathcal{R}_n,q)=\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}.$

For a permutation $\pi \in \mathfrak{S}_n$, $C(\pi)_{\color{red}{i}}=\left|\{j < i : \color{blue}{\pi_j}> \color{red}{\pi_i}\}\right|$. $\pi=4\color{blue}{7}2\color{blue}{6}1\color{blue}{9}\color{red}{5}83 \hspace{2em} C(\pi)=002140\color{red}{3}16$ $\pi \mapsto x_1^0x_2^0x_3^2x_4x_5^4x_6^0x_7^{\color{red}{3}}x_8^1x_9^6$ $\mathcal{R}_n = \mathrm{span}_\mathbb{C}\left\{x_1^{C(\pi)_1}x_1^{C(\pi)_2}\cdot\cdots\cdot x_n^{C(\pi)_n}\right\}_{\pi \in \mathfrak{S}_n}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

Combinatorics before algebra.

Theorem. (Foata)
There is a bijection $\phi$ on $\mathfrak{S}_n$ such that $\color{blue}{\mathrm{maj}(\pi)}=\color{red}{\mathrm{inv}(\phi(\pi))}$.
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$7 \leftarrow 4$ $\begin{array}{c|c} \circlearrowleft& \\ 7& 4\end{array}$ $\begin{array}{cc} 7& 4 \end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$74 \leftarrow 9$ $\begin{array}{c|c|c} \circlearrowleft& \circlearrowleft& \\7 &4 &9\end{array}$ $\begin{array}{ccc} 7 &4 &9\end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$749 \leftarrow 2$ $\begin{array}{c|c|c|c} \circlearrowleft& \circlearrowleft&\circlearrowleft& \\ 7&4&9&2\end{array}$ $\begin{array}{cccc} 7&4&9&2\end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$7492 \leftarrow 6$ $\begin{array}{cc|cc|c} &\circlearrowleft& &\circlearrowleft& \\ 7& 4 &9 &2 &6 \\ 4&7&2&9&6 \end{array}$ $\begin{array}{ccccc} 4&7&2&9&6 \end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$47296 \leftarrow 1$ $\begin{array}{c|c|c|c|c|c} \circlearrowleft& \circlearrowleft&\circlearrowleft&\circlearrowleft&\circlearrowleft&\\4&7&2&9&6&1\end{array}$ $\begin{array}{cccccc}4&7&2&9&6&1\end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$472961 \leftarrow 5$ $\begin{array}{c|cc|ccc|c} \circlearrowleft& & \circlearrowleft& & & \circlearrowleft& & \\ 4&7&2&9&6&1&5& \\ 4& 2 & 7 & 1 & 9 & 6 & 5 \end{array}$ $\begin{array}{ccccccc} 4& 2 & 7 & 1 & 9 & 6 & 5 \end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$4271965 \leftarrow 8$ $\begin{array}{c|c|c|c|cc|c|c} \circlearrowleft&\circlearrowleft&\circlearrowleft&\circlearrowleft&&\circlearrowleft&\circlearrowleft& \\ 4&2&7&1&9&6&5&8\\ 4 &2 & 7 & 1 & 6 & 9 & 5 & 8\end{array}$ $\begin{array}{cccccccc}4 &2 & 7 & 1 & 6 & 9 & 5 & 8\end{array}$
Foata:  $\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}$

$\color{blue}{\pi=749261583}$ $\bullet \pi_{k}>\pi_{k+1}$: bar after every $\pi_j>\pi_{k+1}$ and rotate
$\bullet \pi_{k}<\pi_{k+1}$: bar after every $\pi_j<\pi_{k+1}$ and rotate

$42716958 \leftarrow 3$ $\begin{array}{c|cc|cc|c|c|c|c} \circlearrowleft& & \circlearrowleft& & \circlearrowleft& \circlearrowleft& \circlearrowleft& \circlearrowleft& \\ 4&2&7&1&6&9&5&8&3 \\ 4&7&2&6&1&9&5&8&3\end{array}$ $\color{red}{\phi(\pi)=472619583}$
$\tiny\color{blue}{\begin{array}{c|ccccccccc}D(\pi)&1&\cdot&3&\cdot&5&\cdot&\cdot&8&\cdot\\\pi&7&4&9&2&6&1&5&8&3\end{array}}$ $\color{blue}{\pi=749261583} \hspace{2em} \color{blue}{\mathrm{maj}(\pi)=17}$
$\color{red}{\phi(\pi)=472619583} \hspace{1em} \color{red}{\mathrm{inv}(\phi(\pi))=17}$ $\tiny\color{red}{\begin{array}{c|ccccccccc}C(\phi(\pi))&0&0&2&1&4&0&3&1&6\\\phi(\pi)&4&7&2&6&1&9&5&8&3\end{array}}$
Theorem. (Foata)
$\phi$ is a bijection on $\mathfrak{S}_n$ and $\color{blue}{\mathrm{maj}(\pi)}=\color{red}{\mathrm{inv}(\phi(\pi))}$.

$\color{blue}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{maj}(\pi)}}=\color{red}{\sum_{\pi \in \mathfrak{S}_n} q^{\mathrm{inv}(\pi)}}.$

Diagonal Coinvariants

Diagonal Coinvariants

\begin{align}\text{Let }\mathfrak{S}_n\text{ act diagonally on } \mathbb{C}[\color{red}{\mathbf{x}},\color{blue}{\mathbf{y}}]&=\mathbb{C}[\color{red}{x_1,\ldots,x_n},\color{blue}{y_1,\ldots,y_n}] \text{ and define} \\ \mathcal{DH}_n&=\mathbb{C}[\color{red}{\mathbf{x}},\color{blue}{\mathbf{y}}]/\langle\mathbb{C}[\color{red}{\mathbf{x}},\color{blue}{\mathbf{y}}]^{\mathfrak{S}_n}_+\rangle, \end{align}

where $\langle\mathbb{C}[\mathbf{x},\mathbf{y}]^{\mathfrak{S}_n}_+\rangle$ is the ideal in $\mathbb{C}[\mathbf{x},\mathbf{y}]$ generated by the $\mathfrak{S}_n$-invariants with no constant term. $\mathcal{DH}_n$ is bigraded, so...

Problem (A. Garsia, M. Haiman). $\mathrm{Hilb}(\mathcal{DH}_n,\color{red}{q},\color{blue}{t})\stackrel{?}{=} \sum_{?} \color{red}{q^{?}}\color{blue}{t^{?}}.$
Dyck Paths

Definition.
An $(n,m)$-Dyck word records the column lengths of an $(n,m)$-Dyck path (a path in an $n \times m$ rectangle that stays above the diagonal).
$\begin{array}{ccccccccc}0& &0&&0&&1&&2\end{array}$
Parking Functions

Definition. An $(n,m)$-parking function is a permutation of an $(n,m)$-Dyck word. $\tiny \mathcal{PW}_n^m:=\left\{ p_1 p_2 \ldots p_m \in [n]^m : \big|\{p_j < i\}\big| \geq \frac{im}{n}\right\}.$

We can draw an $(n,m)$-parking function $\mathfrak{p}$ as a labelled Dyck path.
$\begin{array}{ccccccccc}1& &0&&0&&0&&2\end{array}$
Diagonal Harmonics

Theorem. (Specialization of the shuffle conjecture)
Conjectured: 2004 by J. Haglund and N. Loehr,
Proved: 2015 by E. Carlsson and A. Mellit, 2018 by E. Carlsson and A. Oblomkov. $\mathrm{Hilb}(\mathcal{DH}_n,q,t)= \sum_{\pi \in \mathfrak{S}_n} t^{\color{blue}{\mathrm{maj}(\pi)}} \prod_{i=1}^n [\color{red}{w_i(\pi)}]_q= \sum_{p \in \mathcal{P}_n} q^{\mathrm{\color{red}{dinv}}(p)}t^{\mathrm{\color{blue}{area}}(p)}.$

■ $\mathcal{P}_{n}$ are $(n,n{+}1)$-parking functions (@$q=0,t=0$).

■ $\color{red}{w_i(\pi)}$ is something like $\color{red}{\mathrm{inv}}$.

■ area is just the sum of the parking function.

A Foata-Like Generalization

Conjecture. (E. Gorsky, M. Mazin, M. Vazirani) Fix $n,m$ coprime.
There is a bijection $\zeta:\mathcal{P}_{n}^m \to \mathcal{P}_{n}^m$ such that if we define the "combinatorial Hilbert series" $\mathrm{H}_{n,m}(q,t):= \sum_{p \in \mathcal{P}_{n}^m} q^{\mathrm{\color{red}{area}}(\zeta(p))}t^{\mathrm{\color{blue}{area}}(p)},$ then
■ $\mathrm{Hilb}(\mathcal{DH}_n,q,t)=\mathrm{H}_{n,n+1}(q,t)$,
■ $\mathrm{H}_{n,m}(\color{red}{q},1)=\mathrm{H}_{n,m}(1,\color{blue}{q})$.

Motivations from symmetric functions, DAHA, and affine Springer fibers:
■ For $n,m$ coprime, Lusztig and Smelt defined affine Springer fibers $\Sigma_{\widetilde{w}}$ naturally indexed by certain elements $\widetilde{w}$ of the affine symmetric group.
■ Further studied by Hikita, who found a formula for the dimension of $\Sigma_{\widetilde{w}}$.

Sweep Maps

Sweep Maps

Theorem.
Conjectured: 2014 by Armstrong, Loehr, and Warrington.
Proved: 2012 by Thomas and W.
Armstrong, Loehr, and Warrington's sweep map is a bijection on $(n,m)$-Dyck paths.

Levels

Fix $n$ and $m$ coprime. For $(i,j) \in \mathbb{Z} \times \mathbb{Z}$, define the level $\ell(i,j)=(i,j) \bullet (n,m)=in+jm.$
$n=3$ and $m=5$.
Sweep Maps Sort Levels

Theorem (Thomas, W.).
Armstrong, Loehr, and Warrington's sweep map is a bijection on $(n,m)$-Dyck paths.

$\tiny \begin{array}{cccccccccccc} 0&4&8&12&16&9&13&6&10&14&7\\ E&E&E&E&S&E&S&E&E&S&S\\ \end{array} \mapsto$$\tiny \begin{array}{ccccccccccc} 0&4&6&7&8&9&10&12&13&14&16\\ E&E&E&S&E&E&E&E&S&S&S\\ \end{array}\phantom{\mapsto}$

Sweep Maps Sort Levels

Theorem (Thomas, W.).
Armstrong, Loehr, and Warrington's sweep map is a bijection on $(n,m)$-Dyck paths.

As Greg Warrington says, "Sorting is not usually bijective!"

The inverse map is described by the following story...

How my computer works (idealized)

The day has 5 hours, and my computer has the (prioritized) list of 7 tasks:

Length

1.     1.    Run garbage collection
2.     2.    Scan for viruses
■■■
3.     3.    Ask user to update software
■■■
4.     4.    Update software anyway
5.     5.    Display spinning wheel
■■■■
6.     6.    Freeze mouse temporarily
■■
7.     7.    Execute user commands

Summary: The ordered list of task lengths is $[1,3,3,1,4,2,1]$.
How my computer works (idealized)

The day has 5 hours, and my computer has the (prioritized) list of 7 tasks:

Length

1.     1.    Run garbage collection
2.     2.    Scan for viruses
■■■
3.     3.    Ask user to update software
■■■
4.     4.    Update software anyway
5.     5.    Display spinning wheel
■■■■
6.     6.    Freeze mouse temporarily
■■
7.     7.    Execute user commands

Problem. Find an equitable assignment of starting hours for the tasks so that the workload throughout the day is constant.

Example. Find an equitable assignment of starting hours for the ordered list of task lengths $[1,3,3,1,4,2,1]$ and a 5 hour day.

Example. Find an equitable assignment of starting hours for the ordered list of task lengths $[1,3,3,1,4,2,1]$ and a 5 hour day.

• The day is divided into $m$ hours.
• There are $N$ tasks to be carried out each day (prioritized from $1$ to $N$).
• Each task takes an integer number of hours to complete (between $0$ and $N-1$).
• Tasks start on the hour, and cannot be interrupted once started.
• Tasks can be worked on concurrently.
• The schedule repeats every day (tasks can carry over into the next day).
• The total amount of time required to carry out all of the tasks is some multiple of $m$.

Problem. Find an equitable assignment of starting hours for the tasks so that the workload throughout the day is constant.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.

Theorem (Thomas, W.). There always exists an equitable assignment of starting hours.
Sweep Maps

Theorem.
Conjectured: 2014 by Armstrong, Loehr, and Warrington.
Proved: 2012 by Thomas and W.
Armstrong, Loehr, and Warrington's sweep map is a bijection on $(n,m)$-Dyck paths.

Gorksy-Mazin-Vazirani's Map

Affine Permutations

The affine symmetric group $\widetilde{\mathfrak{S}}_m$ is the group of bijections $\widetilde{w}: \mathbb{Z} \to \mathbb{Z}$ such that $\widetilde{w}(i+m)=\widetilde{w}(i)+m$ and $\sum_{i=1}^m \widetilde{w}(i) = \binom{m+1}{2}.$
Affine Permutations

We represent elements of $\widetilde{\mathfrak{S}}_m$ in (short) one-line notation $\widetilde{w} = \left[\widetilde{w}(1),\widetilde{w}(2),\ldots,\widetilde{w}(m)\right].$
The Sommers Region

Definition. The $(n,m)$-Sommers region in $\widetilde{\mathfrak{S}}_m$ is bounded by the hyperplanes corresponding to roots of height $n$ ($m$ coprime to $n$).
$n^{m-1}$$4^2 Consists of the elements of \widetilde{\mathfrak{S}}_m with no inversions of height n. The Sommers Region Definition. The (n,m)-Sommers region in \widetilde{\mathfrak{S}}_m is bounded by the hyperplanes corresponding to roots of height n (m coprime to n). n^{m-1}$$5^2$
Contains the elements of $\widetilde{\mathfrak{S}}_m$ with no inversions of height $n$.
A Brief History of the Sommers Region

1.      1980s
Luzstig, Shi, ...: affine Kazhdan-Luzstig cells
2.     1991
Lusztig, Smelt: affine Springer fibers
3.     1993
Haiman: diagonal coinvariants for Weyl groups
4.     1995
Pak-Stanley: parking functions
5.     1996
Fan: affine Springer fibers
6.     1996
Reiner, Postnikov: Nonnesting partitions
7.     1965 to 1998
Peterson (Kostant): abelian ideals of Borel
8.     2003
Haglund-Loehr: statistics on parking functions
9.     2004
10.     2010
Armstrong: Shi and Ish statistics
11.     2012
Hikita: affine Springer fibers
12.     2012
Gorsky, Mazin, Vazirani: rational parking functions and zeta
13.     2012
Thomas, W.: Cyclic Symmetry
14.     2014
Armstrong, Loehr, and Warrington: sweep and rational statistics

15.     2017
Sommers surprised to learn about the Sommers region
The Pak-Stanley and GMV Map

GMV generalized the Pak-Stanley map by counting inversions of height less than $m$ for affine permutations in the Sommers region.

We'll give an equivalent definition that feels more like sweep.
Recall the Levels

Fix $n$ and $m$ coprime. For $(i,j) \in \mathbb{Z} \times \mathbb{Z}$, define the level $\ell(i,j)=(i,j) \bullet (n,m)=in+jm.$
$n=3$ and $m=5$.
Paths in $\mathbb{Z} \times \mathbb{Z}$

A lattice path is periodic if it repeats after $n+m$ steps. Such a path is specified by its $n$ levels visible from the left

$\{\color{red}{-7},\color{red}{-2},\color{red}{0}\}$
(or by the $m$ levels visible from below $\{-7,-4,-1,0,2\}$)
Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep using Visible Levels

Revisiting Sweep

$\text{What if we "swept" in a different order?}$
Parking Functions as Labelled Lattice Paths

Draw an $(n,m)$-parking function $\mathfrak{p}$ as a labelled periodic lattice path.
$10001$
$\mapsto$
Gorsky-Mazin-Vazirani Generalizes Sweep

■ Draw a parking function $\mathfrak{p}$ as a periodic labelled lattice path.
■ Remove exterior boxes in order of the label of the horizontal step to their right.
■ Record the relative order of the removed label among the visible labels.

$\color{red}{0}\mathbf{4}\color{red}{5} \hspace{5em} \color{red}{05}\mathbf{7}$ $\zeta(\mathfrak{p})= 1\ldots$
Gorsky-Mazin-Vazirani Generalizes Sweep

$\text{Record the relative order of the label removed}.$

$0\mathbf{4}5 \rightarrow \mathbf{0}57 \rightarrow \mathbf{3}57 \rightarrow 5\mathbf{6}7 \rightarrow 5\mathbf{7}9 \rightarrow 59A$ $\zeta(\mathfrak{p})= 10011 \color{red}{\text{ is again a (3,5)-parking function!}}$
Invertibility of $\zeta$

Conjecture (Gorsky, Mazin, Vazirani).
For $n,m$ coprime, $\zeta$ is a bijection on $\mathcal{P}_n^m$.

■ Known for $m=n+1$ (Haglund-Haiman-Loehr)

■ Known for $m=kn+1$ (Loehr)

■ Known for $m=kn-1$ (Gorsky-Mazin-Vazirani)
Given $\zeta(\mathfrak{p})$, how to reconstruct $\mathfrak{p}$?

■ The effect on the underlying Dyck path for $\mathfrak{p}$ is to shift it up.
■ On visible labels, the total effect is to add $m$ to each label.
■ Up to "balancing", these visible labels are therefore a fixed point for $\zeta(\mathfrak{p})$.
■ This fixed point allows us to reconstruct the original underlying Dyck path using levels, and then $\mathfrak{p}$ itself.

Finding this fixed point is equivalent to inverting $\zeta$.

Puzzle Revisited

A word in $[n]^m$ acts on $\mathfrak{S}_n \backslash \mathbb{R}^n/\mathbb{1}$

Read an $i$: add $n$ to the $i$th largest entry of $\mathbf{x}$ and sort.
The point $(0,2,4)$ is a fixed point for the word 01020:
$024 \xrightarrow{0} 123 \xrightarrow{1} 024 \xrightarrow{0} 123 \xrightarrow{2} 015 \xrightarrow{0} 024$
So which words have fixed points?

So which words have fixed points?

Theorem. (McCammond, Thomas, W.)

The action by a word $p \in [n]^m$ on $\mathfrak{S}_n \backslash \mathbb{R}^n/\mathbb{1}$ has:

■   a unique fixed point when $n, m$ coprime and $p \in \mathcal{P}_n^m$;

■  infinitely many fixed points when $n, m$ not coprime and $p\in \mathcal{P}_n^m$;

■  no fixed points if $p\not \in \mathcal{P}_n^m$.

Hence, $\zeta$ is invertible when $n,m$ are coprime.
Proof Sketch

■   For $p$ an $(n,m)$-parking word with $n,m$ coprime, we argue that $p$ sends a (large) disk into itself. The Brouwer fixed-point theorem implies existence of a fixed point.

■   We argue that there is a unique fixed point $\mathbf{x}$ (in the center of an alcove). The points that don't get closer to $\mathbf{x}$ when iterating $p$ are exactly the points in the alcove containing $\mathbf{x}$.

■   The center of any alcove eventually converges to $\mathbf{x}$ when iterating!

■   We take linear combinations of coprime fixed points to construct infinitely many fixed points in the non-coprime case.

■   We show that non-parking words send every point to infinity.
A Few Open Problems

■  algorithmic proof

■  combinatorial proof of $(q,t)$-symmetry

■  Frobenius series

■  Sommers regions in non-affine types

■  noncrossing and nonnesting

Thank you!

Use a spacebar or arrow keys to navigate