ON A TRANSFER THEOREM FOR THE P ≠ N P CONJECTURE

GREGORIO MALAJOVICH

Abstract. A model of computation is defined over the algebraic numbers and over number fields. This model is non-uniform, and the cost of operations depends on the height of the operands and on the degree of the extension of the rational defined by those operands.

A transfer theorem for the P ≠ N P Conjecture is proved, namely: P ≠ N P in this model over the real algebraic numbers if and only if P ≠ N P in the classical setting.

Contents

1. Introduction 2 2. Heights and Weights 4 2.1. Heights in ℤ and ℚ 4 2.2. Absolute values 5 2.3. The product formula 7 2.4. Heights 8 2.5. Properties of Heights 9 2.6. Weights 12 3. Weighted model of Computation 13 3.1. Machines over a ring 13 3.2. The register equations 16 3.3. Non-deterministic machines 17 3.4. The 3-Nullstellensatz problem 18 4. A transfer theorem for the P ≠ N P Conjecture 19 4.1. Morphisms and Transfer Theorem 19 4.2. Examples 24 4.3. Is x ≥ 0 hard ? 24 5. Complexity of diophantine approximation 25 5.1. Approximate Newton Iteration 25 5.2. Approximation of Algebraic Numbers 30 5.3. Proof of Theorem C 30 6. Bit representation of Algebraic Numbers 31 6.1. Lattice basis reduction 32 6.2. Symbolic algebra 35 6.3. P ≠ N P over (ℤ, >, w) ⇔ P ≠ N P over (ℚ^{ra}, >, w) 37 References 37

Date: December 14, 1998.

1. Introduction

A model of computation over a ring was introduced by Blum, Shub and Smale in [BSS89]. This model preserves the main features of the classical theory of Computation. Turing computability appears as a particular case (computation over 𝔽_{2} = ℤ mod 2ℤ).

One of the main objectives of this theory was to generalize the P ≠ N P conjecture by relating it to more traditional mathematical ideas and problems.

A model of computation in the sense of [BSS89] is given essentially by:

1. A ring R with unity and without zero divisors.

2. A subset o of R. Machines will be allowed to decide (to branch on) x ∈ o. Natural choices are o = {0} or, when R is ordered, the positive numbers o = {x ∈ R : x > 0}.

3. A cost function c : R^{∞} → ℝ. Here, R^{∞} stands for the disjoint union of R^{k}, where k ∈ ℕ. (i.e., R^{∞} is the set of finite lists of elements in R).

We will write for short: (R, =, c) and (R, >, c) for the models of computation over a ring R, with cost function c and branching on o = {0} or on o = {x ∈ R : x > 0}, respectively.

In this paper, the ‘size’ of some x ∈ R^{k} ⊂ R^{∞} is kc(x), and the ‘cost’ of a computation is the size of the output, plus the number of ring operations times max c(s) where s ranges over the operands of all the ring operations performed. Concepts of ‘polynomial time’ and ‘nondeterministic polynomial time’ arise naturally.

The main reference for computations over a ring is [BCSS98]. In the notation above, the main examples described in [BCSS98] are (𝔽_{2}, =, 1), (ℤ, >, x ↦ ⌈log |x|⌉ + 1), (ℝ, >, 1), (ℂ, =, 1).

Given a model of computation, there is a P ≠ N P conjecture associated to it. A ‘transfer’ theorem is a theorem relating the P ≠ N P conjecture in different models.

A few ‘transfer’ theorems are known for unit-cost models. The conjecture P ≠ N P is equivalent over the ring of complex numbers (ℂ, =, 1), over the algebraic closure of the rationals (ℚ^{a}, =, 1), or over any extension in-between [BCSS96]. See also [BCSS98, CG97, CK95, Koi94, Koi97, Mic94]. For a few consequences related to the transfer principle see [MM99].

In most literature on Computability over a ring, the cost function (or the cost of an arithmetic operation over the ring R (complex, real, ...) is usually fixed as c ≡ 1. Uniform cost is related to consequences such as the existence of ‘wisdom numbers’ over the reals, encoding an infinite sequence of 0’s and 1’s. Or such as the fact that P ≠ N P is true over (K, =, 1) for all infinite field K not algebraically closed (See [BCSS98] Chapter 7 Theorem 9).

In this paper, a ‘weighted’ model of computation is introduced. The cost function will be defined as the ‘weight’, a measure of the complexity of the operands. The definition of weight will encode some natural number-theoretical invariants, such as the height of algebraic numbers or the degree of an extension.

More precisely, if x_{1}, ⋯, x_{k} are algebraic over ℚ, then the weight of x is defined as

w(x) = [ℚ[x_{1}, ⋯ x_{k}] : ℚ] (1 + ⌈log_{2} H(1 : x_{1} : ⋯: x_{k})⌉)

where H is the projective, multiplicative height function as defined in [Lan97] and [Sil86].

In the particular case x ∈ ℤ, the model (ℤ, >, w) is precisely the model of computation over the integers ‘with height’ in [BSS89] or ‘with respect to logarithmic cost’ in [BCSS98]. This model is known to be equivalent to the Turing model, up to polynomial time.

Under the weighted model of computation, we will obtain a few conditions for the equivalence of the P ≠ N P conjecture over two rings; we will use those facts to prove that

Theorem A. Let K be a real number field, and let ℚ^{ra} be the real algebraic closure of rationals. The following are equivalent:

1. P ≠ N P over the Turing model

2. P ≠ N P over (ℤ, >, w).

3. P ≠ N P over (ℚ, >, w).

4. P ≠ N P over (K, >, w).

5. P ≠ N P over (ℚ^{ra}, >, w).

In view of the τ-conjecture [BCSS98, Sma98] it is interesting to ask what happens if one removes ‘order’ from the models above. Is deciding x > 0 hard over (ℚ^{ra}, =, w) ? Actually, {x > 0} will turn out to be undecidable, and the following theorem will follow:

Theorem B. P ≠ N P over (ℚ^{a}, =, w) and over (ℚ^{ra}, =, w)

The proof of Theorem A requires some results on the complexity of ‘effective’ diophantine approximation. Algebraic numbers can be approximated by rationals generated by a machine over (ℤ, >, w) (or equivalently, a Turing machine). This machine is ‘universal’ in the sense that it can be used to approximate any algebraic number x, given a suitable description y of x.

When given k ∈ ℕ and y ∈ ℤ^{∞}, where y is a suitable description of x, that machine will produce a, b ∈ ℤ and c ∈ ℕ such that

|x − (a + ib)2^{−c}| < 2^{−k}

The ‘suitable information’ on x may be its minimal polynomial and an approximation of x.

Theorem C. There are a machine M over (ℤ, >, w) and a function y : ℚ^{a} → ℤ^{∞} with the following properties:

If x is an algebraic number, then M with input k, y(x) will output a, b ∈ ℤ and c ∈ ℕ such that

|x − (a + ib)2^{−c}| < 2^{−k}

The running time for k > 5 is k log k w(x) log w(x) Poly(deg[ℚ[x] : ℚ]). Also, w(x) ≤ Bitsize(y). Moreover, if x is real, then b is always zero in M(y(x), k).

The running time above is better than the O(k^{2}) in the proof of Theorem (1.4.7)(a) in [Lov86] or in Algorithm 2 Step 3 in [Loo83]. This theorem gives also an implicit bound for the bit-size of y(x). Given y(x), this can be used to decide if an algebraic number is > 0, for instance.

Theorem C makes sense in the Turing model of computation. However, it also makes sense in the weighted model over ℚ^{ra}, with or without order. In that model, Turing computations can be simulated by using sequences of 0’s and 1’s. It is possible to compute ‘mixed’ expressions, like f(x) where f is an integer polynomial and x ∈ ℚ^{ra}.

Theorem D. The restriction y : ℚ^{ra} → ℤ^{∞} of the function y of Theorem D can be computed in polynomial time over (ℚ^{ra}, >, w).

Unlike Theorem (1.4.7)(b) in [Lov86], the machine in Theorem D does not know a priori the weight of the input. Theorem D implies that it is possible to decide in polynomial time whether x ∈ ℚ. The proof relies heavily on the Lenstra-Lenstra- Lovasz algorithm [LLL82].

A non-uniform model of computation over number fields was introduced by Adler and Beling [AB94] in the realm of linear programming. This model was used to bound the running time of a simplex algorithm, with input defined over the algebraic numbers. The running time depends (among other parameters) on the degree of the extension and on a measure related to the Height of the input.

I wish to thank Ilan Adler, Lenore Blum, Felipe Cucker, Jim Demmel, Benjamin Diament, Steve Smale, Felipe Voloch, Zhu Hui for their comments and suggestions.

Part of this work was supported by CNPq (Brasil). Another part of this work was done while visiting Mathematical Sciences Research Institute, Berkeley, CA.

2. Heights and Weights

The height function is an invariant of ℚ^{a}, the algebraic closure of the rationals, under automorphisms. It extends naturally to a projective invariant of ℙ^{n}(ℚ^{a}).

The motivation for the introduction of the height function comes from two (related) goals. One of them is counting rational points (or algebraic points) in algebraic varieties. The other goal is bounding above or below algebraic expressions.

The main standard references are Lang [Lan86, Lan97] and Silverman [Sil86]. This section is intended to be an introduction for readers not acquainted with the technicalities of the construction of the height function; those readers coming from a number-theoretical background may skip most of this section and proceed to Subsection 2.6

2.1. Heights in ℤ and ℚ. Let x ∈ ℤ. We may define H(x) = max(|x|, 1), where | · | is the ordinary absolute value. The following properties are obvious:

(H1) H(0) = H(1) = H(−1) = 1 (H2) H(xy) ≤ H(x)H(y) (H3) H(x + y) ≤ 2H(x)H(y)

The reason for writing (H3) instead of H(x + y) ≤ H(x) + H(y) will become clear below.

The function H may be extended to ℤ^{n} by putting:

H(x⃗) = max (H(x_{1}), …, H(x_{n}))

It becomes a projective invariant if one sets:

H(x_{0} : ⋯: x_{n}) = max (H(λx_{0}), ⋯, H(λx_{n}))

where λ ∈ ℚ is such that all the λx_{i} are relatively prime integers.

Note that H(x⃗) = H(1 : x_{1} : ⋯: x_{n}), so there is a close relationship between those two formulations. In the sequel, we will prefer the projective one.

We can extend the height function to rational numbers by stating:

H (\frac{p}{q}) = H(p : q)

If p and q are relatively prime, this last expression is also max(|p|, |q|). In case q_{1}, q_{2} ∈ ℤ are relatively prime, we have also:

H (\frac{1}{q_{1}} + \frac{1}{q_{2}} ) = H (\frac{q_{1} + q_{2}}{q_{1}q_{2}} )
= max (|q_{1} + q_{2}|, |q_{1}q_{2}|)
= |q_{1}||q_{2}|
= H (\frac{1}{q_{1}} ) H (\frac{1}{q_{2}} )

This is why the height of the sum needs to be bounded in terms of the product of the heights. Property (H3) is sharp, in the sense that H(1 + 1) = 2 = 2H(1)H(1).

It is natural to further generalize the height function to ℙ^{n}(ℚ) by:

H(x_{0} : ⋯: x_{n}) = max |λx_{0}|, ⋯, |λx_{n}|

and λ is chosen so that the λx_{i} are integers and relatively prime.

This is not the same as max H(x_{i}) and should not be. Indeed, the objective of introducing the Height function was to obtain reasonable estimates for expressions.

Example 1. Consider the function: f(x⃗) = ∑ x_{i}. For instance,

f(\frac{1}{2}, −\frac{1}{3}, −\frac{1}{7}, ⋯) = \frac{1}{2 × 3 × 7 ⋯}

so H(f(x⃗)) ≤ (max H(x_{i}))^{n} is almost sharp ! However, we have also the more elegant bound:

H(f(x⃗)) ≤ nH(x⃗)

The above definition of height in ℙ^{n}(ℚ) allows us to bound many integer or algebraic expressions:

Example 2. Let a(x) = a_{d}x^{d} + a_{d−1}x^{d−1} + ⋯ + a_{0} be a polynomial with rational coefficients, a(x) ≢ 0. The following bound is due to Cauchy: if α ≠ 0 is a root of a, then:

|α| > \frac{1}{1 + H(a)}

Indeed, we can assume without loss of generality (and without changing the height) that the a_{i} are relatively prime integers. Also, we can assume that a_{0} ≠ 0. If |α| < 1, a(α) = 0 implies:

|a_{0}| ≤ |a_{1}||α| + |a_{2}||α|^{2} + ⋯ + |a_{d}||α|^{d}
≤ |α|H(a)(1 + |α| + ⋯ + |α|^{d−1})
< H(a)\frac{|α|}{1 − |α|}

Hence, |a_{0}| < (H(a) + |a_{0}|)|α| and hence,

|α| > \frac{1}{\frac{H(a)}{|a_{0}|} + 1} > \frac{1}{H(a) + 1}

The height function H can be extended to the algebraic closure ℚ^{a} of the rationals. The estimate in Example 2 can be generalized to polynomials with algebraic coefficients (the actual statement is a little more subtle, see Theorem 5 below.)

Also, the height of a minimal polynomial of α can be bounded in terms of H(α) (see Corollary 4 below). In that sense, the height function will capture the ‘complexity’ of algebraic numbers.

2.2. Absolute values. In order to generalize the Height into ℚ^{a}, a few definitions are needed. First of all, let K be a finite algebraic extension of ℚ. An absolute value on K is a function

| · |_{ν} : K → ℝ_{+}

such that: (A1) |x|_{ν} = 0 ⇔ x = 0. (A2) |xy|_{ν} = |x|_{ν}|y|_{ν} (A3) |x + y|_{ν} ≤ |x|_{ν} + |y|_{ν}

If | · |_{ν} satisfies the condition (A3’) |x + y|_{ν} ≤ max(|x|_{ν}, |y|_{ν}) then | · |_{ν} is called a non-archimedian absolute value, or valuation. Otherwise, | · |_{ν} is said to be archimedian.

In the sequel, we will need to consider the set of all possible valuations of K, modulo the following equivalence: | · |_{μ} and | · |_{ν} are equivalent if and only if there are a, b > 0 such that

|x|_{ν} ≤ a|x|_{μ}^{b}
|x|_{μ} ≤ a|x|_{ν}^{b}

Each of the classes of equivalence above will make K into a metric space, with distance function d(x, y) = |x − y|_{ν}. Equivalent absolute values give rise to equivalent metric spaces. We will denote by M_{K} a (carefully chosen) system of representatives of each class of absolute values. There is precisely one class of archimedian absolute value associated to every automorphism σ of K over ℚ, namely:

|x|_{σ} = |σ(x)|

where | · | is the ordinary absolute value. The case of non-archimedian absolute values is more subtle:

Example 3. Let K = ℚ. It is a famous theorem by Ostrowski (See [Cas67]) that the absolute values of ℚ are precisely, up to equivalence:

• The usual (archimedian) absolute value |x|.

• For each prime number r ∈ ℕ, a valuation |r^{k} \frac{p}{q}|_{r} = r^{−k}, where it is assumed that r, p, q are

relatively prime integers. Furthermore, we have the product formula

∏_{ν∈M_{ℚ}} |x|_{ν} = 1

where M_{ℚ} is the set of absolute values of ℚ defined above. A generalization of this product formula will hold in the more general setting of number fields.

Example 4. Let K = ℚ[\sqrt{2}]. In this case, it is easy to show that the ring of integers of K (i.e., the set of x ∈ K s.t. f(x) = 0 for some monic polynomial f with coefficients in ℤ) is given by

𝔬_{K} = \{a + b\sqrt{2} : a, b ∈ ℤ\}

The norm N(a + b\sqrt{2}) is defined by:

N(a + b\sqrt{2}) = ∏_{σ∈Gal(K:ℚ)} σ(a + b\sqrt{2}) = a^{2} − 2b^{2}

where σ ranges over the automorphisms of K.

The units u of the ring of integers of K are characterized by the equation: N(u) = ±1. Those can be proved to be precisely the expressions of the form:

±(1 + \sqrt{2})^{r} , r ∈ ℤ

(This follows from a theorem by Dirichlet. See [BS67] Section II.4 Theorem 5, and ibid. Table 1).

The ring of integers of K is an Euclidian domain (hint: Euclidian Algorithm for the division, with ‘degree’ function |N(.)|), hence it admits a unique prime factorization

x = up_{1}^{a_{1}} ⋯ p_{s}^{a_{s}}

where p_{1}, ⋯, p_{s} are prime numbers in 𝔬_{K} and u is a unit.

If we are given x ∈ 𝔬_{K}, we can compute the prime number factorization of N(x) over ℤ:

N(x) = ±q_{1}^{b_{1}}q_{2}^{b_{2}} ⋯ q_{s}^{b_{s}}

Then for each of the q_{i}’s, two cases may arise:

Case 1: q_{i} is prime over 𝔬_{K}. This will be the case if the equation N(a + b\sqrt{2}) = q_{i} has no solution. For instance, it is easy to check by enumeration that N(a + b\sqrt{2}) ≡ 0 mod 3 has no solution, hence 3 is prime in 𝔬_{K}. In this case, 3 divides x. Also, | · |_{3} is a valuation on K and |x|_{3} = \sqrt{|N(x)|_{3}}.

Case 2: The prime number q_{i} factors over 𝔬_{K}, so that ±q_{i} = p_{i}p′_{i}. Example: −7 = (1+2\sqrt{2})(1− 2\sqrt{2}) so that p_{i} or p′_{i} divide x. There will be valuations associated to p_{i} and p′_{i}, normalized such that:

|p_{i}^{a} \frac{q}{r} |_{p_{i}} = p_{i}^{−a}

for relatively prime p_{i}, q, r.

We have also two absolute values at infinity,

|a + b\sqrt{2}|_{σ_{1}} = |a + b\sqrt{2}|
|a + b\sqrt{2}|_{σ_{2}} = |a − b\sqrt{2}|

where σ_{1} is the identity and σ_{2} : a + b\sqrt{2} ↦ a − b\sqrt{2}.

Example 5. Let K = ℚ[\sqrt{−5}]. The ring of integers of K is given by 𝔬_{K} = \{a + b\sqrt{−5}, a, b, ∈ ℤ\} and its units are ±1.

This example is interesting because 𝔬_{K} is not an Euclidian Domain. The closest we can get from prime number factorization is the primary decomposition into ideals. For instance, the ideal (3) splits in:

(3) = 𝔭_{1}𝔭_{2}

with 𝔭_{1} = (3\sqrt{−5}, 1+\sqrt{−5}) and 𝔭_{2} = (3\sqrt{−5}, 1−\sqrt{−5}). Those are prime ideals (Proof: 𝔬_{K} mod 𝔭_{1} has three equivalence classes 𝔭_{1}, 𝔭_{1} + \sqrt{−5} and 𝔭_{1} + 2\sqrt{−5}. By writing down all the possibilities for x mod 𝔭_{1} and y mod 𝔭_{1}, we conclude that xy ≡ 0 mod 𝔭_{1} implies that x or y ∈ 𝔭_{1}. Same proof for 𝔭_{2}).

To each prime ideal 𝔭, we associate the absolute value

|x|_{𝔭} = (N𝔭)^{−a}

where N𝔭 is the number of elements of the field K/𝔭 and (x) = (𝔭)^{a}(𝔭_{2})^{a_{2}} … is the prime ideal decomposition of (x) in 𝔬_{K}. This definition can be extended to K by setting |\frac{y}{z} |_{𝔭} = |y|_{𝔭} − |z|_{𝔭}.

There are also two archimedian valuations, |x| and |\overline{x}|.

General case: Let K be a number field (i.e. a finite extension of ℚ). Then its ring of integers 𝔬_{K} is a Dedekind domain (See [AM69], Chapter 9 for definitions and theory on Dedekind domains. This last fact is stated as Theorem 9.5). It is a classical result that :

Theorem 1 (Corollary 9.4 in [AM69]). In a Dedekind domain, every non-zero ideal has a unique factorization as a product of prime ideals.

This theorem was proved by Dedekind (c. 1871) in its original formulation (number fields), and later generalized to Dedekind domains by Noether (1921, 1927).

Most modern textbooks provide just an existential proof of that factorization. An effective algorithm to compute the prime ideal decomposition of a principal ideal in a number field appears in classical textbooks such as [BS67]. More recent algorithms are discussed in [Coh93].

A non-archimedian valuation | · |_{𝔭} is associated to each prime ideal 𝔭. Once we know that (x) = 𝔭_{1}^{a_{1}} ⋯ 𝔭_{s}^{a_{s}}, it is possible to compute the |x|_{𝔭_{i}}.

2.3. The product formula. Given a finite extension K of ℚ, let M_{K} be the set of absolute values constructed as in the examples above:

1. The archimedian absolute values | · |_{σ} associated to all σ ∈ Gal_{ℚ}K

2. The valuations | · |_{𝔭} associated to the prime ideals 𝔭 of 𝔬_{K}.

For each of those valuations | · |_{ν}, we can define a new metric space K_{ν} as the completion of K by the metric associated to | · |_{ν}. This completion is a field, it is indeed a (possibly infinite) field extension of K.

Example 6. The archimedian completion of the rationals is ℚ_{∞} = ℝ. The non-archimedian completion associated to prime number p is given by all sequences of the form

(q_{i}) = p^{n}(a_{0} + pa_{1} + p^{2}a_{2} + ⋯ p^{i}a_{i} + ⋯)

for n ∈ ℤ and a_{i} ∈ {0; ⋯; p − 1}.

Example 7. If K = ℚ[\sqrt{2}] then K_{∞} = ℝ. If K = ℚ[i], we have two archimedian valuations. For any of those, K_{∞} = ℂ.

If L is a finite extension of K and ν ∈ M_{K}, then ν extends to at least one absolute value ν_{0} of M_{L}.

The completion L_{ν_{0}} of L is clearly an extension of the completion K_{ν} of K. This extension turns to be finite. Indeed, let α be a primitive element of L with respect to K. A sequence (l_{i}) with values in L can always be written as l_{i} = ∑ k_{ij}α^{j}, k_{ij} ∈ K.

Definition 1. The local degree n_{ν_{0}} of the extension L : K in ν_{0} is the degree of the extension [L_{ν_{0}} : K_{ν}].

The local degrees are the multiplicity values that make the product formula true. Indeed,

Theorem 2. Let K be a number field and let M_{K} be constructed as above. Then for any x ∈ K,

∏_{ν∈M_{K}} |x|_{ν}^{n_{ν}} = 1

This fact comes from the formula

Theorem 3. Let L and K be number fields, L a finite extension of K. Let ν ∈ M_{K}. Then

∑_{ν_{0} extends ν} n_{ν_{0}} = [L : K]

For proofs, refer to [Lan97].

Example 8. Let K = ℚ[\sqrt{2}]. Let | · |_{σ_{1}} and | · |_{σ_{2}} be the archimedian absolute values. Then

n_{σ_{1}} = [K_{σ_{1}} : ℚ_{σ_{1}}] = [ℝ : ℝ] = 1

and same for n_{σ_{2}}.

As we saw, 3 is a prime in K. ℚ_{3} is the set of expressions 3^{a}(p_{0} + 3p_{1} + 3^{2}p_{2} + ⋯) with p_{i} in {0; 1; 2}. On the other hand, K_{3} is the set of expressions 3^{a}(r_{0} + 3r_{1} + ⋯) with r_{i} defined modulo 3. Possible values are 0, 1, 2, \sqrt{2}, 1 + \sqrt{2}, 2 + \sqrt{2}. So n_{3} = 2.

Now, let us compute n_{1+2\sqrt{2}}. As usual, ℚ_{7} is the set of expressions 7^{a}(p_{0} + 7p_{1} + 7^{2}p_{2} + ⋯) with p_{i} in \{0; 1; ⋯; 7\}. On the other hand, K_{1+2\sqrt{2}} contains the expressions (1 + 2\sqrt{2})^{a}(r_{0} + (1 + 2\sqrt{2})r_{1} + ⋯). Since the r_{i} are defined modulo 1 + 2\sqrt{2}, we have only 7 possible values (recall that 7 ≡ 0 and that 1 ≡ 2\sqrt{2}). Therefore K_{1+2\sqrt{2}} is indeed ℚ_{7} and n_{1+2\sqrt{2}} = 1.

2.4. Heights. Let x = (x_{0} : ⋯: x_{n}) ∈ ℙ^{n}(K), where x is a number field. If x_{0}, ⋯, x_{n} ∈ K we define relative height as:

H_{K}(x) = ∏_{ν∈M_{K}} max_{i} |x_{i}|_{ν}^{n_{ν}}

Because of the product formula, this definition is invariant with respect to multiplication of x by any λ ∈ K:

H_{K}(λx) = ∏_{ν∈M_{K}} max_{i} |λx_{i}|_{ν}^{n_{ν}} a
= ∏_{ν∈M_{K}} max_{i} |λ|_{ν}^{n_{ν}} |x_{i}|_{ν}^{n_{ν}}

= ( ∏_{ν∈M_{K}} |λ|_{ν}^{n_{ν}} ) ( ∏_{ν∈M_{K}} |x_{i}|_{ν}^{n_{ν}} )

= ( ∏_{ν∈M_{K}} |x_{i}|_{ν}^{n_{ν}} )
= H_{K}(x)

However, this definition is still not invariant under multiplication by λ ∈ ℚ^{a}, λ ∉ K. In order to obtain an invariant definition in ℚ^{a}, it is customary to set:

H(x) = H_{K}(x)^{\frac{1}{[K:ℚ]}}

In the particular case 𝔬_{K} is an Euclidian domain, we can choose representatives x_{0}, ⋯, x_{n} of (x_{0} : ⋯: x_{n}) that belong to 𝔬_{K} and are relatively prime. Afterwards, only the Archimedian absolute values of x can be different of 1.

2.5. Properties of Heights. The basic properties we stated in section 2.1 can be generalized to a convenient bound on H(f(P)) in terms of H(f) and H(P), where f is a polynomial or a system of polynomials. That bound is stated below as Theorem 4. This statement generalizes Theorem 5.6 in [Sil86]. Theorem 4 seems well-known to people working in number theory. However, the precise statement does not seem to be written down in the literature, so it will be stated and proved below. A lot of useful properties of heights will then be stated as corollaries.

Before giving the precise statement, it is convenient to clarify some notations: we will reserve the notation H(x) for the projective height of x ∈ ℙ^{n}(ℚ^{a}), as we defined in section 2.1. If we want to write down the affine height of some y ∈ (ℚ^{a})^{n} we will write instead: H(y, 1).

This convention can be extended to polynomials or systems of polynomials. If f = (f_{1}, ⋯, f_{k}) is a system of multivariate polynomials, then its height H(f) is the height of the projective point (⋯: f_{iI} : ⋯) ∈ ℙ^{S(f)−1}(ℚ^{a}). Above, S(f) = S(f_{1}) + ⋯ + S(f_{k}) where S(f_{i}) is the number of non-zero coefficients of f_{i}. Of course, when we need the ‘affine’ height of f, we will write H(f, 1).

With those conventions, we may state the

Theorem 4. Let

\begin{aligned}F = (F_{0}, ⋯, F_{m}) : & ℂ^{n_{1}} × ℂ^{n_{2}} × ⋯ × ℂ^{n_{k}} & → & ℂ^{m+1} \\ & P^{1}, ⋯, P^{k} & ↦ & F (P^{1}, ⋯, P^{k}) \end{aligned}

be a system of multi-homogeneous polynomials with algebraic coefficients, where each F_{i} has degree d_{j} in variables P^{j}. Let the P^{j} be algebraic. Then

H(F (P)) ≤ (max S(f_{i}))H(F)H(P^{1})^{d_{1}} ⋯ H(P^{k})^{d_{k}}

In the particular case k = 1, F is a morphism from ℙ^{n}(ℚ^{a}) into ℙ^{m}(ℚ^{a}) and Theorem 4 is Theorem 5.7 in [Sil86]. In the full statement, Theorem 4 generalizes that fact to morphisms from ℙ^{n_{1}}(ℚ^{a}) × ⋯ × ℙ^{n_{k}}(ℚ^{a}) into ℙ^{m}(ℚ^{a}).

The proof below is a modification of the proof of Theorem 5.6 in [Sil86].

Proof of Theorem 4. Let K ⊂ ℚ^{a} be a finite extension of ℚ, containing all the coefficients of F and all the coordinates of P. We have:

H_{K} (F (P)) = ∏_{ν∈M_{K}} max_{i} |F_{i}(P)|_{ν}^{n_{ν}} by definition
= ∏_{ν∈M_{K}} max_{i} | ∑_{J} F_{iJ}(P^{1})^{J_{1}} ⋯ (P^{k})^{J_{k}}|_{ν}^{n_{ν}}

where the J_{k} are multi-indices, |J_{j}| = d_{j} and J = (J_{1}; ⋯; J_{k}). Let ϵ(ν) be equal to 1 when ν is

archimedian, and to 0 when ν is a valuation. The triangular inequality implies now: | ∑_{1≤i≤n} a_{i}|_{ν} ≤ n^{ϵ(ν)} max |a_{i}|_{ν}. Hence.

H_{K} (F (P)) ≤ ∏_{ν∈M_{K}} S^{ϵ(ν)n_{ν}} max_{i,J} |F_{iJ}(P^{1})^{J_{1}} ⋯ (P^{k})^{J_{k}}|_{ν}^{n_{ν}}
≤ S^{∑ ϵ(ν)n_{ν}} ∏_{ν∈M_{K}} max_{i,J} |F_{iJ}(P^{1})^{J_{1}} ⋯ (P^{k})^{J_{k}}|_{ν}^{n_{ν}}
≤ S^{deg[K:ℚ]} ∏_{ν∈M_{K}} max_{i,J} |F_{iJ}(P^{1})^{J_{1}} ⋯ (P^{k})^{J_{k}}|_{ν}^{n_{ν}}

using the fact ∑_{ν} ϵ(ν)n_{ν} = ∑_{ν archimedian} n_{ν} = deg[K : ℚ].

Now, since the degree of (P^{j})^{J_{j}} is precisely d_{j}, we can write:

|(P^{j})^{J}|_{ν} ≤ max_{l} (|(P_{l}^{j})|_{ν})^{|J|}

We can use homogeneity to bound:

H_{K} (F (P)) ≤ S^{deg[K:ℚ]} ∏_{ν∈M_{K}} max_{i,J} |F_{iJ}|_{ν}^{n_{ν}} max_{l} |(P_{l}^{1})|_{ν}^{d_{1}n_{ν}} ⋯ max_{l} |(P_{l}^{k})|_{ν}^{d_{k}n_{ν}}

≤ S^{deg[K:ℚ]} ( ∏_{ν∈M_{K}} max_{i,J} |F_{iJ}|_{ν}^{n_{ν}} ) ( ∏_{ν∈M_{K}} max_{l} (|(P_{l}^{1})|_{ν})^{d_{1}n_{ν}} ) ⋯

⋯ ( ∏_{ν∈M_{K}} max_{l} (|(P_{l}^{k})|_{ν})^{d_{k}n_{ν}} )
= S^{deg[K:ℚ]}H_{K}(F)H_{K}(P^{1})^{d_{1}} ⋯ H_{K}(P^{k})^{d_{k}}

So, after taking the deg[K : ℚ]-th root, we obtain:

H(F (P)) ≤ SH(F)H(P^{1})^{d_{1}} ⋯ H(P^{k})^{d_{k}}

Also, we may want an affine version of Theorem 4:

Corollary 1. Let

\begin{aligned}G = (G_{1}, ⋯, G_{m}) : & ℂ^{n_{1}} × ℂ^{n_{2}} × ⋯ × ℂ^{n_{k}} & → & ℂ^{m} \\ & Q^{1}, ⋯, Q^{k} & ↦ & G(Q^{1}, ⋯, Q^{k}) \end{aligned}

be a system of polynomials with algebraic coefficients, where each G_{i} has degree at most d_{j} in variables Q^{j}. Let the Q^{j} be algebraic. Then

H(G(Q), 1) ≤ (max S(G_{i}))H(G, 1)H(Q^{1}, 1)^{d_{1}} ⋯ H(Q^{k}, 1)^{d_{k}}

Proof of Corollary 1. Introduce homogenizing variables q_{1}, ⋯, q_{k} so that for each G_{i}, its homogenization F_{i}(Q^{1}, q_{1}; ⋯; Q^{k}, q_{k}) has degree precisely d_{j} in variables (Q^{j}, q_{j}). Also, introduce the polynomial F_{0} = q_{1}^{d_{1}} ⋯ q_{k}^{d_{k}}. Then we have H(F) = H(G, 1). Moreover, max S(F_{i}) = max S(G_{i}). Specialize q_{1} = ⋯ = q_{k} = 1, and apply Theorem 4 to obtain

H(G(Q), 1) ≤ H(F (P))
≤ (max S(f_{i}))H(F)H(P^{1})^{d_{1}} ⋯ H(P^{k})^{d_{k}}
≤ (max S(G_{i}))H(G, 1)H(Q^{1}, 1)^{d_{1}} ⋯ H(Q^{k}, 1)^{d_{k}}

Corollary 2. Let x_{1}, …, x_{k} ∈ ℚ^{a}. Then

H(x_{1}x_{2} ⋯ x_{k}) ≤ H(x_{1})H(x_{2}) ⋯ H(x_{k})

Corollary 3. Let x_{1}, …, x_{k} ∈ ℚ^{a}. Then

H(x_{1} + x_{2} + ⋯ + x_{k}) ≤ nH(x_{1})H(x_{2}) ⋯ H(x_{k})

Corollary 4. Let α ∈ ℚ^{a} and let p(x) be the minimal polynomial of α over ℚ. Then

H(p) = H(p, 1) ≤ (2H(α))^{[ℚ[α]:ℚ]}

Proof. By definition p is an irreducible polynomial and its coefficients are relatively prime integers hence H(P) = H(P, 1).

We will use the following fact (Lemma 5.10 in [Sil86]): If ᾱ is a conjugate of α by the Galois group of ℚ^{a} over ℚ, then H(ᾱ) = H(α).

In our case, the roots of the minimal polynomial p(x) are all the conjugates of α by the Galois group of ℚ[α] over ℚ. Hence they have the same height as α.

Consider now the polynomial system:

σ(x_{1}, ⋯, x_{n}) = [ σ_{0}(x_{1}, ⋯, x_{n}) ; σ_{1}(x_{1}, ⋯, x_{n}) ; ⋮ ; σ_{n}(x_{1}, ⋯, x_{n}) ] = [ 1 ; x_{1} + ⋯ + x_{n} ; ⋮ ; x_{1} ⋯ x_{n} ]

Then σ can be interpreted as having degree at most 1 in each variable x_{j}. According to Corollary 1,

H(σ(α_{1}, ⋯, α_{n})) ≤ max S(σ_{i})H(σ, 1)H(α)^{n}

where α = α_{1}, ⋯, α_{n} are all the Galois conjugates of α. Furthermore, H(σ, 1) = 1 and S(σ_{i}) =

( \begin{matrix}n \\ i \end{matrix} ) < 2^{n}.

We can generalize the Cauchy bound in example 2 into the following statement using Heights:

Theorem 5. Let p(x) be a polynomial with algebraic coefficients, and let α be a root of p. Then

H(α) < 2H(p)

Proof of Theorem 5. Let d = deg p and assume without loss of generality that p_{d} = 1. Let K = ℚ[p_{0}, ⋯, p_{d}]. Let M_{K} be a system of absolute values of K.

We claim that if ν ∈ M_{K},

max(|α|_{ν}, 1) ≤ s + max |p_{i}|_{ν}

where s = 1 is ν is Archimedian and s = 0 otherwise. It will follow that max(|α|_{ν}, 1) ≤ (1 + s) max |p_{i}|_{ν}.

Indeed, we write

α^{d} = −p_{d−1}α^{d−1} − ⋯ − p_{0}

If ν is a valuation, this implies that

|α|_{ν}^{d} ≤ max |p_{i}|_{ν}|α|_{ν}^{i}

Hence,

max(|α|_{ν}, 1)^{d} ≤ (max |p_{i}|_{ν}) max(|α|_{ν}, 1)^{d−1}

and

max(|α|_{ν}, 1) ≤ (max |p_{i}|_{ν})

On the other hand, if ν is an Archimedian absolute value,

max(|α|_{ν}, 1)^{d} ≤ (max |p_{i}|_{ν}) ∑_{j=1}^{d−1} max(|α|_{ν}, 1)^{j}

Therefore, if |x|_{ν} > 1,

max(|α|_{ν}, 1)^{d} < (max |p_{i}|_{ν})\frac{max(|α|_{ν}, 1)^{d}}{max(|α|_{ν}, 1) − 1}

It follows at once that

max(|α|_{ν}, 1) < 1 + max |p_{i}|_{ν}

If |x|_{ν} ≤ 1, then inequality max(|α|_{ν}, 1) ≤ 1 + max |p_{i}|_{ν} is trivial.

We can now estimate the height of x:

H_{K}(x, 1) < ∏_{ν∈M_{K}}(1 + s(ν)) max |p_{i}|_{ν}^{n_{ν}}
≤ 2^{∑_{ν} n_{ν}} H_{K}(p)

where the last sum ranges over all archimedian valuations in M_{K}.

We can invoke now Theorem 3 to replace ∑_{ν} n_{ν} by [K : ℚ]. Taking roots, we obtain:

H(x) < 2H(p)

2.6. Weights.

Definition 2. Let α ∈ (ℚ^{a})^{k}. We define the weight function as:

w(α) = [ℚ[α_{1}, ⋯, α_{k}] : ℚ](1 + ⌈log_{2} H(α, 1)⌉)

Weights can be used to bound absolute values:

Lemma 1. Let α ∈ ℚ^{a}, α ≠ 0. Then 2^{−w(α)} < |α| < 2^{w(α)}.

Proof. Let K = ℚ[α]. Recall that

H_{K}(α) = ∏_{ν∈M_{K}} max(1, |α|_{ν}^{n_{ν}})

There is one archimedian valuation equal to the absolute value, so H_{K}(α) ≥ |α|. Hence H(α) ≥ |α|^{\frac{1}{[K:ℚ]}} . It follows that |α| < 2^{w(α)}. Since H(α) = H(α^{−1}), the first inequality also holds.

Theorem 6. Let x be an algebraic number, and let p be its minimal polynomial over ℚ. Let d = deg p = deg_{ℚ}(x). Then:

w(p) − 2 ≤ w(x) ≤ d(1 + w(p)) ≤ w(x)^{2}

Proof of Theorem 6. Theorem 5 implies that

w(x) ≤ d(1 + ⌈log_{2} 2H(p)⌉) ≤ d(1 + w(p))

On the other hand, Corollary 4 gives:

H(p) ≤ (2H(x))^{d}

hence

log_{2} H(p) ≤ d log_{2}(1 + H(x)) ≤ w(x)

and therefore w(p) ≤ 2 + w(x).

The hypothesis of irreducibility of p is essential here.

An interesting question is how to bound the height of an isolated root of a system of polynomial equations. We conclude this section by quoting, for further reference, the following result by Krick and Pardo:

Theorem 7 (Krick and Pardo [KP95], Corollary 6). Let f_{1}, ⋯, f_{r} r ≤ n be polynomials in ℤ[x_{1}, ⋯, x_{r}] of degree and height bounded by d ≥ n and η, respectively, and let V denote the algebraic affine variety defined by: V = {x : f_{1}(x) = ⋯ f_{r}(x) = 0}.

Then V has at most d^{n} isolated points, and their height verifies:

log_{2} H(P) ∈ d^{O(n)}(log_{2} r + log_{2} η)

3. Weighted model of Computation

3.1. Machines over a ring. Let R be a commutative ring with unity and without zero divisors. The following examples will be of interest here:

• The ring 𝔽_{2} consisting of elements 0 and 1.

• The ring ℤ of rational integers.

• The rings ℚ^{a} and ℚ^{ra} of algebraic and real algebraic numbers, resp.

• A number field K, i.e. a finite algebraic extension of ℚ. However, for simplicity, we consider K as a ring.

Also, let o be a subset of R and let c : R^{∞} → ℝ^{+} be a cost function.

Essentially, a machine M maps an input space into an output space. For input and output space, we want to allow all finite, arbitrarily large sequences in our base ring R. Those sequences are denoted by R^{∞}. (In earlier literature, the notation was R^{∗}). Eventually, we use the same notation for the machine M and for the function M : R^{∞} → R^{∞}, x ↦ M(x).

Intermediate calculations are stored in a State Space S, that can contain arbitrarily large, finite bisequences over R. This is denoted R_{∞}.

A polynomial map f : R_{∞} → R_{∞} is a finite sequence of polynomials in R_{∞}, and therefore it is described by a finite set of coefficients.

One can think of a machine as a flowchart, i.e., as a labelled directed graph consisting of nodes and edges. A first, initial node is ‘executed’. Then the machine follows and outgoing edge, and finds a new node to ‘execute’, and so on.

A machine M over (R, o, c) is a defined as a labelled directed graph Γ. The nodes of Γ, indexed 1 to N, are of the following five types:

[figure: s ← g_{γ}(s)]

\underline{Computation nodes} have exactly one outgoing edge, and Computation Node γ is associated to a (finite) polynomial system g_{γ} : S → S. The effect of executing γ is to ‘replace’ s ∈ S by g_{γ}(s) ∈ (S). Replacing means the following. Suppose that g_{γ} = (g_{−1}, g_{0}, g_{1}, g_{2}) where each of the g_{−1}, …, g_{2} is a polynomial in s. Then we replace s_{−1}, …, s_{2} by the values of g_{−1}(s), …, g_{2}(s) and leave all the other coordinates invariant:

⋯ s_{−3}  s_{−2}  s_{−1}  s_{0}  s_{1}  s_{2}  s_{3} ⋯

f_{γ}

⋯ s_{−3}  s_{−2} g_{−1}(s) g_{0}(s) g_{1}(s) g_{2}(s) s_{3} ⋯

\underline{Branching nodes} have exactly two outgoing edges labelled TRUE and FALSE, and Branching Node γ is associated to the expression s_{0} ∈ o. Execution branches accordingly.

[figure: s_{0} ∈ o; FALSE; TRUE]

[figure: s ← I(Input)] The \underline{Input node} has exactly one outgoing edge, and is associated to the input map I : I → S. I just copies the input into non-negative positions in the state space. Input node is indexed 1.

i_{0}  i_{1}  i_{2}  i_{3} ⋯
I

⋯  0  0  0  i_{0}  i_{1}  i_{2}  i_{3} ⋯

The \underline{Output node} has one outgoing edge to itself, and is associated to an output map O : S → O. O copies the non-negative state space into the output space. The output node is indexed N.

[figure: Output O(s)]

⋯ s_{−3}  s_{−2}  s_{−1}  s_{0}  s_{1}  s_{2}  s_{3} ⋯
O

s_{0}  s_{1}  s_{2}  s_{3} ⋯

Fifth node [figure: ⟳]

The \underline{Fifth node} shifts s ∈ S by 1 to the left or to the right.

⋯ s_{−3}  s_{−2}  s_{−1}  s_{0}  s_{1}  s_{2}  s_{3} ⋯ ⋯ s_{−2}  s_{−1}  s_{0}  s_{1}  s_{2}  s_{3}  s_{4} ⋯

The formal definition goes as follows: Let M be a machine with input x, and let γ_{0} be the input node. Let β(γ) denote the node associated to the outgoing edge of γ if γ is not a decision node. In case γ is a decision node, set β_{true} and β_{false} be the corresponding nodes. Let σ_{left} and σ_{right} be the left shift and right shift, respectively. We can define the recurrence:

s^{t+1} ← \{ \begin{matrix}g_{γ^{t}}(s^{t}) & if γ^{t} is a computation node. \\ σ_{right}(s^{t}) & if γ^{t} is a right shift node. \\ σ_{left}(s^{t}) & if γ^{t} is a left shift node. \\ s^{t} & otherwise \end{matrix}

γ^{t+1} ← \{ \begin{matrix}β_{true}(γ^{t}) & if γ^{t} is a decision node and s_{0}^{t} ∈ o. \\ β_{false}(γ^{t}) & if γ^{t} is a decision node and s_{0}^{t} ∉ o. \\ β(γ^{t}) & Otherwise. \end{matrix}

(R_{1})

with initial condition

\begin{aligned}γ^{1} & = γ \\ s^{1} & = I(x) \end{aligned} (R_{2})

Definition 3. The machine M with input x stops after T steps if γ^{T} is an output node. The output, also denoted as M(x), is O(s^{T}). The function x ↦ M(x) is called the input-output mapping, and is defined only for those x such that the machine stops at some time T. The set Ω_{M} = {x : M(x) stops} is said to be the set recognized by machine M, or ‘halting set’ of M.

Definition 4. A set X ∈ K^{∞} belongs to class re over (K, o, w) if and only if it is the halting set of a machine over (K, o, w). A set X belongs to class r if both X and its complement are in class re

Note that the definitions of classes re and r do not depend on the weighting function. They do depend on the branching set o.

Sets in the class r are also said to be ‘decidable’. Indeed, it is easy to construct a machine that ‘decides’ a set X ∈ r, i.e., M(x) = 0 for x ∈ X and 1 otherwise, in finite time.

Definition 5. The size of some x ∈ R^{k} ⊂ R^{∞} is defined as:

Size (x) = kc(x)

Definition 6. The cost or running time of computing M(x) is

Cost (M, x) = T max c(s_{j}^{t}) + Size (M(x))

where T is the number of steps (formally, T = min t s.t. γ^{t} is an output node) and s is the vector of all s_{j}^{t} for all values of j ∈ ℤ and t ∈ ℕ. Note that it suffices to take 1 ≤ t ≤ T and −t−m ≤ j ≤ t+m where m is the maximum of the length of input x and a constant depending on the machine M.

Definition 7. A machine M is polynomial time if and only if there are constants a, b such that for any x, if M(x) is defined, then

Cost (M, x) ≤ a(Size x)^{b}

By defining the size of the input as in Definition 5 for the cost function c(x) = w(x), the sum:

k, x_{1}, ⋯, x_{k} ↦ ∑_{i=1}^{k} x_{i}

can be performed in polynomial time. If we had defined the size as k max c(x_{i}) instead, with c = w, the weight of the output (and of intermediate results) would be exponentially large in the input size.

The motivation for including the size of the output in the definition of the cost is the following property: Under the definitions above, if M and N are polynomial time machines, their composition M ∘ N is also polynomial time.

Definition 8. Two machines M and M′ are polynomially equivalent if and only if they have the same input-output map and the running time of computing M(x) and M′(x) are related by

Cost (M, x) ≤ aCost (M′, x)^{b}
Cost (M′, x) ≤ aCost (M, x)^{b}

where a and b are constants depending on M and M′ only.

The definition of ‘machine’ given above corresponds to a ‘machine in normal form’ in the terminology of [BCSS98]. It is easy to see that for any machine in the sense of [BCSS98] there is a polynomially equivalent machine in ‘normal form’.

Moreover, given M, there is a polynomially equivalent machine M′ with all polynomials g_{γ} of the form s_{0} ← x + y or s_{0} ← x − y or s_{0} ← xy where x and y can be state variables s_{j} or constants.

It is easy to see that for any machine M, there is a constant C_{M} independent of the input such that max_{i,t} w(s_{i}^{t}) ≤ C_{M} max_{i,t} w((s′)_{i}^{t}) where s′ corresponds to an equivalent machine with the restrictions above.

3.2. The register equations. Assume a model (R, o, c) of computation. As in [BSS89] or [BCSS98], the recurrence (R_{1}-R_{2}) can be rewritten in a more concise form

\{ \begin{matrix}s^{t+1} & = & G_{t}(γ^{t}, s^{t}) \\ γ^{t+1} & = & B(γ^{t}, χ(s_{0}^{t})) \end{matrix} (R’)

with initial conditions γ^{1} = 1 and s^{1} = I(x). Above, G_{t} and B are polynomials and χ is the characteristic function of the branching-set o:

In the ordered case, χ(x) = 1 if x > 0 and 0 otherwise. In the unordered case, χ(x) = 1 if x = 0 and 0 otherwise. For a p-adic analogue, see [MW97].

Polynomials G_{t} and B are polynomials with coefficients in the field of fractions of R. They can be constructed explicitly. Assume that the machine M has N nodes.

Let p(i, j) be the N-th Lagrange interpolating polynomial:

p(i, j) = \frac{∏_{1≤j≤N,k≠j}(i − k)}{∏_{1≤j≤N,k≠j}(j − k)}

This is a degree N polynomial in i. If j ∈ {1; ⋯ N}, its denominator divides N − 1 !. If i, j ∈ {1; ⋯ N} then p(i, j) = 1 if i = j and zero otherwise.

Let

g_{i}^{t}(s) = \{ \begin{matrix}g_{i}(s) & if i is a computation node \\ s_{−t+1}, ⋯, s_{t+1} & if i is a left shift node \\ s_{−t−1}, ⋯, s_{t−1} & if i is a right shift node \\ Empty polynomial & otherwise \end{matrix}

Then we can set:

G_{t}(γ, s) = ∑_{i=1}^{N} p(γ, i)g_{i}^{t}(s)

Also, if we set

β(i, χ) = \{ \begin{matrix}β(i) & if i is not a branching node \\ χβ_{true}(i) + (1 − χ)β_{false}(i) & if i is a branching node \end{matrix}

then we can set

B(γ, χ) = ∑_{i=1}^{N} p(γ, i)β(i, χ)

It is also possible to rewrite (R’) as a system of algebraic equations with coefficients in R, by introducing new variables u^{t} and v^{t}:

\{ \begin{matrix}N − 1 !s^{t+1} & = & N − 1 !G_{t}(γ^{t}, s^{t}) \\ N − 1 !γ^{t+1} & = & N − 1 !B(γ^{t}, u^{t}) \end{matrix} (R_{1}”)

In the ordered case o = {x ∈ R : x > 0}, variables u^{t} should satisfy:

\{ \begin{matrix}s_{0}^{t} (1 − s_{0}^{t}(v^{t})^{2}) (1 + s_{0}^{t}(v^{t})^{2}) & = & 0 \\ u^{t} − s_{0}^{t}(v^{t})^{2} & = & 0 \end{matrix} (R_{2a}”)

In the unordered case o = {0}, one needs instead:

\{ \begin{matrix}s_{0}^{t}(1 − s_{0}^{t}v^{t}) & = & 0 \\ u^{t} − s_{0}^{t}v^{t} & = & 0 \end{matrix} (R_{2b}”)

We may summarize all this as:

Theorem 8. Let M be a machine (in normal form) over (R, =, w) for any R or over (ℚ^{ra}, >, w). Let N be the number of nodes of M. Then there are systems φ_{T} of polynomial equations such that (γ^{t}, s^{t}) satisfy equation (R”) for t = 1, ⋯, T if and only if there are u_{j} ∈ ℤ, v_{j} such that v_{j}^{2} ∈ R, such that φ_{T} (γ, s, u, v) = 0. Moreover

1. The number of equations is ≤ 4T (2T + 1 + C) where C is a constant depending on M.

2. The coefficients of φ_{T} are all in R.

3. deg φ_{T} ≤ max(max_{γ}(deg f_{γ}) + N − 1, 7)

4. The number of non-zero coefficients in each equation of φ_{T} is bounded by (N − 1) ∑_{γ} S(g_{γ}) where S(g) is the number of non-zero coefficients of g and the sum ranges over all the computation nodes.

5. The height of the coefficients of φ_{T} is bounded by N!2^{N}H(M), where H(M) is the height of the vector of all the coefficients of each g_{γ}.

6. H(u) = 1 and H(v_{j}^{t}) ≤ \sqrt{H(s)}, H(γ) ≤ N. Moreover, u ∈ \{−1; 0; 1\} and v ∈ R or v^{2} ∈ R, respectively.

This extends Theorem 2 in Chapter 3 of [BCSS98] to the weighted model.

3.3. Non-deterministic machines.

Definition 9. Let (R, o, c) be a model of computation. Let X ⊂ R^{∞}. The set X belongs to the class P over (R, o, c) if and only if there are a machine M with input x and constants a, b such that

x ∈ X ⇔ M(x) = 1

and for any x ∈ R^{∞}, M(x) is defined and the cost of computing M(x) is bounded above by a(w(x)Length(x))^{b}

The class P stands for Polynomial Time. A lot of sets are known to belong to the possibly larger class N P (Nondeterministic Polynomial Time). Those are the sets that can be recognized by a ‘nondeterministic’ machine.

A non-deterministic machine M to recognize a set X is allowed to input some x and a guess g. If x belongs to the set X, then there is a guess that makes M(x; g) = 1. Moreover, this computation can be performed in polynomial time with respect to the size of x (for at least one guess). On the other hand, given any guess g, if M(x; g) = 1 then x ∈ X. More formally:

Definition 10. Let (R, o, c) be a model of computation. Let X ⊂ R^{∞}. The set X belongs to the class N P over (R, o, c) if and only if there are a machine M with inputs x and g and constants a, b such that:

1. ∀x ∈ R^{∞}, x ∈ X ⇔ ∃ g s.t. M(x; g) = 1

2. ∀x ∈ X, ∃ g s.t. M(x; g) = 1 and Cost(M(x; g)) ≤ a(w(x)Length(x))^{b}

A now classical example is Hilbert Nullstellensatz over unit cost models (See [BCSS98] Ch. 5). Let HN(K) be the set of all the (r, s, f_{1}, ⋯, f_{r}) where f_{i}’s are polynomials in x_{1}, ⋯, x_{s} in sparse representation, and where there is x ∈ K^{s} s.t. f_{1}(x) = ⋯ = f_{r}(x) = 0

In the unit cost model, the weight of x does not need to be polynomially bounded by the length of the input (r, s, f_{1}, ⋯, f_{r}). (Theorem 7 seems quite sharp). However, this is necessary in the weighted-cost model, so we need to give another example of a N P set. That example will be a subset of the Nullstellensatz, obtained by intersecting the Yes-set of the Nullstellensatz with a set in P.

3.4. The 3-Nullstellensatz problem.

Definition 11. The restricted 3-Nullstellensatz problem over ℚ^{ra}, or HN3 for short, is the set of all (m, n, a, f_{1}, ⋯, f_{m}) where

1. m, n and a are integers, in unary representation (i.e., they are represented by a sequence of 1’s terminated by a 0. This representation has the following feature: the ‘bit-size’ of a is now a).

2. f_{1}, ⋯, f_{m} are polynomials in variables x_{1}, ⋯, x_{n}, of the form:

f_{i}(x) = x_{j_{i}} − (x_{k_{i}} \{ \begin{matrix}+ \\ − \\ × \end{matrix} \}x_{l_{i}} )

or of the form

f_{i}(x) = x_{j_{i}} − constant

3. There is x in (ℚ^{ra})^{n} so that f(x) = 0 and the size of a multiple of the minimal polynomial of each x_{i} is < a.

It is also very natural to rewrite conditions 1 and 3 in terms of a few extra polynomial equations, with integer (and uniformly bounded) coefficients. This leads to an interpretation of HN3 as a subset of HN. There are no heights in the new definition.

Lemma 2. HN3 is in N P over (ℚ^{ra}, >, w).

Proof of Lemma 2. We consider the machine N = N(m, n, a, f_{1}, ⋯, f_{m}; x_{1}, ⋯ x_{n}, p_{1}, ⋯, p_{m}). The last part of the input (the x_{i}’s and the p_{i}’s should be interpreted as the guess in a nondeterministic machine). The machine N will check in polynomial time the following facts:

1. f_{i}(x) = 0 for all i.

2. p_{i}(x_{i}) = 0

3. The bit-size of p_{i} is smaller than a.

Clearly, if the answer is yes to all the 3 items, then (m, n, a, f) ∈ HN3. On the other hand, if (m, n, a, f) ∈ HN3, then the bit-size of the minimal polynomials of each of the x_{i}’s is bounded by a; furthermore, due to Theorem 6, w(x_{i}) is polynomially bounded, hence steps 1 to 3 can be performed in polynomial time on (m, n, a, f).

Theorem 9. HN3 is N P-Complete over (ℚ^{ra}, >, w).

It follows from Lemma 9 that both HN3 and HN are N P-hard over (ℚ^{ra}, >, w). However, HN is not likely to be in N P. Indeed, the usual ‘guess’ for a nondeterministic machine in the unit cost model is the solution of the equations; that solution can have a very large weight. (The bound in Theorem 7 seems to be quite sharp). Therefore, building a nondeterministic polynomial time machine to check HN seems a difficult, maybe impossible task.

Proof of Theorem 9. Let X ∈ N P be recognized by the ‘nondeterministic’ machine M = M(x; g) in time < a size(x)^{b}.

Let T = a(length(x) max W (x_{i}))^{b} where W is a weight estimator, i.e., a polynomial time function satisfying:

w(x) ≤ W (x) ≤ poly(w(x))

Existence of the weight estimator follows from Theorem D). Therefore, machine M does terminate in time ≤ T.

Let Φ^{T} (x; g, s, u, v) be the register equations (R”). This is a system in g, s, u, v, since x is fixed. Clearly, there is a polynomial time machine R_{1} that given T, x, produces the system R_{1}(T, x) =

Φ^{T} (x; g, s, u, v)

Also, there is a polynomial time machine R_{2} that transforms a system φ(z) into a HN3 sort of system (R_{2}φ)(ẑ); φ has a solution z if and only if R_{2}φ has a solution ẑ. Moreover, because of Corollary 1, max w(z_{j}) and max w(ẑ_{j}) are related as follows:

max w(z_{j}) ≤ max w(ẑ_{j}) ≤ max w(z_{j})^{A}

We consider the reduction x ↦ R(x) = R_{2}(R_{1}(T (x), x)). If x ∈ X, then R(x) has a solution of weight < T^{A}, so the bit-size of the minimal polynomials of the solutions is bounded by T^{2A}.

Reciprocally, if R(x) has a solution ẑ, then Φ^{T} (x; g, s, u, v) = 1 and hence there is g s.t. M(x, g) = 0. This implies x ∈ X.

The situation over (ℤ, =, w) is interesting too. The set ℕ is clearly in N P over that model, since it is possible to guess the ‘bits’ of a number x and then decide if x ≥ 0. (A similar argument works with (ℤ, =, 1)) [BSS89].

However, assume that the τ-conjecture [Sma98] is true. Then it is hard to decide x ∈ {1; ⋯; n}. The input size is defined as log n, both for unit cost or for logarithmic cost. Hence ℕ ∉ P with any of those cost models. Thus, the τ-conjecture implies P ≠ N P over (ℤ, =, w).

4. A transfer theorem for the P ≠ N P Conjecture

.

4.1. Morphisms and Transfer Theorem. Let (R_{1}, o_{1}, c_{1}) and (R_{2}, o_{2}, c_{2}) be models of computation. We do not assume R_{2} to be an extension of R_{1} or whatsoever. Instead, we will relate those models by a partial mapping of the form

σ : R_{1} ← R_{2}^{k}

with k ∈ ℕ ∪ {∞}. This mapping will be used to ‘embed’ the model of computation (R_{1}, o_{1}, c_{1}) into the model of computation (R_{2}, o_{2}, c_{2}).

This ‘covariant’ language calls for an explanation: one of the main features of this ‘embedding’ should be to allow for the simulation of machines in (R_{1}, o_{1}, c_{1}) by machines in (R_{2}, o_{2}, c_{2}). In that case, elements of R_{1} should be represented by sequences of elements in R_{2}.

For instance, if R_{1} = ℤ and R_{2} = 𝔽_{2}, then an integer in R_{1} should be represented by a sequence of bits (i.e. a finite sequence in 𝔽_{2}).

If x ∈ R_{1}, the set σ^{−1}(x) will contain all the valid representations of x. Not all the possible lists of elements of R_{2} need to make sense, hence σ can be a partial map.

Moreover, representation of a given x ∈ R_{1} does not need to be unique. For instance, if R_{1} = ℚ^{ra} is the ring of real algebraic numbers, and R_{2} = ℤ, then x ∈ R_{1} may be represented by its minimal polynomial, together with a good approximation of x (In the sense of Theorem C).

By the use of coupling functions, σ can be naturally extended to a map R_{1}^{∞} ← R_{2}^{∞}. We will use the same name for σ and for its extension, and specify domain and range when necessary.

An important conceptual point should be stressed: σ is a map, not a computable map. It makes no sense to ‘compute’ σ in some model of computation. This map is introduced so we can work ‘in coordinates’, much as in linear algebra or differential geometry. Of course, since σ should transfer a certain ‘computable polynomial time’ structure from one model of computation into another, a few constraints will be necessary.

Let us fix the notation Size_{i}(x) = Length(x)c_{i}(x) for x a sequence in (R_{i}, o_{i}, c_{i}) and i = 1, 2.

Definition 12. A map φ : (R_{1})^{∞} ⊇ X → Y ⊆ (R_{2})^{∞} is polynomially bounded if and only if there are a, b such that for any x ∈ X,

Size(φ(x)) < aSize(x)^{b}

A reciprocal of the condition of ”polynomially bounded” will be often necessary. This motivates the definitions below:

Definition 13. A map σ : R_{1}^{∞} ← R_{2}^{∞} is honest over Y ⊂ R_{1}^{∞} if and only if there are a, b > 0 such that

∀y ∈ Y, ∃x ∈ σ^{−1}(y) such that Size_{1}(x) < a Size_{2}(y)^{b}

A map will said to be honest if and only if it is honest over its image.

This definition is closely related to the one of a honest map on a set X, in Chapter 5 of [BCSS98]. Here, we do not require honest maps to be computable. It is possible also to define

Definition 14. A map σ : R_{1}^{∞} ← R_{2}^{∞} is honest on X ⊂ R_{2}^{∞} if and only if there are a, b > 0 such that

∀x ∈ X, such that Size_{1}(x) < a Size_{2}(σ(x))^{b}

Clearly, a map σ honest on X is always honest over σ(X). Also, a map σ honest over Y is always honest on some X contained in σ^{−1}(Y).

An example: the projection π : R^{2} → R, (x, y) ↦ x is honest over R but is not honest on R^{2}. However it is honest on {(x, y) s.t. Size(x) < ai Size(y)^{b}} for a and b fixed.

An alternative definition for the class N P over (R, o, c) can be given in terms of honest maps. The statement below is somewhat simpler than Proposition 2 in Chapter 5 of [BCSS98]. However, only one direction seems to be valid in general:

Proposition 1. Let a model of computation (R, o, c) be fixed. Let Y be a set of R^{∞}. If there exist a set X ∈ P and a honest map φ over Y, computable in polynomial time, and such that φ(X) = Y, then the set Y is in N P over (R, o, c).

The proof is immediate, so it is omitted. The reciprocal is true (and easy) when c = 1. A candidate counterexample for the reciprocal over (ℚ^{ra}, =, w) is the following set: {(k, x_{1}, ⋯, x_{k}) : x_{i} ≥ 0}. Obvious guesses are the square roots of the x_{i}’s, but the weight of the guess vector may be exponential in the input size.

In order to transfer ‘computable polynomial time’ structure from the model of computation (R_{1}, o_{1}, c_{1}) into the model of computation (R_{2}, o_{2}, c_{2}), we can still follow the analogy with differential geometry and define the ‘pull-back’ by σ of computable functions and machines over (R_{1}, o_{1}, c_{1}).

Definition 15. Let σ : (R_{2})^{∞} → (R_{1})^{∞} and let f be a n-ary function,

\begin{aligned}f : & (R_{1})^{n} & → & R_{1} \\ & y_{1}, ⋯ y_{n} & ↦ & f(y_{1}, ⋯, y_{n}) \end{aligned}

Then a function f^{∗} : (R_{2})^{∞} → (R_{2}i)^{∞} is a pull-back of f if and only if,

∀x_{1}, ⋯ x_{n} ∈ R_{2}, σ(f^{∗}(x_{1}, ⋯, x_{n})) = f(σ(x_{1}), ⋯, σ(x_{n}))

The pull-back of a function does not need to be unique. A similar definition, this time unique, can be produced for a total function g from R into {0, 1}: (i.e. a set): its pull-back g^{∗} is the unique function such that g^{∗}(x) = g(σ(x)). For example, ‘y ∈ o_{1}’ has pull-back ‘σ(x) ∈ o′_{1}.

We can summarize that information in the following commutative diagrams:

\xymatrix{(R_{2})^{∞} \ar[r]^{(σ,σ,···σ)} \ar@{.>}[d]_{f^{∗}} & (R_{1})^{n} \ar[d]^{f} & (R_{2})^{∞} \ar[r]^{σ} \ar@{.>}[dr]_{g^{∗}} & R_{1} \ar[d]^{g} \\ (R_{2})^{∞} \ar[r]_{σ} & R_{1} &  & \{0; 1\}}

It is also reasonable to speak of the pull-back of a machine. We will need the following condition in the sequel:

Definition 16. Let σ : R_{1}^{∞} ← R_{2}^{∞}. We say that σ has the pull-back property if and only if for any machine M over (R_{1}, o_{1}, c_{1}) there are a, b > 0 and a machine M^{∗} over (R_{2}, o_{2}, c_{2}) such that

1. The function computed by M^{∗} is a pull-back of the function computed by M.

2. Cost (M^{∗}, x) < a Cost(M, σ(x))^{b}

It is now clear that

Lemma 3. Let σ : R_{1}^{∞} ← R_{2}^{∞} is polynomially bounded and has the pull-back property. Then Y ∈ P over (R_{1}, o_{1}, c_{1}) implies that its preimage σ^{−1}(Y) is in P over (R_{2}, o_{2}, c_{2})

If M is a nondeterministic polynomial time machine, the situation is more subtle: Guesses g taken by M should correspond to guesses g′ taken by the pull-back, so that g = σ(g′) and the size of g′ is polynomially bounded on the size of g. Moreover, it is necessary to ensure that the guess g′ is indeed in the domain of σ.

Definition 17. A morphism from (R_{1}, o_{1}, c_{1}) into (R_{2}, o_{2}, c_{2}) is a polynomially bounded, partial mapping σ : R_{1} ← R_{2}^{k}, with k ∈ ℕ ∪ {∞}, so that: (M1) σ is surjective. (M2) σ is honest. (M3) The domain of definition of σ belongs to N P over (R_{2}, o_{2}, w_{2}). (M4) σ has the pull-back property.

The main feature of morphisms is to allow for a ‘transfer’ of the class N P (and of the class P, also).

Lemma 4. Let σ be a morphism from (R_{1}, o_{1}, c_{1}) into (R_{2}, o_{2}, c_{2}). Let X be in N P over (R_{1}, o_{1}, c_{1}). Then σ^{−1}(X) is in N P over (R_{2}, o_{2}, c_{2})

Proof of Lemma 4. Let M = M(x, g) be a nondeterministic polynomial time machine to recognize X. Let M^{∗} be a pull-back of M by σ, and let Y = σ^{−1}(X).

If y ∈ Y, then σ(y) ∈ X and there is a guess g such that M accepts σ(y) in polynomial time (with respect to the size of σ(y)). Since σ is polynomially bounded, σ(y) is accepted in polynomial time with respect to the size of y indeed.

Since σ is surjective, there is g′ in σ^{−1}(g) such that M^{∗}(y, g′) ‘accepts’ y in polynomial time, again with respect to the size of y.

It is necessary to take a closer look at the preimage g′ of the guess g. It can be decomposed into sub-guesses g′_{1}, ⋯, g′_{s} ∈ (R_{2})^{∞}, such that for each coordinate g_{i} ∈ R_{1} of g, we have:

σ(g′_{i}) = g_{i}

By Hypothesis (M2) we can assume without loss of generality that Size_{2}(g′_{i}) < Size_{1}(g_{i}) = c_{1}(g_{i}). Moreover, since M is polynomial time w.r.t. Size_{2}(y), c_{1}(g_{i}) is polynomially bounded w.r.t. Size_{2}(y).

By Hypothesis (M3), there is a non-deterministic polynomial time machine D = D(z, g′′) that recognizes the domain of σ. Setting z = g′_{i}, one can use D to recognize valid guesses g′_{i} is nondeterministic polynomial time w.r.t. Size_{2}(y).

We define a machine N as follows: N inputs y and guesses g′, g′′_{i}. It first tests D(g′_{i}, g′′_{i}). If all tests succeed (i.e. g′ is in the domain of σ), the machine tests M^{∗}(y, g′) and returns ‘Yes’ on success.

Clearly, if y ∈ Y, there will be guesses g′ and g′′ such that N(y, g′, g′′) will succeed in polynomial time w.r.t. Size_{2}(y).

Assume now that y gets accepted by N, with guess (g′, g′′). Then g′ was accepted by D, hence g′ is in the domain of definition of σ and g = σ(g′) is well-defined. It follows from the pull-back property that M accepts σ(y), with guess g. Hence, y ∈ Y.

A few remarks:

Remark 1. Identity is a morphism from (R_{1}, o_{1}, c_{1}) into itself.

Remark 2. The composition of two morphisms is again a morphism

Remark 3. In order to define a Category, we should specify the objects. Those can be chosen to be the class of all (R, o, c) where R is a commutative ring with unity and no zero divisors, o is a proper subset of R and c is a function from R into the positive reals. One can also restrict this to o = {0} or to reasonable cost functions in some sense...

Remark 4. The usual category theory functors do not seem to make any sense in this context. However, the word morphism was selected in absence of a better name. P-morphisms are taken, maybe N P-morphisms would be a good name ?

Of the properties in the definition of morphisms, the pull-back property may be the hardest to check. In some conditions, it may be enough to check the pull-back condition for a few basic functions:

Definition 18. A map σ : R_{1}^{∞} ← R_{2}^{∞} is very honest over Y ⊂ R_{1}^{∞} if and only if there are a, b > 0 and a polynomial time machine S over (R_{2}, o_{2}, c_{2}) such that σ(x) = σ(S(x)) and,

∀x ∈ σ^{−1}(Y), Size_{1}(S(x)) < aSize_{2}(σ(x))^{b}

A map is ‘very honest’ if and only if it is very honest over its image.

Clearly, a very honest map is always honest; the machine S can be seen as a simplification procedure for the representation x of some y = σ(x).

Lemma 5. Let σ be a very honest map, such that the following functions have a polynomial time pull-back: x, y ↦ x + y, x, y ↦ xy, x ↦ −x, x ↦ (x ∈ o_{1}). Then σ has the pull-back property.

We can now define the following relation of equivalence between two models:

Definition 19. Computation models (R_{1}, o_{1}, c_{1}) and (R_{2}, o_{2}, c_{2}) are polynomially equivalent if and only if there are morphisms:

σ_{1} : (R_{1}, o_{1}, c_{1}) → (R_{2}, o_{2}, c_{2})
σ_{2} : (R_{2}, o_{2}, c_{2}) → (R_{1}, o_{1}, c_{1})

such that:

(T1) There is a polynomial time machine A_{1} over (R_{1}, o_{1}, c_{1}) such that σ_{1} ∘ σ_{2} ∘ A_{1} is the identity

in (R_{1})^{∞}. (T2) There is a polynomial time machine A_{2} over (R_{2}, o_{2}, c_{2}) such that σ_{2} ∘ σ_{1} ∘ A_{2} is the identity

in (R_{2})^{∞}.

[figure: R_{1}; Id; A_{1}; (R_{2})^{∞}; σ_{1}; (R_{1})^{∞}; σ_{2}; R_{2}; Id; A_{2}; (R_{1})^{∞}; σ_{2}; (R_{2})^{∞}; σ_{1}]

We can now state a transfer theorem:

Theorem 10. Let computation models (R_{1}, o_{1}, c_{1}) and (R_{2}, o_{2}, c_{2}) be polynomially equivalent. Then P ≠ N P over (R_{1}, o_{1}, c_{1}) if and only if P ≠ N P over (R_{2}, o_{2}, c_{2}).

Note that Theorem 10 does not require the existence of a N P-complete problem over any of (R_{1}, o_{1}, c_{1}) or (R_{2}, o_{2}, c_{2}).

It is clearly enough to prove only one sense, viz. P ≠ N P over (R_{1}, o_{1}, c_{1}) implies P ≠ N P over (R_{2}, o_{2}, c_{2}).

Proof of Theorem 10. Assume that P ≠ N P over (R_{1}, o_{1}, c_{1}).

Step 1: By hypothesis, there is a problem X that is in N P over (R_{1}, o_{1}, c_{1}), but not in P. Step 2: Let Y = σ_{1}^{−1}(X). Y is in N P over (R_{2}, o_{2}, c_{2}) (Lemma 4). Step 3: Assume by absurd that P = N P over (R_{2}, o_{2}, c_{2}). Then Y is in P over (R_{2}, o_{2}, c_{2}). Step 4: Z = σ_{2}^{−1}(Y) is in P over (R_{1}, o_{1}, c_{1}) (Lemma 3). Step 5: Z contains the image of X by the polynomial time machine A_{1} of property (T1). Step 6: On the other hand, if A_{1}(x) is in Z, then x is in X. Step 7: Therefore, machine A_{1} reduces the decision of membership in X to membership in Z.

This later problem can be solved in polynomial time. Hence P = N P over (R_{1}, o_{1}, c_{1}), contradiction.

As a matter of fact, the same proof shows a more general, weaker statement:

Theorem 11. Let (R_{1}, o_{1}, c_{1}) and (R_{2}, o_{2}, c_{2}) be computation models, such that there exist mappings

σ_{1} : (R_{1}, o_{1}, c_{1}) → (R_{2}, o_{2}, c_{2})
σ_{2} : (R_{2}, o_{2}, c_{2}) → (R_{1}, o_{1}, c_{1})

such that σ_{1} is a morphism, σ_{2} is a polynomially bounded partial mapping that has the pull-back property (M4). Assume that (T1) holds. Then P ≠ N P over (R_{1}, o_{1}, c_{1}) implies P ≠ N P over (R_{2}, o_{2}, c_{2}).

A further remark: the technology of Theorem 10 allows to transfer the P ≠ N P Conjecture between models where R_{1}^{∞} and R_{2}^{∞} have same cardinality.

This is different from the argument in [BCSS98] for transferring between algebraic and complex numbers, that used Tarski’s strong transfer principle.

4.2. Examples.

Proposition 2. Models (ℤ, ≥, w) and (𝔽_{2}, =, 1) (the Turing model) are polynomially equivalent.

Proof of Proposition 2. Let

\begin{aligned}b : & 𝔽_{2}^{∞} & → & ℤ \\ & (s, 0, x_{1}, 0, ⋯, x_{k}, 1) & ↦ & (−1)^{s} ∑_{i=0}^{k} 2^{i}x_{i} \end{aligned}

This is clearly a morphism from (ℤ, ≥, w) into (𝔽_{2}, =, 1). We can also define a morphism from (𝔽_{2}, =, 1) into (ℤ, ≥, w) by:

i : ℤ ⊇ {0; 1} → 𝔽_{2}
0 ↦ 0
1 ↦ 1

Machines A_{1} and A_{2} are essentially similar. They associate to any input x its binary expansion. In the case of A_{2}, the input x is supposed to belong to 𝔽_{2}, hence the only possible values are 0 and 1. In the case of A_{1}, x ∈ ℤ.

Since i ∘ b ∘ A_{2} and b ∘ i ∘ A_{1} are the identity in 𝔽_{2} and in ℤ respectively, those two models are polynomially equivalent.

Proposition 3. Models (ℚ, ≥, w) and (ℤ, ≥, w) are polynomially equivalent.

Proof of Proposition 3. In the same spirit, we define:

\begin{aligned}b : & ℤ^{2} ⊇ ℤ × ℤ_{∗} & → & ℚ \\ & p, q & ↦ & \frac{p}{q} \end{aligned}

\begin{aligned}i : & ℚ ⊇ ℤ & → & ℤ \\ & x & ↦ & x \end{aligned}

Then we have to define A_{1} : x ↦ (x, 1) and A_{2} : p/q ↦ (p, q) where p and q are relatively prime. This last machine will just perform Euclidian algorithm (For its running time, see the discussion in [Knu98] Section 4.5.3)

4.3. Is x ≥ 0 hard ? Towards the proof of Theorem B, we will assume Theorem C and show its Corollary:

Corollary 5. The set ℚ^{ra} is in N P over the algebraic numbers (ℚ^{a}, =, w)

Proof of Corollary 5. Given x ∈ ℚ^{a}, guess y(x) where y is the function defined in Theorem C. Then compute a 2^{−k}-approximation of x, of the form a + bi. By Theorem C, b = 0 if and only if x is real.

Lemma 6. P ≠ N P over (ℚ^{ra}, =, w) implies P ≠ N P over (ℚ^{a}, =, w).

Proof. Define:

\begin{aligned}σ_{1} : & ℚ^{ra} & → & ℚ^{a} \\ & x & ↦ & σ_{1}(x) = x \end{aligned}

This is clearly a morphism. (Property (I3) follows from Corollary 5). Define also the morphism:

\begin{aligned}σ_{2} : & ℚ^{a} & → & (ℚ^{ra})^{2} \\ & x + iy & ↦ & σ_{2}(x + iy) = (x, y) \end{aligned}

Then σ_{2} ∘ σ_{1} is the identity map in R_{1}, so (T1) holds. Note that σ_{1} ∘ σ_{2} maps x + iy into x, y, so it is not clear if (T2) hold.

Hence, we are under the conditions of Theorem 11 and P ≠ N P over (ℚ^{ra}, =, w) implies P ≠ N P over (ℚ^{a}, =, w)

Now we can show that Theorem 12. P ≠ N P over (ℚ^{ra}, =, w).

This implies Theorem B

Proof. Let ℚ_{+}^{ra} be the set of {x ∈ ℚ^{ra} : x ≥ 0}. Clearly, ℚ_{+}^{ra} is in N P, since the non-deterministic machine M(x, y) that checks x − y^{2} = 0 decides x ∈ ℚ_{+}^{ra} in polynomial time. (Recall that H(\sqrt{x}) = \sqrt{H(x)} and [ℚ[\sqrt{x}] : ℚ] ≤ 2[ℚ[x] : ℚ]).

Now, suppose that there is a deterministic machine M that decides x ∈ ℚ_{+}^{ra} in polynomial time. Let K be the number field generated over ℚ by all the coefficients of M.

There is some α > 0 algebraic over K with the following property: there is an automorphism σ of K[α] over K such that α^{σ} < 0. Choose z ∈ K such that \sqrt{z} ∉ K, and set α = \sqrt{z}.

The machine M cannot distinguish between α and α^{σ}. Indeed, let γ^{t} be the path associated to input α and let G^{t}(α) = g_{γ^{t}}(s^{t}) be the polynomial in α associated to each branching node in γ^{t}. The coefficients of G^{t} are in K, so σ fixes G^{t} and

G^{t}(x) = 0 ⇔ G^{t}(x^{σ}) = 0

This means that replacing α by α^{σ} does not modify the path γ^{t}, hence the output of M is the same.

The same argument is true for the unit cost model (ℚ^{ra}, =, 1). However, in the unit cost case, a more general theorem holds, as discussed in [BCSS98] Chapter 7. Namely P ≠ N P over all (K, >, 1) where K is an infinite field not real closed, and over all (K, =, 1) where K is an infinite field not algebraically closed.

5. Complexity of diophantine approximation

The main goal of this section is to prove Theorem C. A few remarks concerning that Theorem: It is possible to represent an algebraic number x by its minimal polynomial and an interval

containing x. This interval should be taken smaller than the distance to the nearest root. See [Mig83] and [Loo83] for a bound. See also Corollary 1 of Ch. 8 in [BCSS98], and [Mal93] for other ‘gap’ bounds. However, in order to refine that interval up to 2^{−k} by a method such as bisection, it takes k steps with k-bits arithmetic. This is why Theorem C was stated.

In order to obtain this sharper estimate, we use Newton Iteration instead. Newton iteration is known to converge quadratically once close enough to the root. [KA82, Sma86, SS93]. See also Chapter 8 in [BCSS98].

If we use some sort of approximate computation, we have to allow for some sort of ‘approximate’ Newton iteration. Theorems on quadratic convergence of ‘approximate’ Newton iteration appear in [Mal94].

Also, it is necessary to bound the precision necessary to specify the ‘starting point’ of the Newton iteration. Those are the main ingredients of the proof of Theorem C.

5.1. Approximate Newton Iteration. Let f be a univariate polynomial. The following invariants [Sma86] are associated to f:

β(x) = β(f, x) = \frac{|f(x)|}{|f′(x)|}

γ(x) = γ(f, x) = max_{k≥2} (\frac{|f^{(k)}(x)|}{k! |f′(x)|})^{\frac{1}{k−1}}
α(x) = α(f, x) = β(f, x) γ(f, x)

The following theorem is a particular case of some earlier results in [Mal94]. It generalizes the convergence theorems in [Sma86] to the case of approximate Newton iteration. It is stronger than Theorem 4 in Chapter 8 of [BCSS98], which only provides linear convergence for approximate Newton iteration.

Theorem 13. Let f be a univariate polynomial, and let s ∈ ℕ, s ≥ 2. Let x_{0} be such that α(f, x_{0}) < 2^{−5}. Let δ be such that δγ(f, x_{0}) < 2^{−4−2^{s+2}}. Let the sequence x_{i} satisfy

|x_{i+1} − (x_{i} − \frac{f(x_{i})}{f′(x_{i})})| < δ

Then there is a zero x^{∗} of f such that

|x_{i} − x^{∗}| < \frac{2^{1−2^{min(i,s)}}}{γ(f, x_{0})}

Some of the Lemmas below are standard and may have appeared in [Sma86, SS93, BCSS98]. For later use, we define the function ψ(t) = 1 − 4t + 2t^{2}. The Lemma below is slightly sharper and implies Proposition 3 in Chapter 8 of [BCSS98].

Lemma 7. Let f be a univariate polynomial, and let x, h ∈ ℂ. Let f′(x) ≠ 0 and assume that |h|γ(f, x) < 1 − \sqrt{2}/2. Then:

β(f, x + h) ≤ |\frac{f(x)}{f′(x)} + h| \frac{( 1 − γ(f, x)|h|)^{2}}{ψ( γ(f, x)|h|)} + |h|^{2}γ(f, x)\frac{1 − γ(f, x)|h|}{ψ( γ(f, x)|h|)}

In particular,

1. If h = −\frac{f(x)}{f′(x)} + δ, we get:

β(x + h) ≤ |δ| \frac{( 1 − γ(x)|h|)^{2}}{ψ( γ(x)|h|)} + ( |β(x)| + |δ|)^{2} γ(x)\frac{1 − γ(x)|h|}{ψ( γ(x)|h|)}

2. If β(f, x) = 0, we get:

β(x + h) ≤ |h| \frac{( 1 − γ(x)|h|)^{2}}{ψ( γ(x)|h|)} + |h|^{2}γ(x)\frac{1 − γ(x)|h|}{ψ( γ(x)|h|)}

Proof of Lemma 7. We can break

β(x + h) = \frac{|f(x + h)|}{|f′(x + h)|} = \frac{|f′(x)|}{|f′(x + h)|} \frac{|f(x + h)|}{|f′(x)|}

Using Taylor development, it is easy to estimate, since f′(x) ≠ 0:

\frac{|f(x + h)|}{|f′(x)|} ≤ |\frac{f(x)}{f′(x)} + h| + ∑_{k≥2} |\frac{f^{(k)}(x)}{k!f′(x)}h^{k}|

≤ |\frac{f(x)}{f′(x)} + h| + |h| ∑_{k≥2}( γ(f, x)|h|)^{k−1}

and hence

\frac{|f(x + h)|}{|f′(x)|} ≤ |\frac{f(x)}{f′(x)} + h| + \frac{|h|^{2}γ(x)}{1 − γ(x)|h|} (1)

On the other hand, using again the hypothesis f′(x) ≠ 0,

\frac{f′(x + h)}{f′(x)} = 1 + ∑_{k≥2} \frac{f^{(k)}(x)}{k − 1!f′(x)}h^{k−1}

hence

|\frac{f′(x + h)}{f′(x)} − 1| ≤ ∑_{k≥2}( kγ(x)|h|)^{k−1} ≤ \frac{1}{( 1 − γ(x)|h|)^{2}} − 1

Thus,

\frac{|f′(x)|}{|f′(x + h)|} ≤ \frac{1}{1 − |\frac{f′(x+h)}{f′(x)} − 1|} ≤ \frac{1}{2 − \frac{1}{( 1−γ(x)|h|)^{2}}} ≤ \frac{1 − γ(x)|h|}{ψ( γ(x)|h|)} (2)

Combining bounds 1 and 2 together, we obtain

β(x + h) ≤ |\frac{f(x)}{f′(x)} + |h|| \frac{( 1 − γ(x)|h|)^{2}}{ψ( γ(x)|h|)} + |h|^{2}γ(x)\frac{1 − γ(x)|h|}{ψ( γ(x)|h|)}

Lemma 8. Let f be a univariate polynomial, and let x, h ∈ ℂ. Let f′(x) ≠ 0. Assume also that γ(f, x)|h| < 1 − \sqrt{2}/2. Then:

γ(f, x + h) ≤ \frac{γ(f, x)}{( 1 − γ(f, x)|h|)ψ( γ(f, x)|h|)}

Since this is Proposition 3 in Chapter 8 of [BCSS98], the proof is omitted.

From Lemma 8 we can deduce that:

Lemma 9. Let f be a univariate polynomial. Let C be a constant, C < \frac{1}{10}. Let x^{∗} ∈ ℂ be a zero of f. Let U be a neighborhood of x^{∗}, of radius ρ < \frac{C}{γ(f,x^{∗})}. Then for any x ∈ U,

(1 − 10C)γ(f, x^{∗}) < γ(f, x) < \frac{1}{1 − 5C} γ(f, x^{∗})

Proof of Lemma 9. From Lemma 8 centered at x^{∗}, we have

γ(x) ≤ \frac{γ(x^{∗})}{(1 − γ(x^{∗})ρ)ψ(γ(x^{∗})ρ)}
≤ \frac{γ(x^{∗})}{(1 − C)ψ(C)}
≤ \frac{γ(x^{∗})}{1 − 5C}

On the other hand, Lemma 8 also tells us that

γ(x^{∗}) ≤ \frac{γ(x)}{(1 − γ(x)ρ)ψ(γ(x)ρ)}
≤ \frac{γ(x)}{(1 − \frac{C}{1−5C})ψ (\frac{C}{1−5C} )}

≤ \frac{1 − 5C}{1 − 10C} γ(x)

Lemma 10. Let f be a univariate polynomial. Let x be such that α(f, x) < 2^{−4}. Then there is x^{∗} such that f(x^{∗}) = 0 and |x − x^{∗}| < 1.1β(f, x)

Proof. First of all, let x_{0} = x and x_{i+1} = x_{i} − f(x_{i})/f′(x_{i}). Then α(x_{i}) < 2^{−2^{i+1}−2}. Indeed, by putting Lemma 7 and Lemma 8 together, one gets:

α(x_{i+1}) ≤ α(x_{i})^{2} \frac{1}{ψ(α(x_{i}))^{2}} < \frac{16}{9}α(x)^{2} < 2α(x)^{2}

so

α(x_{i+1}) < 2 × 2^{−4−2^{i+2}} = ×2^{−3−2^{i+2}}

Besides, lim α(x_{i}) = 0 so x_{i} converges. Let x^{∗} = lim x_{i}.

|x − x^{∗}| ≤ ∑ β(x_{i})

From Lemma 7,

β(x_{i+1}) < β(x_{i})α(x_{i})\frac{1 − α(x_{i})}{ψ(α(x_{i})} < 0.078 ⋯ β(x_{i}) < 0.08β(x_{i})

Therefore,

|x − x^{∗}| < \frac{1}{1 − 0.08}β(x_{0}) < 1.087 ⋯ β(x_{0}) < 1.1β(x_{0})

Lemma 11. Let f be a univariate polynomial. Let x^{∗} ∈ ℂ be a zero of f. Let U be a neighborhood of x^{∗}, of radius ρ < \frac{1}{100γ(f,x^{∗})}. Then for any x_{0} ∈ U, set x_{1} = x_{0} − f(x_{0})/f′(x_{0})

|x_{1} − x^{∗}| < 0.1ρ

Proof. First of all, we can use Lemma 9 to bound γ in U. We obtain, using C = \frac{1}{100}, that for all x ∈ U,

0.9γ(x^{∗}) < γ(x) < \frac{20}{19}γ(x^{∗})

Also, from Lemma 7 item 2, we obtain:

β(x) ≤ ρ\frac{(1 − γ(x^{∗})ρ)^{2}}{ψ(γ(x^{∗})ρ)} + ρ^{2}γ(x^{∗})\frac{1 − γ(x^{∗})ρ}{ψ(γ(x^{∗})ρ)} ≤ 1.031 ⋯ ρ < 1.05ρ

Hence,

α(x) ≤ β(x)γ(x) < (1.05ρ)\frac{20}{19}γ(x^{∗}) ≤ 0.01105 < 0.012

We can also bound

α(x_{1}) < 2α(x)^{2}

Thus,

β(x_{1}) ≤ \frac{2α(x)^{2}}{γ(x)}
≤ 2α(x)β(x)
≤ 2 × 0.012 × 1.05ρ
≤ 0.0252ρ

Hence, using lemma 10,

|x_{1} − x^{∗}| < 0.028ρ

Proof of Theorem 13. Lemma 10, together with the hypothesis α(x_{0}) < \frac{1}{32}, implies the existence of a point x^{∗} s.t. f(x^{∗}) = 0, with

|x_{0} − x^{∗}| < 1.1β(x) < \frac{1.1}{32γ(x)}

We apply Lemma 8 to estimate γ(x^{∗}):

γ(x^{∗}) ≤ \frac{γ(x_{0})}{( 1 − γ(x_{0})|x^{∗} − x_{0}|)ψ( γ(x_{0})|x^{∗} − x_{0}|)}
≤ \frac{γ(x_{0})}{1 − 5\frac{1.1}{32}}
≤ 1.21γ(x_{0})

Let U be a disc centered in x^{∗} and with radius \frac{1}{20γ(x^{∗})}. Clearly, x_{0} ∈ U. (Proof: \frac{1.1}{32γ(x_{0})} < \frac{1.1×1.21}{32γ(x^{∗})} < \frac{1}{20γ(x^{∗})}. Lemma 9 provides the following uniform bound for any x ∈ U:

\frac{1}{2}γ(x^{∗}) < γ(x) < \frac{4}{3}γ(x^{∗}) < 2γ(x_{0})

Our induction hypothesis is: α(x_{i}) < 2^{−3−2^{i+1}} for all i ≤ s. We also assume by induction that x_{i} ∈ U so that γ(x_{i})δ < 2^{−4−2^{s+2}}. Combining Lemma 7 and Lemma 8 we get:

α(x_{i+1}) < \frac{1}{ψ(α(x_{i}) + γ(x_{i})δ)^{2}} (γ(x_{i})δ + (α(x_{i}) + γ(x_{i})δ)^{2})

Using the induction hypothesis, we can further simplify:

α(x_{i+1}) < 2α(x_{i})^{2} + 2γ(x_{i})δ

Replacing α(x_{i}) by 2^{−3−2^{i+1}} and γ(x_{i})δ by 2^{−4−2^{s+2}} one obtains

α(x_{i+1}) < 2^{−5−2^{i+2}} + 2^{−4−2^{s+2}} < 2^{−3−2^{i+2}}

since i ≤ s. Then we need to verify that x_{i+1} ∈ U. We use Lemma 10 item 1:

β(x_{i+1}) ≤ |δ|\frac{( 1 − γ(x_{i})|h|)^{2}}{ψ( γ(x_{i})|h|)} + |h|^{2}γ(x_{i})\frac{1 − γ(x_{i})|h|}{ψ( γ(x_{i})|h|)}

In the right-hand term, we can bound γ(x_{i})|h| by α(x_{i}) + γ(x_{i})δ. By the induction hypothesis, this is less than 2^{−5} + 2^{−8}. Hence,

β(x_{i+1}) ≤ \frac{1}{γ(x_{i})} (2^{−8} \frac{(1 − (2^{−5} + 2^{−8}))^{2}}{1 − 4(2^{−5} + 2^{−8})} + (2^{−5} + 2^{−8})^{2} \frac{1 − (2^{−5} + 2^{−8})}{1 − 4(2^{−5} + 2^{−8})})

Besides, γ(x_{i}) > \frac{1}{2}γ(x^{∗}), so

β(x_{i+1}) < \frac{2}{2^{7}γ(x^{∗})} < \frac{1}{20γ(x^{∗})}

This was for i < s. When i = s, it is easy to bound using Lemmas 9 and 10 that

|x_{i} − x^{∗}| < \frac{2^{−2^{s+1}−1}}{γ(x^{∗})}

and then, since s ≥ 2, we are in the conditions of Lemma 11, for

ρ = \frac{2^{−2−2^{s+1}}}{γ(x^{∗})}

This is mapped into a ρ/10 neighborhood of x^{∗}. Since the error δ is less than ρ/2, the sequence of x_{i} will never leave the ρ-neighborhood.

We state the following Lemma, that we will need later on:

Lemma 12. Let f be a polynomial and let x^{∗} be a single root of f. Let |x − x^{∗}| < 2^{−6}/γ(x^{∗}). Then α(f, x) < 2^{−5}.

Proof of Lemma 12. By Lemma 7 item 2,

β(x) < |x − x^{∗}|\frac{( 1 − γ(x^{∗})|x − x^{∗}|)^{2}}{ψ( γ(x^{∗})|x − x^{∗}|)} + γ(x)|x − x^{∗}|^{2} \frac{1}{ψ( γ(x^{∗})|x − x^{∗}|)}

Lemma 9 implies that γ(x) < \frac{1}{1−4×2^{−6}} γ(x^{∗}). Putting all together,

α(x_{i}) < \frac{2^{−6} + 2^{−12}}{(1 − 4 × 2^{−6})^{2}} < 2^{−5}

5.2. Approximation of Algebraic Numbers.

Theorem 14. Let K be a number field. Let f be a degree d polynomial with coefficients in K. Let x be a single root of f. Let x_{0} ∈ ℂ be such that f′(x) ≠ 0 Then the following bounds are true:

1. w(γ(f, x_{0})) ≤ [K[x_{0}] : ℚ] (d^{2}⌈log_{2} d⌉ + d^{3}⌈log_{2} H(x_{0})⌉ + d^{2}⌈log_{2} H(f)⌉)

2. w(γ(f, x)) ≤ 3d^{4}w(f)

3. γ(f, x) ≤ 2^{3d^{4}w(f)}

4. If f is the minimal polynomial of x over ℚ, then γ(f, x) ≤ 2^{3d^{4}w(f)} ≤ 2^{3w(x)^{5}}

Proof of Theorem 14. In order to bound the weight of

γ(x_{0}) = max_{k≥2} (\frac{|f^{(k)}(x_{0})|}{k!|f′(x_{0})|})^{\frac{1}{k−1}}

we use Theorem 4 with F_{0}(f, y) = f^{(k)}(y) and F_{1}(y) = k!f′(y), y = (x_{0} : 1). We get

H(F_{0}(y) : F_{1}(y)) ≤ (d − 1)\frac{d!}{d − k!}H(f)H(y)^{d−1}

A gross estimate of k! and of d − k! is d!. So we deduce that

H(γ(x_{0})) ≤ max_{k≥2} (d!(d − 1)H(f)H(x_{0} : 1)^{d−1})^{\frac{1}{k−1}}
≤ d!(d − 1)H(f)H(x_{0} : 1)^{d−1}

We can also bound

[ℚ[γ(x_{0})] : ℚ] ≤ (d − 1)[K[x_{0}] : K][K : ℚ]

Hence,

w(γ(x_{0})) ≤ (d − 1)[K[x_{0}] : K][K : ℚ] (1 + ⌈log_{2} d!(d − 1)H(f)H(x)^{d−1}⌉)

and the first part of the Theorem follows. The second part is a consequence of Theorem 5. Then we use Lemma 1 to deduce part 3, and Lemma 6 for part 4.

5.3. Proof of Theorem C.

Proof of Theorem C. Let x be an algebraic number, and let d = [ℚ[x] : ℚ]. Let f be the minimal polynomial of x over ℚ. By Corollary 4,

H(f) ≤ 2^{w(x)}

and therefore f can be represented by d + 1 numbers of 1 + w(x) bits.

Theorem 14 item 4 implies:

γ(x) ≤ 2^{3d^{4}w(f)}

Let x_{0} be an approximation of f, such that |x − x_{0}| < \frac{2^{−6}}{γ(x)}. It is enough to choose x_{0} within a radius of

|x − x_{0}| < 2^{−6−3d^{4}w(f)}

from x. One possibility is to truncate the real and imaginary part into fixed points of 8 + 3d^{4}w(f) + w(x) bits of precision (using fixed point representation).

We are under the conditions of Lemma 12, so α(x_{0}) < 2^{−5}.

We can now produce the function y(x). It is a list (d, w, f, x_{0}) where w = ⌈w(x)⌉, and d, f and x_{0} are as above. Theorem 6 yields w(x) < Bitsize(y(x)).

It is time to construct the machine M that will provide the 2^{−k}- approximations of x. First of all, we can bound γ(f, x_{0}) by applying Lemma 8. The following conclusion is not sharp, but is convenient:

\frac{1}{2}γ(x) ≤ γ(x_{0}) ≤ 2γ(x)

The next step is to choose s such that

\frac{2^{1−2^{s}}}{γ(x_{0})} < 2^{−k}

Using w(γ(x_{0})) ≤ Cd^{7}w, we restrict our choice to:

2^{1−2^{s}} < 2^{−k−Cd^{7}w}

A good choice is s = ⌈log_{2} (k + 1 + Cd^{7}w)⌉. In that case, s ≤ log_{2} k + 7 log_{2} d + log_{2} w + C′, for some constant C′. The machine M will perform s approximate Newton iterations, obtaining at each step x_{i} with accuracy

δ = 2^{−4−Cd^{7}w−2^{s+2}} < \frac{2^{−4−2^{s+2}}}{γ(x_{0})}

This corresponds to 4 + Cd^{7}w + 2^{s+2} bits of precision in each x_{i}. This can be achieved by using precision of kwPoly(d) bits of fixed point, and truncating.

Therefore, the total running time can be bounded in terms of k log_{2} k w log_{2} w Poly(d) bit operations, or more precisely:

O(k log_{2} k w log_{2} w d^{8} log_{2} d)

where the exponent in d is not intended to be sharp.

6. Bit representation of Algebraic Numbers

Algebraic numbers are essentially discrete objects. They can be represented by a minimal polynomial. We have seen in Theorem 6 and C that the bit-length of such a representation is related to the weight of the algebraic number.

We will start this section by proving Theorem D. The main tool in the proof is the basis reduction algorithm by Lenstra, Lenstra and Lovasz [LLL82] (LLL for short). This algorithm provides an effective procedure to check for algebraic dependence.

The main results about that algorithm are only quoted below. Since this algorithm is defined over the integers (with the bit model), a few extra estimates will be necessary.

Next, we would like to extend the ideas of Theorem C to the case where we have several algebraic numbers α_{1}, …, α_{n}. It makes sense to represent them as polynomials q_{i}(α), where α is a primitive element of ℚ[α_{1}, ⋯, α_{n}].

Definition 20. An integer representation of α_{1}, …, α_{n} ∈ (ℚ^{a})^{n} is a list (y(α), q_{1}, ⋯, q_{n}) ∈ ℤ^{∞} where

1. α is a primitive element of ℚ[α_{1}, ⋯, α_{n}]

2. y : ℚ^{a} → ℤ^{∞} is the function defined in Theorem C, where ℚ^{a} is the ring of algebraic numbers.

3. q_{1}, ⋯, q_{n} are densely represented polynomials with rational coefficients such that α_{i} = q_{i}(α)

We will then prove a theorem on the complexity of basic arithmetic operations over integer representations of algebraic numbers. Namely,

Theorem 15. The following operations can be executed in polynomial time over (ℤ, >, w):

1. Merging: given an integer representation of a_{1}, ⋯, a_{n} and an integer representation of b_{1}, ⋯, b_{m}, compute one integer representation of a_{1}, ⋯, a_{n}, b_{1}, ⋯, b_{m}.

2. Arithmetic: given integer representation for x, y, compute integer representation for x, y, x + y, xy, x − y.

3. Decision: given an integer representation for x, decide x = 0, or x ∈ ℝ, or if this is the case, whether x > 0.

4. Restriction: Given an integer representation for a_{1}, ⋯, a_{n}, produce an integer representation of a_{n}, of size polynomially bounded in w(a_{n}).

Theorem 15 will be proved using a modification of well-known symbolic algebra algorithms (namely Collins’ SIMPLE algorithm for primitive elements).

One consequence of Theorem 15 and Theorem D together will be that computation models over the integers (ℤ, >, w) and over the real algebraic numbers (ℚ^{ra}, >, w) are polynomially equivalent, finishing the proof of Theorem A.

6.1. Lattice basis reduction.

Definition 21. A Lattice is a subset Λ of ℝ^{n} of the form:

Λ = {Az : z ∈ ℤ^{n}}

where A is a (real or) integer n × n matrix.

We can restrict ourselves to the case where A is invertible. In that case, the columns of A are said to be a basis of the Lattice Λ. Of course a lattice admits an infinity of bases, and it is possible to pass from a basis to another basis through elementary column operations (adding a multiple of another column, or column permutation).

Given A, the LLL algorithm will perform those operations and output a ‘reduced’ basis. Reduced bases keep some of the good properties of orthonormal bases, while maintaining integer arithmetic. The price to pay is to replace orthogonality and norm-1 with certain bounds.

Following the notation of [LLL82], let (b) = (b_{1}, ⋯, b_{n}) be a basis for a lattice Λ. The following vectors and numbers are associated to (b):

b_{i}^{∗} = b_{i} − ∑_{j=1}^{i−1} μ_{ij}b_{j}

μ_{ij} = \frac{< b_{i}, b_{j}^{∗} >}{∥b_{j}^{∗}∥^{2}}

Vectors b_{i}^{∗} correspond to the Gram-Schmidt orthogonalization of (b) in ℝ^{n}.

Definition 22 (LLL). A basis (b) for a lattice Λ is said to be reduced if and only if

\begin{aligned}|μ_{ij}| & ≤ & \frac{1}{2} & , 1 ≤ j < i ≤ n \\ |b_{i}^{∗} + μ_{i,i−1}b_{i−1}^{∗}| & ≥ & \frac{3}{4}|b_{i−1}^{∗}|^{2} & , 1 < i ≤ n \end{aligned}

The following result is Proposition 1.11 in [LLL82]:

Proposition 4. Let L ⊂ ℝ^{n} be a lattice with reduced basis b_{1}, b_{2}, ⋯, b_{n}. Then |b_{1}|^{2} ≤ 2^{n−1}|x|^{2} for any x ∈ L, x ≠ 0.

Also, Proposition 1.9 ibid says that:

Proposition 5. Let L ⊂ ℝ^{n} be a lattice with reduced basis b_{1}, b_{2}, ⋯, b_{n}. Then ∥b_{1}∥ ≤ 2^{\frac{n−1}{4}} (det L)^{\frac{1}{n}}

where the determinant of a lattice L is the determinant of any positively oriented basis of L.

Complexity of the basis-reduction algorithm goes as follows (Proposition 1.26 in [LLL82]):

Proposition 6. Let L ∈ ℤ^{n} be a lattice with basis b_{1}, ⋯, b_{n} and let B ∈ ℝ, B ≥ 2 be such that |b_{i}|^{2} ≤ B for 1 ≤ i ≤ n. Then the number of arithmetic operations needed by the basis reduction algorithm described in [LLL82] equation (1.15) is O(n^{4} log B), and the integers on which those operations are performed each have binary length O(n log B).

This was used in [LLL82] to deduce that

Theorem 16. The cost of factorizing f ∈ ℤ[x] into irreducible factors, in the bit model, is

O((deg f)^{12} + (deg f)^{9}(log ∥f∥_{2})^{3})

Before giving the proof of Theorem D, we will proceed like it is suggested in [LLL82] 1.39 to obtain the following, preliminary result:

Lemma 13. There is a polynomial time machine in (ℚ^{ra}, ≥, w) accepting input w_{0}, n ∈ ℕ and α_{0} = 1, α_{1}, ⋯ α_{n} ∈ ℚ^{ra} with output p ∈ ℤ^{∞} with the following properties:

1. If w(α_{1}, ⋯, α_{n}) ≤ w_{0}, and there is a relation ∑ p̂_{i}α_{i} = 0, not all the p̂_{i} equal to zero, then the machine returns some p ≠ 0 such that ∑ p_{i}α_{i} = 0.

2. If the machine returns p ≠ 0, then ∑ p_{i}α_{i} = 0.

3. The machine always terminates.

Proof of Lemma 13.

Step 1. Let b be a constant in ℕ^{∗}, to be precised later. Each of the α_{i} can be approximated by \frac{a_{i}}{b}, a_{i} ∈ ℤ, with error |α_{i} − \frac{a_{i}}{b} | ≤ \frac{1}{2b}. The a_{i}’s can be found by computing bα_{i} and rounding to the nearest integer.

Step 2. let m ∈ ℤ^{n+1}, m_{i} < B where B is another constant to be computed later. We assume here that w(α) < w_{0}. Then we have two possibilities, namely

∑_{i=0}^{n} m_{i}α_{i} = 0

or

| ∑_{i=0}^{n} m_{i}α_{i}| > δ = (B(n + 1))^{−w_{0}}

Indeed,

H(∑ m_{i}α_{i}) ≤ (n + 1) ∏ H(m_{i}α_{i}) = n ∏ m_{i} ∏ H(α_{i})

Let d = deg[ℚ[α_{1}, ⋯, α_{n}]] and assume that ∑ m_{i}α_{i} ≠ 0. Then

| ∑ m_{i}α_{i}| > H(∑ m_{i}α_{i})^{−d}
> (n + 1)^{−d}B^{−nd} (∏ H(α_{i}))^{−d}
> (n + 1)^{−d}B^{−nd}2^{−nw_{0}}

Also, setting b > \frac{(n+1)B}{δ}, so that \frac{(n+1)B}{2b} < \frac{δ}{2}, one obtains:

|∑_{i=0}^{n} m_{i}α_{i} − ∑_{i=0}^{n} m_{i} \frac{a_{i}}{b} | < \frac{δ}{2}

Hence, under the assumptions w(α) < w_{0}, |m_{i}| < B one obtains:

| ∑ m_{i} \frac{a_{i}}{b} | < \frac{δ}{2} ⇒ ∑ m_{i}α_{i} = 0
| ∑ m_{i} \frac{a_{i}}{b} | ≥ \frac{δ}{2} ⇒ ∑ m_{i}α_{i} ≠ 0

Step 3 We consider now the lattice Λ given by the basis:

U = [ \begin{matrix}1 \\ & 1 \\ . & . & . \\ \frac{a_{0}C}{b} & \frac{a_{1}C}{b} & ⋯ & \frac{a_{n}C}{b} \end{matrix} ]

where C is a multiple of b to be given later. Suppose that u_{1} = U [ m_{0} ; m_{1} ; ⋮ ; m_{n} ] is the first vector of a

reduced basis of Λ. According to Proposition 5,

∥u_{1}∥ ≤ 2^{\frac{n}{4}} (det U)^{\frac{1}{n+1}}
= 2^{\frac{n}{4}} (\frac{Ca_{n}}{b})^{\frac{1}{n+1}}

Step 4. Now, since u_{1} = [ m_{0} ; ⋮ ; m_{n−1} ; ∑_{i=0}^{n} \frac{Ca_{i}}{b} m_{i} ] we can estimate:

|∑_{i=0}^{n} \frac{Ca_{i}}{b} m_{i}| < 2^{\frac{n}{4}} (\frac{Ca_{n}}{b} )^{\frac{1}{n+1}}

hence

|∑_{i=0}^{n} \frac{a_{i}}{b} m_{i}| < 2^{\frac{n}{4}} C^{− \frac{n}{n+1}} (\frac{a_{n}}{b} )^{\frac{1}{n+1}}

so if we fix C > (\frac{2}{δ}2^{− \frac{n}{4}} |α_{n} + \frac{1}{2b}|^{− \frac{1}{n+1}} )^{1+ \frac{1}{n}} we obtain

|∑_{i=0}^{n} \frac{a_{i}}{b} m_{i}| < \frac{δ}{2}

Step 5. In order to guarantee the condition in Step 2, we need to give B where |m_{i}| < B for the reduced basis we will obtain. Let us assume that w(α) ≤ w_{0}. Also, we assume that ∑ p̂_{i}α_{i} = 0, with p̂_{i} minimal, p̂_{i} ≠ 0. Then according to Theorem 6, |p̂_{i}| < 2^{w_{0}}. Proposition 4 lets us choose

B = 2^{n+w_{0}}

Then we choose δ and b as above and C as in step 4. All the operations done so far involve integer values with polynomially bounded size. The a_{i}’s can be obtained by binary search (also in polynomial time). The LLL algorithm is also polynomial time. At the end of the program, we check if ∑ p_{i}α_{i} = 0.

Remark 5. Felipe Cucker pointed out that in the argument above, only the binary search and the final test ∑ p_{i}α_{i} = 0 involve computations over ℚ^{ra}. All other computations can be performed in a Turing machine.

Proof of Theorem D. Let x ∈ ℚ^{ra}. If we knew d = [ℚ[x] : ℚ] and a reasonable bound for w_{0}, we could just apply Lemma 13 to input 1, x, x^{2}, ⋯, x^{d} to obtain the minimal polynomial of x. Since we don’t, we proceed as follows:

Start with bounds d = 1, w_{0} = 2, and apply Lemma 13. In case of failure (p = 0), multiply d and w_{0} by 2 and start again.

The machine in Lemma 13 will eventually succeed, with some d < 2[ℚ[x] : ℚ] and some w_{0} < 2dw(x). Those bounds are polynomial in w(x).

Next, we use Theorem 16 to factorize p over ℚ, so we obtain the minimal polynomial of x.

At that time, we also have an upper bound w_{0} for w(x). Therefore, Theorem 14 implies that:

γ(x) < 2^{3w_{0}^{5}}

Recall from Lemma 12 that if |x − x′| < 2^{−6}/γ(x), then α(x′) < 2^{−5} and x′ is a suitable approximation of x. So all that we need is to compute an approximation of x with precision 2^{−6−3w_{0}^{5}}. This can be done by bisection, in polynomial time, in such a way that the denominator is indeed 2^{−6−3w_{0}^{5}}.

6.2. Symbolic algebra.

Proof of Theorem 15. The most difficult part of the proof of Theorem 15 is the first.

We will follow Collins’ SIMPLE algorithm, as explained in [Loo83]. However, instead of using isolating intervals, we will use approximate roots. Also, due to the estimates on weights, some of the steps will have to be modified.

Item 1 reduces to the following problem.

Problem 1 (Extension). Let A and B be minimal polynomials of a and b, respectively. Let a′ and b′ be approximate roots associated to a and b. Produce a minimal polynomial C for a primitive element c of ℚ[a, b], together with an approximate root c′ of C associated to c. Also, produce rational polynomials q_{1} and q_{2} such that a = q_{1}(c) and b = q_{2}(c).

We need a polynomial time algorithm for solving the Extension Problem. Let us fix some notation. If f and g are polynomials in y, f = ∑_{i=1}^{m} f_{i}y^{i} and g = ∑_{i=1}^{n} g_{i}y^{i}, f_{m} ≠ 0, g_{n} ≠ 0, the Sylvester matrix Syl_{y}(f, g) is the matrix associated to the operator:

a, b ↦ af + bg

where a and b are polynomials of degree n − 1 and m − 1, respectively:

Syl_{y}(f, g) = [ \begin{matrix}f_{0} & & & & g_{0} \\ f_{1} & f_{0} & & & g_{1} & g_{0} \\ f_{2} & f_{1} & ... & & ⋮ & g_{1} & ... \\ ⋮ & f_{2} & ... & f_{0} & & ⋮ & ... & g_{0} \\ f_{m} & & ... & f_{1} & g_{n} & & & g_{1} \\ & f_{m} & & f_{2} & & g_{n} & & ⋮ \\ & & ... & ⋮ & & & ... \\ & & & f_{m} & & & & g_{n} \end{matrix} ]

The resultant Res_{y}(f, g) is just

Res_{y}(f, g) = det Syl_{y}(f, g)

It is obvious that if f and g have a common root then Res_{y}(f, g) vanishes. The converse is easy (assume that af + bg ≡ 0 and suppose that f and g have no common root. Then a has to vanish at the roots of g, with multiplicity, etc...)

This is still valid if the coefficients of f and g belong to the transcendental extension ℚ[x].

We can now produce a primitive element c for ℚ[a, b] as follows. Let

r(x, t) = Res_{y}(A(x − ty), B(y))

where x is a formal variable. We need to compute r(x, t) as a polynomial in x for a fixed value of t. We will choose t such that r(x, t) has no multiple root (as a polynomial in x).

Note that the roots of r(x, t) are the expressions c_{ij} = a_{i} + tb_{j} where a_{i} and b_{j} are the roots of A and B, respectively.

Therefore, if we set t large enough (namely t > 2^{2+w(a)+w(b)}) we get:

|a_{i} − a_{j}| < 2^{w(a_{i}−a_{j})} ≤ 2^{1+w(a)}

because of Lemma 1.

|b_{k} − b_{l}| > 2^{−1−w(b)}

by the same reason. Thus

|a_{i} − a_{j}| < t|b_{k} − b_{l}|

and hence

a_{i} − tb_{k} ≠ a_{j} − tb_{l}

It follows that r(x, t) has no multiple root.

We can use Theorem 16 to find out an irreducible factor of r(x, t) vanishing in a_{i} + tb_{k}. Let C(x) be that factor.

Our primitive element is c = a_{i} + tb_{k}. The weight of c is polynomially bounded on the input size. An approximation c′ can be computed by using estimate on w(c) and Lemma 11.

The polynomial r(x, t) is a polynomial of degree no more than (deg A)(deg B) in x. i For any x in {0; 1; (deg A)(deg B)}, it is possible to compute, in polynomial time, Res_{y}(A(x −

ty), B(y)). Moreover,

Res_{y}(A(x − ty), B(y))_{|x=i} = Res_{y}(A(i − ty), By)

so that the coefficients of r(x, t) may be obtained by interpolation.

We can use Theorem 16 to deduce that an irreducible factor of r(x, t) vanishing in c can be computed in polynomial time. Let C(x) be that factor.

Let D(x) = gcd(A(c − tx), B(x)). The polynomial D(x) can be computed symbolically with arithmetic in ℚ[c]. Its only root is b_{k}, so it has degree 1, and is of the form: D(x) = x − q_{2}(c).

We can also set q_{1}(x) = x − tq_{2}(x) so that q_{1}(c) = a.

Item 2: Let x = q_{1}(a) and y = q_{2}(a). Since A is the minimal polynomial of a,

x + y = (q_{1} + q_{2})(a)
x − y = (q_{1} − q_{2})(a)
xy = (q_{1}q_{2} mod A)(a)

Item 3: If x = q(a) we have, by Corollary 1 that:

H(x) ≤ SH(q)H(a)^{deg q}

Also,

w(x) = [ℚ[x] : ℚ] ⌈1 + log_{2} H(x)⌉
≤ [ℚ[a] : ℚ] ⌈1 + (deg q) log_{2} H(a) + log_{2} H(q)⌉
≤ (deg q)w(a) + w(q)

If x ≠ 0 then |x| > 2^{−w(x)}. Thus it is enough to compute x up to accuracy 2^{−w(x)−1}. If we evaluate a with accuracy 2^{−b}, then q(a) may be evaluated with accuracy 2^{−b}|a|^{deg q−1} max |q_{i}|. All this can be done in polynomial time (Theorem C).

Item 4. Let q be such that a_{n} = q(a). Using arithmetic in ℤ[x] mod A, we can compute 1, q(x), q^{2}(x) mod A, q^{3}(x) mod A, etc..., and check for linear independence. Once we get linear dependency, we solve the system:

Qp = 0

where Q is the matrix with columns 1, q(x), …, q(x)^{i} mod A(x), and where each polynomial is represented by its coefficients.

6.3. P ≠ N P over (ℤ, >, w) ⇔ P ≠ N P over (ℚ^{ra}, >, w). We complete here the proof of Theorem A. Define:

\begin{aligned}b : & ℤ^{∞} & → & ℚ^{ra} \\ & y & ↦ & lim_{k→∞} M(k, y) \end{aligned}

where M is the machine defined in Theorem C.

Let us recall the construction of M. The list y is interpreted as the coefficients of an irreducible polynomial p and an initial approximate root. M(k, y) computes then a certain number of Newton iterations. If the limit is defined, this means that b(y) is a root of p.

I claim that b is a morphism from (ℚ^{ra}, >, w) into (ℤ, >, w). Indeed, surjectivity (M1) and honesty (M2) follow from Theorem C.

The domain of definition of b is the class of y such that Newton iteration will converge to a root of p. Combining Theorem C, Lemma 12 and Theorem 14, we can check the domain of b in polynomial time. This implies property (M3).

Theorem 15 implies that b is ‘very honest’ and satisfies the hypotheses of Lemma 5. Therefore, b has the pull-back property (M4).

We define also the inclusion morphism from (ℤ, >, w) into (ℚ^{ra}, >, w) :

\begin{aligned}i : & ℚ^{ra} ⊇ ℤ & → & ℤ \\ & x & ↦ & x \end{aligned}

It remains to produce machines A_{1} and A_{2}. The machine A_{1} is fairly trivial: it associates, to every x ∈ ℤ, its corresponding y(x).

The machine A_{2} is the polynomial time machine from Theorem D. It associates to every x ∈ ℚ^{ra}, its y(x)

Thus, models (ℤ, >, w) and (ℚ^{ra}, >, w) are polynomially equivalent and we can apply Theorem 10 to deduce that

P ≠ N P over (ℤ, >, w) ⇔ P ≠ N P over (ℚ^{ra}, >, w)

Almost the same argument shows that P ≠ N P over (ℤ, >, w) if and only if P ≠ N P over (K, >, w) where K is a number field, considered as a ring. Together with Propositions 2 and 3, this concludes the proof of Theorem A

Define

\begin{aligned}σ_{1} : & ℤ & → & ℚ^{ra} \\ & n & ↦ & n \end{aligned}

and

\begin{aligned}σ_{2} : & ℚ^{ra} & → & ℤ \\ & x & ↦ & y(x) \end{aligned}

where y(x) is the function in Theorem C.

It follows from Theorem 15 that σ_{2} is a morphism. Moreover, from Theorem D we can deduce that σ_{1} ∘ σ_{2} is in polynomial time over (ℤ, >, w). Hence, we can apply Theorem 10.

References

[AB94] Ilan Adler and Peter A. Beling. Polynomial algorithms for linear programming over the algebraic numbers. Algorithmica, 12:436–457, 1994.

[AM69] M. F. Atiyah and I. G. Macdonald. Introduction to Commutative Algebra. Addison Wesley, Reading MA, 1969.

[BCSS96] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Algebraic settings for the problem P ≠ N P. In Steve Smale James Renegar, Michael Shub, editor, The Mathematics of Numerical Analysis, volume 32 of Lectures in Applied Mathematics, pages 125–144. American Mathematical Society, 1996.

[BCSS98] Lenore Blum, Felipe Cucker, Mike Shub, and Steve Smale. Complexity and Real Computation. Springer, 1998.

[BS67] Z. I. Borevich and I. R. Shafarevich. Théorie des Nombres. Gauthier-Villars, Paris, 1967. Reprinted by Editions Jacques Gabay, 1993.

[BSS89] Lenore Blum, Mike Shub, and Steve Smale. On a theory of computation and complexity over the real numbers: N P-completeness, recursive functions and universal machines. Bulletin of the AMS, 21(1), 1989.

[Cas67] J. W. S. Cassels. Global fields. In Algebraic Number Theory (Proc. Instructional Conf., Brighton, 1965), pages 42–84. Thompson, Washington, D.C., 1967.

[CG97] Felipe Cucker and Dima Grigoriev. On the power of real Turing machines over binary inputs. SIAM Journal on Computing, 26(1):243–254, 1997.

[CK95] Felipe Cucker and Pascal Koiran. Computing over the reals with addition and order: higher complexity classes. Journal of Complexity, 11(3):358–376, 1995.

[Coh93] Henri Cohen. A course in computational algebraic number theory, volume 138 of Graduate Texts in Mathematics. Springer-Verlag, Berlin, 1993.

[KA82] L. V. Kantorovich and G. P. Akilov. Functional analysis. Pergamon Press, Oxford, second edition, 1982. Translated from the Russian by Howard L. Silcock.

[Knu98] Donald E. Knuth. The Art of Computer Programming, volume 2. Addison-Wesley, Reading MA, third edition edition, 1998.

[Koi94] Pascal Koiran. Computing over the reals with addition and order. Journal of Complexity, 133:486–495, 1994.

[Koi97] Pascal Koiran. A weak version of the Blum, Shub, and Smale model. Journal of Computer and System Sciences, 54(1, part 2):177–189, 1997. 1st Annual Dagstuhl Seminar on Neural Computing (1994).

[KP95] Teresa Krick and Luis M Pardo. A computational method for diophantine approximation. In Proceedings of MEGA’94, Progress in Mathematics. Birkhauser, 1995.

[Lan86] Serge Lang. Algebraic Number Theory. Springer-Verlag, New York, 1986.

[Lan97] Serge Lang. Survey of Diophantine Geometry. Springer, Berlin, 1997. Corrected Second Printing.

[LLL82] Arjen K. Lenstra, Hendrik W. Lenstra, and Laszlo Lovasz. Factoring polynomials with rational coefficients. Mathematische Annalen, 261:515–534, 1982.

[Loo83] R. Loos. Computing in algebraic extensions. In Computer algebra, pages 173–187. Springer, Vienna, 1983.

[Lov86] László Lovász. An Algorithmic Theory of Numbers, Graphs and Convexity. CBMS-NSF Reg. Conference Series in Appl. Math. 50. SIAM, Philadelphia, 1986.

[Mal93] Gregorio Malajovich. On the complexity of path-following Newton algorithms for solving systems of polynomial equations with integer coefficients. PhD thesis, Berkeley, 1993.

[Mal94] Gregorio Malajovich. On generalized Newton algorithms: quadratic convergence, path-following and error analysis. Theoret. Comput. Sci., 133(1):65–84, 1994. Selected papers of the Workshop on Continuous Algorithms and Complexity (Barcelona, 1993).

[Mic94] Christian Michaux. P ≠ N P over the nonstandard reals implies P ≠ N P over ℝ. Journal of Complexity, 133:95–104, 1994.

[Mig83] M. Mignotte. Some useful bounds. In Computer algebra, pages 259–263. Springer, Vienna, 1983.

[MM99] Gregorio Malajovich and Klaus Meer. On the structure of N P_{ℂ}. SIAM Journal on Computing, 28(1), 1999.

[MW97] Michael Maller and Jennifer Whitehead. Computational complexity over the p-adic numbers. Journal of Complexity, 13(2):195–207, 1997.

[Sil86] Joseph A. Silverman. The Arithmetic of Elliptic Curves. Graduate Texts in Mathematics 106. Springer, New York, 1986.

[Sma86] Steve Smale. Newton’s method estimates from data at one point. In The merging of disciplines: new directions in pure, applied, and computational mathematics (Laramie, Wyo., 1985), pages 185–196. Springer, New York, 1986.

[Sma98] Steve Smale. Mathematical problems for the next century. Math. Intelligencer, 20(2):7–15, 1998.

[SS93] Michael Shub and Steve Smale. Complexity of Bézout’s theorem. I. Geometric aspects. J. Amer. Math. Soc., 6(2):459–501, 1993.

Departamento de Matemática Aplicada, Universidade Federal do Rio de Janeiro. Caixa Postal 68530, CEP 21945, Rio de Janeiro, RJ, Brasil

   E-mail address: gregorio@labma.ufrj.br

Current address: On leave at MSRI, 1000 Centennial Drive, Berkeley CA 94720-5070, e-mail: gregorio@msri.org