Asymptotic enumeration of minimally transitive permutation groups

Binzhou Xia; Shasha Zheng

Asymptotic enumeration of minimally transitive permutation groups

T0 review · 0 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that the known upper bound on the number of minimally transitive permutation groups, $2^{O(n\log n)}$, is best possible along powers of every fixed prime, even counting groups up to relabelling.

desk verdict Sharp lower bound matching Pyber's upper bound along prime powers, via a clever wreath-product construction and clean ideal counting; only minor presentation issues in the upper-bound section. read the letter →

arxiv 2608.25792 v1 pith:NASOJEQZ submitted 2026-08-26 math.GR math.CO

Binzhou Xia , Shasha Zheng This is my paper · ORCID

classification math.GRmath.CO MSC 20B0505A1620B35

keywords minimallytransitivepermutationgroupsasymptoticenumerationprime-powerdegreespermutationalisomorphismvertex-transitivegraphsdigraphswreathproductstruncatedpolynomialrings

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

A transitive permutation group is minimally transitive if none of its proper subgroups is transitive; every finite transitive group contains one, so these are the minimal building blocks. The paper establishes that the known upper bound of $2^{O(n\log n)}$ for how many minimally transitive subgroups of the symmetric group $S_n$ exist cannot be improved in general: for each fixed prime $p$, as the degree $n$ runs through powers of $p$, there are at least $2^{(1/p-o(1))\,n\log n}$ minimally transitive permutation groups of degree $n$, even when two groups that differ by a relabelling of the underlying set are counted as the same. The proof builds many nonregular $p$-groups inside a wreath product and distinguishes them through ideals in a truncated polynomial ring. Along prime-power degrees this pins the exponent of the count to $\Theta(n\log n)$, rules out any exponential upper bound, and, as a byproduct, shows that minimally transitive groups of degree $n$ can have order $2^{\Theta(n)}$. The same counting also determines the order of magnitude of the number of labelled vertex-transitive graphs and digraphs on $n$ vertices as $2^{\Theta(n\log n)}$.

What carries the argument

The central object is the map $\Psi\colon R^m\to R^{\binom{m+1}{2}}$ defined on $R=\mathbb{F}_p[X_1,\dots,X_m]/(X_i^p)$ by $b\mapsto (X_i^{p-1}b_i \text{ for }1\le i\le m,\; X_jb_i-X_ib_j \text{ for }1\le i<j\le m)$. For each parameter vector $b=(b_1,\dots,b_m)$, the group $G(b)$ inside $B\rtimes T$ has the property that the intersection of all maximal subgroups of $G(b)$, denoted $\Phi(G(b))$, equals $G(b)\cap B=K(b)$, the ideal generated by the coordinates of $\Psi(b)$. Three facts carry the argument: the fiber-size identity $|\ker\Psi|=p^{p^m-1}$, which follows because every complement of $B$ in $B\rtimes T$ is conjugate to $T$; a bound on how many parameter vectors can produce the same ideal; and a variance-based concentration inequality that shows the middle band of monomial degrees has dimension $(1-o(1))p^m$. Together they force at least $2^{(1/p-o(1))n\log n}$ distinct groups of degree $n=p^{m+1}$ up to permutational isomorphism.

What would settle it

For $p=2$ and $m=3$, enumerate all $2^{24}$ parameter vectors in $R^3$ and check whether exactly $2^7$ of them satisfy $\Psi(b)=0$; any other number would refute the fiber-size lemma and the counting argument behind the lower bound.

Watch

Extended reading notes

Core claim

For each fixed prime $p$, as $n$ increases as a power of $p$, the number of minimally transitive permutation groups of degree $n$, counted up to permutational isomorphism (i.e. up to conjugation in $S_n$), is at least $2^{(1/p-o(1))\,n\log n}$. This is the paper's central discovery. It matches the known upper bound $2^{O(n\log n)}$ in the exponent along those degrees, so the exponent is $\Theta(n\log n)$ when both bounds are combined, and no bound of the form $2^{O(n)}$ can hold. The groups witnessing the bound are constructed inside the imprimitive wreath product $B\rtimes T$, where $B$ is the group of functions from an $m$-dimensional $\mathbb{F}_p$-vector space $V$ to the additive group of $\mathbb{F}_p$ and $T$ is the translation group of $V$; each group $G(b)$ is generated by elements $b_i t_i$, and its intersection with $B$ equals the ideal $K(b)$ generated by the coordinates of an explicitly defined map $\Psi$. The parameter count for distinct ideals yields the lower bound, while a separate result shows there are minimally transitive groups of degree $n=p^{m+1}$ and order $n p^{n/p-p}$, so the maximal order along prime powers is $2^{\Theta(n)}$.

Load-bearing premise

The lower-bound construction relies on the exact count of choices that produce the same group: it assumes that all possible complements of the base group in the wreath product are conjugate to one another, which fixes the number of parameter vectors collapsing to a single group at $p^{p^m-1}$. If that count were larger, the number of distinct minimally transitive groups produced would drop below the claimed bound.

Editorial extensions

If this is right

Combining the lower bound with the known upper bound determines the exponent: along powers of each fixed prime $p$, the number of minimally transitive subgroups of $S_n$ is $2^{\Theta(n\log n)}$, both counted directly and up to permutational isomorphism.
No exponential upper bound $2^{O(n)}$ is possible for minimally transitive permutation groups, even after identifying permutationally isomorphic groups.
Along prime-power degrees, the maximum order of a minimally transitive permutation group of degree $n$ is $2^{\Theta(n)}$: the construction supplies groups of order $n p^{n/p-p}$, and the standard bound on the order of a $p$-subgroup of $S_n$ gives the matching upper bound.
The number of labelled vertex-transitive graphs of order $n$ and the number of labelled vertex-transitive digraphs of order $n$ are both $2^{\Theta(n\log n)}$, improving the previous upper bound of the form $2^{(1+o(1))n(\log n)^2}$.
The lower bound rules out one proposed group-theoretic route to the conjecture that almost all vertex-transitive digraphs are of regular-group type: the route that would use an unweighted $2^{o(n)}$ count of minimally transitive groups. The alternative route through transitive 2-closed groups is not affected.

Reading between the lines

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

One direction the paper leaves open is quantitative: replacing the concentration step by a sharper large-deviation argument would convert the $o(1)$ in the exponent into an explicit constant, possibly settling the still-open infimum problems for the counting exponent.
Because the parameter space for $G(b)$ is the ideal lattice of a truncated polynomial ring, an editorial extension is that the typical minimally transitive group of prime-power degree is governed by the zero-dimensional commutative algebra of $R$, not by the regular-group mechanism; this suggests looking for a classification of the corresponding ideals rather than of the groups themselves.
The paper's own concluding remark invites a weighted version of the proposed route to the vertex-transitive digraph conjecture: instead of counting minimally transitive classes, weight each class by the number of vertex-transitive digraphs it produces. An editorial reading is that this weighted count might still be $2^{o(n)}$ even though the unweighted count is $2^{\Theta(n\log n)}$ along prime po

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: For each fixed prime $p$, as $n$ increases as a power of $p$, the number of minimally transitive permutation groups of degree $n$, counted up to permutational isomorphism (i.e. up to conjugation in $S_n$), is at least $2^{(1/p-o(1))\,n\log n}$. This is the paper's central discovery. It matches the known upper bound $2^{O(n\log n)}$ in the exponent along those degrees, so the exponent is $\Theta(n\

/-- @claim 1 For each fixed prime $p$, as $n$ increases as a power of $p$, the number of minimally transitive permutation groups of degree $n$, counted up to permutational isomorphism (i.e. up to conjugation in $S_n$), is at least $2^{(1/p-o(1))\,n\log n}$. This is the paper's central discovery. It matches the known upper bound $2^{O(n\log n)}$ in the exponent along those degrees, so the exponent is $\Theta(n\ -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

Chris, the short version: this is a real result. Xia and Zheng prove that Pyber's 1993 upper bound 2^{O(n log n)} on minimally transitive subgroups of S_n is tight along powers of every fixed prime, even counting up to permutational isomorphism. That settles the sharpness question on every prime-power degree sequence, rules out exponential upper bounds in those degrees, and closes off the naive Morris-Spiga route via minimally transitive groups for the McKay-Praeger conjecture.

What's new is the lower-bound construction. They take the wreath product F_p^+ wr T with T the regular translation group on V = F_p^m, acting imprimitively on V x F_p. Choosing generators g_i = b_i t_i, the intersection with the base group becomes an ideal in a truncated polynomial ring via the standard identification of F_p[T] with F_p[X]/(X_i^p). The delicate point is Lemma 4.5: every complement of the base group is conjugate to T, giving |Ker Psi| = p^{p^m-1}. I traced that argument; it works. Complements are semiregular, translate to T, and the centralizer of T in the base group is exactly the constant functions. Good.

