Folkman's theorem

Last updated January 15, 2024

Folkman's theorem is a theorem in mathematics, and more particularly in arithmetic combinatorics and Ramsey theory. According to this theorem, whenever the natural numbers 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.^[1] The theorem had been discovered and proved independently by several mathematicians,^[2]^[3] before it was named "Folkman's theorem", as a memorial to Jon Folkman, by Graham, Rothschild, and Spencer.^[1]

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 N₁, N₂, ... 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}.^[1]

Relation to Rado's theorem and Schur's theorem

Schur's theorem 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 Ax = 0 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

x_{T}=\sum _{i\in T}x_{\{i\}},

where T ranges over each nonempty subset of the set {1, 2, ..., m}.^[1]

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, 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 {x, x + y²}, result which was further improved by Bergelson in 1987. In 2016, J. Moreira proved there exists a set of the form {x, x + y, xy} contained in an element of the partition^[4] However it is not even known whether there must necessarily exist a set of the form {x, y, x + y, xy} for which all four elements belong to the same partition set.^[1]

Canonical Folkman Theorem

Let $FS(\{x_{i}\}_{i=1}^{n})$ denote the set of all finite sums of elements of $\{x_{i}\}_{i=1}^{n}$ . Let $C$ be a (possibly infinite) coloring of the positive integers, and let $n$ be an arbitrary positive integer. There exists $\{x_{i}\}_{i=1}^{n}$ such that at least one of the following 3 conditions holds.

1) $FS(\{x_{i}\}_{i=1}^{n})$ is a monochromatic set.

2) $FS(\{x_{i}\}_{i=1}^{n})$ is a rainbow set.

3) For any $B\subseteq [1,n]$ , the color of $\sum _{i\in B}x_{i}$ is determined solely by $\min(B)$ .

Previous results

Variants of Folkman's theorem had been proved by Richard Rado and by J. H. Sanders.^[2]^[3]^[1] Folkman's theorem was named in memory of Jon Folkman by Ronald Graham, Bruce Lee Rothschild, and Joel Spencer, in their book on Ramsey theory.^[1]

Related Research Articles

In mathematics, a (real) interval is the set of all real numbers lying between two fixed endpoints with no "gaps". Each endpoint is either a real number or positive or negative infinity, indicating the interval extends without a bound. An interval can contain neither endpoint, either endpoint, or both endpoints.

Hilbert's tenth problem is the tenth on the list of mathematical problems that the German mathematician David Hilbert posed in 1900. It is the challenge to provide a general algorithm that, for any given Diophantine equation, can decide whether the equation has a solution with all unknowns taking integer values.

In mathematics, the well-ordering principle states that every non-empty set of positive integers contains a least element. In other words, the set of positive integers is well-ordered by its "natural" or "magnitude" order in which $precedes if and only if is either or the sum of and some positive integer.$

A finite geometry is any geometric system that has only a finite number of points. The familiar Euclidean geometry is not finite, because a Euclidean line contains infinitely many points. A geometry based on the graphics displayed on a computer screen, where the pixels are considered to be the points, would be a finite geometry. While there are many systems that could be called finite geometries, attention is mostly paid to the finite projective and affine spaces because of their regularity and simplicity. Other significant types of finite geometry are finite Möbius or inversive planes and Laguerre planes, which are examples of a general type called Benz planes, and their higher-dimensional analogs such as higher finite inversive geometries.

In general topology, a branch of mathematics, a non-empty family A of subsets of a set $is said to have the finite intersection property (FIP) if the intersection over any finite subcollection of is non-empty. It has the strong finite intersection property (SFIP) if the intersection over any finite subcollection of is infinite. Sets with the finite intersection property are also called centered systems and filter subbases .$

In geometry, Radon's theorem on convex sets, published by Johann Radon in 1921, states that:

Any set of d + 2 points in R^d can be partitioned into two sets whose convex hulls intersect.

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, also due to Issai Schur.

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 mathematics, an IP set is a set of natural numbers which contains all finite sums of some infinite set.

