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.