Opened 6 months ago
Closed 3 months ago
#33972 closed defect (fixed)
Another error in height_difference_bound
Reported by:  Jing Guo  Owned by:  

Priority:  minor  Milestone:  sage9.7 
Component:  dynamics  Keywords:  gsoc2022 
Cc:  Ben Hutz, Alexander Galarraga  Merged in:  
Authors:  Jing Guo  Reviewers:  Ben Hutz 
Report Upstream:  N/A  Work issues:  
Branch:  97ae98d (Commits, GitHub, GitLab)  Commit:  97ae98d43829256ae7b7cfa509c2aa569bcd648d 
Dependencies:  #34175  Stopgaps: 
Description (last modified by )
Similar to #33971, the height of a polynomial is not typically the max of the heights of the coefficients. In this application the height of the polynomial should be the height of the coefficients if they are thought of as a projective point (i.e., the height is independent of scaling). This is sometimes called the "projective" height of a polynomial. However, this function is computing h(g_i)
as the max of the heights of the coefficients of g_i
.
for k in range(N + 1): CoeffPolys = (CR.gen(k) ** D).lift(I) h = max([c.global_height(prec) for g in CoeffPolys for c in (g).coefficients()]) maxh = max(maxh, h)
Change History (18)
comment:1 Changed 6 months ago by
Description:  modified (diff) 

comment:2 Changed 5 months ago by
Branch:  → u/ghguojing0/33972_height_diff_bound 

Commit:  → f8df80820dc7321dc9b18c9644c3b8315999670b 
comment:3 Changed 5 months ago by
Dependencies:  → #34060 

comment:4 Changed 5 months ago by
Branch:  u/ghguojing0/33972_height_diff_bound → u/ghguojing0/33972_height_bound 

Commit:  f8df80820dc7321dc9b18c9644c3b8315999670b → ebaa377df21f419faa36f86c825ce8af8cb85aef 
New commits:
212ce1f  polynomial_element.pyx: First version of `global_height`

c642890  multi_polynomial_libsingular.pyx: `global_height`

0c6a176  More examples

c2242cb  Move `import` stmts to top and correct doc

4ac23b8  remove `QQbar`

a94e199  local_height and local_height_arch for polys

4f4fe17  Correct doc

ebaa377  Replace incorrect code with `global_height`

comment:5 Changed 5 months ago by
Status:  new → needs_review 

comment:6 Changed 5 months ago by
Branch:  u/ghguojing0/33972_height_bound → u/ghguojing0/33972_hdb 

Commit:  ebaa377df21f419faa36f86c825ce8af8cb85aef → a5e23b81d90ed9b9d893e6cf11c8b608ecaef356 
comment:7 Changed 5 months ago by
Only failure (with actual return value 2.9957322...
):
sage: P.<x,y> = ProjectiveSpace(QQ, 1) sage: f = DynamicalSystem([5*x^2 + 3*x*y , y^2 + 3*x^2]) sage: f.height_difference_bound(prec=100) 5.3375380797013179737224159274
comment:8 Changed 5 months ago by
Reviewers:  → Ben Hutz 

Status:  needs_review → needs_work 
This change is wrong:
 CR = f.domain().coordinate_ring()  I = CR.ideal(f.defining_polynomials())  maxh = 0  for k in range(N + 1):  CoeffPolys = (CR.gen(k) ** D).lift(I)  h = max([c.global_height(prec) for g in CoeffPolys for c in (g).coefficients()])  maxh = max(maxh, h)  L = R((N + 1) * binomial(N + D  d, D  d)).log() + maxh + L = R((N + 1) * binomial(N + D  d, D  d)).log() + f.global_height(prec)
The error of the existing code is the line
h = max([c.global_height(prec) for g in CoeffPolys for c in (g).coefficients()])
What is wrong is that it is taking the height of g to be the max of the height of its coefficients. You still need to take maxh to be the max of the heights of the CoeffPolys?, but the correction is to use the new height code (#34060) to compute the heights of each g.
comment:9 Changed 5 months ago by
Commit:  a5e23b81d90ed9b9d893e6cf11c8b608ecaef356 → a3af7bab11fb37afa52b47e08cf67441623777d0 

comment:10 Changed 5 months ago by
Commit:  a3af7bab11fb37afa52b47e08cf67441623777d0 → 2aff55c8787f735d621387e729adf847710e749d 

comment:11 Changed 5 months ago by
Dependencies:  #34060 → #34175 

Status:  needs_work → needs_review 
comment:12 Changed 5 months ago by
Commit:  2aff55c8787f735d621387e729adf847710e749d → 1ceb3d6da2e2ad209971436ab5bb0a059166a198 

comment:13 Changed 4 months ago by
Status:  needs_review → positive_review 

This looks fine at this point. The difference in the examples is because of correcting the height of the g polynomials. They are monomials in these examples, so have (logarithmic) height 0 rather than the height of the coefficient.
So I'll mark this positive modulo any issues that show up when the dependency gets merged.
comment:14 Changed 4 months ago by
Status:  positive_review → needs_work 

********************************************************************** File "src/sage/dynamics/arithmetic_dynamics/projective_ds.py", line 2116, in sage.dynamics.arithmetic_dynamics.projective_ds.?.height_difference_bound Failed example: f.height_difference_bound() Expected: 11.0020998412042 Got: 10.3089526606443 ********************************************************************** File "src/sage/dynamics/arithmetic_dynamics/projective_ds.py", line 2128, in sage.dynamics.arithmetic_dynamics.projective_ds.?.height_difference_bound Failed example: f.height_difference_bound() Expected: 11.0020998412042 Got: 11.3683039374269 q^CKilling test src/sage/dynamics/arithmetic_dynamics/projective_ds.py  Doctests interrupted: 0/1 files tested 
comment:15 Changed 4 months ago by
I'm also getting these errors on a clean branch. The first one is in the example
sage: P.<x,y,z> = ProjectiveSpace(ZZ, 2) sage: f = DynamicalSystem_projective([4*x^2 + 100*y^2, 210*x*y, 10000*z^2]) sage: f.height_difference_bound() 11.0020998412042 sage: f.normalize_coordinates() sage: f.height_difference_bound() 10.3089526606443
It doesn't make sense to keep .normalize in here anymore as the height of the polynomials is independent of the normalization. The 10.308... is the correct value. So condense this example down to a single (correct) value.
The second failure is just the wrong value.
comment:16 Changed 4 months ago by
Branch:  u/ghguojing0/33972_hdb → u/ghguojing0/33972_stable 

Commit:  1ceb3d6da2e2ad209971436ab5bb0a059166a198 → 97ae98d43829256ae7b7cfa509c2aa569bcd648d 
Status:  needs_work → needs_review 
Build and pass all tests on the new branch based on the latest develop
branch.
New commits:
97ae98d  33972 final version

comment:17 Changed 4 months ago by
Status:  needs_review → positive_review 

This looks fine and the tests pass for me.
In the future it's better to edit the existing ticket to fix the issues rather than create a whole new branch that erases the history.
comment:18 Changed 3 months ago by
Branch:  u/ghguojing0/33972_stable → 97ae98d43829256ae7b7cfa509c2aa569bcd648d 

Resolution:  → fixed 
Status:  positive_review → closed 
It may makes sense to first implement a height function for polynomials and then use that height function in height_difference_bound