ixed Points of Parking Function

We define an action of words in $[m]^n$ on ${{\mathbb{R}}}^m$ to give a new characterization of rational parking functionsthey are exactly those words whose action has a fixed point. We use this viewpoint to give a simple definition of Gorsky, Mazin, and Vazirani's zeta map on rational parking functions when $m$ and $n$ are coprime@gorsky2016affine, and prove that this zeta map is invertible. A specialization recovers Loehr and Warrington's sweep map on rational Dyck paths@armstrong2015sweep [@thomas2015sweeping; @gorsky2017rational].

Introduction
============

Parking Words
-------------

Classical parking words have a well-known interpretation in the language of parking cars. There are $n$ parking places and $n$ cars, each indexed from $0$ to $n{-}1$. As in @konheim1966occupancy [Section 6], car $i$ has a preference for parking place ${{\sf p}}_i$, and cars attempt to park as follows: for $0 \leq i \leq n-1$, car $i$ takes the unoccupied parking place with the lowest number larger than or equal to ${{\sf p}}_i$, should such a parking place exist. The <span>*classical parking words*</span> ${{\mathcal{PW}}}_n$ are defined as those words for which each car is able to park.

The 16 parking words in ${{\mathcal{PW}}}_3$ are given on the left side of . Garsia introduced a combinatorial interpretation of ${{\mathcal{PW}}}_n$ as certain super-diagonal labelled paths in an $n {\times} n$ square, which has served as the basis of many subsequent investigations. Replacing the square by an $m \times n$ rectangle gives the <span>*(m,n)-parking words*</span> ${{\mathcal{PW}}}_{m}^n$—those words ${{\sf p}}= {{\sf p}}_0 \cdots {{\sf p}}_{n-1} \in [m]^n = \{0,1,\ldots,m{-}1\}^n$ such that $$\Big| \big\{ j : {{\sf p}}_j < i \big\}\Big| \geq \frac{in}{m} \text{ for } 1 \leq i \leq m.\label{eq:parking_def}$$ The classical parking words are recovered as ${{\mathcal{PW}}}_n = {{\mathcal{PW}}}_{n{+}1}^{n}$. The 25 parking words in ${{\mathcal{PW}}}_5^3$ are illustrated on the right side of .

  ----- ----- ----- ----- -----
   000   001   002   011   012
         010   020   101   021
         100   200   110   102
                           120
                           201
                           210
  ----- ----- ----- ----- -----

  ----- ----- ----- ----- ----- ----- -----
   000   001   002   003   011   012   013
         010   020   030   101   021   031
         100   200   300   110   201   301
                                 210   310
                                 120   130
                                 102   103
  ----- ----- ----- ----- ----- ----- -----

A New Characterization of Parking Words
---------------------------------------

Our main result is a new characterization of $(m,n)$-parking words as *piecewise-linear functions* from $\mathbb{R}^m$ to $\mathbb{R}^m$. This characterization is new even for classical parking words.

Define $$\begin{aligned}
 V^m := \Big\{ {{\mathbf{x}}}= (x_0,\ldots,x_{m-1}) \in \mathbb{R}^m : \sum_{i=0}^{m-1} x_i = 0 \text{ and } x_0\leq x_1 \leq \cdots \leq x_{m-1} \Big\}. \end{aligned}$$ A letter $i \in [m]$ acts on $\mathbf{x} \in V^m$ by adding $m$ to $x_i$, subtracting the tuple $\mathbbm{1}_m:=(1,1,\ldots,1)$, and then resorting. A word ${{\sf w}}\in [m]^n$ acts on $\mathbf{x} \in V^m$ by acting by its letters from left to right. The following theorem distinguishes parking words in $[m]^n$ by their action on $V^m$.

The action of ${{\sf w}}\in [m]^n$ on $V^m$ has a fixed point if and only if ${{\sf w}}$ is an $(m,n)$-parking word. More precisely, the action of ${{\sf w}}\in [m]^n$ on $V^m$:

-   has a <span>**unique**</span> fixed point iff ${{\sf w}}\in {{\mathcal{PW}}}_m^n$ and $\gcd(m,n)=1$;

-   has <span>**infinitely many**</span> fixed points iff ${{\sf w}}\in {{\mathcal{PW}}}_m^n$ and $\gcd(m,n)> 1$; and

-   has <span>**no**</span> fixed points iff ${{\sf w}}\in [m]^n \setminus {{\mathcal{PW}}}_m^n$.

\[thm:park\_char\]

The motivation for  comes from generalizations of the space of diagonal coinvariants and the zeta map on parking functions, as we now explain.

Coinvariants and the Symmetric Group
------------------------------------

The Hilbert series for the space of coinvariants is the generating function for two important statistics on the $n!$ permutations in ${{\mathfrak{S}}}_n$: $$\mathrm{Hilb}\left({{\mathbb{C}}}[{{\mathbf{x}}}_n] / \langle {{\mathbb{C}}}[{{\mathbf{x}}}_n]_+^{{{\mathfrak{S}}}_n} \rangle; q\right) = \sum_{w \in {{\mathfrak{S}}}_n} q^{{{\mathsf{inv}}}(w)} = \sum_{w \in {{\mathfrak{S}}}_n} q^{{{\mathsf{maj}}}(w)},\label{eq:coinv}$$ where ${{\mathbb{C}}}[{{\mathbf{x}}}_n]$ is shorthand for a polynomial ring in $n$ variables and $\langle {{\mathbb{C}}}[{{\mathbf{x}}}_n]_+^{{{\mathfrak{S}}}_n} \rangle$ is the ideal of ${{\mathbb{C}}}[{{\mathbf{x}}}_n]$ generated by symmetric polynomials with no constant term.

Artin gave a basis for this space using the code of a permutation to reflect the first generating function of  @artin1944galois, while Garsia and Stanton found a basis using the descents of a permutation to explain the second @garsia1984group.

A statistic with the same distribution as ${{\mathsf{inv}}}$ or ${{\mathsf{maj}}}$ is eponymously named <span>*mahonian*</span> @macmahon1913indices, but Foata gave the first bijection sending one statistic to the other @foata1968netto. Exploiting the fact that this bijection preserves descents of the inverse permutation, Foata and Schützenberger later found an involution that *interchanges* ${{\mathsf{inv}}}$ and ${{\mathsf{maj}}}$ @foata1978major.

Diagonal Coinvariants
---------------------

The study of the space of diagonal coinvariants originated with Garsia and Haiman; its relationship to parking words was first suggested by Gessel @haiman1994conjectures [@garsia1996remarkable]. More precisely, Carlsson and Mellit's recent proof of the shuffle conjecture @haglund2005combinatorial [@carlsson2015proof; @haglund2017lecture] implies the long-suspected fact that the bigraded Hilbert series of the space of diagonal coinvariants is encoded as a positive sum over the $(n{+}1)^{n{-}1}$ parking words ${{\mathcal{PW}}}_n$ @haiman2002vanishing [@haglund2005conjectured]:[^1]

$$\mathrm{Hilb}\left({{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n] / \langle {{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n]_+^{{{\mathfrak{S}}}_n} \rangle; q,t\right) = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_n} q^{{{\mathsf{dinv}}}({{\sf p}})} t^{{{\mathsf{area}}}({{\sf p}})},\label{eq:diagonal_coinvariants}$$

where $q$ records the degree of the variables ${{\mathbf{x}}}_n$, $t$ the degree of $\mathbf{y}_n$, and ${{\mathsf{area}}}$ and ${{\mathsf{dinv}}}$ are certain statistics on parking functions. Recently, Carlsson and Oblomkov artfully merged the Artin and Garsia-Stanton bases to give an explicit basis of the space of diagonal coinvariants @carlsson2018affine, explaining the generating function in .

It is known from  that ${{\mathsf{area}}}$ and ${{\mathsf{dinv}}}$ are symmetric, i.e., $$\sum_{{{\sf p}}\in {{\mathcal{PW}}}_n} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})} = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_n} q^{{{\mathsf{dinv}}}({{\sf p}})} t^{{{\mathsf{area}}}({{\sf p}})}.\label{eq:qtsym}$$ However, it is a long-standing open problem to find an involution that interchanges ${{\mathsf{area}}}$ and ${{\mathsf{dinv}}}$—in the style of Foata and Schützenberger's involution for ${{\mathsf{inv}}}$ and ${{\mathsf{maj}}}$—thus combinatorially proving . This problem is still wide open, even for the alternating subspace @carleton [@gillespie2016combinatorial]. As a first step towards this elusive involution, the equidistribution of ${{\mathsf{dinv}}}$ and ${{\mathsf{area}}}$—obtained by setting $t=1$ in —was proven combinatorially by Loehr and Remmel @loehr2004conjectured [@haglund2005conjectured] @haglund2008q [Corollary 5.6.1]:

\[<span>@loehr2004conjectured</span>\] $$\sum_{{{\sf p}}\in {{\mathcal{PW}}}_n} q^{{{\mathsf{area}}}({{\sf p}})} = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_n} q^{{{\mathsf{dinv}}}({{\sf p}})}.$$\[thm:haglund\_loehr\]

This bijection on ${{\mathcal{PW}}}_n$ takes ${{\mathsf{area}}}$ to ${{\mathsf{dinv}}}$, combinatorially proving the symmetry of . It was first understood, generalized, and inverted for the alternating subspace, where it was called called the <span>*zeta map*</span> @krattenthaler2002enumeration [@haglund2003conjectured; @haglund2005conjectured; @garsia2002proof; @haglund2008q; @armstrong2015sweep; @thomas2015sweeping]. It has been rediscovered many times. We review the history of the zeta map in .

Rational Parking Words and the Affine Symmetric Group
-----------------------------------------------------

*We now assume $m$ and $n$ are coprime*. The classical parking words ${{\mathcal{PW}}}_n$, their statistics ${{\mathsf{area}}}$ and ${{\mathsf{dinv}}}$, and the shuffle conjecture have all been (at least combinatorially) generalized to the $(m,n)$-parking words ${{\mathcal{PW}}}_{m}^n$ @bergeron2015compositional [@armstrong2016rational; @gorsky2016affine; @gorsky2015refined; @thiel2016anderson; @gorsky2017rational].

The Fuss $(nk{+}1,n)$ generalization of the story of diagonal coinvariants is due to Garsia and Haiman @haiman1998t [@garsia1996remarkable]. Writing $\mathcal{A}$ for the ideal generated by the alternating polynomials in ${{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n]$, Mellit proved the rational shuffle conjecture in  @mellit2016toric, which implies that $$\text{Hilb}\left(\mathcal{A}^{k-1}/\mathcal{A}^{k-1} {{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n]_+^{{{\mathfrak{S}}}_n}; q,t\right) = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_{kn{+}1}^n} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})}.$$

The more general rational $(m,n)$ version comes from Hikita's study of the Borel-Moore homology of affine type $A$ Springer fibers, which has a natural basis indexed by the $m^{n-1}$ elements of the affine symmetric group $\widetilde{{{\mathfrak{S}}}}_n$ lying inside an $m$-fold dilation of the fundamental alcove @shi1987sign [@haiman1994conjectures; @cellini2002ad; @cherednik2003double; @sommers2003b; @hikita2014affine; @gorsky2016affine; @thiel2016anderson]. Thus, while the space of coinvariants ${{\mathbb{C}}}[{{\mathbf{x}}}_n] / \langle {{\mathbb{C}}}[{{\mathbf{x}}}_n]_+^{{{\mathfrak{S}}}_n} \rangle$ is related to the symmetric group ${{\mathfrak{S}}}_n$, the diagonal coinvariants are related to the affine symmetric group ${{\widetilde{\mathfrak{S}}}}_n$.

There are many bijections from these affine elements to the parking words ${{\mathcal{PW}}}_{m}^n$. Armstrong found natural interpretations of ${{\mathsf{area}}}$ and ${{\mathsf{dinv}}}$ in terms of affine permutations for the Fuss case @armstrong2013hyperplane, and his work was extended to the rational case by Gorsky, Mazin, and Vazirani @gorsky2016affine [@gorsky2017rational]. Gorsky and Negut formulated the rational shuffle conjecture in @gorsky2015refined—that Hikita's polynomial was given by an operator from an elliptic Hall algebra (see also @bergeron2015compositional). This operator formulation leads to a $q,t$-symmetric bivariate polynomial generalizing :[^2] $$\sum_{{{\sf p}}\in {{\mathcal{PW}}}_m^n} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})} = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_m^n} q^{{{\mathsf{dinv}}}({{\sf p}})} t^{{{\mathsf{area}}}({{\sf p}})}. \label{eq:parkinghilb}$$

As a combinatorial proof of $q,t$-symmetry seems out of reach even in the classical $m=n{+}1$ case, the next best thing is the analogue of the equidistribution of . To this end, Gorsky, Mazin, and Vazirani defined a zeta map on ${{\mathcal{PW}}}_m^n$ (a map taking ${{\mathsf{area}}}$ to ${{\mathsf{dinv}}}$), and conjectured that it was a bijection by providing what they believed to be an inverse map. A curious feature of their conjectural inverse is that it appears to *converge* to the correct answer.

As a corollary to our , we prove Gorsky, Mazin, and Vazirani's conjecture and obtain a rational generalization of .

For $m$ and $n$ relatively prime, $$\sum_{{{\sf p}}\in {{\mathcal{PW}}}_{m}^n} q^{{{\mathsf{area}}}({{\sf p}})} = \sum_{{{\sf p}}\in {{\mathcal{PW}}}_{m}^n} q^{{{\mathsf{dinv}}}({{\sf p}})}.$$ \[thm:rat\_sym\]

Outline of the Paper
--------------------

In  we define $(m,n)$-parking words, the action of words in $[m]^n$ on $\mathbb{R}^m$, and prove our characterizations in  using the Brouwer fixed point theorem.

To relate this characterization to parking functions, we introduce some notation. Fixing $(m,n)$ relatively prime, we define $(m,n)$-filters as certain periodic filters of ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ in , and show that equivalence classes of these filters are naturally parameterized by rational $(m,n)$-Dyck paths and balanced $(m,n)$-filters. We define $(m,n)$-filter tuples in  as certain sequences of $(m,n)$-filters, and relate these sequences to labeled $(m,n)$-Dyck paths.

The notion of $(m,n)$-filters allows us to give a new, remarkably simple definition of the zeta map on $(m,n)$-parking words in . We summarize past work on zeta maps in , define the zeta map in , and relate our construction to Loehr and Warrington's sweep map on $(m,n)$-Dyck paths in .

In , we finally turn to the affine symmetric group. After basic definitions in , we use balanced $(m,n)$-filters to give a bijection between $(m,n)$-filter tuples and affine permutations whose inverses lie in the Sommers region in . We use this bijection in  to relate our constructions to the work of Gorsky, Mazin, and Vazirani, showing that our  resolves @gorsky2016affine [Conjecture 1.4].

Acknowledgements {#acknowledgements .unnumbered}
================

We thank Drew Armstrong for the clarity of his exposition, Marko Thiel and Robin Sulzgruber for their input on the history of zeta maps, and Adriano Garsia, Eugene Gorsky, Nick Loehr, Mikhail Mazin, Igor Pak, Monica Vazirani, and Greg Warrington for many inspiring conversations. H.T. was partially supported by the Canada Research Chairs program and an NSERC Discovery Grant.

This research was supported in part by the National Science Foundation under Grant No. NSF PHY17-48958. We also gratefully acknowledge SageDays<span>@</span>ICERM and the Centre de Recherches Mathémathiques.

Words and Actions {#sec:words_and_actions}
=================

Parking Words
-------------

As in the introduction, the <span>*(m,n)-parking words*</span> ${{\mathcal{PW}}}_{m}^n$ are those words ${{\sf p}}= {{\sf p}}_0 \cdots {{\sf p}}_{n-1} \in [m]^n$ such that $$\Big| \big\{ j : {{\sf p}}_j < i \big\}\Big| \geq \frac{in}{m} \text{ for } 1 \leq i \leq m.\label{eq:parking_def2}$$

By definition, any $(m,n)$-parking word is a permutation of the column lengths of a lattice path staying above the main diagonal in an $m \times n$ rectangle, as illustrated in . (Here, by "column lengths," we mean the distances between the top of the rectangle and the horizontal steps of the lattice path.) We write ${{\mathcal{DW}}}_m^n$ for the increasing $(m,n)$-parking words—the <span>*$(m,n)$-Dyck words*</span>—which are in bijection with the set of such lattice paths.

Hyperplanes {#sec:hyperplane_and_functions}
-----------

Although we defer most of the connections between parking words and the affine symmetric group to , we will require the hyperplane arrangement of the affine symmetric group $\widetilde{\mathfrak{S}}_{m}$ immediately. For $0 \leq i,j < m$ and $k \in \mathbb{N}$, we define the hyperplane $$\mathcal{H}^k_{i,j} = \{\mathbf{x} \in {{\mathbb{R}}}^m : x_i-x_j=mk\}$$ to be of <span>*height*</span> $j-i+mk$, so that the <span>*affine simple hyperplanes*</span> $\left\{\mathcal{H}^0_{i,i+1}\right\}_{0\leq i < m-1} \cup \left\{\mathcal{H}^1_{m-1,0}\right\}$ each have height one. We call the set $\left\{\mathcal{H}^0_{i,i+1}\right\}_{0\leq i < m-1}$ the <span>*simple hyperplanes*</span>. Write $$\mathcal{H} =  \bigcup_{\substack{0 \leq i < j < m\\ k \in \mathbb{Z}}} \mathcal{H}^k_{i,j}$$ for the affine hyperplane arrangement of type $\widetilde{\mathfrak{S}}_{m}$ and let $$\mathbb{R}^{m}_t = \left\{{{\mathbf{x}}}\in \mathbb{R}^m : \sum_{i=0}^{m-1} x_i = t \right\} \cong {{\mathbb{R}}}^{m-1}.$$ The closure of each connected region of ${{\mathbb{R}}}^m_t \setminus \mathcal{H}$ is called an <span>*alcove*</span>. For $0 \leq i < m$, write $\mathbf{e}_i$ for the $i$th standard basis vector of ${{\mathbb{R}}}^m$. The set of alcoves is permuted under translations by $m\mathbf{e}_i-\mathbbm{1}_m$ and under reflections in any hyperplane $\mathcal{H}_{i,j}^k$. We define the norm of an $m$-tuple ${{\mathbf{x}}}\in {{\mathbb{R}}}^m_t$ to be $$|{{\mathbf{x}}}|:=\sum_{0\leq i<j< m} (x_j-x_i)^2.$$

A fundamental domain for the natural action of $\mathfrak{S}_m$ on $\mathbb{R}^m$ is given by those points whose coordinates weakly increase. Define the cone $$V^m_t := \Big\{ {{\mathbf{x}}}\in \mathbb{R}^m_t : x_0\leq x_1 \leq \cdots \leq x_{m-1} \Big\}$$ and $V^m:=V^m_0$. We may <span>*rebalance*</span> an element of $V^m_{t_1}$ to an element of $V^m_{t_2}$ by adding the appropriate multiple of $\mathbbm{1}_m$. \[def:space\_and\_norm\]

Actions of Words
----------------

For each $i \in [m]$, we define piecewise linear transformations on ${{\mathbb{R}}}^m_t\setminus \mathcal H$ and on $V^m_t$.

A letter $i \in [m]$ acts on $\mathbf{x} \in {{\mathbb{R}}}^m_t \setminus \mathcal{H}$ by adding $m$ to the $i$th smallest coordinate of $\mathbf{x}$ and subtracting the tuple $\mathbbm{1}_m$. The letter $i$ acts on $\mathbf{x} \in  V^m_t$ in the same way, but with a final resorting step at the end. A word ${{\sf w}}\in [m]^n$ acts on $\mathbf{x} \in {{\mathbb{R}}}^m_t \setminus \mathcal{H}$ or $\mathbf{x} \in V^m_t$ by acting by its letters from left to right. \[def:action\]

More precisely, writing $\mathbf{y}:=\mathrm{sort}(\mathbf{x})$ for the increasing rearrangement of a point $\mathbf{x} \in {{\mathbb{R}}}^m_t$, $$\begin{aligned}
 \label{eq:action_letter}
 i(\mathbf{x}) &:= \mathbf{x}+\mathbf{e}_j-\mathbbm{1}_m \text{ for } \mathbf{x} \in {{\mathbb{R}}}^m_t \setminus \mathcal{H} \text{ if } x_j=\mathbf{y}_i, \text{ and }\\
 i(\mathbf{x}) &:= \mathrm{sort}(\mathbf{x}+\mathbf{e}_i-\mathbbm{1}_m) \text{ for } \mathbf{x} \in V^m_t.
 \end{aligned}$$

An example of the action on ${{\mathbb{R}}}^3_6 \setminus \mathcal{H}$ is given in .[^3]

![An orbit of the action of the letters $\textcolor{red}{0}$, $\textcolor{blue}{1}$, and $\textcolor{green}{2}$ on ${{\mathbb{R}}}^3_6 \setminus \mathcal{H}$. Acting by $\textcolor{red}{0}$ adds 3 to the smallest coordinate and subtracts $\mathbbm{1}_3$; acting by $\textcolor{green}{2}$ adds 3 to the largest coordinate and subtracts $\mathbbm{1}_3$; and acting by $\textcolor{blue}{1}$ adds 3 to the coordinate that is neither largest nor smallest and subtracts $\mathbbm{1}_3$. For formatting, we have written $\overline{i}$ for $-i$ and suppressed commas and parentheses; thus, the string $\overline{2}53$ stands for the point with coordinates $(-2,5,3)$.<span data-label="fig:parking_on_perm_classes"></span>](parkinggraph3all1.pdf){width=".8\textwidth"}

The action of a letter $i \in [m]$ on $V_t^m$ is the restriction to $V_t^m$ of a piecewise-linear function from ${{\mathbb{R}}}^m_t \cong {{\mathbb{R}}}^{m-1}$ to $V_t^m$ that sends alcoves to alcoves. By , the letter $i$ acts on ${{\mathbf{x}}}\in {{\mathbb{R}}}^m_t$ by the translation ${{\mathbf{x}}}+ m\mathbf{e}_i - \mathbbm{1}_m$, and the final resorting of the coordinates into increasing order may be interpreted geometrically by folding once along the simple hyperplane $\mathcal{H}^0_{i,i+1}$, and then folding again as needed along simple hyperplanes until all points lie in the cone $V_t^m$.

\[rem:action\] The action of a word ${{\sf w}}\in [m]^n$ on $V^m$ sends alcoves to alcoves and only decreases distances between points: $|\mathbf{x}-\mathbf{y}|\geq |{{\sf w}}(\mathbf{x})-{{\sf w}}(\mathbf{y})|$.

The conclusion of the lemma is evident from the geometric description of the action of a letter.

Affine Dimension
----------------

We say that a subset $X \subseteq V^m$ is <span>*of affine dimension $k$*</span> if it is a convex set contained in an affine subspace of dimension $k$ and contains an open ball in that affine subspace. In particular, $X$ is of affine dimension $0$ if it consists of a single fixed point. Note that affine dimension is not defined for an arbitrary subset of $V^m$; to say that a subset is of affine dimension $k$ is to make a strong statement about the kind of subset it is.

For ${{\sf w}}\in [m]^n$, define $${{\mathrm{Fix}}}({{\sf w}}):=\big\{{{\mathbf{x}}}\in V^m : {{\sf w}}({{\mathbf{x}}})={{\mathbf{x}}}\big\}$$ to be the set of points that are fixed under ${{\sf w}}$.

Fix ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ and write $d:=\gcd(m,n)$. We will prove  in  by showing that ${{\mathrm{Fix}}}({{\sf p}})$ is of affine dimension $d-1$. For now, we prove that ${{\mathrm{Fix}}}({{\sf p}})$ is convex and is contained in an affine subspace of dimension $d-1$.

${{\mathrm{Fix}}}({{\sf p}})$ is convex. \[lem:convex\]

Let ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ and suppose ${{\mathbf{x}}},\mathbf{y} \in {{\mathrm{Fix}}}({{\sf p}})$. Since the application of ${{\sf p}}$ only decreases distances, the line between them is fixed.

Let $\gcd(m,n)=d$, ${{\sf p}}\in {{\mathcal{PW}}}_m^n$, and suppose ${{\mathbf{x}}}\in {{\mathrm{Fix}}}({{\sf p}})$. Then the multiset of coordinates $\{x_i\}_{i=0}^{m-1}$ can be partitioned into disjoint multisets, each of which is of size $m/d$ and of the form $\{a+kd+b_km\}_{k=0}^{m/d-1}$. \[lem:ad\]

Up to rebalancing, the action of each letter of ${{\sf p}}$ increases one coordinate of ${{\mathbf{x}}}$ by $m$, but the effect of the entire parking word is to send $x_i$ to $x_i + n$. Since each individual entry changes by a multiple of $m$, it does not change modulo $m$. This means that the multiset of remainders of $x_i {\operatorname{mod}}m$ must be fixed under addition of $n$, so it must also be fixed under addition of $\gcd(n,m)=d$.

\[lem:contained\] Let $\gcd(m,n)=d\geq 1$ and ${{\sf p}}\in {{\mathcal{PW}}}_m^n$. Then ${{\mathrm{Fix}}}({{\sf p}})$ is contained in an affine subspace of dimension $d-1$.

Let ${{\mathbf{x}}}\in{{\mathrm{Fix}}}({{\sf p}})$, and let ${{\mathbf{y}}}\in{{\mathrm{Fix}}}({{\sf p}})$ be another fixed point in a small ball around ${{\mathbf{x}}}$. By , the coordinates of ${{\mathbf{y}}}$ can be partitioned into $d$ disjoint multisets of size $m/d$, each of which consists of a set of residues mod $m$ which are fixed under addition of $d$. Because ${{\mathbf{y}}}$ is close to ${{\mathbf{x}}}$, the partition we have found for the coordinates of ${{\mathbf{y}}}$ also works for the coordinates of ${{\mathbf{x}}}$. For each of the parts in the partition, there is therefore some offset such that adding this offset to the coordinates of ${{\mathbf{x}}}$ in that part, yields the coordinates of ${{\mathbf{y}}}$ in that part. These offsets must add up to zero, since the sum of the entries of ${{\mathbf{x}}}$ and ${{\mathbf{y}}}$ are assumed to be the same. This shows that ${{\mathbf{y}}}$ lies in an affine subspace of dimension $d-1$ which also contains ${{\mathbf{x}}}$.

In principle, if we chose a different ${{\mathbf{y}}}'\in{{\mathrm{Fix}}}({{\sf p}})$ near ${{\mathbf{x}}}$, we could obtain a different affine subspace (corresponding to a different way of partitioning the coordinates of ${{\mathbf{x}}}$). However, convexity would then imply that the line between ${{\mathbf{y}}}$ and ${{\mathbf{y}}}'$ is also in ${{\mathrm{Fix}}}({{\sf p}})$, and this includes points which are not on any affine subspace of the above form, which is impossible. Thus all the points in ${{\mathrm{Fix}}}({{\sf p}})$ near ${{\mathbf{x}}}$ lie in a single affine subspace.

By convexity, any point in ${{\mathrm{Fix}}}({{\sf p}})$ lies in the same affine subspace.

A New Characterization of Parking Words {#sec:new_char}
=======================================

In this section we prove , distinguishing parking words in the set of all words in $[m]^n$ using the action of a word on $V^m$.

\[def:touch\] For ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ and $1 \leq i < m$, define $i$ to be a <span>*touch point*</span> of ${{\sf p}}$ if $$\Big|\big\{j : {{\sf p}}_j<i\big\}\Big|=i\frac{n}{m}.$$

Note that we do not count $0$ or $m$ as touch points, so that when $n$ and $m$ are coprime, no ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ has a touch point.

We break the proof of  into five parts. Let ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ and $d:=\gcd(m,n)$.

-   : if ${{\sf p}}$ has no touch points, then it has a fixed point.

-   : if $d=1$, then ${{\sf p}}$ has a unique fixed point.

-   : if ${{\sf p}}$ has no touch points, then its fixed point space is bounded of affine dimension $d-1$.

-   : if ${{\sf p}}$ has a touch point, then it has infinitely many fixed points, of arbitrarily large norm.

-   : if ${{\sf w}}\in [m]^n \setminus {{\mathcal{PW}}}_m^n$, then it has no fixed points.

Parking words without touch points
----------------------------------

The action of ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ on $V^m$ has a fixed point when ${{\sf p}}$ has no touch point. \[lem:rp\_fixed\]

We want to show that $|{{\sf p}}({{\mathbf{x}}})|<|{{\mathbf{x}}}|$ for $|{{\mathbf{x}}}|>N$, provided $N$ is sufficiently large (that is, parking contracts). By , the Brouwer fixed point theorem can then be invoked on the $(m-1)$-ball $$\left\{{{\mathbf{x}}}\in \mathbb{R}^m : \sum_{i=0}^{m-1} x_i = 0, |{{\mathbf{x}}}|\leq N\right\}$$ to guarantee a fixed point.

We first consider the case that the $x_i$ are sufficiently separated that each "resort" step does nothing—that is, the actions of ${{\sf p}}$ on ${{\mathbf{x}}}$ as an element of ${{\mathbb{R}}}^m_0 \setminus \mathcal{H}$ and as an element of $V^m$ coincide. For $0\leq i <m$, let $$q_{i} = \Big| \big\{ j : {{\sf p}}_j = i\big\} \Big|$$ be the number of occurrences of $i$ in the $(m,n)$-parking word ${{\sf p}}$. The change in the norm produced by applying ${{\sf p}}$ to ${{\mathbf{x}}}\in V^m$ is the difference

$$\begin{gathered}
\sum_{0 \leq i<j< m} \left[ (x_i+mq_i-x_j-mq_j)^2 - (x_i-x_j)^2 \right] \\
=\sum_{0 \leq i<j<m}m^2(q_i-q_j)^2 + \sum_{i=0}^{m-1} 2m^2 q_i x_i -2\left(\sum_{i=0}^{m-1} x_i\right)\left( \sum_{i=0}^{m-1} q_i\right).\label{eq:pdiff}\end{gathered}$$

Of the three terms on the right-hand side of , the first sum depends only on ${{\sf p}}$. The third vanishes because we have assumed that $\sum_i x_i =0$. We want to show that the second sum on the right-hand side $$\sum_{i=0}^{m-1} 2m^2 q_i x_i$$ is sufficiently negative to dominate the first, provided $|{{\mathbf{x}}}|$ is big enough. We will do this by showing that we can add a sequence of positive numbers to the second sum to make it zero.

Suppose that $x_0=x_1=\dots=x_{b-1}$ (with $b$ maximal) and $x_{m-1}=x_{m-2}=\dots=x_{m-c}$ (with $c$ maximal). If we increase each of the $b$ minimal coordinates of ${{\mathbf{x}}}$ by $c\alpha$ and decrease each of the $c$ maximal coordinates of ${{\mathbf{x}}}$ by $b\alpha$, we have not changed the average value of ${{\mathbf{x}}}$. On the other hand, the value of $\sum_i q_i x_i$ changes by

$$\sum_{i=0}^{b-1} \alpha c q_i -  \sum_{i=m-c}^{m-1} \alpha b q_i.\label{eq:pdiff2}$$

By —because ${{\sf p}}$ is an $(m,n)$-parking word—the first term of  is greater than $\alpha cb\frac{n}{m}$, while the second term is less than $\alpha cb\frac{n}{m}$. Thus, changing the values of ${{\mathbf{x}}}$ in this way increases the sum $\sum_i q_i x_i$.

Choose $\alpha$ maximal so that, in increasing the $b$ minimal coordinates and decreasing the $c$ maximal coordinates, none of the values changed pass any other values of ${{\mathbf{x}}}$. We call this a <span>*step*</span>. Since at least one of $b$ or $c$ increases, after a finite number of steps, we will have all entries of ${{\mathbf{x}}}$ at zero and the value of the sum $\sum_i q_i x_i$ will also be zero. But since we increased the value of the sum at each step, its initial value was negative.

In fact, we can bound the initial value of $\sum_i q_i x_i$ away from 0 by approximating its change across all steps. For $b,c<m$, we have $$\begin{aligned}
\left(\sum_{i=0}^{i=b-1} q_i\right) - \frac{bn}{m} &\geq \frac{1}{m} \hspace{2em} \text{ and} \\ \frac{cn}{m} - \left(\sum_{i=m-c}^{i=m-1}q_i\right) &\geq \frac{1}{m},\end{aligned}$$ since both left-hand sides are strictly positive (because of our assumption that ${{\sf p}}$ has no touch points) and can be expressed as a rational number with denominator $m$. Therefore, $$\sum_{i=0}^{b-1} \alpha c q_i -  \sum_{i=m-c}^{m-1} \alpha b q_i \geq \frac{\alpha c}{m} + \frac{\alpha b}{m}.\label{eq:approx}$$ To approximate $\sum_i q_i x_i$, we bound the two terms on the right-hand side of  over the entire process which moves all the $x_i$ to zero.

Since $\alpha c$ is the amount that each of the minimal $x_i$'s were moved during each step, the sum of $\alpha c/m$ over all steps is $1/m$ times the total amount the minimal coordinates are increased over the whole process. But this begins at $x_0$ and terminates at $0$, so the total amount they change by is $-x_0$ and the sum of the first term on the right-hand side of  over the whole process is $-x_0/m$. Similarly, the sum of the second term on the right-hand side of  over the whole process is $x_{m-1}/m$. We obtain the bound $$\sum_{i=0}^{m-1} 2m^2 q_i x_i \leq 2m(x_0-x_{m-1}),$$ which we can make as negative as we like by requiring $|{{\mathbf{x}}}|$ to be sufficiently large.

We now consider the case that the resorting is not necessarily trivial—that is, the action on ${{\mathbf{x}}}$ as an element of ${{\mathbb{R}}}^m_0 \setminus \mathcal{H}$ and as an element of $V^m$ do *not* necessarily coincide. Fix a sorted tuple ${{\mathbf{x}}}$ and distinguish this tuple as living in ${{\mathbb{R}}}^m_0 \setminus \mathcal{H}$ or $V^m$ by writing ${{\mathbf{x}}}_U \in {{\mathbb{R}}}^m_0 \setminus \mathcal{H}$ and ${{\mathbf{x}}}_V \in V^m$. Write $$\begin{aligned}
 {{\mathbf{x}}}_U^{(j)} &:= {{\sf p}}_0{{\sf p}}_1\cdots{{\sf p}}_{j-1}({{\mathbf{x}}}_U) \text{ and} \\ {{\mathbf{x}}}_V^{(j)} &:={{\sf p}}_0{{\sf p}}_1\cdots{{\sf p}}_{j-1}({{\mathbf{x}}}_V).\end{aligned}$$ We note that after applying a single letter $i$ to ${{\mathbf{x}}}_U$ and ${{\mathbf{x}}}_V$, the difference between any coordinate of ${{\mathbf{x}}}_U$ and the same coordinate of ${{\mathbf{x}}}_V$ is less than $m$. By induction, corresponding coordinates of ${{\mathbf{x}}}_U^{(j)}$ and ${{\mathbf{x}}}_V^{(j)}$ differ by at most $mj$.

On the other hand, for any tuple ${{\mathbf{y}}}$, applying a single letter $i$ to ${{\mathbf{y}}}_U$ or ${{\mathbf{y}}}_V$, we compute $$\begin{aligned}
|i({{\mathbf{y}}}_U)|-|{{\mathbf{y}}}_U| = |i({{\mathbf{y}}}_V)|-|{{\mathbf{y}}}_V| &= \sum_{\substack{0\leq j < m\\ j\ne i}} \Big[ (y_i+m - y_j)^2 - (y_i-y_j)^2\Big] \\
&= (m-1)m^2 +2m\sum_{\substack{0\leq j < m\\ j\ne i}} (y_i-y_j) \\ &= (m-1)m^2+2m^2y_i.\label{eq:diffdiff}\end{aligned}$$

By telescoping, we can now bound the difference $|{{\sf p}}({{\mathbf{x}}}_U)|-|{{\sf p}}({{\mathbf{x}}}_V)|$:

$$\begin{aligned}
|{{\sf p}}({{\mathbf{x}}}_U)|-|{{\sf p}}({{\mathbf{x}}}_V)| &= \sum_{j=0}^{n-1} \left(|{{\mathbf{x}}}_U^{(j+1)}|-|{{\mathbf{x}}}_U^{(j)}|\right)-\left(|{{\mathbf{x}}}_V^{(j+1)}|-|{{\mathbf{x}}}_V^{(j)}|\right) \\ &\leq \sum_{j=0}^{n-1} 2m^3 j = n(n-1)m^3,\end{aligned}$$

using our analysis that corresponding coordinates in ${{\mathbf{x}}}_U^{(j)}$ and ${{\mathbf{x}}}_V^{(j)}$ differ by at most $mj$. This quantity is still a constant in the fixed parameters $n$ and $m$, so we can overcome it by requiring that $|{{\mathbf{x}}}|$ be sufficiently large.

We conclude that the second term of the right-hand side of  dominates the first if $|{{\mathbf{x}}}|>N$ for $N$ sufficiently large, so that $|{{\sf p}}({{\mathbf{x}}})|<|{{\mathbf{x}}}|$ for $|{{\mathbf{x}}}|>N$.

In the case $\gcd(m,n)=1$, , together with our previous results, suffices to show that the set of fixed points is of affine dimension 0 (i.e., consists of a single point).

Let $\gcd(m,n)=1$ and ${{\sf p}}\in {{\mathcal{PW}}}_m^n$. Then ${{\mathrm{Fix}}}({{\sf p}})$ is of affine dimension 0. In particular, $|{{\mathrm{Fix}}}({{\sf p}})|=1$. \[lem:rp\_unique\]

We now show that ${{\mathrm{Fix}}}({{\sf p}})$ is of affine dimension $d-1$ for $d=\gcd(m,n)$ in the case that ${{\sf p}}$ has no touch points.

Let $\gcd(m,n)=d\geq 1$ and ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ with no touch points. Then ${{\mathrm{Fix}}}({{\sf p}})$ is bounded of affine dimension $d-1$. \[lem:nrp\_fixed0\]

${{\mathrm{Fix}}}({{\sf p}})$ is bounded, since we showed in  that $|{{\sf p}}({{\mathbf{x}}})|<|{{\mathbf{x}}}|$ for $|x|>N$ for some large $N$.

Let $F$ be a face of the affine arrangement $\mathcal{H}$ such that for any $G$ having $F$ as a face, we have $G\cap{{\mathrm{Fix}}}({{\sf p}})=F\cap{{\mathrm{Fix}}}({{\sf p}})$. Suppose, seeking a contradiction, that $F$ is of codimension $c\geq 1$. Consider the action of ${{\sf p}}$ on a small sphere $S$ around a point $x$ of ${{\mathrm{Fix}}}({{\sf p}})$ in the plane normal to $F$. Since the sphere is not fixed by ${{\sf p}}$, the action of ${{\sf p}}$ on it is by some non-trivial foldings. The image therefore misses some open ball $B$ in the sphere. Restricting, ${{\sf p}}$ now defines a map from $S\setminus B$ to $S\setminus B$, and by Brouwer's fixed point theorem, it has a fixed point. This contradicts our assumption on $F$. Thus there must be a fixed point ${{\mathbf{x}}}$ not lying on any hyperplane.

divides the set of all coordinates of ${{\mathbf{x}}}$ into $d$ subsets of size $m/d$, where the elements of each set are congruent modulo $d$. Since ${{\mathbf{x}}}$ lies on no hyperplane, no coordinate value modulo $m$ is repeated, so it is unambiguous how to apportion the coordinates into these sets.

Now consider the action of ${{\sf p}}$, omitting rebalancing. Each entry in the multiset of coordinates is changed by a multiple of $d$. Thus the entries in each of the $d$ subsets are permuted among themselves by the action of ${{\sf p}}$. We may translate each family with respect to the others by some small amount without changing the relative order of any coordinates, so all such points are still fixed. This gives us an open ball around ${{\mathbf{x}}}$ in the $(d-1)$-dimensional affine subspace constructed in consisting entirely of fixed points. ${{\mathrm{Fix}}}({{\sf p}})$ is therefore of affine dimension $d-1$.

Fix $(m,n) = (6,9)$ with $d = \gcd(m,n) = 3$. Consider the $(m,n)$-parking word ${{\sf p}}= 020101151$, and note that ${{\sf p}}$ has no touch points.

It is easily verified that ${{\sf p}}$ has a fixed point ${{\mathbf{x}}}=(-3,1,2,4,6,11)$, which modulo $d$ is of the form $(0,1,2,1,0,2)$. Let $$\begin{aligned}
v_0 &= (-3,0,3,3,6,12),\\
v_1 &= (-2,1,1,4,7,10), \text{ and} \\
v_2 &= (-4,2,2,5,5,11).\end{aligned}$$ Then one can check that $\mathrm{Fix}({{\sf p}}) \supseteq \mathrm{conv}(v_0,v_1,v_2).$

Parking words with touch points
-------------------------------

When the parking word has a touch point, we now use  to also produce infinitely many fixed points. These fixed points may now be of arbitrarily large norm.

The action of ${{\sf w}}\in {{\mathcal{PW}}}_m^n$ on $V^m$ has infinitely many fixed points when ${{\sf w}}$ has at least one touch point. The set ${{\mathrm{Fix}}}({{\sf w}})$ has affine dimension $d-1$, and contains fixed points of arbitrarily large norm. \[lem:nrp\_fixed\]

Suppose that $\gcd(m,n)=d\neq 1$ and that ${{\sf w}}$ has $k\geq 1$ touch points. We will break ${{\sf p}}$ into a number of smaller parking words based on its touch points, find the unique fixed points for each of those parking words, and then reassemble them in uncountably many ways to find fixed points for ${{\sf p}}$. To this end, list the $k$ touch points of ${{\sf p}}$ as $m_1,\dots,m_k$ with $$m_0=0<m_1<m_2<\cdots<m_{k}<m=m_{k+1}.$$ For $0\leq j \leq k$, let ${{\sf p}}^{(j)}$ be the (not-necessarily consecutive) subword of ${{\sf p}}$ containing all letters $p$ of ${{\sf p}}$ such that $m_{j}\leq p < m_{j+1}$. Let $n_j$ be the length of ${{\sf p}}^{(j)}$—necessarily a multiple of $n/d$—and note that ${{\sf p}}$ is a shuffle of ${{\sf p}}^{(0)},{{\sf p}}^{(1)},\ldots,{{\sf p}}^{(k-1)}$.

To define smaller parking words, we shift the individual letters of ${{\sf p}}^{(j)}$ by the previous touch point to produce the $(m_j,n_j)$-parking word ${{\sf q}}^{(j)}:= {{\sf p}}^{(j)}-m_{j}$.

We can now use  and the previous case to find ${{\mathbf{x}}}^{(j)} \in V^{m_j}$ that are fixed points for the ${{\sf q}}^{(j)}$. In preparation to reassemble these individual fixed points ${{\mathbf{x}}}^{(j)}$ into a fixed point for ${{\sf p}}$, we scale them to define $${{\mathbf{x}}}^{(j)}_N := \frac{n}{n_j}{{\mathbf{x}}}^{(j)}+N_j$$ for some $N_j \in {{\mathbb{R}}}$. Finally, define ${{\mathbf{x}}}_N \in V^m$ by the concatenation: $${{\mathbf{x}}}_N := \left({{\mathbf{x}}}^{(0)}_N,{{\mathbf{x}}}^{(1)}_N,\ldots,{{\mathbf{x}}}^{(k)}_N\right),$$ and then rebalancing so that the sum is 0.

We now check that ${{\mathbf{x}}}_N$ is really a fixed point of ${{\sf p}}$, as long as the $N_j$ give sufficient space between the ${{\mathbf{x}}}_N^{(j)}$. Since ${{\sf p}}$ is a shuffle of the ${{\sf p}}^{(j)}$, as long as the individual coordinates of ${{\mathbf{x}}}_N$ do not overlap during the application of the letters of ${{\sf p}}$ (for example, we may take $N_j>mn+N_{j-1}$), we may discuss the action of ${{\sf p}}$ on each component ${{\mathbf{x}}}_N^{(j)}$ separately. On ${{\mathbf{x}}}_N^{(j)}$, then, only the subword ${{\sf p}}^{(j)}$ of ${{\sf p}}$ will act; the only difference from its usual action on ${{\mathbf{x}}}^{(j)}$ is that (as a piece of the larger parking word ${{\sf p}}$) it adds $m$ rather than $m_j$—but we have compensated for this by the scaling factor $\frac{n}{n_j}$.

We illustrate the proof of . Let $(m,n)=(9,12)$ so that $d=3$, and let ${{\sf p}}= 531030678631$. Then there are 2 touch points of ${{\sf p}}$: $m_1=3$ and $m_2=6$, so that $${{\sf p}}^{(0)} = 1001, {{\sf p}}^{(1)}=5333, \text{ and } {{\sf p}}^{(2)} = 6786$$ and $${{\sf q}}^{(0)} = 1001, {{\sf q}}^{(1)}=2000, \text{ and } {{\sf q}}^{(2)} = 0120.$$ Fixed points for ${{\sf q}}^{(j)}$ are $${{\mathbf{x}}}^{(0)} = (-2,0,2),\, {{\mathbf{x}}}^{(1)} = (-1,0,1), \text{ and } {{\mathbf{x}}}^{(2)} = (-2,-1,3),$$ so that $${{\mathbf{x}}}^{(0)}_N = (-6,0,6),\, {{\mathbf{x}}}^{(1)}_N = (-3,0,3)+N_2, \text{ and } {{\mathbf{x}}}^{(2)}_N = (-6,-3,9)+N_3,$$ and before rebalancing $${{\mathbf{x}}}_N = \left(-6,0,6,-3+N_2,N_2,3+N_2,-6+N_3,-3+N_3,9+N_3\right).$$

When $N_2>21$ and $N_3>21+N_2$, we see that portion of ${{\sf p}}$ corresponding to ${{\sf p}}^{(j)}$ acts only on the $3j-2$, $3j-1$, and $3j$th coordinates of ${{\mathbf{x}}}$.

Non-parking words
-----------------

Repeated application of ${{\sf w}}\in [m]^n \setminus {{\mathcal{PW}}}_m^n$ on $V^m$ sends every point to infinity. In particular, ${{\sf w}}$ has no fixed points. \[lem:no\_fixed\]

We show that repeated application of ${{\sf w}}$ sends some point to infinity. Since ${{\sf w}}$ only decreases the distance between two points, this implies that every point is sent to infinity, so that ${{\sf w}}$ has no fixed points.

Suppose that ${{\sf w}}\in [m]^n \setminus {{\mathcal{PW}}}_m^n$ is not a parking function because it has too many numbers that are at least $k$, and choose $k$ maximal. Let $${{\mathbf{x}}}= \left( x_0,x_1,\ldots,x_{m-1}\right) \in V^m$$ be a vector with sum 0. We claim that the result of applying ${{\sf w}}$ to ${{\mathbf{x}}}$ has the effect of increasing the difference between the average value of $x_k,\dots,x_{m-1}$ and the average value of $x_0,\dots,x_{k-1}$ by a fixed quantity. Thus, after enough applications of ${{\sf w}}$, the value of $x_m$ will be arbitrarily large.

In the course of applying ${{\sf w}}$ to ${{\mathbf{x}}}$ there are two ways that the difference between the average value of $x_0,\dots,x_{k-1}$ and the average value of $x_{k},\dots,x_{m-1}$ changes. One is as a result of adding $m$ to an entry corresponding to an element of ${{\sf w}}$. By the assumption on ${{\sf w}}$, these steps have the property that, on average, a more than proportionate number of these steps are applied to the entries $x_k,\dots,x_{m-1}$, which therefore increases the difference between the average values by a fixed positive amount. The other way that the difference between the averages increases is in the resort step. If an element in $x_1,\dots,x_{k-1}$ is increased far enough that it moves into the top $m-k$ elements, then it is resorted into one of these positions. Whenever this happens, this also increases the difference between the average values.

Summary
-------

We obtain  as a corollary of  and  . Examples for $m=3$ are given in .

The remainder of this paper is devoted to explaining the coprime case in more detail, explicitly identifying the isolated fixed points of parking words as the centers of alcoves of dominant affine permutations whose inverses lie in the Sommers region. It would be desirable to explicitly identify the regions of fixed points in the non-relatively prime case. We note that in the special $(m,mk)$ case when the fixed regions are full dimensional, Gorsky, Mazin, and Vazirani have recently identified the set of fixed regions of an $(m,mk)$-parking word with the dominant regions in the $k$-Shi arrangement of $\widetilde{\mathfrak{S}}_{m}$ @gorsky2017rational [Section 3.4] (compare with ).

\[scale=1.3\] (0,0) – (1.5,2.6); (0,0) – (-1.5,2.6); (-.5,.866) – (.5,.866); (-.5,.866) – (.5,2.6); (.5,.866) – (-.5,2.6); (a) at (0,0.577) <span>$123$</span>; (b) at (0,1.155) <span>$024$</span>; (e) at (0,2.3094) <span>$\overline{2}26$</span>; (d) at (.5,1.443) <span>$015$</span>; (c) at (-.5,1.443) <span>$\overline{1}34$</span>; (a3) at (-3,-.866) <span>$\begin{array}{ccc} 000 &010 &100 \\ 110 &200 &210\end{array}$</span>; (a4) at (3,-.866) <span>$\begin{array}{cccc} 0000 &0010 &0100 &0110 \\ 0200& 0210& 1000& 1010 \\ 1100 &2000& 2010& 2100\end{array}$</span>; (b3) at (-3,.2887) <span>$\begin{array}{ccc} 001 &020 &101 \\ 110 &200 &210\end{array}$</span>; (b4) at (3,.2887) <span>$\begin{array}{ccc} 0001 &0020 &0101 \\ 1001 &1020 &1200\end{array}$</span>; (c3) at (-3,1.44) <span>$\begin{array}{ccc}011 &021 &101\\ 110 &201 &210\end{array}$</span>; (d3) at (-3,2.59) <span>$\begin{array}{ccc}002 &020 &102\\ 120 &200 &210\end{array}$</span>; (c4) at (3,2.59) <span>$\begin{array}{cccc}0011 &0021 &0201 &2001\end{array}$</span>; (d4) at (3,1.44) <span>$\begin{array}{cccc}0002 &0102 &0120 &1002\end{array}$</span>; (e3) at (-3,3.753) <span>$\begin{array}{ccc}012 &021 &102 \\120 &201 &210\end{array}$</span>; (e4) at (3,3.753) <span>$\begin{array}{c}0012\end{array}$</span>; (a3) – (a); (b3) – (b); (a4) – (a); (b4) – (b); (c3) – (c); (c4) – (c); (d3) – (d); (d4) – (d); (e3) – (e); (e4) – (e);

Parking Filters {#sec:parking_functions}
===============

<span>**For the rest of the paper, we fix $m$ and $n$ relatively prime.**</span>

In this section, we define the combinatorial objects—generally thought of as Dyck paths and labeled Dyck paths—that we will use to compute the zeta map defined in . These objects are all well-known; our main contribution is the simplicity of our definition of the zeta map on parking functions in , and its relation with affine permutations in .

Filters {#sec:filters}
-------

Fix $m$ and $n$ relatively prime, and label the point $(i,j) \in {{\mathbb{Z}}}\times {{\mathbb{Z}}}$ by its <span>*level*</span> $$\ell(i,j)=(i,j) \bullet (m,n).$$ If we draw the levels of points in the plane, rows correspond to residue classes modulo $m$, while columns correspond to residue classes modulo $n$. Any fixed row and column intersect in a unique point, and the Chinese remainder theorem ensures that the levels are distinct modulo $mn$ in any contiguous $n \times m$ rectangle. A portion of the levels of ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ for $(m,n)=(3,4)$ and $(3,5)$ is illustrated in .

An <span>*$(m,n)$-filter*</span> ${{\mathfrak{i}}}$ is an order filter of ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ such that whenever the point $(i,j)$ is in ${{\mathfrak{i}}}$, then all $(i',j')$ for which $\ell(i',j')=\ell(i,j)$ are also in ${{\mathfrak{i}}}$. We write ${{\mathcal{F}}}_m^n$ for the set of all $(m,n)$-filters. \[def:filters\]

Interchanging the copies of ${{\mathbb{Z}}}$ in ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ gives a bijection between the set of $(m,n)$-filters and the set of $(n,m)$-filters; we call this the <span>*$(m{\leftrightarrow}n)$-bijection*</span>. An $(m,n)$-filter ${{\mathfrak{i}}}$ is specified in three natural ways:

-   $\ell({{\mathfrak{i}}}) := \{ \ell(i,j) : (i,j) \in {{\mathfrak{i}}}\}$, the set of all its levels,

-   $m({{\mathfrak{i}}}) := \{ \min_{(i,j) \in {{\mathfrak{i}}}} \ell(i,j) : j \in \mathbb{Z} \}$, i.e., the set formed by taking, for each row, the minimal level of a point in that row which is also in ${{\mathfrak{i}}}$. or

-   $n({{\mathfrak{i}}}) := \{ \min_{(i,j) \in {{\mathfrak{i}}}} \ell(i,j) : i \in \mathbb{Z} \}$, i.e., the set formed by taking, for each column, the minimal level of a point in that column which is also in ${{\mathfrak{i}}}$.

Note that $m({{\mathfrak{i}}})$ consists of $m$ integers, one from each congruence class mod $m$, while $n({{\mathfrak{i}}})$ consists of $n$ integers, one from each congruence class mod $n$.

An example of  is given in . It is useful to identify the sets $m({{\mathfrak{i}}})$ and $n({{\mathfrak{i}}})$ with the corresponding sorted lists.

; iin <span>0,...,3</span><span> in <span>0,...,4</span><span> ; <span>(-,i) rectangle (+.5,+.5);</span>; </span>; </span>; (,0) – (0,); (-.5,-.5) grid (+.5,+.5); iin <span>0,...,3</span><span> in <span>0,...,4</span><span> ; ; (-,i) node; </span>; </span>;

; iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; <span>(-,i) rectangle (+.5,+.5);</span>; </span>; </span>; (,0) – (0,); (-.5,-.5) grid (+.5,+.5); iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; ; (-,i) node; </span>; </span>;

We say that ${{\mathfrak{i}}},{{\mathfrak{i}}}'\in {{\mathcal{F}}}_m^n$ are <span>*equivalent*</span> if ${{\mathfrak{i}}}= {{\mathfrak{i}}}'+(x,y)$ for some $(x,y) \in {{\mathbb{Z}}}\times {{\mathbb{Z}}},$ and write ${{\widetilde{\mathcal{F}}}}_m^n$ for the set of equivalence classes of ${{\mathcal{F}}}_m^n$.

Define a directed graph $\mathfrak{F}_m^n$ on ${{\widetilde{\mathcal{F}}}}_m^n$ with a directed edge from $\widetilde{{{\mathfrak{i}}}} \in {{\widetilde{\mathcal{F}}}}_m^n$ to $\widetilde{{{\mathfrak{i}}}}' \in {{\widetilde{\mathcal{F}}}}_m^n$ iff there is some ${{\mathfrak{i}}}' \in \widetilde{{{\mathfrak{i}}}}'$ and some ${{\mathfrak{i}}}\in \widetilde{{{\mathfrak{i}}}}$ such that $\ell({{\mathfrak{i}}}')$ can be obtained from $\ell({{\mathfrak{i}}})$ by removing a single level from ${{\mathfrak{i}}}$. We write $\widetilde{{{\mathfrak{b}}}}_m^n$ for the equivalence class containing the $(m,n)$-filters generated by a single level. \[def:directed\_graph\]

The $(m{\leftrightarrow}n)$-bijection gives an isomorphism between $\mathfrak{F}_m^n$ and $\mathfrak{F}_n^m$. The graphs $\mathfrak{F}_3^4$ and $\mathfrak{F}_3^5$ are illustrated in .

Representatives
---------------

In this section, we introduce two natural representatives of the equivalence classes of $(m,n)$-filters:

-   Dyck $(m,n)$-filters, in bijection with Dyck paths and most useful to relate our constructions to the standard combinatorial objects (); and

-   balanced $(m,n)$-filters, which will be essential for specifying affine permutations (, , and )

### Dyck filters {#sec:dyck}

We define a first representative of the equivalence classes in ${{\widetilde{\mathcal{F}}}}_m^n$. These representatives are usually defined in the literature as lattice paths staying above or below a diagonal, and we show how our definition recovers this interpretation in .

A <span>*Dyck $(m,n)$-filter*</span> is an $(m,n)$-filter ${{\mathfrak{d}}}$ such that $$\min_{(i,j) \in {{\mathfrak{d}}}} \ell(i,j) = 0.$$ We write ${{\mathcal{DF}}}_m^n$ for the set of all Dyck $(m,n)$-filters. \[def:dyck\_filter\]

In particular, for ${{\mathfrak{d}}}\in {{\mathcal{DF}}}_m^n$, $\min(n({{\mathfrak{d}}}))=\min(m({{\mathfrak{d}}}))=0.$ Note that the $(m{\leftrightarrow}n)$-bijection restricts to a bijection between ${{\mathcal{DF}}}_m^n$ and ${{\mathcal{DF}}}_n^m$.

We relate  to the set of <span>*$(m,n)$-Dyck paths*</span>—those lattice paths from $(0,0)$ to $(-n,m)$ using north steps $(0,1)$ and west steps $(-1,0)$ and staying above the line $(x,y)\bullet(m,n)=0$. The boundary of an $(m,n)$-filter of ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ traces out a periodic path in the plane. This periodicity allows us to restrict to the contiguous $n \times m$ rectangle with corners at level $0$ without losing information, giving ${{\mathcal{DF}}}_m^n$ the standard geometric interpretation as $(m,n)$-Dyck paths. This is illustrated in . \[rem:dyck\_pic\]

; iin <span>0,...,3</span><span> in <span>0,...,4</span><span> ; <span>(-,i) rectangle (+.5,+.5);</span>; </span>; </span>; ; in <span>1,1,0,1,1,0,0</span><span> ; ; i=i; =; </span>; (,0) – (0,); (-.5,-.5) grid (+.5,+.5); iin <span>0,...,3</span><span> in <span>0,...,4</span><span> ; ; (-,i) node; </span>; </span>;

; iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; <span>(-,i) rectangle (+.5,+.5);</span>; </span>; </span>; ; in <span>1,1,1,0,1,0,1,0</span><span> ; ; i=i; =; </span>; (,0) – (0,); (-.5,-.5) grid (+.5,+.5); iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; ; (-,i) node; </span>; </span>;

All $(m,n)$-filters whose boundaries trace out the same path—up to translation—are equivalent to the same Dyck $(m,n)$-filter.

Each equivalence class in ${{\widetilde{\mathcal{F}}}}_m^n$ contains a unique element of ${{\mathcal{DF}}}_m^n$.

To a $(m,n)$-filter ${{\mathfrak{i}}}$ we associate the unique equivalent Dyck $(m,n)$-filter ${{\mathfrak{d}}}$ obtained by translating ${{\mathfrak{i}}}$ so that it touches the line $(x,y)\bullet(m,n)=0$, but does not go below.

There is a directed path in $\mathfrak{F}_m^n$ from the equivalence class $\widetilde{{{\mathfrak{b}}}}_m^n$ to any other equivalence class. \[lem:connected\]

Starting from $\widetilde{{{\mathfrak{b}}}}_m^n$, the directed graph $\mathfrak{F}_m^n$ contains a copy of the distributive lattice (whose Hasse diagram is thought of as a directed graph) consisting of the $(m,n)$-Dyck paths ordered by inclusion. (Note that this is via the identification with Dyck paths which lie below the diagonal, not above it.)

The following enumeration is a well-known application of the cycle lemma.

$$\left|{{\widetilde{\mathcal{F}}}}_m^n\right| = \left|{{\widetilde{\mathcal{F}}}}_n^m\right| = \frac{1}{n+m}\binom{n+m}{n}.$$ \[thm:dyck\_paths\]

### Balanced Filters {#sec:balanced}

We define a second representative of the equivalence classes in ${{\widetilde{\mathcal{F}}}}_m^n$. These objects appear to have been much less studied, and will allow us to relate ${{\widetilde{\mathcal{F}}}}_m^n$ and affine permutations.

We call an $(m,n)$-filter ${{\mathfrak{b}}}\in {{\mathcal{F}}}_m^n$ satisfying $$\sum_{ i \in m({{\mathfrak{b}}})} i = \binom{m+1}{2} \text{ and } \sum_{ j \in n({{\mathfrak{b}}})} j = \binom{n+1}{2}$$ a <span>*balanced $(m,n)$-filter*</span>. We write ${{\mathcal{BF}}}_m^n$ for the set of balanced $(m,n)$-filters \[prop:balanced1\]

It is a simple check that this set is nonempty—it contains the $(m,n)$-filter ${{\mathfrak{b}}}_m^n$ generated by the points with level $\ell=\frac{1+m+n-mn}{2}$.

Each equivalence class in ${{\widetilde{\mathcal{F}}}}_m^n$ contains a unique element of ${{\mathcal{BF}}}_m^n$. Furthermore, for ${{\mathfrak{b}}}\in {{\mathcal{F}}}_m^n$, $$\sum_{ i \in m({{\mathfrak{b}}})} i = \binom{m+1}{2} \text{ if and only if } \sum_{ j \in n({{\mathfrak{b}}})} j = \binom{n+1}{2}.$$ \[prop:balanced2\]

Suppose we have an $(m,n)$-filter ${{\mathfrak{i}}}$ satisfying both conditions. Removing a minimal element from ${{\mathfrak{i}}}$ to make a new $(m,n)$-filter ${{\mathfrak{i}}}'$ has the effect of adding $m$ to the sum of elements of $m({{\mathfrak{i}}})$ and the effect of adding $n$ to the sum of the elements of $n({{\mathfrak{i}}})$. The $(m,n)$-filter defined by $\ell({{\mathfrak{i}}}'')=\ell({{\mathfrak{i}}}')-1$ therefore also satisfies both conditions. The conclusions now follow from .

The five balanced $(3,4)$-filters are illustrated in .

Filter Tuples {#sec:tuples}
-------------

We define $(m,n)$-filter tuples as certain sequences of $(m,n)$-filters, and we explain in  how $(m,n)$-filter tuples are in bijection with the usual definition of parking functions as labeled Dyck paths.

An <span>*$(m,n)$-filter tuple*</span> ${{\mathfrak{p}}}$ is a tuple of $n{+}1$ $(m,n)$-filters $${{\mathfrak{p}}}=\left({{\mathfrak{p}}}^{(0)},{{\mathfrak{p}}}^{(1)},\ldots,{{\mathfrak{p}}}^{(n)}\right)$$ such that:

-   $m({{\mathfrak{p}}}^{(i+1)})=\left(m({{\mathfrak{p}}}^{(i)})\setminus \{p_{i}\}\right)\cup \{p_{i}+m\}$ for $0 \leq i < n$, and

-   $m({{\mathfrak{p}}}^{(0)})+n = m({{\mathfrak{p}}}^{(n)})$.

We write $\mathcal{T}_m^n$ for the set of all $(m,n)$-filter tuples and we say that two $(m,n)$-filters tuples ${{\mathfrak{p}}}_1$ and ${{\mathfrak{p}}}_2$ are <span>*equivalent*</span> if ${{\mathfrak{p}}}_1^{(i)}={{\mathfrak{p}}}_2^{(i)}+(x,y)$ for all $0\leq i \leq n$ and some fixed $(x,y) \in \mathbb{Z}\times\mathbb{Z}$. \[def:parking\]

is illustrated in ; the caption is explained in the next few paragraphs.

An $(m,n)$-filter tuple may be equivalently thought of as a cycle of length $n$ in the directed graph $\mathfrak{F}_m^n$ of  with a choice of initial representative in the first equivalence class, as in .

illustrates a cycle in $\mathfrak{F}_3^5$: start at the vertex labeled by the balanced $(3,5)$-filter ${{\mathfrak{b}}}$ with $m({{\mathfrak{b}}})=[-1,3,4]$ and then follow the red edges. This cycle corresponds to the $(3,5)$-filter tuple in . \[rem:park\_cycles\]

An $(m,n)$-filter tuple ${{\mathfrak{p}}}$ is specified by the sequence of the $n$ levels removed: $$n({{\mathfrak{p}}}) = [p_0,p_1,\ldots,p_{n-1}].\label{eq:n_of_park}$$ The first condition of  ensures that $n({{\mathfrak{p}}})$ is a permutation of $n({{\mathfrak{p}}}^{(0)})$, such that levels in the same residue class modulo $m$ appear in increasing order.

We call ${{\mathfrak{p}}}\in \mathcal{T}_m^n$ <span>*parking*</span> if ${{\mathfrak{p}}}^{(0)} \in {{\mathcal{DF}}}_m^n$ and write ${{\mathcal{PT}}}_m^n$ for the set of all parking $(m,n)$-filter tuples. We call ${{\mathfrak{p}}}\in \mathcal{T}_m^n$ <span>*balanced*</span> if ${{\mathfrak{p}}}^{(0)}\in {{\mathcal{BF}}}_m^n$ and write ${{\mathcal{BT}}}_m^n$ for the set of all balanced $(m,n)$-filter tuples. show that any $(m,n)$-filter tuple is equivalent to a unique parking $(m,n)$-filter tuple and a unique balanced $(m,n)$-filter tuple.

We relate  to the definition of <span>*$(m,n)$-parking paths*</span>—$(m,n)$-Dyck paths whose $n$ horizontal edges are labeled $1,2,\ldots,n$, such that levels in the same row increase from left to right. Fix ${{\mathfrak{p}}}\in {{\mathcal{PT}}}_m^n$, so that ${{\mathfrak{p}}}^{(0)}$ may be thought of as an $(m,n)$-Dyck path by . Number each horizontal step in this path by the order in which its left endpoint is removed in ${{\mathfrak{p}}}$. Since ${{\mathfrak{p}}}^{(i)}$ is an $(m,n)$-filter, points in the same row must be removed in order—this recovers the condition on levels for parking paths, as illustrated in  (which corresponds to the parking $(m,n)$-filter tuple of ). Thus, we may represent a parking $(m,n)$-filter as an $(m,n)$-parking path. \[rem:park\_pic\]

; iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; <span>(-,i) rectangle (+.5,+.5);</span>; </span>; </span>; ; in <span>2,3,4,0,1,5,0,0</span><span> ; ; i=i; =; </span>; (,0) – (0,); (-.5,-.5) grid (+.5,+.5); iin <span>0,...,3</span><span> in <span>0,...,5</span><span> ; ; (-,i) node; </span>; </span>;

The following enumerative result follows from the cycle lemma, and is given geometric meaning in .

\[<span>@armstrong2016rational [Corollary 4],@aval2015interlaced</span>\] $$\left|{{\mathcal{PT}}}_m^n\right| = m^{n-1} \text{ and } \left|{{\mathcal{PT}}}_n^m\right| = n^{m-1}.$$ \[thm:number\_parking\_functions\]

The Zeta Map {#sec:combinatorial_zeta}
============

After reviewing the state of the art for zeta maps in , we use the combinatorial objects of  to define two (different) bijections between parking $(m,n)$-filter tuples and $(m,n)$-parking words ()—the first map is trivially a bijection, but we only conclude that the second map is a bijection as a corollary of  in . The composition of these two bijections defines the zeta map for rational parking words ().

In , we show that our zeta map on rational words recovers Armstrong, Loehr, and Warrington's sweep map on rational Dyck paths using a canonical injection of Dyck paths inside parking paths.

Context and History {#sec:zeta_history}
-------------------

The classical zeta map $\zeta$ is a bijection from $(n{+}1,n)$-Dyck paths to themselves developed by Garsia, Haglund, and Haiman to explain the equidistribution on Dyck paths of $(\mathsf{area},\mathsf{bounce})$ and $(\mathsf{dinv},\mathsf{area})$. The statistic $\mathsf{bounce}$ is due to Haglund, while $\mathsf{dinv}$ is due to Haiman; we shall not review their definitions here. This equidistribution expresses the agreement of the two formulas on the righthand side of the following combinatorial expansion of the Hilbert series of the *alternating* subspace of the space of diagonal coinvariants @garsia2002proof [@haiman2002vanishing; @carlsson2015proof]:

$$\begin{aligned}
\mathrm{Hilb}\left(\left({{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n] / \langle {{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n]_+^{{{\mathfrak{S}}}_n} \rangle\right)^\epsilon; q,t\right) &=\sum_{\mathsf{d} \in {{\mathcal{DW}}}_{n{+}1}^n} q^{{{\mathsf{area}}}(\mathsf{d})} t^{{{\mathsf{bounce}}}(\mathsf{d})}\\ &= \sum_{\mathsf{d} \in {{\mathcal{DW}}}_{n{+}1}^n} q^{{{\mathsf{dinv}}}(\mathsf{d})} t^{{{\mathsf{area}}}(\mathsf{d})},\end{aligned}$$

With the proper conventions[^4], the map $\zeta$ explains the equidistribution in the sense that ${{\mathsf{area}}}(\mathsf{d})={{\mathsf{dinv}}}(\zeta(\mathsf{d}))$ and ${{\mathsf{bounce}}}(\mathsf{d}) = {{\mathsf{area}}}(\zeta(\mathsf{d}))$.

From the point of view of lattice path combinatorics, the Dyck paths encoding the Hilbert series of the alternating subspace of the space of diagonal coinvariants are much simpler than the parking paths encoding the full Hilbert series of the space of diagonal coinvariants. Presumably due to this difference in complexity, the definition and study of the zeta map was restricted to Dyck paths at first @haglund2003conjectured [@garsia2002proof], and its extension by Haglund and Loehr @haglund2005conjectured[^5] and by Loehr and Remmel @loehr2004conjectured to parking paths only came later:

$$\begin{aligned}
\mathrm{Hilb}\left({{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n] / \langle {{\mathbb{C}}}[{{\mathbf{x}}}_n,\mathbf{y}_n]_+^{{{\mathfrak{S}}}_n} \rangle; q,t\right) &=\sum_{{{\sf p}}\in {{\mathcal{PW}}}_{n{+}1}^n} q^{{{\mathsf{area}}}({{\sf p}})} t^{\mathsf{pmaj}({{\sf p}})}\\ &= \sum_{{{\sf p}}\in {{\mathcal{PW}}}_{n{+}1}^n} q^{{{\mathsf{dinv}}}({{\sf p}})} t^{{{\mathsf{area}}}({{\sf p}})},\end{aligned}$$

where $\mathsf{pmaj}$ is a generalization of $\mathsf{bounce}$, ${{\mathsf{area}}}({{\sf p}})={{\mathsf{dinv}}}(\zeta({{\sf p}}))$, and $\mathsf{pmaj}({{\sf p}}) = {{\mathsf{area}}}(\zeta({{\sf p}}))$. When restricted to Dyck paths, this result generalizes the zeta map on Dyck paths @haglund2008q [Exercise 5.7]; see also our .

As Dyck paths and parking paths were generalized to the Fuss $(kn+1,n)$, Dogolon $(kn-1,n)$, and rational $(m,n)$ cases, extensions of the zeta map were again first defined on Dyck paths, and only later for parking paths. The definition of zeta on rational parking words turns out to be surprisingly simple, as we show in . This definition appears in @gorsky2016affine—but in a different language that we postpone to .

The table in  contains a historical summary of the definitions of zeta, where for brevity we have suppressed some details as to the exact generality of the maps involved—in the column with heading "Type," we use "Dyck" or "Parking" to refer to the unlabeled or labeled case of lattice paths, respectively. (We recommend @armstrong2015sweep for a thorough survey of the literature on zeta maps defined on lattice paths, at least when the dimensions of the bounding rectangle are coprime.)

<span>|l|c|c|c|r|</span> Authors & Reference & Type & Generality & Proof of Bijectivity\

  ---------
  Garsia
  Haiman
  Haglund
  ---------

& @garsia2002proof & Dyck & $(n{+}1,n)$ & @garsia2002proof\

  -------
  Loehr
  -------

& @loehr2005conjectured & Dyck & $(kn{+}1,n)$ & @loehr2005conjectured\

  ---------
  Haglund
  Loehr
  ---------

& @haglund2005conjectured & Parking & $(n{+}1,n)$ & @haglund2005conjectured\

  --------
  Gorsky
  Mazin
  --------

&

  -------------------------
   @gorsky2013compactified
   @gorsky2014compactified
  -------------------------

& Dyck & coprime $(m,n)$ &

  --------------------------------------------
    @gorsky2013compactified for $(kn{\pm}1,n)$
                           @thomas2015sweeping
                   <span>**This paper**</span>
  --------------------------------------------

\

  ------------
  Amstrong
  Loehr
  Warrington
  ------------

& @armstrong2015sweep & Dyck & $N$-dim. box & @thomas2015sweeping\

  ----------
  Gorsky
  Mazin
  Vazirani
  ----------

& @gorsky2016affine & Parking & coprime $(m,n)$ &

  --------------------------------------------
    @gorsky2013compactified for $(kn{\pm}1,n)$
                   <span>**This paper**</span>
  --------------------------------------------

\

  ----------
  Gorsky
  Mazin
  Vazirani
  ----------

& @gorsky2017rational & Dyck & $(m,n)$ & @gorsky2017rational\

The Zeta Map {#sec:zeta}
------------

We define the zeta map using two bijections $A,B$ from parking $(m,n)$-filter tuples to $(m,n)$-parking words. The zeta map is then defined to be the map $\zeta := B \circ A^{-1}$.

Following Gorsky, Mazin, and Vazirani, the $q$ and $t$ statistics may be read off these $(m,n)$-parking words @armstrong2013hyperplane [@gorsky2016affine]: $$\begin{aligned}
{{\mathsf{area}}}({{\mathfrak{p}}})&:=\frac{(n-1)(m-1)}{2}-\sum_{i=0}^{n-1} A({{\mathfrak{p}}})_i, \\ {{\mathsf{dinv}}}({{\mathfrak{p}}})&:=\frac{(n-1)(m-1)}{2}-\sum_{i=0}^{n-1} B({{\mathfrak{p}}})_i.\end{aligned}$$

### Area (A) {#sec:mapa}

Our first map is a simple application of the interpretation in  of an $(m,n)$-filter tuple as an $(m,n)$-parking path.

Define $A: {{\mathcal{PT}}}_m^n \to {{\mathcal{PW}}}_m^n$ to be the $(m,n)$-parking word recording the column lengths (in the order of the edge labels) of the $(m,n)$-parking path associated to ${{\mathfrak{p}}}$ by . \[def:parka\]

It is easy to see that $A$ may be equivalently defined by $$n({{\mathfrak{p}}})=[p_1,p_2,\ldots,p_n] \xmapsto{A} \left[ap_1, ap_2,\ldots, ap_n \right] {\operatorname{mod}}m,$$ where $a n = -1 {\operatorname{mod}}m$.

The parking $(3,5)$-filter tuple ${{\mathfrak{p}}}\in {{\mathcal{PT}}}_3^5$ encoded by the $(3,5)$-parking path in  is mapped to the $(3,5)$-parking word $$A({{\mathfrak{p}}})=10001$$ (there is one gray box in the columns containing the horizontal edges with labels 1 and 5, and no gray boxes in the other columns). We may also compute it using the word $n({{\mathfrak{p}}})$ from : $$n({{\mathfrak{p}}}) = [4,0,3,6,7] \mapsto [1\cdot 4,1\cdot 0,1\cdot 3,1\cdot 6,1\cdot 7] {\operatorname{mod}}3 = [1,0,0,0,1],$$ since $1 \cdot 5 = -1 {\operatorname{mod}}3$. We compute $${{\mathsf{area}}}({{\mathfrak{p}}}) = \frac{2\cdot 4}{2}-\left(1+0+0+0+1\right) = 2.$$

On the other hand, we compute the $(5,3)$-parking word for the element ${{\mathfrak{p}}}\in {{\mathcal{PT}}}_5^3$ with $n({{\mathfrak{p}}})=[0,7,5]$: $$n({{\mathfrak{p}}}) = [0,7,5] \mapsto [3\cdot 0,3\cdot 7,3\cdot 5] {\operatorname{mod}}5 = [0,1,0],$$ since $3 \cdot 3 = -1 {\operatorname{mod}}5$. \[ex:mapa\]

It is immediate from  that  is a bijection from ${{\mathcal{PT}}}_m^n$ to ${{\mathcal{PW}}}_m^n$.

### Dinv ($B$) {#sec:mapb}

Define $B: {{\mathcal{PT}}}_m^n \to [m]^n$ by recording the relative order in the word $m({{\mathfrak{p}}}^{(i-1)})$ of the number $p_{i}$ removed for $1\leq i \leq n$. That is, we define a word ${{\sf w}}={{\sf w}}_1\cdots {{\sf w}}_n \in [m]^n$ by ${{\sf w}}_{i}=j$ if $p_{i}$ is the $j$th smallest number in $m({{\mathfrak{p}}}^{(i-1)})$. \[def:parkb\]

As in , we compute $m({{\mathfrak{p}}}^{(i)})$ for each $(3,5)$-filter in  to be $$[-1,\mathbf{3},4] \to [\mathbf{-1},4,6] \to [\mathbf{2},4,6] \to [4,\mathbf{5},6] \to [4,\mathbf{6},8] \to [4,8,9],$$ where we haven't rebalanced. Recording the relative order of the elements removed (marked in bold above) gives the $(3,5)$-parking word $$B({{\mathfrak{p}}})=10011.$$ We compute $${{\mathsf{dinv}}}({{\mathfrak{p}}}) = \frac{2\cdot 4}{2}-\left(1+0+0+1+1\right) = 1.$$ \[ex:b1\]

It is not immediately obvious that  really does produce $(m,n)$-parking words.

The map $B$ is a bijection from ${{\mathcal{PT}}}_m^n$ to ${{\mathcal{PW}}}_m^n$. \[thm:b\_is\_bij\]

Let ${{\mathfrak{p}}}\in{{\mathcal{PT}}}_m^n$. For $0 \leq i\leq n$, we define a point ${{\mathbf{x}}}^{(i)} \in V^m$ by $\mathbf{x}^{(i)} = m({{\mathfrak{p}}}^{(i)}) $, and adding a multiple of $\mathbbm{1}$ so that the sum of the elements in ${{\mathbf{x}}}^{(i)}$ is zero (since every element in $ m({{\mathfrak{p}}}^{(i)})$ changes by the same amount, their relative order is preserved). So the action of $B({{\mathfrak{p}}})$ on ${{\mathbf{x}}}^{(0)} \in V^m$ (as defined in ) is recorded by the sequences ${{\mathbf{x}}}^{(i)}$. Finally, ${{\mathbf{x}}}^{(0)} = {{\mathbf{x}}}^{(n)}$ because ${{\mathfrak{p}}}$ is a parking $(m,n)$-tuple. In particular, we have shown that the word $B({{\mathfrak{p}}})$ has a fixed point. Now  tells us that $B({{\mathfrak{p}}})$ is a parking word.

Further,  tells us that the fixed point of $B({{\mathfrak{p}}})$ is unique. Therefore, from $B({{\mathfrak{p}}})$, we can identify its unique fixed point ${{\mathbf{x}}}^{(0)}$, from which we can reconstruct ${{\mathbf{x}}}^{(i)}$ for all $i$, and thus ${{\mathfrak{p}}}^{(i)}$ for all $i$. That is to say, from $B({{\mathfrak{p}}})$, we can reconstruct ${{\mathfrak{p}}}$. This implies that the map $B$ is an injection from ${{\mathcal{PT}}}_m^n$ to ${{\mathcal{PW}}}_m^n$. We have already established that the map $A$ is a bijection between these two sets, so the fact that $B$ is an injection means that it must also be surjective.

Given an $(m,n)$-filter tuple ${{\mathfrak{p}}}$, *the* fixed point for $B({{\mathfrak{p}}})$ in $V^m$ is the word $m({{\mathfrak{p}}}^{(0)})$—up to addition of a multiple of $\mathbbm{1}$.

Continuing  (and recalling ), balancing each $(3,5)$-filter ${{\mathfrak{p}}}^{(i)}$ gives $$[-1,\mathbf{3},4] \to [\mathbf{-2},3,5] \to [\mathbf{0},2,4] \to [1,\mathbf{2},3] \to [0,\mathbf{2},4]\to [-1,3,4].$$ Balancing doesn't change the relative order of the elements, and thinking of ${{\mathfrak{p}}}^{(0)}$ as an element of $V_6^3$, we observe that ${{\mathfrak{p}}}^{(0)}$ is a fixed point for the action of $B({{\mathfrak{p}}})=10011$.

### The Zeta Map ($A \mapsto B$)

The zeta map $\zeta$ sends the first method of associating an $(m,n)$-parking word to a parking $(m,n)$-filter tuple in  to the second in . By , we conclude that $\zeta$ is a bijection.

The <span>*zeta map*</span> is the bijection from ${{\mathcal{PW}}}_m^n$ to itself defined by $$\begin{aligned}
\zeta: {{\mathcal{PW}}}_m^n &\to {{\mathcal{PW}}}_m^n \\
\mathsf{p} & \mapsto B \circ A^{-1}(\mathsf{p})\end{aligned}$$ \[def:zetamap\]

Examples are illustrated in .

   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$
  ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- -----------------------
            123                     012                     000              $\overline{1}34$               001                     011                     015                     011                     002
            132                     021                     010              $\overline{1}43$               010                     021                     105                     101                     102
            213                     102                     100              $4\overline{1}3$               100                     201                     150                     110                     120
            231                     120                     110                     024                     020                     001              $\overline{2}26$               000                     012
            312                     201                     200                     042                     002                     020                                                           
            321                     210                     210                     204                     200                     101                                                           

$$\begin{aligned}
\sum_{{{\mathfrak{d}}}\in {{\mathcal{DF}}}_4^3} q^{{{\mathsf{area}}}({{\mathfrak{d}}})} t^{{{\mathsf{dinv}}}({{\mathfrak{d}}})} = \begin{array}{cccc}
 0 & 0 & 0 & 1 \\
 0 & 1 & 1 & 0 \\
 0 & 1 & 0 & 0 \\
 1 & 0 & 0 & 0 \\
\end{array}, \sum_{{{\sf p}}\in {{\mathcal{PT}}}_4^3} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})} = \begin{array}{cccc}
 1 & 2 & 2 & 1 \\
 2 & 3 & 1 & 0 \\
 2 & 1 & 0 & 0 \\
 1 & 0 & 0 & 0 \\
\end{array}\end{aligned}$$

   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$   $n({{\mathfrak{p}}})$   $A({{\mathfrak{p}}})$   $B({{\mathfrak{p}}})$
  ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- ----------------------- -----------------------
            123                     031                     000                     024                     012                     001              $\overline{2}35$               001                     012                    $015$                    030                     002
            132                     013                     010                     042                     021                     020              $\overline{2}53$               010                     031                    $051$                    003                     030
            312                     103                     200                     204                     102                     101              $5\overline{2}3$               100                     301                    $105$                    300                     102
            321                     130                     210                     240                     120                     120              $\overline{1}34$               020                     011              $\overline{1}16$               011                     003
            213                     301                     100                     402                     201                     300              $\overline{1}43$               002                     021              $1\overline{1}6$               101                     103
            231                     310                     110                     420                     210                     310              $3\overline{1}4$               200                     201              $16\overline{1}$               110                     130
                                                                                                                                                                                                                             $\overline{3}27$               000                     013

$$\begin{aligned}
\sum_{{{\sf p}}\in {{\mathcal{DW}}}_5^3} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})} &= \begin{array}{ccccc}
 0 & 0 & 0 & 0 & 1 \\
 0 & 0 & 1 & 1 & 0 \\
 0 & 1 & 1 & 0 & 0 \\
 0 & 1 & 0 & 0 & 0 \\
 1 & 0 & 0 & 0 & 0 \\
\end{array},
\sum_{{{\sf p}}\in {{\mathcal{PW}}}_5^3} q^{{{\mathsf{area}}}({{\sf p}})} t^{{{\mathsf{dinv}}}({{\sf p}})} &= \begin{array}{ccccc}
 0 & 1 & 2 & 2 & 1 \\
 1 & 4 & 3 & 1 & 0 \\
 2 & 3 & 1 & 0 & 0 \\
 2 & 1 & 0 & 0 & 0 \\
 1 & 0 & 0 & 0 & 0 \\
\end{array}\end{aligned}$$

The Sweep Map {#sec:sweep}
-------------

In this section, we relate the zeta map on $(m,n)$-parking words to the sweep map on $(m,n)$-Dyck paths.

Having fixed $m$ and $n$ coprime, define the <span>*level*</span> of a step of a lattice path in ${{\mathbb{Z}}}\times {{\mathbb{Z}}}$ to be the level of its north/west endpoint. In @armstrong2015sweep, Armstrong, Loehr, and Warrington defined the <span>*sweep map*</span> on $(m,n)$-Dyck paths by *sorting* the steps of a given path by their levels.[^6] See  for an example. One can visualize this procedure geometrically as a *sweep* of the line ${\mathcal H}_{\mathbf{a},k}:=\{\mathbf{x}:\mathbf{x} \bullet (m,n)=k\}$ up from $k=0$ to $k=\infty$, as illustrated in  for $(m,n)=(4,7)$.

$\xmapsto{{{\sf sweep}}}$

. \[fig:sweep\]

$$\begin{aligned}
{4}
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw1-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw1-2.pdf}}} \\ \textcolor{red}{0} \ 6 \ 7 \ 9 \end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw2-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw2-2.pdf}}}\\ \textcolor{red}{4} \ 6 \ 7 \ 9\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw3-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw3-2.pdf}}}\\ \textcolor{red}{6} \ 7 \ 8 \ 9\end{tabular}} &&\to \\
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw4-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw4-2.pdf}}}\\ \textcolor{red}{\bf 7} \ 8 \ 9 \ 10\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw5-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw5-2.pdf}}} \\ {\bf 7} \ \textcolor{red}{8} \ 9 \ 10\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw6-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw6-2.pdf}}}\\ {\bf 7} \ \textcolor{red}{9} \ 10 \ 12\end{tabular}} &&\to \\
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw7-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw7-2.pdf}}}\\ {\bf 7} \ \textcolor{red}{10} \ 12 \ {13}\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{swi-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{swi-2.pdf}}}\\ {\bf 7} \ \textcolor{red}{12} \ 13 \ {14}\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw8-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw8-2.pdf}}}\\ {\bf 7} \ \textcolor{red}{\bf 13} \ 14 \ {16}\end{tabular}} &&\to \\
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw9-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw9-2.pdf}}}\\ {\bf 7} \ {\bf 13} \ \textcolor{red}{\bf 14} \ 16\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw10-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw10-2.pdf}}}\\ {\bf 7} \ {\bf 13} \ {\bf 14} \ \textcolor{red}{\bf 16}\end{tabular}} &&\to
\framebox{\begin{tabular}{c}\raisebox{-0.5\height}{\reflectbox{\includegraphics[width=.12\linewidth]{sw11-1.pdf}}\reflectbox{\includegraphics[width=.12\linewidth]{sw11-2.pdf}}}\\ {\bf 7} \ {\bf 13} \ {\bf 14} \ {\bf 16} \end{tabular}} &&\makebox[\widthof{$\to$}][c]{$.$}\end{aligned}$$

