TIME–SPACE TRADEOFFS IN ALGEBRAIC COMPLEXITY THEORY

M. Aldaz, J. Heintz, G. Matera, J. L. Montaña & L. M. Pardo

Abstract. We exhibit a new method for showing lower bounds for time– space tradeoffs of polynomial evaluation procedures given by straight– line programs. From the tradeoff results obtained by this method we deduce lower space bounds for polynomial evaluation procedures running in optimal nonscalar time. Time, denoted by L, is measured in terms of nonscalar arithmetic operations and space, denoted by S, is measured by the maximal number of pebbles (registers) used during the given evaluation procedure. The time–space tradeoff function considered in this paper is LS^{2} . We show that for “almost all” univariate polynomials of degree at most d our time–space tradeoff functions satisfy the inequality: LS^{2} ≥ \frac{d}{8} . From this we conclude that for “almost all” degree d univariate polynomials, any nonscalar time optimal evaluation procedure requires space at least S ≥ c ^{4} \sqrt{d}, where c > 0 is a suitable universal constant. The main part of this paper is devoted to the exhibition of specific families of univariate polynomials which are “hard to compute” in the sense of time-space tradeoff (this means that our tradeoff function increases linearly in the degree).

Key words. Pebble game, time–space tradeoff, straight–line program, elimination theory. Subject classifications. 68Q40. 68Q25.

1. Introduction

Computer oriented algorithmics often requires simultaneos optimization of mo– re than one complexity measure. Although it is not easy to capture the programming reality in a theoretical model one feels compelled at least to attempt an effort in this direction. In this sense the present paper is devoted to the interplay between the (computational) issue of time and (necessary) space in the particular case of (numeric) evaluation of univariate polynomials. Our theoretical model is that of arithmetic circuits represented by directed acyclic graphs (DAGs) on which we play a pebble game (see the surveys Pippenger 1980, Savage 1981 and Borodin 1993). Thus arithmetic operations are counted at unit cost and an intermediate result of our computation, mathematically being represented by a rational function, occupies just one unit of memory space when it is stored. More specifically when measuring time we shall take only nonscalar multiplications/divisions into account, linear operations, in particular additions, are free. This coarsening of the computational model is due to technical reasons and acceptable since we are interested just in lower bounds for the tradeoff between computation time and memory space necessary to evaluate a given univariate polynomial. A particularity of our model is that any polynomial can be evaluated in constant memory space (as one easily sees when analyzing Horner’s rule, see also Ben-Or & Cleve 1992 and Michaux 1989 for more general results in this direction). However computation time cannot be compressed arbitrarily in polynomial evaluation, the logarithm of the degree being a universal lower bound. This motivates the study of time-space tradeoffs or alternatively the behaviour of memory space under the assumption of a time optimal algorithm. As said before our basic algorithmic model for time and space is that of a pebble game played on an arithmetic circuit represented by a DAG. There exists another model well suited for our purpose, which is not considered here, namely that of a branching program (see Borodin 1993). The reason for the omission of this model is that straight–line programs, although less relevant in computer science than branching programs, are better suited for the technical tools we are going to apply in this paper. These technical tools come mainly from geometric and arithmetic intersection theory (see e.g. Heintz 1983, Fulton 1984, Fitchas & Galligo 1990, Krick & Pardo 1996, Heintz & Morgenstern 1993, Pardo 1995 and the references cited therein). For a similar reason (uniformity assumptions do not help for our techniques) we do not consider modeling of time and space by Turing machines.

Straight–line programs have been used in the past extensively in order to show lower bounds for time-space tradeoffs of many problems of different computational nature and taste. Examples of such problems with significant results are: sorting (Tompa 1980), language recognition (Duris & Galil 1981), algebraic problems such as convolution, matrix–vector products and discrete Fourier transformation (Tompa 1980, Savage & Swamy 1978), binary integer multiplication (Savage & Swamy 1979), matrix multiplication and inversion, iterated matrix multiplication (Grigor’ev 1976, Ja’Ja’ 1983, Savage 1984), range queries (Yao 1980, Vaidya 1985). The general question, namely whether it is possible to find efficient tradeoffs between time and space while pebbling an arbitrary (not necessarily computation) DAG was considered an negatively answered in Lengauger & Tarjan (1979), Paul & Tarjan (1978), Pippenger (1978). The rather combinatorial branching program model is powerful enough to produce relevant lower bounds for time-space tradeoffs of algebraic problems. Results in this direction can be found in Yesha (1984) where lower bounds for the time-space tradeoff of the discrete Fourier transform in the branching program model are established and in Abrahamson (1991) where such lower bounds for a large list of computational problems are given. This problem list includes the task of computing the convolution of two vectors of numbers, computing a matrix-vector product, matrix multiplication, matrix inversion, computing the product of three matrices and integer multiplication. Lower bounds for time-space tradeoffs in the branching program model are known in the case of the following counting problems: sorting (see Borodin et al. 1981, and Borodin & Cook 1982), element distinctness (Borodin et al. 1987 and Yao 1988) and finding unique elements (Beame 1989).

In this paper we are concerned with the time–space complexity of evaluating univariate polynomials and the computation model we use is that of straight– line programs (or DAGs) together with pebble games played on them. Our method for obtaining lower bounds for time–space tradeoffs for polynomial evaluation is based on a geometrical interpretation of the notion of a straight– line program of given nonscalar time L and space S (see Section 2, Definitions 2.2, 2.3 and Lemmata 2.4, 2.5, 2.6). First of all let us observe that the computation DAG associated to Horner’s rule for the evaluation of an univariate polynomial P of degree d can be pebbled using exactly two pebbles in total time 2d and nonscalar time d. Let L and S denote nonscalar time and the space used by the Horner algorithm for the evaluation of the polynomial P . With this notation we obtain the following obvious time-space tradeoff upper bound for the evaluation of the polynomial P :

L · S^{2} = 4 · d.

Using a simple counting argument we show in Section 2 that this upper bound is, asymptotically, exact for almost all univariate degree d polynomials. In analogy with Strassen (1974), Heintz & Sieveking (1980), von zur Gathen & Strassen (1981) and Heintz (1989) we callsuch polynomials hard to compute in terms of tradeoff. In Section 3 we develop a global strategy which we shall follow in Section 4 to exhibit specific families of univariate polynomials which are hard to compute in the sense of time-space tradeoff. The new aspect of our strategy consists in a problem adapted analysis of the height of points lying on the fiber of a given 0 Q -definable algebraic morphism of affine spaces. The conclusions of this analysis constitute our main tool to establish time–space tradeoffs for univariate polynomials with integer coefficients (see Proposition 3.1). The case of polynomials with algebraic coefficients is treated using an adaptation of the degree method of Heintz & Sieveking (1980) (see also Heintz & Schnorr 1982, and Heintz & Morgenstern 1993). The following time-space tradeoff lower bounds are presented in Section 4:

(1) Polynomials with integer coefficients of the form ∑_{0≤j≤d} 2^{j!}X^{j} have a time-space tradeoff LS^{2} = Ω(d) .

(2) Polynomials with integer coefficients of the form ∏_{0≤j≤d}(X − 2^{2^{j}}) have a time space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}).

(3) Polynomials with algebraic coefficients of the form

∑_{1≤j≤d} \sqrt{p_{j}}X^{j−1},

have a time-space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}) . (Here p_{j} denotes the j –th prime number).

(4) Polynomials with algebraic coefficients of the form ∏_{1≤j≤d}(X−\sqrt{p_{j}}) have a time-space tradeoff LS^{2} = Ω(\frac{d}{log_{2} d}) .

In all these examples L denotes the number of nonscalar mutiplications/divi– sions and S the number of pebbles (registers) used when evaluating the polynomial under consideration by a given straight–line program. Our time-space tradeoff results imply that any nonscalar time optimal algorithm which evaluates any of the mentioned polynomial families needs at least space S = Ω( ^{4} \sqrt{d}) (see Proposition 4.12). Finally let us observe that to our knowledge our method is the first one which is able to produce time-space tradeoff lower bounds for algebraic computation problems with just one output.

2. Time and Space for Arithmetic Circuits

In this section we discuss how the complexity measures time and space can be suitably represented in our basic model of computation, namely the random access model of straight–line programs (also called arithmetic circuits). Intuitively one would say that computational time and space of a straight–line program find a natural representation playing a pebble game on the underlying computation graph (see e.g. Borodin 1993). However this combinatorial definition of our complexity measures is not well suited for the application of geometric methods to proofs of lower complexity bounds –the main subject of this paper. For this reason we are going to transform the pebble game complexity model first in a register allocation model and then the register allocation model in a geometric model of computation.

2.1. From the Pebble Game Complexity Model to the Register Allocation Model. Let K be an infinite field and let X_{1}, …, X_{n} be indeterminates over K. By K[X_{1}, …, X_{n}] we denote the ring of n –variate polynomials over K and by K(X_{1}, …, X_{n}) its fraction field. Let F be an element of K(X_{1}, …, X_{n}) , i.e. a rational function over the field K in the variables X_{1}, …, X_{n}. Let us recall the following standard notions of algebraic complexity theory (see Borodin & Munro 1975, Strassen 1990, Stoss 1989a, Heintz 1989, von zur Gathen 1993, von zur Gathen 1993, Pardo 1995, Bürgisser et al. 1996).

Definition 2.1. A straight–line program in K(X_{1}, …, X_{n}) which computes the rational function F is a sequence β = (Q_{1}, …, Q_{r}) of elements of the field K(X_{1}, …, X_{n}) with the following properties 1. Q_{r} = F ,

2. for any 1 ≤ ρ ≤ r, the rational function Q_{ρ} belongs to K ∪{X_{1}, …, X_{n}} or there exist 1 ≤ ρ_{1}, ρ_{2} < ρ and an arithmetic operation op_{ρ} in {+, −, ∗, /} such that Q_{ρ} = Q_{ρ_{1}} op_{ρ} Q_{ρ_{2}} holds.

The rational functions Q_{1}, …, Q_{r} are called intermediate results of the straight– line program β and the rational function F = Q_{r} is called final result or output of β. In the sequel we shall assume without loss of generality that all intemediate results Q_{1}, …, Q_{r} of β are non–zero. To a given straight–line program β = (Q_{1}, …, Q_{r}) in K(X_{1}, …, X_{n}) we associate as usually a labeled directed acyclic graph (computation DAG for short) which we denote by Γ(β) and which we call the computation graph of the straight–line program β. The computation graph Γ(β) has r vertices called nodes (or gates). Each node of Γ(β) has indegree 0 or 2 and is labeled by an element of K ∪ {X_{1}, …, X_{n}} in the first case and by an arithmetic operation in the latter case. Nodes of indegree 0 are called source nodes of Γ(β) . Source nodes labeled by a variable X_{1}, …, X_{n} are called input nodes and source nodes labeled by an element of K are called parameter nodes. The elements of K occuring in that way are called parameters of the computation graph Γ(β) (or of the straight–line program β). The nodes of Γ(β) are numbered by 1 ≤ ρ ≤ r. If for a node ρ of Γ(β) there exist nodes 1 ≤ ρ_{1}, ρ_{2} < ρ and an arithmetic operation op_{ρ} such that Q_{ρ} = Q_{ρ_{1}} op_{ρ} Q_{ρ_{2}} holds, then the node ρ is labeled by op_{ρ}, its indegree is 2 and Γ(β) contains directed edges leading from the vertices ρ_{1} and ρ_{2} to the vertex ρ (the nodes ρ_{1} and ρ_{2} are called predecessor nodes of ρ). The nodes which are not source nodes are called internal nodes of Γ(β) . The node r is called output node of the computation graph Γ(β) . To each node ρ of Γ(β) we associate the rational function Q_{ρ} appearing in the sequence β as intermediate result. This rational function is recursively computed by the graph Γ(β) starting with the source nodes. In particular the rational function which corresponds to the output node r is Q_{r} = F . We call a node ρ of Γ(β) nonscalar if it has the following property: the node ρ has indegree 2, the arithmetic operation op_{ρ} is a multiplication or division and the intermediate results Q_{ρ_{1}}, Q_{ρ_{2}} of β associated to the predecessors nodes ρ_{1}, ρ_{2} of ρ satisfy the condition Q_{ρ_{1}}, Q_{ρ_{2}} ∉ K if op_{ρ} is a multiplication and the condition Q_{ρ_{2}} ∉ K if op_{ρ} is a division. On the directed acyclic graph Γ(β) we may play a pebble game subject to the following rules (see Borodin 1993):

P1 any source node can be pebbled,

P2 if the predecessor nodes of a given node ρ of Γ(β) are both pebbled, then ρ can be pebbled by a new pebble or just by moving a pebble from one of the predecessor nodes to ρ,

P3 a pebble can always be removed from a pebbled node of Γ(β) .

The pebble game finishes when the output node of Γ(β) is pebbled. In general various distinct pebble games can be played on a given computation graph Γ(β) . That means that the computation graph Γ(β) typically does not admit just one pebble game, or with other words: pebble games are not uniquely determined by the underlying DAG. For a particular pebble game on a given computation graph Γ(β) we have the following complexity measures:

C1 a space measure given by the maximum number of pebbles used at any moment of the game,

C2 a total time measure given by the number of pebble placements performed during the game following rules P1 and P2,

C3 a nonscalar time measure given by the number of pebble placements on the nonscalar nodes of Γ(β) performed during the game following the rule P2.

We extend our notion of straight–line program as follows: from now on we shall understand by a straight–line program an arithmetic circuit β in the sense of Definition 2.1 together with a fixed pebble game played on its computation graph Γ(β) . We use the same notation, namely β, for the new mathematical object: the straight–line program together with a fixed pebble game. We introduce the following combinatorial complexity model which reflects sequential time and space in our arithmetic setting:

Definition 2.2. Let F ∈ K(X_{1}, …, X_{n}) be a rational function. A straight– line program in the field of rational functions K(X_{1}, …, X_{n}) which evaluates F using total time T , nonscalar time L and space S is a straight–line program β for F in the sense of Definition 2.1 together with a pebble game played on Γ(β) in total time T , nonscalar time L and space S, where these complexity measures are determined following the conditions C2, C3 and C1.

In this way we obtain a purely combinatorial complexity model measuring total and nonscalar time and space playing a pebble game on a computation DAG. Next, we are going to construct a register allocation model for our general purpose of deriving lower bounds on time–space tradeoffs for polynomial evaluation. Suppose that there is given a straight–line program β as above together with its computation graph Γ(β) . Suppose furthermore that there is given a pebble game on Γ(β) which uses S pebbles say 1, …, S and which can be played in total time T on the graph Γ(β) . In what follows we think the pebble game given as a time sequence of T register allocation instructions in which the new variables R_{1}, …, R_{S} appear as names of registers. The register allocation instructions are labeled by the symbols (1), …, (T) . We introduce them as follows:

1. If at time 1 ≤ t ≤ T of the game a source node ρ of Γ(β) is pebbled following the rule P1 by pebble 1 ≤ j ≤ S then the instruction (t) has the form

“R_{j} := X_{i}”

in case that node ρ is labeled by the input variable X_{i}. In case that node ρ is labeled by the parameter α ∈ K the register allocation instruction (t) has the form

“R_{j} := α”.

2. If at time 1 ≤ t ≤ T of the game the internal node ρ of Γ(β) is pebbled following rule P2 by pebble 1 ≤ j ≤ S, then the register allocation instruction (t) has the form

“R_{j} := R_{k} op_{ρ} R_{l}”

where op_{ρ} is the arithmetic operation associated with the node ρ and 1 ≤ k, l ≤ S are the pebbles already placed on the predecessor nodes ρ_{1} , ρ_{2} of ρ.

According to the register allocation rules just introduced we may redefine the notion of a straight–line program of total time T (resp. nonscalar time L) and space S in the following way:

Definition 2.3. A straight–line program β in K(X_{1}, …, X_{n}) using total time T and space S is a sequence of register allocation instructions labeled (1), …, (T) such that for each 1 ≤ t ≤ T instruction (t) is one of the following two types:

(i) “R_{j} := a” with a ∈ K ∪ {X_{1}, …, X_{n}} and 1 ≤ j ≤ S,

(ii) “R_{j} := R_{k} op R_{l}” with op ∈ {+, −, ∗, /} and 1 ≤ k, l < j ≤ S.

Here R_{1}, …, R_{S} are the (distinct) register variables the straight–line program β uses.

The total time used by the straight–line program β is therefore the number T of register allocation instructions it contains. The nonscalar time used by β (or its nonscalar length) is the number of register allocation instructions of the form (ii) occuring in β which are subject to the following restrictions: the arithmetic operation op is a multiplication or division, the contents of the registers R_{k}, R_{l} –to be introduced below– do not belong to the parameter domain K in case op is a multiplication and the content of the register R_{l} does not belong to K if op is a division. In the sequel we shall write L( β) for the nonscalar time and S( β) for the space used by the straight–line program β. Given a straight–line program β in the sense of Definition 2.3 one may define in the most obvious way for any time instance 1 ≤ t ≤ T and any register R_{j} with 1 ≤ j ≤ S its content R_{j}^{t} as a rational function of K(X_{1}, …, X_{n}) obtained applying step by step the register allocation instructions (1), …, (T) . In case that register j remains unspecified in this way at time t we define its content as the constant value 1 of the field K. Thus at any time any register content is the constant value 1 ∈ K or a rational function of K(X_{1}, …, X_{n}) which appears as intermediate result of the underlying arithmetic circuit β in the sense of Definition 2.1. We call (R_{j}^{t})_{1≤j≤S,1≤t≤T} the computation matrix of the straight–line program β.

2.2. From the Register Allocation Model to the Geometric Complexity Model. In this subsection we introduce a geometric model of polynomial evaluation which reflects computational time and space when arithmetic operations are counted at unit cost. This model is somewhat coarse with regard to upper complexity bounds but it is well suited for the inference of lower bounds for the intrinsic time–space tradeoff function of a series of explicit polynomials which –we guess– are studied for the first time under the aspect of time versus space. Our method to obtain lower bounds on time–space tradeoffs for polynomial evaluation is based on a geometrical interpretation of the notion of a straight– line program which uses nonscalar time and space not exceeding some prefixed quantities L and S respectively. In the sequel we restricted ourselves to the case n := 1 . This means that we are only dealing with univariate polynomials and rational functions defined over the field K. We denote by X := X_{1} the only variable of the polynomials and rational functions occuring as intermediate results in the straight–line programs we are considering from now on. First of all let us observe that the computation graph associated with Horner’s rule for a univariate degree d polynomial F ∈ K[X] can be pebbled in total time 2d and nonscalar time d using exactly two pebbles. Let L and S denote nonscalar time and space used by the Horner algorithm which evaluates the polynomial F . Then L and S satisfy the tradeoff relation LS^{2} = 4d. This consideration leads us to the following question: given any polynomial F ∈ K[X] of degree at most d, do there exist straight–line programs β in K(X) using nonscalar time L(β) and space S(β) such that the time–space tradeoff LS^{2}(β) := L(β)S^{2}(β) is considerably smaller than d? Using a simple counting argument we shall find that the answer to this question is negative. This means that there exists a universal constant c > 0 such that (in some precise sense) almost all polynomials of F ∈ K[X] of degree bounded by d have the property that any straight–line program β in K(X) evaluating F has a time–space tradeoff LS^{2}(ēta) satisfying the inequality

LS^{2}(β) ≥ cd

(see Theorem 2.7 below). In the sequel we shall abreviate such a statement as

LS^{2}(F) = Ω(d).

Similarly as in Strassen (1974) and Heintz (1989) we say that a family of univariate degree d polynomials (F_{d})_{d∈IN} is hard to compute in terms of time-space tradeoff if there exists a constant c′ > 0 such that any family of arithmetic circuits (β_{d})_{d∈IN} in K[X] with β_{d} evaluating the polynomial F_{d} satisfies the following time–space tradeoff inequality

LS^{2}(β_{d}) ≥ d^{c′}.

In the sequel we shall abreviate such a statement as

LS^{2}(F_{d}) = d^{Ω(1)}.

The geometrical method we are going to develop will allow us to exhibit specific families of univariate polynomials which are hard to compute in this sense. Let L and S be fixed natural numbers and let us suppose that we are given a straight–line program β which computes the rational function F ∈ K(X) in nonscalar time L(β) ≤ L and space S(β) ≤ S.

In order to homogenize notations let start the computation formally at time zero fixing for 1 ≤ j ≤ S the content R_{j}^{0} of each register R_{j} as R_{j}^{0} := 0 . Besides of space we shall take into account only nonscalar time as complexity measure. Non–scalar time will be indicated by the new parameter l which ranges from 1 to L. Moreover, we shall use two extra registers R_{−1} and R_{0} whose contents at any time instance 0 ≤ l ≤ L are fixed as R_{−1}^{l} := 1 and R_{0}^{l} := X. Since in the nonscalar model K –linear operations are free and since we take in the straight–line program β only nonscalar operations into account, we may describe β by a recursive sequence of register allocation instructions (I_{j}^{l}) of the following type: for 1 ≤ j ≤ S and 1 ≤ l ≤ L the instruction (I_{j}^{l}) has the form

R_{j}^{l} := ( ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1}) op ( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1}) ,

where op is a multiplication or division and where the a_{k}^{(j,l)} and b_{k}^{(j,l)} are suitable elements of K. The output F of β is given by a final register allocation instruction (I) , namely

F := ∑_{−1≤k≤S} c_{k}R_{k}^{L}

with the c_{k} being suitable elements of K. The elements a_{k}^{(j,l)} , b_{k}^{(j,l)} , c_{k} of K occuring in these register allocation instructions are called the parameters of the straight–line program β. Moreover, the intermediate results of β are given by the computation matrix

M(β) := (R_{j}^{l})_{−1≤j≤S,0≤l≤L}.

The circuit β itself is determined by its parameters and the indication which arithmetic operation, multiplication or division, is applied in each register allocation instruction (I_{j}^{l}) . We observe here that the register allocation instructions (I_{j}^{l}) do not exactly reflect a pebble game on the computation graph Γ(β) since in our modeling all registers are assumed to change their contents simultaneously. Nevertheless, in a pebble game at any time instance only one register is affected and not all of them simultaneously. Therefore, the modeling of a computation in K(X) using given nonscalar time L and space S by register allocation rules of type (I_{j}^{l}) and of type (I) with 1 ≤ j ≤ S and 1 ≤ l ≤ L is somewhat coarser than the modeling given by Definition 2.2 and 2.3. This means that in this way there may appear rational functions as “outputs of the computations” which cannot be evaluated by a straight–line program which uses only nonscalar time L and space S. Since our final aim is to prove lower bounds for the tradeoff between nonscalar time and space required to compute certain univariate polynomials, this coarsening of the complexity model will not affect the correctness of our results which we shall state in the sense of Definitions 2.2 and 2.3.

Let us also remark that the complexity model we have selected is somewhat arbitrary even within its own category. A moment’s reflection shows that at least two alternative complexity models of the same type are thinkable. The first alternative model includes some parallelism admitting S simultaneous nonscalar multiplications/divisions at each step. Altough this alternative complexity model is at first glance more general than the one we have chosen for our presentation, the time-space tradeoff lower bounds we are going to prove in this paper remain the same for this alternative model.

The second alternative model is more restrictive than ours, It allows only the change of just one register at each step and requires that this step represents a nonscalar multiplication/division. This second alternative complexity model produces slightly different time-space tradeoff lower bounds from those we are going to show (although the proving methods would be essentially the same). Whereas the time-space tradeoff function we are going to consider in this paper is always of the type LS^{2} , this second alternative complexity model yields a tradeoff function of type LS. It is surely a question of taste or personal preference, but in view of our proving methods the complexity model we have selected for this paper appears the most natural to us.

Let the quantities L and S be fixed. Let us think the parameters a_{k}^{(j,l)} , b_{k}^{(j,l)} , c_{k} occuring for −1 ≤ k ≤ S, 1 ≤ j ≤ S and 1 ≤ l ≤ L in the register allocation instructions (I_{j}^{l}) and (I) as variying, i.e. let us replace these parameters by new indeterminates. Then the entries of the computation matrix M(β) and the rational function F representing intermediate results and output of the straight–line program β become rational expressions in the the parameters of the circuit β (and of course in the variable X). In this way the straight–line program β becomes a generic computation scheme of nonscalar time L and space S which is uniquely determined by the quantities L and S and the choice of the arithmetic operation (multiplication or division) done for each 1 ≤ j ≤ S and 1 ≤ l ≤ L in the register allocation instruction (I_{j}^{l}) . We are going to simplify somewhat further our computation scheme of nonscalar time L and space S. For this purpose we introduce for each 1 ≤ j ≤ S and 1 ≤ l ≤ L a new parameter d^{(j,l)} which will be interpreted as follows: the value to be assigned to the parameter d^{(j,l)} is 1 if the arithmetic operation occuring in the instruction (I_{j}^{l}) as op is a multiplication and the value is 0 if this arithmetic operation is a division. Now we replace for each 1 ≤ j ≤ S, 1 ≤ l ≤ L the register allocation instruction (I_{j}^{l}) by the following new one which we denote by (J_{j}^{l}) :

R_{j}^{l} = ( ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1}) · (d^{(j,l)} ( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1}) +

+ (1 − d^{(j,l)}) ( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1})^{−1}) .

(Let us observe that taking in the register allocation instruction (J_{j}^{l}) the inverse of the subexpression ∑_{−1≤k≤S} b_{k}^{j,l}R_{k}^{l−1} is consistent with our general assumption that the computations we consider do not contain the rational function zero as intermediate result.) Again we represent each parameter d^{(j,l)} by a new indeterminate. In this way we obtain a new generic computation scheme wich depends only on the nonscalar time L and the space S. The parameters of this new computation scheme are a_{k}^{(j,l)} , b_{k}^{(j,l)} , d^{(j,l)} and c_{k} with −1 ≤ k ≤ S, 1 ≤ j ≤ S and 1 ≤ l ≤ L. Let us analyze how the output F depends on these parameters if F is a polynomial belonging to K[X] . To this end we use an idea going back to Strassen (1974) (see also Schnorr 1978). In order to state the following technical result we recall that the weight of a polynomial with integer coefficients is the sum of the absolute values of these coefficients.

Lemma 2.4. Let d, L, S be given natural numbers, let N := 8LS^{2} and let Z_{1}, …, Z_{N} be new indeterminates. There exist polynomials P_{d}, …, P_{0} ∈ ZZ[Z_{1}, …, Z_{N}] of degree and weight bounded by

2(Ld + 1)

and

(4(S + 1))^{(d+1)^{L+1}}

respectively, such that the morphism of affine spaces

Φ_{d,L,S} : K^{N} → K^{d+1}

defined by these polynomials has the following property: for any polynomial F ∈ K[X] of degree at most d which can be computed by a straight–line program in K(X) using at most nonscalar time L and space S, there exists a (nonempty) cofinite subset U_{F} of K such that for any element η ∈ U_{F} the point (f_{d}(η), …, f_{0}(η)) ∈ K^{d+1} given by the representation

F = ∑_{0≤i≤d} f_{i}(η)(X − η)^{i}

belongs to the image of the morphism Φ_{d,L,S}.

Proof. Let β be an arbitrary straight–line program in K(X) which computes a given polynomial F ∈ K[X] of degree at most d using nonscalar time L and space S. We suppose that β is given as before by a sequence of register allocation instructions (J_{j}^{l}) with 1 ≤ j ≤ S and 1 ≤ l ≤ L and a final instruction (I) . Thus the intermediate results of β are rational functions R_{k}^{l} ∈ K(X) with −1 ≤ k ≤ S and 0 ≤ l ≤ L which satisfy the following recursive relations:

∘ R_{−1}^{l} = 1 for any 0 ≤ l ≤ L,

∘ R_{0}^{l} = X for any 0 ≤ l ≤ L,

∘ R_{j}^{0} = 0 for any 1 ≤ j ≤ S,

and

∘ R_{j}^{l} = ( ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1}) · (d^{(j,l)} ( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1}) +

+ (1 − d^{(j,l)}) ( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1})^{−1}) (2.1)

for any 1 ≤ j ≤ S and any 1 ≤ l ≤ L. Finally the output polynomial F ∈ K[X] is representable as

F = ∑_{−1≤k≤S} c_{k}R_{k}^{L}.  (2.2)

Here a_{k}^{(j,l)} , b_{k}^{(j,l)} , d^{(j,l)} , c_{k} are suitable elements of K with −1 ≤ k ≤ S, 1 ≤ j ≤ S and 1 ≤ l ≤ L, namely the parameters of the straight–line program β. Each of the rational functions ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1} and ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1} occuring as subexpressions in Equation (2.1) are defined and different from zero in all points of some cofinite subset U_{F} of K. Since by assumption K is infinite the set U_{F} is nonempty. Let η an arbitrary point of U_{F} and let 1 ≤ j ≤ S and 1 ≤ l ≤ L. Then the rational functions R_{−1}^{l−1}, …, R_{S}^{l−1} , ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1} and ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1} are defined and different from zero in η. By a suitable change of the parameters a_{j}^{(j,l)}, b_{j}^{(j,l)} and c_{k} in Equations (2.1) and (2.2) we may assume without loss of generality that ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1}(η) = 1 and ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1}(η) = 1 holds. The parameter d^{(j,l)} takes by assumption only the values 0 or 1 . This implies that the rational function R_{j}^{l} is defined in η and that R_{j}^{l}(η) = 1 holds. This enables us to represent R_{j}^{l} as a formal power series in X − η with coefficients in K. More precisely we may write the rational function R_{j}^{l} uniquely as power series

R_{j}^{l} = 1 + ∑_{i≥1} R_{j,i}^{l}(X − η)^{i}

with coefficients R_{j,i}^{l} belonging to the field K. Observe that R_{0}^{l} = X has also a power series representation of theform R_{0}^{l} = η+(X −η) = η+∑_{i≤1} R_{0,i}^{l}(X −η)^{i} with R_{0,1}^{l} = 1 and R_{0,i}^{l} = 0 for i > 1 . From our assumptions we deduce

∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k}^{l−1} = ∑_{−1≤k≤S} a_{k}^{(j,l)}R_{k,i}^{l−1}(η) + ∑_{0≤k≤S} a_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i} =
= 1 + ∑_{0≤k≤S} a_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i}  (2.3)

and similarly

∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1} = 1 + ∑_{0≤k≤S} b_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i}.  (2.4)

Equation (2.4) implies

( ∑_{−1≤k≤S} b_{k}^{(j,l)}R_{k}^{l−1})^{−1} = 1 + ∑_{v≥1} (− ∑_{0≤k≤S} b_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i})^{v} .

This enables us to express Equation (2.1) in terms of power series. For 1 ≤ j ≤ S and 1 ≤ l ≤ L we have

1 + ∑_{i≥1} R_{j,i}^{l}(X − η)^{i} =

= (1 + ∑_{0≤k≤S} a_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i})·

·(d^{(j,l)}(1 + ∑_{0≤k≤S} b_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i}) +

+ (1 − d^{(j,l)})(1 + ∑_{v≥1}(− ∑_{0≤k≤S} b_{k}^{(j,l)} ∑_{i≥1} R_{k,i}^{l−1}(X − η)^{i})^{v})). (2.5)

From Equation (2.5) we deduce inductively that the coefficients R_{j,i}^{l} are polynomial expressions which integer coefficients in the parameters a_{k}^{(j′,l′)} , b_{k}^{(j′,l′)} , d^{(j′,l′)} of the straight–line program β where the range of k, j′ and l′ is 0 ≤ k ≤ S, 1 ≤ j′ ≤ S and 1 ≤ l′ ≤ l. These polynomial expressions depend only on L and S and are independent of the particular choice of η and of the particular straight–line program β. Since no ambiguity may appear, we shall denote such a polynomial expression by the same symbol as the power series coefficient that it represents, namely R_{j,i}^{l}. Comparing coefficients in Equation (2.5) we see that each coefficient R_{j,i}^{l} is up to sign a sum of monomial expressions of one of the following two types:

(d^{(j,l)})^{ϵ} ∏_{1≤v≤μ} b_{k_{v}}^{(j,l)}R_{k_{v},i_{v}}^{l−1}  (2.6)

or

a_{k_{μ}}^{(j,l)}R_{k_{μ},i_{μ}}^{l−1}(d^{(j,l)})^{ϵ} ∏_{1≤v<μ} b_{k_{v}}^{(j,l)}R_{k_{v},i_{v}}^{l−1}  (2.7)

with ∑_{1≤v≤μ} i_{v} = i, 1 ≤ i_{v} ≤ i, 1 ≤ μ ≤ i, 0 ≤ k_{v} ≤ S and ϵ ∈ {0, 1}. From this observation we deduce the following recursive degree bound:

deg R_{j,i}^{l} ≤ max {μ + 1 + ∑_{1≤v≤μ} deg R_{k_{v},i_{v}}^{l−1} :

: ∑_{1≤v≤μ} i_{v} = i, 1 ≤ i_{v} ≤ i, 1 ≤ μ ≤ i, 0 ≤ k_{v} ≤ S} . (2.8)

From our construction one deduces immediatly that for any 0 ≤ k ≤ S and any i ≥ 1 the estimate

deg R_{k,i}^{0} ≤ 0  (2.9)

holds. Solving the recurrence relations (2.8) taking into account the initial conditions (2.9) yields

deg R_{j,i}^{l} ≤ i(2l − 1) + 1  (2.10)

for any 1 ≤ j ≤ S, 1 ≤ l ≤ L and i ≥ 1 . We are going to estimate the weight

of the polynomials R_{j,i}^{l}. To this aim observe that the number of monomial expressions (2.6) and (2.7) appearing in R_{j,i}^{l} does not exceed 2^{i+1}(S + 1)^{i}. From this remark we deduce the following recursive weight bound:

weight R_{j,i}^{l} ≤ 2^{i+1}(S + 1)^{i} max { ∏_{1≤v≤μ} weight R_{k_{v},i_{v}}^{l−1} :

: ∑_{1≤v≤μ} i_{v} = i, 1 ≤ i_{v} ≤ i, 1 ≤ μ ≤ i, 0 ≤ k_{v} ≤ S} .  (2.11)

By direct inspection one verifies easily that for any 1 ≤ l ≤ L and any 0 ≤ k ≤ S the estimate

weight R_{k,1}^{l} ≤ 4^{l}(S + 1)^{l}  (2.12)

holds. Solving the recurrence relations (2.11) taking into account the initial conditions (2.12) yields

weight R_{j,i}^{l} ≤ 2^{(i+1)((i+1)^{l}−1)}(S + 1)^{i(i+1)^{l}−1)}.  (2.13)

The coefficients R_{j,i}^{l} of the power series occuring in Equation (2.5) are polynomial expressions over the integers in the 2LS^{2} + 3LS parameters a_{k}^{(j,l)} , b_{k}^{(j,l)} , d^{(j,l)} with 0 ≤ k ≤ S, 1 ≤ j ≤ S and 1 ≤ l ≤ L. Thus we shall consider them as (2LS^{2} + 3LS) –variate polynomials over the integers. The polynomial F ∈ K[X] is of degree at most d and has therefore a finite Taylor series expansion in (X − η) , say

F = ∑_{0≤i≤d} f_{i}(η)(X − η)^{i}

with coefficients f_{i}(η) belonging to the field K.

From Equation (2.2) we deduce

F = ∑_{0≤i≤d} f_{i}(η)(X − η)^{i} = ∑_{−1≤k≤S} c_{k}R_{k}^{L} =

= (c_{−1} + c_{0}η + ∑_{1≤k≤S} c_{k}) + ∑_{0≤k≤S} c_{k} (∑_{i≥1} R_{k,i}^{L}(X − η)^{i}) =

= (c_{−1} + c_{0}η + ∑_{1≤k≤S} c_{k}) + ∑_{i≥1} ( ∑_{0≤k≤S} c_{k}R_{k,i}^{L}) (X − η)^{i}.

This implies

f_{i}(η) = ∑_{0≤k≤S} c_{k}R_{k,i}^{L}  (2.14)

for 1 ≤ i ≤ d and

f_{0}(η) = c_{−1} + c_{0}η + ∑_{1≤k≤S} c_{k}  (2.15)

for i = 0 . Observe that Equation (2.14) is independent of the parameter c_{−1} . This allows us to consider c_{−1} +c_{0}η just as a new parameter c from which the straight–line program β depends and which replaces the old parameter c_{−1} . In this sense we can rewrite Equation (2.15) as

f_{0}(η) = c + ∑_{1≤k≤S} c_{k}.  (2.16)

The right hand side of Equations (2.14) and (2.16) are polynomial expressions in the 2LS^{2} + 3LS + S + 2 ≤ 8LS^{2} parameters c, c_{k}, a_{k}^{(j,l)} , b_{k}^{(j,l)} , d^{(j,l)} with 0 ≤ k ≤ S, 1 ≤ j ≤ S and 1 ≤ l ≤ L. These polynomial expressions depend only on L and S and they are independent of the choice of the point η ∈ U_{F} . Let N := 8LS^{2} and let Z_{1}, …, Z_{N} be new indeterminates. From Equations (2.10), (2.13), (2.14) and (2.16) we deduce that there exist polynomials P_{0}, …, P_{d} ∈ ZZ[Z_{1}, …, Z_{N}] such that for any 0 ≤ i ≤ d degree and weight of P_{i} can be estimated by

deg P_{i} ≤ i(2L − 1) + 2 ≤ 2(Ld + 1)

and

weight P_{i} ≤ (4(S + 1))^{(d+1)^{L+1}}

and such that the following holds: for any polynomial F ∈ K[X] of degree at most d which can be evaluated by a straight–line program using at most nonscalar time L and space S there exists a (nonempty) cofinite set U_{F} in K such that for any value η ∈ U_{F} there is a point z ∈ K^{N} with

F = ∑_{0≤i≤d} f_{i}(η)(X − η)^{i} = ∑_{0≤i≤d} P_{i}(z)(X − η)^{i}.

Let now

Φ_{d,L,S} : K^{N} ⟶ K^{d+1}

be the morphism of affine spaces defined by Φ_{d,L,S}(z) := (P_{d}(z), …, P_{0}(z)) for arbitrary z ∈ K^{N}. This morphism has all the properties announced in the statement of Lemma 2.4. □

In our applications we shall need a more comprehensive formulation of Lemma 2.4 in which the generic value η and the cofinite set U_{F} it belongs to do not appear anymore explicitely. Such a formulation can easily be obtained by including the generic value η in the list of parameters of the hypothetical straight–line program β analyzed in the proof of Lemma 2.4. From this observation we deduce our next result.

Lemma 2.5. Let d, L, S be given natural numbers, let N := 8LS^{2} + 1 and let Z_{1} …, Z_{N} be new indeterminates. There exist polynomials P_{d}, …, P_{0} ∈ ZZ[Z_{1}, …, Z_{N}] of degree and weight bounded by

2(Ld + 1)

and

(d + 1)!(4(S + 1))^{(d+1)^{L+1}}

respectively such that the morphism of affine spaces

Φ_{d,L,S} : K^{N} ⟶ K^{d+1}

defined by these polynomials has the following property: for any polynomial F ∈ K[X] of degree at most d which can be computed by a straight–line program using at most nonscalar time L and space S, the point (f_{d}, …, f_{0}) ∈ K^{d+1} given by the representation F = ∑_{0≤i≤d} f_{i}X^{i} belongs to the image of Φ_{d,L,S}.

In the sequel we shall identify any polynomial F = ∑_{0≤i≤d} f_{i}X^{i} ∈ K[X] of degree at most d with its coefficient vector (f_{d}, …, f_{0}) which we consider as a point of the affine space K^{d+1} . In this sense a statement like “F ∈ K^{d+1}” should be understood as “(f_{d}, …, f_{0}) ∈ K^{d+1}” . From Lemma 2.4 we deduce the following geometric consequences which represents our main tool in deriving lower bounds for the intrisic time–space tradeoff of univariate polynomials (compare with Heintz & Sieveking 1980).

Lemma 2.6. Let d, L, S be given natural numbers. There exists a Zariski closed, irreducible and 0 Q –definable subset W_{d,L,S} of K^{d+1} such that the following conditions are satisfied:

(i) dim W_{d,L,S} ≤ 8LS^{2} .

(ii) deg W_{d,L,S} ≤ (2(Ld + 1))^{8LS^{2}} .

(iii) The coefficient vector of any polynomial F ∈ K[X] of degree at most d which can be evaluated by a straight–line program in K(X) using at most nonscalar time L and space S belongs to the algebraic variety W_{d,L,S}.

Proof. Let W := W_{d,L,S} be the Zariski–closure in K^{d+1} of the image of the morphism Φ := Φ_{d,L,S} of Lemma 2.4. One sees immediately that W is a Zariski closed irreducible subset of the affine space K^{d+1} . This subset is also 0 Q –definable since the morphism Φ is given by the polynomials P_{d}, …, P_{0} which have integer coefficients. For the rest of the proof let us interprete Φ as a morphism of affine varieties which maps K^{N} into W . In this interpretation Φ is dominant. This implies dim W ≤ N = 8LS^{2} . Therefore the algebraic variety W = W_{d,L,S} satisfies condition (i). Let us verify condition (ii). Let r := dim W . Since the morphism Φ is dominant there exists a nonempty, Zariski open subset of W which is contained in im Φ , the image of Φ . Therefore we may deduce from Heintz (1983) that there exist r affine hyperplanes H_{1}, …, H_{r} of K^{d+1} which intersect im Φ in deg W many points. Let M = H_{1} ∩ … ∩ H_{r} ∩ im Φ . By assumption we have #M = deg W . From Lemma 2.4 one deduces inmediately that Φ^{−1}(H_{1}), …, Φ^{−1}(H_{r}) are hypersurfaces of K^{N} of degree at most 2(Ld + 1) . Let

C := {C : C is an irreducible component of Φ^{−1}(H_{1}) ∩ … ∩ Φ^{−1}(H_{r})}.

By the Bézout Inequality (see Heintz 1983, or Fulton 1984) we have

# C ≤ ∑_{C∈C} deg C ≤ (2(Ld + 1))^{r} ≤ (2(Ld + 1))^{8LS^{2}},

where deg C denotes the (geometric) degree of the irreducible closed subset C of K^{N}. For any C ∈ C the Zariski closure of the image Φ(C) is an irreducible subset of K^{d+1} contained in M, hence a point of M. Since the set M is contained in im Φ we conclude

deg W_{d,L,S} = deg W = #M ≤ #C ≤ (2(Ld + 1))^{8LS^{2}}.

Finally we are going to verify condition (iii). Let F = ∑_{0≤i≤d} f_{i}X^{i} ∈ K[X] be a polynomial of degree at most d which can be evaluated by a straight–line program in K(X) using at most nonscalar time L and space S. For any η ∈ K let F = ∑_{0≤i≤d} f_{i}(η)(X − η)^{i} be the Taylor expansion of F in X − η. The vector (f_{d}(η), …, f_{0}(η)) depends in a polynomial way on the parameter η. Let U := U_{F} be the nonempty, cofinite subset introduced in Lemma 2.4. For any η ∈ U we have

(f_{d}(η), …, f_{0}(η)) ∈ im Φ_{d,L,S} = im Φ ⊂ W,

by this Lemma. Since U is infinite and W is Zariski closed in K^{d+1} we conclude that (f_{d}, …, f_{0}) = (f_{d}(0), …, f_{0}(0)) belongs to the algebraic variety W = W_{d,L,S}. □

From Lemma 2.6 we deduce now our first complexity result. This result characterizes the intrinsic time–space tradeoff complexity of “almost all” univariate polynomials of degree at most d generalizing thus the main outcome of Paterson & Stockmeyer (1973) and showing that Horner’s rule is assymptotically optimal in terms of time–space tradeoffs.

Theorem 2.7. Let d be a given natural number. There exists a nonempty Zariski open subset U of K^{d+1} such that for any polynomial F ∈ K[X] of degree at most d with F ∈ U the tradeoff estimate LS^{2}(F) ≥ \frac{d}{8} holds.

Proof. Let d be fixed. For any positive rational number t ≤ d we consider the Zariski closed subset W_{d,t} of K^{d+1} defined by

W_{d,t} := ⋃_{L,S∈IN, LS^{2}≤t} W_{d,L,S}.

From Lemma 2.6 (i) we deduce:

dim W_{d,t} ≤ max{dim W_{d,L,S} : L, S ∈ IN, LS^{2} ≤ t} ≤ 8t.

