REVIEW 5 minor 9 references
$q$-Difference Equations for two classes of Pattern Avoiding Permutations
T0 review · 0 major / 5 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read The paper proves that the generating functions of two nested pattern-avoiding permutation classes are not D-finite, hence their counting sequences are not P-recursive, and it gives exact exponential growth rates for both.
desk verdict The rejection signal rests on a misread kth-root limit in Theorem 3.5; the paper's central claims hold up and it deserves serious refereeing. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the trivariate generating function $G^{(j)}(z;x,y)=\sum_{n\ge1}B_{n}^{(j)}(x,y)z^{n-1}$, where $B_{n}^{(j)}$ records two integers $(k,\ell)$ attached to the longest terminal suffix of each permutation whose standardization lies in the container class. The common kernel is $(1-y)(1-zx)+zy$; setting $y$ equal to its root and changing variables to $m$ and $w$ turns kernel cancellation into a $q$-difference equation relating $f(w)$ to $f(m^{2}w)$. The remainder of the proof is coefficientwise iteration of that equation: a second-order recurrence for the limits $R_{k}(m)$, $S_{k}(m)$ in the three-pattern case, and a convergent infinite product and sum in the two-pattern case, with the first exceptional event being the collision of two roots of $H_{m}$.
What would settle it
Check the growth assertion in Theorem 3.5 directly: for fixed $m$ with $0<|m|<1$, the factor $|m|^{k(k+3)}$ in the coefficient formula has $k$-th root $|m|^{k+3}$, which tends to $0$, so the claimed contradiction requires the remaining factors $R_k(m)$ and $S_k(m)$ to grow faster than $|m|^{-k(k+3)}$; verifying whether they do is the decisive calculation.
Extended reading notes
Core claim
On the paper's own terms, the central discovery is that the two generating functions $D^{(2)}(z)$ and $D^{(3)}(z)$ obey the same affine kernel equation with root $Y(x)$, and the substitution $z=m/(1+m)^{2}$, $w=(1+m-x)/(1+m-mx)$ sends $Y(x)$ to the dilation $w\mapsto m^{2}w$. For the three-pattern class, iteration of the resulting $q$-difference equation away from the attracting fixed point produces analytic functions $R(m)$ and $S(m)$ with $D^{(3)}(z)=1-z S(m)/R(m)$; $R(m)$ has infinitely many sign-changing zeros in $(0,1)$ that are not cancelled by $S(m)$, giving infinitely many finite singularities and non-D-finiteness. For the two-pattern class, iteration toward the attracting fixed point yields a convergent product and sum whose first obstruction is the collision of two roots of $H_{m}$ at $m^{(2)}=0.28197\ldots$; this produces the square-root singularity at $z=3-2\sqrt{2}$ and $d_{n}^{(2)}\sim C^{(2)}(3+2\sqrt{2})^{n}n^{-3/2}$ with $C^{(2)}=0.084983363\ldots$, while analytic continuation around that branch point creates infinitely many poles, again proving non-D-finiteness. The numerical values in the three-pattern case are $\rho^{(3)}=0.223793301\ldots$, $C^{(3)}=0.018967232\ldots$.
Load-bearing premise
The three-pattern result depends on the assertion that, if the denominator combination in the quotient formula did not vanish, the coefficients of the auxiliary series $\Phi_m$ would grow faster than any exponential, contradicting its convergence; that growth assertion is the load-bearing point.
Editorial extensions
If this is right
- No linear recurrence with polynomial coefficients can reproduce the counting sequences of either class.
- The three-pattern sequence grows purely exponentially, $d_{n}^{(3)}=C^{(3)}(\rho^{(3)})^{-n}+O((r^{(3)})^{-n})$, certifying the earlier experimental suggestion of pure exponential growth.
- The two-pattern sequence has the form $d_{n}^{(2)}\sim C^{(2)}(3+2\sqrt{2})^{n}n^{-3/2}$, with a unique dominant square-root singularity at $z=3-2\sqrt{2}$.
- The singularities of $D^{(3)}$ accumulate at $z=1/4$, while the analytic continuation of $D^{(2)}$ has infinitely many poles approaching $z=1/2$.
- The probabilistic corollaries hold: the number of sum-indecomposable components in the three-pattern class is asymptotically Gaussian, and in the two-pattern class the limiting component-count distribution is given explicitly by a parameter $\theta^{(2)}$.
Reading between the lines
- The same kernel-and-dilation framework should apply to other pairs of pattern-avoiding classes whose generating functions are suspected to be non-D-finite, with the two regimes here suggesting that the first obstruction of the $q$-difference iteration fixes the singularity type.
- The pole positions for $D^{(3)}$ computed from zeros of $R(m)$ match numerically the singularities already observed experimentally; a proof that each oscillation interval of $R$ contains exactly one zero would complete the description of the singularity set accumulating at $1/4$.
- The probabilistic limit laws give a testable extension: sampling uniformly random members of these classes should show the stated mean, variance, and limiting distribution for the number of sum-indecomposable components.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. This paper studies the nested permutation classes D^(3) = Av(4123,4231,4312) and D^(2) = Av(4123,4312). Using a succession-rule decomposition and the kernel method, the author derives trivariate generating-function equations whose common kernel, after z = m/(1+m)^2, becomes a q-difference equation with dilation w -> m^2 w. The three-pattern case is solved by coefficientwise iteration into a quotient formula D^(3)(z) = 1 - z S(m)/R(m); analytic and asymptotic analysis shows that R has infinitely many zeros in (0,1), none cancelled by S, so D^(3) is meromorphic in |z| < 1/4 with infinitely many poles, is not D-finite, and its coefficients satisfy d_n^(3) ~ C^(3)(rho^(3))^{-n}. The two-pattern case gives a product-sum representation whose first obstruction is a collision of roots of a quadratic at m^(2) = 0.281971680061..., leading to a square-root singularity at z = 3-2√2 and d_n^(2) ~ C^(2)(3+2√2)^n n^{-3/2}; continuation on a two-sheeted Riemann surface produces infinitely many poles and proves non-D-finiteness. The paper thus proves, rigorously, the experimental asymptotics and non-P-recursive nature conjectured by Albert, Homberger, Pantone, Shar, and Vatter.
Significance. The paper's main contribution is a rigorous resolution of two long-standing test cases at the boundary of exact and experimental enumeration. It gives compact, explicit permutation classes whose counting sequences are provably non-P-recursive, adding to the Garrabrant-Pak phenomenon with much smaller and more natural classes. A particular strength is that the constants in Theorems 1.1 and 1.2 are not fitted to data: they are defined as limits of explicit recurrences or roots of explicit algebraic equations, and the known initial terms are used only as consistency checks. The paper also contains a nontrivial interval-arithmetic certification of the sign of a derivative in Proposition 4.5, and the analytic-continuation argument for the two-pattern class is careful and inventive. I have checked the critical kth-root argument in Theorem 3.5: the prefactor contributes |m|^{-(k+3)} to the kth root, which diverges when 0 < |m| < 1, so the quotient formula g^(3) = -S/R is justified as written. I find no load-bearing error in the manuscript.
minor comments (5)
- [Abstract] The abstract and the first paragraph of the Introduction contain the typo 'generation functions'; this should be 'generating functions'.
- [Section 4] In the proof of Theorem 4.6 and in Corollary 4.11, sum closure of D^(2) is asserted without proof, although the analogous statement for D^(3) is proved in Lemma 3.15; the same short pattern-occurrence argument applies to the two sum-indecomposable basis elements and should be stated for completeness.
- [Remark 3.17] The remark contains the unproved statement that asymptotically there is only one zero of R per interval; since this assertion is not used in the main theorems, it should be explicitly labelled as an unproved observation or removed.
- [Theorems 1.1-1.2, (3.29), (4.20)] The decimal constants are asserted to many digits without explicit error bounds or certification of all displayed digits; the paper should state the certified precision or provide interval enclosures, especially since the numerical values appear in the theorems.
- [Throughout] Diacritics are missing in 'Möbius' and 'Schrödinger'; also, the title capitalizes 'q-Difference' while the body uses 'q-difference'.
Circularity Check
No significant circularity: the constants are defined as limits of explicit recurrences and roots of explicit equations; initial terms are consistency checks only.
full rationale
The derivation chain is self-contained. The counting sequences are not fitted: the constants m^(3), rho^(3), C^(3), C^(2) are defined by convergent recurrences, algebraic equations, and derivatives of explicit expressions, then evaluated rigorously. Initial terms are used only as consistency checks, not as inputs to the asymptotics. The only self-citation, reference [3], appears in a terminological aside about transfer matrices and plays no load-bearing role. The external comparisons with Pantone's slides and Albert et al.'s data are validations, not ingredients. The reader's stated concern about Theorem 3.5 inverts the kth-root limit: for 0<|m|<1, the kth root of |(1+m)(1-m)^2|^k / |m|^{k(k+3)} equals |1+m||1-m|^2 |m|^{-(k+3)}, which tends to infinity, so the analyticity contradiction is valid as written. No step reduces a prediction to a fitted parameter or imports a conclusion from a self-citation chain.
Assumptions & free parameters
assumptions (4)
- domain assumption The restricted-container machine theorem of Albert, Homberger, Pantone, Shar and Vatter identifies the C^(j)-machine output with D^(j).
- standard math Equivalence between D-finiteness of an ordinary generating function and P-recursiveness of its coefficient sequence (Stanley).
- standard math Vivanti-Pringsheim theorem and the singular value and transfer theorems of Flajolet-Sedgewick.
- standard math Marcus-Tardos theorem provides exponential upper bounds for permutation class growth.
Cite this review
Pith. "Pith review of $q$-Difference Equations for two classes of Pattern Avoiding Permutations." pith.science (2026). https://pith.science/paper/E2VX24HQ
@misc{pith2026260809078,
author = {Pith},
title = {Pith review of: $q$-Difference Equations for two classes of Pattern Avoiding Permutations},
year = {2026},
howpublished = {\url{https://pith.science/paper/E2VX24HQ}},
note = {Machine review of arXiv:2608.09078}
}
abstract
We study the nested permutation classes $Av(4123,4231,4312)\subset Av(4123,4312)$. We relate the corresponding generating functions $D^{(2)}(z)$, $D^{(3)}(z)$ to $q$-difference equations. Solving these equations allows to show that the generation functions are not D-finite, and that $[z^n]D^{(3)}(z)\sim 0.0189672325071988\ldots\, (4.46840899160393\ldots)^n$, $[z^n]D^{(2)}(z)\sim0.0849833632890843\ldots\, (3+2\sqrt2)^n n^{-3/2}$.
Reference graph
Works this paper leans on
-
[1]
M. H. Albert, C. Homberger, J. Pantone, N. Shar and V . Vatter,Generating permutations with restricted containers, J. Combin. Theory Ser. A157(2018), 205–232
work page 2018
-
[2]
M. Bousquet-M ´elou, M. Bouvel and J. Pantone,Solution to a functional equation forAv(1243,1324,1432), Mini-Workshop: Permutation Patterns, Oberwolfach Rep.6(2024), 299–302
work page 2024
- [3]
-
[4]
P . Flajolet and R. Sedgewick,Analytic Combinatorics, Cambridge University Press, 2009
work page 2009
-
[5]
S. Garrabrant and I. Pak,Permutation patterns are hard to count, inProceedings of the Twenty-Seventh Annual ACM–SIAM Symposium on Discrete Algorithms, SIAM, 2016, 923–936
work page 2016
-
[6]
A. Marcus and G. Tardos,Excluded permutation matrices and the Stanley–Wilf conjecture, J. Combin. The- ory Ser. A107(2004), 153–160
work page 2004
-
[7]
Algorithmic and Enumerative Combi- natorics,
J. Pantone,Sorting with C-machines, slides for the programme “Algorithmic and Enumerative Combi- natorics,” Erwin Schr ¨odinger Institute, Vienna, 20 October 2017,https://www.mat.univie.ac. at/˜kratt/esi4/pantone.pdf
work page 2017
-
[8]
R. P . Stanley,Differentiably finite power series, European J. Combin.1(1980), 175–188
work page 1980
Show all 9 references
-
[9]
Vatter,An assortment of problems in permutation patterns: unimodality, equivalence, derangements, and sorting, arXiv:2602.16355, 2026
V . Vatter,An assortment of problems in permutation patterns: unimodality, equivalence, derangements, and sorting, arXiv:2602.16355, 2026. PAULZINN-JUSTIN, SCHOOL OFMATHEMATICS ANDSTATISTICS, THEUNIVERSITY OFMELBOURNE, VICTORIA3010, AUSTRALIA Email address:pzinn@unimelb.edu.au
2026
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.