Hamming sandwiches

We describe primitive association schemes X of degree n such that Aut(X) is imprimitive and |Aut(X)|≥exp(n^1/8), contradicting a conjecture of Babai. This and other examples we give are the first known examples of nonschurian primitive coherent configurations (PCC) with more than a quasipolynomial number of automorphisms. Our constructions are “Hamming sandwiches”, association schemes sandwiched between the dth tensor power of the trivial scheme and the d-dimensional Hamming scheme. We study Hamming sandwiches in general, and exhaustively for d≤8. We revise Babai’s conjecture by suggesting that any PCC with more than a quasipolynomial number of automorphisms must be an association scheme sandwiched between a tensor power of a Johnson scheme and the corresponding full Cameron scheme. If true, it follows that any nonschurian PCC has at most expO(n^1/8log n) automorphisms.