On The Collatz Conjecture

On the Collatz conjecture Alexandre Bali April 9, 2019 Abstract This paper is a revision to the latter I had released on the conjecture[1] . A few additional results were also found in much more rigorous ways. The results introduced in this paper may not forcefully be new, but I wanted to share what I found since September 2018.

Definitions. The study of the conjecture typically uses either one of the following mappings :  3n + 1 n odd n 7−→ n/2 otherwise  1.5n + 0.5 n odd or n 7−→ n/2 otherwise

(original one) (slightly faster)

We’ll be using neither. Instead, we’ll use the one which only outputs odd numbers. We can write define this map for odd inputs using the 2-adic valuation ν2 as such : φ : n 7−→

3n + 1 2ν2 (3n+1)

We start with some odd number e0 and define the sequence (en )n≥0 with en+1 = φ(en ). The usefulness of this approach can be revealed through a strong pattern which reveals for n ≥ 2 which can be proven by induction :   n−1 P 1 k−1 Q ν2 (3e +1) n n−1 ` 3 e0 + 3 1+ 2 3k `=0 k=1 en = (∗) n−1 Q ν (3e +1) 2 k 2 k=0

1

Proof. First off, we need to start with e2 . Using the hypothesis, we should find the following : 32 e0 +31 1+

k=1

e2 = =

1 P

k−1 Q

1 3k

