A Generalization of Schur’s Theorem

Jon Henry Sanders

arXiv:1712.03620v1 [math.CO] 11 Dec 2017

JHS Consulting jon sanders@partech.com

1
Chapter 1

1.1 A GENERALIZATION OF SCHUR’S THEOREM

In 1916 Schur [1] proved the following theorem:

Theorem 1. Given a number1 there exists a number J(t) such that if the
set {1, . . . , J(t)} is divided into t classes A1 , . . . , At then there exists numbers
a, b and a number ℓ, 1 ≤ ℓ ≤ t, such that a, b, a + b ∈ Aℓ . We prove the
following generalization:
Theorem 2. Let P (t, n) be the statement, “Given numbers t, n there
exists a number J(t, n) such that if the set S = {1, . . . , J(t, n)} is divided
into t classes A1 , . . . , At there exists a sequence of (not necessarily distinct)
P
numbers a1 , . . . , an and a number ℓ, 1 ≤ ℓ ≤ t, such that i∈I a1 ∈ Aℓ for
all I ⊆ {1, . . . , n}.” Then P (t, n) is true for all numbers t, n.
We first prove the following corollary:
Corollary 1.1. The ai may be assumed distinct in the above theorem.
Proof. Let J ′ (t, n) = J(t, n4 ). We show if the set S = {1, . . . , J ′ (t, n)}
is divided into t classes there are n distinct numbers in S with the desired
property. For let a1 , . . . , an4 be a sequence of n4 not necessarily distinct
1
The word “number” will mean “positive integer” throughout this section.

2
numbers of S with the desired property. Then either there are at least n2
distinct numbers among them or there is a number k such that a1 = k for
at least n2 distinct numbers among them or there is a number k such that
ai = k for at least n2 distinct values of i. In the first case we are through. In
X
the second define bi = ik, i = 1, . . . , n. Then bi , I ⊆ {1, . . . , n} is equal
X i∈I
to ℓk, 1 ≤ ℓ ≤ n(n−1)
2
≤ n2
= ai , I ′ ⊆ {1, . . . , n4 } where I ′ is a set of ℓ
i∈I
(distinct) indices which satisfy i ∈ I ′ implies ai = k. Thus the b1 have the
desired property since the a1 do and furthermore they are distinct.
We need to make one remark before proceeding. Let P (t, n, k) be the
statement derived from P (t, n) by substituting the set S ′ = {k, 2k, . . . , J(t, n)k}
for the set S = {1, 2, . . . , J(t, n)}.
Remark. For any given number k, P (t, n) implies2 P (t, n, k).
Proof. Let A1 , . . . , At be a division of S ′ into t sets. Divide S into t sets
by the rule for all a ∈ S, a ∈ A′j iff ka ∈ Aj . If P (t, n) is true there exists a
X
sequence b1 , . . . , bn such that b1 ∈ A′ℓ for some fixed ℓ, 1 ≤ ℓ ≤ t, for all
i∈I
I ⊆ {1, . . . , n}. But then the sequence ai = bi k, i = 1, . . . , n and the number
ℓ, 1 ≤ ℓ ≤ t, have the desired property for S ′ so P (t, n, k) is true.
We now prove an “Iterated Ramsey Theorem” needed for the proof of
Theorem 2. Let R(k, r, t) be Ramsey’s function, i.e., let R(k, r, t) be the
smallest number such that when the r−subsets of any set S of order R(k, r, t)
are divided into t classes A1 , . . . , At there always exists a k-subset K of S
and a number ℓ, 1 ≤ ℓ ≤ t such that all the r-subsets of K are contained in
Aℓ . We prove
2
Actually, P (t, n) and P (t, n, k) are equivalent.

3
Lemma 1. Given numbers k, r, t, k ≥ r there exists a number N(k, r, t)
such that if all the non-empty subsets of a set S of order n ≥ N(k, r, t) are
divided into t classes A1 , . . . , At then there exists a k−subset K ⊆ S and a
sequence Ai1 , . . . , Air , 1 ≤ ij ≤ t, j = 1, . . . , r, such that all the j-subsets
of K are contained in Aij for j = 1, . . . , r.
Proof. The proof is by induction on r. If r = 1 we take N(k, l, t) >
kt. Suppose the theorem is true for r = ro −1 and arbitrary k, t. We wish
to prove it true for r = ro and arbitrary values of k, t, say ko , to . Take
N(ko , ro , to ) = N(R(ko , ro −1, to ), ro , to ). If the order of S is larger than
N(ko , ro , to ) then by the induction hypothesis there exists a subset K ′ of S of
order R(ko , ro , to ) and a sequence i1 , . . . , iro −1 such that each j-subset of K ′
is contained in Aij , j = 1, . . . , ro −1. But by Ramsey’s Theorem there exists a
ko −subset K ′′ of K ′ such that all the ro −subsets of K ′ are in some A′ . Then
K ′′ is the desired subset of S and Ai1 , . . . , Airo −1 , A′ is the required sequence
of classes.
We are now ready to prove Theorem 2.
Proof. The proof is by induction on n. Let P ′ (n) be the statement “P (t, n) is
true for all possible values of t.” Then P ′ (2) is Theorem 1. Assume P ′ (no −1)
is true. We prove P ′(no ) is true. Take

J(no , t) = N(4J(no −1, t), 4J(no −1, t), t).

Let the set S = {1, . . . , J(no , t)} be divided into t classes A1 , . . . , At . If

B = {a1 , a2 , . . . , ak } is any subset of S, a1 < a2 < · · · < ak define f (B) by
Xk Xk
j
f (B) = (−1) aj if k is even and by f (B) = (−1)j+1 aj if k is odd.
j=1 j=1
Divide all the non-empty subsets of S into t classes A′1 , . . . , A′t by the rule

4
B ∈ A′i iff f (B) ∈ Ai . (Note that this is well defined since f (B) ∈ S if θ 6=
B ⊆ S). By Lemma 13 , there exists a subset K of S of order 4J(n−1
o , t) := N

and a sequence of classes A′j1 , . . . , A′jN such that all the i-subsets of K are con-
tained in A′ji , i = 1, · · · , N. Now divide the set S ′ = {4, 8, . . . , 4J(no −1, t)}
into t classes A′′1 , ..., A′′t by the rule for all a ∈ S ′ , a ∈ A′′j iff all the a−subsets
of K are contained in A′j . Then by the induction hypothesis and the preced-
ing remark we can find a sequence a1 , . . . , ano −1 , say a1 ≤ a2 ≤ · · · ≤ ano −1 ,
X
and a number ℓ, 1 ≤ ℓ ≤ t, such that ai ∈ A′′ℓ for all I ⊆ {1, . . . , no −1}.
X i∈I
4
Since ai ≤ order of K we may choose a strictly increasing sequence
i=I
o −1
nX
b1 , b2 , . . . , bθno −1 of elements of K, where θno −1 = ai . In general define
i=1
i
X
θi = aj , i = 1, . . . , no −1 and define some subsets of K as follows (see Fig.
j=1
1).

B1 = {b1 , . . . , ba1 },

Bi = {bθi−1 +1 , . . . , bθi }, i = 2, . . . , no −1,

n o
P1 = b a21 −1 , . . . , ba1 −1 ,
n o
P2 = ba1 +2 , . . . , b 3a1 +2 ,
2

and Bno = P1 ∪ P2 .
3
with k = r = N.
nX
o −1 nX
o −1
4
Since ai ∈ A′′ℓ ⊆ S ′ , a1 ≤ max S ′ = 4J(no −1, t) = order of K.
i−1 i=1

5
 B B B
z }|1 { z }|2 { z }|3 {
b1 , . . . , b a1 −1 , . . . , ba1 −1 , ba1 , ba1 +1 , ba1 +2 , . . . , b 3a1 +2 , . . . , ba1 +a2 , ba1 +a2 +1 , . . .
2
| {z } | {z 2 }
P1 P2

Figure 1.
We claim that f (Bi ), i = 1, . . . , no and Aℓ are the required numbers and class,
i.e.,
X
f (Bi ) ∈ Aℓ , I ⊆ {1, . . . , no }. T
i∈I

We first state two facts about the function f .

F1 f (A ∪ B) = f (A) + f (B) if A and B are of even order and A < B 5 .

F2 f (A) = f (A − P ) − f (P ) when P is a consecutive6 subset of A of even

order such that all the elements of A larger than the largest element of
P are odd in number.

We first show T assuming either no ∈ / I or no ∈ I but 1, 2 ∈ / I. By F1 we

X [ [ X
have f (Bi ) = f ( Bi ). But Bi is of order ai if no ∈
/ I and of order
X i∈I i∈I i∈I i∈I
ai + a1 if no ∈ I, 1, 2 ∈
/ I since the Bi are disjoint in either case and
i∈I−{no }
[
|Bno | = a1 and |Bi | = ai , i = 1, . . . , no −1. Thus in either case Bi ∈ A′ℓ
[ X [ i∈I
′′
(since | Bi | ∈ Aℓ ) so f (Bi ) = f ( Bi ) ⊆ Aℓ . Next we consider the case
i∈I i∈I i∈I S
/ I. We claim f (Bno ) + f (B1 ) = f ((B1 − P1 ) P2 ). [ This follows
no , 1 ∈ I, 2 ∈
5
A < B denotes here that the largest element of A is less than the smallest element of
B.
6
By a consecutive subset we mean that a ∈ A, x < a < y, x, y ∈ P implies a ∈ P.

6
 a1
S
from the fact that 2
is even so f (Bno ) = f (P1 P2 ) = f (P1 ) + f (P2 ) (by F1
a1
since |P1 | = |P2 | = 2
and P1 < P2 ). Then by F2 , f (B1 ) + f (P1) = f (B1 −P1 )
S S
and by F1 , f (B1 − P1 ) + f (P2 ) = f ((B1 − P1 ) P2 ).] But (B1 − P1 ) P2 is
S
of order a1 and (B1 − P1 ) P2 < Bi , i = 3, . . . , no −1,
P P
so by F1 , i∈I f (Bi ) = f (Bn0 ) + f (B1 ) + i∈I−{n0 ,1} f (Bi ) = f ((B1 −
P S
P1 ) ∪ P2 ) + i∈I−{no ,1} f (Bi ) = f ((B1 − P1 ) ∪ P2 i∈I−{no ,1} Bi . But (B1 −
S S P S
P1 ) P2 ∪ i∈I−{no ,1} Bi is of order i∈I−{no } ai . Thus ((B1 − P1 ) P2 ) ∪
S P S
i∈I−{no ,1} Bi ∈ Aℓ , so i∈I f (Bi ) = f ( i=1−{1,no } Bi ∪ (B1 − P1 ) ∪ P2 ) ∈ Aℓ .

Similar arguments hold in the cases no , 2 ∈ I, 1 ∈

/ I and no , 2, 1 ∈ I
noting f (Bno ) + f (B2 ) = f ((B2 − P2 ) ∪ B1 ) and f (Bno ) + f (B2 ) + f (B1 ) =
f ((B1 ∪ B2 ) − Bno ).

1.2 FURTHER GENERALIZATIONS

It is natural to ask whether either Lemma 1 or Theorem 2 generalize in

the following way:
Lemma 1′ . Let all the non-empty finite subsets of a countably infinite set
S be divided into t classes A1 , . . . , At . Then there exists a countably infinite
subset K ⊆ S and an infinite sequence i1 , i2 , . . . , i ≤ ij ≤ t, i = 1, 2, . . . ,
such that all the j−subsets of K are contained in Aij , j = 1, 2, . . . .
Theorem 2′ . Let the natural numbers be divided into t classes A1 , . . . , At .
Then there exists an infinite sequence a1 , a2 , . . . , and a number ℓ, 1 ≤ ℓ ≤ t,
X
such that ai ∈ Aℓ , for all (non-empty) finite sets I of natural numbers.
i∈I
A counter example to Lemma 1′ is as follows. Divide all the finite (non-
empty) subsets S of the natural numbers N into two classes A1 and A2 by

7
the rule:

S ∈ A1 iff |S| ∈ S,

S ∈ A2 iff |S| ∈
/ S.

Then K contains k−subsets which contain k and k−subsets which do not,

i.e., subsets which belong to A1 and ones which belong to A2 .
We note that if Theorem 2′ were true then using an argument similar to
that of Corollary 1.1 we could assume the a1 are distinct, however, at present
the validity of Theorem 2′ is not known.

BIBLIOGRAPHY
1. 1. I. Schur, Uber die Kongruenz xm + y m = z m (mod p), Jahresbericht
der Deut. Mathematiker-Vereiningung, Band 25 (1916) pp. 114-117.