Solving Algebraic Equations in Terms of A-Hypergeometric Series

Bernd Sturmfels Department of Mathematics University of California Berkeley, CA 94720, U.S.A.

                          bernd@math.berkeley.edu

Abstract The roots of the general equation of degree n satisfy an A-hypergeometric system of differential equations in the sense of Gel’fand, Kapranov and Zelevinsky. We construct the n distinct A-hypergeometric series solutions for each of the 2^{n−1} triangulations of the Newton segment. This works over any field whose characteristic is relatively prime to the lengths of the segments in the triangulation.

1. Solving the Quintic A classical problem in mathematics is to find a formula for the roots of the general equation of degree n in terms of its n + 1 coefficients. While there are formulas in terms of radicals for n ≤ 4, Galois theory teaches us that no such formula exists for the general quintic

a_{5}x^{5} + a_{4}x^{4} + a_{3}x^{3} + a_{2}x^{2} + a_{1}x + a_{0} = 0.  (1.1)

An alternative approach is to expand the roots into fractional power series (or Puiseux series). In 1757 Johann Lambert expressed the roots of the trinomial equation x^{p} + x + r as a Gauss hypergeometric function in the parameter r. Series expansions of more general algebraic functions were subsequently given by Euler, Chebyshev and Eisenstein, among others. The poster “Solving the Quintic with Mathematica” [12] gives a nice introduction to these classical techniques and underlines their relevance for symbolic computation.

The state of the art in the first half of our century appears in works of Richard Birkeland [2] and Karl Mayr [10]. They proved that the roots are multivariate hypergeometric functions (in the sense of Horn) in all of the coefficients and they gave series expansions for the roots and their powers. The purpose of this note is to refine the these results.

Our point of departure is the fact that the roots satisfy the A-hypergeometric differential equations introduced by Gel’fand, Kapranov and Zelevinsky [6],[7]. Here A denotes the configuration of n + 1 equidistant points on the affine line. It follows from recent work of McDonald [11] that there are 2^{n−1} distinct complete sets of series solutions, one for each of the 2^{n−1} triangulations of A. We shall construct these series solutions explicitly.

Let us illustrate our general construction for the example of the quintic (1.1). Here the set A has 16 distinct triangulations. The finest triangulation divides A into five segments of unit length. The coarsest triangulation of A is just a single segment of length 5.

For the finest triangulation we get the following expressions for the five roots of (1.1):

\begin{aligned}X_{1,−1} = −[\frac{a_{0}}{a_{1}} ],  X_{2,−1} & = −[\frac{a_{1}}{a_{2}} ] + [\frac{a_{0}}{a_{1}} ],  X_{3,−1} = −[\frac{a_{2}}{a_{3}} ] + [\frac{a_{1}}{a_{2}} ], \\ X_{4,−1} & = −[\frac{a_{3}}{a_{4}} ] + [\frac{a_{2}}{a_{3}} ],  X_{5,−1} = −[\frac{a_{4}}{a_{5}} ] + [\frac{a_{3}}{a_{4}} ]. \end{aligned}

Each bracket represents a power series having the monomial in the bracket as its first term:

\begin{aligned}[\frac{a_{0}}{a_{1}} ] & = \frac{a_{0}}{a_{1}} + \frac{a_{0}^{2}a_{2}}{a_{1}^{3}} − \frac{a_{0}^{3}a_{3}}{a_{1}^{4}} + 2\frac{a_{0}^{3}a_{2}^{2}}{a_{1}^{5}} + \frac{a_{0}^{4}a_{4}}{a_{1}^{5}} − 5\frac{a_{0}^{4}a_{2}a_{3}}{a_{1}^{6}} − \frac{a_{0}^{5}a_{5}}{a_{1}^{6}} + ⋯ \\ [\frac{a_{1}}{a_{2}} ] & = \frac{a_{1}}{a_{2}} + \frac{a_{1}^{2}a_{3}}{a_{2}^{3}} − \frac{a_{1}^{3}a_{4}}{a_{2}^{4}} − 3\frac{a_{0}a_{1}^{2}a_{5}}{a_{2}^{4}} + 2\frac{a_{1}^{3}a_{3}^{3}}{a_{2}^{5}} + \frac{a_{1}^{4}a_{5}}{a_{2}^{5}} − 5\frac{a_{1}^{4}a_{3}a_{4}}{a_{2}^{6}} + ⋯ \\ [\frac{a_{2}}{a_{3}} ] & = \frac{a_{2}}{a_{3}} − \frac{a_{0}a_{5}}{a_{3}^{2}} − \frac{a_{1}a_{4}}{a_{3}^{2}} + 2\frac{a_{1}a_{2}a_{5}}{a_{3}^{3}} + \frac{a_{2}^{2}a_{4}}{a_{3}^{3}} − \frac{a_{2}^{3}a_{5}}{a_{3}^{4}} + 2\frac{a_{2}^{3}a_{4}^{2}}{a_{3}^{5}} + ⋯ \\ [\frac{a_{3}}{a_{4}} ] & = \frac{a_{3}}{a_{4}} − \frac{a_{2}a_{5}}{a_{4}^{2}} + \frac{a_{3}^{2}a_{5}}{a_{4}^{3}} + \frac{a_{1}a_{5}^{2}}{a_{4}^{3}} − 3\frac{a_{2}a_{3}a_{5}^{2}}{a_{4}^{4}} − \frac{a_{0}a_{5}^{3}}{a_{4}^{4}} + 4\frac{a_{1}a_{3}a_{5}^{3}}{a_{4}^{5}} + ⋯ \\ [\frac{a_{4}}{a_{5}} ] & = \frac{a_{4}}{a_{5}} \end{aligned}

Note that the last bracket is just a single Laurent monomial. The other four brackets [\frac{a_{i−1}}{a_{i}} ] can easily be written as an explicit sum over N^{4}. For instance,

[\frac{a_{0}}{a_{1}} ] = ∑_{i,j,k,l≥0} \frac{(−1)^{2i+3j+4k+5l} (2i+3j+4k+5l)!}{i! j! k! l! (i+2j+3k+4l + 1)!} · \frac{a_{0}^{i+2j+3k+4l+1}a_{2}^{i}a_{3}^{j}a_{4}^{k}a_{5}^{l}}{a_{1}^{2i+3j+4k+5l+1}}

Each coefficient appearing in one of these series is integral. Therefore our five series solutions of the general quintic are characteristic-free. They work over any base field.

The situation is different for the coarsest triangulation of A. Here we must assume that the characteristic is different from 5. The five series solutions of (1.1) are

X_{5,ξ} = ξ · [\frac{a_{0}^{1/5}}{a_{5}^{1/5}} ] + \frac{1}{5} · (ξ^{2}[\frac{a_{1}}{a_{0}^{3/5}a_{5}^{2/5}} ] + ξ^{3}[\frac{a_{2}}{a_{0}^{2/5}a_{5}^{3/5}} ] + ξ^{4}[\frac{a_{3}}{a_{0}^{1/5}a_{5}^{4/5}} ] − [\frac{a_{4}}{a_{5}} ])

where ξ runs over the five roots of the equation ξ^{5} = −1. The brackets denote the series

\begin{aligned}[\frac{a_{0}^{1/5}}{a_{5}^{1/5}} ] & = \frac{a_{0}^{1/5}}{a_{5}^{1/5}} − \frac{1}{25} \frac{a_{1}a_{4}}{a_{0}^{4/5}a_{5}^{6/5}} − \frac{1}{25} \frac{a_{2}a_{3}}{a_{0}^{4/5}a_{5}^{6/5}} + \frac{2}{125} \frac{a_{1}^{2}a_{3}}{a_{0}^{9/5}a_{5}^{6/5}} + \frac{3}{125} \frac{a_{2}a_{4}^{2}}{a_{0}^{4/5}a_{5}^{11/5}} + ⋯ \\ [\frac{a_{1}}{a_{0}^{3/5}a_{5}^{2/5}} ] & = \frac{a_{1}}{a_{0}^{3/5}a_{5}^{2/5}} − \frac{1}{5} \frac{a_{3}^{2}}{a_{0}^{3/5}a_{5}^{7/5}} − \frac{2}{5} \frac{a_{2}a_{4}}{a_{0}^{3/5}a_{5}^{7/5}} + \frac{7}{25} \frac{a_{3}a_{4}^{2}}{a_{0}^{3/5}a_{5}^{12/5}} + \frac{6}{25} \frac{a_{1}a_{2}a_{3}}{a_{0}^{8/5}a_{5}^{7/5}} + ⋯ \\ [\frac{a_{2}}{a_{0}^{2/5}a_{5}^{3/5}} ] & = \frac{a_{2}}{a_{0}^{2/5}a_{5}^{3/5}} − \frac{1}{5} \frac{a_{1}^{2}}{a_{0}^{7/5}a_{5}^{3/5}} − \frac{3}{5} \frac{a_{3}a_{4}}{a_{0}^{2/5}a_{5}^{8/5}} + \frac{6}{25} \frac{a_{1}a_{2}a_{4}}{a_{0}^{7/5}a_{5}^{8/5}} + \frac{3}{25} \frac{a_{1}a_{3}^{2}}{a_{0}^{7/5}a_{5}^{8/5}} + ⋯ \\ [\frac{a_{3}}{a_{0}^{1/5}a_{5}^{4/5}} ] & = \frac{a_{3}}{a_{0}^{1/5}a_{5}^{4/5}} − \frac{1}{5} \frac{a_{1}a_{2}}{a_{0}^{6/5}a_{5}^{4/5}} − \frac{2}{5} \frac{a_{4}^{2}}{a_{0}^{1/5}a_{5}^{9/5}} + \frac{1}{25} \frac{a_{1}^{3}}{a_{0}^{11/5}a_{5}^{4/5}} + \frac{4}{25} \frac{a_{1}a_{3}a_{4}}{a_{0}^{6/5}a_{5}^{9/5}} + ⋯ \end{aligned}

Each of these four series can be expressed as an explicit sum over the lattice points in a 4-dimensional polyhedron. The general formula will be presented in Theorem 3.2 below.

2. The Roots are A-hypergeometric Our problem is to compute the roots of the general equation of degree n,

f(x) = a_{0} + a_{1}x + a_{2}x^{2} + … + a_{n−1}x^{n−1} + a_{n}x^{n}.  (2.1)

Each root of f(x) is an algebraic function in the indeterminate coefficients:

X = X(a_{0}, a_{1}, a_{2}, …, a_{n−1}, a_{n}).

Proposition 2.1. (Karl Mayr [10, p. 284]) The roots of the general equation of degree n satisfy the following system of linear partial differential equations:

\frac{∂^{2}X}{∂a_{i}∂a_{j}} = \frac{∂^{2}X}{∂a_{k}∂a_{l}}  whenever i + j = k + l,  (2.2)

∑_{i=0}^{n} ia_{i} \frac{∂X}{∂a_{i}} = −X  and  ∑_{i=0}^{n} a_{i} \frac{∂X}{∂a_{i}} = 0.  (2.3)

The system (2.2)-(2.3) is a special instance of the class of A-hypergeometric differential equations introduced by Gel’fand, Kapranov and Zelevinsky [5],[7]. Namely, (2.2)-(2.3) is the A-hypergeometric system with parameters \binom{−1}{0} associated with the integer matrix

A := ( \begin{matrix}0 & 1 & 2 & 3 & ⋯ & n − 1 & n \\ 1 & 1 & 1 & 1 & ⋯ & 1 & 1 \end{matrix} ) .  (2.4)

The column vectors of A are homogeneous coordinates of n + 1 equidistant points on the line. Their convex hull is a line segment: it is the Newton polytope of f(x).

The Euler-type equations (2.3) follow readily from the homogeneity relations

\begin{aligned}X(a_{0}, ta_{1}, t^{2}a_{2}, …, t^{n−1}a_{n−1}, t^{n}a_{n}) & = \frac{1}{t} · X(a_{0}, a_{1}, a_{2}, …, a_{n−1}, a_{n}), \\ X(ta_{0}, ta_{1}, ta_{2}, …, ta_{n−1}, ta_{n}) & = X(a_{0}, a_{1}, a_{2}, …, a_{n−1}, a_{n}). \end{aligned}

The equations (2.2) appeared in Karl Mayr’s 1937 paper [10, equation (2) on page 284]. I shall present two proofs different proofs. The first one was shown to me in the spring of 1992 by Jean-Luc Brylinski. See [3] for an appearance of (2.2) in differential geometry.

Brylinsky’s proof of (2.2): It uses implicit differentiation and works over any base field. We consider the first derivative f′(x) = ∑_{i=1}^{n} ia_{i}x^{i−1} and the second derivative f′′(x) = ∑_{i=2}^{n} i(i − 1)a_{i}x^{i−2}. Note that f′(X) ≠ 0, since a_{0}, …, a_{n} are indeterminates. Differentiating the defining identity ∑_{i=0}^{n} a_{i}X(a_{0}, a_{1}, …, a_{n})^{i} = 0 with respect to a_{j}, we get

X^{j} + f′(X) · \frac{∂X}{∂a_{j}} = 0.  (2.5)

We next differentiate ∂X/∂a_{j} with respect to the indeterminate a_{i}:

\frac{∂^{2}X}{∂a_{i}∂a_{j}} = \frac{∂}{∂a_{i}} (−\frac{X^{j}}{f′(X)}) = \frac{∂f′(X)}{∂a_{i}}X^{j}f′(X)^{−2} − jX^{j−1} \frac{∂X}{∂a_{i}} f′(X)^{−1}. (2.6)

Using (2.5) and the identity \frac{∂f′(X)}{∂a_{i}} = −\frac{f′′(X)}{f′(X)} · X^{i} + iX^{i−1}, we can rewrite (2.6) as

\frac{∂^{2}X}{∂a_{i}∂a_{j}} = −f′′(X)X^{i+j}f′(X)^{−3} + (i + j)X^{i+j−1}f′(X)^{−2}.  (2.7)

The expression (2.7) depends only on the sum of indices i + j. This proves (2.2).

A complex analysis proof of (2.2): Suppose we are working over the field of complex numbers C. Consider the logarithmic derivative [log(f(x))]′ = f′(x)/f(x). We view it as a rational function in ahabe_{0}, a_{1}, …, a_{n} and differentiate with respect to these variables:

\frac{∂^{2}}{∂a_{i}∂a_{j}} [log(f(x))]′ = (\frac{−x^{i+j}}{f^{2}(x)} )′.

This shows that [log(f(x))]′ satisfies the quadratic A-hypergeometric equations (2.2). Proposition 2.1 follows by differentiating under the integral sign in Cauchy’s formula

X = \frac{1}{2πi} ∫_{Γ} \frac{zf′(z)}{f(z)}dz,  (2.8)

where Γ is a sufficiently small loop in the complex plane.

3. Series Expansions For any rational number u and any integer v we abbreviate

