Changeset 3360fb in git for Singular/LIB/tropical.lib
- Timestamp:
- Apr 14, 2009, 2:00:15 PM (14 years ago)
- Branches:
- (u'spielwiese', '8e0ad00ce244dfd0756200662572aef8402f13d5')
- Children:
- 334c21f9e573112667d39f4cd9dcad9c7b19a50c
- Parents:
- 2c3a5db391a25c28449b80c5f27e1dd77ed2c30f
- File:
-
- 1 edited
Legend:
- Unmodified
- Added
- Removed
-
Singular/LIB/tropical.lib
r2c3a5d r3360fb 1 version="$Id: tropical.lib,v 1.1 4 2009-04-08 12:42:19 seelischExp $";1 version="$Id: tropical.lib,v 1.15 2009-04-14 12:00:15 Singular Exp $"; 2 2 category="Tropical Geometry"; 3 3 info=" … … 8 8 @* Thomas Markwig, email: keilen@mathematik.uni-kl.de 9 9 10 WARNING: 10 WARNING: 11 11 - tropicalLifting will only work with LINUX and if in addition gfan is installed. 12 @*- drawTropicalCurve and drawTropicalNewtonSubdivision will only display the 13 @* tropical curve with LINUX and if in addition latex and kghostview 12 @*- drawTropicalCurve and drawTropicalNewtonSubdivision will only display the 13 @* tropical curve with LINUX and if in addition latex and kghostview 14 14 @* are installed. 15 @*- For tropicalLifting in the definition of the basering the parameter t 15 @*- For tropicalLifting in the definition of the basering the parameter t 16 16 @* from the Puiseux series field C{{t}} must be defined as a variable, 17 17 @* while for all other procedures it must be defined as a parameter. 18 18 19 19 THEORY: 20 Fix some base field K and a bunch of lattice points v0,...,vm in the integer 21 lattice Z^n, then this defines a toric variety as the closure of (K*)^n in 22 the projective space P^m, where the torus is embedded via the map sending a 20 Fix some base field K and a bunch of lattice points v0,...,vm in the integer 21 lattice Z^n, then this defines a toric variety as the closure of (K*)^n in 22 the projective space P^m, where the torus is embedded via the map sending a 23 23 point x in (K*)^n to the point (x^v0,...,x^vm). 24 The generic hyperplane sections are just the images of the hypersurfaces 24 The generic hyperplane sections are just the images of the hypersurfaces 25 25 in (K*)^n defined by the polynomials f=a0*x^v0+...+am*x^vm=0. Some properties 26 of these hypersurfaces can be studied via tropicalisation. 27 28 For this we suppose that K=C{{t}} is the field of Puiseux series over the 26 of these hypersurfaces can be studied via tropicalisation. 27 28 For this we suppose that K=C{{t}} is the field of Puiseux series over the 29 29 field of complex numbers (or any other field with a valuation into the real 30 numbers). One associates to the hypersurface given by f=a0*x^v0+...+am*x^vm 30 numbers). One associates to the hypersurface given by f=a0*x^v0+...+am*x^vm 31 31 the tropical hypersurface defined by the tropicalisation 32 trop(f)=min{val(a0)+<v0,x>,...,val(am)+<vm,x>}. 32 trop(f)=min{val(a0)+<v0,x>,...,val(am)+<vm,x>}. 33 33 Here, <v,x> denotes the standard scalar product of the integer vector v in Z^n 34 34 with the vector x=(x1,...,xn) of variables, so that trop(f) is a piecewise 35 linear function on R^n. The corner locus of this function (i.e. the points 36 at which the minimum is attained a least twice) is the tropical hypersurface 37 defined by trop(f). 38 The theorem of Newton-Kapranov states that this tropical hypersurface is 39 the same as if one computes pointwise the valuation of the hypersurface 40 given by f. The analogue holds true if one replaces one equation f by an 41 ideal I. A constructive proof of the theorem is given by an adapted 42 version of the Newton-Puiseux algorithm. The hard part is to find a point 43 in the variety over C{{t}} which corresponds to a given point in the 35 linear function on R^n. The corner locus of this function (i.e. the points 36 at which the minimum is attained a least twice) is the tropical hypersurface 37 defined by trop(f). 38 The theorem of Newton-Kapranov states that this tropical hypersurface is 39 the same as if one computes pointwise the valuation of the hypersurface 40 given by f. The analogue holds true if one replaces one equation f by an 41 ideal I. A constructive proof of the theorem is given by an adapted 42 version of the Newton-Puiseux algorithm. The hard part is to find a point 43 in the variety over C{{t}} which corresponds to a given point in the 44 44 tropical variety. 45 45 46 It is the purpose of this library to provide basic means to deal with 47 tropical varieties. Of course we cannot represent the field of Puiseux 48 series over C in its full strength, however, in order to compute interesting 49 examples it will be sufficient to replace the complex numbers C by the 50 rational numbers Q and to replace Puiseux series in t by rational functions 51 in t, i.e. we replace C{{t}} by Q(t), or sometimes even by Q[t]. 46 It is the purpose of this library to provide basic means to deal with 47 tropical varieties. Of course we cannot represent the field of Puiseux 48 series over C in its full strength, however, in order to compute interesting 49 examples it will be sufficient to replace the complex numbers C by the 50 rational numbers Q and to replace Puiseux series in t by rational functions 51 in t, i.e. we replace C{{t}} by Q(t), or sometimes even by Q[t]. 52 52 Note, that this in particular forbids rational exponents for the t's. 53 53 54 Moreover, in Singular no negative exponents of monomials are allowed, so 55 that the integer vectors vi will have to have non-negative entries. 56 Shifting all exponents by a fixed integer vector does not change the 57 tropicalisation nor does it change the toric variety. Thus this does not 54 Moreover, in Singular no negative exponents of monomials are allowed, so 55 that the integer vectors vi will have to have non-negative entries. 56 Shifting all exponents by a fixed integer vector does not change the 57 tropicalisation nor does it change the toric variety. Thus this does not 58 58 cause any restriction. 59 If, however, for some reason you prefer to work with general vi, then you 60 have to pass right away to the tropicalisation of the equations, whereever 59 If, however, for some reason you prefer to work with general vi, then you 60 have to pass right away to the tropicalisation of the equations, whereever 61 61 this is allowed -- these are linear polynomials where the constant coefficient 62 corresponds to the valuation of the original coefficient and where 63 the non-constant coefficient correspond to the exponents of the monomials, 64 thus they may be rational numbers respectively negative numbers: 62 corresponds to the valuation of the original coefficient and where 63 the non-constant coefficient correspond to the exponents of the monomials, 64 thus they may be rational numbers respectively negative numbers: 65 65 e.g. if f=t^{1/2}*x^{-2}*y^3+2t*x*y+4 then trop(f)=min{1/2-2x+3y,1+x+y,0}. 66 66 67 67 The main tools provided in this library are as follows: 68 @* - tropicalLifting implements the constructive proof of the Theorem of 69 Newton-Kapranov and constructs a point in the variety 70 over C{{t}} corresponding to a given point in the 71 corresponding tropical variety associated to an 72 ideal I; the generators of I have to be in the 73 polynomial ring Q[t,x1,...,xn] considered as a 74 subring of C{{t}}[x1,...,xn]; a solution will be 75 constructed up to given order; note that several 68 @* - tropicalLifting implements the constructive proof of the Theorem of 69 Newton-Kapranov and constructs a point in the variety 70 over C{{t}} corresponding to a given point in the 71 corresponding tropical variety associated to an 72 ideal I; the generators of I have to be in the 73 polynomial ring Q[t,x1,...,xn] considered as a 74 subring of C{{t}}[x1,...,xn]; a solution will be 75 constructed up to given order; note that several 76 76 field extensions of Q might be necessary throughout 77 77 the intermediate computations; the procedures use 78 78 the external program gfan 79 @* - drawTropicalCurve visualises a tropical plane curve either given by a 80 polynomial in Q(t)[x,y] or by a list of linear 81 polynomials of the form ax+by+c with a,b in Z and c 79 @* - drawTropicalCurve visualises a tropical plane curve either given by a 80 polynomial in Q(t)[x,y] or by a list of linear 81 polynomials of the form ax+by+c with a,b in Z and c 82 82 in Q; latex must be installed on your computer 83 @* - tropicalJInvariant computes the tropical j-invaiant of a tropical 83 @* - tropicalJInvariant computes the tropical j-invaiant of a tropical 84 84 elliptic curve 85 85 @* - jInvariant computes the j-invariant of an elliptic curve 86 @* - weierstrassForm computes the Weierstrass form of an elliptic curve 86 @* - weierstrassForm computes the Weierstrass form of an elliptic curve 87 87 88 88 PROCEDURES FOR TROPICAL LIFTING: 89 tropicalLifting computes a point in the tropical variety 89 tropicalLifting computes a point in the tropical variety 90 90 displayTropicalLifting displays the output of tropicalLifting 91 91 … … 104 104 tropicalise computes the tropicalisation of a polynomial 105 105 tropicaliseSet computes the tropicalisation several polynomials 106 tInitialForm computes the tInitial form of a poly in Q[t,x_1,...,x_n] 106 tInitialForm computes the tInitial form of a poly in Q[t,x_1,...,x_n] 107 107 tInitialIdeal computes the tInitial ideal of an ideal in Q[t,x_1,...,x_n] 108 initialForm computes the initial form of poly in Q[x_1,...,x_n] 109 initialIdeal computes the initial ideal of an ideal in Q[x_1,...,x_n] 108 initialForm computes the initial form of poly in Q[x_1,...,x_n] 109 initialIdeal computes the initial ideal of an ideal in Q[x_1,...,x_n] 110 110 111 111 PROCEDURES FOR LATEX CONVERSION: 112 112 texNumber outputs the texcommand for the leading coefficient of poly 113 texPolynomial outputs the texcommand for the polynomial poly 113 texPolynomial outputs the texcommand for the polynomial poly 114 114 texMatrix outputs the texcommand for the matrix 115 115 texDrawBasic embeds output of texDrawTropical in a texdraw environment 116 116 texDrawTropical computes the texdraw commands for a tropical curve 117 texDrawNewtonSubdivision computes texdraw commands for a Newton subdivision 117 texDrawNewtonSubdivision computes texdraw commands for a Newton subdivision 118 118 texDrawTriangulation computes texdraw commands for a triangulation 119 119 … … 121 121 radicalMemberShip checks radical membership 122 122 tInitialFormPar computes the t-initial form of poly in Q(t)[x_1,...,x_n] 123 tInitialFormParMax same as tInitialFormPar, but uses maximum 123 tInitialFormParMax same as tInitialFormPar, but uses maximum 124 124 solveTInitialFormPar displays approximated solution of a 0-dim ideal 125 125 detropicalise computes the detropicalisation of a linear form 126 dualConic computes the dual of an affine plane conic 126 dualConic computes the dual of an affine plane conic 127 127 parameterSubstitute substitutes in the poly the parameter t by t^N 128 128 tropicalSubst makes certain substitutions in a tropical polynomial … … 155 155 /// - eliminatecomponents 156 156 /// - findzerosAndBasictransform 157 /// - ordermaximalideals 157 /// - ordermaximalideals 158 158 /// - verticesTropicalCurve 159 159 /// - bunchOfLines … … 204 204 205 205 /////////////////////////////////////////////////////////////////////////////// 206 /// Procedures concerned with tropical parametrisation 206 /// Procedures concerned with tropical parametrisation 207 207 /////////////////////////////////////////////////////////////////////////////// 208 208 209 209 proc tropicalLifting (ideal i,intvec w,int ordnung,list #) 210 210 "USAGE: tropicalLifting(i,w,ord[,opt]); i ideal, w intvec, ord int, opt string 211 ASSUME: - i is an ideal in Q[t,x_1,...,x_n], w=(w_0,w_1,...,w_n) 212 and (w_1/w_0,...,w_n/w_0) is in the tropical variety of i, 213 and ord is the order up to which a point in V(i) over Q{{t}} 214 lying over (w_1/w_0,...,w_n/w_0) shall be computed; 211 ASSUME: - i is an ideal in Q[t,x_1,...,x_n], w=(w_0,w_1,...,w_n) 212 and (w_1/w_0,...,w_n/w_0) is in the tropical variety of i, 213 and ord is the order up to which a point in V(i) over Q{{t}} 214 lying over (w_1/w_0,...,w_n/w_0) shall be computed; 215 215 w_0 may NOT be ZERO 216 @* - the basering should not have any parameters on its own 217 and it should have a global monomial ordering, 216 @* - the basering should not have any parameters on its own 217 and it should have a global monomial ordering, 218 218 e.g. ring r=0,(t,x(1..n)),dp; 219 @* - the first variable of the basering will be treated as the 219 @* - the first variable of the basering will be treated as the 220 220 parameter t in the Puiseux series field 221 @* - the optional parameter opt should be one or more strings among 221 @* - the optional parameter opt should be one or more strings among 222 222 the following: 223 223 @* 'isZeroDimensional' : the dimension i is zero (not to be checked); 224 @* 'isPrime' : the ideal is prime over Q(t)[x_1,...,x_n] 224 @* 'isPrime' : the ideal is prime over Q(t)[x_1,...,x_n] 225 225 (not to be checked); 226 @* 'isInTrop' : (w_1/w_0,...,w_n/w_0) is in the tropical 226 @* 'isInTrop' : (w_1/w_0,...,w_n/w_0) is in the tropical 227 227 variety (not to be checked); 228 @* 'oldGfan' : uses gfan version 0.2.1 or less 229 @* 'findAll' : find all solutions of a zero-dimensional 228 @* 'oldGfan' : uses gfan version 0.2.1 or less 229 @* 'findAll' : find all solutions of a zero-dimensional 230 230 ideal over (w_1/w_0,...,w_n/w_0) 231 231 @* 'noAbs' : do NOT use absolute primary decomposition … … 233 233 RETURN: IF THE OPTION 'findAll' WAS NOT SET THEN: 234 234 @* list, containing one lifting of the given point (w_1/w_0,...,w_n/w_0) 235 in the tropical variety of i to a point in V(i) over Puiseux 235 in the tropical variety of i to a point in V(i) over Puiseux 236 236 series field up to the first ord terms; more precisely: 237 237 @* IF THE OPTION 'noAbs' WAS NOT SET, THEN: … … 248 248 @* IF THE OPITON 'findAll' WAS SET, THEN: 249 249 @* list, containing ALL liftings of the given point ((w_1/w_0,...,w_n/w_0) 250 in the tropical variety of i to a point in V(i) over Puiseux 251 series field up to the first ord terms, if the ideal is 250 in the tropical variety of i to a point in V(i) over Puiseux 251 series field up to the first ord terms, if the ideal is 252 252 zero-dimensional over Q{{t}}; 253 more precisely, each entry of the list is a list l as computed 253 more precisely, each entry of the list is a list l as computed 254 254 if 'findAll' was NOT set 255 255 @* WE NOW DESCRIBE THE LIST ENTRIES IF 'findAll' WAS NOT SET: 256 @* - the ring l[1] contains an ideal LIFT, which contains 256 @* - the ring l[1] contains an ideal LIFT, which contains 257 257 a point in V(i) lying over w up to the first ord terms; 258 @* - and if the integer l[2] is N then t has to be replaced by t^1/N 258 @* - and if the integer l[2] is N then t has to be replaced by t^1/N 259 259 in the lift, or alternatively replace t by t^N in the defining ideal 260 @* - if the k+1st entry of l[3] is non-zero, then the kth component of 261 LIFT has to be multiplied t^(-l[3][k]/l[3][1]) AFTER substituting t 260 @* - if the k+1st entry of l[3] is non-zero, then the kth component of 261 LIFT has to be multiplied t^(-l[3][k]/l[3][1]) AFTER substituting t 262 262 by t^1/N 263 @* - unless the option 'noResubst' was set, the kth entry of list l[4] 263 @* - unless the option 'noResubst' was set, the kth entry of list l[4] 264 264 is a string which represents the kth generator of 265 the ideal i where the coordinates have been replaced by the result 265 the ideal i where the coordinates have been replaced by the result 266 266 of the lift; 267 the t-order of the kth entry should in principle be larger than the 267 the t-order of the kth entry should in principle be larger than the 268 268 t-degree of LIFT 269 @* - if the option 'noAbs' was set, then the string in l[5] defines 270 a maximal ideal in the field Q[X(1),...,X(k)], where X(1),...,X(k) 269 @* - if the option 'noAbs' was set, then the string in l[5] defines 270 a maximal ideal in the field Q[X(1),...,X(k)], where X(1),...,X(k) 271 271 are the parameters of the ring in l[1]; 272 the basefield of the ring in l[1] should be considered modulo this 272 the basefield of the ring in l[1] should be considered modulo this 273 273 ideal 274 REMARK: - it is best to use the procedure displayTropicalLifting to 274 REMARK: - it is best to use the procedure displayTropicalLifting to 275 275 display the result 276 276 @* - the option 'findAll' cannot be used if 'noAbs' is set 277 277 @* - if the parameter 'findAll' is set AND the ideal i is zero-dimensional 278 in Q{{t}}[x_1,...,x_n] then ALL points in V(i) lying over w are 278 in Q{{t}}[x_1,...,x_n] then ALL points in V(i) lying over w are 279 279 computed up to order ord; if the ideal is not-zero dimenisonal, then 280 280 only the points in the ideal after cutting down to dimension zero 281 281 will be computed 282 282 @* - the procedure requires that the program GFAN is installed on your 283 computer; if you have GFAN version less than 0.3.0 then you must 283 computer; if you have GFAN version less than 0.3.0 then you must 284 284 use the optional parameter 'oldGfan' 285 @* - the procedure requires the Singular procedure absPrimdecGTZ to be 285 @* - the procedure requires the Singular procedure absPrimdecGTZ to be 286 286 present in the package primdec.lib, unless the option 'noAbs' is set; 287 but even if absPrimdecGTZ is present it might be necessary to set 288 the option 'noAbs' in order to avoid the costly absolute primary 289 decomposition; the side effect is that the field extension which is 287 but even if absPrimdecGTZ is present it might be necessary to set 288 the option 'noAbs' in order to avoid the costly absolute primary 289 decomposition; the side effect is that the field extension which is 290 290 computed throughout the recursion might need more than one 291 291 parameter to be described 292 292 @* - since Q is infinite, the procedure finishes with probability one 293 @* - you can call the procedure with Z/pZ as base field instead of Q, 293 @* - you can call the procedure with Z/pZ as base field instead of Q, 294 294 but there are some problems you should be aware of: 295 @* + the Puiseux series field over the algebraic closure of Z/pZ is 296 NOT algebraicall closed, and thus there may not exist a point in 297 V(i) over the Puiseux series field with the desired valuation; 295 @* + the Puiseux series field over the algebraic closure of Z/pZ is 296 NOT algebraicall closed, and thus there may not exist a point in 297 V(i) over the Puiseux series field with the desired valuation; 298 298 so there is no chance that the procedure produced a sensible output 299 - e.g. if i=tx^p-tx-1 300 @* + if the dimension of i over Z/pZ(t) is not zero the process of 301 reduction to zero might not work if the characteristic is small 299 - e.g. if i=tx^p-tx-1 300 @* + if the dimension of i over Z/pZ(t) is not zero the process of 301 reduction to zero might not work if the characteristic is small 302 302 and you are unlucky 303 @* + the option 'noAbs' has to be used since absolute primary 303 @* + the option 'noAbs' has to be used since absolute primary 304 304 decomposition in Singular only works in characteristic zero 305 @* - the basefield should either be Q or Z/pZ for some prime p; 306 field extensions will be computed if necessary; if you need 307 parameters or field extensions from the beginning they should 308 rather be simulated as variables possibly adding their relations to 305 @* - the basefield should either be Q or Z/pZ for some prime p; 306 field extensions will be computed if necessary; if you need 307 parameters or field extensions from the beginning they should 308 rather be simulated as variables possibly adding their relations to 309 309 the ideal; the weights for the additional variables should be zero 310 310 EXAMPLE: example tropicalLifting; shows an example" … … 357 357 noabs=1; 358 358 } 359 // this option is not documented -- it prevents the execution of gfan and 360 // just asks for wneu to be inserted -- it can be used to check problems 361 // with the precedure without calling gfan, if wneu is know from previous 359 // this option is not documented -- it prevents the execution of gfan and 360 // just asks for wneu to be inserted -- it can be used to check problems 361 // with the precedure without calling gfan, if wneu is know from previous 362 362 // computations 363 363 if (#[j]=="noGfan") … … 370 370 } 371 371 } 372 // if the basering has characteristic not equal to zero, 372 // if the basering has characteristic not equal to zero, 373 373 // then absolute factorisation 374 374 // is not available, and thus we need the option noAbs … … 384 384 { 385 385 Error("The first coordinate of your input w must be NON-ZERO, since it is a DENOMINATOR!"); 386 } 386 } 387 387 // if w_0<0, then replace w by -w, so that the "denominator" w_0 is positive 388 388 if (w[1]<0) … … 391 391 } 392 392 intvec prew=w; // stores w for later reference 393 // for our computations, w[1] represents the weight of t and this 393 // for our computations, w[1] represents the weight of t and this 394 394 // should be -w_0 !!! 395 395 w[1]=-w[1]; … … 401 401 w[1]=-1; 402 402 } 403 // if some entry of w is positive, we have to make a transformation, 403 // if some entry of w is positive, we have to make a transformation, 404 404 // which moves it to something non-positive 405 405 for (j=2;j<=nvars(basering);j++) … … 427 427 { 428 428 variablen=variablen+var(j); 429 } 429 } 430 430 map GRUNDPHI=BASERING,t,variablen; 431 431 ideal i=GRUNDPHI(i); 432 // compute the initial ideal of i and test if w is in the tropical 433 // variety of i 432 // compute the initial ideal of i and test if w is in the tropical 433 // variety of i 434 434 // - the last entry 1 only means that t is the last variable in the ring 435 435 ideal ini=tInitialIdeal(i,w,1); 436 436 if (isintrop==0) // test if w is in trop(i) only if isInTrop has not been set 437 { 437 { 438 438 poly product=1; 439 439 for (j=1;j<=nvars(basering)-1;j++) … … 453 453 int dd=dim(i); 454 454 setring GRUNDRING; 455 // if the dimension is not zero, we cut the ideal down to dimension zero 455 // if the dimension is not zero, we cut the ideal down to dimension zero 456 456 // and compute the 457 457 // t-initial ideal of the new ideal at the same time 458 458 if(dd!=0) 459 459 { 460 // the procedurce cutdown computes a new ring, in which there lives a 460 // the procedurce cutdown computes a new ring, in which there lives a 461 461 // zero-dimensional 462 // ideal which has been computed by cutting down the input with 462 // ideal which has been computed by cutting down the input with 463 463 // generic linear forms 464 // of the type x_i1-p_1,...,x_id-p_d for some polynomials 465 // p_1,...,p_d not depending 466 // on the variables x_i1,...,x_id; that way we have reduced 464 // of the type x_i1-p_1,...,x_id-p_d for some polynomials 465 // p_1,...,p_d not depending 466 // on the variables x_i1,...,x_id; that way we have reduced 467 467 // the number of variables by dd !!! 468 // the new zero-dimensional ideal is called i, its t-initial 468 // the new zero-dimensional ideal is called i, its t-initial 469 469 // ideal (with respect to 470 // the new w=CUTDOWN[2]) is ini, and finally there is a list 471 // repl in the ring 470 // the new w=CUTDOWN[2]) is ini, and finally there is a list 471 // repl in the ring 472 472 // which contains at the polynomial p_j at position i_j and 473 473 //a zero otherwise; … … 492 492 list liftrings; // will contain the final result 493 493 // if the procedure is called without 'findAll' then it may happen, that no 494 // proper solution is found when dd>0; in that case we have 494 // proper solution is found when dd>0; in that case we have 495 495 // to start all over again; 496 496 // this is controlled by the while-loop … … 508 508 // compute the liftrings by resubstitution 509 509 kk=1; // counts the liftrings 510 int isgood; // test in the non-zerodimensional case 510 int isgood; // test in the non-zerodimensional case 511 511 // if the result has the correct valuation 512 512 for (jj=1;jj<=size(TP);jj++) 513 513 { 514 // the list TP contains as a first entry the ring over which the 515 // tropical parametrisation 514 // the list TP contains as a first entry the ring over which the 515 // tropical parametrisation 516 516 // of the (possibly cutdown ideal) i lives 517 517 def LIFTRING=TP[jj][1]; 518 // if the dimension of i originally was not zero, 518 // if the dimension of i originally was not zero, 519 519 // then we have to fill in the missing 520 520 // parts of the parametrisation 521 521 if (dd!=0) 522 522 { 523 // we need a ring where the parameters X_1,...,X_k 523 // we need a ring where the parameters X_1,...,X_k 524 524 // from LIFTRING are present, 525 525 // and where also the variables of CUTDOWNRING live 526 526 execute("ring REPLACEMENTRING=("+charstr(LIFTRING)+"),("+varstr(CUTDOWNRING)+"),dp;"); 527 list repl=imap(CUTDOWNRING,repl); // get the replacement rules 527 list repl=imap(CUTDOWNRING,repl); // get the replacement rules 528 528 // from CUTDOWNRING 529 ideal PARA=imap(LIFTRING,PARA); // get the zero-dim. parametrisatio 529 ideal PARA=imap(LIFTRING,PARA); // get the zero-dim. parametrisatio 530 530 // from LIFTRING 531 531 // compute the lift of the solution of the original ideal i … … 533 533 k=1; 534 534 // the lift has as many components as GRUNDRING has variables!=t 535 for (j=1;j<=nvars(GRUNDRING)-1;j++) 535 for (j=1;j<=nvars(GRUNDRING)-1;j++) 536 536 { 537 537 // if repl[j]=0, then the corresponding variable was not eliminated 538 if (repl[j]==0) 538 if (repl[j]==0) 539 539 { 540 LIFT[j]=PARA[k]; // thus the lift has been 540 LIFT[j]=PARA[k]; // thus the lift has been 541 541 // computed by tropicalparametrise 542 542 k++; // k checks how many entries of PARA have already been used … … 544 544 else // if repl[j]!=0, repl[j] contains replacement rule for the lift 545 545 { 546 LIFT[j]=repl[j]; // we still have to replace the vars 546 LIFT[j]=repl[j]; // we still have to replace the vars 547 547 // in repl[j] by the corresp. entries of PARA 548 548 // replace all variables!=t (from CUTDOWNRING) 549 for (l=1;l<=nvars(CUTDOWNRING)-1;l++) 549 for (l=1;l<=nvars(CUTDOWNRING)-1;l++) 550 550 { 551 551 // substitute the kth variable by PARA[k] 552 LIFT[j]=subst(LIFT[j],var(l),PARA[l]); 552 LIFT[j]=subst(LIFT[j],var(l),PARA[l]); 553 553 } 554 554 } 555 555 } 556 556 setring LIFTRING; 557 ideal LIFT=imap(REPLACEMENTRING,LIFT); 558 // test now if the LIFT has the correct valuation !!! 559 // note: it may happen, that when resubstituting PARA into 557 ideal LIFT=imap(REPLACEMENTRING,LIFT); 558 // test now if the LIFT has the correct valuation !!! 559 // note: it may happen, that when resubstituting PARA into 560 560 // the replacement rules 561 // there occured some unexpected cancellation; 561 // there occured some unexpected cancellation; 562 562 // we only know that for SOME 563 // solution of the zero-dimensional reduction NO 564 // canellation will occur, 565 // but for others this may very well happen; 563 // solution of the zero-dimensional reduction NO 564 // canellation will occur, 565 // but for others this may very well happen; 566 566 // this in particular means that 567 // we possibly MUST compute all zero-dimensional 567 // we possibly MUST compute all zero-dimensional 568 568 // solutions when cutting down! 569 569 intvec testw=precutdownw[1]; … … 589 589 kill PARA; 590 590 // only if LIFT has the right valuation we have to do something 591 if (isgood==1) 592 { 593 // it remains to reverse the original substitutions, 591 if (isgood==1) 592 { 593 // it remains to reverse the original substitutions, 594 594 // where appropriate !!! 595 // if some entry of the original w was positive, 595 // if some entry of the original w was positive, 596 596 // we replace the corresponding 597 597 // variable x_i by t^-w[i]*x_i, so we must now replace … … 610 610 */ 611 611 // if LIFTRING contains a parameter @a, change it to a 612 if ((noabs==0) and (defined(@a)==-1)) 612 if ((noabs==0) and (defined(@a)==-1)) 613 613 { 614 // pass first to a ring where a and @a 614 // pass first to a ring where a and @a 615 615 // are variables in order to use maps 616 616 poly mp=minpoly; … … 621 621 // replace @a by a in minpoly and in LIFT 622 622 map phi=INTERRING,t,a,a; 623 mp=phi(mp); 623 mp=phi(mp); 624 624 LIFT=phi(LIFT); 625 625 // pass now to a ring whithout @a and with a as parameter … … 628 628 ideal LIFT=imap(INTERRING,LIFT); 629 629 kill INTERRING; 630 } 630 } 631 631 // then export LIFT 632 export(LIFT); 632 export(LIFT); 633 633 // test the result by resubstitution 634 setring GRUNDRING; 634 setring GRUNDRING; 635 635 list resubst; 636 636 if (noresubst==0) … … 641 641 } 642 642 else 643 { 643 { 644 644 resubst=tropicalliftingresubstitute(substitute(i,t,t^(TP[jj][2])),list(LIFTRING),N*TP[jj][2]); 645 645 } 646 646 } 647 647 setring BASERING; 648 // Finally, if t has been replaced by t^N, then we have to change the 648 // Finally, if t has been replaced by t^N, then we have to change the 649 649 // third entry of TP by multiplying by N. 650 650 if (noabs==1) … … 662 662 kill LIFTRING; 663 663 } 664 // if dd!=0 and the procedure was called without the 664 // if dd!=0 and the procedure was called without the 665 665 // option findAll, then it might very well 666 // be the case that no solution is found, since 666 // be the case that no solution is found, since 667 667 // only one solution for the zero-dimensional 668 // reduction was computed and this one might have 668 // reduction was computed and this one might have 669 669 // had cancellations when resubstituting; 670 670 // if so we have to restart the process with the option findAll … … 674 674 "The procedure will be restarted with the option 'findAll'."; 675 675 "Go on by hitting RETURN!"; 676 findall=1; 676 findall=1; 677 677 noabs=0; 678 678 setring CUTDOWNRING; … … 680 680 "i";i; 681 681 "ini";tInitialIdeal(i,w,1); 682 682 683 683 /* 684 684 setring GRUNDRING; … … 698 698 } 699 699 } 700 // if internally the option findall was set, then return 700 // if internally the option findall was set, then return 701 701 // only the first solution 702 702 if (defined(hadproblems)!=0) … … 707 707 if (voice+printlevel>=2) 708 708 { 709 709 710 710 "The procedure has created a list of lists. The jth entry of this list 711 711 contains a ring, an integer and an intvec. 712 712 In this ring lives an ideal representing the wanted lifting, 713 713 if the integer is N then in the parametrisation t has to be replaced by t^1/N, 714 and if the ith component of the intvec is w[i] then the ith component in LIFT 714 and if the ith component of the intvec is w[i] then the ith component in LIFT 715 715 should be multiplied by t^-w[i]/N in order to get the parametrisation. 716 716 717 717 Suppose your list has the name L, then you can access the 1st ring via: 718 718 "; 719 719 if (findall==1) 720 720 { 721 "def LIFTRing=L[1][1]; setring LIFTRing; LIFT; 721 "def LIFTRing=L[1][1]; setring LIFTRing; LIFT; 722 722 "; 723 723 } 724 724 else 725 725 { 726 "def LIFTRing=L[1]; setring LIFTRing; LIFT; 726 "def LIFTRing=L[1]; setring LIFTRing; LIFT; 727 727 "; 728 } 728 } 729 729 } 730 730 if (findall==1) // if all solutions have been computed, return a list of lists … … 751 751 def LIFTRing=LIST[1]; 752 752 setring LIFTRing; 753 // LIFT contains the first 4 terms of a point in the variety of i 753 // LIFT contains the first 4 terms of a point in the variety of i 754 754 // over the Puiseux series field C{{t}} whose order is -w[1]/w[0]=1 755 755 LIFT; … … 779 779 // NOTE: since the last component of v is positive, the lifting 780 780 // must start with a negative power of t, which in Singular 781 // is not allowed for a variable. 781 // is not allowed for a variable. 782 782 def LIFTRing3=LIST[1]; 783 783 setring LIFTRing3; … … 834 834 string Kstring="Z/"+string(char(LIFTRing))+"Z"; 835 835 } 836 // this means that tropicalLifting was called with 836 // this means that tropicalLifting was called with 837 837 // absolute primary decomposition 838 if (size(troplift)==4) 839 { 838 if (size(troplift)==4) 839 { 840 840 setring LIFTRing; 841 841 "The lifting of the point in the tropical variety lives in the ring"; 842 842 if ((size(LIFTpar)==0) and (N==1)) 843 843 { 844 Kstring+"[[t]]"; 844 Kstring+"[[t]]"; 845 845 } 846 846 if ((size(LIFTpar)==0) and (N!=1)) 847 847 { 848 Kstring+"[[t^(1/"+string(N)+")]]"; 848 Kstring+"[[t^(1/"+string(N)+")]]"; 849 849 } 850 850 if ((size(LIFTpar)!=0) and (N!=1)) 851 { 852 Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t^(1/"+string(N)+")]]"; 851 { 852 Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t^(1/"+string(N)+")]]"; 853 853 } 854 854 if ((size(LIFTpar)!=0) and (N==1)) 855 { 856 Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t]]"; 855 { 856 Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t]]"; 857 857 } 858 858 } … … 871 871 } 872 872 if ((size(LIFTpar)!=0) and (N!=1)) 873 { 874 Kstring+"["+LIFTpar+"]/M[[t^(1/"+string(N)+")]]"; 873 { 874 Kstring+"["+LIFTpar+"]/M[[t^(1/"+string(N)+")]]"; 875 875 "where M is the maximal ideal"; 876 876 "M=<"+m+">"; 877 877 } 878 878 if ((size(LIFTpar)!=0) and (N==1)) 879 { 880 Kstring+"["+LIFTpar+"]/M[[t]]"; 879 { 880 Kstring+"["+LIFTpar+"]/M[[t]]"; 881 881 "where M is the maximal ideal"; 882 882 "M=<"+m+">"; 883 } 883 } 884 884 } 885 885 ""; … … 908 908 } 909 909 } 910 } 910 } 911 911 } 912 912 example … … 922 922 923 923 /////////////////////////////////////////////////////////////////////////////// 924 /// Procedures concerned with drawing a tropical curve or a Newton subdivision 924 /// Procedures concerned with drawing a tropical curve or a Newton subdivision 925 925 /////////////////////////////////////////////////////////////////////////////// 926 926 927 927 proc tropicalCurve (def tp,list #) 928 928 "USAGE: tropicalCurve(tp[,#]); tp list, # optional list 929 ASSUME: tp is list of linear polynomials of the form ax+by+c 930 with integers a, b and a rational number c representing 929 ASSUME: tp is list of linear polynomials of the form ax+by+c 930 with integers a, b and a rational number c representing 931 931 a tropical Laurent polynomial defining a tropical plane curve; 932 alternatively tp can be a polynomial in Q(t)[x,y] defining a 933 tropical plane curve via the valuation map; 934 the basering must have a global monomial ordering, 932 alternatively tp can be a polynomial in Q(t)[x,y] defining a 933 tropical plane curve via the valuation map; 934 the basering must have a global monomial ordering, 935 935 two variables and up to one parameter! 936 RETURN: list, each entry i=1,...,size(l)-1 corresponds to a vertex 936 RETURN: list, each entry i=1,...,size(l)-1 corresponds to a vertex 937 937 in the tropical plane curve defined by tp 938 938 l[i][1] = x-coordinate of the ith vertex 939 939 l[i][2] = y-coordinate of the ith vertex 940 l[i][3] = intmat, if j is an entry in the first row 940 l[i][3] = intmat, if j is an entry in the first row 941 941 of intmat then the ith vertex of 942 the tropical curve is connected to the 942 the tropical curve is connected to the 943 943 jth vertex with multiplicity given 944 944 by the corresponding entry in the second row 945 l[i][4] = list of lists, the first entry of a list is 946 a primitive integer vector defining the direction 947 of an unbounded edge emerging from the ith vertex 948 of the graph, the corresponding second entry in 945 l[i][4] = list of lists, the first entry of a list is 946 a primitive integer vector defining the direction 947 of an unbounded edge emerging from the ith vertex 948 of the graph, the corresponding second entry in 949 949 the list is the multiplicity of the unbounded edge 950 l[i][5] = a polynomial whose monomials mark the vertices 950 l[i][5] = a polynomial whose monomials mark the vertices 951 951 in the Newton polygon corresponding to the entries 952 in tp which take the common minimum at the ith 953 vertex -- if some coefficient a or b of the 954 linear polynomials in the input was negative, 952 in tp which take the common minimum at the ith 953 vertex -- if some coefficient a or b of the 954 linear polynomials in the input was negative, 955 955 then each monomial has to be shifted by 956 956 the values in l[size(l)][3] 957 l[size(l)][1] = list, the entries describe the boundary 957 l[size(l)][1] = list, the entries describe the boundary 958 958 points of the Newton subdivision 959 l[size(l)][2] = list, the entries are pairs of integer 959 l[size(l)][2] = list, the entries are pairs of integer 960 960 vectors defining an interior 961 961 edge of the Newton subdivision 962 l[size(l)][3] = intvec, the monmials occuring in l[i][5] 963 have to be shifted by this vector 964 in order to represent marked 962 l[size(l)][3] = intvec, the monmials occuring in l[i][5] 963 have to be shifted by this vector 964 in order to represent marked 965 965 vertices in the Newton polygon 966 NOTE: here the tropical polynomial is supposed to be the MINIMUM 967 of the linear forms in tp, unless the optional input #[1] 966 NOTE: here the tropical polynomial is supposed to be the MINIMUM 967 of the linear forms in tp, unless the optional input #[1] 968 968 is the string 'max' 969 969 EXAMPLE: example tropicalCurve; shows an example" … … 978 978 ERROR("The basering should have a global monomial ordering, e.g. ring r=(0,t),(x,y),dp;"); 979 979 } 980 // if you insert a single polynomial instead of an ideal 980 // if you insert a single polynomial instead of an ideal 981 981 // representing a tropicalised polynomial, 982 // then we compute first the tropicalisation of this polynomial 982 // then we compute first the tropicalisation of this polynomial 983 983 // -- this feature is not documented in the above help string 984 984 if (typeof(tp)=="poly") 985 985 { 986 // exclude the case that the basering has not precisely 986 // exclude the case that the basering has not precisely 987 987 // one parameter and two indeterminates 988 988 if ((npars(basering)!=1) or (nvars(basering)!=2)) 989 989 { 990 ERROR("The basering should have precisely one parameter and two indeterminates!"); 990 ERROR("The basering should have precisely one parameter and two indeterminates!"); 991 991 } 992 992 poly f=tp; … … 997 997 if (nvars(basering) != 2) 998 998 { 999 ERROR("The basering should have precisely two indeterminates!"); 1000 } 1001 // -1) Exclude the pathological case that the defining 999 ERROR("The basering should have precisely two indeterminates!"); 1000 } 1001 // -1) Exclude the pathological case that the defining 1002 1002 // tropical polynomial has only one term, 1003 1003 // so that the tropical variety is not defined. … … 1007 1007 intmat M[2][1]=0,0; 1008 1008 return(list(list(0,0,M,list(),detropicalise(tp[1])),list(list(leadexp(detropicalise(tp[1]))),list()))); 1009 } 1010 // 0) If the input was a list of linear polynomials, 1009 } 1010 // 0) If the input was a list of linear polynomials, 1011 1011 // then some coefficient of x or y can be negative, 1012 // i.e. the input corresponds to the tropical curve 1012 // i.e. the input corresponds to the tropical curve 1013 1013 // of a Laurent polynomial. In that case we should 1014 // add some ax+by, so that all coefficients are positive. 1014 // add some ax+by, so that all coefficients are positive. 1015 1015 // This does not change the tropical curve. 1016 // however, we have to save (a,b), since the Newton 1016 // however, we have to save (a,b), since the Newton 1017 1017 // polygone has to be shifted by (-a,-b). 1018 1018 poly aa,bb; // koeffizienten … … 1026 1026 { 1027 1027 bb=koeffizienten(tp[i],2); 1028 } 1028 } 1029 1029 } 1030 1030 if ((aa!=0) or (bb!=0)) … … 1035 1035 } 1036 1036 } 1037 // 1) compute the vertices of the tropical curve 1037 // 1) compute the vertices of the tropical curve 1038 1038 // defined by tp and the Newton subdivision 1039 1039 list vtp=verticesTropicalCurve(tp,#); 1040 // if vtp is empty, then the Newton polygone is just 1040 // if vtp is empty, then the Newton polygone is just 1041 1041 // a line segment and constitutes a bunch of lines 1042 1042 // which can be computed by bunchOfLines … … 1045 1045 return(bunchOfLines(tp)); 1046 1046 } 1047 // 2) store all vertices belonging to the ith part of the 1047 // 2) store all vertices belonging to the ith part of the 1048 1048 // Newton subdivision in the list vtp[i] as 4th entry, 1049 1049 // and store those, which are not corners of the ith subdivision polygon 1050 1050 // in vtp[i][6] 1051 poly nwt; 1051 poly nwt; 1052 1052 list boundaryNSD; // stores the boundary of a Newton subdivision 1053 intmat zwsp[2][1]; // used for intermediate storage 1053 intmat zwsp[2][1]; // used for intermediate storage 1054 1054 for (i=1;i<=size(vtp);i++) 1055 1055 { 1056 1056 k=1; 1057 nwt=vtp[i][3]; // the polynomial representing the 1057 nwt=vtp[i][3]; // the polynomial representing the 1058 1058 // ith part of the Newton subdivision 1059 // store the vertices of the ith part of the 1059 // store the vertices of the ith part of the 1060 1060 // Newton subdivision in the list newton 1061 list newton; 1061 list newton; 1062 1062 while (nwt!=0) 1063 1063 { … … 1066 1066 k++; 1067 1067 } 1068 boundaryNSD=findOrientedBoundary(newton);// a list of the vertices 1069 // of the Newton subdivision 1070 // as integer vectors (only those 1071 // on the boundary, and oriented 1068 boundaryNSD=findOrientedBoundary(newton);// a list of the vertices 1069 // of the Newton subdivision 1070 // as integer vectors (only those 1071 // on the boundary, and oriented 1072 1072 // clockwise) 1073 1073 vtp[i][4]=boundaryNSD[1]; 1074 1074 vtp[i][5]=boundaryNSD[2]; 1075 vtp[i][6]=zwsp; // the entries of the first row will denote to which 1076 // vertex the ith one is connected 1077 // and the entries of the second row will denote 1075 vtp[i][6]=zwsp; // the entries of the first row will denote to which 1076 // vertex the ith one is connected 1077 // and the entries of the second row will denote 1078 1078 //with which multiplicity 1079 1079 kill newton; // we kill the superflous list 1080 1080 } 1081 // 3) Next we build for each part of the Newton 1081 // 3) Next we build for each part of the Newton 1082 1082 // subdivision the list of all pairs of vertices on the 1083 1083 // boundary, which are involved, including those which are not corners … … 1096 1096 kill ipairs; 1097 1097 } 1098 // 4) Check for all pairs of verticies in the Newton diagram if they 1098 // 4) Check for all pairs of verticies in the Newton diagram if they 1099 1099 // occur in two different parts of the Newton subdivision 1100 int deleted; // if a pair occurs in two NSD, it can be removed 1100 int deleted; // if a pair occurs in two NSD, it can be removed 1101 1101 // from both - deleted is then set to 1 1102 list inneredges; // contains the list of all pairs contained in two NSD 1102 list inneredges; // contains the list of all pairs contained in two NSD 1103 1103 // - these are inner the edges of NSD 1104 1104 int ggt; 1105 1105 d=1; // counts the inner edges 1106 1106 for (i=1;i<=size(pairs)-1;i++) 1107 { 1107 { 1108 1108 for (j=i+1;j<=size(pairs);j++) 1109 1109 { … … 1112 1112 deleted=0; 1113 1113 for (l=size(pairs[j]);l>=1 and deleted==0;l--) 1114 { 1114 { 1115 1115 if (((pairs[i][k][1]==pairs[j][l][1]) and (pairs[i][k][2]==pairs[j][l][2])) or ((pairs[i][k][1]==pairs[j][l][2]) and (pairs[i][k][2]==pairs[j][l][1]))) 1116 1116 { … … 1118 1118 d++; 1119 1119 ggt=abs(gcd(pairs[i][k][1][1]-pairs[i][k][2][1],pairs[i][k][1][2]-pairs[i][k][2][2])); 1120 zwsp=j,ggt; // and it is recorded that the ith and jth 1120 zwsp=j,ggt; // and it is recorded that the ith and jth 1121 1121 // vertex should be connected with mult ggt 1122 1122 vtp[i][6]=intmatconcat(vtp[i][6],zwsp); 1123 1123 zwsp=i,ggt; 1124 1124 vtp[j][6]=intmatconcat(vtp[j][6],zwsp); 1125 pairs[i]=delete(pairs[i],k); // finally the pair is deleted 1125 pairs[i]=delete(pairs[i],k); // finally the pair is deleted 1126 1126 // from both sets of pairs 1127 1127 pairs[j]=delete(pairs[j],l); … … 1163 1163 } 1164 1164 } 1165 // 6.3) Order the vertices such that passing from one to the next we 1165 // 6.3) Order the vertices such that passing from one to the next we 1166 1166 // travel along the boundary of the Newton polytope clock wise. 1167 1167 boundaryNSD=findOrientedBoundary(vertices); 1168 1168 list orderedvertices=boundaryNSD[1]; 1169 1169 // 7) Find the unbounded edges emerging from a vertex in the tropical curve. 1170 // For this we check the remaining pairs for the ith NSD. 1170 // For this we check the remaining pairs for the ith NSD. 1171 1171 // Each pair is ordered according 1172 // to the order in which the vertices occur in orderedvertices. 1172 // to the order in which the vertices occur in orderedvertices. 1173 1173 // The direction of the 1174 // unbounded edge is then the outward pointing primitive normal 1174 // unbounded edge is then the outward pointing primitive normal 1175 1175 // vector to the vector 1176 1176 // pointing from the first vertex in a pair to the second one. … … 1182 1182 for (i=1;i<=size(pairs);i++) 1183 1183 { 1184 list ubedges; // stores the unbounded edges 1184 list ubedges; // stores the unbounded edges 1185 1185 k=1; // counts the unbounded edges 1186 1186 for (j=1;j<=size(pairs[i]);j++) 1187 1187 { 1188 1188 // computes the position of the vertices in the 1189 pos1=positionInList(orderedvertices,pairs[i][j][1]); 1189 pos1=positionInList(orderedvertices,pairs[i][j][1]); 1190 1190 // pair in the list orderedvertices 1191 pos2=positionInList(orderedvertices,pairs[i][j][2]); 1191 pos2=positionInList(orderedvertices,pairs[i][j][2]); 1192 1192 if (((pos1>pos2) and !((pos1==size(orderedvertices)) and (pos2==1))) or ((pos2==size(orderedvertices)) and (pos1==1))) // reorders them if necessary 1193 1193 { … … 1197 1197 } 1198 1198 // the vector pointing from vertex 1 in the pair to vertex2 1199 normalvector=pairs[i][j][2]-pairs[i][j][1]; 1199 normalvector=pairs[i][j][2]-pairs[i][j][1]; 1200 1200 ggt=gcd(normalvector[1],normalvector[2]); // the gcd of the entries 1201 1201 zw=normalvector[2]; // create the outward pointing normal vector … … 1229 1229 kill ubedges; 1230 1230 } 1231 // 8) Store the computed information for the ith part 1231 // 8) Store the computed information for the ith part 1232 1232 // of the NSD in the list graph[i]. 1233 1233 list graph,gr; … … 1235 1235 { 1236 1236 // the first coordinate of the ith vertex of the tropical curve 1237 gr[1]=vtp[i][1]; 1237 gr[1]=vtp[i][1]; 1238 1238 // the second coordinate of the ith vertex of the tropical curve 1239 gr[2]=vtp[i][2]; 1239 gr[2]=vtp[i][2]; 1240 1240 // to which vertices is the ith vertex of the tropical curve connected 1241 gr[3]=vtp[i][6]; 1242 // the directions unbounded edges emerging from the ith 1241 gr[3]=vtp[i][6]; 1242 // the directions unbounded edges emerging from the ith 1243 1243 // vertex of the trop. curve 1244 gr[4]=vtp[i][7]; 1245 // the vertices of the boundary of the ith part of the NSD 1246 gr[5]=vtp[i][3]; 1244 gr[4]=vtp[i][7]; 1245 // the vertices of the boundary of the ith part of the NSD 1246 gr[5]=vtp[i][3]; 1247 1247 graph[i]=gr; 1248 1248 } … … 1263 1263 } 1264 1264 } 1265 // 10) Finally store the boundary vertices and 1265 // 10) Finally store the boundary vertices and 1266 1266 // the inner edges as last entry in the list graph. 1267 1267 // This represents the NSD. … … 1280 1280 // the coordinates of the first vertex are graph[1][1],graph[1][2]; 1281 1281 graph[1][1],graph[1][2]; 1282 // the first vertex is connected to the vertices 1282 // the first vertex is connected to the vertices 1283 1283 // graph[1][3][1,1..ncols(graph[1][3])] 1284 1284 intmat M=graph[1][3]; 1285 1285 M[1,1..ncols(graph[1][3])]; 1286 // the weights of the edges to these vertices are 1286 // the weights of the edges to these vertices are 1287 1287 // graph[1][3][2,1..ncols(graph[1][3])] 1288 1288 M[2,1..ncols(graph[1][3])]; 1289 1289 // from the first vertex emerge size(graph[1][4]) unbounded edges 1290 1290 size(graph[1][4]); 1291 // the primitive integral direction vector of the first unbounded edge 1291 // the primitive integral direction vector of the first unbounded edge 1292 1292 // of the first vertex 1293 1293 graph[1][4][1][1]; 1294 1294 // the weight of the first unbounded edge of the first vertex 1295 1295 graph[1][4][1][2]; 1296 // the monomials which are part of the Newton subdivision of the first vertex 1296 // the monomials which are part of the Newton subdivision of the first vertex 1297 1297 graph[1][5]; 1298 // connecting the points in graph[size(graph)][1] we get 1298 // connecting the points in graph[size(graph)][1] we get 1299 1299 // the boundary of the Newton polytope 1300 1300 graph[size(graph)][1]; 1301 // an entry in graph[size(graph)][2] is a pair of points 1301 // an entry in graph[size(graph)][2] is a pair of points 1302 1302 // in the Newton polytope bounding an inner edge 1303 1303 graph[size(graph)][2][1]; … … 1308 1308 proc drawTropicalCurve (def f,list #) 1309 1309 "USAGE: drawTropicalCurve(f[,#]); f poly or list, # optional list 1310 ASSUME: f is list of linear polynomials of the form ax+by+c with 1311 integers a, b and a rational number c representing a tropical 1310 ASSUME: f is list of linear polynomials of the form ax+by+c with 1311 integers a, b and a rational number c representing a tropical 1312 1312 Laurent polynomial defining a tropical plane curve; 1313 alternatively f can be a polynomial in Q(t)[x,y] defining 1314 a tropical plane curve via the valuation map; 1315 the basering must have a global monomial ordering, two 1313 alternatively f can be a polynomial in Q(t)[x,y] defining 1314 a tropical plane curve via the valuation map; 1315 the basering must have a global monomial ordering, two 1316 1316 variables and up to one parameter! 1317 1317 RETURN: NONE 1318 NOTE: - the procedure creates the files /tmp/tropicalcurveNUMBER.tex and 1319 /tmp/tropicalcurveNUMBER.ps, where NUMBER is a random four 1320 digit integer; 1318 NOTE: - the procedure creates the files /tmp/tropicalcurveNUMBER.tex and 1319 /tmp/tropicalcurveNUMBER.ps, where NUMBER is a random four 1320 digit integer; 1321 1321 moreover it displays the tropical curve via kghostview; 1322 if you wish to remove all these files from /tmp, 1322 if you wish to remove all these files from /tmp, 1323 1323 call the procedure cleanTmp 1324 1324 @* - edges with multiplicity greater than one carry this multiplicity 1325 1325 @* - if # is empty, then the tropical curve is computed w.r.t. minimum, 1326 if #[1] is the string 'max', then it is computed w.r.t. maximum 1327 @* - if the last optional argument is 'onlytexfile' then only the 1328 latex file is produced; this option should be used if kghostview 1326 if #[1] is the string 'max', then it is computed w.r.t. maximum 1327 @* - if the last optional argument is 'onlytexfile' then only the 1328 latex file is produced; this option should be used if kghostview 1329 1329 is not installed on your system 1330 @* - note that lattice points in the Newton subdivision which are 1331 black correspond to markings of the marked subdivision, 1330 @* - note that lattice points in the Newton subdivision which are 1331 black correspond to markings of the marked subdivision, 1332 1332 while lattice points in grey are not marked 1333 1333 EXAMPLE: example drawTropicalCurve shows an example" … … 1347 1347 if (typeof(f)=="poly") 1348 1348 { 1349 // exclude the case that the basering has not precisely 1349 // exclude the case that the basering has not precisely 1350 1350 // one parameter and two indeterminates 1351 1351 if ((npars(basering)!=1) or (nvars(basering)!=2)) 1352 1352 { 1353 ERROR("The basering should have precisely one parameter and two indeterminates!"); 1353 ERROR("The basering should have precisely one parameter and two indeterminates!"); 1354 1354 } 1355 1355 texf=texPolynomial(f); // write the polynomial over Q(t) … … 1362 1362 texf="\\mbox{\\tt The defining equation was not handed over!}"; 1363 1363 list graph=f; 1364 } 1364 } 1365 1365 else 1366 1366 { // write the tropical polynomial defined by f 1367 1367 if (size(#)==0) 1368 { 1368 { 1369 1369 texf="\\min\\{"; 1370 1370 } … … 1375 1375 for (j=1;j<=size(f);j++) 1376 1376 { 1377 texf=texf+texPolynomial(f[j]); 1377 texf=texf+texPolynomial(f[j]); 1378 1378 if (j<size(f)) 1379 1379 { … … 1384 1384 texf=texf+"\\}"; 1385 1385 } 1386 } 1386 } 1387 1387 list graph=tropicalCurve(f,#); // the graph of the tropical polynomial f 1388 1388 } … … 1402 1402 \\addtolength{\\topmargin}{-\\headheight} 1403 1403 \\addtolength{\\topmargin}{-\\topskip} 1404 \\setlength{\\textheight}{267mm} 1404 \\setlength{\\textheight}{267mm} 1405 1405 \\addtolength{\\textheight}{\\topskip} 1406 1406 \\addtolength{\\textheight}{-\\footskip} 1407 1407 \\addtolength{\\textheight}{-30pt} 1408 \\setlength{\\oddsidemargin}{-1in} 1408 \\setlength{\\oddsidemargin}{-1in} 1409 1409 \\addtolength{\\oddsidemargin}{20mm} 1410 1410 \\setlength{\\evensidemargin}{\\oddsidemargin} 1411 \\setlength{\\textwidth}{170mm} 1411 \\setlength{\\textwidth}{170mm} 1412 1412 1413 1413 \\begin{document} 1414 1414 \\parindent0cm 1415 1415 \\begin{center} 1416 \\large\\bf The Tropicalisation of 1416 \\large\\bf The Tropicalisation of 1417 1417 1418 1418 \\bigskip … … 1438 1438 1439 1439 \\begin{center} 1440 "+texDrawNewtonSubdivision(graph,#)+" 1440 "+texDrawNewtonSubdivision(graph,#)+" 1441 1441 \\end{center} 1442 1442 \\end{document}"; … … 1445 1445 int rdnum=random(1000,9999); 1446 1446 write(":w /tmp/tropicalcurve"+string(rdnum)+".tex",TEXBILD); 1447 system("sh","cd /tmp; latex /tmp/tropicalcurve"+string(rdnum)+".tex; dvips /tmp/tropicalcurve"+string(rdnum)+".dvi -o; /bin/rm tropicalcurve"+string(rdnum)+".log; /bin/rm tropicalcurve"+string(rdnum)+".aux; /bin/rm tropicalcurve"+string(rdnum)+".ps?; /bin/rm tropicalcurve"+string(rdnum)+".dvi; kghostview tropicalcurve"+string(rdnum)+".ps &"); 1447 system("sh","cd /tmp; latex /tmp/tropicalcurve"+string(rdnum)+".tex; dvips /tmp/tropicalcurve"+string(rdnum)+".dvi -o; /bin/rm tropicalcurve"+string(rdnum)+".log; /bin/rm tropicalcurve"+string(rdnum)+".aux; /bin/rm tropicalcurve"+string(rdnum)+".ps?; /bin/rm tropicalcurve"+string(rdnum)+".dvi; kghostview tropicalcurve"+string(rdnum)+".ps &"); 1448 1448 } 1449 1449 else … … 1472 1472 proc drawNewtonSubdivision (def f,list #) 1473 1473 "USAGE: drawTropicalCurve(f[,#]); f poly, # optional list 1474 ASSUME: f is list of linear polynomials of the form ax+by+c with integers 1475 a, b and a rational number c representing a tropical Laurent 1474 ASSUME: f is list of linear polynomials of the form ax+by+c with integers 1475 a, b and a rational number c representing a tropical Laurent 1476 1476 polynomial defining a tropical plane curve; 1477 alternatively f can be a polynomial in Q(t)[x,y] defining a tropical 1478 plane curve via the valuation map; 1479 the basering must have a global monomial ordering, two variables 1477 alternatively f can be a polynomial in Q(t)[x,y] defining a tropical 1478 plane curve via the valuation map; 1479 the basering must have a global monomial ordering, two variables 1480 1480 and up to one parameter! 1481 1481 RETURN: NONE 1482 NOTE: - the procedure creates the files /tmp/newtonsubdivisionNUMBER.tex, 1483 and /tmp/newtonsubdivisionNUMBER.ps, where NUMBER is a random 1484 four digit integer; 1482 NOTE: - the procedure creates the files /tmp/newtonsubdivisionNUMBER.tex, 1483 and /tmp/newtonsubdivisionNUMBER.ps, where NUMBER is a random 1484 four digit integer; 1485 1485 moreover it desplays the tropical curve defined by f via kghostview; 1486 if you wish to remove all these files from /tmp, call the procedure 1486 if you wish to remove all these files from /tmp, call the procedure 1487 1487 cleanTmp; 1488 @* if # is empty, then the tropical curve is computed w.r.t. minimum, 1489 if #[1] is the string 'max', then it is computed w.r.t. maximum 1490 @* - note that lattice points in the Newton subdivision which are black 1491 correspond to markings of the marked subdivision, while lattice 1488 @* if # is empty, then the tropical curve is computed w.r.t. minimum, 1489 if #[1] is the string 'max', then it is computed w.r.t. maximum 1490 @* - note that lattice points in the Newton subdivision which are black 1491 correspond to markings of the marked subdivision, while lattice 1492 1492 points in grey are not marked 1493 1493 EXAMPLE: example drawNewtonSubdivision; shows an example" … … 1503 1503 { // write the tropical polynomial defined by f 1504 1504 if (size(#)==0) 1505 { 1505 { 1506 1506 texf="\\min\\{"; 1507 1507 } … … 1512 1512 for (j=1;j<=size(f);j++) 1513 1513 { 1514 texf=texf+texPolynomial(f[j]); 1514 texf=texf+texPolynomial(f[j]); 1515 1515 if (j<size(f)) 1516 1516 { … … 1521 1521 texf=texf+"\\}"; 1522 1522 } 1523 } 1523 } 1524 1524 list graph=tropicalCurve(f,#); // the graph of the tropical polynomial f 1525 1525 } … … 1529 1529 \\parindent0cm 1530 1530 \\begin{center} 1531 \\large\\bf The Newtonsubdivison of 1531 \\large\\bf The Newtonsubdivison of 1532 1532 \\begin{displaymath} 1533 1533 f="+texf+" … … 1537 1537 1538 1538 \\begin{center} 1539 "+texDrawNewtonSubdivision(graph)+ 1539 "+texDrawNewtonSubdivision(graph)+ 1540 1540 " \\end{center} 1541 1541 … … 1543 1543 int rdnum=random(1000,9999); 1544 1544 write(":w /tmp/newtonsubdivision"+string(rdnum)+".tex",TEXBILD); 1545 system("sh","cd /tmp; latex /tmp/newtonsubdivision"+string(rdnum)+".tex; dvips /tmp/newtonsubdivision"+string(rdnum)+".dvi -o; /bin/rm newtonsubdivision"+string(rdnum)+".log; /bin/rm newtonsubdivision"+string(rdnum)+".aux; /bin/rm newtonsubdivision"+string(rdnum)+".ps?; /bin/rm newtonsubdivision"+string(rdnum)+".dvi; kghostview newtonsubdivision"+string(rdnum)+".ps &"); 1545 system("sh","cd /tmp; latex /tmp/newtonsubdivision"+string(rdnum)+".tex; dvips /tmp/newtonsubdivision"+string(rdnum)+".dvi -o; /bin/rm newtonsubdivision"+string(rdnum)+".log; /bin/rm newtonsubdivision"+string(rdnum)+".aux; /bin/rm newtonsubdivision"+string(rdnum)+".ps?; /bin/rm newtonsubdivision"+string(rdnum)+".dvi; kghostview newtonsubdivision"+string(rdnum)+".ps &"); 1546 1546 // return(TEXBILD); 1547 1547 } … … 1568 1568 proc tropicalJInvariant (def f,list #) 1569 1569 "USAGE: tropicalJInvariant(f[,#]); f poly or list, # optional list 1570 ASSUME: f is list of linear polynomials of the form ax+by+c with integers 1571 a, b and a rational number c representing a tropical Laurent 1570 ASSUME: f is list of linear polynomials of the form ax+by+c with integers 1571 a, b and a rational number c representing a tropical Laurent 1572 1572 polynomial defining a tropical plane curve; 1573 alternatively f can be a polynomial in Q(t)[x,y] defining a 1574 tropical plane curve via the valuation map; 1575 @* the basering must have a global monomial ordering, two variables 1573 alternatively f can be a polynomial in Q(t)[x,y] defining a 1574 tropical plane curve via the valuation map; 1575 @* the basering must have a global monomial ordering, two variables 1576 1576 and up to one parameter! 1577 RETURN: number, if the graph underlying the tropical curve has precisely 1578 one loop then its weighted lattice length is returned, 1577 RETURN: number, if the graph underlying the tropical curve has precisely 1578 one loop then its weighted lattice length is returned, 1579 1579 otherwise the result will be -1 1580 NOTE: - if the tropical curve is elliptic and its embedded graph has 1581 precisely one loop, then the weigthed lattice length of 1580 NOTE: - if the tropical curve is elliptic and its embedded graph has 1581 precisely one loop, then the weigthed lattice length of 1582 1582 the loop is its tropical j-invariant 1583 @* - the procedure checks if the embedded graph of the tropical 1584 curve has genus one, but it does NOT check if the loop can 1585 be resolved, so that the curve is not a proper tropical 1586 elliptic curve 1587 @* - if the embedded graph of a tropical elliptic curve has more 1588 than one loop, then all but one can be resolved, but this is 1589 not observed by this procedure, so it will not compute 1583 @* - the procedure checks if the embedded graph of the tropical 1584 curve has genus one, but it does NOT check if the loop can 1585 be resolved, so that the curve is not a proper tropical 1586 elliptic curve 1587 @* - if the embedded graph of a tropical elliptic curve has more 1588 than one loop, then all but one can be resolved, but this is 1589 not observed by this procedure, so it will not compute 1590 1590 the j-invariant 1591 1591 @* - if # is empty, then the tropical curve is computed w.r.t. minimum, 1592 if #[1] is the string 'max', then it is computed w.r.t. maximum 1593 @* - the tropicalJInvariant of a plane tropical cubic is the 1594 'cycle length' of the cubic as introduced in the paper: 1595 Eric Katz, Hannah Markwig, Thomas Markwig: The j-invariant 1592 if #[1] is the string 'max', then it is computed w.r.t. maximum 1593 @* - the tropicalJInvariant of a plane tropical cubic is the 1594 'cycle length' of the cubic as introduced in the paper: 1595 Eric Katz, Hannah Markwig, Thomas Markwig: The j-invariant 1596 1596 of a cubic tropical plane curve. 1597 1597 EXAMPLE: example tropicalJInvariant; shows an example" … … 1607 1607 { 1608 1608 if (typeof(f[1])=="list") 1609 { 1609 { 1610 1610 list graph=f; 1611 1611 } … … 1619 1619 { 1620 1620 ERROR("This is no valid input."); 1621 } 1621 } 1622 1622 } 1623 1623 } … … 1636 1636 genus=-genus/2; // we have counted each bounded edge twice 1637 1637 genus=genus+size(graph); // the genus is 1-#bounded_edges+#vertices 1638 // 3) if the embedded graph has not genus one, 1638 // 3) if the embedded graph has not genus one, 1639 1639 // we cannot compute the j-invariant 1640 1640 if(genus!=1) … … 1648 1648 else 1649 1649 { 1650 intmat nullmat[2][1]; // used to set 1651 // 4) find a vertex which has only one bounded edge, 1652 // if none exists zero is returned, 1650 intmat nullmat[2][1]; // used to set 1651 // 4) find a vertex which has only one bounded edge, 1652 // if none exists zero is returned, 1653 1653 // otherwise the number of the vertex in the list graph 1654 int nonloopvertex=findNonLoopVertex(graph); 1654 int nonloopvertex=findNonLoopVertex(graph); 1655 1655 int dv; //checks if vert. has been found to which nonloopvertex is connected 1656 intmat delvert; // takes for a moment graph[i][3] of the vertex 1656 intmat delvert; // takes for a moment graph[i][3] of the vertex 1657 1657 // to which nonloopvertex is connected 1658 // 5) delete successively vertices in the graph which 1658 // 5) delete successively vertices in the graph which 1659 1659 // have only one bounded edge 1660 1660 while (nonloopvertex>0) 1661 1661 { 1662 // find the only vertex to which the nonloopvertex 1662 // find the only vertex to which the nonloopvertex 1663 1663 // is connected, when it is found 1664 1664 // delete the connection in graph[i][3] and set dv=1 … … 1673 1673 { 1674 1674 delvert=graph[i][3]; 1675 delvert=intmatcoldelete(delvert,j); // delete the connection (note 1675 delvert=intmatcoldelete(delvert,j); // delete the connection (note 1676 1676 // there must have been two!) 1677 1677 dv=1; … … 1681 1681 } 1682 1682 } 1683 graph[nonloopvertex][3]=nullmat; // the only connection of nonloopvertex 1683 graph[nonloopvertex][3]=nullmat; // the only connection of nonloopvertex 1684 1684 // is killed 1685 nonloopvertex=findNonLoopVertex(graph); // find the next vertex 1685 nonloopvertex=findNonLoopVertex(graph); // find the next vertex 1686 1686 // which has only one edge 1687 1687 } … … 1689 1689 intvec loop,weights; // encodes the loop and the edges 1690 1690 i=1; 1691 // start by finding some vertex which belongs to the loop 1692 while (loop==0) 1691 // start by finding some vertex which belongs to the loop 1692 while (loop==0) 1693 1693 { 1694 1694 // if graph[i][3] of a vertex in the loop has 2 columns, all others have 1 1695 if (ncols(graph[i][3])==1) 1695 if (ncols(graph[i][3])==1) 1696 1696 { 1697 1697 i++; … … 1699 1699 else 1700 1700 { 1701 loop[1]=i; // a starting vertex is found 1702 loop[2]=graph[i][3][1,1]; // it is connected to vertex with this number 1701 loop[1]=i; // a starting vertex is found 1702 loop[2]=graph[i][3][1,1]; // it is connected to vertex with this number 1703 1703 weights[2]=graph[i][3][2,1]; // and the edge has this weight 1704 1704 } … … 1708 1708 while (j!=i) // the loop ends with the same vertex with which it starts 1709 1709 { 1710 // the first row of graph[j][3] has two entries 1710 // the first row of graph[j][3] has two entries 1711 1711 // corresponding to the two vertices 1712 // to which the active vertex j is connected; 1712 // to which the active vertex j is connected; 1713 1713 // one is loop[k-1], i.e. the one which 1714 1714 // precedes j in the loop; we have to choose the other one 1715 if (graph[j][3][1,1]==loop[k-1]) 1715 if (graph[j][3][1,1]==loop[k-1]) 1716 1716 { 1717 1717 loop[k+1]=graph[j][3][1,2]; … … 1724 1724 } 1725 1725 j=loop[k+1]; // set loop[k+1] the new active vertex 1726 k++; 1727 } 1726 k++; 1727 } 1728 1728 // 7) compute for each edge in the loop the lattice length 1729 poly xcomp,ycomp; // the x- and y-components of the vectors 1729 poly xcomp,ycomp; // the x- and y-components of the vectors 1730 1730 // connecting two vertices of the loop 1731 number nenner; // the product of the denominators of 1731 number nenner; // the product of the denominators of 1732 1732 // the x- and y-components 1733 1733 number jinvariant; // the j-invariant 1734 int eins,zwei,ggt; 1734 int eins,zwei,ggt; 1735 1735 for (i=1;i<=size(loop)-1;i++) // compute the lattice length for each edge 1736 1736 { 1737 xcomp=graph[loop[i]][1]-graph[loop[i+1]][1]; 1738 ycomp=graph[loop[i]][2]-graph[loop[i+1]][2]; 1737 xcomp=graph[loop[i]][1]-graph[loop[i+1]][1]; 1738 ycomp=graph[loop[i]][2]-graph[loop[i+1]][2]; 1739 1739 nenner=denominator(leadcoef(xcomp))*denominator(leadcoef(ycomp)); 1740 execute("eins="+string(numerator(leadcoef(nenner*xcomp)))+";"); 1741 execute("zwei="+string(numerator(leadcoef(nenner*ycomp)))+";"); 1740 execute("eins="+string(numerator(leadcoef(nenner*xcomp)))+";"); 1741 execute("zwei="+string(numerator(leadcoef(nenner*ycomp)))+";"); 1742 1742 ggt=gcd(eins,zwei); // the lattice length is the "gcd" 1743 1743 // of the x-component and the y-component 1744 jinvariant=jinvariant+ggt/(nenner*weights[i+1]); // divided by the 1744 jinvariant=jinvariant+ggt/(nenner*weights[i+1]); // divided by the 1745 1745 // weight of the edge 1746 1746 } 1747 return(jinvariant); 1747 return(jinvariant); 1748 1748 } 1749 1749 } … … 1759 1759 // the curve can have arbitrary degree 1760 1760 tropicalJInvariant(t*(x7+y7+1)+1/t*(x4+y4+x2+y2+x3y+xy3)+1/t7*x2y2); 1761 // the procedure does not realise, if the embedded graph of the tropical 1761 // the procedure does not realise, if the embedded graph of the tropical 1762 1762 // curve has a loop that can be resolved 1763 1763 tropicalJInvariant(1+x+y+xy+tx2y+txy2); 1764 1764 // but it does realise, if the curve has no loop at all ... 1765 1765 tropicalJInvariant(x+y+1); 1766 // or if the embedded graph has more than one loop - even if only one 1766 // or if the embedded graph has more than one loop - even if only one 1767 1767 // cannot be resolved 1768 1768 tropicalJInvariant(1+x+y+xy+tx2y+txy2+t3x5+t3y5+tx2y2+t2xy4+t2yx4); … … 1773 1773 proc weierstrassForm (poly f,list #) 1774 1774 "USAGE: weierstrassForm(wf[,#]); wf poly, # list 1775 ASSUME: wf is a a polynomial whose Newton polygon has precisely one 1776 interior lattice point, so that it defines an elliptic curve 1775 ASSUME: wf is a a polynomial whose Newton polygon has precisely one 1776 interior lattice point, so that it defines an elliptic curve 1777 1777 on the toric surface corresponding to the Newton polygon 1778 1778 RETURN: poly, the Weierstrass normal form of the polynomial … … 1780 1780 to Fernando Rodriguez Villegas, villegas@math.utexas.edu 1781 1781 @* - the characteristic of the base field should not be 2 or 3 1782 @* - if an additional argument # is given, a simplified Weierstrass 1782 @* - if an additional argument # is given, a simplified Weierstrass 1783 1783 form is computed 1784 1784 EXAMPLE: example weierstrassForm; shows an example" … … 1841 1841 1842 1842 proc jInvariant (poly f,list #) 1843 "USAGE: jInvariant(f[,#]); f poly, # list 1844 ASSUME: - f is a a polynomial whose Newton polygon has precisely one 1845 interior lattice point, so that it defines an elliptic curve 1843 "USAGE: jInvariant(f[,#]); f poly, # list 1844 ASSUME: - f is a a polynomial whose Newton polygon has precisely one 1845 interior lattice point, so that it defines an elliptic curve 1846 1846 on the toric surface corresponding to the Newton polygon 1847 @* - it the optional argument # is present the base field should be 1848 Q(t) and the optional argument should be one of the following 1847 @* - it the optional argument # is present the base field should be 1848 Q(t) and the optional argument should be one of the following 1849 1849 strings: 1850 @* 'ord' : then the return value is of type integer, 1850 @* 'ord' : then the return value is of type integer, 1851 1851 namely the order of the j-invariant 1852 @* 'split' : then the return value is a list of two polynomials, 1852 @* 'split' : then the return value is a list of two polynomials, 1853 1853 such that the quotient of these two is the j-invariant 1854 1854 RETURN: poly, the j-invariant of the elliptic curve defined by poly 1855 NOTE: the characteristic of the base field should not be 2 or 3, 1855 NOTE: the characteristic of the base field should not be 2 or 3, 1856 1856 unless the input is a plane cubic 1857 1857 EXAMPLE: example jInvariant; shows an example" … … 1879 1879 echo=2; 1880 1880 ring r=(0,t),(x,y),dp; 1881 // jInvariant computes the j-invariant of a cubic 1881 // jInvariant computes the j-invariant of a cubic 1882 1882 jInvariant(x+y+x2y+y3+1/t*xy); 1883 // if the ground field has one parameter t, then we can instead 1883 // if the ground field has one parameter t, then we can instead 1884 1884 // compute the order of the j-invariant 1885 1885 jInvariant(x+y+x2y+y3+1/t*xy,"ord"); … … 1889 1889 poly h=x22y11+x19y10+x17y9+x16y9+x12y7+x9y6+x7y5+x2y3+x14y8; 1890 1890 // its j-invariant is 1891 jInvariant(h); 1891 jInvariant(h); 1892 1892 } 1893 1893 … … 1908 1908 @* l[6] = a list containing the vertices of the tropical conic f 1909 1909 @* l[7] = a list containing lists with vertices of the tangents 1910 @* l[8] = a string which contains the latex-code to draw the 1910 @* l[8] = a string which contains the latex-code to draw the 1911 1911 tropical conic and its tropicalised tangents 1912 1912 @* l[9] = if # is non-empty, this is the same data for the dual … … 1932 1932 ring LINRING=(0,t),(x,y,a(1..6)),lp; 1933 1933 list points=imap(BASERING,points); 1934 ideal I; // the ideal will contain the linear equations given by the conic 1934 ideal I; // the ideal will contain the linear equations given by the conic 1935 1935 // and the points 1936 1936 for (i=1;i<=5;i++) … … 1953 1953 ring tRING=0,t,ls; 1954 1954 list pointdenom=imap(BASERING,pointdenom); 1955 list pointnum=imap(BASERING,pointnum); 1955 list pointnum=imap(BASERING,pointnum); 1956 1956 intvec pointcoordinates; 1957 1957 for (i=1;i<=size(pointdenom);i++) … … 2029 2029 We consider the concic through the following five points: 2030 2030 \\begin{displaymath} 2031 "; 2031 "; 2032 2032 string texf=texDrawTropical(graphf,list("",scalefactor)); 2033 2033 for (i=1;i<=size(points);i++) … … 2067 2067 \\end{document}"; 2068 2068 setring BASERING; 2069 // If # non-empty, compute the dual conic and the tangents 2070 // through the dual points 2069 // If # non-empty, compute the dual conic and the tangents 2070 // through the dual points 2071 2071 // corresponding to the tangents of the given conic. 2072 2072 if (size(#)>0) 2073 2073 { 2074 2074 list dualpoints; 2075 for (i=1;i<=size(points);i++) 2075 for (i=1;i<=size(points);i++) 2076 2076 { 2077 2077 dualpoints[i]=list(leadcoef(tangents[i])/substitute(tangents[i],x,0,y,0),leadcoef(tangents[i]-lead(tangents[i]))/substitute(tangents[i],x,0,y,0)); … … 2097 2097 // conic[2] is the equation of the conic f passing through the five points 2098 2098 conic[2]; 2099 // conic[3] is a list containing the equations of the tangents 2099 // conic[3] is a list containing the equations of the tangents 2100 2100 // through the five points 2101 2101 conic[3]; 2102 2102 // conic[4] is an ideal representing the tropicalisation of the conic f 2103 2103 conic[4]; 2104 // conic[5] is a list containing the tropicalisation 2104 // conic[5] is a list containing the tropicalisation 2105 2105 // of the five tangents in conic[3] 2106 2106 conic[5]; 2107 // conic[6] is a list containing the vertices of the tropical conic 2107 // conic[6] is a list containing the vertices of the tropical conic 2108 2108 conic[6]; 2109 2109 // conic[7] is a list containing the vertices of the five tangents 2110 2110 conic[7]; 2111 // conic[8] contains the latex code to draw the tropical conic and 2112 // its tropicalised tangents; it can written in a file, processed and 2113 // displayed via kghostview 2114 write(":w /tmp/conic.tex",conic[8]); 2115 system("sh","cd /tmp; latex /tmp/conic.tex; dvips /tmp/conic.dvi -o; 2111 // conic[8] contains the latex code to draw the tropical conic and 2112 // its tropicalised tangents; it can written in a file, processed and 2113 // displayed via kghostview 2114 write(":w /tmp/conic.tex",conic[8]); 2115 system("sh","cd /tmp; latex /tmp/conic.tex; dvips /tmp/conic.dvi -o; 2116 2116 kghostview conic.ps &"); 2117 // with an optional argument the same information for the dual conic is computed 2117 // with an optional argument the same information for the dual conic is computed 2118 2118 // and saved in conic[9] 2119 2119 conic=conicWithTangents(points,1); 2120 2120 conic[9][2]; // the equation of the dual conic 2121 2121 } 2122 2122 2123 2123 /////////////////////////////////////////////////////////////////////////////// 2124 2124 /// Procedures concerned with tropicalisation … … 2129 2129 ASSUME: f is a polynomial in Q(t)[x_1,...,x_n] 2130 2130 RETURN: list, the linear forms of the tropicalisation of f 2131 NOTE: if # is empty, then the valuation of t will be 1, 2132 @* if # is the string 'max' it will be -1; 2133 @* the latter supposes that we consider the maximum of the 2131 NOTE: if # is empty, then the valuation of t will be 1, 2132 @* if # is the string 'max' it will be -1; 2133 @* the latter supposes that we consider the maximum of the 2134 2134 computed linear forms, the former that we consider their minimum 2135 2135 EXAMPLE: example tropicalise; shows an example" … … 2154 2154 { 2155 2155 tropicalf[i]=tropicalf[i]+exp[j]*var(j); 2156 } 2156 } 2157 2157 f=f-lead(f); 2158 2158 } … … 2194 2194 ///////////////////////////////////////////////////////////////////////// 2195 2195 2196 proc tInitialForm (poly f, intvec w) 2196 proc tInitialForm (poly f, intvec w) 2197 2197 "USAGE: tInitialForm(f,w); f a polynomial, w an integer vector 2198 2198 ASSUME: f is a polynomial in Q[t,x_1,...,x_n] and w=(w_0,w_1,...,w_n) 2199 2199 RETURN: poly, the t-initialform of f(t,x) w.r.t. w evaluated at t=1 2200 NOTE: the t-initialform is the sum of the terms with MAXIMAL 2200 NOTE: the t-initialform is the sum of the terms with MAXIMAL 2201 2201 weighted order w.r.t. w 2202 2202 EXAMPLE: example tInitialForm; shows an example" … … 2208 2208 // do the same for the remaining part of f and compare the results 2209 2209 // keep only the smallest ones 2210 int vglgewicht; 2211 f=f-lead(f); 2210 int vglgewicht; 2211 f=f-lead(f); 2212 2212 while (f!=0) 2213 2213 { … … 2224 2224 initialf=initialf+lead(f); 2225 2225 } 2226 } 2226 } 2227 2227 f=f-lead(f); 2228 2228 } … … 2244 2244 proc tInitialIdeal (ideal i,intvec w,list #) 2245 2245 "USAGE: tInitialIdeal(i,w); i ideal, w intvec 2246 ASSUME: i is an ideal in Q[t,x_1,...,x_n] and w=(w_0,...,w_n) 2246 ASSUME: i is an ideal in Q[t,x_1,...,x_n] and w=(w_0,...,w_n) 2247 2247 RETURN: ideal ini, the t-initial ideal of i with respect to w" 2248 2248 { 2249 2249 // THE PROCEDURE WILL BE CALLED FROM OTHER PROCEDURES INSIDE THIS LIBRARY; 2250 // IN THIS CASE THE VARIABLE t WILL INDEED BE THE LAST VARIABLE INSTEAD OF 2250 // IN THIS CASE THE VARIABLE t WILL INDEED BE THE LAST VARIABLE INSTEAD OF 2251 2251 // THE FIRST, 2252 2252 // AND WE THEREFORE HAVE TO MOVE IT BACK TO THE FRONT! … … 2272 2272 // ... and compute a standard basis with 2273 2273 // respect to the homogenised ordering defined by w. Since the generators 2274 // of i will be homogeneous it we can instead take the ordering wp 2275 // with the weightvector (0,w) replaced by (M,...,M)+(0,w) for some 2276 // large M, so that all entries are positive 2277 int M=-minInIntvec(w)[1]+1; // find M such that w[j]+M is 2274 // of i will be homogeneous it we can instead take the ordering wp 2275 // with the weightvector (0,w) replaced by (M,...,M)+(0,w) for some 2276 // large M, so that all entries are positive 2277 int M=-minInIntvec(w)[1]+1; // find M such that w[j]+M is 2278 2278 // strictly positive for all j 2279 2279 intvec whomog=M+1; … … 2283 2283 } 2284 2284 execute("ring WEIGHTRING=("+charstr(basering)+"),("+varstr(basering)+"),(wp("+string(whomog)+"));"); 2285 // map i to the new ring and compute a GB of i, then dehomogenise i, 2286 // so that we can be sure, that the 2285 // map i to the new ring and compute a GB of i, then dehomogenise i, 2286 // so that we can be sure, that the 2287 2287 // initial forms of the generators generate the initial ideal 2288 2288 ideal i=subst(groebner(imap(HOMOGRING,i)),@s,1); … … 2538 2538 proc texDrawBasic (list texdraw) 2539 2539 "USAGE: texDrawBasic(texdraw); list texdraw 2540 ASSUME: texdraw is a list of strings representing texdraw commands 2541 (as produced by texDrawTropical) which should be embedded into 2540 ASSUME: texdraw is a list of strings representing texdraw commands 2541 (as produced by texDrawTropical) which should be embedded into 2542 2542 a texdraw environment 2543 2543 RETURN: string, a texdraw environment enclosing the input … … 2559 2559 \\end{texdraw}"; 2560 2560 return(texdrawtp); 2561 } 2561 } 2562 2562 example 2563 2563 { … … 2576 2576 ASSUME: graph is the output of tropicalCurve 2577 2577 RETURN: string, the texdraw code of the tropical plane curve encoded by graph 2578 NOTE: - if the list # is non-empty, the first entry should be a string; 2579 if this string is 'max', then the tropical curve is considered 2580 with respect to the maximum; otherwise the curve is considered 2581 with respect to the minimum and the string can be used to insert 2578 NOTE: - if the list # is non-empty, the first entry should be a string; 2579 if this string is 'max', then the tropical curve is considered 2580 with respect to the maximum; otherwise the curve is considered 2581 with respect to the minimum and the string can be used to insert 2582 2582 further texdraw commands (e.g. to have a lighter image as when called 2583 from inside conicWithTangents); 2584 @* - the procedure computes a scalefactor for the texdraw command which 2585 should help to display the curve in the right way; this may, 2586 however, be a bad idea if several texDrawTropical outputs are 2587 put together to form one image; the scalefactor can be prescribed 2583 from inside conicWithTangents); 2584 @* - the procedure computes a scalefactor for the texdraw command which 2585 should help to display the curve in the right way; this may, 2586 however, be a bad idea if several texDrawTropical outputs are 2587 put together to form one image; the scalefactor can be prescribed 2588 2588 by a second optional entry of type poly 2589 2589 @* - the list # is optional and may as well be empty … … 2591 2591 { 2592 2592 int i,j; 2593 // deal first with the pathological case that 2593 // deal first with the pathological case that 2594 2594 // the input polynomial was a monomial 2595 // and does therefore not define a tropical curve, 2596 // and check if the Newton polytope is 2595 // and does therefore not define a tropical curve, 2596 // and check if the Newton polytope is 2597 2597 // a line segment so that the curve defines a bunch of lines 2598 2598 int bunchoflines; 2599 2599 // if the boundary of the Newton polytope consists of a single point 2600 if (size(graph[size(graph)][1])==1) 2600 if (size(graph[size(graph)][1])==1) 2601 2601 { 2602 2602 return(string()); … … 2611 2611 } 2612 2612 // then the Newton polytope is a line segment 2613 if ((size(graph[size(graph)][1])-size(syz(M)))==1) 2613 if ((size(graph[size(graph)][1])-size(syz(M)))==1) 2614 2614 { 2615 2615 bunchoflines=1; … … 2618 2618 // go on with the case that a tropical curve is defined 2619 2619 if (size(#)==0) 2620 { 2620 { 2621 2621 string texdrawtp=" 2622 2622 … … 2626 2626 { 2627 2627 if ((#[1]!="max") and (#[1]!="")) 2628 { 2628 { 2629 2629 string texdrawtp=#[1]; 2630 2630 } … … 2675 2675 { 2676 2676 // if the curve is a bunch of lines no vertex has to be drawn 2677 if (bunchoflines==0) 2677 if (bunchoflines==0) 2678 2678 { 2679 2679 texdrawtp=texdrawtp+" … … 2681 2681 } 2682 2682 // draw the bounded edges emerging from the ith vertex 2683 for (j=1;j<=ncols(graph[i][3]);j++) 2684 { 2685 // don't draw it twice - and if there is only one vertex 2683 for (j=1;j<=ncols(graph[i][3]);j++) 2684 { 2685 // don't draw it twice - and if there is only one vertex 2686 2686 // and graph[i][3][1,1] is thus 0, nothing is done 2687 if (i<graph[i][3][1,j]) 2688 { 2687 if (i<graph[i][3][1,j]) 2688 { 2689 2689 texdrawtp=texdrawtp+" 2690 2690 \\move ("+decimal(graph[i][1]-centerx)+" "+decimal(graph[i][2]-centery)+") \\lvec ("+decimal(graph[graph[i][3][1,j]][1]-centerx)+" "+decimal(graph[graph[i][3][1,j]][2]-centery)+")"; 2691 2691 // if the multiplicity is more than one, denote it in the picture 2692 if (graph[i][3][2,j]>1) 2692 if (graph[i][3][2,j]>1) 2693 2693 { 2694 2694 texdrawtp=texdrawtp+" … … 2699 2699 // draw the unbounded edges emerging from the ith vertex 2700 2700 // they should not be too long 2701 for (j=1;j<=size(graph[i][4]);j++) 2702 { 2701 for (j=1;j<=size(graph[i][4]);j++) 2702 { 2703 2703 relxy=shorten(list(decimal(3*graph[i][4][j][1][1]/scalefactor),decimal(3*graph[i][4][j][1][2]/scalefactor),"2.5")); 2704 2704 texdrawtp=texdrawtp+" 2705 2705 \\move ("+decimal(graph[i][1]-centerx)+" "+decimal(graph[i][2]-centery)+") \\rlvec ("+relxy[1]+" "+relxy[2]+")"; 2706 2706 // if the multiplicity is more than one, denote it in the picture 2707 if (graph[i][4][j][2]>1) 2707 if (graph[i][4][j][2]>1) 2708 2708 { 2709 2709 texdrawtp=texdrawtp+" … … 2783 2783 poly scalefactor=minOfPolys(list(12/leadcoef(maxx),12/leadcoef(maxy))); 2784 2784 if (scalefactor<1) 2785 { 2785 { 2786 2786 subdivision=subdivision+" 2787 2787 \\relunitscale"+ decimal(scalefactor); … … 2791 2791 { 2792 2792 subdivision=subdivision+" 2793 \\move ("+string(boundary[i][1])+" "+string(boundary[i][2])+") 2793 \\move ("+string(boundary[i][1])+" "+string(boundary[i][2])+") 2794 2794 \\lvec ("+string(boundary[i+1][1])+" "+string(boundary[i+1][2])+")"; 2795 } 2795 } 2796 2796 subdivision=subdivision+" 2797 \\move ("+string(boundary[size(boundary)][1])+" "+string(boundary[size(boundary)][2])+") 2797 \\move ("+string(boundary[size(boundary)][1])+" "+string(boundary[size(boundary)][2])+") 2798 2798 \\lvec ("+string(boundary[1][1])+" "+string(boundary[1][2])+") 2799 2799 … … 2802 2802 { 2803 2803 subdivision=subdivision+" 2804 \\move ("+string(inneredges[i][1][1])+" "+string(inneredges[i][1][2])+") 2804 \\move ("+string(inneredges[i][1][1])+" "+string(inneredges[i][1][2])+") 2805 2805 \\lvec ("+string(inneredges[i][2][1])+" "+string(inneredges[i][2][2])+")"; 2806 2806 } … … 2822 2822 } 2823 2823 } 2824 // deal with the pathological cases 2824 // deal with the pathological cases 2825 2825 if (size(boundary)==1) // then the Newton polytope is a point 2826 2826 { … … 2877 2877 { 2878 2878 subdivision=subdivision+" 2879 \\move ("+string(markings[i][1])+" "+string(markings[i][2])+") 2879 \\move ("+string(markings[i][1])+" "+string(markings[i][2])+") 2880 2880 \\fcir f:0 r:"+decimal(2/(8*scalefactor),size(string(int(scalefactor)))+1); 2881 2881 } 2882 2882 // enclose subdivision in the texdraw environment 2883 string texsubdivision=" 2883 string texsubdivision=" 2884 2884 \\begin{texdraw} 2885 \\drawdim cm \\relunitscale 1 2885 \\drawdim cm \\relunitscale 1 2886 2886 \\linewd 0.05" 2887 2887 +subdivision+" … … 2897 2897 poly f=x+y+x2y+xy2+1/t*xy; 2898 2898 list graph=tropicalCurve(f); 2899 // compute the texdraw code of the Newton subdivision of the tropical curve 2899 // compute the texdraw code of the Newton subdivision of the tropical curve 2900 2900 texDrawNewtonSubdivision(graph); 2901 2901 } … … 2905 2905 proc texDrawTriangulation (list triang,list polygon) 2906 2906 "USAGE: texDrawTriangulation(triang,polygon); triang,polygon list 2907 ASSUME: polygon is a list of integer vectors describing the 2907 ASSUME: polygon is a list of integer vectors describing the 2908 2908 lattice points of a marked polygon; 2909 triang is a list of integer vectors describing a 2909 triang is a list of integer vectors describing a 2910 2910 triangulation of the marked polygon 2911 in the sense that an integer vector of the form (i,j,k) describes 2911 in the sense that an integer vector of the form (i,j,k) describes 2912 2912 the triangle formed by polygon[i], polygon[j] and polygon[k] 2913 RETURN: string, a texdraw code for the triangulation described 2913 RETURN: string, a texdraw code for the triangulation described 2914 2914 by triang without the texdraw environment 2915 2915 EXAMPLE: example texDrawTriangulation; shows an example" … … 2920 2920 "; 2921 2921 int i,j; // indices 2922 list pairs,markings; // stores edges of the triangulation, respecively 2923 // the marked points for each triangle store the edges and marked 2922 list pairs,markings; // stores edges of the triangulation, respecively 2923 // the marked points for each triangle store the edges and marked 2924 2924 // points of the triangle 2925 2925 for (i=1;i<=size(triang);i++) … … 2930 2930 markings[3*i-2]=triang[i][1]; 2931 2931 markings[3*i-1]=triang[i][2]; 2932 markings[3*i]=triang[i][3]; 2932 markings[3*i]=triang[i][3]; 2933 2933 } 2934 2934 // delete redundant pairs which occur more than once … … 2963 2963 { 2964 2964 latex=latex+" 2965 \\move ("+string(polygon[markings[i]][1])+" "+string(polygon[markings[i]][2])+") 2965 \\move ("+string(polygon[markings[i]][1])+" "+string(polygon[markings[i]][2])+") 2966 2966 \\fcir f:0 r:0.08"; 2967 2967 } … … 2970 2970 { 2971 2971 latex=latex+" 2972 \\move ("+string(polygon[pairs[i][1]][1])+" "+string(polygon[pairs[i][1]][2])+") 2972 \\move ("+string(polygon[pairs[i][1]][1])+" "+string(polygon[pairs[i][1]][2])+") 2973 2973 \\lvec ("+string(polygon[pairs[i][2]][1])+" "+string(polygon[pairs[i][2]][2])+")"; 2974 2974 } … … 2977 2977 { 2978 2978 latex=latex+" 2979 \\move ("+string(polygon[i][1])+" "+string(polygon[i][2])+") 2979 \\move ("+string(polygon[i][1])+" "+string(polygon[i][2])+") 2980 2980 \\fcir f:0.7 r:0.04"; 2981 2981 } … … 2986 2986 "EXAMPLE:"; 2987 2987 echo=2; 2988 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 2988 // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) 2989 2989 // with all integer points as markings 2990 2990 list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0),intvec(0,0), 2991 2991 intvec(2,1),intvec(0,1),intvec(1,2),intvec(0,2),intvec(0,3); 2992 // define a triangulation by connecting the only interior point 2992 // define a triangulation by connecting the only interior point 2993 2993 // with the vertices 2994 2994 list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,2,10); … … 2998 2998 2999 2999 /////////////////////////////////////////////////////////////////////////////// 3000 /// Auxilary Procedures 3000 /// Auxilary Procedures 3001 3001 /////////////////////////////////////////////////////////////////////////////// 3002 3002 … … 3004 3004 "USAGE: radicalMemberShip (f,i); f poly, i ideal 3005 3005 RETURN: int, 1 if f is in the radical of i, 0 else 3006 EXAMPLE: example radicalMemberShip; shows an example" 3006 EXAMPLE: example radicalMemberShip; shows an example" 3007 3007 { 3008 3008 def BASERING=basering; … … 3044 3044 { 3045 3045 // compute first the t-order of the leading coefficient of f (leitkoef[1]) and 3046 // the rational constant corresponding to this order in leadkoef(f) 3046 // the rational constant corresponding to this order in leadkoef(f) 3047 3047 // (leitkoef[2]) 3048 3048 list leitkoef=simplifyToOrder(f); … … 3054 3054 // do the same for the remaining part of f and compare the results 3055 3055 // keep only the smallest ones 3056 int vglgewicht; 3057 f=f-lead(f); 3056 int vglgewicht; 3057 f=f-lead(f); 3058 3058 while (f!=0) 3059 3059 { 3060 leitkoef=simplifyToOrder(f); 3060 leitkoef=simplifyToOrder(f); 3061 3061 vglgewicht=leitkoef[1]+scalarproduct(w,leadexp(f)); 3062 3062 if (vglgewicht<gewicht) … … 3073 3073 initialf=initialf+koef*leadmonom(f); 3074 3074 } 3075 } 3075 } 3076 3076 f=f-lead(f); 3077 3077 } … … 3098 3098 { 3099 3099 // compute first the t-order of the leading coefficient of f (leitkoef[1]) and 3100 // the rational constant corresponding to this order in leadkoef(f) 3100 // the rational constant corresponding to this order in leadkoef(f) 3101 3101 // (leitkoef[2]) 3102 list leitkoef=simplifyToOrder(f); 3102 list leitkoef=simplifyToOrder(f); 3103 3103 execute("poly koef="+leitkoef[2]+";"); 3104 3104 // take in lead(f) only the term of lowest t-order and set t=1 … … 3109 3109 // keep only the largest ones 3110 3110 int vglgewicht; 3111 f=f-lead(f); 3111 f=f-lead(f); 3112 3112 while (f!=0) 3113 3113 { … … 3127 3127 initialf=initialf+koef*leadmonom(f); 3128 3128 } 3129 } 3129 } 3130 3130 f=f-lead(f); 3131 3131 } … … 3146 3146 proc solveTInitialFormPar (ideal i) 3147 3147 "USAGE: solveTInitialFormPar(i); i ideal 3148 ASSUME: i is a zero-dimensional ideal in Q(t)[x_1,...,x_n] generated 3149 by the (1,w)-homogeneous elements for some integer vector w 3148 ASSUME: i is a zero-dimensional ideal in Q(t)[x_1,...,x_n] generated 3149 by the (1,w)-homogeneous elements for some integer vector w 3150 3150 - i.e. by the (1,w)-initialforms of polynomials 3151 3151 RETURN: none 3152 NOTE: the procedure just displays complex approximations 3152 NOTE: the procedure just displays complex approximations 3153 3153 of the solution set of i 3154 3154 EXAMPLE: example solveTInitialFormPar; shows an example" … … 3175 3175 ///////////////////////////////////////////////////////////////////////// 3176 3176 3177 proc detropicalise (poly p) 3177 proc detropicalise (poly p) 3178 3178 "USAGE: detropicalise(f); f poly 3179 3179 ASSUME: f is a linear polynomial with an arbitrary constant term and 3180 3180 positive integer coefficients as further coefficients; 3181 3181 RETURN: poly, the detropicalisation of (the non-constant part of) f 3182 NOTE: the output will be a monomial and the constant coefficient 3182 NOTE: the output will be a monomial and the constant coefficient 3183 3183 has been ignored 3184 3184 EXAMPLE: example detropicalise; shows an example" … … 3188 3188 { 3189 3189 if (leadmonom(p)!=1) 3190 { 3190 { 3191 3191 dtp=dtp*leadmonom(p)^int(leadcoef(p)); 3192 3192 } … … 3241 3241 proc parameterSubstitute (poly f,int N) 3242 3242 "USAGE: parameterSubstitute(f,N); f poly, N int 3243 ASSUME: f is a polynomial in Q(t)[x_1,...,x_n] describing 3243 ASSUME: f is a polynomial in Q(t)[x_1,...,x_n] describing 3244 3244 a plane curve over Q(t) 3245 3245 RETURN: poly f with t replaced by t^N … … 3295 3295 poly f=t2x+1/t*y-1; 3296 3296 tropicalSubst(f,2,x,x+t,y,tx+y+t2); 3297 // The procedure can be used to study the effect of a transformation of 3297 // The procedure can be used to study the effect of a transformation of 3298 3298 // the form x -> x+t^b, with b a rational number, on the tropicalisation and 3299 3299 // the j-invariant of a cubic over the Puiseux series. 3300 3300 f=t7*y3+t3*y2+t*(x3+xy2+y+1)+xy; 3301 // - the j-invariant, and hence its valuation, 3301 // - the j-invariant, and hence its valuation, 3302 3302 // does not change under the transformation 3303 3303 jInvariant(f,"ord"); 3304 // - b=3/2, then the cycle length of the tropical cubic equals -val(j-inv) 3305 list g32=tropicalSubst(f,2,x,x+t3,y,y); 3304 // - b=3/2, then the cycle length of the tropical cubic equals -val(j-inv) 3305 list g32=tropicalSubst(f,2,x,x+t3,y,y); 3306 3306 tropicalJInvariant(g32); 3307 3307 // - b=1, then it is still true, but only just ... … … 3316 3316 3317 3317 proc randomPoly (int d,int ug, int og, list #) 3318 "USAGE: randomPoly(d,ug,og[,#]); d, ug, og int, # list 3318 "USAGE: randomPoly(d,ug,og[,#]); d, ug, og int, # list 3319 3319 ASSUME: the basering has a parameter t 3320 RETURN: poly, a polynomial of degree d where the coefficients are 3320 RETURN: poly, a polynomial of degree d where the coefficients are 3321 3321 of the form t^j with j a random integer between ug and og 3322 NOTE: if an optional argument # is given, then the coefficients are 3323 instead either of the form t^j as above or they are zero, 3322 NOTE: if an optional argument # is given, then the coefficients are 3323 instead either of the form t^j as above or they are zero, 3324 3324 and this is chosen randomly 3325 3325 EXAMPLE: example randomPoly; shows an example" … … 3337 3337 { 3338 3338 if (size(#)!=0) 3339 { 3339 { 3340 3340 k=random(0,1); 3341 3341 } 3342 3342 if (k==0) 3343 { 3343 { 3344 3344 j=random(ug,og); 3345 3345 randomPolynomial=randomPolynomial+t^j*m[i]; … … 3371 3371 RETURN: none" 3372 3372 { 3373 system("sh","cd /tmp; /bin/rm -f tropicalcurve*; /bin/rm -f tropicalnewtonsubdivision*"); 3373 system("sh","cd /tmp; /bin/rm -f tropicalcurve*; /bin/rm -f tropicalnewtonsubdivision*"); 3374 3374 } 3375 3375 … … 3428 3428 static proc cutdown (ideal jideal,intvec wvec,int dimension,list #) 3429 3429 "USAGE: cutdown(i,w,d); i ideal, w intvec, d int, # list 3430 ASSUME: i an ideal in Q[t,x_1,...,x_n], (w_1,...,w_n) is in the tropical 3431 variety of jideal and d=dim(i)>0, in Q(t)[x]; the optional 3432 parameter # can contain the string 'isPrime' to indicate that 3433 the input ideal is prime and no minimal associated primes have 3430 ASSUME: i an ideal in Q[t,x_1,...,x_n], (w_1,...,w_n) is in the tropical 3431 variety of jideal and d=dim(i)>0, in Q(t)[x]; the optional 3432 parameter # can contain the string 'isPrime' to indicate that 3433 the input ideal is prime and no minimal associated primes have 3434 3434 to be computed 3435 RETURN: list, the first entry is a ring, namely the basering where some 3436 variables have been eliminated, and the ring contains 3435 RETURN: list, the first entry is a ring, namely the basering where some 3436 variables have been eliminated, and the ring contains 3437 3437 the ideal i (with the same variables eliminated), 3438 the t-initial ideal ini of i (w.r.t. the weight vector 3439 where the entries corresponding to the deleted variables 3440 have been eliminated) and a list repl where for each 3438 the t-initial ideal ini of i (w.r.t. the weight vector 3439 where the entries corresponding to the deleted variables 3440 have been eliminated) and a list repl where for each 3441 3441 eliminated variable there is one entry, namely a polynomial 3442 in the remaining variables and t that explains how 3443 resubstitution of a solution for the new i gives a solution 3442 in the remaining variables and t that explains how 3443 resubstitution of a solution for the new i gives a solution 3444 3444 for the old i; the second entry is the weight vector 3445 wvec with the components corresponding to the eliminated 3445 wvec with the components corresponding to the eliminated 3446 3446 variables removed 3447 NOTE: needs the libraries random.lib and primdec.lib; 3447 NOTE: needs the libraries random.lib and primdec.lib; 3448 3448 is called from tropicalLifting" 3449 { 3450 // IDEA: i is an ideal of dimension d; we want to cut it with d random linear 3449 { 3450 // IDEA: i is an ideal of dimension d; we want to cut it with d random linear 3451 3451 // forms in such a way that the resulting 3452 3452 // ideal is 0-dim and still contains w in the tropical variety 3453 // NOTE: t is the last variable in the basering 3453 // NOTE: t is the last variable in the basering 3454 3454 ideal pideal; //this is the ideal we want to return 3455 3455 ideal cutideal; … … 3469 3469 for (j1=1;j1<=nvars(basering)-1;j1++) 3470 3470 { 3471 variablen=variablen+var(j1); // read the set of variables 3471 variablen=variablen+var(j1); // read the set of variables 3472 3472 // (needed to make the quotring later) 3473 product=product*var(j1); // make product of all variables 3473 product=product*var(j1); // make product of all variables 3474 3474 // (needed for the initial-monomial-check later 3475 } 3475 } 3476 3476 execute("ring QUOTRING=("+charstr(basering)+",t),("+string(variablen)+"),dp;"); 3477 3477 setring BASERING; … … 3480 3480 { 3481 3481 setring QUOTRING; 3482 ideal jideal=imap(BASERING,jideal); 3483 list primp=minAssGTZ(jideal); //compute the primary decomposition 3482 ideal jideal=imap(BASERING,jideal); 3483 list primp=minAssGTZ(jideal); //compute the primary decomposition 3484 3484 for (j1=1;j1<=size(primp);j1++) 3485 { 3485 { 3486 3486 for(j2=1;j2<=size(primp[j1]);j2++) 3487 3487 { 3488 3488 // clear all denominators 3489 3489 primp[j1][j2]=primp[j1][j2]/content(primp[j1][j2]); 3490 } 3490 } 3491 3491 } 3492 3492 setring BASERING; 3493 3493 list primp=imap(QUOTRING,primp); 3494 3494 // if i is not primary itself 3495 // go through the list of min. ass. primes and find the first 3495 // go through the list of min. ass. primes and find the first 3496 3496 // one which has w in its tropical variety 3497 if (size(primp)>1) 3497 if (size(primp)>1) 3498 3498 { 3499 3499 j1=1; … … 3502 3502 //compute the t-initial of the associated prime 3503 3503 // - the last entry 1 only means that t is the last variable in the ring 3504 primini=tInitialIdeal(primp[j1],wvec,1); 3505 // check if it contains a monomial (resp if the product of var 3504 primini=tInitialIdeal(primp[j1],wvec,1); 3505 // check if it contains a monomial (resp if the product of var 3506 3506 // is in the radical) 3507 if (radicalMemberShip(product,primini)==0) 3508 { 3507 if (radicalMemberShip(product,primini)==0) 3508 { 3509 3509 // if w is in the tropical variety of the prime, we take that 3510 3510 jideal=primp[j1]; … … 3513 3513 setring BASERING; 3514 3514 winprim=1; // and stop the checking 3515 } 3515 } 3516 3516 j1=j1+1; //else we look at the next associated prime 3517 3517 } … … 3520 3520 { 3521 3521 jideal=primp[1]; //if i is primary itself we take its prime instead 3522 } 3522 } 3523 3523 } 3524 3524 // now we start as a first try to intersect with a hyperplane parallel to 3525 3525 // coordinate axes, because this would make our further computations 3526 // a lot easier. 3527 // We choose a subset of our n variables of size d=dim(ideal). 3526 // a lot easier. 3527 // We choose a subset of our n variables of size d=dim(ideal). 3528 3528 // For each of these 3529 // variables, we want to fix a value: x_i= a_i*t^-w_i. 3529 // variables, we want to fix a value: x_i= a_i*t^-w_i. 3530 3530 // This will only work if the 3531 // projection of the d-dim variety to the other n-d variables 3531 // projection of the d-dim variety to the other n-d variables 3532 3532 // is the whole n-d plane. 3533 // Then a general choice for a_i will intersect the variety 3533 // Then a general choice for a_i will intersect the variety 3534 3534 // in finitely many points. 3535 // If the projection is not the whole n-d plane, 3535 // If the projection is not the whole n-d plane, 3536 3536 // then a general choice will not work. 3537 // We could determine if we picked a good 3537 // We could determine if we picked a good 3538 3538 // d-subset of variables using elimination 3539 // (NOTE, there EXIST d variables such that 3539 // (NOTE, there EXIST d variables such that 3540 3540 // a random choice of a_i's would work!). 3541 // But since this involves many computations, 3541 // But since this involves many computations, 3542 3542 // we prefer to choose randomly and just 3543 // try in the end if our intersected ideal 3544 // satisfies our requirements. If this does not 3543 // try in the end if our intersected ideal 3544 // satisfies our requirements. If this does not 3545 3545 // work, we give up this try and use our second intersection idea, which 3546 3546 // will work for a Zariksi-open subset (i.e. almost always). 3547 3547 // 3548 // As random subset of d variables we choose 3548 // As random subset of d variables we choose 3549 3549 // those for which the absolute value of the 3550 // wvec-coordinate is smallest, because this will 3550 // wvec-coordinate is smallest, because this will 3551 3551 // give us the smallest powers of t and hence 3552 // less effort in following computations. 3552 // less effort in following computations. 3553 3553 // Note that the smallest absolute value have those 3554 // which are biggest, because wvec is negative. 3554 // which are biggest, because wvec is negative. 3555 3555 //print("first try"); 3556 3556 intvec wminust=intvecdelete(wvec,1); … … 3559 3559 A[1,1..size(wminust)]=-wminust; 3560 3560 A[2,1..size(wminust)]=1..size(wminust); 3561 // sort this matrix in order to get 3561 // sort this matrix in order to get 3562 3562 // the d biggest entries and their position in wvec 3563 A=sortintmat(A); 3564 // we construct a vector which has 1 at entry j if j belongs to the list 3563 A=sortintmat(A); 3564 // we construct a vector which has 1 at entry j if j belongs to the list 3565 3565 // of the d biggest entries of wvec and a 0 else 3566 3566 for (j1=1;j1<=nvars(basering)-1;j1++) //go through the variables … … 3571 3571 { 3572 3572 setvec[j1]=1;//put a 1 3573 } 3574 } 3575 } 3576 // using this 0/1-vector we produce 3577 // a random constant (i.e. coeff in Q times something in t) 3578 // for each of the biggest variables, 3573 } 3574 } 3575 } 3576 // using this 0/1-vector we produce 3577 // a random constant (i.e. coeff in Q times something in t) 3578 // for each of the biggest variables, 3579 3579 // we add the forms x_i-random constant to the ideal 3580 // and we save the constant at the i-th place of 3580 // and we save the constant at the i-th place of 3581 3581 // a list we want to return for later computations 3582 3582 j3=0; … … 3589 3589 { 3590 3590 if(setvec[j1]==1)//if x_i belongs to the biggest variables 3591 { 3591 { 3592 3592 if ((j3==1) and ((char(basering)==0) or (char(basering)>3))) 3593 { 3593 { 3594 3594 randomp1=random(1,3); 3595 randomp=t^(A[1,j2])*randomp1;// make a random constant 3595 randomp=t^(A[1,j2])*randomp1;// make a random constant 3596 3596 // --- first we try small numbers 3597 } 3597 } 3598 3598 if ((j3==2) and ((char(basering)==0) or (char(basering)>100))) 3599 3599 { 3600 3600 randomp1=random(1,100); 3601 randomp=t^(A[1,j2])*randomp1;// make a random constant 3601 randomp=t^(A[1,j2])*randomp1;// make a random constant 3602 3602 // --- next we try bigger numbers 3603 } 3603 } 3604 3604 else 3605 3605 { … … 3613 3613 else 3614 3614 { 3615 ergl[j1]=0; //if the variable is not among the d biggest ones, 3615 ergl[j1]=0; //if the variable is not among the d biggest ones, 3616 3616 //save 0 in the list 3617 3617 erglini[j1]=0; 3618 } 3618 } 3619 3619 } 3620 3620 // print(ergl);print(pideal); 3621 // now we check if we made a good choice of pideal, i.e. if dim=0 and 3621 // now we check if we made a good choice of pideal, i.e. if dim=0 and 3622 3622 // wvec is still in the tropical variety 3623 3623 // change to quotring where we compute dimension … … 3626 3626 { 3627 3627 if(setvec[j1]==1) 3628 { 3629 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3630 } 3628 { 3629 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3630 } 3631 3631 } 3632 3632 setring QUOTRING; … … 3640 3640 { 3641 3641 // compute the t-initial of the associated prime 3642 // - the last 1 just means that the variable t is 3642 // - the last 1 just means that the variable t is 3643 3643 // the last variable in the ring 3644 3644 pini=tInitialIdeal(cutideal,wvec ,1); 3645 3645 //print("initial"); 3646 3646 //print(pini); 3647 // and if the initial w.r.t. t contains no monomial 3647 // and if the initial w.r.t. t contains no monomial 3648 3648 // as we want (checked with 3649 3649 // radical-membership of the product of all variables) 3650 if (radicalMemberShip(product,pini)==0) 3651 { 3652 // we made the right choice and now 3653 // we substitute the variables in the ideal 3650 if (radicalMemberShip(product,pini)==0) 3651 { 3652 // we made the right choice and now 3653 // we substitute the variables in the ideal 3654 3654 // to get an ideal in less variables 3655 // also we make a projected vector 3655 // also we make a projected vector 3656 3656 // from wvec only the components of the remaining variables 3657 3657 wvecp=wvec; 3658 variablen=0; 3658 variablen=0; 3659 3659 j2=0; 3660 3660 for(j1=1;j1<=nvars(basering)-1;j1++) … … 3669 3669 else 3670 3670 { 3671 variablen=variablen+var(j1); // read the set of remaining variables 3671 variablen=variablen+var(j1); // read the set of remaining variables 3672 3672 // (needed to make quotring later) 3673 } 3674 } 3673 } 3674 } 3675 3675 // return pideal, the initial and the list ergl which tells us 3676 3676 // which variables we replaced by which form … … 3682 3682 export(ini); 3683 3683 export(repl); 3684 return(list(BASERINGLESS1,wvecp)); 3684 return(list(BASERINGLESS1,wvecp)); 3685 3685 } 3686 3686 } 3687 3687 } 3688 3688 // this is our second try to cut down, which we only use if the first try 3689 // didn't work out. We intersect with d general hyperplanes 3689 // didn't work out. We intersect with d general hyperplanes 3690 3690 // (i.e. we don't choose 3691 3691 // them to be parallel to coordinate hyperplanes anymore. This works out with 3692 3692 // probability 1. 3693 3693 // 3694 // We choose general hyperplanes, i.e. linear forms which involve all x_i. 3695 // Each x_i has to be multiplied bz t^(w_i) in order 3696 // to get the same weight (namely 0) 3694 // We choose general hyperplanes, i.e. linear forms which involve all x_i. 3695 // Each x_i has to be multiplied bz t^(w_i) in order 3696 // to get the same weight (namely 0) 3697 3697 // for each term. As we cannot have negative exponents, we multiply 3698 // the whole form by t^minimumw. Notice that then in the first form, 3698 // the whole form by t^minimumw. Notice that then in the first form, 3699 3699 // there is one term without t- the term of the variable 3700 3700 // x_i such that w_i is minimal. That is, we can solve for this variable. 3701 // In the second form, we can replace that variable, 3702 // and divide by t as much as possible. 3703 // Then there is again one term wihtout t - 3704 // the term of the variable with second least w. 3701 // In the second form, we can replace that variable, 3702 // and divide by t as much as possible. 3703 // Then there is again one term wihtout t - 3704 // the term of the variable with second least w. 3705 3705 // So we can solve for this one again and also replace it in the first form. 3706 // Since all our coefficients are chosen randomly, 3707 // we can also from the beginning on 3708 // choose the set of variables which belong to the d smallest entries of wvec 3709 // (t not counting) and pick random forms g_i(t,x') 3710 // (where x' is the set of remaining variables) 3711 // and set x_i=g_i(t,x'). 3706 // Since all our coefficients are chosen randomly, 3707 // we can also from the beginning on 3708 // choose the set of variables which belong to the d smallest entries of wvec 3709 // (t not counting) and pick random forms g_i(t,x') 3710 // (where x' is the set of remaining variables) 3711 // and set x_i=g_i(t,x'). 3712 3712 // 3713 3713 // make a matrix with first row wvec (without t) and second row 1..n 3714 3714 //print("second try"); 3715 3715 setring BASERING; 3716 A[1,1..size(wminust)]=wminust; 3716 A[1,1..size(wminust)]=wminust; 3717 3717 A[2,1..size(wminust)]=1..size(wminust); 3718 // sort this matrix in otder to get the d smallest entries 3718 // sort this matrix in otder to get the d smallest entries 3719 3719 // (without counting the t-entry) 3720 3720 A=sortintmat(A); … … 3722 3722 setvec=0; 3723 3723 setvec[nvars(basering)-1]=0; 3724 // we construct a vector which has 1 at entry j if j belongs to the list of 3724 // we construct a vector which has 1 at entry j if j belongs to the list of 3725 3725 // the d smallest entries of wvec and a 0 else 3726 3726 for (j1=1;j1<=nvars(basering)-1;j1++) //go through the variables … … 3742 3742 { 3743 3743 j2=j2+1; 3744 wvecp=intvecdelete(wvecp,j1+2-j2);// delete the components 3744 wvecp=intvecdelete(wvecp,j1+2-j2);// delete the components 3745 3745 // we substitute from wvec 3746 3746 } 3747 3747 else 3748 3748 { 3749 variablen=variablen+var(j1); // read the set of remaining variables 3749 variablen=variablen+var(j1); // read the set of remaining variables 3750 3750 // (needed to make the quotring later) 3751 3751 } 3752 } 3752 } 3753 3753 setring BASERING; 3754 3754 execute("ring BASERINGLESS2=("+charstr(BASERING)+"),("+string(variablen)+",t),(dp("+string(ncols(variablen))+"),lp(1));"); 3755 // using the 0/1-vector which tells us which variables belong 3755 // using the 0/1-vector which tells us which variables belong 3756 3756 // to the set of smallest entries of wvec 3757 // we construct a set of d random linear 3758 // polynomials of the form x_i=g_i(t,x'), 3757 // we construct a set of d random linear 3758 // polynomials of the form x_i=g_i(t,x'), 3759 3759 // where the set of all x_i is the set of 3760 // all variables which are in the list of smallest 3760 // all variables which are in the list of smallest 3761 3761 // entries in wvec, and x' are the other variables. 3762 // We add these d random linear polynomials to 3763 // the ideal pideal, i.e. we intersect 3762 // We add these d random linear polynomials to 3763 // the ideal pideal, i.e. we intersect 3764 3764 // with these and hope to get something 3765 // 0-dim which still contains wvec in its 3766 // tropical variety. Also, we produce a list ergl 3765 // 0-dim which still contains wvec in its 3766 // tropical variety. Also, we produce a list ergl 3767 3767 // with g_i at the i-th position. 3768 3768 // This is a list we want to return. … … 3770 3770 setring BASERING; 3771 3771 pideal=jideal; 3772 for(j1=1;j1<=dimension;j1++)//go through the list of variables 3772 for(j1=1;j1<=dimension;j1++)//go through the list of variables 3773 3773 { // corres to the d smallest in wvec 3774 3774 if ((char(basering)==0) or (char(basering)>3)) 3775 { 3775 { 3776 3776 randomp1=random(1,3); 3777 3777 randomp=randomp1*t^(-A[1,j1]); … … 3786 3786 if(setvec[j2]==0)//if x_j belongs to the set x' 3787 3787 { 3788 // add a random term with the suitable power 3788 // add a random term with the suitable power 3789 3789 // of t to the random linear form 3790 3790 if ((char(basering)==0) or (char(basering)>3)) … … 3811 3811 } 3812 3812 //print(ergl); 3813 // Again, we have to test if we made a good choice 3814 // to intersect,i.e. we have to check whether 3813 // Again, we have to test if we made a good choice 3814 // to intersect,i.e. we have to check whether 3815 3815 // pideal is 0-dim and contains wvec in the tropical variety. 3816 3816 cutideal=pideal; … … 3819 3819 if(setvec[j1]==1) 3820 3820 { 3821 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3822 } 3821 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3822 } 3823 3823 } 3824 3824 setring QUOTRING; … … 3832 3832 { 3833 3833 // compute the t-initial of the associated prime 3834 // - the last 1 just means that the variable t 3834 // - the last 1 just means that the variable t 3835 3835 // is the last variable in the ring 3836 3836 pini=tInitialIdeal(cutideal,wvec ,1); … … 3839 3839 // and if the initial w.r.t. t contains no monomial as we want (checked with 3840 3840 // radical-membership of the product of all variables) 3841 if (radicalMemberShip(product,pini)==0) 3841 if (radicalMemberShip(product,pini)==0) 3842 3842 { 3843 3843 // we want to replace the variables x_i by the forms -g_i in 3844 // our ideal in order to return an ideal with less variables 3844 // our ideal in order to return an ideal with less variables 3845 3845 // first we substitute the chosen variables 3846 3846 for(j1=1;j1<=nvars(basering)-1;j1++) … … 3859 3859 export(ini); 3860 3860 export(repl); 3861 return(list(BASERINGLESS2,wvecp)); 3861 return(list(BASERINGLESS2,wvecp)); 3862 3862 } 3863 3863 } 3864 3864 // now we try bigger numbers 3865 while (1) //a never-ending loop which will stop with prob. 1 3865 while (1) //a never-ending loop which will stop with prob. 1 3866 3866 { // as we find a suitable ideal with that prob 3867 3867 setring BASERING; 3868 3868 pideal=jideal; 3869 for(j1=1;j1<=dimension;j1++)//go through the list of variables 3869 for(j1=1;j1<=dimension;j1++)//go through the list of variables 3870 3870 { // corres to the d smallest in wvec 3871 3871 randomp1=random(1,100); 3872 3872 randomp=randomp1*t^(-A[1,j1]); 3873 3873 for(j2=1;j2<=nvars(basering)-1;j2++)//go through all variables 3874 { 3874 { 3875 3875 if(setvec[j2]==0)//if x_j belongs to the set x' 3876 3876 { 3877 // add a random term with the suitable power 3877 // add a random term with the suitable power 3878 3878 // of t to the random linear form 3879 3879 if ((char(basering)==0) or (char(basering)>100)) 3880 { 3880 { 3881 3881 randomp2=random(1,100); 3882 3882 randomp1=randomp1+randomp2*var(j2); … … 3899 3899 } 3900 3900 //print(ergl); 3901 // Again, we have to test if we made a good choice to 3902 // intersect,i.e. we have to check whether 3901 // Again, we have to test if we made a good choice to 3902 // intersect,i.e. we have to check whether 3903 3903 // pideal is 0-dim and contains wvec in the tropical variety. 3904 3904 cutideal=pideal; … … 3907 3907 if(setvec[j1]==1) 3908 3908 { 3909 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3910 } 3909 cutideal=cutideal,var(j1)-ergl[j1];//add all forms to the ideal 3910 } 3911 3911 } 3912 3912 setring QUOTRING; … … 3916 3916 //print(dimp); 3917 3917 kill cutideal; 3918 setring BASERING; 3918 setring BASERING; 3919 3919 if (dimp==0) // if it is 0 as we want 3920 3920 { 3921 3921 // compute the t-initial of the associated prime 3922 // - the last 1 just means that the variable t 3922 // - the last 1 just means that the variable t 3923 3923 // is the last variable in the ring 3924 3924 pini=tInitialIdeal(cutideal,wvec ,1); 3925 3925 //print("initial"); 3926 3926 //print(pini); 3927 // and if the initial w.r.t. t contains no monomial 3927 // and if the initial w.r.t. t contains no monomial 3928 3928 // as we want (checked with 3929 3929 // radical-membership of the product of all variables) 3930 if (radicalMemberShip(product,pini)==0) 3930 if (radicalMemberShip(product,pini)==0) 3931 3931 { 3932 3932 // we want to replace the variables x_i by the forms -g_i in … … 3939 3939 pideal=subst(pideal,var(j1),ergl[j1]);//substitute it 3940 3940 pini=subst(pini,var(j1),erglini[j1]); 3941 } 3942 } 3941 } 3942 } 3943 3943 // return pideal and the list ergl which tells us 3944 3944 // which variables we replaced by which form … … 3950 3950 export(ini); 3951 3951 export(repl); 3952 return(list(BASERINGLESS2,wvecp)); 3952 return(list(BASERINGLESS2,wvecp)); 3953 3953 } 3954 3954 } … … 3961 3961 static proc tropicalparametriseNoabs (ideal i,intvec ww,int ordnung,int gfanold,int nogfan,list #) 3962 3962 "USAGE: tropicalparametriseNoabs(i,tw,ord,gf,ng[,#]); i ideal, tw intvec, ord int, gf,ng int, # opt. list 3963 ASSUME: - i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k], 3964 tw=(w_0,w_1,...,w_n,0,...,0) and (w_0,...,w_n,0,...,0) is in 3965 the tropical variety of i, and ord is the order up to which a point 3966 in V(i) over C((t)) lying over w shall be computed; 3963 ASSUME: - i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k], 3964 tw=(w_0,w_1,...,w_n,0,...,0) and (w_0,...,w_n,0,...,0) is in 3965 the tropical variety of i, and ord is the order up to which a point 3966 in V(i) over C((t)) lying over w shall be computed; 3967 3967 - moreover, k should be zero if the procedure is not called recursively; 3968 - the point in the tropical variety is supposed to lie in the NEGATIVE 3968 - the point in the tropical variety is supposed to lie in the NEGATIVE 3969 3969 orthant; 3970 - the ideal is zero-dimensional when considered 3970 - the ideal is zero-dimensional when considered 3971 3971 in (Q(t)[X_1,...,X_k]/m)[x_1,...,x_n], 3972 where m=#[2] is a maximal ideal in Q(t)[X_1,...,X_k]; 3972 where m=#[2] is a maximal ideal in Q(t)[X_1,...,X_k]; 3973 3973 - gf is 0 if version 2.2 or larger is used and it is 1 else 3974 - ng is 1 if gfan should not be executed 3974 - ng is 1 if gfan should not be executed 3975 3975 RETURN: list, l[1] = ring Q(0,X_1,...,X_r)[[t]] 3976 3976 l[2] = int 3977 3977 l[3] = string 3978 3978 NOTE: - the procedure is also called recursively by itself, and 3979 if it is called in the first recursion, the list # is empty, 3980 otherwise #[1] is an integer, one more than the number 3979 if it is called in the first recursion, the list # is empty, 3980 otherwise #[1] is an integer, one more than the number 3981 3981 of true variables x_1,...,x_n, 3982 3982 and #[2] will contain the maximal ideal m in the variables X_1,...X_k … … 3984 3984 work correctly in K[t,x_1,...,x_n] where K=Q[X_1,...,X_k]/m is a field 3985 3985 extension of Q; 3986 - the ring l[1] contains an ideal PARA, which contains the 3987 parametrisation of a point in V(i) lying over w up to the 3986 - the ring l[1] contains an ideal PARA, which contains the 3987 parametrisation of a point in V(i) lying over w up to the 3988 3988 first ord terms; 3989 - the string m=l[3] contains the code of the maximal ideal m, 3990 by which we have to divide Q[X_1,...,X_r] in order to have 3989 - the string m=l[3] contains the code of the maximal ideal m, 3990 by which we have to divide Q[X_1,...,X_r] in order to have 3991 3991 the appropriate field extension over which the parametrisation lives; 3992 - and if the integer l[2] is N then t has to be replaced by t^1/N in 3993 the parametrisation, or alternatively replace t by t^N in the 3992 - and if the integer l[2] is N then t has to be replaced by t^1/N in 3993 the parametrisation, or alternatively replace t by t^N in the 3994 3994 defining ideal 3995 - the procedure REQUIRES that the program GFAN is installed on 3995 - the procedure REQUIRES that the program GFAN is installed on 3996 3996 your computer" 3997 3997 { … … 4001 4001 if (size(#)==2) // this means the precedure has been called recursively 4002 4002 { 4003 // how many variables are true variables, and how many come 4003 // how many variables are true variables, and how many come 4004 4004 // from the field extension 4005 4005 // only true variables have to be transformed … … 4007 4007 ideal gesamt_m=std(#[2]); // stores all maxideals used for field extensions 4008 4008 // find the zeros of the w-initial ideal and transform the ideal i; 4009 // findzeros and basictransformideal need to know how 4009 // findzeros and basictransformideal need to know how 4010 4010 // many of the variables are true variables 4011 4011 list m_ring=findzeros(i,ww,anzahlvariablen); … … 4014 4014 else // the procedure has been called by tropicalLifting 4015 4015 { 4016 // how many variables are true variables, and how many come from 4016 // how many variables are true variables, and how many come from 4017 4017 // the field extension only true variables have to be transformed 4018 4018 int anzahlvariablen=nvars(basering); … … 4021 4021 ideal ini=#[1]; 4022 4022 // find the zeros of the w-initial ideal and transform the ideal i; 4023 // we should hand the t-initial ideal ine to findzeros, 4023 // we should hand the t-initial ideal ine to findzeros, 4024 4024 // since we know it already 4025 4025 list m_ring=findzeros(i,ww,ini); … … 4043 4043 list a=btr[2]; 4044 4044 ideal m=btr[3]; 4045 gesamt_m=gesamt_m+m; // add the newly found maximal 4045 gesamt_m=gesamt_m+m; // add the newly found maximal 4046 4046 // ideal to the previous ones 4047 4047 } 4048 4048 // check if there is a solution which has the n-th component zero, 4049 // if so, then eliminate the n-th variable from sat(i+x_n,t), 4049 // if so, then eliminate the n-th variable from sat(i+x_n,t), 4050 4050 // otherwise leave i as it is; 4051 // then check if the (remaining) ideal has as solution 4051 // then check if the (remaining) ideal has as solution 4052 4052 // where the n-1st component is zero, 4053 4053 // and procede as before; do the same for the remaining variables; 4054 // this way we make sure that the remaining ideal has 4054 // this way we make sure that the remaining ideal has 4055 4055 // a solution which has no component zero; 4056 4056 intvec deletedvariables; // the jth entry is set 1, if we eliminate x_j 4057 4057 int numberdeletedvariables; // the number of eliminated variables 4058 4058 ideal variablen; // will contain the variables which are not eliminated 4059 intvec tw=ww; // in case some variables are deleted, 4059 intvec tw=ww; // in case some variables are deleted, 4060 4060 // we have to store the old weight vector 4061 4061 deletedvariables[anzahlvariablen]=0; 4062 ideal I,LI; 4062 ideal I,LI; 4063 4063 i=i+m; // if a field extension was necessary, then i has to be extended by m 4064 4064 for (jj=anzahlvariablen-1;jj>=1;jj--) // the variable t is the last one !!! … … 4067 4067 LI=subst(I,var(nvars(basering)),0); 4068 4068 //size(deletedvariables)=anzahlvariablen(before elim.) 4069 for (kk=1;kk<=size(deletedvariables)-1;kk++) 4069 for (kk=1;kk<=size(deletedvariables)-1;kk++) 4070 4070 { 4071 4071 LI=subst(LI,var(kk),0); 4072 4072 } 4073 if (size(LI)==0) // if no power of t is in lead(I) 4073 if (size(LI)==0) // if no power of t is in lead(I) 4074 4074 { // (where the X(i) are considered as field elements) 4075 // get rid of var(jj) 4075 // get rid of var(jj) 4076 4076 i=eliminate(I,var(jj)); 4077 4077 deletedvariables[jj]=1; 4078 anzahlvariablen--; // if a variable is eliminated, 4078 anzahlvariablen--; // if a variable is eliminated, 4079 4079 // then the number of true variables drops 4080 4080 numberdeletedvariables++; … … 4086 4086 } 4087 4087 variablen=invertorder(variablen); 4088 // store also the additional variables and t, 4088 // store also the additional variables and t, 4089 4089 // since they for sure have not been eliminated 4090 4090 for (jj=anzahlvariablen+numberdeletedvariables-1;jj<=nvars(basering);jj++) … … 4092 4092 variablen=variablen+var(jj); 4093 4093 } 4094 // if some variables have been eliminated, 4094 // if some variables have been eliminated, 4095 4095 // then pass to a new ring which has less variables, 4096 4096 // but if no variables are left, then we are done 4097 4097 def BASERING=basering; 4098 if ((numberdeletedvariables>0) and (anzahlvariablen>1)) // if only t remains, 4098 if ((numberdeletedvariables>0) and (anzahlvariablen>1)) // if only t remains, 4099 4099 { // all true variables are gone 4100 4100 execute("ring NEURING=("+charstr(basering)+"),("+string(variablen)+"),(dp("+string(size(variablen)-1)+"),lp(1));"); 4101 4101 ideal i=imap(BASERING,i); 4102 ideal gesamt_m=imap(BASERING,gesamt_m); 4103 } 4104 // now we have to compute a point ww on the tropical variety 4102 ideal gesamt_m=imap(BASERING,gesamt_m); 4103 } 4104 // now we have to compute a point ww on the tropical variety 4105 4105 // of the transformed ideal i; 4106 // of course, we only have to do so, if we have not yet 4106 // of course, we only have to do so, if we have not yet 4107 4107 // reached the order up to which we 4108 4108 // were supposed to do our computations 4109 if ((ordnung>1) and (anzahlvariablen>1)) // if only t remains, 4109 if ((ordnung>1) and (anzahlvariablen>1)) // if only t remains, 4110 4110 { // all true variables are gone 4111 4111 def PREGFANRING=basering; 4112 4112 if (nogfan!=1) 4113 { 4113 { 4114 4114 // pass to a ring which has variables which are suitable for gfan 4115 4115 execute("ring GFANRING=("+charstr(basering)+"),(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z),dp;"); 4116 ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; 4116 ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; 4117 4117 phiideal[nvars(PREGFANRING)]=a; // map t to a 4118 map phi=PREGFANRING,phiideal; 4118 map phi=PREGFANRING,phiideal; 4119 4119 ideal i=phi(i); 4120 // homogenise the ideal i with the first not yet 4121 // used variable in our ring, since gfan 4122 // only handles homogenous ideals; in principle 4120 // homogenise the ideal i with the first not yet 4121 // used variable in our ring, since gfan 4122 // only handles homogenous ideals; in principle 4123 4123 // for this one has first to compute a 4124 // standard basis of i and homogenise that, 4125 // but for the tropical variety (says Anders) 4124 // standard basis of i and homogenise that, 4125 // but for the tropical variety (says Anders) 4126 4126 // it suffices to homogenise an arbitrary system of generators 4127 // i=groebner(i); 4127 // i=groebner(i); 4128 4128 i=homog(i,maxideal(1)[nvars(PREGFANRING)+1]); 4129 4129 // if gfan version >= 0.3.0 is used and the characteristic … … 4137 4137 write(":a /tmp/gfaninput","{"+string(i)+"}"); 4138 4138 } 4139 else 4139 else 4140 4140 { 4141 4141 // write the ideal to a file which gfan takes as input and call gfan … … 4158 4158 string trop=read("/tmp/gfanoutput"); 4159 4159 setring PREGFANRING; 4160 intvec wneu=-1; // this integer vector will store 4160 intvec wneu=-1; // this integer vector will store 4161 4161 // the point on the tropical variety 4162 4162 wneu[nvars(basering)]=0; … … 4171 4171 "IF YOU WANT wneu TO BE TESTED, THEN SET goon=0;"; 4172 4172 ~ 4173 // THIS IS NOT NECESSARY !!!! IF WE COMPUTE NOT ONLY THE 4173 // THIS IS NOT NECESSARY !!!! IF WE COMPUTE NOT ONLY THE 4174 4174 // TROPICAL PREVARIETY 4175 // test, if wneu really is in the tropical variety 4175 // test, if wneu really is in the tropical variety 4176 4176 while (goon==0) 4177 4177 { … … 4190 4190 { 4191 4191 system("sh","gfan_tropicallifting -n "+string(anzahlvariablen)+" --noMult -c < /tmp/gfaninput > /tmp/gfanoutput"); 4192 // read the result from gfan and store it to a string, 4192 // read the result from gfan and store it to a string, 4193 4193 // which in a later version 4194 4194 // should be interpreded by Singular … … 4203 4203 } 4204 4204 } 4205 // if we have not yet computed our parametrisation 4205 // if we have not yet computed our parametrisation 4206 4206 // up to the required order and 4207 // zero is not yet a solution, then we have 4207 // zero is not yet a solution, then we have 4208 4208 // to go on by calling the procedure recursively; 4209 4209 // if all variables were deleted, then i=0 and thus anzahlvariablen==0 4210 4210 if ((ordnung>1) and (anzahlvariablen>1)) 4211 { 4212 // we call the procedure with the transformed ideal i, 4211 { 4212 // we call the procedure with the transformed ideal i, 4213 4213 // the new weight vector, with the 4214 // required order lowered by one, and with 4214 // required order lowered by one, and with 4215 4215 // additional parameters, namely the number of 4216 // true variables and the maximal ideal that 4216 // true variables and the maximal ideal that 4217 4217 // was computed so far to describe the field extension 4218 4218 list PARALIST=tropicalparametriseNoabs(i,wneu,ordnung-1,gfanold,nogfan,anzahlvariablen,gesamt_m); 4219 // the output will be a ring, in which the 4219 // the output will be a ring, in which the 4220 4220 // parametrisation lives, and a string, which contains 4221 4221 // the maximal ideal that describes the necessary field extension … … 4224 4224 string PARAm=PARALIST[3]; 4225 4225 setring PARARing; 4226 // if some variables have been eliminated in before, 4227 // then we have to insert zeros 4226 // if some variables have been eliminated in before, 4227 // then we have to insert zeros 4228 4228 // into the parametrisation for those variables 4229 4229 if (numberdeletedvariables>0) … … 4231 4231 ideal PARAneu=PARA; 4232 4232 int k; 4233 for (jj=1;jj<=anzahlvariablen+numberdeletedvariables-1;jj++) // t admits 4233 for (jj=1;jj<=anzahlvariablen+numberdeletedvariables-1;jj++) // t admits 4234 4234 { // no parametrisation 4235 4235 if (deletedvariables[jj]!=1) … … 4245 4245 } 4246 4246 } 4247 // otherwise we are done and we can start to compute 4247 // otherwise we are done and we can start to compute 4248 4248 // the last step of the parametrisation 4249 4249 else … … 4251 4251 // we store the information on m in a string 4252 4252 string PARAm=string(gesamt_m); 4253 // we define the weight of t, i.e. in the parametrisation t 4253 // we define the weight of t, i.e. in the parametrisation t 4254 4254 // has to be replaced by t^1/tweight 4255 4255 int tweight=-tw[1]; 4256 // if additional variables were necessary, 4256 // if additional variables were necessary, 4257 4257 // we introduce them now as parameters; 4258 // in any case the parametrisation ring will 4259 // have only one variable, namely t, 4260 // and its order will be local, so that it 4258 // in any case the parametrisation ring will 4259 // have only one variable, namely t, 4260 // and its order will be local, so that it 4261 4261 // displays the lowest term in t first 4262 4262 if (anzahlvariablen+numberdeletedvariables<nvars(basering)) … … 4269 4269 } 4270 4270 ideal PARA; // will contain the parametrisation 4271 // we start by initialising the entries to be zero; 4271 // we start by initialising the entries to be zero; 4272 4272 // one entry for each true variable 4273 // here we also have to consider the variables 4273 // here we also have to consider the variables 4274 4274 // that we have eliminated in before 4275 4275 for (jj=1;jj<=anzahlvariablen+numberdeletedvariables-1;jj++) … … 4278 4278 } 4279 4279 } 4280 // we now have to change the parametrisation by 4280 // we now have to change the parametrisation by 4281 4281 // reverting the transformations that we have done 4282 4282 list a=imap(BASERING,a); 4283 if (defined(wneu)==0) // when tropicalparametriseNoabs is called for the 4284 { // last time, it does not enter the part, where wneu is defined and the 4283 if (defined(wneu)==0) // when tropicalparametriseNoabs is called for the 4284 { // last time, it does not enter the part, where wneu is defined and the 4285 4285 intvec wneu=-1; // variable t should have weight -1 4286 4286 } … … 4289 4289 PARA[jj]=(PARA[jj]+a[jj+1])*t^(tw[jj+1]*tweight/ww[1]); 4290 4290 } 4291 // if we have reached the stop-level, i.e. either 4291 // if we have reached the stop-level, i.e. either 4292 4292 // we had only to compute up to order 1 4293 // or zero was a solution of the ideal, then we have 4293 // or zero was a solution of the ideal, then we have 4294 4294 // to export the computed parametrisation 4295 4295 // otherwise it has already been exported before 4296 4296 // note, if all variables were deleted, then i==0 and thus testaufnull==0 4297 4297 if ((ordnung==1) or (anzahlvariablen==1)) 4298 { 4298 { 4299 4299 export(PARA); 4300 4300 } 4301 4301 // kill the gfan files in /tmp 4302 system("sh","cd /tmp; /usr/bin/touch gfaninput; /usr/bin/touch gfanoutput; /bin/rm gfaninput; /bin/rm gfanoutput"); 4303 // we return a list which contains the 4302 system("sh","cd /tmp; /usr/bin/touch gfaninput; /usr/bin/touch gfanoutput; /bin/rm gfaninput; /bin/rm gfanoutput"); 4303 // we return a list which contains the 4304 4304 // parametrisation ring (with the parametrisation ideal) 4305 // and the string representing the maximal ideal 4305 // and the string representing the maximal ideal 4306 4306 // describing the necessary field extension 4307 4307 return(list(PARARing,tweight,PARAm)); … … 4312 4312 static proc findzeros (ideal i,intvec w,list #) 4313 4313 "USAGE: findzeros(i,w[,#]); i ideal, w intvec, # an optional list 4314 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_n+1,...,X_m] and 4314 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_n+1,...,X_m] and 4315 4315 w=(w_0,...,w_n,0,...,0) is in the tropical variety of i 4316 RETURN: list, l[1] = is polynomial ring containing an associated maximal 4317 ideal m of the w-initial ideal of i which does not 4316 RETURN: list, l[1] = is polynomial ring containing an associated maximal 4317 ideal m of the w-initial ideal of i which does not 4318 4318 contain any monomial and where the variables 4319 which do not lead to a field extension have already 4320 been eliminated, and containing a list a such that 4321 the non-zero entries of a correspond to the values 4319 which do not lead to a field extension have already 4320 been eliminated, and containing a list a such that 4321 the non-zero entries of a correspond to the values 4322 4322 of the zero of the associated maximal ideal for the 4323 4323 eliminated variables 4324 4324 l[2] = number of variables which have not been eliminated 4325 l[3] = intvec, if the entry is one then the corresponding 4325 l[3] = intvec, if the entry is one then the corresponding 4326 4326 variable has not been eliminated 4327 NOTE: the procedure is called from inside the recursive procedure 4327 NOTE: the procedure is called from inside the recursive procedure 4328 4328 tropicalparametriseNoabs; 4329 if it is called in the first recursion, the list #[1] contains 4330 the t-initial ideal of i w.r.t. w, otherwise #[1] is an integer, 4329 if it is called in the first recursion, the list #[1] contains 4330 the t-initial ideal of i w.r.t. w, otherwise #[1] is an integer, 4331 4331 one more than the number of true variables x_1,...,x_n" 4332 4332 { 4333 def BASERING=basering; 4333 def BASERING=basering; 4334 4334 // set anzahlvariablen to the number of true variables 4335 4335 if (typeof(#[1])=="int") … … 4337 4337 int anzahlvariablen=#[1]; 4338 4338 // compute the initial ideal of i 4339 // - the last 1 just means that the variable t is the last 4339 // - the last 1 just means that the variable t is the last 4340 4340 // variable in the ring 4341 4341 ideal ini=tInitialIdeal(i,w,1); … … 4344 4344 { 4345 4345 int anzahlvariablen=nvars(basering); 4346 ideal ini=#[1]; // the t-initial ideal has been computed 4346 ideal ini=#[1]; // the t-initial ideal has been computed 4347 4347 // in before and was handed over 4348 4348 } 4349 // move to a polynomial ring with global monomial ordering 4349 // move to a polynomial ring with global monomial ordering 4350 4350 // - the variable t is superflous 4351 4351 ideal variablen; 4352 4352 for (int j=1;j<=nvars(basering)-1;j++) 4353 { 4353 { 4354 4354 variablen=variablen+var(j); 4355 4355 } … … 4357 4357 ideal ini=imap(BASERING,ini); 4358 4358 // compute the associated primes of the initialideal 4359 // ordering the maximal ideals shall help to avoid 4359 // ordering the maximal ideals shall help to avoid 4360 4360 // unneccessary field extensions 4361 4361 list maximalideals=ordermaximalidealsNoabs(minAssGTZ(std(ini)),anzahlvariablen); 4362 4362 ideal m=maximalideals[1][1]; // the first associated maximal ideal 4363 4363 int neuvar=maximalideals[1][2]; // the number of new variables needed 4364 intvec neuevariablen=maximalideals[1][3]; // the information which variable 4364 intvec neuevariablen=maximalideals[1][3]; // the information which variable 4365 4365 // leads to a new one 4366 list a=maximalideals[1][4]; // a_k is the kth component of a 4366 list a=maximalideals[1][4]; // a_k is the kth component of a 4367 4367 // zero of m, if it is not zero 4368 // eliminate from m the superflous variables, that is those ones, 4368 // eliminate from m the superflous variables, that is those ones, 4369 4369 // which do not lead to a new variable 4370 4370 poly elimvars=1; … … 4376 4376 } 4377 4377 } 4378 m=eliminate(m,elimvars); 4379 export(a); 4378 m=eliminate(m,elimvars); 4379 export(a); 4380 4380 export(m); 4381 4381 list m_ring=INITIALRING,neuvar,neuevariablen; … … 4389 4389 static proc basictransformideal (ideal i,intvec w,list m_ring,list #) 4390 4390 "USAGE: basictransformideal(i,w,m_ring[,#]); i ideal, w intvec, m_ring list, # an optional list 4391 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k], 4392 w=(w_0,...,w_n,0,...,0) is in the tropical variety of i, and 4391 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k], 4392 w=(w_0,...,w_n,0,...,0) is in the tropical variety of i, and 4393 4393 m_ring contains a ring containing a maximal ideal m needed 4394 to describe the field extension over which a corresponding 4395 associated maximal ideal of the initialideal of i, considered 4396 in (Q[X_1,...,X_k]/m_alt)(t)[x_1,...,x_n], has a zero, and 4394 to describe the field extension over which a corresponding 4395 associated maximal ideal of the initialideal of i, considered 4396 in (Q[X_1,...,X_k]/m_alt)(t)[x_1,...,x_n], has a zero, and 4397 4397 containing a list a describing the zero of m, and m_ring contains 4398 4398 the information how many new variables are needed for m … … 4401 4401 l[3] = ideal, the maximal ideal m 4402 4402 or l[1] = ring which contains the ideals i and m, and the list a 4403 NOTE: the procedure is called from inside the recursive procedure 4403 NOTE: the procedure is called from inside the recursive procedure 4404 4404 tropicalparametriseNoabs; 4405 if it is called in the first recursion, the list # is empty, 4405 if it is called in the first recursion, the list # is empty, 4406 4406 otherwise #[1] is an integer, the number of true variables x_1,...,x_n; 4407 during the procedure we check if a field extension is necessary 4408 to express a zero (a_1,...,a_n) of m; if so, we have to introduce 4409 new variables and a list containing a ring is returned, otherwise 4410 the list containing i, a and m is returned; 4411 the ideal m will be changed during the procedure since all variables 4407 during the procedure we check if a field extension is necessary 4408 to express a zero (a_1,...,a_n) of m; if so, we have to introduce 4409 new variables and a list containing a ring is returned, otherwise 4410 the list containing i, a and m is returned; 4411 the ideal m will be changed during the procedure since all variables 4412 4412 which reduce to a polynomial in X_1,...,X_k modulo m will be eliminated, 4413 4413 while the others are replaced by new variables X_k+1,...,X_k'" … … 4421 4421 wdegs[j]=deg(i[j],intvec(w[2..size(w)],w[1])); 4422 4422 } 4423 // how many variables are true variables, 4423 // how many variables are true variables, 4424 4424 // and how many come from the field extension 4425 4425 // only real variables have to be transformed … … 4436 4436 // get the information if any new variables are needed from m_ring 4437 4437 int neuvar=m_ring[2]; // number of variables which have to be added 4438 intvec neuevariablen=m_ring[3]; // [i]=1, if for the ith comp. 4438 intvec neuevariablen=m_ring[3]; // [i]=1, if for the ith comp. 4439 4439 // of a zero of m a new variable is needed 4440 4440 def MRING=m_ring[1]; // MRING contains a and m 4441 list a=imap(MRING,a); // (a_1,...,a_n)=(a[2],...,a[n+1]) will be 4441 list a=imap(MRING,a); // (a_1,...,a_n)=(a[2],...,a[n+1]) will be 4442 4442 // a common zero of the ideal m 4443 ideal m=std(imap(MRING,m)); // m is zero, if neuvar==0, 4443 ideal m=std(imap(MRING,m)); // m is zero, if neuvar==0, 4444 4444 // otherwise we change the ring anyway 4445 // if a field extension is needed, then extend the polynomial 4445 // if a field extension is needed, then extend the polynomial 4446 4446 // ring by new variables X_k+1,...,X_k'; 4447 4447 if (neuvar>0) 4448 4448 { 4449 // change to a ring where for each variable needed 4449 // change to a ring where for each variable needed 4450 4450 // in m a new variable has been introduced 4451 4451 ideal variablen; … … 4458 4458 // map i into the new ring 4459 4459 ideal i=imap(BASERING,i); 4460 // define a map phi which maps the true variables, which are not 4460 // define a map phi which maps the true variables, which are not 4461 4461 // reduced to polynomials in the additional variables modulo m, to 4462 // the corresponding newly introduced variables, and which maps 4462 // the corresponding newly introduced variables, and which maps 4463 4463 // the old additional variables to themselves 4464 4464 ideal phiideal; 4465 4465 k=1; 4466 for (j=2;j<=size(neuevariablen);j++) // starting with 2, since the 4466 for (j=2;j<=size(neuevariablen);j++) // starting with 2, since the 4467 4467 { // first entry corresponds to t 4468 4468 if(neuevariablen[j]==1) … … 4473 4473 else 4474 4474 { 4475 phiideal[j-1]=0; 4475 phiideal[j-1]=0; 4476 4476 } 4477 4477 } … … 4480 4480 phiideal=phiideal,X(1..nvars(BASERING)-anzahlvariablen); 4481 4481 } 4482 map phi=MRING,phiideal; 4483 // map m and a to the new ring via phi, so that the true variables 4482 map phi=MRING,phiideal; 4483 // map m and a to the new ring via phi, so that the true variables 4484 4484 // in m and a are replaced by 4485 4485 // the corresponding newly introduced variables … … 4487 4487 list a=phi(a); 4488 4488 } 4489 // replace now the zeros among the a_j by the corresponding 4489 // replace now the zeros among the a_j by the corresponding 4490 4490 // newly introduced variables; 4491 // note that no component of a can be zero 4491 // note that no component of a can be zero 4492 4492 // since the maximal ideal m contains no variable! 4493 // moreover, substitute right away in the ideal i 4493 // moreover, substitute right away in the ideal i 4494 4494 // the true variable x_j by (a_j+x_j)*t^w_j 4495 4495 zaehler=nvars(BASERING)-anzahlvariablen+1; 4496 for (j=1;j<=anzahlvariablen;j++) 4496 for (j=1;j<=anzahlvariablen;j++) 4497 4497 { 4498 4498 if ((a[j]==0) and (j!=1)) // a[1]=0, since t->t^w_0 4499 { 4499 { 4500 4500 a[j]=X(zaehler); 4501 4501 zaehler++; … … 4504 4504 { 4505 4505 if (j!=1) // corresponds to x_(j-1) -- note t is the last variable 4506 { 4506 { 4507 4507 i[k]=substitute(i[k],var(j-1),(a[j]+var(j-1))*t^(-w[j])); 4508 4508 } … … 4516 4516 for (j=1;j<=ncols(i);j++) 4517 4517 { 4518 if (wdegs[j]<0) // if wdegs[j]==0 there is no need to divide, and 4518 if (wdegs[j]<0) // if wdegs[j]==0 there is no need to divide, and 4519 4519 { // we made sure that it is no positive 4520 4520 i[j]=i[j]/t^(-wdegs[j]); 4521 4521 } 4522 4522 } 4523 // since we want to consider i now in the ring 4523 // since we want to consider i now in the ring 4524 4524 // (Q[X_1,...,X_k']/m)[t,x_1,...,x_n] 4525 // we can reduce i modulo m, so that "constant terms" 4525 // we can reduce i modulo m, so that "constant terms" 4526 4526 // which are "zero" since they 4527 4527 // are in m will disappear; simplify(...,2) then really removes them 4528 4528 i=simplify(reduce(i,m),2); 4529 // if new variables have been introduced, we have 4529 // if new variables have been introduced, we have 4530 4530 // to return the ring containing i, a and m 4531 4531 // otherwise we can simply return a list containing i, a and m … … 4548 4548 static proc testw (ideal i,intvec w,int anzahlvariablen,list #) 4549 4549 "USAGE: testw(i,w,n); i ideal, w intvec, n number 4550 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k] and 4551 w=(w_0,...,w_n,0,...,0) 4552 RETURN: int b, 0 if the t-initial ideal of i considered in 4550 ASSUME: i is an ideal in Q[t,x_1,...,x_n,X_1,...,X_k] and 4551 w=(w_0,...,w_n,0,...,0) 4552 RETURN: int b, 0 if the t-initial ideal of i considered in 4553 4553 Q(X_1,...,X_k)[t,x_1,...,x_n] is monomial free, 1 else 4554 4554 NOTE: the procedure is called by tinitialform" … … 4564 4564 ideal tin=tInitialIdeal(i,w,1); 4565 4565 } 4566 4566 4567 4567 int j; 4568 4568 ideal variablen; … … 4596 4596 def BASERING=basering; 4597 4597 if (anzahlvariablen<nvars(basering)) 4598 { 4598 { 4599 4599 execute("ring TINRING=("+charstr(basering)+","+string(Parameter)+"),("+string(variablen)+"),dp;"); 4600 4600 } … … 4606 4606 poly monom=imap(BASERING,monom); 4607 4607 return(radicalMemberShip(monom,tin)); 4608 } 4608 } 4609 4609 4610 4610 ///////////////////////////////////////////////////////////////////////// … … 4612 4612 static proc simplifyToOrder (poly f) 4613 4613 "USAGE: simplifyToOrder(f); f a polynomial 4614 ASSUME: f is a polynomial in Q(t)[x_1,...,x_n] 4614 ASSUME: f is a polynomial in Q(t)[x_1,...,x_n] 4615 4615 RETURN: list, l[1] = t-order of leading term of f 4616 4616 l[2] = the rational coefficient of the term of lowest t-order … … 4635 4635 static proc scalarproduct (intvec w,intvec v) 4636 4636 "USAGE: scalarproduct(w,v); w,v intvec 4637 ASSUME: w and v are integer vectors of the same length 4637 ASSUME: w and v are integer vectors of the same length 4638 4638 RETURN: int, the scalarproduct of v and w 4639 4639 NOTE: the procedure is called by tropicalparametriseNoabs" … … 4693 4693 "USAGE: ordermaximalidealsNoabs(minassi); minassi list 4694 4694 ASSUME: minassi is a list of maximal ideals 4695 RETURN: list, the procedure orders the maximal ideals in minassi according 4696 to how many new variables are needed to describe the zeros 4695 RETURN: list, the procedure orders the maximal ideals in minassi according 4696 to how many new variables are needed to describe the zeros 4697 4697 of the ideal 4698 4698 l[j][1] = jth maximal ideal 4699 4699 l[j][2] = the number of variables needed 4700 l[j][3] = intvec, if for the kth variable a new variable is 4701 needed to define the corresponding zero of 4700 l[j][3] = intvec, if for the kth variable a new variable is 4701 needed to define the corresponding zero of 4702 4702 l[j][1], then the k+1st entry is one 4703 l[j][4] = list, if for the kth variable no new variable is 4704 needed to define the corresponding zero of 4703 l[j][4] = list, if for the kth variable no new variable is 4704 needed to define the corresponding zero of 4705 4705 l[j][1], then its value is the k+1st entry 4706 4706 NOTE: if a maximal ideal contains a variable, it is removed from the list; … … 4711 4711 int pruefer; // is set one if a maximal ideal contains a variable 4712 4712 list minassisort; // will contain the output 4713 for (j=1;j<=size(minassi);j++){minassisort[j]=0;} // initialise minassisort 4713 for (j=1;j<=size(minassi);j++){minassisort[j]=0;} // initialise minassisort 4714 4714 // to fix its initial length 4715 4715 list zwischen; // needed for reordering 4716 4716 list a;// (a_1,...,a_n)=(a[2],...,a[n+1]) will be a common zero of the ideal m 4717 4717 poly nf; // normalform of a variable w.r.t. m 4718 intvec neuevariablen; // ith entry is 1, if for the ith component of a zero 4718 intvec neuevariablen; // ith entry is 1, if for the ith component of a zero 4719 4719 // of m a new variable is needed 4720 4720 intvec testvariablen; // integer vector of length n=number of variables 4721 // compute for each maximal ideal the number of new variables, 4721 // compute for each maximal ideal the number of new variables, 4722 4722 // which are needed to describe 4723 // its zeros -- note, a new variable is needed if modulo 4724 // the maximal ideal it does not reduce 4723 // its zeros -- note, a new variable is needed if modulo 4724 // the maximal ideal it does not reduce 4725 4725 // to something which only depends on the following variables; 4726 // if no new variable is needed, then store the value 4727 // a variable reduces to in the list a; 4726 // if no new variable is needed, then store the value 4727 // a variable reduces to in the list a; 4728 4728 for (j=size(minassi);j>=1;j--) 4729 4729 { 4730 a[1]=poly(0); // the first entry in a and in neuevariablen 4730 a[1]=poly(0); // the first entry in a and in neuevariablen 4731 4731 // corresponds to the variable t, 4732 4732 neuevariablen[1]=0; // which is not present in the INITIALRING … … 4736 4736 { 4737 4737 nf=reduce(var(k),minassi[j]); 4738 // if a variable reduces to zero, then the maximal ideal 4738 // if a variable reduces to zero, then the maximal ideal 4739 4739 // contains a variable and we can delete it 4740 4740 if (nf==0) … … 4742 4742 pruefer=1; 4743 4743 } 4744 // set the entries of testvariablen corresponding to the first 4744 // set the entries of testvariablen corresponding to the first 4745 4745 // k variables to 1, and the others to 0 4746 4746 for (l=1;l<=nvars(basering);l++) 4747 4747 { 4748 4748 if (l<=k) 4749 { 4749 { 4750 4750 testvariablen[l]=1; 4751 4751 } … … 4755 4755 } 4756 4756 } 4757 // if the variable x_j reduces to a polynomial 4757 // if the variable x_j reduces to a polynomial 4758 4758 // in x_j+1,...,x_n,X_1,...,X_k modulo m 4759 // then we can eliminate x_j from the maximal ideal 4759 // then we can eliminate x_j from the maximal ideal 4760 4760 // (since we do not need any 4761 // further field extension to express a_j) and a_j 4761 // further field extension to express a_j) and a_j 4762 4762 // will just be this normalform, 4763 4763 // otherwise we have to introduce a new variable in order to express a_j; … … 4766 4766 a[k+1]=nf; // a_k is the normal form of the kth variable modulo m 4767 4767 neuevariablen[k+1]=0; // no new variable is needed 4768 } 4768 } 4769 4769 else 4770 4770 { 4771 a[k+1]=poly(0); // a_k is set to zero until we have 4771 a[k+1]=poly(0); // a_k is set to zero until we have 4772 4772 // introduced the new variable 4773 4773 neuevariablen[k+1]=1; … … 4777 4777 // if the maximal ideal contains a variable, we simply delete it 4778 4778 if (pruefer==0) 4779 { 4779 { 4780 4780 minassisort[j]=list(minassi[j],neuvar,neuevariablen,a); 4781 4781 } 4782 // otherwise we store the information on a, 4782 // otherwise we store the information on a, 4783 4783 // neuevariablen and neuvar together with the ideal 4784 4784 else … … 4789 4789 } 4790 4790 } 4791 // sort the maximal ideals ascendingly according to 4791 // sort the maximal ideals ascendingly according to 4792 4792 // the number of new variables needed to 4793 4793 // express the zero of the maximal ideal … … 4796 4796 l=j; 4797 4797 for (k=j-1;k>=1;k--) 4798 { 4798 { 4799 4799 if (minassisort[l][2]<minassisort[k][2]) 4800 4800 { … … 4814 4814 "USAGE: displaypoly(p,N,wj,w1); p poly, N, wj, w1 int 4815 4815 ASSUME: p is a polynomial in r=(0,X(1..k)),t,ls 4816 RETURN: string, the string of t^-wj/w1*p(t^1/N) 4816 RETURN: string, the string of t^-wj/w1*p(t^1/N) 4817 4817 NOTE: the procedure is called from displayTropicalLifting" 4818 4818 { … … 4832 4832 { 4833 4833 if (koeffizienten[j-ord(p)+1]!=0) 4834 { 4834 { 4835 4835 if ((j-(N*wj)/w1)==0) 4836 4836 { … … 4882 4882 static proc displaycoef (poly p) 4883 4883 "USAGE: displaycoef(p); p poly 4884 RETURN: string, the string of p where brackets around 4884 RETURN: string, the string of p where brackets around 4885 4885 have been added if they were missing 4886 4886 NOTE: the procedure is called from displaypoly" … … 4954 4954 static proc tropicalliftingresubstitute (ideal i,list liftring,int N,list #) 4955 4955 "USAGE: tropicalliftingresubstitute(i,L,N[,#]); i ideal, L list, N int, # string 4956 ASSUME: i is an ideal and L[1] is a ring which contains the lifting of a 4957 point in the tropical variety of i computed with tropicalLifting; 4958 t has to be replaced by t^1/N in the lifting; #[1]=m is the string 4959 of the maximal ideal defining the necessary field extension as 4956 ASSUME: i is an ideal and L[1] is a ring which contains the lifting of a 4957 point in the tropical variety of i computed with tropicalLifting; 4958 t has to be replaced by t^1/N in the lifting; #[1]=m is the string 4959 of the maximal ideal defining the necessary field extension as 4960 4960 computed by tropicalLifting, if #[1] is present 4961 4961 RETURN: string, the lifting has been substituted into i … … 4980 4980 ideal i=imap(BASERING,i); 4981 4981 } 4982 } 4982 } 4983 4983 else 4984 4984 { … … 4993 4993 } 4994 4994 // map the resulting i back to LIFTRing; 4995 // if noAbs, then reduce i modulo the maximal ideal 4995 // if noAbs, then reduce i modulo the maximal ideal 4996 4996 // before going back to LIFTRing 4997 4997 if ((size(parstr(LIFTRing))!=0) and size(#)>0) … … 5010 5010 for (j=1;j<=ncols(i);j++) 5011 5011 { 5012 SUBSTTEST[j]=displaypoly(i[j],N,0,1); 5012 SUBSTTEST[j]=displaypoly(i[j],N,0,1); 5013 5013 } 5014 5014 return(SUBSTTEST); … … 5020 5020 /// - eliminatecomponents 5021 5021 /// - findzerosAndBasictransform 5022 /// - ordermaximalideals 5022 /// - ordermaximalideals 5023 5023 /////////////////////////////////////////////////////////////////////////////// 5024 5024 5025 5025 static proc tropicalparametrise (ideal i,intvec ww,int ordnung,int gfanold,int findall,int nogfan,list #) 5026 5026 "USAGE: tropicalparametrise(i,tw,ord,gf,fa,ng[,#]); i ideal, tw intvec, ord int, gf,fa,ng int, # opt. list 5027 ASSUME: - i is an ideal in Q[t,x_1,...,x_n,@a], tw=(w_0,w_1,...,w_n,0) 5028 and (w_0,...,w_n,0) is in the tropical variety of i, 5029 and ord is the order up to which a point in V(i) 5030 over K{{t}} lying over w shall be computed; 5031 - moreover, @a should be not be there if the procedure is not 5027 ASSUME: - i is an ideal in Q[t,x_1,...,x_n,@a], tw=(w_0,w_1,...,w_n,0) 5028 and (w_0,...,w_n,0) is in the tropical variety of i, 5029 and ord is the order up to which a point in V(i) 5030 over K{{t}} lying over w shall be computed; 5031 - moreover, @a should be not be there if the procedure is not 5032 5032 called recursively; 5033 5033 - the point in the tropical variety is supposed to lie in the 5034 5034 NEGATIVE orthant; 5035 - the ideal is zero-dimensional when considered in 5036 (K(t)[@a]/m)[x_1,...,x_n], where m=#[2] is a maximal ideal in K[@a]; 5035 - the ideal is zero-dimensional when considered in 5036 (K(t)[@a]/m)[x_1,...,x_n], where m=#[2] is a maximal ideal in K[@a]; 5037 5037 - gf is 0 if version 2.2 or larger is used and it is 1 else 5038 5038 - fa is 1 if all solutions should be found … … 5041 5041 l[2] = int 5042 5042 NOTE: - the procedure is also called recursively by itself, and 5043 if it is called in the first recursion, the list # is empty, 5044 otherwise #[1] is an integer, one more than the number of 5045 true variables x_1,...,x_n, and #[2] will contain the maximal 5046 ideal m in the variable @a by which the ring K[t,x_1,...,x_n,@a] 5047 should be divided to work correctly in L[t,x_1,...,x_n] where 5043 if it is called in the first recursion, the list # is empty, 5044 otherwise #[1] is an integer, one more than the number of 5045 true variables x_1,...,x_n, and #[2] will contain the maximal 5046 ideal m in the variable @a by which the ring K[t,x_1,...,x_n,@a] 5047 should be divided to work correctly in L[t,x_1,...,x_n] where 5048 5048 L=Q[@a]/m is a field extension of K 5049 - the ring l[1] contains an ideal PARA, which contains the 5050 parametrisation of a point in V(i) lying over w up to the first 5049 - the ring l[1] contains an ideal PARA, which contains the 5050 parametrisation of a point in V(i) lying over w up to the first 5051 5051 ord terms; 5052 - the string m contains the code of the maximal ideal m, by which we 5052 - the string m contains the code of the maximal ideal m, by which we 5053 5053 have to divide K[@a] in order to have the appropriate field extension 5054 5054 over which the parametrisation lives; 5055 5055 - and if the integer l[3] is N then t has to be replaced by t^1/N in the 5056 parametrisation, or alternatively replace t by t^N in the defining 5056 parametrisation, or alternatively replace t by t^N in the defining 5057 5057 ideal 5058 - the procedure REQUIRES that the program GFAN is installed 5058 - the procedure REQUIRES that the program GFAN is installed 5059 5059 on your computer" 5060 5060 { … … 5062 5062 int recursively; // is set 1 if the procedure is called recursively by itself 5063 5063 int ii,jj,kk,ll,jjj,kkk,lll; 5064 if (typeof(#[1])=="int") // this means the precedure has been 5064 if (typeof(#[1])=="int") // this means the precedure has been 5065 5065 { // called recursively 5066 // how many variables are true variables, and how many come 5066 // how many variables are true variables, and how many come 5067 5067 // from the field extension 5068 5068 // only true variables have to be transformed 5069 5069 int anzahlvariablen=#[1]; 5070 5070 // find the zeros of the w-initial ideal and transform the ideal i; 5071 // findzeros and basictransformideal need to know 5071 // findzeros and basictransformideal need to know 5072 5072 // how many of the variables are true variables 5073 5073 // and do the basic transformation as well … … 5077 5077 else // the procedure has been called by tropicalLifting 5078 5078 { 5079 // how many variables are true variables, and 5079 // how many variables are true variables, and 5080 5080 // how many come from the field extension 5081 5081 // only true variables have to be transformed 5082 5082 int anzahlvariablen=nvars(basering); 5083 list zerolist; // will carry the zeros which are 5084 //computed in the recursion steps 5083 list zerolist; // will carry the zeros which are 5084 //computed in the recursion steps 5085 5085 // the initial ideal of i has been handed over as #[1] 5086 5086 ideal ini=#[1]; 5087 5087 // find the zeros of the w-initial ideal and transform the ideal i; 5088 // we should hand the t-initial ideal ine to findzeros, 5088 // we should hand the t-initial ideal ine to findzeros, 5089 5089 // since we know it already; 5090 5090 // and do the basic transformation as well … … 5092 5092 } 5093 5093 list wneulist; // carries all newly computed weight vector 5094 intvec wneu; // carries the newly computed weight vector 5094 intvec wneu; // carries the newly computed weight vector 5095 5095 int tweight; // carries the weight of t 5096 list PARALIST; // carries the result when tropicalparametrise 5096 list PARALIST; // carries the result when tropicalparametrise 5097 5097 // is recursively called 5098 5098 list eliminaterings; // carries the result of eliminatecomponents … … 5103 5103 list liftings,partliftings; // the computed liftings (all resp. partly) 5104 5104 // consider each ring which has been returned when computing the zeros of the 5105 // the t-initial ideal, equivalently, consider 5105 // the t-initial ideal, equivalently, consider 5106 5106 // each zero which has been returned 5107 5107 for (jj=1;jj<=size(trring);jj++) … … 5109 5109 def TRRING=trring[jj]; 5110 5110 setring TRRING; 5111 // check if a certain number of components lead to suitable 5111 // check if a certain number of components lead to suitable 5112 5112 // solutions with zero components; 5113 5113 // compute them all if findall==1 5114 5114 eliminaterings=eliminatecomponents(i,m,oldanzahlvariablen,findall,oldanzahlvariablen-1,deletedvariables); 5115 // consider each of the rings returned by eliminaterings ... 5115 // consider each of the rings returned by eliminaterings ... 5116 5116 // there is at least one !!! 5117 5117 for (ii=1;ii<=size(eliminaterings);ii++) 5118 5118 { 5119 5119 // #variables which have been eliminated 5120 numberdeletedvariables=oldanzahlvariablen-eliminaterings[ii][2]; 5120 numberdeletedvariables=oldanzahlvariablen-eliminaterings[ii][2]; 5121 5121 // #true variables which remain (including t) 5122 anzahlvariablen=eliminaterings[ii][2]; 5122 anzahlvariablen=eliminaterings[ii][2]; 5123 5123 // a 1 in this vector says that variable was eliminated 5124 deletedvariables=eliminaterings[ii][3]; 5124 deletedvariables=eliminaterings[ii][3]; 5125 5125 setring TRRING; // set TRRING - this is important for the loop 5126 5126 // pass the ring computed by eliminatecomponents 5127 def PREGFANRING=eliminaterings[ii][1]; 5127 def PREGFANRING=eliminaterings[ii][1]; 5128 5128 setring PREGFANRING; 5129 5129 poly m=imap(TRRING,m); // map the maximal ideal to this ring 5130 5130 list zero=imap(TRRING,zero); // map the vector of zeros to this ring 5131 // now we have to compute a point ww on the tropical 5131 // now we have to compute a point ww on the tropical 5132 5132 // variety of the transformed ideal i; 5133 // of course, we only have to do so, if we have 5133 // of course, we only have to do so, if we have 5134 5134 // not yet reached the order up to which we 5135 5135 // were supposed to do our computations 5136 if ((ordnung>1) and (anzahlvariablen>1)) // if only t remains, 5136 if ((ordnung>1) and (anzahlvariablen>1)) // if only t remains, 5137 5137 { // all true variables are gone 5138 5138 if (nogfan!=1) 5139 { 5139 { 5140 5140 // pass to a ring which has variables which are suitable for gfan 5141 5141 execute("ring GFANRING=("+string(char(basering))+"),(a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z),dp;"); 5142 ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; 5142 ideal phiideal=b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,q,r,s,t,u,v,w,x,y,z,A,B,C,D,E,F,G,H,I,J,K,L,M,N,O,P,Q,R,S,T,U,V,W,X,Y,Z; 5143 5143 phiideal[nvars(PREGFANRING)]=a; // map t to a 5144 map phi=PREGFANRING,phiideal; 5144 map phi=PREGFANRING,phiideal; 5145 5145 ideal II=phi(i); 5146 // homogenise the ideal II with the first not yet 5147 // used variable in our ring, since gfan 5148 // only handles homogenous ideals; in principle for this 5146 // homogenise the ideal II with the first not yet 5147 // used variable in our ring, since gfan 5148 // only handles homogenous ideals; in principle for this 5149 5149 // one has first to compute a 5150 // standard basis of II and homogenise that, 5151 // but for the tropical variety (says Anders) 5150 // standard basis of II and homogenise that, 5151 // but for the tropical variety (says Anders) 5152 5152 // it suffices to homogenise an arbitrary system of generators 5153 // II=groebner(II); 5153 // II=groebner(II); 5154 5154 II=homog(II,maxideal(1)[nvars(PREGFANRING)+1]); 5155 5155 // if gfan version >= 0.3.0 is used and the characteristic … … 5189 5189 int goon=1; 5190 5190 trop; 5191 "CHOOSE A RAY IN THE OUTPUT OF GFAN WHICH HAS ONLY"; 5191 "CHOOSE A RAY IN THE OUTPUT OF GFAN WHICH HAS ONLY"; 5192 5192 "NON-POSITIVE ENTRIES AND STARTS WITH A NEGATIVE ONE,"; 5193 5193 "E.G. (-3,-4,-1,-5,0,0,0) - the last entry will always be 0 -"; … … 5196 5196 "IF YOU WANT wneu TO BE TESTED, THEN SET goon=0;"; 5197 5197 ~ 5198 // THIS IS NOT NECESSARY !!!! IF WE COMPUTE NOT ONLY 5198 // THIS IS NOT NECESSARY !!!! IF WE COMPUTE NOT ONLY 5199 5199 // THE TROPICAL PREVARIETY 5200 // test, if wneu really is in the tropical variety 5200 // test, if wneu really is in the tropical variety 5201 5201 while (goon==0) 5202 5202 { … … 5216 5216 { 5217 5217 system("sh","gfan_tropicallifting -n "+string(anzahlvariablen)+" --noMult -c < /tmp/gfaninput > /tmp/gfanoutput"); 5218 // read the result from gfan and store it to a string, 5218 // read the result from gfan and store it to a string, 5219 5219 // which in a later version 5220 5220 // should be interpreded by Singular … … 5239 5239 } 5240 5240 } 5241 // if we have not yet computed our parametrisation up to 5241 // if we have not yet computed our parametrisation up to 5242 5242 // the required order and 5243 // zero is not yet a solution, then we have to go on 5243 // zero is not yet a solution, then we have to go on 5244 5244 // by calling the procedure recursively; 5245 5245 // if all variables were deleted, then i=0 and thus anzahlvariablen==0 5246 5246 lll=0; 5247 5247 if ((ordnung>1) and (anzahlvariablen>1)) 5248 { 5248 { 5249 5249 partliftings=list(); // initialise partliftings 5250 // we call the procedure with the transformed 5250 // we call the procedure with the transformed 5251 5251 // ideal i, the new weight vector, with the 5252 // required order lowered by one, and with 5252 // required order lowered by one, and with 5253 5253 // additional parameters, namely the number of 5254 // true variables and the maximal ideal that 5254 // true variables and the maximal ideal that 5255 5255 // was computed so far to describe the field extension 5256 5256 for (kk=1;kk<=size(wneulist);kk++) … … 5258 5258 wneu=wneulist[kk]; 5259 5259 PARALIST=tropicalparametrise(i,wneu,ordnung-1,gfanold,findall,nogfan,anzahlvariablen,zero); 5260 // the output will be a ring, in which the 5260 // the output will be a ring, in which the 5261 5261 // parametrisation lives, and a string, which contains 5262 5262 // the maximal ideal that describes the necessary field extension 5263 5263 for (ll=1;ll<=size(PARALIST);ll++) 5264 { 5264 { 5265 5265 def PARARing=PARALIST[ll][1]; 5266 5266 tweight=-ww[1]*PARALIST[ll][2]; 5267 5267 setring PARARing; 5268 // if some variables have been eliminated 5269 // in before, then we have to insert zeros 5268 // if some variables have been eliminated 5269 // in before, then we have to insert zeros 5270 5270 // into the parametrisation for those variables 5271 5271 if (numberdeletedvariables>0) … … 5273 5273 ideal PARAneu=PARA; 5274 5274 kkk=0; 5275 for (jjj=1;jjj<=anzahlvariablen+numberdeletedvariables-1;jjj++) 5275 for (jjj=1;jjj<=anzahlvariablen+numberdeletedvariables-1;jjj++) 5276 5276 { // t admits no parametrisation 5277 5277 if (deletedvariables[jjj]!=1) … … 5293 5293 } 5294 5294 } 5295 // otherwise we are done and we can start 5295 // otherwise we are done and we can start 5296 5296 // to compute the last step of the parametrisation 5297 5297 else 5298 5298 { 5299 // we define the weight of t, i.e. in the 5299 // we define the weight of t, i.e. in the 5300 5300 // parametrisation t has to be replaced by t^1/tweight 5301 5301 tweight=-ww[1]; 5302 // if additional variables were necessary, 5302 // if additional variables were necessary, 5303 5303 // we introduce them now as parameters; 5304 // in any case the parametrisation ring will 5305 // have only one variable, namely t, 5306 // and its order will be local, so that it 5304 // in any case the parametrisation ring will 5305 // have only one variable, namely t, 5306 // and its order will be local, so that it 5307 5307 // displays the lowest term in t first 5308 5308 if (anzahlvariablen<nvars(basering)) … … 5316 5316 } 5317 5317 ideal PARA; // will contain the parametrisation 5318 // we start by initialising the entries to be zero; 5318 // we start by initialising the entries to be zero; 5319 5319 // one entry for each true variable 5320 // here we also have to consider the variables 5320 // here we also have to consider the variables 5321 5321 // that we have eliminated in before 5322 5322 for (jjj=1;jjj<=anzahlvariablen+numberdeletedvariables-1;jjj++) … … 5330 5330 kill PARARing; 5331 5331 } 5332 // we now have to change the parametrisation by 5332 // we now have to change the parametrisation by 5333 5333 // reverting the transformations that we have done 5334 5334 for (lll=1;lll<=size(partliftings);lll++) 5335 5335 { 5336 if (size(partliftings[lll])==2) // when tropicalparametrise is called 5337 { // for the last time, it does not enter the part, where wneu is 5336 if (size(partliftings[lll])==2) // when tropicalparametrise is called 5337 { // for the last time, it does not enter the part, where wneu is 5338 5338 wneu=-1; // defined and the variable t should have weight -1 5339 5339 } … … 5350 5350 PARA[jjj]=(PARA[jjj]+zeros[size(zeros)][jjj+1])*t^(ww[jjj+1]*tweight/ww[1]); 5351 5351 } 5352 // delete the last entry in zero, since that one has 5352 // delete the last entry in zero, since that one has 5353 5353 // been used for the transformation 5354 5354 zeros=delete(zeros,size(zeros)); 5355 // in order to avoid redefining commands an empty 5355 // in order to avoid redefining commands an empty 5356 5356 // zeros list should be removed 5357 5357 if (size(zeros)==0) … … 5369 5369 } 5370 5370 // kill the gfan files in /tmp 5371 system("sh","cd /tmp; /usr/bin/touch gfaninput; /usr/bin/touch gfanoutput; /bin/rm gfaninput; /bin/rm gfanoutput"); 5372 // we return a list which contains lists of the parametrisation 5371 system("sh","cd /tmp; /usr/bin/touch gfaninput; /usr/bin/touch gfanoutput; /bin/rm gfaninput; /bin/rm gfanoutput"); 5372 // we return a list which contains lists of the parametrisation 5373 5373 // rings (with the parametrisation ideal) 5374 5374 // and an integer N such that t should be replaced by t^1/N … … 5380 5380 static proc eliminatecomponents (ideal i,ideal m,int anzahlvariablen,int findall,int lastvar,intvec deletedvariables) 5381 5381 "USAGE: eliminatecomponents(i,m,n,a,v,d); i,m ideal, n,a,v int, d intvec 5382 ASSUME: i is an ideal in Q[x_1,...,x_n,@a,t] and w=(-w_1/w_0,...,-w_n/w_0) 5383 is in the tropical variety of i considered in 5384 Q[@a]/m{{t}}[x_1,...,x_n]; 5385 considered in this ring i is zero-dimensional; @a need not be present 5382 ASSUME: i is an ideal in Q[x_1,...,x_n,@a,t] and w=(-w_1/w_0,...,-w_n/w_0) 5383 is in the tropical variety of i considered in 5384 Q[@a]/m{{t}}[x_1,...,x_n]; 5385 considered in this ring i is zero-dimensional; @a need not be present 5386 5386 in which case m is zero; 1<=v<=n 5387 5387 RETURN: list, L of lists … … 5389 5389 L[j][2] = an integer anzahlvariablen 5390 5390 L[j][3] = an intvec deletedvariables 5391 NOTE: - the procedure is called from inside the recursive 5391 NOTE: - the procedure is called from inside the recursive 5392 5392 procedure tropicalparametrise 5393 - the procedure checks for solutions which have certain 5394 components zero; these are separated from the rest by 5395 elimination and saturation; the integer deletedvariables 5396 records which variables have been eliminated; 5397 the integer anzahlvariablen records how many true variables remain 5393 - the procedure checks for solutions which have certain 5394 components zero; these are separated from the rest by 5395 elimination and saturation; the integer deletedvariables 5396 records which variables have been eliminated; 5397 the integer anzahlvariablen records how many true variables remain 5398 5398 after the elimination 5399 - if the integer a is one then all zeros of the ideal i are 5400 considered and found, otherwise only one is considered, so that L 5399 - if the integer a is one then all zeros of the ideal i are 5400 considered and found, otherwise only one is considered, so that L 5401 5401 has length one" 5402 5402 { … … 5406 5406 // if all solutions have to be found 5407 5407 if (findall==1) 5408 { 5408 { 5409 5409 list saturatelist,eliminatelist; // carry the solution of the two tests 5410 // we test first if there is a solution which has the component 5411 // lastvar zero and 5410 // we test first if there is a solution which has the component 5411 // lastvar zero and 5412 5412 // where the order of each component is strictly positive; 5413 // if so, we add this variable to the ideal and 5413 // if so, we add this variable to the ideal and 5414 5414 // eliminate it - which amounts to 5415 // to projecting the solutions with this component 5415 // to projecting the solutions with this component 5416 5416 // zero to the hyperplane without this component; 5417 // for the test we compute the saturation with 5417 // for the test we compute the saturation with 5418 5418 // respect to t and replace each variable 5419 // x_i and also t by zero -- if the result is zero, 5420 // then 1 is not in I:t^infty 5419 // x_i and also t by zero -- if the result is zero, 5420 // then 1 is not in I:t^infty 5421 5421 // (i.e. there is a solution which has the component lastvar zero) and 5422 // the result lives in the maximal 5423 // ideal <t,x_1,...,[no x_lastvar],...,x_n> so that 5422 // the result lives in the maximal 5423 // ideal <t,x_1,...,[no x_lastvar],...,x_n> so that 5424 5424 // there is a solution which has strictly positive valuation 5425 5425 /* 5426 5426 // DER NACHFOLGENDE TEIL IST MUELL UND WIRD NICHT MEHR GAMACHT 5427 // for the test we simply compute the leading ideal 5427 // for the test we simply compute the leading ideal 5428 5428 // and set all true variables zero; 5429 // since the ordering was an elimination ordering 5429 // since the ordering was an elimination ordering 5430 5430 // with respect to (@a if present and) t 5431 // there remains something not equal to zero 5431 // there remains something not equal to zero 5432 5432 // if and only if there is polynomial which only 5433 // depends on t (and @a if present), but that is 5433 // depends on t (and @a if present), but that is 5434 5434 // a unit in K{{t}}, which would show that there 5435 5435 // is no solution with the component lastvar zero; 5436 // however, we also have to ensure that if there 5436 // however, we also have to ensure that if there 5437 5437 // exists a solution with the component lastvar 5438 // equal to zero then this component has a 5438 // equal to zero then this component has a 5439 5439 // valuation with all strictly positive values!!!!; 5440 // for this we can either saturate the ideal 5440 // for this we can either saturate the ideal 5441 5441 // after elimination with respect to <t,x_1,...,x_n> 5442 // and see if the saturated ideal is contained in <t,x_1,...x_n>+m, 5443 // or ALTERNATIVELY we can pass to the 5442 // and see if the saturated ideal is contained in <t,x_1,...x_n>+m, 5443 // or ALTERNATIVELY we can pass to the 5444 5444 // ring 0,(t,x_1,...,x_n,@a),(ds(n+1),dp(1)), 5445 // compute a standard basis of the elimination 5445 // compute a standard basis of the elimination 5446 5446 // ideal (plus m) there and check if the dimension 1 5447 // (since we have not omitted the variable lastvar, 5447 // (since we have not omitted the variable lastvar, 5448 5448 // this means that we have the ideal 5449 // generated by t,x_1,...,[no x_lastvar],...,x_n 5449 // generated by t,x_1,...,[no x_lastvar],...,x_n 5450 5450 // and this defines NO curve after omitting x_lastvar) 5451 5451 I=std(ideal(var(lastvar)+i)); … … 5453 5453 LI=lead(reduce(I,std(m))); 5454 5454 //size(deletedvariables)=anzahlvariablen(before elimination) 5455 for (j=1;j<=anzahlvariablen-1;j++) 5455 for (j=1;j<=anzahlvariablen-1;j++) 5456 5456 { 5457 5457 LI=subst(LI,var(j),0); … … 5459 5459 if (size(LI)==0) // if no power of t is in lead(I) (where @a is considered as a field element) 5460 5460 */ 5461 I=reduce(sat(ideal(var(lastvar)+i),t)[1],std(m)); // get rid of the minimal 5461 I=reduce(sat(ideal(var(lastvar)+i),t)[1],std(m)); // get rid of the minimal 5462 5462 // polynomial for the test 5463 5463 LI=subst(I,var(nvars(basering)),0); 5464 5464 //size(deletedvariables)=anzahlvariablen(before elimination) 5465 for (j=1;j<=anzahlvariablen-1;j++) 5465 for (j=1;j<=anzahlvariablen-1;j++) 5466 5466 { 5467 5467 LI=subst(LI,var(j),0); 5468 5468 } 5469 if (size(LI)==0) // the saturation lives in the maximal 5469 if (size(LI)==0) // the saturation lives in the maximal 5470 5470 { // ideal generated by t and the x_i 5471 5471 // get rid of var(lastvar) … … 5482 5482 { 5483 5483 string elring="ring ELIMINATERING=("+charstr(basering)+"),("+string(simplify(reduce(maxideal(1),std(var(lastvar))),2))+"),("; 5484 } 5485 if (anzahlvariablen<nvars(basering)) // if @a was present, the 5484 } 5485 if (anzahlvariablen<nvars(basering)) // if @a was present, the 5486 5486 { // ordersting needs an additional entry 5487 5487 elring=elring+"dp(1),"; 5488 5488 } 5489 5489 elring=elring+"lp(1));"; 5490 execute(elring); 5490 execute(elring); 5491 5491 ideal i=imap(BASERING,I); // move the ideal I to the new ring 5492 // if not yet all variables have been checked, 5492 // if not yet all variables have been checked, 5493 5493 // then go on with the next smaller variable, 5494 // else prepare the elimination ring and the neccessary 5494 // else prepare the elimination ring and the neccessary 5495 5495 // information for return 5496 5496 if (lastvar>1) … … 5505 5505 setring BASERING; 5506 5506 } 5507 // next we have to test if there is also a solution 5507 // next we have to test if there is also a solution 5508 5508 // which has the variable lastvar non-zero; 5509 // to do so, we saturate with respect to this variable; 5510 // since when considered over K{{t}} 5511 // the ideal is zero dimensional, this really removes 5509 // to do so, we saturate with respect to this variable; 5510 // since when considered over K{{t}} 5511 // the ideal is zero dimensional, this really removes 5512 5512 // all solutions with that component zero; 5513 5513 // the checking is then done as above 5514 5514 i=std(sat(i,var(lastvar))[1]); 5515 5515 I=reduce(i,std(m)); // "remove" m from i 5516 // test first, if i still is in the ideal <t,x_1,...,x_n> -- if not, then 5517 // we know that i has no longer a point in the tropical 5516 // test first, if i still is in the ideal <t,x_1,...,x_n> -- if not, then 5517 // we know that i has no longer a point in the tropical 5518 5518 // variety with all components negative 5519 5519 LI=subst(I,var(nvars(basering)),0); 5520 for (j=1;j<=anzahlvariablen-1;j++) // set all variables 5520 for (j=1;j<=anzahlvariablen-1;j++) // set all variables 5521 5521 { // t,x_1,...,x_n equal to zero 5522 5522 LI=subst(LI,var(j),0); 5523 5523 } 5524 5524 if (size(LI)==0) // the entries of i have not constant part 5525 { 5526 // check now, if the leading ideal of i contains an element 5525 { 5526 // check now, if the leading ideal of i contains an element 5527 5527 // which only depends on t 5528 5528 LI=lead(I); 5529 5529 //size(deletedvariables)=anzahlvariablen(before elimination) 5530 for (j=1;j<=anzahlvariablen-1;j++) 5530 for (j=1;j<=anzahlvariablen-1;j++) 5531 5531 { 5532 5532 LI=subst(LI,var(j),0); 5533 5533 } 5534 if (size(LI)==0) // if no power of t is in lead(i) 5534 if (size(LI)==0) // if no power of t is in lead(i) 5535 5535 { // (where @a is considered as a field element) 5536 // if not yet all variables have been tested, go on with the 5536 // if not yet all variables have been tested, go on with the 5537 5537 // next smaller variable 5538 5538 // else prepare the neccessary information for return … … 5542 5542 } 5543 5543 else 5544 { 5544 { 5545 5545 execute("ring SATURATERING=("+charstr(basering)+"),("+varstr(basering)+"),("+ordstr(basering)+");"); 5546 5546 ideal i=imap(BASERING,i); … … 5553 5553 return(eliminatelist+saturatelist); 5554 5554 } 5555 else // only one solution is searched for, we can do a simplified 5555 else // only one solution is searched for, we can do a simplified 5556 5556 { // version of the above 5557 // check if there is a solution which has the n-th component 5557 // check if there is a solution which has the n-th component 5558 5558 // zero and with positive valuation, 5559 // if so, then eliminate the n-th variable from 5559 // if so, then eliminate the n-th variable from 5560 5560 // sat(i+x_n,t), otherwise leave i as it is; 5561 // then check if the (remaining) ideal has as 5561 // then check if the (remaining) ideal has as 5562 5562 // solution where the n-1st component is zero ..., 5563 5563 // and procede as before; do the same for the remaining variables; 5564 // this way we make sure that the remaining ideal has 5564 // this way we make sure that the remaining ideal has 5565 5565 // a solution which has no component zero; 5566 5566 ideal variablen; // will contain the variables which are not eliminated … … 5570 5570 LI=subst(I,var(nvars(basering)),0); 5571 5571 //size(deletedvariables)=anzahlvariablen-1(before elimination) 5572 for (k=1;k<=size(deletedvariables);k++) 5572 for (k=1;k<=size(deletedvariables);k++) 5573 5573 { 5574 5574 LI=subst(LI,var(k),0); 5575 5575 } 5576 if (size(LI)==0) // if no power of t is in lead(I) 5576 if (size(LI)==0) // if no power of t is in lead(I) 5577 5577 { // (where the X(i) are considered as field elements) 5578 // get rid of var(j) 5578 // get rid of var(j) 5579 5579 i=eliminate(I,var(j)); 5580 5580 deletedvariables[j]=1; 5581 anzahlvariablen--; // if a variable is eliminated, 5581 anzahlvariablen--; // if a variable is eliminated, 5582 5582 // then the number of true variables drops 5583 5583 } … … 5588 5588 } 5589 5589 variablen=invertorder(variablen); 5590 // store also the additional variable and t, 5590 // store also the additional variable and t, 5591 5591 // since they for sure have not been eliminated 5592 5592 for (j=size(deletedvariables)+1;j<=nvars(basering);j++) … … 5594 5594 variablen=variablen+var(j); 5595 5595 } 5596 // if there are variables left, then pass to a ring which 5597 // only realises these variables else we are done 5596 // if there are variables left, then pass to a ring which 5597 // only realises these variables else we are done 5598 5598 if (anzahlvariablen>1) 5599 5599 { … … 5603 5603 { 5604 5604 string elring="ring ELIMINATERING=("+charstr(basering)+"),("+string(variablen)+"),("; 5605 } 5606 if (size(deletedvariables)+1<nvars(basering)) // if @a was present, 5605 } 5606 if (size(deletedvariables)+1<nvars(basering)) // if @a was present, 5607 5607 { // the ordersting needs an additional entry 5608 5608 elring=elring+"dp(1),"; 5609 5609 } 5610 5610 elring=elring+"lp(1));"; 5611 execute(elring); 5611 execute(elring); 5612 5612 ideal i=imap(BASERING,i); 5613 5613 ideal m=imap(BASERING,m); … … 5622 5622 static proc findzerosAndBasictransform (ideal i,intvec w,list zerolist,int findall,list #) 5623 5623 "USAGE: findzerosAndBasictransform(i,w,z,f[,#]); i ideal, w intvec, z list, f int,# an optional list 5624 ASSUME: i is an ideal in Q[t,x_1,...,x_n,@a] and w=(w_0,...,w_n,0) 5624 ASSUME: i is an ideal in Q[t,x_1,...,x_n,@a] and w=(w_0,...,w_n,0) 5625 5625 is in the tropical variety of i; @a need not be present; 5626 5626 the list 'zero' contains the zeros computed in previous recursion steps; 5627 if 'f' is one then all zeros should be found and returned, 5627 if 'f' is one then all zeros should be found and returned, 5628 5628 otherwise only one 5629 RETURN: list, each entry is a ring corresponding to one conjugacy class of 5630 zeros of the t-initial ideal inside the torus; each of the rings 5629 RETURN: list, each entry is a ring corresponding to one conjugacy class of 5630 zeros of the t-initial ideal inside the torus; each of the rings 5631 5631 contains the following objects 5632 5632 ideal i = the ideal i, where the variable @a (if present) has 5633 possibly been transformed according to the new 5634 minimal polynomial, and where itself has been 5635 submitted to the basic transform of the algorithm 5633 possibly been transformed according to the new 5634 minimal polynomial, and where itself has been 5635 submitted to the basic transform of the algorithm 5636 5636 given by the jth zero found for the t-initial ideal; 5637 note that the new minimal polynomial has already 5637 note that the new minimal polynomial has already 5638 5638 been added 5639 poly m = the new minimal polynomial for @a 5639 poly m = the new minimal polynomial for @a 5640 5640 (it is zero if no @a is present) 5641 list zero = zero[k+1] is the kth component of a zero 5641 list zero = zero[k+1] is the kth component of a zero 5642 5642 the t-initial ideal of i 5643 NOTE: - the procedure is called from inside the recursive procedure 5643 NOTE: - the procedure is called from inside the recursive procedure 5644 5644 tropicalparametrise; 5645 if it is called in the first recursion, the list #[1] contains 5646 the t-initial ideal of i w.r.t. w, otherwise #[1] is an integer, 5645 if it is called in the first recursion, the list #[1] contains 5646 the t-initial ideal of i w.r.t. w, otherwise #[1] is an integer, 5647 5647 one more than the number of true variables x_1,...,x_n 5648 - if #[2] is present, then it is an integer which tells whether 5648 - if #[2] is present, then it is an integer which tells whether 5649 5649 ALL zeros should be found or not" 5650 5650 { … … 5664 5664 int anzahlvariablen=#[1]; 5665 5665 // compute the initial ideal of i 5666 // - the last 1 just means that the variable t is the last 5666 // - the last 1 just means that the variable t is the last 5667 5667 // variable in the ring 5668 5668 ideal ini=tInitialIdeal(i,w,1); … … 5672 5672 int recursive=0; 5673 5673 int anzahlvariablen=nvars(basering); 5674 ideal ini=#[1]; // the t-initial ideal has been computed 5674 ideal ini=#[1]; // the t-initial ideal has been computed 5675 5675 // in before and was handed over 5676 } 5676 } 5677 5677 // collect the true variables x_1,...,x_n plus @a, if it is defined in BASERING 5678 5678 ideal variablen; 5679 5679 for (j=1;j<=nvars(basering)-1;j++) 5680 { 5680 { 5681 5681 variablen=variablen+var(j); 5682 5682 } 5683 // move to a polynomial ring with global monomial ordering 5683 // move to a polynomial ring with global monomial ordering 5684 5684 // - the variable t is superflous, 5685 5685 // the variable @a is not if it was already present 5686 5686 execute("ring INITIALRING=("+charstr(basering)+"),("+string(variablen)+"),dp;"); 5687 5687 ideal ini=imap(BASERING,ini); 5688 // compute the minimal associated primes of the 5688 // compute the minimal associated primes of the 5689 5689 // initialideal over the algebraic closure; 5690 // ordering the maximal ideals shall help to 5690 // ordering the maximal ideals shall help to 5691 5691 // avoid unneccessary field extensions 5692 5692 list absminass=absPrimdecGTZ(ini); 5693 def ABSRING=absminass[1]; // the ring in which the minimal 5693 def ABSRING=absminass[1]; // the ring in which the minimal 5694 5694 // associated primes live 5695 5695 setring ABSRING; … … 5704 5704 // check fort the jth maximal ideal a field extension is necessary; 5705 5705 // the latter condition says that @a is not in BASERING; 5706 // if some of the maximal ideals needs a field extension, 5706 // if some of the maximal ideals needs a field extension, 5707 5707 // then everything will live in this ring 5708 5708 if ((maximalideals[j][1]!=0) and (nvars(BASERING)==anzahlvariablen)) 5709 5709 { 5710 // define the extension ring which contains 5710 // define the extension ring which contains 5711 5711 // the new variable @a, if it is not yet present 5712 5712 execute("ring EXTENSIONRING=("+charstr(BASERING)+"),("+string(imap(BASERING,variablen))+",@a,"+tvar+"),(dp("+string(anzahlvariablen-1)+"),dp(1),lp(1));"); 5713 // phi maps x_i to x_i, @a to @a (if present in the ring), 5713 // phi maps x_i to x_i, @a to @a (if present in the ring), 5714 5714 // and the additional variable 5715 // for the field extension is mapped to @a as well 5715 // for the field extension is mapped to @a as well 5716 5716 // -- note that we only apply phi 5717 // to the list a, and in this list no @a is present; 5717 // to the list a, and in this list no @a is present; 5718 5718 // therefore, it does not matter where this is mapped to 5719 5719 map phi=ABSRING,imap(BASERING,variablen),@a; 5720 5720 } 5721 else // @a was already present in the BASERING or no 5721 else // @a was already present in the BASERING or no 5722 5722 { // field extension is necessary 5723 5723 execute("ring EXTENSIONRING=("+charstr(BASERING)+"),("+varstr(BASERING)+"),("+ordstr(BASERING)+");"); 5724 // phi maps x_i to x_i, @a to @a (if present in the ring), 5724 // phi maps x_i to x_i, @a to @a (if present in the ring), 5725 5725 // and the additional variable 5726 // for the field extension is mapped to @a as well respectively to 0, 5726 // for the field extension is mapped to @a as well respectively to 0, 5727 5727 // if no @a is present; 5728 // note that we only apply phi to the list a and to 5728 // note that we only apply phi to the list a and to 5729 5729 // the replacement rule for 5730 // the old variable @a, and in this list resp. 5731 // replacement rule no @a is present; 5730 // the old variable @a, and in this list resp. 5731 // replacement rule no @a is present; 5732 5732 // therefore, it does not matter where this is mapped to; 5733 5733 if (anzahlvariablen<nvars(EXTENSIONRING)) // @a is in EXTENSIONRING 5734 { 5734 { 5735 5735 // additional variable is mapped to @a 5736 map phi=ABSRING,imap(BASERING,variablen),@a; 5736 map phi=ABSRING,imap(BASERING,variablen),@a; 5737 5737 } 5738 5738 else 5739 5739 { 5740 5740 // additional variable is mapped to 0 5741 map phi=ABSRING,imap(BASERING,variablen),0; 5741 map phi=ABSRING,imap(BASERING,variablen),0; 5742 5742 } 5743 5743 } … … 5746 5746 poly m=maximalideals[j][1]; // extract m 5747 5747 list zeroneu=maximalideals[j][2]; // extract the new zero 5748 poly repl=maximalideals[j][3]; // extract the replacement rule 5749 // the list zero may very well exist as an EMPTY global list 5748 poly repl=maximalideals[j][3]; // extract the replacement rule 5749 // the list zero may very well exist as an EMPTY global list 5750 5750 // - in this case we have to remove it 5751 5751 // in order to avoid a redefining warning 5752 if (defined(zero)!=0) 5752 if (defined(zero)!=0) 5753 5753 { 5754 5754 if (size(zero)==0) … … 5761 5761 { 5762 5762 ideal i=imap(BASERING,i); 5763 if (defined(zerolist)==0) // if zerolist is empty, it does not 5763 if (defined(zerolist)==0) // if zerolist is empty, it does not 5764 5764 { // depend on BASERING ! 5765 5765 list zero=imap(BASERING,zerolist); 5766 5766 } 5767 else 5767 else 5768 5768 { 5769 5769 list zero=zerolist; 5770 5770 } 5771 5771 } 5772 else // in BASERING was @a present 5772 else // in BASERING was @a present 5773 5773 { 5774 5774 ideal variablen=imap(BASERING,variablen); 5775 // map i and zerolist to EXTENSIONRING replacing @a 5775 // map i and zerolist to EXTENSIONRING replacing @a 5776 5776 // by the replacement rule repl 5777 5777 map psi=BASERING,variablen[1..size(variablen)-1],repl,var(nvars(basering)); … … 5783 5783 zero[size(zero)+1]=zeroneu; 5784 5784 // do now the basic transformation sending x_l -> t^-w_l*(zero_l+x_l) 5785 for (l=1;l<=anzahlvariablen;l++) 5785 for (l=1;l<=anzahlvariablen;l++) 5786 5786 { 5787 5787 for (k=1;k<=size(i);k++) 5788 5788 { 5789 5789 if (l!=1) // corresponds to x_(l-1) -- note t is the last variable 5790 { 5790 { 5791 5791 i[k]=substitute(i[k],var(l-1),(zeroneu[l]+var(l-1))*t^(-w[l])); 5792 5792 } … … 5800 5800 for (l=1;l<=ncols(i);l++) 5801 5801 { 5802 if (wdegs[l]<0) // if wdegs[l]==0 there is no need to divide, 5802 if (wdegs[l]<0) // if wdegs[l]==0 there is no need to divide, 5803 5803 { // and we made sure that it is no positive 5804 5804 i[l]=i[l]/t^(-wdegs[l]); … … 5806 5806 } 5807 5807 // since we want to consider i now in the ring (Q[@a]/m)[t,x_1,...,x_n] 5808 // we can reduce i modulo m, so that "constant terms" 5808 // we can reduce i modulo m, so that "constant terms" 5809 5809 // which are "zero" since they 5810 5810 // are in m will disappear; simplify(...,2) then really removes them; … … 5813 5813 export(i); 5814 5814 export(m); 5815 export(zero); 5815 export(zero); 5816 5816 extensionringlist[j]=EXTENSIONRING; 5817 5817 kill EXTENSIONRING; … … 5825 5825 static proc ordermaximalideals (list minassi,int anzahlvariablen) 5826 5826 "USAGE: ordermaximalideals(minassi); minassi list 5827 ASSUME: minassi is a list of maximal ideals (together with the information 5828 how many conjugates it has), where the first polynomial is the 5829 minimal polynomial of the last variable in the ring which is 5827 ASSUME: minassi is a list of maximal ideals (together with the information 5828 how many conjugates it has), where the first polynomial is the 5829 minimal polynomial of the last variable in the ring which is 5830 5830 considered as a parameter 5831 RETURN: list, the procedure orders the maximal ideals in minassi according 5832 to how many new variables are needed (namely none or one) to 5833 describe the zeros of the ideal, and accordingly to the 5831 RETURN: list, the procedure orders the maximal ideals in minassi according 5832 to how many new variables are needed (namely none or one) to 5833 describe the zeros of the ideal, and accordingly to the 5834 5834 degree of the corresponding minimal polynomial 5835 5835 l[j][1] = the minimal polynomial for the jth maximal ideal 5836 l[j][2] = list, the k+1st entry is the kth coordinate of the 5837 zero described by the maximal ideal in terms 5836 l[j][2] = list, the k+1st entry is the kth coordinate of the 5837 zero described by the maximal ideal in terms 5838 5838 of the last variable 5839 l[j][3] = poly, the replacement for the old variable @a 5839 l[j][3] = poly, the replacement for the old variable @a 5840 5840 NOTE: if a maximal ideal contains a variable, it is removed from the list; 5841 5841 the procedure is called by findzerosAndBasictransform" … … 5844 5844 int pruefer; // is set one if a maximal ideal contains a variable 5845 5845 list minassisort; // will contain the output 5846 for (j=1;j<=size(minassi);j++){minassisort[j]=0;} // initialise minassisort 5846 for (j=1;j<=size(minassi);j++){minassisort[j]=0;} // initialise minassisort 5847 5847 // to fix its initial length 5848 5848 list zwischen; // needed for reordering 5849 list zero; // (a_1,...,a_n)=(zero[2],...,zero[n+1]) will be 5849 list zero; // (a_1,...,a_n)=(zero[2],...,zero[n+1]) will be 5850 5850 // a common zero of the ideal m 5851 5851 poly nf; // normalform of a variable w.r.t. m 5852 poly minimalpolynomial; // minimal polynomial for the field extension 5852 poly minimalpolynomial; // minimal polynomial for the field extension 5853 5853 poly parrep; // the old variable @a possibly has to be replaced by a new one 5854 // compute for each maximal ideal the number of new variables, which are 5855 // needed to describe its zeros -- note, a new variable is needed 5854 // compute for each maximal ideal the number of new variables, which are 5855 // needed to describe its zeros -- note, a new variable is needed 5856 5856 // if the first entry of minassi[j][1] is not the last variable 5857 // store the value a variable reduces to in the list a; 5857 // store the value a variable reduces to in the list a; 5858 5858 for (j=size(minassi);j>=1;j--) 5859 5859 { … … 5863 5863 minimalpolynomial=0; 5864 5864 } 5865 zero[1]=poly(0); // the first entry in zero and in 5865 zero[1]=poly(0); // the first entry in zero and in 5866 5866 // neuevariablen corresponds to the variable t, 5867 5867 minassi[j][1]=std(minassi[j][1]); … … 5869 5869 { 5870 5870 // zero_k+1 is the normal form of the kth variable modulo m 5871 zero[k+1]=reduce(var(k),minassi[j][1]); 5872 // if a variable reduces to zero, then the maximal 5871 zero[k+1]=reduce(var(k),minassi[j][1]); 5872 // if a variable reduces to zero, then the maximal 5873 5873 // ideal contains a variable and we can delete it 5874 5874 if (zero[k+1]==0) … … 5877 5877 } 5878 5878 } 5879 // if anzahlvariablen<nvars(basering), then the old ring 5879 // if anzahlvariablen<nvars(basering), then the old ring 5880 5880 // had already an additional variable; 5881 5881 // the old parameter @a then has to be replaced by parrep … … 5886 5886 // if the maximal ideal contains a variable, we simply delete it 5887 5887 if (pruefer==0) 5888 { 5888 { 5889 5889 minassisort[j]=list(minimalpolynomial,zero,parrep); 5890 5890 } 5891 // otherwise we store the information on a, neuevariablen 5891 // otherwise we store the information on a, neuevariablen 5892 5892 // and neuvar together with the ideal 5893 5893 else … … 5898 5898 } 5899 5899 } 5900 // sort the maximal ideals ascendingly according to the 5900 // sort the maximal ideals ascendingly according to the 5901 5901 // number of new variables needed to 5902 5902 // express the zero of the maximal ideal … … 5905 5905 l=j; 5906 5906 for (k=j-1;k>=1;k--) 5907 { 5907 { 5908 5908 if (deg(minassisort[l][1])<deg(minassisort[k][1])) 5909 5909 { … … 5940 5940 static proc verticesTropicalCurve (def tp,list #) 5941 5941 "USAGE: verticesTropicalCurve(tp[,#]); tp list, # optional list 5942 ASSUME: tp is represents an ideal in Z[x,y] representing a tropical 5942 ASSUME: tp is represents an ideal in Z[x,y] representing a tropical 5943 5943 polynomial (in the form of the output of the procedure tropicalise) 5944 5944 defining a tropical plane curve 5945 RETURN: list, each entry corresponds to a vertex in the tropical plane 5945 RETURN: list, each entry corresponds to a vertex in the tropical plane 5946 5946 curve defined by tp 5947 5947 l[i][1] = x-coordinate of the ith vertex 5948 5948 l[i][2] = y-coordinate of the ith vertex 5949 l[i][3] = a polynomial whose monimials mark the vertices in 5950 the Newton polygon corresponding to the entries in 5949 l[i][3] = a polynomial whose monimials mark the vertices in 5950 the Newton polygon corresponding to the entries in 5951 5951 tp which take the common minimum at the ith vertex 5952 5952 NOTE: - the information in l[i][3] represents the subdivision of the Newton 5953 polygon of tp (respectively a polynomial which defines tp); 5954 - if # is non-empty and #[1] is the string 'max', then in the 5955 computations minimum and maximum are exchanged; 5956 - if # is non-empty and the #[1] is not a string, only the vertices 5953 polygon of tp (respectively a polynomial which defines tp); 5954 - if # is non-empty and #[1] is the string 'max', then in the 5955 computations minimum and maximum are exchanged; 5956 - if # is non-empty and the #[1] is not a string, only the vertices 5957 5957 will be computed and the information on the Newton subdivision will 5958 5958 be omitted; 5959 - here the tropical polynomial is supposed to be the MINIMUM of the 5960 linear forms in tp, unless the optional input #[1] is the 5959 - here the tropical polynomial is supposed to be the MINIMUM of the 5960 linear forms in tp, unless the optional input #[1] is the 5961 5961 string 'max' 5962 - the procedure is called from tropicalCurve and from 5962 - the procedure is called from tropicalCurve and from 5963 5963 conicWithTangents" 5964 5964 { 5965 // if you insert a single polynomial instead of an ideal representing 5965 // if you insert a single polynomial instead of an ideal representing 5966 5966 // a tropicalised polynomial, 5967 // then we compute first the tropicalisation of this polynomial 5967 // then we compute first the tropicalisation of this polynomial 5968 5968 // -- this feature is not documented in the above help string 5969 5969 if (typeof(tp)=="poly") … … 5974 5974 } 5975 5975 int i,j,k,l,z; // indices 5976 // make sure that no constant entry of tp has type int since that 5976 // make sure that no constant entry of tp has type int since that 5977 5977 // would lead to trouble 5978 5978 // when using the procedure substitute … … 5992 5992 int e=1; 5993 5993 option(redSB); 5994 // for each triple (i,j,k) of entries in tp check if they have a 5995 // point in common and if they attain at this point the minimal 5994 // for each triple (i,j,k) of entries in tp check if they have a 5995 // point in common and if they attain at this point the minimal 5996 5996 // possible value for all linear forms in tp 5997 5997 for (i=1;i<=size(tp)-2;i++) … … 6046 6046 e++; 6047 6047 } 6048 } 6048 } 6049 6049 } 6050 6050 } … … 6069 6069 static proc bunchOfLines (def tp,list #) 6070 6070 "USAGE: bunchOfLines(tp[,#]); tp list, # optional list 6071 ASSUME: tp is represents an ideal in Q[x,y] representing a tropical 6071 ASSUME: tp is represents an ideal in Q[x,y] representing a tropical 6072 6072 polynomial (in the form of the output of the procedure tropicalise) 6073 6073 defining a bunch of ordinary lines in the plane, 6074 6074 i.e. the Newton polygone is a line segment 6075 RETURN: list, see the procedure tropicalCurve for an explanation of 6075 RETURN: list, see the procedure tropicalCurve for an explanation of 6076 6076 the syntax of this list 6077 NOTE: - the tropical curve defined by tp will consist of a bunch of 6078 parallel lines and throughout the procedure a list with the 6079 name bunchoflines is computed, which represents these lines and 6077 NOTE: - the tropical curve defined by tp will consist of a bunch of 6078 parallel lines and throughout the procedure a list with the 6079 name bunchoflines is computed, which represents these lines and 6080 6080 has the following interpretation: 6081 list, each entry corresponds to a vertex in the tropical plane 6081 list, each entry corresponds to a vertex in the tropical plane 6082 6082 curve defined by tp 6083 6083 l[i][1] = the equation of the ith line in the tropical curve 6084 l[i][2] = a polynomial whose monimials mark the vertices in 6085 the Newton polygon corresponding to the entries in 6084 l[i][2] = a polynomial whose monimials mark the vertices in 6085 the Newton polygon corresponding to the entries in 6086 6086 tp which take the common minimum at the ith vertex 6087 6087 - the information in l[i][2] represents the subdivision of the Newton 6088 polygon of tp (respectively a polynomial which defines tp); 6089 - if # is non-empty and #[1] is the string 'max', then in the 6090 computations minimum and maximum are exchanged; 6091 - if # is non-empty and the #[1] is not a string, only the vertices 6092 will be computed and the information on the Newton subdivision 6088 polygon of tp (respectively a polynomial which defines tp); 6089 - if # is non-empty and #[1] is the string 'max', then in the 6090 computations minimum and maximum are exchanged; 6091 - if # is non-empty and the #[1] is not a string, only the vertices 6092 will be computed and the information on the Newton subdivision 6093 6093 will be omitted; 6094 - here the tropical polynomial is supposed to be the MINIMUM of the 6095 linear forms in tp, unless the optional input #[1] is the 6094 - here the tropical polynomial is supposed to be the MINIMUM of the 6095 linear forms in tp, unless the optional input #[1] is the 6096 6096 string 'max' 6097 6097 - the procedure is called from tropicalCurve" … … 6110 6110 intvec direction=leadexp(detropicalise(tp[1]))-leadexp(detropicalise(tp[2])); 6111 6111 direction=direction/gcd(direction[1],direction[2]); 6112 // change the coordinates in such a way, that the Newton polygon 6112 // change the coordinates in such a way, that the Newton polygon 6113 6113 // lies on the x-axis 6114 if (direction[1]==0) // there is no x-term - exchange x and y 6114 if (direction[1]==0) // there is no x-term - exchange x and y 6115 6115 { // and get rid of the new y part 6116 6116 for (i=1;i<=size(tp);i++) … … 6126 6126 } 6127 6127 } 6128 // For all tuples (i,j) of entries in tp check if they attain 6128 // For all tuples (i,j) of entries in tp check if they attain 6129 6129 // at their point of intersection 6130 6130 // the minimal possible value for all linear forms in tp … … 6142 6142 { 6143 6143 vergleich=substitute(tp[l],var(1),px); 6144 if (vergleich==wert) 6144 if (vergleich==wert) 6145 6145 { 6146 6146 newton=newton+detropicalise(oldtp[l]); … … 6153 6153 e++; 6154 6154 } 6155 } 6155 } 6156 6156 } 6157 6157 // if a vertex appears several times, only its first occurence will be kept … … 6160 6160 for (j=i-1;j>=1;j--) 6161 6161 { 6162 if (bunchoflines[i][1]==bunchoflines[j][1]) 6162 if (bunchoflines[i][1]==bunchoflines[j][1]) 6163 6163 { 6164 6164 bunchoflines=delete(bunchoflines,i); …