It is not hard to argue that the sweep map sends an $(m,n)$-Dyck path to another $(m,n)$-Dyck path @thomas2015sweeping [Theorem 6.7], but invertibility is considerably more difficult. The sweep map and its various generalizations were first shown to be bijective by Thomas and Williams in @thomas2015sweeping.

There is a canonical injection $$\begin{aligned}
{{\mathcal{DF}}}_m^n &\xhookrightarrow{} {{\mathcal{PT}}}_m^n \\ {{\mathfrak{d}}}&\mapsto {{\mathfrak{p}}}_{{\mathfrak{d}}}, \end{aligned}$$ where ${{\mathfrak{p}}}_{{\mathfrak{d}}}$ is the unique element of ${{\mathcal{PT}}}_m^n$ such that $n({{\mathfrak{d}}}) = n({{\mathfrak{p}}}_{{\mathfrak{d}}})$ (recall that we think of $n({{\mathfrak{d}}})$ as a *sorted* list). We call ${{\mathfrak{p}}}_{{\mathfrak{d}}}$ a <span>*Dyck $(m,n)$-filter tuple*</span>. By replacing ${{\mathfrak{d}}}$ by ${{\mathfrak{p}}}_{{\mathfrak{d}}}$, we may consider ${{\mathcal{DF}}}_m^n$ as a subset of ${{\mathcal{PT}}}_m^n$.

We can rephrase this injection using the interpretation of ${{\mathfrak{d}}}$ as an $(m,n)$-Dyck path and elements of ${{\mathcal{PT}}}_m^n$ as $(m,n)$-parking paths. Thinking of ${{\mathfrak{d}}}$ as an $(m,n)$-Dyck path from $(0,0)$ to $(-n,m)$ (as in ), we label each horizontal edge by the relative order of the level of its left endpoint. This associates a canonical $(m,n)$-parking path to ${{\mathfrak{d}}}$, which corresponds to a parking $(m,n)$-filter tuple ${{\mathfrak{p}}}_{{\mathfrak{d}}}$ by . Note that the lattice path used to compute ${{\sf sweep}}({{\mathfrak{d}}})$ is the same as the (unlabeled) lattice path associated to ${{\mathfrak{p}}}_{{\mathfrak{d}}}$ in , whose column heights are counted by $A({{\mathfrak{p}}}_{{\mathfrak{d}}})$. \[rem:embed\]

The injection of  allows us to relate the zeta and sweep maps as follows.

For ${{\mathfrak{d}}}$ an $(m,n)$-Dyck path, $B({{\mathfrak{p}}}_{{\mathfrak{d}}})$ is an increasing word that records the column heights of ${{\sf sweep}}({{\mathfrak{d}}})$. \[prop:sweep\_and\_zeta\]

We check that $B({{\mathfrak{p}}}_{{\mathfrak{d}}})$ encodes ${{\sf sweep}}({{\mathfrak{d}}})$: by construction of ${{\mathfrak{p}}}_{{\mathfrak{d}}}$, the number $p_i$ being removed when passing from ${{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i-1)}$ to ${{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i)}$ is the minimal level among those levels in $m({{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i-1)})$ which are the levels of horizontal edges. Meanwhile, the levels in $m({{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i)})$ with value less than that minimal horizontal edge level keep track of the vertical steps in the construction of ${{\sf sweep}}({{\mathfrak{d}}})$. The number of such vertical edge levels which are present as we pass from ${{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i-1)}$ to ${{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i)}$ tells us, on the one hand, the height of the $i$-th column in ${{\sf sweep}}({{\mathfrak{d}}})$ and on the other hand the relative order in $m({{\mathfrak{p}}}_{{\mathfrak{d}}}^{(i-1)})$ of $p_i$ (which is what $B$ records). This is illustrated in .

By , since $B: {{\mathcal{PT}}}_m^n \to {{\mathcal{PW}}}_m^n$ is a bijection, we obtain a new proof that the sweep map on $(m,n)$-Dyck paths is invertible.

For $m,n$ coprime, the sweep map on $(m,n)$-Dyck paths is invertible.

