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 + a 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[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(g, n) d'un B[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 :
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 et n (le record mentionné dans correspond à ε = 0,2375).
La suite R(2, ) est donc équivalente à , mais aucun progrès n'a été fait sur la conjecture d'Erdős qui prévoit que la différence R(2, ) – est non bornée, ni sur la positivité de cette différence.
Suites de Sidon infinies
Alfred Stöhr, § 12aβ, 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,
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
Erdős a demandé s'il existe une suite de Sidon (a) telle que a = o(k) pour un certain ε > 0. Ajtai, Komlós et Szemerédi en avaient en effet construit une telle que
en a construit une telle que
Erdős et Rényi ont démontré que pour tout ε > 0 et pour tout h ≥ 2, il existe des g et des B[g]-suites de Sidon telles que a = O(k).
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
Articles connexes Somme d'ensembles Conjecture d'Erdős-Turán sur les bases additives Suite de Mian-Chowla
Catégorie:Théorie des nombres Catégorie:Combinatoire