SSL Notes
2004-02-03 Tuesday
Today's notetaker: Sam
Today's snack provider: Paul
Thursday's notetaker: Emilie
Thursday's snack provider: Carl
* * *
Before the meeting officially begins:
JIM: Any favorite sequences? We all know Fibonacci . . .
(Catalan, Lucas, Motzkin called out).
JIM: What about derangements? That is, a permutation with no fixed points
(if p in S_n then p(i) != i for any i in [1,n]).
One can show using the inclusion-exclusion principle that D_n, the number of
derangements of n elements (sometimes denoted !n and called subfactorial),
is the nearest integer to n!/e.
(Meeting commences)
On Wednesday, March 3rd the NSF will be doing a site visit for VIGRE grants.
Keep 3-4 pm open in case they would like to meet with SSL participants.
Also, any visually exciting or interesting mathematical pictures or
representations should be posted in the Undergraduate Math Lounge.
JIM hands out contracts and plans to sign and return on Thursday.
JIM requests that we decide whether to work on old (Fall semester) problems
or to learn new material.
We decide on the latter and adjourn to the computer lab.
JIM mainly discusses problems dealing with proving Laurentness (and positivity)
of some generalized Somos-k sequences by the technique of weighted counting
(of perfect matchings of graphs).
The bulk of the discussion is contained in the Maple worksheet, which can be
found in its various incarnations (mws,mpl,txt) in the main SSL directory
under the names Feb.mws, Febinput.mpl, and Febtext.txt (e.g.,
http://jamespropp.org/SSL/Feb.mws).
Some sidenotes are collected here.
JIM: I'm going to write a program (f) that returns a sequence.
How do we figure out what it counts?
I'll create a new function (F) with two arguments.
Initial conditions in original function all 1's.
Initial condition x(n,k) in F, where x(n,k) is indeterminate.
Clearly F(1,0) is a rational function with the property that if you replace
all the variables with 1s you always get integers.
F(1,1) same deal with different starting conditions.
If we continue in this way
F(n,k) we continue getting rational functions where the denominator is
actually a product (as opposed to a sum of products).
That is, it's a Laurent polynomial (a polynomial in x and x^(-1),
where "x" stands for all the different x's).
Expanding F will show us this.
In some sense, we have a multivariate generalization of our original
sequences of numbers. It is a lot more complicated, but the nice thing
is that it gives us clues as to what our original sequence enumerates.
For one, the terms of the sequence seem to count the number of terms in
the numerator. (So one sort of "trivial" combinatorial significance is
simply that it enumerates the number of terms in the numerator of some
Laurent polynomial.)
Now, is this circular?
A simpler recurrence merely replaced by a complicated one?
The point is we might be able to deduce the combinatorial structure from
inferences based on the polynomials and how they behave (algebraically).
It amounts to assigning weights in some fashion to some graph, and
generalizing from the number of matchings to sums of weights of matchings
of the graph.
The implication is that the weighting scheme is perhaps the difficult part.
Front of REACH t-shirt
Somos-4
The sequence corresponding to the recurrence S(n)*S(n-4) = S(n-1)*S(n-3) +
S(n-2)^2 also corresponds to the number of perfect matchings of some graph.
What the REACH undergraduates did was reverse engineer Laurent polynomials
from graphs, and there is *a lot more work* to be done in this area.
Let's return to an example from Thursday ("the Dana Scott sequence") and see
first of all what properties this sequence has and if it so happens that it
behaves at all like Somos-4.
I am going to write a Maple procedure to compute the terms of the sequence.
Let's look up this sequence in the OEIS.
(http://www.research.att.com/~njas/sequences/)
("Dana Scott sequence", no combinatorial interpretation given.)
Can we find a graph using the weighting approach?
Let's make a function with more variables again.
(Might not work well - sort of a black art, generalizations?)
Trying to make this satisfy an octahedron rule. (never mind - I'm not)
Matches up! Sequence of Laurent polynomials (do we know this - let's check)
Denominators all products for 1<=n<=12
Sidebar:
Maple stores equations in a tree-like data structure, so one must be clear
what "nops" returns.
Might there be a command that counts the number of terms (for sums of
polynomials)? We can write one.
I am not certain that there isn't a plus sign lurking somewhere (I check).
So it seems these *are* in fact Laurent polynomials.
JIM Will post Maple worksheet in next couple of days.
These are currently unlinked but available--see note at top. (e.g,
http://jamespropp.org/SSL/Feb.mws)
JIM Will also try and find
what Reid Barton (et al) have proved regarding some of these mixed (linear
and quadratic) recurrences.
In summary, there are plenty of problems with this flavor.
The general approach is to replace integers with lots of variables to get
Laurent polynomials, which could lead to a combinatorial understanding of
where those numbers came from in the first place.
Some updates on ongoing research:
Newton's method?
Brendan cleaned up the formula a bit. We still have some difficulties in
proving the formula for the coefficients by induction (though it appears
to be computational in nature).
Other avenues to explore?
Herriot's work/Markoff brothers:
JIM: We should return to Herriot's work, determine what he has proved and
what there is left to prove. We should return to Itsara's work on the Markoff
equation, in the hopes of attacking the brothers using analogous techniques.
What kinds of linear transformations on the triangular lattice preserve the
structure (that is, send type-4 vertices to type-4 vertices and type-8
vertices to type 8-vertices)?
The "prices" of these sides (calculated by the delta-Y method) should turn
into triples (?)
Lifting mod p?
Stephen has some ideas, will ask Professor Ken Ono.
Not combinatorial, Jim does not as many techniques and heuristics in this
setting.
Connectivity of Markoff graph modulo p/Associated Functions and Sequences
Are these expander graphs? How can we find out?
Apollonian gasket (dead-end?)
Combinatorial explanation? No new ideas.
An idea:
We have delineated the idea of an inversion of a circle with respect to some
other circle.
If someone wants to approach this, it would be great:
Take an infinite chain of tangent circles, take inverses with respect to other
circles, and determine anything that is "combinatorially interesting."
If anything, this can result in some nice pictures.
JIM will do a literature search on the Apollonian gasket/Dionysian
space-filler/variants and report back.