A finitary version of [839]. Taking $A=(N/2,N]\cap \mathbb{N}$ shows $\lvert A\rvert \geq N/2-O(1)$ is possible.

Adenwalla has observed that\[\lvert A\rvert \leq (\tfrac{2}{3}+o(1))N.\]Indeed, if $\lvert A\cap [x,2x]\rvert=t$ then there are $t-1$ distinct sums of consecutive pairs of elements in $(2x,4x]$, all of which are not in $A$ by assumption. It follows that\[\lvert A\cap [x,4x]\rvert \leq t+(2x-(t-1))=2x+1.\]It follows that\[\lvert A\rvert \leq \sum_{i\geq 1}\lvert A\cap [4^{-i}n, 4^{1-i}n]\rvert \leq \frac{2}{3}n+O(\log n).\]In fact this problem is false. Freud [Fr93] constructed a sequence with density $\geq 19/36$. The current best bounds are due to Coppersmith and Phillips [CoPh96], who prove that the maximal size of such an $A$ satisfies\[\frac{13}{24}N -O(1)\leq \lvert A\rvert \leq \left(\frac{2}{3}-\frac{1}{512}\right)N+\log N.\]

View the LaTeX source