Page 48 -

IV. Sequences without Arithmetic Progressions
42
fàn ;Pð . So, for example, for the trivial property, fàn ;P 0 ) n, and
for P A , fà 3;P A ) 2, fà 5;P A ) 4.
It follows easily from conditions 1 and 2 that this f (n) is sub-
additive, i.e., fàm + n) ≤ f (m) + f (n). If we recall the fact
f (n)
that subadditive functions enjoy the property that lim n→∞ ex-
n
f (n) f (n)
ists (in fact lim n→∞ inf ), we are led to define C P
n n
fàn ;Pð
lim n→∞ . This number is a measure of how permissive the
n
1, because P 0 is totally permissive. The
property P is. Thus C P 0
announced result about progression = free sequences amounts to the
0, so that P A is, in this sense, totally unper-
statement that C P A
missive. At any rate, we always have 0 ≤ C P ≤ 1, and we may dub
C P the permission constant.
The remarkable result proved by Szemer´ edi and then later by
Furstenberg is that, except for P 0 , C P is always 0. Their proofs are
both rather complicated, and we shall content ourselves with the case
of P A , which was proved by Roth.

The Basic Approximation Lemma

It turns out that the extremal sets S(n;Pð all behave very much as
though their elements were chosen at random. For example, we note
that such a set must contain roughly the same number of evens
as odds. Indeed if 2b 1 , 2b 2 ,..., 2b k were its even elements, then
n
b 1 ,b 2 ,...,b k would be a subset of 0, and so we could conclude
2

n
that k ≤ f . Similarly the population of the odd elements of
2
S would satisfy this same inequality. Since n ∼ 1 f (n), we con-
2 2
clude that both the evens and the odds contain not much more than
half the whole set. Thereby the evens and the odds must be roughly
equinumerous. (Thus, two upper bounds imply the lower bounds.)
Delaying for the moment the precise statement of this “random-
ness,” let us just note how it will prove useful to us with regard to
our arithmetic progression considerations. The point is simply that,
if integers were chosen truly at random with a probability C> 0,
there would automatically be a huge number of arithmetic progres-