text:
# Modular transformations of the elliptic hypergeometric functions, Macdonald polynomials, and the shift operator

## 1. Introduction

In the WZW model of conformal field theory associated with a simple complex Lie algebra $`𝔤`$, one defines a holomorphic vector bundle, the bundle of conformal blocks, on the moduli space of smooth complex compact curves with marked points labeled by representations of $`𝔤`$. This vector bundle comes with a projectively flat connection, see \[TUY\]. For curves of genus zero and one, this connection is flat and can be described in explicit classical terms. Moreover, horizontal sections admit integral representations \[SV\], \[FV1\].

For genus zero curves, the connection is the Knizhnik–Zamolodchikov (KZ) connection and the equation for horizontal sections (KZ equation) is a generalization of the Gauss hypergeometric equation. The KZ equation reduces to the Gauss hypergeometric equation in a special case. The solutions to the KZ equations are given by integrals of certain differential forms over $`m`$-dimensional cycles where $`m`$ depends on $`𝔤`$ and on the representations labeling marked points. The classical integral representation of the hypergeometric function is recovered in the case of four points on the Riemann sphere when $`m=1`$. The horizontal sections (conformal blocks) are holomorphic functions on the universal covering of the configuration space of points on the complex plane and integral representation may be used to compute the action of covering transformations on conformal blocks. In this way representations of the pure braid group are obtained as monodromy representations.

We consider here the case of genus one curves with one marked point (elliptic curves) and the Lie algebra $`sl_2`$. The equation for horizontal sections is the Knizhnik–Zamolodchikov–Bernard (KZB) heat equation (1): it is essentially the heat equation associated to the Hamilton operator of a particle in a Weierstrass function potential. Again, solutions are given by generalizations of hypergeometric integrals, which are appropriately called elliptic hypergeometric integrals. Of particular interest is a finite dimensional subspace of the space of solutions, the space of conformal blocks of the WZW model. It may be characterized by symmetry and holomorphy conditions, see Sect. 2. This subspace is invariant under the (projective) action of the modular group $`\mathrm{SL}(2,)`$ of covering transformations of the upper half plane, viewed as the universal cover of the moduli space of elliptic curves.

We compute the projective action of the modular group on this space and relate the matrix elements of the $`S`$-transformation $`\tau 1/\tau `$ to values of $`A_1`$-Macdonald polynomials. This implies a special case of Kirillov’s theorem, stating that the representation of the modular group on certain conformal blocks on elliptic curves for $`sl_N`$ is equivalent to a representation where the matrix elements of $`S`$ are given in terms of $`A_{N1}`$-Macdonald polynomials.

One new feature of our computation is that it gives a formula for the matrix elements of the projective representation of the modular group (not just its conjugacy class) with respect to an explicit basis of elliptic hypergeometric integral solutions of the KZB equation (1). Moreover, the elliptic hypergeometric integrals give naturally a recursive procedure, developed in \[FS\] in a similar situation, to compute the matrix elements of $`S`$ by repeated application of the Stokes theorem. This recursive procedure shows the role of the shift operator \[AI\] in this context: it is identical to the recursive construction of Macdonald polynomials out of Schur functions by repeated application of the shift operator. We also discuss the relation of the matrix elements of $`S`$ with the traces of intertwining operators of the quantum group $`U_q(sl_2)`$ at root of unity.

Finally, let us point out that the KZB connection is unitary with respect to a hermitian form which can also be given by integrals of elliptic hypergeometric type. They are discussed in \[FG\].

The authors thank P. Etingof and A. Kirillov, Jr., for useful discussions and the referee for useful suggestions.

## 2. Conformal Blocks on the Torus

Let $`\kappa `$ and $`p`$ be non-negative integers satisfying $`\kappa 2p+2`$. Let $`q=e^{\frac{\pi i}{\kappa }}`$. Denote

$$[n]_q=[n]=\frac{q^nq^n}{qq^1},[n]!=[1][2]\mathrm{}[n],\left[\begin{array}{c}n\\ j\end{array}\right]=\frac{[n]!}{[j]![nj]!},$$

$$(n,q)_j=[n][n+1]\mathrm{}[n+j1].$$

Let $`\tau `$ be such that $`\mathrm{Im}\tau >0`$. The KZB-heat equation is the partial differential equation

(1)
$$2\pi i\kappa \frac{u}{\tau }(\lambda ,\tau )=\frac{^2u}{\lambda ^2}(\lambda ,\tau )+p(p+1)\rho ^{}(\lambda ,\tau )u(\lambda ,\tau ).$$

Here, the prime denotes the derivative with respect to the first argument, and $`\rho `$ is defined in terms of the first Jacobi theta function \[WW\],

$$\vartheta _1(t,\tau )=\underset{j}{}e^{\pi i(j+\frac{1}{2})^2\tau +2\pi i(j+\frac{1}{2})(t+\frac{1}{2})},\rho (t,\tau )=\frac{\vartheta _1^{}(t,\tau )}{\vartheta _1(t,\tau )}.$$

Holomorphic solutions of the KZB-heat equation with the properties,

1. $`u(\lambda +2,\tau )=u(\lambda ,\tau )`$,
2. $`u(\lambda +2\tau ,\tau )=e^{2\pi i\kappa (\lambda +\tau )}u(\lambda ,\tau )`$,
3. $`u(\lambda ,\tau )=(1)^{p+1}u(\lambda ,\tau )`$,
4. $`u(\lambda ,\tau )=𝒪((\lambda mn\tau )^{p+1})`$ as $`\lambda m+n\tau `$ for any $`m,n`$,

are called conformal blocks associated with the family of elliptic curves $`/+\tau `$ with the marked point $`z=0`$ and the irreducible $`sl_2`$ representation of dimension $`2p+1`$. It is known that the space of conformal blocks has dimension $`\kappa 2p1`$.

Remark. The relation of this definition of conformal blocks with the more standard one of \[TUY\] is the following. Recall the definition of \[TUY\] in this case: integrable irreducible representations $`V_{k,m}`$ of the affine Kac–Moody Lie algebra $`\widehat{sl}_2`$ are labeled by two non-negative integers: $`k`$, the level and $`m\{0,\mathrm{},k\}`$, the highest weight. To each such pair $`(k,m)`$ and a curve $`E_\tau =/+\tau `$ one associates a space of conformal blocks: it is the space of linear functions on $`V_{k,m}`$ invariant under a natural action the Lie algebra $`R(\tau )`$ of $`sl_2`$-valued functions on $`E_\tau `$ with poles at $`0`$. As one varies $`\tau `$ in the upper half plane, the spaces of conformal blocks form a vector bundle with a flat connection. The description of this bundle and connection in terms of theta functions was explained in \[FW\]: the family of Lie algebras $`R(\tau )`$ is extended to a two parameter family $`R(\lambda ,\tau )`$ which also acts on $`V_{k,m}`$. The $`R(\lambda ,\tau )`$-invariant linear forms on $`V_{k,m}`$ form a vector bundle of twisted conformal blocks with a flat connection. The space of horizontal sections is then isomorphic to the space of twisted conformal blocks at any $`(\lambda ,\tau )`$, in particular if $`\lambda =0`$, where (untwisted) conformal blocks are recovered. We have an injective restriction map from the space of horizontal sections of the bundle of twisted conformal blocks to the space of holomorphic functions of $`\lambda ,\tau `$ with values in the the dual of the zero weight space $`V_m[0]V_{k,m}`$ of the $`2m+1`$-dimensional irreducible representation $`V_m`$ of $`sl_2`$. If $`m`$ is odd, $`V_m[0]=0`$. If $`m=2p`$ is even, then $`V_m[0]=`$ and the image of the restriction map consists of functions of the form $`v(\lambda ,\tau )=\vartheta _1(\lambda ,\tau )u(\lambda ,\tau )`$, where $`u`$ is a solution of the KZB-heat equation obeying (i)-(iv) with $`\kappa =k+2`$. Conformal blocks may also be defined in other ways which also lead to the same description in terms of theta functions: in \[FG\] this is done for conformal blocks defined as states of the Chern–Simons–Witten theory and in \[EFK\] for the definition as spherical functions on the Kac–Moody group.

Introduce two transformations

(2)
$$Tu(\lambda ,\tau )=u(\lambda ,\tau +1),Su(\lambda ,\tau )=e^{\pi i\kappa \frac{\lambda ^2}{2\tau }}\tau ^{\frac{1}{2}\frac{p(p+1)}{\kappa }}u(\frac{\lambda }{\tau },\frac{1}{\tau }),$$

where we fix $`\mathrm{arg}\tau (0,\pi )`$.

###### Theorem 2.1.

\[EK\] If $`u(\lambda ,\tau )`$ is a solution of the KZB-heat equation, then $`Tu(\lambda ,\tau )`$ and $`Su(\lambda ,\tau )`$ are solutions too. Moreover, the transformations $`T`$ and $`S`$ preserve the properties (i)-(iv).

The proof of Theorem 2.1 is by direct verification. Restricted to the space of conformal blocks, the transformations $`T`$ and $`S`$ satisfy the relations

$$S^2=(1)^piq^{p(p+1)}I,(ST)^3=(1)^piq^{p(p+1)}I,$$

where $`I`$ is the identity transformation.

The modular group is the group generated by two elements $`T`$ and $`S`$ with relations

$$S^2=1,(ST)^3=1.$$

The modular group is naturally isomorphic to the quotient group $`\mathrm{SL}(2,)/\{\pm I\}`$. The formulas (2) define a projective representation of the modular group in the space of conformal blocks.

The isomorphism class of the projective representation of the modular group in the space of conformal blocks is described in \[K\] using the Kazhdan-Lusztig-Finkelberg isomorphism between the modular tensor categories arising from affine Lie algebras and the modular tensor categories arising from quantum groups at roots of unity. In this paper, we describe the action of the modular group on the space of conformal blocks using integral representations of solutions of the KZB-heat equation.

## 3. Integral Representations of Solutions of the KZB-Heat Equation

Solutions of the KZB-heat equation can be realized as elliptic hypergeometric integrals depending on parameters. Introduce special functions

$$\sigma _\lambda (t,\tau )=\frac{\vartheta _1(\lambda t,\tau )\vartheta _1^{}(0,\tau )}{\vartheta _1(\lambda ,\tau )\vartheta _1(t,\tau )},E(t,\tau )=\frac{\vartheta _1(t,\tau )}{\vartheta _1^{}(0,\tau )}.$$

They have the properties

(3)
$$E(t+1,\tau )=E(t,\tau ),E(t+\tau ,\tau )=e^{\pi i\tau 2\pi it}E(t,\tau ),$$

(4)
$$\sigma _\lambda (t+1,\tau )=\sigma _\lambda (t,\tau ),\sigma _\lambda (t+\tau ,\tau )=e^{2\pi i\lambda }\sigma _\lambda (t,\tau ).$$

The modular transformation properties of the functions $`\sigma _\lambda `$ and $`E`$ are calculated using the modular transformation properties of the function $`\vartheta _1`$,

(5)
$$\vartheta _1(t,\tau +1)=e^{\frac{\pi i}{4}}\vartheta _1(t,\tau ),\vartheta _1(\frac{t}{\tau },\frac{1}{\tau })=\frac{\sqrt{i\tau }}{i}e^{\pi i\frac{t^2}{\tau }}\vartheta _1(t,\tau ),$$

where $`\sqrt{i\tau }`$ is to be interpreted by the convention $`|\mathrm{arg}(i\tau )|<\pi /2`$. We have

$$\sigma _\lambda (t,\tau +1)=\sigma _\lambda (t,\tau ),\sigma _{\frac{\lambda }{\tau }}(\frac{t}{\tau },\frac{1}{\tau })=\tau e^{\frac{2\pi it\lambda }{\tau }}\sigma _\lambda (t,\tau ),$$

$$E(t,\tau +1)=E(t,\tau ),E(\frac{t}{\tau },\frac{1}{\tau })=\tau ^1e^{\pi i\frac{t^2}{\tau }}E(t,\tau ).$$

Let $`\mathrm{\Phi }_{p,\kappa }`$ be the multi-valued function

$$\mathrm{\Phi }_{p,\kappa }=\mathrm{\Phi }_\kappa (t_1,\mathrm{},t_p,\tau )=\underset{j=1}{\overset{p}{}}E(t_j,\tau )^{\frac{2p}{\kappa }}\underset{1i<jp}{}E(t_it_j,\tau )^{\frac{2}{\kappa }}.$$

For $`\kappa 2`$ and $`n`$, let $`\theta _{\kappa ,n}`$ be the theta function of level $`\kappa `$

$$\theta _{\kappa ,n}(t,\tau )=\underset{j}{}e^{2\pi i\kappa (j+\frac{n}{2\kappa })^2\tau +2\pi i\kappa (j+\frac{n}{2\kappa })t}.$$

We have

(6)
$$\theta _{\kappa ,n+2\kappa }(t,\tau )=\theta _{\kappa ,n}(t,\tau ),\theta _{\kappa ,n}(t,\tau )=\theta _{\kappa ,n}(t,\tau ),$$

(7)
$$\theta _{\kappa ,n}(t+\frac{2}{\kappa },\tau )=q^{2n}\theta _{\kappa ,n}(t,\tau ),\theta _{\kappa ,n}(t+\frac{2\tau }{\kappa },\tau )=e^{2\pi it\frac{2\pi i\tau }{\kappa }}\theta _{\kappa ,n+2}(t,\tau ).$$

The modular transformation properties of $`\theta _{\kappa ,n}`$ are given by

$$\theta _{\kappa ,n}(t,\tau +1)=q^{\frac{n^2}{2}}\theta _{\kappa ,n}(t,\tau ),$$

$$\theta _{\kappa ,n}(\frac{t}{\tau },\frac{1}{\tau })=\sqrt{\frac{i\tau }{2\kappa }}e^{\pi i\kappa \frac{t^2}{2\tau }}\underset{m=0}{\overset{2\kappa 1}{}}q^{mn}\theta _{\kappa ,m}(t,\tau ).$$

Let $`\mathrm{\Delta }_k^k^k`$ be the simplex

$$\mathrm{\Delta }_k=\{(t_1,t_2,\mathrm{},t_k)^k^k|\mathrm{\hspace{0.17em}0}t_kt_{k1}\mathrm{}t_11\}.$$

Let $`\stackrel{~}{\mathrm{\Delta }}_k`$ be the image of $`\mathrm{\Delta }_k`$ under the map $`(t_1,\mathrm{},t_k)(\tau t_1,\mathrm{},\tau t_k)`$. For $`0kp`$, define

$$J_{\kappa ,n}^{[k]}(\lambda ,\tau )=\mathrm{\Phi }_\kappa (t_1,\mathrm{},t_p,\tau )\theta _{\kappa ,n}(\lambda +\frac{2}{\kappa }\underset{j=1}{\overset{p}{}}t_j,\tau )\underset{j=1}{\overset{p}{}}\sigma _\lambda (t_j,\tau )dt_j,$$

where the integral is over

$$\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,(t_{k+1},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk}\}.$$

The integral is a meromorphic function of the exponents of $`\mathrm{\Phi }_{p,\kappa }`$. It is well-defined when all of the exponents in the function $`\mathrm{\Phi }_{p,\kappa }`$ have positive real parts. We are interested in the case when the exponents in the function $`\mathrm{\Phi }_{p,\kappa }`$ are negative real numbers. In this case, the integral is understood as an analytic continuation from the region where the exponents have positive real parts. The branch of $`\mathrm{\Phi }_{p,\kappa }`$ is determined by fixing the arguments of all factors of $`\mathrm{\Phi }_{p,\kappa }`$ for the case $`\tau =i`$ and deforming continuously for arbitrary values of $`\tau `$. For $`\tau =i`$, we fix $`\mathrm{arg}E(t_j,\tau )=0`$ for $`j=1,\mathrm{},k`$, $`\mathrm{arg}E(t_j,\tau )=\frac{\pi }{2}`$ for $`j=k+1,\mathrm{},p`$, and $`\mathrm{arg}E(t_it_j,\tau )(\pi ,\pi )`$ for $`1i<jp`$. Introduce

$$u_n^{[k]}(\lambda ,\tau )=u_{\kappa ,n}^{[k]}(\lambda ,\tau )=J_{\kappa ,n}^{[k]}(\lambda ,\tau )+(1)^{p+1}J_{\kappa ,n}^{[k]}(\lambda ,\tau ).$$

###### Lemma 3.1.

The integrals $`u_n^{[k]}`$ have the properties

$$u_n^{[k]}=u_{n+2\kappa }^{[k]},u_n^{[k]}=q^{2k(n+pk)}u_{n2(pk)}^{[k]}.$$

###### Proof.

The first equation is an immediate consequence of the $`2\kappa `$ periodicity of the functions $`\theta _{\kappa ,n}`$. To derive the second equation, we consider the integrals $`u_n^{[k]}`$ after the change of variables $`t_jt_j+1`$ for $`1jk`$, $`t_jt_j+\tau `$ for $`k+1jp`$. The result follows from the formulas (3), (4), (6), and (7). ∎

###### Theorem 3.2.

\[FV1\] For $`0kp`$ and any $`n`$, the integrals $`u_{\kappa ,n}^{[k]}(\lambda ,\tau )`$ are solutions of the KZB-heat equation having the properties (i)-(iv).

###### Theorem 3.3.

The set

$$\{u_n^{[p]}(\lambda ,\tau )|p+1n\kappa p1\}$$

is a basis for the space of conformal blocks.

###### Proof.

We prove that for $`n\{p+1,\mathrm{},\kappa p1\}`$, the integrals $`u_n^{[p]}`$ are linearly independent over $``$. In Theorem 3.7, we show that for all other values of $`n`$ in the interval $`0n\kappa `$, the integrals $`u_n^{[p]}`$ are identically zero. In the limit as $`\tau i\mathrm{}`$, the leading term of $`u_n^{[p]}`$ is of the form

$$\frac{A_pe^{\frac{\pi in^2}{2\kappa }\tau }}{(\mathrm{sin}(\pi \lambda ))^p}\left(\left(\underset{j=1}{\overset{p}{}}(q^{2(n+j)}1)\right)B_p(\frac{n+1}{\kappa },\frac{2p}{\kappa },\frac{1}{\kappa })\mathrm{sin}(\pi \lambda (n+p))+C_n(e^{\pi i\lambda },e^{\pi i\lambda })\right),$$

where $`C_n(e^{\pi i\lambda },e^{\pi i\lambda })`$ is a Laurent polynomial of degree $`<n+p`$ in $`e^{\pi i\lambda }`$. Here $`A_p`$ is a non-zero constant depending only on $`p`$, and $`B_p(\alpha ,\beta ,\gamma )`$ is the Selberg integral,

$$B_p(\alpha ,\beta ,\gamma )=\frac{1}{p!}\underset{j=0}{\overset{p1}{}}\frac{\mathrm{\Gamma }(1+\gamma +j\gamma )\mathrm{\Gamma }(\alpha +j\gamma )\mathrm{\Gamma }(\beta +j\gamma )}{\mathrm{\Gamma }(1+\gamma )\mathrm{\Gamma }(\alpha +\beta +(p+j1)\gamma )}.$$

It follows that the $`u_n^{[p]}`$ are linearly independent provided that the coefficients $`_{j=1}^p(q^{2(n+j)}1)`$ and $`B_p((n+1)/\kappa ,2p/\kappa ,1/\kappa )`$ are nonzero functions for each $`n`$ in the range $`p+1n\kappa p1`$. It is straightforward to check that the product $`_{j=1}^p(q^{2(n+j)}1)`$ is never zero for $`n`$ in this interval. The Selberg integral $`B_p((n+1)/\kappa ,2p/\kappa ,1/\kappa )`$ is also nonzero for $`n`$ in this interval since $`1+1/\kappa _0`$, and $`(np+j)/\kappa _0`$ for any $`j`$ satisfying $`0jp1`$. ∎

We use the modular transformation properties of the functions $`E`$, $`\sigma _\lambda `$ and $`\theta _{\kappa ,n}`$ to obtain the following two lemmas.

###### Lemma 3.4.

For any $`n`$, the action of the operator $`T`$ on $`u_n^{[p]}`$ is given by the formula

$$Tu_n^{[p]}(\lambda ,\tau )=q^{\frac{n^2}{2}}u_n^{[p]}(\lambda ,\tau ).\mathit{}$$

###### Lemma 3.5.

For any $`n`$, we have

$$Su_n^{[p]}(\lambda ,\tau )=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}\underset{m=0}{\overset{2\kappa 1}{}}q^{mn}u_m^{[0]}(\lambda ,\tau ).\mathit{}$$

In Lemma 3.5, we have written $`Su_n^{[p]}`$ as a linear combination of $`u_m^{[0]}`$. Our goal is to express $`Su_n^{[p]}`$ in terms of the basis $`\{u_m^{[p]}(\lambda ,\tau )|p+1m\kappa p1\}`$. This is accomplished using the Stokes theorem. Repeated applications of the Stokes theorem give us a recursive procedure for expressing the integrals $`u_m^{[0]}`$ as linear combinations of the integrals $`u_m^{[p]}`$.

###### Lemma 3.6.

For $`0kp1`$ and any $`n`$, we have

$$[pk](q^{n+pk}q^{np+k})u_n^{[k]}=q^{nk1}[k+1]\left(q^{2(k+1)}u_{n+2}^{[k+1]}u_n^{[k+1]}\right).$$

###### Proof.

Recall that the $`u_n^{[k]}`$ are defined as analytic continuations of integrals where all of the exponents in the function $`\mathrm{\Phi }_{p,\kappa }`$ have positive real parts. So the identity in the lemma relates objects which are understood as analytic continuations. To prove the identity, we begin by considering simpler objects. Namely, we consider the case when all of the exponents in $`\mathrm{\Phi }_{p,\kappa }`$ have positive real parts. In this case, we can apply the Stokes theorem which gives an identity for integrals with positive exponents. Then, we analytically continue all terms of the identity to get the statement of the lemma. More precisely, let $`A`$ be the parallelogram with vertices at $`0,\mathrm{\hspace{0.17em}1},\tau ,\mathrm{\hspace{0.17em}1}+\tau `$. Consider the $`(p+1)`$-dimensional cell

$$B_k=\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,t_{k+1}A,(t_{k+2},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk1}\}.$$

Applying the Stokes theorem to $`B_k`$ gives

(8)
$$\begin{array}{c}_{\delta B_k}\mathrm{\Phi }_\kappa (t_1,\mathrm{},t_p,\tau )\theta _{\kappa ,n}(\lambda +\frac{2}{\kappa }\underset{j=1}{\overset{p}{}}t_j,\tau )\underset{j=1}{\overset{p}{}}\sigma _\lambda (t_j,\tau )dt_j\hfill \\ \hfill +(1)^{p+1}_{\delta B_k}\mathrm{\Phi }_\kappa (t_1,\mathrm{},t_p,\tau )\theta _{\kappa ,n}(\lambda +\frac{2}{\kappa }\underset{j=1}{\overset{p}{}}t_j,\tau )\underset{j=1}{\overset{p}{}}\sigma _\lambda (t_j,\tau )dt_j=0.\end{array}$$

The boundary of $`B_k`$ consists of $`2p+2`$ components of dimension $`p`$. When all of the exponents in the function $`\mathrm{\Phi }_{p,\kappa }`$ have positive real parts, the restrictions of the integrand to all but four of the boundary components are zero. Those four components are

$`\gamma _k^1=\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,t_{k+1}[0,1],(t_{k+2},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk1}\},`$
$`\gamma _k^2=\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,t_{k+1}[1,1+\tau ],(t_{k+2},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk1}\},`$
$`\gamma _k^3=\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,t_{k+1}[\tau ,1+\tau ],(t_{k+2},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk1}\},`$
$`\gamma _k^4=\{(t_1,t_2,\mathrm{},t_p)^p|(t_1,\mathrm{},t_k)\mathrm{\Delta }_k,t_{k+1}[0,\tau ],(t_{k+2},\mathrm{},t_p)\stackrel{~}{\mathrm{\Delta }}_{pk1}\},`$
where $`[a,b]`$ denotes the straight line segment connecting $`a`$ and $`b`$. Thus, the Stokes theorem applied to $`B_k`$ gives us that the sum of the integrals over $`\gamma _1^k`$, $`\gamma _2^k`$, $`\gamma _3^k`$, and $`\gamma _4^k`$ is equal to zero.

We obtain the result of the lemma as follows. Let $`B_k`$ be defined as above. Take the analytic continuation of all terms in the identity (8). Let $`\gamma _k^{}`$ be any component of $`\delta B_k\backslash _{i=1}^4\gamma _k^i`$. In the case when the exponents in $`\mathrm{\Phi }_{p,\kappa }`$ had positive real parts, we had that the integral over $`\gamma _k^{}`$ was zero. Thus we must have that the analytic continuation of the integral over $`\gamma _k^{}`$ is also zero. So we have that the sum of the integrals (understood as analytic continuations) over $`\gamma _1^k`$, $`\gamma _2^k`$, $`\gamma _3^k`$, and $`\gamma _4^k`$ is equal to zero. The integrals over the boundary components $`\gamma _1^k`$ and $`\gamma _4^k`$ are $`c_1^ku_n^{[k+1]}`$ and $`c_4^ku_n^{[k]}`$, respectively, where $`c_1^k,c_4^k`$. To recognize the integral over $`\gamma _2^k`$ as $`c_2^ku_n^{[k]}`$, where $`c_2^k`$, we make the change of variables $`t_{k+1}t_{k+1}+1`$. To recognize the integral over $`\gamma _3^k`$ as $`c_3^ku_{n+2}^{[k+1]}`$, where $`c_3^k`$, we make the change of variables $`t_{k+1}t_{k+1}+\tau `$. We calculate the constants $`c_j^k`$ using the formulas (3), (4), and (7). ∎

###### Theorem 3.7.

For $`0kp`$ and $`n\{p,p+1,\mathrm{},p+2k\}\{\kappa p,\kappa p+1,\mathrm{},\kappa p+2k\}`$, we have

$$u_n^{[k]}=0.$$

###### Proof.

We prove the statement by induction on $`k`$. Setting $`k=0`$ in Lemma 3.1 gives us the identity

$$u_n^{[0]}=u_{n2p}^{[0]}.$$

Hence, using the $`2\kappa `$ periodicity of the $`u_n^{[k]}`$, for $`npmod\kappa `$, we have

$$u_n^{[0]}=0.$$

Now assume the theorem is true for some $`k`$ in the interval from $`0`$ to $`p1`$. We must show that $`u_n^{[k+1]}=0`$ for $`n\{p,p+1,\mathrm{},p+2k+2\}\{\kappa p,\kappa p+1,\mathrm{},\kappa p+2k+2\}`$. We use the reflection identity of Lemma 3.1,

$$u_n^{[k+1]}=q^{2(k+1)(n+pk1)}u_{n2(pk1)}^{[k+1]},$$

and the relation of Lemma 3.6,
(9)
$$[pk](q^{n+pk}q^{np+k})u_n^{[k]}=q^{nk1}[k+1]\left(q^{2(k+1)}u_{n+2}^{[k+1]}u_n^{[k+1]}\right).$$

By the induction hypothesis, the left hand side of equation (9) is zero for $`n\{p,p+1,\mathrm{},p+2k\}\{\kappa p,\kappa p+1,\mathrm{},\kappa p+2k\}`$. Thus, for $`n\{p,p+1,\mathrm{},p+2k\}\{\kappa p,\kappa p+1,\mathrm{},\kappa p+2k\}`$, we have the recursion relations

(10)
$$u_n^{[k+1]}=q^{2(k+1)}u_{n+2}^{[k+1]}.$$

We use the identities

$$u_{p+k+1}^{[k+1]}=u_{\kappa p+k+1}^{[k+1]}=0,u_{p+k}^{[k+1]}=u_{\kappa p+k}^{[k+1]}=0,$$

to obtain, recursively on the subscripts, the result. The first identity is an immediate consequence of the reflection identity, and the second identity follows from comparing the recursion relations (10) for $`n=p+k`$ and $`n=\kappa p+k`$, respectively, with the reflection identities

$$u_{p+k}^{[k+1]}=q^{2(k+1)}u_{p+k+2}^{[k+1]},u_{\kappa p+k}^{[k+1]}=q^{2(k+1)}u_{\kappa p+k+2}^{[p]}.$$

###### Proposition 3.8.

For $`0kp`$ and any $`n`$,

$$Su_n^{[p]}(\lambda ,\tau )=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}\left(\underset{m=p+2k+1}{\overset{\kappa p1}{}}f_{m,n}^{(k)}u_m^{[k]}(\lambda ,\tau )+\underset{m=\kappa p+2k+1}{\overset{2\kappa p1}{}}f_{m,n}^{(k)}u_m^{[k]}(\lambda ,\tau )\right),$$

where

$$f_{m,n}^{(k)}=\frac{q^{m(n+k)\frac{k(k+1)}{2}}}{(q^1q)^k}\left[\begin{array}{c}p\\ k\end{array}\right]^1\underset{j=0}{\overset{k}{}}\left[\begin{array}{c}k\\ j\end{array}\right]\frac{q^{2jn}}{(mp+k+1,q)_j(m+pk+1,q)_{kj}}.$$

###### Proof.

The proof is by induction on $`k`$. The result from Lemma 3.5 (where we have used the periodicity of the $`u_n^{[k]}`$ to shift the interval of summation) combined with the identity $`u_p^{[0]}=u_{\kappa p}^{[0]}=0`$ of Theorem 3.7 give us

$$e^{\frac{\pi i}{4}}\sqrt{2\kappa }Su_n^{[p]}(\lambda ,\tau )=S^{}u_n^{[p]}=\underset{m=p+1}{\overset{\kappa p1}{}}q^{mn}u_m^{[0]}(\lambda ,\tau )+\underset{m=\kappa p+1}{\overset{2\kappa p1}{}}q^{mn}u_m^{[0]}(\lambda ,\tau ).$$

But this is exactly the result for $`k=0`$ since

$$f_{m,n}^{(0)}=q^{mn}.$$

Assuming the result for some $`k`$ satisfying $`0kp1`$, we have

(11)
$$S^{}u_n^{[p]}(\lambda ,\tau )=\underset{m=p+2k+1}{\overset{\kappa p1}{}}f_{m,n}^{(k)}u_m^{[k]}(\lambda ,\tau )+\underset{m=\kappa p+2k+1}{\overset{2\kappa p1}{}}f_{m,n}^{(k)}u_m^{[k]}(\lambda ,\tau ).$$

Rewriting (11) using the identity of Lemma 3.6,

$$u_m^{[k]}=\frac{q^{mk1}}{(q^{m+pk}q^{mp+k})}\frac{[k+1]}{[pk]}\left(q^{2(k+1)}u_{m+2}^{[k+1]}u_m^{[k+1]}\right),$$

which makes sense for all $`m`$ in the interval of summation since those values of $`m`$ never give zero denominators, we obtain

