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 Somos4 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:
oo o oo o
 
oo o oo o
superimposed with
oo o o
 
oo o o
equals
ooo oo o
   
ooo oo o
which equals
oo o oo

oo o oo
superimposed with
oo o o o
  
oo 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:
oo oo oo
oo oo oo
superimposed with
oo oo
oo oo
equals
oooooo
oooooo
which CANNOT be split up into two matchings of 2by4 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 Somos4.)
Algebra gives you a hint, if you generalize the problem.
Replace the onedimensional recurrence by a twodimensional 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 onedimensional 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 nontrivial 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 2by4 grid.
[Skip this, if time is running short! "We'll see a similar encoding
later."]
oo oo
f b g c h f g h / b c
oo oo
oo o o
f b g  c  h f / b c
oo o o
o o oo
f  b  g c h h / b c
o o oo
o o o o
f  b  g  c  h 1 / b c g
o o o o
o oo o
f  b g c  h 1 / g
o oo 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 onetoone 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 presystematic way to connect the story I just told you with
a couple of other stories.
1) The KenyonChapman generalization of antifrieze 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 upstep, end with a downstep)
* * * 1
* * *
* *
*
1
1 1 1
1 1 2 1
2 3 3 1
7 5 4
12 7
17
Combinatorial interpretation:
Latticepaths:
o
o o o
x o o o
o o o y
o o
Matchings:
oo
/ \
oo oo oo
/ \ / \ / \
o oo oo oo
\ / \ / \ / \
oo oo oo o
\ / \ /
oo oo
How does this apply in the case we were studying?
oo oo oo oo
/ \ / \ / \ / \
o oo oo oo o
\ / \ / \ / \ /
oo oo oo oo
\ / \ / \ /
oo oo oo
becomes
oooooooo
\ / \ / \ / \ /
oooooooo
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:
oo
 
oooo
   
oooooo
     
oooooo
   
oooo
 
oo
and one of its matchings:
oo
oo oo
o oo o o o
   
o o o o o o
 
o o oo
oo
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 1dimensional recurrence by a 3dimensional 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 setup 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 3dimensional 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(n2,i,j) = M(n1,i1,j1) M(n1,i+1,j+1) +
M(n1,i1,j+1) M(n1,i+1,j1)
(a special case of MillsRobbinsRumsey's lambdacondensation
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
oo
b  c  d
oooo
e  f  g  h  i
oooo
j  k  l
oo
m
a 0
oo
b c d 1 0 0
o o oo
e  f  g h i > 0 1 0 1 1 > b i j / f h
o o oo
j k l 1 0 0
oo
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 reinvent 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): 1dimensional recurrences are specializations
of 2dimensional recurrences which in turn are specializations of
3dimensional recurrences (but it seems to stop there) [The
2by2n 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 nonintersecting lattice paths (which I like to call
"routings"; is that standard? .....).
5. NOTSONICE 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 notsonice; 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".
[KenyonChapman]
What about Somos4?
I can tell you how to get a "notsonice" combinatorial interpretation.
It's doubly notsonice, 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 onedimensional recurrence
a_{n+4} = (a_{n+3} a_{n+1} + a_{n+2}^2) / a_{n}
by the threedimensional recurrence
S(n,i,j) S(n4,i,j) = S(n1,i1,j) S(n3,i+1,j) +
S(n2,i,j1) S(n2,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 twodimensional grammar of these arrays,
as Mills, Robbins, and Rumsey did with lambdacondensation?
This will give us a combinatorial model of the Somos4 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 "notsonice" model. Can we then go on to find the
nice combinatorial model that underlies the notsonice 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
threeparameter family of recurrence relations
a_{n+k} = (a_{n+i} a_{n+ki} + a_{n+j} a_{n+kj}) / 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 a1} prod_{j=0 to b1}
prod_{k=0 to c1} (i+j+k+2)/(i+j+k+1)
with properties analogous to binomial coefficients
C(a,b) = prod_{i=0 to a1} prod_{j=0 to b1} (i+j+2)/(i+j+1)
(mention that H(a,b,c) counts constrained plane partitions /
lozenge tilings). There's a whole richframework for
binomial coefficients: additive recurrence relations
(Pascal's triangle) and generating functions (1/(1xy)
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 Somos4 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 Somos4 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
Somos4 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 Somos4 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)
multivariate Laurent polynomials that generalize Somos numbers:
somos := proc (n) if (n <= 3) then v(i,j); else
simplify((subs(i=i1,somos(n1))*subs(i=i+1,somos(n3))
+subs(j=j1,somos(n2))*subs(j=j+1,somos(n2)))
/somos(n4)); fi; end;
3. There are lots of subproblems, with interrelated answers. An important
one is the cube recurrence
F(i,j,k) = (F(i1,j,k) F(i,j1,k1) + F(i,j1,k) F(i1,j,k1)
+ F(i,j,k1) F(i1,j1,k)) / F(i1,j1,k1)
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 gameshow metaphors: Algebra is the
emergency "lifeline" 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