Let $a_{1} = 1$. For $n \in \mathbb{N}$, $n \geq 2$ we inductively define $a_{n}$ to be the smallest natural number bigger than $a_{n-1}$ so that $a_{n}-a_{j}$ is not square for $j=1,...,n-1$. The first few terms of the sequence are $1,3,6,8,11,13,...$.
Let $\hat{S}_{n} = \{S: S\subset \{1,...,n\}, a,b \in S \Rightarrow |a-b| \text{ is not a square } \}.$
Do we have
$$S \in \hat{S}_{n} \Rightarrow |S| \leq |\{s: s \in (a_{j})_{j\in \mathbb{N}}, s \leq n\}| ?$$
The sequence $(a_{j})_{j\in \mathbb{N}}$ has infinitely many members (simple exercise). A related sequence has been studied for the game of "subtract the square'' (see https://en.wikipedia.org/wiki/Subtract_a_square and https://oeis.org/A030193).
The first few terms of the sequence $(a_{j})_{j\in \mathbb{N}}$ are $1,3,6,8,11,13,...$
This question is asked to know whether the constructed greedy sequence (found elsewhere in literature when shifted back by $1$) is the "densest" in the intervals $[1,n]$ for $n \in \mathbb{N}$.
Some examples of the largest sets of $\hat{S}_{n}$ and confirmation of our conjecture for various $n$;
For $n=1$ the largest set of $\hat{S}_{1}$ is $\{1\}$. $1 \leq |\{s: s \in (a_{j})_{j\in \mathbb{N}}, s \leq 1\}|$
For $n=2$ the largest sets of $\hat{S}_{2}$ are $\{1\}$ and $\{2\}$ respectively. Each has size of not more than $1$.
For $n=3$ the largest set of $\hat{S}_{3}$ is $\{1,3\}$.
For $n=4$ the largest sets of $\hat{S}_{4}$ are $\{1,3\}, \{2,4\}, \{1,4\}$. Each has a size of not more than $2$.
For $n=5$... $\{1,3\},\{2,4\}, \{1,4\},\{2,5\}, \{3,5\}$.
For $n=6$...$\{1,3,6\}, \{1,4,6\}$
For $n=7$... $\{1,3,6\}, \{1,4,6\}, \{2,4,7\}, \{2,5,7\}, \{1,4,7\}$
For $n=8$... $\{1,3,6,8\}$
For $n=9$...$\{1,3,6,8\}, \{2,4,7,9\}, \{1,3,6,9\}, \{1,4,6,9\}$
For $n=10$...$\{1,3,6,8\}, \{2,4,7,9\}, \{1,3,6,9\}, \{1,4,6,9\}, \{2,5,8,10\}, \{2,4,7,10\}, \{2,5,7,10\} $
For $n=11$...$\{1,3,6,8,11\}, \{1,3,6,9,11\}, \{1,4,6,9,11\}$