SSL Minutes for 3/4/04 Notes: Carl Snacks: Jim's Birthday Surprise Next time: Notes: Hal Snacks: We forgot to pick someone. (Carl will bring something next time if no one else has high hopes of providing something) SSL Starts right up! Sam has been looking at "A=B", the automatic theorem prover, and suggests we use it. A small debate arises as to whether we actually know what to ask it to prove yet: Hal/Carl - for the specific case of the newton recurrence (a=1,b=1,c=-1), it now seems that something went wrong with our empirical explicit formula using Fibonacci numbers, but we don't understand why yet... Jim enters with distinguished guest, Rick Kenyon. Before talking about what we're working on / how things are going, how did VIGRE go on Wednesday? Sam/Emilie - Talked mostly about SSL. Big question was, "do you write a lot of stuff up?" (our emphasis in SSL has not been as heavily on writing things up though..) Jim says, Gloria says "We love your undergrads!" so that is encouraging. Next Tuesday: we will be having the interviews again, about how you thing things are going, etc. We won't be assigning time slots though. [Jim will get more markers for B107] Emilie - has a conjecture for the family of recurrences a(n) a(n-k) = a(n-1) a(n-k+1) + a(n-(k-1)/2) a(n-(k+1)/2) a(n) = [1/2 (k^2 + 1) + 3k] (a(n-k+1) - a(n-2k+2)) + a(n-3k+3) Jim - Fundamental theorem of linear recurrences says we can write the solutions to the recurrence in terms of exponential functions in which the bases of the exponentials are the roots of the characteristic polynomial. In the case of the Fibonacci numbers, the characteristic polynomial is x^2 - x - 1 = 0. We will be able to find an explicit formula for the roots of the characteristic polynomial of the a(n) recurrence. m = k - 1 r = 1/2 (k^2 + 1) + 3k a(n) = r (a(n-m) - a(n-2m)) + a(n-3m) a~ = r (T^m a~ - T^(2m) a~) + T^(3m) a~ (T^(3m) - r T^(2m) + r T^m - I) a~ = 0~ (Here a~ is the two-sided infinite sequence ...,a(-1),a(0),a(1),..., 0~ is the all-zeroes sequence, T is the shift-operator that sends a~ to b~ where b(n) = a(n-1), and I is the identity operator that sends a~ to a~. Thm: If p(T) has distinct roots lamda1, lamda2, ... then the general solution to p(T) (a~) = 0~ is of the form a(n) = c1 lamda1^n + c2 lamda2^n + ... (There's a more complicated formula that applies when p(T) has multiple roots, but we don't need it here.) p(x) = x^(3m) - r x^(2m) + r x^m - 1 = (x^m - 1) (x^(2m) - (r-1) x^m + 1) = (x^m - 1) (x^m - (((r-1) + sqrt(r^2 - 2r - 3))/2) (x^m - (((r-1) - sqrt(r^2 - 2r - 3))/2) And it's easy to find the roots of these: if we write this as (x^m - 1) (x^m - A) (x^m - B), then the roots are precisely the numbers of the form zeta^n, alpha (zeta^n), and beta (zeta^n), where zeta ranges over all the complex mth roots of 1, alpha is an mth root of A, and beta is an mth root of B. The whole Newton's method problem gets brought up again. Jim thinks there will be a connection with continued fractions. To be specific about this, let's define polynomials p_n and q_n so that what we called P_n before is the same as p_(2^n) and what we called Q_n before is the same as q_(2^n) (but let's stick to the P's and p's for now). Newton's algorithm is a way to get from p_(N) to p_(2N), whereas the continued fraction algorithm is a way to get from p_(N) to p_(N+1). Newton's algorithm is a much faster way to get good approximations, but in some ways its very speed makes it hard to analyze (witness the trouble we're having proving our formulas). It might be helpful to come up with a conjectural "continued-fraction" formula relating p_(N) and p_(N+1). [ Jim's birthday cake is excellent! Happy Birthday Jim! ] [ Sadly, his birthday song wasn't very long... ] Continuing with the Newton's method theme, Rick suggests looking at the complex Mobius transformation z |--> (az + b)/(cz + d) that maps the two roots to 0 and infinity AND maps the bisecting line (in the complex plane) to the unit circle. Try roots 1,-1 f(z) = (z+1)/(z-1) (sends 1 -> inf, -1 -> 0) f^(-1)(z) = (z+1)/(z-1) = f(z) p(x) = x^2 - 1 p'(x) = 2x z |--> z - p(z)/p'(z) = (z^2+1)/(2z) applying f^(-1)([f(z)]^2) is equivalent to applying Newton's method. p(z) = az^2 + bz + c N_p(z) = z - p(z)/p'(z) N_p z --------> N_p(z) | | M | | M V S V zeta -------> zeta^2 where M is the Mobius transformation that sends r1 -> 0, r2 -> inf and S is the squaring map that sends zeta to zeta^2 N_p = M^(-1) o S o M (here "o" denotes composition of functions) (N_p)^n = M^(-1) o S^n o M S^n is the map that sends zeta to zeta^(2^n), which is comparatively easy to understand; so this could give us a good way to understand the nth iterate of the Newton map N_p associated with the polynomial p. Does something like this work for some cubics? p= z^2 (z-1) N_p(z) = (2z^2 - z) / (3z -2) ~~> z^2 + c | | Related to taking | iterates of: V w |--> (w^2 + w)/2 } } related by z |--> z^2 + 1/4 } mobius } transformations z |--> (2z^2 - z)/(3z - 2) } These should be analogous to Newton's method; Interesting sequences to try.. Are there any instances of Newton's method that are conjugate to z -> z^3 ? (Rick says No, ... or at least it can't involve simple rational functions.) The others have been working in B107 on their mathematical monsters. (Trying to make them into nice, respectable, tame monsters though..) Martin will be getting Magma tomorrow, OR ELSE BE CAST INTO THE VOLCANO! But that's how things go here at sizzle :) A parting observation made at today's SSL session: "Two is the oddest prime."