% A LaTeX2e file for a 25 page document. \documentclass[12pt]{article} \usepackage{amssymb,latexsym} \textwidth=6in \textheight=9in \evensidemargin=0in \oddsidemargin=\evensidemargin \advance\topmargin by-\headheight \def\aut{\mathop{\rm Aut}\nolimits} \def\bpl{\mathop{\boxplus}\nolimits} \def\C{\mathbb C} \def\cel{\mathop{\rm Cel}\nolimits} \def\dim{\mathop{\rm dim}\nolimits} \def\G{\Gamma} \def\I{{\cal I}} \def\id{\mathop{\rm id}\nolimits} \def\iso{\mathop{\rm Iso}\nolimits} \def\isow{\mathop{\rm Isow}\nolimits} \def\J{{\cal J}} \def\K{{\cal K}} \def\k{{(k)}} \def\L{{\widehat L}} \def\Mat{\mathop{\rm Mat}\nolimits} \def\m{{(m)}} \def\mod{\mathop{\rm mod}\nolimits} \def\orb{\mathop{\rm Orb}\nolimits} \def\ov{\overline} \def\P{{\cal P }} \def\R{{\cal R}} \def\RR{{\widehat\R}} \def\sch{\mathop{\rm Sch}\nolimits} \def\sym{\mathop{\rm Sym}\nolimits} \def\WCP{\widehat{{\cal W}'}} \def\WP{\widehat{W'}} \def\W{{\widehat W}} \def\WC{{\cal W}} \def\WL{\mathop{\rm WL}\nolimits} \def\wh{\widehat} \def\wt{\widetilde} \def\Z{{\cal Z}} \def\proof{{\bf Proof}.\ } \def\bull{\vrule height .9ex width .8ex depth -.1ex } \def\SuSS{\stepcounter{subsection}{\bf\thesubsection{.}} \addtocounter{subsection}{-1}\refstepcounter{subsection}} \def\eSuSS{\vspace{2mm}\SuSS} \newtheorem{formula}{}[section] \newtheorem{proposition}[formula]{Proposition} \newtheorem{definition}[formula]{Definition} \newtheorem{corollary}[formula]{Corollary} \newtheorem{remark}[formula]{Remark} \newtheorem{lemma}[formula]{Lemma} \newtheorem{theorem}[formula]{Theorem} \def\thrm{\begin{theorem}} \def\ethrm{\end{theorem}} \def\rmrk{\begin{remark}} \def\ermrk{\end{remark}} \def\dfntn{\begin{definition}} \def\edfntn{\end{definition}} \def\nmrt{\begin{enumerate}} \def\enmrt{\end{enumerate}} \def\tm#1{\item[{\rm (#1)}]} \def\qtn{\begin{equation}} \def\eqtn{\end{equation}} \def\lmm{\begin{lemma}} \def\elmm{\end{lemma}} \def\crllr{\begin{corollary}} \def\ecrllr{\end{corollary}} \begin{document} \pagestyle{myheadings} \markright{\sc the electronic journal of combinatorics 6 (1999), \#R18\hfill} \thispagestyle{empty} \title{ On highly closed cellular algebras\\ and highly closed isomorphisms \thanks{Research supported by RFFI, grants 96-15-96060 and 96-01-00676.}\\[6mm] \hfill\parbox{67mm} {\small\it Dedicated to A. A. Lehman and B. Yu. Weisfeiler on the occasion of the 30th anniversary of their paper where the cellular algebra first appeared.\\ \small\rm Sapienti sat... }{\quad\quad} } \author{ Sergei Evdokimov \\ \small St. Petersburg Institute \\[-2pt] \small for Informatics and Automation \\[-2pt] {\tt \small evdokim@pdmi.ras.ru } \and Ilia Ponomarenko \\ \small Steklov Institute of Mathematics\\[-2pt] \small at St. Petersburg \\[-2pt] {\tt \small inp@pdmi.ras.ru} } \date{\small Submitted: June 2, 1998; Accepted: November 6, 1998} \maketitle \begin{abstract} We define and study $m$-closed cellular algebras (coherent configurations) and $m$-iso\-mor\-phisms of cellular algebras which can be regarded as $m$th approximations of Schurian algebras (i.e. the centralizer algebras of permutation groups) and of strong isomorphisms (i.e. bijections of the point sets taking one algebra to the other) respectively. If $m=1$ we come to arbitrary cellular algebras and their weak isomorphisms (i.e. matrix algebra isomorphisms preserving the Hadamard multiplication). On the other hand, the algebras which are $m$-closed for all $m\ge 1$ are exactly Schurian ones whereas the weak isomorphisms which are $m$-isomorphisms for all $m\ge 1$ are exactly ones induced by strong isomorphisms. We show that for any $m$ there exist $m$-closed algebras on $O(m)$ points which are not Schurian and $m$-isomorphisms of cellular algebras on $O(m)$ points which are not induced by strong isomorphisms. This enables us to find for any~$m$ an edge colored graph with $O(m)$ vertices satisfying the $m$-vertex condition and having non-Schurian adjacency algebra. On the other hand, we rediscover and explain from the algebraic point of view the Cai-F{\"u}rer-Immerman phenomenon that the $m$-dimensional Weisfeiler-Lehman method fails to recognize the isomorphism of graphs in an efficient way. \end{abstract} \section{Introduction} The association scheme theory was called in \cite{BI} a ``group theory without groups''. Indeed, the axiomatics of association schemes reflects combinatorial properties of permutation groups. The close connection between these objects is stressed by the fact that each permutation group produces a scheme the basis relations of which are exactly the 2-orbits of the group. However, this correspondence is not reversible and there are schemes which can not be obtained in such a way (for example, the scheme of the Shrikhande graph). A similar situation arises if one is interested in isomorphisms of schemes. Namely, each of them induces a combinatorial isomorphism which can be defined as an ordinary isomorphism of the adjacency algebras of the schemes preserving the basis matrices. But also in this case there are combinatorially isomorphic schemes which are not isomorphic (for example, the Hamming schemes and the schemes of the Doob graphs). The main purpose of this paper is to prove the nondegeneracy of the natural filtration of the class of all schemes (resp. of all combinatorial isomorphisms) whose limit is the class of all permutation group schemes (resp. genuine isomorphisms of schemes). Having in mind the algebraic nature of the above questions we prefer to deal with the adjacency algebra of a coherent configuration being a generalization of an association scheme. These algebras were introduced by B.~Yu.~Weisfeiler and A.~A.~Lehman as cellular algebras and independently by D.~G.~Higman as coherent algebras (see~\cite{WL} and~\cite{Hi}). They are by definition matrix algebras over~$\C$ closed under the Hadamard multiplication and the Hermitian conjugation and containing the identity matrix and the all-one matrix. Let $W$ be a cellular algebra on a finite set~$V$, i.e. a cellular subalgebra of the full matrix algebra $\Mat_V$ on~$V$. The automorphism group $\aut(W)$ of~$W$ consists by definition of all permutations of~$V$ preserving any matrix of~$W$. In this language a group scheme corresponds to a Schurian cellular algebra (see~\cite{FKM} for the explanation of the term), i.e. one coinciding with the centralizer algebra of its automorphism group. A combinatorial isomorphism of coherent configurations is transformed to a weak isomorphism of cellular algebras which is by definition a matrix algebra isomorphism preserving the Hadamard multiplication. Our technique is based on the following notion of the extended algebra introduced in~\cite{EKP} (for the exact definition see Section~\ref{eaac}). For each positive integer $m$ we define the $m$-dimensional extended algebra $\W^\m$ of a cellular algebra~$W$ on~$V$ as the smallest cellular algebra on $V^m$ containing the $m$-fold tensor product of~$W$ and the adjacency matrix of the reflexive relation corresponding to the diagonal of $V^m$. (This definition differs from that of~\cite{EKP} but Theorem~\ref{tpea1} of this paper establishes the equivalence between them.) Using the natural bijection between the diagonal of $V^m$ and~$V$ we define a cellular algebra $\ov{W}^\m$ on~$V$ called the $m$-closure of~$W$. This produces the following series of inclusions: $$W=\ov{W}^{(1)}\leq\ldots\leq \ov{W}^{(n)}=\ldots=\sch(W)$$ where $\sch(W)$ is the centralizer algebra of $\aut(W)$ in $\Mat_V$ and $n$ is the number of elements of~$V$. Thus the $m$-closure of~$W$ can be viewed as an $m$th approximation of its Schurian closure $\sch(W)$. We say that~$W$ is $m$-closed if $\ov{W}^{(m)}=W$. Each algebra is certainly 1-closed and it is $m$-closed for all~$m$ iff it is Schurian. Thus $$\bigcap_{m=1}^\infty\WC_m=\WC_\infty,\quad \WC_m\supset\WC_{m+1}$$ where~$\WC_m$ (resp.~$\WC_\infty$) is the class of all $m$-closed (resp. Schurian) cellular algebras. Surely, the larger~$m$ is, the more an $m$-closed algebra is similar to the centralizer algebra of a permutation group. For example, some nontrivial facts from permutation group theory can be generalized even to 2-closed cellular algebras (see~\cite{EP}). The following theorem shows in particular that the filtration~$\{\WC_m\}_{m=1}^\infty$ does not collapse from any~$m$. \thrm \label{theorem1} There exists $\varepsilon>0$ such that for any sufficiently large positive integer $n$ one can find a non-Schurian cellular algebra on~$n$ points which is $m$-closed for some $m\geq\lfloor\varepsilon n\rfloor$. \ethrm One of the application of the theorem is related to constructing graphs satisfying the $m$-vertex condition in sense of~\cite{HH} (see also Subsection~\ref{mvcon}). Namely, we show (Theorem~\ref{thrd}) that the edge colored graph (coherent configuration) underlying an $m$-closed cellular algebra satisfies the $m$-vertex condition. So Theorem~\ref{theorem1} implies the following statement. \crllr \label{ucoro} For any positive integer~$m$ there exists an edge colored graph with $O(m)$ vertices satisfying the $m$-vertex condition and having non-Schurian adjacency algebra. \ecrllr Concerning the combinatorial isomorphism problem we refine the concept of a weak isomorphism. Namely, we say that a weak isomorphism of cellular algebras is an $m$-isomorphism if it can be extended to a weak isomorphism of their $m$-extended algebras (see Section~\ref{wkis} for the exact definition). Obviously, each weak isomorphism is a 1-isomorphism in this sense. On the other hand, Theorem~\ref{n2star} shows that it is an $m$-isomorphism for all~$m$ iff it is induced by a strong isomorphism (which is by definition a bijection between the point sets preserving the algebras). The following theorem is similar to Theorem~\ref{theorem1}. \thrm \label{theorem2} There exists $\varepsilon>0$ such that for any sufficiently large positive integer $n$ one can find a cellular algebra on~$n$ points (even a Schurian one) admitting an $m$-isomorphism with $m\geq\lfloor\varepsilon n\rfloor$ which is not induced by a strong isomorphism. \ethrm It follows from the proof of Theorem~\ref{theorem2} that the required algebra can be chosen having simple spectrum. So there exist weak isomorphisms of cellular algebras with simple spectrum which are not induced by strong isomorphisms. This shows that Theorem~5.6 from~\cite{F} is not true. Let us briefly outline the proofs of the theorems. To prove Theorem~\ref{theorem2} we construct a family of cellular algebras with simple spectrum each of which corresponds to some cubic (3-regular) graph. Any such algebra admits a weak isomorphism~$\varphi$ which is not induced by a strong isomorphism (Theorem~\ref{nexwi}). Moreover, if the graph is a Ramanujan one, this weak isomorphism becomes induced by a strong one when restricted to sufficiently large point sets. In this case we are able to prove that $\varphi$ is in fact an $m$-isomorphism for a sufficiently large~$m$ and the corresponding algebra~$W$ is a Schurian one. Theorem~\ref{theorem1} is deduced from Theorem~\ref{theorem2} by considering the wreath product of the cellular algebra~$W$ by the symmetric group on~2 points with respect to the weak isomorphism~$\varphi$. This wreath product is not Schurian, since~$\varphi$ is not induced by a strong isomorphism. On the other hand, it is $m$-closed for a sufficiently large~$m$ due to the facts that so is~$W$ (being a Schurian one) and~$\varphi$ is an $m$-isomorphism. The last implication is the result of the detailed analysis of the extended algebras of general direct sums and wreath products (Theorems~\ref{eads} and~\ref{clwr}). In the context of the discussed topics we can ask ourselves: is the filtration~$\{\WC_m\}_{m=1}^\infty$ defined above natural in a sense. For instance, one can compare it to some other filtrations. A number of them arises from combinatorial algorithms related to the Graph Isomorphism Problem which is polynomial-time equivalent to the problem of constructing the Schurian closure of a cellular algebra. The analysis of such algorithms lead us in~\cite{EKP} to the following concept of a Schurian polynomial approximation scheme reflecting the idea of measuring non-Schurity. Let us have a rule according to which given a cellular algebra $W\leq\Mat_V$ and a positive integer $m$ a cellular algebra $S_m(W)\le\Mat_V$ can be constructed. We say that the operators $W\mapsto S_m(W)$ $(m=1,2,\ldots)$ define a {\it Schurian polynomial approximation scheme}~$S$ if the following conditions are satisfied: \nmrt \item[{\rm (1)}] $W=S_1(W)\leq\ldots\leq S_n(W)=\ldots=\sch(W)$; \item[{\rm (2)}] $S_l(S_m(W))=S_m(W)$ for all $l=1,\ldots,m$; \item[{\rm (3)}] $S_m(W)$ can be constructed in time $n^{O(m)}$ \enmrt where $n$ is the number of elements of~$V$. Each scheme of such a kind defines a filtration of the class of all cellular algebras. Moreover, there is a natural way to compare the filtrations by comparing the underlying schemes. Namely, let~$S$ and~$T$ be two Schurian polynomial approximation schemes. We say that $S$ is dominated by $T$ if there exists a positive integer $c=c(S,T)$ such that $S_m(W)\le T_{cm}(W)$ for all cellular algebras~$W$ and all~$m$. Schemes $S$~and $T$ are called equivalent if each of them is dominated by the other. We proved in \cite{EKP} that the operators $W\mapsto\ov W^\m$ mapping a cellular algebra $W$ to its $m$-closure define a Schurian polynomial approximation scheme. Another example is given by the well-known $m$-dimensional Weisfeiler-Lehman method ($m$-dim W-L, see~\cite{CFI}). Despite the fact that in its original form this method can be applied only to graphs, a natural interpretation of it produces the algorithm which given a cellular algebra $W$ constructs a certain cellular algebra $\WL_m(W)$ ($m=1,2,...$) satisfying conditions (1)-(3) above (the exact definitions can be found in Section~\ref{eoss}). The third main result of the paper shows that these schemes are equivalent. \thrm \label{theorem3} Let $W$ be a cellular algebra on $V$. Then $$\WL_m(W)\leq\ov W^\m \leq \WL_{3m}(W),\quad m=1,2,\ldots.$$ In particular, the Schurian polynomial approximation schemes corresponding to the $m$-closure and the $m$-dimensional Weisfeiler-Lehman methods are equivalent. \ethrm The proof of the theorem is based on the notion of a {\it stable} partition of $V^m$, the axiomatics of which gathers some combinatorial regularity conditions generalizing those satisfied by the $m$-orbits of a permutation group. It should be noted that similar objects were considered in~\cite{Iv} and~\cite{Sm}. The key point of the analysis consists of the fact that the partition of~$V^m$ found by the $m$-dim W-L method is a stable partition of~$V^m$ in our sense (Theorem~\ref{spcol}). Besides, it turns out that a stable partition of $V^{3m}$ produces a coherent configuration on~$V^m$ (Lemma~\ref{prsp}). Combining these observations and the inclusion $\WL_{m}(W)\leq\ov W^{(m)}$ proved in~\cite{EKP} we obtain the required statement. We complete the introduction by making some remarks concerning the $m$-dim W-L method. This method was discovered to test the isomorphism of two graphs by comparing the canonical colorings of $V^m$ constructed from them. However it was proved in~\cite{CFI} that there exist infinitly many pairs of non-isomorphic vertex colored graphs with~$O(m)$ vertices for which the $m$-dim W-L method does not recognize their non-isomorphism. Nevertheless, the technique used for the proof of this result leaves the algebraic nature of this phenomenon unclear. In contrast to~\cite{CFI} the results of the present paper completely clarify the situation. Namely, let $\G_1$ and $\G_2$ be two graphs which can not be identified by the $m$-dim W-L method (see~\cite{CFI}). Then the cellular algebras $W_1$ and $W_2$ generated by the adjacency matrices of them are weakly isomorphic and this weak isomorphism is not induced by a strong one. Moreover, it follows from Theorem~\ref{comsch} that the last isomorphism can be extended to a weak isomorphism of the $\lfloor m/3\rfloor$-extended algebras corresponding to~$W_1$ and~$W_2$. So it is in fact an $\lfloor m/3\rfloor$-isomorphism. Thus the algebraic reason for the high-dimensional W-L method to fail in recognizing the isomorphism of graphs is that there are highly closed isomorphisms of cellular algebras which are not induced by strong isomorphisms (Theorem~\ref{theorem2}). In fact the construction underlying Theorem~\ref{theorem2} produces for any positive integer~$m$ examples of non-isomorphic edge colored graphs (even vertex colored ones) with~$O(m)$ vertices which are indistinguishable by the $m$-dim W-L method due to Theorem~\ref{comsch}. We notice that these graphs slightly differ from those found by Cai-F{\" u}rer-Immerman in~\cite{CFI}. The paper consists of six sections and Appendix. Section~2 contains the main definitions and notation concerning cellular algebras. In Section~\ref{eaac} we define extended algebras and closures. Also we describe the connection of these notions with the $m$-vertex condition. Section~\ref{wkis} is devoted to refining the notion of a weak isomorphism. In Sections~\ref{nsca} and~~\ref{eoss} we prove Theorems~\ref{theorem1} and~\ref{theorem2}, and Theorem~\ref{theorem3} respectively. Appendix contains the explicit description of the extended algebras of the direct sum and the wreath product by a permutation group. These results are used in proving Theorems~\ref{theorem1} and~\ref{theorem2}. {\bf Notation.} As usual by $\C$ we denote the complex field. Throughout the paper $V$ denotes a finite set with $n = |V|$ elements. The algebra of all complex matrices whose rows and columns are indexed by the elements of~$V$ is denoted by $\Mat_V,$ its unit element (the identity matrix) by $I_V$ and the all-one matrix by $J_V.$ For $U \subset V$ the algebra $\Mat_U$ is considered in a natural way as a subalgebra of $\Mat_V.$ For $U, U' \subset V$ let $J_{U,U'}$ denote the \{0,1\}-matrix with 1's exactly on the places belonging to $U \times U'.$ The transpose of a matrix $A$ is denoted by $A^T$, its Hermitian conjugate by $A^*.$ Each bijection $g:V \to V'$ defines a natural algebra isomorphism from $\Mat_V$ onto $\Mat_{V'}.$ The image of a matrix $A$ under $g$ will be denoted by $A^g.$ The group of all permutations of $V$ is denoted by $\sym(V).$ For integers $l,m$ the set $\{l,l+1,\ldots,m\}$ is denoted by $[l,m]$. We write $[m]$, $\sym(m)$, $\Mat_m$, $V^m$ and $V$ instead of $[1,m]$, $\sym([m])$, $\Mat_{[m]}$, $V^{[m]}$ and $V^1$ respectively. \section{Cellular algebras} \label{catc} All undefined terms below concerning cellular algebras and permutation groups can be found in~\cite{W} and~\cite{Wi} respectively. \eSuSS By a {\it cellular algebra} on~$V$ we mean a subalgebra $W$ of~$\Mat_V$ for which the following conditions are satisfied: \nmrt \item[{\rm (C1)}] $I_V,J_V\in W$; \item[{\rm (C2)}] $\forall A\in W:\quad A^*\in W$; \item[{\rm (C3)}] $\forall A,B\in W:\quad A\circ B\in W$, \enmrt where $A\circ B$ is the Hadamard (componentwise) product of the matrices $A$ and~$B$. It follows from~(C2) that $W$ is a semisimple algebra over~$\C$. Each cellular algebra $W$ on $V$ has a uniquely determined linear base $\R=\R(W)$ consisting of \{0,1\}-matrices such that \qtn \label{laststar} \sum_{R\in\R}R=J_V\quad\mbox{and}\quad R\in\R\ \Leftrightarrow\ R^T\in\R. \eqtn The linear base $\R$ is called the {\it standard basis} of~$W$ and its elements the {\it basis matrices}. The nonnegative integers $c^T_{R,S}$ defined by $RS = \sum_{T\in \R} c^T_{R,S}\cdot T$ where $R,S\in\R$, are called the {\it structure constants} of~$W$. Set $\cel(W)=\{U\subset V:\ I_U\in\R\}$ and $\cel^*(W)=\{\bigcup_{U\in S}U:\ S\subset\cel(W)\}$. Each element of $\cel(W)$ (resp. $\cel^*(W)$) is called a {\it cell} of~$W$ (resp. a {\it cellular set} of~$W$). Obviously, $$V=\bigcup_{U\in\cel(W)}U\qquad \mbox{(disjoint union).}$$ The algebra $W$ is called {\it homogeneous} if $|\cel(W)|=1$. For $U,U'\in\cel^*(W)$ set $\R_{U,U'}=\{R\in\R:\ R\circ J_{U,U'}=R\}$. Then $$\R=\bigcup_{U,U'\in\cel(W)}\R_{U,U'}\qquad\mbox{(disjoint union).}$$ Moreover, given cells $U,U'$ the number of 1's in the $u$th row (resp. $v$th column) of the matrix $R\in \R_{U,U'}$ does not depend on the choice of $u\in U$ (resp. $v\in U'$). For each $U\in\cel^*(W)$ we view the subalgebra $I_UWI_U$ of~$W$ as a cellular algebra on~$U$ and denote it by $W_U$. The basis matrices of $W_U$ are in 1-1 correspondence to the matrices of~$\R_{U,U}$. If $U\in\cel(W)$ we call $W_U$ the {\it homogeneous component} of~$W$ corresponding to~$U$. Each matrix $R\in\R$ being a \{0,1\}-matrix is the adjacency matrix of some binary relation on $V$ called a {\it basis relation} of~$W$. By (\ref{laststar}) the set of all of them form a partition of $V\times V$ which can be interpreted as a coherent configuration on~$V$ (see~\cite{Hi}). We use all the notations introduced for basis matrices also for basis relations. \eSuSS A large class of cellular algebras comes from permutation groups as follows (see~\cite{W}). Let $G\leq\sym(V)$ be a permutation group and $$\Z(G)=\Z(G,V)=\{A\in\Mat_V:\ A^g=A,\ g\in G\}$$ be its centralizer algebra. Then $\Z(G)$ is a cellular algebra on $V$ such that $\cel(\Z(G))=\orb(G)$ and $\R(\Z(G))=\orb_2(G)$ where $\orb(G)$ is the set of orbits of~$G$ and $\orb_2(G)$ is the set of its 2-orbits. We say that cellular algebras $W$ on~$V$ and~$W'$ on~$V'$ are {\it strongly isomorphic}, if $W^g=W'$ for some bijection $g:V\to V'$ called a {\it strong isomorphism} from~$W$ to~$W'$. Clearly,~$g$ induces a bijection between the sets $\R(W)$ and $\R(W')$. We use notation $\iso(W,W')$ for the set of all isomorphisms from~$W$ to~$W'$. The group $\iso(W,W)$ contains a normal subgroup $$\aut(W)=\{g\in\sym(V):\ A^g=A,\ A\in W\}$$ called the {\it automorphism group} of~$W$. If $W=\Z(\aut(W))$, then $W$ is called {\it Schurian}. It is easy to see that $W$ is Schurian iff the set of its basis relations coincides with the set of 2-orbits of $\aut(W)$. It follows from~\cite{Wi} that there exist cellular algebras which are not Schurian (see also~\cite{FKM}). \eSuSS The set of all cellular algebras on $V$ is ordered by inclusion. The largest and the smallest elements of this set are respectively the full matrix algebra $\Mat_V$ and the simplex on~$V$, i.e. the algebra with the linear base $\{I_V,J_V\}$. For cellular algebras~$W$ and~$W'$ we write $W\le W'$ if~$W$ is a subalgebra of~$W'$. Given subsets $X_1,\ldots,X_s$ of $\Mat_V$, their cellular closure, i.e. the smallest cellular algebra containing all of them, is denoted by $[X_1,\ldots,X_s]$. If $X_i=\{A_i\}$ we omit the braces. \section{Extended algebras and closures} \label{eaac} \SuSS The notion of an $m$-closed cellular algebra was introduced in~\cite{EKP} in connection with the Schurity problem. It goes back to~\cite{W} where a similar notion was defined in an algorithmic way. We start with the main definitions concerning highly closed cellular algebras. Let $W$ be a cellular algebra on $V$. For each positive integer~$m$ we set $$\W=\W^\m=[W^m,\ \Z_m(V)]$$ where $W^m=W\otimes\cdots\otimes W$ is the $m$-fold tensor product of~$W$ and $\Z_m(V)$ is the centralizer algebra of the coordinatewise action of $\sym(V)$ on $V^m$. We call the cellular algebra $\W\le\Mat_{V^m}$ the {\it $m$-dimensional extended algebra} of~$W$. The group $\aut(\W)$ acts faithfully on the set $$\Delta=\Delta^\m(V)=\{(v,\ldots,v)\in V^m:\ v\in V\}.$$ Moreover, the mapping $\delta:v\mapsto (v,\ldots,v)$ induces a permutation group isomorphism between $\aut(W)$ and the constituent of $\aut(\W)$ on~$\Delta$. Set $$\ov W=\ov W^\m=((\W^\m)_\Delta)^{\delta^{-1}}.$$ We call $\ov W$ the {\it $m$-closure} of~$W$ and say that~$W$ is {\it $m$-closed} if~$W=\ov W$. Each cellular algebra is certainly 1-closed. The following proposition describes the relationship between the $m$-closures for $m\ge 1$ and the Schurian closure $\sch(W)=\Z(\aut(W))$ of a cellular algebra~$W$ and shows that in a sense $\ov W$ can be regarded as an $m$th approximation of $\sch(W)$. \begin{proposition}[\cite{EKP}, Proposition 3.3] \label{clopro} For each cellular algebra $W$ on $n$ points the following statements hold: \nmrt \item[{\rm (1)}] $\aut(\ov W^\m)=\aut(W)$ for all $m\geq 1$; \item[{\rm (2)}] $W=\ov W^{(1)}\leq\ldots\leq \ov W^{(n)}=\ldots=\sch(W)$; \item[{\rm (3)}] $\ov{(\ov W^\m)}^{(l)}=\ov W^\m$ for all $l\in [m]$.\bull \enmrt \end{proposition} The following statement gives in fact an equivalent definition of the $m$-extended algebra and hence of the $m$-closure. \thrm \label{tpea1} Let $W\leq\Mat_V$ be a cellular algebra. Then $\W=[W^m,I_\Delta]$. \ethrm \proof We will prove the following equality: \qtn \label{e1s2} \Z_m(V)= [\Z_1(V)^m,I_\Delta]. \eqtn Then since obviously $W^m\geq\Z_1(V)^m$, we will have $$\W=[W^m,\Z_m(V)]=[W^m,\Z_1(V)^m,I_\Delta]=[W^m,I_\Delta].$$ To prove (\ref{e1s2}) it suffices to check that any 2-orbit $R$ of the coordinatewise action of~$\sym(V)$ on~$V^m$ is a union of the basis relations of the algebra $[\Z_1(V)^m,I_\Delta]$. It is easy to see that the set of all of these 2-orbits is in 1-1 correspondence with the set of all equivalence relations~$E$ on $[2m]$ having at most~$n$ classes so that \qtn \label{nstar} R=R(E)=\{(\bar u,\bar v)\in V^m\times V^m:\ (\bar u\cdot\bar v)_i= (\bar u\cdot\bar v)_j\ \Leftrightarrow\ (i,j)\in E\} \eqtn where $\bar u\cdot\bar v\in V^{2m}$ is the composition of~$\bar u$ and~$\bar v$. Any $R(E)$ can be expressed with the help of set-theoretic operations by the sets \qtn \label{nnstar} R(S)=\{(\bar u,\bar v):\ i,j\in S\ \Rightarrow\ (\bar u\cdot\bar v)_i=(\bar u\cdot\bar v)_j\} \eqtn with nonempty $S\subset[2m]$. Set $A(S)=\big(\bigotimes_{i=1}^mA^{(0)}_i\big) I_\Delta\big(\bigotimes_{i=1}^mA^{(1)}_i\big)$ where $A^{(l)}_i$ coincides with $I_V$ or $J_V$ depending on whether $lm+i$ belongs or does not belong to $S\cap[1+lm,m+lm]$, $l=0,1$. Then a straightforward check shows that $A(S)$ equals the adjacency matrix of the relation $R(S)$. So the latter matrix belongs to the right side of~(\ref{e1s2}).\bull \eSuSS \label{mvcon} In this subsection we prove a theorem which is needed for Corollary~\ref{ucoro}. Under a {\it colored graph} $\Gamma$ on~$V$ we mean a pair~$(V,c)$ where~$c=c_\Gamma$ is a mapping from~$V\times V$ to the set of positive integers. The number~$c(u,v)$ is called the~{\it color} of a pair~$(u,v)$. The following definition goes back to~\cite{HH}. A colored graph~$\Gamma$ is called satisfying the~{\it $m$-vertex condition} if for each colored graph~$\K$ on~$m$ vertices with designated pair of vertices~$(x,y)$, the number of embeddings of~$\K$ as induced subgraph of~$\Gamma$ such that~$(x,y)$ is mapped to~$(u,v)$, depends only on the color of the pair~$(u,v)$. A detailed information about this notion can be found in~\cite[p.70]{FKM}. We say that a colored graph~$\Gamma$ is associated with a cellular algebra~$W$ if the color classes of~$\Gamma$ coincide with the basis relations of~$W$. In fact, the graph~$\Gamma$ is nothing else than the coherent configuration (with labeling) underlying~$W$. \thrm \label{thrd} A colored graph associated with an $m$-closed cellular algebra satisfies the $m$-vertex condition. \ethrm \proof First we prove the following statement. \lmm \label{lmzero} Let~$W$ be a cellular algebra on~$V$ and~$X$ be a cell of its $m$-extended algebra. Then the set $R_{i,j}(X)=\{(v_i,v_j):\ \ov v\in X\}$ is a basis relation of the algebra~$\ov W$ for all~$i,j\in[m]$. \elmm \proof It follows from statement~(2) of Proposition~3.6 of~\cite{EKP} that~$R_{i,j}(X)\subset R$ for some~$R\in\R(\ov W)$. On the other hand, by statement~(1) of the same proposition the set~$X_R=\{(u,\ldots,u,v)\in V^m:\ (u,v)\in R\}$ is a cell of~$\W$. So the number of 1's in any row of the adjacency matrix of the relation~$\{(\ov u,\ov v)\in X_R\times X:\ u_1=v_i,u_m=v_j\}$ is the same (this relation is obviously a union of basis ones). By the choice of~$R$ the last number is not zero. Thus~$R_{i,j}(X)=R$.\bull Let now~$\Gamma$ be a graph associated with an $m$-closed algebra~$W\le\Mat_V$ and~$\K$ be an arbitrary colored graph on~$[m]$ with designated pair of vertices~$(x,y)$. Let~$u,v\in V$ and $\ov u=u^\delta$, $\ov v=v^\delta$. It is easy to see that the number of embeddings of~$\K$ as induced subgraph of~$\Gamma$ such that~$(x,y)$ is mapped to~$(u,v)$ equals the cardinality of the set \qtn \label{lll1} \{\ov w\in V^m:\ w_x=u,\ w_y=v,\ c_{\Gamma}(w_i,w_j)=c_\K(i,j),\ i,j\in[m]\}. \eqtn Since~$\ov W=W$, by Lemma~\ref{lmzero} the set~$X=\{\ov w:\ c_{\Gamma}(w_i,w_j)=c_\K(i,j),\ i,j\in[m]\}$ is a cellular set of~$\W$ and depends only on~$c_{\Gamma}(u,v)$, i.e. on the basis relation~$R$ of~$W$ such that~$(u,v)\in R$. So the set~(\ref{lll1}) coincides with \qtn \label{lll2} \{\ov w\in V^m:\ (\ov u,\ov w)\in R_1,\ (\ov w,\ov v)\in R_2,\ \ov w\in X\} \eqtn where $R_1$ (resp.~$R_2$) is the binary relation on~$V^m$ defined by the equality of the first and $x$th (resp. $y$th and first) coordinates. However the cardinality of the set~(\ref{lll2}) equals the sum of the structure constants~$c_{S,T}^{R_0}$ of~$\W$ where~$R_0=R^\delta$, and $S$ and~$T$ run over the sets of basis relations of~$\W$ contained in~$(\Delta\times X)\cap R_1$ and~$(X\times\Delta)\cap R_2$ respectively. Since the last number depends only on~$R$, we are done.\bull \rmrk In fact, it can be proved that the graph of Theorem~\ref{lmzero} satisfies the $3m$-vertex condition. However, the proof of this statement is out of the scope of this paper. \ermrk \section{Weak isomorphisms and their extensions} \label{wkis} \SuSS Along with the notion of a strong isomorphism we consider for cellular algebras that of a weak one. Namely, cellular algebras $W$ on $V$ and $W'$ on $V'$ are called {\it weakly isomorphic} if there exists an algebra isomorphism $\varphi:W\to W'$ such that $$\varphi(A\circ B)=\varphi(A)\circ \varphi(B)\quad\mbox{for all}\quad A,B\in W.$$ Any such~$\varphi$ is called a {\it weak isomorphism} from $W$ to~$W'$. The set of all of them is denoted by $\isow(W,W')$. If $W=W'$ we write $\isow(W)$ instead of $\isow(W,W)$. Clearly, $\isow(W)$ forms a group which is isomorphic to a subgroup of $\sym(\R(W))$. We note that each strong isomorphism from~$W$ to~$W'$ induces in a natural way a weak isomorphism between these algebras. The following statement establishes the simplest properties of weak isomorphisms. \lmm \label{isowpr} Let $W\leq\Mat_V$, $W'\leq\Mat_{V'}$ be cellular algebras and $\varphi\in\isow(W,W')$ be a weak isomorphism. Then \nmrt \item[{\rm (1)}] $\varphi(\R)=\R'$ where $\R=\R(W)$ and $\R'=\R(W')$. Besides, $\varphi(R^T)=\varphi(R)^T$ for all $R\in\R$. \item[{\rm (2)}] $\varphi$ induces a natural bijection $U\mapsto U^\varphi$ from $\cel^*(W)$ onto $\cel^*(W')$ preserving cells such that $\varphi(I_U)=I_{U^\varphi}$. Moreover, $|U|=|U^\varphi|$ and, in particular, $|V|=|V'|$. \item[{\rm (3)}] $\varphi(\R_{U_1,U_2})=\R'_{U^\varphi_1,U^\varphi_2}$ for all $U_1,U_2\in\cel^*(W)$. \enmrt \elmm \proof The first part of statement (1) is trivial. The second follows from the observation that given $R\in\R$, the matrix $R^T$ is the only matrix of $\R$ whose product by $R$ is not orthogonal to $I_V$ with respect to the Hadamard multiplication. Let $U\in\cel^*(W)$. Then the equalities $I_UI_U=I_U\circ I_U=I_U$ imply that $\varphi(I_U)\varphi(I_U)=\varphi(I_U)\circ\varphi(I_U)=\varphi(I_U)$. So there exists $U'\subset V'$ such that $\varphi(I_U)=I_{U'}$. Since $I_{U'}\in W'$, we have $U'\in\cel^*(W')$. Set $U^\varphi=U'$. Since $I_V=\sum_{U\in\cel(W)}I_U$ and $\varphi(I_V)=I_{V'}$, the mapping $U\mapsto U^\varphi$ gives a bijection from $\cel(W)$ to $\cel(W')$, which proves the first part of statement~(2). Note that $\varphi(J_V)=J_{V'}$. So $\varphi(J_U)=\varphi(I_UJ_VI_U)=I_{U^\varphi}J_{V'}I_{U^\varphi}= J_{U^\varphi}$ for all $U\in\cel^*(W)$. Now the rest of statement~(2) follows from the equality $J_U^2=|U|J_U$. Statement~(3) is the consequence of the equality $\R_{U_1,U_2}=\{I_{U_1}RI_{U_2}:\ R\in\R,\ I_{U_1}RI_{U_2}\not=0\}$ and statements~(1) and (2).\bull Lemma~\ref{isowpr} implies that if $U$ is a cellular set of $W$, then any weak isomorphism $\varphi:W\to W'$ induces a weak isomorphism from $W_U$ to~$W'_{U^\varphi}$. It will be denoted by $\varphi_U$ and called the {\it restriction} of~$\varphi$ to~$U$. \eSuSS Let $\varphi:W\to W'$ be a weak isomorphism from a cellular algebra $W\leq\Mat_V$ to a cellular algebra $W'\leq\Mat_{V'}$. \dfntn \label{defwmi} We say that a weak isomorphism $\psi:\W\to\widehat{W'}$ is an $m$-extension of $\varphi$ if the following conditions are satisfied: \nmrt \label{eloc1} \item[{\rm (i)}] $\psi(I_\Delta)=I_{\Delta'}$, \item[{\rm (ii)}] $\psi(A)=\varphi^m(A)$ for all $A\in W^m$, \enmrt where $\Delta$ and $\Delta'$ are the diagonals of $V^m$ and $(V')^m$ respectively and $\varphi^m$ is the weak isomorphism from $W^m$ to $(W')^m$ induced by $\varphi$. \edfntn The proof of Theorem~\ref{tpea1} implies that~$\psi$ takes a basis matrix of~$\Z_m(V)$ to the corresponding basis matrix of~$\Z_m(V')$ (i.e. with the same defining equivalence relation~$E$ on~$[2m]$, see (\ref{nstar})). It follows from~(ii) that any 1-extension of~$\varphi$ coincides with~$\varphi$. \lmm \label{eun} Let $\psi$ be an $m$-extension of a weak isomorphism $\varphi:W\to W'$. Then \nmrt \tm{1} $\psi$ is uniquely determined by $\varphi$. \tm{2} $\varphi$ has an $l$-extension for all~$l\in[m]$. \enmrt \elmm \proof The first statement immediately follows from Theorem~\ref{tpea1} whereas the second one is the consequence of statement~(2) of Lemma~\ref{wisoea}.\bull The weak isomorphism $\psi:\W\to\WP$ (uniquely determined by~$\varphi$ according to Lemma~\ref{eun}) will be denoted below by~$\widehat\varphi$. \eSuSS \label{wimdef} Now we are ready to introduce the central notion of the paper. \dfntn A weak isomorphism $\varphi$ is called an $m$-isomorphism if there exists an $m$-extension of $\varphi$. \edfntn Obviously, the inverse of an $m$-isomorphism as well as the composition of $m$-isomorphisms is also an $m$-isomorphism. The set of all $m$-iso\-mor\-phisms from $W$ to $W'$ will be denoted by $\isow_m(W,W')$. It follows from statement~(2) of Lemma~\ref{eun} that \qtn \label{e1pea2} \isow_l(W,W')\supset\isow_m(W,W'),\quad l\in[m]. \eqtn Obviously, $\isow_1(W,W')=\isow(W,W')$. We note that given $g\in\iso(W,W')$ its $m$-fold Cartesian product~$g^m$ belongs to $\iso(W^m,(W')^m)$ and takes~$I_\Delta$ to~$I_{\Delta'}$. So $g^m$ belongs to $\iso(\W,\WP)$ and the weak isomorphism from~$\W$ to~$\WP$ induced by it is the $m$-extension of the weak isomorphism induced by~$g$. Thus any weak isomorphism induced by a strong isomorphism (the set of all of them will be denoted by $\isow_\infty(W,W')$) is an $m$-isomorphism for all $m$. The following statement shows that the converse statement is also true. \thrm \label{n2star} $\isow_m(W,W')=\isow_\infty(W,W')$ for all $m\geq n$. \ethrm \proof Let $\varphi\in\isow_m(W,W')$ where $m\ge n$. Choose $\ov v=(v_1,\ldots,v_m)\in V^m$ such that $V=\{v_1,\ldots,v_n\}$ and denote by~$U$ the cell of~$\W$ containing~$\ov v$. Since~$U$ is contained in an orbit of~$\sym(V)$ acting on~$V^m$, the last equality holds also for all points of~$U$ and $|\R(\W_U)|=|U|$, i.e. $\W_U$ is the centralizer algebra of a regular permutation group. Hence by Lemma~\ref{isowpr} so is the algebra~$\WP_{U'}$ where $U'=U^{\wh\varphi}$. It is easy to see that any weak isomorphism of such algebras is induced by a strong isomorphism. So there exists a bijection $h:U\to U'$ inducing $\wh\varphi_U$: \qtn \label{bboxx} \wh\varphi(A)=A^h,\quad A\in\W_U. \eqtn Since $\wh\varphi$ takes a basis matrix of~$\Z_m(V)$ to the corresponding basis matrix of~$\Z_m(V')$ (i.e. with the same defining equivalence relation~$E$ on~$[2m]$, see~(\ref{nstar})), there exists a uniquely determined bijection $g:V\to V'$ such that \qtn \label{bstx} \ov v^h=(v_1^g,\ldots,v_m^g). \eqtn %for all $\ov u=(u_1,\ldots,u_m)\in U$. To complete the proof it suffices to check that $(\varphi(R))_{v_i^g,v_j^g}=R_{v_i,v_j}$ for all $R\in\R(W)$ and $i,j\in[n]$. Denote by~$A_i$ (resp.~$A'_i$) the adjacency matrix in~$\Mat_{V^m}$ (resp.~$\Mat_{(V')^m}$) of the relation~(\ref{nnstar}) with $S=\{i\}\cup[m+1,2m]$. Then $$(\varphi(R))_{v_i^g,v_j^g}= (A'_i\varphi(R)^{\delta'}{A'_j}^T)_{\ov v^h,\ov v^h}= (\wh\varphi(A_i)\wh\varphi(R^\delta)\wh\varphi(A_j)^T)_{\ov v^h,\ov v^h}= (A_iR^\delta A_j^T)_{\ov v,\ov v}= R_{v_i,v_j}$$ where $\delta$ and $\delta'$ are the diagonal inclusions of~$V$ into~$V^m$ and~$V'$ into~$(V')^m$. (We made use of~(\ref{bstx}), (\ref{bboxx}) and the fact that $\wh\varphi$ is the $m$-extension of~$\varphi$.)\bull \eSuSS It seems difficult to verify that a given weak isomorphism is actually an $m$-isomorphism. However, we can give a sufficient condition for this. To formulate it let us denote by $\cel^*_k(W)$ the set of all cellular sets of $W$ containing at most $k$ cells. We will also make use of the obvious inclusion $\wh{W_U}\leq\W_{U^m}$ where $U\in\cel^*(W)$ and~$\wh{W_U}$ is the $m$-extended algebra of~$W_U$. \thrm \label{th34} Let $W\leq\Mat_V, W'\leq\Mat_{V'}$ be cellular algebras and $\varphi\in\isow(W,W')$ be a weak isomorphism. Suppose also that for positive integers~$k,m$ the following conditions are satisfied: \nmrt \tm{i} For any $U\in\cel^*_k(W)$ there exist an $m$-extension of~$\varphi_U$ and a weak isomorphism $\psi_U\in\isow(\W_{U^m},\WP_{(U^\varphi)^m})$ extending it. \tm{ii} For any $U_1,U_2\in\cel^*_k(W)$ the restrictions of~$\psi_{U_1}$ and $\psi_{U_2}$ to $(U_1\cap U_2)^m$ coincide. \enmrt Then $\varphi\in\isow_m(W,W')$ whenever $k\geq 3m$. \ethrm \proof Supposing $k\geq 3m$ let us define a mapping $\psi:\R\to\R'$ where $\R=\R(\W)$ and $\R'=\R(\WP)$ as follows. Given $R\in\R$ set \qtn \label{sep21e1} \psi(R)=\psi_U(R). \eqtn where $U\in\cel^*_k(W)$ is chosen such that~$R\in\R_{U^m,U^m}$. Since~$2m\leq k$, at least one such $U$ does exist. By~(ii) the element $\psi(R)$ does not depend on the choice of~$U$. Obviously, $\psi$ is a bijection (the inverse map is given by $(\psi_U)^{-1}$). This defines a linear 1-1 mapping from $\W$ to $\WP$ for which we use the same notation $\psi$. Let $R,S\in\R$ with $RS\not=0$. Then $R,S\in\R_{U^m,U^m}$ for some $U\in\cel^*_{3m}(W)$. Since $3m\leq k$, we obtain from~(\ref{sep21e1}) and (i) that $$\psi(RS)=\psi_U(RS)=\psi_U(R)\psi_U(S)=\psi(R)\psi(S),$$ which implies that $\psi\in\isow(\W)$. It also follows from~(\ref{sep21e1}) and (i) that the restriction of $\psi$ to $U^m$ extends the $m$-extension of $\varphi_U$ for all $U\in\cel^*_k(W)$. So $\psi$ is the $m$-extension of $\varphi$.\bull In Section~\ref{nsca} it will be convenient for us to make use of a weaker version of the theorem as follows. \crllr \label{mcor} The conclusion of Theorem \ref{th34} still holds if conditions (i) and (ii) are replaced by the following conditions: \nmrt \tm{i$'$} For any $U\in\cel^*_k(W)$ there exists a bijection $h=h(U)\in\iso(W,W')$ such that $U^h=U^\varphi$ and the weak isomorphism from~$W_U$ to~$W'_{U^\varphi}$ induced by it coincides with $\varphi_U$. \tm{ii$'$} For any $U_1,U_2\in\cel^*_k(W)$ there exists a permutation $h=h(U_1,U_2)\in\aut(W)$ such that $$ (h_1)_U=h_U\,(h_2)_U$$ where~$h_1$ and~$h_2$ are the bijections associated with~$U_1$ and~$U_2$, $U=U_1\cap U_2$ and $h_U$, $(h_1)_U$ and $(h_2)_U$ are the bijections obtained from $h$, $h_1$ and $h_2$ by restriction to~$U$. \enmrt \ecrllr \proof Set $\psi_U$ to be the restriction to $U^m$ of the weak isomorphism from~$\W$ to~$\WP$ induced by the $m$-fold Cartesian product of~$h$. Then conditions (i) and (ii) follow from (i$'$) and (ii$'$) respectively.\bull \section{Proofs of Theorems \protect\ref{theorem1} and \protect\ref{theorem2}} \label{nsca} Our constructions below involve the notions of the direct sum of cellular algebras and the wreath product of a cellular algebra by a permutation group. As to the definitions see Subsection~\ref{dswp} \SuSS Let $G$ be an elementary Abelian group of order 4 and~$V_i=G$, $i\in[s]$, and consider~$G$ as acting on~$V_i$ by multiplications. Let us denote by~$\K$ the class of all cellular algebras~$W$ on the disjoint union~$V$ of~$V_i$'s such that $$W\geq\bpl\limits_{i=1}^s\Z(G,V_i),\qquad \cel(W)=\{V_i:\ i\in[s]\}.$$ For $W\in\K$ the group $\aut(W)$ is naturally identified with a subgroup of~$G^s$ the elements of which will be denoted by $(g_1,\ldots,g_s)$. Moreover, each element of~$G^s$ can be considered as a strong isomorphism of~$W$ to itself inducing the identity isomorphism of all of its homogeneous components. Below we set $\R=\R(W)$ and $\R_{i,j}=\R_{V_i,V_j}$ where $i,j\in[s]$. The following statement is straightforward from the definitions (see also~\cite{F}). \lmm \label{slem} Let $W\in\K$. Then \nmrt \tm{1} $W_{V_i}=\Z(G,V_i)$ for all $i$. \tm{2} If $i\not=j$, then $W_{V_i\cup V_j}=\Z(G_{i,j},V_i\cup V_j)$ where $G_{i,j}$ is a subgroup of~$G\times G$ of index 1, 2 or 4. Moreover, $\aut(W_{V_i\cup V_j})=G_{i,j}$ and $|\R_{i,j}|=[G\times G:G_{i,j}]$. \tm{3} If $|\R_{i,j}|=2$, then $G_{i,j}$ is of the form $$K(c_1,c_2)=\langle c_1\rangle\times\langle c_2\rangle\,\cup\ \ov{\langle c_1\rangle}\times\ov{\langle c_2\rangle}$$ where $c_1=c_1(i,j)$, $c_2=c_2(i,j)$ are uniquely determined elements of $G\setminus\{1\}$, $\langle c_l\rangle=\{1,c_l\}$ and $\ov{\langle c_l\rangle}=G\setminus\langle c_l\rangle,\ l=1,2$. Moreover, $c_1(i,j)=c_2(j,i)$ and $\R_{i,j}$ consists of the adjacency matrices of the relation $G_{i,j}$ and its complement in $V_i\times V_j$.\bull \enmrt \elmm It follows from statement (1) and Proposition 2.1 of~\cite{EPN} that $\K$ consists of algebras with simple spectrum. \eSuSS In this paper we are especially interested in the subclass $\K^*$ of the class~$\K$ consisting of all cellular algebras~$W$ such that \nmrt \tm{i} $|\R_{i,j}|\leq 2$ for all $i\not=j$. \tm{ii} Given $i\in[s]$ the elements $c_1(i,j)$ with $|\R_{i,j}|=2$ are pairwise distinct. \enmrt We associate to such an algebra a graph~$\G=\G(W)$ with vertex set $V(\G)=[s]$ and edge set $E(\G)=\{(i,j):\ |\R_{i,j}|=2\}$. Since $|\R_{i,j}|=|\R_{j,i}|$, this graph can be considered as an undirected one. We observe that \qtn \label{circle} |\R_{i,j}|=\cases{4, &if $i=j$,\cr 2, &if $(i,j)\in E(\G)$,\cr 1, &otherwise\cr } \eqtn It should be noted that each weak isomorphism of the algebras belonging~$\K^*$ induces an isomorphism of the corresponding graphs. Moreover, it is easy to see that each isomorphism of the graphs is induced by a strong isomorphism of the algebras. \lmm \label{classK} Let $\G$ be an undirected graph with $V(\G)=[s]$. Then $\G=\G(W)$ for some~$W\in\K^*$ iff the degree of any vertex of~$\G$ is at most~3. \elmm \proof Let $W\in\K^*$. It follows from (ii) and the definition of $c_1(i,j)$ that the degree of a vertex~$i$ in the graph~$\G(W)$ is at most $|G\setminus\{1\}|=3$, which proves the necessity. Conversely, let the degree of any vertex of~$\G$ be at most~3. For each $i\in[s]$ choose an injection $$f_i:\{j:\ (i,j)\in E(\G)\}\to G\setminus\{1\}$$ and denote by $W$ the linear subspace of $\Mat_V$ spanned by $\bpl_{i=1}^s\Z(G,V_i)$ and the adjacency matrices $A(i,j)$ of the relations $K(c_1,c_2)\subset V_i\times V_j$ where $c_1=c_1(i,j)=f_i(j)$, $c_2=c_2(i,j)=f_j(i)$ for all $(i,j)\in E(\G)$. Let $(i,j),(j,k)\in E(\G)$ and $i\not=k$. Then $c_2(i,j)\not=c_1(j,k)$ and so $$A(i,j)\cdot A(j,k)=J_{V_i,V_k}.$$ This implies that the linear space $W$ is closed with respect to the matrix multiplication and hence is a cellular algebra from~$\K^*$.\bull Let us study the isomorphisms of a cellular algebra $W\in\K^*$ to itself leaving any cell of~$W$ fixed. For an edge $(i,j)$ of the graph $\G=\G(W)$ set \qtn \label{nopl} g_{(i,j)}=(h_1,\ldots,h_s),\qquad h_k=\cases{c_1(i,j), &if $k=i$,\cr c_2(i,j), &if $k=j$,\cr 1, &otherwise.\cr } \eqtn Let $P=(i_0,\ldots,i_t)\in[s]^{t+1}$ be a path in the graph $\G$ from $i_0$ to $i_t$ (i.e. $(i_{l-1},i_l)\in E(\Gamma)$ for all $l\in[t]$). We define a permutation of~$V$ by \qtn \label{blacks} g_P=\prod_{l=1}^tg_{(i_{l-1},i_l)}. \eqtn Clearly, $g_P\in\iso(W,W)$ for all~$P$ (including ones with $t=0$ for which $g_P=1$) and also \qtn \label{krest} g_{P\cdot P'}=g_Pg_{P'},\quad g_{P^{-1}}=g_P^{-1} \eqtn where $P\cdot P'$ is the composition of the paths~$P$ and~$P'$ (providing that the last vertex of~$P$ coincides with the first vertex of~$P'$) and $P^{-1}$ is the reverse of~$P$. Denote by $\varphi_P$ the weak isomorphism of the algebra~$W$ to itself induced by the strong isomorphism $g_P$. Obviously, $\varphi_P$ is identical on each homogeneous component of~$W$ and $\varphi_P^2=\id_W$. \lmm \label{propgr} Let $W\in\K^*$ and $\G=\G(W)$. Then the following statements hold: \nmrt \tm{1} Let $\varphi=\varphi_{(i,j)}$ where $(i,j)\in E(\G)$. Then the action of~$\varphi$ on the set $\R_{a,b}$ is nontrivial iff $(a,b)\in E(\G)$ and $|\{a,b\}\cap\{i,j\}|=1$. \tm{2} If $P=(i_0,\ldots,i_t)$ is a closed path in the graph~$\G$ (i.e. $i_0=i_t$), then\\ $g_P\in\aut(W)$. \tm{3} If $\G$ is a 3-connected graph, then $W$ is a Schurian algebra. \enmrt \elmm \proof If $\varphi$ is not identical on $\R_{a,b}$, then obviously $(a,b)\in E(\G)$ and $\{a,b\}\cap\{i,j\}\not=\emptyset$ (see~(\ref{circle}) and~(\ref{nopl})). Further, if $\{a,b\}=\{i,j\}$, then $g_{(i,j)}$ is of the form $(c_1(a,b),c_2(a,b))$ on $V_a\cup V_b$ and consequently belongs to $\aut(W_{V_a\cup V_b})$ (see Lemma~\ref{slem}) acting trivially on $\R_{a,b}$. Conversely, let $(a,b)\in E(\G)$ and for instance $a=i$, $b\not=j$. Then $g_{(i,j)}$ is of the form $(c_1(a,j),1)$ on $V_a\cup V_b$ with $c_1(a,j)\not=c_1(a,b)$ and so can not belong to $\aut(W_{V_a\cup V_b})$. This proves statement~(1). Now, if~$P$ is a closed path in~$\G$, then by statement~(1) and formula~(\ref{krest}) the weak isomorphism $\varphi_P$ acts trivially on the set $\R$. This means that $g_P\in\aut(W)$, which proves statement~(2). To prove statement~(3) we will make use of the following property of a 3-connected graph: given an edge and a vertex nonincident to each other, there exists a cycle (a closed path without repeating vertices) passing through the edge but not through the vertex. (Indeed, the subgraph obtained by removing the vertex is 2-connected and so there is a cycle in it passing through the edge, see Corollaries~2 and~4 on pp.~168 and~169 of~\cite{B}). Given distinct $i,j\in[s]$ we define a set $S_{i,j}$ of cycles of the graph~$\G$ as follows. If $(i,j)\in E(\G)$, then $S_{i,j}$ consists of~3 elements: a cycle passing through~$i$ but not through~$j$, a cycle passing through~$j$ but not through~$i$ and a cycle passing through the edge~$(i,j)$. If $(i,j)\not\in E(\G)$, then $S_{i,j}$ consists of~4 elements: 2 cycles passing through~$i$ but not through~$j$ covering all edges incident to~$i$ and 2 cycles passing through~$j$ but not through~$i$ covering all edges incident to~$j$. It follows from~(\ref{nopl}) and~(\ref{blacks}) that the order of the group generated by all permutations $g_P$, $P\in S_{i,j}$, and even of its constituent~$H_{i,j}$ on~$V_i\cup V_j$ equals~$2^{|S_{i,j}|}$. So $$|H_{i,j}|=\cases{8, &if $(i,j)\in E(\G)$,\cr 16, &otherwise.\cr } $$ On the other hand, by statement~(2) of the lemma the group $H_{i,j}$ is a subgroup of $\aut(W_{V_i\cup V_j})$ whereas~$|\aut(W_{V_i\cup V_j}|=16/|\R_{i,j}|$ by statement~(2) of Lemma~\ref{slem}. Thus $H_{i,j}=\aut(W_{V_i\cup V_j})$ by~(\ref{circle}). Since the algebra~$W_{V_i\cup V_j}$ is obviously Schurian and each element of~$H_{i,j}$ is the restriction of an automorphism of~$W$, statement~(3) follows.\bull \rmrk In fact, if $\G$ is a connected cubic graph, then the 3-connectivity of~$\G$ is also necessary for~$W$ to be Schurian. This can be proved by using the fact that in this case the group~$\aut(W)$ is generated by the permutations~$g_P$ where~$P$ runs over all cycles of~$\G$. \ermrk \eSuSS Let $W\in\K^*$ and $a\in[s]$. Set $$\psi_a=\prod_{b\in\G(a)}\psi_{a,b}$$ where $\G=\G(W)$, $\G(a)$ is the neighbourhood of~$a$ in~$\G$ and $\psi_{a,b}$ is the weak isomorphism of the algebra~$W$ defined for $R\in\R$ by $$\psi_{a,b}(R)=\cases{J_{V_a,V_b}-R, &if $R\in\R_{a,b}$,\cr J_{V_b,V_a}-R, &if $R\in\R_{b,a}$,\cr R, &otherwise.} $$ Then $\psi_a$ is an involutory weak isomorphism of~$W$ moving~$R$ iff $R\in\R_{a,b}\cup\R_{b,a}$ with $b\in\G(a)$. These weak isomorphisms are closely related to those of the previous subsection. Namely, by statement~(1) of Lemma~\ref{propgr} we have $\varphi_{(i,j)}=\psi_i\psi_j$ for all $(i,j)\in E(\G)$. So \qtn \label{znak} \varphi_P=\psi_a\psi_b \eqtn where $P$ is any path in the graph~$\G$ from~$a$ to~$b$. \thrm \label{nexwi} Let $W\in\K^*$, $\G=\G(W)$ be a cubic graph and $a\in[s]$. Then \nmrt \item[{\rm (1)}] The weak isomorphism $\psi_a$ is not induced by a permutation of~$V$. \item[{\rm (2)}] If $\G$ is a connected graph with no separator of some cardinality $k\geq 3m$, then $\psi_a\in\isow_m(W)$. (A set $X$ is called a separator of $\G$ if any connected component of the induced subgraph $\G\setminus X$ on $[s]\setminus X$ has at most $s/2$ vertices.) \enmrt \ethrm \proof Given $\varphi\in\isow(W)$ leaving any cell of~$W$ fixed let us denote by $T(\varphi)$ (resp. $t(\varphi)$) the set of all 2-subsets $\{i,j\}$ of~$[s]$ such that $\varphi(R)\not=R$ for some $R\in\R_{i,j}\cup\R_{j,i}$ (resp. its cardinality). Then, obviously, $t(\psi_a)=3$. So to prove statement~(1) it suffices to check that \qtn \label{bubi} t(\varphi_g)\equiv 0\,(\mod 2),\quad g\in G^s \eqtn where $\varphi_g$ is the weak isomorphism of~$W$ induced by $g$ (see Subsection~\ref{nsca}.1). It is easy to see that $$|T(\varphi_{gh})|=|T(\varphi_g)|+|T(\varphi_h)|- 2|T(\varphi_g)\cap T(\varphi_h)|,\quad g,h\in G^s$$ whence $t(\varphi_{gh})=t(\varphi_g)+(\varphi_h)\,(\mod 2)$ for all $g,h$. Now (\ref{bubi}) follows from the straightforward equality $t(\varphi_g)=2$ where $g=(g_1,\ldots,g_s)$ with exactly one of $g_i$'s not equal to~$1$. To prove (2) it suffices to verify that for $\varphi=\psi_a$ conditions~(i$'$) and~(ii$'$) of Corollary~\ref{mcor} are satisfied. Let $U\in\cel_k^*(W)$. Denote by $C_U$ the vertex set of a largest connected component of the graph $\G\setminus X_U$ where $X_U$ is the subset of $[s]$ corresponding to the cells of~$W$ contained in~$U$. Choose a vertex $b=b_U\in C_U$ and a path $P=P_U$ in the graph $\G$ from~$a$ to~$b$. Then by~(\ref{znak}) and the fact that $b\not\in U$ we have $(\varphi_P)_U=(\psi_a)_U$. So the condition (i$'$) is satisfied for $h=g_P$. Let $U_1,U_2\in\cel_k^*(W)$. Set $b_i=b_{U_i}$, $C_i=C_{U_i}$, $X_i=X_{U_i}$, $P_i=P_{U_i}$ ($i=1,2$). Then $|C_i|>s/2$, since $X_i$ is not a separator of~$\G$ by the hypothesis of statement~(2). So $C_1\cap C_2\not=\emptyset$ and there exists a path $P_{1,2}$ in~$\G$ from~$b_1$ to~$b_2$ all vertices of which belong to $C_1\cup C_2$. Set $P=P_1\cdot P_{1,2}\cdot P_2^{-1}$. Then by~(\ref{krest}) and the fact that $P_{1,2}$ contains no vertices of $U=U_1\cap U_2$ we have $$(g_P)_U=(g_{P_1}g_{P_{1,2}}g_{P_2}^{-1})_U=(h_1)_U(h_2^{-1})_U$$ where $h_1=g_{P_1}$,\ $h_2=g_{P_2}$. It follows from statement (2) of Lemma~\ref{propgr} that\\ $g_P\in\aut(W)$. Thus the condition~(ii$'$) is satisfied for $h=g_P$.\bull \rmrk Let $\G(W)$ be a connected cubic graph and $\varphi_1,\varphi_2\in\isow(W)$ be weak isomorphisms leaving any cell of~$W$ fixed such that $(\varphi_1)_{V_i}=(\varphi_2)_{V_i}$ for all $i\in[s]$. Then it can be proved by the same technique that $\varphi_1\varphi_2^{-1}$ is induced by a strong isomorphism of~$W$ iff $t(\varphi_1)=t(\varphi_2)\,(\mod 2)$. \ermrk \eSuSS {\bf Proof of Theorem~\ref{theorem2}.} It follows from~\cite{LU} and~\cite{U} that for all sufficiently large ~$l$ the graph $CD(l,3)$ defined in~\cite{LU} is a connected, edge-transitive, cubic Ramanujan graph with $s_l=2\cdot 3^{l-\lfloor{{l+2}\over{4}}\rfloor+1}$ vertices. One can easily veryfy that there exists $\varepsilon'>0$ such that any cubic Ramanujan graph with $s$ vertices has no separator of cardinality $k$ for all $k\leq\varepsilon's$. By Lemma~\ref{classK} there exists a cellular algebra $W(l)\in\K^*$ on $4s_l$ points with $\G(W(l))=CD(l,3)$. So by Theorem~\ref{nexwi} there exists an $\lfloor{s_l\varepsilon'\over{3}}\rfloor$-isomorphism $\varphi(l)$ of $W(l)$ which is not induced by a strong isomorphism. According to~\cite{Wa} the graph $CD(l,3)$ being a connected edge-transitive cubic graph, is 3-connected. Thus $W(l)$ is a Schurian algebra by statement~(3) of Lemma~\ref{propgr}. Let us define a cellular algebra $W_n$ on $n$ points by $W_n=W(l)\bpl\Mat_{n-4s_l}$ where $l$ is the largest positive integer for which $4s_l\leq n$. Let~$\varphi_n$ be the weak isomorphism of~$W_n$ coinciding with $\varphi(l)$ on the first summand and identical on the second one. Then by above $W_n$ is a Schurian algebra and $\varphi_n$ is not induced by a strong isomorphism for all sufficiently large~$n$. Set $m=\lfloor{s_l\varepsilon'\over{3}}\rfloor$. Since $\varphi(l)\in\isow_m(W(l))$, Theorem~\ref{sumext} implies that $\varphi_n\in\isow_m(W_n)$. Taking into account the inequality $s_l/n\geq s_l/s_{l+1}\geq 1/12$, we conclude that $m\geq\lfloor n\varepsilon\rfloor$ where $\varepsilon=\varepsilon'/36$.\bull \eSuSS {\bf Proof of Theorem~\ref{theorem1}.} Let $W$ and $\varphi$ be the Schurian algebra on $n$ points and the $m$-isomorphism from Theorem~\ref{theorem2}. Set $W'=\WC\wr_\Psi G$ where $\WC=\{W_i\}_{i=1}^2$, $\Psi=\{\psi_{i,j}\}_{i,j=1}^{2}$, $G=\sym(2)$ with $W_1=W_2=W$ and $\psi_{1,2}=\varphi$. Then by statement~(3) of Theorem~\ref{clwr} the algebra $W'$ is $m$-closed. On the other hand, $W'$ is not Schurian by Corollary~\ref{wrschurn}. Thus for a sufficiently large even integer the required algebra is constructed. The odd case is reduced to the even one by considering the algebra $W'\bpl\Mat_1$.\bull \section{Proof of Theorem~\protect\ref{theorem3}} \label{eoss} We start with the description of the $m$-dimensional Weisfeiler-Lehman method and the Schurian polynomial approximation scheme associated with it. Below a mapping~$f$ from~$V^m$ to the set of positive integers is called a {\it coloring} of $V^m$. Any nonempty set $f^{-1}(i)\subset V^m$ is called a {\it color class} of $f$. The following algorithm was described in~\cite{CFI} (see also~\cite{EKP}). \vspace{5mm} \noindent{\bf\large $m$-dim stabilization} \vspace{3mm} \noindent {\bf Input:} a coloring $f_0$ of $V^m$. \noindent {\bf Output:} a coloring $f$ of $V^m$. \noindent {\bf Step 1.} Set $k=0$. \noindent {\bf Step 2.} For each $\bar v\in V^m$ find a formal sum $S(\bar v)=\sum_{u\in V}f_k(\bar v/u)$ where\\ $\bar v/u=(\bar v_{1,u},\ldots,\bar v_{m,u})$ with $\bar v_{i,u}=(v_1,\ldots,v_{i-1},u,v_{i+1},\ldots,v_m)$, and\\ $f_k(\bar v/u)=(f_k(\bar v_{1,u}),\ldots,f_k(\bar v_{m,u})).$ \noindent {\bf Step 3.} Find a coloring $f_{k+1}$ of $V^m$ such that $$f_{k+1}(\bar v)=f_{k+1}(\bar v')\quad\Leftrightarrow\quad (f_k(\bar v)=f_k(\bar v'),\ S(\bar v)=S(\bar v')).$$ If the numbers of color classes of~$f_k$ and~$f_{k+1}$ are different, then $k:=k+1$ and go to Step~2. Otherwise set $f=f_k$.\bull \vspace{2mm} For a cellular algebra $W$ on~$V$ with standard basis~$\R$ let us denote by~$f_0$ the coloring of~$V^m$ defined by $$f_0(\bar v)=f_0(\bar v')\quad\Leftrightarrow\quad \forall R\in\R\ \forall i,j\in[m]:\ ((v_i,v_j)\in R \quad\Leftrightarrow\quad (v'_i,v'_j)\in R)$$ and set $$\WL_1(W)=W\quad\mbox{and}\quad \WL_m(W)=[\R_f],\ m\ge 2$$ where $f$ is the coloring of~$V^m$ derived from~$f_0$ by the $m$-dim stabilization procedure and $\R_f$ is the set of the adjacency matrices of the relations $$\{(u',v')\in V\times V: \ f(u',\ldots,u',v')=f(u,\ldots,u,v)\},\quad u,v\in V.$$ Let us define $\P_m=\P_m(W)$ to be the partition of~$V^m$ into the cells of~$W$ if $m=1$, and into the color classes of~$f$ if $m\geq 2$. In the last case denote by $\P_{m,k}(W)$, $k=0,\ldots,\bar k$ the partition of $V^m$ into the classes of the coloring~$f_k$ obtained in applying the $m$-dim stabilization procedure to the coloring~$f_0$. Then \qtn \label{sstar} \P_{m,0}\leq\P_{m,1}\leq\cdots\leq\P_{m,\bar k}=\P_m \eqtn where for partitions $\P,\P'$ of~$V^m$ we write $\P\leq\P'$ if~$\P'$ is the refinement of~$\P$. \thrm \label{spcol} The partition $\P=\P_m(W)$, $m\geq 1$ satisfies the following conditions: \nmrt \tm{P1} $\P$ is normal, i.e. the set~$\pi_L^{-1}(\Delta^{(L)})$ is a union of the elements of~$\P$ for all~$L\subset M$ where $\Delta^{(L)}=\Delta^{(L)}(V)=\{(v,\ldots,v)\in V^L:\ v\in V\}$ and $\pi_L=\pi_L^M:V^M\to V^L$ is a natural projection, \tm{P2} $\P$ is invariant, i.e. $\P^g=\P$ for all $g\in\sym(M)$ where $\P^g=\{T^g:\ T\in\P\},\ g\in\sym(M)$, \tm{P3} $\P$ is regular, i.e. given $T\in\P$, $S\in\pi_L(\P)$ the number $|\pi_L^{-1}(\ov u)\cap T|$ does not depend on $\ov u\in S$ for all $L\subset M$ where $\pi_L(\P)=\{\pi_L(T):\ T\in\P\}$, \enmrt where~$M=[m]$. \ethrm \proof It follows from the definition of the coloring $f_0$ that the partition $\P_{m,0}$ satisfies conditions~(P1) and~(P2). So $\P_{m,k+1}$ and hence~$\P_m$ satisfies~(P1) by~(\ref{sstar}) and~(P2) by the definition of~$f_{k+1}$ at Step~3. Thus it suffices to check that~$\P_m$ satisfies condition~(P3) or, equivalently, the following condition: \nmrt \tm{P3$^*$} given $l\in[m-1]$ and $S\in\pi_{l+1}(\P)$, $R\in\pi_l(\P)$ the number $|(\pi_l^{l+1})^{-1}(\ov u)\cap S|$ does not depend on~$\ov u\in R$ \enmrt where $\pi_l^{l+1}=\pi_{[l]}^{[l+1]}$ and~$\pi_l=\pi_{[l]}$. For $l\in[m]$ let $\eta_l$ be the mapping defined by $$\eta_l:V^m\to V^m,\quad (v_1,\ldots,v_m)\mapsto(v_1,\ldots,v_l,v_1,\ldots,v_1).$$ \lmm \label{llemm} $T\in\P_m$ implies $\eta_l(T)\in\P_m$. \elmm \proof Using induction on $l=m,m-1,\ldots$ we assume that $T=\eta_{l+1}(T)$. Let $\ov v=(v_1,\ldots,v_m)\in T$. Then by the definition of the initial coloring~$f_0$ and formula~(\ref{sstar}) we conclude that the final color of the tuple $\ov v_{l+1,u}$ for $u=v_1$ differs from that for $u\not=v_1$ (see Step~2). So the final color of $\eta_l(\ov v)$ does not depend on the choice of $\ov v$ in the color class~$T$ due to the termination condition at Step~3. Thus $\eta_l(T)\subset T'$ for some $T'\in\P_m$. To prove the inverse inclusion we observe that $T'\subset\eta_l(V^m)$. On the other hand, given $\ov v'\in T'$ the number $|\{u\in V:\ \ov v'_{l+1,u}\in T\}|$ does not depend on $\ov v'$ and is positive since $\eta_l(T)\not=\emptyset$. Thus $T'\subset\eta_l(T)$.\bull To prove~(P3$^*$) set $S=\pi_{l+1}(T)$ and $R=\pi_l(T')$ where $T,T'\in\P_m$. By Lemma~\ref{llemm} we assume $T=\eta_{l+1}(T),T'=\eta_l(T')$. For $\ov u\in V^l$ set $\ov v=\eta_l(\ov v')$ where $\ov v'$ is any element of the set $(\pi_l^m)^{-1}(\ov u)$. Then obviously $$|(\pi_l^{l+1})^{-1}(\ov u)\cap S|=|\{u\in V:\ \ov v_{l+1,u}\in T\}|.$$ If $\ov u$ runs over $R$, then $\ov v$ runs over $T'$. Since the right side of the last equality does not depend on $\ov v\in T'$, we conclude that the left side of it does not depend on $\ov u\in R$.\bull Below given a finite set~$M$ a partition~$\P$ of~$V^M$ satisfying (P1)--(P3) will be called {\it stable}. The following statement contains the simplest properties of a stable partition to be used in proving Theorem~\ref{theorem3}. \lmm \label{prsp} Let $\P$ be a stable partition of $V^M$. Then \nmrt \tm{1} $\pi_L(\P)$ is a stable partition of $V^L$ for all $L\subset M$, \tm{2} if $M=I\times K$, then $\P$ is a stable partition of~$(V^I)^K$, \tm{3} if $M=[3]$, then $\pi_{[2]}(\P)$ is the set of basis relations of a cellular algebra on~$V$. \enmrt \elmm \proof To prove statement~(1) we observe first that the elements of~$\pi_L(\P)$ are pairwise disjoint by~(P3) and so~$\pi_L(\P)$ is a partition of~$V^L$. The obvious equality $(\pi_K^L)^{-1}(\Delta^{(K)})=\pi_L(\pi_K^{-1}(\Delta^{(K)}))$ with~$K\subset L$ implies that this partition is normal. It is also invariant since $\pi_L(T)^g=\pi_L(T^{\wt g})$ for all~$g\in\sym(L)$ where~$\wt g$ is the image of~$g$ under the natural injection of~$\sym(L)$ into~$\sym(M)$. Finally, let $S\in\pi_L(\P)$, $R\in\pi_K^L(\pi_L(\P))$, $K\subset L$, and~$\ov u\in R$. Then $$|V|^{|M\setminus L|}|(\pi_K^L)^{-1}(\ov u)\cap S|= |\pi_L^{-1}((\pi_K^L)^{-1}(\ov u)\cap S)|= |\pi_K^{-1}(\ov u)\cap\pi_L^{-1}(S)|.$$ Since~$\pi_L(\P)$ is a partition of~$V^L$, we see that $\pi_L^{-1}(S)=\bigcup_{T\in\P, T\in\pi_L^{-1}(S)}T$. So the last number equals $\sum_T|\pi_K^{-1}(\ov u)\cap T|$. Thus the regularity of~$\pi_L(\P)$ follows from the regularity of~$\P$. Let us prove statement~(2). The normality of~$\P$ as a partition of~$(V^I)^K$ follows from the equality $$(\pi_J^K)^{-1}(\Delta^{(J)}(V^I))= \bigcap_{i\in I}\pi_{\{i\}\times J}^{-1}(\Delta^{(\{i\}\times J)})$$ where $J\subset K$ and the normality of~$\P$ as a partition of~$V^M$. The invariance (resp. regularity) of~$\P$ as a partition of~$(V^I)^K$ is obtained by the specialization of~(P2) (resp.~(P3)) for~$g$ belonging to the subgroup of~$\sym(M)$ equal to the wreath product of the identity group on~$I$ and~$\sym(K)$ (resp. for~$L=I\times J$, $J\subset K$). Let us prove the third statement. Set $\R=\pi_{[2]}(\P)$. It follows from statement~(1) that $\R$ is a stable partition of $V^2$. In particular, $V^2$ and $\Delta^{([2])}(V)$ are unions of the elements of~$\R$. Besides, $\R^T=\R$ since $R^T=R^g$ for all $R\in\R$ where $g$ is the transposition belonging to $\sym(2)$. So it suffices to check that given $Q,R,S\in\R$ the number $$p(u_1,u_2;Q,R)=|\{u\in V:\ (u_1,u)\in Q,\ (u,u_2)\in R\}|$$ does not depend on the choice of $(u_1,u_2)\in S$. However, $p(u_1,u_2;Q,R)$ coincides with the sum of the numbers $|\pi^{-1}_L(\ov u)\cap T|$ where $L=[2]$, $\ov u=(u_1,u_2)\in S$ and $T$ runs over the elements of~$\P$ contained in the set $$\pi_L^{-1}(Q)\cap \pi_L^{-1}(R)^g\cap \pi_L^{-1}(S)^h$$ with $g=(1,2,3)$, $h=(2,3)$ in cyclic notation. By~(P3) these numbers do not depend on ~$\ov u$.\bull Now we are ready to prove Theorem~\ref{theorem3}. Let us compare the partitions of Cartesian powers of~$V$ associated with the Schurian polynomial approximation schemes $\{\ov W^\m\}$ and $\{\WL_m(W)\}$ where $W$ is a cellular algebra on~$V$. \thrm \label{comsch} For all cellular algebra $W$ and all $m\geq 1$ \qtn \label{triang} \P_m(W)\leq\cel(\W^\m),\qquad \R(\W^\m)\leq\pi_{2m}(\P_{3m}(W)). \eqtn (We consider the elements of $\R(\W^\m)$ as subsets of~$V^{2m}$, see proof of Theorem~\ref{tpea1}.) \ethrm \proof The first inequality was in fact proved in Proposition~4.1 of~\cite{EKP}. According to Theorem~\ref{spcol} $\P_{3m}(W)$ is a stable partition of~$V^{3m}$. So by Lemma~\ref{prsp} there exists a cellular algebra $\wh A_m(W)$ on $V^m$ whose set of basis relations coincides with $\pi_{2m}(\P_{3m}(W))$. It follows from~(P1) with $\P=\P_{3m}(W)$ that $I_{\Delta^\m}\in\wh A_m(W)$. Besides, $\R(W^m)\leq\pi_{2m}(\P_{3m,0}(W))$ by the definition of the initial coloring~$f_0$, whence $W^m\leq\wh A_m(W)$. Thus $$\W^\m\leq\wh A_m(W)$$ by Theorem~\ref{tpea1}.\bull The inclusion $\WL_m(W)\leq\ov W^\m$ was proved in Theorem 1.2 of~\cite{EKP} (in fact deduced from the first inequality of Theorem~\ref{comsch}). To prove the inclusion $\ov W^\m\leq \WL_{3m}(W)$ we observe that by Theorem~\ref{spcol} the partition~$\P_{3m}(W)$ is stable and hence $$\R(\WL_{3m}(W))=\pi_2(\P_{3m}(W))=\pi_2(\pi_{2m}(\P_{3m}(W)))= \pi_2(\R(\wh A_m))$$ where $\wh A_m=\wh A_m(W)$ is the cellular algebra on~$V^m$ defined in the proof of Theorem~\ref{comsch}. On the other hand, the stability of partition $\pi_{2m}(\P_{3m}(W))$ (see Lemma~\ref{prsp}) implies that $\pi_2(\R(\wh A_m))=\R(((\wh A_m)_\Delta)^{\delta^{-1}})$ where~$\Delta$ and~$\delta$ are defined in Subsection~3.1. So by the second inequality of Theorem~\ref{comsch} we have $$\R(\WL_{3m}(W))=\R(((\wh A_m)_\Delta)^{\delta^{-1}})\ge \R(((\W^\m)_\Delta)^{\delta^{-1}})=\R(\ov W^\m).$$ This completes the proof of Theorem~\ref{theorem3}.\bull \section{Appendix} \SuSS \label{dswp} Throughout the subsection we denote by $W_i$ (resp.$W'_i$) a cellular algebra on a set~$V_i$ (resp.$V'_i$) where $i\in[s]$. Following~\cite{W} we call the cellular algebra $$\bpl\limits_{i=1}^sW_i=[\bigcup_{i=1}^s\R(W_i)]$$ on the disjoint union~$V$ of~$V_i$'s the {\it direct sum} of~$W_i$'s. Obviously, it does not depend on the ordering of the summands. Any set~$V_i$ is a cellular set of this algebra. Any of its basis relations contained in~$V_i\times V_j$ coincides with a basis relation of~$W_i$ (for~$i=j$) or equals the direct product of a cell of~$W_i$ and a cell of~$W_j$ (for~$i\ne j$). Let~$\varphi_i\in\isow(W_i,W'_i)$ for all $i\in[s]$. Then the mapping \qtn \label{inddsum} \varphi:\bpl\limits_{i=1}^sW_i\to\bpl\limits_{i=1}^sW'_i \eqtn coinciding with~$\varphi_i$ on~$W_i$ and taking~$J_{X,Y}$ to~$J_{X',Y'}$ where $X\in\cel(W_i)$, $Y\in\cel(W_j)$, $i\ne j$, and~$X'=X^{\varphi_i}$, $Y'=Y^{\varphi_j}$, is obviously a weak isomorphism. We say that it is induced by~$\varphi_i$'s. It is easy to see that each weak isomorphism~$\varphi$ of the direct sums such that $\varphi(W_i)=W'_i$ for all~$i$ can be obtained in this way. Let $W\leq\Mat_V$ be a cellular algebra and~$\Phi\subset\isow(W)$ be a group of its weak isomorphisms. Then according to~\cite{EP} the set~$W^\Phi=\{A\in W:\ \varphi(A)=A,\ \varphi\in\Phi\}$ is a cellular algebra on~$V$. If $\Phi\subset\isow_m(W)$, then $\wh{W^\Phi}\leq\W^{\wh\Phi}$ where $\wh\Phi=\{\wh\varphi^\m:\ \varphi\in\Phi\}$. Let now $\WC=\{W_i\}_{i=1}^s$ and $\Psi=\{\psi_{i,j}\}_{i,j=1}^s$ with $\psi_{i,j}\in\isow(W_i,W_j)$ such that \qtn \label{eiso} \psi_{i,j}\,\psi_{j,k}=\psi_{i,k}, \qquad i,j,k\in[s] \eqtn It is easy to see that $\psi_{i,i}=\id_{W_i}$ and $\psi_{i,j}^{-1}=\psi_{j,i}$ for all~$i,j$. Any permutation $g\in\sym(s)$ induces~$s$ weak isomorphisms $\psi_{i,i^g}:W_i\to W_{i^g}$, $i\in[s]$, and hence by~(\ref{inddsum}) a weak isomorphism $\varphi_g:W\to W$ where $W=\bpl_{i=1}^sW_i$. Obviously, given a group $G\leq\sym(s)$ the set $\Phi(\Psi,G)=\{\varphi_g:\ g\in G\}$ is a subgroup of~$\isow(W)$. \dfntn The cellular algebra $W^\Phi$ with~$\Phi=\Phi(\Psi,G)$ is called the wreath product of the family~$\WC$ by the group~$G$ with respect to $\Psi$ and is denoted by $\WC\wr_\Psi G$~\footnote{We note that if~$G$ is transitive and~$W_i$ is homogeneous for all $i$, this is a special case of the corresponding construction of~\cite{W}.}. \edfntn The algebra $\WC\wr_\Psi G$ contains two subalgebras \qtn \label{twostar} \WC^\Psi=\{\sum_{i=1}^sA_i:\ A_i\in W_i,\ A_j=\psi_{i,j}(A_i),\ i,j\in[s]\} \eqtn and \qtn \label{onestar} \WC^G=\bigl\{\sum_{O\in\orb_2(G)}\alpha_OA_O,\ \alpha_O\in\C\bigr\},\qquad A_O=\sum_{(i,j)\in O}J_{V_i,V_j} \eqtn closed under the Hadamard multiplication and the Hermitian conjugation. It is easy to see that \qtn \label{bsqu} \WC\wr_\Psi G=[\WC^\Psi,\WC^G]. \eqtn Let $W=\WC\wr_\Psi G$ with $\WC=\{W_i\}_{i=1}^s$, $\Psi=\{\psi_{i,j}\}_{i,j=1}^s$, $W'=\WC'\wr_{\Psi'} G$ with $\WC'=\{W'_i\}_{i=1}^s$, $\Psi'=\{\psi'_{i,j}\}_{i,j=1}^s$ and~$\varphi_i\in\isow(W_i,W'_i)$ for all $i$. If \qtn \label{WRI} \varphi_i\,\psi'_{i,j}=\psi_{i,j}\,\varphi_j,\quad i,j\in[s], \eqtn then $\varphi(\WC^\Psi)=(\WC')^{\Psi'}$ and $\varphi(\WC^G)=(\WC')^G$ where~$\varphi$ is the weak isomorphism~(\ref{inddsum}). By~(\ref{bsqu}) this defines by restriction a weak isomorphism from~$W$ to~$W'$ such that \begin{equation} \label{wicond} \varphi(A_O)=A'_O\quad\mbox{for all}\quad O\in\orb_2(G). \end{equation} In this case we say that it is induced by~$\varphi_i$'s. Conversely, any~$\varphi\in\isow(W,W')$ for which~(\ref{wicond}) is satisfied can be obtained in this way with uniquely determined~$\varphi_i$'s. According to \cite{W} the tensor product $\bigotimes_{i=1}^sW_i$ can be considered as a cellular algebra on the set~$\prod_{i=1}^sV_i$. The basis matrices (resp. cells) of this algebra are exactly the Kronecker (resp. direct) products of the basis matrices (resp. cells) of~$W_i$'s. \eSuSS \label{ss32} Here given a cellular algebra $W\le\Mat_V$ we define and study an auxiliary cellular algebra $\W^*$ on the set $V^*=\bigcup_{I\subset[m]}V^I$. Below we denote by $\Mat_{V_1,V_2}$ the linear space of all complex matrices the rows and columns of which are indexed by the elements of sets~$V_1$ and $V_2$ respectively. The tensor product $\Mat_{V_1,V_2}\otimes\Mat_{V'_1,V'_2}$ is naturally identified with $\Mat_{V_1\times V'_1,V_2\times V'_2}$. Given~$I,J\subset[m]$ let~$D_{I,J}=D_{I,J}(V)$ denotes the adjacency matrix of the binary relation $\{(\ov u,\ov v)\in V^I\times V^J:\ u_i=v_i,\ i\in I\cap J\}$. Set~$D_I=D_I(V)=D_{I,[m]}(V)$ and~$d_I=d_I(V)=|V|^{m-|I|}$. Then \qtn \label{staro} D_{I,I}=I_{V^I},\quad (D_{I,J})^T=D_{J,I},\quad d_{I\cup J}D_{I,J}=D_ID_J^T. \eqtn Besides, \qtn \label{stard} D_I^TD_I=E_I,\quad D_IE_I=d_ID_I,\quad E_I^2=d_IE_I \eqtn where~$E_I$ is the adjacancy matrix of the relation~$\{(\ov u,\ov v):\ V^m\times V^m:\ u_i=v_i,\ i\in I\}$. We also observe that ~$E_I\in\Z_m(V)$. For~$I,J\subset[m]$ set $$\W_{I,J}=D_I\W D_J^T,\qquad\RR_{I,J}=\{R_{I,J}:\ R_{I,J}=(d_{I,J}^R)^{-1}D_IRD_J^T,\ R\in\RR\}$$ where $\RR=\R(\W)$ and $d_{I,J}^R$ is the coefficient at~$R$ in the decomposition of the matrix~$E_IRE_J$ with respect to~$\RR$. Both of the sets are contained in~$\Mat_{V^I,V^J}$. Set $$\W^*=\sum_{I,J\subset[m]}\W_{I,J},\qquad \RR^*=\bigcup_{I,J\subset[m]}\RR_{I,J}(W).$$ Obviously, the sum is meant to be direct and the union is meant to be disjoint. \lmm \label{auex} The following statements hold: \nmrt \tm{1} The linear space $\W^*$ is a cellular algebra on $V^*$ and the set $\RR^*$ is its standard basis. \tm{2} $\W^*=[\W,\{D_I\}_{I\subset[m]}]$. \tm{3} For each $I\subset[m]$ the set $V^I$ is a cellular set of $\W^*$. Moreover, $(\W^*)_{V^l}\ge\W^{(l)}$ for all $l\in[m]$ and also $(\W^*)_{V^m}=\W$, $(\W^*)_V=\ov W$. \tm{4} Let $I,J\subset[m]$ and $\{I_k\}_{k=1}^s$, $\{J_k\}_{k=1}^s$ be partitions of~$I$ and~$J$ (with some of $I_k,J_k$ possibly empty). Then\ \ $\bigotimes_{k=1}^s\W_{I_k,J_k}\subset\W_{I,J}.$ \enmrt \elmm \proof Let us show that any matrix $A=D_IRD_J^T$, $R\in\RR$, is a $d_{I,J}^R$-multiple of a \{0,1\}-matrix. It is easy to see that given~$(\ov u,\ov v)\in V^I\times V^J$ the number~$A_{\ov u,\ov v}$ equals any $(\ov u',\ov v')$-element of the matrix~$B=E_IRE_J$ with $(D_I)_{\ov u,\ov u'}>0$, $(D_J)_{\ov v,\ov v'}>0$. If $A_{\ov u,\ov v}\ne 0$, then $\ov u',\ov v'$ can be chosen so that in addition~$R_{\ov u',\ov v'}>0$. So $A_{\ov u,\ov v}=B_{\ov u',\ov v'}=d_{I,J}^R$ by the definition of~$d_{I,J}^R$. Thus~$\RR_{I,J}$ consists of \{0,1\}-matrices. Moreover, any two of them %matrices of~$\RR_{I,J}$ are orthogonal with respect to the Hadamard multiplication or coincide. Indeed, let~$R_{I,J}\circ S_{I,J}\ne 0$ where $R,S\in\RR$. Then $S\circ(E_IRE_J)\ne 0$ and $R\circ(E_ISE_J)\ne 0$. Since the matrices $E_IRE_J,E_ISE_J$ belong to~$\W$ and are multiples of \{0,1\}-matrices, they (and hence also $D_IRD_J,D_ISD_J$) coincide up to a scalar factor. It follows from above that the set~$\RR^*$ consists of \{0,1\}-matrices summing up to~$J_{V^*}$. Besides, it is easy to see that it is closed under transposition and linearly spans~$\W^*$. Since $\W_{I,J}\W_{J,K}\subset\W_{I,K}$ (see~(\ref{stard})), statement~(1) follows. Statement~(2) is the consequence of the definition of~$\W^*$, statement~(1) and the fact that~$D_I\in\W_{I,[m]}$ for all~$I\subset[m]$. To prove statement (3) it suffices to check that $(\W^*)_{V^l}\ge\W^{(l)}$. To do this we observe that \qtn \label{laseqq} I_{\Delta^{(l)}}=D_{[l]}I_{\Delta^\m}D_{[l]},\quad R_1\otimes\ldots\otimes R_l=d_{[l]}^{-1} D_{[l]}(R_1\otimes\ldots\otimes R_l\otimes I_V\otimes\ldots\otimes I_V)D_{[l]} \eqtn where $R_i\in\R(W)$ for all $i\in[l]$. Thus we are done by Theorem~\ref{tpea1} (with $m=l$). Let us prove statement~(4). First we observe that for all~$l\in[s]$ $$D_{I,I_l}A_lD_{J_l,J}=\bigotimes_{k=1}^s C_k^{(l)},\qquad A_l\in\Mat_{V^{I_l},V^{J_l}}$$ where $C_k^{(l)}$ is the all-one matrix of $\Mat_{V^{I_k},V^{J_k}}$ if $k\not=l$, and $C_l^{(l)}=A_l$. Since the Hadamard multiplication in $\Mat_{V^I,V^J}=\bigotimes_{k=1}^s\Mat_{V^{I_k},V^{J_k}}$ can be done factorwise, we come to the equality \qtn \label{sep20} (D_{I,I_1}A_1D_{J_1,J}^T)\circ\cdots\circ(D_{I,I_s}A_sD_{J_s,J}^T)= \bigotimes_{k=1}^s A_k. \eqtn Thus, if $A_k\in\W_{I_k,J_k}$ for all $k$, then by statement~(1) each Hadamard factor in the left side of~(\ref{sep20}) (and hence the whole product) belongs to~$\W_{I,J}$.\bull We complete the subsection by defining and studying some natural weak isomorphisms of our auxiliary algebras. \lmm \label{wisoea} Let~$\varphi\in\isow_m(W,W')$ and~$\psi=\wh\varphi$. Then \nmrt \tm{1} There exists a uniquely determined weak isomorphism $\psi^*:\W^*\to\WP^*$ such that~$(\psi^*)_{V^m}=\psi$ and $\psi^*(D_I)=D'_I$ for all~$I\subset[m]$. \tm{2} The mapping $(\psi^*)_{V^l}$ induces by restriction an $l$-extension of~$\varphi$ for all $l\in[m]$. In particular, $(\psi^*)_V:\ov W\to\ov{W'}$ extends~$\varphi$. \enmrt \elmm \proof To prove statement~(1) set $$\psi^*(A)=(d_Id_J)^{-1}D'_I\psi(D_I^TAD_J)(D'_J)^T, \qquad A\in\W_{I,J}.$$ It immediately follows from~(\ref{staro}) and~(\ref{stard}) that $\psi^*(A)=\psi(A)$ for all~$A$ from~$\W=(\W^*)_{V^m}$ and also $\psi^*(D_I)=D'_I$ for all~$I\subset[m]$. Moreover, making use of the same properties of the matrices~$D_I$ and~$E_I$ we have for $A\in\W_{I,J}$, $B\in\W_{J.K}$: $$d_Id_K\psi^*(AB)=D'_I\psi(D_I^TABD_K)(D'_K)^T= d_J^{-1}D'_I\psi(D_I^TAD_J)\psi(D_J^TBD_K)(D'_K)^T=$$ $$d_J^{-3}D'_I\psi(D_I^TAD_JE_J)\psi(E_JD_J^TBD_K)(D'_K)^T= d_J^{-2}D'_I\psi(D_I^TAD_J)E'_J\psi(D_J^TBD_K)(D'_K)^T=$$ $$d_J^{-2}D'_I\psi(D_I^TAD_J)(D'_J)^TD'_J\psi(D_J^TBD_K)(D'_K)^T= d_Id_K\psi^*(A)\psi^*(B).$$ This shows that~$\psi^*$ is a matrix algebra isomorphism. In particular, $$\psi^*(R_{I,J})=(d_{I,J}^R)^{-1}\psi^*(D_I)\psi(R)\psi^*(D_J^T)= (d_{I,J}^{\psi(R)})^{-1}D'_I\psi(R)(D'_J)^T=\psi(R)_{I,J}$$ for all~$R\in\RR$ and~$I,J\subset[m]$. Thus~$\psi^*$ preserves the Hadamard multiplication and hence is a weak isomorphism. Since the uniqueness of~$\psi^*$ follows from statement~(2) of Lemma~\ref{auex}, we are done. The second statement of the lemma follows from the first one, statement~(3) of Lemma~\ref{auex} and formula~(\ref{laseqq}).\bull The isomorphism~$(\psi^*)_V$ will be denoted by~$\ov\varphi$ and called the $m$-closure of~$\varphi$. \eSuSS It is clear that the direct sum is Schurian iff so is any of its summands. In this subsection we generalize this observation to $m$-closed algebras. To do this we need to study the $m$-extended algebra of the direct sum. \thrm \label{thot} Let $W=\bpl_{k=1}^sW_k$. Then the set~$V^*$ is a cellular set of the algebra~$\bigotimes_{k=1}^s\wh{W_k}^*$ and \qtn \label{hous} \W^*=(\bigotimes_{k=1}^s\wh{W_k}^*)_{V^*}. \eqtn \ethrm \proof It is easy to see that given $I\subset[m]$ we have $V^I=\bigcup_\I V^\I$ where~$\I=\{I_k\}_{k=1}^s$ runs over all ordered partitions of the set~$I$ into~$s$ classes (possibly empty) and $V^{\I}=\prod_{k=1}^sV_k^{I_k}$. Since~$V_k^{I_k}$ is a cellular set of the algebra~$\wh{W_k}^*$ the first part of the theorem follows. Further, the right side of~(\ref{hous}) denoted by~$W'$ below, coincides with the direct sum over all~$I,J\subset[m]$ and all partitions $\{I_k\}_{k=1}^s$ and $\{J_k\}_{k=1}^s$ of~$I$ an~$J$ of the linear spaces $\bigotimes_{k=1}^s(\wh{W_k})_{I_k,J_k}$. Since $(\wh{W_k})_{I_k,J_k}\subset\W_{I_k,J_k}$ for all~$k$, we conclude by statement~(4) of Lemma~\ref{auex} that $W'$ is a subalgebra of~$\W^*$ . To prove the inverse inclusion it suffices to check by statement~(2) of Lemma~\ref{auex} and Theorem~\ref{tpea1} that~$W'$ contains the algebra~$W^m$ and the matrices~$I_\Delta$ and~$D_I$, $I\in[m]$. Let us prove that $I_\Delta\in W'$. Since $I_\Delta=\sum_{k=1}^sI_{\Delta_k}$ where $\Delta_k=\Delta^\m(V_k)$, we need only to check that $I_{\Delta_k}\in W'$ for all~$k$. Given $k\in[s]$ let us define a partition $\{I_l\}$ of~$[m]$ so that $I_l=\emptyset$ for $l\not=k$ and $I_k=[m]$. Then, obviously, $$I_{\Delta_k}\in{\wh{W_k}}=\bigotimes_{l=1}^s(\wh{W_l})_{I_l,I_l}\subset W'.$$ Further, given $I\subset[m]$ it is easy to see that $$D_I=\sum_{\{I_k\},\{J_k\}}\bigotimes_{k=1}^sD_{I_k,J_k}(V_k)$$ where the sum is taken over all partitions of the sets~$I$ and~$[m]$ respectively with $I_k\subset J_k$ for all~$k\in[s]$. Since $D_{I_k,J_k}(V_k)=d_{J_k}(V_k)^{-1}D_{I_k}(V_k)D_{J_k}(V_k)^T$ (see~(\ref{staro})) and $D_{I_k}(V_k)$, $D_{J_k}(V_k)$ belong to $\wh{W_k}^*$ by statement~(2) of Lemma~\ref{auex}, we conclude that~$D_I\in W'$. Let us prove now that~$W^m\subset W'$. It follows from the definition of the direct sum that~$W$ coincides with the cellular closure of the sets~$\R(W_k)$, $k\in[s]$, and the matrices~$J_{V_k,V_l}$, $k,l\in[s]$. So it suffices to prove that~$W'$ contains any matrix $A=\bigotimes_{i=1}^mA_i$ with~$A_i\in\R(W_k)$ for some~$k$ or $A_i=J_{V_k,V_l}=J_{V_k,\emptyset}\otimes J_{\emptyset,V_l}$ for~$k\ne l$. Let us define partitions~$\{I_k\}$ and~$\{J_k\}$ of~$[m]$ by $$I_k=\{i\in[m]:\ A_i\in\Mat_{V_k,V}\},\quad J_k=\{i\in[m]:\ A_i\in\Mat_{V,V_k}\}. $$ Then $$A=\bigotimes_{k=1}^sA^\k \quad\mbox{with}\quad A^\k=A^{(k,0)}\otimes A^{(k,1)}\otimes A^{(k,2)} $$ where $A^{(k,0)}=\bigotimes_{i\in I_k\cap J_k}A_i$, $A^{(k,1)}=D_{I_k\setminus J_k,\emptyset}(V_k)$, $A^{(k,2)}=D_{\emptyset,J_k\setminus I_k}(V_k)$. We only need to prove that~$A^\k\in(\wh{W_k})_{I_k,J_k}$ for all~$k\in[s]$. However, this follows from statement~(4) of Lemma~\ref{auex} applied to the partitions of~$I_k$ and~$J_k$ with 3 classes~$I_{k,0}=J_{k,0}=I_k\cap J_k$, $I_{k,1}=I_k\setminus J_k$, $I_{k,2}=J_{k,1}=\emptyset$ and $J_{k,2}=J_k\setminus I_k$.\bull Theorem~\ref{thot} enables us to obtain the following decomposition of the $m$-extended algebra of the direct sum: \qtn \label{ccircl} \W=\sum_{\I,\J}\W_{\I,\J},\qquad\W_{\I,\J}=\bigotimes_{k=1}^s(\wh{W_k})_{I_k,J_k} \eqtn where $\I=\{I_k\}_{k=1}^s$ and $\J=\{J_k\}_{k=1}^s$ run over all ordered partitions of the set~$[m]$ into~$s$ classes (possibly empty). According to this each basis matrix of~$\W$ can uniquely be represented as the Kronecker product over~$k\in[s]$ of the ``basis'' matrices of~$(\wh{W_k})_{I_k,J_k}$. For each~$k\in[s]$ let us define the partition~$\I^\k=\{I_l^\k\}_{l=1}^s$ of the set~$[m]$ by~$I_l^\k=\emptyset$, if~$l\ne k$, and~$I_k^\k=[m]$. Then it is easy to see that $V^{\I^\k}=V_k^m$, $\W_{\I^\k,\I^\k}=\wh{W_k}$ and $\W_{\I^\k,\I^{(l)}}$ for $k\ne l$ coincides with the linear span of the matrices $J_{X,Y}$ where $X\in\cel(\wh{W_k})$, $Y\in\cel(\wh{W_l})$. Thus, restricting~$\W$ to the union of~$V^{\I^\k}$, $k\in[s]$, we come by~(\ref{ccircl}) to the following statement. \thrm \label{eads} Let $W=\bpl_{k=1}^sW_k$. Then \nmrt \tm{1} The set $U=\bigcup_{k=1}^sV^m_k$ is a cellular set of the algebra~$\W$ and $\W_U=\bpl_{k=1}^s\wh{W_k}$. \tm{2} $\ov W=\bpl_{k=1}^s\ov W_k$. \tm{3} The algebra~$W$ is $m$-closed iff so is~$W_k$ for all $k$.\bull \enmrt \ethrm Another consequence of Theorem~\ref{thot} concerns the $m$-extensions of weak isomorphisms between direct sums. \thrm \label{sumext} Let $W=\bpl_{k=1}^sW_k$, $W'=\bpl_{k=1}^sW'_k$ and $\varphi:W\to W'$ be the weak isomorphism induced by weak isomorphisms $\varphi_k:W_k\to W'_k$, $k\in[s]$. Then $\varphi\in\isow_m(W,W')$ iff $\varphi_k\in\isow_m(W_k, W'_k)$ for all~$k$. \ethrm \proof The necessity is obvious. Conversely, let $\varphi_k\in\isow_m(W_k, W'_k)$ for all~$k$. It follows from Theorem~\ref{thot} and Lemma~\ref{auex} that the algebras~$\W$ and~$\WP$ coincide with the restrictions to~$V^m$ and to~$(V')^m$ of the tensor products $\bigotimes_{k=1}^s\wh{W_k}^*$ and $\bigotimes_{k=1}^s\wh{W'_k}^*$ respectively. By statement~(1) of Lemma~\ref{wisoea} the isomorphism $\wh{\varphi_k}$ is extended to the weak isomorphism $\wh{\varphi_k}^*:\wh{W_k}^*\to \wh{W'_k}^*$ taking~$(V_k)^I$ to~$(V'_k)^I$ for all~$I\subset[m]$. So the restriction to~$V^m$ of the weak isomorphism $\bigotimes_{k=1}^s\wh{\varphi_k}^*$ is a correctly defined weak isomorphism from $\W$ to $\WP$ being in fact the $m$-extension of~$\varphi$.\bull \eSuSS Here we use the results of the previous subsection to give a sufficient condition for the wreath product~$\WC\wr_\Psi G$ to be $m$-closed. We note that if $\psi_{i,j}\in\isow_m(W_i,W_j)$ for all~$i,j$, then by Theorem~\ref{sumext} $\varphi_g\in\isow_m(W)$ for all $g\in\sym(s)$ where~$W=\bpl_{i=1}^sW_i$. In this case we can consider the group $\wh{\Phi(\Psi,G)}=\{\wh{\varphi_g}:\ g\in G\}\subset\isow(\W)$. \thrm \label{clwr} Let $\WC\wr_\Psi G$ be the wreath product of $\WC=\{W_i\}_{i=1}^s$ by $G\leq\sym(s)$ with respect to $\Psi=\{\psi_{i,j}\}_{i,j=1}^s$. Suppose that $\psi_{i,j}\in\isow_m(W_i,W_j)$ for all~$i,j$. Then \nmrt \tm{1} The set $U=\bigcup_{i=1}^sV_i^m$ is a cellular set of $\wh{\WC\wr_\Psi G}$ and $(\wh{\WC\wr_\Psi G})_U=\wh{\WC}\wr_{\wh\Psi}G$ where $\wh{\WC}=\{\wh{W_i}\}_{i=1}^s$ and $\wh\Psi=\{\wh{\psi_{i,j}}\}_{i,j=1}^s$. \tm{2} $\ov{\WC\wr_\Psi G}=\ov{\WC}\wr_{\ov\Psi}G$ where $\ov{\WC}=\{\ov{W_i}\}_{i=1}^s$ and $\ov\Psi=\{\ov{\psi_{i,j}}\}_{i,j=1}^s$ with $\ov{\psi_{i,j}}$ being the $m$-closure of~$\psi_{i,j}$. \tm{3} The algebra $\WC\wr_\Psi G$ is $m$-closed iff so is~$W_i$ for all~$i$. \enmrt \ethrm \proof We prove only the first statement since the others are straightforward from it. It is easy to see that the adjacency matrix of the relation $\bigcup_{i=1}^sV_i^m\times V_i^m\subset V^m\times V^m$ is a multiple of~$AI_\Delta A$ where $A$ is the $m$-fold tensor product of the matrix $\sum_{i=1}^sJ_{V_i}$ belonging to $\WC\wr_\Psi G$, and so belongs to $\wh{\WC\wr_\Psi G}$. Thus the first part of statement~(1) follows. Further, since $\WC\wr_\Psi G\leq\bpl_{i=1}^sW_i$, we have $$(\wh{\WC\wr_\Phi G})_U\leq \bpl\limits_{i=1}^s\wh{W_i}$$ by statement~(1) of Theorem~\ref{eads}. The group $\wh\Phi=\wh{\Phi(\Psi,G)}$ acts trivially on the algebra $(\WC\wr_\Psi G)^m$ and leaves the matrix $I_\Delta$ fixed. So it acts trivially also on $\wh{\WC\wr_\Psi G}$ by Theorem~\ref{tpea1}, which implies that the group~$\Phi(\wh\Psi,G)$ coinciding with $\wh\Phi_U$ acts trivially on $(\wh{\WC\wr_\Psi G})_U$. Since $\wh\WC\wr_{\wh\Psi}G$ is obviously the largest subalgebra of $\bpl_{i=1}^s\wh{W_i}$ with this property, we conclude that $$(\wh{\WC\wr_\Psi G})_U\leq \wh\WC\wr_{\wh\Psi}G.$$ To prove the converse inclusion we make use of the equality~(\ref{bsqu}) with $\WC$ and $\Psi$ replaced by $\wh\WC$ and $\wh\Psi$ and verify that $\wh\WC^{\wh\Psi},\wh\WC^G\subset(\wh{\WC\wr_\Psi G})_U$. A straightforward check shows that $I_U(\WC^\Psi)^mI_U=(\WC^m)^{\Psi^m}$ where $\WC^m=\{W_i^m\},\ \Psi^m=\{\psi_{i,j}^m\}$. So $(\WC^m)^{\Psi^m}\subset(\widehat{\WC\wr_\Psi G})_U$. Since $I_\Delta$ also belongs to $(\WC\wr_\Psi G)_U$, this algebra contains the smallest algebra satisfying~(C2) and~(C3) and containing $(\WC^m)^{\Psi^m}$ and $I_\Delta=\sum_{i=1}^s I_{\Delta_i}$. The last algebra coincides with $\wh\WC^{\wh\Psi}$ by Theorem~\ref{tpea1} applied to~$\wh{W_i}$, $i\in[s]$ (see~(\ref{twostar})). On the other hand, for any $O\in\orb_2(G)$ we have $$\wh A_O=\sum_{(i,j)\in O}J_{V^m_i,V^m_j}= I_U(\sum_{(i,j)\in O}J_{V_i,V_j})^mI_U=I_UA_O^mI_U$$ where $A_O^m$ is the $m$-fold tensor product of the matrix~$A_O$ (see~(\ref{onestar})). This implies that the algebra~$\wh\WC^G$ spanned by~$\wh A_O$'s is contained in $(\widehat{\WC\wr_\Psi G})_U$, which completes the proof.\bull \rmrk It follows from the above proof that $\wh{\WC\wr_\Psi G}\leq(\wh{\bpl_{i=1}^sW_i})^{\wh\Phi}$. On the other hand, it is easy to see that each Schurian algebra is strongly isomorphic to the wreath product of one-point matrix algebras by its automorphism group. So the equality would imply in particular that the $m$-extended algebra of a Schurian algebra is also Schurian. However, this does not seem to be true. \ermrk \crllr \label{wrschurn} Let $G$ be a transitive group. Then the algebra $\WC\wr_\Psi G$ is Schurian iff so is $W_i$ for all $i$ and $\psi_{i,j}\in\isow_\infty(W_i,W_j)$ for all~$i,j$. \ecrllr \proof By statement (3), Theorem~\ref{n2star} and the fact that $\ov W^\m=\sch(W)$ for all $W\leq\Mat_V$ and $m\geq n$ (see Proposition~\ref{clopro}) it suffices to prove that if $\WC\wr_\Psi G$ is Schurian, then $\psi_{i,j}$ is induced by a bijection $g_{i,j}$ from $V_i$ to $V_j$ for all $i,j$. Since the group~$G$ is transitive, each cell of $\WC\wr_\Psi G$ meets any set~$V_i$. The Schurity of $\WC\wr_\Psi G$ implies then that so does each orbit of its automorphism group. However, the relation $\bigcup_{i=1}^sV_i\times V_i$ is invariant with respect to this group. So given $i,j\in[s]$ there exists an automorphism of $\WC\wr_\Psi G$ taking~$V_i$ to~$V_j$, which produces the required bijection~$g_{i,j}$.\bull The analog of Theorem~\ref{sumext} for wreath products is the following statement in which we use the notation of Subsection~\ref{dswp}. \thrm Let $W=\WC\wr_\Psi G$, $W'=\WC'\wr_{\Psi'} G$ and $\varphi:W\to W'$ be the weak isomorphism induced by weak isomorphisms $\varphi_i:W_i\to W'_i$, $i\in[s]$, satisfying~(\ref{WRI}). Suppose that $\psi_{i,j}\in\isow_m(W_i,W_j)$ for all~$i,j$. Then $\varphi\in\isow_m(W,W')$ iff $\varphi_i\in\isow_m(W_i,W'_i)$ for all~$i$. \ethrm \proof Let us prove the necessity. Since $U=\bigcup_{i=1}^sV_i^m$ and $U'=\bigcup_{i=1}^s(V'_i)^m$ are cellular sets of the algebras~$\W$ and~$\WP$ and $U^{\wh\varphi}=U'$, we have $\wh\varphi(\W_U)=\WP_{U'}$. By statement~(1) of Theorem~\ref{clwr} $\W_U=\wh\WC\wr_{\wh\Psi}G$ where $\wh\WC=\{\wh{W_i}\}$, $\wh\Psi=\{\wh{\psi_{i,j}}\}$. It is easy to see that $\wh\varphi(\wh\WC^{\wh\Psi})=(\wt\WC')^{\wt\Psi'}$ for some $\wt\WC'=\{\wt W'_i\}_{i=1}^s$ with $\wt W'_i\le\Mat_{(V'_i)^m}$ and $\wt\Psi'=\{\wt\psi'_{i,j}\}_{i,j=1}^m$ with $\wt\psi'_{i,j}\in\isow(\wt W'_i,\wt W'_j)$. Moreover,~$\wh\varphi$ takes~$\wh\WC^G$ to~$(\wt\WC')^G$ so that condition~(\ref{wicond}) is satisfied. So $\wh{W'}_{U'}=\wt\WC'\wr_{\wt\Psi'}G$ and the weak isomorphism $$\wh\varphi_U:\wh\WC\wr_{\wh\Psi}G\to\wt\WC'\wr_{\wt\Psi'}G$$ is induced by some weak isomorphisms $\wt\varphi_i:\wh{W_i}\to\wt W'_i$, $i\in[s]$. It suffices to check that~$\wt W'_i=\wh{W'_i}$ and~$\wt\varphi_i$ is an $m$-extension of~$\varphi_i$ for all~$i$. First we observe that~$\wh\varphi(E)=E'$ where~$E$ (resp.~$E'$) is the adjacency matrix of the equivalence relation~$\bigcup_{i=1}^sV_i^m\times V_i^m$ (resp. $\bigcup_{i=1}^s(V'_i)^m\times (V'_i)^m$). So, $$\sum_i\wt\varphi_i\big(\bigotimes_jA_i^{(j)}\big)= \wh\varphi\big(\sum_i\bigotimes_jA_i^{(j)}\big)= \wh\varphi(E\circ\big(\bigotimes_j\sum_iA_i^{(j)}\big))=$$ $$\wh\varphi(E)\circ\wh\varphi\big(\bigotimes_j\sum_iA_i^{(j)}\big)= E'\circ\big(\bigotimes_j\varphi(\sum_iA_i^{(j)})\big)= E'\circ\big(\bigotimes_j\sum_i\varphi(A_i^{(j)})\big)= \sum_i\bigotimes_j\varphi_i(A_i^{(j)})$$ where~$i$ runs over~$[s]$, $j$ runs over~$[m]$ and~$A_i^{(j)}\in W_i$ with $\sum_iA_i^{(j)}\in\WC^\Psi$ for all~$j$. Thus~$\wt\varphi_i(A)=\varphi^m_i(A)$ for all~$A\in W_i^m$ and all~$i\in[s]$. Finally, $$\sum_{i=1}^s\wt\varphi_i(I_{\Delta_i})=\varphi(I_\Delta)=I_{\Delta'}= \sum_{i=1}^sI_{\Delta'_i}$$ where $\Delta_i$ (resp.~$\Delta'_i$) is the diagonal of~$V_i^m$ (resp.~$(V'_i)^m$). So~$\wt\varphi_i(I_{\Delta_i})=I_{\Delta'_i}$ for all~$i$. Therefore, $\wt W'_i=[(W'_i)^m,I_{\Delta'}]=\wh{W'_i}$ and $\wt\varphi_i$ is an $m$-extension of~$\varphi_i$ (see Theorem~\ref{tpea1} and Definition~\ref{defwmi}). Conversely, let~$\varphi_i\in\isow_m(W_i,W'_i)$ for all~$i\in[s]$. Then the weak isomorphism from~$\bpl_{i=1}^sW_i$ to~$\bpl_{i=1}^sW'_i$ induced by~$\varphi_i$'s is an $m$-isomorphism by Theorem~\ref{sumext}. The $m$-extension of it takes~$I_\Delta$ to~$I_{\Delta'}$ and coincides with~$\varphi^m$ on~$W^m$ (we use Definition~\ref{defwmi} and the fact that~$\varphi$ is induced by~$\varphi_i$'s). Thus we are done by Theorem~\ref{tpea1}.\bull \begin{thebibliography}{99} \bibitem{B} C.~Berge, {\em Graphs and Hypergraphs}, North-Holland Publ. Co., London, 1973. \bibitem{BI} E.~Bannai, T.~Ito, {\em Algebraic Combinatorics I. Association schemes}, Benjamin/Cummings, London, 1984. \bibitem{CFI} J.~Cai, M.~F{\" u}rer, N.~Immerman, {\em Optimal lower bound on the number of variables for graph identification}, Combinatorica {\bf 12} (1992), 389--410. \bibitem{EKP} S.~A.~Evdokimov, M.~Karpinski, I.~N.~Ponomarenko, {\em On a New High Dimensional Weisfeiler-Lehman Algorithm}, (accepted to J. of Algebraic Combinatorics). \bibitem{EP} S.~A.~Evdokimov, I.~N.~Ponomarenko, {\em On primitive cellular algebras}, to appear in Zapiski Nauchnykh Seminarov POMI, {\bf 256} (1999). \bibitem{EPN} S.~A.~Evdokimov, I.~N.~Ponomarenko, {\em Two Inequalities for the Parameters of a Cellular Algebra}, Zapiski Nauchnykh Seminarov POMI, {\bf 240} (1997), 82--95. \bibitem{FKM} I.~A.~Farad{\v z}ev, M.~H.~Klin, M.~E.~Muzichuk, {\em Cellular rings and groups of automorphisms of graphs}, in: I. A. Farad{\v z}ev et al. (eds): Investigations in algebraic theory of combinatorial objects, Kluwer Acad. Publ., Dordrecht, 1994, 1--152. \bibitem{F} S.~Friedland, {\em Coherent algebras and the graph isomorphism problem}, Discrete Appl. Math., {\bf 25} (1989), 73--98. \bibitem{HH} M.~D.~Hestens, D.~G.~Higman, {\em Rank~3 groups and strongly regular graphs}, SIAM-AMS Proc., {\bf 4} (1971), 141--159. \bibitem{Hi} D.~G.~Higman, {\em Coherent algebras}, Linear Algebra Appl., {\bf 93} (1987), 209--239. \bibitem{Iv} G.~Ivanyos, {\em On the combinatorics of Evdokimov's deterministic factorization method}, Preprint, 1997. \bibitem{LU} F.~Lazebnik, V.~A.~Ustimenko, A.~J.~Woldar, {\em A characterization of the components of the graphs $D(k,q)$}, Discrete Math., {\bf 157} (1996), 271--283. \bibitem{Sm} J.~D.~H.~Smith, {\em Association schemes, superschemes, and the relation invariant under permutation groups}, European J. Combin., {\bf 15} (1994), 285--291. \bibitem{U} V.~A.~Ustimenko, {\em Coordinates of Trees and their Quotients}, in ``Voronoj's Impact in Modern Science'', Kiev, Institute of Mathematics, {\bf 2} (1998), 125--152. \bibitem{Wa} M.~Watkins, {\em Connectivity of transitive graphs}, J. Combin. Theory, {\bf 8} (1970), 23--29. \bibitem{WL} B.~Ju.~Weisfeiler, A.~A.~Lehman, {\em Reduction of a graph to a canonical form and an algebra which appears in the process}, NTI, Ser.2, (1968), 9, 12--16. \bibitem{W} B.~Ju.~Weisfeiler (editor), {\em On construction and identification of graphs}, Springer Lecture Notes, 558, 1976. \bibitem{Wi} H.~Wielandt, {\em Finite permutation groups}, Academic press, New York - London, 1964. \end{thebibliography} \end{document}