1
$\begingroup$

Prove or disprove:

For all functions $f:\Bbb Z^+ \to \{0,1\}$ , the following is true: There exists positive integers n and d such that: $$f(n)=f(n+d)=f(n+2d)=f(n+3d)$$

  • 0
    Is it homework ?2012-05-04
  • 0
    No, it is not. I can show that their exists n and d such that f(n)=f(n+d)=f(n+2d). I wanted to know if the statement that I posted originally is true or not.2012-05-04
  • 0
    I would say yes, but so far, I have no proof. I think its even true for arbitrary length. (T. Tao would know of course ;))2012-05-04
  • 0
    I think it is true too. Moreover I think that that for all positive integers k there exists n and d such that f(n)=f(n+d)=f(n+2d)=f(n+3d)=......=f(n+kd)2012-05-04

1 Answers 1

2

The Szemerédi’s theorem applies here. It says that for all $0 < d < 1$, and $k$ positive integer, there exists $N$, such that every subset of $\{1, \dotsc, N \}$ with cardinal at least $dN$ contains an arithmetic progression with length $k$.

Take $d = 1/2$ and $k = 4$, and let $N = N(1/2, 4)$. Either $[1, N]\cap f^{-1}(1)$ as cardinal at least $N/2$, or $[1, N] \cap f^{-1}(0)$ has. So there is a arithmetic progression of length 4 in one of them. Qed.

Edit

It appears that this easy corollary of the Szemerédi’s theorem is in fact a special case (2 colors) of the easier van der Waerden's theorem (1927).