Cycle lengths and member sizes when k > ceiling(x log 3)

General
1

Let’s show

  1. Every rational cycle with k= \lceil x \log_2 3 \rceil + b, where b\geq 1, has some member less than \cfrac{x}{(b+1)\ln 2}.

  2. Any rational cycle with k= \lceil x \log_2 3 \rceil + 1 must have at least 3.2 \cdot 10^{21} odd members.

k = length of cycle
x = total number of odd terms in cycle

For every (k,x)-cycle v, its smallest member f(v) is less than f(v_h), the smallest member of the (k,x)-high-cycle.

f(v) \leq f(v_h) = \cfrac{\beta(v_h)}{2^k-3^x}

The parity vector for the smallest member of the high cycle has ones distributed evenly throughout the zeroes, giving

f(v_h) = \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^k-3^x}

Now consider the case where k= \lceil x \log_2 3 \rceil + b, where b\geq 1. As b goes up, the denominator increases faster than the numerator. Plugging in for k, we get

f(v_h) = \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^k-3^x}

= \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^{\lceil x \log_2 3 \rceil + b} - 3^x}

\leq \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^{x \log_2 3 + b} - 3^x}

= \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{3^x\,2^b - 3^x}

= \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{3^x(2^b-1)}

Note that if b=0, the algebra doesn’t work, producing division by zero.

Turning to the numerator,

f(v_h) = \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{\lceil x \log_2 3 \rceil + b}{x}\,i \rfloor}}{3^x(2^b-1)}

< \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\frac{x \log_2 3 + b + 1}{x}\,i}}{3^x(2^b-1)}

= \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{i\,\log_2 3} 2^{\frac{i(b + 1)}{x}}}{3^x(2^b-1)}

= \cfrac{3^{x-1} \sum_{i=0}^{x-1} [2^{\frac{b + 1}{x}}]^i}{3^x(2^b-1)}

= \cfrac{3^{x-1} \frac{2^{b + 1}-1}{2^{\frac{b+1}{x}}-1}}{3^x(2^b-1)}

The next step uses the identity 2^t-1 > t \ln 2 for t>0, with t=\frac{b+1}{x}.

f(v_h) < \cfrac{3^{x-1} (2^{b + 1}-1) \frac{x}{(b+1) \ln\,2}}{3^x(2^b-1)}

= \cfrac{1}{3} \cdot \cfrac{2^{b + 1}-1}{2^b-1} \cdot \cfrac{x}{(b+1) \ln 2}

Next, note that \cfrac{2^{b + 1}-1}{2^b-1} = 3 for b=1, and converges to 2 as b increases, meaning

f(v_h) < \cfrac{x}{(b+1) \ln 2},

which is what we set out to show.

For example, for b=1, we have f(v) \leq f(v_h) < 0.72\,x, meaning every (k,x)-cycle has some member less than 0.72\,x.

Numerical confirmation:

For k=65,x=41,
f(v_h)=\cfrac{364625035073295549935}{420491770248316829} \approx 867.1.

For k=66,x=41,
f(v_h)=\cfrac{519869004464865760111}{37313979917667420061} \approx 13.9 < 0.72 \cdot 41.

When we add the fact that many numbers have been computer-checked and don’t participate in non-trivial cycles, we get:

2.35 \cdot 10^{21} < f(v) < \cfrac{x}{(b+1) \ln\,2}.

Setting b=1 and solving for x, we find that any cycle with k= \lceil x \log_2 3 \rceil + 1 must have at least x > 3.2 \cdot 10^{21} odd members.

2

Note that with k = \lceil x \log_2 3 \rceil +b, with b>0, you have 2^k>2^b\cdot 3^x and therefore a_0<\cfrac{3^x\,(x/3)}{2^k-3^x}<\frac{x}{3(2^b-1)}

3

@collagen, this is great. If I understand right, your bound \cfrac{3^x(x/3)}{2^k-3^x} is not only tighter than \cfrac{3^x(x/2)}{2^k-3^x}, but also more flexible, since the proof of the latter is restricted to k=\lceil x \log_2 3 \rceil, while the former is proven for any k > x \log_2 3. Fixing that problem motivated the first post in this thread.

