create a class for basic function_field arithmetic for Sage #9054

williamstein · 2010-05-26T11:21:12Z

One of the first things we learned at Sage Days 21: Function Fields, is that it is not even possible to really define or even do arithmetic in function fields at all in Sage! It's amazing that this most basic arithmetic still isn't supported, but it isn't (maybe it used to be via generic machinery, but got broken...?). The point of this ticket is to create classes for standard function field structures, along with support for arithmetic. This should be organized in a way similar to number fields.

For this code, the main point is to establish an API that works solidly. It will be insanely slow. A subsequent patch will make things fast.

See also: #9069, #9051, #9094, #9095.

Note that the dependancy on #9138 is only because of a really minor change in the doctests. This ticket already has a positive review so I suspect this will get merged first. If that ticket eventually gets rejected it will be trivial to rebase the patch withouth that ticket.

Apply attachment: 9054_function_fields.patch to the Sage library.

Dependencies: sage-5.0.beta1

CC: @burcin @sagetrac-khwilson @koffie @mstreng @novoselt @pjbruin @mminzlaff @saraedum

Component: algebra

Author: William Stein, Robert Bradshaw, Maarten Derickx, Moritz Minzlaff, Julian Rueth

Reviewer: Maarten Derickx, Julian Rueth

Merged: sage-5.0.beta2

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

burcin · 2010-05-26T22:22:52Z

comment:1

Attachment: trac_9054-part1.patch.gz

williamstein · 2010-05-27T01:27:22Z

Attachment: trac_9054-part2.patch.gz

williamstein · 2010-05-27T03:01:01Z

Attachment: trac_9054-part3.patch.gz

sagetrac-salmanhb · 2010-05-27T05:38:49Z

comment:2

There seems to be an issue with returning the base ring of a RationalFunctionField. Neither base() nor base_ring() return the correct ring:

sage: K.<t> = FunctionField(QQ); K
Rational function field in t over Rational Field
sage: R1 = K.base(); R1
Rational function field in t over Rational Field
sage: R2 = K.base_ring(); R2
Rational function field in t over Rational Field
sage: R3.<s> = QQ[]; K3 = Frac(R3); K3
Fraction Field of Univariate Polynomial Ring in s over Rational Field
sage: R3
Univariate Polynomial Ring in s over Rational Field
sage: K3.base() == R3
True

robertwb · 2010-05-27T10:10:47Z

Attachment: trac_9054-part4.patch.gz

Attachment: trac_9054-part5.patch.gz

robertwb · 2010-05-27T10:13:10Z

comment:3

Looks like you forgot to add the file function_field_order, so I wasn't able to doctest on top of your latest patch (let alone debug it). See also #9051 for added speed in the positive characteristic case.

williamstein · 2010-05-27T22:53:04Z

Attachment: trac_9054-part6.patch.gz

Attachment: trac_9054-part7.patch.gz

polynomial factorization!

jbalakrishnan · 2010-05-28T01:21:20Z

comment:4

FunctionField constructor clips names

sage: F = FunctionField(GF(7), 'bit')
sage: F.gen()
b

williamstein · 2010-05-28T06:29:45Z

ideals and orders!

williamstein · 2010-05-28T08:22:52Z

Attachment: trac_9054-part8.patch.gz

inverses of fractional ideals

williamstein · 2010-05-28T10:54:25Z

comment:5

Attachment: trac_9054-part9.patch.gz

Replying to @sagetrac-salmanhb:

There seems to be an issue with returning the base ring of a RationalFunctionField. Neither base() nor base_ring() return the correct ring:

sage: K.<t> = FunctionField(QQ); K
Rational function field in t over Rational Field
sage: R1 = K.base(); R1
Rational function field in t over Rational Field
sage: R2 = K.base_ring(); R2
Rational function field in t over Rational Field
sage: R3.<s> = QQ[]; K3 = Frac(R3); K3
Fraction Field of Univariate Polynomial Ring in s over Rational Field
sage: R3
Univariate Polynomial Ring in s over Rational Field
sage: K3.base() == R3
True

The above is correct. To get what you want, use the constant_field() method.

sage: K.<t> = FunctionField(QQ);
sage: K.constant_field()
Rational Field

williamstein · 2010-05-28T10:55:53Z

morphisms of function fields

williamstein · 2010-05-29T03:13:02Z

Attachment: trac_9054-part10.patch.gz

robertwb · 2010-05-30T09:54:48Z

Attachment: trac_9054-part11.patch.gz

Attachment: trac_9054-part12.patch.gz

Various methods needed for #9095 (doctesets depend on #9094)

sagetrac-khwilson · 2010-06-04T22:17:13Z

comment:6

Should be some automatic way to do the following:

K.<T> = FunctionField(GF(17))
P = T-5
f = P^5
R = K._ring
R(f.element()).valuation(R(p.element()))

williamstein · 2010-07-06T09:25:32Z

Attachment: trac_9054-part1-12.patch.gz

flattened patch that incorporates all of patches 1-12 above into a single patch.

williamstein · 2010-07-06T09:37:38Z

comment:8

Here is a link to the result of doctesting sage-4.4.4 + patches 1-12:

http://sage.math.washington.edu/home/wstein/patches/9054-part1-12.doctest.txt

The failed tests:

The following tests failed:

        sage -t  devel/sage-main/sage/matrix/matrix2.pyx # 1 doctests failed
        sage -t  devel/sage-main/sage/plot/matrix_plot.py # 0 doctests failed
        sage -t  devel/sage-main/sage/modular/abvar/morphism.py # 1 doctests failed
        sage -t  devel/sage-main/sage/modular/abvar/finite_subgroup.py # 1 doctests failed
        sage -t  devel/sage-main/sage/tests/startup.py # 1 doctests failed
        sage -t  devel/sage-main/sage/modular/modform/hecke_operator_on_qexp.py # 1 doctests failed
        sage -t  devel/sage-main/sage/categories/function_fields.py # 5 doctests failed
        sage -t  devel/sage-main/sage/rings/function_field/function_field_element.pyx # 14 doctests failed

williamstein · 2010-07-07T13:01:55Z

comment:13

NOTE: #9094 implements sqrt for polynomials, which is relevant to trac_9054-doctest.patch

koffie · 2010-07-07T21:17:51Z

comment:14

I guess the doctest patch isn't really usefull addition to sage (although making it was a usefull learning experience for Peter Bruin and me since it was our first patch). The patch fixes some bugs which are also fixed in other patches in trac. Some are indeed fixed by #9094 (although i think this can be done faster and more elegant) and another one related calculating the valuation in fraction fields is fixed by 9051-FpT_4.patch in #9051.

Since I'm quite new to developing and using trac and hg etc. I would like to know what is the best thing to do now. And especially how to deal with the relating patches wich also contain fixes for stuff happening here.

koffie · 2010-07-17T11:02:34Z

comment:16

Added an attachment that fixes all but three doctest failures. The remaining failures are:


sage -t  "devel/sage-mderickx/sage/modular/abvar/morphism.py" # 1 failure

sage -t  "devel/sage-mderickx/sage/modular/abvar/finite_subgroup.py" # 1 failure

sage -t  "devel/sage-main/sage/modular/modform/hecke_operator_on_qexp.py" # 1 failure

}}}They are all related since their error messages all end in:{{{      File "/Applications/sage/local/lib/python/site-packages/sage/modules/free_module.py", line 4700, in _echelonized_basis        d = self._denominator(basis)      File "/Applications/sage/local/lib/python/site-packages/sage/modules/free_module.py", line 4810, in _denominator        d = d.lcm(x.denominator())    !AttributeError: 'int' object has no attribute 'lcm'}}}It would be nice if someone who has a better understanding of sage to fix this final bug, since then we would have no doctests failing anymore for this patch.

koffie · 2010-07-17T11:05:00Z

comment:17

Oeps, wrong fromatting. Now a bit more readable:

sage -t  "devel/sage-mderickx/sage/modular/abvar/morphism.py" # 1 failure

sage -t  "devel/sage-mderickx/sage/modular/abvar/finite_subgroup.py" # 1 failure

sage -t  "devel/sage-main/sage/modular/modform/hecke_operator_on_qexp.py" # 1 failure

They are all related since their error messages all end in:


      File "/Applications/sage/local/lib/python/site-packages/sage/modules/free_module.py", line 4700, in _echelonized_basis
        d = self._denominator(basis)
      File "/Applications/sage/local/lib/python/site-packages/sage/modules/free_module.py", line 4810, in _denominator
        d = d.lcm(x.denominator())
    AttributeError: 'int' object has no attribute 'lcm'

saraedum · 2011-11-15T13:36:28Z

comment:81

I'm replacing the commit messages now. I don't have privileges to replace attachements so I have to upload a new set of patches instead.

saraedum · 2011-11-15T13:36:59Z

provide basic function field arithmetic (combined patch by various authors)

saraedum · 2011-11-15T13:37:50Z

Attachment: trac_9054-all-parts.2.patch.gz

