REVIEW 4 major objections 4 minor 13 references
Finite Permutation Groups with Few Orbits Under the Action on the Power Set
T0 review · 4 major / 4 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read Every permutation group whose powerset action has exactly n+r orbits is classified for 2≤r≤15.
desk verdict New classification tables for the n+r set-orbit problem (r=2..15), but completeness for r=13-15 is delegated to unshown computation and the n<=81 bound in Corollary 2.8 is not established as written. 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 set-orbit: an orbit of $G$ on the collection of all subsets of $\{1,\dots,n\}$, with $s(G)$ counting all such orbits. The argument is carried by a chain of reductions. A monotonicity theorem, saying that for $t\le n/2$ the number of $t$-set-orbits never decreases as $t$ increases, turns a small number of orbits at one cardinality into a cascade of forced orbits. A prime-gap estimate (a prime always exists between $x$ and $9x/8$ for $x\ge 48$) is used with a transitivity bound to show that, for $r<16$, a group not containing the alternating group must have degree $n\le 81$. Parity constraints, together with lower bounds for intransitive and imprimitive groups in terms of orbit products and binomial coefficients, eliminate most degrees and force surviving candidates to be transitive or primitive. Finally, divisibility of $|G|$ by binomial coefficients, followed by a GAP computation over all remaining transitive and primitive groups, yields the tables.
What would settle it
Run the published GAP code independently and compare its output with the tables; any group whose computed $s(G)$ equals $n+r$ but is absent from the tables, or any listed group whose recomputed $s(G)$ differs from $n+r$, would falsify the completeness claim. A direct first check is to recompute $s(G)$ for every listed group from its generators and verify the table value.
Extended reading notes
Core claim
For each integer $r$ with $2\le r\le 15$, the paper claims to have determined every permutation group $G \subseteq S_n$ whose induced action on the power set $\mathscr{P}(\{1,\dots,n\})$ has exactly $s(G)=n+r$ orbits. The answer is a finite list for each $r$, tabulated with the degree, order, and a GAP identifier; for $r=12$ through $15$ the elimination of intransitive and imprimitive groups is described (in detail for $r=12$) and the remaining cases are computed. The classification is exhaustive in the sense that any group with $n+r$ set-orbits appears in the corresponding table, and no group outside the table has that count. This extends the classical $r=1$ classification of set-transitive groups.
Load-bearing premise
The classification is complete only if the published elimination lemmas and the GAP code together cover every intransitive, imprimitive, transitive, and primitive group for each $r\le 15$; for $r=13,14,15$ the paper outlines the elimination by analogy with the detailed $r=12$ case rather than writing it out.
Editorial extensions
If this is right
- For every $r$ from $2$ to $15$, the tables are exhaustive: no permutation group outside the listed ones has exactly $n+r$ set-orbits.
- The reduction method is reusable: for any fixed $r$ it bounds $n$, eliminates intransitive and imprimitive groups, and reduces the check to transitive and primitive candidates, so larger $r$ can be attempted by the same route.
- If $G$ does not contain the alternating group and has fewer than $n+16$ set-orbits, then $n\le 81$, so the whole classification problem for small $r$ is finite and bounded.
- The $r=1$ case is included as the base of the same framework, so the set-transitive classification and its near neighbours are treated uniformly.
Reading between the lines
- The tables reveal a family the paper does not isolate: for $r=n$, the groups $S_{n-1}$ and $A_{n-1}$ acting on $n$ points with one fixed point have exactly $2n=n+r$ set-orbits, so any classification for unrestricted $r$ must contain this family for every $n$.
- Because the expensive step is enumerating all subgroups of $S_n$ for $n\ge 12$, a classification beyond $r=15$ would likely advance most by a theoretical treatment of intransitive and imprimitive groups, not by faster orbit-counting.
- The parity and monotonicity constraints appear to be the main force fixing small $r$: for large $n$ they rule out most degrees before any group-specific computation is needed, which is why the tables contain mostly small degrees.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies the natural action of a permutation group G ≤ S_n on the power set of an n-element set and classifies, for 2 ≤ r ≤ 15, all groups G with exactly n + r set-orbits. The method combines a theoretical bound on the degree n (Corollary 2.8 and Step 0), elimination of intransitive and imprimitive groups via Lemmas 2.10 and 2.11, classification of primitive groups using GAP's primitive-group library, and enumeration of subgroups of S_n for small n. The authors present hand-worked classifications for r = 2, 3, 4, 5 and computer-assisted tables for r = 6 through 15, together with a brief discussion of the r = 12 elimination and a statement that r = 13, 14, 15 follow 'very similarly'.
Significance. If the classification tables are complete, this is a substantial extension of the Beaumont–Peterson classification of set-transitive groups and of Kantor's work on k-set-transitive groups. The paper also contributes a general template (Step 0 through Step 4) that could in principle be applied to larger r. A notable strength is that the theoretical reductions use standard results (Livingstone–Wagner, Breusch, Beaumont–Peterson) and that the tables give explicit groups, orders, and GAP identifiers, making the claims concrete and falsifiable. However, the completeness of the central claim depends on computational work that is not fully reproducible from the manuscript, and one of the stated degree bounds is not justified by the argument given.
major comments (4)
- [§4, 'Remaining Computations' and §5] The completeness of the classification for r = 13, 14, 15 is asserted but not demonstrated. Section 4 states that 'the process will be very similar' and then immediately lists tables; no surviving-degree lists, no intransitive/imprimitive elimination details, and no exhaustive-search certificate are supplied for these three values. Since the central claim of the paper is that the tables are exhaustive for every r ≤ 15, this is a load-bearing gap, not a presentation issue.
- [§2, Corollary 2.8, and §3, Step 0] The stated bound n ≤ 81 for groups with s(G) < n + 16 is not established by the reasoning in the text. The argument notes that n = 81 yields k0 = 7 and says this gives 'at least 14 additional set-orbits', but 14 additional orbits is compatible with s(G) = n + 15, i.e. with r = 15. To exclude n > 81 one needs at least 15 additional orbits (or a separate argument); no such argument appears. In particular, the statement that 'for any reasonable r, say r < 16, we know that n ≤ 81' is not justified by Theorem 2.7 as used.
- [§4, 'Remaining Computations'] For r = 12 the paper works out the elimination only for n = 12, saying other possible n values 'can be checked in a similar way.' Since the intended range of n is not explicitly listed, and since Lemmas 2.10 and 2.11 provide lower bounds that must be individually compared with n + r, the reader cannot verify that all intransitive and imprimitive degrees in the relevant range are eliminated. The same concern applies a fortiori to r = 13, 14, 15.
- [§5 and reference [8]] The classification relies on GAP computations that are not included in the paper or in an appendable artifact. Reference [8] is an external URL with no version identifier, hash, or log of the computation, and no machine-checked certificate is provided. For a computational classification with completeness as the main claim, the absence of a reproducible and auditable computation makes the result unverifiable as currently presented.
minor comments (4)
- [§2, Corollary 2.6 proof] In the proof of Corollary 2.6, 'If G is even' should read 'If n is even'; the current wording is a typographical slip that could confuse readers.
- [§4, r = 4 paragraph] The phrase 'the primitive groups on 8, 10, 12 letters that whose order is divisible by 28, 120, 495' contains a redundant 'that whose'; the intended meaning is clear but the sentence should be rewritten.
- [§4, tables for r = 12 and r = 13] The tables list entries such as '12 A11' and '13 A12' without comment; these are presumably point stabilizers of A11 in S12 and A12 in S13, but this should be stated explicitly because it aids the reader in checking the table against the definition of degree n.
- [References] Reference [7] is a URL rather than a stable bibliographic entry; if the transitive-group structures are being cited, a more permanent source (such as the GAP small-groups library or Butler–McKay tables) should be given.
Circularity Check
No circularity found: the derivation chain uses external classical theorems and an independent GAP computation; the unshown completeness for r=13–15 is a verification gap, not a circular step.
full rationale
The paper's central claim—a complete classification of permutation groups with s(G)=n+r set-orbits for 2≤r≤15—is not obtained by fitting a parameter and then predicting that same parameter, nor by importing a self-authored uniqueness theorem. The reduction chain is built from external inputs: Lemma 2.2 uses the elementary symmetry s_t(G)=s_{n-t}(G); Theorem 2.3 is the Livingstone–Wagner monotonicity theorem; Lemmas 2.4 and 2.5 and Corollary 2.6 rely on Beaumont–Peterson transitivity facts and Breusch's prime-gap theorem; Step 2 invokes Miller's transitivity bound; Step 3 uses Beaumont–Peterson divisibility and primitivity results; and Step 4 delegates the enumeration to GAP with code made available at reference [8]. None of these inputs restates the target classification. The only self-citation in the paper is [13], by author Yang, and it appears in the introduction solely as background on solvable groups and power-set orbits; it is not load-bearing for any theorem or table in this paper. The passage 'we list the results for 13 ≤ r ≤ 15 as the process will be very similar' does assert completeness without exhibiting the detailed elimination for those three values, and Corollary 2.8's n≤81 bound is not fully justified in the text. These are legitimate correctness and verifiability concerns, but they are not circularity: the asserted results are not defined in terms of the method's outputs, no fitted constant is renamed as a prediction, and no self-citation is used to forbid alternatives. Accordingly the paper is self-contained against external benchmarks and receives score 0.
Assumptions & free parameters
assumptions (7)
- standard math Beaumont-Peterson classification of set-transitive groups and the criterion that t-set-transitivity for 2≤t≤floor(n/2) implies primitivity (Theorems 5 and 6 of [2]).
- standard math Livingstone-Wagner monotonicity: s_{t-1}(G) ≤ s_t(G) for 1≤t≤n/2 (Theorem 2.3).
- standard math Breusch's prime theorem: for every x≥48 there is a prime p with x < p < 9x/8.
- standard math Burnside's bound: a permutation group not containing A_n is at most n/3+1-transitive (cited to [4, page 152]).
- standard math Miller's theorem on transitivity of groups of degree n = m p0 + r (from [11]).
- domain assumption GAP primitive group library is complete for degree up to 4096, and the transitive group databases used are complete for the degrees considered.
- standard math Babai-Pyber inequalities relating orbit counts of subgroups (Lemma 2.9) and intransitive products (Lemma 2.10).
Cite this review
Pith. "Pith review of Finite Permutation Groups with Few Orbits Under the Action on the Power Set." pith.science (2026). https://pith.science/paper/SWEGLKJD
@misc{pith2026190800613,
author = {Pith},
title = {Pith review of: Finite Permutation Groups with Few Orbits Under the Action on the Power Set},
year = {2026},
howpublished = {\url{https://pith.science/paper/SWEGLKJD}},
note = {Machine review of arXiv:1908.00613}
}
abstract
We study the orbits under the natural action of a permutation group $G \subseteq S_n$ on the powerset $\mathscr{P}(\{1, \dots , n\})$. The permutation groups having exactly $n+1$ orbits on the powerset can be characterized as set-transitive groups and were fully classified in \cite{BP55}. In this paper, we establish a general method that allows one to classify the permutation groups with $n+r$ set-orbits for a given $r$, and apply it to integers $2 \leq r \leq 15$ using the computer algebra system GAP.
Reference graph
Works this paper leans on
-
[12]
O. Morgenstern and J. von Neumann, Theory of Games and Economic Behavior , Princeton, Univ. Press, Princeton, NJ, 1947
work page 1947
-
[8]
https://www.math.txstate.edu/research-conferences/summerreu/yang documents.html
-
[1]
L. Babai and L. Pyber, Permutation groups without expone ntially many orbits on the power set, J. Comb. Theory A 66 (1998), 160-168
work page 1998
-
[2]
R. A. Beaumont and R. P. Peterson, Set-transitive permut ation groups, Canad. J. Math. 7 (1955), 35-42
work page 1955
-
[3]
R. Breusch, Zur Verallgemeinerung des Bertrandschen Po stulates, das zwischen x and 2 x stets Primzahlen liegen, [To generalize Bertrand’s postulate, which is alwa ys a prime between x and 2 x] Math. Z. 34 (1932), 505-526
work page 1932
-
[4]
Burnside, Theory of Groups , Cambridge, 1897
W. Burnside, Theory of Groups , Cambridge, 1897
-
[5]
P. J. Cameron, Regular orbits of permutation groups on th e power set, Discrete Math. 62 (1986), 307-309
work page 1986
-
[6]
The GAP Group, GAP – Groups, Algorithms, and Programming , Version 4.11.0; 2020. (https://www.gap-system.org)
work page 2020
Show all 13 references
-
[7]
https://people.maths.bris.ac.uk/∼ matyd/GroupNames/T31.html
-
[9]
W. M. Kantor, k-homogeneous groups, Math. Z. 124 (1972), 261-265
1972
-
[10]
Livingstone and A
D. Livingstone and A. Wagner, Transitivity of finite per mutation groups on unordered sets, Math. Z. 90 (1965), 393-403
1965
-
[11]
G. A. Miller, Collected works , vols 1 and 3, Urbana, 1935 and 1946
1935
-
[13]
Yang, Solvable permutation groups and orbits on powe r sets, Comm
Y. Yang, Solvable permutation groups and orbits on powe r sets, Comm. Algebra 42 (2014), 2813-2820. Department of Mathematics, Le Moyne College, 1419 Salt Spri ngs Road, Syracuse, NY 13214 Email address : betzas@lemoyne.edu Department of Mathematics, Harvey Mudd College, 340 E...
2014
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.