Behrend sequence

In number theory, a Behrend sequence is an integer sequence whose multiples include almost all integers. The sequences are named after Felix Behrend.

DefinitionEdit

If   is a sequence of integers greater than one, and if   denotes the set of positive integer multiples of members of  , then   is a Behrend sequence if   has natural density one. This means that the proportion of the integers from 1 to   that belong to   converges, in the limit of large  , to one.

ExamplesEdit

The prime numbers form a Behrend sequence, because every integer greater than one is a multiple of a prime number. More generally, a subsequence   of the prime numbers forms a Behrend sequence if and only if the sum of reciprocals of   diverges.[1]

The semiprimes, the products of two prime numbers, also form a Behrend sequence. The only integers that are not multiples of a semiprime are the prime powers. But as the prime powers have density zero, their complement, the multiples of the semiprimes, have density one.[1]

HistoryEdit

The problem of characterizing these sequence was described as "very difficult" by Paul Erdős in 1979.[2]

These sequences were named "Behrend sequences" in 1990 by Richard R. Hall, with a definition using logarithmic density in place of natural density.[3] Hall chose their name in honor of Felix Behrend, who proved that for a Behrend sequence  , the sum of reciprocals of   must diverge.[4] Later, Hall and Gérald Tenenbaum used natural density to define Behrend sequences in place of logarithmic density.[5] This variation in definitions makes no difference in which sequences are Behrend sequences, because the Davenport–Erdős theorem shows that, for sets of multiples, having natural density one and having logarithmic density one are equivalent.[6]

Derived sequencesEdit

When   is a Behrend sequence, one may derive another Behrend sequence by omitting from   any finite number of elements.[5]

Every Behrend sequence may be decomposed into the disjoint union of infinitely many Behrend sequences.[1]

ReferencesEdit

  1. ^ a b c Ruzsa, I. Z.; Tenenbaum, G. (1996), "A note on Behrend sequences", Acta Mathematica Hungarica, 72 (4): 327–337, doi:10.1007/BF00114546, MR 1406402
  2. ^ Erdős, Paul (1979), "Some unconventional problems in number theory" (PDF), Journées Arithmétiques de Luminy (Colloq. Internat. CNRS, Centre Univ. Luminy, Luminy, 1978), Astérisque, 61: 73–82, MR 0556666
  3. ^ Hall, R. R. (1990), "Sets of multiples and Behrend sequences", in Baker, A.; Bollobás, B.; Hajnal, A. (eds.), A tribute to Paul Erdős, Cambridge University Press, pp. 249–258, MR 1117017
  4. ^ Behrend, F. A. (1948), "Generalization of an inequality of Heilbronn and Rohrbach", Bulletin of the American Mathematical Society, 54: 681–684, doi:10.1090/S0002-9904-1948-09056-5, MR 0026081
  5. ^ a b Hall, R. R.; Tenenbaum, G. (1992), "On Behrend sequences", Mathematical Proceedings of the Cambridge Philosophical Society, 112 (3): 467–482, doi:10.1017/S0305004100071140, MR 1177995
  6. ^ Tenenbaum, Gérald (2015), Introduction to Analytic and Probabilistic Number Theory, Graduate Studies in Mathematics, 163 (3rd ed.), Providence, Rhode Island: American Mathematical Society, p. 422, ISBN 978-0-8218-9854-3, MR 3363366