# Arithmetic progression in a set or its complement

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)$$

-
Is it homework ? – Lierre May 4 '12 at 16:31
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. – Amr May 4 '12 at 16:41
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 ;)) – Lierre May 4 '12 at 16:43
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) – Amr May 4 '12 at 16:46

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.