A certain kind of set of integers

Question

Let us call a set $S$ of integers sparse if for any four integers $a,b,c,d \in S$ such that $a<b<c<d$, we have that $a+d \ne b+c$. Define $P(n)$ to be maximal size of a sparse subset of $\{1,2,\dotsc,n\}$. Is it true that $\lim\limits_{n\to \infty} P(n)/n=0$?

Answer 1

Yes, it's true. It follows from (the finitary version of) Szemerédi's theorem: if a set $A\subseteq\mathbb N$ has positive upper density, then for every positive integer $k$ it contains an arithmetic progression of length $k;$ see Endre Szemerédi, On sets of integers containing no $k$ elements in arithmetic progression, Acta Arithmetica 27 (1975), 199–245. The case $k=4$ was proved earlier: Endre Szemerédi, On sets of integers containing no four elements in arithmetic progression, Acta Math. Acad. Sci. Hungar. 20 (1969), 89–104. (Of course, a "sparse" set contains no arithmetic progression of length $4.$)

Answer 2

Here's an explicit, tighter bound for the size of a sparse set. If $A\subseteq \{1,2,\ldots,n\}$ is sparse, then every pair of distinct elements of $A$ has a distinct sum. There are $\Theta(|A|^2)$ pairs of distinct elements, but only $O(n)$ different sums that they can have. By the pigeonhole principle we conclude that $|A|$ is $O(\sqrt{n})$, and hence $|A|/n$ is $O(1/\sqrt{n})$.