American Mathematical Society

Cluster algebras I: Foundations

By Sergey Fomin and Andrei Zelevinsky

Abstract

In an attempt to create an algebraic framework for dual canonical bases and total positivity in semisimple groups, we initiate the study of a new class of commutative algebras.

1. Introduction

In this paper, we initiate the study of a new class of algebras, which we call cluster algebras. Before giving precise definitions, we present some of the main features of these algebras. For any positive integer n , a cluster algebra script upper A of rank n is a commutative ring with unit and no zero divisors, equipped with a distinguished family of generators called cluster variables. The set of cluster variables is the (non-disjoint) union of a distinguished collection of n -subsets called clusters. These clusters have the following exchange property: for any cluster bold x and any element x element-of bold x , there is another cluster obtained from bold x by replacing x with an element x prime related to x by a binomial exchange relation

StartLayout 1st Row with Label left-parenthesis 1.1 right-parenthesis EndLabel x x Superscript prime Baseline equals upper M 1 plus upper M 2 comma EndLayout

where upper M 1 and upper M 2 are two monomials without common divisors in the n minus 1 variables bold x minus StartSet x EndSet . Furthermore, any two clusters can be obtained from each other by a sequence of exchanges of this kind.

The prototypical example of a cluster algebra of rank 1 is the coordinate ring script upper A equals double-struck upper C left-bracket upper S upper L 2 right-bracket of the group upper S upper L 2 , viewed in the following way. Writing a generic element of upper S upper L 2 as Start 2 By 2 Matrix 1st Row 1st Column a 2nd Column b 2nd Row 1st Column c 2nd Column d EndMatrix comma we consider the entries a and d as cluster variables, and the entries b and c as scalars. There are just two clusters StartSet a EndSet and StartSet d EndSet , and script upper A is the algebra over the polynomial ring double-struck upper C left-bracket b comma c right-bracket generated by the cluster variables a and d subject to the binomial exchange relation

a d equals 1 plus b c period

Another important incarnation of a cluster algebra of rank 1 is the coordinate ring script upper A equals double-struck upper C left-bracket upper S upper L 3 slash upper N right-bracket of the base affine space of the special linear group upper S upper L 3 ; here upper N is the maximal unipotent subgroup of upper S upper L 3 consisting of all unipotent upper triangular matrices. Using the standard notation left-parenthesis x 1 comma x 2 comma x 3 comma x 12 comma x 13 comma x 23 right-parenthesis for the Plücker coordinates on upper S upper L 3 slash upper N , we view x 2 and x 13 as cluster variables; then script upper A is the algebra over the polynomial ring double-struck upper C left-bracket x 1 comma x 3 comma x 12 comma x 13 right-bracket generated by the two cluster variables x 2 and x 13 subject to the binomial exchange relation

x 2 x 13 equals x 1 x 23 plus x 3 x 12 period

This form of representing the algebra double-struck upper C left-bracket upper S upper L 3 slash upper N right-bracket is closely related to the choice of a linear basis in it consisting of all monomials in the six Plücker coordinates which are not divisible by x 2 x 13 . This basis was introduced and studied in Reference9 under the name “canonical basis”. As a representation of upper S upper L 3 , the space double-struck upper C left-bracket upper S upper L 3 slash upper N right-bracket is the multiplicity-free direct sum of all irreducible finite-dimensional representations, and each of the components is spanned by a part of the above basis. Thus, this construction provides a “canonical” basis in every irreducible finite-dimensional representation of upper S upper L 3 . After Lusztig’s work Reference13, this basis had been recognized as (the classical limit at q right-arrow 1 of) the dual canonical basis, i.e., the basis in the q -deformed algebra double-struck upper C Subscript q Baseline left-bracket upper S upper L 3 slash upper N right-bracket which is dual to Lusztig’s canonical basis in the appropriate q -deformed universal enveloping algebra (a.k.a. quantum group). The dual canonical basis in the space double-struck upper C left-bracket upper G slash upper N right-bracket was later constructed explicitly for a few other classical groups upper G of small rank: for upper G equals upper S p 4 in Reference16 and for upper G equals upper S upper L 4 in Reference2. In both cases, double-struck upper C left-bracket upper G slash upper N right-bracket can be seen to be a cluster algebra: there are 6 clusters of size 2 for upper G equals upper S p 4 , and 14 clusters of size 3 for upper G equals upper S upper L 4 .

We conjecture that the above examples can be extensively generalized: for any simply-connected connected semisimple group upper G , the coordinate rings double-struck upper C left-bracket upper G right-bracket and double-struck upper C left-bracket upper G slash upper N right-bracket , as well as coordinate rings of many other interesting varieties related to upper G , have a natural structure of a cluster algebra. This structure should serve as an algebraic framework for the study of “dual canonical bases” in these coordinate rings and their q -deformations. In particular, we conjecture that all monomials in the variables of any given cluster (the cluster monomials) belong to this dual canonical basis.

A particularly nice and well-understood example of a cluster algebra of an arbitrary rank n is the homogeneous coordinate ring double-struck upper C left-bracket upper G r Subscript 2 comma n plus 3 Baseline right-bracket of the Grassmannian of 2 -dimensional subspaces in double-struck upper C Superscript n plus 3 . This ring is generated by the Plücker coordinates left-bracket i j right-bracket , for 1 less-than-or-equal-to i less-than j less-than-or-equal-to n plus 3 , subject to the relations

left-bracket i k right-bracket left-bracket j l right-bracket equals left-bracket i j right-bracket left-bracket k l right-bracket plus left-bracket i l right-bracket left-bracket j k right-bracket comma

for all i less-than j less-than k less-than l . It is convenient to identify the indices 1 comma ellipsis comma n plus 3 with the vertices of a convex left-parenthesis n plus 3 right-parenthesis -gon, and the Plücker coordinates with its sides and diagonals. We view the sides left-bracket 12 right-bracket comma left-bracket 23 right-bracket comma ellipsis comma left-bracket n plus 2 comma n plus 3 right-bracket comma left-bracket 1 comma n plus 3 right-bracket as scalars, and the diagonals as cluster variables. The clusters are the maximal families of pairwise noncrossing diagonals; thus, they are in a natural bijection with the triangulations of this polygon. It is known that the cluster monomials form a linear basis in double-struck upper C left-bracket upper G r Subscript 2 comma n plus 3 Baseline right-bracket . To be more specific, we note that this ring is naturally identified with the ring of polynomial upper S upper L 2 -invariants of an left-parenthesis n plus 3 right-parenthesis -tuple of points in double-struck upper C squared . Under this isomorphism, the basis of cluster monomials corresponds to the basis considered in Reference11Reference18. (We are grateful to Bernd Sturmfels for bringing these references to our attention.)

An essential feature of the exchange relations (Equation1.1) is that the right-hand side does not involve subtraction. Recursively applying these relations, one can represent any cluster variable as a subtraction-free rational expression in the variables of any given cluster. This positivity property is consistent with a remarkable connection between canonical bases and the theory of total positivity, discovered by G. Lusztig Reference14Reference15. Generalizing the classical concept of totally positive matrices, he defined totally positive elements in any reductive group upper G , and proved that all elements of the dual canonical basis in double-struck upper C left-bracket upper G right-bracket take positive values at them.

It was realized in Reference15Reference5 that the natural geometric framework for total positivity is given by double Bruhat cells, the intersections of cells of the Bruhat decompositions with respect to two opposite Borel subgroups. Different aspects of total positivity in double Bruhat cells were explored by the authors of the present paper and their collaborators in Reference1Reference3Reference4Reference5Reference6Reference7Reference12Reference17Reference20. The binomial exchange relations of the form (Equation1.1) played a crucial role in these studies. It was the desire to explain the ubiquity of these relations and to place them in a proper context that led us to the concept of cluster algebras. The crucial step in this direction was made in Reference20, where a family of clusters and exchange relations was explicitly constructed in the coordinate ring of an arbitrary double Bruhat cell. However, this family was not complete: in general, some clusters were missing, and not any member of a cluster could be exchanged from it. Thus, we started looking for a natural way to “propagate” exchange relations from one cluster to another. The concept of cluster algebras is the result of this investigation. We conjecture that the coordinate ring of any double Bruhat cell is a cluster algebra.

This article, in which we develop the foundations of the theory, is conceived as the first in a forthcoming series. We attempt to make the exposition elementary and self-contained; in particular, no knowledge of semisimple groups, quantum groups or total positivity is assumed on the part of the reader.

One of the main structural features of cluster algebras established in the present paper is the following Laurent phenomenon: any cluster variable x viewed as a rational function in the variables of any given cluster is in fact a Laurent polynomial. This property is quite surprising: in most cases, the numerators of these Laurent polynomials contain a huge number of monomials, and the numerator for x moves into the denominator when we compute the cluster variable x prime obtained from x by an exchange (Equation1.1). The magic of the Laurent phenomenon is that, at every stage of this recursive process, a cancellation will inevitably occur, leaving a single monomial in the denominator.

In view of the positivity property discussed above, it is natural to expect that all Laurent polynomials for cluster variables will have positive coefficients. This seems to be a rather deep property; our present methods do not provide a proof of it.

On the bright side, it is possible to establish the Laurent phenomenon in many different situations spreading beyond the cluster algebra framework. One such extension is given in Theorem 3.2. By a modification of the method developed here, a large number of additional interesting instances of the Laurent phenomenon are established in a separate paper Reference8.

The paper is organized as follows. Section 2 contains an axiomatic definition, first examples and the first structural properties of cluster algebras. One of the technical difficulties in setting up the foundations involves the concept of an exchange graph whose vertices correspond to clusters, and the edges to exchanges among them. It is convenient to begin by taking the n -regular tree double-struck upper T Subscript n as our underlying graph. This tree can be viewed as a universal cover for the actual exchange graph, whose appearance is postponed until Section 7.

The Laurent phenomenon is established in Section 3. In Sections 4 and 5, we scrutinize the main definition, obtain useful reformulations, and introduce some important classes of cluster algebras.

Section 6 contains a detailed analysis of cluster algebras of rank 2. This analysis exhibits deep and somewhat mysterious connections between cluster algebras and Kac-Moody algebras. This is just the tip of an iceberg: these connections will be further explored (for cluster algebras of an arbitrary rank) in the sequel to this paper. The main result of this sequel is a complete classification of cluster algebras of finite type, i.e., those with finitely many distinct clusters; cf. Example 7.6. This classification turns out to be yet another instance of the famous Cartan-Killing classification.

2. Main definitions

Let upper I be a finite set of size n ; the standard choice will be upper I equals left-bracket n right-bracket equals StartSet 1 comma 2 comma ellipsis comma n EndSet . Let double-struck upper T Subscript n denote the n -regular tree, whose edges are labeled by the elements of upper I , so that the n edges emanating from each vertex receive different labels. By a common abuse of notation, we will sometimes denote by double-struck upper T Subscript n the set of the tree’s vertices. We will write t StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t prime if vertices t comma t prime element-of double-struck upper T Subscript n Baseline are joined by an edge labeled by i .

To each vertex t element-of double-struck upper T Subscript n , we will associate a cluster of n generators (“variables”) bold x left-parenthesis t right-parenthesis equals left-parenthesis x Subscript i Baseline left-parenthesis t right-parenthesis right-parenthesis Subscript i element-of upper I . All these variables will commute with each other and satisfy the following exchange relations, for every edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t prime in double-struck upper T Subscript n :

StartLayout 1st Row with Label left-parenthesis 2.1 right-parenthesis EndLabel 1st Column x Subscript i Baseline left-parenthesis t right-parenthesis 2nd Column equals x Subscript i Baseline left-parenthesis t prime right-parenthesis for any i not-equals j semicolon 2nd Row with Label left-parenthesis 2.2 right-parenthesis EndLabel 1st Column x Subscript j Baseline left-parenthesis t right-parenthesis x Subscript j Baseline left-parenthesis t prime right-parenthesis 2nd Column equals upper M Subscript j Baseline left-parenthesis t right-parenthesis left-parenthesis bold x left-parenthesis t right-parenthesis right-parenthesis plus upper M Subscript j Baseline left-parenthesis t Superscript prime Baseline right-parenthesis left-parenthesis bold x left-parenthesis t Superscript prime Baseline right-parenthesis right-parenthesis period EndLayout

Here upper M Subscript j Baseline left-parenthesis t right-parenthesis and upper M Subscript j Baseline left-parenthesis t prime right-parenthesis are two monomials in the n variables x Subscript i Baseline comma i element-of upper I ; we think of these monomials as being associated with the two ends of the edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t prime .

To be more precise, let double-struck upper P be an abelian group without torsion, written multiplicatively. We call double-struck upper P the coefficient group; a prototypical example is a free abelian group of finite rank. Every monomial upper M Subscript j Baseline left-parenthesis t right-parenthesis in (Equation2.2) will have the form

StartLayout 1st Row with Label left-parenthesis 2.3 right-parenthesis EndLabel upper M Subscript j Baseline left-parenthesis t right-parenthesis equals p Subscript j Baseline left-parenthesis t right-parenthesis product Underscript i element-of upper I Endscripts x Subscript i Superscript b Super Subscript i Superscript Baseline comma EndLayout

for some coefficient p Subscript j Baseline left-parenthesis t right-parenthesis element-of double-struck upper P and some nonnegative integer exponents b Subscript i .

The monomials upper M Subscript j Baseline left-parenthesis t right-parenthesis must satisfy certain conditions (axioms). To state them, we will need a little preparation. Let us write upper P bar upper Q to denote that a polynomial upper P divides a polynomial upper Q . Accordingly, x Subscript i Baseline bar upper M Subscript j Baseline left-parenthesis t right-parenthesis means that the monomial upper M Subscript j Baseline left-parenthesis t right-parenthesis contains the variable x Subscript i . For a rational function upper F equals upper F left-parenthesis x comma y comma period period period right-parenthesis , the notation upper F vertical-bar Subscript x left-arrow g left-parenthesis x comma y comma period period period right-parenthesis Baseline will denote the result of substituting g left-parenthesis x comma y comma period period period right-parenthesis for x into upper F . To illustrate, if upper F left-parenthesis x comma y right-parenthesis equals x y , then upper F vertical-bar Subscript x left-arrow StartFraction y Over x EndFraction Baseline equals StartFraction y squared Over x EndFraction .

Definition 2.1

An exchange pattern on double-struck upper T Subscript n with coefficients in double-struck upper P is a family of monomials script upper M equals left-parenthesis upper M Subscript j Baseline left-parenthesis t right-parenthesis right-parenthesis Subscript t element-of double-struck upper T Sub Subscript n Subscript comma j element-of upper I of the form (Equation2.3) satisfying the following four axioms:

StartLayout 1st Row with Label left-parenthesis 2.4 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column If t element-of double-struck upper T Subscript n Baseline comma then x Subscript j Baseline does-not-divide upper M Subscript j Baseline left-parenthesis t right-parenthesis period 2nd Row with Label left-parenthesis 2.5 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column If t 1 StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t 2 and x Subscript i Baseline bar upper M Subscript j Baseline left-parenthesis t 1 right-parenthesis comma then x Subscript i Baseline does-not-divide upper M Subscript j Baseline left-parenthesis t 2 right-parenthesis period 3rd Row with Label left-parenthesis 2.6 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column If t 1 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t 2 StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t 3 comma then x Subscript j Baseline bar upper M Subscript i Baseline left-parenthesis t 1 right-parenthesis if and only if x Subscript i Baseline bar upper M Subscript j Baseline left-parenthesis t 2 right-parenthesis period 4th Row with Label left-parenthesis 2.7 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column Let t 1 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t 2 StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t 3 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t 4 period Then StartFraction upper M Subscript i Baseline left-parenthesis t 3 right-parenthesis Over upper M Subscript i Baseline left-parenthesis t 4 right-parenthesis EndFraction equals StartFraction upper M Subscript i Baseline left-parenthesis t 2 right-parenthesis Over upper M Subscript i Baseline left-parenthesis t 1 right-parenthesis EndFraction vertical-bar Subscript x Sub Subscript j Subscript left-arrow upper M 0 slash x Sub Subscript j Subscript Baseline comma 5th Row 1st Column Blank 2nd Column Blank 3rd Column where upper M 0 equals left-parenthesis upper M Subscript j Baseline left-parenthesis t 2 right-parenthesis plus upper M Subscript j Baseline left-parenthesis t 3 right-parenthesis right-parenthesis vertical-bar Subscript x Sub Subscript i Subscript equals 0 Baseline period EndLayout

We note that in the last axiom, the substitution x Subscript j Baseline left-arrow StartFraction upper M 0 Over x Subscript j Baseline EndFraction is effectively monomial, since in the event that neither upper M Subscript j Baseline left-parenthesis t 2 right-parenthesis nor upper M Subscript j Baseline left-parenthesis t 3 right-parenthesis contain x Subscript i , condition (Equation2.6) requires that both upper M Subscript i Baseline left-parenthesis t 2 right-parenthesis and upper M Subscript i Baseline left-parenthesis t 1 right-parenthesis do not depend on x Subscript j , thus making the whole substitution irrelevant.

One easily checks that axiom (Equation2.7) is invariant under the “flip” t 1 left-right-arrow t 4 , t 2 left-right-arrow t 3 , so no restrictions are added if we apply it “backwards”. The axioms also imply at once that setting

StartLayout 1st Row with Label left-parenthesis 2.8 right-parenthesis EndLabel upper M prime Subscript j Baseline left-parenthesis t right-parenthesis equals upper M Subscript j Baseline left-parenthesis t prime right-parenthesis EndLayout

for every edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t prime , we obtain another exchange pattern script upper M prime ; this gives a natural involution script upper M right-arrow script upper M prime on the set of all exchange patterns.

Remark 2.2

Informally speaking, axiom (Equation2.7) describes the propagation of an exchange pattern along the edges of double-struck upper T Subscript n . More precisely, let us fix the 2 n exchange monomials for all edges emanating from a given vertex t . This choice uniquely determines the ratio upper M Subscript i Baseline left-parenthesis t prime right-parenthesis slash upper M Subscript i Baseline left-parenthesis t double-prime right-parenthesis for any vertex t prime adjacent to t and any edge t prime StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t double-prime (to see this, take t 2 equals t and t 3 equals t prime in (Equation2.7), and allow i to vary). In view of (Equation2.5), this ratio in turn uniquely determines the exponents of all variables x Subscript k in both monomials upper M Subscript i Baseline left-parenthesis t prime right-parenthesis and upper M Subscript i Baseline left-parenthesis t double-prime right-parenthesis . There remains, however, one degree of freedom in determining the coefficients p Subscript i Baseline left-parenthesis t prime right-parenthesis and p Subscript i Baseline left-parenthesis t double-prime right-parenthesis because only their ratio is prescribed by (Equation2.7). In Section 5 we shall introduce an important class of normalized exchange patterns for which this degree of freedom disappears, and so the whole pattern is uniquely determined by the 2 n monomials associated with edges emanating from a given vertex.

Let double-struck upper Z double-struck upper P denote the group ring of double-struck upper P with integer coefficients. For an edge t StartLayout 1st Row k 2nd Row minus minus minus 3rd Row Blank EndLayout t prime , we refer to the binomial upper P equals upper M Subscript k Baseline left-parenthesis t right-parenthesis plus upper M Subscript k Baseline left-parenthesis t prime right-parenthesis element-of double-struck upper Z double-struck upper P left-bracket x Subscript i Baseline colon i element-of upper I right-bracket as the exchange polynomial. We will write t StartLayout 1st Row Blank 2nd Row minus minus minus 3rd Row upper P EndLayout t Superscript prime Baseline or t StartLayout 1st Row k 2nd Row minus minus minus 3rd Row upper P EndLayout t Superscript prime Baseline to indicate this fact. Note that, in view of the axiom (Equation2.4), the right-hand side of the exchange relation (Equation2.2) can be written as upper P left-parenthesis bold x left-parenthesis t right-parenthesis right-parenthesis , which is the same as upper P left-parenthesis bold x left-parenthesis t prime right-parenthesis right-parenthesis .

Let script upper M be an exchange pattern on double-struck upper T Subscript n with coefficients in double-struck upper P . Note that since double-struck upper P is torsion-free, the ring double-struck upper Z double-struck upper P has no zero divisors. For every vertex t element-of double-struck upper T Subscript n , let script upper F left-parenthesis t right-parenthesis denote the field of rational functions in the cluster variables x Subscript i Baseline left-parenthesis t right-parenthesis , i element-of upper I , with coefficients in double-struck upper Z double-struck upper P . For every edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row upper P EndLayout t prime , we define a double-struck upper Z double-struck upper P -linear field isomorphism upper R Subscript t t Sub Superscript prime Subscript Baseline colon script upper F left-parenthesis t Superscript prime Baseline right-parenthesis right-arrow script upper F left-parenthesis t right-parenthesis by

StartLayout 1st Row with Label left-parenthesis 2.9 right-parenthesis EndLabel StartLayout 1st Row upper R Subscript t t prime Baseline left-parenthesis x Subscript i Baseline left-parenthesis t prime right-parenthesis right-parenthesis equals x Subscript i Baseline left-parenthesis t right-parenthesis for i not-equals k semicolon 2nd Row upper R Subscript t t prime Baseline left-parenthesis x Subscript k Baseline left-parenthesis t prime right-parenthesis right-parenthesis equals StartFraction upper P left-parenthesis bold x left-parenthesis t right-parenthesis right-parenthesis Over x Subscript k Baseline left-parenthesis t right-parenthesis EndFraction period EndLayout EndLayout

Note that property (Equation2.4) ensures that upper R Subscript t prime t Baseline equals upper R Subscript t t prime Superscript negative 1 . The transition maps upper R Subscript t t prime enable us to identify all the fields script upper F left-parenthesis t right-parenthesis with each other. We can then view them as a single field script upper F that contains all the elements x Subscript i Baseline left-parenthesis t right-parenthesis , for all t element-of double-struck upper T Subscript n and i element-of upper I . Inside script upper F , these elements satisfy the exchange relations (Equation2.1)–(Equation2.2).

Definition 2.3

Let double-struck upper A be a subring with unit in double-struck upper Z double-struck upper P containing all coefficients p Subscript i Baseline left-parenthesis t right-parenthesis for i element-of upper I and t element-of double-struck upper T Subscript n . The cluster algebra script upper A equals script upper A Subscript double-struck upper A Baseline left-parenthesis script upper M right-parenthesis of rank n over double-struck upper A associated with an exchange pattern script upper M is the double-struck upper A -subalgebra with unit in script upper F generated by the union of all clusters bold x left-parenthesis t right-parenthesis , for t element-of double-struck upper T Subscript n .

The smallest possible ground ring double-struck upper A is the subring of double-struck upper Z double-struck upper P generated by all the coefficients p Subscript i Baseline left-parenthesis t right-parenthesis ; the largest one is double-struck upper Z double-struck upper P itself. An intermediate choice of double-struck upper A appears in Proposition 2.6 below.

Since script upper A is a subring of a field script upper F , it is a commutative ring with no zero divisors. We also note that if script upper M prime is obtained from script upper M by the involution (Equation2.8), then the cluster algebra script upper A Subscript double-struck upper A Baseline left-parenthesis script upper M prime right-parenthesis is naturally identified with script upper A Subscript double-struck upper A Baseline left-parenthesis script upper M right-parenthesis .

Example 2.4

Let n equals 1 . The tree double-struck upper T 1 has only one edge t StartLayout 1st Row 1 2nd Row minus minus minus 3rd Row Blank EndLayout t prime . The corresponding cluster algebra script upper A has two generators x equals x 1 left-parenthesis t right-parenthesis and x prime equals x 1 left-parenthesis t prime right-parenthesis satisfying the exchange relation

x x Superscript prime Baseline equals p plus p Superscript prime Baseline comma

where p and p prime are arbitrary elements of the coefficient group double-struck upper P . In the “universal” setting, we take double-struck upper P to be the free abelian group generated by p and p prime . Then the two natural choices for the ground ring double-struck upper A are the polynomial ring double-struck upper Z left-bracket p comma p prime right-bracket , and the Laurent polynomial ring double-struck upper Z double-struck upper P equals double-struck upper Z left-bracket p Superscript plus-or-minus 1 Baseline comma p prime Superscript plus-or-minus 1 Baseline right-bracket . All other realizations of script upper A can be viewed as specializations of the universal one. Despite the seeming triviality of this example, it covers several important algebras: the coordinate ring of each of the varieties upper S upper L 2 , upper G r Subscript 2 comma 4 and upper S upper L 3 slash upper B (cf. Section 1) is a cluster algebra of rank 1 , for an appropriate choice of double-struck upper P , p , p prime and double-struck upper A .

Example 2.5

Consider the case n equals 2 . The tree double-struck upper T 2 is shown below:

StartLayout 1st Row with Label left-parenthesis 2.10 right-parenthesis EndLabel midline-horizontal-ellipsis StartLayout 1st Row 1 2nd Row minus minus minus 3rd Row Blank EndLayout t 0 StartLayout 1st Row 2 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout t 1 StartLayout 1st Row 1 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout t 2 StartLayout 1st Row 2 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout t 3 StartLayout 1st Row 1 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout t 4 StartLayout 1st Row 2 2nd Row minus minus minus 3rd Row Blank EndLayout midline-horizontal-ellipsis period EndLayout

Let us denote the cluster variables as follows:

y 1 equals x 1 left-parenthesis t 0 right-parenthesis equals x 1 left-parenthesis t 1 right-parenthesis comma y 2 equals x 2 left-parenthesis t 1 right-parenthesis equals x 2 left-parenthesis t 2 right-parenthesis comma y 3 equals x 1 left-parenthesis t 2 right-parenthesis equals x 1 left-parenthesis t 3 right-parenthesis comma period period period

(the above equalities among the cluster variables follow from (Equation2.1)). Then the clusters look like

midline-horizontal-ellipsis StartLayout 1st Row 1 2nd Row minus minus minus 3rd Row Blank EndLayout StartLayout 1st Row y 1 comma y 0 2nd Row bullet 3rd Row t 0 EndLayout StartLayout 1st Row 2 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout StartLayout 1st Row y 2 comma y 1 2nd Row bullet 3rd Row t 1 EndLayout StartLayout 1st Row 1 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout StartLayout 1st Row y 3 comma y 2 2nd Row bullet 3rd Row t 2 EndLayout StartLayout 1st Row 2 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout StartLayout 1st Row y 4 comma y 3 2nd Row bullet 3rd Row t 3 EndLayout StartLayout 1st Row 1 2nd Row minus minus minus minus minus minus minus 3rd Row Blank EndLayout StartLayout 1st Row y 5 comma y 4 2nd Row bullet 3rd Row t 4 EndLayout StartLayout 1st Row 2 2nd Row minus minus minus 3rd Row Blank EndLayout midline-horizontal-ellipsis period

We claim that the exchange relations (Equation2.2) can be written in the following form:

StartLayout 1st Row with Label left-parenthesis 2.11 right-parenthesis EndLabel StartLayout 1st Row 1st Column y 0 y 2 equals q 1 y 1 Superscript b Baseline plus r 1 comma 2nd Column y 1 y 3 equals q 2 y 2 Superscript c Baseline plus r 2 comma 2nd Row 1st Column y 2 y 4 equals q 3 y 3 Superscript b Baseline plus r 3 comma 2nd Column y 3 y 5 equals q 4 y 4 Superscript c Baseline plus r 4 comma ellipsis comma EndLayout EndLayout

where the integers b and c are either both positive or both equal to 0 , and the coefficients q Subscript m and r Subscript m are elements of double-struck upper P satisfying the relations

StartLayout 1st Row with Label left-parenthesis 2.12 right-parenthesis EndLabel StartLayout 1st Row 1st Column q 0 q 2 r 1 Superscript c Baseline equals r 0 r 2 comma 2nd Column q 1 q 3 r 2 Superscript b Baseline equals r 1 r 3 comma 2nd Row 1st Column q 2 q 4 r 3 Superscript c Baseline equals r 2 r 4 comma 2nd Column q 3 q 5 r 4 Superscript b Baseline equals r 3 r 5 comma period period period period EndLayout EndLayout

