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: sage-8.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:

Status badges

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 raghukul01

  • Branch set to u/raghukul01/numerical_precision_for_heights_in_number_fields

comment:2 Changed 4 years ago by raghukul01

  • Authors set to Raghukul Raman
  • Commit set to 1e52f3d6d42b189114b525ddcab3532d6439075a
  • Keywords number fields gsoc2018 added
  • Status changed from new to needs_review

New commits:

53e69a2Doyle-Krumm Algorithm 4 Implemented
1e52f3dChanges made in enum function

comment:3 Changed 4 years ago by git

  • Commit changed from 1e52f3d6d42b189114b525ddcab3532d6439075a to ee98b3318d835a895bbff36359ab046e518d259c

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

ee98b33Updated comments

comment:4 Changed 4 years ago by bhutz

  • 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([x-y])
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 git

  • Commit changed from ee98b3318d835a895bbff36359ab046e518d259c to f6433687380c987a3d906585cdb8fbd52515075b

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

f64336822771: Reformat code and replaced iter with yield

comment:6 Changed 4 years ago by git

  • Commit changed from f6433687380c987a3d906585cdb8fbd52515075b to 5a25a24329df4c8b1aeaf971a3b2bd90ca7d23e3

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

5a25a2422771: Fixed conversion of d_tilde to RR

comment:7 Changed 4 years ago by raghukul01

  • Status changed from needs_work to needs_review

comment:8 Changed 4 years ago by bhutz

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

  • Commit changed from 5a25a24329df4c8b1aeaf971a3b2bd90ca7d23e3 to aa3ace513ae79b05ae2f07b248d9d649376f025e

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

aa3ace5converted d_tilde globally to RR

comment:10 Changed 4 years ago by raghukul01

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

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

  • Commit changed from aa3ace513ae79b05ae2f07b248d9d649376f025e to 18cbd5ac3b98417cce273dfa12d47f71752c2c7b

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

ea7b41cDoyle-Krumm Algorithm 4 Implemented
b04b18cChanges made in enum function
395e254Updated comments
4e80b4422771: Reformat code and replaced iter with yield
4266f8922771: Fixed conversion of d_tilde to RR
07f97a1converted d_tilde globally to RR
18cbd5a22771: Fixed Caculation of relative height

comment:13 Changed 4 years ago by raghukul01

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

  • Status changed from needs_review to positive_review

comment:15 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Doctests fail. Run "make ptestlong"

comment:16 Changed 4 years ago by bhutz

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 follow-up: Changed 4 years ago by git

  • Commit changed from 18cbd5ac3b98417cce273dfa12d47f71752c2c7b to e6f53c889da3f7f4b12140a65ef7dba85029d568

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

e6f53c8Corrected doctest

comment:18 in reply to: ↑ 17 Changed 4 years ago by raghukul01

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

Replying to git:

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

e6f53c8Corrected doctest
Version 0, edited 4 years ago by raghukul01 (next)

comment:19 Changed 4 years ago by raghukul01

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

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 raghukul01

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 algorithm-3 we get correct output (2171). If we use bound 50 in algorithm-4 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 bhutz

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 raghukul01

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 bhutz

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 git

  • Commit changed from e6f53c889da3f7f4b12140a65ef7dba85029d568 to bef2fcd930739238131910170a820dad389b0480

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

bef2fcdupdated universal value of tolerance parameter

comment:26 Changed 4 years ago by bhutz

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

  • Commit changed from bef2fcd930739238131910170a820dad389b0480 to 2383d5220d39c95b527e7e612dbae102790cdd15

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

2383d5222771: Corrected doctest in affine_homset and affine_rational_points

comment:28 Changed 4 years ago by raghukul01

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 raghukul01

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 [Doyle-Krumm] algorithm cannot be guaranteed to be correct due to the necessity of floating point computations. In some cases, the default 53-bit 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!

Last edited 4 years ago by raghukul01 (previous) (diff)

comment:30 Changed 4 years ago by bhutz

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 raghukul01

Okay so should this comment be made only in bdd_height? or every place where bdd_height is called indirectly?

Last edited 4 years ago by raghukul01 (previous) (diff)

comment:32 Changed 4 years ago by git

  • Commit changed from 2383d5220d39c95b527e7e612dbae102790cdd15 to ba1cd419af55a84713c38600e4c5a48cfea5505d

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

ba1cd41Docstring updated

comment:33 Changed 4 years ago by raghukul01

  • Status changed from needs_work to needs_review

updated doctests and docstrings

comment:34 Changed 4 years ago by bhutz

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

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 git

  • Commit changed from ba1cd419af55a84713c38600e4c5a48cfea5505d to 23a8c2c68f5431a2ff39fbd2086625b3d32e9d1d

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

23a8c2cDocumentation updated

comment:37 Changed 4 years ago by raghukul01

  • Status changed from needs_work to needs_review

comment:38 Changed 4 years ago by bhutz

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

  • 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 --warn-long 63.5 product_projective/homset.py  # 1 doctest failed
sage -t --warn-long 63.5 product_projective/space.py  # 2 doctests failed

New commits:

3bc7acd22771: docstring updates

comment:40 Changed 4 years ago by raghukul01

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

  • Commit changed from 3bc7acd8c857e7aad5200781bdc780a37cec052e to fbceb5290e98e656d50114fdfd81f10e29cdd6d7
  • Status changed from needs_work to needs_review

New commits:

fbceb52added keywork in homsets and product_projective

comment:42 Changed 4 years ago by bhutz

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

  • Commit changed from fbceb5290e98e656d50114fdfd81f10e29cdd6d7 to 82edb4aaa36b4d62cda4843d3bf8b619953fc863

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

82edb4a22771: some changes

comment:44 Changed 4 years ago by raghukul01

  • Status changed from needs_work to needs_review

added suggested changes

comment:45 Changed 4 years ago by bhutz

  • Milestone changed from sage-8.0 to sage-8.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 --warn-long 66.7 src/sage/graphs/generators/smallgraphs.py  # 3 doctests failed
sage -t --long --warn-long 66.7 src/sage/coding/linear_code.py  # 109 doctests failed
sage -t --long --warn-long 66.7 src/sage/coding/codecan/autgroup_can_label.pyx  # 55 doctests failed
sage -t --long --warn-long 66.7 src/sage/coding/codecan/codecan.pyx  # 41 doctests failed
sage -t --long --warn-long 66.7 src/sage/coding/code_constructions.py  # 3 doctests failed
sage -t --long --warn-long 66.7 src/doc/en/constructions/linear_codes.rst  # 13 doctests failed
sage -t --long --warn-long 66.7 src/sage/coding/hamming_code.py  # 1 doctest failed
sage -t --long --warn-long 66.7 src/sage/tests/books/judson-abstract-algebra/algcodes-sage.py  # 9 doctests failed

comment:46 Changed 4 years ago by git

  • Commit changed from 82edb4aaa36b4d62cda4843d3bf8b619953fc863 to f88426be129022992e144d89dc25b12f96a2dfec

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

f88426bfixed doctest

comment:47 Changed 4 years ago by raghukul01

  • Status changed from needs_work to needs_review

Corrected the line in hamming_code.py

comment:48 Changed 4 years ago by bhutz

  • Status changed from needs_review to positive_review

comment:49 Changed 4 years ago by vbraun

  • 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
Note: See TracTickets for help on using tickets.