No perfect squares in A-A

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JustPostChinaTST

38 posts

JustPostChinaTST

#1 h Apr 30, 2022, 3:17 PM • 5 Y

Y by ImSh95, oVlad, Mango247, Mango247, Mango247

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.

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

Prod55

127 posts

Prod55

#2 h May 2, 2022, 12:24 PM • 1 Y

Y by ImSh95

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

IAmTheHazard

5001 posts

IAmTheHazard

#3 h May 2, 2022, 12:50 PM • 1 Y

Y by ImSh95

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

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

oVlad

1746 posts

oVlad

#4 h May 2, 2022, 2:55 PM • 5 Y

Y by ImSh95, pavel kozlov, Mango247, Kingsbane2139, MS_asdfgzxcvb

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!

This post has been edited 2 times. Last edited by oVlad, May 2, 2022, 2:57 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

CANBANKAN

1301 posts

CANBANKAN

#5 h May 7, 2022, 6:17 AM • 2 Y

Y by pavel kozlov, rama1728

wait oops this is clearly easier than problem 3 of test 3. In fact, if you want me to flex

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.

This post has been edited 2 times. Last edited by CANBANKAN, May 22, 2022, 11:42 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

JG666

287 posts

JG666

#7 h May 22, 2022, 11:38 PM • 2 Y

Y by VicKmath7, Mango247

The main idea is Trivial solutions --> Generalize.

I'll present two similar approaches.

Solution 1)

Solution 2)

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

This post has been edited 2 times. Last edited by JG666, May 22, 2022, 11:43 PM

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

flower417477

375 posts

flower417477

#8 h Sep 1, 2023, 10:02 AM

Y by

JG666 wrote:

The main idea is Trivial solutions --> Generalize.

I'll present two similar approaches.

Solution 1)

Solution 2)

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$

Z K Y

The post below has been deleted. Click to close.

This post has been deleted. Click here to see post.

kes0716

18 posts

kes0716

#9 h Apr 18, 2025, 8:47 AM

Y by

JG666 wrote:

The main idea is Trivial solutions --> Generalize.

I'll present two similar approaches.

Solution 1)

Solution 2)

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

I think the first solution is incorrect because $25-9=16$ is square while $25=19_{(16)}$ and $9=9_{(16)}$ are in $A$ . It is necessary that in the choice of digits, not only differences but also elements themselves should be not square modulo $16$ . Choosing $2,5,7,13,15$ as the set of digits will be correct.

This post has been edited 1 time. Last edited by kes0716, Apr 18, 2025, 8:48 AM

Z K Y