SSL Minutes
2004-02-10

>From now on, we will start Tuesday at 3:45 and Thursday at 3:30.

Jim will post an announcement.

Thursday's notetaker is Carl,
Thursdays Refreshment bringer is Stephen.

URS (Undergraduate Research Symposium): Should we do it? We need
people to be excited about it first.

Contracts were signed.

Jim may not be here Thursday.

Carl looked at AB+CD=EFG.  It is not Laurent.

Jim: Let's look at [a_n a_{n-4} = a_{n-2} a_{n-3} + 1]

THEOREM: [a_n a_{n-4} = a_{n-2} a_{n-3} + 1] always gives integers if
the initial conditions are (1,1,1,1).

PROOF:

Here is the beginning of the sequence:

	1, 1, 1, 1, 2, 3, 4, 9, 14, 19, 43, 67, 91, 206, 321, 436,...

Make a number fence:
                                    1     1 
				 1     1    
                        1     1     2     4 
                     1     1     3     9    
            1     1     2     4     14    43
         1     1     3     9     19    67
1     1     2     4     14    43    91    321
   1     3     9     19    67    206   436
2     4     14    43    91    321   987   2089
   9     19    67    206   436   1538  4729

Choose a number , say 9.  Look at everything above that:
                                    1
				 1
                        1     1
                     1     1
            1     1     2
         1     1     3
            2     4
               9

Consider this a digraph pointed left to right.  Look at the number of
routes on this graph from the leftmost point to the rightmost.  It is
9!

Try 19:                 1
                       /
		      1
                     /                    
                1   1
               / \ /
              1   1
             / \ /
        1   1   2
       / \ / \ /
      1   1   3
     / \ / \ /
1   1   2   4
 \ / \ / \ /
  1   3   9
   \ /
    4

Leave off everything below the first two rows:  1-d object.  The
number of routes from the left 1 to the right 1 is 19!

We will use Lindstrom's Lemma.

Define Number in the array as counting the numbers of routings from
the left side to the right side.  Then use the lemma to show that
AD=BC+1 holds.

Hal points out that Kuo's theorem might be applicable to the hexagons.
He will look into it.

Lindstrom's Lemma says that given a network with 2 sources and 2
terminals with a unique pairing, if N(s_i,t_j) is the number of paths
from s_i to t_j, then the determinant

| N(s_1,t_1) N(s_1,t_2) | = Number routing that pair s_1 to t_1 AND
| N(s_2,t_1) N(s_2,t_2) |    s_2 to t_2.  (In this case 1.)

Then we can prove that given 

	  3
	4   14
	  19

	| 3  4  | = 1
	| 14 19 |

	3 * 19 = 4 * 14 + 1
	
This proves that the fence of integers defined by the routing on those
lattices satisfies the recurrence, because this works with any group
of four numbers in the lattice.  QED.

ALSO, we can think in terms of hexagons.
                                    1
				 1
                        1     1
                     1     1
            1     1     2
         1     1     3
            2     4
               9

can be turned into hexagons:
                     _/
               _   _/
             _/9\_/
       _   _/7\_/
      /2\_/5\_/
      \_/3\_/
        \_/

There are 9 matchings.  This works as well.

What about Laurent polynomials? 

            y
	   / \ /
	  x   z
	 / \ / 
	w   ? = (xz+1)/y
         \ /
	  ? = (w(xz+1)/y +1)/x = (xwz+w+y)/xy


Three matchings correspond to:
         _
       _/y\
      /x\_/z	1/x	= w x^2 y^2 z * w^{-1} x^{-3} y^{-2} z^{-1} 
     w\_/
         _
       _/y\
      /x\_/z	wz/y	= w x^2 y^2 z * w^{0}  x^{-2} y^{-3} z^{0} 
     w\_/
         _
       _/y\	w/xy	= w x^2 y^2 z * w^{0} x^{-3} y^{-3} z^{-1} 
      /x\_/z
     w\_/


So, here are the weights:

	                  1/y
	                O-------O
	               /         \
	          1/y /           \1/y
	      1/x    /             \
	    O-------O               O
	   /         \             /
	  /1/x        \1/xy       /1/yz
	 /             \         /
	O               O-------O
	 \             /    1/y
	  \1/wz       /
	   \         / 1/x
	    O-------O
                1/x

Multiply the weights, then multiply by (w x^2 y^2 z).  Is complicated.

Jim would like someone to document this nicely.

We discussed growth rates.  Most of these are O(x^n).  Some are
O(x^{n^2}). It would be neat to find an interesting O(x^{n^3})
sequence.

BREAK.

Sam would like to look at this.

Carl wants to look at that cubic recurrence from before.

Stephen has been looking at the lifting problem.

Paul has been looking at 

	a_n a_{n-3} = a_{n-2} a_{n-1} + a_{n-2} + a_{n-1}

Hasn't gotten anything interesting yet, but then we discussed his
methods.  If you shift the problem (number wall becomes number fence)
then be CAREFUL with your initial conditions.

Jim tells us that undergrads will be given access to B107 by way of
keypad.  Be careful and don't break anything.