Talk:Van der Waerden's theorem

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	Start Class	Mid Priority	Field: Discrete mathematics
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. Geometry guy 21:55, 17 June 2007 (UTC)

In the statement of the theorem, we use {1,...,N}, but in the proof we use {0,...,N-1}. Should we use the same convention throughout? AxelBoldt 03:59 Jan 13, 2003 (UTC)

I've incremented the numbers in the proof by 1 to make it consistent. Terry 17:58, 6 Sep 2004 (UTC)

You cannot just increment all the numbers in a proof with no understanding of what is going on; the "consistent" proof was completely wrong. For example, you had

That is, there are two integers b₁ and b₂, both in {1,...,33}, such that c(b₁·5 + k) = c(b₂·5 + k) for all k in {1,...,5}.

which makes no sense, because if b₁ is 33 then later on b₃ will be larger than 325.

I have reverted the page. Please feel free to add back the remarks you put in about upper bounds, or to revert the page again and then correct the damage you did to the proof. -- Dominus 13:40, 7 Sep 2004 (UTC)

Sorry about that. I went through the proof again; the error you pointed out was the only error I made in the proof, as far as I can tell. I'm pretty sure it's correct now. Terry 05:59, 8 Sep 2004 (UTC)

Yes, you're right. I'm sorry I said you had no understanding of what was going on; it looked to me like you had just done a global replace of each number n with n-1. Thanks for correcting the proof and adding back your remarks about the upper bounds. -- Dominus 13:39, 8 Sep 2004 (UTC)

[edit] Proof

A very simple way to prove the Van der Wareden's theorem is to derive it as a corollary of Gallai's Theorem which in turn is a corollary of the Hales–Jewett theorem. The proof runs like this:

Apply Gallai's Theorem for V = {0,...k}. Now {b, b+c,...b+kc} is monochromatic. Q.E.D.

Note->Here we were looking for an AP of length k. c and b are the positive integers existing by Gallai's so that cV + b is monochromatic.

This should be included in the article. Any comments?--Shahab 10:16, 17 May 2007 (UTC)

While that does seem to work (although I'm not entirely familiar with Gallai's Theorem), I would say that it doesn't make sense to prove things "backwards" - although these generalized versions of each can be proven subsequently and independently, I think it makes more sense to prove them from the ground-up, as opposed to using the most general theorem at any given time to plainly and uninsightfully assert the more specific cases. Cheeser1 15:20, 17 May 2007 (UTC)

I am only talking about adding the fact that Van der Waerden's theorem is a corollary of Gallai's theorem (or of the Hales-Jewett Theorem) because it is a point worth realizing that all these theorems are a part of general geometric picture. You are right Cheeser1 when you say that it makes sense to give an insightful picture but there is no reason why the Hales Jewett bit can't be included in the article. Adding some info won't hurt the insight. BTW although the Hales Jewett Theorem is a generalization, it and the Van der Waerden's theorem have very similar colour focussing proofs, so HJ is really not that far advanced then VDW. Cheers--Shahab 13:01, 18 May 2007 (UTC)

I'm not sure when it was added, but I just noticed there is mention of both Szemeredi's theorem and Hales-Jewett as stronger theorems. I also noticed that this article's a bit of a mess, I think. Maybe I'll tidy it up. --Cheeser1 22:21, 17 June 2007 (UTC)

[edit] importan nitpicking

Is there anyone who can look at the expression

,

without instantly see why the comma really needs to be INSIDE the "displayed" TeX? On the browser I'm using, it is positioned ridiculously. Michael Hardy 01:43, 21 June 2007 (UTC)

[edit] request explanation of bound

What is the point in the sentence "The best-known lower bound for V(2,k) is that V(2,k) > 2k / kε for all positive ε.[4]"? It seems to mean that V(2,k) is at least equal to 2k. —Preceding unsigned comment added by 193.50.42.4 (talk) 09:31, 22 May 2008 (UTC)

The statement is that V(2,k) > 2^k / k^ε for all positive ε. This means that although V(2,k) is not known to exceed 2^k in general, it is known to come very, very close: it exceeds 2^k / k^0.000001 and other quantities that are just a hair smaller than 2^k. -- Dominus (talk) 17:10, 22 May 2008 (UTC)