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.