How is this set of solutions for exponential diophantine equations been found?(Generalized Collatz mx+1, 2-odd-step-cycle)

Question

I'm doctoring many weeks on the problem of the existence and set of solutions of 2-step-cycles in the generalized Collatz-problem, written in the Syracuse-form: $$ Y_m(a): b = {ma+1 \over 2^A} \qquad\qquad a,b,m \in Z \text{ odd }, A =\nu_2(ma+1) $$ We discuss the existence of 2-step-cycles of the form $$ b = {ma+1 \over 2^A } \qquad a = {mb+1 \over 2^B } \qquad \qquad B =\nu_2(mb+1) $$ To see, for which numbers $m,a,b$ solutions exist, I've constructed an equation $$ a \cdot b = ({ma+1 \over 2^A })({mb+1 \over 2^B }) \\ 2^{A+B} = (m+{1 \over a })(m+{1 \over b }) $$ $$ 2^S = (m+{1 \over a })(m+{1 \over b }) \qquad \qquad \text{always } S = A+B \tag 1 $$ $$ \small \text{Note: this equality is necessary but -in the generalized version $mx+1$ } \\ \small \text{with $m \in \mathbb Z /2\mathbb Z$ - not sufficient to have a 2-step-cycle defined.} $$ I was unable to solve this problem in general. To get a clue, I reduced complexity, assuming $a=1$ and $b \ne 1$. Still I could only solve the further reduced problem with $b=3$, finding that $m=5$ is required, (and $S=5, A=1, B=4$ follows) and that this is the only solution.

Reduced, but still unsolvable for me so far: $$ 2^S=2\cdot 4^T = (m+1)(m+{1 \over b }) \qquad \qquad \text{always } S = A+B =2T+1 \text{ odd} \tag 2 $$ What I can do so far, is, that $m$ is odd, so $m=2m'+1$ and $m'+1$ must be a multiple of $b$ such that for instance $m'+1=k \cdot b$ with some $k$ and we get $$ 2\cdot 4^T = (2m'+2)(2m'+1+{1 \over b }) \\ 2\cdot 4^T = 2(m'+1)(2m'+1+{1 \over b }) \\ 4^T = (m'+1)(2m'+1+{1 \over b }) \\ $$ getting $$ 4^T = k\cdot(2b(m'+1)-b+1) = k\cdot(2kb^2-b+1) \tag 3 $$ Here $k$ must be a perfect power of $2$.
But now, fiddling starts and I don't get progress...

Today I fed this problem, leaving $b$ indeterminate, to Wolfram Alpha and got the following set of solutions:

