text:
# Contents

## 1 Introduction

Several experimental and theoretical developments point to the possibility that the usual relation between energy and momentum valid within the special theory of relativity,

$$E^2=p^2+m^2$$
(1)
may be modified at Planck scales. For instance, the high-energy cosmic ray anomalies  may be solved if there are Planck scale departures from these relations . It has also been shown that one may establish an observer independent border between the classical and quantum pictures of space-time , by means of specially designed deformed dispersion relations.

The usual argument linking these deformations to quantum gravity is simple . The combination of gravity ($`G`$), the quantum ($`\mathrm{}`$) and relativity ($`c`$) gives rise to the Planck length,

$$L_P=\sqrt{\frac{\mathrm{}G}{c^3}}$$
(2)
or its inverse, the Planck energy

$$E_P=\sqrt{\frac{\mathrm{}c^5}{G}}.$$
(3)
These scales mark thresholds beyond which the old description of spacetime breaks down and qualitatively new phenomena are expected to appear. However, the new theory has to agree with special relativity for experiments probing the nature of space-time at energy scales much smaller than $`E_P`$. The question, then, arises: in whose reference frame are $`L_P`$ and $`E_P`$ the thresholds for new phenomena? It is clear that the Lorentz-Fitzgerald contraction cannot apply all the way down to the Planck scale, if we are to avoid introducing preferred frame in quantum gravity. A possible way out is the introduction of non-linear realizations of the Lorentz group, associated with deformed dispersion relations. This possibility, sometimes called, “doubly special relativity” has been explored in a number of recent papers-.

The most important reason to investigate this possibility is that it is an hypothesis that will be testable in experiments to be carried out over the next decade. What if a combination of low energy and astrophysical experiments found evidence of this kind of theory, such as energy dependent speed of light and/or modifications in relativistic energy-momentum conservation laws? What would be the implications for various candidate quantum theories of gravity? Given that the relevant experiments are planned, it is important if the different approaches to quantum gravity make predictions for their outcomes.

It has recently been shown that this possibility is realized in the case of quantum gravity coupled to point particles in $`2+1`$ dimensions. This shows that there are physically sensible interacting quantum theories of gravity that are described in terms of deformed dispersion relations. As far as $`3+1`$ dimensions is concerned, there are as yet no definitive results, but there are preliminary indications that such deformations may emerge naturally in loop quantum gravity .

In this paper we thus take up the question of whether phenomena associated with deformed dispersion relations may be realized in a consistent string theory . For simplicity, we study here only the bosonic string.

In Section 2 we present the formalism for introducing deformed dispersion relations into the action of the bosonic string. We find that in most cases the vibrational modes do not linearize, however there is a large class of examples in which they do. We study these in Section 3 and we are able then to first quantize the theory. Next, we examine the constraints imposed at the quantum level. In Section 4 we study the Virasoro algebra and spectrum of the deformed strings.

In the following section (Section 5) we look at three simple examples. The first employs a simple deformation of the energy-momentum relations, studied for particles in , in which there is a maximum invariant mass (or rest energy to be more precise). We show that this remains the case in string theory, so that the rest energies of the string excitations are bounded from above.

In the next two examples, the deformed energy-momentum relations are chosen so that the tachyonic mode of the free bosonic string is eliminated. We find this an intriguing result, as the possibility of a consistent, tachyon free bosonic string would obviously be of great importance for string theory.

## 2 The action and equations of motion

It is possible to write the bosonic string action in the form:

$$S=𝑑\sigma 𝑑\tau (\dot{x}^ap_aNM𝒟)$$
(4)
where, $`N`$ and $`M`$ are Lagrange multipliers, $``$ is the Hamiltonian constraint, and $`𝒟`$ is the constraint associated with spatial diffeomorphism invariance on the string. Together they generate diffeomorphisms on the worldsheet. However we now write the Hamiltonian constraint as

$$=\frac{f}{2T}\eta ^{ab}p_ap_b+\frac{Tg}{2}\eta _{ab}x^a^{}x^b^{}$$
(5)
where $`T`$ is the string tension and the dash represents a derivative with respect to $`\sigma `$. It can be checked that this action is reparameterization invariant. Here $`f`$ and $`g`$ are functions of the total energy

$$𝐏_0=𝑑\sigma p_0$$
(6)
and are expected to encode all deviations from linear special relativity. Furthermore

$$𝒟=\sqrt{fg}p^ax_a^{}$$
(7)
With these modifications we can still write the algebra of constraints as

$$L_n=𝑑\sigma e^{in\sigma }2(+𝒟)=𝑑\sigma e^{in\sigma }\left(\sqrt{\frac{f}{T}}p_a+\sqrt{Tg}x_a^{}\right)^2$$
(8)
Notice that the theory we have just proposed is not a mere redefinition of the string tension. Firstly $`f`$ and $`g`$ multiply $`T`$ differently in the various terms of the constraints. Secondly, even if one considers each of these terms on its own, it looks as if the tension is being renormalized by a factor dependent on the total string energy. The latter is the zero component of a vector. Thus such a “renormalized” tension would no longer be a scalar, invariant for all observers. One may expect a variety of new phenomena/pathologies to appear, an expectation we shall soon confirm.

The equations of motion can be found, e.g. from Hamilton’s equation, and we note that the space and time coordinates in target space are now to be treated differently. For the spacial coordinates we find:

$`\dot{x}^i`$ $`=`$ $`{\displaystyle \frac{}{p_i}}={\displaystyle \frac{f}{T}}p^i`$ (9)
$`\dot{p}_i`$ $`=`$ $`{\displaystyle \frac{}{x^i}}=Tg_\sigma ^2x_i`$ (10)
from which we may infer

$$\ddot{x}^ifg_\sigma ^2x^i=0$$
(11)
Hence we find our first result: the $`x^i`$ coordinates satisfy the wave equation, but the speed of light on the string depends upon the total energy $`𝐏_0`$ stored in the string:

$$c_s=\sqrt{fg}$$
(12)
We denote this speed as $`c_s`$ because it is really a speed of sound, i.e. a speed of propagation of vibrations along the string. It can be easily proved that $`𝐏_0`$ remains a constant of motion for general $`f`$ and $`g`$.

A similar set of equations may be found for the time target space coordinate

$`\dot{x}^0`$ $`=`$ $`{\displaystyle \frac{}{p_i}}={\displaystyle \frac{f}{T}}p^0+{\displaystyle \frac{f^{}}{2T}}p^2+{\displaystyle \frac{Tg^{}}{2}}x_{}^{}{}_{}{}^{2}`$ (13)
$`\dot{p}_0`$ $`=`$ $`{\displaystyle \frac{}{x^0}}=Tg_\sigma ^2x_0`$ (14)
As a result we find that the $`x^0`$ coordinate in general satisfies a rather complicated non-linear equation, coupled to the $`x^i`$ coordinates. The only exception occurs if $`f=g`$. Then the new terms are proportional to $``$ and so vanish as a result of the Hamiltonian constraint. Hence we learn that the deformations with $`f=g`$ play a special role in string theory, as they preserve the equation

$$\ddot{x}^afg_\sigma ^2x^a=0$$
(15)
for $`a=0,i`$.

It is very difficult to find solutions in the coupled case. The bosonic string has become non-linear and the quanta travelling along the string interact with each other. This unpleasant property already plagues standard $`p`$-branes with $`p>1`$.

In order to build further intuition about the meaning of the case $`f=g`$, in the Appendix we consider the analogue construction for point particles.

## 3 Solutions and canonical quantization

The particular case where the string remains linear is therefore the only one where we shall be able to perform a full study. In this case we may introduce light-cone variables:

$$\sigma ^\pm =\sqrt{fg}\tau \pm \sigma $$
(16)
It is important that in this definition the speed of sound multiples the coordinate $`\tau `$, rather than divide the coordinate $`\sigma `$. In terms of $`\sigma ^\pm `$ the wave equation (15) becomes

$$_+_{}x^a=0$$
(17)
Its most general solution is:

$$x^a=𝐱^a+\frac{𝐏_{CM}^a}{\pi T}\tau +v(\sigma ^+)+w(\sigma ^{})$$
(18)
where $`𝐱^a`$ and $`𝐏_a^{CM}`$ are center of mass integration constants. If we consider an open string with $`\sigma [0,\pi ]`$ we can therefore write:

$$x^a=𝐱^a+\frac{𝐏_{CM}^a}{\pi T}\tau +\frac{i}{\sqrt{\pi T}}\underset{n0}{}\frac{\alpha _n^a}{n}e^{in\sqrt{fg}\tau }\mathrm{cos}(n\sigma )$$
(19)
Note that we must have $`\alpha _n^a=\alpha _n^a`$, for $`x^a`$ to be real. The associated string momentum is:

$$p_a=\frac{T}{f}\dot{x}_a=\frac{𝐏_{CM}^a}{\pi f}+\sqrt{\frac{gT}{\pi f}}\underset{n0}{}\alpha _n^ae^{in\sqrt{fg}\tau }\mathrm{cos}(n\sigma )$$
(20)
We now proceed to canonically quantize this string, starting from the equal-time commutation relations:

$$[x^a(\sigma ,\tau ),p_b(\sigma ^{},\tau )]=i\delta (\sigma \sigma ^{})\delta _b^a$$
(21)
Using

$$\delta (\sigma \sigma ^{})=\frac{1}{\pi }\left(1+2\underset{n=1}{\overset{\mathrm{}}{}}\mathrm{cos}(n\sigma )\mathrm{cos}(n\sigma ^{})\right)$$
(22)
we thus arrive at:

$`[𝐱^a,𝐏_b^{CM}]`$ $`=`$ $`if\delta _b^a`$ (23)
$`[\alpha _n^a,\alpha _n^b]`$ $`=`$ $`\sqrt{{\displaystyle \frac{f}{g}}}n\eta ^{ab}`$ (24)
The first relation suggests an energy dependent Planck’s constant, a phenomenon we have found before in non-linear realizations of Lorentz invariance . Given that we have assumed $`f=g`$ the second relation leads to trivial definitions of creations and annihilation operators:

$`\alpha _n^a`$ $`=`$ $`\sqrt{n}a_n^a`$ (25)
$`\alpha _n^s`$ $`=`$ $`\sqrt{n}a_n^a`$ (26)
with

$$[a_n^a,a_m^b]=\delta _{mn}\eta ^{ab}$$
(27)
Should $`fg`$ the whole quantization procedure should be different. One may argue that the extra non-linear terms may be seen as an interaction, and the system described by means of an $`S`$ matrix. If this is true one should bear in mind that $`f/g`$ will still appear in the definition of creation and annihilation operators and thus in the asymptotic states.

## 4 The quantum constraints and the spectrum

We now examine the constraints and their enforcement at quantum level, starting with the Hamiltonian constraint. Using Eqns. (19) and (20), the Hamiltonian (5) may be written in terms of the amplitudes $`\alpha _n^a`$. The quantum Hamiltonian, however, should contain only normal ordered $`\alpha _n^a`$, and so an ordering constant $`a`$ has to be added at quantum level. The result is:

$$H=𝑑\sigma =\frac{𝐏_{CM}^2}{2\pi fT}+\frac{g}{2}\left(\underset{n0}{}|\alpha _n^a|^2a\right)$$
(28)
By setting $`H=0`$ we this arrive at the string center of mass dispersion relations:

$$\frac{\eta _{ab}𝐏_{CM}^a𝐏_{CM}^b}{fg}=M^2=2\pi T\left(a\underset{n0}{}|\alpha _n^a|^2\right)$$
(29)
Given (24), it is convenient to define,

$$\beta _n^a=\left(\frac{g}{f}\right)^{1/4}\alpha _n^a$$
(30)
so that their algebra is energy independent. It is also convenient to define,

$$\beta _0^a=\frac{1}{f^{3/4}g^{1/4}}𝐏_{cm}^a$$
(31)
Their algebra is

$`[𝐱^a,\beta _0^b]`$ $`=`$ $`i\left({\displaystyle \frac{f}{g}}\right)^{1/4}\delta _b^a`$ (32)
$`[\beta _n^a,\beta _m^b]`$ $`=`$ $`n\eta ^{ab}\delta _{n+m}`$ (33)
We then define, as usual,

$$\stackrel{~}{M}^2=\underset{m>0}{}\beta _m\beta _m$$
(34)
In terms of these, the modified generators of the Virasoro algebra are

$$L_0=\frac{1}{2\pi Tf}[𝐏_{cm}^2+\sqrt{fg}\stackrel{~}{M}^2]$$
(35)
$$L_l=\sqrt{fg}\underset{m>0}{}\beta _{lm}\beta _m=\sqrt{fg}\stackrel{~}{L}_l$$
(36)
where $`\stackrel{~}{L}_l`$ are, for $`l0`$, the conventional Viraroso generators. The algebra is

$$[L_m,L_n]=\sqrt{fg}(mn)L_{mn}+fg\frac{Dm(m^21)}{12}\delta _{m+n}.$$
(37)
We see that the anomaly appears to be energy dependent,

$$c=fg\frac{Dm(m^2m)}{12}$$
(38)
Of course, as long as $`fg>0`$ for all $`𝐏_0`$ we can use the rescaled generators $`\stackrel{~}{L}_n=(fg)^{1/2}L_n`$, which have the conventional Virasoro algebra, with energy independent anomaly. However, as we will see shortly, there are interesting cases in which $`fg`$ vanishes for finite $`𝐏_0`$. In these cases we should be careful about which version of the Virasoro algebra is defined on the whole space of physical states.

Now we study the spectrum of the theory. It is most convenient to define $`k`$ as

$$𝐏_{cm}^a|0,k>=k^a|0,k>$$
(39)
as $`𝐏_{cm}^a`$ is in fact by (19) and (20) the quantity that defines the velocity of the center of mass of the string.

The ground state is defined as usual by $`L_n|0,k>=0`$. The ground state energy is given by

$$𝐏_{cm}^2=k^2=2\pi Taf\sqrt{fg}$$
(40)
where $`a`$ is the usual energy independent constant resulting from the normal ordering of $`\stackrel{~}{M}`$.

We see from these relations that the spectrum of the deformed string will be the same as the spectrum for the ordinary bosonic string, so long as we express momentum in terms of the non-linear variable

$$\stackrel{~}{p}^a=f^{3/4}g^{1/4}𝐏_{cm}^a$$
(41)
If $`f\sqrt{fg}>0`$ and is non-vanishing and non-singular, all the standard results on the string spectrum will go through regarding the elimination of ghosts, the extistence of a tachyon, $`a=1`$, etc. For example, we see directly from (40) that so long as $`f\sqrt{fg}>0`$ the ground state remains tachyonic. However, if we choose to violate this condition, we can eliminate the tachyonic ground state, as we will describe below. With a suitable choice of functions this can be done without reintroducing ghosts into the theory.

## 5 Examples

### 5.1 A simple example

Let us finally look at several examples that illustrate how much freedom is allowed by string theory, with regard to deforming the energy-momentum relations. We have found that to keep the embedding degrees of freedom linear, we must take $`f=g`$. We have also found that the character of the spectrum is unchanged if $`f^2`$ is positive, non-vanishing and non-singular.

One consequence is that a varying speed of light is ruled out . By computing $`c=dE/dp`$, for $`M=0`$, one finds that massless modes always move at the speed of light. On the other hand it is easy to accommodate the dispersion relation discussed in , by choosing

$$f=g=1L_P𝐏_0^{CM}.$$
(42)
Such a dispersion relation leads to a modified mass-energy relation . Setting $`l^2=1/(2\pi T)`$ (the string “length”), the usual string spectrum mass spectrum (inferred from the right hand side of (29)) is

$$l^2M_n^2=N1.$$
(43)
where $`N=_{n0}|\alpha _n^a|^2`$. However, the rest energy spectrum is now

$$E_n=\frac{M_n}{1+M_nL_P}$$
(44)
If $`lL_P`$, the lowest string states are uncorrected, but as the string energy approaches the Planck energy, states accumulate just below $`E_P=L_P^1`$ and can never exceed this energy. This is precisely the property sought in , ensuring an invariant border between classical and quantum gravity.

### 5.2 Eliminating the tachyon

It is also possible to choose deformations for which the ground state with negative $`M^2`$ is NOT a tachyon, a phenomenon already discussed in the context of neutrino flavour states . As we are about to see, this can be done by choosing deformations such that $`f^2`$ is not positive over its entire range. Note that there is nothing wrong with a negative $`f^2`$, because even though $`f`$ is then imaginary, it always leads to real Lorentz transformations (see  for how to construct them).

We can for example choose

$$f^2(𝐏_0^{CM})=1(L_P𝐏_0^{CM})^2$$
(45)
This fails to be positive only for high energies $`𝐏_{CM}^0>L_P^1`$. We get the rest mass-energy relation:

$$(𝐏_{CM}^0)^2=\frac{M^2}{1+(L_PM)^2}$$
(46)
Using (43) leads to the energy spectrum. In this case, if we choose the string scale $`l<L_P`$ the tachyon state ($`N=0`$) is no longer a tachyon. From (40), we have that at rest,

$$(𝐏_{CM}^0)^2=\frac{2\pi T}{\frac{L_P^2}{l^2}1}$$
(47)
Thus, whenever $`L_P>l`$ we have $`(𝐏_{CM}^0)^2>0`$. Indeed the $`N=0`$ state is the only state with $`𝐏_{CM}^0>L_P^1`$; states with $`N1`$ accumulate just under $`L_P^1`$. The lowest energy state is the first “excited” state $`N=1`$ for which $`M^2=0`$. As a result, the rest of the spectrum is as in the ordinary bosonic string, expressed in terms of $`\stackrel{~}{p}^2=f^2𝐏_{cm}^2`$.

Another example is given by

$$f^2(𝐏_0^{CM})=\frac{(\lambda 𝐏_0^{CM})^2}{2}\left(\pm \sqrt{1+\left(\frac{2}{\lambda 𝐏_0^{CM}}\right)^2}1\right)$$
(48)
where $`\lambda `$ is a length scale. The negative branch is chosen whenever $`(𝐏_0^{CM})^2<0`$. With this choice we can use $`E^2/f^2=M^2`$ to find the rest mass-energy relation:

$$E_n^2=\frac{M_n^2}{1+\frac{1}{(\lambda M_n)^2}}$$
(49)
If $`l>\lambda `$ (a condition satisfied if $`\lambda =L_Pl`$), then the $`N=0`$ state has $`M^2=1/l^2`$, but its rest energy squared is positive. The ground state is again the massless state $`N=1`$ (for which both $`M`$ and the rest $`E`$ are zero). The $`N=0`$ state has negative $`M^2`$ but behaves like a normal massive particle.

## 6 Conclusions

In this paper we introduced deformed dispersion relations into string theory, considering the bosonic string, and using perturbative canonical quantization methods. The results found here are only a first step, and more work is required to see if a consistent theory can be constructed along these lines.

The basic results we found may be summarized as follows.

* The deformations of the string action affect both the vibrational and center of mass modes. In most cases we find that the vibrational modes no longer decouple, and that only a very specific class of deformations preserve mode decoupling, those with $`f=g`$. This condition implies that the speed of light remains energy independent. Thus, it appears that the observation of an energy dependent speed of light would be difficult to fit into a consistent string theory.
* So long as $`fg>0`$ on the whole space of states, we can define conventional Virasoro generators, and the spectrum is as usual, but with a transformed center of mass energy and momentum. But there are intersesting cases in which $`fg`$ vanishes at finite $`𝐏_0`$, in which case care must be used to define the Virasoro generators for all states. The result can be an energy dependent central charge. It may still be possible to choose the ghost action so as to cancel the energy dependence of the central charge; this remains an interesting question for future work.
* For a large class of theories , those for which $`f=g`$ and $`f^2>0`$ and non-singular for its whole range, the usual conclusions concerning the elimination of ghosts and the presence of a tachyon hold.
* By choosing $`f^2<0`$ for energies near the string scale, the tachyonic mode of the bosonic string can be eliminated.
* The choice

$$f^2=1(L_P𝐏_0^{CM})^2$$
(50)
with $`l_P<l`$ is promising. It appears to produce a bosonic string without a tachyon, and it also appears to be ghost free.

## Acknowledgements

We would like to thank A. Tseytlin and J, Schwarz for helpful comments. JM thanks the Perimeter Institute for support and hospitality while this work was being done. LS was supported during the initial phase of this work by a gift from the Jesse Phillips Foundation.

## Appendix: Particle analogue

In order to understand the significance of the $`f=g`$ case, we now consider a simple model of a relativistic massive particle in $`D`$ dimensional Minkowski spacetime moving in a static potential. The action is given by

$$S=𝑑tp_a\dot{x}^aN$$
(51)
where the Hamiltonian constraint is

$$=\frac{f(E)}{2}\eta ^{ab}p_ap_b+g(E)[m^2+V[x^i]]$$
(52)
where $`f`$ and $`g`$ are as before functions of $`E=p_0`$ and the potential is a function only of the spatial coordinates $`x^i`$, so that $`E`$ is still a conserved quantity. We find that the equations of motion are,

$$\ddot{x}^i=\frac{fgN}{m}\frac{V}{x^i}$$
(53)
$$\ddot{x}^0=\frac{N^2}{m}p_i\frac{V}{x^i}[fg^{}f^{}g]$$
(54)
So that we see that there is an anomalous acceleration of $`x^0`$ unless we eliminate the last factor by choosing $`f=g`$. In this case we note that if we do not make such a choice we will not be able to fix the gauge in which $`x^0=Ct`$, which appears to contradict reparameterization invariance. The resolution of this apparent paradox is that when there is a potential and these modified energy momentum relations we cannot assume that a relativistic particle does not reverse direction in time, because there will be trajectories that pass through $`\dot{x}^0=0`$. So the failure of the $`x^0`$ equations of motion to linearize appears necessary if these trajectories are to be included as part of the theory.


format: text

text:
# Experimental realization of the one qubit Deutsch-Jozsa algorithm in a quantum dot

## Abstract

We perform quantum interference experiments on a single self-assembled semiconductor quantum dot. The presence or absence of a single exciton in the dot provides a qubit that we control with femtosecond time resolution. We combine a set of quantum operations to realize the single-qubit Deutsch-Jozsa algorithm. The results show the feasibility of single qubit quantum logic in a semiconductor quantum dot using ultrafast optical control.

Time-resolved optical spectroscopy in semiconductor quantum dots has recently progressed toward the full quantum control of excitons trapped inside a single dot.Bonadeo et al. (1998); Stievater et al. (2001); Zrenner et al. (2002); Htoon et al. (2002) These advances have stimulated proposals to use excitons in quantum dots as quantum bits Troiani et al. (2000); Chen et al. (2001); Biolatti et al. (2002) for implementation of quantum computing. Very recently, the ability to operate a two-qubit gate using exciton and biexciton states was demonstrated in a single quantum dot.Li et al. (2003) These achievements represent a step toward an all-optical implementation of quantum computing using excitonic qubits. The first algorithm that comes to mind in order to check the feasibility of quantum computation in this context is the Deutsch-Jozsa (DJ) algorithm.Deutsch and Jozsa (1992) This algorithm is one of the simplest quantum algorithms that provides an exponential speed-up with respect to classical algorithms. As such, it has been extensively studied and has been used in experimental demonstrations of simple quantum computation in a variety of systems. Chuang et al. (1998); Linden et al. (1998); Gulde et al. (2003) In this Rapid Communication we report the experimental realization of the DJ algorithm for a single qubit using an optimized version of the algorithmCollins et al. (1998).

The Deutsch problem Deutsch and Jozsa (1992) involves global properties of binary functions on a subset of the natural numbers. Given a natural number $`N`$, we can define a set called $`X_N`$ with all the natural numbers that can be represented with $`N`$ bits. A binary function $`f:X_N\{0,1\}`$ is called balanced if it returns $`0`$ for exactly half of the elements of $`X_N`$ and $`1`$ for the other half. Given a function that is either balanced or constant, the Deutsch problem consists of finding out which type it is. A general classical algorithm requires evaluating the function on more than half of the elements, requiring at least $`2^{N1}+1`$ evaluations. This causes the classical run time to grow exponentially with the input size. The Deutsch-Jozsa algorithm provides a way to solve the Deutsch problem on a quantum computer using a quantum subroutine that evaluates $`f`$. The problem and its solution provide an example of Oracle-based quantum computation.Berthiaume and Brassard (1994); Bennett et al. (1997) It is assumed that a quantum subroutine or Oracle contains the information about the unknown function. The algorithm gives a recipe on how to prepare (encoding) and read out (decoding) the qubit in an efficient way. In an experimental demonstration, we have not only to implement the algorithm (encoding and decoding operations), but we also have to build the Oracle. The specific structure of the Oracle, encoding and decoding is not unique and several versions can be found in the literature.Deutsch and Jozsa (1992); Chuang and Yamamoto (1995); Cleve et al. (1998); Collins et al. (1998). The one we are using hereCollins et al. (1998) allows us to implement the $`N`$=1 case with a single qubit.

Figure 1 shows a quantum circuit depiction of the algorithm. This circuit uses the following quantum transformations:

1. A Hadamard transformation independently applied to each qubit, $`\widehat{H}^N=\widehat{H}\mathrm{}\widehat{H}`$. A single qubit transformation is represented by

$$\widehat{H}=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right].$$
(1)
2. A $`f`$-controlled gate, whose operation is defined as

$$\widehat{U}_f|x=(1)^{f(x)}|x.$$
(2)

The final step in the algorithm measures the expectation value of the $`|00|`$ operator. This expectation value for a constant function will be equal to $`1`$ while for a balanced function it will be equal to $`0`$. When $`N`$=1 there are only four possible functions $`f_j:\{0,1\}\{0,1\}`$:

$`f_1(x)=0,`$ (3)
$`f_2(x)=1,`$ (4)
$`f_3(x)=x,`$ (5)
$`\text{and}f_4(x)=1x.`$ (6)
Of these four, $`f_1`$ and $`f_2`$ are constant while $`f_3`$ and $`f_4`$ are balanced. The explicit matrix forms of the $`\widehat{U}_f`$ operators are:

$$\widehat{U}_{f_1}=\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]=\widehat{I},\widehat{U}_{f_2}=\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]=\widehat{I},$$
(7)
$$\widehat{U}_{f_3}=\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]=\widehat{\sigma _z},\text{and}\widehat{U}_{f_4}=\left[\begin{array}{cc}\hfill 1& \hfill 0\\ \hfill 0& \hfill 1\end{array}\right]=\widehat{\sigma _z}.$$
(8)
We can see that the balanced functions share the same $`f`$-controlled operator except for a global phase. This is also true for the constant functions. If the qubit is initially in the state $`|0`$, the encoding transformation consists in one Hadamard operation that transforms the qubit to

$$\frac{1}{\sqrt{2}}(|0+|1).$$
(9)
By applying $`\widehat{U}_{f_j}`$ to the state in Eq. 9 we obtain

$$\widehat{U}_{f_j}\frac{1}{\sqrt{2}}(|0+|1)=\frac{1}{\sqrt{2}}[(1)^{f_j(0)}|0+(1)^{f_j(1)}|1].$$
(10)
For a constant function this gives

$$(1)^{f_j(0)}\frac{1}{\sqrt{2}}(|0+|1),$$
(11)
while for a balanced function we get

$$(1)^{f_j(0)}\frac{1}{\sqrt{2}}(|0|1).$$
(12)
As a decoding procedure, we apply again the Hadamard transformation. We obtain

$$(1)^{f_j(0)}|0$$
(13)
for a constant function, and

$$(1)^{f_j(0)}|1$$
(14)
for a balanced function. Therefore, by measuring one of the two states, one can decide in a deterministic way to which class $`f`$ belongs. We remark that if we were to obtain an answer using only classical operations, we would need to evaluate the unknown $`f`$ function twice, obtaining both $`f(0)`$ and $`f(1)`$ and comparing them. Conversely, the described quantum procedure only requires one call of the quantum subroutine $`\widehat{U}_f`$ is needed. Therefore the $`N`$=1 case of the DJ already shows that the quantum algorithm outperforms its classical counterpart by a factor of two in the number of evaluations.

We have been able to implement the single-qubit Deutsch-Jozsa algorithm discussed above using the excitonic states of a self-assembled InGaAs quantum dot as a qubit. The level scheme we used is depicted in Fig. 2. The absence of an exciton is taken as the $`|0`$ state of the qubit, while the first excited excitonic state is taken as $`|1`$. The $`|1`$ state population is monitored via a non-radiative transition to the exciton ground state (labeled as $`|1^{}`$) whose radiative recombination is recorded using a micro-photoluminescence setup.Htoon et al. (1999, 2000, 2001, 2002); Muller et al. (2004)

We will use two different unitary transformations to realize the Deutsch-Jozsa algorithm: a $`\frac{\pi }{2}`$ single qubit rotation and a phase shift. The corresponding explicit matrix forms are:

$$\widehat{U}_{\frac{\pi }{2}}=\frac{1}{\sqrt{2}}\left[\begin{array}{cc}\hfill 1& \hfill 1\\ \hfill 1& \hfill 1\end{array}\right]$$
(15)
and

$$\widehat{U}(\varphi )=\left[\begin{array}{cc}\hfill e^{i\frac{\varphi }{2}}& \hfill 0\\ \hfill 0& \hfill e^{i\frac{\varphi }{2}}\end{array}\right].$$
(16)
The single qubit rotation is realized by a $`\pi /2`$ pulse resonant with the $`|0`$ to $`|1`$ transition. We use the rotating wave approximation and the qubit is defined in the rotating frame. The phase gate $`\widehat{U}(\varphi )`$ is realized by controlling the phase of the optical pulses with respect to the first pulse which is used as a reference. This is achieved experimentally by a piezoelectric translation stage that controls the phase locking between the pulses. By choosing specific values for $`\varphi `$, $`\widehat{U}(\varphi )`$ becomes equivalent to the $`f`$-controlled operators, as shown in Table I. In this version of the algorithm, the Oracle distinguishes the operations within the same class only by a global phase in the single qubit space. We can always think about an additional reference qubit in the Oracle to make this phase physically measurable. However, this reference qubit will never come into play in the real algorithm since it is part of the internal structure of the Oracle.

Notice that although $`\widehat{U}_{\frac{\pi }{2}}`$ and $`\widehat{H}`$ behave in a similar way, they are not the same operator. It is easy to show that the only effect of this change is that the interpretation of the final result has to exchange balanced with constant functions. We can think about the quantum evolution of the qubit during the algorithm using the picture of a pseudo-spin in the Bloch sphere. The first pulse corresponds to an effective magnetic field in the $`+𝐲`$ direction that brings the pseudo-spin from $`𝐳`$ to the $`𝐱`$ direction. The phase shift corresponds to a rotation of the pseudo-spin around the $`𝐳`$ axis of multiples of $`\pi `$. The second pulse will bring the pseudo-spin back to $`𝐳`$ in the case of a balanced function (by destructive interference), and to $`+𝐳`$ in the case of a constant function. In this picture the $`N`$=1 Deutsch algorithm shows clearly its equivalence to a Mach-Zehnder interferometer experiment.Cleve et al. (1998)

The sample consisted of In0.5Ga0.5As MBE grown self-assembled quantum dots, kept at a temperature of 5 K inside a continuous flow liquid helium cryostat. The quantum dots were resonantly excited with pulses from a mode-locked Ti:Sa laser. The pulses were linearly polarized in a way to make sure only one state out of an anisotropy induced doublet was excited.Muller et al. (2004) By using a spectrometer combined with a two-dimensional liquid nitrogen cooled charge-coupled device (CCD) array detector, we were able to detect the integrated photoluminescence signals of many quantum dots at the same time.Htoon et al. (2000) This enabled us to search for a quantum dot with a large enough dipole moment (and thus a good signal-to-noise ratio) and a dephasing time larger than 20 ps for the excited state, which is the case for about 1% of the dots. We did not select any specific polarization at the detection.

The use of the excitonic ground state photoluminescence as the means of detection prevented us from being able to use this state as the $`|1`$ state of our qubit. This entailed a severe decrease in the dephasing time of the qubit, as the non-radiative decay from the excited state to the exciton ground state (necessary for our detection scheme to work) puts an upper bound in the coherence time of the exciton111Other mechanisms might further reduce the coherence time.. This upper bound is significant, since measured dephasing times for excitonic ground states are in the order of hundreds of picosecondsBorri et al. (2001); Birkedal et al. (2001); Bayer and Forchel (2002) while those for carefully chosen excited states (i.e. no further than approximately 20 meV apart from the corresponding ground state) range in the tens of picoseconds.Htoon et al. (2001)

The actual implementation of the algorithm was similar to that of standard wave packet interferometry measurements,Bonadeo et al. (1998); Kamada et al. (2001) but in the nonlinear excitation regime.Htoon et al. (2002) In order to establish the appropriate excitation intensity for a $`\frac{\pi }{2}`$ pulse, we first recorded Rabi Oscillations of the excited state.Kamada et al. (2001); Htoon et al. (2002) We also performed a low intensity wave packet interferometry measurement to estimate the dephasing time of the quantum dot.Bonadeo et al. (1998); Kamada et al. (2001) In that experiment, the photoluminescence signal is proportional to the wavefunction autocorrelation. By fitting the decay of the autocorrelation signal with an exponential function we were able to measure the dephasing time of the exciton in the dot, obtaining 40 ps as a result.

In the main experiment, the time delay between two identical resonant $`\frac{\pi }{2}`$ laser pulses (approximately 5 ps long) was scanned while simultaneously recording the photoluminescence. A mechanical translation stage controlled the coarse delay between the two pulses while a piezoelectric stage changed the fine delay. The fine delay is used to control the phase shift of the second pulse with respect to the first one. It can be mapped to the relative phase by the relation $`\varphi =\omega _0\tau `$, where $`\mathrm{}\omega _0`$ is the laser energy, and has been calibrated by performing wavepacket interferometry at low intensity on the quantum dot, keeping the mechanical stage at a fixed position.

The encoding and decoding consist of the preparation of the two pulses with the same phase. We can imagine that the Oracle controls the fine delay knob, and, by changing the relative phase, determines which one of the four functions is being implemented. Figure 3a shows the intensity of the detected photoluminescence as a function of the coarse delay between the two pulses. The lower and upper signals correspond to constructive and destructive interference depending on the relative phase of the two pulses. The contrast between the maxima and minima of the signal decreases as the delay between the pulses approaches the dephasing time of the dot (40 ps), leading to lower fidelities. Figures 3b-e describe the detailed behavior of the signal for various values of the phase difference between the two pulses.

We can now interpret this result in terms of the DJ quantum algorithm. As expected, the maximum population at $`|1`$ (that is maximum photoluminescence) occurs for even numbers of $`\pi `$ in the relative phase between the two pulses, corresponding to the constant quantum subroutines $`\widehat{U}_{f_{1,2}}`$. On the other hand, minima occur for odd numbers of $`\pi `$ in the phase shift between the two pulses, corresponding to the balanced quantum subroutines $`\widehat{U}_{f_{3,4}}`$. The probability of successfully solving the problem is related to the contrast of the maxima and minima in the interference process. We remark that the first three insets in Fig. 3 (all with a delay between the pulses between 10 and 20 ps) have a contrast of the order of 75%. This implies a fidelity for the quantum operations comparable to other similar implementations.Li et al. (2003) The fidelity is mainly limited by the dephasing time of the excited excitonic state of the quantum dot. Making the coarse delay between the pulses as short as possible gives the best fidelity (as can be seen in Fig. 3), but this delay must be no shorter than twice the excitation pulse width, so that any optical interference arising out of the overlap of the two pulses is negligible. Also, a detection scheme able to resonantly excite and then measure the exciton ground state would allow for much larger fidelities, due to the increased coherence times.

By using an interferometric set-up on an excitonic qubit system, we have been able to implement the single-qubit Deutsch-Jozsa algorithm. Although the 1-qubit version of the algorithm does not show all the features of Quantum Computing (in particular entanglement), it is an experimental demonstration of simple quantum computation, including superpositions and interference, in a solid state system.

###### Acknowledgements.

We would like to thank John Robertson for proof-reading the article and for his style corrections. This work was supported by NSF-NIRT (DMR-0210383), NSF-FRG (DMR-0306239), NSF-ITR (DMR-0312491), the Texas Advanced Technology program, and the W.M. Keck Foundation.


text:
# An Effect of Stimulated Radiation Processes on Radio Emission from Major Planets

AN EFFECT OF STIMULATED RADIATION PROCESSES ON RADIO EMISSION FROM MAJOR PLANETS. F. V. Prigara, Institute of Microelectronics and Informatics, Russian Academy of Sciences, 21 Universitetskaya, 150007 Yaroslavl, Russia, (fprigara@imras.yar.ru).

The standard theory of thermal radio emission encounters some difficulties. The most crucial one is non-possibility to explain the radio spectrum of Venus in the decimeter range . The radio spectra of planetary nebulae at high frequencies also are not comfortably consistent with the standard theory . Here we show that the account for an induced character of radiation processes sufficiently improves the predictions of the standard theory.

It was shown recently  that thermal radio emission has a stimulated character. According to this conception thermal radio emission from non-uniform gas is produced by an ensemble of individual emitters. Each of these emitters is a molecular resonator the size of which has an order of magnitude of mean free path l of photons

$$l=\frac{1}{n\sigma }$$
(1)
where n is the number density of particles and $`\sigma `$ is the absorption cross-section.

The emission of each molecular resonator is coherent, with the wavelength

$$\lambda =l,$$
(2)
and thermal radio emission of gaseous layer is incoherent sum of radiation produced by individual emitters.

The condition (2) implies that the radiation with the wavelength $`\lambda `$ is produced by the gaseous layer with the definite number density of particles n .

The condition (2) is consistent with the experimental results by Looney and Brown on the excitation of plasma waves by electron beam . The wavelength of standing wave with the Langmuir frequency of oscillations depends on the density as predicted by equation (1). The discrete spectrum of oscillations is produced by the non-uniformity of plasma and the readjustment of the wavelength to the length of resonator. From the results of experiment by Looney and Brown the absorption cross-section for plasma can be evaluated.

Let us apply the above-formulated condition for emission to the atmosphere of planet. In this case the number density of molecules n continuously decreases with the increase of height h in accordance with barometrical formula

$$n=n_0exp(\frac{mgh}{kT})$$
(3)
where $`m`$ is the mass of molecule, $`g`$ is the gravity acceleration; $`k`$ is the Boltzmann constant (e.g., ). Here the temperature of atmosphere $`T`$ is supposed to be constant. In fact the temperature changes with the increase of height, so the formula (3) describes the change of molecule concentration in the limits of layer, for which we can consider the temperature to be approximately constant (the temperature changes with the increase of height essentially slower than the concentration of molecules).

If the emitting particles are the molecules of definite sort, then their number density is monotonously decreasing with the increase of height. Therefore, according to the condition for emission (1), the radio waves with the wavelength $`\lambda `$ are emitted by the gaseous layer, located at well-defined height h in atmosphere. Thus, the relation between the brightness temperature of radio emission and wavelength T($`\lambda `$) reproduces (partially or in whole) the temperature section across the atmosphere T(h).

This is the case for the Venus atmosphere. Here the emitting particles are the molecules of $`CO_2`$. This oxide of carbon is the main component of Venus atmosphere, its contents being 97%. The data concerning the brightness temperature of radio emission from Venus are summarized in .

Assuming $`\sigma =10^{15}cm^2`$ and using the condition for emission (1), we can find the number density of emitting molecules n in the gaseous layer, which emits the radio waves with given wavelength $`\lambda `$. Then, with the help of barometrical formula (3) and the data upon the pressure and the temperature in the lower layer of Venus atmosphere , we can establish the height of emitting layer in the atmosphere. This procedure gives the temperature section of Venus atmosphere similar to those of Earth’s atmosphere. It is not in contradiction with the data received by the means of spacecrafts Venera, since on these apparatus the temperature was measured only in the limits of troposphere, up to the height 55 km.

Though the direct measurements of a temperature profile at the heights of 100 to 160 km are absent, the electron density profile for these heights is available . Using the theory of thermal ionization , one can see that the night profile of electron density is in agreement with the temperature profile derived in the present paper.

Quite similarly the brightness temperature of Jovian thermal radio emission in the range of 0.1 cm to 4 cm as a function of wavelength  reproduces the temperature section of Jovian atmosphere. In this case the temperature structure of atmosphere also is similar to those of Earth’s atmosphere: there are two minimums of temperature (tropopause and mesopause) and one intermediate maximum (mesopeak).

The observational data concerning the thermal radio emission of Mars, Saturn, Uranus and Neptune are not so complete as in the case of Venus and Jupiter. These data, however, are in agreement with Earth type temperature structure of atmosphere. In the case of Mars the measurements of pressure and temperature in the lower layer of atmosphere are available , so one can reproduce using the radio emission data the temperature section of Mars atmosphere. Here the emitting particles are the CO2 molecules as in the case of Venus atmosphere.

The intermediate maximum of temperature in the region of mesopeak perhaps can be explained by absorption and next re-emission of infrared radiation transferred from the lower layers of atmosphere .

If the planetary atmosphere is sufficiently dense, the own thermal radio emission from the solid surface of the planet is quenched, and only the radio emission from the planetary atmosphere is observed. In accordance with equations (1) and (2), the condition for the quenching of thermal radio emission with the wavelength $`\lambda `$ from a solid surface in a dense atmosphere is as follows

$$n_0>\frac{1}{\lambda \sigma }$$
(4)
where $`n_0`$ is the number density of molecules nearby the solid surface. The condition (4) is valid both for Venus and Mars at radio wavelengths.

Equation (4) determines the quenching of thermal emission from the solid surface in the gaseous atmosphere in the whole Rayleigh-Jeans region of spectrum, not only in the radio band.

REFERENCES

 Chamberlain J. W. (1978), Theory of Planetary Atmospheres (New York: Academic Press).  Hubbard W. B. (1984), Planetary Interiors (London: Van Nostrand Reinhold).  Ksanfomality L.V. (1985), The Planet Venus (Moscow: Nauka).  Mayer C. H. (1970), in Surfaces and Interiors of Planets and Satellites, ed. A. Dollfus (New York: Academic Press).  Prigara F.V. (2003), Astron. Nachr., 324, No. S1, 425.  Siodmiak N. and Tylenda R. (2001), A&A, 373, 1032.  Landau L.D. and Lifshitz E.M. (1976), Statistical Physics (Moscow: Nauka).  Alexeev B.V. (2003), Usp. Fiz. Nauk, 173, 145, Physics-Uspekhi, Vol.46.  Chen F.F. (1984), Introduction to Plasma Physics and Controlled Fusion, Vol.1: Plasma Physics (New York: Plenum Press).


text:
# 0 Introduction

## 0 Introduction

In their work on cluster algebras , S. Fomin and A. Zelevinsky have introduced simplicial fans associated to finite crystallographic root systems. These fans are associated with convex polytopes called generalized associahedra  and have been shown to be related to classical combinatorial objects such as triangulations, noncrossing and nonnesting partitions and Catalan numbers. The lattice of noncrossing partitions, which was defined first for symmetric groups by G. Kreweras , has been recently generalized to all finite Coxeter groups . Surveys of its properties can be found in  and .

The aim of the present article is twofold. First, a refined enumerative invariant, called the $`F`$-triangle, of the fan associated to a root system is introduced and an inductive procedure is given for its computation. The $`F`$-triangle is then related to a simple combinatorial bicomplex and its spectral sequences. The second theme is a conjecture which relates, through an explicit change of variables, the $`F`$-triangle of a root system and a bivariate polynomial defined in terms of the noncrossing partition lattice for the corresponding Weyl group. Several evidences are given for this conjecture.

The final section contains the computation of the $`F`$-triangle for the root systems of type $`A`$ and $`B`$, using arguments based on hypergeometric functions.

Thanks to C. Krattenthaler for his help with hypergeometric identities.

## 1 The simplicial fans of clusters

Let $`\mathrm{\Phi }`$ be the root system associated to an irreducible Dynkin diagram $`X_n`$ of finite type and rank $`n`$. Thus $`X_n`$ is among the Killing-Cartan list $`A_n,B_n,C_n,D_n`$ or $`E_6,E_7,E_8,F_4,G_2`$. Let $`I`$ be the underlying set of the Dynkin diagram and $`\{\alpha _i\}_{iI}`$ be the set of simple positive roots in $`\mathrm{\Phi }`$.

Let us recall briefly the construction by S. Fomin and A. Zelevinsky of the simplicial fan $`\mathrm{\Delta }(\mathrm{\Phi })`$. Let $`\mathrm{\Phi }_1`$ be the union of the set of negative simple roots $`\{\alpha _i\}_{iI}`$ with the set $`\mathrm{\Phi }_{>0}`$ of positive roots. Elements of $`\mathrm{\Phi }_1`$ are called almost positive roots. A symmetric binary relation on $`\mathrm{\Phi }_1`$ called compatibility was defined in . The following is \[11, Theorem 1.10\].

###### Theorem 1

The cones spanned by subsets of mutually compatible elements in $`\mathrm{\Phi }_1`$ define a complete simplicial fan $`\mathrm{\Delta }(\mathrm{\Phi })`$.

From now on, cones of the fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ will be identified with their spanning set of mutually compatible elements of $`\mathrm{\Phi }_1`$. The cones of dimension $`n`$ of $`\mathrm{\Delta }(\mathrm{\Phi })`$ are in bijection with maximal mutually compatible subsets of $`\mathrm{\Phi }_1`$, which are called clusters. The cones of dimension $`1`$ of $`\mathrm{\Delta }(\mathrm{\Phi })`$ are in bijection with $`\mathrm{\Phi }_1`$ and will be called roots. A cone of $`\mathrm{\Delta }(\mathrm{\Phi })`$ is called positive if it is spanned by positive roots and non-positive else.

One can define a fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ also for a non-irreducible root system $`\mathrm{\Phi }`$, as the product of the fans associated to its irreducible components.

Let $`P`$ be the closed cone spanned by simple positive roots. This is not a cone of $`\mathrm{\Delta }(\mathrm{\Phi })`$ in general.

###### Proposition 1

The cone $`P`$ is exactly the union of all positive cones of $`\mathrm{\Delta }(\mathrm{\Phi })`$.

* Proof. Each positive cone is spanned by positive roots, hence is contained in $`P`$. Conversely, as the fan is complete, $`P`$ is contained in the union of all cones whose interior meet $`P`$. The interior of a non-positive cone does not meet $`P`$ as it consists of vectors with at least one negative coordinate in the basis of simple roots. Hence $`P`$ is contained in the union of all positive cones.

As a special case of the description of the fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ in , the following Lemma holds.

###### Lemma 1

The span of negative simple roots is a cone of $`\mathrm{\Delta }(\mathrm{\Phi })`$

We recall \[11, Proposition 3.6\] for later use.

###### Proposition 2

For every subset $`JI`$, the correspondence $`cc\{\alpha _i\}_{iJ}`$ is a bijection between cones of $`\mathrm{\Delta }(\mathrm{\Phi })`$ whose negative part is $`J`$ and positive cones of $`\mathrm{\Delta }(\mathrm{\Phi }(IJ))`$, where $`\mathrm{\Phi }(IJ)`$ is the restriction of the root system $`\mathrm{\Phi }`$ to $`IJ`$.

## 2 The $`F`$-triangle and the bicomplex of cones

Let us define the $`F`$-triangle by its generating function

$$F(\mathrm{\Phi })=F(x,y)=\underset{k=0}{\overset{n}{}}\underset{\mathrm{}=0}{\overset{n}{}}f_{k,\mathrm{}}x^ky^{\mathrm{}},$$
(1)
where $`f_{k,\mathrm{}}`$ is the cardinality of the set $`C_{k,\mathrm{}}`$ of cones of $`\mathrm{\Delta }(\mathrm{\Phi })`$ spanned by exactly $`k`$ positive roots and $`\mathrm{}`$ negative simple roots. The coefficient $`f_{k,\mathrm{}}`$ vanishes if $`k+\mathrm{}>n`$, hence the name triangle.

###### Proposition 3

The $`F`$-triangle has the following properties.

1. If $`\mathrm{\Phi }`$ and $`\mathrm{\Phi }^{}`$ are two root systems, one has $`F(\mathrm{\Phi }\times \mathrm{\Phi }^{})=F(\mathrm{\Phi })\times F(\mathrm{\Phi }^{})`$.
2. If $`\mathrm{\Phi }`$ is an irreducible root system on $`I`$, then one has

$$_yF(\mathrm{\Phi }(I))=\underset{iI}{}F(\mathrm{\Phi }(I\{i\})),$$
(2)
where $`\mathrm{\Phi }(I\{i\})`$ is the restriction of the root system $`\mathrm{\Phi }`$ to $`I\{i\}`$.

* Proof. The first statement is obvious. The proof of the second statement is by double counting of the sets of pairs

$$\{(i,c)\alpha _ic\text{ and }cC_{k,\mathrm{}}\},$$
(3)
for all $`k`$ and $`\mathrm{}`$. Let us fix $`k`$ and $`\mathrm{}`$.

On one side, the cardinalityof this set is just $`\mathrm{}f_{k,\mathrm{}}`$ by definition of $`C_{k,\mathrm{}}`$. On the other hand, by \[11, Proposition 3.5 (3)\], the cardinalityis given by the sum over $`iI`$ of $`f_{k,\mathrm{}1}^i`$ where $`f^i`$ is the $`F`$-triangle for the root system induced on $`I\{i\}`$.

This gives the equality

$$\mathrm{}f_{k,\mathrm{}}=\underset{iI}{}f_{k,\mathrm{}1}^i,$$
(4)
which proves the second assertion of the proposition.

The usual $`f`$-vector is given by the generating series

$$f(x)=\underset{k=0}{\overset{n}{}}f_kx^k=F(x,x),$$
(5)
where $`f_k`$ is the number of cones of dimension $`k`$.

The following is \[11, Proposition 3.7\].

###### Proposition 4

The $`f`$-vector has the following properties.

1. If $`\mathrm{\Phi }`$ and $`\mathrm{\Phi }^{}`$ are two root systems, one has $`f(\mathrm{\Phi }\times \mathrm{\Phi }^{})=f(\mathrm{\Phi })\times f(\mathrm{\Phi }^{})`$.
2. If $`\mathrm{\Phi }`$ is an irreducible root system on $`I`$, then one has

$$_xf(\mathrm{\Phi }(I))=\frac{\text{h}+2}{2}\underset{iI}{}f(\mathrm{\Phi }(I\{i\})),$$
(6)
where h is the Coxeter number of $`\mathrm{\Phi }`$.

Together Proposition 3 and Proposition 4 are sufficient to compute simultaneously the $`F`$-triangle and the $`f`$-vector by induction on the cardinality of $`I`$, using (5).

For example, the $`A_3`$ $`f`$-vector is $`(1,9,21,14)`$ and the $`A_3`$ $`F`$-triangle is presented below, with $`k=0`$ to $`3`$ from top to bottom and $`\mathrm{}=0`$ to $`3`$ from left to right.

$$\left[\begin{array}{cccc}1& 3& 3& 1\\ 6& 8& 3\\ 10& 5\\ 5\end{array}\right]$$
(7)
The $`F`$-triangle has a nice symmetry property, which is a refined version of the classical Dehn-Sommerville equations for complete simplicial fans.

###### Proposition 5

One has

$$F(x,y)=(1)^nF(1x,1y).$$
(8)
* Proof. The proof is just an adaptation of the original proof of the Dehn-Sommerville equations (see \[3, p. 212-213\]), taking care of the two different kind of half-edges of the fan. The proposition is equivalent to the set of equations

$$f_{i,j}=\underset{k,\mathrm{}}{}(1)^{n+k+\mathrm{}}\left(\genfrac{}{}{0pt}{}{k}{i}\right)\left(\genfrac{}{}{0pt}{}{\mathrm{}}{j}\right)f_{k,\mathrm{}},$$
(9)
for all $`i,j`$. Let us now fix $`i`$ and $`j`$ and compute $`f_{i,j}`$. First, it is given by

$$f_{i,j}=\underset{cC_{i,j}}{}1.$$
(10)
Then using Lemma 2, this is rewritten as

$$\underset{cC_{i,j}}{}\underset{cd}{}(1)^{n+dim(d)}.$$
(11)
Exchanging summations, one obtains

$$\underset{k,\mathrm{}}{}(1)^{n+k+\mathrm{}}\underset{dC_{k,\mathrm{}}}{}\underset{\genfrac{}{}{0.0pt}{}{cd}{cC_{i,j}}}{}1.$$
(12)
As the fan is simplicial, this is

$$\underset{k,\mathrm{}}{}(1)^{n+k+\mathrm{}}\left(\genfrac{}{}{0pt}{}{k}{i}\right)\left(\genfrac{}{}{0pt}{}{\mathrm{}}{j}\right)f_{k,\mathrm{}}.$$
(13)
The proposition is proved.

The following lemma is classical. It follows from the fact that the link of a simplex in a homology sphere is again a homology sphere, see \[3, p. 214\].

###### Lemma 2

Let $`c`$ be a cone in a complete simplicial fan of dimension $`n`$. Then

$$\underset{cd}{}(1)^{n+dim(d)}=1.$$
(14)
Let us now introduce two specializations of the $`F`$-triangle.

The positive $`f^+`$-vector is given by the generating series

$$f^+(x)=\underset{k=0}{\overset{n}{}}f_k^+x^k=F(x,0),$$
(15)
where $`f_k^+=f_{k,0}`$ is the number of positive cones of dimension $`k`$.

The natural $`f^{\mathrm{}}`$-vector is given by the generating series

$$f^{\mathrm{}}(x)=\underset{k=0}{\overset{n}{}}f_k^{\mathrm{}}x^k=F(x,1).$$
(16)
Its interpretation will be given later in Proposition 8.

The symmetry obtained in Proposition 5 has the following consequences.

###### Corollary 1

The $`f^+`$-vector and $`f^{\mathrm{}}`$-vector determine each other. One has

$$F(x,0)=(1)^nF(1x,1).$$
(17)
###### Corollary 2

One has

$$F(0,x)=(1)^nF(1,1x)=(x+1)^n.$$
(18)
Equivalently, one has $`F(1,y)=y^n`$.

* Proof. By Lemma 1, each subset of the set of negative simple roots is a cone of $`\mathrm{\Delta }(\mathrm{\Phi })`$.

Let us define a bicomplex on cones and study its two spectral sequences. This bicomplex is essentially the complex associated to the simplicial set defined by the fan, where the differential is split according to the two kinds of elements of $`\mathrm{\Phi }_1`$.

In the unital exterior algebra generated over $``$ by the set $`\mathrm{\Phi }_1`$, consider the linear span $`D`$ of the monomials associated to the cones of the fan $`\mathrm{\Delta }(\mathrm{\Phi })`$. The simplicial differential of a monomial in $`D`$ is defined by

$$d(\alpha _1\alpha _2\mathrm{}\alpha _k)=\underset{\mathrm{}=1}{\overset{k}{}}(1)^\mathrm{}1\alpha _1\alpha _2\mathrm{}\widehat{\alpha _{\mathrm{}}}\mathrm{}\alpha _k,$$
(19)
where $`\widehat{\alpha _{\mathrm{}}}`$ means that $`\alpha _{\mathrm{}}`$ has been removed.

This gives a complex $`(D,d)`$ computing the reduced homology of a sphere.

The differential $`d`$ is the sum of two maps $`d_+`$ and $`d_{}`$ which correspond respectively to the removal of a positive root or a negative simple root in a monomial. It is clear that each of $`d_+`$ and $`d_{}`$ is a differential. This defines a bicomplex structure on $`D`$ when bigraded by the number of positive roots and negative simple roots.

###### Proposition 6

The spectral sequence of $`D`$ starting with $`d_+`$ degenerates at first step.

* Proof. The complex $`(D,d_+)`$ decomposes as a direct sum of complexes $`D_S_{}`$ according to the fixed negative part $`S_{}`$. If this negative part $`S_{}`$ is not the full set $`\{\alpha _i\}_{iI}`$, the subcomplex $`D_S_{}`$ has no homology. To prove this, it is enough to consider the complex of positive cones for the differential $`d_+`$ for all root systems, as the subcomplex $`D_S_{}`$ with fixed negative part $`S_{}`$ is isomorphic to the complex of positive cones for a smaller root system by Proposition 2. The complex of positive cones for the differential $`d_+`$ has no homology because it computes the reduced homology of the contractible simplicial complex $`P`$, by Proposition 1.

###### Proposition 7

The spectral sequence of $`D`$ starting with $`d_{}`$ degenerates at second step.

* Proof. The complex $`(D,d_{})`$ decomposes as a direct sum of complexes $`D_{S_+}`$ according to the fixed positive part $`S_+`$ of pairwise compatible positive roots. Let $`N(S_+)`$ be the set of negative simple roots compatible with all roots of $`S_+`$. Then the complex $`D_{S_+}`$ is isomorphic to the tensor product over the set $`N(S_+)`$ of contractible complexes of the following shape

$$0\stackrel{}{}0.$$
(20)
Hence either $`N(S_+)`$ is empty and $`d_{}`$ vanishes on $`D_{S_+}`$, or the subcomplex $`D_{S_+}`$ has no homology. Therefore the homology of $`(D,d_{})`$ is concentrated in positive cones and is given exactly by positive cones which can not be extended with negative simple roots. This implies the collapsing of the spectral sequence at second step.

A positive cone of which is not a subcone of a non-positive cone is called a natural cone.

###### Proposition 8

The number of natural cones of dimension $`k`$ is $`f_k^{\mathrm{}}`$.

* Proof. The natural $`f^{\mathrm{}}`$-vector is by definition the Euler characteristic of the complex $`(D,d_{})`$. By the proof of Proposition 7, the homology of $`d_{}`$ is concentrated in degree $`0`$ and has dimension given by the numbers of natural cones.

The first step of the spectral sequence starting with $`d_{}`$ is therefore a complex on natural cones. Its homology is concentrated in degree $`n`$.

## 3 The Lattice of noncrossing partitions

The lattice $`\text{L}_W`$ of noncrossing partitions associated to a finite Coxeter group $`W`$ has been introduced independently in . The surveys  give a good feeling of its importance in different parts of mathematics. Let us recall shortly its definition.

Let $`n`$ be the rank of $`W`$. Let $`S=\{s_1,\mathrm{},s_n\}`$ be the set of simple reflections in $`W`$. Let $`T`$ be the set of all reflections in $`W`$. As $`W`$ is also generated by $`T`$, one can define a length function $`\mathrm{}_T`$ on $`W`$ with respect to the generators in $`T`$. Using this length function, a partial order is defined on $`W`$ as follows. Let $`v`$ and $`w`$ be two elements of $`W`$. Then $`vw`$ if and only if there exists $`t_1,\mathrm{},t_k`$ in $`T`$ such that $`w=t_1\mathrm{}t_kv`$ and $`\mathrm{}_T(w)=\mathrm{}_T(v)+k`$. Maximal elements for this partial order are exactly Coxeter elements of $`W`$, i.e. products in some order of the set $`S`$ of simple reflections. The group $`W`$ acting by conjugation gives automorphisms of this partial order, as the set $`T`$ of all reflections is stable by conjugation. As all Coxeter elements are conjugated, one can define, up to isomorphism, the noncrossing partition lattice $`\text{L}_W`$ to be the interval between the unit and a Coxeter element for this partial order.

From this description, one can see that the noncrossing partition poset associated to the product of two Coxeter groups is isomorphic to the product of the noncrossing partition posets associated to these groups.

We shall now recall some properties of $`\text{L}_W`$. The poset $`\text{L}_W`$ is a finite lattice which is graded of rank $`n`$ and self-dual. Let $`\widehat{0}`$ and $`\widehat{1}`$ be the minimum and maximum elements of $`\text{L}_W`$. Let $`\mu `$ be the Möbius function of $`\text{L}_W`$. Then the lattice $`\text{L}_W`$ has the following invariants.

###### Proposition 9

The Zeta polynomial of $`\text{L}_W`$ is

$$Z_W(X)=\underset{i=1}{\overset{n}{}}\frac{\text{h}Xe_i+1}{e_i+1},$$
(21)
the cardinalityof $`\text{L}_W`$ is

$$\mathrm{\#}\text{L}_W=\underset{i=1}{\overset{n}{}}\frac{\text{h}+e_i+1}{e_i+1},$$
(22)
and the Möbius number of $`\text{L}_W`$ is

$$\mu (\widehat{0},\widehat{1})=(1)^n\underset{i=1}{\overset{n}{}}\frac{\text{h}+e_i1}{e_i+1},$$
(23)
where h is the Coxeter number and $`e_1,\mathrm{},e_n`$ are the exponents of $`W`$.

This proposition follows from the known formulas for the Zeta polynomial of $`\text{L}_W`$ in the classical cases  and from the computation of the Zeta polynomials in the exceptional cases by V. Reiner . The statements about cardinal and Möbius numbers follows from the knowledge of the Zeta polynomial. The cardinality part of the Proposition can also be checked from the data in . To find a uniform proof of Proposition 9 is an interesting open problem.

Let $`\mathrm{rk}`$ be the rank function of $`\text{L}_W`$. Consider the following generating function for Möbius numbers of intervals in $`\text{L}_W`$ according to the ranks:

$$M(x,y)=\underset{ab}{}\mu (a,b)x^{\mathrm{rk}(b)}y^{\mathrm{rk}(a)}.$$
(24)
This generating function is called the $`M`$-triangle for $`W`$.

Let us assume from now on that $`W`$ is the Weyl group of a crystallographic root system $`\mathrm{\Phi }`$. Here is the main Conjecture.

###### Conjecture 1

The $`F`$-triangle for $`\mathrm{\Phi }`$ and the $`M`$-triangle for $`W`$ are related by the following invertible transformation:

$$(1y)^nF(\frac{x+y}{1y},\frac{y}{1y})=M(x,y/x).$$
(25)
Let us note that the left-hand side of (25) can be rewritten using Proposition 5 as

$$(y1)^nF(\frac{x+1}{y1},\frac{1}{y1}).$$
(26)
It is not hard to check by hand that Conjecture 1 holds for root systems of small ranks. It is probably possible to prove it for classical types using the combinatorial descriptions of the noncrossing lattices  and of the generalized associahedra . Using a computer, one could check it for most of the exceptional types. Rather than doing that, we prefer to give now several conceptual evidences for Conjecture 1.

### 3.1 First Evidence

Let us consider the value of (25) at $`x=0`$. The left-hand side becomes $`(1y)^nF(\frac{y}{1y},\frac{y}{1y})`$, which is nothing but the $`h`$-vector of the simplicial fan $`\mathrm{\Delta }(\mathrm{\Phi })`$. The right-hand side is

$$\underset{a}{}y^{\mathrm{rk}(a)},$$
(27)
which is known to coincide with the $`h`$-vector for all root systems, see . These $`h`$-vectors are sometimes called the generalized Narayana numbers. Note that there is no uniform proof of this fact known so far.

### 3.2 Second evidence

Let us compute the coefficient of $`x^n`$ in the constant term of (25) with respect to $`y`$. On the left-hand side, this is the number $`f_{n,0}`$ of positive clusters, which is known by \[11, Proposition 3.9\] to be given by

$$\underset{i=1}{\overset{n}{}}\frac{\text{h}+e_i1}{e_i+1}.$$
(28)
On the right-hand-side, one gets $`(1)^n`$ times the Möbius number $`\mu (\widehat{0},\widehat{1})`$, which is given by (23).

### 3.3 Third evidence

It is known that the lattice $`\text{L}_W`$ is self-dual \[4, §2.3\]. This fact implies the following symmetry of the $`M`$-triangle:

$$M(x,y)=(xy)^nM(1/y,1/x).$$
(29)
###### Claim 1

Assuming Conjecture 1, this symmetry is equivalent to Proposition 5.

Indeed, the symmetry of the $`M`$-triangle is equivalent to

$$M(x,y/x)=y^nM(x/y,1/x).$$
(30)
Now applying Conjecture 1 to the right-hand side, one gets (26), which is the same as (25) thanks to Proposition 5. This proves the claim.

### 3.4 Fourth evidence

Consider the value of (25) at $`x=1`$. The left-hand side is computed using (26) to be

$$(y1)^nF(0,\frac{1}{y1}).$$
(31)
But this is just $`y^n`$ by Corollary 2. That the right-hand side is also $`y^n`$ is a standard property of the $`M`$-triangle for graded posets of rank $`n`$ with $`\widehat{0}`$ and $`\widehat{1}`$.

### 3.5 Fifth evidence

By Proposition 3, the $`F`$-triangle has a multiplicative behavior with respect to product of root systems. It is classical that the $`M`$-triangle is also multiplicative for the product of lattices. These multiplicative behaviors are compatible with Formula (25).

## 4 Computation for type $`A`$

In this section, the $`F`$-triangle is computed for root systems of type $`A`$. This can serve as a first step towards the proof of Conjecture 1 in type $`A`$.

Let us first recall the known expression for the $`f`$-vector in type $`A`$ .

###### Proposition 10

The $`f`$-vector for $`A_n`$ is given by

$$\underset{k=0}{\overset{n}{}}\frac{1}{k+1}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left(\genfrac{}{}{0pt}{}{n+k+2}{k}\right)x^k.$$
(32)
Let us define a generating function for $`f`$-vectors of type $`A`$. First the $`f`$-vector for $`A_n`$ is made homogeneous of degree $`n`$ using a new variable $`z`$, then all homogenized $`f`$-vectors are added. Let

$$f=\underset{m=0}{\overset{\mathrm{}}{}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{1}{k+1}\left(\genfrac{}{}{0pt}{}{m+k}{k}\right)\left(\genfrac{}{}{0pt}{}{2k+m+2}{k}\right)x^kz^m.$$
(33)
Our aim is now to prove the following Proposition.

###### Proposition 11

The $`F`$-triangle for $`A_n`$ is given by

$$\underset{k=0}{\overset{n}{}}\underset{\mathrm{}=0}{\overset{n}{}}\frac{\mathrm{}+1}{k+\mathrm{}+1}\left(\genfrac{}{}{0pt}{}{n}{k+\mathrm{}}\right)\left(\genfrac{}{}{0pt}{}{n+k}{n}\right)x^ky^{\mathrm{}}.$$
(34)
Let us define similarly a generating function for the functions (34). Let

$$F=\underset{\mathrm{}=0}{\overset{\mathrm{}}{}}\underset{m=0}{\overset{\mathrm{}}{}}\underset{k=0}{\overset{\mathrm{}}{}}\frac{\mathrm{}+1}{k+\mathrm{}+1}\left(\genfrac{}{}{0pt}{}{k+\mathrm{}+m}{k+\mathrm{}}\right)\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{k+\mathrm{}+m}\right)x^ky^{\mathrm{}}z^m.$$
(35)
Recall that Proposition 3 and Formula (5) give a recursion for computing the $`F`$-triangle assuming that the $`f`$-vector is known. In type $`A`$, the induction given by Proposition 3 is easily seen to be equivalent to the equation $`_yF=F^2`$. Hence, to prove Proposition 11, it is enough to prove that $`_yF=F^2`$ and that the substitution of $`y`$ by $`x`$ in $`F`$ is $`f`$. This is done in the next two Lemmas.

###### Lemma 3

The partial derivative $`_yF`$ equals $`F^2`$.

* Proof. Let us fix $`k,\mathrm{},m`$ and consider the coefficient of $`x^ky^{\mathrm{}}z^m`$ in $`F^2`$. It is given by

$$\underset{k_1,\mathrm{}_1,m_1}{}\frac{(\mathrm{}_1+1)(2k_1+\mathrm{}_1+m_1)!}{(k_1+\mathrm{}_1+1)!m_1!k_1!}\frac{(\mathrm{}\mathrm{}_1+1)(2k2k_1+\mathrm{}\mathrm{}_1+mm_1)!}{(kk_1+\mathrm{}\mathrm{}_1+1)!(mm_1)!(kk_1)!}.$$
(36)
One can first do the summation with respect to $`m_1`$ using the Chu-Vandermonde identity. The result is

$$\begin{array}{c}\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m+1}{m}\right)\underset{k_1,\mathrm{}_1}{}\frac{\mathrm{}_1+1}{2k_1+\mathrm{}_1+1}\left(\genfrac{}{}{0pt}{}{2k_1+\mathrm{}_1+1}{k_1}\right)\hfill \\ \hfill \frac{\mathrm{}\mathrm{}_1+1}{2k2k_1+\mathrm{}\mathrm{}_1+1}\left(\genfrac{}{}{0pt}{}{2k2k_1+\mathrm{}\mathrm{}_1+1}{kk_1}\right).\end{array}$$
(37)
Then using a result of Carlitz \[7, Theorem 6, Formula (5.14)\] with parameters $`a=2,c=1,\alpha =\alpha ^{}=1,b=0,d=0,\beta =\beta ^{}=1`$, the remaining double sum can be computed. The result is

$$\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m+1}{m}\right)(1)^{\mathrm{}}\frac{2\mathrm{}4}{(2k+\mathrm{}+2)(2)}\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+2}{k}\right)\left(\genfrac{}{}{0pt}{}{2}{\mathrm{}}\right).$$
(38)
This can be rewritten as

$$\frac{(2k+\mathrm{}+m+1)!(\mathrm{}+2)(\mathrm{}+1)}{m!k!(k+\mathrm{}+2)!},$$
(39)
which is exactly the coefficient of $`x^ky^{\mathrm{}}z^m`$ in $`_yF`$. The Lemma is proved.

###### Lemma 4

The substitution of $`y`$ by $`x`$ in $`F`$ equals $`f`$.

* Proof. Let us fix $`K,m`$ and compute the coefficient of $`x^Kz^m`$ in this substituted $`F`$. This is given by

$$\frac{1}{(K+1)!m!}\underset{\mathrm{}}{}\frac{(\mathrm{}+1)(2K\mathrm{}+m)!}{(K\mathrm{})!}.$$
(40)
This is rewritten as

$$\frac{(K+m)!}{(K+1)!m!}\underset{\mathrm{}}{}\left(\genfrac{}{}{0pt}{}{\mathrm{}+1}{\mathrm{}}\right)\left(\genfrac{}{}{0pt}{}{2K+m\mathrm{}}{K\mathrm{}}\right).$$
(41)
Using the Chu-Vandermonde identity, this equals

$$\frac{(K+m)!}{(K+1)!m!}\left(\genfrac{}{}{0pt}{}{2K+m+2}{K}\right),$$
(42)
which in turn is equal to

$$\frac{(K+m)!(2K+m+2)!}{m!K!(K+1)!(K+m+2)!}.$$
(43)
This is exactly the coefficient of $`x^Ky^{\mathrm{}}`$ in $`f`$. The Lemma is proved.

## 5 Computation for type $`B`$

