format: text

text:
# Minimal and maximal elements in two-sided cells of 𝑆_𝑛 and Robinson-Schensted correspondence

## 1 Introduction

In this article, we consider the symmetric group $`S_n`$. For $`wS_n`$, the length of $`w`$, denoted $`\mathrm{}(w)`$, is the number of inversions of $`w`$.

The Robinson-Schensted correspondence  is the well-known bijection $`\pi :w(P(w),Q(w))`$ between $`S_n`$ and pairs of standard tableaux of the same shape (a partition of $`n`$). For each partition $`\lambda `$ of $`n`$, we denote by $`𝒯^\lambda `$ the set of all permutations which are mapped by $`\pi `$ on a pair of tableaux of shape $`\lambda `$. In the Kazhdan-Lusztig theory, which we use in this article, the sets $`𝒯^\lambda `$ are called two-sided cells (see ).

Our goal is to describe, for any partition $`\lambda `$ of $`n`$, the set $`𝒯_{min}^\lambda `$ of elements of minimal length in $`𝒯^\lambda `$ and the set $`𝒯_{max}^\lambda `$ of elements of maximal length in $`𝒯^\lambda `$.

For each composition $`c=(n_1,\mathrm{},n_k)`$ of $`n`$ (with $`n_i1`$), the Young subgroup $`S_c=S_{n_1}\times \mathrm{}\times S_{n_k}`$ contains a unique permutation $`\sigma _c`$ of maximal length. It is well-known that $`\sigma _c`$ is an involution, called the longest element of $`S_c`$. Denote $`\lambda (c)`$ the decreasing reordering of $`c`$. It is well-known that two Young subgroups $`S_{c_1}`$ and $`S_{c_2}`$ are conjugated in $`S_n`$ if and only if $`\lambda (c_1)=\lambda (c_2)`$.

Schützenberger  has shown that the map $`Tw_T=\pi ^1(T,T)`$ is a bijection between the standard tableaux of shape a partition of $`n`$ and the involutions of $`S_n`$ (see also  where another interesting description of this bijection is given).

A standard tableau $`T`$ is a reading tableau if it has the following property: for any $`1pn`$, either $`p`$ is in the first line of $`T`$, or if $`p`$ is in the $`i^{\text{th}}`$ line of $`T`$ ($`i>1`$) then $`p1`$ is in the $`(i1)^{\text{th}}`$ line of $`T`$.

As example, the column superstandard tableaux (which are tableaux numbered from the bottom to the top of each column, from left to right) are reading tableaux. These particular tableaux are the transposed of those defined by Garsia and Remmel in . Our main result is the following:

###### Theorem 1.1.

Let $`\lambda `$ be a partition of $`n`$ and $`𝒯^\lambda `$ be its associated two-sided cell, then

$`𝒯_{min}^\lambda `$ $`=`$ $`\{\sigma _c|\lambda (c)=\lambda ^t\}`$
$`=`$ $`\{w_T|T\text{ is a reading tableau of shape }\lambda \},`$
where $`\lambda ^t`$ denotes the conjugate partition of $`\lambda `$.

Example. Consider the partition $`\lambda =(3,2,1,1)`$ of $`7`$; $`\lambda ^t=(4,2,1)`$. Then the reading tableaux of shape $`\lambda `$ are

$$T_1=\text{   1   5   7      2   6      3      4   }\text{   4      3      2      1      6      5      7   };T_2=\text{   1   3   7      2   4      5      6   }\text{   2      1      6      5      4      3      7   }$$

$$T_3=\text{   1   2   6      3   7      4      5   }\text{   1      5      4      3      2      7      6   };T_4=\text{   1   5   6      2   7      3      4   }\text{   4      3      2      1      5      7      6   }$$

$$T_5=\text{   1   3   4      2   5      6      7   }\text{   2      1      3      7      6      5      4   };T_6=\text{   1   2   4      3   5      6      7   }\text{   1      3      2      7      6      5      4   }$$

The right skew tableau is taken in the plactic class of the corresponding tableau viewed in the plactic monoid  (see also ). The corresponding involutions are then

$$w_{T_1}=\mathrm{4\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}1\hspace{0.17em}6\hspace{0.17em}5\hspace{0.17em}7}=\sigma _{(4,2,1)};w_{T_2}=\mathrm{2\hspace{0.17em}1\hspace{0.17em}6\hspace{0.17em}5\hspace{0.17em}4\hspace{0.17em}3\hspace{0.17em}7}=\sigma _{(2,4,1)}$$

$$w_{T_3}=\mathrm{1\hspace{0.17em}5\hspace{0.17em}4\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}7\hspace{0.17em}6}=\sigma _{(1,4,2)};w_{T_4}=\mathrm{4\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}1\hspace{0.17em}5\hspace{0.17em}7\hspace{0.17em}6}=\sigma _{(4,1,2)}$$

$$w_{T_5}=\mathrm{2\hspace{0.17em}1\hspace{0.17em}3\hspace{0.17em}7\hspace{0.17em}6\hspace{0.17em}5\hspace{0.17em}4}=\sigma _{(2,1,4)};w_{T_6}=\mathrm{1\hspace{0.17em}3\hspace{0.17em}2\hspace{0.17em}7\hspace{0.17em}6\hspace{0.17em}5\hspace{0.17em}4}=\sigma _{(1,2,4)}$$

and $`𝒯_{min}^{(3,2,1,1)}=\{\sigma _{(4,2,1)},\sigma _{(2,4,1)},\sigma _{(1,4,2)},\sigma _{(4,1,2)},\sigma _{(2,1,4)},\sigma _{(1,2,4)}\}`$.

Let $`\lambda `$ be a partition of $`n`$ and $`T`$ be a standard tableau of shape $`\lambda `$. The Schützenberger evacuation of $`T`$, denoted by $`ev(T)`$, is a tableau of shape $`\lambda `$  (see also \[18, p.128-130\]). The evacuation illustrates the conjugation and the left (and right) multiplication by the longest element $`\sigma _{(n)}`$ in $`S_n`$. In particular $`Q(w\sigma _{(n)})=ev(Q(w)^t)`$, for any $`wS_n`$, and $`𝒯^\lambda \sigma _{(n)}=\sigma _{(n)}𝒯^\lambda =𝒯^{\lambda ^t}`$. Denote $`d_c=\sigma _{(n)}\sigma _c`$. As $`\mathrm{}(\sigma _{(n)}w)=\mathrm{}(\sigma _{(n)})\mathrm{}(w)`$, we obtain the following corollary:

###### Corollary 1.2.

Let $`\lambda `$ be a partition of $`n`$ and $`𝒯^\lambda `$ be its associated two-sided cell, then

$`𝒯_{max}^\lambda `$ $`=`$ $`\{d_c|\lambda (c)=\lambda \}`$
$`=`$ $`\{w|ev(Q(w)^t)=P(w\sigma _{(n)})\text{ is a reading tableau of shape }\lambda ^t\}.`$
In the theory of Coxeter groups, the element $`d_c`$ is well-known as the unique element of maximal length in the set of minimal right coset representatives of $`S_c`$ \[9, Chapter 2\].

As a by-product of our proof, we obtain, in Section 3, that if $`w`$ is an involution, the Kazhdan-Lusztig polynomial $`P_{e,w}=1`$ if and only if $`w`$ is the longest element of a Young subgroup, where $`e`$ denotes the identity of $`S_n`$. More precisely, we show that an involution $`w`$ avoids the pattern $`3412`$ and $`4231`$ if and only if $`w`$ is the longest element of a Young subgroup of $`S_n`$.

To our knowledge, our results are the first results relating the Robinson-Schensted transformation and the length function (number of inversions) of a permutation. There is no evident link between both. Our proof is non combinatorial and uses heavily the $`a`$function of Lusztig  (questions about the leading term of Kazhdan-Lusztig polynomials and the $`a`$function are heavily studied, see for instance ). Trying to find a combinatorial proof (which is a challenge) leads first to the following difficulty: for any permutations $`w,x`$ in a two sided-cell $`𝒯^\lambda `$, there are permutations $`w_1,\mathrm{},w_k𝒯^\lambda `$ such that $`w_1=w`$, $`w_k=x`$ and $`w_{i+1}`$ is obtained from $`w_i`$ by a Knuth or a dual-Knuth relation (see ). But a permutation $`w`$ may be ‘locally minimal’, that is whenever $`w`$ (or $`w^1`$) admits a Knuth or a dual-Knuth elementary relation, this relation increases the length. The involution $`\sigma =632541S_6`$ is locally minimal, but not of minimal length, in its two-sided cell.

It would be interesting to find a purely combinatorial proof of the main result. It is apparently an open problem to read the length of a permutation $`w`$ directly on the pair of tableaux $`\pi (w)`$ (however, see , where the author gives a way to read the signature on the pair of tableaux). Fortunately, the Lusztig $`a`$-function gives us a way to avoid this problem.

## 2 Consequences of the main result

We denote a partition of $`n`$ by $`\lambda =(\lambda _1,\mathrm{},\lambda _k)`$, with $`\lambda _1\mathrm{}\lambda _k1`$. Our reference for the general theory of the symmetric group is .

For any partition $`\lambda =(\lambda _1,\mathrm{},\lambda _k)`$ of $`n`$, we define, for $`i>0`$,

$$m_i(\lambda )=\left|\{j|\lambda _j=i\}\right|.$$

The number $`m_i(\lambda )`$ is called the multiplicity of $`i`$ in $`\lambda `$ (see ). Observe that $`m_i(\lambda )=0`$ for all $`i>n`$, since $`_i\lambda _i=n`$. It is well-known that the multinomial coefficient

$$\left(\begin{array}{c}m_1(\lambda )+m_2(\lambda )+\mathrm{}+m_n(\lambda )\\ m_1(\lambda ),m_2(\lambda ),\mathrm{},m_n(\lambda )\end{array}\right)$$

is the number of compositions associated to $`\lambda `$. Hence, we obtain the following corollary.

###### Corollary 2.1.

Let $`\lambda `$ be a partition of $`n`$, then

$$\left|𝒯_{min}^\lambda \right|=\left(\begin{array}{c}m_1(\lambda ^t)+m_2(\lambda ^t)+\mathrm{}+m_n(\lambda ^t)\\ m_1(\lambda ^t),m_2(\lambda ^t),\mathrm{},m_n(\lambda ^t)\end{array}\right),$$

which is the number of compositions $`c`$ of $`n`$ such that $`\lambda (c)=\lambda ^t`$.

The minimal elements in two-sided cells are linked to another important number in combinatorics

$$n(\lambda )=\underset{i=1}{\overset{k}{}}\left(\begin{array}{c}\lambda _i^t\\ 2\end{array}\right),$$

see \[16, p.2-3\].

###### Corollary 2.2.

Let $`\lambda `$ be a partition of $`n`$ and write $`\lambda ^t=(\lambda _1^t,\mathrm{},\lambda _k^t)`$. Then $`\mathrm{}(w)=n(\lambda )`$ for all $`w𝒯_{min}^\lambda `$.

###### Proof.

Let $`c`$ be a composition of $`n`$ such that $`\lambda (c)=\lambda ^t`$. Then $`\mathrm{}(\sigma _c)=\mathrm{}(\sigma _{\lambda ^t}`$. Let $`w_i`$ be the longest element of the Young subgroup $`S_{\lambda _i^t}`$, then $`\mathrm{}(w_i)=\left(\begin{array}{c}\lambda _i^t\\ 2\end{array}\right)`$. Therefore

$$\mathrm{}(\sigma _{\lambda ^t})=\underset{i=1}{\overset{k}{}}\left(\begin{array}{c}\lambda _i^t\\ 2\end{array}\right)$$

since $`\sigma _{\lambda ^t}=w_1\mathrm{}w_k`$ (seen as a word on the letters $`1,\mathrm{},n`$) and that the letters in $`w_{i+1}`$ are greater than the letters in $`w_i`$. The corollary follows from Theorem 1.1. ∎

As in the case of minimal elements, we have the following corollaries:

###### Corollary 2.3.

Let $`\lambda `$ be a partition of $`n`$, then

$$\left|𝒯_{max}^\lambda \right|=\left(\begin{array}{c}m_1(\lambda )+m_2(\lambda )+\mathrm{}+m_n(\lambda )\\ m_1(\lambda ),m_2(\lambda ),\mathrm{},m_n(\lambda )\end{array}\right),$$

which is the number of compositions $`c`$ of $`n`$ such that $`\lambda (c)=\lambda `$.

###### Corollary 2.4.

Let $`\lambda =(\lambda _1,\mathrm{},\lambda _k)`$ be a partition of $`n`$, then

$$\mathrm{}(w)=\left(\begin{array}{c}n\\ 2\end{array}\right)\underset{i=1}{\overset{k}{}}\left(\begin{array}{c}\lambda _i\\ 2\end{array}\right)$$

for all $`w𝒯_{max}^\lambda `$.

###### Proof.

As $`\mathrm{}(\sigma _{(n)})=\left(\begin{array}{c}n\\ 2\end{array}\right)`$ and $`\mathrm{}(\sigma _{(n)}w)=\mathrm{}(\sigma _{(n)})\mathrm{}(w)`$, for any $`wS_n`$, the corollary follows from same argument than in the proof of Corollary 2.2. ∎

## 3 Proof of Theorem 1.1

The following proposition implies that

$$\{\sigma _c|\lambda (c)=\lambda ^t\}=\{w_T|T\text{ is a reading tableau of shape }\lambda \}𝒯^\lambda .$$

###### Proposition 3.1.

Let $`\lambda `$ be a partition of $`n`$; then the following conditions are equivalent:

1. $`T`$ is a reading tableau of shape $`\lambda `$;
2. $`w_T=\sigma _c`$, where $`c`$ is a composition of $`n`$ such that $`\lambda (c)=\lambda ^t`$.

###### Proof.

Recall that the longest element of a Young subgroup is an involution, since it is unique.

Assume $`(i)`$. As $`T`$ is a reading tableau, if $`n`$ is in the row $`T_i`$, one has $`1pn1`$ such that $`p+1`$ is in the first row of $`T`$, $`p+i=n`$ and $`p+j`$ is at the end of the row $`T_j`$, for all $`1ji`$. One applies the $`i`$ first steps of the inverse of Robinson-Schensted correspondence, hence

$$w_T=w_T^{}n\mathrm{}p+1.$$

where $`T^{}`$ is the standard Young tableau obtained by deleting $`p+1,\mathrm{},n`$ in $`T`$. Thus $`w_T^{}`$ is a permutation on the set $`\{1,\mathrm{},p\}`$. Observe that $`T^{}`$ is also a reading tableau. The shape of $`T^{}`$ is denoted by $`\lambda ^{}`$. By induction on $`n`$, $`w_T^{}`$ is the longest element of the Young subgroup $`S_c^{}`$, where $`\lambda (c^{})=\lambda ^{}`$. Then $`w_T`$ is the longest element of the Young subgroup $`S_c^{}\times S_i`$. Let $`c=(c^{},i)`$; it is now easy to see that $`\lambda (c)=\lambda ^t`$.

Conversely, let $`c=(n_1,\mathrm{}n_k)`$ and use induction and similar arguments with direct Robinson-Schensted correspondence on the permutation

$$w_T=n_1\mathrm{}1w^{},$$

where $`n_1\mathrm{}1`$ is the longest element of the Young subgroup $`S_{n_1}`$ and $`w^{}`$ is the longest element of the Young subgroup $`S_{n_2}\times \mathrm{}\times S_{n_k}`$. ∎

Now, it remains to prove that $`\{\sigma _c|\lambda (c)=\lambda ^t\}=𝒯_{min}^\lambda `$, to end the proof of Theorem 1.1.

#### The Lusztig $`a`$-function:

We consider the symmetric group $`S_n`$ as a Coxeter system $`(W,S)`$ of type $`A_{n1}`$ with $`W=S_n`$ and generating set $`S`$ consisting of the $`n1`$ simple transpositions $`\tau _i=(i,i+1)`$, where $`i=1,\mathrm{},n1`$. Then $`\mathrm{}(w)`$ is also the length of $`w`$ as a reduced word in the elements of $`S`$. A classical bijection between subsets of $`S`$ and compositions of $`n`$ is obtained as follow: Let $`IS`$ and $`SI=\{\tau _{i_1},\mathrm{},\tau _{i_k}\}`$ with $`1i_1<i_2<\mathrm{}<i_kn1`$. Set $`n_1=i_1`$, $`n_2=i_2i_1+1`$, $`\mathrm{}`$, $`n_k=ni_k`$, then $`n_i`$ are non-negative integers. By this way, we have obtained a unique composition $`c_I=(n_1,\mathrm{},n_k)`$ of $`n`$ associated to $`I`$. Moreover,

$$W_I=S_{n_1}\times \mathrm{}\times S_{n_k}.$$

Therefore, as is well-known the Young subgroups of $`S_n`$ are precisely the parabolic subgroups of $`S_n`$ (see \[9, Proposition 2.3.8\]).

Our basic references for the work of Kazhdan and Lusztig are ,  (see also ). We denote by $``$ the Bruhat order on $`S_n`$.

Let $`𝒜=[q^{1/2},q^{1/2}]`$ where $`q^{1/2}`$ is an indeterminate. Let $``$ be the Hecke algebra over $`𝒜`$ corresponding to $`S_n`$. Let $`(T_w)_{wS_n}`$ be the standard basis of $``$ and $`(\stackrel{~}{T}_w)_{wS_n}`$ the basis defined as follows:

$$\stackrel{~}{T}_w=q^{\mathrm{}(w)/2}T_w.$$

In \[11, Theorem 1.1\], Kazhdan and Lusztig have shown that there is a basis $`(b_w)_{wS_n}`$ of $``$, called the Kazhdan-Lusztig basis, such that

$$b_w=\underset{yw}{}(1)^{\mathrm{}(w)\mathrm{}(y)}q^{(\mathrm{}(w)\mathrm{}(y))/2}P_{y,w}(q^1)\stackrel{~}{T}_y,$$

where $`P_{y,w}𝒜`$ are the Kazhdan-Lusztig polynomials. Moreover, they have defined three equivalence relations on $`S_n`$, with equivalence classes that are called left cells, right cells and two-sided cells. In our case, the following result of Vogan and Jantzen result on $`S_n`$  gives the link with the Robinson-Schensted correspondence (see also ): the set $`𝒯^\lambda `$ is a two-sided cell for all partitions $`\lambda `$ of $`n`$; and any two-sided cell of $`S_n`$ arises by this way.

Following Lusztig , let $`h_{x,y,w}`$ be the structure constants of the Kazhdan-Lusztig base $`(b_w)_{wW}`$, that is

$$b_xb_y=\underset{wW}{}h_{x,y,w}b_w.$$

Denote $`\delta (w)`$ the degree of the Kazhdan-Lusztig polynomial $`P_{e,w}`$ as a polynomial in $`q`$. Write $`u=q^{1/2}`$. Let $`a(w)`$ be the smallest integer such that for any $`x,yS_n`$, $`u^{a(w)}h_{x,y,w}𝒜^+`$, where $`𝒜^+=[u]`$ (this is well defined for any Weyl group). In , Lusztig has shown the following properties about the $`a`$function:

1. $`a(w)\mathrm{}(w)2\delta (w)`$ (\[15, Section 1.3\]);
2. The $`a`$function is constant on two-sided cells (\[14, Theorem 5.4\]).
3. For any $`IS`$, $`a(\sigma _{c_I})=\mathrm{}(\sigma _{c_I})`$ (\[15, Corollary 1.9 (d) and Theorem 1.10\]). In other words, for any composition $`c`$ of $`n`$, $`a(\sigma _c)=\mathrm{}(\sigma _c)`$.
4. Let $`𝒟=\{wW|a(w)=\mathrm{}(w)2\delta (w)\}`$, then each element in $`𝒟`$ is an involution, called a Duflo involution (\[15, Proposition 1.4\]). In symmetric groups, all involutions are Duflo involutions. Indeed, each left cell contains a unique Duflo involution ; left cells are precisely coplactic classes (the sets of permutations having the same right tableau under $`\pi `$, see for instance ), and each coplactic class contains a unique involution.

Let $`\lambda `$ be a partition of $`n`$ and $`𝒯^\lambda `$ be its associated two-sided cells. Properties (b) and (c) imply that $`a_\lambda :=a(\sigma _{\lambda ^t})=a(w)`$, for all $`w𝒯^\lambda `$. Therefore, by (a),

$$\mathrm{}(\sigma _c)=a_\lambda =a(w)\mathrm{}(w),$$

for any $`w𝒯^\lambda `$. Thus

$$\{\sigma _c|\lambda (c)=\lambda ^t\}𝒯_{min}^\lambda .$$

Now, let $`w𝒯_{min}^\lambda `$, then $`a(w)=a_\lambda =\mathrm{}(\sigma _{\lambda ^t})=\mathrm{}(w)`$, since $`\sigma _{\lambda ^t}𝒯_{min}^\lambda `$. Property (d) implies that $`w`$ is a Duflo involution and $`\delta (w)=0`$.

By Proposition 3.1, $`\sigma _c𝒯^\lambda `$ implies $`\lambda (c)=\lambda ^t`$ Therefore, Theorem 1.1 is a direct consequence of the following result, which gives a surprising criterion about the degree $`\delta (w)`$ of the Kazhdan-Lusztig polynomial $`P_{e,w}`$, for $`wS_n`$ an involution.

###### Proposition 3.2.

Let $`wS_n`$, then the following conditions are equivalent:

1. $`w`$ is an involution and $`\delta (w)=0`$;
2. $`w=\sigma _c`$, for some composition $`c`$ of $`n`$.

#### KL Polynomials and smoothness of Schubert Varieties:

We say that a permutation $`wS_n`$, seen as a word $`w=x_1\mathrm{}x_n`$, avoids the pattern $`4231`$ (resp. avoids the pattern $`3412`$) if there is no $`1i<j<k<ln`$ such that $`x_l<x_j<x_k<x_i`$ (resp. $`x_k<x_l<x_i<x_j`$). In other words, there is no subword of $`w`$ with the same relative order as the word $`4231`$ (resp. $`3412`$).

Here, we link these definitions with Kazhdan-Lusztig polynomials by the way of the following well-known criterion: Let $`wS_n`$, then

$$()P_{e,w}=1w\text{ avoids the patterns }4231\text{ and }3412.$$

Indeed, on one hand, Lakshmibai and Sandhya have shown that a Schubert variety $`X(w)`$, $`wS_n`$, is smooth if and only if $`w`$ avoids the pattern $`3412`$ and $`4231`$ ( or see \[2, Theorem 8.1.1\]).

On the other hand, Deodhar  has shown a useful characterization of the smoothness by the way of Kazhdan-Lusztig polynomials: Let $`wS_n`$ then $`P_{e,w}=1`$ if and only if $`X(w)`$ is smooth.

#### Proof of Proposition 3.2:

By the above discussion, Proposition 3.2 is a direct consequence of the following lemma.

###### Lemma 3.3.

Let $`wS_n`$ an involution, then the following statements are equivalent

1. $`w`$ avoids the patterns $`4231`$ and $`3412`$;
2. there is a composition $`c`$ of $`n`$ such that $`w=\sigma _c`$;

###### Proof.

$`(ii)(i)`$: write $`c=(c_1,\mathrm{},c_k)`$. If $`k=1`$ then $`\sigma _c=\sigma _{(n)}`$ avoids the patterns $`4231`$ and $`3412`$. If $`k>1`$ then $`\sigma _c`$ is the image of $`(\sigma _{(c_1)},\mathrm{},\sigma _{(c_k)})`$ under the canonical isomorphism between $`S_{c_1}\times \mathrm{}\times S_{c_k}`$ and $`S_c`$. Conclude by induction on $`n`$.

$`(i)(ii)`$: one sees $`w=x_1\mathrm{}x_n`$ as a word on the letters $`1,\mathrm{},n`$.

One proceeds by induction on $`n`$. Therefore, one may suppose that $`(i)(ii)`$ for all proper Young subgroups of $`S_n`$. If $`n4`$, it is readily seen. Suppose $`n>4`$.

If $`x_1=1`$, then $`wS_1\times S_{n1}`$, and the lemma follows by induction.

If $`n>x_1=p>1`$, then $`x_p=1`$ and $`1x_ip`$, for all $`1ip`$. Otherwise, there is $`1<i<p`$ such that $`x_i>p`$. In other words, there is $`1<i<p<x_i`$ such that $`x_p=1<x_{x_i}=i<x_1=p<x_i`$, that is, $`w`$ has the pattern $`3412`$ which is a contradiction.

Hence $`wS_p\times S_{np}`$ and the lemma follows by induction.

If $`x_1=n`$, then $`x_n=1`$ one just has to show that $`w=w_0`$. Otherwise, there is $`1<i<n1`$ such that $`x_i<x_{i+1}`$ (since if $`i=1`$, $`x_1=n<x_2`$ and if $`i+1=n`$, $`x_{n1}<x_n=1`$ which are contradictions). Thus there is $`1<i<i+1<n`$ such that $`x_n<x_i<x_{i+1}<x_1`$, that is, $`w`$ has the pattern $`4231`$ which is a contradiction. ∎

### Acknowledgements

I am indebted to C. Chauve and C. Reutenauer for useful discussions about Robinson-Schensted correspondence and plactic classes and to P. Polo for his useful remarks. I would thank P. Baumann, R. Bédard and F. Chapoton for pointing out some references.


text:
# Pseudospin Quantum Computation in Semiconductor Nanostructures

## Abstract

We theoretically show that spontaneously interlayer-coherent bilayer quantum Hall droplets should allow robust and fault-tolerant pseudospin quantum computation in semiconductor nanostructures with voltage-tuned external gates providing qubit control and a quantum Ising Hamiltonian providing qubit entanglement. Using a spin-boson model we estimate decoherence to be small $`(10^5)`$.

Among the stringent requirements for viable quantum computer architectures are robust (i.e. relatively decoherence-free) and scalable qubits (i.e. quantum two-level systems) allowing single- and two-qubit operations necessary for quantum computation Divincenzo . The scalability requirement makes semiconductor nanostructure based quantum computer architectures particularly attractive, and two spin-based semiconductor quantum computer architectures, one using electron spins in GaAs quantum dots Loss-Divincenzo  and the other using Si donor spin states Kane , have attracted considerable attention. The proposed advantage of solid state spin quantum computation over the corresponding charge or orbital state quantum computation is the long decoherence time for spin states ($`\mu s`$ or longer at low temperatures) compared with orbital states ($`ps`$ or less) allowing, at least in principle, robust quantum computation using spin qubits in semiconductor nanostructures. A very serious problem in solid state spin quantum computation is, however, the measurement of single spin states crucial for the quantum computation read-out. (There is no known solid state experimental technique for measuring a single spin, i.e. one Bohr magneton, and a great deal of experimental activity is currently being focused on measuring a single spin in semiconductor structures.) In this letter we theoretically establish the practical possibility of a novel pseudospin quantum computation in semiconductor nanostructures which synergetically combines the robustness of spins (i.e. long decoherence time) with the ease of qubit-specific measurement of charge states by using mesoscopic “coherent” charge states in quantum Hall droplets MacDonald ; evenodd .

Quantum Hall systems offer well studied mesoscopic quantum states with the potential for dynamic manipulation with long dephasing times. Surprisingly little work has gone into exploring the possibility of engineering quantum Hall states for the purpose of quantum computation. Mozyrsky *et al.* Privman  have explored the possibility of using nuclear spins as qubits with an interaction mediated by a two-dimensional electron gas in the quantum Hall regime. Recently, Yang. *et al.* MacDonald  have made a proposal for a quantum Hall two-level system using the charge degrees of freedom in two vertically coupled quantum dots in a large magnetic field, a system which is currently the subject of intense experimental study Tarucha . In these systems the layer degree of freedom acts as a pseudospin, controllable through external gates. The incompressibility of the finite size quantum Hall liquid preserves the integrity of the two-level system while the mapping between layer index and pseudospin relies on the presence of spontaneous interlayer phase coherence Eisenstein . Drawing upon the direct analogy between number fluctuations in the Cooper pair box experiment Nakamura  and fluctuations in the layer degree of freedom in bilayer quantum Hall droplets (BQHDs) an even-odd effect in the Coulomb blockade spectra of BQHDs has been proposed evenodd  as a simple measure of spontaneous interlayer phase coherence (and hence the robustness) of the two-level system discussed in Ref. evenodd .

The remainder of this article will be concerned with entangling two BQHDs which, when isolated, demonstrate the even-odd effect independently. Establishing controllable entanglement is crucial to performing large scale quantum computing. Our primary result is that the Coulomb interaction offers a natural entangling mechanism, opening the possibility of large scale quantum computing using BQHDS. We find that, for weak coupling, the Coulomb interaction between two laterally separated BQHDs can be mapped onto a quantum Ising model with a tunable, effective magnetic field. This two-qubit Hamiltonian allows for relatively simple implementation of a controlled-NOT operation Schon  which, when combined with single qubit operations, provides a universal set of quantum gates Barenco . We further address the extent to which phonons and voltage fluctuations in the leads dephase our system.

We begin by considering a set of two parabolically confined quantum dots vertically separated by a distance $`d`$ under a transverse magnetic field, $`B`$. The two dots will form a BQHD for appropriate magnetic fields and layer spacings. We further assume there to be a small, odd number of electrons distributed between the two droplets. In a large magnetic field the Coulomb interaction exhibits energy cusps at configurations corresponding to bulk, bilayer quantum Hall states. We focus our attention on the maximum density droplet (MDD) which is the mesoscopic realization of the bilayer quantum Hall state at total Landau level filling $`\nu _T=1`$.

The Hamiltonian for an isolated BQHD in the Fock-Darwin basis is:

$`H`$ $`=`$ $`H_0+\widehat{P}V_{\text{coul}}\widehat{P}`$ (1)
where $`H_0=\frac{1}{2}\left(\sqrt{\omega _c^2+4\omega _0^2}\omega _c\right)\widehat{L}_z`$, with $`\widehat{L}_z`$ being the total angular momentum in the $`z`$-direction. Also, $`\omega _c`$ is the cyclotron frequency and $`\omega _0`$ parameterizes the parabolic confining potential. $`\widehat{P}`$ is the lowest Landau level (LLL) projection operator and $`V_{\text{coul}}`$ represents the usual Coulomb interaction between electrons:

$`{\displaystyle \frac{V_{\text{coul}}}{e^2/\epsilon a}}={\displaystyle \underset{i<j}{}}{\displaystyle \frac{1}{r_{ij}}}+{\displaystyle \underset{k<l}{}}{\displaystyle \frac{1}{r_{kl}}}+{\displaystyle \underset{i,k}{}}{\displaystyle \frac{1}{\sqrt{r_{ik}^2+(\frac{d}{a})^2}}},`$ (2)
where $`\epsilon `$ is the GaAs dielectric constant, and $`r_{ij}`$ is the lateral separation between the $`i`$-th and $`j`$-th electron. The natural unit of length is the modified magnetic length $`a=l_B(1+4\omega _0^2/\omega _c^2)^{1/4}`$ which reduces to the planar magnetic length, $`l_B=\sqrt{\mathrm{}c/eB}`$, when the cyclotron energy is much larger than the confining potential energy. In the above we have used a pseudo-spin representation to describe the double layer system: $``$ and $``$ distinguish different layers. In general we define the pseudo-spin operator:

$`𝑺{\displaystyle \frac{1}{2}}{\displaystyle \underset{m}{}}c_a^{}(m)𝝈_{ab}c_b(m),`$ (3)
where $`c_a^{}(c_b)`$ creates (annihilates) an electron in the layer $`a(b)`$ with single particle angular momentum $`m`$. $`𝝈`$ are the usual Pauli matrices. $`\widehat{S}_z`$ measures half the electron number difference between layers, and $`\widehat{S}_x`$ is associated with interlayer tunneling. We take the real spin to be fully polarized either because of the large Zeeman coupling or because of electron-electron repulsion, i.e. Hund’s rule.

We diagonalize $`H`$ in the basis of LLL single-particle eigenstates. In particular, we focus our attention on the part of the Hilbert space containing the MDD state. It was shown in Ref. evenodd  that, in the absence of tunneling, the two degenerate states with $`S_z=\pm \frac{1}{2}`$ are separated from states with different $`S_z`$ by a large charging energy. These two states, labeled $``$ and $``$, form the qubit basis of our two-level pseudospin system.

Now consider a second BQHD along the $`x`$-axis at a distance $`R`$ away from the first BQHD, as shown in Fig. 1. To avoid lateral tunneling we keep the distance between BQHDs larger than the MDD diameter which is the diameter of the largest Fock-Darwin orbital, roughly $`2\sqrt{N}a`$, where $`N`$ is the total number of electrons in both BQHDs. To include the inter-BQHD Coulomb interaction we first note that for $`Ra`$ the low lying energy levels of the two BQHDs contain a set of four degenerate product states. For $`R8a`$ the Coulomb interaction between electrons in different BQHDs will favor the two pseudospin unpolarized states. We will verify, by direct calculation, that the inter-BQHD interaction energy can be made smaller than the intra-BQHD energy gap. We will consider a regime where the inter-BQHD interaction is too weak to produce intra-BQHD excitations, leaving the density unperturbed. Then, to a first approximation, we may take the basis states of the weakly interacting system of two BQHDs to be product states.

We now calculate the inter-BQHD interaction matrix between the four product states: $`\{,,,\}`$. First note that the Coulomb interaction does not flip pseudospin so that all off-diagonal matrix elements vanish. The four diagonal matrix elements do not vanish. The inter-BQHD coulomb interaction, within our restricted Hilbert space, therefore maps onto a Ising interaction:

$`H_I={\displaystyle \frac{J}{2}}\sigma _z^1\sigma _z^2,`$ (4)
where we define the exchange splitting to be:

$`J`$ $`=`$ $`{\displaystyle \underset{i,j}{}}V(R,d;𝒓_i,𝒓_j^{})`$ (5)
$``$ $`{\displaystyle \underset{i,j}{}}V(R,d;𝒓_i,𝒓_j^{}),`$
where:

$`V`$ $`(R,d;𝒓_i,𝒓_j^{})=`$ (6)
$`{\displaystyle \frac{e^2}{\epsilon ^{}a}}{\displaystyle \frac{1}{\sqrt{(x_ix_j^{}+R/a)^2+(y_iy_j^{})^2+(d/a)^2}}}.`$
$`𝒓`$ $`(𝒓^{})`$ indicates the radial vector in the $`x`$-$`y`$ plane in the left (right) BQHD and $`\epsilon ^{}`$ is the inter-BQHD dielectric constant. Note that with this definition the Coulomb interaction will favor an antiferromagnetic interaction with $`J>0`$. The states $``$ and $``$ are nontrivial, many-body eigenstates of $`H`$.

Fig. 2 is a log-log plot of $`J`$ as a function of the inter-BQHD separation $`R`$ for a total of 6,10, and 14 electrons distributed between two BQHDs with vertical spacing $`d=a`$. For $`R8a`$ we find that $`J`$ is appropriately smaller than the intra-BQHD edge excitation gap which is $`0.04\frac{e^2}{\epsilon a}`$ evenodd . At sufficiently large distances an odd number of electrons in a single BQHD in the MDD state can be thought of as a dipole. Fig. 2 shows that $`JR^3`$ for $`R25a`$, demonstrating that the inter-BQHD interaction is dipolar only for sufficiently large distances. In the regime of interest $`R8a`$, $`J`$ decreases much faster than $`R^3`$. We find that for $`R20a`$ the exchange splitting is already as low as $`J0.5\mu `$ eV at $`B=9T`$. This suggests that the interaction between a collection of BQHDs will be effectively nearest neighbor given that we have not considered effects such as finite layer thickness and, in general, screening of the inter-BQHD interaction, which significantly reduce the strength of the Coulomb interaction.

We now allow for interlayer tunneling within a single BQHD. The tunneling Hamiltonian can be written in terms of the pseudospin operator:

$`H_t=t\widehat{S}_x,`$ (7)
where $`t`$ is the single particle, interlayer tunneling gap. In the reduced Hilbert space, $``$ and $``$, of the $`i`$th BQHD we find MacDonald ; evenodd :

$`H_{\text{red}}^i=\mathrm{\Delta }_x^i\sigma _x^i+\mathrm{\Delta }_z^i\sigma _z^i.`$ (8)
In the limit of a small single-particle tunneling gap $`t`$, $`\mathrm{\Delta }_x=t\widehat{S}_x`$. Also, $`\mathrm{\Delta }_z`$ is the relative bias voltage between layers. $`\mathrm{\Delta }_x`$ is the renormalized tunneling gap which is greatly enhanced from the single-particle tunneling gap, $`t`$, by the Coulomb interaction. $`H_{\text{red}}`$ acts as the Hamiltonian of an effective magnetic field pointing in the $`x`$-$`z`$ plane. The effective field will reorient the direction of the on-site pseudospin.

The system discussed here has the advantage of being scalable. One may consider a large number of BQHDs coupled via nearest neighbor interactions. Two examples include a linear chain of closely spaced BQHDs or a planar, triangular lattice. The reduced Hamiltonian of a weakly coupled, many-BQHD system corresponds to a quantum Ising model:

