Suite de Sidon

En théorie des nombres, une suite de Sidon est une suite (finie ou infinie) d'entiers 0 < a₁ < a₂ < … dont les sommes de deux termes, a_i + a_j 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 B_h[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 R_h(g, n) d'un B_h[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 R₂(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^{-\varepsilon })\leq R_{2}(2,n)\leq 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 – n^{1 – 2ε} et n (le record mentionné dans O'Bryant 2004 correspond à ε = 0,2375).

La suite R₂(2, n) est donc équivalente à √n, mais aucun progrès n'a été fait sur la conjecture d'Erdős qui prévoit que la différence R₂(2, n) – √n 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,

$\liminf _{n\to \infty }{\frac {A(n)}{\sqrt {n/\log n}}}<\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

$\limsup _{x\to \infty }{\frac {A(n)}{\sqrt {n}}}\geq {\frac {1}{\sqrt {2}}}.$

Erdős a demandé s'il existe une suite de Sidon (a_k) telle que a_k = o(k^{3 – ε}) 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}.$

Imre Z. Ruzsa (en) 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 B_h[g]-suites de Sidon telles que a_k = O(k^{h + ε}).

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) = x⁵ + [cx⁴] 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.

Notes et références

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sidon sequence » (voir la liste des auteurs).

Articles connexes

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