Opened 6 years ago
Closed 5 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:  sage6.3 
Component:  number theory  Keywords:  sagedays55 
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 6 years ago by
 Branch set to u/jdoyle/bdd_height
 Commit set to 6395710f6953fc50173226e0fa2eef565323d578
 Owner changed from dkrumm, jdoyle to dkrumm
comment:2 Changed 6 years ago by
 Commit changed from 6395710f6953fc50173226e0fa2eef565323d578 to b81322cb555becf5b44cf6a8419dbaf737f8f4fd
Branch pushed to git repo; I updated commit sha1. New commits:
b81322c  Edited the examples for the elements_of_bdd_height function 
6b4719b  We have included the new function elements_of_bdd_height in number_field.py 
c155659  Edited the elements_of_bdd_height function. 
74531e2  Further changes to bdd_height.py 
comment:3 Changed 6 years ago by
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 291298
# 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 followup: ↓ 5 Changed 6 years ago by
 Cc vdelecroix added
comment:5 in reply to: ↑ 4 Changed 6 years ago by
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 5 years ago by
 Commit changed from b81322cb555becf5b44cf6a8419dbaf737f8f4fd to e6a89f45a9ec3fca9987e919b9cb849cfa69e79f
Branch pushed to git repo; I updated commit sha1. New commits:
e6a89f4  Made minor improvements based on suggestions from vdelecroix.

comment:7 Changed 5 years ago by
 Cc jdoyle added
comment:8 Changed 5 years ago by
 Milestone changed from sage6.1 to sage6.2
comment:9 Changed 5 years ago by
 Commit changed from e6a89f45a9ec3fca9987e919b9cb849cfa69e79f to bac2d779a1cba38ec787e1a9cbfe77e609ccd99a
Branch pushed to git repo; I updated commit sha1. New commits:
bac2d77  Included option to compute LLLreduced basis for unit group.

comment:10 Changed 5 years ago by
 Milestone changed from sage6.2 to sage6.3
comment:11 Changed 5 years ago by
 Status changed from new to needs_review
comment:12 followup: ↓ 13 Changed 5 years ago by
 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
 same with real_mpfr.RealField?
 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 nonnegative 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 5 years ago by
Replying to bhutz:
 if bound is nonnegative 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 5 years ago by
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 5 years ago by
 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 5 years ago by
 Commit changed from bac2d779a1cba38ec787e1a9cbfe77e609ccd99a to 3b3950196522602f9d53b0088db285b10a70af2c
Branch pushed to git repo; I updated commit sha1. New commits:
3b39501  Updated number_field.py.

comment:17 Changed 5 years ago by
 Status changed from needs_work to needs_review
comment:18 Changed 5 years ago by
 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 5 years ago by
 Commit changed from 3b3950196522602f9d53b0088db285b10a70af2c to f48cf26707645c8adf6351fd2331511f00b013cb
Branch pushed to git repo; I updated commit sha1. New commits:
f48cf26  Changed import statement as per Ben's comment.

comment:21 Changed 5 years ago by
 Branch changed from u/jdoyle/ticket/15389 to f48cf26707645c8adf6351fd2331511f00b013cb
 Resolution set to fixed
 Status changed from positive_review to closed
comment:22 Changed 5 years ago by
 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 5 years ago by
 Branch changed from f48cf26707645c8adf6351fd2331511f00b013cb to u/jdoyle/ticket/15389
 Commit set to f48cf26707645c8adf6351fd2331511f00b013cb
Last 10 new commits:
74531e2  Further changes to bdd_height.py

c155659  Edited the elements_of_bdd_height function.

6b4719b  We have included the new function elements_of_bdd_height in number_field.py

b81322c  Edited the examples for the elements_of_bdd_height function

e6a89f4  Made minor improvements based on suggestions from vdelecroix.

bac2d77  Included option to compute LLLreduced basis for unit group.

8379f47  Merge branch 'master' into ticket/15389

087fefe  Made changes based on comments from bhutz.

3b39501  Updated number_field.py.

f48cf26  Changed import statement as per Ben's comment.

comment:24 Changed 5 years ago by
Failure on the OSX 10.9 buildbot is reproducable...
comment:25 Changed 5 years ago by
I had the same problem with my mac running OS 10.9.
comment:26 Changed 5 years ago by
 Commit changed from f48cf26707645c8adf6351fd2331511f00b013cb to cd36a73894be52bf69f9c5e9b5d7b7e998262e55
Branch pushed to git repo; I updated commit sha1. New commits:
cd36a73  Modified two examples and added pari import statement.

comment:27 Changed 5 years ago by
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 5 years ago by
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 5 years ago by
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 5 years ago by
All doctests are passing now on my machine running Mac OS 10.9.
comment:31 Changed 5 years ago by
 Status changed from new to needs_review
comment:32 Changed 5 years ago by
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 5 years ago by
 Commit changed from cd36a73894be52bf69f9c5e9b5d7b7e998262e55 to cdad564de1a6cd71f2d42d9f6844dd9070368b88
Branch pushed to git repo; I updated commit sha1. New commits:
cdad564  Removed some trailing whitespace from bdd_height.py.

comment:34 Changed 5 years ago by
 Status changed from needs_review to positive_review
comment:35 Changed 5 years ago by
 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 5 years ago by
 Commit changed from cdad564de1a6cd71f2d42d9f6844dd9070368b88 to 8fed00f0386a0c29d0b85de1b4b6c30bb415af3c
Branch pushed to git repo; I updated commit sha1. New commits:
8fed00f  Changed some examples so they take less time to test.

comment:37 Changed 5 years ago by
 Status changed from needs_info to needs_review
comment:39 Changed 5 years ago by
 Branch changed from u/jdoyle/ticket/15389 to 8fed00f0386a0c29d0b85de1b4b6c30bb415af3c
 Resolution set to fixed
 Status changed from positive_review to closed
Last 10 new commits: