Minutes from REACH Meeting, February 26, 2002, 3-5 PM (Gabriel D. Carroll, with some assistance from Gregg Musiker) - Stathis will take notes on Thursday. - Private REACH websites: anyone with a personal site should make a personal REACH subdirectory (it's allowed to be publicly accessible if you want, but of course there should be no public links to the general private site). This way we can offer each other big files without crowding mailboxes. Email Jim the URL for your page; he will put links to everyone's pages on the general site. Nobody currently has a personal REACH site, so do it now. - Jim still needs to update the site with Maple code for Laurent polynomials. He is still reading emails from last fall. Also wants some meeting time to be spent talking about the articles we've read. - Gregg is trying to understand cluster algebras - is working on writing up a "cookbook" of proofs of Laurentness which will be sent to the group. Trying to practice e.g. by seeing what happens with Somos 8 (where Laurentness fails). - Jason is working on cluster algebras - working through Fomin's paper as well as Zelevinsky's paper connecting representation theory with cluster algebras. - Gabriel is working on Problem 7 (the two-dimensional recurrence obtained by specializing Dodgson condensation to the Toeplitz case). He is looking for relatively "literal" combinatorial interpretations of the exponents in the monomials that appear as terms in the Laurent polynomials produced by this recurrence. - Roberto is studying the readings; he has also proven that every homogeneous linear recurrence can be seen as counting matchings of a suitable family of graphs. He is finding quadratic recurrences inside these sequences as well. - Dan is looking for a combinatorial interpretation of Somos-3, via integrality. He and Roberto together have been looking at cases of quadratic recurrences that can be broken down into linear ones. - Jim comments on relevance to dimensional reduction: since any one-dimensional combinatorial quantity can grow at most exponentially, it is clear that objects enumerated by faster-growing sequences (e.g. Somos sequences) must be of dimension at least two. But we can specialize into lower-dimensional cases, e.g. the Dodgson-Aztec connection can be specialized to a one-dimensional version that counts 2 x 2n domino tilings. Can we reason similarly with (e.g.) Somos-3? It would be nice to see when quadratic recurrences which break down into linear ones can be viewed as "vestiges" of more complex quadratic recurrences. - David is playing with cluster algebras (since Monday's talk) and will work on the cookbook with Gregg. He is looking at the following problem: . . . .O.O.O. .O.O. .O. . If this represents a fragment of a two-dimensional array, where the O's represent given values a_ij(where the indexing is by axes that are tilted by 45 degrees, not horizontal and vertical) and we require the numbers at the four adjacent dots to have determinant equal to the O between them, can the dots' values be expressed as polynomials in the O's? Cluster algebra machinery works here only when a_ij = b_i * c_j for some fixed sequences b_i, c_j. Also, David would be willing to explain the domino-shuffling material in EKLP. (Jim has written another, more elaborate paper that uses domino shuffling; you can find this on the web at http://front.math.ucdavis.edu/math.CO/0111034.) - Jim comments: he doesn't know of ways to use edge variables to obtain genuine (not Laurent) polynomials in 4-term recurrences, even though there are extensive conjectures for 3-term recurrences. Jim also reminds that he will paraphrase Robbins and Rumsey's work in terms of Aztec diamonds and Laurentness if asked to do so (maybe even if not asked). - Jim also reminds us that we should avoid working too much on cluster algebras, since we want combinatorial approaches to our problems, not algebraic ones - but cluster algebras are a useful tool for showing that Laurentness actually occurs; this way we can pursue combinatorial proofs without fearing that the things we want to prove are false. - Roberto asks whether there are interesting pairs of families of graphs that generate the same matching numbers. Jim responds that this can often be proven uninstructively by noticing that two such sequences have the same initial values and satisfy the same recurrence. Also, there are "local moves" that can be applied to individual graphs to change the numbers of matchings in predictable ways, e.g. choose a vertex and double every edge coming out of it, so as to double the total number of matchings. - Gabriel asks about higher-dimensional analogues of the cube recurrence. Jim answers that the obvious possibilities have been tried and don't seem to give Laurent polynomials, though they could actually be Laurent in variables other than the obvious ones (e.g. Laurent with respect to binomial functions of these variables). Apropos of this, he notes that Elkies sees recurrences obtained from theta functions as emerging from geometric structures rather than being defining properties in themselves. Also, in higher dimensions, according to Elkies, the values obtained from these recurrences allow only finitely many degrees of freedom, so that the statistical-mechanical model of having lots of variables to fiddle with breaks down. However, we shouldn't focus on this for now. - In passing, Jim also comments that, under suitable algebraic dependency conditions, Somos-8 actually does produce Laurent polynomials in the initial terms (David Cantor has worked on this). In particular, the initial terms can be chosen to be integers such that the denominators of all subsequent terms are divisible only by a fixed finite set of possible prime factors. It is not known whether there are nontrivial all-integer sequences satisfying the Somos-8 recurrence. [Note: When checking into this later, Jim found that Cantor's example involves a modified Somos-8 recurrence in which the terms have constant coefficients that are not equal to 1.] - Gregg talks about one way of proving Laurentness: Assume we have a sequence defined by the recurrence x_n * x_(n-k-1) = P(x_(n-1), ..., x-(n-k)), where P is a polynomial. Let R be the ring of Laurent polynomials in x_1, ..., x_k, with integer coefficients. Suppose that there are 2k+2 consectutive terms of the sequence lie in R. It can then be shown that the whole sequence is in R. This can be obtained by cluster algebras. Gregg is working on a way to explain the intution behind Fomin and Zelevinsky's proof without going into all of the details . We would like to know what nice conditions on P, in turn, cause the first 2k+2 terms to be in R. (The following example will make more sense after reading about Cluster Algebras and comparing this proof with David's example of how to prove Laurentness of the same sequence.) Gregg's example: Let x_n*x_(n-3) = x_(n-1)*x_(n-2) + 1, so k = 3. Then clearly x_1, ..., x_6 are in R, so we just need to show x_7 is; equivalently, that x_5*x_6 + 1 is divisible by x_4 in the ring R. Rewrite it as x_5*(x_5*x_4 + 1)/x_3 + 1, so we want to prove x_5*(x_5*x_4 + 1)/x_3 + 1 == x_5*(0 + 1)/x_3 + 1 == 0 modulo x_4. This requires an assumption that we can divide through by x_3 (which implies a condition that consectutive x_i's should be relatively prime). Assuming that we've dealt with the condition of relatively prime. (Fomin and Zelevinsky have a condition that deals with this), then We multiply through by x_3 and get x_5 + x_3 (This polynomial comes from the same process that gets us "P = x_2 + x_3" using the Caterpillar lemma.) x_5 + x_3 == (x_4*x_3 + 1)/x_2 + x_3 + 1 == (1 + x_3*x_2)/x_2 modulo x_4 But by the defining recurrence, (1 + x_3*x_2) == x_4*x_1 == 0 modulo x_4. So we're done. This gives some intuition behind how the Cluster Algebras Method can prove Laurentness. One still has to deal with the important question raised about whether it is valid to divide through by terms like x_4. However, these are details that Gregg hasn't worked out yet, though Fomin and Zelevinsky's proof do contain these details. The Cluster Algebra method gives a more general theory for recurrences like this, rather than doing these computations for each recurrence separately. David says Fomin and Zelevinsky seem to have some general strategies. - Something is wrong with Problem 3, from the draft project list. Jim will look into this. - The remainder of the meeting is spent discussing cluster algebras, based on yesterday's talk. (Jim will soon post a link to suitable articles). There is some debate over the correct definitions. Gregg offers this definition: Fix a unique factorization domain and a positive integer n. A "cluster" is an ordered n-tuple of elements of the domain. Now suppose, for 1 <= i <= n, we have polynomials P_i in variables x_1, ..., x_(i-1), x_(i+1), ..., x_n. Suppose we have a bunch of clusters with the following property: Whenever X = (x_1, ..., x_n) is a cluster, and there exist i, x' such that x_i * x' = P_i(x_1, ..., x_(i-1), x_(i+1), ..., x_n), then we can replace x_i by x' to obtain another cluster. Such a collection is a "cluster algebra." Note: Fomin and Zelevinsky's original formulation of cluster algebra requires the exchange polynomials to be binomials. However, if one makes other axioms stricter one can allow exchange polynomials with an arbitrary number of terms and prove Laurentness for associated sequences. We can build a graph on a cluster algebra - let each vertex be a cluster, and draw an edge between clusters linked by such an exchange as above; label the edge it with the index i exchanged and the corresponding P_i for that vertex. We don't need directed graphs - these exchanges are involutions (as long as we don't get into sticky stuff with P_i's values being zero). We can use this to describe sequences given by one-dimensional recurrences. Example: take s_m = (s_(m-1)^2 + 1)/s_(m-2), so P_1(x) = P_2(x) = x^2 + 1. We have the graph O ----- O ----- O ----- O --- ... P_1 P_2 P_1 where the vertices (from left to right) are labeled (s_(m-1), s_m), (s_(m+1), s_m), (s_(m+1), s_(m+2)), (s_(m+3), s_(m+2)), .... Thus, each cluster is like a "window" on the sequence thatshows just enough terms to apply the recurrence and get a new term. David basically uses Fomin / Zelevinsky's definition of a cluster algebra: we don't have to have just one polynomial associated to each i. Thus, given any cluster, there exist n other clusters adjacent to it, one for each value of i; for any two adjacent clusters, there exists some polynomial P (depending on the clusters) such that one cluster (x_1, ..., x_n) is turned into the other by replacing x_i by P(x_1, ..., x_(i-1), x_(i+1), ..., x_n)/x_i (and vice versa) - and this quotient must exist. David presents the "caterpillar lemma": consider a subgraph of a cluster algebra of the form O -->-- O -->-- O -->-- O -->-- O (in this drawing n = 4; there may be / \ / \ / \ more "legs" from each "spine" vertex) / \ / \ / \ O O O O O O with arrows along the "spine" from the "tail" to the "head." If certain conditions are met, it follows that the entries in the head cluster are Laurent polynomials in the entries in the tail cluster. For applications, we normally are given the spine polynomials and want to choose polynomials on the legs to meet these conditions. The main condition is a formula when we have successive edges of the form: i j i O ----- O -->-- O ----- O P Q R In general, let Q_0 be the polynomial obtained from Q by setting x_i = 0. The condition is that L * Q_0^b * P = R(x_1, ..., x_(j-1), Q_0(x_1,...,x_n)/x_j, x_(j+1), ..., x_n), where b is a nonnegative integer, L a laurent monomial coprime to P. Given the additional constraint that P, Q_0 should be relatively prime, this determines P uniquely in terms of Q, R. Example: David shows Laurentness for Gregg's sequence, s_m*s_(m+3) = s_(m+1)*s_(m+2) + 1. Here n = 3: O -->-- O -->-- O -->-- O -->-- O 1 | 2 | 3 | 1 | 3 | 1 | 2 | | | O O O Here the labels for the spine vertices are (s_1, s_2, s_3), (s_4, s_2, s_3), (s_4, s_5, s_3), etc. Also, the polynomials for the spine edges, in order, are x_2*x_3 + 1, x_1*x_3 + 1, x_1*x_2 + 1, x_2*x_3 + 1. This caterpillar actually can get arbitrarily long, but we can do two reductions to turn it into the above: by periodicity, it suffices to show that we can assign polynomials to the legs above to make our condition hold; also, by homogeneity (i.e. cyclic symmetry of the polynomials) it suffices to assign a polynomial just to the i = 1 leg. Look first at the 1-3-1 path on the right; we have i = 1, j = 3, R = x_2*x_3 + 1, Q = x_1*x_2 + 1, so Q_0 = 1, and then R(x_1, x_2, Q_0/x_3) = x_2/x_3 + 1, so P = x_2 + x_3. Now we can apply the same reasoning to the left 1-2-1 path to get a polynomial label for the leftmost 1 edge; we hope it turns out to be the same label (x_2*x_3 + 1) we have already assigned. Miraculously, it is, so the conditions for the caterpillar lemma hold, and Laurentness follows. This is basically the technique described in Fomin's talk. Cluster Algebras are still a developing theory, and there are many recurrences that have not been analyzed and proven to be Laurent using this method.