Äîêóìåíò âçÿò èç êýøà ïîèñêîâîé ìàøèíû. Àäðåñ îðèãèíàëüíîãî äîêóìåíòà : http://www.mccme.ru/~smirnoff/papers/snapshot.pdf Äàòà èçìåíåíèÿ: Sat Jan 16 07:43:30 2016 Äàòà èíäåêñèðîâàíèÿ: Sun Apr 10 13:00:05 2016 Êîäèðîâêà:

Snapshots of modern mathematics from Oberwolfach

8/2015

Ideas of Newton-Okounkov bodies

Va l e n t i n a K i r i t c h e n k o · E v g e n y S m i r n o v Vladlen Timorin

In this snapshot, we will consider the problem ing the number of solutions to a given system nomial equations. This question leads to the of Newton polytopes and Newton-Okounkov of which we will give a basic notion.
1 Preparator y considerations: one equation

of findof polytheory bodies

The simplest system of polynomial equations we could consider is that of one polynomial equation in one variable: P (x) = aN xN + aN
-1

x

N -1

+ . . . + a0 = 0

(1)

Here a0 , a1 ,. . ., aN R are real numbers, and aN = 0 is (silently) assumed. The number N is the degree of the polynomial P . We might wonder: how many solutions does this equation have? We can extend (1) to a system of d equations which is of the form P1 (x1 , . . . , xd ) = 0 P2 ( x 1 , . . . , x d ) = 0 ... Pd (x1 , . . . , xd ) = 0, for some arbitrary positive integer d. Here, P1 , P2 , . . . , Pd are polynomials in d variables x1 , x2 , . . . , xd and the number of variables is always equal to the number of equations. In the following sections, we will extensively deal with the case d = 2. For the moment, though, let's keep the case of one equation as in (1) and try to answer the question we posed before.

1


1.1 The number of solutions

At first, consider the following example: Example 1. The equation xN - 1 = 0 has two real solutions, namely ±1, if N is even and one real solution, 1, if N is odd. However, the complex 1 solutions are just the N th roots of unity 2 , hence, the number of complex solutions is N . This example illustrates the following general facts: The number of complex solutions of a polynomial equation as in (1) is equal to the degree of P . This statement generally follows from the Fundamental Theorem of Algebra : a polynomial P of degree N has exactly N complex roots 3 when the counting of multiplicities, the number of times a root occurs, is implied. Put in other words, P (x) can be written as P (x) = (x - c1 )n1 (x - c2 )n2 . . . (x - ck )nk where n1 + . . . + nk = N . The roots of the polynomial are then the complex numbers c1 , . . . , ck and they have integer multiplicities n1 , . . . , nk , respectively. If ni 2, ci is said to be a multiple root.
1.2 Generic polynomials and discriminants

Now that we know about the total number of solutions, we are interested in a way to distinguish between polynomials with multiple roots and such that have pairwise distinct roots, that is, N roots with no root equal to any other. Again, consider an example: Example 2. The roots of the quadratic equation ax2 + bx + c = 0 can be found by means of a well-known formula: -b ± b2 - 4ac x± = . 2a This formula was obtained in the IX-th century by the Persian mathematician Muhammad ibn Musa al-Khawarismi. If the discriminant D = b2 - 4ac of the equation is not zero, then there are two distinct complex roots x+ = x- and ax2 + bx + c = a(x - x+ )(x - x- ). If the discriminant is zero, then there is only one root x = 2ba of multiplicity two, that is, ax2 + bx + c = a(x - 2ba )2 .
that is from the complex numbers C; for a definition and if you want to learn more about the field of complex numbers, you might want to have a look at the first section of the snapshot What does ">" real ly mean? by Bruce Reznick, Snapshots of modern mathematics (2014), no. 4, 1­3, available at http://www.mfo.de/math- in- public/snapshots/ files/what- do es- really- mean. The N th ro ots of unity are the N complex numb ers e2i N , k {0, . . . , N - 1}. 3 Generally, solutions to a p olynomial equation P (x) = 0 are also called roots of the p olynomial P (x).
2
k

1

2


In this sense, the discriminant is a polynomial function dependent on the coefficients a, b, c. Via the value it takes for a specific set of coefficients, it distinguishes between polynomials with pairwise distinct roots and such with multiple roots. The notion of discriminant can be extended to polynomials of degree N > 2: there is a polynomial function D(a0 , . . . , aN ) such that the following holds: a general polynomial equation such as (1) has N pairwise distinct complex solutions if and only if D(a0 , . . . , aN ) = 0. Polynomials of degree N that have N pairwise distinct roots are generic, or in general position, among all polynomials of degree N in the following sense: a small perturbation of the coefficients of such a polynomial does not change the number of its pairwise distinct complex roots. Why this? Easily, we can check this via the discriminant. Indeed, if D(a0 , . . . , aN ) = 0 then D(a0 + 0 , . . . , aN + N ) = 0 for all sufficiently small 0 ,. . ., N . In other words, we could say, generic polynomials are polynomials which are stable under small perturbations of the coefficients. Note that polynomials with multiple roots are never generic. For instance, xN has a root of multiplicity N at 0, but xN - has N pairwise distinct roots for any however small = 0. Hence, a polynomial with a multiple root is unstable: no matter how small the perturbation is, it may destroy a multiple root and change the number of pairwise distinct roots. In fact, this is the only thing that can happen to the roots of a polynomial as long as the degree stays fixed. Under perturbations, distinct roots can collide and form multiple roots (or vice versa) but they cannot disappear. This means, roots move continuously. Using this fact one may formulate a conservation of number principle : the number of roots of a polynomial is always the same provided that we count multiplicities. It can be used to prove the Fundamental Theorem of Algebra stated above. Various versions of this principle hold in the multidimensional case as well. The only bad thing that can happen is that a root escapes to infinity. However, in this case, the degree of the polynomial effectively drops. 4
1 . 3 N o n ze r o s o l u t i o n s a n d l e n g t h s o f i n t e r va l s

Before we delve into the involved multidimensional world, let us make one more observation. Fixing the degree of a polynomial P means fixing the order of its highest term. What if we fix the order of the lowest term? Suppose that
4 If n=1 like a looks

you draw, for example, the polynomial x2 (x - n)2 for increasing values of n, that is , 2, 3, 4, . . . you will recognize that for very large n the graph of the polynomial looks parabola, at least in the vicinity of 0. This means, effectively, for n going to infinity, it like the graph of a quadratic p olynomial.

3


the lowest monomial in P is xM . What can be said about the roots of P ? For P = xM , the answer is very simple: the root 0 has multiplicity M . We may now consider a polynomial whose terms start with xM and go all the way up to xN , M < N . Such a polynomial has 0 as a root of multiplicity M , and it has N - M roots in C - {0}, the complex plane without the point 0. Note that, incidentally, the number of roots in C - {0} is equal to the length N - M of the interval [M , N ] on the real line. This last statement has a nice multidimensional generalization obtained by A. Kouchnirenko in the 1970s which we will learn more about in Section 3.

2 B È z o u t 's t h e o r e m
After having discussed the one-dimensional case, d = 1, extensively, we proceed to systems of several equations. Although, to keep the ideas simple, we only discuss the case d = 2. This means, we now look for the number of complex solutions of a polynomial system with two unknowns x and y of the form P (x, y ) := am,n xm y n = 0; m,nN (2) Q(x, y ) := bm,n xm y n = 0.
m,nN

Here, the coefficients am,n , bm,n again are real numbers 5 . P (x, y ) and Q(x, y ) are polynomials, that is, only finitely many of the coefficients am,n and bm,n are nonzero. Correspondingly as in one dimension, the degree deg P of a polynomial P (x, y ) = am,n xm y n is defined as max{m + n | am,n = 0}.
m,nN

In order to gain some understanding about the nature of solutions to such systems, we start with an example: Example 3. Consider the system of linear equations a1,0 x + a0,1 y + a0,0 b1,0 x + b0,1 y + b0,0 = 0; = 0.

As you might know from the theory of linear algebra, there are three cases to distinguish: the system has one solution (if the determinant a1,0 b0,1 - a0,1 b1,0 = 0), infinitely many solutions, or no solution. We can interpret the problem of finding solutions to the above system geometrically. The equations P (x, y ) = 0
5 all ideas discussed throughout this snapshot can b e extended to p olynomials with complex coefficients. We here keep the real coefficients in order not to produce unnecessary complications.

