pith. sign in

arxiv: 2211.12397 · v4 · submitted 2022-11-22 · 🧮 math.CO

Uncountably many enumerations of well-quasi-ordered permutation classes

Robert Brignall , Vincent Vatter This is my paper

Pith reviewed 2026-05-24 10:24 UTC · model grok-4.3

classification 🧮 math.CO
keywords permutation classeswell-quasi-orderenumeration sequencesgenerating functionsbinary languagesD-finite functionsfactor-closed languages
0
0 comments X

The pith

There exist uncountably many well-quasi-ordered permutation classes with pairwise distinct enumeration sequences.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper builds an uncountable family of well-quasi-ordered permutation classes in which each class is counted by a different sequence. The construction translates an existing uncountable collection of factor-closed well-quasi-ordered binary languages into permutation classes while keeping both the ordering property and the distinct counts intact. If the translation succeeds, then the generating functions of these classes cannot all be algebraic, and in fact many cannot be D-finite or D-algebraic. A reader should care because this removes any hope that well-quasi-order alone forces a simple algebraic or analytic form on the counting sequences of permutation classes.

Core claim

We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.

What carries the argument

The explicit mapping from Pouzet's factor-closed well-quasi-ordered binary languages to permutation classes that preserves both well-quasi-order and distinct enumeration sequences.

If this is right

  • The generating functions of many well-quasi-ordered permutation classes are not algebraic.
  • The generating functions of many well-quasi-ordered permutation classes are not D-finite.
  • The generating functions of many well-quasi-ordered permutation classes are not D-algebraic.
  • There are uncountably many distinct enumeration sequences arising from well-quasi-ordered permutation classes.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Enumeration problems for well-quasi-ordered permutation classes may require analytic machinery beyond algebraic or D-finite functions.
  • The construction suggests that similar translations could produce further examples with prescribed enumeration properties.
  • It remains open whether every enumeration sequence arising this way can be realized by a finitely based permutation class.

Load-bearing premise

The mapping from the binary languages to permutation classes preserves both the well-quasi-order property and the distinctness of the resulting enumeration sequences.

What would settle it

An explicit pair of distinct Pouzet languages whose images under the mapping are two well-quasi-ordered permutation classes with identical enumeration sequences would falsify the claim.

Figures

Figures reproduced from arXiv: 2211.12397 by Robert Brignall, Vincent Vatter.

Figure 1
Figure 1. Figure 1: The rightward-yearning pin sequence associated to the word drduruurudrdurudrddrduru. It remains to explain how to start a pin sequence. In the present work, we start every pin sequence with a point called an origin and labelled by p0. Importantly, we do not consider the origin p0 to be part of the resulting rightward-yearning pin sequence. For the first real pin, p1, if it has encoding u or ru, then p1 app… view at source ↗
Figure 2
Figure 2. Figure 2: Deleting the circled interior pin from ψ ˝ drdurudrdurudrd results in ψ ˝ drduru ‘ ψ ‚ rdurudrd . We call the operation in this last case inflating the origin, and this case is the reason we introduced the permutations ψ ‚ w in Section 3 in the first place. The process of removing pins from the permu￾tations ψ ‚ w is also needed, but is entirely analogous to the above, and will be handled once we have intr… view at source ↗
read the original abstract

We construct an uncountable family of well-quasi-ordered permutation classes, each with a distinct enumeration sequence. This disproves a conjecture that all well-quasi-ordered permutation classes have algebraic generating functions, and in fact shows that many such classes lack D-finite or D-algebraic generating functions. Our construction is based on an uncountably large collection of factor-closed, well-quasi-ordered binary languages due to Pouzet.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 1 minor

Summary. The manuscript constructs an uncountable family of well-quasi-ordered permutation classes with pairwise distinct enumeration sequences. The construction maps Pouzet's uncountable collection of factor-closed WQO binary languages to permutation classes while preserving WQO and distinctness of the resulting sequences. This disproves the conjecture that every WQO permutation class has an algebraic generating function and shows that many such classes have generating functions outside the D-finite and D-algebraic classes.

