<figure><img src="image_1.png" /></figure>

laboria

laboratoire de recherche
en informatique
et automatique

AN OPTIMAL LOWER BOUND
ON THE NUMBER OF TOTAL
OPERATIONS TO COMPUTE
0-1 POLYNOMIALS
OVER THE FIELD OF
COMPLEX NUMBERS

Jean-Paul Van de WIELE

Rapport de Recherche N° 303

Mai 1978

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20
# AN OPTIMAL LOWER BOUND ON THE NUMBER OF TOTAL OPERATIONS TO COMPUTE 0-1 POLYNOMIALS OVER THE FIELD OF COMPLEX NUMBERS

Jean-Paul Van de Wiele

## Résumé :

Nous montrons l'existence de polynômes de degré n à coefficients 0-1 dont le calcul sur $C$ requiert $\Omega(n/\log n)$ opérations arithmétiques. Auparavant la meilleure borne était $\Omega(n^{1/2}/\log n)$. Nous obtenons ainsi la première borne inférieure asymptotiquement optimale de la complexité sur $C$ des polynômes 0-1. Nous améliorons également la borne inférieure de la complexité additive de ces polynômes dans le même modèle en montrant qu'il existe des polynômes 0-1 de degré n dont le calcul sur $C$ requiert $\Omega(n^{1/2}/\log n)$ additions. La meilleure borne était auparavant dans ce cas $\Omega(n^{1/3}/\log n)$.

## Abstract :

We show an $\Omega(n/\log n)$ lower bound on the total number of operations necessary to compute 0-1 polynomials of degree n in the model with complex preconditioning. The best previous result was $\Omega(n^{1/2}/\log n)$. This yields the first asymptotically optimal lower bound on the complexity of 0-1 polynomials in this model. We show also that there are 0-1 polynomials of degree n that require $\Omega(n^{1/2}/\log n)$ additive operations over $C$. The best previously shown lower bound on additions was $\Omega(n^{1/3}/\log n)$.
# 1. INTRODUCTION

In order to get lower bounds on the number of operations necessary to compute 0-1 polynomials, in the model with general complex preconditioning, one can use the method which Strassen has presented in [12] to derive lower bounds for concrete polynomials with rational and algebraic coefficients. This idea has been first exploited by Lipton [6] and lateron by Lipton, Stockmeyer [7], Hyafil, Van de Wiele [5] and Schnorr [11]. By using the same approach we show in this paper that there are univariate 0-1 polynomials with degree $n$ that require $\Omega(n/\log n)$ total arithmetic operations over $C$. This result yields the first asymptotically optimal lower bound on the complexity of 0-1 polynomials in the general complex model since Savage [10] has shown that every univariate 0-1 polynomial with degree $n$, can be realized over $C$ with $O(\sqrt{n})$ scalar multiplications, $O(\sqrt{n})$ non scalar multiplications and $O(n/\log n)$ additive operations. The best previous lower bound on the number of total operations for 0-1 polynomials was $\Omega(n^{1/2}/\log n)$ (See Hyafil, Van de Wiele [5] and Schnorr [11]).

In the same model an $\Omega(n^{1/3}/\log n)$ lower bound has been shown in [5] on additions/subtractions. We improve here this result by showing that there are 0-1 polynomials of degree $n$ that require $\Omega(n^{1/2}/\log n)$ additive operations over $C$.

The best lower bound on the number of multiplications/divisions to compute 0-1 polynomials has been obtained so far by Schnorr [11] who has shown that there exist 0-1 polynomials with degree $n$ that cannot be evaluated over $C$ with less than $(n^{1/2}/4 \log n)$ non scalar multiplicative operations. Before that Lipton [6] has shown an $\Omega(n^{1/4}/\log n)$ lower bound and $\Omega(n^{1/3}/\log n)$ has been obtained in [5].

