# A Simple Introduction to Gröbner Basis Methods in String Phenomenology

Authors: James Gray
Journal: Advances in High Energy Physics
 (2011)

---

## Abstract

I give an elementary introduction to the key algorithm used in recent applications
of computational algebraic geometry to the subject of string phenomenology. I
begin with a simple description of the algorithm itself and then give 3 examples of its use in
physics. I describe how it can be used to obtain constraints on flux parameters, how it can
simplify the equations describing vacua in 4D string models, and lastly how it can be used to
compute the vacuum space of the electroweak sector of the MSSM.


---

## Body

## 1. Introduction

There is currently a great deal of interest in applying the methods of computational algebraic geometry to string phenomenology and closely related subfields of theoretical physics. For some examples of recent work see [1, 2, 6–8, 11–18, 21, 22] and references therein. These papers utilise advances in algorithmic techniques in commutative algebra to study a wide range of subjects including various aspects of globally supersymmetric gauge theory [1, 2, 6–8], finding flux vacua in string phenomenology [10–16], studying heterotic model building on smooth Calabi-Yau in non-standard embeddings [17, 18], and more besides [19–23].Despite the wide range of physical problems which have been addressed within this context, the computational tools which are being used are all based, finally, on the same algorithm. The Buchberger algorithm [24, 25] is at once what lends these methods their power and also the rate limiting step-placing bounds on the size of problem that can be dealt with. The recent burst of activity in this field has been fueled, in part, by the advent of freely available, efficient implementations of this algorithm [26, 27]. There are also interfaces available between the commutative algebra program [27] and Mathematica [11–14, 28], with [11–14] being particularly geared towards physicist's needs. The aim of this paper is to give an elementary introduction to the Buchberger algorithm and some of its recent applications.In order to give an idea of how one simple algorithm can make so much possible, I will present the Buchberger algorithm and then show how it may be applied to physics in 3 elementary examples. Firstly, I will describe how it can be used to obtain constraints on the flux parameters in four-dimensional descriptions of string phenomenological models which are necessary and sufficient for the existence of certain types of vacuum [11–14]. Secondly, I will describe how the Buchberger algorithm can be used to simplify the equations describing the vacua of such systems making problems of finding minima much more tractable [11–14]. Finally, I will describe how the same simple algorithm can be used to calculate the supersymmetric vacuum space geometry of the electroweak sector of the MSSM [1, 2].The remainder of this paper is structured as follows. In Section2, I take a few pages to explain the algorithm and the few mathematical concepts that we will require. In the three sections following that, I then describe the three examples mentioned above. I will conclude by making a few final comments about the versatility and scaling of the Buchberger algorithm.


## 2. A Tiny Bit of Commutative Algebra

Two pages of simple mathematics will suffice to achieve all of the physical goals mentioned in the introduction. First of all we define the notion of a polynomial ring. In this paper we will call the fields of the physical systems we studyϕi and any parameters present, such as flux parameters, aα. The polynomial rings ℂ[ϕi,aα] and ℂ[aα] are then simply the infinite set of all polynomials in the fields and parameters and the infinite set of all polynomials in the parameters, respectively.Another mathematical concept we will require is that of a monomial ordering. This is simply an unambiguous way of stating whether any given monomial is formally bigger than any other given monomial. We may denote this in a particular case by sayingm1>m2, where m1, m2∈ℂ[ϕi,aα] are monomials in the fields and parameters. It is important to say what is not meant by this. We are not saying that we are taking values of the variables such that the monomial m1 is numerically larger than the monomial m2. We are rather saying that, in our formal ordering, m1 is considered to come before m2.For our purposes we will require a special type of monomial ordering called an elimination ordering. This means that our formal ordering of monomials has the following property:(2.1)P∈C[ϕi,aα],LM(P)∈C[aα]⟹P∈C[aα].
In words this just says that if the largest monomial in P according to our ordering, LM(P), does not depend on ϕi, then P does not depend on the fields at all. The monomial ordering classes all monomials with fields in them as being bigger than all of those without such constituents.Given this notion of monomial orderings, we can now present the one algorithm we will need to use—the Buchberger algorithm [24, 25]. The Buchberger algorithm takes as its input a set of polynomials. These may be thought of as a system of polynomial equations by the simple expedient of setting all of the polynomials to zero. The algorithm returns a new set of polynomials which, when thought of as a system of equations in the same way, has the same solution set as the input. The output system, however, has several additional useful properties as we will see.The Buchberger Algorithm
(1)
Start with a set of polynomials call this set𝒢.(2)
Choose a monomial ordering with the elimination property described above.(3)
For any pair of polynomialsPi, Pj∈𝒢, multiply by monomials, and form a difference so as to cancel the leading monomials with respect to the monomial ordering:(2.2)S=p1PI-p2PJs.t.p1LM(PI),p2LM(PJ)cancel.(4)
Perform polynomial long division ofS with respect to 𝒢; that is, form h̃=S-m3Pk, where m3 is a monomial and Pk∈𝒢 such that m3LM(Pk) cancels a monomial in S. Repeat until no further reduction is possible. Call the result h.(5)
Ifh=0, then consider the next pair. If h≠0, then add h to 𝒢 and return to step (3).The algorithm terminates when allS-polynomials which may be formed reduce to 0. The final set of polynomials is called a Gröbner basis.As mentioned above, the resulting set of polynomials has several nice properties. The feature which is often taken as defining is that polynomial long division with respect to this new set of polynomials always gives the same answer—it does not matter in which order we divide the polynomials out by.For us, however, the important point about our Gröbner basis𝒢 is that it has what is called the elimination property. The set of all polynomials in 𝒢 which depend only upon the parameters, 𝒢∩ℂ[aα], gives a complete set of equations on the aα which are necessary and sufficient for the existence of a solution to the set of equations we started with. The reason why this is so is actually very straightforward. Our elimination ordering says that any monomial with a field in it is greater than any monomial only made up of parameters. Looking back at step (3) of the Buchberger algorithm we see that we are repeatedly canceling off the leading terms of our polynomials—those containing the fields—as much as we can. Thus, if it is possible to rearrange our initial equations to get expressions which do not depend upon the fields ϕi, then the Buchberger algorithm will do this for us. Clearly, while we have interpreted the aα as parameters and the ϕi as fields in the above, as this is what we will require for Section 3, this was not necessary. The Buchberger algorithm can be used to eliminate any unwanted set of variables from a problem, in the manner we have described.This completes all of the mathematics that we will need for our entire discussion, and we may now move on to apply what we have learnt.


## 3. Constraints

The first physical question we wish to answer is the following. Given a four-dimensional𝒩=1 supergravity describing a flux compactification, what are the constraints on the flux parameters which are necessary and sufficient for the existence of a particular kind of vacuum? This question can be asked, and answered [11–14], for any kind of vacuum, but in the interests of concreteness and brevity let us restrict ourselves to the simple case of supersymmetric Minkowski vacua.Here is the superpotential of a typical system, taken from [29]. It describes a nongeometric compactification of type IIB string theory(3.1)W=a0-3a1τ+3a2τ2-a3τ3+S(-b0+3b1τ-3b2τ2+b3τ3)+3U(c0+(ĉ1+č1+c̃1)τ-(ĉ2+č2+c̃2)τ2-c3τ3).
This system has some known constraints on its parameters which are necessary for the existence of a permissible vacuum. These come from, for example, tadpole cancellation conditions:  (3.2)a0b3-3a1b2+3a2b1-a3b0=16,a0c3+a1(č2+ĉ2-c̃2)-a2(č1+ĉ1-c̃1)-a3c0=0,c0b2-c̃1b1+ĉ1b1-č2b0=0,c0c̃2-č12+c̃1ĉ1-ĉ2c0=0,č1b3-ĉ2b2+c̃2b2-c3b1=0,c3c̃1-č22+c̃2ĉ2-ĉ1c3=0,c0b3-c̃1b2+ĉ1b2-č2b1=0,c3c0-č2ĉ1+c̃2c̆1-ĉ1c̃2=0,č1b2-ĉ2b1+c̃2b1-c3b0=0,ĉ2c̃1-c̃1č2+č1ĉ2-c0c3=0.We also have the same constraints with the hats and checks switched around. In this example the fields, which we have been callingϕi, are S, τ, and U, and everything else is a “flux” parameter, or an aα in our notation.In total, the equations which must be satisfied if a supersymmetric Minkowski vacuum is to exist areW=0, ∂SW=0, ∂τW=0, ∂UW=0, and the constraints on the flux parameters given above. To extract a set of constraints solely involving the parameters which are necessary and sufficient for the existence of a solution to these equations, we simply follow the procedure outlined in the previous section.We can carry out this calculation trivially in Stringvacua [11–14] and, in fact, this example is provided for the user in the help system. The result is as follows:(3.3)0=c̃1=c̃2=ĉ1=ĉ2=č1=č2=c0=c3,0=16+a3b0-3a2b1+3a1b2-a0b3,0=16a32b02-96a2a3b0b1-288a22b12+432a1a3b12+54a23b13-81a1a2a3b13+27a0a32b13+432a1a3b0b2-27a22a3b02b2+48a1a32b02b2-288a0a3b1b2-18a1a2a3b0b1b2-45a0a32b0b1b2-54a1a22b12b2+81a12a3b12b2-27a0a2a3b12b2+54a0a2a3b0b22+27a0a1a3b1b22-27a02a3b23-288a1a2b0b3-32a0a3b0b3+27a23b02b3-45a1a2a3b02b3+432a0a2b1b3-27a1a22b0b1b3+54a12a3b0b1b3+48a0a2a3b0b1b3+18a0a22b12b3-81a0a1a3b12b3-144a0a1b2b3+27a12a2b0b2b3-54a0a22b0b2b3-51a0a1a3b0b2b3+27a0a1a2b1b2b3+45a02a3b1b2b3-27a0a12b22b3+27a02a2b22b3+16a02b32-27a13b0b32+45a0a1a2b0b32+27a0a12b1b32-48a02a2b1b32+3a02a1b2b32.The reader will note that the result is a somewhat lengthy set of equations. In principle one has to find quantized solutions to these expressions, an obviously intractable Diophantine problem, and therefore it might be asked why this result is of any use. In fact, knowledge of such constraints on the flux parameters is hugely useful for a number of reasons.(i)
Firstly, we note that, while the full result of this process is often complex, some of the constraints can give us simple information about the system. In the current case, for example, it can be seen thatc̃2=0 is required for the existence of a supersymmetric Minkowski vacuum.(ii)
Secondly, if one is scanning over a range of flux parameters and trying to numerically solve the equations to find vacua, one can speed up one’s analysis by first substituting any given set of flux parameters into the constraints we have obtained. If the constraints are not satisfied, then vacua do not exist and there is no point in searching numerically for a solution. This turns what would be a time-consuming numerical process giving inconclusive results (no solution was found) into a quick analytic conclusion (no solution exists).(iii)
Lastly, knowledge of such constraints can greatly speed up algebraic approaches to finding vacua such as those outlined in [11–14].


## 4. Simplifying Equations for Vacua

Another use for the mathematics we learnt in Section2 is the so-called “splitting tools” used in work such as [11–14]. The physical idea here is simple. Consider trying to solve the equations ∂V/∂ϕi=0 to find the vacua, including those which spontaneously break supersymmetry, of some supergravity theory. These equations are often extremely complicated. One way of viewing why this is so is that the equations for the turning points of the potential contain a lot of information. They describe not only the isolated minima of the potential which are of interest but also lines of maxima, saddle points of various sorts, and so forth. A useful tool to have, therefore, would be an algorithm that takes such a system as an input and returns a whole series of separate sets of equations, each individually describing fewer turning points. Since each separate equation system would then contain less information, one might expect them to be easier to solve. It would be beneficial to choose a division of these equations which has physical interest. The choice we will make here, and which programs like Stringvacua implement [11–14], is to split up the equations for the turning points according to how they break supersymmetry—that is, according to which F-terms vanish when evaluated on those loci.The ability that packages such as Stringvacua have to split up equations in this manner is based upon the following splitting tool (see [30] for a nice set of more detailed notes on this kind of mathematical technique). Say that one of the F-terms of our theory is called F. Then we can split the equations describing turning points of the potential into two pieces: (4.1)∂V∂ϕi=0,F=0,(4.2)∂V∂ϕi=0,F≠0.The first of these expressions is a set of equations which is easier to solve, in general, than∂V/∂ϕi=0 alone. We can use the F-term to simplify the equations for the turning points of the potential. On the other hand, expression (4.2) is not even a set of equations—it contains an inequality. We can convert (4.2) into a system purely involving equalities by making use of the mathematics we learned in Section 2.Consider the following set of equations, including a dummy variablet:  (4.3)∂V∂ϕi=0,Ft-1=0.The second equation in (4.3) has a solution if and only if F≠0, simply t=1/F. If F=0, then the equation reduces to -1=0 which clearly has no solutions. Equations (4.3), then, have a solution whenever the set of equalities and inequalities (4.2) do. Unfortunately they also depend upon one extra, and unwanted, variable—t. This is not a problem as we already know how to remove unwanted variables from our equations. We can simply eliminate them, as we did the fields in Section 2. This will leave us with a necessary and sufficient set of equations in ϕi and aα for a solution to (4.3) and thus to (4.2).So we can split the equations for the turning points of our potential into two simpler systems. One describes the turning points ofV for which F=0 and the other, those for which F≠0. We can of course perform such a splitting many times—once for each F-term! In fact, using additional techniques from algorithmic algebraic geometry [11–14, 31–33], which are essentially based upon the same trick, one can go much further. One can split the equations for the turning points up into component parts gaining one set of equations for every separate locus. Because we know which F-terms are nonzero on each of them, these are classified according to how they break supersymmetry. The researcher interested in a certain type of breaking can therefore select the equations describing the vacua of interest and throw everything else away.The above process of splitting up the equations for the vacua of a system can be very simply carried out in Stringvacua. Numerous examples can be found in the Mathematica help files which come with the package [11–14]. Here, let us consider the example of M-theory compactified on the coset (SU(3)×U(1))/(U(1)×U(1)). The Kähler and superpotential for this coset, which has SU(3) structure, has been presented in [34](4.4)K=-4log⁡(-i(U-U¯))-log⁡(-i(T1-T¯1)(T2-T¯2)(T3-T¯3)),W=18[4U(T1+T2+T3)+2T2T3-T1T3-T1T2+200].
Even this, relatively simple, model results in a potential of considerable size. Defining Ti=-iti+τi and U=-ix+y, we find
(4.5)V=1256t1t2t3x4(40000+t32τ12-400τ1τ2-4t32τ1τ2+4t32τ22+τ12τ22-400τ1τ3+800τ2τ3)+2τ12τ2τ3-4τ1τ22τ3+τ12τ32-4τ1τ2τ32+4τ22τ32-24t2t3x2+4t32x2-24t1(t2+t3)x2+4τ12x2+8τ1τ2x2+4τ22x2+8τ1τ3x2+8τ2τ3x2+4τ32x2+1600τ1y-8t32τ1y+1600τ2y+16t32τ2y-8τ12τ2y-8τ1τ22y+1600τ3y-8τ12τ3y+16τ22τ3y-8τ1τ32y+16τ2τ32y+16t32y2+16τ12y2+32τ1τ2y2+16τ22y2+32τ1τ3y2+32τ2τ3y2+16τ32y2+t12(t22+t32+τ22+2τ2τ3+τ32+4x2-8τ2y-8τ3y+16y2)+t22(4t32+τ12-4τ1(τ3+2y)+4(τ32+x2+4τ3y+4y2)).To find the turning points of this potential we naively need to take eight different derivatives of (4.5) and solve the resulting set of intercoupled equations in eight variables. This is clearly prohibitively difficult. Using the techniques described in this section, however, Stringvacua can separate off parts of the vacuum space for us with ease. Consider, for example, the vacua which are isolated in field space and for which the real parts of all of the F-terms are nonzero, with the imaginary parts vanishing. To find these, the package tells us, we need only to solve the equations  (4.6)9x2-500=0,5t1-2x=0,t2-x=0,t3-x=0,τ1=τ2=τ3=y=0.Because they only describe a small subset of all of the turning points of the full potential, these equations are extremely simple in form and may be trivially solved. For this particular example the physically acceptable turning point that results is a saddle—something which can be readily ascertained once its location has been discovered.


## 5. Geometry of Vacuum Spaces

As a final example of what we can do with the simple techniques introduced in Section2, we will show how to calculate the vacuum space of a globally supersymmetric gauge theory. It is a well-known result (see [35] and references therein) that the supersymmetric vacuum space of such a theory, with gauge group G, can be described as the space of holomorphic gauge invariant operators (GIOs) built out of F-flat field configurations. What does this space look like? Consider a space, the coordinates of which are identified with the GIOs of the theory. If there were no relations amongst the gauge invariant operators, then this space would be the vacuum space. However, there frequently are relations because of the way in which the GIOs are built out of the fields. For example, if we have three gauge invariant operators S1, S2, and S3 which are built out of the fields as S1=(ϕ1)2, S2=(ϕ2)2, S3=ϕ1ϕ2, then we have the relation S1S2=(S3)2. If we take these GIOs to be built out of the F-flat field configurations, then there will be still further relations among them. The vacuum space of the theory is the subspace defined by the solutions of these equations describing relations amongst the gauge invariant operators, once F-flatness has been taken into account.How can we calculate such a thing? The holomorphic gauge invariant operators of a globally supersymmetric gauge theory are given in terms of the fields(5.1)SI=fI(ϕi).HereSI are our GIOs, and the fI are the functions of the fields that define them. Let us write the F-terms of the theory as Fi. Consider the following set of equations:  (5.2)Fi=0,SI-fI(ϕi)=0.
These equations have solutions whenever the SI are given by functions of the fields in the correct way and when those field configurations which are being used are F-flat. However, according to the proceeding discussion, we wish to simply have equations in terms of the GIOs to describe our vacuum space. As in previous sections, we can eliminate the unwanted variables in our problem, in this case, the fields ϕi, using the algorithm of Section 2 to obtain the equations describing the vacuum space.As a simple example, let us take the electroweak sector of the MSSM [1, 2] (with right-handed neutrinos). Given the field content of the left-handed leptons, Lαi, the right-handed leptons, ei and νi, and the two Higgs, H and H¯, one can build the elementary GIOs given in Table 1. The indices i, j run over the 3 flavours, and the indices α,β label the fundamental of SU(2).Table 1
The set of elementary gauge invariant operators for the electroweak sector of the MSSM.
TypeExplicit sumIndexNumberLHLαiHβϵαβi=1,2,33HH¯HαH¯βϵαβ1LLeLαiLβjekϵαβi,j=1,2,3;k=1,…,j-19LH¯eLαiH¯βϵαβeji,j=1,2,39ννii=1,2,31To compute theF-terms we require the superpotential. Let us take the most general renormalizable form which is compatible with the symmetries of the theory and R-parity(5.3)Wminimal=C0∑α,βHαH¯βϵαβ+∑i,jCij3ei∑α,βLαjH¯βϵαβ+∑i,jCij4νiνj+∑iCij5νi∑α,βLαjHβϵαβ.
Here ϵ is the invariant tensor of SU(2) and C0, Cij3, Cij4, and Cij5 are constant coefficients.We now just follow the procedure outlined at the begining of this section. We calculate theF-terms by taking derivatives of the superpotential, we label the gauge invariant operators S1 to S23, we form (5.2), and then we simply run the elimination algorithm given in Section 2.The result is, upon simplification, given by six quadratic equations in 6 variables. It is a simple description of an affine version of a famous algebraic variety—the Veronese surface [1, 2]. What can be done with such a result? The first observation we can make is that this vacuum space is not a Calabi-Yau. This means, for example, that one can say definitively that it is not possible to engineer this theory by placing a single D3 brane on a singularity in a Calabi-Yau manifold, without having to get into any details of model building.Secondly one can study such vacuum spaces in the hope of finding hints at the structure of the theory's higher energy origins. In the case we have studied in this section, for example, we can “projectivize” (pretend the GIOs are homogeneous coordinates on projective space rather than flat space coordinates) and study the Hodge diamond of the result. The structure of supersymmetric field theory tells us that this Hodge diamond should depend on 4 arbitrary integers, but there is nothing at low energies which prevents us from building theories with any such integers we like. Interestingly, in the case of electroweak theory, these integers are all zero or one:(5.4)hp,q=h0,0h0,1h0,1h0,2h1,1h0,2h0,1h0,1h0,0=100010001.Whether this structure is indeed a hint of some high energy antecedent or just a reflection of the simplicity of the theory is debatable. This example does, however, demonstrate the idea of searching for such evidence of new physics in vacuum space structure. We should also add here that similar techniques can be used to show that the vacuum space of SQCD is a Calabi-Yau [6–8].


## 6. Final Comments

To conclude we will make several points—one of which is a note of caution, with the rest being more optimistic. The first point which we will make is that we should be careful lest the above discussion makes the algorithm we have been describing sound like an all-powerful tool. There is, as ever, a catch. In this case it is the way the algorithm scales with the complexity of the problem. A “worst case” upper bound for the degree of the polynomials in areduced Gröbner basis can be found in [36]. If d is the largest degree found in your original set of equations, then this bound is
(6.1)2(d22+d)2n-1,wheren is the number of variables. This worst case bound is therefore scaling doubly exponentially in the number of degrees of freedom. These very high-degree polynomials are an indication that the problem is becoming very complex and thus computationally intensive. Despite this, physically useful cases can be analysed using this algorithm quickly, as demonstrated in this paper and in the references. This scaling does mean that one is not likely to gain much by putting one's problem on a much faster computer. One good point about (6.1) is that if you can find a way, using physical insight, to simplify the problem under study, then what you can achieve may improve doubly exponentially. Such a piece of physical insight was one of the keystones of the application of these methods to finding flux vacua [11–14].We finish by commenting that the methods of computational commutative algebra which we have discussed here are extremely versatile. We have been able to perform three very different tasks simply utilizing one algorithm in a very simple manner. These methods are of great utility in problems taken from the literature, and their implementation in a user friendly way in Stringvacua means that they may be tried out on any given problem with very little expenditure of time and effort by the researcher. Many more techniques from the field of algorithmic commutative algebra could be applied to physical systems than those described here or indeed in the physics literature. We can therefore expect that this subject will only increase in importance in the future.



---

*Source: 217035-2011-05-10.xml*