Global function fields: orders and ideals

kwankyu commented 6 years ago

This is part of the meta-ticket #22982.

The goal of the present ticket is to add code for computing finite and infinite maximal orders and ideals thereof.

The central engine for computing maximal orders is the Leonard-Pellikaan-Singh-Swanson algorithm implemented in Singular. Most algorithms for computing with ideals are from Cohen's book A Course in Computational Algebraic Number Theory.

Component: algebra

Author: Kwankyu Lee

Branch/Commit: 48100b4

Reviewer: Travis Scrimshaw

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

kwankyu commented 6 years ago

Branch: u/klee/25435

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

Commit: 14d325a

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

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

14d325a Add orders and ideals

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

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

1649c10 Remove is_Ideal

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

Changed commit from 14d325a to 1649c10

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

Changed commit from 1649c10 to 36aae07

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

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

36aae07 Trim some comments

tscrim commented 6 years ago

comment:6

There are some doctest failures according to the patchbot. Some of them come the file name change, which technically you should deprecate the old file name (see #19879 for an example how to do this) if you think people could be importing directly from the file.

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

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

77a64da Fix a doctest failure due to a changed name

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

Changed commit from 36aae07 to 77a64da

kwankyu commented 6 years ago

comment:8

Replying to @tscrim:

There are some doctest failures according to the patchbot. Some of them come the file name change, which technically you should deprecate the old file name (see #19879 for an example how to do this) if you think people could be importing directly from the file.

I regard it as an internal change. So there is no need to deprecate.

kwankyu commented 6 years ago

comment:9

The startup modules plugin complains that

New:
    _md5
    _sha
    _sha256
    _sha512
    sage.rings.function_field.element
    sage.rings.function_field.ideal
    sage.rings.function_field.order
Removed:
    _hashlib
    _ssl
    sage.rings.function_field.function_field_element
    ssl

I don't really understand what is happening and how to deal with it. I suspect that this is somehow related with __hash__ method in the ideal or order modules...

Travis, would you give me some tips?

tscrim commented 6 years ago

comment:10

So the last three extra imports are from this change to function_field.py:

+from .order import (
+    FunctionFieldOrder_basis,
+    FunctionFieldOrderInfinite_basis,
+    FunctionFieldMaximalOrder_rational,
+    FunctionFieldMaximalOrder_global,
+    FunctionFieldMaximalOrderInfinite_rational,
+    FunctionFieldMaximalOrderInfinite_global)

However, you seem to basically be doing these imports locally anyways. I would run pyflakes on the file to see what is being duplicated in terms of imports, and you should decide if they need to be at the module level.

I probably wouldn't worry about the others as they seem to be unrelated.

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

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

`f362751`	`Merge branch 'develop' into function_fields_1`
`21d4b5b`	`Remove imports from .order at module level`
`895c379`	`Remove some more imports from module level`
`2811ce3`	`Remove CAT from module level in function_field`

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

Changed commit from 77a64da to 2811ce3

kwankyu commented 6 years ago

comment:12

Replying to @tscrim:

So the last three extra imports are from this change to function_field.py:
+from .order import (
+    FunctionFieldOrder_basis,
+    FunctionFieldOrderInfinite_basis,
+    FunctionFieldMaximalOrder_rational,
+    FunctionFieldMaximalOrder_global,
+    FunctionFieldMaximalOrderInfinite_rational,
+    FunctionFieldMaximalOrderInfinite_global)
However, you seem to basically be doing these imports locally anyways. I would run pyflakes on the file to see what is being duplicated in terms of imports, and you should decide if they need to be at the module level.

I probably wouldn't worry about the others as they seem to be unrelated.

Ok. Let's see what would happen with new commits, though still I don't understand where

   _md5
    _sha
    _sha256
    _sha512

come from...

tscrim commented 6 years ago

comment:13

Replying to @kwankyu:

Ok. Let's see what would happen with new commits, though still I don't understand where
   _md5
    _sha
    _sha256
    _sha512
come from...

I don't know either. I suspect it is an artifact or bug in the plugin.

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

Changed commit from 2811ce3 to cf4b92b

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

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

cf4b92b Restore erroneously deleted valuation method

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

Changed commit from cf4b92b to e34194f

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

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

e34194f Restore ideal_with_gens_over_base method for rational function field

kwankyu commented 6 years ago

Description changed:

--- 
+++ 
@@ -1,3 +1,5 @@
 This is part of the meta-ticket #22982. 

-The goal of the present ticket is to add code for computing finite and infinite maximal orders and ideals thereof. The central engine for computing maximal orders is the Leonard-Pellikaan-Singh-Swanson algorithm implemented in Singular. Most algorithms for computing with ideals are from Cohen's book  A Course in Computational Algebraic Number Theory.
+The goal of the present ticket is to add code for computing finite and infinite maximal orders and ideals thereof. 
+
+The central engine for computing maximal orders is the Leonard-Pellikaan-Singh-Swanson algorithm implemented in Singular. Most algorithms for computing with ideals are from Cohen's book  A Course in Computational Algebraic Number Theory.

dimpase commented 6 years ago

comment:18

Why do you copy Singular's library code here? The latter is available in SAGE_LOCAL/share/singular/LIB/

E.g. normal.lib with normalP is there.

kwankyu commented 6 years ago

comment:19

Replying to @dimpase:

Why do you copy Singular's library code here? The latter is available in SAGE_LOCAL/share/singular/LIB/

E.g. normal.lib with normalP is there.

The code of this patch was written more than two years ago. It might be the case that the normal.lib was then an experimental package. But I don't remember well.

Another reason that may still be relevant now is that the normalP in the singular library does more computations than necessary for my case. For example, it also computes delta invariants of the given ideal. So I decided to make a stripped-down light version of normalP just for the code in this ticket.

dimpase commented 6 years ago

comment:20

If it's a different version than the one in Singular, this should be made clear in the file header. The functions and .lib files also should be named differently, to prevent name clashes with the ones from the Singular lib.

dimpase commented 6 years ago

comment:21

Anyway, unless Singular's own version is significantly slower, you should rather use it.

kwankyu commented 6 years ago

comment:22

Replying to @dimpase:

Anyway, unless Singular's own version is significantly slower, you should rather use it.

I am trying this approach. During computation, the Singular's version spits out many comments, each line starting with //, causing doctest failures. Do you know how to deal with this?

Failed example:
    O = F.maximal_order()
Expected nothing
Got:
    <BLANKLINE>
    // ** WARNING: result is correct if ideal is prime (not checked) **
    // disable option "isPrim" to decompose ideal into prime components
    <BLANKLINE>
    <BLANKLINE>
    // 'normalP' computed a list, say nor, of two lists:
    // To see the result, type
         nor;
    <BLANKLINE>
    // * nor[1] is a list of 1 ideal(s), where each ideal nor[1][i] consists
    // of elements g1..gk of the basering R such that gj/gk generate the integral
    // closure of R/P_i (where P_i is a min. associated prime of the input ideal)
    // as R-module in the quotient field of R/P_i;
    <BLANKLINE>
    // * nor[2] shows the delta-invariant of each component and of the input ideal
    // (-1 means infinite, and 0 that R/P_i is normal).

kwankyu commented 6 years ago

comment:23

A small timing for you.

With my version:

sage:  K.<x> = FunctionField(GF(2));
sage: R.<t> = PolynomialRing(K);
sage: F.<y> = K.extension(t^4 + x^12*t^2 + x^18*t + x^21 + x^18)
sage: time F.maximal_order()
CPU times: user 178 ms, sys: 27.3 ms, total: 205 ms
Wall time: 201 ms

With Singular's version:

sage:  K.<x> = FunctionField(GF(2));
sage: R.<t> = PolynomialRing(K);
sage: F.<y> = K.extension(t^4 + x^12*t^2 + x^18*t + x^21 + x^18)
sage: time F.maximal_order()
//...
...
//...
CPU times: user 222 ms, sys: 31.3 ms, total: 254 ms
Wall time: 249 ms

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

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

74b2e50 Rename normalP in core.lib to core_normalize

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

Changed commit from e34194f to 74b2e50

kwankyu commented 6 years ago

comment:25

As using Singular's version has some technical problems noted above, I switched to the alternative path to renaming the procedure in core.lib

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`aa79205`	`Add orders and ideals`
`b42ad6b`	`Rename files`

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

Changed commit from 74b2e50 to b42ad6b

kwankyu commented 6 years ago

comment:29

I force-pushed two commits. The first commit contains all changes, and the second commit contains only filename changes.

Hopefully, a reviewer could see the changes against the devel branch more easily from the first commit.

tscrim commented 6 years ago

comment:30

Can you do a rebase? If so, I will do the review for this in the next few days (now that I have freed up a bit of time).

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

Changed commit from b42ad6b to 5a67ee5

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

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

`3cc6ecf`	`Add orders and ideals`
`5a67ee5`	`Rename files`

kwankyu commented 6 years ago

comment:32

Replying to @tscrim:

I will do the review for this in the next few days (now that I have freed up a bit of time).

Thank you, Travis. I thought of splitting this big patch into pieces, but it seemed difficult. If you find reviewing the patch annoying because of its size, let me know. Then I will try once again.

tscrim commented 6 years ago

comment:33

I have been able to make it through the code. I cannot vouch so much for the mathematical correctness, but it does work as documented. Here are my comments about the code:

For order_infinite_with_basis, did you want *basis instead of basis as an input (in which case, you will have to have check be part of a **kwds)? Or do you expect people to pass a list with a single list of basis elements inside?
Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis? It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).
I am pretty sure there is a bug in the caching of vector_space as the key is always return None, so the base parameter is ignored. Actually, you do not need to have a key here because you error out when base is not None. Is this for compatibility with something else? Does base**1 do something? I feel like it should just be base. I guess some of this is a hold-over from the old code, so it is not a big issue.
In all of the __init__ tests, it would be good to have TestSuite(I).run() (especially over a type(I) call IMO). I would also move the INPUT: block outside of the __init__ and into the class-level doc so that it is visible from the html doc.
Returns -> Return (in base_ring()).
Note that _rmul_ (like _lmul_) can have general input as they are designed to be hooks for actions. (Not that this is necessarily wrong here, but I just want to make sure this has all of the behaviors you are expecting.)
I don't see the point of having _gens_over_base. It is only called from gens_over_base and could be moved into there.
Instead of handling your own custom cache with _two_gens, I would just @cached_method gens_two.
You should make sure the result of basis_matrix is an immutable matrix by adding m.set_immutable().
I don't like avoiding self: it makes you have strange sentences like Return the ideal below the ideal., which I might even argue is close to ill-defined (which ideal is the ideal?).
Same comment about custom cache for _is_prime.
A better way from category or IntegralDomains() to get the category might be IntegralDomains().or_subcategory(category) (works fine when category=None). You can also then tack on category = category.Infinite() and then remove the is_finite method.
You don't need to cache ideal_monoid, at least the IdealMonoid class is better as a UniqueRepresentation.
Error messages should start with a lowercase letter (as per our convention).

Some little doc formatting things:

       - ``gens`` -- list of elements that are a basis for the
-             ideal over the maximal order of the base field
+           ideal over the maximal order of the base field

      - ``gens`` -- list of generators or an ideal in a ring which coerces
-          to this order.
+          to this order

Some micro-optimizations:

-        basis = [V(sigma_a_pow[j]*beta_pow[i]) for i in range(s) for j in range(r)]
+        basis = [V(sap * bp) for bp in beta_pow for sap in sigma_a_pow]
       W = V.span_of_basis(basis)

       def to_K(f):
           coeffs = (f % q).list()
-            return sum([sigma(coeffs[i]) * beta_pow[i] for i in range(len(coeffs))], K.zero())
+            return sum((sigma(c) * beta_pow[i] for i, c in enumerate(coeffs)), K.zero())

       if r == 1: # take care of the prime field case
           def fr_K(g):
               co = W.coordinates(V(g),check=False)
               return R([k(co[j]) for j in range(s)])
       else:
-            t = r * s
           def fr_K(g):
               co = W.coordinates(V(g),check=False)
-                return R([k(co[i:i+r]) for i in range(0,t,r)])
+                return R([k(co[i:i+r]) for i in range(0,r*s,r)])

(well, the last changes are for readability, less variables to keep track of).

Micro-optimization: in mul_vecs, you might want to move self._mtable[i] part out of the for j in range(n): loop to avoid the extra lookups.

I think it is bad form to use raises of errors to dictate program flow. I think a better way in _ideal_from_vectors_and_denominator (which should be faster too) is to have

            M = []
            g = d
            for v in vecs:
                for c in l:
                    g = g.gcd(c)
                    if g.is_one():
                        break
                else:
                    M += l
                    continue
                break
            else:
                d = d // g
                mat = matrix(R, len(vecs), [c // g for c in M])

where the else block is run iff the loop did not run to completion. You could also dispatch this to an internal function that would return mat or None upon failure.

Is there a clear benefit to having mtable a list of vectors, as opposed to a list of lists or a Matrix object?

Isn't this block of the div in Buchman-Lenstra algorithm just the same as mul_vec?

                    c = 0
                    for i in range(n):
                        for j in range(n):
                            c += a[i] * b[j] * mtable[i][j]

Perhaps there would be a benefit from cythonizing mul_vec considering how frequently it is used.

kwankyu commented 6 years ago

comment:34

Replying to @tscrim:

For order_infinite_with_basis, did you want *basis instead of basis as an input (in which case, you will have to have check be part of a **kwds)? Or do you expect people to pass a list with a single list of basis elements inside?

The code seems to be intended to support these three cases:

L.order_infinite_with_basis([1/x,1/x*y, 1/x^2*y^2])

L.order_infinite_with_basis([1/x])

L.order_infinite_with_basis(1/x)

But this is not described in the docstring. Also this is not consistent with order_with_basis. Hence I will remove the responsible code from order_infinite_with_basis. Happily, there is no doctest failure because of this.

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

Changed commit from 5a67ee5 to 9a1bbb2

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

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

9a1bbb2 Remove unnecessary code from order_infinite_with_basis

kwankyu commented 6 years ago

comment:36

Replying to @tscrim:

Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis?

No.

It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).

I followed your suggestion partially. Now FunctionFieldMaximalOrder class inherits UniqueRepresentation. So for maximal_order() and maximal_order_infinite() are not cached.

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

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

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

d4c8e8b Inherit UniqueRepresentation to MaximalOrder class

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

Changed commit from 9a1bbb2 to d4c8e8b

tscrim commented 6 years ago

comment:38

Replying to @kwankyu:

Replying to @tscrim:

Can you construct FunctionFieldMaximalOrder(Infinite)_global with having a different basis?

No.

It feels like these classes should just take one input, FunctionField(_global), which then has a hook to construct the corresponding basis (or maybe do this computation on-demand in the class itself). This would allow FunctionFieldOrder to inherit from UniqueRepresentation and maximal_order_infinite() to not be cached. I don't see how FunctionFieldOrder and subclasses are compared/hashed by default (the default Parent.__hash__ using the string representation is a horrible hash too).

I followed your suggestion partially. Now FunctionFieldMaximalOrder class inherits UniqueRepresentation. So for maximal_order() and maximal_order_infinite() are not cached.

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

They are subclasses of Parent, correct? Things work faster/better in regard to, say, coercion and equality with UniqueRepresentation. It is also faster to compare for equality and hash (just use the id in both cases). Speaking of which, because of the MRO, it is better to have UniqueRepresentation as the first class.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

FYI - if you do really only want cached behavior, there is a CachedRepresentation class you could use. However, I don't see a reason why not to upgrade to the UniqueRepresentation here.

kwankyu commented 6 years ago

comment:39

Replying to @tscrim:

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

There was a typo here. I meant:

Order_basis class does not have unique representation behavior. It could have cached representation behavior. But I don't see a reason to force this.

Equation orders can have unique representation behavior. But I leave them just to be cached. I don't see a compelling reason to avoid using @cached_method for these. Do you have?

They are subclasses of Parent, correct? Things work faster/better in regard to, say, coercion and equality with UniqueRepresentation. It is also faster to compare for equality and hash (just use the id in both cases). Speaking of which, because of the MRO, it is better to have UniqueRepresentation as the first class.

Ok. I will make this fix.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

I agree. But EquationOrder(Infinite) class is something that I do not expect to be subclassed. Anyway now it occurs to me that I can just get rid of this class, and use the superclassOrder_basis.

tscrim commented 6 years ago

comment:40

Replying to @kwankyu:

Replying to @tscrim:

Orders created with a basis do have unique representation behavior. They could have cached representation behavior. But I don't see a reason to force this.

Thank you.

There was a typo here. I meant:

Order_basis class does not have unique representation behavior. It could have cached representation behavior. But I don't see a reason to force this.

If you expect to create elements of this class and implement coercions between them, then it makes the mechanisms in the coercion framework work a lot better and faster. In addition to the reasons given below. However, this is only a suggestion, and I don't have a strong preference (or a stake in the outcome). If you prefer it this way, then that is fine with me.

It also means the cache is tied with the object itself rather than a creation method. Say, someone else creates a (maybe completely separate) class that wants to use the basis classes. They would also have to implement a cache, which would either create two copies of the same object or have to make the two caches interact; both of which I think are bad.

I agree. But EquationOrder(Infinite) class is something that I do not expect to be subclassed. Anyway now it occurs to me that I can just get rid of this class, and use the superclassOrder_basis.

Okay, but someone might have a completely different class that would call it. For example, someone implements a 3rd party library for function fields that we tie into Sage, but you still would want to have a method, say, equation_order from that new implementation. This would give the situation I am describing above. Granted, this is not so likely, but it is better to future-proof when there is little cost to complexity IMO.

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

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

5ee44a2 Inherit CachedRepresentation to Order_basis class

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

Changed commit from d4c8e8b to 5ee44a2

sagemath / sage

Global function fields: orders and ideals #25435