[FOM] Could it be that a "typical" Diophantine set is computable?

[Joe Shipman]

There is a lot to be learned from the interplay of different notions of "most". 

For example, most irreducible polynomials have symmetric galois groups, but most algebraic numbers in any given algebraic number field have an irreducible polynomial with a "small" Galois group relative to its degree. 

Reflecting on this tension led to the insights I needed to improve the Fundamental theorem of Algebra. (Gauss's version: any field of characteristic 0 in which all polynomials whose degree is 2 or an odd number have roots is algebraically closed. My version eliminates the characteristic 0 assumption, weakens "2 or odd" to "prime", and gives a computable criterion for all implications between statements that polynomials of various degrees always have roots.) 

-- JS

Sent from my iPhone

> On Jul 2, 2017, at 8:36 PM, Timothy Y. Chow <tchow at alum.mit.edu> wrote:
> 
> By the MRDP theorem, a set is Diophantine if and only if it is computably enumerable.
> 
> The impression I've gotten---although I don't think I've seen it explicitly asserted anywhere---is that in some sense "most" Diophantine sets are *not* computable.  Are there any results, or even heuristic arguments, in this direction?
> 
> Of course it is not clear what I mean by "most Diophantine sets."  One way to make this a little more precise is to imagine that we pick a polynomial
> 
>  P(x1,x2,...,xj,y1,y2,...,yk)
> 
> with integer coefficients according to some probability distribution and then consider the set of assignments to (x1,x2,...,xj) such that the resulting polynomial in (y1,y2,...,yk) has a zero.  This is still not quite precise because I haven't specified the probability distribution, but you get the idea: Is there some sense in which a "random" or "arbitrary" choice of P will "usually" result in an undecidable problem?
> 
> This question came up indirectly on MathOverflow:
> 
> https://mathoverflow.net/questions/115430/what-is-the-geometry-of-an-undecidable-diophantine-equation
> 
> One respondent was surprised when I stated my expectation that undecidability was "generic"; he said that in the context of combinatorial group theory, there is a condition called "hyperbolicity" that (a) is "probabilistically generic" and (b) implies the solvability of all the usual problems (word problem, isomorphism problem, etc.).  So perhaps I'm wrong that "average" Diophantine sets are not computable.
> 
> Tim
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom