7
$\begingroup$

Is there any famous number theory conjecture proven undecidable?

Is there any history about it?

i would like to know any number theory conjecture by the types of undecidable.

  • 6
    "Proven impossible to be find out thee truth or false". Do you mean, "proven to be [formally] undecidable"? If that's what you mean, *in what formal theory*? (There is no *absolute* undecidability).2012-06-30
  • 0
    @arturo magidin - i would like to know any number theory conjecture by the types of undecidable?2012-06-30
  • 0
    @ArturoMagidin Is there any more undecidable problem apart from the celebrated Hilbert's 10th? For instance, does the [word problem for groups](http://en.wikipedia.org/wiki/Word_problem_for_groups) has any number theoretic analogue?2012-06-30
  • 1
    @rsg: I think that's a different meaning of "undecidable". "Undecidable" can either mean "not computable" or "independent of some particular axiom system". The former does not apply to single conjectures, so Victor must have the latter in mind. (This latter meaning seems to be disfavored by professionals, but continues to be used in more popular works due to Gödel's use of the word in that sense).2012-06-30
  • 1
    @Victor: I'm sure you would like to know a lot of things. But because you are being **unclear** about what it is you want, it's hard to help you. "any number theory conjecture by the types of undecidable" is, to me unparsable and incomprehensible.2012-06-30
  • 0
    Once a statement is proven to be undecidable (in whatever formal system) it's no longer a conjecture, since its truth or falsity cannot be established.2012-06-30
  • 1
    For (first-order) Peano Arithmetic, google the Paris-Harrington Theorem, or Kanamori-McAloon. (But in these cases truth can be settled in ZFC.)2012-06-30

2 Answers 2

6

Perhaps Hilbert's Tenth Problem and Matiyasevich's Theorem are what you have in mind. Here are some particular points taken from the two wikipages:

Corresponding to any given consistent axiomatization of number theory, one can explicitly construct a Diophantine equation which has no solutions, but such that this fact cannot be proved within the given axiomatization. Hilbert's tenth problem asks for a general algorithm deciding the solvability of Diophantine equations. The conjunction of Matiyasevich's theorem with earlier results known collectively as the MRDP theorem implies that a solution to Hilbert's tenth problem is impossible.

Harold N. Shapiro and Alexandra Shlapentokh prove that Hilbert's tenth problem is unsolvable for the ring of integers of any algebraic number field whose Galois group over the rationals is abelian.

Later work has shown that the question of solvability of a Diophantine equation is undecidable even if the equation only has 9 natural number variables (Matiyasevich, 1977) or 11 integer variables (Zhi Wei Sun, 1992).

  • 3
    But that's not even a conjecture. One could perhaps say that the problem statement entails the _impicit_ conjecture that an algorithm for Diophantine satisfiability _exists_, but that implicit conjecture is _not_ undecidable -- it is now known to be _false_.2012-06-30
  • 1
    This is why I began with "perhaps". I understand the statement of Hilbert's Tenth Problem.2012-06-30
5

[references added, at bottom]

You know the Collatz problem, right? Start with a positive integer, if it's even, divide by 2, if it's odd, multiply by 3 and add 1, iterate and see what happens? The possibilities being that you eventually go into a cycle, or that you never go into a cycle?

Well, you can fit that problem into a family of problems where you fix a modulus $m$, and $m$ different linear functions $f_0,f_1,f_{m-1}$, and then given a positive integer you look at what the remainder would be if you were to divide it by $m$, and if that remainder would be $r$ you apply the function $f_r$ to the positive integer; you iterate this procedure, and again the question is whether you ever get into a cycle. The functions $f_i$ have to be chosen so that you always get integers out of the computations.

It has been proved that there is a modulus $m$ and a collection of functions $f_0,f_1,f_{m-1}$ such that the cycle question is undecidable.

I don't know whether this qualifies. For the original Collatz, the standard conjecture is that you always wind up in the cycle $4,2,1,4,2,1,\dots$. But original Collatz has not been proved undecidable. I don't know whether anyone has written down an explicit example of a problem in this family for which undecidablity can be proved, and I don't know what conjectures are out there about members of the family.

This is probably covered in Lagarias' book about $3x+1$.

EDIT: You can get the flavor of the argument here, although that looks like a preprint that needs some work. The published version of that paper is Kurtz, S. A. and Simon, J. "The Undecidability of the Generalized Collatz Problem," in Theory and Applications of Models of Computation: Proceedings of the 4th International Conference (TAMC 2007) held in Shanghai, May 22-25, 2007 (Ed. J.-Y. Cai, S. B. Cooper, and H. Zhu), Springer, Berlin, pp. 542-553, 2007. The published version is available at http://www.springerlink.com/content/e03333g2u28450q5/ but I think that's behind a pay wall.

Conway's paper on this is Conway, J. H., Unpredictable iterations, Proc. 1972 Number Th. Conf., University of Colorado, Boulder, Colorado, pp. 49-52, 1972. It's in the Lagarias book.