Behrend sequence

Uses your system voice; voice and rate in settings.

Snapshot

≈ 2 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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

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 A is a sequence of integers greater than one, and if M(A) denotes the set of positive integer multiples of members of A , then A is a Behrend sequence if M(A) has natural density one. This means that the proportion of the integers from 1 to n that belong to M(A) converges, in the limit of large 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 A of the prime numbers forms a Behrend sequence if and only if the sum of reciprocals of A diverges. 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.

History

The problem of characterizing these sequence was described as "very difficult" by Paul Erdős in 1979. These sequences were named "Behrend sequences" in 1990 by Richard R. Hall, with a definition using logarithmic density in place of natural density. Hall chose their name in honor of Felix Behrend, who proved that for a Behrend sequence A , the sum of reciprocals of A must diverge. Later, Hall and Gérald Tenenbaum used natural density to define Behrend sequences in place of logarithmic density. 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.

Derived sequences

When A is a Behrend sequence, one may derive another Behrend sequence by omitting from A any finite number of elements. Every Behrend sequence may be decomposed into the disjoint union of infinitely many Behrend sequences.

References

Text derived from https://en.wikipedia.org/w/index.php?oldid=1329713989 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

4 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.