Divisor summatory function

The divisor summatory function is defined as

${\displaystyle D(x)=\sum _{n\leq x}d(n)=\sum _{j,k \atop jk\leq x}1}$

where

${\displaystyle d(n)=\sigma _{0}(n)=\sum _{j,k \atop jk=n}1}$

is the divisor function. The divisor function counts the number of ways that the integer n can be written as a product of two integers. More generally, one defines

${\displaystyle D_{k}(x)=\sum _{n\leq x}d_{k}(n)=\sum _{m\leq x}\sum _{mn\leq x}d_{k-1}(n)}$

where d_k(n) counts the number of ways that n can be written as a product of k numbers. This quantity can be visualized as the count of the number of lattice points fenced off by a hyperbolic surface in k dimensions. Thus, for k=2, D(x) = D₂(x) counts the number of points on a square lattice bounded on the left by the vertical-axis, on the bottom by the horizontal-axis, and to the upper-right by the hyperbola jk = x. Roughly, this shape may be envisioned as a hyperbolic simplex. This allows us to provide an alternative expression for D(x), and a simple way to compute it in ${\displaystyle O({\sqrt {x}})}$ time:

${\displaystyle D(x)=\sum _{k=1}^{x}\left\lfloor {\frac {x}{k}}\right\rfloor =2\sum _{k=1}^{u}\left\lfloor {\frac {x}{k}}\right\rfloor -u^{2}}$, where ${\displaystyle u=\left\lfloor {\sqrt {x}}\right\rfloor }$

If the hyperbola in this context is replaced by a circle then determining the value of the resulting function is known as the Gauss circle problem.

Sequence of D(n)(sequence A006218 in the OEIS):
0, 1, 3, 5, 8, 10, 14, 16, 20, 23, 27, 29, 35, 37, 41, 45, 50, 52, 58, 60, 66, 70, 74, 76, 84, 87, 91, 95, 101, 103, 111, ...

Finding a closed form for this summed expression seems to be beyond the techniques available, but it is possible to give approximations. The leading behavior of the series is given by

${\displaystyle D(x)=x\log x+x(2\gamma -1)+\Delta (x)\ }$

where ${\displaystyle \gamma }$ is the Euler–Mascheroni constant, and the error term is

${\displaystyle \Delta (x)=O\left({\sqrt {x}}\right).}$

Here, ${\displaystyle O}$ denotes Big-O notation. This estimate can be proven using the Dirichlet hyperbola method, and was first established by Dirichlet in 1849.[1]^{: 37–38, 69} The Dirichlet divisor problem, precisely stated, is to improve this error bound by finding the smallest value of ${\displaystyle \theta }$ for which

${\displaystyle \Delta (x)=O\left(x^{\theta +\epsilon }\right)}$

holds true for all ${\displaystyle \epsilon >0}$. As of today, this problem remains unsolved. Progress has been slow. Many of the same methods work for this problem and for Gauss's circle problem, another lattice-point counting problem. Section F1 of Unsolved Problems in Number Theory [2] surveys what is known and not known about these problems.

• In 1904, G. Voronoi proved that the error term can be improved to ${\displaystyle O(x^{1/3}\log x).}$ [3]^: 381
• In 1916, G. H. Hardy showed that ${\displaystyle \inf \theta \geq 1/4}$. In particular, he demonstrated that for some constant ${\displaystyle K}$, there exist values of x for which ${\displaystyle \Delta (x)>Kx^{1/4}}$ and values of x for which ${\displaystyle \Delta (x)<-Kx^{1/4}}$.[1]^: 69
• In 1922, J. van der Corput improved Dirichlet's bound to ${\displaystyle \inf \theta \leq 33/100=0.33}$.[3]^: 381
• In 1928, J. van der Corput proved that ${\displaystyle \inf \theta \leq 27/82=0.3{\overline {29268}}}$.[3]^: 381
• In 1950, Chih Tsung-tao and independently in 1953 H. E. Richert proved that ${\displaystyle \inf \theta \leq 15/46=0.32608695652...}$.[3]^: 381
• In 1969, Grigori Kolesnik demonstrated that ${\displaystyle \inf \theta \leq 12/37=0.{\overline {324}}}$.[3]^: 381
• In 1973, Grigori Kolesnik demonstrated that ${\displaystyle \inf \theta \leq 346/1067=0.32427366448...}$.[3]^: 381
• In 1982, Grigori Kolesnik demonstrated that ${\displaystyle \inf \theta \leq 35/108=0.32{\overline {407}}}$.[3]^: 381
• In 1988, H. Iwaniec and C. J. Mozzochi proved that ${\displaystyle \inf \theta \leq 7/22=0.3{\overline {18}}}$.[4]
• In 2003, M.N. Huxley improved this to show that ${\displaystyle \inf \theta \leq 131/416=0.31490384615...}$.[5]

So, ${\displaystyle \inf \theta }$ lies somewhere between 1/4 and 131/416 (approx. 0.3149); it is widely conjectured to be 1/4. Theoretical evidence lends credence to this conjecture, since ${\displaystyle \Delta (x)/x^{1/4}}$ has a (non-Gaussian) limiting distribution.[6] The value of 1/4 would also follow from a conjecture on exponent pairs.[7]

In the generalized case, one has

${\displaystyle D_{k}(x)=xP_{k}(\log x)+\Delta _{k}(x)\,}$

where ${\displaystyle P_{k}}$ is a polynomial of degree ${\displaystyle k-1}$. Using simple estimates, it is readily shown that

${\displaystyle \Delta _{k}(x)=O\left(x^{1-1/k}\log ^{k-2}x\right)}$

for integer ${\displaystyle k\geq 2}$. As in the ${\displaystyle k=2}$ case, the infimum of the bound is not known for any value of ${\displaystyle k}$. Computing these infima is known as the Piltz divisor problem, after the name of the German mathematician Adolf Piltz (also see his German page). Defining the order ${\displaystyle \alpha _{k}}$ as the smallest value for which ${\displaystyle \Delta _{k}(x)=O\left(x^{\alpha _{k}+\varepsilon }\right)}$ holds, for any ${\displaystyle \varepsilon >0}$, one has the following results (note that ${\displaystyle \alpha _{2}}$ is the ${\displaystyle \theta }$ of the previous section):

${\displaystyle \alpha _{2}\leq {\frac {131}{416}}\ ,}$[5]

${\displaystyle \alpha _{3}\leq {\frac {43}{96}}\ ,}$[8] and[9]

${\displaystyle {\begin{aligned}\alpha _{k}&\leq {\frac {3k-4}{4k}}\quad (4\leq k\leq 8)\\[6pt]\alpha _{9}&\leq {\frac {35}{54}}\ ,\quad \alpha _{10}\leq {\frac {41}{60}}\ ,\quad \alpha _{11}\leq {\frac {7}{10}}\\[6pt]\alpha _{k}&\leq {\frac {k-2}{k+2}}\quad (12\leq k\leq 25)\\[6pt]\alpha _{k}&\leq {\frac {k-1}{k+4}}\quad (26\leq k\leq 50)\\[6pt]\alpha _{k}&\leq {\frac {31k-98}{32k}}\quad (51\leq k\leq 57)\\[6pt]\alpha _{k}&\leq {\frac {7k-34}{7k}}\quad (k\geq 58)\end{aligned}}}$

• E. C. Titchmarsh conjectures that ${\displaystyle \alpha _{k}={\frac {k-1}{2k}}\ .}$

Both portions may be expressed as Mellin transforms:

${\displaystyle D(x)={\frac {1}{2\pi i}}\int _{c-i\infty }^{c+i\infty }\zeta ^{2}(w){\frac {x^{w}}{w}}\,dw}$

for ${\displaystyle c>1}$. Here, ${\displaystyle \zeta (s)}$ is the Riemann zeta function. Similarly, one has

${\displaystyle \Delta (x)={\frac {1}{2\pi i}}\int _{c^{\prime }-i\infty }^{c^{\prime }+i\infty }\zeta ^{2}(w){\frac {x^{w}}{w}}\,dw}$

with ${\displaystyle 0<c^{\prime }<1}$. The leading term of ${\displaystyle D(x)}$ is obtained by shifting the contour past the double pole at ${\displaystyle w=1}$: the leading term is just the residue, by Cauchy's integral formula. In general, one has

${\displaystyle D_{k}(x)={\frac {1}{2\pi i}}\int _{c-i\infty }^{c+i\infty }\zeta ^{k}(w){\frac {x^{w}}{w}}\,dw}$

and likewise for ${\displaystyle \Delta _{k}(x)}$, for ${\displaystyle k\geq 2}$.

• H.M. Edwards, Riemann's Zeta Function, (1974) Dover Publications, ISBN 0-486-41740-9
• E. C. Titchmarsh, The theory of the Riemann Zeta-Function, (1951) Oxford at the Clarendon Press, Oxford. (See chapter 12 for a discussion of the generalized divisor problem)
• Apostol, Tom M. (1976), Introduction to analytic number theory, Undergraduate Texts in Mathematics, New York-Heidelberg: Springer-Verlag, ISBN 978-0-387-90163-3, MR 0434929, Zbl 0335.10001 (Provides an introductory statement of the Dirichlet divisor problem.)
• H. E. Rose. A Course in Number Theory., Oxford, 1988.
• M.N. Huxley (2003) 'Exponential Sums and Lattice Points III', Proc. London Math. Soc. (3)87: 591–609