Folkman's theorem
Encyclopedia
Folkman's theorem is a theorem
in mathematics, and more particularly in arithmetic combinatorics
and Ramsey theory
. According to this theorem, whenever the natural number
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, Rothschild
, and Spencer.
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 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
, 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. 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.
by Ronald L. Graham, Bruce Lee Rothschild
, and Joel H. Spencer, in their book on Ramsey theory.
Theorem
In mathematics, a theorem is a statement that has been proven on the basis of previously established statements, such as other theorems, and previously accepted statements, such as axioms...
in mathematics, and more particularly in arithmetic combinatorics
Arithmetic combinatorics
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...
and Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
. According to this theorem, whenever the natural number
Natural number
In mathematics, the natural numbers are the ordinary whole numbers used for counting and ordering . These purposes are related to the linguistic notions of cardinal and ordinal numbers, respectively...
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, Rothschild
Bruce Lee Rothschild
Bruce Lee Rothschild is a professor of mathematics at the University of California, Los Angeles specializing in combinatorial mathematics. Rothschild was born in 1941 in Los Angeles. He got his Ph.D. from Yale University in 1967. Rothschild wrote several papers with Paul Erdős, giving him an Erdős...
, and Spencer.
Statement of the theorem
Let N be the set {1, 2, 3, ...} of positive integers, and suppose that N is partitioned into k different subsets N1, N2, ... Nk, where k is any positive integer. Then Folkman's theorem states that, for every positive integer m, there exists a set Sm and an index im such that Sm has m elements and such that every sum of a nonempty subset of Sm belongs to Nim.Relation to Rado's theorem and Schur's theorem
Schur's theoremSchur's theorem
In discrete mathematics, Schur's theorem is either of two different theorems of the mathematician Issai Schur. In differential geometry, Schur's theorem is a theorem of A. Schur...
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
Rado's theorem (Ramsey theory)
Rado's theorem is a theorem from the branch of mathematics known as Ramsey theory. It is named for the German mathematician Richard Rado. It was proved in his thesis, Studien zur Kombinatorik....
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 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 twoPower of two
In mathematics, a power of two means a number of the form 2n where n is an integer, i.e. the result of exponentiation with as base the number two and as exponent the integer n....
, 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. 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.
Previous results
Variants of Folkman's theorem had been proved by Richard Rado and by J. H. Sanders. Folkman's theorem was named in memory of Jon FolkmanJon Folkman
Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.-Schooling:Folkman was a Putnam Fellow in 1960. He received his Ph.D...
by Ronald L. Graham, Bruce Lee Rothschild
Bruce Lee Rothschild
Bruce Lee Rothschild is a professor of mathematics at the University of California, Los Angeles specializing in combinatorial mathematics. Rothschild was born in 1941 in Los Angeles. He got his Ph.D. from Yale University in 1967. Rothschild wrote several papers with Paul Erdős, giving him an Erdős...
, and Joel H. Spencer, in their book on Ramsey theory.