Significance. If the explicit mapping succeeds, the result is significant for the theory of permutation classes and enumerative combinatorics. It supplies a concrete, uncountable family of WQO classes whose enumeration sequences are all distinct, implying that the generating functions of all but countably many lie outside the countable families of algebraic, D-finite, and D-algebraic series. The paper correctly credits Pouzet's prior result and focuses its contribution on the preservation properties of the mapping.

minor comments (1)
  1. [Abstract] The abstract states the mapping but does not name the section containing the explicit definition of the correspondence between binary languages and permutation classes; adding a forward reference would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive report and the recommendation to accept.

Circularity Check

0 steps flagged

No circularity: direct external construction from Pouzet

full rationale

The paper's central claim is an explicit construction that maps Pouzet's uncountable family of factor-closed WQO binary languages to WQO permutation classes while preserving distinct enumeration sequences. The abstract states the construction is 'based on' Pouzet's collection, with no equations, fitted parameters, or self-citations that reduce the claimed enumerations or WQO preservation to the paper's own inputs by definition. No load-bearing step matches any of the enumerated circularity patterns; the countability argument follows directly once the external mapping succeeds. This is a standard non-circular use of prior independent work.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claim rests on the correctness of Pouzet's uncountable collection of factor-closed well-quasi-ordered binary languages and on the (unstated in the abstract) details of how those languages are translated into permutation classes while preserving the required properties.

axioms (1)
  • domain assumption Pouzet's construction yields an uncountable family of factor-closed well-quasi-ordered binary languages.
    Invoked as the starting point for the mapping to permutation classes.

pith-pipeline@v0.9.0 · 5586 in / 1308 out tokens · 19375 ms · 2026-05-24T10:24:08.459752+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

  1. Pin classes II: Small pin classes

    math.CO 2024-12 unverdicted novelty 7.0

    Pin classes exhibit a phase transition at μ ≈ 3.28277 with countably many below the threshold and uncountably many at it; all growth rates below μ are classified via periodic pin permutations.

Reference graph

Works this paper leans on

40 extracted references · 40 canonical work pages · cited by 1 Pith paper · 3 internal anchors

  1. [1]

    Large infinite antichains of permutations

    Albert, M., Brignall, R., and V atter, V. Large infinite antichains of permutations. Pure Math. Appl. (PU.M.A.) 24 , 2 (2013), 47–57

    work page 2013

  2. [2]

    Generating permutations with restricted containers

    Albert, M., Homberger, C., Pantone, J., Shar, N., and V atter , V. Generating permutations with restricted containers. J. Combin. Theory Ser. A 157 (2018), 205–232. 6Although it seems likely given his some of his writing [16, Pr oblem 28] that Knuth was aware of this application of Fekete’s lemma in 1972. Uncountably Many Enumera tions of WQO Permuta tion...

    work page 2018

  3. [3]

    Growing at a perfect speed

    Albert, M., and Linton, S. Growing at a perfect speed. Combin. Probab. Comput. 18 , 3 (2009), 301–308

    work page 2009

  4. [4]

    Inflations of geometric grid classes of permuta- tions

    Albert, M., Ruškuc, N., and V atter, V. Inflations of geometric grid classes of permuta- tions. Israel J. Math. 205 , 1 (2015), 73–108

    work page 2015

  5. [5]

    H., and Atkinson, M

    Albert, M. H., and Atkinson, M. D. Simple permutations and pattern restricted permu- tations. Discrete Math. 300 , 1-3 (2005), 1–15

    work page 2005

  6. [6]

    The ubiquitous Prouhet–Thue–Morse sequence

    Allouche, J.-P., and Shallit, J. The ubiquitous Prouhet–Thue–Morse sequence. In Se- quences and their Applications , C. Ding, T. Helleseth, and H. Niederreiter, Eds. Springer, London, England, 1999, pp. 1–16

    work page 1999

  7. [7]

    On the Stanley–Wilf conjecture for the number of permutatio ns avoiding a given pattern

    Arratia, R. On the Stanley–Wilf conjecture for the number of permutatio ns avoiding a given pattern. Electron. J. Combin. 6 (1999), Note 1, 4 pp

    work page 1999

  8. [8]

    Hereditary properties of ordered graphs

    Balogh, J., Bollobás, B., and Morris, R. Hereditary properties of ordered graphs. In Topics in Discrete Mathematics , M. Klazar, J. Kratochvíl, M. Loebl, J. Matoušek, R. Thomas, and P. Valtr, Eds., vol. 26 of Algorithms and Combinatorics . Springer, Berlin, Germany, 2006, pp. 179–213

    work page 2006

  9. [9]

    Enumeration of pin-permutations

    Bassino, F., Bouvel, M., and Rossin, D. Enumeration of pin-permutations. Electron. J. Combin. 18 , 1 (2011), Paper 57, 39 pp

    work page 2011

  10. [10]

    Intervals of permutation class growth rates

    Bev an, D. Intervals of permutation class growth rates. Combinatorica 38, 2 (2018), 279–303

    work page 2018

  11. [11]

    Permutations avoiding sets of patterns with long monotone subsequences

    Bóna, M., and Pantone, J. Permutations avoiding sets of patterns with long monotone subsequences. J. Symbolic Comput. 116 (2023), 130–138

    work page 2023

  12. [12]

    Grid classes and partial well order

    Brignall, R. Grid classes and partial well order. J. Combin. Theory Ser. A 119 , 1 (2012), 99–116

    work page 2012

  13. [13]

    Decomposing simple permutations, with enumerative consequences

    Brignall, R., Huczynska, S., and V atter, V. Decomposing simple permutations, with enumerative consequences. Combinatorica 28, 4 (2008), 385–400

    work page 2008

  14. [14]

    Simple permutations: decidability and un- avoidable substructures

    Brignall, R., Ruškuc, N., and V atter, V. Simple permutations: decidability and un- avoidable substructures. Theoret. Comput. Sci. 391 , 1-2 (2008), 150–163

    work page 2008

  15. [15]

    Labelled well-quasi-order for permutation classes

    Brignall, R., and V atter, V. Labelled well-quasi-order for permutation classes. Comb. Theory 2, 3 (2022), Article 14, 54 pp

    work page 2022

  16. [16]

    Selected combinatorial research prob- lems

    Chv átal, V., Klarner, D., and Knuth, D. Selected combinatorial research prob- lems. Tech. Rep. STAN-CS-72-292, Stanford University, 197 2. A vailable online at http://i.stanford.edu/TR/CS-TR-72-292.html

    work page

  17. [17]

    Classical length- 5 pattern- avoiding permutations

    Clisby, N., Conw ay, A., Guttmann, A., and Inoue, Y. Classical length- 5 pattern- avoiding permutations. Electron. J. Combin. 29 , 3 (2022), Paper 3.14, 63 pp

    work page 2022

  18. [18]

    On the growth rate of 1324-avoiding permutations

    Conw ay, A., and Guttmann, A. On the growth rate of 1324-avoiding permutations. Adv. in Appl. Math. 64 (2015), 50–69

    work page 2015

  19. [19]

    1324-avoiding permutations revisited

    Conw ay, A., Guttmann, A., and Zinn-Justin, P. 1324-avoiding permutations revisited. Adv. in Appl. Math. 96 (2018), 312–333

    work page 2018

  20. [20]

    Linearly recurrent subshift s have a finite number of non-periodic subshift factors

    Durand, F. Corrigendum and addendum to: “Linearly recurrent subshift s have a finite number of non-periodic subshift factors”. Ergodic Theory Dynam. Systems 23 , 2 (2003), 663–669

    work page 2003

  21. [21]

    Do the properties of an S-adic representation determine factor complexity? J

    Durand, F., Leroy, J., and Richomme, G. Do the properties of an S-adic representation determine factor complexity? J. Integer Seq. 16 , 2 (2013), Article 13.2.6, 30 pp

    work page 2013

  22. [22]

    Elder, M., and V atter, V. Problems and conjectures presented at the Third Inter- Uncountably Many Enumera tions of WQO Permuta tion Classes 23 national Conference on Permutation Patterns, University o f Florida, March 7–11, 2005. arXiv:math/0505504 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2005

  23. [23]

    Pattern avoidance is not P-recursive

    Garrabrant, S., and Pak, I. Pattern avoidance is not P-recursive. arXiv:1505.06508 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv

  24. [24]

    Permutation patterns are hard to count

    Garrabrant, S., and Pak, I. Permutation patterns are hard to count. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algo rithms (SODA) . ACM, New York, New York, 2016, pp. 923–936

    work page 2016

  25. [25]

    Ordering by divisibility in abstract algebras

    Higman, G. Ordering by divisibility in abstract algebras. Proc. London Math. Soc. (3) 2 , 1 (1952), 326–336

    work page 1952

  26. [26]

    Grid classes and the Fibonacci dichotomy for restricted permutations

    Huczynska, S., and V atter, V. Grid classes and the Fibonacci dichotomy for restricted permutations. Electron. J. Combin. 13 (2006), Paper 54, 14 pp

    work page 2006

  27. [27]

    On growth rates of closed permutation classes

    Kaiser, T., and Klazar, M. On growth rates of closed permutation classes. Electron. J. Combin. 9 , 2 (2003), Paper 10, 20 pp

    work page 2003

  28. [28]

    Well-quasi-ordering, the tree theorem, and Vazsonyi’s con jecture

    Kruskal, J. Well-quasi-ordering, the tree theorem, and Vazsonyi’s con jecture. Trans. Amer. Math. Soc. 95 , 2 (1960), 210–225

    work page 1960

  29. [29]

    Interview with Richard P

    Mansour, T. Interview with Richard P. Stanley. Enum. Combin. Appl. 1 , 1 (2021), Article S3I1, 8 pp

    work page 2021

  30. [30]

    Excluded permutation matrices and the Stanley–Wilf conjec - ture

    Marcus, A., and Tardos, G. Excluded permutation matrices and the Stanley–Wilf conjec - ture. J. Combin. Theory Ser. A 107 , 1 (2004), 153–160

    work page 2004

  31. [31]

    forbidden

    Noonan, J., and Zeilberger, D. The enumeration of permutations with a prescribed number of “forbidden” patterns. Adv. in Appl. Math. 17 , 4 (1996), 381–407

    work page 1996

  32. [32]

    Sur l'\'enum\'eration de structures discr\`etes, une approche par la th\'eorie des relations

    Oudrar, D. Sur l’énumération de structures discrètes, une approche par la théorie des rela- tions. PhD thesis, Université des Sciences et de Technologie Houa ri Boumediene, 2015. Also available as arXiv:1604.05839 [math.CO]

    work page internal anchor Pith review Pith/arXiv arXiv 2015

  33. [33]

    Minimal prime ages, words and permutation graphs

    Oudrar, D., Pouzet, M., and Zaguia, I. Minimal prime ages, words and permutation graphs. arXiv:2206.01557

    work page arXiv

  34. [34]

    Growth rates of permutation classes: categorization up to t he uncountability threshold

    Pantone, J., and V atter, V. Growth rates of permutation classes: categorization up to t he uncountability threshold. Israel J. Math. 236 , 1 (2020), 1–43

    work page 2020

  35. [35]

    Un bel ordre d’abritement et ses rapports avec les bornes d’u ne multirelation

    Pouzet, M. Un bel ordre d’abritement et ses rapports avec les bornes d’u ne multirelation. C. R. Acad. Sci. Paris Sér. A-B 274 (1972), A1677–A1680

    work page 1972

  36. [36]

    Sur la théorie des relations

    Pouzet, M. Sur la théorie des relations . PhD thesis, Université Claude-Bernard (Lyon 1), 1978

    work page 1978

  37. [37]

    V atter, V.Permutation classes of every growth rate above 2. 48188. Mathematika 56, 1 (2010), 182–192

    work page 2010

  38. [38]

    Small permutation classes

    V atter, V. Small permutation classes. Proc. Lond. Math. Soc. (3) 103 , 5 (2011), 879–921

    work page 2011

  39. [39]

    Permutation classes

    V atter, V. Permutation classes. In Handbook of Enumerative Combinatorics , M. Bóna, Ed. CRC Press, Boca Raton, Florida, 2015, pp. 754–833

    work page 2015

  40. [40]

    Growth rates of permutation classes: from countable to unco untable

    V atter, V. Growth rates of permutation classes: from countable to unco untable. Proc. Lond. Math. Soc. (3) 119 , 4 (2019), 960–997

    work page 2019