Pith. sign in

REVIEW 1 major objections 1 minor 10 references

A Characterization of the $2m-4$ Case of Highly Sorted Permutations

T0 review · 1 major / 1 minor · reviewed 2026-06-27 · grok-4.3

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read The permutations sortable by exactly m-4 applications of stack-sorting on 2m-4 symbols are characterized and number B_m plus (m squared plus 7m minus 28) over 2 for m at least 5.

desk verdict Closes the 2m-4 case with a characterization and count, but the case analysis lacks independent verification. read the letter →

arxiv 2606.08429 v1 pith:CUXLU4UT submitted 2026-06-07 math.CO

Kai Yi This is my paper · ORCID
classification math.CO
keywords stack-sortingWest'smaphighlysortedpermutationsBellnumberspermutationenumerationiteratedsortingcombinatoricsonwords
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper extends earlier work on iterated stack-sorting by classifying the extra permutations that appear when the number of sorts drops to m-4 and the length is fixed at 2m-4. It shows that the total count is the Bell number B_m plus a simple quadratic polynomial in m. A reader would care because the result pins down the precise boundary between the pure Bell-number regime and the cases with additional structure, completing the picture left open by prior characterizations at depths m-3 and higher. The work also notes that the next lower depth 2m-5 behaves differently.

What carries the argument

West's stack-sorting map s applied iteratively, with the preimage sets s^k(S_n) for k = m-4 and n = 2m-4.

What would settle it

Direct enumeration of s^{m-4}(S_{2m-4}) for m=5 (so n=6) and comparison against the predicted total of 68.

Watch

Extended reading notes

Core claim

The set s^{m-4}(S_{2m-4}) consists of all m-stack-sortable permutations of length 2m-4 together with several additional families that arise exactly at this depth; these families are classified by extending the structural decomposition used for the 2m-3 case, and the resulting enumeration equals B_m plus (m^2 + 7m - 28)/2 for every m at least 5.

Load-bearing premise

The extra permutations that first appear at depth m-4 can be exhaustively listed by extending the same structural decomposition already used for depth m-3.

Editorial extensions

If this is right

  • The formula gives the exact cardinality of s^{m-4}(S_{2m-4}) for all m >= 5.
  • The 2m-5 case exhibits different additional structure than the 2m-3 and 2m-4 cases.
  • Defant's open question on the 2m-4 case is settled by the explicit characterization and count.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Similar structural arguments may produce closed formulas for s^{m-5}(S_{2m-5}) once the differing behavior is accounted for.
  • The quadratic term suggests that the number of exceptional permutations grows like the number of pairs or triples of distinguished positions inside the permutation.
  • The same counting technique could be tested on other sorting operators that admit an iterated preimage description.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit.

Referee Report

1 major / 1 minor

Summary. The paper extends Defant's 2020 characterization of the preimages under iterated West stack-sorting s^{n-m}(S_n) to the boundary case n=2m-4. It supplies an explicit structural characterization of s^{m-4}(S_{2m-4}) and proves that the cardinality equals the m-th Bell number B_m plus the quadratic correction (m^2 + 7m - 28)/2 for all m ≥ 5. The manuscript also records qualitative differences in the behavior of the still-lower 2m-5 regime.

Significance. If the case analysis is complete, the result answers the explicit question left open by Defant and supplies the first exact enumeration at this depth. The closed-form count, together with the structural description, makes the 2m-4 layer amenable to further asymptotic or bijective study and clarifies how the Bell-number regime breaks down as the iteration depth decreases.

major comments (1)
  1. [proof of the main enumeration theorem (the case division into additional forms)] The derivation of the quadratic term rests entirely on an exhaustive partition of the 'additional permutations' that first appear at depth m-4 into several disjoint structural forms (extending the 2m-3 analysis). No independent verification—small-m explicit enumeration, recurrence, or generating-function identity—is supplied to confirm that every such permutation is captured exactly once. This completeness assumption is load-bearing for both the characterization and the stated cardinality.
minor comments (1)
  1. [abstract] The abstract states the formula without indicating whether the quadratic polynomial arises from a single closed expression or from summing separate case counts; a one-sentence clarification in the introduction would help readers.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their thoughtful report and for recognizing the significance of extending Defant's characterization to the 2m-4 case. We address the single major comment below.

read point-by-point responses

  1. Referee: The derivation of the quadratic term rests entirely on an exhaustive partition of the 'additional permutations' that first appear at depth m-4 into several disjoint structural forms (extending the 2m-3 analysis). No independent verification—small-m explicit enumeration, recurrence, or generating-function identity—is supplied to confirm that every such permutation is captured exactly once. This completeness assumption is load-bearing for both the characterization and the stated cardinality.

    Authors: We agree that the enumeration theorem relies on the completeness of the case division into structural forms for the additional permutations. The proof proceeds by an exhaustive analysis of the possible configurations that require exactly m-4 iterations under s, extending the pattern-avoidance and stack-behavior arguments from the 2m-3 case in Defant (2020). While we maintain that the cases are disjoint and cover all possibilities by the recursive definition of stack-sorting, the referee is correct that no independent verification (such as direct enumeration for small m) appears in the manuscript. We will add a new subsection containing explicit computational verification of the formula for m=5 to m=9, together with a brief description of the enumeration algorithm used, to confirm that the count matches B_m plus the quadratic term in each case. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity; explicit case analysis extends external prior work

full rationale

The paper characterizes s^{m-4}(S_{2m-4}) by enumerating additional permutation forms via structural extension of Defant's (external) arguments for the 2m-3 case, then directly counts them to obtain the stated formula. No step reduces a claimed prediction or result to a fitted parameter, self-definition, or load-bearing self-citation chain inside the paper. The derivation is self-contained combinatorial casework whose validity stands or falls on the completeness of the listed forms rather than any internal tautology or renaming of inputs.

Assumptions & free parameters 0 free parameters · 0 assumptions · 0 invented entities

No free parameters, axioms, or invented entities are described in the abstract.

how reviews work

0 comments
Cite this review

Pith. "Pith review of A Characterization of the $2m-4$ Case of Highly Sorted Permutations." pith.science (2026). https://pith.science/paper/CUXLU4UT

@misc{pith2026260608429,
  author       = {Pith},
  title        = {Pith review of: A Characterization of the $2m-4$ Case of Highly Sorted Permutations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CUXLU4UT}},
  note         = {Machine review of arXiv:2606.08429}
}
abstract

Let $s$ denote West's stack-sorting map. In 2020, Defant characterized and enumerated the set $s^{n-m}(S_n)$ for $n \geq 2m-3$. While $|s^{n-m}(S_n)| = B_m$ when $n \geq 2m-2$, where $B_m$ denotes the $m$th Bell number, there are additional permutations when $n = 2m-3$. In this paper, we explore the more complex $n = 2m-4$ case, with several forms of additional permutations. We characterize $s^{m-4}(S_{2m-4})$ and find that its size is \[B_m + \frac{m^2 + 7m - 28}{2}\] for $m \geq 5$. This answers Defant's question about the $2m-4$ case. Furthermore, we find some differences in the behavior of the $2m-5$ case compared to the $2m-3$ and $2m-4$ cases.

Figures

Figures reproduced from arXiv: 2606.08429 by the authors.

Figure 1
Figure 1. Stack Sorting 15243 using West’s function [PITH_FULL_IMAGE:figures/full_fig_p002_1.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

10 extracted references · 5 canonical work pages

  1. [1]

    Knuth, Donald E.The Art of Computer Programming. 1968. Vol. 1, Addison-Wesley Professional, 1997, pp. 238–243

    1968

  2. [2]

    West, Julian.Permutations with Forbidden Subsequences, And, Stack-Sortable Permutations. 1990

    1990

  3. [3]

    5th ed., World Scientific, 2023, pp

    B´ ona, Mikl´ os.A Walk through Combinatorics. 5th ed., World Scientific, 2023, pp. 361–371

    2023

  4. [4]

    A Proof of Julian West’s Conjecture That the Number of Two-Stacksortable Permutations of Length N Is 2(3n)!/((N + 1)!(2n + 1)!)

    Doron Zeilberger. “A Proof of Julian West’s Conjecture That the Number of Two-Stacksortable Permutations of Length N Is 2(3n)!/((N + 1)!(2n + 1)!).”Discrete Mathematics, vol. 102, no. 1, May 1992, pp. 85–93, https://doi.org/10.1016/0012-365X(92)90351-F

    work page doi:10.1016/0012-365x(92)90351-f 1992

  5. [5]

    Sorted And/or Sortable Permutations

    Bousquet-M´ elou, Mireille. “Sorted And/or Sortable Permutations.”Discrete Mathematics, vol. 225, no. 1-3, 2000, pp. 25–50, https://doi.org/10.1016/S0012-365X(00)00146-1

    work page doi:10.1016/s0012-365x(00)00146-1 2000

  6. [6]

    Sorting and Preimages of Pattern Classes

    Claesson, Anders, and Henning ´Ulfarsson. “Sorting and Preimages of Pattern Classes.”Dis- crete Mathematics & Theoretical Computer Science, vol. DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012), 2012, https://doi.org/10.46298/dmtcs.3066

    work page doi:10.46298/dmtcs.3066 2012

  7. [7]

    Descents in t-Sorted Permutations

    Defant, Colin. “Descents in t-Sorted Permutations.”Journal of Combinatorics, vol. 11, no. 3, 2020, pp. 511–526, https://doi.org/10.4310/joc.2020.v11.n3.a5

    work page doi:10.4310/joc.2020.v11.n3.a5 2020

  8. [8]

    Highly Sorted Permutations and Bell Numbers

    Defant, Colin. “Highly Sorted Permutations and Bell Numbers.”Enumerative Combinatorics and Applications, vol. 2021, no. 1, 4 Dec. 2020, https://doi.org/10.54550/ECA2021V1S1R6

    work page doi:10.54550/eca2021v1s1r6 2021

Show all 10 references
  1. [9]

    A Combinatorial Interpretation of the Eigensequence for Composition

    Callan, David. “A Combinatorial Interpretation of the Eigensequence for Composition.”Journal of Integer Sequences, vol. 9, no. 1, 2006

    2006

  2. [10]

    2022, arks.princeton.edu/ark:/88435/dsp016m311s469

    Defant, Colin.Stack-Sorting and Beyond. 2022, arks.princeton.edu/ark:/88435/dsp016m311s469

    2022

Pith tools

Reviewed June 27, 2026 · model on record in the stance chip above.