A propos de la fonction $X$ d’Erdös et Graham

Plagne, Alain

Annales de l'Institut Fourier, Tome 54 (2004), p. 1717-1767 / Harvested from Numdam

Résumé

Nous améliorons les meilleures bornes supérieures et inférieures connues pour la fonction $X$ d’Erdös et Graham définie par $X (h) = \max _{h {\mathcal {A}} \sim \mathbb {N}}\ \max _{a \in {\mathcal {A}^*}}\ {\rm ord}^* ({\mathcal {A}} {\setminus a})$, où le premier maximum est pris sur toutes les bases (exactes) ${\mathcal {A}}$ d’ordre au plus $h$, où ${\mathcal {A}}^*$ désigne le sous-ensemble de ${\mathcal {A}}$ composé des éléments $a$ tels que ${\mathcal {A}} \setminus \lbrace a\rbrace $ soit encore une base et où, enfin, ${\rm ord}^* ({\mathcal {A}})$ désigne l’ordre (exact) de ${\mathcal {A}}$. Notre étude nous conduira, entre autres, à prouver un nouveau résultat additif général découlant de la méthode isopérimétrique et à étudier trois problèmes additifs (dans les groupes cycliques) de nature combinatoire.

Abstract

We improve the best known upper and lower bounds for the Erdös and Graham’s $X$ function defined by $X (h) = \max _{h {\mathcal {A}} \sim \mathbb {N}}\ \max _{a \in {\mathcal {A}}^*}\ {\rm ord}^* ({\mathcal {A}} \setminus a)$, where the first maximum is taken over all (exact) bases $\mathcal {A}$ of order at most $h$, where ${\mathcal {A}}^*$ stands for the subset of ${\mathcal {A}}$ composed of the elements $a$ such that ${\mathcal {A}} \setminus \lbrace a\rbrace $ is also a basis and where ${\rm ord}^* ({\mathcal {A}})$ denotes the (exact) order of ${\mathcal {A}}$. Our study leads us, among other things, to prove a new general additive result following from the isoperimetric method and to study three additive problems (in cyclic groups) of a combinatorial nature.

Détail

Publié le : 2004-01-01

MR 2134222 | Zbl 1074.11009 | 1 citation dans Numdam

DOI : https://doi.org/10.5802/aif.2064
Classification:  11B13
Mots clés: base additive, base asymptotique, base exacte, ordre, méthode isopérimétrique, théorème des trois distances

Bibliographie

[1] J. Cassaigne; A. Plagne Grekos' $S$ function has a linear growth, Proc. Amer. Math. Soc, Tome 132 (2004), pp. 2833-2840 | MR 2063100 | Zbl 1051.11011

[2] A.-L. Cauchy Recherches sur les nombres, J. École Polytech, Tome 9 (1813), pp. 99-123

[3] M. Deléglise Recouvrement optimal du cercle par les multiples d'un intervalle, Acta Arith, Tome 59 (1991), pp. 21-35 | MR 1133235 | Zbl 0697.10030

[4] B. Deschamps; G. Grekos Estimation du nombre d'exceptions à ce qu'un ensemble de base privé d'un point reste un ensemble de base, J. Reine Angew. Math, Tome 539 (2001), pp. 45-53 | MR 1863853 | Zbl 1002.11011

[5] P. Erdős; R. L. Graham On bases with an exact order, Acta Arith, Tome 37 (1980), pp. 201-207 | MR 598875 | Zbl 0443.10036

[6] P. Erdős; R. L. Graham Old and new problems and results in combinatorial number theory, Monographies de l'Enseignement Mathématique, Tome 28 (1980) | Zbl 0434.10001

[7] G. Grekos Sur l'ordre d'une base additive, Séminaire de théorie des nombres de Bordeaux, Tome exposé 31 (1987/88) | Zbl 0718.11007

[8] H. Halberstam; K. Roth Sequences, Oxford University Press (1966) | MR 210679 | Zbl 0141.04405

[9] Y. Ould Hamidoune An isoperimetric method in Additive Theory, J. Algebra, Tome 179 (1996), pp. 622-630 | MR 1367866 | Zbl 0842.20029

[10] Y. Ould Hamidoune Subsets with small sums in Abelian groups I: the Vosper property, Europ. J. of Combinatorics, Tome 18 (1997), pp. 541-556 | MR 1455186 | Zbl 0883.05065

[11] Y. Ould Hamidoune Some results in additive number theory I: The critical pair theory, Acta Arith, Tome 96 (2001), pp. 97-119 | MR 1814447 | Zbl 0985.11011

[12] Y. Ould Hamidoune; A. Plagne A generalization of Freiman's $3k-3$ theorem, Acta Arith, Tome 103 (2002), pp. 147-156 | MR 1904869 | Zbl 1007.11011

[13] Y. Ould Hamidoune; A. Plagne A critical pair theorem applied to sum-free sets in abelian groups, Comment. Math. Helv, Tome 79 (2004), pp. 183-207 | MR 2031705 | Zbl 1045.11072

[14] G. H. Hardy; E. M. Wright An introduction to the theory of numbers, Clarendon Press, Oxford University Press (1979) | MR 568909 | Zbl 0423.10001

[15] J. H. B. Kemperman On complexes in a semi-group, Indag. Math, Tome 18 (1956), pp. 247-254 | MR 79005 | Zbl 0072.25605

[16] M. Kneser Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z, Tome 58 (1953), pp. 459-484 | MR 56632 | Zbl 0051.28104

[17] M. Kneser Summenmengen in lokalkompakten abelschen Gruppen, Math. Z, Tome 66 (1956), pp. 88-110 | MR 81438 | Zbl 0073.01702

[18] H. B. Mann Addition theorems, Wiley-Interscience (1965) | Zbl 0127.27203

[19] M. B. Nathanson Additive number theory. Inverse problems and the geometry of sumsets, Springer Verlag, GTM, Tome 165 (1996) | MR 1477155 | Zbl 0859.11003

[20] J. C. M. Nash Some applications of a theorem of M. Kneser, J. Number Theory, Tome 44 (1993), pp. 1-8 | MR 1219479 | Zbl 0780.11007

[21] A. Plagne Removing one element from an exact additive basis, J. Number Theory, Tome 87 (2001), pp. 306-314 | MR 1824151 | Zbl 1067.11005

[22] P. Scherk Distinct elements in a set of sums (solution of a problem of Leo Moser), Amer. Math. Monthly, Tome 62 (1955), p. 46-47

[23] V. T. Sós On the distribution mod,of the sequence $n\alpha$, Ann. Univ. Sci. Budapest. Eötvös Sect. Math, Tome 1 (1958), pp. 127-134 | Zbl 0094.02903

[24] A. Stöhr Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, J. Reine Angew. Math, Tome 194 (1955), pp. 40-65 | MR 75228 | Zbl 0066.03101

[25] A. Stöhr Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe II, J. Reine Angew. Math, Tome 194 (1955), pp. 111-140 | MR 75228 | Zbl 0066.03101

[26] J. Surányi Über die Anordnung der Vielfachen einer reellen Zahl mod 1, Ann. Univ. Sci. Budapest Eötvös Sect. Math, Tome 1 (1958), pp. 107-111 | Zbl 0094.02904

[27] S. Świerczkowski On successive settings of an arc on the circumference of a circumference of a circle, Fund. Math, Tome 46 (1959), pp. 187-189 | MR 104651 | Zbl 0085.27203

[28] A. G. Vosper The critical pairs of subsets of a group of prime order, J. London Math. Soc, Tome 31 (1956), pp. 200-205 | MR 77555 | Zbl 0072.03402

[29] A. G. Vosper Addendum to The critical pairs of subsets of a group of prime order, J. London Math. Soc, Tome 31 (1956), pp. 280-282 | MR 78368 | Zbl 0072.03402