In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, an IP set is a set of
natural number
In mathematics, the natural numbers are those numbers used for counting (as in "there are ''six'' coins on the table") and ordering (as in "this is the ''third'' largest city in the country").
Numbers used for counting are called ''Cardinal n ...
s which contains all finite sums of some
infinite set
In set theory, an infinite set is a set that is not a finite set. Infinite sets may be countable or uncountable.
Properties
The set of natural numbers (whose existence is postulated by the axiom of infinity) is infinite. It is the only set th ...
.
The finite sums of a set ''D'' of natural numbers are all those numbers that can be obtained by adding up the elements of some finite
nonempty
In mathematics, the empty set is the unique set having no elements; its size or cardinality (count of elements in a set) is zero. Some axiomatic set theories ensure that the empty set exists by including an axiom of empty set, while in other ...
subset of ''D''.
The set of all finite sums over ''D'' is often denoted as FS(''D''). Slightly more generally, for a sequence of natural numbers (''n''
i), one can consider the set of finite sums FS((''n''
i)), consisting of the sums of all finite length subsequences of (''n''
i).
A set ''A'' of natural numbers is an IP set if there exists an infinite set ''D'' such that FS(''D'') is a subset of ''A''. Equivalently, one may require that ''A'' contains all finite sums FS((''n''
i)) of a sequence (''n''
i).
Some authors give a slightly different definition of IP sets: They require that FS(''D'') equal ''A'' instead of just being a subset.
The term IP set was coined by
Hillel Furstenberg
Hillel (Harry) Furstenberg ( he, הלל (הארי) פורסטנברג) (born September 29, 1935) is a German-born American-Israeli mathematician and professor emeritus at the Hebrew University of Jerusalem. He is a member of the Israel Academy o ...
and
Benjamin Weiss
Benjamin Weiss ( he, בנימין ווייס; born 1941) is an American-Israeli mathematician known for his contributions
to ergodic theory, topological dynamics, probability theory, game theory, and descriptive set theory.
Biography
Benjamin ( ...
to abbreviate "infinite-dimensional
parallelepiped". Serendipitously, the abbreviation IP can also be expanded to "idempotent" (a set is IP if and only if it is a member of an idempotent
ultrafilter
In the mathematical field of order theory, an ultrafilter on a given partially ordered set (or "poset") P is a certain subset of P, namely a maximal filter on P; that is, a proper filter on P that cannot be enlarged to a bigger proper filter on ...
).
Hindman's theorem
If
is an IP set and
, then at least one
is an IP set.
This is known as ''Hindman's theorem'' or the ''finite sums theorem''.
In different terms, Hindman's theorem states that the class of IP sets is
partition regular
In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.
Given a set X, a collection of subsets \mathbb \subset \mathcal(X) is called ''partition regular'' if every set ''A'' in the coll ...
.
Since the set of natural numbers itself is an IP set and partitions can also be seen as colorings, one can reformulate a special case of Hindman's theorem in more familiar terms: Suppose the natural numbers are "colored" with ''n'' different colors; each natural number gets one and only one of the ''n'' colors. Then there exists a color ''c'' and an infinite set ''D'' of natural numbers, all colored with ''c'', such that every finite sum over ''D'' also has color ''c''.
Hindman's theorem is named for mathematician
Neil Hindman
Neil is a masculine name of Gaelic and Irish origin. The name is an anglicisation of the Irish ''Niall'' which is of disputed derivation. The Irish name may be derived from words meaning "cloud", "passionate", "victory", "honour" or "champion".. A ...
, who proved it in 1974.
The
Milliken–Taylor theorem
In mathematics, the Milliken–Taylor theorem in combinatorics is a generalization of both Ramsey's theorem and Hindman's theorem. It is named after Keith Milliken and Alan D. Taylor.
Let \mathcal_f(\mathbb) denote the set of finite subsets of ...
is a common generalisation of Hindman's theorem and
Ramsey's theorem
In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...
.
Semigroups
The definition of being IP has been extended from subsets of the special
semigroup
In mathematics, a semigroup is an algebraic structure consisting of a set together with an associative internal binary operation on it.
The binary operation of a semigroup is most often denoted multiplicatively: ''x''·''y'', or simply ''xy'', ...
of natural numbers with addition to subsets of semigroups and partial semigroups in general. A variant of Hindman's theorem is true for arbitrary semigroups.
See also
*
Ergodic Ramsey theory Ergodic Ramsey theory is a branch of mathematics where problems motivated by additive combinatorics are proven using ergodic theory.
History
Ergodic Ramsey theory arose shortly after Endre Szemerédi's proof that a set of positive upper density ...
*
Piecewise syndetic set In mathematics, piecewise syndeticity is a notion of largeness of subsets of the natural numbers.
A set S \sub \mathbb is called ''piecewise syndetic'' if there exists a finite subset ''G'' of \mathbb such that for every finite subset ''F'' of \mat ...
*
Syndetic set In mathematics, a syndetic set is a subset of the natural numbers having the property of "bounded gaps": that the sizes of the gaps in the sequence of natural numbers is bounded.
Definition
A set S \sub \mathbb is called syndetic if for some finit ...
*
Thick set In mathematics, a thick set is a set of integers that contains arbitrarily long intervals. That is, given a thick set T, for every p \in \mathbb, there is some n \in \mathbb such that \ \subset T.
Examples
Trivially \mathbb is a thick set. Other w ...
References
Further reading
*
Vitaly Bergelson
Vitaly Bergelson (born 1950 in Kiev) is a mathematical researcher and professor at Ohio State University in Columbus, Ohio. His research focuses on ergodic theory and combinatorics.
Bergelson received his Ph.D in 1984 under Hillel Furstenberg ...
, I. J. H. Knutson, R. McCutcheon
Simultaneous diophantine approximation and VIP Systems ''Acta Arith.'' 116, Academia Scientiarum Polona, (2005), 13-23
*
Vitaly Bergelson
Vitaly Bergelson (born 1950 in Kiev) is a mathematical researcher and professor at Ohio State University in Columbus, Ohio. His research focuses on ergodic theory and combinatorics.
Bergelson received his Ph.D in 1984 under Hillel Furstenberg ...
,
Minimal Idempotents and Ergodic Ramsey Theory ''Topics in Dynamics and Ergodic Theory 8-39, London Math. Soc. Lecture Note Series 310'', Cambridge Univ. Press, Cambridge, (2003)
*
* J. McLeod,
Some Notions of Size in Partial Semigroups, ''Topology Proceedings'', Vol. 25 (2000), pp. 317–332
{{DEFAULTSORT:Ip Set
Semigroup theory
Ergodic theory
Ramsey theory