Intersection sans densité

Fermeture

Dans son article « Problème sur la densité d’un ensemble de naturels », Robert Ferréol introduit progressivement des notions et notations qui permettent de donner un sens à la proportion de certains ensembles d’entiers dans N (ou N), qu’on appelle densité asymptotique.

Ainsi la densité de l’ensemble des entiers pairs vaut 1/2, comme celle de l’ensemble des entiers impairs, et plus généralement l’ensemble des entiers congrus à r modulo pN vaut 1/p. L’ensemble des carrés, comme l’ensemble des nombres premiers, a une densité nulle.

Il est tentant d’exprimer ces valeurs en termes de probabilité, mais la densité ne satisfait pas plusieurs propriétés indispensable pour une loi de probabilité. Elle est certes toujours comprise entre 0 (densité du vide) et 1 (densité de l’ensemble des entiers), croissante pour l’inclusion, et étant donnés deux ensembles disjoints A et B admettant tous deux une densité asymptotique, la réunion AB en admet une aussi, qui est la somme des deux précédentes ; enfin elle est asymptotique, c’est-à-dire que deux ensembles qui ne diffèrent qu’en-deçà d’un certain entier ont la même densité ou n’en ont ni l’un ni l’autre. Mais la densité asymptotique n’est pas σ-additive (« sigma-additive »), ce qui est indispensable pour la notion de probabilité et plus généralement de mesure. Plus fondamentalement encore il est possible de trouver deux ensembles admettant chacun une densité mais dont l’intersection n’en a pas (et la réunion n’en a pas non plus dans ce cas). Le présent article donne quelques exemples d’ensembles pour lesquels diverses intersections n’admettent pas de densité.

Exemple de deux ensembles d’entiers

On note A l’ensemble des entiers pairs, et B défini par le fait que pour tout entier k ⩾ 0, l’intersection B ∩ ⟦4k, 4k+1 − 1⟧ est l’ensemble des entiers pairs de cet intervalle si k est pair, et l’ensemble des entiers impairs de cet intervalle si k est impair. Autrement dit, B est la différence symétrique entre A et la réunion des intervalles de la forme ⟦42k−1, 42k − 1⟧.

Il est assez clair que les ensembles A et B admettent tous deux une densité 1/2. Mais B coïncide avec A puis se dissocie de A alternativement sur des plages de longueur en progression géométrique. On peut faire le calcul de façon exacte, mais sur l’intervalle ⟦0, 42k − 1⟧ l’intersection AB est restreinte au premier quart donc sa proportion ne peut dépasser 1/4, tandis que sur l’intervalle ⟦0, 42k+1 − 1⟧, l’intersection AB contient les trois quarts des entiers pairs, donc contient une proportion supérieure à 3/8 des éléments.

Un exemple du même genre était déjà donné la thèse de Persi Diaconis, en remplaçant B par l’ensemble des nombre dont la parité est celle de leur nombre de chiffres.

Exemple avec trois ensembles d’entiers

On définit cette fois encore A comme l’ensemble des entiers pairs, mais B est l’ensemble des entiers congrus à 0 ou 1 modulo 4. On définit l’ensemble C par ses intersections avec les intervalles de la forme ⟦6k, 6k+1 − 1⟧ :

Alors les trois ensembles A, B, C admettent une densité 1/2, et leurs intersections deux à deux admettent une densité 1/4. Mais l’intersection ABC n’a pas de densité, car son intersection avec un intervalle de la forme ⟦6k, 6k+1 − 1⟧ est vide si k est pair mais contient le quart des entiers si k est impair.

Conjecture sur la réalisation d’une fonction booléenne

Soit nN. Étant donné un ensemble E de parties non vides de ⟦1, n (assimilable à une fonction booléenne avec n variables), existe-t-il des ensembles (A1, … , An) tels que pour tout S ⊂ ⟦1, n, l’intersection iS Ai admet une densité si et seulement SE ?