On Sunday, February 2, 2014 2:28:15 AM UTC, William Elliot wrote: > On Sat, 1 Feb 2014, Paul wrote: > > > > > For example: BEGIN QUOTE Let [a, b] denote the set of integers x with a <= > > > x <= b. Let (x_1, ..., x_m), (y_1, ..., y_m) be members of [0, k] ^ m. > > > Then (x_1, ..., x_m), (y_1, ..., y_m) are called k-equivalent if they agree > > > up through their last occurrences of k. END QUOTE > > > > So if k not in x and y, then x and y are k-equivalent > > because it states up through, ie starting at x1 and y1 > > they have to be equal until the right k's show up and > > if they don't, then per force, to the end of sequence. > > > > > Suppose k = 5 and m = 1. Suppose also that we are working with the logic of > > > the definition, without reading ahead to get more context. Are the > > > 1-element sequences x = 2 and y = 3 k-equivalent? > > > > No. > > > > > This is completely unclear to me, and it seems that "yes" or "no" could be > > > argued with equal force. The yes-campaigners might say: "Yes, they are > > > 5-equivalent. > > > > It's difficulate to understand accurately. > > > > > No occurrence of 5 occurs in either sequence, so vacuously, > > > all the terms of x and all the terms of y occur after the non-existent > > > occurrences of 5. Since the only disagreements between x and y occur after > > > these non-existent occurrences, x and y are 5-equivalent." However, a > > > no-campaigner might argue: "No, they are not 5-equivalent. No occurrence of > > > 5 occurs in either sequence, so vacuously, all the terms of x and all the > > > terms of y occur before the non-existent occurrences of 5. Since x and y > > > disagree before we see the final (non-existent) occurrences of 5, x and y > > > are not 5-equivalent." > > > > > From context, it's clear that the authors are siding with the > > > yes-campaigners but I don't see how that's clear from the logic. Is this a > > > genuine ambiguity? If not, why are 2 and 3 5-equivalent, and why is the > > > no-argument wrong? > > > > He to be faulted for not explicately stating > > if simutanous k's never show up. I read it as: > > > > (1,2), (2,1) not 2-equivalent > > (2,2), (1,2) not 2-equivalent > > (1,2), (1,2) 2-equivalent > > (2,2), (2,1) 2-equivalent > > (1,1), (1,1) 2-equivalent > > (1,3), (1,1) not 2-equivalent > > > > although the 4th could be disputed. > > > > Email the author and ask him just what he does mean > > in no less than 100 words.
Thanks a lot for thinking about this problem in maths exposition. By reading other proofs of Van der Waerden, it is possible to deduce what the author means, so emailing the author is unnecessary. The point of my original post wasn't that I was unable to discern the meaning, but that I wasn't able to discern the meaning without further reading.
A clearer definition of k-equivalence is as follows: Let x and y be m-element sequences in [0, k] ^ m. Call a sequence k-free if k does not occur in the sequence. Then x and y are k-equivalent iff [ x and y are both k-free or ( x and y are both non-k-free and the sequence from x_1 to the last occurrence of k in x is the same sequence as the sequence from y_1 to the last occurrence of k in y) ].
With this definition, the proof of Van der Waerden works effortlessly if a further mistake in the paper is corrected -- the interval [a' * M + 1, (a' + 1) * M] needs to be replaced by the interval [(a' - 1) * M + 1, a' * M].
Perhaps these two corrections would result in the paper being better known. Now, the examples can be tackled. The 1-element sequences 2 and 3 are 5-equivalent. (1,2), (2,1) not 2-equivalent (2,2), (1,2) not 2-equivalent (1,2), (1,2) 2-equivalent (2,2), (2,1) not 2-equivalent because the final 2 in sequence 1 destroys the equivalence. (1,1), (1,1) 2-equivalent (1,3), (1,1) undefined. Not within the domain of definition because k-equivalence only applies to sequences of integers <= k and can't therefore contain 3 > 2.
Your 4th and 6th examples gave different results to what the authors intended.
Many many thanks for answering and thinking about the problem.