$S \subseteq \mathbb{N}$ and $\forall k \in \mathbb{N},$ there exists $x$ (depending on $k$) such that $\forall i,j \in S,$ we have $|i-j| \notin [x,x+2^k].$ How do I show that the density of $S$ in $\mathbb{N}$ is zero, or equivalently that $\lim\limits_{n \to \infty} \frac{S_n}{n} = 0$ where $S_n = |\{x \le n : x \in S\}|$?
Any individual value of $k$ does not restrict $S$ much because we can take $x = 2^k$ and $S = \{ x : (x \mod 3 \cdot 2^k) \in [0, 2^k) \}.$ On the other hand, we clearly have $|S_n|/|n| \le 0.5$ for $n$ large enough since once $x$ is defined, only one of $a, a+x$ can be in $S$ for all $a \in \mathbb{N}.$ Thus, we need to combine information from multiple values of $k.$
Approach 1: Perhaps we need to prove a statement of the form "at most one of $a, a+c, 1+2c, \dots, a+nc$ can be in $S$ for all $a \in \mathbb{N}$" for some $c$ depending on $n.$ Taking $n \to \infty$ proves the result. However, I have no idea how to proceed past the case $n=1.$
Approach 2: Maybe the statement could be proven by contradiction. If we suppose the limit is not zero, then there exists some $\epsilon > 0$ such that $S_n \ge n\epsilon$ for arbitrarily large values of $n.$ We need to derive a contradiction for $n$ large enough. However, I have no idea how large "large enough" would be here, so I have no idea how to proceed.
Any other approaches, ideas, or hints?