Rationality Below Growth Rate Four

Definitions and mathematical statement

Let $S_n$ be the set of permutations of $\{1,\ldots,n\}$, with $S_0$ containing the empty permutation. A permutation $\sigma\in S_k$ is a classical pattern of $\pi\in S_n$, written $\sigma\leq\pi$, if some subsequence of $\pi$ of length $k$ has the same relative order as $\sigma$. A permutation class is a set $\mathcal C\subseteq\bigcup_{n\geq0}S_n$ closed downward under this relation. For a set $B$ of permutations, define \[ \operatorname{Av}(B)=\{\pi: \beta\nleq\pi\text{ for every }\beta\in B\}. \] The class $\mathcal C$ is finitely based if $\mathcal C=\operatorname{Av}(B)$ for some finite $B$. Put \[ c_n=|\mathcal C\cap S_n|,\qquad F_{\mathcal C}(x)=\sum_{n\geq0}c_nx^n,\qquad \overline{\operatorname{gr}}(\mathcal C)=\limsup_{n\to\infty}c_n^{1/n}. \] The class is rational if $F_{\mathcal C}(x)=P(x)/Q(x)$ as a formal power series for some $P,Q\in{\mathbb{Q}}[x]$ with $Q(0)\neq0$.

Conjecture attributed in the supplied excerpt to Robert Brignall. Under the upper-growth interpretation of the source's phrase "growth rate," the precise assertion is \[ \forall B\subseteq\bigcup_{n\geq0}S_n\text{ finite},\qquad \overline{\operatorname{gr}}(\operatorname{Av}(B))<4 \ \Longrightarrow\ F_{\operatorname{Av}(B)}(x)\in{\mathbb{Q}}(x). \] The inequality is strict; growth rate exactly $4$ is excluded. The supplied record does not specify its growth-rate convention. If it instead requires the ordinary limit $\lim_{n\to\infty}c_n^{1/n}$, the hypothesis must explicitly require that this limit exists and is less than $4$. No equivalence between these formulations is asserted here.

Evidence reported in the supplied excerpt. Let $\mathcal S=\operatorname{Av}(\{2413,3142\})$ be the class of separable permutations. A class is strongly rational if every permutation subclass has a rational generating function. The excerpt reports that if $\mathcal C\subseteq\mathcal S$ and $\mathcal C$ contains none of the symmetry images of $\operatorname{Av}(\{132\})$, then $\mathcal C$ is strongly rational. Here symmetry images are obtained by applying reversal, complementation, and inversion to permutations, and containment means containment of entire classes. This is preserved as supplied supporting evidence, without independent verification.

The supplied label partially_solved is accompanied by a literature assessment about moment representations for principal classes. That assessment does not establish a partial result for the rationality conjecture stated here; its relevance remains unresolved.

Short English statement

The conjecture attributed to Robert Brignall asks whether every finitely based permutation class with growth rate strictly below $4$ has a rational ordinary generating function. The meaning of growth rate needs confirmation. The supplied moment-sequence literature assessment concerns a different apparent target and does not substantiate the supplied partial-solution label for this conjecture.

Sources

• Supplied local UnsolvedMath registry record, permanent ID $30005762$, title Rationality Below Growth Rate Four, exact source problem code catalogue entry. The original excerpt attributes the conjecture to Robert Brignall; the separate proposed_by field is null. The supplied proposed year is $2024$.
• Mini-Workshop: Permutation Patterns (2024), Oberwolfach Reports, pp. 273--308, DOI 10.4171/owr/2024/6. Supplied source URL and literature reference labelled "original OWR report": https://doi.org/10.4171/owr/2024/6.
• Supplied literature reference labelled "moment-sequence paper": https://www.combinatorics.org/ojs/index.php/eljc/article/view/v27i4p20.
• Supplied literature reference labelled "length-five pattern paper": https://arxiv.org/abs/2109.13485.
• Literature checked at: 2026-08-22. This is supplied dated curation, not an independently verified assessment. It reports partial solution and says that moment representations are proved for several principal classes and substantial pattern families while a conjecture for every principal class remains open. The supplied background explicitly requests independent verification of time-sensitive status and cited claims. The relationship of that assessment to the present rationality conjecture is unclear.
• The registry labels its statement corrected_verified and reports that the official report was checked directly and the clean statement retained the mathematical target while removing extraction artifacts. These are supplied provenance claims; no independent source visit or verification is claimed in this draft.