# In the $mx+1$-problem: headache with a lower bound for the minimal element of a cycle …

I'm trying to optimize my search-routine for cycles in the $mx+1$-problem and seem to have a knot in my brain trying to make sure a certain lower bound for the minimal member $a_1$ is reliable.

My notation is $$a_{k+1}=\text{oddpart}(m \cdot a_k + 1)= {m \cdot a_k + 1\over 2^{A_k} } \tag 1$$ $\qquad \qquad$ with the odd numbers as domain for $a_k$ and with the exponents $A_k \ge 1$ such that the resulting values become odd again. I'm testing for $m \in \{3,5,7,9,11,...\}$ from the positive odd numbers.

Let us use the letter $N$ for the number of exponents (resp. of odd steps), and $S$ for the sum of the exponents, then $m^N$ and $2^S$ are the largest perfect powers getting involved in a given problem; when $N$ and $m$ is given, then $S$ can be determined as $S=\left \lceil N \cdot \log_2(m) \right \rceil$ . (To use the ceil-function makes sure the domain for the $a_k$ is the positive odd numbers, taking the $\lfloor \cdot \rfloor$ instead we'd work on negative $a_k$)

Of course it is impossible to check infinitely many $a_k$, whether they are leading elements of a cycle, by looking at their trajectory of $N$ transformations. But it is possible to reduce the search space drastically by lower and upper bounds for the minimal element, which we always want to assume to occur in $a_1$.

A basic ansatz gives a safe lower and upper bound for $a_1$ but I have now a second one, which gives often a higher lower bound (and thus a reduced search interval) but I'm getting a bit confused, or unsure, when I try to argue that this new lower bound is reliable.

Thus my question is: is the estimate by the second ansatz a true lower bound for $a_1$?

Background: I'm writing the (trivial) equality of two products for a projected cycle with given $m$ and $N$ and resulting $S=\lceil N \cdot \log_2 m\rceil$ and the exponents $A_k$ satisfying $S=A_1+A_2+ \ldots + A_N$ as $$a_2 \cdot a_3 \cdot \ldots a_N \cdot a_1= {m \cdot a_1 + 1\over 2^{A_1} } \cdot{m \cdot a_2 + 1\over 2^{A_2} } \cdot \ldots \cdot{m \cdot a_N + 1\over 2^{A_N} }$$ which is rearranged $$2^S = (m+{1\over a_1}) \cdot (m+{1\over a_2}) \cdot \ldots \cdot(m+{1\over a_N}) \tag 2$$

Ansatz 1: Assume all $a_k$ are equal, namely some value $\alpha$ (where that $\alpha$ were roughly a mean value for the $a_k$), then we can write $$2^S = (m+{1\over \alpha})^N$$ or $$\alpha = {1\over 2^{S/N} - m } \tag {3.1}$$ With $\alpha$ being somehow an average value we necessarily have one or more values $a_k$ smaller and some values $a_k$ larger than that $\alpha$, so $\alpha$ is a very simple upper bound for the minimal element $a_1$ of an assumed cycle. Moreover, since all $a_k$ are integer and must be odd we could define $$a_1 \le \text{oddfloor}(\alpha) \tag {3.2}$$ where $\text{oddfloor}(x)$ means the largest odd integer below $x$.

Example: We set $N=3$,$m=5$ and get from this $S=7$ . We get $\alpha = 25.198$ and thus $a_1 \le 25$ . That means, only for odd values $1 \le a_1 \le 25$ I need to check whether their trajectories are cyclic in $N$ steps.

After having a rough upper-bound for $a_1$ there is one simple argument to increase the lower bound above the trivial $1 \le a_1$: because if we assume that all except $a_1$ have the maximal value $a_{k, k=2..N} = \infty$ then we can determine the resulting $a_{min}$ by $$2^S = (m+{1 \over a_{min}})\cdot(m + 0)^{N-1} \\ {2^S \over m^{N-1}} - m = {1 \over a_{min}} \\ a_{min} = {m^{N-1} \over 2^S - m^N } \tag {3.3}\\$$ which in our example gives $a_{min} = 25/3 \approx 8.333$ and because $a_1$ must be odd and larger than $a_{min}$ we get $$9 \le a_1 \le 25 \tag{by Ansatz 1}$$

Ansatz 2: with question: is the lower bound by this reliable?

In the previous I estimate the lower bound by assuming all $a_2 \ldots a_N = \infty$. Of course that assumption should be improved - there should be a maximal possible element $a_j$ directly determinable by $a_1$, $N$ and $m$.
It is immediate to see, that if all transformations except the last divide only by $2^1$ then the trajectory grows maximally. So we assume $A_1 \ldots A_{N-1} =1$ and $A_N = S-(N-1)$ . The equality of that $A_k$ allows a compact formula to determine $\alpha_1$ which solves for equality in eq. $(2)$ and is in most cases of fractional value.
We get $$\alpha_1 = { m^N - 2^N\over 2^S - m^N }{1\over m -2} \tag {4.1}$$ which in our example gives $\alpha_1 = 13$ and thus $$13 \le a_1 \le 25 \tag{by Ansatz 2 (4.2)}$$ Accidently this value $13$ is already the minimal element of an actual cycle!

So the idea of ansatz 2 reduces (in many relevant cases) the interval for expectable $a_1$ to be tested. It does so because we assume the somehow widest-spread distribution of the $a_k$ which should lead to a definitive minimal (possibly fractional) element $\alpha_1$ compatible with equality to $2^S$ getting $$\text{oddceil}(\alpha_1) \le a_1 \le \text{oddfloor}(\alpha) \tag {4.3}$$

My question again: is some other distribution (of course with less spreaded ) $a_k$ thinkable which leads to a smaller $\alpha_1$ and thus smaller lower bound for $a_1$ (which would destroy this ansatz)? Or is this ansatz safe?

I lack reputation to comment, but I have the following observation: for a fixed $$S$$ and $$N$$, we have an explicit lower-bound for a minimal element.
A "Bohm-Sontacchi" argument yields the following expression for an arbitrary periodic iterate $$a$$: $$a = \frac{\sum_{0\leq w < N}m^w2^{S'_w}}{2^S-m^N},$$ where the $$S'_w$$ are partial sums of the terms in $$(A_1,\ldots A_{N-1})$$. This value is minimized when $$A_1 =\cdots= A_{N-1} = 1$$, and thus $$S'_w = N-1-w$$ (as you have observed--this can be interpreted as the perigee (ref. Belaga, Mignotte) of a "1-cycle" of Steiner in this $$mx+1$$ setting).
Thus, the inequality $$a \geq \frac{\sum_{0\leq w < N}m^w2^{N-1-w}}{2^S-m^N} = \frac{\frac{m^N-2^N}{m-2}}{2^S-m^N}$$ holds, and it is tight.
• Ah, thanks for the reminding of the formula for $a$. Of course I know this formula, but it looks very good to formalize my setting. Addition: for the 1-cycle-analysis in the $3x+1$-problem it is moreover helpful that the $a_{min}=a_1$ must -by modular considerations- have a structure like $k \cdot 2^A-1$ which pushes the list of possible candidates of $a_1$ in such high regions that it is impossible for any such 1-cycle to exist. Unfortunately I cannot exploit that process for $m\ge5$, because there are more than one value in exponent $A_k$ which allow the trajectory to grow (ok: slower). – Gottfried Helms Jul 12 '18 at 14:56