///////////////////////////////////////////////////////////////////////////// version="$Id$"; category="Tropical Geometry"; info=" LIBRARY: realizationMatroidsNC.lib Deciding Relative Realizability for Tropical Curves in 2-Dimensional Matroidal Fans AUTHORS: Anna Lena Birkmeyer, birkmeyer@mathematik.uni-kl.de OVERVIEW: In tropical geometry, one question to ask is the following: given a one-dimensional balanced polyhedral complex C which is set theoretically contained in the tropicalization Trop(Y) of an algebraic variety Y, does there exist a curve X in Y such that Trop(X) = C? This equality of C and Trop(X) denotes an equality of both, the polyhedral complexes Trop(X) and C and their weights on the maximal cones. This library provides procedures deciding relative realizability for tropical curves, i.e. one-dimensional weighted balanced polyhedral complexes, contained in two-dimensional matroidal fans Trop(Y) where Y is a projective plane in K{{t}}^n but I(Y) has generators in K[x]. If Y is a projective plane in (n-1)-dimensional projective space, we consider Trop(Y) in R^n/<1>. PROCEDURES: realizable(I,C); For a given tropical curve C in Trop(Y), where Y = V(I) is a projective plane, this routine returns 1 if C is relatively realizable and -1 if it is not. realizablePoly(I,C); If C is a tropical curve contained in the tropicalization Trop(Y) of the projective plane Y = V(I) such that C is relatively realizable, then this routine returns a polynomial with coefficients in the Puiseux series realizing C. If C is not relatively realizable, the routine returns -1. The routine needs a basering with a parameter which will play the role of t in K{{t}} in the output. "; LIB "qhmoduli.lib"; static proc gcdvector(intvec v) { int i; int ggt = 0; for(i=1;i<=size(v);i++) { ggt = gcd(ggt,v[i]); if( ggt == 1 ) { return(ggt); } } return(ggt); } /////////////////////////////////////////////////////////////////////////////////////////////////////// static proc balanced(list lInput) { int w; int m; int i; int j; list iDirections; if(size(lInput[1])>0) { for(j=1;j<=size(lInput[1]);j++) { if(lInput[1][j][1] == 0) { iDirections = iDirections + list(j); } } m = 0; for(i=1;i<=size(lInput[2]);i++) { if((lInput[2][i][1] == iDirections[1]) or (lInput[2][i][2] == iDirections[1])) { m = m + lInput[3][i]; } } intvec v = m*lInput[1][iDirections[1]]; for(j=2;j<=size(iDirections);j++) { m = 0; for(i=1;i<=size(lInput[2]);i++) { if((lInput[2][i][1] == iDirections[j]) or (lInput[2][i][2] == iDirections[j])) { m = m + lInput[3][i]; } } v = v + m*lInput[1][iDirections[j]]; } int boolean = 1; for(i=3;i<=size(v);i++) { if(v[i] != v[2]) { boolean = 0; } } if(boolean == 1) { return(v[2]); } else { return(0); } } else { return(0); } } //////////////////////////////////////////////////////////////////////////////////////////////////// static proc balancedFan(list L) { int v = 0; int w; int i; int j; if(size(L)>0) { for(j=1;j<=size(L);j++) { v = v + L[j][1]; } int boolean = 1; for(i=2;i<=size(L[1]);i++) { w = 0; for(j=1;j<=size(L);j++) { w = w + L[j][i]; } if(w != v) { boolean = 0; i = size(L[1]); } } if(boolean == 1) { return(v); } else { return(0); } } else { return(0); } } ///////////////////////////////////////////////////////////////////////////////////////////////////// static proc genPoly(int d, int i, int j, int k) { int ii; int ij; int ik = 1; poly f = 0; for(ii=0;ii<=d;ii++) { for(ij=0;ij<=d-ii;ij++) { f = f + a(ik)*x(i)^(d-ii-ij)*x(j)^ij*x(k)^ii; ik = ik + 1; } } return(f); } ///////////////////////////////////////////////////////////////////////////////////////////////////// static proc latticePoints(int d) { int ii; int ij; list L; for(ii=0;ii<=d;ii++) { for(ij=0;ij<=d-ii;ij++) { L = L + list(intvec(d-ii-ij,ij,ii)); } } return(L); } ////////////////////////////////////////////////////////////////////////////////////////////////////// static proc deleteElement(list L, def v) { int i; for(i=1;i<=size(L);i++) { if(L[i] == v) { L = delete(L,i); i = i-1; } } return(L); } ///////////////////////////////////////////////////////////////////////////////////////////////////// static proc prodvar(int n) { int i; poly f = 1; for(i=1;i<=n;i++) { f = f * x(i); } return(f); } ////////////////////////////////////////////////////////////////////////////////////////////////////// static proc lessThan(int i, int j, intvec v, intvec w) { number a = v[i]; number b = v[j]; number c = w[i]; number d = w[j]; if((a/b)<(c/d)) { return(1); } else { return(0); } } ///////////////////////////////////////////////////////////////////////////////////////////////////// static proc sortSlope(int i, int j, list lInput) { int k; int l; intvec v; for(k=1;k i) { P[2][j][1] = P[2][j][1] - 1; } if(P[2][j][2] > i) { P[2][j][2] = P[2][j][2] - 1; } } } i = i-1; } else { //simplify directions if(P[1][i][1] == 0) { if(gcdvector(P[1][i]) != 1) { k = gcdvector(P[1][i]); for(j=1;j<=size(P[2]);j++) { if((P[2][j][1] == i) or (P[2][j][2] == i)) { P[3][j] = P[3][j] * k; } } P[1][i] = P[1][i] div k; } } } } //check whether or not directions/vertices are contained several times for(i=1;i<=size(P[1]);i++) { for(j=i+1;j<=size(P[1]);j++) { if(P[1][i] == P[1][j]) { for(l=1;l<=size(P[2]);l++) { if(P[2][l][1] == j) { P[2][l][1] = i; } else { if(P[2][l][1] > j) { P[2][l][1] = P[2][l][1] - 1; } } if(P[2][l][2] == j) { P[2][l][2] = i; } else { if(P[2][l][2] > j) { P[2][l][2] = P[2][l][2] - 1; } } } P[1] = delete(P[1],j); j = j-1; } } } //get rid of connections which do not exist anymore for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == P[2][i][2]) { P[2] = delete(P[2],i); P[3] = delete(P[3],i); i = i-1; } } //sort the vertices and directions contained in a contracted face into lists for(i=1;i<=size(P[1]);i++) { v = P[1][i]; w = v[2..4]; if(ismultiple(w,intvec(1,0,0))) { if(P[1][i][1] == 1) { iVertices[1] = iVertices[1] + list(i); } } if(ismultiple(w,intvec(0,1,0))) { if(P[1][i][1] == 1) { iVertices[2] = iVertices[2] + list(i); } } if(ismultiple(w,intvec(0,0,1))) { if(P[1][i][1] == 1) { iVertices[3] = iVertices[3] + list(i); } } } //sort the vertices for(i=size(iVertices[1]);i>0;i--) { for(j=1;j P[1][iVertices[1][j+1]][2]) { k = iVertices[1][j]; iVertices[1][j] = iVertices[1][j+1]; iVertices[1][j+1] = k; } } } for(i=size(iVertices[2]);i>0;i--) { for(j=1;j P[1][iVertices[2][j+1]][3]) { k = iVertices[2][j]; iVertices[2][j] = iVertices[2][j+1]; iVertices[2][j+1] = k; } } } for(i=size(iVertices[3]);i>1;i--) { for(j=1;j P[1][iVertices[3][j+1]][4]) { k = iVertices[3][j]; iVertices[3][j] = iVertices[3][j+1]; iVertices[3][j+1] = k; } } } //if the direction e_i starts at the vertex neq the last one, correct it for(i=1;i<=size(P[2]);i++) { if(P[1][P[2][i][1]] == intvec(0,1,0,0)) { L = isContained(iVertices[1],P[2][i][2]); if((L[1] == 1) and (L[2] != size(iVertices[1]))) { P[2][i][2] = iVertices[1][size(iVertices[1])]; for(j=L[2];j P[2][i][2]) { k = P[2][i][1]; P[2][i][1] = P[2][i][2]; P[2][i][2] = k; } } for(i=1;i i) { P[2][j][1] = iVertices[l][i-1]; if(P[2][j][1] > k) { P[2][j][1] = P[2][j][1] - 1; } } else { P[2] = delete(P[2],j); P[3] = delete(P[3],j); j = j-1; } } else { if(P[2][j][1] > k) { P[2][j][1] = P[2][j][1] - 1; } } if(P[2][j][2] == k) { if(isContained(iVertices[l],P[2][j][1])[2] > i) { P[2][j][2] = iVertices[l][i-1]; if(P[2][j][2] > k) { P[2][j][2] = P[2][j][2] - 1; } } else { P[2] = delete(P[2],j); P[3] = delete(P[3],j); j = j-1; } } else { if(P[2][j][2] > k) { P[2][j][2] = P[2][j][2] - 1; } } } iVertices[l] = delete(iVertices[l],i); i = i-1; P[1] = delete(P[1],k); } } } //delete all 2-valent vertices with at least one bounded edge connected to it for(i=1;i<=size(P[1]);i++) { boolean = 0; if(P[1][i][1] == 1) { v = 0; for(j=1;j<=size(P[2]);j++) { if((P[2][j][1] == i) or (P[2][j][2] == i)) { v = v,j; if(P[1][P[2][j][1]][1] + P[1][P[2][j][2]][1] == 2) { boolean = 1; } } } if((size(v) == 3) and (boolean == 1)) { //2-valent vertex, delete it if((P[2][v[2]][1] == i) and (P[2][v[3]][1] == i)) { P[2][v[2]][1] = P[2][v[3]][2]; } if((P[2][v[2]][1] == i) and (P[2][v[3]][2] == i)) { P[2][v[2]][1] = P[2][v[3]][1]; } if((P[2][v[2]][2] == i) and (P[2][v[3]][1] == i)) { P[2][v[2]][2] = P[2][v[3]][2]; } if((P[2][v[2]][2] == i) and (P[2][v[3]][2] == i)) { P[2][v[2]][2] = P[2][v[3]][1]; } P[2] = delete(P[2],v[3]); P[3] = delete(P[3],v[3]); for(j=1;j<=size(P[2]);j++) { if(P[2][j][1] > i) { P[2][j][1] = P[2][j][1] - 1; } if(P[2][j][2] > i) { P[2][j][2] = P[2][j][2] - 1; } } P[1] = delete(P[1],i); i = i-1; } } } return(P); } //////////////////////////////////////////////////////////////////////////////////////////////// static proc newtonPolytope(list P) { list newton; list directions; list iDirections; list verToDo; list connections; list iConnections; list possVert; list L; list K; list H; int m; int n; int numb; int i; int j; int k; int l; int d = balanced(P); int index = 0; intvec v; intvec w; intvec trans; for(i=1;i<=size(P[1]);i++) { if(P[1][i][1] == 0) { directions = directions + list(intvec(P[1][i][2],P[1][i][3],P[1][i][4])); iDirections = iDirections + list(i); } else { verToDo = verToDo + list(i); } } //compute rezession fan: add up multiplicities for(i=1;i<=size(directions);i++) { m = 0; numb = 0; for(j=1;j<=size(P[2]);j++) { if((P[2][j][1] == iDirections[i]) or (P[2][j][2] == iDirections[i])) { m = m + P[3][j]; numb = numb + 1; } } directions[i] = directions[i]*m; if(numb == 1) { index = i; } } if(index != 0) { L = list(); k = iDirections[index]; //find the vertex to which this directions is connected to for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == k) { l = P[2][i][2]; } if(P[2][i][2] == k) { l = P[2][i][1]; } } verToDo = deleteElement(verToDo,l); for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == l) { v = P[1][P[2][i][2]]; if(v[1] == 1) { connections = connections + list(P[2][i]); iConnections = iConnections + list(i); verToDo = deleteElement(verToDo,P[2][i][2]); w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } if(P[2][i][2] == l) { v = P[1][P[2][i][1]]; if(v[1] == 1) { connections = connections + list(intvec(P[2][i][2],P[2][i][1])); iConnections = iConnections + list(i); verToDo = deleteElement(verToDo,P[2][i][1]); w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } } trans = newtonPosition(directions,intvec(P[1][k][2],P[1][k][3],P[1][k][4])); newton = newton + list(list(newtonPart(L,intvec(P[1][k][2],P[1][k][3],P[1][k][4]),trans),intvec(P[1][l][2],P[1][l][3],P[1][l][4]))); } else //no direction appears only once, so we have to find a first position { k = 1; //take any direction while((P[1][k][1] != 0) && (k <= size(P[1]))) { k = k+1; } if(k > size(P[1])) { return(-3); } possVert = list(); for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == k) { possVert = possVert + list(P[2][i][2]); } if(P[2][i][2] == k) { possVert = possVert + list(P[2][i][1]); } } //find maximal value on these vertices v = intvec(P[1][k][2],P[1][k][3],P[1][k][4]); v = v - v[3]*intvec(1,1,1); w = P[1][possVert[1]]; m = w[2]*v[2] - w[3]*v[1]; l = 1; for(i=2;i<=size(possVert);i++) { w = P[1][possVert[i]]; n = w[2]*v[2] - w[3]*v[1]; if(n > m) { m = n; l = i; } } //the vertex corresponding to the start of direction P[1][k] is possVert[l] l = possVert[l]; L = list(); verToDo = deleteElement(verToDo,l); for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == l) { v = P[1][P[2][i][2]]; if(v[1] == 1) { connections = connections + list(P[2][i]); iConnections = iConnections + list(i); verToDo = deleteElement(verToDo,P[2][i][2]); w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } if(P[2][i][2] == l) { v = P[1][P[2][i][1]]; if(v[1] == 1) { connections = connections + list(intvec(P[2][i][2],P[2][i][1])); iConnections = iConnections + list(i); verToDo = deleteElement(verToDo,P[2][i][1]); w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } } trans = newtonPosition(directions,intvec(P[1][k][2],P[1][k][3],P[1][k][4])); newton = newton + list(list(newtonPart(L,intvec(P[1][k][2],P[1][k][3],P[1][k][4]),trans),intvec(P[1][l][2],P[1][l][3],P[1][l][4]))); } //first part is fixed, find recursively the other parts while(size(connections) > 0) { k = connections[1][1]; l = connections[1][2]; connections = delete(connections,1); iConnections = delete(iConnections,1); L = list(); for(i=1;i<=size(P[2]);i++) { if(P[2][i][1] == l) { v = P[1][P[2][i][2]]; if(v[1] == 1) { K = isContained(verToDo,P[2][i][2]); if(K[1] == 1) { connections = connections + list(P[2][i]); iConnections = iConnections + list(i); verToDo = delete(verToDo,K[2]); } w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } if(P[2][i][2] == l) { v = P[1][P[2][i][1]]; if(v[1] == 1) { K = isContained(verToDo,P[2][i][1]); if(K[1] == 1) { connections = connections + list(intvec(P[2][i][2],P[2][i][1])); iConnections = iConnections + list(i); verToDo = delete(verToDo,K[2]); } w = v - P[1][l]; w = intvec(w[2],w[3],w[4]); w = w - Min(w)*intvec(1,1,1); w = w div gcdvector(w); L = L + list(P[3][i]*w); } else { L = L + list(P[3][i]*intvec(v[2],v[3],v[4])); } } } for(i=1;i<=size(newton);i++) { if(newton[i][2] == intvec(P[1][k][2],P[1][k][3],P[1][k][4])) { H = newton[i][1]; } } v = P[1][l] - P[1][k]; v = intvec(v[2],v[3],v[4]); v = v - Min(v)*intvec(1,1,1); v = v div gcdvector(v); v = v*P[3][iDirections[1]]; trans = newtonTranslation(H,v); v = -v; v = v - Min(v)*intvec(1,1,1); v = v div gcdvector(v); v = v*P[3][iDirections[1]]; newton = newton + list(list(newtonPart(L,v,trans),intvec(P[1][l][2],P[1][l][3],P[1][l][4]))); } if(size(verToDo) > 0) { newton = list(); k = 1; //take any direction, the only appearing one (up to sign) while((P[1][k][1] != 0) && (k <= size(P[1]))) { k = k+1; } if(k > size(P[1])) { return(-3); } possVert = list(); for(i=1;i<=size(P[1]);i++) { if(P[1][i][1] == 1) { possVert = possVert + list(i); } } //sort the vertices with respect to this direction v = intvec(P[1][k][2],P[1][k][3],P[1][k][4]); v = v - v[3]*intvec(1,1,1); for(i=1;i l) { P[2][i2][1] = P[2][i2][1] - 1; } if(P[2][i2][2] == l) { P[2] = delete(P[2],i2); P[3] = delete(P[3],i2); i2 = i2-1; } else { if(P[2][i2][2] > l) { P[2][i2][2] = P[2][i2][2] - 1; } } } } P[1] = delete(P[1],l); l = l-1; } else { if((P[1][l][1] == 0) and (gcdvector(intvec(P[1][l][2],P[1][l][3],P[1][l][4])) > 1)) { i3 = gcdvector(intvec(P[1][l][2],P[1][l][3],P[1][l][4])); for(i2=1;i2<=size(P[2]);i2++) { if((P[2][i2][1] == l) or (P[2][i2][2] == l)) { P[3][i2] = P[3][i2] * i3; } } P[1][l][2] = P[1][l][2] div i3; P[1][l][3] = P[1][l][3] div i3; P[1][l][4] = P[1][l][4] div i3; } } } P = pushForward(P); //collect the conditions coming from the rezession fan S1 = list(); S2 = list(); S3 = list(); for(l=1;l<=size(P[2]);l++) { if((P[1][P[2][l][1]][1] == 0) and (P[1][P[2][l][1]][2] != 0) and (P[1][P[2][l][1]][3] != 0)) { S3 = S3 + list(P[3][l]*intvec(P[1][P[2][l][1]][2],P[1][P[2][l][1]][3],P[1][P[2][l][1]][4])); } if((P[1][P[2][l][2]][1] == 0) and (P[1][P[2][l][2]][2] != 0) and (P[1][P[2][l][2]][3] != 0)) { S3 = S3 + list(P[3][l]*intvec(P[1][P[2][l][2]][2],P[1][P[2][l][2]][3],P[1][P[2][l][2]][4])); } if((P[1][P[2][l][1]][1] == 0) and (P[1][P[2][l][1]][3] != 0) and (P[1][P[2][l][1]][4] != 0)) { S1 = S1 + list(P[3][l]*intvec(P[1][P[2][l][1]][2],P[1][P[2][l][1]][3],P[1][P[2][l][1]][4])); } if((P[1][P[2][l][2]][1] == 0) and (P[1][P[2][l][2]][3] != 0) and (P[1][P[2][l][2]][4] != 0)) { S1 = S1 + list(P[3][l]*intvec(P[1][P[2][l][2]][2],P[1][P[2][l][2]][3],P[1][P[2][l][2]][4])); } if((P[1][P[2][l][1]][1] == 0) and (P[1][P[2][l][1]][2] != 0) and (P[1][P[2][l][1]][4] != 0)) { S2 = S2 + list(P[3][l]*intvec(P[1][P[2][l][1]][2],P[1][P[2][l][1]][3],P[1][P[2][l][1]][4])); } if((P[1][P[2][l][2]][1] == 0) and (P[1][P[2][l][2]][2] != 0) and (P[1][P[2][l][2]][4] != 0)) { S2 = S2 + list(P[3][l]*intvec(P[1][P[2][l][2]][2],P[1][P[2][l][2]][3],P[1][P[2][l][2]][4])); } } //add up same directions S1 = simplifyList(S1); S2 = simplifyList(S2); S3 = simplifyList(S3); //sort the lists S1 = sortSlope(3,2,S1); S2 = sortSlope(1,3,S2); S3 = sortSlope(2,1,S3); //find conditions from S1 i_start = 0; for(l=1;l<=size(S1);l++) { i_start = i_start + S1[l][2]; } //find starting point w = intvec(0,i_start); for(i2=1;i2<=size(S1);i2++) { w[1] = w[1] + S1[i2][3]; w[2] = w[2] - S1[i2][2]; v = zerovec; v[j] = S1[i2][2]; v[k] = S1[i2][3]; i_w = S1[i2][2]*w[1] + S1[i2][3]*w[2]; g = jet(h,i_w-1,v); F = coef(g,prodvar(n)); for(i3=1;i3<=ncols(F);i3++) { E = E + ideal(F[2,i3]); expon = leadexp(F[1,i3]); lattice = deleteElement(lattice,intvec(expon[i],expon[j],expon[k])); } } //find conditions from S2 i_start = 0; for(l=1;l<=size(S2);l++) { i_start = i_start + S2[l][3]; } //find starting point w = intvec(i_start,0); for(i2=1;i2<=size(S2);i2++) { w[1] = w[1] - S2[i2][3]; w[2] = w[2] + S2[i2][1]; v = zerovec; v[i] = S2[i2][1]; v[k] = S2[i2][3]; i_w = S2[i2][3]*w[2] + S2[i2][1]*w[1]; g = jet(h,i_w-1,v); F = coef(g,prodvar(n)); for(i3=1;i3<=ncols(F);i3++) { E = E + ideal(F[2,i3]); expon = leadexp(F[1,i3]); lattice = deleteElement(lattice,intvec(expon[i],expon[j],expon[k])); } } //find conditions from S3 i_start = 0; for(l=1;l<=size(S3);l++) { i_start = i_start + S3[l][1]; } //find starting point w = intvec(0,i_start); for(i2=1;i2<=size(S3);i2++) { w[1] = w[1] + S3[i2][2]; w[2] = w[2] - S3[i2][1]; v = zerovec; v[i] = S3[i2][1]; v[j] = S3[i2][2]; i_w = S3[i2][2]*w[2] + S3[i2][1]*w[1]; g = jet(h,i_w-1,v); F = coef(g,prodvar(n)); for(i3=1;i3<=ncols(F);i3++) { E = E + ideal(F[2,i3]); expon = leadexp(F[1,i3]); lattice = deleteElement(lattice,intvec(expon[i],expon[j],expon[k])); } } E = std(E); //collect the conditions on the valuations //i,j,k; //h; newton = newtonPolytope(P); //newton; for(i2=1;i2<=size(newton);i2++) { lattice = deleteElement(lattice,newton[i2][1][1]); val1 = list(coefMonomial(h,x(i)^(newton[i2][1][1][1])*x(j)^(newton[i2][1][1][2])*x(k)^(newton[i2][1][1][3]),n,N),(transpose(newton[i2][1][1])*newton[i2][2])[1]); for(l=2;l<=size(newton[i2][1]);l++) { lattice = deleteElement(lattice,newton[i2][1][l]); val2 = list(coefMonomial(h,x(i)^(newton[i2][1][l][1])*x(j)^(newton[i2][1][l][2])*x(k)^(newton[i2][1][l][3]),n,N),(transpose(newton[i2][1][l])*newton[i2][2])[1]); valeq = valeq + list(list(val1,val2)); } } //for all inner lattice point, we want to find the inequalities on the valuations //for any inner lattice point, check in which part it lies in and find conditions for(l=1;l<=size(lattice);l++) { for(i2=1;i2<=size(newton);i2++) { boolean = 1; for(i3=2;i3 0) { boolean = 0; } mMat = (newton[i2][1][i3+1][1] - newton[i2][1][i3][1]),(newton[i2][1][i3+1][2] - newton[i2][1][i3][2]),(lattice[l][1] - newton[i2][1][i3][1]),(lattice[l][2] - newton[i2][1][i3][2]); if(det(mMat) < 0) { boolean = 0; } } //check for the last vertex mMat = (newton[i2][1][i3-1][1] - newton[i2][1][i3][1]),(newton[i2][1][i3-1][2] - newton[i2][1][i3][2]),(lattice[l][1] - newton[i2][1][i3][1]),(lattice[l][2] - newton[i2][1][i3][2]); if(det(mMat) > 0) { boolean = 0; } mMat = (newton[i2][1][1][1] - newton[i2][1][i3][1]),(newton[i2][1][1][2] - newton[i2][1][i3][2]),(lattice[l][1] - newton[i2][1][i3][1]),(lattice[l][2] - newton[i2][1][i3][2]); if(det(mMat) < 0) { boolean = 0; } if(boolean == 1) //lattice point lies in this part of the Newton polytope { //add condition valleq = valleq + list(list(list(coefMonomial(h,x(i)^(newton[i2][1][1][1])*x(j)^(newton[i2][1][1][2])*x(k)^(newton[i2][1][1][3]),n,N),(transpose(newton[i2][1][1])*newton[i2][2])[1]),list(coefMonomial(h,x(i)^(lattice[l][1])*x(j)^(lattice[l][2])*x(k)^(lattice[l][3]),n,N),(transpose(lattice[l])*newton[i2][2])[1]))); i2 = size(newton); } } } } } } } //reduce the linear combinations modulo E and bring them in a standard form for(i=1;i<=size(valeq);i++) { valeq[i][1][1] = cleardenom(simplify(valeq[i][1][1],1)); valeq[i][2][1] = cleardenom(simplify(valeq[i][2][1],1)); } for(i=1;i<=size(valleq);i++) { valleq[i][1][1] = cleardenom(simplify(valleq[i][1][1],1)); valleq[i][2][1] = cleardenom(simplify(valleq[i][2][1],1)); } //fix first valuation and use this to simplify conditions g = valeq[1][1][1]; list valeqnr = list(list(g,0)); for(i=1;i<=size(valeq);i++) { if(valeq[i][1][1] == g) { valeq[i][1][1] = 0; } if(valeq[i][2][1] == g) { valeq[i][2][1] = 0; } } int a = 1; while((size(valeq) != 0) && (a == 1)) { a = 0; //search conditions which only contain one expression for(i=1;i<=size(valeq);i++) { if((deg(valeq[i][1][1]) <= 0) && (deg(valeq[i][2][1]) <= 0)) { if(valeq[i][1][1] + valeq[i][1][2] != valeq[i][2][1]+valeq[i][2][2]) { return(-1); } valeq = delete(valeq,i); a = 1; i = i-1; } else { if(deg(valeq[i][1][1])+deg(valeq[i][2][1]) <= 1) { a = 1; if(deg(valeq[i][1][1]) == 1) { g = valeq[i][1][1]; l = valeq[i][2][1]+valeq[i][2][2]-valeq[i][1][2]; valeqnr = valeqnr + list(list(g,l)); valeq = delete(valeq,i); } else { g = valeq[i][2][1]; l = valeq[i][1][1]+valeq[i][1][2]-valeq[i][2][2]; valeqnr = valeqnr + list(list(g,l)); valeq = delete(valeq,i); } for(j=1;j<=size(valeq);j++) { if(valeq[j][1][1] == g) { valeq[j][1][1] = l; } if(valeq[j][2][1] == g) { valeq[j][2][1] = l; } } i = size(valeq); } } } } //simplify the inequalities for(i=1;i<=size(valeqnr);i++) { for(j=1;j<=size(valleq);j++) { if(valleq[j][1][1] == valeqnr[i][1]) { valleq[j][1][1] = valeqnr[i][2]; } } } list valleqnr; for(i=1;i<=size(valleq);i++) { if(deg(valleq[i][1][1]) > 0) { return(-2); } valleqnr = valleqnr + list(list(valleq[i][2][1],valleq[i][1][1]+valleq[i][1][2]-valleq[i][2][2])); } //translate the valuations such that no valuation is negative l = valeqnr[1][2]; for(i=1;i<=size(valeqnr);i++) { if(valeqnr[i][2] < l) { l = valeqnr[i][2]; } } for(i=1;i<=size(valleqnr);i++) { if(valleqnr[i][2] < l) { l = valleqnr[i][2]; } } //adapt the valuations for(i=1;i<=size(valeqnr);i++) { valeqnr[i][2] = valeqnr[i][2] - l; } for(i=1;i<=size(valleqnr);i++) { valleqnr[i][2] = valleqnr[i][2] - l; } //find the right hand sides of the conditions list RHS; for(i=1;i<=size(valeqnr);i++) { RHS = addIfNotContained(RHS,valeqnr[i][2]); } for(i=1;i<=size(valleqnr);i++) { RHS = addIfNotContained(RHS,valleqnr[i][2]); } //find a basis of free parameters list freeVariables; for(i=1;i<=N;i++) { freeVariables[i] = a(i); } list depVariables; E = std(E); for(i=1;i<=size(E);i++) { g = E[i]; depVariables[i] = list(leadmonom(g),reduce(leadmonom(g),E)); freeVariables = deleteElement(freeVariables,leadmonom(g)); } //initialize Puiseux-Polynomials int m = size(freeVariables)*size(RHS); int bVal = size(valleqnr); int bDep = size(depVariables); int bFree = size(freeVariables); ring R = 0,(x(1..n),a(1..N),b(1..m),t),dp; list valeqnr = fetch(r,valeqnr); if(bVal != 0) { list valleqnr = fetch(r,valleqnr); } if(bFree != 0) { list freeVariables = fetch(r,freeVariables); } if(bDep != 0) { list depVariables = fetch(r,depVariables); } list puiseuxPoly; poly f; k = 1; for(i=1;i<=size(freeVariables);i++) { f = 0; for(j=1;j<=size(RHS);j++) { f = f + b(k)*t^(RHS[j]); k = k+1; } puiseuxPoly[i] = f; } //generate ideal of conditions, see if rezession fan is realizable //initialize a vector to measure t-degree zerovec = 0; for(i=2;i<=(n+N+m);i++) { zerovec = zerovec,0; } zerovec = zerovec,1; int realisierbar = 1; ideal B; list NE; matrix G; for(i=1;i<=size(valeqnr);i++) { f = valeqnr[i][1]; for(j=1;j<=size(depVariables);j++) { f = subst(f,depVariables[j][1],depVariables[j][2]); } if(f == 0) { realisierbar = 0; return(-1); } for(j=1;j<=size(freeVariables);j++) { f = subst(f,freeVariables[j],puiseuxPoly[j]); } f = jet(f,valeqnr[i][2],zerovec); G = coef(f,t); NE = NE + list(G[2,1]); for(j=2;j<=ncols(G);j++) { B = B + ideal(G[2,j]); } } for(i=1;i<=size(valleqnr);i++) { f = valleqnr[i][1]; for(j=1;j<=size(depVariables);j++) { f = subst(f,depVariables[j][1],depVariables[j][2]); } for(j=1;j<=size(freeVariables);j++) { f = subst(f,freeVariables[j],puiseuxPoly[j]); } f = jet(f,valleqnr[i][2],zerovec); G = coef(f,t); for(j=2;j<=ncols(G);j++) { B = B + ideal(G[2,j]); } } //check whether or not there is a common solution B = std(B); for(i=1;i<=size(NE);i++) { if(reduce(NE[i],B) == 0) { realisierbar = 0; } } if(back == 1) { setring save; if(realisierbar == 1) { return(1); } else { return(-1); } } else { if(realisierbar == 1) { export(B); export(NE); export(m,n,N,d); export(goodproj); export(depVariables); export(freeVariables); export(puiseuxPoly); return(1,R); } else { setring save; return(-1); } } } //////////////////////////////////////////////////////////////////////////////////////////////////////////// proc realizable(ideal I, list C) "USAGE: realizable(I,C); where I is a homogeneous linear ideal defining the projective plane Y = V(I) and C represents the tropical curve. This is done in the following way: C = list(V,E,M) consists of the three lists V,E,M. In V, there is an intvector of the form (1,v) for any vertex v of C and an intvector of the form (0,r) for any unbounded edge of C in primitive direction r. In E, we have an intvector (i,j) for any bounded edge between the vertex at position i in V and the vertex of C at position j in V. Moreover, there is an intvector (i,j) for any unbounded edge starting at the vertex at position i in the direction at position j. Finally, the list M stores the multiplicities of the edges in E. ASSUME: This routine expects v and r to have homogeneous coordinates such that the minimum over the entries is zero. RETURNS: 1 if C is relatively realizable and -1 if not. EXAMPLE: example realizable; shows an example" { return(realization(I,C,1)[1]); } example { "EXAMPLE:"; echo=2; ring r = 0,(x(0..3)),dp; ideal I = x(0)+x(1)+x(2)+x(3); list V = list(intvec(1,1,1,0,0),intvec(1,0,0,1,1),intvec(0,1,0,0,0), intvec(0,0,1,0,0),intvec(0,0,0,1,0),intvec(0,0,0,0,1)); list E = list(intvec(1,2),intvec(1,3),intvec(1,4),intvec(2,5), intvec(2,6)); list M = list(2,2,2,2,2); list C = list(V,E,M); // C represents the tropical curve which has two vertices // [1,1,0,0] and [0,0,1,1], which are connected by a bounded // edge, and has an unbounded edge in any // standard direction. Any maximal cell in C has weight 2. realizable(I,C); } ////////////////////////////////////////////////////////////////////////////////////////////////////////////// proc realizablePoly(ideal I, list C) "USAGE: realizablePoly(I,C); where I is a homogeneous linear ideal defining the projective plane Y = V(I) and C represents the tropical curve. This is done in the following way: C = list(V,E,M) consists of the three lists V,E,M. In V, there is an intvector of the form (1,v) for any vertex v of C and an intvector of the form (0,r) for any unbounded edge of C in primitive direction r. In E, we have an intvector (i,j) for any bounded edge between the vertex at position i in V and the vertex of C at position j in V. Moreover, there is an intvector (i,j) for any unbounded edge starting at the vertex at position i in the direction at position j. Finally, the list M stores the multiplicities of the edges in E. ASSUME: This routine expects v and r to have homogeneous coordinates such that the minimum over the entries is zero. The base ring needs to have a parameter which plays the role of t in C{{t}}. RETURNS: If C is relatively realizable, it returns (1,f), where f is a polynomial such that Trop(I+(f)) = C, and -1 if C is not relatively realizable. EXAMPLE: example realizablePoly; shows an example" { def save = basering; list L = realization(I,C,2); if(L[1] == -1) { return(-1); } def R = L[2]; setring R; int i; int j; int k; //compute a polynomial realizing C //find variables which are free to choose intvec x; for(i=1;i<=size(B);i++) { x = x + leadexp(B[i]); } ideal E1; list NE1; //initialize the list of the free variables list lValues; if(size(x) > 1) { for(j=1;j<=m;j++) { if(x[j+n+N] == 0) { lValues = lValues + list(list(b(j),0)); } } } else { for(j=1;j<=m;j++) { lValues = lValues + list(list(b(j),0)); } } //try to find an easy solution int boolean = 1; for(j=1;j<=size(lValues);j++) { if(boolean == 0) { lValues[j][2] = lValues[j][2] + 1; } boolean = 1; E1 = B; for(i=1;i<=size(E1);i++) { for(k=1;k<=j;k++) { E1[i] = subst(E1[i],lValues[k][1],lValues[k][2]); } } NE1 = NE; for(i=1;i<=size(NE);i++) { for(k=1;k<=j;k++) { NE1[i] = subst(NE1[i],lValues[k][1],lValues[k][2]); } } E1 = std(E1); for(i=1;i<=size(NE1);i++) { if(reduce(NE1[i],E1) == 0) { boolean = 0; } } if(boolean == 0) { j = j-1; } } poly f; //compute the values of the dependent variables for(j=1;j<=size(B);j++) { f = B[j]; for(k=1;k<=size(lValues);k++) { f = subst(f,lValues[k][1],lValues[k][2]); } if(leadcoef(f) != 1) { for(k=1;k<=size(lValues);k++) { lValues[k][2] = lValues[k][2] * leadcoef(f); } } f = subst(f,leadmonom(f),0); lValues = lValues + list(list(leadmonom(B[j]),-f)); } poly gNeu = genPoly(d,goodproj[1],goodproj[2],goodproj[3]); for(j=1;j<=size(depVariables);j++) { gNeu = subst(gNeu,depVariables[j][1],depVariables[j][2]); } for(j=1;j<=size(freeVariables);j++) { gNeu = subst(gNeu,freeVariables[j],puiseuxPoly[j]); } for(j=1;j<=size(lValues);j++) { gNeu = subst(gNeu,lValues[j][1],lValues[j][2]); } ring rNeu = (0,t),(x(1..n)),dp; poly g = imap(R,gNeu); setring save; return(1,fetch(rNeu,g)); } example { "EXAMPLE:"; echo=2; ring r = (0,t),(x(0..3)),dp; ideal I = x(0)+x(1)+x(2)+x(3); list V = list(intvec(1,1,1,0,0),intvec(1,0,0,1,1),intvec(0,1,0,0,0), intvec(0,0,1,0,0),intvec(0,0,0,1,0),intvec(0,0,0,0,1)); list E = list(intvec(1,2),intvec(1,3),intvec(1,4),intvec(2,5), intvec(2,6)); list M = list(2,2,2,2,2); list C = list(V,E,M); // C represents the tropical curve which has two vertices // [1,1,0,0] and [0,0,1,1], which are connected by a // bounded edge, and has an unbounded edge in any // standard direction. Any maximal cell in C has weight 2. realizablePoly(I,C); }