Opened 14 months ago

Last modified 12 days ago

#32292 needs_review enhancement

Reduction of Point Clusters

Reported by: Alexander Galarraga Owned by:
Priority: minor Milestone: sage-9.8
Component: algebraic geometry Keywords: gsoc2021
Cc: Ben Hutz Merged in:
Authors: Alexander Galarraga Reviewers: Ben Hutz
Report Upstream: N/A Work issues:
Branch: u/gh-EnderWannabe/cluster_reduction (Commits, GitHub, GitLab) Commit: 59814a8557cfb7136a54419495da2315a697458a
Dependencies: Stopgaps:

Status badges

Description

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.

Change History (27)

comment:1 Changed 14 months ago by Alexander Galarraga

Branch: u/gh-EnderWannabe/cluster_reduction

comment:2 Changed 14 months ago by Ben Hutz

Commit: 6c0f68228699a0643e43de0c83539612ae4b0c8c

A couple comments here.

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

6c0f68232292: initial commit with code and docs

comment:3 Changed 14 months ago by git

Commit: 6c0f68228699a0643e43de0c83539612ae4b0c8cab7d522a1504dfe3f4ca51dd175fa91ea5dea824

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

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

comment:4 in reply to:  2 Changed 14 months ago by Alexander Galarraga

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

comment:5 Changed 14 months ago by Ben Hutz

Reviewers: Ben Hutz
  • 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

comment:6 Changed 14 months ago by git

Commit: ab7d522a1504dfe3f4ca51dd175fa91ea5dea824bd5ac381f8b7e4f28ff9a15e8fa3dcfc73e15a09

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

f26553832292: fixes for docs and functionality
bd5ac3832292: added height check

comment:7 in reply to:  5 Changed 14 months ago by Alexander Galarraga

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 eB1, which is also symmetric.

comment:8 Changed 14 months ago by git

Commit: bd5ac381f8b7e4f28ff9a15e8fa3dcfc73e15a09cffe758cba2146eeceb507db59167428243cc662

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

cffe75832292: added copyright

comment:9 Changed 14 months ago by Alexander Galarraga

Status: newneeds_review

comment:10 Changed 14 months ago by Matthias Köppe

Milestone: sage-9.4sage-9.5

comment:11 Changed 14 months ago by Ben Hutz

Status: needs_reviewneeds_work

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

comment:12 Changed 14 months ago by git

Commit: cffe758cba2146eeceb507db59167428243cc66212f721fbe68e38ee4763ba5626057a4439b9638a

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

016dd1eMerge branch 'u/gh-EnderWannabe/cluster_reduction' of git://trac.sagemath.org/sage into cluster_reduce
12f721f32292: fixed embedding parameter

comment:13 Changed 14 months ago by git

Commit: 12f721fbe68e38ee4763ba5626057a4439b9638a994868566fe4385ba9e44fdc796e69041285c78b

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

3a3b52732292: added documentation
994868532292: updated error message

comment:14 Changed 14 months ago by Alexander Galarraga

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?

comment:15 Changed 14 months ago by Alexander Galarraga

Status: needs_workneeds_review

comment:16 Changed 14 months ago by Ben Hutz

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.

comment:17 Changed 14 months ago by git

Commit: 994868566fe4385ba9e44fdc796e69041285c78bd2e6555123de257efe5defe14811a175c829dc8f

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

d2e655532292: changed embedding parameter

comment:18 Changed 14 months ago by Ben Hutz

Status: needs_reviewpositive_review

comment:19 Changed 14 months ago by Ben Hutz

Status: positive_reviewneeds_work

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

src/sage/schemes/projective/reduce_cluster.py

comment:20 Changed 14 months ago by git

Commit: d2e6555123de257efe5defe14811a175c829dc8f77da46d2f628ca30bae3678b3355815b86cf9eab

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

77da46d32292: fixing failing tests

comment:21 Changed 14 months ago by Alexander Galarraga

Status: needs_workneeds_review

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

comment:22 Changed 14 months ago by Ben Hutz

Status: needs_reviewneeds_work

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

comment:23 Changed 13 months ago by git

Commit: 77da46d2f628ca30bae3678b3355815b86cf9eab59814a8557cfb7136a54419495da2315a697458a

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

59814a832292: fixed long test

comment:24 Changed 13 months ago by Alexander Galarraga

Status: needs_workneeds_review

comment:25 Changed 10 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:26 Changed 6 months ago by Matthias Köppe

Milestone: sage-9.6sage-9.7

comment:27 Changed 12 days ago by Matthias Köppe

Milestone: sage-9.7sage-9.8
Note: See TracTickets for help on using tickets.