In combinatorics, a branch of mathematics, partition regularity is one notion of largeness for a collection of sets.

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.

In the mathematical field of graph theory, the Rado graph, Erdős–Rényi graph, or random graph is a countably infinite graph that can be constructed by choosing independently at random for each pair of its vertices whether to connect the vertices by an edge. The names of this graph honor Richard Rado, Paul Erdős, and Alfréd Rényi, mathematicians who studied it in the early 1960s; it appears even earlier in the work of Wilhelm Ackermann (1937). The Rado graph can also be constructed non-randomly, by symmetrizing the membership relation of the hereditarily finite sets, by applying the BIT predicate to the binary representations of the natural numbers, or as an infinite Paley graph that has edges connecting pairs of prime numbers congruent to 1 mod 4 that are quadratic residues modulo each other.

Kuratowski's free set theorem, named after Kazimierz Kuratowski, is a result of set theory, an area of mathematics. It is a result which has been largely forgotten for almost 50 years, but has been applied recently in solving several lattice theory problems, such as the congruence lattice problem.

In the mathematical field of set theory, an ideal is a partially ordered collection of sets that are considered to be "small" or "negligible". Every subset of an element of the ideal must also be in the ideal, and the union of any two elements of the ideal must also be in the ideal.

In mathematics, infinitary combinatorics, or combinatorial set theory, is an extension of ideas in combinatorics to infinite sets. Some of the things studied include continuous graphs and trees, extensions of Ramsey's theorem, and Martin's axiom. Recent developments concern combinatorics of the continuum and combinatorics on successors of singular cardinals.

In mathematics, arithmetic combinatorics is a field in the intersection of number theory, combinatorics, ergodic theory and harmonic analysis.

The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.

Jon Hal Folkman was an American mathematician, a student of John Milnor, and a researcher at the RAND Corporation.

In mathematics, structural Ramsey theory is a categorical generalisation of Ramsey theory, rooted in the idea that many important results of Ramsey theory have "similar" logical structures. The key observation is noting that these Ramsey-type theorems can be expressed as the assertion that a certain category has the Ramsey property.

References

1 2 3 4 5 6 7 Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), "3.4 Finite sums and finite unions (Folkman's theorem)", Ramsey Theory, Wiley-Interscience, pp. 65–69.
1 2 Rado, R. (1970), "Some partition theorems", Combinatorial theory and its applications, III: Proc. Colloq., Balatonfüred, 1969, Amsterdam: North-Holland, pp. 929–936, MR 0297585 .
1 2 Sanders, Jon Henry (1968), A generalization of Schur's theorem, Ph.D. thesis, Yale University, MR 2617864 .
↑ Moreira, J. (2017), "Monochromatic sums and products in N", Annals of Mathematics, SECOND SERIES, Vol. 185, No. 3, Evanston: Mathematics Department, Princeton University, pp. 1069–1090, MR 3664819 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[grs-1] 1 2 3 4 5 6 7 Graham, Ronald L.; Rothschild, Bruce L.; Spencer, Joel H. (1980), "3.4 Finite sums and finite unions (Folkman's theorem)", Ramsey Theory, Wiley-Interscience, pp. 65–69.

[Rado-2] 1 2 Rado, R. (1970), "Some partition theorems", Combinatorial theory and its applications, III: Proc. Colloq., Balatonfüred, 1969, Amsterdam: North-Holland, pp. 929–936, MR 0297585 .

[Sanders-3] 1 2 Sanders, Jon Henry (1968), A generalization of Schur's theorem, Ph.D. thesis, Yale University, MR 2617864 .

[Moreira-4] Moreira, J. (2017), "Monochromatic sums and products in N", Annals of Mathematics, SECOND SERIES, Vol. 185, No. 3, Evanston: Mathematics Department, Princeton University, pp. 1069–1090, MR 3664819 .

[1]

[2]

[3]

[4]