Théorème de Fürstenberg-Sárközy

En mathématiques, plus précisément en théorie additive des nombres, le théorème de Fürstenberg-Sárközy porte sur les ensemble d'entiers dont aucunes différences n'est un nombre carré. Hillel Furstenberg et András Sárközy ont trouvé à la fin des années 1970 une borne supérieure pour de tel ensemble. Un autre ensemble sans différence de carré est obtenu en doublant la suite de Moser–de Bruijn (suite A000695 de l'OEIS).

La meilleure borne supérieure sur la taille d'un ensemble sans différence carrée inclus dans $[\![1,n]\!]$ n'est que légèrement sous-linéaire, mais les plus grands ensembles connus de cette forme sont nettement plus petits, de taille $\approx n^{0{,}733412}$. Combler l'écart entre ces bornes supérieure et inférieure reste un problème ouvert.

Le théorème de Fürstenberg-Sárközy admet des généralisations à des ensembles de polynômes.

Exemple

Un exemple d'ensemble sans différences carrées apparaît dans le jeu de soustraction d'un carré, inventé par Richard A. Epstein et décrit pour la première fois en 1966 par Solomon W. Golomb. Dans ce jeu, deux joueurs retirent à tour de rôle des pièces d'une pile de pièces ; le joueur qui enlève la dernière pièce gagne. À chaque tour, le joueur ne peut retirer qu'un nombre carré non nul de pièces de la pile. Toute position dans ce jeu peut être décrite par un entier, son nombre de pièces. Les entiers positifs peuvent être divisés en positions dites « froides », dans lesquelles le joueur qui est sur le point de se déplacer perd, et « chaudes », dans lesquelles le joueur qui est sur le point de se déplacer peut gagner en se déplaçant vers une position froide. Deux positions froides ne peuvent pas différer d'un carré, car si c'était le cas, un joueur confronté à la plus grande des deux positions pourrait passer à la position la plus petite et gagner. Ainsi, les positions froides forment un ensemble sans carré de différence : 0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … suite A030193 de l'OEIS Ces positions peuvent être générées par un algorithme glouton dans lequel les positions froides sont générées dans l'ordre numérique, en sélectionnant à chaque étape le plus petit nombre qui n'a pas de différence carrée avec un nombre. Comme l'a observé Golomb, le nombre de positions froides jusqu'à $n$ est au moins égal à ${\sqrt {n}}$. Le théorème de Furstenberg-Sárközy montre cependant que les positions froides sont moins fréquentes que les positions chaudes : pour tout $\varepsilon >0$, et pour tout$n$ assez grand, la proportion de positions froides jusqu'à $n$ est au plus de $\varepsilon$. Autrement dit, face à une position de départ comprise entre 1 et $n$, le premier joueur peut gagner depuis la plupart de ces positions. Des études numériques suggèrent que le nombre de positions froides inférieure à $n$ est proche de $n^{0.7}$.

Bornes supérieures

D'après le théorème de Furstenberg-Sárközy, si $S$ est un ensemble sans différence carré, alors la densité naturelle de $S$ est nulle. De manière équivalente, tout ensemble d'entiers naturels avec une densité supérieure positive contient deux nombres dont la différence est un carré, et même une infinité. Le théorème de Furstenberg-Sárközy a été conjecturé par László Lovász, et prouvé indépendamment à la fin des années 1970 par Hillel Furstenberg et András Sárközy. Depuis, plusieurs autres preuves du même résultat ont été publiées, généralement soit en simplifiant les preuves précédentes, soit améliorant les bornes. La meilleure borne supérieure actuellement connue est due à Thomas Bloom et James Maynard, qui montrent que la taille d'un ensemble sans différence carrée inclut dans $[\![1,n]\!]$ vérifie

$$O\left({\frac {n}{(\log n)^{c\log \log \log n}}}\right)$$

où $c>0$ est une constante absolue.

La plupart de ces preuves qui établissent des limites supérieures quantitatives utilisent l'analyse de Fourier ou la théorie ergodique, bien qu'aucune ne soit nécessaire pour prouver le résultat plus faible selon lequel chaque ensemble sans différence carrée a une densité nulle.

Bornes inférieures

Paul Erdős a conjecturé que tout ensemble sans différence carrée est de taille

$$O(n^{1/2}\log ^{k}n)$$

pour une constante $k$, mais cela a été réfuté par Sárközy, par des contre-exemples. Sárközy a affaibli la conjecture d'Erdős pour suggérer que, pour chaque $\varepsilon >0$, chaque ensemble sans différence carrée dans $[\![1,n]\!]$ vérifie

$$O(n^{1/2+\varepsilon })$$

Cette conjecture a elle aussi été réfutée par Imre Z. Ruzsa, qui a trouvé des ensembles sans différence carrée de cardinal

$$\Omega {\big (}n^{(1\,+\,\log _{65}7)/2}{\big )}\approx n^{0.733077}$$

Avec ces résultats, il est conjecturé que pour chaque $\varepsilon >0$ et pour $n$ suffisamment grand il existe des sous-ensembles sans différence carrée de $[\![1,n]\!]$ de cardinal $\Omega (n^{1-\varepsilon })$. Autrement dit, si cette conjecture est vraie, l'exposant 1 dans les limites supérieures du théorème de Furstenberg-Sárközy ne peut pas être abaissé.

Généralisation à d'autres polynômes

La borne supérieure du théorème de Furstenberg – Sárközy peut être généralisée pour une différence qui n'évite plus les carrés mais l'ensembl $p(\mathbb {N} )$,où $p$ est un polynôme à coefficients entiers, tel que les tout entier soit un multiple d'une valeur de $p$ Cette dernière condition est nécessaire, car sinon les multiples d'un tel $k$ formerait un ensemble de densité non nulle sans différences de $p(\mathbb {N} )$.

Références

• (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Square-difference-free set » (voir la liste des auteurs).