MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Many problems in analytic number theory regard the error term in asymptotic formulas. These problems usually take the form: prove that the number theoretic quantity $f(n)$ satisfies $f(n) = G(n) + O(n^{e})$ for some exponent $e$ where $G(n)$ is an elementary function. In many cases lower bounds on the permissible values of $e$ are known.

What are some examples of nontrivial number theoretic problems, particularly asymptotic formulas, where best possible error terms/exponents are known?

share|cite|improve this question

If $r_k(n)$ is the number of representations of $n$ as a sum of $k$ squares, and $k\geq 5$, then the estimate

$\sum_{n \leq X}r_k(n)=C_k X^{\frac{k}{2}}+O(X^{\frac{k}{2}-1})$

is known, and is best possible, because $r_k(n) \neq o(n^{\frac{k}{2}-1})$.

share|cite|improve this answer
Could you give me a reference for this? – Mark Lewko Apr 28 '10 at 19:06
Sure, it's in chapter one of Iwaniec and Kowalski's book on analytic number theory. – David Hansen Apr 28 '10 at 19:29

It's a nice question. As you know the best orders of the error terms in most important asymptotic formulas are still unknown. (Riemann Hypothesis as the best error term in PNT, Dirichlet's divisor problem, Gauss circle problem etc.)

A few examples of asymptotics that come to mind, that are useful and (some of them, kind of?) sharp include:

  • The Sato-Tate conjecture, which is proven in many cases
  • The theorem of Bombieri-Vinogradov, concerning the error term in the prime number theorem for arithmetic progressions, is a very strong result and unconditional replacement of the error predicted by GRH. However this is not optimal as you can see from the Elliott-Halberstam conjecture.
  • The fundamental lemma of sieve theory.
  • Results like: Denote the number of prime factors of $n$ counting multiplicity by $\Omega(n)$, then $$\# \{n\le x |\Omega(n)\equiv j\mod m \}=\frac{x}{m}+O\left(\frac{x}{\log^k x}\right)$$ for some $k>0$, and the error term is not $o(x^k)$ for any $1>k$.
  • The divisor bound $d(n)\le \exp((1+\epsilon)\log 2 \log n/\log \log n)$, which holds for any $\epsilon>0$ and sufficiently large $n$, but is false for any negative $\epsilon$,
  • Smoothing sums! from the Tricki. This is not a sharp estimate but more of a technique of how to find one.(and I really like the article)
share|cite|improve this answer
Which one is of the form $G(n)+O(G_1(n))$ with $G_1(n)=o(G(n))$ and sharp? – Wadim Zudilin Apr 20 '10 at 10:25
There are some examples of sharp estimates for counting lattice points in certain domains, but here an expertise of somebody from analytic number theory is required. – Wadim Zudilin Apr 20 '10 at 10:32
Sato-Tate is definitely of that form :) and so is Bombieri-Vinogradov(but is not sharpest ) – Gjergji Zaimi Apr 20 '10 at 10:36
I agree with your second comment, of course. – Gjergji Zaimi Apr 20 '10 at 10:38
Note: Sato--Tate is now proved in general (even for elliptic curves over totally real fields). – Emerton Apr 20 '10 at 15:32

Let $\omega(n)$ denote the number of distinct prime factors of $n$ and $\Phi(\cdot)$ denote the Normal distribution with mean $0$ and variance $1$. Then, uniformly in $t$, the number of integers $n \leq x$ with $\omega(n) \leq \log\log n + t \sqrt{\log\log n}$ is $$\Phi(t) + O\left(\frac{1}{\sqrt{\log\log x}}\right)$$ as $x \rightarrow \infty$. The error term is sharp.

This particular error term was conjectured to hold by Leveque in the 40's. His conjecture was settled a few years later by Erdos and Renyi.

Before Erdos and Renyi's paper the best error term was $O(\log\log\log x / \sqrt{\log\log x})$ and was due (if I recall correctly) to Kubilius. Kubilius's method was in its origin probabilistic and relied in an essential way on truncating the "random variable" $\omega(n)$. This introduced an additional factor of $\log\log\log x$ to the error term, as inevitably, truncation leads to loss of information.

In contrast, Renyi's and Erdos's method was purely analytic: the idea was to estimate $\sum_{n \leq x} exp(\text{i}t \omega(n))$ uniformly in $t$ in a certain range, and extract the desired conclusion from the behavior of this sum. To this end, they apply Berry-Esseen's theorem, but in principle one could use an more hands-on approach: smooth the indicator function of $\omega(n) \leq \log\log n + t \sqrt{\log\log n}$ and express it in terms of a variant of Perron's formula, after summing the resulting expression over $n \leq x$ one could proceed with the saddle-point method.

However when purely analytic methods are not directly accessible, Kubilius's method is the canonical method. For example suppose that you want to investigate the distribution of $\omega(n)$ over a peculiar subset of $[1,x]$ on which sieve methods -- but not "heavy" analytic methods -- are applicable, then Kubilius's method is still your best bet.

(As far as terminology is concerned it's "Kubilius model's" rather than "Kubilius's method"; more details about "Kubilius's model" can be found in Volume 1 of Elliott's "Probabilistic Number Theory").

share|cite|improve this answer

Let $0\le a<b$ and $l(a/b)$ be the length of continued fraction expansion $a/b=[0;q_1,\ldots,a_l]$. Then (see Asymptotic behaviour of the first and second moments for the number of steps in the Euclidean algorithm) $$\frac{2}{R(R+1)}\sum_{0\le a\le b\le R}l(a/b)=\frac{2\log2}{\zeta(2)}\log R+C+O(R^{-1}\log ^5R).$$

According to numerical experiments this error term is best possible up to some power of $\log R$. (Optimality is not proved so far.)

share|cite|improve this answer

It's probably not what you were thinking of, but very precise versions of Stirling's approximation to the factorial are known.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.