5
$\begingroup$

So I got an email from one of my colleagues on the Collatz Conjecture with a link to the article Computer Scientists Attempt to Corner the Collatz Conjecture by Kevin Hartnett in Quanta Magazine.

On digging through the conjecture, it seems it is not even known it is a $\Pi_1$ or $\Sigma_1$ statement. See the Math.StackExchange question Is the Collatz conjecture in $Σ_1/Π_1$?. For more information we can find details in the following thesis:

  • Matthew Alexander Denend, Challenging variants of the Collatz Conjecture, Masters Thesis, The University of Texas at Austin 2018, doi:10.26153/tsw/1559.

Does it mean they have already shown Collatz is a $\Sigma_1$ statement?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
12
$\begingroup$

It seems I was wrong - see Emre Yolcu's comment below.

My understanding is that that has not been accomplished (although the Quanta article is pretty vague so I could be misunderstanding the situation).

The Quanta article describes the following process:

  • Whip up a rewriting system which always terminates iff Collatz is true. This has been successfully done - but note that the termination problem is a priori $\Pi^0_2$, just like Collatz.

  • Try to find a collection of matrices satisfying some complicated constraints relating to that rewriting system. This is the task which SAT solvers are relevant for. However, they have not yet found an appropriate collection of matrices.

  • (This is where I was wrong:) Even after finding such a collection, we're not done. All that this will accomplish is reduce Collatz to a particular problem about matrix multiplication (which the Quanta article doesn't state - moreover, it doesn't explain why that problem should be more tractable than the rewriting one or the original Collatz conjecture).

Re: that third bulletpoint, I think that there's a particular part of the article which is potentially confusing:

“You try to find matrices that satisfy these constraints,” said Emre Yolcu, a graduate student at Carnegie Mellon who is working with Heule on the problem. “If you can find them, you prove [they’re] terminating,” and by implication, you prove Collatz.

It would have been clearer to write "If you can find them, you then try to prove [they're] terminating, and if you can you prove Collatz." That is, finding a system of matrices satisfying the given constraints - which is indeed $\Sigma^0_1$ - is only the first step, and the remaining fact we need to prove is presumably still $\Pi^0_2$.

Actually it seems I got that exactly wrong!

That said, pending further elaboration from Emre we may only have a $\Sigma_1$ sentence which implies Collatz - I don't know if the nonexistence of an appropriate matrix family would imply that Collatz fails.

Improve this answer
$\endgroup$
6
  • 3
    $\begingroup$ I was misquoted in the article—I actually said "If you can find them, this implies that the rewriting system is terminating." This is due to a method called "matrix interpretations" [1], widely used in proving termination of rewriting systems. Finding the matrices does settle the conjecture as true. We will put a preliminary writeup on arXiv soon. [1]: Endrullis, J., Waldmann, J. & Zantema, H. Matrix Interpretations for Proving Termination of Term Rewriting. J Autom Reasoning 40, 195–220 (2008). doi.org/10.1007/s10817-007-9087-9 $\endgroup$
    – Emre Yolcu
    Commented Sep 3, 2020 at 4:10
  • $\begingroup$ @EmreYolcu Oh, that's fascinating! I didn't know that at all. Do you know if the existence of such matrices is equivalent to Collatz, or merely sufficient for Collatz? $\endgroup$
    – Noah Schweber
    Commented Sep 3, 2020 at 4:13
  • 2
    $\begingroup$ As far as we know, it is merely sufficient. This method is basically searching for proofs of a certain size that fit a template, and if the search does not succeed after some time we modify the constraints to allow larger proofs and keep searching. There exist rewriting systems that are terminating but do not admit a direct matrix interpretation proof. For a given rewriting system, I imagine it might be possible to prove that if it is terminating then there is a matrix interpretation proof of this fact. We know of no such result for the system at hand. $\endgroup$
    – Emre Yolcu
    Commented Sep 3, 2020 at 4:36
  • 2
    $\begingroup$ @EmreYolcu Of course it certainly can't be equivalent in general since termination is $\Pi_2$-complete. $\endgroup$
    – Noah Schweber
    Commented Sep 3, 2020 at 4:43
  • 4
    $\begingroup$ It does not imply that Collatz is in $\Sigma_1$: as Noah says above, there is only a $\Sigma_1$ sentence implying Collatz, not one that is equivalent to it. $\endgroup$
    – Emre Yolcu
    Commented Sep 3, 2020 at 8:07

You must log in to answer this question.

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