# Bornes inferieures pour la complexite des polynomes a coefficients 0-1

Laurent Hyafil, Jean-Paul van de Wiele

► To cite this version:

Laurent Hyafil, Jean-Paul van de Wiele. Bornes inferieures pour la complexite des polynomes a coefficients 0-1. [Rapport de recherche] IRIA-RR-192, IRIA. 1976, pp.48. hal-04716375

HAL Id: hal-04716375

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

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
IRIA

laboria

Institut de Recherche
d'Informatique
et d'Automatique

Domaine de Voluceau
Rocquencourt
B. P. 5 78150 - Le Chesnay
France

Tél.: 954 90 20

Inv-02260

laboratoire de recherche
en informatique
et automatique

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

BORNES INFÉRIEURES
POUR LA COMPLEXITÉ
DES POLYNÔMES
A COEFFICIENTS 0-1

L. HYAFIL
J. P. VAN DE WIELE

Rapport de Recherche N° 192
Octobre 1976
BORNES INFÉRIEURES POUR LA COMPLEXITÉ
DES POLYNÔMES A COEFFICIENTS 0-1

L. Hyafil
J.P. Van de Wiele*

Résumé :

Nous montrons dans le modèle avec préconditionnement complexe l'existence dans l'ensemble
des polynômes en une variable de degré $d$ à coefficients 0-1 :

- de polynômes qui requièrent $\Omega (\frac{d^{1/3}}{\log_2 d})$ multiplications-divisions non sclaires.

- de polynômes qui requièrent $\Omega (\frac{d^{1/3}}{\log_2 d})$ additions-soutractions,

et de polynômes qui requièrent $\Omega (\frac{d^{1/2}}{\log_2 d})$ opérations arithmétiques.

Enfin, nous relions la complexité des formes multilinéaires à coefficients 0-1 à celles des formes
linéaires à coefficients 0-1.

Abstract :

We show the existence of univariate 0-1 polynomials of degree $d$ that require $\Omega (\frac{d^{1/3}}{\log_2 d})$ non
scalar multiplications/divisions when arbitrary complex preconditionning is allowed. Morover we
show the existence in the same model of computation of 0-1 polynomials of degree $d$ that
require $\Omega (\frac{d^{1/3}}{\log_2 d})$ additions/subtractions and of 0-1 polynomials of degree $d$ that require $\Omega (\frac{d^{1/2}}{\log_2 d})$ arithmetical operations.

Finally, we relate the multiplicative complexity of 0-1 $n$-linear forms to the complexity of 0-1
linear forms.
# 1. Introduction *

Nous nous intéressons au nombre minimum d'opérations arithmétiques nécessaire pour évaluer les polynômes à coefficients complexes dans le modèle avec préconditionnement complexe arbitraire. Dans ce modèle on s'autorise gratuitement tout calcul préalable dans $\mathbb{C}$ sur les coefficients du polynôme qui ne fait pas intervenir la valeur des variables. Ce calcul peut dépendre du polynôme particulier que l'on veut évaluer. En utilisant la terminologie de Strassen [72] nous considérons les calculs dans $C(X_1, X_2, ..., X_N)$ mod. $Cu\{X_1, X_2, ..., X_N\}$ (dans le cas des polynômes à $N$ variables).

Bien que tous les résultats que nous démontrons dans cet article soient aussi valables pour les polynômes à coefficients dans un corps k *infini* quelconque nous nous limitons dans un souci de simplicité au cas complexe.

Motzkin [55] et Belaga [58] ont montré que les polynômes de degré $d$ dans $C[X]$ (1 variable) dont les coefficients sont algébriquement indépendants requièrent pour leur évaluation dans $C(X)$ mod. $Cu\{X\} \left[ \frac{d+1}{2} \right]$ multiplications-divisions (m/d) *et* d additions-soutractions (a/s). Ces bornes sont quasiment optimales (Motzkin [55], Belaga [58], Revah [75]). En effet tout polynôme de degré $d$ peut être évalué dans ce modèle avec d $a/s$ et $\left[ \frac{d+2}{2} \right]$ m/d.

Parmi les polynômes à coefficients rationnels certains sont aussi "difficiles" à calculer que les polynômes à coefficients algébriquement

* Si $k$ est un corps, nous notons :

k[X] l'anneau des polynômes en $X$ à coefficients dans $k$

k(X) le corps des fractions de k[X]

k[[X]] l'anneau des séries formelles en $X$ à coefficients dans $k$

$C, Q$ et $Z$ désignent l'ensemble des complexes, des rationnels et des entiers relatifs.
indépendants. Strassen [74] a construit effectivement des polynômes à coefficients rationnels de degré d dont l'évaluation dans $C(X)$ mod. $Cu\{X\}$ requiert $[\frac{d}{2}-2]$ m/d et d-4 a/s (ex : $\sum_{\delta=0}^{d} 2^{2^\delta} d^3 x^\delta$). On peut interpréter ce résultat en disant que $\sum_{\delta=0}^{d} 2^{2^\delta} d^3 x^\delta$ a une complexité quasi maximale dans $C(X)$ mod. $Cu\{X\}$. Notons au passage que la question de savoir si la complexité maximale des polynômes de $Q[X]$ de degré d dans $Q(X)$ mod. $Qu\{X\}$ est $\approx \frac{3d}{2}$ est encore ouverte. La meilleure borne supérieure est $\frac{3d}{2} + O(d^{1/2})$. (Paterson-Stockmeyer [73], Rabin-Winograd [71]).

Les polynômes rationnels de Strassen sont "compliqués" en ce sens que leurs coefficients croissent très rapidement. Les bornes inférieures qu'il obtient sont fonction du taux de croissance des coefficients et sont d'autant meilleures que ce taux est plus grand. Par exemple la borne inférieure pour le nombre total d'opérations est $\approx \frac{\sqrt{d}}{\sqrt{\log_2 d}}$ pour $\sum_{\delta=0}^{d} 2^{2^\delta} x^\delta$ alors qu'elle est $\approx \frac{3d}{2}$ pour $\sum_{\delta=0}^{d} 2^{2^\delta} d^3 x^\delta$.

Une question naturelle était de se demander s'il existe des polynômes "simples" difficiles à calculer et d'en construire effectivement. Par polynômes simples on entend par exemple les polynômes dont les coefficients appartiennent à l'ensemble $\{0,1\}$. Ce problème considéré par Strassen [74] comme l'un des problèmes ouverts les plus intéressants dans ce domaine a été étudié par Paterson et Stockmeyer [73] et plus récemment par Dobkin et Lipton [75], Lipton [75] et Lipton-Stockmeyer [76]. Les deux premiers résultats sont relatifs à des modèles de calcul plus restrictifs que celui que l'on considère dans cet article.

Paterson et Stockmeyer ont montré que dans $Z[X]$ mod. $Zu\{X\}$ (pré-conditionnement entier, pas de division) il existe des polynômes $O(1)$ de degré d qui requièrent de l'ordre de $d^{1/2}$ m/d non scalaires.
Dobkin et Lipton ont étudié le modèle avec préconditionnement fini
qui est peut être plus proche de la "pratique" que le modèle avec
préconditionnement arbitraire. Dans ce modèle les seules données autorisées
gratuitement sont la valeur de la variable X et la constante l et les
opérations sont les 4 opérations arithmétiques {+, -, ., ‡} ; si bien que
la constante n s'obtient avec un coût qui dépend de n. Dobkin et Lipton
ont montré qu'il existe des polynômes O-1 de degré d qui requièrent
(dans ce modèle) de l'ordre de $\frac{d}{\log_2 d}$ opérations. Et ce résultat est
optimal d'après Savage [74].

En ce qui concerne le modèle avec préconditionnement complexe :
Lipton [75] a montré en utilisant des résultats de Strassen qu'il existe
des polynômes O-1 de degré d qui requièrent $\Omega(\frac{d^{1/4}}{\log_2 d}) * m/d$ non scalaires
dans $C(X)$ mod. $Cu\{X\}$. D'autre part, Lipton et Stockmeyer [76] ont montré
que des polynômes simples ($\text{Ex : } X^{n-1}$) pouvaient se factoriser en le
produit de deux polynômes "compliqués" ($\Omega(d^{1/4-\epsilon})$, arbitrairement petit)
mais sans exhiber les facteurs.

Dans la deuxième partie nous montrons, en améliorant l'argument de
Lipton [75] et en l'étendant aux a/s et au nombre total d'opérations, qu'il
existe des polynômes en une variable à coefficients O-1 qui requièrent,
dans $C(X)$ mod. $Cu\{X\}$, $\Omega(\frac{d^{1/3}}{\log_2 d})$ m/d non scalaires, qu'il en existe également
qui requièrent $\Omega(\frac{d^{1/3}}{\log_2 d})$ a/s dans le même modèle et nous obtenons une
borne inférieure en $\Omega(\frac{d^{1/2}}{\log_2 d})$ pour le nombre total d'opérations (m/d + a/s).
La meilleure borne supérieure comme actuellement est $O(\frac{d}{\log_2 d})$ (Savage [74]).

Ces résultats comme ceux de Lipton et des auteurs cités ci-dessus
sont uniquement des résultats d'existence. Notons d'ailleurs que mis à
part le trivial argument de croissance sur le degré ($X^d$ requiert $\lceil \log_2 d \rceil$ m/d)

$$ \* f(d) = \Omega(g(d)) \iff \exists c > 0 \text{ et } d_0 > 0 \text{ tq : } f(d) \ge cg(d) \text{ pour } d \ge d_0 $$
on ne connaît à l'heure actuelle **aucun** résultat constructif de complexité pour les polynômes à coefficients 0-1. Un résultat partiel a été obtenu par Hyafil et Van de Wiele [75] pour la complexité additive de $\sum_{i=0}^{d} x^i$ quand on ne s'autorise pas la division.

La méthode qui a permis d'obtenir des bornes inférieures pour les polynômes à une variable peut être appliquée aux polynômes à plusieurs variables. Ainsi nous montrons dans la troisième partie des bornes inférieures pour la complexité des formes linéaires et multilinéaires. En ce qui concerne particulièrement les formes linéaires, nous montrons qu'il existe des ensembles de d telles formes à coefficients 0-1 en d variables dont l'évaluation dans $C(X_1, X_2, ..., X_d) \mod. Cu\{X_1, X_2, ..., X_d\}$ requiert $\Omega(d^{2/\log_2 d})$ opérations et cette borne est optimale d'après un résultat de Savage [74].

Enfin dans la quatrième partie, à partir d'une caractérisation nouvelle de la complexité d'un ensemble de polynômes homogènes en plusieurs variables, nous relions la complexité des formes multilinéaires à celles des formes linéaires. En particulier nous montrons que la construction effective d'une forme multilinéaire à coefficients 0-1 de degré d en $Nd$ variables dont l'évaluation dans $C(X_1, X_2, ..., X_{Nd}) \mod. Cu\{X_1, X_2, ..., X_{Nd}\}$ requiert $\Omega((\lambda N)^{d/6-2})m/d$ non scalaires (λ constante >0), peut se déduire de la construction d'un ensemble de $N^{d/2}$ formes linéaires en $N^{d/2}$ variables à coefficients 0-1 dont l'évaluation dans $C(X_1, X_2, ..., X_{Nd/2}) \mod. Cu\{X_1, X_2, ..., X_{Nd/2}\}$ requiert $\Omega(\frac{N^d}{d \log_2 N})$ opérations arithmétiques.
## 2. Bornes inférieures sur la complexité des polynômes à une variable à coefficients 0-1 avec préconditionnement complexe :

### 2.1. Définitions

Rappelons qu'un calcul ou programme $\beta$ dans $C(X)$ mod. $Cu\{X\}$ est une suite $F = \{f_0, f_1, -, f_\ell\}$ de fonctions de $C(X)$ telle que $f_i \in C\{X\}$ ou $f_i = f_j \circ f_k$ avec $j, k < i$ et $\circ \in \{+, -, \cdot, \div\}$.

La complexité additive (resp. multiplicative) de $\beta$ est le nombre d' a/s (resp. m/d) contenue dans $\beta$. Nous la noterons : $L(\pm/\beta)$ (resp. $L(*/\beta)$). La complexité de $\beta$ est : $L(\pm/\beta) + L(*/\beta)$.

Un calcul $\beta$ dans $C(X)$ mod. $Cu\{X\}$ calcule une fonction $p$ de $C(X)$ si $p \in F$.

La complexité additive de $p \in C(X)$ dans $C(X)$ mod. $Cu\{X\}$ que nous noterons dans cet article sans ambiguïté $L(\pm/p)$ est :

$$ \text{Min}[L(\pm/\beta)] \text{ pour tout } \beta \text{ calculant } p \text{ dans } C(X) \text{ mod. } Cu\{X\}. $$

Nous définirons de même la complexité multiplicative $L(*/p)$ et la complexité totale : $L(p)$ de $p$.

Enfin $L'(*/\beta)$ et $L'(*/p)$ sont les complexités multiplicatives non scalaires c'est-à-dire relatives au nombre de m/d non scalaires. Une m/d est non scalaire si : $f_i = f_j \cdot f_k$ avec $f_j, f_k \notin C$ ou $f_i = f_j \div f_k$ avec $f_k \notin C$.

Soit $Z_{01}^d[X]$ l'ensemble des polynômes en $X$ de degré $\le d$ dont les coéfficients sont égaux à 0 ou 1.

Nous allons montrer dans la première partie de cet article que dans $Z_{01}^d[X]$ chacune des conditions :

$$ L'(*/p) = \Omega\left(\frac{d^{1/3}}{\log_2 d}\right), \quad L(\pm/p) = \Omega\left(\frac{d^{1/3}}{\log_2 d}\right), \quad L(p) = \Omega\left(\frac{d^{1/2}}{\log_2 d}\right) $$

est vérifiée pour au moins un polynôme $p$ de $Z_{01}^d[X]$. Ce n'est pas nécessairement le même dans chacun des trois cas.
En d'autres termes si $c_{01}(d)$ (resp. $c'_{01}(*/d)$ et $c_{01}(\pm/d)$) est la complexité maximale des polynômes de $Z_{01}^d[X] : c_{01}(d) = \max_{p \in Z_{01}^d[X]} [L(p)]$

$$c_{01}(d) = \Omega\left(\frac{d^{1/2}}{\log_2 d}\right), c'_{01}(*/d) = \Omega\left(\frac{d^{1/3}}{\log_2 d}\right), c_{01}(\pm/d) = \Omega\left(\frac{d^{1/3}}{\log_2 d}\right)$$

Les preuves de ces résultats s'inspirent de celle d'un résultat de Lipton [75] qui a montré que :

$$c'_{01}(*/d) = \Omega\left(\frac{d^{1/4}}{\log_2 d}\right).$$

C'est en analysant dans le détail la preuve de Lipton qui repose fondamentalement sur des résultats de Strassen [74] que nous avons été capables de l'améliorer et de montrer qu'on peut l'étendre au cas des additions et du nombre total d'opérations.

## 2.2. Borne inférieure pour les m/d non scalaires :

Dans un souci de clarté, nous allons exposer de façon détaillée et un peu différente de la façon dont il l'a exposé lui-même l'argument de Lipton. Mais auparavant nous allons en présenter de façon informelle les idées fondamentales :

Soit $E_*(\tau,d)$ l'ensemble des polynômes de $C[X]$ de degré $\le d$ calculables avec $\le \tau$ m/d non scalaires.

A des détails techniques près il existe des polynômes $P_{\tau i}$, $1 \le i \le +\infty$, fixes (ils ne dépendent que de $\tau$) dans $Z[z_1, z_2, \dots, z_{m(\tau,d)}]$, où $m(\tau,d)$ est un entier qui ne dépend que de $\tau$ et de $d$, et $\max_{1 \le i \le d} \deg(P_{\tau i}) \le f(\tau,d)$ entier positif, qui satisfont la propriété suivante :

pour tout $r \in E_*(\tau,d)$, $r = \sum_{\delta=0}^{d} \alpha^{\delta} x^{\delta}$, $\alpha_{\delta} \in C$ il existe des paramètres $\lambda, \lambda_1, \lambda_2, \dots, \lambda_{m(\tau,d)} \in C$ tels que :

$$\forall \delta, 1 \le \delta \le d, \alpha_{\delta} = \lambda P_{\tau \delta}(\lambda_1, \lambda_2, \dots, \lambda_{m(\tau,d)})$$
Comme les polynômes $P_{\tau i}$ sont des polynômes à coefficients entiers en $m(\tau,d)$ variables de degré $\le f(\tau,d)$ il existe une forme $H \in Z[y_1,y_2,\dots,y_d]$ de degré $g = g[f(\tau,d),m(\tau,d)]$ (polynôme homogène à coefficients entiers de degré $g$ en $d$ variables) telle que :

$$H(P_{\tau 1}, P_{\tau 2}, \dots, P_{\tau d}) = 0.$$

On en déduit :

$$\forall r = \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta} \in E_{*}(\tau, d) \quad H(\alpha_{1}, \alpha_{2}, \dots, \alpha_{d}) = 0.$$

g de même que $f$ et $m$ est fonction croissante de $\tau$ et de $d$.

Soit alors un polynôme de degré $\le d$ à coefficients entiers positifs

$$r_0 = \sum_{\delta=0}^{d} \beta_{\delta} X^{\delta} \text{ tel que : } H(\beta_1, \beta_2, \dots, \beta_d) \neq 0.$$

On montre qu'il en existe avec : $\beta_{\delta} \le g[f(\tau,d),m(\tau,d)]$ pour $1 \le \delta \le d$ ;
$r_0$ n'appartient pas à $E_*(\tau,d)$. Il peut s'écrire comme combinaison linéaire de $k = k[g[f(\tau,d),m(\tau,d)]]$ polynômes de $Z_{01}^d[X]$, où $k$ est un entier qui ne dépend que de $\tau$ et de $d$. Il s'ensuit que :

$$\tau \le L'(*/r_0) \le k(\tau,d) c'_{01}(*/d)$$

Rappelons que $c'_{01}(*/d)$ est la complexité multiplicative non scalaire maximale des polynômes de $Z_{01}^d[X]$.

$$D'\text{où : } c'_{01}(*/d) \ge \frac{\tau}{k(\tau,d)}$$

On obtiendra des bornes inférieures d'autant plus grandes que $k(\tau,d)$ croîtra plus faiblement avec $\tau$, donc que $f(\tau,d)$ et $m(\tau,d)$ seront plus petits. C'est justement la mise en évidence pour les degrés des $P_{\tau i}$ d'une meilleure borne supérieure ($f(\tau,d)$) que celle qu'utilise Lipton qui nous permet d'améliorer son résultat.

Nous allons maintenant entrer dans plus de détails.

**Théorème 1** : (Lipton [75]).

Il existe une constante $c > 0$ telle que pour tout entier $d > 0$ il existe un polynôme $p$ de $Z_{01}^d[X]$ tel que :

$$L'(*/p) \ge \frac{d^{1/4}}{c \log_2 d} \quad \square$$
Démonstration :

Lemme 1 (Strassen [74]).

Soit k un corps. Soit $\beta$ un calcul de $a = \sum_{\delta=0}^{\infty} \alpha_{\delta} X^{\delta} \in k[[X]]$ dans $k[[X]]$ mod. ku{X}. $k[[X]]$ est l'anneau des séries formelles en X. Rappelons que ses éléments inversibles sont les $b = \sum_{\delta=0}^{\infty} b_{\delta} X^{\delta}$ tels que : $b_0 \neq 0$.

Soit : $L(\pm/\beta) = u>0$, $L(*/\beta) = v>0$ le nombre d'a/s et le nombre de m/d contenues dans $\beta$. Soit $m = 2v$.

Alors il existe des polynômes $P_{\delta} \in Z[z_1, z_2, \dots, z_m]$, pour $1 \le \delta < +\infty$, à coefficients entiers en m variables et des éléments $\lambda, \lambda_1, \dots, \lambda_m$ de k tels que :

$$
\alpha_{\delta} = \lambda P_{\delta}(\lambda_1, \lambda_2, \dots, \lambda_{\min}), \quad \delta \ge 1
$$

De plus :

$$
\max_{1 \le \delta \le d} \left[ \deg(P_{\delta}) \right] \le 2(u+1)d^v \quad \text{pour } d \ge 5. \quad \square
$$

Lemme 2 : *Soit d entier>0, τ entier>0, E*_*(τ,d) = {p ∈ C[X] tels que deg p ≤ d et L'(*/p)≤τ} m = 4τ + (τ+1)(3τ+2) ≤ 4τ² pour τ ≥ τ₀.

Il existe des polynômes $P_{\tau i}$, $1 \le i \le +\infty$ fixes (ils ne dépendent que de $\tau$) dans $Z[z_1, z_2, \dots, z_m]$ avec $\max_{1 \le i \le d} \deg(P_{\tau i}) \le f(\tau, d)$ et :

$f(\tau,d) \le [(\tau+1)(\frac{3\tau}{2}+1)+1]2d \left[ \left(\frac{3\tau}{2}+1\right)(\tau+1)+2\tau \right] \le d^{2\tau^2} \text{ pour } d \text{ et } \tau \text{ suffisamment grands qui satisfont la propriété suivante :}$

pour tout $r = \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta} \in E_{*}(\tau, d)$ et pour tout $\theta \in C$ en dehors d'un ensemble fini $F_r \subset C$ ($F_r$ dépend de $r$) il existe des éléments de $C$, $\lambda, \lambda_1, \lambda_2, \dots, \lambda_m$ qui dépendent de $\theta$ et de $r$ tels que :

$$
\forall \delta \ge 1 \quad \tilde{\alpha}_{\delta} = \lambda P_{\tau \delta}(\lambda_1, \lambda_2, \dots, \lambda_{\min}) \text{ avec } :
$$

$$
r = \sum_{\delta=0}^{d} \tilde{\alpha}_{\delta} (X-\theta)^{\delta} \quad \Box
$$
Démonstration du lemme 2 :

Tout r de $E_*(\tau,d)$ est calculable dans $C(X)$ mod. $Cu\{X\}$ par un programme
du type :

$$
Q_r^* : s_{-1} = 1
$$

$s_0 = X$

pour $t = 1, \dots, \tau$

$$
s_t = \left( \sum_{i=-1}^{t-1} m_{t,i} s_i \right) \left( \sum_{i=-1}^{t-1} m'_{t,i} s_i \right) \div \left( \sum_{i=-1}^{t-1} m''_{t,i} s_i \right)
$$

$$
r(X) = \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta} = s_{\tau+1} = \sum_{i=-1}^{\tau} m_{\tau+1, i} s_{i}
$$

où les $m_{t,i}$ $1 \le t \le \tau+1, -1 \le i \le t-1$

$$
m'_{t,i} \quad 1 \le t \le \tau, \quad -1 \le i \le t - 1
$$

$$
m''_{t,i} \quad 1 \le t \le \tau, \quad -1 \le i \le t - 1
$$

sont des éléments de C.

Soit $F_r$ l'ensemble des zéros des résultats intermédiaires de $Q_r^*$ qui
apparaissent en dénominateur. C'est un ensemble fini.

Pour tout $\theta \notin F_r$, $Q_r^*$ est exécutable dans $C[[X-\theta]]$ mod. $Cu\{X\}$ et calcule
$$r = \sum_{\delta=0}^{d} \tilde{\alpha}_{\delta}(X-\theta)^{\delta} \equiv \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta}$$

$$
Q_r^* \text{ contient } u = \sum_{t=1}^{\tau} 3t + (\tau+1) = (\tau+1)(\frac{3\tau}{2}+1) \text{ a/d}
$$

$v'_1 = u \text{ m/d scalaires}$

$v'_2 = 2\tau \text{ m/d non scalaires}$

$v = v'_{1} + v'_{2} \text{ m/d}$

Donc on peut appliquer le lemme 1 avec $m = 2v = 4\tau + (\tau+1)(3\tau+2)$; (le
fait que $Q_r^*$ soit un calcul dans $C[[X-\theta]]$ mod. $CuX$ et non pas dans $C[[X]]$
mod. $Cu\{X\}$ n'a pas d'importance (cf Strassen [74]). Pour se convaincre que
les $P_{\tau i}$ ne dépendent pas de r et de d il suffit de remarquer que leur
construction dans la preuve de Strassen (Strassen [74] lemme 2.4. P 134,
cas : $m = 2v$) ne dépend que de la suite des opérations de $Q_r^*$. $\square$
**Lemme 3 (Strassen [74]):**

Soit $m \ge 1$, $c \ge 2$, $q \ge 5$ des entiers naturels, soient $z_1, z_2, \dots, z_m$ des indéterminés sur $Z$ et soient

$$P_1, P_2, \dots, P_q \in Z[z_1, z_2, \dots, z_m]$$

tels que $\deg(P_i) \le c$ pour tout $i$

Si $g$ est un entier naturel tel que :

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

alors il existe une forme $H$ de degré $g$ dans $Z[y_1, y_2, \dots, y_d]$ telle que :
$$ H(P_1, \dots, P_q) = 0. \square $$

**Remarque :** Strassen donne en fait une forme un peu différente et beaucoup plus forte du lemme 3. (Se reporter à l'annexe I pour la démonstration du lemme 3). Le lemme 2.3. de Strassen (Strassen [74] P 133) fait intervenir le poids des $P_i$ de façon à borner la hauteur de $H$. C'est pourquoi la borne supérieure que nous utilisons pour $g$ (formule (1)) est un peu meilleure que celle qu'utilise Lipton mais le résultat final n'en est pas affecté. $\square$

Nous déduisons des lemmes 2, 3 qu'il existe une forme $H$ de degré $g$, si $g^{d-4\tau^2-1} \ge (d^{2\tau^2} 4\tau^2)^d$, dans $Z[y_1, y_2, \dots, y_d]$ telle que pour tout $r = \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta}$ dans $E_{*}(\tau, d)$ :

$$ (2) \quad H(\alpha_1, \alpha_2, \dots, \alpha_d) = 0. $$

En effet, on a :

$$ H(\tilde{\alpha}_1, \tilde{\alpha}_2, \dots, \tilde{\alpha}_d) = 0 \text{ avec : } r = \sum_{\delta=0}^{d} \tilde{\alpha}_{\delta} (X-\theta)^{\delta} \text{ pour tout } r \text{ et tout } \theta $$

en dehors d'un ensemble fini $F_r \subset C$. Application de la formule (1) avec :
$$ q = d \quad m \le 4\tau^2, \quad c \le d^{2\tau^2}. $$

On peut choisir $\theta$ transcendant sur les $\alpha_i$. On a :

$$ 0 = H\left( \sum_{\delta=1}^{d} (\delta) \alpha_{\delta} \theta^{\delta-1}, \dots, \sum_{\delta=d}^{d} (\delta) \alpha_{\delta} \theta^{\delta-d} \right) $$

Le terme constant de ce polynôme identiquement nul en $\theta$ est $H(\alpha_1, \dots, \alpha_d)$.
Comme $\theta$ est transcendant sur les $\alpha_i$, $H(\alpha_1, \dots, \alpha_d) = 0$.
**Lemme 4** : (Lipton [75]).

Soit $H(y_1, y_2, \dots, y_d)$, $H \neq 0$, **un polynôme de degré g en d variables, à coefficients dans** C. **Alors il existe un tuplet d'entiers, $(\beta_1, \beta_2, \dots, \beta_d)$ avec** $0 \le \beta_i \le g$ **tel que** : $H(\beta_1, \beta_2, \dots, \beta_d) \neq 0$. ☐

**Lemme 5** : (Lipton [75]).

Soit $r = \sum_{i=1}^{d} \beta_i x^i$ un polynôme de $Z[X]$, $0 \le \beta_i \le M$. **Alors**
$L'(*/r) \le c'_{01}(*/d) \cdot (\log_2 M + 1)$. ☐

D'après une remarque de Kung* il suffit de décomposer les $\beta_i$ en base 2. ☐

Nous pouvons maintenant terminer la démonstration du Théorème 1.

Soit $r_0 = \sum_{i=1}^{d} \beta_i x^i$ où $\bar{\beta} = (\beta_1, \dots, \beta_d)$ satisfait le lemme 4 avec :

$$ (3) \quad g^{d-4\tau^2-1} \ge (d^{2\tau^2})^{4\tau^2} d^d. \text{ D'après (2) : } L'(*/r_0) > \tau $$

D'après le lemme 5 : $L'(*/r_0) \le c'_{01}(*/d) \cdot (\log_2 g+1)$; (3) est satisfaite
si $g \ge d^{(8\tau^4+d)/d}$ et $\tau^2 < \frac{d-1}{4}$ donc si :

$$ (4) \quad g \ge d^{1+8\tau^4/d} \quad \text{et} \quad \tau < \frac{\sqrt{d-1}}{2} $$

$$ \Rightarrow c'_{01}(*/d) \ge \sup_{0<\tau<(d^{1/2}-\epsilon)/2} \left[ \frac{\tau}{(1+8\tau^4/d)\log_2 d + 1} \right] $$

Soit $c'_{01}(*/d) \ge \frac{d^{1/4}}{c \log_2 d}$ avec $c \le 10$ (pour $d$ suffisamment grand). ☐

Nous allons maintenant montrer comment on peut améliorer ce résultat :

**Théorème 2** :

Il existe une **constante** $c_1 > 0$ **telle que** pour tout entier $d \ge 2$ :

$$ c'_{01}(*/d) \ge \frac{d^{1/3}}{c_1 \log_2 d} \quad \square $$

<footnote>* H.T. Kung : communication personnelle.</footnote>
## Démonstration

L'idée est de prendre une meilleure borne supérieure pour le degré des $P_{\tau i}$ dans le lemme 2.

**Lemme 6 :** (mêmes notations que le lemme 2)

$$ (5) \quad \max_{1 \le i \le d} \deg(P_{\tau i}) \le 2(v'_1+1)d^{\frac{v'_2}{2}} \quad \text{pour d suffisamment grand.} $$

avec :

$$ v'_1 = (\tau+1)(3\tau+2) \quad \text{(nb de m/d scalaires dans } Q_r^*\text{)} $$

$$ v'_2 = 2\tau \quad \text{(nb de m/d non scalaires dans } Q_r^*\text{)} $$

Donc quand d et τ sont suffisamment grands :

$$ \max_{1 \le i \le d} \deg(P_{\tau i}) \le d^{3\tau} \quad \square $$

La formule (5) du lemme 6, bien qu'elle ne soit pas explicitement démontrée dans l'article de Strassen, se déduit immédiatement de la démonstration du lemme 1. (lemme 2-4 de Strassen [74], P 134, cas $m = 2v$). Soit, en reprenant les notations de Strassen :

u le nombre d'a/s

$v'_1$ le nombre de m/d scalaires

$v_1$ le nombre de m non scalaires

$v_2$ le nombre de d non scalaires

$D(u, v'_1, v_1, v_2)$ le degré maximum des $P_{\tau i}$, $1 \le i \le d$ ;

On a :

$$ D(u+1, v'_1, v_1, v_2) = D(u, v'_1, v_1, v_2) $$

$$ D(u, v'_1+1, v_1, v_2) = D(u, v'_1, v_1, v_2)+1 $$

$$ D(u, v'_1, v_1+1, v_2) \le 2D(u, v'_1, v_1, v_2) $$

$$ D(u, v'_1, v_1, v_2+1) \le dD(u, v'_1, v_1, v_2)+d+2 $$

$$ \begin{aligned} > D(u, v'_1, v_1, v_2) & \le (v'_1+1) 2^{\frac{v_1}{2} + \frac{v_2}{2} - 1} (d^{3d} + 3d + -3d + 2) \\ & \le 2(v'_1+1)d^{\frac{v_1}{2} + \frac{v_2}{2}} = 2(v'_1+1)d^{\frac{v'_2}{2}} \end{aligned} $$

pour d suffisamment grand.
Cette borne tient compte du fait qu'une multiplication scalaire ne double pas le degré comme une multiplication non scalaire mais l'augmente seulement de 1.

On obtient donc pour le degré des $P_{\tau i}$ du lemme 2 une borne supérieure en $d^{\alpha\tau}$ ($\alpha \in \mathbb{N}$) et non plus en $d^{\alpha\tau^2}$.

La condition (3) ci-dessus est donc remplacée par :

$$ (6) \quad g^{d-4\tau^2-1} \ge (d^{3\tau})^{4\tau^2} d^d. \text{ Elle est satisfaitement si :} $$

$$ (7) \quad g \ge d^{(12\tau^3+d)/d} \quad \text{et} \quad \tau^2 < \frac{d-1}{4} $$

$$ \Rightarrow c'_{01}(*,d) \ge \sup_{0<\tau<d} 1/2 - \epsilon \left[ \frac{\tau}{(1+12\tau^3/d)\log_2 d + 1} \right] $$

Soit : $c'_{01}(*,d) \ge \frac{d^{1/3}}{c_1 \log_2 d}$ avec $c_1 \le 14$ pour d suffisamment grand. []

### 2.3. Borne inférieure pour le nombre minimum d'a/s :

Nous allons établir pour la complexité additive des polynômes à coéfficients $0-1$ dans $C(X)$ mod. $Cu\{X\}$ un résultat analogue à celui que nous avons obtenu pour la complexité multiplicative. Le cas des a/s n'a pas été envisagé dans le papier de Lipton [75]. Pour étendre son argument nous nous sommes inspirés des idées de Borodin et Cook [74] et naturellement de Strassen [74]. Nous démontrons d'abord un lemme analogue au lemme 2 de 2.2.

**Lemme 7 :** soit $d$ entier>0, $\tau$ entier>0.

$$ E_+(\tau) = \{r \in \mathbb{C}[X] \text{ tels que } L(\pm r/\tau) \le \tau\}, \quad m(\tau) = (\tau+1)(\tau+3). $$

Il existe des polynômes fixes $P_{\tau\delta}$, $0 \le \delta \le d$, dans $Z[z_1, z_2, \dots, z_m(\tau)]$ ne dépendant que de $\tau$ et de $d$ dans $Z[z_1, z_2, \dots, z_m(\tau)]$ avec
$$ \text{Max deg}(P_{\tau i}) \le (d+1)^2(\tau+1) + 2(d+1)^2\tau + \dots + 2(d+1)^2, P_{\tau 0} = (d!)^{2\tau+2} \text{ tels que pour tout} $$
$$ 0 \le i \le d \quad \text{et pour tout} \quad \theta \in C \text{ non inclus dans un ensemble fini } F_r \subset C \text{ qui} \\ \text{dépend de r, il existe des éléments de } C, \lambda, \lambda_1, \dots, \lambda_m \text{ qui dépendent de } \theta \\ \text{et de r tels que :} $$
$$
\forall \delta, 0 \le \delta \le d, \quad \tilde{\alpha}_{\delta} = \lambda P_{\tau\delta}(\lambda_1, \lambda_2, \dots, \lambda_{m(\tau)}) \quad \underline{\text{avec}} \\
r \equiv \sum_{\delta=0}^{d} \tilde{\alpha}_{\delta} (X-\theta)^{\delta} \mod.(X-\theta)^{d+1} . \quad \Box
$$

Remarquons qu'ici les $P_{\tau\delta}$ dépendent de $\tau$ **et** de $d$.

**Démonstration :**

Donnons d'abord une idée informelle de la preuve. Le programme le plus général contenant $\tau$ a/s dans $C(X)$ mod. $Cu\{X\}$ peut se mettre sous la forme suivante :

$$
\begin{align*}
Q_{\tau}^{+} : & s_{0} = X \\
s_{1} & = c_{1} + s_{0} \qquad m_{0,1} \\
s_{2} & = c_{2} + s_{0} \qquad m_{0,2} \ s_{1} \qquad m_{1,2} \\
s_{\tau} & = c_{\tau} + s_{0} \cdot s_{1}^{m_{0,\tau}} \ s_{\tau-1} \qquad m_{1,\tau-1} \\
s_{\tau+1} & = c_{\tau+1} \cdot s_{0}^{m_{0,\tau+1}} \ \dots \ s_{\tau} \qquad m_{\tau,\tau+1}
\end{align*}
$$

où les $c_i$, $1 \le i \le \tau+1$ sont dans $C$ et les $m_{ij}$, $1 \le j \le \tau+1$, $0 \le i \le j-1$ dans $Z$.

Tout programme du type $Q_{\tau}^{+}$ sera appelé un $\tau_{+}$-programme. On ne peut pas procéder comme dans le cas des m/d car, comme l'ont noté Borodin et Cook, on ne peut pas considérer un $\tau_{+}$-programme comme une instance d'un programme général ayant $\tau$ a/s et $v(\tau)$ m/d. En effet les m/d scalaires (du type $m_{t,i} \cdot s_i$) sont ici remplacées par des exponentiations ($s_i^{m_{ij}}$) qui représentent un nombre variable de m/d.

L'idée de Borodin et Cook [74] est d'interpréter les calculs comme
s'effectuant dans $C[[X-\theta]]/(X-\theta)^{d+1}$ où $\theta$ est différent des zéros et des
pôles des $s_i$ ; $C[[x-\theta]]/(x-\theta)^{d+1}$ est l'anneau quotient de $C[[x-\theta]]$ par
l'idéal engendré par $(x-\theta)^{d+1}$. Comme l'on s'intéresse en fait uniquement
au calcul des polynômes de $C[X]$ de degré $d$, donc aux $d+1$ premiers termes
des séries résultat, les résultats finaux sont les mêmes. Prenons l'exemple
d'un programme simple à 1 addition :

$$ \beta_0 : s_0 = X $$

$$ s_1 = c_1 + X $$

$$ s_2 = c_2(c_1+X)^{m_{12}} $$

et supposons $c_1 \neq 0$, $m_{12} \geq d$. Dans ce cas $0$ n'est ni un zéro ni un pôle des $s_i$, $0 \le i \le 2$, donc $\beta_0$ est exécutable dans $C[[X]]$.

Introduisons : $\lambda = c_2 c_1^{m_{12}} \cdot \frac{1}{d!}$, $\lambda_1 = \frac{1}{c_1}$, $\lambda_2 = m_{12}$.

Alors : 
$$ s_2 = \frac{1}{d!} c_2 c_1^{m_{12}} d! \left(1 + \frac{X}{c_1}\right)^{m_{12}} $$
$$ \equiv \lambda \left[ d! + d! \binom{\lambda_2}{1} \lambda_1 X + d! \binom{\lambda_2}{2} \lambda_1^2 X^2 + \dots + d! \binom{\lambda_2}{d} \lambda_1^d X^d \right] \mod (X^{d+1}) $$
$$ \equiv \lambda \left[ d! + d! \lambda_2 \lambda_1 X + \frac{d!}{2} \lambda_2 (\lambda_2 - 1) \lambda_1^2 X^2 + \dots \right. $$
$$ \left. + \lambda_2 (\lambda_2 - 1) \dots (\lambda_2 - d + 1) \lambda_1^d X^d \right] \mod. (X^{d+1}) $$

Soit : $s_2 \equiv \lambda \sum_{\delta=0}^{d} P_{\delta}(\lambda_1, \lambda_2) X^{\delta}$ avec $P_{\delta} \in Z[z_1, z_2]$ pour $0 \le \delta \le d$.

Par exemple : 
$P_0(z_1, z_2) = d!$
$P_1(z_1, z_2) = d! z_1 z_2$
$\vdots$
$P_d(z_1, z_2) = z_2 (z_2 - 1) \dots (z_2 - d + 1) z_1^d$

Il semble à priori que l'on obtient par cette méthode un ensemble de $P_{\delta}$ différent pour chacun des cas : $m_{12} \le -d$, $m_{12} = -d+1, \dots, m_{12} = 0, \dots, m_{12} = d-1$, $m_{12} \ge d$. C'est la conclusion à laquelle sont arrivés Borodin et Cook.

Remarquons cependant que dans le cas $0 \le m_{12} < d$ on peut prendre exactement les mêmes $P_{\delta}$ que dans le cas $m_{12} \ge d$. En effet, supposons :
$$ m_{12} = j \quad 0 \le j < d $$
Alors il est facile de voir qu'en prenant : $\lambda' = \frac{1}{d!} c_2 c_1^j, \lambda'_1 = \frac{1}{c_1}$,
$\lambda'_2 = m_{12} = j$ on obtient :

$$s_2 \equiv \lambda' \sum_{\delta=0}^{d} P_{\delta}(\lambda'_1, \lambda'_2) X^{\delta}$$

Il suffit de vérifier que : $P_{\delta}(\lambda'_1, \lambda'_2) = 0$ pour $j < \delta \le d$.

$$ 
\begin{array}{l}
\text{Or : } P_{\delta} = z_2(z_2-1)\cdots(z_2-\delta+1)z_1^{\delta} \quad \text{pour } 0 \le \delta \le d \\
\Rightarrow \quad P_{\delta}(z_1,j) = 0 \quad \text{pour } j < \delta.
\end{array}
$$

Par contre les polynômes $P_{\delta}$ sont différents pour $m_{12} < 0$ de ceux qu'on obtient pour $m_{12} \ge 0$ mais de même on peut prendre les mêmes $P_{\delta}$, $0 \le \delta \le d$, pour toutes les valeurs négatives de $m_{12}$.

L'idée pour obtenir un *seul* jeu canonique de $P_{\delta}$ est donc très simple. Il suffit de considérer tout $\tau_+$-programme dans $C(X)$ mod. $Cu\{X\}$ comme un calcul du type suivant :

$$ 
\begin{align*}
Q_{\tau}^{+} &: s_0 = X \\
s_1 &= c_1 + s_0 \stackrel{\mu_{01} - \nu_{01}}{=} \\
s_2 &= c_2 + s_0 \stackrel{\mu_{02} - \nu_{02}}{=} s_1 \stackrel{\mu_{12} - \nu_{12}}{=} \\
& \cdot \cdot \cdot \stackrel{\mu_{0\tau} - \nu_{0\tau}}{=} \cdot \cdot \cdot s_{\tau-1} \stackrel{\mu_{\tau-1,\tau} - \nu_{\tau-1,\tau}}{=} \\
s_{\tau} &= c + s_0 \stackrel{\mu_{\tau,\tau+1} - \nu_{\tau,\tau+1}}{=} \cdot \cdot \cdot s_{\tau-1} \stackrel{\mu_{\tau,\tau+1} - \nu_{\tau,\tau+1}}{=} \\
s_{\tau+1} &= c_{\tau+1} \cdot s_0 \stackrel{\mu_{0,\tau+1} - \nu_{0,\tau+1}}{=} \cdot \cdot \cdot s_{\tau} \stackrel{\mu_{\tau,\tau+1} - \nu_{\tau,\tau+1}}{=} 
\end{align*}
$$

avec $\mu_{ij}, \nu_{ij} \ge 0$ pour $1 \le j \le \tau+1$ et $0 \le i \le j-1$.

Nous en venons maintenant à la démonstration effective du lemme 7. La preuve est par récurrence sur $\tau$.
1) $\tau = 0$

Un $O_+$-programme est de la forme :

$$s_0 = X$$
$$s_1 = c_1 X^{\mu_{01}-\nu_{01}} \quad \text{avec } \mu_{01}, \nu_{01} \ge 0.$$

Soit : $\theta \neq 0$

$$s_1 \bmod ((X-\theta)^{d+1}) \equiv c_1 (X-\theta+\theta)^{\mu_{01}-\nu_{01}}$$
$$\equiv c_1 \theta^{\mu_{01}-\nu_{01}} \left[ 1 + \frac{X-\theta}{\theta} \right]^{\mu_{01}-\nu_{01}}$$

D'où :

$$s_1 \equiv c_1 \theta^{\mu_{01}-\nu_{01}} \left[ 1 + \sum_{\delta=1}^{d} \binom{\mu_{01}}{\delta} \left(\frac{X-\theta}{\theta}\right)^{\delta} \right]^{-1} \left[ 1 + \sum_{\gamma=1}^{d} \binom{\nu_{01}}{\delta} \left(\frac{X-\theta}{\theta}\right)^{\gamma} \right]$$

En posant : $\lambda = c_1 \theta^{\mu_{01}-\nu_{01}}$. $\frac{1}{(d!)^2}$ les $P_{0\delta}$ sont définis par :

$$(8) \quad \lambda \sum_{\delta=0}^{d} P_{0\delta}(z_1, z_2, z_3) (X-\theta)^{\delta} \equiv \lambda \left[ d! + \sum_{\gamma=1}^{d} \frac{d!}{\gamma!} z_2 (z_2-1) \cdots (z_2-\delta+1) z_1^{\delta} (X-\theta)^{\gamma} \right] \\
\qquad \cdot \left[ d! + \sum_{\delta=1}^{d} (-1)^{\gamma} d! \left( \sum_{\gamma=1}^{d} \frac{1}{\gamma!} z_3 (z_3-1) \cdots (z_3-\delta+1) z_1^{\delta} (X-\theta)^{\gamma} \right) \right] \quad \text{mod. } (X-\theta)^{d+1}$$

$$\text{avec : } \lambda_1 = \frac{1}{\theta}, \lambda_2 = \mu_{01}, \lambda_3 = \nu_{01}.$$

Donc :

$$\lambda \sum_{\delta=0}^{d} P_{0\delta}(z_1, z_2, z_3) (X-\theta)^{\delta} \equiv \lambda \left[ \sum_{\delta=0}^{d} Q_{0\delta}(z_1, z_2) (X-\theta)^{\delta} \right] \\ \cdot \left[ \sum_{\delta=0}^{d} R_{0\delta}(z_1, z_3) (X-\theta)^{\delta} \right]$$

$$\Rightarrow m(0) = 3 = (\tau+1)(\tau+3).$$
Il est clair que les $Q_{0\delta}$ sont dans $Z[z_1,z_2]$. Pour montrer que les $R_0$ sont dans $Z[z_1,z_3]$ (et non pas seulement dans $Q[z_1,z_3]$) il suffit de remarquer que dans le membre de droite de l'égalité (8), seuls doivent être pris en considération dans le terme qui est élevé à la puissance $\gamma$ les termes de degré en $(X-\theta) \le q$ avec : $q\gamma \le d$. Or :

$(q!)^\gamma \text{ divise } (q\gamma)! \text{ qui divise } d!$

Donc tous les coefficients des polynômes en $\overline{z}$ qui interviennent dans les termes $[\sum_{\delta=1}^{d} \frac{1}{\delta!} z_3(z_3-1)\dots(z_3-\delta+1)z_1^{\delta}(X-\theta)^{\delta}]^\gamma$ ont des dénominateurs qui divisent $d!$.

Il est clair également que les $P_{0\delta}$, $0\le\delta\le d$, ne dépendent que de $d$ et pas des coefficients $c_1, \mu_{01}$ et $\nu_{01}$.

Enfin : $P_{00} = (d!)^2 = (d!)^{2\tau+2} \quad (\tau = 0)$ et

$$ \deg_{z_1,z_2,z_3} P_{0\delta} = \max_{\delta_1, \delta_2} \left[ \deg_{z_1,z_2} Q_{0\delta_1} + \deg_{z_1,z_3} R_{0\delta_2} \right] = 2\delta \\ \delta_1 + \delta_2 = \delta $$

En effet trivialment : $\deg_{z_1,z_2} Q_{0\delta_1} = 2\delta_1$

D'autre part :

$$ \deg_{z_1,z_3} R_{0\delta_2} = 0 \text{ si } \delta_2 = 0 \\ = \max_{1 \le \gamma \le d} \deg_{z_1,z_3} \left( \sum_{\delta=0}^{d} Q_{0\delta}(z_1,z_3)(X-\theta)^\delta \right)^\gamma \text{ si } \delta_2 \ne 0 $$

en notant $S_\rho$ le coefficient de $(X-\theta)^\rho$ dans le polynôme $S$ en $X-\theta$.
On a :

$$
\deg_{z_1 z_3} \left( \sum_{\delta=0}^{d} Q_{0\delta} (z_1, z_3) (X-\theta)^{\delta} \right)_{\delta=2}^{\gamma} = \max \left[ \deg_{z_1 z_3} Q_{01}^{\gamma_1} \cdots Q_{0d}^{\gamma_d} \right]
$$

pour tous les $\gamma_1, \gamma_2, \dots, \gamma_d$ tels que :

$$
\gamma_1 + \gamma_2 + \dots + \gamma_d = \gamma \text{ et } \gamma_1 + 2\gamma_2 + \dots + d\gamma_d = \delta_2.
$$

Soit :

$$
\begin{align*}
\deg_{z_1 z_3} \left( \sum_{\delta=0}^{d} Q_{0\delta} (z_1, z_3) (X-\theta)^\delta \right)_{\delta=2}^\gamma &= 2[\gamma_1 + 2\gamma_2 + \dots + d\gamma_d] = 2\delta_2 \\
\Rightarrow \deg_{z_1 z_3} P_{0\delta_2} &= 2\delta_2 \quad \text{et :}
\end{align*}
$$

$$
\deg_{z_1 z_2 z_3} P_{0\delta} = 2(\delta_1 + \delta_2) = 2\delta
$$

$$
\text{Soit finalement :} \quad \max_{0 \le \delta \le d} \deg_Z P_{0\delta} = 2d \le (d+1)^{2(\tau+1)} + 2(d+1)^2 \quad (\tau = 0)
$$

2) Hypothèse d'induction

Le lemme 7 est vrai pour tout $j \le \tau-1$. De plus les éléments
$\lambda, \lambda_1, \lambda_2, \dots, \lambda_m(j)$ pour tout $j$, $0 \le j \le \tau-1$, pour tout $r \in E_+(j,d)$ et pour
tout $\theta \notin F_r$, peuvent être choisis en conformité avec les principes
suivants :

Soit $\beta_r$ un $\tau_+$-programme calculant $r \in E_+(\tau)$ :

<figure><img src="image_3.png" /></figure>
Alors si l'on ordonne les éléments de l'ensemble $S = \{\theta, \mu_{01}, \nu_{01}, c_1, \mu_{02}, \nu_{02}, \mu_{12}, \nu_{12}, c_2, \dots, \mu_{j,j+1}, \nu_{j,j+1}\}$ comme l'indique le fléchage ci-dessus :

a) $\lambda_i$, $1 \le i \le m(j) = (j+1)(j+3)$, correspond au i-ième élément de la liste $S$ et la correspondance a les propriétés suivantes :
(on voit facilement que $S$ a $m(j)$ éléments).

$$ 
\begin{array}{l@{\qquad}l}
\text{b) } \lambda_1 = \frac{1}{\theta} & \\
\qquad \mu_{ik} \rightarrow \lambda_{t(i,k)} = \mu_{ik} & \text{pour : } 1 \le k \le j+1 \text{ et } 0 \le i \le k-1 \\
\qquad \nu_{ik} \rightarrow \lambda_{t(i,k)+1} = \nu_{ik} & \\
\text{c) Pour : } 1 \le i \le j & \\
\qquad c_i \rightarrow \lambda_{u(i)} = h(\lambda_1, \lambda_2, \dots, \lambda_{u(i)-1}, c_i) &
\end{array}
$$

en d'autres termes $\lambda_{u(i)}$ qui est associé à $c_i$ ne dépend que de $\theta$, $c_i$ et des $\mu, \nu, c$ qui sont avant $c_i$ dans la liste $S$. Exemple :

$$ c_1 \rightarrow \lambda_4 = \frac{1}{\left[ c_1 + (\theta)^{\mu_{01} - \nu_{01}} \right]} = \frac{1}{\left[ c_1 + \left( \frac{1}{\lambda_1} \right)^{\lambda_2 - \lambda_3} \right]} $$

d) $c_{j+1}$ n'intervient que dans $\lambda$. $\square$

**Remarque** : Ces propriétés des $(\lambda_i)$ sont vérifiées pour $j = 0$ puisque dans

$$ \text{ce cas : } \lambda = c_1 \frac{\theta^{\mu_{01} - \nu_{01}}}{(d!)^2}, \quad \lambda_1 = \frac{1}{\theta}, \quad \lambda_2 = \mu_{01}, \quad \lambda_3 = \nu_{01}. \quad \square $$

Soit : $j = \tau$ et soit $\beta_r$ un $\tau_+$-programme calculant $r \in E_+(\tau)$. Posons :
$\mu_{ij} - \nu_{ij} = \pi_{ij}$, $\tau - 1 = \rho$. On a :
$$
r = c_{\tau+1} \cdot s_0^{\pi_0, \tau+1} \cdots s_{\tau-1}^{\pi_{\tau-1}, \tau+1} \left( c_{\tau} + s_0^{\pi_0, \tau} \cdots s_{\tau-1}^{\pi_{\tau-1}, \tau} \right)^{\pi_{\tau}, \tau+1}
$$

soit

$$
(9) \quad r = b (c_{\tau} + e)^{\pi_{\tau}, \tau+1}
$$

où b et e sont dans E+(τ-1).

D'après l'hypothèse d'induction pour tout θ en dehors des zéros et
des pôles des sᵢ, 0≤i≤ρ, il existe des éléments :

$$
\eta, \eta_1, \eta_2, \dots, \eta_m(\rho) - 2\tau, \eta'_m(\rho) - 2\tau + 1 = \mu_{0,\tau}
$$

$$
\eta_{m}(\rho) - 2\tau + 2 = \nu_{0,\tau}, \dots \eta_{m}(\rho) - 1 = \mu_{\rho,\tau}, \eta'_{m}(\rho) = \nu_{\rho,\tau}
$$

$$
\eta', \eta'_m(\rho) - 2\tau + 1 = \mu_{0,\tau+1}, \eta'_m(\rho) - 2\tau + 2 = \nu_{0,\tau+1}
$$

$$
\dots, \eta'_{m}(\rho) - 1 = \mu_{\rho, \tau+1}, \eta'_{m}(\rho) = \nu_{\rho, \tau+1}
$$

tels que l'on ait pour e et b qui sont dans $C[[X-\theta]]$ :

$$
(10) \quad e \equiv \eta \sum_{\delta=0}^{d} P_{\rho\delta} (n_1, n_2, \dots, n_{m(\rho)}) (X-\theta)^{\delta} \quad \mod (X-\theta)^{d+1}
$$

$$
(11) \quad b \equiv \eta' \sum_{\delta=0}^{d} P_{\rho\delta} (n_1, n_2, \dots, n_{m(\rho)} - 2\tau, n'_{m(\rho)} - 2\tau + 1, \dots, n'_{m(\rho)}) (X-\theta)^{\delta} \quad \mod (X-\theta)^{d+1}
$$

Donc pour tout θ ∉ F_r u{zéros et pôles de s_τ} r est dans C[[X-θ]] et
l'on a :

$$
r \bmod (X-\theta)^{d+1} \equiv \lambda \sum_{\delta=0}^{d} P_{\tau\delta}(\lambda_1, \lambda_2, \dots, \lambda_s) (X-\theta)^{\delta}
$$

$$
où \lambda = \eta'(c_{\tau} + \eta P_{\rho 0})^{\pi_{\tau}, \tau+1} \cdot \frac{1}{(d!)^2} = \frac{\eta'}{(d!)^2} (c_{\tau} + \eta(d!)^{2\tau})^{\pi_{\tau}, \tau+1}
$$
$$ 
\begin{aligned}
s &= m(\rho) + 2\tau + 3 \\
  &= (\tau - 1 + 1)(\tau - 1 + 3) + 2\tau + 3 = \tau^2 + 4\tau + 3 = (\tau + 1)(\tau + 3) = m(\tau)
\end{aligned}
$$

et où les $P_{\tau\delta}$, $0\le\delta\le d$, sont définis par :

$$ \sum_{\delta=0}^{d} P_{\rho\delta}(z_1, z_2, \dots, z_{m(\tau)}) (X-\theta)^{\delta} = Q_1 Q_2 Q_3 \quad \text{avec, d'après (9), (10) et (11):} $$

$$ Q_1 = \sum_{\delta=0}^{d} P_{\rho\delta}(z_1, z_2, \dots, z_{m(\rho)-2\tau'}, z_{m(\rho)+2}, z_{m(\rho)+3}, \dots, z_{m(\rho)+2\tau+1}) (X-\theta)^{\delta} $$

$$ Q_2 = d! + \sum_{s=1}^{d} \frac{d!}{s!} \left( \sum_{\delta=1}^{d} P_{\rho\delta}(z_1, z_2, \dots, z_{m(\rho)}) (X-\theta)^{\delta} \right)^s \left[ \left( \sum_{\delta=1}^{d} P_{\rho\delta}(z_1, z_2, \dots, z_{m(\rho)}) (X-\theta)^{\delta} \right)^s \right] $$

$$ Q_3 = d! + \sum_{s=1}^{d} (-1)^s \left[ \left( \sum_{s=1}^{d} \frac{1}{s!} \left( z_{m(\rho)} + 2\tau + 3 \right) \right) \left[ z_{m(\rho)} + 1 \right] \right]^s \left( \sum_{\delta=1}^{d} P_{\rho\delta}(z_1, \dots, z_{m(\rho)}) (X-\theta)^{\delta} \right)^s $$

$$ \text{et : } \lambda_1 = \eta_1, \lambda_2 = \eta_2, \dots, \lambda_{m(\rho)} = \eta_{m(\rho)} $$

$$ \lambda_{m(\rho)+1} = \frac{1}{c_{\tau} + nP_{\rho 0}} = \frac{1}{c_{\tau} + n(d!)^{2\tau}} $$

$$ \lambda_{m(\rho)+2} = \eta'_{m(\rho)} - 2\tau + 1 = \mu_{0,\tau+1} $$

$$ \lambda_{m(\rho)+3} = \eta'_{m(\rho)} - 2\tau + 2 = \nu_{0,\tau+1} $$

$$ \lambda_{m(\rho)+2\tau+1} = \eta'_{m(\rho)} = \nu_{\rho,\tau+1} = \nu_{\tau-1,\tau+1} $$

$$ \lambda_{m(\rho)+2\tau+2} = \mu'_{\tau,\tau+1} \quad \text{et} \quad \lambda_{m(\rho)+2\tau+3} = \nu_{\tau,\tau+1} $$

1) Il est clair que les $P_{\tau\delta}$ ne dépendent pas de $\theta$ et des coefficients $c_i, \mu_{ij}, \nu_{ij}$ donc qu'ils ne dépendent que de $d$ et de $\tau$. Il faut montrer qu'ils sont dans $Z[\overline{z}]$. Il suffit de montrer cela que les polynômes
en $\bar{z}$ qui sont coefficients des termes en X-θ de degré $\le d$ dans :

$$d! \left[ \sum_{s=1}^{d} \frac{1}{s!} \left( z_{m(\rho)+2\tau+3}^{s} (z_{m(\rho)+1})^{s} \left( \sum_{\delta=1}^{d} P_{\rho\delta}(z_1, \dots, z_{m(\rho)}) (X-\theta)^{\delta} \right)^s \right) \right] t$$

ont des coefficients entiers. Le raisonnement est exactement le même que dans le cas : $\tau = 0$.

$$2) P_{\tau 0}(z_1, \dots, z_{m(\tau)}) = P_{\rho 0}(d!)^2 = (d!)^{2(\tau-1)+2} (d!)^2 = (d!)^{2\tau+2}$$

$$3) \max_{0 \le \delta \le d} \deg P_{\tau \delta} \le (\max_{0 \le \delta \le d} \deg P_{\rho \delta})(1+d)+2d + (2d+d) \max_{0 \le \delta \le d} \deg P_{\rho \delta})d$$

$$\le (\max_{0 \le \delta \le d} \deg P_{\rho \delta})(d^2+d+1)+2d^2+2d$$

$$\le [(d+1)^{2\tau} + 2(d+1)^{2(\tau-1)} + \dots + 2(d+1)^2](d+1)^2 + 2(d+1)^2$$

$$\le (d+1)^{2\tau+2} + 2(d+1)^{2\tau} + \dots + 2(d+1)^2$$

4) Les conditions sur les $\lambda_i$ sont trivialment vérifiées. Ce qui termine la démonstration du lemme 7. $\square$

Procédant comme dans le cas des m/d avec ici :

$$m = (\tau+1)(\tau+3) \le 2\tau^2$$

$$c \le (d+1)^{2(\tau+1)} + 2(d+1)^{2\tau} + \dots + 2(d+1)^2 \le 2(d+1)^{2(\tau+1)} \le d^{3\tau} \quad \text{pour d et } \tau \\ \text{suffisamment grands.}$$

On obtient le :

**Lemme 8 :** Si $g$ est un entier tel que :

$$(12) \quad g^{d-2\tau^2-1} \ge (d^{3\tau})^{2\tau^2}.d^d, \text{ et si } d \text{ et } \tau \text{ sont suffisamment grands il existe une forme } H \text{ de degré } g \text{ dans } \mathbb{Z}[y_1, y_2, \dots, y_d] \text{ telle que pour tout} \\ r = \sum_{\delta=0}^{d} \alpha_{\delta} X^{\delta} \text{ dans } E_{+}(\tau) : \\ H(\alpha_1, \alpha_2, \dots, \alpha_d) = 0 \quad \square$$
**Lemme 9 :**

Soit $r = \sum_{i=1}^{d} \beta_i x^i$ un polynôme de $Z[X]$, $0 \le \beta_i \le M$. Alors :

$$L(\pm/r) \le c_{01}(\pm/d) \cdot (\log_2 M + 1) + \log_2 M \\ \le (2 \log_2 M) c_{01}(\pm/d)$$

pour $d$ assez grand. $\square$

Nous pouvons démontrer maintenant le

**Théorème 3 :**

Il existe une constante $c_2 > 0$ telle que pour tout entier $d \ge 2$ :

$$c_{01}(\pm/d) \ge \frac{d^{1/3}}{c_2 \log_2 d} \quad \square$$

**Démonstration :**

La condition (12) est satisfaite si :

$$ (13) \quad g \ge d^{(6\tau^3/d)+1} \quad \text{et} \quad 2\tau^2 < d-1. $$

On sait donc qu'il existe $r_0 = \sum_{i=1}^{d} \beta_i x^i \in Z_+[X]$ avec $0 \le \beta_i \le d^{(6\tau^3/d)+1}$

tel que :

$$ L(\pm/r_0) > \tau \quad (\text{lemme 8} + \text{lemme 5}). $$

Donc (lemme 9) :

$$ c_{01}(\pm/d) \ge \max_{2\tau^2 < d-1} \frac{\tau}{2\left(\frac{6\tau^3}{d}+1\right) \log_2 d} $$

pour $d$ assez grand. $\square$

$$ \text{Soit : } c_{01}(\pm/d) \ge \frac{d^{1/3}}{13 \log_2 d} \quad \square $$
2.4. Borne inférieure pour le nombre total d'opérations :

Nous allons montrer qu'il existe des polynômes de $Z_{01}^d[X]$ qui requièrent $\Omega(d^{1/2}/\log_2 d)$ opérations (m/d+ a/s) pour leur évaluation dans $C(X) \bmod. Cu\{X\}$.

Aussi bien dans le cas des m/d que dans celui des a/s, nous nous sommes fondés pour établir des bornes inférieures sur la complexité des polynômes à coefficients 0-1 sur une formule fondamentale du type suivant :

$$ (14) \quad g^{d-m(\tau)-1} \ge [f(d,\tau)]^{\mathfrak{M}(\tau)} d^d $$

cù $\tau$ est le nombre de m/d (resp. a/s), $m(\tau)$ est à une constante multi-plicative près le nombre de paramètres introduits dans un programme type contenant $\tau$ m/d (resp. a/s), et $f(d,\tau)$ est le Sup. des degrés des $P_{\tau i}$ (cf. Lemmes 2 et 7).

Dans les deux cas on a établi des majorations du type :

$m(\tau) \le c_1 \tau^\mu \quad f(d,\tau) \le d^{c_2 \tau^\nu}$ où $c_1$ et $c_2$ sont des constantes positives et $\mu$ et $\nu$ des entiers $\ge 1$, et on en a déduit par un argument dû à Lipton une borne inférieure pour $c'_{01}(*/d)$ (resp. $c'_{01}(\pm/d)$)

en $\Omega(d^{\mu+\nu}/\log_2 d)$.
Nous utilisons la même approche pour montrer une borne inférieure sur $c_{01}(d)$. Rappelons que par définition :

$$c_{01}(d) = \max_{p \in \mathbb{Z}_{01}^d [X]} [L(p)]$$

Informellement le nombre de paramètres dans un programme type contenant $\tau$ opérations (m/d + a/s) est en $\tau^2$ ($\mu=2$). Le Sup. des degrés des $P_{\delta_i}$ est en $d^{c_2\tau}$ ($v=1$). On ne devrait donc obtenir pour le nombre total d'opérations, comme dans les autres cas, qu'une borne inférieure en $\Omega(\frac{d^{1/3}}{\log_2 d})$.

Mais en remarquant que dans le programme type, $c'\tau$ au plus parmi les $c\tau^2$ paramètres sont $\neq 0$, on peut montrer que "tout se passe comme s'il" n'y avait que de l'ordre de $\tau$ paramètres ($\mu=1$) ce qui permet d'obtenir une borne inférieure en $\Omega(\frac{\tau^{1/2}}{\log_2 d})$ pour $c_{01}(d)$.
**Lemme 10 :**

Soient $d$ et $\tau$ entiers positifs, $E(\tau,d) = \{p \in \mathbb{C}_d[X] \text{ tels que :}$
$L(p) \le \tau\}$. Il existe des constantes positives $c_1$ et $c_2$ telles que :

Si $d$ et $\tau < d$ sont suffisamment grands et si $g$ entier est tel
que :
$$g^{d-m(\tau)-1} \ge [f(d,\tau)]^{m(\tau)} d^d$$

avec $m(\tau) \le c_1 \tau$, $f(d,\tau) \le d^{c_2 \tau}$ ($c_1$ et $c_2$ constantes positives)

Il existe une forme $H$ de degré $g$ dans $Z[y_1, y_2, \dots, y_d]$ telle que :
$H(\alpha_1, \alpha_2, \dots, \alpha_d) = 0$ pour tout $p = \sum_{i=1}^{d} \alpha_i X^i \in E(\tau, d)$. $\square$

Admettons le lemme 10 pour le moment. On en déduit le

**Théorème 4**

Il existe une constante $c > 0$ telle que :
$$c_{01}(d) \ge \frac{d^{1/2}}{c \log_2 d} \quad \square$$

La démonstration est analogue à celle des théorèmes 1, 2 et 3.
L'idée générale est celle qu'on a rappelée au début du paragraphe. On
a ici d'après le lemme 10 : $\mu = 1$, $\nu = 1$.

La démonstration du lemme 10 utilise le lemme suivant :

**Lemme 11 :**

Soient $m \ge 1$, $1 \le m' \le m$, $c \ge 2$, $q \ge 2$ des entiers, $z_1, z_2, \dots, z_m$
des indéterminées sur $Z$, k un corps, $P_1, P_2, \dots, P_q$ des polynômes de
$Z[z_1, z_2, \dots, z_m]$ avec : $\max \deg(P_\delta) \le c$.
$1 \le \delta \le q$
Si $g$ entier naturel est tel que :

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

il existe une forme $H$ de degré $g$ dans $Z[y_1, \dots, y_q]$ telle que pour tout
$\bar{\lambda} = (\lambda_1, \lambda_2, \dots, \lambda_m) \in k^m$ tel que $m'$ des $\lambda_i$ au plus soient $\ne 0$ :

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

**Démonstration :**

Elle calque celle du lemme 2.3. de Strassen ([74], P133).

Soit : $\Lambda_m = \{\bar{\lambda} \in k^m \text{ tels que } m' \text{ au plus des } \lambda_i \text{ soient } \neq 0\}$

Soit à démontrer : $\exists b_{i_1 i_2 \dots i_q}^\lambda$ entiers non tous nuls tels que :

$$ \sum_{i_1+i_2+\dots+i_q = g} b_{i_1 i_2 \dots i_q} P_1^{i_1} P_2^{i_2} \dots P_q^{i_q} (\bar{\lambda}) = 0 \text{ pour tout } \bar{\lambda} \in \Lambda_m $$

$$ \text{Soit : } Q = \sum_{i_1+i_2+\dots+i_q = g} B_{i_1 i_2 \dots i_q} P_1^{i_1} \dots P_q^{i_q} (\bar{z}) \in Z[\bar{B}, \bar{z}] $$

Les notations sont celles de Strassen (cf. Annexe I).

Les coefficients de $Q$ en tant que polynômes en $\bar{z}$ sont des formes linéaires de $Z[\bar{B}]$, c'est-à-dire à coefficients entiers en $\binom{g+q-1}{q-1}$ variables. Tout produit de $j \ge (m'+1)$ composantes d'un $\bar{\lambda} \in \Lambda_m$, est nul par définition. Par conséquent il suffit de montrer que les formes linéaires associées ont un zéro entier non trivial commun. Comme il y a $\le \binom{m}{m'} (g^c + m')$ telles formes il suffit pour cela que :

$$ \binom{m}{m'} (g^c + m') < \binom{g+q-1}{q-1} $$
Supposons le contraire :

$$
\begin{align*}
(16) \quad \left(\begin{array}{c} m \\ m' \end{array}\right) \left(\begin{array}{c} gc + m' \\ m' \end{array}\right) &\ge \left(\begin{array}{c} g + q-1 \\ q-1 \end{array}\right) \\
&\quad - \left(\begin{array}{c} 3+q-1 \\ q-1 \end{array}\right) > \left(\begin{array}{c} g \\ q \end{array}\right)^{q-1} \quad \text{puisque } g \ge 2, q \ge 2 \\
&\quad \left(\begin{array}{c} gc + m' \\ m' \end{array}\right) \le (gc)^{m'} + 1 \quad \text{puisque } m' \ge 1, c \ge 2, g \ge 2 \text{ d'après (15).}
\end{align*}
$$

Donc :

$$
\begin{align*}
(16) \Rightarrow \binom{m}{m'} [(gc)^{m'} + 1] &> \left(\frac{g}{q}\right)^{q-1} \\
\Rightarrow \binom{m}{m'} (gc)^{m'} q^q &> g^{q-1} \quad \text{puisque } q \ge 2
\end{align*}
$$

ce qui contredit (15). $\square$

Démonstration du lemme 10 :

Dans la suite les $c_i$, $1 \le i \le 6$, sont des constantes positives. Un calcul $\beta_\tau$ contenant $\tau$ opérations (m/d + a/s) dans $C(X)$ mod. $Cu\{X\}$ peut être mis sous la forme générale $Q_r^*$ du lemme 2.

$$
\begin{align*}
Q_r^* : s_{-1} &= 1 \\
s_0 &= X \\
\text{pour } t &= 1, \dots, \tau \\
s_t &= \left( \sum_{i=-1}^{t-1} m_{ti} s_i \right) \cdot \left( \sum_{i=-1}^{t-1} m'_{t,i} s_i \right) \div \left( \sum_{i=-1}^{t-1} m''_{t,i} s_i \right) \\
s_{\tau+1} &= \sum_{i=-1}^{\tau} m_{\tau+1,i} s_i
\end{align*}
$$

$Q_r^*$ contient $\le c_3 \tau^2$ paramètres $m_{ti}, m'_{ti}, m''_{ti}$. Parmi ceux-là au plus $c_4 \tau$ sont $\ne 0$, puisqu'il n'y a que $\tau$ opérations au total. Nous avons vu en 2.2 qu'il existe des polynômes $P_\delta$, $1 \le \delta \le d$, dans $Z[y_1, y_2, \dots, y_d]$ dont
les coefficients ne dépendent que de $d$ et dont le degré est majoré par $d^{3\tau}$,
et des complexes $\lambda, \lambda_1, \lambda_2, \dots, \lambda_m$ avec $m \le 4 \tau^2$ tels que les coefficients
$\tilde{\alpha}_\delta$ de la série r calculée par $Q_r^*$ dans un $C[[x-\theta]]$ convenablement choisi
satisfont :

$$
\tilde{\alpha}_{\delta} = \lambda P_{\delta}(\lambda_1, \lambda_2, \dots, \lambda_m) \quad \text{pour } 1 \le \delta \le \infty.
$$

En fait, il est facile de voir (Strassen [74], lemme 2.4., P 134)
que les $\lambda_i$ sont à l'exception de $c_5\tau$ d'entre eux des éléments de l'ensemble
$\{m_{ti}, m'_{ti}, m''_{ti}\}$. Par conséquent au plus $c_6\tau$ sont $\ne$ 0. Il suffit alors
d'appliquer le lemme 11 avec :

$$
q = d, m \le c_3 \tau^2, m' \le c_6 \tau, c = d^{3\tau}
$$

Nous obtenons : si $g$ entier naturel est tel que :

$$
(17) \quad g^{d-c_6\tau-1} \ge \binom{c_3\tau^2}{c_6\tau} (d^{3\tau})^{c_6\tau} d^d
$$

il existe une forme H de degré g telle que :

$$
H(\tilde{\alpha}_1, \tilde{\alpha}_2, \dots, \tilde{\alpha}_d) = 0
$$

Ce qui conduit par le raisonnement habituel à :

Si $g$ satisfait (17), $\exists H$, $\deg(H) = g$, telle que :

$$
\forall p \in E(\tau, d), p = \sum_{i=1}^{d} \alpha_i^p X^i, H(\alpha_1, \alpha_2, \dots, \alpha_d) = 0
$$

Or (17) sera satisfaite si : $g^{d-m(\tau)-1} \ge [f(d,\tau)]^{m(\tau)} d^d$ avec $m(\tau) = c_6^\tau$
et $[f(d,\tau)]^{m(\tau)} \le (c_3^2 \tau^2)^{c_6^\tau} \cdot (d^{3\tau})^{m(\tau)}$. Soit $f(d,\tau) \le (c_3^2 \tau^2) d^{3\tau} \le d^{4\tau}$
puisque $\tau < d$ si $d$ et $\tau$ sont suffisamment grands. D'où le lemme 10
avec : $c_1 = c_6$ et $c_2 = 4$. $\square$
### 3. Bornes inférieures pour la complexité des polynômes en plusieurs variables à coefficients 0-1 :

#### Polynômes généraux et formes multilinéaires

3.1. Les résultats que nous avons obtenus dans la deuxième partie pour les polynômes à une variable peuvent se généraliser pour les polynômes à plusieurs variables.

### Théorème 5

Soit $c_{01}(N,d)$ (resp. $c_{01}(\pm/N,d)$, $c'_{01}(\*/N,d)$) la complexité maximale totale (resp. additive, multiplicative non scalaire) des polynômes de $C[X_1, X_2, \dots, X_N]$ de degré $\le d$ en $N$ variables à coefficients 0-1 dans $C(X_1, X_2, \dots, X_N)$ mod. $CU\{X_1, X_2, \dots, X_N\}$. Alors :

$$c_{01}(N,d) = \Omega\left(\binom{d+N}{N}^{1/2} / \log_2 \binom{d+N}{N}\right)$$ $$c_{01}(\pm/N,d) = c'_{01}(\*/N,d) = \Omega\left(\binom{d+N}{N}^{1/3} / \log_2 \binom{d+N}{N}\right) \quad \square$$

### Démonstration :

Il suffit d'appliquer la méthode que l'on a exposée dans le deuxième paragraphe. Prenons le cas par exemple des m/d non scalaires.

On obtient une formule analogue à la formule (14) ci-dessus, où d est remplacé par $\binom{N+d}{N}$, le nombre de monômes distincts dans le polynôme le plus général de degré $d$ en $N$ variables ; il est facile de voir que le nombre de paramètres introduits par un programme type contenant $\tau$ m/d non scalaires est en $O(\tau^2 + N\tau)$, soit $m(\tau) \le c_1\tau^2$ pour $\tau \ge N$, et que le maximum $f(d,N,\tau)$ des degrés des $P_{\tau i}$, $1 \le i \le \binom{N+d}{N}-1$, ne dépend pas de $N$, soit $f(d,N,\tau) = f(d,1,\tau) \le d^{c_2\tau}$. D'où le résultat $\square$.

Si l'on se restreint en particulier aux formes multilinéaires de $(C^N)^d$ dans $C, \sum_i \lambda_{i_1 i_2 \dots i_d} X_1^{i_1} \dots X_d^{i_d}$ (les $i_j$ sont des indices de variables et
non des exposants) on obtient des bornes inférieures en $\Omega(N^{d/2}/d\log_2 N)$ et $\Omega(N^{d/3}/d \log_2 N)$, le nombre de monômes distincts dans la forme multi-linéaire la plus générale de degré d en N variables étant $N^d$.

### 3.2. Formes linéaires.

Pour les formes linéaires la méthode fournit un résultat asymptotiquement optimal. En effet on peut dans ce cas se restreindre aux programmes linéaires ce qui permet d'obtenir des bornes supérieures bien meilleures pour le nombre de paramètres et le degré maximum des $P_{\tau i}$.

Un programme linéaire dans $\mathcal{L}_C[X_1, X_2, \dots, X_d]$ mod. $\mathrm{Cu}\{X_1, X_2, \dots, X_d\}$ est une suite de formes linéaires $\in \mathcal{L}_C[X_1, X_2, \dots, X_d]$ $\ell_1, \ell_2, \dots, \ell_s$ telle que tout $\ell_i, 1 \le i \le s$, est ou bien $X_j, 1 \le j \le d$, ou bien de l'une des formes : $\ell_i = k \ell_j$ avec $k \in \mathbb{C}, j < i$ ou $\ell_i = \ell_j + \ell_k$ avec $j, k < i$.

On sait (cf Borodin et Munro [75], Théorème 2.5.3. P 35) que les programmes linéaires sont asymptotiquement optimaux pour calculer les formes linéaires. La borne inférieure asymptotique que nous mettons en évidence ci-dessous pour la complexité linéaire est donc valable également dans $C(X_1, X_2, \dots, X_d)$ mod. $\mathrm{Cu}\{X_1, X_2, \dots, X_d\}$.

Soit $c_{01}^\ell(d',d)$ la complexité maximale des ensembles de d' formes linéaires à coefficients 0-1 en d variables dans $\mathcal{L}_C[X_1, X_2, \dots, X_d]$ mod. $\mathrm{Cu}\{X_1, X_2, \dots, X_d\}$.

**Théorème 6 :**

Il existe une constante $c > 0$ telle que :

$$c_{01}^\ell(d',d) \ge \frac{d'd}{c \log_2(d'd)} \quad \text{et ce résultat est asymptotiquement optimal.}$$

**Démonstration :**

Un programme linéaire contenant $\tau$ opérations est du type :

$$ \beta_{\tau}: s_{-d} = 1, s_{-d+1} = X_1, \dots, s_0 = X_d, \text{ pour } t = 1 \text{ jusqu'à } \tau \\ s_t = \sum_{i=-d}^{t-1} m_{ti} s_i $$
Ce programme contient $\sum_{t=1}^{\tau} (d+t-1) = \tau d + \frac{\tau(\tau-1)}{2}$ paramètres mais $2\tau$ au plus d'entre eux sont $\neq 0$.

Par ailleurs les coefficients des formes linéaires calculées par $\beta_{\tau}$ s'expriment polynomialement en fonction de ces paramètres. Le degré des polynômes $P_i$ qui ne dépendent que de $\tau$ qui expriment ces dépendances est majoré par $2\tau$ ; en effet une addition n'augmente pas le degré et une multiplication scalaire l'augmente de 1.

Si $E_{\tau}(d',d)$ est l'ensemble des ensembles de $d'$ formes linéaires de $\mathcal{L}_C[X_1, X_2, \dots, X_d]$ calculables dans $\mathcal{L}_C[X_1, \dots, X_d] \mod. \text{Cu}\{X_1, X_2, \dots, X_d\}$ avec $\leq \tau$ opérations on obtient (lemme 11) :

Soit $g$ entier naturel tel que :

$$ (18) \quad g^{dd'-2\tau-1} \ge \left( \frac{\tau d + \frac{\tau(\tau-1)}{2}}{2\tau} \right) (2\tau)^{2\tau} (dd')^{dd'} $$

il existe une forme $H$ de degré $g$ telle que :

$$ H(\alpha_1, \alpha_2, \dots, \alpha_{dd'}) = 0 $$

pour tout élément $M$ de $E_{\tau}(d',d)$ représenté par la matrice :

$$ \begin{pmatrix} \alpha_1 & \alpha_2 & \dots & \alpha_d \\ \alpha_{d+1} & \dots & \alpha_{2d} & \\ \alpha_{d'(d-1)+1} & \dots & \alpha_{d'd} & \end{pmatrix} $$

Si $|M|$ est le plus grand élément de la matrice $M = (\alpha_i)$ avec $\alpha_i \ge 0$, et si $L(\pm/M)$ est la complexité additive de l'ensemble de formes linéaires $M$ il est facile de voir que :

$$ (19) \quad L(\pm/M) \le c_{01}^{\ell}(d',d) \cdot 2 \log_2(|M|) $$
D'où (argument usuel +(18) et (19)) :

$$c_{01}^{l}(d', d) \geq \sup_{0 < \tau < \frac{dd'-1}{2}} \frac{\tau}{(\frac{7}{dd'} + 1) \log_2 dd'}$$

$$\Rightarrow c_{01}^{l}(d', d) \geq \frac{dd'}{c \log_2 dd'} \quad \square$$

**Remarque :**

1). Le point important ici est que le nombre de paramètres "actifs" est $\leq 2\tau(\mu=1)$ et que le degré des $P_i$ est borné par $2\tau$ également ($\Rightarrow \nu=0$) $\Rightarrow \mu + \nu = 1$.

2). Nous avons mis en évidence des bornes inférieures pour la complexité multiplicative des formes multilinéaires à coefficients 0-1 et pour la complexité totale des ensembles de formes linéaires à coefficients 0-1. Il est intéressant de constater que l'on peut relier ces deux complexités. C'est ce que nous allons faire dans la quatrième partie de cet article en partant d'une caractérisation nouvelle de la complexité multiplicative non scalaire d'un ensemble de polynômes en plusieurs variables.

## 4. Bornes inférieures pour la complexité multiplicative non scalaire des formes multilinéaires à coefficients 0-1 :

### 4.1. Introduction

Nous étudions dans ce paragraphe la complexité multiplicative des formes multilinéaires de degré d, applications de $(C^N)^d$ dans C. Nous relions cette complexité à la complexité totale de $N^{d/2}$ formes linéaires en $N^{d/2}$ variables. Ceci ne nous permet pas d'obtenir pour la complexité des formes multilinéaires à coefficients 0-1 une borne inférieure meilleure que celle que l'on a mise en évidence au paragraphe précédent. Par contre nous montrons que si l'on peut construire un ensemble de $N^{d/2}$
formes linéaires en $N^{d/2}$ variables à coefficients 0-1 dont le calcul requiert $\Omega(N^d/d \log_2 N)$ opérations, dans $C(X_1, X_2, ..., X_N \mod{N^d/2})$ mod. $Cu\{X_1, ..., X_N \mod{N^d/2}\}$ (il en existe d'après le paragraphe précédent), alors on pourra construire une forme multilinéaire de degré d en $N$ variables dont le calcul requiert $\Omega[(\lambda N)^{d/6-2}] \text{ m/d non scalaires dans } C(Y_1, ..., Y_{Nd}) \mod{Cu\{Y_1, Y_2, ..., Y_{Nd}\}}$. ($\lambda$ constante >0).

## 4.2. Nouvelle caractérisation de la complexité multiplicative non scalaire d'une famille de polynômes homogènes.

Nous nous ramenons d'abord au cas où le programme n'utilise pas de division par le lemme suivant :

**Lemme 12 :** (Strassen [73])

**Soient $P_1, P_2, ..., P_m \in C[X_1, X_2, ..., X_k]$, $L'(*/P_1, P_2, ..., P_m)$ le nombre minimum de m/d non scalaires nécessaires pour évaluer $P_1, P_2, ..., P_m$ dans $C(X_1, X_2, ..., X_k) \mod{Cu\{X_1, X_2, ..., X_k\}}$, $L(x/P_1, P_2, ..., P_m)$ le nombre minimum de multiplications non scalaires nécessaires à un programme ne comportant pas de divisions et calculant $P_1, P_2, ..., P_m$ alors :**

$$ L'(*/P_1, P_2, \dots, P_m) \ge \frac{2L(x/P_1, P_2, \dots, P_m)}{\max_{i} [\deg(P_i)] (\max_{i} [\deg(P_i)] - 1)} \quad \square $$

En fait les formes multilinéaires sont des polynômes homogènes de degré d, et nous allons considérer des programmes "homogènes". Un programme $\beta$ sera dit homogène de degré d si :

1. $\beta$ ne contient pas de division

2. Pour toute opération additive $P_i = Q_i \pm R_i$ alors $Q_i$ et $R_i$ sont des polynômes homogènes et de même degré $\le d$.

3. Pour toute opération multiplicative $P_i = Q_i \times R_i$ alors $Q_i$ et $R_i$ sont homogènes et le degré de $P_i$ est $\le d$. $L(Hxd/P_1, P_2, ..., P_m)$ désigne le
nombre minimum de multiplications non scalaires utilisées par un programme
homogène pour calculer P₁,P₂,...,Pₘ.

Lemme 13

Soient $P_1, P_2, \dots, P_m$ une famille de polynômes homogènes de degrés $\le d$
alors :

$$
L'(*/P_1, P_2, \dots, P_m) \ge \frac{4}{[d(d-1)]^2} L(H \times d/P_1, P_2, \dots, P_m) \quad \Box
$$

Démonstration :

Il suffit de montrer que $L(x/P_1, P_2, \dots, P_m) \ge \frac{2 L(H \times d/P_1, P_2, \dots, P_m)}{[d(d-1)]}$

Soit $\beta$ un programme calculant $P_1, P_2, \dots, P_m$ dans $C[X_1, X_2, \dots, X_k] \bmod C$
$\cup\{X_1, X_2, \dots, X_k\}$. $\beta$ est une suite $\mathcal{F} = \{f_0, f_1, \dots, f_\ell\}$ de fonctions de
$C[X_1, X_2, \dots, X_k]$ où $f_i = f_j \circ f_k \ (\circ = +, -, x)$.

Posons $1 \le \alpha \le k$ ; $X_\alpha = \lambda X'_\alpha$ . On peut alors considérer $\beta$ comme un
programme sur $C[X'_1, X'_2, \dots, X'_k](\lambda) \bmod C \cup \{X'_1, X'_2, \dots, X'_k\} \cup \{\lambda\}$, calculant
des polynômes $P'_1, P'_2, \dots, P'_m$ qui sont en fait des monômes en $\lambda$ de degré $\le d$.

Définissons $f_u^\alpha \in C[X'_1, X'_2, \dots, X'_k]$ $1 \le u \le l$, $1 \le \alpha \le d$

par :

$$
f_u = \sum_{\alpha=0}^{\deg(f_u)} f_u^{\alpha} {}^{\alpha}.
$$

Les $f_u^\alpha$ sont des polynômes homogènes en les $X'_i$.

Nous pouvons alors construire à partir de $\beta$ un programme $\beta'$ obtenu
en remplaçant chaque instruction $f_i = f_j \circ f_k$ de $\beta$ par une suite d'instructions
de $\beta'$ définie de la façon suivante :

$\alpha) \circ = +,-$

$f_i = f_j \circ f_k$ est remplacée dans $\beta'$ par les $d+1$ instructions

$f_i^\alpha = f_j^\alpha \circ f_k^\alpha \text{ pour } 0 \le \alpha \le d.$
b) $\circ = x$

$f_i = f_j \times f_k$ est remplacée dans $\beta'$ par les instructions suivantes :

pour $0 \le \alpha \le d$ on met les instructions :

$$f_i^{\alpha, -1} = 0$$

pour $0 \le \beta \le \alpha$ on met les instructions :

$$f_i^{\alpha, \beta} = f_i^{\beta} \times f_k^{\alpha-\beta}$$

$$g(\alpha, \beta) = g(\alpha, \beta-1) + f_i^{\alpha, \beta}$$

$$f_i^{\alpha} = g(\alpha, \alpha)$$

On vérifie alors aisément que $\sum_{\alpha=0}^{d} f_i^{\alpha} X^{\alpha} = f_i[\text{mod.} \lambda^{d+1}]$ donc que $\beta'$ calcule effectivement $P_1, P_2, \dots, P_m$. $\beta'$ est un programme homogène dont le nombre de multiplications non scalaires est au plus $\frac{d(d-1)}{2}$ fois le nombre de multiplications non scalaires de $\beta$. $\square$

Soit $P_1, P_2, \dots, P_m$ une famille de polynômes homogènes de degrés $\le d$. Définissons $d_d(P_1, P_2, \dots, P_m) \in \mathbb{N}$ de la façon suivante : $d_d(P_1, P_2, \dots, P_m)$ est le plus petit entier a tel qu'il existe une famille de polynômes homogènes $U_1, U_2, \dots, U_a$ satisfaisant :

$$1- \frac{d}{3} \le \deg U_j \le \frac{2d}{3} \quad 1 \le j \le a$$

2- Pour $1 \le i \le m$ si $\frac{d}{3} \le \deg(P_i) \le d$ alors il existe $V_1, V_2, \dots, V_a$ polynômes homogènes tels que :

$$P_i = \sum_{j=1}^{a} U_j V_j$$

**Lemme 14 :**

Soit $P_1, P_2, \dots, P_m \in C[X_1, X_2, \dots, X_k]$ une famille de polynômes homogènes de degrés $\le d$ alors :

$$d_d(P_1, P_2, \dots, P_m) \le k+L(Hxd/P_1, P_2, \dots, P_m) \le k+\left[\frac{d(d-1)}{2}\right]^2 L'\left(\frac{*}{P_1}, P_2, \dots, P_m\right) \square$$
Démonstration :

La deuxième partie de l'inégalité résulte directement du lemme 12.
Nous montrons la première par induction sur L(H.d/P₁,P₂,...,Pm), longueur
minimale du calcul homogène permettant d'évaluer simultanément P₁,P₂,...,Pm :

a) Montrons que si L(H.d/P₁,P₂,...,Pm) = 0 alors $d_d(P₁,P₂,...,Pm) \le k$.

Si $L(H.d/P_1,P_2,...,P_m) = 0$ alors $\forall i P_i \in Cu\{X_1,X_2,...,X_k\}$ et l'on
peut choisir pour $1 \le i \le k$ $U_i = X_i$ et donc $d_d(P_1,P_2,...,P_m) \le k$.

b) Supposons que $L(H.d/P_1,P_2,...,P_m) \le \lambda = > d_d(P_1,P_2,...,P_m) \le k+L(Hxd/P_1,P_2,...,P_m)$
et montrons que $L(H.d/P_1,P_2,...,P_m) = \lambda+1 = > d_d(P_1,P_2,...,P_m) \le k+L(Hxd/P_1,P_2,...,P_m)$
On posera $L(Hxd/P_1,P_2,...,P_m) = \ell$.

Soit $Q_1, Q_2, \dots, Q_m$ un ensemble de polynômes homogènes tels que
$L(H.d/Q_1, Q_2, \dots, Q_m) = \lambda+1$. Le programme homogène calculant $Q_1, Q_2, \dots, Q_m$ et
ayant $\lambda+1$ opérations a une dernière opération dont le résultat est un des
$Q_i$, nous supposerons que c'est $Q_1$. Cette dernière opération peut donc
s'écrire $Q_1 = f_i \circ f_i'$ et $L(H.d/f_i, f_i', Q_2, \dots, Q_m) \le \lambda$. Donc d'après l'hypothèse
d'induction, $d_d(f_i, f_i', Q_2, Q_3, \dots, Q_m) \le k+\ell$. Et l'on peut donc associer à
$f_i, f_i', Q_2, \dots, Q_m$ une famille de polynômes homogènes $U_1, U_2, \dots, U_{k+\ell}$ satisfai-
sant les conditions (1) et (2) précédentes. On a donc :

si $\deg(f_i) \ge \frac{d}{3}$ et $f_i = \sum_{j=1}^{k+\ell} U_j V_j$, si $\deg(f_i') \ge \frac{d}{3}$ alors $f_i' = \sum_{j=1}^{k+\ell} U_j V_j'$ et si $i \ge 2$, $\deg(Q_i) \ge \frac{d}{3}$ alors $Q_i = \sum_{j=1}^{k+\ell} U_j V_j^i$ pour des polynômes $V_j, V_j', V_j^i$ homogènes.

On peut supposer $\frac{d}{3} \le \deg(Q_1) \le d$.
Cas 1 : $\circ = +,-$ alors $Q_l = f_i + f'_i = \sum_{j=1}^{k+l} U_j(V_j^+ - V_j^-)$.

Cas 2 : $\circ = X$

$$
a) \deg(f_i) \ge \frac{d}{3} \text{ (resp. } \deg f'_i \ge \frac{d}{3}\text{)}
$$

$$
\text{alors } f_i = \sum_{j=1}^{k+l} U_j V_j \text{ et } Q_l = f_i f'_i = \sum_{j=1}^{k+l} U_j (V_j f'_i)
$$

$$
b) \deg(f_i) < \frac{d}{3} \text{ et } \deg(f'_i) < \frac{d}{3}
$$

$$
\text{donc } \frac{d}{3} \le \deg Q_1 < \frac{2d}{3} \text{ et 1'on prend } U_{\ell+k+1} = Q_1. \quad \square
$$

4.3. Formes multilinéaires

Nous venons de relier la quantité $d_d(P_1, P_2, \dots, P_m)$ au nombre minimal
de m/d non scalaires nécessaires pour calculer l'ensemble des polynômes.
Nous nous intéressons maintenant plus particulièrement aux formes multi-
linéaires. Une forme multilinéaire Q est une application de $(C^N)^d$ dans C.
C'est un polynôme homogène et de degré d en Nd variables $X_i^j$ ($1 \le i \le d$, $1 \le j \le N$)

$$
\phi(X_i^j) = \sum_{\substack{1 \le i_1 \le N \\ \vdots \\ 1 \le i_n \le N}} \lambda_{i_1, i_2, \dots, i_d} X_1^{i_1} X_2^{i_2} \dots X_d^{i_n}
$$

E désignera l'ensemble {1,2,...,d} et si A est un sous ensemble de E,
alors A' désignera son complément dans E.

Si $A = (i_1, i_2, \dots, i_p) \subset E$ et $B = (j_1, j_2, \dots, j_p) \subset E$ alors $X_A^B$ désignera
le monôme $\prod_{k=1, p}^{j_k} X_i^k$
Si P est un polynôme en les variables $x_i^j$ (P,A) désignera la forme multilinéaire somme de tous les monômes de P qui sont de la forme :

$$ \lambda_A X_A^B \text{ où } B \subset E, \lambda_A = \lambda_{i_1 i_2 \dots i_p} \in C $$

Ainsi si $\phi$ est multilinéaire $(\phi, E) = E$.

D'autre part, nous supposerons que d est un multiple de 2. $d_d(\phi)$, que nous savons relier au nombre minimal de m/d non scalaires nécessaires pour calculer $\phi$, est la longueur minimale d'une décomposition de $\phi$ en

$$ \phi = \sum_{i=1}^{d_d(\phi)} U_i V_i \text{ où } U_i \text{ et } V_i \text{ sont des polynômes homogènes satisfaisant } \frac{d}{3} \le \text{deg}(U_i), \text{ deg}(V_i) \le \frac{2d}{3}. \text{ Nous allons nous intéresser à des décompositions plus particulières de } \phi. $$

Définissons $d_d^*(\phi) = \min\{a \in \mathbb{N} | \phi = \sum_{i=1}^a U_i V_i \text{ où } U_i \text{ et } V_i \text{ satisfont les conditions suivantes :}$

$$ a) \ (U_i, E_l) = U_i, \ (V_i, \bar{E}_l) = V_i \text{ avec } E_l = \{1, 2, \dots, \frac{d}{2}\}. $$

(donc $U_i$ et $V_i$ sont multilinéaires homogènes de degré $d/2$ en les $Nd/2$ variables $x_i^j$ ($1 \le i \le d/2$, $1 \le j \le N$) pour $U_i$ et $x_i^j$ ($d/2+1 \le i \le d$, $1 \le j \le N$) pour $V_i$).

$$ b) \ U_i \text{ et } V_i \text{ ont au maximum } N^{d/4} \text{ coefficients non nuls. On a alors :} $$

**Lemme 15 :**

Si $\phi$ est une forme multilinéaire de $(C^N)^d$ dans C alors

$$ d_d^*(\phi) \le \left(\frac{d}{2}\right)^{7d/12} d_d(\phi). \quad \square $$
**Démonstration :**

$$ \text{On a } \phi = (\phi, E) = \sum_{i=1}^{d_d(\phi)} (U_i \cdot V_i, E) $$

$$ \text{et } (U_i \cdot V_i, E) = \sum_{A \subset E} (U_i, A) (V_i, \bar{A}) \cdot \\ |A| = \text{deg}(U_i) $$

Nous allons maintenant décomposer

$$ (U_i, A)(V_i, \bar{A}) \text{ où } \frac{d}{3} \le |A| = \text{deg}(U_i) \le \frac{2d}{3} $$

quitte à échanger le rôle de $A$ et $\bar{A}$ on peut toujours trouver des ensembles $B \subset A$ et $C \subset \bar{A}$ telles que :

$$ B \subset \{1, 2, \dots, \frac{d}{2}\} \quad \min\left(\frac{d}{4}, \frac{|A|}{2}\right) \le |B| \le \frac{d}{4} $$

$$ C \subset \left\{ \frac{d}{2} + 1, \dots, d \right\} \quad \min\left(\frac{d}{4}, \frac{|\bar{A}|}{2}\right) \le |C| \le \frac{d}{4} $$

$$ \text{On a alors } (U_i, A) = \sum_{D \subset E} X_{A-B}^D \psi_i^D \\ |D| = |A-B| $$

$$ \text{où } \psi_i^D \text{ est une forme multilinéaire satisfaisant } (\psi_i^D, B) = \psi_i^D $$

$$ \text{et } (V_i, \bar{A}) = \sum_{D \subset E} X_{\bar{A}-C}^D \theta_i^D \\ |D| = |\bar{A}-C| $$

$$ \text{où } \theta_i^D \text{ satisfait } (\theta_i^D, C) = \theta_i^D $$

On a donc :

$$ \phi \coloneqq \sum_{i=1}^{d_d(\phi)} \sum_{|A| = \text{deg}(U_i)} \sum_{|D| = |A - B|} \sum_{|D'| = |\bar{A} - C|} X_{A-B}^{D} X_{\bar{A}-C}^{D'} \psi_i^D \theta_i^{D'} $$

$$ \text{on a : } X_{A-B}^D X_{\bar{A}-C}^{D'} \psi_i^D \theta_i^{D'} = (\psi_i^D X_{E_1}^F - B) \cdot (\theta_i^{D'} X_{E_1}^F - C) $$
où $E_l = \{1,2,...,\frac{d}{2}\}$ et $F \subset E_l, F' \subset \bar{E}_l$ se déduisent de $D$ et $D'$ de façon immédiate.

$$ \text{Or } (\psi_i^D X_{E_l-B}^F, E_l) = (\psi_i^D X_{E_l-B}^F \quad \text{et} \quad \psi_i^D X_{E_l-B}^F) $$

a au maximum $N^{|B|} \le N^{d/4}$ coefficients non nuls de même

$$ (\theta_i^{D'} X_{E_l-C}^F, \bar{E}_l) = (\theta_i^{D'} X_{E_l-C}^F \quad \text{et ce polynôme a au maximum } N^{|C|} \le N^{d/4}) $$

coefficients non nuls.

$$ \text{Donc } d_d^*(\phi) \le d_d(\phi) \max \left( \binom{d}{m} N^{\max(\frac{m}{2}, \frac{d}{4})} N^{\max(\frac{d-m}{2}, \frac{d}{4})} \right) $$

$$ \text{Soit } d_d^*(\phi) \le d_d(\phi) \left(\frac{d}{2}\right) N^{7d/12}. \quad \square $$

### 4.4. Formes multilinéaires et formes linéaires :

Nous allons maintenant relier $d_d^*(\phi)$ à la complexité du calcul de formes linéaires. Pour cela nous allons associer à toute forme multi-linéaire $\phi$ une matrice carrée $B(\phi)$ de dimension $N^{d/2} \times N^{d/2}$ définie de la façon suivante :

$$ \begin{align*} \text{si } \phi = & \sum_{0 \le i_1 \le N-1} \lambda_{i_1 i_2 \dots i_d} x_{i_1}^{i_1} x_{i_2}^{i_2} \dots x_{i_d}^{i_d} \\ & 0 \le i_2 \le N-1 \\ & 0 \le i_n \le N-1 \end{align*} $$

alors le coefficient $b_{ij}$, $0 \le i \le N^{d/2}-1$, $0 \le j \le N^{d/2}-1$, de $B$ est défini par :

$$ b_{ij} = \lambda_{i_1 i_2 \dots i_{d/2}} j_{i_1} j_{i_2} \dots j_{i_{d/2}} $$

où
$$ i = \sum_{k=0}^{d/2-1} i_k N^k \quad \text{et} \quad j = \sum_{k=0}^{d/2-1} j_k N^k \quad \text{avec } 0 \le i_k, j_k < N. $$
D'autre part, à une matrice B pxp) nous associons la quantité $r_{\alpha}(B)$ pour $1 \le \alpha \le p$ définie par :

$$r_{\alpha}(B) = \min\{a | B = \sum_{i=1}^{a} X_i \cdot Y_i, X_i, Y_i \in \mathbb{C}^p \text{ et } |X_i|, |Y_i| \le \alpha\}$$

où $|X_i|$ désigne le nombre de coefficients non nuls dans X. On déduit de la définition de $r_{\alpha}(B)$ que :

$$r_{\alpha}(B_1 + B_2) \le r_{\alpha}(B_1) + r_{\alpha}(B_2)$$

$$r_{\alpha}(\lambda B) = r_{\alpha}(B) \text{ pour tout } \lambda \in \mathbb{C}\{-0\}$$

$r_p(B)$ est exactement le rang de B

$r_l(B)$ est exactement le nombre de coefficients non nuls de B.

**Théorème 7** : Si $\phi$ est une forme multilinéaire application de $(C^N)^d$ dans $C$ alors :

$$r_{Nd/4} [B(\phi)] \le [Nd + \left[\frac{d(d-1)}{2}\right]^2 L'(*/\phi)] N^{7d/12} \binom{d}{2}. \quad \square$$

**Démonstration** :

Il suffit de montrer que :

$$r_{Nd/4}[B(U_i, V_i)] = 1 \quad \text{quand } U_i \text{ et } V_i \text{ satisfont}$$

$$a) (U_i, E_l) = U_i ; (V_i, \bar{E}_l) = V_i$$

b) $U_i$ et $V_i$ ont au maximum $N^{d/4}$ coefficients non nuls. et ceci découle immédiatement de la définition de $r$ et de $B$.

Nous allons maintenant relier $r_{\alpha}(B)$ au nombre minimum d'opérations nécessaires pour calculer les $p$ formes linéaires BZ, $Z = (z_1, z_2, \dots, z_p)$ et $B$ est une matrice $p \times p$.

**Lemme 16** : Soit $L(B)$ le nombre minimum d'opérations nécessaires pour calculer les $p$ formes linéaires BZ alors :

$$L(B) \le 4\alpha r_{\alpha}(B). \quad \square$$
### Démonstration :

$$ \text{On a BZ} = \sum_{i=1}^{r_{\alpha}(B)} X_i^{t_{Y_i Z}}. $$

Le calcul de $t_{Y_i Z}$ ne demande que $2\alpha-1$ opérations puisque $Y_i$ a au maximum $\alpha$ coefficients non nuls et $X_i^{t_{Y_i Z}}$ fournit $\alpha$ formes au maximum.

Il suffit de les additionner ce qui requiert au maximum $2\alpha r_{\alpha}(B)-p$ opérations. ☐

### Corollaire 1 :

$$ L(B(\phi)) \le c(2+\epsilon)^d N \quad \text{L'}(*,\phi) $$

pour $c \in \mathbb{R}^+, \phi \in \mathbb{R}^+$ arbitrairement petit et $N$ et $d$ suffisamment grands. ☐

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

### Corollaire 2 :

Il existe des formes multilinéaires de degré d, en $N$ variables et à coefficients $0-1$ dont le calcul nécessite $\Omega((\lambda N)^{d/6-2})$ m/d non scalaires (λ constante >0, λ < 4⁵) et dont la construction explicite peut être déduite de la construction de p formes linéaires en p variables à coefficients $0-1$ dont le calcul nécessite $\Omega(p^2/\log_2 p)$ opérations. (prendre $p = N^{d/2}$)

### REFERENCES.

* Belaga, E.G., (1958) "Some Problems in the Computation of Polynomials", Dokl. Akad. Nauk. SSR, vol 123 : pp 775-777.

* Borodin, A. & Cook, S. (1974) "On the Number of Additions to Compute Specific Polynomials", SIAM Journal of Computing, vol. 5, n°1, pp. 146-157.

* Borodin, A. & Munro, I. (1975) "The computational Complexity of Algebraic and Numeric Problems", American Elsevier, New York.
Dobkin, D. & Lipton R.J., (1975) "Complexity Measures and Hierarchies for the Evaluation of Integers, Polynomials and N-linear Forms", Proc. 7th Annual ACM Symp. on Theory of Computing, pp. 1-5.

Hyafil, L. & Van de Wiele, J.P., (1975) "On the Additive Complexity of Specific Polynomials", Information Processing Letters, vol. 4, n°2, pp. 45-47.

Lipton, R.J. (1975) "Polynomials with 0-1 Coefficients that are Hard to Evaluate", Proc. 16th Annual Symp. on Foundations of Computer Science, pp. 6-10.

Lipton, R. & Stockmeyer, L.J. (1976) "Evaluation of Polynomials with Super-Preconditioning", Proc. 8th Annual ACM Symp. on Theory of Computing; pp. 174-180.

Motzkin, T.S. (1955) "Evaluation of Polynomials and Evaluation of Rational Functions", Bull. Amer. Math. Soc. vol. 61, p. 163.

Paterson, M. & Stockmeyer, L. (1973) "On the Number of Nonscalar Multipli-cations Necessary to Evaluate Polynomials", SIAM Journal of Computing, vol 2, n°1, pp. 60-66.

Rabin, M. & Winograd, S. (1971) "Fast Evaluation of Polynomials by Rational Preparation", IBM Tech. Report RC 3645.

Revah, L. (1975) "On the number of Multiplications/Divisions Evaluating a Polynomial with Auxiliary Functions", SIAM Journal of Computing, vol. 4, n°3, pp. 381-392.

Savage, J.E. (1974) "An algorithm for the computation of Linear Forms" SIAM Journal of Computing, vol 3, n°2, pp. 150-158.

Strassen, V. (1972) "Berechnung und Programm. I." Acta Informatica, vol 1, pp. 320-335.

Strassen, V. (1973) "Vermeidung non Divisionen", J. Reine Angew. Math. vol 264, pp. 184-202.

Strassen, V. (1974) "Polynomials with Rational Coefficients which are Hard to Compute", SIAM Journal on Computing, vol 3, n°2, pp. 128-149.
# Annexe 1

## Démonstration du lemme 3 :

Soit à montrer : il existe des entiers naturels $b_{i_1, i_2, \dots, i_q}$ (non tous nuls) tels que :

$$ (1) \quad \sum_{i_1+i_2+\dots+i_q=g} b_{i_1 i_2 \dots i_q} P_1^{i_1} \dots P_q^{i_q} = 0 $$

Remplaçons les $b_{i_1 i_2 \dots i_q}$ par des indéterminés et considérons

$$ Q = \sum_{i_1+i_2+\dots+i_q=g} B_{i_1, \dots, i_q} P_1^{i_1} \dots P_q^{i_q} \in Z[\bar{B}, \bar{Z}] $$

$$ \text{On a : } \deg_{\mathbb{Z}} Q \le gc $$

Si nous écrivons $Q$ comme un polynôme en $z_1, z_2, \dots, z_m$ les coefficients sont des formes linéaires dans $Z[\bar{B}]$ ; il y a au plus $(gc^m+m)$ telles formes :

(1) exprime que les $b_{i_1 i_2 - i_q}$ sont des zéros communs de ces formes. Le lemme du tiroir (cf Strassen [74]) implique l'existence d'un zéro entier non trivial $b_{i_1 i_2 \dots i_q}$ si :

$$ \begin{array}{l@{\quad}l} \text{(2)} & \begin{array}{@{}c@{}} (g+q-1)^{q-1} \\ \mid \\ \text{nombre} \\ \text{de} \\ \text{variables} \end{array} > \begin{array}{@{}c@{}} (g+c+m)^m \\ \mid \\ \text{nombre} \\ \text{de} \\ \text{formes} \end{array} \end{array} $$

Les hypothèses sur $m$, $c$ et $q$ impliquent

$$ (4) \quad (g^c+m) \le (gc)^m + 1 $$

et

$$ (5) \quad (g) q^{q-1} < (g+q-1) q^{q-1} $$
On déduit de (2), (4) et (5) qu'il suffit de montrer :

$$ (6) \quad g^{q-m-1} \geq c^{m}q \quad \Rightarrow \quad \left(\frac{g}{q}\right)^{q-1} \geq (gc)^{m} + 1 \quad (7) $$

Or :

$$ (7) \quad \Leftrightarrow \quad ((gc)^m + 1)q^{q-1} \leq g^{q-1} $$

$$ ((gc)^m + 1) q^{q-1} < (gc)^m q $$

Donc (7) sera vrai si : $(gc)^{m}q \leq g^{q-1}$ et (6) $\Rightarrow$ (7). $\square$