Metraipolis › archive › dc_99a8f2aab2fc

A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry — arXiv:2609.05005

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.05005
License (as archived)
CC0-1.0
Archived
2026-10-16T23:21:04.414Z
SHA-256 of the archived text
9c7101716f7602b0278c3f3769142cb66650fcb00c4c9de3eb18a0651eb25b50
Stable URL of this page
https://metraipolis.com/documento/dc_99a8f2aab2fc

How to cite

A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry — arXiv:2609.05005 — arXiv (en), https://arxiv.org/abs/2609.05005 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_99a8f2aab2fc (Metraipolis archive dc_99a8f2aab2fc, sha256 9c7101716f7602b0278c3f3769142cb66650fcb00c4c9de3eb18a0651eb25b50)
BibTeX
@misc{dc99a8f2aab2fc,
  title = {A Computational Obstruction to Swapping Area and Dinv: An Automata-Theoretic View of the $q,t$-Catalan Symmetry — arXiv:2609.05005},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.05005},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_99a8f2aab2fc; sha256 9c7101716f7602b0278c3f3769142cb66650fcb00c4c9de3eb18a0651eb25b50},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.05005. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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=\bigcup_{n\ge 0}D_n$, and let $area, dinv, bounce \colon D\to\mathbb{N}$ be the standard statistics. Then, \[ C_n(q,t)=\sum_{P\in D_n}q^{area(P)}t^{bounce(P)} =\sum_{P\in D_n}q^{dinv(P)}t^{area(P)}. \] Haglund's zeta map $\zeta\colon D\to 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 $\zeta$ 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 $\zeta^{-1}$ lies outside WRP and that no WRP map can realise a semilength-preserving area-dinv swap. Thus the rank-sorting strategy behind $\zeta$ cannot be extended within WRP to exchange the two statistics.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-07 in math.CO).
Categorie arXiv: Combinatorics (math.CO) ; Computational Complexity (cs.CC); Formal Languages and Automata Theory (cs.FL); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.05005 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-16T23:03:13.255Z dalla pagina https://arxiv.org/catchup/math.CO/2026-09-07?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).