Opened 14 months ago

Closed 7 weeks ago

#32686 closed defect (fixed)

points_of_bounded_height for projective space is incorrect

Reported by: Ben Hutz Owned by: Ben Hutz
Priority: major Milestone: sage-9.8
Component: algebraic geometry Keywords: gsoc2022
Cc: pfili, Alexander Galarraga, Ben Hutz Merged in:
Authors: Jing Guo Reviewers: Alexander Galarraga, Ben Hutz
Report Upstream: N/A Work issues:
Branch: c053c2a (Commits, GitHub, GitLab) Commit: c053c2ac5367b08f553d6dd3d4fa86dec14bc09d
Dependencies: #34212 Stopgaps:

Status badges

Description

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

Change History (67)

comment:1 Changed 14 months ago by Ben Hutz

Owner: set to Ben Hutz

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

comment:2 Changed 14 months ago by Alexander Galarraga

Cc: Alexander Galarraga added

comment:3 Changed 13 months ago by Alexander Galarraga

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.

comment:4 Changed 13 months ago by Ben Hutz

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.

comment:5 Changed 13 months ago by Alexander Galarraga

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

comment:6 Changed 13 months ago by Ben Hutz

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.

comment:7 Changed 13 months ago by Alexander Galarraga

Branch: u/gh-EnderWannabe/32686

comment:8 Changed 13 months ago by Alexander Galarraga

Commit: e80d0425e3d025b6f3d94731d6b6c49dd8c8003c

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:

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

comment:9 Changed 13 months ago by Alexander Galarraga

Status: newneeds_review

comment:10 Changed 13 months ago by Ben Hutz

Shouldn't this be <= in the check?

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

comment:11 Changed 13 months ago by git

Commit: e80d0425e3d025b6f3d94731d6b6c49dd8c8003ca753459e083283195d4f290e3676892fbe9eda16

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

a75345932686: fixed inequality

comment:12 Changed 13 months ago by Alexander Galarraga

Authors: Alexander Galarraga

comment:13 Changed 13 months ago by Ben Hutz

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

comment:14 Changed 13 months ago by Ben Hutz

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.

comment:15 Changed 13 months ago by Ben Hutz

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

comment:16 Changed 13 months ago by git

Commit: a753459e083283195d4f290e3676892fbe9eda16e39611d358e50daecc4c367b838efffec4adda6a

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

e39611d32686: changed check on global height before yielding

comment:17 Changed 13 months ago by Alexander Galarraga

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.

comment:18 Changed 12 months ago by Matthias Köppe

Milestone: sage-9.5sage-9.6

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

comment:19 Changed 8 months ago by Jing Guo

Has the Krumm code been integrated into the Sage code?

comment:20 Changed 7 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:21 Changed 5 months ago by Jing Guo

Cc: Ben Hutz added
Keywords: gsoc2022 added

comment:22 Changed 5 months ago by Jing Guo

Authors: Alexander GalarragaAlexander Galarraga, Jing Guo
Branch: u/gh-EnderWannabe/32686u/gh-guojing0/32686_pobh
Commit: e39611d358e50daecc4c367b838efffec4adda6a625ac58151d34ba21cf7e8ebcb31170deb88c457
Status: needs_reviewneeds_work

comment:23 Changed 5 months ago by git

Commit: 625ac58151d34ba21cf7e8ebcb31170deb88c457f37f639256c753fcf55d75e25ec5bd7137f1336f

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

f37f63932686: QQ_points_of_bounded_height

comment:24 Changed 5 months ago by git

Commit: f37f639256c753fcf55d75e25ec5bd7137f1336f35552f563d7adb4b2ea61e125833a5ecdff63697

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

35552f532686: Krumm code to projective_space.py

comment:25 Changed 3 months ago by Jing Guo

Branch: u/gh-guojing0/32686_pobhu/gh-guojing0/points
Commit: 35552f563d7adb4b2ea61e125833a5ecdff636977deccb66793f0230a9c5e9644abddd52b7addb49
Dependencies: #34212

New commits:

42ffe7cpoints
eb7aaf5clean
ad70de3clean
495febbrational
7deccb6import

comment:26 Changed 3 months ago by git

Commit: 7deccb66793f0230a9c5e9644abddd52b7addb498310541f07cb2dff05d734588913ce8fd36bc641

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

d08647934212: clean version
2e9c42a34212: fix doc
ba8c65834212: fix doc and code
fd52184points
b0e5a5aclean
587d113clean
4db42f6rational
2b6e068import
8310541number fields

comment:27 Changed 3 months ago by git

Commit: 8310541f07cb2dff05d734588913ce8fd36bc641bcd21b17da2e292e67b4d7888be2ad26e6edc3ee

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

bcd21b1log embed

