A Solution to the 3x + 1 Problem A Solution to the 3x + 1 Problem by Peter Schorer (Hewlett-Packard Laboratories, Palo Alto, CA (ret.)) 2538 Milvia St. Berkeley, CA 94704-2611 Email: [email protected] Phone: (510) 548-3827 Jan. 20, 2015 “Very often in mathematics the crucial problem is to recognize and to discover what are the relevant concepts; once this is accomplished the job may be more than half done.”1 Important Note: The reader can safely assume, initially, that all referenced lemmas are true, since their proofs have been checked and deemed correct by several mathematicians. Thus it is only necessary to read pages 1 - 9, and the section “(3) Common Misconceptions About the Nature of Comparison of Mutually-Exclusive Cases”, pp. 14-18, in order to understand our proofs of the 3x + 1 Conjecture. We consider the best of these to be “Most Recent Proof of the Conjecture” on page 10 Key words: 3x + 1 Problem, 3n + 1 Problem, Syracuse Problem, Ulam’s Problem, Collatz Conjecture, computational number theory, proof of termination of programs, recursive function theory American Mathematical Society Classification Numbers: 11Y16, 11Z05, 03D20, 68Q60 1. Herstein, I. N., Topics in Algebra, John Wiley & Sons, N.Y., 1975, p. 50. 1 A Solution to the 3x + 1 Problem Abstract We present several proofs of the 3x + 1 Conjecture, which asserts that repeated iterations of the function C(x) = (3x + 1)/(2a) always terminate in 1 Here x is an odd, positive integer, and a = ord2(3x + 1), the largest positive integer such that the denominator divides the numerator. Our first proofs are based on a structure called “tuple-sets” that represents the 3x + 1 function in the “forward” (as opposed to the inverse) direction. In “Most Recent Proof of the Conjecture” on page 10, we show that, because the “number”1 of tuples in each tuple-set is the same, regardless if counterexamples exist or not, and because the set of all non-counterexamples is the same, regardless if counterexampels exist or not, it follows that counterexamples do not exist. In our next two proofs, we show, by a simple inductive argument, that the contents of the set of all tuple-sets is the same, regardless if counterexamples exist or not, and from this we conclude that counterexamples do not exist. “Third Proof” is based on a structure called “recursive ‘spiral’s” that represents the 3x + 1 function in the inverse direction. We show that, because a large number of consecutive odd, positive integers are known, by computer test, to be non-counterexamples, it follows, by an inductive argument based on certain fundamental properties of recursive “spiral”s, that the set of all tuples in each infinite set of recursive “spiral”s is the same regardless if counterexamples exist or not. We infer from this that counterexamples do not exist. As far as we have been able to determine, our approach to a solution of the Problem is original. 1. This is an abuse of language that is made precise in step 2 of the proof. 2 A Solution to the 3x + 1 Problem Introduction Statement of Problem For x an odd, positive integer, set 3x + 1 C(x) = ------------------------2 ord 2(3x + 1) where ord2(3x + 1) is the largest exponent of 2 such that the denominator divides the numerator. Thus, for example, C(17) = 13, C(13) = 5, C(5) = 1. The 3x + 1 Problem, also known as the 3n + 1 Problem, the Syracuse Problem, Ulam’s Problem, the Collatz Conjecture, Kakutani’s Problem, and Hasse’s Algorithm, asks if repeated iterations of C always terminate at 1. The conjecture that they do is hereafter called the 3x + 1 Conjecture. We call C the 3x + 1 function; note that C(x) is by definition odd. Other equivalent formulations of the 3x + 1 Problem are given in the literature; we base our formulation on the C function (following Crandall) because, as we shall see, it brings out certain structures that are not otherwise evident. Summary of Research on the Problem As stated in (Lagarias 1985), “The exact origin of the 3x + 1 problem is obscure. It has circulated by word of mouth in the mathematical community for many years. The problem is traditionally credited to Lothar Collatz, at the University of Hamburg. In his student days in the 1930’s, stimulated by the lectures of Edmund Landau, Oskar Petron, and Issai Schur, he became interested in number-theoretic functions. His interest in graph theory led him to the idea of representing such number-theoretic functions as directed graphs, and questions about the structure of such graphs are tied to the behavior of iterates of such functions. In the last ten years [that is, 19751985] the problem has forsaken its underground existence by appearing in various forms as a problem in books and journals...” On the Structure of This Paper To enhance readability, we have placed proofs of all lemmas in Appendix A. 3 A Solution to the 3x + 1 Problem Tuple-sets: The Structure of the 3x + 1 Function in the “Forward” Direction Definitions Iteration An iteration takes an odd, positive integer, x, to another odd, positive integer, y, via one application of the 3x + 1 function, C. Thus, in one iteration C takes 17 to 13 because C(17) = 13. Tuple A (finite) tuple is a sequence of zero or more successive iterations of C, that is, k C k x k 0 = x C(x) C 2 x C x A finite tuple is the prefix of an infinite tuple. If x is a non-counterexample, then x is the first element of an infinite tuple <x, y, ..., 1, 1, 1, ... >. Of course, if x is a range element of C, then x can be an element other than the first in another non-counterexample tuple. If x is a counterexample, then x is the first element of an infinite tuple <x, y, ... > which does not contain 1. Of course, if x is a range element of C, then x can be an element other than the first in another counterexample tuple. Exponent, Exponent Sequence If C(x) = y, with y = (3x + 1)/2a, we say that a is the exponent associated with x (in more formal language, this can be expressed as ord2(3x + 1) = a.) The sequence {a2, a3, ..., ai}, where a2, a3, ..., ai are the exponents associated with x, C(x), ..., C(i - 1)(x) respectively, is called an exponent sequence. We number exponents beginning with a2 in order that the subscript corresponds to a level number in the corresponding tuple-set. See “Levels in Tuples and Tuple-sets” on page 5 We say that x maps to y via ai if C(x) = y and ord2(3x + 1) = ai . By extension, we say that x maps to z if z is the result of a finite sequence of iterations of C beginning with x, that is if the tuple <x, y, ..., z> exists. Tuple-set Let A = {a2, a3, ..., ai} be a finite sequence of exponents, where i 2The tuple-set TA consists of all and only the tuples that are associated with all successive approximations to A. Thus TA consists of all and only the following tuples (Note: x, y, etc. in different tuples are different numbers): all tuples <x> such that x does not map to an odd, positive integer via a2; a3; all tuples <x, y> such that x maps to y via a2 but y does not map to an odd, positive integer via all tuples <x, y, y> such that x maps to y via a2 and y maps to y via a3, but y does not map to an odd, positive integer via a4; ... 4 A Solution to the 3x + 1 Problem all tuples <x, y, yy(i – 3)y(i – 2)> such that x maps to y via a2 and y maps to y via a3 and ... and y(i – 3) maps to y(i – 2) via the exponent ai. (The longest tuple in an i-level tuple-set has i elements.) And so on for tuples of four, five, ... (i – 1) elements. In other words, for each i-level exponent sequence A: there are tuples <x> whose associated exponent sequence approximates A for no exponent of A, and there are other tuples <x, y> whose associated exponent sequence approximates A for the first exponent of A, and there are other tuples <x, y, y> whose associated exponent sequence approximates A for the first two exponents of A, and ... there are other tuples <x, y, z, ..., y(i – 2)> whose associated exponent sequence approximates A for all i – 1 exponents of A. Tuples are ordered in the natural way by their first elements. The set of first elements of all tuples in a tuple-set is the set of odd, positive integers (see proof under “The Structure of Tuple-sets” on page 7). Thus, there is a countable infinity of tuples in each tuple-set. Levels in Tuples and Tuple-sets Let A be an i-level exponent sequence, {a2, a3, ..., ai}. The reason subscripts of exponents begin with 2, rather than with 0 or 1, is so that they correspond to levels in each tuple-set. (No tuple-set has only one level, because that would mean it is associated with no exponent sequence.) Let TA be the tuple-set determined by A. Then, by definition of tuple-set, there exist j-level tuples in TA, where 1 j i, that is, tuples t = <x, y, ..., z>, where x is the 1-level element of t, y is the 2level element of t, ..., and z is the j-level element of t. We say that TA is an i-level tuple-set, and we sometimes speak of the set of j-level tuple-elements in TA, where 1 j i. For 2 j i, two tuples are said to be consecutive at level j if no j-level or higher-level tuple exists between them. Example of Tuple-set As an example of (part of) a tuple-set: in Fig. 1, where A = {a2, a3, a4} = {1, 1, 2} and where we adopt the convention of orienting tuples vertically on the page, the tuple-set TA includes: the tuple <1>, because e(1) a2; the tuple <3, 5> , because e(3) = a2 = 1, but e(5) = 4 a3 = 1; the tuple <15, 23, 35>, because e(15) = a2 = 1, and e(23) = a3 = 1, but e(35) = 1 a4 = 2. 5 A Solution to the 3x + 1 Problem level 4 13 3 17 2 5 ... 35 18 17 11 53 23 29 ... 35 41 ... 1 1 3 5 7 9 11 13 15 17 19 21 4 23 25 27 ... tuple no. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 ... Fig. 1. Part of the tuple-set TA associated with the sequence A = {1, 1, 2} The number 18 between the arrows at level 3 and the number 4 between the arrows at level 1 are the values of the level 3 and level 1 distance functions, respectively, established by Lemma 1.0 (see “Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6). In each i-level tuple-set TA, where i 2, for each odd, positive integer x there exists a tuple whose first element is x. The tuple may be one-level (<x>), or 2-level (<x, y>), or ... or i-level (<x, y, yy(i – 3)y(i – 2)>). Thus each tuple-set is non-empty. Graphical Representation of the Set of All Tuple-sets It is clear from the definition of tuple-set that the set of all tuple-sets can be represented by an infinitary tree in which each node is a tuple-set. We can imagine the tuple-set (which contains an infinity of tuples) extending into the page. Lemmas Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i) (a) Let A = {a2, a3, ..., ai}, where i 2, be a sequence of exponents, and let t(r), t(s) be tuples consecutive at level i1 in TA. Then d(i, i) is given by: d i i = 2 3 i – 1 1. For 2 j i, two tuples are consecutive at level j if no j-level or higher-level tuple exists between them (see “Levels in Tuples and Tuple-sets” on page 5. 6 A Solution to the 3x + 1 Problem (b) Let t(r), t(s) be tuples consecutive at level i in TA. Then d(1, i) is given by: d 1 i = 2 2 a 2 2 a 3 2 ai Proof: see “Lemma 1.0: Statement and Proof” on page 25 Remark: Similar relationships hold for successive j-level tuples, where 2 j < i, but since they are not needed for our purposes in this paper, we have omitted stating them. The interested reader should see the section, “Remarks About the Distance Functions” in our paper, “Are We Near a Proof of the 3x + 1 Problem?”, on occampress.com. Lemma 2.0 Assume a counterexample exists. Then for all i 2, each i-level tuple-set contains an infinity of i-level counterexample tuples and an infinity of i-level non-counterexample tuples. Proof: “Lemma 2.0: Statement and Proof” on page 30 The Structure of Tuple-sets It is important for the reader to understand that the structure of each tuple-set is unchanged by the presence or absence of counterexample tuples. Regardless if counterexample tuples exist or not, the set of first elements of all tuples in each tuple-set is always the same, namely, the set of odd, positive integers. Proof: Let x be any odd, positive integer and let A = {a2, a3, ..., ai}, where i 2, be any exponent sequence. Then there are exactly two possibilities: (1) x maps to a y in a single iteration of the 3x + 1 function, C; (2) x does not map to a y in a single iteration of C. But if (1) is true, then the tuple <x> is in TA; if (2) is true, then a tuple containing at least two elements, with x as the first, is in TA. There is no third possibility. It can never be the case that, if counterexample tuples exist, then somehow there are “more” tuples in a tuple-set than if there are no counterexample tuples1. Furthermore, the distance functions defined in “Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6 are the same regardless if counterexample tuples exist or not. 1. To make this statement more precise: in no tuple-set does there ever exist a first element of a tuple, regardless how large that first element is, such that there are more tuples in that tuple-set having smaller first elements if counterexamples exist, than if counterexamples do not exist. 7 A Solution to the 3x + 1 Problem “Recursive ‘Spiral’s”: The Structure of the 3x + 1 Function in the Inverse Direction Lemma and Definitions Lemma 3.0 Exactly one set J of odd, positive integers maps to 1, regardless if counterexamples exist or not.1 Proof: see “Lemma 3.0: Statement and Proof” on page 30. Note: Readers who have difficulty believing that Lemma 3.0 is valid might be helped by the following: Let S1 denote the singleton set containing the set of all odd, positive integers. Let S2 denote the set containing all proper subsets of the odd, positive integers. Then if counterexamples do not exist, J S1; if counterexamples exist, then J S2. Another Way of Understanding the Lemma Another way of understanding the Lemma is the following: today, let all non-counterexample tuples in all tuple-sets be colored green. Then if there are no tuples in the set of all tuple-sets that are not green, we know that counterexamples do not exist; if there are tuples that are not green, then we know that counterexamples exist. A proof based on Lemma 3.0 is given under “Most Recent Proof of the Conjecture” on page 10. Definition of “Fixed-Set” We call the set J the Fixed-Set because it is the set of all odd, positive integers each of whose values, under the 3x + 1 function, is the same regardless if counterexamples exist or not. (Clearly, no counterexample can be an element of the Fixed-Set.) Definitions Pertaining to “Recursive ‘Spiral’s” The set J can be represented by an infinitary tree, as shown in the following figure. We thus sometimes refer to J as the 1-tree. 1. Some readers consider the phrase “regardless if counterexamples exist or not” as unnecessary. The reason we include it is that when it was not present, other readers assumed that the meaning of the Lemma was: exactly one set J of odd, positive integers maps to 1 (if counterexamples do not exist), and exactly one (different) set J of odd, positive integers maps to 1 if counterexamples exist. This meaning is incorrect. A second reason for including the phrase will become clear when the reader reads our proofs of the 3x + 1 Conjecture. 8 A Solution to the 3x + 1 Problem 453 85 21 1 26 5 1 22 1 2 6 113 22 24 22 24 2 22 1 10 2 1813 26 28 85 8 24 1 85 2 4 7253 1 28 85 2 8 341 1 2 10 85 2 6 .. . . .. Fig. 2. Recursive “spirals” structure of odd, positive integers that map to 1 Bold-faced numbers are range elements (21 and 453 are multiples of 3, hence are not range elements). Partial “spirals” surrounding the base elements 1 and 85 are shown. The line connecting 1813 to 85 is marked with a 26 because (3 • 181326 = 85. The line connecting 453 to 1813 is marked 85 • 24 because 453 + 85 • 24 = 1813. The exponents of 2 are not even in all “spiral”s, of course. For example, the “spiral” of numbers (not shown) mapping to 341 has odd exponents. The set of all x that map to a given range element y in one iteration of the 3x + 1 function is sometimes called a “recursive ‘spiral’ ”. Thus, for example, the set {1, 5, 21, 85, 341, ... } is a recursive “spiral”. It contains all odd, positive integers that map to 1 in one iteration of the 3x + 1 function. 9 A Solution to the 3x + 1 Problem Theorem. The 3x + 1 Conjecture is true. Most Recent Proof of the Conjecture Note 1: in order for this proof to be evaluated with minimum chance for misunderstandings, it is essential that it be read one sentence at a time, with the reader asking each time, “Is this sentence clear?” and “Is this sentence correct?” If the answer to either question is no, the reader is urged to stop reading and contact the author, so that he can try to repair the problem before the reader proceeds. If a proof is incorrect, then there is a first sentence in it that is incorrect. Note 2: Readers who have reservations about our use of the phrase, “whether or not counterexamples exist”, should refer to the section, “On the Phrase, “Whether or Not Counterexamples Exist”” on page 15. Readers who have difficulties understanding the proof should read the section, “(3) Common Misconceptions About the Nature of Comparison of Mutually-Exclusive Cases” on page 13, since the present proof is also based on a comparison of the two cases: counterexamples exist, and counterexamples do not exist. Proof: 0. We begin by stating two facts: (1) at the time of this writing, it is not known if counterexamples to the 3x + 1 Conjecture exist; and (2) it is known, by computer test, that if counterexamples exist, then the smallest one is greater than 1015. 1. Whether or not counterexamples exist, the set of first elements of all tuples in each tuple-set is the set of odd, positive integers. Specifically, the first element of the first tuple in each tuple-set is 1; the first element of the second tuple in each tuple-set is 3; the first element of the third tuple in each tuple-set is 5; the first element of the fourth tuple in each tuple-set is 7; … (See “The Structure of Tuple-sets” on page 7.) 2. Whether or not counterexamples exist, the set of non-counterexamples is the same (Lemma 3.0; thus, for example, 13 maps to 1 today, it will map to 1 if the Conjecture is proved true tomorrow, and it will map to 1 if the Conjecture is proved false tomorrow). Let J denote the set of non-counterexamples, and let M denote the set of odd, positive integers. Then the function f: J M that maps each non-counterexample n = 2k + 1 in J to 2k + 1 in M, is one-one. We can think of f as mapping each non-counterexample to the first element of a tuple in a tuple-set. 3. If counterexamples exist, then each tuple-set contains an infinity of counterexample tuples and an infinity of non-counterexample tuples (“Lemma 2.0” on page 7). 4. Assume counterexamples exist. Then, if step 1 is true, the set of non-counterexample tuples — that is, the set of tuples having a non-counterexample as first element — must be a proper subset of the tuples in each tuple-set. But this contradicts step 2, because it implies there is 10 A Solution to the 3x + 1 Problem not one set of non-counterexamples (hence non-counterexample tuples), but two: one if counterexamples exist, and another if counterexamples do not exist. Hence, counterexamples do not exist. An alternate step 4 is the following: Assume counterexamples exist. Then if step 2 is true, there are additional tuples in each tupleset beyond the ones described in step 1. These additional tuples are empty if counterexamples do not exist, and are occupied by counterexamples if counterexamples exist. But this contradicts step 1, hence counterexamples do not exist. . Remark 1 We challenge readers who are skeptical about the validity of the above proof to tell us how they imagine step 1, step 2, step 3, and the statement, “counterexamples exist” can all be true. So far, after more than 2,700 visits to this paper, we have received only one attempt to meet this challenge. It contained an obvious error. We regard the absence of successful challenges as further reason to believe the proof is correct. Remark 2 The proof passes the 3x – 1 Test, which asks if the proof also applies to the 3x – 1 Conjecture. If it does, then the proof is invalid, since the Conjecture is known to be false. The above proof passes the Test because step 0 does not apply to the 3x – 1 function — the smallest counterexamples to the 3x – 1 Conjecture are 5 and 7. . Earlier Proofs of the Conjecture Important Preliminary Remarks To properly understand the following proofs of the Conjecture, it is essential that the reader be aware of: (1) a common misconception about the nature of the 3x + 1 function, and (2) a common misconception about “3x + 1-like function” tests, and (3) common misconceptions about the nature of comparison of mutually-exclusive cases Furthermore, in order for the proofs to be evaluated with minimum chance for misunderstandings, it is essential that they be read one sentence at a time, with the reader asking each time, “Is this sentence clear?” and “Is this sentence correct?” If the answer to either question is no, the reader is urged to stop reading and contact the author, so that he can try to repair the problem before the reader proceeds. If a proof is incorrect, then there is a first sentence in it that is incorrect. We now provide a few details on points (1) through (3). 11 A Solution to the 3x + 1 Problem (1) A Common Misconception About the Nature of the 3x + 1 Function We will use an analogy to explain this misconception. Suppose there is a black box that contains a marble. The marble is either white or black. The Marble Conjecture states that the marble is white. It is clear that, in a proposed proof of the Marble Conjecture, any comparison of the case that the marble is white with the case that the marble is black would almost certainly be illegitimate (but in any case fruitless). Some readers imagine that the 3x + 1 function is like what we can call the “marble function”. That is, they imagine that either all odd, positive integers map to 1, or none of them do, and furthermore that at present we do not know which case is true. However, the 3x + 1 function is fundamentally different from the marble function. The reason is that, by “Lemma 3.0” on page 8, if an odd, positive integer maps to 1, then it does so regardless if counterexamples exist or not. It is an element of what we are calling the Fixed-Set (see “Definition of “Fixed-Set”” on page 8). Computer tests have shown that all odd, positive integers up to at least 1015 map to 1. These integers are elements of the Fixed-Set. In fact it is easy to show, using the 1-tree described in “Lemma 3.0” on page 8, and the fact, also easily shown, that a countable infinity of odd, positive integers map to each range element of the 3x + 1 function, hence that a countable infinity of odd, positive integers map to 1. These constitute all the elements of the Fixed-Set. The fact that a large number (indeed an infinity) of integers map to 1 regardless if counterexamples exist or not, makes the 3x + 1 function fundamentally different from the marble function (which has only one domain element (the marble) and one value (black or white)) . The marble function is a trivial example of a function that has no Fixed-Set, that is, a function such that no domain element has a fixed value, regardless if counterexamples exist or not. Our proofs of the 3x + 1 Conjecture in this paper cannot be applied to such a function. On the basis of our communications with readers, it seems clear that many readers imagine that the 3x + 1 function is a function without a Fixed-Set. Many of their objections to our proofs would make perfect sense if that were the case. But it is not. (2) A Common Misconception About “3x + 1-Like Function” Tests The 3x – 1 Test is the application of a proposed proof of the 3x + 1 Conjecture to the 3x – 1 function. If the proposed proof also proves the 3x – 1 Conjecture, then the proof may be faulty, because counterexamples to the 3x – 1 Conjecture are known (5 and 7 are two of them). We say “may be faulty” rather than “is faulty” because in order for the Test to be valid, it must be the case that all the lemmas supporting the 3x + 1 proof are also valid in the 3x – 1 case. There is an infinite class of what we have called “3x + 1-like functions” (they are defined in Appendix C of our paper, “Are We Near a Solution to the 3x + 1 Problem?” on occampress.com), and include the 3x – 1, 3x + 5 and 3x + 29 functions). Some readers have felt that a proof of the 3x + 1 Conjecture is not valid unless it can be shown not to apply to the 3x + 5 function as well as to the 3x – 1 function. Upon being convinced that the 3x + 1 proof passes the 3x + 5 Test, some of these readers have felt that the proof must pass the 3x + 29 Test as well (counterexamples to the 3x + 29 Conjecture are known), before the 3x + 1 proof can be considered valid. Since there is an infinite number of 3x + 1-like functions, and since at present there is no known property of all of them such that if a 3x + 1 proof passes the Test for one of them, it passes the test for all, this demand that a 3x + 1 proof pass successive 3x + 1-like function Tests, amounts to a declaration that the 3x + 1 Conjecture is undecidable. 12 A Solution to the 3x + 1 Problem In any case, a proof must stand or fall on its own. We feel that if a reader believes our proof has failed a Test, then he or she must show the error in our proof. In reply, some readers have gone so far as to claim that, even if all steps of a proof are correct, the proof as a whole can nevertheless be invalid. Our reply to this is that if the reader can get a paper published that proves the validity of that statement, then he or she will become world famous, because the statement contradicts one of the fundamental theorems of foundations of mathematics, namely, that if a proof is correct, then the correctness can be confirmed by machine (computer program). In fact, that fundamental theorem gives us another rebuttal to those who claim that our proof of the 3x + 1 Conjecture cannot be considered valid unless we can show that it does not also apply to the possible countable infinity of similar conjectures that contain counterexamples, namely, the conjectures associated with 3x + 1-like functions (and possibly others!). For no program at present can (1) determine all “similar” conjectures, and (2) for each one, determine if a counterexample exists, and then (3) verify that our proof does not also apply to a proof of the (false) conjecture. (Full details on 3x + 1-like functions, and our arguments against the demand for unlimited Tests, and against excessive reliance on even one or two of the Tests, are contained in the abovementioned Appendix C.) (3) Common Misconceptions About the Nature of Comparison of Mutually-Exclusive Cases We Do Not Claim That Existence of Non-Counterexamples Implies No Counterexamples! Despite the simplicity of “First Proof” and “Second Proof”, below, we have found that there are readers who believe that the proofs argue that because a very large number of odd, positive integers map to 1, therefore all odd, positive integers map to 1, or that somehow the distance functions (“Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6) are able to discriminate between counterexamples and non-counterexamples. These beliefs are false. Our proof is based on a comparison of two 2-level tuple-sets: one under the assumption that counterexamples do not exist, and the other (defined by the same exponent sequence as the first) under the assumption that counterexamples exist. An elementary inductive argument yields the fact that both tuplesets have exactly the same contents, which in turn implies that counterexamples do not exist. Comparison of Mutually-Exclusive Cases Is Made Frequently Inside of And Outside of Mathematics Some readers claim that the comparison implies that the two possibilities somehow exist simultaneously, which, of course, would be absurd. In fact, such comparisons are made every day, both inside of, and outside of, the mathematical culture. For example, “If the Yankees win the pennant this year, then ... but if they don’t, then ...”, or “If the next President of the U.S. is a Republican, then ... but if a Democrat, then ...”, or “If the abc-conjecture is true, then ... but if it is not, then ...”, or “If an odd, perfect number exists, then ... but if an odd, perfect number does not exist, then...” or, 13 A Solution to the 3x + 1 Problem “If a counterexample to the 3x + 1 Conjecture exists that results from an infinitely-repeating cycle of odd, positive integers, then there is a computer program that, in principle, will find the counterexample and halt. But if there is no such counterexample, then the program will run forever,” or, (Prior to the confirmation of the existence of the Higgs boson), “If the Higgs boson exists, then ... but if it does not exist, then ...” Another refutation of the claim that comparison implies simultaneous existence, especially when the claim is made in reference to “First Proof” and “Second Proof” on page 19, is the following: suppose an architect designs a skyscraper. His client looks at the plans, then suggests a change, though one that does not affect the basic structure of the building. The architect prepares a second set of plans, this set showing the change. He places both sets of plans side by side on a table so that the client can compare them. Surely something like this process takes place routinely in the field of architecture! We are confident that neither the architect nor the client ever says words to the effect, “Our comparing the two sets of plans unfortunately implies that the change both exists and does not exist, which of course is a contradiction, and therefore the comparison cannot be made.” (The unchanged drawings are analogous to the set of all tuple-sets if counterexamples do not exist ; the changed drawings are analogous to the set of all tuple-sets if counterexamples exist.) The analogy of the claim that two mutually-exclusive possibilities cannot be compared because only one of them actually exists, would be the claim that, when the architect’s client wanted to look at the drawings showing the changes, the architect would be required to remove from the room the drawings without the changes , and only then bring in the drawings with the changes. If the client later wanted to view the drawings without the changes, the architect would be required to remove from the room the drawings with the changes, then bring in the drawings with the changes. A Truth-Table Argument We now believe that the claim, “Comparison implies simultaneous existence”, is in fact a logical fallacy. Apart from the informal refutations of the claim given above, there is one that follows directly from a truth-table argument. Let p denote “Counterexamples to Conjecture X exist”. Now consider: (1) (p r) and (~p s) (p and ~p), where “” denotes “implies”, “~” denotes “not”, r is a true statement describing properties that exist if p is true, and s is a true statement describing properties that exist if ~p is true. The truth table for (1) yields (true false), which is a false implication. So it is false that the comparison of the two cases, p and ~p, implies that both exist simultaneously. 14 A Solution to the 3x + 1 Problem Another Purely Logical Argument Some readers feel that it is only legitimate to “consider” one case at a time, because to consider both implies both cases exist simultaneously. In other words, one must somehow blot out from one’s mind, all thought of the case not being considered (a task not greatly different from that of not thinking of a white bear all day), just as the architect’s client, in the above analogy, could require the architect to show only one set of drawings at a time. But these readers are wrong. The truth of the following two sentences confirms the validity of our comparison strategy. (1) If a mathematician writes, on a sheet of paper, “If p, then ...” , where p is a statement, and then below this, on the same sheet of paper, he writes “If not-p, then ...” he has not thereby written a contradiction, in particular, the contradiction “p and not-p ...”! (2) Furthermore, if in the first “...”, he then shows that the integer w has the property U, and in the second “...” he shows that the integer w has the property not-U, he has not thereby asserted that w has both the properties U and not-U. . However, we must hasten to add that, for our proofs of the 3x + 1 Conjecture, the existence of the large Fixed-Set (see “Definition of “Fixed-Set”” on page 8) is essential, and, in particular the large subset of the Fixed-Set that consists of all odd, positive integers 1015 + 1, these having all been determined by computer test, to be non-counterexamples. Our proofs most certainly are not based on the invalid argument that because this large subset exists, therefore all odd, positive integers are non-counterexamples. The large subset is just the point of departure for our proofs. Comparison of Mutually-Exclusive Cases Does Not Necessarily Involve Questions of Existence We must point out that comparison of two entities does not require that even one of them exists! Recall Kant's refutation of the ontological proof for the existence of God. That proof asserted that a perfect Being that does not exist is less perfect than a perfect Being that does exist, therefore God exists. Kant's reply was “Existence is not a predicate!” That is, existence is not a property. Thus, we can compare two unicorns in a painting or cartoon film (as to, say, size), or we can compare two characters in a novel, or two different sets of drawings for a proposed building (neither plan might represent a future building, or only one might, or both might, if separate buildings are built). In short, we can compare two things: both of which exist, or only one of which exists, or neither of which exists. On the Phrase, “Whether or Not Counterexamples Exist” Some readers question the validity of statements of the form, “Whether or not counterexamples exist, p,” where p is a statement. They argue (correctly) that such statements are equivalent to the two statements, “If counterexamples exist, then p” and “If counterexamples do not exist, then p”. They then argue (incorrectly) that, because the antecedent in one of these statements is false, and “false implies anything”, the statements, hence the original statement, “Whether or not counterexamples exist, then p”, are meaningless. This argument is incorrect because the two implications (in this paper) are cases of what has been called “informational implication”. For example, prior to the confirmation of the existence 15 A Solution to the 3x + 1 Problem of the Higgs boson, statements of the form, “Whether or not the Higgs boson exists, the law [name of accepted physical law} will continue to hold” must have been made frequently. This statement is equivalent to “If the Higgs boson exists, then the law ... will continue to hold; if the Higgs boson does not exist, then the law will continue to hold.” These implications provide information about the relationship between the existence of the Higgs boson and a certain law. It is highly unlikely that a physicist ever made the (illegitimate) reply “But the antecedent in one of the implications is false, and since false implies anything, the original statement is meaningless.” An informational implication has the property that the consequent (1) is true, and (2) provides information about the antecedent. Thus, “if counterexamples exist, then 2 + 2 = 4” is not an informational implication, because the consequent does not provide information about the antecedent. And, of course, the same distinction applies to statements of the form, “whether or not r, p”, where r, p are statements. If p does not provide information about r, then “whether or not r, p” is not informational. We can place all this on a rigorous logical basis. Recall that, as we stated above, “whether or not q, p” is the equivalent of (I) (if q then p) and (if not-q then p) In all the cases we are concerned with, p is true — p is a fact that provides information in a certain context, namely, the context of q being true or of q being false. And so, as the reader can easily verify by examining the truth-table for (I) when p is true, (I) is true. It is not “meaningless”. The phrase “whether or not” occurs in and outside of mathematics. For example, in mathematics: “Whether X is orientable or not, [a certain cap product between Hp(X; Z/2) and Hn–p(X; Z/ 2)] is an isomorphism1”. Outside of mathematics, for example in everyday life: “Whether or not it rains tomorrow, we will leave for San Diego.” [Professor to student]: “Whether or not you pass this course, you will not be able to graduate in June.” “Whether or not state taxes are increased, the extension of the stadium will be completed.” “Whether or not a Democrat is elected president in the 2016 election, the U.S. will continue to have a national debt.” Other readers have argued that, because “whether or not counterexamples exist, 2 + 2 = 4” is trivially true and therefore unimportant, all statements “whether or not counterexamples exist, p”, where p is any true statement, are trivially true and therefore unimportant. But once again, these readers are ignorant of the difference between trivial (true) statements and informational (true) statements. The statement, “whether or not counterexamples exist, each tuple-set contains an infinity of non-counterexample tuples”, is an informational (true) statement. It is by no means obvious, in the way that 2 + 2 = 4 is obvious, that each tuple-set should contain an infinity of noncounterexample tuples. It would be perfectly reasonable if a person just beginning his or her study of this paper, wondered if the existence of counterexamples might reduce the number of 1. Munkres, James R., Elements of Algebraic Topology, Addison-Wesley Publishing Company, Menlo Park, California, 1984, p. 394. Our word-processor does not have all the symbols used to represent the cap product in the actual text, hence the phrase in brackets. 16 A Solution to the 3x + 1 Problem non-counterexample tuples in at least one tuple-set to a finite number. Possible Explanation for Readers’ Difficulty With Comparison of These Cases Some readers nevertheless continue to believe that comparison of mutually-exclusive cases implies simultaneous existence of the cases. Through patient questioning, we have come to the conclusion that there are two reasons for this belief: (A) the readers’ belief that the 3x + 1 function is a function without a Fixed-Set (see “(1) A Common Misconception About the Nature of the 3x + 1 Function” on page 12), and (B) the readers’ imagining that there is a “realm” in which the cases are to be discussed or written about. This realm, they feel, only has room for one case at a time. So if we want to discuss or write statements about the case that counterexamples exist, then we must first remove from this realm the case that counerexamples do not exist. And if we want to discuss or write statements about the case that counterexamples do not exist, then we must remove from this realm, the case that counterexamples exist. To compare the two cases is to place both of them in the one realm at one time, and that results in contradictions. However, it is perfectly legitimate to imagine the realm as being big enough to hold the two cases simultaneously — “side-by-side”. There are then no contradictions in saying, for example, “assume x in the one case is a counterxample, and that x in the other case is a non-counterexample.” (The realm that is big enough to hold the two cases simultaneously is an example of the use of increased logical “space” to avoid contradictions. The source of this idea, and further details, will be found in “Appendix B — On Increased “Space” to Avoid Logical Contradictions” on page 38.) So we encourage the reader who is skeptical about the validity of the comparison strategy to get a piece of paper, draw a few lines descending from a point (the root of the tree representing the set of all tuple-sets) and below the top of the paper to write, “Set of All Tuple-Sets if Counterexamples Exist.) We then ask the reader to get a second piece of paper, and do the same, with the title at the top reading “Set of All Tuple-Sets if Counterexamples Do Not Exist.” We hope that it is clear that if the reader were to write, somewhere on the first sheet, “Let x be a counterexample,” and somewhere on the second sheet, “Let x be a non-counterexample”, there would be no contradiction! Other refutations of the claim that comparison implies simultaneous existence, are given in our short paper, “Is It Legitimate to Begin a Sentence With ‘If Counterexamples Exist, Then...’ ”, on occampress.com. However, we must emphasize that our proofs require, in addition to the validity of comparison of mutually-exclusive cases, the fact that all consecutive odd, positive integers from 1 to a large number map to 1 and do so regardless if counterexamples exist or not (these integers are a proper subset of the Fixed-Set (see “Definition of “Fixed-Set”” on page 8) ). For example 13 maps to 1 now, and will do so even if a counterexample to the Conjecture is discovered. With all these points clearly in mind, the reader can proceed to our proofs of the 3x + 1 Conjecture. We urge him or her to begin with “First Proof”, as it is by far the simplest. (It was discovered after the longer “Second Proof” was discovered.) If the reader believes that at least one of our proofs is correct, we encourage him or her to tell a mathematician or computer scientist, as we would like to have the proofs read by as many such qualified readers as possible before we submit the paper for publication. 17 A Solution to the 3x + 1 Problem First Proof 1. Assume a counterexample exists. 2. Let TA be any 2-level tuple-set. Then by “Lemma 3.0” on page 8 there exists a first 2-level tuple t in TA that is a counterexample tuple1. Let y be its second element. 3. The second element, x, of the preceding (necessarily non-counterexample) tuple, is given by x = y – 2 • 3 (“Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6). 4. But x + 2 • 3 is also the value of the second element of the next 2-tuple if t is not a counterexample tuple. Note that this argument would fail if Lemma 1.0 stated: “If, in an i-level tuple-set, where i 2, the (k + 1)st tuple is a counterexample tuple, and the kth tuple is a non-counterexample tuple, then the distance from the ith element of the kth tuple to the ith element of the (k + 1)st tuple is a, but if the (k + 1)st tuple is a non-counterexample tuple, kth tuple is also a non-counterexample tuple, then the distance from the ith element of the kth tuple to the last element of the (k + 1)st tuple is b,” where a b. But Lemma 1.0 does not say that. 5. We conclude that the set of 2-level tuples in TA is the same whether counterexamples exist or not. The same argument can be applied to any i-level tuple-set, i 2. 6. We conclude that the contents of the set of all tuple-sets is the same2 whether counterxamples exist or not. Therefore there are no counterexamples. For, assume a counterexample, hence a counterexample tuple, exists. But then its behavior is the same as that of a non-counterexample tuple, which is impossible. Remark The same argument can be applied to the set of all 35-level anchor tuples, which, by computer test, we know are all non-counerexample tuples. We observe that, since the distance functions in “Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6, are not sensitive to the existence or non-existecne of counterexamples, the second 35-level tuple in each 35-level tuple-set is exactly the same, whether or not counterexamples exist. (The first 35-level tuple is the anchor tuple.) And similarly for the third, fourth, fifth ... 35-level tuples. We conclude that the contents of the set of all tuple-sets in the same whether or not counterexamples exist or not. 1. See results of tests performed by Tomás Oliveira e Silva, www.ieeta.pt/~tos/3x+1/html. All consecutive odd, positive integers to at least 20 • 258 5.76 • 1018, which is greater than 3.33 • 1016 2 • 3(35 - 1) – 1, have been tested and found to be non-counterexamples.. 2. This means, of course, on a corresponding element of corresponding tuple basis. 18 A Solution to the 3x + 1 Problem Second Proof 1. (1) If counterexamples exist, then the set of all tuple-sets containing counterexamples are different from the set of all tuple-sets containing no counterexamples. (If counterexamples do not exist, then the set of all tuple-sets containing counterexamples is the same as the set of all tuple-sets containing no counterexamples.) Let A = {a2} be any 2-level exponent sequence. Let TA, nc denote the tuple-set defined by the exponent sequence A if counterexamples do not exist. Let TA, c denote the tuple-set defined by the exponent sequence A if if counterexamples exist. We imagine the two tuple-sets lined up side-by-side, with the kth tuple of TA, nc next to the kth tuple of TA, c. 1 2. Let S denote the set of consecutive odd, positive integers, beginning with 1, that are known, by computer test2, to map to 1. The elements of the set S map to 1 — that is, are noncounterexamples — whether or not counterexamples exist (see “Lemma 3.0” on page 8). Let tj be the 2-level tuple in TA, nc such that the second element of tj is the largest element in S that can be the second element of a 2-tuple in TA. In passing, we observe3 that j must be at least 333. Similarly, let tj´ be the 2-level tuple in TA, c such that the second element of tj´ is the largest element in S that can be the second element of a 2-tuple in TA. In passing, we observe that j´ must be at least 333. It is clear that all tuples in TA, nc up to and including tj are equal, respectively, to all tuples in TA, c, up to and including tj´. The tuples in each set are generated by elements of the Fixed-Set (see “Definition of “Fixed-Set”” on page 8), and hence remain the same regardless if a counterexample exists or not. 3. Let tj(2) denote the second element of tj. By part (a) of “Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6, we know that the second element of the next consecutive 2level tuple in TA, nc, that is, the element t(j+1)(2), is equal to tj(2) + d(2, 2) = tj(2) + 2 • 3(2 – 1) = tj(2) + 6. Since the definitions of the distance functions in Lemma 1.0 are independent of the existence of counterexamples, we also know that the second element of the next consecutive 2-level tuple in 1. We remind the reader that the set of all tuple-sets can be represented by an infinitary tree in which each node is a tuple-set. We can imagine each tuple-set as extending into the page. (See “Graphical Representation of the Set of All Tuple-sets” on page 6.) 2. See results of tests performed by Tomás Oliveira e Silva, www.ieeta.pt/~tos/3x+1/html. All consecutive odd, positive integers to at least 20 • 258 5.76 • 1018, which is greater than 3.33 • 1016 2 • 3(35 - 1) – 1, have been tested and found to be non-counterexamples.. 3. Since by part (a) of “Lemma 1.0: the “Distance” Functions d(i, i) and d(1, i)” on page 6, the distance between successive second elements of 2-level tuples in TA is 2 • 32 – 1 = 6, we see from the preceding footnote that j must be at least 333. 19 A Solution to the 3x + 1 Problem TA, c, that is, the element t(j+1)´(2), is equal to tj´(2) + d(2, 2) = tj´(2) + 2 • 3(2 – 1) = tj(2) + 6. But since tj = tj´, it follows that t(j+1) = t´(j+1). It is therefore clear that all tuples in TA, c up to and including t(j+1)´ are equal, respectively, to all tuples in TA, nc up to and including t(j+1). A similar argument applies for tuples t(j+2)´, t(j+3)´, ..., in TA, c and tuples t(j+2), t(j+3), ..., in TA, nc and so we conclude that all 2-level tuples in TA, c are equal, respectively, to all 2-level tuples in TA, nc . Note that this argument would fail if Lemma 1.0 stated: “If, in an i-level tuple-set, where i 2, the (k + 1)st tuple is a counterexample tuple, and the kth tuple is a non-counterexample tuple, then the distance from the ith element of the kth tuple to the ith element of the (k + 1)st tuple is a, but if the (k + 1)st tuple is a non-counterexample tuple, kth tuple is also a non-counterexample tuple, then the distance from the ith element of the kth tuple to the last element of the (k + 1)st tuple is b,” where a b. But Lemma 1.0 does not say that. Now the same is true for each two-level tuple-set TA. But each successive pair of elements, u, v, in each tuple in each tuple-set, regardless of the number of levels in the tuple-set, and regardless of the level at which u occurs, is a 2-level tuple in some 2-level tuple-set. So we conclude that the set of all tuples in all tuple-sets if counterexamples exist, is the same as the set of all tuples in all tuple-sets if counterexamples do not exist. But then, by the contrapositive of statement (1) in step 1, counterexamples do not exist. We now give two alternate proofs that the equality of the set of all tuple-sets1 if counterexamples exist and the set of all tuple-sets if counterexamples do not exist, implies that counterexamples do not exist. First alternate proof: Let A´ be any i-level exponent sequence, where i 2 . Let TA´, nc denote the tuple-set defined by the exponent sequence A´ if counterexamples do not exist. Let TA´, c denote the tuple-set defined by the exponent sequence A´ if counterexamples exist. By what we have established in step 3, the set of non-counterexample tuples in TA´, c is the same as the set of non-counterexample tuples in TA´, nc. But the set of first elements of all these non-counterexample tuples is the set of odd, positive integers. Therefore each counterexample tuple in TA´, c is also a non-counterexample tuple. But that is absurd, hence counterexample tuples, and therefore counterexamples, do not exist, and the Theorem is proved. Second alternate proof: The equality of the two sets of all tuple-sets implies there are two possibilities: (1) Each set contains counterexample tuples (the same such tuples in both cases), or (2) Neither set contains counterexample tuples. But (1) implies that some non-counterexample tuples can become, or are, also counterexample tuples. However, this is impossible, by “Lemma 3.0” on page 8, which says, 1. This means, of course, on a corresponding element of corresponding tuple basis. 20 A Solution to the 3x + 1 Problem in effect, “once a non-counterexample tuple, always a non-counterexample tuple — that is, regardless if counterexamples exist or not”. The corresponding statement for counterexample tuples is clearly false: “once a counterexample tuple, always a counterexample tuple — that is, regardless if counterexamples exist or not”. And so (2) must be true, hence counterexamples do not exist. Remarks (1) The above proof passes the 3x – 1 Test: it cannot also apply to the 3x – 1 function, as we will show in a moment. If it did, our argument would have a flaw, because counterexamples are known to exist in the 3x – 1 function. For example, 5 is a counterexample, since 5 is the second element of the infinite cycle < 7, 5, 7, ...>. The reason that “Second Proof” does not also apply to the 3x – 1 function is that the proof requires that in any 2-level tuple-set TA, at least the first 2-level tuple is a non-counterexample tuple. But in the 3x – 1 function, the first 2-level tuple in each 2-level tuple-set generated by an even exponent, is <7, 5>, and, as we showed in the previous paragraph, this is the start of a tuple that is an infinite cycle, hence a counterexample to the 3x – 1 Conjecture. (2) Both the first proof and the second proof in essence make the following argument: (a) Assume that a tuple-set that contains a counterexample is different, in at least one tuple, from a tuple-set generated by the same exponent sequence that does not contain a counterexample. (b) However, careful reasoning shows that both tuple-sets contain exactly the same tuples, contradicting our assumption. This contradiction proves the 3x + 1 Conjecture. Third Proof 1. By “Lemma 3.0” on page 8, we know that the 1-tree contains all and only the odd, positive integers that map to 1 — in other words, all and only the non-counterexamples. There is only one 1-tree. It is the same regardless if counterexamples exist or not. (Thus, for example, 13 maps to 1 regardless if counterexamples exist or not; 13 is an element of the 1-tree. See concluding paragraphs of section “Lemma 3.0” on page 8.) 2. Orient the 1-tree vertically, so that the root, 1, is on top, and the branches descend below it. Let S denote the set of consecutive odd, positive integers, beginning with 1, that are known, by computer test1, to map to 1. (See results of tests performed by Tomás Oliveira e Silva, www.ieeta.pt/~tos/3x+1/html. All odd, positive integers to at least 20 • 258 » 5.76 • 1018 which is greater than 3.33 • 1016 » 2 • 3(35 - 1) – 1 have been tested and found to be non-counterexamples.) We observe in passing that the set {1, 3, 5, ..., 2 • 3(35 1) – 1} is a subset of S. 1. See results of tests performed by Tomás Oliveira e Silva, www.ieeta.pt/~tos/3x+1/html. All odd, positive integers to at least 20 • 258 5.76 • 1018 which is greater than 3.33 • 1016 2 • 3(35 1) – 1 have been tested and found to be non-counterexamples. 21 A Solution to the 3x + 1 Problem Place an “X” next to each node y in the 1-tree that is associated with an element of S. In addition, place an “X” next to each node that is in the same “spiral” as y. Do not place an “X” next to any node y that is a descendant of a node in such a “spiral” unless y is an element of S. The set of nodes whose immediate descendants are not marked “X” we call the 1st non-counterexample extension subset. The elements of the 1st non-counterexample extension subset are what they would be if no counterexamples existed. (The set of odd, positive integers that map to a given y in one iteration of the 3x + 1 function is the same regardless if counterexamples exist or not. (The definition of the 3x + 1 function is independent of the existence of counterexamples.)) 3. Consider any node y marked “X” such that the node is associated with a range element and such that immediately below it no node y is marked “X”. But clearly, the odd, positive integers immediately below y are what they would be if no counterexamples existed, since the set of odd, positive integers that map to a given y in one iteration of the 3x + 1 function is the same regardless if counterexamples exist or not. (The definition of the 3x + 1 function is independent of the existence of counterexamples.) We conclude that all immediate descendants of nodes marked “X” are what they would be if no counterexamples existed. We mark these immediate descendants “X”. The new set of all nodes marked “X” we call the 2nd non-counterexample exxtension subset. 4. We can continue as in step 3 without limit. We conclude that the 1-tree is what it would be if no counterexamples existed. Or, in other words, that no counterexamples exist, and the 3x + 1 Conjecture is proved. Remark “Remark” following “Second Proof” also applies to “Third Proof”. .. Remark On All of the Above Proofs Our proofs make use of the fact that a large number of successive odd, positive integers, beginning with 1 and extending to at least 2 • 3(35 1) , are known (by computer test) to be noncounterexamples. These integers are elements of the Fixed-Set (see “Definition of “Fixed-Set”” on page 8) and are the first elements of the 2-tuples in two of our proofs. We believe the existence of this large set of consecutive non-counterexamples is of fundamental importance, and we consider our recognition of its importance to be one of the most important results of our research. At the very least, the fact distinguishes the 3x + 1 function from the 3x – 1 function, for the reason explained in “Remark” following “Second Proof”. But we believe that no proof of the 3x + 1 Conjecture that uses tuple-sets and recursive “spiral”s, is possible if the proof does not make use of this fact, and we are almost prepared to say that no proof of the Conjecture is possible, regardless of the machinery employed, if it does not make use of the fact, directly or indirectly. Researchers must also keep in mind that, no matter how many properties they determine in the equivalent of a very large number of very large non-counterexample tuples — say, all non- 22 A Solution to the 3x + 1 Problem counterexample tuples of length up to 1010 — counterexample tuples of the same length would have the same properties, by “Lemma 2.0” on page 7, unless one or more of the counterexample tuples contained a cycle. 23 A Solution to the 3x + 1 Problem References Lagarias, J., (1985), “The 3x + 1 Problem and Its Generalizations”, American Mathematical Monthly, 93, 3-23. Wirsching, Günther J.. The Dynamical System Generated by the 3n + 1 Function, SpringerVerlag, Berlin, Germany, 1998. 24 A Solution to the 3x + 1 Problem Appendix A — Statement and Proof of Each Lemma Lemma 1.0: Statement and Proof Definition: let TA be an i-level tuple-set, where i 2. Let t(r), t(s) denote tuples consecutive at level i, with r < s in the natural ordering of tuples by first elements. Let t(r)(h), t(s)(h) denote the elements of t(r), t(s) at level h, where 1 h i. Then we call |t(s)(h) - t(r)(h)| the distance between t(r) and t(s) at level h. We denote this distance by d(h, i) and call d the distance functions (one function for each h). Lemma 1.0 (a) Let A = {a2, a3, ..., ai}, where i 2, be a sequence of exponents, and let t(r), t(s) be tuples consecutive at level i in TA. Then d(i, i) is given by: d i i = 2 3 i – 1 (b) Let t(r), t(s) be tuples consecutive at level i in TA. Then d(1, i) is given by: d 1 i = 2 2 a 2 2 a 3 2 ai Thus, in “Fig. 1. Part of the tuple-set TA associated with the sequence A = {1, 1, 2}” on page 6, the distance d(3, 3) between t8(3) = 35 and t4(3) = 17 is 2 · 3(3-1) = 18. The distance d(1, 2) between t12(1) = 23 and t10(1) = 19 is 2 · 21 = 4. Proof: The proof is by induction. Proof of Basis Step for Parts (a) and (b) of Lemma 1.0: Let t(r) and t(s) be the first and second 2-level tuples, in the standard linear ordering of tuples based on their first elements, that are consecutive at level i = 2 in the 2-level tuple-set TA, where A = {a2}. (See Fig. 2 (1).) 25 A Solution to the 3x + 1 Problem level tuple tr 4 3 tuple ts 2 t(r)(2) d(2, 2) = 2 • 1 t(r)(1) t(s)(2) d (1, 2) = 2 •2 a2 t(s)(1) Fig. 2 (1). Illustration for proof of Basis Step of Lemma 1.0. Then we have: 3t r 1 + 1 -------------------------- = t r 2 2 a2 (1.1) and since, by definition of d(1, 2), t s 1 = t r 1 + d(1 2) we have: 3 t r 1 + d(1 2) + 1 ----------------------------------------------------- = t s 2 2 a2 Therefore, since, by definition of d(i, i), t r 2 + d(2 2) = t s 2 26 (1.2) A Solution to the 3x + 1 Problem we can write, from (1.1) and (1.2): 3t r 1 + 1 3 t r 1 + d(1 2) + 1 -------------------------- + d(2 2) = ---------------------------------------------------2 a2 2 a2 By elementary algebra, this yields: 2 a 2 d(2 2) = 3 d(1 2) Now d(2, 2) must be even, since it is the difference of two odd, positive integers, and furthermore, by definition of tuples consecutive at level i, it must be the smallest such even number, whence it follows that d(2, 2) must = 3 • 2, and necessarily d 1 2 = 2 2 a2 A similar argument establishes that d(2, 2) and d(1,2) have the above values for every other pair of tuples consecutive at level 2. Thus we have our proof of the Basis Step for parts (a) and (b) of Lemma 1.0. Proof of Induction Step for Parts (a) and (b) of Lemma 1.0 Assume the Lemma is true for all levels j, 2 j i and that TA is an i-level tuple-set, where A = {a2, a3, ..., ai}. Let t(r) and t(s) be tuples consecutive at level i, and let t(r) and t(f) be tuples consecutive at level i +1. (See Fig. 2 (2).) 27 A Solution to the 3x + 1 Problem level t f i + 1 = t r i + 1 + d(i + 1 i + 1) t(r)(i + 1) d(i+1,i+1) = 2•3i i+1 i t(r)(i) t f i = t r i + g 2 3 i – 1 d(i, i)=2•3i-1 tuple ts tuple tr tuple tf 3 2 1 d(1, i) = 2 2 a2 2 a 3 2 a i Fig. 2 (2). Illustration for proof of Induction Step of Lemma 1.0. Then we have: 3t r i + 1 ------------------------- = t r i + 1 2 ai + 1 and since, by definition of d(i, i), t f i = t r i + g d(i i) for some g 1, we have: 3 t r i + g d(i i) + 1 --------------------------------------------------------- = t f i + 1 2 ai + 1 28 A Solution to the 3x + 1 Problem Thus, since t r i + 1 + d(i + 1 i + 1) = t f i + 1 we can write: 3 t t r i + gd(i i) + 1 3t t r i + 1 ----------------------- + d(i + 1 i + 1) = -------------------------------------------------2 ai + 1 2 ai + 1 This yields, by elementary algebra: 2 a i + 1 d(i + 1 i + 1) = 3 gd(i i) As in the proof of the Basis Step, d(i+1, i+1) must be even, since it is the difference of two odd, positive integers, and furthermore, by definition of tuples consecutive at level i+1, it must be the smallest such even number. Thus d(i+1, i+1) = 3 • d(i, i), and g d i i = 2 Hence g = 2 ai + 1 d i i . ai + 1 Now g is the number of tuples consecutive at level i that must be “traversed” to get from t(r) to t(f). By inductive hypothesis, d(1, i) for each pair of these tuples is: a a d 1 i = 2 2 2 2 3 2 ai hence, since g = 2 ai + 1 we have a d 1 i + 1 = d 1 i 2 i + 1 . A similar argument establishes that d(i+1, i+1) and d(1, i+1) have the above values for every pair of tuples consecutive at level i+1. Thus we have our proof of the Induction Step for parts (a) and (b) of Lemma 1.0. The proof of Lemma 1.0 is completed. 29 A Solution to the 3x + 1 Problem Lemma 2.0: Statement and Proof Assume a counterexample exists. Then for all i 2, each i-level tuple-set contains an infinity of i-level counterexample tuples and an infinity of i-level non-counterexample tuples. Proof: 1. Assume counterexamples exist. Then: There is a countable infinity of non-counterexample range elements. Proof: Each non-counterexample maps to a range element, by definition of range element. Each range element is mapped to by an infinity of elements ( “Lemma 6.0: Statement and Proof” on page 32). A countable infinity of these are range elements (proof of “Lemma 7.0: Statement and Proof” on page 35). There is a countable infinity of counterexample range elements. Proof: same as for non-counterexample case. 2. For each finite exponent sequence A, and for each range element y, non-counterexample or counterexample, there is an x that maps to y via A possibly followed by a buffer exponent (“Lemma 7.0: Statement and Proof” on page 35). The presence of the buffer exponent does not change the fact that x is the first element of a tuple associated with the exponent A. Lemma 3.0: Statement and Proof Exactly one set J of odd, positive integers maps to 1, regardless if counterexamples exist or not. 1 Proof: . The set J = {odd, positive integers y | y maps to 1 in one iteration of the 3x + 1 function} {odd, positive integers y | y maps to 1 in two iterations of the 3x + 1 function} {odd, positive integers y | y maps to 1 in three iterations of the 3x + 1 function} ... If an odd, positive integer y maps to 1, then it maps to 1 regardless if counterexamples exist or not. For, certainly y will continue to map to 1 if counterexamples do not exist. If counterexamples exist, and y does not continue to map to 1, that implies that the proof that counterexamples 1. Some readers consider the phrase “regardless if counterexamples exist or not” as unnecessary. The reason we include it is that when it was not present, other readers assumed that the meaning of the Lemma was: exactly one set J of odd, positive integers maps to 1 (if counterexamples do not exist), and exactly one (different) set J of odd, positive integers maps to 1 if counterexamples exist. This meaning is incorrect. A second reason for including the phrase will become clear when the reader reads our proofs of the 3x + 1 Conjecture. 30 A Solution to the 3x + 1 Problem exist somehow changes the definition of the 3x + 1 function or the laws of arithmetic. But such changes are absurd. Thus the Lemma is true. Lemma 4.0: Statement and Proof No multiple of 3 is a range element. Proof : If 3x + 1-------------= 3m 2a then 1 0 mod 3, which is false. Lemma 5.0: Statement and Proof Each odd, positive integer (except a multiple of 3) is mapped to by a multiple of 3 in one iteration of the 3x + 1 function. Proof: Since the domain of the 3x + 1 function is the odd, positive integers, the only relevant generators are 3(2k + 1), k . We show that, for each odd, positive integer y not a multiple of 3, there exists a k and an a such that 3 3 2k + 1 + 1 - , y = --------------------------------------------a 2 (11.1) where a is necessarily the largest such a, since y is assumed odd. Rewriting (11.1), we have: y2 a – 1 – 5 = 9k . (11.2) Without loss of generality, we can let y r mod 18, where r is one of 1, 5, 7, 11, 13, or 17 (since y is odd and not a multiple of 3, these values of r cover all possibilities mod 18). Or, in other words, for some q, r, y = 18q + r . Then, from (11.2) we can write: 18 2 a – 1 q + 2 a – 1 r – 5 = 9k . (11.3) Since the first term on the left-hand side is a multiple of 9, (2a - 1)r – 5 must also be if the equation is to hold. We can thus construct the following table. (Certain larger a also serve equally well, but those given suffice for purposes of this proof.) 31 A Solution to the 3x + 1 Problem Table 1: Values of r, a, for Proof of Lemma 2 a – 1 r – 5 r a 1 6 27 5 1 0 7 2 9 11 5 171 1 3 4 99 1 7 3 63 Given q and r (hence y), we can use r to look up a in the table, and then solve (11.3) for integral k, thus producing the multiple of 3 that maps to y in one iteration of the 3x + 1 function. Lemma 6.0: Statement and Proof (a) Each range element y is mapped to, in one iteration of the 3x + 1 function, by every exponent of one parity only. Furthermore, (b) For each of the two parities, there exists a range element that is mapped to by every exponent of that parity. Proof of part (a): Steps 1 and 2 are slightly edited versions of proofs by Jonathan Kilgallin and Alex Godofsky. Any errors are entirely ours. Step 3 is a slightly edited version of a proof by Michael Klipper. Any errors are entirely ours. 1. We first show that if y is mapped to by the exponent a, then y is mapped to by every exponent greater than a that is of the same parity as a. Let y be a range element, and let x map to y via the exponent a. Then 3x + 1y = -------------a 2 We wish to show that there exists an x´ such that x´ maps to y via the exponent 2a + 2. That is, we wish to show that there exists an x´ such that 32 A Solution to the 3x + 1 Problem 3x + 1 y = ---------------a+2 2 Rewriting, this gives a+2 y–1 2 x = -----------------------3 Substituting for y yields + 1- ------------- a –1 2 x = ------------------------------------------3 2 a + 2 3x Simplifying, this gives x´ = 4x + 1. Since x is an odd, positive integer, clearly x´ is as well. Thus, by induction, if y is mapped to via the exponent a , it is mapped to by every exponent greater than a of the same parity. 2. Next we show that if y is mapped to by the exponent a which is greater than 2, then it is mapped to by every exponent less than a that is of the same parity as a. Let y be a range element, and let x map to y via the exponent a where a > 2. Then 3x + 1y = -------------a 2 We wish to show that there exists an x´ such that x´ maps to y via the exponent 2 a – 2. That is, we wish to show that there exists an x´ such that 3x + 1y = ---------------a–2 2 Rewriting, this gives 33 A Solution to the 3x + 1 Problem a–2 2 y–1 x = -----------------------3 Supstituting for y yields + 1- -------------–1 a 2 x = -----------------------------------------3 2 a – 2 3x Simplifying yields x–1 x = ----------4 3. We must now show that x´ = (x – 1)/4 is an odd, positive integer. This means we must show that (x – 1) = 4(2k + 1) for some k 0, or that (x – 1) = 8k + 4, hence that x = 8k + 5. Thus, we must prove x 5 mod 8. We know that x maps to y via a, where a 3. Thus, y = (3x + 1)/2a, so 2ay = 3x + 1. Because a 3, 2ay is a multiple of 8. Thus, (3x + 1) 0 mod 8, and 3x 7 mod 8. This readily implies x 5 mod 8. 4. Thus, by induction, if y is mapped to via the exponent a, where a > 2, then it is mapped to by every exponent less than a of the same parity. Proof of part (b): We now show that for each of the two parities there exists a range element that is mapped to by every exponent of that parity. 1. Fix a range element y, and suppose that x maps to y via the exponent a. Now a is either even or odd, hence a = 2n + h, where h is either 0 or 1. Since y = (3x + 1)/2a, it follows that (2a)y = 3x+1. Reduce the equation mod 3, and we get (2h)y 1 mod 3, by the following reasoning: (2a)y 1 mod 3 implies (22n + h)y 1 mod 3 implies 22n 2hy 1 mod 3 implies 2hy 1 (mod 3) because 22n = 4n 1 mod 3. 2. Since y is fixed, either y 1 or y 2 mod 3. (We know that y, a range element, is not a multiple of 3 by “Lemma 4.0: Statement and Proof” on page 31). If y 1 mod 3, then we have 2h(1) 1 mod 3, which implies that h must be 0. If y 2 mod 3, then we have (2h)(2) 1 mod 3, implying that h must be 1. 34 A Solution to the 3x + 1 Problem Lemma 7.0: Statement and Proof Let y be a range element of the 3x + 1 function. Then for each finite exponent sequence A, there exists an x that maps to y via A possibly followed by a “buffer” exponent. (For example, if y is mapped to by even exponents, and our exponent sequence A ends with an odd exponent, then there must be a “buffer” exponent following A, and similarly if y is mapped to by odd exponents and A ends with an even exponent. However, there are other cases in which a “buffer” exponent is required.) Proof: 1. Each range element y is mapped to by all exponents of one parity (“Lemma 6.0: Statement and Proof” on page 32). 2. Each range element y is mapped to by a multiple of 3 (“Lemma 5.0: Statement and Proof” on page 31). Each range element is mapped to by an infinity of range elements (“Lemma 5.0: Statement and Proof” on page 31). 3. Let y be a range element and let S = {s1, s2, s3, ... } be the set of all odd, positive integers that map to y in one iteration of the 3x + 1 function. In other words, S is the set of all elements in a “spiral”. Furthermore, let the si be in increasing order of magnitude. It is easily shown that si+1 = 4si + 1. (In Fig. 18, y = 13, S = {17, 69, 277, 1109, ... } 13 22 17 21 11 24 26 277 69 28 1109 22 21 369 739 Fig. 18 35 ... A Solution to the 3x + 1 Problem 4. If si is a multiple of 3, then 4si +1 is mapped to, in one iteration of the 3x + 1 function, by all exponents of even parity. To prove this, we need only show that x is an integer in the equation 3x + 14 3u + 1 = -------------2 2 Multiplying through by 22 and collecting terms we get 48u + 4 = 3x + 1 and clearly x is an integer. 5. If sj is mapped to by all even exponents, then 4sj + 1 is mapped to, in one iteration of the 3x + 1 function, by all exponents of odd parity. (The proof is by an algebraic argument similar to that in step 4.) 6. If sk is mapped to by all odd exponents, then 4sk + 1 is a multiple of 3. (The proof is by an algebraic argument similar to that in step 4.) 7. The Lemma follows by an inductive argument that we now describe. Let y be a range element. It is mapped to by all exponents of one parity. Thus it is mapped to by an infinite sequence of odd, positive integers. As a consequence of steps 1 through 6, we can represent an infinite sub-sequence of the sequence by ...3, 2, 1, 3, 2, 1, ... where “3” means “this odd, positive integer is a multiple of 3 and therefore is not mapped to by any odd, positive integer”; “2” means “this odd, positive integer is mapped to by all even exponents”; “1” means “this odd, positive integer is mapped to by all odd exponents”. 36 A Solution to the 3x + 1 Problem Each type “2” and type “1” odd, positive integer is mapped to by all exponents of one parity. Thus it is mapped to by an infinite sequence of odd, positive integers. We can represent an infinite sub-sequence of the sequence by ...3, 2, 1, 3, 2, 1, ... where each integer has the same meaning as above. Temporarily ignoring the case in which a buffer exponent is needed, it should now be clear that, for each range element y, and for each finite sequence of exponents B, we can find a finite path down through the infinitary tree we have just established, starting at the root y. The path will end in an odd, positive integer x. Let A denote the path B taken in reverse order. Then we have our result for the non-buffer-exponent case. The buffer-exponent case follows from the fact that the buffer exponent is one among an infinity of exponents of one parity. Thus y is mapped to by an infinite sequence of odd, positive integers. We then simply apply the above argument.. 37 A Solution to the 3x + 1 Problem Appendix B — On Increased “Space” to Avoid Logical Contradictions Russell's analogy to the set theory paradox he called attention to, is a town in which the barber shaves every man who doesn’t shave himself. The question is, Does the barber shave himself? The answer is, if he does, he doesn't and if he doesn't, he does. A resolution of this paradox is to define two identical towns, each with a barber who follows the same rule, except that if the barber in town 1 does not shave himself, the barber in town 2 shaves him. And if the barber in town 1 shaves himself, the barber in town 2 does not shave him. And similarly for the barber in town 2. We have used extra logical “space” — namely, the duplicate second town — to resolve the paradox. Or consider the coin that has written on each side, “The statement on the other side of this coin is false.” Thus the statement on each side of the coin is both true and false. A resolution of this paradox is to define levels for coins. The coins at level 0 can contain any sentences or phrases on either side except for sentences or phrases referring to sentences or phrases on coins at level 0. The coins at level 1 contain only phrases and sentences that refer to phrases and sentences on coins at level 0. In general, the coins at level n contain only phrases and sentences that refer to phrases and sentences at level n – 1 and lower levels. Thus, for example, if side 1 of coin 1289 at level 0 contains the statement "2 + 2 = 5", it is not only legitimate for a side of a coin at level 1 to contain the statement, "The statement on side 1 of coin 1289 at level 0 is false", it is also legitimate for a coin at level 1 to contain the statement, "The statement on side 1 of coin 1289 at level 0 is true". Of course, the latter statement is false, but that does not lead to a paradox. The extra logical “space” here is level 1 and higher levels. The reader will probably recognize that these levels are based on the core concept of Russell's Theory of Types , which, in a later implementation, stipulated that at level 0 only statements about numbers are allowed; at level 1, only statements about statements at level 0 are allowed; at level 2, only statements about statements at level 1 or level 0 are allowed, etc. So whereas it certainly leads to contradictions if we try to imagine the set of all tuple-sets simultaneously containing, and not containing, counterexamples, it does not lead to contradictions if we postulate two separate sets of all tuple-sets, one if counterexamples exist, the other if counterexamples do not exist, and then compare the two. Of course, the set of all non-counterexamples will be the same in both cases (“Lemma 3.0” on page 8). For further thoughts on the use of additional logical “space” to resolve paradoxes, see the section “Paradoxes” in the paper, “Notes on Self-Representing, and Other, Information Structures”, on occampress.com. 38 A Solution to the 3x + 1 Problem We emphasize again that questions of existence are irrelevant to comparisons. We can compare two possibilities for a mythical beast: it has three horns, or it has none. Our comparison will in no way be illegitimate because the beast does not exist. Our comparison will in no way imply that the beast simultaneously has no horns and three horns. 39 A Solution to the 3x + 1 Problem Appendix C — Criticisms of Our Proofs of the 3x + 1 Conjecture, and Our Responses We have so far received criticisms of our proofs of the 3x + 1 Conjecture from eight readers. (In 2014 this paper received close to 3,000 visits.) In this Appendix, we will describe these criticisms, and give our responses to them. Criticisms We Have Dismissed Outright Two readers wrote, regarding our four proofs of the Conjecture, “It won’t work,” providing no indication of what “It” referred to, despite our request that we be told the sentences that contain purported errors. So we feel justified in dismissing these criticisms. Another reader did quote sentences that he claimed contained errors. However, the sentences seemed strange to us. When we did a string search on the entire paper, none of the sentences was found. So we feel justified in dismissing these criticisms as well. Criticism: That Sentences of the Form, “Whether or Not p, q” are Meaningless or Ambiguous Our response to this criticism is contained in the section, “On the Phrase, “Whether or Not Counterexamples Exist”” on page 15. Criticism: That We Argue That Because No Counterexamples Have Been Found, Therefore There Are No Counterexamples. Our response to this cticism is contained in the section, “We Do Not Claim That Existence of Non-Counterexamples Implies No Counterexamples!” on page 13 Criticism: That Mutually-Exclusive Cases Cannot Be Compared Our response to this criticism is contained in the section “(3) Common Misconceptions About the Nature of Comparison of Mutually-Exclusive Cases” on page 13. Criticism: That We Prove There Are No Counterexamples to the 3x – 1 Conjecture, When In Fact There Are This has probably been the most frequent criticism we have received over the years. We suspect that one reason is that it does not require the reader to spend much time and effort trying to understand our paper, and, in particular, our proofs of the Conjecture. The reader simply issues the claim and leaves it to us to prove that it is false, the reader reserving the right to disagree with our proof of falsity despite the reader’s only superficial understanding of our paper. We have come to call the criticism, the “3x – 1 Test”. The 3x – 1 function is the same as the 3x + 1 function, except for the minus sign preceding the 1. In fact, the 3x – 1 function is the negative of the 3x + 1 function over the odd, negative integers. Thus, for example, (3(13) – 1)/2 = 19 = –(3(–13) + 1)/2. Counterexamples to the 3x – 1 Conjecture occur early. The smallest ones are 5 and 7. This 40 A Solution to the 3x + 1 Problem fact allows “Most Recent Proof of the Conjecture” on page 10 to easily pass the 3x – 1 Test — step 0 of the proof simply does not apply to the 3x – 1 function. The same fact allows “First Proof”, “Second Proof” and “Third Proof” to pass the 3x – 1 Test, because each of these requires at least one 2-level non-counterexample tuple in any 2-level tupleset to precede the first 2-level counterexample tuple in that tuple-set. But this requirement cannot be met by the 3x – 1 function, because the first 2-level tuple in the 3x – 1 tuple-set TA, where A = {4, is already a counterexample tuple, namely, <5, 7>. Another response to the 3x – 1 Test is that it implies that a proof P that no counterexamples to a conjecture exist, must be accompanied by a proof that P does not prove the non-existence of counterexamples in “related” conjectures known to be false. Clearly, this implication effectively negates a fundamental theorem of Foundations of Mathematics, namely, the theorem that states that if a proof is correct, then the correctness can be verified by machine (computer program)1. For, if the implication holds, then the verifying program must somehow know all “related” conjectures, and must be able to ascertain which ones are false, and then, for each of these, determine that P does not prove one of these false conjectures. The reader may reply that it is up to us to specify all the related conjectures. Now, there appears to be a countable infinity of what we might reasonably call “3x + 1-like” functions2 However, we do not know (a) if our functions are the only ones that the mathematics community would believe are related to the 3x + 1 function; (b) if not, what the mathematics community regards the other such functions to be, and (c) which of the corresponding conjectures are false. Furthermore, the implication requires that all proofs Q that counterexamples to a conjecture do not exist, must be accompanied by proofs that Q does not prove “related” conjectures known to be false. 1. The fundamental theorem is true because each mathematical subject can be represented by a Type 0 formal grammar. The theorem to be tested is a purported string in the language generated by that grammar. However, membership in a Type 0 language is only semi-decidable: If a string is in the language, then there is a program that will ascertain that fact (halt) in a finite amount of time (test of a finite number of strings). But if a string is not in the language, then the program may loop forever, that is, never halt. 2. See our paper, “Are We Near a Solution to the 3x + 1 Problem” on occampress.com. 41

© Copyright 2018