On the Order of Uniprimitive Permutation Groups

One of the central problems of 19th century group theory was the estimation of the order of a primitive permutation group G of degree n, where G X An. We prove I G I < exp (4V'/ n log2 n) for the case when G is not doubly transitive. This result is best possible apart from an O(log n) factor in the exponent. The best result previously known was I G I < el (H. Wielandt). A similar estimate for the doubly transitive case follows in a subsequent paper. For rank 3 groups with subdegree p < n/2 we obtain I GI < exp (4(n/p) log2 n). In the proof we develop some new combinatorial properties of coherent configurations. The results also have relevance to theoretical estimates on the computational complexity of graph isomorphism testing.