# Is the Collatz conjecture in $\Sigma_1 / \Pi_1$?

Prompted by some of the comments on this question, I'm wondering if anything is known about the place of the Collatz Conjecture in the arithmetic hierarchy. More specifically, is Collatz known to be equivalent to a $\Sigma_1$ or $\Pi_1$ statement? It's obvious that it can be expressed in the second level of the hierarchy, as $\forall n\exists k . C^{(k)}(n) = 1$ (and I believe functional composition is $\Delta_0$, so the fact that we're using a slightly extended language here should be moot; we can encode the computational path involved in computing $C^{(k)}(n)$ as a finite sequence of integers and thus as a single integer by appropriate coding), but there doesn't seem to be any obvious way of expressing it as a first-level statement...

-
The Collatz Conjecture can be written as a conjunction: (A) every Collatz sequence is bounded, and (B) the only Collatz orbit is $(1,4,2)$. Neither part is known to be true or false. But it seems like (B) is in $\Pi_1$, since it can be written as $\forall{n,k}.(C^{(k)}(n)=n)\rightarrow(n=1\vee n=2\vee n=4)$. –  mjqxxxx Jan 18 '12 at 19:12
@mjqxxxx: That looks right to me - (A) is definitely the tricky part, though, and it doesn't look to have an easy $\Pi_1$ formulation. I saw a slightly-sketchy looking paper on the web that seemed to say that questions about similar sequences were $\Pi^0_2$-complete and I seem to recall results along those lines about 'multi-Collatz' sequences with more than one iterable function (maybe from John Conway?), so I suspect there may not be any known answer for this. –  Steven Stadnicki Jan 18 '12 at 19:58
@mjqxxx: if we try to check (B) according to your last recipe, and if we are by accident on a divergent trajectory - isn't the result whether we are on an orbit or on a divergent trajectory not depending on the answer whether the current trajectory is in fact divergent? –  Gottfried Helms Jan 18 '12 at 20:39
The usual statement is $\Pi_2$, but since the Collatz conjecture is a sentence it is equivalent to either $0=1$ or $0=0$... (Assuming we're working in the standard model. If you're asking whether the conjecture is provably equivalent to a $\Pi_1$ or $\Sigma_1$ sentence over PA or ZFC, that's a different matter.) –  François G. Dorais Jul 31 '12 at 2:28

As suggested in my comment above, I will interpret your question as asking whether the Collatz conjecture is provably equivalent to a $\Pi_1$ or $\Sigma_1$ sentence over some base theory $T$. There are a variety of issues at stake depending on the outcome of the conjecture (in the standard model).

Case 0: The Collatz conjecture is false because some Collatz sequence is periodic with a period other than $4,2,1$. In that case, the Collatz conjecture is provably equivalent to $0=1$ over any theory with enough power to encode and decode the witnessing sequence up to its first repetition (e.g. PA or I$\Sigma_1$).

Case 1: The Collatz conjecture is false because some Collatz sequence never repeats itself. In that case, the conjecture is perhaps equivalent to a $\Pi_1$ sentence. To say that the Collatz sequence starting with some standard number $n_0$ is never repeating is a $\Pi_1$ statement. In the strange scenario where the Collatz sequences that don't repeat are precisely the ones that go through $n_0$, then the Collatz conjecture is equivalent to that $\Pi_1$ statement. More generally, if there is a (standard) finite list $n_0,n_1,\dots,n_k$ such that the Collatz sequences that don't repeat are precisely those that go through one of these, then we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. Still more generally, if there is a computable sequence $n_0,n_1,\dots$ with that property, we also have a $\Pi_1$ sentence equivalent to the Collatz conjecture. However, if no such computable sequence exists then it is unlikely that we can do better than $\Sigma_2$ unless we use a non-axiomatizable base theory like the $\Pi_1$ theory of the standard model.

Case 2: The Collatz conjecture is true. In that case, the Collatz conjecture is equivalent to the statement that $g(n) = (\mu k)(C^k(n)=1)$ is a total computable function. We can then compare $g$ to various levels of the fast-growing hierarchy for a more precise analysis. For example, if $g(n)$ is bounded above by some $f_k$ where $k$ is finite, then $g$ is actually primitive recursive and the Collatz conjecture is provably true in I$\Sigma_1$ (same as PA except that induction is restricted to $\Sigma_1$ formulas). If $g(n)$ is abounded above by some $f_\alpha$ with $\alpha \lt \varepsilon_0$, then the Collatz conjecture is provably true in PA. If $g$ grows faster than that then a still stronger theory is required to prove the Collatz conjecture.

-

I've never dealt much with the question of divergent trajectories (condition (A) in mjqxxx's comment), but the question of existence of orbits (condition (B)) can be translated into a question, whether finite sets $\small E_N$ of N integer parameters $\small \left<A,B,C,\ldots,H \right>$ where $\small A,B,\ldots,H>0$ admit a rational solution of a related system of linear equations.
(Note: that parameters are used as exponents in the "Syracuse"-formulation of the Collatz-problem: $\small x_{k+1}=(3x_k +1)/2^A$ where $\small x_k$ is odd and A is such, that also $\small x_{k+1}$ is odd).

If we denote the number of the above parameters as N and their sum as S then N and S must be in a (not exact, but tight) relation, for instance $\small 1.5 N < S< 2N$ so the values of the parameters for any set $\small E_N$ are upper-bounded.

Moreover, the number of parameters, which equal 1 versus that which exceed 1 is related by the fact, that the 1 -parameters represent rising and >1-parameters represent falling steps in the "Syracuse"-notation

Then the question of the existence of nontrivial cycles of any specified length N can be solved by enumeration and the check of solutions: "has the solution integer value?" of the associated linear equation which has the form $\small x={Q(A,B,C,...,H) \over 2^S-3^N}$ where $\small Q(\ldots)$ is a linear composition of powers of 3 and 2 with exponents made from the parameters A,B,...,H. The amount of computation for each N is then limited by the number of combinatorical choices to satisfy the mentioned limitations for the set of N parameters . This is a kind of problem which can be solved by a supertask-machine because it is subfactorial for each N .

(I've done a related discussion about the existence of cycles in that "Syracuse"-view of the problem and the relation to the linear equation myself, but a more professional discussion of this point of view and the description of the equation (and for some specific types of cycles of a complete system of linear equations) is done for instance by John Simons 2007, one example online here or even better here in an updated joint article with Benne de Weger 2010, which I just found here)

-
Scanning through that paper, it does not seem that their results give a bound better than $\Pi^0_2$, while that same bound can be had directly from the problem. Is there a result in this paper that reduces the Collatz problem to $\Sigma^0_1$ or $\Pi^0_1$? –  Carl Mummert Apr 20 '12 at 16:46
Seconding what Carl said here, it looks like they have a different way of formulating the Collatz problem for any individual number $n$ as a $\Sigma_1$ statement, but the standard means for encoding the sequence of Collatz iterates already gave that; there's still the external universal quantifier of 'this holds true for all numbers' that their paper doesn't seem to do anything to change. (Unfortunately, the quantifier bounds in their statements that 'this is true if there exist numbers $w, t, \ldots$' go the wrong way) –  Steven Stadnicki Apr 20 '12 at 17:37