On Asymptotic Estimates for Arithmetic Cost Functions

CARLOS GUSTAVO T. DE A. MOREIRA

I M P A Estrada Dona Castorina, 110 22460-320, Rio de Janeiro-RJ

Abstract: Let τ(n) (the cost of n) be the minimum number of arithmetic operations needed to obtain n starting from 1. We prove that τ(n) ≥ \frac{log n}{log log n} for almost all n ∈ N, and, given ε > 0, τ(n) ≤ \frac{(1+ε) log n}{log log n} for all n sufficiently large. We prove analogous results for costs of polynomials with integer coefficients.

Introduction:

The aim of this work is the study of arithmetic cost functions. The most basic case is the cost of an integer, which is the minimum number of arithmetic operations needed to obtain the integer starting from 1. That is, given k ∈ Z, τ(k) is defined as the minimum m ∈ N such that there exists a sequence (s_{0}, s_{1}, …, s_{m}) where s_{0} = 1, s_{m} = k and for each ℓ ≥ 1 there are i, j, 0 ≤ i, j < ℓ with s_{ℓ} = Op(s_{i}, s_{j}), Op ∈ {+, −, ·}. This function plays an important role in the paper by Shub and Smale ([SS]), in which some questions are proposed about the behavior of the function τ (which we shall discuss later) that have consequences in the study of an algebraic version of the famous and fundamental problem in computer science known as “NP ≠ P ” (see [SS]). In [SS] and in [MS] the following universal bounds for τ are presented:

log_{2} log_{2} m + 1 ≤ τ(m) ≤ 2 log_{2} m, ∀m ∈ N.

The first inequality cannot be improved, since τ(2^{2^{k}}) = k + 1. These inequalities are proved in the paper by de Melo and Svaiter ([MS]), where it is also proved that for any fixed ε > 0, we have τ(n) ≥ \frac{log n}{(log log n)^{1+ε}} for almost all n ∈ N .

Here we improve the above results, by proving the following:

For almost all n ∈ N we have τ(n) ≥ \frac{log n}{log log n} and, for any given ε > 0, we have τ(n) ≤ \frac{(1+ε) log n}{log log n}, for every n ∈ N sufficiently large. More precisely, given ε > 0,

\{ \begin{matrix}τ(n) ≥ \frac{log n}{log log n} + (1 − ε)\frac{log n log log log n}{(log log n)^{2}}, for almost all n ∈ N \\ τ(n) ≤ \frac{log n}{log log n} + (3 + ε)\frac{log n log log log n}{(log log n)^{2}}, for n large enough. \end{matrix}

Moreover, the first inequality does not depend on the number of binary operations that we can use (provided that this number is finite).

Subsequently, we extend our results for more general cost functions, such as cost functions of polynomials, and discuss some open problems.

Section 1: The lower estimates.

Theorem 1. Suppose that we have O binary or unary operations in the definition of τ. Then N(k) = #{n ∈ N | τ(n) ≤ k} satisfies N(k) ≤ A^{k} · k^{k} for some constant A > 0. Proof. Let Ω = {Op_{1}, Op_{2}, …, Op_{O}} the set of operations. Then τ(n) = k ⇒ ∃(s_{0}, s_{1}, …, s_{k}); s_{0} = 1, and for each ℓ ≥ 1 ∃i_{ℓ}, j_{ℓ}, 0 ≤ i, j < ℓ such that s_{ℓ} = Op(s_{i_{ℓ}}, s_{j_{ℓ}}), Op ∈ Ω, with s_{k} = n. Let (r_{1}, r_{2}, …, r_{2k}) := (i_{1}, j_{1}, i_{2}, j_{2}, …, i_{k}, j_{k}). We must have {i_{1}, j_{1}, …, i_{k}, j_{k}} = {0, 1, 2, …, k − 1}, since otherwise we would create an unnecessary s_{i}, and so τ(n) < k. Moreover, we may assume that there exists a sequence 1 ≤ ℓ_{1} < ℓ_{2} < ⋯ < ℓ_{k} ≤ 2k such that r_{ℓ_{i}} = i − 1, for i = 1, 2, …, k. Indeed, we may assume i_{ℓ} ≤ j_{ℓ}, for ℓ = 1, 2, …, k (perhaps by creating the new operations Op_{j}^{∗}(x, y) = Op_{j}(y, x)), and, if P (i) := min{j ∈ {1, 2, …, 2k} | r_{j} = i}, for i = 0, 1, …, k − 1, we shall have, perhaps rearranging the order of the operations, that P (0) < P (1) < ⋯ < P (k − 1), because if P (i) > P (i + 1), then we do not use s_{i} to create s_{i+1}, and can therefore create s_{i+1} before s_{i}. Now we can take ℓ_{i} := P (i).

Let N′(k) = #{n ∈ N | τ(n) = k}. By the above arguments, N′(k) ≤ O^{k} · N′′(k). where N′′(k) = #{(r_{1}, r_{2}, …, r_{2k}) | r_{i} ∈ {0, 1, …, k − 1}. There are 1 ≤ ℓ_{1}, < ℓ_{2} < ⋯ < ℓ_{k} ≤ 2k with r_{ℓ_{i}} = i − 1, for i = 1, 2, …, k} but then N′′(k) ≤ C_{2k}^{k}. k^{k} ≤ 4^{k} · k^{k} thus

N′(k) ≤ (4O)^{k} · k^{k}, and so N(k) ≤ ∑_{r=0}^{k} N′(r) ≤ A^{k} · k^{k}, for A = 4O + 1. □

Corollary. Given ε > 0, we have, for almost all n ∈ N, that

τ(n) ≥ \frac{log n}{log log n} + (1 − ε)\frac{log n log log log n}{(log log n)^{2}} =: f(n)

Proof. Let us compute B(n) = #{k ≤ n | τ(k) ≤ f(k)}. If k ∈ B(n) then τ(k) ≤ f(k) ≤ f(n), and we have at most N(f(n)) numbers with this property, that is, at most A^{f(n)} · f(n)^{f(n)} numbers with this property, by the theorem, but now we have, for n large enough, A^{f(n)}f(n)^{f(n)} = exp(f(n) log(Af(n))) ≤ exp (f(n) log (\frac{log n}{(log log n)^{1− \frac{ε}{2}}} )) =

exp(log n (1 + (1 − ε)\frac{log log log n}{log log n}) (1 − (1 − \frac{ε}{2})\frac{log log log n}{log log n}) ≤ n exp (−\frac{ε}{2} \frac{log n log log log n}{log log n}), therefore lim_{n→∞} \frac{B(n)}{n} = 0. □ Remark. If we have p-ary operations instead of binary operations (p ≥ 2), we have an analogous result by changing N(k) ≤ A^{k} · k^{k} into N(k) ≤ A^{k}k^{(p−1)k}, in the theorem and f(n) into \frac{f(n)}{p−1} in the Corollary.

Section 2: The upper estimates

Theorem 2. Given ε > 0, we have, for n large enough

τ(n) ≤ \frac{log n}{log log n} + (3 + ε)\frac{log n log log log n}{(log log n)^{2}} =: g(n)

Proof. Let B = [\frac{log n}{(log log n)^{3}} ], C = B^{k}, where k = [log log n] (in the calculations we shall omit the integer parts). Take s_{0} = 1, s_{1} = 2, s_{2} = 3, …, s_{B−2} = B − 1, s_{B−1} = B, s_{B} = 2B, s_{B+1} = 3B, …, s_{2B−3} = (B − 1)B, …, s_{(k−1)(B−1)}B^{k−1}, s_{(k−1)(B−1)+1} = 2B^{k−1}, …, s_{k(B−1)−1} = (B − 1)B^{k−1}, s_{k(B−1)} = B^{k} = C. Now take the representation of n in basis C

n = a_{0} + a_{1}C + ⋯ + a_{r}C^{r}, 0 ≤ a_{i} < C, r = [\frac{log n}{log C}] ∼ \frac{log n}{(log log n)^{2}} ,

and the representations of the a_{i} in basis B:

a_{i} = b_{i1} + b_{i2}B + ⋯ + b_{ik} · B^{k−1}, 0 ≤ b_{ij} < B.

Observe now that we have constructed the b_{ij} ·B^{j−1}, so we can construct an a_{i} doing k −1 sums. Since we have r + 1 coefficients a_{i} we have a total time (k − 1)(r + 1) to generate all the a_{i}’s. But (k − 1)(r + 1) ∼ (\frac{log n}{log C})(\frac{log C}{log B}) + k − r ∼ \frac{log n}{log B} + k − r. Having generated the a_{j}, we do the following, in 2r steps:

a_{r} → a_{r}·C → a_{r}·C+a_{r−1} → (a_{r}·C+a_{r−1})·C → ⋯ → a_{r}C^{r}+a_{r−1}C^{r−1}+⋯+a_{1}C+a_{0} = n.

The total time is less than k · B + \frac{log n}{log B} + r ∼ \frac{log n}{(log log n)^{3}} · log log n + \frac{log n}{log log n−3 log log log n} + \frac{log n}{(log log n)^{2}} = \frac{log n}{log log n} + \frac{3 log n log log log n}{(log log n)^{2}} + O(\frac{log n}{(log log n)^{2}} ) ≤ g(n). □

Remark. Using essentially the same proof we can replace g(n) by \frac{g(n)}{p−1} if we have the binary product and the p-ary sum s(x_{1}, x_{2}, …, x_{p}) = x_{1} + x_{2} + ⋯ + x_{p}.

Section 3: The cost of Polynomials

We shall extend the previous results to polynomials in several variables whose coefficients are integers or natural numbers.

Let P (X_{1}, X_{2}, …, X_{k}) be a polynomial. We define τ(P) as the minimum m ∈ N such that there exists a sequence (s_{−k}, s_{1−k}, …, s_{−1}, s_{0}, s_{1}, …, s_{m}), where s_{−i} = X_{i}, i = 1, 2, …, k; s_{0} = 1 and s_{m} = P, such that for each ℓ ≥ 1 there are i, j < ℓ with s_{ℓ} = Op(s_{i}, s_{j}), Op ∈ {+, −, 0}. Theorem 3. Let P be a polynomial whose coefficients are natural numbers.

Let d_{i} be the degree of P in the variable X_{i}, and let

h(P) = (1 + d_{1})(1 + d_{2}) … (1 + d_{k}) max_{(I)} log(1 + a_{(I)}),

where a_{(I)} are the coefficients of P. Then, we have the following results:

i) τ(P) ≥ \frac{h(P)}{log h(P)} for almost all P (in the sense that the ratio of the number of polynomials that satisfy this property to the number of polynomials with h(P) ≤ M tends to 1 as M tends to infinity);

ii) For any given ε > 0, τ(P) ≤ \frac{(1+ε)h(P)}{log h(P)}, provided h(P) is large enough. Remark 1. If we consider polynomials with integer coefficients we still have the above, results provided we define

h(P) = (1 + d_{1})(1 + d_{2}) … (1 + d_{k}) max_{(I)} log(1 + 2 |a_{(I)}|).

Remark 2. In the proof below we work with log = log_{2}. Proof. i) Given d_{1}, d_{2}, …, d_{k} and M ∈ N, there are N = (1 + M)^{(1+d_{1})(1+d_{2})(1+d_{k})} polynomials with degrees bounded by the d_{i}’s and with max_{(I)} a_{(I)} ≤ M (the a_{(I)}’s are natural numbers). Since \frac{log N}{log log N} = \frac{h}{log h}, where h = (1 + d_{1}) … (1 + d_{k}) log(M + 1), the result will follow exactly as in Theorem 1, Corollary.

ii) Let B = [\frac{h(P)}{(log h(P))^{3}} ], C = B^{[log h(P)]}. At least one of the two following cases must

occur: ii.1) max_{(I)} a_{(I)} ≥ C^{[log h(P)]}. In this case we proceed as in the Theorem 2. We construct

1, 2, …, B − 1, B, 2B, …, (B − 1)B, …, (B − 1)B^{[log h(p)]}, C and then construct all the a_{(I)}’s using basis C, writing the obtained coefficients in basis B. After this, we obtain the polynomial term by term. The total cost of this is bounded by B \frac{log C}{log B} + (1 + \frac{log M}{log B} + \frac{log M}{log C} + \frac{log C}{log B} ) D + 2D, where M = max_{(I)}(1 + a_{(I)}) and D = (1 + d_{1})(1 + d_{2}) … (1 + d_{k}), and so is bounded by (1 + \frac{ε}{2})\frac{D log M}{log B} < (1 + ε)\frac{h(P)}{log h(P)}, for h(P) sufficiently large.

ii.2) 2^{(1+d_{i})} ≥ C^{[log h(P)]} for some i, say for i = 1. Let M = max_{(I)}(1 + a_{(I)}). We have two subcases:

ii.2.1) M ≥ 2^{\sqrt{log h(P)}}: In this case we construct all the polynomials ∑_{j=0}^{r−1} δ_{j}X_{1}^{j}, with δ_{j} ∈ \{0, 1\},

∀j and r = [log B] + 1, forming the set β and then we construct all the polynomials in the set Γ = {X_{1}^{jr} · P | P ∈ β, 0 ≤ j ≤ [log h(P)]}. Let t = X_{1}^{r[log h(P)]} and

A = { ∑_{j=0}^{r[log h(p)]} δ_{j}X_{1}^{j}, δ_{j} ∈ {0, 1}}. Then, we can write

(*) P (x) = ∑ ã_{(I)} · 2^{i_{0}}t^{i_{1}}X_{2}^{i_{2}}X_{3}^{i_{3}} … X_{k}^{i_{k}}, where i_{0} < log(M + 1), i_{1} ≤ \frac{d_{1}}{r[log h(P)]},

i_{r} ≤ d_{r} for r ≥ 2 and ã_{(I)} ∈ A. An element of A can be obtained as the sum of [log h(P)] elements of Γ, and, since the total number of coefficients ã_{(I)} is bounded by (1 + log(M + 1)) (1 + \frac{d_{1}}{r[log h(P)]}) (1 + d_{2}) … (1 + d_{k}), we can obtain all the ã_{(I)}’s and then obtain P using (*), and we can estimate the total cost as before, obtaining τ(P) ≤ \frac{(1+ε)h(P)}{log h(P)}, for h(P) sufficiently large.

ii.2.2) M < 2^{\sqrt{log h(P)}}: In this case we construct all the polynomials ∑_{j=0}^{r−1} δ_{j}X_{1}^{j}, with δ_{j} ∈

\{0, 1, 2, …, M − 1\}, ∀j and r = [\frac{log B}{log M}], forming the set β and then we construct all the polynomials in the set Γ = {X_{1}^{jr} · P | P ∈ β, 0 ≤ j ≤ [log h(P)]}. Let t = X_{1}^{r[log h(P)]}

and A = { ∑_{j=0}^{r[log h(p)]} δ_{j}X_{1}^{j}, δ_{j} ∈ {0, 1, 2, …, M − 1}}. Then we can write

(*)  P (x) = ∑ ã_{(I)} · t^{i_{1}}X_{2}^{i_{2}}X_{3}^{i_{3}} … X_{k}^{i_{k}}, where i_{1} ≤ \frac{d_{1}}{r[log h(P)]},

