SSL Minutes for Tuesday, Nov. 25, 2003 Note taker: Abby Snacks: Forgotten Next Tuesday's Note Taker: Carl Next Tuesday's Snacks: Hal Hal's results: S(p,k) = number of solutions to the Markoff equation from GF(p,k) S(2,k) = 4^k + 1 {C(2,k)} = number of components = {2,3,4,5,9 or 10, 17,18,31...} here Hal knows his code has a bug, so he wants someone to check it. {S(5,k)} = {41, 701,16001,...} Next Jim attempted to convey to us the link between necklaces and the number of elements in a finite field. Necklaces have two colors and can be rotate to make the same necklace, but not flipped. Carl comes up to the board to explain what people had done after SSL on Thursday. Looking at the plane divided up by 30-60-90 triangles and trying to correspond the distance between to vertices to the Markoff brother equation x^2 + 2 y^2 + 3 z^2 = 6xyz. Found that taking a certain triangle that has a 12 degree vertex, a 6 degree vertex and a 4 degree vertex the "length" of the sides, or the perfect matchings of the corresponding snake graph between the 4 degree vertex and the 6 degree vertex is 7. Between the 4 degree vertex and 12 degree vertex is 11, and between 6 and 12 is 1. (1,11,7) happens to be a triple of our markoff equation. Yeah! But easy to see that this is not always the case for any visible 4-6-12 triangle. Found one triangle of (1,25,153). Now we try 4-6-12 triangles that don't have any vertices inside. Get one of (1,7,9), which isn't a triple but each of the numbers are Markoff numbers of our equation. ** Jim suggests that over the break everyone look at what Neil Harriot wrote and specific rules about his triangle-Markoff relation. Martin volunteers to write a program that prints out the first 100 numbers of the x,y, and z components of the two Markoff brothers equations. This will help us study the triangulations. Jim asks if anyone else looked at other ways to tile the plane with polygons... no one did. Hal really wants someone to check his last program that he sent out and also make it more efficient. Martin has a conjecture about the number of triples mod p that are Markoff triples (see his email). He also points out that x^2 + y^2 + 2 z^2 = 4xyz is disconnected for mod 2 but the others are connected and x^2 + 2 y^2 + 3 z^2 = 6xyz is disconnected mod ?. He says he will do girth thing later. He also says he will look into making a program that calculates the automorphism (relabeling of vertices st. vertices still have the same neighbors) group of the graphs. Jim forwarded Issac's email to us, and one about Newton's algorithm in 1 variable (including a conjecture, as well as a generalized version of this conjecture expressed in terms of 2 non-commuting variables!). Jim explains the Newton's algorithm email: approximate Maple code: > R:= proc(n) if n=0 then x else simplify(R(n-1-p(R(n-1))/q(R(n-1)); fi; end; > p:= proc(t) a*t^2 + b*t + c; end; > q:= proc(t) 2*a*t + b; end; look at coeffients of rational polynomials R(n) >coeffs(numer(R(3))); >lcm(%); >ifactor(%); lcm of the numerator coefficients are < 2^n where n is R(n). find it's exactly the same for the denominator coefficients (remember to expand first though) Jim's explanation of Non-commuting variables: If yx = qxy (and qx = xq and qy = yq but xy != yx) then (x + y)^2 = (x + y)(x + y) = xx + xy + yx + yy = xx + xy + qxy + yy = x^2 + (1 + q)xy + y^2. So (x + y)^6 has 2^6 = 64 terms, etc. We can represent this combinatorially with a lattice where x is 1 unit of horizontal movement and y is one unit of vertical movement. So if you have a 3 step staircase, the string would be xyxyxy = q^3*x^3*y^3, where the exponent in "q^3" tells us that the area under the path is 3. So the binomial equation is (x + y) = sum over k from 0 to n ([n k]_q * x^k * y^(n-k)) where [4 2]_q = [(1+q+q^2+q^3)(1+q+q^2)] / [(1+q)(1)], etc.