A new method to obtain lower bounds for polynomial evaluation ⋆

M. Aldaz^{a,1}, G. Matera^{b,c,2}, J.L. Montaña^{a,1}, and
L.M. Pardo^{d,3}

aUniversidad Pública de Navarra, Departamento de Matemática e Informática,

31006 Pamplona, Spain

                    {mikaldaz, pepe}@unavarra.es

bUniversidad Favaloro, Laboratorio de Computación, Solis 453 (1078) Buenos Aires, Argentina

                       gmatera@favaloro.edu.ar

cUniversidad Nacional de Gral. Sarmiento, Instituto de Desarrollo Humano,

Roca 850 (1663) San Miguel, Argentina

                         gmatera@ungs.edu.ar

dUniversidad de Cantabria, Fac. de Ciencias, Depto. de Matemáticas, Estadística

y Computación, 39071 Santander, Spain

                    pardo@hall.matesco.unican.es

Abstract

We present a new method to obtain lower bounds for the time complexity of polynomial evaluation procedures. Time, denoted by L, is measured in terms of nonscalar arithmetic operations. In contrast with known methods for proving lower complexity bounds, our method is purely combinatorial and does not require powerful tools from algebraic or diophantine geometry.

By means of our method we are able to verify the computational hardness of new natural families of univariate polynomials for which this was impossible up to now. By computational hardness we mean that the complexity function L^{2} grows linearly in the degree of the polynomials of the family we are considering.

Our method can also be applied to classical questions of transcendence proofs in number theory and geometry. A list of (old and new) formal power series is given whose transcendence can be shown easily by our method.

Key words: Algebraic Complexity; Straight-line program complexity; Complexity of polynomial evaluation; Transcendence criterion.

Preprint submitted to Elsevier Preprint 10 December 1999

1 Introduction

The study of complexity issues for straight-line programs evaluating univariate polynomials is a standard subject in theoretical computer science. One of the most fundamental tasks in this domain is the exhibition of explicit families of univariate polynomials which are “hard to compute” in the given context. Following Motzkin [18], Belaga [3] and Paterson–Stockmeyer [20] “almost all” univariate polynomials of degree d need for their evaluation at least Ω(d) additions/subtractions, Ω(d) scalar multiplications/divisions, and Ω(\sqrt{d}) nonscalar multiplications/divisions. A family (F_{d})_{d∈ℕ} of univariate polynomials F_{d} satisfying the condition deg F_{d} = d is called hard to compute in a given complexity model if there exists a positive constant c such that any straightline program evaluating the polynomial F_{d} requires the execution of at least Ω(d^{c}) arithmetic operations in the given model.

In the present contribution we shall restrict ourselves to the nonscalar complexity model. This model is well suited for lower bound considerations and does not represent any limitation for the generality of our statements.

Families of specific polynomials which are hard to compute were first considered by Strassen in [25]. The method used by Strassen was later refined by Schnorr [22] and Stoss [24]. In [14], Heintz and Sieveking introduced a considerably more adaptive method which allowed the exhibition of quite larger classes of specific polynomials which are hard to compute. However in its beginning the application of this new method was restricted to polynomials with algebraic coefficients. In [13], Heintz and Morgenstern adapted the method of Heintz–Sieveking to polynomials given by their algebraic roots and this adaptation was considerably simplified in [2].

Finally the methods of Strassen [25] and Heintz–Sieveking [14] were unified to a common approach by Aldaz et alii in [1]. This new approach was based on effective elimination and intersection theory with their implications for diophantine geometry (see e.g. [8,15,21]). This method allowed for the first time applications to polynomials having only integer roots.

The results of the present contribution are based on a new, considerably sim-

⋆ An extended abstract of this paper appeared in the Proceedings of the 23rd Symposium on the Mathematical Foundations of Computer Science, Springer Lecture Notes in Computer Science 1450 (1998) pp. 167–175. 1 Partially supported by Gobierno de Navarra under project “Complejidad y Estructuras de Datos en Cálculo Simbólico”, Spain. 2 Partially supported by UBA–CYT TW80, PIP CONICET 4571 and ANPCYT PICT 03–00000–01593, Argentina. 3 Partially supported by DGCYT PB 96–0671–C02–02, Spain.

plified version of the unified approach mentioned before. Geometric considerations are replaced by simple counting arguments which make our new method more Ωexible and adaptive (see Lemma 4). The new method is inspired in [23] and [2] and relies on a counting technique developed in [25] (see also [22,24]). Except for this result (Theorem 2) the method is elementary and requires only basic knowledge of algebra.

Our new method yields a simple criterion (Theorem 6) to establish computational hardness results for several new families of polynomials given either by their integer coefficients or by their integer roots (see Theorems 10, 11 and 12). The method also implies some known results for polynomials with algebraic coefficients (see Theorems 7 and 8).

Our method can also be applied to establish transcendence proofs for power series. Using Newton’s method to approximate algebraic functions we obtain a simple criterion of transcendence (see Theorem 13 and Criterion 14). Several (old and new) power series are given whose transcendence can be shown easily by our method (see Corollary 15).

Let us finally remark that our method does not apply to polynomials having “small” integer roots such as the Pochhammer–Wilkinson polynomials. Some result in this direction would be of great interest because of their relationship with other subjects of theoretical computer science. Connections with boolean complexity problems can be found in [13] where the complexity of evaluation of the Pochhammer–Wilkinson polynomials is related with the complexity of a geometric elimination problem, and also in [17] where the complexity of evaluating polynomials with many different rational roots is related with the complexity of integer factorization. In [4, Chapter 7] the hypothesis that the multiples of the Pochhammer–Wilkinson polynomials are hard to compute is used to show that P ≠ NP holds for computations over algebraically closed fields of characteristic zero.

2 Straight-line Programs and Representation Theorem

Let K be an algebraically closed field of characteristic zero. By K[X] we denote the ring of univariate polynomials in the indeterminate X over K and by K(X) its fraction field. Let α be a point of K. By K[[X − α]] we denote the ring of formal power series in X − α with coefficients in K and by O_{α} the localization of K[X] by the maximal ideal generated by the linear polynomial X − α. This means that O_{α} is the subring of K(X) given by the rational functions F := f/g, with f, g ∈ K[X] and g(α) ≠ 0.

Since K has characteristic zero for every α ∈ K there exists a natural embedding i_{α} from O_{α} into K[[X − α]] defined as follows: for any F ∈ O_{α}, let i_{α}(F) be the Taylor expansion of F at the point α, namely

i_{α}(F) := ∑_{j∈ℕ} \frac{F^{(j)}(α)}{j!} · (X − α)^{j} .

Here we denote by F^{(j)}, j ∈ ℕ, the j-th derivative of the rational function F.

Let A be one of the following K-algebras: K[X], K(X) or O_{α}, where α ∈ K. We recall the following standard notion of algebraic complexity theory (see [6,10,12,24,26,19] and [7, Chapter 4]).

Definition 1 Let L be a natural number. A straight-line program of nonscalar length L in A is a sequence β of elements of A, namely β := (Q_{−1}, Q_{0}, …, Q_{L}), satisfying the following conditions:

• Q_{−1} := 1.

• Q_{0} := X.

• For any ρ, 1 ≤ ρ ≤ L, there exist d_{ρ} ∈ {0, 1} and a_{ρ,j}, b_{ρ,j} ∈ K, with −1 ≤ j < ρ, such that

Q_{ρ} := ( ∑_{−1≤j<ρ} a_{ρ,j} ·Q_{j})·((1−d_{ρ})·( ∑_{−1≤j<ρ} b_{ρ,j} ·Q_{j})+d_{ρ}·( ∑_{−1≤j<ρ} b_{ρ,j} ·Q_{j})^{−1})

holds.

Let F be an arbitrary element of the K-algebra A. We say that the straightline program β = (Q_{−1}, Q_{0}, …, Q_{L}) computes F if there exist field elements c_{l} ∈ K, with −1 ≤ l ≤ L, such that the following identity holds:

F = ∑_{−1≤l≤L} c_{l} · Q_{l} .

The nonscalar complexity L_{A}(F) of an element F of the K-algebra A is defined as

L_{A}(F) := min {nonscalar length of β : β in A that computes F } .

Now let F be a rational function belonging to the K-algebra O_{α}. Suppose that F is given by a straight-line program β in O_{α}. We are going to analyze how F depends on the parameters of the straight-line program β. To this end we use an idea going back to [25] (see also [22,24]). The following analysis of the rational function F represents the main technical tool we use in this paper. A detailed proof of a similar result can be found in [7, Chapter 9, Theorem 9.9, pp. 212–215].

Let us first recall that the height of a given polynomial with integer coefficients is the maximum of the absolute values of its coefficients and the weight is the sum of the absolute values of these coefficients. Note that the weight is subadditive and submultiplicative.

Theorem 2 (Representation theorem for rational functions) Let L be a natural number and N := (L+1)(L+2). Then there exists a family (P_{L,j})_{j∈ℕ} of polynomials P_{L,j} ∈ ℤ[Z_{1}, …, Z_{N}] with

deg P_{L,j} ≤ j(2L − 1) + 2 (1)

and

weight P_{L,j} ≤ 2^{3((j+1)^{L}−1)} (2)

such that for any α ∈ K and any F ∈ O_{α} with L_{O_{α}}(F) ≤ L there exists a point z_{F} ∈ K^{N} satisfying the identity

i_{α}(F) = ∑_{j∈ℕ}P_{L,j}(z_{F}) · (X − α)^{j} .

Following [14] for given natural numbers d and L let

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

be the morphism of affine spaces defined by Φ_{d,L}(z) := (P_{L,0}(z), …, P_{L,d}(z)) for arbitrary z ∈ K^{N}. Let W_{d,L} := \overline{im Φ_{d,L}} ⊆ K^{d+1} be the Zariski closure over ℚ of the image im Φ_{d,L} of the morphism Φ_{d,L}.

In the sequel we shall identify any polynomial ∑_{0≤j≤d} f_{j}X^{j} ∈ K[X] of degree d with its coefficient vector (f_{0}, …, f_{d}) which we consider as a point of the affine space K^{d+1}.

3 Combinatorial Method

This Section is devoted to present the main results of this paper. In order to state our technical lemma (namely Lemma 4 below) we need the following notion and notation.

Definition 3 Let n be a given natural number. For fixed d ∈ ℕ we define a map

μ : K^{d+1} ⟶ ℕ

which is given in the following way: for any point F := (f_{0}, …, f_{d}) belonging to K^{d+1} let

μ(F; n) := # { ∑_{S⊆{0,...,d}} θ_{S} ∏_{j∈S} f_{j}^{v_{j}}: 1 ≤ v_{j} ≤ n, 0 ≤ j ≤ d, θ_{S} ∈ {0, 1}} .

For n = 1 we write simply

μ(F) := μ(F; 1) .

Lemma 4 (Main Lemma) Let d, L and n be given nonzero natural numbers. Then for any point F belonging to the algebraic variety W_{d,L} ⊆ K^{d+1} we have

μ(F; n) ≤ 2^{(n(d+1))^{20L^{2}}} . (3)

PROOF. First of all observe that for any given natural numbers d, n and k the subset

{F ∈ K^{d+1} : μ(F; n) ≤ k}

is closed in the ℚ-Zariski topology of K^{d+1}. Hence, since the variety W_{d,L} is the ℚ-Zariski closure of the image of the morphism Φ_{d,L} = (P_{L,0}, …, P_{L,d}), it suffices to prove the statement of the lemma for an arbitrary (d + 1)-tuple F := (f_{0}, …, f_{d}) which belongs to im Φ_{d,L}. Let N := (L + 1)(L + 2). For fixed d, L and n ∈ ℕ let us define the following set of polynomials of ℤ[Z_{1}, …, Z_{N}]:

Γ := { ∑_{S⊆{0,...,d}} θ_{S} ∏_{j∈S} P_{L,j}^{v_{j}} : 1 ≤ v_{j} ≤ n, 0 ≤ j ≤ d, θ_{S} ∈ {0, 1}} .

For any z ∈ K^{N} let us write Γ(z) := {P (z) : P ∈ Γ} ⊆ K. Clearly we have # Γ(z) ≤ # Γ. From Theorem 2 and Definition 3 we conclude that for any (d + 1)-tuple F := (f_{0}, …, f_{d}) belonging to im Φ_{d,L} there exists a point z_{F} ∈ K^{N} such that the following holds:

μ(F; n) = # Γ(z_{F}) ≤ # Γ .

Therefore, in order to prove (3) it suffices to show that the inequality

# Γ ≤ 2^{(n(d+1))^{20L^{2}}}

holds.

Let D := max{deg P : P ∈ Γ} and H := max{height P : P ∈ Γ}. Then every polynomial in Γ has at most \binom{D+N}{N} monomials each of them with an integer coefficient of absolute value less or equal than H. Therefore

# Γ ≤ (2H + 1)^{\binom{D+N}{N}} ≤ (2H + 1)^{(D+1)^{N}} , (4) since the inequality

\binom{D + N}{N} ≤ (D + 1)^{N}

holds for every pair of natural numbers D and N.

From the degree bound (1) we deduce the estimate:

D + 1 ≤ n ∑_{0≤j≤d}(j(2L − 1) + 2) + 1 ≤ n(d + 1)(Ld + 2) . (5)

Since every polynomial P ∈ ℤ[Z_{1}, …, Z_{N}] verifies height (P) ≤ weight (P), from (2) we infer the following bound for the height of any polynomial in Γ:

H ≤ 2^{d+1} · ∏_{0≤j≤d} 2^{3n((j+1)^{L}−1)} ≤ 2^{3n(d+1)^{L+1}−(3n−1)(d+1)} . (6)

Now, putting together (4), (5) and (6) we obtain the following estimate:

# Γ ≤ (2H + 1)^{(D+1)^{N}} ≤ 2^{3n(d+1)^{L+1}(n(d+1)(Ld+2))^{(L+1)(L+2)}} ≤
≤ 2^{n(d+1)^{L+1}(n(d+1)^{2}(L+1))^{(L+1)(L+2)}} .

By Horner’s rule we may suppose without loss of generality that L ≤ d holds. This implies finally

# Γ ≤ 2^{n(d+1)^{L+1}(n(d+1)^{3})^{(L+1)(L+2)}} ≤ 2^{(n(d+1))^{20L^{2}}} . □

From Lemma 4 we obtain easily a sufficient condition (Theorem 6) saying when a polynomial with integer coefficients is hard to compute. Let p ∈ ℕ be a prime number. For any integer f ∈ ℤ let us denote by ν_{p}(f) the multiplicity of p in the prime factor decomposition of f.

In the proof of Theorem 6 we need the following elementary fact.

Claim 5 Let a_{1}, …, a_{b} be nonzero natural numbers and let p be a prime number such that ν_{p}(a_{j}) < ν_{p}(a_{j+1}) holds for each j, 1 ≤ j < b. Then

# {∑_{j∈S} a_{j} : S ⊆ {1, …, b}} = 2^{b} .

PROOF. It suffices to show that for any pair of different subsets S and S′ of {1, …, b} it holds:

∑_{j∈S} a_{j} ≠ ∑_{j∈S′} a_{j} . (7)

By cancelling common elements in both sides of the former inequality (if necessary) we conclude that it is enough to prove that inequality (7) holds for any pair of disjoint subsets S and S′ of {1, …, b}.

Now for each j, 1 ≤ j ≤ b, let n_{j} := ν_{p}(a_{j}) be the multiplicity of p in the prime factor decomposition of the natural number a_{j}. We can write a_{j} = p^{n_{j}} ·ã_{j} with ν_{p}(ã_{j}) = 0. By hypothesis for each j, 1 ≤ j ≤ b, we know that n_{j} < n_{j+1}. Consequently, we deduce that for any subset S of {1, …, b} the following equality holds:

ν_{p}(∑_{j∈S} a_{j}) = ν_{p}(p^{n_{m}} · (ã_{m} + ∑_{{j∈S \atop m<j}} p^{n_{j}−n_{m}} · ã_{j}) ) = n_{m} , (8)

where m ∈ {1, …, b} is the minimum of S.

From (8) we deduce immediatly that for any pair of different subsets S and S′ of {1, …, b} it holds:

ν_{p}(∑_{j∈S} a_{j})≠ ν_{p}( ∑_{j∈S′} a_{j}) ,

and this finishes the prove of Claim 5. □

Theorem 6 There exists a positive universal constant c with the following property: let d and L be given nonzero natural numbers, d > 1. Let F := ∑_{0≤j≤d} f_{j}X^{j} ∈ ℤ[X] be a polynomial of degree at most d with integer coefficients such that F belongs to the algebraic variety W_{d,L}. Then for any prime number p ∈ ℕ we have

L^{2} ≥ c · \frac{log_{2}(# \{∑_{j∈S} ν_{p}(f_{j}) : S ⊆ \{0, …, d\}\})}{log_{2} d} .

PROOF. Let p ∈ ℕ be a prime number and let

b := # {ν_{p}(∏_{j∈S} f_{j}): S ⊆ {0, …, d}} .

Then from Claim 5 we deduce that the following estimate holds:

μ(F) = # { ∑_{S⊆{0,...,d}} θ_{S} ∏_{j∈S} f_{j} : θ_{S} ∈ {0, 1}, S ⊆ {0, …, d}} ≥ 2^{b} . (9)

Combining (9) with the inequality (3) for n = 1 and taking logarithms twice gives

L^{2} ≥ \frac{1}{20} · \frac{log_{2}(# \{∑_{j∈S} ν_{p}(f_{j}) : S ⊆ \{0, …, d\}\})}{log_{2}(d + 1)} .

Finally, since d > 1, we conclude

L^{2} ≥ \frac{1}{20 log_{2} 3} · \frac{log_{2}(# \{∑_{j∈S} ν_{p}(f_{j}) : S ⊆ \{0, …, d\}\})}{log_{2} d} . □

Theorem 6 is the key result to show computational hardness of several new families of polynomials with integer coefficients. From Theorem 6 we can also obtain simple hardness proofs for some known families of polynomials with integer coefficients. For example Theorem 6 easily implies that the family of polynomials (F_{d})_{d∈ℕ} defined by F_{d} := ∑_{0≤j≤d} 2^{2^{j}}X^{j} satisfies the complexity bound L^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}) (see [25]).

Lemma 4 implies also some known hardness results for polynomials with algebraic coefficients. This is the content of the next two theorems.

Theorem 7 (Heintz–Sieveking [14]) There exists a positive universal constant c with the following property: let D a given natural number and let F := ∑_{0≤j≤d} f_{j}X^{j} ∈ ℂ[X] be a polynomial of degree at most d with algebraic complex coefficients. Let N be the dimension of the ℚ-vector space ℚ[f_{0}, …, f_{d}]. Suppose that there exist polynomials g_{1}, …, g_{s} ∈ ℚ[X_{0}, …, X_{d}] of degree at most D, such that the locus of common zeroes of these polynomials in ℂ^{d+1}, Z(g_{1}, …, g_{s}), is finite and contains the point (f_{0}, …, f_{d}). Then for any natural number L such that F belongs to the algebraic variety W_{d,L} we have the estimate

L^{2} ≥ c · \frac{log_{2} N}{log_{2} d + log_{2} D} .

PROOF. For any subset V ⊂ K^{d+1} let us denote by I(V) ⊂ ℚ[X_{0}, …, X_{d}] the ideal of the polynomials of ℚ[X_{0}, …, X_{d}] which vanish on V. From the assumption (f_{0}, …, f_{d}) ∈ Z(g_{1}, …, g_{s}) we deduce the following inclusions of ideals:

(g_{1}, …, g_{s}) ⊆ I(Z(g_{1}, …, g_{s})) ⊆ I(\overline{\{(f_{0}, …, f_{d})\}}) ,

where \overline{\{(f_{0}, …, f_{d})\}} is the closure in the ℚ-Zariski topology of ℂ^{d+1} of the set containing only the point (f_{0}, …, f_{d}). These inclusions and the fact that the ℚvector space ℚ[f_{0}, …, f_{d}] and the ℚ-algebra ℚ[X_{0}, …, X_{d}]/I(\overline{\{(f_{0}, …, f_{d})\}}) are isomorphic imply that the morphism of ℚ-algebras

π : ℚ[X_{0}, …, X_{d}]/(g_{1}, …, g_{s}) ⟶ ℚ[f_{0}, …, f_{d}] ,

defined by π(X_{j} + (g_{1}, …, g_{s})) := f_{j} for any j, 0 ≤ j ≤ d, is an epimorphism.

From the assumption that the polynomials g_{1}, …, g_{s} define a nonempty finite subset we deduce that the ℚ-vector space ℚ[X_{0}, …, X_{d}]/(g_{1}, …, g_{s}) is finite dimensional. According to [9] it is possible to find for ℚ[X_{0}, …,X_{d}]/(g_{1}, …, g_{s}) a monomial basis β of the form

β := {X_{0}^{v_{0}} ⋯ X_{d}^{v_{d}} + (g_{1}, …, g_{s}) : 0 ≤ v_{0} + ⋯ + v_{d} ≤ D(d + 1)} .

The image of the basis β under the epimorphism π,

π(β) = {f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}: 0 ≤ v_{0} + ⋯ + v_{d} ≤ D(d + 1)} ,

is a set of generators of the ℚ-vector space ℚ[f_{0}, …, f_{d}]. Therefore, if N is the dimension of ℚ[f_{0}, …, f_{d}] then

# {∑_{f∈S} f : S ⊆ π(β)} ≥ 2^{N} .

Taking into account Definition 3 and the inclusion

{∑_{f∈S} f : S ⊆ π(β)} ⊆ { ∑_{S⊆{0,...,d}} θ_{S} ∏_{j∈S} f_{j}^{v_{j}}: 1 ≤ v_{j} ≤ D(d + 1), θ_{S} ∈ {0, 1}}

we can write

2^{N} ≤ μ(F; D(d + 1)) . (10)

Finally, let L be a natural number such that the point F belongs to the variety W_{d,L}. Then Lemma 4 yields the inequality

μ(F; D(d + 1)) ≤ 2^{(D(d+1)^{2})^{20L^{2}}} . (11)

The proof finishes combining (10) and (11) and taking logarithms twice. □

Theorem 7 implies that the following families of polynomials with algebraic coefficients (F_{d})_{d∈ℕ} satisfy the complexity bound L^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}):

• F_{d} := ∑_{1≤j≤d} e^{\frac{2πi}{j}}X^{j} (see [14]),

• F_{d} := ∑_{1≤j≤d} \sqrt{p_{j}}X^{j}, where p_{j} is the j-th prime number (see [11]).

Theorem 8 (Baur [2]) There exists a positive universal constant c with the following property: let D be a natural number and let F := ∑_{0≤j≤d} f_{j}X^{j} ∈ ℂ[X] be a polynomial of degree at most d with complex coefficients. Suppose that there exist polynomials g_{1}, …, g_{s} ∈ ℚ[X_{0}, …, X_{d}] of degree at most D such that the complex numbers g_{1}(f_{0}, …, f_{d}), …, g_{s}(f_{0}, …, f_{d}) are ℚ-linearly independent. Then for any natural number L such that F belongs to the algebraic variety W_{d,L} we have the estimate

L^{2} ≥ c · \frac{log_{2} s}{log_{2} d + log_{2} D} .

PROOF. Let ⟨g_{i}(f_{0}, …, f_{d}) : 1 ≤ i ≤ s⟩ be the vector space over ℚ spanned by the set {g_{1}(f_{0}, …, f_{d}), …, g_{s}(f_{0}, …, f_{d})}. Similarly, let ⟨f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}} : 0 ≤ v_{0} +⋯+v_{d} ≤ D⟩ be the vector space over ℚ generated by the set {f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}: 0 ≤ v_{0} + ⋯ + v_{d} ≤ D}. Since for each i, 1 ≤ i ≤ s, there exist coefficients a_{i,v}∈ ℚ, with v := (v_{0}, …, v_{d}) ∈ ℕ^{d+1} and 0 ≤ |v| ≤ D, such that

g_{i}(f_{0}, …, f_{d}) = ∑_{{v:=(v_{0},...,v_{d})∈ℕ^{d+1} \atop 0≤|v|≤D}} a_{i,v} · f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}

holds, we have the following inclusion between vector spaces:

⟨g_{i}(f_{0}, …, f_{d}) : 1 ≤ i ≤ s⟩ ⊆ ⟨f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}: 0 ≤ v_{0} + ⋯ + v_{d} ≤ D⟩ .

This inclusion and the linear independence in ℚ of the complex numbers g_{i}(f_{0}, …, f_{d}), 1 ≤ i ≤ s, yield the inequality

dim_{ℚ} ⟨f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}: 0 ≤ v_{0} + ⋯ + v_{d} ≤ D⟩ ≥ s .

This inequality implies that there exist at least 2^{s} elements which can be expressed as sums of distinct elements of the set {f_{0}^{v_{0}} ⋯ f_{d}^{v_{d}}: 0 ≤ v_{0}+⋯+v_{d} ≤ D}. From this and by Definition 3 we deduce

μ((f_{0}, …, f_{d}); D) ≥ 2^{s} . (12)

Finally, let L ∈ ℕ such that F belongs to the variety W_{d,L}. Then from Lemma 4 we deduce the inequality

μ(F; D) ≤ 2^{(D(d+1))^{20L^{2}}} . (13)

Combining (12) and (13) and taking logarithms twice finishes the proof. □

Theorem 8 implies that the family of polynomials with algebraic coefficients (F_{d})_{d∈ℕ} defined by F_{d} := ∏_{1≤j≤d}(X −\sqrt{p_{j}}), where p_{j} is the j-th prime number, satisfies the complexity bound L^{2}(F_{d}) = Ω (\frac{d}{log_{2} d}) (see [13]).

4 Polynomials Which Are Hard to Compute

As mentioned in the previous section, Theorem 6 yields hardness proofs for several new families of polynomials with integer coefficients, which are collected in Theorems 10, 11 and 12 below.

In the proofs of these theorems we need the following elementary fact.

Claim 9 Let a_{1}, …, a_{b} be natural numbers such that ∑_{1≤k<j} a_{k} < a_{j} holds for each j, 1 ≤ j ≤ b. Then

# {∑_{j∈S} a_{j} : S ⊆ {1, …, b}} = 2^{b} .

PROOF. In order to prove Claim 9 it suffices to show that for any pair of different subsets S, S′ of {1, …, b} the inequality ∑_{j∈S} a_{j} ≠ ∑_{j∈S′} a_{j} holds. Without loss of generality we may assume that the conditions S ∩ S′ = ∅ and max(S) < max(S′) are satisfied. Thus

∑_{j∈S} a_{j} ≤ ∑_{1≤j≤max(S)} a_{j} ≤ ∑_{1≤j<max(S′)} a_{j} < a_{max(S′)} ≤ ∑_{j∈S′} a_{j}

holds and therefore

∑_{j∈S} a_{j} ≠ ∑_{j∈S′} a_{j} . □

Theorem 10 Let n be a fixed positive integer number. Let φ be the Euler totient function and let π(j) be the number of primes not exceeding j. Let F := (F_{d})_{d∈ℕ} be the family of polynomials defined by any of the following expressions:

(i) F_{d} := ∑_{0≤j≤d} 2^{2^{φ(⌊ ^{n} \sqrt{j}⌋)}}X^{j},

(ii) F_{d} := ∑_{0≤j≤d} 2^{φ(⌊ ^{n} \sqrt{j}⌋)!} X^{j},

(iii) F_{d} := ∑_{0≤j≤d} 2^{2^{π(⌊ ^{n} \sqrt{j}⌋)}}X^{j},

(iv) F_{d} := ∑_{0≤j≤d} 2^{π(⌊ ^{n} \sqrt{j}⌋)!} X^{j}.

Then the family F satisfies the complexity bound L^{2}(F_{d}) = Ω(\frac{n ^{n} \sqrt{d}}{(log_{2} d)^{2}} ).

PROOF. Let F := (F_{d})_{d∈ℕ} be the family defined by the expression (i) of the statement of Theorem 10. We are going to show that for any nonzero natural number d the following estimate holds:

# \{ν_{2}(∏_{j∈S} 2^{2^{φ(⌊ ^{n} \sqrt{j}⌋)}}) : S ⊆ \{0, …, d\}\} ≥ 2^{π(⌊ ^{n} \sqrt{d}⌋)} . (14)

Therefore the complexity bound of the statement of Theorem 10 follows immediately applying Theorem 6 and the Chebyshev’s Theorem (see [7, Chapter 9, Exercises 9.19–9.21]): for any natural number d, d > 1, the following estimate holds

\frac{1}{6} · \frac{d}{ln d} ≤ π(d) ≤ 6 · \frac{d}{ln d} .

For any j ≥ 1, let p_{j} be the j-th prime number. From the inclusion

\{p_{j}^{n} : 1 ≤ j ≤ π(⌊ ^{n} \sqrt{d}⌋)\} ⊂ \{j : 0 ≤ j ≤ d\}

we deduce the inclusion:

\{ν_{2}(∏_{j∈S} 2^{2^{φ(p_{j})}}):S ⊆ \{1, …, π(⌊ ^{n} \sqrt{d}⌋)\}\}⊆ \{ν_{2}(∏_{j∈S} 2^{2^{φ(⌊ ^{n} \sqrt{j}⌋)}}):S ⊆ \{0, …, d\}\}.

Therefore, to show inequality (14) it is sufficient to prove the following equality

# \{ν_{2}(∏_{j∈S} 2^{2^{φ(p_{j})}}) : S ⊆ \{1, …, π(⌊ ^{n} \sqrt{d}⌋)\}\} = 2^{π(⌊ ^{n} \sqrt{d}⌋)} .

For this purpose, according to Claim 9, we only need to demonstrate that for any j, 1 ≤ j ≤ π(⌊ ^{n} \sqrt{d}⌋), the following inequality holds:

ν_{2}( ∏_{1≤k<j} 2^{2^{φ(p_{k})}}) = ∑_{1≤k<j} ν_{2}(2^{2^{φ(p_{k})}}) = ∑_{1≤k<j} 2^{φ(p_{k})} < 2^{φ(p_{j})} = ν_{2}(2^{2^{φ(p_{j})}}) ,

which follows from the estimate

∑_{1≤k<j} 2^{φ(p_{k})} = ∑_{1≤k<j} 2^{p_{k}−1} ≤ ∑_{0≤k<p_{j−1}} 2^{k} = 2^{p_{j−1}} − 1 < 2^{p_{j−1}} < 2^{p_{j}−1} = 2^{φ(p_{j})} .

Similarly the lower bounds for the nonscalar complexity of the families of polynomials defined by the expressions (ii), (iii) and (iv) of the statement of Theorem 10 can be obtained respectively using the following estimations:

• ∑_{1≤k<j} φ(p_{k})! = ∑_{1≤k<j}(p_{k} − 1)! ≤ ∑_{0≤k<p_{j−1}} k! ≤ p_{j−1}! < (p_{j} − 1)! = φ(p_{j})!,

• ∑_{1≤k<j} 2^{π(p_{k})} = ∑_{1≤k<j} 2^{k} = 2^{j} − 2 < 2^{j} = 2^{π(p_{j})},

• ∑_{1≤k<j} π(p_{k})! = ∑_{1≤k<j} k! ≤ j! − 1 < j! = π(p_{j})! □

Theorem 11 Let n ≥ 1 be a fixed natural number. Let F := (F_{d})_{d∈ℕ} be the family of polynomials defined by any of the following expressions:

(i) F_{d} := ∑_{0≤j≤d} 2^{2^{⌊ ^{n} \sqrt{j}⌋}}X^{j},

(ii) F_{d} := ∏_{1≤j≤d}(X − 2^{2^{⌊ ^{n} \sqrt{j}⌋}}),

(iii) F_{d} := ∑_{0≤j≤d} 2^{⌊ ^{n} \sqrt{j}⌋!} X^{j},

(iv) F_{d} := ∏_{1≤j≤d}(X − 2^{⌊ ^{n} \sqrt{j}⌋!} ).

Then the family F satisfies the complexity bound L^{2}(F_{d}) = Ω(\frac{\sqrt[n]{d}}{log_{2} d}).

PROOF. Let F := (F_{d})_{d∈ℕ} be any of the families of polynomials defined by any of the expressions (i) or (iii). Let us write F_{d} := ∑_{0≤j≤d} f_{j}X^{j} where f_{0}, …, f_{d} are suitable integers. We are going to show that for any nonzero natural number d the following estimate holds:

# \{ν_{2}(∏_{j∈S} f_{j}): S ⊆ \{0, …, d\}\} ≥ 2^{⌊ ^{n} \sqrt{d}⌋} . (15)

Therefore the complexity bound of the statement of Theorem 11 for the families of polynomials defined by any of the expressions (i) or (iii) follows immediately from the application of Theorem 6 and the estimate (15).

In order to obtain the estimate (15) we observe that for any j, 1 ≤ j ≤ ⌊ ^{n} \sqrt{d}⌋, the following estimations holds:

• ∑_{1≤k<j} ν_{2}(2^{2^{k}}) = ∑_{1≤k<j} 2^{k} = 2^{j} − 2 < 2^{j} = ν_{2}(2^{2^{j}} ),

• ∑_{1≤k<j} ν_{2}(2^{k!}) = ∑_{1≤k<j} k! ≤ j! − 1 < j! = ν_{2}(2^{j!}).

Applying Claim 9 we deduce that the equality

# \{∑_{j∈S} ν_{2}(f_{j^{n}}) : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}⌋\}\} = 2^{⌊ ^{n} \sqrt{d}⌋}

holds for the sets constructed employing only the coefficients of the form f_{j^{n}}, 1 ≤ j ≤ ⌊ ^{n} \sqrt{d}⌋, of the polynomials defined by the expressions (i) or (iii). Taking into account the inclusion

\{∑_{j∈S} ν_{2}(f_{j^{n}}) : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}⌋\}\} ⊆ \{∑_{j∈S} ν_{2}(f_{j}) : S ⊆ \{0, …, d\}\} ,

we deduce that estimate (15) holds for the family of polynomials defined either by the expression (i) or by the expression (iii).

Now, let F := (F_{d})_{d∈ℕ} be any of the families of polynomials defined either by the expression (ii) or by the expression (iv). Let us write F_{d} := ∑_{0≤j≤d} f_{d−j}X^{j} where f_{0}, …, f_{d} are suitable integers. We are going to show that for any j, 1 ≤ j < ⌊ ^{n} \sqrt{d}⌋, we have:

∑_{1≤k<j} ν_{2}(f_{(k+1)^{n}−1}) < ν_{2}(f_{(j+1)^{n}−1}) .

For this purpose, we observe that the multiplicity of the roots 2^{2^{j}} and 2^{j!}, 1 ≤ j < ⌊ ^{n} \sqrt{d}⌋, in the polynomials F_{d} defined by the expressions (ii) or (iv) is exactly (j + 1)^{n} − j^{n}.

From this last remark, we deduce the following estimations:

•

∑_{1≤k<j} ν_{2}(f_{(k+1)^{n}−1}) = ∑_{1≤k<j} ∑_{1≤l≤k}((l + 1)^{n} − l^{n})2^{l} ≤
≤ ∑_{1≤k<j}((k + 1)^{n} − k^{n})( ∑_{1≤l≤k} 2^{l}) =
= ∑_{1≤k<j}((k + 1)^{n} − k^{n})(2^{k+1} − 2) <
< ∑_{1≤k≤j}((k + 1)^{n} − k^{n})2^{k} = ν_{2}(f_{(j+1)^{n}−1}) ,

•

∑_{1≤k<j} ν_{2}(f_{(k+1)^{n}−1}) = ∑_{1≤k<j} ∑_{1≤l≤k}((l + 1)^{n} − l^{n})l! ≤
≤ ∑_{1≤k<j}((k + 1)^{n} − k^{n})( ∑_{1≤l≤k} l!) ≤
≤ ∑_{1≤k<j}((k + 1)^{n} − k^{n})((k + 1)! − 1) <
< ∑_{1≤k≤j}((k + 1)^{n} − k^{n})k! = ν_{2}(f_{(j+1)^{n}−1}) .

Now applying Claim 9 we deduce that the equality

# \{∑_{j∈S} ν_{2}(f_{(j+1)^{n}−1}) : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}⌋ − 1\}\} = 2^{⌊ ^{n} \sqrt{d}⌋−1}

holds for the sets constructed employing only the coefficients of the form f_{(j+1)^{n}−1}, 1 ≤ j < ⌊ ^{n} \sqrt{d}/2⌋, of the polynomials defined by expressions (ii) or (iv). Since the following inclusion holds

\{∑_{j∈S} ν_{2}(f_{(j+1)^{n}−1}) : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}⌋ − 1\}\} ⊆ \{∑_{j∈S} ν_{2}(f_{j}) : S ⊆ \{0, …, d\}\} ,

we deduce the following inequality

# \{∑_{j∈S} ν_{2}(f_{j}) : S ⊆ \{0, …, d\}\} ≥ 2^{⌊ ^{n} \sqrt{d}⌋−1}

for any of the families of polynomials defined either by the expression (ii) or by the expression (iv), and therefore the complexity bound of the statement of Theorem 11 for these families follows immediately applying Theorem 6. □

Theorem 12 Let n be a fixed positive integer number. Let F := (F_{d})_{d∈ℕ} be the family of polynomials defined by any of the following expressions:

(i) F_{d} := ∑_{0≤j≤d} 2^{F_{⌊ ^{n} \sqrt{j}⌋}}X^{j},

(ii) F_{d} := ∏_{1≤j≤d}(X − 2^{F_{⌊ ^{n} \sqrt{j}⌋}}).

where F_{j} is the j-th Fibonacci number. Then the family F satisfies the complexity bound L^{2}(F_{d}) = Ω(\frac{\sqrt[n]{d}}{log_{2} d}).

PROOF. Let F := (F_{d})_{d∈ℕ} be the family defined by the expression (i). Let us write ∑_{0≤j≤d} f_{j}X^{j} := ∑_{0≤j≤d} 2^{F_{⌊ ^{n} \sqrt{j}⌋}}X^{j} where f_{j}, 0 ≤ j ≤ d, are suitable integers. Since for j ≥ 1 it holds

∑_{1≤k<j} F_{2k} = F_{2j−1} − 1 < F_{2j} ,

we deduce from Claim 9 the following equality

# \{ν_{2}(∏_{j∈S} f_{(2j)^{n}}) : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}/2⌋\}\} =

= # \{∑_{j∈S} F_{2j} : S ⊆ \{1, …, ⌊ ^{n} \sqrt{d}/2⌋\}\} = 2^{⌊ \frac{^{n} \sqrt{d}}{2}⌋} .

From this last equality we deduce the estimate

# \{ν_{2}(∏_{j∈S} f_{j}): S ⊆ \{0, …, d\}\} ≥ 2^{⌊ \frac{^{n} \sqrt{d}}{2}⌋} . (16)

Finally the complexity bound for the family F defined by the expression (i) follows from Theorem 6 and the estimate (16).

Let F := (F_{d})_{d∈ℕ} be the family of polynomials defined by expression (ii). Let us write ∑_{0≤j≤d} f_{d−j}X^{j} := ∏_{1≤j≤d} (X − 2^{F_{⌊ ^{n} \sqrt{j}⌋}}) where f_{j}, 0 ≤ j ≤ d are suitable integers. We are going to show that the inequality

∑_{1≤k<j} ν_{2}(f_{(2k+1)^{n}−1}) < ν_{2}(f_{(2j+1)^{n}−1})

holds for any j satisfying 1 ≤ j < ⌊ ^{n} \sqrt{d}/2⌋. For this purpose we observe that the multiplicity of the root 2^{F_{j}}, 1 ≤ j < ⌊ ^{n} \sqrt{d}⌋, in the polynomial F_{d} defined by the expression (ii) is exactly (j + 1)^{n} − j^{n}.

From this observation we deduce that for any j, 1 ≤ j < ⌊ ^{n} \sqrt{d}/2⌋, it holds:

∑_{1≤k<j} ν_{2}(f_{(2k+1)^{n}−1}) = ∑_{1≤k<j} ∑_{1≤l≤2k}((l + 1)^{n} − l^{n})F_{l} ≤
≤ ∑_{1≤k<j}((2k + 1)^{n} − (2k)^{n})( ∑_{1≤l≤2k} F_{l}) =
= ∑_{1≤k<j}((2k + 1)^{n} − (2k)^{n})(F_{2k+2} − 1) <
< ∑_{1≤k<j}((2k + 1)^{n} − (2k)^{n})F_{2k+2} <
< ∑_{1≤k≤2j}((k + 1)^{n} − k^{n})F_{k} = ν_{2}(f_{(2j+1)^{n}−1}) .

Therefore, applying Claim 9 we deduce the following inequality

# \{ν_{2}(∏_{j∈S} f_{j}): S ⊆ \{0, …, d\}\} ≥ 2^{⌊ ^{\frac{^{n} \sqrt{d}}{2}}⌋−1} . (17)

The complexity bound for the family F := (F_{d})_{d∈ℕ} follows now from Theorem 6 and the estimate (17). □

5 Applications to Transcendental Function Theory

Our algebraic complexity method can be applied to classical questions of transcendence in number theory and geometry. Using Newton’s method to approximate algebraic functions we obtain a sufficient condition (Theorem 13) for the transcendence of formal power series.

Theorem 13 Let K be an algebraically closed field of characteristic zero and let σ := ∑_{j∈ℕ} f_{j}X^{j} ∈ K[[X]] be a given formal power series. Suppose that for any positive integer c there exists a natural number k such that the open condition

(f_{0}, …, f_{2^{k}−1}) ∉ W_{2^{k}−1,ck}

holds. Then the power series σ is transcendental over K(X).

PROOF. Let us suppose that σ is algebraic over K(X). Then by Bochnak et alii ([5, Chapter 8]) the power series series σ defines a holomorphic function around the origin. Now using the Newton’s method we are able to approximate the holomorphic funtion σ. More precisely, using the construction given in [16] we conclude that there exist a positive integer c and a Zariski open subset U ⊂ K with the following property: for any point α ∈ U belonging to the domain of σ and for any natural number k there exists a rational function ξ_{k} such that the initial segment of degree 2^{k} − 1 of the Taylor expansion around α of ξ_{k} agrees with the initial segment of degree 2^{k} −1 of the Taylor expansion around α of the holomorphic function σ, namely

∑_{0≤j≤2^{k}−1} \frac{ξ_{k}^{(j)}(α)}{j!} · (X − α)^{j} = ∑_{0≤j≤2^{k}−1} \frac{σ^{(j)}(α)}{j!} · (X − α)^{j} .

Moreover, in the construction of the rational function ξ_{k} we employ c · k nonscalar operations, that is L_{O_{α}}(ξ_{k}) ≤ c · k.

Now using Theorem 2, the previous property can be paraphrased as follows: there exist a positive integer number c and a Zariski open subset U ⊂ K such that for any point α ∈ U belonging to the domain of σ and for any natural number k the point given by the coefficients of the Taylor polynomial of (formal) degree 2^{k} − 1 in α of the holomorphic function σ belongs to the variety W_{2^{k}−1,ck}, that is,

(σ^{(j)}(α)/j! : 0 ≤ j ≤ 2^{k} − 1) ∈ W_{2^{k}−1,ck} . (18)

On the other hand, for the given c, according to the hypothesis of the theorem, there must exists a natural number k such that

(f_{0}, …, f_{2^{k}−1}) ∉ W_{2^{k}−1,ck} .

Since the power series σ is holomorphic so is any derivative σ^{(j)} of σ, j ∈ ℕ. Then any coefficient f_{j} of σ, j ∈ ℕ, verifies

f_{j} = \frac{σ^{(j)}(0)}{j!} ,

and consequently

(σ^{(j)}(0)/j! : 0 ≤ j ≤ 2^{k} − 1) ∉ W_{2^{k}−1,ck} .

By the continuity of σ^{(j)} we deduce that there exists a neighbourhood of zero V ⊂ K such that for any α ∈ V the following open condition holds:

(σ^{(j)}(α)/j! : 0 ≤ j ≤ 2^{k} − 1) ∉ W_{2^{k}−1,ck} .

But this contradicts the condition (18) which is satisfied for any point α of the Zariski open subset U if we suppose that the power series σ is algebraic. Hence σ must be transcendental. □

From Lemma 4 and Theorem 13 we deduce the following criterion of transcendence.

Criterion 14 Let K be an algebraically closed field of characteristic zero and let σ := ∑_{j∈ℕ} f_{j}X^{j} ∈ K[[X]] be a given power series. Suppose that for any positive real number c there exists a natural number k such that the following inequality holds

μ((f_{0}, …, f_{2^{k}−1})) > 2^{2^{ck^{3}}} . (19)

Then the power series σ is transcendental over K(X).

PROOF. Let c be an arbitrary positive real number and let k be a natural number for which, according to the hypothesis, the inequality (19) holds.

Fixed c and k, let L be a natural number such that the point (f_{0}, …, f_{2^{k}−1}) belongs to the variety W_{2^{k}−1,L}. Then from Lemma 4 we have

μ((f_{0}, …, f_{2^{k}−1})) ≤ 2^{2^{20kL^{2}}} . (20)

Combining (20) with (19) and taking logarithms twice we obtain

L > √ ; \overline{\frac{c}{20}} · k ,

and from this inequality we deduce that the point (f_{0}, …, f_{2^{k}−1}) does not belong to the variety W_{2^{k}−1,c′k}, where c′ := ⌊\sqrt{\frac{c}{20}}⌋. Since c is arbitrary, the transcendence of σ follows from Theorem 13. □

From Criterion 14 we obtain the following transcendence results.

Corollary 15 Let n be a given nonzero natural number. The following power series which belong to ℚ[[X]] are transcendental over the function field ℂ(X):

(i) ∑_{j∈ℕ} \frac{1}{2^{2^{φ(⌊ ^{n} \sqrt{j}⌋)}}} X^{j} and ∑_{j∈ℕ} \frac{1}{2^{φ(⌊ ^{n} \sqrt{j}⌋)!}} X^{j}, where φ is the Euler to-

tient function.

(ii) ∑_{j∈ℕ} \frac{1}{2^{2^{π(⌊ ^{n} \sqrt{j}⌋)}}} X^{j} and ∑_{j∈ℕ} \frac{1}{2^{π(⌊ ^{n} \sqrt{j}⌋)!}} X^{j}, where π(j) is the number

of primes not exceeding j.

(iii) ∑_{j∈ℕ} \frac{1}{2^{2^{⌊ ^{n} \sqrt{j}⌋}}} X^{j} and ∑_{j∈ℕ} \frac{1}{2^{⌊ ^{n} \sqrt{j}⌋!}} X^{j}.

(iv) ∑_{j∈ℕ} \frac{1}{2^{F_{⌊ ^{n} \sqrt{j}⌋}}} X^{j}, where F_{j} denotes the j-th Fibonacci number.

(v) ∑_{j∈ℕ} \frac{1}{2^{2^{⌊(log_{2}(j+1))^{n}⌋}}} X^{j}, for n ≥ 4.

PROOF. First of all we observe that, according to Definition 3, the equality

μ((a_{1}^{−1}, …, a_{b}^{−1})) = μ((a_{1}, …, a_{b})) (21)

holds for any nonzero elements a_{j}, 1 ≤ j ≤ b, of the field K.

Let σ := ∑_{j∈ℕ} f_{j}^{−1}X^{j} be any of the power series of (i) or (ii). For any natural number k the estimate (14) and Claim 5 imply

μ((f_{j} : 0 ≤ j ≤ 2^{k} − 1)) ≥ 2^{2^{π(⌊ ^{n} \sqrt{2^{k}−1}⌋)}} .

Then from (21), the inequality

μ((f_{j}^{−1} : 0 ≤ j ≤ 2^{k} − 1)) ≥ 2^{2^{π(⌊ ^{n} \sqrt{2^{k}−1}⌋)}}

holds for any natural number k and therefore the transcendence of the series σ follows from Criterion 14 and Chebyshev’s Theorem.

Employing estimations (15) and (16) in a similar way we deduce from Criterion 14 the transcendence of the power series of (iii) and (iv).

In order to prove the transcendence of the power series of (v) we are going to demonstrate that the inequality

# {ν_{2}(∏_{j∈S} 2^{2^{⌊(log_{2} j)^{n}⌋}}) : S ⊆ {1, …, 2^{k}}} ≥ 2^{k^{n}−λ(n)+1} , (22)

holds for any natural number k, where λ(n) := ⌈\frac{1}{2} (\frac{(2n)!}{(ln 2)^{2n}} − 1)⌉. From Claim 5 we deduce that to prove the estimate (22) it is sufficient to show that the estimate

# {⌊(log_{2} j)^{n}⌋ : 1 ≤ j ≤ 2^{k}} ≥ k^{n} − λ(n) + 1

holds for any natural number k. Fixed k, this estimate is satisfied if for any natural number l such that λ(n) ≤ l ≤ k^{n} there exists a natural number j, 1 ≤ j ≤ 2^{k}, such that the inequalities

2^{\sqrt[n]{l}} ≤ j < 2^{\sqrt[n]{l+1}} (23)

hold. To prove (23), we consider 2^{\sqrt[n]{l+1}} and 2^{\sqrt[n]{l}} as functions in l. Expanding them in power series and retaining only the (2n)-th term in the expansions we obtain the following inequality:

2^{\sqrt[n]{l+1}} − 2^{\sqrt[n]{l}} = ∑_{i∈ℕ} \frac{((l + 1)^{\frac{1}{n}} ln 2)^{i}}{i!} − ∑_{i∈ℕ} \frac{(l^{\frac{1}{n}} ln 2)^{i}}{i!} ≥
≥ \frac{(ln 2)^{2n}}{(2n)!} · (l + 1)^{2} − \frac{(ln 2)^{2n}}{(2n)!} · l^{2} = \frac{(ln 2)^{2n}}{(2n)!} · (2l + 1) .

Now taking l such that l ≥ \frac{1}{2} (\frac{(2n)!}{(ln 2)^{2n}} − 1) we deduce the inequality

2^{\sqrt[n]{l+1}} − 2^{\sqrt[n]{l}} ≥ 1

and this is sufficient to guarantee the existence of a natural number j such that (23) holds.

For any natural number k, the estimate (22) and Claim 5 yield the inequality

μ((2^{2^{⌊(log_{2} j)^{n}⌋}} : 1 ≤ j ≤ 2^{k})) ≥ 2^{2^{k^{n}−λ(n)+1}} .

From this inequality and (21), we finally deduce that the inequality

μ((2^{−2^{⌊(log_{2} j)^{n}⌋}} : 1 ≤ j ≤ 2^{k})) ≥ 2^{2^{k^{n}−λ(n)+1}}

holds for any natural number k. The transcendence of power series of (v) now follows from Criterion 14. □

References

[1] M. Aldaz, J. Heintz, G. Matera, J.L. Montaña and L.M. Pardo, Time-space tradeoffs in algebraic complexity theory, Journal of Complexity (2000, to appear).

[2] W. Baur, Simplified lower bounds for polynomials with algebraic coefficients, Journal of Complexity, 13 (1997) 38–41.

[3] E.G. Belaga, Some problems involved in the computations of polynomials, Dokl. Akad. Nauk. SSSR, 123 (1958) 775–777.

[4] L. Blum, F. Cucker, M. Shub and S. Smale, Real Complexity and Computation (Springer, Berlin, 1998).

[5] J. Bochnak, M. Coste and M.F. Roy. Géométrie Algébrique Réelle, Ergebnisse der Mathematik und ihrer Grenzgebiete vol. 12 (Springer, Berlin, 1987).

[6] A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems (Elsevier, 1975).

[7] P. Bürguisser, M. Clausen and M.A. Shokrollahi, Algebraic Complexity Theory, Comprehensive Studies in Mathematics vol. 315 (Springer, Berlin, 1997).

[8] N. Fitchas, A. Galligo and J. Morgenstern, Precise sequential and parallel complexity bounds for the quantifier elimination over algebraically closed fields, Journal of Pure and Applied Algebra 67 (1990) 1–14.

[9] N. Fitchas, M. Giusti and F. Smietanski, Sur la complexitè du Thèoréme des Zèros, in: B. Brosowski, F. Deutsch and J. Guddat, eds., Proceedings Second International Conference on Non-Linear Optimization and Approximation (Peter Lange, 1995) 274–329.

[10] J. von zur Gathen, Algebraic complexity theory, Ann. Review of Computer Science 3 (1988) 317–347, .

[11] J. von zur Gathen and V. Strassen, Some polynomials which are hard to compute, Theoretical Computer Science 11(3) (1980) 331–335.

[12] J. Heintz, On the computational complexity of polynomials and bilinear mappings. a survey, in: L. Huget and A. Poli, eds., Proceedings 5th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, AAECC-5 , Lecture Notes in Computer Science vol. 356 (Springer, Berlin, 1989) 269–300.

[13] J. Heintz and J. Morgenstern, On the intrinsic complexity of elimination theory, Journal of Complexity 9 (1993) 471–498.

[14] J. Heintz and M. Sieveking, Lower bounds for polynomials with algebraic coefficients, Theoretical Computer Science 11(3) (1980) 321–330.

[15] T. Krick and L.M. Pardo, A computational method for diophantine approximation, in: L. González-Vega and T. Recio, eds., Proceedings MEGA’94 Algorithms in Algebraic Geometry and Applications (1996) 193–254.

[16] H.T. Kung and J.F. Traub, All algebraic functions can be computed fast, Journal of the ACM 25(2) (1978) 245–260.

[17] R.J. Lipton, Straight-line complexity and integer factorization, in: L.M. Adleman and M.D. Huang, eds., Proceedings First International Symposium on Algorithmic Number Theory, ANTS-I , Lecture Notes in Computer Science vol. 877, (Springer, Berlin, 1994) 71–79.

[18] T.S. Motzkin, Evaluation of polynomials and evaluation of rational functions, Bulletin of American Mathematical Society 61 (1955) 163.

[19] L.M. Pardo, How lower and upper complexity bounds meet in elimination theory, in: G. Cohen, M. Giusti and T. Mora, eds., Proceedings 11th International Symposium on Applied Algebra, Algebraic Algorithms and Error Correcting Codes, AAECC-11 , Lecture Notes in Computer Science vol. 948, (Springer, Berlin, 1995) 33–69.

[20] M.S. Paterson and L.J. Stockmeyer, On the number of nonscalar multiplications necessary to evaluate polynomials, SIAM Journal on Computing 2 (1973) 60– 66.

[21] S. Puddu and J. Sabia, An effective algorithm for quantifier elimination over algebraically closed fields using straight-line programs, Journal of Pure and Applied Algebra 129(2) (1998) 173–200.

[22] C.P. Schnorr, Improved lower bounds on the number of multiplications-divisions which are necessary to evaluate polynomials, Theoretical Computer Science 7(3) (1978) 251–261.

[23] V. Shoup and R. Smolensky, Lower bounds for polynomial evaluation and interpolation problems, in Proceedings 31st Annual IEEE Symposium on Foundations of Computer Science (1991) 378–383, 1991.

[24] H.J. Stoss, On the representation of rational functions of bounded complexity, Theoretical Computer Science 64 (1989) 1–13.

[25] V. Strassen, Polynomials with rational coefficients which are hard to compute, SIAM Journal on Computing 3(2) (1974) 128–149.

[26] V. Strassen, Algebraic Complexity Theory, in Handbook of Theoretical Computer Science (Elsevier Science, Amsterdam, 1990) 634–672.