, 2022

Proof. For $n \ge 25$, write $5^{2t} \le n < 5^{2t+2}$ for $t \in \mathbb{N}^*$. Take the set
$$A = \{(\alpha_{2t}, \dots, \alpha_1)_5 \mid \alpha_{2i} \in \{0, 1, 2, 3, 4\} \text{ and } \alpha_{2i-1} \in \{1, 3\} \text{ for } i = 1, \dots, t\},$$
where $(\alpha_{2t}, \dots, \alpha_1)_5$ denotes the number $m = 5^{2t-1}\alpha_{2t} + \dots + 5\alpha_2 + \alpha_1$ in quinary. It is obvious that $A \subset \{1, 2, \dots, n\}$.
For each pair of integers $u_1, u_2 \in A$, write $u_1 = (a_{2t}, \dots, a_1)$ and $u_2 = (b_{2t}, \dots, b_1)$. We may assume $u_1 > u_2$ and consider $u_1 - u_2$. Now let $s$ be the minimal index such that $a_s \ne b_s$. Namely, we have $a_1 = b_1, \dots, a_{s-1} = b_{s-1}, a_s \ne b_s$. Note that in this case, $u_1 - u_2 = (a_{2t} - b_{2t})5^{2t-1} + \dots + (a_s - b_s)5^{s-1}$.
If $2 \mid s$, then $5^{s-1} \mid (u_1 - u_2)$ i.e., $a_s - b_s \ne 0$ and $-4 \le a_s - b_s \le 4$. Hence $u_1 - u_2$ cannot be a perfect square.
If $2 \nmid s$, then $\frac{u_1 - u_2}{5^{s-1}} = (a_{2t} - b_{2t})5^{2t-1} + \dots + (a_s - b_s) \in \mathbb{Z}$. Suppose that $u_1 - u_2$ is a perfect square, then $\frac{u_1 - u_2}{5^{s-1}}$ is a perfect square as well. On the other hand, the condition $2 \mid s - 1$ and $a_s \ne b_s$ implies that $\{a_s, b_s\} = \{1, 3\}$ and $\frac{u_1 - u_2}{5^{s-1}} \equiv 2, 3 \pmod 5$, which can never be a perfect square. This is a contradiction.
Thus for any distinct element $u_1, u_2 \in A$, the number $|u_1 - u_2|$ is not a perfect square. Hence $A$ satisfies the requirement. Also, note that $|A| = 10^t$. Since $\alpha = \log_{25} 10 > 1/2$, we obtain
$$n^\alpha < 5^{(2t+2)\log_{25} 10} = 10^{t+1} = 10|A|.$$
So it suffices to take $C = \frac{1}{24}$ and $\alpha = \log_{25} 10 \in (0, 1)$. As for $n \le 24$, we may take $A = \{1\}$ and then $|A| \ge \frac{1}{24}n \ge \frac{1}{24}n^\alpha$.
To sum up, for all $n \in \mathbb{N}^*$, one can find a desired subset $A$ with $|A| \ge Cn^\alpha$.