SSL Meeting 03/02/04 Notetaker: Brendan Snacks: Paul Next Time Notetaker: Carl Snacks: Surprise! (courtesy of Jim ) The Milewski Visit Need to give Paul Milewski an overview of the projects we are currently working on as well as tips on how to run something like SSL/CURL in the future. Also, we need to practice for the dreaded VIGRE visit on Weds. +Project 1: Newton's Method for Quadratics Sam begins explanation. Most recent development is the following: Sum[ Binomial[ 2^n, k ] Binomial[ 2^n, N - k} ] ( Fibonacci[ k ] Fibonacci[ N - k ] - 2 Fibonacci[ N - k ] ), {k, 0, N}] =?= Binomial[ 2^(n + 1), N ] Fibonacci[ N ] The question is whether this is true for (lots) of values of N. The question has been raised as to whether 2^n can be replaced by a variable u which can take on non-powers of two values. If so, this is a prime candidate for automated proof. Hal and Sam also seem to believe that, with this proved, we can retroactively add the a, b, and c values back in. As a side note for the VIGRE visit, we probably won't be able to go into such detail and it might be good to just give the executive summary first. We could start out by giving the background of the problem, mention that we came up with a conjecture, and say a little about how we might solve it. We should also mention that this is interesting since the analogous problem for cubics and quartics and higher does not work. Along these lines, Milewski suggests that we might profitably spend out time working out why it doesn't give nice polynomials for the cubic and higher polynomials. He suggests that, because Newton's method does not always converge for cubics and higher that we might restrict our attention to polynomials with only real roots or polynomials without inflection points. That it works for quadratics may be because the formula for the distance to the root in the complex plane uses the second derivative, which is a constant. Jim suggests that perhaps bounded derivatives might provide the same behavior. +Project 2: Quadratic Recurrences Paul starts off with the most recent and interesting general form which he and Emilie have found: A_N * A_N-K = A_N-1 * A_N-K+1 + A_N-floor(K/2) + A_N-ceil(K/2) (where K is a fixed parameter and N is a variable). This works for any K, either odd or even. When K is even, it's almost like Reid Barton's recurrence. Paul also put forth an interesting general family of recurrences: A_N * A_N-K = A_N-L * A_N-M + A_N-O + A_N-P where the parameters K,L,M,N,O,P satisfy L,M < K and L + M = K and O + P = K. What is interesting here is that the sequence of values is not monotonically increasing. He also noted that eventually the sequence arrives at a fixed point and that this fixed point becomes larger as K grows. [Comment from Jim: I don't think this last sentence says exactly what Paul meant, but I can't figure out a good concise way to say it; presumably Paul will give us more details soon.] Emilie also mentions that she's been doing work on finding linear recurrences for these quadratic recurrences by using Hankel matrices. For instance, with the Fibonacci numbers, [ 1 1 2 ] [ 1 ] [ 1 2 3 ] [ 1 ] = [ 0 ] [ 2 3 5 ] [ -1 ] Jim notes that trying to get a linear recurrence from a quadratic one is not terribly well understood right now. He reminds us of one problem in Math 491 wherein we proved that x,y,(y^2 + 1) / x, (((y^2 + 1) / x) + 1) / y, etc. gives Laurent polynomials, by proving that the terms can be expressed as A_N = A_N-1 * p(x,y) + A_N-2 * q(x,y) where p(x,y) and q(x,y) are Laurent polynomials. Also notes that when the coefficients are positive, this is both remarkable and hints at deeper theory. Milewski notes that you can take an nth-order recurrence and get a corresponding nth-order differential equation; we might want to look at this already. Milewski then leaves. Hal now says that he's been working on the Newton's method equation presented earlier and that (he thinks) by taking out the Fibonacci numbers, the equation still holds. Jim suggests that this might be proved via Vandermonde convolution. John Vano and Sam agree to work together on the A = B computer proof. Now the discussion centers on the number-fence recurrence studied by David Speyer and Reid Barton, namely A B C D E AE=BD+C . This is to be considered as a variant of A B C D AD = BC + 1 There follows a small disagreement about what exactly the recurrences were and how they were solved and what was equivalent to what . . . it was over my head. Finally, Jim suggests that we look at A B C D E A B C D E A B C D E with the rule that AE = BD + C and extend it outwards to a larger rhombus and see if it gives "good" values. Postscript by Jim: We tried this in the computer room, and Jim and Hal found that we do indeed get good values. Indeed, if we put subscripts on the A's, B's, C's, and D's, so that they all correspond to distinct variables, then the E's, F's, etc. can all be expressed in terms of these variables, and they appear to be the very best kind of rational functions we know (the best kind for the purposes of combinatorics, at least): faithful Laurent polynomials! This suggests that the terms of the Dana Scott sequence 1, 1, 1, 1, 2, 3, 5, 13, 22, 41, 111, 191, 361, 982, 1693, 3205, ... (satisfying a(n) a(n-4) = a(n-1) a(n-3) + a(n-2)) have a combinatorial meaning. Meanwhile, Emilie and Carl (I think it was they) used Maple's linear algebra capabilities to find a linear recurrence relation satisfied by the term of this sequence, namely, a(n) - 10 a(n-3) + 10 a(n-6) - a(n-9).