🌀 nonlinear sciences

The information-theoretic complexity of differentiable functions

Cet article introduit la « complexité-V », une mesure informationnelle pour les fonctions différentiables fondée sur des approximations constantes par morceaux, postule son équivalence avec des métriques de compression de données et démontre son utilité pour définir la Complexité Effective de systèmes tels que la diffusion de crème dans le café, où la complexité atteint un pic durant la transition vers l'équilibre.

Auteurs originaux : Matthijs Ruijgrok

Publié 2026-05-19

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Matthijs Ruijgrok

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous essayez de décrire une image à un ami au téléphone. Certaines images sont faciles à décrire : « Un carré noir à gauche, un carré blanc à droite. » D'autres sont un cauchemar : « Une ligne sinueuse qui monte, descend, ondule trois fois, plonge, s'élève en pic, puis s'incurve... »

Ce papier traite de la création d'une « note » mathématique pour mesurer exactement à quel point il est difficile de décrire une ligne lisse et changeante (une fonction dérivable). L'auteur, Matthijs Ruijgrok, appelle cette note complexité-V.

Voici la décomposition des idées du papier en utilisant des analogies simples :

1. Le jeu « Pixellisé » (Fonctions en escalier)

Pour mesurer la complexité, le papier suggère de ne pas regarder la ligne lisse elle-même, mais plutôt de tenter de l'approcher à l'aide de fonctions en escalier.

L'analogie : Imaginez que vous avez un dessin lisse et courbe. Vous n'êtes autorisé à le redessiner qu'en utilisant un escalier. Vous ne pouvez tracer que des lignes horizontales plates et des chutes verticales.
L'objectif : Vous voulez correspondre au dessin original aussi étroitement que possible en utilisant le nombre d'escaliers le plus faible possible.
La règle : Vous avez droit à une infime marge d'erreur (l'« escalier » n'a pas besoin de toucher la ligne parfaitement, il doit juste rester proche).

Si la ligne originale est une courbe simple (comme une douce colline), vous pouvez l'approcher avec seulement quelques grands escaliers. Si la ligne est chaotique et sinueuse (comme un sismographe pendant un tremblement de terre), vous avez besoin de milliers de petits escaliers pour vous rapprocher.

La note de complexité-V est essentiellement un calcul de : Combien d'escaliers ai-je besoin, par rapport à la précision que je souhaite ?

Note faible : La fonction est simple (facile à décrire avec peu d'escaliers).
Note élevée : La fonction est complexe (nécessite beaucoup d'escaliers pour être décrite avec précision).

2. Le lien avec la « Compression »

L'auteur demande : « Cette méthode de « comptage d'escaliers » est-elle la même que celle utilisée par les ordinateurs pour compresser des fichiers ? »

L'analogie : Pensez au Codage par Longueur de Course (RLE). Si vous avez une chaîne de texte comme AAAAABBBBBCCCC, un ordinateur peut la compresser en 5A, 5B, 4C. C'est très court. Mais si le texte est ABCDEF... sans motifs répétitifs, le fichier reste long.
La découverte : Le papier émet l'hypothèse que la « complexité-V » (le nombre d'escaliers) est mathématiquement très proche de la capacité d'un ordinateur à compresser une version numérique de cette ligne.
- Une ligne simple (peu d'escaliers) = Facile à compresser (fichier court).
- Une ligne sinueuse (beaucoup d'escaliers) = Difficile à compresser (fichier long).

Le papier teste cela avec deux outils de compression courants (RLE et GZIP) et constate que pour des lignes lisses et prévisibles, le « nombre d'escaliers » et la « taille du fichier » racontent la même histoire.

3. L'expérience de la tasse de café (Systèmes complexes)

Pour montrer pourquoi cela importe, l'auteur applique ce concept à un problème classique de physique : le mélange de la crème dans le café.

Le dispositif : Imaginez une tasse où la moitié supérieure est de la crème pure blanche et la moitié inférieure est du café noir.
Le processus : Au fil du temps, ils se mélangent.
- Début : Deux couches distinctes. Très simple. (Faible complexité).
- Milieu : La frontière s'estompe. Vous avez du blanc, du brun clair, du brun foncé et du noir qui tourbillonnent ensemble. C'est l'état le plus « désordonné » et détaillé. (Haute complexité).
- Fin : Toute la tasse est d'un brun clair uniforme. Simple à nouveau. (Faible complexité).

L'auteur calcule la complexité-V de ce processus de mélange :

Simulation informatique : Ils ont simulé le mélange particule par particule (comme un automate cellulaire) et mesuré à quel point le motif était « compressible ».
Formule mathématique : Ils ont utilisé l'équation standard de diffusion (la formule mathématique décrivant comment la crème se répand) et calculé la complexité-V de la courbe résultante.

Le résultat : Les deux méthodes ont donné la même courbe exacte. La complexité a commencé basse, a grimpé à un pic lorsque le mélange était le plus chaotique, puis est redescendue à zéro alors que le café devenait uniforme.

4. Pourquoi la « Complexité Effective » importe

Le papier suggère une nouvelle façon de définir la « complexité » d'un système. Habituellement, les scientifiques disent qu'un système est complexe s'il contient beaucoup de bruit aléatoire. Mais ce papier soutient que la véritable complexité concerne les motifs réguliers (les « régularités perçues »).

Si un système est parfaitement ordonné (comme une ligne droite), il est simple.
Si un système est du chaos pur (bruit aléatoire), il est également simple à décrire (il suffit de dire « aléatoire »).
La véritable complexité est la zone « juste comme il faut » au milieu — où il y a assez de structure pour être intéressant, mais assez de variation pour être difficile à décrire.

Résumé

Le papier introduit une nouvelle règle appelée complexité-V pour mesurer à quel point une ligne lisse est « sinueuse » ou « détaillée ».

Elle compte combien d'« escaliers » vous avez besoin pour dessiner la ligne.
Elle prouve que ce comptage est essentiellement le même que la réduction de taille d'un fichier informatique si vous essayiez de compresser la ligne.
Elle montre que dans une tasse de café en train de se mélanger, la « complexité » monte et descend exactement comme notre intuition l'attend : simple au début, désordonnée au milieu, et simple à nouveau à la fin.

L'auteur conclut que cet outil nous aide à définir mathématiquement ce que nous entendons quand nous disons qu'un système est « complexe », comblant le fossé entre l'intuition visuelle et l'informatique.

Résumé technique : La complexité informationnelle des fonctions différentiables

Énoncé du problème
L'article aborde la difficulté de définir une mesure rigoureuse de la complexité des fonctions différentiables $f: [a, b] \to \mathbb{R}$ . Bien que la complexité soit un concept omniprésent dans des systèmes allant des modèles climatiques aux automates cellulaires, elle manque d'une définition unifiée. L'auteur postule que la complexité devrait correspondre à la quantité d'informations requise pour décrire un objet. Puisque les fonctions différentiables contiennent une information infinie, l'article propose de définir la complexité sur la base d'approximations finies. L'intuition centrale est qu'une fonction est « simple » si une bonne approximation peut être décrite avec peu de paramètres, et « complexe » si elle en nécessite beaucoup. L'article examine spécifiquement la relation entre la simplicité visuelle (perçue par l'œil humain comme des contrastes nets et des contours) et les mesures informationnelles.

Méthodologie
L'article introduit une mesure appelée complexité V, dérivée de l'approximation d'une fonction différentiable $f$ à l'aide de fonctions constantes par morceaux (fonctions en escalier). La méthodologie procède comme suit :

Cadre d'approximation : La fonction $f$ est approchée par une fonction en escalier $q$ telle que la norme $L_1$ de la différence, $||f - q||_1$ , soit inférieure à une erreur maximale $\epsilon$ . La norme $L_1$ est choisie par rapport à d'autres normes $L_p$ car elle correspond à la perception visuelle humaine, où l'emplacement précis d'une frontière nette (contraste) importe moins que l'existence du contraste lui-même.
Équirépartition de l'erreur : Pour minimiser le nombre d'intervalles $N(\epsilon)$ requis pour un $\epsilon$ donné, l'article utilise le principe de l'équirépartition de l'erreur. Cela consiste à construire une fonction en escalier où l'erreur sur chaque sous-intervalle est égale ( $||f - q_k||_{I_k} = \epsilon/N(\epsilon)$ ). L'article cite des preuves suggérant que cette méthode produit asymptotiquement le nombre minimal d'intervalles.
Analyse asymptotique : En transformant le calcul récursif des extrémités des intervalles en une équation différentielle lorsque $\epsilon \to 0$ , l'article déduit la relation d'échelle entre le nombre d'intervalles et l'erreur.
Comparaison avec la compression : Pour valider la complexité V, l'article la compare à la complexité par compression. Cela implique de discrétiser $f$ sur une grille, de convertir les valeurs en une chaîne de symboles, et d'appliquer des algorithmes de compression sans perte (Encodage par plages [RLE] et Lempel-Ziv 77 [LZ77/GZIP]). La complexité est définie comme le produit de la longueur de la chaîne compressée et de l'erreur d'approximation lorsque l'erreur tend vers zéro.
Application aux systèmes complexes : Le concept est appliqué au modèle de diffusion « crème dans le café ». L'article compare deux approches :
- Complexité apparente : Simulation du système via un automate à gaz sur réseau, grossissement de la sortie et mesure de la longueur compressée.
- Complexité effective modifiée : Modélisation du système via l'équation de diffusion (une fonction différentiable) et calcul de sa complexité V.

Contributions et résultats clés

Définition de la complexité V : L'article établit que pour une fonction différentiable $f$ , le nombre d'intervalles $N(\epsilon)$ nécessaire pour une approximation par fonction en escalier précise à $\epsilon$ évolue selon $N(\epsilon) \approx V(f)\epsilon^{-1}$ lorsque $\epsilon \to 0$ . Le préfacteur $V(f)$ est défini comme la complexité V :
$V(f) = \frac{1}{4} \left( \int_a^b |f'(x)|^{1/2} dx \right)^2$
Cette formule fournit une mesure analytique concrète de la complexité basée sur la dérivée de la fonction.
Exemples de comportement :
- Fonctions de type marche : Les fonctions qui convergent vers une fonction en escalier (par exemple, des fonctions sigmoïdes à pentes raides) ont une complexité V tendant vers zéro.
- Fonctions oscillantes : Pour des fonctions comme $\cos(n\pi x)$ , la complexité V croît linéairement avec le nombre d'oscillations $n$ , reflétant l'augmentation des détails.
- Fonctions plates : Les fonctions presque constantes (plates) présentent également une faible complexité V.
Hypothèse d'équivalence : L'article émet l'hypothèse que la complexité V est équivalente à la complexité RLE et, par extension, à la complexité GZIP (pour les séquences monotones ou à la limite de petites tailles de grille). Les simulations numériques sur des familles de fonctions (par exemple, $x^\alpha$ ) montrent une similarité qualitative entre la complexité V analytique et la complexité par compression empirique.
Application au modèle de diffusion : Dans le modèle crème dans le café, l'approche par automate cellulaire (complexité apparente) et l'approche par équation de diffusion (complexité V) produisent le même résultat qualitatif : la complexité commence à zéro (séparation), atteint un maximum lorsque l'interface se mélange et crée des gradients, puis revient à zéro lorsque le système atteint un équilibre uniforme.

Portée et affirmations
L'article affirme que la complexité V formalise l'intuition selon laquelle la simplicité visuelle correspond à un faible contenu informationnel. Elle sert de pont entre l'analyse statique et déterministe des fonctions et l'étude des systèmes complexes.

Plus précisément, l'article propose une modification de la définition de la complexité effective (CE). La CE standard est définie comme la longueur d'une description concise des régularités d'un système. Cependant, si les régularités sont décrites par une fonction différentiable, la longueur de la description est infinie. L'article suggère d'amender cette définition : la CE d'un système dont les régularités sont décrites par une fonction différentiable $f$ est simplement la complexité V de $f$ .

L'auteur note que l'équivalence entre la complexité V et la complexité par compression reste une hypothèse soutenue par des simulations plutôt qu'une preuve rigoureuse. De même, l'hypothèse selon laquelle l'équirépartition de l'erreur produit le nombre absolu minimal d'intervalles est traitée comme une hypothèse pratique forte. L'article conclut que la complexité V offre un outil prometteur pour caractériser les systèmes complexes décrits par des fonctions différentiables, bien que la généralisation aux fonctions à plusieurs variables et un éclaircissement théorique ultérieur soient réservés à des travaux futurs.

1. Le jeu « Pixellisé » (Fonctions en escalier)

2. Le lien avec la « Compression »

3. L'expérience de la tasse de café (Systèmes complexes)

4. Pourquoi la « Complexité Effective » importe

Résumé

Articles similaires