1
$\begingroup$

Apologies on the length of this question. I found it surprisingly difficult to take even this baby step with the Collatz Conjecture.

If you see any step that is unclear, please let me know in a comment and I will update.

Let:

  • gcd$(a,b)$ be the greatest common divisor of $a$ and $b$

  • $C(x) = \dfrac{3x+1}{2^w}$ where $w$ is the highest power of $2$ that divides $3x+1$

  • $x_1>1, x_2>1, \dots, x_n>1$ be the sequence of $n$ distinct odd integers for each application of $C(x_i)$ so that:

  • for $i > 1$, $x_i = C(x_{i-1})$
  • $x_i > 1$
  • $C_1(x) = C(x)$
  • $C_n(x) = C(C_{n-1}(x))$
  • for each $x_i$, there exists $w_{x_i,1}\ge 1, w_{x_i,2} \ge 1, \dots w_{x_i,n} \ge 1$ such that:

$$C_n(x_i) = \dfrac{3^n x_i + 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{2^{\left(\sum\limits_{k=1}^n w_{x_i,k}\right)}}$$

Note 1: Details for this equation can be found here.

  • $m \ge n$ be an integer with $m = \sum\limits_{k=1}^{n}w_{x_1,k}$

  • Let integers $c_1 > 0, c_2 > 0, \dots, c_n > 0$ form an n-cycle so that each $c_{i+n} = c_i$

  • $\text{avg}(c_1, c_2, \dots, c_n) = \dfrac{\sum\limits_{k=1}^n c_k}{n}$

Observation:

  • Given an n-cycle: $c_1, c_2, \dots, c_n$, there exists $1 \le k \le n$ such that for all $k \le j < k+n$:

$$\sum\limits_{i=k}^{j} c_i \le \text{avg}(c_1, c_2, \dots, c_n)$$

Argument

  • Base Case: $n=2$: either $c_1 \le \text{avg}(c_1, c_2)$ or $c_2 \le \text{avg}(c_1,c_2)$
  • Assume that $k$ exists for any $n$-cycle up to $n \ge 2$
  • Inductive Case:
  • Let $d_1, d_2, \dots, d_n, d_{n+1}$ be an $(n+1)$-cycle with $d_{n+1+i} = d_i$
  • There exists $1 \le m \le n$ with $d_m < \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$. Otherwise, all values are equal to $\text{avg}(d_1, d_2, \dots, d_{n+1})$ and any $1 \le i \le n$ will serve as $k$.
  • Let $c_1, c_2, \dots, c_n$ be an $n$-cycle such that: $$c_i = \begin{cases} d_i, & i < m\\ d_{i+1}-\text{avg}(d_1,\dots,d_{n+1}) + d_i, & i = m\\ d_{i+1}, & i > m\\ \end{cases}$$
  • Since $c_1, c_2, \dots, c_n$ forms an $n$-cycle, there exists $1 \le k \le n$ such that for all $k \le j < k+n$:

$$\sum\limits_{i=k}^{j} c_i \le \text{avg}(c_1, c_2, \dots, c_n) = \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$

  • Case 1: $k = m$ $$d_k = d_m < \text{avg}(d_1, d_2, \dots, d_{n+1})$$
  • Case 2: $1 \le j \le n$ and $k+j < m$
  • By assumption: $$\sum\limits_{i=k}^{k+j} c_i = \sum\limits_{i=k}^j d_i \le \text{avg}(c_1, c_2, \dots, c_n) = \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$
  • Case 3: $1 \le j \le n$ and $k+j = m$ $$\sum\limits_{i=k}^{k+j} d_i = \left(\sum\limits_{i=k}^{k+j-1} d_i\right) + d_m \le \text{avg}(d_1, d_2, \dots, d_n, d_{n+1})$$
  • Case 4: $1 \le j \le n$ and $k+j > m$ $$\sum\limits_{i=k}^{k+j} d_i = \left(\sum\limits_{t=k}^{k+j-1} c_t\right) - \text{avg}(d_1,d_2,\dots,d_{n+1}) + d_{m} \le \text{avg}(d_1, d_2, \dots, d_{n+1})$$

Question:

Does it now follow that if $x_1, x_2, \dots, x_n$ form an n-cycle, then either $2^{m-1} < 3^n$ or there exists $x_i$ where $x_i < n$

If yes, is there a simpler or more straight forward way to make the same argument?

Argument:

(1) Assume that $x_1, x_2, \dots, x_n$ forms an n-cycle.

(2) For each $x_i$, it follows that:

$$x_i = C_n(x_i) = \dfrac{3^n x_i + 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{2^{\left(\sum\limits_{k=1}^n w_{x_i,k}\right)}}$$

Which implies that:

$$x_i\left(2^{m}-3^n\right) = 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)$$

(3) $2^m > 3^n$

This follows since $2^m - 3^n = \dfrac{3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{x_i}$

Since, clearly: $\dfrac{3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)}{x_i} > 0$

(4) Assume that $2^{m-1} > 3^n$

(5) $2^m - 3^n > 2^m - 2^{m-1} = 2^{m-1}$

(6) The average of each $w_{x_i,k}$ is $\dfrac{m}{n}$ with $2^{\frac{m}{n}} > 3$ since:

  • $m \ln 2 > n \ln 3$
  • $\frac{m}{n}\ln 2 > \ln 3$
  • $2^{\frac{m}{n}} > 3$

(7) Since $x_1, x_2, \dots, x_n$ forms an $n$-cycle, from the Observation above, there exists an $x_i$ such that for each $1 \le u \le n$, $\left(\sum\limits_{k=1}^{u} w_{x_i,k}\right) \le \dfrac{um}{n}$

Note: The argument in the observation is derived from the solution to the well known gas stations on a circular trek problem.

(8) $2^{m-1}n > 3^{n-1} + \sum\limits_{i=1}^{n-1}\left(3^{n-i-i}2^{\left(\sum\limits_{k=1}^i w_{x_i,k}\right)}\right)$ since:

  • $2^{m-1} > 3^{n-1}$ from step(3) above
  • $2^{m-1} \ge 2^{\left(\sum\limits_{k=1}^{n-1} w_{x_i,k}\right)}$
  • $2^{m-1} > 2^{(n-1)\frac{m}{n}} > 3\times2^{\left(\sum\limits_{k=1}^{n-2} w_{x_i,k}\right)}$ since: $\dfrac{m}{n} > 1$ from $2^{\frac{m}{n}} > 3$ and $\frac{m}{n} + (n-1)\frac{m}{n} = m < m-1 + \frac{m}{n}$
  • $2^{(n-1)\frac{m}{n}} \ge 3^2\times2^{\left(\sum\limits_{k=1}^{n-3} w_{x_i,k}\right)}$
  • $\dots$
  • $2^{(n-1)\frac{m}{n}} \ge 3^{n-2}\times2^{w_{x_i,1}}$

(9) $x_i < \dfrac{2^{m-1}n}{(2^m - 3^n)} < \dfrac{2^{m-1}n}{2^{m-1}} = n$


Edit 1:

I found a mistake in my reasoning which led me to change the title slightly and change the question in order to fix the mistake in reasoning.


Edit 2:

I made changes based on comments from John Omielan.

$\endgroup$
4
  • $\begingroup$ I haven't finished reading all of your question yet, but note your "$C_n(x) = C_1(C_2(\dots(C_n(x))\dots))$" is self-referential, and unclear, as stated. For $n=1$, we get $C_1(x) = C_1(x)$. For $n = 2$, we get $C_2(x) = C_1(C_2(x))$, i.e., $C_2(x)$ must be a value so $C_1$ of it returns that value. However, $C_1$ is not explicitly defined. Based on your previous question & the context, I believe you mean $C_n(x)$ is the composition of $C(x)$ $n$ times. One explicit, unambiguous way to state this is "$C_1(x)=C(x)$" and "$C_n(x)=C(C_{n-1}(x)) \; \forall \; n \gt 1$". $\endgroup$ Sep 27 '20 at 0:43
  • $\begingroup$ Your "Note 2" of "Each set of $w_{x_i,1}, w_{x_i,2}, \dots w_{x_i,n}$ will consist of the same set of values with a shifted order ...", plus the later note of "$x_1$ was used but this sum will be the same for all $x_i$" will only necessarily be true if you have an $n$-cycle starting at $x_1$. You don't state this previously as being a requirement, with your question later asking about if we have $n$-cycle. It seems you're implicitly assuming an $n$-cycle initially, so if this is your intent, you should state this then & reword the rest of the question accordingly. $\endgroup$ Sep 27 '20 at 1:09
  • $\begingroup$ You're welcome. Here's one more issue. In your (7) list of bullet points, there's "Since $v_{x_1,1}, \dots, v_{x_1,n}$ is a sequence of $n$ values, by assumption, there exists $j$ where $v_{x_j,1}, v_{x_j,2}, \dots v_{x_j,n}$ have the properties and $\dfrac{\sum\limits_{k=1}^n v_{x_j,k}}{n} = \text{avg}$". However, the assumption is only valid for a set of $n$ positive integers adding to $m$. In your case, this requires $\text{avg} = w_{x_j,l}-w_{x_j,n+1}$, where $\text{avg}$ is as defined earlier, which will usually be false. Also, you don't define it, but I assume $w_{x_j,n+1}=w_{x_j,1}$. $\endgroup$ Sep 27 '20 at 2:03
  • $\begingroup$ @JohnOmielan Great points. I will attempt to revise the argument to address your comments. $\endgroup$ Sep 27 '20 at 2:49
1
$\begingroup$

from $(3+\frac{1}{e_0})(3+\frac{1}{e_1})...(3+\frac{1}{e_n})=\frac{e_{n+1}}{e_0}\prod_{k=0}^n2^{\nu_2(3e_k+1)}$ you can see that for a cycle: $$2^m\leq (3+\frac{1}{x_{min}})^n$$

If you state that $2\cdot3^n<2^m$ than you have

$$2\cdot3^n< (3+\frac{1}{x_{min}})^n$$ $$2^\frac{1}{n}\cdot3<3+\frac{1}{x_{min}}$$ $$x_{min}<\frac{1}{3(2^\frac{1}{n}-1)}<n$$

$\endgroup$
2
  • $\begingroup$ Much simpler! Thanks very much! $\endgroup$ Sep 27 '20 at 9:58
  • $\begingroup$ Also, thanks for the link. Your explanation there of your notation is very helpful. $\endgroup$ Sep 27 '20 at 20:37

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.