Non-D-finiteness conjecture for the generating function of Av(A5,1)\mathcal{A}v(A_{5,1})

Let A5,1A_{5,1} be the permutation class under discussion, and let Av(A5,1)\mathcal{A}v(A_{5,1}) denote the class of permutations avoiding the patterns in A5,1A_{5,1}. Its generating function is the ordinary generating function counting permutations in Av(A5,1)\mathcal{A}v(A_{5,1}) by length. A formal power series is D-finite if it satisfies a non-trivial linear differential equation

pk(x)f(k)(x)+pk1(x)f(k1)(x)++p0(x)f(x)+q(x)=0,p_k(x)f^{(k)}(x)+p_{k-1}(x)f^{(k-1)}(x)+\cdots+p_0(x)f(x)+q(x)=0,

where the coefficients pi(x)p_i(x) and q(x)q(x) are polynomials.

Non-D-finiteness conjecture. The generating function for Av(A5,1)\mathcal{A}v(A_{5,1}) is not D-finite.

The conjecture is motivated by computational evidence: 642 initial terms did not fit the generating function to the tested rational, algebraic, D-finite, or differentially algebraic forms. The computations are not dispositive, and the conjecture remains open.

Sources & referencesView supporting material

Primary source

Miklós Bóna and Jay Pantone, “Permutations avoiding sets of patterns with long monotone subsequences”, arXiv:2103.06918 (2022).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.