Consider the following statement due to F.Behrend (1946)

Theorem: Let $N$ be a large integer. Then there exists a subset $A\subset [1,N]$ with $\frac{|A|}{N}\geq \exp(-4\sqrt{\ln N})$ which does not contain any arithmetic progression of length three.

By $[1,N]$ I mean the set of integers from this interval.

Informally this theorem states that we can construct a large set of integers which lacks three-term arithmetic progression.

Let me ask the following question: Suppose we have that $\frac{|A|}{N}\geq \exp(-4\sqrt{\ln N})$ then why we say that the set $A$ is large? On one hand, $\exp(-4\sqrt{\ln N})\to 0$ as $N\to +\infty$. On the other hand we call it large?

I would be very thankful for explanation since I am novice in this field of math.

  • 3
    $\begingroup$ but the inequality works in the right direction, doesn't it? $|A|\geq \exp(\ln N-4\sqrt{\ln N})\rightarrow\infty $ when $N\rightarrow \infty$. $\endgroup$ – Carlo Beenakker Apr 5 '18 at 20:28
  • $\begingroup$ @CarloBeenakker, That's what I need! Thanks a lor for answer! +1 $\endgroup$ – RFZ Apr 5 '18 at 20:36

The term "large" is subjective, of course, but arguably a subset of $\{1,2,\dots,N\}$ of size at least $N^{1-o(1)}$ can be regarded as "large". The set $A$ in the theorem is of that kind, since $\sqrt{\ln N}=o(\ln N)$. See also small-o notation.


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.