MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

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 & 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<13$ or $n=13$ ? There are probably some more interesting questions to ask.

So: do you know any research concerning such weaker classes of diophantine functions?

Best regards.

share|cite|improve this question
As far as I know, there is no (published) work on this topic. I agree it is interesting. See also… – Andrés E. Caicedo Dec 19 '12 at 21:49

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.