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;

o---o---o---o---o---o | | | | | | o---o---o---o---o---owith 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:

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

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

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

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

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

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

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

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.