How to do partial summation?

228 Views Asked by At

I don't understand the following step in a proof:

gcd(k,l)=1. Then we have the following formula (p is a prime number):

$\sum_{p\leq x, p\equiv l( k)}{\frac{log^2(p)}{p}}\leq \frac{1}{\phi(k)}log^2(x)+O(log(x))$

This is a formula I already know. Then the one who wrote the proof says that from this "we easily find, by partial summation:"

$\sum_{p\leq x, p\equiv l( k)}{\frac{log(p)}{p}}\leq \frac{2}{\phi(k)}log(x)+O(log(log(x)))$

I know that normally "partial summation" means that I should use this formula here. Unfortunately it didn't work.

1

There are 1 best solutions below

4
On BEST ANSWER

As they say, this follows by summation by parts. $\DeclareMathOperator{\llog}{llog} %ignore my preamble :)$

We start with

$$ \sum_{\substack{p \leq x \\ p \equiv l\, \bmod k}}\frac{\log p}{p} = \sum \frac{\log p}{p} \cdot 1,$$

where I notate the $1$ so that we see what our two summation terms are. Thinking of summation by parts as integration by parts $\displaystyle\int fdg = fg - \int gdf$ (which is how I always think about it), then let us think of $\frac{\log x}{x}$ as our $f$ and the indicator function on primes congruent to $l \bmod k$ as $dg$ (so it's $1$ and is what makes the support of the sum the way it is). This has the benefit of leaving $f$ as a differentiable function, which means we can actually treat the right hand side of the summation by parts as an integral.

With our choices of $f$ and $dg$, we should ask ourselves what $\displaystyle \int_1^x dg = g(x)$ is. $dg$ is $1$ on those primes congruent to $l \bmod k$ up to $x$. There are on the order of $\frac{x}{\varphi(k)}$ of these terms (which this becoming an asymptotic as $x \to \infty$, Dirichlet's Theorem on Primes in Arithmetic Progressions), so $g(x) = \dfrac{x}{\varphi(k)}$ as $x \to \infty$. One might be safe and say that there are always (for $x > 100$, say) fewer than $\dfrac{2x}{\varphi(x)}$, and at least $\dfrac{x}{2\varphi(x)}$, so that one doesn't have to keep track of asymptotics. Integrating by parts then gives us that

$$\begin{align} \sum_{\substack{p \leq x \\ p \equiv l\, \bmod k}}\frac{\log p}{p}\cdot 1 &\leq \frac{\log x}{x}\frac{2x}{\varphi(x)} - \int_1^x \frac{y}{2\varphi(k)}\frac{1 - \log y}{y^2}\mathrm{d}y \\ &\leq \frac{2\log x}{\varphi(k)} + \int_1^x\frac{\log y}{2\varphi(k)y}\mathrm{d}y - \int_1^x \frac{1}{2\varphi(k)y}\mathrm{d}y \\ &\leq \frac{2\log x}{\varphi(k)} + O(\mathop{\llog x)}, \end{align}$$

where the $2$ is very kind.