Thus for t := \frac{d}{8} we have

dim W_{d, \frac{d}{8}} ≤ d.

This implies that the Zariski open set U := K^{d+1} \ W_{d, \frac{d}{8}} is nonempty. From Lemma 2.6 (iii) we deduce finally that for any polynomial F of K[X] whose degree does not exceed d and which belongs to the set U the tradeoff estimate LS^{2}(F) ≥ \frac{d}{8} holds. □

Following Paterson & Stockmeyer (1973) there exists a constant c > 0 such that any polynomial F ∈ K[X] of arbitrary degree d can be evaluated by a straight–line program in K[X] in nonscalar time not exceeding c\sqrt{d}. Combining this result with Theorem 2.7 we are able to make the following conclusion:

Corollary 2.8. There exist a constant c′ > 0 with the following property: let d be a given natural number and let U be the nonempty Zariski open subset of K^{d+1} introduced in Theorem 2.7. Then for any polynomial F ∈ K[X] of degree at most d satisfying the condition F ∈ U and for any straight–line program β in K(X) which evaluates F in optimal nonscalar time the space S(β) required by the procedure β is bounded from below by

S(β) ≥ c′ ^{4} \sqrt{d}.

We may paraphrase the content of Corollary 2.8 as follows: almost all polynomials of K[X] of degree at most d require space c′ ^{4} \sqrt{d} if they are evaluated optimally with respect to nonscalar time. On the other hand following Paterson & Stockmeyer (1973) there exists a constant c′′ > 0 such that almost all polynomials of K[X] of degree at most d need nonscalar time c′′\sqrt{d} for their evaluation. This explains in which sense Theorem 2.7 contains the best possible generic time–space tradeoff result we may hope for.

3. Tools from geometric elimination and intersection theory

In this paper we shall often face situations like the following one: assume that there is given a polynomial F ∈ K[X] of degree d. Only from the knowledge of the coefficients of F we have to deduce a lower bound for the quantity LS^{2} where L and S are arbitrary natural numbers satisfying the condition F ∈ W_{d,L,S} or the condition F ∈ im Φ_{d,L,S} with W_{d,L,S} and Φ_{d,L,S} defined as in Lemma 2.6 and Lemma 2.5 respectively. These two Lemmas establish a relation between the size of the complexity parameters L and S and the degree or height of the algebraic variety W_{d,L,S} or the algebraic morphism Φ_{d,L,S}.

Therefore we need a tool which allows us to estimate these geometric invariants, namely degree and height of W_{d,L,S} and Φ_{d,L,S} respectively from the knowledge of just one specific point belonging to the algebraic variety W_{d,L,S} or to the image of the morphism Φ_{d,L,S}. We are going to develop such a tool making use of suitable Nullstellensätze and Bézout Inequalities from geometric and arithmetic elimination and intersection theory (compare Paterson & Stockmeyer 1973, Strassen 1974, Schnorr 1978, Heintz & Sieveking 1980, Gathen & Strassen 1981, Heintz & Schnorr 1982, Heintz 1989, Heintz & Morgenstern 1989, Stoss 1989a, Stoss 1989b, Lickteig 1990, Montaña & Pardo 1993, Baur 1996, for a similar viewpoint). In this technical section we are going to explain the results of elimination and intersection theory we shall apply in the sequel. Let us start recalling that the height of a polynomial with integer coefficients is the maximum absolute value of its coefficients. Similarly the logarithmic height of this polynomial is the maximum bit length of its coefficients. The logarithmic height of a polynomial over the integers is therefore roughly speaking the logarithm at base two of its height. The main result of this section is the following one:

Proposition 3.1. Let N, d, D and η be given natural numbers and let Φ := (P_{d}, …, P_{0}) : C^{N} ⟶ C^{d+1} be a morphism of affine spaces with P_{0}, …, P_{d} being polynomials belonging to ZZ[Z_{1}, …, Z_{N}] . Let F be a given point of ZZ^{d+1} . Consider the Φ –fiber V := Φ^{−1}(F) of the point F as a 0 Q –definable Zariski closed subvariety of C^{N}. Suppose that V is nonempty. Let h_{1}, …, h_{s} ∈ ZZ[Z_{1}, …, Z_{N}] be polynomials satisfying the following conditions:

1. V := {z ∈ C^{N} : h_{1}(z) = 0, …, h_{s}(z) = 0}

2. max{deg(h_{i}) : 1 ≤ i ≤ s} ≤ D and

3. max{log_{2} height(h_{i}) : 1 ≤ i ≤ s} ≤ η

Then, there exists a point θ = (θ_{1}, …, θ_{N}) of the fiber V satisfying the estimate

log_{2} max{| θ_{i} | : 1 ≤ i ≤ N} ≤ D^{cN}(log_{2} s + η),

where c > 0 is a suitable universal constant.

The rest of this section is devoted to the proof of this result. To this aim we need a series of intermediate technical results from geometric elimination theory. The first one is a suitable form of an effective Nullstellensatz.

In order to keep exposition more transparent we have choosen a “classical” version of this type of result implying rather coarse lower complexity bounds in our applications. Such Nullstellensatz versions can be found in Brownawell (1987), Caniglia et al. (1988), Caniglia et al. (1989), Kollár (1988). Let us remark that recent “intrinsic” Nullstellensätze as in Giusti et al. (1995, 1996, 1997), Krick et al. (1996), Sombra (1997) would allow a slight improvement of our tradeoff bounds.

Theorem 3.2. (Effective Nullstellensatz) Let D ≥ 3 and N ≥ 3 be given natural numbers and let h_{1}, …, h_{s} ∈ ZZ[Z_{1}, …, Z_{N}] be polynomials of degree at most D. Consider the ideal I = (h_{1}, …, h_{s}) generated by these polynomials in 0 Q[Z_{1}, …, Z_{N}] . Then the ideal I is trivial (i.e. I = (1) ) if and only if there exists polynomials g_{1}, …, g_{s} ∈ ZZ[Z_{1}, …, Z_{N}] satisfying the degree bound

max{deg(g_{i}) : 1 ≤ i ≤ s} ≤ D^{N} − D

such that the Bézout identity

1 = ∑_{1≤i≤s} g_{i}h_{i}  (3.17)

holds.

For a proof of this result see Kollár (1988), Fitchas & Galligo (1990), or Philippon (1989). The bound on the degree of the polynomials g_{1}, …, g_{s} in Theorem 3.2 allow us to reduce the question of the emptyness of the algebraic variety V defined by the polynomials h_{1}, …, h_{s} to the question of solving a inhomogeneous system of linear equations of size D^{N^{2}} ×sD^{N^{2}} over the rational numbers. The entries of this linear equation system are given by the coefficients of the polynomials h_{1}, …, h_{s}. This linear system of equations allows us to compute a suitable polynomial of bounded degree which expresses a certain elimination property of the variety V . This observation leads us to the next result.

Lemma 3.3. Let D ≥ 3 and N ≥ 3 be given natural numbers and let V be a 0 Q –definable Zariski closed subset of C^{N} having positive dimension r. Suppose that V is given as the locus of zeroes of finitely many polynomials in ZZ[Z_{1}, …, Z_{N}] of degree at most D. Let us introduce for 1 ≤ i ≤ r and 1 ≤ j ≤ N + 1 new indeterminates T_{i,j} and polynomials

L_{i} := T_{i,1}Z_{1} + ⋯ + T_{i,N}Z_{N} + T_{i,N+1}.

Under this assumptions there exists a non–zero polynomial E ∈ ZZ[T_{i,j}; 1 ≤ i ≤ r, 1 ≤ j ≤ N + 1] of degree at most D^{N^{2}} having the following property: for any matrix t = (t_{i,j})_{{1≤i≤r, 1≤j≤N+1}} of C^{r×(N+1)} defining r affine linear polynomials

L_{1}(t, Z_{1}, …, Z_{N}) = t_{1,1}Z_{1} + ⋯ + t_{1,N}Z_{N} + t_{1,N+1},
⋮
L_{r}(t, Z_{1}, …, Z_{N}) = t_{r,1}Z_{1} + ⋯ + t_{r,N}Z_{N} + t_{r,N+1}

the intersection of V with the affine linear subspace of C^{N} given by these polynomials, namely

V ∩ {z ∈ C^{N} : L_{1}(t, z) = 0, …, L_{r}(t, z) = 0},

is nonempty if the (consistent) Zariski open condition E(t) ≠ 0 holds.

Notation 3.4. For the rest of this section let us fix the following notations:

T := (T_{i,j})_{1≤i≤r,1≤j≤N+1} and Z := (Z_{1}, …, Z_{N}).

Proof of Lemma 3.3. By hypothesis there exist finitely many, say s polynomials h_{1}, …, h_{s} ∈ ZZ[Z_{1}, …, Z_{N}] of degree at most D which define the variety V . Since r is the (positive) dimension of V there exists a nonempty Zariski open subset U of C^{r×(N+1)} such that for any t ∈ U the intersection

V ∩ {z ∈ C^{N} : L_{1}(t, z) = 0, …, L_{r}(t, z) = 0},

contains at least one point (see e.g. Heintz 1983, Lemma 1). This implies that the ideal J generated by the polynomials h_{1}, …, h_{s}, L_{1}, …, L_{r} in the polynomial ring 0 Q(T)[Z] is proper. From Theorem 3.2 we deduce therefore that there cannot exist polynomials g_{1}, …, g_{r+s} ∈ 0 Q(T)[Z] such that for any 1 ≤ k ≤ r + s the polynomial g_{k} has the form

g_{k}(Z) := ∑_{ν_{1}+···+ν_{N} ≤D^{N} −D} Y_{ν_{1},...,ν_{N}}^{(k)} Z_{1}^{ν_{1}} … Z_{N}^{ν_{N}}

with coefficients Y_{ν_{1},...,ν_{N}}^{(k)} in the field 0 Q(T) and such that the Bézout identity

1 = g_{1}(Z)h_{1}(Z) + ⋯ + g_{s}(Z)h_{s}(Z) +
+ g_{s+1}(Z)L_{1}(T, Z) + ⋯ + g_{r+s}(Z)L_{r}(T, Z) (3.18)

holds in 0 Q(T)[Z] . We may interpret the (inconsistent) polynomial identity (3.18) as an inhomogeneous linear equation system in the unknowns Y_{ν_{1},...,ν_{N}}^{(k)} appearing as coefficients of the “potential” polynomials g_{1}, …, g_{r+s} in the variables Z_{1}, …, Z_{N}. This equation system has roughly size D^{N^{2}} ×sD^{N^{2}} and its matrix, which we denote by A, contains as entries only coefficients of the polynomials h_{1}, …, h_{s} and L_{1}, … L_{r} with respect to the variables Z_{1}, …, Z_{N}. Thus the matrix A is built up by integers and indeterminates T_{i,j}. Let us write

AY = B  (3.19)

for the inhomogeneous linear equation system representing the polynomial identity (3.18). Here B and Y are column vectors of length at most D^{N^{2}} and sD^{N^{2}} respectively, all entries of B are 0 except one wich is 1 , and Y is the column vector of unknowns of the system. These unknowns can be written as Y_{ν_{1},...,ν_{N}}^{(k)} with 1 ≤ k ≤ r+s and ν_{1}+⋯+ν_{n} ≤ D^{N}. The inconsistency of the polynomial identity (3.18) implies the inconsistency of the linear equation system (3.19). Therefore the rank of the matrix A is strictly smaller than the rank, say m, of the matrix A^{∗} obtained by adding to the matrix A the column vector B. This means that A^{∗} contains a regular m×m minor with nonzero determinant E ∈ ZZ[T] whereas all m × m minors of A are singular. This determinant E(T) express a suitable elimination property of the algebraic variety defined in C^{r×(N+1)} × C^{N} by the polynomials h_{1}(Z), …, h_{s}(Z), L_{1}(T, Z), …, L_{r}(T, Z) if we project this variety into the affine space C^{r×(N+1)} . The following arguments contain the precise sense of this statement and its justification: for any t ∈ C^{r×(N+1)} such that E(t) ≠ 0 holds the linear equation system we obtain from (3.19) specializing the generic matrix T into t is inconsistent. In view of Theorem 3.2 this means that the ideal generated by the polynomials h_{1}(Z), …, h_{s}(Z), L_{1}(t, Z), …, L_{r}(t, Z) in the polynomial ring C[Z] is proper. Therefore the variety

V ∩ {z ∈ C^{N} : L_{1}(t, z) = 0, …, L_{r}(t, z) = 0} = = {z ∈ C^{N} : h_{1}(z) = 0, …, h_{s}(z) = 0, L_{1}(t, z) = 0, …, L_{r}(t, z) = 0}

is nonempty. Observe now that the entries of the matrix A^{∗} are constants or linear polynomials of ZZ[T] and that it contains at most D^{N^{2}} rows what implies m ≤ D^{N^{2}} . Therefore the degree of the polynomial E(T) is bounded by D^{N^{2}} . □

Lemma 3.3 represents the main step in the proof of the next result.

Lemma 3.5. Let D ≥ 3 and N ≥ 3 be natural numbers and let V a 0 Q –definable Zariski closed subset of C^{N} having positive dimension r. Suppose that V is given as the locus of zeroes of finitely many polynomials of ZZ[Z_{1}, …, Z_{N}] of degree at most D. Then there are r affine linear polynomials L_{1}, …, L_{r} ∈ ZZ[Z_{1}, …, Z_{N}] of logarithmic height bounded by N(N +1) log_{2} D, such that for any 1 ≤ k ≤ r the algebraic variety

V ∩ {z ∈ C^{N} : L_{1}(z) = 0, …, L_{k}(z) = 0}

is nonempty of dimension r − k.

We observe here that the results of Krick & Pardo (1996), Subsection 4.8 imply an improvement of the estimate for the logarithmic height of the affine linear polynomials L_{1}, …, L_{r} in Lemma 3.5 to cN log_{2} D where c > 0 is a suitable universal constant. However we prefer to work with the coarser height bound in the statement of Lemma 3.5, since the impact of the mentioned improvement on our complexity results is rather modest and since this coarse bound is much easier to prove. In the following proof we shall make again use of the matrix

T := (T_{i,j})_{1≤i≤r,1≤j≤N+1}

of indeterminates T_{i,j} introduced above.

Proof of Lemma 3.5. Applying Lemma 3.3 we construct recursively in the dimension r of the variety V affine linear polinomials L_{1}, …, L_{r} ∈ ZZ[Z] satisfying the requirements of the Lemma to show. Before starting this recursive construction let us observe that the assumption that V being given by N –variate polynomials of degree at most D and the Bézout Inequality (see e.g. Heintz 1983, Theorem 1 or Fulton 1984, Example 8.4.6) imply together that the degree of V is bounded by D^{N} (in the sequel we shall denote the degree of V by deg V ). Let us first consider the case r := 1 . Since deg V ≤ D^{N} holds we may choose a set Γ of at most D^{N} points of V such that for each irreducible component of maximal dimension r = 1 of V there exist at least one point in this component belonging to Γ . Let

Q := ∏_{(γ_{1},...,γ_{N})∈Γ}(γ_{1}T_{1,1} + ⋯ + γ_{N}T_{1,N} + T_{1,N+1}) ∈ C[T_{1,1}, …, T_{1,N+1}]

and let E_{1} ∈ ZZ[T_{1,1}, …, T_{1,N}] be the elimination polynomial of Lemma 3.3. Thus QE_{1} is a nonzero polynomial of C[T_{1,1}, …, T_{1,N+1}] of degree at most D^{N^{2}} + D^{N} < D^{N(N+1)} . Therefore there exists in the set

{(t_{1,1}, …, t_{1,N+1}) ∈ ZZ^{N+1} : max{| t_{1,j} |: 1 ≤ j ≤ N + 1} ≤ D^{N(N+1)}}

a point (t_{1,1}, …, t_{1,N+1}) such that QE_{1}(t_{1,1}, …, t_{1,N+1}) ≠ 0 holds. Let L_{1} := t_{1,1}Z_{1} + ⋯ + t_{1,N}Z_{N} + t_{1,N+1} . From Q(t_{1,1}, …, t_{1,N+1}) ≠ 0 we deduce that the affine hyperplane {z ∈ C^{N} : L_{1}(z) = 0} cuts properly all irreducible components of V of maximal dimension r = 1 and E_{1}(t_{1,1}, …, t_{1,N+1}) ≠ 0 implies that V ∩ {z ∈ C^{N} : L_{1}(z) = 0} is nonempty. Therefore by the Dimension Theorem (see e.g. Shafarevich 1994) the dimension of the algebraic variety V ∩{z ∈ C^{N} : L_{1}(z) = 0} is r−1 = 0 . Moreover the logarithmic height of the affine linear polynomial L_{1} satisfies the requirements in the conclusion of Lemma 3.5. In the general case r > 1 we proceed similarly. We assume inductively that we are able to find for any closed subvariety of C^{N} of dimension r − 1 which is definable by polynomials of ZZ[Z_{1}, …, Z_{N}] of degree at most D, a set of r − 1 affine linear polynomials of ZZ[Z_{1}, …, Z_{N}] satisfying the requirements in the conclusion of Lemma 3.5. Again we choose a set Γ of at most D^{N} points of V such that for each component of maximal dimension r of V there exist at least one point in this component belonging to Γ . Let

Q := ∏_{(γ_{1},...,γ_{N})∈Γ}(γ_{1}T_{1,1} + ⋯ + γ_{N}T_{1,N} + T_{1,N+1}) ∈ C[T_{1,1}, …, T_{1,N+1}]

and let E_{r} ∈ ZZ[T] be the elimination polynomial of Lemma 3.3. Thus QE_{r} is again a nonzero polynomial of C[T] of degree strictly less than D^{N(N+1)} . Therefore there exists in the set

{(t_{i,j})_{1≤i≤r, 1≤j≤N+1} ∈ ZZ^{r×(N+1)} :
: max{| t_{i,j} |: 1 ≤ i ≤ r, 1 ≤ j ≤ N + 1} ≤ D^{N(N+1)}}

a point t = (t_{i,j})_{1≤i≤r, 1≤j≤N+1} such that QE_{r}(t) ≠ 0 holds. Let L_{1} := t_{1,1}Z_{1} + ⋯ + t_{1,N}Z_{N} + t_{1,N+1} . From Q(t) = Q(t_{1,1}, …, t_{1,N+1}) ≠ 0 we deduce that the affine hyperplane {z ∈ C^{N} : L_{1}(z) = 0} cuts properly all components of V of maximal dimension r. On the other hand, if we write T^{∗} for the matrix obtained from T replacing the first row vector (T_{1,1}, …, T_{1,N+1}) in T by (t_{1,1}, …, t_{1,N+1}) we are able to infer from E_{r}(t) ≠ 0 that the (r−1)(N +1) – variate polynomial E_{r}(T^{∗}) is nonzero. From Lemma 3.3 one deduces easily that any selection of r − 1 affine linear polynomials of C[Z_{1}, …, Z_{n}] whose coefficients satisfy the nonempty Zariski open condition E_{r}(T^{∗}) ≠ 0 define a nonempty intersection with the algebraic variety W := V ∩ {z ∈ C^{N} : L_{1}(z) = 0}. This implies that W is nonempty and that dim W = r − 1 holds. On the other hand W is definable by polynomials of ZZ[Z_{1}, …, Z_{N}] of degree at most D. Thus applying the induction hypothesis to the variety W we find affine linear polynomials L_{2}, …, L_{r} ∈ ZZ[Z_{1}, …, Z_{N}] of logarithmic height bounded by N(N + 1) log_{2} D such that for any 2 ≤ k ≤ r the Zariski closed subset

W ∩ {z ∈ C^{N} : L_{2}(z) = 0, …, L_{k}(z) = 0} =
= V ∩ {z ∈ C^{N} : L_{1}(z) = 0, …, L_{k}(z) = 0}

is nonempty of dimension dim W − (k − 1) = (r − 1) − (k − 1) = r − k. Putting all this information together we see that the affine linear polynomials L_{1}, …, L_{r} satisfy the requirements in the conclusion of Lemma 3.5. □

In order to finish the proof of Proposition 3.1 we need now the following result which estimates the absolute value of the coordinates of the isolated points of a 0 Q –definable Zariski closed subset of the affine space C^{N}.

Proposition 3.6. Let N, D, η and s be given natural numbers with D ≥ N and let h_{1}, …, h_{s} be polynomials of degree at most D and logarithmic height at most η belonging to ZZ[Z_{1}, …, Z_{N}] . Let V be the Zariski closed subset of C^{N} defined by these polynomials, i.e. let

V := {z ∈ C^{N} : h_{1}(z) = 0, …, h_{s}(z) = 0}.

Then any isolated point θ := (θ_{1}, …, θ_{N}) of V satisfies the estimate

max{log_{2} | θ_{i} |: 1 ≤ j ≤ N} ≤ D^{c′N}(log_{2} s + η),

where c′ > 0 is a suitable universal constant.

For a proof of this result see Krick & Pardo (1996), Corollary 7. We are now able to show Proposition 3.1:

Proof of Proposition 3.1. Let r := dim V . Since V is nonempty by assumption we have 0 ≤ r ≤ N. In case r = 0 all points of V are isolated and we may apply directly Proposition 3.6 to get a point θ of V satisfying the required estimate. Let us therefore suppose r > 0 . From Lemma 3.5 we deduce that there exist r affine linear polynomials in ZZ[Z_{1}, …, Z_{N}] , say L_{1}, …, L_{r}, of logarithmic height at most N(N + 1) log_{2} D such that

W := V ∩ {z ∈ C^{N} : L_{1}(z) = 0, …, L_{r}(z) = 0} = = {z ∈ C^{N} : h_{1}(z) = 0, …, h_{s}(z) = 0, L_{1}(z) = 0, …, L_{r}(z) = 0} is a zero–dimensional algebraic subvariety of C^{N}. In particular W is nonempty. The variety W is defined by s + r ≤ s + N polynomials which belong to ZZ[Z_{1}, …, Z_{N}] and which have degree at most D and logarithmic height at most max{η, N(N + 1) log_{2} D}. Let θ = (θ_{1}, …, θ_{N}) be any point of W . Applying Proposition 3.6 to the variety W we deduce the estimate

max{log_{2} | θ_{i} |: 1 ≤ j ≤ N} ≤ D^{c′N}(log_{2}(s+N)+max{η, N(N +1) log_{2} D}) ≤

≤ D^{cN}(log_{2} s + η),

where c > 0 is a suitable universal constant (here we use the assumption D ≥ N). Since W is contained in V the point θ belongs to the variety V . Moreover the absolute values of the coordinates of θ satisfy the requirements in the conclusion of Proposition 3.1. □

4. Polynomials which are hard to compute

In this last section we are going to exhibit some examples of specific time– space tradeoff hard families of univariate polynomials. In these examples we shall be able to exhibit significant lower bounds for the space requirements of any nonscalar time optimal procedure which evaluates these polynomials. We may divide our examples in two main groups following the criterion whether the polynomials under consideration are given by their coefficients or by their roots. The interest of the latter group of examples is motivated by the search for lower complexity bounds in geometric elimination theory where the representation of polynomials given by their roots arises naturally (see Heintz & Morgenstern 1993). A second division of our examples in two classes will be given by the distinction whether the polynomials under consideration have algebraic or only rational coefficients. We have tried to find an almost unified presentation for these example classes.

4.1. Polynomials given by their coefficients.

We present in this section a series of techniques for showing lower bounds for time–space tradeoffs and apply them to specific families of polynomials with integer and algebraic coefficients. We start with two particular families of polynomials with integer coefficients and show that these families are hard to compute in terms of time–space tradeoff. Then the same kind of result is proved for a specific family of polynomials with algebraic coefficients. Finally we show that there exist many families of polynomials with {0, 1} -coefficients which are hard to compute in terms of time–space tradeoff.

4.1.1 Polynomials with integer coefficients.

In Strassen (1974) there are presented several explicit families of polynomials with integer coefficients which are shown to be hard to compute in the sense of sequential time complexity. This kind of result is extended and improved in Schnorr (1978) and Stoss (1989a). We apply Proposition 3.1 in order to obtain time-space tradeoff results in the spirit of the above cited references.

Example 4.1. Let F_{1} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ ZZ[X] of degree d defined by

F_{d} := ∑_{0≤j≤d} 2^{j!}X^{j}.

Then this family F_{1} is hard to compute in the sense of time-space tradeoff. More precisely, we have

LS^{2}(F_{d}) = Ω(d).

Proof. Let d be fixed and let F := F_{d}. Furthermore, let L and S be arbitrary natural numbers such that the polynomial F can be computed by a straight–line program in 0 Q(X) , using non-scalar time L and space S. Thus the polynomial F belongs to the image of the morphism

Φ := Φ_{d,L,S} := (P_{d}, …, P_{0}) : C^{N} ⟶ C^{d+1}

introduced in Lemma 2.5, with N := 8LS^{2}+1 and P_{0}, …, P_{d} ∈ ZZ[Z_{1}, …, Z_{N}] . (Remember that we identify the polynomial F ∈ ZZ[X] with the point

(f_{j})_{0≤j≤d} := (2^{j!})_{0≤j≤d}

of C^{d+1} given by the vector of coefficients of F ). We observe that (f_{j})_{0≤j≤d} is the only point of C^{d+1} contained in the algebraic variety

{(f_{d}, …, f_{0}) ∈ C^{d+1} : f_{0} − 2 = 0, f_{1} − f_{0} = 0, …, f_{d} − f_{d−1}^{d} = 0}.

Let Z = (Z_{1}, …, Z_{N}) and consider the polynomials Q_{0}, …, Q_{d} ∈ ZZ[Z] defined by Q_{0} := P_{0}(Z) − 2 and Q_{j}(Z) := P_{j}(Z) − P_{j−1}^{j}(Z) with 1 ≤ j ≤ d. Note that the Φ –fiber V := Φ^{−1}(F) of the point F ∈ C^{d+1} is the algebraic set

V = {z ∈ C^{N} : Q_{0}(z) = 0, …, Q_{d}(z) = 0}.

Let

D := max{deg Q_{i} : 0 ≤ j ≤ d}

and

η := max{log_{2} height(Q_{j}) : 0 ≤ j ≤ d}.

From Lemma 2.5 we deduce that

deg(Q_{j}) ≤ j deg(P_{j}) ≤ 2j(Ld + 1) ≤ 2d(Ld + 1)

holds for 0 ≤ j ≤ d. This implies

D ≤ 2d(Ld + 1).  (4.20)

Furthermore, from Lemma 2.5 we conclude

log_{2}(height(Q_{0})) ≤ 1 + log_{2}(weight(P_{0})) ≤
≤ 1 + (d + 1) log_{2}(d + 1) + (d + 1)^{L+1}(2 + log_{2}(S + 1)),

and

log_{2}(height(Q_{j})) ≤ log_{2}(weight(P_{j})) + log_{2}(weight(P_{j−1}))^{j} ≤
≤ (d + 1) log_{2}(d + 1) + (d + 1)^{L+1}(2 + log_{2}(S + 1)) +
+ d((d + 1) log_{2}(d + 1) + (d + 1)^{L+1}(2 + log_{2}(S + 1))) ≤
≤ (d + 1)^{2} log_{2}(d + 1) + (d + 1)^{L+2}(2 + log_{2}(S + 1))

for 1 ≤ j ≤ d. This implies the height bound

η ≤ (d + 1)^{2} log_{2}(d + 1) + (d + 1)^{L+2}(2 + log_{2}(S + 1)) + 1.  (4.21)

Applying Proposition 3.1 to the algebraic variety V above and taking into account the depth and height estimates (4.20) and (4.21)), we conclude that V contains a point θ = (θ_{1}, …, θ_{N}) satisfying the estimate:

log_{2} max{| θ_{i} |: 1 ≤ i ≤ N} ≤ D^{cN}(log_{2}(d + 1) + η)},

where c > 0 is a suitable universal constant. Let us write | θ |:= max{| θ_{i} |: 1 ≤ i ≤ N}. In order to finish the proof let us consider for 0 ≤ j ≤ d the j –th coefficient f_{j} of the polynomial F . Since the image of the point θ under the morphism Φ is F , we have f_{j} = P_{j}(θ) for 0 ≤ j ≤ d. Thus, by Lemma 2.5 the absolute value of f_{j} is bounded as follows:

log_{2} | f_{j} | ≤ log_{2} weight(P_{j}) + deg P_{j} · log_{2} | θ | ≤
≤ (d + 1) log_{2} (d + 1) + (d + 1)^{L+1}(2 + log_{2}(S + 1)) +
+ 2(Ld + 1)D^{cN}(η + log_{2}(d + 1)).

From Horner’s rule we deduce that we may assume without loss of generality that LS^{2} ≤ c_{1}d holds for a suitable universal constant c_{1} . Combining this observation with the estimates (4.20) and (4.21) for D and η, we conclude that the absolute values of the coordinates f_{0}, …, f_{d} of the polynomial F satisfy the inequalities

d! ≤ max{log_{2} | f_{j} | : 0 ≤ j ≤ d} ≤ d^{c_{2}N},

where c_{2} > 0 is a suitable universal constant. Thus we obtain d! ≤ d^{c_{2}N} on one hand and N = 8LS^{2} + 1 on the other. This implies c_{3}d ≤ LS^{2} for a suitable universal constant c_{3} > 0 . Since L and S are the time and space requirements of an arbitrary straight–line program evaluating the polynomial F = F_{d} we finally obtain LS^{2}(F_{d}) = Ω(d) . □

Example 4.2. Let F_{2} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ ZZ[X] of degree d defined by

F_{d} := ∑_{0≤j≤d} 2^{2^{j}}X^{j}.