Attachment: trac_9054-julian-combined.2.patch.gz

cleanup function field code and documentation

saraedum · 2011-11-15T13:38:18Z

Attachment: trac_9054-review2.2.patch.gz

fix doctests for function fields

saraedum · 2011-11-15T13:38:47Z

Attachment: trac_9054_review_fixup.2.patch.gz

fixes for function fields related to the review comments by mderickx

saraedum · 2011-11-15T13:39:14Z

Attachment: trac_9054-can_this_really_be_the_last.2.patch.gz

last fixes for function fields

saraedum · 2011-11-15T13:39:44Z

fix pickling for extensions of function fields

saraedum · 2011-11-15T13:42:17Z

comment:82

Attachment: trac_9054_pickling.2.patch.gz

Apply trac_9054-all-parts.2.patch, trac_9054-julian-combined.2.patch, trac_9054-review2.2.patch, trac_9054_review_fixup.2.patch, trac_9054-can_this_really_be_the_last.2.patch, trac_9054_pickling.2.patch

jdemeyer · 2012-01-22T21:23:44Z

comment:84

Patches attachment: trac_9054-all-parts.2.patch and attachment: trac_9054-review2.2.patch apply with fuzz 2 against sage-5.0.beta1. Please rebase such that they apply cleanly.

jdemeyer · 2012-01-30T10:51:06Z

Changed dependencies from #9094, #11751, #9138 to sage-5.0.beta1

koffie · 2012-01-30T12:55:11Z

comment:86

Thanks for rebasing, I added it to my todo list, but didn't get to it yet.

jdemeyer · 2012-01-31T09:08:07Z

Attachment: 9054_function_fields.patch.gz

jdemeyer · 2012-02-02T12:52:09Z

Merged: sage-5.0.beta2

williamstein added this to the sage-4.6 milestone May 26, 2010

williamstein added c: algebra labels May 26, 2010

williamstein assigned aghitza May 26, 2010

williamstein assigned williamstein and unassigned aghitza Jul 6, 2010

This comment has been minimized.

Sign in to view

jdemeyer added the s: needs work label Nov 15, 2011

This comment has been minimized.

Sign in to view

saraedum added s: positive review and removed s: needs work labels Nov 15, 2011

jdemeyer added this to the sage-5.0 milestone Dec 9, 2011

jdemeyer removed the pending label Dec 9, 2011

jdemeyer added s: needs work and removed s: positive review labels Jan 22, 2012

This comment has been minimized.

Sign in to view

jdemeyer added s: positive review and removed s: needs work labels Jan 30, 2012

jdemeyer removed the s: positive review label Feb 2, 2012

jdemeyer closed this as completed Feb 2, 2012

saraedum mentioned this issue Nov 30, 2011

proof parameter not passed on when factoring polynomials over function fields #12100

Closed

sagetrac-sydahmad mannequin mentioned this issue Oct 19, 2013

Genus computation (using singular) and _singular_ object for function field #12170

Closed

This was referenced Jun 28, 2014

Enhancing function field capabilities: collapse a tower of function field extensions to a simple extension and more #12194

Closed

is_squarefree() incorrect over imperfect fields #12404

Closed

create a class for basic function_field arithmetic for Sage #9054

create a class for basic function_field arithmetic for Sage #9054

Comments

williamstein commented May 26, 2010

burcin commented May 26, 2010

williamstein commented May 27, 2010

williamstein commented May 27, 2010

sagetrac-salmanhb mannequin commented May 27, 2010

robertwb commented May 27, 2010

robertwb commented May 27, 2010

williamstein commented May 27, 2010

jbalakrishnan commented May 28, 2010

williamstein commented May 28, 2010

williamstein commented May 28, 2010

williamstein commented May 28, 2010

williamstein commented May 28, 2010

williamstein commented May 29, 2010

robertwb commented May 30, 2010

sagetrac-khwilson mannequin commented Jun 4, 2010

williamstein commented Jul 6, 2010

williamstein commented Jul 6, 2010

This comment has been minimized.

williamstein commented Jul 7, 2010

koffie commented Jul 7, 2010

This comment has been minimized.

koffie commented Jul 17, 2010

koffie commented Jul 17, 2010

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

saraedum commented Nov 15, 2011

This comment has been minimized.

saraedum commented Nov 15, 2011

jdemeyer commented Jan 22, 2012

jdemeyer commented Jan 30, 2012

This comment has been minimized.

koffie commented Jan 30, 2012

jdemeyer commented Jan 31, 2012

jdemeyer commented Feb 2, 2012