PlanetMath (more info)
 Math for the people, by the people. Sponsor PlanetMath
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Owner confidence rating: Very high Entry average rating: No information on entry rating
Dirichlet hyperbola method (Definition)

Let $f$ $g$ and $h$ be multiplicative functions such that $f=g*h$ where $*$ denotes the convolution of $g$ and $h$ The Dirichlet hyperbola method (typically shortened to hyperbola method) is a way to calculate $\displaystyle \sum_{n \le x} f(n)$ by using the fact that $f=g*h$

$$\sum_{n \le x} f(n) = \sum_{n \le x} \sum_{ab=n} g(a)h(b) = \sum_{a \le \sqrt{x}} \sum_{b \le \frac{x}{a}} g(a)h(b) + \sum_{b \le \sqrt{x}} \sum_{a \le \frac{x}{b}} g(a)h(b) - \sum_{a \le \sqrt{x}} \sum_{b \le \sqrt{x}} g(a)h(b)$$

Note that, since $ab=n \le x$ not both of $a$ and $b$ can be larger than $\sqrt{x}$ The Dirichlet hyperbola method follows from this fact as well as the inclusion-exclusion principle.

This method for calculating $\displaystyle \sum_{n \le x} f(n)$ is advantageous when the sums in terms of $g$ and $h$ are easier to handle and when $|g(n)-h(n)|$ is relatively small for most $n \in \mathbb{N}$

As an example, the sum $\displaystyle \sum_{n \le x} \tau(n)$ will be calculated using the Dirichlet hyperbola method.

Note that $\tau=1*1$ Thus:

$\begin{array}{ll} \displaystyle \sum_{n \le x} \tau(n) & \displaystyle = \sum_{a \le \sqrt{x}} \sum_{b \le \frac{x}{a}} 1 + \sum_{b \le \sqrt{x}} \sum_{a \le \frac{x}{b}} 1 - \sum_{a \le \sqrt{x}} \sum_{b \le \sqrt{x}} 1 \\ & \\ & \displaystyle = \sum_{a \le \sqrt{x}} \left( \frac{x}{a} + O(1) \right) + \sum_{b \le \sqrt{x}} \left( \frac{x}{b} + O(1) \right) - \left( \sum_{a \le \sqrt{x}} 1 \right) \left( \sum_{b \le \sqrt{x}} 1 \right) \\ & \\ & \displaystyle = 2 \sum_{c \le \sqrt{x}} \left( \frac{x}{c} + O(1) \right) - \left( \sum_{c \le \sqrt{x}} 1 \right)^2 \\ & \\ & \displaystyle = 2x \sum_{c \le \sqrt{x}} \frac{1}{c} + O \left( \sum_{c \le \sqrt{x}} 1 \right) - (\sqrt{x}+O(1))^2 \\ & \\ & \displaystyle = 2x \left( \log \sqrt{x} + \gamma + O \left( \frac{1}{\sqrt{x}} \right) \right) + O(\sqrt{x}) - \left( x + O(\sqrt{x}) + O(1) \right) \\ & \\ & \displaystyle = 2x \left( \frac{1}{2} \log x + \gamma + O \left( \frac{1}{\sqrt{x}} \right) \right) - x + O(\sqrt{x}) \\ & \\ & \displaystyle = x \log x + 2 \gamma x + O \left( \frac{x}{\sqrt{x}} \right) - x + O(\sqrt{x}) \\ & \\ & \displaystyle = x \log x + (2 \gamma - 1)x + O(\sqrt{x}) \end{array}$




"Dirichlet hyperbola method" is owned by Wkbj79.
(view preamble | get metadata)

View style:

See Also: convolution method, $\tau$ function, Euler's constant

Other names:  hyperbola method
Log in to rate this entry.
(view current ratings)

Cross-references: sums, inclusion-exclusion principle, multiplicative functions
There are 2 references to this entry.

This is version 11 of Dirichlet hyperbola method, born on 2006-06-10, modified 2007-06-28.
Object id is 7990, canonical name is DirichletHyperbolaMethod.
Accessed 2832 times total.

Classification:
AMS MSC11N37 (Number theory :: Multiplicative number theory :: Asymptotic results on arithmetic functions)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
post | correct | update request | add derivation | add example | add (any)