Let be an algebraic variety over ; that is to say, the zero locus of a bunch of polynomials with complex coefficients. We will consider this zero locus as a topological space using the ordinary topology on . One of the main themes of algebraic geometry in the last century has been learning how to study the topology of in terms of the algebraic properties of the defining equations.

In this post, I will explain that there are intrinsic limits to this approach; things that **cannot** be computed algebraically. In particular, I want to explain how from a categorical point of view, we can’t even compute the homology . And, even if you don’t believe in categories, you’ll still have to concede that we can’t compute . This is a very pretty example and it should be more widely known.

Absolutely none of the ideas in this post are original; I think most of them are due to Serre. (Thanks to Attila Smith in comments for the reference.)

What does it mean that something cannot be computed algebraically? I could give a general definition, but let me just explain the kind of examples we will be looking at. Let be a finite Galois extension of . Suppose that all of the equations defining have coefficients in . Let be the new variety obtained by replacing all the coefficients of by their Galois conjugates, for some . Since the Galois action preserves the truth of every algebraic statement; clearly we will not be able to use algebraic methods to distinguish and . Thus, if we can come up with cases where and have different topology, then the manner in which they differ will be something that cannot be seen by algebraic methods.

If we were looking at topology of real points, it would be easy to build examples. For example, let and let be the elliptic curve , so is the elliptic curve . Looking at real solutions, has two connected components and has only one. In the figure below, is the solid black curve and is the dashed blue curve.

Looking at complex solutions, however, both and are two dimensional tori. (More precisely, tori with a single point removed; the “point at infinity”.) So one might think that determining the real geometry of a variety requires some subtle ideas, but that complex geometry is purely algebraic. In fact, this is not so.

Consider two lattices in the complex plane. The first, , will be spanned by and . The second, , Will be spanned by and .

Let be the elliptic curve and let . Notice that both and are taken into themselves under multiplication by . This multiplication descends to holomorphic endomorphisms of and , which we will denote and .

Since is an elliptic curve, it can be written as for some and . (Plus a point at infinity.) It turns out that the endomorphism imposes enough rigidity on the situation to see that and can be taken to be algebraic numbers; I will sketch an explanation for this below. In fact, we can take and to be in . Moreover, the map can be written as , where and are rational functions whose coefficients are algebraic — explicitly, in .

I wanted to compute , , and for you*, but I couldn’t find them in any books or websites and it seemed a bit difficult. I was able to work out that the invariant of is

There is a theory of elliptic curves with unusual endomorphisms — the technical term is curves with complex multiplication. Here is one consequence of this theory: Let and let be the Galois automorphism where and . Then the curve is given by . Moreover, the automorphism is given by applying to the coefficients of .

So, why do I say that “from a categorical point of view, we can’t even compute the homology .” Of course, is naturally isomorphic to , and unnaturally isomorphic to ; similarly, is also unnaturally isomorphic to . So you could say that and were the same, if you are willing to engage in unnatural acts.

But homology is a functor! Computing it should means computing what it does to morphisms, not just what it does to objects! Looking at how multiplication by acts on and . we see that the module is generated by a single element, where as the module is not. So there is an element of so that and span , but there is no so that and span . In short, the action of an endomorphism on cannot be computed algebraically.

**A clever trick, for those who mistrust categories:** If you believe in the categorical philosophy, you are done now. But, if you are a classical sort, you might want to see two varieties and which are not homeomorphic.

If we were living in the topological category, we could take the mapping cylinder of and get a map whose topology reflects the map . But in the algebraic category, mapping cylinders don’t exist. In the remainder of this post, I’ll sketch a trick to get around that, due to again to Serre.

Just like abelian curves come from lattices in , abelian varieties come from lattices in higher dimensional complex vector spaces. Just as has nonisomorphic modules, so does for certain values of . A more complicated version of the above argument constructs an abelian variety , with endomorphism , such that , and such that there is a Galois automorphism for which is topologically different from . I’ll write for the dimension of ; for the curious, .

Now, let be simply connected, with a free action of . (And let this variety and action be given by rational coefficients, so it is unaffected by .) Consider . This is , where acts diagonally. It is extremely plausible, and not hard to prove, that . Now, some basic topology tells us that and are both semidirect products of acting on . However, in the case of , this action is by the action of on , and in the case of it is by the other action. These are nonisomorphic groups, so we see that even those who mistrust categories must admit that cannot be computed algebraically.

**Sketch of why these numbers are algebraic**. We can write down the condition that and give an automorphism of , whose square is . This is a whole lot of equations in , and the coefficients of and ; all the coefficients of these equations are rational. Now, an elliptic curve will only have such an automorphism if is closed under multiplication by . It is a good exercise to show that any such lattice is, up to dilation and rotation, either or . So these equations will only have two solutions. (Actually, they will have two solutions up to automorphism, see the footnote. But this is a sketch!) Any set of equations with finitely many solutions, and coefficients in a field , has all of its solutions in ; this is a corollary of the Nullstellensatz.

*There is a technical point I am glossing over: and are not quite well defined. Specifically, the elliptic curve is, as a complex variety, isomorphic to . Moreover, even if , and are all in , the isomorphism will involve coefficients in . This is called twisting, and is important if you want to get all the details right, but I will not deal with it.

Dear David,

the relevant article by Serre might be:

Exemple de variétés projectives conjuguées non homéomorphes.

C.R.Acad.Sci. Paris258 (1964), 4194-4196.

Your explanations are friendly and clear: bravo!

Thanks for the reference and the complement; I’ll update the article.

Dear David,

Nice post!

You may have already seen the paper, but James Milne and Junecue Suh have some recent work on this topic too.

http://arxiv.org/abs/0804.1953

Russell Miller and I treated a rather different formalization of the same intuitive problem (can one compute topological invariants from elementary data) in a paper soon to appear in the proceedings of Unconventional Computation 2009.

We showed that if a manifold is “effectively given,” in the sense that we have algebraically computable functions (in the sense of Blum-Shub-Smale) to describe the transition functions, then

a) We cannot, in most cases, decide if a loop is nullhomotopic, but

b) There is a canonical system of loops which suffices to compute a presentation of pi_1.

I don’t have the preprint available online (yet), but can provide it upon request.

Thanks for the interesting post!

If you view your curve as a real algebraic set in then you certainly can compute its Betti numbers algebraically (well, semi-algebraically). See e.g. http://arxiv.org/abs/0806.3911 for abundant references on this.

I’m not sure whether you are disagreeing or just discussing a different, but related, idea. So I’ll explain the difference in perspective between Serre’s result and the one you link to.

To my mind, pure algebra does not include testing inequalities, and Galois theory is designed to study things that can be computed algebraically. So semialgebraic methods are outside this paradigm. For example, in Galois theory we consider the field automorphism which takes to . This automorphism preserves field structure but not inequalities: it takes a positive number to a negative one. Even worse, we are allowed to take a real number like to an imaginary one like .

The amazing thing, then is that there is so much that can be computed purely algebraically — including betti numbers! (You only need to read the first section of the linked reference to get my point, although the whole thing is excellent.) It is data like the action of endomorphisms on cohomology, or like the fundamental group, which requires nonalgebraic techniques.

Finally, although this is not my field, I’ll point out that there are lots of subtle issues in semi-algebraic computation. For example, it is not known whether there is an efficient way to test whether an algebraic number is positive!

Dear Wesley – from the sound of it, you might be interested in the papers of Nabutovsky and Weinberger, which have a similar flavor (if you are not already aware of them . . .) For example, see Weinberger’s nice book:

http://www.ams.org/mathscinet-getitem?mr=2109177

Best,

Danny

David,

to me it seems that computations involving real algebraic numbers can still be counted as algebraic, although it’s a matter of taste.

By the way, computing the fundamental group becomes doable, as one would be able, starting from a variety, to construct a finite simplical complex with the same fundamental group. Then you can run something along the lines of http://www.maths.qmul.ac.uk/~leonard/fundamental/

To comment on your claim that testing positivity is not known to be efficient, it seems to me that you misread the part of the Lipton’s post you are referring to. Indeed, he talks about SSP, i.e. testing inequalities of the form This way you’re effectively leaving the polynomial “universe”. An algebraic way to encode this would need variables and a system involving nonlinear polynomial equations and inequalities in all of them. Needless to say, already the task of testing solvability of a system of -variate polynomial equations is also NP-hard, even if you allow complex solutions.

On the other hand, if you work with the encoding of a real algebaric number by a defining univariate polynomial and a rational interval to locate the particular root (or what is called

Thom encoding, i.e. the signs of the derivatives of at the root) then everything becomes efficient, and these procedures are dating back from 19th century.(The complexity of SSP is related to the complexity semidefinite programming, and as such is indeed quite important. But this is another story.)

David,

I’ve been thinking about a problem, only tangentially related to this post, but maybe you’ll enjoy it.

Suppose I hand you an algorithm. It can be run on your household computer. [Formalize this as you will.] This algorithm spit out, one at a time, digits for a positive real number (say less than 1).

Is there another algorithm (call it the Decider) which will decide whether or not the first algorithm is describing 0?

I believe the answer is no. However, I’m a little weak on how one defines an algorithm, in ZFC set theory say.

Application: Given an explicit function (say an L-function attached to an explicit elliptic curve with integer coefficients), is there an algorithm to determine if there is more than a double pole at the origin?

Hi David,

Is it true that when you are looking at “real” or “complex” points in a scheme defined over rationals this incompatibility creeps in.

Consider the following reformulation :

If K1 and K2 are conjugate schemes defined over some algebraic extension of rationals, and L is some Galois extension containing K1 and K2, then for any locally constant sheaf F the cohomologies over K1 and K2 are isomorphic.

But this looks like a obvious base change…

For a locally constant sheaf with torsion coefficients, sure, that’s base change. If you are going to consider locally constant sheaves like , then you have to worry about the fact that the etale and analytic topologies don’t give the same results for such sheaves.

Indeed, the singular cohomology of with coefficients in is naturally isomorphic to the cohomology of the locally constant sheaf in the analytic topology. The examples above show that and need not be naturally isomorphic, but of course you only said isomorphic. I’d need to think a bit to see if I could find some for which these groups were not isomorphic at all.

Yes, I meant natural isomorphism for sure.

I was wondering if it is not a stupid question to ask : can one find a family of varieties (flat?) where the fibers differ in their topology (i.e analytic cohomologies ).

In other words, is it possible to have an example where a variety and it’s “sufficiently” bad degenration are connected by a flat family of deformations.

(I know very little about deformation theory to guess, if it is an obviously wrong question to ask)

If my understanding of your question is correct, take the family on . For , you have a smooth elliptic curve, which is topologically . For , you have a nodal cubic, which is a sphere with the north and south poles identified, which is not the same topology.