Furthermore, any such choice of parameters b , c , left-parenthesis q Subscript m Baseline right-parenthesis , left-parenthesis r Subscript m Baseline right-parenthesis results in a well-defined cluster algebra of rank 2.

To prove this, we notice that, in view of (Equation2.4)–(Equation2.5), both monomials upper M 2 left-parenthesis t 0 right-parenthesis and upper M 2 left-parenthesis t 1 right-parenthesis do not contain the variable x 2 , and at most one of them contains x 1 . If x 1 enters neither upper M 2 left-parenthesis t 0 right-parenthesis nor upper M 2 left-parenthesis t 1 right-parenthesis , then these two are simply elements of double-struck upper P . But then (Equation2.6) forces all monomials upper M Subscript i Baseline left-parenthesis t Subscript m Baseline right-parenthesis to be elements of double-struck upper P , while (Equation2.7) implies that it is possible to give the names q Subscript m and r Subscript m to the two monomials corresponding to each edge t Subscript m Baseline StartLayout 1st Row Blank 2nd Row minus minus minus 3rd Row Blank EndLayout t Subscript m plus 1 so that (Equation2.11)–(Equation2.12) hold with b equals c equals 0 .

Next, consider the case when precisely one of the monomials upper M 2 left-parenthesis t 0 right-parenthesis and upper M 2 left-parenthesis t 1 right-parenthesis contains x 1 . Applying if necessary the involution (Equation2.8) to our exchange pattern, we may assume that upper M 2 left-parenthesis t 0 right-parenthesis equals q 1 x 1 Superscript b and upper M 2 left-parenthesis t 1 right-parenthesis equals r 1 for some positive integer b and some q 1 comma r 1 element-of double-struck upper P . Thus, the exchange relation associated to the edge t 0 StartLayout 1st Row 2 2nd Row minus minus minus 3rd Row Blank EndLayout t 1 takes the form y 0 y 2 equals q 1 y 1 Superscript b Baseline plus r 1 . By (Equation2.6), we have upper M 1 left-parenthesis t 1 right-parenthesis equals q 2 x 2 Superscript c and upper M 1 left-parenthesis t 2 right-parenthesis equals r 2 for some positive integer c and some q 2 comma r 2 element-of double-struck upper P . Then the exchange relation for the edge t 1 StartLayout 1st Row 1 2nd Row minus minus minus 3rd Row Blank EndLayout t 2 takes the form y 1 y 3 equals q 2 y 2 Superscript c Baseline plus r 2 . At this point, we invoke (Equation2.7):

StartFraction upper M 2 left-parenthesis t 2 right-parenthesis Over upper M 2 left-parenthesis t 3 right-parenthesis EndFraction equals StartFraction upper M 2 left-parenthesis t 1 right-parenthesis Over upper M 2 left-parenthesis t 0 right-parenthesis EndFraction StartAbsoluteValue equals StartFraction r 1 Over q 1 x 1 Superscript b Baseline EndFraction EndAbsoluteValue Subscript x 1 left-arrow r 2 slash x 1 Baseline Subscript x 1 left-arrow r 2 slash x 1 Baseline equals StartFraction r 1 x 1 Superscript b Baseline Over q 1 r 2 Superscript b Baseline EndFraction period

By (Equation2.5), we have upper M 2 left-parenthesis t 2 right-parenthesis equals q 3 x 1 Superscript b and upper M 2 left-parenthesis t 3 right-parenthesis equals r 3 for some q 3 comma r 3 element-of double-struck upper P satisfying q 1 q 3 r 2 Superscript b Baseline equals r 1 r 3 . Continuing in the same way, we obtain all relations (Equation2.11)–(Equation2.12).

For fixed b and c , the “universal” coefficient group double-struck upper P is the multiplicative abelian group generated by the elements q Subscript m and r Subscript m for all m element-of double-struck upper Z subject to the defining relations (Equation2.12). It is easy to see that this is a free abelian group of infinite rank. As a set of its free generators, one can choose any subset of StartSet q Subscript m Baseline comma r Subscript m Baseline colon m element-of double-struck upper Z EndSet that contains four generators q 0 comma r 0 comma q 1 comma r 1 and precisely one generator from each pair StartSet q Subscript m Baseline comma r Subscript m Baseline EndSet for m not-equals 0 comma 1 .

A nice specialization of this setup is provided by the homogeneous coordinate ring of the Grassmannian upper G r Subscript 2 comma 5 . Recall (cf. Section 1) that this ring is generated by the Plücker coordinates left-bracket k comma l right-bracket , where k and l are distinct elements of the cyclic group double-struck upper Z slash 5 double-struck upper Z . We shall write m overbar equals m mod 5 element-of double-struck upper Z slash 5 double-struck upper Z for m element-of double-struck upper Z , and adopt the convention left-bracket k comma l right-bracket equals left-bracket l comma k right-bracket ; see Figure 1.

The ideal of relations among the Plücker coordinates is generated by the relations

left-bracket m overbar comma ModifyingAbove m plus 2 With bar right-bracket left-bracket ModifyingAbove m plus 1 With bar comma ModifyingAbove m plus 3 With bar right-bracket equals left-bracket m overbar comma ModifyingAbove m plus 1 With bar right-bracket left-bracket ModifyingAbove m plus 2 With bar comma ModifyingAbove m plus 3 With bar right-bracket plus left-bracket m overbar comma ModifyingAbove m plus 3 With bar right-bracket left-bracket ModifyingAbove m plus 1 With bar comma ModifyingAbove m plus 2 With bar right-bracket

for m element-of double-struck upper Z . A direct check shows that these relations are a specialization of the relations (Equation2.11), if we set b equals c equals 1 , y Subscript m Baseline equals left-bracket ModifyingAbove 2 m minus 1 With bar comma ModifyingAbove 2 m plus 1 With bar right-bracket , q Subscript m Baseline equals left-bracket ModifyingAbove 2 m minus 2 With bar comma ModifyingAbove 2 m plus 2 With bar right-bracket , and r Subscript m Baseline equals left-bracket ModifyingAbove 2 m minus 2 With bar comma ModifyingAbove 2 m minus 1 With bar right-bracket left-bracket ModifyingAbove 2 m plus 1 With bar comma ModifyingAbove 2 m plus 2 With bar right-bracket equals q Subscript m minus 2 Baseline q Subscript m plus 2 for all m element-of double-struck upper Z . The coefficient group double-struck upper P is the multiplicative free abelian group with 5 generators q Subscript m . It is also immediate that the elements q Subscript m and r Subscript m defined in this way satisfy the relations (Equation2.12).

We conclude this section by introducing two important operations on exchange patterns: restriction and direct product. Let us start with restriction. Let script upper M be an exchange pattern of rank n with an index set upper I and coefficient group double-struck upper P . Let upper J be a subset of size m in upper I . Let us remove from double-struck upper T Subscript n all edges labeled by indices in upper I minus upper J , and choose any connected component double-struck upper T of the resulting graph. This component is naturally identified with double-struck upper T Subscript m . Let script upper M prime denote the restriction of script upper M to double-struck upper T , i.e., the collection of monomials upper M Subscript j Baseline left-parenthesis t right-parenthesis for all j element-of upper J and t element-of double-struck upper T . Then script upper M prime is an exchange pattern on double-struck upper T whose coefficient group double-struck upper P prime is the direct product of double-struck upper P with the multiplicative free abelian group with generators x Subscript i , i element-of upper I minus upper J . We shall say that script upper M prime is obtained from script upper M by restriction from upper I to upper J . Note that script upper M prime depends on the choice of a connected component double-struck upper T , so there can be several different patterns obtained from script upper M by restriction from upper I to upper J . (We thank the anonymous referee for pointing this out.)

Proposition 2.6

Let script upper A equals script upper A Subscript double-struck upper A Baseline left-parenthesis script upper M right-parenthesis be a cluster algebra of rank n associated with an exchange pattern script upper M , and let script upper M prime be obtained from script upper M by restriction from upper I to upper J using a connected component double-struck upper T . The double-struck upper A -subalgebra of script upper A generated by union Underscript t element-of double-struck upper T Endscripts bold x left-parenthesis t right-parenthesis is naturally identified with the cluster algebra script upper A Subscript double-struck upper A prime Baseline left-parenthesis script upper M prime right-parenthesis , where double-struck upper A prime is the polynomial ring double-struck upper A left-bracket x Subscript i Baseline colon i element-of upper I minus upper J right-bracket .

Proof.

If i element-of upper I minus upper J , then (Equation2.1) implies that x Subscript i Baseline left-parenthesis t right-parenthesis stays constant as t varies over double-struck upper T . Therefore, we can identify this variable with the corresponding generator x Subscript i of the coefficient group double-struck upper P prime , and the statement follows.

Let us now consider two exchange patterns script upper M 1 and script upper M 2 of ranks n 1 and n 2 , respectively, with index sets upper I 1 and upper I 2 , and coefficient groups double-struck upper P 1 and double-struck upper P 2 . We will construct the exchange pattern script upper M equals script upper M 1 times script upper M 2 (the direct product of script upper M 1 and script upper M 2 ) of rank n equals n 1 plus n 2 , with the index set upper I equals upper I 1 square-cup upper I 2 , and coefficient group double-struck upper P equals double-struck upper P 1 times double-struck upper P 2 . Consider the tree double-struck upper T Subscript n whose edges are colored by upper I , and, for nu element-of StartSet 1 comma 2 EndSet , let pi Subscript nu Baseline colon double-struck upper T Subscript n Baseline right-arrow double-struck upper T Subscript n Sub Subscript nu Subscript Baseline be a map with the following property: if t StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout t prime in double-struck upper T Subscript n and i element-of upper I Subscript nu (resp., i element-of upper I minus upper I Subscript nu Baseline equals upper I Subscript 3 minus nu ), then pi Subscript nu Baseline left-parenthesis t right-parenthesis StartLayout 1st Row i 2nd Row minus minus minus 3rd Row Blank EndLayout pi Subscript nu Baseline left-parenthesis t prime right-parenthesis in double-struck upper T Subscript n Sub Subscript nu (resp., pi Subscript nu Baseline left-parenthesis t right-parenthesis equals pi Subscript nu Baseline left-parenthesis t prime right-parenthesis ). Clearly, such a map pi Subscript nu exists and is essentially unique: it is determined by specifying the image of any vertex of double-struck upper T Subscript n . We now introduce the exchange pattern script upper M on double-struck upper T Subscript n by setting, for every t element-of double-struck upper T Subscript n and i element-of upper I Subscript nu subset-of upper I , the monomial upper M Subscript i Baseline left-parenthesis t right-parenthesis to be equal to upper M Subscript i Baseline left-parenthesis pi Subscript nu Baseline left-parenthesis t right-parenthesis right-parenthesis , the latter monomial coming from the exchange pattern script upper M Subscript nu . The axioms (Equation2.4)–(Equation2.7) for script upper M are checked directly.

Proposition 2.7

Let script upper A 1 equals script upper A Subscript double-struck upper A 1 Baseline left-parenthesis script upper M 1 right-parenthesis and script upper A 2 equals script upper A Subscript double-struck upper A 2 Baseline left-parenthesis script upper M 2 right-parenthesis be cluster algebras. Let script upper M equals script upper M 1 times script upper M 2 and double-struck upper A equals double-struck upper A 1 circled-times double-struck upper A 2 . Then the cluster algebra script upper A Subscript double-struck upper A Baseline left-parenthesis script upper M right-parenthesis is canonically isomorphic to the tensor product of algebras script upper A 1 circled-times script upper A 2 left-parenthesis all tensor products are taken over double-struck upper Z right-parenthesis .

Proof.