The ideal-counting in Lemma 4.6 is also sound. The Chebyshev concentration argument that the middle slab of degrees has dimension (1-o(1))p^m is clean, and the final exponent (1/p - o(1)) n log n for n = p^{m+1} follows. The division by the fiber size is legitimate, and I see no circular step. The lower bound is self-contained and does not use CFSG; Pyber's upper bound, included for completeness, uses Aschbacher-Guralnick but is properly attributed to the literature.

Soft spots are minor. The OCR in the supplied copy of Lemma 4.6 is garbled in places, so the displayed exponents need a careful check against the proof text, but the proof gives a consistent accounting. More substantively, Lemma 3.1 states G = while the quoted Theorem 2.5 gives G = . If the quotation is faithful, the upper-bound section needs a small repair, replacing with in Lemma 3.1 and Theorem 3.3. That does not affect the lower bound at all. Also note that the constant 1/p in Theorem 4.7 is not uniform in p, so the paper does not claim a 2^{Omega(n log n)} lower bound on a sequence that includes all n; but the theorem is stated honestly for prime powers.

This paper deserves a serious referee. It is a major step on a long-standing question, and the main construction will be useful beyond this exact statement. I would send it to review and expect the referee to confirm the proof with at most minor revisions.

Referee Report

0 major / 4 minor

Summary. The paper proves that Pyber's upper bound 2^{O(n log n)} on the number of minimally transitive subgroups of S_n is sharp along the sequence n=p^m for every fixed prime p, even when counting only permutational isomorphism classes. The lower bound is obtained by an explicit wreath-product construction: for each parameter vector b in a suitable subspace of R^m, where R=F_p[X_1,...,X_m]/(X_i^p), the group G(b)=<b_i t_i> is minimally transitive on a set of size p^{m+1}, and the Frattini subgroup K(b)=G(b)∩B is realized as an ideal generated by the coordinates of a linear map Psi. A delicate fiber-size computation (Lemma 4.5) shows |Ker Psi|=p^{p^m-1}, and Lemma 4.6 uses this to count distinct ideals K(b) obtained from b in a Chebyshev-concentrated degree window. The paper also presents Pyber's previously unpublished proof of the upper bound, proves that the maximum order of a minimally transitive group of degree p^m is 2^{Theta(n)}, and derives the corollary that labelled vertex-transitive graphs and digraphs have 2^{Theta(n log n)} members. The lower-bound construction is independent of the Classification of Finite Simple Groups, which enters only through the Aschbacher-Guralnick theorem used in the upper-bound section.

Significance. If the results stand, they resolve the sharpness question for Pyber's bound in a strong form, ruling out exponential upper bounds for minimally transitive groups even up to permutational isomorphism. The proof is unusually transparent: the lower bound is a parameter-free construction with no fitted constants, and the delicate fiber-size estimate is proved in detail rather than imported. The paper also gives a complete, self-contained account of Pyber's upper-bound argument, which was previously only stated, and the corollary on vertex-transitive graphs and digraphs determines the correct exponent in both labelled enumeration problems. The large-order byproduct (Theorem 1.5) and the discussion of the McKay-Praeger conjecture are useful additions. I checked the central chain leading to Theorem 4.7, in particular Lemma 4.5, Lemma 4.6, and the ideal-counting argument; I found no load-bearing error.

minor comments (4)

[Section 3, Lemma 3.1] Theorem 2.5 is quoted as giving G=<H,H^g>, while Lemma 3.1 states G=<H,g>. The implication is correct because <H,g> contains both H and g, hence contains H^g, so <H,g>=G; however this step is not stated and should be added so the proof reads as complete.
[Theorem 1.5 and Section 5 proof] The statement of Theorem 1.5 as typeset is inconsistent with its proof. The proof computes |G(b)|=p^{p^m-(p-1)} * p^m = p^{p^m+m-p+1}; for n=p^{m+1} this is p^{n/p + log_p n - p} = 2^{Theta(n)}. The expression printed in Theorem 1.5 appears to be a different, super-exponential quantity that would violate the Sylow p-subgroup bound |S_n|_p = p^{(n-1)/(p-1)}. Please correct the theorem statement to match the proof.
[Corollary 1.7 proof] The lower bound is stated using 'the cycle of length n', whose automorphism group has order 2n and which gives the bound for graphs. For digraphs, the same argument works with a directed cycle, whose automorphism group has order n and gives n!/n distinct labellings; this should be stated explicitly to avoid ambiguity.
[Throughout] There are several typographical artifacts in the title and abstract ('ENUMERA TION', 'MINIMALL Y') and in displayed formulas such as the order in Theorem 1.5. A careful proofreading pass is needed before publication.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity: the lower bound is a self-contained construction, and the upper-bound proof rests on external results.

