[FOM] Could it be that a "typical" Diophantine set is computable?
Todd Rowland
rowland at wolfram.com
Tue Jul 4 20:53:18 EDT 2017
It is safe to say that the status of most Diophantine equations is unknown, because in any reasonable enumeration one quickly goes beyond the classes of equations with known techniques.
Even the decidability for some of the simplest ones is unknown. See for example this list in Wolfram's A New Kind of Science http://www.wolframscience.com/nks/p790 A box means there are no solutions. The unknown ones are left blank. This list was checked by experts in 2002. What would be of interest to the theme of his book would be the simplest universal example. One expects that universality is common according to his Principle of Computational Equivalence .
The experimental evidence is not so clear with Diophantine equations compared with cellular automata. There are no visual tools for experimenting with equations. With cellular automata, it is easy to run random rules with many colors and it does not take long to realize that they are almost all complex, and experimentally at least, the typical cellular automaton has universal behavior (and hence rife with undecidability).
With Diophantine equations, one expects that a decent fraction of equations will have no solutions for trivial reasons, such as 2x+3y=1 has no solutions in positive x,y, and that a decent fraction have easily found small solutions (there is an interesting story about simple equations with large solutions).
What fraction are trivially decidable depends on the choice of enumeration, which is largely a matter of choice, more so with equations than finite groups or other mathematical objects.
----- On Jul 3, 2017, at 6:25 PM, Joe Shipman <joeshipman at aol.com> wrote:
> 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
> _______________________________________________
> FOM mailing list
> FOM at cs.nyu.edu
> http://www.cs.nyu.edu/mailman/listinfo/fom
-------------- next part --------------
An HTML attachment was scrubbed...
URL: </pipermail/fom/attachments/20170704/059b09cc/attachment.html>
More information about the FOM
mailing list