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).