From: hsbrand@cs.vu.nl (HS Brandsma)
Newsgroups: sci.math
Subject: Re: Question: Ramsey Theory and Arithmetic progressions in subsets of N
Date: 20 Oct 1997 10:54:53 GMT

Asger Grunnet (asger@diku.dk) wrote:
: I was working on a problem in number theory recently, when the
: following problem suddenly materialized on the paper before me :
: 
: Given any subset M of the natural numbers N and any number n in N.
: Is it possible to find numbers a and b, such that the
: arithmetic progression {a, a+b, a+2b, ... , a+nb} is either
: contained in M or contained in N\M ?
: 
: The problem can be rephrased by considering sequences of 0 and 1 :
: 
: Given any sequence (A_i) with A_i in {0,1}, i=1,2,..., and any number n, 
: is it possible to find a,b such that A_a = A_{a+b} = ... = A_{a+nb} ?
: 
: With this perspective one can consider the stronger problem :
: 
: Given a number n, is it possible to find a number m, such that any
: sequence A_1, A_2, ... , A_m in {0,1} contains a progression
: A_a = A_{a+b} = ... = A_{a+nb} ?
: 
: This smells distinctively like Ramsey Theory, but after thinking
: about it for quite some time, I still haven't succeded in finding
: a way to make use of Ramsey's Theorem.
: 
: Of course one can set a higher goal and try to prove (or disprove) this
: for sequences of {1,2,...,k} instead of just {0,1}.
: 
: I seem to remember a conjecture by Erdos saying something like :
: If M is a subset of N with SUM(k in M, 1/k) = infinity, then
: M contains arbitrarily long arithmetic progressions. This would
: of course prove my original problem.
: Has this conjecture been resolved yet?
: 
: Any responce will be greatly appreciated, as I have been wasting
: a lot of time lately, pacing and thinking about arithmetic progressions!
: 
: Asger Grunnet,  asger@diku.dk / grunnet@math.ku.dk.


You could use Van der Waerden's theorem:

Let N be a union of finitely many sets A_i.
Then there is an i such that A_i contains arbitrarily long arithmetic
progressions. 
(you need the case N=A \cup N\A).

reference: Van der Waerden 
Beweis einer Baudetschen Vermutung.
Nieuw Archief voor Wiskunde, 19, 212-216 (1927)

I know the theorem from a topology course where this is proved using
the Cech-Stone compactification of N (as a semigroup)

Henno Brandsma

==============================================================================
From: hsbrand@cs.vu.nl (HS Brandsma)
Newsgroups: sci.math
Subject: Re: Question: Ramsey Theory and Arithmetic progressions in subsets of N
Date: 22 Oct 1997 12:19:13 GMT

jhnieto@luz.ve wrote:
: In article <62fd9t$8pa$1@star.cs.vu.nl>,
:   hsbrand@cs.vu.nl (HS Brandsma) wrote:
: [snip]
: > ... Van der Waerden's theorem:
: >
: > Let N be a union of finitely many sets A_i.
: > Then there is an i such that A_i contains arbitrarily long arithmetic
: > progressions.
: [snip]
: > I know the theorem from a topology course where this is proved using
: > the Cech-Stone compactification of N (as a semigroup)
: 
: This seems very interesting to me. Could you give a sketch of
: the proof, or at least some references?
: 
: Sincerely,
:                  José H. Nieto
: 
: -------------------==== Posted via Deja News ====-----------------------
:       http://www.dejanews.com/     Search, Read, Post to Usenet

I've heard of one other proof yesterday, also using this idea, from
our topological dynamics guy. He said you can use the existence of
multiple recurring points in some compact space.
The proof I know goes roughly as follows:

First note that \beta N is a half-topological semigroup: it has an
operation *, which extends the addition on N, which is associative,
and such that for fixed x, left multiplication by x is a continuous
map from \beta N to \beta N. * is not associative, nor continuous in
two variables. 
Let X be a compact half-topological semigroup.
An idempotent is an element x s.t. x*x=x.
We define an partial ordering on the idempotent elements of X by x <=
y iff x = x*y = y*x.
We need a minimal (in this ordering) idempotent, and such can be found
using compactness.

Such a point is an ultrafilter on N, and if a finite union of sets is
in the ultrafilter, the ultrafilter contains at least one of those
sets. On then shows that does what you want: it yields arithmetic
progressions in this set in a natural way.

I only have a copy of this proof in Dutch, and I have no further
references. 

Henno Brandsma