A complete proof of the Collatz conjecture

[Guest]

collatz conjecture (2).docx

(77.19 KiB) Downloaded 286 times

Hi everybody

Yes, it's a complete proof for the Collatz conjecture. At least, I checked it over again and again and could not find any flaw in it.
Can you please take a look if you can find out something that I've missed ? I'll appreciate it a lot.
Thank you !
Dror

[dodomaze]

Hi,
on page 3, on the "case 1" and "case 2" for the proof coming from page 2,
you seem to have drawn conclusions for nm=1 or 2, and assume it will be the same for higher nm.

For example, for nm=3, (please correct me if these examples are wrong),
starting from 11 you reach 10 in 1 mult., 1 div., 1 mult., 2 div., 1 mult., 2 div.,
but starting from 23 you reach 20 in 1 mult., 1 div., 1 mult., 1 div., 1 mult., 3 div.

Notice how the divisions after the second mult. are different!
Even if the total number of divisions is the same, the route changes, so your induction proof does not hold - that is not a way to prove that a smaller number will be reached.

I could not continue from page 3 because of this. If you could clarify this particular issue, I'm listening.

[Guest]

Hi
a[tex]x_{1 }[/tex]

[Guest]

Oops! correction:

[dodomaze]

Thanks for the corrections,
but you keep having problems with the "and so on" part. There is no simple "and so on".
As nm increases. the number of ways in which the total "nd" can partition among the various "nd_i" gets more complex.
More importantly for an induction proof, you don't establish how to create the cases for nm+1 based on the cases for nm.

Some examples for nm=16:
991 1,1,1,1,3,1,2,1,1,2,2,1,2,1,2,4 637
1951 1,1,1,1,2,1,3,2,1,1,3,1,1,1,3,3 1253
1959 1,1,2,1,2,2,1,1,2,1,1,2,1,1,1,6 1258
Some for nm=17:
251 1,2,1,2,1,1,1,1,1,3,1,1,1,4,2,2,2 244
495 1,1,1,2,1,1,2,1,1,2,2,1,2,1,2,4,2 478
795 1,2,1,1,1,1,1,1,3,1,3,2,1,1,1,3,3 767
And these are not, by far, the only cases.
But you need to understand that your attempt at proof is not fixed only by adding the few numerical examples I give you;
you would need to find a general rule that describes how to generate the cases for nm+1, based on the cases for nm.

[Guest]

Hi
Does it answer your question ?

[Guest]

In short: no.

I see what you are trying to do (compensate increases with decreases to get the same total), but there are multiple problems here.

Let me address the most important one, before it is forgotten in the forest of details: all the algebra you're doing "should" have the purpose of demonstrating that the numbers "nm" and "nd" EXIST in the first place.

That was the idea in your initial proof by induction, two days ago. But this idea gets lost every time you assume that these series, from a_0 to a_nm, EXIST. You can entertain yourself (it's a nice exercise that you're doing here) trying to prove that, for any series where 2^nd > 3^nm, you will have a_nm < a_0. Nice exercise, but it will not prove the Collatz conjecture. Because you ASSUME that such series always exist and such numbers nd, nm always exist. This is a big "if". There could be a series that just grows and grows "nm", without decreasing "nd" sufficiently - you can't discard that from the start, especially when "nm" and "nd" could be as arbitrarily large as you wish - there exist infinite integers, not just a collection of enumerable cases. Your proof by induction was supposed to guarantee this, but you seem to have abandoned it. You will notice the abandonment, the moment you try to put all your material together in a single, complete proof, instead of showing one chapter at a time.

Now let me go to the problems in your last document. But, I insist, this is just about a separate exercise ("IF" nm, nd exist for a series a_0,a_1,...,a_nm such that 2^nd < 3^nm, "THEN" a_nm < a_0). In other words, you may complete "if A then B" after a lot of work, but if you don't prove A by itself, you don't have B. You only have B when BOTH of the following conditions are met: (1) "A is true" AND (2) "if A then B". Please don't say "I already did A", because you have not yet, except for a few cases (but there are infinite cases!). If you believe you have, first prove it to yourself, and then to others (in that order).

And, by the way, congratulations, good discovery work you're doing here, but I'm afraid this is not new. (Don't worry, we all reinvent the wheel.) Terras' 1976 paper "A stopping time problem on the positive integers" already mentions these subjects, but I don't have it fresh and I can't tell you at the moment how much overlap is there with your work. I'll try to go through the paper again this weekend (I need the refresher myself), but you can give it a shot yourself, just google it. Theorem 1.1 defines a quantity "lambda_i = 3^{S(i)} / 2^i", where his "S(i)" is similar to your "nm" and his "i" to your "nd"; his "n" is your "a_0" and his "T^i(n)" or "T^k(n)" is your "a_nm" (except he is not assuming a_nm < a_0 yet). Then "Definition 1.5" starts to study the case where "lambda_i" < 1 (that is, where 3^{S(i)} < 2^i, precisely what you're trying to study). (Notice how in Definition 1.5 he is VERY careful to recognize that these numbers may or may not exist.) Propositions 1.7 and 1.8, and I think up to Theorem 1.9, try to go where you are going but, as I said, I don't have the details fresh. Try to read it and understand it anyway if you're serious about what you do, because this paper is Collatz 101.