In this section, the $`F`$-triangle is computed for root systems of type $`B`$. Let us first recall the known expression for the $`f`$-vector in type $`B`$ .

###### Proposition 12

The $`f`$-vector for $`B_n`$ is given by

$$\underset{k=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n}{k}\right)\left(\genfrac{}{}{0pt}{}{n+k}{k}\right)x^k.$$
(44)
Let us define a generating function for $`f`$-vectors of type $`B`$ as we did before for type $`A`$. By convention, $`B_0`$ is $`A_0`$ and $`B_1`$ is $`A_1`$. Let

$$g=\underset{m=0}{\overset{\mathrm{}}{}}\underset{k=0}{\overset{\mathrm{}}{}}\left(\genfrac{}{}{0pt}{}{m+k}{k}\right)\left(\genfrac{}{}{0pt}{}{2k+m}{k}\right)x^kz^m.$$
(45)
Our aim is now to prove the following Proposition.

###### Proposition 13

The $`F`$-triangle for $`A_n`$ is given by

$$\underset{k=0}{\overset{n}{}}\underset{\mathrm{}=0}{\overset{n}{}}\left(\genfrac{}{}{0pt}{}{n}{k+\mathrm{}}\right)\left(\genfrac{}{}{0pt}{}{n+k1}{n1}\right)x^ky^{\mathrm{}}.$$
(46)
Let us define similarly a generating function for the functions (46). Let

$$G=\underset{\mathrm{}=0}{\overset{\mathrm{}}{}}\underset{m=0}{\overset{\mathrm{}}{}}\underset{k=0}{\overset{\mathrm{}}{}}\left(\genfrac{}{}{0pt}{}{k+\mathrm{}+m}{k+\mathrm{}}\right)\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m1}{k+\mathrm{}+m1}\right)x^ky^{\mathrm{}}z^m.$$
(47)
Recall again that Proposition 3 and Formula (5) give a recursion for computing the $`F`$-triangle assuming that the $`f`$-vector is known. In type $`B`$, the induction given by Proposition 3 is easily seen to be equivalent to the equation $`_yG=FG`$. Hence, to prove Proposition 13, it is enough to prove that $`_yG=FG`$ and that the substitution of $`y`$ by $`x`$ in $`G`$ is $`g`$. This is done in the next two Lemmas.

###### Lemma 5

The partial derivative $`_yG`$ equals $`FG`$.

* Proof. The proof is very similar to the type $`A`$ case and will be more sketchy. Let us fix $`k,\mathrm{},m`$ and consider the coefficient of $`x^ky^{\mathrm{}}z^m`$ in $`FG`$. It is given by

$$\begin{array}{c}\underset{k_1,\mathrm{}_1,m_1}{}\frac{(\mathrm{}_1+1)(2k_1+\mathrm{}_1+m_1)!}{(k_1+\mathrm{}_1+1)!m_1!k_1!}\hfill \\ \hfill \frac{(kk_1+\mathrm{}\mathrm{}_1+mm_1)(2k2k_1+\mathrm{}\mathrm{}_1+mm_11)!}{(kk_1+\mathrm{}\mathrm{}_1)!(mm_1)!(kk_1)!}.\end{array}$$
(48)
Let us consider separately the summation of factors depending on $`m_1`$ with respect to $`m_1`$:

$$\begin{array}{c}\underset{m_1}{}(kk_1+\mathrm{}\mathrm{}_1+mm_1)(2k_1+\mathrm{}_1+m_1)!\hfill \\ \hfill \frac{(2k2k_1+\mathrm{}\mathrm{}_1+mm_11)!}{m_1!(mm_1)!}.\end{array}$$
(49)
This sum can be split in two terms:

$$\begin{array}{c}\underset{m_1}{}\frac{(kk_1+\mathrm{}\mathrm{}_1)(2k_1+\mathrm{}_1+m_1)!(2k2k_1+\mathrm{}\mathrm{}_1+mm_11)!}{m_1!(mm_1)!}\hfill \\ \hfill +\underset{m_1}{}\frac{(2k_1+\mathrm{}_1+m_1)!(2k2k_1+\mathrm{}\mathrm{}_1+mm_11)!}{m_1!(mm_11)!}.\end{array}$$
(50)
Rewriting the summations with binomial coefficients gives

$$\begin{array}{c}(kk_1+\mathrm{}\mathrm{}_1)(2k_1+\mathrm{}_1)!(2k2k_1+\mathrm{}\mathrm{}_11)!\hfill \\ \hfill \underset{m_1}{}\left(\genfrac{}{}{0pt}{}{2k_1+\mathrm{}_1+m_1}{m_1}\right)\left(\genfrac{}{}{0pt}{}{2k2k_1+\mathrm{}\mathrm{}_1+mm_11}{mm_1}\right)\\ \hfill +(2k_1+\mathrm{}_1)!(2k2k_1+\mathrm{}\mathrm{}_1)!\\ \hfill \underset{m_1}{}\left(\genfrac{}{}{0pt}{}{2k_1+\mathrm{}_1+m_1}{m_1}\right)\left(\genfrac{}{}{0pt}{}{2k2k_1+\mathrm{}\mathrm{}_1+mm_11}{mm_11}\right).\end{array}$$
(51)
Using the Chu-Vandermonde identity for each of these two terms gives

$$\begin{array}{c}(kk_1+\mathrm{}\mathrm{}_1)(2k_1+\mathrm{}_1)!(2k2k_1+\mathrm{}\mathrm{}_11)!\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m}\right)\hfill \\ \hfill +(2k_1+\mathrm{}_1)!(2k2k_1+\mathrm{}\mathrm{}_1)!\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m1}\right).\end{array}$$
(52)
Now it is time to plug this result into the full summation (48). Let us do this separately for the the two terms of (52). The first term of (52) plugged into (48) gives

$$\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m}\right)\underset{k_1,\mathrm{}_1}{}\left(\genfrac{}{}{0pt}{}{2(kk_1)+(\mathrm{}\mathrm{}_1)1}{kk_1}\right)\frac{\mathrm{}_1+1}{2k_1+\mathrm{}_1+1}\left(\genfrac{}{}{0pt}{}{2k_1+\mathrm{}_1+1}{k_1}\right).$$
(53)
Using another formula of Carltiz \[7, (5.15)\] with parameters $`a=2,c=1,b=0,d=0,\alpha =0,\beta =0,\alpha ^{}=1,\beta ^{}=1`$, this becomes

$$\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m}\right)\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}}{k}\right)(\mathrm{}+1).$$
(54)
The second term of (52) plugged into (48) gives

$$\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m1}\right)\underset{k_1,\mathrm{}_1}{}\left(\genfrac{}{}{0pt}{}{2(kk_1)+(\mathrm{}\mathrm{}_1)}{kk_1}\right)\frac{\mathrm{}_1+1}{2k_1+\mathrm{}_1+1}\left(\genfrac{}{}{0pt}{}{2k_1+\mathrm{}_1+1}{k_1}\right).$$
(55)
Using again \[7, (5.15)\] with parameters $`a=2,c=1,b=0,d=0,\alpha =1,\beta =0,\alpha ^{}=1,\beta ^{}=1`$, this becomes

$$\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+m}{m1}\right)\left(\genfrac{}{}{0pt}{}{2k+\mathrm{}+1}{k}\right)(\mathrm{}+1).$$
(56)
Summing (54) and (56) gives

$$\frac{(\mathrm{}+1)(2k+\mathrm{}+m)!(k+\mathrm{}+m+1)}{k!m!(k+\mathrm{}+1)!}.$$
(57)
This is exactly the coefficient of $`x^ky^{\mathrm{}}z^m`$ in $`_yG`$. The Lemma is proved.

###### Lemma 6

The substitution of $`y`$ by $`x`$ in $`G`$ equals $`g`$.

* Proof. Let us fix $`K,m`$ and compute the coefficient of $`x^Kz^m`$ in this substituted $`G`$. This is given by

$$\left(\genfrac{}{}{0pt}{}{K+m}{K}\right)\underset{k=0}{\overset{K}{}}\left(\genfrac{}{}{0pt}{}{K+k+m1}{K+m1}\right).$$
(58)
This is rewritten using the standard column summation property of binomial coefficient as

$$\left(\genfrac{}{}{0pt}{}{K+m}{K}\right)\left(\genfrac{}{}{0pt}{}{2K+m}{K+m}\right).$$
(59)
This is exactly the coefficient of $`x^Ky^{\mathrm{}}`$ in $`g`$. The Lemma is proved.


text:
# Rectification and Flux Reversals for Vortices Interacting with Triangular Traps

\[

## Abstract

We simulate vortices in superconductors interacting with two-dimensional arrays of triangular traps. We find that, upon application of an ac drive, a net dc flow can occur which shows current reversals with increasing ac drive amplitude for certain vortex densities, in agreement with recent experiments and theoretical predictions. We identify the vortex dynamics responsible for the different rectification regimes. We also predict the occurrence of a novel transverse rectification effect in which a dc flow appears that is transverse to the direction of the applied ac drive.

\]

Vortices interacting with periodic pinning structures have been attracting considerable attention since they are an ideal system in which to study the static and dynamical behaviors of collectively interacting particles coupled to periodic substrates. In these systems, a variety of commensurability effects and novel vortex crystals can occur as a function of the ratio of the number of vortices to the number of pinning sites . The vortex crystals are composed of one or more vortices trapped at each pin with any remaining vortices located in the interstitial regions between the pinning sites. A variety of dynamical flow phases occur when a drive is applied, including the flow of interstitial vortices between the pinning sites  as well as channeling along rows of pinning . Much of the physics of vortices interacting with periodic pinning is also observed for repulsively interacting colloids in periodic optical trap arrays . In addition to the basic science issues, vortices interacting with periodic pinning arrays are relevant to possible technological applications of superconductors, such as critical current enhancement or controlled motion of flux for new types of devices.

Several methods have been proposed for using periodic pinning or controlled disorder in superconductors to create vortex ratchets, rectifiers, and logic devices . As in general ratchet systems, which can be deterministic or stochastic in nature , a vortex ratchet transforms an ac input into a dc response. Vortex ratchets can be created via asymmetric periodic pinning lines , asymmetric channels, or the asymmetry introduced by multiple ac drives in a system with a symmetric substrate . Ratchets constructed of periodic two-dimensional (2D) arrays of asymmetric pinning sites have also been proposed . Recently, both positive and negative vortex rectification have been experimentally realized in periodic arrays of triangular pinning sites . In Ref. , the triangles are arranged in a square lattice with the tips of the triangles oriented in the $`+y`$ direction. When an ac force is applied in the $`y`$ direction at low matching fields, rectification of the vortex motion in the $`+y`$ direction occurs over a range of ac amplitudes, with a peak rectification at a particular amplitude. For higher matching fields, there is a $`y`$ rectification at lower ac drives, followed by a $`+y`$ rectification at higher ac drives. This change in the rectification direction is explained in Ref.  as originating from the separate motion of interstitial vortices at low drives, giving $`y`$ rectification, and the motion of the pinned vortices at higher drives, producing $`+y`$ rectification. It is not clear how the motions of these two vortex species can be fully separated, especially in the presence of thermal fluctuations, and thus a clearer picture of the vortex dynamics producing the rectification is needed.

In this work we present simulations of vortices interacting with 2D square arrays of triangular pinning sites for parameters corresponding to the recent experiments of Ref. . We find a $`+y`$ rectification at low ratios $`n`$ of the number of vortices to the number of pinning sites, with a maximum $`+y`$ dc flux as a function of ac amplitude. When interstitial vortices are present, the initial rectification is in the $`y`$ direction, and is followed by a crossover to $`+y`$ rectification at higher ac amplitude, as seen in experiments. We find that for large ac amplitudes, when the motion of the vortex lattice becomes elastic, the rectification switches to the $`y`$ direction, which is explained in terms of channeling effects. We also predict a novel transverse ratchet effect where a dc motion is generated in the direction transverse to the applied ac drive. All of the effects we describe here should also occur for repulsively interacting colloidal particles interacting with 2D triangular traps.

We consider a thin film superconductor containing a square array of $`N_p=64`$ triangular pinning sites with periodic boundary conditions in the $`x`$ and $`y`$-directions. We add $`N_v=nN_p`$ vortices to the sample, each of which obeys the overdamped equation of motion

$$\eta \frac{d𝐫_i}{dt}=𝐟_i^{vv}+𝐟_p+𝐟_{AC}+𝐟_T.$$
(1)
Here the vortex-vortex interaction force, appropriate for a thin film superconductor, is $`𝐟_i^{vv}=_{ji}^{N_v}(\mathrm{\Phi }_0^2/\mu _0\pi \mathrm{\Lambda })\widehat{r}/r_{ij}`$, where $`\mathrm{\Phi }_0`$ is the elementary flux quantum and $`\mathrm{\Lambda }`$ is the thin film screening length . We use a fast summation method to evaluate this long-range interaction . The pinning force $`𝐟_p`$ comes from a square array of equilateral triangles with one vertex pointing in the $`+y`$ direction, as shown in Fig. 1. Every triangular

pin is modeled as three half-parabolas of equal strength, each of which attracts the vortex to a line passing through the center of the triangle and parallel to one of the sides. The pinning force is cut off at the edge of the triangle. The applied ac force $`𝐟_{AC}=A\mathrm{sin}(\omega t)\widehat{𝐫}`$ acts in the direction perpendicular to an applied ac current. Here we consider either $`f_{AC}^y=A\mathrm{sin}(\omega t)\widehat{𝐲}`$ or $`f_{AC}^x=A\mathrm{sin}(\omega t)\widehat{𝐱}`$, with no mixtures of ac drives. Temperature is modeled as random thermal kicks with the property $`<𝐟_T(t)>=0`$ and $`<𝐟_T(t)𝐟_T(t^{})>=2\eta k_BT\delta (tt^{})`$.

We match our parameters to those of the experiment in Ref. , performed in Nb films with $`\eta =1.4\times 10^{12}`$ Ns/m. We take $`T/T_c=0.98`$, giving $`f_T=0.46f_0`$, where $`f_0=\varphi _0^2/2\pi \mu _0\lambda ^3=1.09\times 10^5`$ N/m. At this temperature, the London penetration depth $`\lambda =\lambda (0)/(1(T/T_c)^2)^{1/2}=368`$ nm, so our pin spacing is $`2.09\lambda `$ in the $`x`$ direction and $`2.03\lambda `$ in the $`y`$ direction, and the pins are $`1.68\lambda `$ on a side. In the experiment, each pin held a maximum of three vortices, so to match this we set the pinning strength to $`f_p=1.05f_0`$. We fix $`\omega =78`$ kHz, higher than experiment due to the limitation of simulation time; however, since the behavior of the system is controlled by the ratio $`A/\omega `$, we compensate by taking $`A`$ larger than in experiment. We note that we find the same generic behaviors for other parameters, including a pinning array that is triangular rather than square.

In Fig. 1 we show the vortex positions and pin locations at $`A=0`$ for a system with a square array of triangular pins at fillings $`n=1`$, 2, 3, and 4. A global symmetry breaking occurs at $`n=2`$ between the two possible arrangements of the vortices allowed by the square pinning

lattice. All of the vortices sit in the pins for $`n3`$, but for $`n4`$ the vortex-vortex interaction is strong enough that some vortices move to the interstitial regions.

We first consider the dc depinning force $`f_{dp}`$ in the positive and negative $`y`$ directions by applying a dc driving force of increasing magnitude and measuring the average vortex velocity $`<V_y>`$. In the inset to Fig. 2(a) we plot $`|f_{dp}|`$ as a function of $`n`$. At $`n=1`$ the depinning is symmetric in the $`\pm y`$ directions, as expected given our model for the pinning. For $`n=2`$, $`|f_{dp}^y|`$ is twice as large as $`|f_{dp}^{+y}|`$, due to the fact that the vortices align vertically for $`+y`$ driving, and horizontally for $`y`$ driving. For $`n=3`$ and 4, $`|f_{dp}^{+y}|`$ is 25% larger than $`|f_{dp}^y|`$. Here, the vortex at the top of each pin acts to assist in the depinning of the vortices along the bottom of the pin for $`y`$ driving. For $`n>4`$, the depinning is dominated by the interstitial vortices and the asymmetry in the depinning is lost. The depinning asymmetry at $`n=2`$ to 4 should be large enough to be observable experimentally. Depinning in the $`\pm x`$ directions is symmetric for all $`n`$. Asymmetric depinning at noninteger $`n`$ was observed in Ref. .

We next consider the effect of an applied ac drive $`f_{AC}^y`$. We monitor the net dc velocity $`<V_y>`$ at fixed $`\omega `$ and sweep the ac amplitude $`A`$, averaging $`<V_y>`$ for 20 periods at each increment of $`A`$. In Fig. 2(a) we plot $`<V_y>`$ vs $`A`$ for $`n=1`$. For $`A<0.9`$, there is no net flow in $`x`$ or $`y`$, indicating that the vortices are still pinned. For $`A=0.9`$ a finite $`+y`$ dc velocity appears with no net $`x`$ dc velocity, corresponding to a $`+y`$ rectification. As $`A`$ increases further, $`<V_y>`$ increases, reaching a maximum at $`A=0.99`$ and then dropping back to zero at $`A=1.05`$. This behavior matches that seen in the experiments of Ref. . We find no steps in the $`+y`$ rectification regime, in agreement with the experiments, but in disagreement with recent $`T=0`$ simulations of a very small system for asymmetric pinning sites that predicted steps in the velocity vs

$`f_{AC}`$ curve . The transport does not occur in an organized step like flow, but is instead a stochastic process, as we will show in more detail in Fig. 3. In Fig. 2(b) and Fig. 2(c) we plot $`<V_y>`$ for $`n=2`$ and 3, respectively. These curves are similar to the $`n=1`$ case, with an initial pinned phase followed by $`+y`$ rectification that goes through a maximum with increasing $`A`$.

In Fig. 2(d) we show $`<V_y>`$ for the case of $`n=4`$ when interstitial vortices are present, as seen in Fig. 1(d). Here there is an initial negative rectification regime in the $`y`$ direction, followed by a crossover to a $`+y`$ rectification as seen in experiments . In Fig. 2(e,f) we plot the cases for $`n=5`$ and $`n=6`$, respectively, which show a similar rectification to that in Fig. 2(d). In all of these cases, a combination of interstitial and pinned vortices are present. As $`n`$ is increased further, the ratcheting effects are gradually reduced and become indistinguishable from thermal noise.

For $`n=1`$ in Fig. 2(a), at higher $`A>1.05`$, $`<V_y>`$ becomes negative, indicating $`y`$ rectification at high drives. This reversal occurs for all fillings but is most pronounced for $`n=1`$ and $`n=4`$, when the onset of the reversal falls at lower values of $`A`$. We predict that this effect should be easily observable in experiment, although it was not reported in Ref. . The high-drive $`y`$ rectification originates when the $`y`$ vortex motion occurs through interstitial channels while the $`+y`$ vortex motion becomes localized on top of a column of pinning, giving a larger drag during the $`+y`$ portion of the cycle.

To understand the role of interstitial and pinned vortices in the rectification process, we examine the dynamics of the vortices. In Fig. 3(a,b) we illustrate a typical example of vortex motion leading to $`+y`$ rectification at $`n=2`$ and $`A=1.0`$. Fig. 3(a) shows the vortex trajectories during 1/4 of the drive cycle when the drive is in the $`y`$ direction. At these temperatures, none of the vortices remain pinned. The vortex motion is uncoordinated and the vortices wander stochastically as they pass through the pinning. In contrast, during the $`+y`$ portion of the cycle shown in Fig. 3(b), the vortices are channeled both within and between the columns of pinning sites, and there is little wandering in the $`x`$ direction. This more focused motion leads to a greater overall displacement in the $`+y`$ direction, and a net $`+y`$ rectification. Similar motion occurs for $`n=1`$ and $`n=3`$, except that for $`n=1`$ all of the motion is confined to the pinning channel and there is no interstitial motion, so the net rectification is correspondingly reduced as seen in Fig. 2(a).

At $`n=4`$ and above, when interstitial vortices are present, $`y`$ rectification occurs at low drives, as shown in Fig. 2(d-f). In Fig. 3(c-d) we illustrate an example of vortex motion in the $`y`$ rectification regime for $`n=4`$ and $`A=0.35`$. Fig. 3(c) shows that the vortices meander moderately in the $`x`$ direction during the $`y`$ portion of the drive cycle. Note that none of the vortices remain pinned; instead, all of the vortices are participating in the motion, with pinned and interstitial vortices switching places frequently. During the $`+y`$ portion of the drive cycle shown in Fig. 3(d), the drive is too low to overcome the pinning force and allow the formation of channels of the type seen in Fig. 3(b). Instead, the $`+y`$ vortex flow is strongly diverted into the $`x`$ direction by the pins, reducing the net motion in the $`+y`$ direction, and resulting in an overall $`y`$ rectification. As $`A`$ is further increased, the vortices begin to overcome the pinning in the $`+y`$ direction and form channels during the $`+y`$ portion of the cycle, as illustrated in Fig. 3(f) for $`n=4`$ and $`A=0.75`$. This gives $`+y`$ rectification just as in Fig. 3(a-b). As $`n`$ increases above 4, the channels become more closely packed and the amount of vortex wandering in the $`x`$ direction during the $`y`$ portion of the cycle decreases, progressively lowering the net $`+y`$ rectification. The onset of the $`y`$ and $`+y`$ rectification phases also drops to

lower $`A`$ with increasing $`n`$ since the effectiveness of the pinning decreases with increasing vortex density.

In Fig. 4 we illustrate $`<V_x>`$ and $`<V_y>`$ when an ac drive $`f_{AC}^x`$ is applied in the $`x`$ direction for $`n=2`$ and 4. The net $`x`$ velocity is zero but we find a transverse rectification in the $`y`$ direction: $`y`$ for $`n=2`$ and $`+y`$ for $`n=4`$. The magnitude of the rectification is comparable to that seen for $`f_{AC}^y`$, and it should thus be experimentally observable. The transverse ratchet effect is produced by the interaction of the vortices with the pinning sites. For $`n=2`$, the vortices channel along the rows of pins and are deflected downward by the pinning sites, producing $`y`$ rectification. Similar motion occurs for $`n=3`$. For $`n=4`$ to 6, the interstitial vortices dominate the motion through channels that pass along the tips of the triangles, although all vortices are being pinned and depinned. The interstitial vortices are deflected upward by the vortices inside the pins, producing $`+y`$ rectification. Since the transverse motion does not require breaking of the $`x`$ direction symmetry of the system, it can also be observed for a dc $`x`$ direction drive.

In conclusion, we have conducted simulations of vortices in thin film superconductors interacting with triangular pinning sites for parameters relevant to recent experiments. We show that both a $`+y`$ and $`y`$ rectification can occur at depinning depending on whether interstitial vortices are present, in agreement with experiment. We find dc depinning anisotropy for $`n=2`$ to 4, but observe that even when the dc depinning is not anisotropic, rectification can still occur due to the fact that the vortex dynamics differs under ac and dc drives. Rectification in the $`+y`$ direction occurs when the ac drive overcomes the pinning strength and vortex channels form that flow in the $`+y`$ direction. When interstitial vortices are present at zero ac drive, an initial $`y`$ rectification occurs at lower ac drives due to scattering of the $`+y`$ vortex motion by the pinning sites. This occurs for $`n=4`$ and above, in agreement with experiments. We also predict that a novel transverse ratchet effect should occur when the ac drive is applied in the $`x`$ direction. Here, the rectification is in the $`y`$ direction. Our results should be generic to any type of repulsively interacting particles moving through triangular traps and may have potential applications for species fractionalization in colloidal systems.

This work was supported by the U.S. DoE under Contract No. W-7405-ENG-36.