Questions about n < 2^k

General
1

I have a few claims which represent kind of a scale of the same claim from weak to strong.

I’m wondering how much of this is true, and if it is, how it’s proven. If it’s not easy but there’s a paper, I would be interested in reading up on it.

I’ll be using the n, k, x, β terminology I’ve been seeing here.

  • The smallest number in a cycle is less than 2^k
  • All odd members of a cycle are less than 2^k
  • All members of a cycle are less than or equal to 2^k
  • Let Δn be the difference between n and the first number <= n in its trajectory. If Δn < 2^k - 3^x, then n < 2^k

My general reasoning is based off of the sequence equation and the fact that parity vectors are unique for k divisions by two for numbers up to 2^k, and are periodic mod 2^k, as proven by Steiner (correction: Terras and Everett, independently).

This is how I like to write the sequence equation, with a Δn term instead of final n. This way it’s more like the cycle equation.

n = (β + Δn * 2^k) / (2^k - 3^x)

You can see how if Δn = 2^k - 3^x, that term cancels to 2^k, so every time you add 2^k to n, you get the same parity vector, but Δn increases by 2^k - 3^x. I would think that for a cycle, with Δn = 0, it wouldn’t make sense if it was equal to some smaller positive number plus 2^k. And then I would argue similarly but less confidently for the rest of the claims. I know the last claim particularly can’t be substantiated using this equation.

Since I’m here asking questions, I’ve heard a lot of different claims about the maximum value of β for a cycle. We all know the minimum is 2^k - 3^x, but finding the upper bound is a lot harder. If it’s derived from the “high cycle”, where every division by two that keeps the current n >= the initial n, then it would be nice to have a closed form we know will always be larger, but not too much larger, than the definitely not closed form of the high cycle. This would be complicated by the fact that we don’t know whether the Coefficient Stopping Time Conjecture is true, so there could be extra divisions by two in there if the +1s add up enough.

Okay one last thing: I’ve also heard that if the CSTC is true, then there are no non-trivial cycles. Does anyone know if this is true and how or where it’s substantiated?

Thanks!

2

In a cycle,

All elements n_i<2^x<2^k
(here x,n,k are used instead of n,k,x)

3^x-2^x \leqslant \beta <x3^{x-1}

I don’t think the truthness of CSTC means no other cycles exists. I saw that the Google search AI seems to imply that from the “paradoxical” paper of @oros, but that seems far-fetched to me.

3

I agree with @Collag3n that all the members in a cycle are less than 2^k where k is the length of the cycle. However, the proof is not elementary and uses Baker-like results (Rhin’s bound). That was precisely the question of this post in stackexchange (initiated by @cosmo) with some useful references.

Regarding the “uniqueness” of parity vectors of length k for numbers up to 2^k, it was not proved by Steiner but (independently) by Everett and Terras.

I’m sure @mathkook can answer for your question on high cycles.

Regarding the Coefficient Stopping Time (CST) conjecture of Terras, it is obvious to me that it implies the absence of nontrivial cycles. The proof is elementary and goes as follows:
Just consider the contrapositive and assume the existence of a nontrivial cycle. If n is the smallest member, then it has an infinite stopping time since its trajectory never reaches any integer smaller than n. On the other hand, its coefficient stopping time is not larger than k since T^k(n) has coefficient 3^x/2^k which is strictly lower than 1. Therefore, n would be a counterexample to CST. So, if the CST conjecture is true, there cannot be a nontrivial cycle.

You can find the exact same reasoning in the well known and highly referenced paper of Lagarias published in Amer. Math. Month (1985). If anything is unclear, please let me know. I would like to understand why so many people don’t see it. Maybe because the CST conjecture seems more simple than the Collatz conjecture. But it is not.

4

Indeed you are right, the exclusion of cycles is in the definition of \chi (strict inequality). I always used his conjecture in relation to k\geqslant\lceil xlog_23\rceil which is the origin of the conjecture and at the core of the question (“extra division by 2”), and never paid enough attention (even with equality this is still a hard conjecture).

5

Thanks for the clarification.

The implication is recalled in my “paradoxical” paper for which a new revision is ongoing. Amazingly, an equivalent formulation of the CST conjecture is that the first term of a paradoxical sequence is never the smallest. This will appear in the next revision.

By the way, there seems to be some confusion around my definition of a paradoxical sequence. Maybe I should have required a strict inequality as well… Hopefully, the next revision will clarify that by distinguishing the cyclic case (not occuring) from the non-cyclic one (effectively occuring).

I find it stunning that no significant progress has been made on CST conjecture since the paper of Terras. Probably because this conjecture has received less attention.

One more comment: It is not common that Google search engine refers to an arXiv manuscript. Google is our friend, sometimes…

6

For \beta values of rational cycles, I use this picture. There’s a formula for the smallest \beta of all cycles’ members (211 = 3^5 - 2^5), and also for the largest (1688). There’s no formula for the high cycle’s smallest member’s \beta = 319, or its largest \beta = 842, though these quantities can be pretty tightly bounded in terms of k and x.

Looking only at (putative) integer cycles, instead of rational cycles, involves different stuff.

7

Oh yeah I meant Terras and left out Everett. I’ll edit that.

That makes sense about CSTC since stopping time is defined as reaching a smaller number. So cycles may or may not have “extra downs steps”, and it wouldn’t affect CSTC, I assume.

It seems like “If Δn < 2^k - 3^x, then n < 2^k” might not be related to a standard result then. I tested it for n < 10,000,000 and I think the code is doing what I think it’s doing. I have another sub-result that depends on it which is why I’m interested.

Edited to add: Although it seems the above is usually true, if you set Δn in the sequence equation to 2^k - 3^x - 1 (the most extreme case), you get n < 2^k only if β < 2^k, which is low in the range of β discussed here.

I see you used k = ceil(n log2(3)). That assumes no “extra down steps” right? Or is it known for cycles? That reminds me, I’ve also heard the up and down steps must come from one of the continued fraction convergents for log2(3). This I think also implies no extra down steps if it’s true.

8

I see you used k = ceil(n log2(3))

No, I only assumed an integer cycle, see this discussion

9

You’re right, I need to spend more time reading the backlog here.