Opened 5 years ago
Closed 4 years ago
#22771 closed enhancement (fixed)
Numerical Precision for Heights in Number Fields
Reported by:  tjcombs  Owned by:  

Priority:  major  Milestone:  sage8.3 
Component:  algebraic geometry  Keywords:  number fields, gsoc2018 
Cc:  raghukul01, bhutz  Merged in:  
Authors:  Raghukul Raman  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  f88426b (Commits, GitHub, GitLab)  Commit:  f88426be129022992e144d89dc25b12f96a2dfec 
Dependencies:  Stopgaps: 
Description
Use real interval field for floating point computations to compute relative heights in number fields without precision errors.
Change History (49)
comment:1 Changed 4 years ago by
 Branch set to u/raghukul01/numerical_precision_for_heights_in_number_fields
comment:2 Changed 4 years ago by
 Commit set to 1e52f3d6d42b189114b525ddcab3532d6439075a
 Keywords number fields gsoc2018 added
 Status changed from new to needs_review
comment:3 Changed 4 years ago by
 Commit changed from 1e52f3d6d42b189114b525ddcab3532d6439075a to ee98b3318d835a895bbff36359ab046e518d259c
Branch pushed to git repo; I updated commit sha1. New commits:
ee98b33  Updated comments

comment:4 Changed 4 years ago by
 Reviewers set to Ben Hutz
 Status changed from needs_review to needs_work
Here are a few things I've noticed so far.
 Need to have in the longer description that this is using the 'relative multiplicative height'
 remove todo block (QQ and r=0 are covered in other functions)
 step 13: spelling: thier
 why switching to iter instead of yield? What about the issues of this being possibly *many* points? Please respond.
 LLL reduction still in docs for elements_of_bounded_height.
 need spaces between inputs lines in elements_of_bounded_height
 spaces after , in parameters
 This fails:
R.<x>=QQ[] K.<a> = NumberField(x^3  x^2 + 1) A.<x,y>=AffineSpace(K,2) list(A.points_of_bounded_height(2))
then so does subschemes
A.<x,y>=AffineSpace(K,2) C = A.subscheme([xy]) C.rational_points(2)
 reference should be updated with published version
 add yourself and TJ Combs to author section at top of file
comment:5 Changed 4 years ago by
 Commit changed from ee98b3318d835a895bbff36359ab046e518d259c to f6433687380c987a3d906585cdb8fbd52515075b
Branch pushed to git repo; I updated commit sha1. New commits:
f643368  22771: Reformat code and replaced iter with yield

comment:6 Changed 4 years ago by
 Commit changed from f6433687380c987a3d906585cdb8fbd52515075b to 5a25a24329df4c8b1aeaf971a3b2bd90ca7d23e3
Branch pushed to git repo; I updated commit sha1. New commits:
5a25a24  22771: Fixed conversion of d_tilde to RR

comment:7 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:8 Changed 4 years ago by
 Status changed from needs_review to needs_work
Sorry, I just realized I never commented on this. The fix does work, but I would change one thing.
d_tilde is used in a couple other places, so I would covert d_tilde to RR in the same place M is converted (after calculations with it are done)
d_tilde = RR(d_tilde)
comment:9 Changed 4 years ago by
 Commit changed from 5a25a24329df4c8b1aeaf971a3b2bd90ca7d23e3 to aa3ace513ae79b05ae2f07b248d9d649376f025e
Branch pushed to git repo; I updated commit sha1. New commits:
aa3ace5  converted d_tilde globally to RR

comment:10 Changed 4 years ago by
 Cc raghukul01 bhutz added
 Status changed from needs_work to needs_review
Sir, I have made the changes which you suggested, please review. I guess trac doesn't notify about commits pushed on the ticket, though I have added you to cc now.
comment:11 Changed 4 years ago by
 Status changed from needs_review to needs_work
no, I did get notified and even pulled it down and tested, but apparently I never put in my comments.
In going back over my tests with the new branch, there is one addition thing that I had noticed that needs to be fixed. With affine schemes working it exposed the fact that the height is converted to an absolute height incorrectly. In affine_space.py it has
bound = bound**(1/self.base_ring().absolute_degree())
which should be
bound = bound**self.base_ring().absolute_degree()
You may need to adjust an example. If not, you should definitely add one that ensures this bound is converted correctly.
comment:12 Changed 4 years ago by
 Commit changed from aa3ace513ae79b05ae2f07b248d9d649376f025e to 18cbd5ac3b98417cce273dfa12d47f71752c2c7b
Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:
ea7b41c  DoyleKrumm Algorithm 4 Implemented

b04b18c  Changes made in enum function

395e254  Updated comments

4e80b44  22771: Reformat code and replaced iter with yield

4266f89  22771: Fixed conversion of d_tilde to RR

07f97a1  converted d_tilde globally to RR

18cbd5a  22771: Fixed Caculation of relative height

comment:13 Changed 4 years ago by
 Status changed from needs_work to needs_review
I have changed the part which calculates relative height in affine_space.py, example 2 was taking a long time and the answer was also wrong. So I changed that (examples show previous calculation was wrong).
comment:14 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:15 Changed 4 years ago by
 Status changed from positive_review to needs_work
Doctests fail. Run "make ptestlong"
comment:16 Changed 4 years ago by
I ran the regular test, but neglected to reun the longtests
File "src/sage/rings/number_field/number_field.py", line 9375, in sage.rings.number_field.number_field.NumberField_absolute.elements_of_bounded_height Failed example: len(list(L)) # long time (2 s) Expected: 2163 Got: 2171
you should check if this is another case of alg 3 missing points. If so we can just correct the result value.
comment:17 followup: ↓ 18 Changed 4 years ago by
 Commit changed from 18cbd5ac3b98417cce273dfa12d47f71752c2c7b to e6f53c889da3f7f4b12140a65ef7dba85029d568
Branch pushed to git repo; I updated commit sha1. New commits:
e6f53c8  Corrected doctest

comment:18 in reply to: ↑ 17 Changed 4 years ago by
comment:19 Changed 4 years ago by
 Status changed from needs_work to needs_review
Yes it was a case of missing points, changing the height to 50.1 yeilds required output
sage: K.<a> = NumberField(x^4  5) sage: L = K.elements_of_bounded_height(50.1) sage: len(list(L)) # long time (2 s) 2171
comment:20 Changed 4 years ago by
Changing the height bound is not quite what I meant. It sounds like this is an instance of getting the points in L' which are supposed to be within tolerance of the height
abs(H_k(x)  B) < tolerance
If you need to move the bound to 50.1, then these points are outside of the specified tolerance when bound=50. Since we have to do some conversion between relative and absolute heights. Perhaps the issue is that tolerance must also undergo a similar 'conversion'?
comment:21 Changed 4 years ago by
Sorry, my comment was quite confusing,
What I meant was if we change the bound to 50.1 or even to 50.02 (current default of tolerance is 0.01), and use algorithm3 we get correct output (2171). If we use bound 50 in algorithm4 we get 2171 as the output.
So it was a case of missing points.
Which conversion are you suggesting? we are dealing with relative heights here, right?
comment:22 Changed 4 years ago by
The point I'm making is that we shouldn't be seeing if we can adjust the parameters to gt the 'right' answer, but rather see which is the right answer for the parameters in the doctest.
The difference are the eight points which all have height
50.0163488242872
so, if the tolerance is specified as 0.01 with a bound of 50, then these points should not be returned. In other words, that would be a failure in the tolerance.
Actually, it looks like the number_field.py function has default tolerance 0.2, which makes the new output correct, however, the other function (bdd_height) has default tolerance 0.01. I would say maybe to make the default tolerance in all of these functions the same (perhaps the 0.01).
comment:23 Changed 4 years ago by
Yes sir, I got your point, but before changing there is one issue.
What should be the ideal value of tolerance, in earlier testing 0.01 was good enough, but as in this example height can be very close to tolerance (0.01634..). My suggestion is still to use 0.01, what are your views on that?
comment:24 Changed 4 years ago by
I'm fine with 0.01. More important than the default value is that tolerance does what is claims it does (find all points within tolerance of the specified bound).
comment:25 Changed 4 years ago by
 Commit changed from e6f53c889da3f7f4b12140a65ef7dba85029d568 to bef2fcd930739238131910170a820dad389b0480
Branch pushed to git repo; I updated commit sha1. New commits:
bef2fcd  updated universal value of tolerance parameter

comment:26 Changed 4 years ago by
 Status changed from needs_review to needs_work
I get doctest failures in affine_homset and affine_rational_points.
Additionally, in my testing tolerance is not behaving as described. In other words you can get points that do not satisfy H(P)  B < tol. However, these points are always points that are above the specified height bound, so I do not think is concerning. However, the documentation should be updated accordingly.
comment:27 Changed 4 years ago by
 Commit changed from bef2fcd930739238131910170a820dad389b0480 to 2383d5220d39c95b527e7e612dbae102790cdd15
Branch pushed to git repo; I updated commit sha1. New commits:
2383d52  22771: Corrected doctest in affine_homset and affine_rational_points

comment:28 Changed 4 years ago by
Doc test were failing due to incorrect calculation of relative height, which was corrected in earlier commit. I have changes the bound accordingly, keeping existing bound would have taken very long time for the tests.
comment:29 Changed 4 years ago by
Sir,
For the documentation update I am planning to modify the current warning of algorithm 3 result (In the current implementation, the output of the [DoyleKrumm] algorithm cannot be guaranteed to be correct due to the necessity of floating point computations. In some cases, the default 53bit precision is considerably lower than would be required for the algorithm to generate correct output.
) to what you are suggesting that there might me some points for which H(p) > B + tolerance
, does this seem right?
BTW can you share those tests?
thanks in advance!
comment:30 Changed 4 years ago by
I'm not sure it requires a warning block as it does return all of the points up to the bound and decreasing the tolerance does get you exactly the points up to that bound. The part that I am finding inaccurate is the precise relationship between tolerance and those extra points. Clarifying that there are floating point issues and you may get extra points which can be 'corrected' by lowering the tolerance in enough.
comment:31 Changed 4 years ago by
Okay so should this comment be made only in bdd_height? or every place where bdd_height is called indirectly?
comment:32 Changed 4 years ago by
 Commit changed from 2383d5220d39c95b527e7e612dbae102790cdd15 to ba1cd419af55a84713c38600e4c5a48cfea5505d
Branch pushed to git repo; I updated commit sha1. New commits:
ba1cd41  Docstring updated

comment:33 Changed 4 years ago by
 Status changed from needs_work to needs_review
updated doctests and docstrings
comment:34 Changed 4 years ago by
 Status changed from needs_review to needs_work
I'm ok with the vague description of lowering tolerance, except that I would not just say extra, but rather points larger than the specified bound.
However, there are still a number of documentation issues surrounding tolerance that I had missed earlier.
 bdd_height still claims that all points satisfy H(P)  B < tol. Which is what I am finding to be not accurate.
 elements_of_bounded_height still lists the old warning
 there is no way to specify tolerance or precision in the places affine objects call enum_number_field
 there is no way specify tolerance in the places projective objects call enum_number_field
 The statements about what algorithm is used etc, should be also be in the indirect call places as well. (these are actually more likely to be used by the user).
comment:35 Changed 4 years ago by
btw, this is a situation where I'd be tempted to switch the affine.rational_points/.points and projective.rational_points/.points functions to *kwds since which keywords are needed dependents on which situation/algorithm is being used.
comment:36 Changed 4 years ago by
 Commit changed from ba1cd419af55a84713c38600e4c5a48cfea5505d to 23a8c2c68f5431a2ff39fbd2086625b3d32e9d1d
Branch pushed to git repo; I updated commit sha1. New commits:
23a8c2c  Documentation updated