(12)
$$\begin{array}{c}S^{}u_n^{[p]}(\lambda ,\tau )=\frac{q^{k1}}{(q^1q)}\frac{[k+1]}{[pk]}\times \hfill \\ \hfill (\underset{m=p+2k+1}{\overset{\kappa p1}{}}\frac{q^mf_{m,n}^{(k)}}{[m+pk]}u_m^{[k+1]}(\lambda ,\tau )\underset{m=p+2k+3}{\overset{\kappa p+1}{}}\frac{q^{m2k}f_{m2,n}^{(k)}}{[m+pk2]}u_m^{[k+1]}(\lambda ,\tau )\\ \hfill +\underset{m=\kappa p+2k+1}{\overset{2\kappa p1}{}}\frac{q^mf_{m,n}^{(k)}}{[m+pk]}u_m^{[k+1]}(\lambda ,\tau )\underset{m=\kappa p+2k+3}{\overset{2\kappa p+1}{}}\frac{q^{m2k}f_{m2,n}^{(k)}}{[m+pk2]}u_m^{[k+1]}(\lambda ,\tau )).\end{array}$$

By Theorem 3.7, the integrals $`u_m^{[k+1]}`$ are identically zero for $`m\{p+2k+1,p+2k+2,\kappa p,\kappa p+1,\kappa p+2k+1,\kappa p+2k+2,2\kappa p,2\kappa p+1\}`$. Thus, we may combine the first two terms on the right hand side of (12) into one sum over $`m`$ in the range $`p+2k+3m\kappa p1`$. Similarly, the last two terms give us a sum over $`m`$ in the range $`\kappa p+2k+3m2\kappa p1`$. In each of these sums, the coefficient of $`u_m^{[k+1]}`$ is given by the expression

(13)
$$\begin{array}{c}\frac{q^{m(n+k+1)\frac{(k+1)(k+2)}{2}}}{(q^1q)^{k+1}}\left[\begin{array}{c}p\\ k+1\end{array}\right]^1(\underset{j=0}{\overset{k}{}}\left[\begin{array}{c}k\\ j\end{array}\right]\frac{q^{2jn}}{(mp+k+1,q)_j(m+pk,q)_{kj+1}}\hfill \\ \hfill +\underset{j=1}{\overset{k+1}{}}\left[\begin{array}{c}k\\ j1\end{array}\right]\frac{q^{2jn}}{(mp+k+2,q)_j(m+pk1,q)_{kj+1}}).\end{array}$$

To complete the proof of the theorem, we must show that the expression (13) is equal to the expression

$$\frac{q^{m(n+k+1)\frac{(k+1)(k+2)}{2}}}{(q^1q)^{k+1}}\left[\begin{array}{c}p\\ k+1\end{array}\right]^1\underset{j=0}{\overset{k+1}{}}\left[\begin{array}{c}k+1\\ j\end{array}\right]\frac{q^{2jn}}{(mp+k+2,q)_j(m+pk,q)_{kj+1}}.$$

This is proved by direct calculation. ∎

###### Corollary 3.9.

For $`0kp1`$, $`m\{p+2k+1,\mathrm{},\kappa p1\}\{\kappa p+2k+1,\mathrm{},2\kappa p1\}`$, and any $`n`$, we have

$$f_{m,n}^{(k+1)}=\frac{q^{mk1}}{qq^1}\frac{[k+1]}{[pk]}\left(\frac{q^{2k}f_{m2,n}^{(k)}}{[m2+pk]}\frac{f_{m,n}^{(k)}}{[m+pk]}\right).$$

###### Lemma 3.10.

The functions $`f_{m,n}^{(k)}`$ have the property

$$f_{m,n}^{(k)}=q^{2k(m+pk)+2pn}f_{m2p+2k,n}^{(k)}.\mathit{}$$

We rewrite the sum in Proposition 3.8 using Lemmas 3.1 and 3.10.

###### Corollary 3.11.

For $`0kp`$ and any $`n`$,

$$Su_n^{[p]}(\lambda ,\tau )=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}\underset{m=p+2k+1}{\overset{\kappa p1}{}}\left(f_{m,n}^{(k)}q^{2pn}f_{m,n}^{(k)}\right)u_m^{[k]}(\lambda ,\tau ).$$

## 4. Macdonald Polynomials and the Shift Operator

The Macdonald polynomials of type $`A_1`$ are $`x`$-even polynomials in terms of $`q^{mx}`$, where $`m`$. They depend on two parameters $`k`$ and $`n`$, where $`k`$ and $`n`$ are non-negative integers. They are defined by the conditions:

1. $`P_n^{(k)}(x)=q^{nx}+q^{nx}+`$ lower order terms, except for $`P_0^{(k)}(x)=1`$,
2. $`P_m^{(k)},P_n^{(k)}=0`$ for $`mn`$, where

$$f,g=\frac{1}{2}\text{Const Term}\left(fg\underset{j=0}{\overset{k1}{}}(1q^{2(j+x)})(1q^{2(jx)})\right).$$

###### Example.

For $`n>0`$, we have

$$P_n^{(0)}(x)=q^{nx}+q^{nx}.$$

The shift operator $`D`$ is an operator acting on functions $`f(x)`$ by

$$Df(x)=\frac{f(x1)f(x+1)}{q^xq^x}.$$

The name is “shift operator” because its action on the basic ($`q`$-difference) hypergeometric functions results in a shift of the parameters \[AW, Ch\].

###### Theorem 4.1.

\[AI\] For $`n1`$ and $`k0`$, we have

$$DP_n^{(k)}(x)=(q^nq^n)P_{n1}^{(k+1)}(x).$$

###### Remark.

It follows from Theorem 4.1 that all of the Macdonald polynomials can be calculated from the polynomials $`P_n^{(0)}`$ using the shift operator provided that $`q^nq^n0`$.

###### Example.

For $`n>0`$, we have

$$P_{n1}^{(1)}(x)=\frac{q^{nx}q^{nx}}{q^xq^x}.$$

## 5. Identification of the $`f_{m,n}^{(k)}`$ with values of the Macdonald polynomials

###### Theorem 5.1.

For $`0kp`$, $`k+1n\kappa `$, and $`m\{p+2k+1,\mathrm{},\kappa p1\}`$, we have

$$\begin{array}{c}f_{m,n}^{(k)}q^{2pn}f_{m,n}^{(k)}=q^{pnkm\frac{k(k+1)}{2}}\left[\begin{array}{c}p\\ k\end{array}\right]^1(q^{mp+k}q^{m+pk})\times \hfill \\ \hfill \left(\underset{j=1}{\overset{k}{}}(q^{n+j}q^{nj})\right)P_{nk1}^{(k+1)}(m+pk).\end{array}$$

###### Proof.

We prove the statement by induction on $`k`$. The case $`k=0`$ follows directly from the formulas

$$f_{m,n}^{(0)}=q^{mn},P_{n1}^{(1)}(m+p)=\frac{q^{n(m+p)}q^{n(m+p)}}{q^{m+p}q^{mp}}.$$

We assume that the theorem is true for some $`k`$ in the range $`0kp1`$. To prove the theorem, we must verify the identity

(14)
$$\begin{array}{c}f_{m,n}^{(k+1)}q^{2pn}f_{m,n}^{(k+1)}=q^{pn(k+1)m\frac{(k+1)(k+2)}{2}}\left[\begin{array}{c}p\\ k+1\end{array}\right]^1(q^{mp+k+1}q^{m+pk1})\times \hfill \\ \hfill \left(\underset{j=1}{\overset{k+1}{}}(q^{n+j}q^{nj})\right)P_{nk2}^{(k+2)}(m+pk1)\end{array}$$

for $`k+2n\kappa `$ and $`m\{p+2k+3,\mathrm{},\kappa p1\}`$. By Corollary 3.9, the left hand side of the equation (14) equals

$$\frac{q^{mk1}}{(qq^1)}\frac{[k+1]}{[pk]}\left(q^{2k}\frac{f_{m2,n}^{(k)}q^{2pn}f_{m2,n}^{(k)}}{[m+pk2]}\frac{f_{m,n}^{(k)}q^{2pn}f_{m,n}^{(k)}}{[m+pk]}\right).$$

By Theorem 4.1, the right hand side of the equation (14) equals

$$\begin{array}{c}q^{pn(k+1)m\frac{(k+1)(k+2)}{2}}\left[\begin{array}{c}p\\ k+1\end{array}\right]^1\left(\underset{j=1}{\overset{k}{}}(q^{n+j}q^{nj})\right)\times \hfill \\ \hfill \left(P_{nk1}^{(k+1)}(m+pk)P_{nk1}^{(k+1)}(m+pk2)\right).\end{array}$$

Thus, the equation (14) is equivalent to the equation

$$\begin{array}{c}q^{2k}\frac{f_{m2,n}^{(k)}q^{2pn}f_{m2,n}^{(k)}}{q^{m+pk2}q^{mp+k+2}}+\frac{f_{m,n}^{(k)}q^{2pn}f_{m,n}^{(k)}}{q^{mp+k}q^{m+pk}}=q^{pnkm\frac{k(k+1)}{2}}\left[\begin{array}{c}p\\ k\end{array}\right]^1\times \hfill \\ \hfill \left(\underset{j=1}{\overset{k}{}}(q^{n+j}q^{nj})\right)\left(P_{nk1}^{(k+1)}(m+pk)P_{nk1}^{(k+1)}(m+pk2)\right),\end{array}$$

which follows from the induction hypothesis. ∎

###### Corollary 5.2.

For $`0kp`$ and $`k+1n\kappa `$,

$$\begin{array}{c}Su_n^{[p]}(\lambda ,\tau )=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}\underset{m=p+2k+1}{\overset{\kappa p1}{}}q^{pnkm\frac{k(k+1)}{2}}\left[\begin{array}{c}p\\ k\end{array}\right]^1(q^{mp+k}q^{m+pk})\times \hfill \\ \hfill \left(\underset{j=1}{\overset{k}{}}(q^{n+j}q^{nj})\right)P_{nk1}^{(k+1)}(m+pk)u_m^{[k]}(\lambda ,\tau ).\end{array}$$

The left hand side of the equation in Corollary 5.2 is equal to zero if $`n=k+1,\mathrm{},p`$ or $`n=\kappa p,\kappa p+1,\mathrm{},\kappa k1`$. This gives $`2(pk)`$ relations for the $`\kappa 2k1`$ possibly nonzero functions $`u_m^{[k]}`$, $`m=k+1,\mathrm{},pk1`$.

###### Lemma 5.3.

The $`2(pk)`$ relations between the functions $`u_m^{[k]}`$, $`m=k+1,\mathrm{},pk1`$, given by Corollary 5.2 are linearly independent and thus generate all linear relations between those functions.

###### Proof.

The coefficients of the above relations form $`2(pk)`$ columns of the $`S`$-matrix corresponding to $`\kappa ^{}=\kappa `$ and $`p^{}=k`$. That $`S`$-matrix is a non-degenerate matrix whose square is a root of unity. Thus any set of its columns is linearly independent. ∎

## 6. Representation of the Modular Group

Let $`T=(t_{m,n})`$ and $`S=(s_{m,n})`$ be the matrices of the transformations $`T`$ and $`S`$, respectively, with respect to the basis

$$\{u_{\kappa ,n}^{[p]}(\lambda ,\tau )|p+1n\kappa p1\}.$$

Here the matrices $`T`$ and $`S`$ are defined by

$$Tu_{\kappa ,n}^{[p]}=\underset{m=p+1}{\overset{\kappa p1}{}}t_{m,n}u_{\kappa ,m}^{[p]},$$

$$Su_{\kappa ,n}^{[p]}=\underset{m=p+1}{\overset{\kappa p1}{}}s_{m,n}u_{\kappa ,m}^{[p]}.$$

###### Theorem 6.1.

For $`p+1m,n\kappa p1`$, we have

$$t_{m,n}=q^{\frac{n^2}{2}}\delta _{mn},$$

$$s_{m,n}=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}q^{p(nm)\frac{p(p+1)}{2}}(q^mq^m)\left(\underset{j=1}{\overset{p}{}}(q^{n+j}q^{nj})\right)P_{np1}^{(p+1)}(m),$$

where $`\delta _{mn}=1`$ for $`m=n`$ and $`0`$ otherwise.

The theorem follows directly from Lemma 3.4 and Theorem 5.2.

###### Example.

Let $`\kappa =2p+2`$. In this case, the only element of the S-matrix is

$$s_{p+1,p+1}=\frac{(i)^{p+1}}{\sqrt{p+1}}e^{\pi i\frac{p+1}{4}}\underset{j=1}{\overset{p}{}}(q^j+q^j).$$

On the other hand, according to \[FSV\],

$$u_{2p+2,p+1}^{[p]}=a_p\vartheta _1(\lambda ,\tau )^{p+1},$$

where $`a_p`$ is a constant, and hence,

$$Su_{2p+2,p+1}^{[p]}=a_p(i)^{p+1}e^{\pi i\frac{p+1}{4}}\theta (\lambda ,\tau )^{p+1}.$$

This, in particular, implies

$$\underset{j=1}{\overset{p}{}}(q^j+q^j)=\sqrt{p+1}.$$

This formula and its relations to the classical Gauss sums can be found in \[Ch\].

The projective representation of the modular group in the space of conformal blocks described in \[K\] is given by the matrices $`\stackrel{~}{T}=(\stackrel{~}{t}_{m,n})`$ and $`\stackrel{~}{S}=(\stackrel{~}{s}_{m,n})`$, $`p+1m,n\kappa p1`$, where

$$\stackrel{~}{t}_{m,n}=e^{\frac{\pi i}{4}}q^{\frac{n^2}{2}}\delta _{mn},$$

$$\stackrel{~}{s}_{m,n}=\frac{i}{\sqrt{2\kappa }}q^{\frac{p(p+1)}{2}}\left(\underset{j=0}{\overset{p}{}}(q^{m+j}q^{mj})\right)P_{np1}^{(p+1)}(m).$$

###### Proposition 6.2.

Let $`D`$ be the diagonal matrix such that

$$d_j=q^{pj}\underset{l=1}{\overset{p}{}}(q^{j+l}q^{jl}),p+1j\kappa p1.$$

Then

$$T=e^{\frac{\pi i}{4}}D^1\stackrel{~}{T}D,S=e^{\frac{3\pi i}{4}}D^1\stackrel{~}{S}D.\mathit{}$$

Remark. For the standard definition of conformal blocks $`v(\lambda ,\tau )=\vartheta _1(\lambda ,\tau )^1u(\lambda ,\tau )`$ (see the remark in Sect. 2), the $`S`$ and $`T`$ transformations are defined as

$$\widehat{T}v(\lambda ,\tau )=v(\lambda ,\tau +1),\widehat{S}v(\lambda ,\tau )=e^{\pi i(\kappa 2)\frac{\lambda ^2}{2\tau }}\tau ^{\frac{p(p+1)}{\kappa }}v(\frac{\lambda }{\tau },\frac{1}{\tau }).$$

Using the transformation rules (5) of $`\vartheta _1`$ we see that the corresponding matrices $`\widehat{T}`$, $`\widehat{S}`$ are related to $`T`$, $`S`$ by

$$\widehat{T}=e^{\frac{\pi i}{4}}T,\widehat{S}=e^{\frac{3\pi i}{4}}S.$$

Thus $`\widehat{T}`$, $`\widehat{S}`$ are conjugated to $`\stackrel{~}{T}`$, $`\stackrel{~}{S}`$.

## 7. Trace Functions for $`U_q(sl_2)`$

Let $`q=e^{\frac{\pi i}{\kappa }}`$. The quantum group $`U_q(sl_2)`$ has generators $`E,F,q^{ch}`$, where $`c`$, with relations

$$q^{ch}q^{c^{}h}=q^{(c+c^{})h},q^{ch}Eq^{ch}=q^{2c}E,q^{ch}Fq^{ch}=q^{2c}F,EFFE=\frac{q^hq^h}{qq^1},$$

and comultiplication defined by
$$\mathrm{\Delta }(E)=Eq^h+1E,\mathrm{\Delta }(F)=F1+q^hF,\mathrm{\Delta }(q^{ch})=q^{ch}q^{ch}.$$

Identify weights for $`U_q(sl_2)`$ with complex numbers as follows. Say that a vector $`v`$ in a $`U_q(sl_2)`$-module has weight $`\nu `$ if $`q^hv=q^\nu v`$. Let $`M_\mu `$ be the Verma module over $`U_q(sl_2)`$ with highest weight $`\mu `$, and let $`v_\mu `$ be its highest weight vector. Let $`k`$ be a non-negative integer such that $`\kappa 2k+2`$. Let $`U`$ be the irreducible finite dimensional representation of $`U_q(sl_2)`$ of weight $`2k`$. Let $`U[0]`$ denote the zero weight subspace of $`U`$. Let $`uU[0]`$. For generic $`\mu `$, let $`\mathrm{\Phi }_\mu ^u:M_\mu M_\mu U`$ be the intertwining operator defined by

$$\mathrm{\Phi }_\mu ^uv_\mu =v_\mu u+\frac{Fv_\mu }{[\mu ]}Eu+\mathrm{}+\frac{F^jv_\mu }{[j]!(\mu ,q)_j}E^ju+\mathrm{}.$$

Introduce an $`\mathrm{End}(U[0])`$-valued function $`\psi ^{(k)}(q,\nu ,\mu )`$ defined by

$$\psi ^{(k)}(q,\nu ,\mu )u=\mathrm{Tr}|_{M_\mu }(\mathrm{\Phi }_\mu ^uq^{\nu h}).$$

Since $`U[0]`$ is one-dimensional, this function is a scalar function.

###### Theorem 7.1.

\[EV\] The function $`\psi ^{(k)}(q,\nu ,\mu )`$ is given by the formula

$$\psi ^{(k)}(q,\nu ,\mu )=q^{\nu \mu }\underset{j=0}{\overset{k}{}}(1)^jq^{\frac{j(j3)}{2}}(qq^1)^{j1}\frac{[k+j]!}{[j]![kj]!}\frac{q^{j\mu (j1)\nu }}{_{l=0}^{j1}[\mu l]_{l=0}^j[\nu l]}.$$

Introduce renormalized trace functions $`\mathrm{\Psi }^{(k)}(q,\nu ,\mu )`$ defined by

$$\mathrm{\Psi }^{(k)}(q,\nu ,\mu )=\underset{j=1}{\overset{k}{}}\left(\frac{q^{\mu +1j}q^{\mu 1+j}}{q^{\nu +j}q^{\nu j}}\right)\psi ^{(k)}(q,\nu ,\mu ).$$

The function $`\mathrm{\Psi }^{(k)}`$ is a holomorphic function of $`\mu `$.

## 8. Identification of the $`f_{m,n}^{(k)}`$ with values of the trace functions $`\mathrm{\Psi }^{(k)}`$

###### Theorem 8.1.

For $`0kp`$, $`m\{p+2k+1,\mathrm{},\kappa p1\}\{\kappa p+2k+1,\mathrm{},2\kappa p1\}`$, and any $`n`$,

$$f_{m,n}^{(k)}=q^{pnkmk(k+1)}(q^{m+pk}q^{mp+k})\left[\begin{array}{c}p\\ k\end{array}\right]^1\mathrm{\Psi }^{(k)}(q^1,mp+k,n1).$$

###### Proof.

The statement of the theorem is equivalent to the identity

(15)
$$\begin{array}{c}(qq^1)^k\underset{j=0}{\overset{k}{}}\left[\begin{array}{c}k\\ j\end{array}\right](mp+k+j+1,q)_{kj}(m+pj+1,q)_jq^{2jn}\hfill \\ \hfill =q^{\frac{k(k+1)}{2}+kn}\underset{j=0}{\overset{k}{}}q^{\frac{j(j1)}{2}j(m+pk+n)}(qq^1)^j\frac{[k+j]!}{[j]![kj]!}\times \\ \hfill \underset{l=j+1}{\overset{k}{}}(q^{m+pk+l}q^{mp+kl})(q^{n+l}q^{nl}).\end{array}$$

Let $`x=q^n`$. Using the $`q`$-binomial theorem, we rewrite the identity (15) as

(16)
$$\begin{array}{c}(qq^1)^k\underset{j=0}{\overset{k}{}}\left[\begin{array}{c}k\\ j\end{array}\right](mp+k+j+1,q)_{kj}(m+pj+1,q)_jx^{2jk}\hfill \\ \hfill =q^{k(k+1)}\underset{j=0}{\overset{k}{}}q^{j(m+pk1)}(qq^1)^j\frac{[k+j]!}{[j]![kj]!}\times \\ \hfill \underset{l=j+1}{\overset{k}{}}(q^{m+pk+l}q^{mp+kl})\underset{i=0}{\overset{kj}{}}(1)^{kji}q^{i(k+j+1)}\left[\begin{array}{c}kj\\ i\end{array}\right]x^{2ik}.\end{array}$$

For a fixed value of $`j`$ in the range $`0jk`$, the coefficient of $`x^{2jk}`$ on the left hand side of (16) is

$$(qq^1)^k\left[\begin{array}{c}k\\ j\end{array}\right](mp+k+j+1,q)_{kj}(m+pj+1,q)_j.$$

The coefficient of $`x^{2jk}`$ on the right hand side of (16) is

$$\begin{array}{c}q^{(k+1)(kj)}(qq^1)^k\left[\begin{array}{c}k\\ j\end{array}\right](m+pj+1,q)_j(mp+j,q)_{kj}\times \hfill \\ \hfill \underset{i=0}{\overset{kj}{}}q^{i(m+pkj1)}\frac{(k+1,q)_i(jk,q)_i}{[i]!(m+pk+1,q)_i}.\end{array}$$

