# Complexité additive et zéros des polynômes à coefficients réels et complexes

Jean-Paul van de Wiele

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

## To cite this version:

Jean-Paul van de Wiele. Complexité additive et zéros des polynômes à coefficients réels et complexes. [Rapport de recherche] IRIA-RR-292, IRIA. 1978, pp.17. hal-04716559

HAL Id: hal-04716559

https://inria.hal.science/hal-04716559v1

Submitted on 1 Oct 2024

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
RIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 105 78150 - Le Chesnay
France
Tél.: 954 90 20

laboratoire de recherche
en informatique
et automatique

ARCHIVES

COMPLEXITÉ ADDITIVE
ET ZÉROS DES POLYNÔMES
À COEFFICIENTS
RÉELS ET COMPLEXES

Jean-Paul Van de WIELE

Rapport de Recherche N° 292

Avril 1978

17p
COMPLEXITÉ ADDITIVE ET ZÉROS DES POLYNÔMES
A COEFFICIENTS RÉELS ET COMPLEXES

Jean-Paul Van de Wiele

Résumé :

A. Borodin et S. Cook ont montré l'existence d'une relation entre le nombre de zéros réels distincts d'un polynôme de $R[x]$ et le nombre minimum d'additions-soutractions nécessaires à son calcul sur $R$. A partir de ce résultat on peut espérer obtenir des bornes inférieures intéressantes pour la complexité additive sur $R$ de certaines familles de polynômes ou fractions rationnelles réelles en plusieurs indéterminées. Nous montrons d'abord que pour tout entier $k$ la classe des polynômes de $R[x]$ calculables sur $R$ avec $k$ opérations additives contient le polynôme de Chebyshev de degré $3^k$ qui a $3^k$ zéros réels distincts. Dans l'espoir d'obtenir des bornes inférieures non seulement sur $R$ mais aussi sur $C$, nous considérons ensuite le problème suivant : existe-t-il une relation entre les zéros complexes d'un polynôme de $C[x]$ et sa complexité additive sur $C$ ? Borodin et Cook en suggèrent une dont nous montrons ici qu'elle n'est pas vérifiée. La démonstration met en évidence un certain nombre de propriétés des zéros des polynômes de $R[x]$ et de $C[x]$ calculables avec 3 additions-soutractions. En particulier nous montrons que contrairement à ce qui se passe sur $R$ on peut calculer sur $C$ avec 3 additions-soutractions des polynômes de $R[x]$ ayant un nombre de zéros réels distincts arbitrairement grand.

Abstract :

A. Borodin and S. Cook have shown that the number of distinct real zeros possessed by a given polynomial in $R[x]$ is related to its additive complexity. Starting from this result one can hope to get interesting lower bounds for the additive complexity over $R$ of certain subsets of real rational functions in several indeterminates. We first show that for all integers $k$ the Chebyshev polynomial of degree $3^k$, which has $3^k$ distinct real zeros, is in the class of polynomials in $R[x]$ computable over $R$ within $k \pm$ operations. In order to get lower bounds not only over $R$ but also over $C$ we then study the following problem : can we show a relationship between the complex zeros of a polynomial in $C[x]$ and its additive complexity over $C$ ? Borodin and Cook suggest such a relationship but we show in this paper that this relationship does not hold. The proof establishes certain properties of the zeros of polynomials in $R[x]$ and $C[x]$ which are computable within 3 additive operations. In particular we show the following which does not hold for the computations over $R$. For all integers $n$ there are some real coefficient polynomials in one indeterminate having $n$ distinct real zeros which are computable over $C$ within $3 \pm$ operations.
# I. INTRODUCTION

Soit $N$ l'ensemble des entiers naturels, $Z$ l'ensemble des entiers relatifs, $R$ l'ensemble des nombres réels, $C$ l'ensemble des nombres complexes. Si $K$ est un corps on note $K(x)$ l'ensemble des fractions rationnelles en une indéterminée sur $K$ et $K(x_1, ..., x_n)$ l'ensemble des fractions rationnelles en $n$ indéterminées sur $K$. A. Borodin et S. Cook [1] ont montré l'existence d'une relation entre le nombre de zéros et pôles réels distincts d'une famille finie de fractions rationnelles de $R(x)$ et la complexité additive sur $R$ de cette famille. Précisement soit $F \subset R(x)$ une famille finie de fractions rationnelles de $R(x)$. La complexité additive $L_+^R(F)$ de $F$ sur $R$ est le nombre minimum d'additions-soutractions nécessaires pour calculer les fonctions de $F$ à partir des fonctions constantes réelles et de la fonction identité $x$ en utilisant les quatre opérations arithmétiques : l'addition, la soustraction, la multiplication et la division. Soit $Z(F)$ l'ensemble des zéros et pôles réels distincts de $F$, c'est-à-dire :

$$Z(F) = \{x \in R \text{ tels que } \exists f \in F \text{ tel que ou bien } f(x) = 0 \text{ ou bien } \frac{1}{f(x)} = 0\},$$

et soit $\# F$ le nombre d'éléments de $Z(F)$. Borodin et Cook ont montré qu'il existe une constante positive $c$ telle que, quel que soit $F \subset R(x)$, $F$ fini,

$$c L_+^R(F) \le 1 \quad (1) \qquad \# F \le 2$$
où l'expression à droite du signe d'inégalité a $(L_+^R(F) - 1)$ niveaux d'exponentielle, au sens où $2^{cL_+^R(F)}$ a un niveau d'exponentielle. La majoration (1) est indépendante du nombre de multiplications-divisions nécessaires au calcul de F.

Ce résultat est suceptible de conduire à une méthode constructive pour obtenir des bornes inférieures de la complexité additive de certaines familles de fractions rationnelles réelles en plusieurs variables. L'objectif poursuivi est d'établir pour la complexité additive des bornes inférieures analogues à celles que Strassen [2] a obtenues pour la complexité multiplicative des fonctions symétriques et d'un certain nombre d'autres fonctions. Borodin et Cook suggèrent, dans la conclusion de leur article, un certain nombre de directions de recherche pour progresser dans cette voie.

a) Améliorer la majoration (1) qui n'est certainement pas la meilleure possible.

b) Trouver une fonction $\phi$ de $U \{R(x_1, \dots, x_n)\}$ dans $N$ qui à une fonction $f$ de $R(x_1, \dots, x_n)$ associe un entier positif $\phi(f)$ qui ait les propriétés suivantes :

b.1) Quel que soit $f \in R(x_1)$, $\phi(f)$ est le nombre de zéros et pôles réels distincts de $f$.

b.2) Soit $R(n,k)$ l'ensemble des fonctions de $R(x_1, \dots, x_n)$ calculables avec $\le k$ additions-soutractions sur $R$, c'est-à-dire à partir de $R \cup \{x_1\} \cup \dots \cup \{x_n\}$. Alors, quel que soit $n$ et quel que soit $k$, $\phi$ est bornée supérieurement sur $R(n,k)$.

Ceci revient à trouver une fonction qui généralise aux fractions rationnelles réelles en plusieurs indéterminées le concept de nombre de zéros et pôles réels distincts pour les fractions rationnelles réelles en une indéterminée et qui reste bornée lorsque la complexité additive sur $R$ reste bornée.
c) Afin d'obtenir des bornes inférieures sur C et non plus
seulement sur R, définir sur C(x) une fonction à valeurs
dans les entiers positifs qui soit liée aux zéros et pôles
complexes ou plus généralement à des propriétés géométriques
et qui reste bornée lorsque la complexité additive *sur C* reste
bornée.

Nous étudions dans cet article les points a) et c). Après avoir
défini le modèle de calcul dans la section 2, nous montrons dans la
section 3 que le polynôme de Chebyshev $T_n$ de degré $3^n$ est calculable
sur $\mathbb{R}$ avec $n$ additions-soutractions, ce qui montre, en reprenant les
notations ci-dessus, qu'il existe une famille $\{f_n\}$ de fonctions de $C(x)$
telle que $\lim_{n \to +\infty} L_+^R(f_n) = +\infty$ et telle que quel que soit $n \in \mathbb{N} \# f_n \ge 3$
$T_3^n$ zéros réels distincts. Borodin
 Ceci puisque, quel que soit $n$, $T_3^n$ a 3$^n$ zéros réels distincts. Borodin
et Cook ont montré ce résultat en construisant d'autres familles ayant les
mêmes propriétés que $\{f_n\}$. Il est intéressant de noter que l'on n'a
encore trouvé, à notre connaissance, aucun polynôme de $\mathbb{R}[x]$ calculable sur
$\mathbb{R}$ avec $n$ additions-soutractions et ayant plus de $3^n$ zéros réels distincts.

Dans la section 4 nous étudions le problème de la généralisation du résultat de Borodin et Cook à la complexité additive *sur C* des fonctions de C(x). Borodin et Cook suggèrent de considérer la fonction qui à un polynôme p de C[x] associe l'entier

$$
\delta_o(p) = \min \{ \text{degr } \underline{\text{tel que}} r \in \mathbb{R}[x,y], r \neq 0 \text{ et } z = x + yi \text{ est un zéro de p implique } r(x,y) = 0 \}.
$$

Nous montrons, et c'est le résultat essentiel de cet article, que
$\delta_o(p)$ n'est pas bornée supérieurement sur la classe $C(k)$ des fonctions
de $C(x)$ calculables avec $k$ ou moins additions-soutractions sur $C$, pour
tout $k \ge 3$ ; elle n'a donc pas la propriété désirée. Nous montrons du
même coup un certain nombre de propriétés intéressantes des fonctions de R(3) et de C(3). En particulier nous montrons l'existence dans C(3) de polynômes de R[x] ayant un nombre arbitrairement grand de zéros réels distincts. Nous établissons également l'existence dans R(3), pour tout n ∈ N, de polynômes ayant au moins n² zéros complexes, distincts deux à deux, et répartis sur n droites du plan complexe, chaque droite contenant n zéros distincts.

## II. DEFINITIONS

### 2.1) Calculs

Soit K un corps, $K(x_1, ..., x_n)$ le corps des fractions rationnelles sur K en n indéterminées. Soit F un sous-ensemble fini de $K(x_1, ..., x_n)$. Un calcul de F sur $K(x_1, ..., x_n)$ mod. $K \cup \{x_1\} \cup \{x_2\} ... \cup \{x_n\}$ (en abrégé calcul de F sur K) est une suite de fonctions de $K(x_1, ..., x_n)$, $s = \{f_1, ..., f_1\}$ telle que tout $f$ de F est un $f_i$, $1 \le i \le 1$, et qui se construit de la façon suivante :

$$f_1 = x_1, f_2 = x_2, ..., f_n = x_n \text{ et pour tout } i \ge n+1$$

$$f_i = \alpha_i \in K \text{ ou bien } f_i = f_j \text{ o } f_k \text{ avec } j, k < i \text{ et } o \in \{+, -, ., /\} \\ \text{(addition, soustraction, multiplication, division).}$$

### 2.2) Complexité additive

Soit $F \subset K(x_1, ..., x_n)$, F fini. La complexité additive $L_+(F)$ de F sur K est le nombre minimum d'additions-soutractions contenues dans un calcul de F sur K.

Lorsqu'on prend comme mesure de complexité d'une fonction la complexité additive, cela signifie que l'on "ne compte pas" les multiplications-divisions nécessaires à son calcul. Ces opérations sont "gratuites".
On note $R(k)$ la classe des fonctions de $R(x)$ qui sont calculables sur $R$ avec $k$ ou moins opérations additives. De même $C(k)$ est la classe des fonctions de $C(x)$ dont la complexité additive sur $C$ est inférieure ou égale à $k$.

### III. COMPLEXITE ADDITIVE DES POLYNOMES DE CHEBYSHEV

Soit $T_n$ le polynôme de Chebyshev de degré $n$. Rappelons que $T_n(x) = (\cos n t)(\cos x)$. $T_n$ est un polynôme à coefficients réels dont les $n$ racines sont toutes réelles et distinctes deux à deux. On a :

$$T_1(x) = x, \text{ et pour } k \ge 1$$

$$T_{3^k}(x) = 4 T_{3^k-1}^3(x) - 3 T_{3^k-1}(x),$$

ce qui montre que $T_{3^k}$ est dans $R(k)$ quel que soit $k \ge 1$. Si donc on note $\rho(k)$ le nombre maximum des zéros et pôles réels distincts des fonctions de $R(k)$, on a :

$$\forall k \ge 1 \qquad +\infty > \rho(k) \ge 3^k.$$

L'inégalité stricte est établie par le résultat précité de Borodin et Cook. Ces auteurs ont également montré l'inégalité de droite en considérant la suite $p_k$ de polynômes de $R[x]$ définie par : $p_0(x) = x$ et quel que soit $k \ge 0$, $p_{k+1}(x) = [[p_k(x)]^2 - \epsilon_k^2]$. $p_k(x)$, où $\epsilon_k \in \mathbb{R}^+$ est choisi suffisamment petit pour que $[p_k(x)]^2 - \epsilon_k^2$ ait au moins deux fois plus de zéros réels distincts que $p_k$.

Il ait intéressant de remarquer que l'on a été jusqu'ici, à notre connaissance, incapable de trouver une fonction dans $R(k)$ qui ait strictement plus de $3^k$ zéros et pôles réels distincts ; ce fait rend probable la possibilité d'une grande amélioration de la majoration (1) évoquée dans l'introduction.
# IV. COMPLEXITE ADDITIVE SUR C DES ZEROS DES POLYNOMES EN UNE VARIABLE A COEFFICIENTS COMPLEXES

## 4.1) Position du problème

A partir de maintenant, pour la commodité des notations, nous remplaçons la variable x par la variable z.

Il s'agit de trouver une fonction $\delta$ de $C[z]$ dans $N$, liée aux zéros du polynôme, et telle qu'il existe une fonction $\rho$ de $N$ dans $N$ telle que quel que soit $k \in N$ et quel que soit $p \in C(k)$ on ait :

$$ \delta(p) \leq \rho(k). $$

Rappelons que $C(k)$ est l'ensemble des éléments de $C(z)$ dont la complexité additive est inférieure ou égale à $k$.

Il est clair que le nombre de zéros complexes distincts n'a pas la propriété ci-dessus. En effet $z^n - 1$ est dans $C(1)$ et a n zéros distincts. Mais tous ces zéros sont dans le plan complexe sur le cercle d'équation :

$$ x^2 + y^2 - 1 = 0. $$

On peut donc penser, ainsi que le suggèrent Borodin et Cook dans la conclusion de l'article déjà cité, à la fonction $\delta_o$ suivante. Pour $p \in C[z]$

$\delta_o(p) = \min \{\text{deg } r\}$ sur l'ensemble des polynômes $r$ dans $R[x,y]$ tels que $r \neq 0$ et tels que $r(x_o,y_o) = 0$ pour tous les zéros complexes $z_o = x_o + iy_o$ de $p$.
Nous allons montrer que $\delta_o$ n'a pas la propriété désirée, c'est-à-dire qu'elle n'est pas uniformément majorée sur tout $C(k)$. Plus précisement nous allons montrer (Corollaire 3 du Théorème 2) que quel que soit $k$, entier naturel supérieur ou égal à 3,

$$ \max_{p \in C(k)} \delta_o(p) = +\infty $$

La démonstration met en évidence un certain nombre de propriétés inattendues des fonctions de $R(k)$ et de $C(k)$. En particulier nous montrons (Corollaire 1) que quel que soit $n \in N$ il existe une polynôme de $R[z]$, calculable sur $C$ avec 3 additions-soutractions, qui a n zéros réels distincts. Nous établissons également (Corollaire 2) que quel que soit $n \in N$ il existe un polynôme $q_n$ de $R[z]$, qui se calcule sur $R$ avec 3 opérations additives, dont les zéros complexes se trouvent, dans le plan complexe, sur n droites passant par l'origine, chacune de ces n droites contenant n zéros distincts. Ces résultats sont un peu surprenants si on les compare à celui de A. Borodin et S. Cook qui établit qu'il existe une constante $c$ telle que aucun polynôme de $R[x]$ calculable sur $R$ avec 3 additions-soutractions n'a plus de $2^{2^{3c}}$ zéros réels distincts, c'est-à-dire n'a plus de $2^{2^{3c}}$ zéros distincts sur la droite réelle du plan complexe.

### 4.2) Théorème 1

Quel que soit $n \ge 1$ dans $N$ le polynôme de $R[z]$ $p_n = (1-z)^{n+1} - (1+z)^{n+1}$ se calcule sur $R$ avec 3 additions-soutractions et possède n zéros imaginaire purs tous distincts deux à deux. []
## Démonstration

Soit $q_n(z) = z^{n+1} - 1$. Les zéros de $q_n$ se trouvent dans le plan complexe (P) sur le cercle (C) de centre O et de rayon 1.

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

Soit $I$ le point d'image $-1$. La transformation (T) qui associe au point $M$ d'image $z \neq -1$ le point $M'$ d'image $z'$ tel que $(z'+1)(z+1) = 2$ est la composée de l'inversion de centre $I$ et de puissance 2 avec la symétrie par rapport à l'axe réel. (T) est une transformation biunivoque de (P) – {I} sur lui-même qui transforme le cercle (C) en l'axe des y. On en déduit que $p_n(z) = q_n(z') \cdot (1+z)^{n+1} = q_n(\frac{2}{z+1} - 1) \cdot (1+z)^{n+1} = (1-z)^{n+1} - (1+z)^{n+1}$

a tous ses zéros imaginaires purs et distincts deux à deux. Il y en a $n$ ou $n+1$ suivant la parité de $n$. $p_n(z)$ est un polynôme de $R[z]$ et il se calcule sur $R$ de la façon suivante :
$f_1 = z,$

$f_2 = (1 - f_1)^{n+1},$

$f_3 = (1 + f_1)^{n+1},$

$f_4 = f_2 - f_3.$

Ce calcul utilise 3 additions-soustractions. ☐

On déduit du Théorème 1 les corollaires suivants.

**Corollaire 1**

Quel que soit $n \in N$ il existe un polynôme $r_n$ dans $R[z]$ qui se calcul
sur C avec 3 additions-soustractions et qui a n zéros réels distincts.

On peut prendre $r_n(z) = p_n(iz) = (1-iz)^{n+1} - (1+iz)^{n+1}$. ☐

**Démonstration**

Immédiate. Il est intéressant de noter que par contre, d'après
le résultat de Borodin et Cook, la complexité additive *sur R* de $r_n$
tend vers $+\infty$ quand n tend vers $+\infty$.☐

**Corollaire 2**

Soit $p_{n,m}(z) = p_n(z^m) = (1-z^m)^{n+1} - (1+z^m)^{n+1}$. p_{n,m}$, comme $p_n$,
est dans $R(3)$ et ses zéros sont distribués dans le plan complexe sur
m droites distinctes passant par O et chacune de ces droites contient
n ou n+1 zéros distincts. □

Démonstration
---

Ce sont les m droites d'équation dans le plan complexe, $\theta = \frac{\pi}{2m} + k\pi$, $\theta = \frac{\pi}{2m} + \frac{2\pi}{m} + k\pi$, $\theta = \frac{\pi}{2m} + \frac{4\pi}{m} + k\pi$, ... , $\theta = \frac{\pi}{2m} + \frac{2(m-1)\pi}{m} + k\pi$, où k varie sur les entiers relatifs. La figure ci-dessous représente la distribution des zéros de $p_3$ (entourés par des ronds) et de ceux de $p_{3,3} = (1-z^3)^4 - (1+z^3)^4$ (entourés par des carrés).

$p_{3,3}$ est un polynôme de degré 9.

<figure><img src="image_4.png" /></figure>
Les zéros de $p_{3,3}$ sont situés sur les droites d'équation $\theta = \frac{\pi}{6} + k\pi$, $\theta = \frac{5\pi}{6} + k\pi$, $\theta = \frac{\pi}{2} + k\pi$, et chacune de ces droites contient 3 zéros distincts. O est un zéro triple. $\square$

### 4.3) Théorème 2

Soient $n$ et $m$ deux entiers naturels, $n \ge 1$, $m \ge 1$. Soit $p_{n,m}(z) = (1 - z^m)^{n+1} - (1 + z^m)^{n+1}$ le polynôme de $R[z]$ qui a été introduit dans le Corollaire 2 ci-dessus. Soit $r_o \neq 0$ un polynôme à coefficients réels en deux indéterminées tel que pour tous les zéros complexes $z = x + yi$ de $p_{n,m}$ on ait $r_o(x,y) = 0$. Alors

$$ \deg_{xy} r_o \ge \inf(n,m) $$

#### Démonstration

Rappelons que le degré d'un polynôme en plusieurs indéterminées est le degré du monôme de plus haut degré qu'il contient et que
$$ \deg \pi x_i = \sum a_i \quad \text{n-droites} $$
Appelons $D_1, \dots, D_m$ les $m$ droites du plan complexe qui contiennent les zéros complexes de $p_{n,m}$. $D_i$ est la droite d'équation $\theta = \frac{\pi}{2m} + 2(i-1)\frac{\pi}{m} + k\pi$ dans le plan complexe. $D_i$ a donc pour équation dans le plan $\mathbb{R}^2$ isomorphe au plan complexe :

$$ \begin{gather*} y = x \sin \left( \frac{\pi}{2m} + 2(i-1)\frac{\pi}{m} \right), \text{ soit en posant } \alpha_i = \sin \left( \frac{\pi}{2m} + 2(i-1)\frac{\pi}{m} \right), \\ y = \alpha_i x. \text{ D'après le Corollaire 2, } D_i \text{ contient au moins } n \text{ zéros } (x_1^1, \alpha_1 x_1^1), \dots, (x_n^1, \alpha_n x_n^1) \text{ de } p_{n,m}, \text{ donc de } r_o. \end{gather*} $$
Plus exactement $D_1$ contient les images par la bijection standard
de $C$ sur $\mathbb{R}^2$ des zéros $x_j^1 + i \alpha_j x_j^1$, $1 \le j \le n$, de $p_{n,m}$, mais cet abus
de langage n'entraine pas d'ambiguité. Par suite ou bien le polynôme
$r_o^1(x) = r_o(x, \alpha_j x)$ est identiquement nul ou bien $\deg_x r_o^1 \ge n$. Dans le
deuxième cas la démonstration est terminée car $\deg_{xy} r_o \ge \deg_x r_o^1$.

Dans le premier cas $r_o$ est de la forme $r_o = (y - \alpha_1 x) r_1 (x,y)$, $r_1 \neq 0$, et les zéros de $r_1$ sont ceux de $r_o$ à l'exception éventuellement de ceux de $D_1$. L'ensemble des zéros de $r_1$ contient donc tous les zéros de $r_o$ qui appartiennent aux droites $D_2, \dots, D_m$, à l'exception éventuellement de $O = \bigcap_{1 \le i \le m} D_i$.

Par suite par le même raisonnement que celui qui a été utilisé ci-dessus ou bien $r_1 = (y - \alpha_2 x) r_2 (x,y)$, $r_2 \neq 0$, et $r_o = (y - \alpha_1 x)$ ($y - \alpha_2 x) r_2$, ou bien $\deg_x r_1^2 = \deg_x r_1 (x, \alpha_2 x) \ge n-1$, ce qui implique $\deg_{xy} r_1 \ge n-1$, ce qui implique encore $\deg_{xy} r_o = \deg_{xy} [(y - \alpha_1 x)r_1] \ge n$.

Donc finalement, en itérant le raisonnement,

a) ou bien il existe $i$, $0 \le i \le m-1$, tel que $\deg_x r_i^{i+1} \ge n$ si $i = 0$ et telque $\deg_x r_i^{i+1} \ge n-1$ si $1 \le i \le m-1$, où les polynômes $r_k \in \mathbb{R}[x,y]$, pour $1 \le k \le i$, et $r_k^{k+1} \in \mathbb{R}[x]$, pour $0 \le k \le i$, sont définis de la façon suivante. Quel que soit $k$, $0 \le k \le i$, $r_k^{k+1}(x) = r_k(x, \alpha_k x)$ et quel que soit $k$, $1 \le k \le i$, $r_k(x,y)$ est tel que :

$$
(2) r_o(x,y) = \bigcap_{1 \le j \le k} (y - \alpha_j x) r_k(x,y) \text{ et } r_k \neq 0.
$$
Dans ce cas deg$_{xy}$ rᵢ ≤ deg$_{x}$ rᵢ est supérieur ou égal à n si i = 0
et supérieur ou égal à n-1 si 1 ≤ i ≤ m-1 et l'on a quel que soit
i, deg$_{xy}$ r₀ ≥ n puisque d'après (2), pour i ≥ 1, deg$_{xy}$ r₀ ≥ n-1+i.

b) ou bien r₀ est de la forme r₀ = Π_{1≤j≤m} (y - α_j x) r_m, avec r_m ≠ 0,
ce qui implique deg_{xy} r₀ ≥ m.

On a donc bien dans tous les cas deg_{xy} r_0 ≥ inf (n,m). □

Corollaire 3

$\delta_o$ n'est pas majorée uniformément sur $\mathbb{R}(3). \square$

Démonstration

Rappelons que $\delta_o$ est la fonction qui à un polynôme $p$ de $\mathbb{C}[z]$ associe
l'entier naturel

$\delta_o(p) = \min \{\text{deg } r\} \text{ sur l'ensemble des polynômes } r \in \mathbb{R}[x,y] \text{ tels que } r \neq 0 \text{ et tel que pour tous les zéros complexes } z = x + yi \text{ de } p \text{ on ait } r(x,y) = 0.$

Quels que soient n et m, entiers naturels supérieurs ou égaux à 1,
le polynôme $p_{n,m}(z) = (1 - z^m)^{n+1} - (1 + z^m)^{n+1}$ se calcule sur R avec
3 additions-soutractions, donc est dans R(3). D'autre part d'après le
Théorème 2, quels que soient n et m $\delta_o(p_{n,m}) \ge \inf(n,m)$. Donc :

$$
\max_{p \in \mathbb{R}(3)} \delta_o(p) = +\infty . \square
$$
V. CONCLUSION

Le problème de la caractérisation de la complexité additive sur C des polynômes de R[x] et de C[x] par des propriétés de leurs zéros reste donc complètement ouvert. Nos résultats mettent en évidence par ailleurs l'importance pour la complexité additive du corps des constantes. En effet nous avons montré (Corollaire 1) qu'il existe des suites {$r_n$} de polynômes de R[x] telles que chaque $r_n$ se calcule **sur C** avec au plus 3 additions-soutractions mais telles que, par contre, la complexité additive **sur R** de $r_n$ tend vers l'infini lorsque n tend vers l'infini. En ce sens on peut rapprocher les résultats de cet article de certains résultats de S. Winograd [3] sur la complexité multiplicative.
VI. BIBLIOGRAPHIE

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

[2] V. Strassen, Dic Berechnungskomplexität von elementarsymmetrischen Funktionen und von Interpolationskoeffizienten, Numer. Mathematik 17 (20) (1973) pp 238-251.

[3] S. Winograd, Some bilinear forms whose multiplicative complexity depends on the field of constants, Mathematical Systems Theory 10 (2) (1977) pp 169-180.

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

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