Suppose an irreducible smooth $p \in \mathbb{R}[x_1,x_2]$ is given, and we would like to find finite sets $S_1 , S_2 \subset \mathbb{R}$ such that $p(S_1 \times S_2)=0$ and $|S_1 \times S_2|$ is as big as possible. How do we do this efficiently?

  • $\begingroup$ I do not know an efficient algorithm for your problem. You might be interested in a similar, but less algorithmic problem at mathoverflow.net/q/66895/806. $\endgroup$
    – Boris Bukh
    Jan 11 '19 at 14:18
  • 1
    $\begingroup$ "Generically" I think the best you can hope for is $1 \times m_2$ or $m_1 \times 1$ (where $m_i$ are the degrees of $p$ in $x_1$ and $x_2$ respectively) or $2 \times 2$. $\endgroup$ Jan 11 '19 at 15:38
  • 1
    $\begingroup$ A good first step would probably be to find all pairs $(x_1, x_2)$ such that $p(x_1,y)$ and $p(x_2,y)$ have $\geq 2$ roots in common. To this end, it is useful to know that two degree $d$ polynomials $f(y)$ and $g(y)$ have $\geq 2$ roots in common if and only if there are nonzero polynomials $u(y)$ and $v(y)$ of degree $d-2$ with $f(y) u(y) - g(y) v(y)=0$. The existence of such polynomials is equivalent to a $2d-1 \times 2d-2$ matrix with coefficients depending on $f$ and $g$ having nontrivial kernel. $\endgroup$ Jan 11 '19 at 16:21
  • $\begingroup$ I think there is literature on finding $(x_1, x_2)$ where a $k \times (k-1)$ matrix whose entries depend on $(x_1, x_2)$ has kernel, but I couldn't find it quickly. $\endgroup$ Jan 11 '19 at 16:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.