The growth constant for the stack-sorting map
Let be the symmetric group, let be the stack-sorting map, and let denote its maximum fiber size. The paper considers the exponential growth rate
Stack-sorting growth conjecture. The value of this limit lies in the interval .
The interval is suggested by computations on random permutations for and .
References
Status
- Refuted: Colin Defant. Preimages under the Stack-Sorting Algorithm (arXiv, 2015) https://arxiv.org/abs/1511.05681
Source: Colin Defant and James Propp, “Quantifying Noninvertibility in Discrete Dynamical Systems”, arXiv:2002.07144 (2020).
Progress summary
A reader-submitted argument claims to refute the conjecture, but no independent source verifies it and the published literature still treats the question as open.
Defant and Propp introduced the conjecture in 2020, based on numerical experiments suggesting that the growth constant lies between and . Their paper’s degree is a collision-average quantity, whereas the problem statement describes maximum fiber size.
Known results
- For the collision-average degree, Defant and Propp prove existence of the limit and the bounds , where (2020).
Community submission (unverified) — November 7, 2026
A submitted argument claims that the Defant–Propp interval is false, asserting a lower bound of at least , exact computations through giving at least , and an approximate value near . It also claims a complete refutation, but no independently retrieved mathematical assessment supports that claim.
Current status (as of November 2026): The published collision-average formulation has only broad bounds, while the submitted refutation is unverified; the maximum-fiber formulation in the prompt has no recorded resolution.
Sources
Solutions 1
The stack-sorting degree grows faster than 1.80^n: a refutation of the Defant–Propp interval conjectureSee full solution
Source-interpretation note. The source degree is the collision-average invariant deg(f) = sum_y |f^(-1)(y)|^2 / |X|. The MathDB paraphrase calls it maximum fiber size; that is a different quantity. The substantive result below concerns the source definition, not that paraphrase.
Result and scope. Defant and Propp, arXiv:2002.07144 v3/v4 Conjecture 4.4 (Electron. J. Combin. 27(3) (2020) P3.51, Conjecture 23), restated as open by Defant (Adv. Math. 2022): the limit lies in (1.68, 1.73). False: every limit is at least 1.73 (Lean), and the exact values through n = 82 give at least 1.80468 (ordinary exact computation); the numerical value is about 1.95.
Complete proof: The stack-sorting degree grows faster than 1.80^n: a refutation of the Defant–Propp interval conjecture · PDF.
The paper page contains the supplementary proof-source JSON and extract_sources.py. The linked paper supplies the complete argument and states the precise scope of the Lean certificate, ordinary proofs, supporting computations, and source interpretation. Those qualifications are retained here; a supporting computation is not a proof of a broader statement.
This is an AI-assisted research preprint. Internal review is not external journal peer review. Bounded prior-art searches do not establish worldwide priority. See the paper for formalization and trust limits.