text:
# References and links

## 1 Introduction

Bose-Einstein condensates (BECs) trapped in the periodic potentials created by optical lattices have become a thriving field of research in recent years . Since such systems are very similar in their theoretical description to electrons in a solid state crystal, many experiments have been carried out demonstrating phenomena that were, in some cases, well-known from condensed matter physics, e.g. Bloch oscillations and Landau-Zener tunneling . In a recent experiment, a BEC in an optical lattice even made possible the observation of a quantum phase transition that had, up to then, only been theoretically predicted for condensed matter systems .

Apart from the latter, most experiments to date have been carried out in the regime of shallow lattice depth, for which the system is well described by the Gross-Pitaevskii equation with a periodic potential. The nonlinearity induced by the mean-field of the condensate is included in this description and has been shown both theoretically and experimentally to give rise to instabilities  in certain regions of the Brillouin zone. In this paper we experimentally study these instabilities by accelerating the optical lattice and thus scanning the Brillouin zone in a controlled way.

Nonlinearity-induced instabilities are observed in many different branches of physics, and they provide a dramatic manifestation of strongly nonlinear effects (see review paper ). The effects of modulational and transverse instabilities have been observed mostly for continuous media. However, periodic structures can strongly influence such instabilities. The growth of the instability can be controlled in periodic structures where the effective geometric dispersion provides a key physical mechanism for manipulating waves in various physical systems, including Bragg gratings in optical fibers, waveguide arrays and, more recently, optically induced photonic lattices and crystals, as seen in recent observations of the propagation characteristics of a probe laser beam .

In this Letter we study, both theoretically and experimentally, matter wave propagation in optically-induced lattices near the condition for Bragg reflection. Formally, these experiments are closely linked to light scattering in periodic structures and can be described by similar mathematical models. In particular, our experiments reveal the role of nonlinear Bloch-wave interactions in periodic media.

This paper is organized as follows. After briefly describing in section 2 our experimental apparatus and the method used for scanning the Brillouin zone in a controlled way, we present the results of our experiments in section 3. A comparison between these results and a 1-D numerical simulation is the subject of section 4, followed by a discussion of our findings and prospects for future investigations (section 5).

## 2 Experimental setup and procedure

Our experimental apparatus for creating BECs of $`{}_{}{}^{87}Rb`$ atoms is described in detail in . The main feature of our apparatus relevant for the present work is the triaxial time-averaged orbiting potential (TOP) trap with trapping frequencies $`\nu _x:\nu _y:\nu _z`$ in the ratio $`2:1:\sqrt{2}`$. Our trap is, therefore, almost isotropic. The consequences for our experiment of this near isotropy will be discussed at the end of this paper.
The optical lattice is created by two counterpropagating laser beams with parallel linear polarizations and wavelength $`\lambda `$, as described in detail in . The two beams are derived from the first diffraction orders of two acousto-optic modulators that are phase-locked but whose frequencies are independent, allowing us to introduce a frequency difference $`\mathrm{\Delta }\nu `$ between them. The resulting periodic potential has a lattice constant $`d=\lambda /2=0.39\mu \mathrm{m}`$, and the depth of the potential (depending on the laser intensity and detuning from the atomic resonance of the rubidium atoms) can be varied between $`0`$ and $`2E_{rec}`$ ($`E_{rec}=\frac{\mathrm{}^2\pi ^2}{2md^2}`$). In addition, by linearly chirping the frequency difference $`\mathrm{\Delta }\nu `$, the lattice can be accelerated with $`a=d\frac{d\mathrm{\Delta }\nu }{dt}`$. In our experiments, we used accelerations ranging from $`a=0.3\mathrm{m}\mathrm{s}^2`$ to $`a=5\mathrm{m}\mathrm{s}^2`$.
The experimental protocol for ‘moving’ the condensate across the Brillouin zone is as follows. After creating BECs with $`10^4`$ atoms, we adiabatically relax the magnetic trap frequency to $`\nu _x=42\mathrm{Hz}`$. Thereafter, the intensity of the lattice beams is ramped up from $`0`$ to a value corresponding to a lattice depth of $`2E_{rec}`$. The ramping time is of the order of several milliseconds in order to ensure adiabaticity . Once the final lattice depth has been reached, the lattice is accelerated for a time $`t`$. Finally, both the magnetic trap and the optical lattice are switched off, and the condensate is observed after a time-of-flight of $`21\mathrm{ms}`$ by absorption imaging.

## 3 Results: visibility and radial width

When the lattice is accelerated, the condensate feels a force in the rest frame of the lattice, resulting in a change of quasimomentum of the condensate. In the linear problem, this simply means that when switching off the lattice and magnetic trap at the end of the acceleration process, the instantaneous group velocity of the condensate in the lattice frame is given by the inverse of the curvature of the lowest energy band of the lattice. The resulting Bloch oscillations have been observed in a previous experiment . In practice, the time-of-flight interference pattern of the condensate released from the lattice then consists of a series of well-defined peaks corresponding to the momentum classes (in multiples of the lattice momentum $`2p_{rec}=2\mathrm{}k_L`$ with $`k_L=2\pi /\lambda `$), as can be seen in Figs. 1 (a) and (c). The shape of the interference pattern in the transverse direction is shown in Figs. 1 (b) and (d).

In the nonlinear problem, the solutions of the Gross-Pitaevskii equation are predicted to be unstable in the vicinity of the Brillouin zone edge . When the condensate is close to the zone edge, the unstable solutions grow exponentially in time, leading to a loss of phase coherence of the condensate along the direction of the optical lattice. In our experiment, the time the condensate spends in the ‘critical region’ where unstable solutions exists is varied through the lattice acceleration. When the acceleration is small, the condensate moves across the Brillouin zone more slowly and hence the growth of the unstable modes  becomes more important. Figures 1 (c) and (d) show typical integrated profiles of the interference pattern for a lattice acceleration $`a=0.3\mathrm{m}\mathrm{s}^2`$. Here, the condensate has reached the same point close to the Brillouin zone edge as in Figs. 1 (a) and (b), but because of the longer time it has spent in the unstable region, the interference pattern is almost completely washed out. It is also evident that the radial expansion of the condensate is considerably enhanced when the Brillouin zone is scanned with a small acceleration.

In order to characterize our experimental findings more quantitatively, we define two observables for the time-of-flight interference pattern. By integrating the profile in a direction perpendicular to the optical lattice direction, we obtain a two-peaked curve (see Fig. 1 (a) ) for which we can define a visibility (in analogy to spectroscopy) reflecting the phase coherence of the condensate (visibility close to $`1`$ for perfect coherence, visibility $`0`$ for an incoherent condensate). In order to avoid large fluctuations of the visibility due to background noise and shot-to-shot variations of the interference pattern, we have found that a useful definition of the visibility is as follows:

$$visibility=\frac{h_{peak}h_{middle}}{h_{peak}+h_{middle}},$$
(1)
where $`h_{peak}`$ is the mean value of the two peaks (both averaged over $`1/10`$ of their separation symmetrically about the positions of the peaks). By averaging the longitudinal profile over $`1/3`$ of the peak separation symmetrically about the midpoint between the peaks, we obtain $`h_{middle}`$. For instance, applying this definition to the profiles shown in Figs. 1 (a) and (c), we obtain $`visibility=0.98`$ and $`visibility=0.6`$, respectively. Owing to fluctuations in the background and hence the definition of the zero point of the longitudinal profile, the visibility thus measured can slightly exceed unity, in which case we define it to be $`1`$. The second observable is the width of a Gaussian fit to the interference pattern integrated along the lattice direction over the extent of one of the peaks (see Fig. 1 (b) and (d)).

The results of our experiment are summarized in Fig. 2. For four different accelerations ($`a=5,1,0.5`$ and $`0.3\mathrm{m}\mathrm{s}^2`$) we measured the visibility and radial width of the interference pattern as a function of the quasimomentum of the condensate. For large accelerations, the quasimomentum can be simply calculated from $`a`$ and the duration of the lattice acceleration, whereas for small accelerations the restoring force of the magnetic trap has to be taken into account as the spatial motion of the condensate becomes appreciable. In these cases, we derived the quasimomentum reached in the experiment from a numerical integration of the semi-classical equations of motion of the condensate in the presence of the periodic potential (giving rise to Bloch oscillations due to the dispersion relation of the lowest energy band) and of the magnetic trap.
Figure 2 shows clearly that for accelerations down to $`1\mathrm{m}\mathrm{s}^2`$, both the visibility and the radial width of the interference pattern remain reasonably stable when the edge of the Brillouin zone is crossed. In contrast, for $`a=0.5\mathrm{m}\mathrm{s}^2`$ and $`a=0.3\mathrm{m}\mathrm{s}^2`$ one clearly sees a drastic change in both quantities as the quasimomentum approaches the value $`1`$. For those accelerations, the condensate spends a sufficiently long time in the unstable region of the Brillouin zone and hence loses its phase coherence, resulting in a sharp drop of the visibility. At the same time, the radial width of the interference pattern increases by a factor between $`1.5`$ and $`1.7`$. This increase is evidence for an instability in the transverse direction and may, for instance, be due to solitons in the longitudinal direction decaying into vortices via a snake instability . For $`a=0.5\mathrm{m}\mathrm{s}^2`$ and $`a=0.3\mathrm{m}\mathrm{s}^2`$, the interference patterns for quasimomenta larger than $`1`$ were so diffuse that it was not possible to measure the visibility nor the radial width in a meaningful way.

## 4 Comparison with a 1-D numerical simulation

As pointed out in the introduction, instabilities in nonlinear periodic structures are a topic of intense theoretical and experimental interest and have been discussed in many publications to date. In particular, the exact nature of the instabilities, in particular in 3-D, is still a matter of controversy. In this work, we limit ourselves to comparing our experimental results to a simple 1-D numerical simulation. A more in-depth discussion of 3-D simulations and analytical calculations will be presented elsewhere.

Figure 3 shows the results of a numerical integration of the one-dimensional Gross-Pitaevskii equation with the parameters of our experiment. The visibility was calculated in the same way as was done for the experimental interference patterns. It is clear from this simulation that it is, indeed, the nonlinearity that is responsible for the instability at the edge of the Brillouin zone. The nonlinearity can be characterized through the parameter

$$C=\frac{\pi n_0a_s}{k_L^2},$$
(2)
where $`n_0`$ is the density of the condensate and $`a_s=5.4\mathrm{nm}`$ is the $`s`$-wave scattering length of $`{}_{}{}^{87}Rb`$. For the experimental parameters used in the experiment described here, the value of $`C`$ was $`0.008`$.

When $`C`$ is set to $`0`$ in the numerical simulation, the visibility remains unaltered when the zone edge is crossed, whereas for finite values of $`C`$ the visibility decreases as a quasimomentum of $`1`$ is approached. Furthermore, the larger the value of $`C`$, the more pronounced the decrease in visibility near the band edge. For $`C=0.008`$, corresponding to the value realized in our experiment, the onset of the instability is located just below a quasimomentum of $`0.8`$. Experimentally, we find that the visibility starts decreasing consistently beyond a quasimomentum of $`0.60.7`$, agreeing reasonably well with the results of the simulation.

## 5 Discussion and outlook

The experimental results presented in this work demonstrate that at the edge of the Brillouin zone, a BEC in an optical lattice exhibits unstable behaviour. These instabilities are reproduced in a 1-D numerical simulation, and our experimental findings also agree qualitatively with recent 3-D simulations . The fact that we observe a significant effect of the instabilities below accelerations of $`0.5\mathrm{m}\mathrm{s}^2`$, for which the condensate spends more than $`2\mathrm{ms}`$ in the critical region around the edge of the Brillouin zone (having an extension of around $`1/10`$ of the BZ ), indicates that the growth rate of the instability should be of the order of $`500\mathrm{s}^1`$. This agrees reasonably well with a rough estimate of $`300\mathrm{s}^1`$ derived from a recent work by Wu and Niu .

Clearly, our approach has a number of shortcomings that prevent us from achieving a more quantitative agreement with theory and a better characterization of the instabilities. Firstly, in our experiment the condensate exhibits a residual sloshing motion, meaning that its velocity is not always exactly zero when we load it into the optical lattice. This results in an uncertainty in the quasimomentum which we estimate to be of the order of $`1015\%`$ and leads to a considerable scatter in the experimental data both of the visibility and the radial width, possibly masking a sharper transition between the stable and unstable regions. Also, the fact that our trap is almost isotropic makes it difficult for us to increase the nonlinear parameter $`C`$ through the condensate density by increasing the trap frequency, as this would result in an even stronger restoring force along the lattice direction, making it impossible to cross the BZ edge with a constant (and small) acceleration. In order to overcome this problem, it would be advantageous to use, for instance, a dipole trap which allows one to increase the radial trapping frequency whilst still maintaining a small longitudinal frequency. Another interesting question to address is whether the fact that the direction of our optical lattice is at a small angle (a few degrees) to the axis of the magnetic trap might lead to chaotic motion, contributing to the increase in radial width of the interference pattern we observe .

In summary, the present experimental observations confirm that Bose-Einstein condensates may be used to simulate a variety of nonlinear physics configurations that are also of interest to other areas of physics, such as solid state physics. Bose-Einstein condensates offer the added advantage of a large flexibility in the parameters and in the exploration of phenomena occurring on a millisecond time scale.

## Acknowledgments

We gratefully acknowledge stimulating discussion with Robin Scott and Andrew Martin. This work was supported by the MURST (PRIN2000 Initiative), the INFM (PRA ‘Photonmatter’), and by the EU through Contract No. HPRN-CT-2000-00125.


format: text

text:
# Cluster algebras: Notes for the CDM-03 conference

## 1. Introduction

Cluster algebras, first introduced and studied in , are a class of axiomatically defined commutative rings equipped with a distinguished set of generators (cluster variables) grouped into overlapping subsets (clusters) of the same finite cardinality. The original motivation for this theory lied in the desire to create an algebraic framework for total positivity and canonical bases in semisimple algebraic groups.

Since its inception, the theory of cluster algebras has developed several interesting connections and applications:

* Discrete dynamical systems based on rational recurrences .
* $`Y`$-systems in thermodynamic Bethe Ansatz .
* Generalized associahedra associated with finite root systems .
* Quiver representations .
* Grassmannians, projective configurations and their tropical analogues .
* Quantum cluster algebras, Poisson geometry and Teichmüller theory .

In these lectures, we concentrate on the following aspects. Sections 2 and 3 set the groundwork for the future theory by supplying a family of motivating examples. Specifically, Section 2111 This section contains material that was not covered in CDM-2003 lectures due to time constraints. We feel, however, that it is important to present in these notes what was historically the main motivating example for the creation of cluster algebra theory.  is devoted to total positivity and geometry of double Bruhat cells in semisimple groups (a closely related connection to canonical bases was discussed in ), while a more elementary setup of Section 3 involves Ptolemy relations, combinatorics of triangulations, and a Grassmannian of $`2`$-dimensional subspaces.

Section 4 introduces cluster algebras in earnest, and discusses some basic results, open problems and conjectures. Section 5 focuses on cluster algebras of finite type, including their complete classification and their combinatorics, which is governed by generalized associahedra, a family of convex polytopes associated with finite crystallographic root systems.

We present no proofs, each time referring the reader to primary sources. Some of the material in these notes is based on the coverage in the earlier surveys . Pictures were borrowed from .

## 2. Total positivity and double Bruhat cells

### 2.1. Total positivity in semisimple Lie groups

A matrix is *totally positive* (resp., *totally nonnegative*) if all its minors are positive (resp., nonnegative) real numbers. The first systematic study of these classes of matrices was undertaken in the 1930s by I. J. Schoenberg, and by F. R. Gantmacher and M. G. Krein. References to their papers and a discussion of further connections and applications of totally positive matrices (with an emphasis on algebraic and combinatorial aspects) can be found in . The interest in the subject intensified in the last decade due in large part to the discovery by G. Lusztig  of a surprising connection between total positivity and canonical bases for quantum groups. Among other things, Lusztig extended the subject by defining the *totally positive variety* $`G_{>0}`$ and the *totally nonnegative variety* $`G_0`$ inside every complex reductive group $`G`$. These ideas were further developed in . We are going to present some of the results obtained in those papers. For technical reasons, we restrict ourselves to the case where $`G`$ is semisimple and simply connected. Classical total positivity theory is recovered for $`G=SL_{r+1}()`$, the group of complex $`(r+1)\times (r+1)`$ matrices with determinant $`1`$.

Lusztig defined $`G_{>0}`$ and $`G_0`$ parametrically. As shown in , Lusztig’s original definition is equivalent to setting

(2.1) $`G_{>0}`$ $`=\{xG:\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}(x)>0\text{for all}\gamma ,\delta \},`$
$`G_0`$ $`=\{xG:\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}(x)0\text{for all}\gamma ,\delta \},`$
for a family of regular functions $`\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}`$ on $`G`$ called *generalized minors*. To be more specific, let $`r`$ be the rank of $`G`$, let $`\omega _1,\mathrm{},\omega _r`$ be the fundamental weights, and let $`W`$ be the Weyl group. (The standard terminology and notation used here is explained in more detail in .) The indices $`\gamma `$ and $`\delta `$ of a generalized minor are two elements of the $`W`$-orbit of the same fundamental weight $`\omega _i`$, i.e., two extremal weights in the same fundamental representation $`V_{\textcolor[rgb]{0,0,0}{\omega }_i}`$ of $`G`$. The corresponding minor $`\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}`$ is a suitably normalized matrix element of $`V_{\textcolor[rgb]{0,0,0}{\omega }_i}`$ associated with the weights $`\gamma `$ and $`\delta `$.

In the case $`G=SL_{r+1}()`$, the regular functions $`\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}`$ specialize to the ordinary minors (i.e., determinants of square submatrices) as follows. The Weyl group $`W`$ is identified with the symmetric group $`S_{r+1}`$, and $`V_{\textcolor[rgb]{0,0,0}{\omega }_i}=^i^{r+1}`$, the $`i`$th exterior power of the standard representation. All the weights of $`V_{\textcolor[rgb]{0,0,0}{\omega }_i}`$ are extremal, and are in bijection with the $`i`$-subsets of $`[1,r+1]=\{1,\mathrm{},r+1\}`$, so that $`W=S_{r+1}`$ acts on them in a natural way, and $`\omega _i`$ corresponds to $`[1,i]`$. If $`\gamma `$ and $`\delta `$ correspond to $`i`$-subsets $`I`$ and $`J`$, respectively, then $`\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma },\textcolor[rgb]{0,0,0}{\delta }}=\mathrm{\Delta }_{I,J}`$ is the minor with the row set $`I`$ and the column set $`J`$.

The natural geometric framework for studying the varieties $`G_{>0}`$ and $`G_0`$ is provided by the *double Bruhat cells*

(2.2)
$$G^{u,v}=BuBB_{}vB_{};$$

here $`u,vW`$, and $`B`$ and $`B_{}`$ are two opposite Borel subgroups in $`G`$. (For $`G=SL_{r+1}()`$, the standard choice for $`B`$ (resp., $`B_{}`$) is the subgroup of upper- (resp., lower-) triangular matrices.) The group $`G`$ has two *Bruhat decompositions*, with respect to $`B`$ and $`B_{}`$:

(2.3)
$$G=\underset{uW}{}BuB=\underset{vW}{}B_{}vB_{}.$$

Thus, $`G`$ is the disjoint union of all double Bruhat cells222The term “cell” is somewhat misleading since the topology of $`G^{u,v}`$ may be non-trivial..

Recall that the Weyl group $`W`$ is a Coxeter group generated by *simple reflections* $`s_1,\mathrm{},s_r`$. For $`wW`$, the *length* $`\mathrm{}=\mathrm{}(w)`$ is the shortest length of a sequence of indices $`𝐢=(i_1,\mathrm{},i_{\mathrm{}})`$ such that $`w=s_{i_1}\mathrm{}s_i_{\mathrm{}}`$. Such a sequence is called a *reduced word* for $`w`$. For $`G=SL_{r+1}()`$, the simple reflection $`s_iW=S_{r+1}`$ is the transposition of $`i`$ and $`i+1`$, and $`\mathrm{}(w)`$ is the number of inversions of a permutation $`w`$.

###### Theorem 2.1 (\[18, Theorem 1.1\]).

The variety $`G^{u,v}`$ is isomorphic to a Zariski open subset of an affine space of dimension $`r+\mathrm{}(u)+\mathrm{}(v)`$.

###### Example 2.2.

Let $`w_{}`$ be the longest element in $`W`$. Then $`G^{w_{},w_{}}`$ is the open double Bruhat cell given by:

(2.4)
$$G^{w_{},w_{}}=\{xG:\begin{array}{c}\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\omega }_i,w_{}\textcolor[rgb]{0,0,0}{\omega }_i}(x)0\hfill \\ \mathrm{\Delta }_{w_{}\textcolor[rgb]{0,0,0}{\omega }_i,\textcolor[rgb]{0,0,0}{\omega }_i}(x)0\hfill \end{array}\text{for all}i[1,r]\}.$$

Following , we define the *totally positive part* of $`G^{u,v}`$ by setting

(2.5)
$$G_{>0}^{u,v}=G^{u,v}G_0.$$

###### Proposition 2.3.

The totally positive part of the open double Bruhat cell is the totally positive variety: $`G_{>0}^{w_{},w_{}}=G_{>0}`$.

###### Example 2.4.

As a nice exercise in linear algebra, the reader is invited to check Proposition 2.3 for $`G=SL_3()`$. In other words: if all minors of a matrix $`x=(x_{ij})SL_3()`$ are real and nonnegative, and the minors

$$\mathrm{\Delta }_{1,3}(x)=x_{13},\mathrm{\Delta }_{12,23}(x),\mathrm{\Delta }_{3,1}(x)=x_{31},\mathrm{\Delta }_{23,12}(x)$$

are nonzero, then all the minors of $`x`$ are positive.

It turns out that the variety $`G_{>0}^{u,v}`$ is isomorphic to $`_{>0}^{r+\mathrm{}(u)+\mathrm{}(v)}`$. This was first demonstrated by G. Lusztig  by introducing local coordinates in $`G^{u,v}`$ which consist of rational functions that are not necessarily regular. To sharpen this result, we will need the following notion, which is a slight variation of the definition given in .

###### Definition 2.5.

A *TP-basis* for $`G^{u,v}`$ is a collection of regular functions $`F=\{f_1,\mathrm{},f_m\}[G^{u,v}]`$ with the following properties:

1. The functions $`f_1,\mathrm{},f_m`$ are algebraically independent and generate the field of rational functions $`(G^{u,v})`$; in particular, $`m=r+\mathrm{}(u)+\mathrm{}(v)`$.
2. The map $`(f_1,\mathrm{},f_m):G^{u,v}^m`$ restricts to a biregular isomorphism $`U(F)(_0)^m`$, where

(2.6)
$$U(F)=\{xG^{u,v}:f_k(x)0\text{ for all }k[1,m]\}.$$
3. The map $`(f_1,\mathrm{},f_m):G^{u,v}^m`$ restricts to an isomorphism $`G_{>0}^{u,v}_{>0}^m`$.

Condition (iii) can be rephrased as saying that $`f_1,\mathrm{},f_m`$ provide a *total positivity criterion* in $`G^{u,v}`$: an element $`xG^{u,v}`$ is totally nonnegative (i.e., $`xG_0`$) if and only if $`f_k(x)>0`$ for all $`k[1,m]`$.

The following theorem from  extends the results previously obtained in .

###### Theorem 2.6.

Each reduced word $`𝐢`$ for $`(u,v)W\times W`$ gives rise to a TP-basis $`F_𝐢`$ for $`G^{u,v}`$ consisting of generalized minors:

(2.7)
$$F_𝐢=\{\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma }_k,\textcolor[rgb]{0,0,0}{\delta }_k}:k[1,m]\};$$

here $`m=r+\mathrm{}(u)+\mathrm{}(v)`$, and the weights $`\gamma _k,\delta _k`$ are defined explicitly in terms of $`𝐢`$ in Definition 2.7 below.

###### Definition 2.7.

We will represent $`𝐢`$ as a sequence of indices $`(i_1,\mathrm{},i_m)`$ from the set

$$[1,r][1,r]\stackrel{\mathrm{def}}{=}\{1,\mathrm{},r\}\{1,\mathrm{},r\}$$

such that $`i_j=j`$ for $`j[1,r]`$, and

(2.8)
$$s_{i_{r+1}}\mathrm{}s_{i_m}=u,s_{i_{r+1}}\mathrm{}s_{i_m}=v,$$

with the convention $`s_i=1`$ for $`i[1,r]`$. In this notation, we define:

(2.9)
$$\gamma _k=s_{i_1}\mathrm{}s_{i_k}\omega _{|i_k|},\delta _k=s_{i_m}\mathrm{}s_{i_{k+1}}\omega _{|i_k|}.$$

###### Example 2.8.

Let $`G=SL_3()`$, and let $`u=v=w_{}=s_1s_2s_1=s_2s_1s_2`$ be the order-reversing permutation (the element of maximal length in the symmetric group $`W=S_3`$). Take $`𝐢=(1,2,1,2,1,1,2,1)`$. Then

(2.10)
$$F_𝐢=\{\mathrm{\Delta }_{1,3},\mathrm{\Delta }_{12,23},\mathrm{\Delta }_{1,2},\mathrm{\Delta }_{12,12},\mathrm{\Delta }_{1,1},\mathrm{\Delta }_{2,1},\mathrm{\Delta }_{23,12},\mathrm{\Delta }_{3,1}\}.$$

(The minors on the right-hand side are listed in the natural order, i.e., $`f_1=\mathrm{\Delta }_{1,3}`$, …, $`f_8=\mathrm{\Delta }_{3,1}`$.) The reader is invited to check that these $`8`$ minors provide a total positivity criterion in $`SL_3`$: a $`3\times 3`$ matrix $`x`$ with determinant $`1`$ is totally positive if and only if the evaluations of these $`8`$ minors at $`x`$ are positive.

### 2.2. Coordinate rings of double Bruhat cells

Theorem 2.6 was obtained a couple of years before the discovery of cluster algebras. In retrospect, it can be seen as the first step towards introducing the (upper) cluster algebra structure in the coordinate ring $`[G^{u,v}]`$. (Each collection $`F_𝐢`$ would give rise to a cluster in the future theory.) An impetus for introducing this structure came from a realization that working with the families $`F_𝐢`$ may not be sufficient for answering some natural questions about double Bruhat cells. Here is one such question: describe and enumerate the connected components of the real part of $`G^{u,v}`$. An important special case of this problem, with $`u=1`$ and $`v=w_{}`$ for $`G=SL_{r+1}()`$, was solved in ; see also related work . The general case was handled in  using results and ideas from  and the earlier papers mentioned above. (For follow-ups see .) The solution in  utilized the following general approach, which goes back to : try to find a “simple” Zariski open subvariety $`UG^{u,v}`$ such that the codimension in $`G^{u,v}`$ of the complement of $`U`$ is greater than $`1`$. If furthermore $`U`$ is “compatible” with the real part of $`G^{u,v}`$, then replacing $`G^{u,v}`$ by $`U`$ does not change the structure of connected components of the real part. In many cases (including the one covered in ) one can take

(2.11)
$$U=\underset{𝐢}{}U(F_𝐢),$$

where $`𝐢`$ runs over all reduced words for $`(u,v)`$, and $`U(F_𝐢)`$ is defined by (2.6). In general, however, the complement of the open subvariety (2.11) has codimension $`1`$, so one needs something else.

Here is the main construction from . Fix a pair $`(u,v)W\times W`$ and a reduced word $`𝐢`$ for $`(u,v)`$, written in the form $`𝐢=(i_1,\mathrm{},i_m)`$ as in Definition 2.7. For $`k[1,m]`$, abbreviate $`f_k=\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\gamma }_k,\textcolor[rgb]{0,0,0}{\delta }_k}`$, where $`\gamma _k`$ and $`\delta _k`$ are given by (2.9). We say that an index $`k[1,m]`$ is *$`𝐢`$-exchangeable* if $`r<km`$, and $`|i_p|=|i_k|`$ for some $`p>k`$. Denote by $`\mathrm{𝐞𝐱}=\mathrm{𝐞𝐱}_𝐢[1,m]`$ the subset of $`𝐢`$-exchangeable indices.

###### Lemma 2.9.

The subset

(2.12)
$$𝐜=\{f_k:k[1,m]\mathrm{𝐞𝐱}\}F_𝐢$$

depends only on $`u`$ and $`v`$, not on the particular choice of a reduced word $`𝐢`$. In particular, the cardinality $`n`$ of $`\mathrm{𝐞𝐱}`$ depends only on $`u`$ and $`v`$.

The set $`𝐜`$ can be described explicitly in terms of $`u`$ and $`v`$ as follows: $`f_j=\mathrm{\Delta }_{\textcolor[rgb]{0,0,0}{\omega }_j,v^1\textcolor[rgb]{0,0,0}{\omega }_j}`$ for $`j[1,r]`$, and $`f_k=\mathrm{\Delta }_{u\textcolor[rgb]{0,0,0}{\omega }_i,\textcolor[rgb]{0,0,0}{\omega }_i}`$ if $`i_k`$ is the last occurrence of $`\pm i`$ in $`𝐢`$.

###### Example 2.10.

In the special case of Example 2.8 (that is, $`G=SL_3()`$ and $`u=v=w_{}`$), we have $`\mathrm{𝐞𝐱}=\{3,4,5,6\}`$ and

$$𝐜=\{f_1,f_2,f_7,f_8\}=\{\mathrm{\Delta }_{1,3},\mathrm{\Delta }_{12,23},\mathrm{\Delta }_{23,12},\mathrm{\Delta }_{3,1}\}.$$

###### Lemma 2.11.

Each $`f_k𝐜`$ vanishes nowhere in $`G^{u,v}`$.

By Lemma 2.11, the coordinate ring $`[G^{u,v}]`$ contains the Laurent polynomial ring $`[𝐜^{\pm 1}]`$. Our efforts to understand $`[G^{u,v}]`$ should therefore concentrate on the functions $`f_k𝐜`$, that is, those with exchangeable indices $`k`$.

###### Theorem 2.12.

There is an integer $`m\times n`$ matrix $`\stackrel{~}{B}=\stackrel{~}{B}(𝐢)=(b_{ik})`$ (defined explicitly by (2.15) below) with rows labeled by $`[1,m]`$ and columns labeled by $`\mathrm{𝐞𝐱}`$, such that:

* for every $`k\mathrm{𝐞𝐱}`$, the function

(2.13)
$$f_k^{}=\frac{\underset{b_{ik}>0}{}f_i^{b_{ik}}+\underset{b_{ik}<0}{}f_i^{b_{ik}}}{f_k}$$

is regular on $`G^{u,v}`$ (i.e., $`f_k^{}[G^{u,v}]`$), and the collection

(2.14)
$$F_{𝐢;k}=F_𝐢\{f_k\}\{f_k^{}\}[G^{u,v}]$$

is a TP-basis for $`G^{u,v}`$;
* the complement in $`G^{u,v}`$ of the Zariski open subset $`U`$ given by

$$U=U(F_𝐢)\underset{k\mathrm{𝐞𝐱}}{}U(F_{𝐢;k})G^{u,v}$$

has codimension greater than $`1`$.

Consequently, $`[G^{u,v}]=[U]`$.

For the sake of completeness, we provide the definition of the matrix $`\stackrel{~}{B}=\stackrel{~}{B}(𝐢)`$ in Theorem 2.12 (cf. \[5, (8.7)\]). For $`p[1,m]`$ and $`k\mathrm{𝐞𝐱}`$, we have

(2.15)
$$b_{pk}=\{\begin{array}{cc}\epsilon (i_k)\hfill & \text{if }p=k^{}\text{;}\hfill \\ \epsilon (i_k)a_{|i_p|,|i_k|}\hfill & \text{if }p<k<p^+<k^+,\epsilon (i_k)=\epsilon (i_{p^+})\text{,}\hfill \\ & \text{or }p<k<k^+<p^+,\epsilon (i_k)=\epsilon (i_{k^+})\text{;}\hfill \\ \epsilon (i_p)a_{|i_p|,|i_k|}\hfill & \text{if }k<p<k^+<p^+,\epsilon (i_p)=\epsilon (i_{k^+})\text{,}\hfill \\ & \text{or }k<p<p^+<k^+,\epsilon (i_p)=\epsilon (i_{p^+})\text{;}\hfill \\ \epsilon (i_p)\hfill & \text{if }p=k^+\text{;}\hfill \\ 0\hfill & \text{otherwise,}\hfill \end{array}$$

where we use the following notation and conventions:

* $`\epsilon (i)=\pm 1`$ for $`i\pm [1,r]`$;
* $`A=(a_{ij})_{i,j[1,r]}`$ is the Cartan matrix of $`G`$, that is, the transition matrix between the simple roots and the fundamental weights:

(2.16)
$$\alpha _j=\underset{i=1}{\overset{r}{}}a_{ij}\omega _i.$$
* for $`k[1,m]`$, we denote by $`k^+=k_𝐢^+`$ the smallest index $`\mathrm{}`$ such that $`k<\mathrm{}m`$ and $`|i_{\mathrm{}}|=|i_k|`$; if $`|i_k||i_{\mathrm{}}|`$ for $`k<\mathrm{}m`$, then we set $`k^+=m+1`$;
* $`k^{}=k_𝐢^{}`$ denotes the index $`\mathrm{}`$ such that $`\mathrm{}^+=k`$; if such an $`\mathrm{}`$ does not exist, we set $`k^{}=0`$.

###### Example 2.13.

Let $`G`$ and $`𝐢`$ be as in Examples 2.8 and 2.10. Then

$$\stackrel{~}{B}=\stackrel{~}{B}(𝐢)=\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 1& 0& 0\\ 0& 1& 1& 0\\ 1& 0& 1& 1\\ 1& 1& 0& 1\\ 0& 1& 1& 0\\ 0& 1& 0& 1\\ 0& 0& 0& 1\end{array}\right),$$

where the columns are indexed by $`\mathrm{𝐞𝐱}=\{3,4,5,6\}`$. (Cf. \[5, Example 3.2\] and \[3, Example 2.5\].) Applying (2.13) to the $`f_i`$’s in (2.10), we get

$`f_3^{}`$ $`={\displaystyle \frac{f_2f_5+f_1f_4}{f_3}}={\displaystyle \frac{\mathrm{\Delta }_{12,23}\mathrm{\Delta }_{1,1}+\mathrm{\Delta }_{1,3}\mathrm{\Delta }_{12,12}}{\mathrm{\Delta }_{1,2}}}=\mathrm{\Delta }_{12,23},`$
$`f_4^{}`$ $`={\displaystyle \frac{f_3f_6+f_2f_5f_7}{f_4}}={\displaystyle \frac{\mathrm{\Delta }_{1,2}\mathrm{\Delta }_{2,1}+\mathrm{\Delta }_{12,23}\mathrm{\Delta }_{1,1}\mathrm{\Delta }_{23,12}}{\mathrm{\Delta }_{12,12}}}=\mathrm{\Delta }_{1,1}\mathrm{\Delta }_{23,23}1,`$
$`f_5^{}`$ $`={\displaystyle \frac{f_4+f_3f_6}{f_5}}=\mathrm{\Delta }_{22},`$
$`f_6^{}`$ $`={\displaystyle \frac{f_5f_7+f_4f_8}{f_6}}=\mathrm{\Delta }_{13,12}.`$
We note that, while each of the families $`F_{𝐢;3},F_{𝐢;5}`$, and $`F_{𝐢;6}`$ is itself of the form $`F_𝐢^{}`$ for some reduced word $`𝐢^{}`$, this is not the case for $`F_{𝐢;4}`$, if only for the reason that $`f_4^{}`$ is not a minor.

The last statement in Theorem 2.12 implies the following description of the coordinate ring $`[G^{u,v}]`$.

###### Corollary 2.14.

The subalgebra $`[G^{u,v}]`$ of the field of rational functions $`(G^{u,v})`$ is the intersection of $`n+1`$ Laurent polynomial rings:

(2.17)
$$[G^{u,v}]=[F_𝐢^{\pm 1}]\underset{k\mathrm{𝐞𝐱}}{}[F_{𝐢;k}^{\pm 1}],$$

where the collections $`F_{𝐢;k}`$ are given by (2.14).

As we will see in Section 4, Corollary 2.14 prepares the ground for the concept of an *upper cluster algebra*.

## 3. Ptolemy relations and triangulations

In this section, we present another important motivating example for the concept of cluster algebras: a family of classically studied commutative algebras $`𝒜_n`$ ($`n_{>0}`$). In the forthcoming classification of cluster algebras of finite type (see Section 5), $`𝒜_n`$ will turn out to be “of type $`A_n`$.”

We define the commutative algebra $`𝒜_n`$ explicitly by generators and relations. The algebra $`𝒜_n`$ has $`\left(\genfrac{}{}{0pt}{}{n+3}{2}\right)`$ generators $`x_a`$, where the index $`a`$ runs over all sides and diagonals of a regular $`(n+3)`$-gon $`𝐏_{n+3}`$. Each defining relation for $`𝒜_n`$ corresponds to a choice of a quadruple of vertices in $`𝐏_{n+3}`$. Let $`a`$, $`b`$, $`c`$, and $`d`$ be consecutive sides of the corresponding convex quadrilateral, and let $`e`$ and $`e^{}`$ be its diagonals; see Figure 1. We then write the relation

(3.1)
$$x_ex_e^{}=x_ax_c+x_bx_d.$$

Thus, our presentation of $`𝒜_n`$ involves $`\left(\genfrac{}{}{0pt}{}{n+3}{4}\right)`$ defining relations.

We refer to the relations (3.1) as *Ptolemy relations* because of the classical Ptolemy Theorem which asserts that in an inscribed quadrilateral, the sum of the products of the two pairs of opposite sides equals the product of the two diagonals. One can pass from Euclidean to hyperbolic geometry, where an analogue of (3.1) holds for the exponentiated hyperbolic distances between horocycles drawn around vertices of a polygon with geodesic sides and cusps at the vertices (the “Penner coordinates” on the corresponding *decorated Teichmüller space* ). This observation leads to one of many constructions of cluster algebras arising in the context of Teichmüller theory .

The algebra $`𝒜_n`$ has the following closely related models:

* the ring of polynomial $`SL_2`$-invariants of an $`(n+3)`$-tuple of points in $`^2`$;
* the homogeneous coordinate ring of the Grassmannian $`\mathrm{Gr}_{2,n+3}`$ of 2-dimensional subspaces in $`^{n+3}`$ with respect to its Plücker embedding;
* the ring $`[X_n]`$, where $`X_n`$ is the variety of all decomposable bivectors in $`^2^{n+3}`$.

The equivalence of the last two models is trivial. To see their equivalence to the first model, think of an $`(n+3)`$-tuple of points in $`^2`$ as the columns of a $`2\times (n+3)`$ matrix $`Z`$; the row space of $`Z`$ can then be viewed as a point of $`\mathrm{Gr}_{2,n+3}`$. The $`2\times 2`$ minors $`P_{ij}`$ of $`Z`$ are called *Plücker coordinates*; thus, a generic point of $`X_n`$ has the form

$$x=\underset{i<j}{}P_{ij}e_ie_j,$$

where $`e_1,\mathrm{},e_{n+3}`$ is the standard basis of $`^{n+3}`$. To identify $`𝒜_n`$ with $`[X_n]`$, label the vertices of $`𝐏_{n+3}`$ clockwise, and send the generator $`x_a`$ corresponding to a chord $`a=[i,j]`$ to the Plücker coordinate $`P_{ij}`$. The Ptolemy relations (3.1) then translate into the *Grassmann-Plücker relations*

(3.2)
$$P_{ik}P_{jl}=P_{ij}P_{kl}+P_{il}P_{jk},$$

for all $`1i<j<k<ln+3`$.

One can develop a theory of total positivity in $`X_n`$ that is completely parallel to the theory of total positivity in double Bruhat cells presented in Section 2. Let us call a point $`xX_n`$ *totally positive* if all its Plücker coordinates are positive real numbers. We then define *TP-bases* for $`X_n`$ as $`m`$-element subsets of $`𝒜_n=[X_n]`$ satisfying the conditions in Definition 2.5, with $`m=dim(X_n)=2n+3`$.

In what follows, a *triangulation* of the polygon $`𝐏_{n+3}`$ always means a triangulation by non-crossing diagonals. A nice family of TP-bases for $`X_n`$ can be constructed as follows (cf. Theorem 2.6).

###### Theorem 3.1 ().

Every triangulation $`T`$ of $`𝐏_{n+3}`$ gives rise to a TP-basis $`\stackrel{~}{𝐱}(T)`$ for $`X_n`$ which consists of the $`2n+3`$ generators $`x_a`$ corresponding to the sides and diagonals of $`T`$.

###### Remark 3.2.

The collections $`\stackrel{~}{𝐱}(T)`$ have already appeared in classical $`19^{\mathrm{th}}`$ century literature on invariant theory; for invariant-theoretic connections and applications, see . In particular, it is known  that the monomials in the generators $`x_a`$ which do not involve diagonals crossing each other form a linear basis in $`𝒜_n`$. We shall later discuss a far-reaching generalization of this result in the context of cluster algebras.

The combinatorics of the family of TP-bases described in Theorem 3.1 is encoded by the *exchange graph* whose vertices are all the triangulations of $`𝐏_{n+3}`$, and whose edges correspond to the diagonal *flips*. Each flip removes a diagonal to create a quadrilateral, then replaces it with another diagonal of the same quadrilateral. See Figure 2.

Since every triangulation of $`𝐏_{n+3}`$ involves $`n`$ diagonals, the exchange graph is $`n`$-regular, i.e., every vertex has degree $`n`$. The exchange graph is also connected: it is well known that any two triangulations of $`𝐏_{n+3}`$ are related by a sequence of flips. This exchange graph is the $`1`$-skeleton of an $`n`$-dimensional *associahedron*, or Stasheff’s polytope . See Figure 3. A generalization of this construction, to be presented in Section 5.2, will identify exchange graphs of cluster algebras of “finite type” with the $`1`$-skeleta of *generalized associahedra*, a family of convex polytopes associated with finite root systems.

For a given triangulation $`T`$, each of the $`n`$ TP-bases $`\stackrel{~}{𝐱}(T^{})`$ associated with the neighbors of $`T`$ in the exchange graph is obtained from $`\stackrel{~}{𝐱}(T)`$ by an exchange analogous to (2.14):

(3.3)
$$\stackrel{~}{𝐱}(T^{})=\stackrel{~}{𝐱}(T)\{x_e\}\{x_e^{}\},$$

whenever $`T^{}`$ is obtained from $`T`$ by the flip in Figure 2. Here the participating generators $`x_e`$ and $`x_e^{}`$ satisfy the Ptolemy relation (3.1).

We now make the following crucial observation: the $`n`$ Ptolemy relations that relate $`\stackrel{~}{𝐱}(T)`$ to its neighbors can be written in the same form as the exchange relations (2.13) from Section 2; that is, they can be encoded by an $`m\times n`$ integer matrix $`\stackrel{~}{B}=\stackrel{~}{B}(T)`$ (as above, $`m=2n+3`$). To be more precise, let $`a_1,\mathrm{},a_m`$ denote the sides and diagonals making up the triangulation $`T`$. (We thus fix a labeling of these segments by the numbers $`1,\mathrm{},m`$.) Let $`\mathrm{𝐞𝐱}=\mathrm{𝐞𝐱}_T[1,m]`$ be the $`n`$-element subset of indices which label the diagonals of $`T`$; as above, we refer to the elements of $`\mathrm{𝐞𝐱}`$ as *exchangeable* indices. Now let $`\stackrel{~}{B}=\stackrel{~}{B}(T)=(b_{ij})`$ be the $`m\times n`$ integer matrix with rows labeled by $`[1,m]`$, columns labeled by $`\mathrm{𝐞𝐱}`$, and matrix entries given by

(3.4)
$$b_{ij}=\{\begin{array}{cc}1\hfill & \text{if }a_i\text{ and }a_j\text{ are sides in some triangle of }T\text{,}\hfill \\ & \text{ with }a_j\text{ following }a_i\text{ in the clockwise order;}\hfill \\ 1\hfill & \text{if the same holds, with the counter-clockwise order;}\hfill \\ 0\hfill & \text{otherwise.}\hfill \end{array}$$

An example is shown in Figure 4.

We abbreviate $`x_k=x_{a_k}`$. An easy inspection shows that the Ptolemy relation (3.1) between $`x_k=x_e`$ and $`x_k^{}=x_e^{}`$ can indeed be written in the form completely analogous to (2.13):

(3.5)
$$x_k^{}=\frac{\underset{b_{ik}>0}{}x_i^{b_{ik}}+\underset{b_{ik}<0}{}x_i^{b_{ik}}}{x_k}.$$

We see that the algebraic relationships of the TP-basis $`\stackrel{~}{𝐱}(T)`$ with its neighbors in the exchange graph are very similar to the ones involving the TP-basis $`F_𝐢`$ in Section 2.2. There is however an important difference. In the case of $`𝒜_n`$, the family of TP-bases associated with all triangulations of $`𝐏_{n+3}`$ is closed under the exchanges, whereas in the case of double Bruhat cells, this is not the case (see Example 2.13). This raises the following question, whose answer constituted the decisive step towards introducing cluster algebras: is there a mechanism for extending the exchanges from an “initial” TP-basis $`F_𝐢`$ to all its $`n`$ neighbors $`F_{𝐢;k}`$, then to the $`n`$ neighbors of $`F_{𝐢;k}`$, etc.? More concretely, is there a natural general rule that determines the matrix $`\stackrel{~}{B}^{}`$ associated with a neighboring TP-basis from the matrix $`\stackrel{~}{B}`$ associated with a given TP-basis? Such a rule would enable us to recursively “propagate” away from the initial TP-basis, each time constructing a new basis using the exchange relations involving the entries of the current matrix $`\stackrel{~}{B}`$, then re-calculating $`\stackrel{~}{B}`$ according to the stated rule.

The case of triangulations provides a crucial hint for the solution: it turns out that the matrix $`\stackrel{~}{B}(T^{})`$ can be recovered from $`\stackrel{~}{B}(T)`$ by a purely algebraic procedure which we call *matrix mutation*333Our historic account becomes a bit revisionist at this point: in fact, we discovered matrix mutations *before* considering the algebras $`𝒜_n`$..

###### Definition 3.3 (\[21, Definition 4.2\]).

We say that an $`m\times n`$ integer matrix $`\stackrel{~}{B}^{}`$ is obtained from $`\stackrel{~}{B}`$ by *matrix mutation* in direction $`k\mathrm{𝐞𝐱}`$, and write $`\stackrel{~}{B}^{}=\mu _k(\stackrel{~}{B})`$ if the entries of $`\stackrel{~}{B}^{}`$ are given by

(3.6)
$$b_{ij}^{}=\{\begin{array}{cc}b_{ij}\hfill & \text{if }i=k\text{ or }j=k\text{;}\hfill \\ b_{ij}+\frac{|b_{ik}|b_{kj}+b_{ik}|b_{kj}|}{2}\hfill & \text{otherwise.}\hfill \end{array}$$

The following proposition can be verified by direct inspection.

###### Proposition 3.4.

Suppose that a triangulation $`T^{}`$ is obtained from $`T`$ by a flip replacing a diagonal $`a_k`$ by a diagonal $`a_k^{}`$. (The labeling of all other diagonals and sides remains unchanged.) Then $`\stackrel{~}{B}(T^{})=\mu _k(\stackrel{~}{B}(T))`$.

## 4. Cluster algebra fundamentals

Motivated by the above considerations, we are now ready to develop the axiomatic foundations of the cluster algebra theory.

### 4.1. Upper cluster algebras

We start by introducing *upper cluster algebras* (of geometric type), which first appeared in .

Let $`m`$ and $`n`$ be two positive integers such that $`mn`$. Let $``$ be the field of rational functions over $``$ in $`m`$ independent (commuting) variables. Once and for all, we fix an $`n`$-element subset $`\mathrm{𝐞𝐱}[1,m]`$.

###### Definition 4.1.

A *seed* (of geometric type) in $``$ is a pair $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$, where

* $`\stackrel{~}{𝐱}=\{x_1,\mathrm{},x_m\}`$ is an algebraically independent subset of $``$ which generates $``$;
* $`\stackrel{~}{B}=(b_{ij})`$ is an $`m\times n`$ integer matrix with rows labeled by $`[1,m]`$ and columns labeled by $`\mathrm{𝐞𝐱}`$, such that

+ the $`n\times n`$ submatrix $`B=(b_{i,j})_{i,j\mathrm{𝐞𝐱}}`$ is *skew-symmetrizable*: $`d_ib_{ik}=d_kb_{ki}`$ for some positive integers $`d_i(i,k\mathrm{𝐞𝐱})`$;
    + $`\stackrel{~}{B}`$ has full rank $`n`$.

The seeds are defined up to a relabeling of elements of $`\stackrel{~}{𝐱}`$ together with the corresponding relabeling of rows and columns of $`\stackrel{~}{B}`$.

###### Example 4.2.

In the notation of Section 2, let $`𝐢`$ be a reduced word for $`(u,v)W\times W`$. As shown in \[3, Proposition 2.6\], the matrix $`\stackrel{~}{B}=\stackrel{~}{B}(𝐢)`$ given by (2.15) satisfies the conditions in Definition 4.1. Thus, $`(F_𝐢,\stackrel{~}{B}(𝐢))`$ is a seed inside the field of rational functions $`=(G^{u,v})`$.

###### Example 4.3.

In the notation of Section 3, let $`T`$ be a triangulation of the regular $`(n+3)`$-gon $`𝐏_{n+3}`$. One can show that the matrix $`\stackrel{~}{B}=\stackrel{~}{B}(T)`$ defined by (3.4) satisfies the conditions in Definition 4.1. Thus, $`(\stackrel{~}{𝐱}(T),\stackrel{~}{B}(T))`$ is a seed inside $``$, the field of fractions of the algebra $`𝒜_n`$.

Let $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ be a seed in a field $``$. By analogy with (2.13) and (3.5), for every $`k\mathrm{𝐞𝐱}`$, we set

(4.1)
$$x_k^{}=\frac{\underset{b_{ik}>0}{}x_i^{b_{ik}}+\underset{b_{ik}<0}{}x_i^{b_{ik}}}{x_k}$$

and

(4.2)
$$\stackrel{~}{𝐱}_k=\stackrel{~}{𝐱}\{x_k\}\{x_k^{}\}.$$

It is easy to check that $`\stackrel{~}{𝐱}_k`$ is again a set of algebraically independent generators for $``$.

###### Definition 4.4.

The *upper cluster algebra* $`𝒰(\stackrel{~}{𝐱},\stackrel{~}{B})=𝒰(\stackrel{~}{B})`$ is the subring of the ambient field $``$ given by

(4.3)
$$𝒰(\stackrel{~}{𝐱},\stackrel{~}{B})=𝒰(\stackrel{~}{B})=[\stackrel{~}{𝐱}^{\pm 1}]\underset{k\mathrm{𝐞𝐱}}{}[\stackrel{~}{𝐱}_k^{\pm 1}],$$

where $`[\stackrel{~}{𝐱}^{\pm 1}]`$ (resp., $`[\stackrel{~}{𝐱}_k^{\pm 1}]`$) stands for the ring of Laurent polynomials with integer coefficients in the variables from $`\stackrel{~}{𝐱}`$ (resp., $`\stackrel{~}{𝐱}_k`$).

In this terminology, Corollary 2.14 takes the following form (cf. \[3, Theorem 2.10\]):

###### Corollary 4.5.

The coordinate ring $`[G^{u,v}]`$ of any double Bruhat cell is naturally isomorphic to the complexification of the upper cluster algebra $`𝒰(\stackrel{~}{B}(𝐢))`$ associated with the matrix $`\stackrel{~}{B}(𝐢)`$ determined by an arbitrary reduced word $`𝐢`$ for $`(u,v)`$.

To make the abstract notion of an upper cluster algebra useful, we need to develop a better understanding of the structure of these algebras. This does not seem to be an easy task. In particular, it is not at all clear how big the intersection of Laurent polynomial rings in (4.3) can be. The following problem raised in \[3, Problem 1.27\] is still open:

###### Problem 4.6.

For which matrices $`\stackrel{~}{B}`$ is the upper cluster algebra $`𝒰(\stackrel{~}{B})`$ finitely generated?

### 4.2. Seed mutations and cluster algebras

Prompted by Proposition 3.4, we will now introduce the machinery of seed mutations, which will provide the means to generate a lot of—sometimes infinitely many—new elements in $`𝒰(\stackrel{~}{x},\stackrel{~}{B})`$ from the initial seed $`(\stackrel{~}{x},\stackrel{~}{B})`$. This will in particular lead to partial answers to Problem 4.6 (see Theorem 4.13).

We retain the terminology and notation in Definition 4.1. In addition, we denote $`𝐱=\{x_j:j\mathrm{𝐞𝐱}\}\stackrel{~}{𝐱}`$ and $`𝐜=\stackrel{~}{𝐱}𝐱`$ (cf. (2.12)). We refer to the elements of $`\mathrm{𝐞𝐱}`$ as *exchangeable* indices, and to $`𝐱`$ as a *cluster*. The $`n\times n`$ submatrix $`B`$ of $`\stackrel{~}{B}`$ with rows and columns labeled by $`\mathrm{𝐞𝐱}`$ is called the *principal part* of $`\stackrel{~}{B}`$. We also call $`B`$ the *exchange matrix* of the seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$.

Recall the notion of matrix mutation introduced in Definition 3.3. We note that if the principal part of $`\stackrel{~}{B}`$ is $`B`$, then the principal part of $`\mu _k(\stackrel{~}{B})`$ is $`\mu _k(B)`$. One can show (see, e.g., \[5, Proposition 2.3\]) that matrix mutations preserve the restrictions imposed on $`\stackrel{~}{B}`$ in Definition 4.1. Consequently, the following notion is well defined.

###### Definition 4.7.

Let $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ be a seed in $``$. For any exchangeable index $`k`$, the *seed mutation* in direction $`k`$ transforms $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ into the seed $`\mu _k(\stackrel{~}{𝐱},\stackrel{~}{B})=(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$, where $`\stackrel{~}{𝐱}^{}=\stackrel{~}{𝐱}_k`$ is given by (4.1)–(4.2), and $`\stackrel{~}{B}^{}=\mu _k(\stackrel{~}{B})`$.

It is trivial to check that matrix mutations are involutive, as are seed mutations: in the situation of Definition 4.7 we have $`\mu _k(\stackrel{~}{B}^{})=\stackrel{~}{B}`$ and $`\mu _k(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})=(\stackrel{~}{𝐱},\stackrel{~}{B})`$. Therefore, we can define an equivalence relation on seeds as follows: we say that two seeds $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ and $`(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$ are mutation-equivalent, and write $`(\stackrel{~}{𝐱},\stackrel{~}{B})(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$, if $`(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$ can be obtained from $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ by a sequence of seed mutations. All seeds $`(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$ mutation-equivalent to a given seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ share the same set $`𝐜=\stackrel{~}{𝐱}𝐱`$.

###### Remark 4.8.

Recall that our motivating example of an upper cluster algebra is the coordinate ring $`[G^{u,v}]`$ of a double Bruhat cell, see Corollary 4.5. The mutation procedure makes it obvious that, for every seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ mutation-equivalent to $`(F_𝐢,\stackrel{~}{B}(𝐢))`$, the subset $`\stackrel{~}{𝐱}[G^{u,v}]`$ satisfies conditions (i) and (iii) in Definition 2.5, and therefore provides global coordinates in the totally positive variety $`G_{>0}^{u,v}`$.

Somewhat surprisingly, seed mutations leave the associated upper cluster algebra invariant:

###### Theorem 4.9 (\[3, Theorem 1.5\]).

If $`(\stackrel{~}{𝐱},\stackrel{~}{B})(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$, then $`𝒰(\stackrel{~}{𝐱},\stackrel{~}{B})=𝒰(\stackrel{~}{𝐱}^{},\stackrel{~}{B}^{})`$.

In view of Theorem 4.9, we can use the notation $`𝒰(𝒮)=𝒰(\stackrel{~}{𝐱},\stackrel{~}{B})`$, where $`𝒮`$ is the mutation-equivalence class of a seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$.

Now everything is in place for defining cluster algebras. For a mutation equivalence class of seeds $`𝒮`$, we denote by $`𝒳=𝒳(𝒮)`$ the union of clusters of all seeds in $`𝒮`$. In other words, $`𝒳`$ is the union of all elements of $``$ that appear in all seeds of $`𝒮`$, except that we do not include the elements of $`𝐜`$. We refer to the elements of $`𝒳`$ as *cluster variables*.

###### Definition 4.10.

Let $`𝒮`$ be a mutation equivalence class of seeds. The *cluster algebra* $`𝒜(𝒮)`$ associated with $`𝒮`$ is the $`[𝐜^{\pm 1}]`$-subalgebra444 An alternative definition uses $`[𝐜]`$ instead of $`[𝐜^{\pm 1}]`$ as a ground ring for $`𝒜(𝒮)`$; cf. Section 3. More generally, one can use any ground ring sandwiched between $`[𝐜]`$ and $`[𝐜^{\pm 1}]`$.  of the ambient field $``$ generated by all cluster variables:

$$𝒜(𝒮)\stackrel{\mathrm{def}}{=}[𝐜^{\pm 1},𝒳].$$

The cardinality $`n`$ of every cluster is called the *rank* of $`𝒜(𝒮)`$.

Since $`𝒮`$ is uniquely determined by an arbitrary seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})𝒮`$, we sometimes denote $`𝒜(𝒮)`$ as $`𝒜(\stackrel{~}{𝐱},\stackrel{~}{B})`$, or simply as $`𝒜(\stackrel{~}{B})`$, because $`\stackrel{~}{B}`$ determines this algebra uniquely up to an automorphism of $``$.

The following result first appeared in \[21, Theorem 3.1\]. A new proof based on Theorem 4.9 was given in .

###### Theorem 4.11 (Laurent phenomenon).

A cluster algebra $`𝒜(𝒮)`$ is contained in the corresponding upper cluster algebra $`𝒰(𝒮)`$. Equivalently, $`𝒜(𝒮)[\stackrel{~}{𝐱}^{\pm 1}]`$ for every seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ in $`𝒮`$. That is, every element of $`𝒜(𝒮)`$ is an integer Laurent polynomial in the variables from $`\stackrel{~}{𝐱}`$.

It is worth mentioning that Theorems 4.9 and 4.11 carry over to the quantum setting developed in .

We next present some open problems and conjectures on cluster algebras. The following question was raised in \[3, Problem 1.25\].

###### Problem 4.12.

When does a cluster algebra $`𝒜(𝒮)`$ coincide with the corresponding upper cluster algebra $`𝒰(𝒮)`$?

A sufficient condition for the equality $`𝒜(𝒮)=𝒰(𝒮)`$ was found in . Following , let us call a seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ *acyclic* if there is a linear ordering of $`\mathrm{𝐞𝐱}`$ such that $`b_{ij}0`$ for all $`i,j\mathrm{𝐞𝐱}`$ with $`i<j`$. (Since the principal part of $`\stackrel{~}{B}`$ is skew-symmetrizable, we also have $`b_{ji}0`$.)

###### Theorem 4.13 (\[3, Theorem 1.18, Corollary 1.19\]).

If $`𝒮`$ contains an acyclic seed, then $`𝒜(𝒮)=𝒰(𝒮)`$. Moreover, if $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ is an acyclic seed, then

$$𝒜(\stackrel{~}{𝐱},\stackrel{~}{B})=𝒰(\stackrel{~}{𝐱},\stackrel{~}{B})=[𝐜^{\pm 1},x_k,x_k^{}(k\mathrm{𝐞𝐱})],$$

where the $`x_k^{}`$ is given by (4.1). In particular, this algebra is finitely generated.

An important combinatorial invariant of a cluster algebra $`𝒜(𝒮)`$ is its *exchange graph*. The vertices of this graph correspond to the seeds in $`𝒮`$, and the edges correspond to seed mutations. By definition, the exchange graph is connected and $`n`$-regular; that is, every vertex has degree $`n`$. Besides these properties, not much is known about exchange graphs in general. Here are a few conjectures (some of them already appeared in ).

###### Conjecture 4.14.

1. The exchange graph of an algebra $`𝒜(\stackrel{~}{𝐱},\stackrel{~}{B})`$ depends only on the principal part $`B`$ of the matrix $`\stackrel{~}{B}`$.
2. Every seed in $`𝒮`$ is uniquely determined by its cluster; thus, the vertices of the exchange graph can be identified with the clusters, with two clusters adjacent if and only if their intersection has cardinality $`n1`$.
3. For any cluster variable $`x`$, the seeds from $`𝒮`$ whose clusters contain $`x`$ form a connected subgraph of the exchange graph.
4. The seeds from $`𝒮`$ whose exchange matrix $`B`$ is acyclic form a connected subgraph (possibly empty) of the exchange graph.

### 4.3. Cluster monomials and positive cones

###### Definition 4.15.

A *cluster monomial* in a cluster algebra $`𝒜(𝒮)`$ is a monomial in cluster variables all of which belong to the same cluster.

Inspired by Remark 3.2, we propose the following conjecture.

###### Conjecture 4.16.

The cluster monomials are linearly independent over $`[𝐜^{\pm 1}]`$.

As labels for cluster monomials, we would like to use the denominators in the Laurent expansion with respect to a given cluster. To be more specific, let us fix a cluster $`𝐱`$ from some seed in $`𝒮`$, and choose a numbering of its elements: $`𝐱=\{x_1,\mathrm{},x_n\}`$. Every nonzero element $`y𝒰(𝒮)`$ can be uniquely written as

(4.4)
$$y=\frac{P(x_1,\mathrm{},x_n)}{x_1^{d_1}\mathrm{}x_n^{d_n}},$$

where $`P(x_1,\mathrm{},x_n)`$ is a polynomial with coefficients in $`[𝐜^{\pm 1}]`$ which is not divisible by any cluster variable $`x_i𝐱`$. We denote

(4.5)
$$\delta (y)=\delta _𝐱(y)=(d_1,\mathrm{},d_n)^n,$$

and call the integer vector $`\delta (y)`$ the *denominator vector* of $`y`$ with respect to the cluster $`𝐱`$. (One could also call $`\delta (y)`$ the *tropicalization* of $`y`$ with respect to $`𝐱`$.) For instance, the elements of $`𝐱`$ and their immediate exchange partners have denominator vectors

(4.6)
$$\delta (x_j)=e_j,\delta (x_j^{})=e_j(j[1,n]),$$

where $`e_1,\mathrm{},e_n`$ are the standard basis vectors in $`^n`$. Note also that the map $`y\delta (y)`$ has the following valuation property:

(4.7)
$$\delta (yz)=\delta (y)+\delta (z).$$

###### Conjecture 4.17.

Different cluster monomials have different denominator vectors with respect to a given cluster.

Our last group of questions/conjectures concerns *positivity* in cluster algebras. We define the *positive cones* $`𝒰(𝒮)_0`$ and $`𝒜(𝒮)_0`$ by setting

$`𝒰(𝒮)_0`$ $`={\displaystyle \underset{(\stackrel{~}{𝐱},\stackrel{~}{B})𝒮}{}}_0[\stackrel{~}{𝐱}^{\pm 1}],`$
$`𝒜(𝒮)_0`$ $`=𝒜(𝒮)𝒰(𝒮)_0.`$
That is, $`𝒰(𝒮)_0`$ (resp., $`𝒜(𝒮)_0`$) consists of all elements in $`𝒰(𝒮)`$ (resp., in $`𝒜(𝒮)`$) whose Laurent expansion in terms of the variables from any seed in $`𝒮`$ has nonnegative coefficients. A nonzero element of a positive cone will be referred to as *positive*.

It would be very interesting to find concrete descriptions of the positive cones $`𝒰(𝒮)_0`$ and $`𝒜(𝒮)_0`$. To be more specific: let us call a positive element (in either of the positive cones) *indecomposable* if it cannot be written as a sum of two positive elements.

###### Problem 4.18.

Describe the set of all indecomposable elements in either of the cones $`𝒰(𝒮)_0`$ and $`𝒜(𝒮)_0`$.

###### Conjecture 4.19.

1.  Every cluster variable $`x𝒳`$ is a positive element of the cluster algebra $`𝒜(𝒮)`$. That is, for every seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ in $`𝒮`$, the Laurent expansion of $`x`$ in terms of the variables from $`\stackrel{~}{𝐱}`$ has nonnegative coefficients.
2. Every cluster monomial is an indecomposable positive element.

### 4.4. Example: cluster algebras of rank 2

Let us illustrate the above definitions, results and conjectures by the following example. Let $`m=n=2`$, and let the ambient field $``$ be the field of rational functions $`(y_1,y_2)`$ in two independent variables $`y_1`$ and $`y_2`$. For every pair of positive integers $`(b,c)`$, let $`𝒜(b,c)`$ be the cluster algebra associated with the initial seed $`(\{y_1,y_2\},B)`$, where $`B=\stackrel{~}{B}`$ is the $`2\times 2`$ matrix given by

$$B=\stackrel{~}{B}=[\begin{array}{cc}0& b\\ c& 0\end{array}].$$

The definitions readily imply that the cluster variables in $`𝒜(b,c)`$ are the elements $`y_t`$, for $`t`$, defined recursively by

$$y_{t1}y_{t+1}=\{\begin{array}{cc}y_t^b+1\hfill & \mathrm{if}t\mathrm{is}\mathrm{odd};\hfill \\ y_t^c+1\hfill & \mathrm{if}t\mathrm{is}\mathrm{even}.\hfill \end{array}$$

Thus, $`𝒜(b,c)`$ is simply the subring of $`=(y_1,y_2)`$ generated by all the elements $`y_t`$. The clusters are of the form $`\{y_t,y_{t+1}\}`$, $`t`$. The Laurent phenomenon asserts that $`y_t[y_1^{\pm 1},y_2^{\pm 1}]`$ for all $`t`$. In view of Theorem 4.13, we have a sharper statement:

$$𝒜(b,c)=\underset{t=0}{\overset{2}{}}[y_t^{\pm 1},y_{t+1}^{\pm 1}]=\underset{t}{}[y_t^{\pm 1},y_{t+1}^{\pm 1}]=[y_0,y_1,y_2,y_3].$$

###### Theorem 4.20.

 The sequence $`(y_t)_t`$ of the cluster variables in $`𝒜(b,c)`$ is periodic if and only if $`bc3`$. For $`bc=1`$ (resp., $`2`$, $`3`$), the sequence $`(y_t)_t`$ has period $`5`$ (resp., $`6`$$`8`$).

Conjectures 4.14, 4.16 and 4.17 are known to hold for any $`𝒜(b,c)`$. (The first one follows from the results in , while the last two were proved in .) Conjecture 4.19 is still open even in rank $`2`$; it was proved in  for the special case $`bc4`$. Furthermore, it was shown in  that for $`bc4`$, the indecomposable positive elements form a $``$-basis of the cluster algebra. This raises the following general question.

###### Problem 4.21.

For which matrices $`\stackrel{~}{B}`$ do the indecomposable positive elements form a $``$-basis of the corresponding cluster algebra?

### 4.5. Cluster algebras of finite type

All the problems and conjectures stated above become much more tractable for the cluster algebras of finite type, defined as follows.

###### Definition 4.22.

A cluster algebra $`𝒜(𝒮)`$ is of *finite type* if the mutation equivalence class $`𝒮`$ consists of finitely many seeds.

To rephrase, a cluster algebra is of finite type if its exchange graph is finite. In particular, Theorem 4.20 shows that a rank $`2`$ cluster algebra $`𝒜(b,c)`$ is of finite type if and only if $`bc3`$.

###### Theorem 4.23 ().

Every cluster algebra of finite type contains an acyclic seed, and therefore satisfies the conclusions in Theorem 4.13.

###### Theorem 4.24 ().

Parts (1)-(3) of Conjecture 4.14 hold for any cluster algebra $`𝒜`$ of finite type. In particular, each seed in $`𝒜`$ is uniquely determined by its cluster.

###### Theorem 4.25 ().

Conjecture 4.16 holds for any cluster algebra $`𝒜`$ of finite type.

The proofs of Theorems 4.234.25 are based on the classification of cluster algebras of finite type given in . Remarkably, this classification (to be discussed in Section 5) turns out to be identical to the famous Cartan-Killing classification of semisimple Lie algebras and finite root systems. In the cases where a cluster algebra is of classical Cartan-Killing type, stronger results can be obtained.

###### Theorem 4.26 ().

Conjectures 4.14, 4.16, 4.17 and 4.19 hold for any cluster algebra of classical type.

In fact, Theorem 4.26 can be sharpened as follows.

###### Theorem 4.27 ().

For any cluster algebra $`𝒜`$ of classical type, the cluster monomials form a $`[𝐜^{\pm 1}]`$-linear basis of $`𝒜`$ and a $`_0[𝐜^{\pm 1}]`$-linear basis of the positive cone $`𝒜_0`$.

###### Conjecture 4.28.

Each of the two properties in Theorem 4.27 characterizes cluster algebras of finite type; that is, it holds for a cluster algebra $`𝒜`$ if and only if $`𝒜`$ is of finite type.

## 5. Finite type classification and cluster combinatorics

### 5.1. Finite type classification

We now present a classification of cluster algebras of finite type given in . First, a few preliminaries.

Let $`A=(a_{ij})`$ be an $`n\times n`$ Cartan matrix of finite type. The associated Dynkin diagram is a tree, hence a bipartite graph. Thus, there is a sign function $`\epsilon :[1,n]\{1,1\}`$ such that $`a_{ij}<0\epsilon (i)=\epsilon (j)`$. See Figure 5.

We define a skew-symmetrizable matrix $`B(A)=(b_{ij})`$ by

(5.1)
$$b_{ij}=\{\begin{array}{cc}0\hfill & \text{if }i=j\text{;}\hfill \\ \epsilon (i)a_{ij}\hfill & \text{if }ij\text{.}\hfill \end{array}$$

###### Theorem 5.1 ().

A cluster algebra $`𝒜`$ is of finite type if and only if the exchange matrix at some seed of $`𝒜`$ is of the form $`B(A)`$, where $`A`$ is a Cartan matrix of finite type. Furthermore, the type of $`A`$ in the Cartan-Killing nomenclature is uniquely determined by the cluster algebra $`𝒜`$. (It is called the “cluster type” of $`𝒜`$.)

###### Example 5.2.

In rank $`2`$, the cluster algebras of finite type were classified in Theorem 4.20. The values of $`bc`$ equal to $`1`$, $`2`$, and $`3`$ correspond to the cluster types $`A_2`$, $`B_2`$, and $`G_2`$, respectively.

###### Example 5.3.

The cluster algebra $`𝒜_n`$ discussed in Section 3 has cluster type $`A_n`$. To see this, consider a “snake” triangulation $`T`$ of the regular $`(n+3)`$-gon $`𝐏_{n+3}`$ (Figure 4 illustrates the case $`n=3`$) and note that the principal part of the corresponding matrix $`\stackrel{~}{B}(T)`$ given by (3.4) is of the form (5.1), where $`A`$ is the Cartan matrix of type $`A_n`$.

###### Remark 5.4.

It is a non-trivial problem to decide, given a matrix $`B`$, whether the corresponding cluster algebra is of finite type. This problem was solved by A. Seven in . An alternative criterion has been recently given in .

###### Remark 5.5.

It would be interesting to classify the double Bruhat cells such that the corresponding cluster algebra is of finite type. Some examples of this kind were given in . For instance, as shown in \[3, Example 2.18\], the cluster algebra structure in $`[SL_3^{w_{},w_{}}]`$ (see Examples 2.8 and 2.13 above) is of cluster type $`D_4`$. More details are given in Example 5.20 below.

Over the last several years, cluster algebra structures have been uncovered in (homogeneous) coordinate rings of various classical algebraic varieties. Some of these cluster algebras have finite type; see Figure 6.

In most cases, the symmetry exhibited by the cluster type of a cluster algebra is not apparent at all from its geometric realization. An instance of this phenomenon was demonstrated by J. Scott , who introduced a natural cluster algebra structure in the homogeneous coordinate ring of the Grassmannian $`\mathrm{Gr}_{k,n}`$ of $`k`$-dimensional subspaces of $`^n`$ with respect to its Plücker embedding. (Cf. also .) Among these cluster algebras, all which are of finite type are listed in Figure 6.

### 5.2. Cluster combinatorics and generalized associahedra

Let $`𝒜`$ be a cluster algebra of finite type. In view of Theorem 4.24, the combinatorics of exchanges and mutations in $`𝒜`$ is encoded by the *cluster complex* $`\mathrm{\Delta }(𝒜)`$, a simplicial complex (indeed, a pseudomanifold) on the set of all cluster variables whose maximal simplices are the clusters.

For example, the simplices of the cluster complex $`\mathrm{\Delta }(𝒜_n)`$ associated with the cluster algebra $`𝒜_n`$ of Section 3 are naturally identified with collections of non-crossing diagonals of the regular $`(n+3)`$-gon $`𝐏_{n+3}`$. In what follows, we extend this description to all cluster algebras of finite type.

According to Theorem 5.1, $`𝒜`$ has a seed $`(\stackrel{~}{𝐱},\stackrel{~}{B})`$ with the exchange matrix $`B=B(A)`$ given by (5.1), where $`A=(a_{ij})`$ is a Cartan matrix of finite type (see (2.16)). We refer to such a seed as a *distinguished* seed of $`𝒜`$.

###### Theorem 5.6 ().

Conjectures 4.17 and 4.19(1) hold for a distinguished seed in $`𝒜`$.

The proof of Conjecture 4.17 (for a distinguished seed) given in \[23, Theorem 1.9\] establishes a direct connection between a cluster algebra of finite type and the corresponding root system. Let $`\mathrm{\Phi }`$ be a root system with the Cartan matrix $`A`$, and $`Q`$ the root lattice generated by $`\mathrm{\Phi }`$. We identify $`Q`$ with $`^n`$ using the basis $`\mathrm{\Pi }=\{\alpha _1,\mathrm{},\alpha _n\}`$ of simple roots in $`\mathrm{\Phi }`$. Let $`\mathrm{\Phi }_{>0}`$ be the set of positive roots associated to $`\mathrm{\Pi }`$. In this notation, \[23, Theorem 1.9\] combined with \[24, Theorem 1.8\] can be stated as follows.

###### Theorem 5.7.

The denominator vector parametrization (see (4.4)–(4.5)) with respect to a distinguished cluster $`𝐱`$ provides a bijection between the set of cluster variables $`𝒳`$ and the set

$$\mathrm{\Phi }_1=\mathrm{\Phi }_{>0}(\mathrm{\Pi })$$

of “almost positive roots.” This parametrization also gives a bijection between the set of all cluster monomials and the root lattice $`Q=^n`$.

We next restate Theorem 5.7 in more concrete terms. Let $`x_1,\mathrm{},x_n`$ be the elements of a distinguished cluster $`𝐱`$ which correspond to the simple roots $`\alpha _1,\mathrm{},\alpha _n`$, respectively.

###### Theorem 5.8 ().

For any root $`\alpha =c_1\alpha _1+\mathrm{}+c_n\alpha _n\mathrm{\Phi }_1`$, there is a unique cluster variable $`x[\alpha ]`$ such that

$$x[\alpha ]=\frac{P_\textcolor[rgb]{0,0,0}{\alpha }(x_1,\mathrm{},x_n)}{x_1^{c_1}\mathrm{}x_n^{c_n}},$$

where $`P_\textcolor[rgb]{0,0,0}{\alpha }`$ is a polynomial in $`x_1,\mathrm{},x_n`$ with nonzero constant term; furthermore, any cluster variable is of this form.

In view of Theorems 5.7 and 5.8, the vertices of the cluster complex $`\mathrm{\Delta }(𝒜)`$ (which we will also denote by $`\mathrm{\Delta }(\mathrm{\Phi })`$) can be identified with the almost positive roots in $`\mathrm{\Phi }`$. Our goal is to describe the simplices of $`\mathrm{\Delta }(\mathrm{\Phi })`$ explicitly in root-theoretic terms.

###### Theorem 5.9 ().

The $`n`$ roots that label the cluster variables in an arbitrary cluster form a $``$-basis of the root lattice $`Q`$. The cones spanned by all such $`n`$-tuples of roots form a complete simplicial fan in the ambient real vector space $`Q_{}`$.

Thus, the simplices of the cluster complex can be represented by the cones of the simplicial fan in Theorem 5.9. With some abuse of terminology, we denote this fan by the same symbol $`\mathrm{\Delta }(\mathrm{\Phi })`$.

Figure 7 shows the fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ for the special case of type $`A_2`$. This fan has $`5`$ maximal cones, spanned by the pairs

$`\{\alpha _1,\alpha _2\},\{\alpha _2,\alpha _1+\alpha _2\},\{\alpha _1+\alpha _2,\alpha _1\},\{\alpha _1,\alpha _2\},\{\alpha _2,\alpha _1\}`$
$`\mathrm{\Phi }_1=\{\alpha _1,\alpha _2,\alpha _1,\alpha _2,\alpha _1+\alpha _2\}.`$
The simplicial fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ in Theorem 5.8 is polytopal.

###### Theorem 5.10 ().

The fan $`\mathrm{\Delta }(\mathrm{\Phi })`$ is the normal fan of a simple $`n`$-dimensional convex polytope, which is denoted by $`P(\mathrm{\Phi })`$ and called the generalized associahedron of type $`\mathrm{\Phi }`$.

Thus, the exchange graph of a cluster algebra of finite type can be realized as the $`1`$-skeleton of the generalized associahedron.

Turning to an explicit description of the cluster complex in root-theoretic terms, we start with the following result from .

###### Theorem 5.11.

The cluster complex is a clique complex for its $`1`$-skeleton. In other words, a subset $`S\mathrm{\Phi }_1`$ is a simplex in the cluster complex if and only if every $`2`$-element subset of $`S`$ is a $`1`$-simplex.

In order to describe the cluster complex, we therefore need only to clarify which *pairs* of almost positive roots label the edges of the cluster complex. Without loss of generality, we assume that the root system $`\mathrm{\Phi }`$ is irreducible; the general case can be obtained by taking direct products. Let $`W`$ be the Weyl group of $`\mathrm{\Phi }`$; it is a Coxeter group generated by the simple reflections $`s_1,\mathrm{},s_n`$ which correspond to the simple roots $`\alpha _1,\mathrm{},\alpha _n`$. Let $`w_{}`$ be the element of maximal length in $`W`$, and $`h`$ the Coxeter number. We also recall that $`i\epsilon (i)`$ is the sign function as in Figure 5.

###### Definition 5.12.

Define involutions $`\tau _\pm :\mathrm{\Phi }_1\mathrm{\Phi }_1`$ by

$$\tau _\textcolor[rgb]{0,0,0}{\epsilon }(\alpha )=\{\begin{array}{cc}\alpha \hfill & \text{if }\alpha =\alpha _i\text{, with }\epsilon (i)=\epsilon \text{;}\hfill \\ \left(\underset{\textcolor[rgb]{0,0,0}{\epsilon }(i)=\textcolor[rgb]{0,0,0}{\epsilon }}{}s_i\right)(\alpha )\hfill & \text{otherwise.}\hfill \end{array}$$

For example, in type $`A_2`$ with $`\epsilon (1)=+1`$ and $`\epsilon (2)=1`$, we get:

$$\begin{array}{ccc}\alpha _1& \stackrel{\tau _+}{}\alpha _1\stackrel{\tau _{}}{}\alpha _1+\alpha _2\stackrel{\tau _+}{}\alpha _2\stackrel{\tau _{}}{}& \alpha _2\\ & & \\ \tau _{}& & \tau _+\end{array}$$

###### Theorem 5.13 ().

The order of $`\tau _{}\tau _+`$ is $`(h+2)/2`$ if $`w_{}=1`$, and is $`h+2`$ otherwise. Every $`\tau _{},\tau _+`$-orbit in $`\mathrm{\Phi }_1`$ has a nonempty intersection with $`\mathrm{\Pi }`$. These intersections are precisely the $`w_{}`$-orbits in $`(\mathrm{\Pi })`$.

###### Theorem 5.14 ().

There is a unique binary relation (called “compatibility”) on $`\mathrm{\Phi }_1`$ that has the following two properties:

* $`\tau _{},\tau _+`$-invariance: if $`\alpha `$ and $`\beta `$ are compatible, then so are $`\tau _\textcolor[rgb]{0,0,0}{\epsilon }\alpha `$ and $`\tau _\textcolor[rgb]{0,0,0}{\epsilon }\beta `$ for $`\epsilon \{+,\}`$;
* a negative simple root $`\alpha _i`$ is compatible with a root $`\beta `$ if and only if the simple root expansion of $`\beta `$ does not involve $`\alpha _i`$.

This compatibility relation is symmetric. The clique complex for the compatibility relation is canonically isomorphic to the cluster complex.

In other words (cf. Theorem 5.11), a subset of $`\mathrm{\Phi }_1`$ forms a simplex in the cluster complex if and only if every pair of roots in this subset is compatible.

The above machinery allows us to explicitly describe a generalized associahedron $`P(\mathrm{\Phi })`$ by a set of linear inequalities.

###### Theorem 5.15 ().

Suppose that a $`(w_{})`$-invariant function $`F:\mathrm{\Pi }`$ satisfies the inequalities

$$\underset{iI}{}a_{ij}F(\alpha _i)>0\text{for all }j[1,n]\text{.}$$

Let us extend $`F`$ (uniquely) to a $`\tau _{},\tau _+`$-invariant function on $`\mathrm{\Phi }_1`$. The generalized associahedron $`P(\mathrm{\Phi })`$ is then realized as the set of points $`z`$ in the dual space $`Q_{}^{}`$ satisfying the linear inequalities

$$z,\alpha F(\alpha ),\text{for all}\alpha \mathrm{\Phi }_1.$$

As an example of a function $`F`$ satisfying the conditions in Theorem 5.15, one can take the function whose value $`F(\alpha _i)`$ is equal to the coefficient of a simple coroot $`\alpha _i^{}`$ in the half-sum of all positive coroots.

###### Example 5.16.

In type $`A_3`$, Theorem 5.15 is illustrated in Figure 8, which shows a $`3`$-dimensional simple polytope given by the inequalities

$$\begin{array}{ccc}\hfill \mathrm{max}(z_1,z_3,z_1,z_3,z_1+z_2,z_2+z_3)& & 3/2,\hfill \\ \hfill \mathrm{max}(z_2,z_2,z_1+z_2+z_3)& & 2.\hfill \end{array}$$

For the classical types, the clusters and generalized assohiahedra have concrete combinatorial realizations in terms of triangulations of regular polygons. This realization is discussed in detail in  and further explored in . Here we restrict ourselves to an outline of the type $`A_n`$ construction, where we recover the classical associahedron, originally introduced by Stasheff . More precisely, the cluster complex of type $`A_n`$ is isomorphic to the dual complex of an $`n`$-dimensional associahedron, as explained in Example 5.17 below.

###### Example 5.17.

The cluster complex of type $`A_n`$ can be naturally identified with the simplicial complex whose simplices are all collections of non-crossing diagonals of a regular $`(n+3)`$-gon $`𝐏_{n+3}`$ (cf. Section 3). Thus, we need to identify the roots in $`\mathrm{\Phi }_1`$ with the diagonals of $`𝐏_{n+3}`$. This is done as follows. The roots in $`\mathrm{\Pi }`$ correspond to the diagonals on the “snake” shown in Figure 9.

Each positive root $`\alpha _i+\alpha _{i+1}+\mathrm{}+\alpha _j`$ corresponds to the unique diagonal that crosses precisely the diagonals $`\alpha _i,\alpha _{i+1},\mathrm{},\alpha _j`$ from the snake. As shown in , two roots are compatible if and only if the corresponding diagonals do not cross each other at an interior point. Consequently, an $`n`$-tuple of roots $`\beta _1,\mathrm{},\beta _n\mathrm{\Phi }_1`$ forms a maximal simplex in the cluster complex if and only if the corresponding diagonals do not cross each other—i.e., they form a triangulation of $`𝐏_{n+3}`$. (In particular, in agreement with Example 5.3, the “snake” triangulation is associated with a distinguished cluster.) As a result, the exchange graph for a cluster algebra of type $`A_n`$ becomes identified with the graph that already appeared in Section 3 (with triangulations of $`𝐏_{n+3}`$ as vertices, and diagonal flips as edges). The type $`A_3`$ case is illustrated by Figures 3 and 8.

In types $`B_n`$ and $`C_n`$, the cluster complex is isomorphic to the dual complex of the $`n`$-dimensional *cyclohedron*, or Bott-Taubes polytope . The vertices of this polytope are labeled by the centrally symmetric triangulations of a regular $`(2n+2)`$-gon $`𝐏_{2n+2}`$, while each edge corresponds to a pair of centrally symmetric flips, or to a single flip inside a rectangle. (We omit the description of the dictionary between the almost positive roots in a root system of type $`B_n`$ or $`C_n`$ and the (pairs of) diagonals in $`𝐏_{2n+2}`$, referring the reader to  or .) See Figure 10.

Similar description can be provided for the generalized associahedron of type $`D_n`$; see .

These combinatorial models for the cluster complexes of classical types $`ABCD`$ make the study of the corresponding cluster algebras much more tractable. In particular, these models are utilized in the proof of Theorem 4.26. It is therefore very desirable to find a solution of the following tantalizing problem.

###### Problem 5.18.

Construct combinatorial models for the generalized associahedra of exceptional types.

### 5.3. Numerology

As discussed in Example 5.17, the clusters in a cluster algebra of type $`A_n`$ are in bijection with the triangulations of a convex $`(n+3)`$-gon by $`n`$ non-crossing diagonals. The number of such triangulations is well known to be the Catalan number $`\frac{1}{n+2}\left(\genfrac{}{}{0pt}{}{2n+2}{n+1}\right)`$. The following theorem gives a general formula for the number of clusters in a cluster algebra of arbitrary finite type.

###### Theorem 5.19 ().

The number of clusters in a cluster algebra of finite type associated with a root system $`\mathrm{\Phi }`$ (equivalently, the number of vertices of the corresponding generalized associahedron) is equal to

(5.2)
$$N(\mathrm{\Phi })=\underset{i=1}{\overset{n}{}}\frac{e_i+h+1}{e_i+1},$$

where $`e_1,\mathrm{},e_n`$ are the exponents of $`\mathrm{\Phi }`$, and $`h`$ is the Coxeter number.

Figure 11 shows the values of $`N(\mathrm{\Phi })`$ for all irreducible crystallographic root systems $`\mathrm{\Phi }`$.

The numbers $`N(\mathrm{\Phi })`$ given by (5.2) can be thought of as generalizations of the Catalan numbers to an arbitrary Cartan-Killing type. These numbers are known to count  a variety of combinatorial objects related to the root system $`\mathrm{\Phi }`$. In particular, $`N(\mathrm{\Phi })`$ appears as the number of:

* *$`ad`$-nilpotent ideals* in a semisimple Lie algebra;
* antichains in the *root poset*;
* positive regions of the *Shi arrangement*;
* $`W`$-orbits in the quotient $`Q^{}/(h+1)Q^{}`$ of the dual root lattice;
* conjugacy classes of elements of a semisimple Lie group which have a finite order that divides $`h+1`$;
* *non-crossing partitions* of appropriate type.

We refer the reader to \[17, Lecture 5\] for a discussion of these enumerative formulas and their $`q`$-analogues, as well as for bibliographic directions.

As noted in \[17, Section 5.3\], substantial part of the combinatorial theory of generalized associahedra survives in the case of non-cryctallographic finite root systems $`I_2(n)`$, $`H_3`$, and $`H_4`$, including the construction of the clique complex in Theorem 5.14 and formula (5.2) for the number of root clusters—but excluding cluster algebras as such.

### 5.4. Concluding example

We close this survey with an example of a cluster algebra of finite type that arises from the geometric construction of Section 2.

###### Example 5.20.

\[Coordinate ring of a double Bruhat cell $`G^{w_{},w_{}}SL_3`$\] Recall that the open double Bruhat cell $`G^{w_{},w_{}}SL_3()`$ consists of all complex $`3\times 3`$ matrices $`x=(x_{ij})`$ of determinant $`1`$ whose minors

(5.3)
$$x_{13},||\begin{array}{cc}x_{12}& x_{13}\\ x_{22}& x_{23}\end{array}||,x_{31},||\begin{array}{cc}x_{21}& x_{22}\\ x_{31}& x_{32}\end{array}||$$

are nonzero. The coordinate ring $`[G^{w_{},w_{}}]`$ is a cluster algebra of type $`D_4`$ over the ground ring generated by the minors in (5.3) and their inverses. It has $`16`$ cluster variables, corresponding to the $`16`$ roots in $`\mathrm{\Phi }_1`$:

* $`14`$ (among the $`19`$ total) minors of $`x`$, namely, all excluding $`det(x)`$ and the $`4`$ minors in (5.3);
* $`x_{12}x_{21}x_{33}x_{12}x_{23}x_{31}x_{13}x_{21}x_{32}+x_{13}x_{22}x_{31}`$;
* $`x_{11}x_{23}x_{32}x_{12}x_{23}x_{31}x_{13}x_{21}x_{32}+x_{13}x_{22}x_{31}`$.

They form $`50`$ clusters of size $`4`$, one for each of the $`50`$ vertices of the type $`D_4`$ associahedron.

These clusters give rise to 50 different *total positivity criteria*: a matrix $`xSL_3`$ is totally positive if and only if the following $`8`$ functions are positive at $`x`$: the $`4`$ elements of any given cluster and the $`4`$ minors in (5.3).