Comment empoisonner efficacement tous les grands rats

Piste noire Le 12 décembre 2009  - Ecrit par  Roland Bacher Voir les commentaires

Je propose de décrire la genèse d’un article de recherche et son résultat principal : Il existe un ensemble relativement petit du plan qui rencontre tous les triangles d’aire assez grande. En parsemant le plan de doses de poison disposées selon cet ensemble, on empoisonne tous les rats (qui ont approximativement une forme triangulaire) qui occupent une aire suffisamment grande [1].

Mon université (il s’agit de Grenoble I) publie de temps en temps en interne quelques résultats issus de ses laboratoires de recherche et mes chefs m’ont demandé de rédiger un petit texte vulgarisant un résultat récent.
J’ai donc essayé de décrire de manière simple le contenu de [B] et j’ai recyclé cet essai en le soumettant à « Images des Mathématiques ». Les éditeurs d’IdM m’ont alors suggéré d’y incorporer des éléments de la genèse du résultat exposé pour illustrer par un exemple concret un travail de recherche en mathématique. Le résultat final est actuellement devant vos yeux.
Il n’a pour le moment pas d’application pratique autre que celle suggérée par
le titre car il montre comment disposer des doses de poison permettant de
se débarrasser de tous les rats occupant une surface assez grande en
supposant qu’un rat a approximativement la forme d’un triangle isocèle dont
on ne contrôle pas l’allongement et que le poison n’agit que par contact direct.

Genèse d’un article de maths

Il y a un peu moins d’une année, je me suis inscrit à un petit colloque de trois jours à Paris. Il s’agissait plus précisément d’une
conférence en l’honneur des 60 ans de Philippe Flajolet.

Quelques jours avant le congrès, j’apprends qu’un de mes collègues grenoblois, Didier Piau, participe également à ce colloque. Le jour du départ, vers six heures du matin, je réfléchis dans le tram qui me mène à la gare à un problème qui
pourrait alimenter la conversation avec Didier dans le TGV. L’idée me vient alors à l’esprit de l’interroger sur ce que l’on sait sur « les convexes qui ne rencontrent pas un ensemble aléatoire de points ».

Finalement, je n’étais pas assis dans le même wagon que Didier ! Nous ne nous sommes retrouvés que sur le quai de la gare de Lyon. J’avais cependant passé les trois heures du voyage Grenoble-Paris à réfléchir au problème que je trouvais amusant.

Petit à petit quelque chose comme la question 1 ci-dessous s’est cristallisée et j’ai essayé sans succès de construire un ensemble de points de densité uniforme qui rencontre tous les convexes du plan d’aire assez grande.

J’ai commencé à poser la question de l’existence d’un tel ensemble à un certain nombre de collègues sans obtenir de réponse. Ainsi, un jour où la porte du bureau voisin était ouverte, je pose ma question à Yves Colin de Verdière qui me suggère de commencer par chercher un ensemble un peu plus « gros ». Quelques jours plus tard, j’avais trouvé ma solution.

Il y a bien sûr eu quelques tâtonnements et fausses pistes mais en nombre assez petit. Tout le travail, y compris la rédaction, a pris environ un mois, ce qui est une durée inhabituelle pour un travail de recherche [2]. Normalement
il faut plusieurs mois ou même plusieurs années avant d’aboutir
(il existe bien sûr quelques extraterrestres, comme par exemple Terence Tao, qui font exception).

Il m’est cependant pratiquement impossible d’estimer, même très approximativement, le nombre d’heures que j’ai passées sur ce problème. Il n’est pas nécessaire d’être assis à son bureau avec du papier et un crayon pour réfléchir. Personnellement, je trouve souvent utile d’aller me promener (de préférence en forêt) [3]
quand je veux approfondir une question. La seule indication que je travaille est alors le fait que je reconnais encore moins que d’habitude une connaissance éventuelle rencontrée par hasard.

De plus, une composante importante du travail de recherche est une espèce de rêverie durant laquelle on fait des raisonnements du style « et si on avait ... alors » ou « ce serait joli si on avait ... ». Ce genre de pensées spéculatives pas forcément très rigoureuses et parfois fondées sur des critères esthétiques permet de se forger une intuition du problème et indique des voies prometteuses pour l’attaquer. En effet, il n’est pas nécessaire d’avoir un esprit logique sans faille pour faire des maths mais il faut peut-être plutôt de l’imagination et la capacité d’acquérir une sorte d’intuition concernant les objets abstraits qu’on manipule.

