Opened 3 years ago
Closed 3 years ago
#28094 closed enhancement (fixed)
support function fields in characteristic zero
Reported by:  Brent Baccala  Owned by:  

Priority:  major  Milestone:  sage9.0 
Component:  algebraic geometry  Keywords:  function fields 
Cc:  Merged in:  
Authors:  Brent Baccala  Reviewers:  Travis Scrimshaw, Kwankyu Lee 
Report Upstream:  N/A  Work issues:  
Branch:  77dbf93 (Commits, GitHub, GitLab)  Commit:  77dbf93d3116cf33e090d79607803d96c349e68b 
Dependencies:  Stopgaps: 
Description (last modified by )
Current function field code only works in prime characteristic.
This ticket supports function fields over QQ and NumberField?'s.
After Trac #25390 is integrated, it should also support function fields over QQbar.
Attachments (2)
Change History (31)
Changed 3 years ago by
Attachment:  decomposition.pdf added 

comment:1 Changed 3 years ago by
Branch:  → public/28094 

Commit:  → b0862a94a9601814bd0d6fd941baae6e2cc2ed2d 
Milestone:  sage8.9 → sage9.0 
Last 10 new commits:
d247e7d  Trac #28094: constructor creates FunctionField_integral's if conditions are right

fc0f191  Trac #28094: add new decomposition method to FunctionFieldMaximalOrder_polymod

de8ff74  Trac #28094: add class FunctionFieldHigherDerivation_charzero

0ade7d0  Trac #28094: introduce classes FunctionField_charzero,

efefd59  Trac #28094: remove FunctionFieldCompletion_global, use

2f918fb  Trac #28094: move `valuation` method to superclass so that elements

46f0857  Trac #28094: move `different` method to superclass

e52cae0  Trac #28094: update decomposition algorithm (mostly the description)

c689837  remove QQbar from the test suite, because QQbar won't work with this

b0862a9  Merge tag '9.0.beta0' into public/28094

comment:2 Changed 3 years ago by
Commit:  b0862a94a9601814bd0d6fd941baae6e2cc2ed2d → 865d513907819a415a2135b48d11f638aea021de 

Branch pushed to git repo; I updated commit sha1. New commits:
865d513  Trac #28094: construct extension fields when forming residue fields,

comment:3 Changed 3 years ago by
Current status of this ticket:
 It mostly works!
 There's a new algorithm (see attached pdf and tex files) to compute decomposition of prime ideals in extension fields. The older algorithm, which only works in characteristic p, is still used in characteristic p.
 One way of testing the new decomposition algorithm is to comment out the old algorithm. This produces a bunch of failures in the test cases, but they all look like different ways of writing the same ideals, not actual failures.
 It needs test cases. Lots of them. We have almost no tests for characteristic zero. Many of the characteristic p test cases could be adapted to characteristic zero.
 Once Trac #25390 is integrated, it should work over the algebraic field.
comment:4 Changed 3 years ago by
Commit:  865d513907819a415a2135b48d11f638aea021de → 6e9b58faf623a5bd83a20fc8703995ffa3e8658c 

Branch pushed to git repo; I updated commit sha1. New commits:
e32b3a1  Trac #28094: wrap ring normalization code in a decorator that allows

478f1a9  Trac #28094: add some examples to showcase function fields over QQ

5cfd3d7  Trac #28094: Move _inversion_isomorphism from FunctionField_global to superclass FunctionField_polymod

6e9b58f  Trac #28094: update a failing doctest

comment:5 Changed 3 years ago by
Commit:  6e9b58faf623a5bd83a20fc8703995ffa3e8658c → 4e584b5c3779bf2723ab8b543d6efe762030d1ec 

Branch pushed to git repo; I updated commit sha1. New commits:
4e584b5  Trac #28094: a slight patch since QQbar isn't considered a NumberField

comment:6 Changed 3 years ago by
Commit:  4e584b5c3779bf2723ab8b543d6efe762030d1ec → 49c3aec301f0439f18f66413f0c16d1360f32584 

comment:7 Changed 3 years ago by
Commit:  49c3aec301f0439f18f66413f0c16d1360f32584 → 76cd59e3f6e077980248314e33de020c5647da81 

Branch pushed to git repo; I updated commit sha1. New commits:
76cd59e  Trac #28094: add more doctests for characteristic zero

comment:8 Changed 3 years ago by
Commit:  76cd59e3f6e077980248314e33de020c5647da81 → bb6d83c7d979df945de62bdfb2d7a62b16eb5167 

comment:9 Changed 3 years ago by
Commit:  bb6d83c7d979df945de62bdfb2d7a62b16eb5167 → a72c5188a801af2bc6a2225365bb5f76c5d2730f 

Branch pushed to git repo; I updated commit sha1. New commits:
a72c518  Merge tag '9.0.beta3' into public/28094

comment:10 Changed 3 years ago by
Description:  modified (diff) 

Status:  new → needs_review 
comment:11 Changed 3 years ago by
Commit:  a72c5188a801af2bc6a2225365bb5f76c5d2730f → 07b6a0c20a26c08aaf16c192830cd095128ae2a7 

Branch pushed to git repo; I updated commit sha1. New commits:
07b6a0c  Merge tag '9.0.beta4' into public/28094

comment:12 Changed 3 years ago by
Status:  needs_review → needs_work 

Some little things from a quick read through:
 ``separating_element``  separating element of the function field;  the default is the generator of the rational function field + the default is the generator of the rational function field
Function fields over the rational field are supported: +Function fields over the rational field are supported::
 G.M.Greuel, S.Laplagne, F.Seelisch: Normalization of Rings (2009). + G.M. Greuel, S. Laplagne, F. Seelisch: Normalization of Rings (2009).
Missing doctests on _singular_normal
and FunctionFieldIdeal_global.__init__
(which should be a TestSuite(foo).run()
).
In FunctionFieldIdeal_global.gens_two()
, it should be ALGORITHM:
and no indentation there, and without dollar signs.
In FunctionFieldHigherDerivation_charzero._derive
, I don't see the point of the internal derive
function. Also, I believe it is considered better practice to do def derivative(f): return f.derivative()
since you are naming the function.
In FunctionFieldMaximalOrder_global.decomposition
, the .. TODO::
block needs to be indented. I would also do
is done in `FunctionFieldMaximalOrder_global`'s `decomposition` +is done in :meth:`FunctionFieldMaximalOrder_global.decomposition()`
comment:13 Changed 3 years ago by
Commit:  07b6a0c20a26c08aaf16c192830cd095128ae2a7 → f9bab18e403c62f5f66d591e11008bd6a0c134c5 

Branch pushed to git repo; I updated commit sha1. New commits:
55b65b0  Trac #28094: improve _singular_normal()

0f55dd2  Trac #28094: address issues raised in tscrim's comment:12

c6af97a  Trac #28094: move `places_above` from FunctionField_global to

71f5f18  Trac #28094: major bug fix. Correctly calculate residue fields

a96e079  Trac #28094: bug fix. Correctly compute residue fields and

5f162a4  Trac #28094: add a basic test case for func fields over QQbar

9465800  Merge tag '9.0.beta7' into public/28094

f9bab18  Trac #28094: pass list (not generator) to FiniteDimensionalAlgebra

comment:14 Changed 3 years ago by
Status:  needs_work → needs_review 

I've addressed all of the issues from comment:12 and have fixed a serious bug that I uncovered with some more testing.
I'd like to add some more test cases for function fields over QQbar
(and likely will), but other than that I again think that this ticket is ready for review.
comment:15 followup: 17 Changed 3 years ago by
Status:  needs_review → needs_work 

Before the patch,
sage: K.<x> = FunctionField(GF(3)) sage: _.<Y> = K[] sage: L.<y> = K.extension(Yx) sage: y.zeros() [Place (x)]
After the patch,
sage: K.<x> = FunctionField(GF(3)) sage: _.<Y> = K[] sage: L.<y> = K.extension(Yx) sage: y.zeros() [Place (x, 0)]
comment:16 Changed 3 years ago by
Commit:  f9bab18e403c62f5f66d591e11008bd6a0c134c5 → 87fe1472c7da2912d4ff68c1cc42b4fe3a8447b4 

comment:17 Changed 3 years ago by
Status:  needs_work → needs_review 

Replying to klee:
Looks like I dropped some code during one of my refactoring steps. Fixed.
comment:18 Changed 3 years ago by
Commit:  87fe1472c7da2912d4ff68c1cc42b4fe3a8447b4 → 492a6677006eedd3a7205add2d363f0424edfb1c 

