Reduction of Point Clusters

[EnderWannabe]

In https://arxiv.org/abs/0909.2808, Stoll proves that there exists a minimal representative of a point cluster. A point cluster is a formal sum of points of projective space. Here, minimal means that the representative minimizes the convariant he defines.

This ticket aims to add functions to find an approximation of the minimal representative. Such an approximation is useful as it can be used to reduce projective subschemes of dimension less than 1. We add a method to projective subschemes which implements such a reduction.

CC: @bhutz

Component: algebraic geometry

Keywords: gsoc2021

Author: Alexander Galarraga

Branch/Commit: u/gh-EnderWannabe/cluster_reduction @ 59814a8

Reviewer: Ben Hutz

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

[EnderWannabe]

Branch: u/gh-EnderWannabe/cluster_reduction

[bhutz]

Commit: 6c0f682

[bhutz]

comment:2

A couple comments here.

• Reduction theory of point clusters in projective space is published: https://ems.press/journals/ggd/articles/4454

• subschemes of dimension less than 1 why not say dimension 0. If there are no points it doesn't work either...

• need a statement that this is not necessarily the smallest possible coefficients, just one that corresponds to the minimal covariant (and there could be others)

• We create a subscheme of dimension 1 with large coefficients and reduce -> dimension 0

• This one gets the False return in Magma and a different value the this function. What is happening with it?

P.<x,y>=ProjectiveSpace(QQ,1)
f=DynamicalSystem([23454*x^2 + 234087*y^2, 234729384*y^2])
X=f.periodic_points(1,return_scheme=True)
print(X)
X.reduce_coefficients(return_transformation=True)

• Here is a P3 example

#long time
P.<x,y,z,w>=ProjectiveSpace(QQ, 3)
X = P.subscheme([2342*x^2*y - 23744*x*y^2 + 2234398*y^2*w - 239874234*x*w^2,\
  223487*x*y^2 + 2342*x^2*z - 23234975*x*z^2 + 2234398*y*z*w,\
  2342*x^2*w - 23284*x*w^2 + 2234398*y*w^2,\
  223487*y^3 + 23744*y^2*z - 23234975*y*z^2 + 239874234*z*w^2,\
  23744*y^2*w - 23284*y*w^2 + 239874234*w^3,\
  -223487*y^2*w + 23234975*z^2*w - 23284*z*w^2])
X.reduce_coefficients(return_transformation=True)

---

New commits:

6c0f682

32292: initial commit with code and docs

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 6c0f682 to ab7d522

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

5254a5e	Merge branch 'u/gh-EnderWannabe/cluster_reduction' of git://trac.sagemath.org/sage into cluster_reduce
ab7d522	32292: added example and fixed wording

[EnderWannabe]

comment:4

Replying to @bhutz:

This one gets the False return in Magma and a different value the this function. What is happening with it?

Not sure what is happening in your local Magma. Running reduce cluster on the points defined by that scheme on the online Magma calculator gives the correct output

C := ComplexField(30);
list := [Vector([C!0.000997263398969287822568751566512409423879206685727301710349110387118173172038025883370782563646410577176913432551825758831818069949792437117084439457231, C!1.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]),
Vector([C!1.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000, C!0.000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000]),
Vector([C!10008.0737021482152542987724683423193919139324779178985653562584408614726925200998985307807376850751358866855501267311729120257678237821863037511663640, C!1.00000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000])];
ReduceCluster(list);

[bhutz]

comment:5

• If you run the example from the equations rather than the points, you get the False

P1<x,y> := ProjectiveSpace(Rationals(), 1);
X:=Cluster(P1,[23454*x^2*y - 234729384*x*y^2 + 234087*y^3]);
ReduceCluster(X);

If you run it with the points Magma, is producing the same output as this function. I wonder if the False, is just noting that the new version has larger coefficients so you're better off with the identity?

--

• I looked through the code and had a few more comments.

• name: What do you think about reduced_form() so that it matches the other function (in rings/polynomial/multi_polynomial.pyx)

• 1440, 1472 point cluster is a Magma term -> dimension zero scheme is more familiar to our users

• period at end of lines 1460, 1464

• 1475. grammer: Seems like that transformation is referencing representative, which is not right. Need to re-word this a little bit
• 1548. example has no output
• 1551. Scheme must be dimension 0
• 1552. do no need the extra variable subscheme (just use self)