! 2ν2 (3e` +1)

`=0

1 Q

2ν2 (3ek +1) k=0 ν (3e 9e0 +3+2 2 0 +1) ν 2 2 (3e0 +1) 2ν2 (3e1 +1)

Using the definition of the sequence, we have the following : e2 = = =

3e1 +1 2ν2 (3e1 +1)  3e0 +1 3 ν (3e +1 +1)

0 2 2 2ν2 (3e1 +1) 9e0 +3+2ν2 (3e0 +1) 2ν2 (3e0 +1) 2ν2 (3e1 +1)

Both results are equal, so the hypothesis checks out for n = 2. We now need to induce the hypothesis. For the induction to work, we need to show that (∗) must imply that :   k−1 n P 1 Q ν2 (3e` +1) n+1 n 3 e0 + 3 1 + 2 3k `=0 k=1 en+1 = n Q 2ν2 (3ek +1) k=0

For this, we’ll compute en+1 as φ(en ) using (∗) for en , which gives us the following : !  n−1 k−1 3n e0 +3n−1 1+

2ν2 (3en +1) e

n+1

k=1

 = 3 3n+1 e

n−1 Q

0

+3n

Q

2ν2 (3e` +1)

`=0

 +1

1 3k

k−1 Q

! 2ν2 (3e` +1)

n−1 Q

+

2ν2 (3ek +1)

`=0 k=0 n−1 Q 2ν2 (3en +1) 2ν2 (3ek +1) k=0 ! k−1 Q ν (3e +1) 1 n−1 Q ν (3e +1) 1+ 2 2 ` + 3n 2 2 k 0 k=1 `=0 k=0 n Q ν (3e +1) 2 k 2 k=0 ! k−1 n P 1 Q ν (3e +1) 2 ` 3n+1 e0 +3n 1+ 2 3k k=1 `=0 n Q ν (3e 2 2 k +1) k=0

3n+1 e

=

1+

1 3k

2ν2 (3ek +1)

k=0 n−1 P k=1

en+1 =

=

P

+3n

n−1 P

1 3k



2

Lemma. If e0 = min{en : n ∈ N}, then for all n ∈ N and n ≤ 112, we have

n X

ν2 (3ek + 1) < (n + 1) log2 3 + 2.25

k=0

P roof . We know that all nontrivial cyclic sequences have a length greater than or equal to 301 994[2] . So, assume (en ) is cyclic, and that e0 is the minimal element of the cycle. Then,   n n P Q 3 ν (3e +1) 2 k ν2 (3ek + 1) 2 − log2 en+1 < (n + 1) log2 3 + log2 3e0 + 1 + 2n+1 k=0 k=0  n n P Q 3 = (n + 1) log2 3 + log2 2n+1 ν2 (3ek + 1) + o(1) 2ν2 (3ek +1) − k=0

k=0

= (n + 1)(log2 3 − 1) + log2 3 +

n P

ν2 (3ek + 1) −

k=0

n P

ν2 (3ek + 1) + o(1)

k=0

= (n + 1)(log2 3 − 1) + log2 3 + o(1) Because it’s cyclic, and because the o(1) term will eventually get arbitrarily close to 0, we can remove this term and replace it by 0.00001 or something. Furthermore, since all terms must be greater than 87×260 , we can show that log2 (3en+1 + 1) < log2 (3en+1 ) + 4.795 × 10−21 Because for all n0 ∈ N we have ν2 (n0 ) ≤ log2 n0 , we may show that ν2 (3en+1 + 1) ≤ b(n + 1)(log2 3 − 1) + 3.17c ν2 (3en + 1) is the number of steps to get from en to en+1 with the (3n + 1)/2 sequence. Although, the formula doesn’t apply for n ≤ 1, but we can still show that e0 is minimal implies ν2 (3e0 + 1) = 1 and ν2 (3e1 + 1) ≤ 2, hence 113 X k=0

ν2 (3ek + 1) ≤ 1 + 2 +

113 X

bk log2 (3/2) + 3.17c = 4 070

k=2

Overall, we can only exhaust less than 4 070 out of more than 301 994 terms in the (3n+1)/2 sequence non-trivial cycles as we exhaust 113 in (en ). Hence, there would be infinitely many k for non-trivially cyclic (en ) such that for all k0 : k0 < k ≤ k0 + 112, we’d have ek < ek0 . For non-cyclic sequences, there are automatically infinitely many k ∈ N

3

such that for all k0 > k, we’d have e0 < ek0 . Therefore, we can say that there are infinitely many values of e0 such that for all n ≤ 112, e0 < en+1 e0

n Q

2ν2 (3ek +1)

<

k=0

3n+1

1−

3n /e

 0

n P

k=0

1 3k

3n+1 e 

> n Q `=k

1−

0

3n

+ 

3n e0

1 2ν2 (3e` +1)



n P

k=0

n P k=0 1 3k

1 3k

n Q

`=k

n Q `=k



1 2ν2 (3e` +1)



1 2ν2 (3e` +1)

n Q

2ν2 (3ek +1)

k=0

n Q

2ν2 (3ek +1)

k=0

 > 0 is implied if

j k n + 1 ≤ log3/2 (87 × 260 ) = 113 We can then easily deduce the expected result. 

Corollary. If (en ) is a counterexample of Collatz conjecture, then there are infinitely many values of k ∈ N such that 46 | 3ek + 1. (For the 3n + 1 version, Collatz equivalently states that there are only finitely many even terms for which both the previous term and the next term are odd. For the slightly more dynamic (3n + 1)/2 version, Collatz equivalent states that there are finitely many consecutives odd numbers.)

P roof . There are infinitely many k such that for all k0 : k ≤ k0 ≤ k + 112, we have ek < ek0 (once again because of cycles’ minimal lengths being much bigger than 112). Hence, for these values of k, we may apply, for all n ≤ 112, the formula n X

ν2 (3e` + 1) ≤ (n − k + 1) log2 3 + 2.25

`=k

This is perhaps a more general formula than the lemma’s, but it’s easy to be conviced by “shifting” ek0 to e0 . However, this means that in these regions, the mean of all ν2 (3e` + 1) for all ` : k0 ≤ ` ≤ k0 + 112 doesn’t exceed 1<

113 log2 3+2.25 113

= log2 3 +

4

2.25 113

<2

This means there are values of ν2 (3ek + 1) which are strictly below 2, otherwise it would always exceed or be equal to 2 in these infinitely many regions.  In fact, this corollary can be proved much more easily without the said lemma because there would always be infinitely many k such that k0 > k ⇒ ek0 > ek , and that for all such k, ν2 (3ek + 1) could only be 1 otherwise ek+1 < ek , which is a contradiction, so there would be infinitely many k such that ν2 (3ek + 1) = 1 anyway. However, the longer proof gives us more insight and depth to how ν2 (3ek + 1) behaves within hypothetical counterexamplar sequences, and equivalently on how many terms there are between two odd terms within Collatz sequences defined with slower dynamics. One insight it gives us is the following lemma’s corollary.

Conclusion. Collatz conjecture implies that there should only exist finitely many values of k such that ν2 (3ek + 1) = 1, but by the corollary, this property would fail for all counterexamples of the Collatz conjecture. Hence, if we prove that for all large enough k we have ν2 (3ek + 1) ≥ 2, this would actually prove Collatz conjecture, and throughout this paper, we’ve even shown the strong result that both statement are equivalent.

References. [1] A. Bali, On the eventuality of a smallest counterexample of the Collatz conjecture (Sep 29, 2018). http : //tinyurl.com/y2uf9c85. [2] J. C. Lagarias, The 3x+1 Problem and its Generalizations, the American Mathematical Monthly, vol. 92, 1985, pp. 3-23.

5