pith. sign in

arxiv: 2605.16032 · v1 · pith:MRYUBYLEnew · submitted 2026-05-15 · 🧮 math.GR

Greedy bases and relational complexity of diagonal type groups

Hong Yi Huang , Colva M. Roney-Dougal This is my paper

Pith reviewed 2026-05-19 18:58 UTC · model grok-4.3

classification 🧮 math.GR
keywords primitive permutation groupsdiagonal typebase sizegreedy algorithmrelational complexityCameron conjecturepermutation representations
0
0 comments X

The pith

Primitive groups of diagonal type satisfy Cameron's conjecture on greedy base sizes and have relational complexity at least 4 that is unbounded.

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

This paper studies primitive permutation groups whose socle is a direct power of a simple group acting diagonally. It determines the exact size of every base that the greedy algorithm returns for such groups and shows that these sizes are bounded by a fixed multiple of the minimal base size b(G). This confirms Cameron's 1999 conjecture in the diagonal case. The paper also proves that the relational complexity of every such group is at least 4, that the bound 4 is achieved by infinitely many examples, and that relational complexity takes arbitrarily large values inside this family.

Core claim

When G is a primitive permutation group of diagonal type the greedy algorithm produces a base whose size is at most c b(G) for an absolute constant c, thereby proving Cameron's conjecture for these groups; moreover RC(G) is always at least 4, equality holds for infinitely many such G, and RC(G) is unbounded within the class.

What carries the argument

The socle T^k acting on the cosets of a diagonal subgroup, with greedy choices tracked by determining the orbits of G on successive product spaces Omega^k.

If this is right

  • Cameron's conjecture holds for the entire class of primitive diagonal type groups.
  • Every primitive diagonal type group has relational complexity at least 4.
  • There are infinitely many primitive diagonal type groups with relational complexity exactly 4.
  • Relational complexity is unbounded among primitive diagonal type groups.

Where Pith is reading between the lines

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

  • Similar orbit-tracking techniques might extend the proof of Cameron's conjecture to other families of primitive groups.
  • Diagonal type groups supply an infinite source of examples with successively larger relational complexity, which could help identify all primitive groups of relational complexity 3.

Load-bearing premise

The known structural description of primitive diagonal type groups and the orbit calculations on product spaces used to track the greedy choices are accurate.

What would settle it

A concrete primitive diagonal type group in which the greedy algorithm returns a base larger than the predicted bound, or one whose relational complexity equals 3.

read the original abstract

A base for a subgroup $G$ of $\mathrm{Sym}(\Omega)$ is a sequence of elements of $\Omega$ with trivial pointwise stabiliser. The size of the smallest base for $G$ is denoted $b(G)$. There is a natural greedy algorithm to compute a base for $G$, and it was conjectured by Cameron in 1999 that there exists an absolute constant $c$ such that if $G$ is primitive then any base returned by this algorithm has size at most $cb(G)$. In this paper we determine the size of every base returned by the greedy algorithm when $G$ is a primitive group of diagonal type, and hence prove Cameron's conjecture for these groups. The relational complexity $\mathrm{RC}(G)$ of $G$ is a measure of the way in which the orbits of $G$ on $\Omega^k$ for various $k$ determine the action of $G$ on $\Omega$. Very few precise values of relational complexity are known, and in particular it is not known which primitive groups have relational complexity $3$. In this paper we prove that if $G$ is primitive of diagonal type then $\mathrm{RC}(G) \geqslant 4$, that this lower bound is attained by infinitely many such $G$, and that the relational complexity of the groups of diagonal type is unbounded.

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 / 3 minor

Summary. The paper determines the size of every base returned by the greedy algorithm for primitive groups of diagonal type, thereby proving Cameron's 1999 conjecture for this class. It further proves that RC(G) ≥ 4 for all such G, that the bound is attained by infinitely many examples, and that relational complexity is unbounded within the family of diagonal-type groups.

Significance. If the explicit orbit computations on successive product spaces hold, the work gives a complete, case-by-case resolution of the greedy-base question for the entire diagonal-type class using the standard O'Nan-Scott structural description (socle T^k acting on cosets of a diagonal subgroup). The RC results supply the first infinite family of primitive groups known to have RC exactly 4 and demonstrate unboundedness, both of which are valuable given the scarcity of precise relational-complexity values in the literature.

minor comments (3)
  1. [Abstract] Abstract: the statement that the greedy bases are 'determined' would be strengthened by a brief indication of the range of possible sizes obtained (e.g., whether they are always equal to b(G) or sometimes strictly larger).
  2. [Introduction] The reliance on the known classification of diagonal-type groups is stated clearly, but a short reminder of the precise action (T^k on cosets of D) in the first section would aid readers who are not specialists in the O'Nan-Scott theorem.
  3. [Section 3] Notation for the product-space orbits used to track the greedy choices should be introduced uniformly before the first case division; occasional re-use of symbols for different orbit types risks confusion.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our work on greedy bases for diagonal-type groups and the relational complexity results. The report recommends minor revision, but no specific major comments appear under the MAJOR COMMENTS section. We therefore have no individual points to rebut or revise at this stage and believe the manuscript is ready for publication.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper determines greedy base sizes and relational complexity bounds for primitive diagonal-type groups via the standard O'Nan-Scott structural description (socle T^k on cosets of a diagonal subgroup) together with explicit orbit computations on successive product spaces. These are direct, first-principles calculations of stabilizers and orbits; no quantities are defined in terms of the target results, no parameters are fitted to data and then renamed as predictions, and no load-bearing steps reduce to self-citations by the same authors. The cited structural facts are external theorems, not internal to this work, and the orbit-tracking arguments are independently verifiable from the group action.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper is a pure mathematical proof relying on the established classification of finite primitive permutation groups; no numerical parameters are fitted and no new entities are postulated.

axioms (1)
  • domain assumption The O'Nan-Scott theorem classifies primitive permutation groups into five types, one of which is diagonal type with socle T^k acting diagonally.
    The entire analysis of greedy bases and relational complexity is carried out inside this structural framework.

pith-pipeline@v0.9.0 · 5776 in / 1407 out tokens · 36442 ms · 2026-05-19T18:58:50.233697+00:00 · methodology

discussion (0)

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

Reference graph

Works this paper leans on

31 extracted references · 31 canonical work pages

  1. [1]

    Anagnostopoulou-Merkouri and T.C

    M. Anagnostopoulou-Merkouri and T.C. Burness,On the regularity number of a finite group and other base-related invariants, J. Lond. Math. Soc.110(2024), Paper No. e70035, 65 pp

    work page 2024

  2. [2]

    Blaha,Minimum bases for permutation groups: the greedy approximation, J

    K.D. Blaha,Minimum bases for permutation groups: the greedy approximation, J. Algorithms13 (1992), no. 2, 297–306

    work page 1992

  3. [3]

    Bray, D.F

    J.N. Bray, D.F. Holt and C.M. Roney-Dougal,The maximal subgroups of the low-dimensional finite classical groups, Lond. Math. Soc. Lecture Note Ser., vol. 407, Cambridge Univ. Press, Cambridge, 2013

    work page 2013

  4. [4]

    Bosma, J

    W. Bosma, J. Cannon and C. Playoust,TheMagmaalgebra system I: The user language, J. Symb. Comput.24(1997), 235–265

    work page 1997

  5. [5]

    Brenner, C

    S. Brenner, C. del Valle and C.M. Roney-Dougal,Irredundant bases for soluble groups, Bull. Lond. Math. Soc.57(2025), 3013–3023

    work page 2025

  6. [6]

    Burness,Fixed point ratios in actions in finite classical groups

    T.C. Burness,Fixed point ratios in actions in finite classical groups. II, J. Algebra309(2007), 80–138

    work page 2007

  7. [7]

    Burness and M

    T.C. Burness and M. Giudici,Classical groups, derangements and primes, Australian Mathematical Society Lecture Series, vol. 25, Cambridge University Press, Cambridge, 2016

    work page 2016

  8. [8]

    Burness and H.Y

    T.C. Burness and H.Y. Huang,On the intersections of Sylow subgroups in almost simple groups, J. Algebra690(2026), 596-631

    work page 2026

  9. [9]

    Burness and A.R

    T.C. Burness and A.R. Thomas,The classification of extremely primitive groups, Int. Math. Res. Not. IMRN no. 13 (2022), 10148–10248

    work page 2022

  10. [10]

    Cameron,Permutation groups, London Mathematical Society Student Texts, 45, Cambridge Univ

    P.J. Cameron,Permutation groups, London Mathematical Society Student Texts, 45, Cambridge Univ. Press, Cambridge, 1999

    work page 1999

  11. [11]

    G. Cherlin. Sporadic homogeneous structures. InThe Gelfand Mathematical Seminars, 1996–1999. Boston, MA: Birkh¨ auser, 2000. 22 HONG YI HUANG AND COLVA M. RONEY-DOUGAL

    work page 1996

  12. [12]

    De Franceschi, M.W

    G. De Franceschi, M.W. Liebeck and E.A. O’Brien,Conjugacy in finite classical groups, Springer Monographs in Mathematics, Springer, Cham, 2025

    work page 2025

  13. [13]

    del Valle,Greedy base sizes for sporadic simple groups, J

    C. del Valle,Greedy base sizes for sporadic simple groups, J. Group Theory28(2025), 1079–1094

    work page 2025

  14. [14]

    del Valle and C.M

    C. del Valle and C.M. Roney-Dougal,On Cameron’s Greedy Conjecture, submitted (2025), arXiv:2503.23964

    work page arXiv 2025

  15. [15]

    Dixon and B.C

    J.D. Dixon and B.C. Mortimer,Permutation groups, Graduate Texts in Mathematics, 163, Springer, New York, 1996

    work page 1996

  16. [16]

    Fawcett,The base size of a primitive diagonal group, J

    J.B. Fawcett,The base size of a primitive diagonal group, J. Algebra375(2013), 302–321

    work page 2013

  17. [17]

    Freedman, H.Y

    S.D. Freedman, H.Y. Huang, M. Lee and K. Rekv´ enyi,On the generalised Saxl graphs of permutation groups, Algebr. Comb., to appear

    work page

  18. [18]

    Version 4.15.1; 2025

    The GAP Group.GAP – Groups, Algorithms, and Programming. Version 4.15.1; 2025. (https://www.gap-system.org)

    work page 2025

  19. [19]

    N. Gill, B. Lod` a and P. Spiga,On the height and relational complexity of a finite permutation group, Nagoya Math. J.246(2022), 372–411

    work page 2022

  20. [20]

    Gill, M.W

    N. Gill, M.W. Liebeck and P. Spiga,Cherlin’s conjecture for finite primitive binary permutation groups, Lecture Notes in Math., 2302, Springer, Cham, 2022

    work page 2022

  21. [21]

    Gorenstein, R

    D. Gorenstein, R. Lyons and R. Solomon,The Classification of the Finite Simple Groups. Number 3, Mathematical Surveys and Monographs, vol. 40. Amer. Math. Soc., Providence, RI., 1998

    work page 1998

  22. [22]

    Huang,Base sizes of primitive groups of diagonal type, Forum Math

    H.Y. Huang,Base sizes of primitive groups of diagonal type, Forum Math. Sigma12(2024), Paper No. e2, 43 pp

    work page 2024

  23. [23]

    James,Two point stabilisers of partition actions of linear groups, J

    J.P. James,Two point stabilisers of partition actions of linear groups, J. Algebra297(2006), 453–469

    work page 2006

  24. [24]

    Kelsey and C.M

    V. Kelsey and C.M. Roney-Dougal,On relational complexity and base size of finite primitive groups, Pacific J. Math.318(2022), 89–108

    work page 2022

  25. [25]

    Kleidman, The maximal subgroups of the finite 8-dimensional orthogonal groups PΩ + 8 (q) and of their automorphism groups, J

    P.B. Kleidman, The maximal subgroups of the finite 8-dimensional orthogonal groups PΩ + 8 (q) and of their automorphism groups, J. Algebra110(1987), no. 1, 173–242

    work page 1987

  26. [26]

    Kleidman and M.W

    P.B. Kleidman and M.W. Liebeck,The Subgroup Structure of the Finite Classical Groups, London Math. Soc. Lecture Note Series, vol. 129, Cambridge University Press, 1990

    work page 1990

  27. [27]

    Knuth,The art of computer programming

    D.E. Knuth,The art of computer programming. Vol. 1: Fundamental algorithms, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1969

    work page 1969

  28. [28]

    Lachlan, Homogeneous structures, InProc

    A.H. Lachlan, Homogeneous structures, InProc. Int. Congr. Math., Berkeley 1986, Vol. 1, 314–321, Amer. Math. Soc., Providence, RI, 1987

    work page 1986

  29. [29]

    Leemans and M.W

    D. Leemans and M.W. Liebeck,Chiral polyhedra and finite simple groups, Bull. Lond. Math. Soc.49 (2017), 581–592

    work page 2017

  30. [30]

    Lucchini, M

    A. Lucchini, M. Morigi and M. Moscatiello,Primitive permutation IBIS groups, J. Combin. Theory Ser. A184(2021), Paper No. 105516, 17 pp

    work page 2021

  31. [31]

    Sims,Computation with permutation groups, Proc

    C.C. Sims,Computation with permutation groups, Proc. Second Sympos. on Symbolic and Algebraic Manipulation (Los Angeles, 1971), ACM, New York, 1971, pp. 23–28. H.Y. Huang, Department of Mathematics, Southern University of Science and Technol- ogy, Shenzhen 518055, Guangdong, P. R. China Current address: Alfr´ ed R´ enyi Institute of Mathematics, Re´ altan...

    work page 1971