AnalyseThéorème · Glossaire
Sous-additivité (lemme de)
Le lemme de sous-additivité (ou lemme de Fekete) affirme que pour toute suite sous-additive (a_n), c'est-à-dire satisfaisant a_{m+n} <= a_m + a_n, la suite a_n/n converge et sa limite est égale à l'infimum de a_n/n. Ce lemme est utilisé pour établir la convergence de nombreuses suites en théorie de la mesure, en probabilités (par exemple pour prouver l'existence de l'entropie d'un processus stationnaire) et, dans des cadres déterministes adaptés, en dynamique des systèmes. Pour les cocycles aléatoires ou stationnaires, l'existence d'exposants de Lyapunov relève plutôt du théorème ergodique sous-additif de Kingman, sous des hypothèses supplémentaires d'ergodicité et d'intégrabilité.
Sommaire
Ce que vous allez apprendre
- Reconnaître l'inégalité qui définit une suite sous-additive.
- Relier la limite des quotients a_n/n à leur infimum.
- Refaire l'exemple a_n = plafond de n/2 et contrôler sa limite égale à 1/2.
- Distinguer sous-additivité, additivité et monotonie.
- Repérer les cas où la limite vaut moins l'infini ou l'infimum n'est pas atteint.
En clair
Imaginez des objets transportés deux par deux. Pour en déplacer n, le nombre minimal de voyages est l'entier supérieur ou égal à n/2. Réunir un plan pour m objets et un plan pour n objets donne toujours un plan possible pour les m + n objets : traiter le lot global ne coûte donc pas davantage que traiter séparément les deux lots.
Cette économie possible lors du regroupement est la sous-additivité. Le lemme de Fekete dit qu'à long terme le coût moyen par objet se stabilise, même si les premiers quotients oscillent.
Définition
Une suite de nombres réels, notée (an) pour les indices entiers n au moins égaux à 1, est sous-additive lorsque, pour tous entiers positifs m et n, le terme d'indice m + n ne dépasse pas la somme des deux termes séparés : . L'inégalité doit être vraie pour chaque paire d'indices, et non seulement pour deux valeurs choisies.
Le lemme de sous-additivité, aussi appelé lemme de Fekete, porte sur les quotients an/n. Il affirme que leur limite existe dans les réels étendus et vaut la plus grande borne inférieure de tous ces quotients :
La limite peut donc être un nombre réel ou valoir moins l'infini. L'infimum n'a pas besoin d'être atteint par un indice particulier.
Ce résultat transforme une inégalité valable quand on concatène deux tailles en une convergence à long terme. Il intervient notamment en théorie de la mesure, en probabilités pour l'existence de l'entropie d'un processus stationnaire, et en dynamique des systèmes pour l'existence d'exposants de Lyapunov.
Le principe
Soit (an) une suite réelle indexée par les entiers positifs. Si, pour tous m et n positifs, , alors la suite des quotients an/n converge dans les réels étendus.
Sa limite est donnée sans avoir à calculer chaque quotient :
Il suffit donc d'établir la sous-additivité, puis d'identifier ou d'encadrer cet infimum.
Quand l'utiliser
Le lemme s'applique à une suite de nombres réels définie pour tous les indices entiers positifs. La condition décisive est globale : pour chaque paire d'indices positifs m et n, le terme am+n doit être inférieur ou égal à am + an. Aucune positivité ni monotonie des termes n'est exigée. On obtient la convergence des quotients an/n, pas nécessairement celle des termes an.
Un contrôle sur quelques couples ne suffit pas. Par exemple, la suite bn = (−1)nn échoue dès m = n = 1, car b2 = 2 est supérieur à b1 + b1 = −2 ; de plus, bn/n alterne entre −1 et 1. Sans sous-additivité, il faut étudier directement la convergence ou disposer d'un autre théorème adapté.
Un exemple, pas à pas
Des objets sont transportés deux par deux. Pour chaque entier positif n, notons an le nombre minimal de voyages nécessaires pour transporter n objets. Les données sont une capacité de 2 objets par voyage et les tailles n = 1 à 6. On a .
1. Les six premiers nombres de voyages sont 1, 1, 2, 2, 3 et 3.
2. Les quotients an/n sont successivement 1, 1/2, 2/3, 1/2, 3/5 et 1/2.
3. Regrouper deux plans de transport donne : la suite est sous-additive.
2. Les quotients an/n sont successivement 1, 1/2, 2/3, 1/2, 3/5 et 1/2.
3. Regrouper deux plans de transport donne : la suite est sous-additive.
4. Pour un indice pair, le quotient vaut exactement 1/2. Pour un indice impair écrit 2k + 1, il vaut , donc il se rapproche de 1/2.
5. L'infimum des quotients est 1/2 et leur limite est 1/2 voyage par objet. Les valeurs paires fournissent un contrôle refaisable : elles atteignent déjà cet infimum.
5. L'infimum des quotients est 1/2 et leur limite est 1/2 voyage par objet. Les valeurs paires fournissent un contrôle refaisable : elles atteignent déjà cet infimum.
En pratique
Dans un problème où une quantité mesure le coût minimal d'un objet de taille n, on cherche si deux solutions peuvent être concaténées. Si cette construction donne un coût global au plus égal à la somme des coûts, le lemme fournit un coût moyen asymptotique. Sans cette concaténation, une estimation directe est préférable.
En probabilités, le même geste consiste à découper une longue observation en blocs et à comparer la quantité associée au tout avec celles des blocs. Lorsque la sous-additivité est démontrée, elle peut établir l'existence d'un taux limite, notamment pour l'entropie d'un processus stationnaire.
En dynamique des systèmes, on ramène également une évolution longue à la composition de durées plus courtes. Dans un cadre déterministe adapté, une inégalité sous-additive peut conduire à un taux asymptotique. Pour des cocycles aléatoires ou stationnaires, l'existence d'exposants de Lyapunov s'appuie plutôt sur le théorème ergodique sous-additif de Kingman, avec des hypothèses d'ergodicité et d'intégrabilité ; si l'inégalité porte sur une autre quantité, il faut d'abord reformuler le problème au bon niveau.
À ne pas confondre
Une suite additive vérifie l'égalité am+n = am + an, tandis qu'une suite sous-additive n'impose qu'une majoration. La suite an = n est additive ; la suite du nombre de voyages, an = ⌈n/2⌉, est sous-additive mais n'est pas additive puisque a2 = 1 alors que 2a1 = 2.
La monotonie compare deux indices ordonnés, par exemple an+1 et an. La sous-additivité compare au contraire un indice somme à deux termes. Une suite peut être sous-additive sans que ses quotients soient monotones : dans l'exemple, 1/2 est suivi de 2/3, puis de nouveau de 1/2.
Limites et pièges
L'infimum n'est pas forcément un minimum. Le lemme identifie la plus grande borne inférieure des quotients, mais n'affirme pas qu'un quotient particulier la réalise. Il faut donc écrire « infimum » tant qu'un indice donnant cette valeur n'a pas été exhibé.
La convergence peut avoir lieu vers moins l'infini. Ainsi, an = −n2 est sous-additive pour les indices positifs, car −(m + n)2 ≤ −m2 − n2, et le quotient vaut −n. Il ne faut pas annoncer une limite réelle finie sans borne inférieure supplémentaire.
La suite des quotients n'a aucune raison d'être monotone. Les valeurs 1, 1/2, 2/3, 1/2, 3/5 et 1/2 de l'exemple remontent après chaque indice pair. Il faut utiliser le lemme pour conclure, et non extrapoler la direction prise entre deux termes consécutifs.
Une inégalité vérifiée seulement à partir d'un certain rang, ou avec un terme d'erreur, n'est pas exactement l'hypothèse énoncée ici. Le symptôme est l'impossibilité de traiter tous les couples d'indices positifs. Il faut alors prouver une version adaptée ou absorber rigoureusement l'erreur avant d'invoquer un résultat asymptotique.
Pour aller plus loin
La fiche Sous-additive (suite) approfondit la propriété des suites à laquelle le lemme de Fekete s'applique.
La fiche convergence d'une suite numérique précise le sens d'une limite pour une suite et les façons usuelles de l'établir.
La fiche Entropie présente une quantité pour laquelle la sous-additivité intervient en probabilités et dans l'étude des processus stationnaires.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres