Which Collatz cycle shapes correspond to integer cycles?

Sure! Here’s the argument I have.

Claim: Any k-length parity vector with two rotations that share a prefix longer than k/2 cannot induce a Collatz counter-example cycle.

Corollaries: This rules out circuits, high cycles, regular cycles, and others.

Proof:

Suppose some Collatz cycle is induced by a k-length parity vector u with x 1s.

Now suppose condition A holds:

Parity vector u has two rotations v and w that share a prefix of length greater than k/2.

Let v and w correspond to cycle members \cfrac{\beta(v)}{2^k - 3^x} and \cfrac{\beta(w)}{2^k - 3^x}.

Assume wlog the latter is greater.

If those two members are integers, then so is their difference:

\cfrac{\beta(w) - \beta(v)}{2^k - 3^x}

We going to show, by way of contradiction, that this difference is not (in fact) an integer, so … any cycle where condition A holds cannot be a Collatz counter-example.

Here are examples of w and v:

w = ab = 101011{\color{red}01011}
v = ac = 101011{\color{red}10101}

Let k^\prime = |b| = |c| < k/2, and let x^\prime be the number of 1s in b (or equivalently, c).

To compute \beta(w) - \beta(v), terms from the shared prefix cancel out, so

\beta(w) - \beta(v) = 2^{k-k^\prime} (\beta(b) - \beta(c))

We can get rid of the power of two, because

\cfrac{\beta(w) - \beta(v)}{2^k - 3^x}

is only an integer when

\cfrac{\beta(b) - \beta(c)}{2^k - 3^x}

is an integer.

Now we’ll show the denominator outstrips the numerator, so the last expression can’t, in fact, be an integer.

How big can the numerator \beta(b) - \beta(c) get? In the maximum scenario, b will push all the 1s to the right, and a will push them to the left. With a little effort, we discover that the difference is totally maximized in the case where x^\prime = k^\prime - 1:

b = 0 1^{x^\prime} = 0 1^{k^\prime - 1}
c = 1^{x^\prime} 0 = 1^{k^\prime - 1} 0

\beta(b) = 2 (3^{k^\prime-1} - 2^{k^\prime-1})
\beta(c) = 3^{k^\prime-1} - 2^{k^\prime-1}

Now we have:

\beta(b) - \beta(c)
< 3^{k^\prime-1} - 2^{k^\prime-1}
< 3^{k^\prime}
< 3^{k/2}
< 1.74^k

For the denominator, we have Ellison’s theorem, applicable when k > 27:

2^k - 3^x
> \cfrac{2^k}{e^{k/10}}
> 1.8^k

Thus, the denominator barely outstrips the numerator, so the main result obtains.

You can see that a shared prefix of k/2 is close to the breaking point where Ellison’s theorem won’t suffice. A better result should be possible using Rhin’s theorem.

However, most parity vectors have self-overlap on the order of \log_2 k rather than some constant proportion of k.

Interested in any comments / corrections / errors :slight_smile: