Bornes inferieures et superieures dans les circuits arithmetiques

Bornes inferieures et superieures dans les circuits
arithmetiques

Préliminaires : notations et introduction à la théorie de Valiant

Dans ce chapitre, nous définirons les outils ainsi que les notations que nous allons utiliser dans la suite de ce manuscrit. Nous donnerons ensuite une brève introduction à la théorie des circuits arithmétiques (appelée généralement théorie de Valiant). Toutefois, nous considérerons ici seulement les bases et les résultats qui nous seront utiles pour la suite. Pour un aperçu plus complet de cette théorie, le lecteur interessé pourra se tourner vers les références suivantes [19, 23, 35, 91]. L’idée de cette théorie est de mesurer la complexité des polynômes en termes de nombres d’opérations arithmétiques à effectuer. Commençons par fixer quelques notations pour les polynômes.

Polynômes

Un polynôme univarié f est défini comme une expression de la forme f = c0 + c1X + c2X 2 + . . . + cdX d = X d i=0 ciX i où les ci (pour 0 ≤ i ≤ d) sont des éléments d’un anneau commutatif A avec cd 6= 0 et où X est un symbole formel appelé indéterminée (ou même variable). La constante d est appelée le degré (notée aussi deg(f)) et les (ci)0≤i≤d les coefficients de f. Par convention, le degré du polynôme nul sera −∞. L’ensemble des polynômes à coefficients dans un anneau A est encore un anneau et sera noté A[X]. Remarque 1.1. Dans la suite du manuscrit, les anneaux seront toujours supposés unitaires et commutatifs. Un polynôme est donc une somme de termes où chaque terme est le produit d’un coefficient ci et d’un monôme Xi . Les coefficients cd (où d est le degré) et c0 sont traditionnellement appelés respectivement le coefficient dominant et le terme constant. Si A est un sous-anneau de B, alors, on associera à un polynôme f sa fonction polynomiale sur B. Il s’agit de la fonction : f : B → B x 7→ c0 + c1x + . . . + cdx d . En fait, nous nous intéresserons essentiellement dans la suite à des anneaux très simples. En particulier A correspondra généralement à Z ou Q et B sera R ou C. Les polynômes multivariés sont des polynômes en plusieurs indéterminées. Il s’agit d’expression de la forme f = c0,0,…,0 + c1,0,…,0X1 + . . . + c0,0,…,1Xn + . . . + ci1,i2,…,inX i1X i2 · · · X in = X α∈Nn cαXα où la somme est finie. Les coefficients ci1,i2,…,in sont encore des éléments d’un anneau A. Le coefficient c0,0,…,0 sera encore appelé le terme constant. Le degré d’un monôme m = Xα1 · · · Xαn sera alors défini par deg(m) = Pn i=1 αi . Le degré total du polynôme sera le maximum des degrés de ses monômes, c’est-à-dire deg(f) = maxα(α1 + . . . + αn). Un polynôme est dit homogène si tous les termes associés à un coefficient non nul ont même degré. Un polynôme est constant s’il est de degré au plus 1.

Propriétés élémentaires des polynômes

Un outil pratique pour les polynômes est la décomposition en facteurs irréductibles. Plus formellement, si K est un corps commutatif, un polynôme f est dit irréductible s’il est de degré au moins 1 et si pour toute écriture de f comme un produit g · h alors, un des deux polynômes g ou h est constant. La décomposition en facteurs irréductibles assure que pour tout polynôme f sur un corps K, il existe des polynômes g1, . . . , gp irréductibles et une constante λ de K tels que : f = λg1 . . . gp. De plus, ces nouveaux polynômes sont uniques à constante multiplicative près. Un anneau qui possède cette propriété de décomposition unique en irréductible est appelé factoriel. La théorie sur ces anneaux est beaucoup plus générale que celle présentée ici (en particulier, pour les anneaux de polynômes, l’anneau de base n’a pas besoin d’être un corps) et peut être trouvée dans tout livre d’algèbre. Une racine d’un polynôme f en n variables est un point (a1, . . . , an) de A n tel que f s’annule en ce point (i.e. f(a1, . . . , an) = 0). Dans le cas des polynômes univariés, le fait que a soit une racine de f(X) est équivalent au fait que (X −a) soit un facteur de f. Un corollaire direct de l’unicité de la décomposition en irréductibles est que si f(X) est un polynôme non identiquement nul, alors son nombre de racines est borné par son degré

Fractions rationnelles

On peut tout d’abord remarquer que l’ensemble des polynômes est le plus petit ensemble qui contient les constantes, les variables et qui est stable par les trois lois +, − et ×. Mais que se passe-t-il si on veut rajouter les divisions ? 8 1. POLYNÔMES Il est alors naturel de se placer dans le cas où l’anneau de base est un corps K (comme pour les anneaux, nos corps seront toujours commutatifs). On définit les fractions rationnelles comme les quotients de deux polynômes : f est fraction rationnelle si et seulement s’il existe deux polynômes g et h (avec h non identiquement nul) tels que f = g/h. On dira que g/h est sous forme simplifiée si g et h sont premiers entre eux (i.e. que si un polynôme φ divise g et h, alors φ est constant). De même que pour les polynômes, on peut associer à chaque écriture g/h la fonction rationnelle associée (où B est un sur-corps de K) : g/h : B → B x 7→ g(x)/h(x). Toute fraction rationnelle peut se mettre sous une forme simplifiée, la seule perturbation de cette transformation est que le domaine de la nouvelle fonction associée a potentiellement été étendu par continuité. Ces singularités qui ont disparu sont appelées singularités effaçables. Dans la suite, les fractions rationnelles (ainsi que les fonctions associées) seront par défaut sous forme simplifiée. On peut encore définir les racines d’une fonction rationelle comme les points où elle s’annule. On définira les pôles, comme les points où la fonction rationnelle est non définie. L’ensemble des fractions rationnelles sera noté K(X1, . . . , Xn). 1.3 Polynômes classiques Un premier exemple de polynôme est le produit itéré de matrices. Il s’agit du produit matriciel .