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

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

Sweeping up Zeta
Nathan Williams
LaCIM
March 7, 2016
Two stories with the same answer.
1. Understanding the orbit structure of a subdivided simplex.
Two stories with the same answer.
2. Inverting a map on lattice paths.
2002
Dihedral Symmetry in Young's Lattice
Definition (R. Suter). Let $\mathbb{Y}_n$ be the order ideal of Young's lattice containing those (integer) partitions with hook lengths at most $n$.
$\mathbb{Y}_0$
$\mathbb{Y}_1$
$\mathbb{Y}_2$
$\mathbb{Y}_3$
$\mathbb{Y}_4$
Suter's cyclic action
Theorem (R. Suter). $\mathbb{Y}_n$ has $2^n$ elements and the graph underlying $\mathbb{Y}_n$ has a cyclic symmetric of order $(n+1)$.
Suter's cyclic action
Suter's cyclic action
Why does $\mathbb{Y}_n$ have $2^n$ elements and $(n+1)$-fold cyclic symmetry?
<1993
Abelian Ideals of a Borel Subalgebra
Fix $\mathfrak{g}$ a complex simple Lie algebra and $\mathfrak{b}$ a Borel subalgebra.
An abelian ideal $\mathfrak{a} \subseteq \mathfrak{b}$ is a subspace of $\mathfrak{b}$ such that $[\mathfrak{a},\mathfrak{a}] = 0$ and $[\mathfrak{g},\mathfrak{a}] \subseteq \mathfrak{a}.$
(Using the root-space decomposition \[\mathfrak{b} = \mathfrak{h} \oplus \bigoplus_{\alpha \in \Phi^+} \mathfrak{g_\alpha},\] these biject with certain order filters of "the" positive root poset.)
Theorem (D. Peterson). There are $2^n$ abelian ideals of $\mathfrak{b}$, where $\mathrm{rank}(\mathfrak{g})=n$.
Why such a clean answer?
Weyl Groups
"Definition". A Weyl group $W$ is a finite reflection group stabilizing its root lattice $Q$.
\[\mathfrak{S}_{n+1} = \left \langle s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
  • $s_i$ acts on $\mathbb{R}^{n+1}$ by reflecting in the hyperplane $x_i-x_{i+1}=0.$
  • The lattice $Q = \{(x_1,x_2,\ldots,x_{n+1})\in \mathbb{Z}^{n+1} : \sum_{i=1}^{n+1}x_i = 0\}.$
Affine Weyl Groups
"Definition". The affine Weyl group $\widetilde{W}$ corresponding to the Weyl group $W$ is the group $W \rtimes \check{Q}$.
\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
\[\mathfrak{S}_{n+1} \subset \widetilde{\mathfrak{S}}_{n+1} = \left \langle s_0,s_1,\ldots,s_n : \substack{s_i^2=e, \\ s_i s_{i+1} s_i = s_{i+1} s_i s_{i+1}, \\ s_i s_j = s_j s_i \text{ for } |i-j|>1} \right\rangle.\]
Why such a clean answer? Abelian ideals of $\mathfrak{b}$ specify inversion sets in the 2-fold dilation of the fundamental alcove $2A_0$:
\[\begin{align*}\mathfrak{a}&=\bigoplus_{\alpha \in \Psi \subseteq \Phi^+} \mathfrak{g}_\alpha \mapsto w \in \widetilde{W}, \text{ where}\\ \mathrm{inv}(w) &= \bigsqcup_{\alpha \in \Psi \subseteq \Phi^+} \{\delta-\alpha\}.\end{align*}\]
2004
Symmetries of the Fundamental Alcove
Why does $\mathbb{Y}_n$ have $2^n$ elements and $(n+1)$-fold cyclic symmetry?
The partitions in $\mathbb{Y}_n$ are abelian ideals of $\mathfrak{b}$ in type $A_n$. (So the elements of $\widetilde{A}_n$ "contained" in $2A_0$ are indexed by $\mathbb{Y}_n$.)
Why does $\mathbb{Y}_n$ have $2^n$ elements and $(n+1)$-fold cyclic symmetry?
The $(n+1)$-fold cyclic symmetry of $\mathbb{Y}_n$ comes from the symmetry of the fundamental alcove in $\widetilde{A}_n$ (the poset structure is weak order).
This symmetry has many interesting manifestations:
This symmetry has many interesting manifestations.
Cycle Lemma. For $a$ and $b$ relatively prime, there are \[\frac{1}{a+b}\binom{a+b}{a}\] Dyck paths from $(0,0)$ to $(a,b)$.
2007
Cyclic Sieving Phenomenon
The Cyclic Sieving Phenomenon
In 2004, D. Reiner, D. Stanton, D. White defined the cyclic sieving phenomenon, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.
\[1100 \to 1001 \to 0011 \to 0110\] \[1010 \to 0101\]
The Cyclic Sieving Phenomenon
In 2004, D. Reiner, D. Stanton, D. White defined the cyclic sieving phenomenon, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.
\[1100 \to 1001 \to 0011 \to 0110\] \[1010 \to 0101\]
The Cyclic Sieving Phenomenon
In 2004, D. Reiner, D. Stanton, D. White defined the cyclic sieving phenomenon, a surprising relation between generating functions evaluated at roots of unity and orbit structures under cyclic actions.
\[f(q)=\sum_{\mathcal{D} \in \binom{[4]}{2}} q^{\mathrm{area}(\mathcal{D})} = 1+q+2q^2+q^3+q^4\]
The Cyclic Sieving Phenomenon
\[1100 \xrightarrow{{c}} 1001 \xrightarrow{{c}} 0011 \xrightarrow{{c}} 0110\]
\[1010 \xrightarrow{{c}} 0101\]
\[\begin{align*}f(q)=\sum_{\mathcal{D} \in \binom{[4]}{2}} q^{\mathrm{area}(\mathcal{D})} &= 1+q+2q^2+q^3+q^4\\ f(\sqrt{-1}^4) &= 6 \hspace{1ex} \text{ elements fixed by } c^4, \\ f(\sqrt{-1}^2)&=2 \hspace{1ex} \text{ elements fixed by } c^2, \\ f(\sqrt{-1})&=0 \hspace{1ex} \text{ elements fixed by } c.\end{align*}\]
Conjecture (V. Reiner). $\mathbb{Y}_n$ exhibits the CSP with $\prod_{i=1}^n(1+q^i)$.
Conjecture (D. Stanton). There is an equivariant bijection from $\mathbb{Y}_n$ under R. Suter's action to words with odd sum on $[0,1]$ of length $n+1$ (under rotation).
\[111 \hspace{2em} 100 \to 001 \to 010\] \[(1+q)(1+q^2)\Big|_{q=\omega^1}=1 \hspace{2em} (1+q)(1+q^2)\Big|_{q=\omega^3}=4,\] where $\omega=e^{2\pi i/3}$.
2010
Bijactions
Bijactions
For each partition in an orbit of $\mathbb{Y}_n$: is the first part repeated?
By construction, this gives an equivariant map from $\mathbb{Y}_n$ to some set of words under rotation.
The image turns out to be binary words of odd sum.
The inverse is computed by partitioning the word, and then "bouncing around" (starting in the block labeled by the sum).
\[1011\mathbf{0} \rightarrow \mathbf{0} (1)(1+0)(1+0+1)(1+0+1+1) \rightarrow 01101\]
The inverse is computed by partitioning the word, and then "bouncing around" (starting in the block labeled by the sum).
\[1010\mathbf{1} \rightarrow \mathbf{0} (1)(1+0)(1+0+1)(1+0+1+0) \rightarrow 01100\]
There is only one partition of the word for which "bouncing around" eats up all of the letters!
It is easy to find the partition for binary words...
There is only one partition of the word for which "bouncing around" eats up all of the letters!
It is easy to find the partition for binary words...
...but I generalized the combinatorics to words on $[m]$.
Finding the (unique) successful partitioning becomes less obvious. (It isn't even obvious such a partitioning exists.)
...but I generalized the combinatorics to words on $[m]$.
Finding the (unique) successful partitioning becomes less obvious. (It isn't even obvious such a partitioning exists.)
Mike Hardy and Wikipedia
Mike Hardy and Wikipedia
2011
Cores and Canada
M. Zabrocki and C. Berg generalized Suter's symmetry using the affine symmetric group $\widetilde{S}_{n+1}$ by replacing $2A_0$ with $mA_0$.
Although this gave a beautiful geometric picture, it did not help when trying to find the inverse of my map.
2012
The Inverse
Hugh Thomas and I published the general inverse in 2012.
1988
Macdonald Polynomials
"Definition". The $\widetilde{\mathrm{M}}$acdonald polynomials \[\widetilde{H}_\mu=\sum_{\lambda} \widetilde{K}_{\lambda\mu}(q,t)s_\lambda(\mathbf{x})\] are a linear basis of symmetric functions. Define $\nabla$ by: \[\nabla \left(\widetilde{H}_\mu (\mathbf{x}; q,t) \right) = \left(\prod_{(a,b)\in \mu} q^a t^b\right) \widetilde{H}_\mu (\mathbf{x}; q,t).\]
The $\widetilde{H}_\mu$ generalize Hall-Littlewood polynomials, which generalize Schur and monomial symmetric polynomials.
1996
$(q,t)$-Catalan numbers
$(q,t)$-Catalan polynomials
Applying $\nabla$ to symmetric functions is a favorite past-time.
Definition. (A. Garsia, M. Haiman)\[\mathrm{Cat}(n;q,t):=\langle \nabla e_n, e_n \rangle.\] \[\mathrm{Cat}(n;q,t)=\sum_{\mu \vdash n} \frac{t^{2\sum l} q^{2 \sum a} (1-t)(1-q)\prod (1-q^{a'}t^{l'})\sum q^{a'}t^{l'}}{\prod(q^a-t^{l+1})(t^l-q^a+1)}.\]
\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]
$(q,t)$-Catalan polynomials
Definition. (A. Garsia, M. Haiman)\[\mathrm{Cat}(n;q,t)=\text{a rational function symmetric in $q$ and $t$}.\]
\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]
Conjecture. (A. Garsia, M. Haiman)\[\mathrm{Cat}(n;q,t)=\text{a } polynomial \text{ in $q$ and $t$.}\]
$(q,t)$-Catalan polynomials
\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]
Theorem. (A. Garsia, M. Haiman) \[\mathrm{Cat}(n;q,1)=\mathrm{Cat}(n;1,q)=\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}\]
2001
Bounce, dinv, and Zeta
James Haglund and Mark Haiman
\[\mathrm{Cat}(n;q,t)\stackrel{?}{=}\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{???}(\mathcal{D})}\]
James Haglund and Mark Haiman
found bounce and dinv
Theorem. (A. Garsia, J. Haglund, M. Haiman) \[\mathrm{Cat}(n;q,t)=\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{bounce}(\mathcal{D})}=\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{dinv}(\mathcal{D})}t^{\mathrm{area}(\mathcal{D})},\] \[\zeta: (\mathrm{dinv},\mathbf{area})\mapsto (\mathbf{area},\mathrm{bounce}).\]
\[\zeta: (\mathrm{dinv},\mathbf{area})\mapsto (\mathbf{area},\mathrm{bounce}).\]
\[\mathrm{Cat}(n;q,t)=\sum_{\mathcal{D} \in \mathrm{Dyck}_n} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{area}(\zeta(\mathcal{D}))}.\]
\[\mathrm{Cat}(3;q,t)=q^3+q^2t+qt+qt^2+t^3.\]
2012
The Sweep Map
The Sweep Map
Definition. \[\mathrm{Cat}(\mathrm{Paths};q,t):=\sum_{\mathcal{D} \in \mathrm{Paths}} q^{\mathrm{area}(\mathcal{D})}t^{\mathrm{area}(\mathrm{sweep}(\mathcal{D}))}.\]
Conjecture. (D. Armstrong, N. Loehr, G. Warrington) The sweep map is a bijection (under very general conditions).
  • Loehr, N., 2005, Conjectured statistics for the higher q; t-Catalan sequences. Electronic Journal of Combinatorics.
  • Lee, K., Li, L., and Loehr, N., 2013. Combinatorics of certain higher $(q,t)$-Catalan polynomials: chains, joint symmetry, and the Garsia-Haiman formula. Journal of Algebraic Combinatorics.
  • Armstrong, D., Loehr, N. and Warrington, G., 2014. Sweep maps: A continuous family of sorting algorithms. arXiv:1406.1196.
  • Gorsky, E. and Mazin, M., 2014. Compactified Jacobians and $(q,t)$-Catalan numbers II. Journal of Algebraic Combinatorics.
  • Gorsky, E., Mazin, M., and Vazirani, M., 2014. Affine permutations and rational slope parking functions. Transactions of the American Mathematical Society.
  • Ceballos, C., Denton, T. and Hanusa, C., 2015. Combinatorics of the zeta map on rational Dyck paths. arXiv:1504.06383.
  • Sulzgruber, R., 2015. Rational Shi tableaux and the skew length statistic. arXiv:1512.04320.
  • Thiel, M., 2015. From Anderson to Zeta: A uniform bijection between Shi regions and the finite torus. arXiv:1504.07363.
  • Xin, G., 2015. An efficient search algorithm for inverting the sweep map on rational Dyck paths. arXiv:1505.00823.
2015
The Inverse
CMS Sectional
Sweep Map Combinatorics
This is the same as the previous inverse, as long as we take $m$ "large enough".
Details
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
A partitioned word $\mathsf{u}^*$ for which the "bouncing around" procedure succeeds has a special form that is easier to check than whether or not "bouncing around" succeeds.
For a word $\mathsf{u}={\sf u}_1{\sf u}_2\cdots {\sf u}_N$, let $|\mathsf{u}|=\sum_{i=1}^N {\sf u}_i$ and $|\mathsf{u}|_m=|{\sf u}| \mod m$.
Definition. An equitable partition has column sums $\lceil \frac{|{\sf u}|}{m}\rceil$ in columns $1$ to $|{\sf u}|_m$ and column sums $\lfloor \frac{|{\sf u}|}{m}\rfloor$ otherewise.
Theorem. The equitable partitions of a fixed word ${\sf u}$ form a distributive lattice (under componentwise comparison of the block to which each letter belongs).
The correctly partitioned word is the maximal element of this lattice.
Theorem. The equitable partitions of a fixed word ${\sf u}$ form a distributive lattice (under componentwise comparison of the block to which each letter belongs).
The correctly partitioned word is the maximal element of this lattice.
Step 1: Get in the Lattice
Start with the partition with all letters in the leftmost block. Find the leftmost column that fails the equitable condition and move its rightmost element to the next column over. Repeat.
Proposition. This procedure terminates in the minimal equitable partition.
Step 1: Get in the Lattice
Step 2: Move to the Top
Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top
Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top
Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top
Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Step 2: Move to the Top
Once in the lattice, we move up the lattice by "bouncing around" until failure, and then shifting all unused letters to the right. (This preserves the property of staying in the lattice).
Thank you!

Use a spacebar or arrow keys to navigate