Large set (combinatorics) explained

In combinatorial mathematics, a large set of positive integers

S=\{s0,s1,s2,s3,...\}

is one such that the infinite sum of the reciprocals

1+
s0
1+
s1
1+
s2
1
s3

+ …

diverges. A small set is any subset of the positive integers that is not large; that is, one whose sum of reciprocals converges.

Large sets appear in the Müntz–Szász theorem and in the Erdős conjecture on arithmetic progressions.

Examples

\{1,2,3,4,5,...\}

of all positive integers is a large set; this statement is equivalent to the divergence of the harmonic series. More generally, any arithmetic progression (i.e., a set of all integers of the form an + b with a ≥ 1, b ≥ 1 and n = 0, 1, 2, 3, ...) is a large set.

\{1,2,...,5,6,8,9,...,15,16,18,19,...,65,66,68,69,80,81,...\}

of integers whose decimal expansion does not include the digit 7 is small. Such series are called Kempner series.

Properties

S=\{s1,s2,s3,...\}

is large if and only if the set of polynomials spanned by \ is dense in the uniform norm topology of continuous functions on a closed interval in the positive real numbers. This is a generalization of the Stone–Weierstrass theorem.

Open problems involving large sets

Paul Erdős conjectured that all large sets contain arbitrarily long arithmetic progressions. He offered a prize of $3000 for a proof, more than for any of his other conjectures, and joked that this prize offer violated the minimum wage law.[1] The question is still open.

It is not known how to identify whether a given set is large or small in general. As a result, there are many sets which are not known to be either large or small.

See also

References

Notes and References

  1. [Carl Pomerance]