11

The usual argument in favor of the Collatz conjecture (or at least in favor of there being no unbounded trajectories) essentially argues that, if we have the "shortcut" function defined by: $$f(2x)=x$$ $$f(2x+1)=3x+2$$ then the parity of a number in the trajectory $x,\,f(x),\,f^2(x),\ldots$ of iterates of the Collatz function should be randomly distributed and therefore that the geometric mean of the ratios $\frac{f^n(x)}{f^{n+1}(x)}$ should be $\sqrt{3/4}$ unless $x$ is small - which suggests that the sequence should not grow without bound.

This is famously an open question - but there's an obvious generalization of the same reasoning: fix some natural number $m$ and some sequence of integers $a_k$ and $b_k$ indexed over the set $\{0,\ldots,m-1\}$. Define a function by the rule: $$g(mx+k)=a_kx+b_k$$ where $x$ is an integer and $k$ is an integer in $[0,m)$. Let's say that $g$ is Collatz-like if:

  1. $\gcd(m,a_k)=1$ for every $k$.

  2. $\prod_{k=0}^{m-1}\frac{a_k}m$ < 1.

  3. There is some $k$ such that $\frac{a_k}m > 1$.

The first condition enforces that the proportion of integers $x$ with a prescribed sequence of mod $m$ residues for $x,\,f(x),\,f^2(x),\ldots,\,f^{\ell}(x)$ is exactly $1/m^{\ell}$, which justifies treating these residues somewhat randomly. The second enforces that the logs of large numbers are expected to decrease. The last is a non-triviality condition, since any function violating it clearly has no unbounded trajectories.

Is there any example of a Collatz-like function $g$ for which it is known whether $g$ has an unbounded trajectory?

Milo Brandt
  • 60,888
  • I think (but am not sure) that there aren't known examples. Even for the $5x+1$ problem, where it certainly appears that there are plenty of unbounded trajectories, I don't think any one has proven that there is one. this question may have some useful information. – lulu Jan 12 '20 at 16:13
  • I did not yet really understand the arguing of R. Crandall in his 1978-article, but he pointed to the version $m \cdot x + 1$ with $m=1093$ (a wieferich-prime) , and it seemed to me, he says that there must be divergent trajectories (but I never really got through that argument - correct me if I'm wrong). (P.s.: also don't see at the moment how this reformulates actually in your $g(mx+k)$-style formula) – Gottfried Helms Jan 12 '20 at 16:29
  • @GottfriedHelms Interesting; I'll look into that article. – Milo Brandt Jan 12 '20 at 17:00
  • 2
    See conjectures 1 and 2 here: http://www.numbertheory.org/keith/markov_matrix.html#conjecture1. (They are hard to read, I’m afraid, but they are related to your question). – rukhin Jan 12 '20 at 18:56
  • Conway considered a class of generalizations of Collatz, much like (maybe even identical to) the class you present, and proved that in this class there are examples that are undecidable. J. H. Conway, Unpredictable iterations, in Proc. Number Theory Conf., Boulder, CO, 1972, pp. 49-52. – Gerry Myerson Jan 13 '20 at 02:27
  • 2
    @GerryMyerson That paper inspired this question! Conway considers the class of functions I describe without the three restrictions and, indeed, his construction relies critically on violating the first condition I list in the question - which is what pushed me to think about why his functions could behave so badly in light of the usual heuristic arguments about the Collatz conjecture. – Milo Brandt Jan 13 '20 at 03:35
  • It seems, the reference to Crandall 78 is misleading for this question - if you want I'll retract my comment in the answerbox. – Gottfried Helms Jan 13 '20 at 07:26

0 Answers0