BERNSTEIN’S THEOREM OVER FIELDS WITH DISCRETE VALUATION

VICTOR REINER AND STEVEN SPERBER

Abstract. For fields complete with respect to a discrete valuation, we prove a refinement of Bernstein’s theorem counting the generic number of solutions to a system of n polynomial equations in n unknowns. The refinement predicts the number of solutions whose coordinates have given valuations, generalizing to several variables the classical use of Newton polygons for determining the valuations of the roots of a polynomial in one variable.

with an appendix by William Messing

1. Introduction

This paper is about a common generalization of two well-known results related to root-counting of polynomial systems and Newton polytopes. One of these results is Bernstein’s theorem and the other is the classical theorem on the Newton polygon of a polynomial (or Laurent polynomial) in one variable over a completely valued field. The generalization has the same spirit as (and also generalizes) Khovanskiǐ’s “Curve Theorem” [8, Theorem 27.7.11].

We first recall Bernstein’s Theorem [2]. Let A_{1}, …, A_{n} be finite subsets of ℤ^{d}. Consider a collection f of Laurent polynomials f_{1}, …, f_{n} such that for each i, the exponent vectors of monomials occurring in f_{i} lie in A_{i}. Let P_{i} denote the polytope which is the convex hull of A_{i}. Bernstein’s Theorem states that, for suitably general collections f, the number of common zeros (counting multiplicities) of f_{1}, …, f_{n} in the complex torus (ℂ^{×})^{n} is the Minkowski mixed volume M(P_{1}, …, P_{n}). Recall [5, §5.4] that the mixed volume may be defined as follows: when one dilates each P_{i} by an independent positive scalar λ_{i} and forms the Minkowski sum ∑_{i=1}^{n} λ_{i}P_{i}, the n-dimensional volume of ∑_{i=1}^{n} λ_{i}P_{i} turns out to grow as a homogeneous polynomial function of degree n in the λ_{i}’s, and M(P_{1}, …, P_{n}) is defined to be the coefficient of the monomial λ_{1} ⋯ λ_{n} in this polynomial.

For our purposes, the most convenient version of Bernstein’s Theorem is the following special case of a result of Rojas [11] (see also [9]), which is valid over arbitrary algebraically closed fields. Let x = (x_{1}, …, x_{n}) denote a vector of variables. We use the exponential notation x^{a} := x_{1}^{a_{1}} ⋯ x_{n}^{a_{n}} with a ∈ ℤ^{n} for monomials in the Laurent polynomial ring k[x, x^{−1}] := k[x_{1}, x_{1}^{−1}, …, x_{n}, x_{n}^{−1}].

Key words and phrases. Bernstein’s theorem, mixed volume, Newton polygon, discrete valuation.

First author partially supported by NSF grant DMS-9877047.

Theorem 1. Let k be an algebraically closed field, A = {A_{i}}_{i=1}^{n} a collection of finite subsets in ℤ^{n}, with P_{i} the convex hull of A_{i}. For i = 1, …, n, let

f_{i} := ∑_{a∈A_{i}} c_{i,a}x^{a} ∈ k[x, x^{−1}].

Then on a non-empty Zariski-open subset U of the moduli space of such polynomials (that is, the affine space 𝔸_{k}^{|A_{1}|} × ⋯ × 𝔸_{k}^{|A_{n}|} of coefficients (c_{i,a})), the system

f_{1}(x) = ⋯ = f_{n}(x) = 0

has only isolated solutions x^{∗} in the torus (k^{×})^{n}, and there are M(P_{1}, …, P_{n}) such solutions, counted with multiplicity.

The set U is defined by the following genericity conditions: for every choice of γ ∈ ℚ^{n} − {0}, there are no solutions in (k^{×})^{n} for the initial system

in_{γ}(f_{1}) = … = in_{γ}(f_{n}) = 0,

where

in_{γ}(f_{i}(x)) := ∑_{a∈A_{i}: γ·a is minimal} c_{i,a}x^{a}. □

See [2] for a discussion of why the genericity conditions stated in the theorem actually are generic, that is, why they define a subset U which is non-empty and Zariski-open. For convenience, we will abbreviate by f = 0 and in_{γ}(f) = 0 the polynomial systems which appear in the above theorem.

The second result to be generalized is the classical theorem on valuations of roots of a (Laurent) polynomial in one variable over a field complete with respect to an ultrametric valuation. Let K be the fraction field of a discrete valuation ring 𝔬_{K}, having unique maximal ideal 𝔪_{K}. It will be convenient for us to use the additive form of this valuation

ord : K → ℤ ∪ {∞}

defined on 𝔬_{K} by

ord(x) = \begin{cases}min\{N| x ∈ (𝔪_{K})^{N}\} for x ∈ 𝔬_{K} − \{0\} \\ ∞ for x = 0 \end{cases}

then extended to K by ord(\frac{x}{y}) = ord(x) − ord(y). This valuation satisfies the ultrametric (or non-Archimedean) inequality

(1)  ord(x + y) ≥ min(ord(x), ord(y)).

The logarithm of ord defines an absolute value and a metric on K making it a topological field, and we assume that K is complete with respect to this metric. A standard result [1] asserts that ord has a unique extension to the algebraic closure of K (taking values in ℚ∪{∞}) and hence also to the completion L of this algebraic closure.

For our purposes, we state the classical theorem on Newton polygons for Laurent polynomials, and in terms most amenable to multivariate generalization. Theorem 2. [1] Given a Laurent polynomial f(x) = ∑_{a∈ℤ} c_{a}x^{a} ∈ K[x, x^{−1}], define

Â:= {(a, ord(c_{a}))}_{c_{a}≠0}

a finite collection of points in ℤ × ℤ.

Then for any γ ∈ ℚ, the number of solutions x^{∗} ∈ L^{×} to f(x) = 0 having ord(x^{∗}) = γ, counted with multiplicity, is the length of the projection to the first coordinate axis of the face in the (lower) convex hull of Â on which the dot product with (γ, 1) is minimized. □

