Dirichlet hyperbola method

In number theory, the Dirichlet hyperbola method is a technique to evaluate the sum : F(n) = \sum_{k=1}^n f(k) .

Uses your system voice; voice and rate in settings.

Snapshot

≈ 5 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In number theory, the Dirichlet hyperbola method is a technique to evaluate the sum : F(n) = \sum_{k=1}^n f(k) . The first step is to find a pair of functions and such that, using Dirichlet convolution, we have ; the sum then becomes : F(n) = \sum_{k=1}^n \sum_{xy=k}^{} g(x) h(y), where the inner sum runs over all ordered pairs of positive integers such that . In the Cartesian plane, these pairs lie on a hyperbola, and when the double sum is fully expanded, there is a bijection between the terms of the sum and the lattice points in the first quadrant on the hyperbolas of the form , where runs over the integers : for each such point , the sum contains a term , and vice versa.

Let be a real number, not necessarily an integer, such that , and let . Then the lattice points can be split into three overlapping regions: one region is bounded by and , another region is bounded by and , and the third is bounded by and .

In the diagram, the first region is the union of the blue and red regions, the second region is the union of the red and green, and the third region is the red. Note that this third region is the intersection of the first two regions.

By the principle of inclusion and exclusion, the full sum is therefore the sum over the first region, plus the sum over the second region, minus the sum over the third region. This yields the formula

In number theory, the Dirichlet hyperbola method is a technique to evaluate the sum F(n) = \sum_{k=1}^n f(k) . The first step is to find a pair of functions and such that, using Dirichlet convolution, we have ; the sum then becomes F(n) = \sum_{k=1}^n \sum_{xy=k}^{} g(x) h(y), where the inner sum runs over all ordered pairs of positive integers such that . In the Cartesian plane, these pairs lie on a hyperbola, and when the double sum is fully expanded, there is a bijection between the terms of the sum and the lattice points in the first quadrant on the hyperbolas of the form , where runs over the integers : for each such point , the sum contains a term , and vice versa.

Let be a real number, not necessarily an integer, such that , and let . Then the lattice points can be split into three overlapping regions: one region is bounded by and , another region is bounded by and , and the third is bounded by and .

In the diagram, the first region is the union of the blue and red regions, the second region is the union of the red and green, and the third region is the red. Note that this third region is the intersection of the first two regions.

By the principle of inclusion and exclusion, the full sum is therefore the sum over the first region, plus the sum over the second region, minus the sum over the third region. This yields the formula D(n) = \sum_{k=1}^n \sigma_0(k). Computing naïvely requires factoring every integer in the interval ; an improvement can be made by using a modified Sieve of Eratosthenes, but this still requires time.

Since admits the Dirichlet convolution , taking in ( ) yields the formula D(n) = \sum_{x=1}^{\sqrt{n}} \sum_{y=1}^{n/x} 1 \cdot 1 + \sum_{y=1}^{\sqrt{n}} \sum_{x=1}^{n/y} 1 \cdot 1 - \sum_{x=1}^{\sqrt{n}} \sum_{y=1}^{\sqrt{n}} 1 \cdot 1, which simplifies to D(n) = 2 \cdot \sum_{x=1}^{\sqrt{n}} \left\lfloor \frac{n}{x} \right\rfloor - \left\lfloor \sqrt{n} \right\rfloor^2, which can be evaluated in operations. The method also has theoretical applications: for example, Peter Gustav Lejeune Dirichlet introduced the technique in 1849 to obtain the estimate D(n) = n \log n + (2\gamma - 1)n + O(\sqrt{n}), where is the Euler–Mascheroni constant.

Text derived from https://en.wikipedia.org/w/index.php?oldid=1361608369 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001361608369 · captured 1782687640.0 · version history

Cite this page as: encyclopegia.org, “Dirichlet hyperbola method”, snapshot enwiki-001361608369. https://encyclopegia.org/a/dirichlet-hyperbola-method

Sources cited in this revision

2 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.