comment:28 Changed 3 months ago by git

Commit: bcd21b17da2e292e67b4d7888be2ad26e6edc3ee09fb1324d14871089b9673d0b53ac59c0d21c9f7

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

09fb132doc

comment:29 Changed 3 months ago by git

Commit: 09fb1324d14871089b9673d0b53ac59c0d21c9f702a3d82e574cc6c96aff464b41c128e4cc365d5b

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

02a3d82indent

comment:30 Changed 3 months ago by git

Commit: 02a3d82e574cc6c96aff464b41c128e4cc365d5bde28c6e55fcb2ae90f7fcdc745cc45b45e5fddb9

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

de28c6epython 2 to python 3

comment:31 Changed 3 months ago by git

Commit: de28c6e55fcb2ae90f7fcdc745cc45b45e5fddb9f37f4b2b8cf6b8c7186b3ddd54804dc947776a8f

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

f37f4b2some small changes

comment:32 Changed 3 months ago by git

Commit: f37f4b2b8cf6b8c7186b3ddd54804dc947776a8ff81825e9a6bd40565e7f058d8816fd25df423f10

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

f81825erestore commented line

comment:33 Changed 3 months ago by git

Commit: f81825e9a6bd40565e7f058d8816fd25df423f10dfcf951e84f2d791dcf35b2bee5cc2b687a2e267

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

dfcf951examples

comment:34 Changed 3 months ago by Jing Guo

Status: needs_workneeds_review

comment:35 Changed 3 months ago by git

Commit: dfcf951e84f2d791dcf35b2bee5cc2b687a2e267e5e4dee501ec5f59b651161c58d3660909b7a1f5

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

e5e4deemore examples and rel degree

comment:36 Changed 3 months ago by git

Commit: e5e4dee501ec5f59b651161c58d3660909b7a1f5c14579e2182e7b9919c6e795bfb1b6af24e32d58

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

d8eb584number fields
8abd8calog embed
8eb2d84doc
c8ac591indent
5bfe937python 2 to python 3
ecd4549some small changes
4ed4545restore commented line
72ae6cfexamples
1ea9fa3more examples and rel degree
c14579e34686: Support for relative number field

comment:37 Changed 3 months ago by git

Commit: c14579e2182e7b9919c6e795bfb1b6af24e32d583e803a0ae1e7df9f731472ef29a461a7ff0a40df

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

3e803a032686: points_of_bounded_height for imaginary quadraitc field

comment:38 Changed 3 months ago by git

Commit: 3e803a0ae1e7df9f731472ef29a461a7ff0a40dfd52be45473f3df6ef24c51f4432ef9a07a777057

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

d52be4532686: Support for imaginary quadratic field

comment:39 Changed 3 months ago by git

Commit: d52be45473f3df6ef24c51f4432ef9a07a7770577f615db42934068c2fbfb503b84264d5f68dafdf

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

7f615db32686: Raise degree to absolute degree

comment:40 Changed 3 months ago by git

Commit: 7f615db42934068c2fbfb503b84264d5f68dafdfebbcec4dad4dc8629d25dac765ebc3a9c0325465

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

ebbcec432686: Correct typo, add doc, and remove an unnecessary example

comment:41 Changed 3 months ago by git

Commit: ebbcec4dad4dc8629d25dac765ebc3a9c0325465f8bdb25fd77c41bf11a2958a9cba10500c04faca

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

f8bdb2532686: Correct some examples in hyperplane_transformation_matrix

comment:42 Changed 3 months ago by git

Commit: f8bdb25fd77c41bf11a2958a9cba10500c04facaf3af0c6067d870b766bb72313f96cc6a8ac697b5

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

f3af0c632686: mention Trac ticket 11328 for insert_row

comment:43 Changed 3 months ago by git

Commit: f3af0c6067d870b766bb72313f96cc6a8ac697b54d58e11594da9ea1b7857fcc08eb8f243e04bb60

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

a48141432686: Change ring when no common parent
4d58e11Merge branch 'u/gh-guojing0/points' of trac.sagemath.org:sage into points

comment:44 Changed 3 months ago by git

Commit: 4d58e11594da9ea1b7857fcc08eb8f243e04bb60c45c362d34e3d0a7b31cd14c837c688a3605d1f3

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

a669f1c32686: `bound` allows real numbers and `yield` instead of returning a
c45c362Merge branch 'u/gh-guojing0/points' of https://github.com/sagemath/sagetrac-mirror into points

comment:45 Changed 3 months ago by git

Commit: c45c362d34e3d0a7b31cd14c837c688a3605d1f397933db9b22f30838ad608b093d186c3fca101f4

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

97933db32686: Change some example outputs

comment:46 Changed 3 months ago by git

Commit: 97933db9b22f30838ad608b093d186c3fca101f4a87c3111ee18081763b02b0ccbe96cb87ebbdcc2

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

a87c31132686: Debug `IQ_points_of_bounded_height`

comment:47 Changed 3 months ago by git

Commit: a87c3111ee18081763b02b0ccbe96cb87ebbdcc2f261b8bd578d2bca080cfcb7bf39ee6e8008443e

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

f261b8b32686: Change example outputs

comment:48 Changed 3 months ago by git

Commit: f261b8bd578d2bca080cfcb7bf39ee6e8008443eb68ec93635cda000c4230333195ef850ad331342

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

b68ec9332686: Improve doc and return points in `self`

comment:49 Changed 3 months ago by git

Commit: b68ec93635cda000c4230333195ef850ad331342588260da0be93dd82810a5d31285401a54854c43

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

588260d32686: Change `self` to `K` in non-rational points_of_bounded_height

comment:50 Changed 3 months ago by git

Commit: 588260da0be93dd82810a5d31285401a54854c4383e52b85ca789d2b9b8468a11e9e34475a69fef3

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

83e52b832686: Add `PN` to args of non-rational points_bdd

comment:51 Changed 3 months ago by git

Commit: 83e52b85ca789d2b9b8468a11e9e34475a69fef3e8b8ab92c2bb0e32403b0378576cbfdfea7b3072

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

e8b8ab932686: Correct tests

comment:52 Changed 3 months ago by git

Commit: e8b8ab92c2bb0e32403b0378576cbfdfea7b3072458fba4a6a4fcbd65987e83fa60ed2fd9c034671

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

458fba432686: Improve doc

comment:53 Changed 3 months ago by Matthias Köppe

Milestone: sage-9.7sage-9.8

comment:54 Changed 3 months ago by Alexander Galarraga

Status: needs_reviewneeds_work

Everything seems to be working well. The only remaining issues are with the docs. The input block for points_of_bounded_height says that bound needs to be an integer, but bound can be a positive real number. You should also add an example where bound isn't an integer.

comment:55 Changed 3 months ago by git

Commit: 458fba4a6a4fcbd65987e83fa60ed2fd9c034671ff89c6e33e9b388bbf21a615990e6cbb1693f902

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

ff89c6e32686: Correct doc and add an example

comment:56 Changed 3 months ago by git

Commit: ff89c6e33e9b388bbf21a615990e6cbb1693f90298a467602c4f4959cb847963ad08ade3334841b9

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

31d058732686: Change some example outputs
8afc29232686: Debug `IQ_points_of_bounded_height`
b3b05c832686: Change example outputs
5958fc632686: Improve doc and return points in `self`
1c8086432686: Change `self` to `K` in non-rational points_of_bounded_height
5ec496e32686: Add `PN` to args of non-rational points_bdd
2adb10132686: Correct tests
a23735232686: Improve doc
00af5c732686: Correct doc and add an example
98a467632686: Correct example

comment:57 Changed 3 months ago by Jing Guo

Status: needs_workneeds_review

comment:58 Changed 3 months ago by Alexander Galarraga

Status: needs_reviewpositive_review

Looks good!

comment:59 Changed 2 months ago by Frédéric Chapoton

reviewer full name is missing

comment:60 Changed 2 months ago by Alexander Galarraga

Authors: Alexander Galarraga, Jing GuoJing Guo
Reviewers: Alexander Galarraga, Ben Hutz

comment:61 Changed 2 months ago by Volker Braun

Status: positive_reviewneeds_work

See patchbot for failures

comment:62 Changed 2 months ago by git

Commit: 98a467602c4f4959cb847963ad08ade3334841b9c4aab9f9dc11d787945fad21be16beee4b025456

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

c4aab9f32686: Remove unused imports and variables

comment:63 Changed 2 months ago by Jing Guo

Status: needs_workneeds_review

Let the patch bot run.

comment:64 Changed 2 months ago by git

Commit: c4aab9f9dc11d787945fad21be16beee4b02545610df9a648550ddf79315e9a6c9843eed01415d08

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

10df9a632686: Correct example outputs in various files

comment:65 Changed 2 months ago by git

Commit: 10df9a648550ddf79315e9a6c9843eed01415d08c053c2ac5367b08f553d6dd3d4fa86dec14bc09d

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

c053c2a32686: Format according to lint result

comment:66 Changed 2 months ago by Jing Guo

Status: needs_reviewpositive_review

comment:67 Changed 7 weeks ago by Volker Braun

Branch: u/gh-guojing0/pointsc053c2ac5367b08f553d6dd3d4fa86dec14bc09d
Resolution: fixed
Status: positive_reviewclosed
Note: See TracTickets for help on using tickets.