Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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). –  Arturo Magidin Jun 30 '12 at 16:14
    
@arturo magidin - i would like to know any number theory conjecture by the types of undecidable? –  Victor Jun 30 '12 at 16:22
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). –  Henning Makholm Jun 30 '12 at 17:16
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. –  Arturo Magidin Jun 30 '12 at 17:31
1  
For (first-order) Peano Arithmetic, google the Paris-Harrington Theorem, or Kanamori-McAloon. (But in these cases truth can be settled in ZFC.) –  André Nicolas Jun 30 '12 at 17:49
show 2 more comments

2 Answers 2

up vote 6 down vote accepted

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).

share|improve this answer
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. –  Henning Makholm Jun 30 '12 at 17:18
1  
This is why I began with "perhaps". I understand the statement of Hilbert's Tenth Problem. –  user02138 Jun 30 '12 at 17:22
add comment

[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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.