Small set (combinatorics)
From Wikipedia, the free encyclopedia
- For other uses of the term, see small set.
In combinatorics, a small set of positive integers
is one such that the infinite sum
converges. A large set is any other set of positive integers.
For example, the set 
of all positive integers is known to be a large set (see Harmonic series (mathematics)), and the set 
of powers of 2 is known to be a small set. There are many sets about which it is not known whether they are large or small.
A union of finitely many small sets is small, as the sum of two convergent series is a convergent series. Also, a large set minus a small set is still large. The set of prime numbers has been proven to be large. The set of square numbers is small.
The Müntz-Szasz theorem is that a set 
is large iff the set spanned by
is dense in the uniform norm topology of continuous functions on a closed interval. This is a generalization of the Weierstrass approximation theorem.
Another known fact is that the set of numbers whose decimal representations exclude 7 (or any digit one prefers) is small. That is, for example, the set
is small. (This has been generalized to other bases as well.)
Paul Erdős famously asked the question of whether any set that does not contain arbitrarily long arithmetic progressions must necessarily be small. (The converse follows immediately from the divergence of the harmonic series.) He offered a prize of $3000 for the solution to this problem, more than for any of his other conjectures, and joked that this prize offer violated the minimum wage law.[1]
[edit] References
- A. D. Wadhwa (1975). An interesting subseries of the harmonic series. American Mathematical Monthly 82 (9) 931–933.
- ^ Carl Pomerance, "Paul Erdos, Number Theorist Extraordinaire". Notices of the AMS. January, 1998.
