34
$\begingroup$

The Collatz conjecture is equivalent to the following "induction principle":

If $P(0) \land P(1) \land (\forall{x} P(3 \cdot x + 2) \implies P(2 \cdot x + 1)) \land (\forall x P(x) \implies P(2 \cdot x))$,

then $\forall x P(x)$.

I am wondering if there are any statements that can be proved using this principle that are not obvious and are not obviously equivalent to the Collatz conjecture itself? I'm not so much interested in open problems (implications of the Collatz conjecture), rather something that may be easily provable a different way but also has a simple proof using "Collatz induction".

I have tried some statements $P(x)$ like "there exists a number of the form $2^a \cdot 3^b$ within a distance $f(x)$ from $x$" but I can't quite make this work.

$\endgroup$
9
  • 1
    $\begingroup$ Why the statement is not $P(0) \land P(1) \land (\forall x: P(3 x + 2) \implies P(2 x + 1)) \land (\forall x: P(\mathbf{2 x}) \implies P(\mathbf{x}))$ ? Is it equivalent? For the distance, it seems to me that for most (not for all) elements $x$ : $P^x(x) = 1$ or $2$. In this graph you can see some exceptions: opimedia.be/3nP1/T_100.pdf . (I made this few years ago, so I don't remember details.) $\endgroup$
    – Olivier Pirson
    Aug 12, 2015 at 22:05
  • $\begingroup$ I think you are misunderstanding a few different things. If you reverse the implication arrow in the last clause, it is not equivalent. $P(x)$ denotes an arbitrary predicate, not the Collatz function, so it doesn't make sense to say $P^{x}(x)$. And I am not concerned here about bounds on stopping time anyway, I am just looking for an example of of a statement that can be proved this way. $\endgroup$
    – Dan Brumleve
    Aug 13, 2015 at 21:34
  • $\begingroup$ Yes, I don't understand. Have you references to this equivalence result? $\endgroup$
    – Olivier Pirson
    Aug 13, 2015 at 22:14
  • 1
    $\begingroup$ It is like ordinary induction but instead of starting at $1$ and counting up, start at $1$ and follow the Collatz function backwards. If the Collatz conjecture is true then we can reach every number that way, and if the truth of the predicate at each step is implied by the the previous step then the predicate is universally true. I'm not sure how to make it any more clear. $\endgroup$
    – Dan Brumleve
    Aug 13, 2015 at 22:21
  • $\begingroup$ For the other direction, note that if the Collatz conjecture fails we can construct a not-universally-true predicate that still satisfies the induction conditions (just define it to be false on a non-trivial cycle or non-terminating chain and true elsewhere). But that doesn't mean that every statement provable this way implies the CC. $\endgroup$
    – Dan Brumleve
    Aug 13, 2015 at 22:41

1 Answer 1

Reset to default
1
$\begingroup$

Here is the best I'm able to do so far, following up on my idea in the comments:

Let $P(x)$ be the claim that any set of $x$ integers can be ordered in a sequence $s_i$ with $1 \le i \le x$ such that if $a \lt b \lt c$, then $s_a + s_b \ne s_c$.

Suppose $S$ is a set containing $2 \cdot x$ integers. We have $S = V \cup W$ where $V$ contains the $x$ smallest elements of $S$ and $W$ contains the $x$ largest elements of $S$. If $V$ and $W$ each correspond to a sequence with the property then we can make a sequence for $S$ by starting with $W$'s sequence and appending $V$'s sequence to it. So $\forall x P(x) \implies P(2 \cdot x)$.

If a set can be ordered in such a way so can all of its subsets: to find a sequence for a set after having removed some elements, simply remove those same elements from the original set's sequence. So if $y < x$ then $P(x) \implies P(y)$, and in particular this gives $\forall x P(3 \cdot x + 2) \implies P(2 \cdot x + 1)$.

Therefore if the Collatz conjecture is true, $\forall x P(x)$.

Now this is disappointing because it is just a long-winded way of saying sort the set from highest to lowest, also it proves much more than $P(3 \cdot x + 2) \implies P(2 \cdot x + 1)$. Maybe a starting point for a better example.

$\endgroup$

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.