# Biggest Cartesian Product Included in a Real Plane Curve

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?

• 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. – Boris Bukh Jan 11 at 14:18
• "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$. – Robert Israel Jan 11 at 15:38
• 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. – David E Speyer Jan 11 at 16:21
• 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. – David E Speyer Jan 11 at 16:21