Minutes for 10/8/02, courtesy of Kyle Petersen Andy agreed to be note-taker on Thursday. Gabriel hasn't heard about a new room, he will look into Memorial Hall. Alice found out we couldn't meet in her house. Math 192 lecture videos burn DVDs - Inna hasn't heard about burning DVDs. We decided we could use about 15 copies. Jim reminded us to post weekly updates (Friday, Saturday, or Sunday) including a running total of hours spent on REACH. John wondered how and when we would get paid. Jim told us that it would be monthly and from whichever pocket (Madison, NSA, NSF, VIGRE) is best. Alice hasn't heard back about Harvard's VIGRE money. Jim shamelessly peddled the idea of UW for grad school. ------- Why a set with a+1 positive particles and b+1 negative particles acts like a set with a positive particles and b negative particles. Look at a set of 4 positive particles and one negative particle and consider all the possible pairs of particles -recalling that a negative particle can be chosen more than once. __+___+___+___+___-__ |_+_|_+_|___|___|___| +1 |_+_|___|_+_|___|___| +1 |_+_|___|___|_+_|___| +1 |___|_+_|_+_|___|___| +1 |___|_+_|___|_+_|___| +1 |___|___|_+_|_+_|___| +1 |_+_|___|___|___|_-_| -1 |___|_+_|___|___|_-_| -1 |___|___|_+_|___|_-_| -1 |___|___|___|_+_|_-_| -1 |___|___|___|___|_=_| +1 ____ +3 This table represents /4 - 1\ and we want to say that | | \ 2 / it is the same as / 3 \ | | \ 2 /. We get the bijection by identifying any row with a + in the fourth column with a row that looks like we've removed that + and put a - in the fifth column. In the example, row 3 corresponds to row 7, row 5 corresponds to row 8, row 6 corresponds to row 9, and row 10 corresponds to row 11. Since each pair sums to zero, we're only left with three unidentified rows, and the new table looks like: __+___+___+___+___-__ |_+_|_+_|___|___|___| +1 |_+_|___|_+_|___|___| +1 |___|_+_|_+_|___|___| +1 ____ +3 This looks just like the table for / 3 \ /4-1\ | | = | | \ 2 / \ 2 / via the bijection. We discussed the homework problem (not-necessarily-perfect matchings of 1-by-n and 2-by-n grids, with n<0) in three groups. Two groups discussed combinatorial interpretations of running the 1-by-n case backwards using "anti-points" but neither group had a ironed out all the wrinkles yet. The third group had split into two smaller groups - both had worked out the algebra for 1-by-n but neither had seemed to do much for a combinatorial interpretation. However, some people worked on the algebra for the 2-by-n case. Jim mentioned that the problems of working the 1-by-n and 2-by-n not-necessarily-perfect matching cases backwards is something we could work on as a research topic, with an eye to generalization. He mentioned that we should read Gabriel's article because there are more research topics suggested in it. http://www.fas.harvard.edu/~gcarroll/math/gtpreach/cubeart.pdf Jim discussed more from the article on reciprocity. There were some minor typos, but Gabriel pointed out a significant error in the introduction. Instead of Q(1/x) = Q(x) there should be some polynomial Q'(x) so that Q'(x)Q(1/x) = Q(x). (In fact, Q'(x) turns out to a monomial.) Jen asked a question about annihilation from section four of the article. Let s be a sequence in the space of sequences, say the Fibonacci sequence (forwards and backwards). s = (..., -1, 1, 0, 1, 1, 2, 3, 5, ...) Then let T be the translation operation, where every entry in the sequence is shifted one space to the left. This gives Ts = (..., 1, 0, 1, 1, 2, 3, 5, 8, ...) TTs= (..., 0, 1, 1, 2, 3, 5, 8, 13,...) And so on. We can add and subtract sequences to one another, so in the case of the Fibonacci sequence, we have T^{2}s - Ts - s = 0. We can think of the polynomial T^{2} - T - I = A as an operator in and of itself. We say that A "annihilates" s since As = 0. What the paper said was that there could be no operator B (also a polynomial in T) that annihilated the positive terms of s but not the negative ones. The point being that there is only one way to extrapolate backwards in a sequence given by a recurrence. (Any sequence s whose recurrence is given by some A, such that As = 0, can be extended backwards using A.) To show that there is no such B, we'll first suppose that there there might be one. So say that As = 0 and that Bs agrees with As on all the non-negative terms. Now let s' be some sequence that agrees with s on all its non-negative terms and for which Bs' = 0. Clearly, (AB)s' = 0 since A0 = 0. Now since A and B are just polynomials in T, they clearly commute. So we have (BA)s' = 0. Therefore B annihilates As'. Since the non-negative terms of s and s' agree there is some point (As')_{n} after which all the terms of As' are zero. If As' = (..., c, 0, 0, 0, 0, ...), with c non-zero then when you apply B to As' one of the entries of the new sequence will be a linear combination of zeroes and c. Hence c must be zero, contradicting our choice of c. Thus As' = 0. Jim showed us the problem with higher-dimensional problems (e.g., perfect matchings of n-by-n, Aztec Diamonds). Noticed that perfect matchings of 2n-by-2n squares increased at least as fast as 2^{n^{2}}, so we can't have a linear recurrence. Counting Aztec Diamonds can tell you about matchings of a square. Notice that the recurrence for T(n) = # of domino tilings of an Aztec Diamond of order n is non-linear: T(n)T(n-2) = T(n-1)T(n-1) + T(n-1)T(n-1) There's also a way to count Aztec Diamonds using sines and cosines. See papers about domino tilings for the formula: Pachter or Cohn in ArXiV (2 different papers), also Kasteleyn, P.W. "The statistics of dimers on a lattice" (not on ArXiV). Pachter: http://www.combinatorics.org/Volume_4/Abstracts/v4i1r29.html Cohn: http://www.combinatorics.org/Volume_6/Abstracts/v6i1r14.html or math.CO/0008222 (i.e., http://front.math.ucdavis.edu/math.CO/0008222) In the "pyramid" counting scheme for the number of Aztec diamonds of a given size, we see recurrences of the form f = (be + cd)/a. It's not obvious why f should be an integer - we're interested in questions like this one. The larger question is "when do Laurent polynomial recurrences count something?" Jim thinks it's when the coefficients are all equal to one. So one goal of REACH is to find combinatorial problems that tell the story encoded by these kind of Laurent polynomials. On the other hand, we'd like to come up with recurrence relations (Laurent if necessary) to efficiently encode tiling problems. For Thursday Jim promised to show us his unwritten papers. Homework: Read http://jamespropp.org/bilinear/domino