Dirichlet hyperbola method

In <a href="/facts/Number_theory/zhoa7zrc">number theory</a>, the Dirichlet hyperbola method is a technique to evaluate the sum

F
        (
        n
        )
        =
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        f
        (
        k
        )
        ,
      
    
    {\displaystyle F(n)=\sum _{k=1}^{n}f(k),}

where f is a <a href="/facts/Multiplicative_function/4kfolbBl">multiplicative function</a>. The first step is to find a pair of multiplicative functions g and h such that, using <a href="/facts/Dirichlet_convolution/DjuhDu1L">Dirichlet convolution</a>, we have f = g ∗ h; the sum then becomes

F
        (
        n
        )
        =
        
          ∑
          
            k
            =
            1
          
          
            n
          
        
        
          ∑
          
            x
            y
            =
            k

g
        (
        x
        )
        h
        (
        y
        )
        ,
      
    
    {\displaystyle F(n)=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y),}

where the inner sum runs over all ordered pairs (x,y) of positive <a href="/facts/Integers/PUwwrawx">integers</a> such that xy = k. In the <a href="/facts/Cartesian_plane/lkTqvMmB">Cartesian plane</a>, these pairs lie on a <a href="/facts/Hyperbola/6R6ER0mY">hyperbola</a>, and when the double sum is fully expanded, there is a <a href="/facts/Bijection/j4gTuTmW">bijection</a> between the terms of the sum and the <a href="/facts/Lattice_points/2ls9Iv9N">lattice points</a> in the first quadrant on the hyperbolas of the form xy = k, where k runs over the integers 1 ≤ k ≤ n: for each such point (x,y), the sum contains a term g(x)h(y), and vice versa.
Let a be a real number, not necessarily an integer, such that 1 < a < n, and let b = n/a. Then the lattice points can be split into three overlapping regions: one region is bounded by 1 ≤ x ≤ a and 1 ≤ y ≤ n/x, another region is bounded by 1 ≤ y ≤ b and 1 ≤ x ≤ n/y, and the third is bounded by 1 ≤ x ≤ a and 1 ≤ y ≤ b. In the diagram, the first region is the <a href="/facts/Union_(set_theory)/KVVXKfWl">union</a> 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 <a href="/facts/Intersection_(set_theory)/RPfUNJh9">intersection</a> of the first two regions. By the <a href="/facts/Principle_of_inclusion_and_exclusion/YsA7T8CL">principle of inclusion and exclusion</a>, 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

<table><tbody><tr><td> F ( n ) = ∑ k = 1 n f ( k ) = ∑ k = 1 n ∑ x y = k g ( x ) h ( y ) = ∑ x = 1 a ∑ y = 1 n / x g ( x ) h ( y ) + ∑ y = 1 b ∑ x = 1 n / y g ( x ) h ( y ) − ∑ x = 1 a ∑ y = 1 b g ( x ) h ( y ) . {\displaystyle {\begin{aligned}F(n)&=\sum _{k=1}^{n}f(k)\\&=\sum _{k=1}^{n}\sum _{xy=k}^{}g(x)h(y)\\&=\sum _{x=1}^{a}\sum _{y=1}^{n/x}g(x)h(y)+\sum _{y=1}^{b}\sum _{x=1}^{n/y}g(x)h(y)-\sum _{x=1}^{a}\sum _{y=1}^{b}g(x)h(y){\text{.}}\end{aligned}}} </td> <td></td> <td>1</td></tr></tbody></table>

Dirichlet hyperbola method open-in-new

Dirichlet hyperbola method