# Is this naive test to tell whether a complex elliptic curve has complex multiplication effective?

I have a question about a naive test to tell whether a complex elliptic curve $E$ has complex multiplication.

Recall that the endomorphism ring $End(E)$ of $E$ is isomorphic to either $\mathbb{Z}$ or an order in an imaginary quadratic field $K$. In the latter case we say that $E$ has CM by $K$.

Suppose that we are given an elliptic curve over $\mathbb{C}$, say $$E: y^2=x^3+17x^2-19.$$ One wants to know if there is an imaginary quadratic field $K$ for which $E$ has CM by $K$.

Let $j(E)$ be the j-invariant of our elliptic curve (for example, the above curve has j-invariant $\frac{6179217664}{363641}$) and recall that the j-invariant, viewed as a modular function, gives a surjective map from the upper half plane to $\mathbb{C}$. Let $\omega$ be any element in the preimage of $j(E)$. We now define a second elliptic curve: $$E_\omega: y^2=4x^3-g_2(\omega)-g_3(\omega),$$ where $g_2=60G_4$ and $g_3=140G_6$ are multiples of the appropriate Eisenstein series. Both of these elliptic curves are defined over $\mathbb{C}$ and have the same j-invariant. They are therefore isogenous. It is known that the elliptic curve $E_\omega$ is isomorphic to the complex torus $\mathbb{C}/\Lambda_\omega$ where $\Lambda_\omega=\mathbb{Z}+\mathbb{Z}\omega$.

It is easy to show that $\mathbb{C}/\Lambda_\omega$ has CM by some imaginary quadratic field if and only if $\omega$ is an imaginary, quadratic number. In this case the endomorphism ring of $\mathbb{C}/\Lambda_\omega$ will be an order in the field $\mathbb{Q}(\omega)$.

This suggests a test for CM: given an elliptic curve $E$ defined over $\mathbb{C}$ with j-invariant $j(E)$, find a preimage of $j(E)$ under the modular function $j:\mathbb{H}\rightarrow\mathbb{C}$ and determine whether or nor the preimage generates an imaginary quadratic extension of $\mathbb{Q}$.

Now for my question: can this test actually be performed? Wikipedia tells me that the inverse of the j-invariant can be computed in terms of hypergeometric functions, but I don't know if one could use this inverse to determine whether a given j-invariant was associated to a curve with CM.

-

I don't know anything about hypergeometric functions, so this is not a direct answer to your question. But, I have thought a lot about the problem of detecting complex multiplication of elliptic curves (and certain higher-dimensional analogues for abelian varieties).

Suppose you are given an algebraic integer $j$, and you wish to know whether it is a CM j-invariant. Then there is a sort of night-and-day algorithm you can perform here, where by night you reduce the elliptic curve modulo various primes and keep in mind the fact that if your elliptic curve has CM, then half the time (in the sense of density) you will get a supersingular elliptic curve and the other half you will get a CM elliptic curve whose characteristic p endomorphism algebra is the same as the algebra you started with. Thus, in practice, if your curve does not have CM, you will fairly quickly be able to rule it out by finding two primes of ordinary reduction with different endomorphism algebras. So far this is just a probabilistic algorithm. Once you figure out that the CM field is either a particular quadratic field K or there is no CM at all, you compute (e.g. by classical CM theory as described e.g. in Cox's book Primes of the form...) you compute the $j$-invariants of elliptic curves with K-CM. There are infinitely many of these, because the j-invariant depends on the endomorphism ring (equivalently, the conductor of the order), but you can either just compute all of them in order of conductor or look more carefully at the mod p reductions and get a bound on what the conductor could be.

[Edit: Actually, you can figure out exactly what the CM order must be by computing the endomorphism ring at any two primes of ordinary reduction. It is a theorem that if $E$ is a curve with CM by the order of conductor $f$ in a CM field $K$ and $p$ is a prime of ordinary reduction, the conductor of the reduced endomorphism ring is $f/p^{ord_p(f)}$, i.e., you just strip away the $p$-part of the conductor.]

This is not the state of the art, though. Rather, see the paper

Achter, Jeffrey D. Detecting complex multiplication. (English summary) Computational aspects of algebraic curves, 38--50, Lecture Notes Ser. Comput., 13, World Sci. Publ., Hackensack, NJ, 2005.

[A copy is available via his webpage http://www.math.colostate.edu/~achter/.]

In the paper, Achter uses Faltings' theorem and the effective Cebotarev density theorem to eliminate the "day" part of the algorithm. He also gives a complexity analysis and explains why this is faster than what I sketched above.

Finally, I'm sure the questioner knows this, but others may not: for elliptic curves over $\mathbb{Q}$ there's no need to do any of this. Rather you just compute the $j$-invariant and see whether it's one of the $13$ $j$-invariants of CM elliptic curves over $\mathbb{Q}$ associated to the $13$ class number one quadratic orders (yes, this relies on the Heegner-Baker-Stark resolution of Gauss' class number one problem). For the list, see e.g.

modular.fas.harvard.edu/Tables/cmj.html

-
I don't get what the "day" part is of your "night and day" algorithm. This isn't a term I've run across before. – David Mandell Freeman Feb 11 '10 at 22:27

Interesting question. I have a few remarks, but nothing definitive. I assume that you're implicitly assuming that the $j$-invariant is given as a complex number (with some sort of process giving you more and more digits as you need them).

1) To have CM, $j$ must have a real conjugate.

2) To have CM, $j$ must be an algebraic integer.

3) The degrees as algebraic numbers of the $j$'s are rapidly increasing. That is, there are only a finite number of $j$'s of given degree. As a result of this the amount of precision that you'll need is going be increasing. What I mean by this, is the most practical way of dealing with this is to have a table of $j$'s corresponding to the quadratic imaginary orders of low class number (they probably exist in some useful form), and just test those first. If you don't get a hit, you have a lower bound on the degree as an algebraic number.

4) I don't know anything about how well the ${}_2 F_1$ converges over the complex numbers, however, an interesting thing to try is the $p$-adic hypergeometric function (a la Dwork). I don't know how that might work, but it's worth a try.

Added later: In my comments I said that the most reasonable way to proceed would be to guess a degree, $d$ for $j$ as an algebraic number and then to use lattice reduction to find a putative irreducible equation, $f(x)$, for $j$. We know that in order for $j$ to have CM, it must have a real root, and its Galois group must be abelian. So test for that. I think that you can also get useful information from the Gross-Zagier theorem in that $f(j_0)$ will be an integer with only "small" prime divisors where $j_0$ ranges over the $j$'s corresponding to quadratic orders of class number 1.

-
One extra practical thing that you can do is that if $j$ is a CM $j$-invariant, then $j^{1/3}$ is an algebraic integer of the same degree (and has logarithmic height only about $1/3$ of $j$'s). There are other similar things you can do, e.g. $(j-1728)^{1/3}$. – Victor Miller Feb 10 '10 at 16:40
I have to take issue with statement number 1. It would be more accurate to say that "j must have a real Galois conjugate" For instance an elliptic curve with CM by the quadratic order with discriminant -71 must have j-invariant satisfying a degree 7 polynomial which happens to have only one real root. – stankewicz Feb 10 '10 at 16:57
This is a very elementary remark: In the given example, j is rational. If this is the only case you care about, then you should be aware that there are only finitely many rational j-invariants which support complex multiplication, so you can just check the list. – David Speyer Feb 10 '10 at 17:01
@stankewicz: You are correct! – Victor Miller Feb 10 '10 at 17:05
@PLC : I stand by what I said. It's easy to get an elliptic curve with any given j-invariant, and one of the roots of the polynomial in my earlier example is approximately $30.1939746922985 - 380.060172538012i$, so provably it's a complex number and this elliptic curve will have CM by the quadratic order of discriminant -71. – stankewicz Feb 10 '10 at 18:42

Unlike Pete Clark, I have not spent any real time working on this sort of problem, so you should take all of this with a heavy grain of salt. But I think this algorithm is quite reasonable as a way to rule out CM, although it would be diffciult to use it to prove CM exists. EDIT: As FC points out, this algorithm only finds the lattices of the form $\mathcal{O}_K$, not the lattices of the form $I$ where $I$ is an ideal in $\mathcal{O}_K$. The latter may not even have real $j$-invariant. I don't see a way to get around this.

Here is how I would do it: Start with your $j$ invariant, $j_0$. If it is not real, the curve does not have CM . If $j_0$ is real, compute $\tau$ such that $j(\tau) = j_0$ and such that $\tau$ is in $$\{ i t: t \geq 1 \} \cup \{ z : |z|=1, \ 0 \leq \Re(z) \leq 1/2 \} \cup \{ 1/2 + i t: t \geq \sqrt{3}/2 \}.$$

I'll describe the case where $\tau$ is on the imaginary axis; the other cases are similar. Here is the point which no one has made yet: The pure imaginary $it$ generates an imaginary order if and only if $t^2$ is an integer. So we only need to perform the computation with enough precision to determine whether $t$ is an integer. Of course, a floating point computation can never be known to converge to an integer, but it will very soon either do so or clearly fail to do so.

-
@David: yes, this works. It goes along with what I said before: not having CM is an open condition on moduli, so is amenable to approximate computation. It is similarly easy to compute that an abelian variety of any dimension has endomorphism algebra Q, if it does. The hard part is confirming that the endomorphism algebra is larger than Q when you suspect that it is. I have worked on this problem (sporadically) for abelian surfaces, and it's kind of a pain. – Pete L. Clark Feb 11 '10 at 4:27
@FC: I don't think this is quite right; you rather get that j(E) is real iff [c] has order at most 2 in the Picard group. But there are only finitely many such quadratic fields -- they correspond to the idoneal numbers. As I mentioned above, if you start with an algebraic integer j-invariant, then you can choose a conjugate for which j is real. If j is given only approximately as a complex number, then, agreed -- this method will not work. – Pete L. Clark Feb 11 '10 at 4:49
@FC: Yes, I agree with that. – Pete L. Clark Feb 11 '10 at 5:11
I think that is indeed a crushing point. As far as I know, computing Galois conjugates from floating point data is impossible both in theory and in practice. – David Speyer Feb 11 '10 at 11:49