# Changeset 3360fb in git

Ignore:
Timestamp:
Apr 14, 2009, 2:00:15 PM (14 years ago)
Branches:
(u'jengelh-datetime', 'ceac47cbc86fe4a15902392bdbb9bd2ae0ea02c6')(u'spielwiese', 'a800fe4b3e9d37a38c5a10cc0ae9dfa0c15a4ee6')
Children:
Parents:
2c3a5db391a25c28449b80c5f27e1dd77ed2c30f
Message:
*hannes: format

git-svn-id: file:///usr/local/Singular/svn/trunk@11695 2c84dea3-7e68-4137-9b89-c4e89433aadc
Location:
Singular/LIB
Files:
18 edited

Unmodified
Removed
• ## Singular/LIB/algebra.lib

 r2c3a5d //new proc  nonZeroEntry(id), used to fix a bug in proc finitenessTest /////////////////////////////////////////////////////////////////////////////// version="$Id: algebra.lib,v 1.21 2009-04-07 16:18:05 seelisch Exp$"; version="$Id: algebra.lib,v 1.22 2009-04-14 12:00:13 Singular Exp$"; category="Commutative Algebra"; info=" NOTE:    the proc algebra_containment tests the same using a different algorithm, which is often faster if l[1] == 0 then l[2] may contain more than one relation h(y(0),y(1),...,y(k)), if l[1] == 0 then l[2] may contain more than one relation h(y(0),y(1),...,y(k)), separated by comma EXAMPLE: example inSubring; shows an example } if (deg(ker[i]/y(0))>0) { if( l[2] != "" ){ l[2] = l[2] + ","; } { if( l[2] != "" ){ l[2] = l[2] + ","; } l[2] = l[2] + string(ker[i]); }
• ## Singular/LIB/bfun.lib

 r2c3a5d ////////////////////////////////////////////////////////////////////////////// version="$Id: bfun.lib,v 1.7 2009-04-08 16:51:07 seelisch Exp$"; version="$Id: bfun.lib,v 1.8 2009-04-14 12:00:13 Singular Exp$"; category="Noncommutative"; info=" @*      one is interested in the global b-function (also known as Bernstein-Sato @*      polynomial) b(s) in K[s], defined to be the non-zero monic polynomial of minimal @*      degree, satisfying a functional identity L * F^{s+1} = b(s) F^s, @*      degree, satisfying a functional identity L * F^{s+1} = b(s) F^s, @*      for some operator L in D[s] (* stands for the action of differential operator) @*      By D one denotes the n-th Weyl algebra @*   There is a constructive definition of a b-function of a holonomic ideal I in D @*   (that is, an ideal I in a Weyl algebra D, such that D/I is holonomic module) @*   with respect to the given weight vector w: For a poly p in D, its initial @*   form w.r.t. (-w,w) is defined as the sum of all terms of p which have @*   with respect to the given weight vector w: For a poly p in D, its initial @*   form w.r.t. (-w,w) is defined as the sum of all terms of p which have @*   maximal weighted total degree where the weight of x_i is -w_i and the weight @*   of d_i is w_i. Let J be the initial ideal of I w.r.t. (-w,w), i.e. the @*   of d_i is w_i. Let J be the initial ideal of I w.r.t. (-w,w), i.e. the @*   K-vector space generated by all initial forms w.r.t (-w,w) of elements of I. @*   Put s = w_1 x_1 d_1 + ... + w_n x_n d_n. Then the monic generator b_w(s) of @*   the intersection of J with the PID K[s] is called the b-function of I w.r.t.  w. @*   the intersection of J with the PID K[s] is called the b-function of I w.r.t.  w. @*   Unlike Bernstein-Sato polynomial, general b-function with respect to @*   arbitrary weights need not have rational roots at all. However, b-function @*  of a holonomic ideal is known to be non-zero as well. @* @*      References: [SST] Saito, Sturmfels, Takayama: Groebner Deformations of @* @*      References: [SST] Saito, Sturmfels, Takayama: Groebner Deformations of @*      Hypergeometric Differential Equations (2000), @*      Noro: An Efficient Modular Algorithm for Computing the Global b-function, pIntersect(f,I[,s]);      intersection of ideal with subalgebra K[f] for a poly f pIntersectSyz(f,I[,p,s,t]); intersection of ideal with subalgebra K[f] with syz-solver linReduce(f,I[,s]);         reduce a poly by linear reductions wrt ideal linReduce(f,I[,s]);         reduce a poly by linear reductions wrt ideal linReduceIdeal(I,[s,t]);  interreduce generators of ideal by linear reductions linSyzSolve(I[,s]);         compute a linear dependency of elements of ideal I AUXILIARY PROCEDURES: allPositive(v);  checks whether all entries of an intvec are positive allPositive(v);  checks whether all entries of an intvec are positive scalarProd(v,w); computes the standard scalar product of two intvecs vec2poly(v[,i]); constructs an univariate poly with given coefficients EXAMPLE: example gradedWeyl; shows examples NOTE:    u[i] is the weight of x(i), v[i] the weight of D(i). @*       u+v has to be a non-negative intvec. @*       u+v has to be a non-negative intvec. " { { ERROR("weight vectors have wrong dimension"); } } intvec uv,gr; uv = u+v; for (i=1; i<=n; i++) { if (gr[i] == 1) if (gr[i] == 1) { l2[n+i] = "xi("+string(i)+")"; for (i=1; i<=ncols(I); i++) { M[i] = gen(i);  } } } } dbprint(ppl-1,"// initially sorted ideal:", I); if (remembercoeffs <> 0) { dbprint(ppl-1,"// used permutations:", M); } lmJ = insertGenerator(lmJ,lm,j); ordJ = insertGenerator(ordJ,poly(ordlm),j); if (remembercoeffs <> 0) if (remembercoeffs <> 0) { v = M[i]; { if (ordJ[i] == ord(J[j][k])) { { if (lm == normalize(J[j][k])) { RETURN:  poly or list, linear reductum (over field) of f by elements from I PURPOSE: reduce a poly only by linear reductions (no monomial multiplications) NOTE:    If s<>0, a list consisting of the reduced poly and the coefficient NOTE:    If s<>0, a list consisting of the reduced poly and the coefficient @*       vector of the used reductions is returned, otherwise (and by default) @*       only reduced poly is returned. @*       If t<>0 (and by default) all monomials are reduced (if possible), @*       otherwise, only leading monomials are reduced. @*       If u<>0 (and by default), the ideal is linearly pre-reduced, i.e. @*       If u<>0 (and by default), the ideal is linearly pre-reduced, i.e. @*       instead of the given ideal, the output of @code{linReduceIdeal} is used. @*       If u is set to 0 and the given ideal does not equal the output of f = x3+y2+x2+y+x; I = x3-y3, y3-x2,x3-y2,x2-y,y2-x; list l = linReduce(f,I,1); list l = linReduce(f,I,1); l; module M = I; proc pIntersect (poly s, ideal I, list #) "USAGE:  pIntersect(f, I [,s]);  f a poly, I an ideal, s an optional int RETURN:  vector, coefficient vector of the monic polynomial RETURN:  vector, coefficient vector of the monic polynomial PURPOSE: compute the intersection of ideal I with the subalgebra K[f] ASSUME:  I is given as Groebner basis, basering is not a qring. print("// Try a bound of at least " + string(degbound)); return(vector(0)); } } dbprint(ppl,"// lower bound for the degree of the insection is " +string(degbound)); if (degbound == 0) // lm(s) does not appear in lm(I) v = v + m[j,1]*gen(j); } setring save; setring save; v = imap(@R,v); kill @R; NOTE:    If the intersection is zero, this procedure might not terminate. @*       If p>0 is given, this proc computes the generator of the intersection in @*       char p first and then only searches for a generator of the obtained @*       degree in the basering. Otherwise, it searches for all degrees by @*       char p first and then only searches for a generator of the obtained @*       degree in the basering. Otherwise, it searches for all degrees by @*       computing syzygies. @*       If s<>0, @code{std} is used for Groebner basis computations in char 0, @*       otherwise, and by default, @code{slimgb} is used. @*       If t<>0 and by default, @code{std} is used for Groebner basis @*       If t<>0 and by default, @code{std} is used for Groebner basis @*       computations in char >0, otherwise, @code{slimgb} is used. DISPLAY: If printlevel=1, progress debug messages will be printed, } dbprint(ppl,"// pIntersectSyz finished"); if (solveincharp) { short = shortSave; } if (solveincharp) { short = shortSave; } return(v); } { return(list(ideal(0),intvec(0))); } } if (inorann == 0) // bfct using initial ideal { RETURN:  list of ideal and intvec PURPOSE: computes the roots of the Bernstein-Sato polynomial b(s) @*       for the hypersurface defined by f. @*       for the hypersurface defined by f. ASSUME:  The basering is commutative and of characteristic 0. BACKGROUND: In this proc, the initial Malgrange ideal is computed according to @*       the algorithm by Masayuki Noro and then a system of linear equations is @*       solved by linear reductions. NOTE:    In the output list, the ideal contains all the roots NOTE:    In the output list, the ideal contains all the roots @*       and the intvec their multiplicities. @*       If s<>0, @code{std} is used for GB computations, @*       otherwise, and by default, @code{slimgb} is used. @*       otherwise, and by default, @code{slimgb} is used. @*       If t<>0, a matrix ordering is used for Groebner basis computations, @*       otherwise, and by default, a block ordering is used. @*       the algorithm by Masayuki Noro and then a system of linear equations is @*       solved by computing syzygies. NOTE:    In the output list, the ideal contains all the roots and the intvec NOTE:    In the output list, the ideal contains all the roots and the intvec @*       their multiplicities. @*       If r<>0, @code{std} is used for GB computations in characteristic 0, ASSUME:  The basering is the n-th Weyl algebra in characteristic 0 and for all @*       1<=i<=n the identity var(i+n)*var(i)=var(i)*var(i+1)+1 holds, i.e. the @*       sequence of variables is given by x(1),...,x(n),D(1),...,D(n), @*       sequence of variables is given by x(1),...,x(n),D(1),...,D(n), @*       where D(i) is the differential operator belonging to x(i). @*       Further we assume that I is holonomic. @*  L[3] is 1 (for nonzero constant) or 0 (for zero b-function). @*       If s<>0, @code{std} is used for GB computations in characteristic 0, @*       otherwise, and by default, @code{slimgb} is used. @*       otherwise, and by default, @code{slimgb} is used. @*       If t<>0, a matrix ordering is used for GB computations, otherwise, @*       and by default, a block ordering is used. @*       their multiplicities. @*       If s<>0, @code{std} is used for the GB computation, otherwise, @*       and by default, @code{slimgb} is used. @*       and by default, @code{slimgb} is used. @*       If t<>0, a matrix ordering is used for GB computations, @*       otherwise, and by default, a block ordering is used. def save = basering; int n = nvars(save); if (char(save) <> 0) if (char(save) <> 0) { ERROR("characteristic of basering has to be 0"); // create names for vars list Lvar; Lvar[1]   = safeVarName("t"); Lvar[1]   = safeVarName("t"); Lvar[2]   = safeVarName("s"); Lvar[n+3] = safeVarName("D"+Lvar[1]); intvec @a = 1:N; @a[2] = 2; intvec @a2 = @a; @a2[2] = 0; @a2[2*n+4] = 0; list Lord; list Lord; Lord[1] = list("a",@a); Lord[2] = list("a",@a2); if (methodord == 0) // default: block ordering @*       their multiplicities. @*       If r<>0, @code{std} is used for GB computations, @*       otherwise, and by default, @code{slimgb} is used. @*       otherwise, and by default, @code{slimgb} is used. DISPLAY: If printlevel=1, progress debug messages will be printed, @*       if printlevel>=2, all the debug messages will be printed.
• ## Singular/LIB/crypto.lib

 r2c3a5d //GP, last modified 28.6.06 /////////////////////////////////////////////////////////////////////////////// version="$Id: crypto.lib,v 1.7 2009-04-06 12:39:02 seelisch Exp$"; version="$Id: crypto.lib,v 1.8 2009-04-14 12:00:14 Singular Exp$"; category="Teaching"; info=" "USAGE:  generateG(a,b,m); RETURN: m-th division polynomial NOTE: generate the so-called division polynomials, i.e., the recursively defined NOTE: generate the so-called division polynomials, i.e., the recursively defined polynomials p_m=generateG(a,b,m) in Z[x, y] such that, for a point (x:y:1) on the elliptic curve defined by y^2=x^3+a*x+b  over Z/N the point@*
• ## Singular/LIB/decodegb.lib

 r2c3a5d /////////////////////////////////////////////////////////////////////////////// version="$Id: decodegb.lib,v 1.13 2009-04-10 15:18:18 Singular Exp$"; version="$Id: decodegb.lib,v 1.14 2009-04-14 12:00:14 Singular Exp$"; category="Coding theory"; info=" "USAGE:    decodeRandomFL(redun,p,e,n,t,ncodes,ntrials,minpol); @format - n is length of codes generated, - n is length of codes generated, - redun = redundancy of codes generated, - p is the characteristic,
• ## Singular/LIB/dmod.lib

 r2c3a5d ////////////////////////////////////////////////////////////////////////////// version="$Id: dmod.lib,v 1.39 2009-04-09 12:04:41 seelisch Exp$"; version="$Id: dmod.lib,v 1.40 2009-04-14 12:00:14 Singular Exp$"; category="Noncommutative"; info=" @*             Jorge Martin Morales,    jorge@unizar.es THEORY: Let K be a field of characteristic 0. Given a polynomial ring THEORY: Let K be a field of characteristic 0. Given a polynomial ring @*      R = K[x_1,...,x_n] and a polynomial F in R, @*      one is interested in the R[1/F]-module of rank one, generated by @*      one is interested in the R[1/F]-module of rank one, generated by @*      the symbol F^s for a symbolic discrete variable s. @* In fact, the module R[1/F]*F^s has a structure of a D(R)[s]-module, where D(R) @* One is interested in the following data: @* - Ann F^s = I = I(F^s) in D(R)[s], denoted by LD in the output @* - global Bernstein polynomial in K[s], denoted by bs, @* - global Bernstein polynomial in K[s], denoted by bs, @* - its minimal integer root s0, the list of all roots of bs, which are known @*   to be rational, with their multiplicities, which is denoted by BS @* - Ann F^s0 = I(F^s0) in D(R), denoted by LD0 in the output @* - Ann F^s0 = I(F^s0) in D(R), denoted by LD0 in the output @*   (LD0 is a holonomic ideal in D(R)) @* - Ann^(1) F^s in D(R)[s], denoted by LD1 (logarithmic derivations) @*     PS*F^(s+1) = bs*F^s holds in K[x_1,...,x_n,1/F]*F^s. REFERENCES: REFERENCES: @* We provide the following implementations of algorithms: @* (OT) the classical Ann F^s algorithm from Oaku and Takayama (Journal of @* (OT) the classical Ann F^s algorithm from Oaku and Takayama (Journal of @* Pure and Applied Math., 1999), @* (LOT) Levandovskyy's modification of the Oaku-Takayama algorithm (ISSAC 2007) @*        l'ideal de Bernstein associe a des polynomes, preprint, 2002) @* (LM08) V. Levandovskyy and J. Martin-Morales, ISSAC 2008 @* (C) Countinho, A Primer of Algebraic D-Modules, @* (SST) Saito, Sturmfels, Takayama 'Groebner Deformations of Hypergeometric @* (C) Countinho, A Primer of Algebraic D-Modules, @* (SST) Saito, Sturmfels, Takayama 'Groebner Deformations of Hypergeometric @*         Differential Equations', Springer, 2000 "USAGE:  annfs(f [,S,eng]);  f a poly, S a string, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s with the algorithm PURPOSE: compute the D-module structure of basering[1/f]*f^s with the algorithm @*  given in S and with the Groebner basis engine given in ''eng'' NOTE:  activate the output ring with the @code{setring} command. "USAGE:  Sannfs(f [,S,eng]);  f a poly, S a string, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[f^s] with the algorithm PURPOSE: compute the D-module structure of basering[f^s] with the algorithm @*  given in S and with the Groebner basis engine given in eng NOTE:    activate the output ring with the @code{setring} command. PURPOSE: compute the D-module structure of basering[1/f]*f^s NOTE:    activate the output ring with the @code{setring} command. @*   In the output ring D[s], the ideal LD1 is generated by the elements @*   In the output ring D[s], the ideal LD1 is generated by the elements @*   in Ann F^s in D[s], coming from logarithmic derivations. @*       If eng <>0, @code{std} is used for Groebner basis computations, "USAGE:  ALTannfsBM(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the annihilator ideal of f^s in D[s], where D is the Weyl PURPOSE: compute the annihilator ideal of f^s in D[s], where D is the Weyl @*   algebra, according to the algorithm by Briancon and Maisonobe NOTE:  activate the output ring with the @code{setring} command. In this ring, "USAGE:  bernsteinBM(f [,eng]);  f a poly, eng an optional int RETURN:  list (of roots of the Bernstein polynomial b and their multiplicies) PURPOSE: compute the global Bernstein-Sato polynomial for a hypersurface, PURPOSE: compute the global Bernstein-Sato polynomial for a hypersurface, @* defined by f, according to the algorithm by Briancon and Maisonobe NOTE:    If eng <>0, @code{std} is used for Groebner basis computations, "USAGE:  annfs2(I, F [,eng]);  I an ideal, F a poly, eng an optional int RETURN:  ring PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, @*       based on the output of Sannfs-like procedure @*       annfs2 uses shorter expressions in the variable s (the idea of Noro). "USAGE:  annfsRB(I, F [,eng]);  I an ideal, F a poly, eng an optional int RETURN:  ring PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, @* based on the output of Sannfs like procedure NOTE:    activate the output ring with the @code{setring} command. In this ring, "USAGE:  operatorBM(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the B-operator and other relevant data for Ann F^s, PURPOSE: compute the B-operator and other relevant data for Ann F^s, @*  using e.g. algorithm by Briancon and Maisonobe for Ann F^s and BS. NOTE:    activate the output ring with the @code{setring} command. In the output ring D[s] "USAGE:  annfsBMI(F [,eng]);  F an ideal, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s where PURPOSE: compute the D-module structure of basering[1/f]*f^s where @* f = F[1]*..*F[P], according to the algorithm by Briancon and Maisonobe. NOTE:    activate the output ring with the @code{setring} command. In this ring, "USAGE:  annfsOT(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s, PURPOSE: compute the D-module structure of basering[1/f]*f^s, @* according to the algorithm by Oaku and Takayama NOTE:    activate the output ring with the @code{setring} command. In this ring, "USAGE:  SannfsOT(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the @* 1st step of the algorithm by Oaku and Takayama in the ring D[s] NOTE:    activate the output ring with the @code{setring} command. @*  In the output ring D[s], the ideal LD (which is NOT a Groebner basis) @*  In the output ring D[s], the ideal LD (which is NOT a Groebner basis) @*  is the needed D-module structure. @*  If eng <>0, @code{std} is used for Groebner basis computations, "USAGE:  SannfsBM(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the @* 1st step of the algorithm by Briancon and Maisonobe in the ring D[s]. NOTE:  activate the output ring with the @code{setring} command. @*   In the output ring D[s], the ideal LD (which is NOT a Groebner basis) is @*   In the output ring D[s], the ideal LD (which is NOT a Groebner basis) is @*   the needed D-module structure. @*   If eng <>0, @code{std} is used for Groebner basis computations, PURPOSE: compute Ann f^s and Groebner basis of Ann f^s+f in D[s] NOTE:    activate the output ring with the @code{setring} command. @*  This procedure, unlike SannfsBM, returns a ring with the degrevlex @*  This procedure, unlike SannfsBM, returns a ring with the degrevlex @*  ordering in all variables. @*  In the ring D[s], the ideal LD is the ideal needed (which is returned as a Groebner basis). PURPOSE: compute Ann f^s and Groebner basis of Ann f^s+f in D[s] NOTE:    activate the output ring with the @code{setring} command. @*    This procedure, unlike SannfsBM, returns a ring with the degrevlex @*    This procedure, unlike SannfsBM, returns a ring with the degrevlex @*    ordering in all variables. @*    In the ring D[s], the ideal LD (which IS a Groebner basis) is the needed ideal. " { // DEBUG INFO: ordering on the output ring = dp, // DEBUG INFO: ordering on the output ring = dp, // use std(K,F); for reusing the std property of K "USAGE:  SannfsLOT(f [,eng]);  f a poly, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to the @* Levandovskyy's modification of the algorithm by Oaku and Takayama in D[s] NOTE:    activate the output ring with the @code{setring} command. @*    In the ring D[s], the ideal LD (which is NOT a Groebner basis) is @*    In the ring D[s], the ideal LD (which is NOT a Groebner basis) is @*    the needed D-module structure. @*    If eng <>0, @code{std} is used for Groebner basis computations, "USAGE:  annfsLOT(F [,eng]);  F a poly, eng an optional int RETURN:  ring PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to PURPOSE: compute the D-module structure of basering[1/f]*f^s, according to @* the Levandovskyy's modification of the algorithm by Oaku and Takayama NOTE:    activate the output ring with the @code{setring} command. In this ring, "USAGE:  annfs0(I, F [,eng]);  I an ideal, F a poly, eng an optional int RETURN:  ring PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, based PURPOSE: compute the annihilator ideal of f^s in the Weyl Algebra, based @* on the output of Sannfs-like procedure NOTE:    activate the output ring with the @code{setring} command. In this ring, "USAGE:  annfspecial(I,F,mir,n);  I an ideal, F a poly, int mir, number n RETURN:  ideal PURPOSE: compute the annihilator ideal of F^n in the Weyl Algebra PURPOSE: compute the annihilator ideal of F^n in the Weyl Algebra @*           for the given rational number n ASSUME:  The basering is D[s] and contains 's' explicitly as a variable, @*   the integer 'mir' is the minimal integer root of the BS polynomial of F, @*   and the number n is rational. NOTE: We compute the real annihilator for any rational value of n (both @*       generic and exceptional). The implementation goes along the lines of @*       the Algorithm 5.3.15 from Saito-Sturmfels-Takayama. NOTE: We compute the real annihilator for any rational value of n (both @*       generic and exceptional). The implementation goes along the lines of @*       the Algorithm 5.3.15 from Saito-Sturmfels-Takayama. DISPLAY: If printlevel=1, progress debug messages will be printed, @*       if printlevel>=2, all the debug messages will be printed. RETURN:  int ASSUME: Basering is a commutative ring, alpha is a rational number. PURPOSE: check whether a rational number alpha is a root of the global PURPOSE: check whether a rational number alpha is a root of the global @* Bernstein-Sato polynomial of f and compute its multiplicity, @* with the algorithm given by S and with the Groebner basis engine given by eng. NOTE:  The annihilator of f^s in D[s] is needed and hence it is computed with the NOTE:  The annihilator of f^s in D[s] is needed and hence it is computed with the @*       algorithm by Briancon and Maisonobe. The value of a string S can be @*       'alg1' (default) - for the algorithm 1 of [LM08] proc checkRoot2 (ideal I, poly F, number a, list #) "USAGE:  checkRoot2(I,f,a [,eng]);  I an ideal, f a poly, alpha a number, eng an optional int ASSUME:  I is the annihilator of f^s in D[s], basering is D[s], ASSUME:  I is the annihilator of f^s in D[s], basering is D[s], @* that is basering and I are the output os Sannfs-like procedure, @* f is a polynomial in K[_x] and alpha is a rational number. RETURN:  int, the multiplicity of -alpha as a root of the BS polynomial of f. RETURN:  int, the multiplicity of -alpha as a root of the BS polynomial of f. PURPOSE: check whether a rational number alpha is a root of the global Bernstein- @* Sato polynomial of f and compute its multiplicity from the known Ann F^s in D[s] { // to check: alpha is rational (has char 0 check inside) if (!isRational(a)) ASSUME:  checkFactor is called from the basering, created by Sannfs-like proc, @* that is, from the Weyl algebra in x1,..,xN,d1,..,dN tensored with K[s]. @* The ideal I is the annihilator of f^s in D[s], that is the ideal, computed @* The ideal I is the annihilator of f^s in D[s], that is the ideal, computed @* by Sannfs-like procedure (usually called LD there). @* Moreover, f is a polynomial in K[x1,..,xN] and qs is a polynomial in K[s]. RETURN:  int, 1 if qs is a factor of the global Bernstein polynomial of f and 0 otherwise PURPOSE: check whether a univariate polynomial qs is a factor of the PURPOSE: check whether a univariate polynomial qs is a factor of the @*  Bernstein-Sato polynomial of f without explicit knowledge of the latter. NOTE:    If eng <>0, @code{std} is used for Groebner basis computations, "USAGE:  indAR(L,n);  list L, int n RETURN:  list PURPOSE: computes arrangement inductively, using L and PURPOSE: computes arrangement inductively, using L and @* var(n) as the next variable ASSUME: L has a structure of an arrangement proc isRational(number n) "USAGE:  isRational(n); n number "USAGE:  isRational(n); n number RETURN:  int PURPOSE: determine whether n is a rational number,
• ## Singular/LIB/elim.lib

 r2c3a5d // $Id: elim.lib,v 1.29 2009-04-07 16:18:05 seelisch Exp$ // $Id: elim.lib,v 1.30 2009-04-14 12:00:14 Singular Exp$ // (GMG, modified 22.06.96) // GMG, last modified 30.10.08: new procedure elimRing; // and can now choose as method slimgb or std. /////////////////////////////////////////////////////////////////////////////// version="$Id: elim.lib,v 1.29 2009-04-07 16:18:05 seelisch Exp$"; version="$Id: elim.lib,v 1.30 2009-04-14 12:00:14 Singular Exp$"; category="Commutative Algebra"; info=" //------------------ set resp. compute ring weights ---------------------- int ii; intvec @w;              //to store weights of all variables @w[nvarBR] = 0; @w = @w + 1;            //initialize @w as 1..1 intvec @w=1:nvarBR;     //to store weights of all variables string str = "a";       //default for specifying elimination ordering if (size(#) == 0)       //default values @w = #[1];              //take the given weights str = #[2];             //string for specifying elimination ordering } if ( typeof(#[1]) == "string" and typeof(#[2]) == "intvec" ) { int local = (var(ii) < 1); } } } else //define now the first a-block of the form a(w1,0..0) intvec @v; @v[nvarBR] = 0; intvec @v=0:nvarBR; @v = @v+w1; B3[1] = list("a", @v);
• ## Singular/LIB/freegb.lib

 r2c3a5d ////////////////////////////////////////////////////////////////////////////// version="$Id: freegb.lib,v 1.21 2009-04-09 12:04:41 seelisch Exp$"; version="$Id: freegb.lib,v 1.22 2009-04-14 12:00:14 Singular Exp$"; category="Noncommutative"; info=" PURPOSE: sets attributes for a letterplace ring: @*      'isLetterplaceRing' = true, 'uptodeg' = d, 'lV' = b, where @*      'uptodeg' stands for the degree bound, @*      'uptodeg' stands for the degree bound, @*      'lV' for the number of variables in the block 0. NOTE: Activate the resulting ring by using @code{setring} ERROR("uptodeg and lV do not agree on the basering!"); } // Set letterplace-specific attributes for the output ring! attrib(R, "uptodeg", uptodeg); attrib(R, "lV", lV); attrib(R, "isLetterplaceRing", 1); return (R); attrib(R, "lV", lV); attrib(R, "isLetterplaceRing", 1); return (R); } example "USAGE:  isVar(p);  poly p RETURN:  int PURPOSE: check, whether leading monomial of p is a power of a single variable PURPOSE: check, whether leading monomial of p is a power of a single variable @* from the basering. Returns the exponent or 0 if p is multivariate. EXAMPLE: example isVar; shows examples def R = makeLetterplaceRing(d); setring R; int uptodeg = d; int lV = 2; int uptodeg = d; int lV = 2; def R = setLetterplaceAttributes(r,uptodeg,2); // supply R with letterplace structure setring R;
• ## Singular/LIB/jacobson.lib

 r2c3a5d ////////////////////////////////////////////////////////////////////////////// version="$Id: jacobson.lib,v 1.10 2009-03-05 20:36:11 levandov Exp$"; version="$Id: jacobson.lib,v 1.11 2009-04-14 12:00:14 Singular Exp$"; category="System and Control Theory"; info=" @* with respect to the mult. closed set S = K[x] without 0. @* Thus, we treat basering as principal ideal ring with d a polynomial @* variable and x an invertible one. @* variable and x an invertible one. @* Note, that in computations no division by x will actually happen. @* REFERENCES: @* (1) N. Jacobson, 'The theory of rings', AMS, 1943. @* (2) Manuel Avelino Insua Hermo, 'Varias perspectives sobre las bases de Groebner : @* Forma normal de Smith, Algorithme de Berlekamp y algebras de Leibniz'. @* (2) Manuel Avelino Insua Hermo, 'Varias perspectives sobre las bases de Groebner : @* Forma normal de Smith, Algorithme de Berlekamp y algebras de Leibniz'. @* PhD thesis, Universidad de Santiago de Compostela, 2005. L = LL; } // divide units out int i; int nsize = Min(intvec(nrM,ncM)); poly p; number n; intvec lexp; for(i=1; i<=nsize; i++) { RETURN: matrix or list of matrices, depending on arguments ASSUME: Basering is a commutative polynomial ring in one variable PURPOSE: compute the Smith Normal Form of M with (optionally) transformation matrices PURPOSE: compute the Smith Normal Form of M with (optionally) transformation matrices THEORY: Groebner bases are used for the Smith form like in (2). NOTE: By default, just the Smith normal form of M is returned. @* where U*M*V = D and the diagonal field entries of D are not normalized. @* The normalization of the latter can be done with the 'divideUnits' procedure. @* U and V above are square unimodular (invertible) matrices. @* U and V above are square unimodular (invertible) matrices. @* Note, that the procedure works for a rectangular matrix M. @*
• ## Singular/LIB/nctools.lib

 r2c3a5d /////////////////////////////////////////////////////////////////////////////// version="$Id: nctools.lib,v 1.48 2009-04-14 08:25:19 Singular Exp$"; version="$Id: nctools.lib,v 1.49 2009-04-14 12:00:14 Singular Exp$"; category="Noncommutative"; info=" { print("Warning: Since the current ordering is not global there might be problems computing twostd(Q)!"); "Q:"; "Q:"; @Q; }
• ## Singular/LIB/polymake.lib

 r2c3a5d version="$Id: polymake.lib,v 1.14 2009-04-07 16:18:06 seelisch Exp$"; version="$Id: polymake.lib,v 1.15 2009-04-14 12:00:14 Singular Exp$"; category="Tropical Geometry"; info=" LIBRARY:   polymake.lib    Computations with polytopes and fans, LIBRARY:   polymake.lib    Computations with polytopes and fans, interface to polymake and TOPCOM AUTHOR:    Thomas Markwig,  email: keilen@mathematik.uni-kl.de WARNING: Most procedures will not work unless polymake or topcom is installed and if so, they will only work with the operating system LINUX! if so, they will only work with the operating system LINUX! For more detailed information see the following note or consult the help string of the procedures. NOTE: Even though this is a Singular library for computing polytopes and fans such as the Newton polytope or the Groebner fan of a polynomial, most of the hard computations are NOT done by Singular but by the program Even though this is a Singular library for computing polytopes and fans such as the Newton polytope or the Groebner fan of a polynomial, most of the hard computations are NOT done by Singular but by the program @* - polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt @*   (see http://www.math.tu-berlin.de/polymake/), @*   (see http://www.math.tu-berlin.de/polymake/), @* respectively (only in the procedure triangularions) by the program @* - topcom by Joerg Rambau, Universitaet Bayreuth (see http://www.uni-bayreuth.de/ departments/wirtschaftsmathematik/rambau/TOPCOM); @*   This library should rather be seen as an interface which allows to use a (very limited) number of options which polymake respectively topcom offers to compute with polytopes and fans and to make the results available in (very limited) number of options which polymake respectively topcom offers to compute with polytopes and fans and to make the results available in Singular for further computations; moreover, the user familiar with Singular does not have to learn the syntax of polymake or topcom, if the options offered here are sufficient for his of polymake or topcom, if the options offered here are sufficient for his purposes. @*   Note, though, that the procedures concerned with planar polygons are @*   Note, though, that the procedures concerned with planar polygons are independent of both, polymake and topcom. groebnerFan        computes the Groebner fan of a polynomial intmatToPolymake   transforms an integer matrix into polymake format polymakeToIntmat   transforms polymake output into an integer matrix polymakeToIntmat   transforms polymake output into an integer matrix PROCEDURES USING TOPCOM: splitPolygon     splits a marked polygon into vertices, facets, interior points eta              computes the eta-vector of a triangulation findOrientedBoundary    computes the boundary of a convex hull findOrientedBoundary    computes the boundary of a convex hull cyclePoints      computes lattice points connected to some lattice point latticeArea      computes the lattice area of a polygon KEYWORDS:    polytope; fan; secondary fan; secondary polytope; polymake; Newton polytope; Groebner fan Newton polytope; Groebner fan "; proc polymakePolytope (intmat polytope,list #) "USAGE:  polymakePolytope(polytope[,#]);   polytope list, # string ASSUME:  each row of polytope gives the coordinates of a lattice point of a polytope with their affine coordinates as given by the output of ASSUME:  each row of polytope gives the coordinates of a lattice point of a polytope with their affine coordinates as given by the output of secondaryPolytope PURPOSE: the procedure calls polymake to compute the vertices of the polytope PURPOSE: the procedure calls polymake to compute the vertices of the polytope as well as its dimension and information on its facets RETURN:  list L with four entries @*            L[1] : an integer matrix whose rows are the coordinates of vertices of the polytope of the polytope @*            L[2] : the dimension of the polytope @*            L[3] : a list whose i-th entry explains to which vertices the ith vertex of the Newton polytope is connected -- i.e. L[3][i] is an integer vector and an entry k in there means that the vertex L[1][i] is connected to the ith vertex of the Newton polytope is connected -- i.e. L[3][i] is an integer vector and an entry k in there means that the vertex L[1][i] is connected to the vertex L[1][k] @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give a linear system of equations @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give a linear system of equations describing the affine hull of the polytope, i.e. the smallest affine space containing the polytope NOTE: -  for its computations the procedure calls the program polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; it therefore is necessary that this program is installed in order NOTE: -  for its computations the procedure calls the program polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, TU Darmstadt; it therefore is necessary that this program is installed in order to use this procedure; see http://www.math.tu-berlin.de/polymake/ @*    -  note that in the vertex edge graph we have changed the polymake convention which starts indexing its vertices by zero while we start @*    -  note that in the vertex edge graph we have changed the polymake convention which starts indexing its vertices by zero while we start with one ! @*    -  the procedure creates the file  /tmp/polytope.polymake which contains the polytope in polymake format; if you wish to use this for further computations with polymake, you have to use the procedure @*    -  the procedure creates the file  /tmp/polytope.polymake which contains the polytope in polymake format; if you wish to use this for further computations with polymake, you have to use the procedure polymakeKeepTmpFiles in before @*    -  moreover, the procedure creates the file /tmp/polytope.output which it deletes again before ending @*    -  it is possible to provide an optional second argument a string which then will be used instead of 'polytope' in the name of the which then will be used instead of 'polytope' in the name of the polymake output file EXAMPLE: example polymakePolytope;   shows an example" } } } } newveg=newveg[1,size(newveg)-1]; execute("list nveg="+newveg+";"); "EXAMPLE:"; echo=2; // the lattice points of the unit square in the plane // the lattice points of the unit square in the plane list points=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); // the secondary polytope of this lattice point configuration is computed of the Newton polytope of f @*            L[2] : the dimension of the Newton polytope of f @*            L[3] : a list whose ith entry explains to which vertices the ith vertex of the Newton polytope is connected -- i.e. L[3][i] is an integer vector and an entry k in @*            L[3] : a list whose ith entry explains to which vertices the ith vertex of the Newton polytope is connected -- i.e. L[3][i] is an integer vector and an entry k in there means that the vertex L[1][i] is connected to the vertex L[1][k] @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give a linear system of equations @*            L[4] : an integer matrix whose rows mulitplied by (1,var(1),...,var(nvar)) give a linear system of equations describing the affine hull of the Newton polytope, i.e. the smallest affine space containing the Newton polytope NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move the affine hull to the origin, then we get the equations for the orthogonal comploment of the linearity space of the normal fan dual NOTE: -  if we replace the first column of L[4] by zeros, i.e. if we move the affine hull to the origin, then we get the equations for the orthogonal comploment of the linearity space of the normal fan dual to the Newton polytope, i.e. we get the EQUATIONS that we need as input for polymake when computing the normal fan TU Berlin and Michael Joswig, so it only works if polymake is installed; see http://www.math.tu-berlin.de/polymake/ @*    -  the procedure creates the file  /tmp/newtonPolytope.polymake which contains the polytope in polymake format and which can be used for @*    -  the procedure creates the file  /tmp/newtonPolytope.polymake which contains the polytope in polymake format and which can be used for further computations with polymake @*    -  moreover, the procedure creates the file /tmp/newtonPolytope.output @*    -  moreover, the procedure creates the file /tmp/newtonPolytope.output and deletes it again before ending @*    -  it is possible to give as an optional second argument a string which then will be used instead of 'newtonPolytope' in the name of @*    -  it is possible to give as an optional second argument a string which then will be used instead of 'newtonPolytope' in the name of the polymake output file EXAMPLE: example newtonPolytope;   shows an example" { int i,j; // compute the list of exponent vectors of the polynomial, // compute the list of exponent vectors of the polynomial, // which are the lattice points // whose convex hull is the Newton polytope of f np[2]; // np[3] contains information how the vertices are connected to each other, // e.g. the first vertex (number 0) is connected to the second, third and // e.g. the first vertex (number 0) is connected to the second, third and //      fourth vertex np[3][1]; np[1]; // its dimension is np[2]; // the Newton polytope is contained in the affine space given np[2]; // the Newton polytope is contained in the affine space given //     by the equations np[4]*M; proc newtonPolytopeLP (poly f) "USAGE:  newtonPolytopeLP(f);  f poly RETURN: list, the exponent vectors of the monomials occuring in f, RETURN: list, the exponent vectors of the monomials occuring in f, i.e. the lattice points of the Newton polytope of f EXAMPLE: example normalFan;   shows an example" proc normalFan (intmat vertices,intmat affinehull,list graph,int er,list #) "USAGE:  normalFan (vert,aff,graph,rays,[,#]);   vert,aff intmat,  graph list, rays int, # string ASSUME:  - vert is an integer matrix whose rows are the coordinate of the vertices of a convex lattice polytope; ASSUME:  - vert is an integer matrix whose rows are the coordinate of the vertices of a convex lattice polytope; @*       - aff describes the affine hull of this polytope, i.e. the smallest affine space containing it, in the following sense: denote by n the number of columns of vert, then multiply aff by (1,x(1),...,x(n)) and set the resulting terms to zero in order to the smallest affine space containing it, in the following sense: denote by n the number of columns of vert, then multiply aff by (1,x(1),...,x(n)) and set the resulting terms to zero in order to get the equations for the affine hull; @*       - the ith entry of graph is an integer vector describing to which vertices the ith vertex is connected, i.e. a k as entry means that @*       - the ith entry of graph is an integer vector describing to which vertices the ith vertex is connected, i.e. a k as entry means that the vertex vert[i] is connected to vert[k]; @*       - the integer rays is either one (if the extreme rays should be @*       - the integer rays is either one (if the extreme rays should be computed) or zero (otherwise) RETURN:  list, the ith entry of L[1] contains information about the cone in the normal fan dual to the ith vertex of the polytope @*             L[1][i][1] = integer matrix representing the inequalities which RETURN:  list, the ith entry of L[1] contains information about the cone in the normal fan dual to the ith vertex of the polytope @*             L[1][i][1] = integer matrix representing the inequalities which describe the cone dual to the ith vertex @*             L[1][i][2] = a list which contains the inequalities represented by L[i][1] as a list of strings, where we use the @*             L[1][i][2] = a list which contains the inequalities represented by L[i][1] as a list of strings, where we use the variables x(1),...,x(n) @*             L[1][i][3] = only present if 'er' is set to 1; in that case it is an interger matrix whose rows are the extreme rays an interger matrix whose rows are the extreme rays of the cone @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in each cone NOTE:    - the procedure calls for its computation polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, so it only works if polymake is TU Berlin and Michael Joswig, so it only works if polymake is installed; see http://www.math.tu-berlin.de/polymake/ @*       - in the optional argument # it is possible to hand over other names @*       - in the optional argument # it is possible to hand over other names for the variables to be used -- be careful, the format must be correct which is not tested, e.g. if you want the variable names to be list ineq; // stores the inequalities of the cones int i,j,k; // we work over the following ring // we work over the following ring execute("ring ineqring=0,x(1.."+string(ncols(vertices))+"),lp;"); string greatersign=">"; for (i=1;i<=nrows(vertices);i++) { // first we produce for each vertex in the polytope // first we produce for each vertex in the polytope // the inequalities describing the dual cone in the normal fan list pp;  // contain strings representing the inequalities list pp;  // contain strings representing the inequalities // describing the normal cone intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities intmat ie[size(graph[i])][ncols(vertices)]; // contains the inequalities // as rows // consider all the vertices to which the ith vertex in the // consider all the vertices to which the ith vertex in the // polytope is connected by an edge for (j=1;j<=size(graph[i]);j++) { // produce the vector ie_j pointing from the jth vertex to the ith vertex; // this will be the jth inequality for the cone in the normal fan dual to // this will be the jth inequality for the cone in the normal fan dual to // the ith vertex ie[j,1..ncols(vertices)]=vertices[i,1..ncols(vertices)]-vertices[graph[i][j],1..ncols(vertices)]; p=(VAR*EXP)[1,1]; pl,pr=0,0; // separate the terms with positive coefficients in p from // separate the terms with positive coefficients in p from // those with negative coefficients for (k=1;k<=size(p);k++) } } // build the string which represents the jth inequality // build the string which represents the jth inequality // for the cone dual to the ith vertex // as polynomial inequality of type string, and store this // as polynomial inequality of type string, and store this // in the list pp as jth entry pp[j]=string(pl)+" "+greatersign+" "+string(pr); // create the file ineq.output write(":w /tmp/ineq.output",""); int dimension; // keeps the dimension of the intersection the int dimension; // keeps the dimension of the intersection the // bad cones with the u11tobeseencone for (i=1;i<=size(ineq);i++) { i,". Cone of ",nrows(vertices); // indicate how many i,". Cone of ",nrows(vertices); // indicate how many // vertices have been dealt with ungleichungen=intmatToPolymake(ineq[i][1],"rays"); } // get the linearity space return(list(ineq,linearity)); return(list(ineq,linearity)); } example proc groebnerFan (poly f,list #) "USAGE:  groebnerFan(f[,#]);  f poly, # string RETURN:  list, the ith entry of L[1] contains information about the ith cone in the Groebner fan dual to the ith vertex in the Newton RETURN:  list, the ith entry of L[1] contains information about the ith cone in the Groebner fan dual to the ith vertex in the Newton polytope of the f @*             L[1][i][1] = integer matrix representing the inequalities which describe the cone @*             L[1][i][2] = a list which contains the inequalities represented @*             L[1][i][1] = integer matrix representing the inequalities which describe the cone @*             L[1][i][2] = a list which contains the inequalities represented by L[1][i][1] as a list of strings @*             L[1][i][3] = an interger matrix whose rows are the extreme rays @*             L[1][i][3] = an interger matrix whose rows are the extreme rays of the cone @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in each cone @*             L[3] = the Newton polytope of f in the format of the procedure @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in each cone @*             L[3] = the Newton polytope of f in the format of the procedure newtonPolytope @*             L[4] = integer matrix where each row represents the exponet @*             L[4] = integer matrix where each row represents the exponet vector of one monomial occuring in the input polynomial NOTE: - if you have already computed the Newton polytope of f then you might want to use the procedure normalFan instead in order to avoid doing costly to use the procedure normalFan instead in order to avoid doing costly computation twice @*    - the procedure calls for its computation polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, so it only works if polymake is installed; see http://www.math.tu-berlin.de/polymake/ @*    - the procedure creates the file  /tmp/newtonPolytope.polymake which contains the Newton polytope of f in polymake format and which can @*    - the procedure creates the file  /tmp/newtonPolytope.polymake which contains the Newton polytope of f in polymake format and which can be used for further computations with polymake @*    - it is possible to give as an optional second argument as string which then will be used instead of 'newtonPolytope' in the name of the @*    - it is possible to give as an optional second argument as string which then will be used instead of 'newtonPolytope' in the name of the polymake output file EXAMPLE: example groebnerFan;   shows an example" { int i,j; // compute the list of exponent vectors of the polynomial, which are // compute the list of exponent vectors of the polynomial, which are // the lattice points whose convex hull is the Newton polytope of f intmat exponents[size(f)][nvars(basering)]; proc intmatToPolymake (intmat M,string art) "USAGE:  intmatToPolymake(M,art);  M intmat, art string ASSUME:  - M is an integer matrix which should be transformed into polymake ASSUME:  - M is an integer matrix which should be transformed into polymake format; @*       - art is one of the following strings: @*           + 'rays'   : indicating that a first column of 0's should be added @*           + 'points' : indicating that a first column of 1's should be added RETURN:  string, the matrix is transformed in a string and a first column has @*           + 'points' : indicating that a first column of 1's should be added RETURN:  string, the matrix is transformed in a string and a first column has been added EXAMPLE: example intmatToPolymake;   shows an example" string anf="0 "; } else else { string anf="1 "; proc polymakeToIntmat (string pm,string art) "USAGE:  polymakeToIntmat(pm,art);  pm, art string ASSUME:  pm is the result of calling polymake with one 'argument' like VERTICES, AFFINE_HULL, etc., so that the first row of the string is the name of the corresponding 'argument' and the further rows contain ASSUME:  pm is the result of calling polymake with one 'argument' like VERTICES, AFFINE_HULL, etc., so that the first row of the string is the name of the corresponding 'argument' and the further rows contain the result which consists of vectors either over the integers or over the rationals from the second row, where each row has been multiplied with the lowest common multiple of the denominators of its entries as if it is an integer matrix; moreover, if art=='affine', then the first column is omitted since we only want affine it is an integer matrix; moreover, if art=='affine', then the first column is omitted since we only want affine coordinates EXAMPLE: example polymakeToIntmat;   shows an example" pm=stringdelete(pm,1); } pm=stringdelete(pm,1); // find out how many entries each vector has, namely one more pm=stringdelete(pm,1); // find out how many entries each vector has, namely one more // than 'spaces' in a row int i=1; // if we want to have affine coordinates if (art=="affine") { { s--; // then there is one column less // and the entry of the first column (in the first row) has to be removed pm=stringdelete(pm,1); } // we add two line breaks at the end in order to have this as // we add two line breaks at the end in order to have this as // a stopping criterion pm=pm+zeilenumbruch+zeilenumbruch; z++; pm[i]=","; // if we want to have affine coordinates, // if we want to have affine coordinates, // then we have to delete the first entry in each row if (art=="affine") if (pm[i]==" ") { pm[i]=","; pm[i]=","; } } pm=stringdelete(pm,size(pm)); } // since the matrix could be over the rationals, // since the matrix could be over the rationals, // we need a ring with rational coefficients ring zwischering=0,x,lp; ring zwischering=0,x,lp; // create the matrix with the elements of pm as entries execute("matrix mm["+string(z)+"]["+string(s)+"]="+pm+";"); proc triangulations (list polygon) "USAGE:  triangulations(polygon); list polygon ASSUME:  polygon is a list of integer vectors of the same size representing the affine coordinates of the lattice points ASSUME:  polygon is a list of integer vectors of the same size representing the affine coordinates of the lattice points PURPOSE: the procedure considers the marked polytope given as the convex hull of the lattice points and with these lattice points as markings; it then computes all possible triangulations of this marked polytope computes all possible triangulations of this marked polytope RETURN:  list, each entry corresponds to one triangulation and the ith entry is itself a list of integer vectors of size three, where each integer NOTE:- the procedure calls for its computations the program points2triangs from the program topcom by Joerg Rambau, Universitaet Bayreuth; it therefore is necessary that this program is installed in order to use therefore is necessary that this program is installed in order to use this  procedure; see @*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM @*   - the procedure creates the files /tmp/triangulationsinput and @*   - the procedure creates the files /tmp/triangulationsinput and /tmp/triangulationsoutput; the former is used as input for points2triangs and the latter is its output containing the triangulations of corresponding to points in the format of points2triangs; if you wish to use this for further computations with topcom, you have to use the procedure the former is used as input for points2triangs and the latter is its output containing the triangulations of corresponding to points in the format of points2triangs; if you wish to use this for further computations with topcom, you have to use the procedure polymakeKeepTmpFiles in before @*   - note that an integer i in an integer vector representing a triangle refers to the ith lattice point, i.e. polygon[i]; this convention is different from TOPCOM's convention, where i would refer to the i-1st @*   - note that an integer i in an integer vector representing a triangle refers to the ith lattice point, i.e. polygon[i]; this convention is different from TOPCOM's convention, where i would refer to the i-1st lattice point EXAMPLE: example triangulations;   shows an example" { int i,j; // prepare the input for points2triangs by writing the input polygon in the // prepare the input for points2triangs by writing the input polygon in the // necessary format string spi="["; system("sh","cd /tmp; rm -f triangulationsinput; rm -f triangulationsoutput"); } // preprocessing of p2t if points2triangs is version >= 0.15 // preprocessing of p2t if points2triangs is version >= 0.15 // brings p2t to the format of version 0.14 string np2t; // takes the triangulations in Singular format } else { { np2t=np2t+p2t[i]; } { if (np2t[size(np2t)]!=";") { { np2t=np2t+p2t[size(p2t)-1]+p2t[size(p2t)]; } np2t=np2t+"))"; i++; } } else { "EXAMPLE:"; echo=2; // the lattice points of the unit square in the plane // the lattice points of the unit square in the plane list polygon=intvec(0,0),intvec(0,1),intvec(1,0),intvec(1,1); // the triangulations of this lattice point configuration are computed int i,j,k,l; intmat N[2][2]; // is used to compute areas of triangles intvec vertex;  // stores a point in the secondary polytope as intvec vertex;  // stores a point in the secondary polytope as // intermediate result int eintrag; int halt; intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points intmat secpoly[size(triangs)][size(polygon)];   // stores all lattice points // of the secondary polytope // consider each triangulation and compute the corresponding point // consider each triangulation and compute the corresponding point // in the secondary polytope for (i=1;i<=size(triangs);i++) { // for each triangulation we have to compute the coordinates // for each triangulation we have to compute the coordinates // corresponding to each marked point for (j=1;j<=size(polygon);j++) { eintrag=0; // for each marked point we have to consider all triangles in the // for each marked point we have to consider all triangles in the // triangulation which involve this particular point for (k=1;k<=size(triangs[i]);k++) secpoly[i,1..size(polygon)]=vertex; } return(list(secpoly,triangs)); return(list(secpoly,triangs)); } example proc secondaryFan (list polygon,list #) "USAGE:  secondaryFan(polygon[,#]); list polygon, list # ASSUME:  - polygon is a list of integer vectors of the same size representing ASSUME:  - polygon is a list of integer vectors of the same size representing the affine coordinates of lattice points @*       - if the triangulations of the corresponding polygon have already been computed with the procedure triangulations then these can be given as a second (optional) argument in order to avoid doing this @*       - if the triangulations of the corresponding polygon have already been computed with the procedure triangulations then these can be given as a second (optional) argument in order to avoid doing this computation again PURPOSE: the procedure considers the marked polytope given as the convex hull of the lattice points and with these lattice points as markings; it then computes the lattice points of the secondary polytope given by this computes the lattice points of the secondary polytope given by this marked polytope which correspond to the triangulations computed by the procedure triangulations RETURN:  list, the ith entry of L[1] contains information about the ith cone in the secondary fan of the polygon, i.e. the cone dual to the RETURN:  list, the ith entry of L[1] contains information about the ith cone in the secondary fan of the polygon, i.e. the cone dual to the ith vertex of the secondary polytope @*             L[1][i][1] = integer matrix representing the inequalities which @*             L[1][i][1] = integer matrix representing the inequalities which describe the cone dual to the ith vertex @*             L[1][i][2] = a list which contains the inequalities represented @*             L[1][i][2] = a list which contains the inequalities represented by L[1][i][1] as a list of strings, where we use the variables x(1),...,x(n) @*             L[1][i][3] = only present if 'er' is set to 1; in that case it is an interger matrix whose rows are the extreme rays an interger matrix whose rows are the extreme rays of the cone @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in @*             L[2] = is an integer matrix whose rows span the linearity space of the fan, i.e. the linear space which is contained in each cone @*             L[3] = the secondary polytope in the format of the procedure @*             L[3] = the secondary polytope in the format of the procedure polymakePolytope @*             L[4] = the list of triangulations corresponding to the vertices @*             L[4] = the list of triangulations corresponding to the vertices of the secondary polytope NOTE:- the procedure calls for its computation polymake by Ewgenij Gawrilow, TU Berlin and Michael Joswig, so it only works if polymake is installed; see http://www.math.tu-berlin.de/polymake/ @*   - in the optional argument # it is possible to hand over other names for @*   - in the optional argument # it is possible to hand over other names for the variables to be used -- be careful, the format must be correct which is not tested, e.g. if you want the variable names to be u00,u10,u01,u11 then you must hand over the string 'u11,u10,u01,u11' @*   - if the triangluations are not handed over as optional argument the procedure calls for its computation of these triangulations the program points2triangs from the program topcom by Joerg Rambau, Universitaet Bayreuth; it therefore is necessary that this program is installed in @*   - if the triangluations are not handed over as optional argument the procedure calls for its computation of these triangulations the program points2triangs from the program topcom by Joerg Rambau, Universitaet Bayreuth; it therefore is necessary that this program is installed in order to use this procedure; see @*     http://www.uni-bayreuth.de/departments/wirtschaftsmathematik/rambau/TOPCOM proc cycleLength (list boundary,intvec interior) "USAGE:  cycleLength(boundary,interior); list boundary, intvec interior ASSUME:  boundary is a list of integer vectors describing a cycle in some convex lattice polygon around the lattice point interior ordered ASSUME:  boundary is a list of integer vectors describing a cycle in some convex lattice polygon around the lattice point interior ordered clock wise RETURN:  string, the cycle length of the corresponding cycle in the dual { int j; // create a ring whose variables are indexed by the points in // create a ring whose variables are indexed by the points in // boundary resp. by interior string rst="ring cyclering=0,(u"+string(interior[1])+string(interior[2]); // interior is a lattice point in the interior of this lattice polygon intvec interior=1,1; // compute the general cycle length of a cycle of the corresponding cycle // compute the general cycle length of a cycle of the corresponding cycle // in the dual tropical curve, note that (0,1) and (2,1) do not contribute cycleLength(boundary,interior); proc splitPolygon (list markings) "USAGE:  splitPolygon (markings);  markings list ASSUME:  markings is a list of integer vectors representing lattice points in the plane which we consider as the marked points of the convex lattice ASSUME:  markings is a list of integer vectors representing lattice points in the plane which we consider as the marked points of the convex lattice polytope spanned by them PURPOSE: split the marked points in the vertices, the points on the facets PURPOSE: split the marked points in the vertices, the points on the facets which are not vertices, and the interior points RETURN:  list, L consisting of three lists @*                       L[1][i][1] = intvec, the coordinates of the ith vertex @*                       L[1][i][2] = int, the position of L[1][i][1] in markings @*             L[2][i] : represents the lattice points on the facet of the polygon with endpoints L[1][i] and L[1][i+1] @*             L[2][i] : represents the lattice points on the facet of the polygon with endpoints L[1][i] and L[1][i+1] (i considered modulo size(L[1])) @*                       L[2][i][j][1] = intvec, the coordinates of the jth @*                       L[2][i][j][1] = intvec, the coordinates of the jth lattice point on that facet @*                       L[2][i][j][2] = int, the position of L[2][i][j][1] @*                       L[2][i][j][2] = int, the position of L[2][i][j][1] in markings @*             L[3]    : represents the interior lattice points of the polygon @*             L[3]    : represents the interior lattice points of the polygon @*                       L[3][i][1] = intvec, coordinates of ith interior point @*                       L[3][i][2] = int, the position of L[3][i][1] in markings vert[1]=pb[2]; int i,j,k;      // indices list boundary;  // stores the points on the facets of the list boundary;  // stores the points on the facets of the // polygon which are not vertices // append to the boundary points as well as to the vertices // append to the boundary points as well as to the vertices // the first vertex a second time pb[1]=pb[1]+list(pb[1][1]); // store the information on the boundary in vert[2] vert[2]=boundary; // find the remaining points in the input which are not on // find the remaining points in the input which are not on // the boundary by checking // for each point in markings if it is contained in pb[1] // store the interior points in vert[3] vert[3]=interior; // add to each point in vert the index which it gets from // add to each point in vert the index which it gets from // its position in the input markings; // do so for ver[1] } vert[3][i]=list(vert[3][i],j); } } return(vert); } "EXAMPLE:"; echo=2; // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // with all integer points as markings list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), proc eta (list triang,list polygon) "USAGE:  eta(triang,polygon);  triang, polygon list ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a list with three entries describing a convex lattice polygon in the ASSUME:  polygon has the format of the output of splitPolygon, i.e. it is a list with three entries describing a convex lattice polygon in the following way: @*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] is a lattice point which is a vertex of the lattice @*       polygon[1] : is a list of lists; for each i the entry polygon[1][i][1] is a lattice point which is a vertex of the lattice polygon, and polygon[1][i][2] is an integer assigned to this lattice point as identifying index @*       polygon[2] : is a list of lists; for each vertex of the polygon, i.e. for each entry in polygon[1], it contains a list polygon[2][i], which contains the lattice points on the facet with endpoints polygon[1][i] and polygon[1][i+1] @*       polygon[2] : is a list of lists; for each vertex of the polygon, i.e. for each entry in polygon[1], it contains a list polygon[2][i], which contains the lattice points on the facet with endpoints polygon[1][i] and polygon[1][i+1] - i considered mod size(polygon[1]); each such lattice point contributes an entry each such lattice point contributes an entry polygon[2][i][j][1] which is an integer vector giving the coordinate of the lattice point and an vector giving the coordinate of the lattice point and an entry polygon[2][i][j][2] which is the identifying index @*       polygon[3] : is a list of lists, where each entry corresponds to a lattice point in the interior of the polygon, with @*       polygon[3] : is a list of lists, where each entry corresponds to a lattice point in the interior of the polygon, with polygon[3][j][1] being the coordinates of the point and polygon[3][j][2] being the identifying index; @*       triang is a list of integer vectors all of size three describing a triangulation of the polygon described by polygon; if an entry of @*       triang is a list of integer vectors all of size three describing a triangulation of the polygon described by polygon; if an entry of triang is the vector (i,j,k) then the triangle is built from the vertices with indices i, j and k RETURN:  intvec, the integer vector eta describing that vertex of the Newton polytope discriminant of the polygone whose dual cone in the Groebner fan contains the cone of the secondary fan of the RETURN:  intvec, the integer vector eta describing that vertex of the Newton polytope discriminant of the polygone whose dual cone in the Groebner fan contains the cone of the secondary fan of the polygon corresponding to the given triangulation NOTE:  for a better description of eta see Gelfand, Kapranov, NOTE:  for a better description of eta see Gelfand, Kapranov, Zelevinski: Discriminants, Resultants and multidimensional Determinants. Chapter 10. { int i,j,k,l,m,n; // index variables list ordpolygon;   // stores the lattice points in the order list ordpolygon;   // stores the lattice points in the order // used in the triangulation list triangarea; // stores the areas of the triangulations for (i=1;i<=size(triang);i++) { // Note that the ith lattice point in orderedpolygon has the // Note that the ith lattice point in orderedpolygon has the // number i-1 in the triangulation! N=ordpolygon[triang[i][1]]-ordpolygon[triang[i][2]],ordpolygon[triang[i][1]]-ordpolygon[triang[i][3]]; } intvec ETA;        // stores the eta_ij int etaij;         // stores the part of eta_ij during computations int etaij;         // stores the part of eta_ij during computations // which comes from triangle areas int seitenlaenge;  // stores the part of eta_ij during computations int seitenlaenge;  // stores the part of eta_ij during computations // which comes from boundary facets list seiten;       // stores the lattice points on facets of the polygon intvec v;          // used to compute a facet length // 3) store first in seiten[i] all lattice points on the facet // 3) store first in seiten[i] all lattice points on the facet //    connecting the ith vertex, //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], //    i.e. polygon[1][i], with the i+1st vertex, i.e. polygon[1][i+1], //    where we replace i+1 //    1 if i=size(polygon[1]); //    then append the last entry of seiten once more at the very //    then append the last entry of seiten once more at the very //    beginning of seiten, so //    that the index is shifted by one if ((polygon[1][j][2]==triang[k][1]) or (polygon[1][j][2]==triang[k][2]) or (polygon[1][j][2]==triang[k][3])) { // ... if so, add the area of the triangle to etaij // ... if so, add the area of the triangle to etaij etaij=etaij+triangarea[k]; // then check if that triangle has a facet which is contained // in one of the // then check if that triangle has a facet which is contained // in one of the // two facets of the polygon which are adjecent to the given vertex ... // these two facets are seiten[j] and seiten[j+1] if ((seiten[n][l][2]==triang[k][m]) and (seiten[n][l][2]!=polygon[1][j][2])) { // if so, then compute the vector pointing from this // if so, then compute the vector pointing from this // lattice point to the vertex v=polygon[1][j][1]-seiten[n][l][1]; // and the lattice length of this vector has to be // and the lattice length of this vector has to be // subtracted from etaij etaij=etaij-abs(gcd(v[1],v[2])); ETA[polygon[1][j][2]]=etaij; } // 5) compute the eta_ij for all lattice points on the facets // 5) compute the eta_ij for all lattice points on the facets //    of the polygon which are not vertices, these are the //    lattice points in polygon[2][1] to polygon[2][size(polygon[1])] { for (j=1;j<=size(polygon[2][i]);j++) { { // initialise etaij etaij=0; if ((polygon[2][i][j][2]==triang[k][1]) or (polygon[2][i][j][2]==triang[k][2]) or (polygon[2][i][j][2]==triang[k][3])) { // ... if so, add the area of the triangle to etaij // ... if so, add the area of the triangle to etaij etaij=etaij+triangarea[k]; // then check if that triangle has a facet which is contained in the // then check if that triangle has a facet which is contained in the // facet of the polygon which contains the lattice point in question, // this is the facet seiten[i+1]; // ... and for each lattice point in the triangle ... for (m=1;m<=size(triang[k]);m++) { { // ... if they coincide and are not the vertex itself ... if ((seiten[i+1][l][2]==triang[k][m]) and (seiten[i+1][l][2]!=polygon[2][i][j][2])) { // if so, then compute the vector pointing from // if so, then compute the vector pointing from // this lattice point to the vertex v=polygon[2][i][j][1]-seiten[i+1][l][1]; // and the lattice length of this vector contributes // and the lattice length of this vector contributes // to seitenlaenge seitenlaenge=seitenlaenge+abs(gcd(v[1],v[2])); } } // if the lattice point was a vertex of any triangle // if the lattice point was a vertex of any triangle // in the triangulation ... if (etaij!=0) if ((polygon[3][j][2]==triang[k][1]) or (polygon[3][j][2]==triang[k][2]) or (polygon[3][j][2]==triang[k][3])) { // ... if so, add the area of the triangle to etaij // ... if so, add the area of the triangle to etaij etaij=etaij+triangarea[k]; } "EXAMPLE:"; echo=2; // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // with all integer points as markings list polygon=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), // split the polygon in its vertices, its facets and its interior points list sp=splitPolygon(polygon); // define a triangulation by connecting the only interior point // define a triangulation by connecting the only interior point //        with the vertices list triang=intvec(1,2,5),intvec(1,5,10),intvec(1,5,10); eta(triang,sp); } ///////////////////////////////////////////////////////////////////////////// } // check is the polygon is only a line segment given by more than two points; // for this first compute sum of the absolute values of the determinants // for this first compute sum of the absolute values of the determinants // of the matrices whose // rows are the vectors pointing from the first to the second point // rows are the vectors pointing from the first to the second point // and from the // the first point to the ith point for i=3,...,size(polygon); // the first point to the ith point for i=3,...,size(polygon); // if this sum is zero // then the polygon is a line segment and we have to find its end points intmat laenge[size(polygon)][size(polygon)]; intvec mp; //   for this collect first all vectors pointing from one lattice //   for this collect first all vectors pointing from one lattice //   point to the next, //   compute their pairwise angles and their lengths for (i=1;i<=size(polygon)-1;i++) { { for (j=i+1;j<=size(polygon);j++) { polygon=sortlistbyintvec(polygon,abstand); return(list(polygon,endpoints)); } } /////////////////////////////////////////////////////////////// list orderedvertices;  // stores the vertices in an ordered way list minimisedorderedvertices;  // stores the vertices in an ordered way; list minimisedorderedvertices;  // stores the vertices in an ordered way; // redundant ones removed list comparevertices; // stores vertices which should be compared to list comparevertices; // stores vertices which should be compared to // the testvertex orderedvertices[1]=polygon[1]; // set the starting vertex minimisedorderedvertices[1]=polygon[1]; // set the starting vertex intvec testvertex=polygon[1];  //vertex to which the others have to be compared intvec startvertex=polygon[1]; // keep the starting vertex to test, intvec startvertex=polygon[1]; // keep the starting vertex to test, // when the end is reached int endtest;                   // is set to one, when the end is reached int startvertexfound;// is 1, once for some testvertex a candidate // for the next vertex has been found int startvertexfound;// is 1, once for some testvertex a candidate // for the next vertex has been found polygon=delete(polygon,1);    // delete the testvertex intvec v,w; int l=1;  // counts the vertices // the basic idea is that a vertex can be // the basic idea is that a vertex can be // the next one on the boundary if all other vertices // lie to the right of the vector v pointing // lie to the right of the vector v pointing // from the testvertex to this one; this can be tested // by checking if the determinant of the 2x2-matrix // by checking if the determinant of the 2x2-matrix // with first column v and second column the vector w, // pointing from the testvertex to the new vertex, // pointing from the testvertex to the new vertex, // is non-positive; if this is the case for all // new vertices, then the one in consideration is // new vertices, then the one in consideration is // a possible choice for the next vertex on the boundary // and it is stored in naechste; we can then order // and it is stored in naechste; we can then order // the candidates according to their distance from // the testvertex; then they occur on the boundary in that order! v=polygon[i]-testvertex; // points from the testvertex to the ith vertex comparevertices=delete(polygon,i); // we needn't compare v to itself // we should compare v to the startvertex-testvertex; // we should compare v to the startvertex-testvertex; // in the first calling of the loop // this is irrelevant since the difference will be zero; // this is irrelevant since the difference will be zero; // however, later on it will // be vital, since we delete the vertices // be vital, since we delete the vertices // which we have already tested from the list // of all vertices, and when all vertices // of all vertices, and when all vertices // on the boundary have been found we would // therefore find a vertex in the interior // therefore find a vertex in the interior // as candidate; but always testing against // the starting vertex, this can not happen comparevertices[size(comparevertices)+1]=startvertex; comparevertices[size(comparevertices)+1]=startvertex; for (j=1;(j<=size(comparevertices)) and (d<=0);j++) { d=det(D); } if (d<=0) // if all determinants are non-positive, if (d<=0) // if all determinants are non-positive, { // then the ith vertex is a candidate naechste[k]=list(polygon[i],i,scalarproduct(v,v));// we store the vertex, } if (size(naechste)>0) // then a candidate for the next vertex has been found { { startvertexfound=1; // at least once a candidate has been found naechste=sortlist(naechste,3);  // we order the candidates according naechste=sortlist(naechste,3);  // we order the candidates according // to their distance from testvertex; for (j=1;j<=size(naechste);j++) // then we store them in this for (j=1;j<=size(naechste);j++) // then we store them in this { // order in orderedvertices l++; orderedvertices[l]=naechste[j][1]; } testvertex=naechste[size(naechste)][1];  // we store the last one as testvertex=naechste[size(naechste)][1];  // we store the last one as // next testvertex; // store the next corner of NSD minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; naechste=sortlist(naechste,2); // then we reorder the vertices minimisedorderedvertices[size(minimisedorderedvertices)+1]=testvertex; naechste=sortlist(naechste,2); // then we reorder the vertices // according to their position for (j=size(naechste);j>=1;j--) // and we delete them from the vertices } } else // that means either that the vertex was inside the polygon, {    // or that we have reached the last vertex on the boundary else // that means either that the vertex was inside the polygon, {    // or that we have reached the last vertex on the boundary // of the polytope if (startvertexfound==0) // the vertex was in the interior; if (startvertexfound==0) // the vertex was in the interior; { // we delete it and start all over again orderedvertices[1]=polygon[1]; minimisedorderedvertices[1]=polygon[1]; orderedvertices[1]=polygon[1]; minimisedorderedvertices[1]=polygon[1]; testvertex=polygon[1]; startvertex=polygon[1]; polygon=delete(polygon,1); } else // we have reached the last vertex on the boundary of else // we have reached the last vertex on the boundary of { // the polytope and can stop endtest=1; kill naechste; } // test if the first vertex in minimisedorderedvertices // test if the first vertex in minimisedorderedvertices // is on the same line with the second and // the last, i.e. if we started our search in the // the last, i.e. if we started our search in the // middle of a face; if so, delete it v=minimisedorderedvertices[2]-minimisedorderedvertices[1]; minimisedorderedvertices=delete(minimisedorderedvertices,1); } // test if the first vertex in minimisedorderedvertices // test if the first vertex in minimisedorderedvertices // is on the same line with the two // last ones, i.e. if we started our search at the end of a face; // last ones, i.e. if we started our search at the end of a face; // if so, delete it v=minimisedorderedvertices[size(minimisedorderedvertices)-1]-minimisedorderedvertices[1]; proc cyclePoints (list triang,list points,int pt) "USAGE:      cyclePoints(triang,points,pt)  triang,points list, pt int ASSUME:      - points is a list of integer vectors describing the lattice ASSUME:      - points is a list of integer vectors describing the lattice points of a marked polygon; @*           - triang is a list of integer vectors describing a triangulation of the marked polygon in the sense that an integer vector of the form (i,j,k) describes the triangle formed by polygon[i], @*           - triang is a list of integer vectors describing a triangulation of the marked polygon in the sense that an integer vector of the form (i,j,k) describes the triangle formed by polygon[i], polygon[j] and polygon[k]; @*           - pt is an integer between 1 and size(points), singling out a @*           - pt is an integer between 1 and size(points), singling out a lattice point among the marked points PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice points in points which in the triangulation triang are connected to the point points[pt]; the procedure computes all marked points PURPOSE:     consider the convex lattice polygon, say P, spanned by all lattice points in points which in the triangulation triang are connected to the point points[pt]; the procedure computes all marked points in points which lie on the boundary of that polygon, ordered clockwise RETURN:      list, of integer vectors which are the coordinates of the lattice points on the boundary of the above mentioned polygon P, if this polygon is not the empty set (that would be the case if points[pt] is not a vertex of any triangle in the RETURN:      list, of integer vectors which are the coordinates of the lattice points on the boundary of the above mentioned polygon P, if this polygon is not the empty set (that would be the case if points[pt] is not a vertex of any triangle in the triangulation); otherwise return the empty list EXAMPLE:     example cyclePoints;   shows an example" { int i,j; // indices list v;  // saves the indices of lattice points connected to the list v;  // saves the indices of lattice points connected to the // interior point in the triangulation // save all points in triangulations containing pt in v pts[i]=points[v[i]]; } // consider the convex polytope spanned by the points in pts, // consider the convex polytope spanned by the points in pts, // find the points on the // boundary and order them clockwise "EXAMPLE:"; echo=2; // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // with all integer points as markings list points=intvec(1,1),intvec(3,0),intvec(2,0),intvec(1,0), intvec(0,0),intvec(2,1),intvec(0,1),intvec(1,2), intvec(0,2),intvec(0,3); // define a triangulation // define a triangulation list triang=intvec(1,2,5),intvec(1,5,7),intvec(1,7,9),intvec(8,9,10), intvec(1,8,9),intvec(1,2,8); "USAGE:  latticeArea(polygon);   polygon list ASSUME:  polygon is a list of integer vectors in the plane RETURN:  int, the lattice area of the convex hull of the lattice points in RETURN:  int, the lattice area of the convex hull of the lattice points in polygon, i.e. twice the Euclidean area EXAMPLE: example polygonlatticeArea;   shows an example" proc picksFormula (list polygon) "USAGE:  picksFormula(polygon);   polygon list ASSUME:  polygon is a list of integer vectors in the plane and consider their convex hull C RETURN:  list, L of three integersthe ASSUME:  polygon is a list of integer vectors in the plane and consider their convex hull C RETURN:  list, L of three integersthe @*             L[1] : the lattice area of C, i.e. twice the Euclidean area @*             L[2] : the number of lattice points on the boundary of C bdpts=bdpts+abs(gcd(edge[1],edge[2])); } // Pick's formula says that the lattice area A, the number g of interior // Pick's formula says that the lattice area A, the number g of interior // points and // the number b of boundary points are connected by the formula: A=b+2g-2 "USAGE:  ellipticNF(polygon);   polygon list ASSUME:  polygon is a list of integer vectors in the plane such that their convex hull C has precisely one interior lattice point, i.e. C is the convex hull C has precisely one interior lattice point, i.e. C is the Newton polygon of an elliptic curve PURPOSE: compute the normal form of the polygon with respect to the unimodular PURPOSE: compute the normal form of the polygon with respect to the unimodular affine transformations T=A*x+v; there are sixteen different normal forms (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, 238--250.) RETURN:  list, L such that @*             L[1] : list whose entries are the vertices of the normal form of @*             L[1] : list whose entries are the vertices of the normal form of the polygon @*             L[2] : the matrix A of the unimodular transformation @*             L[3] : the translation vector v of the unimodular transformation @*             L[4] : list such that the ith entry is the image of polygon[i] @*             L[4] : list such that the ith entry is the image of polygon[i] under the unimodular transformation T EXAMPLE: example ellipticNF;   shows an example" intvec trans;    // stores the vector by which we have to translate the polygon intmat A[2][2];  // stores the matrix by which we have to transform the polygon matrix M[3][3];  // stores the projective coordinates of the points matrix M[3][3];  // stores the projective coordinates of the points // which are to be transformed matrix N[3][3];  // stores the projective coordinates of the points to matrix N[3][3];  // stores the projective coordinates of the points to // which M is to be transformed intmat T[3][3];  // stores the unimodular affine transformation in intmat T[3][3];  // stores the unimodular affine transformation in // projective form // add the second point of pg once again at the end pg=insert(pg,pg[2],size(pg)); // if there is only one edge which has the maximal number of lattice points, // if there is only one edge which has the maximal number of lattice points, // then M should be: M=pg[max],1,pg[max+1],1,pg[max+2],1; M=pg[max],1,pg[max+1],1,pg[max+2],1; // the orientation of the polygon matters A=pg[max-1]-pg[max],pg[max+1]-pg[max]; A=pg[max-1]-pg[max],pg[max+1]-pg[max]; if (det(A)==4) { { max++; } } M=pg[max],1,pg[max+1],1,pg[max+2],1; N=0,1,1,1,2,1,2,1,1; // the vertices of the normal form are nf[1]; // it has been transformed by the unimodular affine transformation A*x+v // it has been transformed by the unimodular affine transformation A*x+v // with matrix A nf[2]; "USAGE:  ellipticNFDB(n[,#]);   n int, # list ASSUME:  n is an integer between 1 and 16 PURPOSE: this is a database storing the 16 normal forms of planar polygons with PURPOSE: this is a database storing the 16 normal forms of planar polygons with precisely one interior point up to unimodular affine transformations @*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons @*       (see e.g. Bjorn Poonen, Fernando Rodriguez-Villegas: Lattice Polygons and the number 12.  Amer. Math. Monthly  107  (2000),  no. 3, 238--250.) RETURN:  list, L such that @*             L[1] : list whose entries are the vertices of the nth normal form @*             L[2] : list whose entries are all the lattice points of the nth normal form @*             L[3] : only present if the optional parameter # is present, and then it is a polynomial in the variables (x,y) whose @*             L[1] : list whose entries are the vertices of the nth normal form @*             L[2] : list whose entries are all the lattice points of the nth normal form @*             L[3] : only present if the optional parameter # is present, and then it is a polynomial in the variables (x,y) whose Newton polygon is the nth normal form NOTE:    the optional parameter is only allowed if the basering has the NOTE:    the optional parameter is only allowed if the basering has the variables x and y EXAMPLE: example ellipticNFDB;   shows an example" proc polymakeKeepTmpFiles (int i) "USAGE:  polymakeKeepTmpFiles(int i);   i int PURPOSE: some procedures create files in the directory /tmp which are used for PURPOSE: some procedures create files in the directory /tmp which are used for computations with polymake respectively topcom; these will be removed when the corresponding procedure is left; however, it might be when the corresponding procedure is left; however, it might be desireable to keep them for further computations with either polymake or topcom; this can be achieved by this procedure; call the procedure as: static proc scalarproduct (intvec w,intvec v) "USAGE:      scalarproduct(w,v); w,v intvec ASSUME:      w and v are integer vectors of the same length ASSUME:      w and v are integer vectors of the same length RETURN:      int, the scalarproduct of v and w NOTE:        the procedure is called by findOrientedBoundary" { int m=nrows(M); } else { return(""); } if (i==1) k++; } else else { stop=1; k++; } else else { stop=1; static proc polygonToCoordinates (list points) "USAGE:      polygonToCoordinates(points);   points list ASSUME:      points is a list of integer vectors each of size two describing the marked points of a convex lattice polygon like the output of ASSUME:      points is a list of integer vectors each of size two describing the marked points of a convex lattice polygon like the output of polygonDB RETURN:      list, the first entry is a string representing the coordinates RETURN:      list, the first entry is a string representing the coordinates corresponding to the latticpoints seperated by commata the second entry is a list where the ith entry is a string representing the coordinate of corresponding to the ith lattice point the third entry is the latex format of the the second entry is a list where the ith entry is a string representing the coordinate of corresponding to the ith lattice point the third entry is the latex format of the first entry NOTE:        the procedure is called by fan"
• ## Singular/LIB/presolve.lib

 r2c3a5d /////////////////////////////////////////////////////////////////////////////// version="$Id: presolve.lib,v 1.29 2009-04-06 09:17:01 seelisch Exp$"; version="$Id: presolve.lib,v 1.30 2009-04-14 12:00:14 Singular Exp$"; category="Symbolic-numerical solving"; info=" if ( size(#)!=0 ) {  n=#[1]; } ideal maxi,rest = maxideal(1),0; if ( n < nvars(BAS) ) { rest = maxi[n+1..nvars(BAS)]; if ( n < nvars(BAS) ) { rest = maxi[n+1..nvars(BAS)]; } attrib(rest,"isSB",1); // which do not contain elements not to be eliminated //ideal id = interred(i); //## gmg, gendert 9/2008: interred sehr lange z.B. bei Leonard1 in normal, //ideal id = interred(i); //## gmg, gendert 9/2008: interred sehr lange z.B. bei Leonard1 in normal, //daher interred ersetzt durch: std nur auf linearpart angewendet //Ordnung muss global sein, sonst egal (da Lin affin linear) //--------------- replace ordering by dp if it is not global ----------------- if ( ord_test(BAS) <= 0 ) { intvec V; { intvec V; V[n]=0; V=V+1;                          //weights for dp ordering gnirlist[3] = list("dp",V), g32; ideal i = imap(BAS,i); } list  Lin = linearpart(i); ideal lin = std(Lin[1]);          //SB of ideal generated by polys of i //------------- check for special case of unit ideal and return --------------- int check; if( lin[1] == 1 ) { check = 1; } else if( lin[1] == 1 ) { check = 1; } else { for (ii=1; ii<=size(id); ii++ ) { if ( id[ii] == 1 ) { { check = 1; break; } /* Alte Version mit interred: // Then go to ring newBAS with ordering c,dp(n) and create a matrix with // size(k1) colums and 2 rows, such that if [f1,f2] is a column of M then f1+f2 // is one of the polys of lin containing a pure degree 1 part and f1 is this // part interreduce this matrix (i.e. Gauss elimination on linear part, with // Then go to ring newBAS with ordering c,dp(n) and create a matrix with // size(k1) colums and 2 rows, such that if [f1,f2] is a column of M then f1+f2 // is one of the polys of lin containing a pure degree 1 part and f1 is this // part interreduce this matrix (i.e. Gauss elimination on linear part, with // rest transformed accordingly). //Ist jetzt durch direkte Substitution gemacht (schneller!) //ideal k12 = k1,k2; //matrix M = matrix(k12,2,kk);     //degree 1 part is now in row 1 //M = interred(M); //### interred zu teuer, muss nicht sein. Wenn interred angewendet //M = interred(M); //### interred zu teuer, muss nicht sein. Wenn interred angewendet //werden soll, vorher in Ring mit Ordnung (c,dp) wechseln! //Abfrage:  if( ordstr(BAS) != "c,dp("+string(n)+")" ) -z ergibt ich auch i[2]-z*i[3] mit option(redThrough) statt interred kann man hier auch NF(i,i[3])+i[3] verwenden hier lifert elimpart(i) 2 Substitutionen (x,y) elimpart(interred(i)) hier lifert elimpart(i) 2 Substitutionen (x,y) elimpart(interred(i)) aber 3 (x,y,z) Da interred oder NF aber die Laenge der polys vergroessern kann, nicht gemacht //since lin1 != 0 there are candidates for substituting variables lin2 = lin - lin1;      //difference as matrix lin2 = lin - lin1;      //difference as matrix // rest of lin, part of pure degree 1 substracted from each generator of lin } } //Now each !=0 generator of lin2 contains only constant terms or terms of //Now each !=0 generator of lin2 contains only constant terms or terms of //degree >= 2, hence lin 2 can never be used for further substitutions //We have: lin = ideal(matrix(k1)+matrix(k2)), lin2 ideal kin = matrix(k1)+matrix(k2); ideal kin = matrix(k1)+matrix(k2); //kin = polys of lin which contained a pure degree 1 part. kin = simplify(kin,2); int count=1; while ( count != 0 ) { { count = 0; for ( ii=1; ii<=n; ii++  )    //start direct substitution of var(ii) { //we look for the shortest candidate to substitute var(ii) if ( cand == 0 ) { if ( cand == 0 ) { cand = kin[kk];  //candidate for substituting var(ii) } } else { if ( size(kin[kk]) < size(cand) ) { cand = kin[kk]; if ( size(kin[kk]) < size(cand) ) { cand = kin[kk]; } } } } } if ( cand != 0 ) { neva[ii] = 0; sub = sub+kip;     //poly defining substituion //## gmg: gendert 08/2008, map durch subst ersetzt //## gmg: gendert 08/2008, map durch subst ersetzt //(viel schneller) vip = var(ii) - kip;  //poly to be substituted } } lin = kin+lin; for( ii=1; ii<=size(lin); ii++ ) { } for( ii=1; ii<=n; ii++ ) for( ii=1; ii<=n; ii++ ) { for( kk=1; kk<=size(eva); kk++ )
• ## Singular/LIB/random.lib

 r2c3a5d //(GMG/BM, last modified 22.06.96) /////////////////////////////////////////////////////////////////////////////// version="$Id: random.lib,v 1.18 2009-03-30 18:36:35 motsak Exp$"; version="$Id: random.lib,v 1.19 2009-04-14 12:00:14 Singular Exp$"; category="General purpose"; info=" proc sparseHomogIdeal (int k, int u, list #) "USAGE:   sparseid(k,u[,o,p,b]);  k,u,o,p,b integers RETURN:  ideal having k homogeneous generators, each of random degree in the interval [u,o], p percent of terms in degree d are 0, the remaining have random coefficients in the interval [1,b], (default: o=u, p=75, RETURN:  ideal having k homogeneous generators, each of random degree in the interval [u,o], p percent of terms in degree d are 0, the remaining have random coefficients in the interval [1,b], (default: o=u, p=75, b=30000) EXAMPLE: example sparseid; shows an example { id = maxideal(random(u, o)); // monomial basis of some degree m = sparsemat(size(id),1,p,b); // random coefficients m = sparsemat(size(id),1,p,b); // random coefficients i[ii] = (matrix(id)*m)[1,1]; }
• ## Singular/LIB/ratgb.lib

 r2c3a5d ////////////////////////////////////////////////////////////////////////////// version="$Id: ratgb.lib,v 1.14 2009-02-21 15:26:42 levandov Exp$"; version="$Id: ratgb.lib,v 1.15 2009-04-14 12:00:15 Singular Exp$"; category="Noncommutative"; info=" va = L3[w][2]; for(z=1;z<=nvars(save)-is;z++) { vb[z] = va[is+z]; { vb[z] = va[is+z]; } tmp3[1] = "a"; setring A; IAppel1; def F1 = ratstd(IAppel1,2); lead(pGBid); def F1 = ratstd(IAppel1,2); lead(pGBid); setring F1; rGBid; } setring A; IAppel2; def F1 = ratstd(IAppel2,2); lead(pGBid); def F1 = ratstd(IAppel2,2); lead(pGBid); setring F1; rGBid; } setring A; IAppel4; def F1 = ratstd(IAppel4,2); lead(pGBid); def F1 = ratstd(IAppel4,2); lead(pGBid); setring F1; rGBid; }
• ## Singular/LIB/sing4ti2.lib

 r2c3a5d /////////////////////////////////////////////////////////////////// version="$Id: sing4ti2.lib,v 1.2 2009-04-07 16:18:06 seelisch Exp$"; version="$Id: sing4ti2.lib,v 1.3 2009-04-14 12:00:15 Singular Exp$"; category="Commutative Algebra"; info=" @*    the returned result REQUIRES: External programs 4ti2, sed and awk to be installed REQUIRES: External programs 4ti2, sed and awk to be installed PROCEDURES: //---------------------------------------------------------------------- // calling 4ti2 and converting output // calling 4ti2 and converting output // Singular's string is too clumsy for this, hence we first prepare // using standard unix commands //---------------------------------------------------------------------- j=system("sh","markov sing4ti2"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print $0;}\' sing4ti2.mar | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g|sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print$0;}\' sing4ti2.mar | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g|sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); if(!defined(keepfiles)) { j=system("sh",("rm -f sing4ti2.mar sing4ti2."+fileending)); } } //---------------------------------------------------------------------- // reading output of 4ti2 { if(erglist[2+(i-1)*erglist[2]+j]>=0) { { //--- positive exponents temppol1=temppol1*(var(j)^erglist[2+(i-1)*erglist[2]+j]); } } toric=toric,temppol1-temppol2; toric=toric,temppol1-temppol2; } //--- get rid of leading entry 0; //---------------------------------------------------------------------- // calling 4ti2 and converting output // calling 4ti2 and converting output // Singular's string is too clumsy for this, hence we first prepare // using standard unix commands //---------------------------------------------------------------------- j=system("sh","graver sing4ti2"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print $0;}\' sing4ti2.gra | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g |sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print$0;}\' sing4ti2.gra | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g |sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); if(!defined(keepfiles)) { j=system("sh",("rm -f sing4ti2.gra sing4ti2."+fileending)); } } //---------------------------------------------------------------------- // reading output of 4ti2 { if(erglist[2+(i-1)*erglist[2]+j]>=0) { { //--- positive exponents temppol1=temppol1*(var(j)^erglist[2+(i-1)*erglist[2]+j]); } } toric=toric,temppol1-temppol2; toric=toric,temppol1-temppol2; } //--- get rid of leading entry 0; @*       - number of variables of basering equals number of columns of A @*         (for ker(A)) resp. of rows of A (for Im(A)) CREATE:  temporary files sing4ti2.mat, sing4ti2.lat, sing4ti2.mar CREATE:  temporary files sing4ti2.mat, sing4ti2.lat, sing4ti2.mar @*       in the current directory (I/O files for communication with 4ti2) NOTE:    input rules for 4ti2 also apply to input to this procedure //---------------------------------------------------------------------- // calling 4ti2 and converting output // calling 4ti2 and converting output // Singular's string is too clumsy for this, hence we first prepare // using standard unix commands //---------------------------------------------------------------------- j=system("sh","hilbert sing4ti2"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print $0;}\' sing4ti2.hil | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g |sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); j=system("sh","awk \'BEGIN{ORS=\",\";}{print$0;}\' sing4ti2.hil | sed s/[\\\ \\\t\\\v\\\f]/,/g | sed s/,+/,/g |sed s/,,/,/g|sed s/,,/,/g > sing4ti2.converted"); if(!defined(keepfiles)) { j=system("sh",("rm -f sing4ti2.hil sing4ti2."+fileending)); } } //---------------------------------------------------------------------- // reading output of 4ti2 { if(erglist[2+(i-1)*erglist[2]+j]>=0) { { //--- positive exponents temppol1=temppol1*(var(j)^erglist[2+(i-1)*erglist[2]+j]); } } toric=toric,temppol1-temppol2; toric=toric,temppol1-temppol2; } //--- get rid of leading entry 0;
• ## Singular/LIB/teachstd.lib

 r2c3a5d //GMG, last modified 28.9.01 /////////////////////////////////////////////////////////////////////////////// version="$Id: teachstd.lib,v 1.11 2009-04-06 12:39:02 seelisch Exp$"; version="$Id: teachstd.lib,v 1.12 2009-04-14 12:00:15 Singular Exp$"; category="Teaching"; info=" if( size(#) > 0 ) {// "size(#): ", size(#);   "typeof(#[1]): ", typeof(#[1]); if( typeof(#[1]) == "int" ) {// "#[1] = int ", #[1]; if( #[1] > 0 ) { { return(0); }
• ## Singular/LIB/triang.lib

 r2c3a5d //last change: 13.02.2001 (Eric Westenberger) ////////////////////////////////////////////////////////////////////////////// version="$Id: triang.lib,v 1.13 2009-04-06 09:17:01 seelisch Exp$"; version="$Id: triang.lib,v 1.14 2009-04-14 12:00:15 Singular Exp$"; category="Symbolic-numerical solving"; info=" If i = 2, then each polynomial of the triangular systems is factorized. NOTE:    Algorithm of Moeller (see: Moeller, H.M.: On decomposing systems of polynomial equations with finitely many solutions, Appl. Algebra Eng. NOTE:    Algorithm of Moeller (see: Moeller, H.M.: On decomposing systems of polynomial equations with finitely many solutions, Appl. Algebra Eng. Commun. Comput. 4, 217 - 230, 1993). EXAMPLE: example triangM; shows an example
• ## Singular/LIB/tropical.lib

 r2c3a5d version="$Id: tropical.lib,v 1.14 2009-04-08 12:42:19 seelisch Exp$"; version="$Id: tropical.lib,v 1.15 2009-04-14 12:00:15 Singular Exp$"; category="Tropical Geometry"; info=" @*               Thomas Markwig,  email: keilen@mathematik.uni-kl.de WARNING: WARNING: - tropicalLifting will only work with LINUX and if in addition gfan is installed. @*- drawTropicalCurve and drawTropicalNewtonSubdivision will only display the @*  tropical curve with LINUX and if in addition latex and kghostview @*- drawTropicalCurve and drawTropicalNewtonSubdivision will only display the @*  tropical curve with LINUX and if in addition latex and kghostview @*  are installed. @*- For tropicalLifting in the definition of the basering the parameter t @*- For tropicalLifting in the definition of the basering the parameter t @*  from the Puiseux series field C{{t}} must be defined as a variable, @*  while for all other procedures it must be defined as a parameter. THEORY: Fix some base field K and a bunch of lattice points v0,...,vm in the integer lattice Z^n, then this defines a toric variety as the closure of (K*)^n in the projective space P^m, where the torus is embedded via the map sending a Fix some base field K and a bunch of lattice points v0,...,vm in the integer lattice Z^n, then this defines a toric variety as the closure of (K*)^n in the projective space P^m, where the torus is embedded via the map sending a point x in (K*)^n to the point (x^v0,...,x^vm). The generic hyperplane sections are just the images of the hypersurfaces The generic hyperplane sections are just the images of the hypersurfaces in (K*)^n defined by the polynomials f=a0*x^v0+...+am*x^vm=0. Some properties of these hypersurfaces can be studied via tropicalisation. For this we suppose that K=C{{t}} is the field of Puiseux series over the of these hypersurfaces can be studied via tropicalisation. For this we suppose that K=C{{t}} is the field of Puiseux series over the field of complex numbers (or any other field with a valuation into the real numbers). One associates to the hypersurface given by f=a0*x^v0+...+am*x^vm numbers). One associates to the hypersurface given by f=a0*x^v0+...+am*x^vm the tropical hypersurface defined by the tropicalisation trop(f)=min{val(a0)+,...,val(am)+}. trop(f)=min{val(a0)+,...,val(am)+}. Here, denotes the standard scalar product of the integer vector v in Z^n with the vector x=(x1,...,xn) of variables, so that trop(f) is a piecewise linear function on R^n. The corner locus of this function (i.e. the points at which the minimum is attained a least twice) is the tropical hypersurface defined by trop(f). The theorem of Newton-Kapranov states that this tropical hypersurface is the same as if one computes pointwise the valuation of the hypersurface given by f. The analogue holds true if one replaces one equation f by an ideal I. A constructive proof of the theorem is given by an adapted version of the Newton-Puiseux algorithm. The hard part is to find a point in the variety over C{{t}} which corresponds to a given point in the linear function on R^n. The corner locus of this function (i.e. the points at which the minimum is attained a least twice) is the tropical hypersurface defined by trop(f). The theorem of Newton-Kapranov states that this tropical hypersurface is the same as if one computes pointwise the valuation of the hypersurface given by f. The analogue holds true if one replaces one equation f by an ideal I. A constructive proof of the theorem is given by an adapted version of the Newton-Puiseux algorithm. The hard part is to find a point in the variety over C{{t}} which corresponds to a given point in the tropical variety. It is the purpose of this library to provide basic means to deal with tropical varieties. Of course we cannot represent the field of Puiseux series over C in its full strength, however, in order to compute interesting examples it will be sufficient to replace the complex numbers C by the rational numbers Q and to replace Puiseux series in t by rational functions in t, i.e. we replace C{{t}} by Q(t), or sometimes even by Q[t]. It is the purpose of this library to provide basic means to deal with tropical varieties. Of course we cannot represent the field of Puiseux series over C in its full strength, however, in order to compute interesting examples it will be sufficient to replace the complex numbers C by the rational numbers Q and to replace Puiseux series in t by rational functions in t, i.e. we replace C{{t}} by Q(t), or sometimes even by Q[t]. Note, that this in particular forbids rational exponents for the t's. Moreover, in Singular no negative exponents of monomials are allowed, so that the integer vectors vi will have to have non-negative entries. Shifting all exponents by a fixed integer vector does not change the tropicalisation nor does it change the toric variety. Thus this does not Moreover, in Singular no negative exponents of monomials are allowed, so that the integer vectors vi will have to have non-negative entries. Shifting all exponents by a fixed integer vector does not change the tropicalisation nor does it change the toric variety. Thus this does not cause any restriction. If, however, for some reason you prefer to work with general vi, then you have to pass right away to the tropicalisation of the equations, whereever If, however, for some reason you prefer to work with general vi, then you have to pass right away to the tropicalisation of the equations, whereever this is allowed -- these are linear polynomials where the constant coefficient corresponds to the valuation of the original coefficient and where the non-constant coefficient correspond to the exponents of the monomials, thus they may be rational numbers respectively negative numbers: corresponds to the valuation of the original coefficient and where the non-constant coefficient correspond to the exponents of the monomials, thus they may be rational numbers respectively negative numbers: 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}. The main tools provided in this library are as follows: @*  - tropicalLifting    implements the constructive proof of the Theorem of Newton-Kapranov and constructs a point in the variety over C{{t}} corresponding to a given point in the corresponding tropical variety associated to an ideal I; the generators of I have to be in the polynomial ring Q[t,x1,...,xn] considered as a subring of C{{t}}[x1,...,xn]; a solution will be constructed up to given order; note that several @*  - tropicalLifting    implements the constructive proof of the Theorem of Newton-Kapranov and constructs a point in the variety over C{{t}} corresponding to a given point in the corresponding tropical variety associated to an ideal I; the generators of I have to be in the polynomial ring Q[t,x1,...,xn] considered as a subring of C{{t}}[x1,...,xn]; a solution will be constructed up to given order; note that several field extensions of Q might be necessary throughout the intermediate computations; the procedures use the external program gfan @*  - drawTropicalCurve  visualises a tropical plane curve either given by a polynomial in Q(t)[x,y] or by a list of linear polynomials of the form ax+by+c with a,b in Z and c @*  - drawTropicalCurve  visualises a tropical plane curve either given by a polynomial in Q(t)[x,y] or by a list of linear polynomials of the form ax+by+c with a,b in Z and c in Q; latex must be installed on your computer @*  - tropicalJInvariant computes the tropical j-invaiant of a tropical @*  - tropicalJInvariant computes the tropical j-invaiant of a tropical elliptic curve @*  - jInvariant         computes the j-invariant of an elliptic curve @*  - weierstrassForm     computes the Weierstrass form of an elliptic curve @*  - weierstrassForm     computes the Weierstrass form of an elliptic curve PROCEDURES FOR TROPICAL LIFTING: tropicalLifting          computes a point in the tropical variety tropicalLifting          computes a point in the tropical variety displayTropicalLifting   displays the output of tropicalLifting tropicalise        computes the tropicalisation of a polynomial tropicaliseSet     computes the tropicalisation several polynomials tInitialForm       computes the tInitial form of a poly in Q[t,x_1,...,x_n] tInitialForm       computes the tInitial form of a poly in Q[t,x_1,...,x_n] tInitialIdeal      computes the tInitial ideal of an ideal in Q[t,x_1,...,x_n] initialForm        computes the initial form of poly in Q[x_1,...,x_n] initialIdeal       computes the initial ideal of an ideal in Q[x_1,...,x_n] initialForm        computes the initial form of poly in Q[x_1,...,x_n] initialIdeal       computes the initial ideal of an ideal in Q[x_1,...,x_n] PROCEDURES FOR LATEX CONVERSION: texNumber          outputs the texcommand for the leading coefficient of poly texPolynomial      outputs the texcommand for the polynomial poly texPolynomial      outputs the texcommand for the polynomial poly texMatrix          outputs the texcommand for the matrix texDrawBasic       embeds output of texDrawTropical in a texdraw environment texDrawTropical    computes the texdraw commands for a tropical curve texDrawNewtonSubdivision   computes texdraw commands for a Newton subdivision texDrawNewtonSubdivision   computes texdraw commands for a Newton subdivision texDrawTriangulation       computes texdraw commands for a triangulation radicalMemberShip     checks radical membership tInitialFormPar       computes the t-initial form of poly in Q(t)[x_1,...,x_n] tInitialFormParMax    same as tInitialFormPar, but uses maximum tInitialFormParMax    same as tInitialFormPar, but uses maximum solveTInitialFormPar  displays approximated solution of a 0-dim ideal detropicalise         computes the detropicalisation of a linear form dualConic             computes the dual of an affine plane conic dualConic             computes the dual of an affine plane conic parameterSubstitute   substitutes in the poly the parameter t by t^N tropicalSubst         makes certain substitutions in a tropical polynomial /// - eliminatecomponents /// - findzerosAndBasictransform /// - ordermaximalideals /// - ordermaximalideals /// - verticesTropicalCurve /// - bunchOfLines /////////////////////////////////////////////////////////////////////////////// /// Procedures concerned with tropical parametrisation /// Procedures concerned with tropical parametrisation /////////////////////////////////////////////////////////////////////////////// proc tropicalLifting (ideal i,intvec w,int ordnung,list #) "USAGE:  tropicalLifting(i,w,ord[,opt]); i ideal, w intvec, ord int, opt string ASSUME:  - i is an ideal in Q[t,x_1,...,x_n], w=(w_0,w_1,...,w_n) and (w_1/w_0,...,w_n/w_0) is in the tropical variety of i, and ord is the order up to which a point in V(i) over Q{{t}} lying over (w_1/w_0,...,w_n/w_0) shall be computed; ASSUME:  - i is an ideal in Q[t,x_1,...,x_n], w=(w_0,w_1,...,w_n) and (w_1/w_0,...,w_n/w_0) is in the tropical variety of i, and ord is the order up to which a point in V(i) over Q{{t}} lying over (w_1/w_0,...,w_n/w_0) shall be computed; w_0 may NOT be ZERO @*       - the basering should not have any parameters on its own and it should have a global monomial ordering, @*       - the basering should not have any parameters on its own and it should have a global monomial ordering, e.g. ring r=0,(t,x(1..n)),dp; @*       - the first variable of the basering will be treated as the @*       - the first variable of the basering will be treated as the parameter t in the Puiseux series field @*       - the optional parameter opt should be one or more strings among @*       - the optional parameter opt should be one or more strings among the following: @*         'isZeroDimensional'  : the dimension i is zero (not to be checked); @*         'isPrime'            : the ideal is prime over Q(t)[x_1,...,x_n] @*         'isPrime'            : the ideal is prime over Q(t)[x_1,...,x_n] (not to be checked); @*         'isInTrop'           : (w_1/w_0,...,w_n/w_0) is in the tropical @*         'isInTrop'           : (w_1/w_0,...,w_n/w_0) is in the tropical variety (not to be checked); @*         'oldGfan'            : uses gfan version 0.2.1 or less @*         'findAll'            : find all solutions of a zero-dimensional @*         'oldGfan'            : uses gfan version 0.2.1 or less @*         'findAll'            : find all solutions of a zero-dimensional ideal over (w_1/w_0,...,w_n/w_0) @*         'noAbs'              : do NOT use absolute primary decomposition RETURN:  IF THE OPTION 'findAll' WAS NOT SET THEN: @*       list, containing one lifting of the given point (w_1/w_0,...,w_n/w_0) in the tropical variety of i to a point in V(i) over Puiseux in the tropical variety of i to a point in V(i) over Puiseux series field up to the first ord terms; more precisely: @*             IF THE OPTION 'noAbs' WAS NOT SET, THEN: @*       IF THE OPITON 'findAll' WAS SET, THEN: @*       list, containing ALL liftings of the given point ((w_1/w_0,...,w_n/w_0) in the tropical variety of i to a point in V(i) over Puiseux series field up to the first ord terms, if the ideal is in the tropical variety of i to a point in V(i) over Puiseux series field up to the first ord terms, if the ideal is zero-dimensional over Q{{t}}; more precisely, each entry of the list is a list l as computed more precisely, each entry of the list is a list l as computed if  'findAll' was NOT set @*       WE NOW DESCRIBE THE LIST ENTRIES IF 'findAll' WAS NOT SET: @*       - the ring l[1] contains an ideal LIFT, which contains @*       - the ring l[1] contains an ideal LIFT, which contains a point in V(i) lying over w up to the first ord terms; @*       - and if the integer l[2] is N then t has to be replaced by t^1/N @*       - and if the integer l[2] is N then t has to be replaced by t^1/N in the lift, or alternatively replace t by t^N in the defining ideal @*       - if the k+1st entry of l[3] is  non-zero, then the kth component of LIFT has to be multiplied t^(-l[3][k]/l[3][1]) AFTER substituting t @*       - if the k+1st entry of l[3] is  non-zero, then the kth component of LIFT has to be multiplied t^(-l[3][k]/l[3][1]) AFTER substituting t by t^1/N @*       - unless the option 'noResubst' was set, the kth entry of list l[4] @*       - unless the option 'noResubst' was set, the kth entry of list l[4] is a string which represents the kth generator of the ideal i where the coordinates have been replaced by the result the ideal i where the coordinates have been replaced by the result of the lift; the t-order of the kth entry should in principle be larger than the the t-order of the kth entry should in principle be larger than the t-degree of LIFT @*       - if the option 'noAbs' was set, then the string in l[5] defines a maximal ideal in the field Q[X(1),...,X(k)], where X(1),...,X(k) @*       - if the option 'noAbs' was set, then the string in l[5] defines a maximal ideal in the field Q[X(1),...,X(k)], where X(1),...,X(k) are the parameters of the ring in l[1]; the basefield of the ring in l[1] should be considered modulo this the basefield of the ring in l[1] should be considered modulo this ideal REMARK:  - it is best to use the procedure displayTropicalLifting to REMARK:  - it is best to use the procedure displayTropicalLifting to display the result @*       - the option 'findAll' cannot be used if 'noAbs' is set @*       - if the parameter 'findAll' is set AND the ideal i is zero-dimensional in Q{{t}}[x_1,...,x_n] then ALL points in V(i) lying over w are in Q{{t}}[x_1,...,x_n] then ALL points in V(i) lying over w are computed up to order ord; if the ideal is not-zero dimenisonal, then only the points in the ideal after cutting down to dimension zero will be computed @*       - the procedure requires that the program GFAN is installed on your computer; if you have GFAN version less than 0.3.0 then you must computer; if you have GFAN version less than 0.3.0 then you must use the optional parameter 'oldGfan' @*       - the procedure requires the Singular procedure absPrimdecGTZ to be @*       - the procedure requires the Singular procedure absPrimdecGTZ to be present in the package primdec.lib, unless the option 'noAbs' is set; but even if absPrimdecGTZ is present it might be necessary to set the option 'noAbs' in order to avoid the costly absolute primary decomposition; the side effect is that the field extension which is but even if absPrimdecGTZ is present it might be necessary to set the option 'noAbs' in order to avoid the costly absolute primary decomposition; the side effect is that the field extension which is computed throughout the recursion might need more than one parameter to be described @*       - since Q is infinite, the procedure finishes with probability one @*       - you can call the procedure with Z/pZ as base field instead of Q, @*       - you can call the procedure with Z/pZ as base field instead of Q, but there are some problems you should be aware of: @*         + the Puiseux series field over the algebraic closure of Z/pZ is NOT algebraicall closed, and thus there may not exist a point in V(i) over the Puiseux series field with the desired valuation; @*         + the Puiseux series field over the algebraic closure of Z/pZ is NOT algebraicall closed, and thus there may not exist a point in V(i) over the Puiseux series field with the desired valuation; so there is no chance that the procedure produced a sensible output - e.g. if i=tx^p-tx-1 @*         + if the dimension of i over Z/pZ(t) is not zero the process of reduction to zero might not work if the characteristic is small - e.g. if i=tx^p-tx-1 @*         + if the dimension of i over Z/pZ(t) is not zero the process of reduction to zero might not work if the characteristic is small and you are unlucky @*         + the option 'noAbs' has to be used since absolute primary @*         + the option 'noAbs' has to be used since absolute primary decomposition in Singular only works in characteristic zero @*       - the basefield should either be Q or Z/pZ for some prime p; field extensions will be computed if necessary; if you need parameters or field extensions from the beginning they should rather be simulated as variables possibly adding their relations to @*       - the basefield should either be Q or Z/pZ for some prime p; field extensions will be computed if necessary; if you need parameters or field extensions from the beginning they should rather be simulated as variables possibly adding their relations to the ideal; the weights for the additional variables should be zero EXAMPLE: example tropicalLifting;   shows an example" noabs=1; } // this option is not documented -- it prevents the execution of gfan and // just asks for wneu to be inserted -- it can be used to check problems // with the precedure without calling gfan, if wneu is know from previous // this option is not documented -- it prevents the execution of gfan and // just asks for wneu to be inserted -- it can be used to check problems // with the precedure without calling gfan, if wneu is know from previous // computations if (#[j]=="noGfan") } } // if the basering has characteristic not equal to zero, // if the basering has characteristic not equal to zero, // then absolute factorisation // is not available, and thus we need the option noAbs { Error("The first coordinate of your input w must be NON-ZERO, since it is a DENOMINATOR!"); } } // if w_0<0, then replace w by -w, so that the "denominator" w_0 is positive if (w[1]<0) } intvec prew=w; // stores w for later reference // for our computations, w[1] represents the weight of t and this // for our computations, w[1] represents the weight of t and this // should be -w_0 !!! w[1]=-w[1]; w[1]=-1; } // if some entry of w is positive, we have to make a transformation, // if some entry of w is positive, we have to make a transformation, // which moves it to something non-positive for (j=2;j<=nvars(basering);j++) { variablen=variablen+var(j); } } map GRUNDPHI=BASERING,t,variablen; ideal i=GRUNDPHI(i); // compute the initial ideal of i and test if w is in the tropical // variety of i // compute the initial ideal of i and test if w is in the tropical // variety of i // - the last entry 1 only means that t is the last variable in the ring ideal ini=tInitialIdeal(i,w,1); if (isintrop==0) // test if w is in trop(i) only if isInTrop has not been set { { poly product=1; for (j=1;j<=nvars(basering)-1;j++) int dd=dim(i); setring GRUNDRING; // if the dimension is not zero, we cut the ideal down to dimension zero // if the dimension is not zero, we cut the ideal down to dimension zero // and compute the // t-initial ideal of the new ideal at the same time if(dd!=0) { // the procedurce cutdown computes a new ring, in which there lives a // the procedurce cutdown computes a new ring, in which there lives a // zero-dimensional // ideal which has been computed by cutting down the input with // ideal which has been computed by cutting down the input with // generic linear forms // of the type x_i1-p_1,...,x_id-p_d for some polynomials // p_1,...,p_d not depending // on the variables x_i1,...,x_id; that way we have reduced // of the type x_i1-p_1,...,x_id-p_d for some polynomials // p_1,...,p_d not depending // on the variables x_i1,...,x_id; that way we have reduced // the number of variables by dd !!! // the new zero-dimensional ideal is called i, its t-initial // the new zero-dimensional ideal is called i, its t-initial // ideal (with respect to // the new w=CUTDOWN[2]) is ini, and finally there is a list // repl in the ring // the new w=CUTDOWN[2]) is ini, and finally there is a list // repl in the ring // which contains at the polynomial p_j at position i_j and //a zero otherwise; list liftrings; // will contain the final result // if the procedure is called without 'findAll' then it may happen, that no // proper solution is found when dd>0; in that case we have // proper solution is found when dd>0; in that case we have // to start all over again; // this is controlled by the while-loop // compute the liftrings by resubstitution kk=1;  // counts the liftrings int isgood;  // test in the non-zerodimensional case int isgood;  // test in the non-zerodimensional case // if the result has the correct valuation for (jj=1;jj<=size(TP);jj++) { // the list TP contains as a first entry the ring over which the // tropical parametrisation // the list TP contains as a first entry the ring over which the // tropical parametrisation // of the (possibly cutdown ideal) i lives def LIFTRING=TP[jj][1]; // if the dimension of i originally was not zero, // if the dimension of i originally was not zero, // then we have to fill in the missing // parts of the parametrisation if (dd!=0) { // we need a ring where the parameters X_1,...,X_k // we need a ring where the parameters X_1,...,X_k // from LIFTRING are present, // and where also the variables of CUTDOWNRING live execute("ring REPLACEMENTRING=("+charstr(LIFTRING)+"),("+varstr(CUTDOWNRING)+"),dp;"); list repl=imap(CUTDOWNRING,repl); // get the replacement rules list repl=imap(CUTDOWNRING,repl); // get the replacement rules // from CUTDOWNRING ideal PARA=imap(LIFTRING,PARA);   // get the zero-dim. parametrisatio ideal PARA=imap(LIFTRING,PARA);   // get the zero-dim. parametrisatio // from LIFTRING // compute the lift of the solution of the original ideal i k=1; // the lift has as many components as GRUNDRING has variables!=t for (j=1;j<=nvars(GRUNDRING)-1;j++) for (j=1;j<=nvars(GRUNDRING)-1;j++) { // if repl[j]=0, then the corresponding variable was not eliminated if (repl[j]==0) if (repl[j]==0) { LIFT[j]=PARA[k]; // thus the lift has been LIFT[j]=PARA[k]; // thus the lift has been // computed by tropicalparametrise k++; // k checks how many entries of PARA have already been used else  // if repl[j]!=0, repl[j] contains replacement rule for the lift { LIFT[j]=repl[j]; // we still have to replace the vars LIFT[j]=repl[j]; // we still have to replace the vars // in repl[j] by the corresp. entries of PARA // replace all variables!=t (from CUTDOWNRING) for (l=1;l<=nvars(CUTDOWNRING)-1;l++) for (l=1;l<=nvars(CUTDOWNRING)-1;l++) { // substitute the kth variable by PARA[k] LIFT[j]=subst(LIFT[j],var(l),PARA[l]); LIFT[j]=subst(LIFT[j],var(l),PARA[l]); } } } setring LIFTRING; ideal LIFT=imap(REPLACEMENTRING,LIFT); // test now if the LIFT has the correct valuation !!! // note: it may happen, that when resubstituting PARA into ideal LIFT=imap(REPLACEMENTRING,LIFT); // test now if the LIFT has the correct valuation !!! // note: it may happen, that when resubstituting PARA into //       the replacement rules //       there occured some unexpected cancellation; //       there occured some unexpected cancellation; //       we only know that for SOME //       solution of the zero-dimensional reduction NO //       canellation will occur, //       but for others this may very well happen; //       solution of the zero-dimensional reduction NO //       canellation will occur, //       but for others this may very well happen; //       this in particular means that //       we possibly MUST compute all zero-dimensional //       we possibly MUST compute all zero-dimensional //       solutions when cutting down! intvec testw=precutdownw[1]; kill PARA; // only if LIFT has the right valuation we have to do something if (isgood==1) { // it remains to reverse the original substitutions, if (isgood==1) { // it remains to reverse the original substitutions, // where appropriate !!! // if some entry of the original w was positive, // if some entry of the original w was positive, // we replace the corresponding // variable x_i by t^-w[i]*x_i, so we must now replace */ // if LIFTRING contains a parameter @a, change it to a if ((noabs==0) and (defined(@a)==-1)) if ((noabs==0) and (defined(@a)==-1)) { // pass first to a ring where a and @a // pass first to a ring where a and @a // are variables in order to use maps poly mp=minpoly; // replace @a by a in minpoly and in LIFT map phi=INTERRING,t,a,a; mp=phi(mp); mp=phi(mp); LIFT=phi(LIFT); // pass now to a ring whithout @a and with a as parameter ideal LIFT=imap(INTERRING,LIFT); kill INTERRING; } } // then export LIFT export(LIFT); export(LIFT); // test the  result by resubstitution setring GRUNDRING; setring GRUNDRING; list resubst; if (noresubst==0) } else { { resubst=tropicalliftingresubstitute(substitute(i,t,t^(TP[jj][2])),list(LIFTRING),N*TP[jj][2]); } } setring BASERING; // Finally, if t has been replaced by t^N, then we have to change the // Finally, if t has been replaced by t^N, then we have to change the // third entry of TP by multiplying by N. if (noabs==1) kill LIFTRING; } // if dd!=0 and the procedure was called without the // if dd!=0 and the procedure was called without the // option findAll, then it might very well // be the case that no solution is found, since // be the case that no solution is found, since // only one solution for the zero-dimensional // reduction was computed and this one might have // reduction was computed and this one might have // had cancellations when resubstituting; // if so we have to restart the process with the option findAll "The procedure will be restarted with the option 'findAll'."; "Go on by hitting RETURN!"; findall=1; findall=1; noabs=0; setring CUTDOWNRING; "i";i; "ini";tInitialIdeal(i,w,1); /* setring GRUNDRING; } } // if internally the option findall was set, then return // if internally the option findall was set, then return // only the first solution if (defined(hadproblems)!=0) if (voice+printlevel>=2) { "The procedure has created a list of lists. The jth entry of this list contains a ring, an integer and an intvec. In this ring lives an ideal representing the wanted lifting, if the integer is N then in the parametrisation t has to be replaced by t^1/N, and if the ith component of the intvec is w[i] then the ith component in LIFT and if the ith component of the intvec is w[i] then the ith component in LIFT should be multiplied by t^-w[i]/N in order to get the parametrisation. Suppose your list has the name L, then you can access the 1st ring via: "; if (findall==1) { "def LIFTRing=L[1][1]; setring LIFTRing; LIFT; "def LIFTRing=L[1][1]; setring LIFTRing; LIFT; "; } else { "def LIFTRing=L[1]; setring LIFTRing; LIFT; "def LIFTRing=L[1]; setring LIFTRing; LIFT; "; } } } if (findall==1) // if all solutions have been computed, return a list of lists def LIFTRing=LIST[1]; setring LIFTRing; // LIFT contains the first 4 terms of a point in the variety of i // LIFT contains the first 4 terms of a point in the variety of i // over the Puiseux series field C{{t}} whose order is -w[1]/w[0]=1 LIFT; // NOTE: since the last component of v is positive, the lifting //       must start with a negative power of t, which in Singular //       is not allowed for a variable. //       is not allowed for a variable. def LIFTRing3=LIST[1]; setring LIFTRing3; string Kstring="Z/"+string(char(LIFTRing))+"Z"; } // this means that tropicalLifting was called with // this means that tropicalLifting was called with // absolute primary decomposition if (size(troplift)==4) { if (size(troplift)==4) { setring LIFTRing; "The lifting of the point in the tropical variety lives in the ring"; if ((size(LIFTpar)==0) and (N==1)) { Kstring+"[[t]]"; Kstring+"[[t]]"; } if ((size(LIFTpar)==0) and (N!=1)) { Kstring+"[[t^(1/"+string(N)+")]]"; Kstring+"[[t^(1/"+string(N)+")]]"; } if ((size(LIFTpar)!=0) and (N!=1)) { Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t^(1/"+string(N)+")]]"; { Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t^(1/"+string(N)+")]]"; } if ((size(LIFTpar)!=0) and (N==1)) { Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t]]"; { Kstring+"["+LIFTpar+"]/"+string(minpoly)+"[[t]]"; } } } if ((size(LIFTpar)!=0) and (N!=1)) { Kstring+"["+LIFTpar+"]/M[[t^(1/"+string(N)+")]]"; { Kstring+"["+LIFTpar+"]/M[[t^(1/"+string(N)+")]]"; "where M is the maximal ideal"; "M=<"+m+">"; } if ((size(LIFTpar)!=0) and (N==1)) { Kstring+"["+LIFTpar+"]/M[[t]]"; { Kstring+"["+LIFTpar+"]/M[[t]]"; "where M is the maximal ideal"; "M=<"+m+">"; } } } ""; } } } } } example /////////////////////////////////////////////////////////////////////////////// /// Procedures concerned with drawing a tropical curve or a Newton subdivision /// Procedures concerned with drawing a tropical curve or a Newton subdivision /////////////////////////////////////////////////////////////////////////////// proc tropicalCurve (def tp,list #) "USAGE:      tropicalCurve(tp[,#]); tp list, # optional list ASSUME:      tp is list of linear polynomials of the form ax+by+c with integers a, b and a rational number c representing ASSUME:      tp is list of linear polynomials of the form ax+by+c with integers a, b and a rational number c representing a tropical Laurent polynomial defining a tropical plane curve; alternatively tp can be a polynomial in Q(t)[x,y] defining a tropical plane curve via the valuation map; the basering must have a global monomial ordering, alternatively tp can be a polynomial in Q(t)[x,y] defining a tropical plane curve via the valuation map; the basering must have a global monomial ordering, two variables and up to one parameter! RETURN:      list, each entry i=1,...,size(l)-1 corresponds to a vertex RETURN:      list, each entry i=1,...,size(l)-1 corresponds to a vertex in the tropical plane curve defined by tp l[i][1] = x-coordinate of the ith vertex l[i][2] = y-coordinate of the ith vertex l[i][3] = intmat, if j is an entry in the first row l[i][3] = intmat, if j is an entry in the first row of intmat then the ith vertex of the tropical curve is connected to the the tropical curve is connected to the jth vertex with multiplicity given by the corresponding entry in the second row l[i][4] = list of lists, the first entry of a list is a primitive integer vector defining the direction of an unbounded edge emerging from the ith vertex of the graph, the corresponding second entry in l[i][4] = list of lists, the first entry of a list is a primitive integer vector defining the direction of an unbounded edge emerging from the ith vertex of the graph, the corresponding second entry in the list is the multiplicity of the unbounded edge l[i][5] = a polynomial whose monomials mark the vertices l[i][5] = a polynomial whose monomials mark the vertices in the Newton polygon corresponding to the entries in tp which take the common minimum at the ith vertex -- if some coefficient a or b of the linear polynomials in the input was negative, in tp which take the common minimum at the ith vertex -- if some coefficient a or b of the linear polynomials in the input was negative, then each monomial has to be shifted by the values in l[size(l)][3] l[size(l)][1] = list, the entries describe the boundary l[size(l)][1] = list, the entries describe the boundary points of the Newton subdivision l[size(l)][2] = list, the entries are pairs of integer l[size(l)][2] = list, the entries are pairs of integer vectors defining an interior edge of the Newton subdivision l[size(l)][3] = intvec, the monmials occuring in l[i][5] have to be shifted by this vector in order to represent marked l[size(l)][3] = intvec, the monmials occuring in l[i][5] have to be shifted by this vector in order to represent marked vertices in the Newton polygon NOTE:        here the tropical polynomial is supposed to be the MINIMUM of the linear forms in tp, unless the optional input #[1] NOTE:        here the tropical polynomial is supposed to be the MINIMUM of the linear forms in tp, unless the optional input #[1] is the string 'max' EXAMPLE:     example tropicalCurve;   shows an example" ERROR("The basering should have a global monomial ordering, e.g. ring r=(0,t),(x,y),dp;"); } // if you insert a single polynomial instead of an ideal // if you insert a single polynomial instead of an ideal // representing a tropicalised polynomial, // then we compute first the tropicalisation of this polynomial // then we compute first the tropicalisation of this polynomial // -- this feature is not documented in the above help string if (typeof(tp)=="poly") { // exclude the case that the basering has not precisely // exclude the case that the basering has not precisely // one parameter and two indeterminates if ((npars(basering)!=1) or (nvars(basering)!=2)) { ERROR("The basering should have precisely one parameter and two indeterminates!"); ERROR("The basering should have precisely one parameter and two indeterminates!"); } poly f=tp; if (nvars(basering) != 2) { ERROR("The basering should have precisely two indeterminates!"); } // -1) Exclude the pathological case that the defining ERROR("The basering should have precisely two indeterminates!"); } // -1) Exclude the pathological case that the defining //     tropical polynomial has only one term, //     so that the tropical variety is not defined. intmat M[2][1]=0,0; return(list(list(0,0,M,list(),detropicalise(tp[1])),list(list(leadexp(detropicalise(tp[1]))),list()))); } // 0) If the input was a list of linear polynomials, } // 0) If the input was a list of linear polynomials, //    then some coefficient of x or y can be negative, //    i.e. the input corresponds to the tropical curve //    i.e. the input corresponds to the tropical curve //    of a Laurent polynomial. In that case we should //    add some ax+by, so that all coefficients are positive. //    add some ax+by, so that all coefficients are positive. //    This does not change the tropical curve. //    however, we have to save (a,b), since the Newton //    however, we have to save (a,b), since the Newton //    polygone has to be shifted by (-a,-b). poly aa,bb; // koeffizienten { bb=koeffizienten(tp[i],2); } } } if ((aa!=0) or (bb!=0)) } } // 1) compute the vertices of the tropical curve // 1) compute the vertices of the tropical curve //    defined by tp and the Newton subdivision list vtp=verticesTropicalCurve(tp,#); //    if vtp is empty, then the Newton polygone is just //    if vtp is empty, then the Newton polygone is just //    a line segment and constitutes a bunch of lines //    which can be computed by bunchOfLines return(bunchOfLines(tp)); } // 2) store all vertices belonging to the ith part of the // 2) store all vertices belonging to the ith part of the //    Newton subdivision in the list vtp[i] as 4th entry, //    and store those, which are not corners of the ith subdivision polygon //    in vtp[i][6] poly nwt; poly nwt; list boundaryNSD;  // stores the boundary of a Newton subdivision intmat zwsp[2][1]; // used for intermediate storage intmat zwsp[2][1]; // used for intermediate storage for (i=1;i<=size(vtp);i++) { k=1; nwt=vtp[i][3]; // the polynomial representing the nwt=vtp[i][3]; // the polynomial representing the // ith part of the Newton subdivision // store the vertices of the ith part of the // store the vertices of the ith part of the // Newton subdivision in the list newton list newton; list newton; while (nwt!=0) { k++; } boundaryNSD=findOrientedBoundary(newton);// a list of the vertices // of the Newton subdivision // as integer vectors (only those // on the boundary, and oriented boundaryNSD=findOrientedBoundary(newton);// a list of the vertices // of the Newton subdivision // as integer vectors (only those // on the boundary, and oriented // clockwise) vtp[i][4]=boundaryNSD[1]; vtp[i][5]=boundaryNSD[2]; vtp[i][6]=zwsp; // the entries of the first row will denote to which // vertex the ith one is connected // and the entries of the second row will denote vtp[i][6]=zwsp; // the entries of the first row will denote to which // vertex the ith one is connected // and the entries of the second row will denote //with which multiplicity kill newton; // we kill the superflous list } // 3) Next we build for each part of the Newton // 3) Next we build for each part of the Newton //    subdivision the list of all pairs of vertices on the //    boundary, which are involved, including those which are not corners kill ipairs; } // 4) Check for all pairs of verticies in the Newton diagram if they // 4) Check for all pairs of verticies in the Newton diagram if they //    occur in two different parts of the Newton subdivision int deleted; // if a pair occurs in two NSD, it can be removed int deleted; // if a pair occurs in two NSD, it can be removed // from both - deleted is then set to 1 list inneredges; // contains the list of all pairs contained in two NSD list inneredges; // contains the list of all pairs contained in two NSD // - these are inner the edges of NSD int ggt; d=1;  // counts the inner edges for (i=1;i<=size(pairs)-1;i++) { { for (j=i+1;j<=size(pairs);j++) { deleted=0; for (l=size(pairs[j]);l>=1 and deleted==0;l--) { { 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]))) { d++; ggt=abs(gcd(pairs[i][k][1][1]-pairs[i][k][2][1],pairs[i][k][1][2]-pairs[i][k][2][2])); zwsp=j,ggt;   // and it is recorded that the ith and jth zwsp=j,ggt;   // and it is recorded that the ith and jth // vertex should be connected with mult ggt vtp[i][6]=intmatconcat(vtp[i][6],zwsp); zwsp=i,ggt; vtp[j][6]=intmatconcat(vtp[j][6],zwsp); pairs[i]=delete(pairs[i],k);  // finally the pair is deleted pairs[i]=delete(pairs[i],k);  // finally the pair is deleted // from both sets of pairs pairs[j]=delete(pairs[j],l); } } // 6.3) Order the vertices such that passing from one to the next we // 6.3) Order the vertices such that passing from one to the next we //      travel along the boundary of the Newton polytope clock wise. boundaryNSD=findOrientedBoundary(vertices); list orderedvertices=boundaryNSD[1]; // 7) Find the unbounded edges emerging from a vertex in the tropical curve. //    For this we check the remaining pairs for the ith NSD. //    For this we check the remaining pairs for the ith NSD. //    Each pair is ordered according //    to the order in which the vertices occur in orderedvertices. //    to the order in which the vertices occur in orderedvertices. //    The direction of the //    unbounded edge is then the outward pointing primitive normal //    unbounded edge is then the outward pointing primitive normal //    vector to the vector //    pointing from the first vertex in a pair to the second one. for (i=1;i<=size(pairs);i++) { list ubedges; // stores the unbounded edges list ubedges; // stores the unbounded edges k=1; // counts the unbounded edges for (j=1;j<=size(pairs[i]);j++) { // computes the position of the vertices in the pos1=positionInList(orderedvertices,pairs[i][j][1]); pos1=positionInList(orderedvertices,pairs[i][j][1]); // pair in the list orderedvertices pos2=positionInList(orderedvertices,pairs[i][j][2]); pos2=positionInList(orderedvertices,pairs[i][j][2]); if (((pos1>pos2) and !((pos1==size(orderedvertices)) and (pos2==1))) or ((pos2==size(orderedvertices)) and (pos1==1)))  // reorders them if necessary { } // the vector pointing from vertex 1 in the pair to vertex2 normalvector=pairs[i][j][2]-pairs[i][j][1]; normalvector=pairs[i][j][2]-pairs[i][j][1]; ggt=gcd(normalvector[1],normalvector[2]);   // the gcd of the entries zw=normalvector[2];    // create the outward pointing normal vector kill ubedges; } // 8) Store the computed information for the ith part // 8) Store the computed information for the ith part //    of the NSD in the list graph[i]. list graph,gr; { // the first coordinate of the ith vertex of the tropical curve gr[1]=vtp[i][1]; gr[1]=vtp[i][1]; // the second coordinate of the ith vertex of the tropical curve gr[2]=vtp[i][2]; gr[2]=vtp[i][2]; // to which vertices is the ith vertex of the tropical curve connected gr[3]=vtp[i][6]; // the directions unbounded edges emerging from the ith gr[3]=vtp[i][6]; // the directions unbounded edges emerging from the ith // vertex of the trop. curve gr[4]=vtp[i][7]; // the vertices of the boundary of the ith part of the NSD gr[5]=vtp[i][3]; gr[4]=vtp[i][7]; // the vertices of the boundary of the ith part of the NSD gr[5]=vtp[i][3]; graph[i]=gr; } } } // 10) Finally store the boundary vertices and // 10) Finally store the boundary vertices and //     the inner edges as last entry in the list graph. //     This represents the NSD. // the coordinates of the first vertex are graph[1][1],graph[1][2]; graph[1][1],graph[1][2]; // the first vertex is connected to the vertices // the first vertex is connected to the vertices //     graph[1][3][1,1..ncols(graph[1][3])] intmat M=graph[1][3]; M[1,1..ncols(graph[1][3])]; // the weights of the edges to these vertices are // the weights of the edges to these vertices are //     graph[1][3][2,1..ncols(graph[1][3])] M[2,1..ncols(graph[1][3])]; // from the first vertex emerge size(graph[1][4]) unbounded edges size(graph[1][4]); // the primitive integral direction vector of the first unbounded edge // the primitive integral direction vector of the first unbounded edge //     of the first vertex graph[1][4][1][1]; // the weight of the first unbounded edge of the first vertex graph[1][4][1][2]; // the monomials which are part of the Newton subdivision of the first vertex // the monomials which are part of the Newton subdivision of the first vertex graph[1][5]; // connecting the points in graph[size(graph)][1] we get // connecting the points in graph[size(graph)][1] we get //     the boundary of the Newton polytope graph[size(graph)][1]; // an entry in graph[size(graph)][2] is a pair of points // an entry in graph[size(graph)][2] is a pair of points //     in the Newton polytope bounding an inner edge graph[size(graph)][2][1]; proc drawTropicalCurve (def f,list #) "USAGE:      drawTropicalCurve(f[,#]); f poly or list, # optional list ASSUME:      f is list of linear polynomials of the form ax+by+c with integers a, b and a rational number c representing a tropical ASSUME:      f is list of linear polynomials of the form ax+by+c with integers a, b and a rational number c representing a tropical Laurent polynomial defining a tropical plane curve; alternatively f can be a polynomial in Q(t)[x,y] defining a tropical plane curve via the valuation map; the basering must have a global monomial ordering, two alternatively f can be a polynomial in Q(t)[x,y] defining a tropical plane curve via the valuation map; the basering must have a global monomial ordering, two variables and up to one parameter! RETURN:      NONE NOTE:        - the procedure creates the files /tmp/tropicalcurveNUMBER.tex and /tmp/tropicalcurveNUMBER.ps, where NUMBER is a random four digit integer; NOTE:        - the procedure creates the files /tmp/tropicalcurveNUMBER.tex and /tmp/tropicalcurveNUMBER.ps, where NUMBER is a random four digit integer; moreover it displays the tropical curve via kghostview; if you wish to remove all these files from /tmp, if you wish to remove all these files from /tmp, call the procedure cleanTmp @*           - edges with multiplicity greater than one carry this multiplicity @*           - if # is empty, then the tropical curve is computed w.r.t. minimum, if #[1] is the string 'max', then it is computed w.r.t. maximum @*           - if the last optional argument is 'onlytexfile' then only the latex file is produced; this option should be used if kghostview if #[1] is the string 'max', then it is computed w.r.t. maximum @*           - if the last optional argument is 'onlytexfile' then only the latex file is produced; this option should be used if kghostview is not installed on your system @*           - note that lattice points in the Newton subdivision which are black correspond to markings of the marked subdivision, @*           - note that lattice points in the Newton subdivision which are black correspond to markings of the marked subdivision, while lattice points in grey are not marked EXAMPLE:     example drawTropicalCurve  shows an example" if (typeof(f)=="poly") { // exclude the case that the basering has not precisely // exclude the case that the basering has not precisely // one parameter and two indeterminates if ((npars(basering)!=1) or (nvars(basering)!=2)) { ERROR("The basering should have precisely one parameter and two indeterminates!"); ERROR("The basering should have precisely one parameter and two indeterminates!"); } texf=texPolynomial(f); // write the polynomial over Q(t) texf="\\mbox{\\tt The defining equation was not handed over!}"; list graph=f; } } else { // write the tropical polynomial defined by f if (size(#)==0) { { texf="\\min\\{"; } for (j=1;j<=size(f);j++) { texf=texf+texPolynomial(f[j]); texf=texf+texPolynomial(f[j]); if (j0) { // find the only vertex to which the nonloopvertex // find the only vertex to which the nonloopvertex // is connected, when it is found // delete the connection in graph[i][3] and set dv=1 { delvert=graph[i][3]; delvert=intmatcoldelete(delvert,j); // delete the connection (note delvert=intmatcoldelete(delvert,j); // delete the connection (note // there must have been two!) dv=1; } } graph[nonloopvertex][3]=nullmat; // the only connection of nonloopvertex graph[nonloopvertex][3]=nullmat; // the only connection of nonloopvertex // is killed nonloopvertex=findNonLoopVertex(graph); // find the next vertex nonloopvertex=findNonLoopVertex(graph); // find the next vertex // which has only one edge } intvec loop,weights; // encodes the loop and the edges i=1; //    start by finding some vertex which belongs to the loop while (loop==0) //    start by finding some vertex which belongs to the loop while (loop==0) { // if graph[i][3] of a vertex in the loop has 2 columns, all others have 1 if (ncols(graph[i][3])==1) if (ncols(graph[i][3])==1) { i++; else { loop[1]=i; // a starting vertex is found loop[2]=graph[i][3][1,1]; // it is connected to vertex with this number loop[1]=i; // a starting vertex is found loop[2]=graph[i][3][1,1]; // it is connected to vertex with this number weights[2]=graph[i][3][2,1]; // and the edge has this weight } while (j!=i)  // the loop ends with the same vertex with which it starts { // the first row of graph[j][3] has two entries // the first row of graph[j][3] has two entries // corresponding to the two vertices // to which the active vertex j is connected; // to which the active vertex j is connected; // one is loop[k-1], i.e. the one which // precedes j in the loop; we have to choose the other one if (graph[j][3][1,1]==loop[k-1]) if (graph[j][3][1,1]==loop[k-1]) { loop[k+1]=graph[j][3][1,2]; } j=loop[k+1]; // set loop[k+1] the new active vertex k++; } k++; } // 7) compute for each edge in the loop the lattice length poly xcomp,ycomp; // the x- and y-components of the vectors poly xcomp,ycomp; // the x- and y-components of the vectors // connecting two vertices of the loop number nenner;    // the product of the denominators of number nenner;    // the product of the denominators of // the x- and y-components number jinvariant;  // the j-invariant int eins,zwei,ggt; int eins,zwei,ggt; for (i=1;i<=size(loop)-1;i++) // compute the lattice length for each edge { xcomp=graph[loop[i]][1]-graph[loop[i+1]][1]; ycomp=graph[loop[i]][2]-graph[loop[i+1]][2]; xcomp=graph[loop[i]][1]-graph[loop[i+1]][1]; ycomp=graph[loop[i]][2]-graph[loop[i+1]][2]; nenner=denominator(leadcoef(xcomp))*denominator(leadcoef(ycomp)); execute("eins="+string(numerator(leadcoef(nenner*xcomp)))+";"); execute("zwei="+string(numerator(leadcoef(nenner*ycomp)))+";"); execute("eins="+string(numerator(leadcoef(nenner*xcomp)))+";"); execute("zwei="+string(numerator(leadcoef(nenner*ycomp)))+";"); ggt=gcd(eins,zwei); // the lattice length is the "gcd" // of the x-component and the y-component jinvariant=jinvariant+ggt/(nenner*weights[i+1]); // divided by the jinvariant=jinvariant+ggt/(nenner*weights[i+1]); // divided by the // weight of the edge } return(jinvariant); return(jinvariant); } } // the curve can have arbitrary degree tropicalJInvariant(t*(x7+y7+1)+1/t*(x4+y4+x2+y2+x3y+xy3)+1/t7*x2y2); // the procedure does not realise, if the embedded graph of the tropical // the procedure does not realise, if the embedded graph of the tropical //     curve has a loop that can be resolved tropicalJInvariant(1+x+y+xy+tx2y+txy2); // but it does realise, if the curve has no loop at all ... tropicalJInvariant(x+y+1); // or if the embedded graph has more than one loop - even if only one // or if the embedded graph has more than one loop - even if only one //     cannot be resolved tropicalJInvariant(1+x+y+xy+tx2y+txy2+t3x5+t3y5+tx2y2+t2xy4+t2yx4); proc weierstrassForm (poly f,list #) "USAGE:      weierstrassForm(wf[,#]); wf poly, # list ASSUME:      wf is a a polynomial whose Newton polygon has precisely one interior lattice point, so that it defines an elliptic curve ASSUME:      wf is a a polynomial whose Newton polygon has precisely one interior lattice point, so that it defines an elliptic curve on the toric surface corresponding to the Newton polygon RETURN:      poly, the Weierstrass normal form of the polynomial to Fernando Rodriguez Villegas, villegas@math.utexas.edu @*           - the characteristic of the base field should not be 2 or 3 @*           - if an additional argument # is given, a simplified Weierstrass @*           - if an additional argument # is given, a simplified Weierstrass form is computed EXAMPLE:     example weierstrassForm;   shows an example" proc jInvariant (poly f,list #) "USAGE:      jInvariant(f[,#]); f poly, # list ASSUME:      - f is a a polynomial whose Newton polygon has precisely one interior lattice point, so that it defines an elliptic curve "USAGE:      jInvariant(f[,#]); f poly, # list ASSUME:      - f is a a polynomial whose Newton polygon has precisely one interior lattice point, so that it defines an elliptic curve on the toric surface corresponding to the Newton polygon @*           - it the optional argument # is present the base field should be Q(t) and the optional argument should be one of the following @*           - it the optional argument # is present the base field should be Q(t) and the optional argument should be one of the following strings: @*             'ord'   : then the return value is of type integer, @*             'ord'   : then the return value is of type integer, namely the order of the j-invariant @*             'split' : then the return value is a list of two polynomials, @*             'split' : then the return value is a list of two polynomials, such that the quotient of these two is the j-invariant RETURN:      poly, the j-invariant of the elliptic curve defined by poly NOTE:        the characteristic of the base field should not be 2 or 3, NOTE:        the characteristic of the base field should not be 2 or 3, unless the input is a plane cubic EXAMPLE:     example jInvariant;   shows an example" echo=2; ring r=(0,t),(x,y),dp; // jInvariant computes the j-invariant of a cubic // jInvariant computes the j-invariant of a cubic jInvariant(x+y+x2y+y3+1/t*xy); // if the ground field has one parameter t, then we can instead // if the ground field has one parameter t, then we can instead //    compute the order of the j-invariant jInvariant(x+y+x2y+y3+1/t*xy,"ord"); poly h=x22y11+x19y10+x17y9+x16y9+x12y7+x9y6+x7y5+x2y3+x14y8; // its j-invariant is jInvariant(h); jInvariant(h); } @*                 l[6] = a list containing the vertices of the tropical conic f @*                 l[7] = a list containing lists with vertices of the tangents @*                 l[8] = a string which contains the latex-code to draw the @*                 l[8] = a string which contains the latex-code to draw the tropical conic and its tropicalised tangents @*                 l[9] = if # is non-empty, this is the same data for the dual ring LINRING=(0,t),(x,y,a(1..6)),lp; list points=imap(BASERING,points); ideal I; // the ideal will contain the linear equations given by the conic ideal I; // the ideal will contain the linear equations given by the conic // and the points for (i=1;i<=5;i++) ring tRING=0,t,ls; list pointdenom=imap(BASERING,pointdenom); list pointnum=imap(BASERING,pointnum); list pointnum=imap(BASERING,pointnum); intvec pointcoordinates; for (i=1;i<=size(pointdenom);i++) We consider the concic through the following five points: \\begin{displaymath} "; "; string texf=texDrawTropical(graphf,list("",scalefactor)); for (i=1;i<=size(points);i++) \\end{document}"; setring BASERING; // If # non-empty, compute the dual conic and the tangents // through the dual points // If # non-empty, compute the dual conic and the tangents // through the dual points // corresponding to the tangents of the given conic. if (size(#)>0) { list dualpoints; for (i=1;i<=size(points);i++) for (i=1;i<=size(points);i++) { 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)); // conic[2] is the equation of the conic f passing through the five points conic[2]; // conic[3] is a list containing the equations of the tangents // conic[3] is a list containing the equations of the tangents //          through the five points conic[3]; // conic[4] is an ideal representing the tropicalisation of the conic f conic[4]; // conic[5] is a list containing the tropicalisation // conic[5] is a list containing the tropicalisation //          of the five tangents in conic[3] conic[5]; // conic[6] is a list containing the vertices of the tropical conic // conic[6] is a list containing the vertices of the tropical conic conic[6]; // conic[7] is a list containing the vertices of the five tangents conic[7]; // conic[8] contains the latex code to draw the tropical conic and //          its tropicalised tangents; it can written in a file, processed and //          displayed via kghostview write(":w /tmp/conic.tex",conic[8]); system("sh","cd /tmp; latex /tmp/conic.tex; dvips /tmp/conic.dvi -o; // conic[8] contains the latex code to draw the tropical conic and //          its tropicalised tangents; it can written in a file, processed and //          displayed via kghostview write(":w /tmp/conic.tex",conic[8]); system("sh","cd /tmp; latex /tmp/conic.tex; dvips /tmp/conic.dvi -o; kghostview conic.ps &"); // with an optional argument the same information for the dual conic is computed // with an optional argument the same information for the dual conic is computed //         and saved in conic[9] conic=conicWithTangents(points,1); conic[9][2]; // the equation of the dual conic } /////////////////////////////////////////////////////////////////////////////// /// Procedures concerned with tropicalisation ASSUME:      f is a polynomial in Q(t)[x_1,...,x_n] RETURN:      list, the linear forms of the tropicalisation of f NOTE:        if # is empty, then the valuation of t will be 1, @*           if # is the string 'max' it will be -1; @*           the latter supposes that we consider the maximum of the NOTE:        if # is empty, then the valuation of t will be 1, @*           if # is the string 'max' it will be -1; @*           the latter supposes that we consider the maximum of the computed linear forms, the former that we consider their minimum EXAMPLE:     example tropicalise;   shows an example" { tropicalf[i]=tropicalf[i]+exp[j]*var(j); } } f=f-lead(f); } ///////////////////////////////////////////////////////////////////////// proc tInitialForm (poly f, intvec w) proc tInitialForm (poly f, intvec w) "USAGE:      tInitialForm(f,w); f a polynomial, w an integer vector ASSUME:      f is a polynomial in Q[t,x_1,...,x_n] and w=(w_0,w_1,...,w_n) RETURN:      poly, the t-initialform of f(t,x) w.r.t. w evaluated at t=1 NOTE:        the t-initialform is the sum of the terms with MAXIMAL NOTE:        the t-initialform is the sum of the terms with MAXIMAL weighted order w.r.t. w EXAMPLE:     example tInitialForm;   shows an example" // do the same for the remaining part of f and compare the results // keep only the smallest ones int vglgewicht; f=f-lead(f); int vglgewicht; f=f-lead(f); while (f!=0) { initialf=initialf+lead(f); } } } f=f-lead(f); } proc tInitialIdeal (ideal i,intvec w,list #) "USAGE:      tInitialIdeal(i,w); i ideal, w intvec ASSUME:      i is an ideal in Q[t,x_1,...,x_n] and w=(w_0,...,w_n) ASSUME:      i is an ideal in Q[t,x_1,...,x_n] and w=(w_0,...,w_n) RETURN:      ideal ini, the t-initial ideal of i with respect to w" { // THE PROCEDURE WILL BE CALLED FROM OTHER PROCEDURES INSIDE THIS LIBRARY; // IN THIS CASE THE VARIABLE t WILL INDEED BE THE LAST VARIABLE INSTEAD OF // IN THIS CASE THE VARIABLE t WILL INDEED BE THE LAST VARIABLE INSTEAD OF // THE FIRST, // AND WE THEREFORE HAVE TO MOVE IT BACK TO THE FRONT! // ... and compute a standard basis with // respect to the homogenised ordering defined by w. Since the generators // of i will be homogeneous it we can instead take the ordering wp // with the weightvector (0,w) replaced by (M,...,M)+(0,w) for some // large M, so that all entries are positive int M=-minInIntvec(w)[1]+1; // find M such that w[j]+M is // of i will be homogeneous it we can instead take the ordering wp // with the weightvector (0,w) replaced by (M,...,M)+(0,w) for some // large M, so that all entries are positive int M=-minInIntvec(w)[1]+1; // find M such that w[j]+M is // strictly positive for all j intvec whomog=M+1; } execute("ring WEIGHTRING=("+charstr(basering)+"),("+varstr(basering)+"),(wp("+string(whomog)+"));"); // map i to the new ring and compute a GB of i, then dehomogenise i, // so that we can be sure, that the // map i to the new ring and compute a GB of i, then dehomogenise i, // so that we can be sure, that the // initial forms of the generators generate the initial ideal ideal i=subst(groebner(imap(HOMOGRING,i)),@s,1); proc texDrawBasic (list texdraw) "USAGE:      texDrawBasic(texdraw); list texdraw ASSUME:      texdraw is a list of strings representing texdraw commands (as produced by texDrawTropical) which should be embedded into ASSUME:      texdraw is a list of strings representing texdraw commands (as produced by texDrawTropical) which should be embedded into a texdraw environment RETURN:      string, a texdraw environment enclosing the input \\end{texdraw}"; return(texdrawtp); } } example { ASSUME:  graph is the output of tropicalCurve RETURN:  string, the texdraw code of the tropical plane curve encoded by graph NOTE:    - if the list # is non-empty, the first entry should be a string; if this string is 'max', then the tropical curve is considered with respect to the maximum; otherwise the curve is considered with respect to the minimum and the string can be used to insert NOTE:    - if the list # is non-empty, the first entry should be a string; if this string is 'max', then the tropical curve is considered with respect to the maximum; otherwise the curve is considered with respect to the minimum and the string can be used to insert further texdraw commands (e.g. to have a lighter image as when called from inside conicWithTangents); @*       - the procedure computes a scalefactor for the texdraw command which should help to display the curve in the right way; this may, however, be a bad idea if several texDrawTropical outputs are put together to form one image; the scalefactor can be prescribed from inside conicWithTangents); @*       - the procedure computes a scalefactor for the texdraw command which should help to display the curve in the right way; this may, however, be a bad idea if several texDrawTropical outputs are put together to form one image; the scalefactor can be prescribed by a second optional entry of type poly @*       - the list # is optional and may as well be empty { int i,j; // deal first with the pathological case that // deal first with the pathological case that // the input polynomial was a monomial // and does therefore not define a tropical curve, // and check if the Newton polytope is // and does therefore not define a tropical curve, // and check if the Newton polytope is // a line segment so that the curve defines a bunch of lines int bunchoflines; // if the boundary of the Newton polytope consists of a single point if (size(graph[size(graph)][1])==1) if (size(graph[size(graph)][1])==1) { return(string()); } // then the Newton polytope is a line segment if ((size(graph[size(graph)][1])-size(syz(M)))==1) if ((size(graph[size(graph)][1])-size(syz(M)))==1) { bunchoflines=1; // go on with the case that a tropical curve is defined if (size(#)==0) { { string texdrawtp=" { if ((#[1]!="max") and (#[1]!="")) { { string texdrawtp=#[1]; } { // if the curve is a bunch of lines no vertex has to be drawn if (bunchoflines==0) if (bunchoflines==0) { texdrawtp=texdrawtp+" } // draw the bounded edges emerging from the ith vertex for (j=1;j<=ncols(graph[i][3]);j++) { // don't draw it twice - and if there is only one vertex for (j=1;j<=ncols(graph[i][3]);j++) { // don't draw it twice - and if there is only one vertex //                       and graph[i][3][1,1] is thus 0, nothing is done if (i1) if (graph[i][3][2,j]>1) { texdrawtp=texdrawtp+" // draw the unbounded edges emerging from the ith vertex // they should not be too long for (j=1;j<=size(graph[i][4]);j++) { for (j=1;j<=size(graph[i][4]);j++) { relxy=shorten(list(decimal(3*graph[i][4][j][1][1]/scalefactor),decimal(3*graph[i][4][j][1][2]/scalefactor),"2.5")); texdrawtp=texdrawtp+" \\move ("+decimal(graph[i][1]-centerx)+" "+decimal(graph[i][2]-centery)+") \\rlvec ("+relxy[1]+" "+relxy[2]+")"; // if the multiplicity is more than one, denote it in the picture if (graph[i][4][j][2]>1) if (graph[i][4][j][2]>1) { texdrawtp=texdrawtp+" poly scalefactor=minOfPolys(list(12/leadcoef(maxx),12/leadcoef(maxy))); if (scalefactor<1) { { subdivision=subdivision+" \\relunitscale"+ decimal(scalefactor); { subdivision=subdivision+" \\move ("+string(boundary[i][1])+" "+string(boundary[i][2])+") \\move ("+string(boundary[i][1])+" "+string(boundary[i][2])+") \\lvec ("+string(boundary[i+1][1])+" "+string(boundary[i+1][2])+")"; } } subdivision=subdivision+" \\move ("+string(boundary[size(boundary)][1])+" "+string(boundary[size(boundary)][2])+") \\move ("+string(boundary[size(boundary)][1])+" "+string(boundary[size(boundary)][2])+") \\lvec ("+string(boundary[1][1])+" "+string(boundary[1][2])+") { subdivision=subdivision+" \\move ("+string(inneredges[i][1][1])+" "+string(inneredges[i][1][2])+") \\move ("+string(inneredges[i][1][1])+" "+string(inneredges[i][1][2])+") \\lvec ("+string(inneredges[i][2][1])+" "+string(inneredges[i][2][2])+")"; } } } // deal with the pathological cases // deal with the pathological cases if (size(boundary)==1) // then the Newton polytope is a point { { subdivision=subdivision+" \\move ("+string(markings[i][1])+" "+string(markings[i][2])+") \\move ("+string(markings[i][1])+" "+string(markings[i][2])+") \\fcir f:0 r:"+decimal(2/(8*scalefactor),size(string(int(scalefactor)))+1); } // enclose subdivision in the texdraw environment string texsubdivision=" string texsubdivision=" \\begin{texdraw} \\drawdim cm  \\relunitscale 1 \\drawdim cm  \\relunitscale 1 \\linewd 0.05" +subdivision+" poly f=x+y+x2y+xy2+1/t*xy; list graph=tropicalCurve(f); // compute the texdraw code of the Newton subdivision of the tropical curve // compute the texdraw code of the Newton subdivision of the tropical curve texDrawNewtonSubdivision(graph); } proc texDrawTriangulation (list triang,list polygon) "USAGE:      texDrawTriangulation(triang,polygon);  triang,polygon list ASSUME:      polygon is a list of integer vectors describing the ASSUME:      polygon is a list of integer vectors describing the lattice points of a marked polygon; triang is a list of integer vectors describing a triang is a list of integer vectors describing a triangulation of the marked polygon in the sense that an integer vector of the form (i,j,k) describes in the sense that an integer vector of the form (i,j,k) describes the triangle formed by polygon[i], polygon[j] and polygon[k] RETURN:      string, a texdraw code for the triangulation described RETURN:      string, a texdraw code for the triangulation described by triang without the texdraw environment EXAMPLE:     example texDrawTriangulation;   shows an example" "; int i,j; // indices list pairs,markings; // stores edges of the triangulation, respecively // the marked points for each triangle store the edges and marked list pairs,markings; // stores edges of the triangulation, respecively // the marked points for each triangle store the edges and marked // points of the triangle for (i=1;i<=size(triang);i++) markings[3*i-2]=triang[i][1]; markings[3*i-1]=triang[i][2]; markings[3*i]=triang[i][3]; markings[3*i]=triang[i][3]; } // delete redundant pairs which occur more than once { latex=latex+" \\move ("+string(polygon[markings[i]][1])+" "+string(polygon[markings[i]][2])+") \\move ("+string(polygon[markings[i]][1])+" "+string(polygon[markings[i]][2])+") \\fcir f:0 r:0.08"; } { latex=latex+" \\move ("+string(polygon[pairs[i][1]][1])+" "+string(polygon[pairs[i][1]][2])+") \\move ("+string(polygon[pairs[i][1]][1])+" "+string(polygon[pairs[i][1]][2])+") \\lvec ("+string(polygon[pairs[i][2]][1])+" "+string(polygon[pairs[i][2]][2])+")"; } { latex=latex+" \\move ("+string(polygon[i][1])+" "+string(polygon[i][2])+") \\move ("+string(polygon[i][1])+" "+string(polygon[i][2])+") \\fcir f:0.7 r:0.04"; } "EXAMPLE:"; echo=2; // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // the lattice polygon spanned by the points (0,0), (3,0) and (0,3) // with all in