Folkman's theorem is a
theorem
In mathematics, a theorem is a statement that has been proved, or can be proved. The ''proof'' of a theorem is a logical argument that uses the inference rules of a deductive system to establish that the theorem is a logical consequence of th ...
in mathematics, and more particularly in
arithmetic combinatorics In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.
Scope
Arithmetic combinatorics is about combinatorial estimates associated with arithmetic operations (ad ...
and
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...
. According to this theorem, whenever the
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 are
partitioned into finitely many subsets, there exist arbitrarily large sets of numbers all of whose sums belong to the same subset of the partition.
[.] The theorem had been discovered and proved independently by several mathematicians,
[.][.] before it was named "Folkman's theorem", as a memorial to
Jon Folkman, by
Graham
Graham and Graeme may refer to:
People
* Graham (given name), an English-language given name
* Graham (surname), an English-language surname
* Graeme (surname), an English-language surname
* Graham (musician) (born 1979), Burmese singer
* Clan ...
,
Rothschild
Rothschild () is a name derived from the German ''zum rothen Schild'' (with the old spelling "th"), meaning "with the red sign", in reference to the houses where these family members lived or had lived. At the time, houses were designated by sign ...
, and
Spencer.
Statement of the theorem
Let N be the set of positive integers, and suppose that N is partitioned into ''k'' different subsets ''N''
1, ''N''
2, ... ''N''
''k'', where ''k'' is any positive integer. Then Folkman's theorem states that, for every positive integer ''m'', there exists a set ''S''
''m'' and an index ''i''
''m'' such that ''S''
''m'' has ''m'' elements and such that every sum of a nonempty subset of ''S''
''m'' belongs to ''N''
''i''''m''.
Relation to Rado's theorem and Schur's theorem
Schur's theorem
In discrete mathematics, Schur's theorem is any of several theorems of the mathematician Issai Schur. In differential geometry, Schur's theorem is a theorem of Axel Schur. In functional analysis, Schur's theorem is often called Schur's property ...
in Ramsey theory states that, for any finite partition of the positive integers, there exist three numbers ''x'', ''y'', and ''x'' + ''y'' that all belong to the same partition set. That is, it is the special case ''m'' = 2 of Folkman's theorem.
Rado's theorem in Ramsey theory concerns a similar problem statement in which the integers are partitioned into finitely many subsets; the theorem characterizes the integer matrices A with the property that the
system of linear equations
In mathematics, a system of linear equations (or linear system) is a collection of one or more linear equations involving the same variable (math), variables.
For example,
:\begin
3x+2y-z=1\\
2x-2y+4z=-2\\
-x+\fracy-z=0
\end
is a system of three ...
can be guaranteed to have a solution in which every coordinate of the solution vector ''x'' belongs to the same subset of the partition. A system of equations is said to be ''regular'' whenever it satisfies the conditions of Rado's theorem; Folkman's theorem is equivalent to the regularity of the system of equations
:
where ''T'' ranges over each nonempty subset of the set
Multiplication versus addition
It is possible to replace addition by multiplication in Folkman's theorem: if the natural numbers are finitely partitioned, there exist arbitrarily large sets ''S'' such that all products of nonempty subsets of ''S'' belong to a single partition set. Indeed, if one restricts ''S'' to consist only of
powers of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negative ...
, then this result follows immediately from the additive version of Folkman's theorem. However, it is open whether there exist arbitrarily large sets such that all sums and all products of nonempty subsets belong to a single partition set. The first example of nonlinearity in Ramsey Theory which does not consist of monomials was given, independently, by Furstenberg and Sarkozy in 1977, with the family , result which was further improved by Bergelson in 1987. In 2016, J. Moreira proved there exists a set of the form contained in an element of the partition
[.] However it is not even known whether there must necessarily exist a set of the form for which all four elements belong to the same partition set.
Canonical Folkman Theorem
Let
denote the set of all finite sums of elements of
. Let
be a (possibly infinite) coloring of the positive integers, and let
be an arbitrary positive integer. There exists
such that at least one of the following 3 conditions holds.
1)
is a monochromatic set.
2)
is a rainbow set.
3) For any