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.

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.

Your Answer


By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.