[Math] Some Questions on the Collatz conjecture (reexpressed as “equivalence relation”)

algorithmscollatz conjecturent.number-theoryopen-problems

The set of all positive whole numbers is denoted by $\mathbb{N}_+$.

Let $f\colon\ \mathbb{N}_+\to\mathbb{N}_+:n\mapsto
\begin{cases}\frac{n}{2}&\text{$n$ even}\\3n+1&\text{$n$ odd}\end{cases}$.

Conjecture (Collatz). $\forall n\in\mathbb{N}_+.\ \exists N\in\mathbb{N}.\ f^N(n)=1$.

Let $m,n\in\mathbb{N}_+$. We define: $m\sim n:\iff\exists N_1, N_2\in\mathbb{N}.\ f^{N_1}(m)=f^{N_2}(n)$.

It is easy to see that $\sim$ is an equivalence relation on $\mathbb{N}_+$. If we suppose the truth of the Collatz conjecture, then there is only one equivalence class.

  1. How to prove that there is only a finite number of equivalence classes of $\sim$? Has somebody ever proven this? Or is the question whether there is only a finite number of equivalence classes open?
  2. Is there an algorithm solving the following decision problem?

INSTANCE: A pair $(m, n)\in\mathbb{N}_+\times\mathbb{N}_+$

QUESTION: Does $m\sim n$ hold?

Best Answer

This problem is still open. See for example Sections 2.6 and 2.7 of Lagarias's survey.

Related Question