Introduction

Un nombre premier est un entier naturel qui n’est divisible que par 1 et par lui-même [1]. La suite des nombres premiers commence donc par $2,3,5,7,11, 13, \dots$, et on sait depuis l’Antiquité qu’elle est infinie [2]. En outre, il se trouve que chaque entier est un produit de nombres premiers et que cette décomposition est unique, à l’ordre près. Les nombres premiers constituent alors la « base » de l’ensemble des nombres entiers, et du domaine mathématique qui s’appelle théorie des nombres.

Pourtant, ces nombres restent insaisissables dans le sens où il est très difficile de prédire le prochain nombre premier, ou même de déterminer, dans la pratique, les facteurs premiers d’un très grand entier [3].

D’un point de vue moins pratique et plus abstrait, il reste beaucoup de problèmes ouverts concernant la distribution et le comportement des nombres premiers. Par exemple, est-il vrai que tout entier pair (au moins égal à 4) peut s’écrire comme une somme de deux nombres premiers ? Ce problème porte le nom conjecture de Goldbach, et il reste un des problèmes ouverts les plus célèbres depuis sa mention dans une lettre à Euler en 1742 [4].

Progressions arithmétiques dans l’ensemble des nombres premiers

En 2004 Ben Green et Terence Tao ont résolu un autre problème concernant l’existence de certaines structures arithmétiques dans l’ensemble des nombres premiers, dont nous allons donner un aperçu dans la suite.

Ben Green, University of Cambridge, Royaume-Uni

Une progression arithmétique est une suite d’entiers $x_1, x_2, x_3, \dots$ telle que la différence entre deux termes successifs est constante. On appelle cette différence la raison de la progression. La longueur d’une progression arithmétique est le nombre de termes qu’elle contient.

Les nombres premiers sont marqués en noir.

Par exemple, les nombres $3,5,7$ forment une progression arithmétique de longueur 3, ainsi que les nombres 3,7,11. Par ailleurs, tous les éléments de ces progressions sont premiers, et il s’agit donc dans les deux cas de progressions arithmétiques de longueur 3 formées de nombres premiers.

Déjà pour la longueur 6 cette tâche devient beaucoup plus difficile, et pour une longueur arbitraire donnée ce n’est plus possible d’en vérifier l’existence à la main (ou même par ordinateur). En 2004 Green et Tao ont démontré que l’ensemble des nombres premiers contient des progressions arithmétiques de toute longueur, confirmant ainsi plusieurs vieilles conjectures à cet égard.

Terence Tao, University of California Los Angeles, États-Unis

Il s’agit d’un théorème abstrait qui ne donne pas de formule pour trouver une telle progression [6]. Pourtant, une extension de leur travail dans un article ultérieur [7] donne une formule asymptotique pour le nombre de telles progressions dans un intervalle donné, c’est-à-dire, une formule pour le nombre de progressions dont les termes n’excèdent pas $N$, lorsque $N$ tend vers l’infini.

Le résultat de Green et Tao a attiré beaucoup d’attention, et pas uniquement parce qu’ils ont résolu un problème ouvert depuis très longtemps. Les méthodes utilisées constituent un mélange impressionnant et surprenant d’outils très variés. Dans la suite nous allons essayer d’éclaircir quelques aspects de ce travail et des généralisations récentes.

Le comportement des nombres premiers

Le résultat de Green et Tao peut paraître assez surprenant : les nombres premiers ont un comportement assez imprévisible, presque aléatoire, et en même temps ils semblent contenir des structures arithmétiques très bien ordonnées (comme le sont les progressions arithmétiques).

En fait, c’est précisément l’aspect « pseudo-aléatoire » des nombres premiers qu’on cherche à exploiter. Pourtant, on voit très vite que cela n’est pas très facile, car les nombres premiers ne sont pas vraiment uniformément distribués parmi les entiers. Par exemple, il n’y a pas de nombre premier pair (à part 2). A fortiori, il n’y a pas de nombre premier qui soit un multiple de 3, ou de 5 etc. (à part 3, 5, bien sûr !).

Heureusement, un théorème classique en théorie des nombres nous permet d’estimer les nombres premiers qui n’excèdent pas un entier donné $N$ (qui est grand).

Le théorème des nombres premiers.

La ligne rouge représente le nombre de nombres premiers inférieurs à $x$.
La ligne bleue est la courbe d’équation $y=x/\log x$.

Il se trouve qu’on n’a pas besoin de techniques de théorie des nombres plus avancées que celles qui interviennent dans la démonstration du théorème des nombres premiers, qui en elle-même n’est pas triviale, pour s’attaquer à la démonstration du théorème de Green et Tao. Le reste de la démonstration découle des techniques de l’analyse de Fourier [9] et de la combinatoire qui s’appliquent dans l’étude des structures dans des sous-ensembles d’entiers.

Progressions arithmétiques dans des sous-ensembles d’entiers

Dans la démonstration du théorème de Green et Tao, on se ramène à un résultat plus classique sur les progressions arithmétiques dans les sous-ensembles d’entiers. Ce résultat, connu comme le théorème de Szemerédi d’après le mathématicien hongrois Endre Szemerédi qui l’a démontré en 1975, a plusieurs preuves très intéressantes, utilisant des méthodes de divers domaines mathématiques.

Endre Szemerédi, Rutgers University, États-Unis et Institut de Renyi, Budapest

Comme nous l’avons vu ci-dessus, l’ensemble des nombres premiers a une densité bien inférieure à $1/\log\log N$ [10], et donc le théorème de Szemerédi ne s’applique pas immédiatement aux nombres premiers. On a besoin d’un « principe de transfert » [G2], qui nous permet d’appliquer un résultat concernant les sous-ensembles plus denses d’entiers, comme le théorème de Szemerédi, à des sous-ensembles denses d’un ensemble « pseudo-aléatoire » (comme l’est par exemple l’ensemble des nombres premiers, qui est à densité positive dans l’ensemble des entiers qui possèdent peu de facteurs premiers).

Progressions polynomiales

Quelques années après la preuve du théorème de Green et Tao, en 2008, Tao et Ziegler ont généralisé ce résultat aux « progressions polynomiales », sujet de l’exposé Bourbaki du 24 mars 2012. Un cas spécial de cette généralisation est le suivant.

Tamar Ziegler, Technion, Israël

La démonstration de ce théorème ressemble beaucoup à celle du théorème de Green et Tao, sauf qu’on n’a pas d’analogue quantitatif du théorème de Szemerédi ci-dessus pour les progressions polynomiales. Il y a cependant une exception remarquable : le cas (beaucoup plus facile) d’une progression de longueur 2, démontré par un autre mathématicien hongrois, András Sárközy, en 1978.

Par la contraposée, tout sous-ensemble $A$ de cardinal plus grand que cette borne contient deux éléments distincts dont la différence est un carré (dans ce cas on dira dans la suite que $A$ contient une différence carrée). Le théorème des nombres premiers nous dit que ceci est le cas pour tout sous-ensemble à densité positive [12] dans les nombres premiers, et donc le cas $k=2$ du théorème de Tao et Ziegler découle directement du théorème de Sárközy.

Dans la suite nous allons donner quelques idées plus précises autour du théorème de Sárközy. Cela nous force à quitter la piste noire pour passer en « hors piste », mais j’espère que quelques-uns des lecteurs intrépides suivront cette histoire jusqu’au bout !

Quelques idées de preuves

La démonstration du théorème de Sárközy fait surtout intervenir de l’analyse de Fourier, qui vise à décomposer une fonction en une somme de fonctions trigonométriques. En particulier, on exploite la différence de magnitude de la transformée de Fourier de la fonction caractéristique des carrés, entre les points qui sont « proches » d’un nombre rationnel à petit dénominateur, et les points qui ne le sont pas.

Somme partielle du coefficient de Fourier en $\theta=2/37$.

Somme partielle du coefficient de Fourier en $\theta=\pi$.

Comme nous l’avons vu ci-dessus, la borne dans le théorème de Sárközy est suffisamment forte pour entraîner un résultat dans les nombres premiers. En fait, on s’attend à pouvoir un jour démontrer l’existence de tout genre de structure arithmétique (linéaire ou polynomiale, de toute longueur) dans des sous-ensembles d’entiers suffisamment denses dans le sens où cela s’appliquerait directement à l’ensemble des nombres premiers. Par exemple, si on pouvait améliorer la borne dans le théorème de Szemerédi à $N/\log N$, on arriverait au théorème de Green-Tao sans aucun effort supplémentaire [13]

Construction d’un ensemble dense sans différence carrée

Cependant, il est très peu probable que la borne énoncée dans le théorème de Sárközy soit la meilleure possible. Peut-on construire un ensemble d’entiers qui ne contient pas de différence carrée ? Si on applique le « principe glouton » (c’est-à-dire, si on commence avec le nombre 1 et on rajoute les entiers un par un s’ils ne créent pas de différence carrée avec un nombre précédemment choisi) on obtient la suite $1,3,6,8, \dots$ qui est bien infinie et dont l’intersection avec l’intervalle $\{1, \dots, N\}$ contient environ $N^{1/2}$ éléments.

Imre Z. Ruzsa, Institut de Renyi, Budapest

Une meilleure construction est due à un troisième membre de l’école mathématique hongroise, Imre Ruzsa. Elle est simple, mais ingénieuse, et nous en donnerons ici la démonstration complète.

L’idée principale de la construction est de passer d’un sous-ensemble dans le groupe cyclique $\mathbb{Z}/m\mathbb{Z}$ sans différence carrée, pour $m$ petit, à un sous-ensemble de l’intervalle $\{1,2,\ldots,N\}$ avec cette même propriété, pour un $N$ qui tend vers l’infini. Nous allons décrire dans la suite comment effectuer ce passage ; il restera ensuite à établir l’existence d’un sous-ensemble de $\mathbb{Z}/m\mathbb{Z}$ pour un $m$ qui convient.

En effet, supposons d’abord que nous avons trouvé un grand sous-ensemble $U$ de $\mathbb{Z}/m\mathbb{Z}$ sans différence carrée. Pour un entier $n$, définissons le sous-ensemble $A$ de $\{1, 2, \dots, m^n\}$ par

\[A=\left\{\sum_{i=0} ^{n-1} r_im^i : r_i \in \{0,\ldots,m-1\} \textrm{ si } i \textrm{ est impair et } r_i \in U \textrm{ si } i \text{ est pair}\right\}.\]

Si $m$ est un entier sans facteur carré (c’est-à-dire, si $m$ est un produit de nombres premiers distincts), on peut vérifier les deux propriétés suivantes :

1. le cardinal de $A$ vérifie
   \[|A| = m^{\frac{n}{2}}m^{\frac{n}{2}(\log _m |U|)}\]
2. $A$ ne contient pas de différence carrée.

Si nous posons $N=m^n$, alors le cardinal de $A$ est
$ |A|=N^{\frac{1}{2}(1+\log _m |U|)},$
et on cherche à maximiser l’expression $\log_m |U|$. Ceci est une tâche beaucoup plus facile que la tâche initiale, car le $m$ peut être choisi petit, et on arrive donc à faire les calculs même à la main, comme on le verra dans la suite.

Ruzsa trouve un sous-ensemble $U \subseteq \mathbb{Z}/ 65 \mathbb{Z}$ de cardinal 7, qui donne un ensemble $A$ de cardinal $N^{0.733077}$ dans l’énoncé du théorème ci-dessus. Pour faciliter la démonstration, il se sert du théorème des restes chinois, résultat élémentaire de l’arithmétique modulaire.

En particulier, ce théorème entraîne qu’on peut identifier les éléments de $\mathbb{Z}/(m_1\cdot m_2) \mathbb{Z}$ avec les couples $(u,v) \in \mathbb{Z}/m_1\mathbb{Z} \times \mathbb{Z}/m_2 \mathbb{Z}$. Il est alors facile de vérifier que la différence entre $(u,v) \in \mathbb{Z}/(m_1\cdot m_2) \mathbb{Z}$ et $(u',v') \in \mathbb{Z}/(m_1\cdot m_2) \mathbb{Z}$ n’est pas un carré si au moins un de $u-u' \in\mathbb{Z}/m_1 \mathbb{Z}$ et $v-v' \in\mathbb{Z}/m_2 \mathbb{Z}$ n’est pas un carré.

Voici alors un sous-ensemble de $\mathbb{Z}/5\mathbb{Z} \times \mathbb{Z}/13\mathbb{Z}$ dont aucune différence n’est un carré, dans au moins une coordonnée, ce qu’on peut vérifier à la main :

\[U=\{ (0,0),(0,2),(1,8),(2,1),(2,3),(3,9),(4,7)\}\]

Cela correspond aux éléments $0,15,21,27,42,48,59 \in \mathbb{Z}/65 \mathbb{Z}$.

On peut démontrer (en utilisant la transformée de Fourier discrète, par exemple) que pour $m$ un produit de facteurs premiers congrus à 1 modulo 4, le cardinal maximal de $U\subseteq \mathbb{Z}/m\mathbb{Z}$ sans différence carrée est $\sqrt{m}$, donc la meilleure borne à laquelle on peut s’attendre avec cette construction est $N^{0.75}$. Pourtant, on ne connaît aucun exemple qui atteint cette borne. [14]

D’ailleurs, cet ensemble est très loin de la borne supérieure du théorème de Sárközy. Toute amélioration, d’un côté ou de l’autre, serait d’un grand intérêt.

[BG] R. Beigel and W. Gasarch, Square-difference free sets of size ${\Omega}(n^{.7334})$, Non publié, 2011.

[G1] W.T. Gowers, A new proof of Szemerédi’s theorem, Geom. Funct. Anal., 11 (3) : 465—588, 2001.

[G2] W.T. Gowers, Decompositions, approximate structure, transference, and the Hahn-Banach theorem, Bull. Lond. Math. Soc., 42 (4) : 573—606, 2010.

[GrT1] B.J. Green and T. Tao, The primes contain arbitrarily long arithmetic progressions, Ann. of Math. (2), 167 (2) : 481—547, 2008.

[GrT2] B.J. Green and T. Tao, Linear equations in primes, Ann. of Math. (2), 171 (3) : 1753—1850, 2010.

[PSS] J. Pintz, W.L. Steiger, and E. Szemerédi, On sets of natural numbers whose difference set contains no squares, J. London Math. Soc. (2), 37 (2) : 219—231, 1988.

[R] I.Z. Ruzsa, Difference sets without squares, Period. Math. Hungar., 15 (3) : 205—209, 1984.

[S] A. Sárközy, On difference sets of sequences of integers, I, Acta Math. Acad. Sci. Hungar., 31 (1-2) : 125—149, 1978.

[T] T. Tao,The dichotomy between structure and randomness, arithmetic
progressions, and the primes, In International Congress of Mathematicians. Vol. I,
p. 581—608. Eur. Math. Soc., Zürich, 2007.

[TZ] T. Tao and T. Ziegler, The primes contain arbitrarily long polynomial progressions, Acta Math., 201 (2):213—305, 2008.

[Te] G. Tenenbaum, Introduction à la théorie analytique et probabiliste des nombres, volume 1 de Cours Spécialisés, Société Mathématique de France, Paris, deuxiéme edition, 1995.