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)$.
Best Answer
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$.