4


and Q(x, y ) = 0 define two lines in the x-y -plane (where both x and y are complex!), and the three cases then appear as follows: two lines intersect at one point, coincide, or are parallel. From this geometric point of view we also recognize in which case the system is a generic system ­ without using any discriminant condition. Indeed, only the first case is generic since it is stable under small perturbations: if we perturb two distinct intersecting lines, then they still remain distinct and intersecting. This is not true for the other cases. Note that, if the two lines become parallel, we may think of their intersection point, and equivalently the root of this system, escaping to infinity. We can summarize this example as follows: a generic system of linear equations has a unique solution. Let us now consider a generic pair of polynomials P (x, y ) and Q(x, y ) of general degrees M and N , respectively. Similarly to the one-dimensional case, the condition of being generic can be made precise by using multidimensional versions of discriminants, but this is out of scope of the present text. How many solutions does a generic system P (x, y ) = Q(x, y ) = 0 have? Again, as in Example 3, we can view this algebraic problem as a geometric one: the equations P (x, y ) = 0 and Q(x, y ) = 0 define curves in the plane, for which the lines in Example 3 were a special case; the problem of finding solutions is then reduced to finding the intersection points of the two curves. If M = 1 or 2 this problem can in certain cases be reduced to the Fundamental Theorem of Algebra as becomes clear from the following example: Example 4. If P (x, y ) = xy - 1, and Q(x, y ) is a generic polynomial of degree N , then the number of solutions is equal to 2N . Indeed, if P (x, y ) = 0, then 1 y = x . Speaking geometrically, the hyperbola {xy - 1 = 0} admits a rational 1 parametrization x (x, x ). Substituting this into Q(x, y ) = 0, we obtain 1 the equation Q(x, x ) = 0 on x. The latter equation has 2N solutions by the 1 Fundamental Theorem of Algebra applied to the polynomial xN Q(x, x ). 6 With the previous considerations at hand, the reader may already have guessed the general answer. It is called the BÈzout theorem to give credit to an influential work of BÈzout of 1779; however, it was stated by Newton more than a century earlier, in 1687, in his treatise "Mathematical foundations of Natural Philosophy". Theorem 1 (BÈzout, 1779). The number of complex solutions of a generic system (2) is equal to deg P · deg Q.
6 For further reading we suggest Undergraduate Algebraic Geometry by Miles Reid [7] which covers topics related to this example (and many more). For example, Sections 1.1 and 1.2 discuss rational parametrizations of conic sections and the nonrationality of elliptic curves, resp ectively.

5


If the system is not generic, then it either has an infinite number of solutions or the number of solutions is strictly less than deg P · deg Q. Here is an example of a generic system whose number of solutions is easy to compute: (x - 1)(x - 2) . . . (x - M ) = 0; (y - 1)(y - 2) . . . (y - N ) = 0. To prove BÈzout's theorem it is sufficient to show that any generic system can be continuously deformed to this one above without having roots collide or escape to infinity.
2.1 A refined notion of genericity

What about the systems that are not generic? We have already mentioned that such a system has a number of solutions which is either infinite or strictly less than deg P · deg Q, yet, it would be more satisfying to give a more specific answer. Consider the system P (x, y ) := a1,1 xy + a1,0 x + a0,1 y + a0,0 = 0; Q(x, y ) := b1,1 xy + b1,0 x + b0,1 y + b0,0 = 0. (3)

Any system of type (3) can be solved explicitly, and the number of solutions is either infinite or does not exceed two. Solving this system amounts to intersecting hyperbolas with horizontal and vertical asymptotes. Two such distinct and non-touching hyperbolas intersect in two points, similarly to the fact that any two distinct and non-touching circles intersect in two points. There should have been four solutions if BÈzout's theorem were applicable to such a system. However, systems of type (3) are not generic among all systems with M = N = 2. Namely, a small perturbation P (x, y ) P (x, y ) + x2 increases the number of solutions without changing M and N . Can we refine BÈzout's statement so that to make it applicable to systems of type (3)? It turns out, yes, indeed, there is a generalization to the theorem. First, we may put more restrictions on small perturbations and by that generalize the set of systems we call "generic": We define the support S (P ) of P as the set of points (m, n) in the real plane R2 such that am,n = 0. By definition all points in the support have integer coordinates. The support S (P ) partially encodes the polynomial P : it tells us which monomials xm y n occur in P but does not specify the coefficients am,n belonging to these monomials. Let us now refine our notions of genericity and stability, and say that a system is generic if it is stable under all perturbations which do not enlarge the support of the polynomials P (x, y ) and Q(x, y ). In particular, the perturbation of system (3) which changes P (x, y ) P (x, y ) + x2

6


for = 0 is not allowed because neither P (x, y ) nor Q(x, y ) have a term with x2 . We could also say, the system is generic within the space of polynomials with support contained in S (P ) S (Q). It is easy to check that if a system of type (3) has exactly two solutions, then the allowed perturbations do not change the number of solutions. Second, we generalize the notion of the degree of a polynomial. This refined degree is no longer a number but a polygon!

3 Newton polygons
Consider a polynomial in two variables P (x, y ) :=
m,nN

a

m,n

xm y n = 0.

Again, for P being a polynomial we require that the coefficients am,n are nonzero for finitely many (m, n) only. Furthermore, the degree of P is already completely determined by the support S (P ). Namely, it is the maximal value the linear function f : R2 R defined by f (m, n) := m + n attains on S (P ). Example 5. If P (x, y ) = 1 + 2xy 2 + 3x3 y then S (P ) = {(0, 0), (1, 2), (3, 1)}. It is easy to check that the function m + n attains the maximal value on S (P ) at the point (3, 1). Hence, the degree of P is equal to 3 + 1 = 4. Moreover, we can replace the support by any larger set with the following property: for any linear function f , the maximal value of f on S (P ) coincides with the maximal value of f on . Then the degree of P is determined by . The largest set (P ) with such property is called the Newton polygon of P . It is a convex polygon. We say a set is convex if for any two points p1 and p2 that lie in , the line segment [p1 , p2 ] also lies in . Alternatively, the Newton polygon (P ) can be defined as the smallest convex polygon that contains the support S (P ) (see Figure 1). 7 Exercise 1. Verify that in one dimension, the Newton polygon (P ) of a polynomial P (x) = aN xN + . . . + aM xM is a straight line, that is, an interval on the real axis. What length does this interval have? The classical degree satisfies the following additivity property: if P and Q are polynomials, then deg(P · Q) = deg(P ) · deg(Q). You will verify this very
7 Think ab out why these definitions really are equivalent. You can find more ab out convex polygons in An Introduction to Convex Polytopes by Arne BrÜnsted [2].

7


F i g u r e 1 : The supp ort (red p oints) and the Newton p olygon (blue surface) of

the polynomial 2xy + x2 y + 3x4 y + 5x2 y 2 + xy 3 .

easily. Newton polygons satisfy a similar property. Define the Minkowski sum of sets 1 and 2 in the plane as 1 + 2 = {p1 + p2 | p1 1 , p2 2 }, where p1 + p2 means the usual vector addition, that is, if p1 = (x1 , y1 ) and p2 = (x2 , y2 ), then p1 + p2 = (x1 + x2 , y1 + y2 ) (see Figure 2). Exercise 2. Show that (P · Q) = (P ) + (Q). A word of warning: if we consider supports instead of Newton polygons, then the additivity property fails as seen in the following example: Example 6. Let P (x, y ) = x + y and Q(x, y ) = x - y . Then P · Q = x2 - y 2 . We have S (P ) = {(1, 0), (0, 1)} = S (Q) and S (P · Q) = {(2, 0), (0, 2)}. However, S (P ) + S (Q) = {(2, 0), (1, 1), (0, 2)}, hence, S (P ) + S (Q) = S (P · Q). This is one of the reasons for which Newton polygons are easier to handle than just supports.
3.1 Laurent polynomials

Observe that the Newton polygons are all contained in the first quadrant of the plane R2 due to the nonnegative integer coordinates of the points (m, n). From a geometric perspective, this is an unnecessary restriction which in fact obscures the situation. Let us thus take a look at the so called Laurent polynomials, a

8


F i g u r e 2 : Minkowski sum of two triangles.

natural generalization of the concept of polynomial in our context. We do so via their Newton polynomials which may now be in a general position in the real plane R2 . Let be a lattice polygon in the plane (lattice means that the vertices of have integer coordinates). Consider all polynomials P , whose support is contained in . Since may contain points with negative integer coordinates, it is natural to consider not only polynomials but also Laurent polynomials. A Laurent polynomial is a finite sum P (x, y ) :=
m,nZ

a

m,n

xm y n = 0,

where m and n are allowed to be negative. The values of Laurent polynomials are well-defined for all (x, y ) such that x, y = 0 (we call such (x, y ) total ly nonzero). The definition of the support and the Newton polygon goes verbatim for Laurent polynomials. Let V () be the space of all Laurent polynomials whose support is contained in . Then we can define a notion of a generic system with respect to V (). Let P, Q V (). The system P = Q = 0 is generic if its number of solutions does not change under any sufficiently small perturbation of P and Q within the space V (). Again it is true that non-generic systems are not stable, that is, any non-generic system can be made generic by a very very small perturbation.
3 . 2 A t h e o r e m b y Ko u c h n i r e n k o

We now assembled all necessary ingredients and can formulate a beautiful theorem due to Kouchnirenko [4].

9


Theorem 2 (Kouchnirenko, 1975). The number of total ly nonzero complex solutions of a generic system P (x, y ) = 0; Q(x, y ) = 0; of Laurent polynomials with (P ) = (Q) = is equal to 2Area(). Example 7. Consider a generic system of type (3). It is generic with respect to V (), where is the unit square with the vertices (0, 0), (1, 0), (0, 1) and (1, 1). Hence, the number of solutions is equal to 2Area() = 2. Exercise 3. Deduce the BÈzout theorem in the case M = N from the Kouchnirenko theorem. The Kouchnirenko theorem can be extended to polynomials with different Newton polygons. This was done by D. Bernstein [1]. Theorem 3 (Kouchnirenko-Bernstein, 1975). The number of total ly nonzero solutions of a generic system (4) with (P ) = 1 and (Q) = 2 is equal to Area(1 + 2 ) - Area(1 ) - Area(2 ). This expression is cal led the mixed area of the two polygons 1 and 2 . Exercise 4. Check the above Kouchnirenko-Bernstein theorem for polynomials P (x, y ) = aN xN + aN -1 xN -1 + . . . + a0 and Q(x, y ) = bM y M + bM -1 y M -1 + . . . + b0 . Hint: The area of a degenerate polygon (here meaning a polygon that is entirely contained in a straight line) is zero. (4)

4 Newton-Okounkov bodies
Let us look at the Kouchnirenko theorem from another viewpoint. Instead of starting with a polynomial P and its associated Newton polygon (P ) we could have started from a finite set A = {P1 , . . . , P } of Laurent monomials, that is, Pi (x, y ) = xmi y ni , with mi , ni Z. Next, we can define the Newton polygon to the set A, (A) as the minimal convex polygon that contains all points (m, n) such that xm y n A. Consider the space V (A) of all possible linear combinations P (x, y ) = a1 P1 (x, y ) + . . . + a P (x, y ), where coefficients a1 ,. . ., a are complex numbers. A system of polynomials in V (A) is called generic if its number of solutions does not change under any

10


sufficiently small perturbations of the single polynomials within the space V (A). Then Kouchnirenko's theorem can be rephrased as follows: a generic system P (x, y ) = Q(x, y ) = 0 with P, Q V (A) has 2Area((A)) solutions. A natural generalization of the above situation is to consider a finite set A = {P1 , . . . , P }, where P1 ,. . ., P are now arbitrary polynomials or even rational functions of x and y . Is there an analog of Kouchnirenko's theorem? How to define a Newton polygon (A)? These questions bring us to the theory of Newton-Okounkov convex bodies. The construction of Newton-Okounkov bodies is due to A. Okounkov [6], and the general theory and its applications to algebraic and convex geometry were developed by K. Kaveh-A. Khovanskii [3] and R. Lazarsfeld-M. Mustata [5]. Example 8. Take A = {1, x, y , x2 + y 2 }. A generic system P (x, y ) = Q(x, y ) = 0 with P, Q V (A) has the form a4 (x2 + y 2 ) + a3 y + a2 x + a1 = 0; b4 (x2 + y 2 ) + b3 y + b2 x + b1 = 0. (4)

Solving this system amounts to intersecting two circles, hence, the number of solutions is two. Note that Kouchnirenko's theorem is not applicable here: twice the area of the Newton polygon of P (and Q) is equal to four, not two. However, the theory of Newton-Okounkov bodies applies. We now associate with A a Newton-Okounkov polygon N O (A). Let us order monomials that occur in P V (A). For instance, order them as words in a dictionary with the understanding that x2 = xx and y 2 = y y 1 x x
2

y

y2 .

The ordering has to satisfy certain natural assumptions, say, we should be able to multiply both sides of an inequality by a monomial and still preserve the inequality, but otherwise it is arbitrary. Assign to every P A the smallest (with respect to the chosen ordering) monomial occuring in P . In this way, we obtain monomials 1, x, y and x2 . Finally, take the Newton polygon of these monomials. This is the triangle with vertices (0, 0), (2, 0), (0, 1). It is called the Newton-Okounkov polygon of A and is denoted by N O (A). Note that twice the area of N O (A) is exactly two, which coincides with the number of solutions of a generic system of type (4). The construction of N O (A) depends on certain choices. For instance, we could have assigned to every P A the greatest monomial rather than the smallest one, or we could have used a different ordering of the monomials. Then we would obtain a different Newton-Okounkov polygon (for example, the triangle with vertices (0, 0), (1, 0), (0, 2)) but it can be shown that the area of this Newton-Okounkov polygon would be the same as that of our choice.

11


References
[1] D. N. Bernstein, The number of roots of a system of equations, Funct. Anal. Appl. 9 (1975), no. 3, 183­185. [2] A. BrÜnsted, An introduction to convex polytopes, Springer-Verlag, New York, 1983. [3] K. Kaveh and A. G. Khovanskii, Newton-Okounkov bodies, semigroups of integral points, graded algebras and intersection theory, Ann. of Math. (2) 176 (2012), no. 2, 925­978. [4] A. G. Kouchnirenko, PolyÕdres de Newton et nombres de Milnor, Invent. Math. 32 (1976), no. 1, 1­31. [5] R. Lazarsfeld and M. Mustata, Convex bodies associated to linear series, Ann. Sci. èc. Norm. SupÈr. (4) 42 (2009), no. 5, 783­835. [6] A. Okounkov, Brunn-Minkowski inequality for multiplicities, Invent. Math. 125 (1996), no. 3, 405­411. [7] M. Reid, Undergraduate algebraic geometry, London Mathematical Society Student Texts, vol. 12, Cambridge University Press, Cambridge, 1988.

12


Va l e n t profes Resea Econo

ina sor rch mic

Kir itchenko is an associate of mathematics at the National U n i ve r s i t y H i g h e r S c h o o l o f s , M o s c o w.

Vladlen Timorin is a professor of mathematics at the National Research U n i ve r s i t y H i g h e r S c h o o l o f E c o n o m i c s, M o s c o w. Mathematical subjects Algebra and Number Theor y License C r e a t i v e C o m m o n s B Y- S A 4 . 0 DOI 10.14760/SNAP-2015-008-EN

Evgeny Smir nov is an associate professor of mathematics at the National Research U n i ve r s i t y H i g h e r S c h o o l o f E c o n o m i c s, M o s c o w.

Snapshots of modern mathematics from Oberwolfach are written by participants in the scientific program of the Mathematisches Forschungsinstitut Oberwolfach (MFO). The snapshot project is designed to promote the understanding and appreciation of modern mathematics and mathematical research in the general public worldwide. It is part of the mathematics communication project "Oberwolfach meets IMAGINARY" funded by the Klaus Tschira Foundation and the Oberwolfach Foundation. All snapshots can be found on www.imaginary.org and on www.mfo.de/snapshots.

Junior Editor S a b i h a To k u s j u n i o r - e d i t o r s @ m f o. d e Senior Editor Carla Cederbaum c e d e r b a u m @ m f o. d e

M a t h e m a t i s c h e s Fo r s c h u n g s i n s t i t u t Oberwolfach gGmbH S c h w a r z w a l d s t r . 9 ­ 11 77709 Oberwolfach Ger many Director Gerhard Huisken