Number Theory – Reference for Collatz Conjecture as a Combinatorics Problem

collatz conjectureinfinite-combinatoricsnt.number-theory

It occurs to me that the question about whether non-trivial cycles exist for the collatz conjecture can be restated as these two questions (details on how this relates to the collatz conjecture can be found here):

  • Is there a general method for determining how many distinct values of $t_1, t_2, \dots, t_k$ exist for a given $k$ such that:

    • $t_k > t_{k-1} > \dots > t_2 > t_1 > 0$
    • $2\left(2^{t_k} – 3^k\right) < 3^{k-1} + \sum\limits_{i=1}^{k-1}3^{k-1-i}2^{t_i}$

  • Would it follow that as $k$ increases, the number of distinct values approaches infinity?

It seems to me that if the number of distinct values approaches infinity and distinct values have sufficient variability, then the collatz conjecture is most likely not true. If the number of distinct values has a finite limit, then the collatz conjecture may well be true.

Are there any well known papers that investigate the collatz conjecture from this viewpoint?

Intuitively, it seems to me that one of the following must be true:

  • there is only a finite number of distinct values of $3^{k-1} + \sum\limits_{i=1}^{k-1}3^{k-1-i}2^{t_i} > 2\left(2^{t_k} – 3^k\right)$
  • there is an infinite number of distinct values but all are relatively prime to $2^{t_k} – 3^k$
  • the collatz conjecture has at least one non-trivial cycle

Are there any well-known results that address this approach?

Best Answer

Lagarias' bibliographies give some references from where you might search forward. For instance see this image This is from the year-2004 version; Lagarias updated this up to version 2011; the Lagarias bibliogrphies are downloadable from the net.

Update (7'22): Just found an old downloaded article

Maurice Margenstern and Yuri Matiyasevich   

Abstract:
We show how the 3 x + 1  conjecture can be expressed
in the language of arithmetical formulas with 
binomial coefficients.

e-mail: [email protected]   
e-mail: [email protected]      
URL: http://logic.pdmi.ras.ru/~yumat

This is of 1998; don't know whether the URL or the email is still working; maybe it is only tangential to your question, but thought it might be of interest from a wider perspective in the combinatorical context.

Related Question