We observe that the sum

$$\underset{i=0}{\overset{kj}{}}q^{i(m+pkj1)}\frac{(k+1,q)_i(jk,q)_i}{[i]!(m+pk+1,q)_i}$$

is the hypergeometric series

(17)
$$_2\varphi _1(\begin{array}{c}q^{2(k+1)},q^{2(jk)}\\ q^{2(m+pk+1)}\end{array};q^2,q^{2(m+pkj)}).$$

The series (17) is equal to

$$q^{(kj)(k+1)}\frac{(m+p2k,q)_{k+1}}{(m+pkj,q)_{k+1}}.$$

(For a proof of this formula, see \[GR\]). Hence the coefficients of $`x^{2jk}`$ on both sides of (16) are equal. This proves the theorem. ∎

Under the identification in Theorem 8.1, Corollary 3.9 takes the following form.

###### Corollary 8.2.

For $`0kp1`$, $`m\{p+2k+1,\mathrm{},\kappa p1\}\{\kappa p+2k+1,\mathrm{},2\kappa p1\}`$, and any $`n`$,

$$q^{k1}\mathrm{\Psi }^{(k+1)}(q^1,m,n+k)=\frac{\mathrm{\Psi }^{(k)}(q^1,m1,n+k)\mathrm{\Psi }^{(k)}(q^1,m+1,n+k)}{q^mq^m}.$$

###### Remark.

The right hand side of the equation in Corollary 8.2 is the shift operator applied to $`\mathrm{\Psi }^{(k)}(q^1,m,n+k)`$. Thus, for $`m`$ as above, $`k0`$, and any $`n`$, we have

$$D\mathrm{\Psi }^{(k)}(q^1,m,n)=q^{k1}\mathrm{\Psi }^{(k+1)}(q^1,m,n).$$

Together with Theorem 5.1, the identification in Theorem 8.1 gives us a formula for the Macdonald polynomials evaluated at roots of unity in terms of values of the renormalized trace functions.

###### Corollary 8.3.

For $`\kappa 2k+2`$, $`k+1n\kappa `$, and $`m\{p+2k+1,\mathrm{},\kappa p1\}`$, we have

$$\begin{array}{c}\mathrm{\Psi }^{(k)}(q^1,mp+k,n1)\mathrm{\Psi }^{(k)}(q^1,mp+k,n1)\hfill \\ \hfill =P_{nk1}^{(k+1)}(m+pk)\underset{j=1}{\overset{k}{}}(q^{n+2j}q^n).\end{array}$$

###### Remark.

For a generalization of Corollary 8.3, see \[ES\].

Using the identification in Theorem 8.1, we have the following expression for the $`S`$ transformation in terms of the renormalized trace functions.

###### Corollary 8.4.

For $`0kp`$ and any $`n`$, we have

$$\begin{array}{c}Su_n^{[p]}(\lambda ,\tau )=\frac{e^{\frac{\pi i}{4}}}{\sqrt{2\kappa }}\underset{m=p+2k+1}{\overset{\kappa p1}{}}q^{pnkmk(k+1)}\left[\begin{array}{c}p\\ k\end{array}\right]^1(q^{mp+k}q^{m+pk})\times \hfill \\ \hfill \left(\mathrm{\Psi }^{(k)}(q^1,mp+k,n1)\mathrm{\Psi }^{(k)}(q^1,mp+k,n1)\right)u_m^{[k]}(\lambda ,\tau ).\end{array}$$


format: text

text:
# Bounds on entanglement in qudit subsystems

## I Introduction

Quantum information is a rapidly developing field exploiting the peculiar entanglement properties of quantum states. Its applications can be broadly divided into two general types: quantum computation divincenzo95a ; vedral98b , and quantum communication schumacher96a . Quantum communication (including quantum cryptography and quantum teleportation) can be framed in terms of repeated use of pairs of entangled qubits – the entanglement properties of two qubits have been well characterized, and a number of analytical measures of entanglement are known bennett96b ; vedral97a ; wootters97a ; zyczkowski98a ; horodecki01a ; vidal01a . However, for multi-qubit systems, which are essential for quantum computation, few entanglement measures can be calculated even for pure states. Despite these difficulties, arrays of qubits have been the focus of recent attention wootters00a ; oconnor00a ; koashi00a ; gunlycke01a ; raussendorf01a ; buzek01a , though often only pairwise entanglement has been considered in such systems. The more general question of entanglement in multi-qudit systems ($`d`$–dimensional quantum particles) is also important since most real systems (e. g., atoms) have more than two states.

In this paper we tackle the question of entanglement in larger qudit systems by deriving a bound on the size of typical entangled mixed states that are subsystems of larger pure states. Previous numerical work by some of us kendon01a  suggested that qubit subsystems somewhat less than half the size of the pure state, typically have no usable entanglement. In other words, since pure states are typically highly entangled, the entanglement is distributed in multi-partite entanglement involving around half or more of the qubits. This work was limited by computational resources to small numbers of qubits (less than 14). Here we provide analytical bounds for any number of qubits, and also extend the analysis to any dimension of qudits.

We emphasize that we are interested in average properties of all possible pure states. It is easy to construct states with entanglement properties that lie outside our bounds. For example, the so-called $`W`$ states (symmetric superposition of one qubit in state $`|1`$ with the rest in state $`|0`$) have only pairwise entanglement koashi00a  for any value of $`N`$. However, such states are of small measure and do not contribute significantly to the average properties of pure states sampled from the whole of Hilbert space.

To further motivate our investigations, we note a connection to the the question of the origin of the speedup in quantum computing. Recently Jozsa and Linden in jozsa02a  argue that for an exponential speedup over classical computation, the state of a quantum computer using pure states will have multi-partite entanglement encompassing an arbitrarily large fraction of the total number of qubits in the computation. However, they also point out that the entanglement cannot be inferred to be the cause of the speedup, rather, it is one of a number of properties of the typical states in the Hilbert space of the quantum computer that are necessary for such a speed up. Our work confirms this property of typical states in Hilbert space, and also provides an analytical lower bound on the number of parties in the multi-partite entanglement for a given size of Hilbert space.

The paper is organized as follows. First, in Sec. II, we introduce clear definitions of the system we are considering and the entanglement measures we will use to analyze it. Next in Sec. III, we derive the analytic bounds, followed by comparison with numerical results in Sec. IV. We finish with conclusions in Sec. V.

## II Definitions and entanglement measures

In a finite dimensional Hilbert space $``$ there exists a natural, unitarily invariant, Fubini–Study measure $`\mu _{FS}`$, induced by the Haar measure on the unitary group. A system of $`N`$ qudits has a Hilbert space of size $`d^N`$. We will investigate entanglement in such systems by sampling randomly from the set of all pure $`N`$–qudit states according to the natural measure $`\mu _{FS}`$ and calculating their average, which is to say, typical properties. This will give us useful information about the majority of states in Hilbert space. Having chosen a random pure state of $`N`$ qudits, we can divide it into two subsystems by partial tracing. A subsystem of size $`m`$ is obtained by partial tracing over the other $`Nm`$ qudits. This partitioning could represent the system of interest plus the environment, for example, or two different parts of one system. From the mathematical point of view one obtains in this way a certain probability measure $`\mu _{N,m}`$ in the space of mixed quantum states acting in a $`d^m`$ dimensional Hilbert space induced by the natural measure $`\mu _{FS}`$ on the space of pure states in $`_{d^N}`$ zyczkowski00a . This is a useful way to sample randomly from mixed states, since unlike $`\mu _{FS}`$ for pure states, there is no unique natural measure for the space of mixed states.

### II.1 Entropy of subsystems

Consider now a pure state quantum system described by a density operator $`\rho =|\varphi \varphi |`$ acting in a composite Hilbert space $`_{MK}=_M_K`$ of dimension $`MK`$. The reduced density matrices defined by the partial trace, $`\rho _M:=\mathrm{tr}_K\rho `$ and $`\rho _K:=\mathrm{tr}_M\rho `$ characterize both subsystems. It is well-known that the von Neuman entropies of both subsystems are equal, $`S_M=S(\rho _M)=\mathrm{tr}\rho _M\mathrm{ln}\rho _M=S(\rho _K)=S_K`$. The value of $`S_M`$ shows how entangled the two subsystems are with each other. If $`S_M=0`$, there is no entanglement and the composite state may be factorized, $`\rho =\rho _M\rho _K`$, but this is not a typical case. The mean entropy of a subsystem averaged over the natural measure $`\mu _{FS}`$ is given by

$$S_M=\underset{j=K+1}{\overset{MK}{}}\frac{1}{j}\frac{M1}{2K}\mathrm{ln}M\frac{M}{2K},$$
(1)
where $`MK`$ and the approximation holds for $`0M<K`$. This result was first conjectured by Page page93a  and later proved in foong94a ; sen96a .

In our case the subsystems consist of $`m`$ and $`Nm`$ qudits, so substituting $`M=d^m`$ and $`K=d^{Nm}`$ into (1) we obtain the mean entropy $`S_{N,m}`$ of the subsystem analyzed, where we are now using the subscripts to remind us of the number of qudits in the pure state ($`N`$) as well as the number in the subsystem ($`m`$). Equation (1) tells us that on average, the smaller subsystem has nearly maximal entropy, showing that the two subsystems are highly entangled with each other, a typical pure state is highly entangled, see also kempe01a . The particular value of $`S_{N,m}`$ provides a good measure of entanglement between the two subsystems, but says little about entanglement between the qudits within a single subsystem. Asymptotically, for ($`N\mathrm{}`$), $`mN/2`$ will tend to be maximally mixed and therefore separable, but to obtain useful results for finite $`N`$, we need further information on the size of the region around the maximally mixed state that contains separable states.

### II.2 Purity and mixedness

Next we will characterize how mixed a typical $`m`$–qudit state $`\rho _m`$ might be. A convenient measure is the purity weaire77a  defined by

$$r(\rho _m):=\mathrm{tr}(\rho _m^2).$$
(2)
Pure states are defined to have $`r(\rho _m)=1`$ while mixed states have $`1/d^mr(\rho _m)<1`$. We will also refer to $`R:=1/\mathrm{tr}(\rho _m^2)1/R`$ as the inverse participation ratio (IPR) of the mixed state $`\rho _m`$. The IPR thus ranges from 1 (pure) to $`d^m`$ (maximally mixed), and larger IPR means the states are more mixed, while larger purity means the states are more nearly pure.

