Opened 3 years ago

Closed 3 years ago

#28094 closed enhancement (fixed)

support function fields in characteristic zero

Reported by: gh-BrentBaccala Owned by:
Priority: major Milestone: sage-9.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:

Status badges

Description (last modified by gh-BrentBaccala)

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)

decomposition.pdf (149.3 KB) - added by gh-BrentBaccala 3 years ago.
Description of algorithm to decompose prime ideals in an extension
decomposition.tex (11.1 KB) - added by gh-BrentBaccala 3 years ago.
LaTex? source of decomposition.pdf

Download all attachments as: .zip

Change History (31)

Changed 3 years ago by gh-BrentBaccala

Description of algorithm to decompose prime ideals in an extension

Changed 3 years ago by gh-BrentBaccala

LaTex? source of decomposition.pdf

comment:1 Changed 3 years ago by gh-BrentBaccala

  • Branch set to public/28094
  • Commit set to b0862a94a9601814bd0d6fd941baae6e2cc2ed2d
  • Milestone changed from sage-8.9 to sage-9.0

Last 10 new commits:

d247e7dTrac #28094: constructor creates FunctionField_integral's if conditions are right
fc0f191Trac #28094: add new decomposition method to FunctionFieldMaximalOrder_polymod
de8ff74Trac #28094: add class FunctionFieldHigherDerivation_charzero
0ade7d0Trac #28094: introduce classes FunctionField_charzero,
efefd59Trac #28094: remove FunctionFieldCompletion_global, use
2f918fbTrac #28094: move `valuation` method to superclass so that elements
46f0857Trac #28094: move `different` method to superclass
e52cae0Trac #28094: update decomposition algorithm (mostly the description)
c689837remove QQbar from the test suite, because QQbar won't work with this
b0862a9Merge tag '9.0.beta0' into public/28094

comment:2 Changed 3 years ago by git

  • Commit changed from b0862a94a9601814bd0d6fd941baae6e2cc2ed2d to 865d513907819a415a2135b48d11f638aea021de

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

865d513Trac #28094: construct extension fields when forming residue fields,

comment:3 Changed 3 years ago by gh-BrentBaccala

Current status of this ticket:

  1. It mostly works!
  1. 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.
  1. 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.
  1. 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.
  1. Once Trac #25390 is integrated, it should work over the algebraic field.

New commits:

865d513Trac #28094: construct extension fields when forming residue fields,

New commits:

865d513Trac #28094: construct extension fields when forming residue fields,
Version 0, edited 3 years ago by gh-BrentBaccala (next)

comment:4 Changed 3 years ago by git

  • Commit changed from 865d513907819a415a2135b48d11f638aea021de to 6e9b58faf623a5bd83a20fc8703995ffa3e8658c

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

e32b3a1Trac #28094: wrap ring normalization code in a decorator that allows
478f1a9Trac #28094: add some examples to showcase function fields over QQ
5cfd3d7Trac #28094: Move _inversion_isomorphism from FunctionField_global to superclass FunctionField_polymod
6e9b58fTrac #28094: update a failing doctest

comment:5 Changed 3 years ago by git

  • Commit changed from 6e9b58faf623a5bd83a20fc8703995ffa3e8658c to 4e584b5c3779bf2723ab8b543d6efe762030d1ec

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

4e584b5Trac #28094: a slight patch since QQbar isn't considered a NumberField

comment:6 Changed 3 years ago by git

  • Commit changed from 4e584b5c3779bf2723ab8b543d6efe762030d1ec to 49c3aec301f0439f18f66413f0c16d1360f32584

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

623ba60Trac #28094: add some doctests for function fields over QQ and NumberField's
49c3aecTrac #28094: move method `higher_derivative` to superclass FunctionFieldElement

comment:7 Changed 3 years ago by git

  • Commit changed from 49c3aec301f0439f18f66413f0c16d1360f32584 to 76cd59e3f6e077980248314e33de020c5647da81

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

76cd59eTrac #28094: add more doctests for characteristic zero

comment:8 Changed 3 years ago by git

  • Commit changed from 76cd59e3f6e077980248314e33de020c5647da81 to bb6d83c7d979df945de62bdfb2d7a62b16eb5167

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

85d5640Trac #28094: add more characteristic zero doctests
bb6d83cTrac #28094: documentation indicates that advanced calculations now available

comment:9 Changed 3 years ago by git

  • Commit changed from bb6d83c7d979df945de62bdfb2d7a62b16eb5167 to a72c5188a801af2bc6a2225365bb5f76c5d2730f

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

a72c518Merge tag '9.0.beta3' into public/28094

comment:10 Changed 3 years ago by gh-BrentBaccala

  • Description modified (diff)
  • Status changed from new to needs_review

comment:11 Changed 3 years ago by git

  • Commit changed from a72c5188a801af2bc6a2225365bb5f76c5d2730f to 07b6a0c20a26c08aaf16c192830cd095128ae2a7

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

07b6a0cMerge tag '9.0.beta4' into public/28094

comment:12 Changed 3 years ago by tscrim

  • Status changed from needs_review to 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 git

  • Commit changed from 07b6a0c20a26c08aaf16c192830cd095128ae2a7 to f9bab18e403c62f5f66d591e11008bd6a0c134c5

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

55b65b0Trac #28094: improve _singular_normal()
0f55dd2Trac #28094: address issues raised in tscrim's comment:12
c6af97aTrac #28094: move `places_above` from FunctionField_global to
71f5f18Trac #28094: major bug fix. Correctly calculate residue fields
a96e079Trac #28094: bug fix. Correctly compute residue fields and
5f162a4Trac #28094: add a basic test case for func fields over QQbar
9465800Merge tag '9.0.beta7' into public/28094
f9bab18Trac #28094: pass list (not generator) to FiniteDimensionalAlgebra

comment:14 Changed 3 years ago by gh-BrentBaccala

  • Status changed from needs_work to 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 follow-up: Changed 3 years ago by klee

  • Status changed from needs_review to needs_work

Before the patch,

sage: K.<x> = FunctionField(GF(3))
sage: _.<Y> = K[]
sage: L.<y> = K.extension(Y-x)
sage: y.zeros()
[Place (x)]

After the patch,

sage: K.<x> = FunctionField(GF(3))
sage: _.<Y> = K[]
sage: L.<y> = K.extension(Y-x)
sage: y.zeros()
[Place (x, 0)]

comment:16 Changed 3 years ago by git

  • Commit changed from f9bab18e403c62f5f66d591e11008bd6a0c134c5 to 87fe1472c7da2912d4ff68c1cc42b4fe3a8447b4

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

c831ab1Trac #28094: replace some code accidently dropped in 06ba5dac
87fe147Trac #28094: add klee's doctest that caught the problem fixed by c831ab15

comment:17 in reply to: ↑ 15 Changed 3 years ago by gh-BrentBaccala

  • Status changed from needs_work to 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 git

  • Commit changed from 87fe1472c7da2912d4ff68c1cc42b4fe3a8447b4 to 492a6677006eedd3a7205add2d363f0424edfb1c

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

d36e58bTrac #28094: add Brent Baccala as author to some files where
790cf8bTrac #28094: update documentation to reflect improved support
5d26c7dTrac #28094: change an error message to better reflect its cause
06f81e2Trac #28094: add more examples and test cases for characteristic zero
492a667Merge tag '9.0.beta9' into public/28094

comment:19 follow-up: Changed 3 years ago by 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.

comment:20 in reply to: ↑ 19 Changed 3 years ago by klee

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 to-do list.

comment:21 Changed 3 years ago by git

  • Commit changed from 492a6677006eedd3a7205add2d363f0424edfb1c to 6760fd41d1676cbef776396b9ea28487e8524871

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

6760fd4Lots of clean-ups

comment:22 Changed 3 years ago by klee

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 klee

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 Leonard-Pellikaan-Singh-Swanson 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 git

  • Commit changed from 6760fd41d1676cbef776396b9ea28487e8524871 to 77dbf93d3116cf33e090d79607803d96c349e68b

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

77dbf93Recover normalization algorithm for global function fields

comment:25 Changed 3 years ago by klee

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 gh-BrentBaccala

  • Status changed from needs_review to positive_review

Approved. We can study the performance regression on another ticket.

comment:27 Changed 3 years ago by chapoton

no author name and no reviewer name !

comment:28 Changed 3 years ago by klee

  • Authors set to Brent Baccala
  • Reviewers set to Travis Scrimshaw, Kwankyu Lee

comment:29 Changed 3 years ago by vbraun

  • Branch changed from public/28094 to 77dbf93d3116cf33e090d79607803d96c349e68b
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.