full rationale

The paper's central lower bound (Theorem 4.7) is a direct construction rather than a fitted prediction. The groups G(b) are built in the wreath product B⋊T, and the parameters d1,d2 and the subspace U are chosen by an analytic concentration argument (Chebyshev), with no parameter fitted to data. The key fiber-size estimate |Ker(Ψ)|=p^{p^m−1} in Lemma 4.5 is proved from group-theoretic facts: every complement of B is semiregular, conjugate to T by an element of B, and C_B(T) is exactly the constant functions. Lemma 4.6 then bounds, for a fixed ideal K(b), the number of parameter vectors producing it, using only degree truncation and the fiber-size bound. No step in the lower-bound chain is defined in terms of the quantity being counted, and no equation reduces to its own input by construction. The upper bound is attributed to Pyber and proved from external results (Aschbacher–Guralnick, Dixon, Lovász's bound, Pyber's solvable-subgroup bound); it is not the present authors' prior work, and it is not used to prove the lower bound. There are no load-bearing self-citations. A minor presentation issue appears in Lemma 3.1, which states G=⟨H,g⟩ while Theorem 2.5 gives G=⟨H,H^g⟩; this affects only the exposition of the upper-bound proof and is not circularity, nor does it bear on the lower-bound construction. Overall, the derivation is self-contained and no circular step is present.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The lower bound introduces no fitted parameters and no new postulated entities. The only external inputs are standard probabilistic and group-theoretic facts plus three cited bounds (Pyber's count of maximal solvable subgroups, Dixon's order bound, and Aschbacher-Guralnick), the last used only for Pyber's upper bound. The width m^{2/3} for the degree band U is a proof choice, not a fitted parameter; any o(m) width growing to infinity would give the same asymptotic.

assumptions (6)

standard math Chebyshev's inequality
Used in Theorem 4.7 to bound the deviation of a sum of m independent uniform {0,...,p-1} variables, giving dim U = (1-o(1))p^m.
standard math Maximal subgroups of finite p-groups are normal
Used in Lemma 2.2 to characterize minimal transitivity of transitive p-groups via the Frattini subgroup.
standard math Frattini subgroup of a finite p-group equals G^p G'
Used in Lemma 4.2 to prove K=Phi(G) for the constructed groups.
domain assumption Pyber's bound: at most 2^{17n} conjugacy classes of maximal solvable subgroups of S_n
Cited external result used in the proof of Theorem 3.3, the upper bound.
domain assumption Dixon's theorem: every solvable subgroup of S_n has order at most 24^{(n-1)/3}
Cited in Theorem 3.3 to bound the number of possible orbit-minimal subgroups inside a maximal solvable subgroup.
domain assumption Aschbacher-Guralnick theorem: every finite group G has a solvable H and g in G with G=langle H,H^g rangle
Used in Lemma 3.1 for the upper-bound proof; depends on the Classification of Finite Simple Groups. Not used for the lower bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Asymptotic enumeration of minimally transitive permutation groups." pith.science (2026). https://pith.science/paper/NASOJEQZ

@misc{pith2026260825792,
  author       = {Pith},
  title        = {Pith review of: Asymptotic enumeration of minimally transitive permutation groups},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/NASOJEQZ}},
  note         = {Machine review of arXiv:2608.25792}
}

abstract

We prove that Pyber's upper bound $2^{O(n\log(n))}$ for the number of minimally transitive subgroups of $S_n$ is best possible along the powers of every fixed prime, even when the groups are counted up to permutational isomorphism. As a byproduct, our construction shows that, along the powers of every fixed prime, the maximum order of a minimally transitive permutation group of degree $n$ is $2^{\Theta(n)}$. For completeness, we also present Pyber's previously unpublished proof of his upper bound. We further deduce that the numbers of labelled vertex-transitive graphs and digraphs of order $n$ are both $2^{\Theta(n\log(n))}$, and discuss the implications of our results for approaches to the McKay--Praeger conjecture.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

16 extracted references · 15 canonical work pages

[1]

Aschbacher and R

M. Aschbacher and R. Guralnick, Solvable generation of groups and Sylow subgroups of the lower central series,J. Algebra, 77 (1982) 189–201

work page 1982
[2]

Babai and V

L. Babai and V. T. S´ os, Sidon sets in groups and induced subgraphs of Cayley graphs,European J. Combin., 6 (1985), no. 2, 101–114

work page 1985
[3]

Bosma, J

W. Bosma, J. Cannon and C. Playoust, The magma algebra system I: The user language,J. Symbolic Comput., 24 (1997), no. 3-4, 235–265

work page 1997
[4]

Dalla Volta and J

F. Dalla Volta and J. Siemons, On solvable minimally transitive permutation groups,Des. Codes Cryptogr., 44 (2007), 143–150

work page 2007
[5]

J. D. Dixon, The Fitting subgroup of a linear solvable group,J. Austral. Math. Soc., 7 (1967) 417–424

work page 1967
[6]

Higman, Enumeratingp-groups

G. Higman, Enumeratingp-groups. I. Inequalities,Proc. London Math. Soc. (3), 10 (1960), 24–30

work page 1960
[7]

Lucchini, Generating minimally transitive groups, inGroups and geometries (Siena, 1996), Trends Math., Birkh¨ auser, Basel, 1998, 149–153

A. Lucchini, Generating minimally transitive groups, inGroups and geometries (Siena, 1996), Trends Math., Birkh¨ auser, Basel, 1998, 149–153

work page 1996
[8]

B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I,J. Aus- tral. Math. Soc. Ser. A, 56 (1994), no. 1, 53–63

work page 1994

Show all 16 references

[9]

Morris and P

J. Morris and P. Spiga, Asymptotic enumeration of Cayley digraphs,Israel J. Math., 242 (2021), no. 1, 401–459

2021
[10]

P. M. Neumann and M. R. Vaughan-Lee, An essay on BFC groups,Proc. London Math. Soc. (3), 35 (1977), no. 2, 213–237

1977
[11]

Pyber, Asymptotic results for permutation groups,Groups and computation (New Brunswick, NJ, 1991), 197–219

L. Pyber, Asymptotic results for permutation groups,Groups and computation (New Brunswick, NJ, 1991), 197–219. DIMACS Ser. Discrete Math. Theoret. Comput. Sci., 11, American Mathematical Society, Providence, RI, 1993

1991
[12]

Pyber, Enumerating finite groups of given order,Ann

L. Pyber, Enumerating finite groups of given order,Ann. Math., 137 (1993) 203–220

1993
[13]

J. A. H. Shepperd and J. Wiegold, Transitive groups and groups with finite derived groups,Math. Z., 81 (1963), 279–285

1963
[14]

C. C. Sims, Enumeratingp-groups,Proc. London Math. Soc. (3), 15 (1965), 151–166

1965
[15]

G. M. Tracey, Generating minimally transitive permutation groups,J. Algebra, 460 (2016), 380–386

2016
[16]

G. M. Tracey, Minimal generation of transitive permutation groups,J. Algebra, 509 (2018), 40–100. 14 B. XIA AND S. ZHENG (Binzhou Xia)School of Mathematics and Statistics, The University of Melbourne, Parkville, VIC 3010, Australia Email address:binzhoux@unimelb.edu.au (Shasha...

2018

Pith tools

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

[1] [1]

Aschbacher and R

M. Aschbacher and R. Guralnick, Solvable generation of groups and Sylow subgroups of the lower central series,J. Algebra, 77 (1982) 189–201

work page 1982

[2] [2]

Babai and V

L. Babai and V. T. S´ os, Sidon sets in groups and induced subgraphs of Cayley graphs,European J. Combin., 6 (1985), no. 2, 101–114

work page 1985

[3] [3]

Bosma, J

W. Bosma, J. Cannon and C. Playoust, The magma algebra system I: The user language,J. Symbolic Comput., 24 (1997), no. 3-4, 235–265

work page 1997

[4] [4]

Dalla Volta and J

F. Dalla Volta and J. Siemons, On solvable minimally transitive permutation groups,Des. Codes Cryptogr., 44 (2007), 143–150

work page 2007

[5] [5]

J. D. Dixon, The Fitting subgroup of a linear solvable group,J. Austral. Math. Soc., 7 (1967) 417–424

work page 1967

[6] [6]

Higman, Enumeratingp-groups

G. Higman, Enumeratingp-groups. I. Inequalities,Proc. London Math. Soc. (3), 10 (1960), 24–30

work page 1960

[7] [7]

Lucchini, Generating minimally transitive groups, inGroups and geometries (Siena, 1996), Trends Math., Birkh¨ auser, Basel, 1998, 149–153

A. Lucchini, Generating minimally transitive groups, inGroups and geometries (Siena, 1996), Trends Math., Birkh¨ auser, Basel, 1998, 149–153

work page 1996

[8] [8]

B. D. McKay and C. E. Praeger, Vertex-transitive graphs which are not Cayley graphs, I,J. Aus- tral. Math. Soc. Ser. A, 56 (1994), no. 1, 53–63

work page 1994