On Computing Algebraic Functions using Logarithms and Exponentials

Dima Grigoriev^{1}, Michael Singer^{2}, and Andrew Yao^{3}

Abstract

Let ρ be a set of algebraic expressions constructed with radicals and arithmetic operations, and which generate the splitting field F of some polynomial. Let N_{β}(ρ) be the minimum total number of root-takings and exponentiations used in any straightline program for computing the functions in ρ by taking roots, exponentials, logarithms, and performing arithmetic operations. In this paper it is proved that N_{β}(ρ) = ν(G), where ν(G) is the minimum length of any cyclic Jordan-Hölder tower for the Galois group G of F. This generalizes a result of Ja’Ja’ [1], and shows that the inclusion of certain new primitives, such as taking exponentials and logarithms, does not improve the cost of computing such expressions as compared with programs which use only root-takings.

1Departments of Computer Science and Mathematics, Pennsylvania State University, University Park, Pennsylvania 16802.

2Department of Mathematics, North Carolina State University, Raleigh, North Carolina 27695-8205. Partially supported by NSF Grant DMS 90-24624.

3Department of Computer Science, Princeton University, Princeton, New Jersey 08544.

1 Introduction

The question of how efficiently one can evaluate expressions such as (∑_{1≤i<j≤n} \sqrt{(x_{i} − x_{j})^{2} + (y_{i} − y_{j})^{2}}) /\binom{n}{2}, the mean distance among n points in the plane, was raised in Shamos and Yuval [8]. A systematic study of this question was given in Pippenger [6,7]. Let ρ be a family of algebraic expressions constructed from indeterminates using radicals and arithmetic operations. Define the cost of a program to be the number of root-takings used, with arithmetic operations given for free. Let F be the extension field generated by the members of ρ over the field of rational functions with complex coefficients. It was shown [6,7] that, when the members of ρ are rational functions of the roots of rational functions, the mimimum cost is equal to the number of the torsion orders^{4} for the Galois group of F (an Abelian group in this case). An extension was given in Ja’Ja’ [1], who showed that the minimum cost is equal to the minimum length of any cyclic Jordan-Hölder tower for the Galois group of F, provided that F is a finite Galois extension over the field of rational functions. It is known [1,7] that the former result is a special case of the latter.

These results can be used to determine the minimum cost for computing ρ in many cases. For example, for the mean distance problem, the Galois group can be shown [6] to be isomorphic to (Z_{2})^{\binom{n}{2}}, which clearly has \binom{n}{2} torsion orders.

As taking a root y^{1/d} can be simulated by taking the logarithm log y followed by an exponentiation exp((log y)/d), a natural question is whether the availability of the lograrithm and exponential operations can substantially reduce the cost of evaluating algebraic expressions. In particular, can one evaluate the expression ∑_{1≤i≤n} \sqrt{x_{i}} using o(n) exponentiations and logarithm-takings? (Clearly, the expression can be evaluated with n root-takings.) The possible use of logarithms and exponentials, as well as other primitives, was mentioned in [8], but was not studied in later papers [1,6,7].

In this paper, we show that under the same assumption as in [1] (i.e. F being a finite Galois extension), the availability of taking logarithms and exponentials does not reduce the cost. In particular, we prove that n or more operations are needed to evaluate ∑_{1≤i≤n} \sqrt{x_{i}}, with arithmetic operations given for free. In the next section, we give a precise statement of the main result (Theorem 1), after introducing the needed notations and background. The result is then proved in Section 3; some additional concepts and results from Differential Algebra (see [2-4]) are used in the proof.

4Any finite Abelian group G can be uniquely decomposed into a direct sum of cyclic groups Z_{d_{1}} ⊕ Z_{d_{2}} ⊕ ⋯ Z_{d_{t}}, such that d_{t} > 1 and d_{i} is divisible by d_{i+1} for 1 ≤ i < t. The integers d_{i} are called the torsion orders of G; t is the number of torsion orders for G.

We remark that the complexity question under other cost measures, in which the cost of taking a d-th root may depend on d, were discussed in [1,6,7]. We will not pursue it here.

2 The Main Result

We use the standard teminology in Algebra (as in Lang [3]). In what follows, let Z^{+} be the set of all positive integers.

An α-program A is a sequence of instructions of the form z_{1} ← I_{1}, z_{2} ← I_{2}, ⋯, z_{m} ← I_{m}, where I_{i} are of the form (r_{i}(x_{1}, x_{2}, ⋯, x_{n}, z_{1}, ⋯, z_{i−1}))^{1/d_{i}} with r_{i} is a rational function in x_{1}, ⋯, x_{n}, z_{1}, ⋯, z_{i−1} with complex coefficients and d_{i} ∈ Z^{+}. We call m the cost of A. For 1 ≤ i ≤ m, let g_{i}(x_{1}, x_{2}, ⋯, x_{n}) be the functions defined inductively by g_{i}(x_{1}, x_{2}, ⋯, x_{n}) = (r_{i}(x_{1}, x_{2}, ⋯, x_{n}, g_{1}(x_{1}, ⋯, x_{n}), ⋯, g_{i−1}(x_{1}, ⋯, x_{n})))^{1/d_{i}}. We shall always assume that the r_{i} have been chosen so that the denominators of these functions do not vanish identically. Informally, g_{i}(x_{1}, x_{2}, ⋯, x_{n}) are the values assumed by the variables z_{i} for input (x_{1}, x_{2}, ⋯, x_{n}). Let E_{A} denote the set of all functions of the form r(x_{1}, x_{2}, ⋯, x_{n}, g_{1}(x_{1}, ⋯, x_{n}), ⋯, g_{m}(x_{1}, ⋯, x_{n})) where r is a rational function with complex coefficients whose denominator does not vanish identically when the substitution is made. We note that each element of E_{A} defines a function algebraic over the field F_{0} = C(x_{1}, ⋯, x_{n}) of rational functions in n variables with coeffcients in the complex numbers C.

A solvable algebraic expression is any element of E_{A} for any α-program A. Let ρ = (f_{1}, f_{2}, ⋯, f_{s}) be a finite set of solvable algebraic expressions. We say that ρ is computed by A, if each f_{i} ∈ E_{A}. Let N_{α}(ρ) be the minimum cost of any αprogram computing ρ. Clearly, N_{α}(ρ) is finite. For any such ρ, we can form the field F_{0}(ρ) which is the algebraic extension of F_{0} formed by adjoining the functions corredponding to the elements f_{1}, ⋯, f_{s} of ρ.

Following [1], ρ is said to be normal, if F_{0}(ρ) is a finite Galois extension of F_{0}. In other words, ρ is normal if ρ generates the splitting field of some polynomial over F_{0}.

For any solvable group G, a cyclic Jordan-Hölder tower is a normal tower of groups

G = G_{0} ▷ G_{1} ▷ ⋯ ▷ G_{m−1} ▷ G_{m} = 1,

where G_{i−1}/G_{i} is cyclic for each 1 ≤ i ≤ m. Let ν(G) be the length m of the shortest cyclic Jordan-Hölder tower for G.

The next result is from Ja’Ja’ [1] which we state as a lemma:

Lemma 1 [1] If ρ is normal, then N_{α}(ρ) = ν(G), where G is the Galois group for F_{0}(ρ) over F_{0}.

A β-program B is a sequence of instructions of the form z_{1} ← I_{1}, z_{2} ← I_{2}, ⋯, z_{m} ← I_{m}, where I_{i} are of the form a_{i}^{1/d_{i}}, exp(a_{i}), or log(a_{i}), where a_{i} = r_{i}(x_{1}, x_{2}, ⋯, x_{n}, z_{1}, ⋯, z_{i−1}) with r_{i} is a rational function in x_{1}, ⋯, x_{n}, z_{1}, ⋯, z_{i−1} with complex coefficients and d_{i} ∈ Z^{+}. We shall again always assume that the r_{i} have been chosen so that the denominators of these functions do not vanish identically. Let τ(B) be the number of instructions which either take roots or exponentials. Let g_{i}(x_{1}, x_{2}, ⋯, x_{n}) be the functions associated with variables z_{i}, defined exactly as in the case for α-programs. Let E_{B} denote the set of all functions of the form r(x_{1}, x_{2}, ⋯, x_{n}, g_{1}(x_{1}, ⋯, x_{n}), ⋯, g_{m}(x_{1}, ⋯, x_{n})) where r is a rational function with complex coefficients whose denomincators do not vanish identically when the substituion is made.

Let ρ = (f_{1}, f_{2}, ⋯, f_{s}) be a finite set of solvable algebraic expressions. We say that ρ is computed by B, if each element f_{i} of ρ equals a function in E_{B}. Let N_{β}(ρ) be the minimum τ(B) of any β-program B computing ρ.

Our main result is the following theorem:

Theorem 1 If ρ is normal, then N_{β}(ρ) = ν(G), where G is the Galois group for F_{0}(ρ) over F_{0}.

Corollary 1 If ρ is normal, then N_{β}(ρ) = N_{α}(ρ).

Corollary 2 Let ρ = \{ f \}, where f = ∑_{1≤i≤n} \sqrt{x_{i}}. Then N_{β}(ρ) = n.

Remark It is an interesting open question whether N_{β}(ρ) is equal to N_{α}(ρ) when ρ is not required to be normal.

3 Proof of Theorem 1

Before proving the theorem, we introduce some terms in Differential Algebra (see [2], [3], [4]). A differential field is a field k together with a set Δ = {δ_{i}} of mappings δ_{i} : k→k, called derivations, such that eachδ_{i} satisfies the conditions δ_{i}(a + b) = δ_{i}(a)+δ_{i}(b), δ_{i}(ab) = δ_{i}(a)b+aδ_{i}(b), and δ_{i}(δ_{j}(a)) = δ_{j}(δ_{i}(a)) for all δ_{i}, δ_{j} ∈ Δ, a, b ∈ k. For example, F_{0} can be considered a differential field when we use the derivations Δ = {δ_{1}, ⋯, δ_{n}} where δ_{i}(f) = ∂f/∂x_{i}. In this paper we are concerned only with differential fields that come from fields of differentiable functions a and that are extensions of this differential field. These extensions will be gotten by adjoining elements that can be interpreted as functions on some suitable region in complex n-space C^{n}. We will use K_{0} to denote the differential field obtained from the field F_{0} equipped with these standard derivations Δ. Note that if K is a differential field containing K_{0} and if a ∈ K, then the field obtained by adjoining exp(a) to K gives a differential field. The element exp(a) will satisfy the differential equations δ_{i}(exp(a)) = δ_{i}(a) · exp(a) for i = 1, ⋯, n. Similarly, the adjoining of log(a) gives a differential field and the element log(a) satisfies δ_{i}(log(a)) = δ_{i}(a)/afor i = 1, ⋯, n. We also note that if ρ = (f_{1}, ⋯, f_{s}) is a set of solvable algebraic expressions (or, more generally, any set of algebraic functions), the derivations Δ can be extended uniquely to derivations on F_{0}(ρ) ([4], Lemma 1, p.90).

The classical Galois theory for field theory can be extended to a differential Galois theory for differential fields (See [3] and [4] for definitions and discussions of these concepts; [2] contains an excellent exposition of the theory in the case of only one derivation and the essential results extend, mutatis mutandi to the case of several derivations). This galois theory can be used to study the structure of the solutions of a system of partial linear differential equations, provided that the equations generate a differential ideal of finite linear dimension or, equivalently (see [4], Chapter IV.5), the solution space is a finite dimensional vector space (i.e., the system is holonomic). This is the case for the equations defining exponentials and logarithms (see [3] and [4]). To avoid possible confusions, we will reserve the term Galois group for the classical Galois group, and use the term differential Galois group when differential fields are being discussed. It should be noted, though, that if k_{1} is an algebraic extension of k_{0}, a differential field of characteristic zero, then since all derivations on k_{0} can be extended uniquely to derivations on k_{1}, we can identify the Galois group of k_{1} over k_{0} with the differential galois group of k_{1} over k_{0} (with respect to these derivations). To see this note that any differential automorphism is by definition a usual automorphism. Conversely, for any automorphism σ of k_{1} over k_{0} and any derivation δ of k_{1} that leaves k_{0} invariant, we have that σ^{−1} ∘ δ ∘ σ is a derivation of k_{1} agreeing with δ on k_{0}. Uniqueness implies that they must be equal on all of k_{1} and so σ must be a differential automorphism. This remark allows us to apply results concerning differential galois theory to the galois theory of algebraic extensions of differential fields.

To prove Theorem 1, we first show that if F_{0}(ρ) is contained in a certain tower of differential fields, then there is a tower of algebraic extension fields of no greater length containing F_{0}(ρ). This result (Lemma 2 below) is at the heart of the proof for Theorem 1.

Let K_{0} ⊂ K_{1} ⊂ K_{2} ⊂ … ⊂ K_{m} be a tower of differential fields, where each K_{i} is obtained from K_{i−1} by adjoining an element u_{i}; u_{i} is either exp(a_{i}) or log(a_{i}) with a_{i} ∈ K_{i−1}. Let I be the set of 1 ≤ i ≤ m such that u_{i} is exp(a_{i}). We recall from differential Galois theory that in this case each K_{i} is a Picard-Vessiot extension of K_{i−1}. Furthermore, it is known (see [3, Section 4], or [4, Chapter VI.6]; [2, Lemmas 3.9 and 3.10] contains simillar results for the case of one derivation) that, if i ∈ I, the differential Galois group of K_{i} over K_{i−1} is an algebraic subgroup of C^{∗}, the multiplicative group of non-zero complex numbers, and if i ∉ I, then the differential Galois group of K_{i} over K_{i−1} is an algebraic subgroup of C^{+}, the additive group of complex numbers. Finally, we note that the proper algebraic subgroups of C^{∗} are precisely the finite cyclic groups and the only proper algebraic subgroup of C^{+} is the trivial group. This can be seen by noting that a proper Zariski closed subset of either of these two groups must be finite and that in the first case, we will have a finite multiplicative subgroup of a field and in the second case we will have a finite subgroup of a torsion free group.

Lemma 2 If F_{0}(ρ) ⊂ K_{m} then ν(G) ≤| I |.

Proof Let F_{i} = F_{0}(ρ) ∩ K_{i} for 1 ≤ i ≤ m. Then F_{m} = F_{0}(ρ). Note that F_{0} = F_{0}(ρ)∩K_{0}. Let H_{i} be the differential Galois group of K_{i} over K_{i−1}. We claim that the following statement is true for 1 ≤ i ≤ m :

Fact 1 F_{i} is a Galois extension of F_{i−1}.

To prove this fact, let E_{i} be the subfield of elements of K_{i} algebraic over K_{i−1}. E_{i} is a differential field and is left invariant by all elements of H_{i}. Therefore the differential Galois group of K_{i} over E_{i} is a normal subgroup of H_{i} and so E_{i} is a Galois extension of K_{i−1}. Note that F_{i} = E_{i} ∩F_{0}(ρ). Let p(x) be a polynomial with coeffcients in F_{i−1}. If p(x) = 0 has a root in F_{i}, it must split in both E_{i} and F_{0}(ρ) (since F_{0}(ρ) is a fortiori normal over F_{i−1}). Therefore p(x) = 0 splits in F_{i} and so F_{i} is a Galois extension of F_{i−1}.

Now let J_{i} be the Galois group of F_{i} over F_{i−1}. We claim that the following statement is true:

Fact 2 For 1 ≤ i ≤ m, J_{i} is the trivial group if i ∉ I, and a cyclic group if i ∈ I.

To prove this fact, consider the field K_{i−1} · F_{i}. This is a subfield of K_{i}. Since H_{i} is an abelian group, all of its subgroups are normal, so K_{i−1}·F_{i} is a normal extension of K_{i−1} whose differential Galois group L_{i} is the quotient of H_{i} by a closed subgroup of H_{i}. Furthermore, since K_{i−1} · F_{i} is a finite extension of K_{i−1} , L_{i} is finite and thus coincides with the Galois group of this extension. If i ∉ I, then H_{i} is either C^{+} or the trivial group. The only finite quotient of either of these groups by a closed subgroup is trivial. If i ∈ I, then H_{i} is either C^{∗} or a finite cyclic group. The only possible finite quotients of these groups by closed subgroups are cyclic. To finish the proof of Fact 2, we note that K_{i−1} ∩ F_{i} = F_{i−1} and so the Galois group J_{i} of F_{i} over F_{i−1} is isomorphic to L_{i} (see [5, Corollary, p. 400] or [4, Chapter VII, Theorem 1.12]; [2, Lemma 5.10] is a related result but deals only with the case of one derivation.)

We can now finish the proof of Lemma 2. Let G_{i} denote the group of automorphisms of F_{0}(ρ) leaving F_{i} fixed. By Facts 1 and 2, one concludes from the Galois theory that the series G = G_{0}, G_{1}, G_{2}, …, G_{m} = 1 forms a cyclic Jordan-Hölder tower, with G_{i−1}/G_{i} being isomorphic to J_{i}. Deleting all i ∉ I, we have a tower of length | I |. Hence ν(G) ≤| I | . □

We now turn to the proof of Theorem 1. Observe that N_{β}(ρ) ≤ N_{α}(ρ), which is no greater than ν(G) by Lemma 1. Thus, we only need to prove that N_{β}(ρ) ≥ ν(G).

Let B be any β-program for computing ρ. Without loss of generality, we may assume that no root-taking operations are used in B, as we can replace any instruction z ← r^{1/d} by two instructions y ← (log r)/d, z ← exp(y) without changing the value of τ(B). Let the instructions be z_{1} ← I_{1}, z_{2} ← I_{2}, ⋯, z_{m} ← I_{m}. Let g_{i}(x_{1}, x_{2}, ⋯, x_{n}) be the functions associated with variables z_{i}.

For 1 ≤ i ≤ m, let K_{i} be the differential field obatained by adjoining g_{i} to K_{i−1}. By definition, the functions of E_{B} correspond to elements of K_{m} and F_{0}(ρ) ⊂ K_{m}. By Lemma 2, this implies ν(G) ≤ τ(B). This proves ν(G) ≤ N_{β}(ρ), and completes the proof of Theorem 1. Corollary 1 follows immediately from the theorem and Lemma 1.

To prove Corollary 2, we note that ρ is normal and the Galois group G of F_{0}(ρ) over F_{0} is isomorphic to Z_{2}^{n}. ¿From the result in [1, 7] (see [7, p. 399, Lemma 3.2]), ν(G) is equal to the number of torsion orders of G which is cleary n. Corollary 2 follows from the theorem immediately.

References

[1] J. Ja’ Ja’, “Computation of algebraic functions with root extractions,” Proceedings of 22nd IEEE Symposium on Foundations of Computer Science, 1981, 95-100.

[2] I. Kaplansky, An Introduction to Differential Algebra, Hermann, Paris, 1957.

[3] E. R. Kolchin, “Picard–Vessiot theory of partial differential fields,” Proceedings of the American Mathematical Society, 3 (1952), 596–603.

[4] E. R. Kolchin, Differential Algebra and Algebraic Groups, Academic Press, New York, 1973.

[5] S. Lang, Algebra, Addison-Wesley, Menlo Park, California, 1984 (Second Edition).

[6] N. Pippenger, “Computational complexity of algebraic functions,” Journal of Computer and System Sciences 22 (1981), 454-470.

[7] N. Pippenger, “Corrections to ‘Computational complexity of algebraic functions’,” Journal of Computer and System Sciences 37 (1988), 395-399.

[8] M. Shamos and G. Yuval, “Lower bounds from complex function theory,” Proceedings of 17th IEEE Symposium on Foundations of Computer Science, 1976, 268-273.