Dirichlet hyperbola method

A pdf version is Dirichlet hyperbola method.

1. Introduction

Theorem 1

$\displaystyle \sum_{1\leq n\leq x}d(n)=\sum_{1\leq n\leq x}[\frac{x}{n}]=xlogx+(2\gamma-1) x+O(\sqrt{x}) \ \ \ \ \ (1)&fg=000000$

Remark 1 I thought this problem initial 5 years ago, cost me several days to find a answer, I definitely get something without the argument of Dirchlet hyperbola method and which is weaker but morally the same camparable with the result get by Dirichlet hyperbola method.

Remark 2 How to get the formula:

$\displaystyle \sum_{1\leq n\leq x}d(x)=\sum_{1\leq n\leq x}[\frac{x}{n}]? \ \ \ \ \ (2)&fg=000000$

In fact,

$\displaystyle \sum_{1\leq n\leq x}d(x)=\sum_{1\leq ab\leq x}1=\sum_{1\leq n\leq x}[\frac{x}{n}]\ \ \ \ \ (3)&fg=000000$

Which is the integer lattices under or lying on the hyperbola $latex {\{(a,b)|ab=x\}}&fg=000000$.

Remark 3 By trivial argument, we can bound the quantity as following way,

$\displaystyle \begin{array}{rcl} \sum_{1\leq n\leq x}[\frac{x}{n}] & = & \sum_{1\leq ab\leq x}1\\ & = & x\sum_{i=1}^x\frac{1}{i}-\sum_{i=1}^x\{\frac{x}{i}\}\\ & = &xlnx+\gamma x+O(x) \end{array} &fg=000000$

The error term is $latex {O(x)}&fg=000000$, which is too big. But fortunately we can use the symmetry of hyperbola to improve the error term.

Proof:

$\displaystyle \begin{array}{rcl} \sum_{1\leq n\leq x}d(n) & = & \sum_{ab\leq x}1\\ & = & \sum_{a\geq \sqrt{x}}[\frac{x}{b}]+\sum_{b\geq \sqrt{x}}[\frac{x}{a}]-\sum_{1\leq a,b\leq \sqrt{x}}1\\ & = & xlogx+(2\gamma-1)x+O(\sqrt{x}) \end{array} &fg=000000$

$latex \Box&fg=000000$

Theorem 2

Given a natural number k, use the hyperbola method together
with induction and partial summation to show that

$\displaystyle \sum_{n\leq x}d_k(n) = xP_k(log x) + O(x^{1-\frac{1}{k}+\epsilon}), n\leq x \ \ \ \ \ (4)&fg=000000$

where $latex {P_k(t)}&fg=000000$ denotes a polynomial of degree $latex {k-1}&fg=000000$ with leading term $latex {\frac{t^{k-1}}{(k-1)!}}&fg=000000$.

Remark 4 $l{P_k(x)}&fg=000000$ is the residue of $latex {\zeta(s)^kx^ss^{-1}}&fg=000000$ at $latex {s=1}&fg=000000$.

Proof:

We can establish the dimension 3 case directly, which is the following asymptotic formula,

$\displaystyle \sum_{1\leq xy\leq n}[\frac{n}{xy}]=xP_2(logx)+O(x^{1-\frac{1}{3}+\epsilon}) \ \ \ \ \ (5)&fg=000000$

The approach is following, we first observe that

$\displaystyle \sum_{1\leq xy\leq n}[\frac{n}{xy}]=\sum_{xyz\leq n}1 \ \ \ \ \ (6)&fg=000000$

The problem transform to get a asymptotic formula for the lattices under 3 dimension hyperbola. The first key point is, morally $latex {([n^{\frac{1}{3}}],[n^{\frac{1}{3}}],[n^{\frac{1}{3}}])}&fg=000000$ is the central point under the hyperbola.

Then we can divide the range into 3 parts, and try to get a asymptotic formula for each part then add them together. Assume we have:

  1. $ {A_x=\sum_{1\leq r\leq [n^{\frac{1}{3}}]}\sum_{1\leq yz\leq [n^{\frac{2}{3}}]}[\frac{r}{yz}]}&fg=000000$.
  2. ${A_y=\sum_{1\leq r\leq [n^{\frac{1}{3}}]}\sum_{1\leq xz\leq [n^{\frac{2}{3}}]}[\frac{r}{yz}]}&fg=000000$.
  3. ${A_z=\sum_{1\leq r\leq [n^{\frac{1}{3}}]}\sum_{1\leq xy\leq [n^{\frac{2}{3}}]}[\frac{r}{yz}]}&fg=000000$.

Then the task transform to get a asymptotic formula,

$latex \displaystyle A_x=A_y=A_z=xQ_2(logx)+O(x^{1-\frac{1}{3}+\epsilon}) \ \ \ \ \ (7)&fg=000000$

But we can do the same thing for $latex {\sum_{1\leq yz\leq [n^{\frac{2}{3}}]}[\frac{r}{yz}]}&fg=000000$ and then integral it. This end the proof. For general $latex {k\in {\mathbb N}}&fg=000000$, the story is the same, by induction.

Induction on $latex {k}&fg=000000$ and use the Fubini theorem to calculate $latex {\sum_{x_1…x_r\leq n}\frac{n}{x_1…x_r},\forall 1\leq r\leq k}&fg=000000$. $latex \Box&fg=000000$

There is a major unsolved problem called Dirichlet divisor problem.

$latex \displaystyle \sum_{n\leq x}d(n) \ \ \ \ \ (8)&fg=000000$

What is the error term? The conjecture is the error term is $latex {O(x^{\theta}), \forall \theta>\frac{1}{4}}&fg=000000$, it is known that $latex {\theta=\frac{1}{4}}&fg=000000$ is not right.

Remark 5

To beats this problem, need some tools in algebraic geometry.

2. Several problems

$latex {\forall k\in {\mathbb N}}&fg=000000$, is there a asymptotic formula for $latex {\sum_{t=1}^n\{\frac{kn}{t}\}}&fg=000000$ ?

$latex {\forall k\in {\mathbb N}}&fg=000000$, $latex {f(n)}&fg=000000$ is a polynomial with degree $latex {k}&fg=000000$, is there a asymptotic formula for $latex {\sum_{t=1}^n\{\frac{f(n)}{t}\}}&fg=000000$ ?

$latex {\forall k\in {\mathbb N}}&fg=000000$, $latex {g(n)}&fg=000000$ is a polynomial with degree $latex {k}&fg=000000$, is there a asymptotic formula for $latex {\sum_{t=1}^n\{\frac{n}{g(t)}\}}&fg=000000$ ?

Theorem 3 $latex {k\in {\mathbb N}}&fg=000000$, then we have

$latex \displaystyle \lim_{n\rightarrow \infty}\frac{\{\frac{kn}{1}\}+\{\frac{kn}{2}\}+…+\{\frac{kn}{n}\}}{n}=k(\sum_{i=1}^k\frac{1}{i}-lnk-\gamma) \ \ \ \ \ (9)&fg=000000$

Proof:

$latex \displaystyle \begin{array}{rcl} \frac{\{\frac{kn}{1}\}+\{\frac{kn}{2}\}+…+\{\frac{kn}{n}\}}{n} & = & \frac{\sum_{i=1}^k\frac{kn}{i}-\sum_{i=1}^n[\frac{kn}{i}]}{n}\\ & = & k(lnn+\gamma +\epsilon_n)-\frac{\sum_{i=1}^{kn}[\frac{kn}{i}]-\sum_{i=n+1}^{kn}[\frac{kn}{i}]}{n} \end{array} &fg=000000$

$latex \Box&fg=000000$

Now we try to estimate

$latex \displaystyle S_k(n)=\sum_{i=1}^{kn}[\frac{kn}{i}]-\sum_{i=n+1}^{kn}[\frac{kn}{i}] \ \ \ \ \ (10)&fg=000000$

In fact, we have,

$latex \displaystyle \begin{array}{rcl} S_k(n) & = & (2\sum_{i=1}^{[\sqrt{kn}]}[\frac{kn}{i}]-[\sqrt{kn}]^2)-(\sum_{i=1}^k[\frac{kn}{i}]-kn)\\ & = & 2\sum_{i=1}^{[\sqrt{kn}]}\frac{kn}{i}-\sum_{i=1}^k\frac{kn}{i}+2\{\sqrt{kn}\}[\sqrt{kn}]+\{\sqrt{kn}\}^2-2\sum_{i=1}^{[\sqrt{kn}]}\{\frac{kn}{i}\}+\sum_{i=1}^k\{\frac{kn}{i}\}\\ & = & 2kn(ln[\sqrt{kn}]+\gamma+\epsilon_{[\sqrt{kn}]})-kn\sum_{i=1}^k\frac{1}{i}+r(n)\\ & = & knln(kn)+kn(2\gamma-\sum_{i=1}^k\frac{1}{i})+r'(n)\\ & = & knln n+kn(2\gamma+lnk-\sum_{i=1}^k\frac{1}{i})+r'(n) \end{array} &fg=000000$

Where $latex {-3\sqrt{n}<r(n)<3\sqrt{n}}&fg=000000$, $latex {-3\sqrt{n}<r'(n)<3\sqrt{n}}&fg=000000$.

So by 1 we know,

$latex \displaystyle \begin{array}{rcl} \frac{\{\frac{kn}{1}\}+…+\{\frac{kn}{n}\}}{n} & = & k(lnn+\gamma+\epsilon_n)-klnn-k(2\gamma+lnk-\sum_{i=1}^k\frac{1}{i})+\frac{r'(n)}{n}\\ & = & k(\sum_{i=1}^k\frac{1}{i}-lnk-\gamma)+\frac{r'(n)}{n}+k\epsilon_n \end{array} &fg=000000$

So we have,

$latex \displaystyle \lim_{n\rightarrow \infty}\frac{\{\frac{kn}{1}\}+…+\{\frac{kn}{n}\}}{n} =k(\sum_{i=1}^k\frac{1}{i}-lnk-\gamma)=k\epsilon_k \ \ \ \ \ (11)&fg=000000$

Remark 6 In fact we can get $latex {0<k\epsilon_k<\frac{1}{2}, \forall k\in {\mathbb N}}&fg=000000$, by combining the theorem 3 and 1.

3. Lattice points in ball

Gauss use the cube packing circle get a rough estimate,

$latex \displaystyle \sum_{n\leq x}r_2(n)=\pi x+O(\sqrt{x}) \ \ \ \ \ (12)&fg=000000$

In the same way one can obtain,

$latex \displaystyle \sum_{n\leq x}r_k(n)=\rho_kx^{\frac{k}{2}}+O(x^{\frac{k-1}{2}}) \ \ \ \ \ (13)&fg=000000$

Remark 7 Where $latex {\rho_k=\frac{\pi^{\frac{k}{2}}}{\Gamma(\frac{k}{2}+1)}}&fg=000000$ is the volume of the unit ball in $latex {k}&fg=000000$ dimension.

Dirchlet’s hyperbola method works nicely for the lattic points in a ball of dimension $latex {k\geq 4}&fg=000000$. Langrange proved that every natural number can be represented as the sum of four squares, i.e. $latex {r_4(n)>0}&fg=000000$, and Jacobi established the exact formula for the number of representations

$latex \displaystyle r_4(n)=8(2+(-1)^n)\sum_{d|n,d\ odd}d. \ \ \ \ \ (14)&fg=000000$

Hence we derive,

$latex \displaystyle \begin{array}{rcl} \sum_{n\leq x}r_4(n) & = & 8\sum_{m\leq x}(2+(-1)^m)\sum_{dm\leq x, d\ odd}d\\ & = & 8\sum_{m\leq x}(2+(-1)^m)(\frac{x^2}{4m^2}+O(\frac{x}{m}))\\ & = & 2x^2\sum_1^{\infty}(2+(-1)^m)m^{-2}+O(xlogx)\\ & = & 3\zeta(2)x^2+O(xlogx) = \frac{1}{2}(\pi x)^2+O(xlogx) \end{array} &fg=000000$

This result extend easily for any $latex {k\geq 4}&fg=000000$, write $latex {r_k}&fg=000000$ as the additive convolution of $latex {r_4}&fg=000000$ and $latex {r_{k-4}}&fg=000000$, i.e.

$latex \displaystyle r_k(n)=\sum_{0\leq t\leq n}r_4(t)r_{k-4}(n-t) \ \ \ \ \ (15)&fg=000000$

Apply the above result for $latex {r_4}&fg=000000$ and execute the summation over the remaining $latex {k-4}&fg=000000$ squares by integration.

$latex \displaystyle \sum_{n\leq x}r_k(n)=\frac{(\pi x)^{\frac{k}{2}}}{\Gamma(\frac{k}{2}+1)}+O(x^{\frac{k}{2}-1}logx) \ \ \ \ \ (16)&fg=000000$

Remark 8 Notice that this improve the formula 12 which was obtained by the method of packing with a unit square. The exponent $latex {\frac{k}{2}-1}&fg=000000$ in 16 is the best possible because the individual terms of summation can be as large as the error term (apart from $latex {logx}&fg=000000$), indeed for $latex {k=4}&fg=000000$ we have $latex {r_4(n)\geq 16n}&fg=000000$ if $latex {n}&fg=000000$ is odd by the Jacobi formula. The only case of the lattice point problem for a ball which is not yet solved (i.e. the best possible error terms are not yet established) are for the circle($latex {k=2}&fg=000000$) and the sphere ($latex {k=3}&fg=000000$).

Theorem 4

$latex \displaystyle \sum_{n\leq x}\tau(n^2+1)=\frac{3}{\pi}xlogx+O(x) \ \ \ \ \ (17)&fg=000000$

4. Application in finite fields

Suppose $latex {f(x)\in {\mathbb Z}[x]}&fg=000000$ is a irreducible polynomial. And for each prime $latex {p}&fg=000000$, let

$latex \displaystyle \rho_f(p)=\# \ of \ solutions\ of f(x)\equiv 0(mod\ p) \ \ \ \ \ (18)&fg=000000$

By Langrange theorem we know $latex {\rho_f(p)\leq deg(f)}&fg=000000$. Is there a asymptotic formula for

$latex \displaystyle \sum_{p\leq x}\rho_f(p)? \ \ \ \ \ (19)&fg=000000$

A general version, we can naturally generated it to algebraic variety.

$latex \displaystyle \rho_{f_1,…,f_k}(p)=\#\ of \ solutions\ of f_i(x)\equiv 0(mod\ p) ,\ \forall 1\leq i\leq k \ \ \ \ \ (20)&fg=000000$

Is there a asymptotic formula for

$latex \displaystyle \sum_{p\leq x}\rho_{f_1,…,f_k}(p)? \ \ \ \ \ (21)&fg=000000$

Example 1 We give an example to observe what is involved. $latex {f(x)=x^2+1}&fg=000000$. We know $latex {x^2+1\equiv 0 (mod \ p)}&fg=000000$ is solvable iff $latex {p\equiv 1 (mod\ 4)}&fg=000000$ or $latex {p=2}&fg=000000$. One side is easy, just by Fermat little theorem, the other hand need Fermat descent procedure, which of course could be done by Willson theorem. In this case,

$latex \displaystyle \sum_{p\leq n}\rho_f(p)=\# \ of \{primes \ of \ type\ 4k+1 \ in \ 1,2,…,n\} \ \ \ \ \ (22)&fg=000000$

Which is a special case of Dirichlet prime theorem.

Let $latex {K}&fg=000000$ be an algebraic number field, i.e. the finite field extension of rational numbers, let

$latex \displaystyle \mathcal{O}_K=\{\alpha\in K, \alpha \ satisfied \ a\ monic \ polynomial\ in\ {\mathbb Z}[x]\} \ \ \ \ \ (23)&fg=000000$

Dedekind proved that,

Theorem 5

  1. $latex {\mathcal{O}_K}&fg=000000$ is a ring, we call it the ring of integer of $latex {K}&fg=000000$.
  2. He showed further every non-zero ideal of $latex {\mathcal{O}_K}&fg=000000$ could write as the product of prime ideal in $latex {\mathcal{O}_k}&fg=000000$ uniquely.
  3. the index of every non-zero ideal $latex {I}&fg=000000$ in $latex {\mathcal{O}_K}&fg=000000$ is finite, i.e. $latex {[\mathcal{O}_K:I]<\infty}&fg=000000$, and we can define the norm induce by index.

    $latex \displaystyle N(I):=[\mathcal{O}_K:I] \ \ \ \ \ (24)&fg=000000$

    Then the norm is a multiplication function in the space of ideal, i.e. $latex {N(IJ)=N(I)N(J), \forall I,J \in \ ideal\ class\ group\ of\ \mathcal{O}_K}&fg=000000$.

  4. Now he construct the Dedekind Riemann zeta function,

    $latex \displaystyle \zeta_K(s)=\sum_{N(I)\neq 0}\frac{1}{N(I)^s}=\prod_{J\ prime \ ideal\ }\frac{1}{1-\frac{1}{N(J)^s}},\ \forall Re(s)>1 \ \ \ \ \ (25)&fg=000000$

Now we consider the analog of the prime number theorem. Let $latex {\pi_K(x)=\{I,N(I)<x\}}&fg=000000$, does the exist a asymptotic formula,

$latex \displaystyle \pi_K(x)\sim \frac{x}{ln x}\ as\ x\rightarrow \infty? \ \ \ \ \ (26)&fg=000000$

Given a prime $latex {p}&fg=000000$, we may consider the prime ideal

$latex \displaystyle p\mathcal{O}_K=\mathfrak{P}_1^{e_1}\mathfrak{P}_2^{e_2}…\mathfrak{P}_k^{e_k} \ \ \ \ \ (27)&fg=000000$

Where $latex {\mathfrak{P}_i }&fg=000000$ is different prime ideal in $latex {\mathcal{O}_K}&fg=000000$. But the question is how to find these $latex {\mathfrak{P}_i}&fg=000000$? For the question, there is a satisfied answer.

Lemma 6 (existence of primitive element) There always exist a primetive elements in $latex {K}&fg=000000$, such that,

$latex \displaystyle K={\mathbb Q}(\theta) \ \ \ \ \ (28)&fg=000000$

Where $latex {\theta}&fg=000000$ is some algebraic number, which’s minor polynomial $latex {f(x)\in {\mathbb Z}[x]}&fg=000000$.

Theorem 7 (Dedekind recipe) Take the polynomial $latex {f(x)}&fg=000000$, factorize it in the polynomial ring $latex {{\mathbb Z}_p[x]}&fg=000000$,

$latex \displaystyle f(x)\equiv f_1(x)^{e_1}…f_{r}(x)^{e_r}(mod \ p) \ \ \ \ \ (29)&fg=000000$

Consider $latex {\mathfrak{P}_i=(p, f_i(\theta)) \subset \mathcal{O}_K}&fg=000000$. Then apart from finite many primes, we have,

$latex \displaystyle p\mathcal{O}_K=\mathfrak{P}_1^{e_1}\mathfrak{P}_2^{e_2}…\mathfrak{P}_k^{e_k} \ \ \ \ \ (30)&fg=000000$

Where $latex {N(\mathfrak{P}_i)=p^{deg{f_i}}}&fg=000000$.

Remark 9 The apart primes are those divide the discriminant.

Now we can argue that 4 is morally the same as counting the ideals whose norm is divide by $latex {p}&fg=000000$ in a certain algebraic number theory.

And we have following, which is just the version in algebraic number fields of 2.

Theorem 8 (Weber) $latex {\#}&fg=000000$ of ideals of $latex {\mathcal{O}_K}&fg=000000$ with norm $latex {\leq x}&fg=000000$ equal to,

$latex \displaystyle \rho_k(X)+O(x^{1-\frac{1}{d}}), where \ d=[K:Q] \ \ \ \ \ (31)&fg=000000$