Pith. sign in

REVIEW 3 major objections 5 minor 25 references

BiSC: An algorithm for discovering generalized permutation patterns

T0 review · 3 major / 5 minor · reviewed 2026-08-12 · deepseek-v4-flash

Pith's one-line read Given a finite prefix of a permutation set, BiSC recovers the exact mesh-pattern basis whenever a bounded finite basis exists.

desk verdict A genuinely useful algorithm for conjecturing mesh pattern bases, but Theorem 2.4 is false as stated and needs a simple condition fix. read the letter →

arxiv 2411.17778 v1 pith:P6JTFHK5 submitted 2024-11-26 math.CO

classification math.CO MSC 05A05
keywords permutationpatternsmeshpatternavoidancealgorithmicconjecturediscoveryclassesWilf-equivalencestack-sortablepermutations
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

Many theorems that connect permutations to other areas of mathematics are statements of the form: a certain set of permutations is exactly the set avoiding one or more forbidden patterns. This paper presents BiSC, an algorithm that takes a finite list of permutations and searches for such a description in the more expressive language of mesh patterns, where a pattern may also forbid letters from occupying certain regions. The paper proves that BiSC never outputs a pattern that is contained in the input, and that if the target set truly has a finite forbidden-pattern basis whose longest pattern has length at most $k$, then feeding it the prefix up to length at least $k$ yields an exact description, not just a guess. On known examples the algorithm rediscovers the pattern bases for the smooth, forest-like, Baxter, stack-sortable, and 2-stack-sortable permutation families, and it has produced new conjectured bases for the dihedral and alternating subgroups, Young-tableaux shapes, Wilf-equivalences, and restricted sorting devices. The reader should care because this turns a finite witness list into a certified theorem whenever a bounded description exists, and into an automated conjecture-generator for the many cases where no bound is known.

What carries the argument

The central object is the mesh pattern: a classical pattern with some of the unit squares of its diagram shaded, where an occurrence of the pattern must not place any chosen letters in a shaded square. The algorithm has two phases. Mine scans every subword of every input permutation and, for each classical pattern that appears, records the maximal shading that still keeps some occurrence inside the input; Gen takes the complementary minimal shadings as candidate forbidden patterns and deletes any candidate that is already a consequence of a smaller forbidden pattern. Lemma 2.1 is what guarantees no input permutation is forbidden, and Lemma 2.2 is what guarantees classical-only output for classes defined by classical patterns. The argument therefore runs on the shading lattice of a pattern rather than on the permutations themselves, which is what lets a finite prefix rule out infinitely many possible descriptions.

What would settle it

To test Theorem 2.3, take any set $B$ with a known finite mesh-pattern basis of length $k$, compute $\mathrm{BiSC}(B_{\le N}, m)$ with $N$ and $m$ at least $k$, and compare $\mathrm{Av}(\mathrm{BiSC}(B_{\le N}, m))$ with $B$ at length $k+1$: any extra permutation allowed, or any member of $B$ forbidden, would refute it. For the dihedral-basis conjecture, one can check the 16 listed patterns directly by finding the first length at which a permutation avoiding all 16 is not in the union of the dihedral subgroups.

Watch

Extended reading notes

Core claim

The central claim, formalized as Theorems 2.3 and 2.4, is that the two-step procedure $\mathrm{BiSC} = \mathrm{Gen}(\mathrm{Mine}(A, m))$ is sound and, under a bound, complete. For any set $A$ of permutations, writing $A_{\le N}$ for the permutations of length at most $N$, the output of $\mathrm{BiSC}(A_{\le N}, m)$ never forbids any permutation in $A_{\le n}$ for $n \le N$. If $A$ is defined by a finite list of mesh patterns, with classical patterns as the special case of empty shading, whose longest pattern has length $k$, and if $N \ge n \ge k$ and $m \ge k$, then $A_{\le n}$ exactly equals the set of permutations of length at most $n$ avoiding the output. A separate theorem says that if $A$ is originally defined by classical patterns alone, the output contains only classical patterns, so shaded patterns never appear for such classes. For classes whose true basis is infinite, with the alternating subgroups as the paper's example, BiSC returns only a finite conjecture and the equality guarantee does not apply.

Load-bearing premise

The paper's equality guarantee assumes the permutation set really is defined by finitely many forbidden mesh patterns whose longest pattern has length at most $k$, and that the input prefix is taken to length at least $k$; if either fails, the output is only a conjecture.

Editorial extensions

If this is right

  • If a set is known to have a finite basis of patterns of length at most $k$, then its prefix of length $k$ contains all the information needed to prove the full description, so no extra human pattern-hunting is required.
  • For sets defined by classical patterns alone, the algorithm's output is automatically classical, which gives a cheap way to detect that a proposed set is not a classical permutation class: run BiSC and look for any shaded pattern.
  • The same finite-prefix pipeline can be applied to any permutation set arising in geometry, analysis, or computer science, turning an object-level list of permutations into a proposed theorem statement.
  • The rediscovered bases for smooth, forest-like, Baxter, stack-sortable, and 2-stack-sortable permutations serve as a self-check: when the algorithm reproduces a published theorem from data, its new conjectures inherit some credibility, though not proof.
  • For sets that genuinely need infinitely many forbidden patterns, such as the alternating subgroups, the algorithm still produces its best finite guess; a proof of such an infinite description must come from outside the algorithm.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • A natural extension the paper leaves implicit: running BiSC at increasing values of $m$ and watching the output stabilise could serve as a practical convergence test for when a class has a bounded basis, even when no bound is known in advance.
  • Since Mine records maximal allowed shadings for every pattern, the intermediate data could be reused for other tasks, such as comparing two permutation classes by their allowed patterns or systematically searching for Wilf-equivalences across many bases.
  • The classical-only theorem suggests a screening rule for the literature: if a set claimed to be a classical permutation class produces any shaded pattern in BiSC's output, that claim is immediately suspect without needing to construct a counterexample.
  • If the algorithm is run on finite prefixes of sets whose true descriptions are infinite, the pattern of its outputs across increasing $n$ might itself hint at the structure of the infinite basis, for example by exhibiting all fully shaded patterns in the alternating-subgroup case.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

3 major / 5 minor

Summary. The paper presents BiSC, a two-stage algorithm for conjecturing mesh-pattern descriptions of permutation sets from a finite prefix. Stage one (Mine) records, for each classical pattern up to a chosen length, the maximal shadings that occur in the input permutations; stage two (Gen) derives minimal forbidden shadings and prunes redundant ones. The paper states correctness theorems (Theorems 2.3 and 2.4), reports that BiSC rediscovers several known permutation-class bases, and presents new conjectures for the dihedral and alternating subgroups, Young-tableaux shapes, Wilf-equivalences, and stack-sorting devices. The implementation is part of the Permuta library.

Significance. If the correctness statements can be repaired, BiSC is a genuinely useful conjecture generator: the rediscovery of known bases, including non-classical mesh-pattern bases, is strong empirical evidence that the algorithm captures the right notion of pattern inference. The reproducible implementation and the concrete new conjectures, especially Conjectures 2.4.1-2.4.4, are valuable for the permutation-pattern community. However, the central exactness guarantee for classical bases is currently false as stated, and the pruning step in Gen is not formally specified or proven; these issues affect the paper's main theoretical claim rather than its empirical output.

major comments (3)
  1. [Section 2.1, Theorem 2.4] Theorem 2.4 is false as stated. Let A = Av(231), so k = 3, and run BiSC(A≤3, 5). The input A≤3 contains no permutations of length 4 or 5, so for the classical pattern p = 1234 the output of Mine(A≤3, 5) has sh_p = ∅. In Gen, since sh_p has no members, the empty shading is a minimal shading not contained in any member of sh_p, and therefore (1234, ∅) is included in BiSC(A≤3, 5). But 1234 lies in A because it avoids 231. Hence A ≠ Av(BiSC(A≤3, 5)). The theorem needs an additional hypothesis such as n ≥ m, or its equality claim must be restricted to permutations of length at most n, as already done in Theorem 2.3.
  2. [Algorithm 2, line 5; proof of Theorem 2.3] The redundancy-removal step in Gen is not fully specified and is load-bearing for the correctness proofs. Line 5 says to remove R when it is 'a consequence of some shading in forb_q for a pattern q contained in p', but the notion of consequence is never defined, and no proof is given that removing such an R never changes the set Av(BiSC(A, m)). In the proof of Theorem 2.3 the phrase 'Without loss of generality, we assume that R′′ is not removed due to redundancy in line 5' is not a WLOG assumption; it is an unproven correctness property of the pruning step. The theorems should be proved either for the unpruned algorithm or for a precisely defined pruning rule with a proof that it preserves the avoided set.
  3. [Proof of Theorem 2.4] The proof of Theorem 2.4 consists only of 'This follows from Lemma 2.2', but Lemma 2.2 has the hypothesis sh_q ≠ ∅. For a forbidden basis pattern q ∈ P, the input prefix A≤n contains no occurrence of q, so Mine returns sh_q = ∅ and Lemma 2.2 does not apply. A separate argument is needed to show that forb_q then contains the empty shading, which is what makes q a forbidden classical pattern. This gap is independent of the missing n ≥ m hypothesis and must be repaired for the theorem's proof to be complete.
minor comments (5)
  1. [Section 2.1, Algorithm 1] The symbol ∅ is overloaded: it denotes both the empty shading (as in the mesh pattern (p, ∅)) and the empty set of shadings in the initial value of sh_p in Algorithm 1. This makes the initialization 'S = {(p, ∅)}' ambiguous and should be clarified, for example by writing sh_p = ∅ explicitly.
  2. [Section 2.2 and Conjectures] Several displayed outputs are missing from the text as provided: for example, after 'The output of BiSC(A≤5, 4) is the following.' and after the discussion of Conjecture 2.4.3, the mesh-pattern diagrams do not appear. The final version must include all figures so the conjectures can be checked.
  3. [Conjecture 2.4.2] The conjecture states an equality for 'a basis P' but does not justify that the described family is the unique minimal basis for mesh patterns. Since uniqueness is not automatic for arbitrary mesh-pattern bases, the statement should either prove minimality/uniqueness or explicitly call this the reduced basis.
  4. [Section 2.2, simplification statements] The paper says that outputs such as the 25 mesh patterns for BiSC(A≤6, 5) 'can be simplified' to the displayed conjectures, but it does not say whether the simplification is algorithmic or manual. Specifying this would make the reproducibility claims more precise.
  5. [References] Reference [AB] (Abe and Billey) lacks full publication data, and the reference formatting is otherwise inconsistent; these should be cleaned up before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: BiSC's conjectures are deliberately fitted to a finite prefix, but the central validation uses external benchmarks and the correctness theorems are mathematical claims, not reductions to their inputs.

full rationale

The BiSC pipeline has two stages: Mine records allowed mesh-pattern shadings found in the input prefix, and Gen outputs minimal shadings not recorded as allowed. Thus the subset relation A≤n ⊆ Av(BiSC(A≤N,m))≤n is true by construction; the paper presents this as a sanity property, not as an independent prediction. The nontrivial equality claims in Theorems 2.3 and 2.4 are argued from the assumption that A has a finite pattern basis of length k, using lemmas about Mine and Gen directly; they are not obtained by citing the author's own results. The only self-citations are to the author's definitions and software: marked mesh patterns ([Ulf11, Def. 4.5]) and the Permuta library [AAB+]. These appear as notation and implementation tools, not as load-bearing external theorems, so they do not create circularity. The 'rediscovery' of Table 1 is checked against independent published theorems (Knuth, West, Lakshmibai–Sandhya, Chung–Graham–Hoggatt–Kleiman, etc.), which is the appropriate external validation. Two weaknesses are present but are correctness concerns, not circularity: (i) the implementation's pruning step is asserted without proof; and (ii) Theorem 2.4's equality claim fails when m > n, e.g. for A = Av(231), BiSC(A≤3, 5) would output a spurious 1234 since the prefix contains no length-4 or length-5 permutation, so equality requires n ≥ m. Neither weakness makes the derivation equivalent to its input by definition. No self-definitional identification, fitted-parameter-as-prediction, or author-imported uniqueness step occurs.

Assumptions & free parameters 2 free parameters · 3 assumptions · 0 invented entities

The algorithm's correctness depends on user-chosen parameters N and m, on the finite-basis assumption, and on the unproved soundness of the pruning step. No new mathematical entities are introduced; the marked mesh patterns used in Conjecture 2.4.3 come from prior work [Ulf11].

free parameters (2)
  • m (maximum pattern length searched) = 4 or 5 in the applications (e.g., BiSC(D≤4,4), BiSC(A≤5,4))
    The algorithm searches for patterns up to length m. If the true basis contains a pattern longer than m, the conjecture is incomplete. The value is chosen by the user based on the expected pattern length.
  • N (input prefix length) = 4, 5, or 6 in the applications
    The input is A≤N. The correctness theorem requires N ≥ k where k is the longest basis pattern length. In experiments, N is set to m or m+1; too small a prefix can yield spurious patterns.
assumptions (3)
  • standard math Mesh patterns are defined as in Brändén and Claesson [BC11]; the algorithm operates on this formalism.
    Section 2 defines mesh patterns via shading R and cites [BC11].
  • domain assumption The target set A is definable by a finite list of (classical or mesh) patterns with longest pattern length k, and the input A≤N must satisfy N ≥ k.
    Theorem 2.3's equality statement and Theorem 2.4 rely on the existence of a finite basis of bounded length. Without this, the output is only a conjecture, as stated in Section 3.
  • ad hoc to paper The redundancy removal step in Gen (Algorithm 2, line 5) never removes patterns necessary for the minimal basis.
    The proof of Theorem 2.3 says 'Without loss of generality, we assume that R'' is not removed due to redundancy in line 5.' The paper omits details of the pruning step and asserts it is never a problem in the applications, but gives no proof.

how reviews work

0 comments
Cite this review

Pith. "Pith review of BiSC: An algorithm for discovering generalized permutation patterns." pith.science (2026). https://pith.science/paper/P6JTFHK5

@misc{pith2026241117778,
  author       = {Pith},
  title        = {Pith review of: BiSC: An algorithm for discovering generalized permutation patterns},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/P6JTFHK5}},
  note         = {Machine review of arXiv:2411.17778}
}
read the original abstract

