Suite de Sidon

En théorie des nombres, une suite de Sidon est une suite (finie ou infinie) d'entiers 0 < aModèle:Ind < aModèle:Ind < … dont les sommes de deux termes, aModèle:Ind + aModèle:Ind pour i ≤ j, sont toutes différentes. Le mathématicien hongrois Simon Sidon a introduit ce concept dans le cadre de ses recherches sur les séries de Fourier.

Cette notion a été généralisée : dans un groupe abélien G , une partie A est un BModèle:Ind[g]-ensemble de Sidon si, pour tout élément x de G, le nombre de h-uplets d'éléments de A de somme x est inférieur ou égal à g.

Le principal problème dans l'étude de ces suites, posé par Sidon dans le cas originel h = g = 2, est d'estimer le cardinal maximal RModèle:Ind(g, n) d'un BModèle:Ind[g]-ensemble de Sidon inclus dans {1, 2, … , n}, où n est un entier > 0. Malgré d'abondantes recherches qui progressent encore, cette vaste question n'est toujours pas complètement résolue.

Premiers résultats

Paul Erdős et Pál Turán ont trouvé pour RModèle:Ind(2, n) un encadrement, dont le minorant a été affiné simultanément par Erdős et Sarvadaman Chowla en utilisant une construction de James Singer :

$n^{1/2}(1-n^{-\epsilon })\le R_2(2,n)\le n^{1/2}+n^{1/4}+1,$

le minorant étant valable pour n assez grand, avec ε tel que pour un tel n, il y ait toujours un nombre premier entre n – nModèle:Exp et n (le record mentionné dans Modèle:Harvsp correspond à ε = 0,2375).

La suite RModèle:Ind(2, Modèle:Math) est donc équivalente à Modèle:Sqrt, mais aucun progrès n'a été fait sur la conjecture d'Erdős qui prévoit que la différence RModèle:Ind(2, Modèle:Math) – Modèle:Sqrt est non bornée, ni sur la positivité de cette différence.

Suites de Sidon infinies

Alfred Stöhr a amélioré un résultat que lui avait communiqué Erdős, en démontrant que pour toute suite de Sidon infinie, si A(n) désigne le nombre de termes inférieurs ou égaux à n,

$\underset{n\to \mathrm{\infty }}{\mathrm{lim\; inf}}\frac{A(n)}{\sqrt{n/\log n}}<\mathrm{\infty }.$

Dans la direction opposée, Fritz Krückeberg a amélioré un autre résultat de Stöhr, en montrant qu'il existe une suite de Sidon vérifiant

$\underset{x\to \mathrm{\infty }}{\mathrm{lim\; sup}}\frac{A(n)}{\sqrt{n}}\ge \frac{1}{\sqrt{2}}.$

Erdős a demandé s'il existe une suite de Sidon (aModèle:Ind) telle que aModèle:Ind = o(kModèle:Exp) pour un certain ε > 0. Ajtai, Komlós et Szemerédi en avaient en effet construit une telle que

$A(n)>(n\log n{)}^{1/3}.$

Modèle:Lien en a construit une telle que

$A(n)\sim n^{\sqrt{2}-1-o(1)}.$

Erdős et Rényi ont démontré que pour tout ε > 0 et pour tout h ≥ 2, il existe des g et des BModèle:Ind[g]-suites de Sidon telles que aModèle:Ind = O(kModèle:Exp).

Une autre conjecture d'Erdős est que la suite des puissances cinquièmes d'entiers > 0 est de Sidon. Ruzsa a démontré qu'il existe un nombre irrationnel c (strictement compris entre 0 et 1) tel que l'image de l'application f(x) = xModèle:5 + [[Partie entière|[cxModèle:4]]] soit de Sidon, mais cette application f n'est même pas polynomiale. Cette conjecture d'Erdős, bien que non démontrée, a été généralisée par Lander, Parkin et Selfridge.

Lien avec les règles de Golomb

Les suites de Sidon finies sont exactement les règles de Golomb, puisque x + y = u + v équivaut à x – u = v – y.

Articles connexes

• Somme d'ensembles
• Conjecture d'Erdős-Turán sur les bases additives
• Suite de Mian-Chowla