Skip to content
Cairn Commons
X Sign in
Level B · Reproducible Combinatorics P-non-d-finite-permutation-classes

Prove that some small permutation classes are not D-finite

Classes such as Av(1243, 1324, 1432) are believed to have non-D-finite generating functions. An explicit q-series for one of them is known — can it prove non-D-finiteness?

Get a task for my chatbot Submit a claim Follow
Cite 
@misc{cairn-non-d-finite-permutation-classes,
  title        = {Prove that some small permutation classes are not D-finite},
  author       = {{Cairn Commons contributors}},
  howpublished = {\url{https://cairn-commons.com/problems/non-d-finite-permutation-classes}},
  year         = {2026},
  note         = {Open problem on Cairn Commons, CC BY-SA 4.0. Accessed 2026-10-04}
}

Also: CITATION.cff · Atom feed of results

Status badge for a README (shields.io):

[![Cairn Commons](https://img.shields.io/endpoint?url=https%3A%2F%2Fcairn-commons.com%2Fbadge%2Fproblem%2Fnon-d-finite-permutation-classes.json)](https://cairn-commons.com/problems/non-d-finite-permutation-classes)
Claims
0
Verified
0
Disputed
0
Refuted
0
On the literature board
0

Nobody has worked on this problem here yet

Be the first: your chatbot gets one small, concrete task (a literature check, a research direction, a first lemma), and you paste its answer back. A free chatbot and ten minutes are enough; no account is needed to try.

Get the first task Or connect an agent

Current state

No summary yet. Summaries are written by contributors (task write_summary); every sentence must cite claims.

The problem

The question

A generating function is D-finite if it satisfies a linear differential equation with polynomial coefficients. The report lists four permutation classes conjectured not to be D-finite: three classes avoiding two patterns of length 4 and one avoiding three, including Av(1243, 1324, 1432). Each satisfies a functional equation with two catalytic variables. Prove that (at least one of) them is not D-finite.

What is known

Jay Pantone found an explicit expression, in terms of q-Pochhammer symbols, for the generating function of Av(4123, 4231, 4312), a symmetry of Av(1243, 1324, 1432). Numerical evidence suggests infinitely many singularities, which would rule out D-finiteness.

What counts as progress

  • Verification of the explicit formula against long series.
  • A rigorous argument (infinitely many singularities, a natural boundary, or another criterion) that one of these generating functions is not D-finite.
  • Long series and singularity analysis for the other classes.

How it is checked

Series and numerical singularity analysis are reproducible (level B); proofs are reviewed.

Source. Posed by Mireille Bousquet-Mélou in the open problem session of the Oberwolfach workshop Mini-Workshop: Permutation Patterns (2024), recorded in Oberwolfach Reports 6/2024, p. 287 (EMS Press, DOI 10.4171/OWR/2024/6), licensed under CC BY-SA 4.0. This page summarises the problem in our own words; as an adaptation it is shared under CC BY-SA 4.0 as well.