Schur's theorem

In discrete mathematics , Schur's theorem provides statements as to how large a set of numbers must be so that a single-colored solution always exists for any - coloring of these . This sentence was originally an auxiliary sentence in a publication by Issai Schur in 1916. Schur was not at all interested in examining the coloring of points in the plane, but rather Fermat's last theorem (which only became a theorem after a proof in 1995). Although found twelve years before Ramsey , it is considered the first sentence of the Ramsey theory . ${\displaystyle [1,s(r)]}$ ${\displaystyle r}$

Formulation of the sentence

background

In the sentence coloring problems of the plane are considered. Let be a simple plane and the set of all points on the plane with positive integer coordinates. For example and , this time and not necessarily having to be different. Now a finite set of colors is chosen and a color is assigned to each natural number. ${\displaystyle z=x+y}$ ${\displaystyle {\mathcal {P}}}$ ${\displaystyle (1,1,2)}$ ${\displaystyle (3,4,7)}$ ${\displaystyle x}$ ${\displaystyle y}$

After that, all points are colored with the corresponding color exactly when the coloring of and on the number line is identical. All points not taken into account in this way are marked with a . The question remains whether the existence of a colored point is certain or whether it is possible to mark every point on the plane with one . In other words, whether there is a coloring for such that no point is colored. Schur's theorem answers this question. ${\displaystyle (x,y,z)\in {\mathcal {P}}}$ ${\displaystyle x,y}$ ${\displaystyle z}$ ${\displaystyle X}$ ${\displaystyle X}$ ${\displaystyle \mathbb {N} ^{+}}$ ${\displaystyle (x,y,z)\in {\mathcal {P}}}$

sentence

For each there is a smallest one , so that for each coloration from to there is a monochrome solution . ${\displaystyle r\geq 1}$ ${\displaystyle s(r)\in \mathbb {N} ^{+}}$ ${\displaystyle r}$ ${\displaystyle [1,s(r)]}$ ${\displaystyle x+y=z}$

proof

Be it . The set of Ramsey ensures the existence of the number , for any staining of the complete graph with nodes , the existence of a single-color triangle. We choose our coloring as follows. The nodes of are numbered with and the set is broken down into disjoint subsets. These quantities should correspond to the colors. Now the edge that connects the nodes and is colored with the color of the set to which it belongs. According to Ramsey's theorem, there is a monochrome triangle in the graph and its corners are . Then follows there and are monochrome. With and then applies . The theorem is proved. ${\displaystyle r\geq 1}$ ${\displaystyle n=R(3;r)}$ ${\displaystyle r}$ ${\displaystyle K_{n}}$ ${\displaystyle n}$ ${\displaystyle K_{n}}$ ${\displaystyle 1\ldots n}$ ${\displaystyle \{1,\ldots ,n-1\}}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle i}$ ${\displaystyle j}$ ${\displaystyle |j-i|}$ ${\displaystyle a<b<c}$ ${\displaystyle b-a,c-b}$ ${\displaystyle c-a}$ ${\displaystyle x=b-a,y=c-b}$ ${\displaystyle z=c-a}$ ${\displaystyle x+y=z}$

generalization

In addition to Rado's theorem , a generalization can be achieved if the equation is considered instead of the equation . ${\displaystyle x+y=z}$ ${\displaystyle {\mathcal {L}}(t):x_{1}+\ldots +x_{t-1}=x_{t}}$

Be and each was . Then there exists a smallest number such that every -Color of at least one exists that a solution of the color exists. ${\displaystyle r\geq 1}$ ${\displaystyle 1\leq i\leq r}$ ${\displaystyle k_{i}\geq 3}$ ${\displaystyle S(k_{1},\ldots ,k_{r})\in \mathbb {N} ^{+}}$ ${\displaystyle r}$ ${\displaystyle [1,S(r)]}$ ${\displaystyle j\in \{1,\ldots ,r\}}$ ${\displaystyle {\mathcal {L}}(k_{j})}$ ${\displaystyle j}$

Another generalization examines the equation . The smallest number , such that any 2-coloration of allows a single-colored Pythagorean triple , is . ${\displaystyle x^{2}+y^{2}=z^{2}}$ ${\displaystyle N}$ ${\displaystyle [1,N]}$ ${\displaystyle N=7825}$

specialization

For the original and for the generalized case, it can be examined in each case whether the existence of these numbers is present, if it is additionally required that initially and in the generalized case is for . In this area in particular, only a few upper and lower bounds have been investigated so far. ${\displaystyle x\not =y}$ ${\displaystyle x_{i}\not =x_{j}}$ ${\displaystyle i\not =j}$

Others

• The numbers are called Schur numbers . ${\displaystyle s(r)}$
• The numbers are called general Schur numbers . ${\displaystyle S(r)}$
• The triples that satisfy the above sentence are called Schur triples . ${\displaystyle \{x,y,z\}}$
• The -tuples of the generalization are called Schur-t-tuples . ${\displaystyle t}$ ${\displaystyle \{x_{1},\ldots ,x_{t}\}}$
• The set of Rado is a generalization of Schur's theorem.

While the research focus of Schur's numbers relates to the determination of bounds , the number of tuples is of interest , i.e. how many of the tuples exist for. ${\displaystyle n\geq s(r),S(r)}$

Individual evidence

1. ^ Issai Schur: About the congruence ${\displaystyle x^{m}+y^{m}\equiv z^{m}\ \left(\operatorname {mod} \ p\right).}$ In: Annual report of the DMV. Vol. 25. Teubner, Stuttgart 1917, pp. 114-117.
2. ↑ Bruce M Landman, Aaron Robertson: Ramsey Theory on the Integers. AMS, Rhode Island 2004, pp. 199-200.
3. ^ Heule, Kullmann, Marek: Solving and Verifying the boolean Pythagorean Triples problem via Cube-and-Conquer
4. ↑ Nature News: Two-hundred-terabyte maths proof is largest ever

literature

• Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory . 2nd Edition. Wiley, New York NY 1990, ISBN 0-471-50046-1 .
• Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers . 1st edition. AMS, Rhode Island 2004, ISBN 0-8218-3199-2 .