Opened 12 years ago

Closed 11 years ago

Riemann-Roch computations in the Brill-Noether routines

Reported by: Owned by: malb Oleksandr major 3-1-1 singular-libs 3-1-0 random Oleksandr

Description

David Joyner wrote on [sage-devel]:

```Speaking of pet complaints, can you ask if they will at some point fix the bugs in the Riemann-Roch computations in the Brill-Noether routines?
To be honest, I have not checked them recently but as of a few years
ago they were unreliable. The Sage module sage/coding/ag_codes.py
(from 2006) is waiting for some Singular routines to be fixed I think.
I do not know of an open source correct and functional implementation of any general algorithm to compute a basis for a Riemann-Roch space of a curve over a finite field.
```

Sorry for the vague description, I can ask David for specifics and will also point him to this ticket.

comment:1 Changed 12 years ago by seelisch

Milestone: → Releases 3-1-1 and higher

Please always also assign a milestone!

comment:2 in reply to:  description Changed 12 years ago by bulygin

This is the answer from William Stein to David Joyner: Thanks for the Singular-ish version via evals. I wrote the following pure-Singular version, which you can put in a file "rrbasis.lib" and load into singular with

< "rrbasis.lib";

(or you can just paste it in):

```LIB "brnoeth.lib";
kill X, X2,R,G,LG;
ring R=11,(x,y),lp;
list X = Adj_div(x^7 + y^7 - 1);
def  X2 = NSplaces(1,X);
def  X3 = extcurve(1,X2);
def RR =X3[1][5];
setring RR;
print("POINTS");
print(POINTS);
/* PROBLEM -- this G defined a different divisor every time the
this code is run!!!  Need a way to compute G from a list of points */
intvec G=(10,-1,0,0,9,0,0,0,0,0,0,0,0,0);
def R = X2[1][2];
setring R;
list LG = BrillNoether(G,X2);
print(LG);
```

It gives random answers since the G has a different meaning every time the function is run.

comment:3 Changed 12 years ago by seelisch

Owner: changed from somebody to seelisch

comment:4 follow-up:  5 Changed 12 years ago by seelisch

Resolution: → fixed new → closed

As far as we understand correctly, the problem seems to be that SAGE wants to have stable results when calling this piece of SINGULAR code. But brnoeth.lib works with randomly chosen points.

We suggest to use a random seed, e.g., to pass on the random seed used in SAGE to SINGULAR. This can be done via the SINGULAR command by

system("random", mySeedAsAnInt);

or directly in C using the SINGULAR-internal procedure

srand(mySeedAsAnUnsignedInt);

comment:5 in reply to:  4 Changed 11 years ago by minz <minzlaff@…>

Resolution: fixed closed → reopened

My impression is that the problem lies with Singular. I adapted the example in the description of the corresponding Sage ticket (http://trac.sagemath.org/sage_trac/ticket/8997) and did the following in Singular:

```kill s, C, Ctemp, temp, G, R, LG;

LIB "brnoeth.lib";
int plevel=printlevel;
printlevel=-1;
system("random", 1);

ring s=5,(x,y),lp;
C=NSplaces(1,C);
def R=C[1][2];

# I want to look at the points to be able to define
# the same divisor each time, see below
def Ctemp=extcurve(1,C);
def temp=Ctemp[1][5];
setring temp;
print(POINTS);

setring R;

# adapt the line below according to the ordering of the points
# i always chose the divisor 3(0,-1,1)-1(1,2,1)+10(2,1,1)
intvec G = ;

list LG=BrillNoether(G,C);
LG;

printlevel=plevel;
```

Not only did the bases vary each time I ran this code (even though I fixed the random seed in the sixth line), the resulting bases also had different cardinality (either 0 or 2).

comment:6 Changed 11 years ago by seelisch

Owner: changed from seelisch to ignfar@… reopened → new

comment:7 Changed 11 years ago by ignfar@…

There are two different problems in the proposed example:

(1) In order to compute a basis of L(G) with BrillNoether?, you have to enter a "closed point" of degree 1 (rational) or higher (a class of points conjugated by the Frobenius map). BrillNoether? works so generally, in order to avoid (if you wish) rational points in G, and use all of them to evaluate functions (i.e. in the devisor D).

We knew when we did the program that is very comfortable to write a divisor as 3*(1:1:0)-1(0:0:1) but it is imposible to write in this way a divisor using (for example) a point of degree 2 (well, you can write the coordinates of the conjugated points, but then you have to go to an extension, and this complicates things). Nice expressions have sometimes uncomfortable syntax and programming problems (for example in any normal programming language you have: 3*(1:1:0)-1(0:0:1) ... = (3:3:-1) !! ).

Moreover, a "point" is (much) more than just three homogeneous coordinates. You need local parametrizations in order to carry on with the BrillNoether? algorithm, and then you need to store all this information properly in what we called a "place", inside the suitable "local ring" (in the example of the "ticket", X3[5] contains a list with the local rings, and inside them all the needed local information of the "places").

So the first mistake in the example is that the list POINTS is considered to define G, while the list of "closed points" X3[3] should be considered instead. In the example, there you see that the first two points are of degree 3, and then 12 of degree 1 (rational). Thus, in the proposed example

intvec G=(10,-1,0,0,9,0,0,0,0,0,0,0,0,0);

you are considering a divisor of degree 28. I am (almost) sure that this is not what the example intends? If you still are considering the list POINTS the degree of can change and so the dimension of L(G).

I know that it is tedious, but the right way to do things is to look at the list of closed points X3[3], decide which "places" you want to use (for example, one point of degree 3 and three of degree 1), you have to check in the local rings X3[5][1][1] and X3[5][2][1] (see the help of Adj_div) which are the points you want (you have there the coordinates, the Hamburger-Noether expansions and the local parametrizations), write down which are the position numbers of the points you want (vgr. the point (1:0:1) is the third point of degree one) and identify it in the list X3[3] (vgr. the third point of degree 1, that is (1,3) is in position [5] in that list), so that now you can put the right coefficient in the divisor G (the fifth element of the intvec).

All solutions have pros and cons, and this is the way we decided to proceed. There is too much hidden information involved.

(2) The second problem, the "random" order of the points each time the code is run, I do not know exactly where it comes from. Anyway, it seems a "problem" of randomized general algorithms of Singular, probably from triangulation procedures (triang.lib). It is tedious to check the output each time, but on the other hand the procedure triangMH works efficiently, maybe because of some random choice at some step.

Jose Ignacio Farran - University of Valladolid (one of the authors of the library "brnoeth.lib").

comment:8 Changed 11 years ago by seelisch

Owner: changed from ignfar@… to Oleksandr

comment:9 Changed 11 years ago by Oleksandr

Keywords: random added new → assigned

in case of inactivity (for several months) i would propose to close the ticket

Last edited 11 years ago by Oleksandr (previous) (diff)

comment:11 follow-up:  12 Changed 11 years ago by minz <minzlaff@…>

(1) thanks for the explanations jose! i now understand what goes wrong in the examples.

(2) the line "intvec G = ;" was meant to be completed by hand after looking at POINTS -- which of course I now learned is wrong, one should look at C[3]! -- to define the divisor as in the comment line directly above. sorry for the lack of explanation.

moritz

comment:12 in reply to:  11 Changed 11 years ago by Oleksandr

could you please contribute a correct Singular code for your code example so that everyone could follow?

Oleksandr

comment:13 Changed 11 years ago by Moritz Minzlaff <minzlaff@…>

Here's an example of how I would now proceed:

```LIB "brnoeth.lib";
int plevel=printlevel;
printlevel=-1;

ring s=5,(x,y),lp;
C=NSplaces(1,C);
def R=C[1][2];

# First, I look at the list C[3] relative to which the divisor G
# needs to be defined
C[3];

# The list C[3] contains tuples d,i, where d is the degree of the point and
# i is the index of this point in the list POINTS of the ring C[5][d][1]
# Therefore, I now look at these lists for various d to pick the points I want
def S = C[5][d][1];
setring S;
POINTS;

# I can now define the divisor G by a vector of integers,
# so that the k-th entry denotes the multiplicity of the divisor
# at the i-th point of the list POINTS of C[5][d][1], where
# d,i is the k-th entry of C[3]
intvec G = <SOME SEQUENCE OF INTEGERS>;

setring R;
list LG=BrillNoether(G,C);
LG;
```

comment:14 Changed 11 years ago by Oleksandr

Resolution: → fixed assigned → closed

Besides, the above Moritz's note means that the intvector `G` should have the same size as the list `C[3]`, e.g. in the above case d=1 => `size(G) == 6` and d=6 => `size(G) == 1`