Return to Question

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.

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.

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.

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.

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 algebraic algebraically closed 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.

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.