A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the q,t-Catalan Symmetry
Abstract
Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata theory study such a bijection as a word-to-word computation and measure its memory, input access, and control of output order. This refines existence questions by asking which computational mechanisms a bijection requires. We develop this viewpoint for Dyck paths. Our motivating example is the q,t-Catalan polynomial. Let Dn be the set of Dyck paths of semilength n, let D=⋃n≥ 0Dn, and let area, dinv, bounce : D→ℕ be the standard statistics. Then, Cn(q,t)=∑P∈ Dnqarea(P)tbounce(P) =∑P∈ Dnqdinv(P)tarea(P). Haglund's zeta map ζ: D→ D gives a bijective proof: it preserves semilength and sends $(dinv,area)$ to $(area,bounce)$. By contrast, the full symmetry Cn(q,t)=Cn(t,q) still lacks a direct explanation: no explicit, uniform, semilength-preserving bijection is known that swaps area and dinv on every Dyck path. Polyregular maps from automata theory provide a natural computational starting point, but we prove that neither ζ nor the classical height-sweep bijection witnessing Narayana symmetry is polyregular. The missing mechanism is global ordering by numerical levels whose range grows with the input. We call this a \emph{rank sort} and introduce \emph{weighted-rank polyregular maps} (WRP), extending polyregular maps by one such sort and containing both bijections. Nevertheless, WRP is a proper subclass of deterministic logspace. We prove that ζ−1 lies outside WRP and that no WRP map can realise a semilength-preserving area-dinv swap. Thus the rank-sorting strategy behind ζ cannot be extended within WRP to exchange the two statistics.
Related
BibTeX
@misc{baek2026computational,
title = {{A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry}},
author = {Jineon Baek and Byung-Hak Hwang and Joonhyun La and Hongseok Yang},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.05005},
eprint = {2609.05005},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.05005},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the q,t-Catalan Symmetry
AU - Jineon Baek
AU - Byung-Hak Hwang
AU - Joonhyun La
AU - Hongseok Yang
PY - 2026
DA - 2026/09/04
PB - arXiv
DO - 10.48550/arxiv.2609.05005
UR - https://arxiv.org/abs/2609.05005
AB - Algebraic combinatorics often seeks bijections that explain identities between distributions object by object. Encoding combinatorial objects as words lets automata theory study such a bijection as a word-to-word computation and measure its memory, input access, and control of output order. This refines existence questions by asking which computational mechanisms a bijection requires. We develop this viewpoint for Dyck paths. Our motivating example is the q,t-Catalan polynomial. Let D_n be the set of Dyck paths of semilength n, let D=⋃_n≥ 0D_n, and let area, dinv, bounce : D→ℕ be the standard statistics. Then, C_n(q,t)=∑_P∈ D_nq^area(P)t^bounce(P) =∑_P∈ D_nq^dinv(P)t^area(P). Haglund's zeta map ζ: D→ D gives a bijective proof: it preserves semilength and sends $(dinv,area)$ to $(area,bounce)$. By contrast, the full symmetry C_n(q,t)=C_n(t,q) still lacks a direct explanation: no explicit, uniform, semilength-preserving bijection is known that swaps area and dinv on every Dyck path. Polyregular maps from automata theory provide a natural computational starting point, but we prove that neither ζ nor the classical height-sweep bijection witnessing Narayana symmetry is polyregular. The missing mechanism is global ordering by numerical levels whose range grows with the input. We call this a \emph{rank sort} and introduce \emph{weighted-rank polyregular maps} (WRP), extending polyregular maps by one such sort and containing both bijections. Nevertheless, WRP is a proper subclass of deterministic logspace. We prove that ζ^−1 lies outside WRP and that no WRP map can realise a semilength-preserving area-dinv swap. Thus the rank-sorting strategy behind ζ cannot be extended within WRP to exchange the two statistics.
ER -