Convergence of p-series over subset of the naturals This was a question from an exercise in a first semester Algebra class. The question is as follows:
Let $S \subseteq \mathbb{N}$ and suppose that $|\{n \leq x: n \in S\}| = O ((\log(x))^d)$ for some $d \geq 1$. Show that $$ \sum_{s \in S} \frac{1}{s^{\epsilon}}$$ converges for each $\epsilon > 0$.
My attempt:
I first tried to solve a simpler version of this problem in which we consider a subset $|\{n \leq x: n \in S\}| = O ((\log(x)))$. In this case, the series must converge because we can find a subsequence of partial sums of a geometric series with r < 1 that bounds the partial sums from above. I believe this is possible since the terms eventually become less dense in the reals than the terms of the aforementioned geometric series.
The problem arrives really when we have to prove that this result holds for all $d \geq 1$. I really don't know how to analyze this polylogarithmic growth of the cardinality of the subset.
We also proved earlier that $$ \prod _{n=1}^{\infty }(1+a_{n})$$
converges if and only if the series
$$ \sum _{n=1}^{\infty }a_{n}$$
converges for a sequence of positive reals $\{ a_n\}$. However, I don't see how converting this sum to a product really helps.
 A: This is a nice application of Abel's summation formula:
Indeed, define the indicator function $1_S \colon \mathbb{N} \to \{0,1\}$ of $S$ by $1_S(x) = 1$ if $x \in S$ and $1_S(x) = 0$ if $x \not\in S$. Now consider the partial sum
$$\sum_{s \in S, s \leq x} \frac{1}{s^{\varepsilon}} = \sum_{1 \leq n \leq x} 1_S(n) \cdot \frac{1}{n^{\varepsilon}} =^{\text{Abel}} A(x) \cdot \frac{1}{x^{\varepsilon}} + \varepsilon \int_{1}^x A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y,$$
where $A(x) := \sum_{1 \leq n \leq x} 1_S(n) = |\{n \leq x \colon n \in S\}|$. (Here we used that $-\varepsilon/y^{\varepsilon+1}$ is the derivative of $1/y^{\varepsilon}$.)
Now it remains to check that
$$\lim_{x \to \infty} \Big( A(x) \cdot \frac{1}{x^{\varepsilon}} + \varepsilon \int_{1}^x A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y \Big) < \infty$$
for every $\varepsilon > 0$. For the proof, we need two ingredients: On the one hand, our assumption says that
$$A(x) \leq C_0 \cdot \log(x)^d$$
for every sufficiently large $x > 0$ and some constant $C_0 > 0$. On the other hand, it is true that $\log(x) \in \mathcal{O}(x^{\delta})$ (as $x \to \infty$) for any $\delta > 0$. (You can prove this by computing $\lim_{x \to \infty} \log(x)/x^{\delta}$ using L'Hospital's rule.) As a consequence, we also have $\log(x)^d \in \mathcal{O}(x^{\delta})$ (as $x \to \infty$) for any $\delta > 0$ and $d \geq 1$.
The above suggests that there exists a constant $C_2 > 0$ such that for all $x > C_2$, we have
$$A(x) \leq C_0 \cdot \log(x)^d$$
and
$$\log(x)^d \leq C_1 \cdot x^{\varepsilon/2} \text{ for some constant } C_1 > 0.$$
Therefore,
$$\lim_{x \to \infty} A(x) \cdot \frac{1}{x^{\varepsilon}} \leq C_0C_1 \cdot \lim_{x \to \infty} \frac{x^{\varepsilon/2}}{x^{\varepsilon}} = C_0C_1 \cdot \lim_{x \to \infty} \frac{1}{x^{\varepsilon/2}} = 0$$
and
$$\lim_{x \to \infty} \varepsilon \int_{1}^x A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y = \int_{1}^{C_2} A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y + \lim_{x \to \infty} \varepsilon \int_{C_2}^x A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y \leq $$
$$\int_{1}^{C_2} A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y + \varepsilon C_0 C_1 \lim_{x \to \infty} \int_{C_2}^x \frac{y^{\varepsilon/2}}{y^{\varepsilon+1}} \text{ } \mathrm{d}y = \int_{1}^{C_2} A(y) \frac{1}{y^{\varepsilon+1}} \text{ } \mathrm{d}y + \varepsilon C_0 C_1 \int_{C_2}^\infty \frac{1}{y^{\varepsilon/2+1}} \text{ } \mathrm{d}y < \infty$$
(because $1 + \varepsilon/2 > 1$, suggesting that the integral $\int_{C_2}^\infty$ converges).
A: Here’s another proof.
For each $n \geq 0$, let $k_n$ be the number of elements $x \in S \cap [e^n,e^{n+1})$, so that $k_n \leq C(n+1)^d$ for some positive constants $C,d$.
Then, for each $n \geq 1$, $r > 0$,
$$S_n := \sum_{s \in S, s< e^n}{s^{-r}} \leq\sum_{p=0}^{n-1}{\sum_{s \in S, e^p \leq s < e^{p+1}}{s^{-r}}},$$ so
$$S_n \leq\sum_{p=0}^{n-1}{\sum_{s \in S,e^p \leq s < e^{p+1}}{e^{-rp}}},$$ which simplifies to
$$S_n \leq\sum_{p=0}^{n-1}{k_pe^{-rp}},$$ and thus by what we assumed on $S$,
$$S_n \leq C\sum_{p=0}^{n-1}{(p+1)^de^{-rp}},$$
and the last sum is convergent, hence the conclusion.
