1
$\begingroup$

Are there Diophantine equations in two variables such that counting solutions $\mathrm{mod}\:p$ requires $O(p^2)$ time?

Geometrically this means we have to sort through a positive proportion of the affine plane before being sure we have counted all solutions (modulo the complexity of addition and multiplication).

Non-example: it takes $O(\log p)$ time to count (and output) the $\mathrm{mod}\:p$ solutions of $x+y=0$ as there are $p$ solutions.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ When you say 'diophantine equation' I presume you mean polynomial? (And presumably you mean $\Theta(p^2)$ rather than $O(p^2)$, since e.g. $\log p\in O(p^2)$). And for that matter, do you know of an example where the best known algorithms take even $\Omega(p)$ time? Elliptic curves, for instance, have much faster algorithms known... $\endgroup$
    – Steven Stadnicki
    Commented Sep 16, 2021 at 23:43
  • $\begingroup$ The definition in en.wikipedia.org/wiki/Diophantine_equation requires it to be polynomial. I don't mean $\Theta(p^2)$ I mean $\Omega(p^2)$ in Knuth's sense but since there is ambiguity about $\Omega$ I didn't want to use it and instead opted for "requires $O(p^2)$ time." Sorry for any confusion. $\endgroup$
    – Disen
    Commented Sep 17, 2021 at 5:55

1 Answer 1

Reset to default
4
$\begingroup$

At least for fixed degree, the answer appears to be 'no' — it seems to be well-established that the number of roots of a univariate polynomial $g(x)$ of degree $d$ modulo a prime $p$ can be determined in $O\left((d+\log p)^{O(1)}\right)$ time, which gives a quasilinear time algorithm for a polynomial $f(x,y)$ by just evaluating $f()$ at each value of $y$ to find $p$ univariate polynomials (which can be done in basically $O(dp)$ time) and count the number of roots for each in turn. This means that for any fixed polynomial, it can be done in $O(p(\log p)^{O(1)})$ time as $p$ increases. I don't know whether you can get time sub-linear in $p$, though I wouldn't be surprised if it was an open question. Note that 'linear in $p$' here is still exponential in the size of the input (giving $p$ in binary) and that's the usual metric for this sort of problem for large $p$, so the usual target here is really something in $p^{o(1)}$.

If we allow for an arbitrary polynomial of degree $\lt p$ then this no longer works, but note that then the input naively has size $\Theta(p^2)$ so we can't even read all the data in less time then that. The one case I can't account for is the case of sparse bivariate polynomials of arbitrarily high degree mod $p$, where it seems from at least a bit of digging like not much is specifically known.

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ I think sublinear in $p$ is known for hyperelliptic curves, at least, by Harvey's variant of Kedlaya's $p$-adic algorithm. $\endgroup$
    – Will Sawin
    Commented Sep 17, 2021 at 17:34

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .