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, pp. 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: 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{\textquoteright}Erd\"os} et {Graham}},
     journal = {Annales de l'Institut Fourier},
     pages = {1717--1767},
     publisher = {Association des Annales de l{\textquoteright}institut Fourier},
     volume = {54},
     number = {6},
     year = {2004},
     doi = {10.5802/aif.2064},
     mrnumber = {2134222},
     zbl = {1074.11009},
     language = {fr},
     url = {https://aif.centre-mersenne.org/articles/10.5802/aif.2064/}
}
TY  - JOUR
TI  - A propos de la fonction $X$ d’Erdös et Graham
JO  - Annales de l'Institut Fourier
PY  - 2004
DA  - 2004///
SP  - 1717
EP  - 1767
VL  - 54
IS  - 6
PB  - Association des Annales de l’institut Fourier
UR  - https://aif.centre-mersenne.org/articles/10.5802/aif.2064/
UR  - https://www.ams.org/mathscinet-getitem?mr=2134222
UR  - https://zbmath.org/?q=an%3A1074.11009
UR  - https://doi.org/10.5802/aif.2064
DO  - 10.5802/aif.2064
LA  - fr
ID  - AIF_2004__54_6_1717_0
ER  - 
%0 Journal Article
%T A propos de la fonction $X$ d’Erdös et Graham
%J Annales de l'Institut Fourier
%D 2004
%P 1717-1767
%V 54
%N 6
%I Association des Annales de l’institut Fourier
%U https://doi.org/10.5802/aif.2064
%R 10.5802/aif.2064
%G fr
%F 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. https://aif.centre-mersenne.org/articles/10.5802/aif.2064/

[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 | EuDML: 278989 | 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 | EuDML: 278278 | 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 | EuDML: 169366 | MR: 56632 | Zbl: 0051.28104

[17] M. Kneser Summenmengen in lokalkompakten abelschen Gruppen, Math. Z, Tome 66 (1956), pp. 88-110 | EuDML: 169620 | 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, GTM, Tome 165, Springer Verlag, 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 | EuDML: 150281 | 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 | EuDML: 150285 | 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 | EuDML: 213503 | 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

Cited by Sources: