Counting pop-stacked permutations in polynomial time

Anders Claesson; Bjarki \'Ag\'ust Gu{\dh}mundsson; Jay Pantone

REVIEW 2 major objections 5 minor 11 references

Counting pop-stacked permutations in polynomial time

T0 review · 2 major / 5 minor · reviewed 2026-08-14 · deepseek-v4-flash

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

Pith's one-line read A polynomial-time algorithm counts pop-stacked permutations through length 1000 and computes the first 1000 terms.

desk verdict Solid counting paper with a reproducible DP and 1000 terms; the 'rigorous' negative GF results are credible but underdocumented. read the letter →

arxiv 1908.08910 v1 pith:NMXPYNFV submitted 2019-08-23 math.CO

Anders Claesson , Bjarki Ágúst Gu{ḥmundsson , Jay Pantone This is my paper · ORCID

classification math.CO MSC 05A0505A1505A16

keywords pop-stackedpermutationspop-stacksortingoverlappingballotsdynamicprogrammingpermutationenumerationgeneratingfunctionsasymptoticanalysisdifferentialapproximation

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 establishes that pop-stacked permutations—permutations obtainable as the output of a single pop-stack pass—can be counted exactly by dynamic programming, and it computes the number of such permutations of every length up to 1000. Only the first 16 counts were known before. The 1000 terms let the authors prove quantitative negative results about the generating function: a rational form, for instance, would have to have numerator or denominator degree at least 500, with analogous lower bounds for algebraic and D-finite forms. The data also yields a numerical prediction that the $n$th count behaves like $0.6957 \cdot n! \cdot 0.8981^n$. The method works by counting overlapping ballots rather than permutations directly.

What carries the argument

The load-bearing object is the overlapping ballot: an ordered set partition whose adjacent blocks overlap in their min–max intervals, which is equivalent to the ascending-run decomposition of a pop-stacked permutation. The argument is carried by recurrence (2) for $f_{c,d}(n)$, the number of overlapping ballots of $[n]$ whose last block has minimum $c$ and maximum $d$; it splits the ballot into a last block $B$ and a preceding overlapping ballot, rescales the preceding ballot to a smaller ground set, and sums over all ways to choose $B$. The prefix-sum identity (4), $g_{c,d}(n) = f_{c,d}(n) + g_{c-1,d}(n) + g_{c,d-1}(n) - g_{c-1,d-1}(n)$, collapses the two-dimensional sums inside the recurrence to constant-time lookups, which is what makes the dynamic program run in polynomial time: $O(N^4)$ time and $O(N^3)$ memory for the plain counts, and $O(N^5)$ time when the number of ascending runs is tracked as well.

What would settle it

Exhaustively enumerate all permutations of length up to 10, apply the pop-stack map to each, count the distinct outputs, and compare with the tabulated values $f(1), \dots, f(10)$; a mismatch would show the recurrence is wrong.

Watch

Extended reading notes

Core claim

At the center of the paper is the observation that pop-stacked permutations are exactly the permutations whose ascending-run decomposition forms an overlapping ballot: consecutive blocks have intervals $[\min B_i, \max B_i]$ and $[\min B_{i+1}, \max B_{i+1}]$ that intersect. Counting overlapping ballots on $[n]$ therefore counts pop-stacked permutations, and the paper provides a recurrence that decomposes the family of such ballots according to the last block, reducing the count to prefix sums. This recurrence is evaluated by dynamic programming in $O(N^4)$ time and $O(N^3)$ memory, producing $f(1), \dots, f(1000)$; because the values are large, the computation is carried out modulo many small primes and reassembled by modular arithmetic. The resulting sequence supports rigorous lower bounds on the generating function's complexity—any rational representation must have numerator or denominator degree at least 500, any algebraic representation must satisfy $(m+1)(d+1) > 1000$, and any D-finite representation (satisfying a linear differential equation with polynomial coefficients) must satisfy $(k+2)(d+1) > 1000$—and differential approximation predicts $f(n) \sim C\, n!\, \rho^n$ with $\rho \approx 0.898118$ and $C \approx 0.695688$.

Load-bearing premise

Everything rests on the recurrence's decomposition of overlapping ballots being complete and non-overlapping; if that recursive split into a last block and a preceding ballot misses any ballot or counts any twice, the 1000 computed terms are wrong.

Editorial extensions

If this is right

The exact count of pop-stacked permutations is now known for every length through 1000, where previously only 16 terms were available.
If the ordinary generating function is rational, its numerator or denominator must have degree at least 500; analogous parameter lower bounds hold for algebraic ($(m+1)(d+1)>1000$) and D-finite ($(k+2)(d+1)>1000$) forms.
For a fixed number $k$ of ascending runs, the rational generating functions are verified for $k \le 6$, and data through $k=24$ matches the conjectured denominator $\prod_{i=1}^k (1-ix)^{k-i+1}$.
Differential approximation predicts the asymptotic growth $f(n) \sim 0.695688 \cdot n! \cdot 0.898118^n$, and predicts that the exponential generating function has simple poles on the positive real axis.

Reading between the lines

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

The same dynamic program can likely be adapted to track other statistics of the last block (size, min, max, or number of blocks), producing refined counting sequences that may be easier to fit than the univariate sequence.
If the conjectured denominator for $F_k(x)$ holds, summing over $k$ may reveal that the bivariate generating function has a natural boundary, which would explain the predicted infinite singularities and the apparent non-D-finiteness.
The negative fitting results are inherently limited to the parameter ranges searched; a rational, algebraic, or D-finite generating function with larger degree or order is not ruled out by the 1000 terms.
The same automated-fitting lower bounds could be applied to other combinatorial sequences with long initial terms, giving rigorous complexity floors for their generating functions.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Quick take: the core contribution is the polynomial-time recurrence and the 1000-term sequence, and that part is solid. The negative results in §3.1 are probably true but the paper doesn't fully document the exhaustive search, so the word 'rigorous' there outruns what's shown.

The new algorithmic idea is the overlapping-ballot decomposition with prefix sums. The recurrence (5) checks out structurally: the case analysis for c=d and c

Where it gets soft: §3.1 asserts unconditional lower bounds on rational/algebraic/D-finite forms. The logic is fine—if no solution exists to the linear system for a given (d,m,k), then that class is ruled out—but the paper never states the search bounds explicitly. 'We used GuessFunc' and 'found no conjectured form' is not the same as 'we exhaustively checked all (m+1)(d+1) ≤ 1000.' Without that statement, or a short description of the package's search strategy, the bullets are not demonstrated. The footnote in §3.2 shows awareness that degree bounds are unknown for fixed k, which makes the global claim even more in need of a precise search space. That said, the code is available, so the negative results are reproducible; the issue is documentation, not necessarily correctness. It should be fixed in revision rather than cause rejection.

The asymptotic prediction in §3.3 is honestly labeled experimental, and the dominant-singularity estimate is extremely precise. I'd have no problem with that as a conjecture.

Who's this for: permutation pattern / pop-stack researchers and anyone working on polynomial-time enumeration via DP. The paper is worth a serious referee; the central enumeration result is new and correct, and the §3.1 claims need tightening rather than redoing. I'd accept with revisions, or accept after the authors add the missing search bounds.

Referee Report

2 major / 5 minor

Summary. The paper presents a dynamic-programming algorithm for counting pop-stacked permutations of length n, based on a decomposition of overlapping ballots into their ascending runs. The recurrence is simplified with prefix sums to run in O(N^4) time and O(N^3) memory, and the authors use it to compute the first 1000 terms of the counting sequence, far beyond the previously known 16 terms. The paper also uses an automated fitting package, GuessFunc, to claim rigorous negative results on the rationality, algebraicity, and D-finiteness of the generating function, and it uses differential approximation to predict asymptotic growth of the form C * n! * rho^n with rho ≈ 0.898118 and C ≈ 0.695688. The enumeration algorithm and the computed terms are the main contribution; the negative results and asymptotic prediction are presented as rigorous and experimental, respectively.

Significance. If the enumeration result stands, it is a valuable contribution: it turns a sequence that was previously only computed to length 16 into a sequence of 1000 terms, and the overlapping-ballot decomposition may be reusable for related enumeration problems. The O(N^4) algorithm is clearly explained, and the use of modular arithmetic and the Chinese Remainder Theorem is a sensible practical approach. The negative results in Section 3.1, if properly supported, would be significant, though as written they are not fully demonstrated. The paper is honest about the experimental nature of the asymptotic prediction, and it provides code and data on GitHub, which is commendable.

major comments (2)

[§3.1 (p. 7), bullets after 'From this we can conclude rigorously'] The three bullets claiming rigorous negative results are not supported by the evidence presented in the manuscript. The only evidence is that the authors used the package GuessFunc and it found no fit; the text does not specify the exact linear systems solved, the ranges of degrees and orders exhaustively searched, the precision or exactness of the arithmetic, or any certificate that would let a reader verify the no-solution claim. A fitting search that finds no solution in some finite range does not prove that no solution exists with (m+1)(d+1) ≤ 1000 or (k+2)(d+1) ≤ 1000 unless the search is provably exhaustive over all degrees and orders in that range and every linear algebra step is exact. Please provide the package or a precise description of its search space and rank computations, and an independent verification route (for example, the computed coefficients modulo several primes and a script that recomputes the claimed no-fit conclusions), or downgrade these bullets from 'rigorously' to conditional or conjectural statements.
[§3.1, D-algebraic paragraph] The statement that no D-algebraic form was found is not reproducible because no finite-dimensional search space is defined for the multivariate polynomial P that would be sought. The text explicitly defers the explanation and does not state what degrees or orders were tried. As written, the abstract-level claim that the authors 'prove some negative results' cannot be checked for the D-algebraic case. Either define the search space and report exhaustive results for it, or remove the D-algebraic claim from the summary of conclusions.

minor comments (5)

[§3.2, displayed formula for F3(x)] The displayed denominator for F3(x) appears to contain a typo: it is written as (1 − 3x)(1 − 2x)^2(1 − 3x)^3, which repeats the factor (1 − 3x) and omits the expected (1 − x) factor. This is inconsistent with the pattern of F1, F2, F4 and with Conjecture 2. Please check the intended formula.
[Table 1] Several entries in the rows for n = 42 through n = 45 are broken across line breaks in the table (for example, the value for n = 42 is split as '...0923671 1'). Please typeset each integer on a single line or otherwise separate digits so the numbers cannot be misread.
[§3.3] The list of predicted singularities is truncated in the text, with a note that more digits are available; it would improve clarity to state explicitly that the list is a representative sample and that the complete table is available on GitHub.
[§2, recurrence (2)] The notation [c = 1 ∧ d = n] for the Iverson bracket is standard but might be easily confused with a set; consider adding a sentence reminding the reader that this term is 1 exactly when c = 1 and d = n, and 0 otherwise.
[§3.2, footnote 1] The footnote correctly caveats that the number of terms needed to find Fk(x) is unknown and only exponentially bounded; this caveat is important enough to be moved into the main text, since it directly affects how strongly the rational fits for Fk(x) should be interpreted.

Circularity Check

0 steps flagged · score 2.0 of 10

Core enumeration recurrence is self-contained; the asymptotic 'prediction' is transparently empirical and the negative-result proof has a verification gap, but neither rises to circularity.

full rationale

The central derivation is Section 2's recurrence (Eqs. 1--5), which counts pop-stacked permutations by decomposing them into overlapping ballots. This decomposition uses the independent characterization of Asinowski et al. (Theorem 1), not the paper's own output, and the recurrence is not defined in terms of the counting sequence it is meant to produce. The DP and CRT computation of 1000 terms is code-reproduced on GitHub and does not fit any parameter to the target sequence. The negative results in Section 3.1 ('If F(x) is rational, then either the degree of the denominator or the degree of the numerator is at least 500') are rigorous only if GuessFunc made an exhaustive exact search, but the paper gives no algorithm, search bounds, or certificate for GuessFunc. That is a missing-proof/verification gap, not circularity, because the implication from 'no fit found' to the degree bounds is logically valid and the underlying 1000 terms are independently computed. The differential approximation in Section 3.3 is explicitly labeled experimental ('Obviously such an analysis is only experimental'), and the constants mu and C are estimates obtained from a fitted differential equation; the paper does not present them as first-principles derivations, so this is an honest empirical extrapolation rather than a fitted input disguised as a prediction. The only self-citation, Claesson-Gudmundsson [3], is motivational and not load-bearing. Overall the main enumeration claim is self-contained and non-circular; the minor issues are rigor and reproducibility of the black-box fitting claims, not circularity.

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

The central enumeration is built on the cited characterization of pop-stacked permutations, which is taken as a domain assumption. The experimental analysis assumes the reliability of differential approximation and the authors' fitting package. No new entities are introduced.

free parameters (2)

mu (dominant singularity of the EGF) = 1.1134390417367270...
Obtained by differential approximation from the first 1000 computed terms. Used to predict the exponential growth rate 1/mu ~ 0.898118318.
C (multiplicative constant in the asymptotics) = 0.6956885490706357...
Computed numerically from the fitted mu and the initial terms. Not derived from first principles.

assumptions (4)

domain assumption A permutation is pop-stacked if and only if each pair of adjacent ascending runs overlaps (Theorem 1 of Asinowski et al.).
The ballot model and the entire counting recurrence rest on this characterization. The paper cites [1] but does not prove it.
domain assumption The ascending-run decomposition of a permutation corresponds bijectively to ballots satisfying max B_i > min B_{i+1} and min B_i < max B_{i+1}.
This is the bridge between permutations and overlapping ballots; it follows from Theorem 1 but is used as a working definition.
domain assumption Differential approximation correctly estimates singularity locations and critical exponents from a finite number of initial terms.
The asymptotic prediction in Section 3.3 is a heuristic; the paper itself states 'such an analysis is only experimental'.
ad hoc to paper The GuessFunc package by the third author searches the specified parameter spaces exhaustively and performs exact linear algebra, so the absence of a fit implies non-existence.
The rigorous negative results in Section 3.1 depend on this self-written, unpublished software being correct. The paper does not flag this as an unverified assumption.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Counting pop-stacked permutations in polynomial time." pith.science (2026). https://pith.science/paper/NMXPYNFV

@misc{pith2026190808910,
  author       = {Pith},
  title        = {Pith review of: Counting pop-stacked permutations in polynomial time},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NMXPYNFV}},
  note         = {Machine review of arXiv:1908.08910}
}

read the original abstract

Permutations in the image of the pop-stack operator are said to be pop-stacked. We give a polynomial-time algorithm to count pop-stacked permutations up to a fixed length and we use it to compute the first 1000 terms of the corresponding counting sequence. Only the first 16 terms had previously been computed. With the 1000 terms we prove some negative results concerning the nature of the generating function for pop-stacked permutations. We also predict the asymptotic behavior of the counting sequence using differential approximation.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

11 extracted references · 11 canonical work pages

[1]

Pop-stack sorting and its image: Permutat ions with over- lapping runs

Andrei Asinowski, Cyril Banderier, Sara Billey, Benjam in Hackl, and Svante Linusson. Pop-stack sorting and its image: Permutat ions with over- lapping runs. To appear in Eurocomb 2019

work page 2019
[2]

On pop-stacks in series

David A vis and Monroe Newborn. On pop-stacks in series. Utilitas Math , 19(129-140):410, 1981

work page 1981
[3]

Enumerat ing permu- tations sortable by k passes through a pop-stack

Anders Claesson and Bjarki Ágúst Guðmundsson. Enumerat ing permu- tations sortable by k passes through a pop-stack. Adv. in Appl. Math. , 108:79–96, 2019

work page 2019
[4]

Enumerating the pop-stacked permutations

