9
$\begingroup$

Let $W$ be an infinite word over a finite alphabet $\{1,\dots,n\}$ and $k$ a positive integer. An easy application of Van der Waerden's theorem implies the existence of $k$ disjoint and consecutive intervals in $W$ such that the sum of letters in each interval are equal (Edit. See Barber's answer).

On the other hand, Van der Waerden's theorem for the coloring by two colors (which easily implies the general case of every finite coloring) can be derived by this statement without much effort (Edit. See the comments). So I think of it as an equivalent form of original Van der Waerden theorem.

I had conjectured a stronger version which I was unable to prove or disprove it:

Conjecture: If $W$ is an infinite word over finite alphabet. Then for every positive integer $k$, there exists $k$ disjoint and consecutive intervals in $W$, with the same number of occurrence of each letter.

I also know that a weaker version of this conjecture for binary alphabet and "the same" replaced by "proportional" is correct.

Does there exist a similar known result? Can someone give a prove or counterexample?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ By "disjoint and consecutive intervals" do you mean something like $[2,4],[5,7],[8,10]$? If so, could you please describe the easy application of Van der Waerden's theorem? $\endgroup$
    – Ben Barber
    Commented Aug 6, 2014 at 13:47
  • $\begingroup$ @Ben Yes, this is exactly what I mean and the length of intervals are not necessarily equal. (but the condition in the conjecture implies they are also of the same length). $\endgroup$
    – Mostafa - Free Palestine
    Commented Aug 6, 2014 at 13:57
  • $\begingroup$ @Ben You can see that the above statement implies Van der Waerden for two colors (red and blue) by such an argument: if there are $n$ consecutive blue numbers then we have an a.p. of length $n$, otherwise consider the sequence of (lengths of intervals of blue numbers plus one) and apply the statement for $k=n-1$ which implies the existence of $n$ equidistant red numbers. $\endgroup$
    – Mostafa - Free Palestine
    Commented Aug 6, 2014 at 14:02
  • $\begingroup$ @Mostafa This is proof of Van der Waerden from your statement. I think Ben asked for proof in the otther direction (that Van der Waerden's theorem implies your statement about intervals). $\endgroup$
    – Wojowu
    Commented Aug 6, 2014 at 14:06
  • $\begingroup$ @Wojowu It can be proved from an stronger version of Van der Waerden for two colors: either you have $n$ consecutive blues or a red a.p. of length $n$. Unfortunately I have forgotten the prove but I'm sure that this is correct. $\endgroup$
    – Mostafa - Free Palestine
    Commented Aug 6, 2014 at 14:11

3 Answers 3

Reset to default
18
$\begingroup$

Your claim is not true.

Two consecutive blocks having the same number of occurrences of each letter (such as the English word "reappear") form what is called an "abelian square". A google search will easily produce a large literature on this subject. The best result (in terms of alphabet size) is due to the Finnish mathematician V. Keranen in 1992: he proved the existence of an infinite word over a 4-letter alphabet having no abelian squares. 4 is best possible, as an easy backtracking argument shows there is no such word over a 3-letter alphabet.

Three consecutive blocks with the same property form an "abelian cube". Dekking proved in 1979 that there is an infinite word over a 3-letter alphabet avoiding abelian cubes. Again, 3 is best possible for alphabet size.

Four consecutive blocks with the same property form an "abelian 4th power". Dekking also proved in 1979 that there is an infinite word over a 2-letter alphabet avoiding abelian fourth powers.

You can easily find references with a google search.

Improve this answer
$\endgroup$
0
4
$\begingroup$

Here's a proof of the first statement from Van der Waerden's theorem for $n$ colours and progressions of length $k+1$ for those who'd like to see it.

Given a word $w = a_1a_2a_3\cdots$ on alphabet $[n] = \{1, 2, \ldots, n\}$, obtain a new word $w'$ by replacing each $a_i$ by a copy of $[a_i]$ (listed in increasing order). By Van der Waerden's theorem there is a monochromatic $(k+1)$-AP in $w'$, and by translation we may assume that the colour is $1$. But then the distance between consecutive terms of the AP in $w'$ is precisely the sum of the letters in the block between the corresponding letters of $w$.

Improve this answer
$\endgroup$
1
$\begingroup$

Partial answer/trivial observation: If the intervals are not required to be consecutive, it is easy to show the statement:

Consider such an infinite string. Divide the string into disjoint, consecutive intervals, with exactly $k$ letters in each interval (block).

It is clear that some type of block must appear infinitely many times, and this proves the weaker statement.

Ramble: Now, can we maybe replace each block with a new symbol, where the symbol denotes the "type" of the block (i.e., depending on the letter distribution inside).

We can now apply the theorem again on the blocks... Or something.

Improve this answer
$\endgroup$
1
  • $\begingroup$ I made a mistake in interpreting the problem, however, the idea might perhaps still be useful? $\endgroup$
    – Per Alexandersson
    Commented Aug 6, 2014 at 14:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .