An argument that the value of m in a Collatz conjecture 2-cycle is subject to the same constraints as for a 1-cycle.

195 Views Asked by At

Question: Is the reasoning of the following argument valid?

Objective: To derive a constraint on the permissible number of total divisions by 2, here referred to as $m$, for a Collatz 2-cycle consisting of n elements.

Hypothesis: The total number of divisions by two in traversing a Collatz conjecture 2-cycle containing n elements is constrained by $nln_23<m<nln_23+1$, as it is for a 1-cycle.

Proposed strategy of argument: Show that if m is > $nln_23+1$ then $2^m-3^n>3^n$, and this number, when used in the denominator describing a 2-cycle, is too large to produce an allowable smallest element of the 2-cycle.

Motivating background and example:

In order for there to be a non-trivial loop that satisfies the conditions of 3x + 1 Collatz conjecture, there must be a set of positive integers n, m, f, and $X_1$ that satisfies the equation $$\frac{3^nX_1+f}{2^m}=X_1\tag{1}$$ where f is a sequence that is determined by the pattern of repeated divisions by two as the loop is traversed. We can re-write this equation as $$\frac{f}{2^m-3^n}=X_1\tag{1a}$$For a 1-cycle, $f=3^n-2^n$, which is also equal to $$3^{n-1}+3^{n-2}(2)+3^{n-3}(2^2)+...+2^{n-1}\tag{2}$$As an explicit example, and for a reference in the following discussion, for a 1-cycle and n=10,$$f=3^9+3^8(2)+3^7(2^2)+3^6(2^3)+3^5(2^4)+3^4(2^5)+3^3(2^6)+3^2(2^7)+3(2^8)+2^9\tag{2ex}$$

Argument: (1) If $m>n\frac{ln3}{ln2}+1$ then $2^m-3^n>3^n$.

Let $m=n\frac{ln3}{ln2}+1+\epsilon$, where $\epsilon$ is a positive real number. So $$2^m-3^n=2^{n\frac{ln3}{ln2}+1+\epsilon}-3^n=2^{(1+\epsilon)}3^n-3^n>3^n$$

From this we conclude that $$2^{m_c}-3^n>3^n\tag{3}$$ where the subscript c indicates that $m>n\frac{ln3}{ln2}+1$, and we want to show that this condition is incompatible with a 2-cycle. That is, we want to show that if $\frac{f}{3^n}$ is too small to yield permissible values of $X_1$, then so is $\frac{f}{2^{m_c}-3^n}$

To demonstrate the concept, we consider the case of a 1-cycle. We show that there are no values of mc that satisfy $$\frac{3^n-2^n}{2^{m_c}-3^n}$$Since $2^{m_c}-3^n>3n$,$$\frac{3^n-2^n}{2^{m_c}-3^n}<\frac{3^n-2^n}{3^n}=\frac{3^n}{3^n}-\frac{2^n}{3^n}<1$$Therefore, there are no mc that satisfy the constraints of a 1-cycle, and m is bounded by $n\frac{ln3}{ln2}<m<n\frac{ln3}{ln2}+1$.

(2) To adapt the above reasoning to 2-cycles, we modify equation (2). In a 2-cycle with n elements, $$f=3^{n-1}+3^{n-2}(2)+...3^{n-d-1}{2^{d+l}}+3^{n-d-2}(2^{d+l+1})+3^{n-d-3}(2^{d+l+2}+...+2^{n-1+l}\tag{4}$$where $d$ is the number of elements preceding the first consecutive division by 2, and $l$ is the number of additional divisions at that point in the cycle, i.e., the relative length of the descent which occurs between the largest and smallest $X_i$ in the cycle.

To illustrate this, consider a 2-cycle with 10 elements, with 2 additional, consecutive divisions by 2 occurring after multiplying the 4th element by 3, adding 1 and dividing by 2; $d$=4 and $l$=2. In this case, $$f=3^9+3^8(2)+3^7(2^2)+3^6(2^3)+3^5(2^6)+3^4(2^7)+3^3(2^8)+3^2(2^9)+3(2^{10})+2^{11}\tag{4ex}$$Now we can separate this sequence into those terms that include the $l$ in the powers of 2 and those that do not: $$f=[3^9+3^8(2)+3^7(2^2)+3^6(2^3)]+[3^5(2^6)+3^4(2^7)+3^3(2^8)+3^2(2^9)+3(2^{10})+2^{11}]\tag{4a.ex}$$We note that the two portions of the sequence are of the form $$3^x(3^y-2^y)\tag{5}$$ for the first part of the sequence and $$2^w(3^z-2^z)\tag{6}$$ for the second part. Specifically, equation (4ex) can be written $$3^6(3^4-2^4)+2^6(3^6-2^6)$$ In general, in equation 5,$$x=n-d$$$$y=d$$For equation (6)$$w=d+l$$$$z=x=n-d$$We can write the f for any 2-cycle in this form, with 2 terms. Now the first term is less than $3^n$ because $3^x3^y=3^n$, and then we subtract $3^{n-d}2^d$. Therefore the first term divided by $3^n$ will be less than 1. The same is true of the second term, although showing this is a little trickier. $l$ is related to $d$ as $$2^{l+d}<3^d\tag7$$. This is because the elements in a 2-cycle must form a well-ordered set; one value must be the smallest. We can define the smallest element in a loop as $X_1$. If too many successive divisions by two occur too early in the cycle, we will have an $X_i<X_1$. For example, if we do 3 successive divisions by 2 after multiplying the second element by 3 and adding 1, we get $$X_1$$$$X_2=\frac{3X_1+1}{2}$$$$X_3=\frac{9X_1+5}{16}$$ which is less than $X_1$ for all positive $X_1$.

For a 2-cycle with $m=m_c$ we end up with $X_1$ being the sum of two terms, both of which are less than 1, so any $X_1$ would be less than 2. Therefore, for a 2-cycle, m is constrained by $n\frac{ln3}{ln2}<m<n\frac{ln3}{ln2}+1$.

(3) There is another, related approach that may be more amenable to k-cycles greater than 2. Instead of writing $f$ as in equation (4) we can instead write it as $$(3^n-2^n) + R\tag{8}$$where R is the increment to the $f$ of a 1-cycle with the same number of elements due to the additional divisions by two that occur before the peak of the cycle. In our example, equation (4ex) can be written as $$(3^{10}-2^{10}) + R\tag{8a}$$ where R is equal to$$3^5(2^6-2^4)+3^4(2^7-2^5)+3^3(2^8-2^6)+3^2(2^9-2^7)+3(2^{10}-2^8)+(2^{11}-2^9)\tag{8a.ex}$$We can factor out the lower power of two from each term and get$$3^5(2^4)(2^2-1)+3^4(2^5)(2^2-1)+3^3(2^6)(2^2-1)+3^2(2^7)(2^2-1)+3(2^8)(2^2-1)+2^9(2^2-1)$$This becomes $$(2^2-1)(2^4)(3^5+3^4(2)+3^3(2^2)+3^2(2^3)+3(2^4)+2^5$$which is $$(2^2-1)(2^4)(3^6-2^6)$$This is, in general, $$(2^l-1)(2^d)(3^{n-d}-2^{n-d})$$

Now in the case of the example, we already know that $\frac{(3^n-2^n)}{3^n}$, from the first term in (8a) is less than 1. For the second term we can rewrite $3^n$ as $3^d3^{(n-d)}$. Dividing R by $3^n$ gives $$(\frac{2^{l+d}-2^d}{3^d})(\frac{3^{n-d}-2^{n-d}}{3^{n-d}})\tag{9}$$ Using (7) we see that both factors are less than 1, their product will be less than 1, and $\frac{f}{3^n}$ will be less than 2.

In the example, we would have$$\frac{3^{10}-2^{10}}{3^{10}}+(\frac{(2^6-2^4)}{3^4})(\frac{3^6-2^6}{3^6})=X_1$$As before, for a 2-cycle, we get an $X_1$ that is the sum of two terms, each of which is less than 1. Their sum would be less than 2 (and computes to approximately 1.523226), so there can be no 2-cycles with $m=m_c$.

Conclusion: For a 2-cycle, m is constrained by $n\frac{ln3}{ln2}<m<n\frac{ln3}{ln2}+1.$

Surmise: For a three cycle, $f$ can be decomposed into three terms analogous to the above. Dividing each by $3^n$ will give impermissibly small values for $X_1$. In general, the $f$ for a k-cycle will consists of k terms, one of the form $3^p(3^q-2^q)$ and k-2 terms of the form $2^{r_i}3^{s_i}(3^{t_i}-2^{t_i})$, and 1 term of the form $s^{u_i}(3^{v_i}-2^{v_i})$, i=1, 2,..., k-1. The last element of $f$ for a k-cycle can be no larger than $2^{m-1}$. For large k, $m$ may not be constrained as for 1-cycles.

1

There are 1 best solutions below

0
On

Indeed, and if you extend to a k-cycle you would obtain the Corollary 5 in Simons m-cycles which is $$\Lambda<\frac{k}{X_1} $$

If you start with ($a_i$ and $b_i$ being respectively the number of multiplication by 3 (+1), and the number of division by 2 in cycle i)

$$f=\sum\limits_{j=1}^k (3^{a_j}-2^{a_j})3^{\sum_{i=j+1}^k a_i}\cdot 2^{\sum_{i=1}^{j-1} b_i}$$ and you consider that $2^{\sum_{i=1}^{j-1} b_i}<3^{\sum_{i=1}^{j-1} a_i}$ for $j$ up to $k$ (which, I agree is an unproven shortcut) you would get $$f=X_1(2^m-3^n)<\sum\limits_{j=1}^k3^n=k\cdot3^n$$ $$\frac{2^m}{3^n}-1<\frac{k}{X_1}$$ $$\Lambda=m\cdot log (2)-n\cdot log(3)<\frac{2^m}{3^n}-1<\frac{k}{X_1}$$

From here, there are 2 parts in your development:

showing that $2^{\sum_{i=1}^{j-1} b_i}<3^{\sum_{i=1}^{j-1} a_i}$ for $j$ up to $k$ (your equation $(7)$ extended to k-cycle).

This is tricky because in $X_{p+1}=\frac{3^p\cdot X_1+f}{2^q}$, you can show that $X_{p+1}<X_1 \Rightarrow 2^q>3^p$ and $X_{p+1}>X_1 \Leftarrow 2^q<3^p$ but not (at least in a straightforward way) that $X_{p+1}>X_1 \Rightarrow 2^q<3^p$ (e.g. $8=\frac{3^5\cdot 7+347}{2^8}$)

Perhaps with some kind of recurrence, like you did.

The second part is

using $(2^m-3^n)>3^n$ and the resulting $X_1<k$ to show that $m<n\frac{ln3}{ln2}+1$, at least up to some known bounds on $k$ and/or $X_1$