Another error in height_difference_bound

[guojing0]

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)

Depends on #34175

CC: @bhutz @EnderWannabe

Component: dynamics

Keywords: gsoc2022

Author: Jing Guo

Branch/Commit: 97ae98d

Reviewer: Ben Hutz

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

[bhutz]

comment:1

It may makes sense to first implement a height function for polynomials and then use that height function in height_difference_bound

[guojing0]

Commit: f8df808

[guojing0]

Branch: u/gh-guojing0/33972_height_diff_bound

[guojing0]

Dependencies: #34060

[guojing0]

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`

[guojing0]

Changed branch from u/gh-guojing0/33972_height_diff_bound to u/gh-guojing0/33972_height_bound

[guojing0]

Changed commit from f8df808 to ebaa377

[guojing0]

Changed commit from ebaa377 to a5e23b8

[guojing0]

comment:6

Update with latest code from polynomial height.

---

New commits:

c1b22a1	34060: initial implementation of heights for polynomials
d5aad00	34060: code cleanup and QQbar fixes
ad991a3	34060: Number field and `prec` examples
a5e23b8	33971: Commit with latest polynomial height code

[guojing0]

Changed branch from u/gh-guojing0/33972_height_bound to u/gh-guojing0/33972_hdb

[guojing0]

comment:7

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

[bhutz]

comment:8

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.

[bhutz]

Reviewer: Ben Hutz

[sagetrac-git]

Changed commit from a5e23b8 to a3af7ba

[sagetrac-git]

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

31e2b34	temp example
a3af7ba	33072: Works for most tests

[sagetrac-git]

Changed commit from a3af7ba to 2aff55c

[sagetrac-git]

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

913fe15	34175: global_height returns zero for zero poly
2aff55c	33972: Fix `height_difference_bound`

[guojing0]

Changed dependencies from #34060 to #34175

[sagetrac-git]

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

b8a2b44	34175: Return zero as real of specific precision
1ceb3d6	Merge branch 'zero_height' into height_bound

[sagetrac-git]

Changed commit from 2aff55c to 1ceb3d6

[bhutz]

comment:13

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.

[vbraun]

comment:14

**********************************************************************
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
----------------------------------------------------------------------

[bhutz]

comment:15

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.

[guojing0]

Changed commit from 1ceb3d6 to 97ae98d

[guojing0]

Changed branch from u/gh-guojing0/33972_hdb to u/gh-guojing0/33972_stable

[guojing0]

comment:16

Build and pass all tests on the new branch based on the latest develop branch.

---

New commits:

97ae98d

33972 final version

[bhutz]

comment:17

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.

[vbraun]

Changed branch from u/gh-guojing0/33972_stable to 97ae98d