JustPostChinaTST wrote: Show that there exist constants $c$ and $\alpha > \frac{1}{2}$, such that for any positive integer $n$, there is a subset $A$ of $\{1,2,\ldots,n\}$ with cardinality $|A| \ge c \cdot n^\alpha$, and for any $x,y \in A$ with $x \neq y$, the difference $x-y$ is not a perfect square. any solution for this ? i can prove it only for $a=1/2$ but not for $a>1/2$

https://en.wikipedia.org/wiki/Square-difference-free_set ...

Choose the set $S=\{1,3,8\}.$ This set has the property that for any distinct $a,b\in S,$ $a-b$ is not a quadratic residue modulo $13$. Based on this observation, we will construct the following infinite set:\[N=\bigg\{\sum_{i=0}^\infty \lambda_i\cdot 13^i:\lambda_{2j}\in S, \ \lambda_{2j+1}\in\{0,1,\ldots,12\} \ \forall j\geq 0\bigg\}.\]Let's firstly show that $N$ is indeed square-difference-free. Assume this weren't the case. Therefore, for two sequences $(\alpha_i)$ and $(\beta_i)$ satisfying $\alpha_{2j},\beta_{2j}\in S$ and $\alpha_{2j+1},\beta_{2j+1}\in \{0,1,\ldots, 12\}$ we have \[\sum_{i=0}^\infty (\alpha_i-\beta_i)\cdot 13^i=K^2.\]Let $t$ be the smallest index for which $\alpha_t\neq\beta_t.$ Such an index clearly exists, as $(\alpha_i)\neq(\beta_i).$ It then follows that \[k\cdot 13^{t+1}+(\alpha_t-\beta_t)\cdot 13^t=K^2.\]If $t$ is odd then as $\nu_{13}(K^2)=t$ we reach a contradiction. On the other hand, if $t$ is even, then we get $13k+(\alpha_t-\beta_t)=K'^2$ which is another contradiction, since $\alpha_t\neq\beta_t\in S$ so $\alpha_t-\beta_t$ is not a quadratic residue modulo $13$. Therefore $N$ is square-difference-free. It only remains to estimate the number of elements of $N$ smaller than some $t$. Note that $\lambda_i\leq 12$ for all indices, so we can infer that $\lambda_0\cdot 13^0+\cdots+\lambda_k\cdot 13^k\leq 12(13^0+\cdots+13^k)=13^{k+1}-1.$ Thus \begin{align*}N_t=\Bigg\{\sum_{i=0}^{\lfloor\log_{13}t\rfloor} \lambda_i\cdot 13^i:\lambda_{2j}\in S, \ \lambda_{2j+1}\in\{0,1,\ldots,12\} \ \forall j\geq 0\Bigg\}\subseteq \{1,2,\ldots,t\}.\end{align*}Bearing in mind that there are $\lfloor k/2\rfloor$ even numbers $\leq k$ and $\lfloor (k-1)/2\rfloor$ odd numbers $\leq k$ we can conclude that\begin{align*}|N_t|&=3^{\lfloor\lfloor\log_{13}t\rfloor/2\rfloor}\cdot 13^{\lfloor(\lfloor\log_{13}t\rfloor-1)/2\rfloor}\geq \sqrt{3^{\log_{13}t}\cdot 13^{\log_{13}t-1}}=1/\sqrt{13}\cdot \sqrt{t^{1+\log_{13}3}}.\end{align*}Note that $N_t\subset N$ so $N_t$ is square-difference-free. Therefore, by choosing $c=1/\sqrt{13}$ and $\alpha=(1+\log_{13}3)/2$ we win!

Let $f(n)$ denote the size of the maximal set $A \subseteq \{0,\cdots,n-1\}$ such that $A-A$ contains no squares. I claim $f(n)\ge 10f(\lfloor \frac{n}{25} \rfloor ) \ge 10f(\frac{n}{26})$ for all sufficiently large $n$. Consider the construction for $\lfloor \frac{n}{25} \rfloor$, call $A'$. Consider the set $A=25A' + \{0,5,10,15,20,2,7,12,17,22\}$. I claim $A$ is good as well. Consider $a_1, a_2\in A$. We have 3 cases: 1. $\nu_5(a_1-a_2)=1$, which means $a_1-a_2$ is not a perfect square. 2. $a_1-a_2\equiv \pm 2(\bmod\; 5)$ which means $a_1-a_2$ is not a perfect square. 3. $25\mid a_1-a_2$. This means $a_1=25b_1+r, a_2=25b_2+r$ for some $0\le r\le 24,$ and $b_1,b_2\in A'$. By our assumption on $A'$, $|b_1-b_2|$ isn't a perfect square. Therefore, $a_1-a_2=25(b_1-b_2)$ is not a perfect square. Thus, $c=0.00001, \alpha=\log_{25}(10)$ works. Now, the set $A+1$ satisfies the condition in the problem.

The main idea is Trivial solutions --> Generalize. I'll present two similar approaches.

I believe these two are more succinct than any one above.

JG666 wrote: The main idea is Trivial solutions --> Generalize. I'll present two similar approaches.

I believe these two are more succinct than any one above. I solve this using also hexademical expression,but i choose $2,5,7,13,15$