Sous-additive (suite)

Imaginez que le nombre a_n mesure le coût d'un trajet de longueur n. Mettre bout à bout un trajet de longueur m et un autre de longueur n donne une solution possible pour la longueur m + n. Le meilleur coût direct ne peut donc pas dépasser la somme de ces deux coûts.

Cette idée est la sous-additivité. Elle n'impose pas que les termes diminuent : elle limite ce que coûte la réunion de deux tailles. À long terme, le coût moyen a_n/n finit par se stabiliser, ou tend vers moins l'infini lorsqu'il n'est pas minoré.

Soit une suite de nombres réels dont le terme d'indice n est noté a_n, pour tout entier positif n. Elle 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 correspondants : $a_{m+n}\le a_m+a_{n}a\_\{m+n\}\backslash leq\; a\_m+a\_n$. L'inégalité compare donc une taille réunie à une décomposition possible de cette taille. Elle autorise l'égalité comme une inégalité stricte.

Le lemme de Fekete porte sur les quotients obtenus en divisant chaque terme a_n par son indice n. Il affirme que ces quotients admettent une limite dans les réels étendus et que : ${\lim }_{n\to \mathrm{\infty }}\frac{a_n}{n}={\inf }_{n\ge 1}\frac{a_n}{n}\backslash lim\_\{n\backslash to\backslash infty\}\backslash frac\{a\_n\}\{n\}=\backslash inf\_\{n\backslash geq\; 1\}\backslash frac\{a\_n\}\{n\}$. La limite peut donc être −∞ ; si les quotients sont minorés, elle est un nombre réel. Elle n'est pas nécessairement atteinte par un indice particulier.

La propriété concerne l'addition des indices, pas celle des valeurs de la suite. Des suites associées aux entropies topologiques ou aux exposants de Lyapunov fournissent des cadres naturels où ce mécanisme intervient. La sous-additivité est également importante en théorie des probabilités et en dynamique symbolique.

Une suite sous-additive réunit cinq éléments. Les indices positifs m et n représentent deux tailles que l'on additionne. Les termes a_m, a_n et a_m+n associent un nombre réel à chacune de ces tailles. L'inégalité de sous-additivité exige que le terme de la taille réunie ne dépasse pas la somme des termes séparés.

Les quotients a_n/n traduisent ensuite la valeur moyenne par unité de taille. Leur infimum est la plus grande borne inférieure commune, même si aucun quotient ne lui est égal. L'inégalité permet de découper un grand indice en blocs ; ces découpages contrôlent les quotients lointains et conduisent à la limite donnée par le lemme de Fekete. Les valeurs précises des termes définissent la suite, tandis qu'un tracé ou une échelle graphique ne fait que la représenter.

Considérons la suite définie par $a_n=\lceil \frac{n}{2}\rceil a\_n=\backslash left\backslash lceil\backslash frac\; n2\backslash right\backslash rceil$, où n est un entier positif. Ses huit premiers termes sont 1, 1, 2, 2, 3, 3, 4 et 4.

1. Les arrondis supérieurs de m/2 et n/2 majorent séparément ces deux nombres. Leur somme, qui est entière, majore donc l'arrondi supérieur de (m + n)/2. La sous-additivité est vérifiée pour tout couple.

2. Pour m = 3 et n = 4, a₇ = 4 et a₃ + a₄ = 2 + 2 = 4. Avec m = n = 1, l'inégalité est stricte : a₂ = 1 < 2.

3. Les quotients pour n de 1 à 8 valent successivement 1, 1/2, 2/3, 1/2, 3/5, 1/2, 4/7 et 1/2. Ils oscillent donc au lieu de décroître régulièrement.

4. Les indices pairs donnent exactement 1/2. Pour un indice impair n, le quotient vaut 1/2 + 1/(2n), qui tend vers 1/2. La limite et l'infimum valent donc 1/2.

Pour étudier un coût minimal dépendant d'une taille, on cherche si deux solutions peuvent être concaténées. Si cette réunion fournit une solution admissible, les coûts optimaux sont souvent sous-additifs et le lemme de Fekete donne alors un coût moyen asymptotique.

En théorie des probabilités, on repère de même une quantité portant sur deux portions successives. Lorsque la quantité totale est majorée par la somme des deux portions, la sous-additivité est le bon cadre ; si l'inégalité va dans l'autre sens, il faut employer la sur-additivité.

En dynamique symbolique, ainsi que pour certaines suites liées aux entropies topologiques ou aux exposants de Lyapunov, on découpe le temps en blocs. Le geste utile consiste à établir l'inégalité pour deux blocs quelconques avant d'étudier la valeur moyenne par unité de temps.

Suite sur-additive. Elle vérifie l'inégalité opposée : le terme d'indice m + n est au moins égal à la somme des termes d'indices m et n. Le test m = n = 1 tranche dans l'exemple guidé : a₂ = 1 est inférieur à a₁ + a₁ = 2, donc cette suite n'est pas sur-additive.

Suite sous-multiplicative. Elle compare le terme d'indice m + n au produit a_ma_n, et non à leur somme. Lorsque ses termes sont strictement positifs, prendre leurs logarithmes peut transformer cette relation multiplicative en sous-additivité.

Suite décroissante. Elle compare deux indices ordonnés, par exemple n et n + 1. La sous-additivité compare au contraire trois termes liés par une addition d'indices. Dans l'exemple, a₂ = 1 puis a₃ = 2 : la suite augmente malgré sa sous-additivité.

Tester quelques couples ne suffit pas. L'inégalité doit valoir pour tous les entiers positifs m et n. Des essais numériques peuvent révéler un échec, mais une preuve générale doit expliquer pourquoi tout couple convient.

Les quotients ne sont pas forcément monotones. Dans l'exemple, ils passent de 1/2 à 2/3 puis reviennent à 1/2. Il faut utiliser la conclusion du lemme de Fekete, et non supposer une décroissance terme à terme.

L'infimum peut ne jamais être atteint. Une borne inférieure n'est pas nécessairement un minimum. La conclusion correcte porte sur la limite des quotients et leur infimum commun, sans exiger l'existence d'un indice réalisant cette valeur.

La limite peut valoir −∞. Sans minoration des quotients a_n/n, le lemme s'entend dans les réels étendus. Pour conclure à une limite réelle finie, il faut donc établir une borne inférieure supplémentaire.

Le glossaire Fekete (lemme de) approfondit le passage de l'inégalité sous-additive à la limite des quotients et à leur infimum.

La fiche Sur-additive (suite) présente l'inégalité opposée et aide à choisir le cadre adapté au sens de la comparaison.