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?
3
$\begingroup$
$\endgroup$

$\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 $d2$ with $f(y) u(y)  g(y) v(y)=0$. The existence of such polynomials is equivalent to a $2d1 \times 2d2$ 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 (k1)$ 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