Opened 14 months ago

# Reduction of Point Clusters

Reported by: Owned by: Alexander Galarraga minor sage-9.8 algebraic geometry gsoc2021 Ben Hutz Alexander Galarraga Ben Hutz N/A u/gh-EnderWannabe/cluster_reduction 59814a8557cfb7136a54419495da2315a697458a

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

### comment:1 Changed 14 months ago by Alexander Galarraga

Branch: → u/gh-EnderWannabe/cluster_reduction

### comment:2 follow-up:  4 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:

 ​6c0f682 `32292: initial commit with code and docs`

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

Commit: 6c0f68228699a0643e43de0c83539612ae4b0c8c → ab7d522a1504dfe3f4ca51dd175fa91ea5dea824

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`

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

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 follow-up:  7 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
• 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 a point. So you just need `S.codomain().dimension_relative()+1`
• line 75 - fails if no embedding
• 76 - do you actually need to coerce the norm to be real?
• 80,83 -  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: ab7d522a1504dfe3f4ca51dd175fa91ea5dea824 → bd5ac381f8b7e4f28ff9a15e8fa3dcfc73e15a09

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

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

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

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: bd5ac381f8b7e4f28ff9a15e8fa3dcfc73e15a09 → cffe758cba2146eeceb507db59167428243cc662

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

 ​cffe758 `32292: added copyright`

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

Status: new → needs_review

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

Milestone: sage-9.4 → sage-9.5

### comment:11 Changed 14 months ago by Ben Hutz

Status: needs_review → needs_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)
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: cffe758cba2146eeceb507db59167428243cc662 → 12f721fbe68e38ee4763ba5626057a4439b9638a

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`

### comment:13 Changed 14 months ago by git

Commit: 12f721fbe68e38ee4763ba5626057a4439b9638a → 994868566fe4385ba9e44fdc796e69041285c78b

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

 ​3a3b527 `32292: added documentation` ​9948685 `32292: 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_work → needs_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: 994868566fe4385ba9e44fdc796e69041285c78b → d2e6555123de257efe5defe14811a175c829dc8f

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

 ​d2e6555 `32292: changed embedding parameter`

### comment:18 Changed 14 months ago by Ben Hutz

Status: needs_review → positive_review

### comment:19 Changed 14 months ago by Ben Hutz

Status: positive_review → needs_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: d2e6555123de257efe5defe14811a175c829dc8f → 77da46d2f628ca30bae3678b3355815b86cf9eab

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

 ​77da46d `32292: fixing failing tests`

### comment:21 Changed 14 months ago by Alexander Galarraga

Status: needs_work → needs_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_review → needs_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: 77da46d2f628ca30bae3678b3355815b86cf9eab → 59814a8557cfb7136a54419495da2315a697458a

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

 ​59814a8 `32292: fixed long test`

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

Status: needs_work → needs_review

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

Milestone: sage-9.6 → sage-9.7

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

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