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.