W/A:    m=11  S=7  b=-3  (m'=5  T=3)    check   128=2∙6∙(10+1+1/-3)=4∙(33-1)
W/A:    m=-3  S=3  b=-1  (m'=-2 T=1)    check   8=2∙-1∙(-3+1/-1)
W/A:    m=3   S=3  b=-1  (m'=1  T=1)    check   8=2∙-2∙(-3+1)
W/A:    m=5   S=5  b=3   (m'=2  T=2)    check   32=2∙3/3∙(15+1)

Hmm. Not only W/A found this solutions, it seems this are also all possible solutions. (Note, btw, that the solution with $m=11$ is a solution for (eq 2) but $b=-3$ is not actually an iteration of $a=1$, so in fact it is of course not a solution in this problem.)

My question: How can this result be derived in this generality? And how is it then determined that the set of solutions is finite?

Answer 1

$a=1$.

$2^S= (m+1)(m+\dfrac{1}{b})\qquad\overset{1+2^{S+2}\to k}{\implies}\qquad(k b - 1)^2 - k (2 b m + b + 1)^2=1-k$

This like as Pell equation with given $k$ and unknowns $b,m$.

gp-code:

abms()=
{
 for(s=1, 40,
  k= 1+2^(s+2);
  if(!issquare(k),
   D= k; C= 1-k;
   Q= bnfinit('x^2-D, 1);
   fu= Q.fu[1]; \\print("Fundamental Unit: "fu);
   N= bnfisintnorm(Q, C); \\print("Fundamental Solutions (Norm): "N"\n");
   for(i=1, #N, ni= N[i];
    for(j=0, 4,
     sol= lift(ni*fu^j);
     X= abs(polcoeff(sol, 0)); Y= abs(polcoeff(sol, 1));  
     if(X^2-D*Y^2==C,
      forstep(signx=-1, 1, 2, forstep(signy=-1, 1, 2,
       b= (signx*X+1)/k;
       if(b & b==floor(b),
        m= (signy*Y-b-1)/2/b;
        if(m==floor(m),
         print("("s", "b", "m")")
        )
       )
      ))
     )
    )
   )
  )
 )
};

Output $(S,b,m)$:

(2, 1, -3)
(2, 1, 1)
(3, -1, 3)
(3, -1, -3)
(4, 1, -5)
(4, 1, 3)
(5, 3, 5)
(5, 3, 5)
(6, 1, -9)
(6, 1, 7)
(7, -3, 11)
(8, 1, -17)
(8, 1, 15)
(10, 1, -33)
(10, 1, 31)
(12, 1, -65)
(12, 1, 63)
(13, -45, -91)
(13, -45, -91)
(14, 1, -129)
(14, 1, 127)
(16, 1, -257)
(16, 1, 255)
(18, 1, -513)
(18, 1, 511)
(20, 1, -1025)
(20, 1, 1023)
(22, 1, -2049)
(22, 1, 2047)
(24, 1, -4097)
(24, 1, 4095)
(26, 1, -8193)
(26, 1, 8191)
(28, 1, -16385)
(28, 1, 16383)
(30, 1, -32769)
(30, 1, 32767)
(32, 1, -65537)
(32, 1, 65535)
(34, 1, -131073)
(34, 1, 131071)
(36, 1, -262145)
(36, 1, 262143)
(38, 1, -524289)
(38, 1, 524287)
(40, 1, -1048577)
(40, 1, 1048575)

But if $k$ is square, then need other method of solving as difference of squares.

---

$a\neq1$.

$2^S= (m+\dfrac{1}{a})(m+\dfrac{1}{b})\qquad\overset{1+a^22^{S+2}\to k}{\implies}\qquad(k b - a)^2 - k (2 a b m + a + b)^2=a^2(1-k)$

or

$2^S= (m+\dfrac{1}{a})(m+\dfrac{1}{b})\qquad\overset{a\to u+v\\b\to u-v}{\implies}\qquad \Bigl((m^2 - 2^S) u + m\Bigr)^2 - \Bigl((m^2 - 2^S) v\Bigr)^2 = 2^S$

i.e. for given $S$ set of triples $a,b,m$ is finite.

gp-code:

abms()=
{
 for(s=1, 100,
  k= 2^s;
  T= thue(thueinit('x^2-1, 1), k);
  for(j=1, #T,
   X= T[j][1]; Y= T[j][2];
   if(X, if(Y,
    D= divisors(Y);
    for(i=1, #D,
     v= D[i]; m2= Y/v+k;
     if(issquare(m2),
      forstep(signm=-1, 1, 2,
       m= signm*sqrtint(m2);
       u= (X-m)/(m2-k);
       a= u+v;
       b= u-v;
       if(a==floor(a) & b==floor(b),
        print("("s", "a", "b", "m")")
       )
      )
     )
    )
   ))
  )
 )
};

Output $(S,a,b,m)$:

(3, 1, -1, -3)
(3, -5, -7, 3)
(3, 7, 5, -3)
(3, 1, -1, 3)
(5, 3, 1, 5)
(5, -1, -3, -5)
(7, 3, -1, -11)
(7, 1, -3, 11)
(13, 1, -45, -91)
(13, 45, -1, 91)
(15, 611, 27, 181)
(15, 99, 35, 181)
(15, -35, -99, -181)
(15, -27, -611, -181)

Answer 2

This is how far my own approach brought me. Don't know whether this road arrives at its goal, though...

First I show, that for each $S$ there is a finite (and small) number of solutions. From (eq 1) in my question, $$ 2^S = (m+\frac1a)(m+\frac1b) \tag 1 $$ we can derive an upper bound for $a$. First we do not loose generality, if we fix $a<b$ so there is some mean value $a_m$ in between, which also satisfies $$ 2^S = \left(m+\frac1{a_m}\right)^2 \tag 2 $$ and $$ a_m = {1\over 2^{S/2}-m} \tag 3 $$ Next we find that $m$ (being odd) is uniquely determined by a given $S$.

• ($S$ even:) We see in (eq 2) , that if $S=2T$ is even, then $2^{T}$ is a perfect power of $2$ and $2^T - \frac1{a_m}=m \le 2^T-1$. $m$ must be smaller than $2^T$ and because it must be integral we have, that $m=2^T-1$ .
  By this $m$ is automatically odd, and then $\frac1{a_m}=1=a_m$ , and it follows $a=b=1$. Thus we have the trivial cycle of one odd step, and no ("primitive") two-step-cycle exists.

• ($S$ odd:) If $S=2t$ is odd, we have still from (eq 2) $2^{t}-\frac1{a_m} = m \gt 2^t-1$ but now we have a unique integer between $2^t$ and $2^t-1$ which is then $m$ by which we have: $m=\lfloor 2^t \rfloor $ . Here it can happen, that $m$ is even, and in this case that odd $S$ has no 2-step-cycle in $b>a>0$ integer.

So we know, we need only look at a subset of the odd $S$ whose elements allow $m$ being odd. On the other hand, there is no reason to assume that this subset is finite, so we must consider that we have to check an infinite number of $S$ - if we don't find one better argument against the existence of 2-step-cycles for $S \gt S_0$ with some $S_0$ a large value.

To actually find some 2-step-cycle with integer $0<a<b$ we have the crude upper bound $a \lt a_m$ in (eq 3), which heuristically is often small, even in most cases allow only $a=1$ as possible candidate. In other cases, if for some odd $S=2t$, the distance $2^t-m=\frac1{a_m}$ is small, we have a large $a_m$ and thus a large upper bound for $a$ and our consecutive checking for odd $a$ in the range $1..a_m$ needs still finite, but for (surely) infinitely many large $S$ also unmanageable long time for the checking. Because the runlength of consecutive zeros in the binary representation of $\sqrt 2$ determine the value of $a_m$ and that runlengthes are unbounded when we walk into that infinite bit-sequence we can expect arbitrary large $a_m$, at least bounded by some function on $S$. (For that latter functional bound I've not seen anything in literature and have only some numerical tests up to $S$ of some million, done on my own.)

Well, I've found some options to reduce the range $1..a_m$ as searchspace for $a$ : having some nontrivial lower and upper bounds in that range. But this alone does not allow to assume something like a lower bound for $S$ , above which no more 2-step-cycle can occur.

So surely one must go back to and deeper into the algebraical properties in (eq 1) to find a general statement about the existence of 2-step-cycles in the $mx+1$-problem. So, the "fiddling" as mentioned in my question-text, began/begins... (So that's my surprise that the W|A-result seems to suggest, that they have something like this)