← All problems

The growth constant for the stack-sorting map

6 years old · traced to

Let SnS_n be the symmetric group, let s:Sn→Sns:S_n\to S_n be the stack-sorting map, and let deg⁡(s:Sn→Sn)\deg(s:S_n\to S_n) denote its maximum fiber size. The paper considers the exponential growth rate

lim⁡n→∞deg⁡(s:Sn→Sn)1/n.\lim\limits_{n\to\infty}\deg(s:S_n\to S_n)^{1/n}.

Stack-sorting growth conjecture. The value of this limit lies in the interval (1.68,1.73)(1.68,1.73).

The interval is suggested by computations on random permutations for n=100n=100 and n=300n=300.

References

Status

Source: Colin Defant and James Propp, “Quantifying Noninvertibility in Discrete Dynamical Systems”, arXiv:2002.07144 (2020).

Progress summary

Refreshed
Open · progress reported

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 1.681.68 and 1.731.73. 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 1.12462≤L≤41.12462 \le L \le 4, where L=lim⁡n→∞deg⁡(s:Sn→Sn)1/nL=\lim_{n\to\infty}\deg(s:S_n\to S_n)^{1/n} (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 1.731.73, exact computations through n=82n=82 giving at least 1.804681.80468, and an approximate value near 1.951.95. 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 solutionHide 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.