Numerical Precision for Heights in Number Fields

[tjcombs]

Use real interval field for floating point computations to compute relative heights in number fields without precision errors.

[raghukul01]

New commits:

​53e69a2	Doyle-Krumm Algorithm 4 Implemented
​1e52f3d	Changes made in enum function

[git]

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

​ee98b33

Updated comments

[bhutz]

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

[git]

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

​f643368

22771: Reformat code and replaced iter with yield

[git]

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

​5a25a24

22771: Fixed conversion of d_tilde to RR

[bhutz]

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)

[git]

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

​aa3ace5

converted d_tilde globally to RR

[raghukul01]

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.

[bhutz]

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.

[git]

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

​ea7b41c	Doyle-Krumm 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

[raghukul01]

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

[vbraun]

Doctests fail. Run "make ptestlong"

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

[git]

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

​e6f53c8

Corrected doctest

[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

[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'?

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

[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).

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

[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).

[git]

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

​bef2fcd

updated universal value of tolerance parameter

[bhutz]

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.

[git]

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

​2383d52

22771: Corrected doctest in affine_homset and affine_rational_points

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

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

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

[raghukul01]

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

[git]

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

​ba1cd41

Docstring updated

[raghukul01]

updated doctests and docstrings

[bhutz]

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

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

[git]

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

​23a8c2c

Documentation updated

[bhutz]

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:

​3bc7acd

22771: docstring updates

[raghukul01]

New commits:

​fbceb52

added keywork in homsets and product_projective

[bhutz]

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.

[git]

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

​82edb4a

22771: some changes

[raghukul01]

added suggested changes

[bhutz]

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

[git]

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

​f88426b

fixed doctest

[raghukul01]

Corrected the line in hamming_code.py