2
$\begingroup$

I'm new to asymptotic operation so I need help to understand it. As I know $\mathcal{O(x)}$ is a set of functions. In Selberg's paper about elementary proof of prime number theorem there is that equation,

$$x\sum_{d\leq x}\frac{\mu(d)}{d}\log^2\frac{x}{d}+\mathcal{O}\left(\sum_{d\leq x}\log^2\frac{x}{d}\right)=x\sum_{d\leq x}\frac{\mu(d)}{d}\log^2\frac{x}{d}+\mathcal{O(x)}$$

What is happening when you get into left side? You can say that equation holds because $\mathcal{O(\sum_{d\leq x}\log^2\frac{x}{d}}) \in \mathcal{O(x)}$

is that the reason? $x$ is upper bound for $\log^2x$?

$\endgroup$
7
  • 1
    $\begingroup$ Are you familiar with the big-$O$ notation? $\endgroup$
    – lcv
    Commented Jul 3 at 15:15
  • 1
    $\begingroup$ No. That's why I'm asking it. $\endgroup$
    – user1127460
    Commented Jul 3 at 15:48
  • $\begingroup$ en.m.wikipedia.org/wiki/Big_O_notation $\endgroup$
    – lcv
    Commented Jul 3 at 21:26
  • 1
    $\begingroup$ In general you write $f(x) = O(g(x))$ not $\in$ $\endgroup$
    – lcv
    Commented Jul 3 at 21:27
  • $\begingroup$ If we let $f(x)= \sum_{d\leq x}\log^2\frac{x}{d}$ and $g(x)=x$ you would need that $f(x)\leq k g(x)$ and $g(x)\leq mf(x)$ for some constants k and m, and x sufficiently large. I am not an expert on number theory, but this seems like a nontrivial fact. $\endgroup$
    – Cheerful Parsnip
    Commented Jul 4 at 0:42

2 Answers 2

Reset to default
1
$\begingroup$

We have that,

$ \int_1^x (\log \frac{x}{t})^2 \,dt= 2x-(\log x)^2-2\log x-2=O(x). $

So we calculate using Riemann-Stieltjes integration:

$ \sum_{d\leq x}(\log \frac{x}{d})^2 =\int_1^x(\log\frac{x}{t})^2\,d[t]=\int_1^x(\log\frac{x}{t})^2\,dt-\int_1^x(\log\frac{x}{t})^2\,d\{t\}. $

As noted, the first integral is $O(x)$ as $x\to\infty$ and the second one we solve using integration by parts obtaining a term which is $O((\log x)^2)$. And this last term itself is also of order $O(x)$.

$\endgroup$
0
$\begingroup$

If I remember correctly, this big-oh notation was first introduced by the German mathematician Edmund Landau (1877-1938).

Nowadays, every analytic number theorist may be familiar with this (I am not sure if this useful notation is a common knowledge of all mathematicians, though). It is natural that people get troubles with things that they encounter for the first time in their life. Let us just use and be familiar.

The big-oh notation $O(\cdot)$ is just a way to describe some function; it itself doesn't give us anything new.

In English, $O(f)$ means "a function $g$ which satisfies the inequality \[ |g(x)| \leq A |f(x)| \] for some constant $A$ and all $x$ in some set".

For example, the function $1/x$ as $x \to \infty$ is $O(1)$; there is a constant $A$ (say $1$) such that \[ 1/x \leq A \] for all large $x$.

It doesn't give us anything new, but is a very convenient notation; as we step forwards on our argument, we need to keep recognizing, at each step, what is a major term and what are minors. And very intricate-looking minor terms can be just simplified as $O(f)$.

$\endgroup$

You must log in to answer this question.