Then this family F_{2} is hard to compute in the sense of time-space tradeoff. More precisely, we have

LS^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}) .

The proof of this bound can be established in the same way as in in Example 4.1. For given d, L, S ∈ IN one has to consider the algebraic variety

{(f_{d}, …, f_{0}) ∈ C^{d+1} : f_{0} − 2 = 0, f_{1} − f_{0}^{2} = 0, …, f_{d} − f_{d−1}^{2} = 0} whose only point is the coefficient vector of the polynomial F_{d}. The Φ_{d,L,S} - fiber of this variety is defined by P_{0}(Z)−2 and the polynomials P_{j}(Z)−P_{j−1}^{2}(Z) with 1 ≤ j ≤ d. The remaining arguments are the same as in the proof of the lower bound of Example 4.1.

Let us remark that Example 4.2 is analyzed in Strassen (1974) where the sequential time lower bound L(F_{d}) = Ω ( ^{3} \sqrt{\frac{d}{log_{2} d}}) is shown.

4.1.2 Polynomials with algebraic coefficients.

In this subsection we adapt two general methods for proving lower complexity bounds for polynomials with non-rational coefficients to the context of timespace tradeoffs. The first method we present was recently introduced by W. Baur (Baur 1996). The description of a similar idea can be found in Bürgisser et al. (1996), Chapter 9, Exercise 9.11.

Proposition 4.3. There exists a universal constant c > 0 with the following property: Let D be a given natural number and let

F := ∑_{0≤j≤d} f_{j}X^{j}

be a polynomial of degree at most d with complex coefficients. Suppose that there exist polynomials g_{1}, …, g_{m} ∈ 0 Q[Y_{d}, …, Y_{0}] of degree at most D, and suppose that the complex values g_{1}(f_{d}, …, f_{0}), …, g_{m}(f_{d}, …, f_{0}) are 0 Q – linearly independent. Under these assumptions we have

LS^{2}(F) ≥ c · \frac{log_{2} m}{log_{2} d + log_{2} D}.

Proof. Let be given an arbitrary straight-line program β in C(X) which evaluates the polynomial F in nonscalar time L and space S. As before we deduce from Horner’s rule that we may assume without loss of generality that L ≤ d holds. Let N := 8LS^{2} + 1 and δ := (2Ld + 1) . Let Z_{1}, …, Z_{N} be new indeterminates. Then by Lemma 2.5 there exist polynomials P_{d}, …, P_{0} ∈ ZZ[Z_{1}, …, Z_{N}] of degree at most δ such that the coefficient vector (f_{d}, …, f_{0}) of F is in the image of the morphism of affine spaces Φ_{d,L,S} : C^{N} ⟶ C^{d+1} given by (P_{d}, …, P_{0}) . Since by assumption the complex values g_{1}(f_{d}, …, f_{0}), …, g_{m}(f_{d}, …, f_{0}) are 0 Q –linearly independent and since there exists a point θ ∈ C^{N} such that

(f_{d}, …, f_{0}) = (P_{d}(θ), …, P_{0}(θ))

holds, we conclude that the polynomials g_{1}(P_{d} …, P_{0}), …, g_{m}(P_{d}, …, P_{0}) must be 0 Q –linearly independent too. Note that these polynomials have degree bounded by δD. This implies that the 0 Q –vector space:

P := {G ∈ 0 Q[Z_{1}, …, Z_{N}] : deg G ≤ δD}

has at least dimension m. On the other hand we have

dimP = \binom{N + δD}{N} ≤ (δD)^{N}.

Taking into account L ≤ d we deduce from this the estimate

m ≤ (δD)^{N} = (2(Ld + 1)D)^{8LS^{2}+1} ≤ (2(d^{2} + 1)D)^{8LS^{2}+1}.

Taking logarithms, we conclude that there exists a universal constant c > 0 such that LS^{2} ≥ c\frac{log_{2} m}{log_{2} d+log_{2} D} holds. Since β was an arbitrary straight-line program in C(X) computing the polynomial F in nonscalar time L and space S Proposition 4.3 follows. □

The second method for showing lower bounds for time-space tradeoffs of polynomials with nonrational coefficients goes back to Heintz & Sieveking (1980).

Proposition 4.4. There exists a universal constant c > 0 with the following property: Let D be a given natural number and let

F := ∑_{0≤j≤d} f_{j}X^{j}

be a polynomial of degree at most d with complex algebraic coefficients. Let ρ be the cardinality of the orbit of the point (f_{d}, …, f_{0}) ∈ C^{d+1} under the action of the group of automorphisms of C over 0 Q . Suppose that there exist polynomials g_{1}, …, g_{m} ∈ 0 Q[Y_{d}, …, Y_{0}] of degree at most D, such that the locus of common zeroes of these polynomials in C^{d+1} is finite and contains the point (f_{d}, …, f_{0}) . Under these assumptions we have

LS^{2}(F) ≥ c · \frac{log_{2} ρ}{log_{2} d + log_{2}D}.

Proof. Let β be an arbitrary straight–line program in C(X) which evaluates the polynomial F in nonscalar time L and space S. Observe that the coefficient vector (f_{d}, …, f_{0}) of the polynomial F belongs to the algebraic subvariety W := W_{d,L,S} of C^{d+1} introduced in Lemma 2.6. Let r := dimW and observe that r ≤ 8LS^{2} holds by the same lemma. We choose now r generic 0 Q -linear combinations

B_{k} := β_{1}^{(k)}g_{1} + … + β_{m}^{(k)}g_{m} ∈ 0 Q[Y_{d}, …, Y_{0}]

of the polynomials g_{1}, …, g_{m} with 1 ≤ k ≤ r and coefficients β_{1}^{(k)}, …, β_{m}^{(k)} ∈ 0 Q . The genericity of this choice and the fact that the polynomials g_{1}, …, g_{m} define a nonempty finite subset (i.e. a zero-dimensional subvariety) of C^{d+1} imply together with r = dimW that the set

V := W ∩ {(y_{d}, …, y_{0}) ∈ C^{d+1} : B_{1}(y_{d}, …, y_{0}) = 0, …, B_{r}(y_{d}, …, y_{0}) = 0}

is finite. Observe that (f_{d}, …, f_{0}) ∈ V holds and that B_{1}, …, B_{r} are polynomials of 0 Q[Y_{d}, …, Y_{0}] of degree at most D. Therefore V is a zero-dimensional 0 Q -definable subvariety of C^{d+1} which contains the whole orbit of the point (f_{d}, …, f_{0}) under the action of the automorphism group of C over 0 Q . This implies ρ ≤ #V = degV . From the Bézout Inequality and Lemma 2.6 (ii) we infer

degV ≤ degW · D^{r} ≤ degW · D^{8LS^{2}} ≤ (2(Ld + 1)D)^{8LS^{2}}.

As before we may assume without loss of generality that L ≤ d holds. Putting all this information together we obtain the estimate

ρ ≤ (2(d^{2} + 1)D)^{8LS^{2}}.

Taking logarithms, we conclude that there exists a universal constant c > 0 such that LS^{2} ≥ c · \frac{log_{2} ρ}{log_{2} d+log_{2} D} holds. Since β was an arbitrary straight–line program in C(X) computing the polynomial F in nonscalar time L and space S Proposition 4.4 follows. □

Using Propositions 4.3 and 4.4 we are now going to exhibit two families of polynomials with algebraic coefficients which are hard to compute in the sense of time–space tradeoff. These families were already analyzed in Heintz & Sieveking (1980), and von zur Gathen & Strassen (1981), Application 2 from the point of view of sequential time complexity.

Example 4.5. 1. Let F_{3} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ IR[X] of degree d defined by

F_{d} := ∑_{1≤j≤d} \sqrt{p_{j}}X^{j−1},

where p_{j} denotes the j –th prime number. Then this family F_{3} is hard to compute in the sense of time–space tradeoff. More precisely, we have

LS^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}) .

2. Let be F_{4} := (F_{d})_{d∈IN} the family of polynomials F_{d} ∈ C[X] of degree d defined by

F_{d} := ∑_{1≤j≤d} e^{\frac{2πi}{j}} X^{j−1}

where e^{\frac{2πi}{j}} stands for the (canonical) j –th root of unity contained in C. Then this family F_{4} is hard to compute in the sense of time–space tradeoff. More precisely, we have

LS^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}) .

Proof. Let Y_{d}, …, Y_{0} be new indeterminates. First we discuss the asymptotical lower bound for the family F_{3} . We are going to apply Proposition 4.3. For any S ⊆ {1, …, d} we consider the polynomial

g_{S} := ∏_{j∈S} Y_{j} ∈ 0 Q[Y_{d}, …, Y_{0}].

Observe that the degree of g_{S} is bounded by d. From von zur Gathen & Strassen (1981) we deduce easily that the family of complex values

(g_{S}(\sqrt{p_{1}}, …, \sqrt{p_{d}}) : S ⊆ \{1, …, d\})

is 0 Q -linearly independent. The lower bound for the time-space tradeoff of the family F_{3} follows now easily from Proposition 4.3 setting m := 2^{d} and D := d.

As for the family F_{4} , we will apply Proposition 4.4. Let us consider the polynomials

g_{1} := Y_{0}, g_{2} := Y_{1} − 1, g_{3} := Y_{2}^{2} − 1, …, g_{d+1} := Y_{d}^{d} − 1.

Observe that these polynomials vanish at the point θ := (0, e^{\frac{2πi}{1}} , …, e^{\frac{2πi}{d}}) ∈ C^{d+1} which represents the coefficients of the d -th member of the family F_{4} , namely the polynomial F_{d} = ∑_{1≤j≤d} e^{\frac{2πi}{j}} X^{j−1} . Moreover, the polynomials g_{1}, …, g_{d+1} belong to 0 Q[Y_{d}, …, Y_{0}] and have degree at most d. They define a finite subset of C^{d+1} . Let ρ be the cardinality of the orbit of the point θ under the action of the group of automorphisms of C over 0 Q . Let us denote by φ the Euler function and by [1, 2, …, d] the least common multiple of the numbers 1, 2, …, d. With this notation one sees easily that

ρ = [ 0 Q(e^{\frac{2πi}{1}} , …, e^{\frac{2πi}{d}}) : 0 Q] = φ([1, 2, …, d])

holds. From the Prime Number Theorem (see e.g. Chandrasekharan 1968) one infers

log_{2}ρ = log_{2} φ([1, 2, …, d]) = Ω(d).

The lower bound for the time-space tradeoff of the family F_{4} follows now easily from Proposition 4.4 setting D := d. □

4.1.3 Polynomials with {0, 1} –coefficients.

In this subsection we show that almost all polynomials with {0, 1} –coefficients are hard to compute in the sense of time-space tradeoff. The method we are going to use for the proof of this result was applied in a slightly different way in Heintz & Schnorr (1982) in order to prove a lower bound for the nonscalar time complexity of these polynomials. Let us introduce the following notation: For any natural number d let

LS_{{0,1}}^{2}(d) := max{LS^{2}( ∑_{0≤j≤d} f_{j}X^{j}) : (f_{d}, …, f_{0}) ∈ {0, 1}^{d+1}}.

Theorem 4.6. Let d ≥ 2 and k be natural numbers with d > k log_{2} d. Then the following holds:

(i) #\{(f_{d}, …, f_{0}) ∈ \{0, 1\}^{d+1} : LS^{2}(∑_{0≤j≤d} f_{j}X^{j}) ≤ \frac{1}{16}(\frac{d}{log_{2} d} − k)\} ≤ \frac{2^{d}}{d^{k}} ,

(ii) LS_{\{0,1\}}^{2}(d) ≥ \frac{1}{16} \frac{d}{log_{2} d}.

Proof. Let be given natural numbers d, k, L, S subject to the conditions d ≥ 2 , d > k log_{2} d and LS^{2} ≤ \frac{1}{16}(\frac{d}{log_{2} d} − k) . Observe that the set \{0, 1\}^{d+1} can be defined as the intersection of d + 1 hypersurfaces of C^{d+1} of degree 2 , namely as

{0, 1}^{d+1} = {(f_{d}, …, f_{0}) ∈ C^{d+1} : f_{d}^{2} − f_{d} = 0, …, f_{0}^{2} − f_{0} = 0}.

Applying Heintz & Schnorr (1982), Proposition 2.3 and Lemma 2.6 of Section 2 we deduce from the Bézout Inequality the following estimates:

#(W_{d,L,S} ∩ {0, 1}^{d+1}) ≤ deg W_{d,L,S} · 2^{dim W_{d,L,S}} ≤
≤ (4(Ld + 1))^{8LS^{2}} ≤ (8Ld)^{8LS^{2}} ≤
≤ (8LS^{2}d)^{8LS^{2}}.

Taking logarithms and using the assumption LS^{2} ≤ \frac{1}{16}(\frac{d}{log_{2} d} − k) , we conclude

log_{2}(#(W_{d,L,S} ∩ {0, 1}^{d+1})) ≤ 8LS^{2} log_{2}(8LS^{2}d) ≤
≤ \frac{1}{2} (\frac{d}{log_{2} d} − k) log_{2} (\frac{1}{2} (\frac{d}{log_{2} d} − k) d) ≤
≤ \frac{1}{2} (\frac{d}{log_{2} d} − k) log_{2} (\frac{1}{2}d^{2} (\frac{1}{log_{2} d} − \frac{k}{d} )) .

Thus,

log_{2}(#(W_{d,L,S} ∩ \{0, 1\}^{d+1})) ≤ \frac{1}{2}(\frac{d}{log_{2} d} − k) (2 log_{2} d + log_{2}(\frac{1}{2}(\frac{1}{log_{2} d} − \frac{k}{d}))) .

From the assumption d > k log_{2} d we deduce 0 < \frac{1}{2}(\frac{1}{log_{2} d} − \frac{k}{d}) ≤ 1 . This implies

log_{2}(#(W_{d,L,S} ∩ {0, 1}^{d+1})) ≤ d − k log_{2} d.

From Lemma 2.6 (iii) we infer now that

#\{(f_{d}, …, f_{0}) ∈ \{0, 1\}^{d+1} : LS^{2}( ∑_{0≤j≤d} f_{j}X^{j}) ≤ \frac{1}{16}(\frac{d}{log_{2} d} − k)\} ≤ \frac{2^{d}}{d^{k}}

holds, i.e. assertion (i) of the theorem. Assertion (ii) follows from (i) putting k := 1 and observing that the set \{0, 1\}^{d+1} has 2^{d+1} > \frac{2^{d}}{d} elements. □

4.2. Polynomials given by their roots.

The study of lower complexity bounds for the computation of families of polynomials given by their roots is motivated by their relationship with the intrinsic complexity of quantifier elimination procedures. Evidence for this relationship can be found in Heintz & Morgenstern (1993) and Pardo (1995). In this subsection we exhibit two examples of families of polynomials given by their roots which are hard to compute in terms of time-space tradeoff.

Let Y_{d−1}, …, Y_{0} be new indeterminates and let

G := X^{d} + Y_{d−1}X^{d−1} + ⋯ + Y_{0}

be the generic monic polynomial in the variable X with coefficients Y_{d−1}, … …, Y_{0} . Furthermore let D(Y_{d−1}, …, Y_{0}) be the discriminant of the polynomial G with respect to the variable X.

Lemma 4.7. Let F_{5} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ ZZ[X] of degree d defined by

F_{d} := ∏_{1≤j≤d}(X − 2^{2^{j}}).

Then F_{d} is the only monic polynomial F = X^{d} +f_{d−1}X^{d−1} +⋯+f_{0} of degree d with real coefficients which satisfies the following four conditions:

1. F (0) ≠ 0, F (1) ≠ 0, F (−1) ≠ 0

2. D(f_{d−1}, …, f_{0}) ≠ 0 (this means that F has only simple roots)

3. the polynomial F has only real roots

4. there exists a real number t_{0} with t_{0}^{2} ≠ 4 such that

(−1)^{d}4f_{0} = t_{0}^{2}
and (−1)^{d}F (X)F (−X)(X^{2} − 4) = (X^{2} − t_{o}^{2})F (X^{2}) holds.

Proof. Putting t_{0} := 2^{2^{d}} one easily checks that the polynomial F_{d} satisfies the four conditions of the lemma. Therefore it is sufficient to show that there exists at most one monic polynomial F = X^{d} + f_{d−1}X^{d−1} + ⋯ + f_{0} ∈ IR[X] of degree d which satisfies the conditions. Suppose now that such a polynomial F is given and fix a real number t_{0} which satisfies the fourth condition with respect to this F . This condition implies that for any root x of F either x^{2} = t_{0}^{2} or F (x^{2}) = 0 holds. Thus for any root x of F one of the following two cases may occur:

(i) there exists a natural number k with x^{2^{k}} = t_{0}^{2} , or

(ii) any element of the set S(x) := {x^{2^{m}} : m ∈ IN} is a root of F .

In case (ii) our assumptions on F imply that the set S(x) is infinite. This rules out this case since F is monic. Therefore any root x of F satisfies (i). One easily sees F (4) = 0 . Let r be a maximal nonnegative integer such that 2^{2}, 2^{2^{2}}, …, 2^{2^{r}} are roots of F . From F (4) = 0 and degF = d one concludes 1 ≤ r ≤ d. The maximality of r implies F (2^{2^{r+1}}) ≠ 0 whence 2^{2^{r+1}} = t_{0}^{2} = (−1)^{d}4f_{0} . Thus we have | t_{0} |> 1 .

We are now going to show that r = d holds. Suppose that this is not the case. Since by assumption F has only simple roots which are all real there must exist d − r distinct real zeroes x_{r+1}, …, x_{d} of F not contained in the set {2^{2}, 2^{2^{2}}, …, 2^{2^{r}}}. Thus the roots of F are the real numbers 2^{2}, 2^{2^{2}}, …, 2^{2^{r}}, x_{r+1}, …, x_{d}. This implies

2^{2^{r+1}} = (−1)^{d}4f_{0} = 4 · 2^{2} · 2^{2^{2}} ⋯ 2^{2^{r}} · x_{r+1} ⋯ x_{d}

and consequently x_{r+1} ⋯ x_{d} = 1 . Let r < m ≤ d. Since the root x_{m} of F satisfies (i) there exists a natural number k_{m} such that x_{m}^{2^{km}} = t_{0}^{2} holds. Thus as | t_{0} |> 1 we have | x_{m} |> 1 for any r < m ≤ d. But this contradicts our conclusion x_{r+1} ⋯ x_{d} = 1 . That finishes the proof of the assertion r = d, saying that 2^{2}, 2^{2^{2}}, …, 2^{2^{d}} are all roots of the monic polynomial F of degree d. With other words we have

F = ∏_{1≤j≤d}(X − 2^{2^{j}})) = F_{d}.

□

Let n be a natural number and let X_{1}, …, X_{n} indeterminates over ZZ . A subset S of IR^{n} is called semialgebraic if there exists a finite set of polynomials G ∈ ZZ[X_{1}, …, X_{n}] such that S is definable as a boolean expression built up from atomic formulas of type G = 0 or G > 0 with G ∈ G. In this case we shall also say that S is G -definable semialgebraic. A semialgebraic set has only finitely many connected components which are in turn semialgebraic (for more details see Bochnak et al. 1987). In the sequel we shall use the following estimate which can be found in Vorobjov (1984) (compare also Heintz et al. 1990, Theorem 4):

Proposition 4.8. There exists a universal constant c_{0} > 0 with the following property: Let n, D, s, h be natural numbers and let G be a set of s polynomials of ZZ[X_{1}, …, X_{n}] having degree at most D and logarithmic height at most h, which defines a semialgebraic subset S of IR^{n}. Then the ball of IR^{n} of radius 2^{(sD)^{c_{0}n}·h} centered at the origin intersects with every connected component of S at least in one point.

We are now ready to prove that the family F_{5} is hard to compute in the sense of time-space tradeoff if we restrict ourselves to the field of parameters K := IR (see Subsection 2.2):

Proposition 4.9. There exists a universal constant c > 0 with the following property: Let d, L, S be natural numbers and let

F := ∏_{1≤j≤d}(X − 2^{2^{j}}).

Let γ be a straight–line program in IR(X) which computes the polynomial F using nonscalar time L and space S. Then we have

LS^{2} ≥ c\frac{d}{log_{2} d}.

Proof. Let us write F = f_{d}X^{d}+f_{d−1}X^{d−1}+⋯+f_{0} with (f_{d}, …, f_{0}) ∈ ZZ^{d+1} and f_{d} = 1 . Observe that F and (f_{d−1}, …, f_{0}) satisfy the four conditions of Lemma 4.7. We apply now Lemma 2.5 with K := IR . Following this result and its proof, there exist for N := 8LS^{2} + 1 polynomials P_{d}, …, P_{0} ∈ ZZ[Z_{1}, …, Z_{N}] of degree at most 2(Ld + 1) and weight at most (d + 1)!(4(S + 1))^{(d+1)^{L+1}} such that the morphism of affine spaces Φ_{d,L,S} : IR^{N} → IR^{d+1} introduced in this lemma maps the parameters of the straight–line program γ on (f_{d}, …, f_{0}) ∈ ZZ^{d+1} . Let (ζ_{1}, …, ζ_{N}) be the point of IR^{N} representing the parameters of γ, let Φ := Φ_{d,L,S} and let V := Φ^{−1}((f_{d}, …, f_{0})) be the Φ -fiber of the integer point (f_{d}, …, f_{0}) . Since (ζ_{1}, …, ζ_{N}) is contained in V , we conclude that V is nonempty. One verifies immediately that V is a semialgebraic subset of IR^{N}. Let T, U_{1}, U_{2}, U_{3}, U_{4}, U_{5} be new indeterminates. Using the notation of Lemma 4.7 we consider the following polynomial equation system: P_{d} − 1 = 0 P_{0}U_{1} − 1 = 0 (∑_{0≤j≤d} P_{j})U_{2} − 1 = 0 (∑_{0≤j≤d} P_{j}(−1)^{j})U_{3} − 1 = 0 D(P_{d−1}, …, P_{0})U_{4} − 1 = 0 (T^{2} − 4)U_{5} − 1 = 0 (−1)^{d}4P_{0} − T^{2} = 0 (−1)^{d}R(k)R(−k)(k^{2} − 4) = (k^{2} − T^{2})R(k^{2}) for 0 ≤ k ≤ 2d with R := P_{d}X^{d}+⋯+P_{0} . Observe that the polynomials occuring in the above system belong to the ring ZZ[Z_{1}, …, Z_{N}, T, U_{1}, U_{2}, U_{3}, U_{4}, U_{5}] having degree at most D := c′Ld^{3} and logarithmic height at most h := c′(d + 1)^{L+2}(2 + log S) for a suitable universal constant c′ > 0 and that there are at most s := c′d of them. These polynomials codify the four conditions of Lemma 4.7. They define a semialgebraic subset W of IR^{N} × IR^{6} . Let π : IR^{N} × IR^{6} → IR^{N} be the canonical projection which maps each point of IR^{N} × IR^{6} onto its first N components. From Lemma 4.7 and 2.5 one deduces easily that π(W) = V holds. In particular W is nonempty. Applying Proposition 4.8 we see that W contains a point ω := (θ_{1}, …, θ_{N}, t, u_{1}, u_{2}, u_{3}, u_{4}, u_{5}) ∈ IR^{N} × IR^{6} with

|| ω ||:= (θ_{1}^{2} + ⋯ + θ_{N}^{2} + t^{2} + u_{1}^{2} + u_{2}^{2} + u_{3}^{2} + u_{4}^{2} + u_{5}^{2})^{\frac{1}{2}} ≤ 2^{(sD)^{c_{0}(N+6)·h}}

where c_{0} > 0 is the universal constant of this proposition. This implies that the semialgebraic set contains a point θ := ((θ_{1}, …, θ_{N}) ∈ IR^{N}, namely θ = π(ω) , which satisfies

log_{2} | θ |= log_{2} max{| θ_{i} |: 1 ≤ i ≤ N} ≤ (sD)^{c_{0}(N+6)·h}.

Without loss of generality we may suppose L ≤ d. Therefore, taking into account N = 8LS^{2} +1, s = c′d, D = c′Ld^{3} and h = c′(d+1)^{(L+2)}(2+log S) we conclude that there exists a universal constant c′′ > 0 such that the estimate log_{2} | θ |≤ d^{c′′LS^{2}} holds. Since the point θ belongs to the Φ -fiber V of (f_{d}, …, f_{0}) we have (−1)^{d}2^{2^{d+1}−2} = (−1)^{d} ∏_{1≤j≤d} 2^{2^{j}} = f_{0} = P_{0}(θ) . Reasoning as in the proof of the tradeoff lower bound of Example 4.1 we obtain the following inequalities: 2^{d+1} − 2 = log_{2} | f_{0} |≤ log_{2} weight(P_{0}) + degP_{0} · log_{2} | θ |≤ (d + 1) log_{2}(d + 1) + (d + 1)^{L+1}(2 + log_{2}(S + 1)) + 2(Ld + 1)d^{c′′LS^{2}} . Taking logarithms in these inequalities we deduce from L ≤ d that there exists a universal constant c > 0 such that

LS^{2} ≥ c\frac{d}{log_{2} d} holds.

□

Example 4.10. Let as before F_{5} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ ZZ[X] of degree d defined by

F_{d} := ∏_{1≤j≤d}(X − 2^{2^{j}}).

Then this family F_{6} is hard to compute in the sense of time-space tradeoff. More precisely we have

LS^{2}(F_{d}) = Ω(\frac{d}{log_{2} d}).

Proof. The lower bound we claim in this example refers to straight–line programs in C(X) and not in IR(X) as in Proposition 4.9. Howeverone deduces this lower bound easily from that proposition: it is sufficient to observe that any straight–line program β in C(X) which computes for given d ∈ IN the polynomial F_{d}, can be transformed into a straight–line program γ which evaluates F_{d} in nonscalar time 5L(β) and space 4S(β) using only real parameters. One obtains this straight–line program γ by computing the real and imaginary part of each intermediate result of β separately (note that in view of Lickteig & Werther 1996 our time and space estimates for γ are even rather coarse). Our claim then follows easily from Proposition 4.9. □

We consider now a second example of a family of polynomials given by their roots which is hard to compute in the sense of time-space tradeoff. The polynomials of this second family will have algebraic coefficients. A similar example was analyzed in Heintz & Morgenstern (1993) from the point of view of sequential time complexity.

Example 4.11. Let F_{6} := (F_{d})_{d∈IN} be the family of polynomials F_{d} ∈ ZZ[X] of degree d defined by

F_{d} := ∏_{1≤j≤d}(X − \sqrt{p_{j}}),

where p_{j} denotes the j -th prime number. Then this family F_{6} is hard to compute in the sense of time-space tradeoff. More precisely we have

LS^{2}(F_{d}) = Ω(\frac{d}{log_{2} d}).

Proof. The lower bound we claim follows by adapting an argument first introduced in Baur (1996) to the context of time-space tradoffs. Let d ∈ IN be given and let F := F_{d}. For 1 ≤ j ≤ d we write σ_{j} for the j -th elementary function in d arguments and f_{j} := σ_{j}(\sqrt{p_{1}}, …, \sqrt{p_{d}}) for its value in the point (\sqrt{p_{1}}, …, \sqrt{p_{d}}) ∈ IR^{d}. We have

F = ∏_{1≤j≤d}(X − \sqrt{p_{j}}) = X^{d} − f_{1}X^{d−1} + ⋯ + (−1)^{d}f_{d}

for suitable real algebraic numbers f_{1}, …, f_{d}. Let X_{1}, …, X_{d} and Y_{1}, …, Y_{d} be new indeterminates and let 1 ≤ j ≤ d. The polynomial N_{j} := X_{1}^{2j+1} + ⋯ + X_{d}^{2j+1} is symmetric and therefore exists a (unique) polynomial Q_{j} ∈ ZZ[Y_{1}, …, Y_{d}] of degree at most 2j + 1 such that

N_{j}(X_{1}, …, X_{d}) = Q_{j}(σ_{1}(X_{1}, …, X_{d}), …, σ_{d}(X_{1}, …, X_{d}))

holds (see e.g. van der Waerden 1960). Let b_{j} be the real value

b_{j} := Q_{j}(f_{1}, …, f_{d}).

One verifies immediately that

b_{j} = N_{j}(\sqrt{p_{1}}, …, \sqrt{p_{d}}) = p_{1}^{j}\sqrt{p_{1}} + ⋯ + p_{d}^{j}\sqrt{p_{d}}

holds. Thus the values b_{1}, …, b_{d} can be written as ZZ -linear combinations of the values \sqrt{p_{1}}, …, \sqrt{p_{d}}. The corresponding matrix is the nonsingular Vandermonde matrix (p_{k}^{j})_{1≤j,k≤d}. This implies that there exist 0 Q -linear forms H_{1}, …, H_{d} in d arguments such that \sqrt{p_{j}} = H_{j}(b_{1}, …, b_{d}) holds for 1 ≤ j ≤ d. For any set S ⊂ {1, …, d} consider the polynomial

g_{S} := ∏_{j∈S} H_{j}(Q_{1}(Y_{1}, …, Y_{d}), …, Q_{d}(Y_{1}, …, Y_{d})).

Observe that degg_{S} ≤ d(2d + 1) and

g_{S}(f_{1}, …, f_{d}) = ∏_{j∈S} \sqrt{p_{j}}

holds. Thus

(g_{S}(f_{1}, …, f_{d}) : S ⊂ {1, …, d})

forms a family of 2^{d} real values which are 0 Q -linear independent. The lower bound for the time-space tradeoff of the family F_{6} follows now easily from Proposition 4.3 setting m := 2^{d} and D := d(2d + 1) . □

4.3. Space lower bounds for time optimal evaluation.

From Horner’s rule follows that any univariate polynomial can be computed in constant space (see in this context also Ben-Or & Cleve 1992). Therefore space can be arbitrary small in polynomial evaluation if time is free. However, restricting ourselves to time optimal procedures we obtain as an immediate consequence of our tradeoff results the following statement concerning space lower bounds (compare also Corollary 2.8):

Proposition 4.12. Let 1 ≤ i ≤ 6 and let F_{i} := (F_{d}^{(i)})_{d∈IN} be any of the families of polynomials F_{d}^{(i)} ∈ C[X] introduced in the Examples 4.1, 4.2, 4.5, 4.11, 4.10. Then there exists a universal constant c > 0 with the following property: For any sequence (β_{d})_{d∈IN} of arithmetic circuits in C(X) such that β_{d} evaluates the polynomial F_{d}^{(i)} in nonscalar time L(β_{d}) ≤ \sqrt{d} the space S(β_{d}) used by β_{d} satisfies the lower bound

S(β_{d}) ≥ c · \begin{matrix}^{4} & \sqrt{d} \\ √ & \overline{log_{2} d} \end{matrix}.

For the case of the family F_{1} this bound can be even improved to

S(β_{d}) ≥ c · \sqrt[4]{d}.

Acknowledgements

Research was partially supported by the following Spanish grants: DGICT PB92–0498–C02–01 and PB93–0472–C02–02, “Desarrollo e implementación de la estructura de datos SLP”, Gobierno Foral de Navarra, 1996. Thanks go also to Klemens Hägele, Universidad de Cantabria, for his language corrections of a first draft of this paper.

References

K. R. Abrahamson, Time–Space tradeoffs for algebraic problems on general sequential machines. J. Comput. System Sci. 43, 1991, 269–289. W. Baur, Simplified lower bounds for polynomials with algebraic coefficients. To appear in J. Complexity, 1996. P. Beame, A general sequential time–space tradeoff for finding unique elements. In Proc. Twenty–first Ann. ACM Symp. Theor. Comput., 1989, 197–203.

Algebraic Time–Space Tradeoffs  47

M. Ben-Or and R. Cleve, Computing algebraic formulas using a constant number of registers, SIAM J. Comput. 21(1), 1992, 54-58. C. Berenstein and A. Yger, Effective Bézout identities in 0 Q[X_{1}, …, X_{n}] . Acta Math. 166, 1991, 69–120. C. Berenstein and A. Yger, Une formule de Jacobi et ses conséquences. In Ann. Sci. E.N.S., 4 ième série 24, 1991, 363–377. C. Berenstein and A. Yger, Green currents and analytic continuation. Preprint, Univ. of Maryland, 1995. J. Bochnak, M. Coste and M.-F. Roy, Géométrie algébrique réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete, 3. Folge, Band 12, Springer Verlag, 1987. A. Borodin, Time–space tradeoffs (getting closer to the barrier?). In Algorithms and Computation, Proc. of the 4th ACM–SIGSAM Int. Symp. ISAAC’93, ed. K.W. Ny et al., Lecture Notes in Computer Science 762, Springer Verlag (1993) 209–220. A. Borodin and S. Cook, A time–space tradeoff for sorting on a general sequential model of computation. SIAM J. Comput. 11, 1982, 287–297. A. Borodin, M. J. Fischer, D. J. Kirkpatrick, N. A. Lynch and M. Tompa, A time–space tradeoff for sorting on non–oblivious machines. J. Comput. System Sci. 22, No. 3, 1981, 351–364. A. Borodin, M. J. Fischer, F. Meyer auf der Heide, E. Upfal and A. Wigderson, A time–space tradeoff for element distinctness. SIAM J. Comput. 16, No. 1, 1987, 97–99. A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems. American Elsevier, New York, 1975. D. W. Brownawell, Bounds for the degree in the Nullstellensatz. Ann. Math. 126, 1987, 577–591. P. Bürgisser, M. Clausen and A. Shokrollahi, Algebraic Complexity Theory. Ergebnisse der Mathematik und ihrer Grenzgebiete. Springer Verlag, 1996. L. Caniglia, A. Galligo and J. Heintz, Borne simplement exponentielle pour les degrés dans le théorème des zéros sur un corps de caractéristique quelconque. C.R. Acad. Sci. Paris, Série I, Math. 307, 1988, 255–258. L. Caniglia, A. Galligo and J. Heintz, Some new effectivity bounds in computational geometry. In Proc. AAECC–6, ed. T. Mora, Lecture Notes in Computer Science 357, Springer Verlag, 1989, 131–152. K. Chandrasekharan, Introduction to analytic number theory, Grundlehren der Math. Wissenschaften, Springer Verlag, 1968. P. Duris and Z. Galil, A time–space tradeoff for language recognition. In Proc. 22nd Ann. IEEE Symp. Found. Comput. Sci., 1981, 53–57. N. Fitchas and A. Galligo, Nullstellensatz effective et conjecture de Serre (théo-

48  Aldaz et al.

rème de Quillen–Suslin) pour le calcul formel. Math. Nachrichten 149, 1990, 231– 253. N. Fitchas, M. Giusti and G. Smietanski, Sur la complexité du théoreme des zéros. In Approximation and Optimization 8, ed. J. Guddat et al., Peter Lange Verlag, Frankfurt am Main, 1995, 274–329. W. Fulton, Intersection theory. Ergebnisse der Mathematik und ihrer Grenzgebiete, 3. Folge, Band 2, Springer Verlag, 1984. J. von zur Gathen, Parallel arithmetic computations: a survey. In Proc. 12th Int. Symp. Math. Found. on Comp. Sci., Bratislava, Lecture Notes in Computer Science 233, Springer Verlag, 1986, 93–112. J. von zur Gathen, Parallel linear algebra. In Synthesis of Parallel Algorithms, Chapter 8, Morgan Kauffmann Publishers, 1993, 573–617. J. von zur Gathen and V. Strassen, Some polynomials that are hard to compute. Theoret. Comput. Sci. 11, No. 3 , 1981, 159–171. M. Giusti, J. Heintz, J. E. Morais and L. M. Pardo, When polynomial equation systems can be ’solved’ fast?. In Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, Proc. AAECC–11, eds. G. Cohen, M. Giusti and T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 205–231. M. Giusti, J. Heintz, J. E. Morais, J. Morgenstern and L. M. Pardo, Straight–line programs in geometric elimination theory. To appear in J. of Pure and App. Algebra, 1996. M. Giusti, K. Hägele, J. Heintz, J. L. Montaña, J. E. Morais and L. M. Pardo, Lower Bounds for Diophantine Approximation. To appear in J. of Pure and App. Algebra, 1997. D. Grigor’ev, An application of separability and independence notions for proving lower bounds of circuit complexity. Notes of Scientific Seminars 60, Leningrad Departament, Steklov Mathematical Institute, 1976, 36–48 (in Russian). J. Heintz, Fast quantifier elimination over algebraically closed fields. Theoret. Comput. Sci. 24, 1983, 239–277. J. Heintz, On the computational complexity of polynomials and bilinear mappings. In Proc. AAECC–5, eds. L. Huguet and A. Poli. Lecture Notes in Computer Science 356, Springer Verlag, 1989, 269–300. J. Heintz and J. Morgenstern, On the intrinsic complexity of elimination theory. J. of Complexity 9, 1993, 471–498. J. Heintz, M. F. Roy and P. Solerno, Sur la complexité du principe de Tarski– Seidenberg. Bull. Soc. math. France 118, 1990, 101–126. J. Heintz and C. P. Schnorr, Testing polynomials which are easy to compute. Proc. Twelfth Ann. ACM Symp. Theor. Comput., 1980, 262–268; also in Logic and Algorithmic. An International Symposium held in Honour of Ernst Specker, Monographie No. 30 de l’Enseignement de Mathématiques, Genève, 1982, 237–254. J. Heintz and M. Sieveking, Lower bounds for polynomials with algebraic coefficients. Theoret. Comput Sci. 11, 1980, 321–330. J. Ja’Ja’, Time–space tradeoffs for some algebraic problems. J. Assoc. Comput. Mach. 30, No. 3, 1983, 657–667. J. Kollár, Sharp Effective Nullstellensatz. J. Amer. Math. Soc. 1, 1988, 963–975. T. Krick and L. M. Pardo, Une approche informatique pour l’approximation diophantienne. C. R. Acad. Sci. Paris 318, Série I, no. 5, 1994, 407–412. T. Krick and L. M. Pardo, A Computational Method for Diophantine Approximation. In Algorithms in Algebraic Geometry and Applications, Proc. MEGA’94, eds. L. Gonzalez–Vega and T. Recio. Progress in Mathematics 143, Birkhäuser Verlag, 1996, 193–254. T. Krick, J. Sabia and P. Solernó, On Intrinsic Bounds in the Nullstellensatz. To appear in Appl. Alg. Eng. Comm. Comp., 1996 . T. Lengauer and R. E. Tarjan, Upper and lower bounds on time–space tradeoffs. In Proc. Eleventh Ann. ACM Symp. Theor. Comput., 1979, 262–277. T. Lickteig, Semi–algebraic decision complexity. Tech. Rep. TR-90-052 Int. Comp. Science Inst., Berkeley, 1990, and Univ. Tübingen, Habilitatiosschrift. T. Lickteig and K. Werther, How to compute a complex square root optimally?. Computational Complexity, 1996. C. Michaux, Une remarque à propos des machines sur IR introduites par Blum, Shub et Smale. C. R. Acad. Sci. Paris 309, Série I, 1989, 435–437. J. L. Montaña and L. M. Pardo, Lower bounds for Arithmetic Networks. Appl. Alg. Eng. Comm. Comp. 4, No. 1, 1993, 1–24. J. L. Montaña, J. E. Morais, L. M. Pardo, Lower Bounds for Arithmetic Networks II: Sum of Betti numbers. Appl. Alg. Eng. Comm. and Comp., 7, No. 1, 1996, 41–51. L. M. Pardo, How Lower and Upper Complexity Bounds meet in Elimination Theory. In Applied Algebra, Algebraic Algorithms and Error–Correcting Codes, Proc. AAECC–11, eds. G. Cohen, M.Giusti and T. Mora. Lecture Notes in Computer Science 948, Springer Verlag, 1995, 33–69. M. S. Paterson and L. J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials. SIAM J. Comput. 2, 1973, 80–96. W. J. Paul and R. E. Tarjan, Time–space tradeoffs in a pebble game. Acta Inform. 10, 1978, 111–115. N. Pippenger, A time–space tradeoff. J. Assoc. Comput. Mach. 25, 1978, 509–515. N. Pippenger, Pebbling. In Proc. 5th IBM Symp. on Math. Found. of Comput. Sci., 1980.

50  Aldaz et al.

P. Philippon, Théorème des zéros effective, d’après J. Kollar. Pub. Math. de l’Univ. P. et M. Curie, Paris VI, 88, Groupe d’étude sur les Problémes diophantiens 1988–1989, exposé 6. J. E. Savage, Space–time trade–offs – A survey. In Proc. 3rd Hungarian Comput. Sci. Conf., 1981. J. E. Savage, Space–time tradeoffs for banded matrix problems. J. Assoc. Comput. Mach. 31, No. 4, 1984, 422–437. J. E. Savage and S. Swamy, Space–time tradeoffs on the FFT algorithm. IEEE Trans. Inform. Theory 24, 1978, 563–568. J. E. Savage and S. Swamy, Space–time tradeoffs for oblivious integer multiplication. In Lecture Notes in Computer Science 71, Springer Verlag, 1979, 240–251. C.P. Schnorr, Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials. Theoret. Comput. Sci. 7, 1978, 251–261. I. R. Shafarevich, Basic Algebraic Geometry: Varieties in projective space. Springer Verlag, 1994. M. Sombra, Bounds for the Hilbert function of polynomial ideals and for the degrees in the Nullstellensatz. To appear in J. Pure Appl. Algebra, 1997. H. J. Stoss, On the representation of rational functions of bounded complexity. Theoret. Comput. Sci. 64, 1989a, 1–13. H. J. Stoss, Lower bounds for the complexity of polynomials. Theoret. Comput. Sci. 64, 1989b, 15–23. V. Strassen, Vermeidung von Divisionen. J. Reine Angew. Math. 264, 1973, 184–202. V. Strassen, Polynomials with rational coefficients which are hard to compute. SIAM J. Comput. 3, 1974, 128–149. V. Strassen, Algebraic Complexity Theory. In Handbook of Theoret. Comput. Sci., ch. 11, Elsevier, 1990, 634–671. M. Tompa, Time–space tradeoffs for computing functions, using conectivity properties of their circuits. J. Comput. System Sci. 20, 1980, 118–132. M. Tompa, Two Familiar Transitive Closure Algorithms which Admit no Polynomial Time, Sublinear Space Implementations. SIAM J. Comput. 11, No. 1, 1982, 130– 137. P. M. Vaidya, Space–time tradeoffs for orthogonal range queries. In Proc. Seventeenth Ann. ACM Symp. Theor. Comput. , 1985, 169–174. N. Vorobjov, Bounds of real roots of a system of algebraic equations. Notes of Scientific Seminars 137, Leningrad Departament, Steklov Mathematical Institute, 1984, 7–19.

B.L. van der Waerden, Algebra I, 5. Auflage der Modernen Algebra, Springer Verlag, 1960. A. C. C. Yao, Space–time tradeoff for answering range queries. In Proc. Fourteenth Ann. ACM Symp. Theor. Comput., 1982, 128–136. A. C. C. Yao, Near optimal time–space tradeoff for element distinctness. In Proc. 29th Ann. IEEE Symp. Found. Comput. Sci., 1988, 91–97. Y. Yesha, Time–space tradeoffs for matrix multiplication and the discrete Fourier transformation on any general sequential random acces computer. J. Comput. System Sci. 29, 1984, 183–197.

Manuscript received 11 December 1996

Mikel Aldaz Dpto. de Matemática e Informática Universidad Pública de Navarra Campus de Arrosadía E-31006 PAMPLONA, Spain

mikaldaz@upna.es

J. Heintz

Depto. de Matemáticas, Est. y Comp. Facultad de Ciencias Universidad de Cantabria E-39071 SANTANDER, Spain

                                     heintz@matsun1.matesco.unican.es

Guillermo Matera Depto. de Matemáticas FCEyN, Universidad de Buenos Aires Ciudad Universitaria, Pab. I (1428) BUENOS AIRES, Argentina

gmatera@dm.uba.ar

José L. Montaña

Dpto. de Matemática e Informática Universidad Pública de Navarra Campus de Arrosadía E-31006 PAMPLONA, Spain

                                     pepe@upna.es

Luis M. Pardo Depto. de Matemáticas, Est. y Comp. Facultad de Ciencias Universidad de Cantabria E-39071 SANTANDER, Spain

pardo@matsun1.matesco.unican.es