REACH meeting 2/6/03 Ananda was the note-taker, next time Kezia is the note-taker If you can not make it to a REACH meeting, email Jim beforehand. Otherwise he does not know how many people to wait for. The note-taker should prepare the notes in ASCII and email them to Jim by the next day. The minutes need to be in ordinary text so that the minutes have a uniform format. If an important picture can not be drawn in ASCII, include the url for the picture in the minutes. People's commitments: Kezia will be the note-taker on tuesday. Kyle and Gabriel should create plan of things to do in the computer room. Everybody should read the paper on Kyle's website and send comments to him. Kyle should post his grove coloring book on-line Everyone should work on the homework problem for tuesday Everyone went around and said their favorite math word. New members were asked to turn in contracts. Focus on PROCESS (contrast process and outcome) because that's a good way to get to good outcomes! Kyle announced that his group is trying to finish and submit a paper. See the paper on his REACH website. He would like people to proof read the paper at (http://people.brandeis.edu/~tkpeters/reach/stuff/reach/) and send him comments at tkpeters@brandeis.edu. He especially would like people to read the introduction and the explanations. The paper should give people a good idea how to approach the homework problem. Open discussion about how to improve REACH: Possibly find a quieter place to meet? It is quieter to meet on the couches instead of at the tables. Kyle wants to make a presentation in the computer room. Gabriel also has things to present on the computer. The two of them, and anyone else who is interested should make a concrete proposal for going to the computer room. Gabriel thinks his presentation would only be useful for people who are familiar with Mathematica. Mathematica and Maple on personal computers are free for people at MIT. Go to http://web.mit.edu/is/products/vsls/ Let Jim know if you are not a US citizen and need help getting funding. Richard Stanley is the person to talk to at MIT. In a week or two, we should go around and state our interests. Maybe we should have team meetings earlier so people can shop around more. We need to find a balance between existing teams and new people. Everyone should tell Jim if they feel the balance is off. If people want to know who is doing REACH they should check the reach web-page. www.math.harvard.edu/~propp/reach/ it has been recently updated. Tell Jim if you know someone on the list is not coming back. The focus of REACH is the overlap between Algebra and Combinatorics. There are two important themes. Reciprocity: Surprising symmetry Laurentness: Surprising integrality s_{n+1} = frac{s_n^a +1}{s_{n-1}} or frac{s_n^b + 1}{s_{n-1}} alternating whether n is even or odd. Last time we looked at the example where (a,b)=(1,4) or (4,1). The general version of this sequence with starting values 1,1 looks like 1, 1, 2, 2^b+1, ((2^b+1)^a+1)/2, ((((2^b+1)^a+1)/2)^b+1)/(2^b+1), ... For all a,b>0 this sequence is composed of integers. (Theorem by Fomin and Zelevinsky). The sequence behavior is determined by the product ab. Fomin and Zelevinsky's trichotomy: ab<4: periodic behavior e.g., a=b=1 is the sequence 1,1,2,3,2,1,1,... which has period 5 for any two starting values. a=1, b=2 has period 6 a=1, b=3 has period 8 ab>4: superexponential growth ab=4: simple exponential growth a=2, b=2 then the sequence is every other number in the Fibbonacci recurrence. 1,1,2,5,13,34,... a=1, b=4: can be described by a linear recurrence but there is no known combinatorial interpretation. if we take starting values of x and y the sequence looks like x,y,(y^4 +1)/x,((y^4 +1)/x+1)/y,... Each term is a rational function of x and y. Each can be written as a Laurent polynomial. Laurent polynomials are a sum of monomials where the variables can have negative exponents. Jim believes that all of the coefficients are positive but this has not been shown. This is an algebraic question, but the only known method of solving it is to find a combinatorial model (though later on he retracted this a little; see below). Someone asked if the positivity has been tested. Jim says that testing it would an interesting thing for someone to do. There is a known combinatorial model for the case of a=2, b=2 which is every other number in the Fibbonacci recurrence when x=y=1. For general x and y the problem can be turned into a 2 dimensional recurrence, which makes Laurent polynomials where every coefficient is 1. The method is to create a triangular array where the next value is calculated by multiplying the two values one row above it to the left and right adding 1 and dividing by the value two rows above. x_1 x_3 x_5 x_7 y_2 y_4 y_6 (y_2*y_4+1)/x_3 (y_4*y_6+1)/x_5 (((y_2*y_4+1)/x_3)*((y_4*y_6+1)/x_5)+1)/y_4 These polynomials represent the combinatorial objects. How do you preserve Laurentness when going from 1-d to 2-d? There are lots of possibilities. It would be very cool to do something like above for the (1,4) sequence. Someone could work on showing terms with x,y satisfy linear recurrence as well as the given non-linear recurrence (which might give a non-combinatorial proof of positivity of coefficients). The two ab=4 cases correspond to affine Lie algebras. Jim says, "I don't understand the link, but I just say that so that you know that this isn't just combinatorics! There's also a link with geodesics on hyperbolic manifolds. I've been learning about this from Dylan Thurston." Jim set up the matrix formulas for the spanning tree homework problem: [x(6)+x(7) x(6)x(7)][x(4) + x(5) x(4)x(5)][x(2) + x(3) x(2) x(3)] [x(1)] [ 1 x(6)][ 1 x(4) ][ 1 x(2) ] [ 1 ] Invert: [x(0) + x(1) x(0) x(1)]^(-1) [x(1)] [ 1 x(0) ] [ 1 ] equals [x(0) - x(0) x(1) ] *(1/x(0)^2) [x(1)] = [ 0 ] [ -1 x(0) + x(1)] [ 1 ] [1/x(0)] You can generate this sort of matrix product on one line in Maple or Mathematica. Each determinant is monomial. Running the recurrence backwards gives Laurent polynomials. For more information on reciprocity see Jim's article on reciprocity: http://front.math.ucdavis.edu/math.CO/0104011 (contains some mistakes that he still haven't gotten around to fixing) Next time we will talk about last semester's groups and try to orient the new-comers. Kyle has things that he wants people to work on. Aztec diamond. See links on Kyle's webpage to java applet for pictures. http://people.brandeis.edu/~tkpeters/reach/stuff/reach/ Groves on standard initial conditions. The corners are the frozen regions (with very high probability, all the edges line up as shown) and the blank section is random-looking (with very high probability, the edges are jumbled-looking). ______________ \///// \\\\\/ \/// \\\/ \/ \/ \ / \----/ \--/ \/ The expected shape is a circle. How much does the circle wiggle? What is the variance? This requires some statistics. The problem for Aztec diamonds is not so hard. Only need to look at one corner Looking at the Aztec diamond, draw / through western tiles, \ through eastern tiles and -- through southern tiles. Northern tiles have no lines. Look at the topmost path, above that is all the northern tiles- the frozen region. Kyle wants to do the same thing for groves. He needs a good way to color graphs. He is looking for someone who knows java and would like to make a nice program. Kyle also has pictures of groves that people should try to color in. He needs to post these on the web. he should make a link from his home page. http://people.brandeis.edu/~tkpeters/reach/stuff/reach/ Aztec diamonds and groves related by cube recurrence. Jim- interesting to see if paths fit structure of algebraic recurrence. Height function related to paths Maybe find height function that does not convey all the information for groves. Kyle- look at random groves on Aztec diamond initial conditions. Gabriel- Should we look at the shape of the frozen region for other initials? Kyle-Standard initials make the triangular lattice, but it maybe better to focus on the rhombi. Jim-Turn spanning tree into Hamiltonian path. Trevor- Percolation theory might be useful. Grove on standard initials. Points are connected by some sort of tree. Simplify to paths (from trees). Height of point is band it lies in. Gabriel- asymptotics of height functions for Aztec diamonds might help. Jim-Derivative of asymptotic height function can be gotten in closed form, but not the actual asymptotic height function. Look at symmetric initials or look at general initials? it will probably be too dirty unless we are looking at nice initials. No frozen region of a rectangle. Look for grove case with no frozen region. Aztec octagon: Whe does frozen region stop? __________________________ | / /\ \ | |/ / \ \ | | / \ \| |\ \ / | | \ \ / /| |___\______\/_______ /_| In addition to domino tilings of a region divided into squares, _____________________ |* | | | | | | | ---------------------- |* | | | | | | | ---------------------- | | | | | | | | ---------------------- | | | | | | | | ---------------------- (the two stars denote a connected domino) there are rhombus tilings of a equilateral triangular lattice and there are diabolo tilings of fortresses which are isosceles triangular lattices. Random diabolo tilings of fortresses exhibit three regimes: a frozen regime near the boundary, a temperate zone bordering the frozen region (where tiles are jumbled but the influence of the boundary can be seen in the local statistics of the jumbling, e.g., in the relative preponderance of the different sorts of tiles), and an inner region that (the "tropical astroid") in which the tiles appear to be completely shielded from the influence of the boundary.