4
$\begingroup$

Is there a short Diophantine definition of the sum-of-divisors function? Is there a polynomial $p$ such that $$c = \sum_{d|n}d \ \leftrightarrow \ \exists x_1, \ldots x_{100}\ p(c,n,x_1, \ldots x_{100})=0\ ?$$

This comes from a MathStackExchange post, where I suggested that standard algorithms would produce a polynomial in thousands of variables. Can we do significantly better, maybe with a bit more number theory?

A short definition in Diophantine or exponential Diophantine terms would help give a similarly short and Diophantine version of the Riemann hypothesis.

Improve this question
$\endgroup$
5
  • 2
    $\begingroup$ IIRC there are universal diophantine equations in only tens of variables, but enormous degree. $\endgroup$
    – joro
    Commented Jan 19, 2018 at 8:19
  • 3
    $\begingroup$ (For slower types like me: IIRC="if I recall correctly".) Now, even if the function in question, or RH, or other conjectures, where encoded by a Diophantine equation with only tens of variables and not huge degree, what would that be useful for? Could it remotely, conceivably, be more practical to look for counterexamples that way than directly in the encoded problem? $\endgroup$
    – Yaakov Baruch
    Commented Jan 19, 2018 at 9:36
  • 2
    $\begingroup$ Jones, Universal Diophantine Equation, lists various variables–degree possibilities in Thm. 4; it shows that small number of variables and small degree are simultaneously possible (around 25). Also, he mentions on the next page that one can write a universal Diophantine equation of arithmetic circuit complexity $<100$ (i.e., the number of additions and multiplications). $\endgroup$
    – Emil Jeřábek
    Commented Jan 19, 2018 at 17:53
  • $\begingroup$ @EmilJeřábek, thanks; that answers the question as stated. I had in mind something with degree < 10, variables < 100, coefficients < 1000, but it never occurred to me that people would use polynomials so wild in so many ways. $\endgroup$
    – user44143
    Commented Jan 19, 2018 at 22:01
  • $\begingroup$ @YaakovBaruch, if we’re in the realm of remote possibilities, why not search for a proof instead? With an elegant statement in exponential-Diophantine terms, a strong theorem-prover for such statements, and a good search algorithm, one can always hope. $\endgroup$
    – user44143
    Commented Jan 19, 2018 at 22:49

0

Reset to default

You must log in to answer this question.