Problem 9.1 (Final Fraction; 10, 10, 10, 10 ) . In all but the last sub-problem here, assume that k is a k k fixed positive integer and we examine elements of AGL ( Z / 2 Z ) or GL ( Z / 2 Z ) as the problem dictates. 2 2 k Vectors are arbitrary element ( ~ v, M ) ∈ AGL ( Z / 2 Z ) . 2 a) Error notice: The problem originally stated here was incorrectly phrased. Due to the fact that we are sending out a revision so late, we are awarding everyone the full 10 points for this problem. The problem should have been Proposition 39, which you may assume is true. n n 2 b) Suppose that a, b ∈ Z / 2 Z , c ∈ Z / 2 Z , and n ≥ 2 . Prove the number of pairs ( α, β ) ∈ ( Z / 2 Z ) with n αβ ≡ c (mod 2 ) with α ≡ a (mod 2) and β ≡ b (mod 2) is  0 ab 6 ≡ c (mod 2) ,     n − 1 2 ab ≡ 0 (mod 2) and one of a or b is nonzero , n − 1 n  (2 − 1)( v ( c ) − 1)2 a ≡ b ≡ c ≡ 0 (mod 2) , c 6 ≡ 0 (mod 2 ) , 2    n − 1 n n 2 a ≡ b ≡ c ≡ 0 (mod 2) , c ≡ 0 (mod 2 ) . k k − 1 c) For k ≥ 1 , prove the number of matrices M ∈ GL ( Z / 2 Z ) with det( M − I ) ≡ 0 (mod 2 ) but with 2 k det( M − I ) 6 ≡ 0 (mod 2 ) is { 2 k = 1 , 3 k − 2 2 k − 1 3 · 2 − 3 · 2 k ≥ 2 . 11 d) Prove that the density of primes dividing a term of the Somos-4 sequence is . 21 We present the proofs separately. For part b), we may in fact prove a generalization of the problem for any prime . n Lemma 40 (Generalization of b)) . Suppose that a, b ∈ Z /` Z , c ∈ Z /` Z , and n ≥ 2 . Then, the number of n n pairs ( α, β ) ∈ ( Z /` Z ) with αβ ≡ c (mod ` ) with α ≡ a (mod ` ) and β ≡ b (mod ` ) is  0 ab 6 ≡ c (mod )     n − 1 ` ab ≡ c (mod ` ) and one of a or b is nonzero . n − 1 n  ( ` − 1)( v ( c ) − 1) ` a ≡ b ≡ c ≡ 0 (mod ` ) , c 6 ≡ 0 (mod ` )    n − 1 n ( n` − n − ` + 2) ` a ≡ b ≡ c ≡ 0 (mod ` ) , c ≡ 0 (mod ) . 31 PUMaC 2015 Power Round Section 9 page 32 Proof. We count satisfactory solutions ( α, β ). • It is clear that if ( α, β ) is a solution then c ≡ αβ ≡ ab (mod ). − 1 n • If a or b is nonzero, then α or β is invertible. If α is invertible it suffices to solve β ≡ α c (mod ). n − 1 There are choices for α , and once α is chosen, β is fixed. Similarly, if β is invertible, there are n − 1 solutions. n • If c 6 = 0 suppose that i = v ( α ). Then, the congruence αβ ≡ c (mod ) is equivalent to α ′ n − i β ≡ c (mod ) , i ′ i n − i i where c · ` ≡ c (mod ` ). Then, α/is invertible, and hence we have ( ) − 1 α n − i β ≡ c (mod ) . i n − i n − i − 1 i There are ` − ` choices for α and there are choices for β . Moreover, 1 ≤ i ≤ v ( c ) − 1 and hence we have v ( c ) − 1 ∑ n − 1 n − 1 ( ` − 1) ` = ( ` − 1)(ord ( c ) − 1) ` . ` i =1 • If c = 0, and a = b = 0 then all that we require is v ( α ) + v ( β ) ≥ n . The number of solutions is then ` ` n − 1 ∑ n − k n − 1

{ α : v ( α ) = k } · # { β : β ≡ 0 (mod ` ) } + `

k =1 n − 1 ∑ n − k n − k − 1 k = ( ` − ` ) · k =1 n − 1 ∑ n n − 1 n − 1 = ( ` − ` ) + k =1 n − 1 n − 1 n − 1 = ( n − 1)( ` − 1) ` + ` = ( n` − n − ` + 2) ` . Secondly, here is a lemma necessary for the proof of 9 . 1 c ): 3 Lemma 41. The number of M ∈ GL ( Z /` Z ) for a prime ` such that det( M − I ) = 0 is ` − 2 ` . 2 We do not present a full proof here, as it is unnecessary to prove in generality for our problem that only 1 0 1 1 1 0 considers ` = 2. Note namely that it holds for ` = 2 because the four such matrices are [ ], [ ], [ ], 0 1 0 1 1 1 0 1 and [ ]. 1 0 n n − 1 Lemma 42. For n ≥ 1 , the number of M ∈ GL ( Z /` Z ) with det( M − I ) ≡ 0 (mod ` ) but det( M − I ) 6 ≡ 2 n 0 (mod ) is { 4 3 2 ` − 2 ` − ` + 3 ` n = 1 2 3 n − 2 2 2 n − 1 ( ` − 1) ( ` + 1) ` − ( ` − 1) n ≥ 2 . 32 PUMaC 2015 Power Round Section 9 page 33 Proof. First we deal with the n = 1 case. In this case, it suffices to count the number of M ∈ GL ( F ) with 2 2 det( M − I ) = 0. Using lemma 41 and the fact that | GL ( F ) | = ( ` − 1) ` ( + 1), the result follows for n = 1. 2 n Now assume that n ≥ 2. First, we count the number of matrices M ∈ GL ( Z /Z ) with 2 [ ] α β M − I = γ δ [ ] a − 1 b and ord (det( M − I )) = n − 1. If M − I ≡ (mod ), then the number of such is ` c d − 1 n ` − 1 ` ∑ ∑ n − 1 n

{ ( α, δ ) : αδ ≡ i + ` (mod ` ) , α ≡ a − 1 (mod ` ) , δ ≡ d − 1 (mod ` ) }

=1 i =1 n · { ( β, γ ) : βγ ≡ i (mod ` ) , β ≡ b (mod ` ) , γ ≡ c (mod ) } . [ ] [ ] 1 b a 0 Case I: M 6 ≡ (mod ` ) and M 6 ≡ (mod ` ). c 1 0 d In this case, we never have a − 1 ≡ d − 1 ≡ 0 or b ≡ c ≡ 0. Hence, from lemma 40, the number of 2 n − 2 solutions is either 0 or ` . We must have ( a − 1)( d − 1) ≡ bc ≡ i (mod ` ), and hence the only restriction n − 1 is that i lie in a particular residue class mod ` . Hence, any choice of is fine, and there are ` choices for 3 n − 3 i . Thus, the number of solutions is ( ` − 1) ` . How many matrices M ∈ GL ( F ) satisfy the assumptions 2 of this case? [ ] 1 a 2 2 There are ( ` − 1) diagonal matrices M , and ` − + 1 matrices M so that M = . The only overlap b 1 in these two categories is in the identity matrix. Thus, there are a total of 2 2 2 ( ` − 1) + ( ` − ` + 1) − 1 = 2 ` − 3 + 1 3 excluded matrices. The number of matrices M with det( M − I ) = 0 is ` − 2 ` from lemma 41. Hence, the number of matrices covered in this case is 3 2 3 2 ( ` − 2 ` ) − (2 ` − 3 ` + 1) = ` − 2 ` + − 1 . Thus, the total for this case is 3 2 3 n − 3 ( ` − 1)( ` − 2 ` + ` − 1) . [ ] a 0 Case II: M 6 ≡ I (mod ` ) and M ≡ (mod ` ). 0 d 2 In this case, ( a − 1) and ( d − 1) are not both zero, but b and c are. This implies that i ≡ 0 (mod ). n − 1 Moreover, any choice for will work. There are solutions for ( α, δ ). However, for ( β, γ ) there are n − 1 n − 1 ( ` − 1)(ord ( i ) − 1) ` solutions if i 6 = 0 and if i = 0 there are ( n` − n − ` + 2) solutions. This gives a total of ∑ n − 1 2 n − 1 2 n − 2 ` ( ` − 1) (ord ( i ) − 1) ` + ( n` − n − ` + 2)( ` − 1) n i ∈ ` Z /` Z ,i 6 =0 solutions. The first term above is ∑ 2 2 n − 2 ( ` − 1) ` ord ( i ) − 1 n i ∈ ` ( Z /` Z ) ,i 6 =0 n − 1 ∑ 2 2 n − 2 n − k − 1 = ( ` − 1) ` ( k − 1)( ` − 1) ` k =2 n − 2 ∑ 3 2 n − 2 n − k − 2 = ( ` − 1) ` k . k =1 Now, n − 2 n − 1 ∑ ` − ( n` − n − + 2) n − k − 2 k = . 2 ( − 1) k =1 33 PUMaC 2015 Power Round Section 9 page 34 Hence, the total number of these matrices with M (mod ) fixed is 2 n − 2 n − 1 2 n − 2 ( ` − 1) ` ( ` − ( n` − n − ` + 2)) + ( ` − 1) ` ( n` − n − + 2) 3 n − 3 = ( ` − 1) ` . 2 As there are ` − 2 ` choices for the reduction of M mod , the total number of such matrices is 3 n − 2 ( ` − 2)( ` − 1) . [ ] 1 b Case III: M ≡ (mod ) with b and c not both zero. c 1 In this case it is more convenient to compute n ` − 1 ` ∑ ∑ n

{ ( α, δ ) : αδ ≡ i (mod ` ) , α ≡ a − 1 (mod ` ) , δ ≡ d − 1 (mod ` ) }

i =1 β =1 n − 1 n · { ( β, γ ) : βγ ≡ i − β` (mod ` ) , β ≡ b (mod ` ) , γ ≡ c (mod ` ) } . 2 Since a − 1 ≡ d − 1 ≡ 0 (mod ` ) we must have that i ≡ 0 (mod ` ). Since b and c are not both zero, we n − 1 have that there are ` choices for ( β, γ ) for any i ≡ bc (mod ` ) and any . Thus, the number of matrices with M mod fixed is n − 1 ∑ n − 1 n − 1 2 n − 2 ( ` − 1) ` ( ` − 1)(ord ( i ) − 1) ` + ( ` − 1)( n` − n − ` + 2) ` . n i ∈ ` ( Z /` Z ) ,i 6 =0 3 n − 3 2 This is the same contribution as from Case II and is hence ( ` − 1) ` . In this case, there are ` − ` choices for M mod giving a total of 2 3 n − 2 ( ` − 1) ` matrices. Case IV: M ≡ I (mod ). 2 2 In this case, β ≡ γ ≡ 0 (mod ` ) and hence i ≡ 0 (mod ` ). If n = 2, then 0 ≡ αδ ≡ i + ` (mod ` ), a contradiction and so there are no solutions in this case. Assume therefore that n ≥ 3. We then have that the total number of matrices is ∑ 3 2 n − 2 n − 1 ( ` − 1) ` (ord ( i ) − 1)(ord ( i + ) − 1) ` ` n n i ∈ ` ( Z /` Z ) ,i 6 =0 ,i 6 = − 2 2 n − 2

• 2( ` − 1) ( n − 2)( n` − n − ` + 2) ` . n n Note that if i 6 = 0 and i 6 = − ` then ord ( i ) = ord ( i + ` ). Hence, the first term above is ` ` n − 2 ∑ 3 2 n − 2 2 n 3 2 n − 2 2 ( ` − 1) ` k # { i ∈ ( Z /` Z ) : ord ( i ) = k + 1 } − ( ` − 1) ( n − 2) . k =1 n − 1 The subtracted term takes account for the i = − term which was omitted above. The above sum is n − 2 2 ∑ k 4 3 n − 4 3 2 n − 2 2 ( ` − 1) ` − ( ` − 1) ` ( n − 2) . k k =1 We now make use of the identity m 2 m +3 2 m +2 2 m +1 2 ∑ m x + (1 − 2 m − 2 m ) x + ( m + 1) x − x − x 2 n n x = . 3 ( x − 1) n =1 1 Taking x = and m = n − 2 we obtain n − 2 2 2 2 2 2 ∑ k ` ( ` + 1) ( n − 1) ` − (2 n − 6 n + 3) ` + ( n − 2) = − . k 3 n − 2 3 ` ( ` − 1) ` ( ` − 1) k =1 34 PUMaC 2015 Power Round Section 9 page 35 Hence, the total number of matrices is 3 n − 3 2 2 2 2 2 n − 2 ( ` − 1)( ` + 1) ` − ( ` − 1)(( n − 1) ` − (2 n − 6 n + 3) ` + ( n − 2) ) 3 2 n − 2 2 2 2 n − 2 − ( ` − 1) ` ( n − 2) + 2( ` − 1) ( n − 2)( n` − n − ` + 2) ` 2 3 n − 3 2 2 n − 1 = ( ` − 1) ` − ( ` − 1) ` . Note that this is zero for n = 2. Summing all the contributions, we get 2 3 n − 2 2 2 n − 1 ( ` − 1) ( ` + 1) ` − ( ` − 1) ` . Now finally, we have to prove the final equation concerning density 11 / 21. Proof. By Proposition 37, we have most of what we need to prove the density. We must calculate the fraction in the limit as described. We do this by checking the answer for k = 1, and then imagine lifting to higher k k − 1 and higher k values. Here are two facts as well: | AGL ( Z / 2 Z ) | = 24 · 64 (easily verifiable; exercise for 2 the reader! (it’s actually not that bad)). ∣ ∣ 1 ′ ∣ ∣ • Suppose k = 1. Note that AGL ( Z / 2 Z ) = 24, and we may manually check that | S | = 8. Thus the 2 density for k = 1 is 8 / 24 = 1 / 3. 1 • Suppose k = 2. Note that all 8 elements of AGL ( Z / 2 Z ) that were ruminative lift to elements that are 2 ( [ ]) u 2 a b k ruminative in AGL ( Z / 2 Z ). In general, note that ~ v = [ ] , ∈ AGL ( Z / 2 Z ) has 64 elements 2 2 v c d ([ ] [ ]) k k k u + { 0 , 2 } a + { 0 , 2 } b + { 0 , 2 } k +1 k α = , ∈ AGL ( Z / 2 Z ) such that α ≡ ~ v (mod 2 ). In this manner, k k k 2 v + { 0 , 2 } c + { 0 , 2 } d + { 0 , 2 } 1 2 we see that all 8 ruminative elements of AGL ( Z / 2 Z ) lift to 64 elements each in AGL ( Z / 2 Z ) that 2 2 are also ruminative. 2 Next, we must add elements of AGL ( Z / 2 Z ) that are ruminative but reduce modulo Z / 2 Z to non- 2 2 ruminative elements. These are the elements ( ~ v, M ) ∈ AGL ( Z / 2 Z ) such that det( M − I ) ≡ 0 2 (mod 2), det( M − I ) 6 ≡ 0 (mod 4), and such that ~ v is in the column space of M − I . By problem 9.1 6 − 2 4 − 1 d), note that there are 3 · 2 − 3 · 2 = 24 such matrices M , and by Proposition 39, each M has 8 such vectors. 2 Therefore in total, we have 8 · 64 + 24 · 8 = 702 ruminative elements of AGL ( Z / 2 Z ). Therefore the 2 704 11 density for k = 2 is = . (So we are getting closer!). 24 · 64 24 Thus in general, we may repeat this process indefinitely. At this point, we feel any major hurdle a team would have had in processing this problem is over, and leave the rest of the problem as a final exercise for you to think about :) k k − 1 As one last hint, we claim the number of ruminative elements inside AGL ( Z / 2 Z ) is 8 · 64 + 2 k ( ) ∑ 3 r − 2 2 r − 1 r +1 k − r k k − 1 (3 · 2 − 3 · 2 ) · 2 · 64 . Therefore, knowing that | AGL ( Z / 2 Z ) | = 24 · 64 , it suffices 2 r =1 to find the limit. We encourage you to work this out for yourself, but indeed, k ( ) ∑ k − 1 3 r − 2 2 r − 1 r +1 k − r 8 · 64 + (3 · 2 − 3 · 2 ) · 2 · 64 11 r =1 ′ k lim | S | AGL ( Z / 2 Z ) = = , 2 k − 1 k →∞ 24 · 64 21 and we are done! That’s it! We hope you’ve had a fun ride. 35 PUMaC 2015 Power Round Section A page 36 Appendices A Proof of Integrality We present the following facts about the sequence, including proofs that it is integral. As a quick remark, note one can extend the sequence into negative indices by using the recursive definition of d . Noting that n  2 d d − d n − 1 n − 3 n − 2  if n 6 ≡ 2 (mod 3) d n − 4 d = 2 n d d − 3 d n − 1 n − 3 n − 2  if n ≡ 2 (mod 3) , d n − 4 One has that for all n ∈ Z ,  2 d d − d n +3 n +1 n +2  if n 6 ≡ 1 (mod 3) d n +4 d = 2 n d d − 3 d n +3 n +1 n +2  if n ≡ 1 (mod 3) . d n +4 This fact will be used for establishing base cases in some proofs. Consider the following. Definition 43. For n ∈ N , define s := d d − d d . n n n +5 n +2 n +3 Lemma 44. For all n ∈ N , d s = d s . n +7 n n +1 n +3 Proof. For all k ∈ N , we hope to show d s = d s k +7 k k +1 k +3 ⇔ d d d + d d d − d d d − d d d = 0 . k k +5 k +7 k +1 k +5 k +6 k +2 k +3 k +7 k +1 k +3 k +8 Again after rewriting this expression with terms d through d , factoring, we may find h ( k + 3) = 0 is a k k +4 factor. And equivalently, d s = d s as desired. k +2 k k − 4 k +3 Corollary 45. For all n > 1 , { d d if n ≡ 0 , 1 (mod 3) n +1 n +4 s = n 3 d d if n ≡ 2 (mod 3) . n +1 n +4 Proof. Examine first the case n ≡ 0 mod 3. Computationally. s = d ∗ d − d ∗ d = ( − 3)(247) − ( − 17)(2) = 3 3 8 5 6 − 707 = ( − 7)(101) so the claim is true for n = 3. Now suppose for the sake of induction, suppose for all n ≤ k satisfy the claim for some k ≡ 0 mod 3. Then d d = s k +1 k +4 k d s k +1 k +3 d d = k +1 k +4 d k +7 = ⇒ s = d d . k +3 k +4 k +7 Thus by induction, for all n ∈ N , n ≡ 0 (mod 3), our claim is true. The other two cases modulo 3 are identical. This is sufficient to see integrality. 36 PUMaC 2015 Power Round Section 9 page 37 Proposition 46. For n ≥ 3 , both d ∈ Z and ( d , d ) = ( d , d ) = 1 . n n n − 2 n n − 1 Proof. Proceed by induction. Note that the first 4 terms are 1 , 2 , 1 , − 3 ∈ Z , so the base case is true. Suppose for all n ≤ k + 4 for some k that d is integral and the coprime condition is true. Note since n k + 1 < k + 4 that ( d , d ) = 1. By Bezout’s lemma, ∃ r, s ∈ Z such that 1 = rd + sd = ⇒ d = k k +1 k k +1 k +5 rd d + sd d . k k +5 k +1 k +5 2 By the definition of the sequence, for some coefficient c ∈ { 1 , 3 } , d d = d d − c d . Also 1 k +1 k +5 k +4 k +2 1 k +3 by the corollary above, d d − d d = s = c d d = ⇒ d d = c d d + d d , k k +5 k +2 k +3 k 2 k +1 k +4 k k +5 2 k +1 k +4 k +2 k +3 for some c ∈ { 1 , 3 } . Therefore by the inductive hypothesis, d d , d d ∈ Z , and d = rd d + 2 k +1 k +5 k k +5 k +5 k k +5 sd d ∈ Z as desired. k +1 k +5 To see that d is coprime to the three terms before it, note that ( d d , d d ) = 1 because by k +5 k +1 k +4 k +2 k +3 the inductive hypothesis, both d and d are coprime to d d . Thus k +1 k +4 k +2 k +3 ( d d , d d ) = 1 k +1 k +4 k +2 k +3 ( d d , c d d + d d ) = 1 k +1 k +4 2 k +1 k +4 k +2 k +3 ( d d , d d ) = 1 . k +1 k +4 k k +5 2 2 Therefore d is coprime to d as desired. Similarly, ( d d , d ) = 1 = ⇒ ( d d , d ) = 1, k +5 k +4 k +4 k +2 k +1 k +5 k +3 k +3 and so d is coprime to d as well. Therefore, d is coprime to the two previous terms as desired. k +5 k +3 k +5 37