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!