Approximating zero sets of real polynomials with "less complicated" polynomials

Question

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:

1. $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$.

2. 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!

Answer 1

You can find these approximations algorithmically, but the algorithms may be unfeasible.

The following are not exactly equivalent, but the steps are small enough that I suspect that you'll be able to do all of them feasibly or none:

• finding an approximation in this sense
• verifying that an approximation is good in this sense
• verifying $d(Z_P, Z_Q) < d(Z_P, Z_R)$ or verifying $d(Z_P, Z_Q)<\epsilon$
• checking whether $d(Z_P, Z_Q)>0$
• checking whether $d(Z_P, Z_{P^2+S^2})>0$, i.e. whether $\exists x P(x)=0 \wedge S(x)\neq 0$

The last of these is the key to the decision procedure for real-closed fields, which is known to be superexponentially hard. (So if you think that some of these problems are feasible -- where would you expect the line between feasibility and unfeasibility to be?)

If feasibility is not a concern, then a version of the problem with integer coefficients has a clear algorithm:

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 among such $Q$ 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 using the above decision procedure. Specifically, we can decide 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}\ \exists {\bf y}\ (&d({\bf x},{\bf y})\le t \\ \wedge\, (P({\bf x})=0 &\to Q({\bf y}) =0)\\ \wedge\, (Q({\bf x})=0 &\to P({\bf y}) =0)) \end{align}

This algorithm can also be modified to work:

• for polynomials with algebraic rather than integer coefficients
• for distances $d(Z_P\cap K, Z_Q\cap K)$ where $K$ is a closed ball or closed semialgebraic set
• for further computable restrictions on the polynomial $Q$.