A propos de la fonction X d’Erdös et Graham  [ On Erdös and Graham’s X function ]
Annales de l'Institut Fourier, Volume 54 (2004) no. 6, p. 1717-1767

We improve the best known upper and lower bounds for the Erdös and Graham’s X function defined by X(h)=max h𝒜 max a𝒜 * ord * (𝒜a), where the first maximum is taken over all (exact) bases 𝒜 of order at most h, where 𝒜 * stands for the subset of 𝒜 composed of the elements a such that 𝒜{a} is also a basis and where ord * (𝒜) denotes the (exact) order of 𝒜. 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.

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𝒜 max a𝒜 * ord * (𝒜a), où le premier maximum est pris sur toutes les bases (exactes) 𝒜 d’ordre au plus h, où 𝒜 * désigne le sous-ensemble de 𝒜 composé des éléments a tels que 𝒜{a} soit encore une base et où, enfin, ord * (𝒜) désigne l’ordre (exact) de 𝒜. 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.

DOI : https://doi.org/10.5802/aif.2064
Classification:  11B13
Keywords: additive basis, asymptotic basis, exact basis, order, isoperimetric method, three distance theorem
@article{AIF_2004__54_6_1717_0,
     author = {Plagne, Alain},
     title = {A propos de la fonction $X$ d'Erd\"os et Graham},
     journal = {Annales de l'Institut Fourier},
     publisher = {Association des Annales de l'institut Fourier},
     volume = {54},
     number = {6},
     year = {2004},
     pages = {1717-1767},
     doi = {10.5802/aif.2064},
     zbl = {1074.11009},
     mrnumber = {2134222},
     language = {fr},
     url = {http://www.numdam.org/item/AIF_2004__54_6_1717_0}
}
Plagne, Alain. A propos de la fonction $X$ d’Erdös et Graham. Annales de l'Institut Fourier, Volume 54 (2004) no. 6, pp. 1717-1767. doi : 10.5802/aif.2064. http://www.numdam.org/item/AIF_2004__54_6_1717_0/

[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α, 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