Function fields: updates to series expansion code

[gh-BrentBaccala]

This patch changes four things concerning series expansions in the function field code:

1. The uniformizing variable can be specified

This patch adds an optional local_uniformizer argument to FunctionField's completion() method. It accepts either a function field element or an element of the Symbolic Ring constructed from a root of a function field element. This allows, for example, sqrt(x) to be specified as a uniformizing variable without knowing a specific function field element that is a square root of x.

If the specified element is not a uniformizing variable at the given place, an exception is raised.

2. If a series expansion is exact, the O(s^n) is dropped. So, for example, the following test case:

K.<x> = FunctionField(QQbar); _.<Y> = K[]
L.<y> = K.extension(Y^2 + Y + x + 1/x)
O = L.maximal_order()
I = O.ideal(y)
pl = I.divisor().support()[0]
m = L.completion(pl, prec=5)
m(x)

now returns I + s instead of I + s + O(s^5).

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage. So, now, this test:

sage: K.<x> = FunctionField(GF(2)); _.<Y> = K[]
sage: L.<y> = K.extension(Y^2 + Y + x + 1/x)
sage: p = L.places_finite()[0]
sage: m = L.completion(p)
sage: m(x+y, 5)

returns s^-1 + 1 + s^2 + s^4 + O(s^5) instead of s^-1 + 1 + s^2 + O(s^4)

4. Function field elements can now be raised to fractional powers. If the fractional power does not exist in the function field, a result in the Symbolic Ring is returned. While not, strictly speaking, a change to the series expansion code, this change allows fractional powers like x^(1/3) to be specified as uniformizing variables.

[gh-BrentBaccala]

New commits:

​fca168d	Trac #28922: allow series completion's uniformizing variable to be specified
​2dba013	Trac #28922: return exact results for series expansions that are exact
​f27c629	Trac #28922: modified test cases that now return exact results
​dc2b7a7	Trac #28922: function field series expansion now uses absolute precision,
​aa9230c	Trac #28922: simplify a doctest

[git]

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

​012365f	Trac #28922: compute fractional powers of function field elements
​734c9b2	Trac #28922: no longer need to cast into SR to take roots of fraction field elements

[git]

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

​59081b1

Merge tag '9.0' into public/28922

[klee]

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage.

Why is "absolute precision" more aligned with the rest of Sage? What is the evidence?

[gh-BrentBaccala]

Replying to klee:

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage.

Why is "absolute precision" more aligned with the rest of Sage? What is the evidence?

Taylor and Laurent series expansions in the Symbolic Ring are specified using absolute precision.

sage: var('x')
x

sage: sin(x).series(x,4)
1*x + (-1/6)*x^3 + Order(x^4)

sage: (1/(x^2+x)).series(x,4)
1*x^(-1) + (-1) + 1*x + (-1)*x^2 + 1*x^3 + Order(x^4)

I am not aware of any other examples.

[gh-BrentBaccala]

Replying to klee:

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage.

Why is "absolute precision" more aligned with the rest of Sage? What is the evidence?

Have you already written a lot of code that uses relative precision?

[klee]

Replying to gh-BrentBaccala:

Replying to klee:

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage.

Why is "absolute precision" more aligned with the rest of Sage? What is the evidence?

Have you already written a lot of code that uses relative precision?

No. But no change to an existing interface should be made without a compelling reason.

[gh-BrentBaccala]

Replying to klee:

Replying to gh-BrentBaccala:

Replying to klee:

3. The precision is now specified as absolute precision, instead of relative. This is a backwards incompatible change made to bring the function field code into alignment with the rest of Sage.

Why is "absolute precision" more aligned with the rest of Sage? What is the evidence?

Have you already written a lot of code that uses relative precision?

No. But no change to an existing interface should be made without a compelling reason.

I agree. I suggest making this change now, since I believe that a uniform interface is a compelling reason.

[gh-BrentBaccala]

Another reason to use absolute precision is that a common construction is to calculate the principal part of the series expansion (i.e, the negative powers). With absolute precision, it's easier to specify: prec=0 instead of prec=-A.valuation(pl)(f).

[klee]

My comments:

4. Function field elements can now be raised to fractional powers.

As far as I understand, fractional power, as an operation, is not well defined for elements of an algebraic function field. It may not even exist, and then you return a symbolic ring element. I don't get this. In general, I object to the idea of injecting symbolic ring stuff into exact function field computation.

2. If a series expansion is exact, the O(s^n) is dropped.

Why slow down series expansion computation to check if it is exact? If you want an exact result for your computation, you can check it and get it. This does not make sense to me.

1. The uniformizing variable can be specified

Ok. But please use the name local_uniformizeror shortly uniformizer for consistency. This is only acceptable if you do not clutter the series expansion code with the fractional power stuff.

3. The precision is now specified as absolute precision, instead of relative.

Ok. But this need a deprecation warning as it is an user interface change.

[gh-BrentBaccala]

Replying to klee:

My comments:

4. Function field elements can now be raised to fractional powers.

As far as I understand, fractional power, as an operation, is not well defined for elements of an algebraic function field. It may not even exist, and then you return a symbolic ring element. I don't get this. In general, I object to the idea of injecting symbolic ring stuff into exact function field computation.

OK, I'll drop the symbolic ring stuff, and only return fractional powers if they actually exist, otherwise raise an exception.

I did the symbolic ring stuff so that a uniformizing variable could be specified as something like sqrt(x) even if such an element didn't actually exist.

2. If a series expansion is exact, the O(s^n) is dropped.

Why slow down series expansion computation to check if it is exact? If you want an exact result for your computation, you can check it and get it. This does not make sense to me.

sage: var('x')
x
sage: x.series(x)
1*x + Order(x^20)

OK, not what I expected, but it's consistent with what you propose.

1. The uniformizing variable can be specified

Ok. But please use the name local_uniformizeror shortly uniformizer for consistency. This is only acceptable if you do not clutter the series expansion code with the fractional power stuff.

OK, I'll go with local_uniformizer. I'll rip the fractional power stuff out of the series expansion code and require an actual function field element to be specified as the local_uniformizer.

3. The precision is now specified as absolute precision, instead of relative.

Ok. But this need a deprecation warning as it is an user interface change.

I'm not sure how to do that. The current deprecation warnings are for entire methods that have been dropped. I don't think we have anything to announce that an existing method has changed its interpretation of its arguments, nor can I think of a good way to implement such a warning, since the code could never tell which interpretation was intended.

[klee]

Ok. But this need a deprecation warning as it is an user interface change.

I'm not sure how to do that. The current deprecation warnings are for entire methods that have been dropped. I don't think we have anything to announce that an existing method has changed its interpretation of its arguments, nor can I think of a good way to implement such a warning, since the code could never tell which interpretation was intended.

It would suffice to warn the user:

sage.misc.superseded.warning(28922, "Mind that prec now means absolute precision.")

[gh-BrentBaccala]

Replying to klee:

Ok. But this need a deprecation warning as it is an user interface change.

I'm not sure how to do that. The current deprecation warnings are for entire methods that have been dropped. I don't think we have anything to announce that an existing method has changed its interpretation of its arguments, nor can I think of a good way to implement such a warning, since the code could never tell which interpretation was intended.

It would suffice to warn the user:

sage.misc.superseded.warning(28922, "Mind that prec now means absolute precision.")

I don't like that user interface. It seems like the only way to disable the warning is to disable all warnings. Since the Trac number is included in the message, it would be nice to have a feature where warnings associated with given tickets are silenced, but that's another feature entirely.

I'll just drop this change.

[git]

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

​7c9d261	Trac #28922: don't check for exact result in series expansion
​6df8f55	Trac #28922: if a fractional power can't be taken, raise an exception
​faeb46d	Trac #28922: use 'local_uniformizer' instead of 'uvar' and require
​c258884	Revert "Trac #28922: function field series expansion now uses absolute precision,"
​0ab8240	Merge tag '9.1.beta0' into public/28922

[klee]

Is the algorithm for computing the fractional power correct? I don't see how root has the divisor you want.

[gh-BrentBaccala]

Replying to klee:

Is the algorithm for computing the fractional power correct? I don't see how root has the divisor you want.

191         numer = right.numerator()
192         denom = right.denominator()
193 
194         if denom == 1:
195             return self._pow_int(right)
196         else:
197             try:
198                 D = self.divisor()
199                 Droot = sum([Integer(m*right)*pl for pl,m in D.dict().items()])
200                 basis = (-Droot).basis_function_space()
201                 root = basis[0]
202                 coeff = self.parent().constant_base_field()(self**numer)/(root**denom))**(1/denom)
203                 return coeff*root
204             except (TypeError, IndexError):
205                 pass
206             raise ValueError("not a %s power"%Integer(denom).ordinal_str())

The algorithm's logic runs like this:

1. Valuations are multiplicative homomorphisms, i.e, μ(fg) = μ(f) + μ(g)
2. This implies μ(fⁿ) = nμ(f)
3. So if the divisor of f is ∑mP, the divisor of fⁿ is ∑nmP
4. All of the nm products have to be integers for this to be a well-formed divisor
5. This yields line 199, with TypeError raised if any of nm's aren't integers
6. Droot has total degree zero, so basis will have either zero or one elements
7. If it has zero elements, line 201 will raise IndexError
8. If we make it to line 202, we've found an element with the correct divisor

Is there a flaw in any of this?

[klee]

Replying to gh-BrentBaccala:

The algorithm's logic runs like this:

1. Valuations are multiplicative homomorphisms, i.e, μ(fg) = μ(f) + μ(g)
2. This implies μ(fⁿ) = nμ(f)
3. So if the divisor of f is ∑mP, the divisor of fⁿ is ∑nmP
4. All of the nm products have to be integers for this to be a well-formed divisor
5. This yields line 199, with TypeError raised if any of nm's aren't integers
6. Droot has total degree zero, so basis will have either zero or one elements
7. If it has zero elements, line 201 will raise IndexError
8. If we make it to line 202, we've found an element with the correct divisor

I see. Thanks.

It seems you are assuming the constant field is full, that is, the base constant field is the algebraic closure of itself. Right? Then perhaps you can develop the algorithm further such that it works without that assumption. Moreover this would be a prerequisite for is_square to work correctly.

[gh-BrentBaccala]

Replying to klee:

I see. Thanks.

It seems you are assuming the constant field is full, that is, the base constant field is the algebraic closure of itself. Right? Then perhaps you can develop the algorithm further such that it works without that assumption. Moreover this would be a prerequisite for is_square to work correctly.

That's very likely. I work almost exclusively with algebraically closed constant fields. Where is the problem, exactly? I'm guessing it has to do with the behavior of the divisors?

[klee]

Replying to gh-BrentBaccala:

Replying to klee:

I see. Thanks.

It seems you are assuming the constant field is full, that is, the base constant field is the algebraic closure of itself. Right? Then perhaps you can develop the algorithm further such that it works without that assumption. Moreover this would be a prerequisite for is_square to work correctly.

That's very likely. I work almost exclusively with algebraically closed constant fields. Where is the problem, exactly? I'm guessing it has to do with the behavior of the divisors?

self/root^n is in the full constant field, which is the Riemann-Roch space of zero divisor.

[gh-BrentBaccala]

Replying to klee:

Replying to gh-BrentBaccala:

Replying to klee:

I see. Thanks.

It seems you are assuming the constant field is full, that is, the base constant field is the algebraic closure of itself. Right? Then perhaps you can develop the algorithm further such that it works without that assumption. Moreover this would be a prerequisite for is_square to work correctly.

That's very likely. I work almost exclusively with algebraically closed constant fields. Where is the problem, exactly? I'm guessing it has to do with the behavior of the divisors?

self/root^n is in the full constant field, which is the Riemann-Roch space of zero divisor.

OK, I see.

Thank you.

I spent quite a while convincing myself that the homomorphism logic in steps 1-5 was correct, but I never considered for a minute that the zero divisor might have dimension greater than one.

[mkoeppe]

Batch modifying tickets that will likely not be ready for 9.1, based on a review of the ticket title, branch/review status, and last modification date.

[git]

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

​8240552	Merge tag '9.2.beta0' into public/28922
​6fd8451	Trac #28922: silence pyflakes warnings
​4189256	an attempt to implement __pow__ for function field elements... but

[mkoeppe]

Setting new milestone based on a cursory review of ticket status, priority, and last modification date.

[mkoeppe]

Setting a new milestone for this ticket based on a cursory review.