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.