DRAFT OF R.E.A.C.H. PROJECTS LIST, 2/21/02                        Jim PROPP

1. For integers n,i,j with 6*n+j non-negative, define the rational function 
   F(n,i,j) by way of the recursive program

   F := proc(n,i,j) option remember; if 6*n+j < 0 then undefined;
   elif 6*n+j < 16 then 1; else simplify(
   ( a(i+2*n-1,j+2*n-1)*b(i-2*n+1,j-2*n+1)*F(n-1,i-2,j+2)*F(n-1,i+2,j-2)
   + c(i-2*n+1,j+2*n-1)*d(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;

   Here expressions of the form a(i,j), b(i,j), c(i,j), d(i,j), and x(i,j)
   are to be understood as variables.

   I conjecture (and want you to help me prove) that the rational function
   F(n,i,j) is in fact a polynomial in which every coefficient is equal to
   1, and in which each constituent monomial is a product of distinct
   variables.

   In this work, you will be guided by the analogy between the above
   program and the program

   M := proc(n,i,j) option remember; if n < 0 then undefined;
   elif n < 2 then 1; else simplify(
   ( a(i+2*n-1,j+2*n-1)*b(i-2*n+1,j-2*n+1)*M(n-1,i-2,j+2)*M(n-1,i+2,j-2)
   + c(i-2*n+1,j+2*n-1)*d(i+2*n-1,j-2*n+1)*M(n-1,i+2,j+2)*M(n-1,i-2,j-2))
   / M(n-2,i,j)); fi; end;

   which computes polynomials associated with perfect matchings of Aztec
   diamond graphs.  So you will want to have a fairly detailed understanding
   of how these matching polynomials work.

   As part of this project, you should extend your analysis to cover the
   recurrence

   F := proc(n,i,j) option remember; if 6*n+j < 0 then undefined;
   elif 6*n+j < 16 then x(i,j); else simplify(
   ( a(i+2*n-1,j+2*n-1)*b(i-2*n+1,j-2*n+1)*F(n-1,i-2,j+2)*F(n-1,i+2,j-2)
   + c(i-2*n+1,j+2*n-1)*d(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;

   We no longer expect F(n,i,j) to be a polynomial in all its variables;
   rather, it will be a Laurent polynomial in the new variables x(i,j)
   (that is, it will be expressible as a polynomial once we admit as 
   variables the x(i,j)'s AND their reciprocals).

   Guided by the analogy with the Aztec case, we might hope that the
   variables a(i,j), b(i,j), c(i,j), d(i,j) correspond to edges in some
   graph and that the variables x(i,j) correspond to faces, but this
   working assumption might need to be modified or scrapped.

2. A simpler version of the above question concerns the substitute equation

   G := proc(n,i,j) option remember; if 6*n+j < 0 then undefined;
   elif 6*n+j < 16 then x(i,j); else lcm(
   ( a(i+2*n-1,j+2*n-1)*b(i-2*n+1,j-2*n+1)*G(n-1,i-2,j+2)*G(n-1,i+2,j-2),
     c(i-2*n+1,j+2*n-1)*d(i+2*n-1,j-2*n+1)*G(n-1,i+2,j+2)*G(n-1,i-2,j-2))
   ); fi; end;

   The G-polynomials can help one identify the variables that occur in the
   F-polynomials.  

   Understanding the G-polynomials should not be too hard (it should be
   considerably easier than understanding the F-polynomials), and once 
   one of you has done this in the specific case described above, I'd like 
   to see the analysis extended to other situations, where the linear 
   form 6*n+j is changed (and the bounds 0 and 16 are changed accordingly).  

   The cases of greatest interest to me are the Somos-4 and Somos-5 
   recursions, or rather what you get when these recursions are boosted 
   from one-dimensional recurrences to suitable three-dimensional 
   recurrences.

3. The Somos-4 recurrence is
	a(n) a(n-4) = a(n-1) a(n-3) + a(n-2) a(n-2)
   while the Somos-5 recurrence is
	a(n) a(n-5) = a(n-1) a(n-4) + a(n-2) a(n-3).
   These are special cases of the more general recurrence
   (*) 	a(n) a(n-k) = a(n-i) a(n-k+i) + a(n-j) a(n-k+j)
   (where k must be a positive integer and i,j must be positive integers
   strictly between 1 and k).

   If one puts a(0) = a(1) = ... = a(k-1) = 1 and then defines a(k),
   a(k+1), ... by (*), one finds that all subsequent terms are 
   integers.  This part of the Gale-Robinson conjecture was proved 
   by Fomin and Zelevinsky.  However, the meaning of the integer
   sequences given by such recurrences has remained obscure.

   I believe that each such (one-dimensional) sequence is associated
   with a parametrization of solutions to the (three-dimensional) 
   Hirota equation, in which the term a(n) gets replaced by a
   sum of a(n) monomials, each with coefficient +1.

   I would like a clean statement of this conjecture, and in particular,
   I want these parametrizations to be described in the cleanest possible
   way.  This will probably involve some experimentation.

   Let me try stating the problem another way: If one looks back
   at project 1 and replaces the program for F by

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

   (that is, if one sets all the a, b, c, and d weights equal to 1),
   then one finds that the values of the function F are just numbers,
   and if one sets a(n) = F(n,0,0) one finds that the resulting
   sequence a(0), a(1), a(2), ... satisfies the recurrence

   a(n) a(n-3) = a(n-1) a(n-2) + a(n-1) a(n-2).

   We seek a three-variable recurrence that, when subjected to similar
   specialization, will give the Somos-4 recurrence, and another that
   will give the Somos-5 recurrence, etc., for all the Gale-Robinson
   recurrences.

   It is desired that each such three-variable recurrence yield
   polynomials (or more generally Laurent polynomials) in which
   each coefficient is 1.  

   There are going to be many such recurrences; one goal is to
   find the simplest form for all the equivalent three-dimensional
   recurrences associated with a specific one-dimensional recurrence.
   Hopefully there is a slick approach that covers all of the
   Gale-Robinson cases simultaneously.

4. While some of us are working from concrete algebraic structures
   and trying to derive the associated combinatorics, others of us
   will be working in the other direction, starting with combinatorics
   and trying to derive the associated algebra.

   We know that if a(n) denotes the number of domino tilings of a
   2-by-2n rectangle, then a(n) a(n-2) = a(n-1)^2 + 1.  To what
   extent do results like this exist for things like domino tilings
   of 3-by-2n rectangles?

   We are going to be particularly interested in recurrences that
   lift into the setting where a(n) (a number) is replaced by a
   polynomial whose individual terms actually represent the
   respective tilings.  E.g., let's replace tiligns by matchings
   in the usual way, and associate variables with the edges of
   the 3-by-2 grid graph as shown:

    o--x_1--o
    |       |
   v_1     v_2
    |       |
    o--y_1--o
    |       |
   w_1     w_2
    |       |
    o--z_1--o

    Then the polynomial that counts (and indeed displays) the perfect
    matchings of this graph is x_1 y_1 z_1 + x_1 w_1 w_2 + v_1 v_2 z_1 .
    We'd like some sort of generalization of the multivariate version
    of Kuo's theorem, telling us that these polynomials are not
    independent of each other but satisfy various mutual algebraic
    relationships (of a latently combinatorial nature).

5. The same goes for things like diabolo tilings of fortresses.
   We can represent each matching by a polynomial.  The question
   then becomes, what recurrence relations do these polynomials
   satisfy?  Linear equations won't do; they must be quadratic
   (or higher order).

   Here for instance is the graph dual to the fortress of order 2:

                                    o
                                   / \
                              o---o   o
                             /     \ /
                            o       o
                            |       |
                            o       o
                           / \     /
                          o   o---o
                           \ /
                            o

   Eric Kuo's basic method can be used for graphs like this;
   someone should work out the details.

6. Likewise for tilings of a strip of length n by means of tiles
   of lengths 1, 2, and 3 (or just tiles of lengths 1 and 3, or
   lengths 2 and 3).  What are the basic recurrences that hold?
   Here, as in the two preceding problems, I will operate with
   the prejudice that the most interesting and most basic
   recurrences are those that remain valid in the "lotsa-
   variables" setting.

   More specifically: We could let A(m,n) be the sum of the weights
   of all the tilings of the set {m,m+1,...n}, where a legal tiling
   consists of disjoint sub-intervals of lengths in the prescribed
   subset of {1,2,3}, and where the weight of a tiling is the
   product of the weights of the tiles (where each tile has its
   own weight).  Then we would look for relations among the
   multivariate polynomials A(m,n).

7. Two important specializations of Dodgson condensation are to the
   case of Hankel matrices and the case of Toplitz matrices.  These
   are almost the same theory, except for a sign-flip, they show up
   in the theory of "number walls".  In this setting, the Robbins-
   Rumsey polynomials become polynomials in fewer variables, in
   which the exponents of the variables need no longer be in the
   set {+1, 0, -1}.  I would like you to determine the structure
   of these polynomials.  One basic thing that (to my knowledge) 
   isn't known is, how many terms are there in each such polynomial?
   Even we can't count the monomials, can we at least give a
   combinatorial characterization of those that occur?

   Let me be very concrete here: We are looking at the Laurent
   polynomials that are output by the program

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

   The number of terms in W(n,0) for n=1,2,3,... goes 
   	1, 2, 7, 41, 395, ...
   Is there a general formula?

   If this effort succeeds, I would like to see it lead into an
   analysis of various other two-dimensional recurrences with
   similar features, such as the

              A

        B   C   D   E         AF = BE + CD

              F

   recurrence (which is related to a funy kind of "tilted Toplitz"
   determinant).

8. All of the quadratic recurrences described above have just
   three terms (one on the left of the equals-sign and two on
   the right).  There are also cases of four-term recurrences
   (like the Somos-6 and Somos-7 recurrences) where nice things 
   happen.  Federico and Stathis have been hoping to gain an 
   understanding of an especially nice and symmetrical three-
   dimensional recurrence with four terms, namely the "cube
   recurrence":

     G--------H
    /|       /|
   E-+------F |
   | |      | |
   | |      | |       AH = BG + CF + DE
   | C------+-D
   |/       |/
   A--------B

   Here are our initial variables correspond to lattice points 
   (i,j,k) with i+j+k = -1, 0, or 1.

9. Another recurrence that seems to be tied up with all these
   matters, even though it isn't quadratic and doesn't have the 
   Laurentness property in the strict sense, is the recurrence

              A

           B     C

        D     E     F        A(EI - GH) = DEF + BCI - CDH - BFG

           G     H

              I

   (i.e., the determinant of the three-by-three matrix vanishes),
   with four rows of formal indeterminates to start off the game.
   David Speyer has looked at this, and has already noticed that
   subsequent entries in such a table are polynomials in which
   the denominator can be written as a product of monomials and
   binomials (the latter arising from 2-by-2 subdeterminants).