{"id":"bc7e60e2-499b-4658-97cb-4c269b0d0313","arxiv_id":"1908.08910","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":2,"one_line_summary":"A dynamic-programming recurrence over overlapping ballots counts pop-stacked permutations in polynomial time, producing 1000 terms and rigorous bounds on the generating function.","lead":"The authors give a polynomial-time algorithm to count pop-stacked permutations, expanding the known sequence from 16 terms to 1000. Using the new terms, they rule out simple forms for the generating function and predict its asymptotic growth.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The enumeration recurrence looks correct, but the 'rigorous' negative results in §3.1 rest on an unpublished custom fitting package with no stated exhaustive search bounds; without an exact independent check, those bullets are unproven.","rationale":"The reader's weakest assumption was the completeness of the recurrence decomposition. I tested that decomposition carefully: the bijection behind equation (1) holds because removing the last block B and compressing by order-preserving relabeling maps the overlap conditions min<d and max>c exactly to the rank bounds a≤d−ℓ−2 and b≥c. The recurrence reproduces the first several values by hand, and the prefix-sum simplification is algebraically correct. So the central enumeration claim is sound. The genuine soft spot is the paper's claim to prove negative results on the generating function. Those results are advertised as rigorous in the abstract and in the three bullets of §3.1, yet the only evidence cited is an unpublished package, GuessFunc, by the third author, with no specification of the search space, no exact linear algebra details, and no output certificates. Without knowing that the package searched exhaustively within the stated parameter bounds, 'found no conjectured fit' is not the same as 'proved impossible.' This is particularly important because the package is also used to produce the rational fits for Fk(x) in §3.2, where the footnote admits the required number of terms is unknown. The concrete test would settle the rational bullet by direct linear algebra over Q using the published terms; if the test passes, the concern is resolved. I therefore recommend conditional acceptance: the main polynomial-time counting contribution is solid, but the negative-results section should either be backed by an independent exact exhaustive computation or be relabeled as experimental.","tokens_in":8355,"tokens_out":21927,"duration_ms":214027,"concrete_test":"Using the 1000 coefficients published on the GitHub repository, for each d=1,…,499 form the homogeneous linear system over Q with unknowns q0,…,qd and equations given by the coefficients of x^{d+1},…,x^{1000} in q(x)F(x). If any nontrivial solution q(x) exists for some d≤499, the rational bullet is false; if none exists, the rational bullet is confirmed. Solve this with exact rational arithmetic or with CRT modulo enough primes, preferably using an independent implementation. Separately repeat the same exact-rank test for the algebraic and D-finite systems over all parameter pairs with (m+1)(d+1)≤1000 and (k+2)(d+1)≤1000. Optionally, run GuessFunc on the known rational Fk(x) for k=5 and k=6 to confirm that the package returns the known rational fit when the data is rational.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"After checking the decomposition (1) and recurrence (5) against small cases, I find no error in the counting DP: the rescaling bounds a≤d−ℓ−2 and b≥c follow from counting elements of [n]\\B less than d and greater than c, and the prefix-sum form (4) is standard. The load-bearing weakness is instead in §3.1. The abstract says the 1000 terms 'prove' negative results on rationality/algebraicity/D-finiteness, and the paper states three unconditional bullets, e.g., that rationality implies max(deg p, deg q)≥500. But the only evidence is: 'We have used a different package, GuessFunc, written by the third author.' No algorithm, search bounds, or exact-arithmetic certificate is given, and no independent verification is provided. A guesser that searches a limited degree/order range and finds nothing does not, by itself, prove absence in the full range (m+1)(d+1)≤1000 or (k+2)(d+1)≤1000. The footnote in §3.2 even concedes that for fixed k the degree needed is unknown and only bounded exponentially; the global no-fit claim needs at least as much care. Thus the lower-bound bullets may be true, but as written they are not demonstrated. The 1000-term count and the algorithm do not depend on this, so the main enumeration claim is unaffected.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":8677,"tokens_out":6453,"duration_ms":66796,"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":[{"comment":"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.","section":"§3.1 (p. 7), bullets after 'From this we can conclude rigorously'"},{"comment":"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.","section":"§3.1, D-algebraic paragraph"}],"minor_comments":[{"comment":"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.","section":"§3.2, displayed formula for F3(x)"},{"comment":"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.","section":"Table 1"},{"comment":"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.","section":"§3.3"},{"comment":"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.","section":"§2, recurrence (2)"},{"comment":"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.","section":"§3.2, footnote 1"}],"recommendation":"major_revision","confidential_remarks":"The enumeration algorithm and the 1000-term computation appear sound and are the strongest part of the paper. My recommendation is driven by the gap between the word 'prove' and the undocumented GuessFunc search behind the negative results in §3.1. If the authors can supply the package or a verifiable certificate, I would support acceptance; otherwise those claims should be reframed as empirical or conditional. The paper is otherwise well within the journal's scope."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","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.\n\nThe 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<d is sound, the rescaling bounds are correct, and the prefix-sum transformation is standard. The CRT/parallel computation is a nice practical touch, and shipping the code and data on GitHub makes the 1000-term claim independently checkable. The fixed-k generating functions and Conjecture 2 are reasonable experimental byproducts.\n\nWhere 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.\n\nThe 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.\n\nWho'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.","headline":"Solid counting paper with a reproducible DP and 1000 terms; the 'rigorous' negative GF results are credible but underdocumented.","tokens_in":9156,"tokens_out":2399,"would_cite":true,"duration_ms":23774,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A05","05A15","05A16"],"pacs":[],"model":"deepseek-v4-flash","headline":"A polynomial-time algorithm counts pop-stacked permutations through length 1000 and computes the first 1000 terms.","keywords":["pop-stacked permutations","pop-stack sorting","overlapping ballots","dynamic programming","permutation enumeration","generating functions","asymptotic analysis","differential approximation"],"falsifier":"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.","tokens_in":8171,"feed_emoji":"🧮","tokens_out":10923,"duration_ms":104932,"temperature":0.7,"pith_summary":"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.","feed_headline":"1000 terms now counted for pop-stacked permutations","feed_subtitle":"A polynomial-time algorithm replaces brute force, extending the known counts from 16 terms to 1000.","key_machinery":"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.","core_discovery":"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$.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Supplies the characterization of pop-stacked permutations as those whose adjacent ascending runs overlap, which grounds the overlapping-ballot bijection.","marker":"[1]"},{"why":"Introduces the pop-stack data structure and defines the operator whose image is the class under study.","marker":"[2]"},{"why":"Establishes rational generating functions for permutations sortable by finitely many pop-stack passes, the contrasting enumerative setting that motivates the unconstrained count.","marker":"[3]"},{"why":"Provides the differential-approximation method used to extract the singularity estimates and asymptotic prediction from the 1000 terms.","marker":"[5]"},{"why":"Supplies the companion series-analysis technique referenced for differential-approximation estimates.","marker":"[6]"}],"fun_headline_variants":["Polynomial-time count for pop-stacked permutations","Pop-stacked permutations counted to 1000 terms","Algorithm extends pop-stacked counts from 16 to 1000","New algorithm efficiently counts pop-stacked permutations","Counting pop-stacked permutations in polynomial time"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Polynomial-time count for pop-stacked permutations","Pop-stacked permutations counted to 1000 terms","Algorithm extends pop-stacked counts from 16 to 1000","New algorithm efficiently counts pop-stacked permutations","Counting pop-stacked permutations in polynomial time"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000471,"raw_usage":{"total_tokens":2319,"prompt_tokens":897,"completion_tokens":1422,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":513,"completion_tokens_details":{"reasoning_tokens":1348}},"tokens_in":513,"tokens_out":1422,"duration_ms":10709,"temperature":1.0,"reasoning_tokens":1348,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T11:26:31.694346+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[{"cited_title":"Pop-stack sorting and its image: Permutat ions with over- lapping runs","cited_arxiv_id":null,"evidence_quote":"Supplies the characterization of pop-stacked permutations as those whose adjacent ascending runs overlap, which grounds the overlapping-ballot bijection."},{"cited_title":"On pop-stacks in series","cited_arxiv_id":null,"evidence_quote":"Introduces the pop-stack data structure and defines the operator whose image is the class under study."},{"cited_title":"Enumerat ing permu- tations sortable by k passes through a pop-stack","cited_arxiv_id":null,"evidence_quote":"Establishes rational generating functions for permutations sortable by finitely many pop-stack passes, the contrasting enumerative setting that motivates the unconstrained count."},{"cited_title":"Asymptotic analysis of power-serie s expansions","cited_arxiv_id":null,"evidence_quote":"Provides the differential-approximation method used to extract the singularity estimates and asymptotic prediction from the 1000 terms."},{"cited_title":"Series analysis","cited_arxiv_id":null,"evidence_quote":"Supplies the companion series-analysis technique referenced for differential-approximation estimates."}],"review_version":1}