If \(G\) is a transitive group acting on a set \(\Omega\), then a base for \(G\) is a set \(\Delta\) of points in \(\Omega\) such that the pointwise stabilizer of \(\Delta\) is \(1\). The main theorem of this paper is the following. Suppose that \(G=A_n\) or \(S_n\) (\(n\geq 11\)) acts primitively on a set \(\Omega\) and that a point stabilizer \(H\) of this action is a primitive subgroup of \(S_n\) (not containing \(A_n\)). Then \(G\) has a base of size \(2\) except in the cases \((G,H)=(A_{11},M_{11})\) or \((A_{12},M_{12})\); in the latter cases \(G\) has a base of size \(3\). The twelve cases where the base size is \(>2\) and \(n<11\) are also listed.
This theorem had been conjectured by P. J. Cameron and W. M. Kantor [Comb. Probab. Comput. 2, No. 3, 257-262 (1993; Zbl 0823.20002)] who showed that under the hypothesis of the theorem the probability that a random pair of points in \(\Omega\) forms a base for \(G\) tends to \(1\) as \(n\to\infty\).
One simple criterion which the authors prove is perhaps of independent interest. Let \(G\) be a primitive permutation group on a finite set \(\Omega\) with point stabilizer \(H\), and let \(x_1,x_2,\dots,x_k\) be representatives of the distinct \(G\)-classes of elements of prime order in \(H\). If \(\sum_i|x_i^G\cap H|^2|C_G(x_i)|<|G|\) then \(G\) has a base of size \(2\).