Opened 14 months ago

Closed 7 weeks ago

# points_of_bounded_height for projective space is incorrect

Reported by: Owned by: Ben Hutz Ben Hutz major sage-9.8 algebraic geometry gsoc2022 pfili, Alexander Galarraga, Ben Hutz Jing Guo Alexander Galarraga, Ben Hutz N/A c053c2a c053c2ac5367b08f553d6dd3d4fa86dec14bc09d #34212

### 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
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()))
```

### 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: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:

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

### comment:9 Changed 13 months ago by Alexander Galarraga

Status: new → needs_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: e80d0425e3d025b6f3d94731d6b6c49dd8c8003c → a753459e083283195d4f290e3676892fbe9eda16

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

 ​a753459 `32686: 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

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

 ​e39611d `32686: 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.5 → sage-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.6 → sage-9.7

### comment:22 Changed 5 months ago by Jing Guo

Authors: Alexander Galarraga → Alexander Galarraga, Jing Guo u/gh-EnderWannabe/32686 → u/gh-guojing0/32686_pobh e39611d358e50daecc4c367b838efffec4adda6a → 625ac58151d34ba21cf7e8ebcb31170deb88c457 needs_review → needs_work

### comment:23 Changed 5 months ago by git

Commit: 625ac58151d34ba21cf7e8ebcb31170deb88c457 → f37f639256c753fcf55d75e25ec5bd7137f1336f

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

 ​f37f639 `32686: QQ_points_of_bounded_height`

### comment:24 Changed 5 months ago by git

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

 ​35552f5 `32686: Krumm code to projective_space.py`

### comment:25 Changed 3 months ago by Jing Guo

New commits:

 ​42ffe7c `points` ​eb7aaf5 `clean` ​ad70de3 `clean` ​495febb `rational` ​7deccb6 `import`

### comment:26 Changed 3 months ago by git

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

 ​d086479 `34212: clean version` ​2e9c42a `34212: fix doc` ​ba8c658 `34212: fix doc and code` ​fd52184 `points` ​b0e5a5a `clean` ​587d113 `clean` ​4db42f6 `rational` ​2b6e068 `import` ​8310541 `number fields`

### comment:27 Changed 3 months ago by git

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

 ​bcd21b1 `log embed`

### comment:28 Changed 3 months ago by git

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

 ​09fb132 `doc`

### comment:29 Changed 3 months ago by git

Commit: 09fb1324d14871089b9673d0b53ac59c0d21c9f7 → 02a3d82e574cc6c96aff464b41c128e4cc365d5b

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

 ​02a3d82 `indent`

### comment:30 Changed 3 months ago by git

Commit: 02a3d82e574cc6c96aff464b41c128e4cc365d5b → de28c6e55fcb2ae90f7fcdc745cc45b45e5fddb9

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

 ​de28c6e `python 2 to python 3`

### comment:31 Changed 3 months ago by git

Commit: de28c6e55fcb2ae90f7fcdc745cc45b45e5fddb9 → f37f4b2b8cf6b8c7186b3ddd54804dc947776a8f

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

 ​f37f4b2 `some small changes`

### comment:32 Changed 3 months ago by git

Commit: f37f4b2b8cf6b8c7186b3ddd54804dc947776a8f → f81825e9a6bd40565e7f058d8816fd25df423f10

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

 ​f81825e `restore commented line`

### comment:33 Changed 3 months ago by git

Commit: f81825e9a6bd40565e7f058d8816fd25df423f10 → dfcf951e84f2d791dcf35b2bee5cc2b687a2e267

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

 ​dfcf951 `examples`

### comment:34 Changed 3 months ago by Jing Guo

Status: needs_work → needs_review

### comment:35 Changed 3 months ago by git

Commit: dfcf951e84f2d791dcf35b2bee5cc2b687a2e267 → e5e4dee501ec5f59b651161c58d3660909b7a1f5

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

 ​e5e4dee `more examples and rel degree`

### comment:36 Changed 3 months ago by git

Commit: e5e4dee501ec5f59b651161c58d3660909b7a1f5 → c14579e2182e7b9919c6e795bfb1b6af24e32d58

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

 ​d8eb584 `number fields` ​8abd8ca `log embed` ​8eb2d84 `doc` ​c8ac591 `indent` ​5bfe937 `python 2 to python 3` ​ecd4549 `some small changes` ​4ed4545 `restore commented line` ​72ae6cf `examples` ​1ea9fa3 `more examples and rel degree` ​c14579e `34686: Support for relative number field`

### comment:37 Changed 3 months ago by git

Commit: c14579e2182e7b9919c6e795bfb1b6af24e32d58 → 3e803a0ae1e7df9f731472ef29a461a7ff0a40df

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

 ​3e803a0 `32686: points_of_bounded_height for imaginary quadraitc field`

### comment:38 Changed 3 months ago by git

Commit: 3e803a0ae1e7df9f731472ef29a461a7ff0a40df → d52be45473f3df6ef24c51f4432ef9a07a777057

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

 ​d52be45 `32686: Support for imaginary quadratic field`

### comment:39 Changed 3 months ago by git

Commit: d52be45473f3df6ef24c51f4432ef9a07a777057 → 7f615db42934068c2fbfb503b84264d5f68dafdf

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

 ​7f615db `32686: Raise degree to absolute degree`

### comment:40 Changed 3 months ago by git

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

 ​ebbcec4 `32686: Correct typo, add doc, and remove an unnecessary example`

### comment:41 Changed 3 months ago by git

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

 ​f8bdb25 `32686: Correct some examples in hyperplane_transformation_matrix`

### comment:42 Changed 3 months ago by git

Commit: f8bdb25fd77c41bf11a2958a9cba10500c04faca → f3af0c6067d870b766bb72313f96cc6a8ac697b5

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

 ​f3af0c6 `32686: mention Trac ticket 11328 for insert_row`

### comment:43 Changed 3 months ago by git

Commit: f3af0c6067d870b766bb72313f96cc6a8ac697b5 → 4d58e11594da9ea1b7857fcc08eb8f243e04bb60

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

 ​a481414 `32686: Change ring when no common parent` ​4d58e11 `Merge branch 'u/gh-guojing0/points' of trac.sagemath.org:sage into points`

### comment:44 Changed 3 months ago by git

Commit: 4d58e11594da9ea1b7857fcc08eb8f243e04bb60 → c45c362d34e3d0a7b31cd14c837c688a3605d1f3

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

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

### comment:45 Changed 3 months ago by git

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

 ​97933db `32686: Change some example outputs`

### comment:46 Changed 3 months ago by git

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

 ​a87c311 `32686: Debug `IQ_points_of_bounded_height``

### comment:47 Changed 3 months ago by git

Commit: a87c3111ee18081763b02b0ccbe96cb87ebbdcc2 → f261b8bd578d2bca080cfcb7bf39ee6e8008443e

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

 ​f261b8b `32686: Change example outputs`

### comment:48 Changed 3 months ago by git

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

 ​b68ec93 `32686: Improve doc and return points in `self``

### comment:49 Changed 3 months ago by git

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

 ​588260d `32686: Change `self` to `K` in non-rational points_of_bounded_height`

### comment:50 Changed 3 months ago by git

Commit: 588260da0be93dd82810a5d31285401a54854c43 → 83e52b85ca789d2b9b8468a11e9e34475a69fef3

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

 ​83e52b8 `32686: Add `PN` to args of non-rational points_bdd`

### comment:51 Changed 3 months ago by git

Commit: 83e52b85ca789d2b9b8468a11e9e34475a69fef3 → e8b8ab92c2bb0e32403b0378576cbfdfea7b3072

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

 ​e8b8ab9 `32686: Correct tests`

### comment:52 Changed 3 months ago by git

Commit: e8b8ab92c2bb0e32403b0378576cbfdfea7b3072 → 458fba4a6a4fcbd65987e83fa60ed2fd9c034671

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

 ​458fba4 `32686: Improve doc`

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

Milestone: sage-9.7 → sage-9.8

### comment:54 Changed 3 months ago by Alexander Galarraga

Status: needs_review → needs_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: 458fba4a6a4fcbd65987e83fa60ed2fd9c034671 → ff89c6e33e9b388bbf21a615990e6cbb1693f902

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

 ​ff89c6e `32686: Correct doc and add an example`

### comment:56 Changed 3 months ago by 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`

### comment:57 Changed 3 months ago by Jing Guo

Status: needs_work → needs_review

### comment:58 Changed 3 months ago by Alexander Galarraga

Status: needs_review → positive_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 Guo → Jing Guo → Alexander Galarraga, Ben Hutz

### comment:61 Changed 2 months ago by Volker Braun

Status: positive_review → needs_work

See patchbot for failures

### comment:62 Changed 2 months ago by git

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

 ​c4aab9f `32686: Remove unused imports and variables`

### comment:63 Changed 2 months ago by Jing Guo

Status: needs_work → needs_review

Let the patch bot run.

### comment:64 Changed 2 months ago by git

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

 ​10df9a6 `32686: Correct example outputs in various files`

### comment:65 Changed 2 months ago by git

Commit: 10df9a648550ddf79315e9a6c9843eed01415d08 → c053c2ac5367b08f553d6dd3d4fa86dec14bc09d

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

 ​c053c2a `32686: Format according to lint result`

### comment:66 Changed 2 months ago by Jing Guo

Status: needs_review → positive_review

### comment:67 Changed 7 weeks ago by Volker Braun

Branch: u/gh-guojing0/points → c053c2ac5367b08f553d6dd3d4fa86dec14bc09d → fixed positive_review → closed
Note: See TracTickets for help on using tickets.