• 1561 output description says tuple, but you are simple returning two objects

• reduce_cluster.py

• file needs full header

  • author
  • copyright
  • GPL

• no camelcase for function names. Need to change throughout code and documentation

• line 7,31. end citation with underscore [Sto2009]_

• line 9, 36. The function was adapted from code provided by Stoll.

• line 70. err, isn't S[0] a point. So you just need S[0].codomain().dimension_relative()+1

• line 75 - fails if no embedding

• 76 - do you actually need to coerce the norm to be real?

• 80,83 - [0][0] makes more sense in python

• 86: what is the difference in output when totalcount exits the loop?

• 122 - you have B*pnt and Stoll has pnt*B (whereas 131 you match his order). I'm getting the correct answers either way, which is interesting...

• 128 - need comment here

• line 146, 148, 151 - ending period

• 176 - instead of doing eps**2 for every loop, do that computation once

• need blank line at end of file

[bhutz]

Reviewer: Ben Hutz

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

f265538	32292: fixes for docs and functionality
bd5ac38	32292: added height check

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from ab7d522 to bd5ac38

[EnderWannabe]

comment:7

Replying to @bhutz:

If you run it with the points Magma, is producing the same output as this function. I wonder if the False, is just noting that the new version has larger coefficients so you're better off with the identity?

Added a check to emulate that functionality

• 1548. example has no output

Added output, but I can't quite get the formatting right. Could you take a look?

• 122 - you have B*pnt and Stoll has pnt*B (whereas 131 you match his order). I'm getting the correct answers either way, which is interesting...

Taking a look at it, B is a symmetric matrix. B1 is a symmetrix matrix, and B is e^B1, which is also symmetric.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from bd5ac38 to cffe758

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

cffe758

32292: added copyright

[bhutz]

comment:11

The main issue I've found is the embedding code is not working; both passing in an embedding and letting the code choose one.

• embedding parameter doesn't work

R.<x> = QQ[]
K.<k> = NumberField(x^2 + 1)
P.<x,y,z> = ProjectiveSpace(K, 2)
emb=K.embeddings(CC)[0]
X = P.subscheme([2141136680*x^2 - 27173976948*x*y + 86218809624*y^2 - 3237154682*x*z + 20541978363*y*z + 1223552253*z^2, \
                      (-23886292125*k + 10098628775)*x^2 + (303150593245*k - 128165707435)*x*y \
                      + (-961851694100*k + 406650470284)*y^2 + (36113395312*k - 15267989043)*x*z \
                      + (-229164852285*k + 96886055543)*y*z + (-13649851075*k + 5770869853)*z^2, \
                      453608122027250*x^3 - 8635374873437055*x^2*y + 54797445624349105*x*y^2 \
                      - 115909272072050820*y^3 - 1028706119154993*x^2*z + 13055708282282128*x*y*z \
                      - 41423764177605297*y^2*z + 777643541637373*x*z^2 - 4934687875458069*y*z^2 - 195951485913414*z^3])
X.reduced_form(embedding=emb)

• same is true when your code picks the embedding

R.<x> = QQ[]
K.<k> = NumberField(x^4 + 1)
P.<x,y,z> = ProjectiveSpace(K, 2)
X = P.subscheme([2141136680*x^2 - 27173976948*x*y + 86218809624*y^2 - 3237154682*x*z + 20541978363*y*z + 1223552253*z^2, \
                      (-23886292125*k + 10098628775)*x^2 + (303150593245*k - 128165707435)*x*y \
                      + (-961851694100*k + 406650470284)*y^2 + (36113395312*k - 15267989043)*x*z \
                      + (-229164852285*k + 96886055543)*y*z + (-13649851075*k + 5770869853)*z^2, \
                      453608122027250*x^3 - 8635374873437055*x^2*y + 54797445624349105*x*y^2 \
                      - 115909272072050820*y^3 - 1028706119154993*x^2*z + 13055708282282128*x*y*z \
                      - 41423764177605297*y^2*z + 777643541637373*x*z^2 - 4934687875458069*y*z^2 - 195951485913414*z^3])
X.reduced_form()

• output says tuple as return type -- that is not what you have

• no CamelCase for function names (e.g., MatExp)

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

