Opened 4 years ago

Closed 3 years ago

#15389 closed enhancement (fixed)

An algorithm for enumerating elements of bounded height in number fields

Reported by: dkrumm Owned by: dkrumm
Priority: minor Milestone: sage-6.3
Component: number theory Keywords: sage-days55
Cc: bhutz, vdelecroix, jdoyle Merged in:
Authors: David Krumm, John Doyle Reviewers: Ben Hutz
Report Upstream: N/A Work issues:
Branch: 8fed00f (Commits) Commit: 8fed00f0386a0c29d0b85de1b4b6c30bb415af3c
Dependencies: Stopgaps:

Description

An implementation of the main algorithm in John R. Doyle and David Krumm, Computing algebraic numbers of bounded height, http://arxiv.org/abs/1111.4963 (2013). This will add functionality to determine all elements of small height in any given number field.

Change History (39)

comment:1 Changed 4 years ago by dkrumm

  • Branch set to u/jdoyle/bdd_height
  • Commit set to 6395710f6953fc50173226e0fa2eef565323d578
  • Owner changed from dkrumm, jdoyle to dkrumm

Last 10 new commits:

6395710New changes to bdd_height.py
2cd23d8Added the file bdd_height.py; edited number_field.py to point to new file.
# Pleas enter the commit message for your changes. Lines starting
# with #' will be ignored, and an empty message aborts the commit.
# On brnch bdd_height_test
# Changs to be committed:
# (us "git reset HEAD <file>..." to unstage)
#
# new fle: bdd_height.py
# modifed: number_field.py

comment:2 Changed 4 years ago by git

  • Commit changed from 6395710f6953fc50173226e0fa2eef565323d578 to b81322cb555becf5b44cf6a8419dbaf737f8f4fd

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

b81322cEdited the examples for the elements_of_bdd_height function
6b4719bWe have included the new function elements_of_bdd_height in number_field.py
c155659Edited the elements_of_bdd_height function.
74531e2Further changes to bdd_height.py

comment:3 Changed 4 years ago by vdelecroix

Hi,

Good work! There are some things that need to be changed and others that can be improved (not necessarily in this ticket but it might be a good idea to think about it). First of all about syntax and tests:

1) your tests do not work: if you do bdd_height(K,100) in a console the function bdd_height simply does not exists. You should put the line

from sage.rings.number_field.bdd_height import bdd_height

at the begining of the tests.

2) There are many syntax errors in the documentation:

  • the lines must not be longer than 80 characters.
  • the documentation of each function should start with a short sentence of one line. Then you can add some more documentation after a break line.
  • the syntax for the block of examples is not good
  • ...

For all that, you may have look at the Sage developer guide or even better at other files in the source code (like number_field.py)

3) for your functions there is no need of having an underscore. It is required to have "private" method into classes but it is not needed for functions.

4) the name of functions that are actually used by users should not be abreviated (unless it is as common as det for the determinant). I would prefer having bounded instead of bdd.

About algorithmic

5) Why did you choose 100 as default precision for your floating point numbers? It makes no sense. Either you use the default Sage value or you actually guarantee the result. Moreover you do computations using floating point numbers and then suddenly, at line 500, you switch to rational numbers! It seems to me that you use rational numbers for finding your integer points in the polytope. If you intend to use floating point approximation it makes more sense to use RDF (as there is an highly optimized search for integer points in polyhdera). Much more important, using floating point approximation is always dangerous as you get errors each time you do an operation. It is not a trouble if you have control on your quantities (for example you can safely invert a matrix in RDF as soon as A and A-1 are reasonably small). So, if you want your result to be the good result (meaning that you have all the points and no more) then you should either take more care with floating point numbers or use proven arithmetic (like arithmetic interval, which is implemented in Sage or ball arithmetic etc). Using interval arithmetic is slow so it is not a good advice to use it here.

6) There are a lot of simplification that you can do. For example the lines 291-298

    # Create polyhedron from transformed vertices and find integer points inside
    int_points = Polyhedron(transformed_vertices, base_ring=QQ).integral_points()

    # Return these integer vectors as tuples
    int_point_tuples = []
    for vec in int_points:
        int_point_tuples.append(tuple(vec))
    return int_point_tuples

can be replaced by two (much faster) line

    # Return integer points in the polyhedron
    return map(tuple, Polyhedron(transformed_vertices, base_ring=QQ).integral_points())

And by the way, why do you need to convert the result into tuples?

7) It would make sense to have an iterator rather than an actual list (i.e. a method K.element_of_bounded_height_iterator(500) that returns an iterator and not a list). Most of the time, I guess that people want to use this method to test conjecture or such. So what they want is for each element in that list check some conjecture with that input. Have a look at Tutorial: Programming in Python and Sage.

comment:4 follow-up: Changed 4 years ago by vdelecroix

  • Cc vdelecroix added

comment:5 in reply to: ↑ 4 Changed 4 years ago by dkrumm

Replying to vdelecroix:

Thanks for all your comments! We're working on this. I was wondering if you saw any places where using Cython would speed things up?

Regarding point 5: Unfortunately, RDF is often not precise enough for our computations. The polytope we deal with will sometimes have vertices with very small coordinates, so that RDF thinks they are 0, and then things go wrong. Ideally, we would be able to create a polyhedron whose base ring is a real field with any given precision, but as far as I know this is not allowed by the Polyhedron constructor. This is why we first compute the vertices of our polytope with high precision as floating point numbers and then convert them to rational numbers for the polyhedron computation.

comment:6 Changed 4 years ago by git

  • Commit changed from b81322cb555becf5b44cf6a8419dbaf737f8f4fd to e6a89f45a9ec3fca9987e919b9cb849cfa69e79f

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

e6a89f4Made minor improvements based on suggestions from vdelecroix.

comment:7 Changed 4 years ago by jdoyle

  • Cc jdoyle added

comment:8 Changed 4 years ago by vbraun_spam

  • Milestone changed from sage-6.1 to sage-6.2

comment:9 Changed 4 years ago by git

  • Commit changed from e6a89f45a9ec3fca9987e919b9cb849cfa69e79f to bac2d779a1cba38ec787e1a9cbfe77e609ccd99a

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

bac2d77Included option to compute LLL-reduced basis for unit group.

comment:10 Changed 3 years ago by vbraun_spam

  • Milestone changed from sage-6.2 to sage-6.3

comment:11 Changed 3 years ago by jdoyle

  • Status changed from new to needs_review

comment:12 follow-up: Changed 3 years ago by bhutz

  • Reviewers set to Ben Hutz
  • Status changed from needs_review to needs_work

Mostly minors issues, but there are a few of them.

Some general comments first

  • there are many instances of lines with trailing white space that need to be removed.
  • please merge in most recent beta as the branch on trac is weird and seems to be deleting all of number_field.py, although that is not what the downloaded branch does.
  • put a REFERENCE block in one place, then reference in other places

  • is the GRH parameter really needed as all it does is set the number_field(True/False?) switch? I would rather see that controlled by the global switch and not the individual functions anyway. So, I'd remove the parameter and mention the switch in the documentation.
  • why is lll lower case and GRH upper case?

for the numberfield.py file:

  • doc test error in number_field.py. Seems the elements are out of order.
  • using keywords for the parameters would be better so they can be specified independently.
  • lll keyword is not used in the function
  • output - an iterator of number field elements*

for the bdd_height.py file:

  • It is standard to have some comments at the header to describe the purpose of the file/GNU licence/authors/etc.
  • itertools.product - is the only itertools you use, so only import that one
  • same with copy.copy
  • the warning block is producing docbuild errors.

bdd_norm_pr_gens_iq:

  • this is returning elements of K not ideals like the description says
  • output - a dictionary of principle ideals, keyed by norm

bdd_height_iq:

  • if bound is non-negative should always return 0, not empty list (current skips 0 if the bound is < 1).

bdd_norm_pr_ideal_gens:

  • output - a dictionary of ???
  • returns elements not ideals as doc specifies

integer_points_in_polytope:

  • check docs for [-interval_radius,interval_radius]r
  • # long time (40 s) -- is a very long doc test - does it need to be quite this long or would a short long test do the same thing
  • if you're allowing real numbers for the matrix shouldn't you have the base_ring for the polyhedron be RR?

bdd_height:

  • QQ to QQ, K to K. In general, things that need latex typesetting (i.e., math) should be put in single quotes
  • missed 0 for heights < 1
  • same for these long tests - 290s is a *very* long time, please evaluate whether such a long test is truly necessary.
  • does the precision test by changing to QQ ever actually fail. I'm not sure why this is a precision test since any real number to some finite number of decimals places can be converted to a rational.
  • 'principle ideals of bounded norm' are really generators of principle ideals

comment:13 in reply to: ↑ 12 Changed 3 years ago by dkrumm

Replying to bhutz:

  • if bound is non-negative should always return 0, not empty list (current skips 0 if the bound is < 1).
  • missed 0 for heights < 1

Maybe you're thinking of logarithmic height? For our height function, 0 has height 1.

  • if you're allowing real numbers for the matrix shouldn't you have the base_ring for the polyhedron be RR?

Unfortunately, RDF is often not precise enough for our computations. The polytope we deal with will sometimes have vertices with very small coordinates, so that RDF thinks they are 0, and then things go wrong. Ideally, we would be able to create a polyhedron whose base ring is a real field with any given precision, but as far as I know this is not allowed by the Polyhedron constructor. This is why we first compute the vertices of our polytope with high precision as floating point numbers and then convert them to rational numbers for the polyhedron computation. This is not ideal, but otherwise there would be no point in allowing the user to input a precision, since it's going to be cut down to 53 anyway.

  • does the precision test by changing to QQ ever actually fail. I'm not sure why this is a precision test since any real number to some finite number of decimals places can be converted to a rational.

It certainly does fail if the precision is not good enough. The issue is that a fundamental unit can have an embedding with very very small absolute value; when we take log of that, RR may interpret this as log(0). If I recall correctly this is ok with RR, but when you try to coerce into QQ it raises an error.

comment:14 Changed 3 years ago by bhutz

Yes, my mistake, I was thinking logarithmic height.

I see now for the precision. Please put a comment right before those tests something like # QQ(log(0)) occurs for too low precision

comment:15 Changed 3 years ago by jdoyle

  • Branch changed from u/jdoyle/bdd_height to u/jdoyle/ticket/15389
  • Created changed from 11/09/13 22:19:26 to 11/09/13 22:19:26
  • Modified changed from 07/19/14 17:35:58 to 07/19/14 17:35:58

comment:16 Changed 3 years ago by git

  • Commit changed from bac2d779a1cba38ec787e1a9cbfe77e609ccd99a to 3b3950196522602f9d53b0088db285b10a70af2c

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

3b39501Updated number_field.py.

comment:17 Changed 3 years ago by jdoyle

  • Status changed from needs_work to needs_review

comment:18 Changed 3 years ago by bhutz

  • Status changed from needs_review to needs_work

This is looking good, but there is one last thing on the imports.

You are importing from sage.geometry.polyhedron.constructor import *

but don't you just need the Polyhedron function from that module?

comment:19 Changed 3 years ago by git

  • Commit changed from 3b3950196522602f9d53b0088db285b10a70af2c to f48cf26707645c8adf6351fd2331511f00b013cb

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

f48cf26Changed import statement as per Ben's comment.

comment:20 Changed 3 years ago by bhutz

  • Status changed from needs_work to positive_review

All set.

comment:21 Changed 3 years ago by vbraun

  • Branch changed from u/jdoyle/ticket/15389 to f48cf26707645c8adf6351fd2331511f00b013cb
  • Resolution set to fixed
  • Status changed from positive_review to closed

comment:22 Changed 3 years ago by vbraun

  • Commit f48cf26707645c8adf6351fd2331511f00b013cb deleted
  • Resolution fixed deleted
  • Status changed from closed to new

I got the following on OSX 10.9 once (possibly random/depending on numerical noise):

sage -t --long src/sage/rings/number_field/bdd_height.py
**********************************************************************
File "src/sage/rings/number_field/bdd_height.py", line 418, in sage.rings.number_field.bdd_height.bdd_height
Failed example:
    len(list(bdd_height(K,100))) # long time (9 s)
Expected:
    5171
Got:
    5131