I ran some numeric checks. Below, f(v_h) is a rational number that returns to itself after k steps. (It’s the largest among the minimal members of all rational cycles that do so, so it’s most “testing” of any upper bound.)

For k=66,x=41,b=1,
f(v_h) = \cfrac{519869004464865760111}{37313979917667420061} \approx 13.9
\cfrac{x}{(b+1)\ln 2} \approx 0.72 \cdot 41 = 29.52
\cfrac{x}{3(2^b-1)} \approx 13.66

For k=67,x=41,b=2,
f(v_h) = \cfrac{776800962102176080751}{111100956212505626525} \approx 6.99
\cfrac{x}{(b+1)\ln 2} \approx 19.71
\cfrac{x}{3(2^b-1)} \approx 4.55

For k=68,x=41,b=3,
f(v_h) = \cfrac{1228809109959019553647}{258674908802182039453} \approx 4.75
\cfrac{x}{(b+1)\ln 2} \approx 14.78
\cfrac{x}{3(2^b-1)} \approx 1.95

To explain this data, I’m gonna guess that your bound applies to all (putative) integer cycles, while mine applies to all rational cycles.

Do you think that’s right?

4

It might be the case that it only works with integers since we assume in https://math.meta.stackexchange.com/revisions/4669/655 that all numbers are integer (So that taking 3a_0+1, +2, +3, … will still be smaller than the other 3a_i). I would have to check what happen with these rationals, because I have seen other ways to bound that powers of 2 and 3 sum with 3^x\,(x/3), and I don’t remember if it required integer members. I’ll try to check tomorrow, I won’t have time today.

1 Like
5

Another way to maximize/bound the powers of 2 and 3 sum (\beta(v_h)) is to divide by the highest possible exponent of 2 at each step (this is how the high-cycle parity vector is build, 11011011010…). I think that’s what you did more or less.

So the recurrence relation would be \beta_{i+1}=3\beta_i+2^{\lfloor i\log_2(3)\rfloor}, with \beta_0=0 and at each step we take the highest power of 2 or 2^{\lfloor i\log_2(3)\rfloor}<3^i.

From there you have the same bound: \beta_{x}<x3^{x-1}

The issue is that this recurrence is based on the assumption (not proven even for integers) that the largest possible exponent of 2, to keep a_i>a_0, is 2^{\lfloor i\log_2(3)\rfloor}.

With your rationals at b=1, this is not the case. e.g. at step 8, you have x=5 and k= 8 whilst still having
\frac{539966123744915182447}{37313979917667420061}>\frac{519869004464865760111}{37313979917667420061}
So the parity vector is 11011010… and not the high-cycle 11011011…

Note that for integers, you also can have x=5 and k= 8 whilst still having 8>7 (but here the trajectory went to 5<7 before reaching 8).

So this is probably not related to the rational nature of the terms, but more to the assumption made on the maximum power of 2 that keeps a_i>a_0.

Anyway, if you assume integer terms (and nothing about the maximum power of 2 dividing each term) by using the matchexchange formula, you can trust the bound \beta_{x}<x3^{x-1}. From there i wonder if we can deduce that the maximum power of 2 to keep a_i>a_0 when dealing with integers, is effectively 2^{\lfloor i\log_2(3)\rfloor}. In which case I think you also prove k= \lceil x \log_2 3 \rceil

6

This deduction might be difficult to achieve as it is closely related to a conjecture dating back to Terras, called the Coefficient Stopping Time Conjecture (in Lagarias paper).

One possible formulation of this conjecture is precisely that a_i \geq a_0 as long as the number of divisions by 2 is smaller than (i \log_2 3). In other words, it stated that this number of divisions by 2 cannot be larger than \lfloor i \log_2 3 \rfloor if a_0 \leq a_j for 0 \leq j \leq i.

7

Yes, I remember that. He showed that the density of those cases would be 0 anyway. I’ll check but I still wonder if it can be done by induction. Something like: we know that the maximum power at step i is at least 2^{\lfloor i\log_2(3)\rfloor} but also that the bound at step i is i3^{i-1} (so at most 2^{\lfloor i\log_2(3)\rfloor} ?). I also have the feeling that it would not be so simple (some “cumulative error” preventing this), but who knows…

Edit: @oros you were right. had a look at it this morning and indeed, this seems to be a dead end.

8

@Collag3n thanks. High loop for k=8,x=5 is 11011010. It has 1s spread evenly through 0s, which leads to an irregular, jumpy pattern. For k=65,x=41, it’s
110110110101101101
0110110110101101101
0110110110101101101
011011010.

Also, I don’t know why I so often confound myself with the high-loop-derived bound. I should probably instead write more clearly:

For any positive rational cycle v with smallest member f(v),
f(v) < \cfrac{3^x\,(x/2)}{2^{\lceil x \log_2 3 \rceil}-3^x}

which holds no matter how long v is relative to its total odd terms x. This bound is loose when k \geq \lceil x \log_2 3 \rceil + 1, but we are able to tighten it up with the first post in this thread.

9

If it’s true that a_0 < \cfrac{x}{3(2^b-1)}, and a_0 is a positive integer, then

x > 3(2^b-1)
b < \log_2(\frac{x}{3} + 1)
b < \log_2(\frac{x}{2}) … for x \geq 6
b < \log_2 x

Then can we say the following?

If we have an integer cycle with total odd terms x \geq 6 and length k = \lceil x \log_2 3 \rceil + b, then b must be smaller than \log_2 x.

That would be a big improvement on b< 0.42\,x, when (k=2x), even if not all the way to b=0.

10

Yes, you can say that (you can skip the \log_2(\frac{x}{2}) intermediate step and it would be true for x>1). It still seems too high to be able to do something with it.

11

For my own understanding, here’s a recapitulation of the \cfrac{3^x(x/3)}{2^k-3^x} bound that @Collag3n pointed to, with a note in the middle about integers vs. rationals.

We’re using the Collatz rule “odd n \rightarrow \frac{3n+1}{2}, even n \rightarrow n/2.”

Suppose we have a Collatz integer cycle of length k, containing evens and odds, with distinct odds a_0 ... a_1 ... a_{x-1} embedded in the sequence, with the next odd a_x = a_0. Take a_0 to be the smallest member of the cycle.

For each 0 \leq i \leq x-1,

a_{i+1} = \cfrac{3 a_i + 1}{2^{m_i}}
3(\cfrac{3 a_i +1}{3 a_i}) = 2^{m_i} \cfrac{a_{i+1}}{a_i}

So,

\prod_{i=0}^{x-1} 3(\cfrac{3 a_i +1}{3 a_i}) = 2^{m_0} \cfrac{a_1}{a_0} \cdot 2^{m_1} \cfrac{a_2}{a_1} \cdot 2^{m_2} \cfrac{a_3}{a_2} \cdot \ldots \cdot 2^{m_{x-1}} \cfrac{a_x}{a_{x-1}}
3^{x} \prod_{i=0}^{x-1} \cfrac{3 a_i +1}{3 a_i} = \cfrac{a_x}{a_0} \prod_{i=0}^{x-1} 2^{m_i} = 2^{\sum_{i=0}^{x-1} m_i} = 2^k
\cfrac{2^k}{3^x} = \prod_{i=0}^{x-1} \cfrac{3 a_i+1}{3 a_i}

Now comes a tricky step:

\prod_{i=0}^{x-1} \cfrac{3 a_i+1}{3 a_i} < \prod_{j=3 a_0}^{3 a_0 + x -1} \cfrac{j+1}{j}

Here’s how to justify the inequality. For the first product, rearrange the terms so the a_i are in ascending order. For example, suppose a_0 is the smallest, a_7 the next smallest, and a_4 the next smallest, etc.

lhs = \cfrac{3a_0+1}{3a_0}\cdot\cfrac{3a_7+1}{3a_7}\cdot\cfrac{3a_4+1}{3a_4} \ldots
rhs = \cfrac{3a_0+1}{3 a_0} \cdot \cfrac{3a_0+2}{3a_0+1} \cdot \cfrac{3a_0+3}{3a_0+2} \ldots

Each term in the lhs is smaller than (or equal to) the corresponding term in the rhs. Let’s look at the second term, for example. Because a_0 and a_7 are distinct integers, we have a_7 \geq a_0 + 1. In that case,

\cfrac{3a_7+1}{3a_7} = 1 + \cfrac{1}{3a_7} \leq 1+\cfrac{1}{3(a_0+1)} \leq \cfrac{3a_0+4}{3a_0+3} < \cfrac{3 a_0+2}{3 a_0+1}

(If a_i were rationals instead of integers, this argument wouldn’t work.)

Now we have an inequality in terms of a_0, k, and x, so we can solve for a_0.

\cfrac{2^k}{3^x} < \prod_{j=3 a_0}^{3 a_0 + x -1} \cfrac{j+1}{j}

\cfrac{2^k}{3^x} < \cfrac{3 a_0+x}{3 a_0}

2^k\,3\,a_0 < 3^x(3\,a_0+x)

2^k\,3\,a_0 < 3^x\,3\,a_0+ 3^x\,x

a_0 (2^k-3^x) 3 < 3^x\,x

a_0 < \cfrac{3^x\,(x/3)}{2^k-3^x}

12

Yes that’s it. Note that even if a_7 was the next odd number after a_0, a_0+1 is the even number before a_7, so you can use > instead of \geq:
a_7>a_0+1 \rightarrow 3a_7>3a_0+3>3a_0+1
a_4>a_0+2 \rightarrow 3a_4>3a_0+6>3a_0+2
…
and 3a_7>3a_0+1 \rightarrow \cfrac{3a_7+1}{3a_7}<\cfrac{3a_0+2}{3a_0+1} by the rule that x>y \rightarrow \cfrac{x+1}{x}<\cfrac{y+1}{y} (which is obvious as soon as you multiply both side by xy)

Note that you can find another bound the same with 3a_{max}, 3a_{max}-1, 3a_{max}-2,...

1 Like
13

Just to finish this line off … any rational cycle with all members greater than 1 needs to have k < 2x.

The smallest member of any rational cycle v is less than that of the high cycle.

Easy case, let k=2x.

f(v) \leq f(v_h) = \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^k-3^x}

= \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{2i}}{2^{2x}-3^x}

= \cfrac{4^x-3^x}{4^x-3^x} = 1

Actually, the high cycle’s smallest member is 1 when k=2x because its parity sequence (10)^* follows the trivial cycle.

Here’s a general account of the high cycle’s smallest member:

f(v) \leq f(v_h) = \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\lfloor \frac{k}{x}\,i \rfloor}}{2^k-3^x}

\leq \cfrac{\sum_{i=0}^{x-1} 3^{x-i-1} 2^{\frac{k}{x}\,i}}{2^k-3^x}

= \cfrac{2^k-3^x}{2^{k/x}-3}\cdot\cfrac{1}{2^k-3^x}

= \cfrac{1}{2^{k/x}-3}

So for a rational cycle to have all members greater than 1, we require 2^{k/x}-3 < 1, or k < 2x.

From an integer cycle perspective, this bound is very weak, but rational high cycles with k = 2x -1 manage to have all members above 1.

14

In cycles you can also use 2^k = \prod\limits_{i=0}^{x-1} (3+ \cfrac{1}{a_i})\leqslant (3+ \cfrac{1}{a_{min}})^x\leqslant 4^x=2^{2x} (for a_i\geqslant a_{min}\geqslant1). You can even skip the a_{min} part and just use a_i\geqslant1

From there you also have 2^k \leqslant (3+ \cfrac{1}{a_{min}})^x \rightarrow a_{min}\leqslant \cfrac{1}{2^{k/x}-3}

1 Like