[FOM] 664: Unsolvability in Number Theory

Tue Mar 1 00:08:04 EST 2016

Before I start burying myself in writing manuscripts on Mathematically
Natural Concrete Incompleteness, I thought I would write a little
something about that other main foundational theme - Perfectly
Mathematically Natural Algorithmic Unsolvability.

In contrast, Mathematically Natural Algorithmic Unsolvability had
already been achieved by the time I got out of school in 1967. Here
are two clear examples:

1. Are two finitely presented groups isomorphic? No, by Adian and
Rabin, 1957, 1958, independently.
2. Are two finite simplicial complexes homeomorphic? No, by Markov, 1958.

See http://www-math.mit.edu/~poonen/slides/cantrell3.pdf

In 1967, the overarching issue in Mathematically Natural Algorithmic
Unsolvability was to move it into the realm of number theory. Major
progress on Hilbert's 10th Problem had been made by then, and three
years later, it was solved in the negative by Matijasevich, building
on the work of Robinson, Davis, Putnam, in reverse historical order.
It is commonly called the MRDP theorem, or the DPRM theorem.

So at this point, I don't know of any clear overarching issue in
Mathematically Natural Algorithmic Unsolvailibty - like the
overarching issue of Concreteness for Mathematically Natural
Incompleteness. But there are some potential striking breakthroughs
that have eluded us.

Specifically, in number theory, there are many opportunities for
improving on MRDP. Arguably, the most spectacular would be to show the
following.

3. Whether two variable cubics with integer coefficients have a
solution in integers, is unsolvable(?)

Along the lines of showing unsolvability based on the degree and
number of variables, there hasn't been any or at least not much
improvement on the ones given in

James P. Jones. Universal Diophantine equation. Journal of Symbolic
Logic, 47(3):549-571, 1982.

(4,58), (8,38), (12,32), (16,29),
(20,28), (24,26), (28,25), (36,24),
(96,21), (2686,19), (2 x 10^5,14),
(6.6 x 10^43,13), (1.3 x 10^44,12),
(4.6 x 10^44,11), (8.6 x 10^44,10),
(1.6 x 10^45,9)

I.e., 58 variable quartics, and also 9 variable degree 10^45
Diophantine equations over the nonnegative integers are
algorithmically unsolvable.

4. Whether a polynomial with integer coefficients has a solution in
rationals, is unsolvable(?)

5. Whether a polynomial with integer coefficients has a solution in
various number fields, and rings, is unsolvable(?) See
http://www-math.mit.edu/~poonen/papers/aws2003.pdf

I want to turn to a related kind of number theoretic decision problem,
but which does not directly involve polynomials.

Let S be a piecewise linear subset of Z^n with integer coefficients.
Does S contain an element(s) of a certain simple kind?

6. A perfect square in Z^n (i.e., an n-tuple of squares)?

7. A prime in Z^n (i.e., an n-tuple of primes)?

I don't know the answer to 6 or 7.

There is a much easier result to obtain:

8. It is not algorithmically solvable whether S contains an element
and its square. This is unsolvable for any sufficiently large fixed
dimension n.

**********************************************************
My website is at https://u.osu.edu/friedman.8/ and my youtube site is at
https://www.youtube.com/channel/UCdRdeExwKiWndBl4YOxBTEQ
This is the 664th in a series of self contained numbered
postings to FOM covering a wide range of topics in f.o.m. The list of
previous numbered postings #1-599 can be found at the FOM posting
http://www.cs.nyu.edu/pipermail/fom/2015-August/018887.html

600: Removing Deep Pathology 1  8/15/15  10:37PM
601: Finite Emulation Theory 1/perfect?  8/22/15  1:17AM
602: Removing Deep Pathology 2  8/23/15  6:35PM
603: Removing Deep Pathology 3  8/25/15  10:24AM
604: Finite Emulation Theory 2  8/26/15  2:54PM
605: Integer and Real Functions  8/27/15  1:50PM
606: Simple Theory of Types  8/29/15  6:30PM
607: Hindman's Theorem  8/30/15  3:58PM
608: Integer and Real Functions 2  9/1/15  6:40AM
609. Finite Continuation Theory 17  9/315  1:17PM
610: Function Continuation Theory 1  9/4/15  3:40PM
611: Function Emulation/Continuation Theory 2  9/8/15  12:58AM
612: Binary Operation Emulation and Continuation 1  9/7/15  4:35PM
613: Optimal Function Theory 1  9/13/15  11:30AM
614: Adventures in Formalization 1  9/14/15  1:43PM
615: Adventures in Formalization 2  9/14/15  1:44PM
616: Adventures in Formalization 3  9/14/15  1:45PM
617: Removing Connectives 1  9/115/15  7:47AM
618: Adventures in Formalization 4  9/15/15  3:07PM
619: Nonstandardism 1  9/17/15  9:57AM
620: Nonstandardism 2  9/18/15  2:12AM
621: Adventures in Formalization  5  9/18/15  12:54PM
622: Adventures in Formalization 6  9/29/15  3:33AM
623: Optimal Function Theory 2  9/22/15  12:02AM
624: Optimal Function Theory 3  9/22/15  11:18AM
625: Optimal Function Theory 4  9/23/15  10:16PM
626: Optimal Function Theory 5  9/2515  10:26PM
627: Optimal Function Theory 6  9/29/15  2:21AM
628: Optimal Function Theory 7  10/2/15  6:23PM
629: Boolean Algebra/Simplicity  10/3/15  9:41AM
630: Optimal Function Theory 8  10/3/15  6PM
631: Order Theoretic Optimization 1  10/1215  12:16AM
632: Rigorous Formalization of Mathematics 1  10/13/15  8:12PM
633: Constrained Function Theory 1  10/18/15 1AM
634: Fixed Point Minimization 1  10/20/15  11:47PM
635: Fixed Point Minimization 2  10/21/15  11:52PM
636: Fixed Point Minimization 3  10/22/15  5:49PM
637: Progress in Pi01 Incompleteness 1  10/25/15  8:45PM
638: Rigorous Formalization of Mathematics 2  10/25/15 10:47PM
639: Progress in Pi01 Incompleteness 2  10/27/15  10:38PM
640: Progress in Pi01 Incompleteness 3  10/30/15  2:30PM
641: Progress in Pi01 Incompleteness 4  10/31/15  8:12PM
642: Rigorous Formalization of Mathematics 3
643: Constrained Subsets of N, #1  11/3/15  11:57PM
644: Fixed Point Selectors 1  11/16/15  8:38AM
645: Fixed Point Minimizers #1  11/22/15  7:46PM
646: Philosophy of Incompleteness 1  Nov 24 17:19:46 EST 2015
647: General Incompleteness almost everywhere 1  11/30/15  6:52PM
648: Necessary Irrelevance 1  12/21/15  4:01AM
649: Necessary Irrelevance 2  12/21/15  8:53PM
650: Necessary Irrelevance 3  12/24/15  2:42AM
651: Pi01 Incompleteness Update  2/2/16  7:58AM
652: Pi01 Incompleteness Update/2  2/7/16  10:06PM
653: Pi01 Incompleteness/SRP,HUGE  2/8/16  3:20PM
654: Theory Inspired by Automated Proving 1  2/11/16  2:55AM
655: Pi01 Incompleteness/SRP,HUGE/2  2/12/16  11:40PM
656: Pi01 Incompleteness/SRP,HUGE/3  2/13/16  1:21PM
657: Definitional Complexity Theory 1  2/15/16  12:39AM
658: Definitional Complexity Theory 2  2/15/16  5:28AM
659: Pi01 Incompleteness/SRP,HUGE/4  2/22/16  4:26PM
660: Pi01 Incompleteness/SRP,HUGE/5  2/22/16  11:57PM
661: Pi01 Incompleteness/SRP,HUGE/6  2/24/16  1:12PM
662: Pi01 Incompleteness/SRP,HUGE/7  2/25/16  1:04AM
663: Pi01 Incompleteness/SRP,HUGE/8  2/25/16  3:59PM

Harvey Friedman