Integers with a divisor in a given interval

132 Views Asked by At

Please bear with me, I have a notation question.

In Kevin Ford's paper with the above title, the following statement occurs in Theorem T1, p. 369:

If $2 ≤ y ≤ z ≤ x$, then $$H(x, y, z) = x\left(1 + O\left(\frac{\log y}{\log z}\right)\right),$$ where $H(x, y, z)$ isthe number of positive integers $n ≤ x$ with a divisor in $(y,z].$ Now since $$H(x,y,z)\leq x-1$$ clearly holds, is the $O$ notation to be taken with an implied negative constant? Does this equation actually say that $$H(x,y,z) \geq x\left(1-c\frac{\log y}{\log z}\right)$$ for some universal constant $c$?

1

There are 1 best solutions below

0
On BEST ANSWER

The short answer to your question is yes.

To convince oneself, let's recall the definition of Big-$O$ notation. The exact definition can vary slightly, but most often we write $f(x)=O(g(x))$ when there exists constants $x_0$ and $C$ such that $|f(x)|\leq Cg(x)$ for all $x\geq x_0$. Often the condition that this holds for $x>x_0$ doesn't matter and it is just there to avoid strange oscillatory behavior that could happen early on. In practice it is equivalent to it holding for all $x$, and different people sometimes use a slightly different definition for this reason.

Thus in our case $$H(x,y,z)-x=O\left(x\frac{\log y}{\log z}\right)$$ means that there exists $x_0$ and $c$ such that $$|H(x,y,z)-x|\leq c x\frac{\log y}{\log z}$$ for all $x\geq x_0$, and since the term inside the absolute values must be negative, we arrive at $$H(x,y,z)\geq x\left(1- c \frac{\log y}{\log z}\right)$$ for all $x>x_0$.

To address whether the $x>x_0$ part is important in the definition, note that in this case (and many cases) it can be removed in the following way: For $x<x_0$, $\frac{\log y}{\log z}\geq \frac{\log 2}{\log x_0}$, and so by taking $c'=\max\{c,1\}\frac{\log x_0}{\log 2}$ we see that $$H(x,y,z)\geq x\left(1- c' \frac{\log y}{\log z}\right)$$ holds for all $x$, since the inequality holds trivially when $x<x_0$ as the right hand side will be negative.