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

$S=\{s_1,s_2,s_3,\dots\}$

is one such that the infinite sum

$\frac{1}{s_1}+\frac{1}{s_2}+\frac{1}{s_3}+\cdots$

converges. A large set is any other set of positive integers.

For example, the set $\{1,2,3,4,5,\dots\}$ of all positive integers is known to be a large set (see Harmonic series (mathematics)), and the set $\{1,2,4,8,\dots\}$ 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 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 $S=\{s_1,s_2,s_3,\dots\}$ is large iff the set spanned by

$\{1,x^{s_1},x^{s_2},x^{s_3},\dots\}$

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

$\{\dots, 6, 8, \dots, 16, 18, \dots, 66, 68, 69, 80, \dots, \}$