SSL Notes for meeting #14 (10/23) Today's note-taker: Emilie Next Time: Abby Today's snack-provider: Carl Next Time: Stephen Minutes for 10/23/03 Notetaker today: Emilie Notetaker next time: Abby Snack bringer today: Carl Snack bringer next time: Stephen Logistics: Next Thursday Jim will be out east, but we will still meet and Stephen will run the meeting. Introductions today with favorite theorem name: Jim: Satz 90. He thought it was funny cuz it was just a number for a theorem. Emilie: Myhill-Nerode. sort of sounds like "My hill in the road". Stephen: Nakayama Lemma (it's a lemma, but very useful) Abby: central limit theorem Melania: Adem's Relations Carl: L'hospital's rule Martin: little gauss's theorem, chinese remainder theorem, pumping lemma ------------------------------------------------------------------------------------- Jim talked a bit about cellular automata at the beginning. you have an infinite string of bits (1s and 0s) ....1 1 0 1 0 0 0 1 0 1 1 0 1 0 0 1 0.... and we can replace each of these bits by another 1 or 0 by looking in a "window" around that bit that we want to replace. Look at the one to the right and to the left of the one you want to change. Using the variables t=time and n=space we have a function f_t(n) = phi(f_{t-1}(n-1), f_{t-1}(n), f_{t-1}(n+1)) **this just says that the new bit is a function of the old bit at the space to its left, the old bit at its space, and the old bit at the space to its right** for 1s and 0s we can define phi as a list of possibilities since there are only 8 different ways to write out strings of three bits a b c phi 0 0 0 ? 0 0 1 ? 0 1 0 ? 1 0 0 ? 1 0 1 ? 1 1 0 ? 0 1 1 ? 1 1 1 ? and the phi can be defined in 256 different ways. So there's this "rule 110" (read downwards the 1s and 0s of the phi and the binary number is 110) which is very interesting to Stephen Wolfram. If you start with all 0s except for one 1 in your original string of 1s and 0s then when you iterate the rule 110 you get a light-cone type thing. Now we do cellular automata in a little different way. The variation is: instead of using a string of bits have a string of numbers (real or complex, it doesn't really matter). Instead of the lookup table like above there is an algebriac relation between the old values and the new value. The relationship is as follows: f_0(-4) f_0(-2) f_0(0) f_0(2) f_0(4) \ / | \ / | \ / | \ / f_1(-3) | f_1(-1) | f_1(1) | f_1(3) \ | / \ | / \ | / f_2(-2) f_2(0) f_2(2) and the lines show how the next one is formed (where the lines come from show which terms influence the new terms). so there is a rule where f_{t}(n) = phi(f_{t-1}(n-1), f_{t-2}(n), f_{t-1}(n+1)) let x=f_{t}(n) a=f_{t-1}(n-1) b=f_{t-2}(n) c=f_{t-1}(n+1) Then the rule that we are imposing can be written as x=(ac+1)/b When you iterate many times it turns out that it gives a laurent polynomial. Also, the successive terms on the diagonal have something to do with the domino tilings of a 2-by-(2t-2) rectangle. We did something similar in the lab when Jim was introducing possible ideas for research topics. If we make the top row all b and the second row all a then we really are just doing one sequence since each row will have the same term in it at each position. the sequence is: b, a, (a^2+1)/b, (((a^2+1)/b)^2+1)/a,.... Jim says that this is harder to understand than the 2 dimensional recurrence since more information is preserved with more variables. *if you make the exponents 1 instead of 2 then this recurrence becomes a 5-cycle *you can alternate between exponents of 1 and 2 and it becomes a 6-cycle *in general the recurrence won't cycle if the exponents are greater than 4 *are all coefficients positive? it's not known for sure, but believed to be true. *something interesting might be to go back to the two dimensional recurrence and alternate exponents and see if they count stuff. it's easier to look at the 2 dimensional recurrence since it preserves more information than the 1 dimensional recurrence. Abby: Is cellular automata good for probability? It looks like random walks to me. Jim: Yes, probably if you put in real numbers. It can model heat flow which is related to random walks Carl: Why is alternating exponents a good variation to look at? Jim: It's very interesting because you always get a Laurent polynomial. Usually this doesn't happen. Emilie: What about squaring the bottom too? Would that still be Laurent?? Jim: We'll look at that later in the computer lab. ** and indeed we do that later** What about cycling between three values for the exponent instead of two values. This does not give a Laurent polynomial in general. Abby: What about adding a different thing besides 1? Jim: Sure, add q, sometimes you get Laurent polynomials, but sometimes not. It turns out that domino tilings come up in this as a variant of Kuo condensation. Jim told us this. Stephen: Has it been proven that the gasket polynomial is Laurent? Jim: Yes it has. here is the gasket polynomial: (a+b+c+d)^2 = 2*(a^2+b^2+c^2+d^2) where a, b, c, d are the inverse radii of four tangent circles. In the same way that as you keep getting integers when you put in four integers, replacing by a=A, b=B, c=C, d=D where A,B,C,D are polynomials of 4 variables (w,x,y,z) the radii of new circles can always be expressed as Laurent polynomials of the original 4 circles. It's not known what combinatorics lies beneath these things. Now Jim poses the question as to what should happen in the next hour?? Jim: want's to look at the thing Emilie suggested earlier about squaring the bottom in that recurrence to see if it's Laurent. We'll go to the lab to check that. Martin: At the computers he wants to look at transfer matrices of the straight cube snakes. Abby: I found a 16x16 transfer matrix! Abby: wants to really understand how recurrence mentioned earlier corresponds to domino tilings. Jim: See http://jamespropp.org/bilinear/domino Stephen: Wants to explore what we know about which geometric situations give rise to exchange algebra and Laurent phenomenon. No one really knows how to generate these things...right?? Jim: yes that's true Jim: at some point we may want to read Gregg Musiker's article about alternating between exponents of 1 and 4 in recurrence mentioned at the beginning (cellular automata variation). s_n = {(s_{n-1}^4+1)/s_{n-2} if n=odd {(s_{n-1}^1+1)/s_{n-2} if n=even *jim will create a link to this article* BREAK FOR SNACKS!! CARL BROUGHT DOUGHNUT HOLES AND MILK!!! THANKS CARL!!! Now we're in the computer lab. We tried the thing with squaring the bottom in the recurrence but it turned out to not be Laurent. It grows fast! The transcript of the Maple session can be found at http://jamespropp.org/SSL/squarebottom Martin looked at Abby's transfer matrix and found that it does satisfy the same recurrence that Paul found (there's a proof of it on his website). So now we have two different ways to get to the same generating function for the straight cube snakes recurrence. Now they want to reduce the matrix, but that'll be hard. The end. See you next week.