Prove that there exists a set of infinitely many positive integers such that the elements of no finite subset of this set add up to a perfect square.
Problem
Source: India Postal Coaching 2015
Tags: combinatorics
02.12.2015 04:36
You could have the integers $2^1,2^3,2^5,\cdots,2^{2n+1},\cdots$. The sum of any subset of these integers must be equal to $2^{2k+1}\pmod{2^{2k+2}}$, where $2^{2k+1}$ is the smallest integer chosen from the set. Since there is always an odd number of 2s in the prime factorization, it will never be a perfect square.
02.12.2015 04:44
Suppose you already have a set of such integers $A = \{a_1, a_2, .., a_n\}$. Let $s_1$, $s_2$, .., $s_{2^n-1}$ denote the sums of every non-empty subset of $A$. By CRT, there exists a positive integer $a_{n+1} > \max{a_i}$, such that $a_{n+1} + s_i \equiv p_i $ $\mod p_i^2$ for each $1 \le i \le 2^n -1$, where $p_i$ denotes the i-th prime (you can add the condition $a_{n+1} \equiv p_{2^n}$ $\mod p_{2^n}^2$ to make sure $a_{n+1}$ is a non-perfect square). The set $A \cup \{a_{n+1}\}$ satisfies the conditions. By starting from $A = \{2, 3\}$, you can get an infinite set.
02.12.2015 04:46
I can generalize this! Use $$\mathcal{A}=\{x|x=3 \cdot 15^n\}.$$ Pick some subset $\mathcal{E}$ with $a_1< a_2< a_3< \dots$ where $a_k$ is the largest power of $15$ dividing each element. The elements will sum to $$3\cdot 15^{a_1}+3\cdot 15^{a_2}+3\cdot 15^{a_3}+\dots=3^{a_1+1}5^{a_1}(1+\sum{15^{a_k-a_1}})$$ Notice that the first $3^{a_1+1}5^{a_1}$ is coprime to the other factor, so either $a_1+1$ or $a_1$ will always be odd, hence no perfect square (or perfect power, why?) can exist in $\mathcal{A}$$.\:\blacksquare\:$
02.12.2015 08:40
The sequence $2^{2n+1}, n\ge 9000$ works.
02.12.2015 08:55
how about all such sets? can we say anything about them?
04.12.2015 09:53
utkarshgupta wrote: Prove that there exists a set of infinitely many positive integers such that the elements of no finite subset of this set add up to a perfect square. All of the above proofs use some number theory stuff. But the core of the problem is not NT at all. Let $M$ be an infinite set with density $0$, that's: \[\lim_{N\to\infty} \frac{\#\{n\in\mathbb{N}: n\in M, n\leq N\}}{N}=0\]then there exists a set of infinitely many positive integers such that the elements of no finite subset of this set add up to a member of $M$. Proof: Suppose we have already constructed a set of such positive integers $A=\{a_1,a_2,\dots,a_n\}$. Let $A'$ be the set of all sums of subsets of $A$. Let $a := \max(A')$. consider the sets $A'_j := A'+j a\,,\, j=1,2,\dots$. Then $A'_j$ are pairwise disjoint. If we assume that every $A'_j$ meets an element of $M$ then it would be a contradiction with the fact $M$ has density $0$. So, there is a $j\in \mathbb{N}$ such that $A\cup \{j a\}$ again satisfies the requirements.
04.12.2015 11:22
In fact u dont even need density 0, the only thing u use is there exist 'a' consecutive integers that dont belong to M. So u just need M to be not syndetic.
04.12.2015 20:45
Yes, you are right. The requirement: "$M$ to have arbitrary large holes" is the weakest assumption this approach can cover.