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

I'm trying to work with the following sum: $$f:=\sum_{d\leq x}\mu(d)\tau(d) \Big[ \frac{x}{d}\Big] $$ Where $\mu$ is the Mobius function, $\tau(n)$ is the number of positive divisors of $n$ and $h(x)=[x]$ is the floor function.

We know that $$\sum_{d\leq x} \mu(d)\Big[ \frac{x}{d}\Big]=1,$$ $$ \sum_{d\leq x} \Big[ \frac{x}{d} \Big] \sim x\log(x),$$ $$\sum_{x\leq d} \frac{x}{d} \sim x\ln(x), $$ but what happens if we throw $\tau$ into the mix? Is it similar to $$g:=\sum_{d\leq x}\mu(d)\tau(d)\frac{x}{d}?$$ Or is it similar to multiple of $g$? I've tried Mobius inversion with a few different declarations of $f,g$ but either I'm simply not seeing it, or it doesn't work. Any ideas?

share|cite|improve this question
Have you computed $f$ for $x$ up to, say, 1000, to see what might happen? – Gerry Myerson Sep 3 '12 at 22:39
up vote 5 down vote accepted

First, unraveling the floor function your sum is the same as $$\sum_{d\leq x}\left(1*\mu\tau\right)(d)$$ where $*$ represents mobius convolution. Let $f(n)$ denote the above multiplicative function. Then $f(1)=1$, and $f(p^k)=-1$ for $k\geq 2$.

This means that $f=\mu$, Mobius function, on all but the prime powers, and you can deduce that $$\sum_{d\leq x}\mu(d)\tau(d)\left[\frac{x}{d}\right]\ll \frac{x}{\log x}.$$

Added: There are many ways to prove this last statement, but allow me to outline one you may not have seen. I won't make things too precise, I encourage you to look up the papers of the authors mentioned below.

Granville and Soundararajan define the distance up to $x$ between two bounded multiplicative functions $f,g:\mathbb{N}\rightarrow \mathbb{U}$ to be $$\mathbb{D}(f,g,x)=\sum_{p\leq x} \frac{1-\text{Re}f(p)\bar{g}(p)}{p}.$$ This distance tells us an enormous amount about what the mean of a multiplicative function will look like. If two functions are close together, then their means will be close as well. More remarkably, a Theorem of Halasz tells us that unless the distance between $f$ and $n^{it}$ is close for some $|t|\ll \log x$, the mean of $f$ will go to $0$, that is $\sum_{n\leq x}f(n)=o(x)$. In other words, the only bounded multiplicative functions with a nonzero mean are really close to $n^{it}$ for some $t$.

share|cite|improve this answer
As I recall, last year Alex Botros was a high school student from New York (I am willing to be corrected). I am sure he will ask for more clarity as needed, but I might suggest a little expansion on your remarks for encouragement. I know I would like it. Gerhard "Ask Me About System Design" Paseman, 2012.09.03 – Gerhard Paseman Sep 4 '12 at 2:03

Here is $f(n)$ for $n \le 1000$, as per Gerry Myerson's suggestion:
    f(n) n<=1000
Hopefully I computed it correctly. $f(10)=-4$, $f(100)=14$, $f(1000)=64$ if anyone wants to check.

Following Kevin O'Bryant's suggestion, $f(n)$ is the "Little omega analogue to Liouville's function $L(n)$," $$-5, -4, -5, -4, -3, -4, -5, -4, -5, -4,$$ $$-3, -2, -3, -2, -3, -2, -3, -2, -3, -4,$$ $$-5, -6, -5, -4, -3, -2, -3, -2, -1, 0,$$

Two quotes from OEIS:

Except for the two zeros and the intervening foray into negative territory shown here, the first thousand terms are all positive. The next zero occurs at term 7960. After the zero at term 12100, the function stays negative until term 22395666.

It appears certain that this sequence and the Liouville sequence are equal infinitely often.

share|cite|improve this answer
I suspect that $f(1) \geq 0$. Gerhard "Ask Me About System Design" Paseman, 2012.09.03 – Gerhard Paseman Sep 3 '12 at 23:58
Although I can believe that f(10) is negative. Gerhard "Perhaps That's What Was Meant" Paseman, 2012.09.03 – Gerhard Paseman Sep 4 '12 at 0:00
@Gerhard: Whoops, yep, that was supposed to be $f(10)$. Now corrected. For $f(10)$, for $d=1,\ldots,10$, I get terms $10,-10,-6,0,-4,4,-2,0,0,4$, whose sum is $-4$. – Joseph O'Rourke Sep 4 '12 at 0:07
Have you asked superseeker/OEIS about the first 10 terms? – Kevin O'Bryant Sep 4 '12 at 0:13
Brilliant, Kevin! – Joseph O'Rourke Sep 4 '12 at 0:39

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.