[FOM] Could it be that a "typical" Diophantine set is computable?
Kreinovich, Vladik
vladik at utep.edu
Wed Jul 5 16:00:49 EDT 2017
Here is a possible formal meaning of your statement. Let us effectively enumerate all Diophantine sets, and for some n, let us consider sets S_1, …, S_n in this enumeration.
Cartesian products of Diophantine sets are also Diophantine sets, with a simple pairing function transformation into sets of integers.
For any d, if we consider products S_{i_1} X … X S_{i_d} of d sets S_{i_k}, I _k <= n, then we get n^d possible product sets.
The whole class of Diophantine sets can be obtained if we tend both n and d to infinity.
A Cartesian product A X … X B is decidable if and only if all the sets A, …, B are decidable. Let m(n) denote the number of decidable sets among the first n Diophantine sets S_1, …, S_n. Then out of n^d possible Cartesian products, (m(n))^d are decidable, so the proportion of decidable products is (m(n) / n)^d.
Since some Diophantine sets are undecidable, for large n, we get m(n) < n and m(n) / d < 1. Thus, for all sufficiently large n, when d tends to infinity we have (m(n) / n)^d tends to 0, so this proportion tends to 0. This is true for every n, so the limit of this limit when n --> infinity is also 0.
In this sense, the proportion of decidable sets is 0, and thus, almost all Diophantine sets are undecidable.
> On Jul 2, 2017, at 8:36 PM, Timothy Y. Chow <tchow at alum.mit.edu<mailto: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?
>
> Tim
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170705/4792b4f6/attachment.html>
More information about the FOM
mailing list