Infinite set such that sum of elements of every finite subset is not a power of $p$

Question

Let $p$, be a prime number, and $S$ an infinite set of positive integers, such that all numbers from $S$ are coprime with $p$.

Prove that there is an infinite subset $A\subseteq S$, such that for every finite subset $X\subseteq A$, the sum of the elements of $X$ is not a power of $p$. (i.e. $\sum_{s\in X} s\neq p^k$ for every positive integer $k$).

My attempt:

I think that I have actually managed to prove that for every positive integer $n$, there is a finite subset, $A$ of $S$, such that $A$ has the desired property, and $|A|=n$, but as far as I am concerned, proving that the cardinal of $A$ can be as big as we want, does not necessarily mean that it can also be infinite.

My proof for this is pretty long, but if someone asks for it I will try to add it here.

Answer 1

Define $S_k=\{n\in S:n<p^{k+1}\}$ and define

$$s_k=\min\{p^{k+1}-n:n\in S_k\}$$

For example, with $p=5$, $S=\{1,4,7,9,11,24,26,...\}$, and $k=1$ we have

$$S_k=\{1,4,7,9,11,24\}$$

$$s_k=\min\{1,14,16,18,21,24\}=1$$

Further, define $f=\liminf_{k\to\infty} s_k$. Obviously, since $s_k$ takes integer values either $f=\infty$ or there are infinite $k$ such that $s_k=f$. We consider both cases:

Case 1: Suppose $f=\infty$, implying $s_k\to\infty$. Let $T$ be any finite set such that

$$\{\sum_{n\in W}n\neq p^k:W\in P(T)\text{ and }k\in\mathbb{N}\}$$

Now, since $s_k\to\infty$ and $S$ is infinite, there exists $m$ such that

$$p^m<s_m$$

and

$$2\sum_{n\in T}n<s_m$$

This means that there exists at least one member $s\in S$ such that

$$p^m<s<s+\sum_{n\in T}n<p^{m+1}$$

This then implies that for all $W\in P(S)$ we have

$$p^m<s<s+\sum_{n\in W}n\leq s+\sum_{n\in T}n<p^{m+1}$$

which implies that for all $W'\in P(T')=P(T\cup\{s\})$

$$\sum_{n\in W^{'}}n\neq p^k$$

for all $k\in\mathbb{N}$. Extending this process by induction (with an intial $T=\{\min(S)\}$) gives us our desired infinite subset of $S$.

Case 2: Suppose $f$ is finite. This implies that the set

$$K=\{k\in\mathbb{N}:s_k=f\}$$

is infinite. Additionally, for all $m\in K$ we have

$$p^{m+1}-f\in S$$

Now, choose $m\in K$ such that

$$p^{m+1}-p^m>5f$$

and define $T=\{p^{m+1}-f\}$. It is obvious that

$$p^{m+1}-f\neq p^k$$

for any $k\in\mathbb{N}$. In a similar manner as above, we will prove that $T$ can be extended such that no subset of $T$ sums to a power of $p$. Now, suppose that we have a finite set

$$T\subset \{p^{m+1}-f:m\in\mathbb{N}\}$$

such that no subset of $T$ sums to a power of $p$. Define

$$R=\{p^{m+1}-f:0\leq m\leq |T|\}$$

Further, let $q$ be the smallest integer in $K$ such that

$$p^{q+2}-p^{q+1}+f>\sum_{n\in R}n$$

Since every element of $T$ is greater than $5f$, this gives us

$$p^{q+1}-f+\sum_{n\in T}n>p^{q+1}+3f>p^{q+1}$$

and

$$p^{q+1}-f+\sum_{n\in T}n<p^{q+1}-f+\sum_{n\in R}n<p^{q+2}$$

Put together, this implies that for all $W\in P(T)$ we have

$$p^{q+1}<p^{q+1}-f+\sum_{n\in T}n\leq p^{q+1}-f+\sum_{n\in R}n<p^{q+2}$$

which implies that for all $W'\in P(T')=P(T\cup\{p^{q+1}-f\})$

$$\sum_{n\in W^{'}}n\neq p^k$$

for all $k\in\mathbb{N}$. This completes the proof.

Answer 2

Start with $A_0=\emptyset$. Given $A_{n-1}$, pick $s_n\in S$ with $s_n>\max A_{n-1}$, and such that there is no $k$ with $s\le p^k\le s+\sum_{x\in A_{n-1}}x$ and set $A_{n}=A_{n-1}\cup \{s_n\}$. There are two possibilities:

a) We can continue this process forever.

Then let $A=\bigcup_nA_n$. If $X$ is a finite subset of $A$, let $n$ be maximal with $s_n\in X$. Then by construction, $$ s_n\le \sum_{x\in X}x\le s_n+\sum_{x\in A_{n-1}}x$$ and there is no power of $p$ in that range.

b) The construction stops because for some $A_{n-1}$, no suitable $s_n$ exists.

Then there exists $m$ such that for every $s\in S$, there exists $k$ with $s\le p^k\le s+m$. Say $s\sim t$ if $\lceil \log_ps\rceil=\lceil \log_pt\rceil$ and let $A$ be a set of representatives of $(S\setminus\{1,\ldots,m\})/{\sim}$. As each equivalence class is finite, $A$ is infinite. Let $r\ge1$ and let $X=\{x_0,x_1,\ldots,x_r\}$ be an $(r+1)$-element subset of $A$ with $x_0>x_1>\cdots >x_r$. Let $M=\log_px_0 $. Then $p^M-m\le x_0\le p^M$ whereas for the $1\le i\le r$, we have $$ m+1\le x_i\le p^{M-i}.$$ Therefore, $$p^M<p^{M}-m +r(m+1)\le \sum_{x\in X}\le p^{M}+p^{M-1}+\cdots +p^{M-r}<p^{M+1}, $$ and so the sum of elements of $X$ is not a power of $p$.