RIA
laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
78150 - Le Chesnay
Tél. 954.90.20

laboratoire de recherche
en informatique
et automatique

Sur la complexité
de
certains polynomes

Laurent Jean Paul
L. Hyafil J.P. Van de Wiele

Rapport de Recherche n·100

Février 1975.
SUR LA COMPLEXITÉ DE CERTAINS POLYNOMES

L. Hyafil, J.P. Van de Wiele

Résumé :

Nous étudions dans cet article le nombre d'additions requis pour
l'évaluation de certains polynômes. Nous établissons en particulier
que $\sum_{i=0}^{N} x^i$ ne peut être calculé, sans division, avec un nombre d'additions
indépendant de N.

Abstract :

In this paper we investigate the number of additions required for the
evaluation of specific polynomials. In particular, it is shown that
$\sum_{i=0}^{N} x^i$ cannot be computed, without division, with a number of additions
independent from N.
# 1. Introduction

Borodin [73], remarquant que $\sum_{i=0}^{2^k-1} x^i = \prod_{0 \le j \le k-1} (1+x^j)$, qualifie de "problème délicat" la conjecture suivante :

"Si l'on ne s'autorise pas la division, tout algorithme d'évaluation du polynôme $\sum_{i=0}^{n} x^i$ utilise au moins $\lceil \log n \rceil$ additions ou soustractions".

Cette conjecture s'inscrit dans le cadre général de la recherche d'un argument de croissance pour le nombre d'opérations additives nécessaires pour évaluer un ensemble de polynômes ou de fractions rationnelles.

Les premiers travaux dans cette direction ont été effectués par Ostrowski [54], Motzkin [55], et Belaga [58].

Ils ont été repris et développés par Kirkpatrick [72], Morgenstern [73], Kedem [74], Borodin et Munro [74], Strassen [74]. Un des résultats les plus récents, dû à Borodin et Cook [74], établit que le nombre d'opérations additives nécessaires pour calculer un polynôme de $R[X]$ est borné inférieurement par une fonction du nombre de racines réelles distinctes de ce polynôme.

Nous démontrons ici une forme faible de la conjecture de Borodin à savoir : le nombre minimal d'additions nécessaires pour évaluer $\sum_{i=0}^{n} x^i$ en n'utilisant que des additions et des multiplications (et pas de soustractions) est une fonction qui tend vers $+\infty$ avec n. Nous
démontrons en fait un résultat plus général : toute suite de fonctions de $R_+$ dans $R_+$ qui converge simplement sur un sous-ensemble borné de $R_+$ vers une fonction non bornée n'est pas calculable avec un nombre fini d'additions. ( $\sum_{i=0}^{n} x^i$ converge simplement vers $\frac{1}{1-x}$ sur $[0, 1[$). Ce résultat reste vrai si l'on s'autorise en outre les élévations à la puissance p, p quelconque dans $R_+$.

Ce travail constitue une approche nouvelle pour l'étude de la complexité d'un ensemble de polynômes, complexité que l'on caractérise par des propriétés analytiques.

## 2. Définitions

### Définition 2.1. :

Soit $F$ l'ensemble des fonctions de $R_+$ dans $R_+$ défini de la façon suivante : $F$ contient les constantes de $R_+$ et la fonction identité $x$. De plus si $f_1$ et $f_2$ sont dans $F$ alors : $f_1 + f_2 \in F$, $f_1 \cdot f_2 \in F$ et pour tout $f$ dans $F$, et pour tout $s \in R_+$, $f^s \in F$.

### Définition 2.2. : (cf Winograd ).

Le programme P calcule la fonction $f \in F$ sur $\{x\}$ si P est une séquence d'instructions : $i_1, i_2, \dots, i_t$ telle que :

```
u{x}
    si P est une séquence d'instructions :
        i_1
        i_2
        .
        .
        .
        i_t
```
1) Chaque $i_j$ est de l'une des deux formes suivantes : (on désigne sans confusion possible l'instruction et le résultat de l'instruction par le même nom).

$$ \text{a) } i_j \leftarrow a_j \text{ op } b_j $$

$$ \text{avec : } a_j(\text{resp. } b_j) = \begin{cases} a_j \in R_+ \\ \text{ou} \\ x \\ \text{ou} \\ i_k \quad k<j \end{cases} $$

$$ \text{et op} = \begin{cases} + \\ \text{ou} \\ \cdot \\ \end{cases} $$

$$ \text{b) } i_j \leftarrow (a_j)^s $$

$$ \text{avec : } a_j = \begin{cases} a_j \in R_+ \\ \text{ou} \\ x \\ \text{ou} \\ i_k \quad k<j \end{cases} \quad \text{et : } s \in R_+. $$

2) $i_t$ est identique à $f$.

En d'autres termes les données de P sont $x$ (la variable) et les éléments de $R_+$ ; il n'utilise que des additions, des multiplications et des élévations à la puissance p-ième, $p \in R_+$ ; enfin : $\forall x \in R_+ \ i_t = f(x)$.

**Exemple 1 :**

le programme :

$$ i_1 \leftarrow 1 + x $$

$$ i_2 \leftarrow x \cdot x $$
$$ 
\begin{aligned}
i_3 &+ i_1 \cdot i_2 & & ((1+x)x^2) \\
i_4 &+ i_1 + i_3 & & (1+x+x^2+x^3) \\
i_5 &+ (i_4)^2 & & 
\end{aligned}
$$

calcule $f(x) = \sqrt[3]{\sum_{i=0}^{3} x^i}$ sur $F$ à partir de $R_+ \cup \{x\}$. Ses données sont $1$ et $x$, il n'utilise que les opérations $+$, $\cdot$ et $\sqrt{}$ et : $i_5 \equiv f$.

**Définition 2.3. :**

Soit $k$ un entier positif.

Un programme $P$ est un $k_+$-programme s'il peut se mettre sous la forme canonique suivante :

$$ 
\begin{aligned}
s_0 &\to c_0 x \\
s_1 &\to c_1 x^{\gamma_{0,1}} + d_1 x^{\delta_{0,1}} \\
s_i &\to c_i \prod_{j<i} s_j^{\gamma_{j,i}} + d_i \prod_{j<i} s_j^{\delta_{j,i}} \\
s_k &\to c_k \prod_{j<k} s_j^{\gamma_{j,k}} + d_k \prod_{j<k} s_j^{\delta_{j,k}}
\end{aligned}
$$

avec $c_i, d_i, \gamma_{j,i}, \delta_{j,i} \in \mathbb{R}_+$

$s_i$ est le résultat de la $i$-ème addition et $s_k$ est le résultat de $P$. (Ici les $s_i$ ne sont plus comme dans la définition 2 des instructions élémentaires mais des chaînes d'instructions élémentaires).
Un $k_+$-programme comporte au plus k additions, et il calcule une fonction de F.

**Exemple 2 :**

Le programme :

$$
\begin{array}{l}
s_o \leftarrow x \\
s_1 \leftarrow 1 + \frac{s_o}{n} \quad \text{avec } n \in \mathbb{N} \\
s_2 \leftarrow s_1^n
\end{array}
$$

est un $k_+$-programme. Il calcule la fonction : $f_n(x) = (1+\frac{x}{n})^n$.

**Définition 2.4. :**

Soit $F(k)$ l'ensemble des fonctions de $R_+$ dans $R_+$ calculables par un $k_+$-programme.

$F(k)$ est inclus dans $F$ et il est clair que $k_1 < k_2$ implique
$F(k_1) \subset F(k_2)$.

**Définition 2.5. :**

Soit X un sous-ensemble de R, {$f_n$} une suite de fonctions de X dans R.

Soit $l(x)$ la limite simple de $\{f_n\}$ ; l est une fonction partielle de $x$ dans $\mathbb{R}$ définie par :

$$
l(x) = \lim_{n \to +\infty} f_n(x)
$$

uniquement pour les valeurs de x où cette limite existe et est finie.

On définit alors l'ensemble B(X) de la façon suivante :

la suite {$f_n$} appartient à B(X) si, pour tout borné [a b] n X
de X où [a b] est un intervalle de R+, il existe une constante M ∈ R+
telle que les restrictions à [a b] n X des limites de toutes les sous-
suites de {$f_n$} sont uniformément majorées par M.
Plus précisément : soit $A(f_n,x)$ l'ensemble des points d'accumulation de la suite de réels $\{f_n(x)\}$ pour $x$ donné dans $X$ :

$$ \{f_n\} \in B(X) \iff (1) $$

(1) $\forall a,b \in R$ : $\exists$ $M \ge 0$ tel que :

$\forall x \in X \cap [ab] \text{ avec } A(f_n,x) \neq \emptyset \text{ et } \forall y \in A(f_n,x) :$

$$ y \le M $$

### Exemple 3

Soit $\{f_n\}$ la suite de fonctions définie dans l'exemple 2 : $\{f_n\}$ est dans $B(R_+)$ . En effet $\forall x \in R$ $$ \lim_{n \to +\infty} \left(1 + \frac{x}{n}\right)^n = e^x $$ et $e^x$ est bornée sur tout borné de $R_+$.

### Exemple 4

Soit $g_n$ définie par : $\forall x \in R_+$ $g_n(x) = (-1)^n x^n$. Il est clair que quel que soit $x$ dans $R$, $A(g_n,x)$ contient au plus 0, 1 et -1.

Donc $\{g_n\}$ est dans $B(R)$.

### 3. Sur les fonctions calculables avec un nombre fini d'additions :

Notre principale contribution est le théorème suivant qui établit une propriété caractéristique de la limite d'une suite de fonctions de $F$ calculable avec un nombre fini d'additions.

#### Théorème 3.1. :

Quel que soit l'entier $k$, on peut extraire de toute suite de fonctions de $F(k)$ une sous suite qui appartient à $B(R_+)$.

On en déduit le
**Corollaire 3.2. :**

Quel que soit l'entier k, la limite simple de toute suite de fonctions de F(k) est bornée supérieurement sur tout intervalle borné de R_+.

**Démonstration du corollaire 3.2. :**

Soit $k \in \mathbb{N}$, et soit $\{f_n\}$ une suite de fonctions de $F(k)$. D'après le théorème 3.1. $f_n$ admet une sous suite $\{f_{n,1}\}$ qui appartient à $B(R_+)$. Soit $[a, b]$ un intervalle borné de $R_+$. Soit $D$ le domaine de définition de la limite 1 de $\{f_n\}$, $D'$ le domaine de définition de la limite 1' de $\{f_{n,1}\}$.
Il est clair que :

$$D \subset D' \text{ et } \forall x \in D \ 1(x) = 1'(x).$$

D'autre part, d'après la définition même de $B(R_+)$, 1' est majorée sur $D' \cap [a, b]$ par une constante positive M. Donc 1 est majorée sur $D \cap [a, b]$ par M. ■

On en déduit une formulation faible de la conjecture de Borodin :

**Corollaire 3.3. :**

Pour tout entier k, il existe P ∈ N tel que $\sum_{i=0}^{P} x^i$ n'est pas une fonction de F(k).

**Démonstration :**

Supposons que $\{f_n\} = \{\sum_{i=0}^{n} x^i\}$ soit une suite de fonctions de $F(k)$ pour un certain k dans $\mathbb{N}$. La limite 1 de $\{f_n\}$ est définie sur $[0,1]$ par $1(x) = \frac{1}{1-x}$. Du corollaire 3.2. et du fait que $\lim_{x \to 1^-} 1(x) = +\infty$ résulte la contradiction. ■
### 3.4. Démonstration du théorème 3.1. :

Soit $[a, b] \subset \mathbb{R}_+$, et $\{f_n\}$ une suite de fonctions de F. On désigne par $A(f_n)$ l'ensemble $\cup_{x \in [a, b]} A(f_n, x)$. On veut montrer que pour tout entier positif k, toute suite $\{f_n\}$ de fonctions de F(k) admet une sous suite $\{f_n, \cdot\}$ telle que $A(f_n, \cdot)$ soit borné supérieurement dans $\mathbb{R}_+$. Nous allons le montrer par récurrence. Pour des raisons techniques nous adoptons l'hypothèse d'induction suivante :

**Hypothèse d'induction :**

$\gamma_n$

$H$ : toute suite de fonctions de la forme $\{f_n\}$ avec $f_n$ dans $F(k)$ et $\gamma_n$ dans $\mathbb{R}_+$ admet une sous suite qui appartient à $B(\mathbb{R}_+)$.

1°) **Initialisation** : $k = 0$.

Il faut montrer que la suite $\{f_n\} = \{c_n x\}$ avec $c_n, \gamma_n \in \mathbb{R}_+$, admet une sous suite qui appartient à $B(\mathbb{R}_+)$.

$\{f_n\}$ admet une sous suite notée encore $\{f_n\}$ telle que $\{c_n\}$ et $\{\gamma_n\}$ convergent dans $\mathbb{R}_+$.

$\gamma_n \to \gamma \in \mathbb{R}_+$

Si $\{c_n\} \to +\infty$, $A(f_n)$ est réduit à $A(f_n, 0) = \{0\}$.

Si $\{c_n\} \to c \in \mathbb{R}_+$, $\lim_{n \to +\infty} f_n(x) = cx^\gamma$ et $cx^\gamma$ est borné sur tout borné de $\mathbb{R}_+$.

$\{\gamma_n\} \to +\infty$

Soit $x_1$ dans $[a, b]$, $x_1 > a$ tel que $A(f_n, x_1) - \{0\} \neq \emptyset$. Nous pouvons extraire de $f_n$ une sous suite $\{f_n, \cdot\}$ telle que : $f_n(x_1) \to y_1 > 0$.

S'il existe un point $x_2$ dans $[ab]$, $x_2 > 0$, $x_2 \neq x_1$ tel que $A(f_n, x_2) - \{0\} \neq \emptyset$ ont peut extraire de $\{f_n, \cdot\}$ une sous suite $\{f_n''\}$
telle que : $f_n''(x_2) \to y_2 > 0$ mais de : $\frac{y_2}{y_1} = \lim_{n'' \to +\infty} \left(\frac{x_2}{x_1}\right)^{\gamma_n} > 0$ résulte :
$x_2 = x_1$, puisque $\gamma_n \to +\infty$.

Donc : $A(f_n') = \{0\} \cup A(f_n', x_1) = \{0, y_1\}$ et $\{f_n'\}$ appartient à $B(R_+)$.

Ce qui établit H pour $k = 0$.

2°) Supposons que H est vrai pour tout $j < k$.

Nous allons montrer que H est vrai pour $j = k \ge 1$. Nous démontrons d'abord un lemme.

**Lemme 3.4.1. :**

Soit $\{f_n\}$une suite de fonctions de $F(k)$, $k \ge 1$. Alors pour tout $n$ dans $N$, $f_n$ est de la forme : $g_n^{\delta_n + \epsilon_n}$ avec : $g_n, h_n \in F(k-1)$, $\delta_n, \epsilon_n \in R_+$.

**Démonstration :**

Par définition (cf Def. 2.3.), pour tout $n$, $f_n$ est de la forme :

$$s_k = c_k \prod_{j<k} s_j^{\gamma_{j,k}} + d_k \prod_{j<k} s_j^{\delta_{j,k}} = t_k + u_k$$

$$t_k = c_k \cdot \left[ \left( \prod_{j<k-1} s_j^{\frac{\gamma_{j,k-1}}{\gamma_{k-1,k}}} \right) \cdot s_{k-1} \right]^{\frac{\gamma_{k-1,k}}{\gamma_{k-1,k}}}$$

$$s_{k-1} \text{ est égal à :} = c_{k-1} \prod_{j<k-1} s_j^{\gamma_{j,k-1}} + d_{k-1} \prod_{j<k-1} s_j^{\delta_{j,k-1}}$$

Donc :

$$(t_k)^{\frac{1}{\gamma_{k-1,k}}} = c_k^{\frac{1}{\gamma_{k-1,k}}} \cdot c_{k-1}^{\frac{1}{\gamma_{k-1,k}}} \cdot \left[ (s_j)^{\frac{\gamma_{j,k}}{\gamma_{k-1,k}}} + \gamma_{j,k-1} \right] \\ + c_k^{\frac{1}{\gamma_{k-1,k}}} \cdot d_{k-1}^{\frac{1}{\gamma_{k-1,k}}} \cdot \left[ (s_j)^{\frac{\gamma_{j,k}}{\gamma_{k-1,k}}} + \delta_{j,k-1} \right]$$
$$ \Rightarrow (t_k)^{\frac{1}{\gamma_{k-1}, k}} = s'_{k-1} \Rightarrow t_k = (s'_{k-1})^{\gamma_{k-1}, k} $$

et $s'_{k-1}$ appartient à $F(k-1)$

Ce qui montre le lemme 3.4.1. ■

Il nous faut donc montrer maintenant que, quels que soient $g_n, h_n$ dans $F(k-1)$ et $\gamma_n, \delta_n, \epsilon_n$ dans $R_+$, la suite $\{f_n\} = \{(g_n^{\delta_n} + h_n^{\epsilon_n})^{\gamma_n}\}$ admet une sous suite dans $B(R_+)$.

Nous pouvons toujours supposer que les suites $\{\delta_n\}, \{\gamma_n\}$ et $\{\epsilon_n\}$ convergent dans $\bar{R}_+$.

a) $\gamma_n \to 0$

Alors il est clair qu'à partir d'un certain rang et pour tout $x$ dans $[a, b]$ on aura :

$$ 0 \le \text{Sup}[g_n^{\delta_n \gamma_n}(x), h_n^{\epsilon_n \gamma_n}(x)] \le f(x) \le g_n^{\delta_n \gamma_n}(x) + h_n^{\epsilon_n \gamma_n}(x) $$

Par conséquent tout y de $A(f_n)$ sera inférieur ou égal à la somme d'un $y_1$ de $A(g_n^{\delta_n \gamma_n})$ et d'un $y_2$ de $A(h_n^{\epsilon_n \gamma_n})$. Or d'après l'hypothèse d'induction $\{g_n^{\delta_n \gamma_n}\}$ et $\{h_n^{\epsilon_n \gamma_n}\}$ admettent des sous suites dans $B(R_+)$.

b) $\gamma_n \to \gamma \in \mathbb{R}_+$

Alors pour tout $x$ de $[a, b]$ tel que : $f_n^{\frac{1}{\gamma}}(x) \to y \in R_+$, on a :

$$ \lim_{n \to +\infty} f_n^{\frac{1}{\gamma}(x)} = \lim_{n \to +\infty} (g_n^{\delta_n} + h_n^{\epsilon_n}) (x) $$
Comme $g_n^{\delta_n}$ et $h_n^{\epsilon_n}$ sont des fonctions positives il s'ensuit que tout y
de $A(f_n^{1/\gamma_n})$ est de la forme :

$$
\begin{align*}
y &= y_1 + y_2 \quad \text{avec :} \quad y_1 \in A(g_n^{\delta_n}) \\
y_2 &\in A(h_n^{\epsilon_n})
\end{align*}
$$

et l'hypothèse d'induction nous permet de conclure.

c) $\gamma_n \to +\infty$.

Soit x dans [a b]et supposons : A(f_n,x) -{o} ≠ Ø. On peut extraire
de {f_n} une sous suite {f_n'} telle que : f_n'(x) → y > o.

Comme $\gamma_n'$ converge vers $+\infty$ dans $\overline{R_+}$, la suite
$\{z_n'\} = \{g_n' \delta_n' + h_n' \epsilon_n' (x)\}$ converge vers 1. En effet, soit z un point
d'accumulation de $\{z_n'\}$.

$z < 1 \Rightarrow y = 0$

$$
z > 1 \Rightarrow \{f_n'(x)\} = \{z_n', \gamma_{n'}\} \text{ diverge}
$$

Donc :

$$
y = \lim_{n' \to +\infty} f_n'(x) = \lim_{n \to +\infty} e^{\gamma_n' (g_n^{\delta_n'}(x) + h_n^{\epsilon_n'}(x) - 1)}
$$

Il nous suffit donc de montrer que la suite initiale
$\{\gamma_n(g_n^{\delta_n} + h_n^{\epsilon_n} - 1)\}$ admet une sous suite dans $B(\mathbb{R}_+)$.
Pour cela démontrons la

**Proposition 3.4.2. :**

Toute suite de fonctions de $R_+$ dans $R$ de la forme :
$$r_n = \gamma_n'(g_n^{\delta_n} + h_n^{\epsilon_n} - 1) \text{ avec } g_n, h_n \in F(k-1), \gamma_n, \delta_n, \epsilon_n \in R_+ \text{ et telle que}$$
$$\gamma_n \to +\infty, \text{ admet une sous suite dans } B(\mathbb{R}_+).$$
Pour cela démontrons d'abord le

**Lemme 3.4.3. :**

Toute suite de fonctions de $R_+$ dans $R$ de la forme :

$s_n = \lambda_n (t_n^{\mu_n} - 1)$ avec $t_n \in F(k-1)$, $\lambda_n, \mu_n \in R_+$ et telle que : $\lambda_n \to +\infty$,

admet une sous suite dans $B(R_+)$.

**Démonstration du lemme 3.4.3. :**

Soit : $x \in [a, b]$, $y \in A(s_n, x)$. On peut extraire de {$s_n$} une sous suite {$s_n'$} telle que : $s_n'(x) \to y$. Comme $\lambda_n' \to +\infty$, $t_n' \mu_n' \to 1$.

$$
\begin{align*}
\Rightarrow y &= \lim_{n' \to +\infty} s_n'(x) = \lim_{n \to +\infty} \lambda_n'(e^{\mu_n'} \log t_n'(x)) \\
&= \lim_{n \to +\infty} \lambda_n' \mu_n' \log t_n'(x) \\
\Rightarrow e^y &= \lim_{n \to +\infty} e^{s_n'(x)} = \lim_{n \to +\infty} [t_n'(x)]^{\lambda_n' \mu_n'}
\end{align*}
$$

On est donc ramené à démontrer que {$t_n^{\lambda_n \mu_n}$} admet une sous suite dans $B(R_+)$, ce qui résulte de l'hypothèse d'induction, puisque :

$t_n \in F(k-1)$.

Fin de la démonstration du lemme 3.4.3.

Nous pouvons maintenant reprendre la

**Démonstration de la proposition 3.4.2.**

Soit $x_1$ dans $[a, b]$ tel que : $A(r_n, x_1) \neq \emptyset$.

On suppose en outre :

$$
\forall n \in \mathbb{N} \ g_n^{\delta_n}(x_1) \neq 0 \quad \text{et} \quad h_n^{\epsilon_n}(x_1) \neq 0.
$$
[On peut toujours se ramener à ce cas, éventuellement par extraction de sous-suite, sauf dans le cas où, pour tout $x_l$ dans $[a, b]$, l'une des sous-suites $\{g_n^\delta_n(x_l)\}$ ou $\{h_n^\epsilon_n(x_l)\}$ est identiquement nulle à partir d'un certain rang. Mais, dans cette hypothèse, le fait que $\gamma_n$ converge vers $+\infty$ implique que l'autre est la suite constante 1 et $A(r_n)$ est réduit à $\{0\}$].

On peut extraire de $\{r_n\}$ une sous-suite $\{r_n\}$ telle que :

$$ \lim_{n \to +\infty} r_n(x_l) = y_l \in A(r_n, x_l). $$

Soit $u_n$ la fonction de $R_+$ dans $R$ définie par :

$$ u_n(x) = r_n(x) - r_n(x_l). $$

Nous allons montrer que $\{u_n\}$ admet une sous-suite dans $B(R_+)$ ce qui établira la proposition 3.4.2.

On a :

$$ (2) \quad u_n(x) = \gamma_n (g_n^{\delta_n}(x) - g_n^{\delta_n}(x_l)) + \gamma_n (h_n^{\epsilon_n}(x) - h_n^{\epsilon_n}(x_l)) $$

(2) se réécrit d'après les hypothèses :

$$ \begin{aligned} u_n(x) &= \gamma_n g_n^{\delta_n}(x_l) \left[ \left( \frac{g_n(x)}{g_n(x_l)} \right)^{\delta_n} - 1 \right] + \gamma_n h_n^{\epsilon_n}(x_l) \left[ \left( \frac{h_n(x)}{h_n(x_l)} \right)^{\epsilon_n} - 1 \right] \\ &= s_{1n}(x) + s_{2n}(x) \end{aligned} $$

$s_{1n}$ et $s_{2n}$ sont des fonctions croissantes, négatives ou nulles pour :
$a \le x \le x_l$ et strictement positives pour : $x_l < x \le b$. Donc tout y de $A(u_n)$ est de la forme : $y = y_l + y_2$ avec : $y_l \in A(s_{1n})$ et $y_2 \in A(s_{2n})$.

Mais $s_{1n}$ (resp. $s_{2n}$) est de la forme :

$$ \lambda_{1n} (t_{1n}^{\mu} - 1) \quad (\text{resp.} \quad \lambda_{2n} (t_{2n}^{\mu} - 1)) $$
$$ \text{avec : } \lambda_{1n} = \gamma_n g_n^{\delta_n}(x_1) \quad \lambda_{2n} = \gamma_n h_n^{\epsilon_n}(x_1) $$

$$ \mu_{1n} = \delta_n $$

$$ \mu_{2n} = \epsilon_n $$

$$ t_{1n} = \frac{g_n}{g_n(x_1)} $$

$$ t_{2n} = \frac{h_n}{h_n(x_1)} $$

et $t_{1n}$ et $t_{2n}$ sont dans $F(k^\times)$ ; ce qui, d'après le lemme 3.4.3., termine la démonstration de la proposition 3.4.2. et du théorème 3.1. ■

### 4. Conclusion.

Nous conjecturons un théorème analogue au théorème 3.1. (et par conséquent un corollaire analogue au corollaire 3.3.) lorsqu'on s'autorise la soustraction.

Un tel théorème devra cependant exclure des primitives de base l'élévation à des puissances inférieures à 1.

Notons en effet que la suite de fonctions : $f_n(x) = n(1-x/n)$ converge simplement sur $\mathbb{R}_+$ vers la fonction $-\log x$ qui n'est pas bornée supérieurement sur $]0,1[$.

### 5. Remerciements :

Nous remercions F. Prusker pour son aide au cours de ce travail.
6. Bibliographie :

BELAGA, E.C. [58] : "Some problems in the computation of polynomials".
Dokl. Akad. Nauk. SSSR, 123 775-777.

BORODIN, A.B. [73] : "On the number of arithmetics required to compute certain functions" --circa May 1973. In TRAUB, J.F. "Complexity of sequential and parallel numerical algorithms", Academic Press.

BORODIN, A.B., et COOK, S.A. [74] : "On the number of additions to compute specific polynomials" Proc. 6th Annual ACM Symposium on theory of computing.

BORODIN, A.B., et MUNRO, I. [75] : "Computational complexity of algebraic and numeric problems". American Elsevier. A paraître en Janvier 1975.

KEDEM, Z.M. [74] : "The reduction method for establishing lower bounds on the number of additions" Project MAC. Massachusetts Institute of Technology.

KIRKPATRICK, D. [72] : "On the additions necessary to compute certain functions". Proc. 4th Annual ACM Symposium on Theory of Computing, 94-101.

MORGENSTERN, J. [73] : "Note on a lower bound of the linear complexity of the Fast Fourier Transform". J. ACM 20 : 2, 305-306

MOTZKIN, T.S. [55] : "Evaluation of polynomials and evaluation of rational functions", Bull. Amer. Math. Soc. 61, 163.
OSTROWSKI, A.M. [54] : "On two problems in abstract algebra connected with Horner's rule". Studies presented to R. von Mises, Academic Press, New-York, 40-48.

STRASSEN, V. [74] : "Schwer berechenbare polynome mit rationalen koeffizienten". Siam J. Computing.
ON THE ADDITIVE COMPLEXITY OF SPECIFIC POLYNOMIALS

**Abstract :**

In this paper we investigate the number of additions required for the
evaluation of specific polynomials. In particular, it is shown that,
without division, $\sum_{i=0}^{N} x^i$ cannot be computed with a number of additions
independent from N.

1. Introduction.

Noticing that $\sum_{i=0}^{2^k-1} x^i = \pi \sum_{0 \le j \le k-1} (1+x^j)$, Borodin [1] calls the
following conjecture an "annoying problem" :

If division is not allowed the computation of $\sum_{i=0}^{n} x^i$ requires $O(\log n)$
additive operations.

This conjecture is related to the general problem of finding a growth
argument on the number of additive operations necessary. Most of the
interesting work along that line is described in Borodin-Munro [2].

In this paper we prove the following weaker from of Borodin's
conjecture :

If you only allow multiplication, addition and positive coefficients
(no subtraction) the number of additions required to compute $\sum_{i=0}^{n} x^i$ is
an unbounded function of n.
This result appears in fact as a corollary of our main theorem which states that any sequence of functions from $R^+$ to $R^+$ which simply converges on a bounded subset of $R^+$ towards an unbounded function is not computable, in our model, with a finite number of additions.

Although limited by a restricted model of computation, this work can also be viewed as a tentative form of analytic approach to problems of algebraic complexity.

## 2. Statement of the results.

We first give some definitions :

**Definition 1 :** We say that a polynomial $f(x)$ belongs to $F(k)$ if we can find $c_i, d_i, \gamma_{j,i}, \delta_{j,i}$ in $R^+$ for $1 \le i \le k$ and $1 \le j \le k$ such that for all $x$ in $R^+$:

$$s_o = c_o x$$

$$s_1 = c_1 s_o^{\gamma_{o,1}} + d_1 s_o^{\delta_{o,1}}$$

$$s_i = c_i \prod_{j<i} s_j^{\gamma_{j,i}} + d_i \prod_{j<i} s_j^{\delta_{j,i}}$$

$$f(x) = s_k = c_k \prod_{j<k} s_j^{\gamma_{j,k}} + d_k \prod_{j<k} s_j^{\delta_{j,k}}$$

clearly, a polynomial belongs to $F(k)$ if it can be computed over $R^+$ with $k$ additions and without division and subtraction.

**Definition 2 :**

Let $\{f_n\}$ be a sequence of functions from $X \subset R$ to $R$; we say that $\{f_n\}$ belongs to $B(X)$ if the partial limits of all subsequences of $\{f_n\}$ are bounded on every bounded subset of $X$.
The partial limit of a sequence is the partial function defined by
$f(x) = \lim_{n \to +\infty} f_n(x)$ for all values $x$ such that this limit exists and is
finite.

The main contribution of this paper is the following theorem which
characterizes the sequences of functions of F(k) :

Theorem :

For all k, every sequence of functions of F(k) has a subsequence in B(R<sup>+</sup>).

From the theorem it is possible to deduce the following weak form of
Borodin's conjecture :

Corollary :

For all $k$ there exists $n \ge 0$ such that $\sum_{i=0}^{n} X_i$ is not in $F(k)$.

The proof follows immediately from the fact that $\frac{1}{1-x}$ is not bounded on $[0,1]$.

Proof of the theorem :

In order to prove the theorem we prove by induction on k the following
hypothesis.

H : the sequence ${f_n}^{\gamma_n}$ with $f_n$ in $F(k)$ and $\gamma_n \in R^+$ has a subsequence in $B(R^+)$.

1- **Initialisation** : $k = 0$.

We want to extract a subsequence of ${c_n} \times {}^{\gamma_n}$ ($c_n, \gamma_n \in R^+$) which is in $B(R^+)$. Let ${f_n}$ denote a subsequence of ${c_n} \times {}^{\gamma_n}$ such that ${c_n}$ and ${\gamma_n}$ converge in $\overline{R^+}$.

a) ${\gamma_n} \to \gamma \in R^+$ : the proof is immediate.
b) $\{\gamma_n\} \to +\infty$

The only non trivial case is when there exists $x_1 > 0$ and $x_2 > 0$, $x_1 \neq x_2$ such that a subsequence $\{f_n\}$ of $\{f_n\}$ satisfies :

$$ \lim_{n \to +\infty} f_n(x_1) = y_1 > 0 \text{ and } \lim_{n \to +\infty} f_n(x_2) = y_2 > 0. $$

But $\frac{y_2}{y_1} = \lim_{n \to +\infty} \left(\frac{x_2}{x_1}\right)^{\gamma_n} > 0$ hence a contradiction if $x_1 \neq x_2$.

## 2. Inductive step: Assume $H$ is true for $j<k$.

First of all we give the following lemma whose proof is omitted :

**Lemma 1:** For $k \ge 1$ every polynomial $f_n$ of $F(k)$ satisfies :

$$ f_n = g_n^{\delta_n} + h_n^{\epsilon_n} \text{ with } g_n, h_n \in F(k-1) \text{ and } \delta_n, \epsilon_n \in R^+. $$

By lemma 1, all we need to prove is that $\{f_n^{\gamma_n}\} = \{(g_n^{\delta_n} + h_n^{\epsilon_n})^{\gamma_n}\}$ with $g_n, h_n \in F(k-1)$ and $\epsilon_n, \delta_n, \gamma_n \in R^+$ has a subsequence in $B(R^+)$.

Furthermore, we can assume without loss of generality that $\{\delta_n\}, \{\epsilon_n\}, \{\gamma_n\}$, converge in $\overline{R}^+$.

$$ a) \{\gamma_n\} \to 0 $$

For $n$ large enough we have since $g_n$ and $h_n$ are positive :

$$ 0 \le \sup[g_n^{\delta_n \gamma_n}(x), h_n^{\epsilon_n \gamma_n}(x)] \le f_n(x) \le g_n(x)^{\delta_n \gamma_n} + h_n(x)^{\epsilon_n \gamma_n} $$

and since $g_n$ and $h_n$ are in $F(k-1)$ the results follows from the induction hypothesis.

$$ b) \{\gamma_n\} \to \gamma \in R^+ $$

We have $\lim_{n \to +\infty} [f_n(x)]^{1/\gamma} = \lim_{n \to +\infty} [g_n(x)^{\delta_n} + h_n(x)^{\epsilon_n}]$ and since $g_n$ and $h_n$ are positive the result follows from the induction hypothesis.
c) $\{\gamma_n\} \to +\infty$.

Assume $\lim_{n \to +\infty} f_n(x) = 1$ then
$$ \lim_{n \to +\infty} [f_n(x)]^{\gamma_n} = \lim_{n \to +\infty} e^{\gamma_n [f_n(x)-1]} $$

This is why we first prove :

**Lemma 2** : For $k \ge 1$ the sequence of polynomials $s_n$ defined by
$s_n = \lambda_n (t_n^{\mu_n} - 1)$ with $t_n \in F(k-1)$, $\lambda_n, \mu_n \in R^+$ and $\lim_{n \to +\infty} \lambda_n = +\infty$ has a
subsequence in $B(R^+)$.

**Proof :**

Assume $x$ and $\{s_n\}$ subsequence of $\{s_n\}$ are such that $\lim_{n \to +\infty} s_n(x) = y$.
Since $\lambda_n \to +\infty$ we have

$[t_n(x)]^{\mu_n} \to 1$ and $y = \lim_{n \to +\infty} \lambda_n (e^{\mu_n \log[t_n(x)]} - 1)$ is equal to

$\lim_{n \to +\infty} \lambda_n \mu_n \log[t_n(x)]$. The result follows then from the fact that
$t_n^{\lambda_n \mu_n}$ has a subsequence in $B(R^+)$ since $t_n \in F(k-1)$. $\blacksquare$

We can now prove :

**Lemma 3** : For $k \ge 1$ the sequence of polynomials $s_n$ defined by
$s_n = \gamma_n (g_n^\delta + h_n^\epsilon - 1)$ with $g_n, h_n \in (k-1)$ and $\gamma_n, \delta_n, \epsilon_n \in R^+$ such
that $\gamma_n \to +\infty$ has a subsequence in $B(R^+)$.

**Proof** : Assume we can find $x_l$ such that there exists a subsequence $\{s_n\}$ of $\{s_n\}$ which satisfies :
$$ \psi_n \qquad g_n^\delta(x_l) \neq 0 \text{ and } h_n^\epsilon(x_l) \neq 0 \text{ and } \lim_{n \to +\infty} s_n(x_l) = y_l. $$

Define $u_n$ by $u_n(x) = r_n(x) - r_n(x_1)$. We establish the lemma by proving that $u_n$ has a subsequence in $B(R^+)$.
we have :

$$
\begin{align*}
u_n(x) &= \gamma_n g_n \delta^{\delta} n(x_1) \left[ \left( \frac{g_n(x)}{g_n(x_1)} \right)^{\delta} n - 1 \right] + \gamma_n h_n \epsilon^{\epsilon} n(x_1) \left[ \left( \frac{h_n(x)}{h_n(x_1)} \right)^{\epsilon} n - 1 \right] \\
&= s_{1n}(x) + s_{2n}(x).
\end{align*}
$$

We first notice that $s_{1n}$ and $s_{2n}$ have the same sign. So the result is obtained by application of Lemma 2 to $s_{1n}$ and $s_{2n}$. ■

$$
\text{When } \lim_{n \to +\infty} f_n(x) \neq 1, \text{ since } \gamma_n \to +\infty, \lim_{n \to +\infty} [f_n(x)]_{n=1}^{\gamma_n} = \begin{cases} 0 \\ +\infty \end{cases}
$$

so lemma 3 completes the proof of the theorem. ■

3. Summary

We have characterized functions which can be computed with a finite
number of additions, using a restricted model of computation. We
conjecture that our result can be extended to a model in which substrac-
tion and negative numbers are allowed. However in such a model the
exponentiation should be limited to numbers greater than $\epsilon > 0$ since
$f_n(x) = n(1-x^{1/n})$ has no subsequence in $B(R^+)$.

4. Acknowledgments :

The authors would like to thank F. Prusker for helpful discussions and
C.W. Rackoff for his comments.

5. References :

[1] Borodin, A.B. : "On the number of arithmetics required to compute certain functions", In "Complexity of sequential and parallel numerical algorithms". Academic Press, 1973.

[2] Borodin, A.B and Munro, I. : "Computational complexity of algebraic and numeric problems". American Elsevier, 1975.