Do a purported cycle's length (k) and # of odds (x) have to be co-prime?

General
1

If there were a Collatz counter-example cycle, is it known that the cycle’s length (k) and total odd terms (x) need to be co-prime?

The statement is true for the special case of circuits (where all odds precede all evens), but I don’t know about the general case.

Background:

Any purported Collatz cycle shape has a length k and weight x. The weight counts the total number of “up” moves (versus “down” moves).

For example, the cycle shape “up-up-down-up-down” (repeating) has k=5, x=3.

For any circuit shape (up-up-…-down-down), the bottom member of the circuit has the value \cfrac{3^x-2^x}{2^k-3^x}.

If this is an positive integer > 1, we have a Collatz counter-example.

In that case, these are also integers:

\cfrac{3^x-2^x}{2^k-3^x} + 1, \cfrac{3^x-2^x}{2^k-3^x} + \cfrac{2^k-3^x}{2^k-3^x}, \cfrac{2^k - 2^x}{2^k-3^x}, \cfrac{2^x (2^k-3^x)}{2^k-3^x}, \mbox{and} \cfrac{2^{k-x}-1}{2^k-3^x}.

Is the latter ever a positive integer, for any value of k>2?

For co-prime x and k, there’s an elementary proof of “no” showing the denominator always exceeds the numerator.

(Proof sketch in the PS below.)

Question: Is this also true of any cycle shape (not just the circuit) … i.e., do the length k and weight x need to be co-prime for the cycle to contain integers?

Question: If so, is it also true of all qn+1 problems? For example, the known positive (non-circuit) cycle for 5n+1 has k=7, x=3 (co-prime), and the known (non-circuit) cycle for 181n+1 has k=15, x=2 (co-prime).

PS.

Lemma 1. Because we only care about positive cycles:

2^k -3^x > 0

k > x\ log\ 3

Lemma 2. Because we only care if the bottom member of the cycle > 1:

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

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

2 \cdot 3^x > 2^k + 2^x

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

Theorem. If k and x have a common factor, then \cfrac{2^{k-x}-1}{2^k - 3^x} is not an integer.

Eg, if k and x are both even, 2^k - 3^x = (2^{k/2} + 3^{x/2})(2^{k/2} - 3^{x/2}) > 2^{k/2} > 2^{(x\ log\ 3) / 2} > 1.72^x >2^{k-x}-1.

Lemmas 1 and 2 are used in the 2nd and 4th inequalities. The argument can be extended to the case where gcd(x,k) > 2.

2

The empirical evidence from qn+1 is probably not too compelling. In every case except 181n+1, the small k is already prime (meaning k and x are co-prime). And for the 181n+1 case, a randomly-chosen x is more likely than not to be co-prime to k=15.

And rules like 3n+7 definitely have cycles when \gcd(x,k)>1, such as 5-11-20-10-5 (for k=4, x=2). That’s not only a cycle but a circuit. But that’s kind of vacuous, since for any x and k>x, every parity sequence induces a cycle under the 3n + (2^k-3^x) rule.

3

A non-trivial cycle must have gcd(k,x)=1. Any common divisor of k and x that’s >1 would force a shorter affine map - i.e., you’d have found a strictly shorter period than the one you started with. That’s the idea of minimality. https://arxiv.org/pdf/2101.04067

4

Great, this is what I’m not yet following. Sticking with 3n+1 for a moment …

I can see that if \gcd(k, x) > 1, then there is at least one periodic parity sequence of length k and weight x.

For example, for k=4, x=2, we have 1010, which is just the trival cycle repeated twice.

But there’s another k=4, x=2 parity sequence, namely 1100, which is not periodic. It doesn’t consist of some smaller k<4 cycle repeated.

So I can’t see how to conclude that 1100 doesn’t induce an integer cycle, from \gcd(4, 2) > 1 alone.

Here’s a k=16, x = 10 parity sequence: 1111101001101001 … or consider some vastly larger, randomly-ordered sequence of 1's and 0's with \gcd(k, x) > 1. How to know these sequences don’t induce integer cycles?

For any individual case, we can of course grind it out, eg, the first member of the 1111101001101001 cycle is m = \cfrac{9581}{499} \approx 15.85. Or we can find some other one-off argument that doesn’t rule out other huge sequences.

5

For a parity word of length k and weight x the cycle-closing value is
n=C/D with D=2^{k}-3^{x}. You need D\mid C.

1100 doesn’t give an integer solution, the divisibility fails. It gives (9/16)n+(5/16). i.e. two 1’s four steps. No integer solution, no cycle.

If it did give an integer solution, then the actual cycle wouldn’t be 1100 it would be some smaller piece (like 10 or 01?)

6

Hmm, right, I get that 1100 and 1111101001101001 don’t induce integer cycles, but I only know that from grinding them out individually.

I don’t know a general proof that applies to all parity sequences where \gcd(k, x) > 1.

My proof above only covers circuits (1^* 0^*) where \gcd(k, x) > 1.

That is, when k and x are both even, we have

C = 3^x - 2^x
D = 2^k - 3^x = (2^{k/2} + 3^{x/2})(2^{k/2}-3^{x/2}) > 2^{k/2} > 2^{(x \log 3)/2} > 1.72^x.

If D divides C (and the smallest member of the cycle is greater than 1), then

D = \gcd(C, D) = \gcd(3^x - 2^x, 2^k - 3^x) = \gcd(2^{k-x}-1, 2^k - 3^x) \leq 2^{k-x} - 1 < 2 (\frac{3}{2})^x.

But those two facts about D are incompatible when x>5.

7

For 3n+c there are many loops where they are not coprime. For 3n+35 the cycle {17, 43, 41, 79} the value of x = 4 and k = 8. I can’t think of a reason why 3n+1 would be special.

1 Like
8

Thanks, and good data point. I guess the algebra just works out that way in the case of the 3n+1 circuit.

9

Agree even more after looking at 1000 random parity vectors v with (coprime) length k=27 and weight x=17 …

Of course, none form integer cycles, where beta(v) is a multiple of 2^k-3^x …

But almost exactly 20% have beta(v) sharing a factor of 5 with 2^k-3^x. It seems like the factors of beta(v) via-a-vis 2^k-3^x are unaffected by k and x being coprime.

10

We can’t seem to prove that an integer cycle must have coprime length k and total odds x … but let’s at least show their common factor g can’t be too big.

Suppose \gcd(k,x)=g, and so k=ga, x=gb.

Let’s show that for large enough x:

If g > 0.00001 x, we can't have an integer cycle.

(Or feel free to replace 0.00001 by any constant c.)

We do it by bounding \cfrac{2^a}{3^b} from both sides.

Every cycle has some member less than \cfrac{3^x (x/2)}{2^k-3^x}.

This member must be greater than 1:

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

3^x (x/2) > 2^k-3^x

2^k < 3^x (1 + x/2)

2^k < 3^x x …for x>2

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

\big( \cfrac{2^a}{3^b} \big)^g < gb

\cfrac{2^a}{3^b} < (gb)^{1/g}

For the other side, use Rhin’s bound:

2^a - 3^b > 457^{-1}\ 3^b\ b^{-13.3}

\cfrac{2^a}{3^b} - 1 > 457^{-1}\ b^{-13.3}

\cfrac{2^a}{3^b} > 1 + 457^{-1}\ b^{-13.3}

Combining, and using \ln(1+x) \geq x/2 for 0<x<1,

(gb)^{1/g} > \cfrac{2^a}{3^b} > 1+ 457^{-1}\ b^{-13.3}

(gb)^{1/g} > 1+ 457^{-1}\ b^{-13.3}

(1/g) \ln(gb) > (1/2)\ 457^{-1}\ b^{-13.3}

\ln(gb) > g\ 914^{-1}\ b^{-13.3}

Substituting back x/g for b,

\ln(x) > g\ 914^{-1} (x/g)^{-13.3}

\ln(x) > g^{14.3}\ x^{-13.3}\ 914^{-1}

g^{14.3} < \ln(x)\ x^{13.3}\ 914

g < \ln(x)^{1/14.3}\ x^{13.3/14.3}\ 914^{1/14.3}

g < x^{0.93} \ln(x)^{0.07}

So for large enough x, we can’t have g be any fixed percentage of x.

11

Here is a counterexample with k=19 and x=10: Consider the cycle starting with the rational number 504605/465239, which is the smallest member. This cycle has length k=19 and parity vector 1101010101010101010, so that x=10.

For this rational cycle, we have
504605/465239\approx 1.08
and
\cfrac{3^x (x/2)}{2^k-3^x} \approx 0.63

According to your paper on high cycles, this property has been shown only under the assumption that k = \lceil x \log_2 3 \rceil.
AFAIU.

12

Thanks very much, and for sure. So this proof applies only to k = \lceil x \log 3 \rceil.

I was intending to use \cfrac{3^x(x/3)}{2^k-3^x}, which @Collag3n posted here, and I tried to recapitulate here.

If I understand right, that minimal-member upper bound more flexibly applies to any k \geq \lceil x \log 3 \rceil, though it less flexibly applies only to integer cycles.

1 Like
13

Ok, I just forgot this post from @Collag3n . There are so many ramifications in your Collatz world …
Thanks for recapitulating!

14

Putting together all the pieces, we end up with a rather complicated proof and I find surprising that this result requires so much work. Very likely it is new. So well done.

15

I thought the same … not the prettiest of proofs. Overall, I’m motivated by the fact that when \gcd(k,x) > 1, there’s an elementary no-circuit proof. So I start thinking maybe other interesting things can be shown for the case when \gcd(k,x) \neq 1.

16

If you want to have rationals and keep k \geq \lceil x \log 3 \rceil you can still use this:

From this post we have a_{min}\leqslant \cfrac{1}{2^{k/x}-3}, and with 2^{k/x}>3 \Rightarrow \cfrac{2^k-3^x}{2^\frac{k}{x}-3}=(2^\frac{k}{x})^{x-1}\cdot 3^0+(2^\frac{k}{x})^{x-2}\cdot 3^1+...+(2^\frac{k}{x})^0\cdot 3^{x-1}<x(2^\frac{k}{x})^{x-1}

you have a_{min}\leqslant \cfrac{x(2^\frac{k}{x})^{x-1}}{2^k-3^x} instead of the “integer” bound a_{min}\leqslant \cfrac{x(3)^{x-1}}{2^k-3^x}

1 Like
17

For rationals, the bound \cfrac{1}{2^{k/x}-3} is indeed relatively tight when applied to my previous example with k=19 and x=10:

  • a_{min} \approx 1.08
  • \cfrac{1}{2^{k/x}-3} \approx 1.36
  • \cfrac{x (2^\frac{k}{x})^{x-1}}{2^k-3^x} \approx 3.02
18

For the case k = \lceil x \log_2 3 \rceil, we have \cfrac{(x/3) 3^x }{2^k-3^x} < \cfrac{1}{2^{k/x}-3} \leq \cfrac{(x/(3 \ln 2)) 3^x }{2^k-3^x}
and the upper bound is sharp when k/x \approx \log_2 3.

Here is a sketch of proof:

Let r=k/x, let \rho = \log_2 3 and let \delta = r- \rho.

We calculate the ratio

\cfrac{(x/3) (2^r - 3)}{(2^k-3^x)/3^x} = \cfrac{(x/3) (3 \cdot 2^\delta - 3)}{2^{k-\rho x}-1} = \cfrac{x (2^{\delta} - 1)}{2^{\delta x}-1}.

Since 0 < \delta x = k - \rho x < 1, the above ratio takes all its values in the interval (\ln 2,1].

Here is a plot for x=1, ... , 10^4.

ratio
ratio1237×844 13.8 KB

19

@oros, how did you get your first equation?
k = \lceil x \log_2 3 \rceil \Rightarrow 3<2^{k/x}<3\cdot 2^\frac{1}{x}

and with \cfrac{2^k-3^x}{2^\frac{k}{x}-3}=(2^\frac{k}{x})^{x-1}\cdot 3^0+(2^\frac{k}{x})^{x-2}\cdot 3^1+...+(2^\frac{k}{x})^0\cdot 3^{x-1}

I get x3^{x-1}<\cfrac{2^k-3^x}{2^\frac{k}{x}-3}<3^{x-1}[(2^\frac{1}{x})^{x-1}+(2^\frac{1}{x})^{x-2}+...+(2^\frac{1}{x})^0]=\cfrac{3^{x-1}}{2^\frac{1}{x}-1}<\cfrac{x3^{x-1}}{\log2}

so you should get \cfrac{(\ln 2)(x/3) 3^x }{2^k-3^x} < \cfrac{\ln 2}{2^{k/x}-3} \leq \cfrac{(x/3) 3^x }{2^k-3^x}

(Using the Laurent series of x(2^\frac{1}{x}-1), we know that x(2^\frac{1}{x}-1)>\log2)

So for k = \lceil x \log_2 3 \rceil and rationals, I would say that a_{min}\leqslant \cfrac{x3^{x-1}}{ 2^k-3^x}\cdot\cfrac{1}{\log 2}<\cfrac{(x/2) 3^x }{2^k-3^x}

20

You are right, what I proved is obviously that

\cfrac{(x/3) 3^x }{2^k-3^x} \leq \cfrac{1}{2^{k/x}-3} < \cfrac{(x/(3\ln 2)) 3^x }{2^k-3^x}.

so that the bound \cfrac{1}{2^{k/x}-3} is indeed slightly better than \cfrac{(x/2) 3^x }{2^k-3^x} (in the worst case).

Previous post corrected.