How many cycle shapes could (even conceivably) be Collatz integer cycles?

General
1

Feeling in the mood for pigeonhole arguments, here’s one showing that almost no cycle shapes can have integer members.

A cycle shape is something like “up-down-down”. For every shape, there is a unique rational number m that returns to itself, creating a cycle … in this case, 1/5 \rightarrow^{up} 4/5 \rightarrow^{down} 2/5 \rightarrow^{down} 1/5.

(If you’re unfamiliar with fractions zooming around these cycles, just calculate (3n+1)/2 for n=1/5.)

Now consider all the cycle shapes with length k and x odds – there are \binom{k}{x} / k of them. Even restricting k to x \log_2 3, there are already an exponential number of such cycle shapes:

\binom{k}{x}/k = \cfrac{k!}{k\ x! (k-x)!}
\approx \cfrac{(1.58x)^{1.58x}}{(x \log 3) x^x (0.58x)^{0.58x}}
= O(2.84^x)

On the other hand, every (k,x)-cycle has some member less than \cfrac{3^x (x/2)}{2^k - 3^x}, according to Theorem 4.8 here. Using Rhin’s bound, that member is less than

\cfrac{3^x (x/2)}{\frac{3^x}{457\ x^{13.3}}} < 229\,x^{14.3}

Even if every integer from 1 to 229\,x^{14.3} participated in a distinct integer (k,x)-cycle, that would involve a vanishing fraction of the O(2.84^x) total (k,x)-cycle shapes.

For example, at x=100, there are more than 10^{45} cycle shapes, but no more than 10^{16} of them can conceivably contain integers at the same time.

So this pigeonhole argument rules out vast numbers of cycle shapes as (even remotely conceivable) integer cycles, though it doesn’t say which ones :slight_smile:

1 Like
2

Here’s another argument that almost no parity sequences can correspond to Collatz counterexample cycles.

There are about 2^k/k rational cycles of length k.

Let’s show at most 1.3^k of them can be integer cycles, a vanishing fraction as k increases.

Every parity vector v of length k corresponds to some rational number m that returns to itself after following the even-odd sequence v.

A cycle is a set of parity vectors that are rotations of each other.

There are about 2^k/k cycles (actually a tiny, tiny bit less, due to periodic vectors).

Previously, if two vectors v_1 and v_2 in the same cycle have a common prefix longer than 0.38\,k, then their associated cycle members m_1 and m_2 can’t both be integers, so the cycle can’t be a Collatz counterexample.

We can apply the same idea across cycles, to show that two distinct cycles can’t both be Collatz counter-examples (even if one of them might).

Build a graph with a node for each cycle. Connect any pair of nodes A and B if there’s some parity vector (rotation) v_1 in the A cycle, and some parity vector (rotation) v_2 in the B cycle, such that v_1 and v_2 have a shared prefix longer than 0.38\,k.

Question: What is the largest set S of nodes where none are pairwise connected? All cycles in this set can (conceivably) be Collatz counter-examples simultaneously. This is the maximum independent set of the graph.

In this case, we can show that the set S can’t be bigger than 1.3^k.

  1. The total number of available, distinct blocks of length 0.38k is 2^{0.38k}. (Omitting floors and ceilings for simplicity.)

  2. Every cycle has some parity vector with some block of length 0.38k.

So, if S contains more than 2^{0.38k} cycles, some block will appear twice, meaning two of the cycles will be connected, and therefore S isn’t an independent set.

That means the maximum number of pairwise unconnected nodes is 2^{0.38k} \approx 1.3^k, so there are at most that many conceivable Collatz counterexamples.

As usual, even though almost no parity sequences can form integer cycles, we don’t have much of a grasp on which ones might, or might not …

PS. Similar arguments show the maximum clique T in the graph is also smaller than 1.3^k. Among the cycles in T, at most one can be a Collatz counterexample.