Suite de Sidon

En théorie des nombres, une suite de Sidon est[1] 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[2].

Cette notion a été généralisée[3] : 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[3] qui progressent encore[4], 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[1], dont le minorant a été affiné simultanément par Erdős[5] et Sarvadaman Chowla[3] en utilisant une construction de James Singer[6] :

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 à $\sqrt 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$ ) – $\sqrt n$ est non bornée, ni sur la positivité de cette différence[3].

Suites de Sidon infinies

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}}}\geq {\frac {1}{\sqrt {2}}}.

Erdős a demandé[9] 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[10]

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

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

A(n)\sim n^{{\sqrt {2}}-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 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é[13] 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).

(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)
(de) S. Sidon, « Ein Satz über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen », Math. Ann., vol. 106,‎ 1932, p. 536-539 (lire en ligne)
(en) K. O'Bryant, « A complete annotated bibliography of work related to Sidon sequences », Electron. J. Combin., vol. DS, n^o 11,‎ 2004, p. 1-39 (lire en ligne)
(en) J. Cilleruelo, I. Ruzsa et C. Vinuesa, « Generalized Sidon sets », Adv. Math., vol. 225,‎ 2010, p. 2786-2807 (lire en ligne)
(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)
(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)
(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
(de) Fritz Krückeberg, « B₂-Folgen und verwandte Zahlenfolgen », J. reine angew. Math., vol. 206,‎ 1961, p. 53-60 (lire en ligne)
(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
(en) M. Ajtai, J. Komlós et E. Szemerédi, « A dense infinite Sidon sequence », European J. Combin., vol. 2, n^o 1,‎ 1981, p. 1-11
(en) I. Z. Ruzsa, « An infinite Sidon sequence », J. Number Theory, vol. 68,‎ 1998, p. 63-71 (DOI 10.1006/jnth.1997.2192)
(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)
(en) I. Z. Ruzsa, « An almost polynomial Sidon sequence », Studia Sci. Math. Hungar., vol. 38,‎ 2001, p. 367-375 (DOI 10.1556/SScMath.38.2001.1-4.27)

Articles connexes

Arithmétique et théorie des nombres

Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.

[ErdosTuran-1] (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 über trigonometrische Polynome und seine Anwendungen in der Theorie der Fourier-Reihen », Math. Ann., vol. 106,‎ 1932, p. 536-539 (lire en ligne)

[OBryant-3] (en) K. O'Bryant, « A complete annotated bibliography of work related to Sidon sequences », Electron. J. Combin., vol. DS, n^o 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, « B₂-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, n^o 1,‎ 1981, p. 1-11

[11] (en) I. Z. Ruzsa, « An infinite Sidon sequence », J. Number Theory, vol. 68,‎ 1998, p. 63-71 (DOI 10.1006/jnth.1997.2192)

[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 (DOI 10.1556/SScMath.38.2001.1-4.27)