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 12, comme celle de l’ensemble des entiers impairs, et plus généralement l’ensemble des entiers congrus à r modulo p ∈ N∗ vaut 1p. 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 A ∪ B 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é 12. 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 A ∩ B est restreinte au premier quart donc sa proportion ne peut dépasser 14, tandis que sur l’intervalle ⟦0, 42k+1 − 1⟧, l’intersection A ∩ B contient les trois quarts des entiers pairs, donc contient une proportion supérieure à 38 des éléments.
Un exemple du même genre était déjà donné dans 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⟧ :
- si k est pair, C contient les entiers congrus à 1 ou 2 modulo 4
- si k est impair, C contient les entiers congrus à 0 ou 3 modulo 4.
Alors les trois ensembles A, B, C admettent une densité 12, et leurs intersections deux à deux admettent une densité 14. Mais l’intersection A ∩ B ∩ C 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 n ∈ N∗. É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 ⋂i∈S Ai admet une densité si et seulement S ∈ E ?