i_{r} ≤ d_{r} for r ≥ 2 and ã_{(I)} ∈ A. An element of A can be obtained as the sum of [log h(P)] elements of Γ, and, since the total number of coefficients ã_{(I)} is bounded by (1 + \frac{d_{1}}{r[log h(P)]}) (1+d_{2}) … (1+d_{k}), we can obtain all the ã_{(I)}’s and then obtain P using (*), and we can estimate the total cost as before, obtaining τ(P) ≤ \frac{(1+ε)h(P)}{log h(P)}, for h(P) sufficiently large.

Remark. The case of integer coefficients with max_{(I)} |a_{(I)}| = M is essentially equivalent to the case of natural coefficients with max_{(I)} a_{(I)} = 2M. We can easily see this by adding or subtracting the polynomial M(1 + X_{1} + ⋯ + X_{1}^{d_{1}}) … (1 + X_{k} + ⋯ + X_{k}^{d_{k}}), which has very small cost.

Section 4: Remarks and open problems.

The most important open question related to τ(n) is to decide whether there are natural numbers m_{k} ≥ 1 and a C > 0 such that τ(m_{k} · k!) ≤ (log k)^{C}, ∀k ∈ N. If such a sequence does not exist then the algebraic version of NP ≠ P is true, as is proved in [SS]. About this question we have the following remarks:

• If there is a C > 0 such that τ(C_{2^{n}}^{2^{n−1}}) ≤ n^{C} then there exists such a sequence m_{k}, namely m_{k} = (2^{[log_{2} k]+1})!/k!, because (2^{n})! = C_{2^{n}}^{2^{n−1}}(C_{2^{n−1}}^{2^{n−2}})^{2}(C_{2^{n−2}}^{2^{n−3}})^{4} … (C_{2}^{1})^{2^{n−1}} therefore τ((2^{n})!) ≤ n^{C′}, for some constant C′. (C_{2^{n}}^{2^{n−1}} is the central coefficient of (1+X)^{2^{n}} and, given X, we can compute (1 + X)^{2^{n}} using n + 1 operations.)

• If we have the operations +, ·, − and 2^{n} then there exists such a sequence m_{k}. Indeed, we can construct a sequence M_{k} with τ(M_{k}) ≤ 4k satisfying n ≤ 2^{k} hence n|M_{k}. It is enough to take M_{0} = 1, M_{k+1} = 2^{M_{k}}(2^{2M_{k}} − 1), because n ≤ 2^{k+1}, nodd ⇒ \frac{φ(n)}{2} ≤ 2^{k} ⇒ \frac{φ(n)}{2} |M_{k} ⇒ n| M_{k+1} (M_{k+1} is divisible by sufficiently large powers of 2). Now is easy to check that (2^{n})!|M_{0} · M_{1}^{2} · M_{2}^{4} … M_{n}^{2^{n}} =: P_{n}, which satisfies τ(P_{n}) ≤ \frac{5n(n+1)}{2}.

There is another open question concerning costs with bounded memory. Let g ≥ 1 and define τ_{g}(n) as τ(n) with the restriction that for each ℓ ≥ 1, s_{ℓ} = Op(s_{i}, s_{j}) with s_{i}, s_{j} ∈ {1, s_{ℓ−g}, s_{ℓ−g+1}, …, s_{ℓ−1}}. The question is to determine if there are g ≥ 1 and C > 0 such that τ_{g}(n) ≤ τ(n)^{C}, for every n ∈ N. About this we have the following remarks:

• If g = 5 and we have the operations +, −, ·, / and [ ] (the integer part function) then τ_{g}(n) ≤ τ(n)^{C} for some C. Indeed, if (s_{0}, s_{1}, …, s_{k}), s_{k} = n is a computing sequence for n we may keep 2s_{0} + 4s_{1} + 16s_{2} + ⋯ + 2^{2^{r}}s_{r}, in the position P 1 of the memory and use the position P 2 to generate 2^{2^{j}}. We obtain s_{j} doing [(\frac{X_{j}}{(2^{2^{j}})^{2}} − [\frac{X_{j}}{(2^{2^{j}})^{2}} ]) · 2^{2^{j}}] = s_{j}, (recall that s_{j} ≤ 2^{2^{j−1}}) where X_{j} = 2s_{0} + 4s_{1} + ⋯ + 2^{2^{j}}s_{j}. We put s_{i} and s_{j} on the positions P 3 and P 4 and do Op(s_{i}, s_{j}) = s_{r+1}. Then we put s_{r+1} in the position P 3 and X_{r+1} = X_{2} + 2^{2^{r+1}}s_{r+1} in the position P 1. We proceed so until we obtain s_{k}. It is easy to see that the total time is polynomially related to τ(n) = k.

• If g = 1 and the operations are +, −, · and / then τ_{g} is not polynomially related to τ. Indeed, we can only transform an s_{i} into s_{i+1} = s_{i} ± 1, s_{i+1} = 2s_{i} or s_{i+1} = s_{i}^{2}.

If (s_{0}, s_{1}, …, s_{k}) is a computing sequence for n = s_{k}, and r is the maximum index such that s_{r} = s_{r−1}^{2}, we will have s_{k} = 2^{m}s_{r−1}^{2} + p, with m ≥ 0, |p| ≤ 2^{k−r} ≤ 2^{k} hence there is ℓ ∈ N such that |n − ℓ^{2}| ≤ 2^{k} or |n − 2ℓ^{2}| ≤ 2^{k}. If X_{m} = \frac{1}{2}((3 + 2\sqrt{2})^{2^{m}} + (3 − 2\sqrt{2})^{2^{m}}), Y_{m} = \frac{1}{2\sqrt{2}}((3 + 2\sqrt{2})^{2^{m}} − (3 − 2\sqrt{2})^{2^{m}}), n = X_{m}^{2} + 2^{2^{m}}, then X_{m}^{2} − 2Y_{m}^{2} = 1, X_{m+1} = 2X_{m}^{2} − 1 so τ(X_{m}) ≤ 3m and τ(X_{m}^{2} + 2^{2^{m}}) ≤ 4m + 1, but if a ∈ N, |a^{2} − (X_{m}^{2} + 2^{2^{m}})| ≥ min{2^{2^{m}}, |(X_{m} + 1)^{2} − (X_{m}^{2} + 2^{2^{m}})|} = 2^{2^{m}}, and |2a^{2} − (X_{m}^{2} + 2^{2^{m}})| = |2a^{2} − 2Y_{m}^{2} − 1 − 2^{2^{m}} | ≥ min{2^{2^{m}}+1, |2((Y_{m} + 1)^{2} − Y_{m}^{2}) − 1 − 2^{2^{m}} |} = 2^{2^{m}} + 1 ⇒ 2^{k} ≥ 2^{2^{m}} thus k ≥ 2^{m}, so τ_{1}(X_{m}^{2} + 2^{2^{m}}) ≥ 2^{m} >> τ(X_{m}^{2} + 2^{2^{m}})^{C}, ∀C > 0 fixed, if m is large enough.

Notice, however, that τ_{1}(2^{2^{k}}) = k + 1, and τ_{1}(n) ≤ 2 log_{2} n, for every n ∈ N.

Acknowledgements. I would like to thank Steve Smale, Mike Shub, Welington de Melo and Benar Svaiter for many helpful conversations and sugestions of questions which are discussed in this article.

References:

[SS] Shub, Michael and Smale, Steve. On the Intractability of Hilbert’s Nullstellensatz and an algebraic version of “NP ≠ P?”, to appear.

[MS] de Melo, W. and Svaiter, B.F.. The cost of computing integers, to appear.

[H] Heintz, Joos. “On the Computational Complexity of Polynomials and Bilinear Mappings. A Survey” in Applied Algebra, Algebraic Algorithms and Error-Correcting Codes (Edited by G. Goos and J. Hartmanis), Lecture Notes in Computer Science 356, Springer Verlag.