Summer Kisner – Schur’s theorem

My student Summer Kisner completed her M.S. this term, and graduated on Saturday.

2013–5-18 Summer

Here is a copy of the slides she used on her defense. (The slides display incorrectly on my computer, but it seems to be a problem on my end. If it is not, please let me know, and I’ll see what I can do.)

Her thesis, Schur’s theorem and related topics in Ramsey theory, discusses Schur’s theorem, one of the first result in what we now call Ramsey theory. The result states that if the positive integers are partitioned into finitely many sets, , then for some , , there are integers (not necessarily different), all of them in , such that . One usually describes this in terms of colors: We color the positive integers with finitely many colors, and there is a monochromatic triple with .

This result is a cornerstone of Ramsey theory. It was significantly generalized by Rado (using the notion of partition regularity), and is connected to van der Waerden’s and Szemerédi’s famous results.

Nowadays, Schur’s theorem is typically proved as a corollary of Ramsey’s theorem. This is usually stated in terms of graphs, but I will use the notation from the partition calculus. Let denote the collection of -sized subsets of the set . Suppose that is infinite, and consider a coloring , where the set of colors is finite. Ramsey’s theorem asserts that under these assumptions, there is an infinite subset of that is homogeneous or monochromatic for , in the sense that assigns the same color to all -sized subsets of . In fact, we have finitary versions of this result: For any and any , if we only require that has size at least , then there is an such that it suffices to assume that has size at least . Even for , the study of Ramsey numbers, the least seen as a function of , proves to be incredibly difficult and computationally unfeasible. For example, if , then we know that , but its exact value is not known.

To deduce Schur’s theorem from Ramsey’s, let be such that, for any for coloring of using colors, there is a monochromatic set of size . The least such we denote . We want to show that if , then there is a monochromatic solution to the equation . In fact, we claim that it suffices to consider rather than the whole set of positive integers. Indeed, given a partition , consider the coloring of where if , then the set $\{a,b\}$ has color , where . By definition of , we can find such that all have the same color. Now notice that , that is, are monochromatic for the original coloring of .

An easy inductive argument gives us that , so this gives the upper bound for the so-called -th Schur number . To see the upper bound , note that , and verify inductively that : Suppose that , and consider a coloring of with . Fix an element , and note that for some color there are elements such that has color . Let be the set of all these , that is, has color . Note that if for some we have that has color as well, then is monochromatic with color . Hence we may assume that the coloring, restricted to , only uses colors. We are now done, since .

Schur’s original proof predated Ramsey, and gives a slightly better bound than . Indeed, from his proof, we obtain that .

In terms of lower bounds, one can quickly check by induction that . Indeed, , since . Given a coloring of using colors and without monochromatic triples, we describe a coloring of using colors , again without monochromatic triples. This gives the result. To define , start by letting for . Now let for , and finally let for .

Slightly better bounds are known. For example, Anne Penfold Street shows that in

 W.D. Wallis, Anne Penfold Street, Jennifer Seberry Wallis. Combinatorics: Room squares, sum-free sets, Hadamard matrices. Lecture Notes in Mathematics, Vol. 292. Springer-Verlag, Berlin-New York, (1972). MR0392580 (52 #13397).

Schur proved his theorem in order to establish a result related to Fermat’s last theorem, namely that it cannot be established by a naive argument involving modular arithmetic: Suppose that are integers, and . Then, for any prime , the equality holds modulo and, if is large enough, then we also have that . Hence, to prove that Fermat’s equation admits no solutions , it would suffice to show that there are arbitrarily large primes such that must divide one of . What Schur proved is that this is not possible and, indeed, for any and all sufficiently large primes , there are nontrivial solutions to Fermat’s equation modulo . To see this, let and let be the subgroup of consisting of -th powers. Then is union of cosets of , say where the displayed sets are disjoint. Note that . Now color using colors, by letting have color iff . By choice of , we have a monochromatic Schur triple, that is, there are such that and for some . But then there are , all nonzero modulo , such that , , and , so is a nontrivial solution to Fermat’s equation modulo .

It is actually an interesting problem to try and determine the optimal size of as a function of . Fourier-analytic methods give here the best known bounds. Cornacchia proved in 1909 that , at least if itself is prime.

Let me close with an open problem: We could consider a multiplicative (rather than additive) version of Schur’s theorem: For any there is an such that if is colored using colors, then there is a monochromatic set with . Indeed, this follows as a simple corollary of Schur’s result: Just note that , since we could just color the powers of two and apply the additive version. what if we combine the two? It is still open whether in any finite coloring of there are integers such that all receive the same color. This was originally asked by Hindman.

Advertisement