Research Experiences in Algebraic Combinatorics at Harvard: A Dozen Laurent Recurrences

Here are a dozen Maple programs that implement rational recurrences in one, two or three dimensions. In each case other than #11, the intent is that you should type f(n) (or f(n,0) or f(n,0,0), as needed) for various small values of n and observe that the output in each case is a Laurent polynomial; that is, when it is written as a rational function, the denominator is just a product. In some cases, the output is a bona fide polynomial (i.e., there is no denominator).

In all cases, one can use the cluster algebra machinery of Fomin and Zelevinsky (see Sergei Fomin and A. Zelevinsky's article The Laurent phenomenon) to prove the "Laurentness" of the outputs for all values of n. (See also Fomin and Zelevinsky's Cluster algebras I: Foundations and Zelevinsky's From Littlewood-Richardson coefficients to cluster algebras in three lectures.)

What was desired in each case is an alternative proof using combinatorial methods. Such a proof doesn't merely prove Laurentness of a rational function; it gives detailed information about the structure of the function.

At the start of the semester, such proofs were known only for cases 1, 3, 4, and 5. As of mid-April, the students succeeded in finding combinatorial interpretations for recurrences 6, 8, 9, 10, and 11.

1. THE "DIAMOND PATTERN" OR "ANTIFRIEZE PATTERN" RECURRENCE 

f := proc(n,k) option remember; 
        if n<-1 then undefined;
        elif n<1 then x(n,k);
        else simplify( (f(n-1,k-1)*f(n-1,k+1)+1)/f(n-2,k) ); fi; end;

When we write f(n,0) as a Laurent polynomial, the sum of the coefficients of the Laurent monomials goes like 1, 2, 5, 13, ... (every other Fibonacci number). Moreover, each of these coefficients is equal to 1, so the alternating Fibonacci numbers also give the number of terms of f(n,0). Indeed, there is a natural bijection between the monomials that occur in f(n,0) and domino-tilings of a 2-by-2n rectangle, or equivalently, in matchings of the grid-graph 
o---o---o---o---o---o
|   |   |   |   |   |
o---o---o---o---o---o
with vertices arranged in 2 rows and 2n columns.

Also, if one replaces the term 1 in the numerator of the recurrence by the term -1, one gets a recurrence (governing arrays called "frieze patterns") that have been studied by others. There are links with formulas for determinants of tridiagonal matrices and continued fractions.

You can learn more about this from my Math 192 lectures (11/29, 12/4, 12/11, and 12/13) and homework problems (1.2, 3.2, and 19.2, plus all of assignment 17). Note that videos of lectures and solutions to homework problems and other course-related materials are all available at the site www.math.harvard.edu/~propp/192/. Also note that "problem 1.2" means problem 2 from assignment 1. Finally, note that the solutions to the problem sets are available as .ps and .tex files as well as .pdf files.)

2. THE NUMBER WALL RECURRENCE 

f := proc(n,k) option remember;
        if n<-1 then undefined;
        elif n<1 then x(n,k);
        else simplify( (f(n-1,k)^2 + f(n-1,k-1)*f(n-1,k+1))/f(n-2,k) ); fi; end;

This is the recurrence for "generalized number walls". A pleasant write-up of "walls" and "windows" appears in "The Book of Numbers" by John Conway and Richard Guy; a more comprehensive treatment appears in a monograph by Fred Lunnon:

jamespropp.org/somos/walls.ps
It should be mentioned that in this case (unlike the case we saw above with Fibonacci numbers), no ones knows a formula for the number of terms.

3. ROBBINS-RUMSEY CONDENSATION (with "face-variables") 

f := proc(n,i,j) option remember;
        if n<-1 then undefined;
        elif n<1 then x(n,i,j);
        else simplify( (f(n-1,i-1,j)*f(n-1,i+1,j)+f(n-1,i,j-1)*f(n-1,i,j+1))
                /f(n-2,i,j) ); fi; end;

This famous recurrence (invented by Robbins and Rumsey) is almost the same as the even more famous Dodgson recurrence for computing determinants of matrices by condensation (the only difference is that the minus sign in Dodgson condensation becomes a plus sign). The Math 192 students were challenged to work on this recurrence in homework problem 20.2. You can find out more at

jamespropp.org/bilinear/domino
In particular, you'll learn that the terms of these Laurent polynomials are in bijective correspondence with domino tilings of Aztec diamonds, or, equivalently, perfect matchings of the dual graphs, as shown below: 
        o---o
        |   |
    o---o---o---o
    |   |   |   |
o---o---o---o---o---o
|   |   |   |   |   |
o---o---o---o---o---o
    |   |   |   |
    o---o---o---o
        |   |
        o---o

It's worth noting that antifrieze patterns and number walls are both special cases of Robbins-Rumsey condensation; for an explanation of this, see

jamespropp.org/somos/dodgson

4. KUO CONDENSATION (with "edge-variables") 

f := proc(n,i,j) option remember;
        if n<-1 then undefined;
        elif n<1 then 1;
        else simplify( 
  ( y(i+2*n-1,j+2*n-1)*y(i-2*n+1,j-2*n+1)*f(n-1,i-2,j+2)*f(n-1,i+2,j-2)
  + y(i-2*n+1,j+2*n-1)*y(i+2*n-1,j-2*n+1)*f(n-1,i+2,j+2)*f(n-1,i-2,j-2))
 / f(n-2,i,j) ); fi; end;

These polynomials have an even clearer relationship to the combinatorial model of matchings-of-the-Aztec-diamond-graph than the Laurent polynomials of the preceding example. For more on Kuo condensation, see

jamespropp.org/somos/kuo3
and Eric Kuo's web-article
www.cs.berkeley.edu/~ekuo/condensation.ps
(still a draft).

5. TILTED DIAMOND PATTERNS 

f := proc(n,k) option remember; 
        if 3*n+k<-3 then undefined;
        elif 3*n+k<3 then x(n,k);
        else simplify( (f(n-1,k-1)*f(n-1,k+1)+1)/f(n-2,k) ); fi; end;

All the coefficients in the Laurent polynomial f(n,k) are equal to 1, and the individual monomials correspond to the perfect matchings of certain graphs (whose structure became clear through email conversations between Ron Adin, Robin Chapman, Ira Gessel, Rick Kenyon, Christian Krattenthaler, Eric Kuo, and myself). See Math 192 homework problem 19.2 as well as the discussion near the beginning of

jamespropp.org/bilinear/antifrieze.
The basic moral of this example is that changing the recurrence relation is in some ways dual to changing the set of values used as initial conditions.

6. THE SOMOS-4 RECURRENCE 

f := proc(n) option remember;
	if n<0 then undefined;
	elif n<4 then x(n);
        else simplify( (f(n-1)*f(n-3)+f(n-2)^2)/f(n-4) ); fi; end;

This sequence of polynomials was invented by Michael Somos. For more information on this sequence, and a host of related sequences, see

jamespropp.org/somos.html
At the start of the term, no combinatorial interpretation of these polynomials (or of the number that arise from these variables when one replaces every variable by 1) was known. But during February and March, intensive study of recurrences 8 through 11 gave us enough insight to enable us to find just such an interpretation in terms of perfect matchings of graphs. Details will be posted soon.

7. S-ARRAYS 

f := proc(n,k) option remember;
        if n<0 then undefined
        elif n<4 then x(n,k);
        else simplify( (f(n-1,k+1)*f(n-3,k-1)+f(n-2,k)^2)/f(n-4,k) ); fi; end;

This was an early attempt to lift the Somos-4 recurrence into higher dimensions (thereby bringing all the coefficients closer to 1, at the cost of having more of them). See

jamespropp.org/bilinear/S-arrays
for more information, as well as my posting to the bilinear forum on January 2, 2001 (search for the string "S-arrays").

8. THREE-DIMENSIONAL "SOMOS-3": the "face-variables" version 

f := proc(n,i,j) option remember; 
        if n<0 then undefined;
        elif n<3 then x(n,i,j);
        else simplify( ( f(n-1,i-2,j+2)*f(n-2,i+2,j-2)
                       + f(n-1,i+2,j+2)*f(n-2,i-2,j-2))
                      /  f(n-3,i,j)); fi; end;

This is related to recurrence #5 in much the same way that recurrence #3 is related to recurrence #1 (though this only becomes clear after a suitable change of indexing).

It was known back in January (thanks to Fomin and Zelevinsky) that f(n,0,0) is a Laurent polynomial for every n. It was noticed that, furthermore, every coefficient is positive; that indeed, every coefficient is 1; and that the exponents that are attached to all the variables are universally bounded, regardless of n. This has now been proved by the REACH students using combinatorial techniques.

The term "Somos-3" isn't consistent with the terminology of Michael Somos or David Gale, so I use it here very loosely.

I originally use the term "face-variables" (and below, the term "edge-variables") with some trepidation, because there was no guarantee that in the (at that moment yet-to-be-devised) combinatorial context for the Somos-3 and Somos-4 recurrences, these variables would be associated with faces and edges of graphs. Still, the analogy with "Somos-2", aka Dodgson and Kuo condensation, suggested that this terminology might not be too misleading. As things turned out, the guess was correct, and these variables are indeed most naturally viewed in terms of the faces and edges of certain graphs.

9. THREE-DIMENSIONAL "SOMOS-3": the "edge-variables" version 

f := proc(n,i,j) option remember; 
        if 6*n+j >= 0 and 6*n+j < 16 then 1; else simplify(
   ( y(i+2*n-1,j+2*n-1)*y(i-2*n+1,j-2*n+1)*f(n-1,i-2,j+2)*f(n-1,i+2,j-2)
   + y(i-2*n+1,j+2*n-1)*y(i+2*n-1,j-2*n+1)*f(n-1,i+2,j+2)*f(n-1,i-2,j-2))
  / f(n-2,i,j)); fi; end;

This version of the preceding recurrence (with all initial values being set equal to 1 and with non-obvious coefficients being incorporated into the recurrence relation) has the nice property of giving always true polynomials, not just Laurent polynomials. Moreover, every coefficient in this polynomial is 1, and every variable occurs at most once in any monomial. It was this case that was resolved by the students in early March and gave the ideas that unlocked the other recently-settled cases.

10. THREE-DIMENSIONAL SOMOS-4: the "face-variables version" 

f := proc(n,i,j) option remember; 
        if n<0 then undefined
        elif n<4 then x(n,i,j);
        else simplify( ( f(n-1,i-2,j+2)*f(n-3,i+2,j-2)
                       + f(n-2,i+2,j+2)*f(n-2,i-2,j-2))
                      /  f(n-4,i,j)); fi; end;

See

jamespropp.org/bilinear/startup
for more of what's known (not much!) about this recurrence. Fomin and Zelevinsky showed that this recurrence gives Laurent polynomials, but it was unknown that every coefficient is positive. Thanks to the new combinatorial interpretation, found by the REACH students and independently by Julian West and Mireille Bousquet-Melou, we know a good deal more: every coefficient is equal to 1; and the exponents that are attached to all the variables are universally bounded, regardless of n.

11. THREE-DIMENSIONAL SOMOS-4: the "edge-variables" version (?) 

f := proc(n,i,j) option remember; 
  if 8*n-i+j >= 0 and 8*n-i+j < 16 then 1; else simplify(
  ( y(-(i+2*n-1),j+2*n-1)*y(-(i-2*n+1),j-2*n+1)*f(n-1,i-2,j+2)*f(n-1,i+2,j-2)
  + y(-(i-2*n+1),j+2*n-1)*y(-(i+2*n-1),j-2*n+1)*f(n-1,i+2,j+2)*f(n-1,i-2,j-2))
 / f(n-2,i,j)); fi; end;
S := proc(n) option remember; f(0,-2*n,2*n); end;

This recurrence is different than the preceding ones, in that you are not supposed to get the polynomials of interest by entering f(n,0,0) for various small values of n. Instead, you should simply enter S(n).

This version of the preceding recurrence (with all initial values being set equal to 1 and with non-obvious coefficients being incorporated into the recurrence relation) has the nice property of giving always true polynomials, not just Laurent polynomials. Moreover, every coefficient in this polynomial is 1, and that every variable occurs at most once in any monomial. These facts follow from the the combinatorial interpretation of this recurrence, which was discovered independently by the REACH students and by Julian West and Mireille Bousquet-Melou.

For more information, see my posting to the bilinear forum on Thursday, January 17, 2002 (search for "sequences count").

12. THE CUBE RECURRENCE 

f := proc (i,j,k) option remember;
        if   (i+j+k < 3) then x(i,j,k) else
        simplify(
        ( 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));
        fi; end;

(No "face-variables" version of this recurrence is known.)

For more about what is known (or guessed), see two postings to the bilinear forum, one dated November 15, 2000 (the very first message in the archive) and the other dated Tuesday, August 28, 2001 (search for "hexagon recurrence", which is another name I've used, though I now think "cube recurrence" is better).

Despite a lot of hard work, the cube-recurrence has been frustratingly resistant to our attempts to find a combinatorial interpretation.

Last updated April 17, 2002.