4

I have watched Veritasium's recent video on the Collatz conjecture. At 11m17s, he mentions that if you can show that for every seed value, there is at some point a number less than the seed value in the sequence generated by the Collatz function, then you've proven the conjecture. Doesn't this condition preclude a loop?

If I have some loop, won't it at some point include a reduction in value? For example, if I have a loop that goes $12 \to 15 \to 64 \to 72 \to 12$ can't I just say, well $72$ is my seed value, since $12 < 72$, then $72$ must reduce, and all the other values in the loop reduce as well?

I understand its a popular video, and it's not a precise definition, but it seems like a rather simple statement. I'm just a little confused by what he said, not sure if there's a second unstated condition or if I'm misunderstanding.

Rodrigo de Azevedo
  • 1
Fuzzy_Bunnys
  • 185
  • In the logic of the common argument you would have tested $a=12$ before $a=72$ and had already found that no iteration gives a smaller value $a_k$ than $a_1=12$. – Gottfried Helms Oct 10 '21 at 06:50
  • Presumably they meant "there is at some point a number less than the seed value, unless the seed was 1". This permits loops that contain 1. – Daniel Wagner Oct 10 '21 at 15:03

2 Answers2

6

if you can show that for every seed value, there is at some point a number less than the seed value in the sequence generated by the Collatz function, then you've proven the conjecture. Doesn't this condition preclude a loop?

The key word here is every seed value. If you take your loop, you've only shown the condition for the seed value 72, not for every seed value.

Ted
  • 33,788
4

If every sequence with a seed value $S$ leads to a lower value $L$, then the sequence with seed value using that lower value will itself lead to another lower value.

Applying this recursively eventually forces us to reach the lowest possible value of 1. The seed value must be finite as a positive integer, the number of lower values must also be finite, so the sequence of sequences that lead recursively down to 1 is a finite sequence, proving the conjecture.

A proof of the hypothesis (all seeds lead to at least one lower value) means that loops are impossible; a proof that there exists at least one loop is a proof that the conjecture is false; the two are mutually exclusive.

Nij
  • 2,991