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.

Definition

If ${\displaystyle A}$ is a sequence of integers greater than one, and if ${\displaystyle M(A)}$ denotes the set of positive integer multiples of members of ${\displaystyle A}$, then ${\displaystyle A}$ is a Behrend sequence if ${\displaystyle M(A)}$ has natural density one. This means that the proportion of the integers from 1 to ${\displaystyle n}$ that belong to ${\displaystyle M(A)}$ converges, in the limit of large ${\displaystyle n}$, to one.

Examples

The prime numbers form a Behrend sequence, because every integer greater than one is a multiple of a prime number. More generally, a subsequence ${\displaystyle A}$ of the prime numbers forms a Behrend sequence if and only if the sum of reciprocals of ${\displaystyle A}$ 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]

History

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 ${\displaystyle A}$, the sum of reciprocals of ${\displaystyle A}$ 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 sequences

When ${\displaystyle A}$ is a Behrend sequence, one may derive another Behrend sequence by omitting from ${\displaystyle A}$ any finite number of elements.[5]

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

References

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