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$
$\endgroup$
4
-
$\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 BukhJan 11, 2019 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 IsraelJan 11, 2019 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 SpeyerJan 11, 2019 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 SpeyerJan 11, 2019 at 16:21
Add a comment
|