Anders Claesson, Bjarki Ágúst Guðmundsson, and Jay Pantone. Enumerating the pop-stacked permutations. https://github.com/SuprDewd/pop-stacked-perms

work page
[5]

Asymptotic analysis of power-serie s expansions

Anthony J Guttmann. Asymptotic analysis of power-serie s expansions. Phase transitions and critical phenomena , 13:1–234, 1989

work page 1989
[6]

Series analysis

Anthony J Guttmann and Iwan Jensen. Series analysis. In Polygons, polyominoes and polycubes , volume 775 of Lecture Notes in Phys. , pages 181–202. Springer, Dordrecht, 2009

work page 2009
[7]

Extended rate, more G FUN

Waldemar Hebisch and Martin Rubey. Extended rate, more G FUN. J. Symbolic Comput., 46(8):889–903, 2011

work page 2011
[8]

IHPC - Icelandic High Performance Compu ter - University of Iceland and Reykjavik University, 2019

Garpur cluster. IHPC - Icelandic High Performance Compu ter - University of Iceland and Reykjavik University, 2019

work page 2019

Show all 11 references

[9]

Guess: A Mathematica package for guessin g multivariate recurrence equations

Manuel Kauers. Guess: A Mathematica package for guessin g multivariate recurrence equations. Research Institute for Symbolic Computation
[10]

GFUN: A Maple package f or the manipulation of generating and holonomic functions in one v ariable

Bruno Salvy and Paul Zimmermann. GFUN: A Maple package f or the manipulation of generating and holonomic functions in one v ariable. ACM Trans. Math. Softw. , 20(2):163–177, June 1994. 11

1994
[11]

Neil J. A. Sloane. The Online Encyclopedia of Integer Se quences. https://oeis.org, 2019. 12

2019

Pith tools

Reviewed August 14, 2026 · model on record in the stance chip above.

[1] [1]

Pop-stack sorting and its image: Permutat ions with over- lapping runs

Andrei Asinowski, Cyril Banderier, Sara Billey, Benjam in Hackl, and Svante Linusson. Pop-stack sorting and its image: Permutat ions with over- lapping runs. To appear in Eurocomb 2019

work page 2019

[2] [2]

On pop-stacks in series

David A vis and Monroe Newborn. On pop-stacks in series. Utilitas Math , 19(129-140):410, 1981

work page 1981

[3] [3]

Enumerat ing permu- tations sortable by k passes through a pop-stack

Anders Claesson and Bjarki Ágúst Guðmundsson. Enumerat ing permu- tations sortable by k passes through a pop-stack. Adv. in Appl. Math. , 108:79–96, 2019

work page 2019

[4] [4]

Enumerating the pop-stacked permutations

Anders Claesson, Bjarki Ágúst Guðmundsson, and Jay Pantone. Enumerating the pop-stacked permutations. https://github.com/SuprDewd/pop-stacked-perms

work page

[5] [5]

Asymptotic analysis of power-serie s expansions

Anthony J Guttmann. Asymptotic analysis of power-serie s expansions. Phase transitions and critical phenomena , 13:1–234, 1989

work page 1989

[6] [6]

Series analysis

Anthony J Guttmann and Iwan Jensen. Series analysis. In Polygons, polyominoes and polycubes , volume 775 of Lecture Notes in Phys. , pages 181–202. Springer, Dordrecht, 2009

work page 2009

[7] [7]

Extended rate, more G FUN

Waldemar Hebisch and Martin Rubey. Extended rate, more G FUN. J. Symbolic Comput., 46(8):889–903, 2011

work page 2011

[8] [8]

IHPC - Icelandic High Performance Compu ter - University of Iceland and Reykjavik University, 2019

Garpur cluster. IHPC - Icelandic High Performance Compu ter - University of Iceland and Reykjavik University, 2019

work page 2019