So, problems with your last document:

(1) The main one, a repetition of your "and so on..." habit: you assumed the increase and decrease occur in CONTIGUOUS steps. This is not necessarily true. An increase by 1 could occur at step "j", and the corresponding decrease by 1 has no obligation of occurring at step "j+1", it could occur at step "j+10", or not at all: you assumed all other numbers equal, nd_j increased and nd_{j+1} decreased. This is a VERY PARTICULAR case, and not "without loss of generality", because the inequality that follows in the next line DEPENDS on nd_j and nd_{j+1} being contiguous. Just finishing with the words "and the same method applies to any case" is wrong, and a very bad habit. Please stop doing this. I appreciate your hope and enthusiasm for the problem, but it is no substitute for rigorous and complete procedure.

(2) Your claim at the beginning, "We have proved that if 2^nd > 3^nm, then there is at least one sequence such that a_nm < a_0". I don't see where you proved this, I may be mistaken. Maybe for a few cases of "nm", but not for ANY arbitrarily large "nm". However, I don't think this is much of a problem, since for any "nm" > 0, you can always find an "x" >= nm such that the following fraction is an integer, and use this integer as "a_0":
[tex]\frac{2^x - \sum_{i=0}^{nm-1} 2^i 3^{nm-1-i} {3^nm}[/tex]
("x" would be a "discrete logarithm" for the sum, modulo 3^nm); if I'm not mistaken, this choice of "a_0" should produce "nm" repetitions of the pair or operations "1 mult. 3n+1, 1 div. n/2", after which you end on a power of 2 larger than 3^nm (in fact, descent directly down to 1). So I don't worry too much about it; I just don't see you have done this yourself yet in your documents, not for ALL possible "nm".

[dodomaze]

Sorry, repeating that fraction at the end as a separate post, because apparently I can't edit it:
[tex]\frac{2^x - \sum_{i=0}^{nm-1} 2^i \, 3^{nm-1-i}} {3^{nm}}[/tex]
(namely, sequence A287319 in OEIS.)

[Guest]

I hope it's a clearer description of the 1st part of the solution.

[Guest]

I hope it's a clearern description of the 1st part of the proof

[dodomaze]

Again, multiple logic problems. I will address only one of them, to see if I get an exact answer.

Consider only the case [tex]a_{nm} > \frac 2 3 a_0[/tex]. You claim:

For any given sequence [tex]nd_1,...,nd_j[/tex] (starting with [tex]a_0[/tex] and ending with [tex]a_{nm}[/tex])
that fulfills [tex]2^{nd} > 3^{nm}[/tex] and [tex]a_{nm} < a_0[/tex],
there is a sequence [tex]1,nd_1,...,nd_j+1[/tex] (starting with [tex]a_0'[/tex] and ending with [tex]a_{nm+1}'[/tex])
that fulfills [tex]2^{nd+2} > 3^{nm+1}[/tex] and [tex]a_{nm+1}' < a_0'[/tex]

First, what is "j"? The length of the first sequence should have been "nm". Is j=nm? If so, why a new letter?

I understand why the first item in the second sequence is a 1, because the number must be of the form 4n+3 in order to have nm>1. That is fine.
But why do you add 1 only to the last element, and claim that such a sequence must exist?

For example, for nm=4, [tex]a_0=7[/tex] produces the sequence 1,1,2,3, ending in [tex]a_{nm}=5[/tex]; but I am having trouble finding an number with nm=5 that would produce a sequence 1,1,1,2,4.
Maybe it exists, but MORE IMPORTANTLY, you don't give any reason for it.

It is important that you be the most strict judge of your own statements. Do an effort for checking if every sentence in your documents is actually true. Try on purpose to find examples that make it fail.

[Guest]

reply

[dodomaze]

Sure, you can find one value that works. But your statement says "for any given sequence".

Working "for one" is not the same as working "for all". The rest of the statements afterward will not follow. All you prove is that "some" number fulfill the Collatz conjecture, not "all".

Let me be more clear: the sequences of [tex]nd_i[/tex] alone will not help, if you ignore the [tex]a_0[/tex] that starts the sequence. Statements about sequences were depending on the [tex]a_0[/tex] that started the sequence. You can try making statements about sequences in general, but you cannot conclude from this that every number will fulfill the conjecture, especially when you know that your sequences will not work for some numbers.

Writing about a sequence was based on the number that started the sequence. That is called "making an assumption". Every math proof establishes some assumptions, then proceeds from these assumptions.

The big problem I see in your work is that you easily lose track of your assumptions. I need to insist on writing the complete text, not parts of it. On the previous reply you said "We have already proven...". Well, no, you have not. Write the entire thing. Because the main problem in your text is establishing assumptions, and then ignoring them.

[Guest]

A detailed description of claim A

[dodomaze]

This is considerably better presented. I'm still not convinced , but at least it does not look like a mad rambling anymore, and it is at a stage where I can ask precise questions.

(Q.1)
In claim A2.1, could you write explicitly how would the expression look at the last step, when going from [tex]a_{nm-1}[/tex] to [tex]a_{nm}[/tex], please?
The reason I ask is because it seems to me that, by the final step, the exponent of 2 is going to exhaust, something like [tex](2^{nd-nd_1-nd_2-...-nd_{nm}} = 2^{nd-nd} = 2^0)[/tex];
in this case we cannot claim that the final [tex]a_{nm}[/tex] is odd, nor that the new sequence ends with the same [tex]nd_{nm}[/tex] as the original sequence.
But please check it yourself, it's only an impression and I may be wrong. (Plus I don't want to do the work for you.)
If this is a problem, it's not difficult to solve, just use [tex]a_0+k \cdot 2^{nd+1}[/tex] instead.
But only if there is in fact a problem; if it is correct, it would be better to leave it as it is now, with the minimal possible requisite.
If you find this is in fact wrong and needs one more 2, please try some actual numbers, with k odd, and see if you find a counterexample.

(Q.2)
In claim A2.2, if [tex]a_0+k \cdot 2^{nd}[/tex] generates the given sequence, and [tex]b_0[/tex] is an immediate predecessor of [tex]a_0+k \cdot 2^{nd}[/tex],
then the new sequence for [tex]b_0[/tex] should have ended exactly at the same odd number where the sequence for [tex]a_0+k \cdot 2^{nd}[/tex] ended.
Why would the final number be even half the time? I suspect the issue in Q.1 may be involved. If not, please explain.

I'll ask more question after your answers, because I can't follow claim A2.3 until this is resolved. But you're doing a much clearer work this time, thanks.

[Guest]

A detailed description (correction)

[Guest]

Hold, hold, hold. If you modified claim A2.1, then you can't leave claim A2.2 as it was. In claim A2.2 you say,

according to A2.1, initial values of the form [tex]a_0+k \cdot 2^{nd}[/tex] generate the sequence [tex](nd_1, \ldots, nd_{nm})[/tex]

but this is not what claim A2.1 now says. Claim A2.1 now says something about a "similar" sequence; the "quotes" show imprecision - please be precise, otherwise, how can you use claim A2.1 later?

Also, you seem to have ignored question (2); this is important, since it shows a contradiction with your statements in A2.2. If I understand it incorrectly and the question does not apply, please let me know why do you think so.

...

In case you have some confusion about what happened in claim A2.1, maybe it would help it you write down the second step (first steps always tend to be special); writing down the second step (not as part of the proof, but for you own work, to understand what is happening) is useful before claiming "the same argument hold for the next terms". Hint: the first step was

[tex]\frac{3(a_0+k \cdot 2^{nd})}{2^{nd_1}} = \frac{3a_0+1}{2^{nd_1}} + k \cdot 2^{nd - nd_1}[/tex]

but the second step is definitely NOT

[tex]\frac{3(a_0+k \cdot 2^{nd})}{2^{nd_2}} = \frac{3a_0+1}{2^{nd_2}} + k \cdot 2^{nd - nd_2}[/tex]

You probably know this already, but I'm pointing it out just in case.

[dodomaze]

One simple question, that you can answer with "yes" or "no". Is [tex]a_{nm} = \frac{3a_{nm-1}+1}{2^{nd_{nm}}}[/tex] always odd?
Yes = always odd, or
No = it can be even sometimes.

P.S.: note what you say at the end of claim A2.1, regarding [tex]\frac{3a_{nm-1}+1}{2^{nd_{nm}}} + k[/tex]

which is even for odd k’s

[Guest]

Another day, another correction.

[dodomaze]

End of claim A2.1: if the last number can be odd or even... then what is the reason why the new sequence ends in [tex]nd_{nm}[/tex], like the original one? I'm missing the punchline.

In the other steps it was sufficient to show that the term was odd, therefore guaranteeing that the next step will be a 3n+1 step, as expected. But the sequence terminates when you find a number smaller than the initial one, and I don't see any evidence that the new sequence has terminated in the same manner.

I'm going to add one more issue with claim A2.2, that I didn't the last time because there were already too many problems. You say, "if the last term is an even number, it can be divided". How many times, just one? Why one? Did the final number become smaller than the initial number? Same problem as above, not explaining how the sequence ends.

Also, I have been too lenient in the past. The new terms cannot be called [tex]a_1, a_2, ..., a_{nm}[/tex], because those were the names of the original values (just before each multiplication step), and using the same names implies that the values are the same, which is not the case (for example, [tex]a_0[/tex] is not the same as [tex]a_0 + k \cdot 2^{nd}[/tex]). Please, same names for the same entities, and different names for different entities, otherwise your reader is not following an argument but instead trying to guess what you mean.

The errors I have been pointing out are not merely notation problems. They show that you don't seem to have an argument. This is not about self-expression. It is about you yourself understanding why you computer evidence happens.