\documentclass[ALCO]{cedram} \newcommand{\Ld}{|\!\!|} \newcommand{\Rd}{|\!\!|} \newcommand{\dsl}{/\!\!/} \newcommand{\cal }{\mathcal } \newcommand{\etha}{\alpha} \newcommand{\embedding}{\hookrightarrow} \newcommand{\semidirect}{\rtimes} \newcommand{\sr}{S-ring } \newcommand{\pp}{\mbox {\bf P}\,} \newcommand{\pr}{\mbox {\bf Proof.\ }} \newcommand{\aaa}{\mbox {\cal A}} \newcommand{\pset}{\mbox {\{p_1,\dots,p_m\}}} \newcommand{\zn}{\mbox {\bf Z}_n} \newcommand{\pg}{permutation group } \newcommand{\pgs}{permutation groups } \newcommand{\srg}[3]{${\cal #1}=<{\underline #2}_0,\dots,{\underline #2}_#3>$} \newcommand{\isom}{\cong} \newcommand {\sth}{ such that } \newcommand {\imp}{ imprimitivity system } \newcommand {\tram}{ $V(C_n,G_1)$ } \newcommand {\pair}[1] {#1_1 #1_2^{-1}} \newcommand {\cnp}{ C_{n/p} } \newcommand {\normal}{\trianglelefteq} \newcommand {\congruence} {\equiv} \newcommand {\wreath}{\wr} \newcommand {\longline}{\left|\right.} \newcommand {\Sup}[1]{{\sf Sup}({#1})} \newcommand {\Aut}[1]{{\sf Aut}({#1})} \newcommand {\Out}[1]{{\sf Out}({#1})} \newcommand {\Inn}[1]{{\sf Inn}({#1})} \newcommand {\New}[1]{{\sl #1}} \newcommand {\Sym}[1]{{\sf Sym }(#1)} \newcommand {\encodes}{\ encodes\ } \newcommand {\tran}[1]{{#1}^*} \newcommand {\twomin}{({\sf Sup}_2(H_R))^{min}} \newcommand{\Log}[2]{{\mbox{\boldmath$\eta$\unboldmath}}_{#1}(#2)} \newcommand {\tranjugate}{tranjugate\ } \newcommand {\cclosed}{ complete \ } \newcommand{\fp}{{\Zset}_p} \newcommand{\HH}{{\sf H}} \newcommand{\GG}{{\sf G}} \newcommand{\m}[1]{\overline{#1}} \newcommand{\Ind}{[\m{0},\m{p-1}]} \newcommand{\cay}[2]{{\sf Cay}(#1,#2)} \newcommand{\laa}{\langle\!\langle} \newcommand{\raa}{\rangle\!\rangle} \newcommand{\lla}{\langle\!\langle} \newcommand{\Q}{{\mathbb Q}} \newcommand{\Z}{{\mathbb Z}} \newcommand{\A}{{\cal A}} \newcommand{\und}[1]{\underline{#1}} \newcommand{\aut}[1]{{\sf Aut}(#1)} \newcommand{\bsets}[1]{\Bsets{#1}} \newcommand{\myplus}{\biguplus} \newcommand{\Stab}{{\sf Stab}} \newcommand{\spn}{{\sf Span}} \newcommand{\sk}[1]{{[\!\![ #1 ]\!\!]}} \newcommand{\mymid}{\,\,\vline\,\,} \newcommand{\sfM}{{\sf M}} \newcommand{\cM}{{\mathcal M}} \newcommand{\F}{{\mathbb F}} \newcommand{\cR}{{\mathcal R}} \newcommand{\cP}{{\mathcal P}} \newcommand{\cF}{{\mathcal F}} \newcommand{\cL}{{\mathcal L}} \newcommand{\cT}{{\mathcal T}} \newcommand{\cB}{{\mathcal B}} \newcommand{\cC}{{\mathcal C}} \newcommand{\cD}{{\mathcal D}} \newcommand{\cH}{{\mathcal H}} \newcommand{\cJ}{{\mathcal J}} \newcommand{\cI}{{\mathcal I}} \newcommand{\cV}{{\mathcal V}} \newcommand{\e}{{\sf e}} \newcommand{\trace}{{\rm trace}} \newcommand{\sym}[1]{{\sf Sym }(#1)} \newcommand{\cel}{{\rm Cel}} \newcommand{\lm}{\lambda} \newcommand{\SP}{{\rm Sp}} \newcommand{\ot}[1]{{\bf O}^\theta(#1)} \newcommand{\wh}[1]{\widehat{#1}} \newcommand{\btwn}[2]{{}_{#1}\!S_{#2}} \newcommand{\haho}{half-homogeneous} \newcommand{\coco}{coherent configuration} \newcommand{\cocos}{coherent configurations} \newcommand{\irr}{{\rm Irr}} \newcommand{\rk}{{\rm rk}} \newcommand{\cS}{{\mathcal S}} \newcommand{\ea}{\Z_2^3} \newcommand{\sg}[1]{\langle{#1}\rangle} \newcommand{\ovr}[1]{\overline{#1}} \newcommand{\tr}{T} \newcommand{\vpphi }{\varphi} \newcommand{\Orb}{\mathsf{Orb}} \newcommand{\cyc}{\ cyclotomic} \newcommand{\N}{{\sf N}} \newcommand{\cA}{{\mathcal A}} \newcommand{\Ker}{{\rm Ker}} \newcommand{\End}{{\rm End}} \newcommand{\Fr}{{\rm Fr}} \newcommand{\fq}{{\mathbb F}_q} \newcommand{\sig}{\sigma } \newcommand{\veps}{\varepsilon} \newcommand{\cd}{{\rm c.d.}} \newcommand{\mtrx}[4]{\left(\begin{array}{rr} #1 & #2 \\ #3 & #4\end{array}\right)} \newcommand{\irreps}{ irreducible representations } \newcommand{\C}{{\mathbb C}} \newcommand{\core}{{\sf core}} \def\f{\EuScript} \newcommand{\comment}[1]{} \newcommand{\dv}{\scalebox{.7}{\%}} \newcommand{\rad}{\mathsf{Rad}} \newcommand{\lcm}{\mathsf{l.c.m.}} \newcommand{\G}{\mathbf{G}} \newcommand{\ac}{almost\ cyclic} \newcommand{\orb}{\mathsf{Orb}} \newcommand{\is}{ imprimitivity\ system} \newcommand{\inn}{\mathsf{Inn}} \newcommand{\fix}{\mathsf{Fix}} \newcommand{\fS}{\mathfrak S} \newcommand{\lt}{\lambda} \newcommand{\wt}{\operatorname{wt}} \newcommand{\supp}{\mathrm{supp}} \def\X{\mathfrak{X}} \def\Y{\mathfrak{Y}} \def\T{\mathcal{T}} \renewcommand{\subset}{\subseteq} \renewcommand{\supset}{\supseteq} \begin{DefTralics} \newcommand{\cT}{{\mathcal T}} \newcommand{\cH}{{\mathcal H}} \end{DefTralics} \begin{document} \equalenv{cor}{coro} \title{Fusions of tensor powers of Johnson schemes} \author[\initial{S.} Eberhard]{\firstname{Sean} \lastname{Eberhard}} \address{Centre for Mathematical Sciences\\ Wilberforce Road\\ Cambridge CB3~0WB (U.K.)} \email{eberhard@maths.cam.ac.uk} \author[\initial{M.} Muzychuk]{\firstname{Mikhail} \lastname{Muzychuk}} \address{Department of Mathematics\\ Ben Gurion University\\ P.O.B. 653, Beer Sheva 8410501 (Israel)} \email{muzychuk@bgu.ac.il} \thanks{SE has received funding from the European Research Council (ERC), via the EU's Horizon 2020 grant No.~803711. MM was supported by the Israeli Ministry of Absorption} %under the European Union's Horizon 2020 research and innovation programme (grant No.~803711). MM was supported by the Israeli Ministry of Absorption.} \keywords{association schemes, permutation groups} \subjclass{05E30} \begin{abstract} This paper is a follow-up to \cite{E}, in which the first author studied primitive association schemes lying between a tensor power $\cT_m^d$ of the trivial association scheme and the Hamming scheme $\cH(d,m)$. A question which arose naturally in that study was whether all primitive fusions of $\cT_m^d$ lie between $\cT_{m^e}^{d/e}$ and $\cH(d/e, m^e)$ for some $e \mid d$. This note answers this question positively provided that $m$ is large enough. We similarly classify primitive fusions of the $d$th tensor power of a Johnson scheme on $\binom{m}{k}$ points when $m$ is large enough in terms of $k$ and~$d$. \end{abstract} \maketitle \section{Introduction} Association schemes are objects of central importance in algebraic combinatorics. For an introduction to association schemes, the reader could refer to any of~\cite{CP,BI,Z,B,E}. All our association schemes are symmetric. If $\X, \Y$ are association schemes on a common vertex set then we write $\X \le \Y$ if $\X$ refines $\Y$ as a partition. A fusion of an association scheme is a coarsening which is again an association scheme. {Notice that some authors, for example \cite{KK}, use an opposite order on the set of association schemes. Our choice was motivated by keeping notation consistent with \cite{B,E}. Notice that with this choice of ordering the inclusion $\X \le \Y$ implies a similar inclusion between the automorphism groups $\Aut{\X}\le \Aut{\Y}$.} We denote the Hamming scheme of order $m^d$ and rank $d+1$ by $\cH(d, m)$ and the Johnson scheme of order $\binom{m}{k}$ and rank $k+1$ by $\cJ(m, k)$. The special case $\cH(1, m) \cong \cJ(m, 1)$ is the \emph{trivial scheme}, denoted $\cT_m$. The $d$th tensor power of an association scheme $\X$ is denoted $\X^d$. The symmetrized $d$th tensor power of the Johnson scheme~$\cJ(m, k)$ is called the \emph{Cameron scheme} and denoted $\cC(m, k, d)$. In this paper we classify primitive fusions of $\cJ(m, k)^d$ assuming $m$ is sufficiently large in terms of $k$ and $d$. \begin{theorem} \label{main-thm} {For any positive integers $k,d$ there exists a constant $m_0(k,d)$ such that any primitive fusion $\X$ of $\cJ(m, k)^d$ with $m \geq m_0(k, d)$ belongs, up to permuting coordinates, to one of the following intervals: \begin{enumerate} \item $\cJ(m, k)^d \leq \X \leq \cC(m, k, d)$, \item $\T_{M^e}^{d/e} \leq \X \leq \cH(d/e, M^e)$ for some integer $e \mid d$ where $M=\binom{m}{k}$. \end{enumerate} } \end{theorem} The special cases $k = 1$ and $d = 1$ are worth highlighting individually. In \cite{M-hamming} it was shown that $\cH(d, m)$ has no nontrivial fusions for $m > 4$. The case $k=1$ of Theorem~\ref{main-thm} more generally classifies primitive fusions of $\T_m^d$ (for $m$ sufficiently large). \begin{cor} Let $\X$ be a primitive fusion of $\T_m^d$, where $m \geq m_0(1,d)$. Then, up to permuting coordinates, $\T_{m^e}^{d/e} \le \X \le \cH(d/e, m^e)$ for some integer $e \mid d$. \end{cor} In \cite{M-johnson} it was shown that $\cJ(m, k)$ has no nontrivial fusions for $m \geq 3k+4$. {This result was improved to $m\geq 3k-1$ in \cite{U}.} The case $k = 1$ of Theorem~\ref{main-thm} recovers this result, except for the precise lower bound. \begin{cor} Let $\X$ be a fusion of $\cJ(m, k)$, where $m \geq m_0(k,1)$. Then either $\X = \cJ(m, k)$ or $\X$ is trivial. \end{cor} Association schemes of the type appearing in the conclusion of Theorem~\ref{main-thm} are studied in \cite{E}, where they are called ``Cameron sandwiches'' and ``Hamming sandwiches,'' respectively. The main result of \cite{E} is that there are infinite families of nonschurian Hamming sandwiches. \begin{remark} Imprimitive fusions of $\cJ(m, k)^d$ are not so easily classified. Certainly one must allow arbitrary tensor products of the cases appearing in Theorem~\ref{main-thm}, but there are still many others. For example, the imprimitive wreath product $\T_m \wr \T_m$ (see~\cite[Section~3.4.1]{CP}) is an imprimitive fusion of $\T_m^2$ not fitting this description. \end{remark} As an application we give an elementary classification of primitive groups containing $(A_m^{(k)})^d$. Here $A_m^{(k)}$ denotes the image of the alternating group $A_m$ in its permutation action on $k$-sets, and below $S_m^{(k)}$ is defined similarly. {The statement below is a special case of Cameron's theorem~\cite{cameron,liebeck,maroti}, which more generally classifies all large primitive permutation groups. However, while the proof of Cameron's theorem depends on the classification of finite simple groups, our proof does not.} \begin{cor} \label{cor:cameron} Let $G \le S_n$ be a primitive permutation group containing $(A_m^{(k)})^d$, where $n = \binom{m}{k}^d$ and $m \ge m_0(k, d)$. Then either \begin{enumerate} \item $(A_m^{(k)})^d \le G \le S_m^{(k)} \wr S_d$ or \item $(A_{M^e})^{d/e} \le G \le S_{M^e} \wr S_{d/e}$ for some integer $e \mid d$ where $M = \binom{m}{k}$. \end{enumerate} \end{cor} \begin{proof} { Let $\X$ be the orbital scheme of $G$. It follows from $(A_m^{(k)})^d\leq G$ that $\X$ is a fusion of the orbital scheme of $(A_m^{(k)})^d$, which coincides with $\cJ(m,k)^d$. Thus $\cJ(m,k)^d\leq \X$ and, by Theorem~\ref{main-thm}, either $\cJ(m,k)^d\leq \X \leq \cC(m,k,d)$ or $\T_{M^e}^{d/e} \leq \X \leq \cH(d/e, M^e)$. In the first case, $\X$ has a constituent graph equal to the Cameron graph $C(m, k, d)$. In the second case, $\X$ has a constituent graph equal to the Hamming graph $H(d/e, M^e)$ (which is a special case of a Cameron graph). Applying \cite[Theorem~8.2.1]{wilmes-thesis}, either the claimed conclusion holds or $G$ is small: $|G| \le \exp(c (\log n)^3)$. Since $|G| \ge |(A_m^{(k)})^d| = m!^d$ and~$n = \binom{m}{k}^d \le m^{kd}$, we get $d \log m! \le c (\log n)^3 \le c (kd \log m)^3$, in contradiction to the hypothesis $m \ge m_0(k, d)$. } \end{proof} \section{Notation} Let $[0,k]^d = \{0,\dots,k\}^d$. We use the following notation for vectors $a,b,c \in [0,k]^d$: \begin{align*} &a \leq b \iff a_i \leq b_i ~ \text{for all} ~ i ~ {(\text{in this case we say that } b ~ \text{\emph{dominates}} ~ a)}, &\\ &|a - b| = (|a_1 - b_1|, \dots, |a_d - b_d|),\\ &\min(a, b) = (\min(a_1, b_1), \dots, \min(a_d, b_d)),\\ &\max(a, b) = (\max(a_1, b_1), \dots, \max(a_d, b_d)),\\ &a! = a_1! \cdots a_d!,\\ &\binom{a}{b} = \binom{a_1}{b_1} \cdots \binom{a_d}{b_d},\\ &\wt(a) = a_1 + \cdots + a_d, \\ &\supp(a) = \{ i : a_i > 0\}, \\ &[a] = \{ b \in [0,k]^d : b \leq a\}, \\ &(x)^d = (x, \dots, x), \\ &e_i = (0, \dots, 0, 1, 0, \dots, 0). \end{align*} We understand $\binom{a}{b}$ to be zero unless $(0)^d \le b \le a$. We call $\wt(a)$ the \emph{weight} of $a$ and $\supp(a)$ the \emph{support} of $a$. If $p$ is a polynomial in one variable we write $\deg(p)$ for its degree and $\lt(p)$ for its leading term. \section{Proof} The structure constants of $\cJ(m,k)$ are given by \[ p_{b,c}^a(m) = \sum_{i} \binom{k-a}{i}\binom{a}{k-b-i}\binom{a}{k-c-i} \binom{m-k-a}{b+c+i-k} \] (as in \cite{E,KK}). Here $0 \leq a, b, c \leq k$, and $i$ can be restricted to the range \[ \max(0,k-a-b,k-b-c,k-a-c) \leq i \leq \min(k-a,k-b,k-c, m-a-b-c). \] In the following we always assume $m \geq 3k$. Under this assumption we have $p_{b,c}^a(m) > 0$ if and only if $a,b,c$ satisfy the triangle inequalities \cite[Lemma~4.1]{E}. More precisely we have the following. \begin{lemma} We have $p^a_{b, c}(m) > 0$ if and only if $|b - c| \leq a \leq b + c$. Assuming that~$0 \leq b - c \leq a \leq b + c$, the leading term of $p^a_{b,c}(m)$ is \[ \lt(p_{b,c}^a(m)) = \begin{cases} \binom{a}{b}\binom{a}{c}\frac{1}{(b+c - a)!} m^{b+c-a} &: a \geq b,\\ \binom{k-a}{k-b}\binom{a}{b-c}\frac{1}{c!} m^{c} &: a\leq b. \end{cases} \] In particular, $\deg(p_{b,c}^a(m))\leq \min(b,c)$, and equality holds if and only if $a \leq \max(b,c)$. \end{lemma} Now consider $\cJ(m, k)^d$. For $a, b, c \in [0,k]^d$, let \[ p^a_{b,c}(m) = \prod_{i=1}^d p^{a_i}_{b_i,c_i}(m). \] These are the structure constants of $\cJ(m, k)^d$. The following lemma generalizes the previous one. \begin{lemma} Let $a,b,c\in[0,k]^d$. Then $p^a_{b,c}(m) > 0$ if and only if $|b-c| \leq a \leq b + c$ Moreover $\deg(p_{b,c}^a(m)) \leq \wt(\min(b, c))$, with equality if and only if $a \leq \max(b, c)$. If~$\deg(p_{b,c}^a(m)) = \wt(b) = \wt(c)$ then $a \leq b = c$ and the leading term of $p^a_{b,c}(m)$ is \[ \lambda(p^a_{b,c}(m)) = \binom{(k)^d - a}{(k)^d - b} \frac{1}{b!} m^{\wt(b)}. \] \end{lemma} \begin{proof} It follows from $p_{b,c}^a(m) = \prod_{i=1}^d p_{b_i c_i}^{a_i}(m)$ that $p_{b,c}^a(m)>0$ iff each triple $a_i,b_i,c_i$ satisfies the triangle condition $|b_i-c_i|\leq a_i \leq b_i+c_i$. In this case \[ \deg(p_{b,c}^a(m)) = \sum_{i=1}^d \deg(p_{b_i, c_i}^{a_i}(m))\leq \sum_{i=1}^d\min(b_i,c_i) = \wt(\min(b, c)). \] Equality holds if and only if $a_i \leq \max(b_i, c_i)$ for all $i$. If $\deg(p_{b,c}^a(m)) = \wt(b) = \wt(c)$ then $\wt(\min(b, c)) = \wt(b) = \wt(c)$, which implies $b = c$, and moreover we have seen that we must have $a \leq b$. Multiplying the leading terms of $p^{a_i}_{b_i,c_i}(m)$ given by the previous lemma, we get the claimed formula. \end{proof} Let $\X$ be a fusion of $\cJ(m, k)^d$. Since $\X$ is a coarsening of $\cJ(m, k)^d$ there is a partition $\fS$ of $[0,k]^d$ such that $\X = \{R_\alpha : \alpha \in \fS\}$, where \[ (u, v) \in R_\alpha \iff (|u_1 \setminus v_1|, \dots, |u_d \setminus v_d|) \in \alpha. \] In this situation we write $\X = \cJ(m, k)^\fS$ \cite[Section~4]{E}. For $\beta, \gamma \in \fS$ and $a \in [0,k]^d$ define \[ p^a_{\beta,\gamma}(m) = \sum_{b\in \beta, c \in \gamma} p^a_{b,c}(m). \] For $\X = \cJ(m,k)^\fS$ to be an association scheme, $\fS$ must satisfy two conditions: \begin{enumerate} \item $\{(0)^d\} \in \fS$, \item $p^a_{\beta,\gamma}(m) = p^{a'}_{\beta,\gamma}(m)$ for all $\alpha,\beta,\gamma \in \fS$ and $a,a' \in \alpha$. \end{enumerate} We may denote the common value of $p^a_{\beta,\gamma}(m) ~ (a\in\alpha)$ by $p^\alpha_{\beta,\gamma}(m)$; these are the structure constants of $\X$. We call the sets $\alpha \in \fS$ the \emph{basic $\fS$-sets}; their unions are called \emph{$\fS$-sets}. For nonempty $S \subseteq [0,k]^d$ let $\wt(S) = \max\{\wt(b) \mid b \in S\}$. For $\alpha \in \fS$ let $\alpha^*$ be the set of $a \in \alpha$ of maximal weight. Let $D_\alpha = \bigcup_{a \in \alpha^*} [a]$. Note that $\alpha^*\subseteq D_\alpha$. {For any $\alpha,\beta\subseteq [0,k]^d$ and $a\in [0,k]^d$ the structure constant $p_{\alpha,\beta}^a(m)$ is a real polynomial in $m$ the coefficients of which depend on $\alpha,\beta$ and $a$. For every pair of distinct real polynomials $f,g\in \mathbb{R}[x]$ there exists a real number $c_{f,g}\in\mathbb{R}$ such that~$f(x)\neq g(x)$ holds for all $x > c_{f,g}$. Therefore, there exists a constant $m_0(k,d)$ such that, provided $m \geq m_0(k, d)$, the following condition holds for all $\alpha,\beta\subset [0,k]^d$ and~$a,b\in [0,k]^d$: \begin{align}\label{poly} p_{\alpha,\beta}^a(m) = p_{\alpha,\beta}^b(m) &\implies p_{\alpha,\beta}^a(m) = p_{\alpha,\beta}^b(m)\text{ as polynomials in } m \\ \notag &\implies \lambda(p_{\alpha,\beta}^a(m)) = \lambda(p_{\alpha,\beta}^b(m)). \end{align}} {In what follows we assume that $m \geq m_0(k, d)$ and hence $p^a_{\beta,\gamma}(m) = p^{a'}_{\beta,\gamma}(m)$ only if $p^a_{\beta,\gamma}(m)$ and $p^{a'}_{\beta,\gamma}(m)$ are equal as polynomials in $m$.} \begin{prop}\label{key-prop} Let $\beta \in \fS$ be a basic $\fS$-set. \begin{enumerate} \item $D_\beta$ is an $\fS$-set, and $\wt(D_\beta \setminus \beta) < \wt(\beta)$. \item For every basic set $\alpha \in \fS$ there is a constant $N^\beta_\alpha$ such that \[ \sum_{b : a \leq b \in \beta^*} \binom{(k)^d - a}{(k)^d - b} = N^\beta_\alpha \qquad (a \in \alpha). \] \item Every element of $\beta$ is dominated by a unique element of $\beta^*$. \item Either $\wt(\beta) = \wt(D_\beta \setminus \beta) + 1$ or $\beta^* \subset \{0, k\}^d$. \end{enumerate} \end{prop} \begin{proof} Let $w = \wt(\beta)$ and $D = D_\beta$. Then, since the polynomials $p^a_{b,c}(m)$ have positive leading coefficient whenever they are nonzero, the degree of $p^a_{\beta,\beta}(m)$ is, by the previous lemma, \[ \deg(p^a_{\beta,\beta}(m)) = \max_{b, c \in \beta} \deg(p^a_{b,c}(m)) \le \max_{b, c \in \beta} \wt(\min(b, c)) \le w, \] with equality holding if and only if $a \leq b = c \in \beta^*$, i.e., if and only if $a \in D$. Since~$p^a_{\beta,\beta}(m)$ should depend only on the cell of $\fS$ containing $a$, it follows that $D$ is an $\fS$-set. Since $\beta$ is basic, $\beta \subset D$, and since $\beta \supset \beta^*$ we have $\wt(D \setminus \beta) < \wt(\beta)$. Moreover if $a \in D$ then the leading term of $p^a_{\beta,\beta}$ is \[ \lambda(p^a_{\beta,\beta}(m)) = \sum_{b : a \leq b \in \beta^*} \binom{(k)^d - a}{(k)^d - b} \frac1{b!} m^w, \] and again this should depend only on the cell $\alpha$ containing $a$. {Taking $\alpha = \beta$ and $a\in \beta^*$, it follows that $a!$ is a constant for $a \in \beta^*$.} Hence (2) holds (if $\alpha$ is not contained in $D$ then $N^\beta_\alpha = 0$). Next apply (2) with $\alpha = \beta$. Taking $a \in \beta^*$ shows $N^\beta_\beta = 1$, so (3) holds. Finally let $b \in \beta^*$ and suppose $a = b - e_i \ge 0$. If $a \in \beta$ then we get \[ \binom{k-b_i+1}{k-b_i} = N^\beta_\beta = 1, \] so $b_i = k$. Hence either $\wt(b) = \wt(\beta)+1$ or $b_i \in \{0, k\}$ for all $i$, which implies (4). \end{proof} We can define a partial ordering on $\fS$ by saying $\alpha \preceq \beta$ if every $a \in \alpha$ is dominated by some $b \in \beta$. By part (3) of the proposition, this is equivalent to $N^\beta_\alpha > 0$. It is obvious that $\preceq$ is reflexive and transitive on $\fS$. To verify antisymmetry, note that if $\alpha \preceq \beta \preceq \alpha$ and $a \in \alpha^*$ then there are $b \in \beta$ and $a' \in \alpha$ such that $a \le b \le a'$, which by maximality of $a$ implies $a = b = a'$ and hence $\alpha = \beta$ since $\fS$ is a partition. We say~$\alpha \in \fS$ is \emph{minimal} if it is minimal in $(\fS \setminus \{(0)^d\}, \preceq)$. \begin{cor} Let $\alpha \in \fS$ be a minimal basic set. Then $D_\alpha = \alpha \cup \{(0)^d\}$. Moreover, the elements of $\alpha^*$ have disjoint equal-sized supports, and we either have $\wt(\alpha) = 1$ or $\alpha^* \subset \{0, k\}^d$. \end{cor} \begin{proof} Apply the proposition. Note that if $\beta$ is a basic subset of $D_\alpha \setminus \alpha$ then $\beta \prec \alpha$. By minimality of $\alpha$ this implies $\beta = \{(0)^d\}$. Hence $D_\alpha = \alpha \cup \{(0)^d\}$. Next, for any $a \in \alpha^*$ and $i \in \supp(a)$ we have $e_i \in D_\alpha$. By part (3) of Proposition~\ref{key-prop}, $a$ is the unique element of $\alpha^*$ dominating $e_i$. Therefore the elements of $\alpha^*$ have disjoint supports. By part (4), either $\wt(\alpha) = 1$ or $\alpha^* \subset \{0, k\}^d$. If $\wt(\alpha) = 1$ then all $a \in \alpha^*$ have singleton support, and otherwise $|\supp(a)| = \wt(a) / k = \wt(\alpha) / k$ for all $a \in \alpha^*$. \end{proof} Until now $\X$ could be imprimitive. Now we specialize to the primitive case to complete the proof of Theorem~\ref{main-thm}. Let $\alpha \in \fS$ be minimal. If $\X$ is primitive then $R_\alpha$ must be connected, which implies that $\alpha^*$ covers $\{1, \dots, d\}$. Hence $\alpha^*$ is an equipartition of~$\{1, \dots ,d\}$. Let $w = \wt(\alpha)$. If $w = 1$ then $\alpha^*$ must be the set of elements of weight $1$, so $R_\alpha$ is the Cameron graph. Since the Weisfeiler--Leman stabilization of the Cameron graph is the Cameron scheme, we find $\X \le \cC(m, k, d)$. If $w > 1$ then~$\alpha^* \subset \{0, k\}^d$. If the elements of $\alpha^*$ have support size $e$ then $R_\alpha$ is the Hamming graph $H(M^e, d/e)$, so $\X \le \cH(d/e, M^e)$. To finish we must show $\cT_{M^e}^{d/e} \le \X$. For this it suffices to prove that for every $\beta \in \fS$, the elements of $\beta^*$ are sums of elements of $\alpha^*$ (and in particular~$\beta^* \subset \{0, k\}^d$). We apply Proposition~\ref{key-prop}(2) to $\alpha$ and $\beta$. Let $i \in \{1, \dots, d\}$. Taking $a = e_i$, we find that $N^\beta_\alpha$ is at least the number of $b \in \beta^*$ such that $b_i > 0$. On the other hand, taking~$a$ to be the unique element of $\alpha^*$ dominating $e_i$, since $a \in \{0,k\}^d$ we find that~$N^\beta_\alpha$ is equal to the number of $b \in \beta^*$ such that $a \le b$. Hence $b_i > 0$ implies $a \le b$. This implies that $b$ is the sum of those $a \in \alpha^*$ such that $a \le b$, as required. \bibliographystyle{mersenne-plain} \bibliography{ALCO_Eberhard_737} \end{document}