Notes for lecture "Somos sequences and bilinear combinatorics" delivered 
by Jim Propp at MIT, 10/18/00

PREPARE:

Put up on board as teaser: 
	a_{n+4} = (a_{n+3} a_{n+1} + a_{n+2}^2) / a_{n}
	(a_n) = (1, 1, 1, 1, 2, 3, 7, ... )

7 = # { ... }

        1  

    0  -1   0

    0   0   0

0   0   0   0   0

    0   1   0


        0  

    1  -1   1

    0  -1   0

0   0   0   0   0

    0   1   0


        0  

    0   0   0

    1  -1   1

0   0  -1   0   0

    0   1   0


        0  

    0   0   0

    1   0   1

0  -1  -1  -1   0

    1   0   1


        0  

    0   0   0

    1   0   0

0  -1   0  -1   1

    1   0   0


        0  

    0   0   0

    0   0   1

1  -1   0  -1   0

    0   0   1


        0  

    0   0   0

    0   0   0

1  -1   1  -1   1

    0   0   0


START TALK

Thanks to Michael Kleber and Sara Billey for inviting me to speak in
	the seminar and for hosting me at MIT this semester
I wanted to give a talk entitled "The combinatorics of elliptic functions",
	but I don't feel entitled to yet.
But I can talk about the combinatorics associated with various similar-
	looking recurrence relations, as a start towards assembling a 
	general combinatorial picture of objects having "bilinear" 
	combinatorial properties (matchings, tilings, plane partitions, 
	nonintersecting families of lattice paths, ASMs, etc.)
There are family resemblances, shared generalizations, etc., so I think 
	there might end up being a coherent body of theory that one might 
	call "bilinear combinatorics".
On the other hand, there are some very specific questions that I haven't
	solved; knowing the answer to these questions would tell us a lot
	about what the shape of the general theory should be.
Please interrupt with questions!  As I mentioned in the abstract, I'm
	very interested in getting feedback and ideas and collaborators
	for this project.

The basic Somos-4 sequence (part of a much bigger family of sequences):
		a_{n+4} = (a_{n+3} a_{n+1} + a_{n+2}^2) / a_{n}
	with initial conditions a_1 = a_2 = a_3 = a_4 = 1.
A priori, it's a sequence of rationals; at is turns out, it's a sequence 
	of integers.
"If you get lost or bored, you can amuse yourself by proving integrality"
Mention that you can give exact formulas that interpolate.  Just as 
	Fibonacci sequences <--> exponential functions, Somos
	sequences <--> elliptic functions.
In fact, these sequences were introduced by Somos with an eye towards
	using them as an alternative foundation for the theory of
	elliptic functions (Don Zagier has mused about this too), 
	though this program has never been carried out. (The mainstream
	name for these sequence and their generalizations is "elliptic
	divisibility sequences".)
Analogies:
	Fibonacci			Somos
	Linear recurrence		Bilinear recurrence
	Exponential functions		Elliptic functions
	Integer points on a curve	Rational points on a curve
	    of genus 0 [hyperbola]	    of genus 1 (numerators)

Fibonacci numbers count things; so what do Somos numbers count?
As combinatorialists, we are not permitted to refuse this challenge!
	We have to find a combinatorial story to explain integrality.

To see what I mean by finding a combinatorial story, let's consider
	a different recurrence:
		a_{n+2} = (a_{n+1}^2 + 1) / a_n
	with initial conditions a_1 = a_2 = 1.
(Not bilinear in the strict sense.)
The terms are ..... just every other term of the Fibonacci sequence;
	what does that suggest?
We know ahead of time various interpretations of the Fibonacci numbers;
	for instance, perfect matchings (define; say I'll call them 
	"matchings" henceforth)
Quickly verify the linear recurrence relation for matchings
Interpret  a_{n+2} a_{n} = a_{n+1}^2 + 1  combinatorially:
Let's prove the related but simpler formula f_{2n+2} f_{2n} =
	f_{2n+1}^2 + 1 for the Fibonacci numbers:

	o---o   o   o---o   o
	        |           |
	o---o   o   o---o   o

	  superimposed with
	                                  
	    o---o   o   o                  
	            |   |
	    o---o   o   o                 
	                                    
	equals

	o---o---o   o---o   o
	        |   |   |   |
	o---o---o   o---o   o

	which equals

	o---o   o   o---o 
	        |        
	o---o   o   o---o

	  superimposed with

	    o---o   o   o   o 
	            |   |   |
	    o---o   o   o   o

Mention doubled edges
..... Point out that the proof is not truly bijective
..... The ambiguity factor is the same on both sides of the equation.
..... There's only one exceptional case:

	o---o   o---o   o---o

	o---o   o---o   o---o

	  superimposed with
	                                  
	    o---o   o---o                  

	    o---o   o---o                 
	                                    
	equals

	o---o---o---o---o---o

	o---o---o---o---o---o

	which CANNOT be split up into two matchings of 2-by-4 grids.
	This explains the "+1" in the RHS.

Note: Once you have the combinatorial model in hand, verifying the
	bilinear relation is straightforward, and integrality of
	the original sequence follows as an immediate consequence.

But what would you do if you didn't have the interpretation in advance?
(This is the situation we're in with Somos-4.)
Algebra gives you a hint, if you generalize the problem.
Replace the one-dimensional recurrence by a two-dimensional recurrence:

	... a   b   c   d   e ...	}
					} (two rows of initial conditions)
	      f   g   h   i   		}

	        J   K   L   		J=(fg+1)/b, K=(gh+1)/c, ...

	...       M   N           ...   M=(JK+1)/g, ...

		   ...

"Antifrieze patterns"
On the one hand, if we put a=b=c=d=e=...=1 and f=g=h=i=...=1, then we
	recover the one-dimensional recurrence we started with.
On the other hand, if we let the first two rows consist of formal
	indeterminates, then each element of each subsequent row 
	is a rational function of those indeterminates.
E.g.: M = ([J][K]+1)/g = ([(fg+1)/b][(gh+1)/c]+1)/g
	= fgh/bc + f/bc + h/bc + 1/bcg + 1/g
The "miracle" is that each of these rational functions is in fact
	a Laurent polynomial (define!).
(For the next row down, it's non-trivial that the rational function 
	(MN+1)/K is a Laurent polynomial.)

But more is true: every coefficient in each Laurent polynomial is equal to 1.
Given that this is true, you can predict how many terms each Laurent 
	polynomial should have. .....
If you specialize this Laurent polynomial by replacing all variables
	by 1, you get just the sum 1+1+..., where the sum is the number
	of terms.
But we also know that if you set all variables equal to 1, you get
	a Fibonacci number.
Consequently, the number of terms in the nth Laurent polynomial is 
	the 2nth Fibonacci number.
* Moreover, the structure of these Laurent polynomials gives an encoding
	of the combinatorial structure. *
Example: the five matchings of the 2-by-4 grid.
[Skip this, if time is running short!  "We'll see a similar encoding
	later."]

  o---o   o---o
f   b   g   c   h	f g h / b c
  o---o   o---o

  o---o   o   o
f   b   g | c | h	f / b c
  o---o   o   o

  o   o   o---o
f | b | g   c   h	h / b c
  o   o   o---o

  o   o   o   o
f | b | g | c | h	1 / b c g
  o   o   o   o

  o   o---o   o
f | b   g   c | h	1 / g
  o   o---o   o

See the pattern? ..... [Explain the pattern.]
* Each exponent is +1, 0, or -1. *
It's still a bit of a leap from the monomials to the matchings,
	but there is a one-to-one correspondence.
If you were given this sequence of Laurent polynomials, you might
	come up with something other than matchings as a combinatorial
	model that governs the terms, but you'd definitely come up with
	something.  The "grammar" of these Laurent monomials is too 
	simple to be stymied by (it helps to have a computer).

So that's an example of a combinatorial story that explains why a
	rational recurrence has an integer solution
A general theory is a story that connects lots of smaller stories together
	in a systematic way.
Here's a pre-systematic way to connect the story I just told you with
	a couple of other stories.

1) The Kenyon-Chapman generalization of anti-frieze patterns (developed
	through email conversations over the domino list)

Why require the initial conditions to occupy two consecutive rows? 
Instead, try things like this:


	        1
	  1   1   1
	1   1   *   1     (start with an up-step, end with a down-step)
	  *   *   *   1
	    *   *   *
	      *   *
	        *

	        1
	  1   1   1
	1   1   2   1
	  2   3   3   1
	    7   5   4
	     12   7
	       17

Combinatorial interpretation:

	Lattice-paths:


	        o
	  o   o   o
	x   o   o   o
	  o   o   o   y
	    o       o

	Matchings:

	                    o---o
	                   /     \
	  o---o       o---o       o---o     
	 /     \     /     \     /     \     
	o       o---o       o---o       o---o
	 \     /     \     /     \     /     \
	  o---o       o---o       o---o       o
	       \     /                 \     /
	        o---o                   o---o
	           
How does this apply in the case we were studying?	         

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

	becomes
	           
	o-------o---o-------o---o-------o---o-------o
	 \     /     \     /     \     /     \     /
	  o---o-------o---o-------o---o-------o---o

	which we recognize.
	           
3) Kuo's graphical condensation algorithm (mention how it was found by
	Eric when he was an undergrad here)

Give picture of Aztec diamond graph (define!) of order 3:

        o---o
        |   |
    o---o---o---o
    |   |   |   |
o---o---o---o---o---o
|   |   |   |   |   |
o---o---o---o---o---o
    |   |   |   |
    o---o---o---o
        |   |
        o---o

	and one of its matchings:

        o---o
             
    o---o   o---o
                 
o   o---o   o   o   o
|           |   |   |
o   o   o   o   o   o
    |   |        
    o   o   o---o
             
        o---o

Assign weights to edges, and to matchings.
Think of weights as formal indeterminates.  (So there are *lots* of
	variables flying around --- so many, in fact, that knowing
	the *weight* of a matchings tells you what the matching *is*!
	Moreover, the monomials encode the matchings in a transparent 
	way; compare with the original Laurent polynomials we looked
	at.)
Point out the 4 diamonds of order 2 (N, S, E, W) and the 9 diamonds of 
	order 1 (with C in the Center).
Show the recurrence relation 
	D . C = edge . edge . N . S + edge . edge . E . W
Remark about proof: if you superimpose a matching of D and a matching of C,
	it can be decomposed into a matching of N and a matching of S,
	or it can be decomposed into a matching of E and a matching of W,
	but not both.  The ambiguity factor (how many ways to decompose)
	is the same on both sides of the equation.
We've replaced the 1-dimensional recurrence by a 3-dimensional recurrence
	(explain).
Application: Give every vertical edge weight 0, except at the equator.
Verify the relation
		a_{n+2} a_n = a_{n+1}^2 + 1

Use the set-up to count matchings of the Aztec diamond graph of order n: 
	..... 2^{n(n+1)/2} (set all variables equal to 1!)

It's worth mentioning here a different 3-dimensional recurrence associated 
	with Aztec diamonds, which looks more like the antifrieze recurrence.
	Create variables x(n,i,j) where n = 0 or 1 and i and j have the same 
	parity as n.  Define M(n,i,j) = x(n,i,j) for n = 0 or 1, and for
	n > 1 define M(n,i,j) for by the OCTAHEDRON RECURRENCE
		M(n,i,j) M(n-2,i,j) = M(n-1,i-1,j-1) M(n-1,i+1,j+1) + 
				      M(n-1,i-1,j+1) M(n-1,i+1,j-1)
	(a special case of Mills-Robbins-Rumsey's lambda-condensation
	algorithm, with lambda = 1; lambda = -1 correspond to the
	Dodgson condensation algorithm for computing determinants).
With lambda = 1, we end up with 2^{n(n+1)/2} terms, each a Laurent
	monomial with coefficient 1.  Moreover, each exponent is
	in each monomial is +1 or -1 or 0, and the rule for exponents
	generalizes something we saw earlier:

        a
      o---o
    b | c | d
  o---o---o---o
e | f | g | h | i
  o---o---o---o
    j | k | l
      o---o
        m

        a                       0
      o---o
    b   c   d               1   0   0
  o   o   o---o
e | f | g   h   i  -->  0  -1   0  -1   1  -->  b i j / f h
  o   o   o---o
    j   k   l               1   0   0
      o---o
        m                       0

