Existence of Arithmetic Progression from density inequality

Question

Let $A\subset \{0,1,\dots, N-1\}$ such that $$|A\cap [0,N/3)|\geq \left(\delta+\dfrac{\delta}{8}\right)\cdot \dfrac{N}{3},$$ where $\delta\in (0,1]$. Prove that exists arithmetic progression $P$ with $|P|\ge N/3$ such that $|A\cap P|\geq \left(\delta+\dfrac{\delta}{8}\right)|P|$.

Remark: By $[0,N/3)$ I denote the set of integers from this interval.

If $N$ is divisible by $3$ then we can take $P:=[0,N/3)$ which is also a progression and $|P|=N/3$ we have $|A\cap P|\ge \left(\delta+\dfrac{\delta}{8}\right)|P|$.

If $N$ is not divisible by $3$ and if we we take $P:=[0,N/3)$ which is also progression and has $\lfloor\frac{N}{3}\rfloor+1$ elements. However, I am not able to derive the needed inequality.

Would be very grateful if anyone can explain how to approach in the case when $3\nmid N$?

P.S. This question refers to the proof of Roth's theorem.

Answer 1

This is false. Without loss of generality we may assume that

• $A \subseteq [0,N/3)$ and
• $|A| = (\delta + \delta/8) N/3$.

In the cases where $N$ is not divisible by $3$, you have exactly two sensible choices for $P$: $[0, \lfloor N/3 \rfloor-1]$ and $[1,\lfloor N/3 \rfloor]$. But if $A$ happens to contain both $0$ and $\lfloor N/3 \rfloor$, then $$ \begin{align*} |A \cap P| & \leq |A| - 1 = (\delta + \delta/8) N/3 - 1 \\ & \leq (\delta + \delta/8) \lfloor N/3 \rfloor - 1/3 < (\delta + \delta/8)|P|. \end{align*} $$

It's very easy to get caught up on small discrepancies like this between what an author meant and what they wrote. One of the skills of reading papers that you have to develop is how to handle this sort of problem. Terry Tao has written some excellent advice on this subject here.