Function fields: updates to series expansion code

BrentBaccala commented 4 years ago

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

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.
~~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).~~

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)~~

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.

Component: algebraic geometry

Keywords: function field

Author: Brent Baccala

Branch/Commit: public/28922 @ 4189256

Issue created by migration from https://trac.sagemath.org/ticket/28922

BrentBaccala commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,32 @@
-This patch adds an optional `uvar` 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`.
+This patch changes three things concerning series expansions in the function field code:

-If the specified element is not a uniformizing variable at the given place, an exception is raised.
+1. The uniformizing variable can be specified

+   This patch adds an optional `uvar` 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 case:
+
+```
+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, 10)
+```
+
+   returns `s^-1 + 1 + s^2 + s^4 + s^8 + O(s^10)` instead of `s^-1 + 1 + s^2 + s^4 + s^8 + O(s^9)`

BrentBaccala commented 4 years ago

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`

BrentBaccala commented 4 years ago

Author: Brent Baccala

BrentBaccala commented 4 years ago

Commit: aa9230c

BrentBaccala commented 4 years ago

Branch: public/28922

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from aa9230c to 734c9b2

BrentBaccala commented 4 years ago

Description changed:

--- 
+++ 
@@ -1,4 +1,4 @@
-This patch changes three things concerning series expansions in the function field code:
+This patch changes four things concerning series expansions in the function field code:

 1. The uniformizing variable can be specified

@@ -30,3 +30,5 @@

returns `s^-1 + 1 + s^2 + s^4 + s^8 + O(s^10)` instead of `s^-1 + 1 + s^2 + s^4 + s^8 + O(s^9)`

+ +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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 734c9b2 to 59081b1

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

59081b1 Merge tag '9.0' into public/28922

BrentBaccala commented 4 years ago

Description changed:

--- 
+++ 
@@ -19,16 +19,16 @@

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 case: +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, 10)
+sage: m(x+y, 5)

returns s^-1 + 1 + s^2 + s^4 + s^8 + O(s^10) instead of s^-1 + 1 + s^2 + s^4 + s^8 + O(s^9)
returns s^-1 + 1 + s^2 + s^4 + O(s^5) instead of s^-1 + 1 + s^2 + O(s^4)
1. 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.

kwankyu commented 4 years ago

comment:6

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?

BrentBaccala commented 4 years ago

comment:7

Replying to @kwankyu:

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.

BrentBaccala commented 4 years ago

comment:8

Replying to @kwankyu:

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?

kwankyu commented 4 years ago

comment:9

Replying to @BrentBaccala:

Replying to @kwankyu:

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.

BrentBaccala commented 4 years ago

comment:10

Replying to @kwankyu:

Replying to @BrentBaccala:

Replying to @kwankyu:

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.

BrentBaccala commented 4 years ago

comment:11

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).

kwankyu commented 4 years ago

comment:12

My comments:

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.

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.

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.

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.

BrentBaccala commented 4 years ago

comment:13

Replying to @kwankyu:

My comments:

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.

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.

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.

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.

kwankyu commented 4 years ago

comment:14

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.")

BrentBaccala commented 4 years ago

comment:15

Replying to @kwankyu:

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.

BrentBaccala commented 4 years ago

Description changed:

--- 
+++ 
@@ -2,11 +2,11 @@

 1. The uniformizing variable can be specified

-   This patch adds an optional `uvar` 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`.
+   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:
+2. ~~If a series expansion is exact, the `O(s^n)` is dropped.  So, for example, the following test case:~~

K. = FunctionField(QQbar); _. = K[] @@ -17,9 +17,9 @@ m = L.completion(pl, prec=5) m(x)

-   now returns `I + s` instead of `I + s + O(s^5)`.
+   ~~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:
+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. = FunctionField(GF(2)); _. = K[] @@ -29,6 +29,6 @@ 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)`
+   ~~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.
+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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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`

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 59081b1 to 0ab8240

kwankyu commented 4 years ago

comment:17

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

BrentBaccala commented 4 years ago

comment:18

Replying to @kwankyu:

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:

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

Is there a flaw in any of this?

kwankyu commented 4 years ago

comment:19

Replying to @BrentBaccala:

The algorithm's logic runs like this:

Valuations are multiplicative homomorphisms, i.e, μ(fg) = μ(f) + μ(g)

This implies μ(fⁿ) = nμ(f)

So if the divisor of f is ∑mP, the divisor of fⁿ is ∑nmP

All of the nm products have to be integers for this to be a well-formed divisor

This yields line 199, with TypeError raised if any of nm's aren't integers

Droot has total degree zero, so basis will have either zero or one elements

If it has zero elements, line 201 will raise IndexError

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.

BrentBaccala commented 4 years ago

comment:20

Replying to @kwankyu:

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?

kwankyu commented 4 years ago

comment:21

Replying to @BrentBaccala:

Replying to @kwankyu:

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.

BrentBaccala commented 4 years ago

comment:22

Replying to @kwankyu:

Replying to @BrentBaccala:

Replying to @kwankyu:

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 commented 4 years ago

comment:23

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.

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

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

7ed8c4ca-6d56-4ae9-953a-41e42b4ed313 commented 4 years ago

Changed commit from 0ab8240 to 4189256

mkoeppe commented 3 years ago

comment:26

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

mkoeppe commented 3 years ago

comment:27

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

sagemath / sage

Function fields: updates to series expansion code #28922