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

Plagne, Alain

Annales de l'Institut Fourier, Tome 54 (2004) no. 6, pp. 1717-1767.

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\left(h\right)={max}_{h𝒜\sim \mathbb{N}}{max}_{a\in {𝒜}^{*}}{\mathrm{ord}}^{*}\left(𝒜\setminus a\right)$, 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 $𝒜\setminus \left\{a\right\}$ soit encore une base et où, enfin, ${\mathrm{ord}}^{*}\left(𝒜\right)$ 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.

We improve the best known upper and lower bounds for the Erdös and Graham’s $X$ function defined by $X\left(h\right)={max}_{h𝒜\sim \mathbb{N}}{max}_{a\in {𝒜}^{*}}{\mathrm{ord}}^{*}(𝒜\setminus 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 $𝒜\setminus \left\{a\right\}$ is also a basis and where ${\mathrm{ord}}^{*}\left(𝒜\right)$ 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.

Classification : 11B13
Mot clés : base additive, base asymptotique, base exacte, ordre, méthode isopérimétrique, théorème des trois distances
Keywords: additive basis, asymptotic basis, exact basis, order, isoperimetric method, three distance theorem

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

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

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

[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, Volume 539 (2001), pp. 45-53 | MR | Zbl

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

[22] P. Scherk Distinct elements in a set of sums (solution of a problem of Leo Moser), Amer. Math. Monthly, Volume 62 (1955), pp. 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, Volume 1 (1958), pp. 127-134 | Zbl

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

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

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

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

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

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