On the most informative Boolean function under noise

Dimiter Kramer; Mert Saglam

Résumé IA · arXiv: 2611.05430v1 · cs.IT

On the most informative Boolean function under noise

Dimiter Kramer, Mert Saglam

Article original Soumis à arXiv le 03 Nov. 2026 17 pages, 2 figures Licence : CC BY 4.0 Aussi en : en

Comment lire ce résumé ? Guide illustré

L’essentiel

L’article démontre une borne intermédiaire qui résout la conjecture de Courtade et Kumar : aucune fonction booléenne du vecteur bruité n’informe davantage sur l’entrée qu’une coordonnée.

Question

Pour un vecteur uniforme de bits dont chaque coordonnée est retournée indépendamment avec probabilité p, quelle fonction booléenne du vecteur bruité maximise l’information mutuelle sur le vecteur initial ? L’article vise à établir la conjecture de Courtade et Kumar selon laquelle une coordonnée bruitée est optimale.

Méthode

Les auteurs définissent une quantité « progressive » Q(C), combinant les entropies de Shannon et de Tsallis du bit de sortie C, et prouvent qu’elle encadre son information mutuelle avec l’entrée. La preuve est une induction sur le nombre n de coordonnées : elle choisit une coordonnée dont l’information de Tsallis avec C ne dépasse pas 1/4, puis établit l’étape inductive à l’aide de lemmes sur des bits et de développements en séries.

Résultats

Résultat Pour tout p entre 0 et 1, l’information mutuelle de C avec X est bornée par Q(C), elle-même bornée par l’information mutuelle d’une coordonnée bruitée avec X.
Interprétation des auteurs La borne supérieure établit que le choix d’une coordonnée bruitée atteint la valeur maximale de l’information sur X parmi les sorties booléennes de Y.
Voir le passage dans l’article
They conjecture that taking $C=Y_{i}$ for some $i\in[n]$ maximizes the information conveyed about $X$.
Résultat La preuve du premier encadrement procède par induction sur le nombre de coordonnées et repose sur le choix d’une coordonnée faiblement associée à C au sens de l’information de Tsallis.
Résultat La borne progressive n’est pas valable telle quelle pour la généralisation continue étudiée : l’indicatrice de seuil considérée dépasse Q pour les paramètres indiqués.

Limites

La borne progressive est propre au cadre discret et ne s’étend pas directement à la généralisation sur le cube continu présentée dans l’article.
Le problème continu reste formulé comme une conjecture : les auteurs ne démontrent pas que les fonctions seuil y maximisent l’information mutuelle.
Voir le passage dans l’article
We conjecture that the threshold functions maximize mutual information at each fixed mean.

Portée

Les auteurs présentent leur résultat comme une résolution de la conjecture de Courtade et Kumar, longtemps restée ouverte malgré des progrès partiels. La quantité Q fournit une borne intermédiaire plus fine que la borne classique de traitement de données forte, et sa démonstration repose sur une induction sur la dimension.

Rédigé par une IA à partir de l’article. Les passages cités sont vérifiés mot pour mot dans le texte analysé ; le reste peut contenir des erreurs.

Mots clés générés par l'IA : conjecture de Courtade–Kumar information mutuelle entropie de Tsallis contraction de l’information fonctions booléennes

Pour aller plus loin

Résumé Complet
Résumé vulgarisé
Article de blog
Abstract original

