The Proportion of Fixed-Point-Free Elements of a Transitive Permutation Group

In 1990 Hendrik W. Lenstra, Jr. asked the following question: if G is a transitive permutation group of degree n and A is the set of elements of G that move every letter, then can one find a lower bound (in terms of n) for f(G) = |A|/|G|? Shortly thereafter, Arjeh Cohen showed that 1/n is such a bound. Lenstra’s problem arose from his work on the number field sieve. A simple example of how f(G) arises in number theory is the following: if h is an irreducible polynomial over the integers, consider the proportion: |{primes ≤ x | h has no zeroes mod p}| / |{primes ≤ x}| As x → ∞, this ratio approaches f(G), where G is the Galois group of h considered as a permutation group on its roots. Our results in this paper include explicit calculations of f(G) for groups G in several families. We also obtain results useful for computing f(G) when G is a wreath product or a direct product of permutation groups. Using this we show that {f(G) | G is transitive} is dense in [0, 1]. The corresponding conclusion is true if we restrict G to primitive groups