What are some reasonable things to prove about the Collatz Conjecture?

Question

I am writing an undergraduate paper on the $3n+1$ problem, and I am looking for some theorems related to the problem that would be reasonable for someone with my mathematical background to prove. I'm near the end of my undergraduate studies. I have had a pretty basic introduction to Number Theory and Group Theory. I have also taken a few introductory Computer Science courses. Those are the only courses that I've taken that seem to be relevant to the problem but otherwise my math classes have been: the usually calculus sequence, real analysis, introductory topology, linear algebra.

A good answer to my question would do the following:

• Either state one or more non-trivial theorems related to the Collatz conjecture, or reference sources that would contain this kind of information.
• Would NOT state any proofs unless a proof or partial proof would be essential for someone with my requisites if they are to be able to provide a full proof.

Theorems that I have already proved:

If $L(n)$ is a function that counts the number of mappings in the Collatz function for $n$ to get to 1, then if $n = 8k+4$, $L(n) = L(n+1)$.

If $n = 128k+28$ then $L(n) = L(n+2)$.

Answer 1

The starting point for the literature is the survey by Jeff Lagarias ten years ago:

math/0309224 The 3x+1 problem: An annotated bibliography (1963--1999) (sorted by author). Jeffrey C. Lagarias. math.NT (math.DS). https://arxiv.org/abs/math/0309224

Other papers from an arxiv Front search for Collatz and 3x+1:

math/0608208 The 3x+1 Problem: An Annotated Bibliography, II (2000-2009). Jeffrey C. Lagarias. math.NT (math.DS) https://arxiv.org/abs/math/0608208

arXiv:0910.1944 Stochastic Models for the 3x+1 and 5x+1 Problems. Alex V. Kontorovich, Jeffrey C. Lagarias. in: The Ultimate Challenge: The 3x+1 problem, Amer. Math. Soc.: Providence 2010, pp. 131--188. math.NT. https://arxiv.org/abs/0910.1944

math/0509175 Benford's law for the $3x+1$ function. Jeffrey C. Lagarias, K. Soundararajan. J. London Math. Soc. 74 (2006), 289--303. math.NT (math.PR). https://arxiv.org/abs/math/0509175

math/0412003 Benford's Law, Values of L-functions and the 3x+1 Problem. Alex V. Kontorovich, Steven J. Miller. Acta Arithmetica 120 (2005), no. 3, 269-297. math.NT (math.PR). https://arxiv.org/abs/math/0412003

and

https://arxiv.org/abs/math/0411140

https://arxiv.org/abs/math/0205002

https://arxiv.org/abs/math/0201102

https://arxiv.org/abs/math/0204170

There are many un-serious papers on this subject at the same site, I selected the above from papers that I read or authors whose other papers I have seen.

There is also a celebrated theorem by John H Conway in which he shows that the natural generalization of the Collatz problem, where different linear functions are applied to $n$ in several arithmetic progressions (partitioning all integers), can simulate a computer. A consequence is that it is undecidable to determine if such an iteration loops when started from $1$.

Answer 2

One important relation to other number theoretic problems is that of the distance of perfect powers of 2 and 3, for which a lot of material exists, even online accessible. The existence of the so-called "1-cycles"¹ (which is a whole class of possible cycles of arbitrary length but a certain simple structure) is directly dependent on the question, whether $$ {k3^N-1 \over k2^N-1}=2^A $$ exists in natural numbers N,A and k (besides for "trivial" solution (N,A,k)=(1,1,1), which leads to the (unsolved) problem observed in the Waring-conjecture whether $$ (3/4)^N \lt \{ ( 3/2)^N \} \lt 1-(3/4)^N $$ $ \qquad \qquad $ where $ \{ \cdot \}$ means the fractional part (see for instance mathworld)

Here is also the concept of K.Mahler's "z-numbers" relevant, which also relates the "1-cycles" in a general view to the powers of 3/2 and is also not too difficult to understand for a treatize which focuses an undergraduate publicum.

¹Simons, John; de Weger, Benne, Theoretical and computational bounds for (m)-cycles of the (3n+1)-problem, Acta Arith. 117, No. 1, 51-70 (2005). eudml, ZBL1136.11019.