I read this identity in lecture notes and need help understand ing the $O$ function

$$\sum_{1\leq d\leq x}\mu(d)\cdot \frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac xd\right\rfloor+1\right)=\sum_{1\leq d\leq x}\mu(d)\left(\frac{x^2}{2d^2}+O(x/d)\right)$$

Attempt: This implies

$$\frac{1}{2}\left\lfloor\frac xd\right\rfloor\left(\left\lfloor\frac xd\right\rfloor+1\right)=\frac{x^2}{2d^2}+O(x/d)$$

From the definition of $\left\lfloor\theta\right\rfloor$ being the greatest integer not exceeding $\theta$

I can see that $\left\lfloor\frac xd\right\rfloor=x/d+O(1)$,

But substituting this in cannot lead to an expression with $O(x/d)$, where does this come from?

How do I derive this expression

  • $\begingroup$ Um, what? What is $c$? And $O$ is used for estimation, but what you've stated is an exact equality. You'd pretty much never us $O$ in a proof of an equality, unless the equality included limits. $\endgroup$ – Thomas Andrews May 21 '15 at 12:34
  • $\begingroup$ Corrected the 'c' part $\endgroup$ – Sam Houston May 21 '15 at 12:38
  • $\begingroup$ Also, the limits are set by the summation sign $\endgroup$ – Sam Houston May 21 '15 at 12:39

Let's realize what you really want is:

$$\lfloor y\rfloor (\lfloor y\rfloor +1)=y^2+O(y)$$

Let $f(y)=y(y+1)$. Then $f(y)-f(\lfloor y\rfloor) = f'(z) (y-\lfloor y\rfloor)$ for some $z\in [\lfloor y\rfloor, y]\subseteq (y-1,y]$.

But $f'(z)=2z+1$ so $f'(z)= O(y)$ when $z\in (y-1,y]$, and $0\leq y-\lfloor y\rfloor <1$, so $f(y)-f(\lfloor y\rfloor) = O(y)$ and $f(y)=y^2+O(y)$.

So $$f(\lfloor y\rfloor)=f(y)-(f(y)-f(\lfloor y\rfloor) = y^2 + O(y) - O(y)= y^2+O(y).$$


$$\frac{1}{2}[x/d]([x/d]+1)=\frac12\left(\frac xd+O(1)+1\right)\left(\frac xd+O(1)\right)=\frac{x^2}{2d^2}+\frac xdO(1)+O'(1)\\ =\frac{x^2}{2d^2}+O''\left(\frac xd\right).$$

  • $\begingroup$ Could you elaborate on the last equality please, still confused by that, what is the realationship betweeen $O(1)$ and $O(x/d)$ $\endgroup$ – Sam Houston May 21 '15 at 12:42
  • $\begingroup$ Do you know the big-$O$ notation ? $\endgroup$ – Yves Daoust May 21 '15 at 12:43
  • $\begingroup$ I am working on becoming more familiar with it, not clear on it yet $\endgroup$ – Sam Houston May 21 '15 at 12:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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