User tms - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-22T03:14:18Z http://mathoverflow.net/feeds/user/29263 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/116779/weak-classes-of-diophantine-functions Weak classes of diophantine functions tms 2012-12-19T11:27:44Z 2012-12-19T13:57:09Z <p>From a well-known work(s) by Putnam, Davis, Robinson and Matiyasevich, we know that every partially recursive function is diophantine. Now it seems a natural question to ask: can we say something nontrivial about classes of diophantine functions that corresponds to some weaker classes of functions from computability theory (e.g. Kalmar elementary or primitive resursive functions)? I have not seen any work on this topic. Have I missed something? Or maybe there is no "naturally occuring" characterization of weaker classes of functions in term of diophantine equations? </p> <p>I know this question may sound vague, but surely one can think of some more specific problems. We know, for example, that problem of existence of solutions for an arbitrary diophantine equation can be reduced to similar problem for some diophantine equation with 13 arguments (Y. Matiyasevich &amp; J. Robinson 1975). Let's take only those diophantine equations that define primitively recursive functions (or Kalmar elementary). Clearly, there is the smallest $n\leq 13$ such that problem of existence of solutions for those equations can be reduced to existence of solutions for some $n$-ary equations. Is $n&lt;13$ or $n=13$ ? There are probably some more interesting questions to ask.</p> <p>So: do you know any research concerning such weaker classes of diophantine functions?</p> <p>Best regards.</p>