pith. sign in

arxiv: 2604.18626 · v1 · submitted 2026-04-18 · 🧮 math.CO

Computational Approach to the SC₂₃₁ Consecutive-Pattern-Avoiding Stack Sort

Kai Yi This is my paper

Pith reviewed 2026-05-10 07:21 UTC · model grok-4.3

classification 🧮 math.CO
keywords stack sortingconsecutive pattern avoidanceSC_231sort-numberpermutation enumerationgrowth ratescombinatorial computation
0
0 comments X

The pith

Computations up to length 14 and proven bounds show SC_231 sort-numbers grow faster than linearly in tested ranges.

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

The paper enumerates the exact number of steps each length-n permutation requires to sort under the SC_231 map for all n up to 14 and estimates the averages out to n=1000. It proves that the maximum sort-number for length n is at least n-1 and at most (n+1)(n-2)/2. A reader would care because these results give concrete information on how the consecutive 231-avoidance constraint inside the stack affects the number of passes needed, refining earlier conjectures that were disproved by other authors. The data indicate both the maximum and the average increase faster than linearly for the computed values, although the ultimate growth rate is left open.

Core claim

Through exhaustive enumeration, the SC_231 map produces sort-numbers whose maximum and average both exceed linear growth for n up to 14 and n up to 1000 respectively; the paper proves the maximum sort-number of any length-n permutation is bounded below by n-1 and above by (n+1)(n-2)/2.

What carries the argument

The SC_231 map, the stack-sorting procedure in which the stack is required to avoid the consecutive pattern 231 after every push or pop.

If this is right

  • The maximum sort-number lies between n-1 and (n+1)(n-2)/2 for every n.
  • Average sort-numbers appear to grow faster than linear at least up to length 1000.
  • Long-term asymptotic behavior of the maximum and average remains undetermined by the given data.
  • Earlier conjectures on the growth rate are refined by the combination of computation and the explicit bounds.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The quadratic upper bound implies that the 231-avoidance constraint does not reduce worst-case sorting cost below quadratic order.
  • Repeating the enumeration for n=15 or 16 would provide a direct test of whether the superlinear trend continues.
  • The same computational strategy could be applied to the other consecutive patterns SC_132 and SC_123 to compare their growth rates.
  • The observed gap between the linear lower bound and quadratic upper bound leaves room for a tighter asymptotic analysis.

Load-bearing premise

The program that enumerates and sorts every permutation of length 14 applies the SC_231 rule correctly and without omissions or implementation mistakes.

What would settle it

A verified computation of the maximum sort-number for some permutation of length 15 that lies outside the interval [14, 104] would contradict the proven bounds, while an average that remains strictly linear through n=100 would undermine the observed superlinear trend.

Figures

Figures reproduced from arXiv: 2604.18626 by Kai Yi.

Figure 1
Figure 1. Figure 1: Stack Sorting 15243 using West’s function [PITH_FULL_IMAGE:figures/full_fig_p001_1.png] view at source ↗
Figure 6
Figure 6. Figure 6: Diagram of Length 4 Permutations, Color-Coded by Distance Between Entries 1 and 2 [PITH_FULL_IMAGE:figures/full_fig_p006_6.png] view at source ↗
read the original abstract

Defant and Zheng introduced a consecutive-pattern-avoiding stack sort map $SC_{\sigma}$, where the stack must avoid a consecutive pattern $\sigma$. Seidel and Sun disproved a conjecture in Defant and Zheng's paper about the maximum sort-number of a length $n$ permutation under $SC_{231}$. In this paper, we compute sort-numbers for each permutation of length up to $14$, and we estimate the average sort-numbers up to length $1000$. Our results suggest the maximum and average sort-numbers grow faster than linear with respect to $n$ for the tested ranges, though the long-term behavior remains unclear. We also prove properties of $SC_{231}$ mathematically, such as a $n-1$ lower bound and a $\frac{(n+1)(n-2)}{2}$ upper bound for the maximum sort-number of length $n$ permutations.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

2 major / 2 minor

Summary. The paper computationally enumerates the sort-numbers under the SC_231 consecutive-pattern-avoiding stack sort for all permutations of length at most 14 and estimates average sort-numbers up to length 1000. It also proves a lower bound of n-1 and an upper bound of (n+1)(n-2)/2 on the maximum sort-number for permutations of length n. The authors suggest, based on the data, that both the maximum and average sort-numbers grow faster than linearly with n over the tested ranges, while noting that the long-term asymptotic behavior is unclear.

Significance. The two explicit mathematical bounds are rigorous and independent of the computations, supplying concrete constraints on the complexity of this sorting map. The enumeration and estimates supply new empirical data that can guide future work on the growth rate of sort-numbers under consecutive-pattern-avoiding stack sorts, particularly in light of the earlier conjecture disproved by Seidel and Sun.

major comments (2)
  1. [Computational results section] Computational results section: the suggestion that maximum and average sort-numbers grow faster than linearly rests on exhaustive enumeration up to n=14 together with estimates to n=1000. Because 14! exceeds 8.7×10^10, the enumeration cannot be brute-force; the manuscript must therefore describe the algorithm, data structures, and verification steps used to compute the SC_231 map and tally iteration counts. Without these details the observed trend cannot be independently confirmed.
  2. [Growth-rate discussion] Growth-rate discussion: the upper bound (n+1)(n-2)/2 is quadratic while the lower bound is linear, so the data are consistent with any superlinear rate up to quadratic. The manuscript correctly qualifies the claim as holding only for the tested ranges, but the absence of either an asymptotic proof or a statistical model fitted to the n=14 data leaves the central empirical suggestion dependent on the correctness of the small-n implementation.
minor comments (2)
  1. [Abstract] The abstract states that sort-numbers are computed 'for each permutation of length up to 14'; it would be clearer to add 'all' to emphasize exhaustiveness.
  2. [Computational results section] The notation SC_231 is introduced in the abstract but should be recalled with a one-sentence definition when the computational results are first presented.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful and constructive report. We address each major comment below and will revise the manuscript to improve clarity and reproducibility.

read point-by-point responses

  1. Referee: [Computational results section] Computational results section: the suggestion that maximum and average sort-numbers grow faster than linearly rests on exhaustive enumeration up to n=14 together with estimates to n=1000. Because 14! exceeds 8.7×10^10, the enumeration cannot be brute-force; the manuscript must therefore describe the algorithm, data structures, and verification steps used to compute the SC_231 map and tally iteration counts. Without these details the observed trend cannot be independently confirmed.

    Authors: We agree that a detailed description of the computational methods is required for independent verification. In the revised manuscript we will expand the Computational Results section with a dedicated subsection that describes the recursive algorithm for applying the SC_231 map, the data structures (including memoization tables and permutation representations) used to avoid brute-force enumeration, and the verification procedures (consistency checks against smaller n, cross-validation with the proven bounds, and sample manual checks). revision: yes

  2. Referee: [Growth-rate discussion] Growth-rate discussion: the upper bound (n+1)(n-2)/2 is quadratic while the lower bound is linear, so the data are consistent with any superlinear rate up to quadratic. The manuscript correctly qualifies the claim as holding only for the tested ranges, but the absence of either an asymptotic proof or a statistical model fitted to the n=14 data leaves the central empirical suggestion dependent on the correctness of the small-n implementation.

    Authors: We acknowledge that the linear-to-quadratic bounds permit a range of superlinear behaviors and that our empirical suggestion rests on the computed data. In revision we will strengthen the growth-rate discussion by explicitly noting the absence of an asymptotic proof or fitted statistical model, reiterating the dependence on implementation correctness, and adding a forward-looking remark that theoretical analysis of the long-term growth rate remains an open direction. revision: partial

Circularity Check

0 steps flagged

No significant circularity; derivations are independent enumerations and combinatorial proofs

full rationale

The paper computes sort-numbers via exhaustive enumeration of all permutations of length <=14 and provides separate estimates for averages up to n=1000; these are direct applications of the SC_231 map definition rather than fitted parameters renamed as predictions. The n-1 lower bound and (n+1)(n-2)/2 upper bound on maximum sort-number are proved mathematically from combinatorial arguments on the stack-avoidance rules, without reference to the computational data or self-citations. No steps reduce by construction to prior inputs, self-definitions, or author-overlapping citations that bear the central load. The suggestion of superlinear growth is an observation from the enumerated values, not a claim that loops back to the inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on standard combinatorial definitions of permutations, consecutive patterns, and stack-sorting operators; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Permutations are bijective sequences from 1 to n; consecutive pattern avoidance and stack operations follow the standard definitions in the literature.
    These are background definitions from prior work on permutation patterns and sorting maps.

pith-pipeline@v0.9.0 · 5446 in / 1328 out tokens · 59080 ms · 2026-05-10T07:21:15.184824+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

9 extracted references · 9 canonical work pages

  1. [1]

    The Art of Computer Programming, Volume 1: Fundamental Algorithms

    Knuth, Donald E. The Art of Computer Programming, Volume 1: Fundamental Algorithms. Addison-Wesley, 1973

    work page 1973

  2. [2]

    Permutations with restricted subsequences and stack-sortable permutations

    West, J. Permutations with restricted subsequences and stack-sortable permutations. Ph.D. Thesis, MIT, 1990. 10

    work page 1990

  3. [3]

    Stack Sorting with Restricted Stacks

    Cerbai, Giulio, et al. “Stack Sorting with Restricted Stacks.”Journal of Combinatorial Theory Series A, vol. 173, July 2020, https://doi.org/10.1016/j.jcta.2020.105230

    work page doi:10.1016/j.jcta.2020.105230 2020

  4. [4]

    Stack-Sorting with Consecutive-Pattern- Avoiding Stacks

    Defant, Colin, and Kai Zheng. “Stack-Sorting with Consecutive-Pattern- Avoiding Stacks.”Advances in Applied Mathematics, vol. 128, 18 Mar. 2021, https://doi.org/10.1016/j.aam.2021.102192. Accessed 24 June 2025

    work page doi:10.1016/j.aam.2021.102192 2021

  5. [5]

    Periodic Points of Consecutive-Pattern-Avoiding Stack-Sorting Maps

    Seidel, Ilaria, and Nathan Sun. “Periodic Points of Consecutive-Pattern-Avoiding Stack-Sorting Maps.”2308.05868, arXiv, Aug. 2023, arxiv.org/pdf/2308.05868. Accessed 28 June 2025

    work page arXiv 2023

  6. [6]

    Stack-Sorting with Stacks Avoiding Vincular Patterns

    Zhao, William. “Stack-Sorting with Stacks Avoiding Vincular Patterns.” ArXiv.org, 2024, arxiv.org/abs/2410.17057. Accessed 30 Mar. 2026

    work page arXiv 2024

  7. [7]

    Fertility Numbers of Consecutive S3 Pattern-Avoiding Stack-Sorting Maps

    Kemeklis, Jurgis. “Fertility Numbers of Consecutive S3 Pattern-Avoiding Stack-Sorting Maps.” ArXiv.org, 15 Sept. 2024, arxiv.org/abs/2408.05378. Accessed 2 Apr. 2026

    work page arXiv 2024

  8. [8]

    Shuffle a given Array Using Fisher–Yates Shuffle Algorithm

    GeeksforGeeks. “Shuffle a given Array Using Fisher–Yates Shuffle Algorithm.” Geeks- forGeeks, 10 Oct. 2012, www.geeksforgeeks.org/dsa/shuffle-a-given-array-using-fisher-yates- shuffle-algorithm/

    work page 2012

  9. [9]

    Sc231 Stats v2

    Yi, Kai. “Sc231 Stats v2.” Desmos, 17 Apr. 2026, https://www.desmos.com/calculator/gamyae9s0y. Accessed 17 Apr. 2026

    work page 2026