How many odds could a Collatz counter-example cycle have, relative to its length?

General
1

When I first started working on the Collatz Conjecture, I was pondering all possible cycles of length k with x odds. It’s natural, because being a cycle hinges a lot on the value of 2^k - 3^x.

When making proofs, though, it was awkward to cover all cycles by having to range over two indices (k and x). Constraining k > x or k > x \log_2(3) still didn’t obviate the need to range over two variables.

So I decided to only range only over x and just set k = \lceil x \log_2(3) \rceil.

That simplified life, and it was kinda reasonable. After all, the reduced set of (k, x) pairs was where you’d “most expect” to find a cycle.

(The alternative of ranging over k instead didn’t work out; it often led to multiple reasonable values for x. Too bad, because I would have preferred to use the crowd-pleasing phrase “Consider all cycles of length k…” instead of the weirder “Consider all cycles with x odd members…”)

But it continued to bother me that a Collatz cycle might appear at k = \lceil x log_2(3) \rceil + 1 or something like that … and my proofs wouldn’t cover that case. Or if I were looking for a counter-example, maybe I’d blow right past one. So I wanted to justify my choice.

Here’s a helpful constraint:

The smallest member of a cycle must be greater than 1.

Applying this to positive circuits, we have

\cfrac{3^x - 2^x}{2^k - 3^x} > 1

3^x - 2^x > 2^k - 3^x

2 (3/2)^x > 2^{k-x} + 1 (apologies for illegally dropping the +1)

\log_2(2) + x \log(3/2) > k - x
…
k < x \log_2(3) + 1

But also

k > x \log_2(3), because for a positive cycle, 2^k - 3^x > 0

That justifies k = \lceil x log_2(3) \rceil.

Whew!

Not so fast, for general non-circuit cycles

But considering all (k, x) cycles, the smallest member of a cycle could be as large as the high-cycle’s smallest member, which is less than \cfrac{\frac{1}{2} x 3^x}{2^k - 3^x}. So now we have:

\cfrac{\frac{1}{2} x 3^x}{2^k - 3^x} > 1

\frac{1}{2} x 3^x > 2^k - 3^x
…
k < x \log_2(3) + \log_2(x) - 2.58

That \log_2(x) term is significant. If x=100, then we have to contend with potential cycles at k= 159, 160, 161, 162. We can’t just set k=\lceil x \log_2{3} \rceil = 159.

Well, heck, then, let’s try this constraint instead:

The smallest member of a cycle must be greater than 2^{68}.

We know this because computer-checking tells us that none of those numbers cycle non-trivially.

Now we have:

\cfrac{\frac{1}{2} x 3^x}{2^k - 3^x} > 2^{68}

\frac{1}{2} x 3^x > 2^{68} (2^k - 3^x)
…
k < x \log_2(3) + \log_2(x) - 2.58 - 68

That’ll force k to hug \lceil x \log_2{3} \rceil for a while … but not forever. The \log_2{x} is still there.

If x = \lceil 2^{1070.58} \rceil, for example, we’ll have 1000 values of k to contend with.

Conclusion: working from the constraints above, I can’t see restricting proofs and searches to cycles with k fixed at \lceil x \log_2(3) \rceil.

Maybe others have considered stronger constraints than the ones listed above?

For example, nothing above requires that cycle members be integers, just that they be rational numbers of sufficient size.

2

There are two ways to think of the value of K. If a transition is defined as N’ = (3N+1)/2^e where e is the number of even step to get to the next odd value. If the terminal value for a run is the number of transitions until the value is less than the seed then K can exceed ceiling( x * log2( 3 )).

The final transition can be cut short. The value can be less than the Seed before reaching the next odd value. For a seed of 139 the full transitions values are {209, 157, 59}. In the last transition e is 3. However when e is 2 the value is 118; which is also below the seed. This happens when K = 5 = ceiling( 3 * log2( 3)). The value of the K using the full transition is 6.

Depending on which definition you use the value of (2^K - 3^X) will differ. We know that difference needs to be small for the sequence to loop. Any run where the value of K using full transitions is greater will not form a loop since (2^K - 3^X) will be far apart.

Using the smaller value of K is fine for deriving boundaries. You just need to consider that you are excluding those runs with larger values of K.

1 Like
3

One nice thing about restricting k to \lceil x \log_2(3) \rceil is that we can estimate the total number of (k, x) cycles as

\cfrac{\binom{x \log_2(3)}{x}}{x \log_2(3)} \approx \cfrac{2.83^x}{x \sqrt{x}}

which is useful for a heuristic argument against integer cycles, since with so “few” cycles, there’s a vanishing expectation that any one will have a \beta that’s a multiple of 2^k - 3^x, which itself is closer to 3^x. Given the relatively small number of further k values we need to check, per above, I imagine the same argument still goes through.

4

In fact, you don’t even have to consider all values of k according to the constraint
k=301994 a + 17087915 b + 85137581 c
where a, b and c are non-negative integers, b \geq 1 and ac = 0, proved by Eliahou (see , e.g., the section Cycle length on Wikipedia) by using the continued fraction expansion of \log_2 3.

As for the equality k = \lceil x \log_2(3) \rceil, this seems difficult to establish formally, although having k \geq \lceil x \log_2(3) \rceil +1 is extremely unlikely to occur! Eliahou’s upper bound
\cfrac{k}{x} \leq \log_2(3 +1/m) implies that k \leq x \log_2(3) + \cfrac{x}{3m \log 2} where m is the smallest term of the cycle. So the question is whether 3m \log2 can be smaller than x? For a partial answer, let us consider all sequences (cycling or not) starting from a positive integer m \neq 1, of length k, with x odd terms, and such that k = \lceil x \log_2(3) \rceil + o(x). There is numerical evidence that
m \geq \cfrac{\alpha^k}{k^C} where C \approx 1 is a constant and \alpha = 2^{1-H(1/ \log_2(3))} = 1.035\ldots. Here, H is the binary entropy function H(r) = -r \log_{2}(r) - (1-r) \log_{2}(1-r). This is a particular case of a more general conjecture (namely, LBH with C\approx1) in one of my papers (The $3x+1$ problem: a lower bound hypothesis). Then, it is a easy to establish that we cannot have k/ \log_2(3) > x \geq 3 m \log 2 \geq (3 \log 2) \cfrac{\alpha^k}{k} as soon as, say, k \geq 1000. To conclude, if we assume LBH to be true (with a reasonable constant C), then necessarily k < x \log_2(3) +1 in the case of a cycle of positive integers. Of course, this does not hold if we also consider rational cycles.

5

I find it quite funny that we are only able to prove the desired equality k = \lceil x \log_2(3) \rceil for circuits which is a particular type of cycle that we know does not exist :grinning_face:
… with the notable exception (1,2)

2 Likes
6

Agreed! If we keep proving properties of these nonexistent things, maybe two of those properties will be inconsistent, and we’ll be done!

Also funny that the same requirement (smallest cycle member must be bigger than 1) leads to the integer circuit having k = \lceil x \log 3 \rceil and to its nonexistence via \cfrac{2^{k-x}-1}{2^k-3^x} < \cfrac{O(1.5^x)}{O(2.56^x)} < 1.

7

The constants in Eliahou’s constraint for K have corresponding powers of 3 giving odds. The first two have lots of leading ones in the power of 3. Since K can have different values for a run; using the number of odds as the run length is consistent. It would be nice to have his constraint rewritten for the number of odds rather than K; provided that makes any sense.

order( 3^190_537 ) = 301_994 23 leading ones

order( 3^10_781_274 ) = 17_087_915 26 leading ones

order( 3^53_715_833 ) = 85_137_581

     34_175_830 + 51_263_745 - 301_994 = 85_137_581

order(3^21_562_548) = 34_175_830       25 leading ones

order(3^32_343_822) = 51_263_745       24 leading ones
1 Like
8

As long as it’s impossible to bound the amount of steps one number could have before getting under itself, it will be impossible to know if k=⌈xlog2(3)⌉, you can see that by having the general formulo of any term of n after a said amount of steps. Indeed in it, there is a sum that depends on the variations of x on the terms , i.e in which exact order has it been odd and even for every term before and which unfortunately diverges when the amount of steps gets bigger and the bigger it gets, the more freedom we can have on the expression 3^x/2^k with 3^x/2^k<1 required for a positive integer cycle and it can get as close to 0 as you want as long as the sum gets big enough while k=⌈xlog2(3)⌉+1 would require 1/2<3^x/2^k<1 meaning that you can’t have one k depending on x the only thing we can say is that k>=⌈xlog2(3)⌉+1 be cause else we would have 3^x/2^k>1. Though I am surprised to see the statement k=301994a+17087915b+85137581c
where a, b and c are non-negative integers, b≥1 and ac=0, proved by Eliahou but I imagine that x can still vary even for a given k having this property if k is big enough compared to the maximum n we know obey the conjecture.

1 Like
9

Totally agree; it’s hard to imagine such large k's, but they are out there.

10

I propose a proof of k = \lceil x \log_2(3) \rceil for a larger set of potential cycles. The only conditions are that x \geq 27 and \frac{M}{m} \leq 7 with m and M the least and greatest odd elements of the cycle, respectively. In other words, the cycle has to be relatively flat, unlike a circuit, and not too short.

Amazingly, the main argument is that there is simply not enough space between m and M for a cycle of length k \neq \lceil x \log_2(3) \rceil with x odd terms.

The proof is elementary :slight_smile: and goes as follows:

Let a = \frac{M}{m} > 1 .

We assume that

  • a \leq 7;
  • k = \lceil x \log_2(3) \rceil + d with d \geq 0 and x \geq 27.

Since the cycle has x odd terms coprime to 3 ranging between m and M, we estimate the number of such integers in this range which is at most \frac{M-m}{3} + 1 = \frac{a-1}{3}m + 1. We deduce that x \leq \frac{a-1}{3}m + 1, which we can also write
m \geq \frac{3(x-1)}{a-1}.

Next, we consider the well-known equality
2^k = \prod_{i=1}^x (3+\frac{1}{n_i}) \quad
holding for all cycles with odd terms n_1, \ldots, n_x. See Lemma 2.2 in Eliahou’s paper for an elementary proof.

It implies that: 2^k \leq \left(3+\frac{1}{m}\right)^x.

On the other hand, we have 2^k > 3^x \, 2^d.

It yields

2^d < \left(1 + \frac{1}{3m}\right)^x .

Then, we take the logarithm:

d \log 2 < x \log \left(1 + \frac{1}{3m} \right) < \frac{x}{3m} < \frac{(a-1)x}{9(x-1)}

so that

a > 1 + \frac{9(x-1)d\log 2}{x} \geq 1 + \frac{9 \cdot26 \, d\log 2}{27} > 1 + 6 d.

Our very first assumption that a \leq 7 implies d=0.
\square

Consequently, we can answer in the two extreme cases of a circuit and a high cycle (both of which we know do not exist), but also in the case of all sufficiently “flat” (high?) cycles. If anyone was wondering!

11

@oros that’s great, super-creative!

For high cycles, I previously looked at the ratio of the highest even member to the lowest odd member (since their parity vectors are reverses of each other). When k= \lceil x \log_2 3 \rceil, the flatness ratio seems to approach 3 from below (as x increases). When k= \lceil x \log_2 3 \rceil + 1, the flatness ratio seems to approach 3 from above. Flatness is not bounded for larger k. For example, if x=10, k=101, then the smallest member \approx 4.9 \cdot 10^{-4}, and the largest member \approx 0.501, for a flatness ratio of 1024.

For my own understanding … here’s a recapitulated, weaker version of your post @oros for high cycles only. I know high cycles are already ruled out on other grounds, so this is similar to the original post in this thread :slight_smile:

The lowest odd member of a high cycle is less than \cfrac{3^x (x/2)}{2^k - 3^x} (Theorem 4.8 of shameless plug.)

I have a similar proof that the highest even member of a high cycle is less than \cfrac{2^{k/x}}{2^{k/x}-3}.

The highest odd member should be the one right before the highest even member, so M < \cfrac{2}{3}\,\cfrac{2^{k/x}}{2^{k/x}-3}.

Next, we can establish that if some integer high cycle has k=\lceil x \log_2 3 \rceil + 1, then M < x, which is a contradiction, because x odd integer members can’t all be less than x.

Let k = \lceil x \log_2 3 \rceil + 1.

\cfrac{k}{x} > \cfrac{x \log_2 3 + 1}{x} = \log_2 3 + \cfrac{1}{x}.

Set t = 2^{k/x} > 2^{\log_2 3 + \frac{1}{x}} = 3 \cdot 2^{1/x}.

Since \cfrac{t}{t-3} is decreasing in t,

M < \cfrac{2}{3} \cdot \cfrac{t}{t-3} < \cfrac{2}{3} \cdot \cfrac{3 \cdot 2^{1/x}}{3 \cdot 2^{1/x}-3} = \cfrac{2}{3} \cdot \cfrac{2^{1/x}}{2^{1/x}-1}.

Replacing 2^{1/x} with e^{\ln 2 / x},

M < \cfrac{2}{3} \cfrac{e^{\ln 2 / x}}{e^{\ln 2 / x}-1} < \cfrac{2}{3}(1+\cfrac{x}{\ln 2}) < 0.67 + 0.97\,x,

which is less than x (for x > 22).

Very little margin in the 0.97 :slight_smile: Can’t say whether there’s enough margin for error in the math, of course.

12

Yes, it works very well in the case of the high cycle due to its extreme flatness.

To be even more conclusive, we could use the condition M \geq 3x-2 by discarding the even integers as well as multiples of 3 below M. We obtain a contradiction for any x \geq 2, while x=1 corresponds to the trivial (high) cycle (1,2).

Note also that the ratio 7 in my proof can be further improved by using a stronger corollary of Eliahou’s result involving the harmonic mean of the odd terms instead of the smallest one.

1 Like
13

Makes sense: even fewer pigeonholes for the pigeons.

I wonder if the “lowness” of the cycle (how low its largest member is) may be an alternative to “flatness”.

As k grows relative to x, the high cycle gets lower and lower even as it gets less flat.

Depending on the flatness ratios you’re considering, it’s possible that the distance between 1 and M might not be materially different from the distance between m and M.

14

It’s interesting to think about how many odds an integer cycle might hit in the “operating range” between m and M.

It can’t hit odds that are 0 mod 3, as mentioned.

For a cycle with no adjacent evens (like the high-cycle, for instance), it also can’t hit odds of the form 5 mod 8, because such odds are followed by two evens (eg, 13 \rightarrow 20 \rightarrow 10).

In that case, it’s sufficient to show M < 4x-3, a tiny bit easier than showing M < 3x-2 or M < x.

15

The high cycle also has the weird property that two distinct odd members kick off the same (k-2)-length pattern (eg, in 11011010, two odds both go like “101101…”).

Suppose both those odds are integral.

Since only one residue mod 2^{k-2} has a pattern like 101101 (Terras '76), one of those odds has to be bigger than 2^{k-2}.

At the same time, due to its “flatness” or “lowness”, the high cycle’s largest odd is capped by M < \cfrac{2^{k/x}}{2^{k/x}-3}.

Those two facts are contradictory for x>5, so the high cycle can’t consist of integers, even if k = \lceil x \log_2 3 \rceil.

Which we knew, but it’s a nice argument.

1 Like
16

Less interesting, but we can do the same with circuits also.

Consider a circuit with x up-moves followed by k-x down-moves.

Suppose the circuit members are integers.

The smallest member of the circuit goes up x-1 times, then does some other stuff.

The next-to-smallest member of the circuit also goes up x-1 times, then does some other stuff.

By Terras '76, there’s only one residue mod 2^{x-1} whose initial trajectory goes up x-1 times. (That would be -1.)

So the first two circuit members must be separated by at least 2^{x-1}.

The smallest member’s value is m = \cfrac{3^x-2^x}{2^k-3^x}.

The next-to-smallest member’s value is n= (3m+1)/2.

That means

n-m = \cfrac{2^{x-1} (2^{k-x}-1)}{2^k-3^x} \geq 2^{x-1}

So

2^{k-x}-1 \geq 2^k - 3^x

Which is a familiar circuit-formula known to be false, but only through non-elementary arguments :slight_smile:

So, no integer circuits, as already known.

PS. Terras '76 and Everett '77 were nearly 50 years ago! Wonder if they were thinking, “How hard could this be?”

17

I’ve not proved it, but by noodling around I’ve reasoned to myself that when k > x*log2(3) the sequence will not cycle. The strategy is to work with the smallest value of K and then treat the larger values as a lemma by carrying it through your work.

19

I see you often use this upper bound \cfrac{3^x\,(x/2)}{2^k-3^x}, but there is a better one: \cfrac{3^x\,(x/3)}{2^k-3^x}
It comes from this https://math.meta.stackexchange.com/revisions/4669/655 where you have \frac{2^S}{3^N}<\frac{3a_0+N}{3a_0} leading to a_0<\frac{N3^{N-1}}{2^S-3^N}

1 Like
20

Oh, that’s great … my inequality’s slack comes from bounding the floors and ceilings in the high cycle’s \beta, while yours comes from the idea 3a_0+i < 3a_i (for odds a_0 to a_{x-1}, with a_0 minimal).

23

a_0 > \dfrac{N}{3}

I don’t really get why this is always true. Is it a theorem or just a known fact? I’m pretty ignorant..