Theorems relating permutations with objects in other fields of mathematics are often stated in terms of avoided patterns. Examples include various classes of Schubert varieties from algebraic geometry (Billey and Abe 2013), commuting functions in analysis (Baxter 1964), beta-shifts in dynamical systems (Elizalde 2011) and homology of representations (Sundaram 1994). We present a new algorithm, BiSC, that, given any set of permutations, outputs a conjecture for describing the set in terms of avoided patterns. The algorithm automatically conjectures the statements of known theorems such as the descriptions of smooth (Lakshmibai and Sandhya 1990) and forest-like permutations (Bousquet-M{\'e}lou and Butler 2007), Baxter permutations (Chung et al. 1978), stack-sortable (Knuth 1975) and West-2-stack-sortable permutations (West 1990). The algorithm has also been used to discover new theorems and conjectures related to the dihedral and alternating subgroups of the symmetric group, Young tableaux, Wilf-equivalences, and sorting devices.

Figures

Figures reproduced from arXiv: 2411.17778 by the authors.

Figure 1
Figure 1. Applying the maximal shading to the classical pattern 12 so [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. The mesh patterns (p, R) and (q, R′ ) We now define the full algorithm as BiSC(A, m) = Gen(Mine(A, m)). The next two theorems show that the output of BiSC is correct, in the sense that it will never output patterns contained in a permutation in the input, and can give a proof of the description if a bound is known on the length of the patterns. Theorem 2.3. Let A be any set of permutations. Then for all positive int… view at source ↗
Figure 3
Figure 3. A binary tree and its corresponding mesh pattern, see [PS [PITH_FULL_IMAGE:figures/full_fig_p009_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

25 extracted references · 24 canonical work pages

  1. [1]

    Bjarki Agustsson, Ragnar Ardal, Christian Bean, Jon Steinn Eliasson, Tomas Ken Magnusson, \' E mile Nadeau, Jay Pantone, and Henning Ulfarsson, Permuta

  2. [2]

    1--52 (en)

    Hiraku Abe and Sara Billey, Consequences of the Lakshmibai - Sandhya Theorem : T he ubiquity of permutation patterns in Schubert calculus and related geometry , Schubert Calculus —- Osaka 2012, pp. 1--52 (en)

  3. [3]

    M. D. Atkinson and Robert Beals, Permutation involvement and groups, Q. J. Math. 52 (2001), no. 4, 415--421

  4. [4]

    Michael H. Albert, Christian Bean, Anders Claesson, \'Emile Nadeau, Jay Pantone, and Henning Ulfarsson, Combinatorial E xploration: An algorithmic framework for enumeration , https://arxiv.org/abs/2202.07715, 2022

  5. [5]

    Albert, Young classes of permutations, Australas

    M. Albert, Young classes of permutations, Australas. J. Combin. 54 (2012), 49

  6. [6]

    M. D. Atkinson, Permutations which are the union of an increasing and a decreasing subsequence, Electron. J. Combin. 5 (1998), Research paper 6, 13 pp.\ (electronic)

  7. [7]

    Baxter, On fixed points of the composite of commuting functions, Proc

    G. Baxter, On fixed points of the composite of commuting functions, Proc. Amer. Math. Soc. 15 (1964), 851--855

  8. [8]

    Br \"a nd \'e n and A

    P. Br \"a nd \'e n and A. Claesson, Mesh patterns and the expansion of permutation statistics as sums of permutation patterns, Electron. J. Combin. 18 (2011)

Show all 25 references
  1. [9]

    Jean-Luc Baril, Giulio Cerbai, Carine Khalil, and Vincent Vajnovszki, Catalan and schröder permutations sortable by two restricted stacks, Information Processing Letters 171 (2021), 106138

  2. [10]

    Billey, Consequences of the L akshmibai- S andhya theorem , AWM A nniversary C onference, 2011

    S. Billey, Consequences of the L akshmibai- S andhya theorem , AWM A nniversary C onference, 2011

  3. [11]

    Bousquet-M \'e lou and S

    M. Bousquet-M \'e lou and S. Butler, Forest-like permutations, Ann. Comb. 11 (2007), no. 3-4, 335--354

  4. [12]

    Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, Journal of Combinatorial Theory, Series A 173 (2020), 105230 (en)

  5. [13]

    F. R. K. Chung, R. L. Graham, V. E. Hoggatt, Jr., and M. Kleiman, The number of B axter permutations , J. Combin. Theory Ser. A 24 (1978), no. 3, 382--394

  6. [14]

    Claesson, Personal communication, 2012

    A. Claesson, Personal communication, 2012

  7. [15]

    Warrington, Shape and pattern containment of separable permutations, Ars Comb

    Andrew Crites, Greta Panova, and Gregory S. Warrington, Shape and pattern containment of separable permutations, Ars Comb. 128 (2016), 103--116

  8. [16]

    Sergi Elizalde, Permutations and -shifts , J. Combin. Theory Ser. A 118 (2011), no. 8, 2474--2497

  9. [17]

    Hannah, Personal communication, 2012

    S. Hannah, Personal communication, 2012

  10. [18]

    C. A. R Hoare, Quicksort, Comput. J. 5 (1962), 10--16

  11. [19]

    D. E. Knuth, The art of computer programming, second ed., Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1975, Volume 1: Fundamental algorithms, Addison-Wesley Series in Computer Science and Information Processing

  12. [20]

    Lakshmibai and B

    V. Lakshmibai and B. Sandhya, Criterion for smoothness of S chubert varieties in Sl (n)/B , Proc. Indian Acad. Sci. Math. Sci. 100 (1990), no. 1, 45--52

  13. [21]

    Lara Pudwell, Connor Scholten, Tyler Schrock, and Alexa Serrato, Noncontiguous pattern containment in binary trees, International Scholarly Research Notices 2014 (2014), no. 1, 8

  14. [22]

    N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.oeis.org, 2012

  15. [23]

    Sundaram, The homology representations of the symmetric group on C ohen- M acaulay subposets of the partition lattice , Adv

    S. Sundaram, The homology representations of the symmetric group on C ohen- M acaulay subposets of the partition lattice , Adv. Math. 104 (1994), no. 2, 225--296

  16. [24]

    Ulfarsson, A unification of permutation patterns related to S chubert varieties , Pure Math

    H. Ulfarsson, A unification of permutation patterns related to S chubert varieties , Pure Math. Appl. (PU.M.A.) 22 (2011), no. 2, 273--296

  17. [25]

    West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D

    J. West, Permutations with forbidden subsequences and stack-sortable permutations, Ph.D. thesis, MIT, 1990

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.