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 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$ – Robert Israel Jan 11 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$ – David E Speyer Jan 11 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$ – David E Speyer Jan 11 at 16:21

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.