0

Basically the title. Exhaustive computer searches are going on all the time, but if we seem to find a very large counterexample to the Collatz Conjecture, how will we ever know that it doesn't, in the end, hit $1$? Are there any results, theorems, or algorithms that can help us here?

Gottfried Helms
  • 34,920
Nico A
  • 4,934
  • 4
  • 23
  • 49
  • 2
    An obvious possibility is that it has been found that $n \to \cdots \to n,$ i.e. there is a cycle not including $1$. – md2perpe Jan 01 '18 at 16:52
  • Welcome to the Collatz game :) Might I recommend a book? "The Ultimate Challenge: The 3x+1 Problem", edited by Jeff Lagarias, compiles most known results on this topic. – G Tony Jacobs Jan 01 '18 at 16:52
  • Counterexamples come with a proof that they are counterexamples. – Christian Blatter Jan 01 '18 at 16:54
  • 1
    @ChristianBlatter How? If the number just keeps getting larger and never hits a cycle... – Nico A Jan 01 '18 at 17:09
  • 1
    In theory one could hope to prove that the iterates of $n$ never get below $n$. The least counterexample would certainly have that property. – lulu Jan 01 '18 at 17:13
  • 2
    This is part of what makes the problem difficult. Of course, if we find a loop other than 1-4-2-1, then just listing that loop, or even a single number in that loop, is enough to allow anyone else to confirm. However, if the number just gives a diverging sequence, I don't think anyone knows what a proof of such a divergence could possibly be. Modular arithmetic, for instance, is uncharacteristically unhelpful. – Arthur Jan 01 '18 at 17:44

2 Answers2

1

"Are there any results, theorems, or algorithms that can help us here?" Perhaps the following is interesting if not helpful: if there really is a nontrivial cycle in the Collatz problem, then $\det M (d) = 0$ for all large $d$, but if there are none then $\det M (d) = (−1)^d$ for all $d$. Here $M(d)$ is Zeilberger's matrix.

References: Chapman

Zeilberger's determinant evaluation problem

Dietrich Burde
  • 130,978
  • 1
    Hmm, I think this is a simple (or even complicated) "blow-up" of the original problem (see Chapman's proof) and thus surely not really helpful . – Gottfried Helms Jan 02 '18 at 09:39
  • @GottfriedHelms Yes, I just found it interesting. "Helpful" here, it seems from the comments, is not really available in this context (but "unhelpful" is). – Dietrich Burde Jan 02 '18 at 12:00
  • Dietrich - thanks for your reflection. Actually, my comment might be enough for what should to be said; I've been courious enough to follow your links and to experiment a bit with that matrix - "one nice idea" I must say ... . I'm now deeply involved in another problem so I just want to respond shortly that I don't want to make a big problem. Happy new year to all, btw. - Gottfried – Gottfried Helms Jan 02 '18 at 14:39
0

You're touching upon the notion that the conjecture may be unprovable within certain mathematical systems. This does indeed follow from your observation that one counterexample could ascend indefinitely to infinity.

If a theory weren't strong enough, any proof that some infinitely long sequence exists might itself not be writable in a finite number of steps, making such a proof impossible to complete.

it's a hire car baby
  • 9,243