Approximating zero sets of real polynomials with "less complicated" polynomials Let $K \subset \mathbb{R}^n$ be a compact subset, and let $P(x_1,\dots,x_n)$ be a real multivariable polynomial of degree $d$, whose vanishing set we denote by $Z_P$. Is it plausible to approximate $Z_P$ within $K$ (in the Hausdorff sense, for example) with the zero set of another polynomial $Q(x_1,\dots, x_n)$ which satisfies the following properties:


*

*$Q$ is "simpler" than $P$ in the sense that a lot more of the coefficients of $Q$ are zero? For example, $x^4 - 1$ is simpler than $x^4 - x^3 + 1$.

*The degree of $Q$ is preferably $\leq d$.
If yes, is there is a constructive method for finding $Q$? Any pointer/reference would be highly appreciated!
 A: I’ll record an obvious algorithm for a simpler setting of this problem, which points to some limits on how efficiently we might compute these approximations, while avoiding questions about computations with real numbers or compact sets.

Given a polynomial $P$ in $\mathbb{Z}[{\bf x}]=\mathbb{Z}[x_1,\dots,x_n]$, we can find a
polynomial $Q$ in the same ring which:

*

*has degree, height, and length only as large as $P$'s

*is distinct from $P$

*and has a zero set $Z_Q$ at minimal Hausdorff distance from $Z_P$.


The algorithm is to just to compare the finitely many possible $Q$'s, comparing the Hausdorff distances using the decision procedure for real-closed fields.
Specifically, we can evaluate whether
$$d(Z_P,Z_Q)\le d(Z_P,Z_R)$$
by evaluating the equivalent first-order sentence
$$\forall t\, \big[d(Z_P,Z_R)\le t \to d(Z_P,Z_Q)\le t\big]$$
where $d(Z_P,Z_Q)\le t$ abbreviates
\begin{align}
&\, (\forall {\bf x}\ P({\bf x})=0 \to \exists {\bf y}\ Q({\bf y}) =0\wedge d({\bf x},{\bf y})\le t)\\
\wedge& \, (\forall {\bf x}\ Q({\bf x}) =0\to \exists {\bf y}\ P({\bf y}) =0\wedge d({\bf x},{\bf y})\le t) 
\end{align}
This algorithm can also be modified:

*

*for distances $d(Z_P\cap K, Z_Q\cap K)$ where $K$ is semialgebraic

*for polynomials with algebraic rather than integer coefficients

*for further computable restrictions on the polynomial $Q$
The narrow scope suggests an open question:

Is there a more efficient or more insightful algorithm for the above?

One negative piece of evidence is that $\exists{\bf x}\, P({\bf x})=0 \wedge Q({\bf x})\neq 0$ is equivalent to $d(Z_P,Z_{P^2+Q^2})>d(Z_P,Z_P)$. Since the first statement (in parameterized form) is the key to decidability for real-closed fields, the comparisons of Hausdorff distances are likely to have much of the algorithmic complexity of the broader decision procedure.