$`H_{\text{total}}={\displaystyle \underset{i}{}}[\mathrm{\Delta }_x^i\sigma _x^i+\mathrm{\Delta }_z^i\sigma _z^i]+{\displaystyle \underset{i,j}{}}{\displaystyle \frac{J^{ij}}{2}}\sigma _z^i\sigma _z^j.`$ (9)
To perform a quantum logic operation the single qubit parameters in $`H_{\text{total}}`$ should be tunable. First, $`\mathrm{\Delta }_z`$ may be adjusted by applying a gating bias to each BQHD. $`\mathrm{\Delta }_x`$ can be tuned by changing $`t`$ through an in-plane magnetic field or a gating mechanism which alters the lateral position of the dots. The inter-qubit parameter, $`J`$, may be tuned by placing a third BQHD between the original two BQHDs. The inter-BQHD interaction can be turned on and off by placing an even or odd number of electrons in the intermediate BQHD or by depleting it completely. In fact it is not necessary to physically change $`J`$ because it may be possible to effectively tune the qubit coupling through a series of refocusing pulses. This technique has been used to implement quantum algorithms in NMR liquids governed by $`H_{\text{total}}`$, where the fixed coupling is between nuclear spins. It is also important to note that the architecture proposed here has the additional advantage of being charge based, simplifying read out. Single electron transistors, in principle, already have the capability Schon ; Schoelkopf  of measuring the charge imbalance between states with $`S_z=+1/2`$ and $`S_z=1/2`$.

Finally, we consider the important issue of qubit robustness by showing long pseudospin coherence times in BQHD systems. We consider two sources of dephasing in a single BQHD: phonons and voltage fluctuations in the leads. Phonons readily couple to single electron degrees of freedom in quantum dots. This may potentially destroy our proposed two level system through leakage to excited states. We note, however, that the rigidity of the incompressible quantum Hall droplet lifts the large degeneracy of the excited states, thereby suppressing phonon induced excitations. To show this quantitatively, consider the following general Hamiltonian for electron-phonon coupling:

$`H_{\text{e-p}}={\displaystyle \underset{𝒌}{}}M_𝒌\rho (𝒌)(a_𝒌^{}+a_𝒌^{}),`$ (10)
where $`M`$ is an arbitrary electron-phonon interaction matrix element and $`a_𝒌^{}`$ and $`a_𝒌^{}`$ annihilate and create phonons of wave vector $`𝒌`$ in the $`xy`$ plane. $`\rho (𝒌)`$ is the density operator, given by:

$`\rho (𝒌)={\displaystyle \underset{j=1}{\overset{N}{}}}e^{i𝒌𝒓_j}.`$ (11)
We use first order perturbation theory to estimate the change in the rate at which phonons couple to our two level system as we increase the system size. In which case the electron-phonon scattering rate is proportional to the transition matrix element between the initial and final electronic states. We calculate the transition matrix element between our proposed two-level ground state, $`g`$, and the lowest excitation, $`e`$:

$`T(ge)=|e|\rho (𝒌)|g|^2.`$ (12)
$`T`$ measures the probability that a phonon of wave vector $`𝒌`$ will induce an excitation from the ground state to the excited state. The ground and excited states are computed from $`H`$ using exact diagonalization at angular momenta corresponding to the MDD and its edge excitation, respectively evenodd . Fig. 3 plots the matrix element $`T`$ as a function of $`|𝒌|`$ for several different particle numbers. From the plot we see that phonon coupling to edge modes is suppressed as we increase the system size suggesting that the incompressible system studied here will be less sensitive to dephasing from phonons than analogous systems utilizing single particle, charge degrees of freedom.

Another primary mechanism coupling pseudospin to the environment is similar to the corresponding Cooper pair box problem Schon , through voltage fluctuations, $`\delta V`$, (e.g. in the gating potential) leading to the standard spin-boson model for decoherence of a single qubit:

$`H_{\text{SB}}=\mathrm{\Delta }_x\sigma _x+\mathrm{\Delta }_z\sigma _z+\gamma e\delta V\sigma _z,`$ (13)
where $`\gamma `$ is a dimensionless parameter related to the qubit and gate capacitances. Following standard spin-boson techniques Schon , the voltage fluctuations due to an external impedance with Ohmic dissipation can be modeled by a harmonic oscillator bath, leading to an equivalent mapping of our pseudospin decoherence problem to the corresponding Cooper pair box decoherence Nakamura ; Schon  problem. This then leads, after some straightforward algebra, to the following low temperature estimate for the decoherence factor $`\alpha `$, which is the ratio of the dephasing rate to the elementary logic operation rate:

$`\alpha =\gamma ^2{\displaystyle \frac{4R_v}{R_K}}=\left[{\displaystyle \frac{C_g}{2C_g+C_d}}\right]^2{\displaystyle \frac{4R_v}{R_K}},`$ (14)
where $`C_g`$ and $`C_d`$ are the gate and quantum dot capacitances, respectively; $`R_v(50\mathrm{\Omega })`$ is the typical impedance of the voltage circuits, and $`R_K=h/e^2`$. Using results from Ref. evenodd  to estimate the dot capacitance and reasonable values for the gate capacitance we get $`\alpha 10^5`$, establishing that robust fault-tolerant quantum computation should be possible in pseudospin quantum Hall systems. Although voltage fluctuations are likely to be the dominant decoherence mechanism on our proposed BQHD qubit, there are other possible dephasing channels which should be considered in the future. In particular, we suggest that the time scale of $`1/f`$ noise associated with charge fluctuations Nakamura2  is long enough to be dealt with using refocusing.

We acknowledge helpful conversations with J.K. Jain. This work was supported by ARDA.