One can notice that the $\Omega(n/\log n)$ lower bound on the number of total operations and the $O(\sqrt{n})$ upper bound on the number of multiplications strongly suggest an $\Omega(n/\log n)$ lower bound on the number of additions. As it is the case for polynomials with rational coefficients the additive complexity of 0-1 polynomials is less understood than their multiplicative complexity (for polynomials in $Q[x]$ the best lower and upper bounds on
the number of multiplications and additions are respectively $\Omega(\sqrt{n})$, $O(\sqrt{n})$ and $\Omega(n^{1/2})$, $O(n)$. As pointed out by Borodin, Cook in [1], unlike the situation in the multiplicative case we don't know if the use of unlimited multiplicative operations can in general reduce the $\pm$ complexity of polynomials in $Q[x]$. The interested reader may find in Borodin, Cook [1] and Van de Wiele [13] a new line of research concerning the additive complexity of specific polynomials.

Better lower bounds on the complexity of 0-1 polynomials have been obtained in more restrictive models of computation. Paterson, Stockmeyer [8] have shown that there are 0-1 polynomials that require over $Z$ (and without divisions) $\Omega(n^{1/2})$ non scalar multiplications. In the same model Rivest, Van de Wiele [9] have obtained an $\Omega((n/\log n)^{1/2})$ lower bound on the number of additions. In the model with finite preconditioning Dobkin, Lipton [3] have shown an optimal lower bound ($\Omega(n/\log n)$) on the number of additions, hence on the number of total operations.

One can notice finally that all known results on the complexity of 0-1 polynomials are only existence results. Noone has been able so far to exhibit a specific "hard to compute" 0-1 polynomial. However a partial result has been obtained in a restricted model of computation by Hyafil, Van de Wiele in [4].

The mentioned above new lower bounds appear in § 3,4 as Corollaries of Theorem 2.3, stated in § 2, which yields a frame to derive lower bounds on the number of operations to compute 0-1 polynomials for various basis of arithmetic operations.

## 2. A FRAME TO DERIVE LOWER BOUNDS ON THE COMPLEXITY OF 0-1 POLYNOMIALS.

We set a frame (Theorem 2.3.) to derive lower bounds on the minimum number of operations necessary to compute univariate 0-1 polynomials over $\mathbb{C}$.

### 2.1. Definitions and model of computation.

Let $N'$, $N$, $Z$, $Q$ and $\mathbb{C}$ stand for the set of positive natural numbers, nonnegative natural numbers, integers, rational numbers and complex numbers,
respectively. Let $k$ be a field, $x$ an indeterminate over $k$. $k[x]$ is the ring of polynomials, $k[[x]]$ is the formal power series ring and $k(x)$ is the field of rational functions in $x$ over $k$. Let $y$ be a real number ; $[y]$ is the greatest integer $\le y$, $\lceil y \rceil$ is the least integer $\ge y$. The abbreviation $\log$ stands always for $\log_2$. If $f$ and $g$ are functions from $N$ to $N$, $f(n) = \Omega(g(n))$ means that there is a positive constant $\gamma$ such that finally $f(n) \ge \gamma g(n)$.

A *computation* $\beta$ in $C(x)$ mod. $C \cup \{x\}$ for $p(x) \in C(x)$ is a sequence of computation steps $S_i$, $1 \le i \le 1$, such that there is $i_0$, $1 \le i_0 \le 1$, with $S_{i_0} = p(x)$ and either

(i) $S_i \in C \cup \{x\}$ or

(ii) $S_i = S_j o S_k$ with $j, k < i,$

$o \in \{+, -, ., /\}$ and $S_k \ne 0$ if $o = /$. The rational functions $S_i$, $1 \le i \le 1$, are the results of the computation. Let $\theta$ be a set of operations partially defined over $C(x)$ such that each $\omega \in \theta$ is the restriction over some subset $F \subset C(x)$ of some $\omega' \in \{+, -, ., /\}$ defined over $C(x)$. $\theta$ is called a *subset of arithmetic operations* over $C(x)$ and an operation in $\theta$ is called a *$\theta$-operation*. For instance $\theta$ may be the set of additive operations $\{+, -\}$ or the set of non scalar multiplicative operations. The *$\theta$-length* of the computation $\beta$ is the number of steps $S_i = S_j o S_k$ such that $S_j, S_k \in F_\omega$ and $S_i = \omega(S_j, S_k)$ with $\omega \in \theta$. The *$\theta$-complexity* $L(\theta,p)$ of $p \in C(x)$ is the minimal $\theta$-length of a computation for $p$ in $C(x)$ mod. $C \cup \{x\}$.

Let $\beta$ be a computation in $C(x)$ mod. $C \cup \{x\}$. For the sake of simplicity we say that $\beta$ is a computation over $C$. Let $\gamma \in C$ be such that $S_i(\gamma)$ is defined and is different from zero for all results $S_i$ of $\beta$ but for the identity function $x$, eventually. Then following Schnorr [11] $\beta$ is called *$\gamma$-admissible*.
In this case the computation can be carried out in the ring $C[[x - \gamma]]$ of formal power series in $(x - \gamma)$ and every result is a unit in $C[[x - \gamma]]$.
Any computation $\beta$ is $\gamma$-admissible for each $\gamma \in C - A_\beta$ where $A_\beta$ is a finite set in $C$, provided that the constant $O \in C$ is not a result of $\beta$. The latter condition will be assumed for any computation in the rest of this paper.
Let $k$ be a field. The following lemma has been first stated with minor modifications in [5, Lemme 11, p. 27-28].

**Lemma 2.2.** Let $m, m', c, q$ be integers such that $m \ge m' \ge 1$, $c \ge 2$, $q \ge 1$. Let $z_1, \dots, z_m$ be indeterminates over $Z$ and $P_1, \dots, P_q$ polynomials in $Z[z_1, \dots, z_m]$ such that $\max_{1 \le i \le q} \deg P_i \le c$. Then if $g \in N'$ is such that

$$ (1) \quad g^{q-m'} \ge \binom{m}{m'} c^{m'} q^q $$

there is a non trivial polynomial $H$ of degree $g$ in $Z[y_1, \dots, y_q]$ such that for all $\bar{\lambda} = (\lambda_1, \dots, \lambda_m) \in k^m$ with at most $m'$ non zero $\lambda_i$'s

$$ H(P_1(\bar{\lambda}), \dots, P_q(\bar{\lambda})) = 0. $$

**Proof.** Let $\Lambda_m' = \{\bar{\lambda} = (\lambda_1, \dots, \lambda_m) \in k^m \text{ such that at most } m' \text{ }\lambda_i\text{'s are } \neq 0\}$.

To show : there are integers $b_{i_1, \dots, i_q}$ (not all = 0) such that

$$ \sum_{o \le i_1 + \dots + i_q \le g} b_{i_1, \dots, i_q} \binom{i_1}{p_1} \binom{i}{p_q} (\bar{\lambda}) = 0 $$

for all $\bar{\lambda} \in \Lambda_m'$. Let $R = \sum_{i_1+\dots+i_q \le g} b_{i_1, \dots, i_q} \binom{i}{p_1} \binom{i}{p_q} (\bar{z}) \in Z[\bar{B}, \bar{z}]$

The coefficients of $R$ as a polynomial in $\bar{z}$ are linear forms in $Z[\bar{B}]$, i.e. linear forms in $\binom{g+q}{q} = M$ variables with integer coefficients. Every product $\prod_{k=1}^j \lambda_{ik}$, $1 \le i_k \le m$ of $j \ge (m'+1)$ distinct components of a $\bar{\lambda} \in \Lambda_m'$, is zero, according to the definition of $\Lambda_m'$. Hence we only have to show that the linear forms, coefficients of the monomials $z_1^{\alpha_1} \dots z_m^{\alpha_m}$ such that at most $m'$ $\alpha_i$'s are non zero, have a non trivial common zero in $Z^M$. As there are $\le \binom{m}{m'} \cdot \binom{gc+m'}{m'}$ such forms this will be true, this is a basic fact from linear algebra, whenever
$$
(2) \binom{m}{m'} \cdot \binom{gc+m'}{m'} < \binom{g+q}{q} \cdot \text{Assume (2) false. Thus}
$$

$$
(3) \binom{m}{m'} \cdot \binom{gc+m'}{m'} \ge \binom{g+q}{q} \cdot \text{Furthermore}
$$

$$
\binom{g+q}{q} > \left(\frac{g}{q}\right)^q \quad \text{since } g, q > 0 \quad \text{and} \quad \binom{gc+m'}{m'} \le (gc)^{m'} \quad \text{since } m' \ge 1,
$$
c ≥ 2 and g ≥ 2 according to requirement (1). Thus

$$
(3) \implies \binom{m}{m'} \cdot (gc)^{m'} > \left(\frac{g}{q}\right)^q \implies (4) \binom{m}{m'} c^{m'} q^q > g^{q-m'} , \text{ but (4) is contrary to hypothesis (1). We are done.}
$$

Let now θ be a subset of arithmetic operations over C. Let t be a
natural number and let L₀₁(θ,n) denote the maximal θ-complexity over C
of univariate polynomials p with 0-1 coefficients and deg p ≤ n. L₀₁(θ,n)
is the minimal integer q such that L(θ,p) ≤ q for all 0-1 polynomials p
with deg p ≤ n. A computation over C of p ∈ C[[x]] is defined in the same
manner as a computation over C of p ∈ C(x).

**Theorem 2.3.** Let $m, m'$ be functions from $N$ to $N$ and let $c$ be a function from $N^2$ to $N$ having following properties.

(i) There are real numbers $\gamma_1 > 0$, $\gamma_2 > 0$, $\gamma_3 > 0$, $\mu$, $\mu'$ with $\mu \ge \mu' \ge 1$ and there are integers $t_o \ge 1$ and $n_o \ge 1$ such that for all natural numbers $t \ge t_o$ and $n \ge n_o$

$$
(5) \quad \left\{
\begin{array}{l}
0 < m'(t) \le m(t) \le \gamma_1 t^{\mu}, \\
m'(t) \le \gamma_2 t^{\mu'} \quad \text{and} \\
c(n,t) \le n^{\gamma_3 t^{\nu}} \quad \text{for } t_o \le t \le 2n.
\end{array}
\right.
$$
(ii) For each $(t,n) \in (N')^2$ there is a finite sequence $p_{t,o}^n, p_{t,1}^n, \dots, p_{t,n}^n$ of
polynomials in $Z[z_1, \dots, z_m(t)]$ with $\deg p_{t,i}^n \le c(j,t)$ for all
natural numbers $i, j$ with $n \ge j \ge i \ge 0$, and for each
$p(x) = \sum_{i \ge 0} \alpha_i x^i \in C([x])$ that can be computed over $C$ within
$\le t$ $\theta$-operations by some $0$-admissible computation there is a
$\bar{\lambda} = (\lambda_1, \dots, \lambda_m(t)) \in C^{m(t)}$ such that

(ii₁) _at most_ m'(t) components $\lambda_i$ of $\bar{\lambda}$ are non zero numbers and

(ii₂) $\alpha_i = P_{t,i}^n (\lambda_1, \dots, \lambda_m(t))$ for $0 \le i \le n$.

Then there is a real constant $\gamma > 0$ such that for all integers $n \ge 2$

$$
L_{o1}(\theta, n) \ge (\gamma \cdot n^{\frac{1}{\mu' + \nu}}) / \log n. \square
$$

**Proof**. Let $n$ and $t$ be natural numbers with $n \ge n_o$ and $2 \le t \le 2n$. Let $C(\theta,n,\frac{t}{2})$ be the subset of polynomials $p \in C[x]$ with $\deg p \le n$ that can be computed over $C$ within $\le \frac{t}{2} \theta$-operations. Let $p(x) = \sum_{i=0}^{n} \alpha_i x^i \in C(\theta,n,\frac{t}{2})$ and let $\beta$ be a computation for $p$ in $C(x)$ mod. $C \cup \{x\}$ For all but finitely many $\gamma \in C$ $\beta$ is $\gamma$-admissible and $p(x) = \sum_{i \ge 0} \alpha_i (\gamma) (x-\gamma)^i \in C([x-\gamma])$ can be computed in $C([x-\gamma])$ mod. $C \cup \{x-\gamma\}$ within $\le \frac{t}{2} + 1 \le t \theta$-operations by some $0$-admissible computation. (This is because $x$ can be computed from $(x-\gamma)$ by at most one $\theta$-operation). Hence, according to hypothesis (ii) in which we substitute $(x-\gamma)$ for $x$, for all but finitely many $\gamma \in C$ there is some $\bar{\lambda}_{\gamma} = (\lambda_{\gamma,1}, \dots, \lambda_{\gamma,m(t)}) \in C^{m(t)}$ such that at most $m'(t)$ $\lambda_{\gamma,i}$'s are non zero and

$$
(6) \alpha_i(\gamma) = P_{t,i}^n (\lambda_{\gamma,1}, \dots, \lambda_{\gamma,m(t)}) \text{ for } i \ge 0.
$$
Now, according to (6), Lemma 2.2. and Hypothesis (ii), whenever $g \in N'$ is
such that

$$
(7) \quad g^{n-m'}(t) \ge \binom{m(t)}{m'(t)} \cdot c(n,t) m'(t) \cdot n^n
$$

there is a non trivial polynomial $H_t \in Z[y_1, ..., y_n]$ of degree $g$ sucht
that

$$
(8) \quad H_t(\alpha_1(\gamma), \dots, \alpha_n(\gamma)) = 0.
$$

Note that $H_t$ depends only on $m(t)$, $m'(t)$, $c(n,t)$, $n$ and $p_{t,1}^n, \dots, p_{t,n}^n$,
hence on $n$ and $t$ *but not* on the specific polynomial $p(x) = \sum_{i=0}^{n} \alpha_i x^i$
and on the specific $\gamma$. (8) holds for all but finitely many $\gamma \in C$.

Therefore $H_t(\alpha_1(0), \dots, \alpha_n(0)) = H_t(\alpha_1, \dots, \alpha_n) = 0$ since the $\alpha_i(\gamma)$ are
continuous in $\gamma$. We have thus shown that $H_t(\alpha_1, \dots, \alpha_n) = 0$ for all
$p = \sum_{i=0}^{n} \alpha_i x^i$ in $C(\theta, n, \frac{t}{2})$.

Since $H_t$ is a non trivial polynomial there is some $\bar{a} = (a_1, ..., a_n) \in \mathbb{N}^n$
such that

$$
(9) H_t(\bar{a}) \neq 0 \text{ and}
$$

$$
(10) \quad 0 \le a_i \le \deg H_t = g \quad \text{for } 1 \le i \le n. \text{ Let } p_o(x) = \sum_{i=1}^{n} a_i x^i. \text{ (9) implies}
$$

$$
(11) \quad L(\theta, p_o) > \frac{t}{2}.
$$

On the other hand $L_{O1}(\theta,n)$, the maximal $\theta$-complexity of 0-1 polynomials
with degree $\le n$, is related to $L(\theta, p_o)$ through

$$
(12) \quad L(\theta, p_o) \le L_{O1}(\theta, n) \cdot (1 + \log(\max_i a_i)) + 2 \log(\max_i a_i) + 1.
$$

To show (12) just take the binary decomposition of the $a_i$'s (personal
remark of H.T. Kung). (10) and (12) imply that there is a natural number
$n_1 \ge n_o$ such that
(13) $L(\theta, p_o) \le 3 L_{01}(\theta, n) \cdot \log g,$
provided that $L_{01}(\theta,n) \ge 1$ for $n$ large enough, which will be true in
both subsequent applications.

Now (11) and (13) yield : $L_{01}(\theta,n) > \frac{t}{6 \log g}$. We have thus shown
that for all $n \ge n_1$ in $N$

$$
(14) \quad L_{01}(\theta,n) \ge \sup_{t \in N} \left[ \frac{t}{6 \log g} \right], \quad \text{where } g \text{ satisfies (7).} \\
2 \le t \le 2n
$$

Now we are going to use the upper bounds (5) in Hypothesis (i) of
Theorem 2.3. . (7) holds whenever $g^{n-m'} \ge (mc)^{m'}. n^n$. Put $t_l = \max(2,t_o)$.
Therefore, for all natural numbers t,n with $t_l \le t \le 2n$ and $n \ge n_l$ ,
(7) holds, according to bounds (5), whenever

$$
(15) \quad g^{n-\gamma_2} t^{\mu'} \ge \left[ \gamma_1 t^{\mu} \cdot n^{\gamma_3} t^{\nu} \right]^{\gamma_2} t^{\mu'} \cdot n^n.
$$

There is a natural number $n_2 \ge n_1$ and a real positive constant $\gamma_4 \ge \gamma_3$
such that for all $n \ge n_2$ and for all $t \ge 1$: $\gamma_1 t^\mu \cdot n^{\gamma_3 t^\nu} \le n^{\gamma_4 t^\nu}$. Choose
some real number $\varepsilon$ with $0 < \varepsilon < 1$. Assuming $n \ge n_2$ and $\gamma_2 t^{\mu'} \le (1-\varepsilon)n$,
(15) holds whenever

$$
(16) \quad g \ge n^{\frac{[\gamma_2 \gamma_4 t^{(\mu'+\nu)}]}{\epsilon n}} \cdot n^{\frac{1}{\epsilon}}
$$

Set $t = \lfloor t_n \rfloor$ with $t_n = (\gamma_5 n)^{1/(\mu'+\nu)}$, $\gamma_5$ being a real number such that $0 < \gamma_5 < 1$, $t_l \le t_n \le 2n$ and

$$
\gamma_2 t_n^{\mu'} = n^{\mu'/(\mu'+\nu)} \cdot \left[ \gamma_2 \gamma_5^{\mu'/(\mu'+\nu)} \right] \le (1-\epsilon)n
$$

for all $n \ge n_2$. It is possible to find such a $\gamma_5$ since $\mu' + \nu \ge \mu' \ge 1$
according to Hypothesis (i). Then (16) holds if $g \ge n$ $(\gamma_2 \gamma_4 \gamma_5 + 1)/\epsilon$

Returning to (14), taking $t = \lfloor t_n \rfloor$ and putting $\gamma_6 = \epsilon/6(\gamma_2 \gamma_4 \gamma_5 + 1)$ we get

$$L_{01}(\theta, n) \geq [\gamma_6 / \log n] \cdot \lfloor (\gamma_5 n)^{1/(\mu'+\nu)} \rfloor$$

for all $n \ge n_2$. Thus there is a natural number $n_3 \ge n_2$ and a positive real number $\gamma_7$ such that for all integers $n \ge 2$

$$L_{01}(\theta, n) \ge [\gamma_7 \cdot n^{1/(\mu'+\nu)}] / \log n.$$

We are done.□

In the next sections we apply Theorem 2.3. to concrete situations by specifying the subset $\theta$ of arithmetic operations. In each case we have to show the existence of appropriate functions $m, m', c$ and to specify the values of parameters $\mu, \mu'$ and $\nu$. We first study the total number of arithmetic operations (additions, subtractions, multiplications, divisions) and we obtain an $\Omega(n/\log n)$ lower bound for 0-1 polynomials of degree $n$. This lower bound is asymptotically optimal since Savage [10] has shown that every 0-1 polynomial of degree $n$ can be realized with $O(\sqrt{n})$ multiplications and $O(n/\log n)$ additions. The best previously known lower bound was $\Omega(n^{1/2}/\log n)$. (See [5], [11]).

We then study the number of additive operations $(+, -)$ and show an $\Omega(n^{1/2}/\log n)$ lower bound. The best previously known bound was $\Omega(n^{1/3}/\log n)$. (See [5]).

The best known lower bound on the number of multiplications for 0-1 polynomials is $n^{1/2}/4 \log n$. (See Schnorr [11]).
### 3. AN $\Omega(n/\log n)$ LOWER BOUND ON THE TOTAL NUMBER OF ARITHMETIC OPERATIONS NECESSARY TO COMPUTE 0-1 POLYNOMIALS.

**Lemma 3.1.** There are real numbers $\gamma_1 > 0$ and $\gamma_2 > 0$, there is a natural number $t_0$ and for each $t \in \mathbb{N}$ there are polynomials $P_{t,j} \in \mathbb{Z}[z_1, \dots, z_m(t)]$, $0 \le j < +\infty$, with $1 \le m(t) \le \gamma_1 t^2$ and $\deg P_{t,j} \le \gamma_2$ for $t \ge t_0$ and $j \ge 1$, which have following property. Let $p(x) = \sum_{j \ge t_0} \alpha_j x^j \in \mathbb{C}[[x]]$ be a power series that can be computed within $\le t$ arithmetic operations (i.e. additions, subtractions, multiplications and divisions) by some 0-admissible computation. Then there is some $\bar{\lambda} = (\lambda_1, \dots, \lambda_m(t)) \in \mathbb{C}^{m(t)}$ such that

$$ \sum_{j \ge 0} \alpha_j x^j = \sum_{j \ge 0} P_{t,j}(\bar{\lambda}) \cdot x^j. \square $$

*Proof.* See Schnorr [11, Theorem 2.5., p. 138-139]. In Schnorr's theorem t is the number of non scalar multiplicative operations. But if $\beta$ is a computation for $p(x)$ with $\le t$ arithmetic operations, $\beta$ is also trivially a computation for $p(x)$ with $\le t$ non scalar operations. $\square$

Using Lemma 3.1 Schnorr has shown an $\Omega(n^{1/2}/\log n)$ lower bound on the number of non scalar operations for 0-1 polynomials. Indeed Theorem 2.3 applies with $\mu = \mu' = 2$ and $\nu = 0$. He improved on previous results by showing $\nu = 0$. Lipton [6] has obtained $\Omega(n^{1/4}/\log n)$ by showing $\nu = 2$ and $\Omega(n^{1/3}/\log n)$ has been obtained in [5] by showing $\nu = 1$. We can do better for the number of total operations by showing $\mu' = 1$.

**Lemma 3.2.** There is a real number $\gamma_3 > 0$ and a natural number $t_1 \ge t_0$ such that for each $t \in \mathbb{N}$ with $t \ge t_1$ and for each $p(x) \in \mathbb{C}[[x]]$ that can be computed over $\mathbb{C}$ with $\le t$ arithmetic operations by some 0-admissible computation there are at most $m'(t) \le \gamma_3 t$ non zero numbers among the values $\lambda_1, 1 \le i \le m(t)$, associated to $p$ by Lemma 3.1. above. $\square$
**Proof.** Let $\beta$ be a computation for $p(x)$ with $\le t$ arithmetic operations.
Then $p(x)$ can be computed with the following scheme with $m_{i,j}, m'_{i,j} \in \mathbb{C}$
and $\bar{m}_v \in \{0,1\}$:

$$3.3. \quad \left\{ \begin{array}{l} s_{-3} = -1, s_0 = x, \\ s_{3r-2} = \sum_{j=-1}^{r-1} m_{r,j} s_{3j}, s_{3r-1} = \sum_{j=-1}^{r-1} m'_{r,j} s_{3j}, \\ s_{3r} = s_{3r-2}((1-\bar{m}_r) s_{3r-1} + \bar{m}_r / s_{3r-1}) \quad \text{for } r=1,\dots,t, \\ p(x) = s_{3t+1} = \sum_{j=-1}^{t} m_{t+1,j} s_{3j}. \end{array} \right.$$

There are altogether $t^2 + 3t + 2$ parameters $m_{ij}, m'_{ij}, \bar{m}_v$. But, since there are $\le t$ arithmetic operations in $\beta$, necessarily at most $\gamma_3 t$ of these are non-zero numbers, for $t$ large enough. $\square$

By using Lemma 3.2 ($\mu' = 1$) and showing $\nu = 1$ Hyafil, Van de Wiele [5] got $\Omega(n^{1/2}/\log n)$ for total operations. By using Schnorr's improvement on the degree bound of the polynomials $P_{t,j}$ ($\nu = 0$) we obtain here an asymptotically optimal lower bound. Set $\theta_\tau = \{+, -, ., /\}$ and write $L(p) = L(\theta_\tau,p)$ and $L_{01}(\theta_\tau,n) = L_{01}(n)$.

**Corollary 3.4.** There is $\gamma > 0$ such that for all natural numbers $n \ge 2$ there is $\bar{b} = (b_0, \dots, b_n) \in \{0,1\}^{n+1}$ such that
$$L\left(\sum_{i=0}^{n} b_i x^i\right) \ge \gamma n / \log n.$$

This lower bound is asymptotically optimal. $\square$
**Proof.** According to Lemmas 3.1. and 3.2. Theorem 2.3. applies with $\mu = 2$, $\mu' = 1$, and $\nu = 0$. To show last equality note that for each $t \ge t_o$:

$\deg P_{tj} \le \gamma_2jt = c(j,t)$ for all natural numbers $j \ge i \ge 1$. Therefore there is an integer $n_o$ and a real number $\gamma_4$ such that for all $n \ge n_o$ and for all $t$ with $t_o \le t \le 2n$

$$c(n,t) = \gamma_2nt \le 2\gamma_2n^2 \le n = n^0$$

Therefore there is $\gamma > 0$ such that

$$L_{01}(n) \ge \gamma.n^{1/(1+0)}/\log n = \gamma n/\log n.$$

Savage [10] has shown an $O(n/\log n)$ upper bound. Therefore this lower bound is asymptotically optimal. $\square$

### 4. $\underline{AN \Omega(n^{1/2}/\log n)}$ **LOWER BOUND ON THE NUMBER OF ADDITIVE OPERATIONS FOR O-1 POLYNOMIALS.**

**Lemma 4.1.** *There are real numbers $\gamma_1 > 0$, $\gamma_2 > 0$ there is $t_o \in N'$ and for all $(t,n) \in (N')^2$ there are polynomials $P_{t,j}^n \in Z[z_1, \dots, z_m(t)]$ for $0 \le j \le n$, with $m(t) \le \gamma_1 t^2$ and $\deg P_{t,j}^n \le \gamma_2 jt$ for $t \ge t_o$ and $j \ge 1$, having following property. Let $p(x) = \sum_{j \ge 0} \gamma_j x^j \in C[[x]]$ be a power series that can be computed over $\mathbb{C}$ within $\le t$ additive operations and an arbitrary number of multiplicative operations by some $O$-admissible computation. Then there is $\bar{\lambda} = (\lambda_1, \dots, \lambda_m(t)) \in \mathbb{C}^{m(t)}$ such that*

$$\sum_{j \ge 0} \gamma_j x^j \equiv \left( \sum_{j=0}^{n} P_{t,j}^{n}(\bar{\lambda}) x^j \right) \mod. (x^{n+1}).\square$$

**Proof.** Lemma 4.1. is an improvement on the characterizations given by Borodin, Cook in [1] and Hyafil, Van de Wiele in [5] of the set of rational functions computable over $\mathbb{C}$ with $\le t$ operations. Let $\beta$ be a $O$-admissible computation for $p(x) \in C[[x]]$ with $\le t$ operations. Then it is easy to see that $p(x)$ can be computed by the following scheme with $m_{i,j} \in \mathbb{Z}$ and $c_i, d_i \in \mathbb{C}$.
$$
(17) \quad \left\{
\begin{array}{ll}
S_{-1} = x, & \\
\\
S_0 = c_0 + d_0 S_{-1}, & \\
\\
S_i = c_i + d_i \prod_{j=0}^{i-1} S_j^{m_j}, & \text{for } 1 \le i \le t-1, \\
\\
p(x) = S_t = d_t \prod_{j=0}^{t-1} S_j^{m_j}, &
\end{array}
\right.
$$

Since $\beta$ is assumed to be 0-admissible $x$ cannot appear in $\beta$ as a factor of some intermediate result. Furthermore $S_i(0) \neq 0$ for $i \ge 0$. Therefore we can assume that $S_i(0) = 1$ for $0 \le i \le t-1$. This can always be done by computing the functions $\frac{S_i}{S_i(0)}$ instead of $S_i$, for $0 \le i \le t-1$, together with an appropriate change of the parameters $c_i$ and $d_i$. Then

$$
S_i(x) = 1 + \sum_{j \ge 1} a_{i,j} x^j \quad \text{for } i = 0, \dots, t-1 \text{ with } a_{i,j} \in \mathbb{C}.
$$

Put $c_t = 0$ and apply binomial formula.

We obtain for $1 \le i \le t$ :

$$
\begin{align*}
(18) \quad S_i(x) &= c_i + d_i \prod_{k=1}^{i-1} \left(1 + \sum_{l \ge 1} a_{k,l} x^l\right)^{m_{k,l}} \\
&= c_i + d_i \prod_{k=1}^{i-1} \left[ 1 + \sum_{p \ge 1} \left[ \binom{m_{k,l}}{p} \left(\sum_{l \ge 1} a_{k1} x^l\right)^p \right] \right],
\end{align*}
with $\binom{m_{k,l}}{p} = \frac{1}{p!} \left[ m_{k,l} \cdot (m_{k,l-1}) \cdots (m_{k,l-p+1}) \right]$ for all $m_{k,l} \in \mathbb{Z}$.
$$

Therefore

$$
S_i(x) \equiv \left( \sum_{j=0}^{\Sigma} P_{i,j}^n x^j \right) \mod. (x^{n+1}) \text{ for } 0 \le i \le t, \text{ with} \\
P_{i,j}^n \in \mathbb{Z}[c_0, d_0, \bar{m}, \bar{m}_{k,1}, c_1, d_1 \mid 1 \le i \le 0 \le k \le t-1] \text{ and } \bar{m} = (n!)^{-1}.
$$

(17) and (18) yield the following recursion scheme for the $P_{i,j}^n$ :
$$
(19) \quad \left|
\begin{array}{l}
P_{o,o}^n = c_o, P_{o,1}^n = d_o, P_{o,j}^n = 0 \text{ for } j \ge 1, \text{ and for } i = 1, \dots, t \\
\sum_{j=0}^{n} P_{i,j}^{n} x^j \\
\equiv \left[ c_i + d_i \prod_{k=1}^{i-1} \left[ 1 + \sum_{p \ge 1} \left[ \frac{n!}{p!} \bar{m}_k \cdot m_{k,i} (m_{k,i}^{-1}) \dots (m_{k,i}^{-p+1}) \right. \right. \right. \\
\left. \left. \left. \cdot \left( \sum_{l=1}^{n} P_{k,l}^{n} x^l \right) p^l \right] \right] \right] \mod (x^{n+1}).
\end{array}
\right.
$$

By comparison of the coefficients of the $x^j$ we obtain the following
recursion for deg $P_{i,j}^n$ :

$\deg P_{o,j}^n \le 1$ for $j \ge 0$ and for $i = 1, \dots, t$ and $j \ge 0$

$$
(20) \quad \deg P_{i,j}^n = \max \left\{ j + 2 + \sum_{v=1}^{\mu} \deg P_{i_v, j_v}^n \;\middle|\;
\begin{array}{@{}l@{}}
  \sum_{v=1}^{\mu} j_v = j, \\
  \mu \ge 1, j_v \ge 1, \\
  0 \le i_v < i
\end{array}
\right\}
$$

The recursion formula (20) needs a justification. Expand the expression
on the right side of last equality (19). Each term in $x^j$, $j \ge 1$, is some
$p_{i,j} x^j$ such that

$$
P_{i,j} = d_i \sum_{v=1}^{\rho} \left[ \frac{n!}{p_v!} \bar{m}_{i_v} \cdot m_{i_v, i} (m_{i_v, i-1}) \cdots (m_{i_v, i-p_v+1}) \cdot \begin{pmatrix} p_{i_v} \\ \theta_{i_v}^{\pi=1} = 1 \end{pmatrix} P_{i_v, 1}^n \right], \text{ with}
$$

$$
(21) \quad \rho \sum_{v=1}^{\rho} \theta_{v}^{\Sigma=1} 1_{\theta_{v}} = j, \rho, p_{v}, 1_{\theta_{v}} \ge 1 \text{ and } 0 \le i_{v} < i.
$$

Therefore

$$
(22) \quad \deg p_{i,j} = 2 + \sum_{v=1}^{\rho} \left( p_v + \theta_v^{\Sigma=1} \deg P_{i_v,1}^n \right).
$$
Put $\rho_{\sum_i 1} p_v = \mu$. We derive from (21) and (22)

$\deg p_{i,j} \le \max [2 + j + \sum_i \deg p_{i_v,1_v}^n]$, with $\sum_i 1_{i_v} = j$, $\mu$, $1_v \ge 1$
and $0 \le i_v < i$.

To solve induction (20) assume that there is a constant $c > 0$
such that

$$
(23) \quad \deg p_{i_v, 1_v}^n \le c i_v 1_v + 2 \quad \text{for all } i_v, 1_v \text{ with } 0 \le i_v < i \text{ and } 1_v \ge 1.
$$

We derive from (19) that, in the case $i_v = 0$, (23) holds for any
$c \ge 0$.

Then

$$
\begin{align*}
\deg p_{i,j}^n \le 2 + j + \max \sum_{v=1}^{\mu} (c i_v 1_v + 1) \\
\le 2 + 2j + c(i-1)j \\
= j [2 + c(i-1)] + 2 \le c i j + 2,
\end{align*}
$$

provided that $j(2-c) \le 0$ which holds if $c > 2$. Thus $\deg p_{t,j}^n \le 3tj + 2$
and there is $\gamma_2 > 0$ and $t_o \in \mathbb{N}'$ such that $\deg p_{t,j}^n \le \gamma_2 jt$ for all $t \ge t_o$
and $j \ge 1$.

Next we count the number of parameters in the scheme (17). There are
parameters $c_i$ for $0 \le i \le t$, parameters $d_i$ for $0 \le i \le t$, parameters $m_{j,i}$
for $1 \le i \le t$, $0 \le j \le i-1$ and parameter $\bar{m}$. These altogether are
$m(t) = \frac{t^2 + 5t + 4}{2}$ parameters. For $t$ large enough $m(t) \le t^2$. The proof
is completed. $\square$

From Lemma 4.1. we derive Corollary 4.2.
**Corollary 4.2.** There is $\gamma > 0$ such that for all natural numbers $n \ge 2$

$$L_{01}(\pm, n) \ge \gamma n^{1/2}/\log n. \square$$

**Proof.** Theorem 2.3. applies with $\mu = \mu' = 2$ and $\nu = 0$. $\square$

We thus obtain on additive operations the same lower bound as Schnorr's lower bound on the non scalar multiplicative complexity of 0-1 polynomials. This follows from the total symmetry between Lemma 3.1. and Lemma 4.1. In both cases the parameters $\mu, \mu'$ and $\nu$ of Theorem 2.3. take the same values : $\mu = \mu' = 2$ and $\nu = 0$.

In addition one can show in both cases, for $n$ large enough, an upper bound in $2^{n\gamma t^2}$ on the weight of polynomials $p_{t,j}^n$. ($\gamma$ is a positive real constant number). It is easy to see that this complete similarity between both situations implies that, using Strassen's method, one can show on the additive complexity exactly the same lower bounds (asymptotically) as those obtained by Schnorr [11] on the non scalar multiplicative complexity of concrete polynomials with rational and algebraic coefficients. In particular we can show :

$$L(\pm, \sum_{j=0}^{n} \exp(2\pi i/2^j)) x^j = \Omega((n/\log n)^{1/2})$$

and

$$L(\pm, \sum_{j=0}^{n} 2^{2^j} x^j) = \Omega((n/\log n)^{1/2}).$$

## 5. CONCLUSION

We have shown the existence of univariate 0-1 polynomials of degree $n$ with total complexity $(n/\log n)$ and of univariate 0-1 polynomials of
degree $n$ with additive complexity $(n^{1/2}/\log n)$ (in the model with complex preconditionning). It can be shown that the results of Theorem 2.3 and Corollaries 3.4. and 4.2. can be extended to multivariate polynomials, $n$-linear forms and sets of linear forms with 0-1 coefficients, by applying reducibilities to make these problems equivalent to single-variable evaluation, as pointed out in another context by Dobkin, Lipton [3, p 357].

In particular we can show that there are sets of $n$ 0-1 linear forms in $n$ indeterminates that require $\Omega(n^2/\log n)$ total operations over $C$ and this complexity is asymptotically the largest possible. The latter result has been already obtained in [5] using the fact that linear programs are asymptotically optimal for computing sets of linear functions. (See for instance Borodin, Munro [2, p 36]).

### Acknowledgement.

We would like to thank Professor M. Demazure for number of helpful suggestions on an earlier version of this paper.
References

[1] A. Borodin and S. Cook, On the number of additions to compute specific polynomials, Siam J. Comput. 5 (1) (1976) 146-157.

[2] A. Borodin and I. Munro, The Computational Complexity of Algebraic and Numeric Problems (American Elsevier, New-York, 1975).

[3] D. Dobkin and R.J. Lipton, Complexity measures and hierarchies for the evaluation of integers and polynomials, Theoretical Computer Science 3 (3) (1976) 349-357.

[4] L. Hyafil and J.P. Van de Wiele, On the additive complexity of specific polynomials, Information Processing Letters 4(2) (1975) 45-47.

[5] L. Hyafil and J.P. Van de Wiele, Bornes inférieures pour la complexité des polynômes à coefficients 0-1, Rapport de Recherche Laboria N° 192 (October 1976).

[6] R.J. Lipton, Polynomials with 0-1 coefficients that are hard to evaluate, Sixteenth Annual Symposium on Foundations of Computer Science (University of California at Berkeley, October 1975) 6-10.

[7] R.J. Lipton and L.J. Stockmeyer, Evaluation of polynomials with super-preconditionning, Eight Annual ACM Symposium on Theory of Computing (Hershey, Pennsylvania, May 1976) 174-180.

[8] M.S. Paterson and L.J. Stockmeyer, On the number of non scalar multiplications necessary to evaluate polynomials, Siam J. Comput. 2 (1) (1973) 60-66.

[9] R.L. Rivest and J.P. Van de Wiele, An $\Omega((n/\log n)^{1/2})$ lower bound on the number of additions necessary to compute 0-1 polynomials over the ring of integers. To appear.
[10] J.E. Savage, An algorithm for the computation of linear forms, Siam J. Comput. 2 (1) (1974) 150-158.

[11] C.P. Schnorr, Improved lower bounds on the number of multiplications/divisions which are necessary to evaluate polynomials, Proceedings of Sixth Intern. Symp. On Math. Foundations of Computer Science (Tatranská Lomnica, September 1977), Lecture Notes in Computer Science 53 (Springer-Verlag, Berlin, 1977) 135-147. To appear in Theoretical Computer Science.

[12] V. Strassen, Polynomials with rational coefficients that are hard to compute, Siam J. Comput. 3 (2) (1974) 128-149.

[13] J.P. Van de Wiele, Complexité additive et zéros des polynômes à coefficients réels et complexes, Rapport de Recherche Laboria N° 292 (Mars 1978).