Conversion from a function field to its field of constants

[saraedum]

Currently, there is no such conversion

sage: K.<x> = FunctionField(QQ)
sage: K(1) in QQ
False

[saraedum]

New commits:

​7960d44	Fix conversion from rational function fields to its constant base field
​69bcf16	Fix conversion of function fields into their subfields

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bb2e08e

removed indirect doctest marker

[saraedum]

I ran doctests in function_fields/. The documentation builds without errors. Let's see whether the patchbot likes it as well…

[nbruin]

Are you sure that installing a *conversion* map is the right solution? In many similar situations, there is no such map:

sage: K.<I>=NumberField(x^2+1)
sage: K(1) in QQ
True
sage: QQ._convert_map_from_(K) == None
sage: P.<t>=ZZ[]
sage: P(1) in ZZ
True
sage: ZZ._convert_map_from_(P) == None
True
sage: L.<u>=FunctionField(QQ) #this is one of your cases
sage: L(1) in QQ
False

It might be worth checking how these other cases succeed in making this work, and why they're doing it. It might be because their methods predate the coercion framework, but it might also be because introducing cycles in the conversion graph is not preferred.

[saraedum]

nbruin: Thanks for having a look at this.

Conversion to ZZ works differently:

sage: sage: K.<I>=NumberField(x^2+1)
sage: ZZ.convert_map_from(K)

Conversion via _integer_ method map:
  From: Number Field in I with defining polynomial x^2 + 1
  To:   Integer Ring
sage: ZZ.convert_map_from(QQ)

So, this path does not apply for function fields.

Asking for a conversion to QQ:

sage: QQ.convert_map_from(K)
Conversion map:
  From: Number Field in I with defining polynomial x^2 + 1
  To:   Rational Field

so a DefaultConvertMap_unique which

    […] defers action to the codomain's
    element_constructor method, WITHOUT passing in the codomain as the
    first argument. […]

i.e., the target ring needs to understand what to do with the elements. I certainly do not want to teach the rational ring what a function field element is.

Finally, cycles in conversions are no problem. Conversions are not automatically composed (unlike coercions.)

[saraedum]

I believe that installing a conversion map down to the constant base field is necessary. For the intermediate fields, one could also change _element_constructor_ to make sense of function field elements but then the _to_constant_field would get quite a bit more complicated.

[roed]

I agree with Julian that there's no problem having cycles in the conversion graph, and many rings in Sage with a concept of base ring have a conversion back to it for constants.

Julian, have you looked at how this change impacts object creation time for function fields? Maybe it would be better to implement this in _convert_map_from_ rather than calling register_conversion in __init__. I think register_conversion is available for end users who aren't able to modify _convert_map_from_.

Otherwise, I'm happy with this change, and willing to give a positive review once we hear back from the patchbot.

[saraedum]

For the conversion down to the constant base field, I do not really have an option. (I would have to change _convert_map_from_ for Field or something similar.)

sage: K.<x> = FunctionField(QQ)
sage: from sage.rings.function_field.function_field import FunctionField_polymod
sage: K.<x> = FunctionField(QQ)
sage: R.<y> = K[]
sage: # work around caching by calling the class directly
sage: %timeit FunctionField_polymod(y^2-x, 'y')

Yes, object creation time does go up here from 332 µs to 555 µs. I am not sure if that is an issue. Function fields are cached after all, and I have a hard time imagining someone to create tons of them with different defining polynomials. I implemented this with _convert_map_from_ on the level of function fields (but I still need the register_conversion_map for the constant base field) which gets this number down to 440 µs. Imho, the code is substantially less readable that way. So, about 110 µs seems to be the cost of a call to register_conversion_map.

David, what do you think?

[saraedum]

PS: I am planning to install another conversion down to the polynomial ring that is used to implement the elements of the function field, i.e., K(x) to K[x]. Here again, I won't have no choice but to register the conversion in __init__, so using _convert_map_from_ is about 660 µs or 550 µs which does not look like that much of a difference anymore.

[roed]

You're right that we'll need register_conversion_map for the constant field and for K[x]. I'm fine with a 20% slowdown in parent creation for the sake of readibility, though I would be curious to know if Nils has use cases where he wants to create tons of different function fields and object creation is the bottleneck. I guess another instance where your approach would cause problems is deeply nested relative extensions of function fields, where the total number of conversion maps created grows quadratically with the depth. I don't think that's a common use case though....

[nbruin]

Replying to roed:

I would be curious to know if Nils has use cases where he wants to create tons of different function fields and object creation is the bottleneck.

I don't have immediate examples, although I could imagine that fibred surfaces (either arithmetic or otherwise) might give rise to such a scenario. The bottleneck could arise if someone wants to try something really easy with the fibers, but ends up creating the fibers as curves and perhaps creating the function fields as an unintended side-effect. I don't know if the kind of slow-downs we're talking about here would be likely to be significant in such a setting.

