BASE SIZES AND REGULAR ORBITS FOR COPRIME AFFINE PERMUTATION GROUPS

Abstract

Let G be a permutation group on a finite set Ω. A sequence B=(ω₁, …, ω_b) of points in Ω is called a base if its pointwise stabilizer in G is the identity. Bases are of fundamental importance in computational algorithms for permutation groups. For both practical and theoretical reasons, one is interested in the minimal base size for (G, Ω), For a nonredundant base B, the elementary inequality 2^{[mid ]B[mid ]}[les ][mid ]G[mid ][les ][mid ]Ω[mid ]^{[mid ]B[mid ]} holds; in particular, [mid ]B[mid ][ges ]log[mid ]G[mid ]/log[mid ]Ω[mid ]. In the case when G is primitive on Ω, Pyber [8, p. 207] has conjectured that the minimal base size is less than Clog[mid ]G[mid ]/log[mid ]Ω[mid ] for some (large) universal constant C.

It appears that the hardest case of Pyber's conjecture is that of primitive affine groups. Let H=GV be a primitive affine group; here the point stabilizer G acts faithfully and irreducibly on the elementary abelian regular normal subgroup V of H, and we may assume that Ω=V. For positive integers m, let mV denote the direct sum of m copies of V. If (v₁, …, v_m)∈mV belongs to a regular G-orbit, then (0, v₁, …, v_m) is a base for the primitive affine group H. Conversely, a base (ω₁, …, ω_b) for H which contains 0∈V=Ω gives rise to a regular G-orbit on (b−1) V. Thus Pyber's conjecture for affine groups can be viewed as a regular orbit problem for G-modules, and it is therefore a special case of an important problem in group representation theory. For a related result on regular orbits for quasisimple groups, see [4, Theorem 6].