2
$\begingroup$

I am looking for feedback on the below, any is appreciated :)

Remark:

Apologies in advance for any incorrect use of notation as my mathematical experience is quite novice, additionally a word of warning as the description and ideas that are laid out are more verbal/visual in nature rather than symbolically.

Definition:

As borrowed from Wikipedia, the Collatz conjecture is defined by:

$ f(n) = \left\{\begin{array}{lr} \frac{n} {2} &\text{if } n \equiv 0 \pmod{2}\\ 3n+1 &\text{if } n\equiv 1 \pmod{2} \end{array}\right. $

where ${n \in \mathbb{N}}$ forms a sequence given by:

$ a_i = \left\{\begin{array}{lr} n & \text{for } i = 0\\ f(a_{i-1}) & \text{for } i > 1 \end{array}\right. $

and asserts that the iteration will eventually reach the number 1, regardless of which positive integer is initially chosen.

With the below approach we would like to attempt the impossible, starting with a couple of trivial propositions as an introduction.

Proposition 1:

The sum of any number of even integers is an even integer.

Proposition 2:

The sum of one even integer and two odd integers is always an even integer.

Proposition 3:

Following from proposition 2, any even integer is the sum of at least one or more combinations of one even integer and two equal odd integers.

Some prime examples from proposition 3 are:

$8 = 6 + 1 + 1$,

$6 = 4 + 1 + 1$,

$4 = 2 + 1 + 1$.

Given proposition 3 we can introduce the next proposition.

Proposition 4:

Considering the case where the result of ${3n + 1}$ for $n\equiv 1$ is always an even integer, we can rewrite the operation as an expression consisting of three groups where the first term is odd and the second and third terms are even:

$(1 + 3n) = (1 + n) + 2n = (1 + n) + n + n$

Proposition 5: Similarly, considering the case where the result of $\frac{n} {2}$ for $n\equiv 0$ is always an even integer, we can use proposition 3 to derive an additional operation that also expands $n$ into an expression that consists of three groups:

$n = \frac{n + 2}{3} + \frac{n - 1}{3} + \frac{n - 1}{3}$

Remark:

Considering this is an attempt, we currently disregard the constraint that the above intermediate step has to produce integers for every term pending a better mathematical solution. Experimenting with real examples one can reason that proposition 3 is probably true. This intermediate step is complemented by a second step (equation 2) before the division of $n$ by $2$ takes place that does produce an integer result.

Proposition 6:

Let $p$ be a positive odd integer. From proposition 3 and 4 we can split the $n\equiv 1$ outcome of $f(n)$, which returns an even integer $p_e$ into three terms, with one group denoting an even operation ${p + 1}$ and the remaining two groups with odd terms ${p}$. To iterate on the Collatz function we simply add each half of the first even operation to the remaining two odd operations, giving us the following equation with solely two groups of either $odd + odd$ or $even + even$ integers:

Equation 1:

${p + 1} + p + p = \left(\frac{p + 1}{2} + p\right) + \left(\frac{p + 1}{2} + p\right) = \left(\frac{3p + 1}{2}\right) + \left(\frac{3p + 1}{2}\right) = p_e.$

Proposition 7:

For the other case we let $p$ denote a positive even integer. From proposition 3 and 5 we can also split $p$ into three terms, with one group denoting an even operation ${p + 2}$ and the remaining two groups odd operations ${p - 1}$. Similarly to the previous case, we simply add each half of the first even operation to the remaining two odd operations, giving us the following similar expression with solely two groups of either $odd + odd$ or $even + even$ integers:

Equation 2:

$\frac{p + 2}{3} + \frac{p - 1}{3} + \frac{p - 1}{3} = \left(\frac{p + 2}{6} + \frac{p - 1}{3}\right) + \left(\frac{p + 2}{6} + \frac{p - 1}{3}\right) = \frac{p}{2} + \frac{p}{2} = p_e.$

Continuing with the case of even integers we can divide $p_e$ by $2$ and iterate equation 1 or 2 depending on the outcome.

Lemma: Given that both cases of $f(n)$ can be now defined as a summation of one even integer term and two odd integer terms (in the case of proposition 5 solely the numerators for the time being), we can demonstrate with the above equations that the outcome of $3n + 1$ and $\frac{n}{2}$ follows the same principle of equally distributing the first term across the second and third terms as $f(n)$ iterates.

Remark:

Apologies again if the proof is notationally unconventional.

Proof (attempt): From the above, two insights can be derived. Namely (1) it is evident that $f(n)$ is shown to be an iterative process that distributes one set of even cardinality equally across two other sets of odd cardinality. From this insight follows (2) where the outcome $\frac{p_e}{2} \ge p$, thus intuitively showing that divisions by $2$ will $always$ result in a minimum that reaches 1 and consequently repeating the cycle (4;2;1) ad infinitum.

Intuition:

Suppose we have and odd integer $7$ and we apply proposition 4 resulting in $22$. We can use equation 1 to split the integers into the following set of three vectors:

$\begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $

Let us now split the even vector of eight elements into two separate equal sets:

$ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $

We will now add each new set to the existing stack:

$ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $

At any point when we have two equal vectors we can divide by 2, i.e. discard one:

$ \begin{bmatrix} 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \\ 1 \end{bmatrix} $

Because this vector has an odd number of elements (11) we have to apply proposition 4 again and the process repeats eventually reaching 17, 26, 13, 20, 10, 5, 16, 8, 4, 2, 1.

Note that proposition 5 is applied when the quotient is an even integer.

$\endgroup$
15
  • 7
    $\begingroup$ I don't understand the statement of "Theorem 3". $\endgroup$ Dec 28 '19 at 10:54
  • $\begingroup$ For example, 22 = 8 + 7 +7, 34 = 12 + 11 +11, 52 = 18 + 17 + 17, etc. $\endgroup$ Dec 28 '19 at 10:59
  • 5
    $\begingroup$ Well, theorems 1-2 are completely trivial and even boring in any attempt to prove such a hard conjecture, and thus theorem 3, whatever it means (I still can't understand it) cannot be very relevant being a corollary of theorem 2... $\endgroup$
    – DonAntonio
    Dec 28 '19 at 11:09
  • $\begingroup$ Thanks @don basically the intention is state that any even integer is a combination of one even and two odds. 12 is the sum of 4 + 4 + 4 but also 6 + 3 + 3, so a collection of elements can be split into three groups, one even and two odds, and later I explain that using this approach you arrive at a consistent way to iterate the function until it eventually reaches 1. What would you suggest to remove and replace it with statements/definitions and the like? $\endgroup$ Dec 28 '19 at 11:30
  • 2
    $\begingroup$ Why was this downvoted? Assuming this post is totally flawed, does that matter? The OP has made a ton of effort in the body and is asking an honest question. Just trying to understand why the downvote. $\endgroup$ Dec 28 '19 at 20:42
7
$\begingroup$

I share some of the concerns in the comments, in that I don't understand some of the claims. I also think your attempt has some small issues that make it hard to follow. For example, I don't understand lemma 1. Theorem 3 is not technically correct, it only applies to integers greater than or equal to 4, not for any even integer. Also on the issue of theorem 3, I am not sure if you are correct to claim that it follows from theorem 2 (you can prove it trivially for integers greater than 4, but you don't need theorem 2). The latter two statements don't affect your logic directly (I think), but making sure these are accurate would be helpful.

The first major issue in this attempt is that I disagree with your remark; it absolutely matters whether the terms are even/odd (and hence, integers). I don't see any step in your proposed proof which addresses this. Specifically, you use results about the parity of the terms in your proof, without showing that parity is an applicable property to those terms. As a simple example, consider $n = 12$, and notice that $\frac{12+2}{3}$ is not an integer. This really matters, because you use this property to make conclusions about the the parity of $f(n)$. Specifically you end up claiming the result is always the sum of two odd, or two even numbers. This is not correct, since the parity of the terms defining said result are undefined. You also go on to say:

"Since it is now shown that both the even and odd cases undergo an equal operation that results in an even integer we can divide $p_e$ by 2 and continue the Collatz iteration."

Unless I am misunderstanding completely, this is trivially incorrect. In the second case we consider an arbitrary $p$ that has even parity. It is not correct that $f(p)$ then also has even parity. Just consider $p=10$ for example.

Finally I don't follow your concluding remark. For example, when you discuss the case where $p$ is odd, it equivalent to saying $3p + 1 > p + 1$. This is of course true, but it is also entirely trivial. It gives no insight into the convergence of the sequence to $1$. The claim for when $p$ is even is similarly trivial. Perhaps I have misunderstood what you are trying to say here. Ultimately, your final claim:

"ultimately allowing the iteration to reach 1 and consequently repeating the cycle (4;2;1) ad infinitum."

does not follow from the previous statements.

I also tried to understand your section on intuition, and I think I see what you are doing. However, you are simply applying the iterative step, but this doesn't actually give any insight into the convergence of the sequence!

EDIT IN RESPONSE TO OP'S EDITS: Your restructured argument immediately makes some of my criticisms very clear. It is important to note that you are NOT using proposition 3 in proposition 5. In prop 5 you are assuming an arbitrary $n$ of even parity. Consider $n = 14$, and then consider your expression for $n$, $14 = \frac{14+2}{3} + \frac{14-1}{3} + \frac{14-1}{3} = \frac{16}{3} + \frac{13}{3} + \frac{13}{3}$. In this expression, none of those individual terms are integers. Can you see why this is not an application of proposition 3?

Once again, your remark is simply incorrect! It is important to distinguish between gaining a heuristic understanding of a problem, and proving said problem. Probably true simply doesn't cut it! You have either shown it, or you have not, and in this case you have not. Also it is not quite correct when you say "Experimenting with real examples one can reason that proposition 3 is probably true", because this proposition is actually true (just subtract 2 from any even number to see this). Finally, you cannot simply claim that the fact the terms are not integers does not matter. If you use this fact in your proof (which you have), it does matter.

I have tried to read through the rest of the proof, and while the edits have helped make your thoughts a bit clearer, my original criticisms still stand. In fact, I also now see a few more issues. For example, the inconsistencies between what $p_e$ represents between propositions 6 and 7 are confusing. In the former it is the value of $f(p)$, in the later it is $p$. I also dislike the use of sentences such as:

"From the above, two insights can be derived. Namely (1) it is evident that 𝑓(𝑛) is shown to be an iterative process that distributes one set of even cardinality equally across two other sets of odd cardinality"

Terms such as cardinality, sets, and groups (which you've used in your question) have precise mathematical meaning. Your usage of these terms makes the proof really hard to follow.

Ultimately, your main issue with this proof is what I said in my original answer: unfounded conclusions. Your conclusions do not follow from your earlier statements. In your update you even use the word 'intuition'. This does not qualify as proof! Even if all your previous arguments were sound, your final implication in your proof attempt is entirely unjustified.

As I said in the comments, while it can be fun to try to prove such things, you have to understand how deep a problem proving this conjecture is. A 'metapoint' about your proof attempt is that almost everything in it was a trivial statement, or a misuse of those statements. As such it is almost certainly not the case that you will have proved the Collatz conjecture. (And that's no knock on you either!)

$\endgroup$
16
  • $\begingroup$ Thanks @masiewpao for your constructive feedback. I've revamped the entire thing. As you can see I need to learn the lingua franca of communicating such concepts accordingly. To come specifically back to your comments, it is possible to find at least one combination of even + odd + odd for positive integers 8 and below (see above as I've reworded these paragraphs). The first major issue is indeed a current limitation (pending further improvement) with real examples it checks out AFAIK, in any case this is an intermediate step to substantiate the proof. The "Since..." sentence was reworded. $\endgroup$ Dec 28 '19 at 19:28
  • $\begingroup$ On your final remark @masiewpao, I've made it more clear that is $p_e \ge p$ and not 3p + 1 > p + 1. I encourage you to try a couple of examples, hopefully my reasoning is not too far off as to why I believe that the conjecture is true. $\endgroup$ Dec 28 '19 at 19:31
  • $\begingroup$ @FrancisLaclé I haven't had a chance to look at the edits, I will try to do so at some point. My apologies, I should have said 4, not 8; I will edit that. In the case of n = 2 I am sure you can see why this isn't possible. But of course as I said in the answer, this doesn't really affect the overall argument; I was just nitpicking. $\endgroup$
    – masiewpao
    Dec 28 '19 at 20:06
  • $\begingroup$ @FrancisLaclé While I haven't read your edits, I would exercise extreme skepticism at this proof. A general point to note is that almost every step or claim in your original proof was trivial. I don't mean this in a bad way, I say it to mean that it would be truly incredible if this somehow turned out to solve such an incredibly deep problem. Also considering the fact that someone else would almost certainly have seen this before. $\endgroup$
    – masiewpao
    Dec 28 '19 at 20:09
  • 1
    $\begingroup$ I only say this because you mention in your comment you believe the proof to be correct! Just have a healthy does of skepticism. The Collatz conjecture is incredibly deep, far beyond any capacity of my own. My answer was to try to clarify some points on your proof in general. $\endgroup$
    – masiewpao
    Dec 28 '19 at 20:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.