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 →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
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.
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
- 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.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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)
- [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.
- [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.
- [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)
- [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.
- [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.
- [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.
- [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.
- [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
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
free parameters (2)
- m (maximum pattern length searched) =
4 or 5 in the applications (e.g., BiSC(D≤4,4), BiSC(A≤5,4))
- N (input prefix length) =
4, 5, or 6 in the applications
assumptions (3)
- standard math Mesh patterns are defined as in Brändén and Claesson [BC11]; the algorithm operates on this formalism.
- 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.
- ad hoc to paper The redundancy removal step in Gen (Algorithm 2, line 5) never removes patterns necessary for the minimal basis.
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
Reference graph
Works this paper leans on
-
[1]
Bjarki Agustsson, Ragnar Ardal, Christian Bean, Jon Steinn Eliasson, Tomas Ken Magnusson, \' E mile Nadeau, Jay Pantone, and Henning Ulfarsson, Permuta
-
[2]
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)
work page 2012
-
[3]
M. D. Atkinson and Robert Beals, Permutation involvement and groups, Q. J. Math. 52 (2001), no. 4, 415--421
work page 2001
-
[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
arXiv 2022
-
[5]
Albert, Young classes of permutations, Australas
M. Albert, Young classes of permutations, Australas. J. Combin. 54 (2012), 49
work page 2012
-
[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)
work page 1998
-
[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
work page 1964
-
[8]
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)
work page 2011
Show all 25 references
-
[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
2021
-
[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
2011
-
[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
2007
-
[12]
Giulio Cerbai, Anders Claesson, and Luca Ferrari, Stack sorting with restricted stacks, Journal of Combinatorial Theory, Series A 173 (2020), 105230 (en)
2020
-
[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
1978
-
[14]
Claesson, Personal communication, 2012
A. Claesson, Personal communication, 2012
2012
-
[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
2016
-
[16]
Sergi Elizalde, Permutations and -shifts , J. Combin. Theory Ser. A 118 (2011), no. 8, 2474--2497
2011
-
[17]
Hannah, Personal communication, 2012
S. Hannah, Personal communication, 2012
2012
-
[18]
C. A. R Hoare, Quicksort, Comput. J. 5 (1962), 10--16
1962
-
[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
1975
-
[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
1990
-
[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
2014
-
[22]
N. J. A. Sloane, The on-line encyclopedia of integer sequences, published electronically at http://www.oeis.org, 2012
2012
-
[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
1994
-
[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
2011
-
[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
1990
Reviewed August 12, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.