Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

How does one use Euler Maclaurin to compute asymptotics for sums like $$ \sum_{\substack{n\le x \\ (n,q)=1}} \frac{1}{\sqrt{n}} \quad \text{or} \quad \sum_{\substack{n\le x \\ (n,q)=1}} \frac{\log n}{\sqrt{n}}?$$

share|cite|improve this question
up vote 7 down vote accepted

You can get asymptotics using Abel summation (see Tenenbaum's Introduction to Analytic and Probabilistic Number Theory, section 1.0).

We can let $b(x)=\frac{1}{\sqrt{x}}$ and define $a_n$ to be $1$ if $(n,q)=1$ and 0 otherwise. Then $$ \sum_{\substack{n\le x \\ (n,q)=1}} \frac{1}{\sqrt{n}} =\sum_{n \le x} a_n b(n) =A(x)b(x) - \int_1^x A(t) b'(t) \, dt = \frac{A(x)}{\sqrt{x}} + \frac{1}{2} \int_1^x A(t) t^{-3/2} \, dt $$ where $$ A(x) = \sum_{n \le x} a_n = \frac{x}{q} \phi(q) + O(\phi(q)).$$ From this, we can determine that $$\sum_{\substack{n\le x \\ (n,q)=1}} \frac{1}{\sqrt{n}} = 2 \sqrt{x} \frac{\phi(q)}{q} + O( \phi(q) ). $$ I am sure better bounds on the error terms are possible, but this might be good enough for what you want to do with it.

share|cite|improve this answer

We can actually get an additional term using the Wiener-Ikehara theorem.

Introduce the Dirichlet Series $A(s)$ whose terms are given by the indicator $(n, q) =1$ times $1/\sqrt{n}$. We have $$ A(s) = \sum_{(n,q)=1} \frac{1/\sqrt{n}}{n^s} = \sum_{(n,q)=1} \frac{1}{n^{s+\frac{1}{2}}} = \prod_{p\nmid q} \frac{1}{1-\frac{1}{p^{s+\frac{1}{2}}}} = \zeta\left(s+\frac{1}{2}\right) \prod_{p\mid q} \left(1-\frac{1}{p^{s+\frac{1}{2}}} \right),$$ where $p$ ranges over the primes. Furthermore, introduce $$ B(s) = A(s) - \zeta\left(\frac{1}{2}\right) \prod_{p\mid q} \left(1-\frac{1}{\sqrt{p}}\right)$$ This Dirichlet series differs from $A(s)$ in its constant term and converges in $\mathfrak{R}(s) \ge \frac{1}{2}.$ It has a simple pole at $\frac{1}{2}$ and is zero at $s=0.$ Wiener-Ikehara applies to $B(s)$, giving

$$\sum_{k\le n,(k,n)=1} \frac{1}{\sqrt{k}} - \zeta\left(\frac{1}{2}\right) \prod_{p\mid q} \left(1-\frac{1}{\sqrt{p}}\right) \sim \prod_{p\mid q} \left(1-\frac{1}{p}\right) \frac{\sqrt{n}}{1/2} = 2 \frac{\phi(q)}{q} \sqrt{n}.$$ We construct the zero at $s=0$ because we are actually working with the Mellin-Perron type integral $$\int_{1-i\infty}^{1+i\infty} B(s) n^s \frac{ds}{s}$$ and need to cancel the pole at $s=0$.

The conclusion is that $$ \sum_{k\le n,(k,n)=1} \frac{1}{\sqrt{k}} \sim 2 \frac{\phi(q)}{q} \sqrt{n} + \zeta\left(\frac{1}{2}\right) \prod_{p\mid q} \left(1-\frac{1}{\sqrt{p}}\right)$$ The numerics of this approximation are excellent even for small values of $n$.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.