GROVES AND THE CUBE RECURRENCE
This is a preliminary write-up by Gabriel Carroll and David Speyer,
with some editing and additional explanatory passages by Jim Propp;
it is based on emails sent out by Gabriel and David, dated 5/5 through
5/12.
1. Overview
The following memo is a summary of work done in May 2002. This work
concerns multivariate rational functions f(i,j,k) given by the initial
conditions
f(i,j,k) = x(i,j,k) (for i+j+k = -1, 0, or 1)
(where the x(i,j,k)'s are formal indeterminates) and by the recurrence
relation
f(i,j,k) = [f(i-1,j,k)f(i,j-1,k-1) + f(i,j-1,k)f(i-1,j,k-1) +
f(i,j,k-1)f(i-1,j-1,k)] / f(i-1,j-1,k-1) (for i+j+k > 1).
This is called the cube recurrence, since it gives an algebraic relation
between the values taken by the function f(.,.,.) at eight lattice sites
that form the vertices of a cube. (Motivation for the study of this
recurrence comes from the analogous but simpler relation that is obtained
when the cube is replaced by an octahedron; the resulting recurrence
relation, called the discrete Hirota equation, arises in many combinatorial
contexts, though frequently disguised.)
It was shown by Fomin and Zelevinsky that the rational functions f(i,j,k)
are actually Laurent polynomials in the variables x(i,j,k) (|i+j+k| < 2).
Here we show (as conjectured by Propp) that all coefficients in these
Laurent polynomials are equal to +1. We do this by establishing a
bijection between the Laurent monomials that occur in f(i,j,k) and
combinatorial objects that we call groves; specifically, the terms of
f(i,j,k) correspond to the groves of order i+j+k. By replacing all
the variables x(i,j,k) by 1, we can conclude that G(n), the number of
groves of order n, satisfies the recurrence relation
G(n) = 3 G(n-1) G(n-2) / G(n-3) ,
which (combined with the initial conditions G(-1) = G(0) = G(1) = 1)
implies G(n) = 3^{floor(n^2/4)}.
It is easily seen that for any pair of triples (i,j,k), (i',j',k')
with i+j+k = i'+j'+k', the rational function f(i',j',k') can be
obtained from the rational function f(i,j,k) by a simple substitution
in which each variable x(r,s,t) gets replaced by the variable
x(r+i'-i,s+j'-j,t+k'-k), so without loss of generality, we will
focus henceforth on the case f(n,0,0).
We intend to defer writing a completely formal treatment until we have
at least a picture of how the same recurrence works with general initial
conditions (e.g., slabs of the form 0 <= pi+qj+rk < p+q+r for positive
constants p, q, r). In the meantime, if anyone finds mistakes or unclear
statements in the following proofs, please inform Gabriel (FAS username:
gcarroll).
2. Defining groves
Groves of order n are defined as follows: Begin with a triangular lattice
with n+1 vertices on a side, and label the boundary vertices so that two
vertices receive the same label iff they are exchanged by a reflection
through a median of the triangle passing through the vertex of the triangle
closest to either of them:
a
/ \
b---b
/ \ / \
c---*---e
/ \ / \ / \
d---c---e---f
When n is even, the central vertices of the three sides all receive the
same label:
a
/ \
b---b
/ \ / \
c---*---c
/ \ / \ / \
d---*---*---e
/ \ / \ / \ / \
f---d---c---e---g
Groves are forests contained in this graph such that each tree contains
precisely the lettered vertices of one letter, and every tree contains at
least one lettered vertex. For example,
a
b---b
c---* c
\ /
d---* * e
\ / /
f d c e g
is a grove of order 4. (This example shows that lettered vertices need
not be leaves, and that leaves need not be lettered vertices.)
The number of distinct letters used is (3n+2)/2 when n is even and
(3n+3)/2 when n is odd. Hence the number of trees in a grove of order
n (including three trivial trees with no edges, whose sole respective
vertices are the three corner vertices) is floor((3n+3)/2).
Fix some grove of order n. If we take the number of vertices in each
tree, and sum over all the trees, we get the total number of vertices,
which is (n+1)(n+2)/2. If we take the number of edges in each tree,
and sum over all the trees, on the one hand we get
(n+1)(n+2)/2 - floor((3n+3)/2)
(because each tree now contributes 1 less to the sum, and the number
of trees is floor((3n+3)/2)), and on the other hand we get the number
of edges in the grove. Hence the number of edges in a grove of order
n is (n^2+3n+2)/2 - floor((3n+3)/2) = ceiling((n^2-1)/2) = floor(n^2/2).
3. From groves to Laurent monomials
Groves can be identified with Laurent monomials in the variables x(i,j,k)
as follows. To get the exponents of the variables x(i,j,k) with i+j+k=0,
draw them in the trangular grid in the natural way.
(0, 0, 0)
(1,-1, 0)---(1, 0,-1)
(2,-2, 0)---(2,-1,-1) (2, 0,-2)
\ /
\ /
\ /
(3,-3, 0)---(3,-2,-1) (3,-1,-2) (3, 0,-3)
\ / /
\ / /
\ / /
(4,-4, 0) (4,-3,-1) (4,-2,-2) (4,-1,-3) (4, 0,-4)
For the nonlettered vertices, the exponent is (# of incident edges)-2,
which in general can be anything between 1-2 = -1 and 6-2 = 4. For the
lettered vertices other than the three corners (that is, for b, c, d and
e), the exponent is (# of incident edges)-1, which is always either
1-1 = 0 or 2-1 = 1. For the corners (that is, for a, f and g), the
exponent can be written as (# of incident edges)-0 but is always just 0.
Thus, we get the exponents
0
0 ----- 0
0 ----- 0 0
\ /
\ /
\ /
1 ----- -1 1 0
\ / /
\ / /
\ / /
0 0 0 0 0
So the contribution from the x(i,j,k)'s with i+j+k=0 is
1 -1 1
x(3,-3, 0) x(3,-2,-1) x(3,-1,-2) .
Now, we have to get the exponents of the f(i,j,k) with i+j+k=+/- 1.
These we write in the faces of the triangular grid. There is no way
we can do ASCII art large enough to show this really well, but we'll
draw the two types of triangles that occur and the labels they receive.
(i-1,j,k) (i,j,k+1)------(i,j+1,k)
/ \ \ /
/ \ \ (i,j,k) /
/ \ \ /
/ (i,j,k) \ \ /
/ \ \ /
(i,j-1,k)------(i,j,k-1) (i+1,j,k)
(Note that the coordinate-triple assigned to an upward-pointing triangle
is the componentwise maximum of the coordinate-triples assigned to the
three vertices of the triangle; likewise, the coordinate-triple assigned
to a downward-pointing triangle is the componentwise minimum of the
coordinate-triples assigned to the three vertices. In both cases,
the x-coordinate of the center of a triangle is equal to the x-coordinates
of two of its three vertices, and likewise for the y- and z-coordinates.)
The exponent of a triangle is 1-(# of adjacent edges used) (even if it is
on the boundary). Thus, our example gives rise to the exponent-array
*
0
*-----*
0
0 1
*-----* *
0 \-1 /
0 0 \ / 0
*-----* * *
\-1 0 / 0 /
0 \ 1 / 0 / 0
* * * * *
yielding a contribution of
1 -1 -1
x(2,0,-1) x(2,-1,-2) x(3,-3,-1) x(4,-2,-1)
from these variables.
Putting it all together, we can associate with the grove the array
0
0
0 0
0
0 1
0 0 0
0 -1
0 0 0
1 -1 1 0
-1 0 0
0 1 0 0
0 0 0 0 0
and represent this array by the monomial
1 -1 1
x(3,-3, 0) x(3,-2,-1) x(3,-1,-2) times
1 -1 -1
x(2,0,-1) x(2,-1,-2) x(3,-3,-1) x(4,-2,-1)
which, sure enough, occurs in f(4,0,0).
We will show that the grove can be reconstructed from its monomial,
and that each cube-recurrence Laurent polynomial f(i,j,k) is the sum
of all monomials corresponding to groves of order i+j+k.
4. From Laurent monomials to groves
To convert back from a monomial to a grove, write the exponents of the
monomial inside the "star of David" graph, shown below. This graph is
the mediant graph of the triangular lattice in which our groves embed
(modulo some extra vertices on the boundary); its vertices correspond
to edges of groves, its hexagonal faces correspond to vertices of
groves, and its triangular faces correspond to triangles in the grove
lattice. We illustrate the conversion with our previous example, here
using "-" to signify -1, "+" to signify +1, and " " to signify 0.
*---*
/ \
* *
\ /
*---*---*---*
/ \ / \
* * *
\ / \ /
*---*---*---*---*---*
/ \ / \+/ \
* * * *
\ / \ /-\ /
*---*---*---*---*---*---*---*
/ \ / \ / \ / \
* + * - * + * *
\ /-\ / \ / \ /
*---*---*---*---*---*---*---*---*---*
/ \ / \+/ \ / \ / \
* * * * * *
\ / \ / \ / \ / \ /
*---* *---*---*---*---*---* *---*
For any vertex of the star of David graph, draw the four rays extending
from it, as shown in the two pictures below. The sums of the numbers
in the four wedges will either be 1, -1, 1 and 0 in cyclic order (as in
the first picture) or 0, 0, 0 and 1 (as in the second picture). In the
former case we draw the edge corresponding to this vertex; in the latter
case we do not.
* *
* *
\
* * * *
\
* * *
\
* * * * * *
\1
* * * *
-1\
*---*---*---*---*---*---*---*
\
* 1 * -1 * 1 * *
-1 \
* * * * * * * * * *
1 \
* * * * * *
\
* * * * * * * * * *
* *
* *
* * * *
* * *
\
* * * * * *
\ 1
* * * *
\ -1
*---*---*---*---*---*---*---*
\
* 1 * -1 * 1 * *
-1 \
* * * * * * * * * *
1 \
* * * * * *
\
* * * * * * * * * *
5. Shuffling groves
Shuffling is an operation that turns order-n groves into order-(n+1) groves.
The basic idea is that we turn upward-pointing triangles in an order-n grove
into downward-pointing triangles in an order-(n+1) grove. To see how this
happens, let's first superimpose the vertex grids of the two groves:
+
*
+ +
* *
+ + +
* * *
+ + + +
* * * *
+ + + + +
* * * * *
+ + + + + +
Here the *'s are vertices of the smaller grid, and the +'s are vertices
of the larger grid. We can see that the upward-pointing triangles of *'s
are concentric with the downward-pointing triangles of +'s.
Now suppose we have a grove on the * grid. For ASCIIgraphic purposes, we
will mark edges according to the grid they come from; hopefully this won't
be confusing.
+
*
+ +
*********
+ + +
* * *
* * *
+ * + * + * +
* * *
* ********* *
* * *
+ * + * + + * +
* * *
* * * * *
+ + + + + +
The algorithm is as follows: First we mark each up-pointing * triangle
with 0, 1, or 2, according to the number of edges it has.
+
*
+ 1 +
*********
+ 0 + 0 +
* * *
* * *
+ 1 * + 2 * + * 1 +
* * *
* ********* *
* * *
+ 1 * + 1 * + 0 + * 1 +
* * *
* * * * *
+ + + + + +
Next we "switch" the up-pointing * triangles: If an up * triangle has 2
edges, remove both of them; if it has 1 edge, leave it alone; if it has 0
edges, add two edges arbitrarily.
+
*
+ 1 +
*********
* *
+ 0 * + 0 * +
* *
*****************
* *
+ 1 * + 2 + * 1 +
* *
* * * *
* * * *
+ 1 * + 1 * + * 0 + * 1 +
* * * *
* * ********* *
+ + + + + +
Finally, we "shift" every horizontal edge up, shift every \-shaped edge
down and left, and shift every /-shaped edge down and right. Thus, each
edge of an up * triangle is turned into a parallel edge of the
corresponding down + triangle. If the following drawing is unclear, the
reader is encouraged to work through the example on paper.
+
*
+++++++++
* *
+++++++++++++++++
+ +
* + * + *
+ +
+ + + +
+ +
* + * * + *
+ +
+ + +++++++++ +
+ + + +
* + * + * + * + *
+ + + +
+ + + + + +
We obtain in this fashion a grove of order n+1.
Note that this is not a bijection, and indeed not even a function;
a grove of order n can be shuffled into any of 3^m different groves
of order n+1, where m is the number of up * triangles with no edges
present in the grove.
A different way to conceptualize the shuffling procedure is to swap
the two steps, so that shifting occurs first and switching occurs after
(this time using down + triangles instead of up * triangles). The order
of the two steps does not matter, since each star of David is completely
self-contained in both of the two steps and has no interaction with other
stars of David.
It is also possible to apply shuffling in reverse, starting from a grove
of order n+1 and producing from it a (usually non-unique) grove of order
n, either by doing a shift followed by a switch on the up * triangles,
or by doing a switch on the down + triangles followed by a shift. One
need not worry about situations like
+
+ +
\
+ + +
+ + + +
+ + + + +
+ + + + + +
(in which an edge does not belong to a star of David in the superimposed
graph) because the rules governing groves do not permit such edges in
the first place.
6. Why shuffling works
The claim is if we appy shuffling to a grove of order n (on the * grid),
we obtain a grove of order n+1 (on the + grid). In proving this, we
will also study the relationship between the monomial associated with
the two groves, since this will play a role in later sections.
If an initial * (upward) triangle has one edge, the corresponding + triangle
will have one edge, in the same orientation, produced by shifting the given
* edge. If our * triangle has two edges, the corresponding + triangle will
have no edges. If our * triangle has no edges, the corresponding + triangle
will have two edges (randomly assigned). Translating this into exponent
terms, this tells us that each up-triangle exponents in the * graph is the
negative of the corresponding down-triangle exponent in the + graph, since a
triangle's exponent is 1 minus (# of edges used).
This actually has two important consequences:
(a) The * edges and + edges _never intersect_. In fact, from looking at the
graphs, we can see that any possible intersection would have to involve a
* edge and a + edge on corresponding triangles. The nature of the shuffling
algorithm guarantees that this won't happen: for any two corresponding
triangles, either the * triangle has two edges and the + triangle has none,
or vice versa, or each triangle has one edge; but in the last case, the two
edges used are parallel and so don't intersect.
Here for instance is what we get when we superimpose the pre-shuffle and
post-shuffle edges from our example:
+
*
+++++++++
*********
+++++++++++++++++
+ +
* + * + *
* + * + *
+ * + * + * +
+ * * * +
* + ********* + *
* + * + *
+ * + * +++++++++ * +
+ * + * + * +
* + * + * + * + *
+ + + +
+ + + + + +
(b) The total number of + edges used is forced. The number of edges in
the grove of order n can be written as 0a+1b+2c, where a, b, c denote the
number of up * triangles with 0, 1, or 2 edges present, respectively.
Then the number of + edges present after shuffling must be 2a+1b+0c.
But
2a+1b+0c = 2(a+b+c) - (0a+1b+2c),
where a+b+c (the total number of up * triangles) is forced, and 0a+1b+2c
(the total number of edges in the * grove) is forced. Indeed, we have
a+b+c = n(n+1)/2 and 0a+1b+2c = floor(n^2/2), so
2a+1b+0c = 2n(n+1)/2 - floor(n^2/2)
= ceiling(2n(n+1)/2 - n^2/2)
= ceiling((n^2+2n)/2)
= floor((n^2+2n+1)/2)
= floor((n+1)^2/2),
which is the number of edges in a grove of order n+1.
The number of trees in a forest equals the number of vertices minus the
number of edges, so if we can show that the + graph is acyclic (i.e., a
forest), then the fact that it has the correct number of trees will
follow directly from the fact that it has the correct number of vertices
and the correct number of edges.
However, observation (a) shows that the + graph is acyclic. Indeed, we can
check that any possible cycle (except for the trivial cycle made of a single
downward-pointing triangle, which can never occur) would have to contain at
least one * vertex in its interior. Because + edges never cross * edges,
the + cycle would then contain an entire * component. But each * component
touches two of the three boundary-components of the * grid, so the + cycle
cannot contain such a component without using boundary edges of the + grid.
Since our algorithm never uses these boundary edges, acyclicity follows.
The number of + components then follows as well.
Now for the coup de grace: Let's draw rays coming out of the boundary
vertices of the * grid.
*** + ***
*** ***
***
*** ***
*** + + ***
*** ***
** **
*** ***
*** + + + ***
*** ***
** * **
*** + + + + ***
*** ***
** * * **
+ + + + +
*** ***
** * * * **
* * * * *
+ * + * + * + * + * +
* * * * *
* * * * *
* * * * *
When we insert the * grove graph, the plane is divided into "sectors" by
virtue of the way that the boundary * vertices are connected by the trees.
*** + ***
*** ***
***
*** ***
*** + + ***
*** ***
***********
*** ***
*** + + + ***
*** ***
** * **
* * *
*** + * + * + * + ***
*** * * * ***
** ********* **
* * *
+ * + * + + * +
*** * * * ***
** * * * **
* * * * *
+ * + * + * + * + * +
* * * * *
* * * * *
* * * * *
By lemma (a) and the fact that the + boundary edges are never used, we
conclude that each + component is contained inside one sector. However,
it is not hard to check that we have floor((3n+6)/2) sectors - exactly
the number of components of the + graph. Therefore, each sector contains
precisely the vertices of one component of the + graph. It is now a
straightforward induction to show that the boundary vertices are matched
up in the desired manner: if the order-n grove has the property that two
boundary vertices are in the same tree iff they have the same label, then
it follows that two boundary vertices of the order-(n+1) grid lie in the
same sector iff they have the same label, and we just saw that being in
the same sector is equivalent to being in the same + tree. (The induction
step actually has two cases, depending on the parity of n, but both are
straightforward).
At this point, we've shown that the + graph is acyclic, that it has the
correct number of components, and that the boundary vertices are properly
matched - in other words, it is a grove.
Reverse shuffling works much the same way.
So we can conclude that every order-n grove shuffles into order-(n+1)
groves and, conversely, every order-(n+1) grove is obtained by a shuffle
from order-n groves. In other words, the set of objects produced by the
shuffling algorithm is the same as the set of groves, for any given order.
7. Extension to the plane
Given any grove of order n, we can extend it to a forest on the entire
plane by adding some edges. Here we have the edges to be added:
* * * * * *---*---*---*
\ \ \ \ \
* * * * *---*---*---*---*
\ \ \ \
* * * * *---*---*---*---*
\ \ \ \
* * * * *---*---*---*---*
\ \ \
* * * * * *---*---*---*
\ \ \
* * * * * *---*---*---*
\ \
* * * * * * *---*---*
\ \
* * * * * * *---*---*
/ / / / / / /
* * * * * * * *---*
/ / / / / / /
* * * * * * * *---*
/ / / / / / / /
* * * * * * * * *
Of course, this pattern continues outward to infinity. In case it's not
clear from the picture, the procedure is simply to extend each side of the
triangle to a ray in one direction, thus dividing the exterior of the
triangle into three regions, and then to fill each region with edges that
are all of the same orientation.
The central triangle is where you fill in the edges of your grove (in the
example above, of order 5). It's straightforward to check that we can now
set the exponent of any triangle to be 1 - (# of surrounding edges) and the
exponent of any * to be (# of edges) - 2. We get the same values as before
for all the exponents (and those that lie outside the triangle are all zero).
It's also straightforward to check that if we shuffle an extended order-n
grove, the result is an extended order-(n+1) grove.
This extension will make subsequent computations a bit easier, since we
don't have to worry about special stuff happening on the boundary. It's
analogous to a procedure used in EKLP: to shuffle a domino tiling of the
Aztec diamond, we first extend the tiling to the entire plane by using
horizontals.
8. Shuffling and monomials
So now let's show how shuffling groves is equivalent to a change of variables
in the grove-counting polynomials. From here on we will assume that groves
are extended to the whole plane as described in the previous section, so we
don't need to worry about boundaries, and we're still assured that only
finitely many exponents are nonzero for any given grove.
To keep the initial conditions typographically distinct in a helpful way,
we'll write the initial conditions as
x(i,j,k) for i + j + k = 1 (the up-pointing triangles)
y(i,j,k) for i + j + k = 0 (the vertices of the grove)
z(i,j,k) for i + j + k = -1 (the down-pointing triangles)
So we denote the grove-counting polynomial at (I,J,K), which is a Laurent
polynomial in infinitely many variables (although only finitely many of them
actually appear), as
f(I,J,K) = P_I,J,K ({x(i,j,k)},{y(i,j,k)},{z(i,j,k)})
Notice that lowercase letters index all the formal variables, and uppercase
letters index the particular polynomial in question.
We want to show that
f(I+1,J,K) = P_I,J,K (
{ ( x(i,j,k)y(i+1,j-1,k-1) +
x(i+1,j-1,k)y(i,j,k-1) +
x(i+1,j,k-1)y(i,j-1,k) ) / z(i,j-1,k-1) },
{x(i+1,j,k)},
{y(i+1,j,k)} ).
Because the cube-recurrence polynomials satisfy this same recurrence
(you get this by treating the planes i+j+k = 0, 1, 2 as your initial
conditions instead of -1, 0, 1), and it's straightforward to check that
they agree for the initial cases, this will prove that the cube-recurrence
polynomials and the grove-counting polynomials coincide.
So let's look at the process of shuffling groves. Recall that it operates
as follows:
- First "switch" the up triangles: if an up triangle has two edges,
remove them; if it has no edges, add two arbitrarily.
- Then, "shift" every edge of every up triangle to the parallel edge
of the corresponding down triangle, e.g.
* *
+ \ + + +
\ --> \
* * * \ *
+ +
(*'s are the vertices of the order-n grove, and +'s are the vertices of the
order-(n+1) grove, as before.)
Let's see what each of these steps does to the grove polynomial. In the
process, we'll work through an example. Pretend that the following groves
have been extended to the entire plane as described in the previous section.
* 0
0
*-----* 0 0
0
1 0
* *-----* 0 -1 1
\ / 0 -1
\ / 0 1 0
* * * * 0 0 0 0
Switching can produce the following (or any of eight other possibilities):
* 0
0 0
0
*-----* 1 0
/ -1 0 0
/ -1 0
*-----*-----* 2 1 1
\ \ / 0 -1 -2 0
\ \ / 0 -1 0
* *-----* * 0 1 2 0
0 -1 0
Notice that we are using the same rules as before to turn a graph into a
monomial, even though the graph is not a grove at this stage. Also notice
that we may temporarily have a nonzero exponent outside of our triangular
grid, but since we're actually working with infinite grids, this isn't a
problem. (The -1's outside the triangle come in part from the edges of the
extension, which are not shown here.)
When we do the shift, we get:
+ 0
0
+-----+ 0 0
0
0 0
+-----+-----+ 0 1 0
/ -1 0
/ 1 -1 1
+ +-----+ + 0 1 -1 0
\ \ / 0 -1 0
\ \ / 0 0 1 0
+ + + + + 0 0 0 0 0
It should be noted that there is a somewhat arbitrary choice in the
correspondence between the vertices of the order-n grid and those of
the order-(n+1) grid; we have effectively made this choice by choosing
to compare P_I,J,K with P_I+1,J,K (as opposed to, say, P_I,J+1,K).
How do we express the new exponents in terms of the old ones?
First, let's deal with the switching step. If an up triangle has exponent 1
(no edges), we can replace it by any of the following three configurations:
* * *
/ / \ \
/ / \ \
*-----* * * *-----*
These correspond to changing the 1 to a -1 and performing the following net
changes on the six neighboring exponents:
1 2 1
-1 / 0 -1 / \-1 0 \-1
/ / \ \
2-----1 1 1 1-----2
-1 0 -1
It can be checked in the example above that the switched order-3 grove
monomial is obtained from the original by two operations of this sort.
So if a monomial in P_I,J,K has a variable x(i,j,k) with exponent 1, it
gets effectively replaced by the trinomial
B(i,j,k) =
y(i-1,j,k)^2 y(i,j-1,k) y(i,j,k-1) / z(i-1,j-1,k) z(i-1,j,k-1) x(i,j,k) +
y(i-1,j,k) y(i,j-1,k)^2 y(i,j,k-1) / z(i-1,j-1,k) z(i,j-1,k-1) x(i,j,k) +
y(i-1,j,k) y(i,j-1,k) y(i,j,k-1)^2 / z(i,j-1,k-1) z(i-1,j,k-1) x(i,j,k).
We claim that the same substitution describes the effect of a switch on up
triangles with exponent -1. Indeed, if a up triangle has exponent -1 in
P_I,J,K, then we have one of the three two-edge configurations above. We
claim that the monomials obtained by replacing this configuration with either
of the other two also occur in P_I,J,K. To see this, notice that the claim
is equivalent to the assertion if an up triangle has two edges used, we may
replace them by either other pair of edges and still obtain a valid grove.
But this is easy to see.
Therefore, the polynomial consisting of those monomials in P_I,J,K where
x(i,j,k) has exponent -1 is actually divisible (in the Laurent polynomial ring)
by the same trinomial B(i,j,k) as above. Moreover, we can write B(i,j,k) =
C(i,j,k)/x(i,j,k), where C(i,j,k) is a trinomial independent of the variable
x(i,j,k). In particular, the substitution x(i,j,k) <- B(i,j,k) is an
involution, so applying the switch move to a triangle of exponent -1 (which
should entail dividing by B(i,j,k) and multiplying by x(i,j,k)) is
represented by this substitution.
Finally, if an up-triangle has exponent 0 (one edge used), it will not be
affected by the substitution, which is exactly what we want from the switching
step. Thus, if we let Q_I,J,K({x(i,j,k)},{y(i,j,k)},{z(i,j,k)}) denote the
polynomial which counts switched (but not yet shifted) groves, we have shown
that Q_I,J,K is equal to P_I,J,K({B(i,j,k)},{y(i,j,k)},{z(i,j,k)}).
Now let's deal with the shifting step. The new down triangles have the same
exponents as the corresponding up triangles. For the + vertices we have the
following picture:
*
a f + +
a f f a
* * f a
b e ----> +ccccc+ddddd+
b e b e
*ccccc*ddddd* b e
+ +
where each distinct lowercase letter denotes an edge that may be present or
absent. If we denote the exponents in the picture on the left (order n) by
uppercase letters as follows:
*
A
* *
X
B C
* * *
then the number of edges used from {a,b,c,d,e,f} is (1-A) + (1-B) + (1-C) -
(1-X) = X - (A+B+C) + 2. Therefore, the exponent of the central * (in order
n+1) is X-(A+B+C).
For the up triangles, we have the following picture:
* *
a c +
a c a c
* * * ----> a c
+bbbbb+
*bbbbb*
If we again label the three up triangles' and the central vertex's exponents
by uppercase letters:
* *
A C
* X *
B
* *
then the number of edges used from among {a,b,c} is (1-A)+(1-B)+(1-C)-(X+2) =
1-(A+B+C+X). Therefore, the exponent of the resulting up triangle (in order
n+1) is A+B+C+X.
Now, for each exponent in the order-n picture, let's see which order-(n+1)
exponents it contributes to. If an old up triangle had exponent X, then it
contributes X to the corresponding new down triangle exponent and the three
neighboring up triangle exponents, and -X to the three neighboring vertices
(in the order-(n+1) picture).
The other order-n exponents contribute only to the corresponding order-(n+1)
exponents. That is, a down triangle of exponent X in order n contributes X
to the exponent of the corresponding vertex in order n+1 (and it doesn't
contribute to any other exponents), and a vertex of exponent X in order n
contributes X to the exponent of the corresponding up triangle in order n+1
(and it doesn't contribute to anything else). All of this can be verified
in the example shown above - if we take each nonzero exponent in the
post-switch order-3 grove, record its contributions to the nearby exponents
in the order-4 graph according to the rules just stated, and add, we do get
the same values that were observed above.
Let's write these rules down algebraically. After performing the shift move
on the already-switched order-n groves, we get the order-(n+1) groves, which
are counted by P_I+1,J,K. Therefore,
P_I+1,J,K ({x(i,j,k)},{y(i,j,k)},{z(i,j,k)})
= Q_I,J,K ({ z(i,j-1,k-1)x(i,j,k)x(i+1,j-1,k)x(i+1,j,k-1) /
y(i+1,j-1,k-1)y(i,j-1,k)y(i,j,k-1) },
{ x(i+1,j,k) },
{ y(i+1,j,k) } )
= P_I,J,K ({ ( x(i,j,k)y(i+1,j-1,k-1) +
x(i+1,j-1,k)y(i,j,k-1) +
x(i+1,j,k-1)y(i,j-1,k) ) / z(i,j-1,k-1) },
{x(i+1,j,k)},
{y(i+1,j,k)} )
where the second equality comes from our earlier expression for Q_I,J,K.
And we're done.