4
$\begingroup$

Is there an algorithm which, given two polynomials in $n$ variables with real coefficients, $p(x)$, and $q(x)$, will determine whether the zero sets $p^{-1}(0), q^{-1}(0)\subset R^n$, are homeomorphic to each other?

(also same question for polynomials over $C$ with $R^n$ replaced by $C^n$).

Improve this question
$\endgroup$
14
  • 2
    $\begingroup$ Do you seek a useful algorithm, or are you asking whether the problem is computable in principle? If the latter, then could you clarify what model of computability you have in mind? After all, the input should presumably include the real coefficients, an infinite object, and probably you don't expect to get the answer in finitely many steps of an oracle Turing machine. $\endgroup$
    – Joel David Hamkins
    Commented May 20, 2010 at 20:58
  • 2
    $\begingroup$ I should make a more basic point: if the coefficients of your polynomials are given in a computable form, such as rational numbers, then there is an algorithm to find a simplicial complex homeomorphic to your zero locus. In other words, we "know" what the geometry is. Unfortunately, deciding whether two simplicial complexes are homeomorphic is not computable. $\endgroup$
    – David E Speyer
    Commented May 21, 2010 at 14:05
  • 4
    $\begingroup$ @Andy and David, by a version of the Weierstrass approximation theory, any manifold is homeomorphic to a real variety. Thus, real varieties can have any fundamental group a manifold can have, and are not restricted like Kahler groups are. $\endgroup$
    – Charles Siegel
    Commented May 21, 2010 at 18:04
  • 3
    $\begingroup$ Oh, and regarding being a hypersurface, that's completely meaningless over a nonalgebraically closed field, because I can always make a polynomial $f(x_1,\ldots,x_k)$ such that for any $g_1,g_k$ in $t_1,\ldots,t_n$, we have $f(g_1(t),\ldots,g_k(t))=0$ if and only if all the $g$'s vanish, so every real variety is a "hypersurface"...also over any other nonclosed field. $\endgroup$
    – Charles Siegel
    Commented May 21, 2010 at 18:06
  • 2
    $\begingroup$ Guy, regarding your last point. If all actual instances of pairs of rational polynomials either had a proof (in whatever formal system) that the solutions sets were homeomorphic or that they weren't homeomorphic, then there would be a decision procedure, namely, go and look for a proof one way or the other and output the corresponding answer. That is, if the problem is undecidable, then there is a pair of rational polynomials such that it is neither provable nor refutable in ZFC that the solution sets are homeomorphic. (This would be an existence proof that there is an explicit example.) $\endgroup$
    – Joel David Hamkins
    Commented May 21, 2010 at 19:05

2 Answers 2

Reset to default
3
$\begingroup$

I think the answer to the "real" version of the question is no. Here are some remarks.

  1. One can realize each smooth manifold as a real algebraic variety in a Euclidean space. So one can realize each smooth compact manifold as the zero set of a single polynomial, by taking the sum of the squares of the polynomials that generate the ideal of the corresponding algebraic variety.

  2. In dimensions $\leq 7$ every PL-manifold admits a smooth structure. So given a PL-manifold one can "smoothen" it and construct a homeomorphic real algebraic variety. The question is whether this can be done constructively (and moreover so that the resulting variety is defined over the rationals, if one considers the "rational" version). This looks plausible. If it is true then one can use the fact that the homeomorphism problem for PL-manifolds of dimension 4 is undecidable.

Improve this answer
$\endgroup$
2
$\begingroup$

I find this question extremely interesting. I have two small observations.

First, following up on my comment, the answer is definitely no in the case that you allow real coefficients and want the answer in finite time. It seems natural to suppose that we are given the form of the two polynomials, and then also given the coefficients as oracles. Perhaps we are given an infinite sequence of rational approximations to them, with a known rate of convergence. The difficulty is that it is impossible in principle to compute in finite time whether two oracles are equal. (If they look the same so far, then you cannot say "they are equal" at any finite time, since a difference may arise at some later point that you never inspected.) Similarly, it is impossible in principle to determine if an oracle is $0$ or not in finite time.

Suppose we could decide your problem. Now, given a reals $a$, construct the two polynomials $p(x)=0$ and $q(x)=ax$. In the case that $a=0$, then the solution sets of these polynomials are homeomorphic, since the polynomials are both the zero polynomial. But in the case that $a\neq 0$, then they are not homemorphic, since every $x$ solves $p$ but only $x=0$ solves $q$. Thus, the zero-test problem reduces to your problem, and so your problem is not decidable.

But as I mentioned in my comment, I think in the case of real coefficients we didn't really expect to get an answer in finite time. This is why it is natural to consider the question of what happens with rational coefficients, where the algorithm has full access to the entire system.

Here, I don't have an anwer, but merely offer the observation that if somehow the question is expressible in the language of the first order structure $\langle R,+,\cdot,0,1,\lt\rangle$, that is, in the language of real-closed fields, then it will be decidable by Tarski's theorem, which asserts that the theory of this structure is decidable. We have a computable procedure that answers any first order inquiry about this structure. But I'm not sure that your problem is expressible in this language, and I suspect it isn't. So meanwhile I will wait for the algebraic geometers to settle it.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .