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

Question

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.

Answer 1

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

Answer 2

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.

Answer 3

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.