points_of_bounded_height for projective space is incorrect

[bhutz]

The method for number fields iterates over the points of bounded height for each coordinate. This includes all the appropriate points, but includes some other points that are larger than the specified bound.

B=3
K.<v>=QuadraticField(3)
P.<x,y,z>=ProjectiveSpace(K,2)
for Q in P.points_of_bounded_height(bound=B):
    if exp(Q.global_height()) > B+0.001:
        print(Q,exp(Q.global_height()))

See also #31400

Depends on #34212

CC: @pfili @EnderWannabe @bhutz

Component: algebraic geometry

Keywords: gsoc2022

Author: Jing Guo

Branch/Commit: c053c2a

Reviewer: Alexander Galarraga, Ben Hutz

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

[bhutz]

comment:1

The simplest fix here is probably to check the height before yielding the point. This is not efficient, but would yield correct results, since every correct point does occur in this method.

If I don't hear another suggestion before I have time to fix this, I'll implement that (hopefully in the next week or two).

[EnderWannabe]

comment:3

There is a paper on by David Krumm on the topic (https://arxiv.org/pdf/1403.6501.pdf). He says in Section 7 that he implemented his algorithm in Sage for demonstration purposes. I'll write to him to ask for the code, and then perhaps we can fit his algorithm into Sage.

It might be worth it to implement a temporary fix in the mean time.

[bhutz]

comment:4

The Doyle-Krumm algorithm for points of bounded height in number fields is what is implemented in Sage for number field elements. The issue here is that the points of bounded height in projective space is simply taking the bound for each coordinate and that returns some points with too large a height. I don't think Doyle-Krumm address points in projective space in their paper.

[EnderWannabe]

comment:5

The above paper isn't Doyle Krumm 2011, it's a follow up paper - Krumm 2014. It seems to be about projective space specifically, as it is titled "Computing Points of Bounded Height in Projective Space over a Number Field."

[bhutz]

comment:6

Sorry, you're right, I had the wrong paper. Taking a quick look, I think we should fix the "wrong" output problem with the simple fix here and then make an enhancement ticket to run the faster algorithm from David.

[EnderWannabe]

Branch: u/gh-EnderWannabe/32686

[EnderWannabe]

comment:8

I agree, the algorithm from Krumm will take some time. He sent me his code - which at first glance works beautifully - so the majority of the work will be to write documentation and review the changes.

I've pushed a branch with the quick fix.

---

New commits:

e80d042

32686: added check to height of point before yielding + test

[EnderWannabe]

Commit: e80d042

[bhutz]

comment:10

Shouldn't this be <= in the check?

btw, can you send me the Krumm code (off-line).

[sagetrac-git]

Changed commit from e80d042 to a753459

[sagetrac-git]

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

a753459

32686: fixed inequality

[EnderWannabe]

Author: Alexander Galarraga

[bhutz]

comment:13

This looks fine. Let's let the patchbot pick it up for the full library test.

[bhutz]

comment:14

There are at least a couple doc test errors. Here is one.

File "src/sage/schemes/projective/projective_rational_point.py", line 190, in sage.schemes.projective.projective_rational_point.enum_projective_number_field
Failed example:
    enum_projective_number_field(X(K), bound=RR(5^(1/3)), prec=2^10)
Expected:
    [(0 : 0 : 1), (-1 : -1 : 1), (1 : 1 : 1), (-1/5*v^2 : -1/5*v^2 : 1), (-v : -v : 1),
    (1/5*v^2 : 1/5*v^2 : 1), (v : v : 1), (1 : 1 : 0)]
Got:
    [(0 : 0 : 1),
     (-1 : -1 : 1),
     (1 : 1 : 1),
     (-1/5*v^2 : -1/5*v^2 : 1),
     (1/5*v^2 : 1/5*v^2 : 1),
     (1 : 1 : 0)]

I think the new result is the one that is wrong with those two points having height exactly equal to the bound. Please double check.

[bhutz]

comment:15

Do you need to pass prec to the global_height call as this is probably a numerical issue somewhere...

[sagetrac-git]

Changed commit from a753459 to e39611d

[sagetrac-git]

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

e39611d

32686: changed check on global height before yielding

[EnderWannabe]

comment:17

I think you are right. Taking a look at the point (v : v : 1), we have

sage: X(P([v,v,1])).global_height() - log((RR(5^(1/3))))
1.11022302462516e-16

I think the right fix here is not to just check inequality, but to also check that the difference between the bounds is less than tolerance? Taking a look at the documentation for the points of bounded height function on number fields, it seems to yield all points that are within the tolerance, so maybe we should too.

I think the error in projective_homset.py isn't actually an error - before the fix we were yielding points with height above the bound.

[mkoeppe]

comment:18

Stalled in needs_review or needs_info; likely won't make it into Sage 9.5.

[guojing0]

comment:19

Has the Krumm code been integrated into the Sage code?

[sagetrac-git]

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

ff89c6e

32686: Correct doc and add an example

[sagetrac-git]

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

31d0587	32686: Change some example outputs
8afc292	32686: Debug `IQ_points_of_bounded_height`
b3b05c8	32686: Change example outputs
5958fc6	32686: Improve doc and return points in `self`
1c80864	32686: Change `self` to `K` in non-rational points_of_bounded_height
5ec496e	32686: Add `PN` to args of non-rational points_bdd
2adb101	32686: Correct tests
a237352	32686: Improve doc
00af5c7	32686: Correct doc and add an example
98a4676	32686: Correct example

[sagetrac-git]

Changed commit from ff89c6e to 98a4676

[EnderWannabe]

comment:58

Looks good!

[fchapoton]

comment:59

reviewer full name is missing

[EnderWannabe]

Changed author from Alexander Galarraga, Jing Guo to Jing Guo

[EnderWannabe]

Reviewer: Alexander Galarraga, Ben Hutz

[vbraun]

comment:61

See patchbot for failures

[sagetrac-git]

Changed commit from 98a4676 to c4aab9f

[sagetrac-git]

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

c4aab9f

32686: Remove unused imports and variables

[guojing0]

comment:63

Let the patch bot run.

[sagetrac-git]

Changed commit from c4aab9f to 10df9a6

[sagetrac-git]

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

10df9a6

32686: Correct example outputs in various files

[sagetrac-git]

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

c053c2a

32686: Format according to lint result

[sagetrac-git]

Changed commit from 10df9a6 to c053c2a

[vbraun]

Changed branch from u/gh-guojing0/points to c053c2a