Looping and Divergence in the Collatz Conjecture

Authors: Jai Sharma, Akshat Jha, Sambhabi Bose, Garrett Heller, Dr. Nick Castro

Peer Reviewer: Siri Dasari

Professional Reviewer: Dr. Nick Castro

Abstract

In this paper, we investigate the possible scenarios in which a number does not satisfy the Collatz Conjecture. Specifically, we examine numbers which may have a looping Collatz reduction sequence as well as numbers which may lead to a diverging Collatz reduction sequence. In order to investigate these, we look at the parity of the numbers in a general Collatz reduction sequence. Further, we examine cases in which these parity cycles repeat themselves infinitely in the reduction sequence. Through the research conducted in the paper, we formulate a necessary condition for looping in the Collatz Conjecture. We also prove that if a number has a diverging reduction sequence, then it must generate an infinite non-repeating parity cycle.

Introduction to the Collatz Conjecture

In this paper, we will discuss the ideas of looping and divergence in the Collatz Conjecture. As background, the following is the Collatz Conjecture problem statement:

Conjecture (The Collatz Conjecture) Define a piecewise function f over the domain of positive integers as the following:

The Collatz Conjecture states that, for all x, f ⁿ (x) = 1 for some non-negative integer n, where f ⁱ (x) represents the Collatz Conjecture function being applied to x exactly i times.

Summary of Findings

Consider applying the Collatz Conjecture function repeatedly to number m:

Definition (Collatz Reduction Sequence)
Let f(x) be the result of the Collatz Conjecture function on the positive integer x. 

If the number m satisfies the Collatz Conjecture, then the Collatz Reduction Sequence is the following:

m, f(m), f ² (m), f ³ (m), …, 1.

If the number m does not satisfy the Collatz Conjecture, then the Collatz Reduction Sequence is the following:

m, f(m), f ² (m), f ³ (m), …, f ^a (m)

for arbitrarily large a. 

Suppose that the number m does not satisfy the Collatz Conjecture. Then, there are two ways this can occur:

1. f ⁱ (m) = f ^j (m) for some positive integers i and j such that j < i. We call this Looping. Looping has two cases: 

• Case 1: f ⁱ (m) is equal to m for some positive integer i. We call this Direct Looping. 
• Case 2: f ^k (m) is not equal to m for any positive integer k. We call this Indirect Looping. In this case, there exists some positive integer j such that f ^j (m) = m leads to Direct Looping in its Collatz Reduction Sequence. Here, we only focus on numbers that lead to Direct Looping; if we find the positive odd integers m that lead to Direct Looping, then we can compute all of the numbers that lead to Indirect Looping as f ^-1 (m), f ^-2 (m), f ^-3 (m) etc. for all m (where f ^-1(m) is the inverse of m under the function f). Therefore, any restrictions we put on Direct Looping also apply for Indirect Looping. Henceforth, all references to “Looping” will be references to Direct Looping.

2. f ⁱ (m) increases without bound as i increases to ? and  f ⁱ (m) is not equal to 1 for any positive integer i. We call this Divergence.

We address both of these cases separately after a critical definition:

Definition (Parity Sequence) A Parity Sequence is the sequence formed by the parities of the elements of the Collatz Reduction Sequence for a number. 

For example, take the number 3. The following is the Collatz Reduction Sequence for 3:

3, 10, 5, 16, 8, 4, 2, 1.

Then, the corresponding Parity Sequence is the following:

1 odd, 1 even, 1 odd, 1 even, 1 even, 1 even, 1 even, 1 odd.

or more concisely:

1 odd, 1 even, 1 odd, 4 evens, 1 odd.

Suppose that for some number m, the Collatz Reduction Sequence, and therefore the Parity Sequence, is infinite in length and periodic with some finite period. Call one period of the infinitely long Parity Sequence of m a Parity Cycle. 

In the case of Looping, the Parity Sequence must be infinite and periodic, as the elements in the Collatz Reduction Sequence themselves repeat; therefore, an infinitely repeating Parity Cycle of finite length must exist. Additionally, in the case of Divergence, the Parity Sequence must be infinite, and there is a chance that this infinite Parity Sequence is periodic; therefore, an infinitely repeating Parity Cycle of finite length can exist in this case as well. 

In this paper, we focus on these infinitely repeating Parity Cycles of finite length that occur in the said cases. Specifically, we use the idea of these Parity Cycles to set restrictions on numbers which can lead to Looping or Divergence in the Collatz Conjecture.

Note that the only case not covered here by the concept of Parity Cycles which can still result in a number not satisfying the Collatz Conjecture is when the number generates an infinite aperiodic Parity Sequence through its Collatz Reduction Sequence, which can only happen in the case of Divergence. 

Consider an odd positive integer m which generates an infinitely repeating Parity Cycle of finite length through its Collatz Reduction Sequence. Let the following be the general Parity Cycle of m:

1 odd, p₁ evens, 1 odd, p₂ evens, 1 odd, p₃ evens, … , 1 odd, p_b evens

Notice that we start with an odd number and end with an odd number after the final series of even numbers. This Parity Cycle can then be thought of as a function that takes in an odd integer, performs the Collatz Conjecture function according to the Parity Cycle, and outputs an odd integer which is also in the domain of the same function (meaning that we can put the resulting number into the Parity Cycle again by definition). For future reference, let this Parity Cycle function be g(x), where x = m in the above example. 

From this parity cycle, we define the following:

We can then establish our findings on Looping in the Collatz Conjecture:

Theorem (Looping in the Collatz Conjecture) An odd integer m generates a Looping Collatz Reduction Sequence if and only if it is of the form:

where r, q, and s are defined by the Parity Cycle of m and 2 ^s > r.

We can also establish our findings on Divergence in the Collatz Conjecture:

Theorem (Divergence in the Collatz Conjecture) An odd integer m generates an infinite Diverging Collatz Reduction Sequence only if the infinitely long Parity Sequence corresponding to this Collatz Reduction Sequence is aperiodic.

Proof of Findings

Note that all of the definitions used in this proof (that have not been defined here) are defined in the Summary of Findings.

Consider g(x), a Parity Cycle function that takes an odd integer input, performs the Collatz Conjecture according to some Parity Cycle, and returns an odd integer that is also in the domain of g. Let the Parity Cycle corresponding to g(x) be:

1 odd, p₁ evens, 1 odd, p₂ evens, 1 odd, p₃ evens, … , 1 odd, p_b evens.

By the Collatz Conjecture function, for each “odd,” we can multiply by 3 and add 1 to our number. Similarly, for each “even,” we can divide our number by 2. 

Then, g(x) can be computed in terms of the p_i evens’s:

Due to the bulkiness of this representation, we make some substitutions to make this form more readable. We define the following:

From the definition of q, we deduce that q ? 1 (mod 2). Now, we substitute these values back into the representation for g(x):

By the definition of a Parity Cycle, g(x) may be applied repeatedly to an x in the domain of g. Let   g ^a (x) be the composition of g(x) on the number x exactly a times. Therefore, this would mean that g ^a (x) is an odd integer which is also in the domain of g for any positive integer a. 

Similar to how we expanded g(x), we can also expand g ^a (x) using the concise form we just constructed:

The sum in the numerator encased by parentheses is a geometric sequence with common ratio 2^s / r, so this form can be simplified by taking the sum of a geometric sequence:

Substituting this for the geometric series in the numerator of g ^a (x), we get: 

This final form represents the odd integer given after a applications of the Parity Cycle corresponding to g on a number x in the domain of g. Note that once x is determined, r, q, and s   are uniquely defined constants.

Now, we enforce the restriction that   g ^a (x) ? 1 (mod 2), which should be true by the definition of g: 

Multiplying both sides of this congruence statement by the odd number 2 ^s – r, we get 

We know q ? 1 (mod 2) by definition, so when we subtract q on both sides, we get:

Thus, we see that 

is an even integer. By the definition of g, a can be arbitrarily large and every other variable is constant, including x. From here, we have a few cases.

Case 1: Our first case is when 

In this case, since r and 2^s are relatively prime by definition, we must have that:

for all a. However, x(2^s-r)-q is constant, and 2^as is unbounded since a is unbounded. Therefore, the quotient of the two cannot be an integer and this case is impossible.

Case 2: Our second case is when 

Rearranging this, we find:

Therefore, 

for all a. Thus, this case corresponds to Looping, not Divergence. Specifically, not only do the parities of the numbers repeat after every iteration of the Parity Cycle corresponding to g, but the numbers themselves repeat. 

Before examining this any further, we see that it is not possible for a number to generate an infinite Diverging Collatz Reduction Sequence for which the corresponding infinitely long Parity Sequence is periodic with finite period. Therefore, a number can only Diverge if its infinitely long Parity Sequence is aperiodic, proving our finding on Divergence.

Now, we return to Case 2. We see that a number can lead to Looping if and only if 

Note that both the “if” part and the “only if” part are proven by the computation above for g ^a (x).

Further, since x > 0 and q > 0, we must have 2 ^s – r > 0, or 

if x leads to Looping. 

Hence, we have also proved our finding on Looping, and the proof is complete.

Recommendations For Future Research

A Parity Cycle corresponding to a number x can lead to Looping if and only if: 

For future research, we can try to verify if an expression of this form can be an integer. 

That is, we can try to find a sequence of numbers say p₁, p₂, … , p_b (which would correspond to the Parity Cycle) such that

The only known solution to this form is when b = 1 and p₁ = 2 (there are no p₂, p₃, etc. because b=1). In this case, we simply arrive at the trivial loop 

1, 2, 4, 1, 2, 4, … 

A word of caution: Finding a sequence p₁, p₂, …, p_b which satisfies the form presented above would prove that there exists a Parity Sequence for which Looping can occur, but not necessarily whether any number satisfies this discovered Parity Cycle.

References

[1]  “Collatz Conjecture.” Wikipedia, Wikimedia, 19 Sept. 2020,

https://en.wikipedia.org/wiki/collatz_conjecture.

[2]  Tao, Terence. “Almost All Orbits of the Collatz Map Attain Almost Bounded Values.” ArXiv.org, 7 June 2020,

https://arxiv.org/abs/1909.03562.