Fact 1: The pattern of exponents uniquely determines the matching.
Fact 2: If you just look at the variables in level 0, or the variables
	in level 1, and ask "what patterns of exponents can you see
	for those variables?", you re-invent alternating sign matrices.  
	(In fact, if your name is David Robbins, and it's the late
	1970s, this is how you invent ASMs in the first place!)
Fact 3: This combinatorial model (matchings of Aztec diamonds graphs)
	gives the nicest known way of proving that the octahedral 
	recurrence gives Laurent polynomials.  So here's a case where
	combinatorics has something to offer to algebra.

So there are lots of instances that fit together.
(I'm not even talking about Dodgson condensation, number walls, etc.)

Some general features of the theory:
1. DIMENSIONALITY (1<-2<-3): 1-dimensional recurrences are specializations 
	of 2-dimensional recurrences which in turn are specializations of 
	3-dimensional recurrences (but it seems to stop there)  [The 
	2-by-2n example]
2. INTEGRALITY <- LAURENTNESS: Numerical recurrences that a priori they 
	should generate sequences of rational numbers but (surprise!) 
	generate sequences of integers are specializations of multivariate 
	recurrences that a priori should generate sequences of rational 
	functions but (surprise!) generate sequences of Laurent polynomials.
	[Antifrieze recurrence]
3. ENUMERATION: These Laurent polynomials are _enumerators_ that count 
	combinatorial objects.  They're halfway between algebra and 
	combinatorics: each coefficient is 1 (that's what having lots of 
	variables buys you: lots of variables means lots of exponents in 
	any given monomial, which means lots of information --- enough to 
	encode the combinatorial object).   [Antifrieze recurrence]
4. NICE MODELS: ROUTINGS AND MATCHINGS: Often these combinatorial objects 
	are interpretable as perfect matchings, or as lattice paths, or as 
	families of non-intersecting lattice paths (which I like to call 
	"routings"; is that standard? .....).
5. NOT-SO-NICE MODELS: ARRAYS OF EXPONENTS.  This "model" is a cheat;
	it just records the exponents from the Laurent monomials.
	(Tacit assumption: all coefficients equal 1.  In many cases,
	we have no proof of this assumption, but lots of evidence.)
	These exponents are (demonstrably or conjecturally) uniformly
	bounded.  (E.g., +1s, -1s, and 0s.)  It's easy to go from the
	nice models to the not-so-nice; harder to go the other way.
6. INITIAL CONDITIONS <- BOUNDARY CONDITIONS: Some of the variables are 
	"initial conditions" of the recurrence.  You can make this boundary 
	have lots of different shapes, without sacrificing "Laurentness".  
	[Kenyon-Chapman]
	
What about Somos-4?
I can tell you how to get a "not-so-nice" combinatorial interpretation.
        It's doubly not-so-nice, because it hinges on the conjecture
        that a generalized Somos recurrence with lots of variables in it
        gives Laurent polynomials forever, and that all these infinitely
        many Laurent monomials  have coefficient 1.
Replace the one-dimensional recurrence
                a_{n+4} = (a_{n+3} a_{n+1} + a_{n+2}^2) / a_{n}
        by the three-dimensional recurrence
                S(n,i,j) S(n-4,i,j) = S(n-1,i-1,j) S(n-3,i+1,j) +    
                                      S(n-2,i,j-1) S(n-2,i,j+1)
        where S(n,i,j) = x(n,i,j) for n = 0, 1, 2, and 3.
(Two alternative points of view: 1) This is a different octahedral
	recurrence.  2) This is the ordinary octahedral recurrence,
	but now the initial conditions lie on a tilted plane.)
Challenges: Can we decode the two-dimensional grammar of these arrays,
	as Mills, Robbins, and Rumsey did with lambda-condensation?
	This will give us a combinatorial model of the Somos-4 numbers.
	(Bonus: If we can infer the grammar, proving that everything
	works the way it's supposed to is likely to be a fairly easy 
	induction, and we'll have eliminated the conjectural element.)
	But this model will be expressed in terms of algebraic conditions
	on arrays of 0s, 1s, -1s, and other small numbers: what I've
	called a "not-so-nice" model.  Can we then go on to find the 
	nice combinatorial model that underlies the not-so-nice model?

Why "compelling"?

1. The study of Somos sequences has been hampered by the lack of good
	models.  There is no known proof, for instance, that the
	three-parameter family of recurrence relations
	a_{n+k} = (a_{n+i} a_{n+k-i} + a_{n+j} a_{n+k-j}) / a_{n}
	all yield integer sequences; even proving it for special cases 
	of i, j, and k involves difficult computer algebra with theta
	functions.  I suggest that these facts will become near
	trivialities once we have the right models.
2. The study of the octahedron recurrence led to the discovery of ASMs.
	So this looks like a fertile area.
3. Perfect matchings and ASMs are both instances of exactly solvable
	stat mech models.  So it would not be surprising if, as we
	study other bilinear recurrence relations, we run into other
	stat mech models, and solidify the link between the two
	subjects.
4. Other links: elliptic functions, theta functions, algebraic geometry;
	integrable systems, solitons.
5. Just within combinatorics: Lots of times we encounter functions like
	the MacMahon numbers
	H(a,b,c) = prod_{i=0 to a-1} prod_{j=0 to b-1} 
		   prod_{k=0 to c-1} (i+j+k+2)/(i+j+k+1)
	with properties analogous to binomial coefficients
	C(a,b) = prod_{i=0 to a-1} prod_{j=0 to b-1} (i+j+2)/(i+j+1)
	(mention that H(a,b,c) counts constrained plane partitions /
	lozenge tilings).  There's a whole rich-framework for
	binomial coefficients: additive recurrence relations
	(Pascal's triangle) and generating functions (1/(1-x-y)
	has them all).  What's the analogous framework for
	the MacMahon numbers?  The obvious encoding via generating 
	functions satisfies no algebraic relations.  But these 
	numbers do satisfy bilinear relations, and we need to 
	learn how to make the best use of this.  We need a theory
	that can pick up where generatingfunctionology leaves off.
6. "So close, yet so far": Suppose for the moment that, as the data
	attest, the multivariate Somos-4 recurrence gives an infinite
	sequence of Laurent polynomials, and that all the coefficients
	of all those Laurent polynomials are equal to +1.  Then I can 
	generate all the Somos-4 objects of order n, for any n you pick, 
	just by applying that recurrence.  And yet: I have no idea what
	the inherent, structural, combinatorial properties of the
	Somos-4 objects *are*!  (Roughly trapezoidal.)

Why "accessible"?

1. At least we can generate the objects.  We're in the unusual position of 
	being naturalists, getting to identify a new species by observation
	rather than by combinatorial fiat.  The Somos-4 objects are a new 
	kind of combinatorial object.  We observe them in "the wild" (via 
	the Laurent polynomials that list them) and try to infer the nature 
	of the beast.

2. Maple has a very easy time with recurrences like this.  I can supply
	code.  E.g., here's a complete program to compute the (conjectural)
	multi-variate Laurent polynomials that generalize Somos numbers:

	somos := proc (n) if (n <= 3) then v(i,j); else
		simplify((subs(i=i-1,somos(n-1))*subs(i=i+1,somos(n-3))
		         +subs(j=j-1,somos(n-2))*subs(j=j+1,somos(n-2)))
		         /somos(n-4)); fi; end;
	
3. There are lots of sub-problems, with inter-related answers.  An important
	one is the cube recurrence
	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)
	where F(i,j,k) = x(i,j,k) if i+j+k is 0, 1, or 2.
	Here again, we seem to get exclusively Laurent polynomials,
	and all the coefficients are +1.  If we replace all the
	variables by 1, we'll count the objects themselves.  That
	sequence is governed by the recurrence
		a_{n+3} = 3 a_{n+2} a_{n+1} / a_{n}
	which is easily solved (all terms of the sequence are powers
	of 3).  Jeopardy: The answer is 3^{floor(n^2/4)}; what is
	the question.  To mix game-show metaphors: Algebra is the
	emergency "life-line" that may give you a chance.

Please contact me if you're interested in finding our more and/or 
helping figure out the rest of the story: propp@math.wisc.edu