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 have been playing around with the Möbius Function and primorials and I am finding results that I am not yet able to understand which I suspect are very elementary.

Here's the current result which is I am working through. Any help is greatly appreciated!

Let $p_k$ be any prime. Let $x$ be any integer.

It seems based on my calculations that $\sum_{i | p_{k}\\#} \lfloor{\frac{(x \% i) + (p_k \% i)}{i}}\rfloor\mu(i) \ge -1$

where % is the remainder so that $5 \% 3 = 2$ and $7 \% 3 = 1$

But if we let $x,y$ be any integer, we can find that there exists $x,y$ such that:

$\sum_{i | p_{k}\\#} \lfloor{\frac{(x \% i) + (y \% i)}{i}}\rfloor\mu(i) < -1$

For example:

If $x=13$, $y=23$, $p_k = 5$ , then the sum is $-2$

Is there a well known explanation for this? Thanks.

share|cite|improve this question
Perhaps I'm misunderstanding your notation, but in the case $x=13,y=23,p=5$, I get that the sum is $1 + 1 - \lfloor (3 + 3) / 5 \rfloor = 1$. What is the significance of the #? – Daniel Loughran Jul 11 '12 at 16:13
Right, I see now. $p$# means the primorial of p. – Daniel Loughran Jul 11 '12 at 16:22
up vote 14 down vote accepted

Note that

$$ \lfloor \frac{a \% p + b \% p}{p} \rfloor = \lfloor \frac{a+b}{p} \rfloor - \lfloor \frac{a}{p} \rfloor - \lfloor \frac{b}{p} \rfloor$$

so your expression can be written as $F_{p_k\\#}(x+p_k) - F_{p_k\\#}(x) - F_{p_k\\#}(p_k)$, where

$$ F_n(x) := \sum_{i|n} \lfloor \frac{x}{i} \rfloor \mu(i).$$

Now, the expression $F_n$ can be simplified by elementary number theoretic computations. Indeed, observe that

$$ \lfloor \frac{x}{i} \rfloor = \sum_{m \leq x: i|m} 1$$

and thus after interchanging summations,

$$ F_n(x) = \sum_{m \leq x} \sum_{i|n, i|m} \mu(i).$$

But by Mobius inversion, $\sum_{i|n, i|m} \mu(i)$ equals 1 when n,m are coprime and 0 otherwise. Thus $F_n(x)$ is nothing more than the number of natural numbers $m$ less than $x$ that are coprime to $n$. In particular, this gives

$$ F_{p_k\\#}(x+p_k) \geq F_{p_k\\#}(x)$$


$$ F_{p_k\\#}(p_k) = 1$$

which explains your numerically observed phenomenon.

The quantities here are somewhat reminiscent of the quantity $\pi(x+y)-\pi(x)-\pi(y)$ that occurs in the second Hardy-Littlewood conjecture (which, by the way, is widely believed to be false). Indeed, the quantity $F_{p_k\\#}(x)$ (that is, the number of natural numbers up to x that have no prime factor less than or equal to $p_k$) is more commonly denoted $\pi(x,p_k)$ in the analytic number theory literature.

EDIT: I also encountered some related expressions and inequalities in my paper (and with more advanced versions of these inequalities also in this paper of Granville and Soundararajan: ).

share|cite|improve this answer
Thanks, Terry! I really appreciate your analysis! :-) I look forward to reading the articles you cited! Cheers, -Larry – Larry Freeman Jul 12 '12 at 15:43

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.