AnalyseThéorème · Glossaire
Fekete (lemme de)
Le lemme de Fekete affirme que pour toute suite réelle sous-additive (an) indexée par les entiers positifs, c'est-à-dire vérifiant pour tous entiers positifs m, n, la suite an/n converge (éventuellement vers −∞). Sa limite est l'infimum de la suite an/n. Ce résultat, dû à Michael Fekete, est utilisé dans de nombreux domaines : en théorie de l'information pour les capacités de canal, en dynamique symbolique, et dans la théorie des groupes pour l'entropie. Il établit l'existence d'une limite que l'on ne pourrait a priori que supposer.
Sommaire
Ce que vous allez apprendre
- Identifier l’hypothèse de sous-additivité.
- Relier la limite de a_n/n à l’infimum des quotients.
- Vérifier le lemme sur la suite a_n = plafond(n/3).
- Distinguer sous-additivité, sur-additivité et décroissance.
En clair
Imaginez que le coût de deux morceaux assemblés ne dépasse jamais la somme de leurs coûts séparés. Même si le coût moyen par morceau monte et descend au début, cette règle empêche ses fluctuations de persister n’importe comment.
Le lemme de Fekete garantit alors que ce coût moyen finit par se rapprocher d’une valeur précise : la plus petite valeur qu’il peut approcher. Cette valeur peut aussi décroître sans borne, auquel cas la limite vaut −∞.
Définition
Une suite de nombres réels est dite sous-additive lorsque le terme associé à une somme d’indices ne dépasse jamais la somme des deux termes correspondants. Si le terme de rang positif n est noté an, cette condition s’écrit, pour tous les entiers positifs m et n : .
Le lemme de Fekete porte sur les quotients an/n. Il affirme que cette suite de quotients admet une limite dans les nombres réels complétés par −∞ et identifie exactement cette limite :
La convergence ne signifie donc pas que les quotients sont monotones ; ils peuvent osciller tout en se rapprochant de leur infimum.
La valeur limite n’est pas nécessairement atteinte par un rang particulier. Le cas −∞ est explicitement permis : il signifie que les quotients an/n deviennent arbitrairement négatifs.
Le principe
Soit une suite réelle dont le terme de rang positif n est an. Si, pour tous les entiers positifs m et n, , alors les quotients an/n convergent. Leur limite est donnée par :
Cette valeur peut être un nombre réel ou −∞.
Quand l'utiliser
Le lemme s’applique à une suite indexée par les entiers positifs. Il faut connaître une inégalité valable pour chaque paire d’indices positifs : le terme au rang m + n doit être inférieur ou égal à la somme des termes aux rangs m et n. Quelques vérifications numériques ne suffisent pas ; la sous-additivité doit être démontrée dans le domaine entier considéré.
Par exemple, la suite définie par an = (−1)nn ne convient pas. Pour m = n = 1, on obtient a2 = 2, tandis que a1 + a1 = −2 : l’inégalité requise échoue. Ses quotients alternent d’ailleurs entre −1 et 1. Il faut alors étudier leur convergence par une autre méthode.
Un exemple, pas à pas
On considère la suite dont le terme an est le plus petit entier supérieur ou égal à n/3. Les données sont les entiers positifs n et la règle .
1. Pour deux entiers positifs m et n, arrondir séparément m/3 et n/3 vers le haut ne peut pas donner moins qu’arrondir leur somme vers le haut. La suite est donc sous-additive.
2. Ses six premiers termes sont 1, 1, 1, 2, 2 et 2. Les quotients correspondants sont 1, 1/2, 1/3, 1/2, 2/5 et 1/3. Ils ne décroissent pas à chaque rang.
3. Comme an est toujours supérieur ou égal à n/3, chaque quotient an/n est supérieur ou égal à 1/3. Lorsque n est un multiple de 3, le quotient vaut exactement 1/3.
4. L’infimum des quotients vaut donc 1/3. Le lemme donne le résultat exact : . Le contrôle consiste à reprendre n = 3, 6, 9 ou 12, qui donnent tous le quotient 1/3.
Les douze premiers quotients rendent visible l’alternance : les points remontent après certains multiples de 3, mais restent au-dessus de la ligne 1/3 et s’en rapprochent.
En pratique
En théorie de l’information, on rencontre des quantités attachées à des blocs de longueur n. Lorsqu’une preuve établit que la quantité d’un bloc concaténé est au plus la somme des quantités des deux blocs, le lemme justifie l’existence d’un taux asymptotique par symbole, notamment dans l’étude des capacités de canal.
En dynamique symbolique et dans la théorie des groupes, le même geste consiste à encadrer une quantité de taille m + n par celles des tailles m et n. Une fois la sous-additivité obtenue, on peut définir rigoureusement un taux limite lié à l’entropie. Sans cette inégalité, il faut une autre preuve de convergence.
À ne pas confondre
Une suite sur-additive vérifie l’inégalité inverse : le terme d’indice m + n est supérieur ou égal à la somme des deux autres. Le résultat dual porte alors sur le supremum des quotients. Une égalité comme am+n = am + an satisfait les deux propriétés.
La sous-additivité n’est pas la décroissance. Elle compare trois termes dont les indices s’additionnent, tandis que la décroissance compare deux rangs successifs. Dans l’exemple an = ⌈n/3⌉, la suite augmente parfois, mais elle reste sous-additive.
Limites et pièges
Le piège principal consiste à conclure que les quotients an/n décroissent. Le lemme garantit leur convergence, pas leur monotonie. Dans l’exemple conducteur, le quotient passe de 1/3 au rang 3 à 1/2 au rang 4 ; il faut chercher l’infimum de l’ensemble des quotients, non le plus petit quotient observé dans un court tableau.
La limite peut valoir −∞. Ce cas ne désigne pas un nombre réel caché : pour tout seuil négatif choisi, des quotients finissent par passer en dessous. Il faut conserver cette possibilité au lieu d’annoncer automatiquement une limite réelle finie.
Enfin, une inégalité vérifiée seulement pour les premières valeurs ne déclenche pas le lemme. Le symptôme est une preuve réduite à une liste finie de calculs. Il faut établir la relation pour tous les entiers positifs m et n, ou renoncer à invoquer ce résultat.
Pour aller plus loin
La fiche Sous-additive (suite) approfondit la propriété qui constitue l’hypothèse centrale du lemme.
La fiche Sur-additive (suite) présente la version à inégalité inversée et aide à reconnaître le résultat dual.
La fiche Entropie éclaire une famille d’applications où l’existence d’un taux asymptotique est décisive.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres