Gabriel D. Carroll - REACH, Spring 2003 Thoughts on the graph recurrence as of 2/24/03 The original problem was to find a combinatorial interpretation of the (a,b) recurrence: s_(n+1) = (s_n^a + 1)/s_(n-1) for n odd, s_(n+1) = (s_n^b + 1)/s_(n-1) for n even, where a and b are fixed positive integers. It was shown via cluster algebras that every s_n is a Laurent polynomial in the initial variables s_0, s_-1. We would like to understand why this is the case. Jim's expectation (and mine as well) is that we will need to find a "lifting" of the recurrence - a more general recurrence in multiple variables that collapses to the above when many of the variables are identified with each other. After some experimentation with various potential liftings, trying to determine which do and which do not give Laurent polynomials, it appeared to me that the correct structure to by which to index the polynomials would not be an integer lattice (as we had used for the octahedron and cube recurrences) but rather a more general graph. Specifically, I propose the following: Conjecture: Let G be a graph (possibly infinite), and for every vertex v of G and every integer n, define f_(v,n) = x_v (a formal variable) if n <= 0, f_(v,n) = (prod(w) f_(w,n-1) + 1) / f_(v,n-2) if n > 0, where the product is taken over all neighbors w of v. Then each f_(v,n) is a Laurent polynomial in the variables x_v. How does this lift the (a,b) recurrence? Let G be a bipartite graph with parts X, Y, where every vertex in X has degree a and every vertex in Y has degree b. Let x_v = s_0 for v in X, s_-1 for v in Y; then we get f(v,n) = s_n if n is even and v is in X, or n is odd and v is in Y. In particular, there is a "canonical lifting" as follows: there is an (infinite) tree T in which the vertices have degrees a and b alternately; any bipartite graph G as above can then be represented as a quotient of T. Thus, if the conjecture holds for T, it holds for G. (More generally, to prove the whole conjecture, it suffices to prove it for trees, since any graph - indeed, any multigraph - can be represented as a suitable quotient of a tree; details of the proof are left to the reader. Note also that it suffices to prove the conjecture for finite trees, since each f_(v,n) only cares about finitely many vertices.) For the sake of easy reference, I'll call this tree T the "free graph with degrees (a,b)" - drawing inspiration from the fact that the Cayley graphs of free groups are among such trees. For all I know, other names may already exist. Notice that T is infinite as long as a, b >= 2. For a or b = 1, then, the lifting of the (a,b) sequence is not very exciting; it's still in some sense "one-dimensional." However, this process of lifting seems fairly canonical, so I'm less optimistic about finding more interesting liftings for the a = 1 case. Admittedly, the (1,4) sequence was one of our main objects of investigation, so this might be somewhat disappointing. On the other hand, this whole graph-indexing framework seems like a very powerful way to investigate many new recurrences. Note that, in the above conjecture, it's safe to have the formal variables x_v = f_(v,n) depend only on v, not on n, if we're working with trees. That's because no f_(v,n) for n > 0 uses any initial variable with n < -1, and bipartiteness ensures that we won't use f_(v,0) and f_(v,-1) for the same v in any given polynomial. So we don't really lose any information by assuming f_(v,0) = f_(v,-1). However, this will no longer be true if we consider the following strengthened version of the above conjecture: Conjecture: Let G be a graph (possibly infinite), and let r be a nonnegative integer. For every vertex v of G and every integer n, define f_(v,n) = x_v (a formal variable) if n <= 0, f_(v,n) = (prod(w) f_(w,n-1) + f_(v,n-1)^r) / f_(v,n-2) if n > 0, where the product is taken over all neighbors w of v. Then each f_(v,n) is a Laurent polynomial in the variables x_v. The experiments I have conducted so far suggest that the second conjecture is in fact true. It hopefully should be provable by means of cluster algebras; if anyone has read through Gregg Musiker's thesis and is looking for a place to try out the machinery, this seems like a good target. (I certainly hope this result is new - I don't recall seeing it done in Fomin and Zelevinsky's paper, but I should probably check back there just in case.) Meanwhile, there are still further generalizations to be tried out, either empirically or rigorously. It's easy to see that, to some extent, we can raise the various f_(w,n-1)'s to higher powers - for example, if v and w are adjacent, we can raise f_(w,n-1) to the power s in the formula for f(v,n) and vice versa simultaneously; this simply means that we're using a multigraph, where the edge v-w has multiplicity s. However, this exponentiation stuff probably has to be done symmetrically. I tried running the above recurrence with the various f_(w,n-1)'s raised to random positive integer powers, all independent of each other (and of n), and Laurentness did not survive. A somewhat tamer experiment would be: Experiment: Does the above conjecture appear to remain valid when f_(w,n-1) is raised to some power r_(v,w) - depending on v, w (but constant across all n), where r_(v,w) does not necessarily equal r_(w,v)? [Addendum, 4/5: The conjecture does not remain valid, even if r(v,w) depends only on v. Thus, symmetry seems to be required.] In a similar vein: Experiment: Does the conjecture appear to remain valid when r depends on v? What if it depends on n? Or on both? [Addendum, 4/5: This also seems to be false - r depending purely on v destroys Laurentness, and r = n also destroys Laurentness in general. If I recall correctly, though, there are some special cases in which r = n does retain the Laurent property.] A question that was raised earlier also warrants investigating: Experiment: Does the conjecture remain valid when f_(v,0) and f_(v,-1) are distinct? (Note that once we introduce the f(v,n-1)^r term, we can no longer collapse these two variables using the bipartiteness trick.) [Addendum, 4/5: This seems to remain true, although I didn't experiment very extensively.] Assuming the graph recurrence does have the Laurent property, the obvious question is what the appropriate combinatorial interpretation is. In some sense, it seems like there shouldn't be any further lifting possible - the free-graph framework (or trees in general) will already use as many different variables as the recurrence allows, unless we stick in extra variables as coefficients somehow. However, empirically, the terms of the polynomials still don't all have coefficient 1, so if they do enumerate some nice combinatorial objects, they don't seem to do so in a bijective manner. This is pretty puzzling. However, I'm tempted to try to go ahead and look for combinatorial interpretations in spite of this obstacle. How to go about looking for combinatorial interpretations? There are several different possibilities, none of which I've really pursued as of yet. One is to treat the known interpretations of (say) the frieze-pattern and number-wall recurrences as special cases - which, after all, they are, with G being simply an infinite path - and try to generalize them. Another possibility is to try to do what we did with the cube recurrence: pick some subregions of the tree, and see if the sums of exponents of those subregions can take on only a few possible values across all monomials in a given polynomial. (Example of a subregion to try: for fixed vertices u, v, such a subregion might consist of all vertices w such that the path from u to w goes through v.) I'm not terribly optimistic about how this will work, but it requires sufficiently little thought that I'm going to write it as an experiment: Experiment: For a fixed graph, consider the terms in some large polynomial f_(v,n). Are there interesting sets of vertices of the graph such that the sum of the exponents of the corresponding variables can take on only a few possible values as we explore all monomials in the given f_(v,n)? It's not really clear what sorts of sets of vertices to try, though. In investigating the cube recurrence, we took inspiration from the embedding of the Somos-3-initial octahedron recurrence (whose regions were known) into the cube recurrence with standard initials. It might be nice if we could similarly interpret the cube or octahedron recurrence as a special case of a graph-indexed recurrence; this would give us a starting point in terms of regions to look at. Unfortunately, the most obvious way to try this doesn't work: Ex-experiment: For any word w in the free group with generators a, b, define f_(w,n) = x_w for n <= 0, otherwise (f_(wa,n-1)f_(wa^-1,n-1) + f_(wb,n-1)f_(wb^-1,n-1)) / f_(w,n-2). Is f_(w,n) Laurent in general? Note that this would lift the octahedron recurrence to the free graph with degrees (4,4) (i.e. the Cayley graph of the group). Sadly, Laurentness fails utterly. I haven't tried the analogous extension of the cube recurrence to the (6,6)-free graph, but I'm pretty sure that won't work either. This does raise interesting questions, though, as to what graph-indexed recurrences have the Laurentness property and what ones don't. That would be yet another possible line of empirical investigation - find Laurent recurrences on graphs that aren't generalizations or specializations of the aforementioned ones. Another idea I had in looking for combinatorial interpretations was to try varying the initial conditions: along the lines of the octahedron and cube initial conditions, instead of simply saying f_(v,n) is initial when n <= 0, we can set f_(v,n) = x_v when n <= h(v), where h is some function differing by at most 1 between neighboring vertices. Thus: Experiment: Does the conjecture still seem true when the initial conditions are given by f_(v,n) = x_v for n <= h(v), for various different functions h? [Addendum, 4/5: Yes, both conjectures still seem to be true for suitable functions h, and it also appears - though I have not experimented extensively - that the second conjecture remains true when the initial conditions f(v,n) = x_(v,n) depend on n as well as on v.] If so, then we would at least have a technique for proving a combinatorial interpretation for these polynomials - show that it is preserved when h is varied at one point (the local-move method). However, it seems doubtful that this could lead to the discovery of such an interpretation without some great external source of insight. That's pretty much where I stand on all this stuff right now. I'll plan on working on some of these experiments and continuing to look for other approaches to this problem, and I'll update this file periodically in accordance with any innovations. My main goal right now is to find a combinatorial interpretation for at least the first version of the graph recurrence (assuming it does have the Laurent property). True, the (a,b) recurrence is such a hugely special case that the interpretation for the graph recurrence might not translate into anything simple for the (a,b) recurrence, but that's to be dealt with later, I think. And even if the latter fear is confirmed, understanding the graph recurrence still seems like a pretty exciting prospect. If you're working on any of this stuff, or if you'd like to see the Mathematica work I've done so far (which basically consists of trying out various recurrences and seeing whether or not they produce Laurent polynomials, and computing the polynomials in a couple of very special cases), let me know at gcarroll at fas.harvard.edu . Until quagga o'clock, - GDC 4/5/03 An update: I've tried out some of the quantitative experiments suggested earlier. I've added my findings in the relevant spots in the above pontifications. 4/24/03 I sent the initial conjecture to the bilinear forum, and both Sabin Cautis and David Speyer quickly pointed out that the Laurentness conjecture is true - even with arbitrary initial conditions - by a straightforward, elementary divisibility argument. However, David said there doesn't seem to be any analogous argument in the version where the 1 is replaced by f(v,n-1)^r, so this may require a caterpillar-type proof. Still, it looks like just a matter of actually sitting down and writing out the proof - no inspiration needed. I also made some initial attempt at introducing edge-variables, by including a variable e[v] with either the prod(f(w,n-1)) term or the 1 term of the recurrence. Neither alteration of the recurrence remained Laurent, but presumably I'm just introducing these variables in the wrong way. David also made an intriguing suggestion: for two graphs G and H, define f(v,w,n), with v a vertex of G and w a vertex of H, to be an initial variable when n <= 0, and otherwise f(v,w,n) = (prod(f(v',w,n-1)) + prod(f(v,w',n-1)))/f(v,w,n-2) where the products have v' ranging over the neighbors of v and w' ranging over the neighbors of w. This generalizes the above recurrence (even with the f(v,n-1)^r term: G is the same graph as before, and H has a single vertex and r loops), and it also generalizes the octahedron recurrence (G and H are both infinite paths). In the computational experiments I have performed so far with small random graphs, these functions do indeed continue being Laurent polynomials, even with arbitrary initial conditions. (Initial conditions are specified by a function on the vertex set of GxH, meeting the same smoothness and termination conditions as before.) The fact that this new recurrence generalizes the octahedron recurrence, as well as, say, the (a,b)-recurrence, strongly suggests a model in terms of matchings (cf. Gregg Musiker's work for a matchings model of the (1,4)-recurrence, and the (2,2) antifrieze recurrence is already understood in terms of matchings). Such a model might be found using an extension of the urban-renewal approach used to prove crosses and wrenches, though I wasn't immediately able to find an urban renewal move that applies to faces of a graph with more than 4 edges, and I expect these graphs generally will not be planar anyway. I will look at Gregg's work, which involves graphs with octagonal faces, to see if it provides inspiration here. Meanwhile, the analogy with the octahedron recurrence also suggests a possible way to introduce edge variables. I'll see if this leads anywhere.