Asymptotics of the Average Stack-Sorting Depth

Jerry Zhang · 2026

Read Asymptotics of the Average Stack-Sorting Depth by Jerry Zhang (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-24110.txt.

Introduction

Zhang settles a question in combinatorics that had been open since 1990. It concerns sorting lists with a single stack. The stack-sorting map reads a permutation once, pushing or popping entries under a simple rule. Repeated passes sort it in the end. Researchers track the mean number of passes a random permutation of a given length needs. West conjectured in 1990 that this mean, divided by length, settles toward a fixed limit as length grows.

Working alone, Zhang uses a recent framework of stack-sorting diagrams and tableaux. These diagram tools encode how passes change a permutation. With them he proves the limit exists, which confirms West's conjecture after more than three decades. He also builds a monotone increasing sequence that converges to that limit. It improves the best previous lower bound on the limit's value. The 2026 result closes the existence question, while the exact value stays open for future work.

Catalog record

CREATORJerry Zhang
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.24110

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Asymptotics of the Average Stack-Sorting Depth Jerry Zhang Abstract . Let 𝒟 n \mathcal{D}_{n} denote the average number of passes of the stack-sorting map s s required to sort a permutation in S n S_{n} . We use the recently introduced framework of stack-sorting diagrams and tableaux to prove that the limit lim n → ∞ 𝒟 n / n \lim_{n\to\infty}\mathcal{D}_{n}/n exists. This resolves a longstanding conjecture of West originally proposed in 1990 1990 . As a consequence, we also provide a monotonically increasing sequence that converges to lim n → ∞ 𝒟 n / n \lim_{n\to\infty}\mathcal{D}_{n}/n , improving upon Defant’s lower bound of λ ≈ 0.62433 \lambda\approx 0.62433 . 1. Introduction West [ 2 ] introduced the stack-sorting map s in 1990 as a deterministic procedure on permutations. The input permutation \pi is read from left to right, and at each step, the next entry of \pi is pushed into the stack if either the stack is empty or the top element of the stack is greater than the next entry. If the next entry of \pi cannot be pushed into the stack, then the top element of the stack is popped out and appended to the output permutation. The procedure concludes when all entries have been appended to the output permutation. Figure 1 illustrates the map on \pi=1324 . Note that each application of s sends the greatest unsorted entry to its correct position. Thus, at most n-1 applications of s are required to sort a permutation with n elements. The stack-sorting depth \langle\pi\rangle is the minimum number of passes required to sort \pi . 1324 ​​​​​​​ \longrightarrow ​​​​​​​ 324 1 ​​​​​​​ \longrightarrow ​​​​​​​ 324 1 ​​​​​​​ \longrightarrow ​​​​​​​ 24 3 1 ​​​​​​​ \longrightarrow ​​​​​​​ 4 3 2 1 ​​​​​​​ \longrightarrow ​​​​​​​ 4 3 12 ​​​​​​​ \longrightarrow ​​​​​​​ 4 123 ​​​​​​​ \longrightarrow ​​​​​​​ 4 123 ​​​​​​​ \longrightarrow ​​​​​​​ 1234 Figure 1 . West’s stack-sorting map applied on \pi=1324 . Define the average stack-sorting depth over S_{n} to be \mathcal{D}_{n}:=\frac{1}{n!}\sum_{\pi\in S_{n}}\langle\pi\rangle. West [ 2 ] provided the first asymptotic lower bound for \mathcal{D}_{n} with a pattern avoidance argument, and he conjectured that \mathcal{D}_{n}/n converges as n approaches infinity. Theorem 1.1 (West) . \liminf_{n\to\infty}\frac{\mathcal{D}_{n}}{n}\geq 0.23. In 2020, Defant [ 1 ] improved upon West’s lower bound and proved the first nontrivial upper bound. Theorem 1.2 (Defant) . \lambda\leq\liminf_{n\to\infty}\frac{\mathcal{D}_{n}}{n}\leq\limsup_{n\to\infty}\frac{\mathcal{D}_{n}}{n}\leq\frac{3}{5}(7-8\ln 2) where \lambda is the Golomb–Dickman constant. Our main result is a proof of the convergence of \mathcal{D}_{n}/n as n approaches infinity. Theorem 1.3 . The limit \lim_{n\to\infty}\mathcal{D}_{n}/n exists. Let S_{n}^{\prime} be the set \{\rho 0:\rho\in S_{n}\} , where \rho 0 denotes the concatenation of \rho and 0 , and define the quantity \mathcal{D}^{\prime}_{n}:=\frac{1}{n!}\sum_{\rho\in S_{n}}\langle\rho 0\rangle. Defant [ 1 ] showed that the difference between \mathcal{D}^{\prime}_{n}/n and \mathcal{D}_{n}/n goes to 0 as n approaches infinity. Proposition 1.4 (Defant [ 1 , Proposition 2.9] ) . We have \lim_{n\to\infty}\left(\frac{\mathcal{D}^{\prime}_{n}}{n}-\frac{\mathcal{D}_{n}}{n}\right)=0. Thus, a proof of the convergence of \lim_{n\to\infty}\mathcal{D}^{\prime}_{n}/n is sufficient for Theorem 1.3 . As a natural consequence of the proof of Theorem 1.3 , we also obtain a means to compute lower bounds arbitrarily close to \lim_{n\to\infty}\mathcal{D}_{n}/n . Corollary 1.5 . (\mathcal{D}_{n-1}^{\prime}/n)_{n=2}^{\infty} is a monotonically increasing sequence, which converges to \lim_{n\to\infty}\mathcal{D}_{n}/n . The current author has computed \mathcal{D}^{\prime}_{n-1}/n up to n=38 , which yields the bound 0.724182\leq\lim_{n\to\infty}\frac{\mathcal{D}_{n}}{n}\leq\frac{3}{5}(7-8\ln 2). 2. Preliminaries We follow the notation and conventions of [ 3 ] with some minor discrepancies. Basic notation A composition of n , written \alpha\models n , is a tuple \alpha=(\alpha_{1},\ldots,\alpha_{k}) of positive integers summing to n . The length and width of \alpha are denoted by \ell(\alpha):=k and w(\alpha):=\max_{i\in[k]}\alpha_{i} respectively. The composition diagram of \alpha is the set D(\alpha):=\{(i,j)\in\mathbb{N}^{2}:i\leq\alpha_{j}\} along with the partial order relation \geq_{D} satisfying (i,j)\geq_{D}(i^{\prime},j^{\prime})\iff i\leq i^{\prime},\ j\leq j^{\prime}. A linear extension of (D(\alpha),\geq_{D}) is a bijection f:[n]\to D(\alpha) such that f(x)\geq_{D}f(y) implies x\geq y for all x,y\in[n] . The set of all linear extensions of D(\alpha) is denoted by \mathcal{L}(D(\alpha)) . Stack-sorting diagrams and tableaux For every permutation \pi=\rho 0\in S_{n}^{\prime} , we assign two coordinates \col_{\pi}(i) and \row_{\pi}(i) to each entry i\in[n] . The column \col_{\pi}(i) is the unique integer for which i is sent to the right of 0 when s is applied to s^{\col_{\pi}(i)-1}(\pi) . If \col_{\pi}(i)=1 , then the row \row_{\pi}(i) denotes the position of i amongst the right-to-left maxima of \rho . Otherwise, \row_{\pi}(i) is defined recursively by the equation \row_{\pi}(i)=\row_{\pi}(\leftof_{\pi}(i)), where \leftof_{\pi}(i) is the first element of s^{\col_{\pi}(i)-2}(\pi) to the right of i such that \col_{\pi}(\leftof_{\pi}(i))=\col_{\pi}(i)-1. The existence of \col_{\pi}(i) , \row_{\pi}(i) , and \leftof_{\pi}(i) are proven in [ 3 ] . Remark 2.1 . The general motivation for this framework is the observation that each element i\in[n] is sent to the right of 0 with iterative applications of s on \pi , and the permutation is sorted precisely when every element has been sent to the right of 0 . The column \col_{\pi}(i) tracks the iteration in which i is sent to the right of 0 , while \row_{\pi}(i) is responsible for tracking the relative position of i with respect to elements of the current and previous column. We now introduce the stack-sorting diagram and the stack-sorting tableau of \pi\in S_{n}^{\prime} . Let the composition \alpha_{\pi}\models n be defined such that the j th part of \alpha_{\pi} is (\alpha_{\pi})_{j}:=|\{i\in[n]:\row_{\pi}(i)=j\}|. We refer to D(\alpha_{\pi}) as the stack-sorting diagram of \pi , and the stack-sorting tableau of \pi is the map T_{\pi}:[n]\to D(\alpha_{\pi}) satisfying T_{\pi}(i):=(\col_{\pi}(i),\row_{\pi}(i)) for all i\in[n] . Example 2.2 . Consider the permutation \pi=9\ 3\ 10\ 7\ 8\ 2\ 6\ 1\ 4\ 5\ 0\in S_{10}^{\prime}. We visualize T_{\pi} in English notation below. Note that w(\alpha_{\pi})=\langle\pi\rangle=4 , and \leftof_{\pi}(T_{\pi}^{-1}(i,j)) corresponds to the entry T_{\pi}^{-1}(i-1,j) for all (i,j)\in D(\alpha_{\pi}) such that i>1 . \begin{array}[]{c}{\color[rgb]{0,0.88,0}9}\ {\color[rgb]{0,0.5,1}3}\ {\color[rgb]{0.72,0,0}10}\ {\color[rgb]{0,0.88,0}7}\ {\color[rgb]{0.72,0,0}8}\ {\color[rgb]{0,0.5,1}2}\ {\color[rgb]{0.72,0,0}6}\ {\color[rgb]{0.88,0.41,1}1}\ {\color[rgb]{0,0.88,0}4}\ {\color[rgb]{0.72,0,0}5}\ 0\\ \downarrow{s}\\ {\color[rgb]{0,0.5,1}3}\ {\color[rgb]{0,0.88,0}9}\ {\color[rgb]{0,0.88,0}7}\ {\color[rgb]{0,0.5,1}2}\ {\color[rgb]{0.88,0.41,1}1}\ {\color[rgb]{0,0.88,0}4}\ 0\ {\color[rgb]{0.72,0,0}5}\ {\color[rgb]{0.72,0,0}6}\ {\color[rgb]{0.72,0,0}8}\ {\color[rgb]{0.72,0,0}10}\\ \downarrow{s}\\ {\color[rgb]{0,0.5,1}3}\ {\color[rgb]{0.88,0.41,1}1}\ {\color[rgb]{0,0.5,1}2}\ 0\ {\color[rgb]{0,0.88,0}4}\ {\color[rgb]{0.72,0,0}5}\ {\color[rgb]{0.72,0,0}6}\ {\color[rgb]{0,0.88,0}7}\ {\color[rgb]{0.72,0,0}8}\ {\color[rgb]{0,0.88,0}9}\ {\color[rgb]{0.72,0,0}10}\\ \downarrow{s}\\ {\color[rgb]{0.88,0.41,1}1}\ 0\ {\color[rgb]{0,0.5,1}2}\ {\color[rgb]{0,0.5,1}3}\ {\color[rgb]{0,0.88,0}4}\ {\color[rgb]{0.72,0,0}5}\ {\color[rgb]{0.72,0,0}6}\ {\color[rgb]{0,0.88,0}7}\ {\color[rgb]{0.72,0,0}8}\ {\color[rgb]{0,0.88,0}9}\ {\color[rgb]{0.72,0,0}10}\\ \downarrow{s}\\ 0\ {\color[rgb]{0.88,0.41,1}1}\ {\color[rgb]{0,0.5,1}2}\ {\color[rgb]{0,0.5,1}3}\ {\color[rgb]{0,0.88,0}4}\ {\color[rgb]{0.72,0,0}5}\ {\color[rgb]{0.72,0,0}6}\ {\color[rgb]{0,0.88,0}7}\ {\color[rgb]{0.72,0,0}8}\ {\color[rgb]{0,0.88,0}9}\ {\color[rgb]{0.72,0,0}10}\end{array} {\color[rgb]{0.72,0,0}10} {\color[rgb]{0,0.5,1}3} {\color[rgb]{0.72,0,0}8} {\color[rgb]{0,0.88,0}7} {\color[rgb]{0.72,0,0}6} {\color[rgb]{0.72,0,0}5} {\color[rgb]{0.88,0.41,1}1} In general, the equality w(\alpha_{\pi})=\langle\pi\rangle holds because the number of columns in D(\alpha_{\pi}) equals the number of iterations of s required to sort \pi . Theorem 2.3 (Zhang [ 3 , Theorem 3.16] ) . For all \pi\in S_{n}^{\prime} , the map T_{\pi} is a linear extension of (D(\alpha_{\pi}),\geq_{D}) . Hook length formula for stack-sorting For every composition \alpha\models n and cell (i,j)\in D(\alpha) , let u_{\alpha}(i,j) denote \max(\{j^{\prime}\in[j-1]:\alpha_{j^{\prime}}\geq i-1\}\cup\{0\}), and define the hook length function h_{\alpha}:\mathbb{N}^{2}\to\mathbb{N} such that h_{\alpha}(i,j):=\bigl|\{(i^{\prime},j^{\prime})\in D(\alpha):i^{\prime}\leq i-1,u_{\alpha}(i,j)<j^{\prime}\leq j\}\bigr| if i>1 and h_{\alpha}(i,j):=1 if i=1 for all (i,j)\in\mathbb{N}^{2} . In words, if i>1 , then h_{\alpha}(i,j) is the number of cells between columns 1 and i-1 and rows u_{\alpha}(i,j)+1 and j . Example 2.4 . Continuing with Example 2.2 , each cell (i,j)\in D(\alpha) below is labeled with its hook length h_{\alpha}(i,j) for the composition \alpha=(3,2,1,4) . 1 2 1 1 1 1 6 Theorem 2.5 (Zhang [ 3 , Corollary 4.11] ) . For all \alpha\models n , the number of permutations \pi\in S_{n}^{\prime} satisfying \alpha_{\pi}=\alpha is N(\alpha):=|\mathcal{L}(D(\alpha))|\cdot\prod_{(i,j)\in D(\alpha)}h_{\alpha}(i,j). Theorem 2.5 is arguably the most powerful property of stack-sorting diagrams. Two

Read the complete text