Determining if two algebraic sets are homeomorphic - MathOverflow

Determining if two algebraic sets are homeomorphic

2010-05-20T19:59:39Z

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

Answer by Joel David Hamkins for Determining if two algebraic sets are homeomorphic

2010-05-21T13:21:16Z

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.

Answer by algori for Determining if two algebraic sets are homeomorphic

2010-05-21T18:11:43Z

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

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