Schur's theorem

From Wikipedia, the free encyclopedia

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, Schur's theorem states that for any partition of the positive integers into a finite number of parts, one of the parts contains three integers x, y, z with

x + y = z.

Moreover, for every positive integer c, there exists a number S(c), called Schur's number, such that for every partition of the integers

{1, ..., S(c)}

into c parts, one of the parts contains integers x, y, and z with

x + y = z.

In combinatorics, Schur's theorem tells the number of ways for expressing a given number as a linear combination of a fixed set of relatively prime numbers. In particular, if $\{a_1,\ldots,a_n\}$ is a set of integers such that $gcd(a_1,\ldots,a_n)=1$ , the number of different tuples of non-negative integer numbers $(c_1,\ldots,c_n)$ such that $x=c_1a_1 + \cdots + c_na_n$ when $x$ goes to infinity is:

$\frac{x^{n-1}}{(n-1)!a_1\ldots a_n}$

As a result, for every set of relatively prime numbers $\{a_1,\ldots,a_n\}$ there exists a value of $x$ such that every larger number is representable as a linear combination of $\{a_1,\ldots,a_n\}$ in at least one way. This consequence of the theorem can be recast in a familiar context considering the problem of changing an amount using a set of coins. If the denominations of the coins are relatively prime numbers (such as 2 and 5) then any sufficiently large amount can be changed using only these coins.

In differential geometry, Schur's theorem compares the distance between the endpoints of a space curve $C *$ to the distance between the endpoints of a corresponding plane curve $C$ of less curvature.

Suppose $C (s)$ is a plane curve with curvature $κ(s)$ which makes a convex curve when closed by the chord connecting its endpoints, and $C * (s)$ is a curve of the same length with curvature $κ * (s)$ . Let $d$ denote the distance between the endpoints of $C$ and $d *$ denote the distance between the endpoints of $C *$ . If $\kappa^*(s) \leq \kappa(s)$ then $d^* \geq d$ .

Schur's theorem is usually stated for $C 2$ curves, but Sullivan has observed that Schur's theorem applies to curves of finite total curvature (the statement is slightly different).

[edit] References

Herbert S. Wilf (1994). generatingfunctionology. Academic Press.
Daniel Panario (2005). Integer Partition and The Money Changing Problem.
Dany Breslauer and Devdatt P. Dubhashi (1995). Combinatorics for Computer Scientists
Shiing-Shen Chern (1967). Curves and Surfaces in Euclidean Space. In Studies in Global Geometry and Analysis. Prentice-Hall.
John M. Sullivan (2006). Curves of Finite Total Curvature. arXiv.