Consider random states drawn according to the natural measure $`\mu _{FS}`$ on the space of pure states in a $`MK`$ dimensional Hilbert space. As before, we apply a partial trace to obtain the reduced density matrices $`\rho _M`$ and $`\rho _K`$. In refs. lubkin78a ; zanardi00a ; zyczkowski00a  it was shown that the average purity of $`\rho _M`$ and $`\rho _K`$ is equal to

$$r=\frac{M+K}{MK+1}$$
(3)
This result does not depend on the particular way in which the $`MK`$–dimensional Hilbert space is decomposed, but only on the initial and the final dimensionality of the spaces. Thus it also holds in the problem we are analyzing here of pure states of $`N`$–qudits reduced to $`m`$–qudits by partial tracing. Substituting $`M=d^m`$ and $`K=d^{Nm}`$ the average purity of the system reads

$$r_{N,m}=\frac{d^m+d^{Nm}}{d^N+1}$$
(4)
In other words, the averaging has been performed with respect to the induced measure $`\mu _{N,m}`$.

Numerical investigation of the induced measures shows zyczkowski00a  that for $`mN/2`$ the probability distributions $`P(r)`$ are concentrated close to the mean value $`r`$.

This is illustrated in fig. 1, where $`P(r)`$ is plotted for $`d=m=2`$ and $`N=3`$ to 6 in the main plot, and for $`d=2`$, $`m=3`$, $`N=5`$ to 10 in the inset. The scale of the purity axis on the inset has been adjusted (the scale is in fact linear in $`R=1/r`$) to show the data near the minimum purity more clearly.

Fixing the number $`m`$ of the qudits in the final system and varying the initial number $`N`$ of qudits involved in the pure state we get a sequence of probability measures which sweep the space of the mixed states close to the manifold of a constant purity. Hence it is justified to use the mean value $`r`$ as a good estimate of the actual value $`r`$ for a typical subsystem.

### II.3 Peres criterion, positive partial transpose

We will now describe a simple test for entanglement in multiparticle mixed states due to Peres peres96a . Consider a multiparticle mixed state $`\rho `$ acting in a $`d^m`$ dimensional Hilbert space, which describes the system consisting of $`m`$ qudits. An $`m`$–particle system can be split into two parts containing $`j`$ and $`mj`$ particles respectively. The partial transpose is applied to the $`j`$ particle part of the system producing $`\rho ^{T_j}:=(\mathrm{𝟏}_LT_j)\rho `$. Here $`T_j`$ denotes the transpose operation in the $`d^j`$ dimensional subspace, while the dimension of the subspace that has not been transposed is $`L=d^{mj}`$. We say that the $`m`$–qudit state has the PPT property, if $`\rho ^{T_j}`$ is positive for all possible values of $`j`$ (it is sufficient to take $`1jm/2`$) and choices of $`j`$ particles, i. e., with respect to all of its possible splitting into two subsystems. Conversely, a state which fails this test is described as being NPT (negative partial transpose). NPT states have some useful entanglement that could be distilled with some probability into one or more maximally entangled states of two qubits. This test does not distinguish bound entangled states horodecki97a ; horodecky98a  from separable states, but since bound entanglement is relatively rare zyczkowski99a , and for most purposes it is the free entanglement that is useful, this still provides a useful characterization of entanglement.

For bipartite systems with Hilbert space dimension $`d^2`$, it has been shown zyczkowski98a  that all the states sufficiently close to the maximally mixed state, with $`Rd^21`$ have a positive partial transpose (PPT). This condition defines the maximal ball inscribed in the convex body of mixed states. Very recently it was shown that all mixed states of a bipartite system belonging to the maximal ball posses not only the PPT property but are also separable GurvitsBarnum02 . The former result may be generalized for a multipartite case: any state $`\rho _m`$ (within the $`d^m`$ dimensional Hilbert space) for which

$$RR_{\text{PPT}}=d^m1\text{so that}rr_{\text{PPT}}=\frac{1}{d^m1},$$
(5)
has the PPT property with respect to any possible transpositions of the subsystems. We give the proof of the generalization in Appendix A.

## III Bounds on entanglement in subsystems

We are now ready to provide an analytical relationship between the size of a subsystem and its typical entanglement properties.

### III.1 Bound on PPT region

Using the fact that the distributions of the purity $`P(r)`$ are narrow for the regions of interest ($`mN/2`$), and thus $`r_{N,m}`$ is a good estimate of the actual value of $`r`$ in a typical subsystem, we apply this to the critical value $`r_{\text{PPT}}`$ obtained in the previous section. If the mean value $`r`$ averaged over a certain induced measure is smaller that the critical value $`r_{\text{PPT}}`$, (or $`R>R_{\text{PPT}}`$), the majority of random states distributed with respect to this measure are localized inside the maximal ball and are PPT. We therefore combine eqs. (5) and (4) to calculate a relationship between $`N`$ and $`m`$ such that we expect almost all subsystems of $`m`$ qudits will have a positive partial transpose. We find $`r_{N,m}r_{\text{PPT}}`$ when

$$d^Nd^{3m}(1d^md^{2m}).$$
(6)
Taking the logarithm (base $`d`$) gives us an estimate of how many qudits the initial pure state should contain, such that after the reduction to $`m`$–qudits the obtained mixed state is PPT on average,

$$N_{\text{PPT}}3m+\mathrm{log}_d(1d^md^{2m}).$$
(7)
The $`\mathrm{log}_d`$ term is always negative, becoming rapidly smaller for either $`m>2`$ or $`d>2`$. Hence for systems initially consisting of

$$N3m$$
(8)
qudits we expect the subsystems of size $`m`$ to be PPT mixed states with a considerable probability. For the simplest case of $`m=d=2`$, the smallest integer number larger than the right hand side of (7) gives $`N_{\text{PPT}}=\mathrm{int}[6\mathrm{log}_2(16/11)]+1=6`$. For a fixed number $`N`$ this establishes a bound on $`m`$ below which subsystems of this size have on average no useful entanglement in an $`N`$–qudit pure state. This is the main result in this paper.

It is also possible to calculate the maximum value of the von Neuman entropy for states on the surface of the maximal ball, see Appendix B. This value $`S_c`$, given in eq. (19), can then be combined with eq. (1) for the average entropy of a subsystem, to obtain a similar relationship between $`N`$ and $`m`$. The result is (as it should be) the same as eq. (8), but with the restriction $`m0`$ from the approximate form of eq. (1). Our derivation as presented using eqs. (5) and (4) is applicable to all $`0<m<N`$.

### III.2 Estimation of the transition region

The above result is a bound on the average properties of typical states that identifies the range of parameter values ($`N3m`$) where there is a high probability that a subsystem of size $`m`$ is PPT. We would also like to characterize the range of $`N,m`$ for which with high probability the subsystems of size $`m`$ are entangled. This region is not simply the inverse of the PPT region because while the criterion we are using in eq. (5) is sufficient for ensuring the subsystem is PPT, it is not a necessary condition. There are many states which are PPT that have $`r>r_{\text{PPT}}`$ right up to separable pure states with $`r=1`$.

Since we do not, in general, know the size of the region of PPT states outside the maximal ball defined by eq. (5), our approach is to identify a region of the body of mixed states of a considerable size, which contains entangled states only. There is a one parameter family of mixed states (known as the generalized Werner states) containing $`m`$ qudits defined as a mixture of the maximally entangled pure state $`|\mathrm{\Psi }`$ and the maximally mixed state $`I_{d^m}`$,

$$\rho _\epsilon =\frac{(1\epsilon )}{d^m}I_{d^m}+\epsilon |\mathrm{\Psi }\mathrm{\Psi }|$$
(9)
where

$$|\mathrm{\Psi }=\frac{1}{\sqrt{d}}\underset{i=1}{\overset{d}{}}|i_1\mathrm{}|i_m$$
(10)
and $`\epsilon `$ is a real parameter between $`0`$ and $`1`$ specifying the proportions of the mixture. These states have been shown to be entangled for deuar00a ; pittenger00a ; rungta01a

$$\epsilon >\epsilon _{ent}=\frac{1}{d^{m1}+1}.$$
(11)
and strictly separable for $`\epsilon \epsilon _{ent}`$ (there are no bound entangled states in this family). This boundary at $`\epsilon _{ent}`$ defines a set of entangled states of positive measure 111 By “positive measure” we mean that we have divided the Hilbert space into two regions with measures of comparable size in $`\mu _{N,m}`$, i. e., the ratio of the measures of the two parts is finite (neither infinite nor zero).  as can be seen as follows. The states $`\rho _\epsilon `$ lie on a line that is on an axis of rotational symmetry in the set of mixed states. This line intersects the set of separable states at $`\epsilon =\epsilon _{ent}`$. The set of separable states is convex, so beyond the hyperplane normal to the $`\rho _\epsilon `$ line there exists a set of entangled states of a positive measure (see also lockhart00a ).

It is straight forward to show that the purity for $`\rho _\epsilon `$ at this boundary point ($`\epsilon =\epsilon _{ent}`$) is given by

$$r_{ent}=\frac{d^m+d^2+2d}{\left(d^m+d\right)^2}.$$
(12)
Thus there exists a greater-than-zero probability to encounter entangled states with $`r>r_{ent}`$. However, we don’t know that entangled states actually dominate over PPT states for this value of $`r`$. Since Werner states are among the most entangled states munro01a ; ishizaki00a ; verstraete01a  for a given purity $`r`$, we might actually guess that this estimate will turn out to be too tight. Nonetheless, it provides a useful independent check on our previously derived bound, so we present it anyway.

Equating $`r_{N,m}`$ from eq. (4) with $`r_{ent}`$ from (12) allows us to establish an estimate for the entangled side of the transition between entangled and PPT states. It is easily shown that $`r_{N,m}r_{ent}`$ when

$$N_{ent}3m2+\mathrm{log}_d[1+(2d+1)d^m+(d+2)d^{12m}].$$
(13)
For all $`d`$ and $`m`$, the $`\mathrm{log}_d`$ term is positive and tending to zero for increasing $`d`$ and $`m`$. Hence for all finite $`N`$ with

$$N3m2$$
(14)
we expect the probability of finding the subsystem of size $`m`$ entangled (not PPT), to be non-zero. Looking at the smallest case 222 For 2 qubits, $`\epsilon _{ent}`$ is at the boundary of the maximal ball (PPT implies separable in this case, see also GurvitsBarnum02 ), which is why the exact results for the bounds for two qubits are the same (r.h.s. of eqs. (8) and (13) are equal). But this isn’t so for $`d>2`$ or $`m>2`$, hence we get a different value for the bound from this method in general. The states in between are maximally entangled mixed states, see, munro01a ; ishizaki00a ; verstraete01a . , $`d=m=2`$, we have $`N_{ent}=\mathrm{int}[4+\mathrm{log}_2(11/4)]=5`$. Let us emphasize again, that this is an estimation only; for this (or lower) values of $`N`$ the probability of finding entangled subsystems of size $`m`$ is non-zero, but it does not rule out the existence of substantial numbers of PPT subsystems of size $`m`$, so the transition might occur effectively for even smaller values of $`N`$.

Now let us fix the initial size of the pure states of $`N`$ qudits while we decrease the size of the final system of $`m`$ qudits. For $`m=N`$ the probability of finding a separable pure state is equal to zero. As $`m`$ is reduced, the states obtained by partial tracing over $`Nm`$ qudits become increasingly mixed, and the probability of finding PPT states increases. Putting both results together we may characterize quantitatively a transition region

$$3m2N3m,$$
(15)
which does not depend on the qudit size $`d`$, in which we estimate that PPT subsystems come to dominate over entangled subsystems. (Note that the inequalities have reversed because we are identifying the region where the ratio of PPT to NPT (negative partial transpose) subsystems of size $`m`$ is of order unity, rather than the regions where one case dominates over the other.) These are surprisingly tight estimates of the boundary between entangled and PPT states in terms of the number of qudits in the state. However, it must be remembered that the number of qudits is a logarithmic measure of the size of the Hilbert space. The addition of one qudit enlarges the Hilbert space by a factor of $`d`$.

## IV Numerical comparisons

In kendon01a , for the qubit case $`d=2`$, it was shown numerically that entanglement in a mixed $`m`$–qubit subsystem of a typical $`N`$–qubit pure state falls off sharply towards zero with increasing $`N`$ for values of $`m5`$ and $`N13`$. These numerical results suggest the transition from NPT states dominating to PPT dominanting is complete by $`N2m+3`$, which falls outside the range of eq. (15) for $`m>4`$. This is at the edge of the results presented in kendon01a , so we ran further numerical studies to confirm this divergence between numerical and analytical results and also, since our analytical results apply for any dimension of the constituent quantum particles $`d`$, to test qutrits and confirm they follow the same pattern.

Using straightforward C programs optimized for efficiency to generate the large data sets required for useful statistics, we generated random pure states in the $`d^N`$ dimensional Hilbert space, traced over $`Nm`$ qudits, and analyzed whether the remaining mixed state, with a $`d^m`$–dimensional Hilbert space, had a positive or negative partial transpose (PPT or NPT).

In fig. 2 we represent the transition region in the $`N`$$`m`$ plane for qubits up to $`m=6`$, $`N=15`$ and qutrits up to $`m=3`$, $`N=8`$, combining data from kendon01a  with our new data for $`N=14`$ to 15 (qubits) covering the transition for $`m=6`$, and qutrits for $`N=4`$ to 8. Our new results confirm the trend. For $`m>4`$, the transition from NPT to PPT for a given subsystem size $`m`$ is completed for $`N<3m2`$. This is due to our estimates not taking into account the full size of the set of PPT states, being based only on the maximal ball inscribed in this set.

There is one more feature of this transition that requires comment. As noted in kendon01a , the transition is very sharp, the proportion of PPT subsystems of a given size $`m`$ becomes essentially zero to numerical accuracy with the addition of just a few qudits to the pure state. It is not obvious a priori that the transition should be sharp. One might reasonably expect it to be smoother, with a typical pure state of $`N`$ qudits containing finite amounts of $`m`$partite entanglement for all $`2mN`$. In order to obtain such a sharp transition, the proportion of NPT subsystems of given size $`m`$ must fall exponentially in the size of the Hilbert space $`d^N`$ of the pure state. This is hard to check numerically, but the data we have do support this, see fig. 3.

This sharp transition and exponential fall off allows us to assert that this bound on the multi-partite nature of entanglement in typical states of Hilbert space corresponds to the distinction made in jozsa02a  between sets of states that can be simulated efficiently classically, and sets of states that cannot. It also justifies our statement in the introduction that exceptions to our bound (8) do not contribute significantly to the average properties of typical pure states.

## V Discussion and conclusions

We have obtained analytically a lower bound on the size of subsystem of a typical pure state that can be expected to contain any entanglement within the subsystem. For a typical pure state of $`N`$ qudits, its subsystems of size $`m<N/3`$ can be expected to be PPT, i.e. to have no usable entanglement within them. We then checked numerically and confirmed that the transition from NPT to PPT subsystems actually occurs at significantly larger $`m`$ nearer to $`N/2`$, which is the asymptotic limit as $`N\mathrm{}`$. Our results emphasize the importance of multipartite entanglement in quantum information processing. The types of states necessary for exploring the main bulk of Hilbert space with quantum computers are highly entangled, but the entanglement will not be evident if only a small subset of the qudits are examined. For a quantum computer operating in a pure state, at least a third of the qubits would need to be processed to detect the entanglement present.

###### Acknowledgements.

It is a pleasure to thank Christof Zalka for useful discussions. We also thank the referee for helpful comments. This work was funded in part by the European project EQUIP(IST-1999-11053) and QUIPROCONE (IST-1999-29064). VK is funded by the UK Engineering and Physical Sciences Research Council grant number GR/N2507701. KŻ acknowledges the Polish KBN grant no 2P03B-072-19 and is grateful to the Blackett Laboratory for the hospitality during his stay in London.

## Appendix A PPT property for mixed states of multi–partite systems

In this appendix we prove the following

Proposition. Any mixed state $`\rho `$ of $`m`$ qudits which satisfies the condition

$$R(\rho )=\frac{1}{\mathrm{tr}\rho ^2}d^m1$$
(16)
has the PPT property, i. e., all its partially transposed matrices $`\rho _m^{T_j}`$ are positive.

We start the proof by invoking an algebraic

Lemma. Let $`A`$ be a $`n\times n`$ non-zero Hermitian matrix and consider the real number $`\alpha :=\mathrm{tr}A/(\mathrm{tr}A^2)^{1/2}`$. If $`\alpha \sqrt{n1}`$ then $`A0`$;

the proof of which is given by Mehta, mehta89a , inequality 9.21, p. 217. Let us apply it for the analyzed density matrix partially transposed in an arbitrary way, $`A=\rho ^{T_j}`$, which remains a Hermitian matrix of size $`n=d^m`$. Any operation of partial transpose $`T_j`$ does not change the traces, so $`\text{tr}\rho ^{T_j}=\text{tr}\rho =1`$ and $`\text{tr}(\rho ^{T_j})^2=\text{tr}\rho ^2=1/R`$. Therefore, the coefficient $`\alpha ^2=1/\mathrm{tr}\rho ^2`$ is just equal to the inverse participation ratio $`R`$. If a mixed state $`\rho `$ satisfies the condition (16), the assumption $`\alpha \sqrt{n1}`$ is fulfilled. Hence matrices $`\rho ^{T_j}`$ are positive for all possible operations $`T_j`$ of partial transpose, so the state $`\rho `$ is PPT. $`\mathrm{}`$.

It is illuminating to discuss a simple geometric interpretation of the condition (16), which defines a certain subset of the convex body of mixed states $``$ acting in $`n=d^m`$ dimensional Hilbert space. The center of the $`n^21`$ dimensional set $``$ is given by the maximally mixed state $`\rho _{}=𝕀/n`$. Introducing the Hilbert–Schmidt metric

$$D_{\mathrm{HS}}(\rho _1,\rho _2)=\left(\mathrm{tr}(\rho _1\rho _2)^2\right)^{1/2}$$
(17)
it is not difficult to compute the distance of any state $`\rho `$ with eigenvalues $`\{x_i\}`$ to the center of $``$,

$$D_{HS}^2(\rho ,\rho _{})=\underset{i=1}{\overset{n}{}}\left(x_i\frac{1}{n}\right)^2=\frac{1}{R}\frac{1}{n}.$$
(18)
Hence the condition $`R=`$const determines a set of points equidistant from $`\rho _{}`$.

The boundary of $``$ is defined by the condition det$`\rho =0`$, so any state belonging to it has at least one eigenvalue equal to zero. The state $`\rho _a`$ with the spectrum $`\{\frac{1}{n1},\frac{1}{n1},\mathrm{},\frac{1}{n1},0\}`$ is closest to $`\rho _{}`$ among the states belonging to the boundary of $``$. Its inverse participation ratio, $`R(\rho _a)=n1`$, coincides with the critical value from the constraint (16). Thus all states satisfying it form the maximal ball inscribed into the convex body of mixed states $``$ and centered at $`\rho _{}`$.

## Appendix B von Neumann entropy on the boundary of the maximal ball

In this appendix we outline the proof of the following

Proposition. If the von Neuman entropy of a state $`\rho `$ is larger than $`S_c`$, then $`\rho `$ belongs to the maximal ball and its inverse participation ratio $`R`$ is larger than $`n1`$ where $`n`$ is the dimension of the Hilbert space of $`\rho `$ and $`S_c`$ is given by

$$S_c=\mathrm{ln}n\frac{2}{n}\mathrm{ln}2+\frac{(n2)}{n}\mathrm{ln}\left[\frac{n1}{n2}\right].$$
(19)
In the asymptotic limit $`n\mathrm{}`$, $`S_C\mathrm{ln}n`$, i.e. maximal.

State $`\rho _a`$, with the spectrum

$$\lambda _a=\{\frac{1}{n1},\mathrm{}\frac{1}{n1},0\},$$
(20)
belongs to the boundary of the set of mixed states and to the maximal ball inscribed in it since

$$R=\frac{1}{tr(\rho ^2)}=n1,$$
(21)
see Appendix A. Its entropy $`S(\rho _a)=\mathrm{ln}(n1)`$ is the smallest among all states located at the surface of the hyperspehere $`R=n1`$. To show this it suffices to perturb the spectrum keeping $`R`$ constant and compute the entropy variation. Due to the symmetry of the problem, the state $`\rho _b`$ which belongs to this hypersphere and has the largest entropy, is located opposite to $`\rho _a`$ with respect to the maximally mixed state $`\rho _{}=𝕀/n`$ and we have

$$(\rho _b+\rho _a)/2=\rho _{}.$$
(22)
This gives the spectrum of $`\rho _b`$

$$\lambda _b=\{\frac{n2}{n(n1)},\mathrm{},\frac{n2}{n(n1)},\frac{2}{n}\},$$
(23)
which evidently belongs to the maximal ball $`R=n1`$.

Computing its entropy $`S(\rho _b)`$ one obtains the critical value $`S_c`$ given by (19). $`\mathrm{}`$.