016dd1e	Merge branch 'u/gh-EnderWannabe/cluster_reduction' of git://trac.sagemath.org/sage into cluster_reduce
12f721f	32292: fixed embedding parameter

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from cffe758 to 12f721f

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 12f721f to 9948685

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

3a3b527	32292: added documentation
9948685	32292: updated error message

[EnderWannabe]

comment:14

The embedding keyword should be fixed now. I switched from using an actual embedding to using complex numbers.

The return type is a tuple when return_transformation is True.

type(X.reduced_form(embedding=emb, return_transformation=True))
<class 'tuple'>

But it isn't when return_transformation is False. Do you think these should both be tuples?

[bhutz]

comment:16

No, I don't think they both need to be tuples.

For the embedding fix. I think you should leave the parameter as an embedding. Passing in a value and calling it embedding is a little off (even though that is how NumberField works). Why don't you just do the same thing as when you choose the embedding yourself; i.e., map all the generators with the user specified embedding.

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 9948685 to d2e6555

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

d2e6555

32292: changed embedding parameter

[bhutz]

comment:19

marked it too soon. There are some tests that are failing in

src/sage/schemes/projective/reduce_cluster.py

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from d2e6555 to 77da46d

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

77da46d

32292: fixing failing tests

[EnderWannabe]

comment:21

Ok, pushed a fix. The latest patchbot failed to build, which is worrying. Hopefully the next one goes through.

[bhutz]

comment:22

Still a doctest failing

File "src/sage/schemes/projective/projective_subscheme.py", line 1559, in sage.schemes.projective.projective_subscheme.AlgebraicScheme_subscheme_projective_field.reduced_form
Failed example:
    X.reduced_form(return_transformation=True) #long time
Expected:
    (
    Closed subscheme of Projective Space of dimension 3 over Rational Field defined by:
      2342*x^2*y - 14376*x*y^2 - 38120*y^3 - 28104*x*y*w + 2320654*y^2*w - 239874234*x*w^2 - 479664156*y*w^2 + 1439245404*w^3,
      223487*x*y^2 + 446974*y^3 + 2342*x^2*z + 9368*x*y*z + 9368*y^2*z - 23234975*x*z^2 - 46469950*y*z^2 - 1340922*y^2*w - 28104*x*z*w + 2178190*y*z*w + 139409850*z^2*w + 84312*z*w^2,
      2342*x^2*w + 9368*x*y*w + 9368*y^2*w - 51388*x*w^2 + 2131622*y*w^2 + 224016*w^3,
      223487*y^3 + 23744*y^2*z - 23234975*y*z^2 + 239874234*z*w^2,
      23744*y^2*w - 23284*y*w^2 + 239874234*w^3,
      -223487*y^2*w + 23234975*z^2*w - 23284*z*w^2
Got:
    (
    Closed subscheme of Projective Space of dimension 3 over Rational Field defined by:                                                                                                
      2342*x^2*y - 14376*x*y^2 - 38120*y^3 - 28104*x*y*w + 2320654*y^2*w - 239874234*x*w^2 - 479664156*y*w^2 + 1439245404*w^3,                                                         
      223487*x*y^2 + 446974*y^3 + 2342*x^2*z + 9368*x*y*z + 9368*y^2*z - 23234975*x*z^2 - 46469950*y*z^2 - 1340922*y^2*w - 28104*x*z*w + 2178190*y*z*w + 139409850*z^2*w + 84312*z*w^2,
      2342*x^2*w + 9368*x*y*w + 9368*y^2*w - 51388*x*w^2 + 2131622*y*w^2 + 224016*w^3,                                                                                                 
      223487*y^3 + 23744*y^2*z - 23234975*y*z^2 + 239874234*z*w^2,                                                                                                                     
      23744*y^2*w - 23284*y*w^2 + 239874234*w^3,                                                                                                                                       
      -223487*y^2*w + 23234975*z^2*w - 23284*z*w^2                                                                                                                                     ,
    <BLANKLINE>
    [ 1  2  0 -6]
    [ 0  1  0  0]
    [ 0  0  1  0]
    [ 0  0  0  1]
    )

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

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

59814a8

32292: fixed long test

[7ed8c4ca-6d56-4ae9-953a-41e42b4ed313]

Changed commit from 77da46d to 59814a8

[mkoeppe]

comment:25

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

[mkoeppe]

Branch has merge conflicts