La démonstration d’une assertion par des enchaînements logiques n’est que le produit final du travail. On peut peut-être comparer un texte mathématique à une partition de musique. Ce qui compte, ce ne sont pas les notes écrites sur la partition mais le morceau de musique qui est derrière. Il faut un long et fastidieux apprentissage pour pouvoir entendre dans sa tête un morceau de musique à partir de la lecture d’une partition (surtout si on n’a encore jamais écouté le morceau en question). Heureusement qu’il y a les lecteurs de CD ! Pour les maths, l’équivalent du lecteur de CD fait cruellement défaut et il faut également un long apprentissage pour « entendre des maths dans la tête » à partir d’une « partition mathématique » dont les clés, les portées et les notes, sont des définitions, propositions et preuves.

Je termine ici cette petite digression et je reviens à mes moutons ou plutôt
à mon article. Je l’ai déposé sur arXiv (un serveur de prépublications) après une péripétie amusante : arXiv l’a d’abord automatiquement refusée car ma prépublication ne contenait aucune référence bibliographique ! [4] Il semble qu’arXiv effectue une sorte de contrôle de qualité automatisé pour lequel l’absence de données bibliographiques est éliminatoire. J’ai donc refait un passage sur MathScinet pour créer une liste bibliographique mentionnant deux articles traitant des problèmes voisins.

Une fois l’article déposé, je l’ai signalé à quelques collègues ainsi qu’à deux spécialistes des ensembles convexes pour un éventuel retour. Les réactions à des prépubs (en tout cas aux miennes) sont relativement rares, à part un « ça a l’air marrant » poli des copains. Ceci est d’ailleurs plutôt positif, car les gens ne se privent généralement pas d’écrire « tu devrais lire le papier de Yangtse et Bilboquet écrit en ourdou et paru en 1908 dans le Journal mathématique du Kamtchatka » pour signaler à l’auteur que ses résultats sont connus depuis les temps bibliques mais qu’il fait par contre fort mal son travail en ignorant tout de l’article sublime de Yangtse et Bilboquet.

La prochaine étape est le choix d’un journal (il en existe plusieurs centaines). Comme mon résultat principal était assez facile mais un peu surprenant (mon mérite étant principalement d’avoir été par chance la première personne à s’intéresser à ce genre de question) j’ai opté pour une revue généraliste de bon niveau. Comme je voulais de plus éviter les éditeurs commerciaux pratiquant des tarifs d’usuriers [5], le choix s’est encore restreint et
j’ai finalement soumis mon manuscrit au triptyque « Proceedings, Journal and Bulletin of the London Mathematical Society » (le choix du journal appartient aux rédacteurs, essentiellement selon la longueur de l’article) édité par une société savante.

Après quelques mois d’attente (fébrile et beaucoup trop longue quand on soumet son premier article ; ensuite on devient plus stoïque, surtout après avoir été sollicité quelque fois comme rapporteur (on dit aussi referee)) on apprend la décision des rédacteurs : acceptation (peut-être après modifications) ou refus de l’article, parfois brièvement argumenté par un éditeur et généralement pimenté par l’avis et les commentaires du rapporteur anonyme.

C’est donc soit un moment de fête, soit le début d’une réécriture avec recherche d’un autre journal en cas de refus modéré, soit la cheminée (par exemple après mention par le rapporteur de l’existence de ces plagiaires munis d’une machine à voyager dans le temps que sont Yangtse et Bilboquet).

L’acceptation ou le refus n’est pas forcément une indication fiable de qualité : Le système de l’édition scientifique est humain et commet des erreurs :
Le choix du rapporteur, les préférences des éditeurs, la pression (nombre d’articles soumis et nombres d’articles acceptés en attente de publication) sont des impondérables sur lesquels l’auteur n’a pas de prise.

Cette fois-ci, j’ai eu de la chance : assez vite, j’ai reçu une

des rédacteurs du « Bulletin de la LMS » qui contenait aussi
les

J’ai donc effectué les dernières petites retouches et je l’ai fait relire partiellement par une collègue anglophone avant d’envoyer la version définitive destinée à l’imprimeur. Récemment, j’ai reçu les épreuves pour une dernière relecture. La parution de l’article ne devrait maintenant plus trop tarder. Après il vivra sa propre vie, sera indexé par MathScinet et Zentralblatt et aura, j’espère, quelques lecteurs intéressés qui pousseront peut-être le travail plus loin.

Description de l’article

Une assertion évidente est généralement affublée de l’épithète « triviale » par
les mathématiciens. Un bon exemple est la phrase suivante :

Tout intervalle (de la droite réelle) de longueur plus grande que $1$ contient un nombre entier.

Je dirai que le contenu de mon article est la généralisation de cette trivialité
aux dimensions supérieures
 [6].
Pour simplifier, je me limite dans la suite au cas
de la dimension $2$. Le cas général n’est cependant guère plus
difficile, voir [B] pour les détails.

Le début de la généralisation consiste à trouver l’équivalent en dimension $2$ d’un intervalle et d’une longueur.
Un intervalle [7] peut se définir comme un ensemble de points délimité par deux extrémités. Ceci suggère
de remplacer « intervalle » par « triangle » car un triangle est délimité par trois points du plan : ses sommets.
Le rôle de la longueur
est bien sûr joué par l’aire du triangle
.

Une autre possibilité

Une autre possibilité consiste à remplacer les intervalles,
c’est-à-dire les sous-ensembles convexes de la droite
réelle, par les sous-ensembles convexes du plan. Un sous-ensemble $\mathcal C$ du plan est convexe si $\mathcal C$ contient tout segment dont les extrémités appartiennent à $\mathcal C$. Un habitant d’un pays convexe n’a donc jamais besoin de son passeport s’il veut aller voir de toute urgence un ami habitant ce même pays.

Deux domaines convexes (en bleu) et trois domaines non-convexes (en rouge) du plan. {JPEG}

Il s’avère que les deux choix
sont équivalents pour les questions qui nous intéressent.
La raison est donnée par le fait que tout convexe fermé $\mathcal C$ du plan contient un triangle d’aire au moins le quart de l’aire du convexe $\mathcal C$.

Un grand triangle contenu dans un domaine convexe {JPEG}

Voici deux preuves de ce fait :

Preuve 1 Travaillons pour simplifier avec des convexes fermés et choisissons deux points $A$ et $B$ de $\mathcal C$ qui sont à distance maximale. Notons $l$ la distance de $A$ à $B$. Le convexe $\mathcal C$ est alors inclus dans la bande de largeur $l$ délimitée par les deux droites $L_A$ et $L_B$ qui passent respectivement par $A$ et par $B$ et qui sont orthogonales à la droite passant par $A$ et $B$. Soit $C$ un point de $\mathcal C$ qui est à distance maximal du segment $[A,B]$ reliant $A$ à $B$ et soit $d$ cette distance. L’ensemble convexe $\mathcal C$ contient alors le triangle $T$ de sommets $A,B,C$ qui est d’aire $ld/2$. Notons $A_1,A_2$ et $B_1,B_2$ les
deux points de la droite $L_A$ respectivement $L_B$ qui sont à distance $d$ de $A$ respectivement de $B$. Le convexe $\mathcal C$ est alors inclus dans le rectangle de sommets $A_1,A_2,B_1,B_2$ de longueur $l$ et de largeur $2d$ qui est donc d’aire $2ld=4 \mathop{Aire}(T)=4(ld/2)$.

Preuve 2 Commençons avec
un triangle $T$ de sommets $A,B,C$ contenu dans $\mathcal C$ qui est
d’aire maximale parmi tous les triangles contenus dans $\mathcal C$. Dénotons par $L_A$ la droite passant par $A$ qui est
parallèle à la droite passant par $B$ et $C$. Comme le triangle
$T$ est d’aire maximal,
le convexe $\mathcal C$ est contenu dans un demi-plan fermé
délimité par $L_A$. Plus exactement, $\mathcal C$ est contenu
dans le demi-plan fermé $D_A$ délimité par $L_A$ qui contient les
points $B$ et $C$. Introduisons de manière analogue les demi-plans
fermés $D_B$ et $D_C$. Le convexe $\mathcal C$ est donc un sous-ensemble
de l’intersection des trois demi-plans fermés $D_A,D_B,D_C$. Cette
intersection est un triangle qui est une réunion de quatre copies
isométriques de $T$. L’aire de $\mathcal C$ est donc au plus quatre fois
plus grande que l’aire de $T$.

Ici, je ne résiste pas au plaisir d’une petite digression : Le rapport $4$ entre l’aire maximale d’un triangle contenu dans un convexe donné et l’aire de ce convexe trouvé dans les deux preuves n’est pas optimal. On peut
par exemple l’améliorer en combinant les deux preuves.
Je crois (mais j’avoue que je n’ai pas beaucoup réfléchi) que la plus petite valeur possible pour ce rapport est
$4\pi/\sqrt{27}$ qui vaut environ $2,4184$ et que ce rapport est uniquement réalisé quand $\mathcal C$ est une ellipse. En effet, comme ce rapport est invariant par transformations affines, il est le même pour une ellipse ou pour un cercle et on peut montrer que le triangle d’aire maximale inscrit dans un cercle est équilatéral. Un petit calcul donne alors la valeur $4\pi/\sqrt{27}$ pour le rapport entre l’aire d’un triangle équilatéral et l’aire de son cercle circonscrit.

Cette petite digression est une autre illustration du travail de recherche en mathématique : Un raisonnement secondaire peut suggérer une nouvelle question intéressante. On peut alors choisir de poursuivre l’exploration de la question initiale ou de la nouvelle question. On bifurque ainsi soit parce qu’on n’avance plus sur la question initiale, soit pour un critère esthétique et de goût (par exemple parce que la nouvelle question paraît plus profonde que la question initiale, soit en suivant simplement « son pif » (mon mode opératoire préféré). Ce phénomène est bien illustré par la boutade suivante : « Posez un problème ouvert à un mathématicien. Il donnera une solution approximative à votre problème s’il fait des mathématiques appliqués et il vous donnera la solution exacte d’un problème qui n’a rien à voir avec votre question s’il fait des mathématiques (dites) pures ». Peut-être qu’un jour je décide de revenir sur cette petite question annexe. J’essairai alors de savoir si le problème a déjà été regardé ce qui n’est pas si facile car je ne peux pas poser la question telle quelle à Google ou à MathScinet. En cas de recherche fructueuse ou de réponse par un collègue, je m’informe de ce qui est connu. Le fait que je ne trouve rien dans la littérature ne prouve évidemment pas qu’il n’existe rien :
j’ai peut-être raté la fameuse monographie de 1500 pages de Yangtse et Bilboquet qui est entièrement dévolue au sujet (ce qui me vaudra plus tard un avis cinglant du rapporteur anonyme chargé d’évaluer mon œuvre, désormais destinée à la cheminée).

Si la question n’a pas été balayée dans les moindre recoins, je commence à réfléchir avec l’espoir de trouver des preuve ou des contre-exemples concernant les assertions sans réponse. En cas de succès, le résultat (donnant la réponse à la question : « Le rapport maximal .... vaut-il $4\pi^2/\sqrt{27}$ ? ») peut faire l’objet d’une petite note qui traitera d’ailleurs pas seulement le cas des triangles inscrits mais également le cas probablement pas plus difficile des polygones inscrits ayant un nombre fixé $\geq 3$ quelconque de sommets et de côtés. J’essaierai probablement aussi à traiter la question analogue (obtenue en remplaçant ellipse par ellipsoïde de dimension $n$ et triangle par $n-$simplexe) en dimension arbitraire.

Je travaillerai dorénavant avec des triangles du plan
 [8]

La question qui se pose est la suivante :

Quelle est la taille minimale d’un ensemble $\mathcal S$
(généralisant l’ensemble $\mathbb Z$ des entiers dans le cas de la dimension $1$) du plan
tel que le complémentaire de $\mathcal S$ ne contienne aucun triangle d’aire $>C$ pour une certaine constante $C$ strictement positive ?

En faisant une homothétie de rapport
$1/\sqrt{C}$, on peut se ramener au cas $C=1$. Dans la suite, on ne prêtera
aucune attention à la valeur exacte de la constante $C$, seule son
existence est importante.

Il faut bien sûr clarifier la question ci-dessus en précisant
ce qu’on entend par « taille minimale ». La bonne définition
s’obtient de nouveau en s’inspirant du cas unidimensionnel.
Pour un nombre réel positif $R$ fixé, l’ensemble des réels contient environ $2R$ entiers à distance au plus
$R$ de l’origine : voici une autre trivialité !

On voudrait donc travailler avec un ensemble $\mathcal S$
tel que
$\mathcal S$ ne contienne pas trop de points à distance $\leq R$
de l’origine pour tout
nombre réel $R$ assez grand. Autrement dit,
je m’intéresse à la croissance quand $R$ tend vers l’infini du
nombre de points communs à $\mathcal S$
et au disque (fermé) de rayon $R$ et centré à l’origine.

Rappelons que nous cherchons un ensemble $\mathcal S$ qui rencontre
tout triangle d’aire assez grande.

L’inspection d’un pavage du plan par des copies isométriques d’un triangle d’aire assez grande montre alors que le nombre de points de $\mathcal S$ dans un disque de rayon $R$ suffisamment grand est au moins proportionnel à l’aire $\pi R^2$ de ce disque.

Je donne ici une preuve détaillée en utilisant un pavage carré du plan, un
peu plus facile à mettre en œuvre.

Soit $\mathcal S$ un ensemble de points qui intersecte tout
triangle d’aire plus grande qu’une constante $C$. Comme on peut
découper un carré d’aire $3C$ en deux triangles d’aire $3C/2>C$,
l’ensemble $\mathcal S$ intersecte l’intérieur de tout carré
dont les côtés sont de longueur $l=\sqrt{3C}$.
Considérons un disque $D$ de rayon $R>2\sqrt{2}l$.
Notons $D'\subset D$ le disque concentrique de rayon $R/2$.
Considérons un carré d’aire $3C$ qui intersecte $D'$.
Comme le diamètre $\sqrt{2}l$ d’un tel carré est inférieur
à la distance $R/2$ de $D'$ au bord de $D$, un tel carré est
contenu dans le disque $D$. Il s’ensuit qu’on
peut entièrement recouvrir $D'$ par un pavage
qui n’utilise que des carrés de volume $3C$ contenus
dans $D$. L’aire d’un tel pavage partiel du plan est au moins égal à
l’aire $(R/2)^2\pi$
du disque $D'$. Le nombre de carrés d’un tel pavage est donc
au moins égal à
$(R/2)^2\pi/(3C)$. Comme l’intérieur de chaque
carré d’un tel pavage contient au moins un point de $\mathcal S$,
le disque $D$ de rayon $R$ contient au moins
$R^2\pi/(3C)$ points de $\mathcal S$.

Le cas de la dimension $2$ du résultat principal de [B]
s’énonce alors comme suit :

Théorème  : Il existe un ensemble $\mathcal S$ du plan euclidien $\mathbb R^2$ ayant les deux propriétés suivantes :

(i) Un triangle ne contenant aucun point de $\mathcal S$ est
d’aire au plus $C$ pour une certaine constante $C$.

(ii) L’ensemble $\mathcal S$
contient au plus $R^2\mathop{log}R$ points à distance au plus $R$ pour
tout $R$ assez grand.

Comme le logarithme est une fonction à croissance très lente,
ce résultat montre que le nombre de points de $\mathcal S$
dans un grand disque est « presque » proportionnel l’aire du disque.

Ce théorème est bien une généralisation de la trivialité
de départ :

Tout triangle d’aire assez grande contient un point
de l’ensemble $\mathcal S$ et l’ensemble $\mathcal S$ est en
quelque sorte « petit ».

L’énoncé du théorème est cependant bien moins intuitif
que son analogue en dimension $1$.
En particulier, l’ensemble $\mathbb Z^2$ des
points à coordonnées entières ne fournit pas un ensemble $\mathcal S$
convenable. En effet, le triangle de sommets $(-A,1/4),(0,3/4),(A,1/4)$
ne contient aucun point de $\mathbb Z^2$ et son aire
$\vert A\vert/2$ peut être rendue aussi grande qu’on veut par un
choix convenable du nombre réel $A$.

La preuve du théorème

Il s’agit d’une preuve constructive dans le sens qu’elle ne se limite pas à démontrer l’existence d’un tel ensemble $\mathcal S$ mais
qu’elle décrit la construction d’un ensemble $\mathcal S$ avec les propriétés requises.

Plus précisément, l’ensemble $\mathcal S$ est la réunion des points
de $\mathbb Z^2$ ayant deux coordonnées entières et de
tous les points rationnels $(a,b)$ qui vérifient la
condition suivante :

Le produit $ab$ est un entier non nul, et
les dénominateurs de $a$ et de $b$ sont des puissances de $2$.

(Autrement dit, les deux coordonnées $a,b$ sont non nulles et une des deux
coordonnées est un entier divisible par une puissance de deux qui est le dénominateur
de l’autre coordonnée. )

Le point $(\frac{7}{4},-8)$ par exemple appartient à
$\mathcal C$ mais pas les points $(\frac{7}{8},-4)$, $(\frac{3}{2}, \frac{5}{4})$ ou encore $(\frac{2}{3},6)$.

Une partie de l'ensemble {JPEG}

La présence possible de puissances de $2$ aux dénominateurs
est responsable du
facteur logarithmique dans le théorème. L’absence de triangles
d’aire grande dans le complémentaire de $\mathcal S$ est dûe au
fait qu’un triangle est soit assez « gros »
(c’est-à-dire le rayon de son cercle inscrit n’est pas beaucoup
plus petit que le rayon de son cercle circonscrit), soit fin mais
très long.

Un gros triangle d’aire assez grande contiendra un point
de $\mathcal S$ car $\mathcal S$ contient l’ensemble $\mathbb Z^2$
des points à coordonnées entières
tandis qu’un triangle fin mais très long contiendra un point
dont soit l’abscisse soit l’ordonnée est divisible par
une grande puissance de
$2$. Au voisinage d’un tel point,
un triangle ne rencontrant pas $\mathcal S$ doit
passer par un « chas d’aiguille » (les petites ouvertures
entre deux points très proches de la Figure 1) délimité
à un signe près par deux points de la forme
$(\frac{2m-1}{2^n},2^n(2k+1)),(\frac{2m+1}{2^n},2^n(2k+1))$ ou
$(2^n(2k+1),\frac{2m-1}{2^n}),(2^n(2k+1),\frac{2m+1}{2^n})$.
Ceci permet de borner son aire.

Cet argument résume bien la preuve
mais il est un peu trop simple pour être juste.
Il faut en effet encore s’assurer que le chas d’aiguille utilisé
ne se trouve pas trop près d’un sommet d’angle aigu
du triangle. Ceci complique un peu la preuve et
illustre bien un fait qu’on rencontre souvent en mathématique :
Un argument simple et
intuitivement plausible n’est souvent pas complètement
rigoureux. Il peut cependant parfois servir comme point de
départ d’une preuve.
Les rustines nécessaires pour réparer les trous
amènent des complications techniques et nécessitent des
détours qui ne paraissent pas naturels.
Ceci est une des raisons pour lesquelles la lecture de textes
mathématiques est parfois difficile.

Le lecteur intrépide trouvera ici une preuve complète que l’ensemble $\mathcal S$ satisfait la condition (i).

Nous voulons prouver que tout triangle ne rencontrant pas $\mathcal S$ est d’aire bornée.

Soient $A=(x_A,y_A),B=(x_B,y_B),C=(x_C,y_C)$ les trois sommets d’un tel triangle $T$.

Introduisons les quatre nombres $m_x=\min(x_A,x_B,x_C),M_x=\max(x_A,x_B,x_C),m_y=(\min(y_A,y_B,y_C)$ et $M_y=\max(y_A,y_B,y_C)$. Si $M_x-m_x\leq 4$ et $M_y-m_y\leq 4$,
le triangle $T$ est contenu dans le rectangle de sommets
$(m_x,m_y),(M_x,m_y),(m_x,M_y),(M_x,M_y)$ qui est d’aire
$(M_x-m_x)(M_y-m_y)\leq 4\cdot 4=16$.

Sinon, soit l’intervalle $[m_x,M_x]$
soit l’intervalle $[m_y,M_y]$ formés des abscisses ou ordonnées de $T$ est de longueur plus grande que $4$. Supposons qu’on ait $M_x-m_x>4$ (le cas
$M_y-m_y>4$ est complètement analogue) et notons $l=M_x-m_x>4$ la longueur de l’intervalle $[m_x,M_x]$. contenant les abscisses de tous les
points de $T$.

Coupons cet intervalle en quatre sous-intervalles $[m_x,m_x+l/4]$, $[m_x+l/4,m_x+l/2]$, $[m_x+l/2,m_x+3l/4]$,
$[m_x+3l/4,m_x+l]=[m_x+3l/4,M_x]$ de même longueur $l/4$.
Choisissons parmi les deux intervalles $[m_x+l/4,m_x+l/2]$, et $[m_x+l/2,m_x+3l/4]$ un qui ne contient pas zéro en son intérieur.
Notons le $[a,b]$.

Un triangle fin (en bleu) passant par un chas d'aiguille (en rouge) qui délimite un parallélipipède d'aire au plus contenant {JPEG}

Comme $l$ est strictement plus grand que $4$, il existe un entier naturel
$n$ tel que $2^n est alors de longueur $>1$ et il contient donc un entier $N$ en son intérieur ce qui implique
que $[a,b]$ contient l’entier $2^n N$ divisible par $2^n$. Remarquons
que $N$ est non-nul car zéro n’appartient pas à l’intervalle ouvert
$(a,b)$.

Comme le triangle
$T$ ne rencontre pas $\mathcal S$, la construction de $\mathcal S$ montre
que l’intersection du triangle $T$ avec la droite
définie par l’équation $x=2^n N$ est un segment de longueur au plus
$1/2^n$. Quitte à renommer les sommets de $T$, je peux supposer
que les nombres $m_x$ et $M_x$ sont les abscisses des sommets
$A$ et $B$.

En utilisant Thalès, on voit que le triangle $T$ est contenu
dans le parallélipède de sommets $[x_A,y_A-4/2^n],[x_A,y_A+4/2^n], [x_B,y_B-4/2^n],[x_B,y_B+4/2^n]$ et d’aire $8l/2^n$.
La définition de $n$ montre que $2^n\geq l/8$ et le triangle $T$ est donc contenu dans un parallélogramme d’aire bornée par $8l/(l/8)=64$. Ceci
termine la preuve car ces arguments montrent
que tout triangle d’aire au moins 64 contient un point de $\mathcal S$
(on peut facilement remplacer $64$ par $16$ en regardant un peu
plus finement).

La preuve que $\mathcal S$ remplit également la condition (ii) n’est
guère plus difficile.

Voir ici pour l’idée de la démonstration.

Calculons le nombre de points de $\mathcal S$ dont les coordonnées
appartiennent à $[-2^n,2^n]$. A part l’origine, ces points ont soit une abscisse soit une ordonnée entière non-nulle. Le nombre de tels points est donc majoré
par $1+4a(n)$ où $a(n)$ est le nombre de points dans l’intersection $A(n)$ de $\mathcal S$ avec $\{1,2,3,\dots,2^n\}\times [-2^n,2^n]$. Calculons le nombre $\tilde a'(n,k)$ de points dans $A(n)$ qui sont de la forme $(2^kb,c)$
avec $b$ un entier impair : Si $k$ est plus petit que $n$, il y a $2^{n-k-1}$
possibilités pour $b$. Pour $k=n$, il y a exactement une possibilité.
Le nombre de points dans la « fibre » $\{x\ \vert\ (2^kb,x)\in A_n\}$
au-dessus d’un entier fixé $2^kb$ avec $b$ impair vaut $2^{1+n+k}+1$.
Nous avons donc $\tilde a'(n,n)=2^{2n+1}+1$ et $\tilde a'(n,k)=2^{2n}+2^{n-k-1}$
pour $k $\tilde a(n,n)=2^{2n+1}$ et par $\tilde a(n,k)=2^{2n}$ pour $k ce qui est sans effets sur l’asymptotique car les termes omis deviennent
négligeables pour $n$ grand. L’ensemble $A(n)$
de cardinalité $a(n)$ contient donc environ $\tilde a(n,0)+\tilde a(n,1)+\tilde a(n,n-1)+\tilde a(n,n)= n2^{2n}+2^{2n+1}=(n+2)2^{2n}$ points. L’ensemble
$\mathcal S$ intersecte donc le carré $[-2^n,2^n]^2$ selon un ensemble
de cardinalité majorée approximativement par $1+4(n+2)2^{2n}$.
Ce nombre est bien de la forme souhaitée $O((2^n)^2\mathop{log}(2^n))$
et l’erreur commises provient d’une part de l’approximation $\tilde a(n,k)\sim \tilde a'(n,k)$ et d’autre part du comptage multiple de certains points
entiers (au nombre total de $(2^{n+1}+1)^2$) de $\mathcal S(n)$.
Les deux types d’erreurs ne changent pas l’asymptotique du cardinal de
$\mathcal S(n)$ et cette asymptotique est essentiellement équivalente
à l’assertion (ii) du théorème.

Deux questions ouvertes pour finir

Je voudrais terminer ce texte par deux questions, motivées
par la présence du facteur logarithmique dans l’énoncé
du théorème.

Question 1 Soit $\mathcal S$ un ensemble du plan euclidien
tel que $\mathcal S$ contienne au plus $R^2+1$ points de norme
$\leq R$ pour tout nombre réel $R\geq 0$. Est-ce que
le complémentaire de $\mathcal S$ contient nécessairement des
triangles d’aire arbitrairement grande ?

Si la réponse à cette question est OUI, il n’y a pas d’espoir de
se débarrasser d’un facteur additionnel sous la forme d’une fonction non-bornée
à croissance très lente [9] multipliant le facteur $R^2$
dans l’énoncé du théorème.

Si la réponse est NON, il existe des ensembles bien plus petits
que l’ensemble $\mathcal S$ proposé. Il serait alors intéressant
d’en exhiber un.

La deuxième question nécessite une définition : Appelons
un sous-ensemble $\mathcal S$ du plan euclidien uniformément
discret
s’il existe un $\epsilon>0$ tel que deux points distincts
de $\mathcal S$ soient toujours à distance au moins $\epsilon$
l’un de l’autre.
Comme des disques de rayon $\epsilon/2$ centrés en les
points d’un tel ensemble ne se chevauchent pas,
le nombre de points d’un ensemble uniformément discret contenus
dans un disque assez grand est au plus proportionnel à l’aire
de ce disque.

Question 2 Est-ce que le complémentaire d’un ensemble uniformément
discret contient nécessairement des triangles d’aire arbitrairement
grande ?

La question 2 fait intervenir une restriction supplémentaire
concernant l’ensemble $\mathcal S$.
Si la réponse à
la première question est OUI, elle est donc également OUI à la deuxième
question.
Par contre, la deuxième question garde son intérêt si la réponse
à la première question est NON (ou si cette réponse n’est pas connue).

Signalons à l’intention du lecteur érudit que les choses se passent différemment en courbure constante non-nulle.

En effet, en courbure constante non-nulle (géométrie sphérique ou hyperbolique), l’aire des triangles est bornée et on aimerait connaître
la « densité minimale » d’un nuage de points qui intersecte tout
triangle d’aire au moins $C$ en fonction de $C$, surtout quand on fait
tendre $C$ vers $0$. Il s’avère qu’on peut dans les deux cas (courbure $1$ ou
courbure $-1$) minorer le rayon d’un cercle inscrit dans
un triangle (sphérique ou hyperbolique) par un réel $r(C)$ strictement positif
dépendant seulement de l’aire $C$ du triangle. (Les difficultés en courbure
zéro viennent essentiellement de l’absence d’un telle minoration, rendue
impossible à cause de l’existence de triangles de grande aire
arbitrairement fins.) Ceci implique qu’on peut trouver pour tout $C$ un nuage de point uniformément discret de la sphère ou du plan hyperbolique
qui intersecte tout triangle (sphérique ou hyperbolique) d’aire au moins $C$.
La question intéressante dans ce cas est donc la détermination de la densité
uniforme minimale d’un tel nuage de points en fonction de $C$. Dans le cas hyperbolique se pose en outre le problème de la définition de la « densité » : la formule utilisée dans le cas euclidien ne marche pas bien car une part importante de l’aire d’un grand disque hyperbolique est concentrée très près du bord.

Référence

[B] R. Bacher, Universal convex coverings, prépublication 0810.2371
sur arXiv
, à paraître dans
Bull. London Math. Soc.

Article édité par Étienne Ghys

Notes

[1En effet, le triangle isocèle dont les sommets sont la pointe du museau et les extrémités des deux pattes
arrières du rat approche assez bien la surface occupée par le rat.

[2Il ne s’agit pas d’un mois de travail à temps complet, il s’agit d’heures éparpillées durant un mois de l’année universitaire qui ne sont pas occupées par l’enseignement, les réunions pédagogiques, les différentes tâches administratives et d’autres occupations comme par exemple la lecture d’un article à référer suivie de la rédaction du rapport. Beaucoup de ces occupations ne sont pas comptabilisées dans nos charges, même s’il s’agit clairement d’activités ne relevant pas de la recherche comme par exemple de réunions au rectorat pour l’élaboration d’un sujet d’examen (bac ou autre). C’est entre autres pour ces raisons que la majorité des universitaires que je connais travaillent un peu plus qu’à temps complet si on compte les heures.

[3Je me trouve en excellente compagnie pour cet aspect, voir les conseils d’Alain Connes dans le chapitre « Advice to a Young Mathematician » qui se trouve dans le merveilleux livre
The Princeton Companion to Mathematics édité par Gowers.

[4En effet, je n’avais rien trouvé sur MathScinet (une base de données indexant toutes les parutions en mathématique) et comme l’article est somme toute élémentaire, je n’ai pas jugé utile de mettre des références un peu « bidons ».

[5On peut consulter ici le prix facturé par page pour les diverses revues, qui s’étale entre 10 centimes de dollars et plus de 7 dollars...

[6Etienne Ghys m’a fait remarquer qu’un théorème fameux de Minkowski :
« Tout convexe symétrique de volume supérieur à $2^n$ de
$\mathbb R^n$ contient un point entier non-nul
 »
est une telle généralisation.
Heureusement pour moi, ce n’est pas par là que j’ai commencé, sinon mon travail n’aurait jamais vu le jour

[7ouvert ou fermé, cela n’a pas beaucoup d’importance
pour nous

[8Pour le lecteur pinailleur, il s’agit du plan vectoriel euclidien
identifié à $\mathbb R^2$ après choix d’un système orthogonal de coordonnées.

[9du style $\mathop{log}(R)$
(ou peut-être $\mathop{loglog}(R)$ ou $(\mathop{log}(R))^{\epsilon}$
pour un $\epsilon>0$ arbitrairement petit)

Partager cet article

Pour citer cet article :

Roland Bacher — «Comment empoisonner efficacement tous les grands rats» — Images des Mathématiques, CNRS, 2009

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?

Suivre IDM

htmlavPlleutrea dethematiciens-.html">Tribune M;'>Sig oum;'>Sig l;"> Tribune Siesharenmenta a des-amist-il-avSi webre, jesthematiciens-.html">Tribune ontact"@com/share?url=http%liass= cLexique >

rs blocs_invisible blocs_slide">
> >> <> blocs_ /tre blocs_"> "17;al <> blocs_ /tre blocs_"> "17;al <> blocs_ /tre blocs_"> "17;al < <> blocs_ /tre blocs_"v> var _paq = _paq || [];> _paq.push(['trackPm/sView']);> _paq.push(['enmbleLinkTracking']);> _paq.push(['setTrackerUrl', '/piwik/piwik ']);> _paq.push(['setSi&#Id', 1]);><> (fun tel () {s_slide"> var d=spip.php, r=d.createE ('blocs_'), s=d.getE sByTagName('blocs_')[0];> g. ' /tre blocs_'; g.defer=true; g.async=true; g. /piwik/piwik js';> s.proctNode.insertBefore(g,s);> })();> < < < < <