You are currently browsing the monthly archive for janvier 2014.

La première chose parfaitement évidente concernant une somme de nombres complexes est l’inégalité triangulaire :
\lvert \sum_{i=1}^{n}z_i \rvert \leq \sum_{i=1}^{n}\lvert z_i \rvert .

L’égalité est possible, elle est réalisée quand tous les points se trouvent sur une même demi-droite vectorielle. En général, il y a des pertes, qui peuvent être considérables.

Le théorème d’équirépartition de Weyl
Prenons des points z_i « bien répartis » sur le cercle unité. Alors on sent bien que le module de la somme va être riquiqui par rapport à la somme des modules. L’exemple archétypal est celui des racines n-ièmes de l’unité, qui sont « parfaitement répartis » et dont la somme est nulle.

Définissons l’équirépartition comme suit : une suite infinie (z_n)_{n\in \mathbb{N}} de nombres complexes du cercle est dite équirépartie si pour tout intervalle I=(a,b) du cercle (le cercle est vu comme l’intervalle (0,1) avec 0 et 1 assimilés),
\lim_{N\to\infty}\frac{1}{N}\sum_{n=0}^{N-1}1_{{z_n}\in I}=b-a

Autrement dit, la fréquence d’appartenance à un intervalle est proportionnelle à sa longueur.

Le théorème de Weyl affirme que la suite des z_n est équirépartie si et seulement si
\sum_{n=0}^{N}z_n=o(N)

Sous-somme d’une somme : lemme de confinement
Supposons que je fasse un certain nombre n de pas de longueur 1 qui me font revenir au bout du compte à mon point de départ. J’ai pu atteindre, au cours de ma promenade, un point très éloigné de mon origine (peut-être même n/2 !). Mais me serait-il possible de réordonner ma suite de pas de manière à ce que je ne sorte à aucun moment d’un disque raisonnablement petit centré en 0 ?

Une promenade confinée

Formellement, soit z_i une suite de complexes de somme nulle. Alors je prétends qu’il existe un réordonnancement z_{\sigma(i)} tel que
\text{max }_{k=1}^{n}\lvert\sum_{i=1}^{k}z_{\sigma(i)}\rvert\leq 2\text{max }\lvert z_i \rvert.

Ce théorème se généralise en fait à tout EVN de dimension finie (en remplaçant 2 par la dimension).

Et si on trafiquait les signes ?
Il s’avère que quitte à soustraire certains complexes au lieu de les additionner, on peut se retrouver assez proche du cas d’égalité triangulaire. Concrètement, on a le résultat suivant :
\forall (z_i)_{i=1,\cdots,n}, \exists (\epsilon_i)\in\{-1,1\}^n : \lvert \sum \epsilon_iz_i \rvert\geq 1/2\sum\lvert z_i\rvert

Moi je me demande si cette égalité marche avec un \sqrt{2} au lieu du 2 !

Mentionnons aussi le lemme de Littlewood-Offord.
Soit a_i des nombres complexes de module au moins égal à 1. Quelle est la probabilité, quand je choisis des \epsilon=\pm 1 au hasard et que je considère la somme \sum \epsilon_i a_i, de tomber dans la boule unité ?
Cette probabilité est assez faible en réalité : de l’ordre de 1/\sqrt{n} !

Appesantissons-nous, exemples à l’appui, sur l’éternel débat concernant la valeur d’une démonstration existentielle non-constructive. A l’époque du grand David Hilbert, ce débat faisait particulièrement rage ; Paul Gordan, dégoûté par l’attitude de Hilbert, lâcha même au sujet de ses démonstrations c’est de la théologie, pas des mathématiques.

Un exemple tout bête
Soit F un corps et x_1,\cdots,x_d des éléments de ce corps. On sait bien alors qu’il existe un polynôme non nul, de degré au plus d qui s’annule en ces points. Il est facile d’en exhiber un : \prod (X-x_i).

Une méthode non constructive, un peu ridicule dans ce contexte, consisterait ici à dire que l’application de F_d[X] dans F^d définie par P\mapsto (P(x_1),\cdots,P(x_d)), ne peut être injective pour des raisons de dimension : d+1 à gauche, d à droite. Il y a donc un noyau non trivial, et donc un polynôme non nul, de degré au plus d, qui s’annule aux points prescrits.

On voit déjà le genre d’idées : en linéarisant le problème, on le soumet à la toute puissante algèbre linéaire qui va le broyer… C’est encore ce qu’on va faire dans la suite.

Notons déjà une variante moins bébête de l’énoncé. Pour un polynôme P\in F[x_1,\cdots,x_n] et un point p, notons ord_p(P) l’ordre d’annulation de P en p, soit le plus grand entier k tel que D^{i_1,\cdots,i_n}P(p)=0 avec k=i_1+\cdots i_n et D désignant la dérivation, les exposants étant le nombre de dérivation suivant chaque variable. Si jamais
\sum_{p\in F^n} \binom{c_p+n-1}{n}<\binom{d+n}{n}, alors il existe un polynôme non-nul de degré au plus d tel que ord_p(P)\geq c_p pour tout point p.

Un tel énoncé s’obtient aussi aisément par un argument de dimension.

Le théorème des restes chinois
Ce théorème issu de l’antiquité chinoise (IIIè siècle)
peut être utile pour calculer des concomitances astronomiques (congruences modulo 28 et modulo 365) ou autres.

Sous sa forme européenne formalisée, il dit que si n et m sont deux nombres premiers entre eux, alors \mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}\sim \mathbb{Z}/nm\mathbb{Z}.

Une preuve existentielle s’obtient en disant que la projection canonique
\mathbb{Z}\rightarrow \mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}
a pour noyau nm\mathbb{Z} donc passe au quotient en une application injective, qui est forcée d’être bijective à cause de l’égalité des cardinaux.

Une preuve constructive passe comme souvent par une identité de Bezout. Si n et m sont premiers entre eux, soit u et v tels que uv+nm=1. Soit (x,y)\in\mathbb{Z}/n\mathbb{Z}\times\mathbb{Z}/m\mathbb{Z}c. Construisons son antécédent par la projection canonique : z=uny+vmx convient.

L’obtention d’une identité de Bézout, qui ne demande rien de plus qu’un brave algorithme d’Euclide étendu, est facile et donne l’isomorphisme recherché à bas coût.

Les nombres algébriques
Tout le monde sait bien que la somme et le produit de deux nombres algébriques est aussi un nombre algébrique.

Une preuve « théologique » est facile. Là encore, il s’agit de linéariser. Soient donc a et b deux nombres algébriques sur un corps K ; la remarque linéaire est qu’alors K[a] et K[b] sont de dimension finie d_1 et d_2 sur K. Mais alors K[a,b]=K[a][b] est de dimension au plus d_2 sur K[a], donc de dimension au plus d_1d_2 sur K. Or, K[a+b] et K[ab] en sont des sous-espaces ; ils sont donc de dimension finie sur K, ce qui signifient que a+b et ab sont algébriques.

Une preuve constructive consiste à fournir, étant donné des polynômes annulateurs de a et b, un polynôme annulant a+b ou ab. Un tel polynôme s’obtient par la théorie du résultant.

Le théorème de Bézout
Il s’agit de borner le nombre de points d’intersection de deux courbes selon leur degré.

Soient P_1,P_2\in F[X,Y] deux polynômes sans facteur commun, de degrés d_1, d_2 et notons Z(P) le lieu des zéros d’un polynôme P. Alors Z(P_1)\cap Z(P_2) est fini de cardinal au plus d_1d_2.

Pour le prouver, la linéarisation fait encore des ravages. Considérons les idéaux
(P_1)=\{P_1Q\lvert Q\in F[x,y]\},(P_2), (P_1,P_2),(P_1)+(P_2),(P_1P_2)=(P_1)\cap(P_2).
En effet, il est aisé de voir que l’énoncé à démontrer revient à dire que la codimension
de l’idéal (P_1,P_2), qui est aussi un sous-espace vectoriel de F[X,Y], est inférieure à d_1d_2.

En effet, en supposant acquis cette borne sur la codimension, raisonnons par l’absurde : soient d_1d_2+1 zéros communs notés (x_i,y_i). Alors on peut former autant de polynômes linéairement indépendants dans l’espace quotient F[X,Y]/(P_1,P_2), en posant
Q_i=\prod_{i\neq j}(X-x_j)(Y-y_j)
d’où la contradiction.
Or, la borne dimensionnelle n’est pas trop dure à obtenir avec un peu de ténacité.

Mais il existe une méthode plus constructive, reposant à nouveau sur la théorie du résultant. On est alors capable de donner des candidats à l’intersection des courbes.
En effet notons R_Y(P_1,P_2),R_X(P_1,P_2) les résultants de nos polynômes, vus respectivement dans F(Y)[X], F(X)[Y], où ils sont toujours sans facteur commun. Ce sont des éléments de F(Y),F(X), mais en fait de F[Y],F[X]. Ils ont donc un nombre fini de racines chacun, et on obtient aisément que les coordonnées (x,y) des points d’intersection vérifient
R_Y(P_1,P_2)(x)=0,R_X(P_1,P_2)(y)=0
d’où la borne d_1d_2.

Récemment, j’ai produit une preuve fausse du théorème de Schwarz-Zippel. Ce théorème, du plus grand intérêt, sert à donner une borne au nombre de zéros dans F^n à un polynôme en n variables sur un corps fini F_q. Plus précisément, soit P\in F[X_1,\cdots,X_n], non-nul, de degré d. Alors le nombre de zéros est inférieur à dq^{n-1}.

J’aurais eu envie de dire : pour chaque n-1 uplet (x_1,\cdots,x_{n-1}), soit P_{x_1,\cdots,x_{n-1}}(t)=P(x_1,\cdots,x_{n-1},t), ce qui définit un polynôme à une indéterminée, de degré au plus d. Il a donc au plus d racines. On obtient ainsi q^{n-1} tels polynômes. Or, (x_1,\cdots,x_n) est un zéro de P si et seulement si x_n est un zéro de P_{x_1,\cdots,x_{n-1}}. D’où la borne sur le nombre de zéros.

Avez-vous vu l’erreur ?
Une vraie preuve a besoin d’une vraie récurrence. Ici on part du résultat bien connu pour les polynômes en une variable, et on l’étend. Une vraie preuve suppose le résultat vrai pour n-1 variables, et en déduit le résultat pour n variables.

Chers visiteurs, j’ai créé ce blog il y a quelques mois déjà, profondément charmé par le blog de Terence Tao et quelques autres blogs mathématiques. Mais je n’ai jamais eu le courage de composer le moindre billet jusqu’à aujourd’hui.

Le titre du blog fait bien sûr référence au classique d’Aigner et Ziegler, Das BUCH der Beweise ; le titre original, en anglais, Proofs from the BOOK était semble-t-il déjà pris, par un hurluberlu qui n’a rien posté non plus finalement. Aigner et Ziegler font bien sûr eux-mêmes référence au grand Paul Erdös, qui s’exclamait toujours, en voyant une belle preuve, this one is from the book, faisant allusion à l’un de ses grands fantasmes, le livre complet des preuves retenu caché par le fasciste suprême, que certains assimilaient à Dieu.

L’objectif du blog est assez égoïste ; il s’agit de me forcer à mettre au clair certaines réflexions, survenues à l’occasion de lectures ou de sombres élucubrations personnelles. Je forme toutefois le vœu qu’il soit d’intérêt général, voire utile peut-être à mes collègues en préparation à l’agrégation ou intéressés par la combinatoire additive.

Il n’est pas à exclure que certaines considérations extra-mathématiques s’invitent ici, mais elles ne dépasseront jamais, au pire, les « méta-mathématiques », l’histoire et la philosophie des maths.

J’espère recevoir des commentaires, des correctifs, voire… des élucubrations personnelles. Pour conclure cette introduction, reprenons le caveat de ce brave Montaigne :
ami lecteur, il n’est pas raisonnable que tu emploies ton loisir en un sujet si frivole. Adieu donc ?