text:
# Growth diagrams, Domino insertion and Sign-imbalance

## 1. Introduction

Recently in \[SW\] Shimozono and White described a semistandard generalisation of domino insertion giving a bijection between colored biwords and pairs of semistandard domino tableaux of the same shape. They connected domino insertion with Haiman’s mixed and left-right insertion algorithms \[Hai\] and via this obtained the semistandard analogue. They also made explicit a color-to-spin property of domino insertion. This property appears to have been used earlier by Kirillov, Lascoux, Leclerc and Thibon \[KLLT\] for some special colored involutions.

Earlier, van Leeuwen \[vL\] had described domino insertion in terms of Fomin’s growth diagrams. He connected Barbasch and Vogan’s left-right insertion description \[BV\] with Garfinkle’s traditional bumping description \[Gar\]. He also defines insertion in the presence of a 2-core.

Our first aim in this paper is to give a self contained proof of the semistandard domino-Schensted correspondence, using elementary growth diagram calculations to prove all the main properties of the bijection which we also extend to the nonempty 2-core case. Thus our approach allows us to avoid mention of mixed insertion completely. We also describe two dual domino-Schensted bijections. These are bijections between multiplicity free colored biwords and pairs of semistandard domino tableaux which have conjugate shapes. Finally, we perform a detailed analysis of symmetric growth diagrams for domino insertion.

The study of growth diagrams leads us to a number of applications. These include a number of enumerative results for domino tableaux, an application to sign-imbalance, and a collection of product expansions for generating series of domino functions.

The sign $`sign(T)`$ of a standard Young tableaux $`T`$ is the sign of its reading word. The sign imbalance of a shape $`\lambda `$ is defined as

$$\underset{SYTT:sh(T)=\lambda }{}sign(T).$$

That sign-imbalance is related to domino tableaux has been made explicit in work of White \[Whi\] and Stanley \[Sta\]. In particular, White gives a formula for the sign of the Young tableaux $`T(D)`$ associated to a domino tableaux $`D`$:

$$sign(T)=(1)^{ev(D)}$$

where $`ev(D)`$ is the number of vertical dominoes in even columns of $`D`$. Domino tableaux are in bijection with hyperoctahedral involutions and we prove that in fact $`ev(D)`$ is equal to the number of barred two-cycles of $`\pi `$, where $`D=P_d(\pi )`$ is the insertion tableaux of $`\pi `$. This allows us to prove Stanley’s conjecture on sign-imbalance, our Theorem 24, which is a 4-parameter generalisation of the following elegant result:

$$\underset{SYTT:sh(T)m}{}sign(T)=2^{m/2}.$$

Carré and Leclerc \[CL\] and Kirillov, Lascoux, Leclerc and Thibon \[KLLT\] have studied certain generating functions $`H_\lambda (X;q)`$ for domino tableaux which we loosely call *domino functions*. More general domino functions $`G_\lambda (X;q)`$ were developed also in \[LLT\], where they were connected with the Fock space representation of $`U_q(\widehat{𝔰l_2})`$. These are defined as

$$G_\lambda (X;q)=\underset{D}{}q^{spin(D)}x^D$$

where the sum is over all semistandard domino tableaux of shape $`D`$. The $`H_\lambda `$ are defined by $`H_\lambda (X;q)=G_{2\lambda }(X;q)`$. Product expansions of the sums $`H_\lambda (X;q)`$ and $`H_{\lambda \lambda }(X;q)`$ were given in \[KLLT\].

By studying colored involutions we give a product expansion for a 3-parameter generalisation of the sum $`_\lambda G_\lambda (X;q)`$. When the parameters of this sum is specialised, we obtain both of the product expansions of \[KLLT\].

We now briefly describe the organisation of this paper. In Section 2 we give some notation and definitions for domino tableaux and colored words. We also give a description of domino insertion bumping in an informal manner, following mostly \[SW\]. In Section 3, we introduce and study growth diagrams. This is followed by a proof of the semistandard domino-Schensted correspondence and a description of the dual domino-Schensted correspondences. The section ends with a study of symmetric growth diagrams and some enumerative results. In Section 4, we apply the results of Section 3 to sign-imbalance. In Section 5, we combine the results of Section 3 with a study of the standardisation of colored involutions. These lead to a number of product expansions for generating series of domino functions. In Section 6, we give some final remarks concerning possible generalisations to longer ribbons.

Acknowledgements I am indebted to my advisor, Richard Stanley, for introducing the subjects of domino tableaux and sign-imbalance to me and for suggesting his conjecture for study. My work on generating series of domino functions was inspired by the sum $`(1)^{ev(\lambda )}\stackrel{~}{G}_\lambda (X;1)`$ suggested to me by him.

## 2. Preliminaries

### 2.1. Domino Tableaux

We will let $`[n]=\{1,2,\mathrm{},n\}`$ throughout.

Let $`\lambda =(\lambda _1\lambda _2\mathrm{}\lambda _{l(\lambda )}>0)`$ be a partition of $`n`$. We will often not distinguish between a partition $`\lambda `$ and its diagram (often called $`D(\lambda )`$) but the meaning will always be clear from the context. The partition $`\lambda \mu `$ is obtained by taking the union of the parts of $`\lambda `$ and $`\mu `$ (and reordering to form a partition). We denote by $`\stackrel{~}{\lambda }`$ and $`(\lambda ^{(0)},\lambda ^{(1)})`$ the $`2`$-core and $`2`$-quotient of $`\lambda `$ respectively (see \[Mac\]). Every 2-core has the shape of a staircase $`\delta _r=(r,r1,\mathrm{},0)`$ for some integer $`r0`$. As usual, when $`\lambda `$ and $`\mu `$ are partitions satisfying $`\mu \lambda `$ we will use $`\lambda /\mu `$ to denote the shape corresponding to the set-difference of the diagrams of $`\lambda `$ and $`\mu `$.

We denote the set of partitions by $`𝒫`$ and the set of partitions with 2-core $`\delta _r`$ by $`𝒫_r`$. The set of all partitions $`\lambda `$ satisfying the two conditions:

$`\stackrel{~}{\lambda }`$ $`=\delta _r`$
$`|\lambda |`$ $`=\delta _r+2n`$
will be denoted $`𝒫_r(n)`$. Note that $`𝒫=_{r,n}𝒫_r(n)`$.

A (standard) domino tableaux (SDT) $`D`$ of shape $`\lambda `$ consists of a tiling of the shape $`\lambda /\stackrel{~}{\lambda }`$ by dominoes and a filling of each domino with an integer in $`[n]`$ so that the numbers are increasing when read along either the rows or columns. Here, $`n`$ is $`\frac{1}{2}|\lambda /\stackrel{~}{\lambda }|`$. A domino is any $`2\times 1`$ or $`1\times 2`$ shape, or equivalently, two adjacent squares sharing a common edge. The *value* of a domino is the number written inside it. We will write $`dom_i`$ to indicate the domino with the value $`i`$ inside. We will also write $`sh(D)=\lambda `$. An alternative way of describing a standard domino tableaux of shape $`\lambda `$ is by a sequence of partitions $`\left\{\stackrel{~}{\lambda }=\lambda ^0\lambda ^1\mathrm{}\lambda ^n=\lambda \right\}`$, where $`sh(dom_i)=\lambda _i/\lambda _{i1}`$.

A semistandard domino tableaux (SSDT) $`D`$ of shape $`\lambda `$ consists of a tiling of the shape $`\lambda /\stackrel{~}{\lambda }`$ by dominoes and a filling of each domino with an integer, so that the numbers are non-decreasing when read along the rows and increasing when read along the columns. The *weight* of such a tableaux $`D`$ is the composition $`wt(D)=(\mu _1,\mu _2,\mathrm{})`$ where there are $`\mu _i`$ occurrences of $`i`$’s in $`D`$. Let $`v(D)`$ be the number of vertical dominoes in a domino tableaux $`D`$. The spin $`sp(D)`$, is defined as $`v(D)/2`$. The standardisation of a semistandard domino tableaux $`D`$ of weight $`\mu `$ is a standard domino tableaux $`D^{st}`$ obtained from $`D`$ by replacing the dominoes containing $`1`$’s with $`1,2,\mathrm{},\mu _1`$ from left to right, the dominoes containing $`2`$’s by $`\mu _1+1,\mu _1+2,\mathrm{},\mu _1+\mu _2`$, and so on.

More general skew (semi)standard domino tableaux are defined in a similar manner.

We should remark that Littlewood’s 2-quotient map \[Lit\] gives a bijection between standard domino tableaux of shape $`\lambda `$ and pairs of standard Young tableaux of shapes $`\lambda ^{(0)}`$ and $`\lambda ^{(1)}`$. This bijection generalises naturally to the semistandard case. See for example \[CL\]. We will, however, not be needing this bijection.

### 2.2. Colored Words

We will mostly follow the notation of \[SW\] in this subsection.

A *letter* will be an integer with possibly a bar over it.

A *colored word* is a word made of letters. A colored word $`𝐰`$ is a *colored permutation* if each integer of $`[n]`$ is used exactly once, for some $`n`$. Such a word will also be called a hyperoctahedral permutation or a signed permutation. The set (in fact group) of all such words will be denoted $`B_n`$. We define $`𝐰^{neg}`$ to be the word obtained from $`𝐰`$ by converting all the bars to negative signs. The weight of a word is defined in the usual way, with the bars ignored. The operation $`ev`$ removes the bars from a colored word. Thus if $`𝐰=(2\overline{3}\overline{1})`$ then $`𝐰^{ev}=(231)`$.

A *biletter* is an ordered pair of letters denoted $`\left(\genfrac{}{}{0pt}{}{x}{y}\right)`$.

A *doubly colored biword* is a sequence of biletters $`\left(\genfrac{}{}{0pt}{}{x}{y}\right)`$ ordered canonically in the following way. A biletter $`\left(\genfrac{}{}{0pt}{}{x}{y}\right)`$ occurs before $`\left(\genfrac{}{}{0pt}{}{k}{l}\right)`$ if and only if one of the following holds:

1. $`x<k`$
2. $`x=k`$, both are unbarred, and $`y^{neg}<l^{neg}`$
3. $`x=k`$, both are barred and $`l^{neg}<y^{neg}`$.

A doubly colored biword is a colored biword if only the bottom row has bars. For doubly colored biwords $`𝐰`$, its inverse $`𝐰^{inv}`$ is obtained by swapping the top and bottom letters of each biletter and then reordering. For colored biwords $`𝐰`$ its inverse $`𝐰^{inv_r}`$ is obtained by first moving the bars to the top row and then performing the inverse normally. Note that both $`inv`$ and $`inv_r`$ are involutions.

The total color of a word or a colored word $`𝐰`$, denoted $`tc(𝐰)`$, is the number of barred letters in the word.

Define $`ev`$ to be the operation which removes the bars from a letter, word, biletter or a biword.

Standardisation $`st`$ is defined as follows for a colored biword $`𝐰`$. First define $`𝐰^{\overline{st}}`$ by replacing the top row with $`\{1,2,3,\mathrm{}\}`$ from left to right when the biword is written in order. Then, define $`𝐰^{st}`$ by (see \[SW\])

$$𝐰^{st}=𝐰^{\overline{st}inv\overline{st}inv}.$$

For example, let $`𝐰`$ be the colored biword

$$𝐰=\left(\begin{array}{ccccc}1& 1& 2& 3& 3\\ \overline{2}& 3& 4& \overline{1}& \overline{1}\end{array}\right).$$

Then $`𝐰`$ has top weight $`(2,2,1)`$ and bottom weight $`(2,1,1,1)`$. Its inverse $`𝐰^{inv_r}`$ is given by

$$𝐰^{inv_r}=\left(\begin{array}{ccccc}1& 1& 2& 3& 4\\ \overline{3}& \overline{3}& \overline{1}& 1& 2\end{array}\right).$$

Its standardisation $`𝐰^{st}`$ is computed as follows

$`𝐰^{\overline{st}}`$ $`=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ \overline{2}& 3& 4& \overline{1}& \overline{1}\end{array}\right).`$
$`𝐰^{\overline{st}inv}`$ $`=\left(\begin{array}{ccccc}\overline{1}& \overline{1}& \overline{2}& 3& 4\\ 5& 4& 1& 2& 3\end{array}\right)`$
$`𝐰^{\overline{st}inv\overline{st}}`$ $`=\left(\begin{array}{ccccc}\overline{1}& \overline{2}& \overline{3}& 4& 5\\ 5& 4& 1& 2& 3\end{array}\right)`$
$`𝐰^{\overline{st}inv\overline{st}inv}`$ $`=\left(\begin{array}{ccccc}1& 2& 3& 4& 5\\ \overline{3}& 4& 5& \overline{2}& \overline{1}\end{array}\right)`$
###### Lemma 1.

Let $`𝐰`$ be a colored biword. Then

$`𝐰^{st}`$ $`=𝐰^{inv\overline{st}inv\overline{st}}`$
$`𝐰^{st}`$ $`=𝐰^{\overline{st}inv_r\overline{st}inv_r}`$
$`𝐰^{inv_rst}`$ $`=𝐰^{stinv_r}.`$
###### Proof.

The first statement is \[SW, Proposition 12\]. The second statement is essentially mentioned in \[SW, Proposition 39\]. All three statements can be checked directly, which may be done along the lines of Lemma 27 (but is easier). ∎

We will occassionally identify a colored word $`𝐰`$ or a hyperoctahedral permutation $`\pi `$ with the associated colored biword obtained by filling the top row with $`\{1,2,\mathrm{},n\}`$ from left to right. In the latter case, $`\pi ^{inv}`$ will be identified with the lower row of the inverse of the resulting biword. This the usual inverse in the group $`B_n`$.

### 2.3. Domino insertion

The normal Robinson-Schensted algorithm gives a bijection between permutations of $`S_n`$ and pairs $`(P,Q)`$ of standard Young tableaux (SYT) of size $`n`$ and the same shape. A semistandard generalisation of this was given by Knuth. This is a bijection between certain matrices with non-negative integer entries (or alternatively unbarred biwords) and pairs of semistandard Young Tableaux of the same shape. We refer the reader to \[EC2\] for further details. Henceforth, familiarity with usual Robinson-Schensted insertion will be assumed.

In this section we describe the corresponding bijection for domino tableaux in a traditional insertion ‘bumping’ procedure. We will follow the description given by Shimozono and White \[SW\] for the rest of this section where more details may be found. As the whole theory will be developed completely from the growth diagram point of view in Section 3, we will not be completely formal. The reader is referred to \[Gar\], \[SW\], \[vL\] for full details.

Let $`D`$ be a domino tableaux with $`sh(D)=\lambda `$, no values repeated, and $`i`$ a value which does not occur in $`D`$. We will describe how to insert both a vertical and horizontal domino with value $`i`$ into $`D`$. Let $`AD`$ be the sub-domino tableaux containing values less than $`i`$. If $`\lambda `$ has a 2-core $`\lambda =\stackrel{~}{\lambda }`$, then we will always assume that $`\stackrel{~}{\lambda }sh(A)`$. We set $`B`$ to be the domino tableaux containing $`A`$ and an additional vertical domino in the first column or an additional horizontal domino in the first row labelled $`i`$. Let $`C=D/D^{}`$ be the skew domino tableaux containing values greater than $`i`$. Now we recursively define a bumping procedure as follows.

Let $`(B,C)`$ be a pair of domino tableaux (with no values repeated) overlapping in at most a domino which contains the largest value of $`B`$. The combined shape of $`B`$ and $`C`$ must be a valid skew shape and the values of $`C`$ larger than those of $`B`$. Let $`i<j`$ be the largest and smallest values of $`B`$ and $`C`$ respectively. Denote the corresponding dominoes by $`\gamma _i`$ and $`\gamma _j`$. We now distinguish four cases:

1. If $`\gamma _i`$ and $`\gamma _j`$ do not touch, then we set $`B^{}=B\gamma _j`$ and $`C^{}=C\gamma _j`$.
2. If $`\gamma _i`$ and $`\gamma _j`$ intersect in exactly one square, then we add a domino containing $`j`$ to $`B`$ so that the shape of $`B`$ contains both $`\gamma _i`$ and $`\gamma _j`$ together with the unique additional box which is diagonally outwards (right and down) from $`\gamma _i\gamma _j`$. We set $`C^{}=C\gamma _j`$.
3. If $`\gamma _i=\gamma _j`$ and both are horizontal, then we ‘bump’ the domino $`\gamma _j`$ to the next row, by setting $`B^{}`$ to be the union of $`B`$ with an additional (horizontal) domino with value $`j`$ one row below that of $`\gamma _i`$. We set $`C^{}=C\gamma _j`$.
4. If $`\gamma _i=\gamma _j`$ and both are vertical, then we ‘bump’ the domino $`\gamma _j`$ to the next column, by setting $`B^{}`$ to be the union of $`B`$ with an additional (vertical) domino with value $`j`$ one column to the right of $`\gamma _i`$. We set $`C^{}=C\gamma _j`$.

This procedure is repeated with $`(B,C)`$ replaced by $`(B^{},C^{})`$ until the (skew) domino tableaux $`C`$ becomes empty.

The resulting $`B`$ tableaux will be denoted by $`Di`$ for the insertion of a horizontal domino and $`D\overline{i}`$ for a vertical domino.

Let $`𝐰=w_1w_2\mathrm{}w_n`$ be a colored permutation and $`\delta _r`$ be a 2-core assumed to be fixed throughout. Then the insertion tableaux $`P_d^r(𝐰)`$ is defined as $`((\mathrm{}((\delta _rw_1)w_2)\mathrm{})w_n)`$. The sequence of shapes obtained in the process defines another standard domino tableaux called the recording tableaux $`Q_d^r(𝐰)`$.

As an example, the domino tableaux $`P_d^0(\overline{3}42\overline{1})`$ is constructed as follows:

The following theorem will be proven in Section 3.

###### Theorem 2.

Fix $`r0`$. The above algorithm defines a bijection between signed permutations $`\pi B_n`$ and pairs of domino tableaux $`(P,Q)`$ of the same shape $`\lambda 𝒫_r(n)`$. This bijection satisfies the equality

$$tc(\pi )=sp(P_d(\pi ))+sp(Q_d(\pi )).$$

The insertion algorithm is due to Barbasch and Vogan \[BV\] in a different form (left-right insertion and jeu-de-taquin). The insertion described here in terms of bumping is essentially that of Garfinkle \[Gar\]. Van Leeuwen \[vL\] proves that the Barbasch-Vogan algorithm is the same as the bumping description, and also shows that the bijection holds in the presence of a 2-core. That this algorithm sends total color to the sum of spins seems to have been first used by Kirillov, Lascoux, Leclerc and Thibon in \[KLLT\] for certain hyperoctahedral involutions, though no details or proofs are present. More recently, the color-to-spin property is made explicit by Shimozono and White in \[SW\].

Shimozono and White \[SW\] only prove the color-to-spin property in the absence of a 2-core. However, the color-to-spin property is proven by studying the spin change for all the ‘bumps’ in the insertion and these are unaffected by the presence of a 2-core. Thus the generalisation of the domino insertion bijection to the 2-core case is immediate. Shimozono and White also give a semistandard generalisation of this bijection which is the case $`r=0`$ of the following theorem. Their theory of domino insertion is developed in conjunction with other combinatorial algorithms including Haiman’s mixed insertion and left-right insertion.

###### Theorem 3.

Fix a 2-core $`\delta _r`$. There is a bijection between colored biwords $`𝐰`$ of length $`n`$ and pairs $`(P_d^r(𝐰),Q_d^r(𝐰))`$ of semistandard domino tableaux with the same shape $`\lambda 𝒫_r(n)`$ with the following properties:

1. The bijection has the color-to-spin property:

$$tc(𝐰)=sp(P_d^r(𝐰))+sp(Q_d^r(𝐰)).$$
2. The weight of $`P_d^r(𝐰)`$ is the weight of the lower word of $`𝐰`$. The weight of $`Q_d^r(𝐰)`$ is the weight of the lower word of $`𝐰`$.
3. The bijection commutes with standardisation in the following sense:

$`P_d^r(𝐰)^{st}`$ $`=P_d^r(𝐰^{st}).`$
$`Q_d^r(𝐰)^{st}`$ $`=Q_d^r(𝐰^{st}).`$

The proof of this will be left until the next section, where we give an alternative description of domino insertion in terms of growth diagrams.

## 3. Growth Diagrams and Domino Insertion

### 3.1. Properties of Growth Diagrams

The insertion algorithm of subsection 2.3 can also be phrased in terms of Fomin’s growth diagrams \[Fom1, Fom2\] (also known as the poset-theoretic description, or language of shapes). This was first made explicit by van Leeuwen \[vL\]. We will show how growth diagrams are relevant to the semistandard generalisation of domino insertion of \[SW\]. Thus our aim will be to give a short, stand-alone proof of Theorem 3 using elementary considerations of growth diagrams only, bypassing the connection with mixed insertion used by Shimozono and White. Thus their lemma \[SW, Lemma 33\] is replaced by our Lemma 9. The use of growth diagrams make the generalisation to the case of nonempty 2-core immediate. In fact one could use growth diagrams to define the entire correspondence and develop the theory beginning from that.

Let $`M(i,j)`$ be a $`n\times n`$ matrix taking values from $`\{0,1,1\}`$ thought of as the matrix representing a hyperoctahedral permutation. Thus it has one non-zero value in each row or column. We will take the row and column indices to lie in $`[n]`$.

The growth diagram (of $`M(i,j)`$) is an array of partitions $`\lambda _{(i,j)}`$ for $`1i,jn+1`$. Two ‘adjacent’ partitions $`\lambda _{(i,j)}`$ and $`\lambda _{(i+1,j)}`$ or $`\lambda _{(i,j)}`$ and $`\lambda _{(i,j+1)}`$ are either identical or differ by exactly one domino. Initially, all the partitions $`\lambda _{(1,j)}`$ and $`\lambda _{(i,1)}`$ are set to the same partition $`\mu `$. For our purposes this will usually be a partition satisfying $`\mu =\stackrel{~}{\mu }`$. The remainder of the growth diagram will be determined from $`\mu `$ and the data $`M(i,j)`$ according to the following local rules.

Let $`\lambda =\lambda _{(i,j)}`$, $`\mu =\lambda _{(i+1,j)}`$, $`\nu =\lambda _{(i,j+1)}`$, $`\rho =\lambda _{(i+1,j+1)}`$ be the corners of a ‘square’. Assume (inductively) that $`\lambda ,\mu `$ and $`\nu `$ are known. Then $`\rho `$ is determined as follows:

1. If $`M(i,j)=1`$ then it must be the case that $`\lambda =\mu =\nu `$. Obtain $`\rho `$ from $`\lambda `$ by adding two to the first row.
2. If $`M(i,j)=1`$ then it must be the case that $`\lambda =\mu =\nu `$. Obtain $`\rho `$ from $`\lambda `$ by adding two to the first column.
3. If $`M(i,j)=0`$ and $`\lambda =\mu `$ or $`\lambda =\nu `$ (or both) then $`\rho `$ is set to the largest of the three partitions.
4. Otherwise $`M(i,j)=0`$ and $`\nu `$ and $`\mu `$ differ from $`\lambda `$ by dominoes $`\gamma `$ and $`\gamma ^{}`$. If $`\gamma `$ and $`\gamma ^{}`$ do not intersect then $`\rho `$ is set to be the union $`\lambda \gamma \gamma ^{}`$. If $`\gamma \gamma ^{}`$ is a single square $`(k,l)`$, then $`\rho `$ is the union of $`\lambda \gamma \gamma ^{}(k+1,l+1)`$. If $`\gamma =\gamma ^{}`$ is a vertical domino then $`\rho `$ is obtained from $`\lambda \gamma `$ by adding two to the column immediately to the right of $`\gamma `$. If $`\gamma =\gamma ^{}`$ is a horizontal domino then $`\rho `$ is obtained from $`\lambda \gamma `$ by adding two to the row immediately below $`\gamma `$.

We will call these rules the *local rules* of the growth diagram.

###### Proposition 4.

The above algorithm is well defined. The growth diagram models the insertion of the colored permutation $`\pi `$ corresponding to $`M(i,j)`$ into a 2-core $`\delta _r`$ (in fact more generally any initial partition) .

The partition $`\lambda _{(i,j)}`$ is the shape of the tableaux obtained after the first $`i`$ insertions and restricted to values less than $`j`$. Thus $`\{\lambda _{(n+1,j)}:j[n+1]\}`$ is a chain of partitions determining $`P_d^r(\pi )`$ and $`\{\lambda _{(i,n+1)}:i[n+1]\}`$ is a chain of partitions determining $`Q_d^r(\pi )`$.

###### Proof.

This is proven via induction, by comparing domino insertion with the local rules of the growth diagram. The details can be found in \[vL\]. ∎

For example, Figure 3 is the growth diagram corresponding to the insertion procedure of Figure 2.

###### Lemma 5.

The local rules of a growth diagram are reversible in the following sense. Let $`\lambda =\lambda _{(i,j)}`$, $`\mu =\lambda _{(i+1,j)}`$, $`\nu =\lambda _{(i,j+1)}`$, $`\rho =\lambda _{(i+1,j+1)}`$ be the corners of a ‘square’ of the growth diagram. Then $`\rho `$, $`\mu `$ and $`\nu `$ determine $`\lambda `$ and $`M(i,j)`$.

###### Proof.

This is a simple verification of the local rules. ∎

Note, that there can be two legitimate standard domino tableaux corresponding to $`\{\lambda _{(i,n+1)}:i[n+1]\}`$ and $`\{\lambda _{(n+1,j)}:j[n+1]\}`$ which do not give a growth diagram corresponding to an insertion procedure. For example if $`\lambda _{(1,2)}=(2)=\lambda _{(2,1)}`$ and $`\lambda _{(2,2)}=(2,2)`$ then $`\lambda _{(1,1)}`$ must be $`\mathrm{}`$. This is not a valid growth diagram for insertion as $`\lambda _{(1,1)}\lambda _{(2,1)}`$.

###### Lemma 6.

The correspondence

$$\pi (P_d^r(\pi ),Q_d^r(\pi ))$$

is a bijection between $`\pi B_n`$ and pairs of standard domino tableaux of the same shape $`\lambda 𝒫_r(n)`$.

###### Proof.

The previous Lemma implies that this correspondence is injective. As no dominoes can be removed from $`\delta _r`$, the ‘initial’ row and column of the growth diagram ($`\lambda _{(1,j)}`$ and $`\lambda _{(i,1)}`$) will consist completely of partitions equal to $`\delta _r`$. Thus setting $`\lambda _{(i,n+1)}:i[n+1]`$ and $`\lambda _{(n+1,j)}:j[n+1]`$ to two tableaux of the shape $`\lambda 𝒫_r(n)`$ will give a growth diagram corresponding to the insertion of some hyperoctahedral permutation $`\pi `$. ∎

###### Lemma 7.

Let $`\pi `$ be a hyperoctahedral permutation. Domino insertion possesses the symmetry property

$$P_d^r(\pi )=Q_d^r(\pi ^{inv}).$$

###### Proof.

This is a consequence of the fact that the growth diagram local rules are symmetric. ∎

###### Lemma 8.

Domino insertion for hyperoctahedral permutations $`\pi `$ possesses the color-to-spin property:

$$tc(\pi )=sp(P_d^r(\pi ))+sp(Q_d^r(\pi )).$$

###### Proof.

Let $`\lambda =\lambda _{(i,j)}`$, $`\mu =\lambda _{(i+1,j)}`$, $`\nu =\lambda _{(i,j+1)}`$, $`\rho =\lambda _{(i+1,j+1)}`$ be the corners of a square of the growth diagram. Then the Lemma follows from the observation that

$$sp(\rho /\mu )+sp(\rho /\nu )=sp(\mu /\lambda )+sp(\nu /\lambda )+\{\begin{array}{cc}1\hfill & \text{if }M(i,j)=1\hfill \\ 0\hfill & \text{otherwise}.\hfill \end{array}$$

This can be checked by considering the local rules case by case. ∎

###### Lemma 9.

Let $`\pi =\pi _1\mathrm{}\pi _n`$ be a colored permutation. Then $`\pi _i^{neg}<\pi _{i+1}^{neg}`$ if and only if $`dom_i`$ lies to the left of $`dom_{i+1}`$ in $`Q_d^r(\pi )`$.

###### Proof.

The main idea is to analyze a $`1\times 2`$ rectangle of the growth diagram. Let $`\lambda _0=\lambda _{(i,j)}`$, $`\lambda _1=\lambda _{(i+1,j)}`$, $`\lambda _2=\lambda _{(i+2,j)}`$, $`\mu _0=\lambda _{(i,j+1)}`$, $`\mu _1=\lambda _{(i+1,j+1)}`$ and $`\mu _2=\lambda _{(i+2,j+1)}`$ be the corners of a $`1\times 2`$ rectangle of the growth diagram. We will call the two squares of the $`1\times 2`$ rectangle the first and second squares. We further assume that $`M(i,j)=M(i+1,j)=0`$.

Now suppose that $`\alpha _0=\lambda _1/\lambda _0`$ and $`\alpha _1=\lambda _2/\lambda _1`$ are both dominoes so that $`\alpha _0`$ lies to the left of $`\alpha _1`$. Then it is easy to check that $`\beta _0=\mu _1/\mu _0`$ and $`\beta _1=\mu _2/\mu _1`$ are both dominoes since $`M(i,j)=M(i+1,j)=0`$. We claim that in fact $`\beta _0`$ lies to the left of $`\beta _1`$. If $`\lambda _0=\mu _0`$ this is trivial and most of the cases of the local rules are a simple verification.

The only interesting case is when $`\lambda _1=\mu _1`$ and $`\alpha _0`$ is a vertical domino. In this case, $`\beta _0`$ has moved to the right when compared to $`\alpha _0`$. The key observation is that $`\beta _0`$ is placed in the column immediately to the right of $`\alpha _0`$, so it is either still to the left of $`\alpha _1`$ or it overlaps $`\alpha _1`$. When overlap occurs, $`\beta _1`$ will be moved further to the right and $`\beta _0`$ will remain to the left of $`\beta _1`$. This proves our claim.

To show (one direction of) our lemma, we just need to check, case by case, that the initial condition ($`\alpha _0`$ lying to the left of $`\alpha _1`$) holds for $`j=\mathrm{max}(\pi _i^{ev},\pi _{i+1}^{ev})+1`$. As adding a new domino to the first column will be furthest to the left, and adding a new domino to the first row will be the furthest right this is a simple verification. The claim implies inductively that the same will continue to hold when we get to $`\lambda _{(i,n+1)}`$, $`\lambda _{(i+1,n+1)}`$ and $`\lambda _{(i+2,n+1)}`$, which give exactly $`dom_i`$ and $`dom_{i+1}`$ of $`Q_d^r(\pi )`$.

The other direction of the lemma is proven in exactly the same way, or one could replace ‘left’ by ’above’ and ‘row’ by ‘column’. ∎

###### Lemma 10.

Let $`\pi =\pi _1\mathrm{}\pi _n`$ be a colored permutation. Then $`\left(\pi ^{inv_r}\right)_i^{neg}<\left(\pi ^{inv_r}\right)_{i+1}^{neg}`$ if and only if $`dom_i`$ lies to the left of $`dom_{i+1}`$ in $`P_d^r(\pi )`$.

###### Proof.

This is a consequence of Lemma 9 and Lemma 7. ∎

We are now ready to prove the semistandard domino-Schensted correspondence.

###### Proof of Theorem 3.

That the correspondence exists for standard biwords is Lemma 6. Then the color-to-spin property follows from Lemma 8.

For the semistandard case, fix two weights $`\mu `$ and $`\lambda `$ and let these be the weights of the upper and lower words of a colored biword $`𝐰`$. We define $`P_d^r(𝐰)`$ by standardising the top row first:

$$P_d^r(𝐰)=Q_d^r(𝐰^{\overline{st}inv_r}).$$

This is well defined since $`𝐰^{\overline{st}inv_r}`$ has a colored permutation as its lower word. It is a semistandard domino tableaux because of Lemma 9. This allows us to define $`Q_d^r(𝐰)`$ by

$$Q_d^r(𝐰)=P_d^r(𝐰^{inv_r}).$$

Next we show that these definitions commute with standardisation. For example,

$`P_d^r(𝐰)^{st}`$ $`=Q_d^r(𝐰^{\overline{st}inv_r})^{st}`$
$`=Q_d^r(𝐰^{\overline{st}inv_r\overline{st}})`$
$`=Q_d^r(𝐰^{stinv_r})`$
$`=P_d^r(𝐰^{st}).`$
We have used Lemmas 1 and 7. A similar calculation proves that $`Q_d^r(𝐰)^{st}=Q_d^r(𝐰^{st})`$.

Since standardisation is injective (for both words and tableaux) when the weights $`\mu `$ and $`\lambda `$ are fixed, this proves that the correspondence

$$𝐰(P_d^r(𝐰),Q_d^r(𝐰))$$

is injective for colored biwords with fixed weights for the top and bottom rows. The color-to-spin property is also a consequence of the standardisation procedure, as $`tc(𝐰)=tc(𝐰^{st})=sp(P_d^r(𝐰^{st}))+sp(Q_d^r(𝐰^{st}))=sp(P_d^r(𝐰))+sp(Q_d^r(𝐰^{st}))`$.

Finally, one can show that correspondence is a surjection as follows. Suppose we are given a pair $`(P,Q)`$ of semistandard domino tableaux of shape $`sh(P)=sh(Q)𝒫_r(n)`$ such that $`wt(P)=\lambda `$ and $`wt(Q)=\mu `$. Then we may obtain a colored biword $`𝐯`$ with standardised lower word by performing the inverse correspondence (in the standard case) to $`(Q^{st},P^{st})`$. That the upper word can be converted to have weight $`\lambda `$ is a consequence of the ‘only if’ part of Lemma 9. Thus $`𝐯`$ satisfies $`P_d^r(𝐯)=Q^{st}`$ and $`Q_d^r(𝐯)=P`$. Now perform the inverse correspondence to $`(P^{st},Q^{st})`$, using Lemma 9 to prove that we can change the upperword of $`𝐯^{inv_r}`$ into weight $`\mu `$.

This completes the proof. ∎

An alternative way of proving the surjectiveness of the correspondence is by enumerating both colored words and pairs of tableaux of the same shape. Littlewood’s 2-quotient map will accomplish the latter.

For the case $`r=0`$, it is easy to see that the definition used in the proof agrees with that of Shimozono and White \[SW\].

###### Corollary 11.

The semistandard domino correspondence possesses the symmetry property:

$$P_d^r(𝐰)=Q_d^r(𝐰^{inv_r}).$$

###### Proof.

This is a consequence of the definition used in the proof. ∎

### 3.2. Dual domino-Schensted correspondence

In this section we give a description of two closely related dual domino-Schensted correspondences. They are bijections between certain words and pairs of tableaux of the same shape, one of which is semistandard and the other is column-semistandard. For a description of the dual RSK correspondence for Young tableaux see \[EC2\].

A domino tableaux $`D`$ is *column-semistandard* if its transpose is semistandard.

A *dual colored biword* is a colored biword such that the top row is ordered as usual, but when the bottom row is used to order two biletters, the reverse ordering is chosen. Thus $`\left(\genfrac{}{}{0pt}{}{x}{y}\right)`$ precedes $`\left(\genfrac{}{}{0pt}{}{k}{l}\right)`$ if

1. $`x<k`$, or
2. $`x=k`$ and $`y^{neg}>l^{neg}`$.

The operator $`\overline{st}`$ is defined for dual colored biwords as usual by standardising the top row. The operation $`inv_d`$ changes dual colored biwords to colored biwords and vice versa. It swaps the two letters of each biletter, moving the bar to the lower letter if needed, and orders the biletters accordingly.

A colored biword or dual colored biword is called multiplicity-free if any biletter $`\left(\genfrac{}{}{0pt}{}{i}{j}\right)`$ occurs at most once. The same numbers may appear up to twice, but one must be barred and the other non-barred. For multiplicity-free biwords we define the following new standardisation operation $`std`$ by

$$𝐰^{std}=𝐰^{\overline{st}inv_d\overline{st}inv_d}.$$

###### Lemma 12.

Let $`𝐰`$ be a multiplicity free dual colored biword or colored biword. Then

$`𝐰^{std}`$ $`=𝐰^{inv_d\overline{st}inv_d\overline{st}}`$
$`𝐰^{stdinv_d}`$ $`=𝐰^{inv_dstd}.`$
###### Proof.

The proof is a direct verification, and very similar to Lemma 1. ∎

We may now define the two dual domino-Schensted correspondences $`\alpha `$ and $`\beta `$. Let $`𝐰`$ be a multiplicity-free dual colored biword. Then we define $`Q_\alpha ^r(𝐰)`$ via domino-Schensted applied to $`𝐰^{\overline{st}}`$ where $`𝐰^{\overline{st}}`$ is now treated as a colored biword. To see that $`Q_\alpha ^r(𝐰)`$ is a column-semistandard domino tableaux, we use Lemma 9. Also define $`P_\alpha ^r(𝐰)=P_d^r(𝐯)`$, where $`𝐯`$ is the lower word of $`𝐰`$.

Now let $`𝐰`$ be a multiplicity-free colored biword. We define the correspondence $`\beta `$ in a similar way. Set $`Q_\beta ^r(𝐰)`$ to be $`Q_d^r(𝐰^{inv_d\overline{st}inv_d})`$. We define $`P_\beta ^r(𝐰)`$ by turning $`P_d^r(𝐰^{inv_d\overline{st}inv_d})`$ into a column-semistandard tableaux of the same weight as the lower word of $`𝐰`$. That this is possible is a consequence of Lemma 10.

Note that both correspondences agree with the usual domino correspondence when applied to hyperoctahedral permutations.

###### Theorem 13.

Let $`r0`$ be fixed. The map $`\alpha `$

$$\alpha :𝐰(P_\alpha ^r(𝐰),Q_\alpha ^r(𝐰))$$

is a weight preserving bijection between multiplicity-free dual colored biwords $`𝐰`$ of length $`n`$ and pairs of tableaux $`(P,Q)`$ of the same shape $`\lambda 𝒫_r(n)`$ such that $`P`$ is semistandard and $`Q`$ is column-semistandard.

The map $`\beta `$

$$\beta :𝐰(P_\beta ^r(𝐰),Q_\beta ^r(𝐰))$$

is a weight preserving bijection between multiplicity-free dual colored biwords $`𝐰`$ of length $`n`$ and pairs of tableaux $`(P,Q)`$ of the same shape $`\lambda 𝒫_r(n)`$ such that $`P`$ is column-semistandard and $`Q`$ is semistandard.

These maps satisfy the following properties:

1. They commute with standardisation. Thus

$$(P_\alpha ^r(𝐰)^{st},Q_\alpha ^r(𝐰)^{st})=(P_d^r(𝐰^{std}),Q_d^r(𝐰^{std}))$$

and similarly for $`\beta `$.
2. The maps $`\alpha `$ and $`\beta `$ are related by

$$(Q_\alpha ^r(𝐰),P_\alpha ^r(𝐰))=(P_\beta ^r(𝐰^{inv_d}),Q_\beta ^r(𝐰^{inv_d})).$$
3. Both maps have the color-to-spin property.

###### Proof.

The proof is analogous to that of Theorem 3, requiring use of Lemmas 9 and 10. ∎

### 3.3. Statistics on Domino Tableaux

In this subsection we will introduce and study a number of statistics on partitions and domino tableaux. Let $`\lambda `$ be a partition with 2-core $`\stackrel{~}{\lambda }`$. Let $`o(\lambda )`$ be the number of odd rows of $`\lambda `$ . Thus $`o(\lambda ^{})`$ is the number of odd columns. Let

$$d(\lambda )=\underset{i=1}{\overset{l(\lambda /2)}{}}\frac{\lambda _{2i}}{2}.$$

Note that $`d(\lambda )=d(\lambda ^{})`$ (see for example \[Sta\]). Also let

$$v(\lambda )=\underset{i=1}{\overset{l(\lambda )}{}}\frac{\lambda _i}{2}.$$

Now let $`D`$ be a domino tableaux of shape $`\lambda `$. As before $`v(D)`$ is the number of vertical dominoes in $`D`$ and $`sp(D)=v(D)/2`$. Let $`ov(D)`$ and $`ev(D)`$ be the number of vertical dominoes in odd and even columns respectively. Thus $`sp(D)=(ov(D)+ev(D))/2`$. Let $`mspin(\lambda )`$ be the maximum spin over all domino tableaux of shape $`\lambda `$. Similarly, let $`ov(\lambda )`$ be the maximum of $`ov(D)`$ over all domino tableau of shape $`\lambda `$. Define $`ev(\lambda )`$ similarly. The cospin of a domino tableaux $`D`$ is $`cosp(D)=mspin(\lambda )sp(D)`$ (and is always an integer).

The following lemma is a strengthening of a lemma in \[Whi\].

###### Lemma 14.

Let $`D`$ be a domino tableaux of shape $`\lambda `$ with 2-core $`\stackrel{~}{\lambda }`$. Then

(1)
$$ov(D)ev(D)=\frac{o(\lambda )o(\stackrel{~}{\lambda })}{2}.$$

###### Proof.

We proceed by induction on the size of $`\lambda `$, while keeping $`\stackrel{~}{\lambda }`$ fixed. When $`D`$ has shape $`\stackrel{~}{\lambda }`$ then both sides are 0. Now let $`D`$ have shape $`\lambda `$ and suppose the Lemma is true for all shapes $`\mu `$ that can be obtained from $`\lambda `$ by removing a domino. Let $`\gamma `$ be the domino with the largest value in $`D`$. Removing $`\gamma `$ from $`D`$ gives a domino tableaux $`D^{}`$ for which (1) holds. If $`\gamma `$ is a horizontal domino then neither side changes. If $`\gamma `$ is a vertical domino in an odd row then both sides decrease by 1 (changing from $`D`$ to $`D^{}`$). If $`\gamma `$ is a vertical domino in an even row then both sides increase by 1. ∎

Note that this implies that a domino tableaux $`D`$ which has the maximum spin (amongst all domino tableaux of shape $`\lambda `$) will also have the most number of odd vertical and even vertical dominoes. Thus for example, $`mspin(\lambda )=ev(\lambda )+ov(\lambda )`$.

### 3.4. Symmetric Growth Diagrams

We now specialise to the case where the matrix $`M_\pi (i,j)`$ corresponds to a hyperoctahedral involution $`\pi `$. Thus $`M_\pi (i,j)`$ is symmetric and $`\pi `$ satisfies $`\pi ^2=1`$ in the group $`B_n`$. The hyperoctahedral involution $`\pi `$ will consist of a number of fixed points, barred fixed points, two-cycles and barred two-cycles. For example, let $`\pi =(1\overline{6}\overline{3}54\overline{2}\overline{7})`$. Then $`\pi `$ has one fixed point, two barred fixed points, one two-cycle and one barred two-cycle.

In this case we obtain the following proposition, part of which was first observed by van Leeuwen \[vL\].

###### Proposition 15.

Let $`\pi B_n`$ be a hyperoctahedral involution. Suppose $`\pi `$ has $`a`$ fixed points, $`b`$ barred fixed points, $`c`$ two-cycles and $`d`$ barred two-cycles. Fix a 2-core $`\delta _r`$. Let the insertion tableaux $`P_d^r(\pi )=Q_d^r(\pi )`$ of $`\pi `$ into $`\delta _r`$ have shape $`\lambda =sh(P_d^r(\pi ))`$ (which satisfies $`\stackrel{~}{\lambda }=\delta _r`$). Then

$`sp(P_d^r(\pi ))`$ $`={\displaystyle \frac{b}{2}}+d`$
$`{\displaystyle \frac{o(\lambda )o(\delta _r)}{2}}`$ $`=b`$
$`{\displaystyle \frac{o(\lambda ^{})o(\delta _r)}{2}}`$ $`=c`$
$`d(\lambda )d(\delta _r)`$ $`=c+d.`$
###### Proof.

Since $`P_d^r(\pi )=Q_d^r(\pi )`$ for a hyperoctahedral involution by Lemma 7, the first equation is a consequence of the color-to-spin property of Theorem 2. For the other statements, note that the symmetry of $`M_\pi (i,j)`$ and of the local rules of the growth diagram imply that the growth diagram $`\lambda _{(i,j)}`$ itself is symmetric. We focus our attention on the partitions $`\lambda _{(i,i)}`$. If $`M_\pi (i,i)=1`$ then $`\lambda _{(i+1,i+1)}`$ has two boxes added to its first row, and so $`o(\lambda _{(i+1,i+1)}^{})=o(\lambda _{(i,i)}^{})+2`$. Similarly, if $`M_\pi (i,i)=1`$ then $`o(\lambda _{(i+1,i+1)})=o(\lambda _{(i,i)})+2`$. In both cases $`d(\lambda _{(i,i)})=d(\lambda _{(i+1,i+1)})`$.

If $`M_\pi (i,i)=0`$ and $`\lambda _{(i+1,i)}=\lambda _{(i,i)}=\lambda _{(i,i+1)}`$ then $`\lambda _{(i,i)}=\lambda _{(i+1,i+1)}`$. The only remaining case is if $`\lambda _{(i+1,i)}`$ differs from $`\lambda _{(i,i)}`$ by a domino, in which case $`\lambda _{(i,i+1)}=\lambda _{(i+1,i)}`$ as well. This implies that $`\lambda _{(i+1,i+1)}`$ differs from $`\lambda _{(i,i)}`$ by two dominoes in two adjacent columns or rows. Regardless, the number of odd columns and rows is unchanged while $`d(\lambda _{(i+1,i+1)})=d(\lambda _{(i,i)})+1`$. ∎

###### Corollary 16.

Let $`D=P_d(\pi )`$ correspond to a hyperoctahedral involution $`\pi `$ with $`b`$ barred fixed points and $`d`$ barred two-cycles. Then

$`ev(D)`$ $`=d.`$
$`ov(D)`$ $`=b+d.`$
###### Proof.

As before, let $`\pi `$ have $`b`$ barred fixed points. Then by Proposition 15,

$$ev(D)+ov(D)=2sp(D)=b+2d.$$

Combining Lemma 14 with Proposition 15 again we have,

$$ov(D)ev(D)=\frac{o(\lambda )o(\stackrel{~}{\lambda })}{2}=b.$$

Subtracting the two equations and dividing by two, we obtain the first result. Summing the two equations give the second result. ∎

The significance of this Corollary will become apparent in Section 4.

### 3.5. Some Enumeration for Domino Tableaux

Let $`f^\lambda `$ be the number of SYT of shape $`\lambda `$. The Robinson-Schensted algorithm for standard Young tableaux (SYT) leads to a number of enumerative results including the following well known result.

###### Proposition 17.

Let $`n1`$. Then

(2)
$$\underset{\lambda n}{}(f^\lambda )^2=n!.$$

(3)
$$\underset{\lambda n}{}f^\lambda =t(n).$$

We can easily generalise these to domino tableaux. Define

$$d^\lambda (q)=\underset{SDTD:sh(D)=\lambda }{}q^{spin(D)}.$$

It is unlikely that a ‘hook-length’ formula holds for $`d^\lambda (q)`$. Note that $`d^\lambda (q)`$ depends on more than just the 2-quotient $`(\lambda ^{(0)},\lambda ^{(1)})`$ of $`\lambda `$. For example, $`(3,1,1)`$ and $`(2,2)`$ have the same 2-quotient but $`d^{(3,1,1)}(q)=2q^{1/2}`$ and $`d^{(2,2)}(q)=1+q`$. A cospin version of $`d^\lambda (q)`$ for more general ribbon tableaux was studied by Schilling, Shimozono and White in \[SSW\].

We have the following analogue of (2):

###### Proposition 18.

Let $`n1`$ and $`r0`$ be fixed. Then

$$\underset{\lambda }{}\left(d^\lambda (q)\right)^2=(1+q)^nn!$$

where the sum is over all partitions $`\lambda 𝒫_r(n)`$.

###### Proof.

This is an immediate consequence of the bijection in Theorem 2. ∎

Now define $`h_r(n)`$ as follows:

$$h_r(n)=\underset{\lambda 𝒫_r(n)}{}a^{(o(\lambda )o(\delta _r))/2}b^{(o(\lambda ^{})o(\delta _r))/2}c^{d(\lambda )d(\delta _r)}d^\lambda (q).$$

When $`a=b=c=q=1`$, this is the number of hyperoctahedral involutions in $`B_n`$ and thus a domino analogue of $`t(n)`$.

###### Proposition 19.

The function $`h(n)=h_r(n)`$ does not depend on $`r`$. It satisfies the recursion

$$h(n+1)=(b+aq^{1/2})h(n)+nc(1+q)h(n1).$$

The exponential generating function defined as

$$E_h=h(n)\frac{t^n}{n!}$$

is given by the formula

$$E_h=exp\left((b+aq^{1/2})t+c(1+q)\frac{t^2}{2}\right).$$

###### Proof.

That $`h_r(n)`$ does not depend on $`r`$ follows from the fact that the tableaux being enumerated are in bijection with hyperoctahedral involutions. Furthermore, the bijection preserves the appropriate weighting according to Proposition 15. Thus we are in fact enumerating hyperoctahedral involutions.

The recursion for $`h(n)`$ is immediate from the construction of a hyperoctahedral involution from barred and non-barred fixed points and two-cycles.

For the exponential generating function, we can use the exponential formula (see \[EC2, Corollary 5.1.6\]). Thus we think of a hyperoctahedral involution as a partition of $`[n]`$ into one and two element subsets. The one element subsets can be given a weight of $`b`$ or $`aq^{1/2}`$ while the two element subsets can be given a weight of $`c`$ or $`cq`$. ∎

## 4. Sign-Imbalance and Stanley’s Conjecture

Sign Imbalance can be defined for posets in general, but we will only concern ourselves with the posets arising from partitions.

Let $`T`$ be a standard Young tableaux. Its reading word $`reading(T)`$, for our purposes, will be obtained by reading the first row from left to right, then the second row, and so on. We set $`sign(T)=sign(reading(T))`$ where $`reading(T)`$ is treated as a permutation.

Let $`\lambda `$ be a partition. Then we set

$$I_\lambda =\underset{T}{}sign(T)$$

where the sum is over all standard Young tableaux $`T`$ of shape $`\lambda `$. We say $`I_\lambda `$ is the *sign-imbalance* of $`\lambda `$.

It is not difficult to see that $`I_\lambda `$ is related to domino tableaux. Suppose $`\lambda `$ has no 2-core, then define an involution on standard Young tableaux of shape $`\lambda `$ by swapping $`2i1`$ with $`2i`$ for the smallest possible value of $`i`$ where this is possible. If no such swap is possible the tableaux is fixed by the involution.

The fixed points correspond exactly to the standard domino tableaux of shape $`\lambda `$. We obtain a standard Young tableaux $`T(D)`$ from a standard domino tableaux $`D`$, by filling the domino with a 1 with the values 1 and 2, the domino with a 2, with the values 3 and 4, and so on.

When $`\lambda `$ has 2-core $`\delta _1`$ (a single box) then we use an involution which swaps $`2i`$ with $`2i+1`$ for the smallest value of $`i`$ where it is possible. Again, the fixed points are the standard domino tableaux of shape $`\lambda `$.

It is easy to see that these involutions are sign-reversing on tableaux which are not fixed points and thus we obtain the following proposition.

###### Proposition 20.

Let $`r\{0,1\}`$, $`n1`$ and $`\lambda 𝒫_r(n)`$. Then

$$I_\lambda =\underset{sh(D)=\lambda }{}sign(D)$$

where the sum is over standard domino tableaux of shape $`\lambda `$ and the sign of a domino tableaux $`D`$ is the sign of the corresponding standard Young tableaux $`T(D)`$ .

For other values of $`r`$, we have the following result, see \[Sta\]:

###### Proposition 21.

Let $`\lambda `$ have 2-core $`\delta _r`$ for $`r>1`$, then

$$I_\lambda =0.$$

There is another natural involution on standard Young tableaux of which standard domino tableaux are the fixed points. This is Schützenberger’s involution $`S`$, also known as evacuation. The fixed points of this involution are exactly the domino tableaux of shape $`\lambda `$ satisfying $`\stackrel{~}{\lambda }=\delta _r`$ for $`r\{0,1\}`$ (see \[vL\]). For a fixed shape $`\lambda `$, Stanley \[Sta\] has shown that $`S`$ is either always parity-reversing or parity-preserving.

By analysing the positions of horizontal and vertical dominoes in a standard domino tableaux, White \[Whi\] proves the following proposition.

###### Proposition 22.

Let $`D`$ be a domino tableaux of shape $`\lambda `$ which has 2-core $`\mathrm{}`$ or $`\delta _1`$. Then

$$sign(D)=(1)^{ev(D)}.$$

White has also given an explicit formula (in terms of shifted tableaux) for the sign-imbalance of partitions which have ‘near-rectangular’ shape.

Combining Proposition 22 with Corollary 16 we obtain the following theorem.

###### Theorem 23.

Fix $`r\{0,1\}`$. Let $`\pi `$ be a hyperoctahedral involution. Then the sign of its insertion tableaux $`sign(P_d^r(\pi ))`$ is equal to the number of barred 2-cycles.

###### Proof.

This follows immediately from Corollary 16 and Proposition 22. ∎

We can now prove the following conjecture of Stanley \[Sta\], known as the ‘$`2^{n/2}`$’ conjecture.

###### Theorem 24.

Let $`m1`$ be an integer. Then

$$\underset{\lambda m}{}x^{v(\lambda )}y^{v(\lambda ^{})}q^{d(\lambda )}t^{d(\lambda ^{})}I_\lambda =(x+y)^{m/2}.$$

Note that $`d(\lambda )=d(\lambda ^{})`$ so that one of $`q`$ and $`t`$ is not needed.

###### Proof.

Since $`I_\lambda =0`$ for $`\lambda `$ with a 2-core larger than $`\delta _1`$, we may assume the sum is over $`\lambda 𝒫_r(n)`$, for the unique $`r\{0,1\}`$ and $`n`$ satisfying $`2n+r=m`$. Note that $`o(\delta _1)=o(\delta _1^{})=1`$ and $`d(\delta _1)=0`$.

The standard domino tableaux of such shape correspond exactly to hyperoctahedral involutions $`\pi B_n`$. We define an involution $`\alpha `$ on all such $`\pi `$ by turning the two-cycle $`(i,j)`$ with the smallest value of $`i`$ from barred to non-barred or vice versa, if such an $`i`$ exists. By Theorem 23, $`\alpha `$ is sign-reversing for domino tableaux which are not fixed points. Furthermore, by Proposition 15, all of the statistics $`o(\lambda )r`$, $`o(\lambda ^{})r`$ and $`d(\lambda )`$ remain fixed by $`\alpha `$.

The fixed points of $`\alpha `$ are exactly the hyperoctahedral involutions without two-cycles. Hence we obtain, using Proposition 15

$$a^{(o(\lambda )r)/2}b^{(o(\lambda ^{})r)/2}c^{d(\lambda )}I_\lambda =(a+b)^n.$$

To change this into the form of Stanley’s conjecture, observe that $`2v(\lambda )+o(\lambda )=m=2n+r`$ implying that $`(o(\lambda )r)/2=nv(\lambda )`$ and similarly for $`v(\lambda ^{})`$ and $`o(\lambda ^{})`$. Now substitute this and also $`x=1/a`$ and $`y=1/b`$. Finally multiply both sides by $`(xy)^n`$. ∎

Note that the fixed points of $`\alpha `$ in the proof are exactly the domino tableaux which are hook shaped. That these give the right hand side of the conjecture was shown by Stanley \[Sta\]. When we set $`x=y=q=1`$ we obtain the following signed analogue of (3):

$$\underset{SYTT}{}sign(T)=2^{n/2}$$

where the sum is over all standard Young tableaux $`T`$ of size $`n`$.

## 5. Domino Generating Functions

Let $`\mathrm{\Lambda }`$ denote the ring of symmetric functions in a set of variables $`X=(x_1,x_2,\mathrm{})`$ taking coefficients in $``$ (though the coefficient field will not affect the results). Its completion, $`\stackrel{~}{\mathrm{\Lambda }}`$ includes symmetric power series of unbounded degree (though the coefficient of a monomial $`m_\lambda `$ will always be well defined).

Carré and Leclerc have defined symmetric functions $`H_\lambda (X;q)`$ via semistandard domino tableaux, in the same way that Schur functions arise from semistandard Young tableaux. Slightly more general functions $`G_\lambda (X;q)`$ were used in \[LLT\] and the two are connected via $`H_\lambda (X;q)=G_{2\lambda }(X;q)`$.

Let $`\lambda `$ be a partition. Define

$$G_\lambda =\underset{D}{}q^{sp(D)}x^{wt(D)}$$

where the sum is over all semistandard domino tableaux of shape $`\lambda `$ and $`x^\mu :=x_1^{\mu _1}x_2^{\mu _2}\mathrm{}`$ for a partition $`\mu `$. There is a cospin version of this function which we will not need. In the notation of \[LLT\], our $`G_\lambda `$ would be denoted $`G_{\lambda /\stackrel{~}{\lambda }}`$.

That the $`G_\lambda `$ are symmetric functions is a consequence of a combinatorial interpretation of their expansion into Schur functions given by Carré and Leclerc. As spin is not always integral, the $`G_\lambda `$ lie in the ring $`\mathrm{\Lambda }[q^{1/2}]`$. We will call the $`G_\lambda `$ *domino functions*. Theorem 3 leads immediately to the following *domino Cauchy identity*.

###### Proposition 25.

Fix $`r0`$. Then

$$\underset{\lambda 𝒫_r}{}G_\lambda (X;q)G_\lambda (Y;q)=\frac{1}{_{i,j}(1x_iy_j)(1qx_iy_j)}.$$

The dual domino-Schensted correspondence of Theorem 13 leads to the following *dual domino Cauchy identity*.

###### Proposition 26.

Fix $`r0`$. Then

$$\underset{\lambda 𝒫_r}{}q^{|\lambda /\delta _r|/2}G_\lambda (X;q)G_\lambda ^{}(Y;q^1)=\underset{i,j}{}(1+x_iy_j)(1+qx_iy_j).$$

###### Proof.

This follows from the fact that a column-semistandard domino tableaux $`D`$ with $`m`$ dominoes is a semistandard domino tableaux $`D^{}`$ of the conjugate shape with spin given by

$$sp(D^{})=\frac{m}{2}sp(D).$$

In \[KLLT\], Kirillov, Lascoux, Leclerc and Thibon give two product expansions for certain sums of the $`G_\lambda `$. These will be seen as specialisations of our Theorem 28. As the paper \[KLLT\] contains no proofs, our theorem can be considered both as a proof and as a generalisation.

We begin by studying closely the effect of standardisation on a semistandard colored involution.

A colored word $`𝐰`$ is said to be a colored involution if $`𝐰=𝐰^{inv_r}`$. Every such word is given by the number of fixed points $`\left(\genfrac{}{}{0pt}{}{i}{i}\right)`$, barred fixed points $`\left(\genfrac{}{}{0pt}{}{i}{\overline{i}}\right)`$, two-cycles $`\left(\genfrac{}{}{0pt}{}{i}{j}\right)\mathrm{}\left(\genfrac{}{}{0pt}{}{j}{i}\right)`$ and barred two-cycles $`\left(\genfrac{}{}{0pt}{}{i}{\overline{j}}\right)\mathrm{}\left(\genfrac{}{}{0pt}{}{j}{\overline{i}}\right)`$. Let there be $`a_i`$, $`b_i`$, $`c_{ij}`$ and $`d_{ij}`$ of these respectively. Thus $`c_{ij}=c_{ji}`$ and $`d_{ij}=d_{ji}`$.

###### Lemma 27.

Let $`𝐰`$ be a colored involution. Then its standardisation $`𝐰^{st}`$ is a signed involution with $`a`$ fixed points, $`b`$ barred fixed points, $`c`$ two-cycles and $`d`$ barred two-cycles, where:

$$a=\underset{i}{}a_i,$$

$$b=\underset{i}{}b_i2\underset{i}{}\frac{b_i}{2}$$

$$c=\underset{i<j}{}c_{ij}$$

$$d=\underset{i<j}{}d_{ij}+\underset{i}{}\frac{b_i}{2}.$$

In other words, the only change that occurs is that of barred fixed points becoming barred two-cycles.

###### Proof.

It is clear from Lemma 1 that $`𝐰^{st}`$ is also an involution.

Fix an integer $`i`$. Then in the colored word $`𝐰`$, the fixed points of the form $`\left(\genfrac{}{}{0pt}{}{i}{i}\right)`$ have exactly

$$A=\underset{j<i}{}(a_j+b_j+c_{jk}+d_{jk})+b_i+\underset{k}{}d_{ik}+\underset{k<i}{}c_{ki}$$

biletters in front. If we look at $`𝐰^{\overline{st}inv}`$ the same formula holds using a different ordering for the top row. Thus when we standardise and take inverse and standardise again, this set of biletters will receive identical numbers for both the top and bottom row, and will give us $`a_i`$ fixed points.

Now consider barred fixed points $`\left(\genfrac{}{}{0pt}{}{i}{\overline{i}}\right)`$. There are

$$A=\underset{j<i}{}(a_j+b_j+c_{jk}+d_{jk})+\underset{k>i}{}d_{ik}$$

biletters in front. Now let us consider what happens when we standardise the top row and take the inverse. We will similarly get all (barred or otherwise) fixed points of $`j<i`$ in front and so on. The only possible difference are the biletters involving $`i`$. The fixed points clearly make no contribution. Since the ordering for the lower letter is reversed when the upper letter is barred, the biletters occuring in front are only those of the form $`\left(\genfrac{}{}{0pt}{}{\overline{i}}{j}\right)`$ where $`j>i`$. There are exactly $`_{k>i}d_{ik}`$ of these, thus the collection of barred fixed points $`\left(\genfrac{}{}{0pt}{}{i}{\overline{i}}\right)`$ will get the same set of numbers for the upper and lower biletters. However, individually, the numbers assigned for the two rows will be reversals of each other due to the ordering on the bottom row induced by the bars on the upper row.

Now consider what happens to the collection of biletters of the form $`\left(\genfrac{}{}{0pt}{}{i}{j}\right)`$ and $`ij`$. We need only show that these all become two-cycles when $`𝐰`$ is standardised. Since $`𝐰^{st}`$ is an involution we only need to check that these biletters do not become fixed points. Such a biletter has between

$$A=\underset{l<i}{}(a_l+b_l+c_{lk}+d_{lk})+b_i+\underset{k}{}d_{ik}+\underset{k<j}{}c_{ki}$$

and

$$B=\underset{l<i}{}(a_l+b_l+c_{lk}+d_{lk})+b_i+\underset{k}{}d_{ik}+\underset{k<j}{}c_{ki}+c_{ij}1$$

biletters in front. After standardisation, exactly the same formula holds with $`i`$ swapped with $`j`$. We see that the top and bottom letters will never get the same number via standardisation (in fact if $`i<j`$ then $`i`$ will become a smaller number than what $`j`$ becomes).

Exactly the same analysis holds for a biletter of the form $`\left(\genfrac{}{}{0pt}{}{i}{\overline{j}}\right)`$ and $`ij`$. ∎

As an example, let $`𝐰`$ be the colored involution

$$𝐰=\left(\begin{array}{ccccccccc}1& 1& 2& 2& 2& 3& 3& 4& 5\\ \overline{3}& 3& \overline{2}& \overline{2}& \overline{2}& \overline{1}& 1& 5& 4\end{array}\right)$$

with 3 barred fixed points, 2 two-cycles and 1 barred two-cycle. Then its standardisation

$$𝐰^{st}=\left(\begin{array}{ccccccccc}1& 2& 3& 4& 5& 6& 7& 8& 9\\ \overline{6}& 7& \overline{5}& \overline{4}& \overline{3}& \overline{1}& 2& 9& 8\end{array}\right)$$

has 1 barred fixed point, 2 two-cycle and 2 barred two-cycles.

###### Theorem 28.

Let $`r0`$ be fixed. Let $`S(X;a,b,c,q)\stackrel{~}{\mathrm{\Lambda }}[X][a,b,c,q^{1/2}]`$ be the symmetric power series

$$S(X;a,b,c,q^{1/2})=\underset{\lambda 𝒫_r}{}a^{(o(\lambda )o(\delta _r))/2}b^{(o(\lambda ^{})o(\delta _r))/2}c^{d(\lambda )d(\delta _r)}G_\lambda (X;q).$$

Then $`S(X;a,b,c,q^{1/2})`$ does not depend on $`r`$ and has a product formula given by

$$\frac{_i(1+aq^{1/2}x_i)}{_i(1bx_i)_i(1cqx_i^2)_{i<j}(1cx_ix_j)i<j(1cqx_ix_j)}.$$

###### Proof.

Semistandard domino tableaux are in one-to-one correspondence with colored involutions by Theorem 3 and Corollary 11. If $`𝐰`$ is a colored involution then the shape and spin of $`P_d^r(𝐰)`$ is that of $`P_d^r(𝐰^{st})`$ and thus we may use Proposition 15 and Lemma 27 to calculate the contributions each colored involution makes to the weights $`o(\lambda )`$, $`o(\lambda ^{})`$, $`d(\lambda )`$ and $`sp(P_d^r(𝐰))`$.

Such colored involutions consist of a number of fixed points $`\left(\genfrac{}{}{0pt}{}{i}{i}\right)`$ corresponding to the product $`_i1/(1bx_i)`$. The barred fixed points $`\left(\genfrac{}{}{0pt}{}{i}{\overline{i}}\right)`$ correspond to the product $`_i(1+aq^{1/2}x_i)/(1cqx_i^2)`$ since according to Lemma 27 all but at most one of the barred fixed points of each weight will pair to become a two-cycle upon standardisation. The two-cycles correspond to $`_{i<j}1/(1cx_ix_j)`$ and the barred two-cycles correspond to $`_{i<j}1/(1cqx_ix_j)`$. ∎

There are a number of interesting specialisations. We will set $`r=0`$ for the next few examples.

1. When $`a=b=c=q^{1/2}=1`$, we obtain the square of a well known identity:

$$\left(\underset{\lambda 𝒫}{}s_\lambda (X)\right)^2=\left(\frac{1}{_i(1x_i)_{i<j}(1x_ix_j)}\right)^2.$$
2. Substituting $`q^{1/2}=0`$ and using the fact that $`G_\lambda (X;0)=s_\mu (X)`$ for $`\lambda `$ which satisfy $`\lambda =2\mu `$ (see \[CL\]), while $`G_\lambda (X;q)=0`$ for other $`\lambda 𝒫_0`$, we get

$$\underset{\lambda 𝒫}{}b^{o(\lambda )}c^{v(\lambda )}s_\lambda (X)=\frac{1}{_i(1bx_i)_{i<j}(1cx_ix_j)}.$$

This is another well known identity which can be proved using growth diagrams for normal RSK.
3. The case $`b=c=1`$ and $`a=0`$ picks out the $`G_\lambda `$ of the form $`G_{2\mu }=H_\mu `$ and we obtain the first formula of \[KLLT\]:

$$\underset{\lambda }{}H_\lambda (X;q)=\frac{1}{_i(1x_i)_{i<j}(1x_ix_j)_{ij}(1qx_ix_j)}.$$
4. The case $`a=b=0`$ and $`c=1`$ picks out the partitions of the form $`2\lambda 2\lambda `$ giving us the second formula of \[KLLT\]:

$$\underset{\lambda }{}H_{\lambda \lambda }(X;q)=\frac{1}{_{i<j}(1x_ix_j)_{ij}(1qx_ix_j)}.$$

Note that while $`G_\lambda `$ over $`\lambda 𝒫_r(n)`$ does not depend on $`r`$, the individual $`G_\lambda `$ can differ greatly. In particular, two partitions $`\lambda `$ and $`\mu `$ with the same 2-quotient but with $`\stackrel{~}{\lambda }\stackrel{~}{\mu }`$ may not have the same $`G`$ function. For example, $`G_{(2,2)}=qs_2+s_{1,1}`$ while $`G_{(3,1,1)}=q^{1/2}(s_2+s_{1,1})`$. Both $`(2,2)`$ and $`(3,1,1)`$ have 2-quotient $`\{(1),(1)\}`$.

## 6. Ribbon Tableaux

In this last section we make a few remarks concerning which results might be generalised to ribbon tableaux. We refer the reader to \[LLT\] for the important definitions.

Shimozono and White \[SW2\] also give a spin-preserving insertion algorithm for standard ribbon tableaux. Unfortunately, they stop short of giving a (spin-preserving) bijection between words and pairs of semistandard tableaux. Nevertheless, the standard correspondence works. It is a spin-preserving bijection between pairs of standard ribbon tableaux and permutations $`\pi `$ of the wreath product $`S_n\mathrm{\S }C_p`$. Again the involutions are in bijection with standard ribbon tableaux and thus we obtain a $`p`$-ribbon analogue of Proposition 19 with an identical proof.

###### Proposition 29.

Let $`h(n)`$ be the polynomial in $`q`$ defined as

$$h(n)=\underset{T}{}spin(T)$$

where the sum is over all standard ribbon tableaux of size $`n`$ (and fixed $`p`$-core). Then $`h(n)`$ satisfies the recurrence

$$h(n+1)=(1+q^{1/2}+\mathrm{}+q^{(p1)/2})h(n)+n(1+q+\mathrm{}+q^{p1})h(n1)$$

and has exponential generating function

$$E_h(t)=exp\left((1+q^{1/2}+\mathrm{}+q^{(p1)/2})t+(1+q+\mathrm{}+q^{p1})\frac{t^2}{2}\right).$$

The statistics $`o(\lambda )`$ and $`d(\lambda )`$ are no longer suitable for longer ribbons. It seems likely that the statistic

$$o_k(\lambda )=\mathrm{\#}\{i:\lambda _ikmodp\}$$

may be interesting, but we have been unable to find any applications.

As Shimozono and White’s ribbon correspondence can be phrased in terms of growth diagrams, one might hope that a Lemma similar to Lemma 9 can be shown in the same way – this would allow a semistandard ribbon correspondence to be developed. Unfortunately this appears not to be the case, as ribbons may well not ‘bump’ to the next column or row but quite far away. This phenomenon occurs for certain longer ribbons regardless of whether we insist upon column or row insertion/bumping.

Possibly more promising is the following potential generalisation. The sums over standard Young tableaux of size $`n`$

$`{\displaystyle \underset{T}{}}1`$ $`=`$ $`t(n)`$
$`{\displaystyle \underset{T}{}}sign(T)`$ $`=`$ $`2^{n/2}`$
suggest that we might consider the sum

$$\underset{T}{}\chi (reading(T))$$

for some other character $`\chi `$ of $`S_n`$. If this were to be related to $`p`$-ribbon tableaux and the wreath product $`S_n\mathrm{\S }C_p`$ then $`\chi `$ should take $`p^{th}`$ roots of unity as its values. One possibility is the (virtual) character which on the conjugacy class of cycle type $`\lambda `$ takes the value

$$\chi (C_\lambda )=\omega ^{\lambda l(\lambda )}$$

for some $`p^{th}`$ root of unity $`\omega `$.


format: text

text:
# Statistical linguistic study of DNA sequences

## 1 Introduction

In recent years, the subject of bioinformatics has emerged as an active research subject in biology and other fields such as physics. Researchers are beginning to search for DNA words  and build up dictionaries for genomes . In doing so, people are more willing to regard information stored in DNA sequences as a natural language from nature. A lot of these activities are indeed to employ statistical methods to study DNA sequences. In an early attempt, researchers  used the Zipf’s law  to study the statistical features that are embedded in DNA sequences. Other researchers  subsequently used different distributions to fit the rank of the word distributions in DNA sequences and obtained better fit than the original Zipf plot. The Zipf’s law was first proposed in 1932 when George Zipf made an empirical observation on some statistical regularities of human writings which has become the most prominent statement of statistical linguistic. In his original work, Zipf found that if the number of different words in a given text were arranged in the order of their frequency of usage, there would be an approximate mathematical relation between the frequency of occurrence of each word and its rank in the list of all the words used in the text that were ordered by decreasing frequency. He later pointed out that similar relations also hold in other contexts .

Let us associate a particular word by an index $`r`$ equal to its rank, and by $`f(r)`$ the normalized frequency of occurrence of that word, i.e., the number of times it appears in the text divided by the total number of words $`N`$. Zipf’s law states that there is an approximate relation between $`f(r)`$ and $`r`$

$$f(r)=\frac{A}{r^\alpha },$$
$`(1)`$
where $`\alpha (>1)`$ and $`A`$ are constants. The above mathematical relation was used  to study the statistical features of DNA sequences where similar scaling behavior was found. It was however noted that for sequences composed of primarily coding regions, the data were well fitted by a logarithmic function . And just like in the case of linguistic, the Zipf’s law could only account for a limited zone of the rank variable.

In the early days of quantitative linguistics, researchers, notably Yule  had suggested that the mathematical relation (1) proposed by Zipf was unsatisfactory. He conjectured that the correct distribution for word frequencies would be a compound Poisson model. However, there is no fitting of any mathematical distribution law to the extensive data in his book. Good  later proposed to overcome Yule’s objection by introducing a convergence factor into the Riemann distribution which gives

$$f(r)=Ar^\alpha \theta ^r,$$
$`(2)`$
where $`r1,0<\theta <1,\alpha >0`$ and $`A`$ is the normalization constant in terms of $`\theta `$ and $`\alpha `$. Neither Good nor any other authors have fitted (2) to any real data except for $`\theta `$ very close to one. One should also note that the primary reason to introduce $`\theta `$ was to achieve convergence and secondary to improve the fit. In , Good also proposed a distribution function to fit two sets of data but were rather poor for large values of $`r`$. Researchers in the field have also introduced other distribution functions to fit word frequencies. However, as pointed out by Herdan , the word frequency distribution functions are characterized by the properties of both combinability and divisibility without altering the essential mathematical characteristics of the distribution function. The only distribution functions have these two properties are of the compound Poisson type. With this as the starting point, Sichel  introduced a new family of compound Poisson distribution functions to fit word frequencies. He  also used this family of distribution functions to fit sentence-length, which was first considered by Yule . The fit in both cases were encouraging.

A natural question to ask is whether the quantitative studies made in linguistics can be carried out in a similar fashion in DNA sequences. In particular, we would like to know if the compound Poisson distribution functions introduced in the study of quantitative linguistics are universal, in the sense that they can be used to study human designed languages such as the languages we use everyday as well as the language used by nature—the information stored in DNA sequences. We will answer the above question by carrying out quantitative studies in DNA sequences using these compound Poisson distribution functions. In section II, we give a brief review of the family of compound Poisson distribution function used in this paper, which was first introduced by Sichel. In section III, we use this family of Poisson distribution functions to study the statistical features of the word frequencies in DNA sequences. Section IV is a statistical study of the sentence-length in DNA sequences. Section V is the discussion and summary.

## 2 The Mathematical Model

In this section, we give a brief introduction of the mathematical model that we use throughout this paper. We follow mainly the discussion by Sichel .

Let the total vocabulary that an author uses in his writing consist of $`V`$ distinct words. For each word in the vocabulary $`V`$, there is a long-term probability of occurrence $`\pi _1,\pi _2,\mathrm{},\pi _V`$ where $`\pi _1(\pi _V)`$ refers to the word with lowest and highest probability respectively. Theoretically, we have

$$0<\pi _i<1;\underset{i}{}\pi _i=1.$$
$`(3)`$
The probability of a specific word to appear $`r`$ times in a total word count of N tokens is given by,

$$\varphi (r|N)=\left(\begin{array}{c}N\\ r\end{array}\right)_0^1\pi ^r(1\pi )^{Nr}\psi (\pi )𝑑\pi .$$
$`(4)`$
Since all the $`\pi _i`$’s are small, we may replace the binomial by the Poisson distribution function. We can then write $`\lambda =N\pi `$ and Eq.(2) becomes

$$\varphi (r|N)=\frac{1}{r!}_0^1e^{N\pi }(N\pi )^r\psi (\pi )𝑑\pi =\frac{1}{r!}_0^Ne^\lambda \lambda ^rf(\lambda )𝑑\lambda .$$
$`(3)`$
For mathematical convenience, one can substitute $`N`$ by infinity in the second integral in Eq.(3) since the latter is negligibly small between $`N`$ and infinity.

The choice of the mixing distribution $`\psi (\pi )`$, or $`f(\lambda )`$, is crucial. A set of distribution functions was first suggested in . Later, Sichel expressed Good’s mixing distribution function as

$$f(\lambda )=\frac{1}{2}\frac{(2(1\theta )^{1/2}/\alpha \theta )^\gamma }{K_\gamma (\alpha (1\theta )^{1/2})}\lambda ^{\gamma 1}\mathrm{exp}\{(\frac{1}{\theta }1)\lambda \frac{\alpha ^2\theta }{4\lambda }\},$$
$`(4)`$
where $`\mathrm{}<\gamma <\mathrm{},0<\theta <1`$ and $`\alpha >0`$ are constants and $`K_\gamma `$ is the modified Bessel function of the second kind of order $`\gamma `$. In particular, if $`\gamma =\frac{1}{2}`$, $`f(\lambda )`$ will become the so-called inverse Gaussian distribution function, which has applications in many different areas . Substituting Eq.(4) into Eq.(3) and perform a Bessel function integration, one will obtain the corresponding compound Poisson distribution function

$$\varphi (r)=\frac{((1\theta )^{1/2})^\gamma }{K_\gamma (\alpha (1\theta )^{1/2})}\frac{(\alpha \theta /2)^r}{r!}K_{r+\gamma }(\alpha ),$$
$`(5)`$
where $`r0`$. This three parameter family of discrete distribution functions is extremely powerful. A number of known distribution functions such as the Poisson, negative binomial, geometric, Yule, Good and Riemann distribution functions are all special or limiting forms of Eq.(5). If the parameter $`\gamma `$ is made negative in Eq.(5), an entirely new set of discrete distribution functions is generated.

In general, the parameter $`\alpha `$ characterizes the frequency behavior for low values of $`r`$, whereas $`\theta `$ influences the tail and $`\gamma `$ is important for the entire sweep of the distribution function. For the calculation of the individual probabilities in Eq.(5), Sichel derived a very useful formula based on the following Bessel recursion relation

$$K_{\nu +1}(z)=\frac{2\nu }{z}K_\nu (z)+K_{\nu 1}(z).$$
$`(6)`$
Using this recursion relation, one can easily obtain the following recursion relation for $`\varphi (r)`$

$$\varphi (r)=\theta (\frac{r+\gamma 1}{r})\varphi (r1)+\frac{(\alpha \theta )^2}{4r(r1)}\varphi (r2).$$
$`(7)`$
Thus, as one obtains the first two probabilities $`\varphi (0)`$ and $`\varphi (1)`$ from Eq.(5), it is easy to calculate all other probabilities from Eq.(7). It is clear that the word frequency distribution functions start at $`r=1`$. A zero truncation of the function in Eq.(5) yields

$$\varphi (r)=[((1\theta )^{1/2})^\gamma K_\gamma (\alpha (1\theta )^{1/2})K_\gamma (\alpha )]^1\frac{(\alpha \theta /2)^r}{r!}K_{r+\gamma }(\alpha ),$$
$`(8)`$
for $`r0`$. This is the Sichel model for word frequencies in its most general form.

## 3 Word frequencies in DNA sequences

In this section, we use the Sichel model to study the word frequencies in DNA sequences. In order to adapt the Sichel model to the quantitative study of DNA sequences, the concept of word must first be defined. In the case of coding regions, the words are the 64 3-tuples which code for the amino acids, AAA, AAT, etc. For noncoding regions, the words are however unknown. Therefore, it is better to consider the word length $`n`$ as a free parameter and perform analyses for $`n`$ from say, 3 to 8 as was done in . The number of $`n`$-tuples will be $`4^n`$. Thus, for $`n=6`$, the number of the 6-tuples will be 4096. To obtain the word frequency for each $`n`$-tuple, we will start from the first base pair of the DNA sequence that is under study and progressively shift by 1 base with a window of length $`n`$. For a DNA sequence containing $`L`$ base pairs, the total number of words will be $`Ln+1`$.

To avoid any bias in DNA sequence selection, we performed analysis of 13 sequences of eukaryotes mammals (GenBank accession codes are HSMHCAPG, HUMGHCSA, HUMHBB, HUMHDABCD, HUMHPRTB, HUMMMDBC, HUMNEUROF, HUMRETBLAS, HUMTCRADCV, HUMVITDBP, MMBGCXD, MUSTCRA, RATCRYG), 3 sequences of invertebrate (CEC07A9, CELTWIMUSC, DROABDB), the yeast chromosome III sequence (SCCHRIII), 10 sequences of eukaryotic viruses (ASFV55KB, HE1CG, HEHCMVCG, HEVZVXX, HS1ULR, HSECOMGEN, HSGEND, IH1CG, VACCG, VVCGAA), 7 sequences of bacteria (BSGENR, ECO110K, ECOHU47, ECOUW82, ECOUW85, ECOUW87, ECOUW89), and 2 sequences of phage (LAMCG, MLCGA).

In Sichel’s model, $`\varphi (r)`$ is the fraction of the total number of words with a frequency $`r`$ of appearance in the article under study. For example, $`\varphi (1)`$ is the fraction of words among the total number of words used that appear once in the article. To implement our analysis using the Sichel model, we first record the total number ($`N`$) of words ($`n`$-tuples) among the total number of possible words that are used in the DNA sequence under study. For each frequency of appearance, we record the total number ($`N(r)`$) of words ($`n`$-tuples) that have such a frequency $`r`$ of appearance in that DNA sequence. We divide that number by $`N`$ and call it $`\varphi (r)`$ and then plot $`\varphi (r)`$ against $`r`$. $`\chi ^2`$ test is used to obtain the best fit of the data against $`\varphi (r)`$ in Eq.(5).

Table I is the result of the $`\chi ^2`$ test of the DNA sequences chosen from different groups of species using the Sichel model. For each of the DNA sequences, we give the result for the 6-tuples and 7-tuples. We give the best values for $`\gamma ,\alpha `$ and $`\theta `$ in each case, which is determined by minimizing the $`\chi ^2`$ value,

$$\chi ^2=\underset{i}{}\frac{(N_in_i)^2}{n_i}$$
$`(9)`$
where $`N_i`$’s are the observed values and $`n_i`$’s are the theoretical values. It is interesting to note that in the case of the 7-tuples, most of the DNA sequences can be fit using an inverse Gaussian distribution (i.e. $`\gamma =\frac{1}{2}`$). Fig.1 is an illustration of the $`\chi ^2`$ test of some of the DNA sequences chosen from Table I. We choose one sequence from each group of DNA sequences that we studied. In most cases, $`\varphi (r)`$ can be fit reasonably well.

## 4 Sentence Length in DNA sequences

To study the sentence length of DNA sequences, one needs to define what a sentence is. In linguistics, it is easy to identify what a sentence is. In the case of DNA sequences, what exactly a sentence should be is unknown. One can, for example, identify the word clusters in  as DNA sentences. In our study here, we proceed with the following strategy. We divide a DNA sequence into segments in such a way as to maximize the compositional divergence between the resulting DNA domains until a stopping criterion is reached. We then identify each segment as a sentence in the DNA sequence. In our analysis, we use the segmentation method which employs the Jensen-Shannon divergence measure  to study the bacterial DNA sequence, Eco110K, as an example. We should remind our reader that one can use any other segmentation methods to study the sentence length in DNA sequences. The number of segments ($`N(r)`$) of length ($`r`$) is then recorded. We again divide $`N(r)`$ by the total number of segments to obtain the relative frequency distribution of segments for $`r`$ and plot it against $`r`$, which is shown in Fig.2 . In Fig.2, we present the results for $`d_r=0.55,0.60`$ and $`0.65`$ which correspond to significance level about 76%, 79% and 81% respectively. All of the chosen $`d_r`$s follow an inverse Gaussian distribution. Table II is the result of the $`\chi ^2`$ test of the Eco110K DNA sequences using the Sichel model.

## 5 Summary and Discussion

In the above, we have introduced a family of compound Poisson distribution functions to the statistical study of DNA sequences. We have used the compound Poisson distribution functions to fit both the $`n`$-tuple and segment distributions of the DNA sequences. In both cases, we have obtained reasonable fits, both the shape and the normalization. More interestingly, the relative frequency distribution of $`n`$-tuples and the compositional segmentation study follow the inverse Gaussian distribution among different types of species and the normalization of $`\varphi (r)`$ of both the word frequencies and compositional segmentation comes out naturally from the linguistic model without ambiguity.

In the early linguistics feature studies  of DNA sequences, people have plotted the relative occurrence of DNA words against rank and found power law behaviors. It was later shown that  the Zipf distribution indeed fits very poorly in many cases and the Yule (eq.(2)) distribution can give a much better fit. However, as we have mentioned earlier, the Yule distribution was suggested primarily for the reason of convergence and most of the fits are made when $`\theta `$ approaches one. This is also true in the case of  though the fits are better than that of . On the other hand, the distribution suggested by Sichel has a much rigorous base. It is based on the fact that only compound Poisson distribution functions have the properties that characterize the word frequency distribution function in linguistics and has its rigorous derivation. This model incorporates the characteristic features of linguistics and thus a fit using Sichel’s model should be of more theoretical interest. We have indeed shown that one can obtain reasonably good fits using this model.

As mentioned in the above section, one would want to study the compositional segmentation by using segmentation methods other than the one we used here. One of such methods is suggested in . In , new different stopping criteria for segmenting DNA sequences are introduced. The size of the segments are plotted against the rank and the result indicates that the Zipf plot is different for different segmentation methods. It would be interesting to see how the Sichel model can fit for different segmentation methods. This would then establish the validity of using the Sichel model in the linguistic study of DNA sequences. It would be inappropriate to conclude that our results imply that DNA sequences have any resemblance to a natural language. However, it does suggest that DNA sequences are not random sequences and they could possibly have subsequence structures .

## 6 Acknowledgment

The work of K.L. Ng is support by the ROC NSC grant NSC 91-2626-E275-001, and the Academia Sinica short term visiting program.


text:
# Maximally entangled mixed states: Creation and concentration

(July 31, 2003)

## Abstract

Using correlated photons from parametric downconversion, we extend the boundaries of experimentally accessible two-qubit Hilbert space. Specifically, we have created and characterized maximally entangled mixed states (MEMS) that lie above the Werner boundary in the linear entropy-tangle plane. In addition, we demonstrate that such states can be efficiently concentrated, simultaneously increasing both the purity and the degree of entanglement. We investigate a previously unsuspected sensitivity imbalance in common state measures, i.e., the tangle, linear entropy, and fidelity.

By exploiting quantum mechanics it is possible to implement provably secure cryptography cry (2002), teleportation Bennett et al. (1993), and super-dense coding Bennett and Wiesner (1992). These protocols and most others in quantum information processing require a known initial quantum state, and typically have optimal results for pure, maximally entangled initial states. However, decoherence and dissipation may cause the states to become mixed and/or less entangled. As the success of a protocol such as quantum teleportation often hinges on both the purity and the entanglement of the initial state Bose and Vedral (2000), it is important to study the interplay of these properties. Using a source of 2-qubit polarization states Kwiat et al. (1999), we investigate the creation of maximally entangled mixed states, and their concentration Bennett et al. (1996, 1996); Thew and Munro (2001); foo (a).

Entangled states have been demonstrated in a variety of systems Rarity and Tapster (1990); Kwiat et al. (1995); Brendel et al. (1999); Sackett et al. (2000); Bowen et al. (2003); Bao et al. (2003). In fact, there are several classes of entangled states; maximally entangled and nonmaximally entangled pure states Kwiat et al. (1995, 1999); White et al. (1999), nonmaximally entangled mixed states White et al. (2001), and the special case of Werner states Zhang et al. (2002) (incoherent combinations of a completely mixed state and a maximally entangled pure state) have all been experimentally realized using optical qubits. For some time it was believed that Werner states possess the most entanglement for a given level of mixedness. However, Munro et al. Munro et al. (2001) discovered a class of states that are more entangled than Werner states of the same purity. These maximally entangled mixed states (MEMS) possess the maximal  amount of entanglement (tangle or entanglement of formation) for a given degree of mixedness (linear entropy) foo (b); Wei et al. (2003).

By generating states close to the MEMS boundary, we have experimentally explored the region above the Werner state line on the linear entropy-tangle plane kwi (2003). We have also implemented a partial-polarizer filtration/concentration technique which simultaneously increases both purity and entanglement, at the cost of decreasing the ensemble size of initial photon pairs. Though the implementation requires initial state knowledge, we show that MEMS exist for which this “Procrustean” filtering technique Bennett et al. (1996); Kwiat et al. (2001); Thew and Munro (2001) is much more efficient than other recent entanglement concentration schemes pan ; Yamamoto et al. (2003), even after modification to work on MEMS.

The exact form of the MEMS density matrix depends on the measures used to quantify the entanglement and mixedness Wei et al. (2003); here we use the tangle ($`T(\rho )=[max\{0,\lambda _1\lambda _2\lambda _3\lambda _4\}]^2`$) woo , i.e., the concurrence squared; and the linear entropy ($`S_L(\rho )=\frac{4}{3}[1Tr(\rho ^2)]`$) Bose and Vedral (2000). Here $`\lambda _i`$ are the square roots of the eigenvalues of $`\rho (\sigma _2\sigma _2)\rho ^{}(\sigma _2\sigma _2)`$, in non-increasing order by magnitude, with $`\sigma _2=\left(\begin{array}{cc}0& i\\ i& 0\end{array}\right)`$. For this parameterization, where r is the concurrence, the MEMS density matrices exist in two subclasses Munro et al. (2001), $`\rho _{MEMSI}`$ and $`\rho _{MEMSII}`$,which have two and three eigenvalues, respectively:

$`\rho _{MEMSI}=\begin{array}{cccc}& & & \\ & (\mathrm{}& \frac{r}{2}& 0& 0& \frac{r}{2}& )\mathrm{}\\ & 0& 1r& 0& 0\\ & 0& 0& 0& 0\\ & \frac{r}{2}& 0& 0& \frac{r}{2}\end{array},{\displaystyle \frac{2}{3}}r1,`$ (1)
$`\rho _{MEMSII}=\begin{array}{cccc}& & & \\ & (\mathrm{}& \frac{1}{3}& 0& 0& \frac{r}{2}& )\mathrm{}\\ & 0& \frac{1}{3}& 0& 0\\ & 0& 0& 0& 0\\ & \frac{r}{2}& 0& 0& \frac{1}{3}\end{array},0r{\displaystyle \frac{2}{3}}.`$ (2)
Our creation of MEMS involves three steps: creating an initial state of arbitrary entanglement, applying local unitary transformations, and inducing decoherence. First, frequency degenerate 702-nm photons are created by pumping thin nonlinear $`\beta `$-Barium Borate (BBO) crystals with a 351-nm Ar-ion laser. Polarization entanglement is realized by pumping two such crystals oriented such that their optic axes are in perpendicular planes. With a pump polarized at $`\theta _1`$, a variable entanglement superposition state $`\mathrm{cos}\theta _1|HH+\mathrm{sin}\theta _1|VV`$ is created, where $`|HH`$ represents two horizontally polarized and $`|VV`$ two vertically polarized photons Kwiat et al. (1999); White et al. (1999). The pump polarization is controlled by a half-wave plate (HWP1 in Fig. 1) set to $`\theta _1/2`$.

To create the MEMS I, we start by setting the initial degree of entanglement to that of the target MEMS. Next a maximum likelihood tomography White et al. (1999); James et al. (2001) of this initial entangled state is taken and used to numerically determine the appropriate settings of HWP2 and HWP3 in Fig. 1. These waveplates set the diagonal elements of the density matrix to the target values for the desired MEMS. The initial tomography must be precise, because the waveplate settings are critically dependent on the initial state, as well as on the precise birefringent retardation of the waveplates themselves. After the waveplates, the state passes through decoherers, which lower specific off-diagonal elements in the density matrix, yielding the final state. In our scheme, each decoherer is a thick birefringent element ($``$1 cm quartz, with optic axis horizontal) chosen to have a polarization-dependent optical path length difference ($``$140$`\lambda `$ foo (c)) greater than the downconverted photons’ coherence length ($`L_c\lambda ^2/\mathrm{\Delta }\lambda 70\lambda `$, determined by a 10-nm FWHM interference filter placed before each detector), but much less than the coherence length of the pump ber .

The decoherer in each arm couples the polarization with the relative arrival times of the photons bar . While two horizontal ($`|HH`$) or two vertical ($`|VV`$) photons will be detected at the same time, the state $`|HV`$ will in principle be detected first in arm one and then in arm two, and vice versa for the state $`|VH`$ (assuming the decoherer slows vertically polarized photons relative to horizontally polarized ones). Tracing over timing information during state analysis then erases coherence between any distinguishable terms of the state (i.e., only the coherence term between $`|HH`$ and $`|VV`$ remains). A sample tomography of a MEMS I is shown in Fig. 2(a).

MEMS II are created by first producing the MEMS I at the MEMS I/II boundary, i.e., the state with $`r=\frac{2}{3}`$. In order to travel along the MEMS II curve, the optical path length difference in one arm must be varied from 140$`\lambda `$. This couples different relative timings to the $`|HH`$ and $`|VV`$ states, reducing the coherence between them. For instance, to make the MEMS II (B) in Fig. 2(a), 140$`\lambda `$ decoherence was used in one arm, 90$`\lambda `$ in the other. Fig. 2(a) indicates very good agreement between theory and experiment with fidelities of $``$99% (the fidelity Jozsa (1994) between the target state $`\rho _t`$ and the measured state $`\rho _m`$ is given by $`F(\rho _t,\rho _m)\left|\mathrm{Tr}\left(\sqrt{\sqrt{\rho _t}\rho _m\sqrt{\rho _t}}\right)\right|^2`$).

The states (A) and (B) are shown in the $`S_L`$-$`T`$ plane in Fig. 2(b), along with other MEMS we created. The states do not hit their $`S_L`$-$`T`$ targets (shown as stars in the figure) within errors, even though the states have very high fidelities ($`99\%`$) with their respective targets. To explore the discrepancy, for each target we numerically generated 5000 density matrices that had at least 0.99 fidelity with the target density matrix. The $`S_L`$ and $`T`$ of the numerically generated states are plotted in Fig. 2(b) as shaded regions surrounding the targets. The fact that these regions are rather large (and overlap with our measured MEMS) explains our results, but is surprising nonetheless. The unexpectedly large size of these patches arises from the great difference in sensitivity between the state measures of fidelity, tangle and entropy: for small perturbations ($`\delta r`$) of the MEMS parameter $`r`$, the fidelity is only quadratic in $`\delta r`$, while $`S_L`$ and $`T`$ are linear in $`\delta r`$ foo (d).

While our initial goal was to produce states of maximal tangle for a given linear entropy, maximally entangled pure states are generally more useful for quantum information protocols. However, in some cases, weakly entangled mixed states may be the only available resource. It is therefore important to study ways to simultaneously decrease the entropy and increase the entanglement of an ensemble of photon pairs (necessarily at the cost of reducing the size of the ensemble). Recently several such entanglement concentration experiments have been reported, relying on two-photon interference effects Yamamoto et al. (2003); pan . An interesting characteristic of MEMS is that they can be readily concentrated by a “Procrustean” method of local filtering Bennett et al. (1996); Kwiat et al. (2001). To concentrate we first modify the MEMS using HWP4 at $`45^{}`$ to exchange $`|H|V`$ in the first arm, changing the non-zero diagonal elements of the MEMS density matrix to $`|HVHV|`$, $`|VHVH|`$, and $`|VVVV|`$. By reducing the $`|VVVV|`$ element of the rotated MEMS, the outcome will be driven toward the maximally entangled pure state $`|\varphi ^+(|HV+|VH)/\sqrt{2}`$. We achieve this by inserting glass pieces (each piece consisting of four $``$1mm thick microscope slides sandwiched together with index matching fluid) oriented at Brewster’s angle, as indicated in the dotted box in Fig. 1. Equal numbers of pieces are used in both arms; they are oriented to nearly perfectly transmit horizontally polarized photons (transmission probability $`T_H=0.990\pm 0.006`$) while partially reflecting vertically polarized photons ($`T_V=0.740\pm 0.002`$).

We concentrated a variety of MEMS. Fig. 3 shows the results for the MEMS I and II of Fig. 2 and an additional MEMS I (C). As the number of glass pieces is increased, the states initially become more like a pure maximally entangled state. For example, in the case of (A), the fidelity of the initial MEMS with the state $`|\varphi ^+`$ is 0.672. When the state is concentrated with eight glass slips per arm, the fidelity with $`|\varphi ^+`$ is 0.902; 4.5% of the initial photon pairs survive this filtering process. The theoretical maximum survival probability is 6.4%. Note a characteristic difference between the two MEMS subclasses: MEMS II cannot be filtered into a Bell state.

We now compare the theoretical efficiency of our local filtering scheme with the interference-based concentration proposal of Bennett et al. Bennett et al. (1996), assuming identical initial MEMS and the same number of photon pairs. We shall compare the average final entanglement of formation ($`E_F`$)woo  (i.e., the $`E_F`$ of the concentrated state multiplied by the probability of success) per initial pair. The Bennett el al. Bennett et al. (1996) scheme was recently approximated by Pan et al. pan , with CNOT operations replaced by polarizing beam splitters; however, due to incomplete Bell state analysis, the probability of successful concentration is only 50% of the original proposal (the recent scheme of Yamamoto et al. Yamamoto et al. (2003) is unable to distill MEMS). The first step of both schemes is to perform a “twirling” operation twi  to transform a general entangled state into a Werner state. However, this initial operation usually decreases the entanglement, and the scheme with twirling is efficient only when $`r`$ is close to 1.

In fact, MEMS I could also be distilled without the twirling operation, using the scheme of Pan et al. But then the probability of success depends on the parameter $`r`$.

For most MEMS, the maximum distillation efficiency from filtration can exceed that achievable using the interference-based methods foo (e). For example, as shown in Table I, when the initial state is a MEMS with $`r=0.778`$, the two-piece filtering technique has a theoretical $`E_F`$ per pair nearly three times higher than the interference scheme without twirling, even though a successful concentration produces nearly the same $`E_F`$. In theory, using 2 to 5 slips achieves both higher entanglement of the successful state and better average entanglement yield. In practice, the filtration technique is much more efficient (see the final columns of Table I) foo (e).

We have demonstrated a tunable source of high fidelity MEMS. As a consequence of comparing the $`T`$-$`S_L`$ and fidelity values of generated MEMS with the theoretical targets, we identify and explain an unsuspected difference in sensitivity in these state measures. Furthermore, we have applied a Procrustean filtering technique to several MEMS, realizing a measured efficiency that is well above that achievable using other methods. However, in the limit of very strong filtering, small perturbations in the initial state will eventually dominate the process, yielding only product states (see Fig. 3). In practice, therefore, it may be optimal to combine both methods.

This work was supported by the DCI Postdoctoral Fellowship Program, ARDA and NSF grant $`\mathrm{\#}`$ EIA-0121568.