I guess another instance where your approach would cause problems is deeply nested relative extensions of function fields, where the total number of conversion maps created grows quadratically with the depth. I don't think that's a common use case though....

Indeed, but I would suggest being a little conservative with implementing this. Can we first just install the conversion to the base ring and not transitively close over all the base rings below that?

Incidentally, you have to be very careful about how you implement the conversion maps to the base rings. They will be cached on the codomain (i.e., on the base ring), so you should make sure you're *not* storing any references to the domain or its elements in the map object. All of that needs to be recovered from the argument (this is part of the reason why conversion to ZZ is implemented the way it is).

Otherwise, you'll see that function fields over QQ end up not being garbage collected, because an eternal object (QQ) is keeping a reference to them in the form of registered conversion maps. This is why maps in the coercion system do NOT store their domain. See #14711 for some of the black magic that was required.

So, one thing you should probably test is that

K.<t>=FunctionField(QQ)
P.<X>=PolynomialRing(K)
c=1
while True:
  L=K.extension(X^2-t^2+c*t)
  u=QQ(L(1))

doesn't leak.

[roed]

Replying to nbruin:

Incidentally, you have to be very careful about how you implement the conversion maps to the base rings. They will be cached on the codomain (i.e., on the base ring), so you should make sure you're *not* storing any references to the domain or its elements in the map object. All of that needs to be recovered from the argument (this is part of the reason why conversion to ZZ is implemented the way it is).

Good point; I think the current implementation has this problem.

Otherwise, you'll see that function fields over QQ end up not being garbage collected, because an eternal object (QQ) is keeping a reference to them in the form of registered conversion maps. This is why maps in the coercion system do NOT store their domain. See #14711 for some of the black magic that was required.

#14711 is interesting. I'll have to think about how that should affect conversions. But the memory leak issue definitely should be addressed.

So, one thing you should probably test is that

K.<t>=FunctionField(QQ)
P.<X>=PolynomialRing(K)
c=1
while True:
  L=K.extension(X^2-t^2+c*t)
  u=QQ(L(1))

doesn't leak.

I assume you want to increment c inside your loop.

[roed]

Note that #14711 has a TODO of adding an option to register_conversion to use weak references as well. I think we need that option here, but that should solve the problem you've pointed out.

[nbruin]

I assume you want to increment c inside your loop.

yes, although I now realize that this ticket only seems to be dealing with rational function fields, so the test should be amended accordingly.

Replying to roed:

Note that #14711 has a TODO of adding an option to register_conversion to use weak references as well. I think we need that option here, but that should solve the problem you've pointed out.

Yes, with the implementation of the conversion map proposed here, it should. I don't think the maps store any references to the domain internally. In the mean time, you should use something like

   phi = to_be_registered_map
   phi._make_weak_references() #this should remove the strong references
   K.register_conversion(phi)
   del phi #or just make sure that phi doesn't escape elsewhere

[saraedum]

Thanks for all the input. I had not thought about leaks here. Sadly, _make_weak_references() does not do the trick. The register_convert_map implementation has a line that says self._convert_from_hash.set(mor.domain(),mor) which does not seem to use weak references.

[saraedum]

Actually _convert_from_hash does use weak references, so it must be leaking somewhere else…

[saraedum]

Ok. The problem is the SetMorphism that I have been using. The parameter self._to_constant_base_field that I pass in holds a reference to the function field. I am going to upload a version that uses a proper FunctionFieldConversionToConstantBaseField map. Also, I found a way to implement _conversion_map_from_ that makes the code not unreadable.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​7b2d90c	Use _convert_map_from_
​0b87e90	Wire up conversion to the constant base field in the FunctionField base class

[saraedum]

This needs review again.

[nbruin]

Little doc nitpick:

+    def _to_base_field(self, f):
...
+        - ``f`` -- an element of this function field which is already defined
+          over the base field

you probably mean "an element of the function field that lies in the base field". All elements of the function field are defined over the base field by definition.

Elsewhere: be careful with calling subfields "constants". For instance, the function field QQ(x)[y]/(y^2-2) has as constant subfield QQ(sqrt(2)), whereas the base field is QQ. Finding the exact constant field (i.e., the algebraic closure of the base field in the function field) takes considerable computation, so I'm not sure this is part of the scope of this ticket.

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​21a6a10

improve wording on base fields

[saraedum]

The patchbot complains about modsym/space.py. I checked locally and it works fine. (It would also have been very suprising if this made a difference there.)

[roed]

I'm happy with the changes. Nils, thanks for the suggestions: feel free to add yourself as a reviewer.