Computability of the Additive Complexity of Algebraic Circuits with

Root Extracting

Dima Grigoriev ^{∗}  Marek Karpinski ^{†}

Abstract

We design an algorithm for computing the generalized (algebraic circuits with root extracting, cf. [P 81], [J 81], [GSY 93]) additive complexity of any rational function. It is the first computability result of this sort on the additive complexity of algebraic circuits.

∗Dept. of Computer Science, The Pensylvania State University, University Park, PA 16802, and the Steklov Mathematical Institute, Fontanka 27, St. Petersburg, 191011 Russia. Email: dima@cs.psu.edu.

†Dept. of Computer Science, University of Bonn, 5300 Bonn 1. Supported in part by the International Computer Science Institute, Berkeley, California, by the DFG Grant KA 673/4-1 and by the ESPRIT BR

Grant 7079. Email: marek@cs.bonn.edu.

1 Introduction

It is a well known open problem in the theory of computation, whether the additive complexity of functions is computable. Note that both multiplicative and total complexities of functions are computable. In this paper we prove, somewhat surprisingly, the computability of the generalized additive complexity for algebraic circuits with root extraction. These circuits were considered in [J 81] where a lower bound on the number of root extracting operations for computing on algebraic functions has been proven. This was recently generalized in [GSY 93] for the algebraic circuits which contain in addition also exponential and logarithmic functions. Our result is the first computability result of this sort on the additive complexity of algebraic circuits.

Let us give the definition of the generalized additive complexity. We say that a rational function f ∈ (X_{1}, …, X_{n}) has a generalized additive complexity at most t, if there exists a sequence of algebraic functions:

u_{i+1} = ε^{(i+1)}X_{1}^{α_{1}^{(i+1)}} ⋯ X_{n}^{α_{n}^{(i+1)}}u_{1}^{β_{1}^{(i+1)}} ⋯ u_{i}^{β_{i}^{(i+1)}} + κ^{(i+1)}X_{1}^{γ_{1}^{(i+1)}} ⋯ X_{n}^{γ_{n}^{(i+1)}}u_{1}^{δ_{1}^{(i+1)}} ⋯ u_{i}^{δ_{i}^{(i+1)}}

for 0 ≤ i ≤ t, where κ^{(t+1)} = 0, f = u_{t+1} and all the exponents α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ , 0 ≤ i ≤ t are rationals, coefficients ε^{(i+1)}, κ^{(i+1)} ∈ ¯ are algebraic. The rationality of the exponents (rather than being integers) differs the generalized additive complexity from the usual additive complexity.In other words we consider the algebraic circuits in which in addition to the usual arithmetic operations also extracting an arbitrary root is admitted.

If t equals to the generalized additive complexity of f then we say that computation u_{1}, …, u_{t+1} of f is generalized additive-minimal.

In the first section we consider the computations in which the exponents α_{1}^{(i+1)}, …, δ_{i}^{(i+1)}, 0 ≤ i ≤ t are admitted to be algebraic and the adjusted for this situation notion of the quasi-additive complexity. The computation of the quasi-additive complexity is reduced (see lemma below) to the problem of quantifier elimination in the theory of differentially closed fields (solved in [Se 56], for its complexity see [G 89]).

In the section 2 we prove (see proposition below) that any quasi-additive minimal computation of a rational function can be transformed into a generalized additive-minimal computation with the same number of additions which contains only rational exponents, thus quasi-additive and generalized additive complexities coincide. Moreover, corollary in the section 2 gives a possiblitiy to construct the rational exponents of a generalized additiveminimal computation. In the section 3 we describe an algorithm for producing a generalized additive-minimal computation. In the case of one variable (n = 1) we give an (elementary) complexity bound of the designed algorithm (see theorem below) as it uses the quantifier elimination algorithm from [G 89]. In the general case (n ≥ 2) we do not give complexity bounds as the quantifier elimination method from [Se 56] is invoked which relies in its turn on the efficient bounds in Hilbert’s Idealbasissatz which are unknown to be elementary.

Note that a lower bound on additive complexity of f in terms of the variety of real roots of f was obtained in [G 83] (see also [Ri 85]) where one can find also a survey on other lower bounds, in particular for additive complexity (see also [G 82] [SW 80]). The lower bound from [G 83] is used (see the end of section 3) to show that there are polynomials with the generalized additive complexity equal to 3 and arbitrary large additive complexity.

2 Describing quasi-additive complexity in terms of the firstorder theory of differentially closed fields

We start with designing an algorithm for testing, whether there exist (and if so, also to produce) algebraic exponents α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ ¯ in the computation u_{1}, …, u_{t+1} providing an identity u_{t+1} = f holds. In this case we say that f has the quasi-additive complexity at most t. For this purpose we introduce the (differential) unknowns

u_{i+1}, α̃_{1}^{(i+1)}, …, δ̃_{i}^{(i+1)}, v_{1}^{(i+1)}, …, v_{n}^{(i+1)}, w_{1}^{(i+1)}, …, w_{i}^{(i+1)}, ṽ_{1}^{(i+1)}, …, ṽ_{n}^{(i+1)}, w̃_{1}^{(i+1)}, …, w̃_{i}^{(i+1)}

for all 0 ≤ i ≤ t and the system of (partial) differential equations (denote D_{i} = \frac{d}{dX_{i}} and by D any of the operators D_{1}, …, D_{n}, by δ(l, j) denote the Kronecker symbol):

D(α̃_{1}^{(i+1)}) = ⋯ = D(δ̃_{i}^{(i+1)}) = 0  (1a)_{i+1}
D_{j}(v_{l}^{(i+1)}) = \frac{α̃_{l}^{(i+1)}}{X_{l}} v_{l}^{(i+1)}δ(l, j); D_{j}(ṽ_{l}^{(i+1)}) = \frac{γ̃_{l}^{(i+1)}}{X_{l}} ṽ_{l}^{(i+1)}δ(l, j), 1 ≤ l, j ≤ n (1b)_{i+1}
D(w_{l}^{(i+1)}) = β̃_{l}^{(i+1)}w_{l}^{(i+1)} \frac{Du_{l}}{u_{l}}; D(w̃_{l}^{(i+1)}) = δ̃_{l}^{(i+1)}w̃_{l}^{(i+1)} \frac{Du_{l}}{u_{l}} , 1 ≤ l ≤ i (1c)_{i+1}
u_{i+1} = v_{1}^{(i+1)} ⋯ v_{n}^{(i+1)}w_{1}^{(i+1)} ⋯ w_{i}^{(i+1)} + ṽ_{1}^{(i+1)} … ṽ_{n}^{(i+1)}w̃_{1}^{(i+1)} … w̃_{i}^{(i+1)}  (1d)_{i+1}

for all 0 ≤ i ≤ t together with the equation u_{t+1} = f. The resulting system we denote by (1).

Note that the equations (1a)_{i+1} imply that α̃_{1}^{(i+1)}, …, δ̃_{i}^{(i+1)} ∈ ¯ are the constants; (1b)_{i+1} imply that v_{l}^{(i+1)} = μ_{l}^{(i+1)}X_{l}^{α̃_{l}^{(i+1)}}, ṽ_{l}^{(i+1)} = μ̃_{l}^{(i+1)}X_{l}^{γ̃_{l}^{(i+1)}} for the appropriate constants

μ_{l}^{(i+1)}, μ̃_{l}^{(i+1)} ∈ ¯ ; (1c)_{(i+1)} imply that w_{l}^{(i+1)} = ν_{l}^{(i+1)}uβ̃_{l}^{(i+1)} ; l, w̃_{l}^{(i+1)} = ν̃_{l}^{(i+1)}uδ̃_{l}^{(i+1)} ; l for the

appropriate constants ν_{l}^{(i+1)}, ν̃_{l}^{(i+1)} ∈ ¯ .

Thus, the following lemma is proved. Lemma. The solvability of system (1) (in all its differential unknowns) is equivalent to the fact that the quasi-additive complexity of f is at most t.

Now we consider the statement of solvability of the system (1) as an existentional formula of the first-order theory of differentially closed fields [Se 56]. Applying to it a quantifier elimination algorithm [Se 56] one can eliminate unknowns

u_{i+1}, v_{1}^{(i+1)}, …, v_{n}^{(i+1)}, w_{1}^{(i+1)}, …, w_{i}^{(i+1)}, ṽ_{1}^{(i+1)}, …, ṽ_{n}^{(i+1)}, w̃_{1}^{(i+1)}, …, w̃_{i}^{(i+1)}for all 0 ≤ i ≤ t.

As a result we get an (existentional) equivalent formula containing only the unknowns α̃_{1}^{(i+1)}, …, δ̃_{i}^{(i+1)}, 0 ≤ i ≤ t. Because of (1a) the latter formula can be considered as a formula in the language of polynomials (so, without derivatives), thus as a system of polynomial equations and inequalities with integer coefficients.

Thus, given a rational function f the algorithm tries t = 1, 2, …, and for each t tests (using [CG 83]), whether the above constructed system of polynomial equations and inequalities has a solution (over ¯ ). For a minimal such t we take any of these solutions α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ ¯ , 0 ≤ i ≤ t. In the next section we show that in this case there exists as well a rational solution of this system and moreover we show how to construct it.

To solve the system (1) of differential equations we applied the algorithm from [Se 56] for which elementary complexity bound is unknown since it relies on an efficient bound in Hilbert‘s Idealbasissatz. But the complexity of quantifier elimination is elementary in the case of ordinary differential equations for the algorithm designed in [G 89], i. e. when n = 1, in another words when there is only one independent variable X. In this case the system (1) contains O(t^{2}) unknows, the order of highest occurring derivatives in the equations is at most 1, the degree of the equations is at most O(t) + deg f and the number of equations is at most O(t^{2}), the bit-size of the coefficients of the occuring equations is at most O(1) + M, where M is the bit-size of the coefficients of f. Therefore (see the bounds in [G 89]), one can eliminate quantifiers and produce a system of polynomial equations and inequalities with integer coefficients (see above) in the unknowns α̃_{1}^{(i+1)}, …, δ̃_{i}^{(i+1)}, 0 ≤ i ≤ t in time N = M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} ; the degrees of the polynomials occurring in this system do not exceed N_{1} = (degf)^{2^{2^{O(t^{2})}}} the number of these polynomials is at most N_{1} and the bit-size of (integer) coefficients occurring in this system can be bounded by N.

Thereupon to solve this system of polynomial equations and inequalities we apply the algorithm from [CG 83] which requires time M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} . The algorithm from [CG 83] finds (provided that the system is solvable) a solution α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ ¯ , 0 ≤ i ≤ t in the following form. The algorithm produces an irreducible over polynomial φ(Z) ∈ [Z], also polynomials ᾱ_{1}^{(i+1)}(Z), …, δ̄_{i}^{(i+1)}(Z) ∈ [Z], 0 ≤ i ≤ t such that α_{1}^{(i+1)} = ᾱ_{1}^{(i+1)}(θ), …, δ_{i}^{(i+1)} = δ̄_{i}^{(i+1)}(θ) where θ ∈ ¯ is a root of φ(θ) = 0. From [CG 83] we obtain the following bounds:

deg(φ), deg(ᾱ_{1}^{(i+1)}), …, deg(δ̄_{i}^{(i+1)}) ≤ (deg f)^{2^{2^{O(t^{2})}}} 0 ≤ i ≤ t

and the bit-size of every coefficient occurring in the listed polynomialsdoes not exceed M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} .

3 Rational exponents in the quasi-additive minimal computation

In this section we prove (see the proposition below) the coincidence of the generalized additive and quasi-additive complexities for rational functions. Moreover, we show (see Corollary below) how for given algebraic exponents of a quasi-additive minimal computation to produce the exponents of a certain generalized additive-minimal computation of the same rational function, thus containing only rational exponents. The similar statements were proved also for the rationality of the exponents in the minimal sparse representations of a rational function [GKS 92a] and of a real algebraic function [GKS 92a]. But the latter statements have different (from the one in the present paper) nature, also another difference is that we prove here the existence of the rational exponents rather than the rationality as it was the case in [GKS 92a], [GKS 92a].

So, let

u_{i+1} = ε^{(i+1)}X_{1}^{α_{1}^{(i+1)}} ⋯ X_{n}^{α_{n}^{(i+1)}}u_{1}^{β_{1}^{(i+1)}} ⋯ u_{i}^{β_{i}^{(i+1)}} + κ^{(i+1)}X_{1}^{γ_{1}^{(i+1)}} ⋯ X_{n}^{γ_{n}^{(i+1)}}u_{1}^{δ_{1}^{(i+1)}} ⋯ u_{i}^{δ_{i}^{(i+1)}}

where 0 ≤ i ≤ t, κ^{(t+1)} = 0 and all the exponents and coefficients

α_{1}^{(i+1)}, …, δ_{i}^{(i+1)}, ε^{(i+1)}, κ^{(i+1)} ∈ ¯ .

Proposition. Assume that f = u^{(i+1)} ∈ ¯ (X_{1}, …, X_{n}) is a rational function and t is the minimal possible (so t equals to the quasi-additive complexity of f). Then there exist rational exponents a_{1}^{(i+1)}, …, d_{i}^{(i+1)} ∈ , 0 ≤ i ≤ t, respectively, providing also a computation of f (thus, t equals also to the generalized additive complexity). Proof. For each 1 ≤ j ≤ n consider a -basis θ̄_{j}^{(1)}, θ̄_{j}^{(2)}, … ∈ ¯ of the -linear hull {α_{j}^{(s)}, γ_{j}^{(s)}}_{1≤s≤t+1}. If 1 (thereby ) is contained in the latter linear hull, then we set θ̄_{j}^{(1)} = 1. Denote {θ_{j}^{(1)}, θ_{j}^{(2)}, …} = {θ̄_{j}^{(1)}, θ̄_{j}^{(2)}, …} \ {1}.

Consider a differential field F_{j}, 0 ≤ j ≤ n generated over ¯ (X_{1}, …, X_{n}) by the elements log X_{1}, X_{1}^{θ_{1}^{(1)}}, X_{1}^{θ_{1}^{(2)}}, …, log X_{j}, X_{j}^{θ_{j}^{(1)}}, X_{j}^{θ_{j}^{(2)}}, . . .. Then in the terminology of [RC 79] each F_{j}, 0 ≤ j ≤ n is a log-explicit extension of its field of constants ¯ (one can represent X^{β} = exp(β log X)).

We claim that the elements X_{j+1}^{θ_{j+1}^{(1)}}, X_{j+1}^{θ_{j+1}^{(2)}}, … ∈ F_{j+1} are algebraically independent over the field F_{j}(log X_{j+1}). Assume the contrary. Then the corollary 3. 2 [RC 79] (see also [Ro 76]) implies the existence of a constant κ ∈ ¯ , rational numbers

l_{1}^{(0)}, l_{1}^{(1)}, …, l_{j}^{(0)}, l_{j}^{(1)}, …, l_{j+1}^{(0)}, l_{j+1}^{(1)}, … ∈

such that not all l_{j+1}^{(1)}, l_{j+1}^{(2)}, … are zeroes and

Xl_{j+1}^{(0)}+ ∑_{k≥1} l_{j+1}^{(k)}θ_{j+1}^{(k)}_{j+1} = κXl_{1}^{(0)}+ ∑_{k≥1} l_{1}^{(k)}θ_{1}^{(k)}_{1} ⋯ Xl_{j}^{(0)}+ ∑_{k≥1} l_{j}^{(k)}θ_{j}^{(k)}_{j}

but this leads to a contradiction since the derivative \frac{d}{dX_{j+1}} of the left side is nonzero, but of the right side equals to zero.

For each 1 ≤ i ≤ t consider a -basis η̄_{i}^{(1)}, η̄_{i}^{(2)}, … ∈ ¯ of the -linear hull {β_{i}^{(s)}, δ_{i}^{(s)}}_{i+1≤s≤t+1}. If 1 (thereby ) is contained in the latter linear hull, then we set η̄_{i}^{(1)} = 1. Denote {η_{i}^{(1)}, η_{i}^{(2)}, …} = {η̄_{i}^{(1)}, η̄_{i}^{(2)}, …} \ {1}.

Denote by E_{i}, 0 ≤ i ≤ t a field generated over F_{n} by the elements

log u_{1}, u_{1}^{η_{1}^{(1)}}, u_{1}^{η_{1}^{(2)}}, …, log u_{i}, u_{i}^{η_{i}^{(1)}}, u_{i}^{η_{i}^{(2)}}, ….

It is a log-explicit extension of its field of constants ¯ .

We claim that for 0 ≤ i ≤ t − 1 the elements u_{i+1}^{η_{i+1}^{(1)}}, u_{i+1}^{η_{i+1}^{(2)}}, … ∈ E_{i+1} are algebraically independent over the field E_{i}(log u_{i+1}). Assume the contrary. Then again using corollary 3.2 [RC 79] we conclude that there exist a constant ε ∈ ¯ , rational numbers

p_{1}, p_{1}^{(1)}, p_{1}^{(2)}, …, p_{n}, p_{n}^{(1)}, p_{n}^{(2)}, …, z_{1}, z_{1}^{(1)}, z_{1}^{(2)}, …, z_{i+1}, z_{i+1}^{(1)}, z_{i+1}^{(2)}, … ∈

such that not all z_{i+1}^{(1)}, z_{i+1}^{(2)}, … are zeroes and

u_{i+1}^{z_{i+1}+_{∑_{j≥1}}z_{i+1}^{(j)}η_{i+1}^{(j)}} = εX_{1}^{p_{1}+_{∑_{j≥1}}p_{1}^{(j)}θ_{1}^{(j)}} ⋯ X_{n}^{p_{n}+_{∑_{j≥1}}p_{n}^{(j)}θ_{n}^{(j)}}u_{1}^{z_{1}+_{∑_{j≥1}}z_{1}^{(j)}η_{1}^{(j)}} ⋯ u_{i}^{z_{i}+_{∑_{j≥1}}z_{i}^{(j)}η_{i}^{(j)}}.

This provides an expression of u_{i+1} as a product of powers of X_{1}, …, X_{n}, u_{1}, … u_{i} and thereby we can diminish t by one in the computation of f, this contradiction with the minimality of t proves the algebraic independency of u_{i+1}^{η_{i+1}^{(1)}}, u_{i+1}^{η_{i+2}^{(2)}}, … over E_{i}(log u_{i+1}).

Consider the expansions

\begin{matrix}α_{j}^{(s)} = a_{j}^{(s)} + ∑_{k≥1} a_{j,k}^{(s)}θ_{j}^{(k)}, γ_{j}^{(s)} = & c_{j}^{(s)} + ∑_{k≥1} c_{j,k}^{(s)}θ_{j}^{(k)}, & 1 ≤ j ≤ n, & 1 ≤ s ≤ t + 1 \\ β_{i}^{(s)} = b_{i}^{(s)} + ∑_{k≥1} b_{i,k}^{(s)}η_{i}^{(k)}, δ_{i}^{(s)} = & d_{i}^{(s)} + ∑_{k≥1} d_{i,k}^{(s)}θ_{i}^{(k)}, & 1 ≤ i ≤ t + 1, & i < s ≤ t + 1 \end{matrix} (2)

where a_{j}^{(s)}, …, d_{i,k}^{(s)} ∈ are suitable rationals. Remark that if 1 ∉ {θ̄_{j}^{(1)}, θ̄_{j}^{(2)}, …} then a_{j}^{(s)} = c_{j}^{(s)} = 0, also if 1 ∉ {η̄_{i}^{(1)}, η̄_{i}^{(2)}, …} then b_{i}^{(s)} = d_{i}^{(s)} = 0. Then the initial computation u_{1}, u_{2}, … we can rewrite as follows:

\begin{matrix}u_{i+1} = & ε^{(i+1)}X_{1}^{a_{1}^{(i+1)}}(X_{1}^{θ_{1}^{(1)}})^{a_{1,1}^{(i+1)}}(X_{1}^{θ_{1}^{(2)}})^{a_{1,2}^{(i+1)}} ⋯ X_{n}^{a_{n}^{(i+1)}}(X_{n}^{θ_{n}^{(1)}})^{a_{n,1}^{(i+1)}} ⋯ \\ & u_{1}^{b_{1}^{(i+1)}}(u_{1}^{η_{1}^{(1)}})^{b_{1,1}^{(i+1)}}(u_{1}^{η_{1}^{(2)}})^{b_{1,2}^{(i+1)}} ⋯ u_{i}^{b_{i}^{(i+1)}}(u_{i}^{η_{i}^{(1)}})^{b_{i,1}^{(i+1)}}(u_{i}^{η_{i}^{(2)}})^{b_{i,2}^{(i+1)}} ⋯ + \\ & κ^{(i+1)}X_{1}^{c_{1}^{(i+1)}}(X_{1}^{θ_{1}^{(1)}})^{c_{1,1}^{(i+1)}}(X_{1}^{θ_{1}^{(2)}})^{c_{1,2}^{(i+1)}} ⋯ X_{n}^{c_{n}^{(i+1)}}(X_{n}^{θ_{n}^{(1)}})^{c_{n,1}^{(i+1)}} ⋯ \\ & u_{1}^{d_{1}^{(i+1)}}(u_{1}^{η_{1}^{(1)}})^{d_{1,1}^{(i+1)}}(u_{1}^{η_{1}^{(2)}})^{d_{1,2}^{(i+1)}} ⋯ u_{i}^{d_{i}^{(i+1)}}(u_{i}^{η_{i}^{(1)}})^{d_{i,1}^{(i+1)}}(u_{i}^{η_{i}^{(2)}})^{d_{i,2}^{(i+1)}} ⋯ \end{matrix} (3)

From the latter expression one can show by induction on i that u_{i+1} (and thereby each of the previous elements u_{1}, …, u_{i}) is algebraic over the field E′_{i} ⊂ E_{i} generated over ¯ (X_{1}, …, X_{n}) by the elements

X_{1}^{θ_{1}^{(1)}}, X_{1}^{θ_{1}^{(2)}}, …, X_{n}^{θ_{n}^{(1)}}, X_{n}^{θ_{n}^{(2)}}, …, u_{1}^{η_{1}^{(1)}}, u_{1}^{η_{1}^{(2)}}, …, u_{i}^{η_{i}^{(1)}}, u_{i}^{η_{i}^{(2)}}, …

Above we have proved that the latter elements are algebraically independent over ¯ (X_{1}, …, X_{n}). As u_{t+1} = f ∈ ¯ (X_{1}, …, X_{n}) we can substitute in the expression (3) instead of the elements

X_{1}^{θ_{1}^{(1)}}, X_{1}^{θ_{1}^{(2)}}, …, X_{n}^{θ_{n}^{(1)}}, X_{n}^{θ_{n}^{(2)}}, …, u_{1}^{η_{1}^{(1)}}, u_{1}^{η_{1}^{(2)}}, …, u_{t}^{η_{t}^{(1)}}, u_{t}^{η_{t}^{(2)}}, …

almost (in the sense of Zariski topology) arbitrary constants

y_{1}^{(1)}, y_{1}^{(2)}, …, y_{n}^{(1)}, y_{n}^{(2)}, …, z_{1}^{(1)}, z_{1}^{(2)}, …, z_{t}^{(1)}, z_{t}^{(2)}, … ∈ ¯ ,

respectively, with the mere requirement that in the intermediate computations of u_{1}, u_{2}, …, u_{t+1} = f there is no taking nonpositive powers of zero (each time we choose some branch of a rational power).

As a result we get a computation of ũ_{1}, ũ_{2}, …, ũ_{t+1} = f in which only rational exponents occur, namely

ũ_{i+1} = ε̃^{(i+1)}X_{1}^{a_{1}^{(i+1)}} ⋯ X_{n}^{a_{n}^{(i+1)}}ũ_{1}^{b_{1}^{(i+1)}} ⋯ ũ_{i}^{b_{i}^{(i+1)}} +κ̃^{(i+1)}X_{1}^{c_{1}^{(i+1)}} ⋯ X_{n}^{c_{n}^{(i+1)}}ũ_{1}^{d_{1}^{(i+1)}} ⋯ ũ_{i}^{d_{i}^{(i+1)}} (4)

for some ε̃^{(i+1)} , κ̃^{(i+1)} ∈ ¯ . The proposition is proved.

From the proof of the proposition we extract the Corollary. For every 1 ≤ i ≤ t, 1 ∈ {β_{i}^{(s)}, δ_{i}^{(s)}}_{i+1≤s≤t+1}. For any -basis θ̄_{j}^{(1)}, θ̄_{j}^{(2)}, … of {α_{j}^{(s)}, γ_{j}^{(s)}}_{1≤s≤t+1} and any -basis η̄_{i}^{(1)}, η̄_{i}^{(2)}, … of {β_{i}^{(s)}, δ_{i}^{(s)}}_{i+1≤s≤t+1} we get the rational exponents of the resulting computation of ũ_{1}, …, ũ_{t+1} (see (4)) from the expansions (2).

In order to show that 1 ∈ {β_{i}^{(s)}, δ_{i}^{(s)}}_{s} observe that otherwise b_{i}^{(s)} = d_{i}^{(s)} = 0 for all i + 1 ≤ s ≤ t + 1 and we could diminish t by deleting ũ_{i} from the computation ũ_{1}, …, ũ_{t+1} and get a contradiction with a minimality of t.

Remark that the corollary together with lemma 12 [GKS 92a] entail that for any i the constructible set of all the possible exponent vectors (β_{i}^{(i+1)}, …, β_{i}^{(t+1)}, δ_{i}^{(i+1)}, …, δ_{i}^{(t)}) ∈ ¯ 2t−2i+1 is contained in a finite union of the hyperplanes of the kind

∑_{i+1≤j≤t+1}b̂_{i}^{(j)}β_{i}^{(j)} + ∑_{i+1≤j≤t}d̂_{i}^{(j)}δ_{i}^{(j)} = d̂

where b̂_{i}^{(j)}, d̂_{i}^{(j)}, d̂∈ . The similar holds also for the vectors (α_{i}^{(1)}, …, α_{i}^{(t+1)}, γ_{i}^{(1)}, …, γ_{i}^{(t)}) ∈ ¯ 2t+1 . But we will not use this remark.

Note also that in the resulting computation (4) the rational exponents depend on the choice of the -basis (see the corollary). The following simple example demonstrates that the dependency really can happen:

u_{1} = X^{α}(X + 1), u_{2} = X^{−aα}u_{1}^{a} + X^{−bα}u_{1}^{b} = (X + 1)^{a} + (X + 1)^{b}

where α ∈ ¯ \ , a, b ∈ . Choosing a basis α + z, 1 ∈ {1, α}, for arbitrary z ∈ , we get

u_{1} = (X^{α+z})X^{1−z} + (X^{α+z})X^{−z}
u_{2} = (X^{α+z})^{−a}X^{za}u_{1}^{a} + (X^{α+z})^{−b}X^{zb}u_{1}^{b}

and by the corollary

u_{1} = wX^{1−z} + wX^{−z}
u_{2} = w^{−a}X^{za}u_{1}^{a} + w^{−b}X^{zb}u_{1}^{b}

for arbitrary w ∈ ¯ \ {0}.

4 Constructing a generalized additive-minimal computation

The first two sections (see lemma and corollary) give us a possibility to compute a generalized additive complexity t of a rational function f. Now we complete an algorithm which finds some generalized additive-minimal circuit computing f. Using the corollary from the section 2 the algorithm finds rational exponents α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ , 0 ≤ i ≤ t, it remains to find the coefficients ε^{(i+1)}, κ^{(i+1)} ∈ ¯ , 0 ≤ i ≤ t.

Denote by M a bound on the bit-sizes of the rational exponents α_{1}^{(i+1)}, …, δ_{i}^{(i+1)} ∈ , 0 ≤ i ≤ t. Then by induction on i one can easily show that each u_{i+1}, v_{1}^{(i+1)}, …, w̃_{i}^{(i+1)}, 0 ≤ i ≤ t is an algebraic function of the degree (i.e. the degree of a minimal polynomial to which satisfies the function) at most N = (exp(M))^{t^{O(t)}}. Hence the coefficients ε^{(i+1)}, κ^{(i+1)}, 0 ≤ i ≤ t fit if and only if for every 1 ≤ x_{1}, …, x_{n} ≤ N^{2} for which all the intermediate computations of the circuit are definable, the equality u_{t+1}(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n}) holds. So, for every fixed 1 ≤ x_{1}, …, x_{n} ≤ N^{2} we introduce the variables

u_{t+1}(x_{1}, …, x_{n}), v_{1}^{(i+1)}(x_{1}, …, x_{n}), …, w̃_{i}^{(i+1)}(x_{1}, …, x_{n}), 0 ≤ i ≤ t

and write down a system of polynomial equations and inequalities expressing all the operations of the circuit (provided that they are all definable) and finally the relation u_{t+1}(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n}). Then the algorithm invoking [CG 83] solves this system in N^{2n} + 2t + 1 variables and finds in particular ε^{(i+1)}, κ^{(i+1)} ∈ ¯ , 0 ≤ i ≤ t. More precisely, for each subset J ⊂ {1, …, N^{2}}^{n} we consider a system as above including in it just the points (x_{1}, …, x_{n}) ∈ J (so, J plays the role of the set of points in which the computation is defined). The algorithm solves this system and takes J with the maximal cardinality for which the system is solvable. In a more sophisticated way we can partition the cube {1, …, N^{2}}^{n} into N^{n} subcubes with sides equal to N and as J take each of these subcubes, but this improvement does not change the complexity bounds below.

In the ordinary case (n = 1) we can bound the complexity of the described algorithm. First, observe that in this case M ≤ M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} (see the end of the section 1). Therefore, the system of polynomial equations and inequalities constructed above contains exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} ) polynomials of degrees at most exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} )in exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} ) variables. Hence one can solve it using the algorithm from [CG 83] in time exp(exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} )) and find ε^{(i+1)}, κ^{(i+1)} ∈ ¯ , 0 ≤ i ≤ t representing them as algebraic numbers as at the end of section 1 with the size bounded also by the latter value.

Summarizing, we formulate Theorem.

a) There is an algorithm calculating the generalized additive complexity of a rational function f ∈ (x_{1}, …, x_{n}) and constructing a generalized additive-minimal circuit computing f;

b) In the case of one-variable rational functions f the running time of the algorithm from a) can be bounded by exp(exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} )), where M bounds the bitsize of each (rational) coefficient of f. The absolute values of the numerators and denominators of the found rational exponents in a generalized additive-minimal circuit computing f do not exceed exp(M^{O(1)}(degf)^{2^{2^{O(t^{2})}}} ) .

At the end we demonstrate that there could be a big gap between the the additive complexity and generalized additive complexity. Consider a polynomial

f_{n} = (1 + X^{\frac{1}{2}} )^{n} + (1 − X^{\frac{1}{2}} )^{n} ∈ [X]

with the generalized additive complexity at most 3. As all its ⌊\frac{n}{2}⌋ roots are negative reals, the additive complexity of f_{n} is at least Ω((log n)^{\frac{1}{2}} ) because of the result [G 83] (see also [Ri 85]) based on the method from [Kh 91].

5 Further Research

It remains an interesting open problem on improving the complexity bounds of our algorithm. It will be also very interesting to shed some more light on the status of the problem of computing standard additive complexity of rational functions. At this point we do not know much about this problem.

Acknowledgments

We are thankful to Richard Cleve for starting us up to think about the additive complexity of polynomials, and to Allan Borodin, Joachim von zur Gathen, Thomas Lickteig, Michael Singer, Volker Strassen, and Andy Yao for many interesting discussions.

References

[CG 83] Chistov, A., and Grigoriev, D., Subexponential-time solving systems of algebraic equations, LOMI Preprints E-9-83, E-10-83, Leningrad, 1983.

[G 82] Grigoriev, D., Additive complexity in directed computations, Theor. Comp. Sci., 19 1982, pp. 39-67.

[G 83] Grigoriev, D., Lower bounds in algebraic complexity, Transl. in J. Soviet Math. 29, 1985, pp. 1388-1425.

[G 89] Grigoriev, D., Complexity of quantifier elimination in the theory of differential equations, Lect. Notes Comput. Sci. 378, 1989, pp. 11-25.

[GK 91] Grigoriev, D., and Karpinski, M., Algorithms for Sparse Rational Interpolation, Proc. ACM ISSAC, 1991, pp. 7-13.

[GKS 90] Grigoriev, D., Karpinski, M., and Singer, M., Interpolation of Sparse Rational Functions without Knowing Bounds on Exponents, Proc. 31^{st} IEEE FOCS, 1990, pp. 840-846.

[GKS 92a] Grigoriev, D., Karpinski, M., and Singer, M., Computational complexity of sparse rational interpolation, to appear in SIAM J. Computing 1992.

[GKS 92b] Grigoriev, D., Karpinski, M., and Singer, M., Computational complexity of sparse real algebraic function interpolation, to appear in Proc. MEGA ’92, Nice, 1992 (Progr. in Math. Birkhäuser).

[GSY 93] Grigoriev, D., Singer, M., and Yao, A., On Computing Algebraic Functions using Logarithmus and Exponentials, DIMACS Technical Report 93-07; submitted to SIAM J. Computing.

[J 81] Ja’Ja’, J., Computations of algebraic functions with root extractios, Proc. 22^{nd} IEEE FOCS, 1981, pp. 95-100.

[KW 93] Karpinski, M., Werther, Th., VC Dimension and Uniform Learnability of Sparse Polynomials and Rational Functions, to appear in SIAM J. Computing 22(6), 1993.

[Kh 91] Khovanski, A., Fewnomials, AMS Transl. Math. Monogr. 88, 1991.

[P 81] Pippenger, N., Computational Complexity of Algebraic Functions, J. of Computer and System Sciences 22, 1981, pp. 454-470.

[Ri 85] Risler, J. J., Additive complexity and zeros of real polynomials, SIAM J. Comput. 14, 1985, pp. 178-183.

[Ro 76] Rosenlicht, M., On Liouville’s theory of elementary functions, Pacif. J. Math. 65, N 2, 1976, pp. 485-492.

[RC 79] Rothstein, M., and Caviness, B., A structure theorem for exponential and primitive functions, SIAM J. Comput. 8, N 3, 1979, pp. 357-366.

[Se 56] Seidenberg, A., An elimination theory for differential algebra, Univ. of Calif. Press 3, N 2, 1956, pp. 31-66.

[SW 80] Schnorr, C., and Wiele van de, J., On the additive complexity of polynomials, Theor. Comp. Sci. 10, 1980, pp. 1-18.