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

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.

• I think I have just proven my own question :)). I will post my solution in like 10 minutes. If you can , I would appreciate if you could, please check it for any mistakes. Thank you! May 9, 2022 at 18:33
• Ahhhh, never mind, my solution is wrong May 9, 2022 at 18:46
• To the person that posted a solution earlier, why did you delete it? Was it wrong? May 9, 2022 at 18:52
• I think that it was wrong, because if you have a fixed element from $S$, say $a$, $S$ can be exactly $\{ p^k-a$ : with k big enough such that $p^k>2a \}$ and you can't extend this set anymore so I think that this is why a greedy algorithm would never work May 9, 2022 at 18:54
• Yes, thats exactly why I deleted it. I'm working on a new proof right now, which hopefully manages to fix that error. May 9, 2022 at 18:56

Define $$S_k=\{n\in S:n 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

and

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

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

$$p^m

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

$$p^m

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

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

$$p^{q+1}

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.

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 and so the sum of elements of $$X$$ is not a power of $$p$$.