Small set (combinatorics)

Small set (combinatorics)

In combinatorial mathematics, a small set of positive integers

:S = {s_0,s_1,s_2,s_3,dots}

is one such that the infinite sum:frac{1}{s_0}+frac{1}{s_1}+frac{1}{s_2}+frac{1}{s_3}+cdots
converges. A large set is any other set of positive integers (i.e. whose sum diverges).

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 so is the set obtained from any arithmetic sequence (i.e. of the form a*n+b with a >= 0, b >=1 and n=0,1,2,3,...) where a=0, b=1 give the multiset {1,1,1,dots} and a=1, b=1 give {1,2,3,4,5,dots}.

The set of square numbers is small. So is the set of cube numbers, the set of 4-th powers, and so on... And so is the set of any polynomial numbers of degree k >= 2 (i.e. of the form a_k*n^k+a_{k-1}*n^{k-1}+...+a_2*n^2+a_1*n^1+a_0 , with a_0 >= 1, a_i >= 0 for all i >= 1 but a_i > 0 for at least one i >= 2, and n=0,1,2,3,...). Polynomial numbers of degree k < 2 give an arithmetic sequence (which form a large set.) Polynomial numbers of degree 2 give a quadratic sequence which form a small set. Polynomial numbers of degree 3 give a cubic sequence which also form a small set. And so on...

The set {1,2,4,8,dots} of powers of 2 is known to be a small set, and so is the set of any geometric sequence (i.e. of the form a*b^n with a >= 1, b >= 2 and n=0,1,2,3,...).

The set of prime numbers has been proven to be large. The set of twin primes has been proven to be small (see Brun's constant). A property of prime powers used frequently in analytic number theory is that the set of prime powers which are not prime (i.e. all p^n with n >= 2) is a small set although the primes are a large set.

A union of finitely many small sets is small, as the sum of two convergent series is a convergent series. A union of infinitely many small sets is either a small set (e.g. the sets of p^2, p^3, p^4, ... where p is prime) or a large set (example?). Also, a large set minus a small set is still large. A large set minus a large set is either a small set (e.g. the set of all prime powers p^n with n >= 1 minus the set of all primes) or a large set (e.g. the set of all positive integers minus the set of all positive even numbers).

There are many sets about which it is not known whether they are large or small.

The Müntz–Szász theorem is that a set S={s_1,s_2,s_3,dots} is large if and only if 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 Stone-Weierstrass 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 }

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. 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.Carl Pomerance, "Paul Erdos, Number Theorist Extraordinaire". "Notices of the AMS". January, 1998.]

References

* A. D. Wadhwa (1975). An interesting subseries of the harmonic series. "American Mathematical Monthly" 82 (9) 931&ndash;933.

ee also

*Harmonic series (mathematics)
*Series (mathematics)


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Small set — In mathematics, the term small set may refer to: *Small set (category theory) *Small set (combinatorics)ee also*Ideal (set theory) *Natural density *Large set (Ramsey theory) …   Wikipedia

  • List of combinatorics topics — This is a list of combinatorics topics.A few decades ago it might have been said that combinatorics is little more than a way to classify poorly understood problems, and some standard remedies. Great progress has been made since 1960.This page is …   Wikipedia

  • List of exceptional set concepts — This is a list of exceptional set concepts. In mathematics, and in particular in mathematical analysis, it is very useful to be able to characterise subsets of a given set X as small , in some definite sense, or large if their complement in X is… …   Wikipedia

  • combinatorics — /keuhm buy neuh tawr iks, tor , kom beuh /, n. (used with singular v.) See combinatorial analysis. * * * Branch of mathematics concerned with the selection, arrangement, and combination of objects chosen from a finite set. The number of possible… …   Universalium

  • Set theory — This article is about the branch of mathematics. For musical set theory, see Set theory (music). A Venn diagram illustrating the intersection of two sets. Set theory is the branch of mathematics that studies sets, which are collections of objects …   Wikipedia

  • Small cancellation theory — In the mathematical subject of group theory, small cancellation theory studies groups given by group presentations satisfying small cancellation conditions, that is where defining relations have small overlaps with each other. It turns out that… …   Wikipedia

  • Set notation — Sets are fundamental objects in mathematics. Intuitively, a set is merely a collection of elements or members . There are various conventions for textually denoting sets. In any particular situation, an author typically chooses from among these… …   Wikipedia

  • Large set — In mathematics, the term large set is sometimes used to refer to any set that is large in some sense. It has specialized meanings in three branches of mathematics: *Large set (category theory) *Large set (combinatorics) *Large set (Ramsey… …   Wikipedia

  • Arithmetic combinatorics — arose out of the interplay between number theory, combinatorics, ergodic theory and harmonic analysis. It is about combinatorial estimates associated with arithmetic operations (addition, subtraction, multiplication, and division). Additive… …   Wikipedia

  • Causal set theory bibliography — Main article: Causal Sets This Causal Set Theory Bibliography is intended to aid causal set research. It gathers together academic papers, books, talks and PhD theses related to causal set theory and is intended to help readers find references… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”