comment:37 Changed 4 years ago by
 Status changed from needs_work to needs_review
comment:38 Changed 4 years ago by
 Branch changed from u/raghukul01/numerical_precision_for_heights_in_number_fields to u/bhutz/numerical_precision_for_heights_in_number_fields
comment:39 Changed 4 years ago by
 Commit changed from 23a8c2c68f5431a2ff39fbd2086625b3d32e9d1d to 3bc7acd8c857e7aad5200781bdc780a37cec052e
 Status changed from needs_review to needs_work
Here is a suggestion for updating the docs. Please look over for typos.
Also there are still a couple functionality things: kwds needed so tolerance, precision can be specified if needed
 affine homeset needs *kwds
 product projective needs *kwds
 projective homset needs *kwds
need to remember to run doctests before pushing...
sage t warnlong 63.5 product_projective/homset.py # 1 doctest failed sage t warnlong 63.5 product_projective/space.py # 2 doctests failed
New commits:
3bc7acd  22771: docstring updates

comment:40 Changed 4 years ago by
 Branch changed from u/bhutz/numerical_precision_for_heights_in_number_fields to u/raghukul01/numerical_precision_for_heights_in_number_fields
comment:41 Changed 4 years ago by
 Commit changed from 3bc7acd8c857e7aad5200781bdc780a37cec052e to fbceb5290e98e656d50114fdfd81f10e29cdd6d7
 Status changed from needs_work to needs_review
New commits:
fbceb52  added keywork in homsets and product_projective

comment:42 Changed 4 years ago by
 Status changed from needs_review to needs_work
algorithm 5 is spelled wrong evertywhere
in affine homset: dimension zero line in docs. this doesn't work for rings, so you probably mean: whether the field is infinite or not.
comment:43 Changed 4 years ago by
 Commit changed from fbceb5290e98e656d50114fdfd81f10e29cdd6d7 to 82edb4aaa36b4d62cda4843d3bf8b619953fc863
Branch pushed to git repo; I updated commit sha1. New commits:
82edb4a  22771: some changes

comment:44 Changed 4 years ago by
 Status changed from needs_work to needs_review
added suggested changes
comment:45 Changed 4 years ago by
 Milestone changed from sage8.0 to sage8.3
 Status changed from needs_review to needs_work
from ptestlong looks like the same set of failures from we got in #23627
sage t long warnlong 66.7 src/sage/graphs/generators/smallgraphs.py # 3 doctests failed sage t long warnlong 66.7 src/sage/coding/linear_code.py # 109 doctests failed sage t long warnlong 66.7 src/sage/coding/codecan/autgroup_can_label.pyx # 55 doctests failed sage t long warnlong 66.7 src/sage/coding/codecan/codecan.pyx # 41 doctests failed sage t long warnlong 66.7 src/sage/coding/code_constructions.py # 3 doctests failed sage t long warnlong 66.7 src/doc/en/constructions/linear_codes.rst # 13 doctests failed sage t long warnlong 66.7 src/sage/coding/hamming_code.py # 1 doctest failed sage t long warnlong 66.7 src/sage/tests/books/judsonabstractalgebra/algcodessage.py # 9 doctests failed
comment:46 Changed 4 years ago by
 Commit changed from 82edb4aaa36b4d62cda4843d3bf8b619953fc863 to f88426be129022992e144d89dc25b12f96a2dfec
Branch pushed to git repo; I updated commit sha1. New commits:
f88426b  fixed doctest

comment:47 Changed 4 years ago by
 Status changed from needs_work to needs_review
Corrected the line in hamming_code.py
comment:48 Changed 4 years ago by
 Status changed from needs_review to positive_review
comment:49 Changed 4 years ago by
 Branch changed from u/raghukul01/numerical_precision_for_heights_in_number_fields to f88426be129022992e144d89dc25b12f96a2dfec
 Resolution set to fixed
 Status changed from positive_review to closed
New commits:
DoyleKrumm Algorithm 4 Implemented
Changes made in enum function