**********************************************************************

and related:

sage -t --long src/sage/rings/number_field/number_field.py
**********************************************************************
File "src/sage/rings/number_field/number_field.py", line 8289, in sage.rings.number_field.number_field.NumberField_absolute.elements_of_bounded_height
Failed example:
    len(list(L)) # long time (9 s)
Expected:
    5171
Got:
    5131
**********************************************************************

comment:23 Changed 3 years ago by vbraun

  • Branch changed from f48cf26707645c8adf6351fd2331511f00b013cb to u/jdoyle/ticket/15389
  • Commit set to f48cf26707645c8adf6351fd2331511f00b013cb

Last 10 new commits:

74531e2Further changes to bdd_height.py
c155659Edited the elements_of_bdd_height function.
6b4719bWe have included the new function elements_of_bdd_height in number_field.py
b81322cEdited the examples for the elements_of_bdd_height function
e6a89f4Made minor improvements based on suggestions from vdelecroix.
bac2d77Included option to compute LLL-reduced basis for unit group.
8379f47Merge branch 'master' into ticket/15389
087fefeMade changes based on comments from bhutz.
3b39501Updated number_field.py.
f48cf26Changed import statement as per Ben's comment.

comment:24 Changed 3 years ago by vbraun

Failure on the OSX 10.9 buildbot is reproducable...

comment:25 Changed 3 years ago by dkrumm

I had the same problem with my mac running OS 10.9.

comment:26 Changed 3 years ago by git

  • Commit changed from f48cf26707645c8adf6351fd2331511f00b013cb to cd36a73894be52bf69f9c5e9b5d7b7e998262e55

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

cd36a73Modified two examples and added pari import statement.

comment:27 Changed 3 years ago by jdoyle

I changed the example that was causing an issue. It seems that the issue may be related to the fact that there are elements in that particular number field of height exactly equal to 100, and perhaps the different machines handled the floating point arithmetic differently. I changed the height bound in the example to 60 because there don't seem to be any elements of height exactly 60.

comment:28 Changed 3 years ago by bhutz

Does increasing the precision on OSX cause that example to work?

It would be nice to know that it really is a precision issue (as mentioned in the warning) and not some other underlying issue.

comment:29 Changed 3 years ago by dkrumm

Yes, on mac osx I increased the precision to 200 bits and got the expected answer (5171). Probably a smaller precision would also work. The same answer is obtained with precision 300, 500, and 1000.

comment:30 Changed 3 years ago by dkrumm

All doctests are passing now on my machine running Mac OS 10.9.

comment:31 Changed 3 years ago by jdoyle

  • Status changed from new to needs_review

comment:32 Changed 3 years ago by bhutz

That's resolved as a precision issue then.

doc tests pass on my machine. The new examples are good, but the one with 1899 for bdd_height has some trailing whitespace that needs to be removed.

After that, I'll mark this positive again.

comment:33 Changed 3 years ago by git

  • Commit changed from cd36a73894be52bf69f9c5e9b5d7b7e998262e55 to cdad564de1a6cd71f2d42d9f6844dd9070368b88

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

cdad564Removed some trailing whitespace from bdd_height.py.

comment:34 Changed 3 years ago by bhutz

  • Status changed from needs_review to positive_review

comment:35 Changed 3 years ago by vbraun

  • Status changed from positive_review to needs_info

Long doctests should still take <= 5s. Is there anything that can't be tested by enumerating less than thousands of solutions? Every ticket needs to run the tests, don't slow it down without reason.

comment:36 Changed 3 years ago by git

  • Commit changed from cdad564de1a6cd71f2d42d9f6844dd9070368b88 to 8fed00f0386a0c29d0b85de1b4b6c30bb415af3c

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

8fed00fChanged some examples so they take less time to test.

comment:37 Changed 3 years ago by jdoyle

  • Status changed from needs_info to needs_review

comment:38 Changed 3 years ago by vbraun

  • Status changed from needs_review to positive_review

Thanks!

comment:39 Changed 3 years ago by vbraun

  • Branch changed from u/jdoyle/ticket/15389 to 8fed00f0386a0c29d0b85de1b4b6c30bb415af3c
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.