\[rem:sweep\_levels\] In @armstrong2015sweep [Section 5.2], Armstrong, Loehr, and Warrington remark that the sweep map can be inverted if the individual levels of the steps on the path specified by ${{\sf sweep}}({{\mathfrak{d}}})$ can be determined. The last two authors gave an algorithm to determine these levels in @thomas2015sweeping.

This strategy of determining levels can be related to the fixed point of a parking word as follows. shows that the fixed point of the (increasing) parking word $B({{\mathfrak{p}}}_{{\mathfrak{d}}})$ encodes the levels of the vertical steps of ${{\sf sweep}}({{\mathfrak{d}}})$. For example, the left path ${{\mathfrak{d}}}$ in  corresponds to the $(m,n)$-filter tuple ${{\mathfrak{p}}}_{{\mathfrak{d}}}$ specified on the left of . Then $m({{\mathfrak{p}}}_{{\mathfrak{d}}}^{(n)})= [7,13,14,16]$ records the levels that should be assigned (from top left to bottom right) to the vertical steps of ${{\sf sweep}}({{\mathfrak{d}}})$, as illustrated on the right of . The remaining levels—corresponding to the horizontal steps (again from top left to bottom right)—are determined from by the word $n({{\mathfrak{p}}}_{{\mathfrak{d}}}^{(0)}) = [0,4,6,8,9,10,12]$.

