3
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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). $\endgroup$ – Gottfried Helms Jul 12 '18 at 14:56
  • $\begingroup$ Well, second thought: this is completely convincing. Accepted! $\endgroup$ – Gottfried Helms Jul 12 '18 at 14:59

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.