9
$\begingroup$

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.
$\endgroup$
  • $\begingroup$ Can you verify your conjecture when $f$ is homogeneous? $\endgroup$ – Rbega Feb 22 '12 at 17:36
  • $\begingroup$ Daniel: for my own edification, why is the ability to bound $c$ away from zero not equivalent to the conjecture? $\endgroup$ – Charles Staats Feb 23 '12 at 1:29
  • $\begingroup$ @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$. $\endgroup$ – Daniel Kraschewski Feb 23 '12 at 9:07
  • $\begingroup$ @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,ε)$. $\endgroup$ – Daniel Kraschewski Feb 23 '12 at 9:08
7
$\begingroup$

You want this: http://en.wikipedia.org/wiki/%C5%81ojasiewicz_inequality

The exponent might not be the degree, though.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Daniel Kraschewski Feb 27 '12 at 8:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.