4
$\begingroup$

I have written some code that searches for counter-examples to the Collatz conjecture. The following fact enables me to accelerate the search.

In the paper "Garner, Lynn - On The Collatz 3n + 1 Algorithm" Garner claims it is "not hard to verfiy" that the following rules hold.

enter image description here

I have spent about a week trying to prove the general version of this result, but have not succeeded. I will define the terms in Garner's paper, and would be grateful for any help.

The Collatz map $c:\mathbb{N}\to\mathbb{N}$ is defined by

$c\left(n\right):=\frac{1}{2}\begin{cases} 3n+1 & n\text{ odd}\\ n & n\text{ even} \end{cases}$

Given a seed $n\in\mathbb{N}$ the Collatz sequence is defined as $\left\{ c^{p}\left(n\right)\mid p\in\omega\right\}$, where as usual $c^{0}\left(n\right)=n$ and $c^{p+1}\left(n\right)=c\left(c^{p}\left(n\right)\right)$ for all $n\in\mathbb{N}$.

Given any $n\in\mathbb{N}$ the stopping time $\sigma\left(n\right)$ is the smallest $p\in\mathbb{N}$ such that $c^{p}\left(n\right)<n$. If the Collatz conjecture is true every Collatz sequence has a finite stopping time.

I am after the theorem that says something like; Given $n,m\in\mathbb{N}$, $\sigma\left(n\right)=m$ whenever $n\equiv p\mod{2^{q}}$ for $p,q$ with THIS property. My question is what is THIS property?

$\endgroup$
5
  • 3
    $\begingroup$ THIS property is the result of empirical calculation. For example if $n=16k+3$ then the following Collatz steps are $48k+10$, $24k+5$, $72k+16$, $36k+8$, $16k+4$, $8k+2$ which is less than $16k+3$ after $6$ steps. Check which remaining values modulo a power of $2$ fall out earliest before you hit an undecidable position of $k+$something, and then move on to the next power of $2$ $\endgroup$
    – Henry
    Sep 4, 2021 at 0:31
  • $\begingroup$ Given $p$ run Collatz map till you get an $m$ with $c^m(p)<p.$ Then take $q$ big enough (that would often result in $p<2^q$) so that if $n\equiv p\mod{2^{q}}$ then $n$ has exactly the same sequence of "ups" and "downs" as $p$ does, at least for the initial part of the sequence with the first $m$-many iterations. If $n>p$ this would result in $c^m(n)<n.$ There are two problems with this approach. First, occasionally you will need to wait a lot to get to $c^m(p)<p.$ Second, $q$ may need to get big too, always making necessary to consider more and more cases. (Not an answer for "THIS" property.) $\endgroup$
    – Mirko
    Sep 4, 2021 at 2:17
  • $\begingroup$ One of my deleted questions : math.stackexchange.com/questions/4218434/… $\endgroup$ Sep 4, 2021 at 15:38
  • $\begingroup$ I also contend these aren't hard to verify. I can Almost generalize this to arbitrary integer polynomials. $\endgroup$ Sep 4, 2021 at 15:47
  • $\begingroup$ Thanks Henry, Mirko and Roddy MacPhee. Your answers definitely got me thinking about this in a different way. $\endgroup$ Sep 4, 2021 at 20:39

2 Answers 2

3
$\begingroup$

These numbers come from explicitly writing out the iterates of the Collatz function and seeing, from that, which numbers have which stopping times. If you want to condense the property being discussed, it's as follows: we can compute that $$c^q(x\cdot 2^q+p)=\alpha x + \beta$$ for some integer constants $\alpha$ and $\beta$. If $\alpha < 2^q$, then, for all great enough $n$ equivalent to $p$ mod $2^q$, we will have $c^q(n) < n$ - and we can use this to create the sort of statements in your question.

It's best to illustrate this with an example. To see that the stopping time of $32x + 11$ is $5$ (for the $c$ in the question*), one could calculate: $$c(32x+11) = 48x + 17$$ $$c^2(32x+11) = 72x + 26$$ $$c^3(32x+11) = 36x + 13$$ $$c^4(32x+11) = 54x + 20$$ $$c^5(32x+11) = 27x + 10$$ Where, for $x\geq 0$, it's clear that the first four iterates are greater than the input, and the fifth is less than the input - hence the stopping time is $5$. Note that we cannot compute the sixth iterate, since $27x+10$ could be either even or odd.

You can run a similar sort of calculation to explicitly get the first $q$ iterates of $c$ applied to $2^q\cdot x + p$ for any $p$ as a linear function of $x$ - and doing such a calculation might reveal the stopping time of numbers of that form (as it did in the example I gave).

If you wanted to generate the list they made in the paper, what you can do is calculate this for every possible mod $2$ residue, and note which residues have fixed stopping times. Then, of those residues which did not have fixed stopping times, you can split them into two residue classes mod $4$, and see if any of those have fixed stopping times (now being able to calculate one more iteration in the future). Then, you can split into residues mod $8$ and so on, until you are satisfied. Note that the number of residues remaining mod $2^q$ will grow exponentially (although the proportion of residues lacking a stopping time will decrease towards $0$).

You can be a bit more sophisticated with this, although it's not clear it would be useful for your application. If you fix the parities of the sequence $x, c(x), c^2(x),\ldots, c^{n-1}(x)$, there is a unique equivalence class mod $2^n$ such that $x$ in that class will have a trajectory with the specified parities - for instance, there is some mod $8$ equivalence class such that $x$ is even, $c(x)$ is odd, and $c^2(x)$ is even. You can note that, for $x$ in that class, we must have $c^n(x)=\alpha x + \beta$ for some rational $\alpha$ and $\beta$ - and can explicitly compute $$\alpha = (3/2)^{\text{# of odd steps in trajectory}}\cdot (1/2)^{\text{# of even steps in trajectory}}.$$ This can give the asymptotic results noted in the paper, but is probably not the most efficient way to generate a list of all classes that don't stop after some number of steps.

(*The paper you quote appears to use the version of the Collatz function that takes two steps to go from odd $x$ to $\frac{1}2(3x+1)$, so gets $8$ instead - but it's the same idea with that method, although it works somewhat less elegantly with that slower function)

$\endgroup$
4
  • $\begingroup$ $x^2+x+1\to 3x^2+3x+4$ seems more exciting lol $\endgroup$ Sep 4, 2021 at 19:52
  • $\begingroup$ Thanks @Milo Brandt, that is a really helpful answer! $\endgroup$ Sep 4, 2021 at 20:40
  • $\begingroup$ @Roddy MacPhee, it sound like you have something to add, can you share it? $\endgroup$ Sep 4, 2021 at 20:41
  • $\begingroup$ @Mark Kortink It's just you can tell certain polynomials with integer coefficients always have a certain parity when evaluated at integers, so theory can somewhat be generalized to arbitrary polynomials. $\endgroup$ Sep 4, 2021 at 20:44
0
$\begingroup$

Based on previous answers I have done more analysis and identified a way of finding rules that eliminate a seed n as a candidate for violating the Collatz conjecture. Considering modular restrictions as discussed here on Wikipedia we get the following.

Fact. If for some $k\ge0$ and $2^{k}>b\ge0$ we have $c^{k}\left(2^{k}a+b\right)<2^{k}a+b$ for all $a>0$, then the first number $n$ for which the Collatz sequence does not reach $1$, if it exists, cannot be $b\mod2^{k}$, that is $n\not\equiv b\mod2^{k}$. Recalling that $m\equiv n\mod2^{k}$ iff $m-b=a2^{k}$ for some $a\in\mathbb{Z}$, note that saying $m$ cannot be $b\mod2^{k}$ means that $m\neq a2^{k}+b$ for any $a\in\mathbb{Z}$.

Regarding a Collatz sequence as a partity sequence as described here on Wikipedia we observe that $c^{p}\left(a2^{k}+b\right)=a3^{c\left(p,k,b\right)}+c^{p}\left(b\right)$ and so is linear in $a$ and can therefore be determined by any two points on its line.

By the Fact we are interested in the $p=k$ case. The obvious points on the line to take are $\left(0,c^{k}\left(b\right)\right)$ and $\left(1,c^{k}\left(2^{k}+b\right)\right)$, and these are easily calculated. The line through these two points is then $y\left(a\right)=\left(c^{k}\left(2^{k}+b\right)-c^{k}\left(b\right)\right)a+c^{k}\left(b\right)$

Substituting back into the Fact above we require $\left(c^{k}\left(2^{k}+b\right)-c^{k}\left(b\right)\right)a+c^{k}\left(b\right)<2^{k}a+b$ for all $a>0$. By simple geometry this will be the case iff

  • $c^{k}\left(2^{k}+b\right) \le c^{k}\left(b\right)+2^{k}$

  • $c^{k}\left(b\right) \le b$

  • $c^{k}\left(2^{k}+b\right) < 2^{k}+b$

We will say $\left(k,b\right)\in\omega^{2}$ is an elimination rule iff it satisfies these equations. We can then say that the Collatz sequence with seed $n$ will reach $1$ if it is $b\mod2^{k}$. In other words $n$ is not a candidate for violating the Collatz conjecture.

Let $\left(k,b\right)$ and $\left(k^{\prime},b^{\prime}\right)$ be elimination rules. It is reasonably easy to show that if $k\ge k^{\prime}$ and $0\equiv\left(b-b^{\prime}\right)\mod2^{k^{\prime}}$ then $\left(k,b\right)$ is subordinate to $\left(k^{\prime},b^{\prime}\right)$ in the sense that being $b\mod2^{k}$ implies being $b^{\prime}\mod2^{k^{\prime}}$. For example being $0\mod2^{3}$ (divisible by 8) implies being $0\mod2^{1}$ (even). Given this we can ignore subordinate rules when trying to eliminate $n$.

The following python script generates all non-redundant elimination rules up to k_max. With k_max=8 it generates rules that eliminate about 93% of seeds.

def collatz_seq(seed,p=0):
    # Return c^p(seed). 
    c=seed
    s=[seed]
    k=0
    while True:
        if seed>0 and c<=1:break
        if p!=0 and k==p:break
        c=int(c/2) if (c%2) == 0 else int((3*c+1)/2)
        s+=[c]
        k+=1
    return s[-1]

def cka2kb_test(k,b):
    """
    Work out the line for c^k(a*2^k+b) and compare to a*2^k+b.
    If LHS < RHS for all a>0 then (k,b) is an elimination rule. 
    """  
    # Get two points on the c^k(a*2^k+b) line.  
    pts=[]
    for a in range(2):
        pts+=[(x:=a*(2**k)+b,collatz_seq(x,k))]
    # Work out the equation of the b line a*2^k+b line. 
    b_line=(pts[1][0]-pts[0][0],pts[0][0])
    # Work out the equation of the c line c^k(a*2^k+b) line. 
    c_line=(pts[1][1]-pts[0][1],pts[0][1])
    # Test if lines c^k(a*2^k+b) < a*2^k+b for a>0. 
    vfy=(c_line[0]<=b_line[0]) # c line slope <= b line slope. 
    vfy=vfy and (c_line[1]<=b_line[1]) # c line intercept <= b line intercept. 
    vfy=vfy and (c_line[0]+c_line[1]<b_line[0]+b_line[1]) # c line < b line at 1. 
    return {'verified':vfy,
            'cka2kb':c_line,
            'a2kb':b_line,
            }

def is_in_rules(rule,rules):
    # Check if exclusion rule is subordinate to an existing rule. 
    for r in rules:
        subord=(rule[0]>=r[0])
        x=(rule[1]-r[1])/(2**r[0])
        subord=subord and (x.is_integer()) 
        if subord: 
            return True
    return False

def find_exclusion_rules(k_max=8):
    # Find (k,b) such that c^k(a*2^k+b) < a*2^k+b for all a. 
    # With k_max=8 (2^k=256) this accounts for 93% of seeds. 
    # With k_max=16 (2^k=65,536) evaluates in reasonable time. 
    rules=set()
    for k in range(1,k_max+1):
        for b in range(2**k):
            # skip if (k,b) equiv to found rule
            if is_in_rules((k,b),rules):continue
            # test all a for this (k,b)
            vfy=cka2kb_test(k,b)
            if vfy['verified']:rules.add((k,b))
    rules=list(rules)
    rules.sort()
    return rules

if __name__ == '__main__':
    excl_lvls=8
    rules=find_exclusion_rules(excl_lvls)
    print(rules)

The elimination rules the script generates with k_max=8 are [(1, 0), (2, 1), (4, 3), (5, 11), (5, 23), (7, 7), (7, 15), (7, 59), (8, 39), (8, 79), (8, 95), (8, 123), (8, 175), (8, 199), (8, 219)].

For example consider the rule $(7,15)$, this means that if $n$ is $15\mod2^7$ then the Collatz sequence starting with $n$ reaches $1$, and so is not a candidate for violating the Collatz conjecture. Compare this to the rule from my original question which asserts the stopping time is $11$ if $n$ is $15\mod 128$.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .