Greedy bases and relational complexity of diagonal type groups

Hong Yi Huang, Colva M. Roney-Dougal · 2026

Read Greedy bases and relational complexity of diagonal type groups by Hong Yi Huang, Colva M. Roney-Dougal (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-16032.txt.

Introduction

Huang and Roney-Dougal settle two questions about primitive groups of diagonal type. They determine the size of every base returned by the greedy algorithm, proving Cameron's 1999 conjecture for these groups. They also prove the relational complexity of such groups is at least four, that infinitely many attain four, and that it is unbounded across the family. Few exact relational complexity values were known before.

Catalog record

CREATORHong Yi Huang, Colva M. Roney-Dougal
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83381
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2605.16032

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Greedy bases and relational complexity of diagonal type groups Hong Yi Huang, Colva M. Roney-Dougal Abstract . A base for a subgroup G G of Sym ⁡ ( Ω ) \mathrm{Sym}(\Omega) is a sequence of elements of Ω \Omega with trivial pointwise stabiliser. The size of the smallest base for G G is denoted b ⁡ ( G ) b(G) . There is a natural greedy algorithm to compute a base for G G , and it was conjectured by Cameron in 1999 that there exists an absolute constant c c such that if G G is primitive then any base returned by this algorithm has size at most c ​ b ​ ( G ) cb(G) . In this paper we determine the size of every base returned by the greedy algorithm when G G is a primitive group of diagonal type, and hence prove Cameron’s conjecture for these groups. The relational complexity RC ⁡ ( G ) \mathrm{RC}(G) of G G is a measure of the way in which the orbits of G G on Ω k \Omega^{k} for various k k determine the action of G 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 3 . In this paper we prove that if G G is primitive of diagonal type then RC ⁡ ( G ) ⩾ 4 \mathrm{RC}(G)\geqslant 4 , that this lower bound is attained by infinitely many such G G , and that the relational complexity of the groups of diagonal type is unbounded. 2020 Mathematics Subject Classification 20B15 (primary), 20P05, 20E45 1. Introduction A base for a subgroup G of \mathrm{Sym}(\Omega) is a sequence of elements of \Omega with trivial pointwise stabiliser in G . For finite G the base size b(G) is the minimal size of a base for G . This classical invariant of permutation groups has been studied since the 19th century, and gained particular importance in computational group theory [ 31 ] , as the running time of many permutation group algorithms is a function of the size of a known base. A base (\beta_{1},\ldots,\beta_{k}) is irredundant if the pointwise stabiliser in G of \beta_{1},\ldots,\beta_{i+1} is a proper subgroup of the pointwise stabiliser of \beta_{1},\ldots,\beta_{i} , for all i\in\{1,\ldots,k-1\} . The size of the largest irredundant base is denoted by I(G) : it is straightforward to see that I(G)\leqslant b(G)\log n (our logarithms are to the base 2 unless otherwise specified). In general, b(G) can be as large as |\Omega|-1 , but much smaller bounds are known for most types of primitive groups. The problem of determining b(G) has been considered for all five O’Nan–Scott classes. For example, the precise base sizes of primitive groups of diagonal type are determined by the first author [ 22 ] (see Theorem 2.1 below), and so far this is the only O’Nan–Scott family for which the base sizes are known in all cases. There are no efficient algorithms for computing b(G) , or for constructing a base of minimal size. Indeed, Blaha [ 2 ] proves that computing a base of size b(G) is NP-hard. To find a base of “relatively small” size, there is a natural greedy algorithm, first systematically studied by Blaha. Let \beta_{1} be any point in any longest orbit of G . Now define a sequence (\beta_{i})_{i\geqslant 1} of points of \Omega , terminating as soon as a base is reached, where \beta_{m} lies in a longest orbit of the pointwise stabiliser G_{\beta_{1},\ldots,\beta_{m-1}} . The sequence (\beta_{i})_{i\geqslant 1} is called a greedy base for G , and the greedy base size \mathcal{G}(G) is defined to be the largest size of a greedy base for G . Blaha [ 2 ] shows that \mathcal{G}(G) is “small” in the sense that there is an absolute constant d such that (1) \mathcal{G}(G)\leqslant db(G)\log\log|\Omega| for every permutation group G\leqslant\mathrm{Sym}(\Omega) . And in the same paper, he proves that for a fixed integer k and a sufficiently large integer n , there exists a permutation group G of degree n such that b(G)=k and \mathcal{G}(G)\geqslant\frac{1}{5}k\log\log n , so the bound ( 1 ) is best possible. For primitive groups, Cameron conjectured in 1999 [ 10 ] that a substantially tighter bound than ( 1 ) holds. Conjecture (Cameron’s Greedy Conjecture) . There is an absolute constant c such that \mathcal{G}(G)\leqslant cb(G) for every finite primitive group G . Since every greedy base is irredundant, \mathcal{G}(G)\leqslant I(G) . Building on [ 19 ] , Kelsey and the second author showed in [ 24 ] that if G is primitive and not large base then I(G)\leqslant 5\log n , which automatically bounds \mathcal{G}(G) for these groups, but does not directly address Cameron’s Greedy Conjecture. The conjecture has been proved for many almost simple primitive groups [ 13 , 14 ] , and been proved (with c=1 ) for groups of odd order [ 5 ] . In this paper, we focus on primitive groups of diagonal type. In this setting, G\leqslant\mathrm{Sym}(\Omega) has socle T^{k} , where T is a non-abelian simple group and k\geqslant 2 is an integer. Here |\Omega|=|T|^{k-1} and T^{k}\trianglelefteqslant G\leqslant T^{k}.(\mathrm{Out}(T)\times\mathrm{S}_{k}). The subgroup P\leqslant\mathrm{S}_{k} induced by the action of G by conjugation on the set of factors of T^{k} is called the top group of G . We define Q=\{(1,\dots,1)\sigma:\sigma\in\mathrm{S}_{k}\}\cap G=\mathrm{S}_{k}\cap G. Note that Q is naturally isomorphic to a subgroup of the top group P . For groups of diagonal type, Gill, Lodá and Spiga prove in [ 19 ] that I(G)\leqslant\log|\Omega|+1 , giving the same upper bound on \mathcal{G}(G) . Our first main theorem is the following, which gives the first O’Nan-Scott family for which \mathcal{G}(G) is known in all cases. Theorem 1 . Let G be a primitive group of diagonal type with socle T^{k} and top group P , and let \ell=\lceil\log_{|T|}k\rceil . (i) If k=2 , then \mathcal{G}(G)\in\{3,4\} , with \mathcal{G}(G)=4 if and only if T\in\{\mathrm{A}_{5},\mathrm{A}_{6}\} and G=T^{2}.(\mathrm{Out}(T)\times\mathrm{S}_{2}) . (ii) If P\notin\{\mathrm{A}_{k},\mathrm{S}_{k}\} , then \mathcal{G}(G)=2 . (iii) For k\geqslant 3 , if P\in\{\mathrm{A}_{k},\mathrm{S}_{k}\} then \mathcal{G}(G)\in\{\ell+1,\ell+2\} . Moreover, \mathcal{G}(G)=\ell+2 if and only if either k=|T|^{\ell} , or k\in\{|T|^{\ell}-2,|T|^{\ell}-1\} and Q=\mathrm{A}_{k} . In addition, every greedy base for G has size \mathcal{G}(G) . Combining Theorem 1 with the values of b(G) found in [ 22 ] (see Theorem 2.1 ), we get the following corollary. Corollary 1 . Let G be a primitive group of diagonal type with socle T^{k} and top group P , and let \ell=\lceil\log_{|T|}k\rceil . Then \mathcal{G}(G)\in\{b(G),b(G)+1\} , with \mathcal{G}(G)=b(G)+1 if and only if P\in\{\mathrm{A}_{k},\mathrm{S}_{k}\} and one of the following holds: (a) k=|T|^{2}-2 , Q=\mathrm{S}_{k} , and either T\notin\{\mathrm{A}_{5},\mathrm{A}_{6}\} or G\neq T^{k}.(\mathrm{Out}(T)\times\mathrm{S}_{k}) : here \mathcal{G}(G)=4 ; (b) k=|T|^{\ell}-2 with \ell\geqslant 3 and Q=\mathrm{S}_{k} : here \mathcal{G}(G)=\ell+2 ; (c) k=|T|^{\ell} with \ell\geqslant 2 and Q=\mathrm{A}_{k} : here \mathcal{G}(G)=\ell+2 . In particular, for all b\geqslant 3 , there exist infinitely many primitive groups G of diagonal type such that b(G)=b<\mathcal{G}(G) . If a transitive group G has base size 2 , then in particular G has a regular suborbit, and so \mathcal{G}(G)=2 as well. Combining this observation with Corollary 1 proves Cameron’s Greedy Conjecture for primitive groups

Read the complete text