{"id":"80216ae7-3a25-45e8-876b-18fe3af95d3c","arxiv_id":"1908.03953","paper_version":2,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":8.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"The authors obtain rational generating functions for super-strict patterns, general asymptotic formulas for all strict patterns, and non-algebraicity for patterns whose largest two parts are consecutive.","lead":"This paper counts integer partitions that avoid a given partition-shaped pattern, giving generating functions and growth rates for every pattern. It proves rational generating functions for a wide class of patterns and shows another class has non-algebraic generating functions.","discovery_kind":"new_method","skeptic_critique":null,"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies pattern-avoiding integer partitions, where a partition α contains a pattern µ if the Ferrers board of µ can be obtained from α by deleting rows and columns. Using the Bloom–Saracino theorem that every partition is Wilf-equivalent to a unique strict partition, the authors reduce to strict patterns. They introduce two operators E and N on bivariate generating functions and prove (Theorem 3.18) that the avoidance generating function is rational whenever µ is super-strict, with a constructive algorithm for computing it. For asymptotics, they prove Theorem 4.8 for staircase patterns and Theorems 4.14 and 4.16 for general strict non-staircase patterns, giving explicit polynomial–logarithmic asymptotics whose constants are products of divisor sums and zeta values. Corollary 4.17 then uses Fatou's theorem to show that the generating function is not algebraic when µ1 − µ2 = 1 and µ2 > 0. The paper closes with a table of small cases, a conjecture on non-algebraicity for all non-super-strict µ, and a remark connecting the generating function for (5,2) to metacyclic p-groups.","tokens_in":26199,"tokens_out":49184,"duration_ms":428129,"significance":"If the results hold, the paper gives a clean structural dichotomy: rational generating functions for super-strict patterns and non-algebraicity for patterns whose first two parts differ by 1, with fully explicit parameter-free asymptotic formulas in between. The operator calculus is original and constructive, and the asymptotic theorems are sharp enough to imply non-algebraicity. The proofs are detailed and carefully articulated, with dependencies on published results (Ingham, Estermann, Bloom–Saracino) clearly cited; there are no fitted parameters and no circularity in the derivations. I verified the central chain of reasoning: the rationality theorem follows from the nice/very nice lemmas, and the asymptotic theorems follow by induction with explicit error terms. The table of small cases contains several entries that contradict the theorems, but these appear to be local presentation errors rather than flaws in the central arguments.","major_comments":[],"minor_comments":[{"comment":"The rows for (4,3,1), (4,3,2), and (4,3,2,1) contradict the theorems in the text. Applying Theorem 4.16 to (4,3,1) with k=3, ℓ=1, a0=1 gives |Av_n| = n^2 log n / 2 + O(n^2), not n^3 log n / 2. Applying it to (4,3,2) with k=3, ℓ=2, a0=0 gives n^2 log^2 n / 4 + O(n^2 log n), not n^3 log^2 n / 4. Applying Theorem 4.8 to the staircase (4,3,2,1) with k=3 gives σ2(n) log^3 n / (12ζ(3)), not σ2(n) log^3 n / (6ζ(3)). Please correct the table, or reconcile the theorems if the table was computed independently.","section":"Table 1"},{"comment":"In the sentence 'there can be at most k partitions α ∈ ⋃_{m=1}^n D_{n−m}(µ) with Ψ_{n−|α|}(α) = β', the set should be D_{n−m}(ˆµ), since α is an element of D(ˆµ). The same typo appears in the proof of Lemma 4.15, Case 2, where 'α ∈ D(µ)' should read 'α ∈ D(ˆµ)'.","section":"§4.2.1, Lemma 4.13 proof"},{"comment":"The lemma is stated for an arbitrary partition µ, but its proof invokes Lemma 3.21(iii), which requires µ to be strict. Please restrict the statement to strict µ, or at least note that this is the only case used in the paper.","section":"§3, Lemma 3.10"},{"comment":"The displayed rectangular decomposition of β omits the thin rectangle y_{k−ℓ}, even though the surrounding text immediately uses r ∈ {y_{a0+1}, ..., y_{k−ℓ}}. Please include the missing term for clarity.","section":"§4.2.2, Lemma 4.15, Case 3"},{"comment":"In the comparison after equation (33), the text writes the dominant term as ≍_m n^{k−1} log n, but the cited theorems give log^ℓ n with ℓ > 0; for ℓ > 1 this should be log^ℓ n. This does not affect the argument, but the notation should be corrected.","section":"§4.3, Corollary 4.17"},{"comment":"There are minor typos and notation issues: 'Riordon' should be 'Riordan' in Section 2, and in Theorem 4.16 the expression O(n^{k−1} log^{ℓ−1} n) for ℓ = 0 should be understood as O(n^{k−1}/log n). Please consider a brief note on this convention.","section":"Throughout"}],"recommendation":"minor_revision","confidential_remarks":"The main theorems appear sound and the proofs are carefully written; my main reservation is the table of small cases, which contains entries contradicting Theorems 4.8 and 4.16. These are local and easily fixable, but they should be corrected before publication because readers often use such tables to verify the general results. The self-citations [2,3] are prior published work used as tools, so there is no circularity concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Worth reading: this is the complete solution of the counting problem for pattern-avoiding integer partitions, and the operator calculus is genuinely new. Prior work only covered the two extremes—partitions into at most k parts and staircase avoidance—and this paper fills the whole spectrum with uniform asymptotics. The three headline results are all proven: rationality of the generating function for super-strict patterns, the full asymptotic formula for every strict pattern, and the non-algebraicity corollary for patterns whose first two parts differ by 1. The constructive algorithm and the table of small cases are practical payoffs, not afterthoughts.\n\nThe E/N operator method is the real novelty, and the proof of Theorem 3.18 is careful: the nice/very nice lemmas are simple but effective, and the induction in Theorem 3.7 is clean. On the asymptotic side, the paper does not hand-wave. The error terms are explicit, the k=2 log log n wrinkle is handled honestly, and the use of Ingham, Estermann, and Halberstam is transparent and appropriate. I also appreciate that the reduction to strict partitions is outsourced explicitly to Bloom–Saracino Theorem 1.1; that is a published tool, not a circular dependency.\n\nSoft spots are minor. The non-algebraicity proof via Fatou's theorem is sound, though the multiple-roots-of-unity case deserves the two sentences it gets; they are sufficient. There are small notational hiccups in Lemma 4.15, especially the index shift between µ(i) and µ(i+1) in Case 2, but the counting argument remains legible and the conclusion follows. The metacyclic p-group coincidence is a curiosity, and the paper is honest that no bijective explanation is known. None of these rise to the level of a substantive flaw.\n\nI agree with the reader's high confidence. This paper will likely be the standard reference for pattern-avoiding partitions. I would send it to a serious referee for a good combinatorics journal; I expect minor revision at most.","headline":"A complete, well-proven solution of the pattern-avoiding partition counting problem, with genuinely new operator methods and only minor presentational blemishes.","tokens_in":26642,"tokens_out":2115,"would_cite":true,"duration_ms":24469,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A17","05A15","05A16"],"pacs":[],"model":"deepseek-v4-flash","headline":"Avoiding a fixed pattern makes partition counts grow by a power of n times a power of log n.","keywords":["integer partitions","pattern avoidance","Ferrers boards","generating functions","asymptotic enumeration","rook equivalence","Wilf equivalence","metacyclic p-groups"],"falsifier":"For $\\mu = (4,3)$, the theorem predicts $|\\mathrm{Av}_n(\\mu)| = \\frac{n^2 \\log n}{4} + O(n^2)$; computing $|\\mathrm{Av}_n(4,3)|$ exactly for $n$ up to, say, $10^5$ and checking whether $4 |\\mathrm{Av}_n(4,3)| / (n^2 \\log n)$ tends to $1$ would settle the asymptotic formula, and a persistent deviation would refute it.","tokens_in":1919,"feed_emoji":"🧩","tokens_out":2860,"duration_ms":101830,"temperature":0.7,"pith_summary":"This paper counts how many partitions of an integer $n$ avoid a fixed partition pattern $\\mu$, where containment means the Ferrers board of $\\mu$ can be obtained by deleting rows and columns. It proves that for every super-strict pattern $\\mu$, the generating function for the avoidance counts is rational, and gives an explicit recursive algorithm for computing it. It then derives asymptotic formulas showing that staircase patterns grow like divisor sums times powers of $\\log n$, while every other strict pattern grows as $n^{k-1}(\\log n)^{\\ell}$ with an explicit constant. These asymptotics imply that whenever the two largest parts of $\\mu$ are consecutive integers, the generating function is not algebraic. The results rest on the Wilf-equivalence reduction to strict partitions, which lets every pattern be replaced by a strict one without changing counts.","feed_headline":"Partition-avoidance counts follow one growth law","feed_subtitle":"New proof shows rational generating functions for a large class and rules out algebraic ones when consecutive parts appear.","key_machinery":"The main combinatorial device is a pair of operators $E$ and $N$ attached to the southeast border of a super-strict partition $\\mu$. Reading the border from bottom-left to top-right, each east step becomes $E$ and each north-east step becomes $N$, yielding a word $\\Theta_\\mu$; applying these operators to the bivariate generating function $\\frac{zt}{1-zt}$ and setting $t=1$ produces $F_\\mu(z,1)$, the generating function for avoiding $\\mu$. The operator $E$ adds a column to the current rightmost column, while $N$ appends a new strictly shorter column together with an arbitrary number of width-equal columns, and the proof shows that the composition inherits rationality because super-strictness forbids consecutive $N$'s. For asymptotics, the paper uses the rectangular decomposition of a partition into $x_i y_i$ blocks with strictly decreasing heights; patterns with exactly $\\mu_1-1$ distinct magnitudes form the dominant set $D(\\mu)$, and a map $\\Psi_m$ builds partitions avoiding $\\mu$ from partitions avoiding a smaller pattern $\\hat{\\mu}$, giving the recursive constant in Theorem 4.16.","core_discovery":"For a strict partition $\\mu$, the paper establishes a dichotomy in the growth of $|\\mathrm{Av}_n(\\mu)|$. If $\\mu$ is a staircase $(k+1, k, \\ldots, 1)$, the count is asymptotic to a divisor-sum expression: for $k \\geq 3$, $|\\mathrm{Av}_n(\\mu)| \\sim \\sigma_{k-1}(n)(\\log n)^k / (k!(k-1)!\\zeta(k))$, with separate formulas for $k = 1$ and $k = 2$. If $\\mu$ is strict but not a staircase, written as $(k+1, k, k-1, \\ldots, k-\\ell+1, a_0, a_1, \\ldots)$ with $k-\\ell > a_0$, then $|\\mathrm{Av}_n(\\mu)| = \\frac{n^{k-1}(\\log n)^{\\ell}}{\\ell!(k-1)! \\prod_{j=0}^{k-\\ell-1}(k-\\ell-a_j-j)}\\left(1+O\\left(\\frac{1}{\\log n}\\right)\\right)$. The paper also proves that $F_\\mu(z,1)$ is rational whenever $\\mu$ is super-strict, and that the generating function is not algebraic whenever $\\mu_1 - \\mu_2 = 1$ with $\\mu_2 > 0$.","pith_inferences":["The constant in Theorem 4.16 is built from the Foata-Schützenberger numbers $i + \\mu_i$ appearing in rook-equivalence classification; this hints that the full asymptotic could be expressed as a Wilf-invariant quantity determined solely by the strict representative of $\\mu$.","If Conjecture 1.2 is true, the boundary between algebraic and non-algebraic avoidance generating functions is exactly the super-strict condition; a testable next step is to search the algorithm's outputs for any non-super-strict pattern whose generating function is algebraic.","The coincidence that $F_{(5,2)}(z,1)$ equals the generating function for metacyclic $p$-groups suggests there may be a bijection between partitions avoiding $(5,2)$ and such groups, though the paper does not supply one.","The constructive $E/N$ algorithm could be run for arbitrary super-strict patterns to generate many new integer sequences, making it possible to test the conjecture computationally and to detect further coincidences with existing sequences."],"forward_implications":["For every super-strict partition $\\mu$, the sequence $|\\mathrm{Av}_n(\\mu)|$ has a rational generating function and therefore satisfies a linear recurrence with constant coefficients.","For every fixed $K$, partitions in which any two part sizes differ by at most $K$ have a rational generating function.","For a strict non-staircase $\\mu$, the growth order of $|\\mathrm{Av}_n(\\mu)|$ is determined by two parameters: $n^{k-1}$ times $(\\log n)^{\\ell}$, where $\\ell$ counts how many consecutive part sizes directly below the largest are present in $\\mu$.","If the two largest parts of $\\mu$ are consecutive positive integers, the avoidance generating function cannot be algebraic, so no finite polynomial or rational closed form exists for that count.","Staircase patterns form a genuine exceptional family, with counts controlled by averaged divisor functions rather than by the power-of-$n$ formula."],"supporting_citations":[{"why":"Bloom and Saracino prove that rook-equivalent partitions are Wilf-equivalent, giving the first half of the reduction to strict partitions.","marker":"[2]"},{"why":"Bloom and Saracino prove the converse, so Wilf equivalence coincides with rook equivalence and every class has a unique strict representative.","marker":"[3]"},{"why":"Foata and Schützenberger classify rook equivalence by the multiset $\\{i + \\mu_i\\}$, supplying the product factors that appear in the asymptotic constant.","marker":"[7]"},{"why":"Ingham's asymptotic for convolutions of divisor functions underlies the staircase count used in Theorem 4.8.","marker":"[12]"},{"why":"Estermann's refined asymptotic for sums of two products provides the $k=2$ staircase formula.","marker":"[4]"},{"why":"Estermann's result for sums of three or more products supplies the $k \\geq 3$ staircase formula.","marker":"[5]"},{"why":"Fatou's theorem on rational generating functions with integer coefficients is used to rule out algebraicity in Corollary 4.17.","marker":"[6]"},{"why":"Liedahl's enumeration of metacyclic $p$-groups provides the generating function that coincides with $F_{(5,2)}(z,1)$.","marker":"[15]"},{"why":"Andrews' asymptotic treatment of stacked lattice boxes is used to count partitions with a fixed number of distinct magnitudes.","marker":"[1]"}],"fun_headline_variants":["Pattern-avoiding partitions: two asymptotic regimes found","Rational generating functions for some pattern-avoiding partitions","Staircase patterns set growth rates for avoidant partitions","Non-algebraic generating functions for patterns with consecutive parts","Asymptotic dichotomy for partitions avoiding a fixed pattern"],"cache_read_input_tokens":29184,"weakest_assumption_plain":"Every statement for arbitrary partitions rests on the published theorem that each partition is Wilf-equivalent to a unique strict partition, so avoiding any pattern $\\tau$ has exactly the same counts as avoiding its strict representative.","fun_headline_variants_meta":{"raw":{"variants":["Pattern-avoiding partitions: two asymptotic regimes found","Rational generating functions for some pattern-avoiding partitions","Staircase patterns set growth rates for avoidant partitions","Non-algebraic generating functions for patterns with consecutive parts","Asymptotic dichotomy for partitions avoiding a fixed pattern"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00078,"raw_usage":{"total_tokens":3477,"prompt_tokens":1004,"completion_tokens":2473,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":620,"completion_tokens_details":{"reasoning_tokens":2395}},"tokens_in":620,"tokens_out":2473,"duration_ms":22372,"temperature":1.0,"reasoning_tokens":2395,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:57:59.786457+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"For $\\mu = (4,3)$, the theorem predicts $|\\mathrm{Av}_n(\\mu)| = \\frac{n^2 \\log n}{4} + O(n^2)$; computing $|\\mathrm{Av}_n(4,3)|$ exactly for $n$ up to, say, $10^5$ and checking whether $4 |\\mathrm{Av}_n(4,3)| / (n^2 \\log n)$ tends to $1$ would settle the asymptotic formula, and a persistent deviation would refute it.","supporting_citations":[{"cited_title":"Bloom and D","cited_arxiv_id":null,"evidence_quote":"Bloom and Saracino prove that rook-equivalent partitions are Wilf-equivalent, giving the first half of the reduction to strict partitions."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Bloom and Saracino prove the converse, so Wilf equivalence coincides with rook equivalence and every class has a unique strict representative."},{"cited_title":"Foata and M","cited_arxiv_id":null,"evidence_quote":"Foata and Schützenberger classify rook equivalence by the multiset $\\{i + \\mu_i\\}$, supplying the product factors that appear in the asymptotic constant."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Ingham's asymptotic for convolutions of divisor functions underlies the staircase count used in Theorem 4.8."},{"cited_title":"Estermann, On the representations of a number as the sum of two products , J","cited_arxiv_id":null,"evidence_quote":"Estermann's refined asymptotic for sums of two products provides the $k=2$ staircase formula."},{"cited_title":"London Math","cited_arxiv_id":null,"evidence_quote":"Estermann's result for sums of three or more products supplies the $k \\geq 3$ staircase formula."},{"cited_title":"Fatou, S´ eries trigonom´ etriques et s´ eries de Taylor, Acta Math","cited_arxiv_id":null,"evidence_quote":"Fatou's theorem on rational generating functions with integer coefficients is used to rule out algebraicity in Corollary 4.17."},{"cited_title":"Liedahl, Enumeration of metacyclic p-groups, J","cited_arxiv_id":null,"evidence_quote":"Liedahl's enumeration of metacyclic $p$-groups provides the generating function that coincides with $F_{(5,2)}(z,1)$."},{"cited_title":"Andrews, Stacked lattice boxes , Ann","cited_arxiv_id":null,"evidence_quote":"Andrews' asymptotic treatment of stacked lattice boxes is used to count partitions with a fixed number of distinct magnitudes."}],"review_version":1}