An algorithm for enumerating elements of bounded height in number fields

[sagetrac-dkrumm]

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.

CC: @bhutz @videlec @sagetrac-jdoyle

Component: number theory

Keywords: sage-days55

Author: David Krumm, John Doyle

Branch/Commit: 8fed00f

Reviewer: Ben Hutz

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

[sagetrac-dkrumm]

Branch: u/jdoyle/bdd_height

[sagetrac-dkrumm]

Commit: 6395710

[sagetrac-dkrumm]

Last 10 new commits:

[6395710](https://github.com/sagemath/sagetrac-mirror/commit/6395710)	New changes to bdd_height.py
[2cd23d8](https://github.com/sagemath/sagetrac-mirror/commit/2cd23d8)	Added the file bdd_height.py; edited number_field.py to point to new file.
[https://github.com/sagemath/sagetrac-mirror/commit/# Pleas	# Pleas](https://github.com/sagemath/sagetrac-mirror/commit/# Pleas
[https://github.com/sagemath/sagetrac-mirror/commit/# with	# with ](https://github.com/sagemath/sagetrac-mirror/commit/# with
[https://github.com/sagemath/sagetrac-mirror/commit/# On br	# On br](https://github.com/sagemath/sagetrac-mirror/commit/# On br
[https://github.com/sagemath/sagetrac-mirror/commit/# Chang	# Chang](https://github.com/sagemath/sagetrac-mirror/commit/# Chang
[https://github.com/sagemath/sagetrac-mirror/commit/# (us	# (us](https://github.com/sagemath/sagetrac-mirror/commit/# (us
[#](https://github.com/sagemath/sagetrac-mirror/commit/#)
[https://github.com/sagemath/sagetrac-mirror/commit/# new f	# new f](https://github.com/sagemath/sagetrac-mirror/commit/# new f
[https://github.com/sagemath/sagetrac-mirror/commit/# modif	# modif](https://github.com/sagemath/sagetrac-mirror/commit/# modif

[sagetrac-git]

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

[b81322c](https://github.com/sagemath/sagetrac-mirror/commit/b81322c)	Edited the examples for the elements_of_bdd_height function
[6b4719b](https://github.com/sagemath/sagetrac-mirror/commit/6b4719b)	We have included the new function elements_of_bdd_height in number_field.py
[c155659](https://github.com/sagemath/sagetrac-mirror/commit/c155659)	Edited the elements_of_bdd_height function.
[74531e2](https://github.com/sagemath/sagetrac-mirror/commit/74531e2)	Further changes to bdd_height.py

[sagetrac-git]

Changed commit from 6395710 to b81322c

[videlec]

comment:3

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.

[sagetrac-dkrumm]

comment:5

Replying to @videlec:

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.

[sagetrac-git]

Changed commit from b81322c to e6a89f4

[sagetrac-git]

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

e6a89f4

Made minor improvements based on suggestions from vdelecroix.

[sagetrac-git]

Changed commit from e6a89f4 to bac2d77

[sagetrac-git]

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

bac2d77

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

[bhutz]

Reviewer: Ben Hutz

[bhutz]

comment:12

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

[sagetrac-dkrumm]

comment:13

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.

[bhutz]

comment:14

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

[sagetrac-jdoyle]

Changed branch from u/jdoyle/bdd_height to u/jdoyle/ticket/15389

[vbraun]

Commit: f48cf26

[vbraun]

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 LLL-reduced 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.

[vbraun]

comment:24

Failure on the OSX 10.9 buildbot is reproducable...

[sagetrac-dkrumm]

comment:25

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

[sagetrac-git]

Changed commit from f48cf26 to cd36a73

[sagetrac-git]

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

cd36a73

Modified two examples and added pari import statement.

[sagetrac-jdoyle]

comment:27

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.

[bhutz]

comment:28

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.

[sagetrac-dkrumm]

comment:29

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.

[sagetrac-dkrumm]

comment:30

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

[bhutz]

comment:32

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.

[sagetrac-git]

Changed commit from cd36a73 to cdad564

[sagetrac-git]

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

cdad564

Removed some trailing whitespace from bdd_height.py.

[vbraun]

comment:35

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.

[sagetrac-git]

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

8fed00f

Changed some examples so they take less time to test.

[sagetrac-git]

Changed commit from cdad564 to 8fed00f

[vbraun]

comment:38

Thanks!

[vbraun]

Changed branch from u/jdoyle/ticket/15389 to 8fed00f