Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The so-called "1-cycle" in the Collatz-problem was already disproved by Ray Steiner 1977. However, he used transcendental number theory to achieve that, and Lagarias commented, it is surprising that such heavy weapons are needed for such a tiny result.
I think I have an elementary proof now but usually in the Collatz-problem your proofs are faulty, so I better ask for a crosscheck. As proposed in the MSE.meta I'll put the problem-description in this question and post my attempted proof in an own answer.

The notion of 1-cycles begin with the definition of increasing steps $a_{k+1} = {3a_k +1\over 2} $ if $a_k$ is odd and decreasing steps $a_{k+1} = {a_k\over 2} $ if $a_k$ is even.
If we consider the simple type of a cycle, which occurs if $N$ increasing steps are followed by $B$ decreasing steps, then let us call this with Steiner, Simons, de Weger and others the "1-cycle" of length $S=N+B$.

With Steiner, we can state, that an initial number a which we wish to increase by N steps must have the form $a = 2^N \cdot k -1$ for any integer $k \gt 0$ . The result of that transformation, let's call it b has then the form $b=3^N \cdot k -1 $ with the same parameter k. If b is then transformed by B decreasing steps and reaches c then c has the form $c={3^N \cdot k\ - 1 \over 2^B}$ If $c=a$ then we have a cycle and this is the "1-cycle".
Now identifying a with c this gives the "critical formula" $$ \tag{1.0} 2^N\cdot k - 1 = {3^N \cdot k -1 \over 2^B}$$ Simply rearranging gives the more focused form which appears (using different letters) in J.Simon's paraphrase of R.Steiner's proof: $$ \tag{1.1} (2^S - 3^N)\cdot k = 2^B - 1 $$ where also $S$ is introduced as $S=N+B$ and $2^S \gt 3^N$ is understood. Then the relevant statement is:

For a 1-cycle of any length $N$ to exist we must have a solution in positive integers $(N,S,B,k,a)$ in eq. (1.1) .

$\qquad \qquad$ (two other useful representations of that critical equation are $$ \small (2^S - 3^N)\cdot k = (2^S - 2^N )/2^N \quad , 2^S \gt 3^N \quad \text{ or }\\ \small 2^B = {2^S\over 2^N}={3^N \cdot k -1 \over 2^N\cdot k-1}$$

Using results of transcendental number theory and rational approximation with linear forms of logarithms Steiner proved, that there is no $2^B$ satisfying that formula except $B=1$,$N=1$,$k=1$ and $ a=1, b = 2 = {3a+1\over 2}, a=1={b \over 2} $ which is called the "trivial cycle".

Question: how can it be proven by elementary means, that the formula (1.1) has not other solutions?

Actually, this question is asking for help: to crosscheck my proof attempt, which I'll state in an answer below.


The Steiner-proof is not online, but John Simons has used it when he extended the Steiner-method for the 2-cycle. His article which contains a paraphrase is online at AMS . Note that I use different letters for the variables to be consistent with my own older discussions

[Added]: Empirically, the last shown form of the critical equation can never be satisfied for $N \gt 1, k \ge 1$ because the rhs falls empirically between the sharp bounds $$ \small {3^N\over 2^N} \lt {3^N \cdot k -1 \over 2^N\cdot k-1} \lt \Big\lceil {3^N \over 2^N} \Big\rceil \qquad \text{ for }K=1 \ldots \infty$$
(and thus is never arriving the next integer above $(3/2)^N$) where the right inequality conforms with that conjectured bound in the Waring-problem, but which is not yet proven.

share|improve this question
    
$S=2$, $N=1$, $B$ arbitrary, $k=2^B-1$ seems to work, so perhaps there are some conditions you have left out. Also $(2^4-3^2)(9)=2^6-1$. –  Gerry Myerson Aug 29 '12 at 2:55
    
No, neither S nor B are arbitrary; S is the number of all divisions of 2 and B is that number minus the divisions by 2 done by the (3x+1)/2-steps. So if N=1 and S=2, then B=S-N=1 . The possible integer solutions of this equation are related to the existent cycles on a=1,k=1,N=1,S=2,B=1, and, extended to the negative integers, a=-1,k=-1,N=1,S=1,B=0 and a=-5,k=-1,N=2,S=3,B=1 –  Gottfried Helms Aug 29 '12 at 8:06
    
You asked for a proof that $(2^S-3^N)k=2^B-1$ has no other solutions. I answered that question. If you meant to ask a different question, you should edit so you're asking the question you actually want to ask. –  Gerry Myerson Aug 29 '12 at 13:27
    
But @Gerry, I wrote already in the first version of this question, that it is meant that $S=N+B$ - in the sentence where I introduced this variable $S$ . Wasn't this explicitely enough for the following? Sorry for any inconvenience... –  Gottfried Helms Aug 29 '12 at 13:58
    
Sorry, I skipped all the introductory stuff and went straight for the question. A question should stand on its own. It could have been worded something like, "prove [equation] has no other solutions, where $S,N,B,k,a$ satisfy relations (17), (18), and (23), above." Then I would have known I had to check a few things. –  Gerry Myerson Aug 29 '12 at 23:09

2 Answers 2

[update2]: It was found, that the given considerations below are not completely sufficient to disprove the existence of a "nontrivial" solution in eq (1.1) and thus the disprove of a nontrivial cycle, as asked for in the question. However some modular restrictions are formulated
(Thanks to Steven to point out the flawed argument)[/update2]


I begin with the formula (1.1) in my question $$ (2^S - 3^N)\cdot k = 2^B - 1$$ We check modular conditions on $k,2^B$ and $3^N$ for compatibility.

We begin assuming there might a solution be existent, where also $2^S = 2^N \cdot 2^B \gt 3^N$ and thus $S \gt N \cdot \log_2 3 \approx N \cdot 1.59 $ and thus $B \gt N \cdot 0.59 $

We look at k first:

  1. Corol.: $k \lt 2^B-1$ for any nontrivial case $N \gt 1$.
    Proof: It is obvious that $ k \le 2^B-1 $ so we check, whether $k = 2^B-1$ . This gives $ (2^S - 3^N)\cdot (2^B - 1) = 2^B - 1$ and then $(2^S - 3^N) = 1 $
    But because consecutive powers of 2 and 3 cannot have the difference 1 except for $2^2$ and $3^1$ we must have
    $ \qquad k \lt 2^B-1 $

  2. Corol.: $k \gt 1 $ for any nontrivial cycle $N \gt 1$
    Proof: Assume $k=1$. Then the equation can be rewritten as
    $ \qquad 2^S - 3^N = 2^B - 1 $
    $ \qquad 2^S - 2^B = 3^N - 1 $
    $ \qquad 2^B \cdot (2^N - 1) = 3^N - 1 $
    We look at N:
    a. if N is even, then the parenthese on the lhs has the primefactor 3 but not the rhs, so N cannot be even
    b. if N is odd, then the parenthese on the rhs has the primefactor 2 only to the first power, so $B=1$ and we're again arriving at the "trivial cycle" as only solution

  3. Corol.: $ 3 \le k \le 2^B-3 $ : the possibility of an integer-solution for the main equation depends on modular restrictions on the residue $3^{-N} \pmod{2^B}$, and thus the possibility of a nontrivial cycle.
    Proof:
    First k cannot be even because $2^B-1$ is odd so $ 3 \le k \le 2^B-3 $.
    Next we write the numbers in modular terms $ \pmod{2^B}$
    $\qquad 2^S = 2^B \cdot 2^N$
    $\qquad 3^N = 2^B \cdot n + r $ with necessarily $ n \le 2^N - 1$
    $\qquad k \equiv 1/r \pmod{2^B}$ because eq (1.1) $(2^S - 3^N)\cdot k=2^B-1$ becomes $ ( - 3^N)\cdot k \equiv -1 \pmod{2^B}$ . (Also it must be smaller than $2^B$)
    We get then
    $$ (2^B \cdot 2^N - (2^B \cdot n + r))\cdot k = 2^B - 1 \\ 2^B \cdot (2^N - n)\cdot k - 2^B = r\cdot k -1 \\ (2^N - n)\cdot k = {r\cdot k -1\over 2^B } +1 $$ In that equation the lhs is always $lhs \ge k$ but the $rhs \le k$ , so this equation can only hold, if both sides equal k.
    3.1) For the lhs this means, that $2^N - n = 2^N - \lfloor 3^N/2^B \rfloor = 1 $
    3.2) For the rhs this means, that k must be a divisor of $2^B-1$ and also it must hold $k \le r$. The proof for that property of the rhs was already given in an earlier post .

Condition 3.1) is not further investigated here.

From 3.2) which was the intended part to disprove the nontrivial 1-cycle generally, we can
at least conclude, that the following holds:

  1. if $2^B-1$ has no divisors (thus is a mersenne prime), or ...
  2. if $ 3^N \lt 3^{-N} \pmod{2^B}$ or ...
  3. if the residue of $ 3^{-N} \pmod{2^B}$ is not a divisor of $2^B-1$ ...

then the associated 1-cycle cannot exist.


Unfortunately the last three conditions are not yet formulated as some function of N, so this elementary approach does not yet allow to exclude infinite classes of 1-cycles (for instance it is not even known, whether the number of Mersenne-primes is infinite)

share|improve this answer
1  
One concern with the last step of your proof: you haven't used the fact that you're dealing with a number of the form $3^N$ at all there. What happens if you just take, e.g., $B=8$, $k=17$, and say $S=10$, $n=3$, $r=241$? It looks like your assumption that the RHS can only equal $k$ under those conditions is wrong, because I don't see any reason, for large $r$, why $(r\cdot k-1)/2^B$ can't equal $k-1$... –  Steven Stadnicki Aug 28 '12 at 15:43
    
Hmm, I should have stated explicitely, that the decomposition of $3^N = 2^B \cdot n + r $ means $ 1 \le r \lt 2^B $. But your example $B=8,S=10$ is invalid because $S=B+N$ and thus $N=2$ but we must have, that $ B \approx 0.59 \cdot N$ by the introduction of my attempt. Possibly you have a special thing in mind and we can take a better example? –  Gottfried Helms Aug 28 '12 at 15:55
    
@Steven: your critique was correct. Rereading my own older post which I just linked to in my answer I find, that the constellation that k is a divisor of $2^B-1$ had slipped away in my current sketch... That makes the rhs equal k and thus we can have a solution when also $2^N-n=1$. I'll see how I can reflect this, perhaps I'll retract my question later... –  Gottfried Helms Aug 28 '12 at 16:09

The proof is a lot simpler than that. Let odd2 be the second odd integer in the sequence and odd1 be the starting point. By definition odd2 = (3*odd1+1)/2^n for some integer n. In a one cycle, odd2 = odd1. Thus odd1 = (3*odd1+1)/2^n Thus, odd1 = 1/(2^n-3) Since odd1 is positive and an integer, and 1 is positive 2^n-3 must be positive and less than/equal to the numerator of 1. Since 2^n-3 is an integer, and so i

share|improve this answer
    
Yes, you are correct for the 1-step-cycle - disproof. Ray Steiner with his "1-cycle" meant the hypothetical construction of arbitrarily many increasing steps $a_{k+1}=(3a_k+1)/2^1$ followed by one single step $a_{k+1}=(3a_k+1)/2^A $ where $A>1$ and odd $a_k>1$. This arbitrariness of length is the reason for the complication in the formula. –  Gottfried Helms Jun 15 at 11:04

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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