Collatz-type Problems with Multiple Divisors by Keira Gunn B.Sc., McMaster University, 2007 A THESIS SUBMITTED IN PARTIAL FULFILLMENT OF THE REQUIREMENTS FOR THE DEGREE OF MASTER OF SCIENCE in The Faculty of Graduate Studies (Mathematics) THE UNIVERSITY OF BRITISH COLUMBIA (Vancouver) August 2009 © Keira Gunn 2009 ii Abstract The Collatz Conjecture hypothesizes that if a sequence of integers beginning with any positive integer t0 is recursively defined so that tj+1 = tj 2 when tj is even and tj+1 = 3tj +1 when tj is odd, then there will be some j ∈ N such that tj = 1. I propose a similar family of problems (which I call systems) involving a set of prime divisors {p1, ..., pk} and a multiplier m, where the sequence is recursively defined so that tj+1 = tj p1 if tj is divisible by p1, tj+1 = tj p2 if tj is divisible by p2 but not p1, tj+1 = tj p3 if tj is divisible by p3 but not p1 or p2 etc., and if tj is not divisible by any of the primes, then tj+1 = mtj + 1. Assuming the residues of the terms of these sequences behave randomly modulo p1 · · · pk, I propose a multiplicative expectation and data to suggest that this is a reasonable model for these systems. If the expectation is less than 1, as in the case of the Collatz problem, then I hypothesize that any sequence will eventually result in some finite cycle. As well, if my model for these systems is accurate, then I prove that the inclusion of an increasing prime q to a fixed set of prime divisors will result in an effect that gradually diminishes for the multiplicative expectation of the system. iii Contents Abstract . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . ii Contents . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iii List of Tables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv Acknowledgements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . v 1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 2 Calculating Expectation . . . . . . . . . . . . . . . . . . . . . . . . 3 2.1 The Expectation Formula . . . . . . . . . . . . . . . . . . . . . . 3 2.2 Frequencies of Divisibility . . . . . . . . . . . . . . . . . . . . . . 3 2.2.1 The Probability Distribution Matrix . . . . . . . . . . . . 4 3 Uniqueness of the Principal Eigenvector . . . . . . . . . . . . . . 7 4 Increasing Divisors. . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 5 Evidence Supporting this Model . . . . . . . . . . . . . . . . . . . 29 5.1 The E(S) = 1 threshold . . . . . . . . . . . . . . . . . . . . . . . 29 5.2 Occurrence of Divisors . . . . . . . . . . . . . . . . . . . . . . . . 32 5.3 Occurrence of Residues . . . . . . . . . . . . . . . . . . . . . . . . 38 5.4 Other Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 Bibliography . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 49 iv List of Tables 5.1 Divergence in S(17/{2, 3, 5}) (E(S) = 1.0384) . . . . . . . . . . . 30 5.2 Divergence in S(5/{2, 7}) (E(S) = 1.0275) . . . . . . . . . . . . . 30 5.3 Divergence in S(9/{2, 5, 11}) (E(S) = 1.0182) . . . . . . . . . . . 31 5.4 Divergence in S(11/{2, 3, 67}) (E(S) = 1.0043) . . . . . . . . . . 31 5.5 Divergence in S(11/{2, 3, 59}) (E(S) = 1.0015) . . . . . . . . . . 31 5.6 Highest Number Attained for Systems with Expectation less than 1 31 5.7 Expected and Actual Occurrences of Division in S(17/{2, 3, 5}) . 33 5.8 Expected and Actual Occurrences of Division in S(5/{2, 7}) . . . 33 5.9 Expected and Actual Occurrences of Division in S(9/{2, 5, 11}) . 34 5.10 Expected and Actual Occurrences of Division in S(11/{2, 3, 67}) 34 5.11 Expected and Actual Occurrences of Division in S(11/{2, 3, 59}) 35 5.12 Expected and Actual Occurrences of Division in S(11/{2, 3, 47}) 35 5.13 Expected and Actual Occurrences of Division in S(11/{2, 3, 53}) 36 5.14 Expected and Actual Occurrences of Division in S(19/{2, 3, 5, 11}) 36 5.15 Expected and Actual Occurrences of Division in S(11/{2, 3, 61}) 37 5.16 Expected and Actual Occurrences of Division in S(23/{2, 3, 5, 7}) 37 5.17 Expected and Actual Occurrences for Residues in S(17/{2, 3, 5}) 38 5.18 Expected and Actual Occurrences for Residues in S(5/{2, 7}) . . 38 5.19 Expected and Actual Occurrences for Residues in S(9/{2, 5, 11}) 38 5.20 Expected and Actual Occurrences for Residues in S(11/{2, 3, 67}) 39 5.21 Expected and Actual Occurrences for Residues in S(11/{2, 3, 59}) 40 5.22 Expected and Actual Occurrences for Residues in S(11/{2, 3, 47}) 41 5.23 Expected and Actual Occurrences for Residues in S(11/{2, 3, 53}) 42 5.24 Expected and Actual Occurrences for Residues in S(19/{2, 3, 5, 11}) 43 5.25 Expected and Actual Occurrences for Residues in S(11/{2, 3, 61}) 44 5.26 Expected and Actual Occurrences for Residues in S(23/{2, 3, 5, 7}) 45 5.27 Multiplicative Expectations for some Systems . . . . . . . . . . . 46 5.28 Random Numbers Used in Trials . . . . . . . . . . . . . . . . . . 46 vAcknowledgements This work would not have been possible without the guidance and support of my supervisor, Dr. Greg Martin. As well, I would like to thank David Steinberg and Heather Hurley for helping me make it this far, and Puck Saunders for inspiration. Finally, I would like to thank Tamaki Kano for her encouragement. 1Chapter 1 Introduction The Collatz problem, also known as the “3x+1” problem, was first posed by Lothar Collatz in 1937 [3]. The problem is defined by its very simple iterative step: if a number is even then divide by two, and if the number is odd then multiply by three then add one (hence the name “3x+1”.) The famous conjecture states that–given any starting number–if this itera- tion is repeatedly performed to generate a sequence of numbers, then eventually 1 will be contained in that sequence [3]. While the problem itself seems easy enough, extensive research has yielded no proof to this conjecture. However, as of January 18th of 2009 it has been verified that sequences beginning with any of the numbers up to about 20× 258 do eventually reach 1 [5]. Probabilistically, one would expect any such sequence to decrease over time. For large numbers, the effect of the “+1” is negligible and so one only needs to investigate the effects of multiplication by 3 or division by 2. The problem is set up in such a way that division by 2 occurs immediately following any muli- plication by 3 (the addition of 1 guarantees the resulting number is even) and so–assuming randomness (which will be better explained in the next chapter)– division by 2 again should occur 12 of the time, and division by 2 yet again should occur 14 of the time, etc. For large numbers, this gives a multiplicative expectation of 3 2 · 2 12 · · · 2 12k · · · = 3 2(1+ 1 2+ 1 4+...) = 3 22 = 3 4 . This thesis makes no attempt to prove the “3x+1” conjecture, but seeks to look at a family of related problems in the hopes of gaining some insight. Each problem will be referred to as a “system”, denoted by S(m/{p1, ..., pk}) (pi is prime, and m is coprime to pi for all i in 1, 2, ..., k), where the iterative step will include an “mx+1” action (the multiplication of m then addition of 1) followed by division by each pi until the resulting number is no longer divisible by any of the pi’s. Clearly the resulting number after an iteration is coprime to each pi. For consistency, the starting number in a sequence will be divided by the pi’s as many times as possible before the first iteration is performed. It is not a necessity that the number 1 is used for addition, the only require- ment on the addition number is that it is coprime to each of the prime divisors. However, using 1 guarantees that the addition operation is as negligible as pos- sible. After some analysis (which is covered in the next chapter) a multiplicative expectation can be found for each system. An expectation of greater than 1 Chapter 1. Introduction 2 suggests that sequences are gradually increasing, and so there should be many divergent sequences. An expectation of less than 1 suggests that sequences are gradually decreasing and so all sequences should eventually be contained in some finite cycle. The fifth chapter provides empirical evidence supporting these expectations and the idea that the sequences behave randomly (despite the sequences being predetermined by the initial starting point.) In addition, an interesting but expected result is proven in chapter four. That is, given a system S(m/{p1, ..., pk}), the expection of S(m/{p1, ..., pk, q}) converges to the expectation of S(m/{p1, ..., pk}) as q goes to infinity. Throughout this thesis, N will be used to denote the product of p1 · · · pk. For convenience, the expression “a ≡ b” will mean a ≡ b (mod N) unless a different modular base is specified. In addition, the term “principle eigenvector” will refer to the eigenvector corresponding to the eigenvalue λ = 1 for any probability distribution matrix. 3Chapter 2 Calculating Expectation Assuming a random distribution of the residues, the multiplicative expectation for each system is calculated by finding the frequencies at which a sequence should be divisible by each of the divisors, and then using those frequencies in the upcoming expectation formula. 2.1 The Expectation Formula Given that a randomly selected integer is divisible by a divisor p, there is a 1pn probability that it is divisible by pn+1 for any n ≥ 0. Another way of expressing this is that, if there is divisibility by p, then the probability of divisibility by p again is 1p , and the divisibility by p a third time is 1 p2 and etc.. If we let αi be the expected frequency of divisibility by the divisor pi for the system S(m/{p1, ..., pk}), then the expectation E(S) is E(S) = m k∏ i=1 ( ( 1pi )( 1 pi ) 1 pi · · · ( 1pi ) 1 pn i · · · )αi = m k∏ i=1 ( ( 1pi ) 1+ 1pi +...+ 1 pn i +... )αi = m k∏ i=1 ( 1 pi )αi pipi−1 . For the purposes of this thesis, all systems are of the form S(m/{2, p2, ..., pk}) (see chapter 3 for an explanation). Since the multiplier must be coprime to all the divisors, addition by 1 guarantees that divisibility by 2 must occur after an iteration, so α1 = 1 and α1 p1p1−1 = 2. This simplifies the expectation to E(S) = m (1 2 )2 k∏ i=2 ( 1 pi )αi pipi−1 = m 4 k∏ i=2 ( 1 pi )αi pipi−1 . (2.1) From here it is quite simple to calculate the multiplicative expectation once the values of α2 through αk are known. 2.2 Frequencies of Divisibility Each iteration occurs on one of p−1 coprime residues modulo p. Multiplication by m is a bijection from that set of coprime residues to itself. Addition by 1 Chapter 2. Calculating Expectation 4 will then shift exactly one of those initial p − 1 residues (the residue that is congruent to −m−1, precisely) to the value of 0 modulo p, and will thus grant divisibility by p. Because of this, one could näıvely conclude that the value of each αi is simply 1pi−1 . In fact, as has already been established, this holds true for the case p1 = 2. However, for larger primes there are more complicated interractions taking place between the division processes and the likelihood of resulting in any of the residues. For example, suppose the system is S(5/{2, 3}). This gives N = 6 and the residues 1 and 5. If we start with 5 (mod 6) then mt0 + 1 ≡ 2 and so division by 2 results in either 1 or 4 (mod 6) with equal probabilities of 12 . If the result is 4 then a second division takes place resulting in either 2 or 5 (mod 6) with equal probabilities of 14 . Division of 2 by 2 should again take place, giving the probability of the resulting number being congruent to 1 (mod 6) a value strictly greater than 12 . The probability of the resulting number being congruent to 5 (mod 6) is thus less than 12 . Specifically, the probabilities are not equal, which refutes the hypothesis made in the previous paragraph. If an iteration within a system S is defined to include both the “mx + 1” action and all divisions that take place (until the resulting number is no longer be divisible by any of the primes), then one method of approaching this problem is to construct the probability distribution matrix (which will be denoted by PS) for the coprime residues modulo N after each iteration. If a is a random representative of the set {a, a+N, ..., a+MN} and PS,M,(b,a) is the probability of a being brought to b (mod N) after one iteration, then PS,(b,a) will be the limit of PS,M,(b,a) as M goes to infinity. In the next section, all probabilities discussed will actually be the limit of probabilities of random representives of the set {a, a+N, ..., a+MN} as M →∞. Once PS is constructed, the principal eigenvector will give the long-term expectation of the distribution of the residues. From there, the sum of the expectations of the residues that are congruent to −m−1 (mod pi) will give the overall expectation of being divisible by pi, which is the value of αi. 2.2.1 The Probability Distribution Matrix For the system S(m/{p1, ..., pk}), the matrix PS can be decomposed into k + 1 transitional matrices T0, ..., Tk. The first matrix is the φ(N) × N probability distribution matrix for the set of coprime residues modulo N into the set of all residues modulo N after the “mx + 1” action (T0(b, a) is the probability of anything congruent to a being brought to b (mod N) after the “mx + 1” action). For a ∈ Z∗N , a has a probability of 1 of being brought to ma+1 in ZN , so T0(ma+ 1, a) = 1 and T0(b, a) = 0 for all b 6≡ ma+ 1. Chapter 2. Calculating Expectation 5 For the system S(5/{2, 3}), the first transitional matrix would be given by T0 = 0 0 0 1 0 0 0 0 0 0 1 0 , where T0 gives the probabilities of the set {1, 5} being brought into the set {1, 2, 3, 4, 5, 6} (for T0 above, and T1 and T2 below, the order of the indices in T0 correspond to the order of presentation of the sets). For i ∈ {1, ..., k}, the matrix Ti is the probability distribution matrix for the action of division by pi, so Ti(b, a) is the probability of anything congruent to a being brought to b (mod N) through division by pi. Let Ii = {a ∈ ZN |a coprime to p1, ..., pi−1}. If division takes place in the order the primes are listed, then division by p1 distributes Z∗N = I1 to the set I2, division by p2 distributes I2 to I3, etc.. Each matrix Ti need only consider the probability distribution from Ii to Ii+1 after division by pi. (For our example S(5/{2, 3}), we have I1 = {1, 2, 3, 4, 5, 6}, I2 = {1, 3, 5}, and I3 = {1, 5}) If a is coprime to pi then division by pi does not take place, so the “division by pi” action brings a to a with probability 1. This gives Ti(a, a) = 1 and Ti(b, a) = 0 for all b 6= a. In S(5/{2, 3}), this results in columns [1, 0, 0]T , [0, 1, 0]T , [0, 0, 1]T in T1 corresponding to 1, 3, 5 respectively and columns [1, 0]T , [0, 1]T in T2 cor- responding to 1, 5 respectively. If pi divides a then there is a 1pi probability that division by pi will result in each of b1,s ≡ api+sNpi for s ∈ {1, ..., pi} (the set of all numbers moduloN that are congruent to a when multiplied by pi). Because api ∈ Ii and Npi = R · p1 · · · pi−1 for some integer R, we have that b1,s ∈ Ii for each s. Since Npi is coprime to pi, the values of sNpi run through all residues modulo pi, thus the values b1s also run through all residues modulo pi. One of these values, say c1 = b1,s for some s is divisible by pi again. From there, the numbers b2,s ≡ c1pi + sNpi for s ∈ {1, ..., pi} will each have a probability of 1 p2i of occuring and will all be contained in Ii. As well, one of the values, say c2, will be divisible by p1. For S(5/{2, 3}), consider 2 ∈ I1 and division by 2. b1,1 = 22 + (1) 62 = 4 and b1,2 = 22 + (2) 6 2 = 1. So, c1 = 4. Similarly, b2,1 = 5 and b2,2 = 2. Continuing in this manner, there will be some r, s such that br,s = a (For division of 2 by 2 in S(5/{2, 3}) it is clear that r = 2). In fact, r is the order of pi in the multiplicative group modulo NM where M is the product of all primes in {p1, ..., pk} that divide a (so a = sM for some s coprime to NM ). If d is the order of pi, then apdi = sM · pdi satisfies both apdi ≡ sM (mod NM ) and apdi ≡ 0 (mod M), thus apdi ≡ sM = a (mod N) by the Chinese Remainder Theorem. Since, for any r < d we have apdi 6≡ sM (mod NM ), the Chinese Remainder Theorem also gives that apdi 6≡ a (mod N). By combining this and the fact that each set of bt,s’s runs through all numbers such that bt,spti = a, Chapter 2. Calculating Expectation 6 it is evident that r = d is the first level at which the value a recurs (that is, bd,s = a for some s). The sequence will then repeat itself in such a manner that b(t+r),s = bt,s. Thus the probability of resulting in bt,s (for those bt,s that are not divisible by pi) is equal to 1 pti + 1 pt+ri + 1 pt+2ri + ... = 1 pt ( 1 + 1 pr + 1 p2r + ... ) = pr−ti pri − 1 . (2.2) So, for any a ∈ Ii and b ∈ Ii+1 (we can use Ii+1 since we are restricted to elements in Ii that are not divisible by pi), if r is the least positive integer such that apri ≡ a and t is the least positive integer such that bpti ≡ a then Ti(b, a) = pr−ti pri−1 where t is defined, and 0 elsewhere. Keeping with the S(5/{2, 3}) example, corresponding to 2 in T1 we have the column [ 2 2−1 22−1 , 0, 22−2 22−1 ] T = [23 , 0, 1 3 ] T . The rest of the calculations give T1 = 1 23 0 13 0 00 0 1 0 0 1 0 13 0 2 3 1 0 and T2 = [ 1 12 0 0 12 0 ] . The overall probability distribution matrix, PS is then calculated by the multiplication of all the transitional matrices as follows: PS = Tk · Tk−1 · · ·T1 · T0. (2.3) For S(5/{2, 3}) this results in PS = [ 1 12 0 0 12 1 ]1 23 0 13 0 00 0 1 0 0 1 0 13 0 2 3 1 0 0 0 0 1 0 0 0 0 0 0 1 0 = [ 1 2 2 3 1 2 1 3 ] . The principal eigenvector for PS of this system is [4, 3]T , so the long term probability distribution is [ 47 , 3 7 ] for the residues {1, 5}. Of 1 and 5, the only value which is congruent to −5−1 (mod 3) is 1, and so the expected probability of divisibility by 3 is 47 . Equation (2.1) gives E(S) = 5 4 [( 1 3 ) 3 3−1 ] 4 7 ≈ 0.48747. Since the multiplicative expectation is significantly lower than 1, it is expected that this system should quickly decrease, and eventually result in finite cycles. A list of several other systems and their multiplicative expectations can be found in Table 5.27. 7Chapter 3 Uniqueness of the Principal Eigenvector The final steps in calculating the expectation require that the eigenvector corre- sponding to λ = 1 is unique. Obviously, if there are multiple such eigenvectors then there is significant ambiguity in how to evaluate a2 through ak and thus E(S). This section will show that using p1 = 2 ensures that the principal eigenvec- tor is unique. Showing this can be broken into two parts; first: any residue has a positive probability of being brought to any other residue (or itself) after a finite number of iterations and second: if this is the case, then the steady state vector is unique. The first lemma is a slightly stronger version of the latter. Proposition 3.1. Let M be a probability distribution matrix with index set I. If for any i, j ∈ I there is some r ∈ N such that (Mr)(i,j) is non-zero, then there is a unique eigenvector corresponding to the eigenvalue λ = 1, and that eigenvector has positive entries. Proof. Let M be a probability distribution matrix as described in the lemma. According to Perron-Frobenius theorem, there is an eigenvector associated with the eigenvalue λ = 1, and this vector has non-negative entries [4, Chapter 2]. Let ~v be a non-negative eigenvector (whose entries sum to 1) corresponding to λ = 1; there must be some non-zero value in ~v, so suppose ~v(a) 6= 0 for some a ∈ I. According to the hypothesis, for any k ∈ I there is some s (dependent on k) such that (Ms)(k,a) > 0. ~v is an eigenvector for M corresponding to λ = 1, so ~v is also an eigenvector for Ms corresponding to λ = 1s = 1. We have that that Ms · ~v = ~v, and thus (Ms~v)(k) = ~v(k). This gives ~v(k) = (Ms~v)(k) = ∑ i∈I (Ms)(k,i)~v(i) = ∑ i∈I|i 6=a (Ms)(k,i)~v(i) + (Ms)(k,a)~v(a). Both ~v and Ms have only non-negative entries. This gives ~v(k) ≥ 0 +Ms(k,a)~v(a). Ms(k,a) and ~v(a) were selected to be positive, so we have ~v(k) > 0. Chapter 3. Uniqueness of the Principal Eigenvector 8 ~v(k) must be positive for any k therefore ~v has no zero entries. Now that positivity of the vector is established, uniqueness will be proven. Let ~u be an eigenvector with positive entries as described above. Suppose ~v is a second linearly independent eigenvector corresponding to λ = 1. So, any linear combination a~v + b~u is also an eigenvector corresponding to λ = 1 for a, b ∈ R. Let c = min{ ~vi~ui |i ∈ I}. Consider ~w = ~v − c~u. For each j ∈ I we have ~w(j) = ~v(j) −min{ ~v(i) ~u(i) |i ∈ I}~u(j) ≥ ~v(j) − ~v(j) ~u(j) ~u(j) = 0. So ~w is an eigenvector with non-negative entries. Clearly for the i that elicits the minimum of ~v(i)~u(i) , we have that ~w(i) = 0. Since ~u and ~v are linearly independent, ~w 6= ~0. The first part of the proof of the lemma verifies that any non-negative eigenvector must be have all positive entries, so ~w cannot exist and thus ~v cannot exist. The eigenvector is unique. The second lemma will address the hypothesis in Proposition 3.1 that for any i, j ∈ I, there is an r such that (Mr)(i,j) is positive. The proof of the following proposition will go back and forth between the systems S(m/{2, p2, ..., pk}) and S(m/{2, p2, ..., pk, q}). To avoid confusion, N will refer to 2p2 · · · pk. Since Z∗Nq ' Z∗N × Z∗q , the coprime residues modulo Nq will be written as coordinates in Z∗N × Z∗q (written as [a, b]). Given P (the probability distribution matrix for S(m/{2, p2, ..., pk, q})) and a, b ∈ Z∗Nq, if (P k)(b,a) > 0 for some k ∈ N then we will write a b. Given P̄ (the probability distribution matrix for S(m/{2, p2, ..., pk})) and a, b ∈ Z∗N , if (P̄h)(b,a) > 0 for some h ∈ N then we will write a ̄b. Lemma 3.2. Let M be a probability distribution matrix with index I, and let a, b, c ∈ I. If a b and b c then a c. Proof. It suffices to show that (Ph1+h2)(c,a) > 0. Since a b and b c we have (Ph1)(b,a) > 0 and (Ph2)(c,b) > 0 for some h1, h2 ∈ N. So (Ph1+h2)(c,a) = (Ph2Ph1)(c,a) = ∑ d∈I (Ph2)(c,d)(Ph1)(d,a) ≥ ∑ d=b (Ph2)(c,d)(Ph1)(d,a) = (Ph2)(c,b)(Ph1)(b,a) > 0. Finally, using the notation in Chapter 2, if P = Tk+1 · · ·T0, then let P ′ = Tk · · ·T0. So, P ′ represents the probability distribution in S(m/{2, p2, ..., pk, q}) without division by q. In other words, P ′ is the probability distribution matrix for qZ∗N in S(m/{2, p2, ..., pk}), so we have that P̄(a,b) = ∑ c∈Zq P ′ ([a,c],[b,d]) for any d ∈ Zq (this is proven later as Lemma 4.3). Specifically, if P̄(a,b) > 0 then for any d ∈ Zq there is some c ∈ Zq with P ′([a,c],[b,d]) > 0. For the remainder of this chapter, let T = Tk+1. Chapter 3. Uniqueness of the Principal Eigenvector 9 Lemma 3.3. If P̄(x,a) > 0 then P([x,y],[a,−m−1]) > 0 for any y ∈ Z∗q . Proof. Let c′ ∈ Zq be such that P ′([x,c′],[a,−m−1]) > 0 P([x,y],[a,−m−1]) = (TP ′)([x,y],[a,−m−1]) = ∑ b∈Z∗N ∑ c∈Z∗q T([x,y],[b,c])P ′ ([b,c],[a,−m−1]) ≥ ∑ b=x ∑ c=c′ T([x,y],[b,c])P ′ ([b,c],[a,−m−1]) = T([x,y],[x,c′])P ′([b,c′],[x,−m−1]). P ′ includes the “mx + 1” action but has no division by q, and so for any y1, y2 ∈ Z∗Nq such that P ′([y1,y2],[x,−m−1]) > 0 it must be true that [y1, y2] is divisible by q; therefore c′ ≡ 0 (mod q). If d is the multiplicative order of q in Z∗N , then by equation (2.2), for any [x′, y′] such that [x′qd, y′qd] = [x, c′] we have that T([x′,y′],[x,0]) > 0. But, xqd ≡ x (mod N) and yqd ≡ 0 (mod q) for any y ∈ Z∗q , thus T([x,y],[x,c′]) > 0. For any y ∈ Z∗q , P([x,y],[a,−m−1]) > 0. Recall an iteration is the “mx + 1” action, followed with divisions by the primes 2, p2, ..., pk. So, if ψ is an iteration of x, then ψ(x) = mx+12r1pr22 ···p rk k for some non-negative integers r1, ..., rk (note that the result of an iteration in Z∗N is not necessarily well-defined). However, an iteration that can be applied to one residue may not be applicable to another depending on divisibilities after the “mx+ 1” action. We will say an iteration ψ is valid on x if ψ(x) = mx+1 2r1p r2 2 ···p rk k where ri ≥ 1 when mx+1 is divisible by pi and ri = 0 if mx+1 is not divisible by pi. Also, we will write ψ(x) ≡ a if a ∈ Z∗N and 2r1pr22 · · · prkk a ≡ x. As a result, P(b,a) > 0 if and only if there is a valid iteration ψ such that ψ(a) ≡ b and a b if and only if there is a sequence Ψ of valid iterations on a such that Ψ(a) ≡ b. Lemma 3.4. Let x, a ∈ Z∗N , and b ∈ Z∗q . Let ψ1, ..., ψs be a sequence of valid iterations on x such that ψs ◦ ... ◦ ψ1(x) ≡ a. If there is t ∈ {1, ..., s} such that ψt ◦ ... ◦ ψ1(b) ≡ 0 (mod q) then [a, b] [x, y] for any y ∈ Z∗q . Proof. Let t be the smallest integer such that ψt ◦ ... ◦ ψ1(b) ≡ 0 (mod q). So, ψt−1 ◦ ... ◦ψ1 is a valid sequence of iterations of b in S(m/{2, p1, ..., pk, q}). Let Ψ = ψt−1 ◦ ... ◦ ψ1. Then Ψ(b) ≡ −m−1 (mod q) must be true. Using Lemma 3.3 along with the fact that P̄(ψtΨ(a),Ψ(a)) > 0, we have P([ψtΨ(a),z],[Ψ(a),−m−1]) > 0 for any z ∈ Z∗q , in particular z = −m−1. Thus, ψt can be amended to ψ′t in S(m/{2, p1, ..., pk, q}) to satisfy ψ′t ◦ Ψ([a, b]) = [ψt ◦ ... ◦ ψ1(a),−m−1] and be valid in S(m/{2, p2, ..., pk, q}). t′ = t+ 1 is now the smallest such integer with ψt′ ◦ ... ◦ ψ1(b) ≡ 0 (mod q). Inductively, the same procedure as above can be applied until t′ = s. For t′ = s, choose z = y instead of z = −m−1. As constructed, ψ′t, ..., ψ′s are valid iterations under S(m/{2, p1, ..., pk, q}), and ψ′s ◦ ... ◦ ψ′tΨ(a) ≡ ψs ◦ ... ◦ ψ1(a) = x. Chapter 3. Uniqueness of the Principal Eigenvector 10 For any valid iteration ψ on [−m−1, b], where ψ([−m−1, b]) = [x, y], define 2ψ so that 2ψ([−m−1, b]) = [x, 2y]. Lemma 3.5. 2ψ is a valid iteration on [−m−1, b]. Proof. It is enough to show that P([x,2y],[−m−1,b]) > 0. ψ([−m−1, b]) = [x, y] implies that 2r1pr22 · · · prkk y ≡ mb + 1 (mod q) and 2r1pr22 · · · prkk x ≡ m(−m−1)+1 ≡ 0 (mod N) for some positive integers r1, ..., rk. If r1 > 1 then let r′1 = r1, otherwise let r ′ 1 = r1+d2 where d2 is the multiplicative order of 2 in Z∗q . Then 2r ′ 1−1pr22 · · · prkk x ≡ 0 ≡ m(−m−1) + 1 (mod N), and 2r ′ 1−1pr22 · · · prkk 2y = 2r ′ 1pr22 · · · prkk y ≡ 2r1pr22 · · · prkk y ≡ mb+1 (mod q) and thus P ([x, 2y], [−m−1, b]) > 0. Proposition 3.6. Given a system S = S(m/{2, p2, ..., pk}), let N = 2p2 · · · pk and let P be the probability distribution matrix of S for the coprime residues of N . Then, for any i, j ∈ Z∗N , there is an r ∈ N such that (P r)(i,j) is positive. Proof. Using the notation above, this proposition is equivalent to showing that for all a, b ∈ Z∗N , we have a b. The proof will proceed by induction on the number of prime divisors. First, let k = 1. We have p1 = 2 and a = b = 1. ma+1 = 2sL for some odd L, so division by 2s will occur, resulting in L ≡ 1 ≡ b. So, a b. Suppose the statement is true for all S(m/{2, p2, ..., pk}), and consider the system S(m/{2, p2, ..., pk, q}). Let [a, b] ∈ Z∗N × Z∗q. First, it will be shown that (a, b) ∈ Z∗N × Z∗q can be brought to (a, y) for any y ∈ Z∗q . By the inductive hypothesis, a ̄−m−1 is true. So, there is some sequence of iterations ψ1, ..., ψs−1 in S(m/{2, p2, ..., pk}) such that ψs−1◦...◦ψ1(a) = −m−1. Let ψs(x) = mx+1N be the next iteration in the sequence, and so ψs◦...◦ψ1(a) ≡ x for any x ∈ Z∗N . In particular, ψs ◦ ... ◦ ψ1(a) ≡ a. If for some integer t ≤ s, we have ψt ◦ ... ◦ ψ1(b) ≡ 0 (mod q), then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q and so the first part of the proof is complete. So, suppose there is no such t. Thus, ψ1, ..., ψs are valid iterations in S(m/{2, p1, ..., pk, q}). If Ψ = ψs ◦ ...◦ψ1, then Ψ(a, b) = (a, y) for some fixed y ∈ Z∗q . For any b ∈ Z∗q , if m1, ...,ms are the multiplicative representations of the division modulo q that occurs in each iteration (note that this is well defined since these values are coprime to q), then we have the following: y = Ψ(b) ≡ ms(m(...m2(m(m1(mb+ 1)) + 1)...) + 1) ≡ ms ( s∏ i=1 mi ) b+ s∑ i=1 ( ms−i s∏ j=i mj ) = Ab+B for some integers A and B where A is coprime to pk+1 (since each mi and m is coprime to pk+1). To go forth, it is required that B 6≡ 0 (mod q). If B ≡ 0 (mod q) then ψs can be redefined so that ψs(x) = mx+1N and ψs ◦ ψs−1 ◦ ... ◦ ψ1(a) ≡ −m−1, and ψs+1 defined so that ψs+1(x) = mx+1N and ψs+1 ◦ ψs ◦ ... ◦ ψ1(a) ≡ a. If Chapter 3. Uniqueness of the Principal Eigenvector 11 ψs+1 ◦ ... ◦ ψ1(b) ≡ 0 (mod q), then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q , as desired. Otherwise, let Ψ = ψs+1 ◦ ... ◦ ψ1. We now have y = Ψ(b) ≡ A′b+B′, where B′ = s+1∑ i=1 ( ms+1−i s+1∏ j=i mj ) = s∑ i=1 ( ms+1−i s+1∏ j=i mj ) +ms+1 = ms+1 s∑ i=1 ( ms+1−i s∏ j=i mj ) +ms+1 = ms+1m s∑ i=1 ( ms−i s∏ j=i mj ) +ms+1 = ms+1mB +ms+1. Since B ≡ 0 (mod q), this gives B′ ≡ ms+1 6≡ 0 (mod q), as required. If used, A′ and B′ will be referred to as A and B respectively. If A 6≡ 1 (mod q), then let d be the multiplicative order of A in Z∗q , otherwise let d = q. If there is some t ∈ {1, ..., s} and r ∈ {1, ..., d} such that ψt ◦ ... ◦ ψ1Ψr(b) ≡ 0 (mod q) then Lemma 3.4 gives that [a, b] [a, y] for any y ∈ Z∗q as desired. Suppose there is no such t and r, so Ψd is a valid sequence of iterations on [a, b]. Each application of Ψ gives Ψ(x) ≡ Ax+B. If A ≡ 1 (mod q) then Ψd(b) ≡ b+ dB = b+ qB ≡ b (mod q). For A 6≡ 1 (mod q) we have Ψd(b) = A(...(A(Ab+B) +B)...+B) = Adb+B d−1∑ i=1 Ai = Adb+B (Ad − 1 A− 1 ) ≡ 1b+ 0 = b (mod q). (3.1) In either case, Ψd(b) ≡ b (mod q). Ψd−1 satisfies that ΨΨd−1(b) ≡ b (mod q); therefore AΨd−1(b) + B ≡ b (mod q) and so Ψd−1(b) ≡ b−BA (mod q). Let Φ = (2ψs) ◦ψs−1 ◦ ... ◦ψ1Ψd−2. By Lemma 3.5, Φ is a valid sequence of iterations on b, and Φ(b) = 2Ψd−1(b) ≡ 2 b−BA . Now consider Ψ ◦ Φ. If for some t ∈ {1, ..., s} we have ψt ◦ ... ◦ ψ1 ◦ Φ(b) ≡ 0 (mod q) then Lemma 3.4 gives us that [a, b] [a, y] for any y ∈ Z∗q and so the first part of the proof is complete, otherwise Ψ ◦ Φ is a valid sequence of iterations in S(m/{2, p2, ..., pk, q}) and Ψ ◦ Φ(b) = A ( 2 b−B A ) +B = 2b−B. (3.2) So [a, b] [a, 2b−B]. Let Cb = {y ∈ Z∗q |[a, b] [a, y]}. In the following manipulations of the group Cb, if any sequence of iterations results in 0 modulo q then, as has been shown, this always results in the conclusion that [a, b] [a, y] for any y ∈ Z∗q , Chapter 3. Uniqueness of the Principal Eigenvector 12 or equivalently that Cb = Z∗q . Suppose that no sequence of iterations results in 0 modulo q. Equation (3.1) shows that [a, b] [a, b] through the iterations Ψd, so b ∈ Cb. Also, Φ′ = (2ψs) ◦ ψs−1 ◦ ... ◦ ψ1Ψd−1 is a valid sequence of iterations in S(m/{2, p2, ..., pk, q}) and Φ′(b) = 2(Ψd(b)) = 2b; therefore 2b ∈ Cb by Lemma 3.2, and similarly we have that 2rb ∈ Cb for any integer r. Specifically, 2d−1b ∈ Cb where d is the multiplicative order of 2 in Z∗q . Equation (3.2) gives that [a, 2d−1b] [a, 2(2d−1b)−B] = [a, b−B], and thus b−B ∈ Cb. There is some i ∈ Z∗q such that b ≡ Bi (mod q), and so by repeating this procedure we can conclude that {b, b−B, b− (i− 1)B} ⊂ Cb. Applying the procedure once more gives divisibility by q and so, along with Lemma 3.4 we have [a, b] [a, y] for any y ∈ Z∗q . Thus, in all cases, we have [a, b] [a, y] for any y ∈ Z∗q . Next, consider any [x, y] in Z∗N × Z∗q . Using the induction hypothesis, there is a sequence of iterations Ψ under S(m/{2, p1, ..., pk}) that brings a to x (mod N). If Ψ brings b to 0 (mod q) at some point then proposition 3.4 can be invoked to show [a, b] [x, y]. If at no point Ψ brings b to 0 (mod q) then Ψ is valid under S(m/{2, p1, ..., pk, q}) and so [a, b] [x,Ψ(b)]. Using the results just established [x,Ψ(b)] [x, y] and thus by Lemma 3.2 [a, b] [x, y]. Propositions 3.1 and 3.6 combine to form: Theorem 3.7. Let P be the probability distribution matrix for the coprime residues of N = 2p2 · · · pk in the system S(m/{2, p2, ..., pk}). Then P has a unique positive eigenvecter corresponding to λ = 1. When p1 6= 2, problems arise from the fact that division is not guaranteed to occur within each iteration. Suppose thatm 6≡ 1 (mod pi) for each i ∈ {1, ..., k}, and let di be the multiplicative order of m in Z∗pi . If ψ(x) = mx+ 1 then ψdi(x) = mdx+ d−1∑ j=0 m ≡ x+ m d − 1 m− 1 ≡ x (mod pi). This suggests that the ψ operation will cause any x ∈ Zpi to run a cycle of length di. There are pi−1di cycles of length di, and one cycle of length 1 (the number −1m−1 will return to itself after ψ). Since there are more than 2 cycles in total, there are cycles that do not include 0, and any such cycle is smaller than Z∗pi . A cycle that does not include 0 (mod pi) will never encounter divisibility by pi. In Zp1 × ...×Zpk choose [a1, ..., ak] so that ai is in such a cycle for each i and clearly divisibility by any of the primes will never occur. [a1, ..., ak] will be part of a cycle of length lcm(d1, ..., dk) < φ(p1 · · · pk) = |Z∗p1···pk |, and therefore not all of Z∗p1···pk . Any number starting in this cycle can never leave the cycle, so there is an eigenvector whose only non-zero components correspond to elements in the cycle. Chapter 3. Uniqueness of the Principal Eigenvector 13 When m ≡ 1 (mod pi) for some i ∈ {1, ..., k}, the proof used for p1 = 2 above falls apart where equation (3.2) becomes Ψ ◦ Φ(b) = A(pi b−B A ) +B = pib− (pi − 1)B. Using the same methods it can be shown that pib− (pi−1)B ∈ Cb. If pi ≡ 1 (mod q) then there is no t such that b ≡ t(pi − 1)B (mod q), and so the proof cannot be continued as before. However, if pi 6≡ 1 (mod q) then there is such a t and the proof can be concluded similarly to when pi = 2. This results in the following generalization: Theorem 3.8. Let p1, ..., pk be primes, and m ≡ 1 (mod pi) for some i ∈ {1, ..., k}. Let P be the probability distribution matrix for the coprime residues of N = p1 · · · pk in the system S(m/{p1, ..., pk}). If pi 6≡ 1 (mod pj) for all j ∈ {1, ..., k} then P has a unique positive eigenvecter corresponding to λ = 1. 14 Chapter 4 The Effect of Increasing a Divisor on Expectation A brief investigation of Table 5.27 (Multiplicative Expectations for Systems), suggests that as more divisors are added the expectation tends to decrease but if a divisor is increased then the expectation tends to increase as well. Specifi- cally, looking at the systems S(11/{2, 3, q}) (the right-hand side of the table), it appears that as q increases the expectation is generally increasing, but does not appear to surpass the expectation of S(11/{2, 3}). This observation leads to a prediction that the expectation E(S(m/{2, p1, ..., pk, q}) should converge to E(S(m/{2, p1, ..., pk})) as q →∞. In fact, this is Theorem 4.16. The key to the proof of this theorem is to show that the probability of division by q tends to 0 as q tends to infinity, and thus has minimal effect on the residues modulo N after an iteration (in this case, N = 2p2 · · · pk). The proof will proceed by comparing the principal eigenvector of the probability distribution matrix P (S) to that of a similar, but easily controlled matrix P ′. Let ī be the notation for the residue representative of i in ZN . Also, let P̄ be the probability distribution matrix for Z∗N into itself within the system S(m/{2, p2, ..., pk}) and let P be the probability distribution matrix for the residue set S0 = {x ∈ ZNq|x is coprime to N} into itself within the system S(m/{2, p1, ..., pk, q}). If Q = qZ∗N , then note that S0 = Z∗Nq ∪Q. Although the principal eigenvector for P (S) (the probability distribution matrix for Z∗Nq in S) is ultimately what we are trying to analyse, the next lemma will allow us to substitute this eigenvector for that of P . Lemma 4.1. If ~w ∈ Rφ(Nq) is the principal eigenvector for P (S) and ~u ∈ Rφ(N)q is the principal eigenvector for P , then ~w(a) = ~u(a) for a ∈ Z∗Nq and ~u(a) = 0 for a ∈ Q. Proof. Division by q ensures that after an iteration, no resulting number can be divisible by q. This gives P(a,b) = 0 for any b ∈ S0 when a ∈ Q. So, since ~u is a principal eigenvector for P we have ~u(a) = (P~u)(a) = ∑ b∈S0 P(a,b)~u(b) = ∑ b∈S0 (0)~u(b) = 0. Chapter 4. Increasing Divisors. . . 15 If a, b ∈ Z∗Nq, then P (S)(a,b) = P(a,b). So, for a 6∈ Q, we then have ~u(a) = (P~u)(a) = ∑ b∈S0 P(a,b)~u(b) = ∑ b∈Q P(a,b)~u(b) + ∑ b∈Z∗Nq P(a,b)~u(b) = ∑ b∈Q P(a,b)(0) + ∑ b∈Z∗Nq P (S)(a,b)~u(b) = ∑ b∈Z∗Nq P (S)(a,b)~u(b) = ( P (S)~u ) (a) . The only vector in Rφ(Nq) that satisfies ~u(a) = ( P (S)~u ) (a) for all a ∈ Z∗Nq is ~w. Thus, we have ~u = ~w. Using equation (2.3) we can write P as P = Tk+1 · · ·T0 for the transitional matrices T0, ..., Tk+1. For convenience, let T = Tk+1. Also, let P ′ = Tk · · ·T0. Specifically, P ′ is the probability distribution matrix for S0 into itself within the system S(m/{2, p1, ..., pk}) (notice the omission of division by q). Also, P = TP ′. Finally, let A = {a ∈ Z∗Nq|ma+ 1 ≡ 0 (mod q)} ⊂ Z∗Nq, so A is a subset of S0. Lemma 4.2. |A| = |Q| = φ(N). Proof. Q = qZ∗N , so |Q| = |Z∗N | = φ(N) is trivial. A = {a ∈ Z∗Nq|ma+ 1 ≡ 0 (mod q)}. By the Chinese Remainder Theorem, in Z∗Nq there is a unique solution to a ≡ 0 (mod q) and a ≡ b (mod N) for each b ∈ Z∗N , thus there are |Z∗N | = φ(N) solutions, and so |A| = φ(N). The first part of the proof of the theorem will be to find a principal eigen- vector for the matrix P ′. Before we begin, two more lemmas will be useful: Lemma 4.3. For any a, b ∈ S0,∑ c∈S0|c≡b P ′(c,a) = P̄(b̄,ā). Proof. Recall from earlier that P ′ = Tk · · ·T0. Similar to Chapter 2, let I0 = S0 and Ii = {a ∈ ZNq|a coprime to p1, ..., pi−1} for i ∈ {1, ..., k}. For any a ∈ Ii and b ∈ Ii+1 let Ti(b,a) = ∑ c∈Ii+1|c≡b Ti(c,a). First, it will be shown that Ti(b,a) = T̄i(b̄,ā) for all i ∈ {0, ..., k}. For i = 0, the result is simple. T0(ma+1,a) = 1 and T0(c,a) = 0 for all c 6≡ ma+ 1 (mod Nq). If b 6≡ ma + 1 (mod N) then c 6≡ ma + 1 (mod Nq) for any c ≡ b. Also, b 6≡ mā+ 1 (mod N), so T̄0(b̄,ā) = 0. We have T0(b,a) = ∑ c∈Ii+1|c≡b T0(c,a) = ∑ c∈Ii+1|c≡b 0 = 0 = T̄0(b̄,ā). Chapter 4. Increasing Divisors. . . 16 If b ≡ ma + 1 (mod N) then b′ ≡ ma + 1 (mod Nq) for a unique b′ ∈ S0 such that b′ ≡ b. Also, b ≡ mā+ 1 (mod N), so T̄0(b̄,ā) = 1. We have T0(b,a) = ∑ c∈Ii+1|c≡b T0(c,a) = T0(b′,a) + ∑ c∈Ii+1|c≡b,c6=b′ T0(c,a) = 1 + ∑ c∈Ii+1|c≡b 0 = 1 = T̄0(b̄,ā). When i 6= 1, the result is more involved. For a ∈ Ii and b ∈ Ii+1 suppose T̄i(b̄,ā) = 0. So, bpsi 6≡ a (mod N) for any s ∈ Z. Thus, for any c ≡ b we have that cpsi 6≡ a (mod Nq) for any s ∈ Z and so Ti(b,a) = 0. Suppose then, that T̄i(b̄,ā) 6= 0. According to equation (2.2) we have T̄i(b̄,ā) = pr−ti pri−1 where r is the least positive integer such that ap r i ≡ a and t is the least positive integer such that bpti ≡ a. Suppose that s is the least positive integer such that apsi ≡ a (mod Nq). There is some K ∈ Z+ such that s = Kr. For each j ∈ {0, ...,K − 1}, the Chinese Remainder Theorem gives a unique solution for cj ∈ Ii+1 with cj ≡ b such that cjpjr+ti ≡ a (mod Nq) (and no solution for cjpni ≡ a (mod Nq) where n cannot be written as n = jr + t for some j). Equation (2.2) then gives Ti(cj ,a) = p Kr−(jr+t) i pKri −1 and Ti(c,a) = 0 for all c 6∈ {c0, ..., cK−1}. We have Ti(b,a) = ∑ c∈Ii+1|c≡b Ti(c,a) = K−1∑ j=0 Ti(cj ,a) = K−1∑ j=0 p Kr−(jr+t) i pKri − 1 = K∑ j=1 pjr−ti pKri − 1 = p−ti pKri − 1 pri K−1∑ j=0 pjri = p−ti pKri − 1 pri ( pKri − 1 pri − 1 ) = pr−ti pri − 1 = T̄i(b̄,ā). This concludes the first part of the proof of the lemma, that Ti(b,a) = T̄i(b̄,ā) for all i ∈ {0, ..., k}. It remains to show that multiplication of these matrices maintains this summation property (with appropriate index sets). That is, that P ′(b,a) = P̄ ′ (b̄,ā) for all a, b ∈ S0. Assume the property is held for Tj−1 · · ·T0, then for any a ∈ S0 and b ∈ Ij+1 we have (Tj · · ·T0)(b,a) = ∑ c∈Ii+1|c≡b (Tj · · ·T0)(c,a) = ∑ c∈Ii+1|c≡b (∑ d∈Ii Tj(c,d)(Tj−1 · · ·T0)(d,a) ) = ∑ d∈Ii ( (Tj−1 · · ·T0)(d,a) ∑ c∈Ii+1|c≡b Tj(c,d) ) = ∑ d∈Ii (Tj−1 · · ·T0)(d,a)Tj(b,d). Chapter 4. Increasing Divisors. . . 17 From the previous result, we have that Tj(b,d) = T̄j(b̄,d̄). So, (Tj · · ·T0)(b,a) = ∑ d∈Ii (Tj−1 · · ·T0)(d,a)T̄j(b̄,d̄) = ∑ c∈Ii∩ZN ∑ d∈S0|d≡c (Tj−1 · · ·T0)(d,a)T̄j(b̄,d̄) = ∑ c∈Ii∩ZN T̄j(b̄,c) ∑ d∈S0|d≡c (Tj−1 · · ·T0)(d,a) = ∑ c∈Ii∩ZN T̄j(b̄,c)(Tj−1 · · ·T0)(d,a). The induction hypothesis now gives (Tj · · ·T0)(b,a) = ∑ c∈Ii∩ZN T̄j(b̄,c)(T̄j−1 · · · T̄0)(c,ā) = (T̄j+1 · · · T̄0)(b̄,ā). ∑ c∈S0|c≡b P ′ (c,a) = P̄ ′ (b̄,ā) follows from the conclusion of the induction argu- ment. Lemma 4.4. For any a, c ∈ S0,∑ b∈S0|b≡a P ′(c,b) = P̄(c̄,ā). Proof. As per Section 2.2.1, if a ∈ A, then P ′(b,a) = 0 for any b 6∈ Q. Using Lemma 4.3 we have P̄(c̄,ā) = ∑ b∈S0|b≡c P ′(b,a) = ∑ b∈Q|b≡c P ′(b,a) + ∑ b 6∈Q|b≡c P ′(b,a) = ∑ b∈Q|b≡c P ′(b,a) + ∑ b 6∈Q|b≡c (0) = ∑ b∈Q|b≡c P ′(b,a). According to the Chinese Remainder Theorem, there is a unique b ∈ S0 such that b ≡ 0 (mod q) and b ≡ c, therefore P ′(c,a) = P̄(c̄,ā) when c ∈ Q and a ∈ A. Consider any c ∈ Q. Section 2.2.1 also tells us that if b 6∈ A then P ′(c, b) = 0. This combined with the previous result gives∑ b∈S0|b≡a P ′(c,b) = ∑ b∈A|b≡a P ′(c,b) + ∑ b 6∈A|b≡a P ′(c,b) = ∑ b∈A|b≡a P ′(c,b) + ∑ b 6∈A|b≡a 0 = ∑ b∈A|b≡a P ′(c,b) Again, there is a unique b so that b ∈ A and b ≡ a, so we get∑ b∈S0|b≡a P ′(c,b) = P̄(c̄,ā). Chapter 4. Increasing Divisors. . . 18 Consider c 6∈ Q, so c ∈ Z∗Nq. For any b ∈ S0 there is a unique K ∈ ZNq such that Kc ≡ b (mod Nq). Suppose c′ ≡ c, and let K be such that Kc′ ≡ ma+ 1 (mod Nq); there are two cases. Case 1: K ≡ 2r1pr22 · · · prkk for some sets of integers {r1, ..., rk} with 0 ≤ ri ≤ di (di is the multiplicative order of pi in Z∗Nq) and Case 2: there are no such r1, ..., rk. For Case 2, the operations of S(m/{2, p2, ..., pk}) cannot bring a to c′ and therefore P ′(c′,a) = 0. For Case 1, a can be brought to c ′ and the value of P ′(c′, a) is determined only by the sets {r1, ..., rk}. In both cases, P ′(c′, a) depends only on K. Since c′ ≡ c, we have c ≡ c′ + dN (mod Nq) for some integer d. Let a′ ≡ a+KdNm−1 (mod Nq). Then ma′ + 1 ≡ m(a+KdNm−1) + 1 ≡ ma+KdN + 1 ≡ Kc′ +KdN ≡ K(c′ + dN) ≡ Kc (mod Nq). Thus there is some a′ with P ′(c, a′) = P ′(c′, a). This gives a bijection between the values of P ′(c′, a) and P ′(c, a′) for c′ ≡ c and a′ ≡ a. This, along with Lemma 4.3 gives∑ b∈S0|b≡a P ′(c,b) = ∑ b∈S0|b≡c P ′(b,a) = P̄(ā,c̄). Define the vector ~u′ by ~u′(a) = ~v(ā) q . Then we have the following proposi- tion, which will be the first step in the proof of the theorem mentioned at the beginning of this chapter: Proposition 4.5. ~u′ is a principal eigenvector for P ′. Proof. Consider w = P ′~u′. For each b ∈ S0 we have (P ′~u′)(b) = ∑ a∈S0 P ′(b,a)~u′(a) = ∑ c∈Z∗N ∑ a∈S0|a≡c P ′(b,a)~u′(a) = ∑ c∈Z∗N ∑ a∈S0|a≡c P ′(b,a) ~v(ā) q = ∑ c∈Z∗N ∑ a∈S0|a≡c P ′(b,a) ~v(c) q = 1 q ∑ c∈Z∗N ( ~v(c) ∑ a∈S0|a≡c P ′(b,a) ) . Lemma 4.4 gives (P ′~u′)(b) = 1 q ∑ c∈Z∗N ~v(c)P̄(b̄,c̄) = 1 q ∑ c∈Z∗N ~v(c)P̄(b̄,c) = 1 q (P̄~v)(b̄). Since ~v is the principal eigenvector for P̄ , this simplifies to (P ′~u′)(b) = 1 q ~v(b̄) = ~u′(b). Chapter 4. Increasing Divisors. . . 19 For all b ∈ S0 we have (P ′~u′)(b) = ~u′(b), so ~u′ is a principal eigenvector for P ′. The next step of the proof of the theorem is to show that for any a ∈ Z∗N , the sum of the values of ~u(b) where b ≡ a converges to ~v(a) as q increases. This will be a result of the similarity between P and P ′, and thus their eigenvectors. Several new notations and lemmas will prove useful for the upcoming propo- sition. For any real vector ~w, we will define the function D on ~w so that D(~w) =∑ i∈I |~w(i)|, where I is the index set of ~w. Lemma 4.6. For any real vectors ~u, ~w with index set I and K ∈ R, the following are true: i. D(K~w) = K ·D(~w); ii. D(~u)−D(~w) ≤ D(~u+ ~w) ≤ D(~u) +D(~w); iii. If P is a non-negative matrix with index set I whose columns sum to 1, then D(P ~w) ≤ D(~w). Proof. i. is trivial, and ii. is a straightforward result of the triangle inequality. The proof of iii. is as follows: D(P ~w) = ∑ i∈I |(P ~w)(i)| = ∑ i∈I ∣∣∣∑ j∈I P(i,j) ~wj ∣∣∣ ≤∑ i∈I ∑ j∈I |P(i,j) ~w(j)| = ∑ i∈I ∑ j∈I P(i,j)|~w(j)| = ∑ j∈I |~w(j)| ∑ i∈I P(i,j) = ∑ j∈I |~w(j)|(1) = D(~w). For P and P ′ as defined earlier, let ∆ = P ′ − P . So ∆ = P − P ′ = TP ′ − P ′ = (T − I)P ′ (T − I) will have the form of ~0 for all columns with a 6∈ Q. For a, b ∈ Q and a 6= b, we have (T − I)(a,a) = −1 and (Tq− I)(a,b) = 0. For a ∈ Q and b 6∈ Q the values of (T − I) follow the probability distributions described in Section 2.2.1: if there is no integer r such that bqr ≡ a (mod N) then (T − I)(b,a) = 0; if there is such an r, and d is the multiplicative order of q in Z∗N then by equation (2.2), we have (T − I)(b,a) = q d−r qd−1 , where r ∈ {1, ..., d}. The sum of each column is 0. Lemma 4.7. If ~w is a real vector with index set Z∗Nq then ∑ a∈S0(∆~w)(a) = 0. Proof. ∑ a∈S0 (∆~w)(a) = ∑ a∈S0 ∑ b∈S0 ∆(a,b) ~w(b) = ∑ b∈S0 ~w(b) ∑ a∈S0 ∆(a,b) = ∑ b∈S0 ~w(b)(0) = 0. Lemma 4.8. If ~u′ is the principal eigenvector for P ′, then D(∆~u′) = 2q . Chapter 4. Increasing Divisors. . . 20 Proof. D(∆~u′) = D((T − I)P ′~u′) = D((T − I)~u′) = ∑ a∈S0 |((T − I)~u′)(a)| = ∑ a∈S0 ∣∣∣ ∑ b∈S0 (T − I)(a,b)~u′(b) ∣∣∣ = ∑ a∈S0 ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) + ∑ b 6∈Q (T − I)(a,b)~u′b ∣∣∣. From the construction of (T − I), we have (T − I)(a,b) = 0 for b 6∈ Q, so D(∆~u′) = ∑ a∈S0 ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) + ∑ b 6∈Q (0)~u′b ∣∣∣ = ∑ a∈Q ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) ∣∣∣+ ∑ a∈S0\Q ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) ∣∣∣. (4.1) For all b ∈ Q we have ~u′(b) = ~v(b̄)q > 0. As established earlier, if a ∈ Q, then (T − I)(a,b) ≤ 0 and if a 6∈ Q then (T − I)(a,b) ≥ 0. Combining this with Lemma 4.7, we have∑ a∈Q ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) ∣∣∣ = ∑ a∈S0\Q ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) ∣∣∣. Continuing with equation (4.1) now gives D(∆~u′) = 2 ∑ a∈Q ∣∣∣∑ b∈Q (T − I)(a,b)~u′(b) ∣∣∣ = 2∑ a∈Q ∣∣∣∑ b∈Q (T − I)(a,b) ~v(b̄) q ∣∣∣ = 2 ∑ a∈Q ∣∣∣∑ b=a (T − I)(a,b) ~v(b̄) q + ∑ b 6=a (T − I)(a,b) ~v(b̄) q ∣∣∣ = 2 ∑ a∈Q ∣∣∣∑ b=a (−1)~v(b̄) q + ∑ b 6=a (0) ~v(b̄) q ∣∣∣ = 2∑ a∈Q ~v(b̄) q = 2 q ∑ a∈Z∗N ~v(b̄) = 2 q (1) = 2 q . For a system S(m/{2, p2, ..., pk}) with N = 2p2 · · · pk, and prime q coprime to N , if ~w is a real vector with index set Z∗Nq then define the real vector ~̄w with index set Z∗N so that for any a ∈ Z∗N we have ~̄w(a) = ∑ b∈S0|b≡a ~w(b). We then have the following two results: Lemma 4.9. P ′ ~w = P̄ ~̄w. Chapter 4. Increasing Divisors. . . 21 Proof. P ′ ~w(a) = ∑ b∈S0|b≡a (P ′ ~w)(b) = ∑ b∈S0|b≡a ∑ c∈S0 P ′(b,c) ~w(c) = ∑ c∈S0 ( ~w(c) ∑ b∈S0|b≡a P ′(b,c) ) . Lemma 4.3 and the definition of ~w simplify this to: P ′ ~w(a) = ∑ c∈S0 ~w(c)P̄(ā,c̄) = ∑ d∈Z∗N ∑ c∈S0|c≡d ~w(c)P̄(ā,c̄) = ∑ d∈Z∗N ∑ c∈S0|c≡d ~w(c)P̄(ā,d) = ∑ d∈Z∗N ( P̄(ā,d) ∑ c∈S0|c≡d ~w(c) ) = ∑ d∈Z∗N P̄(ā,d) ~̄w(d) = (P̄ ~̄w)(a). Lemma 4.10. D( ~̄w) ≤ D(~w). Proof. D( ~̄w) = ∑ a∈Z∗N | ~̄w(a)| = ∑ a∈Z∗N ∣∣∣ ∑ b∈S0|b≡a ~w(b) ∣∣∣ ≤ ∑ a∈Z∗N ∑ b∈S0|b≡a |~w(b)| = ∑ b∈S0 |~w(b)| = D(~w). The remaining three lemmas will allow us to conclude the proof of the next proposition. Lemma 4.11. If ~w is a positive vector such that ~w(a) ≤ 1q for all a ∈ Z∗N then (P ~w)(a) < 1 q ( ∑ b∈Z∗N P̄ā,b + φ(N) ) . Proof. (P ~w)(a) = ∑ c∈S0 P(a,c) ~w(c) ≤ ∑ c∈S0 ( P(a,c) 1 q ) = 1 q (∑ c∈A P(a,c) + ∑ c6∈A P(a,c) ) ≤ 1 q (∑ c∈A (1) + ∑ c6∈A P(a,c) ) = 1 q ( |A|+ ∑ c6∈A P(a,c) ) . Lemma 4.2 states that |A| = φ(N). Also, if c 6∈ A, then division by q has no effect on c after the “mx+ 1” action and thus P(a,c) = P ′(a,c) for all a ∈ S0. Chapter 4. Increasing Divisors. . . 22 Using this, and Theorem 4.4 we have (P ~w)(a) = 1 q ( φ(N) + ∑ c6∈A P ′(a,c) ) ≤ 1 q ( φ(N) + ∑ c∈S0 P ′(a,c) ) = 1 q ( φ(N) + ∑ b∈Z∗N ∑ c∈S0|c≡b P ′(a,c) ) = 1 q ( φ(N) + ∑ b∈Z∗N P̄(ā,b) ) Lemma 4.12. Let M be an n-by-n probability distribution matrix with unique principal eigenvector ~w (where the sum of the entries is 1), and { ~wi}i∈N be a sequence of vectors in Rn (whose entries sum to 1) that satisfy M ~wi = ~wi + ~i for some ~i where D(~i)→ 0 as i→∞. Then, ~wi → ~w. Proof. Let ρ(~v1, ~v2) = D(~v1 − ~v2) be a metric between two vectors in Rn (the properties of a metric have been confirmed in Lemma 4.6). Define the function F : Rn → R;F (~w) = D((M − I)~w). Continuity of F under this metric is obvious. Also, F ( ~wi) = D((M − I) ~wi) = D(~i). Suppose that for some constant C there is a subsequence { ~wki}i∈N ⊂ { ~wi}i∈N such that ρ( ~wki , ~w) > C for each i ∈ N. Let G be the compact set {~x ∈ [0, 1]n|D(~x) = 1}\{~x ∈ Rn|ρ(~x, ~w) < C}. Clearly, ~wki ∈ G for each i ∈ N and so the sequence {F ( ~wki)}i∈N = {D(~i)}i∈N is contained in F (G) Since G is compact, the set F (G) is closed and thus contains all its limits [2, Chapter 6.2]. By the hypothesis, D(~i) → 0 and so 0 ∈ F (G). Since ~w is a unique principal eigenvector, it is the only solution to F (~w) = 0, thus ~w ∈ G must be true. But, ρ(~w, ~w) = 0 < C, so ~w 6∈ G, a contradiction. There is no such C, and therefore ~wi → ~w. Lemma 4.13. Let X = {xj}j∈N be a sequence in R+ and let Xi be either a finite set, or a sequence that converges to 0 for any i ∈ Z+ . If X ⊂ ∪i∈Z+Xi and supXi → 0 as i→ 0 then xj → 0 as j →∞. Proof. For some c ∈ R, let c > 0. Since supXi → 0, there are only a finite number of indices i such that x ≥ c is possible for some x ∈ Xi. Each Xi is either finite or a sequence that converges to 0, so there is at most finitely many x ∈ Xi such that x ≥ c. Since a finite union of finite sets is finite, there is at most finitely many x ∈ ∪i∈Z+Xi such that x ≥ c, and thus at most finitely many x ∈ X such that x ≥ c. There must be some M such that xj < c for all j > M and therefore xj → 0. A few more new notations need to be introduced. First, for any real vector ~w with index set I, let ~w+ be the vector such that ~w+(i) = ~w(i) when ~w(i) > 0 and ~w+(i) = 0 when ~w(i) ≤ 0 for all i ∈ {1, ..., n}. Also, let ~w− ∈ Rn be the Chapter 4. Increasing Divisors. . . 23 vector such that ~w−(i) = −~w(i) when ~w(i) < 0 and ~w−(i) = 0 when ~w(i) ≥ 0 for all i ∈ {i, ..., n}. Basically, ~w+ contains the positive components of ~w and ~w− contains the negative components. Finally, let ~u be the principal eigenvector for P , and let ~δ = ~u− ~u′ (the error between our desired vector ~u and the established vector ~u′). The goal of the following proposition is to show that as q →∞ then ~δ+ → ~δ+. Proposition 4.14. ~̄u(a) → ~v(a) as q →∞ for all a ∈ Z∗N . Proof. Since ~u is the principal eigenvector for P we have P~u = ~u P ~u′ + P~δ = ~u′ + ~δ (P ′ +∆)~u′ + P~δ = ~u′ + ~δ P ′~u′ +∆~u′ + P~δ = ~u′ + ~δ. Recall that u′ is the principal eigenvector for P ′, so P ′~u′ = ~u′. We now have ~u′ +∆~u′ + P~δ = ~u′ + ~δ ∆~u′ + P~δ = ~δ P~δ = ~δ −∆~u′. (4.2) Equation (4.2) can be broken into its positive and negative components; −(P~δ)− + (P~δ)+ =− (~δ −∆~u′)− + (~δ −∆~u′)+ (P~δ)− = (~δ −∆~u′)− & (P~δ)+ = (~δ −∆~u′)+. (4.3) Let ~e = [min{(P ~δ+)(b), (P ~δ−)(b)}]b∈S0 (that is, ~e is the overlap in compo- nents between (P ~δ+) and (P ~δ−)). Then P~δ− = (P~δ)−+~e and P~δ+ = (P~δ)++~e. Also, (~δ −∆~u′)− = (~δ)− − ~w for some ~w with |~w(b)| < |(∆~u)(b)| for all b ∈ S0 (and clearly, D(~w) < D(∆~u)). The first half of equation (4.3) becomes P~δ− = ~δ− + ~e− ~w (4.4) (P ′ +∆)~δ− = ~δ− + ~e− ~w P ′~δ− = ~δ− + ~e− ~w −∆~δ−. In Z∗N , this is becomes P ′~δ− = ~δ− + ~̄e− ~w −∆~δ−, and so Lemma 4.9 gives P̄ ′~δ− = ~δ− + ~̄e− ~w −∆~δ− = ~δ− + ~β (4.5) Chapter 4. Increasing Divisors. . . 24 for ~β = ~̄e− ~̄w −∆~δ−. Now, according to Lemma 4.6 and equation (4.4) we have D(~δ−) ≥ D(P~δ−) = D(~δ− + ~e− ~w) = D(~δ− + ~e− ~w) ≥ D(~δ− + ~e)−D(~w) = D(~δ−) +D(~e)−D(~w) (the last equality is true since ~δ− and ~e are both positive vectors). This results in D(~e) ≤ D(~w). Therefore, by Lemma 4.8 and the previous establishment that D(~w) ≤ D(∆~u) we have D(~e) ≤ D(∆~u) = 2 q . (4.6) Consider D(∆~δ−). Since ~u is non-negative, it must be true that for each a ∈ S0, we have 0 ≤ ~ua = ~u′a + ~δa, and so ~δa ≥ −~u′a = −~vāq . So, for each a ∈ S0 we have 0 ≤ (~δ−)a ≤ ~vāq . Similar to the proof of Lemma 4.8, it is true that D(∆~δ−) ≤ 2q . Lemma 4.10 then gives that D(∆~δ−) ≤ 2q . Combining these results with Lemma 4.6 we get D(~β) ≤ D(~̄e) +D(~w−) +D(∆~δ−) ≤ 6 q . (4.7) Let Jq = D(~δ−) (for each respective q). For all primes q we have that 0 ≤ Jq ≤ 1, so if Y = {q|q prime}\{2, p2, ..., pk} then we can partition Y into the sets Y0 = {q ∈ Y |Jq = 0} and Yi = {q ∈ Y | 1i+1 < Jq ≤ 1i } for each i ∈ N. For any i > 0, consider any set Yi such that Yi has an infinite number of elements. For each q ∈ Yi, from Lemma 4.6 and equation (4.7) we have that D ( 1 Jq ~β ) = 1 Jq D(~β) < (i+ 1)D(~β) ≤ 6(i+ 1) q . (4.8) For each q ∈ Yi, if equation (4.5) is divided by Jq, then along with Lemma 4.12 (we are able to apply this lemma because of Theorem 3.7) and equation (4.8) we have that 1Jq ~δ− → ~v (recall that ~v is the principal eigenvector for P̄ ) as q →∞, or ~δ− → Jq~v. Next, consider the positive components of ~δ. A result of the fact that the sum of the components of both ~u and ~u′ is 1 is that D( ~δ−) = D( ~δ+), and therefore for each q ∈ Yi we have D( ~δ−) = Jq. There is also some ~w with D(~w) < D(∆~u) such that the positive counterpart to equation (4.4) is P̄ ′~δ+ = ~δ+ + ~̄e− ~w −∆~δ+. In order to show that ~δ+ → Jq~v for each q ∈ Yi, all that remains is to show that D(∆~δ+)→ 0 as q →∞. First, it will be shown that for each a ∈ A it must be true that (~δ+)(a) → 0, otherwise the value of ~e(b) will not converge for some b ∈ Z∗N (a contradiction). Chapter 4. Increasing Divisors. . . 25 As was proved in Chapter 3, ~v, the eigenvector for P̄ is a fixed non-negative vector. Since ~δ− → Jq~v, Lemma 4.9 gives us that for all a ∈ Z∗N we have (P ′~δ−)(a) = (P̄ ′~δ−)(a) → Jq(P̄ ′~v)(a) = Jq~v(a). Because P = P ′+∆ and D(∆~δ−)→ 0 as q →∞, for every a ∈ Z∗N we have (P~δ−)(a) → (P ′~δ−)(a). If L = min{~v(a)|a ∈ Z∗N} then for large enough q ∈ Yi and for all a ∈ Z∗N we have (P~δ−)(a) > Jq~v(a) 2 ≥ L 2i . Let R = (~δ+)(a) for any a ∈ A. From the definition of P and P ′ it is true that P ~δ+ = TP ′ ~δ+. Recall from the proof of Lemma 4.4 that since a ∈ A we have P ′(b,a) = P̄(b̄,ā) for b ∈ Q. By the pigeonhole principle, since the φ(N) components in any column of P̄ sum to 1, there is some c ∈ Q such that P̄(c̄,ā) ≥ 1φ(N) . So (P ′ ~δ+)(c) = ∑ b∈S0 P ′(c,b)( ~δ+)(b) ≥ ∑ b=a∈S0 P ′(c,b)( ~δ+)(b) = P ′ (c,a)( ~δ+)(a) = P̄(c̄,ā)R ≥ R φ(N) . According to equation (2.2), if d is the multiplicative order of q in Z∗N then for b, c ∈ Z∗Nq such that qb ≡ c (mod qN) we have T(b,c) = q d−1 qd−1 ≥ 2q . So (P ~δ+)(b) = (TP ′ ~δ+)(b) = ∑ a∈S0 T(b,a)(P ′ ~δ+)(a) ≥ ∑ a=c∈S0 T(b,a)(P ′ ~δ+)(a) = T(b,c)(P ′ ~δ+)(c) ≥ 2 q R φ(N) = 2R φ(N) 1 q . Recall that −~v(b̄)q ≤ −(~δ−)(b) ≤ 0. Obviously 0 < ~v(b̄) ≤ 1, so we have 0 ≤ (~δ−)(b) ≤ 1q . Applying this to Lemma 4.11 gives us that (P~δ−)(b) ≤ 1 q (φ(N) + ∑ a∈Z∗N P̄(b̄,a)). For any b such that qb ≡ c (mod Nq), the ratio of positive components of (P~δ) over negative components is (P~δ+)(b) (P~δ−)(b) ≥ 2R φ(N) 1 q 1 q (φ(N) + ∑ a∈Z∗N P̄(b̄,a)) = 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(b̄,a) ) . Chapter 4. Increasing Divisors. . . 26 For all such b we have ~e(b) = min{(P ~δ+)(b), (P ~δ−)(b)} ≥ min { 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(b̄,a) ) (P ~δ−)(b), (P ~δ−)(b)} = 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(b̄,a) ) (P ~δ−)(b). (4.9) The set described by {b ∈ S0|qb ≡ c (mod qN)} is the same as {b ∈ S0|b ≡ cq−1}. Recall that if q ∈ Yi is large enough then (P~δ−)(a) > L2i for all a ∈ Z∗N . Specifically, (P~δ−)(cq−1) > L 2i . From this and equation (4.9), we have ~̄e (cq−1) = ∑ b∈S0|b≡cq−1 ~e(b) ≥ ∑ b∈S0|b≡cq−1 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(b̄,a) ) (P~δ−)(b) = 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(cq−1,a) ) ∑ b∈S0|b≡cq−1 (P~δ−)(b) = 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(cq−1,a) ) (P~δ−) (cq−1) > 2R φ(N) ( φ(N) + ∑ a∈Z∗N P̄(cq−1,a) ) L 2i = RL φ(N)i ( φ(N) + ∑ a∈Z∗N P̄(cq−1,a) ) . Equation (4.6) stated that D(~̄e) → 0, and since D(~̄e) ≥ ~̄e (cq−1), it must be true that ~̄e (cq−1) → 0. We have i, L, φ(N), and ( ∑ a∈Z∗N P̄(cq−1,a)) all positive constants, so for any a ∈ A it must be true that (~δ+)(a) = R → 0 as q →∞ in Yi. Now, given that (~δ+)(a) = R→ 0, we can look at D(∆~δ+). D(∆~δ+) = ∑ a∈Z∗N |(∆~δ+)(a)| = ∑ a∈Z∗N ∣∣∣ ∑ b∈S0|b≡a (∆~δ+)(b) ∣∣∣ ≤ ∑ a∈Z∗N ∑ b∈S0|b≡a ∣∣(∆~δ+)(b)∣∣ = ∑ a∈Z∗N ∑ b∈S0|b≡a ∣∣((T − I)P ′~δ+) (b) ∣∣ = ∑ b∈S0 ∣∣((T − I)P ′~δ+) (b) ∣∣. (4.10) P ′ is a non-negative matrix, and ~δ+ is a non-negative vector, so P ′~δ+ is a non-negative vector as well. (T − I) has all non-positive entries in the rows corresponding to Q, and non-negative entries in the remaining rows. Thus (T − I)(P ′~δ+) will have non-positive entries in components corresponding to Q and non-negative entries elsewhere. Chapter 4. Increasing Divisors. . . 27 By Lemma 4.7, the sum of the entries in (T − I)P ′~δ+ = ∆~δ+ is 0. Thus,∑ b∈Q ∣∣((T − I)P ′~δ+) (b) ∣∣ =∑ b 6∈Q ∣∣((T − I)P ′~δ+) (b) ∣∣. So, by splitting S0 into Q and S0\Q, equation (4.10) becomes D(∆~δ+) = ∑ b∈Q ∣∣((T − I)P ′~δ+) (b) ∣∣+∑ b 6∈Q ∣∣((T − I)P ′~δ+) (b) ∣∣ = 2 ∑ b∈Q ∣∣((T − I)P ′~δ+) (b) ∣∣ = 2∑ b∈Q ∣∣∣ ∑ c∈S0 (T − I)(b,c)(P ′~δ+)(c) ∣∣∣ = 2 ∑ b∈Q ∣∣∣∑ c∈Q (T − I)(b,c)(P ′~δ+)(c) + ∑ c6∈Q (T − I)(b,c)(P ′~δ+)(c) ∣∣∣. Recall that (T − I)(b,c) = 0 for any c 6∈ Q. Also, (T − I)(b,b) = −1 and (T − I)(b,c) = 0 when b, c ∈ Q, so D(∆~δ+) = 2 ∑ b∈Q ∣∣∣∑ c∈Q (T − I)(b,c)(P ′~δ+)(c) + ∑ c6∈Q (0)(P ′~δ+)(c) ∣∣∣ = 2 ∑ b∈Q ∣∣∣∑ c∈Q (T − I)(b,c)(P ′~δ+)(c) ∣∣∣ = 2∑ b∈Q |(−1)(P ′~δ+)(b)| = 2 ∑ b∈Q (P ′~δ+)(b) = 2 ∑ b∈Q ∑ d∈S0 P ′(b,d)~δ + (d) = 2 ∑ b∈Q (∑ d∈A P ′(b,d)~δ + (d) + ∑ d6∈A P ′(b,d)~δ + (d) ) . Recall from the proof of Lemma 4.4 that P ′(b,d) = P̄(b̄,d̄) for b ∈ Q and d ∈ A, and P ′(b,d) = 0 for b ∈ Q and d 6∈ A. So D(∆~δ+) = 2 ∑ b∈Q (∑ d∈A P̄(b̄,d̄) ~δ+(d) + ∑ d6∈A (0)~δ+(d) ) = 2 ∑ b∈Q ∑ d∈A P̄(b̄,d̄) ~δ+(d). It has already been shown that ~δ+(d) → 0 for each d ∈ A. Since P̄(b̄,d̄) is fixed for all q, this is a finite sum of values that converge to 0, and thus D(∆~δ+)→ 0. With this established, the proof for negative components can be used to show that ~δ+ → Jq~v as well. Therefore, for each a ∈ Z∗N ~̄δ(a) = ∑ b∈S0|b≡a ~δ(a) = ∑ b∈S0|b≡a (~δ+(a) − ~δ−(a)) = ∑ b∈S0|b≡a ~δ+(a) − ∑ b∈S0|b≡a ~δ−(a) = ~δ+(a) − ~δ−(a) → Jq~v(a) − Jq~v(a) = 0 Chapter 4. Increasing Divisors. . . 28 From the definition of ~̄δ, we have ~̄u(a) → ~v(a) as q ∈ Yi →∞. If Y is written as the increasing sequence {qj}j∈N then let xj = ~̄δ(a) corre- sponding to each qj and let X = {xj}j∈N. Also, let Xi = {xj |qj ∈ Yi} for each i ∈ Z+. We can now apply Lemma 4.13 to conclude that as q → ∞ we have ~̄δ(a) → 0 for each a ∈ Z∗N . Proposition 4.15. As q →∞, the values α2q , ..., αkq of S(m/{2, p2, ..., pk, q}) converge to α2, ..., αk of S(m/{2, p2, ..., pk}) and αk+1q → 0. Proof. From Lemma 4.1, we can use the values of ~u for the principal eigenvector of P (S). Recall that αi = ∑ a∈Z∗Nq|pi divides ma+1 ~u(a). First, ~u(a) → 0 as q → ∞. Since {a ∈ Z∗Nq|pk+1 divides ma + 1} = A, we have αk+1 = ∑ a∈A ~u(a). Lemma 4.2 states that |A| = φ(N) (constant for all q) and each ~u(a) → 0. Thus αk+1 is a finite sum of numbers that converge to 0, and thus αk+1 converges to 0. Consider αi for i ∈ {2, ..., k}. Suppose ma + 1 ≡ 0 (mod pi) for some a ∈ Z∗N , and let b ≡ a. Clearly mb + 1 ≡ 0 (mod pi) is true. So, we have αi = ∑ a∈Z∗N |pi divides ma+1 ~v(a) and αiq = ∑ b∈Z∗Nq|pi divides mb+1 ~u(b) = ∑ a∈Z∗N |pi divides ma+1 ( ∑ b∈Z∗Nq|b≡a ~u(b) ) = ∑ a∈Z∗N |pi divides ma+1 ~̄u(a). For each a ∈ Z∗N , we have ~̄u(a) → ~v(a). Because αiq is a sum of finitely many things, we have αiq → αi This brings us to our conclusion: Theorem 4.16. If p2, ..., pk, q are prime, and m is coprime to q, 2 and each of p2, ..., pk then E(S(m/{2, p1, ..., pk, q})→ E(S(m/{2, p1, ..., pk})) as q →∞. Proof. From equation (2.1) and using the previous proposition we have the following: E(S(m/{2, p1, ..., pk, q}) = m4 k+1∏ i=2 ( 1 pi )αiq pipi−1 = m 4 k∏ i=2 ( 1 pi )αiq pipi−1(1 q )αk+1q qq−1 → m 4 k∏ i=2 ( 1 pi )αi pipi−1(1 q )(0) qq−1 = m 4 k∏ i=2 ( 1 pi )αi pipi−1 = E(S(m/{2, p1, ..., pk}) 29 Chapter 5 Evidence Supporting this Model 5.1 The E(S) = 1 threshold If the calculated expectations are accurate then any system with an expectation less than 1 should have the property that all sequences eventually result in a finite cycle, and any system with expectation greather than one should have the property that some sequences should diverge. Because of this, systems with expectations near the threshold of 1 are investigated in this chapter. Table 5.27 gives the calculated expectations of several systems. For simplic- ity, in each case 2 is used as p1. The 5 systems with expectations closest to 1 from below (S(11/{2, 3, 47}), S(11/{2, 3, 53}), S(19/{2, 3, 5, 11}), S(11/{2, 3, 61}), S(23/{2, 3, 5, 7})) and the 5 systems with expectations closest to 1 from above (S(17/{2, 3, 5}), S(5/{2, 7}), S(9/{2, 5, 11}), S(11/{2, 3, 67}), S(11/{2, 3, 59})) are investigated regarding divergence. 500 randomly generated numbers (see Table 5.28) were selected, and tested as the initial term for sequences in each of the 10 systems. The sequences were determined until either some term had greater than 10,000 digits, or the remainder of the sequence was cyclic. Tables 5.1 through 5.6 give the results of these tests, where a sequence is considered “divergent” if it eventually reaches a number with greater than 10,000 digits (for these sequences, it is only assumed that the resulting sequences are in fact divergent, but it has not been proven). As expected, for those systems with expectation less than 1, no such sequence was found. In each block of numbers (the random numbers were seperated into five groups of 100, each group being 8-12 digits long) the highest number attained by any “non-divergent” sequence was recorded. For these sequences, the highest number attained is approximately 2,500 digits long and so it is reasonable to assume that those sequences that attain a number of 10,000 digits are in fact “divergent”. Tables 5.1 through 5.5 suggest the fairly intuitive notion that the closer the expection is to 1 from above, the less likely it is that a sequence will diverge (however a comparison of S(17/{2, 3, 5}) and S(5/{2, 7}) seems to contradict this, which could potentially be explained by the choice of smaller divisors hav- ing a more significant effect on smaller starting numbers). A second expected trend in the data is that the larger the starting number, the more likely the Chapter 5. Evidence Supporting this Model 30 sequence is to converge. A hypothesis could be made that as t0 → ∞, the probability that the sequence beginning with t0 diverges goes to 1. Table 5.1: Divergence in S(17/{2, 3, 5}) (E(S) = 1.0384) Digits Divergent Sequences (ref no.) Tally Highest No. 8 1, 2, 6, 8, 11, 14, 20, 29, 31, 33, 38, 39, 40, 43, 55, 61, 70, 73, 76, 77, 79, 81, 83, 85, 86, 98, 100 27 < 1.8× 1055 9 3, 9, 10, 21, 23, 25, 34, 39, 41, 45, 48, 51, 52, 65, 68, 69, 71, 72, 74, 79, 85, 86, 89, 95, 96 25 < 2.5× 1055 10 8, 9, 10, 12, 13, 14, 15, 21, 23, 40, 45, 48, 52, 55, 58, 60, 61, 64, 67, 68, 73, 78, 87, 88, 97, 99 26 < 1.2× 1083 11 1, 2, 3, 6, 15, 19, 21, 23, 25, 31, 36, 41, 42, 45, 46, 47, 52, 53, 54, 57, 58, 60, 61, 63, 64, 67, 68, 70, 71, 74, 77, 80, 82, 85, 89, 92, 93, 94, 97, 98, 99, 100 42 < 3.0× 1080 12 1, 4, 6, 15, 17, 22, 23, 24, 26, 29, 30, 32, 35, 38, 39, 42, 43, 44, 47, 51, 58, 59, 61, 67, 68, 69, 71, 73, 75, 76, 78, 79, 84, 85, 88, 89, 90, 91, 92, 95, 97 41 < 2.4× 1031 8-12 161 < 1.2× 1083 Table 5.2: Divergence in S(5/{2, 7}) (E(S) = 1.0275) Digits Divergent Sequences (ref no.) Tally Highest No. 8 1, 2, 4, 5, 6, 7, 8, 11, 12, 14, 15, 16, 18, 19, 22, 27, 28, 29, 30, 31, 32, 33, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 46, 48, 50, 51, 54, 55, 56, 57, 58, 60, 63, 64, 65, 69, 70, 71, 72, 73, 74, 75, 77, 78, 79, 81, 82, 83, 84, 87, 89, 91, 94, 97 64 < 1.1× 1047 9 7, 10, 13, 14, 15, 19, 20, 21, 23, 24, 27, 28, 31, 33, 35, 36, 38, 41, 44, 45, 47, 48, 53, 54, 55, 57, 63, 65, 66, 68, 70, 74, 75, 77, 78, 79, 82, 83, 86, 87, 90, 91, 93, 97, 98, 99, 100 47 < 1.3× 1041 10 2, 3, 5, 7, 8, 10, 14, 16, 17, 18, 20, 21, 22, 24, 25, 26, 27, 28, 29, 30, 32, 33, 34, 38, 39, 41, 44, 45, 46, 52, 53, 54, 57, 60, 61, 62, 63, 65, 67, 68, 69, 70, 71, 73, 74, 76, 77, 79, 80, 87, 90, 91, 93, 94, 95, 98, 99 57 < 1.3× 1041 11 1, 3, 6, 7, 8, 9, 11, 12, 13, 14, 15, 16, 17, 18, 22, 23, 24, 25, 26, 28, 29, 32, 33, 34, 35, 36, 39, 40, 44, 45, 46, 47, 50, 51, 54, 55, 58, 59, 60, 61, 63, 64, 66, 67, 68, 71, 73, 74, 75, 76, 78, 79, 80, 81, 82, 84, 87, 88, 89, 91, 94, 96, 97, 99, 100 65 < 2.9× 1081 12 1, 2, 3, 5, 6, 7, 8, 12, 13, 15, 19, 21, 22, 25, 27, 28, 29, 30, 32, 33, 35, 36, 37, 38, 40, 42, 43, 44, 45, 46, 47, 49, 51, 52, 53, 55, 56, 57, 60, 62, 64, 66, 67, 68, 69, 72, 75, 76, 78, 82, 83, 84, 85, 86, 87, 89, 91, 95, 96, 97, 98, 100 62 < 2.9× 1081 8-12 295 < 2.9× 1081 Chapter 5. Evidence Supporting this Model 31 Table 5.3: Divergence in S(9/{2, 5, 11}) (E(S) = 1.0182) Digits Divergent Sequences (ref no.) Tally Highest No. 8 18, 23, 25, 30, 54, 55, 59, 71, 88, 91, 93, 94 12 < 5.6× 10111 9 14, 23, 25, 35, 36, 39, 43, 47, 52, 69, 78, 83, 85, 86, 88, 96 16 < 9.4× 1077 10 7, 12, 13, 27, 28, 32, 33, 35, 39, 40, 43, 46, 49, 58, 72, 78, 79, 81, 84, 90, 100 21 < 3.1× 1071 11 1, 13, 17, 19, 26, 49, 50, 52, 53, 54, 55, 59, 62, 70, 77, 81, 84, 88, 94, 96, 98, 99 22 < 3.6× 1082 12 1, 5, 22, 23, 24, 27, 31, 32, 35, 59, 61, 62, 70, 71, 72, 74, 77, 81, 83, 84, 85, 86, 94, 96 24 < 6.0× 10 8-12 95 < 5.6× 10111 Table 5.4: Divergence in S(11/{2, 3, 67}) (E(S) = 1.0043) Digits Divergent Sequences (ref no.) Tally Highest No. 8 3, 9, 55, 61, 63, 79, 82 7 < 4.4× 10101 9 13, 36, 61, 63, 64 5 < 1.1× 10483 10 4, 17, 36, 46, 93 5 < 8.5× 10180 11 16, 25, 37, 47, 95 5 < 3.3× 10173 12 8, 25, 26, 28, 54, 59, 81, 86, 100 9 < 3.6× 10246 8-12 31 < 1.1× 10483 Table 5.5: Divergence in S(11/{2, 3, 59}) (E(S) = 1.0015) Digits Divergent Sequences (ref no.) Tally Highest No. 8 9, 11, 17, 82, 85 5 < 7.9× 10841 9 39, 85 2 < 6.0× 10220 10 14, 16 2 < 4.0× 10242 11 12, 48 2 < 8.9× 101103 12 36, 44, 63 3 < 5.8× 102568 8-12 14 < 5.8× 102568 Table 5.6: Highest Number Attained for Systems with Expectation less than 1 System Expectation Highest Number S(11/{2, 3, 47}) 0.9897 < 1.8× 10266 S(11/{2, 3, 53}) 0.9931 < 1.3× 10446 S(19/{2, 3, 5, 11}) 0.9957 < 8.4× 10702 S(11/{2, 3, 61}) 0.9994 < 5.4× 101572 S(23/{2, 3, 5, 7}) 0.9994 < 1.7× 102523 Chapter 5. Evidence Supporting this Model 32 5.2 Occurrence of Divisors Further support for the proposed eigenvector model for systems can be found in analyzing the individual iterations of each sequence. The construction of the probability distribution matrix was dependent on the notion that, if a number n is divisible by p, then there is an equal probability that np ≡ a (mod N) for any a such that ap ≡ n (mod N). Tables 5.7 through 5.16 specifically deal with the likelihood of np being di- visible by p again. Trials were run on the 500 randomly selected numbers from table 5.28 in each of the 10 systems. Each random number had the divisors fac- tored out until the resulting number was coprime to each of the divisors and this resulting number was used as the starting point for each sequence. From there, the system would run until until either the sequence had reached a number less than 1000, or 10000 iterations had been performed1. After each iteration, the highest number of divisions by each division that took place were tallied. The results in Tables 5.7 through 5.16 are the percentages for the combined tallies for all 500 starting points. As stated earlier, if n is divisible by p, then there is a 1 pk−1 probability that n is divisible by pk. Thus if n is divisible by p, then there is a 1 − 1p = p−1p probability that n is divisible by p but not p2, and so there is a p−1 pk probability that n is divisibly by pk, but not divisible by pk+1. The expected percentages of tables 5.7 through 5.16 were calculated accordingly. With very few exceptions, the expected and actual percentages differ by less than five hundredths of a percentage point. It would appear as though the systems are behaving as expected in this regard. 11000 was chosen to be large enough to avoid the fixed patterns that would occur as the terms in sequences become smaller and repetitive, but small enough to still significant room for sequences to decrease from their initial starting point. Chapter 5. Evidence Supporting this Model 33 Table 5.7: Expected and Actual Occurrences of Division in S(17/{2, 3, 5}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.945 214 .006 .005 31 36.123 36.128 22 25.000 25.023 215 .003 .003 32 12.041 11.999 23 12.500 12.498 216 .002 .002 33 4.014 4.034 24 6.250 6.257 2≥17 .002 .002 34 1.338 1.347 25 3.125 3.152 35 .446 .457 26 1.563 1.567 51 20.542 20.539 36 .149 .143 27 .781 .774 52 4.108 4.127 37 .050 .051 28 .391 .397 53 .822 .805 38 .017 .018 29 .195 .189 54 .164 .164 39 .006 .005 210 .098 .098 55 .033 .034 310 .002 .002 211 .049 .050 56 .007 .007 3≥11 .001 .001 212 .024 .024 57 .001 .002 213 .012 .013 5≥8 .000 .000 Table 5.8: Expected and Actual Occurrences of Division in S(5/{2, 7}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.978 210 .098 .096 71 7.390 7.388 22 25.000 24.974 211 .049 .049 72 1.056 1.052 23 12.500 12.530 212 .024 .024 73 .151 .153 24 6.250 6.239 213 .012 .012 74 .022 .025 25 3.125 3.119 214 .006 .006 75 .003 .004 26 1.563 1.576 215 .003 .004 76 .000 .001 27 .781 .795 216 .002 .002 7≥7 .000 .000 28 .391 .397 217 .001 .001 29 .195 .197 2≥18 .001 .000 Chapter 5. Evidence Supporting this Model 34 Table 5.9: Expected and Actual Occurrences of Division in S(9/{2, 5, 11}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.930 214 .006 .006 51 23.689 23.717 22 25.000 25.050 215 .003 .005 52 4.738 4.726 23 12.500 12.515 216 .002 .001 53 .948 .933 24 6.250 6.230 217 .001 .002 54 .190 .187 25 3.125 3.141 2≥18 .001 .000 55 .038 .040 26 1.563 1.565 56 .008 .007 27 .781 .782 111 6.8061 6.8049 57 .002 .003 28 .391 .394 112 .6183 .6201 58 .000 .001 29 .195 .198 113 .0562 .0561 5≥9 .000 .000 210 .098 .095 114 .0051 .0049 211 .049 .051 115 .0005 .0006 212 .024 .023 116 .0000 .0001 213 .012 .011 11≥7 .0000 .0000 Table 5.10: Expected and Actual Occurrences of Division in S(11/{2, 3, 67}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.937 213 .012 .012 31 38.103 38.159 22 25.000 25.050 214 .006 .005 32 12.701 12.681 23 12.500 12.554 215 .003 .002 33 4.234 4.215 24 6.250 6.227 216 .002 .001 34 1.411 1.405 25 3.125 3.125 2≥17 .002 .000 35 .470 .462 26 1.563 1.536 36 .157 .152 27 .781 .790 37 .052 .058 28 .391 .394 671 1.5233 1.5224 38 .017 .017 29 .195 .203 672 .0227 .0238 39 .006 .004 210 .098 .089 673 .0003 .0001 310 .002 .002 211 .049 .051 674 .0000 .0001 311 .001 .001 212 .024 .024 67≥5 .0000 .0000 3≥12 .000 .000 Chapter 5. Evidence Supporting this Model 35 Table 5.11: Expected and Actual Occurrences of Division in S(11/{2, 3, 59}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.984 213 .012 .012 31 37.947 37.978 22 25.000 25.035 214 .006 .006 32 12.649 12.591 23 12.500 12.457 215 .003 .003 33 4.216 4.241 24 6.250 6.276 216 .002 .002 34 1.405 1.409 25 3.125 3.130 217 .001 .001 35 .468 .467 26 1.563 1.564 218 .000 .001 36 .156 .155 27 .781 .784 2≥19 .000 .000 37 .052 .052 28 .391 .388 38 .017 .017 29 .195 .188 591 1.7016 1.7006 39 .006 .007 210 .098 .098 592 .0288 .0300 310 .002 .002 211 .049 .049 593 .0005 .0004 311 .001 .001 212 .024 .022 59≥4 .0000 .0000 3≥12 .000 .000 Table 5.12: Expected and Actual Occurrences of Division in S(11/{2, 3, 47}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 50.102 213 .012 .014 31 37.981 37.981 22 25.000 24.961 214 .006 .006 32 12.660 12.639 23 12.500 12.481 215 .003 .005 33 4.220 4.216 24 6.250 6.179 216 .002 .002 34 1.407 1.429 25 3.125 3.133 2≥17 .002 .000 35 .469 .474 26 1.563 1.568 36 .156 .158 27 .781 .777 37 .052 .050 28 .391 .393 38 .017 .016 29 .195 .205 471 2.1551 2.1576 39 .006 .005 210 .098 .102 472 .0459 .0436 310 .002 .002 211 .049 .051 473 .0010 .0007 311 .001 .001 212 .024 .020 47≥4 .0000 .0000 3≥12 .000 .000 Chapter 5. Evidence Supporting this Model 36 Table 5.13: Expected and Actual Occurrences of Division in S(11/{2, 3, 53}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.969 213 .012 .010 31 37.848 37.830 22 25.000 25.136 214 .006 .005 32 12.616 12.689 23 12.500 12.333 215 .003 .003 33 4.205 4.176 24 6.250 6.241 216 .002 .002 34 1.402 1.380 25 3.125 3.170 217 .001 .001 35 .467 .476 26 1.563 1.594 218 .000 .001 36 .156 .140 27 .781 .772 2≥19 .000 .000 37 .052 .050 28 .391 .387 38 .017 .022 29 .196 .201 531 1.9847 1.9880 39 .006 .007 210 .098 .102 532 .0374 .0337 310 .002 .001 211 .049 .051 533 .0007 .0012 311 .001 .001 212 .024 .023 53≥4 .0000 .0000 3≥12 .000 .000 Table 5.14: Expected and Actual Occurrences of Division in S(19/{2, 3, 5, 11}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.992 31 30.759 30.789 37 .042 .039 22 25.000 24.951 32 10.253 10.214 38 .014 .018 23 12.500 12.508 33 3.418 3.451 39 .005 .004 24 6.250 6.265 34 1.139 1.105 310 .002 .001 25 3.125 3.167 35 0.380 .391 311 .001 .001 26 1.563 1.557 36 .127 .124 3≥12 .000 .000 27 .781 .797 28 .391 .383 29 .195 .186 210 .098 .094 211 .049 .048 51 20.841 20.814 212 .024 .024 52 4.168 4.185 213 .012 .016 53 .834 .837 111 9.6997 9.6987 214 .006 .006 54 .167 .172 112 .8818 .8873 215 .003 .003 55 .033 .036 113 .0802 .0757 216 .002 .002 56 .007 .005 114 .0073 .0067 217 .001 .001 57 .001 .001 115 .0007 .0012 2≥18 .001 .000 5≥8 .000 .000 11≥6 .0001 .0000 Chapter 5. Evidence Supporting this Model 37 Table 5.15: Expected and Actual Occurrences of Division in S(11/{2, 3, 61}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.933 213 .012 .014 31 38.104 38.037 22 25.000 25.045 214 .006 .006 32 12.701 12.741 23 12.500 12.471 215 .003 .003 33 4.234 4.243 24 6.250 6.287 216 .002 .001 34 1.411 1.424 25 3.125 3.105 217 .001 .001 35 .470 .466 26 1.563 1.583 218 .000 .001 36 .157 .167 27 .781 .799 2≥19 .000 .000 37 .052 .053 28 .391 .387 38 .017 .016 29 .195 .192 611 1.6488 1.6454 39 .006 .006 210 .098 .098 612 .0270 .0299 310 .002 .001 211 .049 .049 613 .0004 .0009 311 .001 .001 212 .024 .025 61≥4 .0000 .0000 3≥12 .000 .000 Table 5.16: Expected and Actual Occurrences of Division in S(23/{2, 3, 5, 7}) Div exp % Act % Div exp % Act % Div exp % Act % 21 50.000 49.962 31 36.069 36.044 36 .148 .145 22 25.000 24.943 32 12.023 12.058 37 .049 .047 23 12.500 12.556 33 4.008 3.994 38 .016 .016 24 6.250 6.224 34 1.336 1.350 39 .005 .004 25 3.125 3.125 35 .445 .441 310 .002 .003 26 1.563 1.613 3≥11 .001 .001 27 .781 .788 28 .391 .387 29 .195 .206 210 .098 .099 51 18.251 18.280 211 .049 .051 52 3.650 3.639 71 14.976 14.974 212 .024 .025 53 .730 .721 72 2.139 2.141 213 .012 .011 54 .146 .137 73 .306 .308 214 .006 .005 55 .029 .029 74 .044 .042 215 .003 .003 56 .006 .006 75 .006 .005 216 .002 .002 57 .001 .001 76 .001 .001 2≥17 .002 .001 5≥8 .000 .000 7≥7 .000 .000 Chapter 5. Evidence Supporting this Model 38 5.3 Occurrence of Residues Finally, the principal eigenvectors were tested. The 500 randomly generated numbers were run through the same test as the previous section; however this time the residues modulo p1 · · · pk were tallied for each system S(m/{p1, ..., pk}) instead of the number of divisions. Again, the expected and actual percentages are significantly close, suggesting that this model is likely appropriate. Table 5.17: Expected and Actual Occurrences for Residues in S(17/{2, 3, 5}) Res exp % Act % Res exp % Act % Res exp % Act % 1 14.996 14.987 13 9.729 9.717 23 13.223 13.204 7 13.443 13.444 17 12.170 12.233 29 10.326 10.347 11 10.035 10.029 19 16.077 16.038 Table 5.18: Expected and Actual Occurrences for Residues in S(5/{2, 7}) Res exp % Act % Res exp % Act % Res exp % Act % 1 15.827 15.859 5 22.302 22.302 11 8.633 8.622 3 20.144 20.161 9 10.072 10.119 13 23.022 22.937 Table 5.19: Expected and Actual Occurrences for Residues in S(9/{2, 5, 11}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 3.1752 3.2983 41 2.6844 3.1351 79 2.2477 2.4142 3 1.4996 1.5039 43 1.7844 1.7128 81 3.0690 3.3052 7 3.2776 3.1746 47 2.9884 2.5763 83 1.8999 2.0900 9 2.3722 2.3134 49 2.4331 2.3252 87 3.1017 2.9552 13 1.9014 2.0048 51 3.2383 2.7756 89 2.2533 2.4266 17 1.6037 1.7094 53 2.0513 1.7959 91 2.5029 2.5397 19 2.3570 2.2552 57 3.3360 3.3049 93 1.9134 1.7985 21 2.9355 2.8396 59 2.5073 2.5026 97 3.1807 3.1757 23 2.0112 2.0395 61 2.0955 2.1248 101 3.2459 3.3120 27 2.9892 3.0151 63 2.0107 1.9487 103 1.7976 2.0036 29 1.9870 2.1065 67 3.3156 3.1878 107 2.5435 3.2354 31 3.3825 3.1551 69 2.4423 2.3248 109 2.2143 1.9358 37 3.2932 3.3147 71 3.3004 3.1290 39 1.4078 1.5635 73 1.6490 1.6709 Chapter 5. Evidence Supporting this Model 39 Table 5.20: Expected and Actual Occurrences for Residues in S(11/{2, 3, 67}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 .89434 .89504 137 .66349 .65522 269 .66690 .66736 5 .65235 .67151 139 .86943 .87190 271 .86653 .86993 7 .80489 .82873 143 .65949 .64962 275 .65165 .67473 11 .66428 .66560 145 .88150 .88726 277 .88191 .87366 13 .87939 .87387 149 .66535 .67670 281 .64011 .64910 17 .50668 .49614 151 .89777 .89255 283 .88454 .88643 19 .88445 .88041 155 .62136 .62409 287 .66643 .67649 23 .66127 .66477 157 .88422 .86723 289 .87889 .87729 25 .86505 .86588 161 .64157 .63312 293 .66143 .65709 29 .59798 .58341 163 .83219 .83547 295 .80519 .79241 31 .86711 .85478 167 .65243 .64536 299 .65546 .64630 35 .65568 .65948 169 .89082 .88539 301 .87917 .87345 37 .87850 .88477 173 .66468 .67618 305 .62242 .62793 41 .61865 .62658 175 .84589 .85924 307 .88686 .89867 43 .88814 .88445 179 .66711 .68282 311 .66326 .66477 47 .60347 .60365 181 .86018 .86194 313 .89497 .91662 49 .86410 .86723 185 .66895 .66466 317 .65427 .66134 53 .65960 .66031 187 .88290 .86640 319 .88891 .90033 55 .88440 .87750 191 .65016 .65761 323 .66337 .65896 59 .66339 .66031 193 .88622 .90324 325 .85847 .85488 61 .89108 .89556 197 .66636 .65584 329 .66448 .66103 65 .66420 .66134 199 .89491 .89660 331 .88193 .89711 71 .66614 .65543 203 .66874 .66944 337 .88827 .88435 73 .88229 .89473 205 .89127 .89037 341 .65602 .65148 77 .66579 .66197 209 .66624 .66456 343 .88734 .87086 79 .88114 .87844 211 .88166 .88788 347 .65686 .65190 83 .65700 .64765 215 .63207 .64526 349 .85983 .87252 85 .86535 .87812 217 .88753 .90521 353 .64646 .65916 89 .64419 .65273 221 .65710 .67390 355 .85817 .87273 91 .87420 .86235 223 .88593 .90241 359 .66703 .63675 95 .59605 .58175 227 .65784 .65875 361 .86705 .85384 97 .88015 .85727 229 .81514 .82375 365 .66703 .66352 101 .67094 .66062 233 .65283 .64121 367 .86705 .86816 103 .87131 .87273 235 .56219 .56722 371 .64325 .63644 107 .65883 .65190 239 .65930 .64827 373 .88627 .90469 109 .81164 .80237 241 .86912 .86515 377 .67256 .66176 113 .65308 .65387 245 .66278 .65169 379 .85502 .83651 115 .85433 .86194 247 .88132 .87325 383 .64025 .63395 119 .66065 .66041 251 .66373 .67369 385 .88507 .86910 121 .83340 .81804 253 .86790 .88259 389 .64402 .63395 125 .65396 .65937 257 .52430 .53163 391 .74841 .73679 127 .88423 .89006 259 .85575 .85197 395 .66028 .66549 131 .66510 .66861 263 .64991 .66300 397 .87980 .89317 133 .87147 .87013 265 .89305 .88279 401 .65814 .65283 Chapter 5. Evidence Supporting this Model 40 Table 5.21: Expected and Actual Occurrences for Residues in S(11/{2, 3, 59}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 .9972 .9837 121 .9582 .9631 239 .7057 .6956 5 .6822 36670 125 .7648 .7780 241 .9372 .9255 7 1.0080 1.0111 127 .9652 .9539 245 .7425 .7446 11 .7638 .7643 131 .7283 .7343 247 1.0043 1.0134 13 1.0015 1.0040 133 1.0137 .9926 251 .5760 .5769 17 .7610 .7607 137 .7623 .7662 253 .9769 .9791 19 1.0062 1.0321 139 1.0050 1.0148 257 .7495 .7637 23 .7144 .7153 143 .7595 .7417 259 .9590 .9585 25 1.0158 1.0129 145 1.0060 .9934 263 .7584 .7544 29 .7380 .7540 149 .7397 .7377 265 .9899 .9899 31 .9865 .9867 151 1.0129 1.0133 269 .7634 .7716 35 .7647 .7729 155 .7638 .7516 271 1.0188 1.0047 37 .8884 .9026 157 1.0146 1.0149 275 .7603 .7680 41 .7425 .7653 161 .7639 .7635 277 .9786 .9825 43 1.0111 .9906 163 .9978 .9962 281 .7458 .7599 47 .7518 .7630 167 .7585 .7598 283 1.0035 .9984 49 .9964 1.0067 169 1.0105 1.0100 287 .76291 .7655 53 .7623 .7569 173 .7631 .7475 289 1.0002 1.0070 55 1.0159 1.0290 175 1.0084 1.0307 293 .7663 .7766 61 .9955 1.0273 179 .7292 .7266 299 .7626 .7587 65 .6964 .6985 181 .9816 .9797 301 .9164 .9054 67 1.0066 1.0041 185 .7603 .7506 305 .6007 .5922 71 .6992 .7083 187 .8417 .8508 307 1.0013 1.0127 73 1.0157 1.0102 191 .7471 .7478 311 .7365 .7381 77 .7442 .7452 193 .9948 .9934 313 1.0009 .9864 79 1.0129 1.0055 197 .7586 .7552 317 .7544 .7515 83 .7528 .7493 199 1.0054 1.0107 319 .8821 .8723 85 .9351 .9322 203 .7655 .7717 323 .7673 .7636 89 .7601 .7601 205 .9742 .9761 325 .6327 .6103 91 .9639 .9702 209 .7282 .7243 329 .7450 .7426 95 .7546 .7558 211 1.0068 1.0145 331 .9891 .9908 97 1.0034 .9874 215 .7373 .7236 335 .7564 .7416 101 .7719 .7696 217 .9950 .9911 337 1.0066 1.0248 103 .9988 .9934 221 .7547 .7493 341 .7698 .7599 107 .6788 .6842 223 1.0201 1.0126 343 .9840 .9948 109 .9957 1.0084 227 .7487 .7712 347 .7579 .7593 113 .7388 .7527 229 1.0072 1.0114 349 .9950 .9921 115 1.0106 .9948 233 .7544 .7560 353 .7627 .7587 119 .7545 .7358 235 .9749 .9570 Chapter 5. Evidence Supporting this Model 41 Table 5.22: Expected and Actual Occurrences for Residues in S(11/{2, 3, 47}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.2577 1.2195 97 1.2810 1.2720 191 .9099 .9344 5 .8982 .8843 101 .9369 .9274 193 1.2006 1.2150 7 1.2362 1.2503 103 1.2695 1.2702 197 .9596 .9444 11 .9621 .9498 107 .9415 .9274 199 1.2713 1.2686 13 1.2329 1.2557 109 1.2746 1.2657 203 .9692 .9530 17 .9440 .9779 113 .9594 .9286 205 1.2084 1.2229 19 1.2801 1.2695 115 1.1846 1.2110 209 .9784 .9876 23 .9202 .9087 119 .9623 9595 211 1.2202 1.2166 25 1.2377 1.2309 121 1.2492 1.2455 215 .9299 .9227 29 .9690 .9424 125 .9554 .9462 217 1.2878 1.2675 31 1.2762 1.2810 127 1.2326 1.2361 221 .9427 .9378 35 .9396 .9401 131 .9617 .9690 223 1.2412 1.2329 37 1.2756 1.2976 133 1.2558 1.2743 227 .9576 .9575 41 .9546 .9575 137 .9535 .9774 229 1.2653 1.2743 43 1.1582 1.1603 139 1.2850 1.2738 233 .9069 .9207 49 1.2280 1.2261 143 .9227 .9161 239 .8611 .8397 53 .9591 .9849 145 1.1845 1.1879 241 1.1569 1.1680 55 1.0566 1.0568 149 .7509 .7717 245 .9733 .9541 59 .7274 .7323 151 1.2884 1.3043 247 1.2593 1.2478 61 1.2763 1.2578 155 .9473 .9378 251 .9650 .9729 65 .9665 .9618 157 1.2637 1.2734 253 1.2706 1.2862 67 1.2793 1.2593 161 .9700 .9740 257 .9721 .9582 71 .9527 .9383 163 1.2935 1.3197 259 .7876 .7902 73 1.2358 1.2507 167 .9312 .9130 263 .9667 .9769 77 .9459 .9161 169 1.2510 1.2569 265 1.2681 1.2731 79 1.2631 1.2327 173 .9185 .9360 269 .8513 .8693 83 .9491 .9537 175 1.2129 1.1917 271 1.2861 1.2808 85 1.2886 1.3172 179 .9806 .9582 275 .9436 .9523 89 .9683 .9394 181 1.2739 1.3113 277 1.2872 1.2912 91 1.2828 1.2903 185 .9668 .9772 281 .9713 .9616 95 .9471 .9274 187 1.2029 1.1922 Chapter 5. Evidence Supporting this Model 42 Table 5.23: Expected and Actual Occurrences for Residues in S(11/{2, 3, 53}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.0946 1.1174 109 1.0640 1.0573 215 .7910 .7956 5 .8529 .8816 113 .8436 .8667 217 1.1089 1.0867 7 1.1185 1.1534 115 .9241 .9284 221 .6670 .6662 11 .8355 .8211 119 .8550 .8582 223 1.1237 1.1283 13 1.1357 1.1318 121 1.1157 1.1136 227 .8508 .8472 17 .8516 .8456 125 .8486 .8454 229 1.1009 1.1046 19 1.1329 1.1311 127 1.1129 1.1216 233 .8320 .8351 23 .8441 .8465 131 .8043 .8084 235 1.1228 1.1260 25 1.1286 1.1075 133 .6929 .6772 239 .8333 .8491 29 .8294 .8801 137 .7497 .7567 241 1.0947 1.1152 31 1.0438 1.0401 139 1.1183 1.1271 245 .8478 .8445 35 .8337 .8199 143 .8489 .8202 247 1.0201 1.0295 37 1.1215 1.1306 145 1.1086 1.1205 251 .8569 .8825 41 .8306 .7975 149 .8526 .8607 253 1.1158 1.1134 43 1.1261 1.1603 151 1.1294 1.1134 257 .8491 .8402 47 .8502 .8218 155 .8516 .8413 259 1.1247 1.0953 49 1.1212 1.1170 157 1.1293 1.1130 263 .8545 .8570 55 1.1198 1.1117 161 .8363 .8524 269 .8353 .8453 59 .8320 .8143 163 1.0980 1.1236 271 1.1271 1.1016 61 1.1082 1.1036 167 .8455 .8376 275 .8025 .7779 65 .8655 .8993 169 1.1263 1.1181 277 1.0889 1.0719 67 1.1012 1.0636 173 .8349 .8211 281 .8075 .8093 71 .8478 .8646 175 1.1017 1.0782 283 1.1253 1.1326 73 1.0295 1.0278 179 .8611 .8758 287 .8429 .8429 77 .8547 .8884 181 1.0938 1.0988 289 1.1419 1.1352 79 1.1241 1.1530 185 .8431 .8441 293 .8085 .8198 83 .8375 .8436 187 1.0906 1.0683 295 1.1175 1.0864 85 1.0343 1.0502 191 .7842 .7713 299 .8455 .8582 89 .8582 .8532 193 1.1220 1.1248 301 1.1328 1.0962 91 1.1268 1.1455 197 .8559 .8589 305 .6380 .6320 95 .8167 .8278 199 1.1330 1.1597 307 1.0832 1.0934 97 1.0949 1.0629 203 .8039 .8205 311 .8256 .8198 101 .8569 .8805 205 1.1001 1.0901 313 1.1226 1.0828 103 1.0301 1.0241 209 .8418 .8395 317 .8208 .8120 107 .8295 .8248 211 1.0999 1.1111 Chapter 5. Evidence Supporting this Model 43 Table 5.24: Expected and Actual Occurrences for Residues in S(19/{2, 3, 5, 11}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 1.5251 1.4997 109 1.5668 1.5525 227 1.1739 1.1979 7 1.6422 1.6384 113 1.0030 .9936 229 1.6233 1.6136 13 .7413 .7301 119 1.0259 1.0419 233 1.1724 1.1852 17 1.1798 1.1703 127 .8169 .8051 239 1.0265 1.0535 19 1.5230 1.5448 131 1.1150 1.1323 241 1.5259 1.5230 23 1.3653 1.3835 133 1.0562 1.0482 247 1.5016 1.5078 29 1.0450 1.0311 137 1.3575 1.3470 251 1.2450 1.2504 31 1.6470 1.6345 139 1.3946 1.3785 257 1.3202 1.3203 37 1.6261 1.6497 149 .9985 1.0008 259 1.0662 1.0378 41 1.0905 1.0830 151 1.3710 1.3828 263 1.1982 1.1869 43 1.0200 1.0258 157 1.6138 1.6155 269 1.1376 1.1222 47 1.0847 1.1025 161 1.1712 1.1794 271 1.4354 1.4590 49 1.5560 1.5725 163 1.0558 1.0628 277 1.5000 1.4720 53 1.2980 1.2816 167 1.1470 1.1443 281 1.1423 1.1554 59 1.0816 1.1030 169 1.5699 1.5795 283 .9934 .9854 61 .8192 .8198 173 1.2794 1.2787 287 1.1773 1.2025 67 1.6027 1.6011 179 1.0872 1.0499 289 1.4086 1.4186 71 1.2476 1.2513 181 1.5894 1.5910 293 1.2922 1.2963 73 .8493 .8383 191 1.0842 1.0785 299 .8782 .8683 79 1.3377 1.3088 193 .9760 .9888 301 1.6598 1.6470 83 1.1997 1.1999 197 1.1586 1.1547 307 1.6163 1.5946 89 .9370 .9446 199 1.4372 1.4350 311 .84457 .8671 91 1.5101 1.5271 203 1.3630 1.3657 313 1.0320 1.0335 97 1.7656 1.7836 211 1.6323 1.6182 317 1.2354 1.2561 101 1.2105 1.1790 217 1.3051 1.3018 323 1.2721 1.2792 103 1.0030 1.0119 221 1.1679 1.1729 329 .9366 .9229 107 1.2888 1.2968 223 1.0452 1.0313 Chapter 5. Evidence Supporting this Model 44 Table 5.25: Expected and Actual Occurrences for Residues in S(11/{2, 3, 61}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 .9826 .9937 125 .7308 .7254 245 .7317 .7276 5 .7237 .7121 127 .9818 .9862 247 .9784 .9968 7 .9542 .9494 131 .7260 .7034 251 .7168 .7243 11 .7254 .7154 133 .9618 .9602 253 .9528 .9746 13 .9677 .9762 137 .7329 .7452 257 .7140 .7162 17 .6608 .6545 139 .9245 .9125 259 .9727 .9662 19 .9388 .9385 143 .7381 .7342 263 .7161 .7106 23 .7344 .7300 145 .8928 .8650 265 .9593 .9724 25 .9759 .9920 149 .7244 .7394 269 .7344 .7245 29 .7292 .7127 151 .9758 .9779 271 .9760 1.0096 31 .6115 .5945 155 .7362 .7383 275 .7309 .7317 35 .7179 .7288 157 .9731 .9613 277 .9436 .9489 37 .8944 .8904 161 .7091 .7204 281 .7280 .7553 41 .7263 .7346 163 .9840 .9817 283 .9417 .9301 43 .9641 .9649 167 .7339 .7461 287 .7156 .7158 47 .7093 .7003 169 .9703 .9799 289 .9764 .9802 49 .9800 1.0015 173 .5745 .5619 293 .6917 .6877 53 .7083 .7123 175 .9603 .9580 295 .8164 .8072 55 .9635 .9761 179 .6662 .6885 299 .7326 .7267 59 .6982 .6916 181 .9488 .9523 301 .9095 .8853 65 .7343 .7399 185 .7417 .7398 307 .9708 .9771 67 .9892 .9634 187 .9841 .9889 311 .7362 .7437 71 .7238 .7040 191 .7355 .7315 313 .9820 1.0148 73 .9730 .9758 193 .9539 .9519 317 .7353 .7445 77 .7266 .7217 197 .7172 .7171 319 .9684 .9707 79 .9604 .9431 199 .9814 .9914 323 .7357 .7548 83 .7204 .7191 203 .6841 .6890 325 .9538 .9480 85 .9787 1.0075 205 .9738 .9697 329 .7244 .7282 89 .6958 .6963 209 .7053 .7119 331 .9400 .9426 91 .9720 .9782 211 .9411 .9115 335 .7301 .7373 95 .7251 .7388 215 .7292 .7342 337 .9660 .9566 97 .9796 .9701 217 .9406 .9344 341 .7241 .7284 101 .7138 .7047 221 .7264 .7208 343 .9771 .9439 103 .9906 .9798 223 .8846 .9012 347 .6929 .6767 107 .5523 .5420 227 .7351 .7334 349 .9735 .9664 109 .9619 .9686 229 .9801 .9868 353 .7293 .7105 113 .7176 .7344 233 .7189 .7309 355 .9716 .9632 115 .9660 .9620 235 .9521 .9690 359 .7326 .7159 119 .7196 .7086 239 .6563 .6535 361 .9014 .8888 121 .9688 .9902 241 .9735 .9637 365 .7200 .7102 Chapter 5. Evidence Supporting this Model 45 Table 5.26: Expected and Actual Occurrences for Residues in S(23/{2, 3, 5, 7}) Res Exp % Act % Res Exp % Act % Res Exp % Act % 1 2.6144 2.6120 71 2.0251 2.0468 143 2.2849 2.2957 11 1.8404 1.8959 73 1.9797 1.9974 149 1.8478 1.8283 13 1.4270 1.4446 79 2.6497 2.6495 151 1.6125 1.5920 17 2.1123 2.0861 83 1.9523 1.9461 157 2.5821 2.5809 19 2.8056 2.8401 89 1.6456 1.6431 163 1.8009 1.8054 23 1.7093 1.6731 97 1.9812 1.9930 167 1.9100 1.9241 29 1.9745 2.0122 101 1.6172 1.5967 169 2.5721 2.5208 31 2.4670 2.4563 103 1.6948 1.6729 173 1.9537 1.9523 37 2.6621 2.6591 107 1.9392 1.9278 179 1.7728 1.7516 41 1.9652 1.9917 109 1.9463 1.9764 181 2.5073 2.4962 43 1.6622 1.6195 113 2.3006 2.3239 187 2.6786 2.6429 47 1.9446 1.9675 121 2.5091 2.5156 191 1.4267 1.4160 53 2.1960 2.1828 127 2.5957 2.5888 193 1.9014 1.8981 59 1.8105 1.8280 131 1.7385 1.7363 197 2.2110 2.2192 61 2.7395 2.7299 137 2.1670 2.1428 199 2.6250 2.6314 67 1.8310 1.8356 139 2.3462 2.3467 209 1.4635 1.5067 Chapter 5. Evidence Supporting this Model 46 5.4 Other Data Table 5.27: Multiplicative Expectations for some Systems System Exp. System Exp. System Exp. S(3/{2}) 0.75 S(7/{2, 3}) 0.9052 S(11/{2, 3}) 1.0724 S(7/{2, 5}) 0.9642 S(11/{2, 3, 17}) 0.9190 S(5/{2}) 1.25 S(7/{2, 11, 13}) 1.1155 S(11/{2, 3, 19}) 0.9031 S(5/{2, 3}) 0.4875 S(7/{2, 11, 17}) 1.1711 S(11/{2, 3, 23}) 0.9386 S(5/{2, 7}) 1.0275 S(11/{2, 3, 29}) 0.9550 S(5/{2, 7, 11}) 0.7546 S(9/{2, 5, 11}) 1.0182 S(11/{2, 3, 31}) 0.9560 S(5/{2, 7, 13}) 0.8419 S(11/{2, 3, 37}) 0.9655 S(5/{2, 7, 17}) 0.8161 S(13/{2, 3, 5}) 1.0845 S(11/{2, 3, 41}) 0.9764 S(5/{2, 7, 19}) 0.8433 S(11/{2, 3, 43}) 0.9784 S(5/{2, 7, 23}) 0.8672 S(17/{2, 3, 5}) 1.0384 S(11/{2, 3, 47}) 0.9897 S(5/{2, 7, 29}) 0.9104 S(11/{2, 3, 53}) 0.9931 S(5/{2, 7, 31}) 0.8889 S(19/{2, 3, 5, 7}) 0.9592 S(11/{2, 3, 59}) 1.0015 S(5/{2, 11}) 0.9263 S(19/{2, 3, 5, 11}) 0.9957 S(11/{2, 3, 61}) 0.9994 S(5/{2, 11, 13}) 0.7688 S(19/{2, 3, 5, 13}) 1.0727 S(11/{2, 3, 67}) 1.0043 S(5/{2, 11, 17}) 0.7528 S(5/{2, 11, 19}) 0.7728 S(23/{2, 3, 5, 7}) 0.9994 Table 5.28: Random Numbers Used in Trials Ref # 8 Digits 9 Digits 10 Digits 11 Digits 12 Digits 1 43949058 133751076 5840371500 73715876729 712999543523 2 57237679 586158240 8010929594 65700862943 245330984447 3 56764175 467287522 6491108036 32424170465 376587456075 4 15883987 153610815 5112460519 25235196453 641902908204 5 84600232 879850007 3816384844 27988963610 374651966999 6 95132796 319106125 5144164697 44344539876 406449767634 7 44637620 155540012 9463631539 17412421905 850409669815 8 36107037 225500149 8732145756 95818212663 902454155507 9 20607915 168378689 7106418225 53421525586 434796455572 10 47522486 868172695 9415955883 83497475450 772869014214 11 14922351 532668526 1581869302 72877304839 440895669155 12 61780436 505135326 5161255391 52427536557 839457647004 13 62449056 437262560 6244301281 59407854984 212155351554 14 56403365 235838395 1809094426 64966684858 942468887962 15 49054505 996998889 9451185402 75976255360 522605526665 16 79209560 554958197 8412421905 32385044556 960696306908 17 58557997 301029038 4427838553 68760991782 164544616043 18 22870850 190777717 2275731771 21770990285 260846663823 19 90377252 915637919 1020544909 71942394930 727488467546 20 63530478 750994542 5777998714 96646091147 232783285421 21 76253611 801327918 9067798189 88606118334 119182685523 22 36965090 632834019 4427077306 43489062233 996485642968 Continued on next page Chapter 5. Evidence Supporting this Model 47 Table 5.28 – continued from previous page Ref # 8 Digits 9 Digits 10 Digits 11 Digits 12 Digits 23 69871636 830798472 6205175372 19949508400 936386069679 24 86951880 869381295 8221384230 82466529986 197309133939 25 12831035 310675943 3039073006 27820308836 702222289407 26 43751076 724983095 1746745227 52924197337 796005861184 27 93505056 686128038 4747053250 52184753306 375130015257 28 63610815 604386587 1640439652 14832623175 962790603924 29 94888397 751006053 9564458969 94884659950 814721677141 30 65540012 182648824 8825014938 16402031176 792355458282 31 78378689 262087183 5832623175 98749509928 392167296340 32 59739450 675390759 7402031176 36310525699 459387387685 33 40015342 680542173 3850164008 58147481356 525549978857 34 95293656 998599952 9809907465 87529384201 633990756471 35 12482142 801311587 9746448575 70286056127 702882754492 36 78827104 177594039 2755486969 46115225337 502854435326 37 11620667 298358220 4468319344 59211688700 113642900126 38 89601089 455822512 8326244625 55043765555 718873478963 39 62305013 523966005 9602039667 47828057712 233400028636 40 76811310 172387746 7253613363 52961778035 444829638290 41 43506413 150986366 4323948758 42830562320 167499645464 42 20331551 434138857 7759224824 33433482547 480076868136 43 65166217 466604856 4765644424 82043425494 340110681519 44 96533896 654334954 4471087299 16759224824 965025968658 45 40239278 871925675 9666272892 99664990344 796074080969 46 69709832 280220195 8820451619 47830825667 239049672077 47 86458215 686491243 7790157226 87385749628 185248995821 48 98112183 517082766 1678852156 35000320803 642977065094 49 59257126 558538714 4477783405 26922489097 670667848839 50 92600807 108479921 6227996711 41837160257 782887092972 51 92648824 760382807 9192069084 16790157226 879083730166 52 37869455 106862945 8939108714 96578198076 938945695809 53 48519847 153853750 8640307487 73401152795 409422465404 54 53671261 224776206 8280969794 53938185730 550355304119 55 40222947 257138152 8214771064 30657652589 998424235844 56 87594039 523909157 2685003584 40015471722 896000531765 57 74140492 760224790 3411870849 54377527460 286536289525 58 97387056 678769206 7031029662 75712276810 784306233136 59 31312821 705257537 2515103006 22943051994 805459503577 60 82387746 552469185 7841126466 17939108714 723335325513 61 60986366 461477542 2530490810 57051442205 259302577763 62 75703401 953606850 2696117849 34820176671 572240858908 63 27464042 381084412 8417214051 44305877875 307359064348 64 56002467 949586749 6963861911 94751725183 801595835584 65 59620331 159524752 7168077974 85934247800 582397680149 66 24429582 231172352 9000141896 80404480320 453009746412 67 20640797 847231251 7959393264 29591740033 602558523846 68 61601423 915190201 3027039028 23778547388 123159642540 69 65885530 100096362 3275654012 93869421791 443196548673 70 18479921 116935512 9214457779 80234579742 198729629455 71 16862945 750771551 3161184684 80249967546 133109574076 72 63853750 764526952 7217327664 39914302785 420494988756 73 32920424 162176315 3595154464 57907948208 975851612875 74 31255973 571873640 7436198272 28875987033 559645047754 75 51898294 891350242 1147391738 20253357838 515410977136 76 78386625 605373287 2559873971 44048322494 330171922316 77 59816001 570051117 8213482157 67707685526 946351270862 Continued on next page Chapter 5. Evidence Supporting this Model 48 Table 5.28 – continued from previous page Ref # 8 Digits 9 Digits 10 Digits 11 Digits 12 Digits 78 15243879 576381427 5488496564 69539749448 167168041201 79 58300482 338325266 3835191639 46386777396 672503985973 80 22648956 429516409 4220971953 20051167073 316743634717 81 54280381 162361065 1571213604 29455523196 198560622730 82 69524752 885646024 2214072539 21665563720 776680397324 83 86142611 456504794 8740009824 76595608988 810831734671 84 19883833 686314289 7989562509 89707157378 903731560158 85 10096362 110146328 1034763086 46520923052 442365266447 86 26935512 223154542 3293225236 20576246183 430390789287 87 57983973 512565683 7179026992 38117398376 108175679917 88 72176315 358368043 4274574484 50577066032 463510107747 89 79220456 821241591 5468789396 91518159752 969052139615 90 26214538 102025624 2086437636 44507130106 674081019884 91 77397933 411526687 7462942210 60920595976 639703917065 92 83728243 393054814 8828028661 83207973300 573607925886 93 94404206 356061060 6591305713 30015060823 695464058943 94 71080953 969610764 6359464643 81940448689 797628332934 95 72361065 881563360 3336703164 44930951972 597366716315 96 98069338 249125755 9107722004 61463846750 213095867233 97 59443377 282240337 6771746857 40474318427 837491010327 98 20146328 623149147 1142887412 17740009824 888789117562 99 19912499 406855912 1699530444 57577745160 152573214076 100 60152951 892862344 9063216615 61574370638 606458752129 49 Bibliography [1] Robert G. Gallager, Discrete Stochastic Processes, Kluwer Academic Pub- lishers, Norwell, Massachusetts, 3rd ed., 1996. [2] Steven G. Krantz, Real Analysis and Foundations, Chapman & Hall, 2nd ed., 2004. [3] J. C. Lagarias, The 3x+1 Problem and its Generalizations, the American Mathematics Monthly 92 (1985), no. 1, 3–23. [4] G. Latouche, V. Ramaswami, Introduction to Matrix Analytic Methods in Stochastic Modelling, PH Distributions, ASA SIAM, 1st ed., 1999. [5] Toms Oliveira e Silva, (January 19, 2009). 3x+1 conjecture verification results. Retrieved July 14, 2009 from http://www.ieeta.pt/ tos/3x+1.html.
- Library Home /
- Search Collections /
- Open Collections /
- Browse Collections /
- UBC Theses and Dissertations /
- Collatz-type problems with multiple divisors
Open Collections
UBC Theses and Dissertations
Featured Collection
UBC Theses and Dissertations
Collatz-type problems with multiple divisors Gunn, Keira 2009
pdf
Notice for Google Chrome users:
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
If you are having trouble viewing or searching the PDF with Google Chrome, please download it here instead.
Page Metadata
Item Metadata
Title | Collatz-type problems with multiple divisors |
Creator |
Gunn, Keira |
Publisher | University of British Columbia |
Date Issued | 2009 |
Description | The Collatz Conjecture hypothesizes that if a sequence of integers beginning with any positive integer t₀ is recursively defined so that t_j₊₁ = (t_j)/2 when t_j is even and t_j₊₁ = 3(t_j)+1 when t_j is odd, then there will be some j in the set of natural numbers such that t_j = 1. I propose a similar family of problems (which I call systems) involving a set of prime divisors {p₁,...,p_k} and a multiplier m, where the sequence is recursively defined so that t_j₊₁ = (t_j)/(p₁) if t_j is divisible by p₁, t_(j₊₁) = (t_j)/(p₂) if t_j is divisible by p₂ but not p₁, t_(j+1) = (t_j)/(p₃) if t_j is divisible by p₃ but not p₁ or p₂ etc., and if t_j is not divisible by any of the primes, then t_(j₊₁) = m(t_j)₊₁. Assuming the residues of the terms of these sequences behave randomly modulo p₁...p_k, I propose a multiplicative expectation and data to suggest that this is a reasonable model for these systems. If the expectation is less than 1, as in the case of the Collatz problem, then I hypothesize that any sequence will eventually result in some finite cycle. As well, if my model for these systems is accurate, then I prove that the inclusion of an increasing prime q to a fixed set of prime divisors will result in an effect that gradually diminishes for the multiplicative expectation of the system. |
Extent | 453927 bytes |
Genre |
Thesis/Dissertation |
Type |
Text |
FileFormat | application/pdf |
Language | eng |
Date Available | 2009-08-31 |
Provider | Vancouver : University of British Columbia Library |
Rights | Attribution-NonCommercial-NoDerivatives 4.0 International |
DOI | 10.14288/1.0067665 |
URI | http://hdl.handle.net/2429/12614 |
Degree |
Master of Science - MSc |
Program |
Mathematics |
Affiliation |
Science, Faculty of Mathematics, Department of |
Degree Grantor | University of British Columbia |
GraduationDate | 2009-11 |
Campus |
UBCV |
Scholarly Level | Graduate |
Rights URI | http://creativecommons.org/licenses/by-nc-nd/4.0/ |
AggregatedSourceRepository | DSpace |
Download
- Media
- 24-ubc_2009_fall_gunn_keira.pdf [ 443.29kB ]
- Metadata
- JSON: 24-1.0067665.json
- JSON-LD: 24-1.0067665-ld.json
- RDF/XML (Pretty): 24-1.0067665-rdf.xml
- RDF/JSON: 24-1.0067665-rdf.json
- Turtle: 24-1.0067665-turtle.txt
- N-Triples: 24-1.0067665-rdf-ntriples.txt
- Original Record: 24-1.0067665-source.json
- Full Text
- 24-1.0067665-fulltext.txt
- Citation
- 24-1.0067665.ris
Full Text
Cite
Citation Scheme:
Usage Statistics
Share
Embed
Customize your widget with the following options, then copy and paste the code below into the HTML
of your page to embed this item in your website.
<div id="ubcOpenCollectionsWidgetDisplay">
<script id="ubcOpenCollectionsWidget"
src="{[{embed.src}]}"
data-item="{[{embed.item}]}"
data-collection="{[{embed.collection}]}"
data-metadata="{[{embed.showMetadata}]}"
data-width="{[{embed.width}]}"
data-media="{[{embed.selectedMedia}]}"
async >
</script>
</div>
Our image viewer uses the IIIF 2.0 standard.
To load this item in other compatible viewers, use this url:
https://iiif.library.ubc.ca/presentation/dsp.24.1-0067665/manifest