Part(\bn,r)$, and write $\bA=\{A_1,\ldots,A_r\}$ and $\bB=\{B_1,\ldots,B_r\}$ with $\min(A_1)<\cdots<\min(A_r)$ and $\min(B_1)<\cdots<\min(B_r)$.  We define $\phi_{\bA,\bB}=\direl{A_1}{\cdots}{A_r}{B_1}{\cdots}{B_r}$.  In order to simplify notation in what follows, and since $n$ is fixed, for each $1\leq k\leq n$, we will write $p_k=S(n,k)$.  For each $1\leq k\leq n$, let us denote the elements of $\Part(\bn,k)$ by $\bA_{k,1},\ldots,\bA_{k,p_k}$.


\ms
\begin{lemma}\label{lem:upper}
For each $1\leq k\leq n-1$, let $\Si_k = \{\phi_{\bA_{k,1},\bA_{k,2}},\ldots,\phi_{\bA_{k,p_k-1},\bA_{k,p_k}}\} \cup \{\lam_{\bA_{k,p_k}},\rho_{\bA_{k,1}}\}$.
Then for any $1\leq r\leq n$,
$I_r=\la J_r\cup\Si_1\cup\cdots\cup\Si_{r-1}\ra$.
\end{lemma}

\pf Put $\Om = J_r\cup\Si_1\cup\cdots\cup\Si_{r-1}$.  By Lemma \ref{lem:LSiR}, to show that $I_r=\la\Om\ra$, it suffices to show that~$\la\Om\ra$ contains both $\cL_r$ and $\cR_r$.  Let $\bA\in\Part(\bn)$ with $|\bA|\leq r$.  We must show that $\lam_\bA,\rho_\bA\in\la\Om\ra$.  If $|\bA|=r$, then $\lam_\bA,\rho_\bA\in J_r\sub\la\Om\ra$, so suppose $\bA\in\Part(\bn,k)$, where $1\leq k\leq r-1$.  Then $\bA=\bA_{k,l}$ for some $1\leq l\leq p_k$.  But then
\begin{align*}
\lam_\bA = \lam_{\bA_{k,l}} &= (\phi_{\bA_{k,l},\bA_{k,l+1}} \dia\cdots\dia \phi_{\bA_{k,p_k-1},\bA_{k,p_k}}) \dia \lam_{\bA_{k,p_k}}, \\
\rho_\bA = \rho_{\bA_{k,l}} &= \rho_{\bA_{k,1}} \dia (\phi_{\bA_{k,1},\bA_{k,2}} \dia\cdots\dia \phi_{\bA_{k,l-1},\bA_{k,l}}),
\end{align*}
where the first bracketed expression is omitted if $l=p_k$, and the second if $l=1$. \epf


\ms
\begin{rem}
We could not help noticing that the generating set used in Lemma \ref{lem:upper} looks very similar to the construction of so-called \emph{rainbow tables} in computer security \cite{Hellman1980}. This is perhaps not surprising, since both constructions have the purpose, broadly speaking, of reducing the total amount of memory used for storing given information.
\end{rem}


Since $|\Si_k|=S(n,k)+1$ for each $k$, it follows from Lemma \ref{lem:upper} that $\rank(I_r:J_r)\leq r-1+\sum_{k=1}^{r-1}S(n,k)$.  To complete the proof of Lemma \ref{lem:IJ}, we must therefore show that this upper bound for $\rank(I_r:J_r)$ is also a lower bound.  To do this, we will show in Lemmas \ref{lem:Si1} and \ref{lem:Si2} that if $\Si\sub I_r$ is such that $I_r=\la J_r\cup\Si\ra$, then $\Si$ must include certain specified kinds of relations. 
First, we prove two intermediate lemmas.  There are obvious dual versions of Lemmas \ref{lem:abc} and \ref{lem:abc2}, but we will not state them.


\ms
\begin{lemma}\label{lem:abc}
If $\al,\be,\ga\in\D_n$ are such that $\al=\be\dia\ga$ and $\dom(\al)=\bn$, then $\ker(\al)=\ker(\be)$.
\end{lemma}

\pf Since $\al=\be\dia\ga$, we have $\al\leq_\R\be$, so Lemma \ref{lem:green}(i) gives $\ker(\al)\sub\ker(\be)$.  Since $\dom(\al)=\bn$, it is clear that $\ker(\al)$ is maximal, inclusion-wise, so we must in fact have $\ker(\al)=\ker(\be)$. \epf



\ms
\begin{lemma}\label{lem:abc2}
If $\al,\be,\ga\in\D_n$ are such that $\al=\be\dia\ga$, $\ker(\al)=\ker(\be)$ and $\codom(\be)=\bn$, then 
$\be^{-1}\dia\al=\ga$.
\end{lemma}

\pf Since $\ker(\be)=\ker(\al)=\ker(\be\dia\ga)$, it follows that $\coker(\be)\sub\ker(\ga)$.  Since $\codom(\be)=\bn$, $\coker(\be)$ is maximal, inclusion-wise, so we must in fact have $\coker(\be)=\ker(\ga)$.  But then $\be^{-1}\dia\be=\ga\dia\ga^{-1}$, which gives $\ga=\ga\dia\ga^{-1}\dia\ga=\be^{-1}\dia\be\dia\ga=\be^{-1}\dia\al$. \epf








\ms
\begin{lemma}\label{lem:Si1}
If $I_r=\la J_r\cup\Si\ra$, and if $1\leq k\leq r-1$, then there exist $\si,\tau\in\Si$ with $\dom(\si)=\codom(\tau)=\bn$, $\rank(\si)=\rank(\tau)=k$ and $\codef(\si),\deff(\tau)>0$.
\end{lemma}

\pf It suffices to prove the existence of $\si$, as the existence of $\tau$ will follow by a symmetrical argument (for which we need the duals of Lemmas \ref{lem:abc} and \ref{lem:abc2}).  Let $1\leq k\leq r-1$, and write 
\[
\Om=\set{\al\in\D_n}{\dom(\al)=\bn,\ \rank(\al)=k,\ \codef(\al)>0}.
\]
For $\al\in\Om$, write $\ell(\al)$ for the minimum value of $m$ such that $\al=\be_1\dia\cdots\dia\be_m$ for some $\be_1,\ldots,\be_m\in J_r\cup\Si$.  Let $L=\min\set{\ell(\al)}{\al\in\Om}$. 
To establish the existence of $\si$, it suffices to prove that $L=1$. 
To do this, suppose to the contrary that $L\geq2$, and choose some $\al= \direl{A_1}\cdots{A_k}{B_1}\cdots{B_k}\in\Om$ with $\ell(\al)=L$.  So we may write $\al=\be_1\dia\be_2\dia\cdots\dia\be_L$ for some $\be_1,\be_2,\ldots,\be_L\in J_r\cup\Si$.   For simplicity, put $\be=\be_1$ and $\ga=\be_2\dia\cdots\dia\be_L$, so $\al=\be\dia\ga$.  Lemma \ref{lem:abc} gives $\ker(\be)=\ker(\al)$, so we may write $\be=\direl{A_1}\cdots{A_k}{C_1}\cdots{C_k}$.  If $\codef(\be)>0$, then we put $\si=\be$, and the proof of the lemma is complete.  So suppose $\codef(\be)=0$.  This means that $\codom(\be)=\bn$, and Lemma \ref{lem