Notetaker for next time: Carl
Snackbringer for next time: Sam
Jim is at faculty meeting, so we just dive right into some fun math!
Hal: How do you prove that two polynomials are relatively prime?
Sam: What does that mean?
Hal: They have no common factors.
Sam: Can we prove by induction? Could we use recursive formulas?
We try this method and it works! Here it is:
-------begin proof-------
P_{n+1}=a*P_{n}^2-c*Q_{n}^2
Q_{n+1}=Q_{n}*(2*n*P_{n}+b*Q_{n})
Base case: P_{0}=x, Q_{0}=1 or y, either way gcd(P_{0},Q_{0})=1
Assume gcd(P_{n},Q_{n})=1 show by induction that gcd(P_{n+1},Q_{n+1})=1.
Well, assume otherwise. That is, there exists some d (an irreducible
polynomial) which divides both P_{n+1} and Q_{n+1}. Since d is irreducible
its degree is >0.
By our assumption that d|P_{n+1} and d|Q_{n+1} it is true that
d|b*P_{n+1}+c*Q_{n+1}. d|b*(a*P_{n}^2-c*Q_{n}^2)+c*(Q_{n}*(2*n*P_{n}+b*Q_{n}))
d|a*b*P_{n}^2+2*a*c*P_{n}*Q_{n}
d|(a*P_{n})(b*P_{n}+2*c*Q_{n})
case 1: d|a*P_{n} implies d|a*P_{n}^2, and since by our assumption that
d|P_{n+1}, d must divide P_{n+1}-a*P_{n}^2. So d|-c*Q_{n}^2. Since d is
irreducible d|Q_{n} and we have that d divides both P_{n} and Q_{n}.
This is a contradiction to gcd(P_{n},Q_{n})=1. So case 1 leads to a
contradiction.
case 2: d|b*P_{n}+2*c*Q_{n} ( call this (*) )
>From our assumption that d|Q_{n+1}, we have d|Q_{n}*(2*n*P_{n}+b*Q_{n})
Now we have two more sub-cases.
case 2.1: d|Q_{n} and d|b*P_{n}+2*c*Q_{n}
Since d divides b*P_{n}+2*c*Q_{n} and Q_{n}, d also divides their difference
(with appropriate constants). So d|P_{n}. But this is another contradiction
because d|Q_{n} and d|P_{n}. So d|Q_{n} leads to a contradiction.
case 2.2: d|2*n*P_{n}+b*Q_{n} and d|b*P_{n}+2*c*Q_{n}
So d|2*a*(b*P_{n}+2*c*Q_{n})-b*(2*n*P_{n}+b*Q_{n})
d|(4*a*c-b^2)*(Q_{n})
So as long as 4ac-b^2 does not equal zero (the roots are distinct) d|Q_{n}
which we've already established is a contradiction.
Now we've gone through all the cases and we have contradictions in each case.
So we're done with our proof!!
-----end of proof------
Now we go into a sort of random discussion on whether or not negative infinity
exists. Paul is very opposed to the notion of negative infinity. In fact, he
goes as far to say that pink elephants are more likely than negative infinity.
Carl then draws a pink elephant on the board. And Carl aparently has a lot of
time on his hands because he sent me (after the meeting) an email. Now we will
all marvel at Carl's wonderful ascii art:
{ }
{ __ _|_|_ __ }
{ ( ) / \ ( ) }
{ ( _ )/ 0 0 \( _ ) }
{ ( \\____/ \____// ) }
{ ( \____| |____/ ) }
{ ( ) | | ( ) }
{ (__) / / / (__) ...----````)@- }
{ _.(/ /..)._ `` ...--- ) }
||\ | . { ( | | ) ---``` ) }
|| \ | |_| { ( | | ) ) }
|| \| { ( | | ) ) }
{ ( | | ) ) }
{ ( | | ) ) }
{ ( | / ) ) }
{ ( |/ ) .... ) }
{ ( ) ---``` ( ) }
{ ( )\/\/\/( ) ) ( ) }
{ ( ) ( ) ) ( ) }
{ ( ) ( ) ) ( ) }
{ ( ) ( )__) (___) }
{ ( ) ( ) }
{ (____) (____) }
( }
//
//
( ,,, )
L ( OO8) )
( ``` )
Now that's what I call quality math! Anyways...back to SSL stuff....
Jim is done with his faculty meeting. He joins us and asks what we have been
doing. We explained the above proof of P_{n} and Q_{n} relative primality.
Hal: should we include this in our paper, or just mention it as "an exercise
for the reader"??
Jim: definetely include it. And also, the fact that we treat a,b,c not as
formal variables really isn't a problem.
Carl volunteers to be the one to write up the proof of relative primality in
pretty latex for the paper.
Jim: so what else happened?
Martin: steven and i went to the computer lab and talked about the
automorphism groups.
Jim: let's leave the automorphism groups alone for now and look instead at the
expansion properties of the markoff graphs.
Martin: if you get the spectrum of the graph and it's under a certain constant,
then the graphs are expander graphs. Magma has a way of computing the spectrum
of a graph so I'll work on that!
Hal: Is it interesting that the only automorphisms of the graphs are the
obvious automorphisms??
Jim: not really. but if the graphs are expander graphs then it could be
interesting. since graphs are so easy to make up they are hard to publish
theorems about unless the graphs are usefull like expander graphs.
What Jim has been thinking about:
How to get the EP (Emilie and Paul) problem "over the hump". He looked at Reid
Barton's work and also at straight snakes. He came to the conclusion that it
is going to be very hard to find the combinatorics behind the EP sequences
since they are pretty different than other sequences. Why are they different...
because it's two quadratic and two linear terms instead of the "traditional"
two quadratic terms or one quadratic term and one linear term.
BREAK TIME! chips, fig newtons, and diet coke are provided by carl! thanks
carl!!
After the break Jim explains the combinatorics behind Reid Barton's sequence.
The sequence codes routings in this type of lattice:
\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /
\/ \/ \/ \/ \/ \/ \/ \/ \/ \/ \/
\ /\ /\ /\ /\ /\ /\ /\ /\ /\ /
\/__\/__\/__\/__\/__\/__\/__\/__\/__\/
\ /\ /\ /\ /\ /\ /\ /\ /\ /
\/ \/ \/ \/ \/ \/ \/ \/ \/
\ /\ /\ /\ /\ /\ /\ /\ /
\/ \/ \/ \/ \/ \/ \/ \/
oh yeah, and the sequence is a(n)a(n-2)=a(n-1)^2+a(n). Reid Barton proves this
combinatorics by first proving that the following determinant is 1.
|a(n) a(n+1) a(n+2)|
|a(n+1) a(n+2) a(n+3)| = 1
|a(n+2) a(n+3) a(n+4)|
This routings lattice corresponds to the folling array of hexagons.
_ _ _ _ _ _ _ _ _ _
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/
\ / \ / \ / \ / \ / \ / \ / \ / \ / \ /
\_/___\_/___\_/___\_/___\_/___\_/___\_/___\_/___\_/___\_/
\ / \ / \ / \ / \ / \ / \ / \ / \ /
\_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/
\ / \ / \ / \ / \ / \ / \ / \ /
\_/ \_/ \_/ \_/ \_/ \_/ \_/ \_/
This is equivalent to:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
Jim thinks that maybe the graphs for the EP sequences could look like:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
or perhaps:
_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _
_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|_|
Unfortunately Jim thinks that it will be very hard to figure out the
combinatorics in the limited amount of time we have left in the semester.
Jim wants Emilie and Paul to concentrate on writing up the work they've
already done.
Now we go into the computer lab for the last 10 mins or so and work.
The end. See you next week!