Summer Kisner – Schur’s theorem

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

2013--5-18 Summer

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 \mathbb Z^+ are partitioned into finitely many sets, \mathbb Z^+=A_1\cup\dots\cup A_n, then for some i, 1\le i\le n, there are integers x,y,z (not necessarily different), all of them in A_i, such that x+y=z. One usually describes this in terms of colors: We color the positive integers with finitely many colors, and there is a monochromatic triple x,y,z with x+y=z.

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 {}[X]^k denote the collection of k-sized subsets of the set X. Suppose that X is infinite, and consider a coloring c:[X]^k\to C, where the set C of colors is finite. Ramsey’s theorem asserts that under these assumptions, there is an infinite subset H of X that is homogeneous or monochromatic for c, in the sense that c assigns the same color to all k-sized subsets of H. In fact, we have finitary versions of this result: For any n and any l=|C|, if we only require that H has size at least n, then there is an m such that it suffices to assume that X has size at least m. Even for k=l=2, the study of Ramsey numbers, the least m seen as a function of n, proves to be incredibly difficult and computationally unfeasible. For example, if n=5, then we know that 43\le m\le 49, but its exact value is not known.

To deduce Schur’s theorem from Ramsey’s, let r be such that, for any for coloring of {}[\{1,\dots,r\}]^2 using n colors, there is a monochromatic set of size 3. The least such r we denote R_n(3). We want to show that if \mathbb Z^+=A_1\cup\dots\cup A_n, then there is a monochromatic solution to the equation x+y=z. In fact, we claim that it suffices to consider \{1,\dots,r-1\} rather than the whole set of positive integers. Indeed, given a partition \{1,\dots,r-1\}=A_1\cup\dots\cup A_n, consider the coloring of {}[\{1,\dots,r\}]^2 where if a<b, then the set $\{a,b\}$ has color i, where b-a\in A_i. By definition of r, we can find a<b<c such that \{a,b\},\{a,c\},\{b,c\} all have the same color. Now notice that c-a=(c-b)+(b-a), that is, b-a,c-b,c-a are monochromatic for the original coloring of \{1,\dots,r-1\}.

An easy inductive argument gives us that R_n(3)\le 3\cdot n!, so this gives the upper bound 3\cdot n!-1 for the so-called n-th Schur number s(n). To see the upper bound R_n(3)\le 3\cdot r!, note that R_1(3)=3, and verify inductively that R_{n+1}(3)\le (n+1)R_n(3): Suppose that |X|\ge (n+1)R_n(3), and consider a coloring of [X]^2 with n+1. Fix an element a\in X, and note that for some color i there are R_n(3) elements b\in X such that \{a,b\} has color i. Let Y be the set of all these b, that is, Y=\{b\in X\mid\{a,b\} has color i\}. Note that if for some b,c\in Y we have that \{b,c\} has color i as well, then \{a,b,c\} is monochromatic with color i. Hence we may assume that the coloring, restricted to {}[Y]^2, only uses n colors. We are now done, since |Y|\ge R_n(3).

Schur’s original proof predated Ramsey, and gives a slightly better bound than s(n)\le 3\cdot n!. Indeed, from his proof, we obtain that s(n)\le \lceil n!e\rceil.

In terms of lower bounds, one can quickly check by induction that s(n)\ge (3^n+1)/2. Indeed, s(1)=2=(3^1+1)/2, since 1+1=2. Given a coloring c of \{1,\dots,k\} using colors \{1,\dots,n\} and without monochromatic triples, we describe a coloring c' of \{1,\dots,3k+1\} using colors \{1,\dots,n+1\}, again without monochromatic triples. This gives the result. To define c', start by letting c'(i)=c(i) for i\le k. Now let c'(j)=n+1 for k+1\le j\le 2k+1, and finally let c'(j)=c(j-(2k+1)) for 2k+2\le j\le 3k+1.

Slightly better bounds are known. For example, Anne Penfold Street shows that s(n)\ge (89\cdot 3^{n-4}+1)/2 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 x, y, z are integers, and x^n+y^n=z^n. Then, for any prime p, the equality holds modulo p and, if p is large enough, then we also have that p\not\mid xyz. Hence, to prove that Fermat’s equation admits no solutions (x,y,z), it would suffice to show that there are arbitrarily large primes p such that p must divide one of x,y,z. What Schur proved is that this is not possible and, indeed, for any n and all sufficiently large primes p, there are nontrivial solutions to Fermat’s equation modulo p. To see this, let p>s(n) and let G be the subgroup of (\mathbb Z/p\mathbb Z)^* consisting of n-th powers. Then (\mathbb Z/p\mathbb Z)^* is union of cosets of G, say (\mathbb Z/p\mathbb Z)^*=\bigcup_{i=1}^k a_iG where the k displayed sets are disjoint. Note that k=n/\mathrm{gcd}(n,p-1)\le n. Now color (\mathbb Z/p\mathbb Z)^* using k colors, by letting t have color i iff t\in a_iG. By choice of p, we have a monochromatic Schur triple, that is, there are \alpha,\beta,\gamma\in (\mathbb Z/p\mathbb Z)^* such that \alpha+\beta=\gamma and \alpha,\beta,\gamma\in a_iG for some i. But then there are x,y,z, all nonzero modulo p, such that \alpha=a_i x^n, \beta=a_i y^n, and \gamma=a_i z^n, so (x,y,z) is a nontrivial solution to Fermat’s equation modulo p.

It is actually an interesting problem to try and determine the optimal size \mathcal N of p as a function of n. Fourier-analytic methods give here the best known bounds. Cornacchia proved in 1909 that \mathcal N(n)\le (n-1)^2(n-2)^2+6n-2, at least if n 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 n there is an s'(n) such that if \{1,2,\dots,s'(n)\} is colored using n colors, then there is a monochromatic set \{x,y,z\} with xy=z. Indeed, this follows as a simple corollary of Schur’s result: Just note that s'(n)\le 2^{s(n)}, 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 \mathbb Z^+ there are integers x,y such that x,y,x+y,xy all receive the same color. This was originally asked by Hindman.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: