On Erdös and Graham’s X function

Alain Plagne[1]

  • [1] Ecole polytechnique, Centre de mathématiques Laurent Schwartz, UMR 7640 du CNRS, 91128 Palaiseau cedex (France)

Annales de l’institut Fourier (2004)

  • Volume: 54, Issue: 6, page 1717-1767
  • ISSN: 0373-0956

Abstract

top
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.

How to cite

top

Plagne, Alain. "A propos de la fonction $X$ d’Erdös et Graham." Annales de l’institut Fourier 54.6 (2004): 1717-1767. <http://eudml.org/doc/116157>.

@article{Plagne2004,
abstract = {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.},
affiliation = {Ecole polytechnique, Centre de mathématiques Laurent Schwartz, UMR 7640 du CNRS, 91128 Palaiseau cedex (France)},
author = {Plagne, Alain},
journal = {Annales de l’institut Fourier},
keywords = {additive basis; asymptotic basis; exact basis; order; isoperimetric method; three distance theorem},
language = {fre},
number = {6},
pages = {1717-1767},
publisher = {Association des Annales de l'Institut Fourier},
title = {A propos de la fonction $X$ d’Erdös et Graham},
url = {http://eudml.org/doc/116157},
volume = {54},
year = {2004},
}

TY - JOUR
AU - Plagne, Alain
TI - A propos de la fonction $X$ d’Erdös et Graham
JO - Annales de l’institut Fourier
PY - 2004
PB - Association des Annales de l'Institut Fourier
VL - 54
IS - 6
SP - 1717
EP - 1767
AB - 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.
LA - fre
KW - additive basis; asymptotic basis; exact basis; order; isoperimetric method; three distance theorem
UR - http://eudml.org/doc/116157
ER -

References

top
  1. J. Cassaigne, A. Plagne, Grekos’ S function has a linear growth, Proc. Amer. Math. Soc 132 (2004), 2833-2840 Zbl1051.11011MR2063100
  2. A.-L. Cauchy, Recherches sur les nombres, J. École Polytech 9 (1813), 99-123 
  3. M. Deléglise, Recouvrement optimal du cercle par les multiples d'un intervalle, Acta Arith 59 (1991), 21-35 Zbl0697.10030MR1133235
  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 539 (2001), 45-53 Zbl1002.11011MR1863853
  5. P. Erdős, R. L. Graham, On bases with an exact order, Acta Arith 37 (1980), 201-207 Zbl0443.10036MR598875
  6. P. Erdős, R. L. Graham, Old and new problems and results in combinatorial number theory, Monographies de l'Enseignement Mathématique 28 (1980) Zbl0434.10001
  7. G. Grekos, Sur l'ordre d'une base additive, Séminaire de théorie des nombres de Bordeaux exposé 31 (1987/88) Zbl0718.11007
  8. H. Halberstam, K. Roth, Sequences, (1966), Oxford University Press Zbl0141.04405MR210679
  9. Y. ould Hamidoune, An isoperimetric method in Additive Theory, J. Algebra 179 (1996), 622-630 Zbl0842.20029MR1367866
  10. Y. ould Hamidoune, Subsets with small sums in Abelian groups I: the Vosper property, Europ. J. of Combinatorics 18 (1997), 541-556 Zbl0883.05065MR1455186
  11. Y. ould Hamidoune, Some results in additive number theory I: The critical pair theory, Acta Arith 96 (2001), 97-119 Zbl0985.11011MR1814447
  12. Y. ould Hamidoune, A. Plagne, A generalization of Freiman’s 3 k - 3 theorem, Acta Arith 103 (2002), 147-156 Zbl1007.11011MR1904869
  13. Y. ould Hamidoune, A. Plagne, A critical pair theorem applied to sum-free sets in abelian groups, Comment. Math. Helv 79 (2004), 183-207 Zbl1045.11072MR2031705
  14. G. H. Hardy, E. M. Wright, An introduction to the theory of numbers, (1979), Clarendon Press, Oxford University Press Zbl0423.10001MR568909
  15. J. H. B. Kemperman, On complexes in a semi-group, Indag. Math 18 (1956), 247-254 Zbl0072.25605MR79005
  16. M. Kneser, Abschätzung der asymptotischen Dichte von Summenmengen, Math. Z 58 (1953), 459-484 Zbl0051.28104MR56632
  17. M. Kneser, Summenmengen in lokalkompakten abelschen Gruppen, Math. Z 66 (1956), 88-110 Zbl0073.01702MR81438
  18. H. B. Mann, Addition theorems, (1965), Wiley-Interscience Zbl0127.27203
  19. M. B. Nathanson, Additive number theory. Inverse problems and the geometry of sumsets, 165 (1996), Springer Verlag Zbl0859.11003MR1477155
  20. J. C. M. Nash, Some applications of a theorem of M. Kneser, J. Number Theory 44 (1993) Zbl0780.11007MR1219479
  21. A. Plagne, Removing one element from an exact additive basis, J. Number Theory 87 (2001), 306-314 Zbl1067.11005MR1824151
  22. P. Scherk, Distinct elements in a set of sums (solution of a problem of Leo Moser), Amer. Math. Monthly 62 (1955), 46-47 
  23. V. T. Sós, On the distribution mod,of the sequence n α , Ann. Univ. Sci. Budapest. Eötvös Sect. Math 1 (1958), 127-134 Zbl0094.02903
  24. A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe I, J. Reine Angew. Math 194 (1955), 40-65 Zbl0066.03101MR75228
  25. A. Stöhr, Gelöste und ungelöste Fragen über Basen der natürlichen Zahlenreihe II, J. Reine Angew. Math 194 (1955), 111-140 Zbl0066.03101MR75228
  26. J. Surányi, Über die Anordnung der Vielfachen einer reellen Zahl mod 1, Ann. Univ. Sci. Budapest Eötvös Sect. Math 1 (1958), 107-111 Zbl0094.02904
  27. S. Świerczkowski, On successive settings of an arc on the circumference of a circumference of a circle, Fund. Math 46 (1959), 187-189 Zbl0085.27203MR104651
  28. A. G. Vosper, The critical pairs of subsets of a group of prime order, J. London Math. Soc 31 (1956), 200-205 Zbl0072.03402MR77555
  29. A. G. Vosper, Addendum to The critical pairs of subsets of a group of prime order, J. London Math. Soc 31 (1956), 280-282 Zbl0072.03402MR78368

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.