Suite de Sidon

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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

Cette notion a été généralisée[3] : dans un groupe abélien G , une partie A est un Bh[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 Rh(g, n) d'un Bh[g]-ensemble de Sidon inclus dans {1, 2, … , n}, où n est un entier > 0. Malgré d'abondantes recherches[3] qui progressent encore[4], cette vaste question n'est toujours pas complètement résolue.

Premiers résultats[modifier | modifier le code]

Paul Erdős et Pál Turán ont trouvé pour R2(2, n) un encadrement[1], dont le minorant a été affiné simultanément par Erdős[5] et Sarvadaman Chowla (en)[3] en utilisant une construction de James Singer[6] :

n^{1/2}(1-n^{-\varepsilon})\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 – n1 – 2ε et n (le record mentionné dans O'Bryant 2004 correspond à ε = 0,2375).

La suite R2(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 R2(2, n) – n est non bornée, ni sur la positivité de cette différence[3].

Suites de Sidon infinies[modifier | modifier le code]

Alfred Stöhr[7] 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 (de)[8] 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}\ge\frac1{\sqrt2}.

Erdős a demandé[9] s'il existe une suite de Sidon (ak) telle que ak = o(k3 – ε) pour un certain ε > 0. Ajtai, Komlós (en) et Szemerédi en avaient en effet construit une telle que[10]

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

Imre Z. Ruzsa (en)[11] en a construit une telle que

A(n)\sim n^{\sqrt2-1-o(1)}.

Erdős et Rényi ont démontré[12] que pour tout ε > 0 et pour tout h ≥ 2, il existe des g et des Bh[g]-suites de Sidon telles que ak = O(kh + ε).

Une autre conjecture d'Erdős est que la suite des puissances cinquièmes d'entiers > 0 est de Sidon. Ruzsa a démontré[13] qu'il existe un nombre irrationnel c (strictement compris entre 0 et 1) tel que l'image de l'application f(x) = x5 + [cx4] 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 (en).

Lien avec les règles de Golomb[modifier | modifier le code]

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[modifier | modifier le code]

(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)

  1. a et b (en) P. Erdős et P. Turán, « On a problem of Sidon in additive number theory, and on some related problems », J. London Math. Soc., vol. 16,‎ 1941, p. 212-216 (lire en ligne)
  2. (de) S. Sidon, « Ein Satz Äuber trigonomietrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen », Math. Ann., vol. 106,‎ 1932, p. 536-539 (lire en ligne)
  3. a, b, c et d (en) K. O'Bryant, « A complete annotated bibliography of work related to Sidon sequences », Electron. J. Combin., vol. DS, no 11,‎ 2004, p. 1-39 (lire en ligne)
  4. (en) J. Cilleruelo, I. Ruzsa et C. Vinuesa, « Generalized Sidon sets », Adv. Math., vol. 225,‎ 2010, p. 2786-2807 (lire en ligne)
  5. (en) P. Erdős, « On a problem of Sidon in additive number theory and on some related problems. Addendum », J. London Math. Soc., vol. 19,‎ 1944, p. 208 (lire en ligne)
  6. (en) James Singer, « A theorem in finite projective geometry and some applications to number theory », Trans. Amer. Math. Soc., vol. 43,‎ 1938, p. 377-385 (lire en ligne)
  7. (de) Alfred Stöhr, « Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe, II », J. reine angew. Math., vol. 194,‎ 1955, p. 111-140 (lire en ligne), § 12aβ, p. 129-135
  8. (de) Fritz Krückeberg, « B2-Folgen und verwandte Zahlenfolgen », J. reine angew. Math., vol. 206,‎ 1961, p. 53-60 (lire en ligne)
  9. (en) Paul Erdős, « Some of my favourite problems which recently have been solved », dans Proc. Int. Math. Conf. Singapore 1981, North-Holland,‎ 1982 (lire en ligne), p. 59-79
  10. (en) M. Ajtai, J. Komlós et E. Szemerédi, « A dense infinite Sidon sequence », European J. Combin., vol. 2, no 1,‎ 1981, p. 1-11
  11. (en) I. Z. Ruzsa, « An infinite Sidon sequence », J. Number Theory, vol. 68,‎ 1998, p. 63-71 (lien DOI?)
  12. (en) P. Erdős et A. Rényi, « Additive properties of random sequences of positive integers », Acta Arithmetica, vol. 6,‎ 1960, p. 83-110 (lire en ligne)
  13. (en) I. Z. Ruzsa, « An almost polynomial Sidon sequence », Studia Sci. Math. Hungar., vol. 38,‎ 2001, p. 367-375 (lien DOI?)

Articles connexes[modifier | modifier le code]