Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Here's a question that I've wondered about somewhat idly from time to time. I think it would be hard, but even a partial result would be interesting. Hopefully someone here can make some headway.

Fix an algebraically closed field k (one can also relax this, e.g. k = $\mathbb{Q}$ is very interesting). Suppose that X and Y are two closed subschemes of affine or projective spaces over k given by explicit equations.

Is there an algorithm to decide whether X and Y are isomorphic?

A few comments.

  1. I'm being a bit sloppy about the use of the word "algorithm". One can assume that the operations of k are Turing computable, or else choose a different model of computation.

  2. For affine schemes, this can be stated as the isomorphism problem for finitely generated commutative k-algebras. I expect that the isomorphism problem for noncommutative finitely presented associative algebras would be false, since it seems close to the corresponding problem for groups which is undecidable. But the reduction is not quite clear to me. Is this known?

  3. To give a positive solution, one would need an effective threshold d, so that either there is no isomorphism at all or there exists an isomorphism defined by a rational expression with degree (of the numerator and denominator) bounded by $d$. I have no feeling for whether this reasonable or not.

  4. For the simplest case, where X is a smooth projective plane curve, a positive solution would amount showing that the corresponding point in the moduli space $M_g$, is computable ($g= (deg X-1)(deg X-2)/2$ ). This looks challenging, but somehow it feels tractable to me.

Added Note: While I think spontaneous discussion is good, I would like to encourage anyone who has a substantial result about this to write it down carefully and perhaps post it on the arxiv.

share|improve this question
add comment

3 Answers

Those are very nice questions. In fact, I too have been asking these questions: see the last few slides in this file. Here are a few comments.

2) If you had an algorithm to decide isomorphism of finitely presented noncommutative $k$-algebras, applying it to group algebras $kG$ associated to finitely presented groups $G$ would let you decide whether a finitely presented group is trivial, but that is a well-known undecidable problem. So this isomorphism problem is undecidable.

4) To decide whether two smooth projective curves over $\overline{\mathbb{Q}}$ are isomorphic, first compute the genus of each curve. Assume that they are the same, both equal to $g$. If $g=0$, they are isomorphic. If $g=1$, compute Weierstrass models and then $j$-invariants. If $g \ge 2$, compute tricanonical embeddings (i.e., associated to the linear system $|3K|$), and try to solve the equation that says that a linear automorphism of the ambient projective space sends one curve to the other. This solves the problem for curves. An extension of this idea solves the problem in higher dimensions whenever one of the varieties is of general type. (I think this was first observed by Burt Totaro.)

As far as I know, all your other questions are open. In particular, it is not clear whether one can relate them to Hilbert's tenth problem over $\mathbb{Z}$ or $\mathbb{Q}$ (or to undecidable problems like the word problem for finitely presented groups).

share|improve this answer
    
Thanks for your comments. It's nice to know you've been thinking about this also. –  Donu Arapura Apr 19 '10 at 21:29
    
A related question is to decide whether or not a variety has a non-trivial automorphism. Do you know if this is known? –  ulrich Apr 20 '10 at 6:06
    
That's unknown too, I think. The closest I've been able to come to this is this paper: www-math.mit.edu/~poonen/papers/automorphism.pdf –  Bjorn Poonen Apr 21 '10 at 8:47
    
Thanks. That's a nice result! –  ulrich Apr 21 '10 at 10:39
add comment

The argument that I had is flawed and I do not know how to fix it. Here is a short description of one part that I cannot address. We are given two polarized K3 surfaces X and Y of degrees x and y respectively. It is clear that we can check if X and Y are isomorphic as polarized surfaces, but we would like to check if they are isomorphic as surfaces. If we could prove that there were finitely many polarizations on X having degree y and this finite set were computable, then we would be done. Unfortunately, there could be infinitely many such polarizations on X.

For Abelian surfaces the situation is slightly better, since the number of polarisations with a given degree is finite (by a theorem of Narasimhan and Nori). To find the polarisations on an Abelian variety A, one possibility is to compute the orbits of the automorphism group of A on the Neron-Severi group of A. While this could be difficult over $\overline{\mathbb{Q}}$, it might be replaced by a similar statement modulo a prime of good reduction, where at least Picard numbers can be computed by the Tate conjecture. Also in this case, I do not know if there are further problems with this approach.

I believe that this kills completely my previous post!

share|improve this answer
    
1) Are you sure that the ample divisors on Enriques surfaces are constant? (The fact that the Picard rank is constant does not impy this in general.) 2) Only principally polarised abelian surfaces correspond to genus 2 curves and there exist non-isomorphic genus 2 curves which have isomorphic Jacobians. –  ulrich Apr 20 '10 at 12:05
    
I've been a little sloppy: Enriques surfaces are probably ok, since they are all sextics in $P^3$ with double lines along the edges of a tetrahedron; this gives you the boundedness that seems needed. (Abelian surfaces in another comment, since they do not fit here!) –  damiano Apr 20 '10 at 12:58
    
For abelian surfaces, construct the Kummer variety, realize the Kummer as a quartic in P^3, and project away from a node. You get a double cover branched along six lines that are tangent to the same conic: I believe that the Jacobian of the genus two curve that you obtain by considering the double cover of the conic branched along the six tangency points is at least isogenous to the initial Abelian surface. This should bound things enough to make the construction computable. –  damiano Apr 20 '10 at 12:58
    
(I would like to emphasize further that the case that worries me most is the case of K3 surfaces.) –  damiano Apr 20 '10 at 12:59
    
This looks interesting. I agree, however, that the K3 surface case needs some clarification. To apply Torelli in a more conventional approach, I think you would need to compare the transcendental lattices. Somehow you're avoiding this issue, but I'm not quite sure how. –  Donu Arapura Apr 20 '10 at 14:28
show 4 more comments

It seems that one can embed 10th Hilbert problem over $\mathbb Z$ into this question, and for that the answer is not known.

share|improve this answer
1  
Hilbert's 10th is undecidable over $\mathbb{Z}$, but probably you meant $\mathbb{Q}$. Yes, I thought about that, but the reduction isn't clear (to me). –  Donu Arapura Apr 19 '10 at 20:59
1  
Could you spell out this reduction? I don't see it. (Even assuming that you meant $\mathbb{Q}$, not $\mathbb{Z}$.) –  David Speyer Apr 20 '10 at 11:56
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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