Branch pushed to git repo; I updated commit sha1. New commits:
d36e58b  Trac #28094: add Brent Baccala as author to some files where

790cf8b  Trac #28094: update documentation to reflect improved support

5d26c7d  Trac #28094: change an error message to better reflect its cause

06f81e2  Trac #28094: add more examples and test cases for characteristic zero

492a667  Merge tag '9.0.beta9' into public/28094

comment:19 followup: 20 Changed 3 years ago by
Kwankyu, can you do a check of the mathematical correctness? I can recheck the code, but I doubt there will be anything more from my side.
comment:20 Changed 3 years ago by
Replying to tscrim:
Kwankyu, can you do a check of the mathematical correctness? I can recheck the code, but I doubt there will be anything more from my side.
Ok. That is on my todo list.
comment:21 Changed 3 years ago by
Commit:  492a6677006eedd3a7205add2d363f0424edfb1c → 6760fd41d1676cbef776396b9ea28487e8524871 

Branch pushed to git repo; I updated commit sha1. New commits:
6760fd4  Lots of cleanups

comment:22 Changed 3 years ago by
It is a nice work. I made lots of small changes to tidy up the overall function field code. Most of them are just for better style and for better naming. I made also some refactoring to add more functionality to function fields of char zero.
I give positive review on the base code. Please review on my part of modifications. Then this is good to go.
comment:23 Changed 3 years ago by
I observe a serious speed regression on computing maximal orders of global function fields:
Previously,
sage: k.<a>=GF(3^3) ....: K.<x>=FunctionField(k); _.<s>=K[] ....: L.<y>=K.extension(s^9 + x^72*s^3 + x^96*s + 2*x^104 + 2*x^96) ....: sage: time L.maximal_order() CPU times: user 3.41 s, sys: 33.8 ms, total: 3.44 s Wall time: 3.45 s Maximal order of Function field in y defined by y^9 + x^72*y^3 + x^96*y + 2*x^104 + 2*x^96
Now with the patch,
sage: k.<a>=GF(3^3) ....: K.<x>=FunctionField(k); _.<s>=K[] ....: L.<y>=K.extension(s^9 + x^72*s^3 + x^96*s + 2*x^104 + 2*x^96) ....: sage: time L.maximal_order() CPU times: user 35.1 s, sys: 168 ms, total: 35.3 s Wall time: 35.2 s Maximal order of Function field in y defined by y^9 + x^72*y^3 + x^96*y + 2*x^104 + 2*x^96
This is actually expected because now Singular's generic normalization algorithm is used while previously a custom implementation (in ext/singular/function_field/core.lib
)of LeonardPellikaanSinghSwanson algorithm specialized for finite field was used.
I think we should recover the previous algorithm for global function fields.
comment:24 Changed 3 years ago by
Commit:  6760fd41d1676cbef776396b9ea28487e8524871 → 77dbf93d3116cf33e090d79607803d96c349e68b 

Branch pushed to git repo; I updated commit sha1. New commits:
77dbf93  Recover normalization algorithm for global function fields

comment:25 Changed 3 years ago by
By the way, I get this timing on Mac pro
sage: k.<a>=GF(3^3) ....: K.<x>=FunctionField(k); _.<s>=K[] ....: L.<y>=K.extension(s^9 + x^72*s^3 + x^96*s + 2*x^104 + 2*x^96) ....: sage: time L.genus() # 5.08s CPU times: user 27.3 s, sys: 83.7 ms, total: 27.4 s Wall time: 27.4 s 12
5.08s is the timing I got more than two years ago on a slower labtop. I wonder what have happened with sage meanwhile. Sigh..
comment:26 Changed 3 years ago by
Status:  needs_review → positive_review 

Approved. We can study the performance regression on another ticket.
comment:28 Changed 3 years ago by
Authors:  → Brent Baccala 

Reviewers:  → Travis Scrimshaw, Kwankyu Lee 
comment:29 Changed 3 years ago by
Branch:  public/28094 → 77dbf93d3116cf33e090d79607803d96c349e68b 

Resolution:  → fixed 
Status:  positive_review → closed 
Description of algorithm to decompose prime ideals in an extension