Hamming sandwiches (Q6057495)

It is described primitive association schemes \(\mathfrak X\) of degree \(n\) such that \( {\text{ Aut}}(\mathfrak X)\) is imprimitive and \(\vert {\text{ Aut}}(\mathfrak X)\vert \ge \exp(n^{1/8})\), contradicting a conjecture of \textit{L. Babai} [in: Proceedings of the international congress of mathematicians 2018, ICM 2018, Rio de Janeiro, Brazil, August 1--9, 2018. Volume IV. Invited lectures. Hackensack, NJ: World Scientific; Rio de Janeiro: Sociedade Brasileira de Matemática (SBM). 3319--3336 (2018; Zbl 1490.68116)]. This and other examples represented in this work are the first known examples of non-schurian primitive coherent configurations (in short \(PCC\)) with more than a quasi-polynomial number of automorphisms. These constructions are ``Hamming sandwiches'', association schemes sandwiched between the \(d\)-th tensor power of the \(d\)-dimensional Hamming scheme. It is studied Hamming sandwiches in general and exhaustively for \(d\le 8\). It is revised Babai's conjecture by suggesting that any \(PCC\) with more than a quasi-polynomial number of automorphisms must be an association scheme sandwiched between a tensor power of a Johnson scheme and the corresponding full Cameron scheme. If that is true, it follows that any non-schurian \(PCC\) has at most \(\exp O(n^{1/8}\log n)\) automorphisms.