Let us identify each cluster variable x Subscript i Baseline left-parenthesis t right-parenthesis , for t element-of double-struck upper T Subscript n and i element-of upper I 1 subset-of upper I (resp., i element-of upper I 2 subset-of upper I ), with x Subscript i Baseline left-parenthesis pi 1 left-parenthesis t right-parenthesis right-parenthesis circled-times 1 (resp., 1 circled-times x Subscript i Baseline left-parenthesis pi 2 left-parenthesis t right-parenthesis right-parenthesis right-parenthesis . Under this identification, the exchange relations for the exchange pattern script upper M become identical to the exchange relations for script upper M 1 and script upper M 2 .

3. The Laurent phenomenon

In this section we prove the following important property of cluster algebras.

Theorem 3.1

In a cluster algebra, any cluster variable is expressed in terms of any given cluster as a Laurent polynomial with coefficients in the group ring double-struck upper Z double-struck upper P .

We conjecture that each of the coefficients in these Laurent polynomials is actually a nonnegative integer linear combination of elements in double-struck upper P .

We will obtain Theorem 3.1 as a corollary of a more general result, which applies to more general underlying graphs and more general (not necessarily binomial) exchange polynomials.

Since Theorem 3.1 is trivial for n equals 1 , we shall assume that n greater-than-or-equal-to 2 . For every m greater-than-or-equal-to 1 , let double-struck upper T Subscript n comma m be a tree of the form shown in Figure 2. The tree double-struck upper T Subscript n comma m has m vertices of degree n in its “spine” and m left-parenthesis n minus 2 right-parenthesis plus 2 vertices of degree 1. We label every edge of the tree by an element of an n -element index set upper I , so that the n edges incident to each vertex on the spine receive different labels. (The reader may wish to think of the tree double-struck upper T Subscript n comma m as being part of the n -regular tree double-struck upper T Subscript n of the cluster-algebra setup.)

We fix two vertices t Subscript head and t Subscript tail of double-struck upper T Subscript n comma m that do not belong to the spine and are connected to its opposite ends. This gives rise to the orientation on the spine: away from t Subscript tail and towards t Subscript head (see Figure 2).

As before, let double-struck upper P be an abelian group without torsion, written multiplicatively. Let double-struck upper Z Subscript greater-than-or-equal-to 0 Baseline double-struck upper P denote the additive semigroup generated by double-struck upper P in the integer group ring double-struck upper Z double-struck upper P . Assume that a nonzero polynomial upper P in the variables x Subscript i Baseline comma i element-of upper I , with coefficients in double-struck upper Z Subscript greater-than-or-equal-to 0 Baseline double-struck upper P , is associated with every edge t StartLayout 1st Row Blank 2nd Row minus minus minus 3rd Row Blank EndLayout t prime of double-struck upper T Subscript n comma m . We call upper P an exchange polynomial, and write t StartLayout 1st Row Blank 2nd Row minus minus minus 3rd Row upper P EndLayout t prime to describe this situation. Suppose that the exchange polynomials associated with the edges of double-struck upper T Subscript n comma m satisfy the following conditions:

StartLayout 1st Row with Label left-parenthesis 3.1 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column An exchange polynomial associated with an edge labeled by j does not 2nd Row 1st Column Blank 2nd Column Blank 3rd Column depend on x Subscript j Baseline comma and is not divisible by any x Subscript i Baseline comma i element-of upper I period 3rd Row with Label left-parenthesis 3.2 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column If t 0 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row upper P EndLayout t 1 StartLayout 1st Row j 2nd Row minus minus right-arrow 3rd Row upper Q EndLayout t 2 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row upper R EndLayout t 3 comma then upper R equals upper C dot left-parenthesis upper P vertical-bar Subscript x Sub Subscript j Subscript left-arrow upper Q 0 slash x Sub Subscript j Subscript Baseline right-parenthesis comma where upper Q 0 equals upper Q vertical-bar Subscript x Sub Subscript i Subscript equals 0 Baseline comma 4th Row 1st Column Blank 2nd Column Blank 3rd Column and upper C is a Laurent polynomial with coefficients in double-struck upper Z Subscript greater-than-or-equal-to 0 Baseline double-struck upper P period EndLayout

(Note the orientation of the edge t 1 right-arrow t 2 in (Equation3.2).)

For every vertex t on the spine, let script upper P left-parenthesis t right-parenthesis denote the family of n exchange polynomials associated with the edges emanating from t . Also, let script upper C denote the collection of all Laurent polynomials upper C that appear in condition (Equation3.2), for all possible choices of t 0 comma t 1 comma t 2 comma t 3 , and let double-struck upper A subset-of double-struck upper Z double-struck upper P denote the subring with unit generated by all coefficients of the Laurent polynomials from script upper P left-parenthesis t Subscript base Baseline right-parenthesis union script upper C , where t Subscript base is the vertex on the spine connected with t Subscript tail .

As before, we associate a cluster bold x left-parenthesis t right-parenthesis equals StartSet x Subscript i Baseline left-parenthesis t right-parenthesis colon i element-of upper I EndSet to each vertex t element-of double-struck upper T Subscript n comma m , and consider the field script upper F left-parenthesis t right-parenthesis of rational functions in these variables with coefficients in double-struck upper Z double-struck upper P . All these fields are identified with each other by the transition isomorphisms upper R Subscript t t Sub Superscript prime Subscript Baseline colon script upper F left-parenthesis t Superscript prime Baseline right-parenthesis right-arrow script upper F left-parenthesis t right-parenthesis defined as in (Equation2.9). We then view the fields script upper F left-parenthesis t right-parenthesis as a single field script upper F that contains all the elements x Subscript i Baseline left-parenthesis t right-parenthesis , for t element-of double-struck upper T Subscript n comma m and i element-of upper I . These elements satisfy the exchange relations (Equation2.1) and the following version of (Equation2.2):

x Subscript j Baseline left-parenthesis t right-parenthesis x Subscript j Baseline left-parenthesis t Superscript prime Baseline right-parenthesis equals upper P left-parenthesis bold x left-parenthesis t right-parenthesis right-parenthesis comma

for any edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row upper P EndLayout t prime in double-struck upper T Subscript n comma m .

Theorem 3.2

If conditions (Equation3.1)–(Equation3.2) are satisfied, then each element of the cluster bold x left-parenthesis t Subscript head Baseline right-parenthesis is a Laurent polynomial in the cluster bold x left-parenthesis t Subscript tail Baseline right-parenthesis , with coefficients in the ring double-struck upper A .

We note that Theorem 3.2 is indeed a generalization of Theorem 3.1, for the following reasons:

double-struck upper T Subscript n comma m is naturally embedded into double-struck upper T Subscript n ;

conditions (Equation3.1)–(Equation3.2) are less restrictive than (Equation2.4)–(Equation2.7);

the claim being made in Theorem 3.2 about coefficients of the Laurent polynomials is stronger than that of Theorem 3.1, since double-struck upper A subset-of double-struck upper Z double-struck upper P .

Proof.

We start with some preparations. We shall write any Laurent polynomial upper L in the variables bold x equals StartSet x Subscript i Baseline colon i element-of upper I EndSet in the form

upper L left-parenthesis bold x right-parenthesis equals sigma-summation Underscript alpha element-of upper S Endscripts u Subscript alpha Baseline left-parenthesis upper L right-parenthesis x Superscript alpha Baseline comma

where all coefficients u Subscript alpha Baseline left-parenthesis upper L right-parenthesis are nonzero, upper S is a finite subset of the lattice double-struck upper Z Superscript upper I (i.e., the lattice of rank n with coordinates labeled by upper I ), and x Superscript alpha is the usual shorthand for product Underscript i Endscripts x Subscript i Superscript alpha Super Subscript i . The set upper S is called the support of upper L and denoted by upper S equals upper S left-parenthesis upper L right-parenthesis .

Notice that once we fix the collection script upper C , condition (Equation3.2) can be used as a recursive rule for computing script upper P left-parenthesis t prime right-parenthesis from script upper P left-parenthesis t right-parenthesis , for any edge t StartLayout 1st Row j 2nd Row minus minus right-arrow 3rd Row Blank EndLayout t prime on the spine. It follows that the whole pattern of exchange polynomials is determined by the families of polynomials script upper P left-parenthesis t Subscript base Baseline right-parenthesis and script upper C . Moreover, since these polynomials have coefficients in double-struck upper Z Subscript greater-than-or-equal-to 0 Baseline double-struck upper P , and the expression for upper R in (Equation3.2) does not involve subtraction, it follows that the support of any exchange polynomial is uniquely determined by the supports of the polynomials from script upper P left-parenthesis t Subscript base Baseline right-parenthesis and script upper C . Note that condition (Equation3.1) can be formulated as a set of restrictions on these supports. In particular, it requires that in the situation of (Equation3.2), the Laurent polynomial upper C does not depend on x Subscript i and is a polynomial in x Subscript j ; in other words, every alpha element-of upper S left-parenthesis upper C right-parenthesis should have alpha Subscript i Baseline equals 0 and alpha Subscript j Baseline greater-than-or-equal-to 0 .

We now fix a family of supports upper S left-parenthesis upper L right-parenthesis , for all upper L element-of script upper P left-parenthesis t Subscript base Baseline right-parenthesis union script upper C , and assume that this family complies with (Equation3.1). As is common in algebra, we shall view the coefficients u Subscript alpha Baseline left-parenthesis upper L right-parenthesis , for all upper L element-of script upper P left-parenthesis t Subscript base Baseline right-parenthesis union script upper C and alpha element-of upper S left-parenthesis upper L right-parenthesis , as indeterminates. Then all the coefficients in all exchange polynomials become “canonical” (i.e., independent of the choice of double-struck upper P ) polynomials in these indeterminates, with positive integer coefficients.

The above discussion shows that it suffices to prove our theorem in the following “universal coefficients” setup: let double-struck upper P be the free abelian group (written multiplicatively) with generators u Subscript alpha Baseline left-parenthesis upper L right-parenthesis , for all upper L element-of script upper P left-parenthesis t Subscript base Baseline right-parenthesis union script upper C and alpha element-of upper S left-parenthesis upper L right-parenthesis . Under this assumption, double-struck upper A is simply the integer polynomial ring in the indeterminates u Subscript alpha Baseline left-parenthesis upper L right-parenthesis .

Recall that we can view all cluster variables x Subscript i Baseline left-parenthesis t right-parenthesis as elements of the field script upper F left-parenthesis t Subscript tail Baseline right-parenthesis of rational functions in the cluster x left-parenthesis t Subscript tail Baseline right-parenthesis with coefficients in double-struck upper Z double-struck upper P . For t element-of double-struck upper T Subscript n comma m , let script upper L left-parenthesis t right-parenthesis denote the ring of Laurent polynomials in the cluster bold x left-parenthesis t right-parenthesis , with coefficients in double-struck upper A . We view each script upper L left-parenthesis t right-parenthesis as a subring of the ambient field script upper F left-parenthesis t Subscript tail Baseline right-parenthesis .

In this terminology, our goal is to show that the cluster bold x left-parenthesis t Subscript head Baseline right-parenthesis is contained in script upper L left-parenthesis t Subscript tail Baseline right-parenthesis . We proceed by induction on m , the size of the spine. The claim is trivial for m equals 1 , so let us assume that m greater-than-or-equal-to 2 , and furthermore assume that our statement is true for all “caterpillars” with smaller spine.

Let us abbreviate t 0 equals t Subscript tail and t 1 equals t Subscript base , and suppose that the path from t Subscript tail to t Subscript head starts with the following two edges: t 0 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row upper P EndLayout t 1 StartLayout 1st Row j 2nd Row minus minus right-arrow 3rd Row upper Q EndLayout t 2 . Let t 3 element-of double-struck upper T Subscript n comma m be the vertex such that t 2 StartLayout 1st Row i 2nd Row minus minus minus 3rd Row upper R EndLayout t 3 .

The following lemma plays a crucial role in our proof.

Lemma 3.3

The clusters bold x left-parenthesis t 1 right-parenthesis , bold x left-parenthesis t 2 right-parenthesis , and bold x left-parenthesis t 3 right-parenthesis are contained in script upper L left-parenthesis t 0 right-parenthesis . Furthermore, gcd left-parenthesis x Subscript i Baseline left-parenthesis t 3 right-parenthesis comma x Subscript i Baseline left-parenthesis t 1 right-parenthesis right-parenthesis equals gcd left-parenthesis x Subscript j Baseline left-parenthesis t 2 right-parenthesis comma x Subscript i Baseline left-parenthesis t 1 right-parenthesis right-parenthesis equals 1 left-parenthesis as elements of script upper L left-parenthesis t 0 right-parenthesis right-parenthesis .

Note that script upper L 0 equals script upper L left-parenthesis t 0 right-parenthesis is a unique factorization domain, so any two elements x comma y element-of script upper L 0 have a well-defined greatest common divisor gcd left-parenthesis x comma y right-parenthesis , which is an element of script upper L 0 defined up to a multiple from the group script upper L 0 Superscript times of units (that is, invertible elements) of script upper L 0 . In our “universal” situation, script upper L 0 Superscript times consists of Laurent monomials in the cluster bold x left-parenthesis t 0 right-parenthesis with coefficients plus-or-minus 1 .

Proof.

The only element from the clusters bold x left-parenthesis t 1 right-parenthesis , bold x left-parenthesis t 2 right-parenthesis , and bold x left-parenthesis t 3 right-parenthesis whose inclusion in script upper L 0 is not immediately obvious is x Subscript i Baseline left-parenthesis t 3 right-parenthesis . To simplify the notation, let us denote x equals x Subscript i Baseline left-parenthesis t 0 right-parenthesis , y equals x Subscript j Baseline left-parenthesis t 0 right-parenthesis equals x Subscript j Baseline left-parenthesis t 1 right-parenthesis , z equals x Subscript i Baseline left-parenthesis t 1 right-parenthesis equals x Subscript i Baseline left-parenthesis t 2 right-parenthesis , u equals x Subscript j Baseline left-parenthesis t 2 right-parenthesis equals x Subscript j Baseline left-parenthesis t 3 right-parenthesis , and v equals x Subscript i Baseline left-parenthesis t 3 right-parenthesis , so that these variables appear in the clusters at t 0 comma ellipsis comma t 3 , as shown below:

StartLayout 1st Row x comma y 2nd Row bullet 3rd Row t 0 EndLayout StartLayout 1st Row i 2nd Row minus minus minus minus minus minus minus 3rd Row upper P EndLayout StartLayout 1st Row y comma z 2nd Row bullet 3rd Row t 1 EndLayout StartLayout 1st Row j 2nd Row minus minus minus minus minus minus right-arrow 3rd Row upper Q EndLayout StartLayout 1st Row z comma u 2nd Row bullet 3rd Row t 2 EndLayout StartLayout 1st Row i 2nd Row minus minus minus minus minus minus minus 3rd Row upper R EndLayout StartLayout 1st Row u comma v 2nd Row bullet 3rd Row t 3 EndLayout period

Note that the variables x Subscript k , for k not-an-element-of StartSet i comma j EndSet , do not change as we move among the four clusters under consideration. The lemma is then restated as saying that

StartLayout 1st Row with Label left-parenthesis 3.3 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column v element-of script upper L 0 semicolon 2nd Row with Label left-parenthesis 3.4 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column gcd left-parenthesis z comma u right-parenthesis equals 1 left-parenthesis as elements of script upper L 0 right-parenthesis semicolon 3rd Row with Label left-parenthesis 3.5 right-parenthesis EndLabel 1st Column Blank 2nd Column Blank 3rd Column gcd left-parenthesis z comma v right-parenthesis equals 1 left-parenthesis as elements of script upper L 0 right-parenthesis period EndLayout

Another notational convention will be based on the fact that each of the polynomials upper P comma upper Q comma upper R has a distinguished variable on which it depends, namely x Subscript j for upper P and upper R , and x Subscript i for upper Q . (In view of (Equation3.1), upper P and upper R do not depend on x Subscript i , while upper Q does not depend on x Subscript j .) With this in mind, we will routinely write upper P , upper Q , and upper R as polynomials in one (distinguished) variable. In the same spirit, the notation upper Q prime , upper R prime , etc., will refer to the partial derivative with respect to the distinguished variable.

We will prove the statements (Equation3.3), (Equation3.4), and (Equation3.5) one by one, in this order.

By (Equation3.2), the polynomial upper R is given by

StartLayout 1st Row with Label left-parenthesis 3.6 right-parenthesis EndLabel upper R left-parenthesis u right-parenthesis equals upper C left-parenthesis u right-parenthesis upper P left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over u EndFraction right-parenthesis comma EndLayout

where upper C is an “honest” polynomial in u and a Laurent polynomial in the “mute” variables x Subscript k , k not-an-element-of StartSet i comma j EndSet . (Recall that upper C does not depend on x Subscript i .) We then have:

StartLayout 1st Row 1st Column Blank 2nd Column Blank 3rd Column z equals StartFraction upper P left-parenthesis y right-parenthesis Over x EndFraction semicolon 2nd Row 1st Column Blank 2nd Column Blank 3rd Column u equals StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction equals StartStartFraction upper Q left-parenthesis StartFraction upper P left-parenthesis y right-parenthesis Over x EndFraction right-parenthesis OverOver y EndEndFraction semicolon 3rd Row 1st Column Blank 2nd Column Blank 3rd Column v equals StartFraction upper R left-parenthesis u right-parenthesis Over z EndFraction equals StartStartFraction upper R left-parenthesis StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction right-parenthesis OverOver z EndEndFraction equals StartStartFraction upper R left-parenthesis StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction right-parenthesis minus upper R left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis OverOver z EndEndFraction plus StartStartFraction upper R left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis OverOver z EndEndFraction period EndLayout

Since

StartStartFraction upper R left-parenthesis StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction right-parenthesis minus upper R left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis OverOver z EndEndFraction element-of script upper L 0

and

StartStartFraction upper R left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis OverOver z EndEndFraction equals StartStartFraction upper C left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis upper P left-parenthesis y right-parenthesis OverOver z EndEndFraction equals upper C left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis x element-of script upper L 0 comma

(Equation3.3) follows.

We next prove (Equation3.4). We have

u equals StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction identical-to StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction mod z period

Since x and y are invertible in script upper L 0 , we conclude that gcd left-parenthesis z comma u right-parenthesis equals gcd left-parenthesis upper P left-parenthesis y right-parenthesis comma upper Q left-parenthesis 0 right-parenthesis right-parenthesis . Now the trouble that we took in passing to universal coefficients finally pays off: since upper P left-parenthesis y right-parenthesis and upper Q left-parenthesis 0 right-parenthesis are nonzero polynomials in the cluster bold x left-parenthesis t 0 right-parenthesis whose coefficients are distinct generators of the polynomial ring double-struck upper A , it follows that gcd left-parenthesis upper P left-parenthesis y right-parenthesis comma upper Q left-parenthesis 0 right-parenthesis right-parenthesis equals 1 , proving (Equation3.4).

It remains to prove (Equation3.5). Let

f left-parenthesis z right-parenthesis equals upper R left-parenthesis StartFraction upper Q left-parenthesis z right-parenthesis Over y EndFraction right-parenthesis period

Then

v equals StartFraction f left-parenthesis z right-parenthesis minus f left-parenthesis 0 right-parenthesis Over z EndFraction plus upper C left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis x period

Our goal is to show that gcd left-parenthesis z comma v right-parenthesis equals 1 ; to this end, we are going to compute v mod z as “explicitly” as possible. We have, mod z ,

StartFraction f left-parenthesis z right-parenthesis minus f left-parenthesis 0 right-parenthesis Over z EndFraction identical-to f prime left-parenthesis 0 right-parenthesis equals upper R prime left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis dot StartFraction upper Q prime left-parenthesis 0 right-parenthesis Over y EndFraction period

Hence

v identical-to upper R prime left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis dot StartFraction upper Q prime left-parenthesis 0 right-parenthesis Over y EndFraction plus upper C left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis x mod z period

Note that the right-hand side is a linear polynomial in x , whose coefficients are Laurent polynomials in the rest of the variables of the cluster bold x left-parenthesis t 0 right-parenthesis . Thus our claim will follow if we show that gcd left-parenthesis upper C left-parenthesis StartFraction upper Q left-parenthesis 0 right-parenthesis Over y EndFraction right-parenthesis comma upper P left-parenthesis y right-parenthesis right-parenthesis equals 1 . This, again, is a consequence of our “universal coefficients” setup since the coefficients of upper C , upper P and upper Q are distinct generators of the polynomial ring double-struck upper A .

We can now complete the proof of Theorem 3.2. We need to show that any variable x equals x Subscript k Baseline left-parenthesis t Subscript head Baseline right-parenthesis belongs to script upper L left-parenthesis t 0 right-parenthesis . Since both t 1 and t 3 are closer to t Subscript head than t 0 , we can use the inductive assumption to conclude that x belongs to both script upper L left-parenthesis t 1 right-parenthesis and script upper L left-parenthesis t 3 right-parenthesis . Since x element-of script upper L left-parenthesis t 1 right-parenthesis , it follows from (Equation2.1) that x can be written as x equals f slash x Subscript i Baseline left-parenthesis t 1 right-parenthesis Superscript a for some f element-of script upper L left-parenthesis t 0 right-parenthesis and a element-of double-struck upper Z Subscript greater-than-or-equal-to 0 . On the other hand, since x element-of script upper L left-parenthesis t 3 right-parenthesis , it follows from (Equation2.1) and from the inclusion x Subscript i Baseline left-parenthesis t 3 right-parenthesis element-of script upper L left-parenthesis t 0 right-parenthesis guaranteed by Lemma 3.3 that x has the form x equals g slash x Subscript j Baseline left-parenthesis t 2 right-parenthesis Superscript b Baseline x Subscript i Baseline left-parenthesis t 3 right-parenthesis Superscript c for some g element-of script upper L left-parenthesis t 0 right-parenthesis and some b comma c element-of double-struck upper Z Subscript greater-than-or-equal-to 0 Baseline . The inclusion x element-of script upper L left-parenthesis t 0 right-parenthesis now follows from the fact that, by the last statement in Lemma 3.3, the denominators in the two obtained expressions for x are coprime in script upper L left-parenthesis t 0 right-parenthesis .

Several examples that can be viewed as applications of Theorem 3.2 are given in Reference8.

4. Exchange relations: The exponents

Let script upper M equals left-parenthesis upper M Subscript j Baseline left-parenthesis t right-parenthesis right-parenthesis colon t element-of double-struck upper T Subscript n Baseline comma j element-of upper I right-parenthesis be an exchange pattern (see Definition 2.1). In this section we will ignore the coefficients in the monomials upper M Subscript j Baseline left-parenthesis t right-parenthesis and take a closer look at the dynamics of their exponents. (An alternative point of view that the reader may find helpful is to assume that all exchange patterns considered in this section will have all their coefficients p Subscript j Baseline left-parenthesis t right-parenthesis equal to 1 .) For every edge t StartLayout 1st Row j 2nd Row minus minus minus 3rd Row Blank EndLayout t prime in double-struck upper T Subscript n , let us write the ratio upper M Subscript j Baseline left-parenthesis t right-parenthesis slash upper M Subscript j Baseline left-parenthesis t prime right-parenthesis of the corresponding monomials as

StartLayout 1st Row with Label left-parenthesis 4.1 right-parenthesis EndLabel StartFraction upper M Subscript j Baseline left-parenthesis t right-parenthesis Over upper M Subscript j Baseline left-parenthesis t Superscript prime Baseline right-parenthesis EndFraction equals StartFraction p Subscript j Baseline left-parenthesis t right-parenthesis Over p Subscript j Baseline left-parenthesis t Superscript prime Baseline right-parenthesis EndFraction product Underscript i Endscripts x Subscript i Superscript b Super Subscript i j Superscript left-parenthesis t right-parenthesis Baseline comma EndLayout

where b Subscript i j Baseline left-parenthesis t right-parenthesis element-of double-struck upper Z (cf. (Equation2.3)); we note that ratios of this kind have already appeared in (Equation2.7). Let us denote by upper B left-parenthesis t right-parenthesis equals left-parenthesis b Subscript i j Baseline left-parenthesis t right-parenthesis right-parenthesis the n times n integer matrix whose entries are the exponents in (Equation4.1). In view of (Equation2.5), the exponents in upper M Subscript j Baseline left-parenthesis t right-parenthesis and upper M Subscript j Baseline left-parenthesis t prime right-parenthesis are recovered from upper B left-parenthesis t right-parenthesis :

StartLayout 1st Row with Label left-parenthesis 4.2 right-parenthesis EndLabel StartLayout 1st Row 1st Column upper M Subscript j Baseline left-parenthesis t right-parenthesis 2nd Column equals 3rd Column p Subscript j Baseline left-parenthesis t right-parenthesis product Underscript i colon b Subscript i j Baseline left-parenthesis t right-parenthesis greater-than 0 Endscripts x Subscript i Superscript b Super Subscript i j Superscript left-parenthesis t right-parenthesis Baseline comma 2nd Row 1st Column upper M Subscript j Baseline left-parenthesis t prime right-parenthesis 2nd Column equals 3rd Column p Subscript j Baseline left-parenthesis t prime right-parenthesis product Underscript i colon b Subscript i j Baseline left-parenthesis t right-parenthesis less-than 0 Endscripts x Subscript i Superscript minus b Super Subscript i j Superscript left-parenthesis t right-parenthesis Baseline period EndLayout EndLayout

Thus, the family of matrices left-parenthesis upper B left-parenthesis t right-parenthesis right-parenthesis Subscript t element-of double-struck upper T Sub Subscript n encodes all the exponents in all monomials of an exchange pattern.

We shall describe the conditions on the family of matrices left-parenthesis upper B left-parenthesis t right-parenthesis right-parenthesis imposed by the axioms of an exchange pattern. To do this, we need some preparation.

Definition 4.1

A square integer matrix upper B equals left-parenthesis b Subscript i j Baseline right-parenthesis is called sign-skew-symmetric if, for any i and j , either b Subscript i j Baseline equals b Subscript j i Baseline equals 0 , or else b Subscript i j and b Subscript j i are of opposite sign; in particular, b Subscript i i Baseline equals 0 for all i .

Definition 4.2

Let upper B equals left-parenthesis b Subscript i j Baseline right-parenthesis and upper B prime equals left-parenthesis b prime Subscript i j right-parenthesis be square integer matrices of the same size. We say that upper B prime is obtained from upper B by the matrix mutation in direction k and write upper B prime equals mu Subscript k Baseline left-parenthesis upper B right-parenthesis if

StartLayout 1st Row with Label left-parenthesis 4.3 right-parenthesis EndLabel b prime Subscript i j Baseline equals StartLayout Enlarged left-brace 1st Row 1st Column minus b Subscript i j Baseline 2nd Column if i equals k or j equals k semicolon 2nd Row 1st Column b Subscript i j Baseline plus StartFraction StartAbsoluteValue b Subscript i k Baseline EndAbsoluteValue b Subscript k j Baseline plus b Subscript i k Baseline StartAbsoluteValue b Subscript k j Baseline EndAbsoluteValue Over 2 EndFraction 2nd Column otherwise period EndLayout EndLayout

An immediate check shows that mu Subscript k is involutive, i.e., its square is the identity transformation.

Proposition 4.3

A family of n times n integer matrices left-parenthesis upper B left-parenthesis t right-parenthesis right-parenthesis Subscript t element-of double-struck upper T Sub Subscript n corresponds to an exchange pattern if and only if the following conditions hold:

(1) upper B left-parenthesis t right-parenthesis is sign-skew-symmetric for any t element-of double-struck upper T Subscript n .

(2) If t StartLayout 1st Row k 2nd Row minus minus minus 3rd Row Blank EndLayout t prime , then upper B left-parenthesis t prime right-parenthesis equals mu Subscript k Baseline left-parenthesis upper B left-parenthesis t right-parenthesis right-parenthesis .

Proof.

We start with the “only if” part, i.e., we assume that the matrices upper B left-parenthesis t right-parenthesis are determined by an exchange pattern via (Equation4.1) and check the conditions (1)–(2). The condition b Subscript j j Baseline left-parenthesis t right-parenthesis equals 0 follows from (Equation2.4). The remaining part of (1) (dealing with i not-equals j ), follows at once from (Equation2.6). Turning to part (2), the equality b prime Subscript i k Baseline equals minus b Subscript i k is immediate from the definition (Equation4.1). Now suppose that j not-equals k . In this case, we apply the axiom (Equation2.7) to the edge t StartLayout 1st Row k 2nd Row minus minus minus 3rd Row Blank EndLayout t prime taken together with the two adjacent edges emanating from t and t prime and labeled by j . Taking (Equation4.2) into account, we obtain:

StartLayout 1st Row with Label left-parenthesis 4.4 right-parenthesis EndLabel product Underscript i Endscripts x Subscript i Superscript b prime Super Subscript i j Baseline equals product Underscript i Endscripts x Subscript i Superscript b Super Subscript i j Superscript Baseline vertical-bar Subscript x Sub Subscript k Subscript left-arrow upper M slash x Sub Subscript k Subscript Baseline comma EndLayout

where upper M equals product Underscript i colon b Subscript i k Baseline b Subscript j k Baseline less-than 0 Endscripts x Subscript i Superscript StartAbsoluteValue b Super Subscript i k Superscript EndAbsoluteValue . Comparing the exponents of x Subscript k on both sides of (Equation4.4) yields b prime Subscript k j Baseline equals minus b Subscript k j . Finally, if i not-equals k , then comparing the exponents of x Subscript i on both sides of (Equation4.4) gives

b prime Subscript i j Baseline equals StartLayout Enlarged left-brace 1st Row 1st Column b Subscript i j Baseline 2nd Column if b Subscript i k Baseline b Subscript j k Baseline greater-than-or-equal-to 0 semicolon 2nd Row 1st Column b Subscript i j Baseline plus StartAbsoluteValue b Subscript i k Baseline EndAbsoluteValue b Subscript k j Baseline 2nd Column otherwise period EndLayout

To complete the proof of (2), it remains to notice that, in view of the already proven part (1), the condition b Subscript i k Baseline b Subscript j k Baseline greater-than-or-equal-to 0 is equivalent to b Subscript i k Baseline b Subscript k j Baseline less-than-or-equal-to 0 , which makes the last formula equivalent to (Equation4.3).

To prove the “if” part, it suffices to show that if the matrices upper B left-parenthesis t right-parenthesis satisfy (1)–(2), then the monomials upper M Subscript j Baseline left-parenthesis t right-parenthesis given by the first equality in (Equation4.2) (with p Subscript j Baseline left-parenthesis t right-parenthesis equals 1 ) satisfy the axioms of an exchange pattern. This is done by a direct check.

Since all matrix mutations are involutive, any choice of an initial vertex t 0 element-of double-struck upper T Subscript n and an arbitrary n times n integer matrix upper B gives rise to a unique family of integer matrices upper B left-parenthesis t right-parenthesis satisfying condition (2) in Proposition 4.3 and such that upper B left-parenthesis t 0 right-parenthesis equals upper B . Thus, the exponents in all monomials upper M Subscript j Baseline left-parenthesis t right-parenthesis are uniquely determined by a single matrix upper B equals upper B left-parenthesis t 0 right-parenthesis . By Proposition 4.3, in order to determine an exchange pattern, upper B must be such that all matrices obtained from it by a sequence of matrix mutations are sign-skew-symmetric. Verifying that a given matrix upper B has this property seems to be quite nontrivial in general. Fortunately, there is another restriction on upper B that is much easier to check, which implies the desired property, and still leaves us with a large class of matrices sufficient for most applications.

Definition 4.4

A square integer matrix upper B equals left-parenthesis b Subscript i j Baseline right-parenthesis is called skew-symmetrizable if there exists a diagonal skew-symmetrizing matrix upper D with positive integer diagonal entries d Subscript i such that upper D upper B is skew-symmetric, i.e., d Subscript i Baseline b Subscript i j Baseline equals minus d Subscript j Baseline b Subscript j i for all i and j .

Proposition 4.5

For every choice of a vertex t 0 element-of double-struck upper T Subscript n and a skew-symmetrizable matrix upper B , there exists a unique family of matrices left-parenthesis upper B left-parenthesis t right-parenthesis right-parenthesis Subscript t element-of double-struck upper T Sub Subscript n associated with an exchange pattern on double-struck upper T Subscript n and such that upper B left-parenthesis t 0 right-parenthesis equals upper B . Furthermore, all the matrices upper B left-parenthesis t right-parenthesis are skew-symmetrizable, sharing the same skew-symmetrizing matrix.

Proof.

The proof follows at once from the following two observations:

1. Every skew-symmetrizable matrix upper B is sign-skew-symmetric.

2. If upper B is skew-symmetrizable and upper B prime equals mu Subscript k Baseline left-parenthesis upper B right-parenthesis , then upper B prime is also skew-symmetrizable, with the same skew-symmetrizing matrix.

We call an exchange pattern—and the corresponding cluster algebra—skew-symmetrizable if all the matrices upper B left-parenthesis t right-parenthesis given by (Equation4.1) (equivalently, one of them) are skew-symmetrizable. In particular, all cluster algebras of rank n less-than-or-equal-to 2 are skew-symmetrizable: for n equals 1 we have upper B left-parenthesis t right-parenthesis identical-to left-parenthesis 0 right-parenthesis , while for n equals 2 , the calculations in Example 2.5 show that one can take

StartLayout 1st Row with Label left-parenthesis 4.5 right-parenthesis EndLabel upper B left-parenthesis t Subscript m Baseline right-parenthesis equals left-parenthesis negative 1 right-parenthesis Superscript m Baseline Start 2 By 2 Matrix 1st Row 1st Column 0 2nd Column b 2nd Row 1st Column negative c 2nd Column 0 EndMatrix EndLayout

for all m element-of double-struck upper Z , in the notation of (Equation2.10)–(Equation2.11).

Remark 4.6

Skew-symmetrizable matrices are closely related to symmetrizable (generalized) Cartan matrices appearing in the theory of Kac-Moody algebras. More generally, to every sign-skew-symmetric matrix upper B equals left-parenthesis b Subscript i j Baseline right-parenthesis we can associate a generalized Cartan matrix upper A equals upper A left-parenthesis upper B right-parenthesis equals left-parenthesis a Subscript i j Baseline right-parenthesis of the same size by setting

StartLayout 1st Row with Label left-parenthesis 4.6 right-parenthesis EndLabel a Subscript i j Baseline equals StartLayout Enlarged left-brace 1st Row 1st Column 2 2nd Column if i equals j semicolon 2nd Row 1st Column minus StartAbsoluteValue b Subscript i j Baseline EndAbsoluteValue 2nd Column if i not-equals j period EndLayout EndLayout

There seem to be deep connections between the cluster algebra corresponding to