# Estimating the distance from a variety by evaluating the polynomial

I have the conjecture stated below, which would be very helpful for a cryptographic security proof I'm working on for several months now. At first glance, it seemed a pretty natural question to me, but after asking a lot of people and also searching the internet I'm still without a solution or any helpful hints. This is the conjecture:

Let any multivariate polynomial $f\in\mathbb R[X_1,\ldots,X_n]$ be given, such that the corresponding variety $V_f$ is not empty: $V_f=\{x\in\mathbb R^n\,|\,f(x)=0\}\neq\emptyset$. Then there exists some constant $c>0$, such that for all $x\in\mathbb R^n$ one can estimate the distance of $x$ from $V$ as follows: $c\cdot\min_{y\in V_f}\|x-y\|^{\deg f}\leq|f(x)|$.

In particular, I only need this to hold true if $\deg(f)\leq4$ and $x$ is only taken from a compact set $K\subset\mathbb R^n$. If the conjecture turns out true, it can be used for generalization of a classification result of mine in theoretic cryptography. Here are some further notes:

• Since all norms on $\mathbb R^n$ are equivalent, the assertion either holds true for every norm or for none.
• If $K\cap V_f=\emptyset$, one can just set $c:=\min_{x\in K,y\in V_f}|f(x)|\cdot\|x-y\|^{-\deg f}$. So, the "interesting" values $x$ are close to $V$.
• If the conjecture is not true, then there exists a counterexample with irreducible polynomial $f$. Given any reducible counterexample, say $f=g\cdot h$, we can estimate $\min_{y\in V_f}\|x-y\|^{\deg f}$ by $\min_{y\in V_g}\|x-y\|^{\deg g}\cdot\min_{y\in V_h}\|x-y\|^{\deg h}$ and it follows straightforwardly that $g$ or $h$ must be a counterexample, too.
• If $n=1$, i.e. $f$ is univariate, the conjecture is true, since the only irreducible polynomials with non-empty variety are of the form $f(x)=ax+b$. Clearly, these are no counterexamples and thus, as mentioned above, there don't exist any univariate counterexamples at all.
• I was able to prove the weak variant of the conjecture with $x\in K$ for the case that $\deg(f)\leq2$, but the proof is quite long; it can be found here.
• Can you verify your conjecture when $f$ is homogeneous? – Rbega Feb 22 '12 at 17:36
• Daniel: for my own edification, why is the ability to bound $c$ away from zero not equivalent to the conjecture? – Charles Staats Feb 23 '12 at 1:29
• @Rbega: I don't know a proof for homogeneous $f$ in general. However, if $f$ is a homogeneous counterexample, then there also exists a counterexample with less variables. I used that in my proof for the case that $\deg(f)\leq2$. – Daniel Kraschewski Feb 23 '12 at 9:07
• @Charles Staats: Bounding $c$ away from zero would prove the conjecture, but e.g. for $f(x,y)=y^2+(x(x−1))^2$ you find straight lines with arbitrarily small $c$, namely the lines through $(0,0)$ and $(1,ε)$. – Daniel Kraschewski Feb 23 '12 at 9:08

• Many thanks! I can perfectly live with any constant exponent. One of the references in your link even says that for $f(x,y)=y^{2m}+(y−x^m)^2$ one needs an exponent $\alpha\geq2m^2$. Thus it seems that in general my conjecture is wrong. – Daniel Kraschewski Feb 27 '12 at 8:16