From: dsavitt@math.harvard.edu (David Savitt) Subject: Re: About Arithmetic Progressions Date: 12 Feb 2001 01:35:43 GMT Newsgroups: sci.math.research Summary: Sets of integers of positive density contain long arithmetic progressions freedom641@my-deja.com writes: >Let P be any finite partition of the set of all natural numbers and >let k be any fixed natural number. Is the following true: > At least one of the members of P contains an arithmetic > progression of length greater than k. Yes, this is true. There's a celebrated theorem of Szemeredi ("On sets of integers containing no k elements in arithemetic progression", Acta Arith. 27 (1975), 199--245) that if S is any subset of natural numbers having positive density, then S contains arbitrarily long finite arithmetic progressions. Several proofs of this theorem are now known, but none are remotely easy. Since at least one of the (finite number of) sets in your partition must have positive density, by Szemeredi's theorem it has your arithmetic progression. I haven't thought about whether it's absolutely necessary to hit your problem with such a big hammer. (e.g., as a first step, can one see in an elementary and clever way that if a subset of the natural numbers contains no arithmetic progression of length k, then its complement must?) Dave ============================================================================== From: George Russell Subject: Re: About Arithmetic Progressions Date: Mon, 12 Feb 2001 18:30:50 +0100 Newsgroups: sci.math.research David Savitt wrote: [snip] > I haven't thought about whether it's absolutely necessary to hit your > problem with such a big hammer. (e.g., as a first step, can one see in an > elementary and clever way that if a subset of the natural numbers contains > no arithmetic progression of length k, then its complement must?) [snip] I must be rather stupid, because I can't see this. Can you e-mail it to me? Call it Savitt's Assertion. Then by a standard looking Ramsey-Theory argument, we can prove the general case. Claim: for n>=2 colours, k>=1 there exists R(n,k) such that any n-colouring of 1..R(n,k) contains a monochromatic arithmetic progression of length k. First we prove that R(n,2) exists. By Savitt's Assertion, an infinite 2-colouring of 1.. must contain a monochromatic arithmetic progression of length k. Suppose we can't find an R(n,2), then the set S of sequences of colourings of 1..N (for some N) containing no monochromatic subsequence contains sequences of arbitrarily large length. Now we invoke the Infinite Lemma, in this form: for any colouring s of 1...N, define S/s to be the set of all colourings beginning with s. Then we can construct an infinite colouring by starting with the empty colouring, and repeatedly extending S such that S/s always contains sequences of arbitrarily large length. Now we prove that R(n,k) always exists, by induction on n. We've just done n=2. Suppose it's true for n=N, we prove n=N+1. We claim R(N+1,k)=R(2,max(k,R(N,k))) For given an N+1-colouring of 1..R(2,max(k,R(N,k))), colour these numbers black if colour number 1 is used, or white if some other colour is used. Then we can find a monochrome arithmetic sequence of length max(k,R(N,k)). If it's black we have a monochromatic k sequence with the original colours. If it's white, we have have an arithmetic sequence of length R(N,k) coloured with just N of the original colours, hence it contains an arithmetic subsequence of length k, and we are also done. [reformatted --djr] ============================================================================== From: cd@newsun-graphe.lri.fr (Charles Delorme) Subject: Re: About Arithmetic Progressions Date: 12 Feb 2001 08:36:24 GMT Newsgroups: sci.math.research In article <966trr$i9r$1@nnrp1.deja.com>, freedom641@my-deja.com writes: |> Let P be any finite partition of the set of all natural numbers and |> let k be any fixed natural number. Is the following true: |> At least one of the members of P contains an arithmetic |> progression of length greater than k. |> Thanks in Advance. |> |> |> Sent via Deja.com |> http://www.deja.com/ |> Yes, it is true. Indeed van der Waerden'theorems tells us that if you take an interval of N of length f(n,k) and partition it into n parts, one of the parts contains an arithmetic progression of length >= k. But the growth of f is very fast, and few of its values are known. Details and proofs in the book: Ramsey theory, by R. L. Graham, B. L. Rotschild and J. H. Spencer. John Wiley & Sons 1980 -- Charles Delorme tous les mégalomanes LRI ont une signature cd@lri.fr à étages ============================================================================== From: Fred Galvin Subject: Re: About Arithmetic Progressions Date: Mon, 12 Feb 2001 15:06:32 -0600 Newsgroups: sci.math.research On 12 Feb 2001, David Savitt wrote: > freedom641@my-deja.com writes: > > >Let P be any finite partition of the set of all natural numbers and > >let k be any fixed natural number. Is the following true: > > At least one of the members of P contains an arithmetic > > progression of length greater than k. > > Yes, this is true. There's a celebrated theorem of Szemeredi ("On > sets of integers containing no k elements in arithemetic > progression", Acta Arith. 27 (1975), 199--245) that if S is any > subset of natural numbers having positive density, then S contains > arbitrarily long finite arithmetic progressions. Several proofs > of this theorem are now known, but none are remotely easy. > > Since at least one of the (finite number of) sets in your > partition must have positive density, by Szemeredi's theorem it > has your arithmetic progression. Actually, all you can be sure of is that one of the sets has positive *upper* density; they could all have lower density 0. That's OK, because Szemeredi's theorem only requires positive upper density. > I haven't thought about whether it's absolutely necessary to hit > your problem with such a big hammer. (e.g., as a first step, can > one see in an elementary and clever way that if a subset of the > natural numbers contains no arithmetic progression of length k, > then its complement must?) Yes. Szemeredi's theorem is a powerful generalization of Van der Waerden's theorem; however, as another poster (Charles Delorme) has pointed out, the original poster only wanted Van der Waerden's theorem. -- It takes steel balls to play pinball. ============================================================================== From: Fred Galvin Subject: Re: About Arithmetic Progressions Date: Mon, 12 Feb 2001 15:08:38 -0600 Newsgroups: sci.math.research On 12 Feb 2001, Charles Delorme wrote: > Yes, it is true. Indeed van der Waerden'theorems tells > us that if you take an interval of N of length f(n,k) > and partition it into n parts, one of the parts > contains an arithmetic progression of length >= k. > > But the growth of f is very fast, and few of its > values are known. > > Details and proofs in the book: Ramsey theory, > by R. L. Graham, B. L. Rotschild and J. H. Spencer. > John Wiley & Sons 1980 That's the first edition, which has Van der Waerden's original proof. The second edition (1990) gives Shelah's new proof, which is simpler and provides better bounds. -- It takes steel balls to play pinball. ============================================================================== From: "Thomas.B.Ward" Subject: Re: About Arithmetic Progressions Date: Wed, 14 Feb 2001 15:10:40 +0000 Newsgroups: sci.math.research On 12 Feb 2001, David Savitt wrote: > freedom641@my-deja.com writes: > > >Let P be any finite partition of the set of all natural numbers and > >let k be any fixed natural number. Is the following true: > > At least one of the members of P contains an arithmetic > > progression of length greater than k. > > Yes, this is true. There's a celebrated theorem of Szemeredi ("On sets of > integers containing no k elements in arithemetic progression", Acta > Arith. 27 (1975), 199--245) that if S is any subset of natural numbers > having positive density, then S contains arbitrarily long finite > arithmetic progressions. Several proofs of this theorem are now known, > but none are remotely easy. > > I haven't thought about whether it's absolutely necessary to hit your > problem with such a big hammer. (e.g., as a first step, can one see in an > elementary and clever way that if a subset of the natural numbers contains > no arithmetic progression of length k, then its complement must?) > > Dave > It's certainly not needed to use such a deep result, since the question starts from a finite partition. This makes it somehow topological not measure-theoretic, and one can prove it using multiple topological recurrence. Not easy, but a great deal more accessible than Szemeredi theorem. Nice expositions are in e.g. Furstenberg, Recurrence in ergodic theory and combinatorial number theory, Princeton Univ. Press. 1981. or Furstenberg & Weiss, J. D'Analyse Math. 34 (1978), 61-85. Tom Ward