γ(u, v) := \{ \begin{matrix}1 & if v = 0, \\ u(u − 1)(u − 2) ⋯ (u + v + 1) & if v < 0, \\ 0 & if u is a negative integer and u ≥ −v, \\ \frac{1}{(u+1)(u+2)···(u+v)} & otherwise. \end{matrix}

If u is not a negative integer then γ(u, v − 1) = (u + v) · γ(u, v) and we have γ(u, v) = Γ(u + 1)/Γ(u + v + 1), where Γ is the usual Gamma function.

Let L denote the integer kernel of A. This is the (n−1)-dimensional sublattice of Z^{n+1} spanned by {e_{i−1} − 2e_{i} + e_{i+1} : i = 1, …, n−1}. Consider any monomial a_{0}^{u_{0}}a_{1}^{u_{1}} ⋯ a_{n}^{u_{n}} with rational exponents in the coefficients of f(x). We define the formal power series

[a_{0}^{u_{0}}a_{1}^{u_{1}} ⋯ a_{n}^{u_{n}}] := ∑_{(v_{0},...,v_{n})∈L} ∏_{i=0}^{n} ( γ(u_{i}, v_{i}) a_{i}^{u_{i}+v_{i}}).  (3.1)

This series satisfies the linear differential equations (2.3) with their right hand sides −X and 0 replaced by γ_{1}X and γ_{2}X, and it satisfies the quadratic equations (2.2) in the following two cases. To prove the second case it is best to first derive formula (4.2) below.

Lemma 3.1. ([6, Lemma 1]) Let (u_{0}, u_{1}, …, u_{n}) be a rational vector which either has no negative integer coordinate or has the form (0, …, 0, 1, −1, 0, …, 0). Then the series [a_{0}^{u_{0}} ⋯ a_{n}^{u_{n}}] is a formal solution of the A-hypergeometric system with parameters \binom{γ_{1}}{γ_{2}} = A · (u_{0}, u_{1}, …, u_{n})^{T}.

Gel’fand, Kapranov and Zelevinsky constructed a complete set of series solutions for each regular triangulations of the set A. We shall adapt their general construction to our special case. Extra care must be taken, however, because our equations (2.3) do not satisfy the non-resonance hypothesis which is necessary for [6, Theorem 3] to hold.

We write 0, 1, …, n for the points in our configuration A in (2.4). It has 2^{n−1} triangulations, all of which are regular. Each triangulation is indexed by a subset I of {1, …, n − 1}. Writing the complementary subset as {0, 1, …, n}\I = {0 = i_{0} < i_{1} < i_{2} < ⋯ < i_{r−1} < i_{r} = n}, the triangulation of A indexed by I consists of the r segments [i_{0}, i_{1}], [i_{1}, i_{2}], …, [i_{r−1}, i_{r}]. See [8, Sections 7.3.A and 12.2.A] for details. If r = n (resp. r = 1) then this is the finest (resp. coarsest) triangulation referred to in Section 1.

We are now prepared to present the main result of this note. In the remainder of Section 3 we shall be working over the field of complex numbers C. Fix any of the 2^{n−1} triangulations of A. For j = 1, …, r we write d_{j} := i_{j} − i_{j−1} for the length of the j-th segment in that triangulation. Clearly, d_{1} + d_{2} + ⋯ + d_{r} = n. Let ξ = (−1)^{1/d_{j}} be any of the d_{j}-th roots of −1. We define the A-hypergeometric series

X_{j,ξ} := ξ · [ai_{j−1}^{\frac{1}{d_{j}}}a_{i_{j}}^{− \frac{1}{d_{j}}} ] + \frac{1}{d_{j}} · ∑_{k=2}^{d_{j}} ξ^{k} · [a_{i_{j−1}+k−1} ai_{j−1}^{\frac{k−d_{j}}{d_{j}}} a_{i_{j}}^{− \frac{k}{d_{j}}} ] + \frac{1}{d_{j}} · [\frac{a_{i_{j−1}−1}}{a_{i_{j−1}}} ]

If j = 1 then the expression [\frac{a_{−1}}{a_{0}} ] appears in the rightmost summand. We define it to be zero. Note that by varying j and ξ we have defined n distinct series in total.

Theorem 3.2. The n series X_{j,ξ} are roots of the general equation of order n, that is, f(X_{j,ξ}) = 0. There exists a constant M such that all n series X_{j,ξ} converge whenever

|a_{i_{j−1}}|^{i_{j}−k} · |a_{i_{j}}|^{k−i_{j−1}} ≤ M · |a_{k}|^{d_{j}} for all 1 ≤ j ≤ r and k ∉ {i_{j−1}, i_{j}}.  (3.2)

Proof: Consider the open convex cone

C = { w ∈ R^{n+1} : (i_{j}−k)·w_{i_{j−1}} + (k−i_{j−1})·w_{i_{j}} < d_{j}·w_{k} for j = 1, …, r, k ∉ {i_{j−1}, i_{j}}}.

This is the outer normal cone to the secondary polytope Σ(A) at the vertex corresponding to the triangulation I of A (cf. [8, Theorem 12.2.2]). Equivalently, the cone C consists of all vectors w = (w_{0}, w_{1}, …, w_{n}) which induce the triangulation in question.

Let U be the region in the coefficient space C^{n+1} defined by the inequalities (3.2) for M ≫ 0. There exists a vector V ∈ R^{n+1} such that (log(|a_{0}|), …, log(|a_{n}|)) − V ∈ C for all (a_{0}, …, a_{n}) in U. Let H be the space of all complex-valued functions on U which are A-hypergeometric with parameters \binom{−1}{0}. The A-hypergeometric system is holonomic of rank n and its singular locus, the discriminantal locus of f, is disjoint from U (see [6]). Hence H is a complex vector space of dimension at most n. We shall identify n linearly independent elements in H, which will imply that H has dimension exactly n.

It follows from [6, Proposition 2] that the series [a_{0}^{u_{0}} ⋯ a_{n}^{u_{n}}] defined in (3.1) converges in U provided at most two of the exponents u_{i} are non-integers. Each of the summands in the definition of X_{j,ξ} has this property. Therefore X_{j,ξ} converges in U. Using Lemma 3.1, we conclude that the n series X_{j,ξ} lie in the vector space H.

We fix an vector w = (w_{0}, …, w_{n}) in C such that all coordinates w_{i} are integers and such that no two of the lines spanned by pairs {(w_{i}, i), (w_{j}, j)} in R^{2} are parallel. The weight of a monomial a_{0}^{i_{0}}a_{1}^{i_{1}} ⋯ a_{n}^{i_{n}} (with rational exponents) is defined to be w_{0}i_{0} +w_{1}i_{1} + ⋯ + w_{n}i_{n}. We replace the input equation by its toric deformation

f_{t}(x) = a_{0}t^{w_{0}} + a_{1}t^{w_{1}}x + a_{2}t^{w_{2}}x^{2} + … + a_{n−1}t^{w_{n−1}}x^{n−1} + a_{n}t^{w_{n}}x^{n}. (3.3)

We shall study the n roots as an algebraic function of t. For t close to the origin the n roots split into r groups, one for each segment [i_{j−1}, i_{j}], for j = 1, …, r. (This is a special case of the multivariate construction in [9, §3].) The roots in the j-th group possess a Puiseux expansion of the form

ψ_{j,ξ}(t) = ξ · ai_{j−1}^{\frac{1}{d_{j}}} · a_{i_{j}}^{− \frac{1}{d_{j}}} · t^{\frac{1}{d_{j}} (w_{i_{j−1}} −w_{i_{j}})} + higher terms in t,

where ξ satisfies ξ^{5} = −1. We shall prove that ψ_{j,ξ}(1) = X_{j,ξ} for all (a_{0}, …, a_{n}) ∈ U. To this end we first determine the second lowest term in the series ψ_{j,ξ}(t). After modifying the weight vector w by an affine transformation w_{i} ↦ αw_{i} + β, which does not alter the structure of the series, we may assume that w_{i_{j}} = w_{i_{j−1}} = 0, and there is a unique index r with w_{r} = 1, and w_{l} > 1 for l ∈ {0, 1, …, n}\{i_{j}, i_{j−1}, r}. An explicit calculation reveals

ψ_{j,ξ}(t) = ξai_{j−1}^{\frac{1}{d_{j}}}a_{i_{j}}^{− \frac{1}{d_{j}}}

+ \frac{1}{d_{j}} · ξ^{r+1−i_{j−1}} · a_{r} · a_{i_{j−1}}^{(r+1−i_{j})/d_{j}} · a_{i_{j}}^{(i_{j−1}−r−1)/d_{j}} · t + higher terms in t.

(3.4)

By varying w within the cone C we can arrange that the role of r is played by any index in the set

({0, 1, …, n}\{i_{1}, i_{2}, …, i_{r}}) ∪ {i_{j−1}, i_{j+2}}.  (3.5)

Note that the cardinality of this set is at least d_{j} − 1. Consider the linear map that extracts from a series in a_{0}, …, a_{n} all those terms which are lowest or second lowest with respect to the grading defined by some w ∈ C. Call this map T. Consider the image of a root ψ_{j,ξ}(1) under T. This is a polynomial (with fractional exponents) having at least d_{j} distinct terms, one for the lowest term in (3.4) and at least d_{j} − 1 for the distinct values of r coming from (3.5). The coefficients of these terms are distinct powers of ξ divided by d_{j}. These considerations imply that the images of the roots ψ_{j,ξ}(1) under T are linearly independent. Therefore the roots themselves are linearly independent over C. Moreover, they all satisfy the A-hypergeometric system with parameter \binom{−1}{0}, by Proposition 2.1. We conclude that the space H is n-dimensional and the roots ψ_{j,ξ}(1) form a basis for H.

We wish to prove ψ_{j,ξ}(1) = X_{j,ξ}. It suffices to show T (ψ_{j,ξ}(1)) = T (X_{j,ξ}) because the functional T defined above separates the space H. Equivalently, given any generic w in C, we must show that, in the w-grading, X_{j,ξ} has the same first two terms as ψ_{j,ξ}(1). This is clear for the first term, so we only need to look at the second term \frac{1}{d_{j}} ξ^{r+1−i_{j−1}} · a_{r} · a_{i_{j−1}}^{(r+1−i_{j})/d_{j}} · a_{i_{j}}^{(i_{j−1}−r−1)/d_{j}}. Let a^{v} denote this monomial. Let k be the unique integer between 1 and d_{j} such that r is congruent to i_{j−1}−1+k modulo d_{j}. If k = 1 then a^{v} equals the second lowest term (with respect to w) of the series ξ · [a_{i_{j−1}}^{1/d_{j}}a_{i_{j}}^{−1/d_{j}}]. If 2 ≤ k ≤ d_{j} − 1 then a^{v} equals the w-lowest term of the series indexed by k in the central sum in the definition of X_{j,ξ}. For k = d_{j} there are two subcases: if r > i_{j−1} then a^{v} equals the w-lowest term of the series indexed by k = d_{j} in the center sum; if r < i_{j−1} then a^{v} equals the w-lowest term of the rightmost series \frac{1}{d_{j}} [a_{i_{j−1}−1}/a_{i_{j}−1}]. In each of these four cases a^{v} is the second lowest term in X_{j,ξ}. This completes the proof of Theorem 3.2.

4. Integrality Issues To prove the identity f(X_{j,ξ}) = 0 in Theorem 3.2 we used the complex numbers. But, a posteriori, there is no need to stick with an algebraically closed field of characteristic zero. If K is any integral domain such that the equation ξ^{d_{j}} = −1 has d_{j} distinct solutions and the coefficients of X_{j,ξ} are defined in K, then f(X_{j,ξ}) = 0 is a valid identity in a suitable fractional power series ring over K. The following result shows that K can be an algebraically closed field of characteristic p, provided p is relatively prime to d_{1}d_{2} ⋯ d_{r}. The proof of Theorem 4.1 using Hensel’s Lemma was suggested to me by Hendrik Lenstra.

Theorem 4.1. All coefficients of the series X_{j,ξ} lie in the ring Z[\frac{1}{d_{j}}][ξ].

Proof: The series ψ_{j,ξ}(t) in (3.4) lies in the fractional power series ring R_{1}[[t^{\frac{1}{d_{j}}}]], where

R_{1} := Q[ ξ][a_{s} : s ∉ \{i_{j−1}, i_{j}\}][a_{i_{j−1}}^{± \frac{1}{d_{j}}} , a_{i_{j}}^{± \frac{1}{d_{j}}}].

This holds because ω is integral and each term of X_{j,ξ} = ψ_{j,ξ}(1) lies in R_{1}. To prove Theorem 4.1, it suffices to show that ψ_{j,ξ}(t) is an element of the subring R_{2}[[t^{\frac{1}{d_{j}}}]], where

R_{2} := Z[\frac{1}{d_{j}}][ ξ][a_{s} : s ∉ \{i_{j−1}, i_{j}\}][a_{i_{j−1}}^{± \frac{1}{d_{j}}} , a_{i_{j}}^{± \frac{1}{d_{j}}}].

We shall apply Hensel’s Lemma [5, Theorem 7.3] to the integral domain R_{2}[[t^{\frac{1}{d_{j}}}]]. This domain is complete with respect to the principal ideal m := ⟨t^{\frac{1}{d_{j}}} ⟩, and it contains all coefficients of the polynomial f_{t}(x) in (3.3). The constant term of ψ_{j,ξ}(t) lies in R_{2}; we

denote it by A := ξai_{j−1}^{\frac{1}{d_{j}}}a_{i_{j}}^{− \frac{1}{d_{j}}}. It is an “approximate root” in the sense that f_{t}(A) ∈ m and f′_{t}(A) is the sum of a unit in R_{2} and an element of m. By Hensel’s Lemma there exists a unique element B in R_{2}[[t^{\frac{1}{d_{j}}}]] such that f_{t}(B) = 0 and A − B ∈ m. By repeating the uniqueness part of this application of Hensel’s Lemma for the coefficient domain R_{1} instead of R_{2}, we conclude that B must be equal to our Puiseux series ψ_{j,ξ}(t).

A case of special interest is the finest triangulation, where I = {1, 2, …, n−1}, r = n, d_{j} = 1 for all j. Theorem 4.1 implies that in this case our construction is characteristic-free. In other words, the series solutions X_{j,−1} have integer coefficients. These series are

X_{j,−1} = −[\frac{a_{j−1}}{a_{j}} ] + [\frac{a_{j−2}}{a_{j−1}} ]  for j = 1, 2, …, n  (4.1)

where [\frac{a_{j−1}}{a_{j}} ] is the sum over all Laurent monomials

\frac{(−1)^{i_{j}}}{i_{j−1} + 1} · \binom{i_{j}}{i_{0} … i_{j−1} i_{j+1} … i_{n}} · \frac{a_{0}^{i_{0}}a_{1}^{i_{1}} ⋯ a_{j−2}^{i_{j−2}} a_{j−1}^{i_{j−1}+1} a_{j+1}^{i_{j+1}} ⋯ a_{n}^{i_{n}}}{a_{j}^{i_{j}+1}}  (4.2)

where i_{0}, i_{1}, …, i_{n} are non-negative integers satisfying the relations

\begin{matrix}i_{0} + i_{1} + i_{2} + i_{3} + ⋯ + i_{j−1} − i_{j} + i_{j+1} + ⋯ + i_{n} = 0 \\ i_{1} + 2i_{2} + 3i_{3} ⋯ + (j − 1)i_{j−1} − ji_{j} + (j + 1)i_{j+1} + ⋯ + ni_{n} = 0. \end{matrix}  (4.3)

For generating the series [\frac{a_{j−1}}{a_{j}} ] on a computer it convenient to rewrite (4.3) as follows.

\begin{aligned}i_{j−1} & = −ji_{0} − (j − 1)i_{1} − (j − 2)i_{2} − ⋯ − 2i_{j−2} + i_{j+1} + 2i_{j+2} + ⋯ + (n − j)i_{n}, \\ i_{j} & = −(j − 1)i_{0} − (j − 2)i_{1} − ⋯ − i_{j−2} + 2i_{j+1} + 3i_{j+2} + ⋯ + (n − j + 1)i_{n}. \end{aligned}

These equations ensure that the multinomial coefficient in (4.2) is divisible by i_{j−1} + 1.

5. Multivariate Outlook Consider a system of n polynomial equations in n variables, where the terms in the i-th equation have their exponent vectors in a fixed set A_{i} ⊂ Z^{n}. (This is the meaning of “sparse” in [9]). By Bernstein’s Theorem, the system has mixed volume many roots (X_{1}, …, X_{n}). Each coordinate X_{i} is an algebraic function in all the coefficients. It is natural to wonder whether X_{i} satisfies the A-hypergeometric differential equations where A is the configuration arising from the “Cayley trick” (cf. [7, 2.5], [8, page 273]):

A := A_{1} × {e_{1}} ∪ A_{2} × {e_{2}} ∪ ⋯ ∪ A_{n} × {e_{n}} ⊂ Z^{2n}.

The answer is no. The coordinates of the roots (X_{1}, …, X_{n}) are not A-hypergeometric. For example, let (X_{1}, X_{2}) be the unique solution of the system of two linear equations

a_{0} + a_{1}x_{1} + a_{2}x_{2} = b_{0} + b_{1}x_{1} + b_{2}x_{2} = 0.

Then we find

\frac{∂^{2}X_{2}}{∂a_{0}∂b_{1}} ≠ \frac{∂^{2}X_{2}}{∂a_{1}∂b_{0}} .

Note also that Mayr’s differential equations (40) and (45) in [10] are no longer binomial.

The correct generalization of Proposition 2.1 to higher dimensions is the following. Let J(x_{1}, …, x_{n}) denote the Jacobian det(\frac{∂f_{i}}{∂x_{j}}) of the given equations f_{1} = ⋯ = f_{n} = 0.

Proposition 5.1. For any integers u_{1}, u_{2}, …, u_{n} the algebraic function

\frac{X_{1}^{u_{1}}X_{2}^{u_{2}} ⋯ X_{n}^{u_{n}}}{J(X_{1}, X_{2}, …, X_{n})}  (5.1)

satisfies the A-hypergeometric differential equations arising from the Cayley trick.

Over the field of complex numbers, we can derive Proposition 5.1 from Theorem 2.7 in [7] using Cauchy’s formula in several variables. An alternative algebraic proof follows from the construction in [1, §2]. The quantity in (5.1) should be thought of as a local residue on a toric variety [4]. The sum over all (mixed volume many) local residues is the global residue associated with the monomial x_{1}^{u_{1}} ⋯ x_{n}^{u_{n}} relative to the given equations f_{1} = ⋯ = f_{n} = 0. The global residue is a rational function. It is of importance in elimination theory. We plan to extend the techniques in Section 3 to the setting of Proposition 5.1 in a subsequent joint work with E. Cattani and A. Dickenstein. The goal of that project is to develop new formulas and algorithms for computing local and global residues. Another interesting question is whether explicit Puiseux series expansions of (5.1) might be useful to improve the numerical component in the homotopy algorithm proposed in [9].

Acknowledgements

I am grateful to Alicia Dickenstein, Hendrik Lenstra and Michael Trott for helpful comments on earlier drafts of this paper. This project was partially supported by grants from the National Science Foundation (NYI) and the David and Lucile Packard Foundation.

References

[1] A. Adolphson and S. Sperber: Differential modules defined by systems of equations, Seminario Rendiconti di Universita di Padova, to appear.

[2] R. Birkeland: Über die Auflösung algebraischer Gleichungen durch hypergeometrische Funktionen, Mathematische Zeitschrift 26 (1927) 565–578.

[3] J.-L. Brylinski: Radon transform and functionals on the space of curves, Manuscript, 1993.

[4] E. Cattani, D. Cox and A. Dickenstein: Residues in toric varieties, Compositio Math., to appear.

[5] D. Eisenbud: Commutative Algebra with a View Towards Algebraic Geometry, Graduate Texts in Mathematics, Springer Verlag, New York, 1995.

[6] I.M. Gel’fand, A.V. Zelevinsky and M.M. Kapranov: Hypergeometric functions and toral manifolds, Functional Analysis and its Applications 23 (1989) 94–106.

[7] I.M. Gel’fand, A.V. Zelevinsky and M.M. Kapranov: Generalized Euler integrals and A-hypergeometric functions, Advances in Mathematics (1990) 84 255–271.

[8] I.M. Gel’fand, A.V. Zelevinsky and M.M. Kapranov: Discriminants, Resultants, and Multidimensional Determinants, Birkhäuser, Boston, 1994.

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

[10] K. Mayr: Über die Auflösung algebraischer Gleichungssysteme durch hypergeometrische Funktionen, Monatshefte für Mathematik und Physik 45 (1937) 280–313.

[11] J. McDonald: Fiber polytopes and fractional power series, Journal of Pure and Applied Algebra, 104 (1995) 213–233.

[12] Solving the Quintic with Mathematica, poster distributed by Wolfram Research, 1994.