The Affine Symmetric Group {#sec:affine_symmetric_and_regions}
==========================

In , we interpreted $(m,n)$-parking words as transformations of ${{\mathbb{R}}}^m$. In this section, we recall their standard interpretation as alcoves in ${{\mathbb{R}}}^n$.

The coincidence between the number of regions in the type $\widetilde{{{\mathfrak{S}}}}_n$ Shi arrangement () and the number of $(n{+}1,n)$-parking words has led to many purely combinatorial investigations @stanley1996hyperplane [@stanley1998hyperplane; @athanasiadis1999simple; @armstrong2012shi; @leven2014bijections]. Although many different authors have found many different bijections between Shi regions and parking words, this direction of research culminates in work of Gorsky, Mazin, and Vazirani @gorsky2016affine, who expand upon and generalize Armstrong's work in @armstrong2013hyperplane from the Fuss to the rational level of generality. In this section, we prove several of their conjectures.

We first review the basic combinatorics of $\widetilde{{{\mathfrak{S}}}}_n$ in . We state the simple relationship between parking $(m,n)$-filter tuples and the affine symmetric group in  and . This relationship allows us to define two maps from a generalization of Shi regions (alcoves in the Sommers region) to parking words, which are a restatement of .

The Affine Symmetric Group {#sec:affine_symmetric}
--------------------------

The affine symmetric group $\widetilde{{{\mathfrak{S}}}}_n$ is the group of bijections ${{w}}: {{\mathbb{Z}}}\to {{\mathbb{Z}}}$ such that $$\begin{aligned}
 {{w}}(i+n)&={{w}}(i)+n \text{ and} \\
\sum_{i=1}^n {{w}}(i) &= \binom{n+1}{2}.\end{aligned}$$ We often represent elements of $\widetilde{{{\mathfrak{S}}}}_n$ in (short) one-line notation $${{w}}= \left[{{w}}(1),{{w}}(2),\ldots,{{w}}(n)\right].$$ A <span>*dominant permutation*</span> is an affine permutation ${{w}}$ whose one-line notation increases, so that ${{w}}(1)<{{w}}(2)<\cdots<{{w}}(n)$. An <span>*inversion*</span> of ${{w}}$ is a pair $(i,j)$ with $1 \leq i \leq n$ and $i<j$ such that ${{w}}(i)>{{w}}(j)$. We refer the reader to @lusztig1983some [@gorsky2016affine] for more details.

The one-line notation of affine permutations bijectively corresponds to the alcoves in the affine $\widetilde{\mathfrak{S}}_{n}$ hyperplane arrangement, introduced in .[^7]

\[<span>@gorsky2016affine [Lemma 2.9]</span>\] Each alcove of ${{\mathbb{R}}}^n \setminus \mathcal{H}$ contains a unique point $(x_1,\ldots,x_n)$ that is the one-line notation of an element of $\widetilde{{{\mathfrak{S}}}}_n$. Conversely, each element of $\widetilde{{{\mathfrak{S}}}}_n$ occurs as such a point. \[thm:alcove\_points\]

The alcove labeled by the identity permutation $(1,2,\ldots,n)$ is called the <span>*fundamental alcove*</span> ${{\mathcal{A}}}_0$. An inversion $(i,j)$ of $w\in\widetilde{{{\mathfrak{S}}}}_n$ corresponds to the hyperplane $\mathcal{H}_{i,j'}^k$ that separates the alcove containing the one-line notation for $w$ from ${{\mathcal{A}}}_0$, where $j'=\begin{cases} j {\operatorname{mod}}n & \text{if } j \neq 0 {\operatorname{mod}}n \\ n & \text{otherwise} \end{cases}$ and $k=\frac{1}{n}(j-j')$. The bijection of  between $\widetilde{{{\mathfrak{S}}}}_n$ and the alcoves of ${{\mathbb{R}}}^n \setminus \mathcal{H}$ is illustrated for $n=3$ in . On the other hand,  depicts the the labeling of an alcove by the *inverse* of the corresponding permutation.

![The labeling of alcoves in ${{\mathbb{R}}}^n \setminus \mathcal{H}$ by $\widetilde{{{\mathfrak{S}}}}_3$. The three solid black lines are the hyperplanes $\mathcal{H}_{1,2}^0, \mathcal{H}_{1,3}^0,$ and $\mathcal{H}_{2,3}^0$.<span data-label="fig:perms"></span>](permsall.pdf){width=".75\textwidth"}

![The labeling of alcoves in ${{\mathbb{R}}}^n \setminus \mathcal{H}$ by inverse permutations.<span data-label="fig:invperms"></span>](invpermsall.pdf){width=".75\textwidth"}

The Sommers Region {#sec:sommers}
------------------

For $m$ coprime to $n$, the <span>*Sommers region*</span> ${{\mathcal{S}}}_m^n\subset\mathbb{R}^{n-1}$ is the region bounded by the $n$ affine hyperplanes in $\widetilde{{{\mathfrak{S}}}}_n$ of height $m$. \[def:sommers\]

Note that when $m$ is not coprime to $n$, the hyperplanes of height $m$ do not bound a finite region. By abuse of notation, we shall write ${{w}}\in {{\mathcal{S}}}_m^n$ if ${{w}}$ is an affine permutation labeling an alcove inside ${{\mathcal{S}}}_m^n$. We can detect such affine permutations with the following simple proposition.

\[<span>@gorsky2016affine [Definition 2.14]</span>\] An affine permutation ${{w}}^{-1} \in \widetilde{{{\mathfrak{S}}}}_n$ labels an alcove in the region ${{\mathcal{S}}}_m^n$ iff ${{w}}(i)-{{w}}(j)\neq m$ for all $i<j$. \[prop:affine\_perm\_in\_so\]

### History of the Sommers Region {#sec:history_sommers}

The Sommers region originated in Shi's study of Kazhdan-Lusztig cells of affine Weyl groups @shi2006kazhdan, as we now outline. The collection of affine hyperplanes $$\bigcup_{1 \leq i < j \leq n} \left(\mathcal{H}_{i,j}^0 \cup  \mathcal{H}_{j,i}^1 \right)$$ is called the <span>*Shi arrangement*</span>, and these hyperplanes cut out connected regions called <span>*Shi regions*</span>. Each Kazhdan-Lusztig cell is a union of Shi regions. Following a suggestion of Carter, Shi gave an elegant geometric proof that there are $(n+1)^{n-1}$ Shi regions by showing that the inverses of the permutations labeling the minimal alcoves in the Shi regions coalesce into what has become known as the Sommers region ${{\mathcal{S}}}_{n+1}^n$ @shi1987sign [@sommers2003b].[^8]

There is a Fuss analogue of the Shi arrangement, defined as the hyperplanes $$\bigcup_{\substack{1 \leq i < j \leq n \\ -k \leq s \leq k-1}} \mathcal{H}_{i,j}^s.$$ This arrangement has $(kn+1)^{n-1}$ connected regions—again, the inverses of the minimal alcoves coalesce into the Sommers region ${{\mathcal{S}}}_{kn+1}^n$.

The <span>*fundamental alcove*</span> $\mathcal{A}_0$ in $\widetilde{{{\mathfrak{S}}}}_n$ is the simplex bounded by the affine simple hyperplanes. It turns out that ${{\mathcal{S}}}_m^n$ is congruent to the $m$-fold dilation of the fundamental alcove $m\mathcal{A}_0$—this may be realized by multiplication by the element @gorsky2016affine [Lemma 2.16],@thiel2017strange [Theorem 4.2] $${{w}}_m^n := [\ell,\ell+m,\ldots,\ell+(n-1)m] \in \widetilde{{{\mathfrak{S}}}}_n, \text{ where } \ell=\frac{1+m+n-mn}{2}.\label{eq:wmn}$$

Variations on subarrangements of affine Weyl hyperplane arrangements has led to interesting and surprisingly difficult combinatorics @stanley1996hyperplane [@stanley1998hyperplane; @athanasiadis1998free; @postnikov2000deformations; @armstrong2012shi; @leven2014bijections; @thomas2014cyclic], but outside of $m=kn+1$ there are no hyperplane arrangements whose regions have minimal alcoves given by the inverses of the elements in ${{\mathcal{S}}}_m^n$ @gorsky2016affine [Example 9.2]. Suggestive results exist for $m=kn-1$ using Zaslavsky's theorem enumerating bounded regions of a hyperplane arrangement (or Ehrhart duality) @fishel2010bijection [@fishel2013counting], and some work has been done when $m$ and $n$ are not coprime @gorsky2017rational.

The regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$ are illustrated in .

![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by inverse permutations.<span data-label="fig:sommers"></span>](sommersregion4.pdf "fig:"){width=".45\textwidth"}![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by inverse permutations.<span data-label="fig:sommers"></span>](sommersregion5.pdf "fig:"){width=".45\textwidth"}

### Filters and the Sommers Region {#sec:filters_and_sommers}

To connect $(m,n)$-filters and affine permutations, we define the analogue of the directed graph $\mathfrak{F}_m^n$ in .

Fix ${{w}}^{-1} \in {{\mathcal{S}}}_m^n \subset {{\widetilde{\mathfrak{S}}}}_n$. An <span>*$m$-minimal element*</span> of ${{w}}$ is an element from the set $\{{{w}}(i) : i \in \mathbb{N}\}$ that is minimal in its residue class modulo $m$. We say that an $m$-minimal element of ${{w}}$ is <span>*removable*</span> if it is in the short one-line notation of ${{w}}$—that is, if it is ${{w}}(i)$ for some $1 \leq i \leq n$.

Define a directed graph $\mathfrak{P}_m^n$ with vertex set $$\left\{{{w}}\text{ dominant} : {{w}}^{-1} \in {{\mathcal{S}}}_m^n \right\}$$ and a directed edge between ${{w}}$ and ${{w}}'$ iff the short one-line notation of ${{w}}'$ can be obtained from the short one-line notation of ${{w}}$ by adding $n$ to a removable $m$-minimal element of ${{w}}$, subtracting one from every element, and then resorting. \[def:directed\_graph2\]

Acting as described in  on a removable $m$-minimal element of a dominant ${{w}}$ with ${{w}}^{-1}\in {{\mathcal{S}}}_m^n$ produces another dominant element whose inverse is in ${{\mathcal{S}}}_m^n$.

Suppose that ${{w}}(i)$ is a removable $m$-minimal element, and let ${{w}}'$ be produced as above starting from that element. Clearly ${{w}}'$ is dominant. We now apply the condition of  to ${{w}}'$. The only way a problem could arise would be if there were some $j>n$ with ${{w}}(j)={{w}}(i)+n-m$. But if $j-n<i$, the fact that ${{w}}(j-n)$ is congruent modulo $m$ to ${{w}}(i)$ would violate the $m$-minimality of $i$, while $j-n>i$ would violate the condition of  for ${{w}}$.

\[scale=1.5\] (A) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,0) <span>$[1,2,3,4]$</span>; (D) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,2.5) <span>$[0,1,3,6]$</span>; (E) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,3.5) <span>$[-2,1,4,7]$</span>; (B) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,2.5) <span>$[-1,2,4,5]$</span>; (C) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,1.5) <span>$[0,2,3,5]$</span>; (B) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (C) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (A) to \[bend right\] node\[midway, right\] <span>$1$</span> (C); (B) to node\[midway, above\] <span>$2$</span> (E); (D) – (B) node\[midway, above\] <span>$1$</span>; (C) – (B) node\[midway, below\] <span>$1$</span>; (D) – (C) node\[midway, below\] <span>$0$</span>; (A) to \[bend right\] node\[midway, right\] <span>$2$</span> (D); (E) – (D) node\[midway, above\] <span>$0$</span>; (A) edge\[loop below\]node<span>$0$</span> (A);

\[scale=1.5\] (A) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,0) <span>$[1,2,3]$</span>; (D) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,2.5) <span>$[0,1,5]$</span>; (E) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,3.5) <span>$[-2,2,6]$</span>; (B) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,2.5) <span>$[-1,3,4]$</span>; (C) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,1.5) <span>$[0,2,4]$</span>; (B) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (C) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (A) to \[bend right\] node\[midway, right\] <span>$1$</span> (C); (B) to node\[midway, above\] <span>$2$</span> (E); (D) – (B) node\[midway, above\] <span>$1$</span>; (C) – (B) node\[midway, below\] <span>$1$</span>; (D) – (C) node\[midway, below\] <span>$0$</span>; (A) to \[bend right\] node\[midway, right\] <span>$2$</span> (D); (E) – (D) node\[midway, above\] <span>$0$</span>; (A) edge\[loop below\]node<span>$0$</span> (A);

\[scale=1.5\] (A) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,0) <span>$[1,2,3,4,5]$</span>; (D) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,2.5) <span>$[0,1,3,4,7]$</span>; (D2) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,4) <span>$[-1,1,2,5,8]$</span>; (E) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,5) <span>$[-3,0,3,6,9]$</span>; (B) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,2.5) <span>$[-1,2,3,5,6]$</span>; (B2) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,4) <span>$[-2,1,4,5,7]$</span>; (C) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,1.5) <span>$[0,2,3,4,6]$</span>; (B) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (C) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (A) to \[bend right\] node\[midway, right\] <span>$1$</span> (C); (B2) to node\[midway, above\] <span>$3$</span> (E); (B2) to node\[midway, right\] <span>$0$</span> (C); (C) to node\[midway, left\] <span>$3$</span> (D2); (B) to node\[midway, left\] <span>$2$</span> (B2); (D) – (B) node\[midway, above\] <span>$1$</span>; (C) – (B) node\[midway, below\] <span>$1$</span>; (D) – (C) node\[midway, below\] <span>$0$</span>; (A) to \[bend right\] node\[midway, right\] <span>$2$</span> (D); (E) – (D2) node\[midway, above\] <span>$0$</span>; (D2) – (D) node\[midway, right\] <span>$0$</span>; (D2) – (B2) node\[midway, above\] <span>$1$</span>; (A) edge\[loop below\]node<span>$0$</span> (A);

\[scale=1.5\] (A) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,0) <span>$[1,2,3]$</span>; (D) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,2.5) <span>$[0,1,5]$</span>; (D2) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (1.5,4) <span>$[-1,1,6]$</span>; (E) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,5) <span>$[-3,2,7]$</span>; (B) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,2.5) <span>$[-1,3,4]$</span>; (B2) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (-1.5,4) <span>$[-2,3,5]$</span>; (C) \[fill=white!20,rounded corners=2pt,inner sep=1pt\] at (0,1.5) <span>$[0,2,4]$</span>; (B) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (C) to \[bend right\] node\[midway, left\] <span>$0$</span> (A); (A) to \[bend right\] node\[midway, right\] <span>$1$</span> (C); (B2) to node\[midway, above\] <span>$2$</span> (E); (B2) to node\[midway, right\] <span>$0$</span> (C); (C) to node\[midway, left\] <span>$2$</span> (D2); (B) to node\[midway, left\] <span>$1$</span> (B2); (D) – (B) node\[midway, above\] <span>$1$</span>; (C) – (B) node\[midway, below\] <span>$1$</span>; (D) – (C) node\[midway, below\] <span>$0$</span>; (A) to \[bend right\] node\[midway, right\] <span>$2$</span> (D); (E) – (D2) node\[midway, above\] <span>$0$</span>; (D2) – (D) node\[midway, right\] <span>$0$</span>; (D2) – (B2) node\[midway, above\] <span>$1$</span>; (A) edge\[loop below\]node<span>$0$</span> (A);

We now relate $(m,n)$-filters and the Sommers region, using the balanced representatives of $(m,n)$-filters. We first use $(m,n)$-filters to understand *dominant* affine permutations whose inverses lie in the Sommers region.

A dominant affine permutation ${{w}}$ satisfies ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$ if and only if $$\begin{aligned}
&=n({{\mathfrak{b}}}_{{w}})\end{aligned}$$ for some balanced $(m,n)$-filter ${{\mathfrak{b}}}_{{w}}\in {{\mathcal{BF}}}_m^n$. \[thm:balanced\_eq\_sommers\]

Note that the one-line notation of the element ${{w}}_m^n$ defined in is $n({{\mathfrak{b}}}_m^n)$, where ${{\mathfrak{b}}}_m^n$ is the balanced $(m,n)$-filter generated by the points with level $\ell$ (see ). If we have ${{w}}= n({{\mathfrak{b}}})$ for some balanced $(m,n)$-filter, then the corresponding notion of minimal elements coincide, and acting on a minimal element of ${{w}}$ mirrors removing the corresponding minimal element of ${{\mathfrak{b}}}$. The result now follows from .

Of course,  applies equally well with the roles of $m$ and $n$ switched, and so we obtain an $(m{\leftrightarrow}n)$-bijection and a version of  for dominant affine permutations whose inverses lie in the Sommers region.

There is a bijection $$\begin{aligned}
\Big\{{{w}}\text{ dominant}: {{w}}^{-1} \in {{\mathcal{S}}}_m^n\Big\} &\leftrightarrow \Big\{{{w}}\text{ dominant}: {{w}}^{-1} \in {{\mathcal{S}}}_n^m\Big\}.\end{aligned}$$ Furthermore, both sets have cardinality $$\frac{1}{n+m}\binom{n+m}{n}.$$ \[thm:dominant\_bij\]

The enumeration follows from , and the bijection is induced by the map $n({{\mathfrak{b}}}) \leftrightarrow m({{\mathfrak{b}}})$.

For example, looking at the balanced $(m,n)$-filter on the righthand side of , and disregarding the labels on the horizontal steps, the sorted list of the left-most level in each row gives $m({{\mathfrak{b}}})=[-1,3,4]$, while the sorted list of the bottom level in each column gives $n({{\mathfrak{b}}})=[-1,2,3,5,6]$.

is well-known in the language of simultaneous $(n,m)$-cores using the bijection between $n$-cores and $m$-cores and the coroot lattices of $\widetilde{{{\mathfrak{S}}}}_n$ and $\widetilde{{{\mathfrak{S}}}}_m$. This bijection of  takes an element in $\widetilde{{{\mathfrak{S}}}}_n$ associated to a particular simultaneous $(m,n)$-core and produces the corresponding element in $\widetilde{{{\mathfrak{S}}}}_m$ associated to the same $(m,n)$-core. We refer the reader to @lapointe2005tableaux, @armstrong2014results [Section 4] and @ceballos2016combinatorics for more details.

We can compute the bijection of  directly on the one-line notation of an affine permutation ${{w}}$ by recording the $m$-minimal elements of ${{w}}$. The sequence ${{w}}(1), {{w}}(2),\dots$ is obtained by recording the lowest entry of each column of ${{\mathfrak{b}}}_{{w}}$, in order, then the second-lowest entry of each column, and continuing in this way. The first time an entry in a given congruence class is recorded is when we come to the leftmost entry of the corresponding row (i.e., an element of $m({{\mathfrak{b}}}_{{w}})$). Thus, the $3$-minimal elements of ${{w}}=[-1,2,3,5,6]$ are $[-1,3,4]$: $$\begin{array}{c|ccccc|cc} i & 1 & 2 & 3 & 4 & 5 & 6 & \ldots \\ {{w}}(i) & {\bf -1} & 2 & {\bf 3} & 5 & 6 & {\bf 4} & \ldots \\ {{w}}(i) \text{ mod } 3 & {\bf 2} & 2 & {\bf 0} & 2 & 0 &{\bf 1} & \ldots \end{array}.$$ Similarly, the $5$-minimal elements of ${{w}}=[-1,3,4]$ are $[-1,2,3,5,6]$: $$\begin{array}{c|ccc|ccc|cc} i & 1 & 2 & 3 & 4 & 5 & 6 & 7  & \ldots \\ {{w}}(i) & {\bf -1} &{\bf 3} & 4 & {\bf 2}& {\bf 6} & 7 & {\bf 5} & \ldots \\ {{w}}(i) \text{ mod } 5 & {\bf 4} & {\bf 3} & 4 & {\bf 2} & {\bf 1} & 2 &{\bf 0}  & \ldots \end{array}.$$ \[rem:directly\]

In fact,  can be extended to the whole Sommers region if we pass from balanced $(m,n)$-filters to balanced $(m,n)$-filter tuples.

An affine permutation ${{w}}$ satisfies ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$ if and only if $$\begin{aligned}
&=n({{\mathfrak{p}}}_{{w}})\end{aligned}$$ for some balanced $(m,n)$-filter tuple ${{\mathfrak{p}}}_{{w}}\in {{\mathcal{BT}}}_m^n$. \[thm:and\_bij\]

Choose ${{\mathfrak{p}}}\in{{\mathcal{BT}}}_m^n$. Now $n({{\mathfrak{p}}})$ is the short one-line notation of an affine permutation $w$ since $n({{\mathfrak{p}}})$ is a permutation of $n({{\mathfrak{p}}}^{(0)})$ and ${{\mathfrak{p}}}^{(0)}$ is balanced. We can think of the sequence $w(1),w(2),\dots$ as being obtained by recording the levels removed from $n({{\mathfrak{p}}}^{(0)})$ by repeatedly removing boxes in the order specified by ${{\mathfrak{p}}}$. (In this way, $w(1)$ through $w(n)$ are the levels removed on the first pass, $w(n+1)$,…, $w(2n)$ are the levels removed on the second pass, and so on.) Since levels that differ by $m$ lie in the same row, the smaller is necessarily removed before the larger, guaranteeing that the condition of  is satisfied, so $w\in {{\mathcal{S}}}_m^n$.

Now ${{\mathcal{S}}}_m^n$ is an $m$-fold dilation of the fundamental alcove in $\mathbb{R}^{n-1}$, and so contains $m^n$ affine permutations. Since ${{\mathfrak{p}}}\mapsto n({{\mathfrak{p}}})$ is a bijection and $|{{\mathcal{BT}}}_m^n|=m^n$ by , we conclude the result.

\[rem:cycles\_affine\] Since $\mathfrak{P}_m^n \cong \mathfrak{F}_m^n$, by  we can interpret affine elements ${{w}}$ with ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$ as cycles with $n$ vertices in the directed graph $\mathfrak{P}_n^m$. The short one-line notation of ${{w}}$ is given by reading the minimal element chosen for the edge (undoing the rebalancing that occurs at each step). For example, reproducing , the cycle in $\mathfrak{P}_5^3$ with removable $3$-minimal elements in bold $$\begin{aligned}
{6}
& [-1,{\bf 3},4] &&\to [{\bf -2},3,5] &&\to [{\bf 0},2,4] &&\to [1,{\bf 2},3] &&\to [0,{\bf 2},4] &&\to [-1,3,4] \text{ (rebalanced)}\\
&+0 &&\phantom{\to} +1 &&\phantom{\to} +2 &&\phantom{\to} +3 &&\phantom{\to} +4 &&\phantom{\to} +5\\
&[-1,{\bf 3},4] &&\to [{\bf -1},4,6] &&\to [{\bf 2},4,6] &&\to [4,{\bf 5},6] &&\to [4,{\bf 6},8] &&\to [4,8,9] \text{ (not rebalanced)}\end{aligned}$$ produces the one-line notation of the affine Weyl group element $${{w}}= [3,-1,2,5,6] \in {{\widetilde{\mathfrak{S}}}}_5.$$

Parking Words from the Sommers Region {#sec:sommers_parking_words}
-------------------------------------

Using , we can easily restate the maps $A$ and $B$ from —originally defined on parking $(m,n)$-tuple filters—in the language of affine permutations. These maps originally appeared in this form in @gorsky2016affine.

There are *many* statistics one can define on Dyck paths and parking functions (in their various combinatorial manifestations). In @armstrong2013hyperplane for $(m,n)=(n{+}1,n)$, Armstrong introduced statistics on the affine symmetric group that corresponded to what Haglund and Loehr called ${{\mathsf{area}}}'$ and ${{\mathsf{bounce}}}$ in @haglund2005conjectured. Armstrong suggested that his statistics would recover work in the $(kn+1,n)$ case, previously considered by Loehr and Remmel in @loehr2004conjectured. By using the relationship between Shi arrangements and Sommers regions, Gorsky, Mazin, and Vazirani generalized Armstrong's constructions to general coprime $(m,n)$—and called the statistics ${{\mathsf{dinv}}}$ and ${{\mathsf{area}}}$ (see ). Finally, we note that the paper @armstrong2016rational also defines statistics for general coprime $(m,n)$, but doesn't define a zeta map on $(m,n)$-parking paths or words.

### The Map $A$: the Anderson Labeling {#sec:anderson2}

Translating  using the bijection  gives the following definition (compare with @gorsky2016affine [Section 3.1]).

For ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$, let $k=\min\{{{w}}(1),{{w}}(2),\ldots,{{w}}(n)\}$ and write ${{w}}'(i)={{w}}(i)-k$. Then $A({{w}})$ is defined by $${{w}}=[{{w}}(1),{{w}}(2),\ldots,{{w}}(n)] \xmapsto{A} \left[a \cdot {{w}}'(1), a \cdot {{w}}'(2),\ldots, a \cdot {{w}}'(n) \right] {\operatorname{mod}}m,$$ where $a n = -1 {\operatorname{mod}}m$.

As in , for ${{w}}=[3,-1,2,5,6]$ with ${{w}}^{-1} \in {{\mathcal{PT}}}_3^5$, we compute $A({{w}})$ by $${{w}}= [3,-1,2,5,6] \mapsto [1\cdot 4,1\cdot 0,1\cdot 3,1\cdot 6,1\cdot 7] {\operatorname{mod}}3 = [1,0,0,0,1],$$ since $1 \cdot 5 = -1 {\operatorname{mod}}3$.

We also find $A({{w}})$ for ${{w}}=[5,-2,3]$ with ${{w}}^{-1} \in {{\mathcal{PT}}}_5^3$: $${{w}}= [5,-2,3] \mapsto [3\cdot 7,3\cdot 0,3\cdot 5] {\operatorname{mod}}5 = [1,0,0],$$ since $3 \cdot 3 = -1 {\operatorname{mod}}5$.

If the short one-line notations of ${{w}}_1$ and ${{w}}_2$ are permutations of each other, then so are $A({{w}}_1)$ and $A({{w}}_2)$, so that elements in the same coset of ${{\widetilde{\mathfrak{S}}}}_n/{{\mathfrak{S}}}_n$ are assigned to the same $(m,n)$-parking word, up to a permutation. It follows from  and  that $A$ is a bijection; this is illustrated for $(m,n)=(4,3)$ and $(5,3)$ in .

The map $$\begin{aligned}
A: {{\mathcal{S}}}_m^n &\to {{\mathcal{PW}}}_m^n\\ {{w}}&\mapsto A({{w}}^{-1})\end{aligned}$$ is a bijection.

There is a more geometric way to recover the parking word $A({{w}})$, which we quickly sketch. There is a natural bijection between dominant permutations of $\widetilde{{{\mathfrak{S}}}}_n$ and the coroot lattice $\check{Q}:=\left\{\mathbf{x} \in \mathbb{Z}^n : \sum_{i=1}^n x_i = 0\right\}$: $${{w}}\in \widetilde{{{\mathfrak{S}}}}_n \mapsto {{w}}^{-1}(0).$$ The restriction of this bijection to the $m$-fold dilation of the fundamental alcove gives a set of representatives for $\check{Q}/m\check{Q}$, which are in bijection with $(m,n)$-parking words using natural coordinates and the cycle lemma. We refer the reader to @haiman1994conjectures [@gorsky2016affine; @thiel2016anderson] for more details relating to this construction.

![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by parking words under the Anderson bijection.<span data-label="fig:anderson"></span>](andersonsommers34.pdf "fig:"){width=".45\textwidth"}![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by parking words under the Anderson bijection.<span data-label="fig:anderson"></span>](andersonsommers35.pdf "fig:"){width=".45\textwidth"}

### The Map $B$: the Pak-Stanley Labeling {#sec:stanley_pak}

It is natural to ask for a *bijective* proof for the number of Shi regions—for example, via a bijection betwen Shi regions and $(n{+}1,n)$-parking words. Pak and Stanley found such a labeling of the Shi regions @stanley1996hyperplane [Theorem 5.1], which Stanley later extended to the Fuss level of generality @stanley1998hyperplane. Using the correspondence between the minimal alcoves of the Shi arrangement and the Sommers region, the Pak-Stanley labeling was finally extended to the rational level in @gorsky2016affine as an affine analogue of the <span>*code*</span> of a permutation.

For ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$, $B({{w}})$ is $$\begin{aligned}
    B: \widetilde{{{\mathfrak{S}}}}_n &\to [m]^n \\
    {{w}}&\mapsto {{\sf p}}_1 \ldots {{\sf p}}_n,
 \end{aligned}$$ where for $1 \leq i \leq n$, $${{\sf p}}_i = \left|\left\{ j>i \in \mathbb{N} : \substack{{{w}}(j) < {{w}}(i),\\ {{w}}(i)-{{w}}(j)< m} \right\}\right|.$$ \[def:sp\]

Using the correspondence between inversions and hyperplanes, ${{\sf p}}_i$ counts the number of hyperplanes of the form $\mathcal{H}_{i,j}^k$ of height less than $m$ separating the alcove corresponding to ${{w}}^{-1}$ from the fundamental alcove. The Pak-Stanley labeling of the Sommers region is illustrated in the cases $(n,m)=(3,4)$ and $(3,5)$ in .

![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by parking functions under the Pak-Stanley bijection.<span data-label="fig:stanley_pak"></span>](stanleypak4.pdf "fig:"){width=".45\textwidth"}![The Sommers regions ${{\mathcal{S}}}_4^3$ and ${{\mathcal{S}}}_5^3$, with alcoves labeled by parking functions under the Pak-Stanley bijection.<span data-label="fig:stanley_pak"></span>](stanleypak5.pdf "fig:"){width=".45\textwidth"}

We will now show that $B({{w}})$ in  is equivalent to $B({{\mathfrak{p}}}_{{w}})$ in  under the bijection in ; in particular, this will show that $B({{w}})$ is a bijection from ${{\mathcal{S}}}_m^n$ to ${{\mathcal{PW}}}_m^n$.

For any ${{w}}$ with ${{w}}^{-1} \in {{\mathcal{S}}}_m^n$, $$B({{w}}) = B({{\mathfrak{p}}}_{{w}}),$$ where ${{\mathfrak{p}}}_{{w}}$ is the $(m,n)$-filter tuple with $[w(1),w(2),\ldots,w(n)]=n({{\mathfrak{p}}}_{{w}})$. \[thm:b\_eq\]

gives a bijection between $n$-cycles in $\mathfrak{P}_n^m$ and affine permutations ${{w}}\in {{\widetilde{\mathfrak{S}}}}_n$ with ${{w}}^{-1} \in {{\mathcal{S}}}^n_m$. Since $\mathfrak{P}_n^m \cong \mathfrak{F}_m^n$, we can see $B({{\mathfrak{p}}}_{{w}})$ directly on the $n$-cycle. Fix $1 \leq i \leq n$. At most one element from each residue class modulo $m$ in the one-line notation of ${{w}}$ can contribute to ${{\sf p}}_i$. The number of residue classes which contribute (which equals ${{\sf p}}_i$) is also the relative order of the number removed when calculating $B({{\mathfrak{p}}}_{{w}})$.

Continuing , we can interpret parking words ${{\sf p}}\in {{\mathcal{PW}}}_m^n$ as cycles with $n$ vertices in the directed graph $\mathfrak{P}_n^m$. The word is obtained by reading the relative order of the minimal element chosen for the edge. For example, when ${{w}}=[3,-1,2,5,6]$, recording the relative order of the element removed gives a correspondence between the $5$-cycle encoding the parking $(3,5)$-filter tuple ${{\mathfrak{p}}}_{{w}}$ and the parking word $B({{\mathfrak{p}}}_{{w}})$:

$$\begin{aligned}
{7}
 & [-1,{\bf 3},4] &&\to [{\bf -2},3,5] &&\to [{\bf 0},2,4] &&\to [1,{\bf 2},3] &&\to [0,{\bf 2},4] &&\to [-1,3,4]\\
&+0 &&\phantom{\to} +1 &&\phantom{\to} +2 &&\phantom{\to} +3 &&\phantom{\to} +4 &&\phantom{\to} +5\\
 & [-1,{\bf 3},4] &&\to [{\bf -1},4,6] &&\to [{\bf 2},4,6] &&\to [4,{\bf 5},6] &&\to [4,{\bf 6},8] &&\to [4,8,9] \\
B({{\mathfrak{p}}}_{{w}}) :&  \phantom{+}1 && \phantom{\to+}0 && \phantom{\to+}0 && \phantom{\to+}1 && \phantom{\to+}1 &&\end{aligned}$$

On the other hand, we can compute $B({{w}})$ by extending the short one-line notation of ${{w}}$. tells us that the results of these two calculations agree.

$$\xymatrix@C=1em@R=1.5em{ i \ar@{-}[]+<3.5em,+1em>;[dd]+<3.5em,-1em> &  1 & 2 & 3 & 4 & 5 \ar@{--}[]+<1.5em,+1em>;[dd]+<1.5em,-1em> & 6 & 7 & 8 & 9 & 10 \\  n({{\mathfrak{p}}}_{{w}}) = {{w}}& {\bf 3}\ar@/_1pc/[rr] & {\bf -1} & 2 & 5 \ar@/_2pc/[rrr] & 6 \ar@/_1pc/[rr] & 8 & {\bf 4} & 7 & 10 & 11 \\ B({{w}}) & 1 & 0 & 0 & 1 & 1 & & & &}.$$

The letters in the one-line notation of $w$ that occur in ${{\mathfrak{p}}}_{{w}}^{(0)}$ are written in bold, and we have marked the inversions that count towards $B({{w}})$ using arrows. Note that the inversion $(i,j)=(1,2)$ doesn't count towards $B({{w}})$ because ${{w}}(1)-{{w}}(2)=3-(-1)\geq 3$. \[ex:b2\]

Now imply that $B$ is a bijection from the ${{\mathcal{S}}}_m^n$ to $(m,n)$-parking words. This resolves @gorsky2016affine [Conjecture 1.4].

\[<span>@gorsky2016affine [Conjecture 1.4]</span>\] The map $B: {{\mathcal{S}}}_m^n \to {{\mathcal{PW}}}_{m}^n$ is a bijection. \[thm:rational\_code\]

In @gorsky2016affine [Section 7.1], Gorsky, Mazin, and Vazirani provide a conjectural algorithm to invert $B$. Their Conjecture 7.9 (which essentially says that their algorithm succeeds) follows now from our  and the convergence proved in  and  .

[^1]: Carlsson and Mellit actually proved a stronger result, giving an explicit formula for the *Frobenius series* for the space of diagonal coinvariants.

[^2]: Something is lost in the rational case: one statistic remains the degree, but the second statistic now appears only using a filtration.

[^3]: To cleanly bridge from this section to the affine symmetric group in , we will want to normalize points so that $\sum_{i=0}^{m-1} x_i = \binom{m+1}{2}$. We therefore used that normalization in .

[^4]: For consistency with its generalization to parking paths, we are using the inverse of the zeta map from @haglund2008q [Theorem 3.15].

[^5]: Although this bijection is between two slightly different manifestations of parking paths.

[^6]: This is a special case of the general definition of the sweep map, which is on general lattice paths in an $N$-dimensional box.

[^7]: But note that we are now working with $\widetilde{\mathfrak{S}}_{n}$ not $\widetilde{\mathfrak{S}}_{m}$.

[^8]: Eric Sommers was surprised to learn that the region has recently been named after him.

{'source': 'arXiv_out/1901'}