Subfields of a function field

Is there an algorithm for generating (some or all) subfields of a certain genus of a given function field (even a random one,I mean for example generating a random elliptic subfield of a certain given function field). I did a quick search and it seems to me that the problem is heavily treated in the case of cyclic and Hermitian function fields, but I was wondering what do we know in general case. Is there something that I can do in Magma?

On the other hand, do we have an algorithm to check if $F$ is a subfield of $E$, When $F, E$ are function fields (of one variable)? Florian Hess told me that somebody developed such an algorithm using his automorphism algorithm but I don't have much luck finding it.

In order to stick to the tradition, I give a motivation also: Subfields of function fields with a rich automorphism group are subject to cover attack in cryptography when they are not one of those few which are fixed by an automorphism of the cover.

Thank you very much indeed!

-
This seems to be a hard problem. For example, given curves $C,E$ over a finite field, with $E$ elliptic, the zeta function of a given curve $C$ will reveal whether there exists a morphism $C\to E$, via Tate's theorem that $Hom(Jac(C),E)\otimes Z_l$ is the module of Galois-invariants in $Hom(T_l(Jac(C),T_l(T)$ (here $T_l$ is the $l$-adic Tate module). However, it's difficult to make Tate's theorem effective. OTOH a general curve will have no morphisms to any other curve of positive genus, so I'm not sure what you mean by "a random one". –  inkspot Feb 26 '11 at 10:55
The solutions to the subfield problem in the case of number fields should pretty much work here as well. For example, take primitive elements of $E$ and $F$ (random elements should do), find their minimal polynomials over $K[t]$ (solve linear system), find a completion of $K[t]$ over which both polynomials have a factor (find a prime ideal with solutions and use Hensel's lemma), and finally, you can use LLL to try to express the first element as a linear combination of powers of the second. For other methods for number fields, which have function field analogues, see Cohen. –  Dror Speiser Feb 26 '11 at 15:09
@Dror, there is no canonical $t$. –  Felipe Voloch Feb 26 '11 at 21:01
@Drar, As Felipe said, exactly the problem is that $K(t)$ is not as good as $\mathbb{Q}$ for number fields. This is why automorphism group is richer than the Galois group and why it's harder to be computed. I think the use of Hess's automorphism algorithm is to check all the (non-canonical but isomorphic)possible ways of embedding of $F$ in $E$ and check if it's work but I don't know the detail. –  Syed Feb 26 '11 at 21:08
@Inkspot I don't get "a general curve will have no morphisms to any other curve of positive genus" part. If $F$ is a subfield of $F$ then there's morphism from the defining curve of $F$ to the defining curve of $E$. Isn't in second chapter of Silverman? By random, I mean given function field $F$. Is there a way to generate a subfield of it, of given genus. As much as I understand you say there's no subfield other than rational subfields (of genus zero)? –  Syed Feb 26 '11 at 21:18

The algorithm to embed function fields, ie. to test if a function field E can be embedded into a function field F has been developed (and implemented in Magma) by a student of Florian Hess: Gerriet Möhlmann as part of his Diploma work. His thesis (in German) can be found at http://www.math.tu-berlin.de/~kant/publications/diplom/moehlmann.pdf. The method is an extension of Florian's automorphism algorithm, in Magma, it is available through the Inclusions command.

To generate function fields of a given genus there are a few possibilities, none of them worked out completely. If the field can be obtained as an Abelian extension (eg. (hyper)elliptic curves have a degree 2 model) then class field theory can be used to generate all such fields. Similar, soluble exxtensions can be constructed this way. For general extensions, one could use Hunter's theorem to get bounds on the valuations of a primitive element and then enumerate all polynomials that might have such roots. Both methods have in common that they produce too many field extensions that correspond to isomorphic curves. The class field theoretic approach has the advantage of being available through Magma.... (I can provide details if anyone is interested)

-

Here is an algorithm (horribly inefficient) to generate all non-hyperelliptic, non-rational, separable subfields of a non-hyperelliptic function field $F$ over a finite field $K$. Let $\Omega$ be the space of global holomorphic differentials of $F/K$. For any $K$-subspace $V$ of $\Omega$, choose a basis $v_1,\ldots,v_m$ of $V$, compute the elements $v_j/v_1,j>1$ of $F$ (and compute the algebraic relations among these $v_j$), let $E_V$ be the subfield they generate. If $E_V \ne F$ and is not rational, then you found a subfield as above. All such subfields will appear this way (proof left to the reader). There are only finitely many such $V$ since $K$ is assume finite.

Don't even dream of implementing this algorithm as is. Using the numerator of the zeta function, its factors and the Cartier operator, you can perhaps cut down the number of $V$'s that need to be tested. Maybe hyperelliptic subfields can be dealt with by using quadratic differentials.

If Florian Hess can't do it, you are probably out of luck, as far as implementation goes.

Added later: For a hyperelliptic subfield of genus $>1$, one still has a subspace $V$ but the corresponding $E_V$ is the canonical rational subfield of the hyperelliptic field. In this case, the field will be intermediate between $F$ and $E_V$ and perhaps the suggestion of Dror Speiser of using number field arguments might lead to it. It's the elliptic fields that are going to be hard to get.

-
"It's the elliptic fields that are going to be hard to get." Exactly, although Tate's theorem can be used effectively to exclude them. But if they are there, then Tate tells you what they are, but does not even bound the degree of the morphism $C\to E$. –  inkspot Feb 27 '11 at 11:46