L’article étudie les fonctions booléennes d’une chaîne binaire bruitée qui conservent le plus d’information sur la chaîne d’origine. La variable $X$ est uniforme sur les chaînes de $n$ bits, et $Y$ s’obtient en inversant indépendamment chaque bit de $X$ avec une probabilité $p$. Pour tout bit $C$ calculé à partir de $Y$, la conjecture de Courtade et Kumar affirme que l’information mutuelle entre $C$ et $X$ ne dépasse pas celle que révèle un seul bit de $Y$, soit $1-h_2(p)$, où $h_2$ désigne l’entropie binaire. Les auteurs démontrent cette conjecture pour tout $p\in[0,1]$. Le résultat central est une borne plus précise, qui dépend de la moyenne de $C$. Les auteurs définissent une quantité $Q(C)$ combinant l’entropie de Shannon de $C$ et son entropie de Tsallis, cette dernière étant égale à quatre fois le produit des probabilités que $C$ vaille 1 et 0. La formule améliore une borne classique de contraction de l’information en lui ajoutant une correction proportionnelle à l’écart entre deux mesures de transmission du bruit. Le théorème établit l’encadrement \[ I(C;X)\leq Q(C)\leq 1-h_2(p). \] La borne classique de contraction forte ne fournit qu’une borne supérieure fondée sur $(1-2p)^2$, tandis que $Q(C)$ constitue un raffinement intermédiaire. La démonstration principale procède par récurrence sur le nombre $n$ de coordonnées. À chaque étape, les auteurs choisissent un bit $Y_i$ dont l’information de Tsallis avec $C$ ne dépasse pas $1/4$. Ils montrent ensuite que l’écart entre $Q(C)$ et l’information mutuelle entre $C$ et $X$ contrôle, à un facteur positif près, l’écart conditionnel obtenu après fixation de $Y_i$. Le problème se ramène ainsi à une chaîne comportant une coordonnée de moins. L’argument technique combine des comparaisons entre les informations de Shannon et de Tsallis, un bit auxiliaire sans biais construit à partir de $Y_i$, ainsi qu’une inégalité précise pour une chaîne de trois bits sans biais. Cette dernière est établie au moyen de développements en séries. Les auteurs prouvent la positivité de chacun des coefficients pertinents en bornant les restes de séries et en vérifiant la positivité d’une fonction scalaire. Le résultat valide donc la conjecture de Courtade et Kumar dans tout le régime de bruit, y compris aux extrémités $p=0$, $p=1/2$ et $p=1$. Les auteurs mentionnent également plusieurs preuves concurrentes annoncées en 2026, ainsi qu’une autre conséquence portant sur une généralisation aux variables continues. Dans le modèle continu, la borne $Q$ ne constitue toutefois pas une borne inférieure de l’information mutuelle pour certaines fonctions seuils. Lorsque la moyenne est strictement comprise entre 0 et 1 et différente de $1/2$, et que le niveau de bruit appartient à $]0,1/2[$, l’information associée au seuil est supérieure à $Q$.

Quelle fonction binaire préserve le mieux l’information sous le bruit ?

Une chaîne de bits peut être altérée par des erreurs aléatoires : chaque bit est inversé avec une certaine probabilité. Dans ce contexte, une question naturelle se pose : si l’on observe uniquement un bit calculé à partir de la chaîne bruitée, quelle quantité d’information cet unique bit peut-il conserver sur la chaîne d’origine ? Dans leur article On the most informative Boolean function under noise, Dimiter Kramer et Mert Saglam apportent une réponse complète à cette question.

Leur résultat démontre, pour tout niveau de bruit, une conjecture importante sur les fonctions booléennes. Il établit aussi une borne plus précise que les estimations classiques, en tenant compte de la moyenne du bit calculé.

Le modèle : une chaîne et sa version bruitée

Les auteurs considèrent une chaîne binaire uniforme de n bits, notée X. On crée ensuite une chaîne Y en inversant indépendamment chaque bit de X avec une probabilité p. Lorsque p est faible, Y ressemble beaucoup à X ; lorsque p vaut un demi, les bits de Y ne révèlent plus rien sur ceux de X.

On choisit une fonction booléenne de Y, c’est-à-dire une règle qui produit un seul bit C. Ce bit pourrait, par exemple, représenter la parité de certains bits de Y ou le résultat d’une autre opération logique. La question est de savoir combien d’information C conserve sur X, même si la fonction n’a accès qu’à la chaîne bruitée.

La conjecture de Courtade et Kumar

La conjecture de Courtade et Kumar affirme que, quelle que soit la fonction booléenne choisie, l’information mutuelle entre C et X ne peut pas dépasser celle que fournit un seul bit bruité. Cette limite vaut 1 moins l’entropie binaire de p. Autrement dit, aucune fonction booléenne de l’ensemble de la chaîne Y ne devrait révéler davantage sur X qu’un bit individuel de Y.

Kramer et Saglam démontrent cette conjecture pour toutes les valeurs de p entre zéro et un. La portée du résultat est donc générale : il couvre aussi bien les faibles niveaux de bruit que les régimes où les inversions sont fréquentes.

Une borne affinée grâce à la moyenne de C

Au-delà de la réponse à la conjecture, l’article établit une borne plus détaillée. Les auteurs définissent une quantité appelée Q(C), qui combine deux façons de mesurer l’incertitude sur le bit C : l’entropie de Shannon et l’entropie de Tsallis. Pour un bit, cette dernière est quatre fois le produit des probabilités que C vaille zéro et un.

Le théorème central donne l’encadrement suivant : l’information mutuelle entre C et X est au plus Q(C), et Q(C) est lui-même au plus 1 moins l’entropie binaire de p. La quantité Q(C) dépend de la distribution de C : elle prend donc en compte la fréquence à laquelle le résultat de la fonction vaut zéro ou un.

Cette borne affine une estimation classique de contraction forte de l’information, fondée sur le carré de 1 moins deux fois p. Au lieu de s’arrêter à cette contraction générale, Q(C) ajoute une correction liée à l’écart entre deux mesures de la transmission du bruit. Elle fournit ainsi une étape intermédiaire plus informative entre la borne classique et la limite de la conjecture.

Comment fonctionne la démonstration ?

La preuve principale procède par récurrence sur le nombre de bits. À chaque étape, les auteurs sélectionnent une coordonnée Yᵢ dont l’information de Tsallis avec C ne dépasse pas un quart. Ils montrent ensuite que l’écart entre Q(C) et l’information mutuelle entre C et X contrôle l’écart correspondant après fixation de cette coordonnée.

Cette réduction permet de ramener le problème à une chaîne comportant un bit de moins. Répétée, elle conduit finalement à des cas simples. La démonstration s’appuie également sur des comparaisons entre les informations de Shannon et de Tsallis, ainsi que sur l’introduction d’un bit auxiliaire sans biais construit à partir de Yᵢ.

Un autre élément technique essentiel est une inégalité précise pour une chaîne de trois bits sans biais. Les auteurs l’établissent à l’aide de développements en séries. Pour démontrer que les coefficients nécessaires sont positifs, ils encadrent les restes des séries et vérifient la positivité d’une fonction d’une seule variable. Ces étapes techniques soutiennent le résultat général obtenu par récurrence.

Les cas limites et une piste de recherche

La conjecture est également vérifiée aux trois régimes particulièrement parlants :

Pour p égal à zéro, la chaîne n’est pas bruitée.
Pour p égal à un demi, le bruit efface toute information sur la chaîne d’origine.
Pour p égal à un, chaque bit est systématiquement inversé.

Les auteurs évoquent aussi une généralisation à des variables continues. Dans ce cadre, toutefois, Q ne constitue pas toujours une borne inférieure de l’information mutuelle : pour certaines fonctions seuils, celle-ci peut être supérieure à Q lorsque la moyenne est comprise entre zéro et un, différente d’un demi, et que le niveau de bruit est strictement compris entre zéro et un demi.

Pourquoi ce résultat compte

L’article répond à une question fondamentale sur la transmission de l’information : une fonction ingénieuse peut-elle extraire d’une observation bruitée plus que ne le permet un bit isolé ? La réponse est non, et elle vaut pour toutes les probabilités de bruit. La borne affinée Q(C) ajoute une nuance utile en reliant la quantité d’information conservée à la distribution du résultat booléen. Ensemble, ces conclusions éclairent la manière dont le bruit limite l’information accessible par des fonctions binaires.

Créé le 09 Nov. 2026

Cette synthèse vous a-t-elle été utile ?

Note : 0

Posez des questions sur cet article à notre assistant IA

Comment discuter avec cet article ? Guide illustré

Comparer avec le PDF

Vous pouvez aussi discutez avec plusieurs papiers à la fois ici.

Instructions pour utiliser l'assistant IA ?

Outils pour cet article

Expliquer autrement 1 réécriture gratuite restante aujourd'hui

Enregistrer dans une collection Regroupez des articles en collections pour les comparer, les interroger et les exporter. Continuer avec Google Créer un compte gratuit Se connecter

Exporter BibTeX · RIS (Zotero, Mendeley, EndNote) · Obsidian (Markdown) · Notion (Markdown)

Outils avancés Premium

Pour suivre un domaine de près : alertes de citations, diapositives de journal club, comparaison des versions et envoi vers Zotero. Découvrir Premium

Zotero

Alertes de citation Guide des alertes de citations

Qui travaille dessus ? Les personnes et institutions qui publient sur son sujet

Lettre hebdomadaire Présenté dans « Informatique hors IA cette semaine » du 9 novembre 2026. Informatique hors IA cette semaine : des preuves aux épreuves du réel

Journal club Premium+ Des slides pour le présenter Proposer pour le journal club

Versions Ce qui a changé entre les versions

En parler en public Premium+ Kit presse : communiqué, questions, détecteur de hype Guide du kit presse

Avertissement : Notre outil de synthèse basé sur l'IA et l'assistant virtuel fournis sur ce site Web peuvent ne pas toujours fournir des résumés complets ou des réponses exactes. Nous vous encourageons à examiner attentivement et à évaluer le contenu généré pour vous assurer de sa qualité et de sa pertinence par rapport à vos besoins.

On the most informative Boolean function under noise

L’essentiel

Question

Méthode

Résultats

Limites

Portée

Pour aller plus loin

Definitions

Quelle fonction binaire préserve le mieux l’information sous le bruit ?

Le modèle : une chaîne et sa version bruitée

La conjecture de Courtade et Kumar

Une borne affinée grâce à la moyenne de C

Comment fonctionne la démonstration ?

Les cas limites et une piste de recherche

Pourquoi ce résultat compte

Posez des questions sur cet article à notre assistant IA

Outils pour cet article

Outils avancés Premium

Les articles autour de celui-ci

Les articles les plus proches

Les travaux antérieurs sur lesquels il s’appuie

Aller plus loin

Citer cet article (BibTeX)