2
$\begingroup$

Consider the following (NP-complete) problem:

Given a system of polynomials $f_1, f_2, \ldots, f_m \in \mathbb{F}_q[x_1, x_2, \ldots, x_n]$ of total degree at most $d$, find an $\mathbb{F}_q$-rational point (ie., a common solution in $\mathbb{F}_q$).

[Kayal, 2007] (cf. page 80) showed that for a fixed $n$, there is a deterministic algorithm with complexity $\mathsf{poly}(d, m, \log q)$ for the existential question (solvability). He also showed that there is an efficient approximation algorithm for counting the number of solutions.

I was unable to find any recent work in this direction, and was wondering if more has been discovered since 2007. In particular, I am interested in knowing whether there has been any progress with regards to the search problem (deterministic or randomized), perhaps even for the simpler case of $n = 2$.

Improve this question
$\endgroup$
6
  • $\begingroup$ Can't you use the usual trick to reduce search problems to existence problems? Substitute in a fixed value for the first coefficient and ask if there are any solutions. If it does, go to the next coefficient, if not, try a different value. This induces a loss of at most $mq$ which weakens the dependence on $\log q$ but keeps it on the other variables. $\endgroup$
    – Will Sawin
    Commented Jun 28 at 18:09
  • $\begingroup$ For practical needs, $q$ is typically a very large prime (say, exponential in the parameters), so this would be inefficient. This is also the assumption in work cited. Note: I had mixed up my use of $n$ and $m$ earlier. It is fixed now. $\endgroup$
    – aayad
    Commented Jun 28 at 18:17
  • 2
    $\begingroup$ The algorithm proceeds by finding a transformation between the algebraic solution set and a hypersurface and proving the hypersurface has many rational points. Here "many" means "close to $q^{k-1}$ for a hypersurface in $\mathbb F_{q^k}$" In this case, a randomized algorithm can find a point quickly: Intersect the hypersurface with a random line. The equation for the hypersurface on that line is a one-variable polynomial. You can quickly check if it has roots by taking the gcd with $x^q-x$ and then find the roots by factoring. $\endgroup$
    – Will Sawin
    Commented Jun 28 at 18:17
  • 2
    $\begingroup$ The probability that you find a root in one iteraion is the probability that a random line intersects at least one $\mathbb F_q$-point which is large as long as the number of points is not much less than $q^{k-1}$. So iterating will find a solution with high probability in a few iterations. $\endgroup$
    – Will Sawin
    Commented Jun 28 at 18:18
  • 3
    $\begingroup$ No. Borrowing notation from Kayal, the hypersurface $\mathbf Y$ in $\mathbb F_q^{\ell+1}$ has $\Theta (q^\ell)$ points. A random line intersects $q$ points of $\mathbb F_q^{\ell+1}$ and thus $\Theta(1)$ points of the hypersurface on average, and a second moment estimate shows the number of points is in fact positive with $\Theta(1)$ probability. $\endgroup$
    – Will Sawin
    Commented Jun 28 at 18:34

0

Reset to default

You must log in to answer this question.