Theorem 4 below is a generalization of Theorem 1 (when we view a field K as endowed with the trivial valuation ord(x) = 0 for all x ∈ K^{×}) and Theorem 2 (when n = 1). Its statement and proof bear a close resemblance to certain proofs of Bernstein’s Theorem (e.g. [2, 6]) and in particular to Khovanskiǐ’s “Curve Theorem” [8, Theorem 27.7.11], which it also generalizes. Roughly speaking, these proofs deform the system f(x) = 0 by introducing a new parameter t, and then work with Puiseux expansions for the solutions x(t) of f(x, t) = 0, considered as algebraic functions in the new variable t. In Theorem 4, the roles played by K and its ord function are similar to the roles in these proofs played by the field of formal Laurent series ℂ((t)) and the function ord : ℂ((t)) → ℝ which measures the order of vanishing at t = 0 (see also Remark 13 below).

Although our proof has the disadvantage that it relies on Theorem 1 and hence does not give an independent proof of Bernstein’s Theorem, it has other advantages. It holds for discretely valued fields in all characteristics, not just for Laurent series over ℂ, and it uses a weaker genericity hypothesis than that of [8, Theorem 27.7.11].

We are indebted to W. Messing and J. Roberts for many helpful discussions regarding the proof of a crucial lemma from commutative algebra (Lemma 17). In particular, the Appendix contains a proof of this due to Messing.

2. The theorem

We begin with some notation and preliminaries. As in the introduction, K is a complete field under the metric induced by its valuation ord. Denote by L the completion of its algebraic closure. We denote the residue class field K̄ = 𝔬_{K}/𝔪_{K} and the reduction map 𝔬_{K} → K̄ by x ↦ x̄. Because 𝔪_{K} = 𝔪_{L} ∩ 𝔬_{K}, the inclusion 𝔬_{K} ↪ 𝔬_{L} induces an inclusion K̄ ↪ L̄. We recall [1] that this identifies L̄ with the algebraic closure of K̄.

Extend the ord function to a map on vectors as follows: for x = (x_{1}, …, x_{n}) ∈ (L^{×})^{n}, define ord(x) := (ord(x_{1}), …, ord(x_{n})) ∈ ℚ^{n}. For vectors x = (x_{1}, …, x_{n}) in 𝔬_{L}^{n}, define x̄ := (x̄_{1}, …, x̄_{n}).

We fix once and for all a uniformizing parameter for K, that is, a generator π for the maximal ideal 𝔪_{K} of 𝔬_{K}. None of our assertions will depend in an essential way on the particular choice of π.

Fix a collection A = {A_{i}}_{i=1}^{n} of finite subsets of ℤ^{n}, and a sequence of integers ω = {ω_{i,a} : i = 1, …, n, a ∈ A_{i}}. For each i = 1, …, n define Â_{i} := {(a, ω_{i,a})}_{a∈A_{i}} a finite subset of points in ℤ^{n+1}, and denote the whole collection Â = {Â_{i}}_{i=1}^{n}. We define an Â-system of Laurent polynomials to be a collection f = {f_{i}}_{i=1}^{n} ∈ K[x, x^{−1}]^{n} of the form

f_{i} := ∑_{a∈A_{i}} c_{i,a}π^{ω_{i,a}}x^{a} ∈ K[x, x^{−1}],

where c_{i,a} ∈ 𝔬_{K}. In other words, it is assumed that the Newton polytope of f_{i} is contained in A_{i}, and that each of its coefficients has a fixed lower bound on its ord. We will make frequent reference to the reduced coefficients c̄_{i,a} ∈ K̄.

We also need to define for each γ in ℚ^{n} − {0} a certain reduced initial system of f = 0. Let

\overline{in}_{γ}(f_{i}(x)) := ∑_{a∈A_{i}: (γ,1)·(a,ω_{i,a}) is minimal} c̄_{i,a}x^{a} ∈ K̄[x, x^{−1}].

Let \overline{in}_{γ}(f) = 0 denote the system \overline{in}_{γ}(f_{1}) = ⋯ = \overline{in}_{γ}(f_{n}) = 0. Note that \overline{in}_{γ}(f_{i}) depends implicitly on the choice of Â, although we have chosen to omit this dependence from the notation. Proposition 3. Let f be an Â-system of Laurent polynomials. If x^{∗} ∈ (L^{×})^{n} is a solution to f = 0 having ord(x) = γ ∈ ℚ^{n}, then there exists a solution in (L̄^{×})^{n} to the system \overline{in}_{γ}(f) = 0.

Proof. Let d be a least common denominator for γ, i.e. γ ∈ \frac{1}{d}ℤ^{n}. Fix a d-th root π^{\frac{1}{d}} of π in L, so that one can define π^{α} for any α in \frac{1}{d}ℤ. Since ord(x) = γ, this allows us to write x = (π^{γ_{1}}y_{1}, …, π^{γ_{n}}y_{n}) for some y_{i} ∈ 𝔬_{L}^{×}. One can then check that ȳ := (ȳ_{1}, …, ȳ_{n}) gives the desired solution to \overline{in}_{γ}(f) = 0 as follows:

0 = f_{i}(x^{∗})

= ∑_{a∈A_{i}} c_{i,a}π^{ω_{i,a}}(x^{∗})^{a}

= ∑_{a∈A_{i}} π^{(γ,1)·(a,ω_{i,a})}c_{i,a}y^{a}

Let μ_{i} be the minimal value of (γ, 1) · (a, ω_{i,a}) for a ∈ A_{i}. Then dividing the previous equation by π^{μ_{i}} gives an equation in 𝔬_{K} which reduces in K̄ to

0 = ∑_{a∈A_{i}: (γ,1)·(a,ω_{i,a}) is minimal} c̄_{i,a}ȳ^{a}

= \overline{in}_{γ}(f)(ȳ)
□

As before, let P_{i} denote the convex hull of A_{i} for i = 1, …, n, so that Theorem 1 tells us that (generically) the system f = 0 will have exactly M(P_{1}, …, P_{n}) isolated solutions (counted with multiplicity) in (L^{×})^{n}. Let p : ℝ^{n+1} → ℝ^{n} be the projection onto the first n coordinates. For γ ∈ ℚ^{n} and i = 1, …, n, let P̂_{i}^{γ} be the face of the convex hull of Â_{i} on which the dot product in ℝ^{n+1} with (γ, 1) is minimized, and let P_{i}^{γ} = p(P̂_{i}^{γ}). Note that P_{i}^{γ} need not be a face of P_{i}, and in particular, P_{i}^{γ} should not be confused with the face of P_{i} on which the dot product with γ is maximized. We also note that, by definition of \overline{in}_{γ}(f) and by Theorem 1, generically the system \overline{in}_{γ}(f) = 0 will have exactly M(P_{1}^{γ}, …, P_{n}^{γ}) isolated solutions (counted with multiplicity) in (L̄^{×})^{n}.

We can now state our main result. Theorem 4. Let f be an Â-system of Laurent polynomials over K. On a nonempty Zariski-open subset U in the moduli space 𝔸|A_{1}| ; K̄ × ⋯ × 𝔸|A_{n}| ; K̄ of reduced coefficients in K̄, the system f = 0 has only isolated solutions in the torus (L^{×})^{n}. Furthermore, for each γ ∈ ℚ^{n}, the number of such solutions x^{∗} having ord(x^{∗}) = γ is, counted with multiplicity, the mixed volume M(P_{1}^{γ}, …, P_{n}^{γ}).

The set U may be defined by the following genericity conditions: for every γ ∈ ℚ^{n}, the system \overline{in}_{γ}(f) = 0 has no solutions in (L̄^{×})^{n} whenever M(P_{1}^{γ}, …, P_{n}^{γ}) = 0.

Before proving the theorem, a few remarks are in order about the genericity conditions assumed in the theorem.

Remark 5. (The case of trivial valuation – Bernstein’s Theorem) In the case that the valuation on K is trivial, the genericity conditions above reduce to those of Theorem 1, as we now explain. For each γ ≠ 0, we have that P_{i}^{γ} is the face of P_{i} on which the dot product with γ is minimized and consequently \overline{in}_{γ}(f) = in_{γ}(f). Because each of the faces P_{i}^{γ} lies in a hyperplane perpendicular to γ, the mixed volume M(P_{1}^{γ}, …, P_{n}^{γ}) vanishes by an argument similar to the one given in the proof of Proposition 9 below.

Remark 6. (Dependence upon uniformizing parameter π) Assume we had made a different choice of uniformizing parameter π, say π′ = uπ for u ∈ 𝔬_{K}^{×}. This has the effect of scaling each reduced coefficient c̄_{i,a} by the unit factor ū^{ω_{i,a}}, and hence alters the Zariski open set U by an invertible diagonal transformation.

Also, the genericity hypotheses of the theorem are unchanged: if μ_{i} is the minimum value of the dot product (γ, 1) · (a, ω_{i,a}) for a in Â_{i}, one can check that the invertible transformation x_{i} ↦ ū^{γ_{i}}x_{i} sends \overline{in}_{γ,π}(f_{i}) to ū^{μ_{i}} \overline{in}_{γ,π′}(f_{i}) (where \overline{in}_{γ,π}(−) means \overline{in}_{γ}(−) defined with respect to the uniformizer π).

Remark 7. (Zariski-openness of U) To see that U is non-empty and Zariski-open, first note that even though there are infinitely many γ ∈ ℚ^{n}, there are only finitely many different systems \overline{in}_{γ}(f) = 0, depending on the convex hulls of the finite sets Â_{i} which occur in the system Â.

Now fix one such system \overline{in}_{γ}(f) = 0. Note that its coefficients are a subset of all of the reduced coefficients {c̄_{i,a}} (namely those for which (γ, 1)·(a, ω_{i,a}) is maximized). Hence a non-empty Zariski-open condition on this subset of coefficients gives rise to a non-empty Zariski-open condition on 𝔸|A_{1}| ; K̄ × ⋯ × 𝔸|A_{n}| ; K̄. The conditions stated in Theorem 1 under which \overline{in}_{γ}(f) = 0 will have exactly M(P_{1}^{γ}, …, P_{n}^{γ}) solutions are known to be non-empty and Zariski-open (see [2, 9, 11]). Hence the conditions under which there will be no solutions to \overline{in}_{γ}(f) = 0 if M(P_{1}^{γ}, …, P_{n}^{γ}) = 0 are non-empty and Zariski-open.

The set U in the theorem is then the intersection of these finitely many nonempty Zariski-open subsets indexed by the different systems \overline{in}_{γ}(f) = 0, and hence is non-empty and Zariski-open.

Remark 8. (Alternate genericity conditions) One might be tempted to alter the genericity conditions in the above theorem by adding in the extra hypothesis that the initial systems \overline{in}_{γ}(f) = 0, when they have roots, have only simple roots (cf. the Curve Theorem [8, Theorem 27.7.11]). In particular, one might have in mind to use things like multivariate Newton’s method/Hensel’s lemma to approximate roots of f = 0 starting with the roots of \overline{in}_{γ}(f) = 0. However, note that in characteristic p, for certain choices of Â these roots for the initial system will never be simple. As an example, when n = 1 and K has characteristic p, the equation c_{1}x^{p} +c_{2} = 0 will always encounter this difficulty. Nevertheless, our theorem as stated still applies (regardless of the choice of the minimum ord values ω_{1}, ω_{2} for c_{1}, c_{2}).

The proof of Theorem 4 occupies the remainder of this section. We begin with some simple facts about the commutation of the operations in_{γ} and \overline{in}_{γ}: Proposition 9. For any γ, γ′ in ℚ^{n} and for ϵ > 0 sufficiently small,

(a)

\overline{in}_{γ′}(in_{γ}(f)) = \overline{in}_{ϵ^{−1}γ+γ′}(f)
and M(P_{1}^{ϵ^{−1}γ+γ′}, …, P_{n}^{ϵ^{−1}γ+γ′}) = 0 whenever γ ≠ 0.

(b)

in_{γ′}(\overline{in}_{γ}(f)) = \overline{in}_{γ+ϵγ′}(f)
and M(P_{1}^{γ+ϵγ′}, …, P_{n}^{γ+ϵγ′}) = 0 whenever γ′ ≠ 0.

Proof. Both (a), (b) follow from a basic fact in polyhedral geometry (see e.g. [12, Equation (2.3)]): for any finite subset A of ℝ^{n}, if in_{δ}(A) for δ ∈ ℝ^{n} denotes the subset of A on which the dot product with δ is minimized, then for ϵ > 0 sufficiently small,

in_{δ′}(in_{δ}(A)) = in_{δ+ϵδ′}(A).

Using this new notation, we can rephrase the definitions of in, \overline{in}:

in_{γ}(f_{i}) = ∑_{a∈in_{γ}(A_{i})} c_{i,a}π^{ω_{i,a}}x^{a} = ∑_{(a,ω_{i,a})∈in_{(γ,0)}(Â_{i})} c_{i,a}π^{ω_{i,a}}x^{a}

\overline{in}_{γ}(f_{i}) = ∑_{(a,ω_{i,a})∈in_{(γ,1)}(Â_{i})} c̄_{i,a}x^{a}

We note here a basic fact which will be used below: for any Laurent polynomial f, the initial form in_{γ}(f) only contains monomials which lie on an affine hyperplane on which the dot product with γ is constant (but the same need not be true for \overline{in}_{γ}(f) !).

To show (a), note that from the above rephrasings one has

\overline{in}_{γ′}(in_{γ}(f_{i})) = ∑_{(a,ω_{i,a})∈in_{(γ′,1)}(in_{(γ,0)}(Â_{i}))} c̄_{i,a}x^{a}

and since

in_{(γ′,1)}(in_{(γ,0)}(Â_{i})) = in_{(γ,0)+ϵ(γ′,1)}(Â_{i}) = in_{ϵ^{−1}(γ,0)+(γ′,1)}(Â_{i}) = in_{(ϵ^{−1}γ+γ′,1)}(Â_{i})

the first assertion in (a) follows.

To see the second assertion in (a), note that if γ ≠ 0, then for each i = 1, …, n, by the first assertion in (a), the polytope P_{i}^{ϵ^{−1}γ+γ′} lies in an affine hyperplane in ℝ^{n} on which the dot product with γ is constant. Consequently, any Minkowski sum ∑_{i=1}^{n} λ_{i}P_{i}^{ϵ^{−1}γ+γ′} is a sum of polytopes lying in a family of parallel affine hyperplanes, and thus lies in such an affine hyperplane, implying that it will have zero n-dimensional volume. This implies the vanishing of the the mixed volume M(P_{1}^{ϵ^{−1}γ+γ′}, …, P_{n}^{ϵ^{−1}γ+γ′}).

The proof of (b) is similar. From the above rephrasings, one has

in_{γ′}(\overline{in}_{γ}(f_{i})) = ∑_{(a,ω_{i,a})∈in_{(γ′,0)}(in_{(γ,1)}(Â_{i}))} c̄_{i,a}x^{a}

and since

in_{(γ′,0)}(in_{(γ,1)}(Â_{i})) = in_{(γ,1)+ϵ(γ′,0)}(Â_{i}) = in_{(γ+ϵγ′,1)}(Â_{i})

the first assertion in (b) follows. The second assertion in (b) follows because when γ′ ≠ 0, each P_{i}^{γ+ϵγ′} lies in an affine hyperplane of ℝ^{n} on which the dot product with γ′ is constant. □

The next lemma explains the reason behind the phrasing of the genericity conditions in Theorem 4. Lemma 10. The genericity conditions assumed in Theorem 4 imply both

(a) the genericity needed to apply Theorem 1 with k = L and conclude that f = 0 has exactly M(P_{1}, …, P_{n}) isolated solutions, counted with multiplicities, in (L^{×})^{n}.

(b) the genericity needed to apply Theorem 1 with k = L̄ and conclude that \overline{in}_{γ}(f) = 0 has exactly M(P_{1}^{γ}, …, P_{n}^{γ}) isolated solutions, counted with multiplicities, in (L̄^{×})^{n}, for each γ in ℚ^{n} − {0}.

Proof. For (a), one argues that for any γ ≠ 0 in ℚ^{n}, there can be no solution in (L^{×})^{n} to the system in_{γ}(f) = 0. If x^{∗} were such a solution, and if γ′ = ord(x^{∗}), then Proposition 3 would give rise to a solution in (L̄^{×})^{n} for the system \overline{in}_{γ′}(in_{γ}(f)) = 0, which is the same as the system \overline{in}_{ϵ^{−1}γ+γ′}(f) = 0 by Proposition 9(a). This contradicts the genericity assumption of Theorem 4 by the second assertion of Proposition 9(a).

For (b), one argues that for any γ, γ′ in ℚ^{n} with γ′ ≠ 0, there can be no solution in (L̄^{×})^{n} to the system in_{γ′}(\overline{in}_{γ}(f)) = 0: this is the same as the system \overline{in}_{γ+ϵγ′}(f) = 0 by Proposition 9(b), and it should have no solutions by the second assertion of Proposition 9(b). □

The assertion of Theorem 4 can now be rephrased as the following lemma, after introducing some terminology. Let μ̂_{γ} denote the (finite) number of solutions x^{∗} to f = 0 in (L^{×})^{n} having ord(x^{∗}) = γ, counted with multiplicity. Let μ_{γ} denote the (finite) number of solutions x̄^{∗} to \overline{in}_{γ}(f) = 0 in (L̄^{×})^{n}, counted with multiplicity. Recall that by Lemma 10 part (b), we have μ_{γ} = M(P_{1}^{γ}, …, P_{n}^{γ}). Lemma 11. Under the assumptions of Theorem 4,

μ̂_{γ} = μ_{γ}(= M(P_{1}^{γ}, …, P_{n}^{γ}))

for all γ ∈ ℚ^{n} − {0}.

Proof. We first explain why there only finitely many γ ∈ ℚ^{n} − {0} for which either μ̂_{γ} or μ_{γ} are non-zero. Since μ̂_{γ} ≠ 0 implies μ_{γ} ≠ 0 by Proposition 3, we need only consider when μ_{γ} is non-zero.

For μ_{γ}, this follows from the method of coherent mixed subdivisons for calculating the mixed volume M(P_{1}, …, P_{n}) which is used in [6]. This method involves lifting each point a in A_{i} ⊂ ℝ^{n} to a generic height w_{i,a} in ℝ^{n+1}, and then computing the volumes of certain projected faces of the Minkowski sum of the convex hulls of these lifted sets A_{i}. If the heights w_{i,a} are chosen to be generic perturbations of our given integers ω_{i,a}, the following equality of mixed volumes results:

(2)  M(P_{1}, …, P_{n}) = ∑_{γ} M(P_{1}^{γ}, …, P_{n}^{γ}),

where γ ranges over the finite subset Γ ⊂ ℚ^{n} − {0} consisting of those γ for which (γ, 1) is a normal vector of some n-dimensional face of the Minkowski sum conv(Â_{1}) + ⋯ + conv(Â_{n}). This theory also predicts that M(P_{1}^{γ}, …, P_{n}^{γ}) = 0 for any γ outside of this finite set Γ, and hence μ_{γ} = 0 for such γ.

We next claim that it suffices to show the seemingly weaker inequality

(3)  μ̂_{γ} ≤ μ_{γ} for every γ ∈ Γ.

To see this claim, note that assuming (3), we would have

M(P_{1}, …, P_{n}) = ∑_{γ∈Γ} μ̂_{γ} ≤ ∑_{γ∈Γ} μ_{γ} = ∑_{γ∈Γ} M(P_{1}^{γ}, …, P_{n}^{γ}).

But then because of Equation (2), the inequality (3) must actually be an equality, as desired.

We now work on proving this inequality (3) for each γ ∈ ℚ^{n}. We can reduce to the case where γ = 0 and each f_{i} has coefficients in 𝔬_{L} by making a change of variables, as follows. As in the proof of Proposition 3, fix a choice of π^{\frac{1}{d}} where d is the least common denominator of γ, so that π^{γ_{i}} is well-defined for each i. Let μ_{i} denote the minimal value of the dot product (γ, 1) · (a, ω_{i,a}) for a in A_{i}. Then one can check that g_{i}(y) := π^{−μ_{i}}f(π^{γ_{1}}y_{1}, …, π^{γ_{n}}y_{n}) has the following properties:

• It lies in 𝔬_{L}[y, y^{−1}].

• Solutions x^{∗} to f(x) = 0 in (L^{×})^{n} having ord(x^{∗}) = γ biject via the invertible map x_{i} = π^{γ_{i}}y_{i} with solutions y^{∗} to g(y) = 0 having ord(y^{∗}) = 0.

• \overline{in}_{γ}(f) = \overline{in}_{0}(g).

Note that \overline{in}_{0}(−) is simply the reduction map

\begin{matrix}𝔬_{L}[x, x^{−1}] & → & L̄[x, x^{−1}] \\ f & ↦ & f̄ \end{matrix}

induced from the reduction map on the coefficients 𝔬_{L} → L̄.

As a further reduction, we can replace L with any finite algebraic extension of K that contains the coordinates of each of the (finitely many) solutions x^{∗} in (L^{×})^{n} of the system f = 0. Having done this, the new field L will be discretely valued, so we can also assume without loss of generality that K = L.

It only remains to show then that for a complete field K with discrete valuation, given f ∈ 𝔬_{K}[x, x^{−1}]^{n} with the property that

• the system f = 0 has only a finite number of isolated solutions in (K^{×})^{n},

• the system f̄ = 0 in K̄[x, x^{−1}] has only a finite number of isolated solutions

in (K̄^{×})^{n}, then the number of solutions to f = 0 lying in (𝔬_{K}^{×})^{n} is at most the number of solutions to f̄ = 0 in (K̄^{×})^{n}, counted with multiplicities.

It turns out that a stronger statement holds for each solution in (K̄^{×})^{n}: its multiplicity as a solution to f̄ = 0 gives an upper bound for the sum of the multiplicities as solutions to f = 0 of all points in (𝔬_{K}^{×})^{n} which reduce to it. This follows from Lemma 17 in the Appendix, applied with A = 𝔬[x, x^{−1}]/(f). □

This completes the proof of Theorem 4.

3. Examples, remarks, questions

Example 12. We give an easy example involving a system of linear equations to illuminate the nature of the genericity conditions and the conclusion in Theorem 4. Consider the system of equations

\begin{aligned}f_{1}(x_{1}, x_{2}) = A_{11}x_{1} + A_{12}x_{2} − B_{1} & = 0 \\ f_{2}(x_{1}, x_{2}) = A_{21}x_{1} + A_{22}x_{2} − B_{2} & = 0 \end{aligned}

equivalent to the matrix system

[\begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix}] [\begin{matrix}x_{1} \\ x_{2} \end{matrix}] = [\begin{matrix}B_{1} \\ B_{2} \end{matrix}] .

In our terminology, this implies that the Newton polygons P_{1}, P_{2} coincide, with both being equal to the triangle in ℝ^{2} having vertices {(0, 0), (1, 0), (0, 1)}. Since the mixed volume M(P_{1}, P_{2}) = 1, Bernstein’s Theorem predicts that this system has exactly 1 solution in (K^{×})^{2} for generic choices of the coefficients A_{ij}, B_{i}.

Now assume that the coefficients A_{ij}, B_{i} lie in a complete discretely valued field K, and to further specify Â, assume that

\begin{aligned}A_{i1} & = π^{α_{1}}a_{i1} \\ A_{i2} & = π^{α_{2}}a_{i2} \\ B_{i} & = π^{β}b_{i} \end{aligned}

where a_{ij}, b_{i} lie in the valuation ring 𝔬.

The lifted Newton polygons conv(Â_{1}), conv(Â_{2}) again coincide, both being equal to the triangle in ℝ^{3} with vertices {(0, 0, β), (1, 0, α_{1}), (0, 1, α_{2})}. Their Minkowski sum conv(Â_{1}) + conv(Â_{2}) is the dilation by 2 of the same triangle, having only one 2-dimensional face. This 2-dimensional face has normal vector in ℝ^{3} of the form (γ_{0}, 1) with γ_{0} = (β − α_{1}, β − α_{2}) in ℝ^{2}, and

M(P_{1}^{γ_{0}}, P_{2}^{γ_{0}})(= M(P_{1}, P_{2})) = 1.

Consequently, Theorem 4 predicts that generically the unique solution (x_{1}, x_{2}) to the system will have ord(x_{1}, x_{2}) = γ_{0} = (β − α_{1}, β − α_{2}).

Of course, we know how to solve this system explicitly via Cramer’s rule, giving (x_{1}, x_{2}) = (\frac{D_{1}}{D} , \frac{D_{2}}{D}) where

D = det [\begin{matrix}A_{11} & A_{12} \\ A_{21} & A_{22} \end{matrix}] , D_{1} = det [\begin{matrix}B_{1} & A_{12} \\ B_{2} & A_{22} \end{matrix}] , D_{2} = det [\begin{matrix}A_{11} & B_{1} \\ A_{21} & B_{2} \end{matrix}] .

Here we can be very explicit about the genericity conditions assumed in the theorem, and check if they suffice to force the coordinates of this unique solution to have the predicted valuations.

If one chooses a generic vector γ in ℝ^{2}, then the dot product of (γ, 1) with points in the lifted triangle in ℝ^{3} will be minimized on one of its vertices. However, somewhat less generic choices of γ in ℝ^{2} give rise to vectors (γ, 1) in ℝ^{3} whose dot product minimizes on various edges of the lifted triangle, producing initial systems \overline{in}_{γ}(f) = 0 of the form

[ā_{11} ; ā_{21}] x_{1} = [b̄_{1} ; b̄_{2}] , [ā_{12} ; ā_{22}] x_{2} = [b̄_{1} ; b̄_{2}] , [\begin{matrix}ā_{11} & ā_{12} \\ ā_{21} & ā_{22} \end{matrix}] [\begin{matrix}x_{1} \\ x_{2} \end{matrix}] = [\begin{matrix}0 \\ 0 \end{matrix}] .

Requiring that all of these initial systems have no solutions in (x_{1}, x_{2}) in (K̄^{×})^{2} is then seen to be equivalent to non-vanishing for the following three determinants in K̄:

D̄ := det [\begin{matrix}ā_{11} & ā_{12} \\ ā_{21} & ā_{22} \end{matrix}] , D̄_{1} := det [\begin{matrix}b̄_{1} & ā_{12} \\ b̄_{2} & ā_{22} \end{matrix}] , D̄_{2} := det [\begin{matrix}ā_{11} & b̄_{1} \\ ā_{21} & b̄_{2} \end{matrix}] .

Equivalently, these conditions assert that

ord(D) = α_{1} + α_{2}
ord(D_{1}) = β + α_{2}
ord(D_{2}) = α_{1} + β,

One can then see that indeed these genericity conditions suffice to imply the weaker genericity assumptions needed to apply Bernstein (cf. Lemma 10), and also to conclude that

ord(x_{1}, x_{2}) = (ord (\frac{D_{1}}{D} ) , ord (\frac{D_{2}}{D} )) = (β − α_{1}, β − α_{2}) = γ_{0}.

Remark 13. Consider the special case of Theorem 2 where K is the ring of formal Laurent series k((t)) with t-adic valuation, and k has characteristic zero. This relates to classic results in Walker [13], Maurer [10], as well as Khovanskiǐ’s Curve Theorem on the Puiseux expansions x(t) about t = 0 for the branches of an algebraic curve defined by f_{i}(x, t) ∈ k[x_{1}, …, x_{n}, t] for i = 1, …, n with prescribed (n + 1)- dimensional Newton polytopes Â_{i}. The Puiseux expansions are vectors in L^{n} where L is the algebraic closure of K = k((t)). Theorem 4 or the Curve Theorem predicts (generically) that the variety V (f_{1}, …, f_{n}) is a curve having exactly M(P_{1}^{γ}, …, P_{n}^{γ}) branches with Puiseux expansions about t = 0 of the form

x = [ c_{γ_{1}}t^{γ_{1}} + o(t^{γ_{1}+1}) ; ⋮ ; c_{γ_{n}}t^{γ_{n}} + o(t^{γ_{n}+1}))]

Remark 14. For some applications where f_{1}, …, f_{n} are polynomials rather than Laurent polynomials, it is more appropriate to count solutions in affine space 𝔸_{L}^{n} rather than the torus (L^{×})^{n}. For example, building on previous work in this direction, Huber and Sturmfels [7] calculate the generic number of solutions in complex affine space 𝔸_{ℂ}^{n} for f = 0 where f ∈ ℂ[x]^{n}. In fact, the paper of Rojas [11] proves a much more general result than Theorem 1, which as a special case, extends the results of [7] from ℂ to an arbitrary algebraically closed field k. For a field K with discrete valution, one can (although we omit the details here) adapt the proof of Theorem 4 to prove the following generalization.

Given f_{1}, …, f_{n} ∈ K[x], choose a large positive number N, and define pointed versions A_{i}^{+}, Â_{i}^{+} of A_{i}, Â_{i} as follows:

(4)  \begin{aligned}A_{i}^{+} & := A_{i} ∪ \{0\} \\ ω_{i,0}^{+} & := \begin{cases}ω_{i,0} & if 0 ∈ A_{i} \\ N & if 0 ∉ A_{i} \end{cases} \\ Â_{i}^{+} & := \{(a, ω_{i,a}^{+}) : a ∈ A_{i}^{+}. \end{aligned}

Let conv(·) denote the convex hull of a set of points. Following [7], it can be shown that for N sufficiently large, the combinatorial structure of the lower convex hull of the Minkowski sum ∑_{i=1}^{n} conv(A_{i}^{+}) is constant in the following sense: there is a finite collection of vectors Γ = {γ_{i}} ⊂ ℚ^{n}, having entries which are affine functions γ_{i} = m_{i}N + b_{i} of N, such that {(γ_{i}, 1)}_{γ_{i}∈Γ} is exactly the set of inward-pointing normal vectors for n-dimensional faces of the lower convex hull (note that if the point (0, N) is not a vertex of the face corresponding to γ_{i}, then m_{i} = 0). Say that γ in Γ is stable if all of the slopes m_{i} are non-negative, and for a stable γ in Γ say that a vector x ∈ L^{n} has ord(x) agreeing with γ if

• x_{i} = 0 if and only if m_{i} > 0.

• ord(x_{i}) = γ_{i}(= b_{i}) if m_{i} = 0.

Roughly speaking, this convention means we are treating N as if N = +∞ = ord(0).

Given a stable γ in Γ, let M(P_{1,+}^{γ}, …, P_{n,+}^{γ}) be the mixed volume of the polytopes P_{1,+}^{γ}, …, P_{n,+}^{γ}, where P_{i,+}^{γ} is the image under the projection ℝ^{n+1} → ℝ^{n} of the face of the lower hull of Â_{i}^{+} on which the dot product with (γ, 1) is minimized. We remark that for N sufficiently large, the polytopes {(P_{1,+}^{γ}, …, P_{n,+}^{γ})}_{γ∈Γ} give a subdivision of (A_{1}^{+}, …, A_{n}^{+}) in the sense of [6], which refines the subdivision introduced in [7] for the sake of stating their affine root-count. Theorem 15. With the above notation, on a non-empty Zariski-open subset U of such f_{i}’s in the moduli space 𝔸|A_{1}| ; K̄×⋯×𝔸|A_{n}| ; K̄ of reduced coefficients (c̄_{i,a}), the system f = 0 has only a finite number of isolated solutions in the affine space 𝔸_{L}^{n}. Furthermore, every such solution x^{∗} has ord(x^{∗}) agreeing with some stable γ ∈ Γ, and the number which agree with γ, counted with multiplicity, is M(P_{1,+}^{γ}, …, P_{n,+}^{γ}). □

Example 16. We give an example to illustrate Theorems 4 and 15. Consider the system f = 0

\begin{aligned}f_{1} & = ay^{3} + bx^{2}y^{2} = 0 \\ f_{2} & = cx + dx^{2} + ex^{3} = 0 \end{aligned}

with f_{1}, f_{2} ∈ K[x, y] for some complete discretely valued field K, and assume that a, b, c, d, e are generically chosen with ord-values α, β, γ, δ, ϵ ∈ ℤ, respectively. In this case it happens that one can enumerate solutions in the affine plane by factoring out powers of variables from f_{1}, f_{2}. Letting r_{1}, r_{2} denote the two roots of the quadratic equation c + dx + ex^{2} = 0, if we assume for definiteness that δ < \frac{1}{2}(γ + ϵ), then the quadratic formula shows

\begin{aligned}ord(r_{1}) & = γ − δ \\ ord(r_{2}) & = δ − ϵ \end{aligned}

and f = 0 has the following solutions:

solution  ord  multiplicity
(0, 0)  (+∞, +∞)  3
(r_{1}, 0)  (γ − δ, +∞)  2
(r_{2}, 0)  (δ − ϵ, +∞)  2
(r_{1}, −\frac{b}{a}r_{1}) (γ − δ, 2(γ − δ) + β − α)  1
(r_{2}, −\frac{b}{a}r_{2}) (δ − ϵ, 2(δ − ϵ) + β − α)  1

The convex geometry of this example is illustrated in Figure 1 for the particular values

N = 5, α = 1, β = 2, γ = 3, δ = 3, ϵ = 4.

Figure 1. An example of Theorems 4 and 15.

Figure 1(a) shows the point sets A_{1}^{+}, A_{2}^{+} in ℤ^{2}, with the points labelled by the coefficient of their corresponding monomial in f_{1} or f_{2}. Figure 1(b) depicts their Minkowski sum A_{1}^{+}+A_{2}^{+} along with its subdivision induced by the lower convex hull of the lifted points Â_{1}^{+} + Â_{2}^{+}, as shown in Figure 1(c). Note that the b + 0 does not participate in the subdivision, as it lifts to a point above the lower convex hull. The set Γ contains six vectors {γ_{A}, γ_{B}, γ_{C}, γ_{D}, γ_{E}, γ_{F} }, corresponding to the labelled 2dimensional faces in Figure 1(b). The corresponding normal vectors (γ, 1) to the 2-dimensional faces in Figure 1(c), and the mixed volumes M(P_{1,+}^{γ}, …, P_{n,+}^{γ}) may then be computed to be

normal vector (γ, 1)  stable? M(P_{1,+}^{γ}, …, P_{n,+}^{γ})
A  (N − γ, \frac{1}{3}(N − α), 1)  yes  3
B  (γ − δ, N + δ − β − γ, 1)  yes  2
C  (δ − ϵ, N + ϵ − β − δ, 1)  yes  2
D (γ − δ, 2(γ − δ) + β − α, 1)  yes  1
E  (δ − ϵ, 2(δ − ϵ) + β − α, 1)  yes  1
F (\frac{1}{6}(N + 2α − 3β), \frac{1}{3}(N − α), 1)  yes  0

In this example, every γ in Γ is stable, but γ_{F} contributes no solutions because the associated mixed volume is 0. Note that the multiplicities and valuations of non-zero coordinates of the roots of f = 0 agree with the mixed volumes and the first and second coordinates of the entries in the above table, as predicted by Theorem 15. Theorem 4 deals only with the two solutions lying in the torus (L^{×})^{2}, whose coordinates’ valuations are predicted by the data in the above table corresponding to the faces labelled D, E that give a subdivision of A_{1} + A_{2}.

4. Appendix by William Messing

Our goal is to state and prove Lemma 17 below on multiplicities, which was used at the end of the proof of Theorem 4. We begin by recalling the definition of multiplicity [4, IV 4.7.12] which we employ.

Assume C is an Artin local ring with residue field K, and that C is a finite dimensional k-algebra for some field k. Then clearly

dim_{k} C = ℓ(C) · [K : k]

where ℓ(C) denotes the length of C (as a C-module). In the case C = O_{Y,y} for y a point on the k-scheme Y, we define mult_{y} Y = dim_{k} C. Lemma 17. Let 𝔬 be a complete discrete valuation ring with residue field K̄, fraction field K, and maximal ideal generated by the uniformizing parameter π.

Let X = Spec(A) with A a finitely generated 𝔬-algebra. Assume XK̄ is a zerodimensional scheme. If x ∈ XK̄ and z_{1}, …, z_{N} are the points of X_{K} which specialize to x, then

∑_{i=1}^{N} mult_{z_{i}} X_{K} ≤ mult_{x} XK̄.

The following is an easy application of Nakayama’s Lemma. Lemma 18. Let R be a local ring and integral domain, with fraction field K and residue class field K̄. Let M be a finitely generated R-module. Then

dim_{K}(M ⊗_{R} K) ≤ dimK̄(M ⊗_{R} K̄).

Proof. M ⊗_{R} K̄ is a finite dimensional K̄-vector space. Let {α_{1}, …, α_{r}} be a basis for M ⊗_{R} K̄ over K̄. Let {α̂_{1}, …, α̂_{r}} be an arbitrary set of liftings in M. By Nakayama’s Lemma, {α̂_{1}, …, α̂_{r}} in fact generate M over R. But then {α̂_{1} ⊗ 1, …, α̂_{r} ⊗ 1} generate M ⊗_{R} K over K. □

We now apply this lemma and some results of Grothendieck to prove Lemma 17. Let S = Spec(𝔬) and X →^{f} S a separated morphism of finite type. Assume 𝔬 is a henselian local ring. Let f(x) = s, the closed point of S. Assume the closed point x is isolated in the special fiber (i.e. {x} is open and closed in XK̄). Then X = X′ ⨿ X′′, the disjoint union of open subschemes with x ∈ X′ and X′/S finite and X′′ ⊆ X_{K} [4, IV 18.12.1]. In the case where 𝔬 is a complete Noetherian local ring (as in Lemma 17 when 𝔬 is a complete discrete valuation ring), the result is considerably more elementary and a simpler proof is given in [4, II 6.2.4].

By hypothesis, XK̄ is zero-dimensional, so the coordinate ring A is an Artinian K̄-algebra. As such,

(5)  A = A_{1} × ⋯ × A_{m}

where the A_{i} are the local rings of A with respect to its maximal ideals. These ideals correspond to the closed points of XK̄, and we fix notation so that A_{1} = O_{XK̄,x}. If we set X′ = Spec(A′), then A′ is finite over 𝔬, and 𝔬 is henselian. Hence there is a one-to-one correspondence between the idempotents of A and those of A′ [3, III, Lemme 2]. Consequently the system of pairwise orthogonal idempotents corresponding to (5) can be lifted to A′ so that

A′ = A′_{1} × ⋯ × A′_{m}

with A′_{i}/𝔪A′_{i} = A_{i}, where 𝔪 is the maximal ideal of 𝔬. Any maximal ideal M′ of A′_{1} must contain 𝔪A′_{1} since otherwise 𝔪A′_{1} + M′ = A′_{1}, which contradicts Nakayama’s Lemma.

But then clearly M′ is the pre-image (under reduction mod 𝔪A′_{1}) of the unique maximal ideal M_{1} of A_{1}. Hence M′ is the unique maximal ideal of A′_{1}, and A′_{1} is local. Since A′_{1} is a factor of A′, clearly A′_{1} = O_{X,x}. The prime ideals of A′ which contain π trivialize in A′ ⊗_{𝔬} K. Thus the points of X_{K} which specialize to x correspond to the height zero prime ideals of A′_{1} which do not contain π. Let {𝔭_{i}}_{i=1}^{N} be those prime ideals of A′_{1} not containing π, and let 𝔭′_{i} = 𝔭_{i} ⊗_{𝔬} K be the corresponding prime ideals in A′_{1} ⊗_{𝔬} K. Let z_{i} denote point of X_{K} specializing to x which corresponds to 𝔭′_{i}. The direct product factorization of the Artinian ring A′_{1} ⊗_{𝔬} K yields

A′_{1} ⊗_{𝔬} K = ∏_{i=1}^{N}(A′_{1} ⊗_{𝔬} K)_{𝔭′_{i}}.

Then

dim_{K}(A′_{1} ⊗_{𝔬} K) = ∑_{i=1}^{N} dim_{K}(A′_{1} ⊗_{𝔬} K)_{𝔭′_{i}}

= ∑_{i=1}^{N} mult_{z_{i}} X_{K}.

But by Lemma 18 above,

dim_{K}(A′_{1} ⊗_{𝔬} K) ≤ dimK̄(A′_{1} ⊗_{𝔬} K̄)
= dimK̄ A_{1}
= mult_{x}(XK̄).

This completes the proof of Lemma 17.

References

[1] E. Artin, Theory of algebraic numbers, (Notes by Gerhard Würges from lectures held at the Mathematisches Institut, Göttingen, Germany, in the Winter Semester, 1956/7), Göttingen 1959

[2] D.N. Bernstein, The number of roots of a system of equations, Func. Anal. Appl. 9 (1975), 1–4.

[3] N. Bourbaki, Éléments de mathématique. Fascicule XXVIII. Algèbre commutative. Chapitre 3 et 4, Hermann, Paris, 1961.

[4] A. Grothendieck, Éléments de géométrie algébrique, Inst. Hautes Études Sci. Publ. Math..

[5] W. Fulton, Introduction to toric varieties, Annals of Mathematics Studies 131, Princeton University Press, Princeton, NJ, 1993.

[6] B. Huber and B. Sturmfels, A polyhedral method for solving sparse polynomial systems, Mathematics of Computation 64 (1995), 1541–1555.

[7] B. Huber and B. Sturmfels, Bernstein’s theorem in affine space, 64 (1995), 1541–1555.

[8] A.G. Khovanskiǐ, Addendum 3. Algebra and Mixed Volumes in Yu.D. Burago and V.A. Zalgaller, Geometric inequalities, Translated from the Russian by A. B. Sosinskiĭ. Grundlehren der Mathematischen Wissenschaften 285, Springer-Verlag, Berlin, 1988

[9] A.G. Kushnirenko, Newton polytopes and the Bezout Theorem, Functional Anal. Appl. 10 (1976), no. 3, 233–235 (1977).

[10] J. Maurer, Puiseux expansions for space curves, Manuscripta Mathematica 32 (1980), 91– 100.

[11] J.M. Rojas, Toric intersection theory for affine root counting, J. Pure Appl. Algebra 136 (1999), 67–100.

[12] B. Sturmfels, Gröbner bases and convex polytopes, University Lecture Series 8, American Math. Society, Providence RI, 1996.

[13] R. J. Walker, Algebraic curves Reprint of the 1950 edition. Springer-Verlag, New York-Heidelberg, 1978.

   E-mail address: messing@math.umn.edu, reiner@math.umn.edu, sperber@math.umn.edu

School of Mathematics, University of Minnesota, Minneapolis, MN 55455