# Existence of Arithmetic Progression from density inequality

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.

• $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*}